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.

5 files changed, 119 insertions, 21 deletions

diff --git a/docs/design/004-text.md b/docs/design/004-text.md
index 9e6f968..dd631af 100644
--- a/docs/design/004-text.md
+++ b/docs/design/004-text.md
@@ -90,7 +90,9 @@ Sentence_Break, 동아시아 폭이 F·W·H인 여는·닫는 괄호)와 규칙�
   고른다. 결과는 조회 번호, 마스크, ZWJ/ZWNJ 규칙, 이 깃발들의 목록이다. 문자 지도는 HarfBuzz가 매기는 대로 싣는다. 모든
   코드 포인트를 `hb_font_get_nominal_glyph`로 물어, 이어지는 글리프로 가거나 한 글리프로 가는 묶음으로 적는다. 목록
   (`hb_face_collect_unicodes`)으로 만들면 틀린다. 형식 13 지도는 목록이 잘리고, 기호 지도(3,0)의 라틴과 아랍 문자는 HarfBuzz가
-  사용자 영역으로 옮겨 찾는다. advance, GDEF·GSUB·GPOS와 `kern` 표는 그대로 싣고, 대체 배치를 하는 계획이 있으면 글리프마다 외곽 상자(HarfBuzz의 glyph extents, 16비트 넷)를 싣는다
+  사용자 영역으로 옮겨 찾는다. 이체 선택자 순서(cmap 형식 14)도 HarfBuzz가 주는 글리프로 싣는다(바탕 글자와 선택자마다
+  하나, 기본 순서는 바탕 글자의 글리프). 정규화는 글꼴이 가진 순서를 그 글리프 하나로 바꾸고, 없는 순서는 두 글자를 따로
+  넘기며 선택자를 숨긴다. advance, GDEF·GSUB·GPOS와 `kern` 표는 그대로 싣고, 대체 배치를 하는 계획이 있으면 글리프마다 외곽 상자(HarfBuzz의 glyph extents, 16비트 넷)를 싣는다
   ([text/shape.h](../../text/shape.h), [text/shape-build.c](../../text/shape-build.c)).
 - 실행 중에: [text/shape.c](../../text/shape.c)가 HarfBuzz 10의 절차를 함수 단위로 옮긴다. 유니코드 성질과 자소 묶음,
   글꼴을 보는 정규화(없는 글자는 분해하고 있는 합성은 합치며, 부호는 HarfBuzz의 수정 결합 등급과 아랍 UTR #53, 히브리
@@ -232,7 +234,6 @@ U+180B–180E만 넣고 네 번째 자유 이체 선택자(U+180F)를 빠뜨렸�
 - `kern` 표의 상태 기계(Apple 형식 1), 등급 형식(2, 3), 교차 방향 커닝. 설치된 글꼴의 `kern` 표는 모두 짝 형식(0)이다.
 - AAT 표(morx, kerx, trak).
 - 미얀마 Zawgyi(표준이 아닌 인코딩, 문자 체계 태그 Qaag로만 오는 것).
-- 이체 선택자(cmap 형식 14)는 싣지 않는다. 선택자는 숨기고 앞 글자는 기본 글리프로 둔다.
 
 ### HarfBuzz의 시험 모음
 
@@ -246,8 +247,9 @@ U+180B–180E만 넣고 네 번째 자유 이체 선택자(U+180F)를 빠뜨렸�
 실패다. 적힌 것이 맞게 되면 알린다(`make check-harfbuzz HARFBUZZ_SRC=...`).
 
 처음 돌렸을 때 비교한 5,199건 가운데 1,355건만 같았다. 차이 대부분은 문자 지도였다(위의 형식 13과 기호 지도). 그것을 고치자
-5,011건이 같다. 남은 것은 AAT 글꼴(거부), 이체 선택자, 글리프를 나눠 쓰는 아랍 대체 셰이핑, `kern` 형식 2, Zawgyi, 계획이 없는
-실행 하나다. 설치된 글꼴 213개와 Noto 21개의 무작위 실행도 다시 돌려 차이가 없다.
+5,011건이 같다. 이체 선택자 순서를 싣자 5,014건이 같고 다른 것이 없다. 남은 것은 거부하는 글꼴(AAT, 글리프를 나눠 쓰는
+아랍 대체 셰이핑, `kern` 형식 2, Zawgyi)과 계획이 없는 실행 하나다. 무작위 실행에도 글꼴이 가진 순서와 아무 선택자를
+섞는다. Noto Sans CJK의 한자 이체 순서(14,787개)를 섞은 3만 실행이 HarfBuzz와 같다.
 
 ## 비례폭 글줄
 
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;