Author: Maciej Fijalkowski <[email protected]>
Branch: rordereddict
Changeset: r67669:9f44c1e921fa
Date: 2013-10-29 00:05 +0200
http://bitbucket.org/pypy/pypy/changeset/9f44c1e921fa/
Log: Provide OrderedDict implemention for RPython, stolen from rdict-
experiments-3 branch. Note that two new tests are skipped, because
rdict-experiments-3 branch has the official version of this file
diff --git a/rpython/annotator/binaryop.py b/rpython/annotator/binaryop.py
--- a/rpython/annotator/binaryop.py
+++ b/rpython/annotator/binaryop.py
@@ -6,7 +6,8 @@
import operator
from rpython.tool.pairtype import pair, pairtype
from rpython.annotator.model import SomeObject, SomeInteger, SomeBool, s_Bool
-from rpython.annotator.model import SomeString, SomeChar, SomeList, SomeDict
+from rpython.annotator.model import SomeString, SomeChar, SomeList, SomeDict,\
+ SomeOrderedDict
from rpython.annotator.model import SomeUnicodeCodePoint, SomeUnicodeString
from rpython.annotator.model import SomeTuple, SomeImpossibleValue,
s_ImpossibleValue
from rpython.annotator.model import SomeInstance, SomeBuiltin, SomeIterator
@@ -581,7 +582,8 @@
class __extend__(pairtype(SomeDict, SomeDict)):
def union((dic1, dic2)):
- return SomeDict(dic1.dictdef.union(dic2.dictdef))
+ assert dic1.__class__ == dic2.__class__
+ return dic1.__class__(dic1.dictdef.union(dic2.dictdef))
class __extend__(pairtype(SomeDict, SomeObject)):
@@ -840,6 +842,7 @@
_make_none_union('SomeString', 'no_nul=obj.no_nul, can_be_None=True')
_make_none_union('SomeUnicodeString', 'can_be_None=True')
_make_none_union('SomeList', 'obj.listdef')
+_make_none_union('SomeOrderedDict', 'obj.dictdef')
_make_none_union('SomeDict', 'obj.dictdef')
_make_none_union('SomeWeakRef', 'obj.classdef')
diff --git a/rpython/annotator/bookkeeper.py b/rpython/annotator/bookkeeper.py
--- a/rpython/annotator/bookkeeper.py
+++ b/rpython/annotator/bookkeeper.py
@@ -5,9 +5,10 @@
from __future__ import absolute_import
import sys, types, inspect, weakref
+from collections import OrderedDict
from rpython.flowspace.model import Constant
-from rpython.annotator.model import (
+from rpython.annotator.model import (SomeOrderedDict,
SomeString, SomeChar, SomeFloat, SomePtr, unionof, SomeInstance, SomeDict,
SomeBuiltin, SomePBC, SomeInteger, TLS, SomeAddress, SomeUnicodeCodePoint,
s_None, s_ImpossibleValue, SomeLLADTMeth, SomeBool, SomeTuple,
@@ -370,7 +371,7 @@
for e in x:
listdef.generalize(self.immutablevalue(e, False))
result = SomeList(listdef)
- elif tp is dict or tp is r_dict:
+ elif tp is dict or tp is r_dict or tp is OrderedDict:
if need_const:
key = Constant(x)
try:
@@ -412,7 +413,10 @@
dictdef.generalize_key(self.immutablevalue(ek, False))
dictdef.generalize_value(self.immutablevalue(ev, False))
dictdef.seen_prebuilt_key(ek)
- result = SomeDict(dictdef)
+ if tp is OrderedDict:
+ result = SomeOrderedDict(dictdef)
+ else:
+ result = SomeDict(dictdef)
elif tp is weakref.ReferenceType:
x1 = x()
if x1 is None:
diff --git a/rpython/annotator/builtin.py b/rpython/annotator/builtin.py
--- a/rpython/annotator/builtin.py
+++ b/rpython/annotator/builtin.py
@@ -2,11 +2,13 @@
Built-in functions.
"""
import sys
+from collections import OrderedDict
from rpython.annotator.model import (
SomeInteger, SomeObject, SomeChar, SomeBool, SomeString, SomeTuple, s_Bool,
SomeUnicodeCodePoint, SomeAddress, SomeFloat, unionof, SomeUnicodeString,
SomePBC, SomeInstance, SomeDict, SomeList, SomeWeakRef, SomeIterator,
+ SomeOrderedDict,
SomeByteArray, annotation_to_lltype, lltype_to_annotation,
ll_to_annotation, add_knowntypedata, s_ImpossibleValue,)
from rpython.annotator.bookkeeper import getbookkeeper
@@ -357,6 +359,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[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
BUILTIN_ANALYZERS[rpython.rtyper.lltypesystem.llmemory.cast_ptr_to_adr] =
llmemory_cast_ptr_to_adr
diff --git a/rpython/annotator/model.py b/rpython/annotator/model.py
--- a/rpython/annotator/model.py
+++ b/rpython/annotator/model.py
@@ -32,6 +32,7 @@
import inspect
import weakref
from types import BuiltinFunctionType, MethodType
+from collections import OrderedDict
import rpython
from rpython.tool import descriptor
@@ -355,6 +356,18 @@
else:
return '{...%s...}' % (len(const),)
+class SomeOrderedDict(SomeDict):
+ knowntype = OrderedDict
+
+ def method_copy(dct):
+ return SomeOrderedDict(dct.dictdef)
+
+ def method_update(dct1, dct2):
+ if s_None.contains(dct2):
+ return SomeImpossibleValue()
+ assert isinstance(dct2, SomeOrderedDict), "OrderedDict.update(dict)
not allowed"
+ dct1.dictdef.union(dct2.dictdef)
+
class SomeIterator(SomeObject):
"Stands for an iterator returning objects from a given container."
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
@@ -194,10 +194,11 @@
return True
-class DictRepr(AbstractDictRepr):
+class OrderedDictRepr(AbstractDictRepr):
def __init__(self, rtyper, key_repr, value_repr, dictkey, dictvalue,
- custom_eq_hash=None):
+ custom_eq_hash=None, force_non_null=False):
+ assert not force_non_null
self.rtyper = rtyper
self.finalized = False
self.DICT = lltype.GcForwardReference()
@@ -389,7 +390,7 @@
v_res = hop.gendirectcall(target, *v_args)
return self.recast_value(hop.llops, v_res)
-class __extend__(pairtype(DictRepr, rmodel.Repr)):
+class __extend__(pairtype(OrderedDictRepr, rmodel.Repr)):
def rtype_getitem((r_dict, r_key), hop):
v_dict, v_key = hop.inputargs(r_dict, r_dict.key_repr)
@@ -419,7 +420,7 @@
hop.exception_is_here()
return hop.gendirectcall(ll_dict_contains, v_dict, v_key)
-class __extend__(pairtype(DictRepr, DictRepr)):
+class __extend__(pairtype(OrderedDictRepr, OrderedDictRepr)):
def convert_from_to((r_dict1, r_dict2), v, llops):
# check that we don't convert from Dicts with
# different key/value types
diff --git a/rpython/rtyper/rbuiltin.py b/rpython/rtyper/rbuiltin.py
--- a/rpython/rtyper/rbuiltin.py
+++ b/rpython/rtyper/rbuiltin.py
@@ -1,3 +1,5 @@
+from collections import OrderedDict
+
from rpython.annotator import model as annmodel
from rpython.flowspace.model import Constant
from rpython.rlib import rarithmetic, objectmodel
@@ -726,10 +728,19 @@
raise TyperError("hasattr is only suported on a constant")
+def rtype_ordered_dict(hop):
+ from rpython.rtyper.lltypesystem.rordereddict import ll_newdict
+
+ hop.exception_cannot_occur()
+ r_dict = hop.r_result
+ cDICT = hop.inputconst(lltype.Void, r_dict.DICT)
+ return hop.gendirectcall(ll_newdict, cDICT)
+
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
# _________________________________________________________________
# weakrefs
diff --git a/rpython/rtyper/rdict.py b/rpython/rtyper/rdict.py
--- a/rpython/rtyper/rdict.py
+++ b/rpython/rtyper/rdict.py
@@ -4,8 +4,12 @@
class __extend__(annmodel.SomeDict):
+ def get_dict_repr(self):
+ from rpython.rtyper.lltypesystem.rdict import DictRepr
+
+ return DictRepr
+
def rtyper_makerepr(self, rtyper):
- from rpython.rtyper.lltypesystem.rdict import DictRepr
dictkey = self.dictdef.dictkey
dictvalue = self.dictdef.dictvalue
s_key = dictkey.s_value
@@ -16,7 +20,7 @@
rtyper.getrepr(dictkey.s_rdict_hashfn))
else:
custom_eq_hash = None
- return DictRepr(rtyper, lambda: rtyper.getrepr(s_key),
+ return self.get_dict_repr()(rtyper, lambda: rtyper.getrepr(s_key),
lambda: rtyper.getrepr(s_value), dictkey, dictvalue,
custom_eq_hash, force_non_null)
@@ -25,6 +29,11 @@
self.dictdef.dictvalue.dont_change_any_more = True
return (self.__class__, self.dictdef.dictkey, self.dictdef.dictvalue)
+class __extend__(annmodel.SomeOrderedDict):
+ def get_dict_repr(self):
+ from rpython.rtyper.lltypesystem.rordereddict import OrderedDictRepr
+
+ return OrderedDictRepr
class AbstractDictRepr(rmodel.Repr):
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
@@ -22,11 +22,11 @@
yield x
-class TestRdict(BaseRtypingTest):
-
+class BaseTestRDict(BaseRtypingTest):
def test_dict_creation(self):
def createdict(i):
- d = {'hello' : i}
+ d = self.newdict()
+ d['hello'] = i
return d['hello']
res = self.interpret(createdict, [42])
@@ -34,7 +34,8 @@
def test_dict_getitem_setitem(self):
def func(i):
- d = {'hello' : i}
+ d = self.newdict()
+ d['hello'] = i
d['world'] = i + 1
return d['hello'] * d['world']
res = self.interpret(func, [6])
@@ -42,7 +43,8 @@
def test_dict_getitem_keyerror(self):
def func(i):
- d = {'hello' : i}
+ d = self.newdict()
+ d['hello'] = i
try:
return d['world']
except KeyError:
@@ -52,7 +54,8 @@
def test_dict_del_simple(self):
def func(i):
- d = {'hello' : i}
+ d = self.newdict()
+ d['hello'] = i
d['world'] = i + 1
del d['hello']
return len(d)
@@ -61,7 +64,8 @@
def test_dict_clear(self):
def func(i):
- d = {'abc': i}
+ d = self.newdict()
+ d['abc'] = i
d['def'] = i+1
d.clear()
d['ghi'] = i+2
@@ -72,7 +76,8 @@
def test_empty_strings(self):
def func(i):
- d = {'' : i}
+ d = self.newdict()
+ d[''] = i
del d['']
try:
d['']
@@ -84,7 +89,8 @@
assert res == 1
def func(i):
- d = {'' : i}
+ d = self.newdict()
+ d[''] = i
del d['']
d[''] = i + 1
return len(d)
@@ -94,9 +100,10 @@
def test_dict_bool(self):
def func(i):
if i:
- d = {}
+ d = self.newdict()
else:
- d = {i: i+1}
+ d = self.newdict()
+ d[i] = i+1
if d:
return i
else:
@@ -106,17 +113,20 @@
def test_contains(self):
def func(x, y):
- d = {x: x+1}
+ d = self.newdict()
+ d[x] = x+1
return y in d
assert self.interpret(func, [42, 0]) == False
assert self.interpret(func, [42, 42]) == True
def test_contains_2(self):
- d = {'5': None, '7': None}
+ d = self.newdict()
+ d['5'] = None
+ d['7'] = None
def func(x):
return chr(x) in d
- #assert self.interpret(func, [ord('5')]) == True
- #assert self.interpret(func, [ord('6')]) == False
+ assert self.interpret(func, [ord('5')]) == True
+ assert self.interpret(func, [ord('6')]) == False
def func(n):
return str(n) in d
@@ -124,7 +134,7 @@
def test_dict_iteration(self):
def func(i, j):
- d = {}
+ d = self.newdict()
d['hello'] = i
d['world'] = j
k = 1
@@ -136,7 +146,7 @@
def test_dict_itermethods(self):
def func():
- d = {}
+ d = self.newdict()
d['hello'] = 6
d['world'] = 7
k1 = k2 = k3 = 1
@@ -151,19 +161,9 @@
res = self.interpret(func, [])
assert res == 42 + 42 + 42
- def test_two_dicts_with_different_value_types(self):
- def func(i):
- d1 = {}
- d1['hello'] = i + 1
- d2 = {}
- d2['world'] = d1
- return d2['world']['hello']
- res = self.interpret(func, [5])
- assert res == 6
-
def test_dict_get(self):
def func():
- dic = {}
+ dic = self.newdict()
x1 = dic.get('hi', 42)
dic['blah'] = 1 # XXX this triggers type determination
x2 = dic.get('blah', 2)
@@ -174,7 +174,7 @@
def test_dict_get_empty(self):
def func():
# this time without writing to the dict
- dic = {}
+ dic = self.newdict()
x1 = dic.get('hi', 42)
x2 = dic.get('blah', 2)
return x1 * 10 + x2
@@ -183,14 +183,14 @@
def test_dict_setdefault(self):
def f():
- d = {}
+ d = self.newdict()
d.setdefault('a', 2)
return d['a']
res = self.interpret(f, ())
assert res == 2
def f():
- d = {}
+ d = self.newdict()
d.setdefault('a', 2)
x = d.setdefault('a', -3)
return x
@@ -200,7 +200,9 @@
def test_dict_copy(self):
def func():
# XXX this does not work if we use chars, only!
- dic = {'ab':1, 'b':2}
+ dic = self.newdict()
+ dic['ab'] = 1
+ dic['b'] = 2
d2 = dic.copy()
ok = 1
for key in d2:
@@ -215,8 +217,12 @@
def test_dict_update(self):
def func():
- dic = {'ab':1000, 'b':200}
- d2 = {'b':30, 'cb':4}
+ dic = self.newdict()
+ dic['ab'] = 1000
+ dic['b'] = 200
+ d2 = self.newdict()
+ d2['b'] = 30
+ d2['cb'] = 4
dic.update(d2)
ok = len(dic) == 3
sum = ok
@@ -228,7 +234,9 @@
def test_dict_keys(self):
def func():
- dic = {' 4':1000, ' 8':200}
+ dic = self.newdict()
+ dic[' 4'] = 1000
+ dic[' 8'] = 200
keys = dic.keys()
return ord(keys[0][1]) + ord(keys[1][1]) - 2*ord('0') + len(keys)
res = self.interpret(func, ())#, view=True)
@@ -240,8 +248,11 @@
class A(Empty):
pass
def func():
- dic0 = {Empty(): 2}
- dic = {A(): 1, A(): 2}
+ dic0 = self.newdict()
+ dic0[Empty()] = 2
+ dic = self.newdict()
+ dic[A()] = 1
+ dic[A()] = 2
keys = dic.keys()
return (isinstance(keys[1], A))*2+(isinstance(keys[0],A))
res = self.interpret(func, [])
@@ -253,8 +264,11 @@
class A(Empty):
pass
def func():
- dic0 = {Empty(): 2}
- dic = {A(): 1, A(): 2}
+ dic0 = self.newdict()
+ dic0[Empty()] = 2
+ dic = self.newdict()
+ dic[A()] = 1
+ dic[A()] = 2
a = 0
for k in dic.iterkeys():
a += isinstance(k, A)
@@ -264,7 +278,9 @@
def test_dict_values(self):
def func():
- dic = {' 4':1000, ' 8':200}
+ dic = self.newdict()
+ dic[' 4'] = 1000
+ dic[' 8'] = 200
values = dic.values()
return values[0] + values[1] + len(values)
res = self.interpret(func, ())
@@ -274,7 +290,9 @@
class A:
pass
def func():
- dic = {1: A(), 2: A()}
+ dic = self.newdict()
+ dic[1] = A()
+ dic[2] = A()
vals = dic.values()
return (isinstance(vals[1], A))*2+(isinstance(vals[0],A))
res = self.interpret(func, [])
@@ -284,7 +302,9 @@
class A:
pass
def func():
- dic = {1: A(), 2: A()}
+ dic = self.newdict()
+ dic[1] = A()
+ dic[2] = A()
a = 0
for v in dic.itervalues():
a += isinstance(v, A)
@@ -300,8 +320,11 @@
class B(Empty):
pass
def func():
- dic0 = {Empty(): 2}
- dic = {B(): A(), B(): A()}
+ dic0 = self.newdict()
+ dic0[Empty()] = A()
+ dic = self.newdict()
+ dic[B()] = A()
+ dic[B()] = A()
items = dic.items()
b = 0
a = 0
@@ -320,8 +343,11 @@
class B(Empty):
pass
def func():
- dic0 = {Empty(): 2}
- dic = {B(): A(), B(): A()}
+ dic0 = self.newdict()
+ dic0[Empty()] = A()
+ dic = self.newdict()
+ dic[B()] = A()
+ dic[B()] = A()
b = 0
a = 0
for k, v in dic.iteritems():
@@ -333,7 +359,9 @@
def test_dict_items(self):
def func():
- dic = {' 4':1000, ' 8':200}
+ dic = self.newdict()
+ dic[' 4'] = 1000
+ dic[' 8'] = 200
items = dic.items()
res = len(items)
for key, value in items:
@@ -344,13 +372,17 @@
def test_dict_contains(self):
def func():
- dic = {' 4':1000, ' 8':200}
+ dic = self.newdict()
+ dic[' 4'] = 1000
+ dic[' 8'] = 200
return ' 4' in dic and ' 9' not in dic
res = self.interpret(func, ())
assert res is True
def test_dict_contains_with_constant_dict(self):
- dic = {'4':1000, ' 8':200}
+ dic = self.newdict()
+ dic['4'] = 1000
+ dic['8'] = 200
def func(i):
return chr(i) in dic
res = self.interpret(func, [ord('4')])
@@ -367,7 +399,9 @@
a = A()
a.d = None
if n > 0:
- a.d = {str(n): 1, "42": 2}
+ a.d = self.newdict()
+ a.d[str(n)] = 1
+ a.d["42"] = 2
del a.d["42"]
return negate(a.d)
res = self.interpret(func, [10])
@@ -379,7 +413,8 @@
def test_int_dict(self):
def func(a, b):
- dic = {12: 34}
+ dic = self.newdict()
+ dic[12] = 34
dic[a] = 1000
return dic.get(b, -123)
res = self.interpret(func, [12, 12])
@@ -403,7 +438,7 @@
def f():
a = A()
b = B()
- d = {}
+ d = self.newdict()
d[b] = 7
d[a] = 3
return len(d) + d[a] + d[b]
@@ -411,7 +446,9 @@
assert res == 12
def test_captured_get(self):
- get = {1:2}.get
+ d = self.newdict()
+ d[1] = 2
+ get = d.get
def f():
return get(1, 3)+get(2, 4)
res = self.interpret(f, [])
@@ -431,40 +468,21 @@
def f():
lst = [A()]
res1 = A() in lst
- d2 = {B(): None, B(): None}
+ d2 = self.newdict()
+ d2[B()] = None
+ d2[B()] = None
return res1+len(d2)
res = self.interpret(f, [])
assert res == 2
-
- def test_type_erase(self):
- class A(object):
- pass
- class B(object):
- pass
-
- def f():
- return {A(): B()}, {B(): A()}
-
- t = TranslationContext()
- s = t.buildannotator().build_types(f, [])
- rtyper = t.buildrtyper()
- rtyper.specialize()
-
- s_AB_dic = s.items[0]
- s_BA_dic = s.items[1]
-
- r_AB_dic = rtyper.getrepr(s_AB_dic)
- r_BA_dic = rtyper.getrepr(s_AB_dic)
-
- assert r_AB_dic.lowleveltype == r_BA_dic.lowleveltype
-
def test_identity_hash_is_fast(self):
class A(object):
pass
def f():
- return {A(): 1}
+ d = self.newdict()
+ d[A()] = 1
+ return d
t = TranslationContext()
s = t.buildannotator().build_types(f, [])
@@ -476,7 +494,7 @@
def test_tuple_dict(self):
def f(i):
- d = {}
+ d = self.newdict()
d[(1, 4.5, (str(i), 2), 2)] = 4
d[(1, 4.5, (str(i), 2), 3)] = 6
return d[(1, 4.5, (str(i), 2), i)]
@@ -486,9 +504,9 @@
def test_dict_of_dict(self):
def f(n):
- d = {}
+ d = self.newdict()
d[5] = d
- d[6] = {}
+ d[6] = self.newdict()
return len(d[n])
res = self.interpret(f, [5])
@@ -504,10 +522,9 @@
pass
def f(i):
- d = {
- A: 3,
- B: 4,
- }
+ d = self.newdict()
+ d[A] = 3
+ d[B] = 4
if i:
cls = A
else:
@@ -526,7 +543,9 @@
class B(A):
pass
- d = {(A, 3): 3, (B, 0): 4}
+ d = self.newdict()
+ d[(A, 3)] = 3
+ d[(B, 0)] = 4
def f(i):
if i:
@@ -553,7 +572,9 @@
return 42
return -1
def g(n):
- d = {1: n, 2: 2*n}
+ d = self.newdict()
+ d[1] = n
+ d[2] = 2*n
return f(d)
res = self.interpret(g, [3])
assert res == 6
@@ -566,7 +587,8 @@
return 42
return -1
def g(n):
- d = {1: n}
+ d = self.newdict()
+ d[1] = n
f(d)
return d[2]
res = self.interpret(g, [3])
@@ -610,7 +632,10 @@
def test_resize_during_iteration(self):
def func():
- d = {5: 1, 6: 2, 7: 3}
+ d = self.newdict()
+ d[5] = 1
+ d[6] = 2
+ d[7] = 3
try:
for key, value in d.iteritems():
d[key^16] = value*2
@@ -625,14 +650,21 @@
def test_change_during_iteration(self):
def func():
- d = {'a': 1, 'b': 2}
+ d = self.newdict()
+ d['a'] = 1
+ d['b'] = 2
for key in d:
d[key] = 42
return d['a']
assert self.interpret(func, []) == 42
def test_dict_of_floats(self):
- d = {3.0: 42, 3.1: 43, 3.2: 44, 3.3: 45, 3.4: 46}
+ d = self.newdict()
+ d[3.0] = 42
+ d[3.1] = 43
+ d[3.2] = 44
+ d[3.3] = 45
+ d[3.4] = 46
def fn(f):
return d[f]
@@ -643,7 +675,9 @@
for r_t in [r_uint, r_longlong, r_ulonglong]:
if r_t is r_int:
continue # for 64-bit platforms: skip r_longlong
- d = {r_t(2): 3, r_t(4): 5}
+ d = self.newdict()
+ d[r_t(2)] = 3
+ d[r_t(4)] = 5
def fn(x, y):
d[r_t(x)] = 123
return d[r_t(y)]
@@ -654,7 +688,7 @@
def test_dict_popitem(self):
def func():
- d = {}
+ d = self.newdict()
d[5] = 2
d[6] = 3
k1, v1 = d.popitem()
@@ -698,7 +732,7 @@
def test_dict_pop(self):
def f(n, default):
- d = {}
+ d = self.newdict()
d[2] = 3
d[4] = 5
if default == -1:
@@ -720,7 +754,7 @@
class A(object):
pass
def f(n):
- d = {}
+ d = self.newdict()
d[2] = A()
x = d.pop(n, None)
if x is None:
@@ -734,7 +768,8 @@
def test_dict_but_not_with_char_keys(self):
def func(i):
- d = {'h': i}
+ d = self.newdict()
+ d['h'] = i
try:
return d['hello']
except KeyError:
@@ -752,7 +787,7 @@
def func(c1, c2):
c1 = chr(c1)
c2 = chr(c2)
- d = {}
+ d = self.newdict()
d[c1] = 1
d[c2] = 2
del d[c1]
@@ -806,27 +841,6 @@
count_frees += 1
assert count_frees >= 3
- def test_dict_resize(self):
- # XXX we no longer automatically resize on 'del'. We need to
- # hack a bit in this test to trigger a resize by continuing to
- # fill the dict's table while keeping the actual size very low
- # in order to force a resize to shrink the table back
- def func(want_empty):
- d = {}
- for i in range(rdict.DICT_INITSIZE << 1):
- d[chr(ord('a') + i)] = i
- if want_empty:
- for i in range(rdict.DICT_INITSIZE << 1):
- del d[chr(ord('a') + i)]
- for i in range(rdict.DICT_INITSIZE << 3):
- d[chr(ord('A') - i)] = i
- del d[chr(ord('A') - i)]
- return d
- res = self.interpret(func, [0])
- assert len(res.entries) > rdict.DICT_INITSIZE
- res = self.interpret(func, [1])
- assert len(res.entries) == rdict.DICT_INITSIZE
-
def test_dict_valid_resize(self):
# see if we find our keys after resize
def func():
@@ -843,6 +857,212 @@
# ____________________________________________________________
+ def test_dict_of_addresses(self):
+ from rpython.rtyper.lltypesystem import llmemory
+ TP = lltype.Struct('x')
+ a = lltype.malloc(TP, flavor='raw', immortal=True)
+ b = lltype.malloc(TP, flavor='raw', immortal=True)
+
+ def func(i):
+ d = self.newdict()
+ d[llmemory.cast_ptr_to_adr(a)] = 123
+ d[llmemory.cast_ptr_to_adr(b)] = 456
+ if i > 5:
+ key = llmemory.cast_ptr_to_adr(a)
+ else:
+ key = llmemory.cast_ptr_to_adr(b)
+ return d[key]
+
+ assert self.interpret(func, [3]) == 456
+
+ def test_prebuilt_list_of_addresses(self):
+ from rpython.rtyper.lltypesystem import llmemory
+
+ TP = lltype.Struct('x', ('y', lltype.Signed))
+ a = lltype.malloc(TP, flavor='raw', immortal=True)
+ b = lltype.malloc(TP, flavor='raw', immortal=True)
+ c = lltype.malloc(TP, flavor='raw', immortal=True)
+ a_a = llmemory.cast_ptr_to_adr(a)
+ a0 = llmemory.cast_ptr_to_adr(a)
+ assert a_a is not a0
+ assert a_a == a0
+ a_b = llmemory.cast_ptr_to_adr(b)
+ a_c = llmemory.cast_ptr_to_adr(c)
+
+ d = self.newdict()
+ d[a_a] = 3
+ d[a_b] = 4
+ d[a_c] = 5
+ d[a0] = 8
+
+ def func(i):
+ if i == 0:
+ ptr = a
+ else:
+ ptr = b
+ return d[llmemory.cast_ptr_to_adr(ptr)]
+
+ py.test.raises(TypeError, self.interpret, func, [0])
+
+ def test_dict_of_voidp(self):
+ def func():
+ d = self.newdict()
+ handle = lltype.nullptr(rffi.VOIDP.TO)
+ # Use a negative key, so the dict implementation uses
+ # the value as a marker for empty entries
+ d[-1] = handle
+ return len(d)
+
+ assert self.interpret(func, []) == 1
+ from rpython.translator.c.test.test_genc import compile
+ f = compile(func, [])
+ res = f()
+ assert res == 1
+
+ def test_dict_with_SHORT_keys(self):
+ def func(x):
+ d = self.newdict()
+ d[rffi.cast(rffi.SHORT, 42)] = 123
+ d[rffi.cast(rffi.SHORT, -43)] = 321
+ return d[rffi.cast(rffi.SHORT, x)]
+
+ assert self.interpret(func, [42]) == 123
+ assert self.interpret(func, [2**16 - 43]) == 321
+
+ def test_dict_with_bool_keys(self):
+ def func(x):
+ d = self.newdict()
+ d[False] = 123
+ d[True] = 321
+ return d[x == 42]
+
+ 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
+ # insertion raises MemoryError, the new item is still inserted.
+ # If we catch the MemoryError, we can keep inserting new items until
+ # the dict table is completely full. Then the next insertion loops
+ # forever. This test only checks that after a MemoryError the
+ # new item was not inserted.
+ def _check_small_range(self, n):
+ if n >= 128:
+ raise MemoryError
+ return range(n)
+ original_check_range = lltype._array._check_range
+ try:
+ lltype._array._check_range = _check_small_range
+ #
+ def do_insert(d, i):
+ d[i] = i
+ def func():
+ d = self.newdict()
+ i = 0
+ while True:
+ try:
+ do_insert(d, i)
+ except MemoryError:
+ return (i in d)
+ i += 1
+ res = self.interpret(func, [])
+ assert res == 0
+ #
+ finally:
+ lltype._array._check_range = original_check_range
+
+ def test_dict_with_none_key(self):
+ def func(i):
+ d = self.newdict()
+ d[None] = i
+ return d[None]
+ res = self.interpret(func, [42])
+ assert res == 42
+
+
+class TestRDict(BaseTestRDict):
+ @staticmethod
+ def newdict():
+ return {}
+
+ def test_two_dicts_with_different_value_types(self):
+ def func(i):
+ d1 = {}
+ d1['hello'] = i + 1
+ d2 = {}
+ d2['world'] = d1
+ return d2['world']['hello']
+ res = self.interpret(func, [5])
+ assert res == 6
+
+ def test_type_erase(self):
+ class A(object):
+ pass
+ class B(object):
+ pass
+
+ def f():
+ d = {}
+ d[A()] = B()
+ d2 = {}
+ d2[B()] = A()
+ return d, d2
+
+ t = TranslationContext()
+ s = t.buildannotator().build_types(f, [])
+ rtyper = t.buildrtyper()
+ rtyper.specialize()
+
+ s_AB_dic = s.items[0]
+ s_BA_dic = s.items[1]
+
+ r_AB_dic = rtyper.getrepr(s_AB_dic)
+ r_BA_dic = rtyper.getrepr(s_AB_dic)
+
+ assert r_AB_dic.lowleveltype == r_BA_dic.lowleveltype
+
+
+ def test_dict_resize(self):
+ # XXX we no longer automatically resize on 'del'. We need to
+ # hack a bit in this test to trigger a resize by continuing to
+ # fill the dict's table while keeping the actual size very low
+ # in order to force a resize to shrink the table back
+ def func(want_empty):
+ d = self.newdict()
+ for i in range(rdict.DICT_INITSIZE << 1):
+ d[chr(ord('a') + i)] = i
+ if want_empty:
+ for i in range(rdict.DICT_INITSIZE << 1):
+ del d[chr(ord('a') + i)]
+ for i in range(rdict.DICT_INITSIZE << 3):
+ d[chr(ord('A') - i)] = i
+ del d[chr(ord('A') - i)]
+ return d
+ res = self.interpret(func, [0])
+ assert len(res.entries) > rdict.DICT_INITSIZE
+ res = self.interpret(func, [1])
+ assert len(res.entries) == rdict.DICT_INITSIZE
+
def test_opt_nullkeymarker(self):
def f():
d = {"hello": None}
@@ -940,145 +1160,6 @@
assert lltype.typeOf(res.item1) == lltype.typeOf(res.item2)
assert lltype.typeOf(res.item1) == lltype.typeOf(res.item3)
- def test_dict_of_addresses(self):
- from rpython.rtyper.lltypesystem import llmemory
- TP = lltype.Struct('x')
- a = lltype.malloc(TP, flavor='raw', immortal=True)
- b = lltype.malloc(TP, flavor='raw', immortal=True)
-
- def func(i):
- d = {}
- d[llmemory.cast_ptr_to_adr(a)] = 123
- d[llmemory.cast_ptr_to_adr(b)] = 456
- if i > 5:
- key = llmemory.cast_ptr_to_adr(a)
- else:
- key = llmemory.cast_ptr_to_adr(b)
- return d[key]
-
- assert self.interpret(func, [3]) == 456
-
- def test_prebuilt_list_of_addresses(self):
- from rpython.rtyper.lltypesystem import llmemory
-
- TP = lltype.Struct('x', ('y', lltype.Signed))
- a = lltype.malloc(TP, flavor='raw', immortal=True)
- b = lltype.malloc(TP, flavor='raw', immortal=True)
- c = lltype.malloc(TP, flavor='raw', immortal=True)
- a_a = llmemory.cast_ptr_to_adr(a)
- a0 = llmemory.cast_ptr_to_adr(a)
- assert a_a is not a0
- assert a_a == a0
- a_b = llmemory.cast_ptr_to_adr(b)
- a_c = llmemory.cast_ptr_to_adr(c)
-
- d = {a_a: 3, a_b: 4, a_c: 5}
- d[a0] = 8
-
- def func(i):
- if i == 0:
- ptr = a
- else:
- ptr = b
- return d[llmemory.cast_ptr_to_adr(ptr)]
-
- py.test.raises(TypeError, self.interpret, func, [0])
-
- def test_dict_of_voidp(self):
- def func():
- d = {}
- handle = lltype.nullptr(rffi.VOIDP.TO)
- # Use a negative key, so the dict implementation uses
- # the value as a marker for empty entries
- d[-1] = handle
- return len(d)
-
- assert self.interpret(func, []) == 1
- from rpython.translator.c.test.test_genc import compile
- f = compile(func, [])
- res = f()
- assert res == 1
-
- def test_dict_with_SHORT_keys(self):
- def func(x):
- d = {}
- d[rffi.cast(rffi.SHORT, 42)] = 123
- d[rffi.cast(rffi.SHORT, -43)] = 321
- return d[rffi.cast(rffi.SHORT, x)]
-
- assert self.interpret(func, [42]) == 123
- assert self.interpret(func, [2**16 - 43]) == 321
-
- def test_dict_with_bool_keys(self):
- def func(x):
- d = {}
- d[False] = 123
- d[True] = 321
- return d[x == 42]
-
- 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
- # insertion raises MemoryError, the new item is still inserted.
- # If we catch the MemoryError, we can keep inserting new items until
- # the dict table is completely full. Then the next insertion loops
- # forever. This test only checks that after a MemoryError the
- # new item was not inserted.
- def _check_small_range(self, n):
- if n >= 128:
- raise MemoryError
- return range(n)
- original_check_range = lltype._array._check_range
- try:
- lltype._array._check_range = _check_small_range
- #
- def do_insert(d, i):
- d[i] = i
- def func():
- d = {}
- i = 0
- while True:
- try:
- do_insert(d, i)
- except MemoryError:
- return (i in d)
- i += 1
- res = self.interpret(func, [])
- assert res == 0
- #
- finally:
- lltype._array._check_range = original_check_range
-
- def test_dict_with_none_key(self):
- def func(i):
- d = {None: i}
- return d[None]
- res = self.interpret(func, [42])
- assert res == 42
-
-
class TestStress:
def test_stress(self):
@@ -1193,3 +1274,4 @@
print 'current dict length:', referencelength
assert l_dict.num_items == referencelength
complete_check()
+
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,9 +1,11 @@
import py
+from collections import OrderedDict
from rpython.rtyper.lltypesystem import lltype, rffi
from rpython.rtyper.lltypesystem import rordereddict, rstr
from rpython.rlib.rarithmetic import intmask
from rpython.rtyper.annlowlevel import llstr, hlstr
+from rpython.rtyper.test.test_rdict import BaseTestRDict
def get_indexes(ll_d):
@@ -21,7 +23,7 @@
c += 1
return c
-
+
class TestRDictDirect(object):
dummykeyobj = None
dummyvalueobj = None
@@ -252,3 +254,24 @@
class TestRDictDirectDummyValue(TestRDictDirect):
class dummyvalueobj:
ll_dummy_value = -42
+
+class TestOrderedRDict(BaseTestRDict):
+ @staticmethod
+ def newdict():
+ return OrderedDict()
+
+ def test_two_dicts_with_different_value_types(self):
+ def func(i):
+ d1 = OrderedDict()
+ d1['hello'] = i + 1
+ d2 = OrderedDict()
+ d2['world'] = d1
+ return d2['world']['hello']
+ res = self.interpret(func, [5])
+ assert res == 6
+
+ def test_dict_with_SHORT_keys(self):
+ py.test.skip("I don't want to edit this file on two branches")
+
+ def test_memoryerror_should_not_insert(self):
+ py.test.skip("I don't want to edit this file on two branches")
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
