Unfortunately eager trait resolution

1

I'd like to write:

#![feature(specialization)]
use std::ops::Range;

trait Trait<T: ?Sized> {}

impl<T> Trait<T> for Range<T> {}

impl<'a, T: ?Sized, C> Trait<T> for C where C: Trait<&'a T> {} // <-- broken

So that, e.g., Trait<str> is implemented on Range<&str>. Unfortunately, rust seems to be eagerly evaluating the marked trait implementation. Is there a fundamental reason this can't work (i.e., could rust support this)?

2

The following works without specialization:

use std::ops::Range;
trait Trait<T: ?Sized> {}
impl<T> Trait<T> for Range<T> {}
impl<'a, T: ?Sized> Trait<T> for Range<&'a T> {}

I'm not quite following what you're trying to do in your original code.

3

I was trying to work around some specialization issues so I wanted my blanket impl to be strictly more general. After trying to explain it, I've realized it wouldn't work anyways so I'm back where I started...

Basically, I have:

trait OrderedRange<T: ?Sized> where T: Ord {
    fn range_cmp(&self, other: &T) -> Ordering;
}

I want the following impls:

// Covers OrderedRange<T> for Range<T>, OrderedRange<Box<T>> for T, etc...
impl<A: ?Sized, B> OrderedRange<A> for Range<B>
    where A: Ord + Borrow<B>, B: Ord
{
    fn range_cmp(&self, other: &A) -> Ordering {
        unimplemented!()
    }
}

// Covers OrderedRange<String> for Range<&str>, etc...
// i.e., the unsized borrows.
impl<'a, A: ?Sized, B: ?Sized> OrderedRange<A> for Range<&'a B>
    where A: Ord + Borrow<B>, B: Ord
{
    fn range_cmp(&self, other: &A) -> Ordering {
        unimplemented!()
    }
}

However, I can't do this with specialization because neither impl is more specific. So I thought I could replace the second impl with:

/// Means that OrderedRange<&A> implies OrderedRange<A>
impl<'a, T: 'a, A: ?Sized> OrderedRange<A> for T
    where T: OrderedRange<&'a A>, A: Ord
{
    default fn range_cmp(&self, other: &A) -> Ordering {
        (&**self).range_cmp(&other)
    }
}

But that (if it worked) would only fix the OrderedRange<T> for Range<&T> case.

4

So, I found a solution that works for all the range types (but it's exactly a nice solution)...

#![feature(optin_builtin_traits)]
use std::cmp::Ordering;
use std::ops::{Range, RangeFull};
use std::borrow::Borrow;
use std::marker::PhantomData;

trait OrderedRange<T: ?Sized> where T: Ord {
    fn range_cmp(&self, other: &T) -> Ordering;
}

impl<'a, T: ?Sized, R: ?Sized> OrderedRange<T> for &'a R
    where R: OrderedRange<T>,
          T: Ord,
{
    fn range_cmp(&self, other: &T) -> Ordering {
        (&**self).range_cmp(other)
    }
}

impl<'a, T: ?Sized + 'a> OrderedRange<T> for Range<&'a T>
    where T: Ord,
{
    fn range_cmp(&self, other: &T) -> Ordering {
        if other <= self.start {
            Ordering::Greater
        } else if other > self.end {
            Ordering::Less
        } else {
            Ordering::Equal
        }
    }
}

// Helps infer the correct type...
trait NotRef {}
impl NotRef for .. {}
impl<'a, T: ?Sized> !NotRef for &'a T {}

impl<T> OrderedRange<T> for Range<T>
    where T: Ord + NotRef,
{
    fn range_cmp(&self, other: &T) -> Ordering {
        if *other <= self.start {
            Ordering::Greater
        } else if *other > self.end {
            Ordering::Less
        } else {
            Ordering::Equal
        }
    }
}

impl<T> OrderedRange<T> for RangeFull where T: Ord {
    fn range_cmp(&self, _: &T) -> Ordering {
        Ordering::Equal
    }
}

struct Set<T>(PhantomData<T>);

impl<T> Set<T> {
    fn new() -> Self {
        Set(PhantomData)
    }
    fn query<K: ?Sized, Q>(&self, _query: Q)
        where K: Ord,
              T: Borrow<K>,
              Q: OrderedRange<K>
    {}
}


fn main() {
    let string_set: Set<String> = Set::new();
    let int_set: Set<u32> = Set::new();

    string_set.query("a".."b");
    string_set.query(String::from("a")..String::from("b"));
    string_set.query(&(String::from("a")..String::from("b")));
    int_set.query(0..100);
    int_set.query(..);
    int_set.query(&(..));
}