aboutsummaryrefslogtreecommitdiff
path: root/crates/syntax
Commit message (Collapse)AuthorAgeFilesLines
* feature: massively improve performance for large filesAleksey Kladov2021-06-211-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This story begins in #8384, where we added a smart test for our syntax highting, which run the algorithm on synthetic files of varying length in order to guesstimate if the complexity is O(N^2) or O(N)-ish. The test turned out to be pretty effective, and flagged #9031 as a change that makes syntax highlighting accidentally quadratic. There was much rejoicing, for the time being. Then, lnicola asked an ominous question[1]: "Are we sure that the time is linear right now?" Of course it turned out that our sophisticated non-linearity detector *was* broken, and that our syntax highlighting *was* quadratic. Investigating that, many brave hearts dug deeper and deeper into the guts of rust-analyzer, only to get lost in a maze of traits delegating to traits delegating to macros. Eventually, matklad managed to peel off all layers of abstraction one by one, until almost nothing was left. In fact, the issue was discovered in the very foundation of the rust-analyzer -- in the syntax trees. Worse, it was not a new problem, but rather a well-know, well-understood and event (almost) well-fixed (!) performance bug. The problem lies within `SyntaxNodePtr` type -- a light-weight "address" of a node in a syntax tree [3]. Such pointers are used by rust-analyzer all other the place to record relationships between IR nodes and the original syntax. Internally, the pointer to a syntax node is represented by node's range. To "dereference" the pointer, you traverse the syntax tree from the root, looking for the node with the right range. The inner loop of this search is finding a node's child whose range contains the specified range. This inner loop was implemented by naive linear search over all the children. For wide trees, dereferencing a single `SyntaxNodePtr` was linear. The problem with wide trees though is that they contain a lot of nodes! And dereferencing pointers to all the nodes is quadratic in the size of the file! The solution to this problem is to speed up the children search -- rather than doing a linear lookup, we can use binary search to locate the child with the desired interval. Doing this optimization was one of the motivations (or rather, side effects) of #6857. That's why `rowan` grew the useful `child_or_token_at_range` method which does exactly this binary search. But looks like we've never actually switch to this method? Oups. Lesson learned: do not leave broken windows in the fundamental infra. Otherwise, you'll have to repeatedly re-investigate the issue, by digging from the top of the Everest down to the foundation! [1]: https://rust-lang.zulipchat.com/#narrow/stream/185405-t-compiler.2Frust-analyzer/topic/.60syntax_highlighting_not_quadratic.60.20failure/near/240811501 [2]: https://rust-lang.zulipchat.com/#narrow/stream/185405-t-compiler.2Frust-analyzer/topic/Syntax.20highlighting.20is.20quadratic [3]: https://rust-lang.zulipchat.com/#narrow/stream/185405-t-compiler.2Frust-analyzer/topic/Syntax.20highlighting.20is.20quadratic/near/243412392
* Don't insert imports outside of cfg attributed itemsLukas Wirth2021-06-181-1/+7
|
* Allow to disable import insertion on single path glob importsLukas Wirth2021-06-181-0/+9
|
* Fix parser tests for 1.53Lukas Wirth2021-06-1754-198/+198
|
* Create modules in correct directory for nested modules in move_module assistLukas Wirth2021-06-171-0/+8
|
* Highlight unsafe trait refs as unsafe only in impl blocks and definitionsLukas Wirth2021-06-151-0/+9
|
* internal: enforce no #[ignore] and no #[should_panic]Aleksey Kladov2021-06-152-2/+2
|
* clippy::manual_str_repeatMaan20032021-06-131-1/+1
|
* clippy::redudant_borrowMaan20032021-06-136-10/+10
|
* internal: cross-crate cov-marksAleksey Kladov2021-06-121-1/+1
|
* Update ungrammarJonas Schievink2021-06-1135-649/+769
|
* Fix edge case for ImportGranularity guessingLukas Wirth2021-06-081-1/+4
|
* Apply more clippy suggestions and update generatedClemens Wasser2021-06-032-5/+5
|
* Account for generics in extract_struct_from_enum_variantLukas Wirth2021-06-021-3/+2
|
* minor: remove debug printAleksey Kladov2021-05-311-1/+0
|
* Merge #9062bors[bot]2021-05-301-1/+1
|\ | | | | | | | | | | | | | | | | | | 9062: internal: Bump deps r=lnicola a=lnicola Fixes #9061 bors r+ Co-authored-by: Laurențiu Nicola <[email protected]>
| * Bump depsLaurențiu Nicola2021-05-301-1/+1
| |
* | Attribute completion is context awareLukas Wirth2021-05-271-0/+7
| |
* | generate match arms with todo!() as placeholder bodyDomantas Jadenkus2021-05-241-6/+15
|/
* Bump rustc_lexerLaurențiu Nicola2021-05-241-1/+1
|
* Add more docsAleksey Kladov2021-05-226-6/+17
|
* internal: replace AstTransformer with mutable syntax treesAleksey Kladov2021-05-224-54/+19
|
* Don't compare ast::Visibility by stringifyingLukas Tobias Wirth2021-05-201-0/+23
|
* fix: don't add extra whitespace around fieldsAleksey Kladov2021-05-171-0/+4
| | | | closes #8785
* internal: use mutable syntax trees when filling fieldsAleksey Kladov2021-05-162-98/+42
|
* internal: use mutable trees when filling match armsAleksey Kladov2021-05-162-126/+69
|
* Merge #8813bors[bot]2021-05-161-20/+61
|\ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 8813: Get some more array lengths! r=lf- a=lf- This is built on #8799 and thus contains its changes. I'll rebase it onto master when that one gets merged. It adds support for r-a understanding the length of: * `let a: [u8; 2] = ...` * `let a = b"aaa"` * `let a = [0u8; 4]` I have added support for getting the values of byte strings, which was not previously there. I am least confident in the correctness of this part and it probably needs some more tests, as we currently have only one test that exercised that part (!). Fixes #2922. Co-authored-by: Jade <[email protected]>
| * Support length for ByteStringsJade2021-05-131-20/+61
| | | | | | | | I am not confident that my added byte string parsing is right.
* | Attach comments to ast::ImplLukas Wirth2021-05-152-5/+5
| |
* | internal: use more mutable APIsAleksey Kladov2021-05-142-35/+17
| |
* | internal: rewrite assoc item manipulaion to use mutable treesAleksey Kladov2021-05-143-153/+72
| |
* | internal: remove SyntaxRewriterAleksey Kladov2021-05-142-153/+4
| |
* | internal: remove more of the SyntaxRewriterAleksey Kladov2021-05-141-29/+31
| |
* | internal: remove one more immutable treeAleksey Kladov2021-05-144-40/+13
| |
* | Cleanup importsAleksey Kladov2021-05-131-4/+3
|/
* simplifyAleksey Kladov2021-05-101-0/+3
|
* internal: introduce `ast::make::ext` module with common shortcutsAleksey Kladov2021-05-091-43/+52
| | | | | | | | | | There's a tension between keeping a well-architectured minimal orthogonal set of constructs, and providing convenience functions. Relieve this pressure by introducing an dedicated module for non-orthogonal shortcuts. This is inspired by the django.shortcuts module which serves a similar purpose architecturally.
* internal: fix make APIAleksey Kladov2021-05-091-8/+31
|
* internal: rewrite **Repalce impl Trait** assist to mutable syntax treesAleksey Kladov2021-05-091-12/+7
|
* cleanupsAleksey Kladov2021-05-091-2/+2
|
* minor: remove dead codeAleksey Kladov2021-05-081-11/+1
|
* internal: pull_assignment_up uses mutable treesAleksey Kladov2021-05-081-0/+3
|
* dead codeAleksey Kladov2021-05-081-121/+1
|
* internal: remove one more syntax rewriterAleksey Kladov2021-05-081-1/+4
|
* fix: use raw idents in `make::name{_ref}` with keywordsJonas Schievink2021-05-071-2/+12
|
* Hide implementation details of TokenTextDawer2021-05-062-8/+20
|
* Clean upDawer2021-05-061-15/+2
|
* Borrow text from nodes of immutable syntax treesDawer2021-05-062-25/+49
|
* Adapt to a new rowan borrowing node API.Dawer2021-05-062-2/+2
|
* Update to rowan 0.13.0-pre.5Dawer2021-05-061-1/+1
|
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-22 13:45:44 +0000