title: Generically implementing a trait for all concrete types implementing another trait
body: <p>I'm pretty new to rust, so this might be a stupid question with an obvious answer, but I don't know the answer yet. I've just read the book and then decided to implement some algorithms I'm familiar with, to get a feeling for the language. That, however, took me down a dark path to a side project that went a little deeper into the language than I had planned for...</p>
  <p>Anyway, I'm now playing around with some code for working with indices and offsets in some algorithms in a type-safe way. I have indices into different arrays and strings and want to prevent using an index from one array to be used into another and things like that. So, I have defined new types for different kinds of indices, those with different domains, and for offsets between them. I don't allow comparisons between domains, I can subtract indices to get an offset and I can add and subtract indices and offsets and stuff like that. Further, I can define which types of objects indices can subscript, so an index into a string can only index a string and not, say, a suffix array, where another type is necessary.</p>
  <p>This mostly works. I have a bunch of macros for defining what objects are allowed to do. For example, with this</p>
  <pre class="lang-rust prettyprint-override"><code>def_offset!(Offset);
  def_idx!(
      Idx
      with offset Offset
      with sub [
          Vec&lt;T&gt;[Idx] =&gt; T,
          [T][Idx] =&gt; T
      ]
  );
  </code></pre>
  <p>I define a generic <code>Offset</code> that you can do arithmics on but nothing else, and then an index type <code>Idx</code> that can do arithmics with <code>Offset</code> and index vectors and slices. The arithmetic for indices looks like this right now, but I'm not done experimenting with it</p>
  <pre class="lang-rust prettyprint-override"><code>macro_rules! def_idx_ops {
      ($idx:ident with offset $offset:ident) =&gt; {
          // You can add an index and an offset
          def_op!($idx + $offset =&gt; $idx);
          def_op!($offset + $idx =&gt; $idx);
          def_op!($idx += $offset);
  
          // You can subtract an index and an offset
          def_op!($idx - $offset =&gt; $idx);
          def_op!($idx -= $offset);
  
          // You can subtract two indices, but you can't add
          // them (adding indices do not usually make sense)
          def_op!($idx - $idx =&gt; $offset);
  
          // You can add scalars to indices.
          def_op!($idx + usize =&gt; $idx);
          def_op!(usize + $idx =&gt; $idx);
          def_op!($idx += usize);
  
          // You can subtract scalars from indices.
          def_op!($idx - usize =&gt; $idx);
          def_op!(usize - $idx =&gt; $idx);
          def_op!($idx -= usize);
      };
  }
  </code></pre>
  <p>where the <code>def_op!</code> macro implements the appropriate trait for the types involved in the operator.</p>
  <p>There is more code generation going on here than I like, but I couldn't figure out how to write generic code any other way. But maybe I will after this question.</p>
  <p>See, now I got to implementing ranges over these types. They come out of the box if you just want a range</p>
  <pre><code>let r = Idx(0)..Idx(10)
  </code></pre>
  <p>but you can't iterate over them. For that, you need to implement some traits. With the code below, it works for the type <code>Idx</code>:</p>
  <pre class="lang-rust prettyprint-override"><code>// Trait for implementing iteration through i..j ranges for Idx.
  // NB: This requires nightly; the iter::Step trait is unstable.
  impl std::iter::Step for Idx {
      fn steps_between(start: &amp;Self, end: &amp;Self) -&gt; Option&lt;usize&gt; {
          match (start.0, end.0) {
              (i, j) if i &gt; j =&gt; None,
              (i, j) =&gt; Some(j - i),
          }
      }
      fn forward_checked(start: Self, count: usize) -&gt; Option&lt;Self&gt; {
          Some(start + count) // Ignoring overflow here...
      }
      fn backward_checked(start: Self, count: usize) -&gt; Option&lt;Self&gt; {
          match start.0 {
              i if i &lt; count =&gt; None,
              _ =&gt; Some(start - count),
          }
      }
  }
  </code></pre>
  <p>But it only works for the concrete type <code>Idx</code>. If I try to make a generic implementation, I run into all kinds of trouble.</p>
  <p>This is my current attempt, but it works as little as the others I have made:</p>
  <pre class="lang-rust prettyprint-override"><code>trait RangeIndex&lt;T&gt;: NumWrapper&lt;T&gt; + std::ops::Add&lt;T&gt; + std::ops::Sub&lt;T&gt;
  where
      T: num::traits::NumCast,
  {
  }
  
  impl&lt;Idx&gt; std::iter::Step for Idx
  where
      Idx: RangeIndex&lt;usize&gt;,
  {
      fn steps_between(start: &amp;Self, end: &amp;Self) -&gt; Option&lt;usize&gt; {
          match (start.wrapped(), end.wrapped()) {
              (i, j) if i &gt; j =&gt; None,
              (i, j) =&gt; Some(j - i),
          }
      }
      fn forward_checked(start: Self, count: usize) -&gt; Option&lt;Self&gt; {
          Some(start + count) // Ignoring overflow here...
      }
      fn backward_checked(start: Self, count: usize) -&gt; Option&lt;Self&gt; {
          match start.wrapped() {
              i if i &lt; count =&gt; None,
              _ =&gt; Some(start - count),
          }
      }
  }
  </code></pre>
  <p>The <code>RangeIndex&lt;T&gt;</code> trait puts the constraints I need on the index type, and <code>NumWrapper</code> is a trait for the numbers I'm wrapping in indices and offsets.</p>
  <pre class="lang-rust prettyprint-override"><code>pub trait Wrapper&lt;Wrapped&gt; {
      fn wrapped(&amp;self) -&gt; Wrapped;
  }
  
  pub trait NumWrapper&lt;Wrapped&gt;:
      Wrapper&lt;Wrapped&gt; + std::cmp::PartialEq + std::cmp::PartialOrd
  where
      Wrapped: num::traits::NumCast,
  {
      fn cast_to_wrapped&lt;T: num::traits::NumCast&gt;(val: T) -&gt; Wrapped {
          num::cast(val).unwrap()
      }
  }
  </code></pre>
  <p>(There is a little more to the wrapped objects, but this is the only relevant part for treating them as numbers).</p>
  <p>This generic code does not work. The compiler suggests that I make the trait <code>dyn</code> but I assure you that I do not want to do that. I don't want any dynamic dispatch or polymorphism at all. I have concrete types; I want implementations for those. Nothing more and nothing less.</p>
  <p>It is a small matter to just generate the code with macros, like I have with the operators. But I am reinventing generic code now, and that is deeply unsatisfying. I feel the same way about generating the operators instead of having code for traits and then just implementing the appropriate trait for each type.</p>
  <p>Is it impossible to say &quot;for any type that implements this particular trait, give me a concrete implementation of this trait like this&quot;? It is really all I want. For any <code>Idx</code> that implements these traits, give me this <code>std::iter::Step</code>.</p>
  <p>And if I can get that, I would love to do the same with the operators</p>
  <pre class="lang-rust prettyprint-override"><code>impl&lt;LHS, RHS, RES&gt; std::ops::Add&lt;RHS&gt; for LHS {
      where //&quot;some constraint involving both LHS and RHS and RES&quot;
            Constraint&lt;LHS,RHS,RES&gt; // yeah, might not be able to do this
      type Output = RES;
      fn add(self, rhs: $rhs) -&gt; Self::Output {
          RES(RES::cast_to_wrapped(self.wrapped()) + 
              RES::cast_to_wrapped(rhs.wrapped()))
      }
  }
  </code></pre>
  <p>One can dream, at least.</p>
  <p>Anyway, I don't mind generating the operators, but I see it as a problem if I have to give up on generic code that works with these types. If I can't even run through a range, then this project is going to die pretty soon. Using macros for every generic function just isn't an attractive idea. (Well, I can still write generic functions, I just cannot implement traits, so it is not all that bad, but it still is pretty bad).</p>
  <p>Really, what I want to tell Rust is that &quot;for all types that implement the following traits&quot;, &quot;give me an instance of this generic code&quot;. Exactly what I can get with macros, I suppose, but using generics that were made for this purpose instead.</p>
  <p>Surely there must be some well know trick to generically implementing a trait without resorting to <code>dyn</code>?</p>
  <p><strong>UPDATE</strong></p>
  <p>I've put a related exampled on playground. The full example where I need the ranges is a bit too long, but I think the smaller example hits the same issue. There, I have a trait for adding wrapped numbers</p>
  <pre class="lang-rust prettyprint-override"><code>// Local trait for adding ... a substitute for the range code I need
  trait MyAdd&lt;Rhs&gt; {
      type Res;
      fn my_add(self, rhs: Rhs) -&gt; Self::Res;
  }
  </code></pre>
  <p>I can implement <code>std::ops::Add</code> just from this interface, but no matter how I try, I cannot do it without explicitly implementing that trait for each type I define. There are a couple of examples of my attempts, but needless to say, they do not work.</p>
  <p><a href="https://play.rust-lang.org/?version=stable&amp;mode=debug&amp;edition=2021&amp;gist=af5f9087a2736904e0c09f3f1674826f" rel="nofollow noreferrer">Playground</a></p>