Riley Fischer
Generics Generator My journey through the development of this tool Preface Welcome! I'm glad you're interested in this blog about my generics generator project! It's been a really interesting journey getting to the point I'm at with it, and I will share that here.

There are two main timelines discussed here:
  • Generics Generator in Zig
  • Generics Generator in C

You will understand why there are two by the end of this blog.

Enjoy! So Why Generics Generator? As a C programmer that came from C++, I've always felt that generic datastructures were kind of a pain in the butt to use. You'd have to rewrite the exact same code for every underlying data type you want to use, and while it works I thought that wasn't a reasonable way to solve the problem. So for the past few months I've been working on a solution to that problem. My journey to the solution wasn't a straight path however, and that's the store this blog will tell. The Idea The initial thoughts was that it would be a command line driven tool. It would look in a specified search directory for files labeled with the .tpl extention. This file would define what that template was for: the source template files, the replacements, and the dependencies.

For every new template you wanted to make you would write a new .tpl file and put it in the search directory, then voila it is now a template that can be generated.

I didn't know it at the time, but this method wouldn't work very well when used in existing C build toolchains like Makefile, Cmake, Meson, etc.
 How does it work? The zig version worked purely off a command line interface. However the way it does so is pretty flexible.

Templates can be put anywhere in your filesystem you wish, as generics-generator-zig allows you to specify where your templates are located via a shell environment variable GEN_TEMPLATE_PATH
It will look for files ending in .tpl in whatever path you set that variable to.

When it finds a file matching that description it will read it, and be able to give you all the information you need in order to fill out the replacements you specified (more on this later).

You can now pass different values into the template and it will generate a file with the contents of your template except now it is filled out with those replacements.

Additionally, each template has the option to define another template to be a dependency. This is to allow for situations where you might want to use another datastructure youve written as a template in another template.

For example, you could implement a queue that utlizes a linkedlist and have the corresponding linked list generate alongside the queue.
 Now what do these template files I'm speaking of look like? Lets go over that.

The followng example will include all the features of the program to demonstrate as much as possible.
Example Template File
 name = "queue" generators = ["queue.htpl", "queue.ctpl"] outformat = "queue_T" [deps.linked_list] datatype = "datatype-type" free = "free" [args.datatype-name] symbol = "$T" [args.datatype-type] symbol = "@T" [args.free] symbol = "FREE" default = "free" [args.print] symbol = "PRINT" default = "printf" [args.calloc] symbol = "CALLOC" default = "calloc" [args.realloc] symbol = "REALLOC" default = "realloc" [args.header] symbol = "HEADER_INCLUDE" default = "stdint.h"
  • name -> defines the name of this template (this field would be used to identify this template from the cli)
  • generators -> defines the list of files that are used to generate the output files (this contains the content of the template)
  • outformat -> defines the format string for how the output files should be named
    • In this case it is saying to output the file using whatever was specified for the 'datatype' argument
  • deps -> defines what other templates this template depends on and how to construct it
      Each entry defines a rule on how to forward args to the dependent.
    • The datatype argument for linked_list will be given the value that the datatype-type argument was given for queue
  • args -> defines what the variables for the template are (this is the meat of the tool)
    • datatype -> the datatype argument here is given the symbol T with no default replacement. This makes it a required argument on the cli.
    • free -> the free argument here is given the symbol FREE with a default replacement of free. This makes it an optional argument on the cli.
    • print -> the print argument here is given the symbol PRINT with a default replacement of printf. This makes it an optional argument on the cli.
I still think that this is generally a good way of describing a template via a file, however the fact that it is a file ended up being the main problem. It meant that you have to keep around this file along with the specific generator files that were used by this template. Demo Next, I will give a demonstration of the workflow for the first zig version.

First things first, you need to decide where your templates should live. This is configured via a shell environment variable GEN_TEMPLATE_PATH. If this value is not provided by default it uses the current working directory.

If setup correctly the help output of generics-generator will now display all the templates it finds in the selected directory. $ generics-generator --help Generics generator Usage: generics-gen [COMMAND] Commands: linked_list
Here we can see that it found a linked_list template! Furthermore each template has its own help message!
 $ generics-generator linked_list --help Usage: generics-gen linked_list [OPTIONS] Options: -f, --free= default = free -p, --print= default = printf -d, --datatype= -o, --outputdir= default = . -h, --help Print this help and exit This linked list is from the same linked_list template I provided in the previous section, and you can see that all the provided args are part of the linked_list subcommand

Also note that the datatype arg has no default value like the others, this is a required field.
Why It Didn't Work Once I was done with the Zig version of generics generator I was finding it difficult to use! I realized that I hadn't thought about how it would be actually used in a codebase.

The way it was structured didn't lend itself to working within the existing build process of a project (commonly Make or CMake) and this is how I originally intended it to be used. Because it required all the input as command line arguments, depending on how many parameters your template had it would make the build code really long, unweildy, and unreadable.

There were ways to make it work, but they were quite cumbersom when you had many templates you needed to generate. Here's an example Makefile for it. OUT_DIR := out GEN_FILES := src/generated/linked_list_int.c \\ src/generated/linked_list_vec2.c \\ src/generated/binary_tree_int.c \\ src/generated/binary_tree_vec2.c \\ src/generated/hash_table_string_int.c \\ src/generated/vector_int.c \\ src/generated/stack_int.c TPL_OUTDIR := src/generated SOURCES := src/main.c $(GEN_FILES) BIN := main # Override the template search path to the local templates folder export GEN_TEMPLATE_PATH=templates .PHONY: template_gen .PHONY: clean always build always: mkdir -p $(OUT_DIR) mkdir -p $(TPL_OUTDIR) clean: rm -r $(OUT_DIR) rm -r $(TPL_OUTDIR) build: always template_gen $(OUT_DIR)/$(BIN) $(OUT_DIR)/$(BIN): $(SOURCES) gcc $^ -o $@ -Isrc -Isrc/generated -ggdb template_gen: $(GEN_FILES) $(TPL_OUTDIR)/linked_list_int.c $(TPL_OUTDIR)/linked_list_int.h: templates/linked_list.tpl templates/linked_list.htpl templates/linked_list.ctpl generics-generator linked_list --datatype=int --outputdir=$(TPL_OUTDIR) $(TPL_OUTDIR)/linked_list_vec2.c $(TPL_OUTDIR)/linked_list_vec2.h: templates/linked_list.tpl templates/linked_list.htpl templates/linked_list.ctpl generics-generator linked_list --datatype=vec2 --header="vec2.h" --outputdir=$(TPL_OUTDIR) $(TPL_OUTDIR)/binary_tree_int.c $(TPL_OUTDIR)/binary_tree_int.h: templates/binary_tree.tpl templates/binary_tree.htpl templates/binary_tree.ctpl generics-generator binary_tree --datatype=int --outputdir=$(TPL_OUTDIR) $(TPL_OUTDIR)/binary_tree_vec2.c $(TPL_OUTDIR)/binary_tree_vec2.h: templates/binary_tree.tpl templates/binary_tree.htpl templates/binary_tree.ctpl generics-generator binary_tree --datatype=vec2 --header="vec2.h" --outputdir=$(TPL_OUTDIR) $(TPL_OUTDIR)/hash_table_string_int.c $(TPL_OUTDIR)/hash_table_string_int.h: templates/hash_table.tpl templates/hash_table.htpl templates/hash_table.ctpl generics-generator hash_table --key-name="string" --key-type="const char*" --val-name="int" --val-type="int" --outputdir=$(TPL_OUTDIR) $(TPL_OUTDIR)/vector_int.c $(TPL_OUTDIR)/vector_int.h: templates/vector.tpl templates/vector.htpl templates/vector.ctpl generics-generator vector --datatype=int --outputdir=$(TPL_OUTDIR) $(TPL_OUTDIR)/stack_int.c $(TPL_OUTDIR)/stack_int.h: templates/stack.tpl templates/stack.htpl templates/stack.ctpl generics-generator stack --datatype=int --outputdir=$(TPL_OUTDIR)`
Here we can see that it found a linked_list template! Furthermore each template has its own help message!
 $ generics-generator linked_list --help Usage: generics-gen linked_list [OPTIONS] Options: -f, --free= default = free -p, --print= default = printf -d, --datatype= -o, --outputdir= default = . -h, --help Print this help and exit
You can see here this is very repetitive Makefile code. There are 7 different targets that do nearly the same thing, but they are different enough to need 7 different targets!
On top of being repetitive, its just flat out hard to read and understand what's going on here! I won't break down how this works, but if any of you are Makefile nerds like me feel free to read it further.

This probably doesn't need to be as verbose as I made it here but if you want to get incremental builds then this is what is needed for Makefile.

So at this point I knew I had to take what I learned here and make a better, more useful version.

Here is a link to the first zig version. Generics Generator (Zig) The Start of the C Version Given everything described above, I felt that I needed to find another solution to this problem. So using all the knowledge I gained about what was good and not so good about the Zig version I started prototyping a new version.

An important point of the c version was that it had to have feature parity with the Zig version. This requirement was really helpful because it allowed me to have a focus, and not accidentally expand the scope too far. The features that needed to stay are as follows:
  1. Ability to replace a given symbol with another (basic, without this its not the same concept anymore)
  2. Support for dependency templates
  3. Configuration of where templates live, and where the outputs go
The main extra requirement was that it must be simpler to use in a C/C++ project

So how does it accomplish those goals?
  1. The C version gets rid of the .tpl file entirely
  2. It removes command line arguments entirely without losing configurability
  3. It is written in a header-only style
  4. All template configuration is done in C with a well defined API

Demo The C version is completely code oriented. Everything can be written in a single build.c file.

Let's write one here real quick, then we'll discuss what it means.
We'll write a build script that generates the same queue that we saw earlier.
 #define GENGEN_IMPLEMENTATION // allows the implementation code to be compiled when build.c is compiled #include "gengen.h" int main() { // Setup the queue template information ctemplate queuetpl = template_create(); template_addfile (&queuetpl, "queue.htpl", "queue_$T.h"); template_addfile (&queuetpl, "queue.ctpl", "queue_$T.c"); template_addreplacement(&queuetpl, "$T", NULL); template_addreplacement(&queuetpl, "^T", NULL); template_addreplacement(&queuetpl, "PRINTF", "printf"); template_addreplacement(&queuetpl, "FREE", "free"); template_addreplacement(&queuetpl, "CALLOC", "calloc"); template_addreplacement(&queuetpl, "HEADER", "stdint.h"); // Setup the linked list template information ctemplate lltpl = template_create(); template_addfile (&lltpl, "linkedlist.htpl", "linkedlist_$T.h"); template_addfile (&lltpl, "linkedlist.ctpl", "linkedlist_$T.c"); template_addreplacement(&lltpl, "$T", NULL); template_addreplacement(&lltpl, "^T", NULL); template_addreplacement(&lltpl, "PRINTF", "printf"); template_addreplacement(&lltpl, "FREE", "free"); template_addreplacement(&lltpl, "CALLOC", "calloc"); template_addreplacement(&lltpl, "HEADER", "stdint.h"); // Setup the forwarding table forward_table fwd_q_ll = forward_table_create(); forward_table_forward(&fwd_q_ll, fwd(.symbol="$T", .as="$T")); forward_table_forward(&fwd_q_ll, fwd(.symbol="^T", .as="^T")); // Setup the dependency and specify how we forward to it (fwd_q_ll) template_adddep(&queue, linkedlist, fwd_q_ll); // Setup a specific replacement context for queue replacement queue_int = replacement_create(); replacement_add(&queue_int, "$T", "int"); replacement_add(&queue_int, "^T", "int"); // Setup a specific replacement context for queue replacement queue_long = replacement_create(); replacement_add(&queue_long, "$T", "long"); replacement_add(&queue_long, "^T", "long"); // Run the generators for the setup templates and replacements generator_run(settings_custom(.search_paths=paths("demo_templates", "."), .outdir="."), linkedlist, ll_int); generator_run(settings_custom(.search_paths=paths("demo_templates", "."), .outdir="."), linkedlist, ll_string); generator_run(settings_custom(.search_paths=paths("demo_templates", "."), .outdir="."), queue , queue_int); generator_run(settings_custom(.search_paths=paths("demo_templates", "."), .outdir="."), queue , queue_long); }
What does this mean?
First we setup the queue template, then we setup the linked_list template.
  • template_create() - Sets up an empty template context.
  • template_addfile(...) - Adds a new source file and specifies the output filename format
  • template_addreplacement(...) - Adds a new replacement that defines symbols and what they should be replaced with

Next we setup the forwarding table that defines how the linked_list is going to get its required replacements.
  • forward_table_create() - Sets up an empty forwarding table
  • forward_table_forward(...) - Adds a new forwarding rule to the forwarding table

Next we tell the queue that it depends on the linked_list and what forwarding table should be used for generation.
  • template_adddep(...) - Adds another template as a dependency using a particular forwarding table

Now we're done setting up the templates themselves. They know:
  • what symbols to expect and what they should be replaced with by default
  • what templates they depend on (if any).

We're almost done! And here comes the component that allows for extreme reusability.
We need to now setup the specific replacements for the different variants of a template we want.
  • replacement_create() - Sets up an empty replacement set
  • replacement_add(...) - Defines what a certain symbol should be replaced with

Finally we're at the point where we can run the generator and create our final output files.
  • generator_run(...) - Runs the generator with specified settings, a template, and a replacement
    • settings
      • .search_paths[] - Where should the generator search for the source template files
      • .outdir - Where should the generator put the output file
      • .verbose - Should the generator produce verbose output
 Conclusion This journey of working on generics generator has been a very enjoyable one.

One of the main concepts I learned is that 'you don't know what you don't know'

It sounds cliche, but when I started this I had a good idea of what I wanted. I was convinced it was the perfect idea and design, but it wasn't until I finished the zig version that I realized the major oversights it had.

With this knowledge I was able to make a version that works better for the target audience and is significanly simpler.

Thank you for being interested in my development journey.

To take a look at either project here are the github links.
Generics Generator (Zig)
Generics Generator (C)