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:
|
