001: /*
002: * xtc - The eXTensible Compiler
003: * Copyright (C) 2004-2007 Robert Grimm
004: *
005: * This program is free software; you can redistribute it and/or
006: * modify it under the terms of the GNU General Public License
007: * version 2 as published by the Free Software Foundation.
008: *
009: * This program is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
012: * GNU General Public License for more details.
013: *
014: * You should have received a copy of the GNU General Public License
015: * along with this program; if not, write to the Free Software
016: * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
017: * USA.
018: */
019: package xtc.parser;
020:
021: import java.util.HashMap;
022: import java.util.Iterator;
023: import java.util.List;
024: import java.util.Map;
025:
026: import xtc.tree.Attribute;
027: import xtc.tree.Visitor;
028:
029: /**
030: * Visitor to test productions and elements for equivalence. This
031: * visitor tests whether two productions or two elements are
032: * structurally the same, modulo using different variable names and
033: * having different nonterminals (for productions). It should only be
034: * invoked through the {@link #areEquivalent(Production,Production)}
035: * and {@link #areEquivalent(Element,Element)} methods.
036: *
037: * @author Robert Grimm
038: * @version $Revision: 1.36 $
039: */
040: public class EquivalenceTester extends Visitor {
041:
042: /** The mapping between equivalent nonterminals. */
043: protected Map<String, String> nts;
044:
045: /** The mapping between equivalent variables. */
046: protected Map<String, String> vars;
047:
048: /** The element to compare to. */
049: protected Element e2;
050:
051: /** Create a new equivalence tester. */
052: public EquivalenceTester() {
053: nts = new HashMap<String, String>();
054: vars = new HashMap<String, String>();
055: }
056:
057: /**
058: * Determine whether the specified productions are equivalent.
059: *
060: * @param p1 The first production.
061: * @param p2 The second production.
062: * @return <code>true</code> if the two productions are equivalent.
063: */
064: public boolean areEquivalent(Production p1, Production p2) {
065: if (!Attribute.areEquivalent(p1.attributes, p2.attributes))
066: return false;
067: if (null == p1.type) {
068: if (!p1.dType.equals(p2.dType))
069: return false;
070: } else {
071: if (!p1.type.equals(p2.type))
072: return false;
073: }
074:
075: nts.put(p2.name.name, p1.name.name);
076: boolean result = areEquivalent(p1.choice, p2.choice);
077: nts.remove(p2.name.name);
078:
079: return result;
080: }
081:
082: /**
083: * Determine whether the specified elements are equivalent.
084: *
085: * @param e1 The first element.
086: * @param e2 The second element.
087: * @return <code>true</code> if the two elements are equivalent.
088: */
089: public boolean areEquivalent(Element e1, Element e2) {
090: if ((null == e1) || (null == e2))
091: return (e1 == e2);
092: if (!e1.getClass().equals(e2.getClass()))
093: return false;
094: this .e2 = e2;
095: return (Boolean) dispatch(e1);
096: }
097:
098: /**
099: * Determine whether the specified lists of bindings are equivalent.
100: *
101: * @param l1 The first list.
102: * @param l2 The second list.
103: * @return <code>true</code> if the two lists are equivalent.
104: */
105: protected boolean areEquivalent(List<Binding> l1, List<Binding> l2) {
106: if (l1.size() != l2.size())
107: return false;
108:
109: Iterator<Binding> iter1 = l1.iterator();
110: Iterator<Binding> iter2 = l2.iterator();
111:
112: while (iter1.hasNext()) {
113: String var1 = iter1.next().name;
114: String var2 = iter2.next().name;
115:
116: if ((!var1.equals(var2)) && (!var1.equals(vars.get(var2)))) {
117: return false;
118: }
119: }
120:
121: return true;
122: }
123:
124: /**
125: * Determine whether the specified generic values are equivalent.
126: *
127: * @param v1 The first value.
128: * @param v2 The second value.
129: * @return <code>true</code> if the two values are equivalent.
130: */
131: protected boolean areEquivalent(GenericValue v1, GenericValue v2) {
132: if ((!v1.name.equals(v2.name))
133: && (!v1.name.equals(nts.get(v2.name)))) {
134: return false;
135: }
136:
137: return areEquivalent(v1.children, v2.children);
138: }
139:
140: /** Visit the specified ordered choice. */
141: public Boolean visit(OrderedChoice c1) {
142: OrderedChoice c2 = (OrderedChoice) e2;
143: final int l = c1.alternatives.size();
144:
145: if (l != c2.alternatives.size()) {
146: return Boolean.FALSE;
147: } else {
148: for (int i = 0; i < l; i++) {
149: if (!areEquivalent(c1.alternatives.get(i),
150: c2.alternatives.get(i))) {
151: return Boolean.FALSE;
152: }
153: }
154:
155: return Boolean.TRUE;
156: }
157: }
158:
159: /** Visit the specified repetition. */
160: public Boolean visit(Repetition r1) {
161: Repetition r2 = (Repetition) e2;
162:
163: if (r1.once != r2.once) {
164: return Boolean.FALSE;
165: } else {
166: return areEquivalent(r1.element, r2.element);
167: }
168: }
169:
170: /** Visit the specified sequence. */
171: public Boolean visit(Sequence s1) {
172: Sequence s2 = (Sequence) e2;
173: final int l = s1.elements.size();
174:
175: if (l != s2.elements.size()) {
176: return Boolean.FALSE;
177: } else {
178: for (int i = 0; i < l; i++) {
179: if (!areEquivalent(s1.elements.get(i), s2.elements
180: .get(i))) {
181: return Boolean.FALSE;
182: }
183: }
184: return Boolean.TRUE;
185: }
186: }
187:
188: /** Visit the specified binding. */
189: public Boolean visit(Binding b1) {
190: Binding b2 = (Binding) e2;
191:
192: if (b1.name.equals(b2.name)) {
193: return areEquivalent(b1.element, b2.element);
194:
195: } else {
196: String alt = vars.get(b2.name);
197:
198: if (null == alt) {
199: // There is no mapping between b1 and b2. Try it.
200: vars.put(b2.name, b1.name);
201: boolean result = areEquivalent(b1.element, b2.element);
202: vars.remove(b2.name);
203: return result;
204:
205: } else if (!b1.name.equals(alt)) {
206: // There is a mapping and it is different.
207: return Boolean.FALSE;
208:
209: } else {
210: // There is a mapping and it fits.
211: return areEquivalent(b1.element, b2.element);
212: }
213: }
214: }
215:
216: /** Visit the specified string match. */
217: public Boolean visit(StringMatch m1) {
218: StringMatch m2 = (StringMatch) e2;
219:
220: return m1.text.equals(m2.text)
221: && areEquivalent(m1.element, m2.element);
222: }
223:
224: /** Visit the specified nonterminal. */
225: public Boolean visit(NonTerminal nt1) {
226: NonTerminal nt2 = (NonTerminal) e2;
227:
228: return nt1.equals(nt2) || nt1.name.equals(nts.get(nt2.name));
229: }
230:
231: /** Visit the specified character switch. */
232: public Boolean visit(CharSwitch s1) {
233: CharSwitch s2 = (CharSwitch) e2;
234: final int l = s1.cases.size();
235:
236: if (l != s2.cases.size()) {
237: return Boolean.FALSE;
238: } else {
239: for (int i = 0; i < l; i++) {
240: CharCase c1 = s1.cases.get(i);
241: CharCase c2 = s2.cases.get(i);
242:
243: if (!areEquivalent(c1.klass, c2.klass)) {
244: return Boolean.FALSE;
245: } else if (!areEquivalent(c1.element, c2.element)) {
246: return Boolean.FALSE;
247: }
248: }
249: }
250:
251: if (null == s1.base) {
252: return null == s2.base;
253: } else {
254: if (null == s2.base) {
255: return Boolean.FALSE;
256: } else {
257: return areEquivalent(s1.base, s2.base);
258: }
259: }
260: }
261:
262: /** Visit the specified parse tree node. */
263: public Boolean visit(ParseTreeNode n1) {
264: ParseTreeNode n2 = (ParseTreeNode) e2;
265:
266: if (!areEquivalent(n1.predecessors, n2.predecessors)) {
267: return Boolean.FALSE;
268: }
269:
270: if ((null == n1.node) != (null == n2.node))
271: return Boolean.FALSE;
272:
273: if ((null != n1.node) && (!n1.node.name.equals(n2.node.name))
274: && (!n1.node.name.equals(vars.get(n2.node.name)))) {
275: return Boolean.FALSE;
276: }
277:
278: return areEquivalent(n1.successors, n2.successors);
279: }
280:
281: /** Visit the specified proper list value. */
282: public Boolean visit(ProperListValue v1) {
283: ProperListValue v2 = (ProperListValue) e2;
284:
285: if (!v1.type.equals(v2.type))
286: return Boolean.FALSE;
287: if (!areEquivalent(v1.elements, v2.elements))
288: return Boolean.FALSE;
289: if ((null == v1.tail) != (null == v2.tail))
290: return Boolean.FALSE;
291: return ((null == v1.tail) || v1.tail.name.equals(v2.tail.name) || v1.tail.name
292: .equals(vars.get(v2.tail.name)));
293: }
294:
295: /** Visit the specified binding value. */
296: public Boolean visit(BindingValue v1) {
297: BindingValue v2 = (BindingValue) e2;
298:
299: return (v1.binding.name.equals(v2.binding.name) || v1.binding.name
300: .equals(vars.get(v2.binding.name)));
301: }
302:
303: /** Visit the specified action base value. */
304: public Boolean visit(ActionBaseValue v1) {
305: ActionBaseValue v2 = (ActionBaseValue) e2;
306:
307: return ((v1.list.name.equals(v2.list.name) || v1.list.name
308: .equals(vars.get(v2.list.name))) && (v1.seed.name
309: .equals(v2.seed.name) || v1.seed.name.equals(vars
310: .get(v2.seed.name))));
311: }
312:
313: /** Visit the specified generic node value. */
314: public Boolean visit(GenericNodeValue v1) {
315: GenericNodeValue v2 = (GenericNodeValue) e2;
316:
317: return areEquivalent(v1, v2)
318: && areEquivalent(v1.formatting, v2.formatting);
319: }
320:
321: /** Visit the specified generic action value. */
322: public Boolean visit(GenericActionValue v1) {
323: GenericActionValue v2 = (GenericActionValue) e2;
324:
325: if (!areEquivalent(v1, v2))
326: return Boolean.FALSE;
327:
328: if ((!v1.first.equals(v2.first))
329: && (!v1.first.equals(vars.get(v2.first)))) {
330: return Boolean.FALSE;
331: }
332:
333: return areEquivalent(v1.formatting, v2.formatting);
334: }
335:
336: /** Visit the specified generic recursion value. */
337: public Boolean visit(GenericRecursionValue v1) {
338: GenericRecursionValue v2 = (GenericRecursionValue) e2;
339:
340: if (!areEquivalent(v1, v2))
341: return Boolean.FALSE;
342:
343: if ((!v1.first.equals(v2.first))
344: && (!v1.first.equals(vars.get(v2.first)))) {
345: return Boolean.FALSE;
346: }
347:
348: if (!areEquivalent(v1.formatting, v2.formatting)) {
349: return Boolean.FALSE;
350: }
351:
352: return (v1.list.name.equals(v2.list.name) || v1.list.name
353: .equals(vars.get(v2.list.name)));
354: }
355:
356: /**
357: * Visit the specified unary operator. This method provides the
358: * default implementation for options, predicates, voided elements,
359: * and parser actions.
360: */
361: public Boolean visit(UnaryOperator op1) {
362: UnaryOperator op2 = (UnaryOperator) e2;
363:
364: return areEquivalent(op1.element, op2.element);
365: }
366:
367: /**
368: * Visit the specified element. This method provides the default
369: * implementation for terminals, node markers, null literals,
370: * actions, and null, string, text, empty list, generic string, and
371: * generic text values.
372: */
373: public Boolean visit(Element e1) {
374: return e1.equals(e2);
375: }
376:
377: }
|