00001: package clogs.staticanalysis; 00002: 00003: import clogs.ast.*; 00004: import clogs.util.List; 00005: import clogs.util.Optional; 00006: 00007: 00008: // Well-formedness addresses the following issues: 00009: // 1. No void array types 00010: // 2. All parameter and variable declarations have non-void types 00011: // 3. No two global variable declarations have the same name 00012: // 4. No two functions declarations have the same name 00013: // 5. No two labels in the same function declaration have the same name 00014: // 6. Every label used in a function is declared in the same function 00015: // 7. Top level declarations have no initializers 00016: // 8. Only top-level compound statements have declarations 00017: public class WellFormedCheck 00018: { 00019: public class WellFormedCheckException extends Exception 00020: { 00021: WellFormedCheckException (String s) 00022: { 00023: super (s); 00024: } 00025: } 00026: 00027: 00028: private final List<Decl> globalDecls; 00029: private final List<FunDefSig> fundefsigs; 00030: 00031: 00032: public WellFormedCheck (List<ExtDecl> edecls, List<FunDefSig> fundefsigs) 00033: { 00034: List<Decl> declsTmp = List.nil (); 00035: List<FunDefSig> fundefsigsTmp = fundefsigs; 00036: for (ExtDecl edecl : edecls) { 00037: if (edecl instanceof Decl) { 00038: Decl decl = (Decl) edecl; 00039: declsTmp = declsTmp.snoc (decl); 00040: 00041: } else if (edecl instanceof FunDef) { 00042: FunDef fundef = (FunDef) edecl; 00043: fundefsigsTmp = fundefsigsTmp.snoc (fundef); 00044: 00045: } else { 00046: throw new RuntimeException ("Missing ExtDecl case: " + edecl.getClass ().getName ()); 00047: } 00048: } 00049: 00050: this.globalDecls = declsTmp; 00051: this.fundefsigs = fundefsigsTmp; 00052: } 00053: 00054: 00055: public void check () 00056: throws WellFormedCheckException 00057: { 00058: checkDecls (globalDecls, false); 00059: checkFunDefSigs (); 00060: } 00061: 00062: 00063: void checkDecls (List<Decl> decls, boolean initializerOK) 00064: throws WellFormedCheckException 00065: { 00066: // Ensure no declarations share the same name. 00067: checkNoDuplicateDecl (decls); 00068: 00069: for (Decl decl : decls) { 00070: // Ensure type is well formed. 00071: if (!checkTypeWellFormed (decl.type)) { 00072: throw new RuntimeException ("Type must be well formed: " + decl); 00073: } 00074: 00075: // Ensure type is suitable for a variable declaration. 00076: if (!checkNonReturnTypeOK (decl.type)) { 00077: throw new RuntimeException ("Variable type must be non-void: " + decl); 00078: } 00079: 00080: // Ensure no initializers in certain locations, e.g., global variables and function parameters 00081: if (!initializerOK && !decl.eo.isEmpty ()) { 00082: throw new RuntimeException ("Initializer not allowed here: " + decl); 00083: } 00084: } 00085: } 00086: 00087: 00088: void checkFunDefSigs () 00089: throws WellFormedCheckException 00090: { 00091: // Ensure no function declarations share the same name. 00092: checkNoDuplicateFunDefSigs (); 00093: 00094: for (FunDefSig fundefsig : fundefsigs) { 00095: // Ensure type is well formed. 00096: if (!checkTypeWellFormed (fundefsig.type)) { 00097: throw new RuntimeException ("Type must be well formed: " + fundefsig.type); 00098: } 00099: 00100: checkDecls (fundefsig.params, false); 00101: 00102: if (fundefsig instanceof FunDef) { 00103: FunDef fundef = (FunDef) fundefsig; 00104: checkStatCompound (fundef.body, true); 00105: } 00106: } 00107: } 00108: 00109: 00110: void checkStatCompound (StatCompound statC, boolean topLevel) 00111: throws WellFormedCheckException 00112: { 00113: if (!statC.decls.isNil() && !topLevel) { 00114: throw new WellFormedCheckException ("Declaration not at top level in \"" + statC + "\""); 00115: } 00116: checkDecls (statC.decls, true); 00117: 00118: 00119: // Gather labels defined and used in compound statement. 00120: GatherLabelsInStat glisc = new GatherLabelsInStat (); 00121: glisc.gather (statC); 00122: 00123: // Ensure no duplicate label definitions. 00124: String duplicate = glisc.labelsDefined.findDuplicate (); 00125: if (duplicate != null) { 00126: throw new WellFormedCheckException ("Found duplicate label \"" + duplicate + "\" definition in \"" + statC + "\""); 00127: } 00128: 00129: // Ensure all used labels are defined in the same top-level compound statement. 00130: if (topLevel) { 00131: for (String label : glisc.labelsUsed) { 00132: if (!glisc.labelsDefined.contains (label)) { 00133: throw new WellFormedCheckException ("Label \"" + label + "\" used but not defined in \"" + statC + "\""); 00134: } 00135: } 00136: } 00137: 00138: for (Stat stat : statC.stats) { 00139: checkStat (stat); 00140: } 00141: } 00142: 00143: 00144: void checkStat (Stat stat) 00145: throws WellFormedCheckException 00146: { 00147: if (stat instanceof StatCompound) { 00148: StatCompound statC = (StatCompound) stat; 00149: checkStatCompound (statC, false); 00150: 00151: } else if (stat instanceof StatExp) { 00152: // Nothing to check. 00153: 00154: } else if (stat instanceof StatGoto) { 00155: StatGoto statG = (StatGoto) stat; 00156: // Nothing to check. 00157: 00158: } else if (stat instanceof StatIf) { 00159: StatIf statI = (StatIf) stat; 00160: checkStat (statI.statT); 00161: checkStat (statI.statF); 00162: 00163: } else if (stat instanceof StatReturn) { 00164: StatReturn statR = (StatReturn) stat; 00165: // Nothing to check. 00166: 00167: } else if (stat instanceof StatSkip) { 00168: StatSkip statS = (StatSkip) stat; 00169: // Nothing to check. 00170: 00171: } else if (stat instanceof StatWhile) { 00172: StatWhile statW = (StatWhile) stat; 00173: checkStat (statW.stat); 00174: 00175: } else { 00176: throw new RuntimeException ("Missing Stat case: " + stat.getClass ().getName ()); 00177: } 00178: } 00179: 00180: 00181: void checkNoDuplicateDecl (List<Decl> decls) 00182: throws WellFormedCheckException 00183: { 00184: List<String> names = List.nil (); 00185: for (Decl decl : decls) { 00186: names = names.cons (decl.name); 00187: } 00188: 00189: String duplicate = names.findDuplicate (); 00190: if (duplicate != null) { 00191: throw new WellFormedCheckException ("Found duplicate declaration name for \"" + duplicate + "\""); 00192: } 00193: } 00194: 00195: 00196: void checkNoDuplicateFunDefSigs () 00197: throws WellFormedCheckException 00198: { 00199: List<String> names = List.nil (); 00200: for (FunDefSig fundefsig : fundefsigs) { 00201: names = names.cons (fundefsig.name); 00202: } 00203: 00204: String duplicate = names.findDuplicate (); 00205: if (duplicate != null) { 00206: throw new WellFormedCheckException ("Found duplicate function definition declaration/signature for \"" + duplicate + "\""); 00207: } 00208: } 00209: 00210: 00211: boolean checkNonReturnTypeOK (Type type) 00212: { 00213: if (type instanceof TypeVoid) { 00214: return false; 00215: } else { 00216: return true; 00217: } 00218: } 00219: 00220: 00221: boolean checkTypeWellFormed (Type type) 00222: { 00223: if ((type instanceof TypeInt) || (type instanceof TypeVoid)) { 00224: return true; 00225: } 00226: 00227: while (type instanceof TypeArray) { 00228: TypeArray typeA = (TypeArray) type; 00229: type = typeA.type; 00230: } 00231: 00232: if (type instanceof TypeInt) { 00233: return true; 00234: } else if (type instanceof TypeVoid) { 00235: return false; 00236: } else { 00237: throw new RuntimeException ("Missing Type case: " + type.getClass ().getName ()); 00238: } 00239: } 00240: } 00241: 00242: 00243: