from rpython.jit.metainterp.walkvirtual import VirtualVisitor
from rpython.jit.metainterp.history import ConstInt, ConstPtr, ConstFloat
from rpython.jit.metainterp.optimizeopt.info import ArrayPtrInfo,\
     ArrayStructInfo, AbstractStructPtrInfo
from rpython.jit.metainterp.optimizeopt.intutils import \
     MININT, MAXINT, IntBound, IntLowerBound
from rpython.jit.metainterp.resoperation import rop, ResOperation, \
     InputArgInt, InputArgRef, InputArgFloat
from rpython.rlib.debug import debug_print

LEVEL_UNKNOWN = '\x00'
LEVEL_NONNULL = '\x01'
LEVEL_KNOWNCLASS = '\x02'
LEVEL_CONSTANT = '\x03'

class VirtualStatesCantMatch(Exception):
    def __init__(self, msg='?', state=None):
        self.msg = msg
        self.state = state


class GenerateGuardState(object):
    def __init__(self, optimizer=None, guards=None, renum=None, bad=None, force_boxes=False):
        self.optimizer = optimizer
        self.cpu = optimizer.cpu
        if guards is None:
            guards = []
        self.extra_guards = guards
        if renum is None:
            renum = {}
        self.renum = renum
        if bad is None:
            bad = {}
        self.bad = bad
        self.force_boxes = force_boxes

    def get_runtime_item(self, box, descr, i):
        array = box.getref_base()
        if descr.is_array_of_pointers():
            return InputArgRef(self.cpu.bh_getarrayitem_gc_r(array, i, descr))
        elif descr.is_array_of_floats():
            return InputArgFloat(self.cpu.bh_getarrayitem_gc_f(array, i, descr))
        else:
            return InputArgInt(self.cpu.bh_getarrayitem_gc_i(array, i, descr))

    def get_runtime_field(self, box, descr):
        struct = box.getref_base()
        if descr.is_pointer_field():
            return InputArgRef(self.cpu.bh_getfield_gc_r(struct, descr))
        elif descr.is_float_field():
            return InputArgFloat(self.cpu.bh_getfield_gc_f(struct, descr))
        else:
            return InputArgInt(self.cpu.bh_getfield_gc_i(struct, descr))

    def get_runtime_interiorfield(self, box, descr, i):
        struct = box.getref_base()
        if descr.is_pointer_field():
            return InputArgRef(self.cpu.bh_getinteriorfield_gc_r(struct, i,
                                                                 descr))
        elif descr.is_float_field():
            return InputArgFloat(self.cpu.bh_getinteriorfield_gc_f(struct, i,
                                                                   descr))
        else:
            return InputArgInt(self.cpu.bh_getinteriorfield_gc_i(struct, i,
                                                                 descr))

class AbstractVirtualStateInfo(object):
    position = -1

    def generate_guards(self, other, op, runtime_op, state):
        """ generate guards (output in the list extra_guards) that make runtime
        values of the shape other match the shape of self. if that's not
        possible, VirtualStatesCantMatch is thrown and bad gets keys set which
        parts of the state are the problem.

        the function can peek into the information about the op, as well
        as runtime value (passed in runtime_op)
        as a guiding heuristic whether making such guards makes
        sense. if None is passed in for op, no guard is ever generated, and
        this function degenerates to a generalization check."""
        assert self.position != -1
        if self.position in state.renum:
            if state.renum[self.position] != other.position:
                state.bad[self] = state.bad[other] = None
                raise VirtualStatesCantMatch(
                        'The numbering of the virtual states does not ' +
                        'match. This means that two virtual fields ' +
                        'have been set to the same Box in one of the ' +
                        'virtual states but not in the other.',
                        state)
        else:
            state.renum[self.position] = other.position
            try:
                self._generate_guards(other, op, runtime_op, state)
            except VirtualStatesCantMatch as e:
                state.bad[self] = state.bad[other] = None
                if e.state is None:
                    e.state = state
                raise e

    def _generate_guards(self, other, box, runtime_box, state):
        raise VirtualStatesCantMatch(
                'Generating guards for making the VirtualStates ' +
                'at hand match have not been implemented')

    def enum_forced_boxes(self, boxes, box, optimizer, force_boxes=False):
        raise NotImplementedError

    def enum(self, virtual_state):
        if self.position != -1:
            return
        virtual_state.info_counter += 1
        self.position = virtual_state.info_counter
        self._enum(virtual_state)

    def _enum(self, virtual_state):
        raise NotImplementedError

    def debug_print(self, indent, seen, bad, metainterp_sd):
        mark = ''
        if self in bad:
            mark = '*'
        self.debug_header(indent + mark)
        if self not in seen:
            seen[self] = True
            for s in self.fieldstate:
                s.debug_print(indent + "    ", seen, bad, metainterp_sd)
        else:
            debug_print(indent + "    ...")

    def debug_header(self, indent):
        raise NotImplementedError


class AbstractVirtualStructStateInfo(AbstractVirtualStateInfo):
    def __init__(self, fielddescrs):
        self.fielddescrs = fielddescrs

    def _generate_guards(self, other, box, runtime_box, state):
        if not self._generalization_of_structpart(other):
            raise VirtualStatesCantMatch("different kinds of structs")

        assert isinstance(other, AbstractVirtualStructStateInfo)
        assert len(self.fielddescrs) == len(self.fieldstate)
        assert len(other.fielddescrs) == len(other.fieldstate)
        if runtime_box is not None:
            opinfo = state.optimizer.getptrinfo(box)
            assert opinfo.is_virtual()
            assert isinstance(opinfo, AbstractStructPtrInfo)
        else:
            opinfo = None

        if len(self.fielddescrs) != len(other.fielddescrs):
            raise VirtualStatesCantMatch("field descrs don't match")

        for i in range(len(self.fielddescrs)):
            if other.fielddescrs[i] is not self.fielddescrs[i]:
                raise VirtualStatesCantMatch("field descrs don't match")
            if runtime_box is not None and opinfo is not None:
                fieldbox = opinfo._fields[self.fielddescrs[i].get_index()]
                if fieldbox is not None:
                    fieldbox_runtime = state.get_runtime_field(runtime_box,
                                                           self.fielddescrs[i])
                else:
                    fieldbox_runtime = None
            else:
                fieldbox = None
                fieldbox_runtime = None
            if self.fieldstate[i] is not None:
                if other.fieldstate[i] is None:
                    raise VirtualStatesCantMatch
                self.fieldstate[i].generate_guards(other.fieldstate[i],
                                                   fieldbox,
                                                   fieldbox_runtime, state)


    def _generalization_of_structpart(self, other):
        raise NotImplementedError

    def enum_forced_boxes(self, boxes, box, optimizer, force_boxes=False):
        box = optimizer.get_box_replacement(box)
        info = optimizer.getptrinfo(box)
        if info is None or not info.is_virtual():
            raise VirtualStatesCantMatch()
        else:
            assert isinstance(info, AbstractStructPtrInfo)

        # The min operation ensures we don't wander off either array, as not all
        # to make_inputargs have validated their inputs with generate_guards.
        for i in range(min(len(self.fielddescrs), len(info._fields))):
            state = self.fieldstate[i]
            if not state:
                continue
            if state.position > self.position:
                fieldbox = info._fields[i]
                state.enum_forced_boxes(boxes, fieldbox, optimizer, force_boxes)

    def _enum(self, virtual_state):
        for s in self.fieldstate:
            if s:
                s.enum(virtual_state)


class VirtualStateInfo(AbstractVirtualStructStateInfo):
    def is_virtual(self):
        return True

    def __init__(self, known_class, fielddescrs):
        AbstractVirtualStructStateInfo.__init__(self, fielddescrs)
        self.known_class = known_class

    def _generalization_of_structpart(self, other):
        return (isinstance(other, VirtualStateInfo) and
                self.known_class.same_constant(other.known_class))


    def debug_header(self, indent):
        debug_print(indent + 'VirtualStateInfo(%d):' % self.position)


class VStructStateInfo(AbstractVirtualStructStateInfo):
    def __init__(self, typedescr, fielddescrs):
        AbstractVirtualStructStateInfo.__init__(self, fielddescrs)
        self.typedescr = typedescr

    def _generalization_of_structpart(self, other):
        return (isinstance(other, VStructStateInfo) and
                self.typedescr is other.typedescr)

    def debug_header(self, indent):
        debug_print(indent + 'VStructStateInfo(%d):' % self.position)


class VArrayStateInfo(AbstractVirtualStateInfo):

    def __init__(self, arraydescr):
        self.arraydescr = arraydescr

    def _generate_guards(self, other, box, runtime_box, state):
        if not isinstance(other, VArrayStateInfo):
            raise VirtualStatesCantMatch("other is not an array")
        if self.arraydescr is not other.arraydescr:
            raise VirtualStatesCantMatch("other is a different kind of array")
        if len(self.fieldstate) != len(other.fieldstate):
            raise VirtualStatesCantMatch("other has a different length")
        fieldbox = None
        fieldbox_runtime = None
        for i in range(len(self.fieldstate)):
            if runtime_box is not None:
                opinfo = state.optimizer.getptrinfo(box)
                assert isinstance(opinfo, ArrayPtrInfo)
                fieldbox = opinfo._items[i]
                fieldbox_runtime = state.get_runtime_item(runtime_box,
                                            self.arraydescr, i)
            if self.fieldstate[i] is not None:
                if other.fieldstate[i] is None:
                    raise VirtualStatesCantMatch
                self.fieldstate[i].generate_guards(other.fieldstate[i],
                                            fieldbox, fieldbox_runtime, state)

    def enum_forced_boxes(self, boxes, box, optimizer, force_boxes=False):
        box = optimizer.get_box_replacement(box)
        info = optimizer.getptrinfo(box)
        if info is None or not info.is_virtual():
            raise VirtualStatesCantMatch()
        if len(self.fieldstate) > info.getlength():
            raise VirtualStatesCantMatch
        for i in range(len(self.fieldstate)):
            fieldbox = info.getitem(self.arraydescr, i)
            s = self.fieldstate[i]
            if s is not None:
                if s.position > self.position:
                    s.enum_forced_boxes(boxes, fieldbox, optimizer, force_boxes)

    def _enum(self, virtual_state):
        for s in self.fieldstate:
            if s:
                s.enum(virtual_state)

    def debug_header(self, indent):
        debug_print(indent + 'VArrayStateInfo(%d):' % self.position)


class VArrayStructStateInfo(AbstractVirtualStateInfo):
    def __init__(self, arraydescr, fielddescrs, length):
        self.arraydescr = arraydescr
        self.fielddescrs = fielddescrs
        self.length = length

    def _generate_guards(self, other, box, runtime_box, state):
        if not isinstance(other, VArrayStructStateInfo):
            raise VirtualStatesCantMatch("other is not an VArrayStructStateInfo")
        if self.arraydescr is not other.arraydescr:
            raise VirtualStatesCantMatch("other is a different kind of array")

        if len(self.fielddescrs) != len(other.fielddescrs):
            raise VirtualStatesCantMatch("other has a different length")

        if len(self.fielddescrs) != len(other.fielddescrs):
            raise VirtualStatesCantMatch("other has a different length")
        for j, descr in enumerate(self.fielddescrs):
            if descr is not other.fielddescrs[j]:
                raise VirtualStatesCantMatch("other is a different kind of array")
        fieldbox = None
        fieldbox_runtime = None
        if box is not None:
            opinfo = state.optimizer.getptrinfo(box)
            assert isinstance(opinfo, ArrayPtrInfo)
        else:
            opinfo = None
        for i in range(self.length):
            for descr in self.fielddescrs:
                index = i * len(self.fielddescrs) + descr.get_index()
                fieldstate = self.fieldstate[index]
                if fieldstate is None:
                    continue
                if other.fieldstate[index] is None:
                    raise VirtualStatesCantMatch
                if box is not None and opinfo is not None:
                    fieldbox = opinfo._items[index]
                    fieldbox_runtime = state.get_runtime_interiorfield(
                        runtime_box, descr, i)
                self.fieldstate[index].generate_guards(other.fieldstate[index],
                                       fieldbox, fieldbox_runtime, state)

    def _enum(self, virtual_state):
        for s in self.fieldstate:
            if s is not None:
                s.enum(virtual_state)

    def enum_forced_boxes(self, boxes, box, optimizer, force_boxes=False):
        opinfo = optimizer.getptrinfo(box)
        if not isinstance(opinfo, ArrayStructInfo):
            raise VirtualStatesCantMatch
        if not opinfo.is_virtual():
            raise VirtualStatesCantMatch
        #if len(self.fielddescrs) > len(value._items):
        #    raise VirtualStatesCantMatch
        for i in range(self.length):
            for descr in self.fielddescrs:
                index = i * len(self.fielddescrs) + descr.get_index()
                fieldstate = self.fieldstate[index]
                itembox = opinfo._items[i * len(self.fielddescrs) +
                                        descr.get_index()]
                if fieldstate is None:
                    if itembox is not None:
                        raise VirtualStatesCantMatch
                    continue
                # I think itembox must be present here
                if fieldstate.position > self.position:
                    fieldstate.enum_forced_boxes(boxes, itembox, optimizer,
                                                 force_boxes)

    def debug_header(self, indent):
        debug_print(indent + 'VArrayStructStateInfo(%d):' % self.position)


def not_virtual(cpu, type, info):
    if type == 'i':
        return NotVirtualStateInfoInt(cpu, type, info)
    if type == 'r':
        return NotVirtualStateInfoPtr(cpu, type, info)
    return NotVirtualStateInfo(cpu, type, info)


class NotVirtualStateInfo(AbstractVirtualStateInfo):
    level = LEVEL_UNKNOWN
    constbox = None

    def __init__(self, cpu, type, info):
        if info and info.is_constant():
            self.level = LEVEL_CONSTANT
            self.constbox = info.getconst()

    def is_const(self):
        return self.constbox is not None

    def is_virtual(self):
        return False

    def _generate_guards(self, other, box, runtime_box, state):
        # XXX This will always retrace instead of forcing anything which
        # might be what we want sometimes?
        extra_guards = state.extra_guards
        if self.level == LEVEL_UNKNOWN:
            return self._generate_guards_unkown(other, box, runtime_box,
                                                extra_guards,
                                                state)
        else:
            if not isinstance(other, NotVirtualStateInfo):
                raise VirtualStatesCantMatch(
                        'comparing a constant against something that is a virtual')
            assert self.level == LEVEL_CONSTANT
            if other.level == LEVEL_CONSTANT:
                if self.constbox.same_constant(other.constbox):
                    return
                raise VirtualStatesCantMatch("different constants")
            if runtime_box is not None and self.constbox.same_constant(runtime_box.constbox()):
                op = ResOperation(rop.GUARD_VALUE, [box, self.constbox])
                extra_guards.append(op)
                return
            else:
                raise VirtualStatesCantMatch("other not constant")
        assert 0, "unreachable"

    def _generate_guards_unkown(self, other, box, runtime_box, extra_guards,
                                state):
        return

    def enum_forced_boxes(self, boxes, box, optimizer, force_boxes=False):
        if self.level == LEVEL_CONSTANT:
            return
        assert 0 <= self.position_in_notvirtuals
        if optimizer is not None:
            box = optimizer.get_box_replacement(box)
            if box.type == 'r':
                info = optimizer.getptrinfo(box)
                if info and info.is_virtual():
                    if force_boxes:
                        info.force_box(box, optimizer)
                    else:
                        raise VirtualStatesCantMatch
        boxes[self.position_in_notvirtuals] = box

    def _enum(self, virtual_state):
        if self.level == LEVEL_CONSTANT:
            return
        self.position_in_notvirtuals = virtual_state.numnotvirtuals
        virtual_state.numnotvirtuals += 1

    def debug_print(self, indent, seen, bad, metainterp_sd=None):
        mark = ''
        if self in bad:
            mark = '*'
        if self.level == LEVEL_UNKNOWN:
            l = "Unknown"
        elif self.level == LEVEL_NONNULL:
            l = "NonNull"
        elif self.level == LEVEL_KNOWNCLASS:
            addr = self.known_class.getaddr()
            if metainterp_sd:
                name = metainterp_sd.get_name_from_address(addr)
            else:
                name = "?"
            l = "KnownClass(%s)" % name
        else:
            assert self.level == LEVEL_CONSTANT
            const = self.constbox
            if isinstance(const, ConstInt):
                l = "ConstInt(%s)" % (const.value, )
            elif isinstance(const, ConstPtr):
                if const.value:
                    l = "ConstPtr"
                else:
                    l = "ConstPtr(null)"
            else:
                assert isinstance(const, ConstFloat)
                l = "ConstFloat(%s)" % const.getfloat()

        lb = ''
        if self.lenbound:
            lb = ', ' + self.lenbound.bound.__repr__()

        result = indent + mark + 'NotVirtualStateInfo(%d' % self.position + ', ' + l
        extra = self._extra_repr()
        if extra:
            result += ', ' + extra
        result += lb + ')'
        debug_print(result)

class NotVirtualStateInfoInt(NotVirtualStateInfo):
    intbound = None

    def __init__(self, cpu, type, info):
        NotVirtualStateInfo.__init__(self, cpu, type, info)
        assert type == 'i'
        if isinstance(info, IntBound):
            if info.lower < MININT / 2:
                info.lower = MININT
            if info.upper > MAXINT / 2:
                info.upper = MAXINT
            self.intbound = info

    def _generate_guards_unkown(self, other, box, runtime_box, extra_guards,
                                state):
        other_intbound = None
        if isinstance(other, NotVirtualStateInfoInt):
            other_intbound = other.intbound
        if self.intbound is None:
            return
        if self.intbound.contains_bound(other_intbound):
            return
        if (runtime_box is not None and
            self.intbound.contains(runtime_box.getint())):
            # this may generate a few more guards than needed, but they are
            # optimized away when emitting them
            self.intbound.make_guards(box, extra_guards, state.optimizer)
            return
        raise VirtualStatesCantMatch("intbounds don't match")

    def _extra_repr(self):
        return self.intbound.__repr__()


class NotVirtualStateInfoPtr(NotVirtualStateInfo):
    lenbound = None
    known_class = None

    def __init__(self, cpu, type, info):
        if info:
            self.known_class = info.get_known_class(cpu)
            if self.known_class:
                self.level = LEVEL_KNOWNCLASS
            elif info.is_nonnull():
                self.level = LEVEL_NONNULL
            self.lenbound = info.getlenbound(None)
        # might set it to LEVEL_CONSTANT
        NotVirtualStateInfo.__init__(self, cpu, type, info)

    def _generate_guards(self, other, box, runtime_box, state):
        if state.force_boxes and isinstance(other, VirtualStateInfo):
            return self._generate_virtual_guards(other, box, runtime_box, state)
        if not isinstance(other, NotVirtualStateInfoPtr):
            raise VirtualStatesCantMatch(
                    'The VirtualStates does not match as a ' +
                    'virtual appears where a pointer is needed ' +
                    'and it is too late to force it.')
        extra_guards = state.extra_guards
        if self.lenbound:
            if other.lenbound is None:
                other_bound = IntLowerBound(0)
            else:
                other_bound = other.lenbound
            if not self.lenbound.contains_bound(other_bound):
                raise VirtualStatesCantMatch("length bound does not match")
        if self.level == LEVEL_NONNULL:
            return self._generate_guards_nonnull(other, box, runtime_box,
                                                 extra_guards,
                                                 state)
        elif self.level == LEVEL_KNOWNCLASS:
            return self._generate_guards_knownclass(other, box, runtime_box,
                                                    extra_guards,
                                                    state)
        return NotVirtualStateInfo._generate_guards(self, other, box,
                                                    runtime_box, state)


    # the following methods often peek into the runtime value that the
    # box had when tracing. This value is only used as an educated guess.
    # It is used here to choose between either emitting a guard and jumping
    # to an existing compiled loop or retracing the loop. Both alternatives
    # will always generate correct behaviour, but performance will differ.

    def _generate_virtual_guards(self, other, box, runtime_box, state):
        """
        Generate the guards and add state information for unifying a virtual
        object with a non-virtual. This involves forcing the object in the
        event that unification can succeed. Since virtual objects cannot be null,
        this method need only check that the virtual object has the expected type.
        """
        assert state.force_boxes and isinstance(other, VirtualStateInfo)

        if self.level == LEVEL_CONSTANT:
            raise VirtualStatesCantMatch(
                    "cannot unify a constant value with a virtual object")

        if self.level == LEVEL_KNOWNCLASS:
            if not self.known_class.same_constant(other.known_class):
                raise VirtualStatesCantMatch("classes don't match")

    def _generate_guards_nonnull(self, other, box, runtime_box, extra_guards,
                                 state):
        if not isinstance(other, NotVirtualStateInfoPtr):
            raise VirtualStatesCantMatch('trying to match ptr with non-ptr??!')
        if other.level == LEVEL_UNKNOWN:
            if runtime_box is not None and runtime_box.nonnull():
                op = ResOperation(rop.GUARD_NONNULL, [box])
                extra_guards.append(op)
                return
            else:
                raise VirtualStatesCantMatch("other not known to be nonnull")
        elif other.level == LEVEL_NONNULL:
            pass
        elif other.level == LEVEL_KNOWNCLASS:
            pass # implies nonnull
        else:
            assert other.level == LEVEL_CONSTANT
            assert other.constbox
            if not other.constbox.nonnull():
                raise VirtualStatesCantMatch("constant is null")

    def _generate_guards_knownclass(self, other, box, runtime_box, extra_guards,
                                    state):
        cpu = state.cpu
        if not isinstance(other, NotVirtualStateInfoPtr):
            raise VirtualStatesCantMatch('trying to match ptr with non-ptr??!')
        if other.level == LEVEL_UNKNOWN:
            if (runtime_box and runtime_box.nonnull() and
                  self.known_class.same_constant(cpu.ts.cls_of_box(runtime_box))):
                op = ResOperation(rop.GUARD_NONNULL_CLASS, [box, self.known_class])
                extra_guards.append(op)
            else:
                raise VirtualStatesCantMatch("other's class is unknown")
        elif other.level == LEVEL_NONNULL:
            if (runtime_box and self.known_class.same_constant(
                    cpu.ts.cls_of_box(runtime_box))):
                op = ResOperation(rop.GUARD_CLASS, [box, self.known_class])
                extra_guards.append(op)
            else:
                raise VirtualStatesCantMatch("other's class is unknown")
        elif other.level == LEVEL_KNOWNCLASS:
            if self.known_class.same_constant(other.known_class):
                return
            raise VirtualStatesCantMatch("classes don't match")
        else:
            assert other.level == LEVEL_CONSTANT
            if (other.constbox.nonnull() and
                    self.known_class.same_constant(cpu.ts.cls_of_box(other.constbox))):
                pass
            else:
                raise VirtualStatesCantMatch("classes don't match")


class VirtualState(object):
    def __init__(self, state):
        self.state = state
        self.info_counter = -1
        self.numnotvirtuals = 0
        for s in state:
            if s:
                s.enum(self)

    def generalization_of(self, other, optimizer):
        state = GenerateGuardState(optimizer)
        assert len(self.state) == len(other.state)
        try:
            for i in range(len(self.state)):
                self.state[i].generate_guards(other.state[i], None, None, state)
        except VirtualStatesCantMatch:
            return False
        return True

    def generate_guards(self, other, boxes, runtime_boxes, optimizer, force_boxes=False):
        assert (len(self.state) == len(other.state) == len(boxes) ==
                len(runtime_boxes))
        state = GenerateGuardState(optimizer, force_boxes=force_boxes)
        for i in range(len(self.state)):
            self.state[i].generate_guards(other.state[i], boxes[i],
                                          runtime_boxes[i], state)
        return state

    def make_inputargs(self, inputargs, optimizer, force_boxes=False):
        if optimizer.optearlyforce:
            optimizer = optimizer.optearlyforce
        assert len(inputargs) == len(self.state)
        boxes = [None] * self.numnotvirtuals

        # We try twice. The first time around we allow boxes to be forced
        # which might change the virtual state if the box appear in more
        # than one place among the inputargs.
        if force_boxes:
            for i in range(len(inputargs)):
                self.state[i].enum_forced_boxes(boxes, inputargs[i], optimizer,
                                                True)
        for i in range(len(inputargs)):
            self.state[i].enum_forced_boxes(boxes, inputargs[i], optimizer)

        return boxes

    def make_inputargs_and_virtuals(self, inputargs, optimizer, force_boxes=False):
        inpargs = self.make_inputargs(inputargs, optimizer, force_boxes)
        # we append the virtuals here in case some stuff is proven
        # to be not a virtual and there are getfields in the short preamble
        # that will read items out of there
        virtuals = []
        for i in range(len(inputargs)):
            if not isinstance(self.state[i], NotVirtualStateInfo):
                virtuals.append(inputargs[i])

        return inpargs, virtuals

    def debug_print(self, hdr='', bad=None, metainterp_sd=None):
        if bad is None:
            bad = {}
        debug_print(hdr + "VirtualState():")
        seen = {}
        for s in self.state:
            s.debug_print("    ", seen, bad, metainterp_sd)


class VirtualStateConstructor(VirtualVisitor):

    def __init__(self, optimizer):
        self.fieldboxes = {}
        self.optimizer = optimizer
        self.info = {}

    def register_virtual_fields(self, keybox, fieldboxes):
        self.fieldboxes[keybox] = fieldboxes

    def already_seen_virtual(self, keybox):
        return keybox in self.fieldboxes

    def create_state_or_none(self, box, opt):
        if box is None:
            return None
        return self.create_state(box, opt)

    def create_state(self, box, opt):
        box = opt.get_box_replacement(box)
        try:
            return self.info[box]
        except KeyError:
            pass
        if box.type == 'r':
            info = opt.getptrinfo(box)
            if info is not None and info.is_virtual():
                result = info.visitor_dispatch_virtual_type(self)
                self.info[box] = result
                info.visitor_walk_recursive(box, self, opt)
                result.fieldstate = [self.create_state_or_none(b, opt)
                                     for b in self.fieldboxes[box]]
            else:
                result = self.visit_not_virtual(box)
                self.info[box] = result
        elif box.type == 'i' or box.type == 'f':
            result = self.visit_not_virtual(box)
            self.info[box] = result
        else:
            assert False
        return result

    def get_virtual_state(self, jump_args):
        if self.optimizer.optearlyforce:
            opt = self.optimizer.optearlyforce
        else:
            opt = self.optimizer
        state = []
        self.info = {}
        for box in jump_args:
            state.append(self.create_state(box, opt))
        return VirtualState(state)

    def visit_not_virtual(self, box):
        return not_virtual(self.optimizer.cpu, box.type,
                           self.optimizer.getinfo(box))

    def visit_virtual(self, descr, fielddescrs):
        known_class = ConstInt(descr.get_vtable())
        return VirtualStateInfo(known_class, fielddescrs)

    def visit_vstruct(self, typedescr, fielddescrs):
        return VStructStateInfo(typedescr, fielddescrs)

    def visit_varray(self, arraydescr, clear):
        # 'clear' is ignored here.  I *think* it is correct, because so
        # far in force_at_end_of_preamble() we force all array values
        # to be non-None, so clearing is not important any more
        return VArrayStateInfo(arraydescr)

    def visit_varraystruct(self, arraydescr, length, fielddescrs):
        return VArrayStructStateInfo(arraydescr, fielddescrs, length)