Stream: t-compiler/wg-rls-2.0

Topic: Name resolution librarification 2019-04-18


pnkfelix (Apr 18 2019 at 13:01, on Zulip):

Hello @WG-rls2.0

matklad (Apr 18 2019 at 13:01, on Zulip):

:wave:

matklad (Apr 18 2019 at 13:03, on Zulip):

Shall we begin? Since the doodle pool was not too popular, I expect the most interested parties are represented :-)

pnkfelix (Apr 18 2019 at 13:03, on Zulip):

sure

pnkfelix (Apr 18 2019 at 13:04, on Zulip):

though I'll say up front: I don't have too much to report (mostly some questions about objectives/scope/requirements)

pnkfelix (Apr 18 2019 at 13:04, on Zulip):

and given that I didn't finish pre-triage for the compiler meeting in an hour

matklad (Apr 18 2019 at 13:04, on Zulip):

I don't have any planed agenda for the meeting as well

pnkfelix (Apr 18 2019 at 13:04, on Zulip):

I might want to just keep this pretty short?

matklad (Apr 18 2019 at 13:04, on Zulip):

Sure, seems fine!

pnkfelix (Apr 18 2019 at 13:05, on Zulip):

I've only started a little bit with name resolution librarification stuff

pnkfelix (Apr 18 2019 at 13:05, on Zulip):

let me start with a couple of ... claims? hypotheses.

matklad (Apr 18 2019 at 13:05, on Zulip):

sure, go ahead!

pnkfelix (Apr 18 2019 at 13:06, on Zulip):

1. We want to create a name resolution library that can be used as a reference spec for how name resolution should behave, on correct programs

pnkfelix (Apr 18 2019 at 13:07, on Zulip):

the reason I add that bit at the end, is because @Vadim Petrochenkov made a comment some time ago that a bulk of the complexity in nameres comes from supporting diagnostics for the error cases

matklad (Apr 18 2019 at 13:07, on Zulip):

but we want at least detect erroneous programs?

pnkfelix (Apr 18 2019 at 13:08, on Zulip):

I imagine we don't want to claim that a given program is valid

pnkfelix (Apr 18 2019 at 13:08, on Zulip):

when, based at least on nameres algorithm, it is not valid

matklad (Apr 18 2019 at 13:09, on Zulip):

yeah, that's what I had in mind, sounds good!

pnkfelix (Apr 18 2019 at 13:09, on Zulip):

I have imagined a couple different ways to try to construct such an artifact

pnkfelix (Apr 18 2019 at 13:09, on Zulip):

at this point, my intention is to make a name-resolver that runs in parallel with the existing one

pnkfelix (Apr 18 2019 at 13:09, on Zulip):

and the two compare their results

pnkfelix (Apr 18 2019 at 13:09, on Zulip):

for the correct cases

pnkfelix (Apr 18 2019 at 13:10, on Zulip):

while the reference name-resolver makes no attempt to match diagnostic quality for the incorrect cases

pnkfelix (Apr 18 2019 at 13:11, on Zulip):

by "runs in parallel"

pnkfelix (Apr 18 2019 at 13:11, on Zulip):

I don't actually mean on parallel cores

matklad (Apr 18 2019 at 13:11, on Zulip):

Seems good, longish-term. Short-term, I expect plugging into rustc would be a ton of work. Another way to get something useful is by plugging into rust-analyzer first.

pnkfelix (Apr 18 2019 at 13:11, on Zulip):

but rather than the code is just added to corresponding points in the control flow of the compiler

pnkfelix (Apr 18 2019 at 13:12, on Zulip):

Yes, that is the place where I have been wondering about strategy here

pnkfelix (Apr 18 2019 at 13:12, on Zulip):

namely, plugging into rustc is a ton of work

matklad (Apr 18 2019 at 13:12, on Zulip):

Could we perhaps reuse save-analysis for comparison?

pnkfelix (Apr 18 2019 at 13:12, on Zulip):

oh that's an interesting idea

matklad (Apr 18 2019 at 13:13, on Zulip):

Like, we don't plug code into rustc, we ask rustc to dump data, and then run test-suite against that data

matklad (Apr 18 2019 at 13:13, on Zulip):

We'll need a parser for rust, of course, but there are a couple available :)

pnkfelix (Apr 18 2019 at 13:14, on Zulip):

I had been assuming that a reason it made sense to plug into rustc was that this would simultanously: 1. yield the testing infrastructure (since its just a mode you turn on via a rustc flag), and 2. yield a software artifact that we would be semi-confident in at the outset (since it was written to match the control-flow of rustc itself)

pnkfelix (Apr 18 2019 at 13:14, on Zulip):

but I hadn't considered that save-analysis gives us an alternative path for testing

pnkfelix (Apr 18 2019 at 13:15, on Zulip):

so, lets try the thought experiment then

matklad (Apr 18 2019 at 13:15, on Zulip):

Plugging direrctly into rustc runs the risk of replicating rustc's interface, which may not be ideal

pnkfelix (Apr 18 2019 at 13:15, on Zulip):

right, that is the risk: How to make something general purpose enough that it can be reused elsewhere

pnkfelix (Apr 18 2019 at 13:16, on Zulip):

do you think it makes sense to try to plan ahead for eventual integration with rustc (the aforementioned testing strategy, lets call it Just-in-Time Testing)

pnkfelix (Apr 18 2019 at 13:17, on Zulip):

because I was semi-concerned about the opposite problem: If i start with Rust-analyzer's nameresolver

pnkfelix (Apr 18 2019 at 13:17, on Zulip):

I may end up with something that I cannot effectively plug into rustc ?

pnkfelix (Apr 18 2019 at 13:17, on Zulip):

though I suppose this is somewhat silly

matklad (Apr 18 2019 at 13:18, on Zulip):

I think no, we shouldn't aim at integration from the outset: integration with rustc is a huge chunk of work, probably larger than just doing the thing from scratch.

pnkfelix (Apr 18 2019 at 13:18, on Zulip):

i.e. anything that can work for an IDE (and that produces correct results), should be able to be hacked on in some manner to integrate with a batch compiler.

pnkfelix (Apr 18 2019 at 13:18, on Zulip):

okay. I can go along with that

pnkfelix (Apr 18 2019 at 13:18, on Zulip):

certainly sounds more palatable to me for the short term.

matklad (Apr 18 2019 at 13:18, on Zulip):

basically, the biggest value we can get here is wild experimentaion

pnkfelix (Apr 18 2019 at 13:19, on Zulip):

another question that has arisen when I've posed the first claim above, that all we need to care about initially is replicating the behavior on correct programs

matklad (Apr 18 2019 at 13:19, on Zulip):

right

pnkfelix (Apr 18 2019 at 13:19, on Zulip):

that has led some to point out "IDE's may want to produce diagnostic suggestions on incorrect programs"

pnkfelix (Apr 18 2019 at 13:19, on Zulip):

suggesting the changes the user might want to make

pnkfelix (Apr 18 2019 at 13:19, on Zulip):

so there's a question of how much of that to plan ahead for

pnkfelix (Apr 18 2019 at 13:20, on Zulip):

Do you have any thoughts there? Or is that something you think we can worry about after we get something running that only worries about correct programs?

matklad (Apr 18 2019 at 13:20, on Zulip):

Good question! An interesting aspect of dagnostics in IDE is that they should be structural (like in structured logging)

matklad (Apr 18 2019 at 13:21, on Zulip):

So, you don't print spans on stderr, you produce some blob of data specific to the problem, and handle these data in the "fixes" layer, completely outside of resolver

pnkfelix (Apr 18 2019 at 13:21, on Zulip):

hmm. interesting

pnkfelix (Apr 18 2019 at 13:21, on Zulip):

the fixes layer isn't expected to need to extract information from the Error value it gets from the resolver?

pnkfelix (Apr 18 2019 at 13:22, on Zulip):

I was assuming it might want e.g. a way to see nearby names ("near" in the sense of string-matching)

matklad (Apr 18 2019 at 13:22, on Zulip):

it is expected: it should downcast error to a specific variant

pnkfelix (Apr 18 2019 at 13:22, on Zulip):

Okay

matklad (Apr 18 2019 at 13:22, on Zulip):

smth like this: https://github.com/rust-analyzer/rust-analyzer/blob/master/crates/ra_ide_api/src/diagnostics.rs#L39-L49

pnkfelix (Apr 18 2019 at 13:23, on Zulip):

my current thinking, in any case, is that if the API is designed appropriately, then we should be able to swap in different name resolution libraries

pnkfelix (Apr 18 2019 at 13:23, on Zulip):

where the library acting as the reference spec would produce Error objects that are practically ()

matklad (Apr 18 2019 at 13:24, on Zulip):

Yeah, seems resonable: create allowance for reporting errors, but report an ZST struct NameresError;

matklad (Apr 18 2019 at 13:24, on Zulip):

actually, could we step back a bit

pnkfelix (Apr 18 2019 at 13:24, on Zulip):

sure

matklad (Apr 18 2019 at 13:25, on Zulip):

What do we mean that we say "name resolution"?

pnkfelix (Apr 18 2019 at 13:25, on Zulip):

heh

matklad (Apr 18 2019 at 13:25, on Zulip):

There's I think two rather orhogonal slices to the thing

matklad (Apr 18 2019 at 13:25, on Zulip):

the first one is "modules & imports" bit, with fixed point, etc

pnkfelix (Apr 18 2019 at 13:25, on Zulip):

right

matklad (Apr 18 2019 at 13:25, on Zulip):

the second one is lexical scope stuff

pnkfelix (Apr 18 2019 at 13:26, on Zulip):

which ... might have some overlap today?

pnkfelix (Apr 18 2019 at 13:26, on Zulip):

I remember seeing some bug recently pointing out that you can write impl blocks within a fn

matklad (Apr 18 2019 at 13:26, on Zulip):

oh yeah

Vadim Petrochenkov (Apr 18 2019 at 13:26, on Zulip):

Imports are also a "lexical scope stuff" with uniform paths.
But with fixed point, etc!

pnkfelix (Apr 18 2019 at 13:27, on Zulip):

oh hi @Vadim Petrochenkov !

matklad (Apr 18 2019 at 13:27, on Zulip):

Hi @Vadim Petrochenkov !

Hm, but even local imports look only for items?

matklad (Apr 18 2019 at 13:27, on Zulip):

Like, you can have "modules and imports" inside functions, but it's still doesn't really intersect with lexical scopes?

matklad (Apr 18 2019 at 13:28, on Zulip):

In other words, would erasing expressions in function bodies change the meaning of items in function bodies?

Vadim Petrochenkov (Apr 18 2019 at 13:29, on Zulip):

Right now imports referring to local variables / generic parameters are actively reported as errors.

Vadim Petrochenkov (Apr 18 2019 at 13:29, on Zulip):

(Rather than skipping local variables and searching for items in outer scopes.)

Vadim Petrochenkov (Apr 18 2019 at 13:30, on Zulip):

With successful compilation imports can only refer to items, yes (+ preludes, built-in things, etc).

matklad (Apr 18 2019 at 13:31, on Zulip):

playground example: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=faf6ea2a0543aa5eac9b503ca0a8b757

Yeah, that's... interesting

Vadim Petrochenkov (Apr 18 2019 at 13:31, on Zulip):

But I'd ideally want to unify the name search algorithm between early and late resolution, there are fewer differences than similarity now.

matklad (Apr 18 2019 at 13:31, on Zulip):

the reason why I seek this separation is that, in IDE, we really want to avoid name resolving function bodies

matklad (Apr 18 2019 at 13:31, on Zulip):

until we actually need to, eg, typecheck the function

pnkfelix (Apr 18 2019 at 13:32, on Zulip):

isn't it enough to just delay such name resolution?

matklad (Apr 18 2019 at 13:32, on Zulip):

I suppose so. Like, they don't have to be two algoithms, they can be a single algorithm, operating on different sets of data

pnkfelix (Apr 18 2019 at 13:32, on Zulip):

or is there some reason to avoid it, beyond latency?

matklad (Apr 18 2019 at 13:33, on Zulip):

Big-O complexity, basically

pnkfelix (Apr 18 2019 at 13:33, on Zulip):

okay

matklad (Apr 18 2019 at 13:33, on Zulip):

there are far more body code than top-level code

Vadim Petrochenkov (Apr 18 2019 at 13:35, on Zulip):

I'd ignore erroneous imports referring to locals for a start, it's an extremely corner case.

pnkfelix (Apr 18 2019 at 13:35, on Zulip):

it seems to me like we should be able to delay such work until you want to e.g. type-check or resolve trait impls.

matklad (Apr 18 2019 at 13:35, on Zulip):

Yeah.... I guess this is all for my "stepping a step back": we should try to find ways to be lazy with nameres.

pnkfelix (Apr 18 2019 at 13:37, on Zulip):

with regards to using RA as the basis for an initial nameres library

matklad (Apr 18 2019 at 13:37, on Zulip):

well, not as basis, as a client: I feel the lib should be independent, and have its own IR, like chalk

pnkfelix (Apr 18 2019 at 13:37, on Zulip):

sure

pnkfelix (Apr 18 2019 at 13:38, on Zulip):

my understanding is that RA today does not attempt to produce results that are always correct

matklad (Apr 18 2019 at 13:39, on Zulip):

That's very true

pnkfelix (Apr 18 2019 at 13:40, on Zulip):

do you think it would be better to have a nameres library that has multiple modes, in terms of how fast it gives results vs the correctness of those results

pnkfelix (Apr 18 2019 at 13:40, on Zulip):

or do you think its better to focus on correctness alone

pnkfelix (Apr 18 2019 at 13:41, on Zulip):

and assume that we'll figure out ways to keep the latency under control?

matklad (Apr 18 2019 at 13:41, on Zulip):

What would "fast" mode do?

pnkfelix (Apr 18 2019 at 13:41, on Zulip):

it might fail to resolve

pnkfelix (Apr 18 2019 at 13:41, on Zulip):

due to not expanding macros, for example

matklad (Apr 18 2019 at 13:42, on Zulip):

I feel it's crucial to aim for "100% correct if we fix all the bugs"

pnkfelix (Apr 18 2019 at 13:42, on Zulip):

okay

matklad (Apr 18 2019 at 13:42, on Zulip):

and it's very important to have lazyness, or, at least, incrementality

matklad (Apr 18 2019 at 13:43, on Zulip):

Basically, re-nameresolving after you modify function body should be fast

pnkfelix (Apr 18 2019 at 13:43, on Zulip):

sure. I had said in the past that I figured one way to go here would be to have an asynchronous interface

matklad (Apr 18 2019 at 13:43, on Zulip):

If we can't do both "correct" and "lazy enough", that would be a pretty difficult position to be

matklad (Apr 18 2019 at 13:43, on Zulip):

with respect to the whole idea of using the same code base for compiler and ide, etc

pnkfelix (Apr 18 2019 at 13:44, on Zulip):

I agree with that

pnkfelix (Apr 18 2019 at 13:44, on Zulip):

I mostly was curious if, based on your work so far, if you thought that such a goal was not achievable in the first place.

pnkfelix (Apr 18 2019 at 13:44, on Zulip):

(I suppose if you thought that, then we wouldn't be having this conversation at all)

matklad (Apr 18 2019 at 13:45, on Zulip):

I am now feeling more optimistic than initially :0)

pnkfelix (Apr 18 2019 at 13:45, on Zulip):

okay. So I think the main action items I would like to look at

matklad (Apr 18 2019 at 13:45, on Zulip):

Salsa works wonders, and our (super-buggy) fixed-point iteration loop actually achives the required lazyness/latency

pnkfelix (Apr 18 2019 at 13:46, on Zulip):

is to try to factor out code from RA that does name-resolution, and that validates its result against save-analysis

pnkfelix (Apr 18 2019 at 13:46, on Zulip):

if I can get something running (and that presumably yields test failures on the appropirate cases exercising the bugs)

pnkfelix (Apr 18 2019 at 13:47, on Zulip):

then that would be a proof-of-concept for what we're talking about here

pnkfelix (Apr 18 2019 at 13:47, on Zulip):

Right?

matklad (Apr 18 2019 at 13:47, on Zulip):

sgmt

matklad (Apr 18 2019 at 13:47, on Zulip):

though, I would add a step before that

pnkfelix (Apr 18 2019 at 13:47, on Zulip):

(and the main issue might be if its too tightly tied to rust-analyzer API stuff)

matklad (Apr 18 2019 at 13:47, on Zulip):
pnkfelix (Apr 18 2019 at 13:48, on Zulip):

(but being too tightly tied to rust-analyzer seems like a far better scenario than being too tightly tied to rustc API)

pnkfelix (Apr 18 2019 at 13:48, on Zulip):

ah yes, okay

matklad (Apr 18 2019 at 13:49, on Zulip):

@pnkfelix if you feel like you need to run to that other thing, I feel we've discussed the most important bits :)

pnkfelix (Apr 18 2019 at 13:49, on Zulip):

I think I do need to try to spend the next 10 minutes doing prep for the meeting that starts in 10 minutes.

pnkfelix (Apr 18 2019 at 13:49, on Zulip):

thanks for this discussion, it has been super helpful food

pnkfelix (Apr 18 2019 at 13:49, on Zulip):

for thought

matklad (Apr 18 2019 at 13:50, on Zulip):

I'll write notes and post them to rust-lang/compiler-team repo

matklad (Apr 18 2019 at 13:50, on Zulip):

Thanks for participating pnkfelix and Vadim Petrochenkov !

Last update: Nov 12 2019 at 16:15UTC