001: package kawa.lang;
002:
003: import gnu.mapping.*;
004: import gnu.expr.*;
005: import java.io.*;
006: import gnu.lists.*;
007: import java.util.Vector;
008: import gnu.text.*;
009:
010: /** This encodes a pattern from a Scheem syntax-case or syntax-rules. */
011:
012: public class SyntaxPattern extends Pattern implements Externalizable {
013: /** An encoding of the pattern in a compact form.
014: * This is a sequence of "matching instructions". These have a 3-bit
015: * "opcode", which is one of the <code>MATCH_XXX</code> cosntants.
016: * The leaves 13 bits available as an operand; if that isn't enough the
017: * <code>MATCH_WIDE</code> "instruction" can be used to modify the
018: * following instruction. */
019: String program;
020:
021: /** This 3-bit "opcode" is used for shorter operand-less instructions. */
022: static final int MATCH_MISC = 0;
023:
024: /** Matches <code>List.Empty</code>. */
025: static final int MATCH_NIL = (1 << 3) + MATCH_MISC;
026:
027: /** Matches a vector (FVector).
028: * Matches a vecetor v if the following list pattern (at pc+1)
029: * matches (vector->list v). */
030: static final int MATCH_VECTOR = (2 << 3) + MATCH_MISC;
031:
032: /** Match anything and ignoe it. */
033: static final int MATCH_IGNORE = (3 << 3) + MATCH_MISC;
034:
035: /** The instruction <code>8*i+MATCH_WIDE</code> is a prefix.
036: * It causes <code>i<<13</code> to be added to the parameter
037: * (<code>i</code>) of the following instruction. */
038: static final int MATCH_WIDE = 1;
039:
040: /** The instruction <code>8*i+MATCH_EQUALS</code> matches the literal values literals[i]. */
041: static final int MATCH_EQUALS = 2;
042:
043: /** The instruction <code>8*i+MATCH_ANY</code> matches any form,
044: * It sets <code>vars[i]</code> to the matched form. */
045: static final int MATCH_ANY = 3;
046:
047: /** The instruction <code>8*i+MATCH_PAIR</code> matches a Pair.
048: * Its <code>car</code> must match the pattern at <code>pc+1</code>, while
049: * its <code>cdr</code> must match the mattern at <code>pc+1+i</code>. */
050: static final int MATCH_PAIR = 4;
051:
052: /** The instruction <code>8*i+MATCH_LREPEAT</code> matches a repeated
053: * pattern. The repeated sub-pattern starts at <code>pc+1</code>,
054: * and is <code>i</code> chars long. Following that (at <code>pc+1+i</code>)
055: * is the index of the first pattern variable in the sub-pattern,
056: * followed by the count of pattern variables in the sub-pattern.
057: * (Both are shifted left by 3 in case we need <code>MATCH_WIDE</code>).
058: * This is followed either by a <code>MATCH_NIL</code> (in which case
059: * all remaining elements must match the repeated sub-pattern),
060: * or by a <code>MATCH_LENGTH</code> (which must match the tail). */
061: static final int MATCH_LREPEAT = 5;
062:
063: /** The instruction <code>8*i+MATCH_LENGTH</code> matches a pure list
064: * of length <code>2*i</code> or an impure list of <code>2*i+1</code> pairs.
065: * It is followed by a pattern which must also match. */
066: static final int MATCH_LENGTH = 6;
067:
068: /** The instruction <code>8*i+MATCH_CAR</code> matches the car of a Pair,
069: * It sets <code>vars[i]</code> to the Pair itself. */
070: static final int MATCH_ANY_CAR = 7;
071:
072: Object[] literals;
073: int varCount;
074:
075: public int varCount() {
076: return varCount;
077: }
078:
079: public boolean match(Object obj, Object[] vars, int start_vars) {
080: boolean r = match(obj, vars, start_vars, 0, null);
081: if (false) // DEBUGGING
082: {
083: OutPort err = OutPort.errDefault();
084: err.print("{match ");
085: kawa.standard.Scheme.writeFormat.writeObject(obj, err);
086: err.print(" in ");
087: err.print(((Translator) Compilation.getCurrent())
088: .getCurrentSyntax());
089: if (r) {
090: err.print(" -> vars: ");
091: for (int i = start_vars; i < vars.length; i++) {
092: err.println();
093: err.print(" " + i + " : ");
094: kawa.standard.Scheme.writeFormat.writeObject(
095: vars[i], err);
096: }
097: err.println('}');
098: } else
099: err.println(" -> failed}");
100: }
101: return r;
102: }
103:
104: public SyntaxPattern(String program, Object[] literals, int varCount) {
105: this .program = program;
106: this .literals = literals;
107: this .varCount = varCount;
108: }
109:
110: public SyntaxPattern(Object pattern, Object[] literal_identifiers,
111: Translator tr) {
112: this (new StringBuffer(), pattern, null, literal_identifiers, tr);
113: }
114:
115: SyntaxPattern(StringBuffer programbuf, Object pattern,
116: SyntaxForm syntax, Object[] literal_identifiers,
117: Translator tr) {
118: Vector literalsbuf = new Vector();
119: translate(pattern, programbuf, literal_identifiers, 0,
120: literalsbuf, null, '\0', tr);
121: program = programbuf.toString();
122: literals = new Object[literalsbuf.size()];
123: literalsbuf.copyInto(literals);
124: varCount = tr.patternScope.pattern_names.size();
125: /* DEBUGGING:
126: System.err.print("{translated pattern");
127: Macro macro = tr.currentMacroDefinition;
128: if (macro != null)
129: {
130: System.err.print(" for ");
131: System.err.print(macro);
132: }
133: String file = tr.getFileName();
134: if (file != null)
135: {
136: System.err.print(" file=");
137: System.err.print(file);
138: }
139: int line = tr.getLineNumber();
140: if (line > 0)
141: {
142: System.err.print(" line=");
143: System.err.print(line);
144: }
145: System.err.print(" vars=");
146: System.err.print(varCount);
147: System.err.println(':');
148: disassemble();
149: */
150: }
151:
152: public void disassemble() {
153: disassemble(OutPort.errDefault(), (Translator) Compilation
154: .getCurrent(), 0, program.length());
155: }
156:
157: public void disassemble(java.io.PrintWriter ps, Translator tr) {
158: disassemble(ps, tr, 0, program.length());
159: }
160:
161: void disassemble(java.io.PrintWriter ps, Translator tr, int start,
162: int limit) {
163: Vector pattern_names = null;
164: if (tr != null && tr.patternScope != null)
165: pattern_names = tr.patternScope.pattern_names;
166: int value = 0;
167: for (int i = start; i < limit;) {
168: char ch = program.charAt(i);
169: ps.print(" " + i + ": " + (int) ch);
170: i++;
171: int opcode = ch & 7;
172: value = (value << 13) | (ch >> 3);
173: switch (opcode) {
174: case MATCH_WIDE:
175: ps.println(" - WIDE " + value);
176: continue;
177: case MATCH_EQUALS:
178: ps.print(" - EQUALS[" + value + "]");
179: if (literals != null && value >= 0
180: && value < literals.length)
181: ps.print(literals[value]);
182: ps.println();
183: break;
184: case MATCH_ANY:
185: case MATCH_ANY_CAR:
186: ps.print((opcode == MATCH_ANY ? " - ANY["
187: : " - ANY_CAR[")
188: + value + "]");
189: if (pattern_names != null && value >= 0
190: && value < pattern_names.size())
191: ps.print(pattern_names.elementAt(value));
192: ps.println();
193: break;
194: case MATCH_PAIR:
195: ps.println(" - PAIR[" + value + "]");
196: break;
197: case MATCH_LREPEAT:
198: ps.println(" - LREPEAT[" + value + "]");
199: disassemble(ps, tr, i, i + value);
200: i += value;
201: ps.println(" " + i + ": - repeat first var:"
202: + (program.charAt(i++) >> 3));
203: ps.println(" " + i + ": - repeast nested vars:"
204: + (program.charAt(i++) >> 3));
205: break;
206: case MATCH_LENGTH:
207: ps.println(" - LENGTH "
208: + (value >> 1)
209: + " pairs. "
210: + (((value & 1) == 0 ? "pure list"
211: : "impure list")));
212: break;
213: case MATCH_MISC:
214: ps.print("[misc ch:" + (int) ch + " n:"
215: + (int) (MATCH_NIL) + "]");
216: if (ch == MATCH_NIL) {
217: ps.println(" - NIL");
218: break;
219: }
220: if (ch == MATCH_VECTOR) {
221: ps.println(" - VECTOR");
222: break;
223: }
224: if (ch == MATCH_IGNORE) {
225: ps.println(" - IGNORE");
226: break;
227: }
228: default:
229: ps.println(" - " + opcode + '/' + value);
230: break;
231: }
232: value = 0;
233: }
234: }
235:
236: /**
237: * @param context 'V' : vector elements; 'P' : car of Pair; '\0' : other.
238: */
239: void translate(Object pattern, StringBuffer program,
240: Object[] literal_identifiers, int nesting, Vector literals,
241: SyntaxForm syntax, char context, Translator tr) {
242: PatternScope patternScope = tr.patternScope;
243: Vector patternNames = patternScope.pattern_names;
244: for (;;) {
245: while (pattern instanceof SyntaxForm) {
246: syntax = (SyntaxForm) pattern;
247: pattern = syntax.form;
248: }
249: if (pattern instanceof Pair) {
250: Object savePos = tr.pushPositionOf(pattern);
251: try {
252: int start_pc = program.length();
253: program.append((char) MATCH_PAIR);
254: Pair pair = (Pair) pattern;
255: SyntaxForm car_syntax = syntax;
256: Object next = pair.cdr;
257: while (next instanceof SyntaxForm) {
258: syntax = (SyntaxForm) next;
259: next = syntax.form;
260: }
261: boolean repeat = false;
262: if (next instanceof Pair
263: && tr.matches(((Pair) next).car,
264: SyntaxRule.dots3)) {
265: repeat = true;
266: next = ((Pair) next).cdr;
267: while (next instanceof SyntaxForm) {
268: syntax = (SyntaxForm) next;
269: next = syntax.form;
270: }
271: }
272:
273: int subvar0 = patternNames.size();
274: if (context == 'P')
275: context = '\0';
276: translate(pair.car, program, literal_identifiers,
277: repeat ? nesting + 1 : nesting, literals,
278: car_syntax, context == 'V' ? '\0' : 'P', tr);
279: int subvarN = patternNames.size() - subvar0;
280: int width = ((program.length() - start_pc - 1) << 3)
281: | (repeat ? MATCH_LREPEAT : MATCH_PAIR);
282: if (width > 0xFFFF)
283: start_pc += insertInt(start_pc, program,
284: (width >> 13) + MATCH_WIDE);
285: program.setCharAt(start_pc, (char) width);
286:
287: int restLength = Translator.listLength(next);
288: if (restLength == Integer.MIN_VALUE) {
289: tr.syntaxError("cyclic pattern list");
290: return;
291: }
292:
293: if (repeat) {
294: addInt(program, subvar0 << 3);
295: addInt(program, subvarN << 3);
296: if (next == LList.Empty) {
297: program.append((char) MATCH_NIL);
298: return;
299: } else {
300: // Map a signed int to an unsigned.
301: restLength = restLength >= 0 ? restLength << 1
302: : ((-restLength) << 1) - 1;
303: addInt(program, (restLength << 3)
304: | MATCH_LENGTH);
305: }
306: }
307:
308: pattern = next;
309: continue;
310: } finally {
311: tr.popPositionOf(savePos);
312: }
313: } else if (pattern instanceof String
314: || pattern instanceof Symbol) {
315: for (int j = literal_identifiers.length; --j >= 0;) {
316: ScopeExp scope = syntax == null ? tr.currentScope()
317: : syntax.scope;
318: if (literalIdentifierEq(pattern, scope,
319: literal_identifiers[j])) {
320: int i = SyntaxTemplate.indexOf(literals,
321: pattern);
322: if (i < 0) {
323: i = literals.size();
324: literals.addElement(pattern);
325: }
326: addInt(program, (i << 3) | MATCH_EQUALS);
327: return;
328: }
329: }
330: if (patternNames.contains(pattern))
331: tr.syntaxError("duplicated pattern variable "
332: + pattern);
333: int i = patternNames.size();
334: patternNames.addElement(pattern);
335: boolean matchCar = context == 'P';
336: int n = (nesting << 1) + (matchCar ? 1 : 0);
337: patternScope.patternNesting.append((char) n);
338: Declaration decl = patternScope.addDeclaration(pattern);
339: decl.setLocation(tr);
340: tr.push(decl);
341: addInt(program, (i << 3)
342: | (matchCar ? MATCH_ANY_CAR : MATCH_ANY));
343: return;
344: } else if (pattern == LList.Empty) {
345: program.append((char) MATCH_NIL);
346: return;
347: } else if (pattern instanceof FVector) {
348: program.append((char) MATCH_VECTOR);
349: pattern = LList.makeList((FVector) pattern);
350: context = 'V';
351: continue;
352: } else {
353: int i = SyntaxTemplate.indexOf(literals, pattern);
354: if (i < 0) {
355: i = literals.size();
356: literals.addElement(pattern);
357: }
358: addInt(program, (i << 3) | MATCH_EQUALS);
359: return;
360: }
361: }
362: }
363:
364: private static void addInt(StringBuffer sbuf, int val) {
365: if (val > 0xFFFF)
366: addInt(sbuf, (val << 13) + MATCH_WIDE);
367: sbuf.append((char) (val));
368: }
369:
370: private static int insertInt(int offset, StringBuffer sbuf, int val) {
371: if (val > 0xFFFF)
372: offset += insertInt(offset, sbuf, (val << 13) + MATCH_WIDE);
373: sbuf.insert(offset, (char) (val));
374: return offset + 1;
375: }
376:
377: /** Match the <code>car</code> of a <code>Pair</code>.
378: * This special case (instead of of just matching the <code>car</code>
379: * directly), is so we can copy <code>PairWithPosition</code> line number
380: * info into the output of a template. */
381: boolean match_car(Pair p, Object[] vars, int start_vars, int pc,
382: SyntaxForm syntax) {
383: int pc_start = pc;
384: char ch;
385: int value = (ch = program.charAt(pc++)) >> 3;
386: while ((ch & 7) == MATCH_WIDE)
387: value = (value << 13) | ((ch = program.charAt(pc++)) >> 3);
388: if ((ch & 7) == MATCH_ANY_CAR) {
389: if (syntax != null && !(p.car instanceof SyntaxForm))
390: p = Translator.makePair(p, syntax.fromDatum(p.car),
391: p.cdr);
392: vars[start_vars + value] = p;
393: return true;
394: }
395: return match(p.car, vars, start_vars, pc_start, syntax);
396: }
397:
398: public boolean match(Object obj, Object[] vars, int start_vars,
399: int pc, SyntaxForm syntax) {
400: int value = 0;
401: Pair p;
402: for (;;) {
403: while (obj instanceof SyntaxForm) {
404: syntax = (SyntaxForm) obj;
405: obj = syntax.form;
406: }
407: char ch = program.charAt(pc++);
408: int opcode = ch & 7;
409: value = (value << 13) | (ch >> 3);
410: switch (opcode) {
411: case MATCH_WIDE:
412: continue;
413: case MATCH_MISC:
414: if (ch == MATCH_NIL)
415: return obj == LList.Empty;
416: else if (ch == MATCH_VECTOR) {
417: if (!(obj instanceof FVector))
418: return false;
419: return match(LList.makeList((FVector) obj), vars,
420: start_vars, pc, syntax);
421: } else if (ch == MATCH_IGNORE)
422: return true;
423: else
424: throw new Error("unknwon pattern opcode");
425: case MATCH_NIL:
426: return obj == LList.Empty;
427: case MATCH_LENGTH:
428: int npairs = value >> 1;
429: Object o = obj;
430: for (int i = 0;; i++) {
431: while (o instanceof SyntaxForm)
432: o = ((SyntaxForm) o).form;
433: if (i == npairs) {
434: if ((value & 1) == 0 ? o != LList.Empty
435: : o instanceof Pair)
436: return false;
437: break;
438: } else if (o instanceof Pair)
439: o = ((Pair) o).cdr;
440: else
441: return false;
442: }
443: value = 0;
444: continue;
445: case MATCH_PAIR:
446: if (!(obj instanceof Pair))
447: return false;
448: p = (Pair) obj;
449: if (!match_car(p, vars, start_vars, pc, syntax))
450: return false;
451: pc += value;
452: value = 0;
453: obj = p.cdr;
454: continue;
455: case MATCH_LREPEAT:
456: int repeat_pc = pc;
457: pc += value;
458: int subvar0 = (ch = program.charAt(pc++)) >> 3;
459: while ((ch & 0x7) == MATCH_WIDE)
460: subvar0 = (subvar0 << 13)
461: | ((ch = program.charAt(pc++)) >> 3);
462: subvar0 += start_vars;
463: int subvarN = program.charAt(pc++) >> 3;
464: while ((ch & 0x7) == MATCH_WIDE)
465: subvarN = (subvarN << 13)
466: | ((ch = program.charAt(pc++)) >> 3);
467:
468: ch = program.charAt(pc++);
469: boolean listRequired = true;
470: int pairsRequired;
471: if (ch == MATCH_NIL) {
472: pairsRequired = 0;
473: } else {
474: value = ch >> 3;
475: while ((ch & 0x7) == MATCH_WIDE)
476: value = (value << 13)
477: | ((ch = program.charAt(pc++)) >> 3);
478: if ((value & 1) != 0)
479: listRequired = false;
480: pairsRequired = value >> 1;
481: }
482: int pairsValue = Translator.listLength(obj);
483: boolean listValue;
484:
485: if (pairsValue >= 0)
486: listValue = true;
487: else {
488: listValue = false;
489: pairsValue = -1 - pairsValue;
490: }
491: if (pairsValue < pairsRequired
492: || (listRequired && !listValue))
493: return false;
494: int repeat_count = pairsValue - pairsRequired;
495: Object[][] arrays = new Object[subvarN][];
496:
497: for (int j = 0; j < subvarN; j++)
498: arrays[j] = new Object[repeat_count];
499: for (int i = 0; i < repeat_count; i++) {
500: while (obj instanceof SyntaxForm) {
501: syntax = (SyntaxForm) obj;
502: obj = syntax.form;
503: }
504: p = (Pair) obj;
505: if (!match_car(p, vars, start_vars, repeat_pc,
506: syntax))
507: return false;
508: obj = p.cdr;
509: for (int j = 0; j < subvarN; j++)
510: arrays[j][i] = vars[subvar0 + j];
511: }
512: for (int j = 0; j < subvarN; j++)
513: vars[subvar0 + j] = arrays[j];
514: value = 0;
515: if (pairsRequired == 0 && listRequired)
516: return true;
517: continue;
518: case MATCH_EQUALS:
519: Object lit = literals[value];
520: // We should be using Translator's matches routine, but the current
521: // Translator isn't available, so here is a special-purpose kludge.
522: if (lit instanceof String && obj instanceof Symbol)
523: obj = ((Symbol) obj).getName();
524: return lit.equals(obj);
525: case MATCH_ANY:
526: if (syntax != null)
527: obj = syntax.fromDatum(obj);
528: vars[start_vars + value] = obj;
529: return true;
530: case MATCH_ANY_CAR: // Disallowed here.
531: default:
532: disassemble();
533: throw new Error("unrecognized pattern opcode @pc:" + pc);
534: }
535: }
536: }
537:
538: public void writeExternal(ObjectOutput out) throws IOException {
539: out.writeObject(program);
540: out.writeObject(literals);
541: out.writeInt(varCount);
542: }
543:
544: public void readExternal(ObjectInput in) throws IOException,
545: ClassNotFoundException {
546: literals = (Object[]) in.readObject();
547: program = (String) in.readObject();
548: varCount = in.readInt();
549: }
550:
551: /** The compiler calls this method to implement syntax-case. */
552: public static Object[] allocVars(int varCount, Object[] outer) {
553: Object[] vars = new Object[varCount];
554: if (outer != null)
555: System.arraycopy(outer, 0, vars, 0, outer.length);
556: return vars;
557: }
558:
559: public static boolean literalIdentifierEq(Object id1, ScopeExp sc1,
560: Object literal2) {
561: if (literal2 instanceof SyntaxForm) {
562: SyntaxForm syntax = (SyntaxForm) literal2;
563: return literalIdentifierEq(id1, sc1, syntax.form,
564: syntax.scope);
565: }
566: return literalIdentifierEq(id1, sc1, literal2, null);
567: }
568:
569: public static boolean literalIdentifierEq(Object id1, ScopeExp sc1,
570: Object id2, ScopeExp sc2) {
571: if (id1 != id2)
572: return false;
573: Declaration d1 = null, d2 = null;
574: while (sc1 != null && !(sc1 instanceof ModuleExp)) {
575: d1 = sc1.lookup(id1);
576: if (d1 != null)
577: break;
578: sc1 = sc1.outer;
579: }
580: while (sc2 != null && !(sc2 instanceof ModuleExp)) {
581: d2 = sc1.lookup(id1);
582: if (d2 != null)
583: break;
584: sc2 = sc2.outer;
585: }
586: return d1 == d2;
587: }
588:
589: /** Parse the literals list in a syntax-rules or syntax-case. */
590: public static Object[] getLiteralsList(Object list,
591: SyntaxForm syntax, Translator tr) {
592: Object savePos = tr.pushPositionOf(list);
593: int count = Translator.listLength(list);
594: if (count < 0) {
595: tr.error('e', "missing or malformed literals list");
596: count = 0;
597: }
598: Object[] literals = new Object[count + 1];
599: for (int i = 1; i <= count; i++) {
600: while (list instanceof SyntaxForm) {
601: syntax = (SyntaxForm) list;
602: list = syntax.form;
603: }
604: Pair pair = (Pair) list;
605: tr.pushPositionOf(pair);
606: Object literal = pair.car;
607: Object wrapped;
608: if (literal instanceof SyntaxForm) {
609: wrapped = literal;
610: literal = ((SyntaxForm) literal).form;
611: } else
612: wrapped = literal; // FIXME
613: if (!(literal instanceof String || literal instanceof gnu.mapping.Symbol))
614: tr.error('e', "non-symbol '" + literal
615: + "' in literals list");
616: literals[i] = wrapped;
617: list = pair.cdr;
618: }
619: tr.popPositionOf(savePos);
620: return literals;
621: }
622:
623: public void print(Consumer out) {
624: out.write("#<syntax-pattern>");
625: }
626: }
|