Design question: where do I put my Traits?

I am writing two different crates at the moment:

  • one implementing kdtrees;
  • one using kdtrees.

One useful "kdtree" feature is efficient points extraction within a certain distance of a query point. That feature is exactly what is used in the second library mentioned above.

So far so good.

Now, instead of kdtrees, I could use many other structures (uniform grid, octree, etc.) or even "no structure" at all (calculate all distances directly). Each of those could be implemented and used instead of my kdtree implementation as long as they offer the same interface, the same behaviour.

Long story short: I want to encode that behaviour in a trait, but I struggle to see what the best approach would be.

  1. I could define the trait unifying the behaviour of all kdtree/grid/octree/etc. in the final library. In that case, the resulting trait is a simple type-system device used for polymorphism. If going that route, I'd need to create final-library-local type shims and any new type/datastructure must be explicitly included in the final library and acted upon to generate a valid type.

  2. Instead I could define the trait in its own crate and use it both in the data structure libraries in impl blocks (so using trait as a contract) and in the final library (using trait as dispatch mechanism). That approach looks very appealing but afaik is rarely seen out there; which seems suspicious. From my limited perspective, especially with version pinning, this looks like a great way do document/prevent API incompatibilities in a central place that is easy to search.

Is there anything blatant I did not consider? How would you do to keep dependees as rich/versatile/isolated as possible while making dependers able to use them in a safe way without systematically having to write proxy types?

I don't think you'd need a "shim" (I assume you mean new-type?) for (1). If the trait is defined in final library, then you can implement it for anything, including types in the rust std library, as needed.

With (2) you'd be more likely to run into problems not being able to implement the (now external) trait for types defined external to the current crate.

Yes, I meant new-type for shim... I see what you mean for (1) and I was wrong about it, though it means that all the libraries wishing to use a query point as described would have to "hardcode" something (i.e. an impl block) which might be necessary or even wanted (as you said, to provide your own implemenetion). But it sounds like a lot of boilerplate and increasing friction between the libs, i.e. you assume a certain behaviour from the external type to implement your trait, which only moves the interface problem and does not solve it, if that makes sense.