Extract comparison traits for greater stdlib fidelity

[eggyal]

Since first publishing copse just a few weeks ago, there's been quite a bit of API churn—I hope it hasn't caused too much headache for many/any users? I rushed to publish too quickly. Apologies.

I am however now pretty comfortable with the v0.4 API and don't expect it to change significantly... except perhaps to accommodate the following idea.

I've been toying with

• essentially splitting the TotalOrder trait into four separate ones to reflect the standard library's Ord, PartialOrd, Eq and PartialEq traits;
• using a suitable analogue of the standard library's Borrow trait instead of the SortableBy trait, thereby providing much greater fidelity with the standard library collections.

I expect that, were this to happen, the arising four comparison traits (together with the default OrdTotalOrder implementation) and one borrow trait would be extracted into a separate library crate upon which copse would depend: let's call it stateful-cmp for now.

However, whilst this idea has some considerable architectural appeal, I am concerned about the ergonomics:

1. Users of copse would need to implement, for each total order that they define, all four comparison traits. The standard library has the same problem here, albeit in most cases it can be trivially accomplished by the provided derive macros; in our case the comparison is necessarily something non-standard (depending on runtime state) and so while a macro approach to implementing these traits is of course feasible, the invocation format will necessarily be something a little more bespoke/unfamiliar.

2. Furthermore there would need to be suitable implementations of our Borrow analogue. What would that analogue look like? The standard library's Borrow trait serves two purposes: to provide a method that converts &self into &Borrowed; and to assert that Borrowed preserves comparison (and hashing) behaviour with respect to Self.

   For maximum fidelity with the standard library, our analogue would have to be parameterised by the total order for which it asserts comparisons will be preserved—hence we would end up with different implementations of our Borrow analogue for each total order: whilst a macro could again reduce the boilerplate/ergonomic burden here, we could still feasibly end up with different conversions from &self into &Borrowed in each case, and I'm not sure there's any justification for that?

   The alternative is to split from our analogue of the Borrow trait its assertion of comparison preservation, so that it becomes more akin to the standard library's AsRef trait albeit with a reflexive blanket implementation (indeed we could just use the standard library's Borrow trait if it is acceptable to limit our notion of "borrowing" to types that meet its requirements). That assertion would then be made by some other trait, perhaps a mere marker subtrait like trait ComparisonPreserved<Borrowed, TotalOrder>: Borrow<Borrowed> {}.

   Either way, we would still have the same issue in providing blanket implementations as we currently have with SortableBy: we can either provide a blanket reflexive implementation for all total orders, or we can provide a blanket implementation of all standard library Borrows for the default OrdTotalOrder. Again, macros could help somewhat to reduce the boilerplate.

Overall this idea seems to come at the cost of not inconsiderable boilerplate, potentially eased by macros that in turn increase cognitive load. I'm not at present convinced that the benefit outweighs these issues, though I'd be delighted to hear thoughts?

Perhaps the most persuasive argument for this idea is that such a stateful-cmp crate could be of wider use outside of copse.

[eggyal]

In light of #17, this proposal will need modification. Rather than our analogue of Borrow merely be parameterised by the total order it will also need to accept a reference to such as argument in the conversion method: this not only negates the possibility of using the standard library's trait for that element of the behaviour, but furthermore provides justification (albeit in obscure edge cases) for different orderings having different implementations of the conversion method.

I wonder whether it'd be desirable/useful to retain something similar to the distinction we now have between SortableBy and SortableByWithOrder so that a simpler conversion trait (not parameterised by order, perhaps the standard library's) can be implemented in most cases and the more complex (parameterised) one implemented in those obscure edge cases for which it's required; or would that just be unnecessarily confusing? It feels like the simplest solution may indeed just be to have the parameterised version.

[eggyal]

I have an implementation of this approach in my contextual_cmp branch. You can use it today with the following in your Cargo.toml:

[patch.crates-io]
copse = { git = "https://github.com/eggyal/copse", branch = "contextual_cmp" }

Would love to have some feedback on this approach, especially with respect to ergonomics; I've actually been pleasantly surprised how the boilerplate has reduced versus the status quo, so right now I'm leaning towards accepting this change. But I can also see that it could be more confusing to grok, and particularly frustrating if impls all have to be provided without the contextual! macro for whatever reason.

I haven't yet documented any of the new items, but I have updated all existing documentation including the README. Hopefully that's enough for you to get started, but do shout if anything's unclear (which will also help me identify what requires documenting).