Make crate no_std compatible

[encounter]

Notable changes:

• All tests were wrapped in #[cfg(test)] mod test {}, so that tests can use extern crate std; while building the library itself with no_std. Required to use insta within the test modules. (Disabling whitespace changes in the diff view makes this easier to read!) This is also why the snapshot tests were renamed: they need to include the new test module in the path.
• udiff's to_writer implementations were wrapped in #[cfg(feature = "std")], given their reliance on std::io.

The cargo test --no-default-features should handle testing the no_std paths in CI already.

Things I'm not sure about:

• How to handle deadlines in no_std land. Right now, it defines

  #[cfg(not(any(feature = "std", feature = "wasm32_web_time")))]
  pub type Instant = ();
  

  which I'm not happy with. Maybe the *_deadline functions should be omitted entirely when compiling without a time provider? This is a more involved change, which is why I did not do it in this PR. Other suggestions welcome.
• hashbrown was added as a dependency because alloc::collections only contains BTreeMap. Rust's std::collections::HashMap requires a random source. With my changes:

  #[cfg(not(feature = "std"))]
  use hashbrown::HashMap;
  #[cfg(feature = "std")]
  use std::collections::HashMap;
  

  Unfortunately, I don't think there's a way to remove the dependency if compiling with std, so it will always show up in the dependency list, regardless of if it's used. Alternatively, we could use BTreeMap for these instead? But that'd require a breaking API change. (Requiring Idx::Output: PartialOrd rather than Hash.) Again, suggestions appreciated.

[mitsuhiko]

How to handle deadlines in no_std land. Right now, it defines

Probably similar to how we are doing with WASM. We define an instant type that is made up and ignored. But yes, it would be better if the entire instant system was just not there if it cannot be provided.

Since adding std as a feature might require a major bump anyways, maybe this is the moment to clean up this entirely and take away the deadline functions if they cannot be provided.

Alternatively, we could use BTreeMap for these instead? But that'd require a breaking API change. (Requiring Idx::Output: PartialOrd rather than Hash.) Again, suggestions appreciated

Since we probably need to bump the major anyways, I think it would be sensible to change the bounds to also require PartialOrd. That leaves options open for alternatives internally.

[encounter]

I migrated the logic into _internal functions, and cfg'd out the _deadline functions if neither std or wasm32_web_time are enabled.

Regarding HashMap, I'm thinking either:

• Are we okay with hashbrown existing as a dependency but being unused when std is enabled? It seems to be a very common dependency. Alternatively, it could always be the HashMap, and we ignore std's.
• If it's really undesired, there could have a separate no_std feature that enables hashbrown. In lib.rs, we can require that either std or no_std is enabled, or both. That way people using the default features won't get the unnecessary dependency, and people who want to disable std can use default-features = false, features = ["no_std"], enabling the hashbrown dependency. I've seen this approach used in a couple of crates.

I was looking at the existing HashMap usages more, and I don't think BTreeMap would be the right thing to use for those.

[mitsuhiko]

I think the right course of action for hashbrown is to

1. use BTreeMap in no_std by default
2. have a hashbrown feature that switches it into a hashmap.

While I agree that a BTreeMap is not the right storage for either of the cases we have today, it might still make sense to have for when you don't opt in. I definitely do not want hashbrown as a general dependency. But we can also say that you need to opt in as otherwise you do not get any functionality associated with the hash maps which would break quite a bit of the crate.

[encounter]

Sorry for the delay. I implemented the suggestions:

• default-features = false -> alloc::collections::BTreeMap
• default-features = false, features = ["hashbrown"] -> hashbrown::HashMap
• default-features = true or features = ["std"] -> std::collections::HashMap

This required adding the Ord bound in a few places. Thankfully, the main diff/diff_deadline functions already had an Ord bound, so I doubt this will cause issues.

[encounter]

@mitsuhiko Are you still interested in these changes? Happy to make further modifications if necessary

[barrett-ruth]

Hi @encounter , I also have a change I'd like to make with respect to floating point diffs.

Would you like to work on a fork together? Not necessarily to actively maintain it, but have a new established repository with a few requested features.

Let me know! I couldn't find your contact on your website, shoot me an email at [email protected].

[ethteck]

@mitsuhiko sorry to nag, but I'm also looking for this feature in my project and am really hoping it can be merged upstream if it's acceptable to you. If there's anything I can do to help also, I'm happy to. thanks for your time and energy on this

[barrett-ruth]

@ethteck @encounter I have made a fork here and will soon publish the package to the crates.io registry with a new name (thinking likewise) right now.

I don't have much experience but would appreciate y'all migrating your prs or helping it (if you'd like!) in this port.