fix: checks subtyping relation when decoding reference types in Candid

[christoph-dfinity]

Description

Implements Candid subtyping and applies it when decoding reference types, to get up to par with the current Candid spec.

At a user-level this means we will fail early when decoding something like:

service { foo : (text) -> () } at an expected type of service { foo : (nat) -> () }

rather than decoding successfully and only failing when actually trying to make the call to foo later on in the code.

Follow-up to https://github.com/dfinity/agent-js/pull/981

How Has This Been Tested?

Additional unit tests

I also had to update one of the existing tests, as the binary value it was checking against actually had the wrong type

Reviewer notes

Unfortunately there are a few formatting changes unrelated to the change itself. These were produced in 3bedee41f13a9027e79c4420fd379d1cd35be18c by running

npm run -w packages/candid prettier:write

I added some tests, but it would probably be a good idea to write a parser for the test format in the spec and make sure this implementation conforms to it. I'd prefer doing that in another PR though. Up to you, dear reviewer, if we'd rather hold off on this change until then.

I added a global subtype cache that is reset before decoding a Candid message. As it's global and mutable, make sure to take a closer look if I messed up...

[github-actions[bot]]

size-limit report 📦

Path	Size
@dfinity/agent	72.21 KB (+0.84% 🔺)
@dfinity/candid	12.45 KB (+5.32% 🔺)
@dfinity/principal	4.21 KB (0%)
@dfinity/auth-client	50.31 KB (+0.39% 🔺)
@dfinity/assets	78.48 KB (+0.86% 🔺)
@dfinity/identity	47.79 KB (+0.25% 🔺)
@dfinity/identity-secp256k1	106.83 KB (+0.58% 🔺)

[christoph-dfinity]

Instead of using a global cache that needs to be reset carefully, how would you feel about passing the relation argument as the intial argument to decodeValue, along with the other bit of state, the Pipe. Then maybe Type could have a binary decodeValue(b, t) that dispatches to the new ternary decodeValue(relations, b, t) with a fresh, local cache?

I got started on this by changing the signature of Type.decodeValue to include an optional argument for the cache (optional so I wouldn't cause a breaking change to the API), but found that after changing a few call sites, it was much easier to miss passing the cache in some place than to reset the global cache "carefully" in one place. Unfortunately you can't overload like you proposed in TypeScript.

Also, constructing an object just to enumerate the fields of variants and records seems a little inefficient. Since the underlying _fields arrays (Array([string, Type]) appear to be sorted by hash of the string, can you just traverse the arrays directly, without the extra allocation? I guess that might mean recomputing he hashed before comparing the labels for relative order...

As discussed I decided to go for clarity over max performance in this case (matching the Rust implementation). I think it's very unlikely to make a noticeable difference (especially with the subtyping cache around).

I think I addressed the rest of your feedback. PTAL

[christoph-dfinity]

I'll set up some benchmarks before trying to think too hard about what's fast or slow here... Thanks for the review I think we're good to merge for now.

[christoph-dfinity]

@krpeacock Looks like I don't have the permissions to merge myself. Would you do me the honor?