Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

fix(16.x.x.): avoid stack size limit in overlapping field rules as well as execute #4116

Closed

Conversation

JoviDeCroock
Copy link
Member

@JoviDeCroock JoviDeCroock commented Jun 19, 2024

Fixes #3938

This moves us from our recursion when we are in a fragment to discovering more referenced fragments to a stack-iterator based approach. The memory consumption might be slightly higher during validation now but this will stop us from crashing which is less desired I presume.

EDIT: found some bugs, working on it (fixed in 18f81bd)

Copy link

Hi @JoviDeCroock, I'm @github-actions bot happy to help you with this PR 👋

Supported commands

Please post this commands in separate comments and only one per comment:

  • @github-actions run-benchmark - Run benchmark comparing base and merge commits for this PR
  • @github-actions publish-pr-on-npm - Build package from this PR and publish it on NPM

@JoviDeCroock JoviDeCroock marked this pull request as draft June 19, 2024 07:50
@JoviDeCroock JoviDeCroock marked this pull request as ready for review June 19, 2024 07:58
@JoviDeCroock

This comment has been minimized.

Copy link

@github-actions run-benchmark

@JoviDeCroock Please, see benchmark results here: https://github.com/graphql/graphql-js/actions/runs/9579845798/job/26413168621#step:6:1

@JoviDeCroock
Copy link
Member Author

@yaacovCR applied your suggestion, thank you!

@yaacovCR
Copy link
Contributor

Does this approach get us to validating nested named fragments of any depth? What was the old limit, what is the new? We presumably have a maximum depth secondary to a stack limit in execution as well with respect to field collection…. Is that now comparable?

@JoviDeCroock
Copy link
Member Author

JoviDeCroock commented Jun 19, 2024

This validates nested named fragments as the second test does. I'm not aware of any stack depth limitations in the implementation nor in the spec, this makes it limitless basically so no more runtime crash.

The old limit was runtime dependent so i.e. 900 in Node vs 9100 in Chrome

@yaacovCR
Copy link
Contributor

I'm not aware of any stack depth limitations in the implementation nor in the spec, this makes it limitless basically so no more runtime crash.

There are none in the spec.

But our execution implementation uses synchronous recursion and so we should hit limits both in collect fields and in field execution:

Eg #4031

I am personally not quite sure what they are tbh. When I am no longer on mobile and have enough bandwidth, I can try to take a closer look at this validation algorithm, but at first glance, it seems with your change to actually not necessarily use recursion at all for the nested named fragments, as advertised, dissimilar to collect fields and therefore allow a deeper limit/no limit. I don’t think that’s a blocker to approval => just curious, perhaps it might make sense to do something similar within collect fields.

Co-Authored-By: yaacovCR <[email protected]>
@yaacovCR
Copy link
Contributor

yaacovCR commented Jun 19, 2024

I think this can also be merged into main

@JoviDeCroock
Copy link
Member Author

@yaacovCR you are right though, this still fails in execution d9c4bd3 I can look at this separately or as part of this PR, as you prefer

@yaacovCR
Copy link
Contributor

I would be fine with either. I suppose we might want @graphql/tsc to address whether it's OK to change the simple recursive algorithm from the spec into something iterative.

It is certainly valid according to the specification, but perhaps there is some benefit in preserving a closer correspondence for the reference implementation. That small benefit might have to be weighed against the practical costs for this library users.

If I had a vote, I would vote in favor!

@JoviDeCroock
Copy link
Member Author

@yaacovCR I've replaced it in 4407b55

@JoviDeCroock JoviDeCroock changed the title fix(16.x.x.): avoid stack size limit in overlapping field rules fix(16.x.x.): avoid stack size limit in overlapping field rules as well as execute Jun 19, 2024
Copy link
Contributor

@yaacovCR yaacovCR left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Is it possible to unify visited Fragment names set with the new encountered fragments collection?

@saihaj saihaj requested a review from a team June 19, 2024 18:03
@yaacovCR
Copy link
Contributor

Is it possible to unify visited Fragment names set with the new encountered fragments collection?

Thinking about this more, I don't think you can.

@yaacovCR
Copy link
Contributor

I think this can also be merged into main

@JoviDeCroock this seems like a straightforward fix that if approved should go both in v16.x and v17. It doesn't matter probably whether we start with merging into main or v16, but we should do both, right, and I guess in general for most things the idea would be to start with main and then backport as necessary. [An exception was the globalThis issue where we are not quite sure I think which direction we want to take for the next version.]

@yaacovCR
Copy link
Contributor

@yaacovCR I've replaced it in 4407b55

Just for the record, this will fix arbitrarily nested fragments at a single level => which is cool => but it's not like we can have arbitrarily deep queries, the completion algorithm within execution is still recursive, so we will hit a limit. This is I think fine, but just want to make explicit that we are not necessarily solving the issue in #4031 ....

@yaacovCR
Copy link
Contributor

@JoviDeCroock this seems like a straightforward fix

I think we have an ordering problem so it no longer seems so straightforward for the execution part.

@JoviDeCroock
Copy link
Member Author

@yaacovCR what impact would ordering have, I thought that the whole collectFields pass would mitigate any ordering issues 😅 that being said, in practice switching to shift over pop would make these go away I reckon.

Heyitsquoracom added a commit to Heyitsquoracom/graphql-js that referenced this pull request Jun 24, 2024
@yaacovCR
Copy link
Contributor

Preserving the serialized map ordering https://spec.graphql.org/draft/#sec-Serialized-Map-Ordering

I think this whole approach would cause all fragments to appear after fields, so I think that would also have to be fixed.

@JoviDeCroock
Copy link
Member Author

JoviDeCroock commented Jun 24, 2024

@yaacovCR the stack based depth first iterator of 43e36cc should resolve that

@JoviDeCroock JoviDeCroock force-pushed the avoid-stack-size-limit branch 2 times, most recently from b102391 to 43e36cc Compare June 25, 2024 12:30
@JoviDeCroock

This comment has been minimized.

Copy link

@github-actions run-benchmark

@JoviDeCroock Please, see benchmark results here: https://github.com/graphql/graphql-js/actions/runs/9684136411/job/26721184177#step:6:1

@JoviDeCroock
Copy link
Member Author

JoviDeCroock commented Jul 15, 2024

Closing this out due to the lack of real world scenarios where this will occur. This also changes the implementation of the spec where we rely on recursion in the spec text, the scenario of > 1000 deep fragment-spreading, ... seems unlikely. If it however becomes a more apparent issue we can re-open this PR.

@JoviDeCroock JoviDeCroock deleted the avoid-stack-size-limit branch July 15, 2024 11:42
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

RangeError: Maximum call stack size exceeded in OverlappingFieldsCanBeMergedRule
3 participants