Author: Armin Rigo <ar...@tunes.org>
Branch: dict-move-to-end
Changeset: r89926:8286c209d677
Date: 2017-02-04 20:17 +0100
http://bitbucket.org/pypy/pypy/changeset/8286c209d677/
Log: Annotation, and the case of last=True
diff --git a/rpython/annotator/unaryop.py b/rpython/annotator/unaryop.py
--- a/rpython/annotator/unaryop.py
+++ b/rpython/annotator/unaryop.py
@@ -14,7 +14,7 @@
SomeUnicodeCodePoint, SomeInstance, SomeBuiltin, SomeBuiltinMethod,
SomeFloat, SomeIterator, SomePBC, SomeNone, SomeTypeOf, s_ImpossibleValue,
s_Bool, s_None, s_Int, unionof, add_knowntypedata,
- SomeWeakRef, SomeUnicodeString, SomeByteArray)
+ SomeWeakRef, SomeUnicodeString, SomeByteArray, SomeOrderedDict)
from rpython.annotator.bookkeeper import getbookkeeper, immutablevalue
from rpython.annotator.binaryop import _clone ## XXX where to put this?
from rpython.annotator.binaryop import _dict_can_only_throw_keyerror
@@ -575,6 +575,13 @@
pair(self, s_key).delitem()
method_delitem_with_hash.can_only_throw = _dict_can_only_throw_keyerror
+class __extend__(SomeOrderedDict):
+
+ def method_move_to_end(self, s_key, s_last):
+ assert s_Bool.contains(s_last)
+ pair(self, s_key).delitem()
+ method_move_to_end.can_only_throw = _dict_can_only_throw_keyerror
+
@op.contains.register(SomeString)
@op.contains.register(SomeUnicodeString)
def contains_String(annotator, string, char):
diff --git a/rpython/rlib/objectmodel.py b/rpython/rlib/objectmodel.py
--- a/rpython/rlib/objectmodel.py
+++ b/rpython/rlib/objectmodel.py
@@ -934,6 +934,24 @@
return
d.delitem_with_hash(key, h)
+def _untranslated_move_to_end(d, key, last):
+ "NOT_RPYTHON"
+ value = d.pop(key)
+ if last:
+ d[key] = value
+ else:
+ items = d.items()
+ d.clear()
+ d[key] = value
+ d.update(items)
+
+@specialize.call_location()
+def move_to_end(d, key, last=True):
+ if not we_are_translated():
+ _untranslated_move_to_end(d, key, last)
+ return
+ d.move_to_end(key, last)
+
# ____________________________________________________________
def import_from_mixin(M, special_methods=['__init__', '__del__']):
diff --git a/rpython/rlib/test/test_objectmodel.py
b/rpython/rlib/test/test_objectmodel.py
--- a/rpython/rlib/test/test_objectmodel.py
+++ b/rpython/rlib/test/test_objectmodel.py
@@ -7,7 +7,7 @@
resizelist_hint, is_annotation_constant, always_inline, NOT_CONSTANT,
iterkeys_with_hash, iteritems_with_hash, contains_with_hash,
setitem_with_hash, getitem_with_hash, delitem_with_hash, import_from_mixin,
- fetch_translated_config, try_inline)
+ fetch_translated_config, try_inline, move_to_end)
from rpython.translator.translator import TranslationContext, graphof
from rpython.rtyper.test.tool import BaseRtypingTest
from rpython.rtyper.test.test_llinterp import interpret
@@ -679,6 +679,16 @@
assert f(29) == 0
interpret(f, [27])
+def test_rordereddict_move_to_end():
+ d = OrderedDict()
+ d['key1'] = 'val1'
+ d['key2'] = 'val2'
+ d['key3'] = 'val3'
+ move_to_end(d, 'key1')
+ assert d.items() == [('key2', 'val2'), ('key3', 'val3'), ('key1', 'val1')]
+ move_to_end(d, 'key1', last=False)
+ assert d.items() == [('key1', 'val1'), ('key2', 'val2'), ('key3', 'val3')]
+
def test_import_from_mixin():
class M: # old-style
def f(self):
diff --git a/rpython/rtyper/lltypesystem/rordereddict.py
b/rpython/rtyper/lltypesystem/rordereddict.py
--- a/rpython/rtyper/lltypesystem/rordereddict.py
+++ b/rpython/rtyper/lltypesystem/rordereddict.py
@@ -407,6 +407,15 @@
hop.exception_is_here()
hop.gendirectcall(ll_dict_delitem_with_hash, v_dict, v_key, v_hash)
+ def rtype_method_move_to_end(self, hop):
+ v_dict, v_key, v_last = hop.inputargs(
+ self, self.key_repr, lltype.Bool)
+ if not self.custom_eq_hash:
+ hop.has_implicit_exception(KeyError) # record that we know about
it
+ hop.exception_is_here()
+ hop.gendirectcall(ll_dict_move_to_end, v_dict, v_key, v_last)
+
+
class __extend__(pairtype(OrderedDictRepr, rmodel.Repr)):
def rtype_getitem((r_dict, r_key), hop):
@@ -542,18 +551,18 @@
ll_assert(False, "ll_call_insert_clean_function(): invalid lookup_fun")
assert False
-def ll_call_delete_by_entry_index(d, hash, i):
+def ll_call_delete_by_entry_index(d, hash, i, replace_with):
# only called from _ll_dict_del, whose @jit.look_inside_iff
# condition should control when we get inside here with the jit
fun = d.lookup_function_no & FUNC_MASK
if fun == FUNC_BYTE:
- ll_dict_delete_by_entry_index(d, hash, i, TYPE_BYTE)
+ ll_dict_delete_by_entry_index(d, hash, i, replace_with, TYPE_BYTE)
elif fun == FUNC_SHORT:
- ll_dict_delete_by_entry_index(d, hash, i, TYPE_SHORT)
+ ll_dict_delete_by_entry_index(d, hash, i, replace_with, TYPE_SHORT)
elif IS_64BIT and fun == FUNC_INT:
- ll_dict_delete_by_entry_index(d, hash, i, TYPE_INT)
+ ll_dict_delete_by_entry_index(d, hash, i, replace_with, TYPE_INT)
elif fun == FUNC_LONG:
- ll_dict_delete_by_entry_index(d, hash, i, TYPE_LONG)
+ ll_dict_delete_by_entry_index(d, hash, i, replace_with, TYPE_LONG)
else:
# can't be still FUNC_MUST_REINDEX here
ll_assert(False, "ll_call_delete_by_entry_index(): invalid lookup_fun")
@@ -814,7 +823,7 @@
@jit.look_inside_iff(lambda d, h, i: jit.isvirtual(d) and jit.isconstant(i))
def _ll_dict_del(d, hash, index):
- ll_call_delete_by_entry_index(d, hash, index)
+ ll_call_delete_by_entry_index(d, hash, index, DELETED)
d.entries.mark_deleted(index)
d.num_live_items -= 1
# clear the key and the value if they are GC pointers
@@ -1064,7 +1073,7 @@
# @jit.look_inside_iff condition should control when we get inside
# here with the jit
@jit.unroll_safe
-def ll_dict_delete_by_entry_index(d, hash, locate_index, T):
+def ll_dict_delete_by_entry_index(d, hash, locate_index, replace_with, T):
# Another simplified version of ll_dict_lookup() which locates a
# hashtable entry with the given 'index' stored in it, and deletes it.
# This *should* be safe against evil user-level __eq__/__hash__
@@ -1081,7 +1090,7 @@
i = (i << 2) + i + perturb + 1
i = i & mask
perturb >>= PERTURB_SHIFT
- indexes[i] = rffi.cast(T, DELETED)
+ indexes[i] = rffi.cast(T, replace_with)
# ____________________________________________________________
#
@@ -1416,3 +1425,35 @@
value = dic.entries[index].value
_ll_dict_del(dic, hash, index)
return value
+
+def ll_dict_move_to_end(d, key, last):
+ assert last #XXX
+
+ hash = d.keyhash(key)
+ old_index = d.lookup_function(d, key, hash, FLAG_LOOKUP)
+ if old_index < 0:
+ raise KeyError
+
+ if old_index == d.num_ever_used_items - 1:
+ return
+
+ # remove the entry at the old position
+ ENTRIES = lltype.typeOf(d.entries).TO
+ ENTRY = ENTRIES.OF
+ old_entry = d.entries[old_index]
+ key = old_entry.key
+ value = old_entry.value
+ d.entries.mark_deleted(old_index)
+ if ENTRIES.must_clear_key:
+ old_entry.key = lltype.nullptr(ENTRY.key.TO)
+ if ENTRIES.must_clear_value:
+ old_entry.value = lltype.nullptr(ENTRY.value.TO)
+
+ # note a corner case: it is possible that 'replace_with' is just too
+ # large to fit in the type T used so far for the index. But in that
+ # case, the list 'd.entries' is full, and the following call to
+ # _ll_dict_setitem_lookup_done() will necessarily reindex the dict.
+ # So in that case, this value of 'replace_with' should be ignored.
+ ll_call_delete_by_entry_index(d, hash, old_index,
+ replace_with = VALID_OFFSET + d.num_ever_used_items)
+ _ll_dict_setitem_lookup_done(d, key, value, hash, -1)
diff --git a/rpython/rtyper/test/test_rordereddict.py
b/rpython/rtyper/test/test_rordereddict.py
--- a/rpython/rtyper/test/test_rordereddict.py
+++ b/rpython/rtyper/test/test_rordereddict.py
@@ -1,7 +1,8 @@
import py
+import random
from collections import OrderedDict
-from hypothesis import settings
+from hypothesis import settings, given, strategies
from hypothesis.stateful import run_state_machine_as_test
from rpython.rtyper.lltypesystem import lltype, rffi
@@ -145,14 +146,18 @@
ll_d = rordereddict.ll_newdict(DICT)
rordereddict.ll_dict_setitem(ll_d, llstr("k"), 1)
rordereddict.ll_dict_setitem(ll_d, llstr("j"), 2)
- ITER = rordereddict.get_ll_dictiter(lltype.Ptr(DICT))
+ assert [hlstr(entry.key) for entry in self._ll_iter(ll_d)] == ["k",
"j"]
+
+ def _ll_iter(self, ll_d):
+ ITER = rordereddict.get_ll_dictiter(lltype.typeOf(ll_d))
ll_iter = rordereddict.ll_dictiter(ITER, ll_d)
ll_dictnext = rordereddict._ll_dictnext
- num = ll_dictnext(ll_iter)
- assert hlstr(ll_d.entries[num].key) == "k"
- num = ll_dictnext(ll_iter)
- assert hlstr(ll_d.entries[num].key) == "j"
- py.test.raises(StopIteration, ll_dictnext, ll_iter)
+ while True:
+ try:
+ num = ll_dictnext(ll_iter)
+ except StopIteration:
+ break
+ yield ll_d.entries[num]
def test_popitem(self):
DICT = self._get_str_dict()
@@ -337,6 +342,31 @@
num_nonfrees += (got > 0)
assert d.resize_counter <= idx.getlength() * 2 - num_nonfrees * 3
+ @given(strategies.lists(strategies.integers(min_value=1, max_value=5)))
+ def test_direct_move_to_end(self, lst):
+ DICT = self._get_int_dict()
+ ll_d = rordereddict.ll_newdict(DICT)
+ rordereddict.ll_dict_setitem(ll_d, 1, 11)
+ rordereddict.ll_dict_setitem(ll_d, 2, 22)
+ def content():
+ return [(entry.key, entry.value) for entry in self._ll_iter(ll_d)]
+ for case in lst:
+ if case == 1:
+ rordereddict.ll_dict_move_to_end(ll_d, 1, True)
+ assert content() == [(2, 22), (1, 11)]
+ elif case == 2:
+ rordereddict.ll_dict_move_to_end(ll_d, 2, True)
+ assert content() == [(1, 11), (2, 22)]
+ elif case == 3:
+ py.test.raises(KeyError, rordereddict.ll_dict_move_to_end,
+ ll_d, 3, True)
+ #elif case == 4:
+ # rordereddict.ll_dict_move_to_end(ll_d, 2, False)
+ # assert content() == [(2, 22), (1, 11)]
+ #elif case == 5:
+ # rordereddict.ll_dict_move_to_end(ll_d, 1, False)
+ # assert content() == [(1, 11), (2, 22)]
+
class TestRDictDirectDummyKey(TestRDictDirect):
class dummykeyobj:
@@ -369,6 +399,32 @@
res = self.interpret(func, [5])
assert res == 6
+ def test_move_to_end(self):
+ def func():
+ d1 = OrderedDict()
+ d1['key1'] = 'value1'
+ d1['key2'] = 'value2'
+ for i in range(20):
+ objectmodel.move_to_end(d1, 'key1')
+ assert d1.keys() == ['key2', 'key1']
+ objectmodel.move_to_end(d1, 'key2')
+ assert d1.keys() == ['key1', 'key2']
+ func()
+ self.interpret(func, [])
+
+ def test_move_to_beginning(self):
+ def func():
+ d1 = OrderedDict()
+ d1['key1'] = 'value1'
+ d1['key2'] = 'value2'
+ for i in range(20):
+ objectmodel.move_to_end(d1, 'key2', last=False)
+ assert d1.keys() == ['key2', 'key1']
+ objectmodel.move_to_end(d1, 'key1', last=False)
+ assert d1.keys() == ['key1', 'key2']
+ func()
+ self.interpret(func, [])
+
class ODictSpace(MappingSpace):
MappingRepr = rodct.OrderedDictRepr
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit
