1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
|
"""
The Bookkeeper class.
"""
from types import FunctionType, ClassType, MethodType
from types import BuiltinMethodType
from pypy.annotation.model import *
from pypy.annotation.classdef import ClassDef
from pypy.interpreter.miscutils import getthreadlocals
from pypy.tool.hack import func_with_new_name
from pypy.interpreter.pycode import CO_VARARGS
from pypy.interpreter.pycode import cpython_code_signature
from pypy.interpreter.argument import ArgErr
class Bookkeeper:
"""The log of choices that have been made while analysing the operations.
It ensures that the same 'choice objects' will be returned if we ask
again during reflowing. Like ExecutionContext, there is an implicit
Bookkeeper that can be obtained from a thread-local variable.
Currently used for factories and user-defined classes."""
def __init__(self, annotator):
self.annotator = annotator
self.creationpoints = {} # map position-in-a-block to its Factory
self.userclasses = {} # map classes to ClassDefs
self.userclasseslist = []# userclasses.keys() in creation order
self.cachespecializations = {}
self.pbccache = {}
# import ordering hack
global BUILTIN_ANALYZERS
from pypy.annotation.builtin import BUILTIN_ANALYZERS
def enter(self, position_key):
"""Start of an operation.
The operation is uniquely identified by the given key."""
self.position_key = position_key
getthreadlocals().bookkeeper = self
def leave(self):
"""End of an operation."""
del getthreadlocals().bookkeeper
del self.position_key
def is_in_an_operation(self):
return hasattr(self, 'position_key')
def getfactory(self, factorycls):
"""Get the Factory associated with the current position,
or build it if it doesn't exist yet."""
try:
factory = self.creationpoints[self.position_key]
except KeyError:
factory = factorycls()
factory.bookkeeper = self
factory.position_key = self.position_key
self.creationpoints[self.position_key] = factory
assert isinstance(factory, factorycls)
return factory
def getclassdef(self, cls):
"""Get the ClassDef associated with the given user cls."""
if cls is object:
return None
try:
return self.userclasses[cls]
except KeyError:
cdef = ClassDef(cls, self)
self.userclasses[cls] = cdef
self.userclasseslist.append(cdef)
return self.userclasses[cls]
def immutablevalue(self, x):
"""The most precise SomeValue instance that contains the
immutable value x."""
tp = type(x)
if tp is bool:
result = SomeBool()
elif tp is int:
result = SomeInteger(nonneg = x>=0)
elif tp is str:
result = SomeString()
elif tp is tuple:
result = SomeTuple(items = [self.immutablevalue(e) for e in x])
elif tp is list:
items_s = [self.immutablevalue(e) for e in x]
result = SomeList({}, unionof(*items_s))
elif tp is dict: # exactly a dict
keys_s = [self.immutablevalue(e) for e in x.keys()]
values_s = [self.immutablevalue(e) for e in x.values()]
result = SomeDict({}, unionof(*keys_s), unionof(*values_s))
elif ishashable(x) and x in BUILTIN_ANALYZERS:
result = SomeBuiltin(BUILTIN_ANALYZERS[x])
elif callable(x) or isinstance(x, staticmethod): # XXX
# maybe 'x' is a method bound to a not-yet-frozen cache?
# fun fun fun.
if (hasattr(x, 'im_self') and isinstance(x.im_self, Cache)
and not x.im_self.frozen):
x.im_self.freeze()
if hasattr(x, '__self__') and x.__self__ is not None:
s_self = self.immutablevalue(x.__self__)
try:
result = s_self.find_method(x.__name__)
except AttributeError:
result = SomeObject()
else:
return self.getpbc(x)
elif hasattr(x, '__class__') \
and x.__class__.__module__ != '__builtin__':
if isinstance(x, Cache) and not x.frozen:
x.freeze()
return self.getpbc(x)
elif x is None:
return self.getpbc(None)
else:
result = SomeObject()
result.const = x
return result
def getpbc(self, x):
try:
# this is not just an optimization, but needed to avoid
# infinitely repeated calls to add_source_for_attribute()
return self.pbccache[x]
except KeyError:
result = SomePBC({x: True}) # pre-built inst
clsdef = self.getclassdef(new_or_old_class(x))
for attr in getattr(x, '__dict__', {}):
clsdef.add_source_for_attribute(attr, x)
self.pbccache[x] = result
return result
def valueoftype(self, t):
"""The most precise SomeValue instance that contains all
objects of type t."""
if t is bool:
return SomeBool()
elif t is int:
return SomeInteger()
elif t is str:
return SomeString()
elif t is list:
return SomeList(factories={})
# can't do dict, tuple
elif isinstance(t, (type, ClassType)) and \
t.__module__ != '__builtin__':
classdef = self.getclassdef(t)
if self.is_in_an_operation():
# woha! instantiating a "mutable" SomeXxx like
# SomeInstance is always dangerous, because we need to
# allow reflowing from the current operation if/when
# the classdef later changes.
classdef.instantiation_locations[self.position_key] = True
return SomeInstance(classdef)
else:
o = SomeObject()
o.knowntype = t
return o
def pycall(self, func, args):
if func is None: # consider None as a NULL function pointer
return SomeImpossibleValue()
if isinstance(func, (type, ClassType)) and \
func.__module__ != '__builtin__':
cls = func
x = getattr(cls, "_specialize_", False)
if x:
if x == "location":
cls = self.specialize_by_key(cls, self.position_key)
else:
raise Exception, \
"unsupported specialization type '%s'"%(x,)
classdef = self.getclassdef(cls)
classdef.instantiation_locations[self.position_key] = True
s_instance = SomeInstance(classdef)
# flow into __init__() if the class has got one
init = getattr(cls, '__init__', None)
if init is not None and init != object.__init__:
# don't record the access of __init__ on the classdef
# because it is not a dynamic attribute look-up, but
# merely a static function call
if hasattr(init, 'im_func'):
init = init.im_func
else:
assert isinstance(init, BuiltinMethodType)
s_init = self.immutablevalue(init)
s_init.call(args.prepend(s_instance))
else:
try:
args.fixedunpack(0)
except ValueError:
raise Exception, "no __init__ found in %r" % (cls,)
return s_instance
if hasattr(func, '__call__') and \
isinstance(func.__call__, MethodType):
func = func.__call__
if hasattr(func, 'im_func'):
if func.im_self is not None:
s_self = self.immutablevalue(func.im_self)
args = args.prepend(s_self)
# for debugging only, but useful to keep anyway:
try:
func.im_func.class_ = func.im_class
except AttributeError:
# probably a builtin function, we don't care to preserve
# class information then
pass
func = func.im_func
assert isinstance(func, FunctionType), "expected function, got %r"%func
# do we need to specialize this function in several versions?
x = getattr(func, '_specialize_', False)
#if not x:
# x = 'argtypes'
if x:
if x == 'argtypes':
key = short_type_name(args)
func = self.specialize_by_key(func, key,
func.__name__+'__'+key)
elif x == "location":
# fully specialize: create one version per call position
func = self.specialize_by_key(func, self.position_key)
else:
raise Exception, "unsupported specialization type '%s'"%(x,)
elif func.func_code.co_flags & CO_VARARGS:
# calls to *arg functions: create one version per number of args
assert not args.has_keywords(), (
"keyword forbidden in calls to *arg functions")
nbargs = len(args.arguments_w)
if args.w_stararg is not None:
s_len = args.w_stararg.len()
assert s_len.is_constant(), "calls require known number of args"
nbargs += s_len.const
func = self.specialize_by_key(func, nbargs,
name='%s__%d' % (func.func_name,
nbargs))
# parse the arguments according to the function we are calling
signature = cpython_code_signature(func.func_code)
defs_s = []
if func.func_defaults:
for x in func.func_defaults:
defs_s.append(self.immutablevalue(x))
try:
inputcells = args.match_signature(signature, defs_s)
except ArgErr, e:
assert False, 'ABOUT TO IGNORE %r' % e # hopefully temporary hack
return SomeImpossibleValue()
return self.annotator.recursivecall(func, self.position_key, inputcells)
def whereami(self):
return self.annotator.whereami(self.position_key)
def specialize_by_key(self, thing, key, name=None):
key = thing, key
try:
thing = self.cachespecializations[key]
except KeyError:
if isinstance(thing, FunctionType):
# XXX XXX XXX HAAAAAAAAAAAACK
self.annotator.translator.getflowgraph(thing)
thing = func_with_new_name(thing, name or thing.func_name)
elif isinstance(thing, (type, ClassType)):
assert not "not working yet"
thing = type(thing)(name or thing.__name__, (thing,))
else:
raise Exception, "specializing %r?? why??"%thing
self.cachespecializations[key] = thing
return thing
def getbookkeeper():
"""Get the current Bookkeeper.
Only works during the analysis of an operation."""
return getthreadlocals().bookkeeper
def ishashable(x):
try:
hash(x)
except TypeError:
return False
else:
return True
def short_type_name(args):
l = []
shape, args_w = args.flatten()
for x in args_w:
if isinstance(x, SomeInstance) and hasattr(x, 'knowntype'):
name = "SI_" + x.knowntype.__name__
else:
name = x.__class__.__name__
l.append(name)
return "__".join(l)
|