← Back to branch summary

~ubuntu-branches/ubuntu/karmic/pypy/karmic

« back to all changes in this revision

Viewing changes to pypy/jit/timeshifter/rcontainer.py

  • Committer: Bazaar Package Importer
  • Author(s): Alexandre Fayolle
  • Date: 2007-04-13 09:33:09 UTC
  • Revision ID: james.westby@ubuntu.com-20070413093309-yoojh4jcoocu2krz
Tags: upstream-1.0.0
Import upstream version 1.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
pypy/jit/timeshifter/rcontainer.py
 
1
import operator
 
2
from pypy.rpython.lltypesystem import lltype, llmemory
 
3
from pypy.rpython.annlowlevel import cachedtype, cast_base_ptr_to_instance
 
4
from pypy.rpython.annlowlevel import base_ptr_lltype, cast_instance_to_base_ptr
 
5
from pypy.jit.timeshifter import rvalue
 
6
from pypy.rlib.unroll import unrolling_iterable
 
7
from pypy.jit.timeshifter import rvirtualizable
 
8
 
 
9
from pypy.annotation import model as annmodel
 
10
 
 
11
from pypy.rpython.lltypesystem import lloperation
 
12
debug_print = lloperation.llop.debug_print
 
13
debug_pdb = lloperation.llop.debug_pdb
 
14
 
 
15
class AbstractContainer(object):
 
16
    _attrs_ = []
 
17
 
 
18
    def op_getfield(self, jitstate, fielddesc):
 
19
        raise NotImplementedError
 
20
 
 
21
    def op_setfield(self, jitstate, fielddesc, valuebox):
 
22
        raise NotImplementedError
 
23
 
 
24
    def op_getsubstruct(self, jitstate, fielddesc):
 
25
        raise NotImplementedError
 
26
 
 
27
 
 
28
class VirtualContainer(AbstractContainer):
 
29
    _attrs_ = ('ownbox',)
 
30
 
 
31
    allowed_in_virtualizable = False
 
32
 
 
33
    def setforced(self, _):
 
34
        raise NotImplementedError
 
35
 
 
36
    def op_ptreq(self, jitstate, otherbox, reverse):
 
37
        equal = self is otherbox.content
 
38
        return rvalue.ll_fromvalue(jitstate, equal ^ reverse)
 
39
 
 
40
 
 
41
class FrozenContainer(AbstractContainer):
 
42
    _attrs_ = []
 
43
 
 
44
    def exactmatch(self, vstruct, outgoingvarboxes, memo):
 
45
        raise NotImplementedError
 
46
    
 
47
    def unfreeze(self, incomingvarboxes, memo):
 
48
        raise NotImplementedError
 
49
 
 
50
# ____________________________________________________________
 
51
 
 
52
class StructTypeDesc(object):
 
53
    __metaclass__ = cachedtype
 
54
 
 
55
    VirtualStructCls = None # patched later with VirtualStruct
 
56
 
 
57
    _attrs_ =  """TYPE PTRTYPE
 
58
                    firstsubstructdesc arrayfielddesc
 
59
                    innermostdesc
 
60
                    ptrkind
 
61
                    alloctoken varsizealloctoken
 
62
                    null gv_null
 
63
                    fielddescs fielddesc_by_name
 
64
                    immutable noidentity
 
65
                    materialize
 
66
                    devirtualize
 
67
                 """.split()
 
68
                            
 
69
 
 
70
    firstsubstructdesc = None
 
71
    materialize = None
 
72
 
 
73
    def __new__(cls, hrtyper, TYPE):
 
74
        if TYPE._hints.get('virtualizable', False):
 
75
            return object.__new__(VirtualizableStructTypeDesc)
 
76
        else:
 
77
            return object.__new__(StructTypeDesc)
 
78
            
 
79
    def __init__(self, hrtyper, TYPE):
 
80
        RGenOp = hrtyper.RGenOp
 
81
        self.TYPE = TYPE
 
82
        self.PTRTYPE = lltype.Ptr(TYPE)
 
83
        self.ptrkind = RGenOp.kindToken(self.PTRTYPE)
 
84
 
 
85
        self.immutable = TYPE._hints.get('immutable', False)
 
86
        self.noidentity = TYPE._hints.get('noidentity', False)
 
87
 
 
88
        fixsize = not TYPE._is_varsize()
 
89
 
 
90
        if fixsize:
 
91
            self.alloctoken = RGenOp.allocToken(TYPE)
 
92
            
 
93
        self.null = self.PTRTYPE._defl()
 
94
        self.gv_null = RGenOp.constPrebuiltGlobal(self.null)
 
95
 
 
96
        self._compute_fielddescs(hrtyper)
 
97
 
 
98
        if self.immutable and self.noidentity:
 
99
            self._define_materialize()
 
100
 
 
101
        if fixsize:
 
102
            self._define_devirtualize()
 
103
 
 
104
        
 
105
    def _compute_fielddescs(self, hrtyper):
 
106
        RGenOp = hrtyper.RGenOp
 
107
        TYPE = self.TYPE
 
108
        innermostdesc = self
 
109
        fielddescs = []
 
110
        fielddesc_by_name = {}
 
111
        for name in TYPE._names:
 
112
            FIELDTYPE = getattr(TYPE, name)
 
113
            if isinstance(FIELDTYPE, lltype.ContainerType):
 
114
                if isinstance(FIELDTYPE, lltype.Array):
 
115
                    self.arrayfielddesc = ArrayFieldDesc(hrtyper, FIELDTYPE)
 
116
                    self.varsizealloctoken = RGenOp.varsizeAllocToken(TYPE)
 
117
                    continue
 
118
                substructdesc = StructTypeDesc(hrtyper, FIELDTYPE)
 
119
                assert name == TYPE._names[0], (
 
120
                    "unsupported: inlined substructures not as first field")
 
121
                fielddescs.extend(substructdesc.fielddescs)
 
122
                self.firstsubstructdesc = substructdesc
 
123
                innermostdesc = substructdesc.innermostdesc
 
124
            else:
 
125
                index = len(fielddescs)
 
126
                if FIELDTYPE is lltype.Void:
 
127
                    desc = None
 
128
                else:
 
129
                    desc = StructFieldDesc(hrtyper, self.PTRTYPE, name, index)
 
130
                    fielddescs.append(desc)
 
131
                fielddesc_by_name[name] = desc
 
132
 
 
133
        self.fielddescs = fielddescs
 
134
        self.fielddesc_by_name = fielddesc_by_name
 
135
        self.innermostdesc = innermostdesc        
 
136
 
 
137
    def _define_devirtualize(self):
 
138
        TYPE = self.TYPE
 
139
        PTRTYPE = self.PTRTYPE
 
140
        descs = unrolling_iterable(self.fielddescs)
 
141
 
 
142
        def make(vrti):
 
143
            s = lltype.malloc(TYPE)
 
144
            s = lltype.cast_opaque_ptr(llmemory.GCREF, s)
 
145
            return s
 
146
        
 
147
        def fill_into(vablerti, s, base, vrti):
 
148
            s = lltype.cast_opaque_ptr(PTRTYPE, s)
 
149
            i = 0
 
150
            for desc in descs:
 
151
                v = vrti._read_field(vablerti, desc, base, i)
 
152
                tgt = lltype.cast_pointer(desc.PTRTYPE, s)
 
153
                setattr(tgt, desc.fieldname, v)
 
154
                i = i + 1
 
155
 
 
156
        self.devirtualize = make, fill_into
 
157
 
 
158
    def _define_materialize(self):
 
159
        TYPE = self.TYPE
 
160
        descs = unrolling_iterable(self.fielddescs)
 
161
        
 
162
        def materialize(rgenop, boxes):
 
163
            s = lltype.malloc(TYPE)
 
164
            i = 0
 
165
            for desc in descs:
 
166
                v = rvalue.ll_getvalue(boxes[i], desc.RESTYPE)
 
167
                tgt = lltype.cast_pointer(desc.PTRTYPE, s)
 
168
                setattr(tgt, desc.fieldname, v)
 
169
                i = i + 1
 
170
            return rgenop.genconst(s)
 
171
 
 
172
        self.materialize = materialize
 
173
        
 
174
    def getfielddesc(self, name):
 
175
        try:
 
176
            return self.fielddesc_by_name[name]
 
177
        except KeyError:
 
178
            return self.firstsubstructdesc.getfielddesc(name)
 
179
 
 
180
 
 
181
    def factory(self):
 
182
        vstruct = self.VirtualStructCls(self)
 
183
        vstruct.content_boxes = [desc.makedefaultbox()
 
184
                                 for desc in self.fielddescs]
 
185
        box = rvalue.PtrRedBox(self.innermostdesc.ptrkind, known_nonzero=True)
 
186
        box.content = vstruct
 
187
        vstruct.ownbox = box
 
188
        return box
 
189
 
 
190
 
 
191
def create(jitstate, typedesc):
 
192
    return typedesc.factory()
 
193
 
 
194
def create_varsize(jitstate, contdesc, sizebox):
 
195
    gv_size = sizebox.getgenvar(jitstate)
 
196
    alloctoken = contdesc.varsizealloctoken
 
197
    genvar = jitstate.curbuilder.genop_malloc_varsize(alloctoken, gv_size)
 
198
    # XXX MemoryError checking
 
199
    return rvalue.PtrRedBox(contdesc.ptrkind, genvar, known_nonzero=True)
 
200
 
 
201
 
 
202
class VirtualizableStructTypeDesc(StructTypeDesc):
 
203
 
 
204
    VirtualStructCls = None # patched later with VirtualizableStruct
 
205
 
 
206
    _attrs_  =  """redirected_fielddescs
 
207
                   redirected
 
208
                   base_desc rti_desc access_desc
 
209
                   gv_access
 
210
                   touch_update
 
211
                   gv_access_is_null_ptr access_is_null_token
 
212
                   get_rti set_rti
 
213
                """.split()
 
214
 
 
215
    def __init__(self, hrtyper, TYPE):
 
216
        RGenOp = hrtyper.RGenOp
 
217
        StructTypeDesc.__init__(self, hrtyper, TYPE)
 
218
        ACCESS = self.TYPE.ACCESS
 
219
        redirected_fields = ACCESS.redirected_fields
 
220
        self.redirected_fielddescs = []
 
221
        self.redirected = {}
 
222
        i = 0
 
223
        for fielddesc in self.fielddescs:
 
224
            if fielddesc.fieldname in redirected_fields:
 
225
                self.redirected_fielddescs.append((fielddesc, i))
 
226
                self.redirected[i] = None
 
227
            i += 1
 
228
        self.base_desc = self.getfielddesc('vable_base')
 
229
        self.rti_desc = self.getfielddesc('vable_rti')
 
230
        self.access_desc = self.getfielddesc('vable_access')
 
231
        TOPPTR = self.access_desc.PTRTYPE
 
232
        self.s_structtype = annmodel.lltype_to_annotation(TOPPTR)
 
233
 
 
234
        annhelper = hrtyper.annhelper
 
235
 
 
236
        self.my_redirected_getsetters_untouched = {}
 
237
        self.my_redirected_getsetters_touched = {}        
 
238
        self.my_redirected_names = my_redirected_names = []
 
239
        j = -1
 
240
        for fielddesc, _  in self.redirected_fielddescs:
 
241
            j += 1
 
242
            if fielddesc.PTRTYPE != self.PTRTYPE:
 
243
                continue
 
244
            my_redirected_names.append(fielddesc.fieldname)
 
245
            self._define_getset_field_ptr(hrtyper, fielddesc, j)
 
246
 
 
247
 
 
248
        access_untouched = lltype.malloc(ACCESS, immortal=True)
 
249
        access_touched = lltype.malloc(ACCESS, immortal=True)
 
250
        self._fill_access('untouched', access_untouched)
 
251
        self._fill_access('touched',   access_touched)
 
252
        self.gv_access = RGenOp.constPrebuiltGlobal(access_untouched)
 
253
 
 
254
        self.touch_update = rvirtualizable.define_touch_update(TOPPTR,
 
255
                                self.redirected_fielddescs,
 
256
                                access_touched)
 
257
 
 
258
        self._define_collect_residual_args()
 
259
 
 
260
        self._define_access_is_null(hrtyper)
 
261
 
 
262
 
 
263
    def _define_virtual_desc(self):
 
264
        pass
 
265
 
 
266
    def _define_getset_field_ptr(self, hrtyper, fielddesc, j):
 
267
        annhelper = hrtyper.annhelper
 
268
        s_lltype = annmodel.lltype_to_annotation(fielddesc.RESTYPE)
 
269
 
 
270
        untouched = self.my_redirected_getsetters_untouched
 
271
        touched = self.my_redirected_getsetters_touched
 
272
 
 
273
        mkptr = annhelper.delayedfunction
 
274
 
 
275
        fnpairs = rvirtualizable.define_getset_field_ptrs(fielddesc, j)
 
276
 
 
277
        name = fielddesc.fieldname
 
278
        for getsetters, (get_field, set_field) in zip((untouched, touched),
 
279
                                                      fnpairs):
 
280
 
 
281
            get_field_ptr = mkptr(get_field, [self.s_structtype], s_lltype,
 
282
                                             needtype = True)
 
283
            set_field_ptr = mkptr(set_field, [self.s_structtype, s_lltype],
 
284
                                             annmodel.s_None, needtype=True)
 
285
            
 
286
            getsetters[name] = get_field_ptr, set_field_ptr
 
287
 
 
288
    def _fill_access(self, which, access):
 
289
        firstsubstructdesc = self.firstsubstructdesc
 
290
        if (firstsubstructdesc is not None and 
 
291
            isinstance(firstsubstructdesc, VirtualizableStructTypeDesc)):
 
292
            firstsubstructdesc._fill_access(which, access.parent)
 
293
            
 
294
        getsetters = getattr(self, 'my_redirected_getsetters_'+which)
 
295
 
 
296
        for name, (get_field_ptr, set_field_ptr) in getsetters.iteritems():
 
297
            setattr(access, 'get_'+name, get_field_ptr)
 
298
            setattr(access, 'set_'+name, set_field_ptr)
 
299
 
 
300
    def _define_collect_residual_args(self):
 
301
        my_redirected_names = unrolling_iterable(self.my_redirected_names)
 
302
        TOPPTR = self.access_desc.PTRTYPE
 
303
 
 
304
        if TOPPTR == self.PTRTYPE:
 
305
            _super_collect = None
 
306
        else:
 
307
            _super_collect = self.firstsubstructdesc._collect_residual_args
 
308
 
 
309
        def _collect_residual_args(v): 
 
310
            if _super_collect is None:
 
311
                assert not v.vable_access  # xxx need to use access ?
 
312
                t = ()
 
313
            else:
 
314
                t = _super_collect(v.super)
 
315
            for name in my_redirected_names:
 
316
                t = t + (getattr(v, name),)
 
317
            return t
 
318
 
 
319
        self._collect_residual_args = _collect_residual_args
 
320
 
 
321
        def collect_residual_args(v): 
 
322
            t = (v,) + _collect_residual_args(v)
 
323
            return t
 
324
 
 
325
        self.collect_residual_args = collect_residual_args
 
326
 
 
327
 
 
328
    def _define_access_is_null(self, hrtyper):
 
329
        RGenOp = hrtyper.RGenOp
 
330
        annhelper = hrtyper.annhelper        
 
331
        def access_is_null(struc):
 
332
            assert not struc.vable_access
 
333
        access_is_null_ptr = annhelper.delayedfunction(access_is_null,
 
334
                                                       [self.s_structtype],
 
335
                                                       annmodel.s_None,
 
336
                                                       needtype = True)
 
337
        self.gv_access_is_null_ptr = RGenOp.constPrebuiltGlobal(
 
338
                                              access_is_null_ptr)
 
339
        self.access_is_null_token =  RGenOp.sigToken(
 
340
                                   lltype.typeOf(access_is_null_ptr).TO)
 
341
 
 
342
 
 
343
    def factory(self):
 
344
        vstructbox = StructTypeDesc.factory(self)
 
345
        outsidebox = rvalue.PtrRedBox(self.innermostdesc.ptrkind,
 
346
                                      self.gv_null)
 
347
        content = vstructbox.content
 
348
        assert isinstance(content, VirtualizableStruct)
 
349
        content.content_boxes.append(outsidebox)             
 
350
        return vstructbox
 
351
 
 
352
# ____________________________________________________________
 
353
 
 
354
# XXX basic field descs for now
 
355
class FieldDesc(object):
 
356
    __metaclass__ = cachedtype
 
357
    _attrs_ = 'structdesc'
 
358
    
 
359
    allow_void = False
 
360
    virtualizable = False
 
361
    gv_default = None
 
362
    canbevirtual = False
 
363
    gcref = False
 
364
    fieldnonnull = False
 
365
 
 
366
    def __init__(self, hrtyper, PTRTYPE, RESTYPE):
 
367
        RGenOp = hrtyper.RGenOp
 
368
        self.PTRTYPE = PTRTYPE
 
369
        T = None
 
370
        if isinstance(RESTYPE, lltype.ContainerType):
 
371
            T = RESTYPE
 
372
            RESTYPE = lltype.Ptr(RESTYPE)
 
373
            self.fieldnonnull = True
 
374
        elif isinstance(RESTYPE, lltype.Ptr):
 
375
            T = RESTYPE.TO
 
376
            if hasattr(T, '_hints'):
 
377
                # xxx hack for simple recursive cases
 
378
                if not PTRTYPE.TO._hints.get('virtualizable', False):
 
379
                    self.virtualizable = T._hints.get('virtualizable', False)
 
380
            self.gcref = T._gckind == 'gc'
 
381
            if isinstance(T, lltype.ContainerType):
 
382
                if not T._is_varsize() or hasattr(T, 'll_newlist'):
 
383
                    self.canbevirtual = True
 
384
            else:
 
385
                T = None
 
386
            self.fieldnonnull = PTRTYPE.TO._hints.get('shouldntbenull', False)
 
387
        self.RESTYPE = RESTYPE
 
388
        self.ptrkind = RGenOp.kindToken(PTRTYPE)
 
389
        self.kind = RGenOp.kindToken(RESTYPE)
 
390
        if self.RESTYPE is not lltype.Void:
 
391
            self.gv_default = RGenOp.constPrebuiltGlobal(self.RESTYPE._defl())
 
392
        if RESTYPE is lltype.Void and self.allow_void:
 
393
            pass   # no redboxcls at all
 
394
        else:
 
395
            if self.virtualizable:
 
396
                self.structdesc = StructTypeDesc(hrtyper, T)
 
397
            self.redboxcls = rvalue.ll_redboxcls(RESTYPE)
 
398
            
 
399
        self.immutable = PTRTYPE.TO._hints.get('immutable', False)
 
400
 
 
401
    def _freeze_(self):
 
402
        return True
 
403
 
 
404
    def makedefaultbox(self):
 
405
        return self.redboxcls(self.kind, self.gv_default)
 
406
    
 
407
    def makebox(self, jitstate, gvar):
 
408
        if self.virtualizable:
 
409
            structbox = self.structdesc.factory()
 
410
            content = structbox.content
 
411
            assert isinstance(content, VirtualizableStruct)
 
412
            content.load_from(jitstate, gvar)
 
413
            return structbox
 
414
        box = self.redboxcls(self.kind, gvar)
 
415
        if self.fieldnonnull:
 
416
            assert isinstance(box, rvalue.PtrRedBox)
 
417
            box.known_nonzero = True
 
418
        return box
 
419
 
 
420
    
 
421
class NamedFieldDesc(FieldDesc):
 
422
 
 
423
    def __init__(self, hrtyper, PTRTYPE, name):
 
424
        FieldDesc.__init__(self, hrtyper, PTRTYPE, getattr(PTRTYPE.TO, name))
 
425
        T = self.PTRTYPE.TO
 
426
        self.fieldname = name
 
427
        self.fieldtoken = hrtyper.RGenOp.fieldToken(T, name)
 
428
 
 
429
    def compact_repr(self): # goes in ll helper names
 
430
        return "Fld_%s_in_%s" % (self.fieldname, self.PTRTYPE._short_name())
 
431
 
 
432
    def generate_get(self, jitstate, genvar):
 
433
        builder = jitstate.curbuilder
 
434
        gv_item = builder.genop_getfield(self.fieldtoken, genvar)
 
435
        return self.makebox(jitstate, gv_item)
 
436
 
 
437
    def generate_set(self, jitstate, genvar, gv_value):
 
438
        builder = jitstate.curbuilder
 
439
        builder.genop_setfield(self.fieldtoken, genvar, gv_value)
 
440
 
 
441
    def generate_getsubstruct(self, jitstate, genvar):
 
442
        builder = jitstate.curbuilder
 
443
        gv_sub = builder.genop_getsubstruct(self.fieldtoken, genvar)
 
444
        return self.makebox(jitstate, gv_sub)
 
445
 
 
446
class StructFieldDesc(NamedFieldDesc):
 
447
 
 
448
    def __init__(self, hrtyper, PTRTYPE, name, index):
 
449
        NamedFieldDesc.__init__(self, hrtyper, PTRTYPE, name)
 
450
        self.fieldindex = index
 
451
 
 
452
class ArrayFieldDesc(FieldDesc):
 
453
    allow_void = True
 
454
 
 
455
    def __init__(self, hrtyper, TYPE):
 
456
        assert isinstance(TYPE, lltype.Array)
 
457
        FieldDesc.__init__(self, hrtyper, lltype.Ptr(TYPE), TYPE.OF)
 
458
        RGenOp = hrtyper.RGenOp
 
459
        self.arraytoken = RGenOp.arrayToken(TYPE)
 
460
        self.varsizealloctoken = RGenOp.varsizeAllocToken(TYPE)
 
461
        self.indexkind = RGenOp.kindToken(lltype.Signed)
 
462
 
 
463
# ____________________________________________________________
 
464
 
 
465
class FrozenVirtualStruct(FrozenContainer):
 
466
 
 
467
    def __init__(self, typedesc):
 
468
        self.typedesc = typedesc
 
469
        #self.fz_content_boxes initialized later
 
470
 
 
471
    def exactmatch(self, vstruct, outgoingvarboxes, memo):
 
472
        assert isinstance(vstruct, VirtualContainer)
 
473
        contmemo = memo.containers
 
474
        if self in contmemo:
 
475
            ok = vstruct is contmemo[self]
 
476
            if not ok:
 
477
                outgoingvarboxes.append(vstruct.ownbox)
 
478
            return ok
 
479
        if vstruct in contmemo:
 
480
            assert contmemo[vstruct] is not self
 
481
            outgoingvarboxes.append(vstruct.ownbox)
 
482
            return False
 
483
        if (not isinstance(vstruct, VirtualStruct)
 
484
            or self.typedesc is not vstruct.typedesc):
 
485
            if not memo.force_merge:
 
486
                raise rvalue.DontMerge
 
487
            outgoingvarboxes.append(vstruct.ownbox)
 
488
            return False
 
489
        contmemo[self] = vstruct
 
490
        contmemo[vstruct] = self
 
491
        self_boxes = self.fz_content_boxes
 
492
        vstruct_boxes = vstruct.content_boxes
 
493
        fullmatch = True
 
494
        for i in range(len(self_boxes)):
 
495
            if not self_boxes[i].exactmatch(vstruct_boxes[i],
 
496
                                            outgoingvarboxes,
 
497
                                            memo):
 
498
                fullmatch = False
 
499
        return fullmatch
 
500
 
 
501
    def unfreeze(self, incomingvarboxes, memo):
 
502
        contmemo = memo.containers
 
503
        if self in contmemo:
 
504
            return contmemo[self]
 
505
        typedesc = self.typedesc
 
506
        ownbox = typedesc.factory()
 
507
        contmemo[self] = ownbox
 
508
        vstruct = ownbox.content
 
509
        assert isinstance(vstruct, VirtualStruct)
 
510
        self_boxes = self.fz_content_boxes
 
511
        for i in range(len(self_boxes)):
 
512
            fz_box = self_boxes[i]
 
513
            vstruct.content_boxes[i] = fz_box.unfreeze(incomingvarboxes,
 
514
                                                       memo)
 
515
        return ownbox
 
516
 
 
517
 
 
518
class VirtualStruct(VirtualContainer):
 
519
    _attrs_ = "typedesc content_boxes".split()
 
520
 
 
521
    allowed_in_virtualizable = True
 
522
    
 
523
    def __init__(self, typedesc):
 
524
        self.typedesc = typedesc
 
525
        #self.content_boxes = ... set in factory()
 
526
        #self.ownbox = ... set in factory()
 
527
 
 
528
    def enter_block(self, incoming, memo):
 
529
        contmemo = memo.containers
 
530
        if self not in contmemo:
 
531
            contmemo[self] = None
 
532
            for box in self.content_boxes:
 
533
                box.enter_block(incoming, memo)
 
534
 
 
535
    def setforced(self, gv_forced):
 
536
        self.content_boxes = None
 
537
        self.ownbox.setgenvar_hint(gv_forced, known_nonzero=True)
 
538
        self.ownbox.content = None
 
539
        
 
540
    def force_runtime_container(self, jitstate):
 
541
        typedesc = self.typedesc
 
542
        builder = jitstate.curbuilder
 
543
        boxes = self.content_boxes
 
544
        self.content_boxes = None
 
545
        if typedesc.materialize is not None:
 
546
            for box in boxes:
 
547
                if box is None or not box.is_constant():
 
548
                    break
 
549
            else:
 
550
                gv = typedesc.materialize(builder.rgenop, boxes)
 
551
                self.ownbox.setgenvar_hint(gv, known_nonzero=True)
 
552
                self.ownbox.content = None
 
553
                return
 
554
        debug_print(lltype.Void, "FORCE CONTAINER: "+ typedesc.TYPE._name)
 
555
        #debug_pdb(lltype.Void)
 
556
        genvar = builder.genop_malloc_fixedsize(typedesc.alloctoken)
 
557
        # force the box pointing to this VirtualStruct
 
558
        self.setforced(genvar)
 
559
        fielddescs = typedesc.fielddescs
 
560
        for i in range(len(fielddescs)):
 
561
            fielddesc = fielddescs[i]
 
562
            box = boxes[i]
 
563
            fielddesc.generate_set(jitstate, genvar, box.getgenvar(jitstate))
 
564
 
 
565
    def freeze(self, memo):
 
566
        contmemo = memo.containers
 
567
        assert self not in contmemo     # contmemo no longer used
 
568
        result = contmemo[self] = FrozenVirtualStruct(self.typedesc)
 
569
        frozens = [box.freeze(memo) for box in self.content_boxes]
 
570
        result.fz_content_boxes = frozens
 
571
        return result
 
572
 
 
573
    def copy(self, memo):
 
574
        typedesc = self.typedesc
 
575
        contmemo = memo.containers
 
576
        assert self not in contmemo     # contmemo no longer used
 
577
        result = contmemo[self] = typedesc.VirtualStructCls(typedesc)
 
578
        result.content_boxes = [box.copy(memo)
 
579
                                for box in self.content_boxes]
 
580
        result.ownbox = self.ownbox.copy(memo)
 
581
        return result
 
582
 
 
583
    def replace(self, memo):
 
584
        contmemo = memo.containers
 
585
        assert self not in contmemo     # contmemo no longer used
 
586
        contmemo[self] = None
 
587
        content_boxes = self.content_boxes
 
588
        for i in range(len(content_boxes)):
 
589
            content_boxes[i] = content_boxes[i].replace(memo)
 
590
        self.ownbox = self.ownbox.replace(memo)
 
591
 
 
592
    def op_getfield(self, jitstate, fielddesc):
 
593
        return self.content_boxes[fielddesc.fieldindex]
 
594
 
 
595
    def op_setfield(self, jitstate, fielddesc, valuebox):
 
596
        self.content_boxes[fielddesc.fieldindex] = valuebox
 
597
 
 
598
    def op_getsubstruct(self, jitstate, fielddesc):
 
599
        return self.ownbox
 
600
 
 
601
    def make_rti(self, jitstate, memo):
 
602
        try:
 
603
            return memo.containers[self]
 
604
        except KeyError:
 
605
            pass
 
606
        typedesc = self.typedesc
 
607
        bitmask = 1 << memo.bitcount
 
608
        memo.bitcount += 1
 
609
        rgenop = jitstate.curbuilder.rgenop
 
610
        vrti = rvirtualizable.VirtualRTI(rgenop, bitmask)
 
611
        vrti.devirtualize = typedesc.devirtualize
 
612
        memo.containers[self] = vrti
 
613
 
 
614
        builder = jitstate.curbuilder
 
615
        place = builder.alloc_frame_place(typedesc.ptrkind)
 
616
        vrti.forced_place = place
 
617
        forced_box = rvalue.PtrRedBox(typedesc.ptrkind)
 
618
        memo.forced_boxes.append((forced_box, place))
 
619
 
 
620
        vars_gv = memo.framevars_gv
 
621
        varindexes = vrti.varindexes
 
622
        vrtis = vrti.vrtis
 
623
        j = -1
 
624
        for box in self.content_boxes:
 
625
            if box.genvar:
 
626
                varindexes.append(memo.frameindex)
 
627
                memo.frameindex += 1
 
628
                vars_gv.append(box.genvar)
 
629
            else:
 
630
                varindexes.append(j)
 
631
                assert isinstance(box, rvalue.PtrRedBox)
 
632
                content = box.content
 
633
                assert content.allowed_in_virtualizable                
 
634
                vrtis.append(content.make_rti(jitstate, memo))
 
635
                j -= 1
 
636
 
 
637
        self.content_boxes.append(forced_box)
 
638
        return vrti
 
639
 
 
640
    def reshape(self, jitstate, shapemask, memo):
 
641
        if self in memo.containers:
 
642
            return
 
643
        typedesc = self.typedesc
 
644
        builder = jitstate.curbuilder        
 
645
        memo.containers[self] = None
 
646
        bitmask = 1<<memo.bitcount
 
647
        memo.bitcount += 1
 
648
 
 
649
        boxes = self.content_boxes
 
650
        outside_box = boxes.pop()
 
651
        if bitmask&shapemask:
 
652
            gv_forced = outside_box.genvar
 
653
            memo.forced.append((self, gv_forced))
 
654
            
 
655
        for box in boxes:
 
656
            if not box.genvar:
 
657
                assert isinstance(box, rvalue.PtrRedBox)
 
658
                content = box.content
 
659
                assert content.allowed_in_virtualizable
 
660
                content.reshape(jitstate, shapemask, memo)
 
661
 
 
662
class VirtualizableStruct(VirtualStruct):
 
663
    
 
664
    def force_runtime_container(self, jitstate):
 
665
        assert 0
 
666
 
 
667
    def getgenvar(self, jitstate):
 
668
        typedesc = self.typedesc
 
669
        gv_outside = self.content_boxes[-1].genvar
 
670
        if gv_outside is typedesc.gv_null:
 
671
            assert isinstance(typedesc, VirtualizableStructTypeDesc)
 
672
            builder = jitstate.curbuilder
 
673
            gv_outside = builder.genop_malloc_fixedsize(typedesc.alloctoken)
 
674
            outsidebox = rvalue.PtrRedBox(self.content_boxes[-1].kind,
 
675
                                          gv_outside,
 
676
                                          known_nonzero = True)
 
677
            self.content_boxes[-1] = outsidebox
 
678
            jitstate.add_virtualizable(self.ownbox)
 
679
            #access_token = typedesc.access_desc.fieldtoken            
 
680
            #gv_access_null = typedesc.access_desc.gv_default
 
681
            #builder.genop_setfield(access_token, gv_outside, gv_access_null)
 
682
            # write all non-redirected fields
 
683
            boxes = self.content_boxes
 
684
            fielddescs = typedesc.fielddescs
 
685
            redirected = typedesc.redirected
 
686
            for i in range(len(fielddescs)):
 
687
                if i not in redirected:
 
688
                    fielddesc = fielddescs[i]
 
689
                    box = boxes[i]
 
690
                    fielddesc.generate_set(jitstate, gv_outside,
 
691
                                           box.getgenvar(jitstate))
 
692
        return gv_outside
 
693
 
 
694
    def store_back(self, jitstate):
 
695
        typedesc = self.typedesc
 
696
        assert isinstance(typedesc, VirtualizableStructTypeDesc)
 
697
        boxes = self.content_boxes
 
698
        gv_outside = boxes[-1].genvar
 
699
        for fielddesc, i in typedesc.redirected_fielddescs:
 
700
            box = boxes[i]
 
701
            fielddesc.generate_set(jitstate, gv_outside,
 
702
                                   box.getgenvar(jitstate))
 
703
 
 
704
    def load_from(self, jitstate, gv_outside):
 
705
        typedesc = self.typedesc
 
706
        assert isinstance(typedesc, VirtualizableStructTypeDesc)
 
707
        # XXX missing check for gv_outside being NULL
 
708
        boxes = self.content_boxes
 
709
        boxes[-1] = rvalue.PtrRedBox(boxes[-1].kind,
 
710
                                     gv_outside,
 
711
                                     known_nonzero=True)
 
712
        builder = jitstate.curbuilder
 
713
        builder.genop_call(typedesc.access_is_null_token,
 
714
                           typedesc.gv_access_is_null_ptr,
 
715
                           [gv_outside])
 
716
        for fielddesc, i in typedesc.redirected_fielddescs:
 
717
            boxes[i] = fielddesc.generate_get(jitstate, gv_outside)
 
718
        jitstate.add_virtualizable(self.ownbox)
 
719
 
 
720
    def make_rti(self, jitstate, memo):
 
721
        typedesc = self.typedesc
 
722
        outsidebox = self.content_boxes[-1]
 
723
        gv_outside = outsidebox.genvar
 
724
        if gv_outside is typedesc.gv_null:
 
725
            return None
 
726
        try:
 
727
            return memo.containers[self]
 
728
        except KeyError:
 
729
            pass
 
730
        assert isinstance(typedesc, VirtualizableStructTypeDesc)        
 
731
        rgenop = jitstate.curbuilder.rgenop
 
732
        vable_rti = rvirtualizable.VirtualizableRTI(rgenop, 0)
 
733
        vable_rti.touch_update = typedesc.touch_update
 
734
        vable_rti.shape_place = jitstate.shape_place
 
735
        memo.containers[self] = vable_rti
 
736
        
 
737
        vars_gv = memo.framevars_gv
 
738
        varindexes = vable_rti.varindexes
 
739
        vrtis = vable_rti.vrtis
 
740
        boxes = self.content_boxes
 
741
        j = -1
 
742
        for _, i in typedesc.redirected_fielddescs:
 
743
            box = boxes[i]
 
744
            if box.genvar:
 
745
                varindexes.append(memo.frameindex)
 
746
                memo.frameindex += 1
 
747
                vars_gv.append(box.genvar)
 
748
            else:
 
749
                varindexes.append(j)
 
750
                assert isinstance(box, rvalue.PtrRedBox)
 
751
                content = box.content
 
752
                assert content.allowed_in_virtualizable
 
753
                vrtis.append(content.make_rti(jitstate, memo))
 
754
                j -= 1
 
755
 
 
756
        nvirtual = -j-1
 
757
        bitmask = 1 << memo.bitcount
 
758
        memo.bitcount += 1
 
759
        memo.bitcount += nvirtual
 
760
        vable_rti.bitmask = bitmask
 
761
        return vable_rti
 
762
 
 
763
    def prepare_for_residual_call(self, jitstate, gv_base, vable_rti):
 
764
        typedesc = self.typedesc
 
765
        assert isinstance(typedesc, VirtualizableStructTypeDesc)        
 
766
        builder = jitstate.curbuilder
 
767
        gv_outside = self.content_boxes[-1].genvar
 
768
        base_desc = typedesc.base_desc
 
769
        base_token = base_desc.fieldtoken
 
770
        builder.genop_setfield(base_token, gv_outside, gv_base)
 
771
        vable_rti_ptr = cast_instance_to_base_ptr(vable_rti)
 
772
        gv_vable_rti = builder.rgenop.genconst(vable_rti_ptr)
 
773
        rti_token = typedesc.rti_desc.fieldtoken
 
774
        builder.genop_setfield(rti_token, gv_outside, gv_vable_rti)
 
775
        access_token = typedesc.access_desc.fieldtoken
 
776
        builder.genop_setfield(access_token, gv_outside, typedesc.gv_access)
 
777
 
 
778
    def check_forced_after_residual_call(self, jitstate):
 
779
        typedesc = self.typedesc
 
780
        builder = jitstate.curbuilder
 
781
        gv_outside = self.content_boxes[-1].genvar
 
782
        if gv_outside is typedesc.gv_null:
 
783
            return
 
784
        assert isinstance(typedesc, VirtualizableStructTypeDesc)
 
785
        access_token = typedesc.access_desc.fieldtoken            
 
786
        gv_access_null = typedesc.access_desc.gv_default
 
787
        builder.genop_setfield(access_token, gv_outside, gv_access_null)
 
788
 
 
789
 
 
790
    def reshape(self, jitstate, shapemask, memo):
 
791
        typedesc = self.typedesc
 
792
        builder = jitstate.curbuilder
 
793
        gv_outside = self.content_boxes[-1].genvar
 
794
        if gv_outside is typedesc.gv_null:
 
795
            return
 
796
        if self in memo.containers:
 
797
            return
 
798
        memo.containers[self] = None
 
799
        assert isinstance(typedesc, VirtualizableStructTypeDesc)
 
800
 
 
801
        boxes = self.content_boxes
 
802
        nvirtual = 0
 
803
        for _, i in typedesc.redirected_fielddescs:
 
804
            box = boxes[i]
 
805
            if not box.genvar:
 
806
                nvirtual += 1
 
807
                assert isinstance(box, rvalue.PtrRedBox)
 
808
                content = box.content
 
809
                assert content.allowed_in_virtualizable
 
810
                content.reshape(jitstate, shapemask, memo)
 
811
 
 
812
        bitmask = 1 << memo.bitcount
 
813
        memo.bitcount += 1
 
814
        memo.bitcount += nvirtual
 
815
        if shapemask&bitmask:
 
816
            vmask = bitmask
 
817
            for fielddesc, i in typedesc.redirected_fielddescs:
 
818
                box = boxes[i]
 
819
                if not box.genvar:
 
820
                    vmask = vmask<<1
 
821
                    if not (shapemask&vmask):
 
822
                        continue
 
823
                boxes[i] = fielddesc.generate_get(jitstate, gv_outside)
 
824
 
 
825
    def op_getfield(self, jitstate, fielddesc):
 
826
        typedesc = self.typedesc
 
827
        assert isinstance(typedesc, VirtualizableStructTypeDesc)
 
828
        gv_outside = self.content_boxes[-1].genvar
 
829
        fieldindex = fielddesc.fieldindex
 
830
        if (gv_outside is typedesc.gv_null or
 
831
            fieldindex in typedesc.redirected):
 
832
            return self.content_boxes[fieldindex]
 
833
        else:
 
834
            gv_ptr = self.getgenvar(jitstate)
 
835
            box = fielddesc.generate_get(jitstate, gv_ptr)
 
836
            return box
 
837
        
 
838
    def op_setfield(self, jitstate, fielddesc, valuebox):
 
839
        typedesc = self.typedesc
 
840
        assert isinstance(typedesc, VirtualizableStructTypeDesc)
 
841
        fieldindex = fielddesc.fieldindex
 
842
        gv_outside = self.content_boxes[-1].genvar
 
843
        if (gv_outside is typedesc.gv_null or
 
844
            fieldindex in typedesc.redirected):
 
845
            self.content_boxes[fielddesc.fieldindex] = valuebox
 
846
        else:
 
847
            gv_ptr = self.getgenvar(jitstate)
 
848
            fielddesc.generate_set(jitstate, gv_ptr,
 
849
                                   valuebox.getgenvar(jitstate))
 
850
 
 
851
    def op_ptreq(self, jitstate, otherbox, reverse):
 
852
        if self is otherbox.content:
 
853
            answer = True
 
854
        else:
 
855
            gv_outside = self.content_boxes[-1].genvar
 
856
            if gv_outside is self.typedesc.gv_null:
 
857
                answer = False
 
858
            else:
 
859
                return None   # fall-back
 
860
        return rvalue.ll_fromvalue(jitstate, answer ^ reverse)
 
861
 
 
862
# patching VirtualStructCls
 
863
StructTypeDesc.VirtualStructCls = VirtualStruct
 
864
VirtualizableStructTypeDesc.VirtualStructCls = VirtualizableStruct
 
865
 
 
866
 
 
867
# ____________________________________________________________
 
868
 
 
869
class FrozenPartialDataStruct(AbstractContainer):
 
870
 
 
871
    def __init__(self):
 
872
        self.fz_data = []
 
873
 
 
874
    def getfzbox(self, searchindex):
 
875
        for index, fzbox in self.fz_data:
 
876
            if index == searchindex:
 
877
                return fzbox
 
878
        else:
 
879
            return None
 
880
 
 
881
    def match(self, box, partialdatamatch):
 
882
        content = box.content
 
883
        if not isinstance(content, PartialDataStruct):
 
884
            return False
 
885
 
 
886
        cankeep = {}
 
887
        for index, subbox in content.data:
 
888
            selfbox = self.getfzbox(index)
 
889
            if selfbox is not None and selfbox.is_constant_equal(subbox):
 
890
                cankeep[index] = None
 
891
        fullmatch = len(cankeep) == len(self.fz_data)
 
892
        try:
 
893
            prevkeep = partialdatamatch[box]
 
894
        except KeyError:
 
895
            partialdatamatch[box] = cankeep
 
896
        else:
 
897
            if prevkeep is not None:
 
898
                d = {}
 
899
                for index in prevkeep:
 
900
                    if index in cankeep:
 
901
                        d[index] = None
 
902
                partialdatamatch[box] = d
 
903
        return fullmatch
 
904
 
 
905
 
 
906
class PartialDataStruct(AbstractContainer):
 
907
 
 
908
    def __init__(self):
 
909
        self.data = []
 
910
 
 
911
    def op_getfield(self, jitstate, fielddesc):
 
912
        searchindex = fielddesc.fieldindex
 
913
        for index, box in self.data:
 
914
            if index == searchindex:
 
915
                return box
 
916
        else:
 
917
            return None
 
918
 
 
919
    def remember_field(self, fielddesc, box):
 
920
        searchindex = fielddesc.fieldindex
 
921
        for i in range(len(self.data)):
 
922
            if self.data[i][0] == searchindex:
 
923
                self.data[i] = searchindex, box
 
924
                return
 
925
        else:
 
926
            self.data.append((searchindex, box))
 
927
 
 
928
    def partialfreeze(self, memo):
 
929
        contmemo = memo.containers
 
930
        assert self not in contmemo     # contmemo no longer used
 
931
        result = contmemo[self] = FrozenPartialDataStruct()
 
932
        for index, box in self.data:
 
933
            if box.is_constant():
 
934
                frozenbox = box.freeze(memo)
 
935
                result.fz_data.append((index, frozenbox))
 
936
        if len(result.fz_data) == 0:
 
937
            return None
 
938
        else:
 
939
            return result
 
940
 
 
941
    def copy(self, memo):
 
942
        result = PartialDataStruct()
 
943
        for index, box in self.data:
 
944
            result.data.append((index, box.copy(memo)))
 
945
        return result
 
946
 
 
947
    def replace(self, memo):
 
948
        for i in range(len(self.data)):
 
949
            index, box = self.data[i]
 
950
            box = box.replace(memo)
 
951
            self.data[i] = index, box
 
952
 
 
953
    def enter_block(self, incoming, memo):
 
954
        contmemo = memo.containers
 
955
        if self not in contmemo:
 
956
            contmemo[self] = None
 
957
            for index, box in self.data:
 
958
                box.enter_block(incoming, memo)
 
959
 
 
960
    def cleanup_partial_data(self, keep):
 
961
        if keep is None:
 
962
            return None
 
963
        j = 0
 
964
        data = self.data
 
965
        for i in range(len(data)):
 
966
            item = data[i]
 
967
            if item[0] in keep:
 
968
                data[j] = item
 
969
                j += 1
 
970
        if j == 0:
 
971
            return None
 
972
        del data[j:]
 
973
        return self