bors[bot] [Wed, 30 Jun 2021 17:37:28 +0000 (17:37 +0000)]
Merge #9436
9436: minor: Add test for macro expanded test module in runnables r=Veykril a=Veykril
Expected this to fail as thats behaving incorrectly on current nightly but I think I fixed this accidentally with https://github.com/rust-analyzer/rust-analyzer/pull/9435
bors r+
bors[bot] [Mon, 28 Jun 2021 19:57:23 +0000 (19:57 +0000)]
Merge #9423
9423: fix: Resolve attribute paths in attribute highlighting r=Veykril a=Veykril
Attributes have a new highlighting format now, whereas the `#[` `]` tokens are now tagged with `attribute.attribute` like before, but all other idents inside token trees are now `generic.attribute`. If a path in an attribute can't be resolved it will instead get the `builtinAttribute.attribute` tags now as highlighting doesn't know about builtins like `allow` yet, so we don't want to emit unresolved references.
Aleksey Kladov [Fri, 25 Jun 2021 07:32:13 +0000 (10:32 +0300)]
internal: add cloning macro fixture
Macro that deep clone the tokens but otherwise preserves source
locations and hygiene info is an interesting case for IDE support. Lets
have this, although we don't actively use it at the moment.
bors[bot] [Wed, 23 Jun 2021 22:33:05 +0000 (22:33 +0000)]
Merge #9380
9380: feat: Implement goto_declaration support r=matklad a=Veykril
This is just a simple implementation that falls back to `goto_definition` for everything but modules where it goes to the actual module declaration if possible.
bors[bot] [Wed, 23 Jun 2021 21:33:30 +0000 (21:33 +0000)]
Merge #9353
9353: Include extra targets when the pkg_root is not the same as the target root. r=matklad a=rezural
Fixes #7715
For example, if a sub-crate includes sets the path='../somewhere-else/lib.rs', the files will not be in pkg_root , but in the target root's parent.
It may actually be in root.parent().parent(), I'm not sure about that.
At the moment it is just a fix, are there any relevant tests that this could go in? I've got about 1 brain cell left... but im happy to add tests where appropriate.
bors[bot] [Tue, 22 Jun 2021 22:28:43 +0000 (22:28 +0000)]
Merge #9383
9383: internal: Rewrite token tree lowering to use an explicit stack r=jonas-schievink a=jonas-schievink
Part of https://github.com/rust-analyzer/rust-analyzer/issues/9358, this fixes the first cause of the stack overflow there. Unfortunately we now run into a stack overflow in the parser.
bors r+
Co-authored-by: Jonas Schievink <jonasschievink@gmail.com>
Aleksey Kladov [Tue, 22 Jun 2021 18:22:36 +0000 (21:22 +0300)]
internal: remove one more accidentally quadratic code-path
Definition::visibility was implemented in a rather roundabout way -- by
asking the parent module about the effective visibility.
This is problematic for a couple of reasons:
* first, it doesn't work for local items
* second, asking module about visibility of a child is a linear
operation (that's a problem in itself, tracked in #9378)
Instead, lets ask the declared visibility directly, we have all the code
for it, and need only to actually us it.
Aleksey Kladov [Mon, 21 Jun 2021 17:14:38 +0000 (20:14 +0300)]
feature: massively improve performance for large files
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!