Author: Brian Kearns <[email protected]>
Branch: stdlib-2.7.4
Changeset: r60710:354042e98f1a
Date: 2013-01-30 02:06 -0500
http://bitbucket.org/pypy/pypy/changeset/354042e98f1a/
Log: merge default
diff --git a/pypy/module/_bisect/interp_bisect.py
b/pypy/module/_bisect/interp_bisect.py
--- a/pypy/module/_bisect/interp_bisect.py
+++ b/pypy/module/_bisect/interp_bisect.py
@@ -1,5 +1,6 @@
from pypy.interpreter.error import OperationError
from pypy.interpreter.gateway import unwrap_spec
+from rpython.rlib.rarithmetic import intmask, r_uint
@unwrap_spec(lo=int, hi=int)
@@ -18,7 +19,7 @@
if hi == -1:
hi = space.len_w(w_a)
while lo < hi:
- mid = (lo + hi) >> 1
+ mid = intmask((r_uint(lo) + r_uint(hi)) >> 1)
w_litem = space.getitem(w_a, space.wrap(mid))
if space.is_true(space.lt(w_litem, w_x)):
lo = mid + 1
@@ -43,7 +44,7 @@
if hi == -1:
hi = space.len_w(w_a)
while lo < hi:
- mid = (lo + hi) >> 1
+ mid = intmask((r_uint(lo) + r_uint(hi)) >> 1)
w_litem = space.getitem(w_a, space.wrap(mid))
if space.is_true(space.lt(w_x, w_litem)):
hi = mid
diff --git a/pypy/module/_bisect/test/test_bisect.py
b/pypy/module/_bisect/test/test_bisect.py
--- a/pypy/module/_bisect/test/test_bisect.py
+++ b/pypy/module/_bisect/test/test_bisect.py
@@ -89,3 +89,12 @@
insort_right(a, 6.0)
assert a == [0, 5, 6, 6, 6, 6.0, 7]
assert map(type, a) == [int, int, int, int, int, float, int]
+
+ def test_bisect_overflow(self):
+ from _bisect import bisect_left, bisect_right
+ import sys
+
+ size = sys.maxsize
+ data = xrange(size - 1)
+ assert bisect_left(data, size - 3) == size - 3
+ assert bisect_right(data, size - 3) == size - 2
diff --git a/rpython/flowspace/framestate.py b/rpython/flowspace/framestate.py
--- a/rpython/flowspace/framestate.py
+++ b/rpython/flowspace/framestate.py
@@ -1,5 +1,6 @@
+from rpython.flowspace.model import Variable, Constant
from rpython.rlib.unroll import SpecTag
-from rpython.flowspace.model import *
+
class FrameState:
def __init__(self, mergeable, blocklist, next_instr):
@@ -86,6 +87,7 @@
raise TypeError('union of %r and %r' % (w1.__class__.__name__,
w2.__class__.__name__))
+
# ____________________________________________________________
#
# We have to flatten out the state of the frame into a list of
@@ -102,6 +104,7 @@
PICKLE_TAGS = {}
UNPICKLE_TAGS = {}
+
def recursively_flatten(space, lst):
from rpython.flowspace.flowcontext import SuspendedUnroller
i = 0
@@ -117,14 +120,15 @@
except:
tag = PICKLE_TAGS[key] = Constant(PickleTag())
UNPICKLE_TAGS[tag] = key
- lst[i:i+1] = [tag] + vars
+ lst[i:i + 1] = [tag] + vars
+
def recursively_unflatten(space, lst):
- for i in xrange(len(lst)-1, -1, -1):
+ for i in xrange(len(lst) - 1, -1, -1):
item = lst[i]
if item in UNPICKLE_TAGS:
unrollerclass, argcount = UNPICKLE_TAGS[item]
- arguments = lst[i+1: i+1+argcount]
- del lst[i+1: i+1+argcount]
+ arguments = lst[i + 1:i + 1 + argcount]
+ del lst[i + 1:i + 1 + argcount]
unroller = unrollerclass.state_pack_variables(space, *arguments)
lst[i] = unroller
diff --git a/rpython/jit/metainterp/optimizeopt/unroll.py
b/rpython/jit/metainterp/optimizeopt/unroll.py
--- a/rpython/jit/metainterp/optimizeopt/unroll.py
+++ b/rpython/jit/metainterp/optimizeopt/unroll.py
@@ -1,16 +1,16 @@
-from rpython.jit.codewriter.effectinfo import EffectInfo
+import sys
+
+from rpython.jit.metainterp.compile import ResumeGuardDescr
+from rpython.jit.metainterp.history import TargetToken, JitCellToken, Const
+from rpython.jit.metainterp.inliner import Inliner
+from rpython.jit.metainterp.optimize import InvalidLoop
+from rpython.jit.metainterp.optimizeopt.generalize import KillHugeIntBounds
+from rpython.jit.metainterp.optimizeopt.optimizer import Optimizer,
Optimization
from rpython.jit.metainterp.optimizeopt.virtualstate import VirtualStateAdder,
ShortBoxes, BadVirtualState
-from rpython.jit.metainterp.compile import ResumeGuardDescr
-from rpython.jit.metainterp.history import TreeLoop, TargetToken, JitCellToken
-from rpython.jit.metainterp.jitexc import JitException
-from rpython.jit.metainterp.optimize import InvalidLoop
-from rpython.rlib.debug import debug_print, debug_start, debug_stop
-from rpython.jit.metainterp.optimizeopt.optimizer import *
-from rpython.jit.metainterp.optimizeopt.generalize import KillHugeIntBounds
-from rpython.jit.metainterp.inliner import Inliner
from rpython.jit.metainterp.resoperation import rop, ResOperation
from rpython.jit.metainterp.resume import Snapshot
-import sys, os
+from rpython.rlib.debug import debug_print, debug_start, debug_stop
+
# FIXME: Introduce some VirtualOptimizer super class instead
@@ -19,6 +19,7 @@
opt.inline_short_preamble = inline_short_preamble
opt.propagate_all_forward()
+
class UnrollableOptimizer(Optimizer):
def setup(self):
self.importable_values = {}
@@ -51,7 +52,7 @@
distinction anymore)"""
inline_short_preamble = True
-
+
def __init__(self, metainterp_sd, loop, optimizations):
self.optimizer = UnrollableOptimizer(metainterp_sd, loop,
optimizations)
self.boxes_created_this_iteration = None
@@ -59,14 +60,14 @@
def fix_snapshot(self, jump_args, snapshot):
if snapshot is None:
return None
- snapshot_args = snapshot.boxes
+ snapshot_args = snapshot.boxes
new_snapshot_args = []
for a in snapshot_args:
a = self.getvalue(a).get_key_box()
new_snapshot_args.append(a)
prev = self.fix_snapshot(jump_args, snapshot.prev)
return Snapshot(prev, new_snapshot_args)
-
+
def propagate_all_forward(self):
loop = self.optimizer.loop
self.optimizer.clear_newoperations()
@@ -78,7 +79,7 @@
# will clear heap caches
self.optimizer.send_extra_operation(start_label)
else:
- start_label = None
+ start_label = None
jumpop = loop.operations[-1]
if jumpop.getopnum() == rop.JUMP or jumpop.getopnum() == rop.LABEL:
@@ -96,7 +97,6 @@
assert isinstance(cell_token, JitCellToken)
stop_label = ResOperation(rop.LABEL, jumpop.getarglist(), None,
TargetToken(cell_token))
-
if jumpop.getopnum() == rop.JUMP:
if self.jump_to_already_compiled_trace(jumpop):
# Found a compiled trace to jump to
@@ -130,7 +130,7 @@
return
# Found nothing to jump to, emit a label instead
-
+
if self.short:
# Construct our short preamble
assert start_label
@@ -146,7 +146,7 @@
def jump_to_start_label(self, start_label, stop_label):
if not start_label or not stop_label:
return False
-
+
stop_target = stop_label.getdescr()
start_target = start_label.getdescr()
assert isinstance(stop_target, TargetToken)
@@ -161,7 +161,6 @@
#virtual_state = modifier.get_virtual_state(args)
#if self.initial_virtual_state.generalization_of(virtual_state):
# return True
-
def export_state(self, targetop):
original_jump_args = targetop.getarglist()
@@ -174,12 +173,11 @@
modifier = VirtualStateAdder(self.optimizer)
virtual_state = modifier.get_virtual_state(jump_args)
-
+
values = [self.getvalue(arg) for arg in jump_args]
inputargs = virtual_state.make_inputargs(values, self.optimizer)
short_inputargs = virtual_state.make_inputargs(values, self.optimizer,
keyboxes=True)
-
if self.boxes_created_this_iteration is not None:
for box in self.inputargs:
self.boxes_created_this_iteration[box] = True
@@ -210,7 +208,7 @@
if op and op.result:
box = op.result
exported_values[box] = self.optimizer.getvalue(box)
-
+
target_token.exported_state = ExportedState(short_boxes,
inputarg_setup_ops,
exported_values)
@@ -232,7 +230,7 @@
virtual_state = modifier.get_virtual_state(self.inputargs)
self.initial_virtual_state = virtual_state
return
-
+
self.short = target_token.short_preamble[:]
self.short_seen = {}
self.short_boxes = exported_state.short_boxes
@@ -276,7 +274,7 @@
#if self.optimizer.loop.logops:
# debug_print(' Falling back to add extra: ' +
#
self.optimizer.loop.logops.repr_of_resop(op))
-
+
self.optimizer.flush()
self.optimizer.emitting_dissabled = False
@@ -287,7 +285,7 @@
# We dont need to inline the short preamble we are creating as we are
conneting
# the bridge to a different trace with a different short preamble
self.short_inliner = None
-
+
newoperations = self.optimizer.get_newoperations()
self.boxes_created_this_iteration = {}
i = 0
@@ -333,7 +331,7 @@
'same box passed to multiple of its ' +
'inputargs, but the jump at the ' +
'end of this bridge does not do that.')
-
+
args[short_inputargs[i]] = jmp_to_short_args[i]
self.short_inliner = Inliner(short_inputargs, jmp_to_short_args)
i = 1
@@ -400,7 +398,7 @@
'loop is not compatible with the virtual ' +
'state at the start of the loop which makes ' +
'it impossible to close the loop')
-
+
#debug_stop('jit-log-virtualstate')
maxguards =
self.optimizer.metainterp_sd.warmrunnerdesc.memory_manager.max_retrace_guards
@@ -408,9 +406,9 @@
target_token = jumpop.getdescr()
assert isinstance(target_token, TargetToken)
target_token.targeting_jitcell_token.retraced_count = sys.maxint
-
+
self.finilize_short_preamble(start_label)
-
+
def finilize_short_preamble(self, start_label):
short = self.short
assert short[-1].getopnum() == rop.JUMP
@@ -482,11 +480,11 @@
if op is None:
return None
if op.result is not None and op.result in self.short_seen:
- if emit and self.short_inliner:
+ if emit and self.short_inliner:
return self.short_inliner.inline_arg(op.result)
else:
return None
-
+
for a in op.getarglist():
if not isinstance(a, Const) and a not in self.short_seen:
self.add_op_to_short(self.short_boxes.producer(a), emit,
guards_needed)
@@ -497,7 +495,7 @@
if guards_needed and self.short_boxes.has_producer(op.result):
value_guards = self.getvalue(op.result).make_guards(op.result)
else:
- value_guards = []
+ value_guards = []
self.short.append(op)
self.short_seen[op.result] = True
@@ -517,7 +515,7 @@
if newop:
return newop.result
return None
-
+
def import_box(self, box, inputargs, short_jumpargs, jumpargs):
if isinstance(box, Const) or box in inputargs:
return
@@ -603,7 +601,7 @@
classbox =
self.getvalue(newop.result).get_constant_class(self.optimizer.cpu)
if not classbox or not
classbox.same_constant(target.assumed_classes[shop.result]):
raise InvalidLoop('The class of an opaque
pointer at the end ' +
- 'of the bridge does not mach
the class ' +
+ 'of the bridge does not mach
the class ' +
'it has at the start of the
target loop')
except InvalidLoop:
#debug_print("Inlining failed unexpectedly",
@@ -615,6 +613,7 @@
debug_stop('jit-log-virtualstate')
return False
+
class ValueImporter(object):
def __init__(self, unroll, value, op):
self.unroll = unroll
@@ -623,7 +622,8 @@
def import_value(self, value):
value.import_from(self.preamble_value, self.unroll.optimizer)
- self.unroll.add_op_to_short(self.op, False, True)
+ self.unroll.add_op_to_short(self.op, False, True)
+
class ExportedState(object):
def __init__(self, short_boxes, inputarg_setup_ops, exported_values):
diff --git a/rpython/jit/metainterp/virtualizable.py
b/rpython/jit/metainterp/virtualizable.py
--- a/rpython/jit/metainterp/virtualizable.py
+++ b/rpython/jit/metainterp/virtualizable.py
@@ -1,14 +1,12 @@
+from rpython.jit.metainterp import history
+from rpython.jit.metainterp.typesystem import deref, fieldType, arrayItem
+from rpython.jit.metainterp.warmstate import wrap, unwrap
+from rpython.rlib.unroll import unrolling_iterable
+from rpython.rtyper import rvirtualizable2
from rpython.rtyper.lltypesystem import lltype, llmemory
from rpython.rtyper.ootypesystem import ootype
-from rpython.rtyper.annlowlevel import cast_base_ptr_to_instance
from rpython.rtyper.rclass import IR_IMMUTABLE_ARRAY, IR_IMMUTABLE
-from rpython.rtyper import rvirtualizable2
-from rpython.rlib.unroll import unrolling_iterable
-from rpython.rlib.nonconst import NonConstant
-from rpython.jit.metainterp.typesystem import deref, fieldType, arrayItem
-from rpython.jit.metainterp import history
-from rpython.jit.metainterp.warmstate import wrap, unwrap
-from rpython.rlib.objectmodel import specialize
+
class VirtualizableInfo(object):
TOKEN_NONE = 0 # must be 0 -- see also x86.call_assembler
@@ -76,7 +74,7 @@
getlength = cpu.ts.getlength
getarrayitem = cpu.ts.getarrayitem
setarrayitem = cpu.ts.setarrayitem
- #
+
def read_boxes(cpu, virtualizable):
assert lltype.typeOf(virtualizable) == llmemory.GCREF
virtualizable = cast_gcref_to_vtype(virtualizable)
@@ -89,7 +87,7 @@
for i in range(getlength(lst)):
boxes.append(wrap(cpu, getarrayitem(lst, i)))
return boxes
- #
+
def write_boxes(virtualizable, boxes):
virtualizable = cast_gcref_to_vtype(virtualizable)
i = 0
@@ -104,7 +102,7 @@
setarrayitem(lst, j, x)
i = i + 1
assert len(boxes) == i + 1
- #
+
def write_from_resume_data_partial(virtualizable, reader, numb):
virtualizable = cast_gcref_to_vtype(virtualizable)
# Load values from the reader (see resume.py) described by
@@ -117,7 +115,7 @@
assert i >= 0
for ARRAYITEMTYPE, fieldname in unroll_array_fields_rev:
lst = getattr(virtualizable, fieldname)
- for j in range(getlength(lst)-1, -1, -1):
+ for j in range(getlength(lst) - 1, -1, -1):
i -= 1
assert i >= 0
x = reader.load_value_of_type(ARRAYITEMTYPE, numb.nums[i])
@@ -128,7 +126,7 @@
x = reader.load_value_of_type(FIELDTYPE, numb.nums[i])
setattr(virtualizable, fieldname, x)
return i
- #
+
def load_list_of_boxes(virtualizable, reader, numb):
virtualizable = cast_gcref_to_vtype(virtualizable)
# Uses 'virtualizable' only to know the length of the arrays;
@@ -140,10 +138,10 @@
boxes = [reader.decode_box_of_type(self.VTYPEPTR, numb.nums[i])]
for ARRAYITEMTYPE, fieldname in unroll_array_fields_rev:
lst = getattr(virtualizable, fieldname)
- for j in range(getlength(lst)-1, -1, -1):
+ for j in range(getlength(lst) - 1, -1, -1):
i -= 1
assert i >= 0
- box = reader.decode_box_of_type(ARRAYITEMTYPE,numb.nums[i])
+ box = reader.decode_box_of_type(ARRAYITEMTYPE,
numb.nums[i])
boxes.append(box)
for FIELDTYPE, fieldname in unroll_static_fields_rev:
i -= 1
@@ -152,7 +150,7 @@
boxes.append(box)
boxes.reverse()
return boxes
- #
+
def check_boxes(virtualizable, boxes):
virtualizable = cast_gcref_to_vtype(virtualizable)
# for debugging
@@ -168,7 +166,7 @@
assert getarrayitem(lst, j) == x
i = i + 1
assert len(boxes) == i + 1
- #
+
def get_index_in_array(virtualizable, arrayindex, index):
virtualizable = cast_gcref_to_vtype(virtualizable)
index += self.num_static_extra_boxes
@@ -180,7 +178,7 @@
index += getlength(lst)
j = j + 1
assert False, "invalid arrayindex"
- #
+
def get_array_length(virtualizable, arrayindex):
virtualizable = cast_gcref_to_vtype(virtualizable)
j = 0
@@ -188,16 +186,16 @@
if arrayindex == j:
lst = getattr(virtualizable, fieldname)
return getlength(lst)
- j = j + 1
+ j += 1
assert False, "invalid arrayindex"
- #
+
unroll_static_fields = unrolling_iterable(zip(FIELDTYPES,
static_fields))
unroll_array_fields = unrolling_iterable(zip(ARRAYITEMTYPES,
array_fields))
unroll_static_fields_rev = unrolling_iterable(
reversed(list(unroll_static_fields)))
- unroll_array_fields_rev = unrolling_iterable(
+ unroll_array_fields_rev = unrolling_iterable(
reversed(list(unroll_array_fields)))
self.read_boxes = read_boxes
self.write_boxes = write_boxes
@@ -291,7 +289,7 @@
def unwrap_virtualizable_box(self, virtualizable_box):
return virtualizable_box.getref(llmemory.GCREF)
-
+
def is_vtypeptr(self, TYPE):
return rvirtualizable2.match_virtualizable_type(TYPE, self.VTYPEPTR)
_______________________________________________
pypy-commit mailing list
[email protected]
http://mail.python.org/mailman/listinfo/pypy-commit
