Getting traits WG up and going


#1

Hi all,

First off, I want to apologize for the radio silence on this working group. It’s been harder than I anticipated to come up get a good crop of “start issues” and so forth. In general, I feel like we’re still trying to figure out the best way to get a “working group” up and going.Therefore, I thought, if I can’t figure this out on my own, why don’t we all start talking it out together? Hence this thread!

There are a few things that have been puzzling me. I’ll write a bit about topics, but mostly I want to hear from all of you.

  • Communication places
  • How can we as a group best stay in sync?
  • How best to proceed with changes?

Communication places

We have the gitter channel. I’ve just creaed a category on internals:

Since we’re spread across so many time zones, let’s try to make good use of the message board for communication. In particular, you can customize notifications for things in this category.

How can we stay in sync?

Most teams wind up with some kind of regular “check-in”, to pass news, stay in touch with what poeple are up to, or ask questions. I think we should do the same. However, here are a few challenges:

  • Time zones: we have a lot of them!
  • Language barriers: voice calls can be tough on folks for whom English isn’t their first language.

I was thinking we could therefore try to do one of two things (or both!):

  • Weekly check-in on the gitter channel at some regular time (optional)
    • We can jump on the gitter channel to sync up. I imagine a relatively short, triage-like meeting. We would then post the notes and minutes to an internals thread for others to comment on async.
  • Weekly check-in on an internals thread
    • We can have a dedicated thread. I can try to ping folks every week, say on Monday, and hopefully people can leave updates in a 24 hour window?

Thoughts?

How best to proceed with changes?

So, I definitely have ambitious plans, and I’m trying to figure out how best to “stage” them. There are a few challenges I see:

Explaining the design I have in mind. My plan here was to write chapters in the rustc-guide. I still want to do this, and am hard at work on it, but it’s been hard to find time for that. I could imagine also writing up an RFC, but I feel like our experience on the compiler team has been that compiler RFCs are not necessarily worth the trouble. Maybe I should just try to write-up some more things and cc this group for feedback? And/or post drafts/links on internals?

Hashing out some of the open questions and a transition plan. The above is really looking at “big picture” questions. But there are also a bunch of smaller things, like how to actually do the transition. Even if you don’t know the compiler really well, I think it’d be pretty useful to be getting feedback on these questions. For one thing, it will help all of us to learn, since if you ask a question, then those who know more will have to explain the answer. But secondly, even a rubber duck can be a pretty useful role to play!

Land the canonicalization PR. One of the first steps that I think needs to get done is to land https://github.com/rust-lang/rust/pull/48411, which adds the idea of canonicalization and is kind of a pre-req to most of the design I have in mind. It’s been a bit stalled trying to overcome some small performance hits in a few cases – I believe these are due to the fact that we’re not using the new design very broadly yet, and hence we’re populating two sets of caches. (I could probably use some help doing profiling and making improvements here, if someone is interested – I only get a few hours a day to code, so I have to have things blocked on me.)

Finding good “startup” issues to help people get acquainted with the trait checker. I haven’t done a thorough search of the GitHub repo, that is the obvious place to start. I will endeavor to make time for this. I’ve found it’s a very time confusing – but very useful! – thing to do. I suspect there will be some good candidates in error reporting – and, incidentally, that is one of the “sticky widgets” with transitioning to a new system, so I’m wondering if we can do some refactoring there.

OK, to avoid this message being too overwhelming, I’m going to end it here. Please give feedback, I’ll try to add more thoughts later.


#2

Hi!

Let me start with… first! :smile:

When it comes to “best” communication place, my preffered method has always been to use Gitter and then leaving important notes on forums (internals). However, when it comes to the weekly updates, I think it would be better to read it here, instead of scrolling through pages of chats. Still, I’m open to whatever the majority picks.

I’m pretty new to rust compiler, so it would be cool if you could link some articles/documentation about traits specifically. We could have a separate thread about all the useful resources. Also, if there aren’t any (or only few), this may be an opportunity for some starter issues :slight_smile:

I’m looking forward to learning and contributing!


#3

So, the main resource at present that I know of is this:

https://rust-lang-nursery.github.io/rustc-guide/trait-resolution.html

I am in the process of trying to write up a kind of “design proposal” that will amend the rustc-guide. I hope to open some PRs before end of the week.


#4

So I was thinking about how to organize our efforts. I believe that the primary initial goal ought to be enabling lazy normalization, for several reasons:

  • It is blocking const generics
  • The current scheme is the source of oh, so many bugs
  • I believe the current scheme is also costing us performance
    • It would be interesting to try and validate this, but maybe not worth too much energy. My basic reasoning is that we are spending a lot of time doing normalization, since we have to eagerly normalize so often, which we could avoid because frequently there aren’t even associated types. That said, we do try to optimize for that scenario (naturally), so maybe this isn’t as bad as it seems – still, I feel pretty confident that there are hidden costs we’re paying.

My previous effort to “cut a swatch towards lazy normalization” almost got things working, but ran aground dealing with cycles. Simultaneously, I put a bunch of effort into chalk and I feel like the current on-demand SLG solver basically represents a better alternative than our current trait solver along a number of dimensions. I don’t actually think it will necessarily be that much work to stand up some sort of initial prototype of the SLG solver within rustc.

However, standing up an initial prototype and actually shipping something are fairly different. There will still be a lot of work to do, particularly around error handling and other user-facing errors, where polish is important.

In addition to that primary goal, I think there are a number of secondary goals worth pursuing. The first few that come to mind are:

  • Improving specialization (#48538) – cc @giannicic
  • Progress on Generic Associated Types (GATs) (#44265) – cc @sunjay
  • Fixing miscellaneous bugs
    • Not sure which ones :slight_smile:

For GATs I’m quite sure there is plenty of work to do that is largely orthogonal from the core solver in use. For specialization, I suspect that the same is true, but I haven’t thought about it enough to be sure.

Thinking about this some more I think I would propose a plan like this:

  • A small set of people determined to stand up an SLG-based solver and validate some of my hypotheses about its potential benefits.
    • I would love to hack on this and plan to do that anyway.
    • I would love to hack with others even more.
    • I imagine we’d make a branch and push there to move faster.
    • I think the ideal candidate would have some number of hours per week to commit.
  • Some people to work on features, like the ones above
  • Some people to do performance analysis and other more targeted activities

#5

Hi @nikomatsakis, Can you give us a bit of an overview of the bigger picture that this WG will be trying to accomplish? The initial goal gives us a great place to start, but an overview would be great to get an idea of where that fits in the grand scheme of things. :blush:


#6

Well, I took a stab at this in my initial announcement, but perhaps that was not the correct level of detail. At the biggest picture, I want Rust’s trait checker to be a thing of beauty – efficient, well-specified with clean and clear semantics, and with a relatively high :bus: bus factor :bus: to boot.

A bit more detailed, the rough plan is still the “Chalk plan”:

  • Map Rust’s traits to logic clauses that roughly correspond to Lambda Prolog, roughly as described in my first Chalk blog post – though the details have evolved since then.
  • Solve these traits with an efficient solver, hopefully one that is quite a bit factored out so as to be independent of rustc. Probably following the on-demand SLG solver model laid out here, but I wouldn’t be surprised if that evolves some more as well.

(The reason I would like the solver to be independent of rustc is basically to make it easier to understand and to help encourage contribution (smaller codebases being more approachable). Also, if all goes well, this code be a shared resource used by e.g. IDEs or other tooling. But independence is ultimately a longer term goal, not something I expect to reach immediately.)

OK, time for bed, but I hope that gives some idea.


#7

Re: check-in/communication, I think doing a weekly check-in on both internals and gitter sounds good to me. We could maybe think of the latter as a slightly more informal/interactive version of the former, as well as a bit more optional (as it’s more time-specific and some might not be able to make it).

As for how best to proceed with changes, I want to say first that the rustc-guide is already an invaluable resource – really, thanks so much for working on it, @nikomatsakis (and others)! From a beginner’s point of view it’s wonderful to have things written down and to digest them at my own pace rather than take up the time of an expert with very basic questions. So for that reason I would definitely encourage you to treat writing up material for the guide as a reasonably high-priority thing, especially since it looks like you already have the high-to-mid-level design pretty well sussed out. The time will be well spent. The newcomers would find it approachable and useful, it would stick around for posterity, and it would also deduplicate a lot of communication. The more low-level questions can then be handled in a more ad hoc, rubber duck interactive style on say gitter.

I agree that the canonicalization PR needs to land soon. Last I checked you said you had some ideas for bandaging the perf loss, but do let us know if there are concrete ways to help.

Also yes, it goes without saying that “startup”-type issues are incredibly useful to beginners. I can only imagine the time it takes it identify them and write up details, though, so anything on this front is very gracious of you and will be appreciated by all.

I think the lazy normalization/new SLG solver issue is a great initial goal, and I’d be happy to be part of that set of people and volunteer a few (~6) hours on it per week! :slight_smile:

Thanks again for all your efforts here, @nikomatsakis, really! :slight_smile:


#8

I like this idea. Let’s say that Monday will be our check-in day? We can schedule an (optional, informal) Gitter check-in on Mondays at… say… 2pm Boston time? I’d also be game for earlier, which would be more inclusive of European schedules.

First PR: https://github.com/rust-lang-nursery/rustc-guide/pull/70

More to come!

I’ve been thinking this over. I think the best place to get started is probably by doing refactorings – and as a side benefit, the code winds up cleaner than it started! I’ve opened up one such issue so far:

but I think I will try to come up with more. I’m sure there’s lots to be done here.

Anyway, I plan to devote most of my energy this morning into finding issues and writing things in the rustc-guide – and yes, doing measurements for the canonicalization PR.


#9

I propose that we have a kind of “sync and planning” meeting around this particular project on Monday Mar 4 at 14:00 Boston time (19:00 UTC). The purpose of this is just to chart a course and break-up issues; attendance would not be mandatory if you want to take part. We can hold the meeting on appear.in; it should scale to up to 12 participants.

If you like, I can add you to a calendar invitation to help you remember, just ping me on gitter.

cc @aravindpg and @scalexm, who have expressed interest so far.


WG-Traits Minutes and General Discussion
#10

I opened up a few more refactoring issues. Look for the issues tagged with :hammer_and_wrench: at the start of this query.