xref: /aosp_15_r20/external/emboss/compiler/front_end/constraints.py (revision 99e0aae7469b87d12f0ad23e61142c2d74c1ef70)

# 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