SyntaxTemplate


1   package kawa.lang;
2   import gnu.lists.*;
3   import java.io.*;
4   import gnu.mapping.*;
5   import gnu.expr.*;
6   import java.util.*;
7   
8   /** The translated form of a <code>(syntax <var>template</var>)</code>. */
9   
10  public class SyntaxTemplate implements Externalizable
11  {
12    /** A <code>syntax</code> or <code>syntax-rules</code> template is
13     * translated into a "template program."
14     * The template program is a simple bytecode stored in a string.
15     * The encoding is designed so that instructions are normally
16     * in the range 1..127, which makes the <code>CONSTANT_Utf8</code> encoding
17     * used in <code>.class</code> files compact.
18     * The folowing <code>BUILD_XXX</code> are the "opcode" of the encoding,
19     * stored in the low-order 3 bits of a <code>char</code>.
20     */
21    String   template_program;
22  
23    /** Template instructions that don't have an operand value. */
24    static final int BUILD_MISC = 0;
25  
26    /** Make following operand into a 1-element list. */
27    static final int BUILD_LIST1 = (1<<3)+BUILD_MISC;
28  
29    static final int BUILD_NIL = (2<<3)+BUILD_MISC;
30  
31    /** Wrap following sub-expression in a SyntaxForm. */
32    static final int BUILD_SYNTAX = (3<<3)+BUILD_MISC;
33  
34    /** Build a vector (an <code>FVector</code>) from following sub-expression.
35     * The latter must evaluate to a list. */
36    static final int BUILD_VECTOR = (5<<3)+BUILD_MISC;
37  
38    /** Instruction to creat a <code>Pair</code> from sub-expressions.
39     * Instruction <code>BUILD_CONS+4*delta</code> is followed by a
40     * sub-expression for the <code>car</code>
41     * (whose length is <code>delta</code> chars),
42     * followed by the expression for the <code>cdr</code>. */
43    static final int BUILD_CONS = 1;
44  
45    /** Instruction BUILD_VAR+8*i pushes vars[i].
46     * This array contains the values of pattern variables. */
47    final static int BUILD_VAR = 2; // Must be an even number.
48  
49    /** Instruction BUILD_VAR_CAR+8*i pushes car(vars[i]).
50     * It assumes that vars[i] is actually a pair whose car was the
51     * matched pattern variable.  (This is done so we can preserve
52     * <code>PairWithPosition</code> source positions). */
53    final static int BUILD_VAR_CAR = BUILD_VAR+1;
54  
55    /** Instruction BUILD_LITERAL+8*i pushes literal_values[i]. */
56    final static int BUILD_LITERAL = 4;
57  
58    /** Instruction <code>BUILD_DOTS+8*i</code> repeats a sub-expression.
59     * The value <code>i</code> is a variable index of a pattern variable
60     * of at least the needed depth.  The result is spliced in. */
61    final static int BUILD_DOTS = 5;
62  
63    /** Unfinished support for "operand" values that need more tahn 13 bits. */
64    final static int BUILD_WIDE = 7;
65  
66    /** Map variable to ellipsis nesting depth.
67     * The nesting depth of the <code>i</code>'th pattern variable
68     * is <code>(int) patternNesting.charAt(i)/2</code>.
69     * The low-order bit indicates that if matched value is the <code>car</code>
70     * of the value saved in the <code>vars</code> array.
71     * (We use a <code>String</code> because it is compact both at runtime
72     * and in <code>.class</code> files. */
73    String   patternNesting;
74  
75    int max_nesting;
76  
77    Object  [] literal_values;
78  
79    static final String   dots3 = "...";
80  
81    /* DEBUGGING:
82    void print_template_program (java.util.Vector patternNames,
83                     java.io.PrintWriter ps)
84    {
85      print_template_program(patternNames, ps,
86                 0, template_program.length());
87      ps.flush();
88    }
89  
90    void print_template_program (java.util.Vector patternNames,
91                     java.io.PrintWriter ps,
92                     int start, int limit)
93    {
94      for (int i = start;  i < limit; i++)
95        {
96      char ch = template_program.charAt(i);
97      ps.print("  " + i + ": " + (int)ch);
98      if (ch == BUILD_LIST1)
99        ps.println (" - LIST1");
100     else if (ch == BUILD_NIL)
101       ps.println (" - NIL");
102     else if (ch == BUILD_SYNTAX)
103       ps.println (" - SYNTAX");
104     else if ((ch & 7) == BUILD_DOTS)
105       {
106         int var_num = ch >> 3;
107         ps.print(" - DOTS (var: ");
108         ps.print(var_num);
109         if (patternNames != null
110         && var_num >= 0 && var_num < patternNames.size())
111           {
112         ps.print(" = ");
113         ps.print(patternNames.elementAt(var_num));
114           }
115         ps.println(')');
116       }
117     else if (ch == BUILD_VECTOR)
118       ps.println (" - VECTOR");
119     else if ((ch & 7) == BUILD_CONS)
120       ps.println (" - CONS "+(ch >> 3));
121     else if ((ch & 7) == BUILD_LITERAL)
122       {
123         int lit_num = ch >> 3;
124         ps.print (" - literal[" + lit_num + "]: ");
125         if (literal_values == null || literal_values.length <= lit_num
126         || lit_num < 0)
127           ps.print("??");
128         else
129           kawa.standard.Scheme.writeFormat.writeObject(literal_values [lit_num], (Consumer) ps);
130         ps.println();
131       }
132     else if ((ch & 6) == BUILD_VAR) // Also catches BUILD_VAR_CAR.
133       {
134         int var_num = ch >> 3;
135         ps.print(((ch & 7) == BUILD_VAR ? " - VAR[" : " - VAR_CAR[")
136                  + var_num + "]");
137         if (patternNames != null
138         && var_num >= 0 && var_num < patternNames.size())
139           ps.print(": " + patternNames.elementAt(var_num));
140         ps.println();
141       }
142     else
143       ps.println (" - ???");      
144       }
145   }
146   END DEBUGGING */
147 
148 
149   protected SyntaxTemplate ()
150   {
151   }
152 
153   public SyntaxTemplate (String   patternNesting, String   template_program,
154              Object  [] literal_values, int max_nesting)
155   {
156     this.patternNesting = patternNesting;
157     this.template_program = template_program;
158     this.literal_values = literal_values;
159     this.max_nesting = max_nesting;
160   }
161 
162   public SyntaxTemplate (Object   template, SyntaxForm syntax, Translator tr)
163   {
164     this.patternNesting = tr == null || tr.patternScope == null ? ""
165       : tr.patternScope.patternNesting.toString();
166     StringBuffer   program = new StringBuffer   ();
167     java.util.Vector   literals_vector = new java.util.Vector   ();
168     /* #ifdef use:java.util.IdentityHashMap */ 
169     IdentityHashMap seen = new IdentityHashMap();
170     /* #else */
171     // Object seen = null;
172     /* #endif */
173     convert_template(template, syntax,
174              program, 0, literals_vector, seen, false, tr);
175     this.template_program = program.toString();
176     this.literal_values = new Object  [literals_vector.size ()];
177     literals_vector.copyInto (this.literal_values);
178 
179     /* DEBUGGING:
180     OutPort err = OutPort.errDefault();
181     err.print("{translated template");
182     Macro macro = tr.currentMacroDefinition;
183     if (macro != null)
184       {
185     err.print(" for ");
186     err.print(macro);
187       }
188     if (tr != null && tr.patternScope != null)
189       {
190         err.println(" - ");
191         print_template_program (tr.patternScope.pattern_names, err);
192       }
193     err.println ('}');
194     */
195   }
196 
197   /** Recursively translate a syntax-rule template to a template program.
198    * @param form the template from the syntax-rule
199    * @param syntax if non-null, the closest surrounding <code>SyntaxForm</code>
200    * @param template_program (output) the translated template
201    * @param nesting the depth of ... we are inside
202    * @param literals_vector (output) the literal data in the template
203    * @param tr  the current Translator
204    * @return the index of a pattern variable (in <code>pattern_names</code>)
205    *   that is nested at least as much as <code>nesting</code>;
206    *   if there is none such, -1 if there is any pattern variable or elipsis;
207    *   and -2 if the is no pattern variable or elipsis.
208    */
209   public int convert_template (Object   form,
210                    SyntaxForm syntax,
211                    StringBuffer   template_program,
212                    int nesting,
213                    java.util.Vector   literals_vector,
214                    Object   seen,
215                    boolean isVector,
216                    Translator tr)
217   {
218     while (form instanceof SyntaxForm)
219       {
220     syntax = (SyntaxForm) form;
221     form = syntax.form;
222       }
223     /* #ifdef use:java.util.IdentityHashMap */ 
224     if (form instanceof Pair || form instanceof FVector)
225       {
226         IdentityHashMap seen_map = (IdentityHashMap) seen;
227         if (seen_map.containsKey(form))
228           {
229             /* FIXME cycles are OK if data are literal. */
230             tr.syntaxError("self-referential (cyclic) syntax template");
231             return -2;
232           }
233         seen_map.put(form, form);
234       }
235     /* #endif */
236 
237   check_form:
238     if (form instanceof Pair)
239       {
240     Pair pair = (Pair) form;
241     int ret_cdr = -2;;
242     int save_pc = template_program.length();
243     Object   car = pair.car;
244 
245         // Look for (... ...) and translate that to ...
246         if (tr.matches(car, dots3))
247           {
248             Object   cdr = Translator.stripSyntax(pair.cdr);
249             if (cdr instanceof Pair)
250               {
251                 Pair cdr_pair = (Pair) cdr;
252                 if (cdr_pair.car == dots3 && cdr_pair.cdr == LList.Empty)
253                   {
254                     form = dots3;
255                     break check_form;
256                   }
257               }
258           }
259 
260     int save_literals = literals_vector.size();
261   
262     // This may get patched to a BUILD_CONS.
263     template_program.append((char) BUILD_LIST1);
264 
265     int num_dots3 = 0;
266     Object   rest = pair.cdr;
267     while (rest instanceof Pair)
268       {
269         Pair p = (Pair) rest;
270         if (! tr.matches(p.car, dots3))
271           break;
272         num_dots3++;
273         rest = p.cdr;
274         template_program.append((char) BUILD_DOTS); // to be patched.
275       }
276     int ret_car = convert_template(car, syntax, template_program,
277                        nesting + num_dots3,
278                        literals_vector, seen, false, tr);
279 
280     if (rest != LList.Empty)
281       {
282         int delta = template_program.length() - save_pc - 1;
283         template_program.setCharAt(save_pc,
284                        (char)((delta<<3)+BUILD_CONS));
285         ret_cdr = convert_template (rest, syntax,
286                     template_program, nesting,
287                     literals_vector, seen, isVector, tr);
288       }
289     if (num_dots3 > 0)
290       {
291         if (ret_car < 0)
292           tr.syntaxError ("... follows template with no suitably-nested pattern variable");
293         for (int i = num_dots3;  --i >= 0; )
294           {
295         char op = (char) ((ret_car << 3) + BUILD_DOTS);
296         template_program.setCharAt(save_pc+i + 1, op);
297         int n = nesting+num_dots3;
298         if (n >= max_nesting)
299           max_nesting = n;
300           }
301       }
302     if (ret_car >= 0)
303       return ret_car;
304     if (ret_cdr >= 0)
305       return ret_cdr;
306     if (ret_car == -1 || ret_cdr == -1)
307       return -1;
308     if (isVector)
309       return -2;
310     // There is no pattern variable in 'form', so treat it as literal.
311     // This is optimization to group non-substrituted "chunks"
312     // as a single literal and a single SyntaxForm value.
313     literals_vector.setSize(save_literals);
314     template_program.setLength(save_pc);
315       }
316     else if (form instanceof FVector)
317       {
318     template_program.append((char) BUILD_VECTOR);
319     return convert_template(LList.makeList((FVector) form), syntax,
320                 template_program, nesting,
321                 literals_vector, seen, true, tr);
322       }
323     else if (form == LList.Empty)
324       {
325     template_program.append((char) BUILD_NIL);
326     return -2;
327       }
328     else if (form instanceof String  
329          && tr != null && tr.patternScope != null)
330       {
331     int pattern_var_num = indexOf(tr.patternScope.pattern_names, form);
332     if (pattern_var_num >= 0)
333       {
334         int var_nesting = patternNesting.charAt(pattern_var_num);
335         int op = (var_nesting & 1) != 0 ? BUILD_VAR_CAR : BUILD_VAR;
336         var_nesting >>= 1;
337         // R4RS requires that the nesting be equal.
338         // We allow an extension here, since it allows potentially-useful
339         // rules like (x (y ...) ...)  => (((x y) ...) ...)
340         if (var_nesting > nesting)
341           tr.syntaxError ("inconsistent ... nesting of " + form);
342         template_program.append((char) (op + 8 * pattern_var_num));
343         return var_nesting == nesting ? pattern_var_num : -1;
344       }
345     // else treated quoted symbol as literal:
346       }
347     int literals_index = indexOf(literals_vector, form);
348     if (literals_index < 0)
349       {
350     literals_index = literals_vector.size ();
351     literals_vector.addElement(form);
352       }
353     if (form instanceof String   || form instanceof Symbol)
354       tr.noteAccess(form, tr.currentScope());
355     if (! (form instanceof SyntaxForm) && form != dots3)
356       template_program.append((char) (BUILD_SYNTAX));
357     template_program.append((char) (BUILD_LITERAL + 8 * literals_index));
358     return  form == dots3 ? -1 : -2;
359   }
360 
361   /** Similar to vec.indexOf(elem), but uses == (not equals) to compare. */
362   static int indexOf(java.util.Vector   vec, Object   elem)
363   {
364     int len = vec.size();
365     for (int i = 0;  i < len;  i++)
366       {
367     if (vec.elementAt(i) == elem)
368       return i;
369       }
370     return -1;
371   }
372 
373   /** The the current repeat count. */
374   private int get_count (Object   var, int nesting, int[] indexes)
375   {
376     for (int level = 0;  level < nesting;  level++)
377       var = ((Object  []) var) [indexes[level]];
378     Object  [] var_array = (Object  []) var;
379     return var_array.length;
380   }
381 
382   /** Expand this template
383    * The compiler translates <code>(syntax <var>template</var>)</code>
384    * to a call to this method.
385    */
386   public Object   execute (Object  [] vars, TemplateScope templateScope)
387   {
388     if (false)  // DEBUGGING
389       {
390     OutPort err = OutPort.errDefault();
391     err.print("{Expand template in ");
392     err.print(((Translator) Compilation.getCurrent()).getCurrentSyntax());
393         err.print(" tscope: ");
394         err.print(templateScope);
395         if (false && vars != null)
396           {
397             err.print(" vars: ");
398             for (int i = 0;  i < vars.length;  i++)
399               {
400                 err.println();
401                 err.print("  " + i +" : ");
402                 kawa.standard.Scheme.writeFormat.writeObject(vars[i], err);
403               }
404           }
405     err.println('}');
406       }
407 
408     Object   result = execute(0, vars, 0, new int[max_nesting],
409                             (Translator) Compilation.getCurrent(),
410                             templateScope);
411 
412     if (false) // DEBUGGING:
413       {
414     OutPort err = OutPort.errDefault();
415     err.startLogicalBlock("", false, "}");
416     err.print("{Expansion of syntax template ");
417     err.print(((Translator) Compilation.getCurrent()).getCurrentSyntax());
418     err.print(": ");
419     err.writeBreakLinear();
420     kawa.standard.Scheme.writeFormat.writeObject(result, err);
421     err.endLogicalBlock("}");
422     err.println();
423     err.flush();
424       }
425     return result;
426   }
427 
428   public Object   execute (Object  [] vars, Translator tr,
429                          TemplateScope templateScope)
430   {
431     return execute(0, vars, 0, new int[max_nesting], tr, templateScope);
432   }
433 
434   Object   get_var (int var_num, Object  [] vars, int[] indexes)
435   {
436     Object   var = vars [var_num];
437     if (var_num < patternNesting.length())
438       {
439     int var_nesting = (int) patternNesting.charAt(var_num) >> 1;
440     for (int level = 0;  level < var_nesting;  level++)
441       var = ((Object  []) var) [indexes[level]];
442       }
443     return var;    
444   }
445 
446   /** Similar to execute, but return is wrapped in a list.
447    * Normally the result is a single Pair, BUILD_DOTS can return zero
448    * or many Pairs. */
449   LList executeToList (int pc, Object  [] vars, int nesting, int[] indexes,
450             Translator tr, TemplateScope templateScope)
451   {
452     int pc0 = pc;
453     int ch = template_program.charAt(pc);
454     while ((ch & 7) == BUILD_WIDE)
455       ch = ((ch - BUILD_WIDE) << 13) |  template_program.charAt(++pc);
456     if ((ch & 7) == BUILD_VAR_CAR)
457       {
458     Pair p = (Pair) get_var(ch >> 3, vars, indexes);
459     return Translator.makePair(p, p.car, LList.Empty);
460       }
461     else if ((ch & 7) == BUILD_DOTS)
462       {
463     int var_num = (int) (ch >> 3);
464     Object   var = vars[var_num];
465     int count = get_count(var, nesting, indexes);
466     LList result = LList.Empty;
467     Pair last = null; // Final Pair of result list, or null.
468     pc++;
469     for (int j = 0;  j < count; j++)
470       {
471         indexes[nesting] = j;
472         LList list
473           = executeToList(pc, vars, nesting + 1, indexes, tr, templateScope);
474         if (last == null)
475           result = list;
476         else
477           last.cdr = list;
478         // Normally list is a single Pair, but if it is multiple Pairs,
479         // find the last Pair so we can properly splice everything.
480         while (list instanceof Pair)
481           {
482         last = (Pair) list;
483         list = (LList) last.cdr;
484           }
485       }
486     return result;
487       }
488     Object   v = execute(pc0, vars, nesting, indexes, tr, templateScope);
489     return new Pair(v, LList.Empty);
490   }
491 
492   /**
493    * @param nesting  number of levels of ... we are nested inside
494    * @param indexes element i (where i in [0 .. nesting-1] specifies
495    * the iteration index for the i'level of nesting
496    */
497   Object   execute (int pc, Object  [] vars, int nesting, int[] indexes,
498           Translator tr, TemplateScope templateScope)
499   {
500     int ch = template_program.charAt(pc);
501     /* DEBUGGING:
502     System.err.print ("{execute template pc:"+pc
503               + " ch:"+(int)ch+" nesting:[");
504     for (int level=0;  level < nesting; level++)
505       System.err.print ((level > 0 ? " " : "") + indexes[level]);
506     System.err.println("]}");
507     */
508     while ((ch & 7) == BUILD_WIDE)
509       ch = ((ch - BUILD_WIDE) << 13) |  template_program.charAt(++pc);
510     if (ch == BUILD_LIST1)
511       {
512     return executeToList(pc+1, vars, nesting, indexes, tr, templateScope);
513       }
514     else if (ch == BUILD_NIL)
515       return LList.Empty;
516     else if (ch == BUILD_SYNTAX)
517       {
518     Object   v = execute(pc+1, vars, nesting, indexes, tr, templateScope);
519     return v == LList.Empty ? v : SyntaxForm.make(v, templateScope);
520       }
521     else if ((ch & 7) == BUILD_CONS)
522       {
523     Pair p = null;
524     Object   result = null;
525     for (;;)
526       {
527         pc++;
528         Object   q
529           = executeToList(pc, vars, nesting, indexes, tr, templateScope);
530         if (p == null)
531           result = q;
532         else
533           p.cdr = q;
534         while (q instanceof Pair)
535           {
536         p = (Pair) q;
537         q = p.cdr;
538           }
539         pc += ch >> 3;
540         ch = template_program.charAt(pc);
541         if ((ch & 7) != BUILD_CONS)
542           break;
543       }
544     Object   cdr = execute(pc, vars, nesting, indexes, tr, templateScope);
545     if (p == null)
546       result = cdr;
547     else
548       p.cdr = cdr;
549     return result;
550       }
551     else if (ch == BUILD_VECTOR)
552       {
553     Object   el = execute(pc+1, vars, nesting, indexes, tr, templateScope);
554     return new FVector((LList) el);
555       }
556     else if ((ch & 7) == BUILD_LITERAL)
557       {
558     int lit_no = ch >> 3;
559     /* DEBUGGING:
560     System.err.println("-- insert literal#"+lit_no
561                +": "+literal_values[lit_no]);
562     */
563     return literal_values[lit_no];
564       }
565     else if ((ch & 6) == BUILD_VAR) // Also handles BUILD_VAR_CAR.
566       {
567     Object   var = get_var(ch >> 3, vars, indexes);
568     if ((ch & 7) == BUILD_VAR_CAR)
569       var = ((Pair) var).car;
570     return var;
571       }
572     else
573       throw new Error  ("unknown template code: "+((int) ch)+" at "+pc);
574   }
575 
576   /**
577    * @serialData 
578    */
579   public void writeExternal(ObjectOutput out) throws IOException
580   {
581     out.writeObject(patternNesting);
582     out.writeObject(template_program);
583     out.writeObject(literal_values);
584     out.writeInt(max_nesting);
585   }
586 
587   public void readExternal(ObjectInput in)
588     throws IOException, ClassNotFoundException  
589   {
590     patternNesting = (String  ) in.readObject();
591     template_program = (String  ) in.readObject();
592     literal_values = (Object  []) in.readObject();
593     max_nesting = in.readInt();
594   }
595 }
596
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags