As a user/dev, I want to compare/diff/relate Candid values

Is your feature request related to a problem? Please describe.

When building CI workflows, we need a human-readable representation of how two Candid values relate when they are not equal.

This human-readable representation would be included in reports of CI failures (e.g., lists of "expected versus observed" test outputs).

To compute that representation meaningfully, we need some constructive math to define it.

Describe the solution you'd like

This issue proposes a new Rust crate, which would augment the existing candid crate with higher-level implementations of various relations over candid values and types.

Let's call it candid_relate.

It gives semantic operations over ASTs of Candid values and types, including:

• Structural comparison (in the sense of mo:base/Order.Order)
• Structural editing, with a representation of diffs/deltas.
• Equality checks, in a semantic sense that requires types (re-implement some semantics of Candid, but at a higher level of abstraction, with more debugging information when things "go wrong").

This crate is not essential for building candid services, but would be essential for any candid tool that tries to debug expected versus observed values of candid data.

Here's an example of some related uses, demonstrating diff, delta and equal, and how they inter-relate:

// suppose we have two Candid ASTs, and a type that classifies each:
let (x : candid::Ast, y : candid::Ast, t : candid::Type) = ... ;

// (note: candid values x and y each have a common candid super-type, t)
// At the common type, we can edit one value into the other
let d : candid_relate::Delta = candid_relate::diff(x, y, t);

// difference/delta is represented by d, and can be applied as follows:
let z = candid_relate::delta(x, d);

// equal at the common supertype t, but perhaps not generally:
assert_eq!( candid::equal(z, y, t) );

When two values are not equal, a CI script could use this crate to help pretty-print a report that summarizes ("usefully") how the two values differ, e.g., by implementing the Show trait, or something similar:

println!("{}", d)

Describe alternatives you've considered

• Standard equality test (gives limited insights when the answer is "false", hence this proposal)

Additional context

• This came up while trying to build useful tools (in Rust) for CI to run to generate reports, and reports about failures of IC services written in Motoko/Rust.

• Caching and cache repair: The proposed "incremental edits representation" is (potentially) related to a future effort that would make query results systematically incremental across the Internet Computer. Just as we prescribe a representation of data by designing Candid, the representation of edits to these values could also be shared/systematic/general.

Start by reviewing the existing candid crate APIs named in the proposal: Ast, Type, and equal. Define the scope and representation for the proposed candid_relate operations—structural comparison, diff/delta editing, semantic equality, and human-readable output—then verify that the resulting crate can transform one value into another and explain differences.