Fix exponential parser time on sequence of [[[[#10439
Merged
sophiajt merged 2 commits intonushell:mainfrom Sep 20, 2023
Merged
Conversation
The old code first tried parsing the head of the table as a list and then after that it checked if it got more arguments. If it didn't, it throws away the previous result and tries to parse the whole thing as a list, which means we call parse_list_expression twice for each call to parse_table_expression, resulting in the exponential growth The fix is to simply check that we have all the arguments we need before parsing the head of the table, so we know that we will either call parse_list_expression only on sub-expressions or on the whole thing, never both. Fixes nushell#10438
0fea546 to
92f04e0
Compare
Contributor
Author
|
I've added a test now, but it will just freeze on regression instead of giving an error. I would like to add a timeout, but I don't know how to do that. Maybe it's only available as a global setting for the full testsuite? |
Contributor
|
Wow, nice catch |
hardfau1t
pushed a commit
to hardfau1t/nushell
that referenced
this pull request
Dec 14, 2023
<!-- if this PR closes one or more issues, you can automatically link the PR with them by using one of the [*linking keywords*](https://docs.github.com/en/issues/tracking-your-work-with-issues/linking-a-pull-request-to-an-issue#linking-a-pull-request-to-an-issue-using-a-keyword), e.g. - this PR should close #xxxx - fixes #xxxx you can also mention related issues, PRs or discussions! --> # Description <!-- Thank you for improving Nushell. Please, check our [contributing guide](../CONTRIBUTING.md) and talk to the core team before making major changes. Description of your pull request goes here. **Provide examples and/or screenshots** if your changes affect the user experience. --> Before this change, parsing `[[[[[[[[[[[[[[[[[[[[[[` would cause nushell to consume several gigabytes of memory, now it should be linear in time. The old code first tried parsing the head of the table as a list and then after that it checked if it got more arguments. If it didn't, it throws away the previous result and tries to parse the whole thing as a list, which means we call `parse_list_expression` twice for each call to `parse_table_expression`, resulting in the exponential growth The fix is to simply check that we have all the arguments we need before parsing the head of the table, so we know that we will either call parse_list_expression only on sub-expressions or on the whole thing, never both. Fixes nushell#10438 # User-Facing Changes Should give a noticable speedup when typing a sequence of `[[[[[[` open brackets <!-- List of all changes that impact the user experience here. This helps us keep track of breaking changes. --> # Tests + Formatting I would like to add tests, but I'm not sure how to do that without crashing CI with OOM on regression - [x] Don't forget to add tests that cover your changes. - [x] `cargo fmt --all -- --check` to check standard code formatting (`cargo fmt --all` applies these changes) - [x] `cargo clippy --workspace -- -D warnings -D clippy::unwrap_used` to check that you're using the standard code style - [x] `cargo test --workspace` to check that all tests pass (on Windows make sure to [enable developer mode](https://learn.microsoft.com/en-us/windows/apps/get-started/developer-mode-features-and-debugging)) - [x] `cargo run -- -c "use std testing; testing run-tests --path crates/nu-std"` to run the tests for the standard library <!-- > **Note** > from `nushell` you can also use the `toolkit` as follows > ```bash > use toolkit.nu # or use an `env_change` hook to activate it automatically > toolkit check pr > ``` --> # After Submitting If your PR had any user-facing changes, update [the documentation](https://github.com/nushell/nushell.github.io) after the PR is merged, if necessary. This will help us keep the docs up to date.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Description
Before this change, parsing
[[[[[[[[[[[[[[[[[[[[[[would cause nushell to consume several gigabytes of memory, now it should be linear in time.The old code first tried parsing the head of the table as a list and then after that it checked if it got more arguments. If it didn't, it throws away the previous result and tries to parse the whole thing as a list, which means we call
parse_list_expressiontwice for each call toparse_table_expression, resulting in the exponential growthThe fix is to simply check that we have all the arguments we need before parsing the head of the table, so we know that we will either call parse_list_expression only on sub-expressions or on the whole thing, never both.
Fixes #10438
User-Facing Changes
Should give a noticable speedup when typing a sequence of
[[[[[[open bracketsTests + Formatting
I would like to add tests, but I'm not sure how to do that without crashing CI with OOM on regression
cargo fmt --all -- --checkto check standard code formatting (cargo fmt --allapplies these changes)cargo clippy --workspace -- -D warnings -D clippy::unwrap_usedto check that you're using the standard code stylecargo test --workspaceto check that all tests pass (on Windows make sure to enable developer mode)cargo run -- -c "use std testing; testing run-tests --path crates/nu-std"to run the tests for the standard libraryAfter Submitting
If your PR had any user-facing changes, update the documentation after the PR is merged, if necessary. This will help us keep the docs up to date.