Inference failure with for-loop and associated type that contains lifetimes

[cessen]

System Info:

Xubuntu 13.10
rustc 1.0.0-nightly (d3732a1 2015-02-06 23:30:17 +0000)
binary: rustc
commit-hash: d3732a1
commit-date: 2015-02-06 23:30:17 +0000
host: x86_64-unknown-linux-gnu
release: 1.0.0-nightly

I'm trying to create a trait for formatting lines of text (e.g. do line wrapping, manage font size, etc.). I want implementers to only have to provide an iterator and a method for producing those iterators, and everything else is provided with default implementations that utilize those.

The following is a minified version of what I'm trying to do that produced an error.

Code:

pub trait LineFormatter<'a> {
    type Iter: Iterator<Item=&'a str> + 'a;
    fn iter(&'a self, line: &'a str) -> Self::Iter;

    fn dimensions(&'a self, line: &'a str) {
        for grapheme in self.iter(line) {
            // Do some stuff
        }
    }
}

fn main() {
    println!("Hello world!");
}

Error:

error: unable to infer enough type information about `_`; type annotations required [E0282]
src/main.rs:6         for grapheme in self.iter(line) {
                          ^~~~~~~~

This error seems strange enough on its own, because rustc ought to be able to infer the type of grapheme from the return type of Self::Iter::next(). So I thought perhaps the problem is that it somehow lacked type information about self.iter(). Thus I changed the code so that the iterator type is explicit, and got a different error:

Code:

pub trait LineFormatter<'a> {
    type Iter: Iterator<Item=&'a str> + 'a;
    fn iter(&'a self, line: &'a str) -> Self::Iter;

    fn dimensions(&'a self, line: &'a str) {
        let mut iter: Self::Iter = self.iter(line);
        for grapheme in iter {
            // Do some stuff
        }
    }
}

fn main() {
    println!("Hello world!");
}

Error (with backtrace):

error: internal compiler error: cannot relate bound region: ReFree(39, BrNamed(DefId { krate: 0, node: 66 }, 'a)) <= ReEarlyBound(66, TypeSpace, 0, 'a)
src/main.rs:6         let mut iter: Self::Iter = self.iter(line);
                                    ^~~~~~~~~~
note: the compiler unexpectedly panicked. this is a bug.
note: we would appreciate a bug report: http://doc.rust-lang.org/complement-bugreport.html
note: run with `RUST_BACKTRACE=1` for a backtrace
thread 'rustc' panicked at 'Box<Any>', /home/rustbuild/src/rust-buildbot/slave/nightly-dist-rustc-linux/build/src/libsyntax/diagnostic.rs:129

stack backtrace:
   1:     0x7fac8cdf4250 - sys::backtrace::write::h361f9c7ed16d6f6eUsy
   2:     0x7fac8ce17950 - failure::on_fail::h69f5f434699d11ccOWF
   3:     0x7fac8cd777d0 - rt::unwind::begin_unwind_inner::hc4455d84b00b874blBF
   4:     0x7fac8a142040 - rt::unwind::begin_unwind::h13236156776379767181
   5:     0x7fac8a141fd0 - diagnostic::SpanHandler::span_bug::h5ec31613fa5cf53fBUE
   6:     0x7fac8af3d770 - middle::infer::region_inference::RegionVarBindings<'a, 'tcx>::make_subregion::h5d6daa2e030d47a0rqv
   7:     0x7fac8aee07f0 - middle::infer::region_inference::RegionVarBindings<'a, 'tcx>::make_eqregion::hc14a7b534b218055Qpv
   8:     0x7fac8aee04c0 - middle::infer::equate::Equate<'f, 'tcx>.Combine<'tcx>::regions::h7b601a41d445840dl9p
   9:     0x7fac8aeed100 - middle::infer::combine::Combine::substs_variances::h505559559396905773
  10:     0x7fac8aeed040 - middle::infer::combine::Combine::substs::h14093085151659474206
  11:     0x7fac8aeecd80 - middle::infer::combine::Combine::trait_refs::h11806062172857789792
  12:     0x7fac8aee83b0 - middle::infer::higher_ranked::C.HigherRankedRelations<'tcx>::higher_ranked_sub::h11345065735083413059
  13:     0x7fac8af5a350 - middle::infer::InferCtxt<'a, 'tcx>::sub_poly_trait_refs::h778d518607558f21afA
  14:     0x7fac8aff14c0 - middle::traits::select::SelectionContext<'cx, 'tcx>::match_poly_trait_ref::hf672789565982957nXS
  15:     0x7fac8aff0e80 - middle::traits::select::SelectionContext<'cx, 'tcx>::evaluate_where_clause::closure.78472
  16:     0x7fac8aff0850 - middle::traits::select::SelectionContext<'cx, 'tcx>::evaluate_where_clause::hd8fd18d51d7963f09pR
  17:     0x7fac8aff0d00 - iter::Filter<I, P>.Iterator::next::h666365327850076025
  18:     0x7fac8aff0a50 - vec::Vec<T>.Extend<T>::extend::h12082665635362077775
  19:     0x7fac8afeb4c0 - middle::traits::select::SelectionContext<'cx, 'tcx>::assemble_candidates::he7da8b218a200b5000Q
  20:     0x7fac8afde060 - middle::traits::select::SelectionContext<'cx, 'tcx>::candidate_from_obligation::hdd5f5f479a261580bFQ
  21:     0x7fac8afc3260 - middle::traits::select::SelectionContext<'cx, 'tcx>::select::h505d79adb1bd97bb3hQ
  22:     0x7fac8afd1a10 - middle::traits::project::assemble_candidates_from_impls::hf1079e75d7f576a9xfP
  23:     0x7fac8afcdb80 - middle::traits::project::opt_normalize_projection_type::hcd0d88e52c938941ZOO
  24:     0x7fac8afbabc0 - middle::traits::project::normalize_projection_type::ha0d2856f827aa82cHNO
  25:     0x7fac8afba380 - middle::traits::fulfill::FulfillmentContext<'tcx>::normalize_projection_type::h56c4a230d5438853zYN
  26:     0x7fac8c569df0 - check::FnCtxt<'a, 'tcx>::normalize_associated_type::h4c37786edcd185bfd7n
  27:     0x7fac8c5429b0 - check::FnCtxt<'a, 'tcx>.AstConv<'tcx>::projected_ty_from_poly_trait_ref::h26f1885bfd9232a3tMn
  28:     0x7fac8c5ce9d0 - astconv::ast_ty_to_ty::closure.33365
  29:     0x7fac8c56c8b0 - astconv::ast_ty_to_ty::hde8725d1f33fc37dS5u
  30:     0x7fac8c560150 - check::GatherLocalsVisitor<'a, 'tcx>.Visitor<'tcx>::visit_local::h7cca3eba209aa7564Jm
  31:     0x7fac8c542e10 - check::check_fn::hc7c6534eca9dcbb42Qm
  32:     0x7fac8c55eb70 - check::check_bare_fn::hc4a0a43726ab3cfekGm
  33:     0x7fac8c562a30 - check::check_method_body::h6885088892563788gen
  34:     0x7fac8c556470 - check::check_item::hf0f84b92a48dd09eBZm
  35:     0x7fac8c622530 - check_crate::closure.34477
  36:     0x7fac8c61ce00 - check_crate::h8571887ed583eda9PKA
  37:     0x7fac8d3e6b20 - driver::phase_3_run_analysis_passes::h8f5a5e5500230bd1oGa
  38:     0x7fac8d3cca40 - driver::compile_input::hcb43bced2a0b021bCba
  39:     0x7fac8d49ebe0 - run_compiler::hb81cf958c2f963666ac
  40:     0x7fac8d49d270 - thunk::F.Invoke<A, R>::invoke::h6159218808669033746
  41:     0x7fac8d49c1a0 - rt::unwind::try::try_fn::h8268217050585033268
  42:     0x7fac8ce83a90 - rust_try_inner
  43:     0x7fac8ce83a80 - rust_try
  44:     0x7fac8d49c450 - thunk::F.Invoke<A, R>::invoke::h8703575304585054118
  45:     0x7fac8ce03e40 - sys::thread::thread_start::h35f66aa7ce5d7277LCB
  46:     0x7fac86e44ea0 - start_thread
  47:     0x7fac8c9f1999 - __clone
  48:                0x0 - <unknown>

I wouldn't be surprised if I'm implementing this stuff wrong, but since it's producing an ICE it seemed like I ought to submit a bug report.

[edwardw]

The ICE is due to #20300, which already has an fix about to be merged. With that out of the way, the more interesting issue here is the type inference error. The compiler is happy if LineFormatter doesn't have a lifetime parameter:

#[cfg(not(works))]
pub trait LineFormatter<'a> {
    type Iter: Iterator<Item=&'a str> + 'a;
    fn iter(&'a self, line: &'a str) -> Self::Iter;

    fn dimensions(&'a self, line: &'a str) {
        for _grapheme in self.iter(line) {
        }
    }
}

#[cfg(works)]
pub trait LineFormatter {
    type Iter: Iterator<Item=&'static str>;
    fn iter<'a>(&'a self, line: &'a str) -> Self::Iter;

    fn dimensions<'a>(&'a self, line: &'a str) {
        for _grapheme in self.iter(line) {
        }
    }
}

fn main() {}

It is probably related to #21974. And this ticket could use a more precise title; it is more about trait lifetime parameter interferes with type inference than ICE.

[edwardw]

This turns out to have the same root cause as #21750 and #22077.

[tamird]

as @edwardw says, the ICE here is fixed. @steveklabnik could you remove the label?

[arielb1]

The inference problem also occurs with

pub trait LineFormatter<'a> {
    type Iter: Iterator<Item=&'a str> + 'a;
    fn iter(&'a self, line: &'a str) -> Self::Iter;

    fn dimensions(&'a self, line: &'a str) {
        let mut iter: Self::Iter = self.iter(line);
        <_ as IntoIterator>::into_iter(iter);
    }
}

fn main() {}

[ehiggs]

I think I still got this ICE.

Fedora 22
$ rustc -V -v
rustc 1.3.0-nightly (d33cab1b1 2015-07-22)
binary: rustc
commit-hash: d33cab1b1fa4943a4bf37baa8c7421e672df10c7
commit-date: 2015-07-22
host: x86_64-unknown-linux-gnu
release: 1.3.0-nightly

The error:

$ RUST_BACKTRACE=1 rustc error.rs --crate-type lib
<std macros>:6:1: 6:32 error: the trait `core::convert::From<PythonObjectDowncastError<'_>>` is not implemented for the type `PyErr<'_>` [E0277]
<std macros>:6 $ crate:: convert:: From:: from ( err ) ) } } )
               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
<std macros>:1:1: 6:48 note: in expansion of try!
error.rs:58:12: 58:41 note: expansion site
<std macros>:6:1: 6:32 help: run `rustc --explain E0277` to see a detailed explanation
error.rs:82:22: 82:36 error: internal compiler error: cannot relate bound region: '_#6r <= ReEarlyBound(315, TypeSpace, 0, 'python)
error.rs:82         E::extract::<Self::Prepared>(&obj)                                      
                                 ^~~~~~~~~~~~~~
note: the compiler unexpectedly panicked. this is a bug.
note: we would appreciate a bug report: https://github.com/rust-lang/rust/blob/master/CONTRIBUTING.md#bug-reports
thread 'rustc' panicked at 'Box<Any>', ../src/libsyntax/diagnostic.rs:176

stack backtrace:
   1:     0x7fbb207304fe - sys::backtrace::write::hf666ea5132cf7b53Zws
   2:     0x7fbb207387b5 - panicking::on_panic::h831316f04c76720d4lx
   3:     0x7fbb206f9a3e - rt::unwind::begin_unwind_inner::h2cf94599b7bd3df8H1w
   4:     0x7fbb1db1d7ac - rt::unwind::begin_unwind::h6329212554763340604
   5:     0x7fbb1db1d74b - diagnostic::SpanHandler::span_bug::h5af5760a7fae491eb9A
   6:     0x7fbb1e7ec6b2 - middle::infer::region_inference::RegionVarBindings<'a, 'tcx>::make_subregion::h04db0d55be1dde413Vx
   7:     0x7fbb1e7a9a0c - middle::infer::equate::Equate<'a, 'tcx>.TypeRelation<'a, 'tcx>::regions::hd979b4b26580e2f2USs
   8:     0x7fbb1e7ac8d5 - middle::infer::sub::Sub<'a, 'tcx>.TypeRelation<'a, 'tcx>::relate_with_variance::h4446034952128033161
   9:     0x7fbb1e7ac722 - iter::_&'a mut I.Iterator::next::h2609482268122873928
  10:     0x7fbb1e7abdce - middle::ty_relate::relate_substs::h9009371242841443843
  11:     0x7fbb1e7ab480 - middle::ty_relate::relate_item_substs::h10613823414329269412
  12:     0x7fbb1e7ab200 - middle::ty_relate::ty..TraitRef<'tcx>.Relate<'a, 'tcx>::relate::h7757131364328309241
  13:     0x7fbb1e808b5b - middle::infer::InferCtxt<'a, 'tcx>::sub_trait_refs::h8f39013586f6e956TPB
  14:     0x7fbb1e89a3f4 - middle::traits::select::SelectionContext<'cx, 'tcx>::match_impl::hc67e696eb9545d7byuW
  15:     0x7fbb1e89f6ee - middle::traits::select::SelectionContext<'cx, 'tcx>::assemble_candidates_from_impls::closure.92164
  16:     0x7fbb1e89ee44 - middle::ty::TraitDef<'tcx>::for_each_relevant_impl::h12250870464500226399
  17:     0x7fbb1e89bbf0 - middle::traits::select::SelectionContext<'cx, 'tcx>::assemble_candidates::h5fc2c8c9d01b49c2yfU
  18:     0x7fbb1e88ee2e - middle::traits::select::SelectionContext<'cx, 'tcx>::candidate_from_obligation::h20de267bd3f86ac54TT
  19:     0x7fbb1e76a58f - middle::traits::select::SelectionContext<'cx, 'tcx>::select::h5810505dcd1952f9fyT
  20:     0x7fbb1e8850cc - middle::traits::project::assemble_candidates_from_impls::h490678811ca30ed0XAS
  21:     0x7fbb1e881cef - middle::traits::project::opt_normalize_projection_type::h46208f7641ab277bv6R
  22:     0x7fbb1e87350f - middle::traits::project::normalize_projection_type::h5ba4514321bf3a83j5R
  23:     0x7fbb1e87300d - middle::traits::fulfill::FulfillmentContext<'tcx>::normalize_projection_type::h7d135b74bb6f9b5fSaR
  24:     0x7fbb1ff0bc12 - check::FnCtxt<'a, 'tcx>::normalize_associated_type::h85a12e550530b4e2PVo
  25:     0x7fbb1fee7459 - check::FnCtxt<'a, 'tcx>.AstConv<'tcx>::projected_ty_from_poly_trait_ref::hd6a5f269b842679fazo
  26:     0x7fbb1ff52309 - astconv::finish_resolving_def_to_ty::h9ad99f78bde11eb4jLv
  27:     0x7fbb1ff1179c - astconv::ast_ty_to_ty::hb97056c0a4f0eb997Mv
  28:     0x7fbb1fe88520 - check::instantiate_path::hf0baba98444853ccMrs
  29:     0x7fbb1ff4883b - check::check_expr_with_unifier::h2221075350936743126
  30:     0x7fbb1fee898d - check::callee::check_call::h091b7e0ee90152ff4Ql
  31:     0x7fbb1ff2ed9a - check::check_expr_with_unifier::h3918486800583074951
  32:     0x7fbb1ff04a3b - check::check_block_with_expected::hd1194d6ba43baad7g0r
  33:     0x7fbb1fee827a - check::check_fn::h00277a9d75327c0eOFn
  34:     0x7fbb1fefe838 - check::check_bare_fn::hfddc865292f08a28rvn
  35:     0x7fbb1ff0a32c - check::check_method_body::h30075ff1c310ad04i8n
  36:     0x7fbb1fefc953 - check::check_item_body::h3f2e3887100269894Vn
  37:     0x7fbb1fefe464 - check::check_item_types::he86a18cc64ef1db4Ysn
  38:     0x7fbb1ffbb66b - check_crate::h26b1f5c95f18291cpTC
  39:     0x7fbb20c967e9 - driver::phase_3_run_analysis_passes::closure.16389
  40:     0x7fbb20c9512b - middle::ty::ctxt<'tcx>::create_and_enter::h7731474059721291206
  41:     0x7fbb20c90101 - driver::phase_3_run_analysis_passes::h16775793763798904703
  42:     0x7fbb20c742e0 - driver::compile_input::h94a4cd7284b1abf6Tba
  43:     0x7fbb20d57f53 - run_compiler::h57cf503a33efb4e7A7b
  44:     0x7fbb20d559ce - boxed::F.FnBox<A>::call_box::h1072113940123396054
  45:     0x7fbb20d552f9 - rt::unwind::try::try_fn::h14039827517923182205
  46:     0x7fbb207b38c8 - rust_try_inner
  47:     0x7fbb207b38b5 - rust_try
  48:     0x7fbb20723977 - rt::unwind::try::inner_try::h54ab330eae71d9c1AXw
  49:     0x7fbb20d55518 - boxed::F.FnBox<A>::call_box::h2790679698620608799
  50:     0x7fbb207373f1 - sys::thread::Thread::new::thread_start::hfedf7e48a39f0895D6v
  51:     0x7fbb1a338554 - start_thread
  52:     0x7fbb20392f3c - __clone
  53:                0x0 - <unknown>

Extracting the code as best I can I got it down to the following:

use std::marker::PhantomData; 

pub struct GILGuard;
trait PythonObject<'a> {
    fn dummy() -> &'a i32;
}

#[derive(Copy, Clone)]                                                          
pub struct Python<'p>(PhantomData<&'p GILGuard>);                               

pub struct PyErr<'p> {                                                          
    pub ptype : PyObject<'p>,                                                   
}  

type PyResult<'p, T> = Result<T, PyErr<'p>>;

pub struct PyObject<'a> {
    dummy : &'a i32
}

impl <'p> PyObject<'p> { 
    pub fn cast_into<T>(self) -> Result<T, PythonObjectDowncastError<'p>> where T: PythonObjectWithCheckedDowncast<'p> {
        PythonObjectWithCheckedDowncast::downcast_from(self)                    
    }   
}

pub struct PythonObjectDowncastError<'p>(pub Python<'p>);                       
pub trait PythonObjectWithCheckedDowncast<'p> : PythonObject<'p> {              
    fn downcast_from(PyObject<'p>) -> Result<Self, PythonObjectDowncastError<'p>>;
}   

impl <'p> PythonObjectWithCheckedDowncast<'p> for PyObject<'p> {                
    #[inline]                                                                   
    fn downcast_from(obj: PyObject<'p>) -> Result<PyObject<'p>, PythonObjectDowncastError<'p>> {
        Ok(obj)                                                                 
    }
}

impl <'p> PythonObject<'p> for PyObject<'p> {                                   
    fn dummy() -> &'p i32 { &7 }
}

pub trait PyExtractor<'python, 'source, 'prepared> {                            
    type Prepared;                                                              
    fn extract<T>(prepared: &'prepared Self::Prepared) -> PyResult<'python, T>  
        where T: PythonObjectWithCheckedDowncast<'python> ;                     
}                                                                               

pub struct PyObjectExtractor;                                                   

impl <'python, 'source, 'prepared> PyExtractor<'python, 'source, 'prepared>     
    for PyObjectExtractor {                                                     
    type Prepared = &'source PyObject<'python>;                                 

    #[inline]                                                                   
    fn extract<T>(&&ref obj: &'prepared Self::Prepared) -> PyResult<'python, T> 
        where T: PythonObjectWithCheckedDowncast<'python> {                     
        Ok(try!(obj.clone().cast_into()))                                       
    }                                                                           
}                                                                               

pub trait ExtractPyObject<'python, 'source, 'prepared> {                        
    type Prepared;                                                              

    fn prepare_extract(obj: &'source PyObject<'python>) -> PyResult<'python, Self::Prepared>;

    fn extract<E: PyExtractor<'python, 'source, 'prepared>>(prepared: &'prepared Self::Prepared) -> PyResult<'python, Self>;
}                                                                               

impl <'python, 'source, 'prepared, T> ExtractPyObject<'python, 'source, 'prepared>
    for T where T: PythonObjectWithCheckedDowncast<'python> {                   

    type Prepared = &'source PyObject<'python>;                                 

    #[inline]                                                                   
    fn prepare_extract(obj: &'source PyObject<'python>) -> PyResult<'python, Self::Prepared> {
        Ok(obj)                                                                 
    }                                                                           

    #[inline]                                                                   
    fn extract<E: PyExtractor<'python, 'source, 'prepared>>(&&ref obj: &'prepared Self::Prepared) -> PyResult<'python, T> {
        E::extract::<Self::Prepared>(&obj)                                      
    }                                                                           
}

[arielb1]

@ehiggs

That is a different issue, which I have split into #27281

[arielb1]

This seems to work on Rust 1.10.