Pete Corey Writing Work Contact

Living the Simple Life with Recursive Parsing and Serialization

Written by Pete Corey on Sep 24, 2018.

I just pushed a massive refactor of my Elixir-powered Bitcoin full node project that considerably simplifies the parsing and serialization of Bitcoin network messages.

I’m a big fan of the solution I landed on, and I wanted to share it with you. The key insight I had was to switch to a recursive solution where each sub-component of every messages handles its own parsing and serialization.

Obviously the devil is in the details, so let’s dive in.

What’s the Problem?

Before I took on this refactor, I was handling the parsing and serialization of Bitcoin network messages entirely manually. For every message, I’d define a parse/1 function and implement a corresponding serialize/1 protocol. Every field within the message was manually parsed and serialized using Elixir’s various binary manipulation operations.

As an example, here’s how a NetAddr message would be parsed using this technique:


def parse(binary) do
  with {:ok, time, rest} <- parse_time(binary),
       {:ok, services, rest} <- parse_services(rest),
       {:ok, ip, rest} <- parse_ip(rest),
       {:ok, port, rest} <- parse_port(rest) do
    {:ok, %NetAddr{time: time, services: services, ip: ip, port: port}, rest}
  end
end

defp parse_time(<<time::32-little, rest::binary>>),
  do: {:ok, time, rest}

defp parse_time(_binary),
  do: {:error, :bad_time}

defp parse_services(<<services::64-little, rest::binary>>),
  do: {:ok, services, rest}

defp parse_services(_binary),
  do: {:error, :bad_services}

defp parse_ip(<<ip::binary-size(16), rest::binary>>),
  do: {:ok, ip, rest}

defp parse_ip(_binary),
  do: {:error, :bad_ip}

defp parse_port(<<port::16-big, rest::binary>>),
  do: {:ok, port, rest}

defp parse_port(_binary),
  do: {:error, :bad_port}

While this was fantastic practice at manipulating binaries within Elixir, it wasn’t a scalable solution. There are simply too many messages in the Bitcoin protocol to implement in this time consuming way. Not only that, but many of the messages share common sub-structures who’s parse/1 and serialize/1 implementations would need to be repeated throughout the project.

Daunted with the task of implementing a parse/1 and serialize/1 function for every message in the protocol’s peer-to-peer vocabulary, I decided I needed a better solution.

Taking Advantage of Sub-Structures

As I mentioned up above, many Bitcoin messages share common sub-structures. Instead of dooming me to tedious repetition, I realized that these repeated structures were actually a blessing from the DRY gods.

If we could architect our parse/1 and serialize/1 implementations in a way that offloads the responsibility of parsing and serializing these shared sub-structures, the parsing and serialization implementations of our top-level messages could be substantially simplified.

Not only that, but we could take the notion of “sub-structures” even further. In many ways, the types of the primitives that compose together to build the protocol’s messages and sub-structures are sub-structures in and of themselves. For example, a uint32_t, which is a C type commonly used to define unsigned integers throughout the protocol’s various messages, is actually a sub-structure that has a single field and specific parsing and serialization rules.

We could implement a UInt32T struct with a corresponding parse/1 function like so:


defmodule BitcoinNetwork.Protocol.UInt32T do
  defstruct value: nil

  def parse(<<value::little-unsigned-integer-32, rest::binary>>),
    do: {:ok, %BitcoinNetwork.Protocol.UInt32T{value: value}, rest}
end

Similarly, we could reverse the process and serialize our newly parsed UInt32T:


defimpl BitcoinNetwork.Protocol.Serialize, for: BitcoinNetwork.Protocol.UInt32T do
  def serialize(%{value: value}),
    do: <<value::little-unsigned-integer-32>>
end

Composing Sub-Structures

Now we have parsing and serialization rules built for these base-level sub-structures like UInt32T and other primitive types. We can build upon the work we’ve done by composing these sub-structures together into more complex structure.

For example, a NetAddr is really just a UInt32T, a UInt64T, a sixteen byte Binary, and a UInt16T representing an addresses’ time, services, ip, and port, respectively. We can write a NetAddr struct complete with a parse/1 function that calls out to the parse/1 functions of these more primitive sub-structures:


defmodule BitcoinNetwork.Protocol.NetAddr do
  defstruct time: nil,
            services: nil,
            ip: nil,
            port: nil

  alias BitcoinNetwork.Protocol.{Binary, NetAddr, UInt32T, UInt64T, UInt16T}

  def parse(binary) do
    with {:ok, time, rest} <- UInt32T.parse(binary),
         {:ok, services, rest} <- UInt64T.parse(rest),
         {:ok, ip, rest} <- Binary.parse(rest, 16),
         {:ok, port, rest} <- UInt16T.parse(rest),
         do:
           {:ok,
            %NetAddr{
              time: time,
              services: services,
              ip: ip,
              port: port
            }, rest}
  end
end

Serializing a NetAddr structure is even easier. We simply build a list of the fields we want serialized, in the order we want them serialized, and then map over that list with our serialize/1 function:


defimpl BitcoinNetwork.Protocol.Serialize, for: BitcoinNetwork.Protocol.NetAddr do
  def serialize(net_addr),
    do:
      [
        net_addr.time,
        net_addr.services,
        net_addr.ip,
        net_addr.port
      ]
      |> BitcoinNetwork.Protocol.Serialize.serialize()
end

We’re left with an Elixir binary that represents the entire serialized NetAddr structure, but we didn’t have to do any of the heavy lifting ourselves.

The best part of this solution is that we can repeatedly build on top of our sub-structures. An Addr message is composed of a VarInt and a list of NetAddr sub-structures. It’s sub-structures all the way down.

Special Cases and Rough Edges

While the general case for this solution works beautifully, there are a few special cases and rough edges we need to smooth over.

The first of these rough edges comes when parsing and serializing fixed-size binaries. For example, within the NetAddr structure, we need to parse sixteen bytes off of the wire and interpret those bytes as an IP address. We instructed our NetAddr parser to do this by calling Binary.parse/2 with 16 as a second argument.

Our Binary module’s parse/2 function accepts an optional second argument that lets us specify exactly how many bytes we want to parse out of the incoming binary:


defmodule BitcoinNetwork.Protocol.Binary do
  def parse(binary, size \\ 1) do
    <<binary::binary-size(size), rest::binary>> = binary
    {:ok, binary, rest}
  end
end

Notice that Binary.parse/2 returns a primitive Elixir binary, rather than a struct. This is an intentional decision and makes our serialization that much easier:


defimpl BitcoinNetwork.Protocol.Serialize, for: BitString do
  def serialize(binary),
    do: binary
end

Another special case we need to handle is made apparent when we need to parse and serialize lists of “things”. A perfect example of this appears in our code when we need to parse an Addr structure, which is composed of a VarInt number of NetAddr structures:


with {:ok, count, rest} <- VarInt.parse(binary),
     {:ok, addr_list, rest} <- Array.parse(rest, value(count), &NetAddr.parse/1),
     do:
       {:ok,
        %Addr{
          count: count,
          addr_list: addr_list
        }, rest}

Like Binary.parse/2, Array.parse/3 has some special behavior associated with it. Our Array module’s parse/3 function takes our binary to parse, the number of “things” we want to parse out of it, and a function to parse each individual “thing”:


defmodule BitcoinNetwork.Protocol.Array do
  def parse(binary, count, parser),
    do: parse(binary, count, parser, [])
end

Our parse/3 function calls out to a private parse/4 function that builds up an accumulator of our parsed “things”. Once we’ve parsed a sufficient number of “things”, we return our accumulated list:


defp parse(rest, 0, parser, list),
  do: {:ok, Enum.reverse(list), rest}

The non-base case of our parse/4 function simply applies our parser/1 function to our binary and appends the resulting parsed “thing” to our list of “things”:


defp parse(binary, count, parser, list) do
  with {:ok, parsed, rest} <- parser.(binary),
       do: parse(rest, count - 1, parser, [parsed | list])
end

Once again, the result of our Array.parse/3 function returns a primitive Elixir list, not a struct. This makes our serialization fairly straight forward:


defimpl BitcoinNetwork.Protocol.Serialize, for: List do
  def serialize(list),
    do:
      list
      |> Enum.map(&BitcoinNetwork.Protocol.Serialize.serialize/1)
      |> join()

  def join(pieces),
    do: 
      pieces
      |> Enum.reduce(<<>>, fn piece, binary -> <<binary::binary, piece::binary>> end)
end

We simply map serialize/1 over our list of “things”, and concatenate the newly serialized pieces together.

If you remember back to our NetAddr serialization example, you’ll notice that we’ve been using our List primitive’s serialization protocol this whole time.

Awesome!

Final Thoughts

I struggled with this refactor on and off for a good few weeks. Ultimately, I’m happy with the solution I landed on. It’s more complex than my original solution in terms of the number of moving parts, but it’s a much more scalable and mentally manageable solution than the one I was originally working with.

Now that this is out of my system, I can turn my attention to the interesting pieces of building a Bitcoin full node: processing blocks!

Expect articles digging into that topic in the future. In the meantime, check out the entire project on Github to get a more hands-on feel for the refactor and the recursive parsing and serialization solution I ultimately landed on.

Minimal Coding with Spacemacs and Olivetti

Written by Pete Corey on Sep 10, 2018.

As I mentioned on Twitter, I’ve been experimenting lately with using a visually minimal Spacemacs setup. I’ve been using this new setup every day for several weeks, and I’m absolutely in love with it.

Want screenshots and an overview of how it works? Read on!

But First, Screenshots

Olivetti is an Emacs package designed to create a distraction-free writing experience within your editor. Most of Olivetti’s screenshots show it in the context of editing markdown. That makes sense, as the term “distraction-free writing” is usually applied to the context of writing prose.

But what if I want a “distraction-free writing” environment for writing code?

It turns out that Olivetti is still perfectly suited for the job. Check out a few screenshots of my current Spacemacs setup. Note that the screenshots below capture my entire screen, from edge to edge. There’s nothing behind the curtain here:

Spacemacs with Olivetti.

I’ve configured Olivetti to only activate when in prog-mode, or in text-mode. This means that things like Spacemac’s home buffer, and inline terminals retain their original layouts. This distinction has been working beautifully for me so far:

Spacemacs with multiterm.

Using Olivetti within Spacemacs

To get Olivetti working with Spacemacs, I needed an Olivetti layer. Unfortunately, an out-of-the-box Spacemacs layer doesn’t exist for Olivetti. Thankfully, the process of creating a custom, private layer isn’t a difficult one.

We can create a new private layer from within Spacemacs by running the configuration-layer/create-layer command with M-x (or SPC + :). Let’s call our layer olivetti. This creates a new ~/.emacs.d/private/olivetti folder and populates a packages.el file with some boilerplate.

We’ll replace the contents of packages.el with the following:


(defconst olivetti-packages
  '(olivetti))

(defun olivetti/init-olivetti ()
  (use-package olivetti))

This tells Spacemacs that we need the olivetti package, and to use the package once it’s been loaded.

Once that’s done, we need to edit our Spacemacs configuration file (SPC f e d), and add an olivetti entry under our dotspacemacs-configuration-layers list to instruct Spacemacs to load our new private layer.


(defun dotspacemacs/layers ()
  (setq-default
   ...
   dotspacemacs-configuration-layers
   '(
     ...
     olivetti
     )))

Finally, we need to configure Olivetti to run in prog-mode and text-mode. We can do this in our dotspacemacs/user-config callback:


(add-hook 'text-mode-hook (lambda ()
                            (interactive)
                            (message "Olivetti text-mode-hook")
                            (olivetti-set-width 81)
                            (hidden-mode-line-mode)
                            (spacemacs/toggle-vi-tilde-fringe-off)
                            (olivetti-mode 1)))
(add-hook 'prog-mode-hook (lambda ()
                            (interactive)
                            (message "Olivetti prog-mode-hook")
                            (olivetti-set-width 81)
                            (hidden-mode-line-mode)
                            (spacemacs/toggle-vi-tilde-fringe-off)
                            (olivetti-mode 1)))

I use this opportunity to tune Olivetti and Spacemacs to my liking. Feel free to make any changes you deem necessary.

With that, we’re good to go!

How To Not Get Lost

The key to not getting lost without any visual indicators is to always know where you are!

That may sound like a truism, but visually paring down my code editing environment has made me realize that there is no substitute for deep understanding and mastery of your tools. I don’t need a modeline to tell me which mode I’m in if I already know. I don’t need a constant reminder of which line I’m on, when I can navigate directly to any given line with :.

Many of the visual indicators that modern editors provide are really just noise. I’m not going to say that noise is never helpful, but you can almost always get by without it.

If you’re interested in seeing exactly how my Spacemacs is set up, you can see my entire .spacemacs file here. It’s very ugly. I’m warning you now.

Using Facades to Simplify Elixir Modules

Written by Pete Corey on Sep 3, 2018.

A common trend I see in Elixir projects is that modules tend to become large. Sometimes very large. This isn’t necessarily an issue, but it goes against some deep seated heuristics I have for building software.

As my Chord project started to get complex, I repeatedly found myself reaching for a pattern to keep my module size and complexity down, while still maintaining a friendly and approachable API.

Let’s dig into some examples.

What’s the problem?

The Chord module is the heart of my Chord project. Using Chord you can generate guitar chord voicings, generate possible fingerings for a given voicing, and even calculate the distances between various chord voicings and fingerings.

It’s conceivable that lots of this functionality should live directly under the Chord module. For example, we’d want to be able to ask for Chord.voicings/1, or Chord.fingerings/1, or even convert a chord into a chord chart with Chord.to_string/1.

The problem is that each of these pieces of functionality comes along with a non-trivial implementation. If we put our voicings/1, fingerings/1, and to_string/1 functions in the Chord module, their implementations would likely live in the Chord module as well. In my mind, this would quickly turn Chord into an unmaintainable mess.

There has to be a better way.

What’s the solution?

It turns out there is a better way. And, like most better ways, it turns out that the solution to our problem is obviously simple.

Let’s use our voicings/1 function as an example. Rather than defining our voicings/1 function and implementation within our Chord module, we’ll create a Chord.Voicing module and define our voicings/1 function there.


defmodule Chord.Voicing do
  def voicings(notes, notes_in_chord \\ nil),
    do: ...
end

Now our Chord.Voicing module is entirely concerned with the act of generating chord voicings for a given set of notes.

However, we still want this functionality available through our Chord module. To accomplish this, we simply need to write a Chord.voicings/1 function that matches the signature of our Chord.Voicing.voicings/1 module and passes the call straight through to our Chord.Voicing module:


defmodule Chord do
  def voicings(notes, notes_in_chord \\ nil),
    do: Chord.Voicing.voicings(notes, notes_in_chord)
end

We can continue on with this pattern by creating a new module to implement each of our features: Chord.Fingering, Chord.Renderer. From there we can flesh our our Chord module to wire our convenience functions up to their actual implementations:


defmodule Chord do
  def voicings(notes, notes_in_chord \\ nil),
    do: Chord.Voicing.voicings(notes, notes_in_chord)

  def to_string(chord, chord_name \\ nil),
    do: Chord.Renderer.to_string(chord, chord_name)

  def fingerings(chord),
    do: Chord.Fingering.fingerings(chord)
end

Beautiful.

Enter Delegates

Using the above pattern, we might make a mistake when passing the arguments from our first function head into the function in our implementation module (I’ve done it before).

Thankfully, Elixir gives us a way to prevent this mistake:


defmodule Chord do
  defdelegate voicings(notes, notes_in_chord \\ nil), to: Chord.Voicing
  defdelegate to_string(chord, chord_name \\ nil), to: Chord.Renderer
  defdelegate fingerings(chord), to: Chord.Fingering
end

Using the defdelegate macro, we can define the interface for each of our voicings/2, to_string/2, and fingerings/1 functions in our Chord module, and point each of these function heads to their implementation module.

Elixir automatically wires each of the delegated functions together, preventing any mindless developer mistakes from creeping into our codebase.

What’s in a name?

In the previous example, the Chord module is essentially acting as a “facade” that wraps and hides the complexity of our Chord.Voicing, Chord.Fingering, and Chord.Renderer modules.

I use the term “facade” loosely, and in real-life, I don’t use it at all. The “facade pattern”, and honestly all classic Gang of Four design patterns, carry baggage that I like to think I’ve let go of in my transition into the world of functional programming.

Another less weighty way to think of Chord is as an “API module”. It’s sole purpose is to act as an “application programming interface” within our application.

What would you call this kind of pattern?