Tracking issue: Allow autoderef and autoref in operators (experiment)

[nikomatsakis]

This is a specific issue to track the changes proposed by @arielb1 in RFC 2174. We decided to roll this into a larger experiment around coercions, generics, and Copy type ergonomics and are therefore ready to implement (but not yet stabilize).

[nikomatsakis]

Note: @arielb1 was going to write-up some mentoring instructions here when they get the time. =)

[arielb1]

Mentor Notes

This basically requires 2 main steps:

1. changing method-style lookup to allow for lookup based on multiple types
2. changing operator dispatch to use method-style lookup

1. Changing method-style lookup to allow for lookup based on multiple types

Method lookup needs to have flags added to it, so it can support operator lookup as specified in RFC 2174.

The semantics are actually pretty similar to how it works today, but there are a few needed changes:

1. Operator lookup looks for a specific method DefId - the operator's trait method - instead of looking for all methods with the right name.
2. Operator lookup can't perform mutable autoref.
3. Operator lookup works with 2 receivers, while method lookup works with only 1

The code for looking up methods is in rustc_typeck::method::probe, and it needs to be adapted for all 3 components.

You basically want to add a method on FnCtxt that does an operator-style probe, which should have a similar interface to probe_for_name at

rust/src/librustc_typeck/check/method/probe.rs

Lines 201 to 283 in d8d5b61

	pub fn probe_for_name(&self,
	span: Span,
	mode: Mode,
	item_name: ast::Name,
	is_suggestion: IsSuggestion,
	self_ty: Ty<'tcx>,
	scope_expr_id: ast::NodeId,
	scope: ProbeScope)
	-> PickResult<'tcx> {
	debug!("probe(self_ty={:?}, item_name={}, scope_expr_id={})",
	self_ty,
	item_name,
	scope_expr_id);
	self.probe_op(span,
	mode,
	Some(item_name),
	None,
	is_suggestion,
	self_ty,
	scope_expr_id,
	scope,
	|probe_cx| probe_cx.pick())
	}
	fn probe_op<OP,R>(&'a self,
	span: Span,
	mode: Mode,
	method_name: Option<ast::Name>,
	return_type: Option<Ty<'tcx>>,
	is_suggestion: IsSuggestion,
	self_ty: Ty<'tcx>,
	scope_expr_id: ast::NodeId,
	scope: ProbeScope,
	op: OP)
	-> Result<R, MethodError<'tcx>>
	where OP: FnOnce(ProbeContext<'a, 'gcx, 'tcx>) -> Result<R, MethodError<'tcx>>
	{
	// FIXME(#18741) -- right now, creating the steps involves evaluating the
	// `*` operator, which registers obligations that then escape into
	// the global fulfillment context and thus has global
	// side-effects. This is a bit of a pain to refactor. So just let
	// it ride, although it's really not great, and in fact could I
	// think cause spurious errors. Really though this part should
	// take place in the `self.probe` below.
	let steps = if mode == Mode::MethodCall {
	match self.create_steps(span, self_ty, is_suggestion) {
	Some(steps) => steps,
	None => {
	return Err(MethodError::NoMatch(NoMatchData::new(Vec::new(),
	Vec::new(),
	Vec::new(),
	None,
	mode)))
	}
	}
	} else {
	vec![CandidateStep {
	self_ty,
	autoderefs: 0,
	unsize: false,
	}]
	};
	debug!("ProbeContext: steps for self_ty={:?} are {:?}",
	self_ty,
	steps);
	// this creates one big transaction so that all type variables etc
	// that we create during the probe process are removed later
	self.probe(|_| {
	let mut probe_cx =
	ProbeContext::new(self, span, mode, method_name, return_type, Rc::new(steps));
	probe_cx.assemble_inherent_candidates();
	match scope {
	ProbeScope::TraitsInScope =>
	probe_cx.assemble_extension_candidates_for_traits_in_scope(scope_expr_id)?,
	ProbeScope::AllTraits =>
	probe_cx.assemble_extension_candidates_for_all_traits()?,
	};
	op(probe_cx)
	})
	}

However, I feel that operator dispatch avoids most of the code in probe_op, so it's probably a good idea to copy-paste and modify probe_op instead of adding a new bunch of flags to it. You probably also want to call pick_core directly instead of doing the extra error reporting pick does - the extra error reporting does not look relevant for method calls.

Only probing for a specific DefId should be easy - instead of calling assemble_inherent_candidates etc., just add the operator method candidate (as a TraitCandidate) to extension_candidates.

Similarly, not probing for mutable autoref just requires having a flag and an if around the call to pick_autorefd_method with a mutable autoref, found in

rust/src/librustc_typeck/check/method/probe.rs

Line 837 in d8d5b61

self.pick_autorefd_method(step, hir::MutMutable)

Allowing dispatch with 2 receivers is a bit more annoying. I think the cleanest way would be to have an optional "secondary" xform_self_ty field on Candidate and to have pick_method and friends take an optional second step parameter, but I could be wrong about this. You'll also need to change ProbeContext so that it has an optional second set of steps, but it's a Simple matter of Coding™.

You will also need to have a variant of method confirmation that handles operators - see

rust/src/librustc_typeck/check/method/confirm.rs

Lines 80 to 143 in d8d5b61

	fn confirm(&mut self,
	unadjusted_self_ty: Ty<'tcx>,
	pick: probe::Pick<'tcx>,
	segment: &hir::PathSegment)
	-> ConfirmResult<'tcx> {
	// Adjust the self expression the user provided and obtain the adjusted type.
	let self_ty = self.adjust_self_ty(unadjusted_self_ty, &pick);
	// Create substitutions for the method's type parameters.
	let rcvr_substs = self.fresh_receiver_substs(self_ty, &pick);
	let all_substs = self.instantiate_method_substs(&pick, segment, rcvr_substs);
	debug!("all_substs={:?}", all_substs);
	// Create the final signature for the method, replacing late-bound regions.
	let (method_sig, method_predicates) = self.instantiate_method_sig(&pick, all_substs);
	// Unify the (adjusted) self type with what the method expects.
	//
	// SUBTLE: if we want good error messages, because of "guessing" while matching
	// traits, no trait system method can be called before this point because they
	// could alter our Self-type, except for normalizing the receiver from the
	// signature (which is also done during probing).
	let method_sig_rcvr =
	self.normalize_associated_types_in(self.span, &method_sig.inputs()[0]);
	self.unify_receivers(self_ty, method_sig_rcvr);
	let (method_sig, method_predicates) =
	self.normalize_associated_types_in(self.span, &(method_sig, method_predicates));
	// Make sure nobody calls `drop()` explicitly.
	self.enforce_illegal_method_limitations(&pick);
	// If there is a `Self: Sized` bound and `Self` is a trait object, it is possible that
	// something which derefs to `Self` actually implements the trait and the caller
	// wanted to make a static dispatch on it but forgot to import the trait.
	// See test `src/test/ui/issue-35976.rs`.
	//
	// In that case, we'll error anyway, but we'll also re-run the search with all traits
	// in scope, and if we find another method which can be used, we'll output an
	// appropriate hint suggesting to import the trait.
	let illegal_sized_bound = self.predicates_require_illegal_sized_bound(&method_predicates);
	// Add any trait/regions obligations specified on the method's type parameters.
	// We won't add these if we encountered an illegal sized bound, so that we can use
	// a custom error in that case.
	if !illegal_sized_bound {
	let method_ty = self.tcx.mk_fn_ptr(ty::Binder(method_sig));
	self.add_obligations(method_ty, all_substs, &method_predicates);
	}
	// Create the final `MethodCallee`.
	let callee = MethodCallee {
	def_id: pick.item.def_id,
	substs: all_substs,
	sig: method_sig,
	};
	if let Some(hir::MutMutable) = pick.autoref {
	self.convert_lvalue_derefs_to_mutable();
	}
	ConfirmResult { callee, illegal_sized_bound }
	}

For that method, you should make the segment parameter optional - it is here to support giving extra type parameters with a turbofish (e.g. my_iter.collect::<Vec<_>>), which isn't possible with operators (that would be something like x +::<IntegerAdd> y, which isn't valid Rust).a

2. Changing operator dispatch to use method-style lookup

For dispatch, there are 2 kinds of operators, "rvalue" operators and "lvalue" operators (the relevant lvalue operator here is overloaded indexing - implementing autoderef for the * operator is a bit pointless). You'll need to change both of them to use the new method-style lookup you implemented in step 1 instead of the hacky lookup they do now.

For an example of method lookup, see lookup_method (the function also does a bunch of error message guessing and other stuff you don't care about, you probably just want the probe and confirm components) at https://github.com/rust-lang/rust/blob/master/src/librustc_typeck/check/method/mod.rs#L144-L180

Rvalue operators are implemented in rustc_typeck::check::op - check_overloaded_binop -

rust/src/librustc_typeck/check/op.rs

Lines 156 to 306 in d8d5b61

	fn check_overloaded_binop(&self,
	expr: &'gcx hir::Expr,
	lhs_expr: &'gcx hir::Expr,
	rhs_expr: &'gcx hir::Expr,
	op: hir::BinOp,
	is_assign: IsAssign)
	-> (Ty<'tcx>, Ty<'tcx>, Ty<'tcx>)
	{
	debug!("check_overloaded_binop(expr.id={}, op={:?}, is_assign={:?})",
	expr.id,
	op,
	is_assign);
	let lhs_pref = match is_assign {
	IsAssign::Yes => PreferMutLvalue,
	IsAssign::No => NoPreference
	};
	// Find a suitable supertype of the LHS expression's type, by coercing to
	// a type variable, to pass as the `Self` to the trait, avoiding invariant
	// trait matching creating lifetime constraints that are too strict.
	// E.g. adding `&'a T` and `&'b T`, given `&'x T: Add<&'x T>`, will result
	// in `&'a T <: &'x T` and `&'b T <: &'x T`, instead of `'a = 'b = 'x`.
	let lhs_ty = self.check_expr_coercable_to_type_with_lvalue_pref(lhs_expr,
	self.next_ty_var(TypeVariableOrigin::MiscVariable(lhs_expr.span)),
	lhs_pref);
	let lhs_ty = self.resolve_type_vars_with_obligations(lhs_ty);
	// NB: As we have not yet type-checked the RHS, we don't have the
	// type at hand. Make a variable to represent it. The whole reason
	// for this indirection is so that, below, we can check the expr
	// using this variable as the expected type, which sometimes lets
	// us do better coercions than we would be able to do otherwise,
	// particularly for things like `String + &String`.
	let rhs_ty_var = self.next_ty_var(TypeVariableOrigin::MiscVariable(rhs_expr.span));
	let result = self.lookup_op_method(lhs_ty, &[rhs_ty_var], Op::Binary(op, is_assign));
	// see `NB` above
	let rhs_ty = self.check_expr_coercable_to_type(rhs_expr, rhs_ty_var);
	let rhs_ty = self.resolve_type_vars_with_obligations(rhs_ty);
	let return_ty = match result {
	Ok(method) => {
	let by_ref_binop = !op.node.is_by_value();
	if is_assign == IsAssign::Yes || by_ref_binop {
	if let ty::TyRef(region, mt) = method.sig.inputs()[0].sty {
	let autoref = Adjustment {
	kind: Adjust::Borrow(AutoBorrow::Ref(region, mt.mutbl)),
	target: method.sig.inputs()[0]
	};
	self.apply_adjustments(lhs_expr, vec![autoref]);
	}
	}
	if by_ref_binop {
	if let ty::TyRef(region, mt) = method.sig.inputs()[1].sty {
	let autoref = Adjustment {
	kind: Adjust::Borrow(AutoBorrow::Ref(region, mt.mutbl)),
	target: method.sig.inputs()[1]
	};
	// HACK(eddyb) Bypass checks due to reborrows being in
	// some cases applied on the RHS, on top of which we need
	// to autoref, which is not allowed by apply_adjustments.
	// self.apply_adjustments(rhs_expr, vec![autoref]);
	self.tables
	.borrow_mut()
	.adjustments_mut()
	.entry(rhs_expr.hir_id)
	.or_insert(vec![])
	.push(autoref);
	}
	}
	self.write_method_call(expr.hir_id, method);
	method.sig.output()
	}
	Err(()) => {
	// error types are considered "builtin"
	if !lhs_ty.references_error() {
	if let IsAssign::Yes = is_assign {
	struct_span_err!(self.tcx.sess, expr.span, E0368,
	"binary assignment operation `{}=` \
	cannot be applied to type `{}`",
	op.node.as_str(),
	lhs_ty)
	.span_label(lhs_expr.span,
	format!("cannot use `{}=` on type `{}`",
	op.node.as_str(), lhs_ty))
	.emit();
	} else {
	let mut err = struct_span_err!(self.tcx.sess, expr.span, E0369,
	"binary operation `{}` cannot be applied to type `{}`",
	op.node.as_str(),
	lhs_ty);
	if let TypeVariants::TyRef(_, ref ty_mut) = lhs_ty.sty {
	if {
	!self.infcx.type_moves_by_default(self.param_env,
	ty_mut.ty,
	lhs_expr.span) &&
	self.lookup_op_method(ty_mut.ty,
	&[rhs_ty],
	Op::Binary(op, is_assign))
	.is_ok()
	} {
	err.note(
	&format!(
	"this is a reference to a type that `{}` can be applied \
	to; you need to dereference this variable once for this \
	operation to work",
	op.node.as_str()));
	}
	}
	let missing_trait = match op.node {
	hir::BiAdd => Some("std::ops::Add"),
	hir::BiSub => Some("std::ops::Sub"),
	hir::BiMul => Some("std::ops::Mul"),
	hir::BiDiv => Some("std::ops::Div"),
	hir::BiRem => Some("std::ops::Rem"),
	hir::BiBitAnd => Some("std::ops::BitAnd"),
	hir::BiBitOr => Some("std::ops::BitOr"),
	hir::BiShl => Some("std::ops::Shl"),
	hir::BiShr => Some("std::ops::Shr"),
	hir::BiEq | hir::BiNe => Some("std::cmp::PartialEq"),
	hir::BiLt | hir::BiLe | hir::BiGt | hir::BiGe =>
	Some("std::cmp::PartialOrd"),
	_ => None
	};
	if let Some(missing_trait) = missing_trait {
	if missing_trait == "std::ops::Add" &&
	self.check_str_addition(expr, lhs_expr, lhs_ty,
	rhs_ty, &mut err) {
	// This has nothing here because it means we did string
	// concatenation (e.g. "Hello " + "World!"). This means
	// we don't want the note in the else clause to be emitted
	} else {
	err.note(
	&format!("an implementation of `{}` might be missing for `{}`",
	missing_trait, lhs_ty));
	}
	}
	err.emit();
	}
	}
	self.tcx.types.err
	}
	};
	(lhs_ty, rhs_ty, return_ty)
	}

Array indexing is implemented in lookup_indexing and try_index_step -

rust/src/librustc_typeck/check/mod.rs

Lines 2188 to 2290 in d8d5b61

	fn lookup_indexing(&self,
	expr: &hir::Expr,
	base_expr: &'gcx hir::Expr,
	base_ty: Ty<'tcx>,
	idx_ty: Ty<'tcx>,
	lvalue_pref: LvaluePreference)
	-> Option<(/*index type*/ Ty<'tcx>, /*element type*/ Ty<'tcx>)>
	{
	// FIXME(#18741) -- this is almost but not quite the same as the
	// autoderef that normal method probing does. They could likely be
	// consolidated.
	let mut autoderef = self.autoderef(base_expr.span, base_ty);
	let mut result = None;
	while result.is_none() && autoderef.next().is_some() {
	result = self.try_index_step(expr, base_expr, &autoderef, lvalue_pref, idx_ty);
	}
	autoderef.finalize();
	result
	}
	/// To type-check `base_expr[index_expr]`, we progressively autoderef
	/// (and otherwise adjust) `base_expr`, looking for a type which either
	/// supports builtin indexing or overloaded indexing.
	/// This loop implements one step in that search; the autoderef loop
	/// is implemented by `lookup_indexing`.
	fn try_index_step(&self,
	expr: &hir::Expr,
	base_expr: &hir::Expr,
	autoderef: &Autoderef<'a, 'gcx, 'tcx>,
	lvalue_pref: LvaluePreference,
	index_ty: Ty<'tcx>)
	-> Option<(/*index type*/ Ty<'tcx>, /*element type*/ Ty<'tcx>)>
	{
	let adjusted_ty = autoderef.unambiguous_final_ty();
	debug!("try_index_step(expr={:?}, base_expr={:?}, adjusted_ty={:?}, \
	index_ty={:?})",
	expr,
	base_expr,
	adjusted_ty,
	index_ty);
	// First, try built-in indexing.
	match (adjusted_ty.builtin_index(), &index_ty.sty) {
	(Some(ty), &ty::TyUint(ast::UintTy::Us)) | (Some(ty), &ty::TyInfer(ty::IntVar(_))) => {
	debug!("try_index_step: success, using built-in indexing");
	let adjustments = autoderef.adjust_steps(lvalue_pref);
	self.apply_adjustments(base_expr, adjustments);
	return Some((self.tcx.types.usize, ty));
	}
	_ => {}
	}
	for &unsize in &[false, true] {
	let mut self_ty = adjusted_ty;
	if unsize {
	// We only unsize arrays here.
	if let ty::TyArray(element_ty, _) = adjusted_ty.sty {
	self_ty = self.tcx.mk_slice(element_ty);
	} else {
	continue;
	}
	}
	// If some lookup succeeds, write callee into table and extract index/element
	// type from the method signature.
	// If some lookup succeeded, install method in table
	let input_ty = self.next_ty_var(TypeVariableOrigin::AutoDeref(base_expr.span));
	let method = self.try_overloaded_lvalue_op(
	expr.span, self_ty, &[input_ty], lvalue_pref, LvalueOp::Index);
	let result = method.map(|ok| {
	debug!("try_index_step: success, using overloaded indexing");
	let method = self.register_infer_ok_obligations(ok);
	let mut adjustments = autoderef.adjust_steps(lvalue_pref);
	if let ty::TyRef(region, mt) = method.sig.inputs()[0].sty {
	adjustments.push(Adjustment {
	kind: Adjust::Borrow(AutoBorrow::Ref(region, mt.mutbl)),
	target: self.tcx.mk_ref(region, ty::TypeAndMut {
	mutbl: mt.mutbl,
	ty: adjusted_ty
	})
	});
	}
	if unsize {
	adjustments.push(Adjustment {
	kind: Adjust::Unsize,
	target: method.sig.inputs()[0]
	});
	}
	self.apply_adjustments(base_expr, adjustments);
	self.write_method_call(expr.hir_id, method);
	(input_ty, self.make_overloaded_lvalue_return_type(method).ty)
	});
	if result.is_some() {
	return result;
	}
	}
	None
	}

lookup_indexing does something weird with builtin indexing, I think because arrays do not implement the Index/IndexMut traits. You might need to add a BuiltinIndexCandidate or some variant of it something to method lookup to get around this. You should avoid the call to write_method_call or undo it (by removing the entries write_method_call inserted) because otherwise you'll have weird borrow errors.

Note: feature gating

This is a big improvement to operator lookup, which we might not want to be active by default. Initially, we should probably keep the old operator lookup code, and switch between the old and the new code using feature gating.

[rustyseris]

I would like to give it a shot!

[arielb1]

@rustyseris

That's cool. This is a nice quality-of-life improvement I'm looking forward to seeing. If you need any help, I'm @arielb1 on gitter.

[rustyseris]

I've studied a long time the code and the documentation to have a glimse on the working of the code i was going to work with.

I'm coming back to you to present a work-in-progress to be sure i'm on the good track :
rustyseris@858a0d8

I think I should use the Op enum defined here directly instead of having a is_assign flag.
https://github.com/rustyseris/rust/blob/858a0d89f7dcf271a163e05935b9985417a429d0/src/librustc_typeck/check/op.rs#L517
The main problem here is that I'm not sure if I can put it in public. It will not leak outside the check module, that's for sure.

I've taken some shortcut for now using unwrap(), i should add some error handling code instead of making the whole compiler panic x) but i'm not sure what exactly i should do.

[peckpeck]

Hi, I have a mostly working MVP for this
ie I can have autoref/autoderef on the self part of binary operators.
A lot is still missing, but i'm wondering what I should do next

[nikomatsakis]

@peckpeck interesting! Where is it?

[peckpeck]

Here : https://github.com/peckpeck/rust/tree/autoref_op
But i got a little bit carried away, it doesn't work as is, i committed in a non working state and i can't make it work again.
Sorry, this is my first attempt at reading the compiler source code and i do a lot of experiment with the code to understand how it works.

It looks like confirm_method mess up with the caller's state, even with the exact same return value as with original code, the result is not accepted when i pass through it

[peckpeck]

As for the second argument part i looked into it and saw that most rust_type_check::check::method::* code assume that there is only one parameter which can be autoref/autoderef
There will be a lot of

Simple matter of Coding™

[peckpeck]

I could use some help in my exploration, I'm pretty sure there are some side effect to the calls of probe_for_name and confirm_method but i can't find which ones.

[peckpeck]

Progress information: it is now feature gated with #![feature(operator_autoref)]

It works for unary ops and self in binary ops, but any attempt with something invalid may break the compilation or the resulting binary.

next step is the hard part : implementing autoref for the rhs if any

[peckpeck]

Hi, i've now got a working implementation for some use cases, the probe loop is still not checking all use cases and some questions remain, but I think it's starting to be usable.

[peckpeck]

It works \o/ and passes existing tests (the current behaviour is unchanged)
Now I need to write tests to exhibit the new behaviour and fix the search loop (it currently tries everything including mutability change for example)

What would be the next step after this ?

[nikomatsakis]

@peckpeck you can open a PR and put "r? @nikomatsakis" in it

[peckpeck]

Hi, i will be offline for a week, so the PR will wait a little bit

[pnkfelix]

visiting for T-compiler backlog bonanza.

Its awesome that @peckpeck picked up the ball and ran with it here, as evidenced at https://github.com/peckpeck/rust/tree/autoref_op

But, since nothing has landed in tree yet, we still want the tracking issue's status label to reflect that. (@peckpeck , feel free to reach out if you need help turning your branch into a PR.)

@rustbot label: S-tracking-unimplemented

[jmintb]

Can I pick this up if it is still relevant?