Classify query locations into three groups: preferred, eligible, ineligible.

    - Ineligible locations are ones that cannot be the starting point of query execution.
      These include locations within recursions, locations that are the target of
      an optional traversal, and locations with an associated "where:" clause with non-local filter.
    - Preferred locations are ones that are eligible to be the starting point, and also have
      an associated "where:" clause that references no non-local fields -- only local fields,
      literals, and variables.
    - Eligible locations are all locations that do not fall into either of these two categories.

    Args:
        match_query: MatchQuery object describing the query being analyzed for optimization

    Returns:
        tuple (preferred, eligible, ineligible) where each element is a set of Location objects.
        The three sets are disjoint.

def _classify_query_locations(match_query):
    """Classify query locations into three groups: preferred, eligible, ineligible.

    - Ineligible locations are ones that cannot be the starting point of query execution.
      These include locations within recursions, locations that are the target of
      an optional traversal, and locations with an associated "where:" clause with non-local filter.
    - Preferred locations are ones that are eligible to be the starting point, and also have
      an associated "where:" clause that references no non-local fields -- only local fields,
      literals, and variables.
    - Eligible locations are all locations that do not fall into either of these two categories.

    Args:
        match_query: MatchQuery object describing the query being analyzed for optimization

    Returns:
        tuple (preferred, eligible, ineligible) where each element is a set of Location objects.
        The three sets are disjoint.
    """
    preferred_locations = set()
    eligible_locations = set()
    ineligible_locations = set()

    # Any query must have at least one traversal with at least one step.
    # The first step in this traversal must be a QueryRoot.
    first_match_step = match_query.match_traversals[0][0]
    if not isinstance(first_match_step.root_block, QueryRoot):
        raise AssertionError(u'First step of first traversal unexpectedly was not QueryRoot: '
                             u'{} {}'.format(first_match_step, match_query))

    # The first step in the first traversal cannot possibly be inside an optional, recursion,
    # or fold. Its location is always an eligible start location for a query.
    # We need to determine whether it is merely eligible, or actually a preferred location.
    if first_match_step.where_block is not None:
        if _is_local_filter(first_match_step.where_block):
            preferred_locations.add(first_match_step.as_block.location)
        else:
            # TODO(predrag): Fix once we have a proper fix for tag-and-filter in the same scope.
            #                Either the locally-scoped tag will have to generate a LocalField
            #                instead of a ContextField, or we'll have to rework the local filter
            #                detection code in this module.
            raise AssertionError(u'The first step of the first traversal somehow had a non-local '
                                 u'filter. This should not be possible, since there is nowhere '
                                 u'for the tagged value to have come from. Values: {} {}'
                                 .format(first_match_step, match_query))
    else:
        eligible_locations.add(first_match_step.as_block.location)

    # This loop will repeat the analysis of the first step of the first traversal.
    # QueryRoots other than the first are required to always be at a location whose status
    # (preferred / eligible / ineligible) is already known. Since we already processed
    # the first QueryRoot above, the rest of the loop can assume all QueryRoots are like that.
    for current_traversal in match_query.match_traversals:
        for match_step in current_traversal:
            current_step_location = match_step.as_block.location

            if isinstance(match_step.root_block, QueryRoot):
                already_encountered_location = any((
                    current_step_location in preferred_locations,
                    current_step_location in eligible_locations,
                    current_step_location in ineligible_locations,
                ))

                if not already_encountered_location:
                    raise AssertionError(u'Unexpectedly encountered a location in QueryRoot whose '
                                         u'status has not been determined: {} {} {}'
                                         .format(current_step_location, match_step, match_query))

                at_eligible_or_preferred_location = (
                    current_step_location in preferred_locations or
                    current_step_location in eligible_locations)

                # This location has already been encountered and processed.
                # Other than setting the "at_eligible_or_preferred_location" state for the sake of
                # the following MATCH steps, there is nothing further to be done.
                continue
            elif isinstance(match_step.root_block, Recurse):
                # All Recurse blocks cause locations within to be ineligible.
                at_eligible_or_preferred_location = False
            elif isinstance(match_step.root_block, Traverse):
                # Optional Traverse blocks cause locations within to be ineligible.
                # Non-optional Traverse blocks do not change the eligibility of locations within:
                # if the pre-Traverse location was eligible, so will the location within,
                # and if it was not eligible, neither will the location within.
                if match_step.root_block.optional:
                    at_eligible_or_preferred_location = False
            else:
                raise AssertionError(u'Unreachable condition reached: {} {} {}'
                                     .format(match_step.root_block, match_step, match_query))

            if not at_eligible_or_preferred_location:
                ineligible_locations.add(current_step_location)
            elif match_step.where_block is not None:
                if _is_local_filter(match_step.where_block):
                    # This location has a local filter, and is not otherwise ineligible (it's not
                    # in a recursion etc.). Therefore, it's a preferred query start location.
                    preferred_locations.add(current_step_location)
                else:
                    # Locations with non-local filters are never eligible locations, since they
                    # depend on another location being executed before them.
                    ineligible_locations.add(current_step_location)
            else:
                # No local filtering (i.e. not preferred), but also not ineligible. Eligible it is.
                eligible_locations.add(current_step_location)

    return preferred_locations, eligible_locations, ineligible_locations