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"""Utility functions for reading and manipulating Emboss IR.""" 16 17import operator 18 19from compiler.util import ir_data 20from compiler.util import ir_data_utils 21 22 23_FIXED_SIZE_ATTRIBUTE = "fixed_size_in_bits" 24 25 26def get_attribute(attribute_list, name): 27 """Finds name in attribute_list and returns a AttributeValue or None.""" 28 if not attribute_list: 29 return None 30 attribute_value = None 31 for attr in attribute_list: 32 if attr.name.text == name and not attr.is_default: 33 assert attribute_value is None, 'Duplicate attribute "{}".'.format(name) 34 attribute_value = attr.value 35 return attribute_value 36 37 38def get_boolean_attribute(attribute_list, name, default_value=None): 39 """Returns the boolean value of an attribute, if any, or default_value. 40 41 Arguments: 42 attribute_list: A list of attributes to search. 43 name: The name of the desired attribute. 44 default_value: A value to return if name is not found in attribute_list, 45 or the attribute does not have a boolean value. 46 47 Returns: 48 The boolean value of the requested attribute, or default_value if the 49 requested attribute is not found or has a non-boolean value. 50 """ 51 attribute_value = get_attribute(attribute_list, name) 52 if (not attribute_value or 53 not attribute_value.expression.HasField("boolean_constant")): 54 return default_value 55 return attribute_value.expression.boolean_constant.value 56 57 58def get_integer_attribute(attribute_list, name, default_value=None): 59 """Returns the integer value of an attribute, if any, or default_value. 60 61 Arguments: 62 attribute_list: A list of attributes to search. 63 name: The name of the desired attribute. 64 default_value: A value to return if name is not found in attribute_list, 65 or the attribute does not have an integer value. 66 67 Returns: 68 The integer value of the requested attribute, or default_value if the 69 requested attribute is not found or has a non-integer value. 70 """ 71 attribute_value = get_attribute(attribute_list, name) 72 if (not attribute_value or 73 attribute_value.expression.type.WhichOneof("type") != "integer" or 74 not is_constant(attribute_value.expression)): 75 return default_value 76 return constant_value(attribute_value.expression) 77 78 79def is_constant(expression, bindings=None): 80 return constant_value(expression, bindings) is not None 81 82 83def is_constant_type(expression_type): 84 """Returns True if expression_type is inhabited by a single value.""" 85 expression_type = ir_data_utils.reader(expression_type) 86 return (expression_type.integer.modulus == "infinity" or 87 expression_type.boolean.HasField("value") or 88 expression_type.enumeration.HasField("value")) 89 90 91def constant_value(expression, bindings=None): 92 """Evaluates expression with the given bindings.""" 93 if expression is None: 94 return None 95 expression = ir_data_utils.reader(expression) 96 if expression.WhichOneof("expression") == "constant": 97 return int(expression.constant.value or 0) 98 elif expression.WhichOneof("expression") == "constant_reference": 99 # We can't look up the constant reference without the IR, but by the time 100 # constant_value is called, the actual values should have been propagated to 101 # the type information. 102 if expression.type.WhichOneof("type") == "integer": 103 assert expression.type.integer.modulus == "infinity" 104 return int(expression.type.integer.modular_value) 105 elif expression.type.WhichOneof("type") == "boolean": 106 assert expression.type.boolean.HasField("value") 107 return expression.type.boolean.value 108 elif expression.type.WhichOneof("type") == "enumeration": 109 assert expression.type.enumeration.HasField("value") 110 return int(expression.type.enumeration.value) 111 else: 112 assert False, "Unexpected expression type {}".format( 113 expression.type.WhichOneof("type")) 114 elif expression.WhichOneof("expression") == "function": 115 return _constant_value_of_function(expression.function, bindings) 116 elif expression.WhichOneof("expression") == "field_reference": 117 return None 118 elif expression.WhichOneof("expression") == "boolean_constant": 119 return expression.boolean_constant.value 120 elif expression.WhichOneof("expression") == "builtin_reference": 121 name = expression.builtin_reference.canonical_name.object_path[0] 122 if bindings and name in bindings: 123 return bindings[name] 124 else: 125 return None 126 elif expression.WhichOneof("expression") is None: 127 return None 128 else: 129 assert False, "Unexpected expression kind {}".format( 130 expression.WhichOneof("expression")) 131 132 133def _constant_value_of_function(function, bindings): 134 """Returns the constant value of evaluating `function`, or None.""" 135 values = [constant_value(arg, bindings) for arg in function.args] 136 # Expressions like `$is_statically_sized && 1 <= $static_size_in_bits <= 64` 137 # should return False, not None, if `$is_statically_sized` is false, even 138 # though `$static_size_in_bits` is unknown. 139 # 140 # The easiest way to allow this is to use a three-way logic chart for each; 141 # specifically: 142 # 143 # AND: True False Unknown 144 # +-------------------------- 145 # True | True False Unknown 146 # False | False False False 147 # Unknown | Unknown False Unknown 148 # 149 # OR: True False Unknown 150 # +-------------------------- 151 # True | True True True 152 # False | True False Unknown 153 # Unknown | True Unknown Unknown 154 # 155 # This raises the question of just how many constant-from-nonconstant 156 # expressions Emboss should support. There are, after all, a vast number of 157 # constant expression patterns built from non-constant subexpressions, such as 158 # `0 * X` or `X == X` or `3 * X == X + X + X`. I (bolms@) am not implementing 159 # any further special cases because I do not see any practical use for them. 160 if function.function == ir_data.FunctionMapping.UNKNOWN: 161 return None 162 if function.function == ir_data.FunctionMapping.AND: 163 if any(value is False for value in values): 164 return False 165 elif any(value is None for value in values): 166 return None 167 else: 168 return True 169 elif function.function == ir_data.FunctionMapping.OR: 170 if any(value is True for value in values): 171 return True 172 elif any(value is None for value in values): 173 return None 174 else: 175 return False 176 elif function.function == ir_data.FunctionMapping.CHOICE: 177 if values[0] is None: 178 return None 179 else: 180 return values[1] if values[0] else values[2] 181 # Other than the logical operators and choice operator, the result of any 182 # function on an unknown value is, itself, considered unknown. 183 if any(value is None for value in values): 184 return None 185 functions = { 186 ir_data.FunctionMapping.ADDITION: operator.add, 187 ir_data.FunctionMapping.SUBTRACTION: operator.sub, 188 ir_data.FunctionMapping.MULTIPLICATION: operator.mul, 189 ir_data.FunctionMapping.EQUALITY: operator.eq, 190 ir_data.FunctionMapping.INEQUALITY: operator.ne, 191 ir_data.FunctionMapping.LESS: operator.lt, 192 ir_data.FunctionMapping.LESS_OR_EQUAL: operator.le, 193 ir_data.FunctionMapping.GREATER: operator.gt, 194 ir_data.FunctionMapping.GREATER_OR_EQUAL: operator.ge, 195 # Python's max([1, 2]) == 2; max(1, 2) == 2; max([1]) == 1; but max(1) 196 # throws a TypeError ("'int' object is not iterable"). 197 ir_data.FunctionMapping.MAXIMUM: lambda *x: max(x), 198 } 199 return functions[function.function](*values) 200 201 202def _hashable_form_of_name(name): 203 return (name.module_file,) + tuple(name.object_path) 204 205 206def hashable_form_of_reference(reference): 207 """Returns a representation of reference that can be used as a dict key. 208 209 Arguments: 210 reference: An ir_data.Reference or ir_data.NameDefinition. 211 212 Returns: 213 A tuple of the module_file and object_path. 214 """ 215 return _hashable_form_of_name(reference.canonical_name) 216 217 218def hashable_form_of_field_reference(field_reference): 219 """Returns a representation of field_reference that can be used as a dict key. 220 221 Arguments: 222 field_reference: An ir_data.FieldReference 223 224 Returns: 225 A tuple of tuples of the module_files and object_paths. 226 """ 227 return tuple(_hashable_form_of_name(reference.canonical_name) 228 for reference in field_reference.path) 229 230 231def is_array(type_ir): 232 """Returns true if type_ir is an array type.""" 233 return type_ir.HasField("array_type") 234 235 236def _find_path_in_structure_field(path, field): 237 if not path: 238 return field 239 return None 240 241 242def _find_path_in_structure(path, type_definition): 243 for field in type_definition.structure.field: 244 if field.name.name.text == path[0]: 245 return _find_path_in_structure_field(path[1:], field) 246 return None 247 248 249def _find_path_in_enumeration(path, type_definition): 250 if len(path) != 1: 251 return None 252 for value in type_definition.enumeration.value: 253 if value.name.name.text == path[0]: 254 return value 255 return None 256 257 258def _find_path_in_parameters(path, type_definition): 259 if len(path) > 1 or not type_definition.HasField("runtime_parameter"): 260 return None 261 for parameter in type_definition.runtime_parameter: 262 if ir_data_utils.reader(parameter).name.name.text == path[0]: 263 return parameter 264 return None 265 266 267def _find_path_in_type_definition(path, type_definition): 268 """Finds the object with the given path in the given type_definition.""" 269 if not path: 270 return type_definition 271 obj = _find_path_in_parameters(path, type_definition) 272 if obj: 273 return obj 274 if type_definition.HasField("structure"): 275 obj = _find_path_in_structure(path, type_definition) 276 elif type_definition.HasField("enumeration"): 277 obj = _find_path_in_enumeration(path, type_definition) 278 if obj: 279 return obj 280 else: 281 return _find_path_in_type_list(path, type_definition.subtype or []) 282 283 284def _find_path_in_type_list(path, type_list): 285 for type_definition in type_list: 286 if type_definition.name.name.text == path[0]: 287 return _find_path_in_type_definition(path[1:], type_definition) 288 return None 289 290 291def _find_path_in_module(path, module_ir): 292 if not path: 293 return module_ir 294 return _find_path_in_type_list(path, module_ir.type) 295 296 297def find_object_or_none(name, ir): 298 """Finds the object with the given canonical name, if it exists..""" 299 if (isinstance(name, ir_data.Reference) or 300 isinstance(name, ir_data.NameDefinition)): 301 path = _hashable_form_of_name(name.canonical_name) 302 elif isinstance(name, ir_data.CanonicalName): 303 path = _hashable_form_of_name(name) 304 else: 305 path = name 306 307 for module in ir.module: 308 if module.source_file_name == path[0]: 309 return _find_path_in_module(path[1:], module) 310 311 return None 312 313 314def find_object(name, ir): 315 """Finds the IR of the type, field, or value with the given canonical name.""" 316 result = find_object_or_none(name, ir) 317 assert result is not None, "Bad reference {}".format(name) 318 return result 319 320 321def find_parent_object(name, ir): 322 """Finds the parent object of the object with the given canonical name.""" 323 if (isinstance(name, ir_data.Reference) or 324 isinstance(name, ir_data.NameDefinition)): 325 path = _hashable_form_of_name(name.canonical_name) 326 elif isinstance(name, ir_data.CanonicalName): 327 path = _hashable_form_of_name(name) 328 else: 329 path = name 330 return find_object(path[:-1], ir) 331 332 333def get_base_type(type_ir): 334 """Returns the base type of the given type. 335 336 Arguments: 337 type_ir: IR of a type reference. 338 339 Returns: 340 If type_ir corresponds to an atomic type (like "UInt"), returns type_ir. If 341 type_ir corresponds to an array type (like "UInt:8[12]" or "Square[8][8]"), 342 returns the type after stripping off the array types ("UInt" or "Square"). 343 """ 344 while type_ir.HasField("array_type"): 345 type_ir = type_ir.array_type.base_type 346 assert type_ir.HasField("atomic_type"), ( 347 "Unknown kind of type {}".format(type_ir)) 348 return type_ir 349 350 351def fixed_size_of_type_in_bits(type_ir, ir): 352 """Returns the fixed, known size for the given type, in bits, or None. 353 354 Arguments: 355 type_ir: The IR of a type. 356 ir: A complete IR, used to resolve references to types. 357 358 Returns: 359 size if the size of the type can be determined, otherwise None. 360 """ 361 array_multiplier = 1 362 while type_ir.HasField("array_type"): 363 if type_ir.array_type.WhichOneof("size") == "automatic": 364 return None 365 else: 366 assert type_ir.array_type.WhichOneof("size") == "element_count", ( 367 'Expected array size to be "automatic" or "element_count".') 368 element_count = type_ir.array_type.element_count 369 if not is_constant(element_count): 370 return None 371 else: 372 array_multiplier *= constant_value(element_count) 373 assert not type_ir.HasField("size_in_bits"), ( 374 "TODO(bolms): implement explicitly-sized arrays") 375 type_ir = type_ir.array_type.base_type 376 assert type_ir.HasField("atomic_type"), "Unexpected type!" 377 if type_ir.HasField("size_in_bits"): 378 size = constant_value(type_ir.size_in_bits) 379 else: 380 type_definition = find_object(type_ir.atomic_type.reference, ir) 381 size_attr = get_attribute(type_definition.attribute, _FIXED_SIZE_ATTRIBUTE) 382 if not size_attr: 383 return None 384 size = constant_value(size_attr.expression) 385 return size * array_multiplier 386 387 388def field_is_virtual(field_ir): 389 """Returns true if the field is virtual.""" 390 # TODO(bolms): Should there be a more explicit indicator that a field is 391 # virtual? 392 return not field_ir.HasField("location") 393 394 395def field_is_read_only(field_ir): 396 """Returns true if the field is read-only.""" 397 # For now, all virtual fields are read-only, and no non-virtual fields are 398 # read-only. 399 return ir_data_utils.reader(field_ir).write_method.read_only 400