Stream: wg-traits

Topic: being generic over types


nikomatsakis (Oct 21 2019 at 14:35, on Zulip):

So I did a lot of exploratory chalk refactoring over the weekend, since I had time to kill in airports while traveling to RBR. My branch is the split-tys branch over on my repository.

nikomatsakis (Oct 21 2019 at 14:35, on Zulip):

Current status:

nikomatsakis (Oct 21 2019 at 14:35, on Zulip):
nikomatsakis (Oct 21 2019 at 14:36, on Zulip):
nikomatsakis (Oct 21 2019 at 14:36, on Zulip):

I started working on the main goal here, which is to make clause generic generic over the "output" type family. It seems to be working "ok" but I decided I wanted to step back a bit from that and first do some other refactorings to that code to clean it up

nikomatsakis (Oct 21 2019 at 14:45, on Zulip):

I'm debating how to manage this branch. On the one hand, I kind of think I should land it ASAP -- it's quite invasive and not something I look forward to rebasing.

On the other hand, it doesn't yet reach a "useful" end-goal, and I'm nervous about introducing a lot of generics to the codebase if we decide this is the wrong direction.

On the gripping hand, I feel like 95% confident this is the right direction, and the codebase doesn't (yet) feel a lot more complex.

detrumi (Oct 21 2019 at 14:47, on Zulip):

impl<T: Zip<TF>, TF: TypeFamily> Zip<TF> for Vec<T>

Interesting, is this indirectly constraining the T by moving the TypeFamily bound to Zip instead?

detrumi (Oct 21 2019 at 14:51, on Zulip):

Merging these changes early doesn't feel like a problem, in the worst case it'll change again later

detrumi (Oct 21 2019 at 14:52, on Zulip):

On the other hand, it doesn't yet reach a "useful" end-goal

Do you have something in mind already, or is it more a matter of seeing how it will turn out?

nikomatsakis (Oct 21 2019 at 14:53, on Zulip):

actually, @detrumi, that's a good point; at some point I introducd the HasTypeFamily trait and we could potentially use that instead of having Zip<TF> -- however, it is also useful to sometimes have types (e.g., usize or whatever) that do not belong to any particular type family

nikomatsakis (Oct 21 2019 at 14:54, on Zulip):

Do you have something in mind already, or is it more a matter of seeing how it will turn out?

I do definitely have things in mind, in particular I want to use this to change how we do associated type normalization

nikomatsakis (Oct 21 2019 at 14:54, on Zulip):

but I think we can also use it for other things in other codebases

nikomatsakis (Oct 21 2019 at 14:54, on Zulip):

e.g., in the Lark compiler, I used a similar trick to distinguish types that may contain inference variables

nikomatsakis (Oct 21 2019 at 14:54, on Zulip):

from those that cannot

nikomatsakis (Oct 21 2019 at 14:54, on Zulip):

and those that may need substitution

nikomatsakis (Oct 21 2019 at 14:55, on Zulip):

one other thing thing I've found: I think ideally you would have

trait Fold<TF, TTF>

where TTF is the "target type family" you are folding into

nikomatsakis (Oct 21 2019 at 14:56, on Zulip):

However, lacking higher-ranked generics bounds (e.g., forall<T> { ... }), I was not able to make that work

nikomatsakis (Oct 21 2019 at 14:56, on Zulip):

though I guess if I were willing to give up on Folder being dyn-compatible I might be able to

detrumi (Oct 21 2019 at 14:56, on Zulip):

Yeah, that does sound a bit too higher-order for Rust atm

nikomatsakis (Oct 21 2019 at 14:57, on Zulip):

( the reason this would matter is that I later had to add some boilerplate, which doesn't show up in the commit history but is true in one of my stashes )

nikomatsakis (Oct 21 2019 at 14:57, on Zulip):

( basically reproducing the "Fold" logic but "cross-family" folding )

nikomatsakis (Oct 21 2019 at 14:57, on Zulip):

anyway having talked this out a bit I am leaning now towards:

nikomatsakis (Oct 21 2019 at 14:58, on Zulip):

landing the work also enables more collaboration. For example, I'd like someone to make a custom derive for Fold

detrumi (Oct 21 2019 at 14:58, on Zulip):

Right, it does seem to enable further work

nikomatsakis (Oct 21 2019 at 14:58, on Zulip):

currently we use macro_rules and it is ungreat

nikomatsakis (Oct 21 2019 at 14:59, on Zulip):

procedural macros didn't exist when chalk was first created though and -- at the time -- the macro rules macros were a big win :P

nikomatsakis (Oct 21 2019 at 21:52, on Zulip):

opened https://github.com/rust-lang/chalk/pull/265

nikomatsakis (Oct 21 2019 at 21:53, on Zulip):

I put r? @tmandry

detrumi (Oct 23 2019 at 09:56, on Zulip):

I'd like someone to make a custom derive for Fold

I've gotten most of the struct_fold converted to a derive macro already, but this one'll take some work:

struct_fold!(impl[TF: TypeFamily, F] Fold<TF> for InEnvironment<F> {
    environment,
    goal,
} where F: HasTypeFamily<TypeFamily = TF> + Fold<TF, Result = F>);
detrumi (Oct 23 2019 at 09:56, on Zulip):

https://github.com/nikomatsakis/chalk-ndm/compare/split-tys...detrumi:fold-derive-macro

detrumi (Oct 23 2019 at 10:00, on Zulip):

The F corresponds to the G: HasTypeFamily in the struct definition, right? I guess this'll require merging extra generic parameters in, instead of just replacing them like the cases where a non-generic struct had to be impl'd with Fold<ChalkIr>

detrumi (Oct 23 2019 at 10:10, on Zulip):

For the simpler cases I opted for a #[fold_family(ChalkIr)] attribute on the fold-deriving struct. Not sure if that's the best way, but it seems to work fine

detrumi (Oct 23 2019 at 13:23, on Zulip):

enum_macro actually was easier to replace (unless I broke something, but the tests are green). Void folding was an edge case but didn't seem to be used, and I don't think the "Hacky variant for use in slg::context::implementation" part of enum_fold was being used either

nikomatsakis (Oct 23 2019 at 13:58, on Zulip):

@detrumi hmm so --

nikomatsakis (Oct 23 2019 at 13:58, on Zulip):

what makes this case different, presumably, is that the type family isn't a direct parameter

nikomatsakis (Oct 23 2019 at 13:58, on Zulip):

but is rather "indirected", right?

nikomatsakis (Oct 23 2019 at 13:58, on Zulip):

one option would be to say that TypeFamily: HasTypeFamily<TypeFamily = Self>

nikomatsakis (Oct 23 2019 at 13:58, on Zulip):

so that we could essentially permit the derive on any type with a single type parameter, and then have the template be

nikomatsakis (Oct 23 2019 at 13:59, on Zulip):
impl<X, TF> Fold<TF> for InputType<X>
where X: HasTypeFamily<TypeFamily = TF>, TF: TypeFamily, /* plus where clauses from the type */
{ .. }
nikomatsakis (Oct 23 2019 at 14:00, on Zulip):

For the simpler cases I opted for a #[fold_family(ChalkIr)] attribute on the fold-deriving struct. Not sure if that's the best way, but it seems to work fine

hmm yeah I guess we want to cover the cases where there is no type parameter too; really there are a few patterns I suppose. The idea of a supporting attribute is pretty ok

detrumi (Oct 23 2019 at 14:03, on Zulip):

I was toying with the idea of detecting the G: HasTypeFamily instead, and then adding a TF parameter in the macro

nikomatsakis (Oct 23 2019 at 14:12, on Zulip):

@detrumi yeah, that's another good option -- now that you mention it, I think when I thought about this before, I was imagining:

it is a bit... sensitive though

nikomatsakis (Oct 23 2019 at 14:12, on Zulip):

i.e., it'll require checking the paths which is error-prone

nikomatsakis (Oct 23 2019 at 14:12, on Zulip):

another option:

nikomatsakis (Oct 23 2019 at 14:13, on Zulip):

decorate the type parameter, or use a fold argument

nikomatsakis (Oct 23 2019 at 14:13, on Zulip):

e.g.,

#[derive(Fold)]
struct Foo<#[TypeFamily] TF> { .. }
nikomatsakis (Oct 23 2019 at 14:13, on Zulip):

although I think the "convention over configuration" option of using distinctive type parameter names might be the easiest/best thing to do here

nikomatsakis (Oct 23 2019 at 14:14, on Zulip):

i.e., maybe we require the type parameter name TF (for a type family) / HTF (for something that has a type family)

detrumi (Oct 23 2019 at 14:15, on Zulip):

Requiring an exact name for the derive to work is kind of brittle though

detrumi (Oct 23 2019 at 14:17, on Zulip):

I think I can make it work for InEnvironment<G: HasTypeFamily>, the macro can then detect the HasTypeFamily bound and generate this:

impl<TF: TypeFamily, G> Fold<TF> for InEnvironment<G>
where
    G: HasTypeFamily<TypeFamily = TF> + Fold<TF, Result = G>
{..}
detrumi (Oct 23 2019 at 14:18, on Zulip):

I'm not 100% sure about all potential edge cases, but as long as we only add to the existing bounds I think it'll work out

nikomatsakis (Oct 23 2019 at 14:20, on Zulip):

I think I can make it work for InEnvironment<G: HasTypeFamily>, the macro can then detect the HasTypeFamily bound and generate

I was concerned about things like InEnvironment<G: foo::HasTypeFamily>

nikomatsakis (Oct 23 2019 at 14:20, on Zulip):

I guess we can make that work by just checking the "tail" element of the path

nikomatsakis (Oct 23 2019 at 14:20, on Zulip):

it is still potentially wrong if you do use HasTypeFamily as HTF but that point "you asked for it"

nikomatsakis (Oct 23 2019 at 14:21, on Zulip):

I'm fine with any such scheme, as long as we document it

nikomatsakis (Oct 23 2019 at 14:22, on Zulip):

I guess I like the idea of scanning the where-clauses and hoping to find exactly one type parameter T that is either:

nikomatsakis (Oct 23 2019 at 14:23, on Zulip):

For the simpler cases I opted for a #[fold_family(ChalkIr)] attribute on the fold-deriving struct. Not sure if that's the best way, but it seems to work fine

regarding this:

nikomatsakis (Oct 23 2019 at 14:23, on Zulip):

one thing that is sort of annoying is writing HasTypeFamily impls

nikomatsakis (Oct 23 2019 at 14:23, on Zulip):

maybe we should derive that too ?

nikomatsakis (Oct 23 2019 at 14:23, on Zulip):

using the same rules, perhaps, and perhaps with a procedural macro that lets you hard-code it

nikomatsakis (Oct 23 2019 at 14:23, on Zulip):

in that case, when you derive Fold, we could do

nikomatsakis (Oct 23 2019 at 14:24, on Zulip):
impl<TF, ...> Fold<TF> for ...
where ..., Self: HasTypeFamily<TypeFamily = TF>, TF: TypeFamily,
{ .. }
nikomatsakis (Oct 23 2019 at 14:24, on Zulip):

i.e., we move the heuristic from derive(Fold) to derive(TypeFamily)

nikomatsakis (Oct 23 2019 at 14:25, on Zulip):

(and if you want to write fold for something that doesn't have a type family, you write it by hand; those are the rare cases like Vec, copy types, etc, and we can't derive those anyway)

detrumi (Oct 23 2019 at 14:29, on Zulip):

Hmm, does that work for enums and structs that have no type parameters?

detrumi (Oct 23 2019 at 14:31, on Zulip):

But yeah, HasTypeFamily wouldn't be too hard to derive probably. Not sure if that would remove all TypeFamily logic from Fold though

detrumi (Oct 23 2019 at 14:33, on Zulip):

I'd like to avoid changing the struct/enum definitions too much while working on the Fold derive macro

nikomatsakis (Oct 23 2019 at 14:46, on Zulip):

Hmm, does that work for enums and structs that have no type parameters?

do you mean the ones in rust-ir?

nikomatsakis (Oct 23 2019 at 14:47, on Zulip):

if so, I think they would require something like

#[derive(Fold, ..)]
#[has_type_family(ChalkIr)]
struct StructDatum { ... }

where has_type_family(ChalkIr) generates something like

impl HasTypeFamily for StructDatum {
    type TypeFamily = ChalkIr;
}

this kills two birds with one stone, since it prevents the need to manually add such an impl

nikomatsakis (Oct 23 2019 at 14:47, on Zulip):

if you can do #[derive(HasTypeFamily(ChalkIr), Fold, ..)] that'd be even slicker

nikomatsakis (Oct 23 2019 at 14:48, on Zulip):

not sure if that's something we support or not though

nikomatsakis (Oct 23 2019 at 14:48, on Zulip):

(the idea would be that #[derive(HasTypeFamily)] requires a suitable type parameter, whereas derive(HasTypeFamily(X)) hard-codes to X)

detrumi (Oct 23 2019 at 14:51, on Zulip):

Derive arguments like that aren't possible, I think. That's why I had to resort to an extra attribute

nikomatsakis (Oct 23 2019 at 14:52, on Zulip):

yeah, ok

simulacrum (Oct 23 2019 at 14:53, on Zulip):

if you want arguments in all cases I would not use a derive; attribute macros are I believe stable these days so just go for them directly I think

nikomatsakis (Oct 23 2019 at 14:53, on Zulip):

you don't want them in all cases

nikomatsakis (Oct 27 2019 at 10:17, on Zulip):

@detrumi (warning, I'm hacking on the Fold trait quite a lot in a branch, so I'm making a lot of edits to the derive)

detrumi (Oct 27 2019 at 13:48, on Zulip):

Cool, curious to see what you can come up with

Last update: Nov 12 2019 at 16:00UTC