# 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 to check miscellaneous constraints on the IR.""" from compiler.front_end import attributes from compiler.util import error from compiler.util import ir_data from compiler.util import ir_data_utils from compiler.util import ir_util from compiler.util import resources from compiler.util import traverse_ir def _render_type(type_ir, ir): """Returns the human-readable notation of the given type.""" assert type_ir.HasField("atomic_type"), ( "TODO(bolms): Implement _render_type for array types.") if type_ir.HasField("size_in_bits"): return _render_atomic_type_name( type_ir, ir, suffix=":" + str(ir_util.constant_value(type_ir.size_in_bits))) else: return _render_atomic_type_name(type_ir, ir) def _render_atomic_type_name(type_ir, ir, suffix=None): assert type_ir.HasField("atomic_type"), ( "_render_atomic_type_name() requires an atomic type") if not suffix: suffix = "" type_definition = ir_util.find_object(type_ir.atomic_type.reference, ir) if type_definition.name.is_anonymous: return "anonymous type" else: return "type '{}{}'".format(type_definition.name.name.text, suffix) def _check_that_inner_array_dimensions_are_constant( type_ir, source_file_name, errors): """Checks that inner array dimensions are constant.""" if type_ir.WhichOneof("size") == "automatic": errors.append([error.error( source_file_name, ir_data_utils.reader(type_ir).element_count.source_location, "Array dimensions can only be omitted for the outermost dimension.")]) elif type_ir.WhichOneof("size") == "element_count": if not ir_util.is_constant(type_ir.element_count): errors.append([error.error(source_file_name, type_ir.element_count.source_location, "Inner array dimensions must be constant.")]) else: assert False, 'Expected "element_count" or "automatic" array size.' def _check_that_array_base_types_are_fixed_size(type_ir, source_file_name, errors, ir): """Checks that the sizes of array elements are known at compile time.""" if type_ir.base_type.HasField("array_type"): # An array is fixed size if its base_type is fixed size and its array # dimension is constant. This function will be called again on the inner # array, and we do not want to cascade errors if the inner array's base_type # is not fixed size. The array dimensions are separately checked by # _check_that_inner_array_dimensions_are_constant, which will provide an # appropriate error message for that case. return assert type_ir.base_type.HasField("atomic_type") if type_ir.base_type.HasField("size_in_bits"): # If the base_type has a size_in_bits, then it is fixed size. return base_type = ir_util.find_object(type_ir.base_type.atomic_type.reference, ir) base_type_fixed_size = ir_util.get_integer_attribute( base_type.attribute, attributes.FIXED_SIZE) if base_type_fixed_size is None: errors.append([error.error(source_file_name, type_ir.base_type.atomic_type.source_location, "Array elements must be fixed size.")]) def _check_that_array_base_types_in_structs_are_multiples_of_bytes( type_ir, type_definition, source_file_name, errors, ir): # TODO(bolms): Remove this limitation. """Checks that the sizes of array elements are multiples of 8 bits.""" if type_ir.base_type.HasField("array_type"): # Only check the innermost array for multidimensional arrays. return assert type_ir.base_type.HasField("atomic_type") if type_ir.base_type.HasField("size_in_bits"): assert ir_util.is_constant(type_ir.base_type.size_in_bits) base_type_size = ir_util.constant_value(type_ir.base_type.size_in_bits) else: fixed_size = ir_util.fixed_size_of_type_in_bits(type_ir.base_type, ir) if fixed_size is None: # Variable-sized elements are checked elsewhere. return base_type_size = fixed_size if base_type_size % type_definition.addressable_unit != 0: assert type_definition.addressable_unit == ir_data.AddressableUnit.BYTE errors.append([error.error(source_file_name, type_ir.base_type.source_location, "Array elements in structs must have sizes " "which are a multiple of 8 bits.")]) def _check_constancy_of_constant_references(expression, source_file_name, errors, ir): """Checks that constant_references are constant.""" if expression.WhichOneof("expression") != "constant_reference": return # This is a bit of a hack: really, we want to know that the referred-to object # has no dependencies on any instance variables of its parent structure; i.e., # that its value does not depend on having a view of the structure. if not ir_util.is_constant_type(expression.type): referred_name = expression.constant_reference.canonical_name referred_object = ir_util.find_object(referred_name, ir) errors.append([ error.error( source_file_name, expression.source_location, "Static references must refer to constants."), error.note( referred_name.module_file, referred_object.source_location, "{} is not constant.".format(referred_name.object_path[-1])) ]) def _check_that_enum_values_are_representable(enum_type, type_definition, source_file_name, errors): """Checks that enumeration values can fit in their specified int type.""" values = [] max_enum_size = ir_util.get_integer_attribute( type_definition.attribute, attributes.ENUM_MAXIMUM_BITS) is_signed = ir_util.get_boolean_attribute( type_definition.attribute, attributes.IS_SIGNED) if is_signed: enum_range = (-(2**(max_enum_size-1)), 2**(max_enum_size-1)-1) else: enum_range = (0, 2**max_enum_size-1) for value in enum_type.value: values.append((ir_util.constant_value(value.value), value)) out_of_range = [v for v in values if not enum_range[0] <= v[0] <= enum_range[1]] # If all values are in range, this loop will have zero iterations. for value in out_of_range: errors.append([ error.error( source_file_name, value[1].value.source_location, "Value {} is out of range for {}-bit {} enumeration.".format( value[0], max_enum_size, "signed" if is_signed else "unsigned")) ]) def _field_size(field, type_definition): """Calculates the size of the given field in bits, if it is constant.""" size = ir_util.constant_value(field.location.size) if size is None: return None return size * type_definition.addressable_unit def _check_type_requirements_for_field(type_ir, type_definition, field, ir, source_file_name, errors): """Checks that the `requires` attribute of each field's type is fulfilled.""" if not type_ir.HasField("atomic_type"): return if field.type.HasField("atomic_type"): field_min_size = (int(field.location.size.type.integer.minimum_value) * type_definition.addressable_unit) field_max_size = (int(field.location.size.type.integer.maximum_value) * type_definition.addressable_unit) field_is_atomic = True else: field_is_atomic = False if type_ir.HasField("size_in_bits"): element_size = ir_util.constant_value(type_ir.size_in_bits) else: element_size = None referenced_type_definition = ir_util.find_object( type_ir.atomic_type.reference, ir) type_is_anonymous = referenced_type_definition.name.is_anonymous type_size_attr = ir_util.get_attribute( referenced_type_definition.attribute, attributes.FIXED_SIZE) if type_size_attr: type_size = ir_util.constant_value(type_size_attr.expression) else: type_size = None if (element_size is not None and type_size is not None and element_size != type_size): errors.append([ error.error( source_file_name, type_ir.size_in_bits.source_location, "Explicit size of {} bits does not match fixed size ({} bits) of " "{}.".format(element_size, type_size, _render_atomic_type_name(type_ir, ir))), error.note( type_ir.atomic_type.reference.canonical_name.module_file, type_size_attr.source_location, "Size specified here.") ]) return # If the type had no size specifier (the ':32' in 'UInt:32'), but the type is # fixed size, then continue as if the type's size were explicitly stated. if element_size is None: element_size = type_size # TODO(bolms): When the full dynamic size expression for types is generated, # add a check that dynamically-sized types can, at least potentially, fit in # their fields. if field_is_atomic and element_size is not None: # If the field has a fixed size, and the (atomic) type contained therein is # also fixed size, then the sizes should match. # # TODO(bolms): Maybe change the case where the field is bigger than # necessary into a warning? if (field_max_size == field_min_size and (element_size > field_max_size or (element_size < field_min_size and not type_is_anonymous))): errors.append([ error.error( source_file_name, type_ir.source_location, "Fixed-size {} cannot be placed in field of size {} bits; " "requires {} bits.".format( _render_type(type_ir, ir), field_max_size, element_size)) ]) return elif element_size > field_max_size: errors.append([ error.error( source_file_name, type_ir.source_location, "Field of maximum size {} bits cannot hold fixed-size {}, which " "requires {} bits.".format( field_max_size, _render_type(type_ir, ir), element_size)) ]) return # If we're here, then field/type sizes are consistent. if (element_size is None and field_is_atomic and field_min_size == field_max_size): # From here down, we just use element_size. element_size = field_min_size errors.extend(_check_physical_type_requirements( type_ir, field.source_location, element_size, ir, source_file_name)) def _check_type_requirements_for_parameter_type( runtime_parameter, ir, source_file_name, errors): """Checks that the type of a parameter is valid.""" physical_type = runtime_parameter.physical_type_alias logical_type = runtime_parameter.type size = ir_util.constant_value(physical_type.size_in_bits) if logical_type.WhichOneof("type") == "integer": integer_errors = _integer_bounds_errors( logical_type.integer, "parameter", source_file_name, physical_type.source_location) if integer_errors: errors.extend(integer_errors) return errors.extend(_check_physical_type_requirements( physical_type, runtime_parameter.source_location, size, ir, source_file_name)) elif logical_type.WhichOneof("type") == "enumeration": if physical_type.HasField("size_in_bits"): # This seems a little weird: for `UInt`, `Int`, etc., the explicit size is # required, but for enums it is banned. This is because enums have a # "native" 64-bit size in expressions, so the physical size is just # ignored. errors.extend([[ error.error( source_file_name, physical_type.size_in_bits.source_location, "Parameters with enum type may not have explicit size.") ]]) else: assert False, "Non-integer/enum parameters should have been caught earlier." def _check_physical_type_requirements( type_ir, usage_source_location, size, ir, source_file_name): """Checks that the given atomic `type_ir` is allowed to be `size` bits.""" referenced_type_definition = ir_util.find_object( type_ir.atomic_type.reference, ir) if referenced_type_definition.HasField("enumeration"): if size is None: return [[ error.error( source_file_name, type_ir.source_location, "Enumeration {} cannot be placed in a dynamically-sized " "field.".format(_render_type(type_ir, ir))) ]] else: max_enum_size = ir_util.get_integer_attribute( referenced_type_definition.attribute, attributes.ENUM_MAXIMUM_BITS) if size < 1 or size > max_enum_size: return [[ error.error( source_file_name, type_ir.source_location, "Enumeration {} cannot be {} bits; {} must be between " "1 and {} bits, inclusive.".format( _render_atomic_type_name(type_ir, ir), size, _render_atomic_type_name(type_ir, ir), max_enum_size)) ]] if size is None: bindings = {"$is_statically_sized": False} else: bindings = { "$is_statically_sized": True, "$static_size_in_bits": size } requires_attr = ir_util.get_attribute( referenced_type_definition.attribute, attributes.STATIC_REQUIREMENTS) if requires_attr and not ir_util.constant_value(requires_attr.expression, bindings): # TODO(bolms): Figure out a better way to build this error message. # The "Requirements specified here." message should print out the actual # source text of the requires attribute, so that should help, but it's still # a bit generic and unfriendly. return [[ error.error( source_file_name, usage_source_location, "Requirements of {} not met.".format( type_ir.atomic_type.reference.canonical_name.object_path[-1])), error.note( type_ir.atomic_type.reference.canonical_name.module_file, requires_attr.source_location, "Requirements specified here.") ]] return [] def _check_allowed_in_bits(type_ir, type_definition, source_file_name, ir, errors): if not type_ir.HasField("atomic_type"): return referenced_type_definition = ir_util.find_object( type_ir.atomic_type.reference, ir) if (type_definition.addressable_unit % referenced_type_definition.addressable_unit != 0): assert type_definition.addressable_unit == ir_data.AddressableUnit.BIT assert (referenced_type_definition.addressable_unit == ir_data.AddressableUnit.BYTE) errors.append([ error.error(source_file_name, type_ir.source_location, "Byte-oriented {} cannot be used in a bits field.".format( _render_type(type_ir, ir))) ]) def _check_size_of_bits(type_ir, type_definition, source_file_name, errors): """Checks that `bits` types are fixed size, less than 64 bits.""" del type_ir # Unused if type_definition.addressable_unit != ir_data.AddressableUnit.BIT: return fixed_size = ir_util.get_integer_attribute( type_definition.attribute, attributes.FIXED_SIZE) if fixed_size is None: errors.append([error.error(source_file_name, type_definition.source_location, "`bits` types must be fixed size.")]) return if fixed_size > 64: errors.append([error.error(source_file_name, type_definition.source_location, "`bits` types must be 64 bits or smaller.")]) _RESERVED_WORDS = None def get_reserved_word_list(): if _RESERVED_WORDS is None: _initialize_reserved_word_list() return _RESERVED_WORDS def _initialize_reserved_word_list(): global _RESERVED_WORDS _RESERVED_WORDS = {} language = None for line in resources.load( "compiler.front_end", "reserved_words").splitlines(): stripped_line = line.partition("#")[0].strip() if not stripped_line: continue if stripped_line.startswith("--"): language = stripped_line.partition("--")[2].strip() else: # For brevity's sake, only use the first language for error messages. if stripped_line not in _RESERVED_WORDS: _RESERVED_WORDS[stripped_line] = language def _check_name_for_reserved_words(obj, source_file_name, errors, context_name): if obj.name.name.text in get_reserved_word_list(): errors.append([ error.error( source_file_name, obj.name.name.source_location, "{} reserved word may not be used as {}.".format( get_reserved_word_list()[obj.name.name.text], context_name)) ]) def _check_field_name_for_reserved_words(field, source_file_name, errors): return _check_name_for_reserved_words(field, source_file_name, errors, "a field name") def _check_enum_name_for_reserved_words(enum, source_file_name, errors): return _check_name_for_reserved_words(enum, source_file_name, errors, "an enum name") def _check_type_name_for_reserved_words(type_definition, source_file_name, errors): return _check_name_for_reserved_words( type_definition, source_file_name, errors, "a type name") def _bounds_can_fit_64_bit_unsigned(minimum, maximum): return minimum >= 0 and maximum <= 2**64 - 1 def _bounds_can_fit_64_bit_signed(minimum, maximum): return minimum >= -(2**63) and maximum <= 2**63 - 1 def _bounds_can_fit_any_64_bit_integer_type(minimum, maximum): return (_bounds_can_fit_64_bit_unsigned(minimum, maximum) or _bounds_can_fit_64_bit_signed(minimum, maximum)) def _integer_bounds_errors_for_expression(expression, source_file_name): """Checks that `expression` is in range for int64_t or uint64_t.""" # Only check non-constant subexpressions. if (expression.WhichOneof("expression") == "function" and not ir_util.is_constant_type(expression.type)): errors = [] for arg in expression.function.args: errors += _integer_bounds_errors_for_expression(arg, source_file_name) if errors: # Don't cascade bounds errors: report them at the lowest level they # appear. return errors if expression.type.WhichOneof("type") == "integer": errors = _integer_bounds_errors(expression.type.integer, "expression", source_file_name, expression.source_location) if errors: return errors if (expression.WhichOneof("expression") == "function" and not ir_util.is_constant_type(expression.type)): int64_only_clauses = [] uint64_only_clauses = [] for clause in [expression] + list(expression.function.args): if clause.type.WhichOneof("type") == "integer": arg_minimum = int(clause.type.integer.minimum_value) arg_maximum = int(clause.type.integer.maximum_value) if not _bounds_can_fit_64_bit_signed(arg_minimum, arg_maximum): uint64_only_clauses.append(clause) elif not _bounds_can_fit_64_bit_unsigned(arg_minimum, arg_maximum): int64_only_clauses.append(clause) if int64_only_clauses and uint64_only_clauses: error_set = [ error.error( source_file_name, expression.source_location, "Either all arguments to '{}' and its result must fit in a " "64-bit unsigned integer, or all must fit in a 64-bit signed " "integer.".format(expression.function.function_name.text)) ] for signedness, clause_list in (("unsigned", uint64_only_clauses), ("signed", int64_only_clauses)): for clause in clause_list: error_set.append(error.note( source_file_name, clause.source_location, "Requires {} 64-bit integer.".format(signedness))) return [error_set] return [] def _integer_bounds_errors(bounds, name, source_file_name, error_source_location): """Returns appropriate errors, if any, for the given integer bounds.""" assert bounds.minimum_value, "{}".format(bounds) assert bounds.maximum_value, "{}".format(bounds) if (bounds.minimum_value == "-infinity" or bounds.maximum_value == "infinity"): return [[ error.error( source_file_name, error_source_location, "Integer range of {} must not be unbounded; it must fit " "in a 64-bit signed or unsigned integer.".format(name)) ]] if not _bounds_can_fit_any_64_bit_integer_type(int(bounds.minimum_value), int(bounds.maximum_value)): if int(bounds.minimum_value) == int(bounds.maximum_value): return [[ error.error( source_file_name, error_source_location, "Constant value {} of {} cannot fit in a 64-bit signed or " "unsigned integer.".format(bounds.minimum_value, name)) ]] else: return [[ error.error( source_file_name, error_source_location, "Potential range of {} is {} to {}, which cannot fit " "in a 64-bit signed or unsigned integer.".format( name, bounds.minimum_value, bounds.maximum_value)) ]] return [] def _check_bounds_on_runtime_integer_expressions(expression, source_file_name, in_attribute, errors): if in_attribute and in_attribute.name.text == attributes.STATIC_REQUIREMENTS: # [static_requirements] is never evaluated at runtime, and $size_in_bits is # unbounded, so it should not be checked. return # The logic for gathering errors and suppressing cascades is simpler if # errors are just returned, rather than appended to a shared list. errors += _integer_bounds_errors_for_expression(expression, source_file_name) def _attribute_in_attribute_action(a): return {"in_attribute": a} def check_constraints(ir): """Checks miscellaneous validity constraints in ir. Checks that auto array sizes are only used for the outermost size of multidimensional arrays. That is, Type[3][] is OK, but Type[][3] is not. Checks that fixed-size fields are a correct size to hold statically-sized types. Checks that inner array dimensions are constant. Checks that only constant-size types are used in arrays. Arguments: ir: An ir_data.EmbossIr object to check. Returns: A list of ConstraintViolations, or an empty list if there are none. """ errors = [] traverse_ir.fast_traverse_ir_top_down( ir, [ir_data.Structure, ir_data.Type], _check_allowed_in_bits, parameters={"errors": errors}) traverse_ir.fast_traverse_ir_top_down( # TODO(bolms): look for [ir_data.ArrayType], [ir_data.AtomicType], and # simplify _check_that_array_base_types_are_fixed_size. ir, [ir_data.ArrayType], _check_that_array_base_types_are_fixed_size, parameters={"errors": errors}) traverse_ir.fast_traverse_ir_top_down( ir, [ir_data.Structure, ir_data.ArrayType], _check_that_array_base_types_in_structs_are_multiples_of_bytes, parameters={"errors": errors}) traverse_ir.fast_traverse_ir_top_down( ir, [ir_data.ArrayType, ir_data.ArrayType], _check_that_inner_array_dimensions_are_constant, parameters={"errors": errors}) traverse_ir.fast_traverse_ir_top_down( ir, [ir_data.Structure], _check_size_of_bits, parameters={"errors": errors}) traverse_ir.fast_traverse_ir_top_down( ir, [ir_data.Structure, ir_data.Type], _check_type_requirements_for_field, parameters={"errors": errors}) traverse_ir.fast_traverse_ir_top_down( ir, [ir_data.Field], _check_field_name_for_reserved_words, parameters={"errors": errors}) traverse_ir.fast_traverse_ir_top_down( ir, [ir_data.EnumValue], _check_enum_name_for_reserved_words, parameters={"errors": errors}) traverse_ir.fast_traverse_ir_top_down( ir, [ir_data.TypeDefinition], _check_type_name_for_reserved_words, parameters={"errors": errors}) traverse_ir.fast_traverse_ir_top_down( ir, [ir_data.Expression], _check_constancy_of_constant_references, parameters={"errors": errors}) traverse_ir.fast_traverse_ir_top_down( ir, [ir_data.Enum], _check_that_enum_values_are_representable, parameters={"errors": errors}) traverse_ir.fast_traverse_ir_top_down( ir, [ir_data.Expression], _check_bounds_on_runtime_integer_expressions, incidental_actions={ir_data.Attribute: _attribute_in_attribute_action}, skip_descendants_of={ir_data.EnumValue, ir_data.Expression}, parameters={"errors": errors, "in_attribute": None}) traverse_ir.fast_traverse_ir_top_down( ir, [ir_data.RuntimeParameter], _check_type_requirements_for_parameter_type, parameters={"errors": errors}) return errors