Appearance
| 1 | namespace IR.Program is | |
| 2 | use Collections.LIST | |
| 3 | use Collections.MAP | |
| 4 | use Collections.SET | |
| 5 | ||
| 6 | use Source.LOCATION | |
| 7 | ||
| 8 | use Semantic.Symbols.Classy | |
| 9 | use Semantic.Symbols.Function | |
| 10 | ||
| 11 | /// What finding a program's reach needs from the target that lowers it. | |
| 12 | trait DiscoveryTarget open is | |
| 13 | /// Follows `instance`'s body far enough to find what it reaches: the | |
| 14 | /// functions it calls, the classes it creates or tests for, and the | |
| 15 | /// methods it dispatches on, each recorded on the plan's worklist, | |
| 16 | /// class set and dispatched methods. Nothing it produces is kept. | |
| 17 | reach(instance: FUNCTION_INSTANCE) | |
| 18 | ||
| 19 | /// Whether a value of `type` can exist: a box only where something | |
| 20 | /// boxes a value in it. | |
| 21 | is_instantiated(type: CLASS_INSTANCE) -> bool | |
| 22 | ||
| 23 | /// Called once for each class found to be instantiated, before its | |
| 24 | /// dispatched methods are reached. | |
| 25 | note_instantiated(type: CLASS_INSTANCE) | |
| 26 | ||
| 27 | /// Reports a construct the target cannot compile, declared at | |
| 28 | /// `location`. | |
| 29 | report(location: LOCATION, construct: string) | |
| 30 | si | |
| 31 | ||
| 32 | /// What a whole program reaches: the function instances to compile, the | |
| 33 | /// classes they use, and the methods they dispatch on, found to a fixed | |
| 34 | /// point from the entry point or, for a library, from every function | |
| 35 | /// that is not generic. | |
| 36 | /// | |
| 37 | /// Following a body finds the functions it calls and the classes it | |
| 38 | /// uses. A class found adds the types its fields hold, since the fields | |
| 39 | /// are laid out wherever the class is, and every instantiated class adds | |
| 40 | /// its implementations of the methods something dispatches on, since | |
| 41 | /// dispatch can reach them. An array type adds every method, since the | |
| 42 | /// trait table reaches them at the element type. | |
| 43 | class PROGRAM_PLAN is | |
| 44 | _classes: CLASS_SET | |
| 45 | _functions: FUNCTION_WORKLIST | |
| 46 | _dispatched: DISPATCHED_METHODS | |
| 47 | _display: DISPLAY_PLAN? | |
| 48 | _methods: MAP[Classy, LIST[Function]] | |
| 49 | ||
| 50 | /// A plan over the bodies `bodies` the program compiles. | |
| 51 | /// | |
| 52 | /// - classes: the classes found, which `reach` adds to | |
| 53 | /// - functions: the worklist of instances to compile, which `reach` | |
| 54 | /// adds to | |
| 55 | /// - dispatched: the methods calls dispatch on, which `reach` adds to | |
| 56 | /// - display: which types get a displayer, and what each calls, or null | |
| 57 | /// where the target writes no displayers | |
| 58 | /// - bodies: every function the program has a body for | |
| 59 | init( | |
| 60 | classes: CLASS_SET, | |
| 61 | functions: FUNCTION_WORKLIST, | |
| 62 | dispatched: DISPATCHED_METHODS, | |
| 63 | display: DISPLAY_PLAN?, | |
| 64 | bodies: Collections.Iterable[Function] | |
| 65 | ) is | |
| 66 | _classes = classes | |
| 67 | _functions = functions | |
| 68 | _dispatched = dispatched | |
| 69 | _display = display | |
| 70 | ||
| 71 | _methods = MAP[Classy, LIST[Function]]() | |
| 72 | ||
| 73 | for function in bodies do | |
| 74 | if let owner = FUNCTION_BODIES.class_of_body(function) then | |
| 75 | if !_methods.contains_key(owner) then | |
| 76 | _methods[owner] = LIST[Function]() | |
| 77 | fi | |
| 78 | ||
| 79 | _methods[owner].add(function) | |
| 80 | fi | |
| 81 | od | |
| 82 | si | |
| 83 | ||
| 84 | /// The classes the program uses. | |
| 85 | classes: CLASS_SET => _classes | |
| 86 | ||
| 87 | /// The function instances the program compiles. | |
| 88 | functions: FUNCTION_WORKLIST => _functions | |
| 89 | ||
| 90 | /// The methods calls dispatch on. | |
| 91 | dispatched: DISPATCHED_METHODS => _dispatched | |
| 92 | ||
| 93 | /// Finds everything the program reaches from what is already on the | |
| 94 | /// worklist, through `target`, until nothing new is found. A generic | |
| 95 | /// class instantiated more often, or at deeper type arguments, than | |
| 96 | /// `INSTANTIATION_LIMITS` allows is reported once, and the types of | |
| 97 | /// its fields are left out. | |
| 98 | discover(target: DiscoveryTarget) is | |
| 99 | let too_deep = SET[Classy]() | |
| 100 | let instantiations = MAP[Classy, int]() | |
| 101 | let instantiated = SET[CLASS_INSTANCE]() | |
| 102 | ||
| 103 | let is_done mut = false | |
| 104 | ||
| 105 | while !is_done do | |
| 106 | is_done = true | |
| 107 | ||
| 108 | while let instance = _functions.next() do | |
| 109 | is_done = false | |
| 110 | ||
| 111 | target.reach(instance) | |
| 112 | od | |
| 113 | ||
| 114 | for type in _classes.take_new_classes() do | |
| 115 | is_done = false | |
| 116 | ||
| 117 | let found mut = 0 | |
| 118 | ||
| 119 | instantiations.try_get_value(type.definition, found ref) | |
| 120 | instantiations[type.definition] = found + 1 | |
| 121 | ||
| 122 | if type.definition.is_generic /\ (found >= INSTANTIATION_LIMITS.MAXIMUM_INSTANTIATIONS \/ TYPE_MAPS.depth(type.arguments) > INSTANTIATION_LIMITS.MAXIMUM_TYPE_ARGUMENT_DEPTH) then | |
| 123 | // A class whose methods or fields instantiate it at | |
| 124 | // deeper and deeper type arguments would be compiled | |
| 125 | // without end, so its fields add nothing further. | |
| 126 | if too_deep.add(type.definition) then | |
| 127 | if found >= INSTANTIATION_LIMITS.MAXIMUM_INSTANTIATIONS then | |
| 128 | target.report(type.definition.location, "a generic class instantiated at more than {INSTANTIATION_LIMITS.MAXIMUM_INSTANTIATIONS} type arguments") | |
| 129 | else | |
| 130 | target.report(type.definition.location, "a generic class that instantiates itself at ever deeper type arguments") | |
| 131 | fi | |
| 132 | fi | |
| 133 | ||
| 134 | _classes.leave_field_types(type) | |
| 135 | else | |
| 136 | _classes.add_field_types(type) | |
| 137 | fi | |
| 138 | od | |
| 139 | ||
| 140 | let count = _functions.count | |
| 141 | let instantiated_count = instantiated.count | |
| 142 | ||
| 143 | for type in _classes.classes_and_arrays do | |
| 144 | if !target.is_instantiated(type) then | |
| 145 | continue | |
| 146 | fi | |
| 147 | ||
| 148 | if instantiated.add(type) then | |
| 149 | target.note_instantiated(type) | |
| 150 | fi | |
| 151 | ||
| 152 | let class_methods: LIST[Function] mut | |
| 153 | ||
| 154 | if _methods.try_get_value(type.definition, class_methods ref) then | |
| 155 | for method in class_methods do | |
| 156 | if (method.generic_arguments.count == 0 /\ _dispatched.is_dispatched_to(method)) \/ _classes.is_array(type) then | |
| 157 | _functions.add(FUNCTION_INSTANCE(method, type.type_map)) | |
| 158 | fi | |
| 159 | od | |
| 160 | fi | |
| 161 | od | |
| 162 | ||
| 163 | // A trait's default method is reached through the table from | |
| 164 | // any implementor that does not override it. | |
| 165 | for (definition, class_methods) in _methods do | |
| 166 | if definition.is_trait /\ !definition.is_generic then | |
| 167 | for method in class_methods do | |
| 168 | if _dispatched.is_dispatched_to(method) then | |
| 169 | _functions.add(method) | |
| 170 | fi | |
| 171 | od | |
| 172 | fi | |
| 173 | od | |
| 174 | ||
| 175 | if let display = _display, helpers = display.helpers then | |
| 176 | for type in _classes.classes_and_arrays do | |
| 177 | for function in display.calls(type, helpers) do | |
| 178 | _functions.add(function) | |
| 179 | od | |
| 180 | od | |
| 181 | fi | |
| 182 | ||
| 183 | if _functions.count != count \/ instantiated.count != instantiated_count then | |
| 184 | is_done = false | |
| 185 | fi | |
| 186 | od | |
| 187 | si | |
| 188 | si | |
| 189 | si |