Banner

Thoughts about software engineering, and game development.

Topics

Software Development

Fancy tools can’t tame complexity

Reversing dependencies with pluggable factories

Collision detection

Smooth collisions part 1 : disk vs segment

Smooth collisions part 2 : AABB vs segment, solving the issue of "internal edges"

Procedural content generation

Generating mazes part 1 : using fibers to prototype the graph generation

Software Security

Write Up: Gre-Hack 2019 - Reverse - The Point

Write Up: Gre-Hack 2019 - Reverse - Angry Tux

Meta

Donate!

1. Reversing dependencies using pluggable factories

What if you could extend your application without modifying existing code, but only by adding new code? In software design circles, this is sometimes called the "open-closed principle":

Software entities (functions, classes, modules, applications, etc.) should be open to extension, but closed to modification.

At first, adding new behaviour to an existing code base without modifying it seems impossible.

I’m going to describe here a design pattern called "pluggable factories" which allows to do exactly that.

TL;DR : think about plugins.

Let’s suppose we’re dealing here with a SVG rendering program. This program loads a SVG vectorial input file, renders it to a frame buffer, then writes it to the disk in the BMP format. The high-level code may look like this:

// main.cpp
#include "lib_bmp.h"

int main(int argc, char** argv)
{
  auto input = argv[1];
  auto output = argv[2];

  auto svg = loadSvg(input);
  auto framebuffer = render(svg);
  writeBmp(framebuffer, output);

  return 0;
}

This code is perfectly fine, until you decide that you need other output formats. Then the code starts to look like this:

// main.cpp
#include "lib_png.h"
#include "lib_gif.h"
#include "lib_bmp.h"

int main(int argc, char** argv)
{
  auto input = argv[1];
  auto output = argv[2];
  auto format = getExtension(output);

  auto svg = loadSvg(input);
  auto framebuffer = render(svg);

  if(format == "png")
    writePng(framebuffer, output);
  else if(format == "gif")
    writeGif(framebuffer, output);
  else if(format == "bmp")
    writeBmp(framebuffer, output);
  else
    fatal("Unknown format");

  return 0;
}

Clearly, something is starting to go wrong here. This code doesn’t conform to the open-closed principle, as it’s not immune to the addition of new formats. Each new format requires to modify the code of the main workflow. Thus, we will never be able to "close" this workflow code. That’s a pity, because the output format is becoming here an annoying detail ; to the user, what our application really does is "render SVG files to raster picture files", regardless of the concrete output format.

One can mitigate the issue by extracting a new method writePicture:

// main.cpp
#include "lib_png.h"
#include "lib_gif.h"
#include "lib_bmp.h"

int main(int argc, char** argv)
{
  auto input = argv[1];
  auto output = argv[2];
  auto format = getExtension(output);

  auto svg = loadSvg(input);
  auto framebuffer = render(svg);
  writePicture(framebuffer, format, output);

  return 0;
}

void writePicture(Framebuffer pic, string format, string output)
{
  if(format == "png")
    writePng(pic, output);
  else if(format == "gif")
    writeGif(pic, output);
  else if(format == "bmp")
    writeBmp(pic, output);
  else
    fatal("Unknown format");
}

At least, the main function now has a clean workflow: read the input file, render it, write it. It’s becoming readable again.

However, it still depends on the availability of writePicture, which in turn depends on the availability of … all the format-specific writer functions. In short, although our main workflow seems isolated from the low-level details, it transitively depends on them : it still can’t be re-used, nor tested, without them.

The "dependency inversion principle" tells us that abstractions should not depend on concretions. In other words: don’t depend on something more volatile than you.

Currently, our workflow depend on concrete picture formats. We need to reverse this dependency: the concrete picture formats should depend on the workflow, and the workflow should depend on … nothing. It might not sound familiar, but I guarantee you it is ; just have a look at the following code, it’s basic object-oriented design (i.e polymorphism):

// main.cpp
int main(int argc, char** argv)
{
  auto input = argv[1];
  auto output = argv[2];
  auto writer = createPictureWriterForFormat(getExtension(output));
  workflow(input, output, writer);
  return 0;
}
// workflow.h

struct IPictureWriter
{
  virtual ~IPictureWriter() {};
  virtual void writePicture(Framebuffer pic, string outputPath) = 0;
};

void workflow(string input, string output, IPictureWriter* format);
// workflow.cpp

void workflow(string input, string output, IPictureWriter* format)
{
  auto svg = loadSvg(input);
  auto framebuffer = render(svg);
  writePicture(framebuffer, format);
}
// output_formats.cpp
#include "workflow.h"
#include "output_format_png.h"
#include "output_format_gif.h"
#include "output_format_bmp.h"

unique_ptr createPictureWriterForFormat(string format)
{
  if(format == "png")
    return make_unique();
  else if(format == "gif")
    return make_unique();
  else if(format == "bmp")
    return make_unique();
  else
    fatal("Unknown format");
}
// output_format_png.h
#include "workflow.h"
#include "lib_png.h"

class PngWriter : IPictureWriter
{
  void writePicture(Framebuffer pic, string path)
  {
    writePng(pic, path);
  }
};

// output_format_gif.h

#include "workflow.h"
#include "lib_gif.h"

class GifWriter : IPictureWriter
{
  void writePicture(Framebuffer pic, string path)
  {
    writeGif(pic, path);
  }
};

// output_format_bmp.h
#include "workflow.h"
#include "lib_bmp.h"

class BmpWriter : IPictureWriter
{
  void writePicture(Framebuffer pic, string path)
  {
    writeBmp(pic, path);
  }
};

It’s a lot better now. Don’t be scared by the number of lines. That’s certainly more text, but that’s exactly the same amount of executable code. The only thing we did was separate this executable code into explicitly-labelled boxes.

Our SVG-to-raster conversion workflow can now handle new formats without having to be modified.

However, one thing still isn’t quite right: the "createPictureWriterForFormat" function. It shows the list of all supported formats, which we might call a "dependency magnet": during the lifecycle of the application, its dependency count is mostly going to only grow, as more formats get added.

Don’t get me wrong: we certainly need to have, somewhere in our application, a list of output formats. However, as soon as such a list is present in one source file, we have created a dependency magnet. What if we could build such a list at link time?

Enter the pluggable factories.

The principle is very simple: each output format will use the global construction mechanism of C++ to register itself to the application. The result looks like this:

// output_formats.cpp
#include "workflow.h"

static map<string, WriterCreationFunc> g_formats;

void registerFormat(string format, WriterCreationFunc func)
{
  g_formats[format] = func;
}

unique_ptr<IPictureWriter> createPictureWriterForFormat(string format)
{
  auto i_func = g_formats.find(format);
  if(i_func == g_formats.end())
    fatal("unknown format");

  return i_func->second();
}
// output_format_bmp.cpp
#include "workflow.h"
#include "output_formats.h"
#include "lib_bmp.h"

class BmpWriter : IPictureWriter
{
  void writePicture(Framebuffer pic, string path)
  {
    writeBmp(pic, path);
  }
};

REGISTER(BmpWriter, "bmp")

As you can see, the growing list of #inclusions has now disappeared from "output_formats.cpp". How does it work?

The macro "REGISTER" is actually defined like this:

#define REGISTER(FormatWriterClass, format) \
  static auto g_registered = registerMe<FormatWriterClass>(format)

So, far so good: the global initialization of "g_registered" will cause "registerMe" to be called ; then, how does the "registerMe" work?

Let’s see the whole file "outut_format.h":

// output_formats.h
#include <functional>
#include <string>
#include <memory>

typedef std::function<std::unique_ptr<IPictureWriter>()> WriterCreationFunc;

void registerFormat(std::string format, WriterCreationFunc func)

template<typename FormatWriterClass>
int registerMe(string format)
{
  auto creationFunc = []()
  {
    return std::make_unique<FormatWriterClass>();
  };
  registerFormat(format, creationFunc);
  return 0; // this value is actually unused
}

#define REGISTER(FormatWriterClass, format) \
  static auto g_registered = registerMe<FormatWriterClass>(format)

Don’t be scared by the lambda, the exact same effect can be achieved using a factory class instead.

The registerMe function simply wraps the proper instanciation of make_unique (i.e the one which uses a concrete format writer class) into a "WriterCreationFunc", which we put into a map.

And that’s it ; we can now add a new format by simply creating a new source file, and adding it to the linking process:

// output_format_tga.cpp
#include "workflow.h"
#include "output_formats.h"
#include "extra/libs/fast_tga.h"

class MyTgaWriter : IPictureWriter
{
  void writePicture(Framebuffer pic, string path)
  {
    fast_tga::writeTga(pic, path);
  }
};

REGISTER(MyTgaWriter, "tga");

Our application can now write .tga files, although no other source file contains nor refers to anything related to TGA ; that’s open-closed as its best!

Some comments: this only is the basic technique, which may need to be refined. Some compilers might issue a warning, as the static variable "g_registered" is unused. Also, using a simple global map isn’t going to work, because of the order of construction: the map might get constructed <em>after</em> some "g_registered" instances. All these problems can be solved by technical details that I’m not going to describe in this post. After all, this post is about abstracting details away! :-)

2. Comments