001: package kawa.lang;
002:
003: import gnu.lists.*;
004: import java.io.*;
005: import gnu.mapping.*;
006: import gnu.expr.*;
007: import java.util.*;
008:
009: /** The translated form of a <code>(syntax <var>template</var>)</code>. */
010:
011: public class SyntaxTemplate implements Externalizable {
012: /** A <code>syntax</code> or <code>syntax-rules</code> template is
013: * translated into a "template program."
014: * The template program is a simple bytecode stored in a string.
015: * The encoding is designed so that instructions are normally
016: * in the range 1..127, which makes the <code>CONSTANT_Utf8</code> encoding
017: * used in <code>.class</code> files compact.
018: * The folowing <code>BUILD_XXX</code> are the "opcode" of the encoding,
019: * stored in the low-order 3 bits of a <code>char</code>.
020: */
021: String template_program;
022:
023: /** Template instructions that don't have an operand value. */
024: static final int BUILD_MISC = 0;
025:
026: /** Make following operand into a 1-element list. */
027: static final int BUILD_LIST1 = (1 << 3) + BUILD_MISC;
028:
029: static final int BUILD_NIL = (2 << 3) + BUILD_MISC;
030:
031: /** Wrap following sub-expression in a SyntaxForm. */
032: static final int BUILD_SYNTAX = (3 << 3) + BUILD_MISC;
033:
034: /** Build a vector (an <code>FVector</code>) from following sub-expression.
035: * The latter must evaluate to a list. */
036: static final int BUILD_VECTOR = (5 << 3) + BUILD_MISC;
037:
038: /** Instruction to creat a <code>Pair</code> from sub-expressions.
039: * Instruction <code>BUILD_CONS+4*delta</code> is followed by a
040: * sub-expression for the <code>car</code>
041: * (whose length is <code>delta</code> chars),
042: * followed by the expression for the <code>cdr</code>. */
043: static final int BUILD_CONS = 1;
044:
045: /** Instruction BUILD_VAR+8*i pushes vars[i].
046: * This array contains the values of pattern variables. */
047: final static int BUILD_VAR = 2; // Must be an even number.
048:
049: /** Instruction BUILD_VAR_CAR+8*i pushes car(vars[i]).
050: * It assumes that vars[i] is actually a pair whose car was the
051: * matched pattern variable. (This is done so we can preserve
052: * <code>PairWithPosition</code> source positions). */
053: final static int BUILD_VAR_CAR = BUILD_VAR + 1;
054:
055: /** Instruction BUILD_LITERAL+8*i pushes literal_values[i]. */
056: final static int BUILD_LITERAL = 4;
057:
058: /** Instruction <code>BUILD_DOTS+8*i</code> repeats a sub-expression.
059: * The value <code>i</code> is a variable index of a pattern variable
060: * of at least the needed depth. The result is spliced in. */
061: final static int BUILD_DOTS = 5;
062:
063: /** Unfinished support for "operand" values that need more tahn 13 bits. */
064: final static int BUILD_WIDE = 7;
065:
066: /** Map variable to ellipsis nesting depth.
067: * The nesting depth of the <code>i</code>'th pattern variable
068: * is <code>(int) patternNesting.charAt(i)/2</code>.
069: * The low-order bit indicates that if matched value is the <code>car</code>
070: * of the value saved in the <code>vars</code> array.
071: * (We use a <code>String</code> because it is compact both at runtime
072: * and in <code>.class</code> files. */
073: String patternNesting;
074:
075: int max_nesting;
076:
077: Object[] literal_values;
078:
079: static final String dots3 = "...";
080:
081: /* DEBUGGING:
082: void print_template_program (java.util.Vector patternNames,
083: java.io.PrintWriter ps)
084: {
085: print_template_program(patternNames, ps,
086: 0, template_program.length());
087: ps.flush();
088: }
089:
090: void print_template_program (java.util.Vector patternNames,
091: java.io.PrintWriter ps,
092: int start, int limit)
093: {
094: for (int i = start; i < limit; i++)
095: {
096: char ch = template_program.charAt(i);
097: ps.print(" " + i + ": " + (int)ch);
098: if (ch == BUILD_LIST1)
099: 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: protected SyntaxTemplate() {
149: }
150:
151: public SyntaxTemplate(String patternNesting,
152: String template_program, Object[] literal_values,
153: int max_nesting) {
154: this .patternNesting = patternNesting;
155: this .template_program = template_program;
156: this .literal_values = literal_values;
157: this .max_nesting = max_nesting;
158: }
159:
160: public SyntaxTemplate(Object template, SyntaxForm syntax,
161: Translator tr) {
162: this .patternNesting = tr == null || tr.patternScope == null ? ""
163: : tr.patternScope.patternNesting.toString();
164: StringBuffer program = new StringBuffer();
165: java.util.Vector literals_vector = new java.util.Vector();
166: /* #ifdef use:java.util.IdentityHashMap */
167: IdentityHashMap seen = new IdentityHashMap();
168: /* #else */
169: // Object seen = null;
170: /* #endif */
171: convert_template(template, syntax, program, 0, literals_vector,
172: seen, false, tr);
173: this .template_program = program.toString();
174: this .literal_values = new Object[literals_vector.size()];
175: literals_vector.copyInto(this .literal_values);
176:
177: /* DEBUGGING:
178: OutPort err = OutPort.errDefault();
179: err.print("{translated template");
180: Macro macro = tr.currentMacroDefinition;
181: if (macro != null)
182: {
183: err.print(" for ");
184: err.print(macro);
185: }
186: if (tr != null && tr.patternScope != null)
187: {
188: err.println(" - ");
189: print_template_program (tr.patternScope.pattern_names, err);
190: }
191: err.println ('}');
192: */
193: }
194:
195: /** Recursively translate a syntax-rule template to a template program.
196: * @param form the template from the syntax-rule
197: * @param syntax if non-null, the closest surrounding <code>SyntaxForm</code>
198: * @param template_program (output) the translated template
199: * @param nesting the depth of ... we are inside
200: * @param literals_vector (output) the literal data in the template
201: * @param tr the current Translator
202: * @return the index of a pattern variable (in <code>pattern_names</code>)
203: * that is nested at least as much as <code>nesting</code>;
204: * if there is none such, -1 if there is any pattern variable or elipsis;
205: * and -2 if the is no pattern variable or elipsis.
206: */
207: public int convert_template(Object form, SyntaxForm syntax,
208: StringBuffer template_program, int nesting,
209: java.util.Vector literals_vector, Object seen,
210: boolean isVector, Translator tr) {
211: while (form instanceof SyntaxForm) {
212: syntax = (SyntaxForm) form;
213: form = syntax.form;
214: }
215: /* #ifdef use:java.util.IdentityHashMap */
216: if (form instanceof Pair || form instanceof FVector) {
217: IdentityHashMap seen_map = (IdentityHashMap) seen;
218: if (seen_map.containsKey(form)) {
219: /* FIXME cycles are OK if data are literal. */
220: tr
221: .syntaxError("self-referential (cyclic) syntax template");
222: return -2;
223: }
224: seen_map.put(form, form);
225: }
226: /* #endif */
227:
228: check_form: if (form instanceof Pair) {
229: Pair pair = (Pair) form;
230: int ret_cdr = -2;
231: ;
232: int save_pc = template_program.length();
233: Object car = pair.car;
234:
235: // Look for (... ...) and translate that to ...
236: if (tr.matches(car, dots3)) {
237: Object cdr = Translator.stripSyntax(pair.cdr);
238: if (cdr instanceof Pair) {
239: Pair cdr_pair = (Pair) cdr;
240: if (cdr_pair.car == dots3
241: && cdr_pair.cdr == LList.Empty) {
242: form = dots3;
243: break check_form;
244: }
245: }
246: }
247:
248: int save_literals = literals_vector.size();
249:
250: // This may get patched to a BUILD_CONS.
251: template_program.append((char) BUILD_LIST1);
252:
253: int num_dots3 = 0;
254: Object rest = pair.cdr;
255: while (rest instanceof Pair) {
256: Pair p = (Pair) rest;
257: if (!tr.matches(p.car, dots3))
258: break;
259: num_dots3++;
260: rest = p.cdr;
261: template_program.append((char) BUILD_DOTS); // to be patched.
262: }
263: int ret_car = convert_template(car, syntax,
264: template_program, nesting + num_dots3,
265: literals_vector, seen, false, tr);
266:
267: if (rest != LList.Empty) {
268: int delta = template_program.length() - save_pc - 1;
269: template_program.setCharAt(save_pc,
270: (char) ((delta << 3) + BUILD_CONS));
271: ret_cdr = convert_template(rest, syntax,
272: template_program, nesting, literals_vector,
273: seen, isVector, tr);
274: }
275: if (num_dots3 > 0) {
276: if (ret_car < 0)
277: tr
278: .syntaxError("... follows template with no suitably-nested pattern variable");
279: for (int i = num_dots3; --i >= 0;) {
280: char op = (char) ((ret_car << 3) + BUILD_DOTS);
281: template_program.setCharAt(save_pc + i + 1, op);
282: int n = nesting + num_dots3;
283: if (n >= max_nesting)
284: max_nesting = n;
285: }
286: }
287: if (ret_car >= 0)
288: return ret_car;
289: if (ret_cdr >= 0)
290: return ret_cdr;
291: if (ret_car == -1 || ret_cdr == -1)
292: return -1;
293: if (isVector)
294: return -2;
295: // There is no pattern variable in 'form', so treat it as literal.
296: // This is optimization to group non-substrituted "chunks"
297: // as a single literal and a single SyntaxForm value.
298: literals_vector.setSize(save_literals);
299: template_program.setLength(save_pc);
300: } else if (form instanceof FVector) {
301: template_program.append((char) BUILD_VECTOR);
302: return convert_template(LList.makeList((FVector) form),
303: syntax, template_program, nesting, literals_vector,
304: seen, true, tr);
305: } else if (form == LList.Empty) {
306: template_program.append((char) BUILD_NIL);
307: return -2;
308: } else if (form instanceof String && tr != null
309: && tr.patternScope != null) {
310: int pattern_var_num = indexOf(
311: tr.patternScope.pattern_names, form);
312: if (pattern_var_num >= 0) {
313: int var_nesting = patternNesting
314: .charAt(pattern_var_num);
315: int op = (var_nesting & 1) != 0 ? BUILD_VAR_CAR
316: : BUILD_VAR;
317: var_nesting >>= 1;
318: // R4RS requires that the nesting be equal.
319: // We allow an extension here, since it allows potentially-useful
320: // rules like (x (y ...) ...) => (((x y) ...) ...)
321: if (var_nesting > nesting)
322: tr.syntaxError("inconsistent ... nesting of "
323: + form);
324: template_program
325: .append((char) (op + 8 * pattern_var_num));
326: return var_nesting == nesting ? pattern_var_num : -1;
327: }
328: // else treated quoted symbol as literal:
329: }
330: int literals_index = indexOf(literals_vector, form);
331: if (literals_index < 0) {
332: literals_index = literals_vector.size();
333: literals_vector.addElement(form);
334: }
335: if (form instanceof String || form instanceof Symbol)
336: tr.noteAccess(form, tr.currentScope());
337: if (!(form instanceof SyntaxForm) && form != dots3)
338: template_program.append((char) (BUILD_SYNTAX));
339: template_program
340: .append((char) (BUILD_LITERAL + 8 * literals_index));
341: return form == dots3 ? -1 : -2;
342: }
343:
344: /** Similar to vec.indexOf(elem), but uses == (not equals) to compare. */
345: static int indexOf(java.util.Vector vec, Object elem) {
346: int len = vec.size();
347: for (int i = 0; i < len; i++) {
348: if (vec.elementAt(i) == elem)
349: return i;
350: }
351: return -1;
352: }
353:
354: /** The the current repeat count. */
355: private int get_count(Object var, int nesting, int[] indexes) {
356: for (int level = 0; level < nesting; level++)
357: var = ((Object[]) var)[indexes[level]];
358: Object[] var_array = (Object[]) var;
359: return var_array.length;
360: }
361:
362: /** Expand this template
363: * The compiler translates <code>(syntax <var>template</var>)</code>
364: * to a call to this method.
365: */
366: public Object execute(Object[] vars, TemplateScope templateScope) {
367: if (false) // DEBUGGING
368: {
369: OutPort err = OutPort.errDefault();
370: err.print("{Expand template in ");
371: err.print(((Translator) Compilation.getCurrent())
372: .getCurrentSyntax());
373: err.print(" tscope: ");
374: err.print(templateScope);
375: if (false && vars != null) {
376: err.print(" vars: ");
377: for (int i = 0; i < vars.length; i++) {
378: err.println();
379: err.print(" " + i + " : ");
380: kawa.standard.Scheme.writeFormat.writeObject(
381: vars[i], err);
382: }
383: }
384: err.println('}');
385: }
386:
387: Object result = execute(0, vars, 0, new int[max_nesting],
388: (Translator) Compilation.getCurrent(), templateScope);
389:
390: if (false) // DEBUGGING:
391: {
392: OutPort err = OutPort.errDefault();
393: err.startLogicalBlock("", false, "}");
394: err.print("{Expansion of syntax template ");
395: err.print(((Translator) Compilation.getCurrent())
396: .getCurrentSyntax());
397: err.print(": ");
398: err.writeBreakLinear();
399: kawa.standard.Scheme.writeFormat.writeObject(result, err);
400: err.endLogicalBlock("}");
401: err.println();
402: err.flush();
403: }
404: return result;
405: }
406:
407: public Object execute(Object[] vars, Translator tr,
408: TemplateScope templateScope) {
409: return execute(0, vars, 0, new int[max_nesting], tr,
410: templateScope);
411: }
412:
413: Object get_var(int var_num, Object[] vars, int[] indexes) {
414: Object var = vars[var_num];
415: if (var_num < patternNesting.length()) {
416: int var_nesting = (int) patternNesting.charAt(var_num) >> 1;
417: for (int level = 0; level < var_nesting; level++)
418: var = ((Object[]) var)[indexes[level]];
419: }
420: return var;
421: }
422:
423: /** Similar to execute, but return is wrapped in a list.
424: * Normally the result is a single Pair, BUILD_DOTS can return zero
425: * or many Pairs. */
426: LList executeToList(int pc, Object[] vars, int nesting,
427: int[] indexes, Translator tr, TemplateScope templateScope) {
428: int pc0 = pc;
429: int ch = template_program.charAt(pc);
430: while ((ch & 7) == BUILD_WIDE)
431: ch = ((ch - BUILD_WIDE) << 13)
432: | template_program.charAt(++pc);
433: if ((ch & 7) == BUILD_VAR_CAR) {
434: Pair p = (Pair) get_var(ch >> 3, vars, indexes);
435: return Translator.makePair(p, p.car, LList.Empty);
436: } else if ((ch & 7) == BUILD_DOTS) {
437: int var_num = (int) (ch >> 3);
438: Object var = vars[var_num];
439: int count = get_count(var, nesting, indexes);
440: LList result = LList.Empty;
441: Pair last = null; // Final Pair of result list, or null.
442: pc++;
443: for (int j = 0; j < count; j++) {
444: indexes[nesting] = j;
445: LList list = executeToList(pc, vars, nesting + 1,
446: indexes, tr, templateScope);
447: if (last == null)
448: result = list;
449: else
450: last.cdr = list;
451: // Normally list is a single Pair, but if it is multiple Pairs,
452: // find the last Pair so we can properly splice everything.
453: while (list instanceof Pair) {
454: last = (Pair) list;
455: list = (LList) last.cdr;
456: }
457: }
458: return result;
459: }
460: Object v = execute(pc0, vars, nesting, indexes, tr,
461: templateScope);
462: return new Pair(v, LList.Empty);
463: }
464:
465: /**
466: * @param nesting number of levels of ... we are nested inside
467: * @param indexes element i (where i in [0 .. nesting-1] specifies
468: * the iteration index for the i'level of nesting
469: */
470: Object execute(int pc, Object[] vars, int nesting, int[] indexes,
471: Translator tr, TemplateScope templateScope) {
472: int ch = template_program.charAt(pc);
473: /* DEBUGGING:
474: System.err.print ("{execute template pc:"+pc
475: + " ch:"+(int)ch+" nesting:[");
476: for (int level=0; level < nesting; level++)
477: System.err.print ((level > 0 ? " " : "") + indexes[level]);
478: System.err.println("]}");
479: */
480: while ((ch & 7) == BUILD_WIDE)
481: ch = ((ch - BUILD_WIDE) << 13)
482: | template_program.charAt(++pc);
483: if (ch == BUILD_LIST1) {
484: return executeToList(pc + 1, vars, nesting, indexes, tr,
485: templateScope);
486: } else if (ch == BUILD_NIL)
487: return LList.Empty;
488: else if (ch == BUILD_SYNTAX) {
489: Object v = execute(pc + 1, vars, nesting, indexes, tr,
490: templateScope);
491: return v == LList.Empty ? v : SyntaxForm.make(v,
492: templateScope);
493: } else if ((ch & 7) == BUILD_CONS) {
494: Pair p = null;
495: Object result = null;
496: for (;;) {
497: pc++;
498: Object q = executeToList(pc, vars, nesting, indexes,
499: tr, templateScope);
500: if (p == null)
501: result = q;
502: else
503: p.cdr = q;
504: while (q instanceof Pair) {
505: p = (Pair) q;
506: q = p.cdr;
507: }
508: pc += ch >> 3;
509: ch = template_program.charAt(pc);
510: if ((ch & 7) != BUILD_CONS)
511: break;
512: }
513: Object cdr = execute(pc, vars, nesting, indexes, tr,
514: templateScope);
515: if (p == null)
516: result = cdr;
517: else
518: p.cdr = cdr;
519: return result;
520: } else if (ch == BUILD_VECTOR) {
521: Object el = execute(pc + 1, vars, nesting, indexes, tr,
522: templateScope);
523: return new FVector((LList) el);
524: } else if ((ch & 7) == BUILD_LITERAL) {
525: int lit_no = ch >> 3;
526: /* DEBUGGING:
527: System.err.println("-- insert literal#"+lit_no
528: +": "+literal_values[lit_no]);
529: */
530: return literal_values[lit_no];
531: } else if ((ch & 6) == BUILD_VAR) // Also handles BUILD_VAR_CAR.
532: {
533: Object var = get_var(ch >> 3, vars, indexes);
534: if ((ch & 7) == BUILD_VAR_CAR)
535: var = ((Pair) var).car;
536: return var;
537: } else
538: throw new Error("unknown template code: " + ((int) ch)
539: + " at " + pc);
540: }
541:
542: /**
543: * @serialData
544: */
545: public void writeExternal(ObjectOutput out) throws IOException {
546: out.writeObject(patternNesting);
547: out.writeObject(template_program);
548: out.writeObject(literal_values);
549: out.writeInt(max_nesting);
550: }
551:
552: public void readExternal(ObjectInput in) throws IOException,
553: ClassNotFoundException {
554: patternNesting = (String) in.readObject();
555: template_program = (String) in.readObject();
556: literal_values = (Object[]) in.readObject();
557: max_nesting = in.readInt();
558: }
559: }
|