Tristan Labelle

Three Designs for Decoding File Formats

This article presents three object-oriented designs for decoding file formats, in the spirit of the Gang of Four design patterns. Structuring your decoding logic by following one of these designs will increase the maintainability and reusability of your code, turning it into a richer API with minimal additional work.

Most useful programs need to process data from files or network streams. This involves two logical steps: decoding the bytes or characters of the stream according to the file format to extract useful data types, and processing the resulting data according to its purpose for the program. In a simple implementation, those two steps are intertwined, as illustrated by this code for parsing properties in the INI file format, which represents simple key/value pairs organized in named sections:

// Decoding the ini file format
string line = stringReader.ReadLine();
var match = Regex.Match(line, "^(\w+)\s*=\s*(\w+)\s*$"); // name=value
// Processing the data as needed by the program
if (match.Success && section == "settings" && match.Groups[1].Value == "history_length") 
  history.Resize(int.Parse(match.Groups[2].Value));

This coupling introduces a few issues:

  1. The implementation can become very complex when both decoding and data processing are nontrivial.
  2. The decoding logic cannot be reused to process the data in a different way.
  3. The decoding and data processing logic cannot be tested in isolation.

To address these issues, these two pieces of logic need to be decoupled. This article presents three designs which achieve this, in the spirit of the Gang of Four design patterns. The basic idea behind each design is simple and commonly found in libraries, but there are various interesting ways to extend and combine them.

The INI file format will be used as an example for its simplicity, but the concepts apply to more complex formats as well. Generalizing, this article will use the terminology "node type" to refer data types defined in a file format, whether hierarchical or not. For example, the INI file format can be described using two node types: sections (e.g. [my_section]) and properties (e.g. my_property=my_value).

Reader design

With the Reader design, every node type becomes a getter on a Reader class. A Read() method and a State property allows the consumer to iterate through the nodes of the file and know which data to retrieve. This is akin to an IEnumerator<T> where T would be a discriminated union of node types. A good example is System.Xml.XmlReader in the .NET base class libraries (XmlReader.NodeType is equivalent to the State property above). Newtonsoft.Json.JsonReader is similar.

class Reader
{
  State State { get; }
  bool Read();
  string GetSectionName();
  string GetPropertyName();
  string GetPropertyValue();
}
 
enum State { Initial, Section, Property, End }

Data processing logic typically takes the form of a while loop with a nested switch statement to handle the different states. Each consumer will likely have to repeat some amount of this boilerplate.

while (reader.Read())
{
  switch (reader.State)
  {
    case State.Section: Console.WriteLine("New section: " + reader.GetSectionName()); break;
    case State.Property: Console.WriteLine("New property: {0} = {1}", reader.GetPropertyName(), reader.GetPropertyValue()); break;
  }
}

Improvements

A Reader can also expose methods to skip parts of the file of no interest, or even seek to arbitrary locations if the file format supports random access.

bool SkipSection();

Sink design

With the Sink design, every node type in the file becomes a void-returning method on an interface, and a method is provided that takes a stream, decodes the data and "feeds" every node into a sink implementation. A good example is ID2D1SimplifiedGeometrySink.

interface ISink
{
  void BeginSection(string name);
  void AddProperty(string name, string value);
  void End(); // Optional
}

static void ReadToSink(Stream stream, ISink sink) {}

Data processing logic is achieved by creating a class implementing the interface and passing an instance of it to the ReadToSink method. Of note is that ReadToSink will then own the control flow, which prevents scenarios such as reading two streams at once and comparing them nodewise. Each sink implementer will also be required to do some amount of state tracking, for example to associate AddProperty calls with the preceding BeginSection call.

Improvements

If only parts of the file are of interest, the Sink design can be augmented to skip sections by returning a corresponding flag. For example:

bool BeginSection(string name) // Return false to skip (AddProperty will not be called)

For file formats with a more hierarchical structure, multiple specialized sinks can be defined. Some sink methods then become factories for children sinks. This keeps the size of each sink interface smaller and can help implementers structure their code following the hierarchical structure of the data.

interface ISink
{
  ISectionSink? BeginSection(string name); // Return null to skip
  void End();
}
 
interface ISectionSink
{
  void AddProperty(string name, string value);
  void End();
}

Concrete Sink examples

The Sink abstraction proves to be useful in many ways. Examples of common implementations include:

For example, copying a file while validating it could be implemented as:

ReadToSink(inputStream, new ValidatorSink(new WriterSink(outputStream)));

Loader design

With the Loader design, every node type becomes a property in an object model mapping closely to the file format. A method is then provided to decode the data from a stream and produce a corresponding object model. The object model may be mutable or immutable. A good example is XmlDocument.Load.

class IniFile { Section[] Sections; }
class Section { Property[] Properties; }
class Property { string Name; string Value; }
IniFile Load(Stream stream);

Data processing consists in walking the resulting object graph, potentially using recursion if the file format has hierarchical data, and inspecting the exposed properties.

Comparison and summary

Hierarchy of power

These three designs form a hierarchy of power: Reader > Sink > Loader. Less powerful designs can be implemented in terms of more powerful designs, but not the other way around*.

The Sink design can be implemented in terms of the Reader design:

while (reader.Read())
{
  switch (reader.State)
  {
    case State.Section: sink.BeginSection(reader.GetSectionName()); break;
    case State.Property: sink.AddProperty(reader.GetPropertyName(), reader.GetPropertyValue()); break;
  }
}

The Loader design can be implemented in terms of the Sink design by means of a Builder sink:

IniFile Load(Stream stream)
{
  var builder = new IniFileBuilder(); // Implements ISink
  ReadToSink(stream, builder);
  return builder.GetResult();
}

The Loader design can also be directly implemented in terms of the Reader design.

* The Reader and Sink designs could be implemented in terms of the Loader design, but this requires the entire file to be loaded first, whereas Reader and Sink would normally support streaming the data.

Summary

The Reader and Sink designs naturally support streaming, whereas the Loader design requires loading the entire file in memory. The Reader design can most easily support partial file reading, and the Loader design has the most natural representation for hierarchical data.

Recommendation

When possible, follow the hierarchy of power:

Thanks!

These thoughts come from my recent experience writing decoders for several file formats related to music notation. Your feedback on its form and content is very welcome.