| OLD | NEW |
|---|
| (Empty) |
| 1 library tree_ir.integrity; | |
| 2 | |
| 3 import 'tree_ir_nodes.dart'; | |
| 4 | |
| 5 /// Performs integrity checks on the tree_ir. | |
| 6 /// | |
| 7 /// Should only be run for debugging purposes, not in production. | |
| 8 /// | |
| 9 /// - Reference counts on must match the actual number of references. | |
| 10 /// - Labels must be in scope when referenced. | |
| 11 /// - Breaks must target a [LabeledStatement]. | |
| 12 /// - Continues must target a [Loop]. | |
| 13 /// - Variables must only be used after their first assignment | |
| 14 /// (checked on a best-effort basis). | |
| 15 /// - Variables with a declaration must only be referenced in scope. | |
| 16 /// - Variables must not have more than one declaration. | |
| 17 /// | |
| 18 class CheckTreeIntegrity extends RecursiveVisitor { | |
| 19 FunctionDefinition topLevelNode; | |
| 20 | |
| 21 Map<Variable, int> varReads = <Variable, int>{}; | |
| 22 Map<Variable, int> varWrites = <Variable, int>{}; | |
| 23 Map<Label, int> labelUses = <Label, int>{}; | |
| 24 Map<Label, JumpTarget> label2declaration = <Label, JumpTarget>{}; | |
| 25 | |
| 26 /// Variables that are currently in scope. | |
| 27 Set<Variable> scope = new Set<Variable>(); | |
| 28 | |
| 29 /// Variables for which we have seen a declaration. | |
| 30 Set<Variable> seenDeclaration = new Set<Variable>(); | |
| 31 | |
| 32 void write(Variable variable) { | |
| 33 if (!seenDeclaration.contains(variable)) { | |
| 34 // Implicitly-declared variables are in scope after the first assignment. | |
| 35 scope.add(variable); | |
| 36 } else if (!scope.contains(variable)) { | |
| 37 // There is a declaration for variable but it is no longer in scope. | |
| 38 error('$variable assigned out of scope'); | |
| 39 } | |
| 40 varWrites.putIfAbsent(variable, () => 0); | |
| 41 varWrites[variable]++; | |
| 42 } | |
| 43 | |
| 44 void read(Variable variable) { | |
| 45 if (!scope.contains(variable)) { | |
| 46 error('$variable used out of scope'); | |
| 47 } | |
| 48 varReads.putIfAbsent(variable, () => 0); | |
| 49 varReads[variable]++; | |
| 50 } | |
| 51 | |
| 52 void declare(Variable variable) { | |
| 53 if (!scope.add(variable) || !seenDeclaration.add(variable)) { | |
| 54 error('Redeclared $variable'); | |
| 55 } | |
| 56 varWrites.putIfAbsent(variable, () => 0); | |
| 57 varWrites[variable]++; | |
| 58 } | |
| 59 | |
| 60 void undeclare(Variable variable) { | |
| 61 scope.remove(variable); | |
| 62 } | |
| 63 | |
| 64 visitVariableUse(VariableUse node) { | |
| 65 read(node.variable); | |
| 66 } | |
| 67 | |
| 68 visitAssign(Assign node) { | |
| 69 visitExpression(node.value); | |
| 70 write(node.variable); | |
| 71 } | |
| 72 | |
| 73 visitTry(Try node) { | |
| 74 visitStatement(node.tryBody); | |
| 75 node.catchParameters.forEach(declare); | |
| 76 visitStatement(node.catchBody); | |
| 77 node.catchParameters.forEach(undeclare); | |
| 78 } | |
| 79 | |
| 80 visitJumpTargetBody(JumpTarget target) { | |
| 81 Label label = target.label; | |
| 82 if (label2declaration.containsKey(label)) { | |
| 83 error('Duplicate declaration of label $label'); | |
| 84 } | |
| 85 label2declaration[label] = target; | |
| 86 labelUses[label] = 0; | |
| 87 visitStatement(target.body); | |
| 88 label2declaration.remove(label); | |
| 89 | |
| 90 if (labelUses[label] != label.useCount) { | |
| 91 error('Label $label has ${labelUses[label]} uses ' | |
| 92 'but its reference count is ${label.useCount}'); | |
| 93 } | |
| 94 } | |
| 95 | |
| 96 visitLabeledStatement(LabeledStatement node) { | |
| 97 visitJumpTargetBody(node); | |
| 98 visitStatement(node.next); | |
| 99 } | |
| 100 | |
| 101 visitWhileTrue(WhileTrue node) { | |
| 102 visitJumpTargetBody(node); | |
| 103 } | |
| 104 | |
| 105 visitFor(For node) { | |
| 106 visitExpression(node.condition); | |
| 107 visitJumpTargetBody(node); | |
| 108 node.updates.forEach(visitExpression); | |
| 109 visitStatement(node.next); | |
| 110 } | |
| 111 | |
| 112 visitBreak(Break node) { | |
| 113 if (!label2declaration.containsKey(node.target)) { | |
| 114 error('Break to label that is not in scope'); | |
| 115 } | |
| 116 if (label2declaration[node.target] is! LabeledStatement) { | |
| 117 error('Break to non-labeled statement ${label2declaration[node.target]}'); | |
| 118 } | |
| 119 labelUses[node.target]++; | |
| 120 } | |
| 121 | |
| 122 visitContinue(Continue node) { | |
| 123 if (!label2declaration.containsKey(node.target)) { | |
| 124 error('Continue to label that is not in scope'); | |
| 125 } | |
| 126 if (label2declaration[node.target] is! Loop) { | |
| 127 error('Continue to non-loop statement ${label2declaration[node.target]}'); | |
| 128 } | |
| 129 labelUses[node.target]++; | |
| 130 } | |
| 131 | |
| 132 void checkBody(FunctionDefinition node) { | |
| 133 node.parameters.forEach(declare); | |
| 134 visitStatement(node.body); | |
| 135 node.parameters.forEach(undeclare); | |
| 136 } | |
| 137 | |
| 138 dynamic error(String message) { | |
| 139 throw 'Tree IR integrity violation in ${topLevelNode.element}:\n$message'; | |
| 140 } | |
| 141 | |
| 142 void check(FunctionDefinition node) { | |
| 143 topLevelNode = node; | |
| 144 checkBody(node); | |
| 145 | |
| 146 // Verify reference counters for all variables. | |
| 147 List<Variable> seenVariables = new List<Variable>(); | |
| 148 seenVariables.addAll(varReads.keys); | |
| 149 seenVariables.addAll(varWrites.keys); | |
| 150 for (Variable variable in seenVariables) { | |
| 151 int reads = varReads.putIfAbsent(variable, () => 0); | |
| 152 int writes = varWrites.putIfAbsent(variable, () => 0); | |
| 153 if (reads != variable.readCount || writes != variable.writeCount) { | |
| 154 error('Invalid reference count for $variable:\n' | |
| 155 '- Variable has $reads reads and $writes writes\n' | |
| 156 '- Reference count is ${variable.readCount} reads and ' | |
| 157 '${variable.writeCount} writes'); | |
| 158 } | |
| 159 } | |
| 160 } | |
| 161 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
