Supporting links as map keys

[warpfork]

Feature request: it should be possible to support links as map keys.

Using IPLD Schema syntax to describe it, for example, all of the following should be valid:

type MapWithLinkKeys {&Any:&Any}

type LinkSet {&Any:Unit}

type MapWithTypedLinkKeys {&Frob : Noz}
type Frob struct { ... details elided ... }
type Noz struct { ... details elided ... }

---

Why do we want this?

1. It generally feels like it "makes sense".

2. It very frequently comes up when someone wants to make "a set of blocks". That, in turn, appears for: building storage systems, caching and memoization systems, etc.

It's been requested by various users over time, and several times now, which is also very strong evidence that this is important. (I'm just being the messenger, by writing this issue up. It's been previously requested by Raul, Rod, Gozala (link), among others.)

---

How shall we do it (if we can do it)?

Discuss below.

[warpfork]

So, Okay, let's identify the elephant in the room immediately. This is impossible by our current definitions.

This is impossible because the definition of the IPLD Data Model states that map keys must be strings.

(This in turn is because if that wasn't the case, we'd be unable to come even close to calling DAG-JSON a well-supported codec (because JSON only supports string keys in maps), and we consider that important. We would also increase the scope of demands on an IPLD library significantly if we expanded this definition, and shouldn't do that lightly. (Diving deeper down the rabbithole: there are technicalities here... such as we actually have tacitly decided "strings SHOULD be UTF-8, but are often in fact just bytes", and some critical software most certainly relies in on that. However, we may want to strive to ignore that detail, to keep this issue at reasonable scope.))

And links (aka, CIDs) are not strings.

Okay. Can we make it possible anyway? Futz with the definitions just enough to make it fit?

I think so.

A possible solution is:

• expand the definition of the logical data model a bi: yes, the logical view can have links as keys. (N.b. this is demanding a distinction between the logical data model and the raw data model, so that that we can keep the definition and domain of the raw data model, as codecs need to worry about, the exact same.)
• and, lean on schemas to help us solve the gap: types could be used as a place to annotate how to represent a link as a string.

This seems reasonable, because we already use schemas to contain similar logic, and indeed to solve fancy problems about map keys -- for example, one can already use things like struct and union representation strategies that produce strings in order to then use those types as map keys:

# This is an example of an existing, valid IPLD Schema that puts complex data
# into a map key, by using a representation strategy that defines how the data morphs to a string.

type AB struct {
    a String
    b String
} representation stringjoin (":")

type CD union {
    | AB ("ab:")
    | Unit ("xx")
} representation stringprefix

The string "ab:1:2" matches the CD type in that schema: the JSON printout of its type level view would be {"AB":{"a":"1","b":"2"}}. But because it has a string representation, we can also freely add a map type of type FancyMap {CD:String} and it's a valid construction.

(Phew, prior art review done.)

So: can we do a similar thing for links? Would it make sense?

Let's try:

# This is *not* yet valid IPLD Schema syntax; I'm spitballing here.

type Foo struct { ... details elided ... }

type FooLink &Foo representation base58

type FooSet {FooLink:&Foo}

I think the above makes some logical sense. We use a the type declaration naming FooLink to attach a representation strategy to it. The representation strategy -- "base58" in this example -- says how we'll turn it into a string. That removes all ambiguity that would otherwise be a problem here: and it becomes perfectly clear how we can represent the describe structures in e.g. JSON.

This is the proposal that comes to my mind first for solving the scenario. It may not be the only one. Comments welcome.

[warpfork]

Downside of the above: means you have to write a whole dang schema to engage with this feature.

On the other hand: if we don't use schemas, we'd need to invent some other declarative system for describing the same things. Fundamentally, I don't think we can solve this without finding someplace to put the "how shall the link be encoded" design.