ChainMap should preserve order of underlying mappings

[rhettinger]

BPO	32792
Nosy	@rhettinger, @ned-deily, @serhiy-storchaka
PRs	bpo-32792: Preserve mapping order in ChainMap() #5586 [3.7] bpo-32792: Preserve mapping order in ChainMap() (GH-5586) #5617

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2018-02-11.09:29:52.688>
created_at = <Date 2018-02-08.08:46:17.632>
labels = ['3.7', '3.8', 'type-bug', 'library']
title = 'ChainMap should preserve order of underlying mappings'
updated_at = <Date 2018-02-11.09:29:52.687>
user = 'https://github.com/rhettinger'

bugs.python.org fields:

activity = <Date 2018-02-11.09:29:52.687>
actor = 'rhettinger'
assignee = 'none'
closed = True
closed_date = <Date 2018-02-11.09:29:52.688>
closer = 'rhettinger'
components = ['Library (Lib)']
creation = <Date 2018-02-08.08:46:17.632>
creator = 'rhettinger'
dependencies = []
files = []
hgrepos = []
issue_num = 32792
keywords = ['patch']
message_count = 10.0
messages = ['311817', '311822', '311852', '311969', '311984', '311985', '311987', '311988', '311989', '311990']
nosy_count = 3.0
nosy_names = ['rhettinger', 'ned.deily', 'serhiy.storchaka']
pr_nums = ['5586', '5617']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue32792'
versions = ['Python 3.7', 'Python 3.8']

[rhettinger]

This also applies to 3.6 because ChainMap can be used with OrderedDict.

[serhiy-storchaka]

An alternate implementation:

d = {}
for mapping in reversed(self.maps):
    d.update(mapping)
return iter(d)

Unfortunately both implementations work only with hashable keys. In general case mappings may be not hashtables.

[ned-deily]

See discussion on PR 5586 regarding backporting to 3.6.x.

[serhiy-storchaka]

Sorry, I was wrong. reversed() is not needed here.

The advantage of this implementation is that it can be faster because of iterating mappings in C code instead of Python code. But the side effect of it is that the iterator keeps references to all values. If this is not desirable, the code can be written something like:

    return iter(dict.fromkeys(itertools.chain.from_iterable(self.maps)))

[rhettinger]

New changeset 3793f95 by Raymond Hettinger in branch 'master':
bpo-32792: Preserve mapping order in ChainMap() (GH-5586)
3793f95

[serhiy-storchaka]

On PR 5586 we discussed reverting the order of the iteration by mappings. There are reasons of doing this. But this adds a subtle behavior change. Currently list(ChainMap({1: int}, {1.0: float})) returns [1]. With reversed() it will return [1.0]. This change LGTM.

[serhiy-storchaka]

The code in msg311969 doesn't reuse hash values. The following implementations do this:

return iter({**m for m in reversed(self.maps)})

or, without keeping reverences to values:

return iter(list({**m for m in reversed(self.maps)}))

[rhettinger]

New changeset 170b3f7 by Raymond Hettinger (Miss Islington (bot)) in branch '3.7':
bpo-32792: Preserve mapping order in ChainMap() (GH-5586) (#GH-5617)
170b3f7

[rhettinger]

The code in msg311969 doesn't reuse hash values.

That doesn't make sense. The dict.update() method reuses the hashes of the input mappings when possible.

    >>> from collections import ChainMap
    >>> class Int(int):
            def __hash__(self):
                    print(f'Hashing {self}', file=sys.stderr)
                    return int.__hash__(self)

            
    >>> import sys
    >>> d = { Int(1): 'f1', Int(2): 'f2' }
    Hashing 1
    Hashing 2
    >>> e = { Int(1): 's1', Int(3): 's3' }
    Hashing 1
    Hashing 3
    >>> c = ChainMap(d, e)
    >>> list(c)                     # Note, no calls to hash() were made
    [1, 3, 2]

[serhiy-storchaka]

I referred to msg311969, not msg311822.