Construct a mapping from locations within @optional to their correspoding optional Traverse.

    Args:
        ir_blocks: list of IR blocks to extract optional data from

    Returns:
        tuple (complex_optional_roots, location_to_optional_roots):
        complex_optional_roots: list of @optional locations (location immmediately preceding
                                an @optional Traverse) that expand vertex fields
        location_to_optional_roots: dict mapping from location -> optional_roots where location is
                                    within some number of @optionals and optional_roots is a list
                                    of optional root locations preceding the successive @optional
                                    scopes within which the location resides

def extract_optional_location_root_info(ir_blocks):
    """Construct a mapping from locations within @optional to their correspoding optional Traverse.

    Args:
        ir_blocks: list of IR blocks to extract optional data from

    Returns:
        tuple (complex_optional_roots, location_to_optional_roots):
        complex_optional_roots: list of @optional locations (location immmediately preceding
                                an @optional Traverse) that expand vertex fields
        location_to_optional_roots: dict mapping from location -> optional_roots where location is
                                    within some number of @optionals and optional_roots is a list
                                    of optional root locations preceding the successive @optional
                                    scopes within which the location resides
    """
    complex_optional_roots = []
    location_to_optional_roots = dict()

    # These are both stacks that perform depth-first search on the tree of @optional edges.
    # At any given location they contain
    # - in_optional_root_locations: all the optional root locations
    # - encountered_traverse_within_optional: whether the optional is complex or not
    # in order that they appear on the path from the root to that location.
    in_optional_root_locations = []
    encountered_traverse_within_optional = []

    # Blocks within folded scopes should not be taken into account in this function.
    _, non_folded_ir_blocks = extract_folds_from_ir_blocks(ir_blocks)

    preceding_location = None
    for current_block in non_folded_ir_blocks:
        if len(in_optional_root_locations) > 0 and isinstance(current_block, (Traverse, Recurse)):
            encountered_traverse_within_optional[-1] = True

        if isinstance(current_block, Traverse) and current_block.optional:
            if preceding_location is None:
                raise AssertionError(u'No MarkLocation found before an optional Traverse: {} {}'
                                     .format(current_block, non_folded_ir_blocks))

            in_optional_root_locations.append(preceding_location)
            encountered_traverse_within_optional.append(False)
        elif isinstance(current_block, EndOptional):
            if len(in_optional_root_locations) == 0:
                raise AssertionError(u'in_optional_root_locations was empty at an EndOptional '
                                     u'block: {}'.format(ir_blocks))

            if encountered_traverse_within_optional[-1]:
                complex_optional_roots.append(in_optional_root_locations[-1])

            in_optional_root_locations.pop()
            encountered_traverse_within_optional.pop()
        elif isinstance(current_block, MarkLocation):
            preceding_location = current_block.location
            if len(in_optional_root_locations) != 0:
                # in_optional_root_locations will not be empty if and only if we are within an
                # @optional scope. In this case, we add the current location to the dictionary
                # mapping it to the sequence of optionals locations leading up to it.
                optional_root_locations_stack = tuple(in_optional_root_locations)
                location_to_optional_roots[current_block.location] = optional_root_locations_stack
        else:
            # No locations need to be marked, and no optional scopes begin or end here.
            pass

    return complex_optional_roots, location_to_optional_roots