SyntaxPattern


1   package kawa.lang;
2   import gnu.mapping.*;
3   import gnu.expr.*;
4   import java.io.*;
5   import gnu.lists.*;
6   import java.util.Vector  ;
7   import gnu.text.*;
8   
9   /** This encodes a pattern from a Scheem syntax-case or syntax-rules. */
10  
11  public class SyntaxPattern extends Pattern implements Externalizable
12  {
13    /** An encoding of the pattern in a compact form.
14     * This is a sequence of "matching instructions".  These have a 3-bit
15     * "opcode", which is one of the <code>MATCH_XXX</code> cosntants.
16     * The leaves 13 bits available as an operand; if that isn't enough the
17     * <code>MATCH_WIDE</code> "instruction" can be used to modify the
18     * following instruction. */
19    String   program;
20  
21    /** This 3-bit "opcode" is used for shorter operand-less instructions. */
22    static final int MATCH_MISC = 0;
23  
24    /** Matches <code>List.Empty</code>. */
25    static final int MATCH_NIL = (1<<3)+MATCH_MISC;
26  
27    /** Matches a vector (FVector).
28     * Matches a vecetor v if the following list pattern (at pc+1)
29     * matches (vector->list v). */
30    static final int MATCH_VECTOR = (2<<3)+MATCH_MISC;
31  
32    /** Match anything and ignoe it. */
33    static final int MATCH_IGNORE = (3<<3)+MATCH_MISC;
34  
35    /** The instruction <code>8*i+MATCH_WIDE</code> is a prefix.
36     * It causes <code>i&lt;&lt;13</code> to be added to the parameter
37     * (<code>i</code>) of the following instruction. */
38    static final int MATCH_WIDE = 1;
39  
40    /** The instruction <code>8*i+MATCH_EQUALS</code> matches the literal values literals[i]. */
41    static final int MATCH_EQUALS = 2;
42  
43    /** The instruction <code>8*i+MATCH_ANY</code> matches any form,
44     * It sets <code>vars[i]</code> to the matched form. */
45    static final int MATCH_ANY = 3;
46  
47    /** The instruction <code>8*i+MATCH_PAIR</code> matches a Pair.
48     * Its <code>car</code> must match the pattern at <code>pc+1</code>, while
49     * its <code>cdr</code> must match the mattern at <code>pc+1+i</code>. */
50    static final int MATCH_PAIR = 4;
51  
52    /** The instruction <code>8*i+MATCH_LREPEAT</code> matches a repeated
53     * pattern.  The repeated sub-pattern starts at <code>pc+1</code>,
54     * and is <code>i</code> chars long.  Following that (at <code>pc+1+i</code>)
55     * is the index of the first pattern variable in the sub-pattern,
56     * followed by the count of pattern variables in the sub-pattern.
57     * (Both are shifted left by 3 in case we need <code>MATCH_WIDE</code>).
58     * This is followed either by a <code>MATCH_NIL</code> (in which case
59     * all remaining elements must match the repeated sub-pattern),
60     * or by a <code>MATCH_LENGTH</code> (which must match the tail). */
61    static final int MATCH_LREPEAT = 5;
62  
63    /** The instruction <code>8*i+MATCH_LENGTH</code> matches a pure list
64     * of length <code>2*i</code> or an impure list of <code>2*i+1</code> pairs.
65     * It is followed by a pattern which must also match. */
66    static final int MATCH_LENGTH = 6;
67  
68    /** The instruction <code>8*i+MATCH_CAR</code> matches the car of a Pair,
69     * It sets <code>vars[i]</code> to the Pair itself. */
70    static final int MATCH_ANY_CAR = 7;
71  
72    Object  [] literals;
73    int varCount;
74  
75    public int varCount() { return varCount; }
76  
77    public boolean match (Object   obj, Object  [] vars, int start_vars)
78    {
79      boolean r = match(obj, vars, start_vars, 0, null);
80      if (false)  // DEBUGGING
81        {
82      OutPort err = OutPort.errDefault();
83      err.print("{match ");
84      kawa.standard.Scheme.writeFormat.writeObject(obj, err);
85      err.print(" in ");
86      err.print(((Translator) Compilation.getCurrent()).getCurrentSyntax());
87      if (r)
88        {
89          err.print(" -> vars: ");
90          for (int i = start_vars;  i < vars.length;  i++)
91            {
92          err.println();
93          err.print("  " + i +" : ");
94          kawa.standard.Scheme.writeFormat.writeObject(vars[i], err);
95            }
96          err.println('}');
97        }
98      else
99        err.println(" -> failed}");
100       }
101     return r;
102   }
103 
104   public SyntaxPattern (String   program, Object  [] literals, int varCount)
105   {
106     this.program = program;
107     this.literals = literals;
108     this.varCount = varCount;
109   }
110 
111   public SyntaxPattern (Object   pattern,
112             Object  [] literal_identifiers, Translator tr)
113   {
114     this(new StringBuffer  (), pattern,
115      null, literal_identifiers, tr);
116   }
117 
118   SyntaxPattern (StringBuffer   programbuf, Object   pattern,
119          SyntaxForm syntax, Object  [] literal_identifiers,
120          Translator tr)
121   {
122     Vector   literalsbuf = new Vector  ();
123     translate(pattern, programbuf,
124           literal_identifiers, 0, literalsbuf, null, '\0', tr);
125     program = programbuf.toString();
126     literals = new Object  [literalsbuf.size()];
127     literalsbuf.copyInto(literals);
128     varCount = tr.patternScope.pattern_names.size();
129     /* DEBUGGING:
130     System.err.print("{translated pattern");
131     Macro macro = tr.currentMacroDefinition;
132     if (macro != null)
133       {
134     System.err.print(" for ");
135     System.err.print(macro);
136       }
137     String file = tr.getFileName();
138     if (file != null)
139       {
140     System.err.print(" file=");
141     System.err.print(file);
142       }
143     int line = tr.getLineNumber();
144     if (line > 0)
145       {
146     System.err.print(" line=");
147     System.err.print(line);
148       }
149     System.err.print(" vars=");
150     System.err.print(varCount);
151     System.err.println(':');
152     disassemble();
153     */
154   }
155 
156   public void disassemble ()
157   {
158     disassemble(OutPort.errDefault(), (Translator) Compilation.getCurrent(),
159         0, program.length());
160   }
161 
162   public void disassemble (java.io.PrintWriter   ps, Translator tr)
163   {
164     disassemble(ps, tr, 0, program.length());
165   }
166 
167   void disassemble (java.io.PrintWriter   ps, Translator tr, int start, int limit)
168   {
169     Vector   pattern_names = null;
170     if (tr != null && tr.patternScope != null)
171       pattern_names = tr.patternScope.pattern_names;
172     int value = 0;
173     for (int i = start;  i < limit;  )
174       {
175     char ch = program.charAt(i);
176     ps.print(" " + i + ": " + (int)ch);
177     i++;
178     int opcode = ch & 7;
179     value = (value << 13) | (ch >> 3);
180     switch (opcode)
181       {
182       case MATCH_WIDE:
183         ps.println(" - WIDE "+value);
184         continue;
185       case MATCH_EQUALS:
186         ps.print(" - EQUALS["+value+"]");
187         if (literals != null && value >= 0 && value < literals.length)
188           ps.print(literals[value]);
189         ps.println();
190         break;
191       case MATCH_ANY:
192       case MATCH_ANY_CAR:
193         ps.print((opcode == MATCH_ANY ? " - ANY[" : " - ANY_CAR[")
194              +value+"]");
195         if (pattern_names != null
196         && value >= 0 && value < pattern_names.size())
197           ps.print(pattern_names.elementAt(value));
198         ps.println();
199         break;
200       case MATCH_PAIR:
201         ps.println(" - PAIR["+value+"]");
202         break;
203       case MATCH_LREPEAT:
204         ps.println(" - LREPEAT["+value+"]");
205         disassemble(ps, tr, i, i+value);
206         i += value;
207         ps.println(" " + i + ": - repeat first var:"+(program.charAt(i++)>>3));
208         ps.println(" " + i + ": - repeast nested vars:"+(program.charAt(i++)>>3));
209         break;
210       case MATCH_LENGTH:
211         ps.println(" - LENGTH "+(value>>1)+" pairs. "
212                + (((value&1)==0?"pure list":"impure list")));
213         break;
214       case MATCH_MISC:
215         ps.print("[misc ch:"+(int)ch+" n:"+(int)(MATCH_NIL)+"]");
216         if (ch == MATCH_NIL)
217           {
218         ps.println(" - NIL");
219         break;
220           }
221         if (ch == MATCH_VECTOR)
222           {
223         ps.println(" - VECTOR");
224         break;
225           }
226         if (ch == MATCH_IGNORE)
227           {
228         ps.println(" - IGNORE");
229         break;
230           }
231       default:
232         ps.println(" - "+opcode+'/'+value);
233         break;
234       }
235     value = 0;
236       }
237   }
238 
239 
240 
241   /**
242    * @param context 'V' : vector elements; 'P' : car of Pair; '\0' : other.
243    */
244   void translate (Object   pattern, StringBuffer   program,
245           Object  [] literal_identifiers, int nesting,
246           Vector   literals, SyntaxForm syntax,
247           char context,
248           Translator tr)
249   {
250     PatternScope patternScope = tr.patternScope;
251     Vector   patternNames = patternScope.pattern_names;
252     for (;;)
253       {
254     while (pattern instanceof SyntaxForm)
255       {
256         syntax = (SyntaxForm) pattern;
257         pattern = syntax.form;
258       }
259     if (pattern instanceof Pair)
260       {
261         Object   savePos = tr.pushPositionOf(pattern);
262         try
263           {
264         int start_pc = program.length();
265         program.append((char) MATCH_PAIR);
266         Pair pair = (Pair) pattern;
267         SyntaxForm car_syntax = syntax;
268         Object   next = pair.cdr;
269         while (next instanceof SyntaxForm)
270           {
271             syntax = (SyntaxForm) next;
272             next = syntax.form;
273           }
274         boolean repeat = false;
275         if (next instanceof Pair
276             && tr.matches(((Pair) next).car, SyntaxRule.dots3))
277           {
278             repeat = true;
279             next = ((Pair) next).cdr;
280             while (next instanceof SyntaxForm)
281               {
282             syntax = (SyntaxForm) next;
283             next = syntax.form;
284               }
285           }
286 
287         int subvar0 = patternNames.size();
288         if (context == 'P')
289           context = '\0';
290         translate(pair.car, program, literal_identifiers,
291               repeat ? nesting + 1 : nesting,
292               literals, car_syntax,
293               context == 'V' ? '\0' : 'P', tr);
294         int subvarN = patternNames.size() - subvar0;
295         int width = ((program.length() - start_pc - 1) << 3)
296           | (repeat ? MATCH_LREPEAT : MATCH_PAIR);
297         if (width > 0xFFFF)
298           start_pc += insertInt(start_pc, program,
299                     (width >> 13) + MATCH_WIDE);
300         program.setCharAt(start_pc, (char) width);
301 
302         int restLength = Translator.listLength(next);
303         if (restLength == Integer.MIN_VALUE)
304           {
305             tr.syntaxError("cyclic pattern list");
306             return;
307           }
308 
309         if (repeat)
310           {
311             addInt(program, subvar0 << 3);
312             addInt(program, subvarN << 3);
313             if (next == LList.Empty)
314               {
315             program.append((char) MATCH_NIL);
316             return;
317               }
318             else
319               {
320             // Map a signed int to an unsigned.
321             restLength = restLength >= 0 ? restLength << 1
322               : ((-restLength) << 1) - 1;
323             addInt(program, (restLength << 3) | MATCH_LENGTH);
324               }
325           }
326 
327         pattern = next;
328         continue;
329           }
330         finally
331           {
332         tr.popPositionOf(savePos);
333           }
334       }
335     else if (pattern instanceof String   || pattern instanceof Symbol)
336       {
337         for (int j = literal_identifiers.length;  --j >= 0; )
338           {
339         ScopeExp scope = syntax == null ? tr.currentScope()
340           : syntax.scope;
341         if (literalIdentifierEq(pattern, scope,
342                     literal_identifiers[j]))
343           {
344             int i = SyntaxTemplate.indexOf(literals, pattern);
345             if (i < 0)
346               {
347             i = literals.size();
348             literals.addElement(pattern);
349               }
350             addInt(program, (i << 3) | MATCH_EQUALS);
351             return;
352           }
353           }
354         if (patternNames.contains(pattern))
355           tr.syntaxError("duplicated pattern variable " + pattern);
356         int i = patternNames.size();
357         patternNames.addElement(pattern);
358         boolean matchCar = context == 'P';
359         int n = (nesting << 1) + (matchCar ? 1 : 0);
360         patternScope.patternNesting.append((char) n);
361             Declaration decl = patternScope.addDeclaration(pattern);
362             decl.setLocation(tr);
363         tr.push(decl);
364         addInt(program, (i << 3) | (matchCar ? MATCH_ANY_CAR : MATCH_ANY));
365         return;
366       }
367     else if (pattern == LList.Empty)
368       {
369         program.append((char) MATCH_NIL);
370         return;
371       }
372     else if (pattern instanceof FVector)
373       {
374         program.append((char) MATCH_VECTOR);
375         pattern = LList.makeList((FVector) pattern);
376         context = 'V';
377         continue;
378       }
379     else
380       {
381         int i = SyntaxTemplate.indexOf(literals, pattern);
382         if (i < 0)
383           {
384         i = literals.size();
385         literals.addElement(pattern);
386           }
387         addInt(program, (i << 3) | MATCH_EQUALS);
388         return;
389       }
390       }
391   }
392 
393   private static void addInt (StringBuffer   sbuf, int val)
394   {
395     if (val > 0xFFFF)
396       addInt(sbuf, (val << 13) + MATCH_WIDE);
397     sbuf.append((char) (val));
398   }
399 
400   private static int insertInt (int offset, StringBuffer   sbuf, int val)
401   {
402     if (val > 0xFFFF)
403       offset += insertInt(offset, sbuf, (val << 13) + MATCH_WIDE);
404     sbuf.insert(offset, (char) (val));
405     return offset+1;
406   }
407 
408   /** Match the <code>car</code> of a <code>Pair</code>.
409    * This special case (instead of of just matching the <code>car</code>
410    * directly), is so we can copy <code>PairWithPosition</code> line number
411    * info into the output of a template. */
412   boolean match_car (Pair p, Object  [] vars, int start_vars,
413              int pc, SyntaxForm syntax)
414   {
415     int pc_start = pc;
416     char ch;
417     int value = (ch = program.charAt(pc++)) >> 3;
418     while ((ch & 7) == MATCH_WIDE)
419       value = (value << 13) | ((ch = program.charAt(pc++)) >> 3);
420     if ((ch & 7) == MATCH_ANY_CAR)
421       {
422     if (syntax != null && ! (p.car instanceof SyntaxForm))
423       p = Translator.makePair(p, syntax.fromDatum(p.car), p.cdr);
424     vars[start_vars + value] = p;
425     return true;
426       }
427     return match (p.car, vars, start_vars, pc_start, syntax);
428   }
429 
430   public boolean match (Object   obj, Object  [] vars, int start_vars,
431             int pc, SyntaxForm syntax)
432   {
433     int value = 0;
434     Pair p;
435     for (;;)
436       {
437     while (obj instanceof SyntaxForm)
438       {
439         syntax = (SyntaxForm) obj;
440         obj = syntax.form;
441       }
442     char ch = program.charAt(pc++);
443     int opcode = ch & 7;
444     value = (value << 13) | (ch >> 3);
445     switch (opcode)
446       {
447       case MATCH_WIDE:
448         continue;
449       case MATCH_MISC:
450         if (ch == MATCH_NIL)
451           return obj == LList.Empty;
452         else if (ch == MATCH_VECTOR)
453           {
454         if (! (obj instanceof FVector))
455           return false;
456         return match(LList.makeList((FVector) obj),
457                  vars, start_vars, pc, syntax);
458           }
459         else if (ch == MATCH_IGNORE)
460           return true;
461         else
462           throw new Error  ("unknwon pattern opcode");
463       case MATCH_NIL:
464         return obj == LList.Empty;
465       case MATCH_LENGTH:
466         int npairs = value>>1;
467         Object   o = obj;
468         for (int i = 0;;i++)
469           {
470         while (o instanceof SyntaxForm)
471           o = ((SyntaxForm) o).form;
472         if (i == npairs)
473           {
474             if ((value&1) == 0 ? o != LList.Empty : o instanceof Pair)
475               return false;
476             break;
477           }
478         else if (o instanceof Pair)
479           o = ((Pair) o).cdr;
480         else 
481           return false;
482           }
483         value = 0;
484         continue;
485       case MATCH_PAIR:
486         if (! (obj instanceof Pair))
487           return false;
488         p = (Pair) obj;
489         if (! match_car(p, vars, start_vars, pc, syntax))
490           return false;
491         pc += value;
492         value = 0;
493         obj = p.cdr;
494         continue;   
495       case MATCH_LREPEAT:
496         int repeat_pc = pc;
497         pc += value;
498         int subvar0 = (ch = program.charAt(pc++)) >> 3;
499         while ((ch & 0x7) == MATCH_WIDE)
500           subvar0 = (subvar0 << 13) | ((ch = program.charAt(pc++)) >> 3);
501         subvar0 += start_vars;
502         int subvarN = program.charAt(pc++) >> 3;
503         while ((ch & 0x7) == MATCH_WIDE)
504           subvarN = (subvarN << 13) | ((ch = program.charAt(pc++)) >> 3);
505 
506         ch = program.charAt(pc++);
507         boolean listRequired = true;
508         int pairsRequired;
509         if (ch == MATCH_NIL)
510           {
511         pairsRequired = 0;
512           }
513         else
514           {
515         value = ch >> 3;
516         while ((ch & 0x7) == MATCH_WIDE)
517           value = (value << 13) | ((ch = program.charAt(pc++)) >> 3);
518         if ((value & 1) != 0)
519           listRequired = false;
520         pairsRequired = value >> 1;
521           }
522         int pairsValue = Translator.listLength(obj);
523         boolean listValue;
524 
525         if (pairsValue >= 0)
526           listValue = true;
527         else
528           {
529         listValue = false;
530         pairsValue = -1-pairsValue;
531           }
532         if (pairsValue < pairsRequired || (listRequired && ! listValue))
533           return false;
534         int repeat_count = pairsValue - pairsRequired;
535         Object  [][] arrays = new Object  [subvarN][];
536 
537         for (int j = 0;  j < subvarN;  j++)
538           arrays[j] = new Object  [repeat_count];
539         for (int i = 0;  i < repeat_count;  i++)
540           {
541         while (obj instanceof SyntaxForm)
542           {
543             syntax = (SyntaxForm) obj;
544             obj = syntax.form;
545           }
546         p = (Pair) obj;
547         if (! match_car (p, vars, start_vars, repeat_pc, syntax))
548           return false;
549         obj = p.cdr;
550         for (int j = 0;  j < subvarN;  j++)
551           arrays[j][i] = vars[subvar0+j];
552           }
553         for (int j = 0;  j < subvarN;  j++)
554           vars[subvar0+j] = arrays[j];
555         value = 0;
556         if (pairsRequired == 0 && listRequired)
557           return true;
558         continue;
559       case MATCH_EQUALS:
560         Object   lit = literals[value];
561         // We should be using Translator's matches routine, but the current
562         // Translator isn't available, so here is a special-purpose kludge.
563         if (lit instanceof String   && obj instanceof Symbol)
564           obj = ((Symbol) obj).getName();
565         return lit.equals(obj);
566       case MATCH_ANY:
567         if (syntax != null)
568           obj = syntax.fromDatum(obj);
569         vars[start_vars + value] = obj;
570         return true;
571       case MATCH_ANY_CAR: // Disallowed here.
572       default:
573         disassemble();
574         throw new Error  ("unrecognized pattern opcode @pc:"+pc);
575       }
576       }
577   }
578   
579   public void writeExternal(ObjectOutput out) throws IOException
580   {
581     out.writeObject(program);
582     out.writeObject(literals);
583     out.writeInt(varCount);
584   }
585 
586   public void readExternal(ObjectInput in)
587     throws IOException, ClassNotFoundException  
588   {
589     literals = (Object  []) in.readObject();
590     program = (String  )  in.readObject();
591     varCount = in.readInt();
592   }
593 
594   /** The compiler calls this method to implement syntax-case. */
595   public static Object  [] allocVars (int varCount, Object  [] outer)
596   {
597     Object  [] vars = new Object  [varCount];
598     if (outer != null)
599       System.arraycopy(outer, 0, vars, 0, outer.length);
600     return vars;
601   }
602 
603   public static boolean literalIdentifierEq (Object   id1, ScopeExp sc1,
604                          Object   literal2)
605   {
606     if (literal2 instanceof SyntaxForm)
607       {
608     SyntaxForm syntax = (SyntaxForm) literal2;
609     return literalIdentifierEq(id1, sc1, syntax.form, syntax.scope);
610       }
611     return literalIdentifierEq(id1, sc1, literal2, null);
612   }
613 
614   public static boolean literalIdentifierEq (Object   id1, ScopeExp sc1,
615                          Object   id2, ScopeExp sc2)
616   {
617     if (id1 != id2)
618       return false;
619     Declaration d1 = null, d2 = null;
620     while (sc1 != null && ! (sc1 instanceof ModuleExp))
621       {
622     d1 = sc1.lookup(id1);
623     if (d1 != null)
624       break;
625     sc1 = sc1.outer;
626       }
627     while (sc2 != null && ! (sc2 instanceof ModuleExp))
628       {
629     d2 = sc1.lookup(id1);
630     if (d2 != null)
631       break;
632     sc2 = sc2.outer;
633       }
634     return d1 == d2;
635   }
636 
637   /** Parse the literals list in a syntax-rules or syntax-case. */
638   public static Object  [] getLiteralsList (Object   list,
639                       SyntaxForm syntax, Translator tr)
640   {
641     Object   savePos = tr.pushPositionOf(list);
642     int count = Translator.listLength(list);
643     if (count < 0)
644       {
645     tr.error('e', "missing or malformed literals list");
646     count = 0;
647       }
648     Object  [] literals = new Object  [count + 1];
649     for (int i = 1;  i <= count;  i++)
650       {
651     while (list instanceof SyntaxForm)
652       {
653         syntax = (SyntaxForm) list;
654         list = syntax.form;
655       }
656     Pair pair = (Pair) list;
657     tr.pushPositionOf(pair);
658     Object   literal = pair.car;
659     Object   wrapped;
660     if (literal instanceof SyntaxForm)
661       {
662         wrapped = literal;
663         literal = (( SyntaxForm) literal).form;
664       }
665     else
666       wrapped = literal; // FIXME
667     if (! (literal instanceof String   
668                || literal instanceof gnu.mapping.Symbol))
669           tr.error('e', "non-symbol '"+literal+"' in literals list");
670     literals[i] = wrapped;
671     list = pair.cdr;
672       }
673     tr.popPositionOf(savePos);
674     return literals;
675   }
676 
677   public void print (Consumer out)
678   {
679     out.write("#<syntax-pattern>");
680   }
681 }
682
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags