"""
- Authors: Peter Mawhorter
- Consulted:
- Date: 2022-10-24
- Purpose: Analysis functions for decision graphs an explorations.
"""

from typing import (
    List, Dict, Tuple, Optional, TypeVar, Callable, Union, Any,
    ParamSpec, Concatenate, Set, cast, Type, TypeAlias, Literal,
    TypedDict, Protocol, Sequence, Callable, Collection, FrozenSet,
    get_args
)

from types import FunctionType

from . import base, core, parsing

import textwrap
import functools
import inspect
import time
import copy
import sys

import networkx as nx


#-------------------#
# Text descriptions #
#-------------------#

def describeConsequence(consequence: base.Consequence) -> str:
    """
    Returns a string which concisely describes a consequence list.
    Returns an empty string if given an empty consequence. Examples:

    >>> describeConsequence([])
    ''
    >>> describeConsequence([
    ...     base.effect(gain=('gold', 5), delay=2, charges=3),
    ...     base.effect(lose='flight')
    ... ])
    'gain gold*5 ,2 =3; lose flight'
    >>> from . import commands
    >>> d = describeConsequence([
    ...     base.effect(edit=[
    ...         [
    ...             commands.command('val', '5'),
    ...             commands.command('empty', 'list'),
    ...             commands.command('append')
    ...         ],
    ...         [
    ...             commands.command('val', '11'),
    ...             commands.command('assign', 'var'),
    ...             commands.command('op', '+', '$var', '$var')
    ...         ],
    ...     ])
    ... ])
    >>> d
    'with consequences:\
\\n    edit {\
\\n      val 5;\
\\n      empty list;\
\\n      append $_;\
\\n    } {\
\\n      val 11;\
\\n      assign var $_;\
\\n      op + $var $var;\
\\n    }\
\\n'
    >>> for line in d.splitlines():
    ...     print(line)
    with consequences:
        edit {
          val 5;
          empty list;
          append $_;
        } {
          val 11;
          assign var $_;
          op + $var $var;
        }
    """
    edesc = ''
    pf = parsing.ParseFormat()
    if consequence:
        parts = []
        for item in consequence:
            # TODO: Challenges and Conditions here!
            if 'skills' in item:  # a Challenge
                item = cast(base.Challenge, item)
                parts.append(pf.unparseChallenge(item))
            elif 'value' in item:  # an Effect
                item = cast(base.Effect, item)
                parts.append(pf.unparseEffect(item))
            elif 'condition' in item:  # a Condition
                item = cast(base.Condition, item)
                parts.append(pf.unparseCondition(item))
            else:
                raise TypeError(
                    f"Invalid consequence item (no 'skills', 'value', or"
                    f" 'condition' key found):\n{repr(item)}"
                )
        edesc = '; '.join(parts)
        if len(edesc) > 60 or '\n' in edesc:
            edesc = 'with consequences:\n' + ';\n'.join(
                textwrap.indent(part, '    ')
                for part in parts
            ) + '\n'

    return edesc


def describeProgress(exploration: core.DiscreteExploration) -> str:
    """
    Describes the progress of an exploration by noting each room/zone
    visited and explaining the options visible at each point plus which
    option was taken. Notes powers/tokens gained/lost along the way.
    Returns a string.

    Example:
    >>> from exploration import journal
    >>> e = journal.convertJournal('''\\
    ... S Start::pit
    ... A gain jump
    ... A gain attack
    ... n button check
    ... zz Wilds
    ... o up
    ...   q _flight
    ... o left
    ... xt left left_nook right
    ... a geo_rock
    ...   At gain geo*15
    ...   At deactivate
    ... o up
    ...   q _tall_narrow
    ... t right
    ... o right
    ...   q attack
    ... ''')
    >>> for line in describeProgress(e).splitlines():
    ...    print(line)
    Start of the exploration
    Start exploring domain main at 0 (Start::pit)
      Gained capability 'attack'
      Gained capability 'jump'
    At decision 0 (Start::pit)
      In zone Start
      In region Wilds
      There are transitions:
        left to unconfirmed
        up to unconfirmed; requires _flight
      1 note(s) at this step
    Explore left from decision 0 (Start::pit) to 2 (now Start::left_nook)
    At decision 2 (Start::left_nook)
      There are transitions:
        right to 0 (Start::pit)
      There are actions:
        geo_rock
    Do action geo_rock
      Gained 15 geo(s)
    Take right from decision 2 (Start::left_nook) to 0 (Start::pit)
    At decision 0 (Start::pit)
      There are transitions:
        left to 2 (Start::left_nook)
        right to unconfirmed; requires attack
        up to unconfirmed; requires _flight
    Waiting for another action...
    End of the exploration.
    """
    result = ''

    regions: Set[base.Zone] = set()
    zones: Set[base.Zone] = set()
    last: Union[base.DecisionID, Set[base.DecisionID], None] = None
    lastState: base.State = base.emptyState()
    prevCapabilities = base.effectiveCapabilitySet(lastState)
    prevMechanisms = lastState['mechanisms']
    oldActiveDecisions: Set[base.DecisionID] = set()
    for i, situation in enumerate(exploration):
        if i == 0:
            result += "Start of the exploration\n"

        # Extract info
        graph = situation.graph
        activeDecisions = exploration.getActiveDecisions(i)
        newActive = activeDecisions - oldActiveDecisions
        departedFrom = exploration.movementAtStep(i)[0]
        # TODO: use the other parts of this?
        nowZones: Set[base.Zone] = set()
        for active in activeDecisions:
            nowZones |= graph.zoneAncestors(active)
        regionsHere = set(
            z
            for z in nowZones
            if graph.zoneHierarchyLevel(z) == 1
        )
        zonesHere = set(
            z
            for z in nowZones
            if graph.zoneHierarchyLevel(z) == 0
        )
        here = departedFrom
        state = situation.state
        capabilities = base.effectiveCapabilitySet(state)
        mechanisms = state['mechanisms']

        # Describe capabilities gained/lost relative to previous step
        # (i.e., as a result of the previous action)
        gained = (
            capabilities['capabilities']
          - prevCapabilities['capabilities']
        )
        gainedTokens = []
        for tokenType in capabilities['tokens']:
            net = (
                capabilities['tokens'][tokenType]
              - prevCapabilities['tokens'].get(tokenType, 0)
            )
            if net != 0:
                gainedTokens.append((tokenType, net))
        changed = [
            mID
            for mID in list(mechanisms.keys()) + list(prevMechanisms.keys())
            if mechanisms.get(mID) != prevMechanisms.get(mID)
        ]

        for capability in sorted(gained):
            result += f"  Gained capability '{capability}'\n"

        for tokenType, net in gainedTokens:
            if net > 0:
                result += f"  Gained {net} {tokenType}(s)\n"
            else:
                result += f"  Lost {-net} {tokenType}(s)\n"

        for mID in changed:
            oldState = prevMechanisms.get(mID, base.DEFAULT_MECHANISM_STATE)
            newState = mechanisms.get(mID, base.DEFAULT_MECHANISM_STATE)

            details = graph.mechanismDetails(mID)
            if details is None:
                mName = "(unknown)"
            else:
                mName = details[1]
            result += (
                f"  Set mechanism {mID} ({mName}) to {newState} (was"
                f" {oldState})"
            )
            # TODO: Test this!

        if isinstance(departedFrom, base.DecisionID):
            # Print location info
            if here != last:
                if here is None:
                    result += "Without a position...\n"
                elif isinstance(here, set):
                    result += f"With {len(here)} active decisions\n"
                    # TODO: List them using namesListing?
                else:
                    result += f"At decision {graph.identityOf(here)}\n"
            newZones = zonesHere - zones
            for zone in sorted(newZones):
                result += f"  In zone {zone}\n"
            newRegions = regionsHere - regions
            for region in sorted(newRegions):
                result += f"  In region {region}\n"

        elif isinstance(departedFrom, set):  # active in spreading domain
            spreadingDomain = graph.domainFor(list(departedFrom)[0])
            result += (
                f"  In domain {spreadingDomain} with {len(departedFrom)}"
                f" active decisions...\n"
            )

        else:
            assert departedFrom is None

        # Describe new position/positions at start of this step
        if len(newActive) > 1:
            newListing = ', '.join(
                sorted(graph.identityOf(n) for n in newActive)
            )
            result += (
                f"  There are {len(newActive)} new active decisions:"
                f"\n  {newListing}"
            )

        elif len(newActive) == 1:
            here = list(newActive)[0]

            outgoing = graph.destinationsFrom(here)

            transitions = {t: d for (t, d) in outgoing.items() if d != here}
            actions = {t: d for (t, d) in outgoing.items() if d == here}
            if transitions:
                result += "  There are transitions:\n"
                for transition in sorted(transitions):
                    dest = transitions[transition]
                    if not graph.isConfirmed(dest):
                        destSpec = 'unconfirmed'
                    else:
                        destSpec = graph.identityOf(dest)
                    req = graph.getTransitionRequirement(here, transition)
                    rDesc = ''
                    if req != base.ReqNothing():
                        rDesc = f"; requires {req.unparse()}"
                    cDesc = describeConsequence(
                        graph.getConsequence(here, transition)
                    )
                    if cDesc:
                        cDesc = '; ' + cDesc
                    result += (
                        f"    {transition} to {destSpec}{rDesc}{cDesc}\n"
                    )

            if actions:
                result += "  There are actions:\n"
                for action in sorted(actions):
                    req = graph.getTransitionRequirement(here, action)
                    rDesc = ''
                    if req != base.ReqNothing():
                        rDesc = f"; requires {req.unparse()}"
                    cDesc = describeConsequence(
                        graph.getConsequence(here, action)
                    )
                    if cDesc:
                        cDesc = '; ' + cDesc
                    if rDesc or cDesc:
                        desc = (rDesc + cDesc)[2:]  # chop '; ' from either
                        result += f"    {action} ({desc})\n"
                    else:
                        result += f"    {action}\n"

        # note annotations
        if len(situation.annotations) > 0:
            result += (
                f"  {len(situation.annotations)} note(s) at this step\n"
            )

        # Describe action taken
        if situation.action is None and situation.type == "pending":
            result += "Waiting for another action...\n"
        else:
            desc = base.describeExplorationAction(situation, situation.action)
            desc = desc[0].capitalize() + desc[1:]
            result += desc + '\n'

        if i == len(exploration) - 1:
            result += "End of the exploration.\n"

        # Update state variables
        oldActiveDecisions = activeDecisions
        prevCapabilities = capabilities
        prevMechanisms = mechanisms
        regions = regionsHere
        zones = zonesHere
        if here is not None:
            last = here
        lastState = state

    return result


#-----------------------#
# Analysis result types #
#-----------------------#

AnalysisUnit: 'TypeAlias' = Literal[
    'step',
    'stepDecision',
    'stepTransition',
    'decision',
    'transition',
    'finalTransition',
    'exploration',
]
"""
The different kinds of analysis units we consider: per-step-per-decision,
per-step-per-transition, per-step, per-ever-decision, per-ever-transition,
per-final-transition, and per-exploration (i.e. overall).
"""


AnalysisResults: 'TypeAlias' = Dict[str, Any]
"""
Analysis results are dictionaries that map analysis routine names to
results from those routines, which can be of any type.
"""


SpecificTransition: 'TypeAlias' = Tuple[base.DecisionID, base.Transition]
"""
A specific transition is identified by its source decision ID and its
transition name. Note that transitions which get renamed are treated as
two separate transitions.
"""

OverspecificTransition: 'TypeAlias' = Tuple[
    base.DecisionID,
    base.Transition,
    base.DecisionID
]
"""
In contrast to a `SpecificTransition`, an `OverspecificTransition`
includes the destination of the transition, which might help disambiguate
cases where a transition is created, then re-targeted or deleted and
re-created with a different destination. Transitions which get renamed
still are treated as two separate transitions.
"""

DecisionAnalyses: 'TypeAlias' = Dict[base.DecisionID, AnalysisResults]
"""
Decision analysis results are stored per-decision, with a dictionary of
property-name → value associations. These properties either apply to
decisions across all steps of an exploration, or apply to decisions in a
particular `core.DecisionGraph`.
"""

TransitionAnalyses: 'TypeAlias' = Dict[OverspecificTransition, AnalysisResults]
"""
Per-transition analysis results, similar to `DecisionAnalyses`.
"""

FinalTransitionAnalyses: 'TypeAlias' = Dict[SpecificTransition, AnalysisResults]
"""
Per-final-transition analysis results, similar to `TransitionAnalyses`
but they apply to `SpecificTransition`s instead of
`OverspecificTransition`s, based on transitions present in the graph on
the final step, rather than all transitions that ever existed (many of
which get deleted by returns which replace old unconfirmed decisions with
existing decisions).
"""

StepAnalyses: 'TypeAlias' = List[AnalysisResults]
"""
Per-exploration-step analysis results are stored in a list and indexed by
exploration step integers.
"""

StepwiseDecisionAnalyses: 'TypeAlias' = List[DecisionAnalyses]
"""
Per-step-per-decision analysis results are stored as a list of decision
analysis results.
"""

StepwiseTransitionAnalyses: 'TypeAlias' = List[TransitionAnalyses]
"""
Per-step-per-transition analysis results are stored as a list of
transition analysis results.
"""

ExplorationAnalyses: 'TypeAlias' = AnalysisResults
"""
Whole-exploration analyses are just a normal `AnalysisResults` dictionary.
"""

class FullAnalysisResults(TypedDict):
    """
    Full analysis results hold every kind of analysis result in one
    dictionary.
    """
    perDecision: DecisionAnalyses
    perTransition: TransitionAnalyses
    perFinalTransition: FinalTransitionAnalyses
    perStep: StepAnalyses
    perStepDecision: StepwiseDecisionAnalyses
    perStepTransition: StepwiseTransitionAnalyses
    overall: ExplorationAnalyses


def newFullAnalysisResults() -> FullAnalysisResults:
    """
    Returns a new empty `FullAnalysisResults` dictionary.
    """
    return {
        'perDecision': {},
        'perTransition': {},
        'perFinalTransition': {},
        'perStep': [],
        'perStepDecision': [],
        'perStepTransition': [],
        'overall': {}
    }


Params = ParamSpec('Params')
'Parameter specification variable for `AnalysisFunction` definition.'


class AnalysisFunction(Protocol[Params]):
    """
    Analysis functions are callable, but also have a `_unit` attribute
    which is a string.
    """
    _unit: AnalysisUnit
    __name__: str
    __doc__: str
    def __call__(
        self,
        exploration: core.DiscreteExploration,
        *args: Params.args,
        **kwargs: Params.kwargs
    ) -> Any:
        ...


StepAnalyzer: 'TypeAlias' = AnalysisFunction[[int]]
'''
A step analyzer is a function which will receive a
`core.DiscreteExploration` along with the step in that exploration being
considered. It can return any type of analysis result.
'''

StepDecisionAnalyzer: 'TypeAlias' = AnalysisFunction[[int, base.DecisionID]]
'''
Like a `StepAnalyzer` but also gets a decision ID to consider.
'''

StepTransitionAnalyzer: 'TypeAlias' = AnalysisFunction[
    [int, base.DecisionID, base.Transition, base.DecisionID]
]
'''
Like a `StepAnalyzer` but also gets a source decision ID, a transition
name, and a destination decision ID to target.
'''


DecisionAnalyzer: 'TypeAlias' = AnalysisFunction[[base.DecisionID]]
'''
A decision analyzer gets full analysis results to update plus an
exploration and a particular decision ID to consider.
'''

TransitionAnalyzer: 'TypeAlias' = AnalysisFunction[
    [base.DecisionID, base.Transition, base.DecisionID]
]
'''
Like a `DecisionAnalyzer` but gets a transition name and destination as well.
'''

FinalTransitionAnalyzer: 'TypeAlias' = AnalysisFunction[
    [base.DecisionID, base.Transition]
]
'''
Like a `TransitionAnalyzer` but doens't get transition destination.
'''

ExplorationAnalyzer: 'TypeAlias' = AnalysisFunction[[]]
'''
Analyzes overall properties of an entire `core.DiscreteExploration`.
'''


#--------------------------#
# Analysis caching support #
#--------------------------#

AnyAnalyzer: 'TypeAlias' = Union[
    ExplorationAnalyzer,
    TransitionAnalyzer,
    FinalTransitionAnalyzer,
    DecisionAnalyzer,
    StepAnalyzer,
    StepDecisionAnalyzer,
    StepTransitionAnalyzer
]


ANALYSIS_RESULTS: Dict[int, FullAnalysisResults] = {}
"""
Caches analysis results, keyed by the `id` of the
`core.DiscreteExploration` they're based on.
"""


class NotCached:
    """
    Reference object for specifying that no cached value is available,
    since `None` is a valid cached value.
    """
    pass


def lookupAnalysisResult(
    cache: FullAnalysisResults,
    analyzer: AnalysisFunction,
    argsInOrder: Sequence[Any]
) -> Union[Type[NotCached], Any]:
    """
    Looks up an analysis result for the given function in the given
    cache. The function must have been decorated with `analyzer`. The
    bound arguments must match the unit of analysis, for example, if the
    unit is 'stepDecision', the arguments must be those for a
    `StepDecisionAnalyzer`. The bound arguments should have had
    `apply_defaults` called already to fill in default argument values.
    Returns the special object `NotCached` if there is no cached value
    for the specified arguments yet.
    """
    unit = analyzer._unit
    if unit == 'step':
        whichStep = argsInOrder[1]
        perStep = cache['perStep']
        while len(perStep) <= whichStep:
            perStep.append({})
        return perStep[whichStep].get(analyzer.__name__, NotCached)
    elif unit == 'stepDecision':
        whichStep = argsInOrder[1]
        whichDecision = argsInOrder[2]
        perStepDecision = cache['perStepDecision']
        while len(perStepDecision) <= whichStep:
            perStepDecision.append({})
        forThis = perStepDecision[whichStep].get(whichDecision)
        if forThis is None:
            return NotCached
        return forThis.get(analyzer.__name__, NotCached)
    elif unit == 'stepTransition':
        whichStep = argsInOrder[1]
        whichTransition = (argsInOrder[2], argsInOrder[3], argsInOrder[4])
        perStepTransition = cache['perStepTransition']
        while len(perStepTransition) <= whichStep:
            perStepTransition.append({})
        forThis = perStepTransition[whichStep].get(whichTransition)
        if forThis is None:
            return NotCached
        return forThis.get(analyzer.__name__, NotCached)
    elif unit == 'decision':
        whichDecision = argsInOrder[1]
        perDecision = cache['perDecision']
        if whichDecision not in perDecision:
            return NotCached
        return perDecision[whichDecision].get(analyzer.__name__, NotCached)
    elif unit == 'transition':
        whichTransition = (argsInOrder[1], argsInOrder[2], argsInOrder[3])
        perTransition = cache['perTransition']
        if whichTransition not in perTransition:
            return NotCached
        return perTransition[whichTransition].get(
            analyzer.__name__,
            NotCached
        )
    elif unit == 'finalTransition':
        whichFinalTransition = (argsInOrder[1], argsInOrder[2])
        perFinalTransition = cache['perFinalTransition']
        if whichFinalTransition not in perFinalTransition:
            return NotCached
        return perFinalTransition[whichFinalTransition].get(
            analyzer.__name__,
            NotCached
        )
    elif unit == 'exploration':
        return cache['overall'].get(analyzer.__name__, NotCached)
    else:
        raise ValueError(f"Invalid analysis unit {unit!r}.")


def saveAnalysisResult(
    cache: FullAnalysisResults,
    result: Any,
    analyzer: AnalysisFunction,
    argsInOrder: Sequence[Any]
) -> None:
    """
    Saves an analysis result in the specified cache. The bound arguments
    must match the unit, for example, if the unit is 'stepDecision', the
    arguments must be those for a `StepDecisionAnalyzer`.
    """
    unit = analyzer._unit
    if unit == 'step':
        whichStep = argsInOrder[1]
        perStep = cache['perStep']
        while len(perStep) <= whichStep:
            perStep.append({})
        perStep[whichStep][analyzer.__name__] = result
    elif unit == 'stepDecision':
        whichStep = argsInOrder[1]
        whichDecision = argsInOrder[2]
        perStepDecision = cache['perStepDecision']
        while len(perStepDecision) <= whichStep:
            perStepDecision.append({})
        forThis = perStepDecision[whichStep].setdefault(whichDecision, {})
        forThis[analyzer.__name__] = result
    elif unit == 'stepTransition':
        whichStep = argsInOrder[1]
        whichTransition = (argsInOrder[2], argsInOrder[3], argsInOrder[4])
        perStepTransition = cache['perStepTransition']
        while len(perStepTransition) <= whichStep:
            perStepTransition.append({})
        forThis = perStepTransition[whichStep].setdefault(whichTransition, {})
        forThis[analyzer.__name__] = result
    elif unit == 'decision':
        whichDecision = argsInOrder[1]
        perDecision = cache['perDecision']
        perDecision.setdefault(whichDecision, {})[analyzer.__name__] = result
    elif unit == 'transition':
        whichTransition = (argsInOrder[1], argsInOrder[2], argsInOrder[3])
        perTransition = cache['perTransition']
        perTransition.setdefault(
            whichTransition,
            {}
        )[analyzer.__name__] = result
    elif unit == 'finalTransition':
        whichFinalTransition = (argsInOrder[1], argsInOrder[2])
        perFinalTransition = cache['perFinalTransition']
        perFinalTransition.setdefault(
            whichFinalTransition,
            {}
        )[analyzer.__name__] = result
    elif unit == 'exploration':
        cache['overall'][analyzer.__name__] = result
    else:
        raise ValueError(f"Invalid analysis unit {unit!r}.")


ALL_ANALYZERS: Dict[str, AnyAnalyzer] = {}
"""
Holds all analyzers indexed by name with the analysis unit plus function
as the value. The `analyzer` decorator registers them.
"""


RECORD_PROFILE: bool = False
"""
Whether or not to record time spent by each analysis function.
"""


class AnalyzerPerf(TypedDict):
    """
    Tracks performance of an analysis function, recording total calls,
    non-cached calls, time spent looking up cached results, and time
    spent in non-cached calls (including the failed cache lookup and
    saving the result in the cache). 
    """
    calls: int
    nonCached: int
    lookupTime: float
    analyzeTime: float


def newAnalyzerPerf() -> AnalyzerPerf:
    """
    Creates a new empty `AnalyzerPerf` dictionary.
    """
    return {
        "calls": 0,
        "nonCached": 0,
        "lookupTime": 0.0,
        "analyzeTime": 0.0
    }


ANALYSIS_TIME_SPENT: Dict[str, AnalyzerPerf] = {}
"""
Records number-of-calls, number-of-non-cached calls, and time spent in
each analysis function, when `RECORD_PROFILE` is set to `True`.
"""


ELIDE: Set[str] = set()
"""
Analyzers which should not be included in CSV output by default.
"""

FINAL_ONLY: Set[str] = set()
"""
Per-step/step-decision/step-transition analyzers which should by default
only be applied to the final step of an exploration to save time.
"""


def getArgsInOrder(
    f: Callable,
    *args: Any,
    **kwargs: Any
) -> List[Any]:
    """
    Given a callable and some arguments, returns a list of argument
    values in the same order as that function would accept them from the
    given arguments, accounting for things like keyword arguments and
    default values.

    For example:

    >>> def f(a, /, b, *more, x=3, y=10, **kw):
    ...     pass
    >>> sig = inspect.Signature.from_callable(f)
    >>> getArgsInOrder(f, 1, 2)
    [1, 2, 3, 10]
    >>> getArgsInOrder(f, 4, 5, y=2, x=8)
    [4, 5, 8, 2]
    >>> getArgsInOrder(f, 4, y=2, x=8, b=3)
    [4, 3, 8, 2]
    >>> getArgsInOrder(f, 4, y=2, x=8, b=3)
    [4, 3, 8, 2]
    >>> getArgsInOrder(f, 1, 2, 3, 4)
    [1, 2, 3, 4, 3, 10]
    >>> getArgsInOrder(f, 1, 2, 3, 4, q=5, k=9)
    [1, 2, 3, 4, 3, 10, 5, 9]
    """
    sig = inspect.Signature.from_callable(f)
    bound = sig.bind(*args, **kwargs)
    bound.apply_defaults()
    result = []
    for paramName in sig.parameters:
        param = sig.parameters[paramName]
        if param.kind in (
            inspect.Parameter.POSITIONAL_ONLY,
            inspect.Parameter.POSITIONAL_OR_KEYWORD,
        ):
            result.append(bound.arguments[paramName])
        elif param.kind == inspect.Parameter.VAR_POSITIONAL:
            result.extend(bound.arguments[paramName])
        elif param.kind == inspect.Parameter.KEYWORD_ONLY:
            result.append(bound.arguments[paramName])
        elif param.kind == inspect.Parameter.VAR_KEYWORD:
            result.extend(bound.arguments[paramName].values())

    return result


def analyzer(unit: AnalysisUnit) -> Callable[
    [Callable[Concatenate[core.DiscreteExploration, Params], Any]],
    AnalysisFunction
]:
    '''
    Decorator which sets up caching for an analysis function in the
    global `ANALYSIS_RESULTS` dictionary. Whenever the decorated function
    is called, it will first check whether a cached result is available
    for the same target exploration (by id) and additional target info
    based on the analysis unit type. If so, the cached result will be
    returned. This allows analysis functions to simply call each other
    when they need results and themselves recursively if they need to
    track things across steps/decisions, while avoiding tons of duplicate
    work.
    '''
    def makeCachedAnalyzer(
        baseFunction: Callable[
            Concatenate[core.DiscreteExploration, Params],
            Any
        ]
    ) -> AnalysisFunction:
        """
        Decoration function which registers an analysis function with
        pre-specified dependencies.
        """
        analysisFunction = cast(AnalysisFunction, baseFunction)
        analysisFunction._unit = unit
        analyzerName= analysisFunction.__name__

        @functools.wraps(analysisFunction)
        def cachingAnalyzer(
            exploration: core.DiscreteExploration,
            *args: Params.args,
            **kwargs: Params.kwargs
        ):
            """
            This docstring will be replaced with the docstring of the
            decorated function plus a note about caching.
            """
            if RECORD_PROFILE:
                ANALYSIS_TIME_SPENT.setdefault(
                    analyzerName,
                    newAnalyzerPerf()
                )
                perf = ANALYSIS_TIME_SPENT[analyzerName]
                perf["calls"] += 1
                start = time.perf_counter()
            cache = ANALYSIS_RESULTS.setdefault(
                id(exploration),
                newFullAnalysisResults()
            )
            argsInOrder = getArgsInOrder(
                baseFunction,
                exploration,
                *args,
                **kwargs
            )
            cachedResult = lookupAnalysisResult(
                cache,
                analysisFunction,
                argsInOrder
            )
            if cachedResult is not NotCached:
                if RECORD_PROFILE:
                    perf["lookupTime"] += time.perf_counter() - start
                return cachedResult

            result = analysisFunction(exploration, *args, **kwargs)
            saveAnalysisResult(cache, result, analysisFunction, argsInOrder)
            if RECORD_PROFILE:
                perf["nonCached"] += 1
                perf["analyzeTime"] += time.perf_counter() - start
            return result

        cachingAnalyzer.__doc__ = (
            textwrap.dedent(analysisFunction.__doc__)
          + """

This function's results are cached in the `ALL_ANALYZERS` dictionary, and
it returns cached results when possible. Use `clearAnalysisCache` to
clear the analysis cache.
"""
        )

        # Save caching version of analyzer
        result = cast(AnalysisFunction, cachingAnalyzer)
        ALL_ANALYZERS[analyzerName] = result
        return result

    return makeCachedAnalyzer


T = TypeVar('T', bound=AnalysisFunction)
'Type variable for `elide` and `finalOnly`.'

def elide(analyzer: T) -> T:
    """
    Returns the given analyzer after noting that its result should *not*
    be included in CSV output by default.
    """
    ELIDE.add(analyzer.__name__)
    return analyzer


def finalOnly(analyzer: T) -> T:
    """
    Returns the given analyzer after noting that it should only be run on
    the final exploration step by default.
    """
    FINAL_ONLY.add(analyzer.__name__)
    return analyzer


#-----------------------#
# Generalizer Functions #
#-----------------------#

AnalyzerType = TypeVar('AnalyzerType', bound=AnyAnalyzer)
"""
Type var to forward through analyzer types.
"""

def registerCount(target: AnalyzerType, sizeName: str) -> AnalyzerType:
    """
    Registers a new analysis routine which uses the same analysis unit as
    the target routine but which returns the length of that routine's
    result. Returns `None` if the target routine does.

    Needs the target routine and the name to register the new analysis
    routine under.

    Returns the analysis function it creates.
    """
    def countAnalyzer(*args, **kwargs):
        'To be replaced'
        result = target(*args, **kwargs)
        if result is None:
            return None
        else:
            return len(result)

    countAnalyzer.__doc__ = (
        f"Measures count of the {target.__name__!r} result applied to"
        f" {target._unit!r}."
    )
    countAnalyzer.__name__ = sizeName

    # Register the new function & return the result
    return cast(
        AnalyzerType,
        analyzer(target._unit)(countAnalyzer)
    )


CombinerResult = TypeVar('CombinerResult')
"""
Type variable for the result of a combiner function.
"""

StepCombiner: 'TypeAlias' = Callable[
    [
        Dict[
            Union[
                base.DecisionID,
                SpecificTransition,
                OverspecificTransition
            ],
            Any
        ],
        core.DiscreteExploration,
        int
    ],
    CombinerResult
]
"""
A combiner function which gets a dictionary of per-decision or
per-transition values along with an exploration object and a step index
and combines the values into a `CombinerResult` that's specific to that
step.
"""

OverallCombiner: 'TypeAlias' = Callable[
    [
        Dict[
            Union[
                base.DecisionID,
                SpecificTransition,
                OverspecificTransition,
                int
            ],
            Any
        ],
        core.DiscreteExploration
    ],
    CombinerResult
]
"""
A combiner function which gets a dictionary of per-decision,
per-transition, and/or per-step values along with an exploration object
and combines the values into a `CombinerResult`.
"""


def registerStepCombined(
    name: str,
    resultName: str,
    combiner: StepCombiner[CombinerResult]
) -> StepAnalyzer:
    """
    Registers a new analysis routine which combines results of another
    routine either across all decisions/transitions at a step. The new
    routine will have a 'step' analysis unit.

    Needs the name of the target routine, the name to register the new
    analysis routine under, and the function that will be called to
    combine results, given a dictionary of results that maps
    decisions/transitions to results for each.

    Returns the analysis function it creates.
    """
    # Target function
    target = ALL_ANALYZERS[name]
    # Analysis unit of the target function
    targetUnit = target._unit

    if targetUnit not in ('stepDecision', 'stepTransition'):
        raise ValueError(
            f"Target analysis routine {name!r} has incompatible analysis"
            f" unit {targetUnit!r}."
        )

    def analysisCombiner(
        exploration: core.DiscreteExploration,
        step: int
    ) -> CombinerResult:
        'To be replaced'
        # Declare data here with generic type
        data: Dict[
            Union[
                base.DecisionID,
                SpecificTransition,
                OverspecificTransition,
                int
            ],
            Any
        ]
        graph = exploration[step].graph
        if targetUnit == "stepDecision":
            analyzeStepDecision = cast(StepDecisionAnalyzer, target)
            data = {
                dID: analyzeStepDecision(exploration, step, dID)
                for dID in graph
            }
        elif targetUnit == "stepTransition":
            edges = graph.allEdges()
            analyzeStepTransition = cast(StepTransitionAnalyzer, target)
            data = {
                (src, transition, dst): analyzeStepTransition(
                    exploration,
                    step,
                    src,
                    transition,
                    dst
                )
                for (src, dst, transition) in edges
            }
        else:
            raise ValueError(
                f"Target analysis routine {name!r} has inconsistent"
                f" analysis unit {targetUnit!r} for 'step' result"
                f" unit."
            )
        return combiner(data, exploration, step)

    analysisCombiner.__doc__ = (
        f"Computes {combiner.__name__} for the {name!r} result over all"
        f" {targetUnit}s at each step."
    )
    analysisCombiner.__name__ = resultName

    # Register the new function & return it
    return analyzer("step")(analysisCombiner)


def registerFullCombined(
    name: str,
    resultName: str,
    combiner: OverallCombiner[CombinerResult]
) -> ExplorationAnalyzer:
    """
    Works like `registerStepCombined` but combines results over
    decisions/transitions/steps across the entire exploration to get one
    result for the entire thing, not one result per step. May also
    target an existing `ExplorationAnalyzer` whose result is a
    dictionary, in which case it will combine that dictionary's values.

    Needs the name of the target routine, the name to register the new
    analysis routine under, and the function that will be called to
    combine results, given a dictionary of results that maps
    decisions/transitions/steps to results for each.

    Returns the analysis function it creates.
    """
    # Target function
    target = ALL_ANALYZERS[name]
    # Analysis unit of the target function
    targetUnit = target._unit
    if targetUnit not in (
        'step',
        'decision',
        'transition',
        'finalTransition',
        'exploration'
    ):
        raise ValueError(
            f"Target analysis routine {name!r} has incompatible analysis"
            f" unit {targetUnit!r}."
        )

    def analysisCombiner(  # type: ignore
        exploration: core.DiscreteExploration,
    ) -> CombinerResult:
        'To be replaced'
        # Declare data here as generic type
        data: Dict[
            Union[
                base.DecisionID,
                SpecificTransition,
                OverspecificTransition,
                int
            ],
            Any
        ]
        if targetUnit == "step":
            analyzeStep = cast(StepAnalyzer, target)
            data = {
                step: analyzeStep(exploration, step)
                for step in range(len(exploration))
            }
        elif targetUnit == "decision":
            analyzeDecision = cast(DecisionAnalyzer, target)
            data = {
                dID: analyzeDecision(exploration, dID)
                for dID in exploration.allDecisions()
            }
        elif targetUnit == "transition":
            analyzeTransition = cast(TransitionAnalyzer, target)
            data = {
                (src, transition, dst): analyzeTransition(
                    exploration,
                    src,
                    transition,
                    dst
                )
                for (src, transition, dst) in exploration.allTransitions()
            }
        elif targetUnit == "finalTransition":
            analyzeFinalTransition = cast(FinalTransitionAnalyzer, target)
            data = {
                (src, transition): analyzeFinalTransition(
                    exploration,
                    src,
                    transition
                )
                for (src, transition) in exploration.allFinalTransitions()
            }
        elif targetUnit == "exploration":
            analyzeExploration = cast(ExplorationAnalyzer, target)
            data = analyzeExploration(exploration)
        else:
            raise ValueError(
                f"Target analysis routine {name!r} has inconsistent"
                f" analysis unit {targetUnit!r} for 'step' result"
                f" unit."
            )
        return combiner(data, exploration)

    analysisCombiner.__doc__ = (
        f"Computes {combiner.__name__} for the {name!r} result over all"
        f" {targetUnit}s."
    )
    analysisCombiner.__name__ = resultName

    # Register the new function & return it
    return analyzer("exploration")(analysisCombiner)


def sumCombiner(data: Dict[Any, Any], *_: Any) -> Union[int, float, complex]:
    """
    Computes sum over numeric data as a "combiner" function to be used
    with `registerStepCombined` or `registerFullCombined`.

    Only sums values which are `int`s, `float`s, or `complex`es, ignoring
    any other values.
    """
    return sum(
        x for x in data.values() if isinstance(x, (int, float, complex))
    )


def meanCombiner(
    data: Dict[Any, Any], *_: Any
) -> Optional[Union[float, complex]]:
    """
    Computes mean over numeric data as a "combiner" function to be used
    with `registerStepCombined` or `registerFullCombined`.

    Only counts values which are `int`s, `float`s, or `complex`es, ignoring
    any other values. Uses `None` as the result when there are 0 numeric
    values.
    """
    numeric = [
        x for x in data.values() if isinstance(x, (int, float, complex))
    ]
    if len(numeric) == 0:
        return None
    else:
        return sum(numeric) / len(numeric)


def medianCombiner(
    data: Dict[Any, Any], *_: Any
) -> Optional[Union[int, float, complex]]:
    """
    Computes median over numeric data as a "combiner" function to be used
    with `registerStepCombined` or `registerFullCombined`.

    Only counts values which are `int`s, `float`s, or `complex`es, ignoring
    any other values. Uses `None` as the result when there are 0 numeric
    values.
    """
    numeric = sorted(
        cast(float, x)
        for x in data.values()
        if isinstance(x, (int, float, complex))
    )
    if len(numeric) == 0:
        return None
    elif len(numeric) == 1:
        return numeric[0]
    else:
        half = len(numeric) // 2
        if len(numeric) % 2 == 0:
            return (numeric[half - 1] + numeric[half]) / 2
        else:
            return numeric[half]


def makeFractionCombiner(
    filterFunction: Callable[[Any, Any], bool],
    ignoreFunction: Optional[Callable[[Any, Any], bool]] = None
) -> Union[StepCombiner[Optional[float]], OverallCombiner[Optional[float]]]:
    """
    Creates a combiner function to be used with, e.g.,
    `registerFullCombined`, which computes the fraction of data entries
    which pass the provided filter function. The filter function will be
    given the key (e.g., decision ID, `OverspecificTransition`, etc.) as
    its first argument and the entire associated data value as its second.

    If an `ignoreFunction` is provided, it gets run first and entries
    for which it returns False are not included in either the numerator
    or denominator of the fraction (the `filterFunction` won't be run on
    them).

    The resulting combiner will return None if it ends up with 0 as the
    denominator (no steps/transitions/decisions to combine due to an
    empty graph or `ignoreFunction` filtering).
    """
    def specificFractionCombiner(
        data: Dict[Any, Any],
        *_: Any
    ) -> Optional[float]:
        """
        Custom combiner function that computes the fraction of the data
        that matches a specified filter function, possibly without
        triggering a specified ignore function.
        """
        numer = 0
        denom = 0
        for (key, value) in data.items():
            if ignoreFunction is not None and ignoreFunction(key, value):
                continue
            else:
                denom += 1
                if filterFunction(key, value):
                    numer += 1

        if denom == 0:
            return None
        else:
            return numer / denom

    return specificFractionCombiner


#---------------------------#
# Simple property functions #
#---------------------------#

@analyzer('decision')
def finalIdentity(
    exploration: core.DiscreteExploration,
    decision: base.DecisionID
) -> str:
    """
    Returns the `identityOf` result for the specified decision in the
    last step in which that decision existed.
    """
    for i in range(-1, -len(exploration) - 1, -1):
        situation = exploration.getSituation(i)
        try:
            return situation.graph.identityOf(decision)
        except core.MissingDecisionError:
            pass
    raise core.MissingDecisionError(
        f"Decision {decision!r} never existed."
    )


@analyzer('step')
def currentDecision(
    exploration: core.DiscreteExploration,
    step: int
) -> Optional[base.DecisionID]:
    """
    Returns the `base.DecisionID` for the current decision in a given
    situation.
    """
    return exploration[step].state['primaryDecision']


@analyzer('step')
def currentDecisionIdentity(
    exploration: core.DiscreteExploration,
    step: int
) -> str:
    """
    Returns the `identityOf` string for the current decision in a given
    situation.
    """
    situation = exploration[step]
    try:
        return situation.graph.identityOf(situation.state['primaryDecision'])
    except core.MissingDecisionError:
        return "<missing in this step>"


@analyzer('step')
def observedSoFar(
    exploration: core.DiscreteExploration,
    step: int
) -> Set[base.DecisionID]:
    """
    Returns the set of all decision IDs observed so far. Note that some
    of them may no longer be present in the graph at the given step if
    they got merged or deleted.
    """
    # Can't allow negative steps (caching would fail)
    if step < 0:
        raise IndexError(f"Invalid step (can't be negative): {step!r}")
    elif step == 0:
        result = set()
    else:
        result = observedSoFar(exploration, step - 1)
    result |= set(exploration[step].graph)
    return result


totalDecisionsSoFar = registerCount(observedSoFar, 'totalDecisionsSoFar')


@analyzer('step')
def justObserved(
    exploration: core.DiscreteExploration,
    step: int
) -> Set[base.DecisionID]:
    """
    Returns the set of new `base.DecisionID`s that first appeared at the
    given step. Will be empty for steps where no new decisions are
    observed. Note that this is about decisions whose existence becomes
    known, NOT decisions which get confirmed.
    """
    if step == 0:
        return observedSoFar(exploration, step)
    else:
        return (
            observedSoFar(exploration, step - 1)
          - observedSoFar(exploration, step)
        )


newDecisionCount = registerCount(justObserved, 'newDecisionCount')


@elide
@analyzer('stepDecision')
def hasBeenObserved(
    exploration: core.DiscreteExploration,
    step: int,
    dID: base.DecisionID
) -> bool:
    """
    Whether or not the specified decision has been observed at or prior
    to the specified step. Note that it may or may not actually be a
    decision in the specified step (e.g., if it was previously observed
    but then deleted).
    """
    return dID in observedSoFar(exploration, step)


@analyzer('exploration')
def stepsObserved(
    exploration: core.DiscreteExploration,
) -> Dict[base.DecisionID, int]:
    """
    Returns a dictionary that holds the step at which each decision was
    first observed, keyed by decision ID.
    """
    result = {}
    soFar: Set[base.DecisionID] = set()
    for step, situation in enumerate(exploration):
        new = set(situation.graph) - soFar
        for dID in new:
            result[dID] = step
        soFar |= new
    return result


@analyzer('decision')
def stepObserved(
    exploration: core.DiscreteExploration,
    dID: base.DecisionID
) -> int:
    """
    Returns the step at which the specified decision was first observed
    (NOT confirmed).
    """
    try:
        return stepsObserved(exploration)[dID]
    except KeyError:
        raise core.MissingDecisionError(
            f"Decision {dID!r} was never observed."
        )


@analyzer('exploration')
def stepsConfirmed(
    exploration: core.DiscreteExploration,
) -> Dict[base.DecisionID, int]:
    """
    Given an exploration, returns a dictionary mapping decision IDs to
    the step at which each was first confirmed. Decisions which were
    never confirmed will not be included in the dictionary.
    """
    result = {}
    for i, situation in enumerate(exploration):
        for dID in situation.graph:
            if (
                dID not in result
            and 'unconfirmed' not in situation.graph.decisionTags(dID)
            ):
                result[dID] = i
    return result


@analyzer('decision')
def stepConfirmed(
    exploration: core.DiscreteExploration,
    dID: base.DecisionID
) -> Optional[int]:
    """
    Returns the step at which the specified decision was first confirmed,
    or `None` if it was never confirmed. Returns `None` for invalid
    decision IDs.
    """
    return stepsConfirmed(exploration).get(dID)


@analyzer('exploration')
def stepsVisited(
    exploration: core.DiscreteExploration,
) -> Dict[base.DecisionID, List[int]]:
    """
    Given an exploration, returns a dictionary mapping decision IDs to
    the list of steps at which each was visited. Decisions which were
    never visited will not be included in the dictionary.
    """
    result: Dict[base.DecisionID, List[int]] = {}
    for i, situation in enumerate(exploration):
        for dID in situation.graph:
            if dID in base.combinedDecisionSet(situation.state):
                result.setdefault(dID, []).append(i)
    return result


@finalOnly
@analyzer('stepDecision')
def hasBeenVisited(
    exploration: core.DiscreteExploration,
    step: int,
    dID: base.DecisionID
) -> bool:
    """
    Whether or not the specified decision has been visited at or prior
    to the specified step. Note that it may or may not actually be a
    decision in the specified step (e.g., if it was previously observed
    but then deleted).
    """
    visits = stepsVisited(exploration).get(dID, [])
    # No visits -> not visited yet
    if len(visits) == 0:
        return False
    else:
        # First visit was at or before this step
        return min(visits) <= step


@analyzer('decision')
def stepFirstVisited(
    exploration: core.DiscreteExploration,
    decision: base.DecisionID,
) -> Optional[int]:
    """
    Returns the first step at which the given decision was visited, or
    `None` if the decision was never visited.
    """
    vis = stepsVisited(exploration)
    if decision in vis:
        return min(vis[decision])
    else:
        return None


@analyzer('decision')
def stepsActive(
    exploration: core.DiscreteExploration,
    decision: base.DecisionID,
) -> Optional[int]:
    """
    Returns the total number of steps in which this decision was active.
    """
    vis = stepsVisited(exploration)
    if decision in vis:
        return len(vis[decision])
    else:
        return 0


@analyzer('exploration')
def stepsTransisionsObserved(
    exploration: core.DiscreteExploration
) -> Dict[SpecificTransition, int]:
    """
    Returns a dictionary that holds the step at which each transition was
    first observed, keyed by (source-decision, transition-name) pairs.

    Does NOT distinguish between cases where a once-deleted transition
    was later reinstated. Tracks transitions regardless of their
    destinations, so a transition which leads to an anonymous
    unconfirmed decision which is later replaced via obviate or return
    will count as the same transition even though its destination ID
    changes.
    """
    result = {}
    for i, situation in enumerate(exploration):
        for dID in situation.graph:
            destinations = situation.graph.destinationsFrom(dID)
            for name, dest in destinations.items():
                key = (dID, name)
                if key not in result:
                    result[key] = i
    return result


@analyzer('finalTransition')
def stepObservedTransition(
    exploration: core.DiscreteExploration,
    source: base.DecisionID,
    transition: base.Transition
) -> Optional[int]:
    """
    Returns the step within the exploration at which the specified
    transition was first observed. Note that transitions which get
    renamed do NOT preserve their identities, so a search for a renamed
    transition will return the step on which it was renamed.

    Returns `None` if the specified transition never existed in the
    exploration.
    """
    obs = stepsTransisionsObserved(exploration)
    return obs.get((source, transition))


@analyzer('step')
def transitionTaken(
    exploration: core.DiscreteExploration,
    step: int
) -> Optional[OverspecificTransition]:
    """
    Returns the source decision Id, the name of the transition taken, and
    the destination decision ID at the given step. This is the transition
    chosen at that step whose consequences were triggered resulting in
    the next step. Returns `None` for steps where no transition was
    taken (e.g., wait, warp, etc.).

    Note that in some cases due to e.g., a 'follow' effect, multiple
    transitions are taken at a step. In that case, this returns the name
    of the first transition taken (which would have triggered any
    others).

    Also in some cases, there may be multiple starting nodes given, in
    which case the first such node (by ID order) which has a transition
    with the identified transition name will be returned, or None if none
    of them match.
    """
    start, transition, end = exploration.movementAtStep(step)
    graph = exploration[step].graph
    if start is None or transition is None:
        return None
    if isinstance(start, set):
        for dID in sorted(start):
            destination = graph.getDestination(dID, transition)
            if destination is not None:
                return (dID, transition, destination)
        return None
    else:
        destination = graph.getDestination(start, transition)
        if destination is not None:
            return (start, transition, destination)
        else:
            return None


@analyzer('exploration')
def transitionStepsTaken(
    exploration: core.DiscreteExploration
) -> Dict[SpecificTransition, List[int]]:
    """
    Returns a dictionary mapping each specific transition that was taken
    at least once to the list of steps on which it was taken. Does NOT
    account for transitions elided by 'jaunt' warps, nor for transitions
    taken as a result of follow/bounce effects.

    TODO: Account for those?
    """
    result: Dict[SpecificTransition, List[int]] = {}
    for i in range(len(exploration)):
        taken = transitionTaken(exploration, i)
        if taken is not None:
            key = taken[:2]
            if key in result:
                result[key].append(i)
            else:
                result[key] = [i]

    return result


@analyzer('finalTransition')
def stepsTaken(
    exploration: core.DiscreteExploration,
    source: base.DecisionID,
    transition: base.Transition
) -> int:
    """
    Returns the list of exploration steps on which a particular
    transition has been taken. Returns an empty list for transitions that
    were never taken.

    Note that this does NOT account for times taken as a result of
    follow/bounce effects, and it does NOT account for all times a
    transition was taken when warp effects are used as shorthand for
    jaunts across the graph.
    
    TODO: Try to account for those?
    """
    return transitionStepsTaken(exploration).get((source, transition), [])


@analyzer('finalTransition')
def timesTaken(
    exploration: core.DiscreteExploration,
    source: base.DecisionID,
    transition: base.Transition
) -> int:
    """
    Returns the number of times a particular transition has been taken
    throughout the exploration. Returns 0 for transitions that were never
    taken.

    Note that this does NOT account for times taken as a result of
    follow/bounce effects, and it does NOT account for all times a
    transition was taken when warp effects are used as shorthand for
    jaunts across the graph.
    
    TODO: Try to account for those?
    """
    return len(stepsTaken(exploration, source, transition))

@analyzer('exploration')
def stepCount(exploration: core.DiscreteExploration) -> int:
    """
    Counts total # of steps in exploration.
    """
    return len(exploration)


@elide
@analyzer('finalTransition')
def requirement(
    exploration: core.DiscreteExploration,
    source: base.DecisionID,
    transition: base.Transition
) -> Optional[base.Requirement]:
    """
    Returns the requirement for the transition on the last step of the
    exploration, or `None` if that transition didn't exist on the last
    step.
    """
    graph = exploration.getSituation().graph
    try:
        return graph.getTransitionRequirement(source, transition)
    except (core.MissingDecisionError, core.MissingTransitionError):
        return None

registerFullCombined(
    'requirement',
    'restrictedFraction',
    cast(
        OverallCombiner[Optional[float]],
        makeFractionCombiner(
            lambda spec, req: req != base.ReqNothing()
        )
    )
)

#--------------------#
# Analysis functions #
#--------------------#

def unexploredBranches(
    graph: core.DecisionGraph,
    context: Optional[base.RequirementContext] = None
) -> List[SpecificTransition]:
    """
    Returns a list of from-decision, transition-at-that-decision pairs
    which each identify an unexplored branch in the given graph.

    When a `context` is provided it only counts options whose
    requirements are satisfied in that `RequirementContext`, and the
    'searchFrom' part of the context will be replaced by both ends of
    each transition tested. This doesn't perfectly map onto actually
    reachability since nodes between where the player is and where the
    option is might force changes in the game state that make it
    un-takeable.

    TODO: add logic to detect trivially-unblocked edges?
    """
    result = []
    # TODO: Fix networkx type stubs for MultiDiGraph!
    for (src, dst, transition) in graph.allEdges():
        req = graph.getTransitionRequirement(src, transition)
        localContext: Optional[base.RequirementContext] = None
        if context is not None:
            localContext = base.RequirementContext(
                state=context.state,
                graph=context.graph,
                searchFrom=graph.bothEnds(src, transition)
            )
        # Check if this edge goes from a confirmed to an unconfirmed node
        if (
            graph.isConfirmed(src)
        and not graph.isConfirmed(dst)
        and (localContext is None or req.satisfied(localContext))
        ):
            result.append((src, transition))
    return result


@analyzer('step')
def allUnexploredBranches(
    exploration: core.DiscreteExploration,
    step: int
) -> List[SpecificTransition]:
    """
    Returns the list of unexplored branches in the specified situation's
    graph, regardless of traversibility (see `unexploredBranches`).
    """
    return unexploredBranches(exploration[step].graph)


unexploredBranchCount = registerCount(
    allUnexploredBranches,
    'unexploredBranchCount'
)


@analyzer('step')
def traversableUnexploredBranches(
    exploration: core.DiscreteExploration,
    step: int
) -> List[SpecificTransition]:
    """
    Returns the list of traversable unexplored branches in the specified
    situation's graph (see `unexploredBranches`). Does not perfectly
    account for all traversibility information, because it uses a single
    context from which to judge traversibility (TODO: Fix that).
    """
    situation = exploration[step]
    context = base.genericContextForSituation(
        situation,
        base.combinedDecisionSet(situation.state)
    )
    return unexploredBranches(situation.graph, context)


traversableUnexploredCount = registerCount(
    traversableUnexploredBranches,
    'traversableUnexploredCount'
)


@finalOnly
@analyzer('stepDecision')
def actions(
    exploration: core.DiscreteExploration,
    step: int,
    decision: base.DecisionID
) -> Optional[Set[base.Transition]]:
    """
    Given a particular decision at a particular step, returns the set of
    actions available at that decision in that step. Returns `None` if
    the specified decision does not exist.
    """
    graph = exploration[step].graph
    if decision not in graph:
        return None
    return graph.decisionActions(decision)


actionCount = registerCount(actions, 'actionCount')
finalOnly(actionCount)

totalActions = registerStepCombined(
    'actionCount',
    'totalActions',
    sumCombiner
)
finalOnly(totalActions)

meanActions = registerStepCombined(
    'actionCount',
    'meanActions',
    meanCombiner
)
finalOnly(meanActions)

medianActions = registerStepCombined(
    'actionCount',
    'medianActions',
    medianCombiner
)
finalOnly(medianActions)


@finalOnly
@analyzer('stepDecision')
def branches(
    exploration: core.DiscreteExploration,
    step: int,
    decision: base.DecisionID
) -> Optional[int]:
    """
    Computes the number of branches at a particular decision, not
    counting actions, but counting as separate branches multiple
    transitions which lead to the same decision as each other. Returns
    `None` for unconfirmed and nonexistent decisions so that they aren't
    counted as part of averages, even though unconfirmed decisions do
    have countable branches.
    """
    graph = exploration[step].graph
    if decision not in graph or not graph.isConfirmed(decision):
        return None

    dests = graph.destinationsFrom(decision)
    branches = 0
    for transition, dest in dests.items():
        if dest != decision:
            branches += 1

    return branches


totalBranches = registerStepCombined(
    'branches',
    'totalBranches',
    sumCombiner
)
finalOnly(totalBranches)

meanBranches = registerStepCombined(
    'branches',
    'meanBranches',
    meanCombiner
)
finalOnly(meanBranches)

medianBranches = registerStepCombined(
    'branches',
    'medianBranches',
    medianCombiner
)
finalOnly(medianBranches)


@analyzer('decision')
def arrivals(
    exploration: core.DiscreteExploration,
    decision: base.DecisionID
) -> int:
    """
    Given an `DiscreteExploration` object and a particular `Decision`
    which exists at some point during that exploration, counts the number
    of times that decision was in the active decision set for a step
    after not being in that set the previous step. Effectively, counts
    how many times we arrived at that decision, ignoring steps where we
    remained at it due to a wait or an action or the like.

    Returns 0 even for decisions that aren't part of the exploration.
    """
    visits = stepsVisited(exploration)
    result = 0
    prev = -2  # won't be contiguous with step 0
    for step in visits.get(decision, []):
        # if previous visited step wasn't the prior step it's a revisit
        if prev != step - 1:
            result += 1
        prev = step

    return result


@analyzer('decision')
def revisits(
    exploration: core.DiscreteExploration,
    decision: base.DecisionID
) -> int:
    """
    Returns the number of times we revisited the target decision, which
    is just `arrivals` minus 1 for the first arrival, but not < 0.
    """
    return max(0, arrivals(exploration, decision) - 1)


totalRevisits = registerFullCombined(
    'revisits',
    'totalRevisits',
    sumCombiner
)

meanRevisits = registerFullCombined(
    'revisits',
    'meanRevisits',
    meanCombiner
)

medianRevisits = registerFullCombined(
    'revisits',
    'medianRevisits',
    medianCombiner
)

registerFullCombined(
    'revisits',
    'revisitFraction',
    cast(
        OverallCombiner[Optional[float]],
        makeFractionCombiner(
            lambda dID, rev: rev > 0
        )
    )
)


#-------------------#
# Paths & distances #
#-------------------#

HopPaths: 'TypeAlias' = Dict[
    Tuple[base.DecisionID, base.DecisionID],
    Optional[List[base.DecisionID]]
]
"""
Records paths between decisions ignoring edge directions & requirements.
Stores a list of decision IDs to traverse keyed by a decision ID pair
where the smaller decision ID comes first (since paths are symmetric).
"""


def hopDistance(
    hopPaths: HopPaths,
    src: base.DecisionID,
    dst: base.DecisionID
) -> Optional[int]:
    """
    Returns the number of hops required to move from the given source to
    the given destination, ignoring edge directions & requirements.
    Looks that up in the given `HopPaths` dictionary. Returns 0 when
    source and destination are the same.

    For example:

    >>> e = core.DiscreteExploration.example()
    >>> hops = shortestHopPaths(e[-1].graph)
    >>> hopDistance(hops, 0, 1)
    1
    >>> hopDistance(hops, 1, 0)
    1
    >>> hopDistance(hops, 0, 0)
    0
    >>> hopDistance(hops, 0, 0)
    0
    >>> hopDistance(hops, 0, 4) is None
    True
    >>> hopDistance(hops, 4, 0) is None
    True
    >>> hopDistance(hops, 0, 5)
    2
    >>> hopDistance(hops, 5, 0)
    2
    >>> hopDistance(hops, 5, 1)
    3
    >>> hopDistance(hops, 1, 5)
    3
    >>> hopDistance(hops, 3, 5)
    1
    >>> hopDistance(hops, 5, 3)
    1
    >>> dIDs = list(e[-1].graph)
    >>> for i, src in enumerate(dIDs):
    ...     for j in range(i + 1, len(dIDs)):
    ...         dst = dIDs[j]
    ...         assert (
    ...             hopDistance(hops, src, dst) == hopDistance(hops, dst, src)
    ...         )
    """
    if src == dst:
        return 0
    elif src < dst:
        path = hopPaths.get((src, dst))
        if path is None:
            return None
        else:
            return 1 + len(path)
    else:
        path = hopPaths.get((dst, src))
        if path is None:
            return None
        else:
            return 1 + len(path)


def shortestHopPaths(
    graph: core.DecisionGraph,
    includeOnly: Optional[Callable[
        [
            base.DecisionID,
            base.Transition,
            base.DecisionID,
            core.DecisionGraph
        ],
        bool
    ]] = None
) -> HopPaths:
    """
    Creates a dictionary that holds shortest paths between pairs of
    nodes, ignoring edge directions and requirements entirely.

    If given an `includeOnly`, that function is applied with source ID,
    transition name, destination ID, and full graph as arguments and
    edges for which it returns False are ignored when computing hops.
    Note that you have to filter out all edges in both directions between
    two nodes for there not to be a 1-hop path between them.

    Keys in the dictionary are pairs of decision IDs, where the decision
    with the smaller ID always comes first (because shortest hop paths
    are symmetric so we don't store the reverse paths). Values are lists
    of decision IDs that can be traversed to get from the first decision
    to the second, with an empty list indicating adjacent decisions
    (note that these "hop paths" cannot always be traversed in the
    actual graph because they may go the "wrong way" across one-way
    connections). The number of hops required to get between the nodes
    is one more than the length of the path. Decision pairs which are
    not reachable from each other will not be included in the
    dictionary. Only decisions present in the final graph in the
    exploration will be included, and only edges present in that final
    graph will be considered.

    Where there are multiple shortest hop paths, an arbitrary one is
    included in the result.

    >>> e = core.DiscreteExploration.example()
    >>> graph = e[-1].graph
    >>> print(graph.namesListing(e[-1].graph))
      0 (House)
      1 (_u.0)
      2 (Cellar)
      3 (Yard)
      5 (Lane)
    <BLANKLINE>
    >>> shortest = dict(nx.all_pairs_shortest_path(graph.connections()))
    >>> for src in shortest:
    ...    print(f"{src} -> {shortest[src]}")
    0 -> {0: [0], 1: [0, 1], 2: [0, 2], 3: [0, 3], 5: [0, 3, 5]}
    1 -> {1: [1], 0: [1, 0], 2: [1, 0, 2], 3: [1, 0, 3], 5: [1, 0, 3, 5]}
    2 -> {2: [2], 0: [2, 0], 3: [2, 3], 1: [2, 0, 1], 5: [2, 3, 5]}
    3 -> {3: [3], 0: [3, 0], 2: [3, 2], 5: [3, 5], 1: [3, 0, 1]}
    5 -> {5: [5], 3: [5, 3], 0: [5, 3, 0], 2: [5, 3, 2], 1: [5, 3, 0, 1]}
    >>> hops = shortestHopPaths(graph)
    >>> for src in hops:
    ...     print(f"{src} -> {hops[src]}")
    (0, 1) -> []
    (0, 2) -> []
    (0, 3) -> []
    (0, 5) -> [3]
    (1, 2) -> [0]
    (1, 3) -> [0]
    (1, 5) -> [0, 3]
    (2, 3) -> []
    (2, 5) -> [3]
    (3, 5) -> []
    """
    allIDs = sorted(graph)
    connections = graph.connections(includeOnly)
    shortest = dict(nx.all_pairs_shortest_path(connections))

    result = {}
    for i, src in enumerate(allIDs):
        for j in range(i + 1, len(allIDs)):
            dst = allIDs[j]
            path = shortest.get(src, {}).get(dst, None)
            if path is not None:
                result[(src, dst)] = path[1:-1]

    return result


@elide
@analyzer('exploration')
def finalHopPaths(exploration: core.DiscreteExploration) -> HopPaths:
    """
    Applies `shortestHopPaths` to the final graph in the given
    `core.DiscreteExploration`.
    """
    return shortestHopPaths(exploration[-1].graph)


VarState = TypeVar('VarState', bound=base.BasicState)


# TODO: Diameter/girth?


def successorStates(
    onGraph: core.DecisionGraph,
    fromState: VarState
) -> Dict[Tuple[base.DeparturePoint, base.AnyFixedTransition], VarState]:
    """
    Given a `core.DecisionGraph` and a game `base.BasicState` or
    `base.State`, Returns a dictionary mapping `base.DeparturePoint` /
    `base.AnyTransition` pairs to successor states that would be reached
    by taking those transitions from those departure points. Only/all
    transitions traversable from the starting state are included.

    Does not include the possibility of reverting to any saved states.

    Note: when a transition with challenges is encountered, the resulting
    successor states dictionary will include entries for each possible
    combination of outcomes of those challenges, HOWEVER, it will not
    include entries for each possible combination of outcomes of
    challenges triggered by 'follow' effects. Instead, the outcomes for
    any challenges on followed transitions will be the most likely
    outcomes for those challenges, biased towards success in 50/50 cases.

    TODO: Add effect type for swapping active focal context, since
    there's currently no way for search to do that.

    Example:

    >>> g = core.DecisionGraph.example('abc')
    >>> # complex B-A-C arrangement w/ lever & helmets
    >>> s = base.emptyState()
    >>> fc = s['contexts']['main']
    >>> fc['activeDecisions']['main'] = 0  # A
    >>> s['exploration'] = {0: 'exploring', 1: 'unknown', 2: 'unknown'}
    >>> s['primaryDecision'] = 0
    >>> succ = successorStates(g, s)
    >>> len(succ)
    2
    >>> list(succ.keys())  # up_left not an option due to requirement
    [(('active', 0), 'left'), (('active', 0), 'down')]
    >>> wentLeft = base.emptyState()
    >>> wentLeft['exploration'] = {0: 'exploring', 1: 'exploring', 2: 'unknown'}
    >>> wentLeft['primaryDecision'] = 1
    >>> leftFC = wentLeft['contexts']['main']
    >>> leftFC['activeDecisions']['main'] = 1  # B
    >>> succ[(('active', 0), "left")] == wentLeft
    True
    >>> wentDown = base.emptyState()
    >>> wentDown['exploration'] = {0: 'exploring', 1: 'unknown', 2: 'exploring'}
    >>> wentDown['primaryDecision'] = 2
    >>> downFC = wentDown['contexts']['main']
    >>> downFC['activeDecisions']['main'] = 2  # C
    >>> succ[(('active', 0), "down")] == wentDown
    True
    >>> succLeft = successorStates(g, wentLeft)
    >>> len(succLeft)
    1
    >>> list(succLeft.keys())
    [(('active', 1), 'right')]
    >>> backRight = copy.deepcopy(s)  # gets back to almost original state
    >>> backRight['exploration'][1] = "exploring"
    >>> succLeft[(('active', 1), "right")] == backRight
    True
    >>> succDown = successorStates(g, wentDown)
    >>> len(succDown)
    2
    >>> list(succDown.keys())
    [(('active', 2), 'up'), (('active', 2), 'grab_helmet')]
    >>> backUp = copy.deepcopy(s)
    >>> backUp['exploration'][2] = "exploring"
    >>> succDown[(('active', 2), "up")] == backUp  # back to almost original
    True
    >>> gotHelm = base.emptyState()
    >>> gotHelm['exploration'] = {0: 'exploring', 1: 'unknown', 2: 'exploring'}
    >>> gotHelm['primaryDecision'] = 2
    >>> gotHelm['effectCounts'] = {
    ...     (2, 'grab_helmet', 1): 1,
    ...     (2, 'grab_helmet', 2): 1
    ... }
    >>> helmetFC = gotHelm['contexts']['main']
    >>> helmetFC['activeDecisions']['main'] = 2  # C
    >>> helmetFC['capabilities']['capabilities'].add('helmet')
    >>> succDown[(('active', 2), "grab_helmet")] == gotHelm
    True
    >>> succHelmet = successorStates(g, gotHelm)
    >>> len(succHelmet)
    2
    >>> list(succHelmet.keys())
    [(('active', 2), 'up'), (('active', 2), 'pull_lever')]
    >>> pulledLever = base.emptyState()
    >>> pulledLever['exploration'] = copy.deepcopy(gotHelm['exploration'])
    >>> pulledLever['primaryDecision'] = 2
    >>> pulledLever['effectCounts'] = {
    ...     (2, 'grab_helmet', 1): 1,
    ...     (2, 'grab_helmet', 2): 1,
    ...     (2, 'pull_lever', 1): 1,
    ...     (2, 'pull_lever', 2): 1
    ... }
    >>> leverFC = pulledLever['contexts']['main']
    >>> leverFC['activeDecisions']['main'] = 2  # C
    >>> leverFC['capabilities']['tokens']['token'] = 1
    >>> gotHelmetWentUp = copy.deepcopy(gotHelm)
    >>> gotHelmetWentUp['exploration'][2] = "exploring"
    >>> gotHelmetWentUp['primaryDecision'] = 0
    >>> gotHelmetWentUp['contexts']['main']['activeDecisions']['main'] = 0  # A
    >>> succHelmet[(('active', 2), "pull_lever")] == pulledLever
    True
    >>> succHelmet[(('active', 2), "up")] == gotHelmetWentUp
    True
    """
    result = {}
    activeContext = fromState['contexts'][fromState['activeContext']]
    commonContext = fromState['common']
    capableOf = base.effectiveCapabilitySet(fromState)
    activeDecisions = base.activeDecisionSet(activeContext)
    combinedDecisions = base.combinedDecisionSet(fromState)

    # Consider each active decision...
    for decisionID in combinedDecisions:

        # All ways in which one could depart this active decision
        # (possible via active and/or common contexts, and via various
        # focal points if in a plural-focalized domain
        departurePoints: List[base.DeparturePoint] = []

        # Figure out what DeparturePoint to use for this one:
        domain = onGraph.domainFor(decisionID)
        if domain in activeContext['activeDecisions']:
            activeHere = activeContext['activeDecisions'][domain]
            if (
                isinstance(activeHere, base.DecisionID)
            and activeHere == decisionID
            ):
                departurePoints.append(("active", decisionID))
                # otherwise try common context below
            elif (
                isinstance(activeHere, set)
            and decisionID in activeHere
            ):
                departurePoints.append(("active", decisionID))
                # otherwise try common context below
            elif isinstance(activeHere, dict):
                for (focus, atID) in activeHere.items():
                    if atID == decisionID:
                        departurePoints.append(("active", domain, focus))
                # otherwise try common context below

        if domain in commonContext['activeDecisions']:
            activeHere = commonContext['activeDecisions'][domain]
            if (
                isinstance(activeHere, base.DecisionID)
            and activeHere == decisionID
            ):
                departurePoints.append(("common", decisionID))
                # otherwise no luck; error below
            elif (
                isinstance(activeHere, set)
            and decisionID in activeHere
            ):
                departurePoints.append(("common", decisionID))
                # otherwise no luck; error below
            elif isinstance(activeHere, dict):
                for (focus, atID) in activeHere.items():
                    if atID == decisionID:
                        departurePoints.append(("common", domain, focus))
                # otherwise no luck; error below

        if len(departurePoints) == 0:
            raise RuntimeError(
                f"Active decision {onGraph.identityOf(decisionID)} is in"
                f" domain {domain} but that domain doesn't appear in the"
                f" active decisions slot of either the active or current"
                f" contexts for the origin state."
            )

        departingFrom: base.DeparturePoint = None
        useContext: base.ContextSpecifier = "active"
        moveWhich: Optional[base.FocalPointName] = None

        # Add entries for each departure point
        for departingFrom in departurePoints:
            assert departingFrom is not None
            useContext = departingFrom[0]
            if len(departingFrom) == 3:
                moveWhich = departingFrom[2]

        outgoing = onGraph.destinationsFrom(decisionID)
        # Consider each transition from this decision:
        for (transition, destinationID) in outgoing.items():
            if (decisionID, transition) in fromState['deactivated']:
                # this transition has been deactivated
                continue
            req = onGraph.getTransitionRequirement(decisionID, transition)
            ctx = base.RequirementContext(
                graph=onGraph,
                state=fromState,
                searchFrom=onGraph.bothEnds(decisionID, transition)
            )
            if req.satisfied(ctx):
                # this transition's requirements are met: add it to our
                # possible options
                toApply = onGraph.getConsequence(decisionID, transition)
                altDest = None
                outcomeLists = base.enumerateChallengeOutcomes(ctx, toApply)
                if len(outcomeLists) == 0:
                    outcomeLists = [[]]
                # One key per possible challenge outcomes list
                for outcomes in outcomeLists:
                    key: Tuple[base.DeparturePoint, base.AnyFixedTransition]
                    if len(outcomes) == 0:
                        key = (departingFrom, transition)
                    else:
                        key = (departingFrom, (transition, tuple(outcomes)))

                    # Add successor state to our result
                    result[key] = successorState(
                        fromState,
                        onGraph,
                        decisionID,
                        transition,
                        destinationID,
                        toApply,
                        outcomes,
                        "mostLikely",
                        useContext,
                        moveWhich
                    )

    return result


def successorState(
    fromState: VarState,
    onGraph: core.DecisionGraph,
    decisionID: base.DecisionID,
    transition: base.Transition,
    destinationID: base.DecisionID,
    toApply: base.Consequence,
    outcomes: List[bool],
    outcomesPolicy: base.ChallengePolicy = "mostLikely",
    whichContext: base.ContextSpecifier = "active",
    moveWhich: Optional[base.FocalPointName] = None,
) -> VarState:
    """
    Given an initial state, a decision graph, a departure decision ID, a
    transition taken, a destination decision ID, a `base.Consequence` to
    apply, and an outcomes list for challenges, returns the successor
    state reached by applying those consequences while traversing that
    transition between those decisions assuming the given challenge
    outcomes.

    `whichContext` may be specified to indicate whether to update the
    active focal context or the common focal context; default is the
    active one.

    `moveWhich` may be provided to specify which focal point to move in
    plural-focalized domains.

    The given `outcomesPolicy` will be used to determine outcomes of
    challenges beyond those listed in the provided `outcomes` list.

    Note that this function will not make any modifications to the
    decision graph, so effects like 'edit' effects cannot be fully
    applied and will result in an error. There is also no full
    `base.Situation` object, so `save` effects cannot apply, but these
    are ignored instead of causing errors.

    Example:

    >>> g = core.DecisionGraph.example('abc')
    >>> # complex B-A-C arrangement w/ lever & helmets
    >>> s = base.emptyState()
    >>> fc = s['contexts']['main']
    >>> fc['activeDecisions']['main'] = 0  # A
    >>> s['exploration'] = {0: 'exploring', 1: 'unknown', 2: 'unknown'}
    >>> s['primaryDecision'] = 0
    >>> succLeft = successorState(s, g, 0, 'left', 1, [], [])
    >>> expLeft = base.emptyState()
    >>> expLeft['exploration'] = {0: 'exploring', 1: 'exploring', 2: 'unknown'}
    >>> expLeft['primaryDecision'] = 1
    >>> leftFC = expLeft['contexts']['main']
    >>> leftFC['activeDecisions']['main'] = 1  # B
    >>> succLeft == expLeft
    True

    TODO: Test w/ challenge outcomes?
    """
    result = copy.deepcopy(fromState)
    base.applySimpleTransitionEffectsToState(
        result,
        onGraph,
        decisionID,
        transition,
        destinationID,
        toApply,
        outcomes,
        outcomesPolicy,
        whichContext,
        moveWhich,
        False  # DON'T update the graph!
    )

    return result


HE = TypeVar('HE')


def shortestStatePath(
    onGraph: core.DecisionGraph,
    fromState: VarState,
    accept: Callable[[core.DecisionGraph, VarState], bool],
    heuristic: Union[
        None,
        Callable[[core.DecisionGraph, VarState], int],
        Callable[[core.DecisionGraph, VarState, HE], int]
    ] = None,
    stepsLimit: Optional[int] = None,
    heuristicExtra: Optional[HE] = None
) -> Optional[base.StatePath]:
    """
    Given a `core.DecisionGraph`, a `base.State`, and a function that
    evaluates a graph + single state and returns true or false to
    indicate whether that state is acceptable as a destination or not,
    this function returns a `StatePath` starting from the provided state
    that reaches a state acceptable to the evaluation function. It uses
    A* search to find a shortest path guided by the given heuristic
    function no guarantees which if multiple shortest paths exist).

    The heuristic function should which takes a graph and a `base.State`
    and returns an int. Optionally, a `heuristicExtra` value may be
    provided in which case the heuristic function will be given that
    value as its third argument. The `heuristicExtra` value may not be
    `None`, as in that case no third argument is given tot he heuristic
    function.

    If no heuristic function is provided, an all-zero heuristic will be
    used. If the heuristic is not admissible (i.e., if it ever
    overestimates the true number of states that need to be traversed to
    reach an acceptable state) then a non-shortest path may be returned.

    Returns `None` if no path to an acceptable state can be found (may
    take a while as it does this only after exhausting the reachable
    state space; could take forever on some graphs). If a `stepsLimit`
    is given then paths that are longer than that limit will not be
    considered (default is no limit).

    Note: the cost of this can easily be prohibitive.
    """
    queue = base.StatesQueue()
    queue.pushOrAdjust(
        fromState,
        0,
        0,
        (None, None, None),
        ignoreIfHigher=True
    )
    while len(queue) > 0:
        # Expand the best-estimate state
        stepsTo, state = queue.pop()
        state = cast(VarState, state)
        if accept(onGraph, state):
            # Return result if we've reached an acceptable state
            result = queue.pathTo(state)
            assert result is not None
            return result
        elif stepsLimit is not None and stepsTo >= stepsLimit:
            # Ignore paths that require taking more steps than the limit
            continue
        else:
            # Compute next states & add them to the queue
            successors = successorStates(
                onGraph,
                state
            )
            for (
                (departurePoint, transitionTaken),
                arrivedAt
            ) in successors.items():
                arrivedAt = cast(VarState, arrivedAt)
                if heuristic is None:
                    priority = stepsTo + 1
                else:
                    if heuristicExtra is not None:
                        heuristic = cast(
                            Callable[
                                [
                                    core.DecisionGraph,
                                    VarState,
                                    Optional[HE]
                                ],
                                int
                            ],
                            heuristic
                        )
                        priority = stepsTo + 1 + heuristic(
                            onGraph,
                            arrivedAt,
                            heuristicExtra
                        )
                    else:
                        heuristic = cast(
                            Callable[[core.DecisionGraph, VarState], int],
                            heuristic
                        )
                        priority = stepsTo + 1 + heuristic(
                            onGraph,
                            arrivedAt
                        )
                queue.pushOrAdjust(
                    arrivedAt,
                    priority,
                    stepsTo + 1,
                    (state, departurePoint, transitionTaken),
                    ignoreIfHigher=True
                )

    # Ran out of states to expand; no path found
    return None


MajorItemSet: TypeAlias = Tuple[
    List[base.Capability],
    List[base.Token],
    List[base.Token],
    List[base.MechanismID],
]
"""
A tuple with lists of capabilities, token names (for countable tokens),
token names (for not-simply-countable tokens) and mechanism IDs that
specifies which parts of a state should be "major items" in a particular
game (or for a particular search).

If a token is "countable" that means that we assume each one is picked
up (or used) individually, so we can count the number of tokens of
difference as part of an estimate of the distance between two states. If
it's not (i.e., if it's included in the second list instead of the
first) then we count 1 distance if two states have different amounts and
0 distance if they have the same amount, but we don't pay attention to
the exact number of tokens. For example, in Zelda games, silver keys
would be countable but rupees would not be, since you might gain or lose
multiple rupees at a time.
"""


def stateChangesEstimate(
    onGraph: core.DecisionGraph,
    majors: MajorItemSet,
    fromState: base.BasicState,
    toState: base.BasicState
) -> int:
    """
    Given a `core.DecisionGraph` and a `MajorItemSet`, estimates the
    number of state changes required to get from the given `fromState`
    to the given `toState` as the number of major items for which those
    states differ. Counts 1 step for each capability that's different,
    plus 1 step per token for each 'countable' token that's different,
    plus 1 step per KIND of token for non-countable tokens with
    different amounts, plus 1 step for each mechanism that's in a
    different state.
    """
    fromCtx = base.RequirementContext(fromState, onGraph, set())
    toCtx = base.RequirementContext(toState, onGraph, set())
    result = 0
    for capability in majors[0]:
        fromHas = base.hasCapabilityOrEquivalent(capability, fromCtx)
        toHas = base.hasCapabilityOrEquivalent(capability, toCtx)
        if fromHas != toHas:
            result += 1
    for countableToken in majors[1]:
        fromCount = base.combinedTokenCount(fromState, countableToken)
        toCount = base.combinedTokenCount(toState, countableToken)
        result += abs(fromCount - toCount)
    for massToken in majors[2]:
        fromCount = base.combinedTokenCount(fromState, massToken)
        toCount = base.combinedTokenCount(toState, massToken)
        if fromCount != toCount:
            result += 1
    for mechanism in majors[3]:
        fromMechanismState = base.stateOfMechanism(fromCtx, mechanism)
        toMechanismState = base.stateOfMechanism(toCtx, mechanism)
        if fromMechanismState != toMechanismState:
            result += 1

    return result


def shortestStatePathToActivate(
    onGraph: core.DecisionGraph,
    fromState: base.BasicState,
    getTo: base.DecisionID,
    stepsLimit: Optional[int] = None
) -> Optional[base.StatePath]:
    """
    Uses `shortestStatePath` to find a shortest path on the given graph
    that activates the specified decision. If a `stepsLimit` is given,
    doesn't consider paths with more than that many steps.

    Examples:

    >>> g = core.DecisionGraph.example('abc')
    >>> s0 = base.emptyState()
    >>> s0['exploration'] = {0: 'exploring', 1: 'unknown', 2: 'unknown'}
    >>> s0['primaryDecision'] = 0
    >>> fc0 = s0['contexts']['main']
    >>> fc0['activeDecisions']['main'] = 0
    >>> origS0 = copy.deepcopy(s0)
    >>> shortestStatePathToActivate(g, s0, 1, 0) is None  # 0-step limit
    True
    >>> p = shortestStatePathToActivate(g, s0, 1)
    >>> s0 == origS0
    True
    >>> len(p)
    2
    >>> p[0] == (None, None, s0)
    True
    >>> wentLeft = copy.deepcopy(s0)
    >>> wentLeft['exploration'][1] = 'exploring'
    >>> wentLeft['primaryDecision'] = 1
    >>> wentLeft['contexts']['main']['activeDecisions']['main'] = 1
    >>> p[1] == (('active', 0), 'left', wentLeft)
    True

    >>> g2 = core.DecisionGraph()
    >>> g2.addDecision('A')
    0
    >>> g2.addDecision('B')
    1
    >>> g2.addDecision('C')
    2
    >>> g2.addDecision('D')
    3
    >>> g2.addTransition('A', 'up', 'B', 'down')
    >>> g2.addTransition('A', 'right', 'C', 'left')
    >>> g2.addTransition('C', 'right', 'D', 'left')
    >>> g2.setTransitionRequirement('C', 'right', base.ReqCapability('x'))
    >>> g2.addAction('B', 'get', consequence=[base.effect(gain='x')])
    >>> shortestStatePathToActivate(g2, s0, 3, 4) is None
    True
    >>> p2 = shortestStatePathToActivate(g2, s0, 3, 5)
    >>> len(p2)
    6
    >>> print(base.statePathSummary(p2, g2))
    start of path
    took 'up' from A to B
    did 'get' at B (gained x)
    took 'down' from B to A
    took 'right' from A to C
    took 'right' from C to D
    <BLANKLINE>
    >>> def cf(step):
    ...     return base.RequirementContext(p2[step][2], g2, set())
    >>> [base.hasCapabilityOrEquivalent('x', cf(i)) for i in range(6)]
    [False, False, True, True, True, True]
    >>> # Add a shortcut:
    >>> g2.addTransition('B', 'around', 'D', 'back')
    >>> p3 = shortestStatePathToActivate(g2, s0, 3, 3)
    >>> print(base.statePathSummary(p3, g2))
    start of path
    took 'up' from A to B
    took 'around' from B to D
    <BLANKLINE>
    """
    def heuristic(
        graph: core.DecisionGraph,
        state: base.BasicState,
        hops: HopPaths
    ) -> int:
        """
        Heuristic that estimates using hop path distance to target
        decision from ANY active decision. If no hop path from any
        active decision to the target decision is available, it will
        return `sys.maxsize`.
        """
        active = base.combinedDecisionSet(state)
        best = None
        for src in active:
            dist = hopDistance(hops, src, getTo)
            if dist is not None:
                if best is None or dist < best:
                    best = dist
        if best is None:
            return sys.maxsize
        else:
            return best

    def accept(graph: core.DecisionGraph, state: base.BasicState) -> bool:
        """
        Returns true if the destination decision is active.
        """
        return getTo in base.combinedDecisionSet(state)

    hops = shortestHopPaths(onGraph)
    return shortestStatePath(
        onGraph,
        fromState,
        accept,
        heuristic,
        stepsLimit,
        hops
    )

def changesToSatisfy(
    req: base.Requirement,
    ctx: base.RequirementContext
) -> int:
    """
    Returns an estimate of the number of state changes required to
    satisfy the given requirement, relative to the given context. If the
    requirement is already satisfied, returns 0. Note that this counts
    the number of capabilities that would need to be gained/lost, the
    number of *types* tokens which would need to change counts, and the
    number of mechanisms that would need to change state, returning a
    minimum across disjunctions. This can be an overestimate of the
    number of state transitions necessary to satisfy the requirement if
    a single transition has consequences which change multiple things at
    once.
    """
    if req.satisfied(ctx):
        return 0
    elif isinstance(req, base.ReqAll):
        return sum(changesToSatisfy(sub, ctx) for sub in req.subs)
    elif isinstance(req, base.ReqAny):
        return min(changesToSatisfy(sub, ctx) for sub in req.subs)
    else:
        return 1


def shortestStatePathToAchieve(
    onGraph: core.DecisionGraph,
    fromState: base.BasicState,
    goal: base.Requirement,
    stepsLimit: Optional[int] = None
) -> Optional[base.StatePath]:
    """
    Uses `shortestStatePath` to find a path that fulfils the given
    requirement.

    In a given successor state, the mechanism search context for checking
    the requirement will include the decision departed from in the
    previous state, and the decision arrived at in the successor state
    being evaluated.

    If a `stepLimit` is provided, the search will not consider any paths
    longer than that.

    TODO: Include all decisions visited via effects in mechanism search
    context?

    Examples:

    >>> g = core.DecisionGraph.example('abc')
    >>> s0 = base.emptyState()
    >>> s0['exploration'] = {0: 'exploring', 1: 'unknown', 2: 'unknown'}
    >>> s0['primaryDecision'] = 0
    >>> fc0 = s0['contexts']['main']
    >>> fc0['activeDecisions']['main'] = 0
    >>> r = base.ReqCapability('helmet')
    >>> origS0 = copy.deepcopy(s0)
    >>> shortestStatePathToAchieve(g, s0, r, 1) is None  # 1-step limit
    True
    >>> p = shortestStatePathToAchieve(g, s0, r, 2)
    >>> s0 == origS0
    True
    >>> len(p)
    3
    >>> p[0] == (None, None, s0)
    True
    >>> print(base.statePathSummary(p, g))
    start of path
    took 'down' from A to C
    did 'grab_helmet' at C (gained helmet)
    <BLANKLINE>
    >>> r2 = base.ReqTokens('token', 2)
    >>> p2 = shortestStatePathToAchieve(g, s0, r2)
    >>> len(p2)
    6
    >>> print(base.statePathSummary(p2, g))
    start of path
    took 'down' from A to C
    did 'grab_helmet' at C (gained helmet)
    did 'pull_lever' at C (lost helmet; gained token*1)
    did 'grab_helmet' at C (gained helmet)
    did 'pull_lever' at C (lost helmet; gained token*1)
    <BLANKLINE>
    >>> r3 = base.ReqAll([
    ...     base.ReqMechanism('grate', 'open'), 
    ...     base.ReqTokens('token', 3), 
    ... ])  # note just the grate can be done via equivalence w/ helmet
    >>> p3 = shortestStatePathToAchieve(g, s0, r3)
    >>> len(p3)
    8
    >>> print(base.statePathSummary(p3, g))
    start of path
    took 'down' from A to C
    did 'grab_helmet' at C (gained helmet)
    did 'pull_lever' at C (lost helmet; gained token*1)
    did 'grab_helmet' at C (gained helmet)
    did 'pull_lever' at C (lost helmet; gained token*1)
    did 'grab_helmet' at C (gained helmet)
    did 'pull_lever' at C (lost helmet; gained token*1; set grate from off to open)
    <BLANKLINE>
    """
    def heuristic(
        graph: core.DecisionGraph,
        state: base.BasicState
    ) -> int:
        """
        Heuristic that estimates using number of unsatisfied clauses.
        """
        ctx = base.RequirementContext(
            state,
            graph,
            base.combinedDecisionSet(state)
        )
        # TODO: Better would be to include
        # distances-to-places-where-things-can-be-changed...
        return changesToSatisfy(goal, ctx)

    def accept(graph: core.DecisionGraph, state: base.BasicState) -> bool:
        """
        Returns true if the destination decision is active.
        """
        ctx = base.RequirementContext(
            state,
            graph,
            base.combinedDecisionSet(state)
        )
        # TODO: Include arrival info so we can more accurately check
        # mechanism states...
        return goal.satisfied(ctx)

    return shortestStatePath(
        onGraph,
        fromState,
        accept,
        heuristic,
        stepsLimit
    )


def mutuallyReachabeSet(
    onGraph: core.DecisionGraph,
    fromState: base.BasicState,
) -> Dict[base.DecisionID, base.StateDifferences]:
    # TODO: HERE
    return {}
    pass


#--------#
# Cycles #
#--------#

CycleList: 'TypeAlias' = List[List[base.DecisionID]]
"""
A list of cycles within the graph, 
"""


def cycleBasis(
    graph: core.DecisionGraph,
    includeOnly: Optional[Callable[
        [
            base.DecisionID,
            base.Transition,
            base.DecisionID,
            core.DecisionGraph
        ],
        bool
    ]] = None
) -> CycleList:
    """
    Returns a list of cycles which forms a cycle basis for the graph,
    treating it as an undirected non-multi graph (see
    `graphs.UniqueExitsGraph.connections`). The `includeOnly` if one is
    provided will be passed to that function to filter edges before the
    graph is simplified; self-edges are also removed.

    See: [the networkx reference for the `cycle_basis`
    function)[https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.cycles.cycle_basis.html].

    Due to the simplification, we don't count every transition plus its
    reciprocal as a possible cycle, and even if there are multiple
    transition/reciprocal pairs between two decisions, we don't count
    those two as a cycle. Only cases where we can move back to an
    original decision around at least a triangle of 3 decisions count as
    cycles.
    """
    combinedFilter = lambda fr, tr, to, gr: (
        fr != to and (includeOnly is None or includeOnly(fr, tr, to, gr))
    )
    simplified = graph.connections(combinedFilter)
    return nx.cycle_basis(simplified)


@elide
@analyzer('step')
def stepCycleBasis(
    exploration: core.DiscreteExploration,
    step: int
) -> CycleList:
    """
    Applies `cycleBasis` to the graph for the given step in the given
    `core.DiscreteExploration`.
    """
    return cycleBasis(exploration[step].graph)


@elide
@analyzer('step')
def stepCycleMap(
    exploration: core.DiscreteExploration,
    step: int
) -> Dict[base.DecisionID, List[base.DecisionID]]:
    """
    Runs `stepCycleBasis` and then converts it into a mapping from
    decision IDs to their basis cycles. Decisions not part of any cycle
    won't appear as keys in the map.
    """
    result = {}
    basis = stepCycleBasis(exploration, step)
    for cycle in basis:
        for dID in cycle:
            result[dID] = cycle
    return result

@elide
@analyzer('stepDecision')
def basisCycle(
    exploration: core.DiscreteExploration,
    step: int,
    decision: base.DecisionID
) -> Optional[List[base.DecisionID]]:
    """
    Returns the basis cycle which includes the given decision, or None
    if the decision is not part of any cycles. Note that when there are
    overlapping cycles, the cycle list may not actually be a real cycle
    on its own.

    TODO: Better here?
    """
    return stepCycleMap(exploration, step).get(decision)

@elide
@analyzer('step')
def stepCyclicSet(
    exploration: core.DiscreteExploration,
    step: int
) -> Set[base.DecisionID]:
    """
    Uses the cycle basis to create the set of all decisions that are
    part of at least one cycle in the given step.
    """
    basis = stepCycleBasis(exploration, step)
    result = set()
    for cycle in basis:
        result.update(cycle)
    return result


@finalOnly
@analyzer('stepDecision')
def onAnyCycle(
    exploration: core.DiscreteExploration,
    step: int,
    decision: base.DecisionID
) -> Optional[bool]:
    """
    Uses the `stepCyclicSet` to determine whether this decision is part
    of any cycle or not at the given step. Returns `None` for decisions
    that don't exist or which are unconfirmed in the specified step.
    """
    graph = exploration[step].graph
    if decision not in graph or not graph.isConfirmed(decision):
        return None
    else:
        return decision in stepCyclicSet(exploration, step)


@finalOnly
@analyzer('step')
def cyclicFraction(
    exploration: core.DiscreteExploration,
    step: int
) -> float:
    """
    Uses the `stepCyclicSet` to figure out the fraction of *all*
    decisions in the specified step which are part of any cycle (as
    opposed to being part of a branching non-cyclic structure).
    Unconfirmed decisions are included in the count.
    """
    return (
        len(stepCyclicSet(exploration, step))
      / len(exploration[step].graph)
    )


#-----------------------------------#
# Discovery & Traversibility Timing #
#-----------------------------------#

class TransitionProspectus(TypedDict):
    """
    Information about when a transition was discovered, when it first
    became traversable, and when both of its endpoints were confirmed.

    Defaults are `None` to indicate 'never'.
    """
    discovered: Optional[int]
    traversable: Optional[int]
    confirmed: Optional[int]


@analyzer('exploration')
def transitionProspectus(
    exploration: core.DiscreteExploration
) -> Dict[SpecificTransition, TransitionProspectus]:
    """
    Returns a dictionary mapping each specific transition that's present
    in the final graph to a `TransitionProspectus` dictionary indicating
    when it was discovered, when it first became traversable, and when
    both ends of it were confirmed.
    """
    result: Dict[SpecificTransition, TransitionProspectus] = {}
    # Figure out all transitions we want to analyze from the final graph
    lastStep = len(exploration) - 1
    final = exploration[lastStep].graph
    relevantTransitions = set()
    for decision in final:
        destinations = final.destinationsFrom(decision)
        for transition, destination in destinations.items():
            spec = (decision, transition)
            relevantTransitions.add(spec)
            try:
                traversable = exploration.isTraversable(
                    decision,
                    transition,
                    lastStep
                )
                confirmed = (
                    final.isConfirmed(decision)
                and final.isConfirmed(destination)
                )
            except Exception as e:
                note = (
                    f" (While processing transition {transition}"
                    f" from decision {final.identityOf(decision)})"
                )
                if hasattr(e, "add_note"):
                    e.add_note(note)
                else:
                    e.args = (e.args[0] + note,) + e.args[1:]
                raise e
            result[spec] = {
                'discovered': lastStep,
                'traversable': lastStep if traversable else None,
                'confirmed': lastStep if confirmed else None
            }
    # Iterate backwards so we can know from the end what all the
    # transitions are (note that transitions which are revised-out
    # before the final graph won't get analyzed).
    for step in range(lastStep - 1, -1, -1):
        graph = exploration[step].graph
        defunct = []
        for spec in relevantTransitions:
            frID, name = spec
            try:
                # Destination of this transition might be different on
                # different steps
                toID = graph.destination(frID, name)
            except (core.MissingDecisionError, core.MissingTransitionError):
                # If the transition doesn't exist in this step, we're
                # done with it
                defunct.append(spec)
                continue
            try:
                traversable = exploration.isTraversable(frID, name, step)
                confirmed = (
                    graph.isConfirmed(frID)
                and graph.isConfirmed(toID)
                )
            except Exception as e:
                try:
                    ident = graph.identityOf(decision)
                except core.MissingDecisionError:
                    ident = str(decision)
                note = (
                    f" (While processing transition {transition}"
                    f" from decision {ident})"
                )
                if hasattr(e, "add_note"):
                    e.add_note(note)
                else:
                    e.args = (e.args[0] + note,) + e.args[1:]
                raise e
            prospectus = result[spec]
            prospectus['discovered'] = step
            if traversable:
                prospectus['traversable'] = step
            if confirmed:
                prospectus['confirmed'] = step

        # Stop checking these transitions at all on earlier steps
        for spec in defunct:
            relevantTransitions.remove(spec)

    return result


@analyzer('finalTransition')
def confirmationDelay(
    exploration: core.DiscreteExploration,
    source: base.DecisionID,
    transition: base.Transition
) -> Optional[int]:
    """
    The delay between discovery of a transition and the first step on
    which both ends are confirmed. Might be `None` if a transition never
    has both ends confirmed, and/or if a transition is revised out of the
    final graph or has its destination swapped at some point.
    """
    spec = (source, transition)
    prospectus = transitionProspectus(exploration).get(spec)
    if prospectus is None:
        return None
    else:
        confirmed = prospectus['confirmed']
        discovered = prospectus['discovered']
        if confirmed is not None and discovered is not None:
            return confirmed - discovered
        else:
            return None

registerFullCombined(
    'confirmationDelay',
    'meanConfirmationDelay',
    meanCombiner
)

registerFullCombined(
    'confirmationDelay',
    'medianConfirmationDelay',
    medianCombiner
)


# Immediate confirmation can happen because the transition is between
# known endpoints or after a single step if we visit its destination
# immediately. We don't distinguish those.
registerFullCombined(
    'confirmationDelay',
    'immediateConfirmationFraction',
    cast(
        OverallCombiner[Optional[float]],
        makeFractionCombiner(
            lambda spec, delay: delay is not None and delay <= 1
        )
    )
)

# Confirmed within 5 steps (but not in 0 or 1)
registerFullCombined(
    'confirmationDelay',
    'quickConfirmationFraction',
    cast(
        OverallCombiner[Optional[float]],
        makeFractionCombiner(
            lambda spec, delay: delay is not None and 1 < delay <= 5
        )
    )
)

# Not confirmed until after at least 6 steps
registerFullCombined(
    'confirmationDelay',
    'delayedConfirmationFraction',
    cast(
        OverallCombiner[Optional[float]],
        makeFractionCombiner(
            lambda spec, delay: delay is not None and 5 < delay
        )
    )
)

# Never confirmed
registerFullCombined(
    'confirmationDelay',
    'neverConfirmedFraction',
    cast(
        OverallCombiner[Optional[float]],
        makeFractionCombiner(
            lambda spec, delay: delay is None
        )
    )
)


# TODO: Mean/median of registration delays > 5?

@analyzer('finalTransition')
def accessDelay(
    exploration: core.DiscreteExploration,
    source: base.DecisionID,
    transition: base.Transition
) -> Optional[int]:
    """
    The delay between discovery of a transition and the first step on
    which it became traversable (even if it later became untraversable
    again). Might be `None` if a transition never became traversable,
    and/or if it was revised out of the final graph.
    """
    spec = (source, transition)
    prospectus = transitionProspectus(exploration).get(spec)
    if prospectus is None:
        return None
    else:
        traversable = prospectus['traversable']
        discovered = prospectus['discovered']
        if traversable is not None and discovered is not None:
            return traversable - discovered
        else:
            return None

registerFullCombined('accessDelay', 'meanAccessDelay', meanCombiner)

registerFullCombined('accessDelay', 'medianAccessDelay', medianCombiner)

# TODO: Mean/median of access delays > 5?


# Immediate access means can traverse on same step discovered
registerFullCombined(
    'accessDelay',
    'immediateAccessFraction',
    cast(
        OverallCombiner[Optional[float]],
        makeFractionCombiner(lambda spec, delay: delay == 0)
    )
)

# Quick access means can't traverse when discovered but can within 5 steps
registerFullCombined(
    'accessDelay',
    'quickAccessFraction',
    cast(
        OverallCombiner[Optional[float]],
        makeFractionCombiner(
            lambda spec, delay: delay is not None and 0 < delay <= 5
        )
    )
)

# Delayed access is anything past 5 steps
registerFullCombined(
    'accessDelay',
    'delayedAccessFraction',
    cast(
        OverallCombiner[Optional[float]],
        makeFractionCombiner(
            lambda spec, delay: delay is not None and 5 < delay
        )
    )
)

# Quick access means can't traverse when discovered but can within 4 steps
registerFullCombined(
    'accessDelay',
    'neverAccessibleFraction',
    cast(
        OverallCombiner[Optional[float]],
        makeFractionCombiner(lambda spec, delay: delay is None)
    )
)


# TODO: Fraction of transitions confirmed in forward vs. reverse
# direction...

# TODO: Average path length...

#---------------------#
# Step classification #
#---------------------#

StepClassification: 'TypeAlias' = Literal[
    'wait',
    'takeAction',
    'trapped',
    'setOut',
    'discoverDeadEnd',
    'discoverDeadForNowEnd',
    'discoverPath',
    'discoverBranchForLater',
    'discoverIntersection',
    'discoverCycleReturn',
    'discoverComplexCycleReturn',
    'completeCycle',
    'completeCycleComplex',
    'retracePath',
    'retraceIntersection',
    'reachNewPath',
    'revisitIntersection',
    'other'
]
"""
Classifies an exploration step according to the options available at the
primary decision for that step. The classifications are:

- 'wait' is any step in which the previous step's
    `base.ExplorationAction` was 'noAction'.
- 'takeAction' is any step in which a self-transition was taken on the
    previous step, regardless of the configuration of transitions
    available after that.
- 'trapped' is a step in which all available non-action transitions are
    blocked.
- 'setOut' is a step in which one is at a previously-unvisited decision
    and there's only one transition available to explore, which leads to
    an unvisited decision. This includes situations in which there's a
    transition back where we came from but it's blocked. 'setOut' is also
    applied to every decision where the previous `base.ExplorationAction`
    is 'start', regardless of the complexity of the options available.
- 'discoverDeadEnd' is a step in which a new decision is visited, but the
    only option (ignoring actions) is to return to the
    previously-visited decision.
- 'discoverDeadForNowEnd' is a step like 'discoverDeadEnd', except that
    there are one or more not-yet-traversable option(s) that lead to
    unvisited decisions in addition to the way back.
- 'discoverPath' is a step in which a new decision is visited, which has
    exactly one transition not counting the way we just came. That single
    way forward leads to an unvisited decision.
- 'discoverBranchForLater' is a step like 'discoverPath', but where
    there are one or more additional not-yet-traversable options in
    addition to the single way forward.
- 'discoverIntersection' is a step in which a new decision is visited,
    and there are at least two currently-traversable options that lead
    onwards to other unvisited decisions (still counts if they lead to
    the same unvisited decision).
- 'discoverCycleReturn' is a step in which a new decision is visited
    which has exactly one transition besides the way back where we came
    from. That transition leads to an already-visited decision.
- 'discoverComplexCycleReturn' is a step in which a new decision is
    visited that has at least one transition to an already-visited
    decision, plus at least on other transition besides the way back to
    where we were on the previous step. Those additional transition(s)
    might or might not be currently traversable.
- 'completeCycle' is a step in which the primary decision was already
    visited on some previous step, but the primary decision of the step
    directly before this one was visited first in that step, as long as
    all outgoing transitions lead to already-visited decisions, and the
    primary decision is not the same as the primary decision two steps
    before (i.e., we're not just turning around after hitting a dead
    end or otherwise turning back the way we came).
- 'completeCycleComplex' is the same as 'completeCycle' except that there
    is at least one transition (possibly blocked) which leads to an
    unvisited decision.
- 'retracePath' is a step in which the primary decision was already
    visited on a previous step, and there are at most two outgoing
    transitions, at least one of which leads back to where we came from
    if there are two. All outgoing transitions lead to already-visited
    decisions. This applies to revisits of dead ends as well as
    retracing along paths without branches.
- 'retraceIntersection' is a step in which the primary decision was
    visited on a previous step, and there are at least two outgoing
    transitions which lead to decisions other than the one we came from.
    All outgoing transitions lead to already-visited decisions.
- 'reachNewPath' is a step in which the primary decision was visited on a
    previous step, but in addition to the way back and at most one other
    transition leading to a previously-visited decision, there's a single
    traversable transition leading to an unvisited decision.
- 'revisitIntersection' is a step in which the primary decision was
    visited in a previous step, but in addition to the way back, there is
    at least one transition leading to an unvisited decision, and at
    least two total transitions (possibly including that one) leading
    elsewhere.
- 'other' is any step that doesn't fall into any of the categories
    above.
"""

@analyzer('step')
def primaryPreviouslyVisited(
    exploration: core.DiscreteExploration,
    step: int
) -> bool:
    """
    Returns True if the primary decision at the specified step had been
    visited by the step before that. Returns False in all other cases,
    including when there is no primary decision, there is no previous
    step, etc.
    """
    if step == 0:
        return False
    primary = exploration.primaryDecision(step)
    if primary is None:
        return False
    if exploration.hasBeenVisited(primary, step - 1):
        return True
    return False

@analyzer('step')
def stepAction(
    exploration: core.DiscreteExploration,
    step: int
) -> str:
    """
    Reports the name of the exploration action for the step.
    """
    action = exploration.getSituation(step).action
    if action is None:
        return 'N/A'
    else:
        return action[0];

@analyzer('step')
def stepClassification(
    exploration: core.DiscreteExploration,
    step: int
) -> StepClassification:
    """
    Computes the  `StepClassification` for the specified step.
    """
    situation = exploration.getSituation(step)
    graph = situation.graph
    pd = situation.state['primaryDecision']  # primary decision
    if step == 0:
        prevSituation = None
        prevGraph = None
        prevPrimary = None
    else:
        prevSituation = exploration.getSituation(step - 1)
        prevGraph = prevSituation.graph
        prevPrimary = prevSituation.state['primaryDecision']
        prevAction = prevSituation.action;
        if prevAction is not None and prevAction[0] == 'noAction':
            return 'wait'
        elif prevAction is not None and prevAction[0] == 'start':
            return 'setOut'
        else:
            prevMove = exploration.movementAtStep(step - 1)
            # If, in the previous step, we were at the same place and
            # took a transition that ended up leaving us there, then
            # that was an action. A previous classification should
            # account for the options available at this decision.
            if (
                prevMove is not None
            and prevMove[1] is not None  # transition was taken
            and prevMove[0] == prevMove[2]  # no movement
            and (prevMove[0] == pd or prevMove[0] == { pd })  # matches PD
            ):
                return 'takeAction'
            # Otherwise keep going with analysis of current situation

    # If there's no current primary decision, or if it's not visited
    # in the current step, we're in 'other' territory
    if (
        pd is None
     or pd not in graph
     or not exploration.hasBeenVisited(pd, step)
    ):
        return 'other'

    # Analyze outgoing transitions in terms 
    blockedCount = 0
    novelCount = 0
    retraceCount = 0
    canReturn = False
    for (name, destination) in graph.destinationsFrom(pd).items():
        # ignore transitions back to where we came from and actions
        if destination == prevPrimary:
            # Only counts as a return option if we can traverse it
            if exploration.isTraversable(pd, name, step):
                canReturn = True
            continue
        elif destination == pd:
            continue

        # Count each outgoing non-return as retrace, blocked, or novel
        if exploration.hasBeenVisited(destination, step):
            # Note we count as a return even if it's blocked
            retraceCount += 1
        elif not exploration.isTraversable(pd, name, step):
            blockedCount += 1
        else:
            novelCount += 1

    # Check if we're trapped
    if novelCount == 0 and retraceCount == 0 and not canReturn:
        # No way out
        return 'trapped'
    # First decision point: previous visited status
    elif primaryPreviouslyVisited(exploration, step):
        # We're revisiting a previously-visited decision
        # Options are retracePath, retraceIntersection, reachNewPath,
        # revisitIntersection, completeCycle, and completeCycleComplex
        if (
            step > 0
        and not primaryPreviouslyVisited(exploration, step - 1)
        and (step <= 1 or exploration.primaryDecision(step - 2) != pd)
        ):
            # Coming from a newly-explored decision in the previous
            # step, and not returning to where we'd just been
            if blockedCount == 0 and novelCount == 0:
                return 'completeCycle'
            else:
                return 'completeCycleComplex'
        else:
            # Coming from another previously-visited decision or from a
            # dead end, or first step of exploration
            if blockedCount == 0 and novelCount == 0 and retraceCount <= 1:
                # Nothing blocked or novel; zero or one return options
                return 'retracePath'
            elif blockedCount == 0 and novelCount == 0:
                # Nothing blocked or novel; > 1 return options
                return 'retraceIntersection'
            elif retraceCount <= 1 and blockedCount == 0 and novelCount == 1:
                # Maybe 1 way to continue explored stuff; exactly 1 new path
                # and no extra blocked ones
                return 'reachNewPath'
            elif (
                retraceCount + blockedCount + novelCount >= 2
            and novelCount >= 1
            ):
                # Multiple paths, including at least one novel path
                return 'revisitIntersection'
            else:
                # Didn't fall into any other category 
                return 'other'
    else:
        # Current decision was first visited on this step, so it's a new
        # discovery. Options for classification are setOut,
        # discoverDeadEnd, discoverDeadForNowEnd, discoverPath,
        # discoverBranchForLater, discoverIntersection,
        # discoverCycleReturn, and discoverComplexCycleReturn
        if retraceCount > 0:
            # Must be a discoverCycleReturn or discoverComplexCycleReturn
            if retraceCount == 1 and blockedCount == 0 and novelCount == 0:
                return 'discoverCycleReturn'
            else:
                return 'discoverComplexCycleReturn'
        else:
            # No retraces, so how many ways forward are there?
            if novelCount == 0:
                # Note: Would have returned 'trapped' above if not
                # canReturn here
                if blockedCount > 0:
                    return 'discoverDeadForNowEnd'
                else:
                    return 'discoverDeadEnd'
            elif novelCount == 1:
                if blockedCount > 0:
                    return 'discoverBranchForLater'
                else:
                    if canReturn:
                        return 'discoverPath'
                    else:
                        return 'setOut'
            else:
                # novelCount 2 or higher
                assert novelCount >= 2
                return 'discoverIntersection'

    # Fallback return if no other classification applies
    # This shouldn't be reachable...
    return 'other'


@analyzer('exploration')
def stepClassCounts(
    exploration: core.DiscreteExploration
) -> Dict[StepClassification, int]:
    """
    Collects step classifications from `stepClassification` and counts
    how many steps fall into each class, returning a dictionary.
    """
    counts = { category: 0 for category in get_args(StepClassification) }
    for step in range(len(exploration)):
        counts[stepClassification(exploration, step)] += 1
    return counts

NON_PROGRESS_CATEGORIES = ('wait', 'takeAction', 'other')
"""
`StepClassification` categories which don't represent exploration
progress directly. We compute some stats that ignore these.
"""


def registerStepCategoryFractionCombiner(category):
    """
    Registers an `OverallCombiner` which computes the fraction of steps
    that belong to the specified `StepClassification`.
    """
    catUpper = category[0].upper() + category[1:]
    registerFullCombined(
        'stepClassification',
        f'stepClass{catUpper}Fraction',
        cast(
            OverallCombiner[Optional[float]],
            makeFractionCombiner(
                lambda step, cat: cat == category
            )
        )
    )

def registerStepCategoryProgressOnlyFractionCombiner(category):
    """
    As with `registerStepCategoryFractionCombiner` but registers a
    combiner that ignores non-progress-category steps. Raises a
    `ValueError` if given a category that's one of the
    `NON_PROGRESS_CATEGORIES`.
    """
    if category in NON_PROGRESS_CATEGORIES:
        raise ValueError(
            f"Can't register progress-only fraction combiner for"
            f" category {category!r} which is a non-progress category."
        )

    catUpper = category[0].upper() + category[1:]
    registerFullCombined(
        'stepClassification',
        f'progressStepClass{catUpper}Fraction',
        cast(
            OverallCombiner[Optional[float]],
            makeFractionCombiner(
                lambda step, cat: cat == category,
                lambda step, cat: cat in NON_PROGRESS_CATEGORIES
            )
        )
    )

# Register combiners to count fraction of steps in each category
for category in get_args(StepClassification):
    registerStepCategoryFractionCombiner(category)


for category in get_args(StepClassification):
    if category not in NON_PROGRESS_CATEGORIES:
        registerStepCategoryProgressOnlyFractionCombiner(category)


#-----------------------#
# Morphology Categories #
#-----------------------#

DecisionMorphologyCategory: 'TypeAlias' = Literal[
    'island',
    'end',
    'path',
    'fork',
    'intersection',
    'unconfirmed'
]
"""
Each decision can be classified based on its branching pattern as one of:

1. An island: A decision that has no connections.
2. An end: Any decision that connects to only one other decision.
3. A path: A decision that connects to exactly two other decisions.
4. A fork: A decision that connects to exactly three other decisions,
    none of which connect to more than two other decisions (one of which
    is the fork in question).
5. An intersection: A decision that connects to four or more other
    decisions, OR a decision that connects to three other decisions at
    least one of which also connects to at least three decisions.
6. Unconfirmed decisions get their own morphology category, as their
    final morphology is not known.

This classification ignores requirements and edge directionality.
"""


@finalOnly
@analyzer('stepDecision')
def morphologyCategory(
    exploration: core.DiscreteExploration,
    step: int,
    decision: base.DecisionID
) -> Optional[DecisionMorphologyCategory]:
    """
    Returns the `DecisionMorphologyCategory` for the given decision at
    the given step. Returns `None` for decisions that don't exist at the
    specified step.
    """
    graph = exploration.getSituation(step).graph
    if decision not in graph:
        return None
    # Get connections graph discarding actions
    connections = graph.connections(lambda fr, tr, to, gr: fr != to)
    degree = connections.degree[decision]
    if not graph.isConfirmed(decision):
        return 'unconfirmed'
    elif degree == 0:
        return 'island'
    elif degree == 1:
        return 'end'
    elif degree == 2:
        return 'path'
    elif degree == 3:
        for nb in connections.neighbors(decision):
            if connections.degree[nb] >= 3:
                return 'intersection'
        return 'fork'
    else:
        assert degree >= 4
        return 'intersection'

# Register fraction combiners for each morphology category
def registerMorphFractionCombiner(morph: DecisionMorphologyCategory) -> None:
    """
    Registers a `StepCombiner` to compute the fraction of decisions at a
    step that belong to a particular morphology category.
    """
    combiner = registerStepCombined(
        'morphologyCategory',
        f'{morph}Fraction',
        cast(
            StepCombiner[Optional[float]],
            makeFractionCombiner(
                lambda dID, morphology: morphology == morph,
                lambda dID, morphology: morphology is None
            )
        )
    )
    # Mark it as final-only
    finalOnly(combiner)

# Register fraction combiners for each morphology category
for morph in get_args(DecisionMorphologyCategory):
    registerMorphFractionCombiner(morph)

#---------------#
# Full analysis #
#---------------#

def runFullAnalysis(
    exploration: core.DiscreteExploration, 
    elide: Collection[str] = ELIDE,
    finalOnly: Collection[str] = FINAL_ONLY
) -> FullAnalysisResults:
    """
    Runs every single analysis function on every valid target for that
    function in the given exploration, building up the cache of
    `FullAnalysisResults` in `ALL_ANALYZERS`. Returns the relevant
    `FullAnalysisResults` object.

    Skips analyzers in the provided `elide` collection, which by default
    is the `ELIDE` global set containing functions explicitly decorated
    with `elide`. Analyzers in the `FINAL_ONLY` set are only applied to
    the final decision graph in the exploration (although note that they
    might call other analyzers which recursively need to analyze prior
    steps). `finalOnly` only has an effect for analyzers with 'step',
    'stepDecision', or 'stepTransition' units.
    """
    for aName, analyzer in ALL_ANALYZERS.items():
        # Skip this one if we're told to
        if aName in elide:
            continue
        # Split out cases for each unit & apply as appropriate
        unit = analyzer._unit
        if unit == 'step':
            sa = cast(StepAnalyzer, analyzer)
            if aName in finalOnly:
                sa(exploration, len(exploration) - 1)
            else:
                for step in range(len(exploration)):
                    sa(exploration, step)
        elif unit == 'stepDecision':
            sda = cast(StepDecisionAnalyzer, analyzer)
            # Only apply to final graph if it's in finalOnly
            if aName in finalOnly:
                step = len(exploration) - 1
                for dID in exploration[step].graph:
                    sda(exploration, step, dID)
            else:
                for step in range(len(exploration)):
                    for dID in exploration[step].graph:
                        sda(exploration, step, dID)
        elif unit == 'stepTransition':
            sta = cast(StepTransitionAnalyzer, analyzer)
            if aName in finalOnly:
                step = len(exploration) - 1
                edges = exploration[step].graph.allEdges()
                for (src, dst, transition) in edges:
                    sta(exploration, step, src, transition, dst)
            else:
                for step in range(len(exploration)):
                    edges = exploration[step].graph.allEdges()
                    for (src, dst, transition) in edges:
                        sta(exploration, step, src, transition, dst)
        elif unit == 'decision':
            da = cast(DecisionAnalyzer, analyzer)
            for dID in exploration.allDecisions():
                da(exploration, dID)
        elif unit == 'transition':
            ta = cast(TransitionAnalyzer, analyzer)
            for (src, trans, dst) in exploration.allTransitions():
                ta(exploration, src, trans, dst)
        elif unit == 'finalTransition':
            fta = cast(FinalTransitionAnalyzer, analyzer)
            for (src, trans) in exploration.allFinalTransitions():
                fta(exploration, src, trans)
        elif unit == 'exploration':
            ea = cast(ExplorationAnalyzer, analyzer)
            ea(exploration)
        else:
            raise ValueError(f"Invalid analysis unit {unit!r}.")

    return ANALYSIS_RESULTS[id(exploration)]


#--------------------#
# Analysis accessors #
#--------------------#

# These functions access pre-computed analysis results. Call
# `runFullAnalysis` first to populate those.


def getDecisionAnalyses(
    exploration: core.DiscreteExploration,
    dID: base.DecisionID
) -> AnalysisResults:
    """
    Retrieves all pre-computed all-step analysis results for the
    specified decision. Use `runFullAnalysis` or call specific analysis
    functions of interest first to populate these results. Does not
    include per-step decision analyses.

    Returns the dictionary of `AnalysisResults`, which can be modified to
    update stored results if necessary (although it's better to write
    additional analysis routines using the `@analyzer` decorator).
    """
    cached = ANALYSIS_RESULTS.setdefault(
        id(exploration),
        newFullAnalysisResults()
    )
    return cached["perDecision"].setdefault(dID, {})


def getTransitionAnalyses(
    exploration: core.DiscreteExploration,
    source: base.DecisionID,
    transition: base.Transition,
    destination: base.DecisionID
) -> AnalysisResults:
    """
    Like `getDecisionAnalyses` but returns analyses for a transition
    instead of a decision.
    """
    cached = ANALYSIS_RESULTS.setdefault(
        id(exploration),
        newFullAnalysisResults()
    )
    return cached["perTransition"].setdefault(
        (source, transition, destination),
        {}
    )


def getStepDecisionAnalyses(
    exploration: core.DiscreteExploration,
    step: int,
    dID: base.DecisionID
) -> AnalysisResults:
    """
    Like `getDecisionAnalyses` but for analyses applicable only to the
    specified exploration step.
    """
    cached = ANALYSIS_RESULTS.setdefault(
        id(exploration),
        newFullAnalysisResults()
    )
    stepwise = cached.setdefault("perStepDecision", [])
    while step >= len(stepwise):
        stepwise.append({})
    return stepwise[step].setdefault(dID, {})


def getStepTransitionAnalyses(
    exploration: core.DiscreteExploration,
    step: int,
    source: base.DecisionID,
    transition: base.Transition,
    destination: base.DecisionID
) -> AnalysisResults:
    """
    Like `getStepDecisionAnalyses` but for a transition at a particular
    step, not a decision.
    """
    cached = ANALYSIS_RESULTS.setdefault(
        id(exploration),
        newFullAnalysisResults()
    )
    stepwise = cached.setdefault("perStepTransition", [])
    while step >= len(stepwise):
        stepwise.append({})
    return stepwise[step].setdefault((source, transition, destination), {})


def getStepAnalyses(
    exploration: core.DiscreteExploration,
    step: int
) -> AnalysisResults:
    """
    Like `getDecisionAnalyses` but retrieves full-step analysis results
    for the specified exploration step.
    """
    cached = ANALYSIS_RESULTS.setdefault(
        id(exploration),
        newFullAnalysisResults()
    )
    stepwise = cached.setdefault("perStep", [])
    while step >= len(stepwise):
        stepwise.append({})
    return stepwise[step]


def getExplorationAnalyses(
    exploration: core.DiscreteExploration
) -> AnalysisResults:
    """
    Like `getDecisionAnalyses` but retrieves full-exploration analysis
    results.
    """
    cached = ANALYSIS_RESULTS.setdefault(
        id(exploration),
        newFullAnalysisResults()
    )
    return cached.setdefault("overall", {})


class AnalyzersByUnit(TypedDict):
    """
    Holds lists of analyzers for each analysis unit type.
    """
    step: List[StepAnalyzer]
    stepDecision: List[StepDecisionAnalyzer]
    stepTransition: List[StepTransitionAnalyzer]
    decision: List[DecisionAnalyzer]
    transition: List[TransitionAnalyzer]
    finalTransition: List[FinalTransitionAnalyzer]
    exploration: List[ExplorationAnalyzer]


def analyzersByUnit(
    onlyInclude: Optional[Set[str]] = None
) -> AnalyzersByUnit:
    """
    Returns an `AnalyzersByUnit` dictionary containing all analyzers
    from `ALL_ANALYZERS` which are in the given `onlyInclude` set (or
    just all of them if no set is specified). This will by default be all
    analyzers registered so far.
    """
    byUnit: AnalyzersByUnit = {
        "step": [],
        "stepDecision": [],
        "stepTransition": [],
        "decision": [],
        "transition": [],
        "finalTransition": [],
        "exploration": []
    }
    for analyzerName in ALL_ANALYZERS:
        if onlyInclude is not None and analyzerName not in onlyInclude:
            continue
        analyzer = ALL_ANALYZERS[analyzerName]
        unit = analyzer._unit
        byUnit[unit].append(analyzer)  # type: ignore
        # Mypy will just have to trust that We've put the correct unit
        # values on each analyzer. That relationship is type-checked in
        # the `analyzer` definition.

    return byUnit