Metaprogramming in kb_text_shape

kb_text_shape comes as a single-header library because it is the most convenient way to ship C code to users. However, it also contains some huge tables that, clearly, are not hand-typed. Where do they come from? Why are they in the middle of normal C code?

The simple answer is that single-header is the shipping format for the library, and that the development version of the library is, indeed, spread out into multiple files, and significantly messier too:

kb_text_shape
├generated
│├unicode_bullshit.h
│└unicode_bullshit_public.h
├out
│└kb_text_shape.h
├ucd
│└(tons of .txt files)
├build.c
├common.h
├generate_indic_rules.c
├generate_khmer_rules.c
├generate_myanmar_rules.c
├generate_use_rules.c
├indic_rules.h
├kb.h
├kb_text_shape_dev.h
└rules.h
The working directory looks something like this.

This is all of the files that go into developing and building a single version of the shippable library. In this blog post, I will explain the purpose of each of these, and, hopefully, by the end, you will have a sense of what problems you can solve with metaprogramming when working with C.

The metaprogram

    kb.h┐
common.h┴build.c

build.c is the code for the metaprogram. At the time of writing, it is 4868 lines long, and is reponsible for all build-time tasks, including generating all of the code in the generated directory. This is a simple C program: it #includes kb.h, which is my personal basic toolkit when writing C code, as well as common.h, which is a header file shared by both the metaprogram and the real program. In my experience, having a common header that contains everything shared by the build step and the run step is a great way to set up simple metaprogramming tasks without relying on parsing or generating frivolous amounts of code. In my case, common.h contains 187 lines of enum definitions that I would like to use in my metaprogram to generate tables. I could put those definitions inside of build.c, but then the metaprogram would have to generate a copy of them to put in kb_text_shape.h, so keeping them in a separate header saves me the trouble and synchronizes them automatically between the two programs.

Code generation

build.c┐
    ucd┼unicode_bullshit.h
       └unicode_bullshit_public.h

Unicode tables

A significant part of the metaprogram is dedicated to reading data from the Unicode Character Database to generate the tables used in kb_text_shape. We only need a few Unicode properties, and I try to preprocess them as much as I can to make it easy for the library to query the information it needs. Here is the information I keep:

enum
{
  UNICODE_TABLE_DECOMPOSITION, // 2 child codepoints packed into a single word
  UNICODE_TABLE_WORD, // Word break class
  UNICODE_TABLE_LINE, // Line break class
  UNICODE_TABLE_GRAPHEME, // Grapheme break class
  UNICODE_TABLE_SYLLABIC, // Indic syllabic class
  UNICODE_TABLE_FLAGS, // Unicode flags
  UNICODE_TABLE_BIDIRECTIONAL, // Bidirectional class
  UNICODE_TABLE_JOINING, // Arabic joining type
  UNICODE_TABLE_COMBINING, // Combining class
  UNICODE_TABLE_PARENT, // Parent codepoint
  UNICODE_TABLE_USE_CLASS, // Universal Shaping Engine class
  UNICODE_TABLE_SCRIPT_EXTENSION, // Set of scripts
  UNICODE_TABLE_MIRROR, // Mirrored codepoint

  UNICODE_TABLE_COUNT,
};

For each of these properties, I generate a two-tier table along with a function to query it. The choice of page size can greatly influence the table's final footprint, so, to optimize for size, I brute-force try to generate a table for each power-of-two page size and pick the one that results in the smallest table. Since the metaprogram is written in C, I don't really have to worry about the execution time very much; parsing the UCD files and generating all tables in debug mode, with address sanitizer enabled, takes about seven seconds; without address sanitizer, it takes two seconds; in release mode, it takes 600ms.

Structured C data

In kb_text_shape, the shaper uses op lists to sequence its operations. Shaping is divided into passes (or ops), within which font lookups have to be reordered in a certain way for the results to line up with the font designer's intention. This is what an op list looks like in the library:

typedef struct kbts__feature_stage
{
  kbts_u32 FeatureCount;
  kbts__feature_set Features;
} kbts__feature_stage;

typedef struct kbts__op_list
{
  kbts_u32 TotalFeatureCount;
  kbts_u32 FeatureStageCount;
  kbts__feature_stage *FeatureStages;
  kbts_u32 OpCount;
  kbts__op_kind *Ops;
} kbts__op_list;

static kbts__op_kind kbts__Ops_Default[] = {
  KBTS__OP_KIND_NORMALIZE,
  KBTS__OP_KIND_BEGIN_GSUB,
  KBTS__OP_KIND_GSUB_FEATURES,
  KBTS__OP_KIND_GSUB_FEATURES_WITH_USER,
  KBTS__OP_KIND_GPOS_METRICS,
  KBTS__OP_KIND_GPOS_FEATURES,
  KBTS__OP_KIND_POST_GPOS_FIXUP,
};

static kbts__feature_stage kbts__FeatureStages_Default[] = {
  {1, {{0ull, 0ull, 0ull, 0ull | KBTS__FEATURE_FLAG3(rvrn)}}},
  {19, {{0ull | KBTS__FEATURE_FLAG0(frac) | KBTS__FEATURE_FLAG0(numr) | KBTS__FEATURE_FLAG0(dnom) | KBTS__FEATURE_FLAG0(ccmp) |
                KBTS__FEATURE_FLAG0(clig) | KBTS__FEATURE_FLAG0(calt) | KBTS__FEATURE_FLAG0(abvm) | KBTS__FEATURE_FLAG0(blwm) |
                KBTS__FEATURE_FLAG0(curs),
         0ull,
         0ull | KBTS__FEATURE_FLAG2(ltra) | KBTS__FEATURE_FLAG2(ltrm) | KBTS__FEATURE_FLAG2(locl) | KBTS__FEATURE_FLAG2(rlig) |
                KBTS__FEATURE_FLAG2(liga) | KBTS__FEATURE_FLAG2(rclt) | KBTS__FEATURE_FLAG2(mark) | KBTS__FEATURE_FLAG2(mkmk) |
                KBTS__FEATURE_FLAG2(dist) | KBTS__FEATURE_FLAG2(kern),
         0ull}}},
  {7, {{0ull | KBTS__FEATURE_FLAG0(abvm) | KBTS__FEATURE_FLAG0(blwm) | KBTS__FEATURE_FLAG0(curs),
        0ull,
        0ull | KBTS__FEATURE_FLAG2(mark) | KBTS__FEATURE_FLAG2(mkmk) | KBTS__FEATURE_FLAG2(dist) | KBTS__FEATURE_FLAG2(kern),
        0ull}}},
};
static kbts__op_list kbts__OpList_Default = {27,
                                             KBTS__ARRAY_LENGTH(kbts__FeatureStages_Default), kbts__FeatureStages_Default,
                                             KBTS__ARRAY_LENGTH(kbts__Ops_Default), kbts__Ops_Default};

While this is a nice format to ingest at runtime, it is not nice at all to hand-edit or to scan for mistakes: feature flags need to be split into 4 words because they don't fit into a single 64-bit integer, and the data is split into three separate compound literals that all need to be kept in sync. I did edit them manually at first, but it quickly grew tedious and extremely error-prone. This data format is not particularly amenable to X-macros, either, so I decided to generate them from the metaprogram. The advantage of this approach is that it lets me specify the data however is most convenient to me, and then use arbitrary build-time code to transform it into the run-time format for the library.

This is what this same op list looks like in the metaprogram:

static u8 kbts_Ops_Default[] = {
  OP_KIND_NORMALIZE,
  OP_KIND_BEGIN_GSUB,
  OP_KIND_GSUB_FEATURES, 1, OPENTYPE_FEATURE_rvrn,
  OP_KIND_GSUB_FEATURES_WITH_USER, 19,
    OPENTYPE_FEATURE_frac, OPENTYPE_FEATURE_numr, OPENTYPE_FEATURE_dnom, OPENTYPE_FEATURE_ccmp, OPENTYPE_FEATURE_clig, OPENTYPE_FEATURE_calt,
    OPENTYPE_FEATURE_ltra, OPENTYPE_FEATURE_ltrm, OPENTYPE_FEATURE_locl, OPENTYPE_FEATURE_rlig, OPENTYPE_FEATURE_liga, OPENTYPE_FEATURE_rclt,
    OPENTYPE_FEATURE_abvm, OPENTYPE_FEATURE_blwm, OPENTYPE_FEATURE_curs,
    OPENTYPE_FEATURE_mark, OPENTYPE_FEATURE_mkmk, OPENTYPE_FEATURE_dist, OPENTYPE_FEATURE_kern,
  OP_KIND_GPOS_METRICS,
  OP_KIND_GPOS_FEATURES, 7,
    OPENTYPE_FEATURE_abvm, OPENTYPE_FEATURE_blwm, OPENTYPE_FEATURE_curs,
    OPENTYPE_FEATURE_mark, OPENTYPE_FEATURE_mkmk, OPENTYPE_FEATURE_dist, OPENTYPE_FEATURE_kern,
  OP_KIND_POST_GPOS_FIXUP,
};

This is a much better authoring format: there is only one array to write, and I don't need to worry about which feature goes into which word of the final bitfield. The metaprogram parses these arrays and generates the corresponding runtime form I described above.

Enum-related code generation

There are a few places where we want to “attach” properties to enum members. An example of this is the ScriptTagToScript function, which tries to map a sparse set of tags to tightly-packed indices. While this sort of straightforward transform can be achieved with X-macros, and that is the way I originally did it, I have found that the more places want to use each enum this way, the nicer it is to have a concrete structural representation for them that I can traverse at build time.

This is how scripts are defined in the metaprogram:

typedef struct script
{
  string UnicodeName;
  char UnicodeC0;
  char UnicodeC1;
  char UnicodeC2;
  char UnicodeC3;

  string InternalName;
  kbts_shaper Shaper;
  char C0;
  char C1;
  char C2;
  char C3;
} script;

static script Scripts[SCRIPT_ID_COUNT] = {
  {STRING_(“DontKnow”), ' ', ' ', ' ', ' ', STRING_(“DONT_KNOW”), KBTS_SHAPER_DEFAULT, ' ', ' ', ' ', ' '},
  {STRING_(“Adlam”), 'A', 'd', 'l', 'm', STRING_(“ADLAM”), KBTS_SHAPER_USE, 'a', 'd', 'l', 'm'},
  {STRING_(“Ahom”), 'A', 'h', 'o', 'm', STRING_(“AHOM”), KBTS_SHAPER_USE, 'a', 'h', 'o', 'm'},
  {STRING_(“Anatolian_Hieroglyphs”), 'H', 'l', 'u', 'w', STRING_(“ANATOLIAN_HIEROGLYPHS”), KBTS_SHAPER_DEFAULT, 'h', 'l', 'u', 'w'},
  {STRING_(“Arabic”), 'A', 'r', 'a', 'b', STRING_(“ARABIC”), KBTS_SHAPER_ARABIC, 'a', 'r', 'a', 'b'},
  {STRING_(“Armenian”), 'A', 'r', 'm', 'n', STRING_(“ARMENIAN”), KBTS_SHAPER_DEFAULT, 'a', 'r', 'm', 'n'},
  // etc.
}

The Unicode values in the struct above are used by the metaprogram to link the scripts described in the UCD to the scripts used by OpenType. If I had stuck to X-macros in kb_text_shape, then I would have had to describe an auxiliary data structure in the metaprogram to make these connections anyway, so working directly with the structural representation turns out to be a decent complexity win.

Generation targets

As you may have noticed from the dependency diagram at the start of this section, the metaprogram generates two separate files: unicode_bullshit.h contains code that will be inserted in the library's “implementation” section, meaning that it will be hidden to the user and used strictly internally by the library. In contrast, unicode_bullshit_public.h will be inserted in the library's “header” section, meaning it will be visible and accessible to the user of the library. The public code only contains a few enums for scripts, script tags and OpenType feature tags.

Generating the final header

      kb_text_shape_dev.h┐
                 common.h┤
       unicode_bullshit.h┤
unicode_bullshit_public.h┴kb_text_shape.h

Now that all of the code that goes into a release version of the library has been generated, we can merge it into a single file. To do this, our metaprogram scans through kb_text_shape_dev.h, finds all of the #include directives, and glues the files together. Now obviously, this is not done for system headers; we specifically scan for local includes (the ones that use “” instead of <>). This is quite a nice way to disambiguate between the includes that should be left in the release code, and those that need to be handled now, without using any new syntax. The metaprogram correctly skips comments and handles recursive includes because older versions of the library used them; as it stands, all of the includes are flat.

That's it! Now, I just need to copy the resulting kb_text_shape.h to my public repositories and push them.

The stupid part

rules.h┐
       ├indic_rules.h┐
       │             ├generate_indic_rules.c
       │             ├generate_khmer_rules.c
       │             └generate_myanmar_rules.c
       └──────────────generate_use_rules.c

Some shaping models require a clustering pass. This clustering pass is described with a regex-like notation and is usually implemented with an FSM. Now, I would like the FSM stepping code to be hand-written, so that I can simply generate the transition table and then modify the stepping loop however I need to depending on the shaping model's constraints. As it turns out, I do not know of any tool that does exactly what I want, but I found something that was very close.

This web tool translates a regex to a state table, and seemed pretty robust. However, there are some limits to the kinds of inputs it accepts: inputs need to be single-letter, and it only accepts basic regex operators. Rewriting all of the clustering rules to this syntax seemed very tedious and extremely error-prone. It seemed like I would have to write a custom regex-like format, and then convert it to the simplified notation to feed to this conversion tool.

I did not end up writing a parser at all. Call me crazy, but I have found the C preprocessor to be extremely effective at tasks like this. The idea is that we use macros to define a structural input syntax which we then use to generate a flat output string through string concatenation. In the include diagram above, the generate files contain grammar definitions, i.e. all of the grouped or complex rules we want to match. They also contain a main function that prints the final regex:

// generate_khmer_rules.c
#include “indic_rules.h”

#define C GROUP(CONSONANT OR RA OR VOWEL)
#define JOINER GROUP(ZWJ OR ZWNJ)
#define CN GROUP(C MAYBE(MAYBE(JOINER) ROBATIC))
#define X ANY(ANY(JOINER) X_GROUP)
#define Y ANY(Y_GROUP)
#define MATRA_GROUP GROUP(MAYBE(VOWEL_PRE) X MAYBE(VOWEL_BELOW) X MAYBE(MAYBE(JOINER) VOWEL_ABOVE) X MAYBE(VOWEL_POST))
#define SYLLABLE_TAIL GROUP(X MATRA_GROUP X MAYBE(HALANT C) Y)
#define BROKEN_CLUSTER GROUP(MAYBE(ROBATIC) ANY(HALANT CN) GROUP(HALANT OR SYLLABLE_TAIL))
#define CONSONANT_SYLLABLE GROUP(GROUP(CN OR PLACEHOLDER OR DOTTED_CIRCLE) BROKEN_CLUSTER)
#define CLUSTER GROUP(BROKEN_CLUSTER OR CONSONANT_SYLLABLE)

#include <stdio.h>
int main(int ArgumentCount, char **Arguments)
{
  printf(“%s\n”, CLUSTER);
  return 0;
}

The indic_rules.h header contains terminator definitions, i.e. it maps Indic syllabic classes, which I mentioned earlier, to single-letter variables that the regex converter will accept (in the case of generate_use_rules.c, the terminator definitions are directly included in the .c file):

// indic_rules.h
#include “rules.h”

#define OTHER “A”
#define CONSONANT “B”
#define VOWEL “C”
#define NUKTA “D”
#define HALANT “E”
#define ZWNJ “F”
#define ZWJ “G”
#define MATRA “H”
#define SYLLABLE_MODIFIER “I”
#define VEDIC_SIGN “J”
#define PLACEHOLDER “K”
#define DOTTED_CIRCLE “L”
#define REGISTER_SHIFTER “M”
#define MATRA_POST “N”
#define REPHA “O”
#define RA “P”
#define CONSONANT_MEDIAL “Q”
#define SYMBOL “R”
#define CONSONANT_WITH_STACKER “S”
#define SYLLABLE_MODIFIER_POST “T”
#define VOWEL_ABOVE “U”
#define VOWEL_BELOW “V”
#define VOWEL_PRE “W”
#define VOWEL_POST “X”
#define ROBATIC “Y”
#define X_GROUP “Z”
#define Y_GROUP “a”
#define ASAT “b”
#define DOT_BELOW “c”
#define SYLLABLE_MOD “d”
#define MEDIAL_HA “e”
#define MEDIAL_RA “f”
#define MEDIAL_WA “g”
#define MEDIAL_YA “h”
#define PWO “i”
#define VARIATION_SELECTOR “j”
#define MEDIAL_MON_LA “k”

Finally, rules.h contains the basic regex operators:

// rules.h
#define OR “|”
#define ANY(S) “(” S “)*”
#define ONE_OR_MORE(S) “(” S “)+”
#define GROUP(S) “(” S “)”
#define MAYBE(S) “(” S “)?”

If we compile generate_khmer_rules.c and run it, we get this beautiful regex:

(((Y)?(E((B|P|C)(((G|F))?Y)?))*(E|((((G|F))*Z)*((W)?(((G|F))*Z)*(V)?(((G|F))*Z)*(((G|F))?U)?(((G|F))*Z)*(X)?)(((G|F))*Z)*(E(B|P|C))?(a)*)))|((((B|P|C)(((G|F))?Y)?)|K|L)((Y)?(E((B|P|C)(((G|F))?Y)?))*(E|((((G|F))*Z)*((W)?(((G|F))*Z)*(V)?(((G|F))*Z)*(((G|F))?U)?(((G|F))*Z)*(X)?)(((G|F))*Z)*(E(B|P|C))?(a)*)))))

Which is 308 characters long. If you are not impressed yet, here is the Indic one, which is a whopping 847 characters:

(((R(D)?)((((G|F))?(I|T)((I|T))?(F)?)?(J)*))|((((PE)|O))?((((F)?M)?(D(D)?)?))?(((((G|F))?E(G(D)?)?)((B|P)(G)?((((F)?M)?(D(D)?)?))?))*(Q)?(((((G|F))?E(G(D)?)?)|(EF))|((((G|F))*(H|(((I|T))?N))(D)?(E)?))*)((((G|F))?(I|T)((I|T))?(F)?)?(J)*)))|((((O|S)?K)|((((PE)|O))?L))((((F)?M)?(D(D)?)?))?(((((G|F))?E(G(D)?)?)((B|P)(G)?((((F)?M)?(D(D)?)?))?))*(Q)?(((((G|F))?E(G(D)?)?)|(EF))|((((G|F))*(H|(((I|T))?N))(D)?(E)?))*)((((G|F))?(I|T)((I|T))?(F)?)?(J)*)))|((((PE)|O))?C((((F)?M)?(D(D)?)?))?(G|(((((G|F))?E(G(D)?)?)((B|P)(G)?((((F)?M)?(D(D)?)?))?))*(Q)?(((((G|F))?E(G(D)?)?)|(EF))|((((G|F))*(H|(((I|T))?N))(D)?(E)?))*)((((G|F))?(I|T)((I|T))?(F)?)?(J)*))))|((O|S)?((B|P)(G)?((((F)?M)?(D(D)?)?))?)(((((G|F))?E(G(D)?)?)((B|P)(G)?((((F)?M)?(D(D)?)?))?))*(Q)?(((((G|F))?E(G(D)?)?)|(EF))|((((G|F))*(H|(((I|T))?N))(D)?(E)?))*)((((G|F))?(I|T)((I|T))?(F)?)?(J)*))))

And if you are still unfazed, then you should know that this very blog is generated using a variant of this technique.

Anyway, as if this wasn't stupid enough, I still manually converted the state table from the regex-to-DFA converted to a transition table I could use directly from C. In practice, coming up with the regex generators and doing the table conversion took a few hours, and, thankfully, clustering rules are unlikely to change very often, so this seemed like an acceptable price to pay to get exactly the tables I wanted without having to implement and debug the conversion myself.