Author: Maciej Fijalkowski <[email protected]>
Branch: rordereddict
Changeset: r67676:bdb7bae76f74
Date: 2013-10-29 11:40 +0200
http://bitbucket.org/pypy/pypy/changeset/bdb7bae76f74/
Log: finish porting
diff --git a/rpython/annotator/builtin.py b/rpython/annotator/builtin.py
--- a/rpython/annotator/builtin.py
+++ b/rpython/annotator/builtin.py
@@ -300,6 +300,10 @@
dictdef.dictkey.update_rdict_annotations(s_eqfn, s_hashfn)
return SomeDict(dictdef)
+def robjmodel_r_ordereddict(s_eqfn, s_hashfn):
+ dictdef = getbookkeeper().getdictdef(is_r_dict=True)
+ dictdef.dictkey.update_rdict_annotations(s_eqfn, s_hashfn)
+ return SomeOrderedDict(dictdef)
def robjmodel_hlinvoke(s_repr, s_llcallable, *args_s):
from rpython.rtyper import rmodel
@@ -359,6 +363,7 @@
BUILTIN_ANALYZERS[rpython.rlib.rarithmetic.longlongmask] = rarith_longlongmask
BUILTIN_ANALYZERS[rpython.rlib.objectmodel.instantiate] = robjmodel_instantiate
BUILTIN_ANALYZERS[rpython.rlib.objectmodel.r_dict] = robjmodel_r_dict
+BUILTIN_ANALYZERS[rpython.rlib.objectmodel.r_ordereddict] =
robjmodel_r_ordereddict
BUILTIN_ANALYZERS[OrderedDict] = lambda :
SomeOrderedDict(getbookkeeper().getdictdef())
BUILTIN_ANALYZERS[rpython.rlib.objectmodel.hlinvoke] = robjmodel_hlinvoke
BUILTIN_ANALYZERS[rpython.rlib.objectmodel.keepalive_until_here] =
robjmodel_keepalive_until_here
diff --git a/rpython/rlib/objectmodel.py b/rpython/rlib/objectmodel.py
--- a/rpython/rlib/objectmodel.py
+++ b/rpython/rlib/objectmodel.py
@@ -628,8 +628,11 @@
The functions key_eq() and key_hash() are used by the key comparison
algorithm."""
+ def _newdict(self):
+ return {}
+
def __init__(self, key_eq, key_hash, force_non_null=False):
- self._dict = {}
+ self._dict = self._newdict()
self.key_eq = key_eq
self.key_hash = key_hash
self.force_non_null = force_non_null
@@ -664,7 +667,7 @@
return dk.key, value
def copy(self):
- result = r_dict(self.key_eq, self.key_hash)
+ result = self.__class__(self.key_eq, self.key_hash)
result.update(self)
return result
@@ -700,6 +703,11 @@
def __hash__(self):
raise TypeError("cannot hash r_dict instances")
+class r_ordereddict(r_dict):
+ def _newdict(self):
+ from collections import OrderedDict
+
+ return OrderedDict()
class _r_dictkey(object):
__slots__ = ['dic', 'key', 'hash']
@@ -735,7 +743,7 @@
Function and staticmethod objects are duplicated, which means
that annotation will not consider them as identical to another
copy in another unrelated class.
-
+
By default, "special" methods and class attributes, with a name
like "__xxx__", are not copied unless they are "__init__" or
"__del__". The list can be changed with the optional second
diff --git a/rpython/rtyper/rbuiltin.py b/rpython/rtyper/rbuiltin.py
--- a/rpython/rtyper/rbuiltin.py
+++ b/rpython/rtyper/rbuiltin.py
@@ -734,13 +734,23 @@
hop.exception_cannot_occur()
r_dict = hop.r_result
cDICT = hop.inputconst(lltype.Void, r_dict.DICT)
- return hop.gendirectcall(ll_newdict, cDICT)
+ v_result = hop.gendirectcall(ll_newdict, cDICT)
+ v_eqfn = hop.inputarg(r_dict.r_rdict_eqfn, arg=0)
+ v_hashfn = hop.inputarg(r_dict.r_rdict_hashfn, arg=1)
+ if r_dict.r_rdict_eqfn.lowleveltype != lltype.Void:
+ cname = hop.inputconst(lltype.Void, 'fnkeyeq')
+ hop.genop('setfield', [v_result, cname, v_eqfn])
+ if r_dict.r_rdict_hashfn.lowleveltype != lltype.Void:
+ cname = hop.inputconst(lltype.Void, 'fnkeyhash')
+ hop.genop('setfield', [v_result, cname, v_hashfn])
+ return v_result
BUILTIN_TYPER[objectmodel.instantiate] = rtype_instantiate
BUILTIN_TYPER[isinstance] = rtype_builtin_isinstance
BUILTIN_TYPER[hasattr] = rtype_builtin_hasattr
BUILTIN_TYPER[objectmodel.r_dict] = rtype_r_dict
BUILTIN_TYPER[OrderedDict] = rtype_ordered_dict
+BUILTIN_TYPER[objectmodel.r_ordereddict] = rtype_ordered_dict
# _________________________________________________________________
# weakrefs
diff --git a/rpython/rtyper/test/test_rdict.py
b/rpython/rtyper/test/test_rdict.py
--- a/rpython/rtyper/test/test_rdict.py
+++ b/rpython/rtyper/test/test_rdict.py
@@ -594,42 +594,6 @@
res = self.interpret(g, [3])
assert res == 77
- def test_r_dict(self):
- class FooError(Exception):
- pass
- def myeq(n, m):
- return n == m
- def myhash(n):
- if n < 0:
- raise FooError
- return -n
- def f(n):
- d = r_dict(myeq, myhash)
- for i in range(10):
- d[i] = i*i
- try:
- value1 = d[n]
- except FooError:
- value1 = 99
- try:
- value2 = n in d
- except FooError:
- value2 = 99
- try:
- value3 = d[-n]
- except FooError:
- value3 = 99
- try:
- value4 = (-n) in d
- except FooError:
- value4 = 99
- return (value1 * 1000000 +
- value2 * 10000 +
- value3 * 100 +
- value4)
- res = self.interpret(f, [5])
- assert res == 25019999
-
def test_resize_during_iteration(self):
def func():
d = self.newdict()
@@ -706,30 +670,6 @@
res = self.interpret(func, [])
assert res in [5263, 6352]
- def test_dict_popitem_hash(self):
- def deq(n, m):
- return n == m
- def dhash(n):
- return ~n
- def func():
- d = r_dict(deq, dhash)
- d[5] = 2
- d[6] = 3
- k1, v1 = d.popitem()
- assert len(d) == 1
- k2, v2 = d.popitem()
- try:
- d.popitem()
- except KeyError:
- pass
- else:
- assert 0, "should have raised KeyError"
- assert len(d) == 0
- return k1*1000 + v1*100 + k2*10 + v2
-
- res = self.interpret(func, [])
- assert res in [5263, 6352]
-
def test_dict_pop(self):
def f(n, default):
d = self.newdict()
@@ -777,74 +717,10 @@
res = self.interpret(func, [6])
assert res == 0
- def test_deleted_entry_reusage_with_colliding_hashes(self):
- def lowlevelhash(value):
- p = rstr.mallocstr(len(value))
- for i in range(len(value)):
- p.chars[i] = value[i]
- return rstr.LLHelpers.ll_strhash(p)
-
- def func(c1, c2):
- c1 = chr(c1)
- c2 = chr(c2)
- d = self.newdict()
- d[c1] = 1
- d[c2] = 2
- del d[c1]
- return d[c2]
-
- char_by_hash = {}
- base = rdict.DICT_INITSIZE
- for y in range(0, 256):
- y = chr(y)
- y_hash = lowlevelhash(y) % base
- char_by_hash.setdefault(y_hash, []).append(y)
-
- x, y = char_by_hash[0][:2] # find a collision
-
- res = self.interpret(func, [ord(x), ord(y)])
- assert res == 2
-
- def func2(c1, c2):
- c1 = chr(c1)
- c2 = chr(c2)
- d = {}
- d[c1] = 1
- d[c2] = 2
- del d[c1]
- d[c1] = 3
- return d
-
- res = self.interpret(func2, [ord(x), ord(y)])
- for i in range(len(res.entries)):
- assert not (res.entries.everused(i) and not res.entries.valid(i))
-
- def func3(c0, c1, c2, c3, c4, c5, c6, c7):
- d = {}
- c0 = chr(c0) ; d[c0] = 1; del d[c0]
- c1 = chr(c1) ; d[c1] = 1; del d[c1]
- c2 = chr(c2) ; d[c2] = 1; del d[c2]
- c3 = chr(c3) ; d[c3] = 1; del d[c3]
- c4 = chr(c4) ; d[c4] = 1; del d[c4]
- c5 = chr(c5) ; d[c5] = 1; del d[c5]
- c6 = chr(c6) ; d[c6] = 1; del d[c6]
- c7 = chr(c7) ; d[c7] = 1; del d[c7]
- return d
-
- if rdict.DICT_INITSIZE != 8:
- py.test.skip("make dict tests more indepdent from initsize")
- res = self.interpret(func3, [ord(char_by_hash[i][0])
- for i in range(rdict.DICT_INITSIZE)])
- count_frees = 0
- for i in range(len(res.entries)):
- if not res.entries.everused(i):
- count_frees += 1
- assert count_frees >= 3
-
def test_dict_valid_resize(self):
# see if we find our keys after resize
def func():
- d = {}
+ d = self.newdict()
# fill it up
for i in range(10):
d[str(i)] = 0
@@ -939,25 +815,6 @@
assert self.interpret(func, [5]) == 123
assert self.interpret(func, [42]) == 321
- def test_nonnull_hint(self):
- def eq(a, b):
- return a == b
- def rhash(a):
- return 3
-
- def func(i):
- d = r_dict(eq, rhash, force_non_null=True)
- if not i:
- d[None] = i
- else:
- d[str(i)] = i
- return "12" in d, d
-
- llres = self.interpret(func, [12])
- assert llres.item0 == 1
- DICT = lltype.typeOf(llres.item1)
- assert sorted(DICT.TO.entries.TO.OF._flds) == ['f_hash', 'key',
'value']
-
def test_memoryerror_should_not_insert(self):
# This shows a misbehaviour that also exists in CPython 2.7, but not
# any more in CPython 3.3. The behaviour is that even if a dict
@@ -1160,6 +1017,149 @@
assert lltype.typeOf(res.item1) == lltype.typeOf(res.item2)
assert lltype.typeOf(res.item1) == lltype.typeOf(res.item3)
+ def test_r_dict(self):
+ class FooError(Exception):
+ pass
+ def myeq(n, m):
+ return n == m
+ def myhash(n):
+ if n < 0:
+ raise FooError
+ return -n
+ def f(n):
+ d = r_dict(myeq, myhash)
+ for i in range(10):
+ d[i] = i*i
+ try:
+ value1 = d[n]
+ except FooError:
+ value1 = 99
+ try:
+ value2 = n in d
+ except FooError:
+ value2 = 99
+ try:
+ value3 = d[-n]
+ except FooError:
+ value3 = 99
+ try:
+ value4 = (-n) in d
+ except FooError:
+ value4 = 99
+ return (value1 * 1000000 +
+ value2 * 10000 +
+ value3 * 100 +
+ value4)
+ res = self.interpret(f, [5])
+ assert res == 25019999
+
+ def test_dict_popitem_hash(self):
+ def deq(n, m):
+ return n == m
+ def dhash(n):
+ return ~n
+ def func():
+ d = r_dict(deq, dhash)
+ d[5] = 2
+ d[6] = 3
+ k1, v1 = d.popitem()
+ assert len(d) == 1
+ k2, v2 = d.popitem()
+ try:
+ d.popitem()
+ except KeyError:
+ pass
+ else:
+ assert 0, "should have raised KeyError"
+ assert len(d) == 0
+ return k1*1000 + v1*100 + k2*10 + v2
+
+ res = self.interpret(func, [])
+ assert res in [5263, 6352]
+
+ def test_nonnull_hint(self):
+ def eq(a, b):
+ return a == b
+ def rhash(a):
+ return 3
+
+ def func(i):
+ d = r_dict(eq, rhash, force_non_null=True)
+ if not i:
+ d[None] = i
+ else:
+ d[str(i)] = i
+ return "12" in d, d
+
+ llres = self.interpret(func, [12])
+ assert llres.item0 == 1
+ DICT = lltype.typeOf(llres.item1)
+ assert sorted(DICT.TO.entries.TO.OF._flds) == ['f_hash', 'key',
'value']
+
+ def test_deleted_entry_reusage_with_colliding_hashes(self):
+ def lowlevelhash(value):
+ p = rstr.mallocstr(len(value))
+ for i in range(len(value)):
+ p.chars[i] = value[i]
+ return rstr.LLHelpers.ll_strhash(p)
+
+ def func(c1, c2):
+ c1 = chr(c1)
+ c2 = chr(c2)
+ d = self.newdict()
+ d[c1] = 1
+ d[c2] = 2
+ del d[c1]
+ return d[c2]
+
+ char_by_hash = {}
+ base = rdict.DICT_INITSIZE
+ for y in range(0, 256):
+ y = chr(y)
+ y_hash = lowlevelhash(y) % base
+ char_by_hash.setdefault(y_hash, []).append(y)
+
+ x, y = char_by_hash[0][:2] # find a collision
+
+ res = self.interpret(func, [ord(x), ord(y)])
+ assert res == 2
+
+ def func2(c1, c2):
+ c1 = chr(c1)
+ c2 = chr(c2)
+ d = self.newdict()
+ d[c1] = 1
+ d[c2] = 2
+ del d[c1]
+ d[c1] = 3
+ return d
+
+ res = self.interpret(func2, [ord(x), ord(y)])
+ for i in range(len(res.entries)):
+ assert not (res.entries.everused(i) and not res.entries.valid(i))
+
+ def func3(c0, c1, c2, c3, c4, c5, c6, c7):
+ d = self.newdict()
+ c0 = chr(c0) ; d[c0] = 1; del d[c0]
+ c1 = chr(c1) ; d[c1] = 1; del d[c1]
+ c2 = chr(c2) ; d[c2] = 1; del d[c2]
+ c3 = chr(c3) ; d[c3] = 1; del d[c3]
+ c4 = chr(c4) ; d[c4] = 1; del d[c4]
+ c5 = chr(c5) ; d[c5] = 1; del d[c5]
+ c6 = chr(c6) ; d[c6] = 1; del d[c6]
+ c7 = chr(c7) ; d[c7] = 1; del d[c7]
+ return d
+
+ if rdict.DICT_INITSIZE != 8:
+ py.test.skip("make dict tests more indepdent from initsize")
+ res = self.interpret(func3, [ord(char_by_hash[i][0])
+ for i in range(rdict.DICT_INITSIZE)])
+ count_frees = 0
+ for i in range(len(res.entries)):
+ if not res.entries.everused(i):
+ count_frees += 1
+ assert count_frees >= 3
+
class TestStress:
def test_stress(self):
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
@@ -6,6 +6,7 @@
from rpython.rlib.rarithmetic import intmask
from rpython.rtyper.annlowlevel import llstr, hlstr
from rpython.rtyper.test.test_rdict import BaseTestRDict
+from rpython.rlib import objectmodel
def get_indexes(ll_d):
@@ -275,3 +276,64 @@
def test_memoryerror_should_not_insert(self):
py.test.skip("I don't want to edit this file on two branches")
+
+
+ def test_r_dict(self):
+ class FooError(Exception):
+ pass
+ def myeq(n, m):
+ return n == m
+ def myhash(n):
+ if n < 0:
+ raise FooError
+ return -n
+ def f(n):
+ d = objectmodel.r_ordereddict(myeq, myhash)
+ for i in range(10):
+ d[i] = i*i
+ try:
+ value1 = d[n]
+ except FooError:
+ value1 = 99
+ try:
+ value2 = n in d
+ except FooError:
+ value2 = 99
+ try:
+ value3 = d[-n]
+ except FooError:
+ value3 = 99
+ try:
+ value4 = (-n) in d
+ except FooError:
+ value4 = 99
+ return (value1 * 1000000 +
+ value2 * 10000 +
+ value3 * 100 +
+ value4)
+ res = self.interpret(f, [5])
+ assert res == 25019999
+
+ def test_dict_popitem_hash(self):
+ def deq(n, m):
+ return n == m
+ def dhash(n):
+ return ~n
+ def func():
+ d = objectmodel.r_ordereddict(deq, dhash)
+ d[5] = 2
+ d[6] = 3
+ k1, v1 = d.popitem()
+ assert len(d) == 1
+ k2, v2 = d.popitem()
+ try:
+ d.popitem()
+ except KeyError:
+ pass
+ else:
+ assert 0, "should have raised KeyError"
+ assert len(d) == 0
+ return k1*1000 + v1*100 + k2*10 + v2
+
+ res = self.interpret(func, [])
+ assert res in [5263, 6352]
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
