Carry variation sequences (cmap format 14)

The section now carries each sequence the font maps, a base and a
selector, with the glyph HarfBuzz gives the pair (a default one's the
base's own). As HarfBuzz's normalizer does, a sequence the font has
becomes that one glyph, the two characters' clusters merged; one it lacks
still passes on as two, the selector hidden. The header grows to 88 bytes
for the table.

The random check now mixes in the font's own sequences and stray
selectors: 30000 runs over Noto Sans CJK's 14787 ideographic variation
sequences are HarfBuzz's, and so are the installed fonts' and Noto's.
HarfBuzz's suite: 5014 of 5199 the same, none different; what is left is
what the build refuses and one run without a plan.

4 files changed, 113 insertions, 17 deletions

diff --git a/text/harfbuzz-suite.known b/text/harfbuzz-suite.known
index f6d9b6d..4b93ab4 100644
--- a/text/harfbuzz-suite.known
+++ b/text/harfbuzz-suite.known
@@ -6,11 +6,6 @@
 text-rendering-tests/MORX-*        # AAT
 in-house/aat-*                     # AAT
 
-# Variation selectors (cmap format 14).
-text-rendering-tests/CMAP-1.tests:2    # cmap format 14
-text-rendering-tests/CMAP-1.tests:3    # cmap format 14
-text-rendering-tests/CMAP-2.tests:2    # cmap format 14
-
 # Arabic fallback shaping where two characters share a glyph (refused).
 in-house/arabic-fallback-shaping.tests:2
 in-house/arabic-fallback-shaping.tests:3
diff --git a/text/shape-build.c b/text/shape-build.c
index fac333b..98a12b0 100644
--- a/text/shape-build.c
+++ b/text/shape-build.c
@@ -898,6 +898,16 @@ static bool fallback_table(hb_font_t *font, Bytes *gsub, uint8_t *features, unsi
     return !failed;
 }
 
+static int by_sequence(const void *a, const void *b) {
+    const unsigned char *x = a, *y = b;
+    for (int k = 0; k < 8; k += 4) {
+        uint32_t p = (uint32_t)x[k] | (uint32_t)x[k + 1] << 8 | (uint32_t)x[k + 2] << 16 | (uint32_t)x[k + 3] << 24;
+        uint32_t q = (uint32_t)y[k] | (uint32_t)y[k + 1] << 8 | (uint32_t)y[k + 2] << 16 | (uint32_t)y[k + 3] << 24;
+        if (p != q) return p < q ? -1 : 1;
+    }
+    return 0;
+}
+
 bool vega_shaping_compile(hb_face_t *face, const uint32_t *scripts, size_t script_count, const uint32_t *codes,
                           size_t code_count, VegaSection *out, hb_set_t *glyphs, char *error, size_t error_size) {
     Plan *plans = calloc(2 * script_count + 1, sizeof(*plans));
@@ -956,11 +966,35 @@ bool vega_shaping_compile(hb_face_t *face, const uint32_t *scripts, size_t scrip
     put32(&o, 0);
     put16(&o, hb_face_get_upem(face));
     put16(&o, glyph_count);
-    for (int i = 0; i < 17; ++i) put32(&o, 0);
+    for (int i = 0; i < 19; ++i) put32(&o, 0);
     set32(&o, 12, group_count);
     set32(&o, 16, (uint32_t)o.size);
     for (uint32_t i = 0; i < 3 * group_count; ++i) put32(&o, groups[i]);
     free(groups);
+    /* Variation sequences (cmap format 14): each selector's bases, and the
+     * glyph HarfBuzz gives the pair (a default one's is the base's own). */
+    hb_set_t *selectors = hb_set_create(), *bases = hb_set_create();
+    hb_face_collect_variation_selectors(face, selectors);
+    uint32_t sequence_count = 0;
+    size_t sequences_at = o.size;
+    for (hb_codepoint_t v = HB_SET_VALUE_INVALID; hb_set_next(selectors, &v);) {
+        hb_set_clear(bases);
+        hb_face_collect_variation_unicodes(face, v, bases);
+        for (hb_codepoint_t u = HB_SET_VALUE_INVALID; hb_set_next(bases, &u);) {
+            hb_codepoint_t g;
+            if (!hb_font_get_variation_glyph(font, u, v, &g)) continue;
+            put32(&o, u);
+            put32(&o, v);
+            put32(&o, g);
+            sequence_count++;
+        }
+    }
+    hb_set_destroy(selectors);
+    hb_set_destroy(bases);
+    /* By base, then selector (they came by selector). */
+    if (!o.failed) qsort(o.bytes + sequences_at, sequence_count, 12, by_sequence);
+    set32(&o, 80, sequence_count);
+    set32(&o, 84, (uint32_t)sequences_at);
     set32(&o, 20, (uint32_t)o.size);
     for (unsigned g = 0; g < glyph_count; ++g) {
         hb_position_t advance = hb_font_get_glyph_h_advance(font, g);
@@ -1297,6 +1331,25 @@ void vega_shaping_check(hb_font_t *font, const VegaShaping *s, uint32_t script,
     }
     hb_set_destroy(inputs);
     if (!letters.count) letters = others, others = (Pool){0};
+    /* Variation sequences the font maps whose base is among the codes: a
+     * base, then its selector (bases[k] and selectors[k]). */
+    Pool bases = {0}, selectors = {0};
+    hb_set_t *given = hb_set_create(), *vs = hb_set_create(), *us = hb_set_create();
+    for (size_t i = 0; i < code_count; ++i) hb_set_add(given, codes[i]);
+    hb_face_collect_variation_selectors(hb_font_get_face(font), vs);
+    for (hb_codepoint_t v = HB_SET_VALUE_INVALID; hb_set_next(vs, &v);) {
+        hb_set_clear(us);
+        hb_face_collect_variation_unicodes(hb_font_get_face(font), v, us);
+        for (hb_codepoint_t u = HB_SET_VALUE_INVALID; hb_set_next(us, &u);)
+            if (hb_set_has(given, u)) {
+                pool_add(&bases, u);
+                pool_add(&selectors, v);
+            }
+    }
+    size_t sequences = bases.count < selectors.count ? bases.count : selectors.count;
+    hb_set_destroy(given);
+    hb_set_destroy(vs);
+    hb_set_destroy(us);
     VegaShaper *shaper = vega_shaper_new();
     hb_buffer_t *buffer = hb_buffer_create();
     Random random = {seed * 0x9E3779B97F4A7C15ULL + script + 1};
@@ -1324,7 +1377,15 @@ void vega_shaping_check(hb_font_t *font, const VegaShaping *s, uint32_t script,
                         n = indic_syllable(&random, indic, text, n);
                         continue;
                     }
+                    if (sequences && !below(&random, 8)) {
+                        size_t k = below(&random, (uint32_t)sequences);
+                        text[n++] = bases.items[k];
+                        text[n++] = selectors.items[k];
+                        continue;
+                    }
                     text[n++] = hot.count && below(&random, 3) == 0 ? pick(&random, &hot) : pick(&random, &letters);
+                    /* a selector the font may not map after it */
+                    if (!below(&random, 60)) text[n++] = 0xFE00 + below(&random, 16);
                     if (marks.count && below(&random, 100) < mark_rate) {
                         text[n++] = pick(&random, &marks);
                         if (!below(&random, 5)) text[n++] = pick(&random, &marks);
@@ -1385,6 +1446,8 @@ void vega_shaping_check(hb_font_t *font, const VegaShaping *s, uint32_t script,
     hb_buffer_destroy(buffer);
     vega_shaper_free(shaper);
     free(letters.items);
+    free(bases.items);
+    free(selectors.items);
     free(marks.items);
     free(others.items);
     free(hot.items);
diff --git a/text/shape.c b/text/shape.c
index 926632d..2c8d2a6 100644
--- a/text/shape.c
+++ b/text/shape.c
@@ -229,6 +229,16 @@ bool vega_shaping_open(VegaShaping *s, const unsigned char *bytes, size_t size,
         s->attach_classes = offset16(s->gdef, 0, 10);
         s->mark_sets = minor >= 2 ? offset16(s->gdef, 0, 12) : 0;
     }
+    s->sequence_count = le32(bytes + 80);
+    uint32_t sequences = le32(bytes + 84);
+    if (!within(size, sequences, (uint64_t)s->sequence_count * 12)) REFUSE("variation sequences");
+    s->sequences = bytes + sequences;
+    for (uint32_t i = 0; i < s->sequence_count; ++i) {
+        const unsigned char *q = s->sequences + 12 * (size_t)i;
+        if ((i && (le32(q) < le32(q - 12) || (le32(q) == le32(q - 12) && le32(q + 4) <= le32(q - 8)))) ||
+            le32(q + 8) >= s->glyph_count)
+            REFUSE("variation sequence %u", i);
+    }
     size_t subtables = 0, allocated = 0;
     uint32_t fallback = le32(bytes + 76);
     if (fallback) {
@@ -857,6 +867,23 @@ static bool compose(const Normalizer *c, uint32_t a, uint32_t b, uint32_t *ab) {
 
 static bool nominal(const VegaShaping *s, uint32_t u, uint32_t *glyph) { return (*glyph = vega_shaping_glyph(s, u)) != 0; }
 
+/* The glyph the font gives base followed by selector (cmap format 14). */
+static bool variation_glyph(const VegaShaping *s, uint32_t base, uint32_t selector, uint32_t *glyph) {
+    uint32_t low = 0, high = s->sequence_count;
+    while (low < high) {
+        uint32_t middle = (low + high) / 2;
+        const unsigned char *q = s->sequences + 12 * (size_t)middle;
+        uint32_t b = le32(q), v = le32(q + 4);
+        if (b < base || (b == base && v < selector)) low = middle + 1;
+        else if (b > base || v > selector) high = middle;
+        else {
+            *glyph = le32(q + 8);
+            return true;
+        }
+    }
+    return false;
+}
+
 static void output_char(VegaShaper *b, uint32_t unichar, uint32_t glyph) {
     b->info[b->idx].glyph_index = glyph;
     size_t before = b->out_len;
@@ -951,21 +978,27 @@ static void decompose_current_character(const Normalizer *c, bool shortest) {
     next_char(b, 0);
 }
 
-/* A variation selector's cluster: normalization gives up on it. (Variation
- * sequences the font maps, cmap format 14, are not carried: each character
- * passes on alone, the selector hidden.) */
+/* A variation selector's cluster: normalization gives up on it. A
+ * sequence the font maps (cmap format 14) becomes its glyph; otherwise
+ * each character passes on alone, the selector hidden. */
 static void handle_variation_selector_cluster(const Normalizer *c, size_t end) {
     VegaShaper *b = c->b;
     uint32_t glyph;
     while (b->idx + 1 < end && b->successful) {
         if (variation_selector(b->info[b->idx + 1].codepoint)) {
-            b->info[b->idx].glyph_index = nominal(c->s, b->info[b->idx].codepoint, &glyph) ? glyph : 0;
-            next_glyph(b);
-            b->scratch |= HAS_VARIATION_SELECTOR_FALLBACK;
-            Info *vs = &b->info[b->idx];
-            vs->uprops = (uint16_t)((vs->uprops & ~0x1Fu & 0xFF) | VEGA_CF | UPROPS_VS);
-            vs->glyph_index = nominal(c->s, vs->codepoint, &glyph) ? glyph : 0;
-            next_glyph(b);
+            if (variation_glyph(c->s, b->info[b->idx].codepoint, b->info[b->idx + 1].codepoint, &glyph)) {
+                b->info[b->idx].glyph_index = glyph;
+                uint32_t unicode = b->info[b->idx].codepoint;
+                replace_glyphs(b, 2, 1, &unicode);
+            } else {
+                b->info[b->idx].glyph_index = nominal(c->s, b->info[b->idx].codepoint, &glyph) ? glyph : 0;
+                next_glyph(b);
+                b->scratch |= HAS_VARIATION_SELECTOR_FALLBACK;
+                Info *vs = &b->info[b->idx];
+                vs->uprops = (uint16_t)((vs->uprops & ~0x1Fu & 0xFF) | VEGA_CF | UPROPS_VS);
+                vs->glyph_index = nominal(c->s, vs->codepoint, &glyph) ? glyph : 0;
+                next_glyph(b);
+            }
             while (b->idx < end && b->successful && variation_selector(b->info[b->idx].codepoint)) {
                 b->info[b->idx].glyph_index = nominal(c->s, b->info[b->idx].codepoint, &glyph) ? glyph : 0;
                 next_glyph(b);
diff --git a/text/shape.h b/text/shape.h
index 3fe3ff8..690430c 100644
--- a/text/shape.h
+++ b/text/shape.h
@@ -41,6 +41,9 @@
  *                                          medi, fina, isol, rlig x3), u32
  *                                          size, then a GSUB table of just
  *                                          those lookups)
+ *   u32 sequence_count, u32 offset        (variation sequences, cmap format
+ *                                          14: u32 base, u32 selector, u32
+ *                                          glyph; by base, then selector)
  * Offsets are from the section's start. A plan (VEGA_PLAN_BYTES):
  *   u32 script (ISO 15924 as a tag: 'Latn'), u8 direction, u8 native
  *   direction (of its script; 0 when it has none), u8 shaper, u8 flags,
@@ -53,7 +56,7 @@
  * A step, a lookup to run: u16 lookup index, u8 flags, u8 0, u32 mask; or
  * a pause, where the shaper does its part: u16 VEGA_STEP_PAUSE, u8 which
  * (VEGA_PAUSE_...), u8 0, u32 0. */
-enum { VEGA_SHAPING_HEADER = 80, VEGA_PLAN_BYTES = 144, VEGA_STEP_BYTES = 8, VEGA_PLAN_MASKS = 16,
+enum { VEGA_SHAPING_HEADER = 88, VEGA_PLAN_BYTES = 144, VEGA_STEP_BYTES = 8, VEGA_PLAN_MASKS = 16,
        VEGA_PLAN_STAGES = 5 };
 enum { VEGA_SHAPE_LTR = 1, VEGA_SHAPE_RTL = 2 };
 enum { VEGA_SHAPER_DEFAULT, VEGA_SHAPER_ARABIC, VEGA_SHAPER_HEBREW, VEGA_SHAPER_HANGUL, VEGA_SHAPER_INDIC,
@@ -115,6 +118,8 @@ typedef struct {
     uint16_t upem, glyph_count;
     uint32_t cmap_groups, plan_count;
     const unsigned char *cmap, *advances, *plans, *steps, *extents;
+    const unsigned char *sequences; /* variation sequences */
+    uint32_t sequence_count;
     VegaTable gdef, gsub, gpos, kern;
     VegaTable fallback;             /* Arabic fallback shaping's lookups, a GSUB table */
     uint32_t fallback_count;