Id::from_name should be const

[alice-i-cecile]

What problem does this solve?

I want to be able to efficiently store constants for the Ids computed from const strings.

This is great when working with hybrid code-data workflows, where you want to quickly spawn an object in a scripting-like way without having to recompute the hash. It also adds some level of typo-resistance, as the name only needs to be typed in a single location.

What solution would you like?

Add const to Id::from_name.

How could this be implemented?

Unfortunately, it's not that simple.

Even when accepting only a String in from_name, adding const to the function below results in a number of compiler errors.

    pub fn from_name(name: String) -> Self {
        // Algorithm adopted from <https://cp-algorithms.com/string/string-hashing.html>

        let mut value = 0;
        let mut p_pow = 1;

        name.bytes().for_each(|byte| {
            value = (value + (byte as u64 + 1) * p_pow) % HASH_M;
            p_pow = (p_pow * HASH_P) % HASH_M;
        });

        Self::new(value)
    }

error[E0015]: cannot perform deref coercion on `std::string::String` in constant functions
    --> src\identifier.rs:64:9
     |
64   |         name.bytes().for_each(|byte| {
     |         ^^^^^^^^^^^^
     |
     = note: attempting to deref into `str`
note: deref defined here
    --> C:\Users\alice\.rustup\toolchains\stable-x86_64-pc-windows-msvc\lib/rustlib/src/rust\library\alloc\src\string.rs:2531:5
     |
2531 |     type Target = str;
     |     ^^^^^^^^^^^
note: impl defined here, but it is not `const`
    --> C:\Users\alice\.rustup\toolchains\stable-x86_64-pc-windows-msvc\lib/rustlib/src/rust\library\alloc\src\string.rs:2530:1
     |
2530 | impl ops::Deref for String {
     | ^^^^^^^^^^^^^^^^^^^^^^^^^^
     = note: calls in constant functions are limited to constant functions, tuple structs and tuple variants

error[E0015]: cannot call non-const fn `core::str::<impl str>::bytes` in constant functions
  --> src\identifier.rs:64:14
   |
64 |         name.bytes().for_each(|byte| {
   |              ^^^^^^^
   |
   = note: calls in constant functions are limited to constant functions, tuple structs and tuple variants

error[E0658]: mutable references are not allowed in constant functions
  --> src\identifier.rs:64:31
   |
64 |           name.bytes().for_each(|byte| {
   |  _______________________________^
65 | |             value = (value + (byte as u64 + 1) * p_pow) % HASH_M;
66 | |             p_pow = (p_pow * HASH_P) % HASH_M;
67 | |         });
   | |_________^
   |
   = note: see issue #57349 <https://github.com/rust-lang/rust/issues/57349> for more information

error[E0015]: cannot call non-const fn `<std::str::Bytes<'_> as Iterator>::for_each::<{closure@src\identifier.rs:64:31: 64:37}>` in constant functions
  --> src\identifier.rs:64:22
   |
64 |           name.bytes().for_each(|byte| {
   |  ______________________^
65 | |             value = (value + (byte as u64 + 1) * p_pow) % HASH_M;
66 | |             p_pow = (p_pow * HASH_P) % HASH_M;
67 | |         });
   | |__________^
   |
   = note: calls in constant functions are limited to constant functions, tuple structs and tuple variants

error[E0493]: destructor of `std::string::String` cannot be evaluated at compile-time
  --> src\identifier.rs:58:28
   |
58 |     pub const fn from_name(name: String) -> Self {
   |                            ^^^^ the destructor for this type cannot be evaluated in constant functions
...
70 |     }
   |     - value is dropped here

Some errors have detailed explanations: E0015, E0493, E0658.
For more information about an error, try `rustc --explain E0015`.
error: could not compile `leafwing_manifest` (lib) due to 5 previous errors

[Optional] What alternatives have you considered?

Swapping to a global append-only store of Names <-> Ids would work, but require unsafe and be more technically complex. If this approach was chosen, we may want to swap to an atomically incrementing identifier scheme, rather than a hash-derived one.

[alice-i-cecile]

Accepting a &str instead gets rid of the error around the destructor of String not being callable in const contexts. The difficulties with mutable references and for_each both seem feasible with a bit of ugly rewriting.

The primary remaining challenge is converting the string into something that represents its value that could be hashed. Currently we use bytes, but that's not the only option. str::as_bytes appears to be const, so we may be in business!

However, for is not allowed in const methods on stable Rust: see rust-lang/rust#87575. On the other hand, while does work! Perhaps this can work, with sufficiently ugly code.