Stream: t-compiler/const-eval

Topic: long term plan for const pattern codegen #66120


pnkfelix (Nov 19 2019 at 15:27, on Zulip):

I spent some time trying to resolve long-standing issues with our #[structural_match] system that tries to restrict the set of consts that are allowed to be used in a pattern context.

pnkfelix (Nov 19 2019 at 15:28, on Zulip):

see also rfc#1445

pnkfelix (Nov 19 2019 at 15:29, on Zulip):

anyway, @eddyb pointed out in a review of my PR #66120 that it might be best to scrap my proposed approach and instead use something based on const-qualification

pnkfelix (Nov 19 2019 at 15:29, on Zulip):

specifically see the discussion here

pnkfelix (Nov 19 2019 at 15:30, on Zulip):

And so I wanted to try to get feedback here on the matter, about whether it makes more sense to try to apply mir_const_qualif here

eddyb (Nov 19 2019 at 15:33, on Zulip):

cc @ecstatic-morse looking at the actual code this seems pretty easy (compared to analyzing HIR)

ecstatic-morse (Nov 19 2019 at 18:18, on Zulip):

@pnkfelix I just looked at the issue referenced by your PR and check_consts::Qualif seems like the right tool for this. We'd have to do this in mir_const_qualif for all consts since we want to get this cross crate right?

ecstatic-morse (Nov 19 2019 at 18:22, on Zulip):

as opposed to doing it lazily for consts that appear as a pattern?

pnkfelix (Nov 19 2019 at 19:08, on Zulip):

Strategy of current PR is to handle cross-crates by falling back on a conservative type-based analysis

pnkfelix (Nov 19 2019 at 19:08, on Zulip):

So it doesn’t have to be done there. But it probably is something to consider

RalfJ (Nov 19 2019 at 19:09, on Zulip):

type-based analysis will anyway be needed for associated consts

ecstatic-morse (Nov 19 2019 at 19:10, on Zulip):

Okay, we can it either way. It just affects whether the code goes in mir_const_qualif or you use the API directly.

ecstatic-morse (Nov 19 2019 at 19:11, on Zulip):

Also, the churn that eddyb mentioned in their comment has abated somewhat, so this shouldn't be too hard.

ecstatic-morse (Nov 19 2019 at 19:14, on Zulip):

Basically, you'll add an implementer of the Qualif trait for structural matching, probably very similar to the existing one for Drop.

ecstatic-morse (Nov 19 2019 at 19:16, on Zulip):

Then use it for a dataflow analysis as is done in the MIR const-checker

ecstatic-morse (Nov 19 2019 at 19:19, on Zulip):

currently those other qualifs look to see if there was a mutable borrow of that local (that's what IndirectlyMutableLocals is for). You probably want to do this, even though we don't allow mutable references in consts at the moment.

ecstatic-morse (Nov 19 2019 at 19:21, on Zulip):

If you want to make this part of mir_const_qualif (and thus allow it to work cross-crate at the cost of running another dataflow pass on every const), you would just have to add the new Qualif to ConstQualifs in rustc::mir and modify Qualifs::in_return_place to extract it.

ecstatic-morse (Nov 19 2019 at 19:23, on Zulip):

Otherwise you can roll your own code using FlowSensitiveAnalysis

pnkfelix (Nov 20 2019 at 07:56, on Zulip):

@eddyb are you opposed to me landing the PR #66120 as is (or with slight tweaks), and filing an issue for the mir_const_qualif-based approach?

eddyb (Nov 20 2019 at 15:19, on Zulip):

@pnkfelix well, other than HIR code that doesn't need to exist and is a dozen times larger than the equivalent Qualif logic,,, (no, I'm not opposed if you don't mind the code being around for a while)

centril (Nov 20 2019 at 15:20, on Zulip):

@pnkfelix would be good to have some write-up in the rustc guide for the new semantics

centril (Nov 20 2019 at 15:20, on Zulip):

maybe an RFC as well if you change the approach so that we don't start accepting a bunch more code without some design input

eddyb (Nov 20 2019 at 15:21, on Zulip):

I'm not happy about the cross-crate distinction, it reminds me of how Enum::Variant as uN in a constant would only work same-crate :P

eddyb (Nov 20 2019 at 15:21, on Zulip):

but conservative type-based reasoning that still works is better than nothing

ecstatic-morse (Nov 25 2019 at 19:31, on Zulip):

@pnkfelix I'm happy to work on the mir_const_qualif part of this if you can point me towards an equivalent to this but for structural_match.

pnkfelix (Nov 26 2019 at 10:21, on Zulip):

@ecstatic-morse I think you are asking for the type_marked_structural function

pnkfelix (Nov 26 2019 at 10:22, on Zulip):

(which this PR refactors but I think its effect is unchanged.)

ecstatic-morse (Nov 26 2019 at 20:49, on Zulip):

@pnkfelix. Yeah that's the basic idea. We would have to store a few more things in check_consts::Item to call that directly.

I have zero experience working with an InferCtxt; do we still have access to one in librustc_mir?

Matthew Jasper (Nov 26 2019 at 20:56, on Zulip):

tcx.infer_ctxt().enter(|infcx| { /* your code here */ )

Matthew Jasper (Nov 26 2019 at 20:57, on Zulip):

There are queries that should allow you to do this as well.

ecstatic-morse (Nov 26 2019 at 20:58, on Zulip):

@Matthew Jasper Is it expensive to create a new inference context? It seems like we should have a is_structural_match query for a Ty.

Matthew Jasper (Nov 26 2019 at 20:59, on Zulip):

It's not that expensive since the 'tcx/'gcx unification (there is still currently an unnecessary TLS access on enter and exit)

Matthew Jasper (Nov 26 2019 at 20:59, on Zulip):

But back to the queries...

Matthew Jasper (Nov 26 2019 at 21:01, on Zulip):

type_op_prove_predicate is the one you want I think...

ecstatic-morse (Nov 26 2019 at 21:04, on Zulip):

The docs for that query say "Do not call this query directly: part of the ProvePredicate type-op". Would this guidance apply here?

Matthew Jasper (Nov 26 2019 at 21:04, on Zulip):

Actually that still needs an Infcx

Matthew Jasper (Nov 26 2019 at 21:04, on Zulip):

Yes that

ecstatic-morse (Nov 26 2019 at 21:09, on Zulip):

Okay, I think ProvePredicate and InferCtxt will be enough to get a prototype built. I can get help with performance later.

Matthew Jasper (Nov 26 2019 at 21:10, on Zulip):

There's an example on how to use these here: https://github.com/rust-lang/rust/blob/9abc34ed9d34873066a186ac5551d5aad9e783b6/src/librustc_mir/borrow_check/nll/type_check/mod.rs#L2723

Matthew Jasper (Nov 26 2019 at 21:11, on Zulip):

There also needs to be some care that regions are erased when we check this.

Matthew Jasper (Nov 26 2019 at 21:12, on Zulip):

Which honestly, they should always be in MIR (except for the borrow checker's copy). But that's a future PR.

ecstatic-morse (Nov 26 2019 at 21:13, on Zulip):

Are we okay using ProvePredicate outside the nll module for things unrelated to lifetimes? Even if regions are erased?

Matthew Jasper (Nov 26 2019 at 21:14, on Zulip):

It should be fine, just don't copy NLL and unwrap the error. :smiley:

Matthew Jasper (Nov 26 2019 at 21:15, on Zulip):

(that is don't unwrap, even though NLL does)

ecstatic-morse (Nov 26 2019 at 21:15, on Zulip):

unreachable_unchecked it is!

Matthew Jasper (Nov 26 2019 at 21:15, on Zulip):

:upside_down:

ecstatic-morse (Nov 26 2019 at 21:16, on Zulip):

I'll give this a try this evening.

Matthew Jasper (Nov 26 2019 at 21:17, on Zulip):

And push_region_constraints should be be replaced with an assertion of data.is_empty()

Matthew Jasper (Nov 26 2019 at 21:17, on Zulip):

Maybe...

Matthew Jasper (Nov 26 2019 at 21:18, on Zulip):

Actually, yes, do that and when it ICEs ask for help.

ecstatic-morse (Nov 26 2019 at 21:18, on Zulip):

In other words whether a type implements StructuralPartialEq should not be dependent on lifetimes since they should all be erased by the time we call this?

Matthew Jasper (Nov 26 2019 at 21:24, on Zulip):

They should all be erased. There might be some issues with late-bound regions and universes, but I'm hoping that it works for now.

Matthew Jasper (Nov 26 2019 at 21:25, on Zulip):

And in the final value they're all 'static

Matthew Jasper (Nov 26 2019 at 21:25, on Zulip):

or late-bound

Matthew Jasper (Nov 26 2019 at 21:26, on Zulip):

I guess not in associated constants, sigh...

ecstatic-morse (Nov 26 2019 at 21:30, on Zulip):

Hmm, well I can always use the same approach as pnkfelix and start caching it later.

ecstatic-morse (Nov 26 2019 at 21:31, on Zulip):

Presumably I can do no worse than their PR?

Matthew Jasper (Nov 26 2019 at 21:38, on Zulip):

I guess

ecstatic-morse (Dec 02 2019 at 21:30, on Zulip):

@pnkfelix I implemented a barebones structural match Qualif in a WIP branch. The next step would be to check the results of mir_const_qualif in hair/pattern/mod.rs. Do you have any opinions on the best way to do this?

pnkfelix (Dec 03 2019 at 09:31, on Zulip):

@ecstatic-morse I was assuming that you'd have to put the check somewhere else; doesn't mir_const_qualifoperate on MIR? the code in hair/pattern/mod.rs is transforming HIR to HAIR, so its running too early to apply something that operates on MIR.

ecstatic-morse (Dec 04 2019 at 17:45, on Zulip):

@pnkfelix Is it not possible for HIR -> HAIR lowering of one item to depend on HIR -> HAIR -> MIR being completed for another? I'm not very familiar with the constraints of the query system.

pnkfelix (Dec 04 2019 at 17:47, on Zulip):

Hmm maybe that is fine ....

ecstatic-morse (Dec 04 2019 at 17:47, on Zulip):

Perhaps a better time for this check would be HAIR -> MIR lowering?

ecstatic-morse (Dec 04 2019 at 17:49, on Zulip):

Although it looks like we would have to keep a DefId in hair::PatKind

ecstatic-morse (Dec 04 2019 at 17:51, on Zulip):

I'll try to work on my branch some more I guess

pnkfelix (Dec 06 2019 at 10:39, on Zulip):

I'll try to look at your branch now

pnkfelix (Dec 06 2019 at 11:53, on Zulip):

@ecstatic-morse what is the self.indirectly_mutable(..) check doing here? is that a cut-and-paste type? https://github.com/rust-lang/rust/compare/master...ecstatic-morse:qualif-structural-match#diff-b0c62fbcd3affaac3e5bfcef42f9d4b0R116

pnkfelix (Dec 06 2019 at 12:18, on Zulip):

also, I am trying to understand the Qualif trait's API. I can see that the methods return booleans to signal whether they've seen "something bad" or not. But is there some way to record what the "something bad" was?

oli (Dec 06 2019 at 12:24, on Zulip):

By what do you mean the exact location of the bad thing? Or the kind of bad thing? Becaues the kind is the type implementing the trait

pnkfelix (Dec 06 2019 at 12:43, on Zulip):

the kind of the bad thing... or at least some specific info about it other than its existence

pnkfelix (Dec 06 2019 at 12:43, on Zulip):

I thought part of what happens here is you do a traversal of the MIR

pnkfelix (Dec 06 2019 at 12:43, on Zulip):

like, the whole const is "bad"

pnkfelix (Dec 06 2019 at 12:43, on Zulip):

but its bad because of something we encountered while traversing it

pnkfelix (Dec 06 2019 at 12:44, on Zulip):

but maybe I simply misinterpreted the Qualif trait itself.

pnkfelix (Dec 06 2019 at 12:55, on Zulip):

concrete example, for structural_match: Say we're analyzing const FOO: (u32, Inner) = (0, Inner::new());, where Inner does not derive PartialEq+Eq. So we do tcx.at(span).mir_const_qualif(foo_def_id). But I want the diagnostic to report the problem is with the use of Inner.

oli (Dec 06 2019 at 13:12, on Zulip):

Hmm... I don't think there's a scheme for pointing to the source of the failure

oli (Dec 06 2019 at 13:13, on Zulip):

Maybe qualifs should have Result<(), SomeInfo> instead of just bool

pnkfelix (Dec 06 2019 at 13:16, on Zulip):

yeah; though I suspect SomeInfo might need to be customized per-analysis (so that's yet another associated type on trait Qualif)

ecstatic-morse (Dec 06 2019 at 17:56, on Zulip):

Qualif is basically a MIR Visitor that can return a boolean, with *_structurally in place of super_*. However, Qualif is fine-grained; it only visits things Rvalues and things that can appear in Rvalues, not entire Statements or Bodys.

The return value of the in_* methods is used to set/clear bits during dataflow analysis, so there's no way to find which Rvalue caused a qualif to appear in a final value at present. It's possible for a qualif to come from multiple places. We would need to construct an actual data dependency graph (a use-def chain) for this. This would also benefit other implementers of the Qualif trait.

indirectly_mutable is a safety measure for when &mut is allowed in constants. If a reference that would allow mutation is created to any local, we fall back to conservative, type-based qualification (in_any_value_of_ty), since we can no longer use dataflow to reason about the value in a local.

ecstatic-morse (Dec 09 2019 at 02:33, on Zulip):

I worked on my branch a bit more. Turns out we need a is_definitely_not_structural_match that returns true for NoDerive but false for Option<NoDerive>. This is the equivalent of has_dtor used for the NeedsDrop qualif, which is powered by the adt_destructor query

ecstatic-morse (Dec 09 2019 at 02:43, on Zulip):

@pnkfelix I don't think this is as simple as "does this type implement {Partial,}Eq but not Structural{Partial,}Eq", since the impl for e.g. Option<T> looks like impl<T: StructuralEq> StructuralEq for Option<T> {}. Is this right?

ecstatic-morse (Dec 09 2019 at 02:45, on Zulip):

I suppose we could look for any impl of StructuralEq for the type in question, even if it's not applicable to the fully substituted type.

ecstatic-morse (Dec 09 2019 at 03:23, on Zulip):

Ah, I just saw this comment, which suggests that there are no where clauses on the StructuralEq impl for Option.

ecstatic-morse (Dec 09 2019 at 03:57, on Zulip):

If that's the case I'm doing something wrong :half_frown:

ecstatic-morse (Dec 09 2019 at 04:11, on Zulip):

Specifically, NotStructuralMatch::in_rvalue is returning true for Option::<NoDerive>::None, but Option<NoDerive should implement StructuralEq no?

pnkfelix (Dec 09 2019 at 06:05, on Zulip):

Correct. It indeed sounds like your code does something wrong. (When I was skimming it, I think I had vague worries that it would fall into the conservative type-structure traversal. Not sure.)

ecstatic-morse (Dec 09 2019 at 20:24, on Zulip):

I'm getting:

 FulfillmentError(Obligation(predicate=Binder(TraitPredicate(<T as std::marker::Sized>)), depth=1),Unimplemented),

as the reason StructuralEq cannot be fulfilled for Option<NoDerive>. Does this mean I'm not passing the right ParamEnv or something? Also, should the generated impl have a ?Sized bound?

Also, it seems that StructuralEq is not implemented for tuples, so I needed to special case those as well.

ecstatic-morse (Dec 09 2019 at 20:39, on Zulip):

Same thing for references. Is this intended?

ecstatic-morse (Dec 09 2019 at 23:31, on Zulip):

@pnkfelix ^

pnkfelix (Dec 09 2019 at 23:34, on Zulip):

Hmm. That is not intended

pnkfelix (Dec 09 2019 at 23:35, on Zulip):

Oh of course

pnkfelix (Dec 09 2019 at 23:35, on Zulip):

The current checker is based on the one that used attributes on ADTs

pnkfelix (Dec 09 2019 at 23:36, on Zulip):

So it handles the traversal of non-ADT types itself

pnkfelix (Dec 09 2019 at 23:36, on Zulip):

But i don’t object to adding blanket impls of StructuralTraits for those types

ecstatic-morse (Dec 09 2019 at 23:37, on Zulip):

I'm guessing you've handled this on your branch. I'm working off master but using your tests

pnkfelix (Dec 09 2019 at 23:38, on Zulip):

Regarding ?Sized: can an unsized type ever be used in a pattern?

pnkfelix (Dec 09 2019 at 23:38, on Zulip):

I guess slices and str, of course

pnkfelix (Dec 09 2019 at 23:39, on Zulip):

But those both feel like special cased instances, not examples of a more general form ...?

ecstatic-morse (Dec 09 2019 at 23:39, on Zulip):

The version of type_marked_structural from master is returning false for Option at the moment, even though the NoDerive struct from your tests is Sized (obvs).

pnkfelix (Dec 09 2019 at 23:40, on Zulip):

Anyway I need to go to bed now, it’s well past my bedtime and I’m unwell

ecstatic-morse (Dec 09 2019 at 23:40, on Zulip):

I don't know enough about patterns, but at least for Option it seems like the Sized bound is needed.

ecstatic-morse (Dec 09 2019 at 23:40, on Zulip):

No problem! Get better.

ecstatic-morse (Dec 10 2019 at 22:43, on Zulip):

I'm gonna hit pause on this until I can land a refactoring of the Qualif trait. My hope is that people who know more about the #[structural_match]/StructuralPartialEq system will be empowered to switch to a MIR-based approach if the intended use of the Qualif trait is clearer.

ecstatic-morse (Dec 10 2019 at 22:44, on Zulip):

I've been making a lot of dumb mistakes in this branch :lol:, and the refactoring will help me as well.

Last update: Dec 12 2019 at 01:00UTC