feat(compiler): validate field merging using the Xing algorithm

[goto-bus-stop]

Current situation This is an offending query:

{
  root { ... on A { unrelated } }
  root { ... on B { overlapping } }
  root { ... on C { overlapping } }
}

Here, assume B.overlapping selects an Int!, and C.overlapping selects an Int. Clearly root.overlapping can either be Int! or Int, and so this must be an error. But previous versions of apollo-compiler do not report anything.

Cause The validation is implemented by drilling in from the top down. The first field it encounters is root. root is selected multiple times so we need to see if its subselections can merge. In main, we do this by comparing every subselection to the first subselection (... on A { unrelated }). Both the B and C subselections can be merged with A, as they don't select any conflicting fields.

Fix Comparing all selections of the same field, to the first occurrence of the same field is not enough, as other occurrences can conflict with each other but not with the first field. This PR uses a different algorithm that efficiently groups and compares all the relevant combinations of fields. https://tech.new-work.se/graphql-overlapping-fields-can-be-merged-fast-ea6e92e0a01

closes #819

[goto-bus-stop]

I think i now have a faithful implementation of https://tech.new-work.se/graphql-overlapping-fields-can-be-merged-fast-ea6e92e0a01, except the caching. I think that it's valid for the output type check and the same field name/arguments check to be ran linearly, just like we did before this change, because of the grouping work that's done beforehand and because the recursions are now independent. Both checks assert that the elements they compare are the same, and a == b && a == c implies b == c. Previously that was also true, but the grouping worked differently, and it could miss out on combinations because of that.

Without caching, we end up grouping most selection sets in exactly the same way twice. It should be simple to add but i want to add more tests to make sure I did it right.

[lrlna]

more tests sounds good! i'd also run this against the harness @garypen wrote to ensure correctness. do you think that with these changes we need to wait to rip out js validation out of the router and keep running the two implementations in parallel?

[goto-bus-stop]

I ran it through the new harness, not comparatively, but just to make sure that it doesn't report anything weird. I think the biggest risk with this change is that there could still be a false negative, like before, so I would like to continue to run it side by side in prod for a few days and make sure our previous false negatives have all gone away.

[lrlna]

that sounds good then - take it away!

[SimonSapin]

I made sure the XING blog post has a copy at https://web.archive.org/web/20240208084612/https://tech.new-work.se/graphql-overlapping-fields-can-be-merged-fast-ea6e92e0a01?gi=3e85e33327df

[goto-bus-stop]

Should add a test for the recursion limit here tomorrow morning.

[lrlna]

Now that the recursion tests are in, shall we merge?