DateKeys/internal/pathrule/gen/main.go

// Command gen generates the Unicode and best-fit tables of package pathrule
// (spec §29.5.1) from the data files of Unicode 18.0.0 and WindowsBestFit:
//
//	go run ./internal/pathrule/gen -data .cache
//
// It reads, below the -data directory,
//
//	unicode/18.0.0/UnicodeData.txt
//	unicode/18.0.0/DerivedCoreProperties.txt
//	unicode/18.0.0/CaseFolding.txt
//	unicode/18.0.0/emoji/emoji-variation-sequences.txt
//	bestfit/bestfit<N>.txt, for the 15 code pages of WindowsBestFit
//
// checks the SHA-256 of each against the value pinned below, and writes
// internal/pathrule/tables.go. The files are not in the repository: only the
// generated tables are. Download them from https://www.unicode.org/Public/.
//
// The tables are also described by a canonical text, whose SHA-256 is
// TablesDigest: an implementation in another language generated from the
// same files computes the same digest (see canonical in package pathrule).
// -ts and -dart write the same tables for the other two implementations:
//
//	go run ./internal/pathrule/gen -data .cache -ts ../datekeys-ts/src/lib/dkc/pathrule-tables.ts
//	go run ./internal/pathrule/gen -data .cache -dart ../datekeys-dart/lib/src/pathrule_tables.dart
package main

import (
	"bufio"
	"bytes"
	"crypto/sha256"
	"encoding/hex"
	"flag"
	"fmt"
	"go/format"
	"os"
	"path/filepath"
	"slices"
	"strconv"
	"strings"
)

// UnicodeVersion is the version of Unicode the tables come from (spec
// §29.5.1). It is fixed with capsule format 3.
const UnicodeVersion = "18.0.0"

// source is one data file and the SHA-256 it must have.
type source struct {
	path, sha256 string
}

// The pinned files (spec §29.5.1).
var (
	unicodeData   = source{"unicode/18.0.0/UnicodeData.txt", "0736451de439ae7baf1425136617da495e09ee5afbe6e394374db7009ea08950"}
	derivedCore   = source{"unicode/18.0.0/DerivedCoreProperties.txt", "09c928886a178fcafd93c29e4bd59073a058e5a100b716d425cb563ab50f68c9"}
	caseFolding   = source{"unicode/18.0.0/CaseFolding.txt", "a004797658a457bec4dc11683e39f69249ea3b595b752dbea6721c4c9f587b0d"}
	emojiVariants = source{"unicode/18.0.0/emoji/emoji-variation-sequences.txt", "ff1707564aa1f1b2fcf4ec92d609d4cb26940bc0d4dcf07f5328ad6879e84da3"}
	bestFitFiles  = []source{
		{"bestfit/bestfit874.txt", "663f43ca662e037c4534cb16298b560f29ce29c27b49b3589601ec3d97dd89fd"},
		{"bestfit/bestfit932.txt", "2614cfea35c3c86c41d33198793a84ca44edee3cf0ee0013a61a43fba4ece331"},
		{"bestfit/bestfit936.txt", "e5070a2d6ad26619f5872ddbe64d3381c11620af5adbb04cda0f0abb1a91fdae"},
		{"bestfit/bestfit949.txt", "50e13b60ea8fda66a8223ecc85270e0f182303222244e2345d3d57f3e839d20a"},
		{"bestfit/bestfit950.txt", "cf8c23389a42a226ea707f7ec32c665556d1fc3364db25bd765ce64d54eaee2a"},
		{"bestfit/bestfit1250.txt", "cef9f171e67b09445bcb3f9ffccdc89418250ff825f1bd2d29a92d2074d7a53b"},
		{"bestfit/bestfit1251.txt", "59ec85612ff908d9da0e877893c935941e56b13a2882b4fb9c9599be3d1ce4e7"},
		{"bestfit/bestfit1252.txt", "72ea23c939c5b26fae7aded0207b327e2f3902d7d3c168d7087f5cfc38ee76a9"},
		{"bestfit/bestfit1253.txt", "ea80c442aff7f09b36da6335f85f8e527f51c146beeb9825ec00d1b6ca99a99e"},
		{"bestfit/bestfit1254.txt", "3d02512087634dc493b720992b590277736ffb2d5b0b665d69b6b9727e2c361a"},
		{"bestfit/bestfit1255.txt", "fdd4bdda74f6571d89171b0070ac052cd3714c395dc3d1799bcd5e4a4da6f83a"},
		{"bestfit/bestfit1256.txt", "745c447ada04a838da8bea406c13f446c7453b6371e8c6c7863a632443d56007"},
		{"bestfit/bestfit1257.txt", "b8c5d7f3b8c25c3d5625d44dd3d6ee7a06e652ddf77373d050282c1cb7517366"},
		{"bestfit/bestfit1258.txt", "5d52a9357b7d6b5b5014ed5a51be0ff9809b0c33625793d2a4feaf502e0682f1"},
		{"bestfit/bestfit1361.txt", "7dcda2d5d2cfc5ddf43757d589a0106e020ef0d9b84de47f08e18297ae0fe1ec"},
	}
)

func main() {
	data := flag.String("data", ".cache", "directory with the downloaded data files")
	out := flag.String("go", "internal/pathrule/tables.go", "Go file to write")
	tsOut := flag.String("ts", "", "TypeScript module to write for datekeys-ts; none when empty")
	dartOut := flag.String("dart", "", "Dart library to write for datekeys-dart; none when empty")
	flag.Parse()
	t, err := build(*data)
	if err != nil {
		fmt.Fprintln(os.Stderr, "gen:", err)
		os.Exit(1)
	}
	src, err := t.goSource()
	if err != nil {
		fmt.Fprintln(os.Stderr, "gen:", err)
		os.Exit(1)
	}
	if err := os.WriteFile(*out, src, 0o644); err != nil {
		fmt.Fprintln(os.Stderr, "gen:", err)
		os.Exit(1)
	}
	if *tsOut != "" {
		if err := os.WriteFile(*tsOut, t.tsSource(), 0o644); err != nil {
			fmt.Fprintln(os.Stderr, "gen:", err)
			os.Exit(1)
		}
		fmt.Printf("wrote %s\n", *tsOut)
	}
	if *dartOut != "" {
		if err := os.WriteFile(*dartOut, t.dartSource(), 0o644); err != nil {
			fmt.Fprintln(os.Stderr, "gen:", err)
			os.Exit(1)
		}
		fmt.Printf("wrote %s\n", *dartOut)
	}
	fmt.Printf("wrote %s: %d assigned ranges, %d ignorable ranges, %d ccc, %d decompositions, %d foldings, %d+%d emoji bases, %d best-fit tables; digest %s\n",
		*out, len(t.assigned), len(t.ignorable), len(t.ccc), len(t.decomp), len(t.fold), len(t.vs15), len(t.vs16), len(t.bestFit), t.digest())
}

// tables are the data package pathrule needs, in canonical order.
type tables struct {
	assigned  [][2]rune       // ranges of assigned code points
	ignorable [][2]rune       // ranges of Default_Ignorable_Code_Point
	ccc       map[rune]uint8  // canonical combining class, non-zero only
	decomp    map[rune][]rune // full canonical decomposition, Hangul excluded
	fold      map[rune][]rune // case folding, statuses C and F
	lower     map[rune][]rune // simple lowercase mapping, field 13 of UnicodeData.txt
	vs15      []rune          // bases of an emoji variation sequence with U+FE0E
	vs16      []rune          // bases of an emoji variation sequence with U+FE0F
	bestFit   []bestFitTable  // one per code page
	sources   []source        // the files, for the record
}

type bestFitTable struct {
	name string        // code page, "874"
	to   map[rune]byte // non-ASCII code point -> ASCII byte
}

// read returns the contents of a data file after checking its digest.
func read(dir string, s source) ([]byte, error) {
	b, err := os.ReadFile(filepath.Join(dir, filepath.FromSlash(s.path)))
	if err != nil {
		return nil, err
	}
	sum := sha256.Sum256(b)
	if got := hex.EncodeToString(sum[:]); got != s.sha256 {
		return nil, fmt.Errorf("%s: SHA-256 %s, want %s", s.path, got, s.sha256)
	}
	return b, nil
}

func build(dir string) (*tables, error) {
	t := &tables{ccc: map[rune]uint8{}, decomp: map[rune][]rune{}, fold: map[rune][]rune{}, lower: map[rune][]rune{}}
	t.sources = append([]source{unicodeData, derivedCore, caseFolding, emojiVariants}, bestFitFiles...)

	b, err := read(dir, unicodeData)
	if err != nil {
		return nil, err
	}
	if err := t.parseUnicodeData(b); err != nil {
		return nil, fmt.Errorf("%s: %w", unicodeData.path, err)
	}
	if b, err = read(dir, derivedCore); err != nil {
		return nil, err
	}
	if t.ignorable, err = parseProperty(b, "Default_Ignorable_Code_Point"); err != nil {
		return nil, fmt.Errorf("%s: %w", derivedCore.path, err)
	}
	if b, err = read(dir, caseFolding); err != nil {
		return nil, err
	}
	if err := t.parseCaseFolding(b); err != nil {
		return nil, fmt.Errorf("%s: %w", caseFolding.path, err)
	}
	if b, err = read(dir, emojiVariants); err != nil {
		return nil, err
	}
	if err := t.parseEmojiVariants(b); err != nil {
		return nil, fmt.Errorf("%s: %w", emojiVariants.path, err)
	}
	for _, s := range bestFitFiles {
		if b, err = read(dir, s); err != nil {
			return nil, err
		}
		bt, err := parseBestFit(b)
		if err != nil {
			return nil, fmt.Errorf("%s: %w", s.path, err)
		}
		bt.name = strings.TrimSuffix(strings.TrimPrefix(filepath.Base(s.path), "bestfit"), ".txt")
		t.bestFit = append(t.bestFit, bt)
	}
	return t, nil
}

func hexRune(s string) (rune, error) {
	v, err := strconv.ParseUint(strings.TrimSpace(s), 16, 32)
	if err != nil || v > 0x10FFFF {
		return 0, fmt.Errorf("bad code point %q", s)
	}
	return rune(v), nil
}

func hexRunes(s string) ([]rune, error) {
	var out []rune
	for _, f := range strings.Fields(s) {
		r, err := hexRune(f)
		if err != nil {
			return nil, err
		}
		out = append(out, r)
	}
	return out, nil
}

// lines yields the data lines of a UCD-style file: comments after '#'
// removed, blank lines skipped.
func lines(b []byte, f func(line string) error) error {
	sc := bufio.NewScanner(bytes.NewReader(b))
	sc.Buffer(make([]byte, 1<<16), 1<<20)
	for n := 1; sc.Scan(); n++ {
		line := sc.Text()
		if i := strings.IndexByte(line, '#'); i >= 0 {
			line = line[:i]
		}
		if strings.TrimSpace(line) == "" {
			continue
		}
		if err := f(line); err != nil {
			return fmt.Errorf("line %d: %w", n, err)
		}
	}
	return sc.Err()
}

func (t *tables) parseUnicodeData(b []byte) error {
	canonical := map[rune][]rune{}
	var assigned []rune
	var first rune = -1
	err := lines(b, func(line string) error {
		f := strings.Split(line, ";")
		if len(f) != 15 {
			return fmt.Errorf("%d fields", len(f))
		}
		cp, err := hexRune(f[0])
		if err != nil {
			return err
		}
		switch name := f[1]; {
		case strings.HasSuffix(name, ", First>"):
			first = cp
			return nil
		case strings.HasSuffix(name, ", Last>"):
			if first < 0 {
				return fmt.Errorf("range end %04X without start", cp)
			}
			for r := first; r <= cp; r++ {
				assigned = append(assigned, r)
			}
			first = -1
		default:
			assigned = append(assigned, cp)
		}
		if c, err := strconv.ParseUint(f[3], 10, 8); err != nil {
			return fmt.Errorf("ccc %q", f[3])
		} else if c != 0 {
			t.ccc[cp] = uint8(c)
		}
		if d := f[5]; d != "" && !strings.HasPrefix(d, "<") {
			m, err := hexRunes(d)
			if err != nil {
				return err
			}
			canonical[cp] = m
		}
		if l := f[13]; l != "" {
			r, err := hexRune(l)
			if err != nil {
				return err
			}
			t.lower[cp] = []rune{r}
		}
		return nil
	})
	if err != nil {
		return err
	}
	t.assigned = ranges(assigned)
	var expand func(r rune) []rune
	expand = func(r rune) []rune {
		m, ok := canonical[r]
		if !ok {
			return []rune{r}
		}
		var out []rune
		for _, x := range m {
			out = append(out, expand(x)...)
		}
		return out
	}
	for r := range canonical {
		t.decomp[r] = expand(r)
	}
	return nil
}

// ranges turns a set of code points into sorted, merged, inclusive ranges.
func ranges(cps []rune) [][2]rune {
	slices.Sort(cps)
	cps = slices.Compact(cps)
	var out [][2]rune
	for _, r := range cps {
		if n := len(out); n > 0 && out[n-1][1]+1 == r {
			out[n-1][1] = r
			continue
		}
		out = append(out, [2]rune{r, r})
	}
	return out
}

func parseProperty(b []byte, name string) ([][2]rune, error) {
	var cps []rune
	err := lines(b, func(line string) error {
		f := strings.SplitN(line, ";", 2)
		if len(f) != 2 || strings.TrimSpace(f[1]) != name {
			return nil
		}
		lo, hi, ok := strings.Cut(strings.TrimSpace(f[0]), "..")
		a, err := hexRune(lo)
		if err != nil {
			return err
		}
		z := a
		if ok {
			if z, err = hexRune(hi); err != nil {
				return err
			}
		}
		for r := a; r <= z; r++ {
			cps = append(cps, r)
		}
		return nil
	})
	if len(cps) == 0 && err == nil {
		err = fmt.Errorf("no %s entries", name)
	}
	return ranges(cps), err
}

func (t *tables) parseCaseFolding(b []byte) error {
	return lines(b, func(line string) error {
		f := strings.Split(line, ";")
		if len(f) < 3 {
			return fmt.Errorf("%d fields", len(f))
		}
		switch strings.TrimSpace(f[1]) {
		case "C", "F":
		default:
			return nil
		}
		cp, err := hexRune(f[0])
		if err != nil {
			return err
		}
		m, err := hexRunes(f[2])
		if err != nil {
			return err
		}
		if _, dup := t.fold[cp]; dup {
			return fmt.Errorf("two C or F foldings for %04X", cp)
		}
		t.fold[cp] = m
		return nil
	})
}

func (t *tables) parseEmojiVariants(b []byte) error {
	err := lines(b, func(line string) error {
		f := strings.SplitN(line, ";", 2)
		seq, err := hexRunes(f[0])
		if err != nil {
			return err
		}
		if len(seq) != 2 {
			return fmt.Errorf("sequence of %d code points", len(seq))
		}
		switch seq[1] {
		case 0xFE0E:
			t.vs15 = append(t.vs15, seq[0])
		case 0xFE0F:
			t.vs16 = append(t.vs16, seq[0])
		default:
			return fmt.Errorf("selector %04X", seq[1])
		}
		return nil
	})
	slices.Sort(t.vs15)
	slices.Sort(t.vs16)
	t.vs15, t.vs16 = slices.Compact(t.vs15), slices.Compact(t.vs16)
	return err
}

// parseBestFit keeps, from the WCTABLE section, the code points of 0x80 and
// above that the code page maps to a single ASCII byte (spec §29.5, R6c).
func parseBestFit(b []byte) (bestFitTable, error) {
	bt := bestFitTable{to: map[rune]byte{}}
	sc := bufio.NewScanner(bytes.NewReader(b))
	in, seen := false, false
	for n := 1; sc.Scan(); n++ {
		line := sc.Text()
		if i := strings.IndexByte(line, ';'); i >= 0 {
			line = line[:i]
		}
		f := strings.Fields(line)
		if len(f) == 0 {
			continue
		}
		if !strings.HasPrefix(f[0], "0x") {
			in = f[0] == "WCTABLE"
			seen = seen || in
			continue
		}
		if !in {
			continue
		}
		if len(f) < 2 {
			return bt, fmt.Errorf("line %d: %q", n, line)
		}
		u, err1 := strconv.ParseUint(f[0][2:], 16, 32)
		v, err2 := strconv.ParseUint(strings.TrimPrefix(f[1], "0x"), 16, 32)
		if err1 != nil || err2 != nil || u > 0xFFFF {
			return bt, fmt.Errorf("line %d: %q", n, line)
		}
		if u >= 0x80 && v <= 0x7F {
			bt.to[rune(u)] = byte(v)
		}
	}
	if !seen {
		return bt, fmt.Errorf("no WCTABLE section")
	}
	return bt, sc.Err()
}

func sortedKeys[V any](m map[rune]V) []rune {
	keys := make([]rune, 0, len(m))
	for k := range m {
		keys = append(keys, k)
	}
	slices.Sort(keys)
	return keys
}

// canonical is the text whose SHA-256 is TablesDigest. Package pathrule
// rebuilds it from the generated tables, and so does any other
// implementation, line by line: every value in upper-case hexadecimal of at
// least four digits, except the combining class and the code page, in
// decimal.
func (t *tables) canonical() string {
	var b strings.Builder
	fmt.Fprintf(&b, "unicode %s\n", UnicodeVersion)
	for _, r := range t.assigned {
		fmt.Fprintf(&b, "assigned %04X %04X\n", r[0], r[1])
	}
	for _, r := range t.ignorable {
		fmt.Fprintf(&b, "ignorable %04X %04X\n", r[0], r[1])
	}
	for _, k := range sortedKeys(t.ccc) {
		fmt.Fprintf(&b, "ccc %04X %d\n", k, t.ccc[k])
	}
	for _, k := range sortedKeys(t.decomp) {
		fmt.Fprintf(&b, "decomp %04X%s\n", k, hexList(t.decomp[k]))
	}
	for _, k := range sortedKeys(t.fold) {
		fmt.Fprintf(&b, "fold %04X%s\n", k, hexList(t.fold[k]))
	}
	for _, k := range sortedKeys(t.lower) {
		fmt.Fprintf(&b, "lower %04X%s\n", k, hexList(t.lower[k]))
	}
	for _, r := range t.vs15 {
		fmt.Fprintf(&b, "vs15 %04X\n", r)
	}
	for _, r := range t.vs16 {
		fmt.Fprintf(&b, "vs16 %04X\n", r)
	}
	for _, bt := range t.bestFit {
		for _, k := range sortedKeys(bt.to) {
			fmt.Fprintf(&b, "bestfit %s %04X %02X\n", bt.name, k, bt.to[k])
		}
	}
	return b.String()
}

func hexList(rs []rune) string {
	var b strings.Builder
	for _, r := range rs {
		fmt.Fprintf(&b, " %04X", r)
	}
	return b.String()
}

func (t *tables) digest() string {
	sum := sha256.Sum256([]byte(t.canonical()))
	return hex.EncodeToString(sum[:])
}

// goSource renders tables.go.
func (t *tables) goSource() ([]byte, error) {
	var b bytes.Buffer
	w := func(format string, args ...any) { fmt.Fprintf(&b, format, args...) }
	w("// Code generated by internal/pathrule/gen from Unicode %s and WindowsBestFit. DO NOT EDIT.\n\n", UnicodeVersion)
	w("package pathrule\n\n")
	w("// UnicodeVersion is the version of Unicode of these tables, fixed with\n// capsule format 3 (spec §29.5.1).\nconst UnicodeVersion = %q\n\n", UnicodeVersion)
	w("// TablesDigest is the SHA-256 of the canonical text of these tables (see\n// Canonical). Another implementation generated from the same files has it too.\nconst TablesDigest = %q\n\n", t.digest())
	w("// Sources are the data files of the tables and their SHA-256 (spec §29.5.1).\nvar Sources = []struct{ Path, SHA256 string }{\n")
	for _, s := range t.sources {
		w("\t{%q, %q},\n", s.path, s.sha256)
	}
	w("}\n\n")

	pairs := func(name, doc string, rs [][2]rune) {
		w("// %s\nvar %s = []rune{", doc, name)
		for i, r := range rs {
			if i%6 == 0 {
				w("\n\t")
			}
			w("0x%04X, 0x%04X, ", r[0], r[1])
		}
		w("\n}\n\n")
	}
	pairs("assignedRanges", "assignedRanges are the assigned code points, as inclusive ranges: lo, hi, ...", t.assigned)
	pairs("ignorableRanges", "ignorableRanges are Default_Ignorable_Code_Point, as inclusive ranges.", t.ignorable)

	w("// cccTable holds each code point with a non-zero canonical combining class,\n// as code point << 8 | class, sorted.\nvar cccTable = []uint32{")
	for i, k := range sortedKeys(t.ccc) {
		if i%8 == 0 {
			w("\n\t")
		}
		w("0x%06X, ", uint32(k)<<8|uint32(t.ccc[k]))
	}
	w("\n}\n\n")

	mapping := func(name, doc string, m map[rune][]rune) {
		keys := sortedKeys(m)
		w("// %s\nvar %s = mapping{\n\tkeys: []rune{", doc, name)
		for i, k := range keys {
			if i%10 == 0 {
				w("\n\t\t")
			}
			w("0x%04X, ", k)
		}
		w("\n\t},\n\tstart: []uint16{")
		n := 0
		for i, k := range keys {
			if i%12 == 0 {
				w("\n\t\t")
			}
			w("%d, ", n)
			n += len(m[k])
		}
		w("%d,\n\t},\n\tdata: []rune{", n)
		i := 0
		for _, k := range keys {
			for _, r := range m[k] {
				if i%10 == 0 {
					w("\n\t\t")
				}
				w("0x%04X, ", r)
				i++
			}
		}
		w("\n\t},\n}\n\n")
	}
	mapping("decompositions", "decompositions is the full canonical decomposition of each code point that has\n// one, Hangul syllables excepted.", t.decomp)
	mapping("foldings", "foldings is the case folding of CaseFolding.txt, statuses C and F.", t.fold)
	mapping("lowercases", "lowercases is the simple lowercase mapping of UnicodeData.txt, field 13.", t.lower)

	set := func(name, doc string, rs []rune) {
		w("// %s\nvar %s = []rune{", doc, name)
		for i, r := range rs {
			if i%10 == 0 {
				w("\n\t")
			}
			w("0x%04X, ", r)
		}
		w("\n}\n\n")
	}
	set("vs15Bases", "vs15Bases are the characters of an emoji variation sequence with U+FE0E.", t.vs15)
	set("vs16Bases", "vs16Bases are the characters of an emoji variation sequence with U+FE0F.", t.vs16)

	w("// bestFitTables are, for each code page of WindowsBestFit, the code points\n// of U+0080 and above that it maps to a single ASCII byte.\nvar bestFitTables = []bestFitTable{\n")
	for _, bt := range t.bestFit {
		keys := sortedKeys(bt.to)
		w("\t{\n\t\tname: %q,\n\t\tfrom: []rune{", bt.name)
		for i, k := range keys {
			if i%10 == 0 {
				w("\n\t\t\t")
			}
			w("0x%04X, ", k)
		}
		w("\n\t\t},\n\t\tto: []byte{")
		for i, k := range keys {
			if i%16 == 0 {
				w("\n\t\t\t")
			}
			w("0x%02X, ", bt.to[k])
		}
		w("\n\t\t},\n\t},\n")
	}
	w("}\n")
	return format.Source(b.Bytes())
}