New Trait Bounds

[mitsuhiko]

One of the behaviors inherited from pijul are many of the original trait bounds. Unfortunately these make things quite hard to improve various aspects of the implementation. In particular for instance the main inputs for the diff functions look something like this:

pub fn diff<Old, New, D>(
    d: &mut D,
    old: &Old,
    old_range: Range<usize>,
    new: &New,
    new_range: Range<usize>,
) -> Result<(), D::Error>
where
    Old: Index<usize> + ?Sized,
    New: Index<usize> + ?Sized,
    D: DiffHook,
    New::Output: PartialEq<Old::Output>,
{
  // ...
}

There are two issues with this that need to be solved:

• Old::Output and New::Output are only required to be PartialEq to each other. In practice however it's significantly more useful for them to be the same type. This for instance allows one to put the items into a HashMap<&'a T, usize> for de-duplication. Patience gets around this currently by handlign each side separately and then to compare by the original value again which is unnecessary wasteful.
• There is no relationship of old to old_range and new to new_range. This both makes the code less than ideal to read but it also means that it's very hard to get rid of the bounds checks. In practice there is an argument to be made that any diffing shall be going through a deduplication step first at which point we might as well require things to look more like slices. Maybe the trait bounds can stay like this externally as a result.

[mitsuhiko]

The first issue is not as problematic. There is now a type called IdentifyDistinct which can work with the current trait bounds and still produces unique IDs for them.