001: package persistence.antlr;
002:
003: /* ANTLR Translator Generator
004: * Project led by Terence Parr at http://www.jGuru.com
005: * Software rights: http://www.antlr.org/license.html
006: *
007: */
008:
009: import persistence.antlr.collections.AST;
010: import persistence.antlr.collections.ASTEnumeration;
011: import persistence.antlr.collections.impl.ASTEnumerator;
012: import persistence.antlr.collections.impl.Vector;
013:
014: import java.io.Serializable;
015: import java.io.IOException;
016: import java.io.Writer;
017:
018: /**
019: * A Child-Sibling Tree.
020: *
021: * A tree with PLUS at the root and with two children 3 and 4 is
022: * structured as:
023: *
024: * PLUS
025: * |
026: * 3 -- 4
027: *
028: * and can be specified easily in LISP notation as
029: *
030: * (PLUS 3 4)
031: *
032: * where every '(' starts a new subtree.
033: *
034: * These trees are particular useful for translators because of
035: * the flexibility of the children lists. They are also very easy
036: * to walk automatically, whereas trees with specific children
037: * reference fields can't easily be walked automatically.
038: *
039: * This class contains the basic support for an AST.
040: * Most people will create ASTs that are subclasses of
041: * BaseAST or of CommonAST.
042: */
043: public abstract class BaseAST implements AST, Serializable {
044: protected BaseAST down;
045: protected BaseAST right;
046:
047: private static boolean verboseStringConversion = false;
048: private static String[] tokenNames = null;
049:
050: /**Add a node to the end of the child list for this node */
051: public void addChild(AST node) {
052: if (node == null)
053: return;
054: BaseAST t = this .down;
055: if (t != null) {
056: while (t.right != null) {
057: t = t.right;
058: }
059: t.right = (BaseAST) node;
060: } else {
061: this .down = (BaseAST) node;
062: }
063: }
064:
065: /** How many children does this node have? */
066: public int getNumberOfChildren() {
067: BaseAST t = this .down;
068: int n = 0;
069: if (t != null) {
070: n = 1;
071: while (t.right != null) {
072: t = t.right;
073: n++;
074: }
075: return n;
076: }
077: return n;
078: }
079:
080: private void doWorkForFindAll(Vector v, AST target,
081: boolean partialMatch) {
082: AST sibling;
083:
084: // Start walking sibling lists, looking for matches.
085: siblingWalk: for (sibling = this ; sibling != null; sibling = sibling
086: .getNextSibling()) {
087: if ((partialMatch && sibling.equalsTreePartial(target))
088: || (!partialMatch && sibling.equalsTree(target))) {
089: v.appendElement(sibling);
090: }
091: // regardless of match or not, check any children for matches
092: if (sibling.getFirstChild() != null) {
093: ((BaseAST) sibling.getFirstChild()).doWorkForFindAll(v,
094: target, partialMatch);
095: }
096: }
097: }
098:
099: /** Is node t equal to this in terms of token type and text? */
100: public boolean equals(AST t) {
101: if (t == null)
102: return false;
103: return this .getText().equals(t.getText())
104: && this .getType() == t.getType();
105: }
106:
107: /** Is t an exact structural and equals() match of this tree. The
108: * 'this' reference is considered the start of a sibling list.
109: */
110: public boolean equalsList(AST t) {
111: AST sibling;
112:
113: // the empty tree is not a match of any non-null tree.
114: if (t == null) {
115: return false;
116: }
117:
118: // Otherwise, start walking sibling lists. First mismatch, return false.
119: for (sibling = this ; sibling != null && t != null; sibling = sibling
120: .getNextSibling(), t = t.getNextSibling()) {
121: // as a quick optimization, check roots first.
122: if (!sibling.equals(t)) {
123: return false;
124: }
125: // if roots match, do full list match test on children.
126: if (sibling.getFirstChild() != null) {
127: if (!sibling.getFirstChild().equalsList(
128: t.getFirstChild())) {
129: return false;
130: }
131: }
132: // sibling has no kids, make sure t doesn't either
133: else if (t.getFirstChild() != null) {
134: return false;
135: }
136: }
137: if (sibling == null && t == null) {
138: return true;
139: }
140: // one sibling list has more than the other
141: return false;
142: }
143:
144: /** Is 'sub' a subtree of this list?
145: * The siblings of the root are NOT ignored.
146: */
147: public boolean equalsListPartial(AST sub) {
148: AST sibling;
149:
150: // the empty tree is always a subset of any tree.
151: if (sub == null) {
152: return true;
153: }
154:
155: // Otherwise, start walking sibling lists. First mismatch, return false.
156: for (sibling = this ; sibling != null && sub != null; sibling = sibling
157: .getNextSibling(), sub = sub.getNextSibling()) {
158: // as a quick optimization, check roots first.
159: if (!sibling.equals(sub))
160: return false;
161: // if roots match, do partial list match test on children.
162: if (sibling.getFirstChild() != null) {
163: if (!sibling.getFirstChild().equalsListPartial(
164: sub.getFirstChild()))
165: return false;
166: }
167: }
168: if (sibling == null && sub != null) {
169: // nothing left to match in this tree, but subtree has more
170: return false;
171: }
172: // either both are null or sibling has more, but subtree doesn't
173: return true;
174: }
175:
176: /** Is tree rooted at 'this' equal to 't'? The siblings
177: * of 'this' are ignored.
178: */
179: public boolean equalsTree(AST t) {
180: // check roots first.
181: if (!this .equals(t))
182: return false;
183: // if roots match, do full list match test on children.
184: if (this .getFirstChild() != null) {
185: if (!this .getFirstChild().equalsList(t.getFirstChild()))
186: return false;
187: }
188: // sibling has no kids, make sure t doesn't either
189: else if (t.getFirstChild() != null) {
190: return false;
191: }
192: return true;
193: }
194:
195: /** Is 't' a subtree of the tree rooted at 'this'? The siblings
196: * of 'this' are ignored.
197: */
198: public boolean equalsTreePartial(AST sub) {
199: // the empty tree is always a subset of any tree.
200: if (sub == null) {
201: return true;
202: }
203:
204: // check roots first.
205: if (!this .equals(sub))
206: return false;
207: // if roots match, do full list partial match test on children.
208: if (this .getFirstChild() != null) {
209: if (!this .getFirstChild().equalsListPartial(
210: sub.getFirstChild()))
211: return false;
212: }
213: return true;
214: }
215:
216: /** Walk the tree looking for all exact subtree matches. Return
217: * an ASTEnumerator that lets the caller walk the list
218: * of subtree roots found herein.
219: */
220: public ASTEnumeration findAll(AST target) {
221: Vector roots = new Vector(10);
222: AST sibling;
223:
224: // the empty tree cannot result in an enumeration
225: if (target == null) {
226: return null;
227: }
228:
229: doWorkForFindAll(roots, target, false); // find all matches recursively
230:
231: return new ASTEnumerator(roots);
232: }
233:
234: /** Walk the tree looking for all subtrees. Return
235: * an ASTEnumerator that lets the caller walk the list
236: * of subtree roots found herein.
237: */
238: public ASTEnumeration findAllPartial(AST sub) {
239: Vector roots = new Vector(10);
240: AST sibling;
241:
242: // the empty tree cannot result in an enumeration
243: if (sub == null) {
244: return null;
245: }
246:
247: doWorkForFindAll(roots, sub, true); // find all matches recursively
248:
249: return new ASTEnumerator(roots);
250: }
251:
252: /** Get the first child of this node; null if not children */
253: public AST getFirstChild() {
254: return down;
255: }
256:
257: /** Get the next sibling in line after this one */
258: public AST getNextSibling() {
259: return right;
260: }
261:
262: /** Get the token text for this node */
263: public String getText() {
264: return "";
265: }
266:
267: /** Get the token type for this node */
268: public int getType() {
269: return 0;
270: }
271:
272: public int getLine() {
273: return 0;
274: }
275:
276: public int getColumn() {
277: return 0;
278: }
279:
280: public abstract void initialize(int t, String txt);
281:
282: public abstract void initialize(AST t);
283:
284: public abstract void initialize(Token t);
285:
286: /** Remove all children */
287: public void removeChildren() {
288: down = null;
289: }
290:
291: public void setFirstChild(AST c) {
292: down = (BaseAST) c;
293: }
294:
295: public void setNextSibling(AST n) {
296: right = (BaseAST) n;
297: }
298:
299: /** Set the token text for this node */
300: public void setText(String text) {
301: }
302:
303: /** Set the token type for this node */
304: public void setType(int ttype) {
305: }
306:
307: public static void setVerboseStringConversion(boolean verbose,
308: String[] names) {
309: verboseStringConversion = verbose;
310: tokenNames = names;
311: }
312:
313: /** Return an array of strings that maps token ID to it's text. @since 2.7.3 */
314: public static String[] getTokenNames() {
315: return tokenNames;
316: }
317:
318: public String toString() {
319: StringBuffer b = new StringBuffer();
320: // if verbose and type name not same as text (keyword probably)
321: if (verboseStringConversion
322: && !getText().equalsIgnoreCase(tokenNames[getType()])
323: && !getText().equalsIgnoreCase(
324: StringUtils.stripFrontBack(
325: tokenNames[getType()], "\"", "\""))) {
326: b.append('[');
327: b.append(getText());
328: b.append(",<");
329: b.append(tokenNames[getType()]);
330: b.append(">]");
331: return b.toString();
332: }
333: return getText();
334: }
335:
336: /** Print out a child-sibling tree in LISP notation */
337: public String toStringList() {
338: AST t = this ;
339: String ts = "";
340: if (t.getFirstChild() != null)
341: ts += " (";
342: ts += " " + this .toString();
343: if (t.getFirstChild() != null) {
344: ts += ((BaseAST) t.getFirstChild()).toStringList();
345: }
346: if (t.getFirstChild() != null)
347: ts += " )";
348: if (t.getNextSibling() != null) {
349: ts += ((BaseAST) t.getNextSibling()).toStringList();
350: }
351: return ts;
352: }
353:
354: public String toStringTree() {
355: AST t = this ;
356: String ts = "";
357: if (t.getFirstChild() != null)
358: ts += " (";
359: ts += " " + this .toString();
360: if (t.getFirstChild() != null) {
361: ts += ((BaseAST) t.getFirstChild()).toStringList();
362: }
363: if (t.getFirstChild() != null)
364: ts += " )";
365: return ts;
366: }
367:
368: public static String decode(String text) {
369: char c, c1, c2, c3, c4, c5;
370: StringBuffer n = new StringBuffer();
371: for (int i = 0; i < text.length(); i++) {
372: c = text.charAt(i);
373: if (c == '&') {
374: c1 = text.charAt(i + 1);
375: c2 = text.charAt(i + 2);
376: c3 = text.charAt(i + 3);
377: c4 = text.charAt(i + 4);
378: c5 = text.charAt(i + 5);
379:
380: if (c1 == 'a' && c2 == 'm' && c3 == 'p' && c4 == ';') {
381: n.append("&");
382: i += 5;
383: } else if (c1 == 'l' && c2 == 't' && c3 == ';') {
384: n.append("<");
385: i += 4;
386: } else if (c1 == 'g' && c2 == 't' && c3 == ';') {
387: n.append(">");
388: i += 4;
389: } else if (c1 == 'q' && c2 == 'u' && c3 == 'o'
390: && c4 == 't' && c5 == ';') {
391: n.append("\"");
392: i += 6;
393: } else if (c1 == 'a' && c2 == 'p' && c3 == 'o'
394: && c4 == 's' && c5 == ';') {
395: n.append("'");
396: i += 6;
397: } else
398: n.append("&");
399: } else
400: n.append(c);
401: }
402: return new String(n);
403: }
404:
405: public static String encode(String text) {
406: char c;
407: StringBuffer n = new StringBuffer();
408: for (int i = 0; i < text.length(); i++) {
409: c = text.charAt(i);
410: switch (c) {
411: case '&': {
412: n.append("&");
413: break;
414: }
415: case '<': {
416: n.append("<");
417: break;
418: }
419: case '>': {
420: n.append(">");
421: break;
422: }
423: case '"': {
424: n.append(""");
425: break;
426: }
427: case '\'': {
428: n.append("'");
429: break;
430: }
431: default: {
432: n.append(c);
433: break;
434: }
435: }
436: }
437: return new String(n);
438: }
439:
440: public void xmlSerializeNode(Writer out) throws IOException {
441: StringBuffer buf = new StringBuffer(100);
442: buf.append("<");
443: buf.append(getClass().getName() + " ");
444: buf.append("text=\"" + encode(getText()) + "\" type=\""
445: + getType() + "\"/>");
446: out.write(buf.toString());
447: }
448:
449: public void xmlSerializeRootOpen(Writer out) throws IOException {
450: StringBuffer buf = new StringBuffer(100);
451: buf.append("<");
452: buf.append(getClass().getName() + " ");
453: buf.append("text=\"" + encode(getText()) + "\" type=\""
454: + getType() + "\">\n");
455: out.write(buf.toString());
456: }
457:
458: public void xmlSerializeRootClose(Writer out) throws IOException {
459: out.write("</" + getClass().getName() + ">\n");
460: }
461:
462: public void xmlSerialize(Writer out) throws IOException {
463: // print out this node and all siblings
464: for (AST node = this ; node != null; node = node
465: .getNextSibling()) {
466: if (node.getFirstChild() == null) {
467: // print guts (class name, attributes)
468: ((BaseAST) node).xmlSerializeNode(out);
469: } else {
470: ((BaseAST) node).xmlSerializeRootOpen(out);
471:
472: // print children
473: ((BaseAST) node.getFirstChild()).xmlSerialize(out);
474:
475: // print end tag
476: ((BaseAST) node).xmlSerializeRootClose(out);
477: }
478: }
479: }
480:
481: }
|