compiler/front_end/module_ir.py

# 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.

"""module_ir contains code for generating module-level IRs from parse trees.

The primary export is build_ir(), which takes a parse tree (as returned by a
parser from lr1.py), and returns a module-level intermediate representation
("module IR").

This module also notably exports PRODUCTIONS and START_SYMBOL, which should be
fed to lr1.Grammar in order to create a parser for the Emboss language.
"""

import re
import sys

from compiler.util import ir_data
from compiler.util import ir_data_utils
from compiler.util import name_conversion
from compiler.util import parser_types


# Intermediate types; should not be found in the final IR.
class _List(object):
    """A list with source location information."""

    __slots__ = ("list", "source_location")

    def __init__(self, l):
        assert isinstance(l, list), "_List object must wrap list, not '%r'" % l
        self.list = l
        self.source_location = ir_data.Location()


class _ExpressionTail(object):
    """A fragment of an expression with an operator and right-hand side.

    _ExpressionTail is the tail of an expression, consisting of an operator and
    the right-hand argument to the operator; for example, in the expression (6+8),
    the _ExpressionTail would be "+8".

    This is used as a temporary object while converting the right-recursive
    "expression" and "times-expression" productions into left-associative
    Expressions.

    Attributes:
      operator: An ir_data.Word of the operator's name.
      expression: The expression on the right side of the operator.
      source_location: The source location of the operation fragment.
    """

    __slots__ = ("operator", "expression", "source_location")

    def __init__(self, operator, expression):
        self.operator = operator
        self.expression = expression
        self.source_location = ir_data.Location()


class _FieldWithType(object):
    """A field with zero or more types defined inline with that field."""

    __slots__ = ("field", "subtypes", "source_location")

    def __init__(self, field, subtypes=None):
        self.field = field
        self.subtypes = subtypes or []
        self.source_location = ir_data.Location()


def build_ir(parse_tree, used_productions=None):
    r"""Builds a module-level intermediate representation from a valid parse tree.

  The parse tree is precisely dictated by the exact productions in the grammar
  used by the parser, with no semantic information.  _really_build_ir transforms
  this "raw" form into a stable, cooked representation, thereby isolating
  subsequent steps from the exact details of the grammar.

  (Probably incomplete) list of transformations:

  *   ParseResult and Token nodes are replaced with Module, Attribute, Struct,
      Type, etc. objects.

  *   Purely syntactic tokens ('"["', '"struct"', etc.) are discarded.

  *   Repeated elements are transformed from tree form to list form:

          a*
         / \
        b   a*
           / \
          c   a*
             / \
            d   a*

      (where b, c, and d are nodes of type "a") becomes [b, c, d].

  *   The values of numeric constants (Number, etc. tokens) are parsed.

  *   Different classes of names (snake_names, CamelNames, ShoutyNames) are
      folded into a single "Name" type, since they are guaranteed to appear in
      the correct places in the parse tree.


  Arguments:
    parse_tree: A parse tree.  Each leaf node should be a parser_types.Token
      object, and each non-leaf node should have a 'symbol' attribute specifying
      which grammar symbol it represents, and a 'children' attribute containing
      a list of child nodes.  This is the format returned by the parsers
      produced by the lr1 module, when run against tokens from the tokenizer
      module.
    used_productions: If specified, used_productions.add() will be called with
      each production actually used in parsing.  This can be useful when
      developing the grammar and writing tests; in particular, it can be used to
      figure out which productions are *not* used when parsing a particular
      file.

  Returns:
    A module-level intermediate representation (module IR) for an Emboss module
    (source file).  This IR will not have symbols resolved; that must be done on
    a forest of module IRs so that names from other modules can be resolved.
  """

    # TODO(b/140259131): Refactor _really_build_ir to be less recursive/use an
    # explicit stack.
    old_recursion_limit = sys.getrecursionlimit()
    sys.setrecursionlimit(16 * 1024)  # ~8000 top-level entities in one module.
    try:
        result = _really_build_ir(parse_tree, used_productions)
    finally:
        sys.setrecursionlimit(old_recursion_limit)
    return result


def _really_build_ir(parse_tree, used_productions):
    """Real implementation of build_ir()."""
    if used_productions is None:
        used_productions = set()
    if hasattr(parse_tree, "children"):
        parsed_children = [
            _really_build_ir(child, used_productions) for child in parse_tree.children
        ]
        used_productions.add(parse_tree.production)
        result = _handlers[parse_tree.production](*parsed_children)
        if parse_tree.source_location is not None:
            if result.source_location:
                ir_data_utils.update(result.source_location, parse_tree.source_location)
            else:
                result.source_location = ir_data_utils.copy(parse_tree.source_location)
        return result
    else:
        # For leaf nodes, the temporary "IR" is just the token.  Higher-level rules
        # will translate it to a real IR.
        assert isinstance(parse_tree, parser_types.Token), str(parse_tree)
        return parse_tree


# Map of productions to their handlers.
_handlers = {}

_anonymous_name_counter = 0


def _get_anonymous_field_name():
    global _anonymous_name_counter
    _anonymous_name_counter += 1
    return "emboss_reserved_anonymous_field_{}".format(_anonymous_name_counter)


def _handles(production_text):
    """_handles marks a function as the handler for a particular production."""
    production = parser_types.Production.parse(production_text)

    def handles(f):
        _handlers[production] = f
        return f

    return handles


def _make_prelude_import(position):
    """Helper function to construct a synthetic ir_data.Import for the prelude."""
    location = parser_types.make_location(position, position)
    return ir_data.Import(
        file_name=ir_data.String(text="", source_location=location),
        local_name=ir_data.Word(text="", source_location=location),
        source_location=location,
    )


def _text_to_operator(text):
    """Converts an operator's textual name to its corresponding enum."""
    operations = {
        "+": ir_data.FunctionMapping.ADDITION,
        "-": ir_data.FunctionMapping.SUBTRACTION,
        "*": ir_data.FunctionMapping.MULTIPLICATION,
        "==": ir_data.FunctionMapping.EQUALITY,
        "!=": ir_data.FunctionMapping.INEQUALITY,
        "&&": ir_data.FunctionMapping.AND,
        "||": ir_data.FunctionMapping.OR,
        ">": ir_data.FunctionMapping.GREATER,
        ">=": ir_data.FunctionMapping.GREATER_OR_EQUAL,
        "<": ir_data.FunctionMapping.LESS,
        "<=": ir_data.FunctionMapping.LESS_OR_EQUAL,
    }
    return operations[text]


def _text_to_function(text):
    """Converts a function's textual name to its corresponding enum."""
    functions = {
        "$max": ir_data.FunctionMapping.MAXIMUM,
        "$present": ir_data.FunctionMapping.PRESENCE,
        "$upper_bound": ir_data.FunctionMapping.UPPER_BOUND,
        "$lower_bound": ir_data.FunctionMapping.LOWER_BOUND,
    }
    return functions[text]


################################################################################
# Grammar & parse tree to IR translation.
#
# From here to (almost) the end of the file are functions which recursively
# build an IR.  The @_handles annotations indicate the exact grammar
# production(s) handled by each function.  The handler function should take
# exactly one argument for each symbol in the production's RHS.
#
# The actual Emboss grammar is extracted directly from the @_handles
# annotations, so this is also the grammar definition.  For convenience, the
# grammar can be viewed separately in g3doc/grammar.md.
#
# At the end, symbols whose names end in "*", "+", or "?" are extracted from the
# grammar, and appropriate productions are added for zero-or-more, one-or-more,
# or zero-or-one lists, respectively.  (This is analogous to the *, +, and ?
# operators in regex.)  It is necessary for this to happen here (and not in
# lr1.py) because the generated productions must be associated with
# IR-generation functions.


# A module file is a list of documentation, then imports, then top-level
# attributes, then type definitions.  Any section may be missing.
# TODO(bolms): Should Emboss disallow completely empty files?
@_handles(
    "module -> comment-line* doc-line* import-line* attribute-line*"
    "          type-definition*"
)
def _file(leading_newlines, docs, imports, attributes, type_definitions):
    """Assembles the top-level IR for a module."""
    del leading_newlines  # Unused.
    # Figure out the best synthetic source_location for the synthesized prelude
    # import.
    if imports.list:
        position = imports.list[0].source_location.start
    elif docs.list:
        position = docs.list[0].source_location.end
    elif attributes.list:
        position = attributes.list[0].source_location.start
    elif type_definitions.list:
        position = type_definitions.list[0].source_location.start
    else:
        position = 1, 1

    # If the source file is completely empty, build_ir won't automatically
    # populate the source_location attribute for the module.
    if (
        not docs.list
        and not imports.list
        and not attributes.list
        and not type_definitions.list
    ):
        module_source_location = parser_types.make_location((1, 1), (1, 1))
    else:
        module_source_location = None

    return ir_data.Module(
        documentation=docs.list,
        foreign_import=[_make_prelude_import(position)] + imports.list,
        attribute=attributes.list,
        type=type_definitions.list,
        source_location=module_source_location,
    )


@_handles("import-line ->" '    "import" string-constant "as" snake-word Comment? eol')
def _import(import_, file_name, as_, local_name, comment, eol):
    del import_, as_, comment, eol  # Unused
    return ir_data.Import(file_name=file_name, local_name=local_name)


@_handles("doc-line -> doc Comment? eol")
def _doc_line(doc, comment, eol):
    del comment, eol  # Unused.
    return doc


@_handles("doc -> Documentation")
def _doc(documentation):
    # As a special case, an empty documentation string may omit the trailing
    # space.
    if documentation.text == "--":
        doc_text = "-- "
    else:
        doc_text = documentation.text
    assert doc_text[0:3] == "-- ", "Documentation token '{}' in unknown format.".format(
        documentation.text
    )
    return ir_data.Documentation(text=doc_text[3:])


# A attribute-line is just a attribute on its own line.
@_handles("attribute-line -> attribute Comment? eol")
def _attribute_line(attr, comment, eol):
    del comment, eol  # Unused.
    return attr


# A attribute is [name = value].
@_handles(
    'attribute -> "[" attribute-context? "$default"?'
    '             snake-word ":" attribute-value "]"'
)
def _attribute(
    open_bracket,
    context_specifier,
    default_specifier,
    name,
    colon,
    attribute_value,
    close_bracket,
):
    del open_bracket, colon, close_bracket  # Unused.
    if context_specifier.list:
        return ir_data.Attribute(
            name=name,
            value=attribute_value,
            is_default=bool(default_specifier.list),
            back_end=context_specifier.list[0],
        )
    else:
        return ir_data.Attribute(
            name=name, value=attribute_value, is_default=bool(default_specifier.list)
        )


@_handles('attribute-context -> "(" snake-word ")"')
def _attribute_context(open_paren, context_name, close_paren):
    del open_paren, close_paren  # Unused.
    return context_name


@_handles("attribute-value -> expression")
def _attribute_value_expression(expression):
    return ir_data.AttributeValue(expression=expression)


@_handles("attribute-value -> string-constant")
def _attribute_value_string(string):
    return ir_data.AttributeValue(string_constant=string)


@_handles("boolean-constant -> BooleanConstant")
def _boolean_constant(boolean):
    return ir_data.BooleanConstant(value=(boolean.text == "true"))


@_handles("string-constant -> String")
def _string_constant(string):
    """Turns a String token into an ir_data.String, with proper unescaping.

    Arguments:
      string: A String token.

    Returns:
      An ir_data.String with the "text" field set to the unescaped value of
      string.text.
    """
    # TODO(bolms): If/when this logic becomes more complex (e.g., to handle \NNN
    # or \xNN escapes), extract this into a separate module with separate tests.
    assert string.text[0] == '"'
    assert string.text[-1] == '"'
    assert len(string.text) >= 2
    result = []
    for substring in re.split(r"(\\.)", string.text[1:-1]):
        if substring and substring[0] == "\\":
            assert len(substring) == 2
            result.append({"\\": "\\", '"': '"', "n": "\n"}[substring[1]])
        else:
            result.append(substring)
    return ir_data.String(text="".join(result))


# In Emboss, '&&' and '||' may not be mixed without parentheses.  These are all
# fine:
#
#     x && y && z
#     x || y || z
#     (x || y) && z
#     x || (y && z)
#
# These are syntax errors:
#
#     x || y && z
#     x && y || z
#
# This is accomplished by making && and || separate-but-equal in the precedence
# hierarchy.  Instead of the more traditional:
#
#     logical-expression   -> or-expression
#     or-expression        -> and-expression or-expression-right*
#     or-expression-right  -> '||' and-expression
#     and-expression       -> equality-expression and-expression-right*
#     and-expression-right -> '&&' equality-expression
#
# Or, using yacc-style precedence specifiers:
#
#     %left "||"
#     %left "&&"
#     expression -> expression
#                 | expression '||' expression
#                 | expression '&&' expression
#
# Emboss uses a slightly more complex grammar, in which '&&' and '||' are
# parallel, but unmixable:
#
#     logical-expression   -> and-expression
#                           | or-expression
#                           | equality-expression
#     or-expression        -> equality-expression or-expression-right+
#     or-expression-right  -> '||' equality-expression
#     and-expression       -> equality-expression and-expression-right+
#     and-expression-right -> '&&' equality-expression
#
# In either case, explicit parenthesization is handled elsewhere in the grammar.
@_handles("logical-expression -> and-expression")
@_handles("logical-expression -> or-expression")
@_handles("logical-expression -> comparison-expression")
@_handles("choice-expression -> logical-expression")
@_handles("expression -> choice-expression")
def _expression(expression):
    return expression


# The `logical-expression`s here means that ?: can't be chained without
# parentheses.  `x < 0 ? -1 : (x == 0 ? 0 : 1)` is OK, but `x < 0 ? -1 : x == 0
# ? 0 : 1` is not.  Parentheses are also needed in the middle: `x <= 0 ? x < 0 ?
# -1 : 0 : 1` is not syntactically valid.
@_handles(
    'choice-expression -> logical-expression "?" logical-expression'
    '                                        ":" logical-expression'
)
def _choice_expression(condition, question, if_true, colon, if_false):
    location = parser_types.make_location(
        condition.source_location.start, if_false.source_location.end
    )
    operator_location = parser_types.make_location(
        question.source_location.start, colon.source_location.end
    )
    # The function_name is a bit weird, but should suffice for any error messages
    # that might need it.
    return ir_data.Expression(
        function=ir_data.Function(
            function=ir_data.FunctionMapping.CHOICE,
            args=[condition, if_true, if_false],
            function_name=ir_data.Word(text="?:", source_location=operator_location),
            source_location=location,
        )
    )


@_handles("comparison-expression -> additive-expression")
def _no_op_comparative_expression(expression):
    return expression


@_handles(
    "comparison-expression ->"
    "    additive-expression inequality-operator additive-expression"
)
def _comparative_expression(left, operator, right):
    location = parser_types.make_location(
        left.source_location.start, right.source_location.end
    )
    return ir_data.Expression(
        function=ir_data.Function(
            function=_text_to_operator(operator.text),
            args=[left, right],
            function_name=operator,
            source_location=location,
        )
    )


@_handles("additive-expression -> times-expression additive-expression-right*")
@_handles("times-expression -> negation-expression times-expression-right*")
@_handles("and-expression -> comparison-expression and-expression-right+")
@_handles("or-expression -> comparison-expression or-expression-right+")
def _binary_operator_expression(expression, expression_right):
    """Builds the IR for a chain of equal-precedence left-associative operations.

    _binary_operator_expression transforms a right-recursive list of expression
    tails into a left-associative Expression tree.  For example, given the
    arguments:

        6, (Tail("+", 7), Tail("-", 8), Tail("+", 10))

    _expression produces a structure like:

       Expression(Expression(Expression(6, "+", 7), "-", 8), "+", 10)

    This transformation is necessary because strict LR(1) grammars do not allow
    left recursion.

    Note that this method is used for several productions; each of those
    productions handles a different precedence level, but are identical in form.

    Arguments:
      expression: An ir_data.Expression which is the head of the (expr, operator,
          expr, operator, expr, ...) list.
      expression_right: A list of _ExpressionTails corresponding to the (operator,
          expr, operator, expr, ...) list that comes after expression.

    Returns:
      An ir_data.Expression with the correct recursive structure to represent a
      list of left-associative operations.
    """
    e = expression
    for right in expression_right.list:
        location = parser_types.make_location(
            e.source_location.start, right.source_location.end
        )
        e = ir_data.Expression(
            function=ir_data.Function(
                function=_text_to_operator(right.operator.text),
                args=[e, right.expression],
                function_name=right.operator,
                source_location=location,
            ),
            source_location=location,
        )
    return e


@_handles(
    "comparison-expression ->" "    additive-expression equality-expression-right+"
)
@_handles(
    "comparison-expression ->" "    additive-expression less-expression-right-list"
)
@_handles(
    "comparison-expression ->" "    additive-expression greater-expression-right-list"
)
def _chained_comparison_expression(expression, expression_right):
    """Builds the IR for a chain of comparisons, like a == b == c.

    Like _binary_operator_expression, _chained_comparison_expression transforms a
    right-recursive list of expression tails into a left-associative Expression
    tree.  Unlike _binary_operator_expression, extra AND nodes are added.  For
    example, the following expression:

        0 <= b <= 64

    must be translated to the conceptually-equivalent expression:

        0 <= b && b <= 64

    (The middle subexpression is duplicated -- this would be a problem in a
    programming language like C where expressions like `x++` have side effects,
    but side effects do not make sense in a data definition language like Emboss.)

    _chained_comparison_expression receives a left-hand head expression and a list
    of tails, like:

        6, (Tail("<=", b), Tail("<=", 64))

    which it translates to a structure like:

        Expression(Expression(6, "<=", b), "&&", Expression(b, "<=", 64))

    The Emboss grammar is constructed such that sequences of "<", "<=", and "=="
    comparisons may be chained, and sequences of ">", ">=", and "==" can be
    chained, but greater and less-than comparisons may not; e.g., "b < 64 > a" is
    not allowed.

    Arguments:
      expression: An ir_data.Expression which is the head of the (expr, operator,
          expr, operator, expr, ...) list.
      expression_right: A list of _ExpressionTails corresponding to the (operator,
          expr, operator, expr, ...) list that comes after expression.

    Returns:
      An ir_data.Expression with the correct recursive structure to represent a
      chain of left-associative comparison operations.
    """
    sequence = [expression]
    for right in expression_right.list:
        sequence.append(right.operator)
        sequence.append(right.expression)
    comparisons = []
    for i in range(0, len(sequence) - 1, 2):
        left, operator, right = sequence[i : i + 3]
        location = parser_types.make_location(
            left.source_location.start, right.source_location.end
        )
        comparisons.append(
            ir_data.Expression(
                function=ir_data.Function(
                    function=_text_to_operator(operator.text),
                    args=[left, right],
                    function_name=operator,
                    source_location=location,
                ),
                source_location=location,
            )
        )
    e = comparisons[0]
    for comparison in comparisons[1:]:
        location = parser_types.make_location(
            e.source_location.start, comparison.source_location.end
        )
        e = ir_data.Expression(
            function=ir_data.Function(
                function=ir_data.FunctionMapping.AND,
                args=[e, comparison],
                function_name=ir_data.Word(
                    text="&&",
                    source_location=comparison.function.args[0].source_location,
                ),
                source_location=location,
            ),
            source_location=location,
        )
    return e


# _chained_comparison_expression, above, handles three types of chains: `a == b
# == c`, `a < b <= c`, and `a > b >= c`.
#
# This requires a bit of subtlety in the productions for
# `x-expression-right-list`, because the `==` operator may be freely mixed into
# greater-than or less-than chains, like `a < b == c <= d` or `a > b == c >= d`,
# but greater-than and less-than may not be mixed; i.e., `a < b >= c` is
# disallowed.
#
# In order to keep the grammar unambiguous -- that is, in order to ensure that
# every valid input can only be parsed in exactly one way -- the languages
# defined by `equality-expression-right*`, `greater-expression-right-list`, and
# `less-expression-right-list` cannot overlap.
#
# `equality-expression-right*`, by definition, only contains `== n` elements.
# By forcing `greater-expression-right-list` to contain at least one
# `greater-expression-right`, we can ensure that a chain like `== n == m` cannot
# be parsed as a `greater-expression-right-list`.  Similar logic applies in the
# less-than case.
#
# There is another potential source of ambiguity here: if
# `greater-expression-right-list` were
#
#     greater-expression-right-list ->
#         equality-or-greater-expression-right* greater-expression-right
#         equality-or-greater-expression-right*
#
# then a sequence like '> b > c > d' could be parsed as any of:
#
#     () (> b) ((> c) (> d))
#     ((> b)) (> c) ((> d))
#     ((> b) (> c)) (> d) ()
#
# By using `equality-expression-right*` for the first symbol, only the first
# parse is possible.
@_handles(
    "greater-expression-right-list ->"
    "    equality-expression-right* greater-expression-right"
    "    equality-or-greater-expression-right*"
)
@_handles(
    "less-expression-right-list ->"
    "    equality-expression-right* less-expression-right"
    "    equality-or-less-expression-right*"
)
def _chained_comparison_tails(start, middle, end):
    return _List(start.list + [middle] + end.list)


@_handles("equality-or-greater-expression-right -> equality-expression-right")
@_handles("equality-or-greater-expression-right -> greater-expression-right")
@_handles("equality-or-less-expression-right -> equality-expression-right")
@_handles("equality-or-less-expression-right -> less-expression-right")
def _equality_or_less_or_greater(right):
    return right


@_handles("and-expression-right -> and-operator comparison-expression")
@_handles("or-expression-right -> or-operator comparison-expression")
@_handles("additive-expression-right -> additive-operator times-expression")
@_handles("equality-expression-right -> equality-operator additive-expression")
@_handles("greater-expression-right -> greater-operator additive-expression")
@_handles("less-expression-right -> less-operator additive-expression")
@_handles("times-expression-right ->" "    multiplicative-operator negation-expression")
def _expression_right_production(operator, expression):
    return _ExpressionTail(operator, expression)


# This supports a single layer of unary plus/minus, so "+5" and "-value" are
# allowed, but "+-5" or "-+-something" are not.
@_handles("negation-expression -> additive-operator bottom-expression")
def _negation_expression_with_operator(operator, expression):
    phantom_zero_location = ir_data.Location(
        start=operator.source_location.start, end=operator.source_location.start
    )
    return ir_data.Expression(
        function=ir_data.Function(
            function=_text_to_operator(operator.text),
            args=[
                ir_data.Expression(
                    constant=ir_data.NumericConstant(
                        value="0", source_location=phantom_zero_location
                    ),
                    source_location=phantom_zero_location,
                ),
                expression,
            ],
            function_name=operator,
            source_location=ir_data.Location(
                start=operator.source_location.start, end=expression.source_location.end
            ),
        )
    )


@_handles("negation-expression -> bottom-expression")
def _negation_expression(expression):
    return expression


@_handles('bottom-expression -> "(" expression ")"')
def _bottom_expression_parentheses(open_paren, expression, close_paren):
    del open_paren, close_paren  # Unused.
    return expression


@_handles('bottom-expression -> function-name "(" argument-list ")"')
def _bottom_expression_function(function, open_paren, arguments, close_paren):
    del open_paren  # Unused.
    return ir_data.Expression(
        function=ir_data.Function(
            function=_text_to_function(function.text),
            args=arguments.list,
            function_name=function,
            source_location=ir_data.Location(
                start=function.source_location.start,
                end=close_paren.source_location.end,
            ),
        )
    )


@_handles('comma-then-expression -> "," expression')
def _comma_then_expression(comma, expression):
    del comma  # Unused.
    return expression


@_handles("argument-list -> expression comma-then-expression*")
def _argument_list(head, tail):
    tail.list.insert(0, head)
    return tail


@_handles("argument-list ->")
def _empty_argument_list():
    return _List([])


@_handles("bottom-expression -> numeric-constant")
def _bottom_expression_from_numeric_constant(constant):
    return ir_data.Expression(constant=constant)


@_handles("bottom-expression -> constant-reference")
def _bottom_expression_from_constant_reference(reference):
    return ir_data.Expression(constant_reference=reference)


@_handles("bottom-expression -> builtin-reference")
def _bottom_expression_from_builtin(reference):
    return ir_data.Expression(builtin_reference=reference)


@_handles("bottom-expression -> boolean-constant")
def _bottom_expression_from_boolean_constant(boolean):
    return ir_data.Expression(boolean_constant=boolean)


@_handles("bottom-expression -> field-reference")
def _bottom_expression_from_reference(reference):
    return reference


@_handles("field-reference -> snake-reference field-reference-tail*")
def _indirect_field_reference(field_reference, field_references):
    if field_references.source_location.HasField("end"):
        end_location = field_references.source_location.end
    else:
        end_location = field_reference.source_location.end
    return ir_data.Expression(
        field_reference=ir_data.FieldReference(
            path=[field_reference] + field_references.list,
            source_location=parser_types.make_location(
                field_reference.source_location.start, end_location
            ),
        )
    )


# If "Type.field" ever becomes syntactically valid, it will be necessary to
# check that enum values are compile-time constants.
@_handles('field-reference-tail -> "." snake-reference')
def _field_reference_tail(dot, reference):
    del dot  # Unused.
    return reference


@_handles("numeric-constant -> Number")
def _numeric_constant(number):
    # All types of numeric constant tokenize to the same symbol, because they are
    # interchangeable in source code.
    if number.text[0:2] == "0b":
        n = int(number.text.replace("_", "")[2:], 2)
    elif number.text[0:2] == "0x":
        n = int(number.text.replace("_", "")[2:], 16)
    else:
        n = int(number.text.replace("_", ""), 10)
    return ir_data.NumericConstant(value=str(n))


@_handles("type-definition -> struct")
@_handles("type-definition -> bits")
@_handles("type-definition -> enum")
@_handles("type-definition -> external")
def _type_definition(type_definition):
    return type_definition


# struct StructureName:
#   ... fields ...
# bits BitName:
#   ... fields ...
@_handles(
    'struct -> "struct" type-name delimited-parameter-definition-list?'
    '          ":" Comment? eol struct-body'
)
@_handles(
    'bits -> "bits" type-name delimited-parameter-definition-list? ":"'
    "        Comment? eol bits-body"
)
def _structure(struct, name, parameters, colon, comment, newline, struct_body):
    """Composes the top-level IR for an Emboss structure."""
    del colon, comment, newline  # Unused.
    ir_data_utils.builder(struct_body.structure).source_location.start.CopyFrom(
        struct.source_location.start
    )
    ir_data_utils.builder(struct_body.structure).source_location.end.CopyFrom(
        struct_body.source_location.end
    )
    if struct_body.name:
        ir_data_utils.update(struct_body.name, name)
    else:
        struct_body.name = ir_data_utils.copy(name)
    if parameters.list:
        struct_body.runtime_parameter.extend(parameters.list[0].list)
    return struct_body


@_handles(
    "delimited-parameter-definition-list ->" '    "(" parameter-definition-list ")"'
)
def _delimited_parameter_definition_list(open_paren, parameters, close_paren):
    del open_paren, close_paren  # Unused
    return parameters


@_handles('parameter-definition -> snake-name ":" type')
def _parameter_definition(name, double_colon, parameter_type):
    del double_colon  # Unused
    return ir_data.RuntimeParameter(name=name, physical_type_alias=parameter_type)


@_handles('parameter-definition-list-tail -> "," parameter-definition')
def _parameter_definition_list_tail(comma, parameter):
    del comma  # Unused.
    return parameter


@_handles(
    "parameter-definition-list -> parameter-definition"
    "                             parameter-definition-list-tail*"
)
def _parameter_definition_list(head, tail):
    tail.list.insert(0, head)
    return tail


@_handles("parameter-definition-list ->")
def _empty_parameter_definition_list():
    return _List([])


# The body of a struct: basically, the part after the first line.
@_handles(
    "struct-body -> Indent doc-line* attribute-line*"
    "               type-definition* struct-field-block Dedent"
)
def _struct_body(indent, docs, attributes, types, fields, dedent):
    del indent, dedent  # Unused.
    return _structure_body(
        docs, attributes, types, fields, ir_data.AddressableUnit.BYTE
    )


def _structure_body(docs, attributes, types, fields, addressable_unit):
    """Constructs the body of a structure (bits or struct) definition."""
    return ir_data.TypeDefinition(
        structure=ir_data.Structure(field=[field.field for field in fields.list]),
        documentation=docs.list,
        attribute=attributes.list,
        subtype=types.list
        + [subtype for field in fields.list for subtype in field.subtypes],
        addressable_unit=addressable_unit,
    )


@_handles("struct-field-block ->")
@_handles("bits-field-block ->")
@_handles("anonymous-bits-field-block ->")
def _empty_field_block():
    return _List([])


@_handles(
    "struct-field-block ->" "    conditional-struct-field-block struct-field-block"
)
@_handles("bits-field-block ->" "    conditional-bits-field-block bits-field-block")
@_handles(
    "anonymous-bits-field-block -> conditional-anonymous-bits-field-block"
    "                              anonymous-bits-field-block"
)
def _conditional_block_plus_field_block(conditional_block, block):
    return _List(conditional_block.list + block.list)


@_handles("struct-field-block ->" "    unconditional-struct-field struct-field-block")
@_handles("bits-field-block ->" "    unconditional-bits-field bits-field-block")
@_handles(
    "anonymous-bits-field-block ->"
    "    unconditional-anonymous-bits-field anonymous-bits-field-block"
)
def _unconditional_block_plus_field_block(field, block):
    """Prepends an unconditional field to block."""
    ir_data_utils.builder(field.field).existence_condition.source_location.CopyFrom(
        field.source_location
    )
    ir_data_utils.builder(
        field.field
    ).existence_condition.boolean_constant.source_location.CopyFrom(
        field.source_location
    )
    ir_data_utils.builder(field.field).existence_condition.boolean_constant.value = True
    return _List([field] + block.list)


# Struct "fields" are regular fields, inline enums, bits, or structs, anonymous
# inline bits, or virtual fields.
@_handles("unconditional-struct-field -> field")
@_handles("unconditional-struct-field -> inline-enum-field-definition")
@_handles("unconditional-struct-field -> inline-bits-field-definition")
@_handles("unconditional-struct-field -> inline-struct-field-definition")
@_handles("unconditional-struct-field -> anonymous-bits-field-definition")
@_handles("unconditional-struct-field -> virtual-field")
# Bits fields are "regular" fields, inline enums or bits, or virtual fields.
#
# Inline structs and anonymous inline bits are not allowed inside of bits:
# anonymous inline bits are pointless, and inline structs do not make sense,
# since a struct cannot be a part of a bits.
#
# Anonymous inline bits may not include virtual fields; instead, the virtual
# field should be a direct part of the enclosing structure.
@_handles("unconditional-anonymous-bits-field -> field")
@_handles("unconditional-anonymous-bits-field -> inline-enum-field-definition")
@_handles("unconditional-anonymous-bits-field -> inline-bits-field-definition")
@_handles("unconditional-bits-field -> unconditional-anonymous-bits-field")
@_handles("unconditional-bits-field -> virtual-field")
def _unconditional_field(field):
    """Handles the unifying grammar production for a struct or bits field."""
    return field


# TODO(bolms): Add 'elif' and 'else' support.
# TODO(bolms): Should nested 'if' blocks be allowed?
@_handles(
    "conditional-struct-field-block ->"
    '    "if" expression ":" Comment? eol'
    "        Indent unconditional-struct-field+ Dedent"
)
@_handles(
    "conditional-bits-field-block ->"
    '    "if" expression ":" Comment? eol'
    "        Indent unconditional-bits-field+ Dedent"
)
@_handles(
    "conditional-anonymous-bits-field-block ->"
    '    "if" expression ":" Comment? eol'
    "        Indent unconditional-anonymous-bits-field+ Dedent"
)
def _conditional_field_block(
    if_keyword, expression, colon, comment, newline, indent, fields, dedent
):
    """Applies an existence_condition to each element of fields."""
    del if_keyword, newline, colon, comment, indent, dedent  # Unused.
    for field in fields.list:
        condition = ir_data_utils.builder(field.field).existence_condition
        condition.CopyFrom(expression)
        condition.source_location.is_disjoint_from_parent = True
    return fields


# The body of a bit field definition: basically, the part after the first line.
@_handles(
    "bits-body -> Indent doc-line* attribute-line*"
    "             type-definition* bits-field-block Dedent"
)
def _bits_body(indent, docs, attributes, types, fields, dedent):
    del indent, dedent  # Unused.
    return _structure_body(docs, attributes, types, fields, ir_data.AddressableUnit.BIT)


# Inline bits (defined as part of a field) are more restricted than standalone
# bits.
@_handles(
    "anonymous-bits-body ->"
    "    Indent attribute-line* anonymous-bits-field-block Dedent"
)
def _anonymous_bits_body(indent, attributes, fields, dedent):
    del indent, dedent  # Unused.
    return _structure_body(
        _List([]), attributes, _List([]), fields, ir_data.AddressableUnit.BIT
    )


# A field is:
#     range  type  name  (abbr)  [attr: value] [attr2: value] -- doc
#         -- doc
#         -- doc
#         [attr3: value]
#         [attr4: value]
@_handles(
    "field ->"
    "    field-location type snake-name abbreviation? attribute* doc?"
    "    Comment? eol field-body?"
)
def _field(
    location,
    field_type,
    name,
    abbreviation,
    attributes,
    doc,
    comment,
    newline,
    field_body,
):
    """Constructs an ir_data.Field from the given components."""
    del comment  # Unused
    field_ir = ir_data.Field(
        location=location,
        type=field_type,
        name=name,
        attribute=attributes.list,
        documentation=doc.list,
    )
    field = ir_data_utils.builder(field_ir)
    if field_body.list:
        field.attribute.extend(field_body.list[0].attribute)
        field.documentation.extend(field_body.list[0].documentation)
    if abbreviation.list:
        field.abbreviation.CopyFrom(abbreviation.list[0])
    field.source_location.start.CopyFrom(location.source_location.start)
    if field_body.source_location.HasField("end"):
        field.source_location.end.CopyFrom(field_body.source_location.end)
    else:
        field.source_location.end.CopyFrom(newline.source_location.end)
    return _FieldWithType(field=field_ir)


# A "virtual field" is:
#     let name = value
#         -- doc
#         -- doc
#         [attr1: value]
#         [attr2: value]
@_handles(
    "virtual-field ->" '    "let" snake-name "=" expression Comment? eol field-body?'
)
def _virtual_field(let, name, equals, value, comment, newline, field_body):
    """Constructs an ir_data.Field from the given components."""
    del equals, comment  # Unused
    field_ir = ir_data.Field(read_transform=value, name=name)
    field = ir_data_utils.builder(field_ir)
    if field_body.list:
        field.attribute.extend(field_body.list[0].attribute)
        field.documentation.extend(field_body.list[0].documentation)
    field.source_location.start.CopyFrom(let.source_location.start)
    if field_body.source_location.HasField("end"):
        field.source_location.end.CopyFrom(field_body.source_location.end)
    else:
        field.source_location.end.CopyFrom(newline.source_location.end)
    return _FieldWithType(field=field_ir)


# An inline enum is:
#     range  "enum"  name  (abbr):
#         -- doc
#         -- doc
#         [attr3: value]
#         [attr4: value]
#         NAME = 10
#         NAME2 = 20
@_handles(
    "inline-enum-field-definition ->"
    '    field-location "enum" snake-name abbreviation? ":" Comment? eol'
    "    enum-body"
)
def _inline_enum_field(
    location, enum, name, abbreviation, colon, comment, newline, enum_body
):
    """Constructs an ir_data.Field for an inline enum field."""
    del enum, colon, comment, newline  # Unused.
    return _inline_type_field(location, name, abbreviation, enum_body)


@_handles(
    "inline-struct-field-definition ->"
    '    field-location "struct" snake-name abbreviation? ":" Comment? eol'
    "    struct-body"
)
def _inline_struct_field(
    location, struct, name, abbreviation, colon, comment, newline, struct_body
):
    del struct, colon, comment, newline  # Unused.
    return _inline_type_field(location, name, abbreviation, struct_body)


@_handles(
    "inline-bits-field-definition ->"
    '    field-location "bits" snake-name abbreviation? ":" Comment? eol'
    "    bits-body"
)
def _inline_bits_field(
    location, bits, name, abbreviation, colon, comment, newline, bits_body
):
    del bits, colon, comment, newline  # Unused.
    return _inline_type_field(location, name, abbreviation, bits_body)


def _inline_type_field(location, name, abbreviation, body):
    """Shared implementation of _inline_enum_field and _anonymous_bit_field."""
    field_ir = ir_data.Field(
        location=location,
        name=name,
        attribute=body.attribute,
        documentation=body.documentation,
    )
    field = ir_data_utils.builder(field_ir)
    # All attributes should be attached to the field, not the type definition: if
    # the user wants to use type attributes, they should create a separate type
    # definition and reference it.
    del body.attribute[:]
    type_name = ir_data_utils.copy(name)
    ir_data_utils.builder(type_name).name.text = name_conversion.snake_to_camel(
        type_name.name.text
    )
    field.type.atomic_type.reference.source_name.extend([type_name.name])
    field.type.atomic_type.reference.source_location.CopyFrom(type_name.source_location)
    field.type.atomic_type.reference.is_local_name = True
    field.type.atomic_type.source_location.CopyFrom(type_name.source_location)
    field.type.source_location.CopyFrom(type_name.source_location)
    if abbreviation.list:
        field.abbreviation.CopyFrom(abbreviation.list[0])
    field.source_location.start.CopyFrom(location.source_location.start)
    ir_data_utils.builder(body.source_location).start.CopyFrom(
        location.source_location.start
    )
    if body.HasField("enumeration"):
        ir_data_utils.builder(body.enumeration).source_location.CopyFrom(
            body.source_location
        )
    else:
        assert body.HasField("structure")
        ir_data_utils.builder(body.structure).source_location.CopyFrom(
            body.source_location
        )
    ir_data_utils.builder(body).name.CopyFrom(type_name)
    field.source_location.end.CopyFrom(body.source_location.end)
    subtypes = [body] + list(body.subtype)
    del body.subtype[:]
    return _FieldWithType(field=field_ir, subtypes=subtypes)


@_handles(
    "anonymous-bits-field-definition ->"
    '    field-location "bits" ":" Comment? eol anonymous-bits-body'
)
def _anonymous_bit_field(location, bits_keyword, colon, comment, newline, bits_body):
    """Constructs an ir_data.Field for an anonymous bit field."""
    del colon, comment, newline  # Unused.
    name = ir_data.NameDefinition(
        name=ir_data.Word(
            text=_get_anonymous_field_name(),
            source_location=bits_keyword.source_location,
        ),
        source_location=bits_keyword.source_location,
        is_anonymous=True,
    )
    return _inline_type_field(location, name, _List([]), bits_body)


@_handles("field-body -> Indent doc-line* attribute-line* Dedent")
def _field_body(indent, docs, attributes, dedent):
    del indent, dedent  # Unused.
    return ir_data.Field(documentation=docs.list, attribute=attributes.list)


# A parenthetically-denoted abbreviation.
@_handles('abbreviation -> "(" snake-word ")"')
def _abbreviation(open_paren, word, close_paren):
    del open_paren, close_paren  # Unused.
    return word


# enum EnumName:
#   ... values ...
@_handles('enum -> "enum" type-name ":" Comment? eol enum-body')
def _enum(enum, name, colon, comment, newline, enum_body):
    del colon, comment, newline  # Unused.
    ir_data_utils.builder(enum_body.enumeration).source_location.start.CopyFrom(
        enum.source_location.start
    )
    ir_data_utils.builder(enum_body.enumeration).source_location.end.CopyFrom(
        enum_body.source_location.end
    )
    ir_data_utils.builder(enum_body).name.CopyFrom(name)
    return enum_body


# [enum Foo:]
#   name = value
#   name = value
@_handles("enum-body -> Indent doc-line* attribute-line* enum-value+ Dedent")
def _enum_body(indent, docs, attributes, values, dedent):
    del indent, dedent  # Unused.
    return ir_data.TypeDefinition(
        enumeration=ir_data.Enum(value=values.list),
        documentation=docs.list,
        attribute=attributes.list,
        addressable_unit=ir_data.AddressableUnit.BIT,
    )


# name = value
@_handles(
    "enum-value -> "
    '    constant-name "=" expression attribute* doc? Comment? eol enum-value-body?'
)
def _enum_value(
    name, equals, expression, attribute, documentation, comment, newline, body
):
    del equals, comment, newline  # Unused.
    result = ir_data.EnumValue(
        name=name,
        value=expression,
        documentation=documentation.list,
        attribute=attribute.list,
    )
    if body.list:
        result.documentation.extend(body.list[0].documentation)
        result.attribute.extend(body.list[0].attribute)
    return result


@_handles("enum-value-body -> Indent doc-line* attribute-line* Dedent")
def _enum_value_body(indent, docs, attributes, dedent):
    del indent, dedent  # Unused.
    return ir_data.EnumValue(documentation=docs.list, attribute=attributes.list)


# An external is just a declaration that a type exists and has certain
# attributes.
@_handles('external -> "external" type-name ":" Comment? eol external-body')
def _external(external, name, colon, comment, newline, external_body):
    del colon, comment, newline  # Unused.
    ir_data_utils.builder(external_body.source_location).start.CopyFrom(
        external.source_location.start
    )
    if external_body.name:
        ir_data_utils.update(external_body.name, name)
    else:
        external_body.name = ir_data_utils.copy(name)
    return external_body


# This syntax implicitly requires either a documentation line or a attribute
# line, or it won't parse (because no Indent/Dedent tokens will be emitted).
@_handles("external-body -> Indent doc-line* attribute-line* Dedent")
def _external_body(indent, docs, attributes, dedent):
    return ir_data.TypeDefinition(
        external=ir_data.External(
            # Set source_location here, since it won't be set automatically.
            source_location=ir_data.Location(
                start=indent.source_location.start, end=dedent.source_location.end
            )
        ),
        documentation=docs.list,
        attribute=attributes.list,
    )


@_handles('field-location -> expression "[" "+" expression "]"')
def _field_location(start, open_bracket, plus, size, close_bracket):
    del open_bracket, plus, close_bracket  # Unused.
    return ir_data.FieldLocation(start=start, size=size)


@_handles('delimited-argument-list -> "(" argument-list ")"')
def _type_argument_list(open_paren, arguments, close_paren):
    del open_paren, close_paren  # Unused
    return arguments


# A type is "TypeName" or "TypeName[length]" or "TypeName[length][length]", etc.
# An array type may have an empty length ("Type[]").  This is only valid for the
# outermost length (the last set of brackets), but that must be checked
# elsewhere.
@_handles(
    "type -> type-reference delimited-argument-list? type-size-specifier?"
    "        array-length-specifier*"
)
def _type(reference, parameters, size, array_spec):
    """Builds the IR for a type specifier."""
    base_type_source_location_end = reference.source_location.end
    atomic_type_source_location_end = reference.source_location.end
    if parameters.list:
        base_type_source_location_end = parameters.source_location.end
        atomic_type_source_location_end = parameters.source_location.end
    if size.list:
        base_type_source_location_end = size.source_location.end
    base_type_location = parser_types.make_location(
        reference.source_location.start, base_type_source_location_end
    )
    atomic_type_location = parser_types.make_location(
        reference.source_location.start, atomic_type_source_location_end
    )
    t = ir_data.Type(
        atomic_type=ir_data.AtomicType(
            reference=ir_data_utils.copy(reference),
            source_location=atomic_type_location,
            runtime_parameter=parameters.list[0].list if parameters.list else [],
        ),
        size_in_bits=size.list[0] if size.list else None,
        source_location=base_type_location,
    )
    for length in array_spec.list:
        location = parser_types.make_location(
            t.source_location.start, length.source_location.end
        )
        if isinstance(length, ir_data.Expression):
            t = ir_data.Type(
                array_type=ir_data.ArrayType(
                    base_type=t, element_count=length, source_location=location
                ),
                source_location=location,
            )
        elif isinstance(length, ir_data.Empty):
            t = ir_data.Type(
                array_type=ir_data.ArrayType(
                    base_type=t, automatic=length, source_location=location
                ),
                source_location=location,
            )
        else:
            assert False, "Shouldn't be here."
    return t


# TODO(bolms): Should symbolic names or expressions be allowed?  E.g.,
# UInt:FIELD_SIZE or UInt:(16 + 16)?
@_handles('type-size-specifier -> ":" numeric-constant')
def _type_size_specifier(colon, numeric_constant):
    """handles the ":32" part of a type specifier like "UInt:32"."""
    del colon
    return ir_data.Expression(constant=numeric_constant)


# The distinctions between different formats of NameDefinitions, Words, and
# References are enforced during parsing, but not propagated to the IR.
@_handles("type-name -> type-word")
@_handles("snake-name -> snake-word")
@_handles("constant-name -> constant-word")
def _name(word):
    return ir_data.NameDefinition(name=word)


@_handles("type-word -> CamelWord")
@_handles("snake-word -> SnakeWord")
@_handles('builtin-field-word -> "$size_in_bits"')
@_handles('builtin-field-word -> "$size_in_bytes"')
@_handles('builtin-field-word -> "$max_size_in_bits"')
@_handles('builtin-field-word -> "$max_size_in_bytes"')
@_handles('builtin-field-word -> "$min_size_in_bits"')
@_handles('builtin-field-word -> "$min_size_in_bytes"')
@_handles('builtin-word -> "$is_statically_sized"')
@_handles('builtin-word -> "$static_size_in_bits"')
@_handles('builtin-word -> "$next"')
@_handles("constant-word -> ShoutyWord")
@_handles('and-operator -> "&&"')
@_handles('or-operator -> "||"')
@_handles('less-operator -> "<="')
@_handles('less-operator -> "<"')
@_handles('greater-operator -> ">="')
@_handles('greater-operator -> ">"')
@_handles('equality-operator -> "=="')
@_handles('inequality-operator -> "!="')
@_handles('additive-operator -> "+"')
@_handles('additive-operator -> "-"')
@_handles('multiplicative-operator -> "*"')
@_handles('function-name -> "$max"')
@_handles('function-name -> "$present"')
@_handles('function-name -> "$upper_bound"')
@_handles('function-name -> "$lower_bound"')
def _word(word):
    return ir_data.Word(text=word.text)


@_handles("type-reference -> type-reference-tail")
@_handles("constant-reference -> constant-reference-tail")
def _un_module_qualified_type_reference(reference):
    return reference


@_handles("constant-reference-tail -> constant-word")
@_handles("type-reference-tail -> type-word")
@_handles("snake-reference -> snake-word")
@_handles("snake-reference -> builtin-field-word")
def _reference(word):
    return ir_data.Reference(source_name=[word])


@_handles("builtin-reference -> builtin-word")
def _builtin_reference(word):
    return ir_data.Reference(
        source_name=[word],
        canonical_name=ir_data.CanonicalName(object_path=[word.text]),
    )


# Because constant-references ("Enum.NAME") are used in the same contexts as
# field-references ("field.subfield"), module-qualified constant references
# ("module.Enum.VALUE") have to take snake-reference, not snake-word, on the
# left side of the dot.  Otherwise, when a "snake_word" is followed by a "." in
# an expression context, the LR(1) parser cannot determine whether to reduce the
# snake-word to snake-reference (to eventually become field-reference), or to
# shift the dot onto the stack (to eventually become constant-reference).  By
# using snake-reference as the head of both, the parser can always reduce, then
# shift the dot, then determine whether to proceed with constant-reference if it
# sees "snake_name.TypeName" or field-reference if it sees
# "snake_name.snake_name".
@_handles('constant-reference -> snake-reference "." constant-reference-tail')
def _module_qualified_constant_reference(new_head, dot, reference):
    del dot  # Unused.
    new_source_name = list(new_head.source_name) + list(reference.source_name)
    del reference.source_name[:]
    reference.source_name.extend(new_source_name)
    return reference


@_handles('constant-reference-tail -> type-word "." constant-reference-tail')
# module.Type.SubType.name is a reference to something that *must* be a
# constant.
@_handles('constant-reference-tail -> type-word "." snake-reference')
@_handles('type-reference-tail -> type-word "." type-reference-tail')
@_handles('type-reference -> snake-word "." type-reference-tail')
def _qualified_reference(word, dot, reference):
    """Adds a name. or Type. qualification to the head of a reference."""
    del dot  # Unused.
    new_source_name = [word] + list(reference.source_name)
    del reference.source_name[:]
    reference.source_name.extend(new_source_name)
    return reference


# Arrays are properly translated to IR in _type().
@_handles('array-length-specifier -> "[" expression "]"')
def _array_length_specifier(open_bracket, length, close_bracket):
    del open_bracket, close_bracket  # Unused.
    return length


# An array specifier can end with empty brackets ("arr[3][]"), in which case the
# array's size is inferred from the size of its enclosing field.
@_handles('array-length-specifier -> "[" "]"')
def _auto_array_length_specifier(open_bracket, close_bracket):
    # Note that the Void's source_location is the space between the brackets (if
    # any).
    return ir_data.Empty(
        source_location=ir_data.Location(
            start=open_bracket.source_location.end,
            end=close_bracket.source_location.start,
        )
    )


@_handles('eol -> "\\n" comment-line*')
def _eol(eol, comments):
    del comments  # Unused
    return eol


@_handles('comment-line -> Comment? "\\n"')
def _comment_line(comment, eol):
    del comment  # Unused
    return eol


def _finalize_grammar():
    """_Finalize adds productions for foo*, foo+, and foo? symbols."""
    star_symbols = set()
    plus_symbols = set()
    option_symbols = set()
    for production in _handlers:
        for symbol in production.rhs:
            if symbol[-1] == "*":
                star_symbols.add(symbol[:-1])
            elif symbol[-1] == "+":
                # symbol+ relies on the rule for symbol*
                star_symbols.add(symbol[:-1])
                plus_symbols.add(symbol[:-1])
            elif symbol[-1] == "?":
                option_symbols.add(symbol[:-1])
    for symbol in star_symbols:
        _handles("{s}* -> {s} {s}*".format(s=symbol))(lambda e, r: _List([e] + r.list))
        _handles("{s}* ->".format(s=symbol))(lambda: _List([]))
    for symbol in plus_symbols:
        _handles("{s}+ -> {s} {s}*".format(s=symbol))(lambda e, r: _List([e] + r.list))
    for symbol in option_symbols:
        _handles("{s}? -> {s}".format(s=symbol))(lambda e: _List([e]))
        _handles("{s}? ->".format(s=symbol))(lambda: _List([]))


_finalize_grammar()

# End of grammar.
################################################################################

# These export the grammar used by module_ir so that parser_generator can build
# a parser for the same language.
START_SYMBOL = "module"
EXPRESSION_START_SYMBOL = "expression"
PRODUCTIONS = list(_handlers.keys())