1# Copyright 2019 Google LLC 2# 3# Licensed under the Apache License, Version 2.0 (the "License"); 4# you may not use this file except in compliance with the License. 5# You may obtain a copy of the License at 6# 7# https://www.apache.org/licenses/LICENSE-2.0 8# 9# Unless required by applicable law or agreed to in writing, software 10# distributed under the License is distributed on an "AS IS" BASIS, 11# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12# See the License for the specific language governing permissions and 13# limitations under the License. 14 15"""Checks for dependency cycles in Emboss IR.""" 16 17from compiler.util import error 18from compiler.util import ir_data 19from compiler.util import ir_util 20from compiler.util import traverse_ir 21 22 23def _add_reference_to_dependencies(reference, dependencies, name, 24 source_file_name, errors): 25 if reference.canonical_name.object_path[0] in {"$is_statically_sized", 26 "$static_size_in_bits", 27 "$next"}: 28 # This error is a bit opaque, but given that the compiler used to crash on 29 # this case -- for a couple of years -- and no one complained, it seems 30 # safe to assume that this is a rare error. 31 errors.append([ 32 error.error(source_file_name, reference.source_location, 33 "Keyword `" + reference.canonical_name.object_path[0] + 34 "` may not be used in this context."), 35 ]) 36 return 37 dependencies[name] |= {ir_util.hashable_form_of_reference(reference)} 38 39 40def _add_field_reference_to_dependencies(reference, dependencies, name): 41 dependencies[name] |= {ir_util.hashable_form_of_reference(reference.path[0])} 42 43 44def _add_name_to_dependencies(proto, dependencies): 45 name = ir_util.hashable_form_of_reference(proto.name) 46 dependencies.setdefault(name, set()) 47 return {"name": name} 48 49 50def _find_dependencies(ir): 51 """Constructs a dependency graph for the entire IR.""" 52 dependencies = {} 53 errors = [] 54 traverse_ir.fast_traverse_ir_top_down( 55 ir, [ir_data.Reference], _add_reference_to_dependencies, 56 # TODO(bolms): Add handling for references inside of attributes, once 57 # there are attributes with non-constant values. 58 skip_descendants_of={ 59 ir_data.AtomicType, ir_data.Attribute, ir_data.FieldReference 60 }, 61 incidental_actions={ 62 ir_data.Field: _add_name_to_dependencies, 63 ir_data.EnumValue: _add_name_to_dependencies, 64 ir_data.RuntimeParameter: _add_name_to_dependencies, 65 }, 66 parameters={ 67 "dependencies": dependencies, 68 "errors": errors, 69 }) 70 traverse_ir.fast_traverse_ir_top_down( 71 ir, [ir_data.FieldReference], _add_field_reference_to_dependencies, 72 skip_descendants_of={ir_data.Attribute}, 73 incidental_actions={ 74 ir_data.Field: _add_name_to_dependencies, 75 ir_data.EnumValue: _add_name_to_dependencies, 76 ir_data.RuntimeParameter: _add_name_to_dependencies, 77 }, 78 parameters={"dependencies": dependencies}) 79 return dependencies, errors 80 81 82def _find_dependency_ordering_for_fields_in_structure( 83 structure, type_definition, dependencies): 84 """Populates structure.fields_in_dependency_order.""" 85 # For fields which appear before their dependencies in the original source 86 # text, this algorithm moves them to immediately after their dependencies. 87 # 88 # This is one of many possible schemes for constructing a dependency ordering; 89 # it has the advantage that all of the generated fields (e.g., $size_in_bytes) 90 # stay at the end of the ordering, which makes testing easier. 91 order = [] 92 added = set() 93 for parameter in type_definition.runtime_parameter: 94 added.add(ir_util.hashable_form_of_reference(parameter.name)) 95 needed = list(range(len(structure.field))) 96 while True: 97 for i in range(len(needed)): 98 field_number = needed[i] 99 field = ir_util.hashable_form_of_reference( 100 structure.field[field_number].name) 101 assert field in dependencies, "dependencies = {}".format(dependencies) 102 if all(dependency in added for dependency in dependencies[field]): 103 order.append(field_number) 104 added.add(field) 105 del needed[i] 106 break 107 else: 108 break 109 # If a non-local-field dependency were in dependencies[field], then not all 110 # fields would be added to the dependency ordering. This shouldn't happen. 111 assert len(order) == len(structure.field), ( 112 "order: {}\nlen(structure.field: {})".format(order, len(structure.field))) 113 del structure.fields_in_dependency_order[:] 114 structure.fields_in_dependency_order.extend(order) 115 116 117def _find_dependency_ordering_for_fields(ir): 118 """Populates the fields_in_dependency_order fields throughout ir.""" 119 dependencies = {} 120 # TODO(bolms): This duplicates work in _find_dependencies that could be 121 # shared. 122 traverse_ir.fast_traverse_ir_top_down( 123 ir, [ir_data.FieldReference], _add_field_reference_to_dependencies, 124 skip_descendants_of={ir_data.Attribute}, 125 incidental_actions={ 126 ir_data.Field: _add_name_to_dependencies, 127 ir_data.EnumValue: _add_name_to_dependencies, 128 ir_data.RuntimeParameter: _add_name_to_dependencies, 129 }, 130 parameters={"dependencies": dependencies}) 131 traverse_ir.fast_traverse_ir_top_down( 132 ir, [ir_data.Structure], 133 _find_dependency_ordering_for_fields_in_structure, 134 parameters={"dependencies": dependencies}) 135 136 137def _find_module_import_dependencies(ir): 138 """Constructs a dependency graph of module imports.""" 139 dependencies = {} 140 for module in ir.module: 141 foreign_imports = set() 142 for foreign_import in module.foreign_import: 143 # The prelude gets an automatic self-import that shouldn't cause any 144 # problems. No other self-imports are allowed, however. 145 if foreign_import.file_name.text or module.source_file_name: 146 foreign_imports |= {(foreign_import.file_name.text,)} 147 dependencies[module.source_file_name,] = foreign_imports 148 return dependencies 149 150 151def _find_cycles(graph): 152 """Finds cycles in graph. 153 154 The graph does not need to be fully connected. 155 156 Arguments: 157 graph: A dictionary whose keys are node labels. Values are sets of node 158 labels, representing edges from the key node to the value nodes. 159 160 Returns: 161 A set of sets of nodes which form strongly-connected components (subgraphs 162 where every node is directly or indirectly reachable from every other node). 163 No node will be included in more than one strongly-connected component, by 164 definition. Strongly-connected components of size 1, where the node in the 165 component does not have a self-edge, are not included in the result. 166 167 Note that a strongly-connected component may have a more complex structure 168 than a single loop. For example: 169 170 +-- A <-+ +-> B --+ 171 | | | | 172 v C v 173 D ^ ^ E 174 | | | | 175 +-> F --+ +-- G <-+ 176 """ 177 # This uses Tarjan's strongly-connected components algorithm, as described by 178 # Wikipedia. This is a depth-first traversal of the graph with a node stack 179 # that is independent of the call stack; nodes are added to the stack when 180 # they are first encountered, but not removed until all nodes they can reach 181 # have been checked. 182 next_index = [0] 183 node_indices = {} 184 node_lowlinks = {} 185 nodes_on_stack = set() 186 stack = [] 187 nontrivial_components = set() 188 189 def strong_connect(node): 190 """Implements the STRONGCONNECT routine of Tarjan's algorithm.""" 191 node_indices[node] = next_index[0] 192 node_lowlinks[node] = next_index[0] 193 next_index[0] += 1 194 stack.append(node) 195 nodes_on_stack.add(node) 196 197 for destination_node in graph[node]: 198 if destination_node not in node_indices: 199 strong_connect(destination_node) 200 node_lowlinks[node] = min(node_lowlinks[node], 201 node_lowlinks[destination_node]) 202 elif destination_node in nodes_on_stack: 203 node_lowlinks[node] = min(node_lowlinks[node], 204 node_indices[destination_node]) 205 206 strongly_connected_component = [] 207 if node_lowlinks[node] == node_indices[node]: 208 while True: 209 popped_node = stack.pop() 210 nodes_on_stack.remove(popped_node) 211 strongly_connected_component.append(popped_node) 212 if popped_node == node: 213 break 214 if (len(strongly_connected_component) > 1 or 215 strongly_connected_component[0] in 216 graph[strongly_connected_component[0]]): 217 nontrivial_components.add(frozenset(strongly_connected_component)) 218 219 for node in graph: 220 if node not in node_indices: 221 strong_connect(node) 222 return nontrivial_components 223 224 225def _find_object_dependency_cycles(ir): 226 """Finds dependency cycles in types in the ir.""" 227 dependencies, find_dependency_errors = _find_dependencies(ir) 228 if find_dependency_errors: 229 return find_dependency_errors 230 errors = [] 231 cycles = _find_cycles(dict(dependencies)) 232 for cycle in cycles: 233 # TODO(bolms): This lists the entire strongly-connected component in a 234 # fairly arbitrary order. This is simple, and handles components that 235 # aren't simple cycles, but may not be the most user-friendly way to 236 # present this information. 237 cycle_list = sorted(list(cycle)) 238 node_object = ir_util.find_object(cycle_list[0], ir) 239 error_group = [ 240 error.error(cycle_list[0][0], node_object.source_location, 241 "Dependency cycle\n" + node_object.name.name.text) 242 ] 243 for node in cycle_list[1:]: 244 node_object = ir_util.find_object(node, ir) 245 error_group.append(error.note(node[0], node_object.source_location, 246 node_object.name.name.text)) 247 errors.append(error_group) 248 return errors 249 250 251def _find_module_dependency_cycles(ir): 252 """Finds dependency cycles in modules in the ir.""" 253 dependencies = _find_module_import_dependencies(ir) 254 cycles = _find_cycles(dict(dependencies)) 255 errors = [] 256 for cycle in cycles: 257 cycle_list = sorted(list(cycle)) 258 module = ir_util.find_object(cycle_list[0], ir) 259 error_group = [ 260 error.error(cycle_list[0][0], module.source_location, 261 "Import dependency cycle\n" + module.source_file_name) 262 ] 263 for module_name in cycle_list[1:]: 264 module = ir_util.find_object(module_name, ir) 265 error_group.append(error.note(module_name[0], module.source_location, 266 module.source_file_name)) 267 errors.append(error_group) 268 return errors 269 270 271def find_dependency_cycles(ir): 272 """Finds any dependency cycles in the ir.""" 273 errors = _find_module_dependency_cycles(ir) 274 return errors + _find_object_dependency_cycles(ir) 275 276 277def set_dependency_order(ir): 278 """Sets the fields_in_dependency_order member of Structures.""" 279 _find_dependency_ordering_for_fields(ir) 280 return [] 281