001: /*
002: * xtc - The eXTensible Compiler
003: * Copyright (C) 2007 New York University
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:
020: package xtc.lang.p2;
021:
022: import java.util.ArrayList;
023: import java.util.HashMap;
024: import java.util.HashSet;
025: import java.util.Iterator;
026: import java.util.List;
027: import java.util.Map;
028: import java.util.Set;
029:
030: import xtc.tree.GNode;
031: import xtc.tree.Node;
032: import xtc.tree.Visitor;
033:
034: import xtc.type.ArrayT;
035: import xtc.type.BooleanT;
036: import xtc.type.ErrorT;
037: import xtc.type.FunctionT;
038: import xtc.type.InternalT;
039: import xtc.type.NumberT;
040: import xtc.type.NullReference;
041: import xtc.type.Parameter;
042: import xtc.type.TupleT;
043: import xtc.type.Type;
044: import xtc.type.VoidT;
045: import xtc.type.Wildcard;
046:
047: import xtc.util.SymbolTable;
048: import xtc.util.Runtime;
049:
050: /**
051: * A visitor to type check Overlog programs.
052: *
053: * @author Robert Soule
054: * @version $Revision: 1.13 $
055: */
056: public final class TypeAnalyzer extends Visitor {
057:
058: /** The runtime. */
059: protected final Runtime runtime;
060:
061: /** The symbol table. */
062: protected SymbolTable table;
063:
064: /** A static counter for temporary variable names */
065: private static int tempNameCount = 0;
066:
067: /** A map to keep updated type information */
068: private Map<Type, Type> updateMap;
069:
070: /** A set to ensure rule identifier names are unique */
071: private Set<String> ruleIdentifiers;
072:
073: /**
074: * Create a new Overlog analyzer.
075: *
076: * @param runtime The runtime.
077: */
078: public TypeAnalyzer(Runtime runtime) {
079: this .runtime = runtime;
080: updateMap = new HashMap<Type, Type>();
081: ruleIdentifiers = new HashSet<String>();
082: }
083:
084: /**
085: * Analyze the specified translation unit.
086: *
087: * @param unit The translation unit.
088: * @return The corresponding symbol table.
089: */
090: public Node analyze(Node unit) {
091: return analyze(unit, new SymbolTable());
092: }
093:
094: /**
095: * Process the specified translation unit.
096: *
097: * @param unit The translation unit.
098: * @param table The symbol table.
099: * @return root of the AST
100: */
101: public Node analyze(Node unit, SymbolTable table) {
102: this .table = table;
103: dispatch(unit);
104: updateSymbolTable();
105: return unit;
106: }
107:
108: // =========================================================================
109:
110: /**
111: * Create a new set whose only member is t
112: *
113: * @param t the sole member of the new set.
114: */
115: private void makeSet(Type t) {
116: // In this representation, a set's representative member
117: // may be espressed as a mapping from that type to null;
118: updateMap.put(t, null);
119: }
120:
121: /**
122: * Unite the dynamic sets that contain x and y into
123: * a new set that is the union of these two sets.
124: * If one of the types is a non-variable node, then
125: * then union makes the non variable node the representative
126: * of the merged classes.
127: *
128: * @param x the first type
129: * @param y the second type
130: */
131: private void union(final Type x, final Type y) {
132: if ((x == null) || (y == null)) {
133: return;
134: } else if (isBasicType(x) && !isBasicType(y)) {
135: /* x represents a non-variable */
136: updateMap.put(y, x);
137: } else if (!isBasicType(x) && isBasicType(y)) {
138: /* y represents a non-variable */
139: updateMap.put(x, y);
140: } else {
141: // In the semantics of this fake disjoint sets algorithm,
142: // joining two sets means creating a new temp variable that
143: // they both point to.
144: Type representative = new Parameter(newTempTypeName());
145: updateMap.put(x, representative);
146: updateMap.put(y, representative);
147: }
148: }
149:
150: /**
151: * Return the representative element of the equivalence class
152: * currently containing element x.
153: *
154: * @param t the type who's representative you are looking for
155: * @return the representative of that class. If the type is
156: * not currently found in the map, then t is returned.
157: */
158: private Type find(final Type t) {
159: final Type u = updateMap.get(t);
160: if (u == null) {
161: return t;
162: } else {
163: return find(u);
164: }
165: }
166:
167: // =========================================================================
168:
169: /**
170: * Updates the nested scopes in the symbol table
171: * with the correct types after type unification.
172: */
173: private void updateSymbolTable() {
174: updateScope(table.current());
175: Iterator<String> iter = table.current().nested();
176: for (; iter.hasNext();) {
177: String symbol = iter.next();
178: updateScope(table.current().getNested(symbol));
179: }
180: }
181:
182: /**
183: * Updates all symbols defined in a single scopes
184: * in the symbol table with the correct types after
185: * type unification.
186: *
187: * @param scope A nested scope from the symbol table
188: */
189: private void updateScope(SymbolTable.Scope scope) {
190: Iterator<String> iter = scope.symbols();
191: for (; iter.hasNext();) {
192: String symbol = iter.next();
193: Type t = (Type) scope.lookup(symbol);
194: Type u = find(t);
195: if (u.isTuple()) {
196: // dispatch to the terms
197: List<Type> termList = new ArrayList<Type>();
198: List<Type> tTypeList = t.toTuple().getTypes();
199: for (Type s : tTypeList) {
200: termList.add(find(s));
201: }
202: scope.define(symbol, new TupleT(u.getName(), termList));
203: } else if (u.isFunction()) {
204: List<Type> updatedArgList = new ArrayList<Type>();
205: List<Type> params = u.toFunction().getParameters();
206: for (Type s : params) {
207: updatedArgList.add(find(s));
208: }
209: Type updatedFunctionT = new FunctionT(find(u
210: .toFunction().getResult()), updatedArgList,
211: false);
212: scope.define(symbol, updatedFunctionT);
213: } else {
214: scope.define(symbol, u);
215: }
216: }
217: }
218:
219: /**
220: * Determines if a type is one of the basic types
221: *
222: * @param t the type to be checked
223: * @return true if t is one of the basic types
224: */
225: private boolean isBasicType(final Type t) {
226: switch (t.tag()) {
227: case BOOLEAN:
228: case INTEGER:
229: case FLOAT:
230: case VOID:
231: case WILDCARD:
232: return true;
233: case INTERNAL:
234: return "location".equals(t.toInternal().getName());
235: default:
236: return false;
237: }
238: }
239:
240: /**
241: * Determines if two types are the same basic type
242: *
243: * @param s the first type
244: * @param t the second type
245: * @return true if the two are the same basic type
246: */
247: public boolean areSameBasicType(final Type s, final Type t) {
248: if (Type.Tag.WILDCARD == t.tag()) {
249: return isBasicType(s);
250: }
251: switch (s.tag()) {
252: case BOOLEAN:
253: return t.isBoolean();
254: case INTEGER:
255: return t.isInteger();
256: case FLOAT:
257: return t.isFloat();
258: case VOID:
259: return t.isVoid();
260: case WILDCARD:
261: return isBasicType(t);
262: case INTERNAL: {
263: if (!t.isInternal()) {
264: return false;
265: } else if ("location".equals(s.toInternal().getName())
266: && "location".equals(t.toInternal().getName())) {
267: return true;
268: } else {
269: return false;
270: }
271: }
272: default:
273: return false;
274: }
275: }
276:
277: /**
278: * Return true if a type is being used as a type
279: * variable.
280: *
281: * @param s The type in question
282: */
283: private boolean isVariable(final Type s) {
284: return s.isParameter();
285: }
286:
287: /**
288: * Creates a new temporary variable name by incrementing
289: * a static counter.
290: *
291: * @return the new temp type name
292: */
293: private String newTempTypeName() {
294: String tmp = "tmp" + tempNameCount;
295: tempNameCount++;
296: return tmp;
297: }
298:
299: /**
300: * Determines if two expressions can be made identical
301: *
302: * @param m The first type
303: * @param m The second type
304: * @return true if m and n unify, false otherwise
305: */
306: private boolean unify(final Type m, final Type n) {
307: final Type s = find(m);
308: final Type t = find(n);
309: if ((s == null) || (t == null)) {
310: return false;
311: } else if (s.equals(t)) {
312: /* s equals t */
313: return true;
314: } else if (areSameBasicType(s, t)) {
315: /* s and t are the same basic type */
316: return true;
317: } else if (s.isTuple() && t.isTuple()) {
318: // make sure they have the same number of children
319: if (s.toTuple().getTypes().size() != t.toTuple().getTypes()
320: .size()) {
321: return false;
322: }
323: final List<Type> sTypeList = s.toTuple().getTypes();
324: final List<Type> tTypeList = t.toTuple().getTypes();
325: int i = 0;
326: for (Type lhs : sTypeList) {
327: Type rhs = tTypeList.get(i);
328: boolean unified = unify(lhs, rhs);
329: if (!unified) {
330: if (!((find(lhs).isFloat() && find(rhs).isInteger()) || (find(
331: lhs).isInteger() && find(rhs).isFloat()))) {
332: return false;
333: }
334: }
335: i++;
336: }
337: return true;
338: } else if (s.isFunction() && t.isFunction()) {
339: if (((FunctionT) s).getParameters().size() != ((FunctionT) t)
340: .getParameters().size()) {
341: return false;
342: }
343: final List<Type> sArgs = s.toFunction().getParameters();
344: final List<Type> tArgs = t.toFunction().getParameters();
345: int i = 0;
346: for (Type lhs : sArgs) {
347: Type rhs = tArgs.get(i);
348: boolean unified = unify(lhs, rhs);
349: if (!unified) {
350: if (!((find(lhs).isFloat() && find(rhs).isInteger()) || (find(
351: lhs).isInteger() && find(rhs).isFloat()))) {
352: return false;
353: }
354: }
355: i++;
356: }
357: return true;
358: } else if (isVariable(s) || isVariable(t)) {
359: /* s or t represents a variable */
360: union(s, t);
361: return true;
362: } else {
363: return false;
364: }
365: }
366:
367: // =========================================================================
368:
369: /**
370: * Visit all nodes in the AST.
371: */
372: public void visit(final GNode n) {
373: for (Object o : n) {
374: if (o instanceof Node) {
375: dispatch((Node) o);
376: } else if (Node.isList(o)) {
377: iterate(Node.toList(o));
378: }
379: }
380: }
381:
382: public void visitRule(final GNode n) {
383: // Rule clauses may start with an optional "RuleIdentifier".
384: // Currently, RuleIdentifiers serve no purpose other than
385: // to provide some clarity to the programmer. We therefore
386: // want to check the first child, and see if it is a type
387: // that we can ignore.
388: String ruleName = "unknown";
389: if ("RuleIdentifier".equals(n.getNode(0).getName())) {
390: ruleName = n.getNode(0).getString(0);
391: if (ruleIdentifiers.contains(ruleName)) {
392: runtime.error("Rule " + ruleName
393: + " previously defined.", n);
394: return;
395: } else {
396: ruleIdentifiers.add(ruleName);
397: }
398: table.enter(ruleName);
399: } else {
400: table.enter(table.freshName());
401: }
402: // dispath to the event
403: dispatch(n.getNode(1));
404: // dispatch to the "actions"
405: for (Node child : n.<Node> getList(2)) {
406: dispatch(child);
407: }
408: table.exit();
409: updateSymbolTable();
410: }
411:
412: public Type visitTuple(final GNode n) {
413: // first we get the tuple's name
414: final String name = n.getNode(0).getString(0);
415: // dispatch to the terms
416: List<Type> termList = new ArrayList<Type>();
417: for (Node term : n.<Node> getList(1)) {
418: final Type t = (Type) dispatch(term);
419: termList.add(t);
420: }
421: Type tuple = new TupleT(name, termList);
422: final Type definedType = (Type) table.root().lookup(name);
423: // Check to see if the tuple has been defined before
424: if (null == definedType) {
425: // If it hasn't, define it now
426: table.root().define(name, tuple);
427: } else {
428: final boolean unified = unify(tuple, definedType);
429: if (!unified) {
430: if (name.equals("periodic")) {
431: runtime
432: .warning(
433: "periodic tuple previously defined with different type.",
434: n);
435: } else {
436: runtime.error("Tuple " + name
437: + " previously defined "
438: + "with different type", n);
439: return ErrorT.TYPE;
440: }
441: }
442: }
443: return tuple;
444: }
445:
446: public Type visitExpression(final GNode n) {
447: final Type lhs = (Type) dispatch(n.getNode(0));
448: final Type rhs = (Type) dispatch(n.getNode(2));
449: // if these are variables, unify will make a union
450: final boolean unified = unify(lhs, rhs);
451: if (unified) {
452: union(lhs, rhs);
453: return find(lhs);
454: } else {
455: // Maybe we can coerce
456: if ((find(lhs).isFloat() && find(rhs).isInteger())
457: || (find(lhs).isInteger() && find(rhs).isFloat())) {
458: return NumberT.FLOAT;
459: } else {
460: runtime.error(
461: "Assignment Expression error. Cannot assign "
462: + find(rhs) + " to " + find(lhs), n);
463: return ErrorT.TYPE;
464: }
465: }
466: }
467:
468: public Type visitLogicalOrExpression(final GNode n) {
469: final Type lhs = (Type) dispatch(n.getNode(0));
470: final Type rhs = (Type) dispatch(n.getNode(2));
471: final boolean unified = unify(lhs, rhs);
472: if (unified) {
473: return new BooleanT();
474: } else {
475: runtime.error("Cannot compare " + find(lhs) + " and "
476: + find(rhs) + " in a logical or expression", n);
477: return ErrorT.TYPE;
478: }
479: }
480:
481: public Type visitLogicalAndExpression(final GNode n) {
482: final Type lhs = (Type) dispatch(n.getNode(0));
483: final Type rhs = (Type) dispatch(n.getNode(2));
484: final boolean unified = unify(lhs, rhs);
485: if (unified) {
486: return new BooleanT();
487: } else {
488: runtime.error("Cannot compare " + find(lhs) + " and "
489: + find(rhs) + " in a logical and expression", n);
490: return ErrorT.TYPE;
491: }
492: }
493:
494: public Type visitEqualityExpression(final GNode n) {
495: final Type lhs = (Type) dispatch(n.getNode(0));
496: final Type rhs = (Type) dispatch(n.getNode(2));
497: final boolean unified = unify(lhs, rhs);
498: if (unified) {
499: return new BooleanT();
500: } else {
501: // Maybe we can coerce
502: if ((find(lhs).isFloat() && find(rhs).isInteger())
503: || (find(lhs).isInteger() && find(rhs).isFloat())) {
504: return new BooleanT();
505: } else {
506: runtime.error("Cannot compare " + find(lhs) + " and "
507: + find(rhs) + " in an equality expression", n);
508: return ErrorT.TYPE;
509: }
510: }
511: }
512:
513: public Type visitShiftExpression(final GNode n) {
514: final Type lhs = (Type) dispatch(n.getNode(0));
515: final Type rhs = (Type) dispatch(n.getNode(2));
516: if (lhs.isInteger() && rhs.isInteger()) {
517: return NumberT.S_INT;
518: } else if (lhs.isFloat() && rhs.isInteger()) {
519: return NumberT.FLOAT;
520: } else if (lhs.isInteger() && rhs.isFloat()) {
521: return NumberT.FLOAT;
522: } else if (lhs.isFloat() && rhs.isFloat()) {
523: return NumberT.FLOAT;
524: } else {
525: if (unify(lhs, rhs)) {
526: return find(lhs);
527: } else {
528: runtime.error("Cannot shift " + find(lhs) + " and "
529: + find(rhs), n);
530: return ErrorT.TYPE;
531: }
532: }
533: }
534:
535: public Type visitAdditiveExpression(final GNode n) {
536: final Type lhs = (Type) dispatch(n.getNode(0));
537: final Type rhs = (Type) dispatch(n.getNode(2));
538: if (lhs.isInteger() && rhs.isInteger()) {
539: return NumberT.S_INT;
540: } else if (lhs.isFloat() && rhs.isInteger()) {
541: return NumberT.FLOAT;
542: } else if (lhs.isInteger() && rhs.isFloat()) {
543: return NumberT.FLOAT;
544: } else if (lhs.isFloat() && rhs.isFloat()) {
545: return NumberT.FLOAT;
546: } else {
547: if (unify(lhs, rhs)) {
548: return find(lhs);
549: } else {
550: runtime.error("Cannot add " + find(lhs) + " and "
551: + find(rhs), n);
552: return ErrorT.TYPE;
553: }
554: }
555: }
556:
557: public Type visitMultiplicativeExpression(final GNode n) {
558: final Type lhs = (Type) dispatch(n.getNode(0));
559: final Type rhs = (Type) dispatch(n.getNode(2));
560: if (lhs.isInteger() && rhs.isInteger()) {
561: return NumberT.S_INT;
562: } else if (lhs.isFloat() && rhs.isInteger()) {
563: return NumberT.FLOAT;
564: } else if (lhs.isInteger() && rhs.isFloat()) {
565: return NumberT.FLOAT;
566: } else if (lhs.isFloat() && rhs.isFloat()) {
567: return NumberT.FLOAT;
568: } else {
569: if (unify(lhs, rhs)) {
570: return find(lhs);
571: } else {
572: runtime.error("Cannot multiply " + find(lhs) + " and "
573: + find(rhs), n);
574: return ErrorT.TYPE;
575: }
576: }
577: }
578:
579: public Type visitLogicalNegationExpression(final GNode n) {
580: dispatch(n.getNode(0));
581: // @fixme what are the rules here? is it like C and we allow ! int
582: // or only booleans?
583: return new BooleanT();
584: }
585:
586: public Type visitInclusiveExpression(final GNode n) {
587: final Type lhs = (Type) dispatch(n.getNode(0));
588: final Type rhs = (Type) dispatch(n.getNode(2));
589: final boolean unified = unify(lhs, rhs);
590: if (unified) {
591: Type type = new BooleanT();
592: makeSet(type);
593: return type;
594: } else {
595: // Maybe we can coerce
596: if ((find(lhs).isFloat() && find(rhs).isInteger())
597: || (find(lhs).isInteger() && find(rhs).isFloat())) {
598: Type type = new BooleanT();
599: makeSet(type);
600: return type;
601: } else {
602: runtime.error("Cannot compare " + find(lhs) + " and "
603: + find(rhs) + " in an inclusion expression", n);
604: return ErrorT.TYPE;
605: }
606: }
607: }
608:
609: public Type visitRangeExpression(final GNode n) {
610: final Type lhs = (Type) dispatch(n.getNode(1));
611: final Type rhs = (Type) dispatch(n.getNode(2));
612: final boolean unified = unify(lhs, rhs);
613: if (unified) {
614: return find(lhs);
615: } else {
616: // Maybe we can coerce
617: if ((find(lhs).isFloat() && find(rhs).isInteger())
618: || (find(lhs).isInteger() && find(rhs).isFloat())) {
619: return NumberT.FLOAT;
620: } else {
621: runtime.error("Cannot compare " + find(lhs) + " and "
622: + find(rhs) + " in a range expression", n);
623: return ErrorT.TYPE;
624: }
625: }
626: }
627:
628: public Type visitPostfixExpression(final GNode n) {
629: // first we get the tuple's name
630: final String name = n.getNode(0).getString(0);
631: // now create a temporary variable to represent the
632: // return value of this function.
633: final Type retVar = new Parameter(newTempTypeName());
634: makeSet(retVar);
635: final ArrayList<Type> args = (ArrayList<Type>) visitArguments(n
636: .getGeneric(1));
637: final FunctionT type = new FunctionT(retVar, args, false);
638: // check to see if the function has been defined before. If it hasn't
639: // define it, and we're done; If it has, see if we can unify.
640: final Type definedType = (Type) table.root().lookup(name);
641: if (null == definedType) {
642: table.root().define(name, type);
643: } else {
644: final boolean unified = unify(definedType, type);
645: if (!unified) {
646: runtime
647: .error(
648: "Function previously defined with a different type",
649: n);
650: return ErrorT.TYPE;
651: }
652: }
653: return retVar;
654: }
655:
656: public ArrayList<Type> visitArguments(final GNode n) {
657: ArrayList<Type> argList = new ArrayList<Type>();
658: if (n.size() != 0) {
659: for (Node term : n.<Node> getList(0)) {
660: Type t = (Type) dispatch(term);
661: argList.add(t);
662: }
663: }
664: return argList;
665: }
666:
667: public Type visitVectorExpression(final GNode n) {
668: ArrayList<Type> indexList = new ArrayList<Type>();
669: final Type idx1 = (Type) dispatch((Node) indexList.get(0));
670: final Type idx2 = (Type) dispatch((Node) indexList.get(1));
671: final boolean unified = unify(idx1, idx2);
672: if (!unified) {
673: runtime.error("Vector mal-typed", n);
674: return ErrorT.TYPE;
675: } else {
676: return new ArrayT(idx1, true);
677: }
678: }
679:
680: public Type visitMatrixExpression(final GNode n) {
681: // @fixme should a matrix be a new type?
682: return new ArrayT(NumberT.S_INT, true);
683: }
684:
685: public Type visitMatrixEntry(final GNode n) {
686: // @fixme should a matrix be a new type?
687: return new ArrayT(NumberT.S_INT, true);
688: }
689:
690: public Type visitParenthesizedExpression(final GNode n) {
691: return (Type) dispatch(n.getNode(0));
692: }
693:
694: public Type visitAggregate(final GNode n) {
695: // visit the name
696: dispatch(n.getNode(0));
697: // visit what the aggregate is on
698: return (Type) dispatch(n.getNode(1));
699: }
700:
701: public Type visitLocationSpecifier(final GNode n) {
702: final Type t = (Type) dispatch(n.getNode(0));
703: final Type type = new InternalT("location");
704: final boolean unified = unify(t, type);
705: if (!unified) {
706: runtime.error("Location Specifier variable "
707: + "previously defined as a different type", n);
708: return ErrorT.TYPE;
709: } else {
710: return type;
711: }
712: }
713:
714: public Type visitAggregateIdentifier(final GNode n) {
715: final String name = n.getString(0);
716: Type type = (Type) table.current().lookup(name);
717: // if already defined, make sure its an aggregate
718: // otherwise, create a new entry;
719: if (type != null) {
720: if ("aggregate".equals(type.getName())) {
721: return type;
722: } else {
723: runtime.error("Aggregate Identifier "
724: + "previously defined as a different type", n);
725: return ErrorT.TYPE;
726: }
727: } else {
728: type = new InternalT("aggregate");
729: makeSet(type);
730: table.current().define(name, type);
731: return type;
732: }
733: }
734:
735: public Type visitVariableIdentifier(final GNode n) {
736: final String name = n.getString(0);
737: Type type = (Type) table.current().lookup(name);
738: // if already defined, return that
739: // otherwise, create a new entry;
740: if (type != null) {
741: return type;
742: } else {
743: type = new Parameter(newTempTypeName());
744: makeSet(type);
745: table.current().define(name, type);
746: return type;
747: }
748: }
749:
750: public Type visitUnnamedIdentifier(final GNode n) {
751: final Wildcard type = new Wildcard();
752: makeSet(type);
753: return type;
754: }
755:
756: public Type visitFloatingPointConstant(final GNode n) {
757: final Type type = NumberT.FLOAT;
758: makeSet(type);
759: return type;
760: }
761:
762: public Type visitIntegerConstant(final GNode n) {
763: final Type type = NumberT.S_INT;
764: makeSet(type);
765: return type;
766: }
767:
768: public Type visitStringConstant(final GNode n) {
769: final Type type = new InternalT("string constant");
770: makeSet(type);
771: return type;
772: }
773:
774: public Type visitBooleanConstant(final GNode n) {
775: final Type type = new BooleanT();
776: makeSet(type);
777: return type;
778: }
779:
780: public Type visitInfinityConstant(final GNode n) {
781: final Type type = NumberT.S_INT;
782: makeSet(type);
783: return type;
784: }
785:
786: public Type visitNullConstant(final GNode n) {
787: final Type type = new VoidT();
788: type.annotate().constant(NullReference.NULL);
789: makeSet(type);
790: return type;
791: }
792: }
|