{"id":4901,"date":"2022-06-22T18:07:06","date_gmt":"2022-06-22T23:07:06","guid":{"rendered":"https:\/\/neosmart.net\/blog\/?p=4901"},"modified":"2022-06-23T15:51:52","modified_gmt":"2022-06-23T20:51:52","slug":"prettysize-0-3-release-and-a-weakness-in-rusts-type-system","status":"publish","type":"post","link":"https:\/\/neosmart.net\/blog\/prettysize-0-3-release-and-a-weakness-in-rusts-type-system\/","title":{"rendered":"PrettySize 0.3 release and a weakness in rust’s type system"},"content":{"rendered":"

\"PrettySize\"<\/a>I’m happy to announce that a new version of size<\/code>, the PrettySize.NET<\/a> port for rust, has been released<\/a> and includes a number of highly requested features and improvements.<\/p>\n

The last major release of the size<\/code> crate was 0.1.2, released in December of 2018. It was feature complete with regards to its original purpose: the (automatic) textual formatting of file sizes for human-readable printing\/display purposes. It would automatically take a file size, pick the appropriate unit (KB, MB, GB, etc) to display the final result in, and choose a suitable precision for the floating numeric component. It had support for both base-10 (KB, MB, GB, etc) and base-2 (KiB, MiB, GiB, etc) types, and the user could choose between them as well as override how the unit was formatted. In short, it did one thing and did it right.<\/p>\n

<\/p>\n

A brief recap of the size<\/code> crate to date<\/h4>\n

Some time after its release, there was a request made<\/a> to add support for mathematical operations on strongly-typed Size<\/code> types (without having to go to an intermediate “raw” bytes value and back) that I originally approached with some gusto, but ended up dismayed by some restrictions of the rust type system that made it difficult to write generic code that could support the full gamut of what a user could reasonably expect to be able to do (more on this later).<\/p>\n

As the size<\/code> crate covered the functionality we needed out of it here at NeoSmart Technologies and as there were valid workarounds for composing\/calculating sizes (via the .bytes()<\/code> escape hatch<\/a>), there wasn’t a pressing need to tackle those limitations and other projects took priority meaning size<\/code> didn’t see any updates since then. But it never sat well with me that I left my git working tree in an unclean state and had open issues languishing unresolved, and from time to time I would always think of going back and issuing an update… but you know how that goes.<\/p>\n

However, in a recent discussion apropos “genuine limitations of the rust type system that frustrate people that otherwise love rust” I raised the issue that I ran into and that finally got me hot and bothered enough to finally tackle a new size<\/code> release with the requested support for mathematical operators and more.<\/p>\n

Rust’s problem with commutative mathematical operations<\/h4>\n

So what’s this about a problem in rust’s type system? Well, with the caveat that it’s importance is almost certainly overinflated in my eyes, the issue lies with how mathematical operations (impl<\/code>s of core::ops::{Add, Sub, Mul, Div}<\/code> and others) are written and how that conflicts with rust’s orphan rule, which forbids you from implementing a trait for a foreign type (defined in a different crate).<\/p>\n

After publishing, I realized that this article heavily uses the LHS and RHS abbreviations, but never defines what they stand for! LHS is “left-hand side” and RHS is “right-hand side” and they denote (for a binary mathematical operation) what side of the operator a token is on. e.g. in 42 apples + 17 oranges<\/code>, the LHS is “42 apples,” while the RHS has a magnitude of 17 with a unit of “oranges.”<\/p>\n

Let’s take a look at how we would normally implement (in rust) support for a mathematical operation like foo * bar<\/code> where Foo<\/code> and Bar<\/code> are different types, both local to the current crate:<\/p>\n

use core::ops::Mul;\r\n\r\nstruct Foo(i32);\r\nstruct Bar(i32);\r\n\r\n\/\/\/ Here, Bar is the RHS type and Foo is the LHS type, \r\n\/\/\/ i.e. this impl is used for `let prod = foo * bar`\r\nimpl Mul<Bar> for Foo {\r\n    type Output = i32;\r\n    \r\n    fn mul(self, other: Bar) -> Self::Output {\r\n        self.0 * other.0\r\n    }\r\n}\r\n\r\n\/\/\/ Here, Foo is the RHS type and Bar is the LHS type, \r\n\/\/\/ i.e. this impl is used for `let prod = bar * foo`\r\nimpl Mul<Foo> for Bar {\r\n    type Output = i32;\r\n    \r\n    fn mul(self, other: Foo) -> Self::Output {\r\n        self.0 * other.0\r\n    }\r\n}\r\n\r\nfn main() {\r\n    println!(\"{}\", Foo(7) * Bar(6));\r\n    println!(\"{}\", Bar(6) * Foo(7));\r\n}\r\n<\/code><\/pre>\n
You can try this online<\/a> in the rust playground.<\/em><\/p>\n
The above code demonstrates the commutative property of scalar multiplication: foo * bar<\/code> is the same as bar * foo<\/code> and returns the same result, both in type (here, i32<\/code>) and magnitude (42<\/code> in this example).<\/p>\n
It’s important for a type system to allow (or even require) you to write out separate implementations for each of the two commutative permutations because not all mathematical operations (or even all multiplications) are commutative. For example, while addition is generally commutative, subtraction isn’t (4 - 2<\/code> gives a different result from 2 - 4<\/code>) – and multiplication of matrices M<\/code> and N<\/code> may not only give different results for M * N<\/code> as compared to N * M<\/code>, one of those operations may be valid while the other is an error!<\/p>\n
So far, we haven’t run into any issues. But let’s say we have a bunch of different types, all of which (for reasons we won’t get into) can be boiled down to an integer equivalent and we want to support commutative multiplication for them all. It sounds like a textbook case for the use of generics: define a trait AsInt<\/code>, have each type implement it however it likes, then implement core::ops::Mul<\/code> via the AsInt<\/code> trait:<\/p>\n
use core::ops::Mul;\r\n\r\ntrait AsInt {\r\n    fn as_int(&self) -> i32;\r\n}\r\n\r\nstruct Foo(i32);\r\nstruct Bar(i32);\r\n\r\nimpl AsInt for Foo {\r\n    fn as_int(&self) -> i32 { self.0 }\r\n}\r\n\r\nimpl AsInt for Bar {\r\n    fn as_int(&self) -> i32 { self.0 }\r\n}\r\n\r\nimpl<Lhs: AsInt, Rhs: AsInt> Mul<Rhs> for Lhs {\r\n    type Output = i32;\r\n    \r\n    fn mul(self, other: Rhs) -> Self::Output {\r\n        self.as_int() * other.as_int()\r\n    }\r\n}\r\n<\/code><\/pre>\n
You can try this online<\/a> in the rust playground.<\/em><\/p>\n
Unfortunately, this doesn’t compile:<\/p>\n
error[E0210]<\/a>: type parameter `Lhs` must be used as the type parameter for some local type (e.g., `MyStruct<Lhs>`)<\/span>\r\n  --> src\/main.rs:18:6\r\n<\/a>   |\r\n18 | impl<Lhs: AsInt, Rhs: AsInt> Mul<Rhs> for Lhs {\r\n   |      ^^^ type parameter `Lhs` must be used as the type parameter for some local type\r\n   |\r\n   = note: implementing a foreign trait is only possible if at least one of the types for which it is implemented is local<\/span>\r\n   = note: only traits defined in the current crate can be implemented for a type parameter<\/span>\r\n\r\nFor more information about this error, try `rustc --explain E0210`.\r\nerror: could not compile `playground` due to previous error<\/span><\/code><\/pre>\n
The problem is that while all the types and the traits in this implementation are indeed local, the rust compiler doesn’t check if we are in violation of the orphan rule by checking which types implement the (local) trait we are implementing (another) trait against – it just checks to see if the implementing type itself is local. You can actually use a generic parameter implementing any (foreign or local) trait in your impl<\/code>, but you can’t implement against that generic type directly – you can only forward it as a generic parameter to a local type.<\/p>\n
Sidebar: Quare rust’s orphan rule and its limitations?<\/h5>\n
The most succinct PLT answer to this is that it’s because “local types” is a closed set (a new local type can never be added without changing your code and its API) while “types implementing local trait” is (or could be) an open set: a downstream user of your crate\/library may implement your trait on their type at a later date, and suddenly we could have a conflict. You might be tempted to think “that’s on them,” and I wouldn’t blame you (and might even agree) but the problems don’t stop there – we absolutely need the ability to implement both local and foreign traits, but a crate or library upstream<\/em> of yours (or even the standard library itself) might implement the same foreign trait against types implementing another foreign trait, and then the conflict would be your problem, in your code.<\/p>\n
Of course the rust compiler could be smarter about this and allow a combination of only certain permutations of impl\/for local\/foreign types\/traits to get around these restrictions (e.g. allow implementing anything for a local type, implementing only sealed traits inaccessible to downstream users for foreign types, etc) and while there are open issues and rfcs for some of these, the road to hell is paved with good intentions and there are a thousand pitfalls.1<\/a><\/sup> Long story short, the situation is what it is (for now) for $reasons and until that changes, these restrictions on commutative operations for generic types aren’t going anywhere.<\/p>\n
Back to the issue at hand<\/h5>\n
You can kind of work around this by abusing Deref<\/code> with an output that’s some intermediate type exposing a reference to an i32<\/code> (because we actually have an underlying i32<\/code> in this case, and are not just calculating one out of the blue each time), but deref coercion<\/a> will only get you so far.<\/p>\n
For the particular case of Size<\/code>, we just need to implement commutative multiplication of Size * number<\/code> and number * Size<\/code> so it turns out we can actually side-step this entire debate by manually writing out a million or so different impl<\/code>s, one for each primitive numeric type (macros help here!). Then multiply those by four, because you need to write a separate impl<\/code> for each of Foo * Bar<\/code>, Foo * &Bar<\/code>, &Foo * Bar<\/code> and &Foo * &Bar<\/code>. Lots of code, but conceptually simple.<\/p>\n
Except it turns out not to be so simple after all. Here’s an example that demonstrates commutative multiplication of a type (but not a reference to a type) with an i32<\/code>\u00a0value:<\/p>\n
use core::ops::Mul;\r\n\r\n#[derive(Debug, Copy, Clone)]\r\nstruct Foo(i32);\r\n\r\nimpl Mul<Foo> for i32 {\r\n    type Output = Foo;\r\n    \r\n    fn mul(self, other: Foo) -> Self::Output {\r\n        Foo(self * other.0)\r\n    }\r\n}\r\n\r\nimpl Mul<i32> for Foo {\r\n    type Output = Foo;\r\n    \r\n    fn mul(self, other: i32) -> Self::Output {\r\n        Foo(self.0 * other)\r\n    }\r\n}\r\n\r\nfn main() {\r\n    println!(\"{:?}\", Foo(7) * 6);\r\n    println!(\"{:?}\", 6 * Foo(7));\r\n}\r\n<\/code><\/pre>\n
You can try this online<\/a> in the rust playground.<\/em><\/p>\n
It works great. This time we are returning a strongly-typed Foo<\/code> rather than an i32<\/code> scalar value, commutative multiplication works fine, the code compiles, and prints the expected output.<\/p>\n
We originally wanted to make this generic over all primitive numeric types, so that if the user has a num: u8<\/code> or a float: f64<\/code> lying around, they can just perform the multiplication automatically without getting a type mismatch error like you would with the above if you tried to multiply by some already-typed value that rust can’t coerce\/infer to be an i32<\/code> (which our impl is specifically for):<\/p>\n
fn main() {\r\n    println!(\"{:?}\", Foo(7) * 6_u8);\r\n    println!(\"{:?}\", 6_f32 * Foo(7));\r\n}\r\n<\/code><\/pre>\n
You can try this online<\/a> in the rust playground.<\/em><\/p>\n
Which gives the following (expected) type errors:<\/p>\n
error[E0308]<\/a>: mismatched types<\/span>\r\n  --> src\/main.rs:23:31\r\n<\/a>   |\r\n23 |     println!(\"{:?}\", Foo(7) * 6_u8);\r\n   |                               ^^^^ expected `i32`, found `u8`\r\n   |\r\nhelp: change the type of the numeric literal from `u8` to `i32`\r\n<\/span>   |\r\n23 |     println!(\"{:?}\", Foo(7) * 6_i32);\r\n   |                                 ~~~\r\n\r\nerror[E0277]<\/a>: cannot multiply `f32` by `Foo`<\/span>\r\n  --> src\/main.rs:24:28\r\n<\/a>   |\r\n24 |     println!(\"{:?}\", 6_f32 * Foo(7));\r\n   |                            ^ no implementation for `f32 * Foo`\r\n   |\r\n   = help: the trait `Mul<Foo>` is not implemented for `f32`\r\n<\/span>\r\nSome errors have detailed explanations: E0277, E0308.\r\nFor more information about an error, try `rustc --explain E0277`.<\/code><\/pre>\n
We said we can’t use generics to implement this support, but we can add a second pair of impl Mul<\/code> for u8<\/code> to get this to work, right?<\/p>\n
use core::ops::Mul;\r\n\r\n#[derive(Debug, Copy, Clone)]\r\nstruct Foo(i32);\r\n\r\nimpl Mul<Foo> for i32 {\r\n    type Output = Foo;\r\n    \r\n    fn mul(self, other: Foo) -> Self::Output {\r\n        Foo(self * other.0)\r\n    }\r\n}\r\n\r\nimpl Mul<i32> for Foo {\r\n    type Output = Foo;\r\n    \r\n    fn mul(self, other: i32) -> Self::Output {\r\n        Foo(self.0 * other)\r\n    }\r\n}\r\n\r\nimpl Mul<Foo> for u8 {\r\n    type Output = Foo;\r\n    \r\n    fn mul(self, other: Foo) -> Self::Output {\r\n        Foo(self as i32 * other.0)\r\n    }\r\n}\r\n\r\nimpl Mul<u8> for Foo {\r\n    type Output = Foo;\r\n    \r\n    fn mul(self, other: u8) -> Self::Output {\r\n        Foo(self.0 * other as i32)\r\n    }\r\n}\r\n\r\nfn main() {\r\n    println!(\"{:?}\", Foo(7) * 6_u8);\r\n    println!(\"{:?}\", 6_i32 * Foo(7));\r\n}\r\n<\/code><\/pre>\n
You can try this online<\/a> in the rust playground.<\/em><\/p>\n
Indeed, this adds support for multiplying a Foo<\/code> by a u8<\/code> or the other way around, just as we wanted. We also still have support for multiplying Foo<\/code> by i32<\/code> (and vice-versa) as well. Great! This is what we wanted, right? Ergonomics +100 achievement unlocked!<\/p>\n
Unfortunately, no. While we\u00a0did<\/em> add support for multiplying by u8<\/code> or i32<\/code> typed values, we broke something probably much more important: the ability to multiply by an untyped (or at least, not explicitly typed) literal:<\/p>\n
use core::ops::Mul;\r\n\r\n#[derive(Debug)]\r\nstruct Foo(i32);\r\n\r\nimpl Mul<Foo> for i32 {\r\n    type Output = Foo;\r\n\r\n    fn mul(self, other: Foo) -> Self::Output {\r\n        Foo(self * other.0)\r\n    }\r\n}\r\n\r\nimpl Mul<Foo> for u8 {\r\n    type Output = Foo;\r\n    \r\n    fn mul(self, other: Foo) -> Self::Output {\r\n        Foo(self as i32 * other.0)\r\n    }\r\n}\r\n\r\nfn main() {\r\n    let prod = 7 * Foo(6);\r\n    assert_eq!(prod.0, 42);\r\n}\r\n<\/code><\/pre>\n
You can try this online<\/a> in the rust playground.<\/em><\/p>\n
This breaks in a rather weird way: you’d expect that if there’s any confusion about what a type is, it’s about whether 7<\/code> is an i32<\/code>\u00a0or u8<\/code> here. Indeed, that’s what’s happening internally, but that’s not what the error surfaced by the rust compiler says:<\/p>\n
error[E0282]<\/a>: type annotations needed<\/span>\r\n  --> src\/main.rs:39:9\r\n<\/a>   |\r\n39 |     let prod = 7 * Foo(6);\r\n   |         ^^^^^\r\n   |\r\n   = note: type must be known at this point<\/span>\r\nhelp: consider giving `prod` an explicit type\r\n<\/span>   |\r\n39 |     let prod: _ = 7 * Foo(6);\r\n   |              +++\r\n<\/code><\/pre>\n
Weird. We know (or at least, can reasonably surmise) the problem is with the ambiguity in the literal 7<\/code> and whether the compiler should invoke the Mul<Foo> for i32<\/code> impl or the Mul<Foo> for u8<\/code> impl, but the compiler says the problem is actually with the missing return type for the entire operation (which is always Foo<\/code> because that’s the Mul::Output<\/code> we have specified for both)! In fact, an older version of the compiler produces a better message<\/a>:<\/p>\n
<snip>\r\n\r\nerror[E0283]<\/a>: type annotations needed<\/span>\r\n  --> src\/main.rs:39:19\r\n<\/a>   |\r\n39 |     let prod1 = 7 * Foo(6);\r\n   |                   ^ cannot infer type for type `{integer}`\r\n   |\r\nnote: multiple `impl`s satisfying `{integer}: Mul<Foo>` found\r\n  --> src\/main.rs:22:1\r\n<\/a>   |\r\n22 | impl Mul<Foo> for i32 {\r\n   | ^^^^^^^^^^^^^^^^^^^^^\r\n...\r\n30 | impl Mul<Foo> for u8 {\r\n   | ^^^^^^^^^^^^^^^^^^^^\r\n<\/code><\/pre>\n
However, let’s just take the latest rustc<\/code> at its word and add the missing Foo<\/code> type to the let prod = ...<\/code> expression:<\/p>\n
fn main() {\r\n    let prod: Foo = 7 * Foo(6);\r\n    assert_eq!(prod.0, 42);\r\n}\r\n<\/code><\/pre>\n
And everything magically works<\/a>! But we didn’t actually\u00a0solve<\/em> the problem we were dealing with, we just worked around the resulting compiler error – something each of our users would have to do any time they relied on type inference to multiply a scalar number by a typed Foo<\/code> (interesting tidbit: this doesn’t happen the other way around, when multiplying a Foo<\/code> by a scalar value – I’m not sure why, but I’ve opened bugs for these issues: [1<\/a>], [2<\/a>]).<\/p>\n
To recap:<\/p>\n
    \n
  • Rust’s orphan rule prevents us from implementing commutative addition\/multiplication for types implementing a trait, which isn’t a complete blocker if you’re the only one that’s ever going to be implementing them because you can use macros or good, old copy-and-paste to work around that limitation and implement the operation manually. Half the operations can be generic over RHS (because impl<Rhs: ...> Mul<Rhs> for SpecificType<\/code> is perfectly legal) but the other half need to be manually spelled out. If you’re doing just two or three types, it’s fairly manageable but since you need 4 * M * N<\/code> impls in total (accounting for the ref\/non-ref permutations), it can quickly spiral into insanity.<\/li>\n
  • A (temporary?) bug? quirk? limitation? in the rust compiler stops us from manually implementing commutative operations with the various numeric literals, because even though rust has a (silent) integer inference preference for i32<\/code> and a default floating point type of f64<\/code>, the presence of multiple impls breaks type inference in interesting ways.<\/li>\n<\/ul>\n
    \n
    Just published a long article on a weakness in the #rust<\/a> type system when it comes to commutative operations and how to preserve backwards compatibility even when making breaking changes.https:\/\/t.co\/Wodf9rfEF2<\/a><\/p>\n
    \u2014 Mahmoud Al-Qudsi (@mqudsi) June 22, 2022<\/a><\/p><\/blockquote>\n