[Python-Dev] PEP for new dictionary implementation

[Mark Shannon]

Terry Reedy wrote:
> On 2/8/2012 2:18 PM, Mark Shannon wrote:
> 
> A pretty clear draft PEP.
> 
>> Changes to repr() output and iteration order:
>> For most cases, this will be unchanged.
>> However for some split-table dictionaries the iteration order will
>> change.
>>
>> Neither of these cons should be a problem.
>> Modules which meddle with the internals of the dictionary
>> implementation are already broken and should be fixed to use the API.
> 
> So are modules that depend on set and dict iteration order and the 
> consequent representations.
> 
>> The iteration order of dictionaries was never defined and has always been
>> arbitrary; it is different for Jython and PyPy.
> 
> I am pretty sure iteration order has changed between CPython versions in 
> the past (and that when it did, people got caught). The documentation 
> for doctest has section 25.2.3.6. Warnings. It starts with this very issue!
> '''
> doctest is serious about requiring exact matches in expected output. If 
> even a single character doesn’t match, the test fails. This will 
> probably surprise you a few times, as you learn exactly what Python does 
> and doesn’t guarantee about output. For example, when printing a dict, 
> Python doesn’t guarantee that the key-value pairs will be printed in any 
> particular order, so a test like
> 
>  >>> foo()
> {"Hermione": "hippogryph", "Harry": "broomstick"}
> is vulnerable! One workaround is to do
> 
>  >>> foo() == {"Hermione": "hippogryph", "Harry": "broomstick"}
> True
> instead. Another is to do
> 
>  >>> d = sorted(foo().items())
>  >>> d
> [('Harry', 'broomstick'), ('Hermione', 'hippogryph')]
> '''
> (Object addresses and full-precision float representations are also 
> discussed.)
> 

There are a few things in the standard lib that rely on dict repr ordering:
http://bugs.python.org/issue13907
http://bugs.python.org/issue13909

I expect that the long-awaited fix to the hash-collision security issue
will expose a few more.

Version 2 of the new dict passes all these tests,
but that doesn't mean the tests are correct.

Cheers,
Mark.