Return 2^n distinct MatchQuery objects in a CompoundMatchQuery.

    Given a MatchQuery containing `n` optional traverses that expand vertex fields,
    construct `2^n` different MatchQuery objects:
    one for each possible subset of optional edges that can be followed.
    For each edge `e` in a subset of optional edges chosen to be omitted,
    discard all traversals following `e`, and add filters specifying that `e` *does not exist*.

    Args:
        match_query: MatchQuery object containing n `@optional` scopes which expand vertex fields
        complex_optional_roots: list of @optional locations (location preceding an @optional
                                traverse) that expand vertex fields within
        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

    Returns:
        CompoundMatchQuery object containing 2^n MatchQuery objects,
        one for each possible subset of the n optional edges being followed

def convert_optional_traversals_to_compound_match_query(
        match_query, complex_optional_roots, location_to_optional_roots):
    """Return 2^n distinct MatchQuery objects in a CompoundMatchQuery.

    Given a MatchQuery containing `n` optional traverses that expand vertex fields,
    construct `2^n` different MatchQuery objects:
    one for each possible subset of optional edges that can be followed.
    For each edge `e` in a subset of optional edges chosen to be omitted,
    discard all traversals following `e`, and add filters specifying that `e` *does not exist*.

    Args:
        match_query: MatchQuery object containing n `@optional` scopes which expand vertex fields
        complex_optional_roots: list of @optional locations (location preceding an @optional
                                traverse) that expand vertex fields within
        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

    Returns:
        CompoundMatchQuery object containing 2^n MatchQuery objects,
        one for each possible subset of the n optional edges being followed
    """
    tree = construct_optional_traversal_tree(
        complex_optional_roots, location_to_optional_roots)
    rooted_optional_root_location_subsets = tree.get_all_rooted_subtrees_as_lists()

    omitted_location_subsets = [
        set(complex_optional_roots) - set(subset)
        for subset in rooted_optional_root_location_subsets
    ]
    sorted_omitted_location_subsets = sorted(omitted_location_subsets)

    compound_match_traversals = []
    for omitted_locations in reversed(sorted_omitted_location_subsets):
        new_match_traversals = []
        for match_traversal in match_query.match_traversals:
            location = match_traversal[0].as_block.location
            optional_root_locations_stack = location_to_optional_roots.get(location, None)
            if optional_root_locations_stack is not None:
                optional_root_location = optional_root_locations_stack[-1]
            else:
                optional_root_location = None

            if optional_root_location is None or optional_root_location not in omitted_locations:
                new_match_traversal = _prune_traverse_using_omitted_locations(
                    match_traversal, set(omitted_locations),
                    complex_optional_roots, location_to_optional_roots)
                new_match_traversals.append(new_match_traversal)
            else:
                # The root_block is within an omitted scope.
                # Discard the entire match traversal (do not append to new_match_traversals)
                pass

        compound_match_traversals.append(new_match_traversals)

    match_queries = [
        MatchQuery(
            match_traversals=match_traversals,
            folds=match_query.folds,
            output_block=match_query.output_block,
            where_block=match_query.where_block,
        )
        for match_traversals in compound_match_traversals
    ]

    return CompoundMatchQuery(match_queries=match_queries)