class Instruction(ABC):
    """A function in the Push language used to modify the PushState.

    The Instruction class is the abstract base class for specific implementations
    that are configured differently. For example, see SimpleInstruction verses
    TakesStateInstruction.

    Parameters
    ----------
    name : str,
        A unique name for the instruction.
    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.

    Attributes
    ----------
    name : str,
        A unique name for the instruction.
    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", "code_block", "docstring"]

    def __init__(self, name: str, code_blocks: int, docstring="Write me!"):
        self.name = name
        self.code_blocks = code_blocks
        self.docstring = docstring

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

        Parameters
        ----------
        push_state: pyshgp.push.state.PushState
            The PushState to run the instruction on.
        push_config: pyshgp.push.interpreter.PushConfig
            The configuration of the Push language.

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

        """
        pass

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

    def meta(self) -> InstructionMeta:
        """Create an ``InstructionMeta`` from the instruction object."""
        return InstructionMeta(name=self.name, code_blocks=self.code_blocks)

    def __eq__(self, other):
        if type(self) == type(other):
            return self.name == other.name
        return False

    def __hash__(self):
        return self.name.__hash__()

    def __repr__(self):
        return "Instruction<{n}>".format(n=self.name) class Program(Saveable, PRecord):
    """A Push program containing all information needed to run the code with consistent behavior.

    Attributes
    ----------
    code : CodeBlock
        The Push code expressing the logic of the program.
    signature : ProgramSignature
        The specification of the program and the configuration of the Push interpreter that it was evolved under.

    """

    code = field(type=CodeBlock, mandatory=True)
    signature = field(type=ProgramSignature, mandatory=True)

    def pretty_str(self) -> str:
        """Generate a simple string representation of the program's code."""
        return self.code.pretty_str() 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 InstructionSet(Dict[str, Instruction]):
    """A collection of Instruction objects stored by name.

    Attributes
    ----------
    type_library : PushTypeLibrary, optional
        The PushTypeLibrary which denote the PushTypes (and thus stacks)
        are supported. Default is None, which corresponds to the core set of types.
    register_core : bool, optional
        If True, all instructions in the core instruction set will be registered
        upon instantiation. Default is False.
    strip_docstrings : bool, optional
        If True, the docstring attribute of registered instructions will be
        removed to reduce memory footprint. Default is True.

    """

    def __init__(self,
                 type_library: PushTypeLibrary = None,
                 register_core: bool = False,
                 strip_docstrings: bool = True):
        super().__init__()
        self.strip_docstrings = strip_docstrings

        if type_library is None:
            type_library = PushTypeLibrary()
        self.type_library = type_library

        if register_core:
            self.register_core()

    def set_type_library(self, type_library: PushTypeLibrary):
        """Set the type library attribute and return self.

        Parameters
        ----------
        type_library
            PushTypeLibrary to set.

        Returns
        -------
        InstructionSet
            A reference to the InstructionSet.

        """
        self.type_library = type_library
        return self

    def register(self, instr: Instruction):
        """Register an Instruction object.

        Parameters
        ----------
        instr
            Instruction to register.

        Returns
        -------
        InstructionSet
            A reference to the InstructionSet.

        """
        if self.strip_docstrings and hasattr(instr, "docstring"):
            del instr.docstring
        if instr.required_stacks() <= self.type_library.supported_stacks():
            self[instr.name] = instr
        return self

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

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

        Returns
        -------
        InstructionSet
            A reference to the InstructionSet.

        """
        for i in instrs:
            self.register(i)
        return self

    def register_core_by_stack(self, include_stacks: Set[str], *, exclude_stacks: Set[str] = None):
        """Register all instructions that make use of the given type name.

        Parameters
        ----------
        include_stacks
            List of PushType names.

        exclude_stacks
            List of PushType names.

        Returns
        -------
        InstructionSet
            A reference to the InstructionSet.

        """
        for i in core_instructions(self.type_library):
            req_stacks = i.required_stacks()
            if req_stacks <= include_stacks:
                if exclude_stacks is None or len(req_stacks & exclude_stacks) == 0:
                    self.register(i)
        return self

    def register_core_by_name(self, name_pattern: str):
        """Register all instructions whose name match the given pattern.

        Parameters
        ----------
        name_pattern
            A regex string.

        Returns
        -------
        InstructionSet
            A reference to the InstructionSet.

        """
        re_pat = re.compile(name_pattern)
        for i in core_instructions(self.type_library):
            if re.match(re_pat, i.name) is not None:
                self.register(i)
        return self

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

        Returns
        -------
        InstructionSet
            A reference to the InstructionSet.

        """
        self.register_list(core_instructions(self.type_library))
        return self

    def unregister(self, instruction_name: str):
        """Unregister an instruction by name.

        Parameters
        ----------
        instruction_name
            The name of the instruction to unregister.

        Returns
        -------
        InstructionSet
            A reference to the InstructionSet.

        """
        self.pop(instruction_name, None)
        return self

    def required_stacks(self) -> Set[str]:
        """Return all stack names used throughout the registered instructions.

        Returns
        -------
        Set[str]
            The set of stack names that are used by the registered instructions.

        """
        all_types = set()
        for instr in self.values():
            all_types.update(instr.required_stacks())
        return all_types - RESERVED_PSEUDO_STACKS 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 Closer(Atom, PClass):
    """An Atom dedicated to denoting the close of a CodeBlock in a `Genomes` representation."""

    def pretty_str(self) -> str:
        """Generate a simple string representation of the Atom."""
        return "close" 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 InstructionMeta(Atom, PClass):
    """An identifier of a Push Instruction.

    The `InstructionMeta` is a placeholder atom. When a PushInterpreter evaluates
    an instruction ID, it searches for an instruction with the given
    name in its `InstructionSet`. If found, this instruction is evaluated by the `PushInterpreter`.

    Attributes
    ----------
    name: str
        The name of the Instruction being referenced.
    code_blocks: int
        The number of code blocks that are expected to follow the instruction.

    """

    name = field(type=str, mandatory=True)
    code_blocks = field(type=int, mandatory=True)

    def pretty_str(self) -> str:
        """Generate a simple string representation of the Instruction."""
        return self.name class CodeBlock(Atom, CheckedPVector):
    """An `Atom` which holds a sequence of other atoms in order to express a nested code block."""

    __type__ = Atom

    def size(self, depth: int = 1) -> int:
        """Return the size of the block and the size of all the nested blocks."""
        return sum([el.size(depth + 1) + 1 if isinstance(el, CodeBlock) else 1 for el in self])

    def depth(self) -> int:
        """Return the farthest depth of the CodeBlock."""
        i = iter(self)
        level = 0
        try:
            for level in count():
                i = chain([next(i)], i)
                i = chain.from_iterable(s for s in i if isinstance(s, Sequence) and not isinstance(s, str))
        except StopIteration:
            return level
        return 0

    def code_at_point(self, ndx: int) -> Optional[Atom]:
        """Return a nested element of the CodeBlock using depth first traversal."""
        if ndx == 0:
            return self
        i = ndx
        for el in self:
            i = i - 1
            if i == 0:
                return el
            if isinstance(el, CodeBlock):
                next_depth = el.code_at_point(i)
                if next_depth is not None:
                    return next_depth
                i = i - el.size()
        return None

    def with_code_inserted_at_point(self, code: Atom, index: int) -> CodeBlock:
        """Insert an element into the CodeBlock using depth first traversal."""
        if index > self.size():
            return self.append(code)
        _, new = self._attempt_code_insert(code, index)
        return new

    def _attempt_code_insert(self, code: Atom, index: int) -> Tuple[bool, CodeBlock]:
        i = index
        for idx, el in enumerate(self):
            if i == 0:
                new = CodeBlock(self[:idx] + [code] + self[idx:])
                return True, new
            if isinstance(el, CodeBlock):
                inserted, new = el._attempt_code_insert(code, i - 1)
                if inserted:
                    return True, self.set(idx, new)
                i = i - (el.size() + 1)
            i = i - 1
        if i == 0:
            return True, self.append(code)
        return False, self

    def pretty_str(self) -> str:
        """Generate a simple string representation of the CodeBlock."""
        return "(" + " ".join([el.pretty_str() for el in self]) + ")" class Input(Atom, PClass):
    """A reference to a positional argument of the `PushProgram` which the atom is part of.

    Attributes
    ----------
    input_index: int
        The position of the associated input to Push program.

    """

    input_index = field(type=int, mandatory=True)

    def pretty_str(self) -> str:
        """Generate a simple string representation of the Input."""
        return "input_" + str(self.input_index) class PushConfig(PRecord):
    """A configuration for a Push program.

    Attributes
    ----------
    step_limit : int
        Max number of atoms to process before terminating the execution of a
        given program. Default is 500
    runtime_limit : int
        Max number of seconds to run a push program before forcing
        termination. Default is 10.
    growth_cap : int
        Max number of elements that can be added to a PushState at any given
        step of program execution. If exceeded, program terminates. Default is 500.
    collection_size_cap : int, optional
        Max size of any collection (code blocks, vectors, strings, etc). Default is 1000.
    numeric_magnitude_limit : float, optional
        Max magnitude of numbers. Default is 1 million.

    """

    step_limit = field(type=int, initial=500, mandatory=True)
    runtime_limit = field(type=int, initial=10, mandatory=True)
    growth_cap = field(type=int, initial=500, mandatory=True)
    collection_size_cap = field(type=int, initial=1000, mandatory=True)
    numeric_magnitude_limit = field(type=float, initial=1e12, mandatory=True) def tap(fn):
    """Decorate a function/method to call any associated taps that have been registered in the ``TapManager``.

    Functional behavior is not changed.

    """
    fn_id = inspect.getmodule(fn).__name__ + "." + fn.__qualname__

    @wraps(fn)
    def tapped(*args, **kwargs):
        tap = TapManager.get(fn_id)
        if tap is not None:
            tap.pre(fn_id, args, kwargs)
        result = fn(*args, **kwargs)
        if tap is not None:
            tap.post(fn_id, args, kwargs, result)
        return result

    return tapped class PushError(Exception):
    """Error raised during Push program execution."""

    @classmethod
    def no_type(cls, thing):
        """Raise PushError when no PushType can be found for something."""
        return cls("Unkown PushType for {th}.".format(th=thing))

    @classmethod
    def failed_coerce(cls, thing, push_type):
        """Raise PushError when something fails to coerce to a PushType."""
        return cls("Could not convert {typ1} {th} to {typ2}.".format(
            th=thing,
            typ1=type(thing),
            typ2=push_type
        ))

    @classmethod
    def empty_character(cls):
        """Raise PushError when Character is made from empty string."""
        return cls("Char object cannot be created from empty string.")

    @classmethod
    def long_character(cls):
        """Raise PushError when Character is made from string length more than 1."""
        return cls("Char object cannot be created from string of length > 1.")
import traceback
import time
from typing import Union
from enum import Enum
from pyshgp.push.instruction import Instruction
from pyshgp.push.program import Program
from pyshgp.push.state import PushState
from pyshgp.push.instruction_set import InstructionSet
from pyshgp.push.atoms import Atom, Closer, Literal, InstructionMeta, CodeBlock, Input
from pyshgp.push.config import PushConfig
from pyshgp.tap import tap
from pyshgp.validation import PushError
"""The :mod:`interpreter` module defines the ``PushInterpreter`` used to run Push programs."""



class PushInterpreterStatus(Enum):
    """Enum class of all potential statuses of a PushInterpreter."""

    normal = 1
    step_limit_exceeded = 2
    runtime_limit_exceeded = 3
    growth_cap_exceeded = 4


class PushInterpreter:
    """An interpreter capable of running Push programs.

    Parameters
    ----------
    instruction_set : Union[InstructionSet, str], optional
        The ``InstructionSet`` to use for executing programs. Default is "core"
        which instantiates an ``InstructionSet`` using all the core instructions.

    Attributes
    ----------
    instruction_set : InstructionSet
        The ``InstructionSet`` to use for executing programs.
    state : PushState
        The current ``PushState``. Contains one stack for each ``PushType``
        mentioned by the instructions in the instruction set.
    status : PushInterpreterStatus
        A string denoting if the interpreter has encountered a situation
        where non-standard termination was required.

    """

    def __init__(self,
                 instruction_set: Union[InstructionSet, str] = "core",
                 reset_on_run: bool = True):
        self.reset_on_run = reset_on_run
        # If no instruction set given, create one and register all instructions.
        if instruction_set == "core":
            self.instruction_set = InstructionSet(register_core=True)
        else:
            self.instruction_set = instruction_set

        self.type_library = self.instruction_set.type_library

        # Initialize the PushState and status
        self.state: PushState = None
        self.status: PushInterpreterStatus = None
        self._validate()

    def _validate(self):
        library_type_names = set(self.type_library.keys())
        required_stacks = self.instruction_set.required_stacks() - {"stdout", "exec", "untyped"}
        if not required_stacks <= library_type_names:
            raise ValueError(
                "PushInterpreter instruction_set and type_library are incompatible. {iset} vs {tlib}. Diff: {d}".format(
                    iset=required_stacks,
                    tlib=library_type_names,
                    d=required_stacks - library_type_names,
                ))

    def _evaluate_instruction(self, instruction: Instruction, config: PushConfig):
        self.state = instruction.evaluate(self.state, config)

    def untyped_to_typed(self):
        """Infer ``PushType`` of items on state's untyped queue and push to corresponding stacks."""
        while len(self.state.untyped) > 0:
            el = self.state.untyped.popleft()
            push_type = self.type_library.push_type_of(el, error_on_not_found=True)
            self.state[push_type.name].push(el)

    @tap
    def evaluate_atom(self, atom: Atom, config: PushConfig):
        """Evaluate an ``Atom``.

        Parameters
        ----------
        atom : Atom
            The Atom (``Literal``, ``InstructionMeta``, ``Input``, or ``CodeBlock``) to
            evaluate against the current ``PushState``.
        config : PushConfig
            The configuration of the Push program being run.

        """
        try:
            if isinstance(atom, InstructionMeta):
                self._evaluate_instruction(self.instruction_set[atom.name], config)
            elif isinstance(atom, Input):
                input_value = self.state.inputs[atom.input_index]
                self.state.untyped.append(input_value)
            elif isinstance(atom, CodeBlock):
                for a in atom[::-1]:
                    self.state["exec"].push(a)
            elif isinstance(atom, Literal):
                self.state[atom.push_type.name].push(atom.value)
            elif isinstance(atom, Closer):
                raise PushError("Closers should not be in push programs. Only genomes.")
            else:

                raise PushError("Cannot evaluate {t}, require a subclass of Atom".format(t=type(atom)))