| # Copyright 2019 Google LLC | |
| # | |
| # Licensed under the Apache License, Version 2.0 (the "License"); | |
| # you may not use this file except in compliance with the License. | |
| # You may obtain a copy of the License at | |
| # | |
| # https://www.apache.org/licenses/LICENSE-2.0 | |
| # | |
| # Unless required by applicable law or agreed to in writing, software | |
| # distributed under the License is distributed on an "AS IS" BASIS, | |
| # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
| # See the License for the specific language governing permissions and | |
| # limitations under the License. | |
| """Routines for fully traversing an IR.""" | |
| import inspect | |
| from compiler.util import ir_pb2 | |
| def _call_with_optional_args(function, positional_arg, keyword_args): | |
| """Calls function with whatever keyword_args it will accept.""" | |
| argspec = inspect.getfullargspec(function) | |
| if argspec.varkw: | |
| # If the function accepts a kwargs parameter, then it will accept all | |
| # arguments. | |
| # Note: this isn't technically true if one of the keyword arguments has the | |
| # same name as one of the positional arguments. | |
| return function(positional_arg, **keyword_args) | |
| else: | |
| ok_arguments = {} | |
| for name in keyword_args: | |
| if name in argspec.args[1:] or name in argspec.kwonlyargs: | |
| ok_arguments[name] = keyword_args[name] | |
| for name in argspec.args[1:len(argspec.args) - len(argspec.defaults or [])]: | |
| assert name in ok_arguments, ( | |
| "Attempting to call '{}'; missing '{}' (have '{!r}')".format( | |
| function.__name__, name, list(keyword_args.keys()))) | |
| return function(positional_arg, **ok_arguments) | |
| def _fast_traverse_proto_top_down(proto, incidental_actions, pattern, | |
| skip_descendants_of, action, parameters): | |
| """Traverses an IR, calling `action` on some nodes.""" | |
| # Parameters are scoped to the branch of the tree, so make a copy here, before | |
| # any action or incidental_action can update them. | |
| parameters = parameters.copy() | |
| # If there is an incidental action for this node type, run it. | |
| if type(proto) in incidental_actions: # pylint: disable=unidiomatic-typecheck | |
| for incidental_action in incidental_actions[type(proto)]: | |
| parameters.update(_call_with_optional_args( | |
| incidental_action, proto, parameters) or {}) | |
| # If we are at the end of pattern, check to see if we should call action. | |
| if len(pattern) == 1: | |
| new_pattern = pattern | |
| if pattern[0] == type(proto): | |
| parameters.update( | |
| _call_with_optional_args(action, proto, parameters) or {}) | |
| else: | |
| # Otherwise, if this node's type matches the head of pattern, recurse with | |
| # the tail of the pattern. | |
| if pattern[0] == type(proto): | |
| new_pattern = pattern[1:] | |
| else: | |
| new_pattern = pattern | |
| # If the current node's type is one of the types whose branch should be | |
| # skipped, then bail. This has to happen after `action` is called, because | |
| # clients rely on being able to, e.g., get a callback for the "root" | |
| # Expression without getting callbacks for every sub-Expression. | |
| # pylint: disable=unidiomatic-typecheck | |
| if type(proto) in skip_descendants_of: | |
| return | |
| # Otherwise, recurse. _FIELDS_TO_SCAN_BY_CURRENT_AND_TARGET tells us, given | |
| # the current node's type and the current target type, which fields to check. | |
| singular_fields, repeated_fields = _FIELDS_TO_SCAN_BY_CURRENT_AND_TARGET[ | |
| type(proto), new_pattern[0]] | |
| for member_name in singular_fields: | |
| if proto.HasField(member_name): | |
| _fast_traverse_proto_top_down(getattr(proto, member_name), | |
| incidental_actions, new_pattern, | |
| skip_descendants_of, action, parameters) | |
| for member_name in repeated_fields: | |
| for array_element in getattr(proto, member_name): | |
| _fast_traverse_proto_top_down(array_element, incidental_actions, | |
| new_pattern, skip_descendants_of, action, | |
| parameters) | |
| def _fields_to_scan_by_current_and_target(): | |
| """Generates _FIELDS_TO_SCAN_BY_CURRENT_AND_TARGET.""" | |
| # In order to avoid spending a *lot* of time just walking the IR, this | |
| # function sets up a dict that allows `_fast_traverse_proto_top_down()` to | |
| # skip traversing large portions of the IR, depending on what node types it is | |
| # targeting. | |
| # | |
| # Without this branch culling scheme, the Emboss front end (at time of | |
| # writing) spends roughly 70% (19s out of 31s) of its time just walking the | |
| # IR. With branch culling, that goes down to 6% (0.7s out of 12.2s). | |
| # type_to_fields is a map of types to maps of field names to field types. | |
| # That is, type_to_fields[ir_pb2.Module]["type"] == ir_pb2.TypeDefinition. | |
| type_to_fields = {} | |
| # Later, we need to know which fields are singular and which are repeated, | |
| # because the access methods are not uniform. This maps (type, field_name) | |
| # tuples to descriptor labels: type_fields_to_cardinality[ir_pb2.Module, | |
| # "type"] == ir_pb2.Repeated. | |
| type_fields_to_cardinality = {} | |
| # Fill out the above maps by recursively walking the IR type tree, starting | |
| # from the root. | |
| types_to_check = [ir_pb2.EmbossIr] | |
| while types_to_check: | |
| type_to_check = types_to_check.pop() | |
| if type_to_check in type_to_fields: | |
| continue | |
| fields = {} | |
| for field_name, field_type in type_to_check.field_specs.items(): | |
| if issubclass(field_type.type, ir_pb2.Message): | |
| fields[field_name] = field_type.type | |
| types_to_check.append(field_type.type) | |
| type_fields_to_cardinality[type_to_check, field_name] = ( | |
| field_type.__class__) | |
| type_to_fields[type_to_check] = fields | |
| # type_to_descendant_types is a map of all types that can be reached from a | |
| # particular type. After the setup, type_to_descendant_types[ir_pb2.EmbossIr] | |
| # == set(<all types>) and type_to_descendant_types[ir_pb2.Reference] == | |
| # {ir_pb2.CanonicalName, ir_pb2.Word, ir_pb2.Location} and | |
| # type_to_descendant_types[ir_pb2.Word] == set(). | |
| # | |
| # The while loop basically ors in the known descendants of each known | |
| # descendant of each type until the dict stops changing, which is a bit | |
| # brute-force, but in practice only iterates a few times. | |
| type_to_descendant_types = {} | |
| for parent_type, field_map in type_to_fields.items(): | |
| type_to_descendant_types[parent_type] = set(field_map.values()) | |
| previous_map = {} | |
| while type_to_descendant_types != previous_map: | |
| # In order to check the previous iteration against the current iteration, it | |
| # is necessary to make a two-level copy. Otherwise, the updates to the | |
| # values will also update previous_map's values, which causes the loop to | |
| # exit prematurely. | |
| previous_map = {k: set(v) for k, v in type_to_descendant_types.items()} | |
| for ancestor_type, descendents in previous_map.items(): | |
| for descendent in descendents: | |
| type_to_descendant_types[ancestor_type] |= previous_map[descendent] | |
| # Finally, we have all of the information we need to make the map we really | |
| # want: given a current node type and a target node type, which fields should | |
| # be checked? (This implicitly skips fields that *can't* contain the target | |
| # type.) | |
| fields_to_scan_by_current_and_target = {} | |
| for current_node_type in type_to_fields: | |
| for target_node_type in type_to_fields: | |
| singular_fields_to_scan = [] | |
| repeated_fields_to_scan = [] | |
| for field_name, field_type in type_to_fields[current_node_type].items(): | |
| # If the target node type cannot contain another instance of itself, it | |
| # is still necessary to scan fields that have the actual target type. | |
| if (target_node_type == field_type or | |
| target_node_type in type_to_descendant_types[field_type]): | |
| # Singular and repeated fields go to different lists, so that they can | |
| # be handled separately. | |
| if (type_fields_to_cardinality[current_node_type, field_name] == | |
| ir_pb2.Optional): | |
| singular_fields_to_scan.append(field_name) | |
| else: | |
| repeated_fields_to_scan.append(field_name) | |
| fields_to_scan_by_current_and_target[ | |
| current_node_type, target_node_type] = ( | |
| singular_fields_to_scan, repeated_fields_to_scan) | |
| return fields_to_scan_by_current_and_target | |
| _FIELDS_TO_SCAN_BY_CURRENT_AND_TARGET = _fields_to_scan_by_current_and_target() | |
| def fast_traverse_ir_top_down(ir, pattern, action, incidental_actions=None, | |
| skip_descendants_of=(), parameters=None): | |
| """Traverses an IR from the top down, executing the given actions. | |
| `fast_traverse_ir_top_down` walks the given IR in preorder traversal, | |
| specifically looking for nodes whose path from the root of the tree matches | |
| `pattern`. For every node which matches `pattern`, `action` will be called. | |
| `pattern` is just a list of node types. For example, to execute `print` on | |
| every `ir_pb2.Word` in the IR: | |
| fast_traverse_ir_top_down(ir, [ir_pb2.Word], print) | |
| If more than one type is specified, then each one must be found inside the | |
| previous. For example, to print only the Words inside of import statements: | |
| fast_traverse_ir_top_down(ir, [ir_pb2.Import, ir_pb2.Word], print) | |
| The optional arguments provide additional control. | |
| `skip_descendants_of` is a list of types that should be treated as if they are | |
| leaf nodes when they are encountered. That is, traversal will skip any | |
| nodes with any ancestor node whose type is in `skip_descendants_of`. For | |
| example, to `do_something` only on outermost `Expression`s: | |
| fast_traverse_ir_top_down(ir, [ir_pb2.Expression], do_something, | |
| skip_descendants_of={ir_pb2.Expression}) | |
| `parameters` specifies a dictionary of initial parameters which can be passed | |
| as arguments to `action` and `incidental_actions`. Note that the parameters | |
| can be overridden for parts of the tree by `action` and `incidental_actions`. | |
| Parameters can be used to set an object which may be updated by `action`, such | |
| as a list of errors generated by some check in `action`: | |
| def check_structure(structure, errors): | |
| if structure_is_bad(structure): | |
| errors.append(error_for_structure(structure)) | |
| errors = [] | |
| fast_traverse_ir_top_down(ir, [ir_pb2.Structure], check_structure, | |
| parameters={"errors": errors}) | |
| if errors: | |
| print("Errors: {}".format(errors)) | |
| sys.exit(1) | |
| `incidental_actions` is a map from node types to functions (or tuples of | |
| functions or lists of functions) which should be called on those nodes. | |
| Because `fast_traverse_ir_top_down` may skip branches that can't contain | |
| `pattern`, functions in `incidental_actions` should generally not have any | |
| side effects: instead, they may return a dictionary, which will be used to | |
| override `parameters` for any children of the node they were called on. For | |
| example: | |
| def do_something(expression, field_name=None): | |
| if field_name: | |
| print("Found {} inside {}".format(expression, field_name)) | |
| else: | |
| print("Found {} not in any field".format(expression)) | |
| fast_traverse_ir_top_down( | |
| ir, [ir_pb2.Expression], do_something, | |
| incidental_actions={ir_pb2.Field: lambda f: {"field_name": f.name}}) | |
| (The `action` may also return a dict in the same way.) | |
| A few `incidental_actions` are built into `fast_traverse_ir_top_down`, so | |
| that certain parameters are contextually available with well-known names: | |
| ir: The complete IR (the root ir_pb2.EmbossIr node). | |
| source_file_name: The file name from which the current node was sourced. | |
| type_definition: The most-immediate ancestor type definition. | |
| field: The field containing the current node, if any. | |
| Arguments: | |
| ir: An ir_pb2.Ir object to walk. | |
| pattern: A list of node types to match. | |
| action: A callable, which will be called on nodes matching `pattern`. | |
| incidental_actions: A dict of node types to callables, which can be used to | |
| set new parameters for `action` for part of the IR tree. | |
| skip_descendants_of: A list of types whose children should be skipped when | |
| traversing `ir`. | |
| parameters: A list of top-level parameters. | |
| Returns: | |
| None | |
| """ | |
| all_incidental_actions = { | |
| ir_pb2.EmbossIr: [lambda ir: {"ir": ir}], | |
| ir_pb2.Module: [lambda m: {"source_file_name": m.source_file_name}], | |
| ir_pb2.TypeDefinition: [lambda t: {"type_definition": t}], | |
| ir_pb2.Field: [lambda f: {"field": f}], | |
| } | |
| if incidental_actions: | |
| for key, incidental_action in incidental_actions.items(): | |
| if not isinstance(incidental_action, (list, tuple)): | |
| incidental_action = [incidental_action] | |
| all_incidental_actions.setdefault(key, []).extend(incidental_action) | |
| _fast_traverse_proto_top_down(ir, all_incidental_actions, pattern, | |
| skip_descendants_of, action, parameters or {}) | |
| def fast_traverse_node_top_down(node, pattern, action, incidental_actions=None, | |
| skip_descendants_of=(), parameters=None): | |
| """Traverse a subtree of an IR, executing the given actions. | |
| fast_traverse_node_top_down is like fast_traverse_ir_top_down, except that: | |
| It may be called on a subtree, instead of the top of the IR. | |
| It does not have any built-in incidental actions. | |
| Arguments: | |
| node: An ir_pb2.Ir object to walk. | |
| pattern: A list of node types to match. | |
| action: A callable, which will be called on nodes matching `pattern`. | |
| incidental_actions: A dict of node types to callables, which can be used to | |
| set new parameters for `action` for part of the IR tree. | |
| skip_descendants_of: A list of types whose children should be skipped when | |
| traversing `node`. | |
| parameters: A list of top-level parameters. | |
| Returns: | |
| None | |
| """ | |
| _fast_traverse_proto_top_down(node, incidental_actions or {}, pattern, | |
| skip_descendants_of or {}, action, | |
| parameters or {}) |