from rpython.rlib import rgc
from rpython.rlib.objectmodel import we_are_translated, r_dict, always_inline
from rpython.rlib.rarithmetic import ovfcheck, highest_bit
from rpython.rtyper.lltypesystem import llmemory, lltype, rstr
from rpython.rtyper.annlowlevel import cast_instance_to_gcref
from rpython.jit.metainterp import history
from rpython.jit.metainterp.history import ConstInt, ConstPtr
from rpython.jit.metainterp.resoperation import ResOperation, rop, OpHelpers
from rpython.jit.metainterp.typesystem import rd_eq, rd_hash
from rpython.jit.codewriter import heaptracker
from rpython.jit.backend.llsupport.symbolic import (WORD,
        get_field_token, get_array_token)
from rpython.jit.backend.llsupport.descr import SizeDescr, ArrayDescr,\
     FLAG_POINTER
from rpython.jit.metainterp.history import JitCellToken
from rpython.jit.backend.llsupport.descr import (unpack_arraydescr,
        unpack_fielddescr, unpack_interiorfielddescr)
from rpython.rtyper.lltypesystem.lloperation import llop

FLAG_ARRAY = 0
FLAG_STR = 1
FLAG_UNICODE = 2

class BridgeExceptionNotFirst(Exception):
    pass

class GcRewriterAssembler(object):
    """ This class performs the following rewrites on the list of operations:

     - Turn all NEW_xxx to either a CALL_R/CHECK_MEMORY_ERROR,
       or a CALL_MALLOC_NURSERY,
       followed by SETFIELDs in order to initialize their GC fields.  The
       two advantages of CALL_MALLOC_NURSERY is that it inlines the common
       path, and we need only one such operation to allocate several blocks
       of memory at once.

     - Add COND_CALLs to the write barrier before SETFIELD_GC and
       SETARRAYITEM_GC operations.

    '_write_barrier_applied' contains a dictionary of variable -> None.
    If a variable is in the dictionary, next setfields can be called without
    a write barrier.  The idea is that an object that was freshly allocated
    or already write_barrier'd don't need another write_barrier if there
    was no potentially collecting resop inbetween.
    """

    _previous_size = -1
    _op_malloc_nursery = None
    _v_last_malloced_nursery = None
    c_zero = ConstInt(0)
    c_null = ConstPtr(lltype.nullptr(llmemory.GCREF.TO))

    def __init__(self, gc_ll_descr, cpu):
        self.gc_ll_descr = gc_ll_descr
        self.cpu = cpu
        self._newops = []
        self._known_lengths = {}
        self._write_barrier_applied = {}
        self._delayed_zero_setfields = {}
        self.last_zero_arrays = []
        self._setarrayitems_occurred = {}   # {box: {set-of-indexes}}

    def remember_known_length(self, op, val):
        self._known_lengths[op] = val

    def remember_setarrayitem_occured(self, op, index):
        op = self.get_box_replacement(op)
        try:
            subs = self._setarrayitems_occurred[op]
        except KeyError:
            subs = {}
            self._setarrayitems_occurred[op] = subs
        subs[index] = None

    def setarrayitems_occurred(self, op):