← Back to branch summary

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

« back to all changes in this revision

Viewing changes to pypy/objspace/std/multimethod.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/objspace/std/multimethod.py
 
1
 
 
2
from pypy.tool.sourcetools import compile2
 
3
 
 
4
class FailedToImplement(Exception):
 
5
    def __init__(self, w_type=None, w_value=None):
 
6
        self.w_type  = w_type
 
7
        self.w_value = w_value
 
8
 
 
9
 
 
10
def raiseFailedToImplement():
 
11
    raise FailedToImplement
 
12
 
 
13
 
 
14
class MultiMethodTable:
 
15
 
 
16
    def __init__(self, arity, root_class, argnames_before=[], argnames_after=[]):
 
17
        """NOT_RPYTHON: cannot create new multimethods dynamically.
 
18
        MultiMethod-maker dispatching on exactly 'arity' arguments.
 
19
        """
 
20
        if arity < 1:
 
21
            raise ValueError, "multimethods cannot dispatch on nothing"
 
22
        self.arity = arity
 
23
        self.root_class = root_class
 
24
        self.dispatch_tree = {}
 
25
        self.argnames_before = list(argnames_before)
 
26
        self.argnames_after = list(argnames_after)
 
27
 
 
28
    def register(self, function, *types, **kwds):
 
29
        assert len(types) == self.arity
 
30
        assert kwds.keys() == [] or kwds.keys() == ['order']
 
31
        order = kwds.get('order', 0)
 
32
        node = self.dispatch_tree
 
33
        for type in types[:-1]:
 
34
            node = node.setdefault(type, {})
 
35
        lst = node.setdefault(types[-1], [])
 
36
        if order >= len(lst):
 
37
            lst += [None] * (order+1 - len(lst))
 
38
        assert lst[order] is None, "duplicate function for %r@%d" % (
 
39
            types, order)
 
40
        lst[order] = function
 
41
 
 
42
    def install(self, prefix, list_of_typeorders, baked_perform_call=True,
 
43
                base_typeorder=None, installercls=None):
 
44
        "NOT_RPYTHON: initialization-time only"
 
45
        assert len(list_of_typeorders) == self.arity
 
46
        installercls = installercls or Installer
 
47
        installer = installercls(self, prefix, list_of_typeorders,
 
48
                                 baked_perform_call=baked_perform_call,
 
49
                                 base_typeorder=base_typeorder)
 
50
        return installer.install()
 
51
 
 
52
    def install_if_not_empty(self, prefix, list_of_typeorders,
 
53
                             base_typeorder=None, installercls=None):
 
54
        "NOT_RPYTHON: initialization-time only"
 
55
        assert len(list_of_typeorders) == self.arity
 
56
        installercls = installercls or Installer
 
57
        installer = installercls(self, prefix, list_of_typeorders,
 
58
                                 base_typeorder=base_typeorder)
 
59
        if installer.is_empty():
 
60
            return None
 
61
        else:
 
62
            return installer.install()        
 
63
        
 
64
    
 
65
 
 
66
    # ____________________________________________________________
 
67
    # limited dict-like interface to the dispatch table
 
68
 
 
69
    def getfunctions(self, types):
 
70
        assert len(types) == self.arity
 
71
        node = self.dispatch_tree
 
72
        for type in types:
 
73
            node = node[type]
 
74
        return [fn for fn in node if fn is not None]
 
75
 
 
76
    def has_signature(self, types):
 
77
        try:
 
78
            self.getfunctions(types)
 
79
        except KeyError:
 
80
            return False
 
81
        else:
 
82
            return True
 
83
 
 
84
    def signatures(self):
 
85
        """NOT_RPYTHON"""
 
86
        result = []
 
87
        def enum_keys(types_so_far, node):
 
88
            for type, subnode in node.items():
 
89
                next_types = types_so_far+(type,)
 
90
                if isinstance(subnode, dict):
 
91
                    enum_keys(next_types, subnode)
 
92
                else:
 
93
                    assert len(next_types) == self.arity
 
94
                    result.append(next_types)
 
95
        enum_keys((), self.dispatch_tree)
 
96
        return result
 
97
 
 
98
# ____________________________________________________________
 
99
# Installer version 1
 
100
 
 
101
class InstallerVersion1:
 
102
    """NOT_RPYTHON"""
 
103
 
 
104
    instance_counter = 0
 
105
 
 
106
    mmfunccache = {}
 
107
 
 
108
    prefix_memo = {}
 
109
 
 
110
    def __init__(self, multimethod, prefix, list_of_typeorders,
 
111
                 baked_perform_call=True, base_typeorder=None):
 
112
        self.__class__.instance_counter += 1
 
113
        self.multimethod = multimethod
 
114
        # avoid prefix clashes, user code should supply different prefixes
 
115
        # itself for nice names in tracebacks
 
116
        base_prefix = prefix
 
117
        n = 1
 
118
        while prefix in self.prefix_memo:
 
119
            n += 1
 
120
            prefix = "%s%d" % (base_prefix, n)
 
121
        self.prefix = prefix
 
122
        self.prefix_memo[prefix] = 1
 
123
        self.list_of_typeorders = list_of_typeorders
 
124
        self.subtree_cache = {}
 
125
        self.to_install = []
 
126
        self.non_empty = self.build_tree([], multimethod.dispatch_tree)
 
127
 
 
128
        self.baked_perform_call = baked_perform_call
 
129
        
 
130
        if self.non_empty:
 
131
            perform = [(None, prefix, 0)]
 
132
        else:
 
133
            perform = []
 
134
 
 
135
        self.perform_call = self.build_function(None, prefix+'_perform_call',
 
136
                                                None, perform)
 
137
 
 
138
    def is_empty(self):
 
139
        return not self.non_empty
 
140
 
 
141
    def install(self):
 
142
        #f = open('LOGFILE', 'a')
 
143
        #print >> f, '_'*60
 
144
        #import pprint
 
145
        #pprint.pprint(self.list_of_typeorders, f)
 
146
        for target, funcname, func, source, fallback in self.to_install:
 
147
            if target is not None:
 
148
                if hasattr(target, funcname) and fallback:
 
149
                    continue
 
150
                #print >> f, target.__name__, funcname
 
151
                #if source:
 
152
                #    print >> f, source
 
153
                #else:
 
154
                #    print >> f, '*\n'
 
155
                setattr(target, funcname, func)
 
156
        #f.close()
 
157
        return self.perform_call
 
158
 
 
159
    def build_tree(self, types_so_far, dispatch_node):
 
160
        key = tuple(types_so_far)
 
161
        if key in self.subtree_cache:
 
162
            return self.subtree_cache[key]
 
163
        non_empty = False
 
164
        typeorder = self.list_of_typeorders[len(types_so_far)]
 
165
        for next_type in typeorder:
 
166
            if self.build_single_method(typeorder, types_so_far, next_type,
 
167
                                        dispatch_node):
 
168
                non_empty = True
 
169
        self.subtree_cache[key] = non_empty
 
170
        return non_empty
 
171
 
 
172
    def build_single_method(self, typeorder, types_so_far, next_type,
 
173
                            dispatch_node):
 
174
        funcname = '__'.join([self.prefix] + [t.__name__ for t in types_so_far])
 
175
 
 
176
        order = typeorder[next_type]
 
177
        #order = [(next_type, None)] + order
 
178
 
 
179
        things_to_call = []
 
180
        for type, conversion in order:
 
181
            if type not in dispatch_node:
 
182
                # there is no possible completion of types_so_far+[type]
 
183
                # that could lead to a registered function.
 
184
                continue
 
185
            match = dispatch_node[type]
 
186
            if isinstance(match, dict):
 
187
                if self.build_tree(types_so_far+[type], match):
 
188
                    call = funcname + '__' + type.__name__
 
189
                    call_selfarg_index = len(types_so_far) + 1
 
190
                    things_to_call.append((conversion, call,
 
191
                                           call_selfarg_index))
 
192
            else:
 
193
                for func in match:   # list of functions
 
194
                    if func is not None:
 
195
                        things_to_call.append((conversion, func, None))
 
196
 
 
197
        if things_to_call:
 
198
            funcname = intern(funcname)
 
199
            self.build_function(next_type, funcname, len(types_so_far),
 
200
                                things_to_call)
 
201
            return True
 
202
        else:
 
203
            return False
 
204
 
 
205
    def build_function(self, target, funcname, func_selfarg_index,
 
206
                       things_to_call):
 
207
        # support for inventing names for the entries in things_to_call
 
208
        # which are real function objects instead of strings
 
209
        miniglobals = {'FailedToImplement': FailedToImplement}
 
210
        def invent_name(obj):
 
211
            if isinstance(obj, str):
 
212
                return obj
 
213
            name = obj.__name__
 
214
            n = 1
 
215
            while name in miniglobals:
 
216
                n += 1
 
217
                name = '%s%d' % (obj.__name__, n)
 
218
            miniglobals[name] = obj
 
219
            return name
 
220
 
 
221
        funcargs = ['arg%d' % i for i in range(self.multimethod.arity)]
 
222
 
 
223
        bodylines = []
 
224
        for conversion, call, call_selfarg_index in things_to_call:
 
225
            callargs = funcargs[:]
 
226
            if conversion is not None:
 
227
                to_convert = func_selfarg_index
 
228
                convert_callargs = (self.multimethod.argnames_before +
 
229
                                    [callargs[to_convert]])
 
230
                callargs[to_convert] = '%s(%s)' % (
 
231
                    invent_name(conversion), ', '.join(convert_callargs))
 
232
            callname = invent_name(call)
 
233
            if call_selfarg_index is not None:
 
234
                # fallback on root_class
 
235
                self.build_function(self.multimethod.root_class,
 
236
                                    callname, call_selfarg_index, [])
 
237
                callname = '%s.%s' % (callargs.pop(call_selfarg_index), callname)
 
238
            callargs = (self.multimethod.argnames_before +
 
239
                        callargs + self.multimethod.argnames_after)
 
240
            bodylines.append('return %s(%s)' % (callname, ', '.join(callargs)))
 
241
 
 
242
        fallback = False
 
243
        if not bodylines:
 
244
            miniglobals['raiseFailedToImplement'] = raiseFailedToImplement
 
245
            bodylines = ['return raiseFailedToImplement()']
 
246
            fallback = True
 
247
 
 
248
 
 
249
        # protect all lines apart from the last one by a try:except:
 
250
        for i in range(len(bodylines)-2, -1, -1):
 
251
            bodylines[i:i+1] = ['try:',
 
252
                                '    ' + bodylines[i],
 
253
                                'except FailedToImplement:',
 
254
                                '    pass']
 
255
 
 
256
        if func_selfarg_index is not None:
 
257
            selfargs = [funcargs.pop(func_selfarg_index)]
 
258
        else:
 
259
            selfargs = []
 
260
        funcargs = (selfargs + self.multimethod.argnames_before +
 
261
                    funcargs + self.multimethod.argnames_after)
 
262
 
 
263
        if target is None and not self.baked_perform_call:
 
264
            return funcargs, bodylines[0][len('return '):], miniglobals, fallback
 
265
 
 
266
        # indent mode
 
267
        bodylines = ['    ' + line for line in bodylines]
 
268
 
 
269
        bodylines.insert(0, 'def %s(%s):' % (funcname, ', '.join(funcargs)))
 
270
        bodylines.append('')
 
271
        source = '\n'.join(bodylines)
 
272
 
 
273
        # XXX find a better place (or way) to avoid duplicate functions 
 
274
        l = miniglobals.items()
 
275
        l.sort()
 
276
        l = tuple(l)
 
277
        key = (source, l)
 
278
        try: 
 
279
            func = self.mmfunccache[key]
 
280
        except KeyError: 
 
281
            exec compile2(source) in miniglobals
 
282
            func = miniglobals[funcname]
 
283
            self.mmfunccache[key] = func 
 
284
        #else: 
 
285
        #    print "avoided duplicate function", func
 
286
        self.to_install.append((target, funcname, func, source, fallback))
 
287
        return func
 
288
 
 
289
# ____________________________________________________________
 
290
# Installer version 2
 
291
 
 
292
class MMDispatcher(object):
 
293
    """NOT_RPYTHON
 
294
    Explicit dispatcher class.  This is not used in normal execution, which
 
295
    uses the complex Installer below to install single-dispatch methods to
 
296
    achieve the same result.  The MMDispatcher is only used by
 
297
    rpython.lltypesystem.rmultimethod.  It is also nice for documentation.
 
298
    """
 
299
    _revcache = None
 
300
 
 
301
    def __init__(self, multimethod, list_of_typeorders):
 
302
        self.multimethod = multimethod
 
303
        self.list_of_typeorders = list_of_typeorders
 
304
 
 
305
    def __call__(self, *args):
 
306
        # for testing only: this is slow
 
307
        i = len(self.multimethod.argnames_before)
 
308
        j = i + self.multimethod.arity
 
309
        k = j + len(self.multimethod.argnames_after)
 
310
        assert len(args) == k
 
311
        prefixargs = args[:i]
 
312
        dispatchargs = args[i:j]
 
313
        suffixargs = args[j:]
 
314
        return self.dispatch([x.__class__ for x in dispatchargs],
 
315
                             prefixargs,
 
316
                             dispatchargs,
 
317
                             suffixargs)
 
318
 
 
319
    def dispatch(self, argtypes, prefixargs, args, suffixargs):
 
320
        # for testing only: this is slow
 
321
        def expr(v):
 
322
            if isinstance(v, Call):
 
323
                return v.function(*[expr(w) for w in v.arguments])
 
324
            else:
 
325
                return v
 
326
        e = None
 
327
        for v in self.expressions(argtypes, prefixargs, args, suffixargs):
 
328
            try:
 
329
                return expr(v)
 
330
            except FailedToImplement, e:
 
331
                pass
 
332
        else:
 
333
            raise e or FailedToImplement()
 
334
 
 
335
    def expressions(self, argtypes, prefixargs, args, suffixargs):
 
336
        """Lists the possible expressions that call the appropriate
 
337
        function for the given argument types.  Each expression is a Call
 
338
        object.  The intent is that at run-time the first Call that doesn't
 
339
        cause FailedToImplement to be raised is the good one.
 
340
        """
 
341
        prefixargs = tuple(prefixargs)
 
342
        suffixargs = tuple(suffixargs)
 
343
 
 
344
        def walktree(node, args_so_far):
 
345
            if isinstance(node, list):
 
346
                for func in node:
 
347
                    if func is not None:
 
348
                        result.append(Call(func, prefixargs +
 
349
                                                 args_so_far +
 
350
                                                 suffixargs))
 
351
            else:
 
352
                index = len(args_so_far)
 
353
                typeorder = self.list_of_typeorders[index]
 
354
                next_type = argtypes[index]
 
355
                for target_type, converter in typeorder[next_type]:
 
356
                    if target_type not in node:
 
357
                        continue
 
358
                    next_arg = args[index]
 
359
                    if converter:
 
360
                        next_arg = Call(converter, prefixargs + (next_arg,))
 
361
                    walktree(node[target_type], args_so_far + (next_arg,))
 
362
 
 
363
        result = []
 
364
        walktree(self.multimethod.dispatch_tree, ())
 
365
        return result
 
366
 
 
367
    def anychance(self, typesprefix):
 
368
        # is there any chance that a list of types starting with typesprefix
 
369
        # could lead to a successful dispatch?
 
370
        # (START-UP TIME OPTIMIZATION ONLY)
 
371
        if self._revcache is None:
 
372
 
 
373
            def build_tree(types_so_far, dispatch_node):
 
374
                non_empty = False
 
375
                typeorder = self.list_of_typeorders[len(types_so_far)]
 
376
                for next_type in typeorder:
 
377
                    if build_single_method(typeorder, types_so_far, next_type,
 
378
                                           dispatch_node):
 
379
                        non_empty = True
 
380
                if non_empty:
 
381
                    self._revcache[types_so_far] = True
 
382
                return non_empty
 
383
 
 
384
            def build_single_method(typeorder, types_so_far, next_type,
 
385
                                    dispatch_node):
 
386
                order = typeorder[next_type]
 
387
                things_to_call = False
 
388
                for type, conversion in order:
 
389
                    if type not in dispatch_node:
 
390
                        # there is no possible completion of
 
391
                        # types_so_far+[type] that could lead to a
 
392
                        # registered function.
 
393
                        continue
 
394
                    match = dispatch_node[type]
 
395
                    if isinstance(match, dict):
 
396
                        if build_tree(types_so_far+(next_type,), match):
 
397
                            things_to_call = True
 
398
                    elif match:
 
399
                        things_to_call = True
 
400
                return things_to_call
 
401
 
 
402
            self._revcache = {}
 
403
            build_tree((), self.multimethod.dispatch_tree)
 
404
        return tuple(typesprefix) in self._revcache
 
405
 
 
406
 
 
407
class Call(object):
 
408
    """ Represents a call expression.
 
409
    The arguments may themselves be Call objects.
 
410
    """
 
411
    def __init__(self, function, arguments):
 
412
        self.function = function
 
413
        self.arguments = arguments
 
414
 
 
415
 
 
416
class CompressedArray(object):
 
417
    def __init__(self, null_value):
 
418
        self.null_value = null_value
 
419
        self.items = [null_value]
 
420
 
 
421
    def ensure_length(self, newlen):
 
422
        if newlen > len(self.items):
 
423
            self.items.extend([self.null_value] * (newlen - len(self.items)))
 
424
 
 
425
    def insert_subarray(self, array):
 
426
        # insert the given array of numbers into the indexlist,
 
427
        # allowing null values to become non-null
 
428
        if array.count(self.null_value) == len(array):
 
429
            return 0
 
430
        test = 1
 
431
        while True:
 
432
            self.ensure_length(test+len(array))
 
433
            for i in range(len(array)):
 
434
                if not (array[i] == self.items[test+i] or
 
435
                        array[i] == self.null_value or
 
436
                        self.items[test+i] == self.null_value):
 
437
                    break
 
438
            else:
 
439
                # success
 
440
                for i in range(len(array)):
 
441
                    if array[i] != self.null_value:
 
442
                        self.items[test+i] = array[i]
 
443
                return test
 
444
            test += 1
 
445
 
 
446
    def _freeze_(self):
 
447
        return True
 
448
 
 
449
 
 
450
class MRDTable(object):
 
451
    # Multi-Method Dispatch Using Multiple Row Displacement,
 
452
    # Candy Pang, Wade Holst, Yuri Leontiev, and Duane Szafron
 
453
    # University of Alberta, Edmonton AB T6G 2H1 Canada
 
454
    # can be found on http://web.cs.ualberta.ca/~yuri/publ.htm
 
455
 
 
456
    Counter = 0
 
457
 
 
458
    def __init__(self, list_of_types):
 
459
        self.id = MRDTable.Counter
 
460
        MRDTable.Counter += 1
 
461
        self.list_of_types = list_of_types
 
462
        self.typenum = dict(zip(list_of_types, range(len(list_of_types))))
 
463
        self.attrname = '__mrd%d_typenum' % self.id
 
464
        for t1, num in self.typenum.items():
 
465
            setattr(t1, self.attrname, num)
 
466
        self.indexarray = CompressedArray(0)
 
467
        self.strict_subclasses = {}
 
468
        for cls1 in list_of_types:
 
469
            lst = []
 
470
            for cls2 in list_of_types:
 
471
                if cls1 is not cls2 and issubclass(cls2, cls1):
 
472
                    lst.append(cls2)
 
473
            self.strict_subclasses[cls1] = lst
 
474
 
 
475
    def normalize_length(self, next_array):
 
476
        # make sure that the indexarray is not smaller than any funcarray
 
477
        self.indexarray.ensure_length(len(next_array.items))
 
478
 
 
479
 
 
480
def invent_name(miniglobals, obj):
 
481
    if isinstance(obj, str):
 
482
        return obj
 
483
    name = obj.__name__
 
484
    n = 1
 
485
    while name in miniglobals:
 
486
        n += 1
 
487
        name = '%s%d' % (obj.__name__, n)
 
488
    miniglobals[name] = obj
 
489
    return name
 
490
 
 
491
 
 
492
class FuncEntry(object):
 
493
 
 
494
    def __init__(self, bodylines, miniglobals, fallback):
 
495
        self.body = '\n    '.join(bodylines)
 
496
        self.miniglobals = miniglobals
 
497
        self.fallback = fallback
 
498
        self.possiblenames = []
 
499
        self.typetree = {}
 
500
        self._function = None
 
501
 
 
502
    def key(self):
 
503
        lst = self.miniglobals.items()
 
504
        lst.sort()
 
505
        return self.body, tuple(lst)
 
506
 
 
507
    def get_function_name(self):
 
508
        # pick a name consistently based on self.possiblenames
 
509
        length = min([len(parts) for parts in self.possiblenames])
 
510
        result = []
 
511
        for i in range(length):
 
512
            choices = {}
 
513
            for parts in self.possiblenames:
 
514
                choices[parts[i]] = True
 
515
            parts = choices.keys()
 
516
            res = str(len(parts))
 
517
            for part in parts:
 
518
                if type(part) is str:     # there is a string at this pos
 
519
                    if '0_fail' in choices:
 
520
                        res = '0_fail'
 
521
                    elif len(parts) == 1:
 
522
                        res = part
 
523
                    break
 
524
            else:
 
525
                # only types at this location, try to find a common base
 
526
                basecls = parts[0]
 
527
                for cls in parts[1:]:
 
528
                    if issubclass(basecls, cls):
 
529
                        basecls = cls
 
530
                for cls in parts[1:]:
 
531
                    if not issubclass(cls, basecls):
 
532
                        break   # no common base
 
533
                else:
 
534
                    res = basecls.__name__
 
535
            result.append(res)
 
536
        return '_'.join(result)
 
537
 
 
538
    def make_function(self, fnargs, nbargs_before, mrdtable):
 
539
        if self._function is not None:
 
540
            return self._function
 
541
        name = self.get_function_name()
 
542
        self.compress_typechecks(mrdtable)
 
543
        checklines = self.generate_typechecks(fnargs[nbargs_before:])
 
544
        if not checklines:
 
545
            body = self.body
 
546
        else:
 
547
            checklines.append(self.body)
 
548
            body = '\n    '.join(checklines)
 
549
        source = 'def %s(%s):\n    %s\n' % (name, ', '.join(fnargs), body)
 
550
 
 
551
        if 0:    # for debugging the generated mm sources
 
552
            f = open('/tmp/mm-source/%s' % name, 'a')
 
553
            for possiblename in self.possiblenames:
 
554
                print >> f, '#',
 
555
                for part in possiblename:
 
556
                    print >> f, getattr(part, '__name__', part),
 
557
                print >> f
 
558
            print >> f
 
559
            print >> f, source
 
560
            f.close()
 
561
 
 
562
        exec compile2(source) in self.miniglobals
 
563
        self._function = self.miniglobals[name]
 
564
        return self._function
 
565
 
 
566
    def register_valid_types(self, types):
 
567
        node = self.typetree
 
568
        for t1 in types[:-1]:
 
569
            if node is True:
 
570
                return
 
571
            node = node.setdefault(t1, {})
 
572
        if node is True:
 
573
            return
 
574
        node[types[-1]] = True
 
575
 
 
576
    def no_typecheck(self):
 
577
        self.typetree = True
 
578
 
 
579
    def compress_typechecks(self, mrdtable):
 
580
        def full(node):
 
581
            if node is True:
 
582
                return 1
 
583
            fulls = 0
 
584
            for key, subnode in node.items():
 
585
                if full(subnode):
 
586
                    node[key] = True
 
587
                    fulls += 1
 
588
            if fulls == types_total:
 
589
                return 1
 
590
 
 
591
            # a word about subclasses: we are using isinstance() to do
 
592
            # the checks in generate_typechecks(), which is a
 
593
            # compromize.  In theory we should check the type ids
 
594
            # instead.  But using isinstance() is better because the
 
595
            # annotator can deduce information from that.  It is still
 
596
            # correct to use isinstance() instead of type ids in
 
597
            # "reasonable" cases, though -- where "reasonable" means
 
598
            # that classes always have a delegate to their superclasses,
 
599
            # e.g. W_IntObject delegates to W_Root.  If this is true
 
600
            # then both kind of checks are good enough to spot
 
601
            # mismatches caused by the compression table.
 
602
 
 
603
            # Based on this reasoning, we can compress the typechecks a
 
604
            # bit more - if we accept W_Root, for example, then we
 
605
            # don't have to specifically accept W_IntObject too.
 
606
            for cls, subnode in node.items():
 
607
                for cls2 in mrdtable.strict_subclasses[cls]:
 
608
                    if cls2 in node and node[cls2] == subnode:
 
609
                        del node[cls2]
 
610
 
 
611
            return 0
 
612
 
 
613
        types_total = len(mrdtable.list_of_types)
 
614
        if full(self.typetree):
 
615
            self.typetree = True
 
616
 
 
617
    def generate_typechecks(self, args):
 
618
        def generate(node, level=0):
 
619
            indent = '    '*level
 
620
            if node is True:
 
621
                result.append('%s_failedtoimplement = False' % (indent,))
 
622
                return
 
623
            if not node:
 
624
                result.append('%s_failedtoimplement = True' % (indent,))
 
625
                return
 
626
            keyword = 'if'
 
627
            for key, subnode in node.items():
 
628
                typename = invent_name(self.miniglobals, key)
 
629
                result.append('%s%s isinstance(%s, %s):' % (indent, keyword,
 
630
                                                            args[level],
 
631
                                                            typename))
 
632
                generate(subnode, level+1)
 
633
                keyword = 'elif'
 
634
            result.append('%selse:' % (indent,))
 
635
            result.append('%s    _failedtoimplement = True' % (indent,))
 
636
 
 
637
        result = []
 
638
        if self.typetree is not True:
 
639
            generate(self.typetree)
 
640
            result.append('if _failedtoimplement:')
 
641
            result.append('    raise FailedToImplement')
 
642
        return result
 
643
 
 
644
 
 
645
class InstallerVersion2(object):
 
646
    """NOT_RPYTHON"""
 
647
 
 
648
    instance_counter = 0
 
649
    mrdtables = {}
 
650
 
 
651
    def __init__(self, multimethod, prefix, list_of_typeorders,
 
652
                 baked_perform_call=True, base_typeorder=None):
 
653
        #print 'InstallerVersion2:', prefix
 
654
        self.__class__.instance_counter += 1
 
655
        self.multimethod = multimethod
 
656
        self.prefix = prefix
 
657
        self.list_of_typeorders = list_of_typeorders
 
658
        self.baked_perform_call = baked_perform_call
 
659
        self.mmfunccache = {}
 
660
        args = ['arg%d' % i for i in range(multimethod.arity)]
 
661
        self.fnargs = (multimethod.argnames_before + args +
 
662
                       multimethod.argnames_after)
 
663
 
 
664
        # compute the complete table
 
665
        base_typeorder = base_typeorder or list_of_typeorders[0]
 
666
        for typeorder in list_of_typeorders:
 
667
            for t1 in typeorder:
 
668
                assert t1 in base_typeorder
 
669
 
 
670
        lst = list(base_typeorder)
 
671
        lst.sort()
 
672
        key = tuple(lst)
 
673
        try:
 
674
            self.mrdtable = self.mrdtables[key]
 
675
        except KeyError:
 
676
            self.mrdtable = self.mrdtables[key] = MRDTable(key)
 
677
 
 
678
        dispatcher = MMDispatcher(multimethod, list_of_typeorders)
 
679
        self.table = {}
 
680
        def buildtable(prefixtypes):
 
681
            if len(prefixtypes) == multimethod.arity:
 
682
                calllist = dispatcher.expressions(prefixtypes,
 
683
                                                  multimethod.argnames_before,
 
684
                                                  args,
 
685
                                                  multimethod.argnames_after)
 
686
                if calllist:
 
687
                    self.table[prefixtypes] = calllist
 
688
            elif dispatcher.anychance(prefixtypes):
 
689
                typeorder = list_of_typeorders[len(prefixtypes)]
 
690
                for t1 in typeorder:
 
691
                    buildtable(prefixtypes + (t1,))
 
692
        buildtable(())
 
693
        self.dispatcher = dispatcher
 
694
 
 
695
    def is_empty(self):
 
696
        return len(self.table) == 0
 
697
 
 
698
    def install(self):
 
699
        nskip = len(self.multimethod.argnames_before)
 
700
        null_entry = self.build_funcentry([self.prefix, '0_fail'], [])
 
701
        null_entry.no_typecheck()
 
702
        if self.is_empty():
 
703
            return self.answer(null_entry)
 
704
 
 
705
        entryarray = CompressedArray(null_entry)
 
706
        indexarray = self.mrdtable.indexarray
 
707
        lst = self.mrdtable.list_of_types
 
708
        indexline = []
 
709
 
 
710
        def compress(typesprefix, typesnum):
 
711
            if len(typesprefix) == self.multimethod.arity:
 
712
                calllist = self.table.get(typesprefix, [])
 
713
                funcname = [self.prefix]
 
714
                funcname.extend(typesprefix)
 
715
                entry = self.build_funcentry(funcname, calllist)
 
716
                entry.register_valid_types(typesprefix)
 
717
                return entry
 
718
            elif self.dispatcher.anychance(typesprefix):
 
719
                flatline = []
 
720
                for num1, t1 in enumerate(lst):
 
721
                    item = compress(typesprefix + (t1,), typesnum + (num1,))
 
722
                    flatline.append(item)
 
723
                if len(typesprefix) == self.multimethod.arity - 1:
 
724
                    array = entryarray
 
725
                else:
 
726
                    array = indexarray
 
727
                return array.insert_subarray(flatline)
 
728
            else:
 
729
                return 0
 
730
 
 
731
        master_index = compress((), ())
 
732
 
 
733
        null_func = null_entry.make_function(self.fnargs, nskip, self.mrdtable)
 
734
        funcarray = CompressedArray(null_func)
 
735
        # round up the length to a power of 2
 
736
        N = 1
 
737
        while N < len(entryarray.items):
 
738
            N *= 2
 
739
        funcarray.ensure_length(N)
 
740
        for i, entry in enumerate(entryarray.items):
 
741
            func = entry.make_function(self.fnargs, nskip, self.mrdtable)
 
742
            funcarray.items[i] = func
 
743
        self.mrdtable.normalize_length(funcarray)
 
744
 
 
745
        #print master_index
 
746
        #print indexarray.items
 
747
        #print funcarray.items
 
748
 
 
749
        attrname = self.mrdtable.attrname
 
750
        exprfn = "%d" % master_index
 
751
        for n in range(self.multimethod.arity-1):
 
752
            exprfn = "hint(indexarray.items, deepfreeze=True)[%s + arg%d.%s]" % (exprfn, n, attrname)
 
753
        n = self.multimethod.arity-1
 
754
        exprfn = "hint(funcarray.items, deepfreeze=True)[(%s + arg%d.%s) & mmmask]" % (exprfn, n,
 
755
                                                                attrname)
 
756
        expr = Call(exprfn, self.fnargs)
 
757
        entry = self.build_funcentry([self.prefix, '0_perform_call'],
 
758
                                     [expr],
 
759
                                     indexarray = indexarray,
 
760
                                     funcarray = funcarray,
 
761
                                     mmmask = N-1)
 
762
        entry.no_typecheck()
 
763
        return self.answer(entry)
 
764
 
 
765
    def answer(self, entry):
 
766
        if self.baked_perform_call:
 
767
            nskip = len(self.multimethod.argnames_before)
 
768
            return entry.make_function(self.fnargs, nskip, self.mrdtable)
 
769
        else:
 
770
            assert entry.body.startswith('return ')
 
771
            expr = entry.body[len('return '):]
 
772
            return self.fnargs, expr, entry.miniglobals, entry.fallback
 
773
 
 
774
    def build_funcentry(self, funcnameparts, calllist, **extranames):
 
775
        def expr(v):
 
776
            if isinstance(v, Call):
 
777
                return '%s(%s)' % (invent_name(miniglobals, v.function),
 
778
                                   ', '.join([expr(w) for w in v.arguments]))
 
779
            else:
 
780
                return v
 
781
 
 
782
        fallback = len(calllist) == 0
 
783
        if fallback:
 
784
            miniglobals = {'raiseFailedToImplement': raiseFailedToImplement}
 
785
            bodylines = ['return raiseFailedToImplement()']
 
786
        else:
 
787
            miniglobals = {'FailedToImplement': FailedToImplement}
 
788
            miniglobals.update(extranames)
 
789
            bodylines = []
 
790
            for v in calllist[:-1]:
 
791
                bodylines.append('try:')
 
792
                bodylines.append('    return %s' % expr(v))
 
793
                bodylines.append('except FailedToImplement:')
 
794
                bodylines.append('    pass')
 
795
            bodylines.append('return %s' % expr(calllist[-1]))
 
796
 
 
797
        from pypy.rlib.objectmodel import hint
 
798
        miniglobals['hint'] = hint
 
799
        entry = FuncEntry(bodylines, miniglobals, fallback)
 
800
        key = entry.key()
 
801
        try:
 
802
            entry = self.mmfunccache[key]
 
803
        except KeyError:
 
804
            self.mmfunccache[key] = entry
 
805
        entry.possiblenames.append(funcnameparts)
 
806
        return entry
 
807
 
 
808
# ____________________________________________________________
 
809
# Selection of the version to use
 
810
 
 
811
Installer = InstallerVersion1   # modified by translate.py targetpypystandalone