Commits

Brian Kearns committed 354042e Merge

merge default

Comments (0)

Files changed (5)

pypy/module/_bisect/interp_bisect.py

 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)
     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
     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

pypy/module/_bisect/test/test_bisect.py

         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

rpython/flowspace/framestate.py

+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):
     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
 PICKLE_TAGS = {}
 UNPICKLE_TAGS = {}
 
+
 def recursively_flatten(space, lst):
     from rpython.flowspace.flowcontext import SuspendedUnroller
     i = 0
             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

rpython/jit/metainterp/optimizeopt/unroll.py

-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
 
     opt.inline_short_preamble = inline_short_preamble
     opt.propagate_all_forward()
 
+
 class UnrollableOptimizer(Optimizer):
     def setup(self):
         self.importable_values = {}
     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
     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()
             # 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:
         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
                     return
 
         # Found nothing to jump to, emit a label instead
-        
+
         if self.short:
             # Construct our short preamble
             assert start_label
     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)
         #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()
 
         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
             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)
 
             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
                     #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
 
         # 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
                                       '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
                               '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
             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
         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)
         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
         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
                             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",
         debug_stop('jit-log-virtualstate')
         return False
 
+
 class ValueImporter(object):
     def __init__(self, unroll, value, op):
         self.unroll = unroll
 
     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):

rpython/jit/metainterp/virtualizable.py

+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
         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)
                 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
                     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
             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])
                 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;
             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
                 boxes.append(box)
             boxes.reverse()
             return boxes
-        #
+
         def check_boxes(virtualizable, boxes):
             virtualizable = cast_gcref_to_vtype(virtualizable)
             # for debugging
                     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
                 index += getlength(lst)
                 j = j + 1
             assert False, "invalid arrayindex"
-        #
+
         def get_array_length(virtualizable, arrayindex):
             virtualizable = cast_gcref_to_vtype(virtualizable)
             j = 0
                 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
 
     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)