8.13.2015

Rust and the most elegant FSM

Finite state machines should be a foundation upon which Software Engineers build complex systems. In this post I want to show how Rust's enum type supports building FSM's in a very simple and elegant manner.


FSM, what?

For anyone who has studied Computer Science, finite state machines are drilled into your head without mercy (or should have been, go ask for you $'s back if these were not drilled into your head). The first CS class I took in college was basically all FSM's, DFA's (deterministic finite automaton) and Turing machines. I don't want to get into the difference between all of these, so I'm going to just refer to FSM's in general, of which Turing machines and DFA's are subsets. In this example I'm more specifically defining a DFA, as all of the states are known, and there is a begin and end.

Ok, but why is this important? FSM's can simplify problems where you have a known input and known outputs. Specifically what I want to use one for in this example is parsing, boring old parsing. It actually wasn't until I was in the industry that I truly began to appreciate how much simpler and more maintainable your code became if you took the time to define state machines to determine how to move from one state to another.

Background

Firstly, I'm still somewhat new to the Rust language, so when a "real" Rust person reads this, they'll probably complain that I've done xyz wrong, or should do it another way. Let me know! I'd love to understand what I could be doing better. I've been searching for a meaty project to work on to hone my skills in this language, and then I finally found one; It seems like there are security advisories that come out around DNS and specifically Bind all the time. Here is the list of all known Security Advisories in Bind9. Reading through some of the issues made me think, wtf, I'll just write a new DNS server in Rust, b/c you know, why not and it will be safe implicitly, right? While doing that, I was writing the parsers for the binary record data from the DNS rfc's and fell on a really nice way of doing FSM's in Rust.

Now in Java I've used lots of different FSM generators, because I wanted strong language guarantees, for reference, my favorite right now was written by a friend of mine and is annotation based called Tron. This is useful because Java's enums and other basic constructs are not quite as expressive as some of the expressions you can make in Rust.

On to the FSM!

The definition of what we need to parse from RFC1035:

3.1. Name space definitions
Domain names in messages are expressed in terms of a sequence of labels.
Each label is represented as a one octet length field followed by that
number of octets. Since every domain name ends with the null label of
the root, a domain name is terminated by a length byte of zero. The
high order two bits of every length octet must be zero, and the
remaining six bits of the length field limit the label to 63 octets or
less.
To simplify implementations, the total length of a domain name (i.e.,
label octets and label length octets) is restricted to 255 octets or
less. Although labels can contain any 8 bit values in octets that make up a
label, it is strongly recommended that labels follow the preferred
syntax described elsewhere in this memo, which is compatible with
existing host naming conventions. Name servers and resolvers must
compare labels in a case-insensitive manner (i.e., A=a), assuming ASCII
with zero parity. Non-alphabetic codes must match exactly.

There are some more sections that provide details on things like pointers, you can read the spec if you want. Here are the states (I used http://madebyevan.com/fsm/ to build this, which doesn't have edge avoidance so I added some extra states to keep the lines in order):

This state diagram basically represents the above, so I decided to translate this (minus the 'offset' and 'store' states) to Rust enums.

This ended up being pretty elegant. but first a side note on enums in Rust.

'enum' really?

So I've noticed this come up in discussions online a few times now. With questions like, "how do you enumerate a Rust enum?" (which has a really funny answer, IMO): You can't! Wait what? You can't enumerate a Rust enum? Why is it called an enum? No, seriously, I don't have an answer to this, why was it called 'enum', when you can't enumerate it's values (other then writing them in order, you can't in code treat them as an array or series as you can in other languages, Java/C/C++ to name a few).

I'm sure someone has an answer to that, but in the mean time I needed to clarify them in my mind. I think they should have been called 'union's because that is what they are most closely related to. In C a union is a data type which which occupies enough memory space to only hold the largest member of the union, but what C doesn't give you is a way to know which thing in that union it really is! (read more here: C unions)

What's cool in Rust is that it does tell you what's stored in the, ahem, enum. So you can write matching (or destructuring) logic like this:

if let MyEnum::Type1 = my_var {
   do_something_really_awesome();
}
Which is very powerful and cool.

FSM Now!

Ok so now for the super awesomeness of Rust. My enum is going to have four states, LabelLengthOrPointer == start, Label, Pointer, Root == end.

/// This is the list of states for the label parsing state machine
enum LabelParseState {
  LabelLengthOrPointer, // basically the start of the FSM
  Label(u8),   // storing length of the label
  Pointer(u8), // location of pointer in slice,
  Root,        // root is the end of the labels list, aka null
}

Ok, now for the code to run the state machine:

/// parses the chain of labels
/// this has a max of 255 octets, with each label being less than 63.
/// all names will be stored lowercase internally.
/// This will consume the portions of the Vec which it is reading...

pub fn parse(slice: &mut Vec<u8>) -> Result<Name, FromUtf8Error> {
  let mut state: LabelParseState = LabelParseState::LabelLengthOrPointer;
  let mut labels: Vec<String> = Vec::with_capacity(3); // www.example.com
  
  // assume all chars are utf-8. We're doing byte-by-byte operations,
  //   no endianess issues...
  // reserved: (1000 0000 aka 0800) && (0100 0000 aka 0400)
  // pointer: (slice == 1100 0000 aka C0), then 03FF & slice = offset
  // label: 03FF & slice = length; slice.next(length) = label
  // root: 0000

  loop {
    state = match state {
      LabelParseState::LabelLengthOrPointer => {
        // determine what the next label is
        match slice.pop() {
          Some(0) | None => LabelParseState::Root,
          Some(byte) if byte & 0xC0 == 0xC0 => 
                                           LabelParseState::Pointer(byte & 0x3F),
          Some(byte) if byte <= 0x3F => LabelParseState::Label(byte),
          _ => unimplemented!(),
        }
      },
      LabelParseState::Label(count) => {
        labels.push(try!(util::parse_label(slice, count))); 
        // reset to collect more data
        LabelParseState::LabelLengthOrPointer
      },
      LabelParseState::Pointer(offset) => {
        // lookup in the hashmap the label to use
        unimplemented!()
      },
      LabelParseState::Root => {
        // technically could return here...
        break;
      }
    }
  } 
  Ok(Name { labels: labels })
}
code here.

So I'll just point out a couple of things that Rust does for us here: 1) guarantee that all states are considered 2) that each state has a result because of the assignment to the state. You'll notice that there are some unimplemented!()'s in there, that's because this is a work in progress, but I was so excited about how easy it was to write an FSM in Rust with just the standard language semantics, that I just had to share.

Basically, the sweet sauce here is that the 'state' can carry context implicitly in the enum as part of it's tuple definition. You can obviously make that more complex than what I did here, but this was such a simple and elegant solution to a common problem.

Conclusion

Rust continues to impress me while learning it. There are definitely some oddities like enum's being called enum's when they really are something else. Also, I continue to fight the compiler on mutability around ownership, etc. It's not that I don't get the ownership model, I do... it's that after working with a GC in Java for so long, I have to train myself to think about it each time I pass a reference to something, and as far as I can tell 90% of the time I'm getting it wrong the first time.

Anyway, getting back to hacking DNS now.


89 comments:

Levi said...

a new type with it, you enumerate all the values that inhabit it. This is opposed to struct/tuple type definitions where you are describing a type inhabited by the Cartesian product of its constituent types' inhabitants.

It's probably also meant to be reminiscent of C, Java, etc syntax, but I am not sure the familiarity is worth the possible confusion over the differences!

Levi said...

Sorry, I posted the previous comment from my phone and I deleted the first line without noticing.

It should have said something to the effect of:

I'm not sure exactly why they chose 'enum', but it could be because when you define a new type with it,

Dan C said...

Umm... a turing machine isn't a finite state machine. The state in a turing machine isn't limited to a finite set of states.

Unknown said...

Turing Machines have an infinite tape (given memory constraints), but the states are finite. Though, I won't argue the point, b/c this is based on my education from 15 years ago, and I don't care much about the theory, just the usefulness. Happy to change that line if people nitpick ;)

Levi said...

It's been a long time since my automata theory course as well, so Dan's comment made me want to refresh my memory. This page of CS notes makes the fundamental difference between finite state automata and Turing machines pretty clear: http://www.cs.hmc.edu/~keller/cs60book/12%20Finite-State%20Machines.pdf

The difference is not so much in the way you define the transition function, but in how that function interacts with input and output. Of course those differences change the sort of transition functions you construct, but it's interesting to see where they're similar and where they're different.

SabrinaGreen said...

Nice post. Heathrow Terminal 1 Parking

Brooke Higgins said...

Keep sharing. valet parking luton

sandeep saxena said...

Wow,great information. I am sure the info on your blog will help others,Thanks.
C C++ Training in Chennai
C Training in Chennai
C++ Training in Chennai
C C++ Training in Velachery
core java training in chennai
javascript training in chennai
SAS Training in Chennai
QTP Training in Chennai

subha said...

sir i am LJ plss help me on how i ans. this question i'm applying for philippine national police i have no experience in work,tell me something about yourself.thanks.
C and C++ Training Institute in chennai | C and C++ Training Institute in anna nagar | C and C++ Training Institute in omr | C and C++ Training Institute in porur | C and C++ Training Institute in tambaram | C and C++ Training Institute in velachery

Data Science Training in Bangalore said...

A great website with interesting and unique material what else would you need.

Data Science Course

Data Science Training in Bangalore said...
This comment has been removed by the author.
Data Science Training said...

I read that Post and got it fine and informative. Please share more like that...

Data Science Training

Data Science Courses said...

Great advice and very easy to understand. It will definitely come in handy when I get the chance to start my blog.

360DigiTMG Data Science Courses

Data Science Certification said...

This is an excellent article. Thanks for sharing this information. I will be visiting your blog regularly for the latest articles. I will be visiting your blog regularly to see some of the latest posts.

360DigiTMG Data Science Certification

Digital Weekday said...

Damien Grant
Damien Grant
Damien Grant
Damien Grant
Damien Grant
Damien Grant
Damien Grant
Damien Grant

Digital Weekday said...

Damien Grant
Damien Grant
Damien Grant
Damien Grant
Damien Grant
Damien Grant
Damien Grant
Damien Grant

Data Science Hyderabad said...

Great blog with excellent information found very useful thank you.
typeerror nonetype object is not subscriptable

Artificial Intelligence Course said...

I will be interested in more similar topics. I see you have some really very useful topics, I will always check your blog thank you.

Artificial Intelligence Course in Bangalore

Business Analytics Course said...

Just a shine from you here. I have never expected anything less from you and you have not disappointed me at all. I guess you will continue the quality work.

Business Analytics Course in Bangalore

Data Analytics Course said...

Interesting post. I wondered about this issue, so thanks for posting. A very good article. This is a really very nice and useful article. Thank you

Data Analytics Course in Bangalore

Cyber Security said...

It took a while to understand all the comments, but I really enjoyed the article. It turned out to be really helpful for me and I'm positive for all the reviewers here! It's always nice to be able to not only be informed, I'm sure you enjoyed writing this article.
Cyber Security Course in Bangalore

Cyber Security Course said...

Happy to chat on your blog, I feel like I can't wait to read more reliable posts and think we all want to thank many blog posts to share with us.
Cyber Security Training in Bangalore

Data Science Institute In Banglore said...

This type of very helpful article. Very interesting to see this article.
Data Science Training Institute in Bangalore

Best Data Science Courses In Bangalore said...


Very wonderful article. I liked reading your article. Very wonderful share. Thanks ! .
Data Science Course In Bangalore With Placement

Ethical Hacking Course said...

Top quality blog with unique content and information shared was valuable looking forward for next updated thank you
Ethical Hacking Course in Bangalore

Artificial Intelligence Course said...

I will very much appreciate the writer's choice for choosing this excellent article suitable for my topic. Here is a detailed description of the topic of the article that helped me the most.

Artificial Intelligence Course in Bangalore

Pankaj Singh said...

It’s very helpful for us, thank you so much for sharing such an amazing article. Visit Ogen Infosystem for top Website Designing and PPC Services in Delhi at an affordable price.
PPC Company in Delhi

jegan said...

wonderful article contains lot of valuable information. Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article.
This article resolved my all queries.good luck an best wishes to the team members.continue posting.learn digital marketing use these following link
Digital Marketing Course in Chennai

Data Science Training said...

Quality articles could be your vital to encourage the traffic to see the internet page, so which is exactly what this internet site is currently providing. Learn Tableau Course in Bangalore

DataScience Specialist said...

I have to search sites with relevant information ,This is a
wonderful blog,These type of blog keeps the users interest in
the website, i am impressed. thank you.
Data Science Course in Bangalore

Data Science Training in Bangalore said...

Actually I read it yesterday but I had some ideas about it and today I wanted to read it again because it is so well written.

Business Analytics Course

Huongkv said...

Mua vé tại đại lý vé máy bay Aivivu, tham khảo

vé máy bay đi Mỹ Vietnam Airline

thông tin chuyến bay từ mỹ về việt nam

giá vé rẻ đi đà nẵng

vé máy bay hà nội

đặt vé máy bay đi nha trang giá rẻ

Tech Science said...

Fantastic blog with excellent information and valuable content just added your blog to my bookmarking sites thank for sharing.
Data Science Course in Chennai

Data Science Training said...

Excellent site with great content and very informative. I would like to thank you for the efforts you have made in writing.
Data Science Training in Bangalore

Data Science Training in Hyderabad said...

Fantastic Site with useful and unique content looking forward to the next update thank you.
Data Science Training in Hyderabad

Data Science in Pune said...

It is late to find this act. At least one should be familiar with the fact that such events exist. I agree with your blog and will come back to inspect it further in the future, so keep your performance going.
Data Science Course in Pune

Data Science Bangalore said...

I really enjoy reading all of your blogs. It is very helpful and very informative and I really learned a lot from it. Definitely a great article
Data Science Course Bangalore

Tech said...

I really enjoy every part and have bookmarked you to see the new things you post. Well done for this excellent article. Please keep this work of the same quality.
Artificial Intelligence course in Chennai

Business Analytics Course in Bangalore said...

Very good message. I stumbled across your blog and wanted to say that I really enjoyed reading your articles. Anyway, I will subscribe to your feed and hope you post again soon.

Business Analytics Course in Bangalore

Data Science Training in Bangalore said...

I have voiced some of the posts on your website now, and I really like your blogging style. I added it to my list of favorite blogging sites and will be back soon ...

Data Science Training in Bangalore

Data Science Institutes in Bangalore said...

I'm glad I found this blog! Occasionally, students want to know the keys to writing productive literary essays. Your first-class knowledge of this great job can become a suitable foundation for these people. Good

Data Science Institutes in Bangalore

Best Data Science Courses said...

I am more curious to take an interest in some of them. I hope you will provide more information on these topics in your next articles.

Best Data Science Courses in Bangalore

Data Analytics Course said...

A great article is really informative and innovative to keep us up to date with new updates. it was really precious. Thank you so much.

Data Analytics Course in Bangalore

Pallavi reddy said...

i am glad to discover this page : i have to thank you for the time i spent on this especially great reading !! i really liked each part and also bookmarked you for new information on your site.
data science training in bangalore

360DigiTMG said...

"Very Nice Blog!!!


Please have a look about "
data science in malaysia

AI course in pune said...

I am really enjoying reading your well written articles. It looks like you spend a lot of effort and time on your blog. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work.
artificial intelligence course in pune

Tech Science said...

A fantastic blog with excellent information and valuable content just added your blog to my bookmarking sites thank you for sharing.
Data Science Course in Chennai

DS Training in Bangalore said...

Happy to chat on your blog, I feel like I can't wait to read more reliable posts and think we all want to thank many blog posts to share with us.

Data Science Training in Bangalore

Digital Marketing Training in Bangalore said...

Really wonderful blog completely enjoyed reading and learning to gain vast knowledge. Eventually, this blog helps in developing certain skills which in turn helpful in implementing those skills. Thanking the blogger for delivering such beautiful content and keep posting the contents in the upcoming days.

Digital Marketing Training in Bangalore

Cyber Security Course said...

The truly mind-blowing blog went amazed with the subject they have developed the content. This kind of post is really helpful to gain knowledge of unknown things which surely triggers to motivate and learn the new innovative contents. Hope you deliver the similar successive contents forthcoming as well.

Cyber Security Course

Machine Learning Course in Bangalore said...

Honestly speaking this blog is absolutely amazing in learning the subject that is building up the knowledge of every individual and enlarging to develop the skills which can be applied into a practical one. Finally, thanking the blogger to launch more further.

Machine Learning Course in Bangalore

Institute said...

Wow, happy to see this awesome post. I hope this think help any newbie for their awesome work and by the way thanks for share this awesomeness, i thought this was a pretty interesting read when it comes to this topic. Thank you..
Artificial Intelligence Course

Emerging Technologies said...

I need to thank you for this very good read and i have bookmarked to check out new things from your post. Thank you very much for sharing such a useful article and will definitely saved and revisit your site.
Data Science Course

Data Science Courses said...

Awesome article. I enjoyed reading your articles. this can be really a good scan for me. wanting forward to reading new articles. maintain the nice work!
Data Science Courses in Bangalore

Data Analytics Course said...

Excellent Blog! I would like to thank you for the efforts you have made in writing this post. Gained lots of knowledge.
Data Analytics Course

Education said...

Your site is truly cool and this is an extraordinary moving article and If it's not too much trouble share more like that. Thank You..
Digital Marketing Course in Hyderabad

Knowledge said...

Thank a lot. You have done excellent job. I enjoyed your blog . Nice efforts
Data Science Certification in Hyderabad

AI Courses said...

What an incredible message this is. Truly one of the best posts I have ever seen in my life. Wow, keep it up.
AI Courses in Bangalore

Business Analytics said...

I am sure it will help many people. Keep up the good work. It's very compelling and I enjoyed browsing the entire blog.
Business Analytics Course in Bangalore

Institute said...

Wow, happy to see this awesome post. I hope this think help any newbie for their awesome work and by the way thanks for share this awesomeness, i thought this was a pretty interesting read when it comes to this topic. Thank you..
Artificial Intelligence Course

Data Science Chennai said...

I feel very grateful that I read this. It is very helpful and very informative and I really learned a lot from it.
Data Science Course in Chennai

Emerging Technologies said...

I need to thank you for this very good read and i have bookmarked to check out new things from your post. Thank you very much for sharing such a useful article and will definitely saved and revisit your site.
Data Science Course

Education said...

Your site is truly cool and this is an extraordinary moving article and If it's not too much trouble share more like that. Thank You..
Digital Marketing Course in Hyderabad

Technology said...

All of these posts were incredible perfect. It would be great if you’ll post more updates and your website is really cool and this is a great inspiring article.
Artificial Intelligence course in Chennai

Knowledge said...

Thank a lot. You have done excellent job. I enjoyed your blog . Nice efforts
Data Science Certification in Hyderabad

360DigiTMGAurangabad said...

Thanks for Sharing This Article.It is very so much valuable content. I hope these Commenting lists will help to my website
machine learning training in aurangabad

Data Science Training in Bangalore said...

Happy to chat on your blog, I feel like I can't wait to read more reliable posts and think we all want to thank many blog posts to share with us.

Data Science Training in Bangalore

Digital Marketing Training in Bangalore said...

Really wonderful blog completely enjoyed reading and learning to gain vast knowledge. Eventually, this blog helps in developing certain skills which in turn helpful in implementing those skills. Thanking the blogger for delivering such beautiful content and keep posting the contents in the upcoming days.

Digital Marketing Training in Bangalore

Artificial Intelligence Training in Bangalore said...

I will very much appreciate the writer's choice for choosing this excellent article suitable for my topic. Here is a detailed description of the topic of the article that helped me the most.

Artificial Intelligence Training in Bangalore

Machine Learning Course in Bangalore said...

The Extraordinary blog went amazed with the content that they have developed in a very descriptive manner. This type of content surely ensures the participants explore themselves. Hope you deliver the same near the future as well. Gratitude to the blogger for the efforts.

Machine Learning Course in Bangalore

360DigiTMGAurangabad said...

Your content is very unique and understandable useful for the readers keep update more article like this.
data science course aurangabad

360DigiTMG-Pune said...

This website and I conceive this internet site is really informative ! Keep on putting up!
data scientist online course

Priya Rathod said...

I have read your blog its very attractive and impressive. I like it your blog.
Data Science Training in Hyderabad
Data Science Course in Hyderabad

Data Science Training in Bangalore said...

I bookmarked your website because this site contains valuable information. I am very satisfied with the quality and the presentation of the articles. Thank you so much for saving great things. I am very grateful for this site.

Data Science Training in Bangalore

Digital Marketing Training in Bangalore said...

I have voiced some of the posts on your website now, and I really like your blogging style. I added it to my list of favorite blogging sites and will be back soon ...

Digital Marketing Training in Bangalore

Digital Marketing Training in Bangalore said...

Wonderful blog found to be very impressive to come across such an awesome blog. I should really appreciate the blogger for the efforts they have put in to develop such amazing content for all the curious readers who are very keen on being updated across every corner. Ultimately, this is an awesome experience for the readers. Anyways, thanks a lot and keep sharing the content in the future too.

Digital Marketing Training in Bangalore

Artificial Intelligence Training in Bangalore said...

I wanted to leave a little comment to support you and wish you the best of luck. We wish you the best of luck in all of your blogging endeavors.

Artificial Intelligence Training in Bangalore

Machine Learning Course in Bangalore said...

You actually make it seem like it's really easy with your acting, but I think it's something I think I would never understand. I find that too complicated and extremely broad. I look forward to your next message. I'll try to figure it out!

Machine Learning Course in Bangalore

Data Science Training in BLR said...

I wanted to leave a little comment to support you and wish you the best of luck. We wish you the best of luck in all of your blogging endeavors.

Data Science Training in Bangalore

Digital Marketing Training in BLR said...

It is late to find this act. At least one should be familiar with the fact that such events exist. I agree with your blog and will come back to inspect it further in the future, so keep your performance going.

Digital Marketing Training in Bangalore

Artificial Intelligence Training in BLR said...

You have completed certain reliable points there. I did some research on the subject and found that almost everyone will agree with your blog.

Artificial Intelligence Training in Bangalore

Machine Learning Course in BLR said...

Happy to chat on your blog, I feel like I can't wait to read more reliable posts and think we all want to thank many blog posts to share with us.

Machine Learning Course in Bangalore

cloud computing course in bangalore said...

Extremely overall quite fascinating post. I was searching for this sort of data and delighted in perusing this one. Continue posting. A debt of gratitude is in order for sharing. python course in delhi

Data Analytics Bangalore said...


I feel very grateful that I read this. It is very helpful and very informative and I really learned a lot from it.
Data Analytics Course

Data Science Courses said...

I am really enjoying reading your well written articles. I am looking forward to reading new articles. Keep up the good work.
Data Science Courses in Bangalore

AI Courses Bangalore said...

What an incredible message this is. Truly one of the best posts I have ever seen in my life. Wow, keep it up.
AI Courses in Bangalore

Business Analytics said...


I am sure it will help many people. Keep up the good work. It's very compelling and I enjoyed browsing the entire blog.
Business Analytics Course in Bangalore

Artificial Intelligence Training in BLR said...

A good blog always contains new and exciting information, and reading it I feel like this blog really has all of these qualities that make it a blog.

Artificial Intelligence Training in Bangalore

data science said...



Great to become visiting your weblog once more, it has been a very long time for me. Pleasantly this article i've been sat tight for such a long time. I will require this post to add up to my task in the school, and it has identical subject along with your review. Much appreciated, great offer. data science course in nagpur