class PushType:
    """Type information for values used by Push programs.

    Attributes
    ----------
    name : str
        A name for the type. Used when referencing the PushType in Instruction
        definitions and will be the key in the PushState for the corresponding
        PushStack.
    is_collection : bool, optional
        Indicates if that the PushType is a collection. Default is False.
    is_numeric : bool, optional
        Indicates if that the PushType is a numeric type. Default is False.

    """

    def __init__(self,
                 name: str,
                 python_types: Tuple[type, ...],
                 is_collection: bool = False,
                 is_numeric: bool = False):
        self.name = name
        self.python_types = python_types
        self.is_collection = is_collection
        self.is_numeric = is_numeric

    def is_instance(self, value) -> bool:
        return isinstance(value, self.python_types)

    def coerce(self, value):
        return self.python_types[0](value)

    def __eq__(self, other):
        return isinstance(other, self.__class__) and self.name == other.name

    def __hash__(self):
        return (str(self.__class__) + self.name).__hash__() class PushTypeLibrary(dict):
    """A collection of PushTypes which can support a corresponding PushStack.

    Parameters
    ----------
    register_core : bool, optional
        If True, all core types will be registered. Default is True.
    *args
        A collection of PushTypes to register.

    Attributes
    ----------
    register_core : bool, optional
        If True, all core types will be registered. Default is True.
    *args
        A collection of PushTypes to register.

    """

    def __init__(self, register_core: bool = True, *args):
        super().__init__()
        if register_core:
            self.register_core()
        self.register_list(args)
        self.create_and_register("code", (Atom,), force=True)
        self.create_and_register("exec", (Atom,), force=True)

    def register(self, push_type: PushType, _force=False):
        """Register a PushType object.

        Parameters
        ----------
        push_type
            PushType to register.
        _force : bool, optional
            For internal use only. Default is False.

        Returns
        -------
        PushTypeLibrary
            A reference to the ``PushTypeLibrary``.

        """
        name = push_type.name
        if (not _force) and (name in RESERVED_PSEUDO_STACKS):
            raise ValueError("Cannot register PushType with name {nm} because it is reserved.".format(nm=name))
        self[name] = push_type
        return self

    def create_and_register(self,
                            name: str,
                            python_types: Tuple[type, ...],
                            is_collection: bool = False,
                            is_numeric: bool = False,
                            force=False):
        """Create a PushType and register it into the library.

        Parameters
        ----------
        name : str
            A name for the type. Used when referencing the PushType in Instruction
            definitions and will be the key in the PushState for the corresponding
            PushStack.
        python_types : Tuple[type]
            A tuple of python types that correspond to the underlying
            native types which the PushType is representing.
        is_collection : bool, optional
            Indicates if the PushType is a collection. Default is False.
        is_numeric : bool, optional
            Indicates if the PushType is a number. Default is False.
        force : bool
            If True, will register the type even if it will overwrite an
            existing reserved stack typed (eg. exec, stdout, untyped). Default
            is False. It is not recommended this argument be changed unless
            you have a very good reason to do so.

        Returns
        -------
        PushTypeLibrary
            A reference to the PushTypeLibrary.

        """
        p_type = PushType(name, python_types, is_collection=is_collection, is_numeric=is_numeric)
        self.register(p_type, force)
        return self

    def unregister(self, push_type_name: str):
        """Unregister a push type by name.

        Parameters
        ----------
        push_type_name
            The name of the push type to unregister.

        Returns
        -------
        PushTypeLibrary
            A reference to the PushTypeLibrary.

        """
        if push_type_name in RESERVED_PSEUDO_STACKS:
            raise ValueError("Cannot unregister PushType with name {nm} because it is reserved.".format(nm=push_type_name))
        self.pop(push_type_name, None)
        return self

    def register_list(self, list_of_push_types: Sequence[PushType]):
        """Register a list of PushType objects.

        Parameters
        ----------
        list_of_push_types
            List of Instruction objects to register.

        Returns
        -------
        PushTypeLibrary
            A reference to the PushTypeLibrary.

        """
        for push_type in list_of_push_types:
            self.register(push_type)
        return self

    def register_core(self):
        """Register all core PushTypes defined in pyshgp.

        Returns
        -------
        PushTypeLibrary
            A reference to the PushTypeLibrary.

        """
        for push_type in CORE_PUSH_TYPES:
            self.register(push_type)

    def supported_stacks(self) -> Set[str]:
        """All stack names which the PushTypeLibrary can support.

        Returns
        -------
        set[str]
            A set of stacks names which the type library can support.

        """
        return set(self.keys())

    def push_type_of(self, thing: Any, error_on_not_found: bool = False) -> Optional[PushType]:
        """Return the PushType of the given thing.

        Parameters
        ----------
        thing : Any
            Any value to try and find the corresponding PushType.
        error_on_not_found : bool, optional
            If True, will raise error if no PushType found. Default is False.

        Returns
        -------
        Optional[PushType]
            The corresponding PushType of the thing. If no corresponding type, returns None.

        """
        for push_type in self.values():
            if push_type.is_instance(thing):
                return push_type
        if error_on_not_found:
            raise PushError.no_type(thing)
        return None

    def push_type_for_type(self, typ: type, error_on_not_found: bool = False) -> Optional[PushType]:
        """Return the PushType of the given python (or numpy) type.

        Parameters
        ----------
        typ : type
            Any type to try and find the corresponding PushType.
        error_on_not_found : bool, optional
            If True, will raise error if no PushType found. Default is False.

        Returns
        -------
        Optional[PushType]
            The corresponding PushType of the given type. If no corresponding type, returns None.

        """
        for push_type in self.values():
            if typ in push_type.python_types:
                return push_type
        if error_on_not_found:
            raise PushError.no_type(typ)
        return None class SimpleInstruction(Instruction):
    """A simple instruction implementation.

    A SimpleInstruction uses a standardized way of manipulating PushStates. In
    other words, it handles popping its own function arguments and pushing the
    function return values.

    The first step of evaluating a SimpleInstruction is to pop the arguments
    from the stacks corresponding the instruction's ``input_stacks`` list.
    If multiple occurrences of the same type are in ``input_stacks``, items are
    taken from progressively deeper in that stack. If the stacks of the
    PushState do not contain a sufficient number of items, the instruction does
    not modify the PushState.

    The popped arguments are then passed to the instruction's function to produce
    a tuple of outputs. It is crucial that the instruction's function produce a
    tuple of outputs, even if it only contains a single element. The elements of
    the tuple are then routed to the corresponding stacks specified in the
    instruction's ``output_stacks``.

    Parameters
    ----------
    name : str,
        A unique name for the instruction.
    f : Callable
        A function whose signature matches input_stacks and output_stacks.
    input_stacks : Sequence[str]
        A list of PushType names to use when popping arguments from the PushState.
    output_stacks : Sequence[str]
        A list of PushType names to use when pushing function results to the PushState.
    code_blocks : int
        The number of CodeBlocks to open following the instruction in a Genome.
    docstring : str, optional
        A string describing in the behavior of the Instruction.

    """

    __slots__ = ["name", "f", "input_stacks", "output_stacks", "code_blocks", "docstring"]

    def __init__(self,
                 name: str,
                 f: Callable,
                 input_stacks: Sequence[str],
                 output_stacks: Sequence[str],
                 code_blocks: int,
                 docstring="Write me!"):
        super().__init__(name, code_blocks, docstring)
        self.f = f
        self.input_stacks = input_stacks
        self.output_stacks = output_stacks

    def evaluate(self, push_state: PushState, push_config: PushConfig = None) -> PushState:
        """Evaluate the instruction on the given PushState. Return mutated State.

        A SimpleInstruction infers which values to pop and push from the stack
        based on its `input_stacks` and `output_stacks`.

        Parameters
        ----------
        push_state : PushState
            Push state to modify with the Instruction.
        push_config :  pyshgp.push.interpreter.PushConfig
            Configuration of the interpreter. Used to get various limits.

        Returns
        -------
        PushState
            Return the given state, possibly modified by the Instruction.

        """
        # Pull args, if present.
        args = push_state.observe_stacks(self.input_stacks)
        if Token.no_stack_item in args:
            return push_state

        # Compute result, return if revert or response too big.
        result = self.f(*args)
        if result is Token.revert:
            return push_state
        _check_is_seq(result, self)

        # Remove arguments, push results.
        push_state.pop_from_stacks(self.input_stacks)
        push_state.push_to_stacks(result, self.output_stacks)
        return push_state

    def required_stacks(self) -> Set[str]:
        """Return a list of PushType names relevant to the instruction.

        Based on the the instructions input and output types.
        """
        return set(self.input_stacks + self.output_stacks) - RESERVED_PSEUDO_STACKS class TakesStateInstruction(Instruction):
    """Instruction that takes entire PushState and returns particular values.

    The function of a TakesStateInstruction accepts an entire PushState as input
    and produces either a ``Token.revert`` or a tuple of outputs values. It is
    crucial that the instruction's function produce a tuple of outputs, even if
    it only contains a single element.

    The elements of the tuple are then routed to the corresponding stacks
    specified in the instruction's ``output_stacks``.

    Additional PushTypes utilized by the instruction are denoted in ``other_stacks``.

    Parameters
    ----------
    name : str,
        A unique name for the instruction.
    f : Callable
        A function that takes a PushState as input and produces values corresponding to ``output_stacks.``
    output_stacks : Sequence[str]
        A list of PushType names to use when pushing function results to the PushState.
    other_stacks : Sequence[str]
        A list of additional PushType names used by the Instruction's function.
    code_blocks : int
        The number of CodeBlocks to open following the instruction in a Genome.
    docstring : str, optional
        A string describing in the behavior of the Instruction.

    """

    __slots__ = ["name", "f", "output_stacks", "other_stacks", "code_blocks", "docstring"]

    def __init__(self,
                 name: str,
                 f: Callable,
                 output_stacks: Sequence[str],
                 other_stacks: Sequence[str],
                 code_blocks: int,
                 docstring="Write me!"):
        super().__init__(name, code_blocks, docstring)
        self.f = f
        self.output_stacks = output_stacks
        self.other_stacks = other_stacks

    def evaluate(self, push_state: PushState, push_config: PushConfig = None) -> PushState:
        """Evaluate the instruction on the given PushState. Return mutated State.

        A SimpleInstruction infers which values to pop and push from the stack
        based on its `input_stacks` and `output_stacks`.

        Parameters
        ----------
        push_state : PushState
            Push state to modify with the Instruction.
        push_config : PushConfig
            Configuration of the interpreter. Used to get various limits.

        Returns
        -------
        PushState
            Return the given state, possibly modified by the Instruction.

        """
        # Compute result. State should be modified in place during function.
        result = self.f(push_state)

        # Return if revert.
        if result is Token.revert:
            return push_state
        _check_is_seq(result, self)

        # Push results.
        push_state.push_to_stacks(result, self.output_stacks)
        return push_state

    def required_stacks(self) -> Set[str]:
        """Return a list of PushType names relevant to the instruction."""
        return set(self.other_stacks + self.output_stacks) - RESERVED_PSEUDO_STACKS class StateToStateInstruction(Instruction):
    """Instruction that takes entire PushState and returns entire PushState."""

    __slots__ = ["name", "f", "stacks_used", "code_blocks", "docstring"]

    def __init__(self,
                 name: str,
                 f: Callable,
                 stacks_used: Sequence[str],
                 code_blocks: int,
                 docstring="Write me!"):
        super().__init__(name, code_blocks, docstring)
        self.f = f
        self.stacks_used = set(stacks_used)

    def evaluate(self, push_state: PushState, push_config: PushConfig = None) -> PushState:
        """Evaluate the instruction on the given PushState. Return mutated State.

        A SimpleInstruction infers which values to pop and push from the stack
        based on its `input_stacks` and `output_stacks`.

        Parameters
        ----------
        push_state : PushState
            Push state to modify with the Instruction.
        push_config : PushConfig
            Configuration of the interpreter. Used to get various limits.

        Returns
        -------
        PushState
            Return the given state, possibly modified by the Instruction.

        """
        result = self.f(push_state)
        if result == Token.revert:
            return push_state
        else:
            return result

    def required_stacks(self) -> Set[str]:
        """Return a list of PushType names relevant to the instruction."""
        return self.stacks_used - RESERVED_PSEUDO_STACKS class ProducesManyOfTypeInstruction(Instruction):
    """Instruction that produces arbitrarily many values of a given PushType.

    ProducesManyOfTypeInstructions pop their arguments in the same was as
    SimpleInstructions. Items are popped from the stacks corresponding the
    types denoted in the ``input_stacks`` list. If multiple occurrences of the
    same type are in ``input_stacks``, items are taken from progressively deeper
    in that stack. If the stacks of the PushState do not contain a sufficient
    number of items, the instruction does not modify the PushState.

    The popped arguments are then passed to the instruction's function to produce
    a tuple of outputs. It is crucial that the instruction's function produce a
    tuple of outputs, even if it only contains a single element. All elements of
    the tuple are pushed individually to the stack denoted in ``output_stack``.

    Parameters
    ----------
    name : str,
        A unique name for the instruction.
    f : Callable
        A function whose signature matches input_stacks and output_stacks.
    input_stacks : Sequence[str]
        A list of PushType names to use when popping arguments from the PushState.
    output_stack : str
        The name of a PushType to use when pushing function results to the PushState.
        All values returned by the function go to the stack for this type.
    code_blocks : int
        The number of CodeBlocks to open following the instruction in a Genome.
    docstring : str, optional
        A string describing in the behavior of the Instruction.

    """

    __slots__ = ["name", "f", "input_stacks", "output_stack", "code_blocks", "docstring"]

    def __init__(self,
                 name: str,
                 f: Callable,
                 input_stacks: Sequence[str],
                 output_stack: str,
                 code_blocks: int,
                 docstring="Write me!"):
        super().__init__(name, code_blocks, docstring)
        self.f = f
        self.input_stacks = input_stacks
        self.output_stack = output_stack

    def evaluate(self, push_state: PushState, push_config: PushConfig = None) -> PushState:
        """Evaluate the instruction on the given PushState. Return mutated State.

        A ProducesManyOfTypeInstruction infers which values to pop from the stack
        based on `input_stacks` and pushes each output to the same stack
        based on `output_stack`.

        Parameters
        ----------
        push_state : PushState
            Push state to modify with the Instruction.
        push_config : PushConfig
            Configuration of the interpreter. Used to get various limits.

        Returns
        -------
        PushState
            Return the given state, possibly modified by the Instruction.

        """
        # Pull args, if present.
        args = push_state.observe_stacks(self.input_stacks)
        if Token.no_stack_item in args:
            return push_state

        # Compute result, return if revert or response too big.
        result = self.f(*args)
        if result is Token.revert:
            return push_state
        _check_is_seq(result, self)

        # Remove arguments, push results.
        push_state.pop_from_stacks(self.input_stacks)
        push_state.push_to_stacks(result, [self.output_stack] * len(result))
        return push_state

    def required_stacks(self) -> Set[str]:
        """Return a list of PushType names relevant to the instruction.

        Based on the the instructions input types and output type.
        """
        return set(self.input_stacks + [self.output_stack]) - RESERVED_PSEUDO_STACKS class PushState(dict):
    """A collection of PushStacks used during push program execution."""

    __slots__ = ["stdout", "inputs", "untyped", "type_library", "push_config"]

    def __init__(self, type_library: PushTypeLibrary, push_config: PushConfig):
        super().__init__()
        self.stdout = ""
        self.inputs = []
        self.untyped = deque([])
        self.type_library = type_library
        self.push_config = push_config

        for name, push_type in type_library.items():
            self[name] = PushStack(push_type, push_config)

    def __eq__(self, other) -> bool:
        if not isinstance(other, PushState):
            return False
        return super().__eq__(other) and self.inputs == other.inputs and self.stdout == other.stdout

    @classmethod
    def from_dict(cls, d, type_library: PushTypeLibrary, push_config: PushConfig):
        """Set the state to match the given dictionary.

        .. warning::
            This is written to be used in ``pyshgp`` tests, NOT as part of
            push program execution or evolution. There are no checks to confirm
            that the ``d`` can be converted to a valid Push state.

        Parameters
        ----------
        d : dict
            Dict that is converted into a Push state.
        type_library : PushTypeLibrary
            A Push type library.
        push_config : PushConfig
            The configuration of the current program being executed.

        """
        state = cls(type_library, push_config)
        inputs = []
        stdout = ""
        for k, v in d.items():
            if k == 'inputs':
                inputs = v
            elif k == 'stdout':
                stdout += v
            elif k == "untyped":
                for el in v:
                    state.untyped.append(el)
            else:
                for el in v:
                    state[k].push(el)
        state.load_inputs(inputs)
        state.stdout = stdout
        return state

    def load_code(self, program: CodeBlock):
        """Push the given CodeBlock to the execution stack."""
        self["exec"].push(program)

    def load_inputs(self, inputs):
        """Load a list of input values onto the PushState inputs.

        Parameters
        ----------
        inputs : list
            List of input values.

        """
        if not isinstance(inputs, (list, np.ndarray)):
            raise ValueError(
                "Push inputs must be a list, got {t}".format(t=type(inputs)))
        self.inputs = inputs

    def observe_stacks(self, types: Sequence[str]) -> list:
        """Return a list of output values based on the given types indicated.

        Items are take from the tops of each stack. If multiple occurrences of
        the same type are in ``output_types``, the returned values are taken
        from progressively deeper in that stack. Does not pop the values off
        the stacks.

        Parameters
        ----------
        types : list
            List of strings denoting the push types of the returned values.

        """
        values = []
        counts = {}
        for typ in types:
            if typ == "stdout":
                values.append(self.stdout)
            else:
                ndx = counts.get(typ, 0)
                values.append(self[typ].nth(ndx))
                counts[typ] = ndx + 1
        return values

    def pop_from_stacks(self, types: Sequence[str]) -> Union[Sequence, Token]:
        """Pop the top items for each value_type. Return a vector of the values popped from each stack."""
        values = []
        for typ in types:
            val = self[typ].top()
            if val is Token.no_stack_item:
                return Token.revert
            else:
                values.append(val)
                self[typ].pop()
        return values

    def push_to_stacks(self, values: list, types: Sequence[str]):
        """Check that all values can be coerced into their expected PushType. Push them onto the correct stack."""
        for ndx in range(len(values)):
            val = values[ndx]
            typ = types[ndx]
            if typ == "stdout":
                self.stdout += str(val)
            elif typ == "untyped":
                self.untyped.append(val)
            else:
                self[typ].push(val)

    def size(self):
        """Return the size of the PushState."""
        return sum([len(s) for s in self.values()]) + len(self.inputs)

    def pretty_print(self):
        """Print the state of all stacks in the PushState."""
        for k, v in self.items():
            print(" ".join([k, ":", str(v)]))
        print("untyped : " + str(self.untyped))
        print("inputs : " + str(self.inputs))
        print("stdout : " + str(self.stdout)) class Atom:
    """Base class of all Atoms. The fundamental element of Push programs."""

    @abstractmethod
    def pretty_str(self) -> str:
        """Generate a simple string representation of the Atom."""
        raise NotImplementedError() class Literal(Atom, PClass):
    """An Atom which holds a constant value.

    Attributes
    ----------
    value : Any
        The value to be stored in Literal.
    push_type : PushType, optional
        The `PushType` of the `Literal`. Usually, the PushType's underlying native
        type is the same as the type of the Literal's value. The PushType is
        used to determine how to route the Literal onto the correct PushStack
        of the PushState during program execution.

    """

    __invariant__ = lambda l: (l.push_type.is_instance(l.value), "Value is not of PushType.")
    value = field(mandatory=True)
    push_type = field(type=PushType, mandatory=True)

    def pretty_str(self) -> str:
        """Generate a simple string representation of the Literal."""
        # @todo make smarter by using a method on the PushType.
        s = str(self.value)
        if isinstance(self.value, str):
            s = "\"" + s + "\""
        return s class Token(Enum):
    """Enum class of all Tokens."""

    no_stack_item = 1
    revert = 2
    whole_state = 3
from typing import Any, Tuple
from functools import partial
from pyshgp.push.types import PushType
from pyshgp.push.type_library import PushTypeLibrary
from pyshgp.push.instruction import (
    SimpleInstruction,
    TakesStateInstruction,
    StateToStateInstruction,
    ProducesManyOfTypeInstruction
)
from pyshgp.push.state import PushState
from pyshgp.push.atoms import Atom, Literal
from pyshgp.utils import Token
    if type_name == "int" and len(state[type_name]) < 2:
        return Token.revert
    raw_ndx = state["int"].pop()
    ndx = max(0, min(raw_ndx, len(state[type_name]) - 1))
    item = state[type_name].nth(ndx)
    state[type_name].push(item)
    return state


def _shove(state: PushState, type_name: str):
    if state["int"].is_empty() or state[type_name].is_empty():
        return Token.revert
    if type_name == "int" and len(state[type_name]) < 2:
        return Token.revert
    raw_ndx = state["int"].pop()
    ndx = max(0, min(raw_ndx, len(state[type_name]) - 1))
    item = state[type_name].pop()
    state[type_name].insert(ndx, item)
    return state


def _shove_dup(state: PushState, type_name: str):
    if state["int"].is_empty() or state[type_name].is_empty():
        return Token.revert
    if type_name == "int" and len(state[type_name]) < 2:
        return Token.revert
    raw_ndx = state["int"].pop()
    ndx = max(0, min(raw_ndx, len(state[type_name])))
    item = state[type_name].top()
    state[type_name].insert(ndx, item)
    return state


def _is_empty(state: PushState, type_name: str):
    return state[type_name].is_empty(),


def _make_code(x: Any, push_type: PushType) -> Tuple[Atom]:
    if isinstance(x, Atom):
        return x,
    else:
        return Literal(value=x, push_type=push_type),


def instructions(type_library: PushTypeLibrary):
    """Return all core numeric instructions."""
    i = []

    for push_type in type_library.keys():
        i.append(SimpleInstruction(
            "{t}_pop".format(t=push_type),
            _noop,
            input_stacks=[push_type],
            output_stacks=[],
            code_blocks=(1 if push_type == "exec" else 0),
            docstring="Pops the top {t}.".format(t=push_type)
        ))

        i.append(SimpleInstruction(
            "{t}_dup".format(t=push_type),
            _dup,
            input_stacks=[push_type],
            output_stacks=[push_type, push_type],
            code_blocks=(1 if push_type == "exec" else 0),
            docstring="Duplicates the top {t}.".format(t=push_type)
        ))

        i.append(ProducesManyOfTypeInstruction(
            "{t}_dup_times".format(t=push_type),
            _dup_times,
            input_stacks=["int", push_type],
            output_stack=push_type,
            code_blocks=(1 if push_type == "exec" else 0),
            docstring="Duplicates the top {t} `n` times where `n` is from the int stack.".format(t=push_type)
        ))

        # Disabled due to performance issues.
        # i.append(StateToStateInstruction(
        #     "{t}_dup_top_n".format(t=push_type),
        #     _dup_top_n_factory(push_type),
        #     stacks_used=[push_type, "int"],
        #     code_blocks=0,
        #     docstring="Duplicates the top n items on the {t} stack.".format(t=push_type)
        # ))

        i.append(SimpleInstruction(
            "{t}_swap".format(t=push_type),
            _swap,
            input_stacks=[push_type, push_type],
            output_stacks=[push_type, push_type],
            code_blocks=(2 if push_type == "exec" else 0),
            docstring="Swaps the top two {t}s.".format(t=push_type)
        ))

        i.append(SimpleInstruction(
            "{t}_rot".format(t=push_type),
            _rot,
            input_stacks=[push_type] * 3,
            output_stacks=[push_type] * 3,
            code_blocks=(3 if push_type == "exec" else 0),
            docstring="Rotates the top three {t}s.".format(t=push_type)
        ))

        i.append(StateToStateInstruction(
            "{t}_flush".format(t=push_type),
            partial(_flush, type_name=push_type),
            stacks_used=[push_type],
            code_blocks=0,
            docstring="Empties the {t} stack.".format(t=push_type)
        ))

        i.append(SimpleInstruction(
            "{t}_eq".format(t=push_type),
            _eq,
            input_stacks=[push_type, push_type],
            output_stacks=["bool"],
            code_blocks=0,
            docstring="Pushes True if the top two {t} are equal. Otherwise pushes False.".format(t=push_type)
        ))


        i.append(TakesStateInstruction(