{"id":5812,"date":"2021-03-31T07:00:43","date_gmt":"2021-03-31T14:00:43","guid":{"rendered":"http:\/\/writeasync.net\/?p=5812"},"modified":"2021-03-29T19:44:49","modified_gmt":"2021-03-30T02:44:49","slug":"letter-boxed-rust-impl-part-1","status":"publish","type":"post","link":"http:\/\/writeasync.net\/?p=5812","title":{"rendered":"Letter Boxed: Rust impl, part 1 (basics)"},"content":{"rendered":"

We’ve already set up the development environment<\/a>, so let’s write some Rust code!<\/p>\n

A good place to start is with the bottom layer data structures, known as Str<\/a> and Ch<\/a> in the C# version. To review, Ch<\/code> is an enumeration representing the characters A-Z (and a None<\/code> value == 0), while Str<\/code> packs up to 12 Ch<\/code> values into 5-bit chunks plus a 4-bit length for a total of 64 bits. Already we have one small point of contention, in that Rust has a very similarly named primitive string slice type called str<\/code><\/a>. To make things a bit less confusing, we can use the name St<\/code> here instead.<\/p>\n

Going test first, we will begin by translating the following C# unit test into Rust:<\/p>\n

\r\n        [Fact]\r\n        public void Empty()\r\n        {\r\n            Str s = default(Str);\r\n\r\n            s.Length.Should().Be(0);\r\n            s.ToString().Should().Be(string.Empty);\r\n            Enumerable.Range(0, 12).Select(i => s[i]).Should().BeEquivalentTo(\r\n                Ch.None,\r\n                Ch.None,\r\n                Ch.None,\r\n                Ch.None,\r\n                Ch.None,\r\n                Ch.None,\r\n                Ch.None,\r\n                Ch.None,\r\n                Ch.None,\r\n                Ch.None,\r\n                Ch.None,\r\n                Ch.None);\r\n        }\r\n<\/pre>\n
Here is one possible reimagining:<\/p>\n
\r\n    #[test]\r\n    fn empty() {\r\n        let s = St::empty();\r\n\r\n        assert_eq!(0, s.len());\r\n        assert_eq!("", s.to_string());\r\n        let expected = vec![\r\n            Ch::None,\r\n            Ch::None,\r\n            Ch::None,\r\n            Ch::None,\r\n            Ch::None,\r\n            Ch::None,\r\n            Ch::None,\r\n            Ch::None,\r\n            Ch::None,\r\n            Ch::None,\r\n            Ch::None,\r\n            Ch::None,\r\n        ];\r\n        let actual: Vec<Ch> = (0..12).map(|i| s[i]).collect();\r\n        assert_eq!(expected, actual);\r\n    }\r\n<\/pre>\n
This already gives us a lot to chew on. Going line by line, let’s dive into the details. First, we assign an empty string value using an associated function<\/a> (acting as our constructor<\/a>) of the St<\/code> struct. Then we ensure the len()<\/code> and to_string()<\/code> functions return sensible values (0 and empty string, respectively). At the end, we prepare a Vec<\/code><\/a> of expected Ch<\/code> values and use a range<\/a> to select (i.e. map<\/a>) each index of the St<\/code> and collect this into an “actual” Vec<\/code>, asserting that it has the right contents. Note that due to Rust’s excellent type inference<\/a>, we only have to explicitly use a type for the result of the collect<\/code> method<\/a>.<\/p>\n
One possible implementation that satisfies this test is as follows:<\/p>\n
\r\nuse std::{\r\n    fmt::{Display, Formatter, Result},\r\n    ops::Index,\r\n};\r\n\r\n#[derive(Clone, Copy, Debug, PartialEq)]\r\npub enum Ch {\r\n    None,\r\n}\r\n\r\npub struct St(u64);\r\n\r\nimpl St {\r\n    fn empty() -> St {\r\n        St(0)\r\n    }\r\n\r\n    fn len(&self) -> u8 {\r\n        0\r\n    }\r\n}\r\n\r\nimpl Display for St {\r\n    fn fmt(&self, f: &mut Formatter) -> Result {\r\n        write!(f, "{}", "")\r\n    }\r\n}\r\n\r\nimpl Index<u8> for St {\r\n    type Output = Ch;\r\n\r\n    fn index(&self, _index: u8) -> &Self::Output {\r\n        &Ch::None\r\n    }\r\n}\r\n<\/pre>\n
Again, we’ll just go through this line by line. The top section is the necessary use declarations<\/a> to avoid having to fully qualify the various library type names that follow. Next, we have the Ch<\/code> enumeration<\/a> which consists of a single member for now. It is annotated with a derive attribute<\/a> telling the compiler to produce default implementations of four traits (roughly equivalent to interfaces<\/a> in other languages). We want the Copy trait<\/a> because we want to be able to freely pass Ch<\/code> by value like any other primitive type. We also need Clone as it is a super-trait of Copy<\/a> (which will implicitly reuse the “cheap” copy behavior in this case). Debug is a nice-to-have trait<\/a> for most types, but we are actually forced to use it here because assert macros require it<\/a> (e.g. in case they have to produce an error message). Similarly, we need PartialEq<\/a> since we can’t reasonably assert equality without it! We could have also used strong equivalence via Eq<\/a>, but for now we’re just doing the minimum necessary to pass the tests (or in this case, the compiler!).<\/p>\n
The rest is code for the St<\/code> struct. We start with the definition which is just about the simplest tuple struct<\/a> you can create — a single 64-bit unsigned integer. Then we have the implementation block<\/a> with stubs for the empty<\/code> and len<\/code> functions. The last two blocks are trait implementations<\/a>. The first is for Display, which is roughly equivalent to IFormattable in the .NET world<\/a> — this is what backs the to_string<\/a> method. The fmt<\/code> function here is basically just boilerplate; we use a Formatter<\/a> with the write macro and format string<\/a> to produce an empty string. Finally, we have a stub indexer implementation which enables us to use square brackets to return a Ch<\/code> item (defined as an associated type<\/a>, similar to a class-level typedef in C++<\/a>). Rust doesn’t have direct operator overloading<\/a> as such, but achieves the same through the traits in std::ops<\/a>.<\/p>\n
The next test introduces the concept of appending a Ch<\/code> to create a longer St<\/code>:<\/p>\n
\r\n#[test]\r\nfn one_char() {\r\n    let s = St::empty() + Ch::A;\r\n\r\n    assert_eq!(1, s.len());\r\n    assert_eq!("A", s.to_string());\r\n    let expected = vec![\r\n        Ch::A,\r\n        Ch::None,\r\n        Ch::None,\r\n        Ch::None,\r\n        Ch::None,\r\n        Ch::None,\r\n        Ch::None,\r\n        Ch::None,\r\n        Ch::None,\r\n        Ch::None,\r\n        Ch::None,\r\n        Ch::None,\r\n    ];\r\n    let actual: Vec<Ch> = (0..12).map(|i| s[i]).collect();\r\n    assert_eq!(expected, actual);\r\n}\r\n<\/pre>\n
Here we use the + operator, which requires us to implement the Add<\/code> trait<\/a> for St<\/code>, as well as a Display implementation for Ch<\/code> and more reasonable definitions for len<\/code> and fmt<\/code>: [see commit on GitHub]<\/a><\/p>\n
Once we get to the two character test case we end up with most of core implementation code: [see commit on GitHub]<\/a><\/p>\n
After that, it’s all pretty mechanical, culminating in the 12 character test (the maximum our St<\/code> can hold) at which point all Ch<\/code> values from A-Z are accounted for: [see commit on GitHub]<\/a><\/p>\n
While developing the above code, I benefited greatly from the exhaustiveness of the Rust match operator<\/a>. When adding new enum values, Rust could automatically tell me if I was missing any cases, e.g.:<\/p>\n
\r\nimpl Add<Ch> for St {\r\n    type Output = St;\r\n\r\n    fn add(self, rhs: Ch) -> Self::Output {\r\n        let c = match rhs {\r\n            Ch::None => 0,\r\n            Ch::A => 1,\r\n            Ch::B => 2,\r\n            Ch::C => 3,\r\n        };\r\n        St((self.0 + 1) | (c << (4 + 5 * self.len())))\r\n    }\r\n}\r\n<\/pre>\n
This code simply doesn’t compile because it only covers four of the possible 27 cases (A-Z + None). Of course, this only works for certain kinds of matches (typically, those involving enums); less help is available for instance in the inverse of the above operation:<\/p>\n
\r\nimpl Index<u8> for St {\r\n    type Output = Ch;\r\n\r\n    fn index(&self, index: u8) -> &Self::Output {\r\n        let c = (self.0 >> (4 + 5 * index)) & 0x1F;\r\n        match c {\r\n            1 => &Ch::A,\r\n            2 => &Ch::B,\r\n            3 => &Ch::C,\r\n            _ => &Ch::None,\r\n        }\r\n    }\r\n}\r\n<\/pre>\n
This code would not compile without the _ placeholder<\/a>, unless we specifically listed out every possible numeric value. This is in theory achievable for a u8<\/code> type (“only” 256 values) but would be out of the question for any larger data type. The compiler is great at reducing the kinds of tests we need<\/a>, but alas we can’t throw them all away.<\/p>\n
We have a good start yet there is a lot more work to do. Let’s continue our Rust journey in the next post.<\/p>\n","protected":false},"excerpt":{"rendered":"
We’ve already set up the development environment, so let’s write some Rust code! A good place to start is with the bottom layer data structures, known as Str and Ch in the C# version. To review, Ch is an enumeration… <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[91,101,41],"tags":[],"class_list":["post-5812","post","type-post","status-publish","format-standard","hentry","category-design","category-native","category-tdd"],"_links":{"self":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5812","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=5812"}],"version-history":[{"count":9,"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5812\/revisions"}],"predecessor-version":[{"id":5821,"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5812\/revisions\/5821"}],"wp:attachment":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5812"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5812"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5812"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}