Finish semantic checks
[IRC.git] / Robust / src / IR / Tree / SemanticCheck.java
1 package IR.Tree;
2
3 import java.util.*;
4 import IR.*;
5
6 public class SemanticCheck {
7     State state;
8     TypeUtil typeutil;
9
10     public SemanticCheck(State state, TypeUtil tu) {
11         this.state=state;
12         this.typeutil=tu;
13     }
14
15     public void semanticCheck() {
16         SymbolTable classtable=state.getClassSymbolTable();
17         Iterator it=classtable.getDescriptorsIterator();
18         // Do descriptors first
19         while(it.hasNext()) {
20             ClassDescriptor cd=(ClassDescriptor)it.next();
21             System.out.println("Checking class: "+cd);
22             //Set superclass link up
23             if (cd.getSuper()!=null) {
24                 cd.setSuper(typeutil.getClass(cd.getSuper()));
25                 // Link together Field and Method tables
26                 cd.getFieldTable().setParent(cd.getSuperDesc().getFieldTable());
27                 cd.getMethodTable().setParent(cd.getSuperDesc().getMethodTable());
28             }
29             
30             for(Iterator field_it=cd.getFields();field_it.hasNext();) {
31                 FieldDescriptor fd=(FieldDescriptor)field_it.next();
32                 System.out.println("Checking field: "+fd);
33                 checkField(cd,fd);
34             }
35             for(Iterator method_it=cd.getMethods();method_it.hasNext();) {
36                 MethodDescriptor md=(MethodDescriptor)method_it.next();
37                 checkMethod(cd,md);
38             }
39         }
40
41         it=classtable.getDescriptorsIterator();
42         // Do descriptors first
43         while(it.hasNext()) {
44             ClassDescriptor cd=(ClassDescriptor)it.next();
45             for(Iterator method_it=cd.getMethods();method_it.hasNext();) {
46                 MethodDescriptor md=(MethodDescriptor)method_it.next();
47                 checkMethodBody(cd,md);
48             }
49         }
50     }
51
52     public void checkTypeDescriptor(TypeDescriptor td) {
53         if (td.isPrimitive())
54             return; /* Done */
55         if (td.isClass()) {
56             String name=td.toString();
57             ClassDescriptor field_cd=(ClassDescriptor)state.getClassSymbolTable().get(name);
58             if (field_cd==null)
59                 throw new Error("Undefined class "+name);
60             td.setClassDescriptor(field_cd);
61             return;
62         }
63         throw new Error();
64     }
65
66     public void checkField(ClassDescriptor cd, FieldDescriptor fd) {
67         checkTypeDescriptor(fd.getType());
68     }
69
70     public void checkMethod(ClassDescriptor cd, MethodDescriptor md) {
71         /* Check return type */
72         if (!md.isConstructor())
73             if (!md.getReturnType().isVoid())
74                 checkTypeDescriptor(md.getReturnType());
75
76         for(int i=0;i<md.numParameters();i++) {
77             TypeDescriptor param_type=md.getParamType(i);
78             checkTypeDescriptor(param_type);
79         }
80         /* Link the naming environments */
81         md.getParameterTable().setParent(cd.getFieldTable());
82         md.setClassDesc(cd);
83         if (!md.isStatic()) {
84             VarDescriptor thisvd=new VarDescriptor(new TypeDescriptor(cd),"this");
85             md.setThis(thisvd);
86         }
87     }
88
89     public void checkMethodBody(ClassDescriptor cd, MethodDescriptor md) {
90         BlockNode bn=state.getMethodBody(md);
91         checkBlockNode(md, md.getParameterTable(),bn);
92     }
93     
94     public void checkBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn) {
95         /* Link in the naming environment */
96         bn.getVarTable().setParent(nametable);
97         for(int i=0;i<bn.size();i++) {
98             BlockStatementNode bsn=bn.get(i);
99             checkBlockStatementNode(md, bn.getVarTable(),bsn);
100         }
101     }
102     
103     public void checkBlockStatementNode(MethodDescriptor md, SymbolTable nametable, BlockStatementNode bsn) {
104         switch(bsn.kind()) {
105         case Kind.BlockExpressionNode:
106             checkBlockExpressionNode(md, nametable,(BlockExpressionNode)bsn);
107             return;
108
109         case Kind.DeclarationNode:
110             checkDeclarationNode(md, nametable, (DeclarationNode)bsn);
111             return;
112             
113         case Kind.IfStatementNode:
114             checkIfStatementNode(md, nametable, (IfStatementNode)bsn);
115             return;
116             
117         case Kind.LoopNode:
118             checkLoopNode(md, nametable, (LoopNode)bsn);
119             return;
120             
121         case Kind.ReturnNode:
122             checkReturnNode(md, nametable, (ReturnNode)bsn);
123             return;
124
125         case Kind.SubBlockNode:
126             checkSubBlockNode(md, nametable, (SubBlockNode)bsn);
127             return;
128         }
129         throw new Error();
130     }
131
132     void checkBlockExpressionNode(MethodDescriptor md, SymbolTable nametable, BlockExpressionNode ben) {
133         checkExpressionNode(md, nametable, ben.getExpression(), null);
134     }
135
136     void checkDeclarationNode(MethodDescriptor md, SymbolTable nametable,  DeclarationNode dn) {
137         VarDescriptor vd=dn.getVarDescriptor();
138         checkTypeDescriptor(vd.getType());
139         Descriptor d=nametable.get(vd.getSymbol());
140         if ((d==null)||
141             (d instanceof FieldDescriptor)) {
142             nametable.add(vd);
143         } else
144             throw new Error(vd.getSymbol()+" defined a second time");
145         if (dn.getExpression()!=null)
146             checkExpressionNode(md, nametable, dn.getExpression(), vd.getType());
147     }
148     
149     void checkSubBlockNode(MethodDescriptor md, SymbolTable nametable, SubBlockNode sbn) {
150         checkBlockNode(md, nametable, sbn.getBlockNode());
151     }
152
153     void checkReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn) {
154         checkExpressionNode(md, nametable, rn.getReturnExpression(), md.getReturnType());
155     }
156
157     void checkIfStatementNode(MethodDescriptor md, SymbolTable nametable, IfStatementNode isn) {
158         checkExpressionNode(md, nametable, isn.getCondition(), new TypeDescriptor(TypeDescriptor.BOOLEAN));
159         checkBlockNode(md, nametable, isn.getTrueBlock());
160         checkBlockNode(md, nametable, isn.getFalseBlock());
161     }
162     
163     void checkExpressionNode(MethodDescriptor md, SymbolTable nametable, ExpressionNode en, TypeDescriptor td) {
164         switch(en.kind()) {
165         case Kind.AssignmentNode:
166             checkAssignmentNode(md,nametable,(AssignmentNode)en,td);
167             return;
168         case Kind.CastNode:
169             checkCastNode(md,nametable,(CastNode)en,td);
170             return;
171         case Kind.CreateObjectNode:
172             checkCreateObjectNode(md,nametable,(CreateObjectNode)en,td);
173             return;
174         case Kind.FieldAccessNode:
175             checkFieldAccessNode(md,nametable,(FieldAccessNode)en,td);
176             return;
177         case Kind.LiteralNode:
178             checkLiteralNode(md,nametable,(LiteralNode)en,td);
179             return;
180         case Kind.MethodInvokeNode:
181             checkMethodInvokeNode(md,nametable,(MethodInvokeNode)en,td);
182             return;
183         case Kind.NameNode:
184             checkNameNode(md,nametable,(NameNode)en,td);
185             return;
186         case Kind.OpNode:
187             checkOpNode(md,nametable,(OpNode)en,td);
188             return;
189         }
190         throw new Error();
191     }
192
193     void checkCastNode(MethodDescriptor md, SymbolTable nametable, CastNode cn, TypeDescriptor td) {
194         /* Get type descriptor */
195         if (cn.getType()==null) {
196             NameDescriptor typenamed=cn.getTypeName().getName();
197             String typename=typenamed.toString();
198             TypeDescriptor ntd=new TypeDescriptor(typeutil.getClass(typename));
199             cn.setType(ntd);
200         }
201
202         /* Check the type descriptor */
203         TypeDescriptor cast_type=cn.getType();
204         checkTypeDescriptor(cast_type);
205
206         /* Type check */
207         if (td!=null) {
208             if (!typeutil.isSuperorType(td,cast_type))
209                 throw new Error("Cast node returns "+cast_type+", but need "+td);
210         }
211
212         ExpressionNode en=cn.getExpression();
213         checkExpressionNode(md, nametable, en, null);
214         TypeDescriptor etd=en.getType();
215         if (typeutil.isSuperorType(cast_type,etd)) /* Cast trivially succeeds */
216             return;
217
218         if (typeutil.isSuperorType(etd,cast_type)) /* Cast may succeed */
219             return;
220
221         /* Different branches */
222         /* TODO: change if add interfaces */
223         throw new Error("Cast will always fail\n"+cn.printNode(0));
224     }
225
226     void checkFieldAccessNode(MethodDescriptor md, SymbolTable nametable, FieldAccessNode fan, TypeDescriptor td) {
227         ExpressionNode left=fan.getExpression();
228         checkExpressionNode(md,nametable,left,null);
229         TypeDescriptor ltd=left.getType();
230         String fieldname=fan.getFieldName();
231         FieldDescriptor fd=(FieldDescriptor) ltd.getClassDesc().getFieldTable().get(fieldname);
232         if (fd==null)
233             throw new Error("Unknown field "+fieldname);
234         fan.setField(fd);
235         if (td!=null)
236             if (!typeutil.isSuperorType(td,fan.getType()))
237                 throw new Error("Field node returns "+fan.getType()+", but need "+td);
238     }
239
240     void checkLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode ln, TypeDescriptor td) {
241         /* Resolve the type */
242         Object o=ln.getValue();
243         if (ln.getTypeString().equals("null")) {
244             ln.setType(new TypeDescriptor(TypeDescriptor.NULL));
245         } else if (o instanceof Integer) {
246             ln.setType(new TypeDescriptor(TypeDescriptor.INT));
247         } else if (o instanceof Long) {
248             ln.setType(new TypeDescriptor(TypeDescriptor.LONG));
249         } else if (o instanceof Float) {
250             ln.setType(new TypeDescriptor(TypeDescriptor.FLOAT));
251         } else if (o instanceof Double) {
252             ln.setType(new TypeDescriptor(TypeDescriptor.DOUBLE));
253         } else if (o instanceof Character) {
254             ln.setType(new TypeDescriptor(TypeDescriptor.CHAR));
255         } else if (o instanceof String) {
256             ln.setType(new TypeDescriptor(typeutil.getClass(TypeUtil.StringClass)));
257         } 
258
259         if (td!=null)
260             if (!typeutil.isSuperorType(td,ln.getType()))
261                 throw new Error("Field node returns "+ln.getType()+", but need "+td);
262     }
263
264     void checkNameNode(MethodDescriptor md, SymbolTable nametable, NameNode nn, TypeDescriptor td) {
265         NameDescriptor nd=nn.getName();
266         String varname=nd.toString();
267         Descriptor d=(Descriptor)nametable.get(varname);
268         if (d==null) {
269             throw new Error("Name "+varname+" undefined");
270         }
271         if (d instanceof VarDescriptor) {
272             nn.setVar((VarDescriptor)d);
273         } else if (d instanceof FieldDescriptor) {
274             nn.setField((FieldDescriptor)d);
275         }
276         if (td!=null)
277             if (!typeutil.isSuperorType(td,nn.getType()))
278                 throw new Error("Field node returns "+nn.getType()+", but need "+td);
279     }
280
281     void checkAssignmentNode(MethodDescriptor md, SymbolTable nametable, AssignmentNode an, TypeDescriptor td) {
282         checkExpressionNode(md, nametable, an.getSrc() ,td);
283         //TODO: Need check on validity of operation here
284         if (!((an.getDest() instanceof FieldAccessNode)||
285               (an.getDest() instanceof NameNode)))
286             throw new Error("Bad lside in "+an.printNode(0));
287         checkExpressionNode(md, nametable, an.getDest(), null);
288         if (!typeutil.isSuperorType(an.getDest().getType(),an.getSrc().getType()))
289             throw new Error("Type of rside not compatible with type of lside"+an.printNode(0));
290     }
291
292     void checkLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln) {
293         if (ln.getType()==LoopNode.WHILELOOP||ln.getType()==LoopNode.DOWHILELOOP) {
294             checkExpressionNode(md, nametable, ln.getCondition(), new TypeDescriptor(TypeDescriptor.BOOLEAN));
295             checkBlockNode(md, nametable, ln.getBody());
296         } else {
297             //For loop case
298             /* Link in the initializer naming environment */
299             BlockNode bn=ln.getInitializer();
300             bn.getVarTable().setParent(nametable);
301             for(int i=0;i<bn.size();i++) {
302                 BlockStatementNode bsn=bn.get(i);
303                 checkBlockStatementNode(md, bn.getVarTable(),bsn);
304             }
305             //check the condition
306             checkExpressionNode(md, bn.getVarTable(), ln.getCondition(), new TypeDescriptor(TypeDescriptor.BOOLEAN));
307             checkBlockNode(md, bn.getVarTable(), ln.getBody());
308             checkBlockNode(md, bn.getVarTable(), ln.getUpdate());
309         }
310     }
311
312
313     void checkCreateObjectNode(MethodDescriptor md, SymbolTable nametable, CreateObjectNode con, TypeDescriptor td) {
314         TypeDescriptor[] tdarray=new TypeDescriptor[con.numArgs()];
315         for(int i=0;i<con.numArgs();i++) {
316             ExpressionNode en=con.getArg(i);
317             checkExpressionNode(md,nametable,en,null);
318             tdarray[i]=en.getType();
319         }
320
321         TypeDescriptor typetolookin=con.getType();
322         checkTypeDescriptor(typetolookin);
323         if (!typetolookin.isClass()) 
324             throw new Error();
325
326         ClassDescriptor classtolookin=typetolookin.getClassDesc();
327         System.out.println("Looking for "+typetolookin.getSymbol());
328         System.out.println(classtolookin.getMethodTable());
329
330         Set methoddescriptorset=classtolookin.getMethodTable().getSet(typetolookin.getSymbol());
331         MethodDescriptor bestmd=null;
332         NextMethod:
333         for(Iterator methodit=methoddescriptorset.iterator();methodit.hasNext();) {
334             MethodDescriptor currmd=(MethodDescriptor)methodit.next();
335             /* Need correct number of parameters */
336             System.out.println("Examining: "+currmd);
337             if (con.numArgs()!=currmd.numParameters())
338                 continue;
339             for(int i=0;i<con.numArgs();i++) {
340                 if (!typeutil.isSuperorType(currmd.getParamType(i),tdarray[i]))
341                     continue NextMethod;
342             }
343             /* Method okay so far */
344             if (bestmd==null)
345                 bestmd=currmd;
346             else {
347                 if (isMoreSpecific(currmd,bestmd)) {
348                     bestmd=currmd;
349                 } else if (!isMoreSpecific(bestmd, currmd))
350                     throw new Error("No method is most specific");
351                 
352                 /* Is this more specific than bestmd */
353             }
354         }
355         if (bestmd==null)
356             throw new Error("No method found for "+con.printNode(0));
357         con.setConstructor(bestmd);
358
359         
360     }
361
362
363     /** Check to see if md1 is more specific than md2...  Informally
364         if md2 could always be called given the arguments passed into
365         md1 */
366
367     boolean isMoreSpecific(MethodDescriptor md1, MethodDescriptor md2) {
368         /* Checks if md1 is more specific than md2 */
369         if (md1.numParameters()!=md2.numParameters())
370             throw new Error();
371         for(int i=0;i<md1.numParameters();i++) {
372             if (!typeutil.isSuperorType(md2.getParamType(i), md1.getParamType(i)))
373                 return false;
374         }
375         if (!typeutil.isSuperorType(md2.getReturnType(), md1.getReturnType()))
376                 return false;
377         return true;
378     }
379
380     ExpressionNode translateNameDescriptorintoExpression(NameDescriptor nd) {
381         String id=nd.getIdentifier();
382         NameDescriptor base=nd.getBase();
383         if (base==null) 
384             return new NameNode(nd);
385         else 
386             return new FieldAccessNode(translateNameDescriptorintoExpression(base),id);
387     }
388
389
390     void checkMethodInvokeNode(MethodDescriptor md, SymbolTable nametable, MethodInvokeNode min, TypeDescriptor td) {
391         /*Typecheck subexpressions
392           and get types for expressions*/
393
394         TypeDescriptor[] tdarray=new TypeDescriptor[min.numArgs()];
395         for(int i=0;i<min.numArgs();i++) {
396             ExpressionNode en=min.getArg(i);
397             checkExpressionNode(md,nametable,en,null);
398             tdarray[i]=en.getType();
399         }
400         TypeDescriptor typetolookin=null;
401         if (min.getExpression()!=null) {
402             checkExpressionNode(md,nametable,min.getExpression(),null);
403             typetolookin=min.getExpression().getType();
404         } else if (min.getBaseName()!=null) {
405             String rootname=min.getBaseName().getRoot();
406             if (nametable.get(rootname)!=null) {
407                 //we have an expression
408                 min.setExpression(translateNameDescriptorintoExpression(min.getBaseName()));
409                 checkExpressionNode(md, nametable, min.getExpression(), null);
410                 typetolookin=min.getExpression().getType();
411             } else {
412                 //we have a type
413                 ClassDescriptor cd=typeutil.getClass(min.getBaseName().getSymbol());
414                 if (cd==null)
415                     throw new Error(min.getBaseName()+" undefined");
416                 typetolookin=new TypeDescriptor(cd);
417             }
418         } else {
419             typetolookin=new TypeDescriptor(md.getClassDesc());
420         }
421         if (!typetolookin.isClass()) 
422             throw new Error();
423         ClassDescriptor classtolookin=typetolookin.getClassDesc();
424         System.out.println("Method name="+min.getMethodName());
425         Set methoddescriptorset=classtolookin.getMethodTable().getSet(min.getMethodName());
426         MethodDescriptor bestmd=null;
427         NextMethod:
428         for(Iterator methodit=methoddescriptorset.iterator();methodit.hasNext();) {
429             MethodDescriptor currmd=(MethodDescriptor)methodit.next();
430             /* Need correct number of parameters */
431             if (min.numArgs()!=currmd.numParameters())
432                 continue;
433             for(int i=0;i<min.numArgs();i++) {
434                 if (!typeutil.isSuperorType(currmd.getParamType(i),tdarray[i]))
435                     continue NextMethod;
436             }
437             /* Method okay so far */
438             if (bestmd==null)
439                 bestmd=currmd;
440             else {
441                 if (isMoreSpecific(currmd,bestmd)) {
442                     bestmd=currmd;
443                 } else if (!isMoreSpecific(bestmd, currmd))
444                     throw new Error("No method is most specific");
445                 
446                 /* Is this more specific than bestmd */
447             }
448         }
449         if (bestmd==null)
450             throw new Error("No method found for :"+min.printNode(0));
451         min.setMethod(bestmd);
452     }
453
454
455     void checkOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on, TypeDescriptor td) {
456         checkExpressionNode(md, nametable, on.getLeft(), null);
457         if (on.getRight()!=null)
458             checkExpressionNode(md, nametable, on.getRight(), null);
459         TypeDescriptor ltd=on.getLeft().getType();
460         TypeDescriptor rtd=on.getRight()!=null?on.getRight().getType():null;
461         TypeDescriptor thistype=null;
462         if (rtd!=null) {
463             // 5.6.2 Binary Numeric Promotion
464             //TODO unboxing of reference objects
465             if (ltd.isDouble()||rtd.isDouble())
466                 thistype=new TypeDescriptor(TypeDescriptor.DOUBLE);
467             else if (ltd.isFloat()||rtd.isFloat())
468                 thistype=new TypeDescriptor(TypeDescriptor.FLOAT);
469             else if (ltd.isLong()||rtd.isLong())
470                 thistype=new TypeDescriptor(TypeDescriptor.LONG);
471             else 
472                 thistype=new TypeDescriptor(TypeDescriptor.INT);
473             
474         } else {
475             //5.6.1 Unary Numeric Promotion
476             if (ltd.isByte()||ltd.isShort()||ltd.isInt())
477                 thistype=new TypeDescriptor(TypeDescriptor.INT);
478             else
479                 thistype=ltd;
480         }
481         on.setType(thistype);
482         if (td!=null)
483             if (!typeutil.isSuperorType(td, thistype))
484                 throw new Error("Type of rside not compatible with type of lside"+on.printNode(0));     
485     }
486
487
488 }