classification
Title: ChainMap should preserve order of underlying mappings
Type: behavior Stage: resolved
Components: Library (Lib) Versions: Python 3.8, Python 3.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: ned.deily, rhettinger, serhiy.storchaka
Priority: normal Keywords: patch

Created on 2018-02-08 08:46 by rhettinger, last changed 2018-02-11 09:29 by rhettinger. This issue is now closed.

Pull Requests
URL Status Linked Edit
PR 5586 merged rhettinger, 2018-02-08 08:49
PR 5617 merged miss-islington, 2018-02-11 08:31
Messages (10)
msg311817 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2018-02-08 08:46
This also applies to 3.6 because ChainMap can be used with OrderedDict.
msg311822 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2018-02-08 09:24
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.
msg311852 - (view) Author: Ned Deily (ned.deily) * (Python committer) Date: 2018-02-08 21:32
See discussion on PR 5586 regarding backporting to 3.6.x.
msg311969 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2018-02-10 23:03
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)))
msg311984 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2018-02-11 08:30
New changeset 3793f95f98c3112ce447288a5bf9899eb9e35423 by Raymond Hettinger in branch 'master':
bpo-32792: Preserve mapping order in ChainMap() (GH-5586)
https://github.com/python/cpython/commit/3793f95f98c3112ce447288a5bf9899eb9e35423
msg311985 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2018-02-11 08:43
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.
msg311987 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2018-02-11 08:52
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)}))
msg311988 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2018-02-11 09:09
New changeset 170b3f79506480f78275a801822c9ff1283e16f2 by Raymond Hettinger (Miss Islington (bot)) in branch '3.7':
bpo-32792: Preserve mapping order in ChainMap() (GH-5586) (#GH-5617)
https://github.com/python/cpython/commit/170b3f79506480f78275a801822c9ff1283e16f2
msg311989 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2018-02-11 09:18
> 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]
msg311990 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2018-02-11 09:24
I referred to msg311969, not msg311822.
History
Date User Action Args
2018-02-11 09:29:52rhettingersetstatus: open -> closed
resolution: fixed
stage: patch review -> resolved
2018-02-11 09:24:34serhiy.storchakasetmessages: + msg311990
2018-02-11 09:18:22rhettingersetmessages: + msg311989
2018-02-11 09:09:59rhettingersetmessages: + msg311988
2018-02-11 08:52:52serhiy.storchakasetmessages: + msg311987
2018-02-11 08:43:07serhiy.storchakasetmessages: + msg311985
2018-02-11 08:31:41miss-islingtonsetpull_requests: + pull_request5427
2018-02-11 08:30:34rhettingersetmessages: + msg311984
2018-02-10 23:03:37serhiy.storchakasetmessages: + msg311969
2018-02-08 21:32:40ned.deilysetmessages: + msg311852
versions: - Python 3.6
2018-02-08 09:24:41serhiy.storchakasetmessages: + msg311822
2018-02-08 09:16:31serhiy.storchakasetnosy: + ned.deily, serhiy.storchaka
2018-02-08 08:49:29rhettingersetkeywords: + patch
stage: patch review
pull_requests: + pull_request5404
2018-02-08 08:46:17rhettingercreate