-
-
Notifications
You must be signed in to change notification settings - Fork 38
/
concrete.py
610 lines (509 loc) · 19.2 KB
/
concrete.py
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
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
import dis
import inspect
import opcode as _opcode
import struct
import sys
import types
# alias to keep the 'bytecode' variable free
import bytecode as _bytecode
from bytecode.instr import (
UNSET,
Instr,
Label,
SetLineno,
FreeVar,
CellVar,
Compare,
const_key,
_check_arg_int,
)
_WORDCODE = sys.version_info >= (3, 6)
def _set_docstring(code, consts):
if not consts:
return
first_const = consts[0]
if isinstance(first_const, str) or first_const is None:
code.docstring = first_const
class ConcreteInstr(Instr):
"""Concrete instruction.
arg must be an integer in the range 0..2147483647.
It has a read-only size attribute.
"""
__slots__ = ("_size", "_extended_args")
def __init__(self, name, arg=UNSET, *, lineno=None, extended_args=None):
# Allow to remember a potentially meaningless EXTENDED_ARG emitted by
# Python to properly compute the size and avoid messing up the jump
# targets
self._extended_args = extended_args
self._set(name, arg, lineno)
def _check_arg(self, name, opcode, arg):
if opcode >= _opcode.HAVE_ARGUMENT:
if arg is UNSET:
raise ValueError("operation %s requires an argument" % name)
_check_arg_int(name, arg)
else:
if arg is not UNSET:
raise ValueError("operation %s has no argument" % name)
def _set(self, name, arg, lineno):
super()._set(name, arg, lineno)
if _WORDCODE:
size = 2
if arg is not UNSET:
while arg > 0xFF:
size += 2
arg >>= 8
if self._extended_args is not None:
size = 2 + 2 * self._extended_args
else:
size = 1
if arg is not UNSET:
size += 2
if arg > 0xFFFF:
size += 3
if self._extended_args is not None:
size = 1 + 3 * self._extended_args
self._size = size
@property
def size(self):
return self._size
def _cmp_key(self, labels=None):
return (self._lineno, self._name, self._arg)
def get_jump_target(self, instr_offset):
if self._opcode in _opcode.hasjrel:
return instr_offset + self._size + self._arg
if self._opcode in _opcode.hasjabs:
return self._arg
return None
if _WORDCODE:
def assemble(self):
if self._arg is UNSET:
return bytes((self._opcode, 0))
arg = self._arg
b = [self._opcode, arg & 0xFF]
while arg > 0xFF:
arg >>= 8
b[:0] = [_opcode.EXTENDED_ARG, arg & 0xFF]
if self._extended_args:
while len(b) < self._size:
b[:0] = [_opcode.EXTENDED_ARG, 0x00]
return bytes(b)
else:
def assemble(self):
if self._arg is UNSET:
return struct.pack("<B", self._opcode)
arg = self._arg
if arg > 0xFFFF:
b = struct.pack(
"<BHBH", _opcode.EXTENDED_ARG, arg >> 16, self._opcode, arg & 0xFFFF
)
else:
b = struct.pack("<BH", self._opcode, arg)
if self._extended_args:
while len(b) < self._size:
b = struct.pack("<BH", _opcode.EXTENDED_ARG, 0) + b
return b
@classmethod
def disassemble(cls, lineno, code, offset):
op = code[offset]
if op >= _opcode.HAVE_ARGUMENT:
if _WORDCODE:
arg = code[offset + 1]
else:
arg = code[offset + 1] + code[offset + 2] * 256
else:
arg = UNSET
name = _opcode.opname[op]
return cls(name, arg, lineno=lineno)
class ConcreteBytecode(_bytecode._BaseBytecodeList):
def __init__(self, instructions=(), *, consts=(), names=(), varnames=()):
super().__init__()
self.consts = list(consts)
self.names = list(names)
self.varnames = list(varnames)
for instr in instructions:
self._check_instr(instr)
self.extend(instructions)
def __iter__(self):
instructions = super().__iter__()
for instr in instructions:
self._check_instr(instr)
yield instr
def _check_instr(self, instr):
if not isinstance(instr, (ConcreteInstr, SetLineno)):
raise ValueError(
"ConcreteBytecode must only contain "
"ConcreteInstr and SetLineno objects, "
"but %s was found" % type(instr).__name__
)
def _copy_attr_from(self, bytecode):
super()._copy_attr_from(bytecode)
if isinstance(bytecode, ConcreteBytecode):
self.consts = bytecode.consts
self.names = bytecode.names
self.varnames = bytecode.varnames
def __repr__(self):
return "<ConcreteBytecode instr#=%s>" % len(self)
def __eq__(self, other):
if type(self) != type(other):
return False
const_keys1 = list(map(const_key, self.consts))
const_keys2 = list(map(const_key, other.consts))
if const_keys1 != const_keys2:
return False
if self.names != other.names:
return False
if self.varnames != other.varnames:
return False
return super().__eq__(other)
@staticmethod
def from_code(code, *, extended_arg=False):
line_starts = dict(dis.findlinestarts(code))
# find block starts
instructions = []
offset = 0
lineno = code.co_firstlineno
while offset < len(code.co_code):
if offset in line_starts:
lineno = line_starts[offset]
instr = ConcreteInstr.disassemble(lineno, code.co_code, offset)
instructions.append(instr)
offset += instr.size
# replace jump targets with blocks
# HINT : in some cases Python generate useless EXTENDED_ARG opcode
# with a value of zero. Such opcodes do not increases the size of the
# following opcode the way a normal EXTENDED_ARG does. As a
# consequence, they need to be tracked manually as otherwise the
# offsets in jump targets can end up being wrong.
if not extended_arg:
nb_extended_args = 0
extended_arg = None
index = 0
while index < len(instructions):
instr = instructions[index]
if instr.name == "EXTENDED_ARG":
nb_extended_args += 1
if extended_arg is not None:
if not _WORDCODE:
raise ValueError("EXTENDED_ARG followed " "by EXTENDED_ARG")
extended_arg = (extended_arg << 8) + instr.arg
else:
extended_arg = instr.arg
del instructions[index]
continue
if extended_arg is not None:
if _WORDCODE:
arg = (extended_arg << 8) + instr.arg
else:
arg = (extended_arg << 16) + instr.arg
extended_arg = None
instr = ConcreteInstr(
instr.name,
arg,
lineno=instr.lineno,
extended_args=nb_extended_args,
)
instructions[index] = instr
nb_extended_args = 0
index += 1
if extended_arg is not None:
raise ValueError("EXTENDED_ARG at the end of the code")
bytecode = ConcreteBytecode()
bytecode.name = code.co_name
bytecode.filename = code.co_filename
bytecode.flags = code.co_flags
bytecode.argcount = code.co_argcount
if sys.version_info >= (3, 8):
bytecode.posonlyargcount = code.co_posonlyargcount
bytecode.kwonlyargcount = code.co_kwonlyargcount
bytecode.first_lineno = code.co_firstlineno
bytecode.names = list(code.co_names)
bytecode.consts = list(code.co_consts)
bytecode.varnames = list(code.co_varnames)
bytecode.freevars = list(code.co_freevars)
bytecode.cellvars = list(code.co_cellvars)
_set_docstring(bytecode, code.co_consts)
bytecode[:] = instructions
return bytecode
def _normalize_lineno(self):
lineno = self.first_lineno
for instr in self:
# if instr.lineno is not set, it's inherited from the previous
# instruction, or from self.first_lineno
if instr.lineno is not None:
lineno = instr.lineno
if isinstance(instr, ConcreteInstr):
yield (lineno, instr)
def _assemble_code(self):
offset = 0
code_str = []
linenos = []
for lineno, instr in self._normalize_lineno():
code_str.append(instr.assemble())
linenos.append((offset, lineno))
offset += instr.size
code_str = b"".join(code_str)
return (code_str, linenos)
@staticmethod
def _assemble_lnotab(first_lineno, linenos):
lnotab = []
old_offset = 0
old_lineno = first_lineno
for offset, lineno in linenos:
dlineno = lineno - old_lineno
if dlineno == 0:
continue
# FIXME: be kind, force monotonic line numbers? add an option?
if dlineno < 0 and sys.version_info < (3, 6):
raise ValueError(
"negative line number delta is not supported " "on Python < 3.6"
)
old_lineno = lineno
doff = offset - old_offset
old_offset = offset
while doff > 255:
lnotab.append(b"\xff\x00")
doff -= 255
while dlineno < -127:
lnotab.append(struct.pack("Bb", 0, -127))
dlineno -= -127
while dlineno > 126:
lnotab.append(struct.pack("Bb", 0, 126))
dlineno -= 126
assert 0 <= doff <= 255
assert -127 <= dlineno <= 126
lnotab.append(struct.pack("Bb", doff, dlineno))
return b"".join(lnotab)
def compute_stacksize(self):
bytecode = self.to_bytecode()
cfg = _bytecode.ControlFlowGraph.from_bytecode(bytecode)
return cfg.compute_stacksize()
def to_code(self, stacksize=None):
code_str, linenos = self._assemble_code()
lnotab = self._assemble_lnotab(self.first_lineno, linenos)
nlocals = len(self.varnames)
if stacksize is None:
stacksize = self.compute_stacksize()
if sys.version_info < (3, 8):
return types.CodeType(
self.argcount,
self.kwonlyargcount,
nlocals,
stacksize,
int(self.flags),
code_str,
tuple(self.consts),
tuple(self.names),
tuple(self.varnames),
self.filename,
self.name,
self.first_lineno,
lnotab,
tuple(self.freevars),
tuple(self.cellvars),
)
else:
return types.CodeType(
self.argcount,
self.posonlyargcount,
self.kwonlyargcount,
nlocals,
stacksize,
int(self.flags),
code_str,
tuple(self.consts),
tuple(self.names),
tuple(self.varnames),
self.filename,
self.name,
self.first_lineno,
lnotab,
tuple(self.freevars),
tuple(self.cellvars),
)
def to_bytecode(self):
# find jump targets
jump_targets = set()
offset = 0
for instr in self:
if isinstance(instr, SetLineno):
continue
target = instr.get_jump_target(offset)
if target is not None:
jump_targets.add(target)
offset += instr.size
# create labels
jumps = []
instructions = []
labels = {}
offset = 0
ncells = len(self.cellvars)
for lineno, instr in self._normalize_lineno():
if offset in jump_targets:
label = Label()
labels[offset] = label
instructions.append(label)
jump_target = instr.get_jump_target(offset)
size = instr.size
arg = instr.arg
# FIXME: better error reporting
if instr.opcode in _opcode.hasconst:
arg = self.consts[arg]
elif instr.opcode in _opcode.haslocal:
arg = self.varnames[arg]
elif instr.opcode in _opcode.hasname:
arg = self.names[arg]
elif instr.opcode in _opcode.hasfree:
if arg < ncells:
name = self.cellvars[arg]
arg = CellVar(name)
else:
name = self.freevars[arg - ncells]
arg = FreeVar(name)
elif instr.opcode in _opcode.hascompare:
arg = Compare(arg)
if jump_target is None:
instr = Instr(instr.name, arg, lineno=lineno)
else:
instr_index = len(instructions)
instructions.append(instr)
offset += size
if jump_target is not None:
jumps.append((instr_index, jump_target))
# replace jump targets with labels
for index, jump_target in jumps:
instr = instructions[index]
# FIXME: better error reporting on missing label
label = labels[jump_target]
instructions[index] = Instr(instr.name, label, lineno=instr.lineno)
bytecode = _bytecode.Bytecode()
bytecode._copy_attr_from(self)
nargs = bytecode.argcount + bytecode.kwonlyargcount
if sys.version_info > (3, 8):
nargs += bytecode.posonlyargcount
if bytecode.flags & inspect.CO_VARARGS:
nargs += 1
if bytecode.flags & inspect.CO_VARKEYWORDS:
nargs += 1
bytecode.argnames = self.varnames[:nargs]
_set_docstring(bytecode, self.consts)
bytecode.extend(instructions)
return bytecode
class _ConvertBytecodeToConcrete:
# Default number of passes of compute_jumps() before giving up. Refer to
# assemble_jump_offsets() in compile.c for background.
_compute_jumps_passes = 10
def __init__(self, code):
assert isinstance(code, _bytecode.Bytecode)
self.bytecode = code
# temporary variables
self.instructions = []
self.jumps = []
self.labels = {}
# used to build ConcreteBytecode() object
self.consts_indices = {}
self.consts_list = []
self.names = []
self.varnames = []
def add_const(self, value):
key = const_key(value)
if key in self.consts_indices:
return self.consts_indices[key]
index = len(self.consts_indices)
self.consts_indices[key] = index
self.consts_list.append(value)
return index
@staticmethod
def add(names, name):
try:
index = names.index(name)
except ValueError:
index = len(names)
names.append(name)
return index
def concrete_instructions(self):
ncells = len(self.bytecode.cellvars)
lineno = self.bytecode.first_lineno
for instr in self.bytecode:
if isinstance(instr, Label):
self.labels[instr] = len(self.instructions)
continue
if isinstance(instr, SetLineno):
lineno = instr.lineno
continue
if isinstance(instr, ConcreteInstr):
instr = instr.copy()
else:
assert isinstance(instr, Instr)
if instr.lineno is not None:
lineno = instr.lineno
arg = instr.arg
is_jump = isinstance(arg, Label)
if is_jump:
label = arg
# fake value, real value is set in compute_jumps()
arg = 0
elif instr.opcode in _opcode.hasconst:
arg = self.add_const(arg)
elif instr.opcode in _opcode.haslocal:
arg = self.add(self.varnames, arg)
elif instr.opcode in _opcode.hasname:
arg = self.add(self.names, arg)
elif instr.opcode in _opcode.hasfree:
if isinstance(arg, CellVar):
arg = self.bytecode.cellvars.index(arg.name)
else:
assert isinstance(arg, FreeVar)
arg = ncells + self.bytecode.freevars.index(arg.name)
elif instr.opcode in _opcode.hascompare:
if isinstance(arg, Compare):
arg = arg.value
instr = ConcreteInstr(instr.name, arg, lineno=lineno)
if is_jump:
self.jumps.append((len(self.instructions), label, instr))
self.instructions.append(instr)
def compute_jumps(self):
offsets = []
offset = 0
for index, instr in enumerate(self.instructions):
offsets.append(offset)
offset += instr.size
# needed if a label is at the end
offsets.append(offset)
# fix argument of jump instructions: resolve labels
modified = False
for index, label, instr in self.jumps:
target_index = self.labels[label]
target_offset = offsets[target_index]
if instr.opcode in _opcode.hasjrel:
instr_offset = offsets[index]
target_offset -= instr_offset + instr.size
old_size = instr.size
# FIXME: better error report if target_offset is negative
instr.arg = target_offset
if instr.size != old_size:
modified = True
return modified
def to_concrete_bytecode(self, compute_jumps_passes=None):
if compute_jumps_passes is None:
compute_jumps_passes = self._compute_jumps_passes
first_const = self.bytecode.docstring
if first_const is not UNSET:
self.add_const(first_const)
self.varnames.extend(self.bytecode.argnames)
self.concrete_instructions()
for pas in range(0, compute_jumps_passes):
modified = self.compute_jumps()
if not modified:
break
else:
raise RuntimeError(
"compute_jumps() failed to converge after" " %d passes" % (pas + 1)
)
concrete = ConcreteBytecode(
self.instructions,
consts=self.consts_list.copy(),
names=self.names,
varnames=self.varnames,
)
concrete._copy_attr_from(self.bytecode)
return concrete