Subject: [Cbor] Maps used as keys?

From: Brian E Carpenter <[email-masked]>
Date: Sun, 3 Dec 2017 15:15:31 +1300

Hi,

I have a question about this CDDL fragment:

   objective-value  /= { 1*elements }
   elements        //= ( @rfcXXXX: { 1*relement } )

   relement  = ( relement-codepoint => relement-value )
   relement-codepoint = uint 
   relement-value     = any
   relement-codepoint /= {
        ?( &(sender-loop-count:1) => 1..255 ),
        ?( &(srv-element:2) => tstr ),
       }

This validates with the Ruby tool and it can generate:

 {"@rfcXXXX": {4224: "toe",
               {1: 225}: "tic",
               2: "tac",
               {1: 36, 2: "toe"}: "tic"
              }
 }

I suspect that the CDDL ABNF allows this via
  memberkey = type1 S "=>"
since type1 covers anything.

Does CBOR allow a map as a key in another map?

However, that is a completely unacceptable construct in Python
("TypeError: unhashable type: 'dict'"); in other words Python
cannot use a map (dictionary) as a key in another map, and I
completely understand that.

What's the ground truth here?

    Brian

---

From: Carsten Bormann <[email-masked]>
Date: Sun, 3 Dec 2017 11:30:26 +0100

Hi Brian,

> Does CBOR allow a map as a key in another map?

Yes.
Any data item can be used as a map key.

> completely understand that.

Using mutable data structures as map keys is somewhat icky in a hashed map implementation.
Strictly speaking, you would need to re-hash a key each time it is changed (muted) internally; but how does the map know that this has been done?

JavaScript only allows strings (which are immutable in Javascript) as keys in “Object”s.
Since that is limiting, it now also has “Map”s.
However, indexing JavaScript “Map"s is by === (identity, not equality, with the weird exception that +0 and -0 are the same map key), so this punts on the problem that Python is apparently trying to avoid.

Grüße, Carsten

---

From: Brian E Carpenter <[email-masked]>
Date: Mon, 4 Dec 2017 08:06:23 +1300

> Any data item can be used as a map key.

Thanks. That was what the ABNF seemed to say.
 
> Strictly speaking, you would need to re-hash a key each time it is changed (muted) internally; but how does the map know that this has been done?

Exactly. The hash needs to be invariant, but it can't be.

> However, indexing JavaScript “Map"s is by === (identity, not equality, with the weird exception that +0 and -0 are the same map key), so this punts on the problem that Python is apparently trying t…

So this suggests to me that while legal, this is a CBOR feature that has
serious issues if you try to use it in interoperable code. I wonder what
Python cbor.loads() would do with such a CBOR fragment?

<pause for testing**>

It crashes with "TypeError: unhashable type: 'dict'" of course.

** I converted my fragment to valid CBOR using diag2cbor, then read it
into Python.

How does Ruby avoid this problem? It seems pretty much unfixable for Python.

Regards
    Brian

---

From: Carsten Bormann <[email-masked]>
Date: Sun, 3 Dec 2017 21:16:36 +0100

On Dec 3, 2017, at 20:06, Brian E Carpenter <[email-masked]> wrote:
> serious issues if you try to use it in interoperable code.

This sounds more like a problem with the Python implementation of CBOR you are using.

> I wonder what

That’s not what it should be doing.
It should be creating some frozen (immutable) data structure that *can* be used as a key, or define its own map type that can use more general keys.

(If the generic data model of CBOR has corners that a generic CBOR decoder can’t represent, a generic implementation should be defining appropriate data structures.  E.g., cbor-ruby defines its own CBOR::Tagged and CBOR::Simple for Tags and Simple values not already supported by the language.  Of course, there are some weird cases — Ruby does not distinguish +0.0 and -0.0 as map keys, so strictly speaking cbor-ruby should define a CBOR::MinusZero or some such for this, but it doesn't.)

> How does Ruby avoid this problem? It seems pretty much unfixable for Python.

Mutable map keys are not disallowed by Ruby — you just have to live with the (inconsistent) consequences if you do change them in place.
(One of the many places where the philosophical differences between Ruby and Python are coming out in plain view.) 

Grüße, Carsten

---

From: Brian E Carpenter <[email-masked]>
Date: Mon, 4 Dec 2017 16:03:33 +1300

> (If the generic data model of CBOR has corners that a generic CBOR decoder can’t represent, a generic implementation should be defining appropriate data structures.  E.g., cbor-ruby defines its own…

Both the cbor packages I've found for Python have this problem.  I'm not even sure I know how to explain it in Pythonic language in a bug report; you're asking Pythonistas to think the unthinkable :-).

> Mutable map keys are not disallowed by Ruby — you just have to live with the (inconsistent) consequences if you do change them in place.

Right. And that's why I'm going to try hard to insist that we avoid this construct in the CBOR application in question (draft-eckert-anima-grasp-dnssd-00). I think the inconsistency makes this a poor design, regardless of the Python defect.

> (One of the many places where the philosophical differences between Ruby and Python are coming out in plain view.) 

You can of course make a hash out of a Python dictionary, as hash(str(my_dict)), but it isn't invariant when the dictionary is updated, so it doesn't strike me as very useful. (And this issue has consequences for the discussion of canonical ordering of maps.)

Thanks again
    Brian

---

From: Jeffrey Yasskin <[email-masked]>
Date: Mon, 04 Dec 2017 05:32:19 +0000

On Sun, Dec 3, 2017 at 7:03 PM Brian E Carpenter <
[email-masked]> wrote:

> >>> Strictly speaking, you would need to re-hash a key each time it is
> changed (muted) internally; but how does the map know that this has been
> done?
> >>
> >>> However, indexing JavaScript “Map"s is by === (identity, not equality,
> with the weird exception that +0 and -0 are the same map key), so this
> punts on the problem that Python is apparently trying to avoid.
> >>
> > It should be creating some frozen (immutable) data structure that *can*
> be used as a key, or define its own map type that can use more general keys.
> >
> > (If the generic data model of CBOR has corners that a generic CBOR
> decoder can’t represent, a generic implementation should be defining
> appropriate data structures.  E.g., cbor-ruby defines its own CBOR::Tagged
> and CBOR::Simple for Tags and Simple values not already supported by the
> language.  Of course, there are some weird cases — Ruby does not
> distinguish +0.0 and -0.0 as map keys, so strictly speaking cbor-ruby
> should define a CBOR::MinusZero or some such for this, but it doesn't.)
> >
>
> Both the cbor packages I've found for Python have this problem.  I'm not
> even sure I know how to explain it in Pythonic language in a bug report;
> you're asking Pythonistas to think the unthinkable :-).
>

Here are three possible ways to explain the idea of an immutable dictionary
to the theoretical Pythonista who doesn't understand the concept:

1. The language already has sets and frozensets, and multiple customized
dictionary types in the collections module. A frozendict is to a dict as a
frozenset is to a set.
2. namedtuples are basically frozen dictionaries plus an ordering on the
fields.
3. Any Python object is basically a dict with some custom methods, so any
immutable object is an immutable dict.

Jeffrey

---

From: Carsten Bormann <[email-masked]>
Date: Mon, 4 Dec 2017 08:42:49 +0100

> You can of course make a hash out of a Python dictionary, as hash(str(my_dict)), but it isn't invariant when the dictionary is updated, so it doesn't strike me as very useful. (And this issue has c…

Hmm.  CBOR is for the serialization of data.  Those data are immutable in nature while being exchanged.

The fact that the most suggestive mapping of the CBOR data types to Python data types is using mutable data structures, and that Python chooses to expose some limitations in the implementation of these data structures as limitations in their allowable structure, doesn’t strike me as a very justifiable influence on the design of the CBOR data types.  (Note that the limitations exposed pertain to any use of non-trivial types as map keys, not just maps as map keys; a rather severe restriction.)

Python indeed happens to be a likely implementation language for protocols, many of which might be using data items as map keys that happen to be mapped to mutable dats structures (maps, arrays) in Python.  Maybe it is worth exploring ways to fill in that gap in the Python CBOR implementations.  Since I’m not very familiar with the preferred styles of Python programming, I can’t help a lot with that; is there something like an alist style data structure in Python that could be used for representing maps with those keys that cannot be put in a Python dict?

Grüße, Carsten

---

From: Carsten Bormann <[email-masked]>
Date: Mon, 4 Dec 2017 08:59:19 +0100

On Dec 4, 2017, at 06:32, Jeffrey Yasskin <[email-masked]> wrote:
> 
> Here are three possible ways to explain the idea of an immutable dictionary to the theoretical Pythonista who doesn't understand the concept:
> 
> 1. The language already has sets and frozensets, and multiple customized dictionary types in the collections module. A frozendict is to a dict as a frozenset is to a set.
> 2. namedtuples are basically frozen dictionaries plus an ordering on the fields.
> 3. Any Python object is basically a dict with some custom methods, so any immutable object is an immutable dict.

Right, but that approach may lead to a somewhat weird way of putting together CBOR data structures.
If non-trivial data need to be transformed into a less natural data structure in order to be usable as map keys, the limitation on the map turns into a transformation of the map key — when you extract that map key and use it somewhere else, it has a different shape than maybe is expected.
I’d prefer to do this in a way that doesn’t have non-local influences beyond overcoming the limitations of the map representation itself.

(In Ruby you can simply “freeze” a data structure before putting that in as a map key, preventing any surprises that you would get when that data structure is mutated while serving as a map key.  A frozen structure retains all the interfaces for data access, including proper equality.  Not sure it’s as simple as than in Python.)

Grüße, Carsten

---

From: Jeffrey Yasskin <[email-masked]>
Date: Mon, 04 Dec 2017 16:39:03 +0000

On Sun, Dec 3, 2017 at 11:59 PM Carsten Bormann <[email-masked]> wrote:

> > Here are three possible ways to explain the idea of an immutable
> dictionary to the theoretical Pythonista who doesn't understand the concept:
> >
> > 3. Any Python object is basically a dict with some custom methods, so
> any immutable object is an immutable dict.
>
> If non-trivial data need to be transformed into a less natural data
> structure in order to be usable as map keys, the limitation on the map
> turns into a transformation of the map key — when you extract that map key
> and use it somewhere else, it has a different shape than maybe is expected.
> I’d prefer to do this in a way that doesn’t have non-local influences
> beyond overcoming the limitations of the map representation itself.
>
> (In Ruby you can simply “freeze” a data structure before putting that in
> as a map key, preventing any surprises that you would get when that data
> structure is mutated while serving as a map key.  A frozen structure
> retains all the interfaces for data access, including proper equality.  Not
> sure it’s as simple as than in Python.)
>

I haven't used it, but https://pypi.python.org/pypi/frozendict/1.2 looks
like the right type to return from CBOR deserialization. For serialization,
it probably makes sense to use the interface in
https://docs.python.org/3/library/pickle.html#pickling-class-instances to
pull fields out of an object, rather than forcing folks to transform those
objects into a CBOR type first. Then immutable objects used as the keys in
a dict naturally work.

Jeffrey

---

From: Brian E Carpenter <[email-masked]>
Date: Tue, 5 Dec 2017 08:30:09 +1300

> Hmm.  CBOR is for the serialization of data.  Those data are immutable in nature while being exchanged.

Yes. That's why using frozen or 'pickled' versions of a Python data structure makes sense. You can even do this:

class mydict(dict):
    def __hash__(self):
        return hash(str(self))

and then any object of type mydict is a hashable dictionary. But as far as I can tell, you can't add a __hash__() method to a built-in type. 
> The fact that the most suggestive mapping of the CBOR data types to Python data types is using mutable data structures, and that Python chooses to expose some limitations in the implementation of t…

Well, it's a matter of taste, I guess. As you pointed out, there are consequences when the key changes, anyway, regardless of programming language.

> Python indeed happens to be a likely implementation language for protocols, many of which might be using data items as map keys that happen to be mapped to mutable dats structures (maps, arrays) in…

I will mull over what Jeffrey has said, although it's stretching my own Python skills a bit. I also need to look at another couple of CBOR implementations that I've never tried, to see if they have the same problem.

Ideally we'd have the Python implementers in this discussion.

Regards
   Brian

---

From: Toerless Eckert <[email-masked]>
Date: Mon, 4 Dec 2017 23:18:45 +0100

When i dynamically process data structures and need a map as a key, i would
use an (object) reference to it as the key to make it invariant.  But there are
no references in CBOR AFAIK, so if i used a reference to an object in multiple
parts of my compoint data structure, the CBOR encoding would likely end
up serializing the referenced structure (like a map) separately every time (waste).
Unless i come up with application workarounds (references = names, create a map of
names to object,...).

I can not remember if i have seen serialization libraries that solved this problem
well, but i have really only used perl with some XML serialization libraries in the distant
past, and i think they all ended up not being able to create serialization formats that
include references, but instead serialized referenced structures/objects
every time they encountered a reference to it. But i haven't looked into that
for a long time (which is obvious by the mentioning of "perl" instad of "python").

Toerless

On Mon, Dec 04, 2017 at 08:42:49AM +0100, Carsten Bormann wrote:
> >> Mutable map keys are not disallowed by Ruby ??? you just have to live with the (inconsistent) consequences if you do change them in place.
> > 
> The fact that the most suggestive mapping of the CBOR data types to Python data types is using mutable data structures, and that Python chooses to expose some limitations in the implementation of these data structures as limitations in their allowable structure, doesn???t strike me as a very justifiable influence on the design of the CBOR data types.  (Note that the limitations exposed pertain to any use of non-trivial types as map keys, not just maps as map keys; a rather severe restriction.)
> 
> Python indeed happens to be a likely implementation language for protocols, many of which might be using data items as map keys that happen to be mapped to mutable dats structures (maps, arrays) in Python.  Maybe it is worth exploring ways to fill in that gap in the Python CBOR implementations.  Since I???m not very familiar with the preferred styles of Python programming, I can???t help a lot with that; is there something like an alist style data structure in Python that could be used for representing maps with those keys that cannot be put in a Python dict?
> 
> Grüße, Carsten
> 
> _______________________________________________
> CBOR mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cbor