Certain changes to anyOf will change internal sorting and produce huge diffs

[untitaker]

Before:

{
    "anyOf": [
        {"properties": {"foo": {}}},
        {"properties": {"type": {"const": "bar"}}}
    ]
}

After:

{
    "anyOf": [
        {
            "title": "replay_recording",
            "type": "object",
            "properties": {"foo": {}}
        },
        {"properties": {"type": {"const": "bar"}}}
    ]
}

Diff:

$ json-schema-diff /tmp/a /tmp/b
{"path":".<anyOf:0>","change":{"PropertyRemove":{"lhs_additional_properties":true,"removed":"foo"}},"is_breaking":false}
{"path":".<anyOf:0>","change":{"PropertyAdd":{"lhs_additional_properties":true,"added":"type"}},"is_breaking":true}
{"path":".<anyOf:1>","change":{"PropertyRemove":{"lhs_additional_properties":true,"removed":"type"}},"is_breaking":false}
{"path":".<anyOf:1>","change":{"PropertyAdd":{"lhs_additional_properties":true,"added":"foo"}},"is_breaking":true}

[untitaker]

Observed in getsentry/sentry-kafka-schemas#135

[untitaker]

I wonder if we can just remove the internal sorting. It was supposed to deal with cases where a user just swaps the items in anyOf around. But when does that actually happen?

[6293]

Agree, we may still group subschemas by type though. Consider this, which I think is practical example:

{
  "lhs": {
    "anyOf": [
      {"properties": {"foo": {}}},
      {"properties": {"type": {"const": "bar"}}}
    ]
  },
  "rhs": {
    "anyOf": [
      { "type": "boolean" },
      {
        "title": "replay_recording",
        "type": "object",
        "properties": {"foo": {}}
      },
      {"properties": {"type": {"const": "bar"}}}
    ]
  }
}

Without grouping, {"properties": {"foo": {}}} would be compared against { "type": "boolean" }.

[untitaker]

i am starting to think that we actually want to invoke something like https://docs.rs/similar/latest/similar/index.html or https://crates.io/crates/json-structural-diff on the two sequences, instead of sorting and zipping

this would give us better signal as to which two JSON objects in each sequence are supposed to be compared to each other

then even things like inserting a new item at the beginning of the sequence works

[6293]

this would give us better signal as to which two JSON objects in each sequence are supposed to be compared to each other

We need to define what is considered to be "similar". I imagine something like this:

trait DiffScore {
    fn score(&mut self, rhs: &mut Self) -> usize;
}

impl DiffScore for SchemaObject {
    fn score(&mut self, rhs: &mut Self) -> usize {
        self.number().score(rhs.number()) + self.string().score(rhs.string()) + ...
    }
}

impl DiffScore for NumberValidation {
    fn score(&mut self, rhs: &mut Self) -> usize {
        let mut score = 0;
        if self.multiple_of != rhs.multiple_of {
            score += 1;
        }
        if self.minimum != rhs.minimum {
            score += 1;
        }
        if self.maximum != rhs.maximum {
            score += 1;
        }
        score
    }
}

Given the criterion function like this, we can calculate the matchings such that the sum of the score is minimum, using Hungarian method

[untitaker]

We need to define what is considered to be "similar"

We can do that, I was thinking of running a generic diff algorithm like json-structural-diff in hopes that it figures out similarity for us

Technically we can also determine the diff score by computing the hamming or levenshtein distance of the Debug output :D

[6293]

generic diff algorithm like json-structural-diff

If we measure diff based on json structures, we would need more thorough normalization. e.g.

{ "properties": { "foo": { "const": "value" } } }

to

{ "type": "object", "properties": { "foo": { "const": "value" } } }

or

{ "not": { "type": "string" } }

to

{ "anyOf": [{ "type": "object" }, { "type": "number" }, ...] }

I will figure out which approach (diff by json structure or our own score) is more convenient.