BaseAST


1   package persistence.antlr;
2   
3   /* ANTLR Translator Generator
4    * Project led by Terence Parr at http://www.jGuru.com
5    * Software rights: http://www.antlr.org/license.html
6    *
7    */
8   
9   import persistence.antlr.collections.AST;
10  import persistence.antlr.collections.ASTEnumeration;
11  import persistence.antlr.collections.impl.ASTEnumerator;
12  import persistence.antlr.collections.impl.Vector;
13  
14  import java.io.Serializable  ;
15  import java.io.IOException  ;
16  import java.io.Writer  ;
17  
18  /**
19   * A Child-Sibling Tree.
20   *
21   * A tree with PLUS at the root and with two children 3 and 4 is
22   * structured as:
23   *
24   *      PLUS
25   *        |
26   *        3 -- 4
27   *
28   * and can be specified easily in LISP notation as
29   *
30   * (PLUS 3 4)
31   *
32   * where every '(' starts a new subtree.
33   *
34   * These trees are particular useful for translators because of
35   * the flexibility of the children lists.  They are also very easy
36   * to walk automatically, whereas trees with specific children
37   * reference fields can't easily be walked automatically.
38   *
39   * This class contains the basic support for an AST.
40   * Most people will create ASTs that are subclasses of
41   * BaseAST or of CommonAST.
42   */
43  public abstract class BaseAST implements AST, Serializable   {
44      protected BaseAST down;
45      protected BaseAST right;
46  
47      private static boolean verboseStringConversion = false;
48      private static String  [] tokenNames = null;
49  
50      /**Add a node to the end of the child list for this node */
51      public void addChild(AST node) {
52          if (node == null) return;
53          BaseAST t = this.down;
54          if (t != null) {
55              while (t.right != null) {
56                  t = t.right;
57              }
58              t.right = (BaseAST)node;
59          }
60          else {
61              this.down = (BaseAST)node;
62          }
63      }
64  
65      /** How many children does this node have? */
66      public int getNumberOfChildren() {
67          BaseAST t = this.down;
68          int n = 0;
69          if (t != null) {
70              n = 1;
71              while (t.right != null) {
72                  t = t.right;
73                  n++;
74              }
75              return n;
76          }
77          return n;
78      }
79  
80      private void doWorkForFindAll(Vector v, AST target, boolean partialMatch) {
81          AST sibling;
82  
83          // Start walking sibling lists, looking for matches.
84          siblingWalk:
85          for (sibling = this;
86               sibling != null;
87               sibling = sibling.getNextSibling()) {
88              if ((partialMatch && sibling.equalsTreePartial(target)) ||
89                  (!partialMatch && sibling.equalsTree(target))) {
90                  v.appendElement(sibling);
91              }
92              // regardless of match or not, check any children for matches
93              if (sibling.getFirstChild() != null) {
94                  ((BaseAST)sibling.getFirstChild()).doWorkForFindAll(v, target, partialMatch);
95              }
96          }
97      }
98  
99      /** Is node t equal to this in terms of token type and text? */
100     public boolean equals(AST t) {
101         if (t == null) return false;
102         return this.getText().equals(t.getText()) &&
103             this.getType() == t.getType();
104     }
105 
106     /** Is t an exact structural and equals() match of this tree.  The
107      *  'this' reference is considered the start of a sibling list.
108      */
109     public boolean equalsList(AST t) {
110         AST sibling;
111 
112         // the empty tree is not a match of any non-null tree.
113         if (t == null) {
114             return false;
115         }
116 
117         // Otherwise, start walking sibling lists.  First mismatch, return false.
118         for (sibling = this;
119              sibling != null && t != null;
120              sibling = sibling.getNextSibling(), t = t.getNextSibling())
121         {
122             // as a quick optimization, check roots first.
123             if (!sibling.equals(t)) {
124                 return false;
125             }
126             // if roots match, do full list match test on children.
127             if (sibling.getFirstChild() != null) {
128                 if (!sibling.getFirstChild().equalsList(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;
157              sibling != null && sub != null;
158              sibling = sibling.getNextSibling(), sub = sub.getNextSibling()) {
159             // as a quick optimization, check roots first.
160             if (!sibling.equals(sub)) return false;
161             // if roots match, do partial list match test on children.
162             if (sibling.getFirstChild() != null) {
163                 if (!sibling.getFirstChild().equalsListPartial(sub.getFirstChild())) return false;
164             }
165         }
166         if (sibling == null && sub != null) {
167             // nothing left to match in this tree, but subtree has more
168             return false;
169         }
170         // either both are null or sibling has more, but subtree doesn't
171         return true;
172     }
173 
174     /** Is tree rooted at 'this' equal to 't'?  The siblings
175      *  of 'this' are ignored.
176      */
177     public boolean equalsTree(AST t) {
178         // check roots first.
179         if (!this.equals(t)) return false;
180         // if roots match, do full list match test on children.
181         if (this.getFirstChild() != null) {
182             if (!this.getFirstChild().equalsList(t.getFirstChild())) return false;
183         }
184         // sibling has no kids, make sure t doesn't either
185         else if (t.getFirstChild() != null) {
186             return false;
187         }
188         return true;
189     }
190 
191     /** Is 't' a subtree of the tree rooted at 'this'?  The siblings
192      *  of 'this' are ignored.
193      */
194     public boolean equalsTreePartial(AST sub) {
195         // the empty tree is always a subset of any tree.
196         if (sub == null) {
197             return true;
198         }
199 
200         // check roots first.
201         if (!this.equals(sub)) return false;
202         // if roots match, do full list partial match test on children.
203         if (this.getFirstChild() != null) {
204             if (!this.getFirstChild().equalsListPartial(sub.getFirstChild())) return false;
205         }
206         return true;
207     }
208 
209     /** Walk the tree looking for all exact subtree matches.  Return
210      *  an ASTEnumerator that lets the caller walk the list
211      *  of subtree roots found herein.
212      */
213     public ASTEnumeration findAll(AST target) {
214         Vector roots = new Vector(10);
215         AST sibling;
216 
217         // the empty tree cannot result in an enumeration
218         if (target == null) {
219             return null;
220         }
221 
222         doWorkForFindAll(roots, target, false);  // find all matches recursively
223 
224         return new ASTEnumerator(roots);
225     }
226 
227     /** Walk the tree looking for all subtrees.  Return
228      *  an ASTEnumerator that lets the caller walk the list
229      *  of subtree roots found herein.
230      */
231     public ASTEnumeration findAllPartial(AST sub) {
232         Vector roots = new Vector(10);
233         AST sibling;
234 
235         // the empty tree cannot result in an enumeration
236         if (sub == null) {
237             return null;
238         }
239 
240         doWorkForFindAll(roots, sub, true);  // find all matches recursively
241 
242         return new ASTEnumerator(roots);
243     }
244 
245     /** Get the first child of this node; null if not children */
246     public AST getFirstChild() {
247         return down;
248     }
249 
250     /** Get the next sibling in line after this one */
251     public AST getNextSibling() {
252         return right;
253     }
254 
255     /** Get the token text for this node */
256     public String   getText() {
257         return "";
258     }
259 
260     /** Get the token type for this node */
261     public int getType() {
262         return 0;
263     }
264 
265     public int getLine() {
266         return 0;
267     }
268 
269     public int getColumn() {
270         return 0;
271     }
272 
273     public abstract void initialize(int t, String   txt);
274 
275     public abstract void initialize(AST t);
276 
277     public abstract void initialize(Token t);
278 
279     /** Remove all children */
280     public void removeChildren() {
281         down = null;
282     }
283 
284     public void setFirstChild(AST c) {
285         down = (BaseAST)c;
286     }
287 
288     public void setNextSibling(AST n) {
289         right = (BaseAST)n;
290     }
291 
292     /** Set the token text for this node */
293     public void setText(String   text) {
294     }
295 
296     /** Set the token type for this node */
297     public void setType(int ttype) {
298     }
299 
300     public static void setVerboseStringConversion(boolean verbose, String  [] names) {
301         verboseStringConversion = verbose;
302         tokenNames = names;
303     }
304 
305     /** Return an array of strings that maps token ID to it's text. @since 2.7.3 */
306     public static String  [] getTokenNames() {
307         return tokenNames;
308     }
309 
310     public String   toString() {
311         StringBuffer   b = new StringBuffer  ();
312         // if verbose and type name not same as text (keyword probably)
313         if (verboseStringConversion &&
314             !getText().equalsIgnoreCase(tokenNames[getType()]) &&
315             !getText().equalsIgnoreCase(StringUtils.stripFrontBack(tokenNames[getType()], "\"", "\""))) {
316             b.append('[');
317             b.append(getText());
318             b.append(",<");
319             b.append(tokenNames[getType()]);
320             b.append(">]");
321             return b.toString();
322         }
323         return getText();
324     }
325 
326     /** Print out a child-sibling tree in LISP notation */
327     public String   toStringList() {
328         AST t = this;
329         String   ts = "";
330         if (t.getFirstChild() != null) ts += " (";
331         ts += " " + this.toString();
332         if (t.getFirstChild() != null) {
333             ts += ((BaseAST)t.getFirstChild()).toStringList();
334         }
335         if (t.getFirstChild() != null) ts += " )";
336         if (t.getNextSibling() != null) {
337             ts += ((BaseAST)t.getNextSibling()).toStringList();
338         }
339         return ts;
340     }
341 
342     public String   toStringTree() {
343         AST t = this;
344         String   ts = "";
345         if (t.getFirstChild() != null) ts += " (";
346         ts += " " + this.toString();
347         if (t.getFirstChild() != null) {
348             ts += ((BaseAST)t.getFirstChild()).toStringList();
349         }
350         if (t.getFirstChild() != null) ts += " )";
351         return ts;
352     }
353 
354     public static String   decode(String   text) {
355         char c, c1, c2, c3, c4, c5;
356         StringBuffer   n = new StringBuffer  ();
357         for (int i = 0; i < text.length(); i++) {
358             c = text.charAt(i);
359             if (c == '&') {
360                 c1 = text.charAt(i + 1);
361                 c2 = text.charAt(i + 2);
362                 c3 = text.charAt(i + 3);
363                 c4 = text.charAt(i + 4);
364                 c5 = text.charAt(i + 5);
365 
366                 if (c1 == 'a' && c2 == 'm' && c3 == 'p' && c4 == ';') {
367                     n.append("&");
368                     i += 5;
369                 }
370                 else if (c1 == 'l' && c2 == 't' && c3 == ';') {
371                     n.append("<");
372                     i += 4;
373                 }
374                 else if (c1 == 'g' && c2 == 't' && c3 == ';') {
375                     n.append(">");
376                     i += 4;
377                 }
378                 else if (c1 == 'q' && c2 == 'u' && c3 == 'o' &&
379                     c4 == 't' && c5 == ';') {
380                     n.append("\"");
381                     i += 6;
382                 }
383                 else if (c1 == 'a' && c2 == 'p' && c3 == 'o' &&
384                     c4 == 's' && c5 == ';') {
385                     n.append("'");
386                     i += 6;
387                 }
388                 else
389                     n.append("&");
390             }
391             else
392                 n.append(c);
393         }
394         return new String  (n);
395     }
396 
397     public static String   encode(String   text) {
398         char c;
399         StringBuffer   n = new StringBuffer  ();
400         for (int i = 0; i < text.length(); i++) {
401             c = text.charAt(i);
402             switch (c) {
403                 case '&':
404                     {
405                         n.append("&amp;");
406                         break;
407                     }
408                 case '<':
409                     {
410                         n.append("&lt;");
411                         break;
412                     }
413                 case '>':
414                     {
415                         n.append("&gt;");
416                         break;
417                     }
418                 case '"':
419                     {
420                         n.append("&quot;");
421                         break;
422                     }
423                 case '\'':
424                     {
425                         n.append("&apos;");
426                         break;
427                     }
428                 default :
429                     {
430                         n.append(c);
431                         break;
432                     }
433             }
434         }
435         return new String  (n);
436     }
437 
438     public void xmlSerializeNode(Writer   out)
439         throws IOException   {
440         StringBuffer   buf = new StringBuffer  (100);
441         buf.append("<");
442         buf.append(getClass().getName() + " ");
443         buf.append("text=\"" + encode(getText()) + "\" type=\"" +
444                    getType() + "\"/>");
445         out.write(buf.toString());
446     }
447 
448     public void xmlSerializeRootOpen(Writer   out)
449         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)
459         throws IOException   {
460         out.write("</" + getClass().getName() + ">\n");
461     }
462 
463     public void xmlSerialize(Writer   out) throws IOException   {
464         // print out this node and all siblings
465         for (AST node = this;
466              node != null;
467              node = node.getNextSibling()) {
468             if (node.getFirstChild() == null) {
469                 // print guts (class name, attributes)
470                 ((BaseAST)node).xmlSerializeNode(out);
471             }
472             else {
473                 ((BaseAST)node).xmlSerializeRootOpen(out);
474 
475                 // print children
476                 ((BaseAST)node.getFirstChild()).xmlSerialize(out);
477 
478                 // print end tag
479                 ((BaseAST)node).xmlSerializeRootClose(out);
480             }
481         }
482     }
483 
484 }
485
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags