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