001: /*
002: * xtc - The eXTensible Compiler
003: * Copyright (C) 2007 New York University
004: *
005: * This library is free software; you can redistribute it and/or
006: * modify it under the terms of the GNU Lesser General Public License
007: * version 2.1 as published by the Free Software Foundation.
008: *
009: * This library 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 GNU
012: * Lesser General Public License for more details.
013: *
014: * You should have received a copy of the GNU Lesser General Public
015: * License along with this library; if not, write to the Free Software
016: * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
017: * USA.
018: */
019: package xtc.typical;
020:
021: import java.util.ArrayList;
022: import java.util.Hashtable;
023: import xtc.tree.Node;
024:
025: import xtc.util.Runtime;
026: import xtc.util.SymbolTable;
027: import xtc.util.Pair;
028: import xtc.util.Function;
029:
030: /**
031: * The base class of all Typical-generated type checkers.
032: *
033: * @author Laune Harris, Anh Le
034: * @version $Revision: 1.145 $
035: */
036: public abstract class Analyzer {
037:
038: /** The runtime. */
039: protected final Runtime runtime;
040:
041: /** The symbol table. */
042: protected final SymbolTable gamma;
043:
044: /** The property to check if enter a scope. */
045: protected final String ENTERSCOPE = "enterScope";
046:
047: /** The property of check if exit a scope. */
048: protected final String EXITSCOPE = "exitScope";
049:
050: /**
051: * The property to store the times of not entering a new scope because
052: * the new scope is also the current scope.
053: */
054: protected final String MAGICNUMBER = "magicNumber";
055:
056: /** The hash table */
057: protected Hashtable<Object, Object> hashTable;
058:
059: /** The analyzer. */
060: protected Function.F1<?, Node> analyzer;
061:
062: /** The tree root. */
063: protected Node root;
064:
065: /** The visited node path.*/
066: protected final ArrayList<Node> matching_nodes = new ArrayList<Node>();
067:
068: /** The list of names of the nodes that trigger scope changes. */
069: protected final ArrayList<String> processScopeNodes = new ArrayList<String>();
070:
071: /** Interface for pattern matches. */
072: public static interface Match<T> extends Function.F0<T> { /*empty*/
073: }
074:
075: /** Interface for ancestor Matches. */
076: public static interface NodeMatch extends
077: Function.F1<Boolean, Node> { /* empty */
078: }
079:
080: /** Interface for require expressions. */
081: public static interface Require<T> extends Function.F0<T> { /*empty*/
082: }
083:
084: /** Interface for let expressions. */
085: public static interface Let<T> extends Function.F0<T> { /*empty*/
086: }
087:
088: /** Interface for guard expressions. */
089: public static interface Guard<T> extends Function.F0<T> { /*empty*/
090: }
091:
092: /** Get the names of the nodes that trigger scope changes. */
093: protected abstract void getScopeNodes();
094:
095: /** The Typical load function to load predefined values and data types. */
096: protected final Function.F3<Void, String, String, Object> load = new Function.F3<Void, String, String, Object>() {
097: public Void apply(String s, String ns, Object t) {
098: if (null == s || null == ns)
099: return null;
100: gamma.current().define(SymbolTable.toNameSpace(s, ns), t);
101: return null;
102: }
103: };
104:
105: /** The ancestor function.*/
106: protected final Function.F1<Node, NodeMatch> ancestor = new Function.F1<Node, NodeMatch>() {
107: public final Node apply(NodeMatch pattern) {
108: for (int i = matching_nodes.size() - 1; i >= 0; i--) {
109: final Node node = matching_nodes.get(i);
110: if (pattern.apply(node))
111: return node;
112: }
113: return null;
114: }
115: };
116:
117: /** The parent function.*/
118: protected final Function.F1<Node, NodeMatch> parent = new Function.F1<Node, NodeMatch>() {
119: public final Node apply(NodeMatch pattern) {
120: final Node node = matching_nodes
121: .get(matching_nodes.size() - 1);
122: if (pattern.equals(node))
123: return node;
124: return null;
125: }
126: };
127:
128: /** A Typical function to lookup a node, without error messages. */
129: protected final Function.F2<Object, Node, Function.F1<?, Node>> lookup2 = new Function.F2<Object, Node, Function.F1<?, Node>>() {
130: public final Object apply(Node n,
131: Function.F1<?, Node> getNameSpace) {
132: Tuple.T3<Name<?>, String, String> tup = cast(getNameSpace
133: .apply(n));
134: assert (null != tup) : "Unable to map namespace for node "
135: + (null == n ? "Null" : n.getName());
136: checkEnterScope(n);
137:
138: final Object res = gamma.lookup(tup.get1().mangle(
139: tup.get2()));
140: if (null == res)
141: showMessage("error", "Undefined: "
142: + tup.get1().mangle(tup.get2()), n);
143: checkExitScope(n);
144: return res;
145: }
146: };
147:
148: /** A Typical function to lookup a node, with an error message. */
149: protected final Function.F4<Object, Node, String, String, Function.F1<?, Node>> lookup4 = new Function.F4<Object, Node, String, String, Function.F1<?, Node>>() {
150: public final Object apply(Node n, String tag, String err,
151: Function.F1<?, Node> getNameSpace) {
152: Tuple.T3<Name<?>, String, String> tup = cast(getNameSpace
153: .apply(n));
154: assert (null != tup) : "Unable to map namespace for node "
155: + (null == n ? "Null" : n.getName());
156: checkEnterScope(n);
157: final Object res = gamma.lookup(tup.get1().mangle(
158: tup.get2()));
159: if (null == res)
160: showMessage(tag, err, n);
161: checkExitScope(n);
162: return res;
163: }
164: };
165:
166: /** A Typical function to lookup a node locally, without error messages. */
167: protected final Function.F2<Object, Node, Function.F1<?, Node>> lookupLocally2 = new Function.F2<Object, Node, Function.F1<?, Node>>() {
168: public final Object apply(Node n,
169: Function.F1<?, Node> getNameSpace) {
170: Tuple.T3<Name<?>, String, String> tup = cast(getNameSpace
171: .apply(n));
172: assert (null != tup) : "Unable to map namespace for node "
173: + (null == n ? "Null" : n.getName());
174:
175: checkEnterScope(n);
176: final Object res = gamma.lookup(tup.get1().mangle(
177: tup.get2()));
178: if (null == res)
179: showMessage("error", "Undefined in the current scope: "
180: + tup.get1().mangle(tup.get2()), n);
181: checkExitScope(n);
182: return res;
183: }
184: };
185:
186: /** A Typical function to lookup a node locally, with an error message. */
187: protected final Function.F4<Object, Node, String, String, Function.F1<?, Node>> lookupLocally4 = new Function.F4<Object, Node, String, String, Function.F1<?, Node>>() {
188: public final Object apply(Node n, String tag, String err,
189: Function.F1<?, Node> getNameSpace) {
190: Tuple.T3<Name<?>, String, String> tup = cast(getNameSpace
191: .apply(n));
192: assert (null != tup) : "Unable to map namespace for node "
193: + (null == n ? "Null" : n.getName());
194:
195: checkEnterScope(n);
196: final Object res = gamma.lookup(tup.get1().mangle(
197: tup.get2()));
198: if (null == res)
199: showMessage(tag, err, n);
200: checkExitScope(n);
201: return res;
202: }
203: };
204:
205: /** A Typical function to define a node, without error messages. */
206: protected final Function.F3<Void, Node, Object, Function.F1<?, Node>> define3 = new Function.F3<Void, Node, Object, Function.F1<?, Node>>() {
207: public final Void apply(Node n, Object t,
208: Function.F1<?, Node> getNameSpace) {
209: Tuple.T3<Name<?>, String, String> tup = cast(getNameSpace
210: .apply(n));
211:
212: assert (null != tup) : "define : no namespace for "
213: + (null == n ? "Null" : n.getName());
214: checkEnterScope(n);
215: gamma.current().define(tup.get1().mangle(tup.get2()), t);
216: checkExitScope(n);
217: return null;
218: }
219: };
220:
221: /** A Typical function to define a node, with an error message. */
222: protected final Function.F5<Void, Node, Object, String, String, Function.F1<?, Node>> define5 = new Function.F5<Void, Node, Object, String, String, Function.F1<?, Node>>() {
223: public final Void apply(Node n, Object t, String tag,
224: String err, Function.F1<?, Node> getNameSpace) {
225: Tuple.T3<Name<?>, String, String> tup = cast(getNameSpace
226: .apply(n));
227:
228: assert (null != tup) : "define : no namespace for "
229: + (null == n ? "Null" : n.getName());
230:
231: checkEnterScope(n);
232: final String newName = tup.get1().mangle(tup.get2());
233: if (gamma.current().isDefined(newName)) {
234: showMessage(tag, err, n);
235: }
236: gamma.current().define(newName, t);
237: checkExitScope(n);
238: return null;
239: }
240: };
241:
242: /** A Typical function to redefine a node. */
243: protected final Function.F3<Void, Node, Object, Function.F1<?, Node>> redefine = new Function.F3<Void, Node, Object, Function.F1<?, Node>>() {
244: public final Void apply(Node n, Object t,
245: Function.F1<?, Node> getNameSpace) {
246: Tuple.T3<Name<?>, String, String> tup = cast(getNameSpace
247: .apply(n));
248:
249: assert (null != tup) : "redefine : no namespace for "
250: + (null == n ? "Null" : n.getName());
251:
252: checkEnterScope(n);
253: String newName = tup.get1().mangle(tup.get2());
254: gamma.current().define(newName, t);
255: checkExitScope(n);
256: return null;
257: }
258: };
259:
260: /** A typical function for checking if a node has been defined */
261: protected final Function.F2<Boolean, Node, Function.F1<?, Node>> isDefined = new Function.F2<Boolean, Node, Function.F1<?, Node>>() {
262: public final Boolean apply(Node n,
263: Function.F1<?, Node> getNameSpace) {
264: Tuple.T3<Name<?>, String, String> tup = cast(getNameSpace
265: .apply(n));
266:
267: assert (null != tup) : "is_define : no namespace for "
268: + (null == n ? "Null" : n.getName());
269: checkEnterScope(n);
270: final boolean res = gamma.isDefined(tup.get1().mangle(
271: tup.get2()));
272: checkExitScope(n);
273: return res;
274: }
275: };
276:
277: /** A typical function for checking if a node has been locally defined */
278: protected final Function.F2<Boolean, Node, Function.F1<?, Node>> isDefinedLocally = new Function.F2<Boolean, Node, Function.F1<?, Node>>() {
279: public final Boolean apply(Node n,
280: Function.F1<?, Node> getNameSpace) {
281: Tuple.T3<Name<?>, String, String> tup = cast(getNameSpace
282: .apply(n));
283:
284: assert (null != tup) : "is_define_locally : no namespace for "
285: + (null == n ? "Null" : n.getName());
286:
287: checkEnterScope(n);
288: boolean res = gamma.current().isDefinedLocally(
289: tup.get1().mangle(tup.get2()));
290: checkExitScope(n);
291: return res;
292: }
293: };
294:
295: /** The Typical function to print a symbol. */
296: protected final Function.F1<Boolean, String> show_symbols = new Function.F1<Boolean, String>() {
297: public Boolean apply(String s) {
298: if ("local".equals(s)) {
299: gamma.current().dump(runtime.console());
300: runtime.console().flush();
301: } else if ("all".equals(s)) {
302: gamma.root().dump(runtime.console());
303: runtime.console().flush();
304: } else {
305: runtime
306: .error("local or all required to use show_symbol function");
307: }
308: return Boolean.TRUE;
309: }
310: };
311:
312: /** The Typical function to get a new name. */
313: protected final Function.F1<String, String> freshName = new Function.F1<String, String>() {
314: public String apply(String s) {
315: return gamma.freshName(s);
316: }
317: };
318:
319: /**
320: * The Typical function to check if a value if bottom.
321: * Return <code>true</code> if not bottom, otherwise bottom
322: * (It will be removed once guard is done)
323: */
324: protected final Function.F1<Boolean, Object> notBottom = new Function.F1<Boolean, Object>() {
325: public Boolean apply(Object t) {
326: return null == t ? null : Boolean.TRUE;
327: }
328: };
329:
330: /**
331: * Create a new TypeChecker base.
332: *
333: * @param runt The runtime.
334: */
335: public Analyzer(Runtime runt) {
336: runtime = runt;
337: gamma = new SymbolTable();
338: hashTable = new Hashtable<Object, Object>();
339: getScopeNodes();
340: }
341:
342: /**
343: * Check a node and enter a scope.
344: *
345: * @param n The node to check.
346: */
347: protected void checkEnterScope(Node n) {
348: if (null != n && n.hasProperty(ENTERSCOPE)) {
349: final String scopeName = (String) n.getProperty(ENTERSCOPE);
350: if (!scopeName.equals(gamma.current().getName())) {
351: gamma.enter(scopeName);
352: } else {
353: // magicNumber is the number of times not entering a new scope
354: // at this node because the new scope is the current scope
355: if (!n.hasProperty(MAGICNUMBER)) {
356: n.setProperty(MAGICNUMBER, 1);
357: } else {
358: final Integer num = (Integer) n
359: .getProperty(MAGICNUMBER);
360: n.setProperty(MAGICNUMBER, num + 1);
361: }
362: }
363: }
364:
365: }
366:
367: /**
368: * Check a node and exit scope.
369: *
370: * @param n The node to check.
371: */
372: protected void checkExitScope(Node n) {
373: if (null != n && n.hasProperty(EXITSCOPE)) {
374: if (!n.hasProperty(MAGICNUMBER))
375: gamma.exit();
376: else {
377: final Integer num = (Integer) n
378: .getProperty(MAGICNUMBER);
379: if (1 == num)
380: n.removeProperty(MAGICNUMBER);
381: else
382: n.setProperty(MAGICNUMBER, num - 1);
383: }
384: }
385: if (null != n && n.hasProperty("deleteScope")) {
386: gamma.delete((String) n.getProperty("deleteScope"));
387: }
388: }
389:
390: /**
391: * Print a error message.
392: *
393: * @param s The msg.
394: * @param n The location.
395: * @return null
396: */
397: protected Object error(String s, Node n) {
398: if (null == n) {
399: n = matching_nodes.get(matching_nodes.size() - 1);
400: }
401: runtime.error(s, n);
402: return null;
403: }
404:
405: /**
406: * Print a warning message.
407: *
408: * @param s The msg.
409: * @param n The location.
410: * @return null
411: */
412: protected Object warning(String s, Node n) {
413: if (null == n) {
414: n = matching_nodes.get(matching_nodes.size() - 1);
415: }
416: runtime.warning(s, n);
417: return null;
418: }
419:
420: /**
421: * Print a error message.
422: *
423: * @param tag The message class.
424: * @param msg The message.
425: * @param o The node generating the message.
426: */
427: protected void showMessage(String tag, String msg, Object o) {
428: Node n = (Node) o;
429: if (null == n) {
430: if ("error".equals(tag)) {
431: if (matching_nodes.size() - 1 < 0) {
432: runtime.error(msg);
433: } else {
434: Node nod = matching_nodes
435: .get(matching_nodes.size() - 1);
436: runtime.error(msg, nod);
437: }
438: } else {
439: if (matching_nodes.size() - 1 < 0) {
440: runtime.warning(msg);
441: } else {
442: Node nod = matching_nodes
443: .get(matching_nodes.size() - 1);
444: runtime.warning(msg, nod);
445: }
446: }
447: } else {
448: if ("error".equals(tag)) {
449: runtime.error(msg, n);
450: } else {
451: runtime.warning(msg, n);
452: }
453: }
454: }
455:
456: /**
457: * Process scope.
458: *
459: * @param n The node to process.
460: * @param getScope The generated getScope function.
461: */
462: protected void processScope(Node n, Function.F1<?, Node> getScope) {
463: // the function getScope(Node n) will be created
464: // after visiting the scope declaration
465: Scope scop = cast(getScope.apply(n));
466: if (null == scop) {
467: throw new AssertionError("unable to get scope for : "
468: + n.getName());
469: }
470: // get the scope name
471: ScopeKind<?> scopename = scop.getTuple().get1();
472: String str;
473: if (scopename.isNamed()) {
474: // Cast to object first to avoid inconvertible types error with Java 5.
475: Name<?> strname = ((ScopeKind.Named) (Object) scopename)
476: .getTuple().get1();
477: if (strname.isSimpleName()) {
478: // Cast to object first to avoid inconvertible types error with Java 5.
479: str = ((Name.SimpleName) (Object) strname).getTuple()
480: .get1();
481: } else {
482: str = "QualifiedName";
483: }
484: } else if (scopename.isAnonymous()) {
485: // Cast to object first to avoid inconvertible types error with Java 5.
486: str = gamma
487: .freshName(((ScopeKind.Anonymous) (Object) scopename)
488: .getTuple().get1());
489: } else {
490: // Cast to object first to avoid inconvertible types error with Java 5.
491: str = gamma
492: .freshName(((ScopeKind.Temporary) (Object) scopename)
493: .getTuple().get1());
494: }
495:
496: Pair<Node> nodes = scop.getTuple().get2();
497:
498: ArrayList<Node> nodeList = (ArrayList<Node>) nodes.list();
499: int index;
500: int prob = -1;
501: // check and remove set scope property in those nodes
502: for (index = 0; index < nodeList.size(); index++) {
503: Node node = nodeList.get(index);
504: if (node == null) {
505: continue;
506: }
507: if (!node.hasProperty(ENTERSCOPE)) {
508: node.setProperty(ENTERSCOPE, str);
509: node.setProperty(EXITSCOPE, true);
510: prob = index;
511: }
512: }
513: if ((prob != -1) && (scopename.isTemporary())) {
514: Node node = nodeList.get(prob);
515: node.setProperty("deleteScope", str);
516: }
517: }
518:
519: /**
520: * Run this typechecker on the tree rooted at n.
521: *
522: * @param n The tree root.
523: * @return The Symbol table of the ast.
524: */
525: public SymbolTable run(Node n) {
526: if (null == analyzer) {
527: runtime.error("Analyzer is null");
528: runtime.exit();
529: }
530:
531: if (null == n) {
532: runtime.error("Tree root is null");
533: runtime.exit();
534: } else {
535: root = n;
536: }
537:
538: matching_nodes.add(n);
539: analyzer.apply(n);
540:
541: return gamma;
542: }
543:
544: /**
545: * Returns the (possibly annotated and modified) AST root.
546: *
547: * @return The root of the ast.
548: */
549: public Node getASTRoot() {
550: return root;
551: }
552:
553: /**
554: * Utility function to print a nicely formatted ast for debugging.
555: *
556: * @param n The ast root.
557: */
558: protected void printAST(Node n) {
559: runtime.console().pln().format(n).pln().flush();
560: }
561:
562: /**
563: * Convert the specified object to a string.
564: *
565: * @param o The object.
566: * @return The corresponding string.
567: */
568: public static final String toString(Object o) {
569: return null == o ? "?" : o.toString();
570: }
571:
572: /**
573: * Test for equality between two objects.
574: *
575: * @param o1 The first object.
576: * @param o2 The second object.
577: * @return <code>true</code> if both are equal, false otherwise.
578: */
579: public static Boolean equal(Object o1, Object o2) {
580: return null == o1 ? null == o2 : o1.equals(o2);
581: }
582:
583: /**
584: * Test for equality between two objects.
585: *
586: * @param o1 The first object.
587: * @param o2 The second object.
588: * @return <code>true</code> if the o1 and o2 not equal, false otherwise.
589: */
590: protected static Boolean not_equal(Object o1, Object o2) {
591: return null == o1 ? null != o2 : (!o1.equals(o2));
592: }
593:
594: /**
595: * Ignore the specified value.
596: *
597: * @param o The value to ignore.
598: */
599: protected static final void discard(Object o) {
600: // Nothing to do.
601: }
602:
603: /**
604: * Cast an object to type T.
605: *
606: * @param arg The object to cast.
607: * @return The object cast to T
608: */
609: @SuppressWarnings("unchecked")
610: public static final <T> T cast(Object arg) {
611: return (T) arg;
612: }
613:
614: }
|