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"""Functions for checking expression types.""" 16 17from compiler.front_end import attributes 18from compiler.util import error 19from compiler.util import ir_data 20from compiler.util import ir_data_utils 21from compiler.util import ir_util 22from compiler.util import traverse_ir 23 24 25def _type_check_expression(expression, source_file_name, ir, errors): 26 """Checks and annotates the type of an expression and all subexpressions.""" 27 if ir_data_utils.reader(expression).type.WhichOneof("type"): 28 # This expression has already been type checked. 29 return 30 expression_variety = expression.WhichOneof("expression") 31 if expression_variety == "constant": 32 _type_check_integer_constant(expression) 33 elif expression_variety == "constant_reference": 34 _type_check_constant_reference(expression, source_file_name, ir, errors) 35 elif expression_variety == "function": 36 _type_check_operation(expression, source_file_name, ir, errors) 37 elif expression_variety == "field_reference": 38 _type_check_local_reference(expression, ir, errors) 39 elif expression_variety == "boolean_constant": 40 _type_check_boolean_constant(expression) 41 elif expression_variety == "builtin_reference": 42 _type_check_builtin_reference(expression) 43 else: 44 assert False, "Unknown expression variety {!r}".format(expression_variety) 45 46 47def _annotate_as_integer(expression): 48 ir_data_utils.builder(expression).type.integer.CopyFrom(ir_data.IntegerType()) 49 50 51def _annotate_as_boolean(expression): 52 ir_data_utils.builder(expression).type.boolean.CopyFrom(ir_data.BooleanType()) 53 54 55def _type_check(expression, source_file_name, errors, type_oneof, type_name, 56 expression_name): 57 if ir_data_utils.reader(expression).type.WhichOneof("type") != type_oneof: 58 errors.append([ 59 error.error(source_file_name, expression.source_location, 60 "{} must be {}.".format(expression_name, type_name)) 61 ]) 62 63 64def _type_check_integer(expression, source_file_name, errors, expression_name): 65 _type_check(expression, source_file_name, errors, "integer", 66 "an integer", expression_name) 67 68 69def _type_check_boolean(expression, source_file_name, errors, expression_name): 70 _type_check(expression, source_file_name, errors, "boolean", "a boolean", 71 expression_name) 72 73 74def _kind_check_field_reference(expression, source_file_name, errors, 75 expression_name): 76 if expression.WhichOneof("expression") != "field_reference": 77 errors.append([ 78 error.error(source_file_name, expression.source_location, 79 "{} must be a field.".format(expression_name)) 80 ]) 81 82 83def _type_check_integer_constant(expression): 84 _annotate_as_integer(expression) 85 86 87def _type_check_constant_reference(expression, source_file_name, ir, errors): 88 """Annotates the type of a constant reference.""" 89 referred_name = expression.constant_reference.canonical_name 90 referred_object = ir_util.find_object(referred_name, ir) 91 if isinstance(referred_object, ir_data.EnumValue): 92 ir_data_utils.builder(expression).type.enumeration.name.CopyFrom(expression.constant_reference) 93 del expression.type.enumeration.name.canonical_name.object_path[-1] 94 elif isinstance(referred_object, ir_data.Field): 95 if not ir_util.field_is_virtual(referred_object): 96 errors.append([ 97 error.error(source_file_name, expression.source_location, 98 "Static references to physical fields are not allowed."), 99 error.note(referred_name.module_file, referred_object.source_location, 100 "{} is a physical field.".format( 101 referred_name.object_path[-1])), 102 ]) 103 return 104 _type_check_expression(referred_object.read_transform, 105 referred_name.module_file, ir, errors) 106 ir_data_utils.builder(expression).type.CopyFrom(referred_object.read_transform.type) 107 else: 108 assert False, "Unexpected constant reference type." 109 110 111def _type_check_operation(expression, source_file_name, ir, errors): 112 for arg in expression.function.args: 113 _type_check_expression(arg, source_file_name, ir, errors) 114 function = expression.function.function 115 if function in (ir_data.FunctionMapping.EQUALITY, ir_data.FunctionMapping.INEQUALITY, 116 ir_data.FunctionMapping.LESS, ir_data.FunctionMapping.LESS_OR_EQUAL, 117 ir_data.FunctionMapping.GREATER, ir_data.FunctionMapping.GREATER_OR_EQUAL): 118 _type_check_comparison_operator(expression, source_file_name, errors) 119 elif function == ir_data.FunctionMapping.CHOICE: 120 _type_check_choice_operator(expression, source_file_name, errors) 121 else: 122 _type_check_monomorphic_operator(expression, source_file_name, errors) 123 124 125def _type_check_monomorphic_operator(expression, source_file_name, errors): 126 """Type checks an operator that accepts only one set of argument types.""" 127 args = expression.function.args 128 int_args = _type_check_integer 129 bool_args = _type_check_boolean 130 field_args = _kind_check_field_reference 131 int_result = _annotate_as_integer 132 bool_result = _annotate_as_boolean 133 binary = ("Left argument", "Right argument") 134 n_ary = ("Argument {}".format(n) for n in range(len(args))) 135 functions = { 136 ir_data.FunctionMapping.ADDITION: (int_result, int_args, binary, 2, 2, 137 "operator"), 138 ir_data.FunctionMapping.SUBTRACTION: (int_result, int_args, binary, 2, 2, 139 "operator"), 140 ir_data.FunctionMapping.MULTIPLICATION: (int_result, int_args, binary, 2, 2, 141 "operator"), 142 ir_data.FunctionMapping.AND: (bool_result, bool_args, binary, 2, 2, "operator"), 143 ir_data.FunctionMapping.OR: (bool_result, bool_args, binary, 2, 2, "operator"), 144 ir_data.FunctionMapping.MAXIMUM: (int_result, int_args, n_ary, 1, None, 145 "function"), 146 ir_data.FunctionMapping.PRESENCE: (bool_result, field_args, n_ary, 1, 1, 147 "function"), 148 ir_data.FunctionMapping.UPPER_BOUND: (int_result, int_args, n_ary, 1, 1, 149 "function"), 150 ir_data.FunctionMapping.LOWER_BOUND: (int_result, int_args, n_ary, 1, 1, 151 "function"), 152 } 153 function = expression.function.function 154 (set_result_type, check_arg, arg_names, min_args, max_args, 155 kind) = functions[function] 156 for argument, name in zip(args, arg_names): 157 assert name is not None, "Too many arguments to function!" 158 check_arg(argument, source_file_name, errors, 159 "{} of {} '{}'".format(name, kind, 160 expression.function.function_name.text)) 161 if len(args) < min_args: 162 errors.append([ 163 error.error(source_file_name, expression.source_location, 164 "{} '{}' requires {} {} argument{}.".format( 165 kind.title(), expression.function.function_name.text, 166 "exactly" if min_args == max_args else "at least", 167 min_args, "s" if min_args > 1 else "")) 168 ]) 169 if max_args is not None and len(args) > max_args: 170 errors.append([ 171 error.error(source_file_name, expression.source_location, 172 "{} '{}' requires {} {} argument{}.".format( 173 kind.title(), expression.function.function_name.text, 174 "exactly" if min_args == max_args else "at most", 175 max_args, "s" if max_args > 1 else "")) 176 ]) 177 set_result_type(expression) 178 179 180def _type_check_local_reference(expression, ir, errors): 181 """Annotates the type of a local reference.""" 182 referrent = ir_util.find_object(expression.field_reference.path[-1], ir) 183 assert referrent, "Local reference should be non-None after name resolution." 184 if isinstance(referrent, ir_data.RuntimeParameter): 185 parameter = referrent 186 _set_expression_type_from_physical_type_reference( 187 expression, parameter.physical_type_alias.atomic_type.reference, ir) 188 return 189 field = referrent 190 if ir_util.field_is_virtual(field): 191 _type_check_expression(field.read_transform, 192 expression.field_reference.path[0], ir, errors) 193 ir_data_utils.builder(expression).type.CopyFrom(field.read_transform.type) 194 return 195 if not field.type.HasField("atomic_type"): 196 ir_data_utils.builder(expression).type.opaque.CopyFrom(ir_data.OpaqueType()) 197 else: 198 _set_expression_type_from_physical_type_reference( 199 expression, field.type.atomic_type.reference, ir) 200 201 202def unbounded_expression_type_for_physical_type(type_definition): 203 """Gets the ExpressionType for a field of the given TypeDefinition. 204 205 Arguments: 206 type_definition: an ir_data.AddressableUnit. 207 208 Returns: 209 An ir_data.ExpressionType with the corresponding expression type filled in: 210 for example, [prelude].UInt will result in an ExpressionType with the 211 `integer` field filled in. 212 213 The returned ExpressionType will not have any bounds set. 214 """ 215 # TODO(bolms): Add a `[value_type]` attribute for `external`s. 216 if ir_util.get_boolean_attribute(type_definition.attribute, 217 attributes.IS_INTEGER): 218 return ir_data.ExpressionType(integer=ir_data.IntegerType()) 219 elif tuple(type_definition.name.canonical_name.object_path) == ("Flag",): 220 # This is a hack: the Flag type should say that it is a boolean. 221 return ir_data.ExpressionType(boolean=ir_data.BooleanType()) 222 elif type_definition.HasField("enumeration"): 223 return ir_data.ExpressionType( 224 enumeration=ir_data.EnumType( 225 name=ir_data.Reference( 226 canonical_name=type_definition.name.canonical_name))) 227 else: 228 return ir_data.ExpressionType(opaque=ir_data.OpaqueType()) 229 230 231def _set_expression_type_from_physical_type_reference(expression, 232 type_reference, ir): 233 """Sets the type of an expression to match a physical type.""" 234 field_type = ir_util.find_object(type_reference, ir) 235 assert field_type, "Field type should be non-None after name resolution." 236 ir_data_utils.builder(expression).type.CopyFrom( 237 unbounded_expression_type_for_physical_type(field_type)) 238 239 240def _annotate_parameter_type(parameter, ir, source_file_name, errors): 241 if parameter.physical_type_alias.WhichOneof("type") != "atomic_type": 242 errors.append([ 243 error.error( 244 source_file_name, parameter.physical_type_alias.source_location, 245 "Parameters cannot be arrays.") 246 ]) 247 return 248 _set_expression_type_from_physical_type_reference( 249 parameter, parameter.physical_type_alias.atomic_type.reference, ir) 250 251 252def _types_are_compatible(a, b): 253 """Returns true if a and b have compatible types.""" 254 if a.type.WhichOneof("type") != b.type.WhichOneof("type"): 255 return False 256 elif a.type.WhichOneof("type") == "enumeration": 257 return (ir_util.hashable_form_of_reference(a.type.enumeration.name) == 258 ir_util.hashable_form_of_reference(b.type.enumeration.name)) 259 elif a.type.WhichOneof("type") in ("integer", "boolean"): 260 # All integers are compatible with integers; booleans are compatible with 261 # booleans 262 return True 263 else: 264 assert False, "_types_are_compatible works with enums, integers, booleans." 265 266 267def _type_check_comparison_operator(expression, source_file_name, errors): 268 """Checks the type of a comparison operator (==, !=, <, >, >=, <=).""" 269 # Applying less than or greater than to a boolean is likely a mistake, so 270 # only equality and inequality are allowed for booleans. 271 if expression.function.function in (ir_data.FunctionMapping.EQUALITY, 272 ir_data.FunctionMapping.INEQUALITY): 273 acceptable_types = ("integer", "boolean", "enumeration") 274 acceptable_types_for_humans = "an integer, boolean, or enum" 275 else: 276 acceptable_types = ("integer", "enumeration") 277 acceptable_types_for_humans = "an integer or enum" 278 left = expression.function.args[0] 279 right = expression.function.args[1] 280 for (argument, name) in ((left, "Left"), (right, "Right")): 281 if argument.type.WhichOneof("type") not in acceptable_types: 282 errors.append([ 283 error.error(source_file_name, argument.source_location, 284 "{} argument of operator '{}' must be {}.".format( 285 name, expression.function.function_name.text, 286 acceptable_types_for_humans)) 287 ]) 288 return 289 if not _types_are_compatible(left, right): 290 errors.append([ 291 error.error(source_file_name, expression.source_location, 292 "Both arguments of operator '{}' must have the same " 293 "type.".format(expression.function.function_name.text)) 294 ]) 295 _annotate_as_boolean(expression) 296 297 298def _type_check_choice_operator(expression, source_file_name, errors): 299 """Checks the type of the choice operator cond ? if_true : if_false.""" 300 condition = expression.function.args[0] 301 if condition.type.WhichOneof("type") != "boolean": 302 errors.append([ 303 error.error(source_file_name, condition.source_location, 304 "Condition of operator '?:' must be a boolean.") 305 ]) 306 if_true = expression.function.args[1] 307 if if_true.type.WhichOneof("type") not in ("integer", "boolean", 308 "enumeration"): 309 errors.append([ 310 error.error(source_file_name, if_true.source_location, 311 "If-true clause of operator '?:' must be an integer, " 312 "boolean, or enum.") 313 ]) 314 return 315 if_false = expression.function.args[2] 316 if not _types_are_compatible(if_true, if_false): 317 errors.append([ 318 error.error(source_file_name, expression.source_location, 319 "The if-true and if-false clauses of operator '?:' must " 320 "have the same type.") 321 ]) 322 if if_true.type.WhichOneof("type") == "integer": 323 _annotate_as_integer(expression) 324 elif if_true.type.WhichOneof("type") == "boolean": 325 _annotate_as_boolean(expression) 326 elif if_true.type.WhichOneof("type") == "enumeration": 327 ir_data_utils.builder(expression).type.enumeration.name.CopyFrom(if_true.type.enumeration.name) 328 else: 329 assert False, "Unexpected type for if_true." 330 331 332def _type_check_boolean_constant(expression): 333 _annotate_as_boolean(expression) 334 335 336def _type_check_builtin_reference(expression): 337 name = expression.builtin_reference.canonical_name.object_path[0] 338 if name == "$is_statically_sized": 339 _annotate_as_boolean(expression) 340 elif name == "$static_size_in_bits": 341 _annotate_as_integer(expression) 342 else: 343 assert False, "Unknown builtin '{}'.".format(name) 344 345 346def _type_check_array_size(expression, source_file_name, errors): 347 _type_check_integer(expression, source_file_name, errors, "Array size") 348 349 350def _type_check_field_location(location, source_file_name, errors): 351 _type_check_integer(location.start, source_file_name, errors, 352 "Start of field") 353 _type_check_integer(location.size, source_file_name, errors, "Size of field") 354 355 356def _type_check_field_existence_condition(field, source_file_name, errors): 357 _type_check_boolean(field.existence_condition, source_file_name, errors, 358 "Existence condition") 359 360 361def _type_name_for_error_messages(expression_type): 362 if expression_type.WhichOneof("type") == "integer": 363 return "integer" 364 elif expression_type.WhichOneof("type") == "enumeration": 365 # TODO(bolms): Should this be the fully-qualified name? 366 return expression_type.enumeration.name.canonical_name.object_path[-1] 367 assert False, "Shouldn't be here." 368 369 370def _type_check_passed_parameters(atomic_type, ir, source_file_name, errors): 371 """Checks the types of parameters to a parameterized physical type.""" 372 referenced_type = ir_util.find_object(atomic_type.reference.canonical_name, 373 ir) 374 if (len(referenced_type.runtime_parameter) != 375 len(atomic_type.runtime_parameter)): 376 errors.append([ 377 error.error( 378 source_file_name, atomic_type.source_location, 379 "Type {} requires {} parameter{}; {} parameter{} given.".format( 380 referenced_type.name.name.text, 381 len(referenced_type.runtime_parameter), 382 "" if len(referenced_type.runtime_parameter) == 1 else "s", 383 len(atomic_type.runtime_parameter), 384 "" if len(atomic_type.runtime_parameter) == 1 else "s")), 385 error.note( 386 atomic_type.reference.canonical_name.module_file, 387 referenced_type.source_location, 388 "Definition of type {}.".format(referenced_type.name.name.text)) 389 ]) 390 return 391 for i in range(len(referenced_type.runtime_parameter)): 392 if referenced_type.runtime_parameter[i].type.WhichOneof("type") not in ( 393 "integer", "boolean", "enumeration"): 394 # _type_check_parameter will catch invalid parameter types at the 395 # definition site; no need for another, probably-confusing error at any 396 # usage sites. 397 continue 398 if (atomic_type.runtime_parameter[i].type.WhichOneof("type") != 399 referenced_type.runtime_parameter[i].type.WhichOneof("type")): 400 errors.append([ 401 error.error( 402 source_file_name, 403 atomic_type.runtime_parameter[i].source_location, 404 "Parameter {} of type {} must be {}, not {}.".format( 405 i, referenced_type.name.name.text, 406 _type_name_for_error_messages( 407 referenced_type.runtime_parameter[i].type), 408 _type_name_for_error_messages( 409 atomic_type.runtime_parameter[i].type))), 410 error.note( 411 atomic_type.reference.canonical_name.module_file, 412 referenced_type.runtime_parameter[i].source_location, 413 "Parameter {} of {}.".format(i, referenced_type.name.name.text)) 414 ]) 415 416 417def _type_check_parameter(runtime_parameter, source_file_name, errors): 418 """Checks the type of a parameter to a physical type.""" 419 if runtime_parameter.type.WhichOneof("type") not in ("integer", 420 "enumeration"): 421 errors.append([ 422 error.error(source_file_name, 423 runtime_parameter.physical_type_alias.source_location, 424 "Runtime parameters must be integer or enum.") 425 ]) 426 427 428def annotate_types(ir): 429 """Adds type annotations to all expressions in ir. 430 431 annotate_types adds type information to all expressions (and subexpressions) 432 in the IR. Additionally, it checks expressions for internal type consistency: 433 it will generate an error for constructs like "1 + true", where the types of 434 the operands are not accepted by the operator. 435 436 Arguments: 437 ir: an IR to which to add type annotations 438 439 Returns: 440 A (possibly empty) list of errors. 441 """ 442 errors = [] 443 traverse_ir.fast_traverse_ir_top_down( 444 ir, [ir_data.Expression], _type_check_expression, 445 skip_descendants_of={ir_data.Expression}, 446 parameters={"errors": errors}) 447 traverse_ir.fast_traverse_ir_top_down( 448 ir, [ir_data.RuntimeParameter], _annotate_parameter_type, 449 parameters={"errors": errors}) 450 return errors 451 452 453def check_types(ir): 454 """Checks that expressions within the IR have the correct top-level types. 455 456 check_types ensures that expressions at the top level have correct types; in 457 particular, it ensures that array sizes are integers ("UInt[true]" is not a 458 valid array type) and that the starts and ends of ranges are integers. 459 460 Arguments: 461 ir: an IR to type check. 462 463 Returns: 464 A (possibly empty) list of errors. 465 """ 466 errors = [] 467 traverse_ir.fast_traverse_ir_top_down( 468 ir, [ir_data.FieldLocation], _type_check_field_location, 469 parameters={"errors": errors}) 470 traverse_ir.fast_traverse_ir_top_down( 471 ir, [ir_data.ArrayType, ir_data.Expression], _type_check_array_size, 472 skip_descendants_of={ir_data.AtomicType}, 473 parameters={"errors": errors}) 474 traverse_ir.fast_traverse_ir_top_down( 475 ir, [ir_data.Field], _type_check_field_existence_condition, 476 parameters={"errors": errors}) 477 traverse_ir.fast_traverse_ir_top_down( 478 ir, [ir_data.RuntimeParameter], _type_check_parameter, 479 parameters={"errors": errors}) 480 traverse_ir.fast_traverse_ir_top_down( 481 ir, [ir_data.AtomicType], _type_check_passed_parameters, 482 parameters={"errors": errors}) 483 return errors 484