001: /*
002: * xtc - The eXTensible Compiler
003: * Copyright (C) 2006-2007 Robert Grimm
004: *
005: * This program is free software; you can redistribute it and/or
006: * modify it under the terms of the GNU General Public License
007: * version 2 as published by the Free Software Foundation.
008: *
009: * This program is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
012: * GNU General Public License for more details.
013: *
014: * You should have received a copy of the GNU General Public License
015: * along with this program; if not, write to the Free Software
016: * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
017: * USA.
018: */
019: package xtc.parser;
020:
021: import java.util.ArrayList;
022: import java.util.HashSet;
023: import java.util.List;
024: import java.util.Set;
025:
026: import xtc.Constants;
027:
028: import xtc.tree.Printer;
029: import xtc.tree.Visitor;
030:
031: import xtc.type.AST;
032: import xtc.type.Type;
033: import xtc.type.TupleT;
034: import xtc.type.UnitT;
035: import xtc.type.VariantT;
036:
037: import xtc.util.Runtime;
038:
039: /**
040: * Visitor to determine a grammar's tree structure. This visitor
041: * assumes that the entire grammar is contained in a single module and
042: * has been annotated with appropriate value elements.
043: *
044: * @author Robert Grimm
045: * @version $Revision: 1.26 $
046: */
047: public class TreeTyper extends Visitor {
048:
049: /** The debug flag. */
050: private static final boolean DEBUG = false;
051:
052: /** The runtime. */
053: protected final Runtime runtime;
054:
055: /** The analyzer utility. */
056: protected final Analyzer analyzer;
057:
058: /** The common type operations. */
059: protected final AST ast;
060:
061: /** The flag for strict unification. */
062: protected boolean strict;
063:
064: /** The flag for flattening lists. */
065: protected boolean flatten;
066:
067: /** The current sequence. */
068: protected Sequence sequence;
069:
070: /**
071: * Create a new tree typer.
072: *
073: * @param runtime The runtime.
074: * @param ast The type operations.
075: * @param analyzer The analyzer utility.
076: */
077: public TreeTyper(Runtime runtime, Analyzer analyzer, AST ast) {
078: this .runtime = runtime;
079: this .analyzer = analyzer;
080: this .ast = ast;
081: }
082:
083: /** Visit the specified module. */
084: public void visit(Module m) {
085: // Initialize the per-grammar state.
086: analyzer.register(this );
087: analyzer.init(m);
088:
089: strict = runtime.test("optionVariant");
090: flatten = m.hasAttribute(Constants.ATT_FLATTEN);
091:
092: // Process the productions.
093: for (Production p : m.productions)
094: analyzer.process(p);
095:
096: // Print the header.
097: final Printer printer = runtime.console();
098:
099: printer.sep();
100: printer.indent().p("// Generated by Rats!, version ").p(
101: Constants.VERSION).p(", ").p(Constants.COPY).pln('.');
102: printer.sep();
103: printer.pln();
104:
105: printer.indent().p("/** AST structure for grammar ").p(
106: m.name.name).pln(". */");
107:
108: // Ensure that all tuples are concrete and then print the result.
109: if (!runtime.test("optionVariant")) {
110: // Flat AST definition.
111: final VariantT node = ast.toVariant("Node", false);
112:
113: ast.concretizeTuples(node, UnitT.TYPE);
114: printer.indent().p("module ").p(m.name.name).p("Tree").pln(
115: ';');
116: printer.pln();
117: ast.print(node, printer, true, false, null);
118: printer.pln();
119:
120: } else {
121: // Hierarchical AST definition.
122: final VariantT root = analyzer.lookup((NonTerminal) m
123: .getProperty(Properties.ROOT)).type.resolve()
124: .toVariant();
125: final AST.MetaData meta = ast.getMetaData(root);
126: final Set<String> processed = new HashSet<String>();
127:
128: // Concretize variants.
129: for (Production p : m.productions) {
130: if (AST.isStaticNode(p.type)) {
131: final VariantT variant = p.type.resolve()
132: .toVariant();
133: final String name = variant.getName();
134:
135: if (meta.reachable.contains(name)
136: && !processed.contains(name)) {
137: processed.add(name);
138: ast.concretizeTuples(variant, UnitT.TYPE);
139: }
140: }
141: }
142: processed.clear();
143:
144: // Print variants...
145: if (!meta.modularize) {
146: // ... in a single module.
147: printer.indent().p("module ").p(m.name.name).p("Tree")
148: .pln(';');
149: printer.pln();
150:
151: for (Production p : m.productions) {
152: if (AST.isStaticNode(p.type)) {
153: final VariantT variant = p.type.resolve()
154: .toVariant();
155: final String name = variant.getName();
156:
157: if (meta.reachable.contains(name)
158: && !processed.contains(name)) {
159: processed.add(name);
160: ast.print(variant, printer, true, false,
161: null);
162: printer.pln();
163: }
164: }
165: }
166:
167: } else {
168: // ... across several modules.
169: boolean first = true;
170: String module;
171:
172: do {
173: module = null;
174:
175: for (Production p : m.productions) {
176: if (AST.isStaticNode(p.type)) {
177: final VariantT variant = p.type.resolve()
178: .toVariant();
179: final String name = variant.getName();
180:
181: if (meta.reachable.contains(name)
182: && !processed.contains(name)) {
183: final String qualifier = variant
184: .getQualifier();
185:
186: if (null == module) {
187: module = qualifier;
188:
189: if (first) {
190: first = false;
191: } else {
192: printer.sep().pln();
193: }
194: printer.indent().p("module ").p(
195: module).pln(';');
196: printer.pln();
197:
198: } else if (!module.equals(qualifier)) {
199: continue;
200: }
201:
202: processed.add(name);
203: ast.print(variant, printer, true, true,
204: module);
205: printer.pln();
206: }
207: }
208: }
209: } while (null != module);
210: }
211: }
212:
213: printer.sep().flush();
214: }
215:
216: /** Visit the specified production. */
217: public void visit(Production p) {
218: dispatch(p.choice);
219: }
220:
221: /** Visit the specified ordered choice. */
222: public void visit(OrderedChoice c) {
223: for (Sequence alt : c.alternatives)
224: dispatch(alt);
225: }
226:
227: /** Visit the specified sequence. */
228: public void visit(Sequence s) {
229: final Sequence old = sequence;
230: sequence = s;
231:
232: for (Element e : s.elements)
233: dispatch(e);
234:
235: sequence = old;
236: }
237:
238: /** Visit the specified unary operator. */
239: public void visit(UnaryOperator op) {
240: dispatch(op.element);
241: }
242:
243: /** Visit the specified element. */
244: public void visit(Element e) {
245: // Nothing to do.
246: }
247:
248: /** Visit the specified generic node value. */
249: public void visit(GenericNodeValue v) {
250: process(v.name, false, v.children);
251: }
252:
253: /** Visit the specified generic action value. */
254: public void visit(GenericActionValue v) {
255: process(v.name, true, v.children);
256: }
257:
258: /**
259: * Determine the type of the specified generic node constructor.
260: *
261: * @param name The constructor's name.
262: * @param isAction The flag for whether the constructor appears in an action.
263: * @param children The list of bindings for the children.
264: */
265: protected void process(String name, boolean isAction,
266: List<Binding> children) {
267: if (flatten) {
268: // Combine [ ..., nt, nt*, ... ] into [ ..., nt*, ... ]
269: boolean isCopy = false;
270: for (int i = 0; i < children.size() - 1; i++) {
271: // Check whether the first binding is for a nonterminal.
272: Binding b1 = children.get(i);
273: if (!(b1.element instanceof NonTerminal))
274: continue;
275: NonTerminal nt1 = (NonTerminal) b1.element;
276:
277: // Check whether the second binding is for a repeated nonterminal.
278: Binding b2 = children.get(i + 1);
279: switch (b2.element.tag()) {
280: case REPETITION: {
281: // Check the preserved repetition.
282: Repetition rep = (Repetition) b2.element;
283: Binding bdg = Analyzer
284: .getBinding(((Sequence) rep.element).elements);
285: if (null == bdg) {
286: throw new IllegalStateException(
287: "Malformed repetition " + rep);
288: }
289: if (!nt1.equals(bdg.element))
290: continue;
291: }
292: break;
293:
294: case NONTERMINAL: {
295: // Check the desugared repetition.
296: NonTerminal non = (NonTerminal) b2.element;
297: Production prod = analyzer.lookup(non);
298: if (!nt1.equals(prod
299: .getProperty(Properties.REPEATED)))
300: continue;
301: }
302: break;
303:
304: default:
305: continue;
306: }
307:
308: // Success.
309: if (!isCopy) {
310: children = new ArrayList<Binding>(children);
311: isCopy = true;
312: }
313: children.remove(i);
314: i -= 2; // Check the previous binding again.
315: if (-1 > i)
316: i = -1;
317: }
318: }
319:
320: // Determine the types of the bindings.
321: final int size = isAction ? children.size() + 1 : children
322: .size();
323: List<Type> types = new ArrayList<Type>(size);
324:
325: if (isAction) {
326: if (runtime.test("optionVariant")) {
327: // Strip away any list and action types.
328: Type t = analyzer.current().type;
329: if (AST.isList(t))
330: t = AST.getArgument(t);
331: if (AST.isAction(t))
332: t = AST.getArgument(t);
333: types.add(t);
334:
335: } else {
336: types.add(AST.NODE);
337: }
338: }
339:
340: for (Binding b : children) {
341: types.add(analyzer.type(b.element));
342: }
343:
344: // Unify the tuple type with any previous tuple type and update
345: // its variant.
346: final TupleT t1 = ast.toTuple(name);
347: final TupleT t2 = new TupleT(name, types);
348: final boolean fresh = (null == t1.getTypes());
349:
350: if (fresh && !runtime.test("optionVariant")) {
351: ast.add(t1, ast.toVariant("Node", false));
352: }
353:
354: if (DEBUG) {
355: runtime.console().p(name).p(" : ");
356: ast.print(t2, runtime.console(), false, true, null);
357: runtime.console().pln();
358: }
359:
360: if (!fresh) {
361: Type result = ast.combine(t1, t2, flatten, strict);
362: if (result.isError()) {
363: runtime.error("unable to consistently type tuple '"
364: + name + "'", sequence);
365: runtime.errConsole().loc(sequence).p(
366: ": error: 1st type is '");
367: ast.print(t1, runtime.errConsole(), false, true, null);
368: runtime.errConsole().pln("'");
369: runtime.errConsole().loc(sequence).p(
370: ": error: 2nd type is '");
371: ast.print(t2, runtime.errConsole(), false, true, null);
372: runtime.errConsole().pln("'").flush();
373:
374: } else {
375: if (DEBUG) {
376: runtime.console().p(" -> ");
377: ast.print(result, runtime.console(), false, true,
378: null);
379: runtime.console().pln();
380: }
381: t1.setTypes(result.toTuple().getTypes());
382: }
383:
384: } else if (flatten) {
385: Type result = ast.flatten(t2, strict);
386: if (result.isError()) {
387: runtime.error("unable to flatten tuple '" + name + "'",
388: sequence);
389: runtime.errConsole().loc(sequence).p(
390: ": error: type is '");
391: ast.print(t2, runtime.errConsole(), false, true, null);
392: runtime.errConsole().pln("'").flush();
393:
394: } else {
395: t1.setTypes(result.toTuple().getTypes());
396: }
397:
398: } else {
399: t1.setTypes(types);
400: }
401: }
402:
403: }
|