Debian Codegraph @

internal/gen/gentables/main.go

raw
1 // Copyright 2023 Charlie Vieth. All rights reserved.
2 // Use of this source code is governed by the MIT license.
3
4 // gen generates the Unicode lookup tables used by strcase. The tables must
5 // be regenerated if this code is changed (`go generate`).
6 package main
7
8 import (
9 "bytes"
10 "cmp"
11 "crypto/sha256"
12 "encoding/binary"
13 "encoding/hex"
14 "encoding/json"
15 "flag"
16 "fmt"
17 "go/format"
18 "io/fs"
19 "log"
20 "math"
21 "os"
22 "os/exec"
23 "os/signal"
24 "path/filepath"
25 "runtime"
26 "runtime/pprof"
27 "slices"
28 "sort"
29 "strconv"
30 "strings"
31 "sync"
32 "sync/atomic"
33 "time"
34 "unicode"
35
36 "github.com/schollz/progressbar/v3"
37 "golang.org/x/term"
38 "golang.org/x/text/unicode/rangetable"
39
40 "github.com/charlievieth/strcase/internal/gen/gen"
41 "github.com/charlievieth/strcase/internal/gen/ucd"
42 "github.com/charlievieth/strcase/internal/gen/util"
43 )
44
45 func init() {
46 initLogs()
47
48 // If $GOMAXPROCS isn't set, use the full capacity of the machine.
49 // For small machines, use at least 4 threads.
50 if os.Getenv("GOMAXPROCS") == "" {
51 n := runtime.NumCPU()
52 if n < 4 {
53 n = 4
54 }
55 runtime.GOMAXPROCS(n)
56 }
57 }
58
59 func initLogs() {
60 log.SetPrefix("")
61 log.SetFlags(log.Lshortfile)
62 log.SetOutput(os.Stdout) // use stdout instead of stderr
63 }
64
65 // WARN: we need to include 'İ' (0x0130) and 'ı' (0x0131) in _FoldMap because
66 // we don't want to fallback to using toUpperLower() since we don't accept the
67 // upper/lower-case variants of these runes (breaks simple folding semantics).
68 //
69 // We should remove these runes and any other runes in _FoldMap from _UpperLower
70 // and maybe remove 'İ' and 'ı' from _FoldMap as well.
71 //
72 // TODO: remove İ (0x0130) from _UpperLower and fix tests
73
74 // TODO: consider renaming the generated tables
75 const (
76 MaxChar = 0x10FFFF
77 caseFoldShift = 19
78 caseFoldSize = 8192
79 foldMapShift = 24
80 foldMapSize = 256
81 upperLowerTableSize = 8192
82 upperLowerTableShift = 19
83 )
84
85 const (
86 GenCookieKey = "b3d53e54921be5a951563a7e77bfcb1a"
87 GenCookieValue = "c1bbb5805a8c389e0dd50234d5c38cce"
88 )
89
90 type foldPair struct {
91 From uint32
92 To uint32
93 }
94
95 var (
96 categories *unicode.RangeTable
97 caseFolds []foldPair
98 caseRanges []unicode.CaseRange // used by toLower and toUpper
99 caseOrbit []foldPair // used by simpleFold
100 asciiFold [unicode.MaxASCII + 1]uint16
101 )
102
103 var (
104 chars = make([]Char, MaxChar+1)
105 scripts = make(map[string][]rune)
106 props = make(map[string][]rune) // a property looks like a script; can share the format
107 )
108
109 // TODO: move
110 func loadCaseFolds() {
111 ucd.Parse(gen.OpenUCDFile("CaseFolding.txt"), func(p *ucd.Parser) {
112 kind := p.String(1)
113 if kind != "C" && kind != "S" {
114 // Only care about 'common' and 'simple' foldings.
115 return
116 }
117 p1 := p.Rune(0)
118 p2 := p.Rune(2)
119 caseFolds = append(caseFolds, foldPair{uint32(p1), uint32(p2)})
120 chars[p1].foldCase = p2
121 })
122 slices.SortFunc(caseFolds, func(a, b foldPair) int {
123 return cmp.Compare(a.From, b.From)
124 })
125 }
126
127 var buildTags = map[string]struct{ version, buildTags, filename string }{
128 "13.0.0": {"13.0.0", "go1.16,!go1.21", "tables_go116.go"},
129 "15.0.0": {"15.0.0", "go1.21", "tables_go121.go"},
130 }
131
132 // tablesFileName is the names of the file to generate and is based off
133 // of the Go version this program is ran with.
134 //
135 // NB: this must be called after command line flags are parsed
136 func tablesFileName(dirname string) string {
137 // gen.UnicodeVersion is set by the "-unicode" flag
138 if name := buildTags[gen.UnicodeVersion()].filename; name != "" {
139 return filepath.Join(dirname, name)
140 }
141 log.Panicf("unsupported Unicode version %q this script might need "+
142 "to be updated", gen.UnicodeVersion())
143 panic("unreachable")
144 }
145
146 type span struct {
147 Start, End int64
148 }
149
150 func generateSpans(start, end, delta int64) []span {
151 maxEnd := end
152 var spans []span
153 for i := start; i <= end; i += delta {
154 end := i + delta
155 if end >= maxEnd {
156 end = maxEnd
157 }
158 spans = append(spans, span{Start: i, End: end})
159 }
160
161 // Reverse spans since larger values are more likely to be better seeds.
162 // We previously randomly shuffled the spans, but led to non-deterministic
163 // behavior when more than one seed was ideal.
164 for i := len(spans)/2 - 1; i >= 0; i-- {
165 opp := len(spans) - 1 - i
166 spans[i], spans[opp] = spans[opp], spans[i]
167 }
168
169 return spans
170 }
171
172 func hash(seed, key, shift uint32) uint32 {
173 m := seed * key
174 return m >> shift
175 }
176
177 func shiftHash(seed, key, shift uint32) uint32 {
178 key |= key << 24 // fill top bits not occupied by unicode.MaxRune
179 m := seed * key
180 return m >> shift
181 }
182
183 type HashConfig struct {
184 TableName string
185 TableSize int
186 HashShift uint32 // TODO: this can be calculated from TableSize
187 // TODO: name is confusing with HashShift
188 ShiftHash bool // Use shiftHash instead of hash
189
190 // Use the first valid hash value instead of performing an exhaustive
191 // search to find the "best" hash seed. The seed is not deterministic
192 // and this is only meant for testing since it is much much faster.
193 FirstValidHash bool
194 }
195
196 var hashSeedCache = map[string]uint32{}
197
198 func cacheKey(inputs []uint32) string {
199 if !slices.IsSorted(inputs) {
200 slices.Sort(inputs)
201 }
202 b := make([]byte, len(inputs)*4)
203 for i, u := range inputs {
204 binary.LittleEndian.PutUint32(b[i*4:], u)
205 }
206 sum := sha256.Sum256(b)
207 return hex.EncodeToString(sum[:])
208 }
209
210 // TODO:
211 // - Return the first working hash value.
212 // - Find a better algorithm.
213 //
214 // GenerateHashValues performs a brute-force search for the best possible
215 // multiplicative hash seed for inputs. All uint32 values are checked.
216 func (conf *HashConfig) GenerateHashValues(inputs []uint32) (hashSeed uint32) {
217 const delta = 512 * 1024
218
219 if *useCachedSeeds {
220 if seed, ok := tableInfo.TableHashes[conf.TableName]; ok {
221 log.Printf("WARN: using cached seed %d for table: %s", seed, conf.TableName)
222 return seed
223 }
224 }
225
226 if seed, ok := hashSeedCache[cacheKey(inputs)]; ok {
227 log.Printf("Using previously computed seed (0x%04X) for the %s table",
228 seed, conf.TableName)
229 tableInfo.TableHashes[conf.TableName] = seed
230 return seed
231 }
232
233 if slices.IndexFunc(inputs, func(u uint32) bool { return u != 0 }) < 0 {
234 log.Panicf("Input is all zeros for table: %s", conf.TableName)
235 }
236
237 log.Printf("Generating values for the %s table (this may take a long time)...\n",
238 conf.TableName)
239
240 // This can take awhile so use a progress bar.
241 var bar *progressbar.ProgressBar
242 if term.IsTerminal(int(os.Stdout.Fd())) {
243 bar = progressbar.Default(math.MaxUint32)
244 } else {
245 bar = progressbar.DefaultSilent(math.MaxUint32)
246 }
247 start := time.Now()
248
249 // TODO: set GOMAXPROCS to NumCPU ??
250 numProcs := runtime.GOMAXPROCS(0)
251
252 // When FirstValidHash we exit before consuming all spans.
253 done := make(chan struct{})
254 defer close(done)
255
256 ch := make(chan *span, numProcs*2)
257 go func() {
258 spans := generateSpans(1, math.MaxUint32, delta)
259 for i := range spans {
260 select {
261 case ch <- &spans[i]:
262 case <-done:
263 return
264 }
265 }
266 close(ch)
267 }()
268
269 var (
270 bestIndex = int64(math.MaxInt64)
271 bestSeed uint32
272 foundSeed atomic.Bool
273 mu sync.Mutex
274 wg sync.WaitGroup
275 )
276 if seed := tableInfo.TableHashes[conf.TableName]; seed != 0 {
277 bestSeed = seed
278 }
279 for i := 0; i < numProcs; i++ {
280 wg.Add(1)
281 go func(inputs []uint32) {
282 defer wg.Done()
283 seen := make([]bool, conf.TableSize)
284 for sp := range ch {
285 if foundSeed.Load() {
286 return
287 }
288 best := atomic.LoadInt64(&bestIndex)
289 Loop:
290 for i := sp.Start; i <= sp.End && best >= int64(len(inputs)); i++ {
291 for i := range seen {
292 seen[i] = false // TODO: zero
293 }
294 // TODO: load more often
295 if i%8192 == 0 {
296 best = atomic.LoadInt64(&bestIndex)
297 }
298 var maxIdx int64
299 shift := conf.HashShift
300 seed := uint32(i)
301 useShiftHash := conf.ShiftHash
302 // TODO: is there anyway we can optimize this?
303 for _, x := range inputs {
304 var u int64
305 if useShiftHash {
306 u = int64(shiftHash(seed, x, shift))
307 } else {
308 u = int64(hash(seed, x, shift))
309 }
310 if u > best || seen[u] {
311 continue Loop
312 }
313 seen[u] = true
314 if u > maxIdx {
315 maxIdx = u
316 }
317 }
318 best = atomic.LoadInt64(&bestIndex)
319 if maxIdx < best {
320 // Use mutex to simplify updating both values
321 mu.Lock()
322 best = atomic.LoadInt64(&bestIndex) // re-check
323 if maxIdx < best {
324 atomic.StoreInt64(&bestIndex, maxIdx)
325 atomic.StoreUint32(&bestSeed, seed)
326
327 // Stop at the first valid has
328 if conf.FirstValidHash && foundSeed.CompareAndSwap(false, true) {
329 log.Println("WARN: -first-valid-hash flag provided: stopping early")
330 mu.Unlock()
331 return
332 }
333 }
334 mu.Unlock()
335 }
336 }
337 // TODO: figure out is we need to use `1 + sp.End - sp.Start`
338 if err := bar.Add64(sp.End - sp.Start); err != nil {
339 max := bar.GetMax64()
340 log.Panicf("error updating progress bar: %v: max: %d delta: %d",
341 err, max, 1+sp.End-sp.Start)
342 }
343 }
344 }(inputs)
345 }
346 wg.Wait()
347 bar.Close()
348
349 // TODO: we can probably just check bestSeed
350 if bestIndex == math.MaxInt64 || bestSeed == 0 {
351 log.Panicf("Failed to generate hash values for %s table: max_index: %d seed: %d",
352 conf.TableName, bestIndex, bestSeed)
353 }
354 if bestIndex <= int64(conf.TableSize/2) {
355 // Error if the algorithm found a table size that is a smaller power of 2
356 log.Panicf("The hash table size can be reduced to %d or less. The best index is: %d.",
357 conf.TableSize/2, bestIndex)
358 }
359
360 log.Printf("Successfully generated %s values in: %s\n"+
361 " max_index: %d\n"+
362 " seed: %d\n",
363 conf.TableName, time.Since(start), bestIndex, bestSeed)
364 // log.Printf("Successfully generated %s values in: %s", conf.TableName, time.Since(start))
365 // log.Printf(" max_index: %d", bestIndex)
366 // log.Printf(" seed: %d", bestSeed)
367
368 hashSeedCache[cacheKey(inputs)] = bestSeed // Cache result
369 tableInfo.TableHashes[conf.TableName] = bestSeed
370 return bestSeed
371 }
372
373 const (
374 CaseUpper = 1 << iota
375 CaseLower
376 CaseTitle
377 CaseNone = 0 // must be zero
378 CaseMissing = -1 // character not present; not a valid case state
379 )
380
381 type caseState struct {
382 point rune
383 _case int
384 deltaToUpper rune
385 deltaToLower rune
386 deltaToTitle rune
387 }
388
389 // Is d a continuation of the state of c?
390 func (c *caseState) adjacent(d *caseState) bool {
391 if d.point < c.point {
392 c, d = d, c
393 }
394 switch {
395 case d.point != c.point+1: // code points not adjacent (shouldn't happen)
396 return false
397 case d._case != c._case: // different cases
398 return c.upperLowerAdjacent(d)
399 case c._case == CaseNone:
400 return false
401 case c._case == CaseMissing:
402 return false
403 case d.deltaToUpper != c.deltaToUpper:
404 return false
405 case d.deltaToLower != c.deltaToLower:
406 return false
407 case d.deltaToTitle != c.deltaToTitle:
408 return false
409 }
410 return true
411 }
412
413 // Is d the same as c, but opposite in upper/lower case? this would make it
414 // an element of an UpperLower sequence.
415 func (c *caseState) upperLowerAdjacent(d *caseState) bool {
416 // check they're a matched case pair. we know they have adjacent values
417 switch {
418 case c._case == CaseUpper && d._case != CaseLower:
419 return false
420 case c._case == CaseLower && d._case != CaseUpper:
421 return false
422 }
423 // matched pair (at least in upper/lower). make the order Upper Lower
424 if c._case == CaseLower {
425 c, d = d, c
426 }
427 // for an Upper Lower sequence the deltas have to be in order
428 // c: 0 1 0
429 // d: -1 0 -1
430 switch {
431 case c.deltaToUpper != 0:
432 return false
433 case c.deltaToLower != 1:
434 return false
435 case c.deltaToTitle != 0:
436 return false
437 case d.deltaToUpper != -1:
438 return false
439 case d.deltaToLower != 0:
440 return false
441 case d.deltaToTitle != -1:
442 return false
443 }
444 return true
445 }
446
447 // Does this character start an UpperLower sequence?
448 func (c *caseState) isUpperLower() bool {
449 // for an Upper Lower sequence the deltas have to be in order
450 // c: 0 1 0
451 switch {
452 case c.deltaToUpper != 0:
453 return false
454 case c.deltaToLower != 1:
455 return false
456 case c.deltaToTitle != 0:
457 return false
458 }
459 return true
460 }
461
462 // Does this character start a LowerUpper sequence?
463 func (c *caseState) isLowerUpper() bool {
464 // for an Upper Lower sequence the deltas have to be in order
465 // c: -1 0 -1
466 switch {
467 case c.deltaToUpper != -1:
468 return false
469 case c.deltaToLower != 0:
470 return false
471 case c.deltaToTitle != -1:
472 return false
473 }
474 return true
475 }
476
477 func getCaseState(i rune) (c *caseState) {
478 c = &caseState{point: i, _case: CaseNone}
479 ch := &chars[i]
480 switch ch.codePoint {
481 case 0:
482 c._case = CaseMissing // Will get NUL wrong but that doesn't matter
483 return
484 case ch.upperCase:
485 c._case = CaseUpper
486 case ch.lowerCase:
487 c._case = CaseLower
488 case ch.titleCase:
489 c._case = CaseTitle
490 }
491 // Some things such as roman numeral U+2161 don't describe themselves
492 // as upper case, but have a lower case. Second-guess them.
493 if c._case == CaseNone && ch.lowerCase != 0 {
494 c._case = CaseUpper
495 }
496 // Same in the other direction.
497 if c._case == CaseNone && ch.upperCase != 0 {
498 c._case = CaseLower
499 }
500
501 if ch.upperCase != 0 {
502 c.deltaToUpper = ch.upperCase - i
503 }
504 if ch.lowerCase != 0 {
505 c.deltaToLower = ch.lowerCase - i
506 }
507 if ch.titleCase != 0 {
508 c.deltaToTitle = ch.titleCase - i
509 }
510 return
511 }
512
513 // TODO: we need to do this since we can't use the [unicode] package due to
514 // a version mismatch between the Unicode version we're generating for and
515 // Unicode version of Go version being used to generate this.
516 //
517 // TODO: fixup the above comment.
518 func generateCaseRanges() []unicode.CaseRange {
519 if gen.UnicodeVersion() == unicode.Version {
520 return unicode.CaseRanges
521 }
522 // The requested Unicode version does not match the stdlibs
523 var (
524 cases []unicode.CaseRange
525 startState *caseState // the start of a run; nil for not active
526 prevState = &caseState{} // the state of the previous character
527 )
528 for i := range chars {
529 state := getCaseState(rune(i))
530 if state.adjacent(prevState) {
531 prevState = state
532 continue
533 }
534 // end of run (possibly)
535 if c, ok := getCaseRange(startState, prevState); ok {
536 cases = append(cases, c)
537 }
538 // printCaseRange(startState, prevState)
539 startState = nil
540 if state._case != CaseMissing && state._case != CaseNone {
541 startState = state
542 }
543 prevState = state
544 }
545
546 return cases
547 }
548
549 // Modified version of golang.org/x/text/internal/export/unicode.printCaseRange
550 func getCaseRange(lo, hi *caseState) (unicode.CaseRange, bool) {
551 if lo == nil {
552 return unicode.CaseRange{}, false
553 }
554 if lo.deltaToUpper == 0 && lo.deltaToLower == 0 && lo.deltaToTitle == 0 {
555 // character represents itself in all cases - no need to mention it
556 return unicode.CaseRange{}, false
557 }
558 switch {
559 case hi.point > lo.point && lo.isUpperLower():
560 c := unicode.CaseRange{
561 Lo: uint32(lo.point),
562 Hi: uint32(hi.point),
563 Delta: [unicode.MaxCase]rune{
564 unicode.UpperLower,
565 unicode.UpperLower,
566 unicode.UpperLower,
567 },
568 }
569 return c, true
570 case hi.point > lo.point && lo.isLowerUpper():
571 log.Panicf("LowerUpper sequence: should not happen: %U. "+
572 "If it's real, need to fix To()", lo.point)
573 default:
574 c := unicode.CaseRange{
575 Lo: uint32(lo.point),
576 Hi: uint32(hi.point),
577 Delta: [unicode.MaxCase]rune{
578 lo.deltaToUpper,
579 lo.deltaToLower,
580 lo.deltaToTitle,
581 },
582 }
583 return c, true
584 }
585 return unicode.CaseRange{}, false
586 }
587
588 // simpleFold is the same as unicode.SimpleFold but uses the version of Unicode
589 // we loaded.
590 func simpleFold(r rune) rune {
591 if r < 0 || r > unicode.MaxRune {
592 return r
593 }
594
595 if int(r) < len(asciiFold) {
596 return rune(asciiFold[r])
597 }
598
599 // Consult caseOrbit table for special cases.
600 lo := 0
601 hi := len(caseOrbit)
602 for lo < hi {
603 m := lo + (hi-lo)/2
604 if rune(caseOrbit[m].From) < r {
605 lo = m + 1
606 } else {
607 hi = m
608 }
609 }
610 if lo < len(caseOrbit) && rune(caseOrbit[lo].From) == r {
611 return rune(caseOrbit[lo].To)
612 }
613
614 // No folding specified. This is a one- or two-element
615 // equivalence class containing rune and ToLower(rune)
616 // and ToUpper(rune) if they are different from rune.
617 if l := toLower(r); l != r {
618 return l
619 }
620 return toUpper(r)
621 }
622
623 // to maps the rune using the specified case mapping.
624 // It additionally reports whether caseRange contained a mapping for r.
625 func to(_case int, r rune, caseRange []unicode.CaseRange) (mappedRune rune) {
626 if len(caseRange) == 0 {
627 panic("empty caseRange")
628 }
629 if _case < 0 || unicode.MaxCase <= _case {
630 return unicode.ReplacementChar // as reasonable an error as any
631 }
632 // binary search over ranges
633 lo := 0
634 hi := len(caseRange)
635 for lo < hi {
636 m := lo + (hi-lo)/2
637 cr := caseRange[m]
638 if rune(cr.Lo) <= r && r <= rune(cr.Hi) {
639 delta := cr.Delta[_case]
640 if delta > unicode.MaxRune {
641 // In an Upper-Lower sequence, which always starts with
642 // an UpperCase letter, the real deltas always look like:
643 // {0, 1, 0} UpperCase (Lower is next)
644 // {-1, 0, -1} LowerCase (Upper, Title are previous)
645 // The characters at even offsets from the beginning of the
646 // sequence are upper case; the ones at odd offsets are lower.
647 // The correct mapping can be done by clearing or setting the low
648 // bit in the sequence offset.
649 // The constants UpperCase and TitleCase are even while LowerCase
650 // is odd so we take the low bit from _case.
651 return rune(cr.Lo) + ((r-rune(cr.Lo))&^1 | rune(_case&1))
652 }
653 return r + delta
654 }
655 if r < rune(cr.Lo) {
656 hi = m
657 } else {
658 lo = m + 1
659 }
660 }
661 return r
662 }
663
664 // toUpper is the same as unicode.ToUpper but uses the Unicode table we loaded.
665 func toUpper(r rune) rune {
666 if r <= unicode.MaxASCII {
667 if 'a' <= r && r <= 'z' {
668 r -= 'a' - 'A'
669 }
670 return r
671 }
672 return to(unicode.UpperCase, r, caseRanges)
673 }
674
675 // toLower is the same as unicode.ToLower but uses the Unicode table we loaded.
676 func toLower(r rune) rune {
677 if r <= unicode.MaxASCII {
678 if 'A' <= r && r <= 'Z' {
679 r += 'a' - 'A'
680 }
681 return r
682 }
683 return to(unicode.LowerCase, r, caseRanges)
684 }
685
686 func folds(sr rune) []rune {
687 r := simpleFold(sr)
688 runes := make([]rune, 1, 2)
689 runes[0] = sr
690 for r != sr {
691 runes = append(runes, r)
692 r = simpleFold(r)
693 }
694 return runes
695 }
696
697 func genCaseFolds(w *bytes.Buffer, firstValidHash bool) {
698 folds := caseFolds
699 inputs := make([]uint32, len(folds))
700 for i, p := range folds {
701 inputs[i] = p.From
702 }
703
704 conf := HashConfig{
705 TableName: "CaseFolds",
706 TableSize: caseFoldSize,
707 HashShift: caseFoldShift,
708 FirstValidHash: firstValidHash,
709 }
710 seed := conf.GenerateHashValues(inputs)
711
712 // TODO: probably don't need this
713 pairs := make([]foldPair, len(folds))
714 copy(pairs, folds)
715 slices.SortFunc(pairs, func(a, b foldPair) int {
716 return cmp.Compare(a.From, b.From)
717 })
718
719 hashes := make([]foldPair, 0, len(pairs))
720 for i, p := range pairs {
721 hashes = append(hashes, foldPair{
722 From: hash(p.From, seed, caseFoldShift),
723 To: uint32(i),
724 })
725 }
726 slices.SortFunc(hashes, func(a, b foldPair) int {
727 return cmp.Compare(a.From, b.From)
728 })
729
730 fmt.Fprint(w, "\n")
731 fmt.Fprintf(w, "const _CaseFoldsSeed = 0x%04X\n", seed)
732 fmt.Fprintf(w, "const _CaseFoldsShift = %d\n", caseFoldShift)
733 fmt.Fprint(w, "\n")
734 fmt.Fprintln(w, "// _CaseFolds stores all Unicode simple case-folds.")
735 fmt.Fprintf(w, "var _CaseFolds = [%d]foldPair{\n", caseFoldSize)
736 for _, h := range hashes {
737 p := pairs[h.To]
738 fmt.Fprintf(w, "\t%d: {0x%04X, 0x%04X}, // %q => %q\n", h.From, p.From, p.To, p.From, p.To)
739 }
740 fmt.Fprint(w, "}\n\n")
741 }
742
743 func dedupe(r []rune) []rune {
744 if len(r) < 2 {
745 return r
746 }
747 slices.Sort(r)
748 return slices.Compact(r)
749 }
750
751 // TODO: consider renaming this table
752 func genFoldTable(w *bytes.Buffer, firstValidHash bool) {
753 runes := make(map[rune][]rune)
754 rangetable.Visit(categories, func(r rune) {
755 ff := folds(r)
756 if len(ff) > 2 {
757 runes[r] = append(runes[r], ff...)
758 }
759 if len(ff) == 1 && toUpper(r) != toLower(r) {
760 runes[r] = append(runes[r], ff...)
761 }
762 })
763 // FIXME: fix the below since we have to work around it in the code
764 // WARN: we should not need to add this manually
765 runes['İ'] = append(runes['İ'], 'İ')
766 runes['ß'] = append(runes['ß'], 'ẞ')
767
768 keys := make([]uint32, 0, len(runes))
769 for k, rs := range runes {
770 // Make sure the key is included (was an issue with: 'ß')
771 if !slices.Contains(rs, k) {
772 rs = append(rs, k)
773 }
774 runes[k] = dedupe(rs)
775 keys = append(keys, uint32(k))
776 }
777
778 conf := HashConfig{
779 TableName: "FoldMap",
780 TableSize: foldMapSize,
781 HashShift: foldMapShift,
782 FirstValidHash: firstValidHash,
783 }
784 seed := conf.GenerateHashValues(keys)
785
786 // Make key the first element of the rune slice
787 folds := make([][]rune, 0, len(runes))
788 for k, rs := range runes {
789 if rs[0] != k {
790 a := []rune{k}
791 for _, r := range rs {
792 if r != k {
793 a = append(a, r)
794 }
795 }
796 rs = a
797 }
798 folds = append(folds, rs)
799 }
800 slices.SortFunc(folds, func(f1, f2 []rune) int {
801 return cmp.Compare(f1[0], f2[0])
802 })
803
804 fmt.Fprint(w, "\n")
805 fmt.Fprintf(w, "const _FoldMapSeed = 0x%04X\n", seed)
806 fmt.Fprintf(w, "const _FoldMapShift = %d\n", foldMapShift)
807 fmt.Fprint(w, "\n")
808 fmt.Fprintln(w, "// FoldMap stores the Unicode case-folds for characters "+
809 "that have two or more folds.")
810 fmt.Fprintf(w, "var _FoldMap = [%d][4]uint16{\n", foldMapSize)
811 for _, ff := range folds {
812 fmt.Fprintf(w, "\t%d: {0x%04X", hash(uint32(ff[0]), seed, foldMapShift), ff[0])
813 for _, f := range ff[1:] {
814 fmt.Fprintf(w, ", 0x%04X", f)
815 }
816 fmt.Fprintf(w, "}, // %q\n", ff)
817 }
818 fmt.Fprint(w, "}\n\n")
819
820 type runeSet struct {
821 r uint32
822 a [2]rune
823 }
824
825 var noUpperLower []runeSet
826 for k, rs := range runes {
827 u := toUpper(k)
828 l := toLower(k)
829 a := make([]rune, 0, 2)
830 for _, r := range rs {
831 if r != u && r != l {
832 a = append(a, r)
833 }
834 }
835 if len(a) > 2 {
836 log.Fatalf("fold set excluding upper/lower %q "+
837 "must have 2 or less elements got: %d", a, len(a))
838 }
839 switch len(a) {
840 case 0:
841 a = append(a, k, k)
842 case 1:
843 a = append(a, a[0])
844 }
845 slices.Sort(a)
846 noUpperLower = append(noUpperLower, runeSet{uint32(k), [2]rune{a[0], a[1]}})
847 }
848 slices.SortFunc(noUpperLower, func(c1, c2 runeSet) int {
849 return cmp.Compare(c1.r, c2.r)
850 })
851
852 const foldMapExcludingUpperLowerComment = `
853 // _FoldMapExcludingUpperLower stores the Unicode case-folds for charactecrs that
854 // have two or more folds, but excludes the uppercase and lowercase forms of the
855 // character.`
856
857 fmt.Fprintln(w, "")
858 fmt.Fprintf(w, "const _FoldMapExcludingUpperLowerSeed = 0x%04X\n", seed)
859 fmt.Fprintf(w, "const _FoldMapExcludingUpperLowerShift = %d\n", foldMapShift)
860 fmt.Fprintln(w, "")
861
862 fmt.Fprintln(w, foldMapExcludingUpperLowerComment)
863 fmt.Fprintf(w, "var _FoldMapExcludingUpperLower = [%d]struct {\n", foldMapSize)
864 fmt.Fprintln(w, "\tr uint16")
865 fmt.Fprintln(w, "\ta [2]uint16")
866 fmt.Fprintln(w, "}{")
867 for _, c := range noUpperLower {
868 h := hash(c.r, seed, foldMapShift)
869 if c.a[0] > math.MaxUint16 {
870 log.Fatalf("rune 0x%04X is larger than MaxUint16 0x%04X", c.a[0], math.MaxUint16)
871 }
872 if c.a[1] > math.MaxUint16 {
873 log.Fatalf("rune 0x%04X is larger than MaxUint16 0x%04X", c.a[1], math.MaxUint16)
874 }
875 fmt.Fprintf(w, "\t%d: {0x%04X, [2]uint16{0x%04X, 0x%04X}}, // %q: [%q, %q]\n",
876 h, c.r, c.a[0], c.a[1], c.r, c.a[0], c.a[1])
877 }
878 fmt.Fprint(w, "}\n\n")
879 }
880
881 func genUpperLowerTable(w *bytes.Buffer, firstValidHash bool) {
882 // WARN: attempt to use caseOrbit so that we don't have to handle special
883 // cases with toUpperLowerSpecial.
884
885 const docComment = `
886 // _UpperLower stores upper/lower case pairs of Unicode code points.
887 // This takes up more space than the stdlib's "unicode" package, but
888 // is roughly ~4x faster.`
889
890 type Case struct {
891 Rune rune `json:"rune"`
892 Upper rune `json:"upper"`
893 Lower rune `json:"lower"`
894 }
895 var cases []Case
896
897 // special cases where Rune != Upper or Lower
898 var special []Case
899
900 for r := rune('A'); r <= unicode.MaxRune; r++ {
901 if r <= unicode.MaxASCII {
902 continue
903 }
904 l := toLower(r)
905 u := toUpper(r)
906 if r != l || r != u {
907 if r == l || r == u {
908 cases = append(cases, Case{Rune: r, Upper: u, Lower: l})
909 } else {
910 special = append(special, Case{Rune: r, Upper: u, Lower: l})
911 }
912 }
913 }
914
915 keys := make([]uint32, len(cases))
916 for i, c := range cases {
917 keys[i] = uint32(c.Rune)
918 }
919 // TODO: this is probably not necessary
920 slices.Sort(keys)
921 keys = slices.Compact(keys)
922
923 conf := HashConfig{
924 TableName: "UpperLower",
925 TableSize: upperLowerTableSize,
926 HashShift: upperLowerTableShift,
927 ShiftHash: true,
928 FirstValidHash: firstValidHash,
929 }
930 seed := conf.GenerateHashValues(keys)
931
932 fmt.Fprint(w, "\n")
933 fmt.Fprintf(w, "const _UpperLowerSeed = 0x%04X\n", seed)
934 fmt.Fprintf(w, "const _UpperLowerShift = %d\n", upperLowerTableShift)
935 fmt.Fprint(w, "\n")
936 fmt.Fprintln(w, strings.TrimSpace(docComment))
937 fmt.Fprintf(w, "var _UpperLower = [%d][2]uint32{\n", upperLowerTableSize)
938 for _, c := range cases {
939 fmt.Fprintf(w, "\t%d: {0x%04X, 0x%04X}, // %q => %q\n",
940 shiftHash(seed, uint32(c.Rune), upperLowerTableShift), c.Upper, c.Lower, c.Upper, c.Lower)
941 }
942 fmt.Fprint(w, "}\n\n")
943
944 slices.SortFunc(special, func(c1, c2 Case) int {
945 return cmp.Compare(c1.Rune, c2.Rune)
946 })
947
948 fmt.Fprintln(w, `
949 // toUpperLowerSpecial returns the uppercase and lowercase form of r,
950 // which is a character that is not equal to either its uppercase or
951 // lowercase form and thus cannot be mapped into the _UpperLower table.
952 func toUpperLowerSpecial(r rune) (rune, rune, bool) {
953 switch r {`)
954 for _, c := range special {
955 fmt.Fprintf(w, "\tcase %q:\n", c.Rune)
956 fmt.Fprintf(w, "\t\treturn %q, %q, %t\n", c.Upper, c.Lower, true)
957 }
958 fmt.Fprintln(w, "\t}")
959 fmt.Fprintln(w, "\treturn r, r, false")
960 fmt.Fprintln(w, "}")
961 }
962
963 func writeInitGuard(w *bytes.Buffer) {
964 const s = `
965
966 func init() {
967 // This is essentially a compile time assertion that can only fail if a
968 // future Go release updates the version of Unicode it supports. This
969 // check is elided if the Unicode versions match.
970 //
971 // TLDR if you see this panic file an issue:
972 // https://github.com/charlievieth/strcase/issues
973 //
974 if UnicodeVersion != unicode.Version {
975 panic("strcase.UnicodeVersion \"" + UnicodeVersion +
976 "\" != unicode.Version \"" + unicode.Version + "\"")
977 }
978 }
979
980 `
981 w.WriteString(s)
982 }
983
984 func writeTypes(w *bytes.Buffer) {
985 const s = `
986
987 // A foldPair stores Unicode case folding pairs
988 type foldPair struct {
989 From uint32
990 To uint32
991 }
992
993 `
994 w.WriteString(s)
995 }
996
997 func writeFunctions(w *bytes.Buffer) {
998 const s = `
999
1000 // TODO: rename to "foldCase"
1001 //
1002 // CaseFold returns the Unicode simple case-fold for r, if one exists, or r
1003 // unmodified, if one does not exist.
1004 func CaseFold(r rune) rune {
1005 // TODO: check if r is ASCII here?
1006 u := uint32(r)
1007 h := (u * _CaseFoldsSeed) >> _CaseFoldsShift
1008 p := _CaseFolds[h]
1009 if p.From == u {
1010 r = rune(p.To)
1011 }
1012 return r
1013 }
1014
1015 // TODO: rename
1016 func FoldMap(r rune) *[4]uint16 {
1017 u := uint32(r)
1018 h := (u * _FoldMapSeed) >> _FoldMapShift
1019 p := &_FoldMap[h]
1020 if uint32(p[0]) == u {
1021 return p
1022 }
1023 return nil
1024 }
1025
1026 func FoldMapExcludingUpperLower(r rune) [2]rune {
1027 u := uint32(r)
1028 h := (u * _FoldMapSeed) >> _FoldMapShift
1029 p := &_FoldMapExcludingUpperLower[h]
1030 if uint32(p.r) == u {
1031 return [2]rune{rune(p.a[0]), rune(p.a[1])}
1032 }
1033 return [2]rune{}
1034 }
1035
1036 // ToUpperLower combines unicode.ToUpper and unicode.ToLower in one function.
1037 func ToUpperLower(r rune) (upper, lower rune, foundMapping bool) {
1038 if r <= 0x80 {
1039 if 'A' <= r && r <= 'Z' {
1040 return r, r + ('a' - 'A'), true
1041 }
1042 if 'a' <= r && r <= 'z' {
1043 return r - ('a' - 'A'), r, true
1044 }
1045 return r, r, false
1046 }
1047 // Hash rune r and see if it's in the _UpperLower table.
1048 u := uint32(r)
1049 h := (u | u<<24) * _UpperLowerSeed
1050 p := &_UpperLower[h>>_UpperLowerShift]
1051 if p[0] == u || p[1] == u {
1052 return rune(p[0]), rune(p[1]), true
1053 }
1054 // Handle Unicode characters that do not equal
1055 // their upper and lower case forms.
1056 return toUpperLowerSpecial(r)
1057 }
1058
1059 `
1060 w.WriteString(s)
1061 }
1062
1063 func runCommand(dir string, args ...string) {
1064 cmd := exec.Command("go", args...)
1065 cmd.Dir = dir
1066 out, err := cmd.CombinedOutput()
1067 if err != nil {
1068 log.Printf("Error: %v", err)
1069 log.Printf("Command: %s", strings.Join(cmd.Args, " "))
1070 log.Printf("Output: %s", bytes.TrimSpace(out))
1071 log.Panicf("Failed to build generated file: %v\n", err)
1072 }
1073 }
1074
1075 func testBuild(tablesFile string, data []byte, skipTests bool) {
1076 dir, err := os.MkdirTemp("", "strcase.*")
1077 if err != nil {
1078 log.Panic(err)
1079 }
1080
1081 tables := filepath.Join(dir, filepath.Base(tablesFile))
1082 overlay := filepath.Join(dir, "overlay.json")
1083
1084 type overlayJSON struct {
1085 Replace map[string]string
1086 }
1087
1088 overlayData, err := json.Marshal(overlayJSON{
1089 Replace: map[string]string{
1090 // filepath.Base(tablesFile): tables,
1091 tablesFile: tables,
1092 },
1093 })
1094 if err != nil {
1095 log.Panic(err)
1096 }
1097
1098 if err := os.WriteFile(overlay, overlayData, 0644); err != nil {
1099 log.Panic(err)
1100 }
1101 if err := os.WriteFile(tables, data, 0644); err != nil {
1102 log.Panic(err)
1103 }
1104
1105 cmdDir := filepath.Dir(tablesFile)
1106 runCommand(cmdDir, "build", "-overlay="+overlay, "./...")
1107 if !skipTests {
1108 runCommand(cmdDir, "test", "-overlay="+overlay, "./...")
1109 }
1110
1111 os.RemoveAll(dir) // Only remove temp dir if successful
1112 }
1113
1114 func dataEqual(filename string, data []byte) bool {
1115 got, err := os.ReadFile(filename)
1116 return err == nil && bytes.Equal(got, data)
1117 }
1118
1119 func writeFile(name string, data []byte) {
1120 if dataEqual(name, data) {
1121 return
1122 }
1123
1124 f, err := os.CreateTemp(filepath.Dir(name), filepath.Base(name)+".tmp.*")
1125 if err != nil {
1126 log.Fatal(err)
1127 }
1128 tmp := f.Name()
1129 exit := func(err error) {
1130 os.Remove(tmp)
1131 log.Panic(err)
1132 }
1133 if _, err := f.Write(data); err != nil {
1134 exit(err)
1135 }
1136 if err := f.Chmod(0644); err != nil {
1137 exit(err)
1138 }
1139 if err := f.Close(); err != nil {
1140 exit(err)
1141 }
1142 if err := os.Rename(tmp, name); err != nil {
1143 exit(err)
1144 }
1145 }
1146
1147 func writeTemp(name string, b []byte) {
1148 dir, err := os.MkdirTemp("", "strcase.gen.*")
1149 if err != nil {
1150 log.Panic(err)
1151 }
1152 path := filepath.Join(dir, name)
1153 if err := os.WriteFile(path, b, 0644); err != nil {
1154 log.Panic(err)
1155 }
1156 log.Println("TMPFILE:", path)
1157 }
1158
1159 // TODO: use gen.CodeWriter
1160 //
1161 // writeGo formats the Go source in w and re-writes it back to w.
1162 func writeGo(w *bytes.Buffer, tablesFile, buildTags string) {
1163 data := make([]byte, w.Len())
1164 copy(data, w.Bytes())
1165 src, err := format.Source(data)
1166 if err != nil {
1167 writeTemp(tablesFile, data)
1168 log.Panic(err)
1169 }
1170 w.Reset()
1171 if _, err := gen.WriteGo(w, "tables", buildTags, src); err != nil {
1172 log.Fatal(err)
1173 }
1174 }
1175
1176 func hashCaseFolds() string {
1177 b := make([]byte, 0, 4096)
1178 for _, p := range caseFolds {
1179 b = binary.LittleEndian.AppendUint32(b, p.From)
1180 b = binary.LittleEndian.AppendUint32(b, p.To)
1181 }
1182 return fmt.Sprintf("%x", sha256.Sum256(b))
1183 }
1184
1185 type TableInfo struct {
1186 Filename string `json:"filename"`
1187 UnicodeVersion string `json:"unicode_version"`
1188 CLDRVersion string `json:"cldr_version"`
1189 CaseFoldHash string `json:"case_fold_hash"`
1190 GenGoHash string `json:"gen_go_hash"`
1191 TableHashes map[string]uint32 `json:"table_hashes"`
1192 }
1193
1194 var tableInfo = TableInfo{
1195 TableHashes: map[string]uint32{},
1196 }
1197
1198 func readTableInfo(root, tablesFile string) (map[string]TableInfo, error) {
1199 m := make(map[string]TableInfo)
1200 // The ".tables.json" file is adjacent to the generated tables file.
1201 data, err := os.ReadFile(filepath.Join(root, ".tables.json"))
1202 if err != nil {
1203 return m, err
1204 }
1205 if err := json.Unmarshal(data, &m); err != nil {
1206 return m, err
1207 }
1208 return m, nil
1209 }
1210
1211 // TODO: change this to use the Unicode version instead of the file name
1212 //
1213 // Note: loadTableInfo may be an absolute path.
1214 func loadTableInfo(root, tablesFile string) {
1215 m, err := readTableInfo(root, tablesFile)
1216 if err != nil {
1217 if os.IsNotExist(err) {
1218 return
1219 }
1220 log.Panic(err)
1221 }
1222 base := filepath.Base(tablesFile)
1223 tableInfo = m[base]
1224 // TODO: do we need this intermediary step ??
1225 if tableInfo.Filename == "" {
1226 tableInfo.Filename = base
1227 }
1228 if tableInfo.TableHashes == nil {
1229 tableInfo.TableHashes = make(map[string]uint32)
1230 }
1231 }
1232
1233 func updateTableInfoFile(root, tablesFile, fileHash, foldHash string) {
1234 base := filepath.Base(tablesFile)
1235
1236 tableInfo.Filename = base
1237 tableInfo.UnicodeVersion = gen.UnicodeVersion()
1238 tableInfo.CLDRVersion = gen.CLDRVersion()
1239 tableInfo.CaseFoldHash = foldHash
1240 tableInfo.GenGoHash = fileHash
1241
1242 m, err := readTableInfo(root, tablesFile)
1243 if err != nil && !os.IsNotExist(err) {
1244 log.Panic(err)
1245 }
1246 m[base] = tableInfo
1247
1248 data, err := json.MarshalIndent(m, "", " ")
1249 if err != nil {
1250 log.Panic(err)
1251 }
1252 writeFile(filepath.Join(root, ".tables.json"), data)
1253 }
1254
1255 func fileExists(name string) bool {
1256 _, err := os.Lstat(name)
1257 return err == nil
1258 }
1259
1260 var category = map[string]bool{
1261 // Nd Lu etc.
1262 // We use one-character names to identify merged categories
1263 "L": true, // Lu Ll Lt Lm Lo
1264 "P": true, // Pc Pd Ps Pe Pu Pf Po
1265 "M": true, // Mn Mc Me
1266 "N": true, // Nd Nl No
1267 "S": true, // Sm Sc Sk So
1268 "Z": true, // Zs Zl Zp
1269 "C": true, // Cc Cf Cs Co Cn
1270 }
1271
1272 // This contains only the properties we're interested in.
1273 type Char struct {
1274 codePoint rune // if zero, this index is not a valid code point.
1275 category string
1276 upperCase rune
1277 lowerCase rune
1278 titleCase rune
1279 foldCase rune // simple case folding
1280 caseOrbit rune // next in simple case folding orbit
1281 }
1282
1283 func allCategories() []string {
1284 a := make([]string, 0, len(category))
1285 for k := range category {
1286 a = append(a, k)
1287 }
1288 sort.Strings(a)
1289 return a
1290 }
1291
1292 func allCatFold(m map[string]map[rune]bool) []string {
1293 a := make([]string, 0, len(m))
1294 for k := range m {
1295 a = append(a, k)
1296 }
1297 slices.Sort(a)
1298 return a
1299 }
1300
1301 // WARN WARN WARN: move this
1302 func loadChars() {
1303 ucd.Parse(gen.OpenUCDFile("UnicodeData.txt"), func(p *ucd.Parser) {
1304 c := Char{codePoint: p.Rune(0)}
1305
1306 getRune := func(field int) rune {
1307 if p.String(field) == "" {
1308 return 0
1309 }
1310 return p.Rune(field)
1311 }
1312
1313 c.category = p.String(ucd.GeneralCategory)
1314 category[c.category] = true
1315 switch c.category {
1316 case "Nd":
1317 // Decimal digit
1318 p.Int(ucd.NumericValue)
1319 case "Lu":
1320 c.upperCase = getRune(ucd.CodePoint)
1321 c.lowerCase = getRune(ucd.SimpleLowercaseMapping)
1322 c.titleCase = getRune(ucd.SimpleTitlecaseMapping)
1323 case "Ll":
1324 c.upperCase = getRune(ucd.SimpleUppercaseMapping)
1325 c.lowerCase = getRune(ucd.CodePoint)
1326 c.titleCase = getRune(ucd.SimpleTitlecaseMapping)
1327 case "Lt":
1328 c.upperCase = getRune(ucd.SimpleUppercaseMapping)
1329 c.lowerCase = getRune(ucd.SimpleLowercaseMapping)
1330 c.titleCase = getRune(ucd.CodePoint)
1331 default:
1332 c.upperCase = getRune(ucd.SimpleUppercaseMapping)
1333 c.lowerCase = getRune(ucd.SimpleLowercaseMapping)
1334 c.titleCase = getRune(ucd.SimpleTitlecaseMapping)
1335 }
1336
1337 chars[c.codePoint] = c
1338 })
1339 }
1340
1341 // WARN: rename and fix other loadCategories()
1342 func loadCategoryTables() map[string]*unicode.RangeTable {
1343 categoryOp := func(code rune, class uint8) bool {
1344 category := chars[code].category
1345 return len(category) > 0 && category[0] == class
1346 }
1347
1348 list := allCategories()
1349 cats := make(map[string]*unicode.RangeTable, len(list))
1350
1351 // Avoid calculating these tables if possible
1352 if gen.UnicodeVersion() == unicode.Version {
1353 for _, name := range list {
1354 if _, ok := unicode.Categories[name]; !ok {
1355 log.Fatal("unknown category", name)
1356 }
1357 cats[name] = unicode.Categories[name]
1358 }
1359 return cats
1360 }
1361
1362 for _, name := range list {
1363 if _, ok := category[name]; !ok {
1364 log.Fatal("unknown category", name)
1365 }
1366 var rt *unicode.RangeTable
1367 if len(name) == 1 { // unified categories
1368 rt = dumpRange(func(code rune) bool { return categoryOp(code, name[0]) })
1369 } else {
1370 rt = dumpRange(func(code rune) bool { return chars[code].category == name })
1371 }
1372 cats[name] = rt
1373 }
1374 return cats
1375 }
1376
1377 type Op func(code rune) bool
1378
1379 // TODO: rename
1380 func dumpRange(inCategory Op) *unicode.RangeTable {
1381 runes := []rune{}
1382 for i := range chars {
1383 r := rune(i)
1384 if inCategory(r) {
1385 runes = append(runes, r)
1386 }
1387 }
1388 return rangetable.New(runes...)
1389 }
1390
1391 // PropList.txt has the same format as Scripts.txt so we can share its parser.
1392 func loadScriptOrProperty(doProps bool) map[string]*unicode.RangeTable {
1393 if gen.UnicodeVersion() == unicode.Version {
1394 if doProps {
1395 return unicode.Properties
1396 }
1397 return unicode.Scripts
1398 }
1399
1400 file := "Scripts.txt"
1401 table := scripts
1402 if doProps {
1403 file = "PropList.txt"
1404 table = props
1405 }
1406 ucd.Parse(gen.OpenUCDFile(file), func(p *ucd.Parser) {
1407 name := p.String(1)
1408 table[name] = append(table[name], p.Rune(0))
1409 })
1410
1411 // Handle deprecated "STerm" alias (this is only needed for tests)
1412 if rt, ok := table["Sentence_Terminal"]; ok {
1413 table["STerm"] = rt
1414 }
1415 tab := make(map[string]*unicode.RangeTable, len(table))
1416 for name, runes := range table {
1417 tab[name] = rangetable.New(runes...)
1418 }
1419 return tab
1420 }
1421
1422 func loadCasefold() (foldCategory, foldScript map[string]*unicode.RangeTable) {
1423 // Build list of case-folding groups attached to each canonical folded char (typically lower case).
1424 var caseOrbit = make([][]rune, MaxChar+1)
1425 for j := range chars {
1426 i := rune(j)
1427 c := &chars[i]
1428 if c.foldCase == 0 {
1429 continue
1430 }
1431 orb := caseOrbit[c.foldCase]
1432 if orb == nil {
1433 orb = append(orb, c.foldCase)
1434 }
1435 caseOrbit[c.foldCase] = append(orb, i)
1436 }
1437
1438 // Insert explicit 1-element groups when assuming [lower, upper] would be wrong.
1439 for j := range chars {
1440 i := rune(j)
1441 c := &chars[i]
1442 f := c.foldCase
1443 if f == 0 {
1444 f = i
1445 }
1446 orb := caseOrbit[f]
1447 if orb == nil && (c.upperCase != 0 && c.upperCase != i || c.lowerCase != 0 && c.lowerCase != i) {
1448 // Default assumption of [upper, lower] is wrong.
1449 caseOrbit[i] = []rune{i}
1450 }
1451 }
1452
1453 // Delete the groups for which assuming [lower, upper] or [upper, lower] is right.
1454 for i, orb := range caseOrbit {
1455 if len(orb) == 2 && chars[orb[0]].upperCase == orb[1] && chars[orb[1]].lowerCase == orb[0] {
1456 caseOrbit[i] = nil
1457 }
1458 if len(orb) == 2 && chars[orb[1]].upperCase == orb[0] && chars[orb[0]].lowerCase == orb[1] {
1459 caseOrbit[i] = nil
1460 }
1461 }
1462
1463 // Record orbit information in chars.
1464 for _, orb := range caseOrbit {
1465 if orb == nil {
1466 continue
1467 }
1468 sort.Slice(orb, func(i, j int) bool {
1469 return orb[i] < orb[j]
1470 })
1471 c := orb[len(orb)-1]
1472 for _, d := range orb {
1473 chars[c].caseOrbit = d
1474 c = d
1475 }
1476 }
1477
1478 loadAsciiFold()
1479 loadCaseOrbit()
1480
1481 // Fast exit if we don't need to recalculate these tables.
1482 if gen.UnicodeVersion() == unicode.Version {
1483 return unicode.FoldCategory, unicode.FoldScript
1484 }
1485
1486 // Tables of category and script folding exceptions: code points
1487 // that must be added when interpreting a particular category/script
1488 // in a case-folding context.
1489 cat := make(map[string]map[rune]bool)
1490 for name := range category {
1491 if x := foldExceptions(inCategory(name)); len(x) > 0 {
1492 cat[name] = x
1493 }
1494 }
1495
1496 scr := make(map[string]map[rune]bool)
1497 for name := range scripts {
1498 if x := foldExceptions(scripts[name]); len(x) > 0 {
1499 scr[name] = x
1500 }
1501 }
1502
1503 return loadCatFold(cat), loadCatFold(scr) // TODO: this takes ~60ms
1504 }
1505
1506 func loadAsciiFold() {
1507 for i := rune(0); i <= unicode.MaxASCII; i++ {
1508 c := chars[i]
1509 f := c.caseOrbit
1510 if f == 0 {
1511 switch {
1512 case c.lowerCase != i && c.lowerCase != 0:
1513 f = c.lowerCase
1514 case c.upperCase != i && c.upperCase != 0:
1515 f = c.upperCase
1516 default:
1517 f = i
1518 }
1519 }
1520 asciiFold[i] = uint16(f)
1521 }
1522 }
1523
1524 // TODO: rename
1525 func loadCaseOrbit() {
1526 for i := range chars {
1527 c := &chars[i]
1528 if c.caseOrbit != 0 {
1529 caseOrbit = append(caseOrbit, foldPair{uint32(i), uint32(c.caseOrbit)})
1530 }
1531 }
1532 }
1533
1534 // inCategory returns a list of all the runes in the category.
1535 func inCategory(name string) []rune {
1536 var x []rune
1537 for j := range chars {
1538 i := rune(j)
1539 c := &chars[i]
1540 if c.category == name || len(name) == 1 && len(c.category) > 1 && c.category[0] == name[0] {
1541 x = append(x, i)
1542 }
1543 }
1544 // fmt.Printf("%s: %d\n", name, len(x))
1545 return x
1546 }
1547
1548 // foldExceptions returns a list of all the runes fold-equivalent
1549 // to runes in class but not in class themselves.
1550 func foldExceptions(class []rune) map[rune]bool {
1551 // Create map containing class and all fold-equivalent chars.
1552 m := make(map[rune]bool)
1553 for _, r := range class {
1554 c := &chars[r]
1555 if c.caseOrbit == 0 {
1556 // Just upper and lower.
1557 if u := c.upperCase; u != 0 {
1558 m[u] = true
1559 }
1560 if l := c.lowerCase; l != 0 {
1561 m[l] = true
1562 }
1563 m[r] = true
1564 continue
1565 }
1566 // Otherwise walk orbit.
1567 r0 := r
1568 for {
1569 m[r] = true
1570 r = chars[r].caseOrbit
1571 if r == r0 {
1572 break
1573 }
1574 }
1575 }
1576
1577 // Remove class itself.
1578 for _, r := range class {
1579 delete(m, r)
1580 }
1581
1582 // What's left is the exceptions.
1583 return m
1584 }
1585
1586 func loadCatFold(m map[string]map[rune]bool) map[string]*unicode.RangeTable {
1587 folds := allCatFold(m)
1588 tabs := make(map[string]*unicode.RangeTable, len(folds))
1589 for _, name := range folds {
1590 class := m[name]
1591 tabs[name] = dumpRange(func(code rune) bool { return class[code] })
1592 }
1593 return tabs
1594 }
1595
1596 // TODO: move to the top
1597 func initTables(root, tablesFile string) {
1598 loadTableInfo(root, tablesFile)
1599 loadChars()
1600 loadCaseFolds() // download Unicode tables
1601 foldCategories, foldScripts := loadCasefold() // TODO: this is slow (~200ms)
1602
1603 cats := []map[string]*unicode.RangeTable{
1604 loadCategoryTables(),
1605 loadScriptOrProperty(false),
1606 loadScriptOrProperty(true),
1607 foldCategories,
1608 foldScripts,
1609 }
1610
1611 tabs := make([]*unicode.RangeTable, 0, len(cats))
1612 for _, m := range cats {
1613 for _, rt := range m {
1614 tabs = append(tabs, rt)
1615 }
1616 }
1617 categories = rangetable.Merge(tabs...)
1618
1619 caseRanges = generateCaseRanges()
1620 }
1621
1622 func requireFlags(names ...string) {
1623 var missing []string
1624 for _, name := range names {
1625 if flag.Lookup(name) == nil {
1626 missing = append(missing, name)
1627 }
1628 }
1629 if len(missing) > 0 {
1630 log.Panicf("The following flags were not registered: %q", missing)
1631 }
1632 }
1633
1634 func listSourceFiles(dir string) []string {
1635 match := func(name string) bool {
1636 if name == "go.mod" || name == "go.sum" {
1637 return true
1638 }
1639 if strings.HasSuffix(name, "_test.go") {
1640 return false
1641 }
1642 switch filepath.Ext(name) {
1643 case ".go", ".c", ".cc", ".cpp", ".cxx", ".f", ".F", ".f90", ".for",
1644 ".h", ".hh", ".hpp", ".hxx", ".m", ".s", ".S", ".swig", ".swigcxx",
1645 ".sx", ".syso":
1646 return true
1647 }
1648 return false
1649 }
1650 var a []string
1651 err := filepath.WalkDir(dir, func(path string, d fs.DirEntry, err error) error {
1652 name := d.Name()
1653 if d.IsDir() && (name == "vendor" || name[0] == '.') {
1654 return fs.SkipDir
1655 }
1656 if match(name) {
1657 a = append(a, path)
1658 }
1659 return nil
1660 })
1661 if err != nil {
1662 log.Fatal(err)
1663 }
1664 slices.Sort(a)
1665 return a
1666 }
1667
1668 func hashGenFiles() string {
1669 root, err := util.GenTablesRoot()
1670 if err != nil {
1671 log.Fatal(err)
1672 }
1673
1674 files := listSourceFiles(root)
1675 if len(files) == 0 {
1676 log.Fatal("no go source files in:", root)
1677 }
1678
1679 h := sha256.New()
1680 for _, name := range files {
1681 fmt.Fprintf(h, "%s\x00", filepath.Base(name))
1682 data, err := os.ReadFile(name)
1683 if err != nil {
1684 log.Fatal(err)
1685 }
1686 _, _ = h.Write(data)
1687 _, _ = h.Write([]byte{'\x00', '\x00'})
1688 }
1689
1690 return fmt.Sprintf("%x", h.Sum(nil))
1691 }
1692
1693 var useCachedSeeds = flag.Bool("cache", false,
1694 "used cached seeds instead of regenerating (for testing only)")
1695
1696 func realMain() int {
1697 initLogs() // Other packages configure logs on init so do it again here
1698
1699 root, err := util.ProjectRoot()
1700 if err != nil {
1701 log.Panic(err)
1702 }
1703
1704 flag.Usage = func() {
1705 flag.CommandLine.SetOutput(os.Stdout) // Write help to STDOUT
1706 fmt.Fprintf(flag.CommandLine.Output(), "Usage: %s [OPTION]...\n",
1707 filepath.Base(os.Args[0]))
1708 flag.PrintDefaults()
1709 }
1710
1711 // NB(charlie): the "-url", "-iana", "-unicode", and "-cldr" flags are
1712 // registered by the github.com/charlievieth/strcase/internal/gen/gen package.
1713 requireFlags("url", "iana", "unicode", "cldr")
1714
1715 skipTests := flag.Bool("skip-tests", false, "skip running tests")
1716 skipBuild := flag.Bool("skip-build", false, "skip building the strcase package (testing only)")
1717 dryRun := flag.Bool("dry-run", false,
1718 "report if generate would change the generated tables file and exit non-zero")
1719 // TODO: remove `-update-gen-hash` since it's dangerous and bypasses
1720 // our checks.
1721 updateGenHash := flag.Bool("update-gen-hash", false,
1722 `only update the hash of the gen.go file stored in ".tables.go" `+
1723 `(WARN: this is only for development)`)
1724 cpuprofile := flag.String("cpuprofile", "",
1725 "write cpu profile to `file`\n"+
1726 "NOTE: this traps SIGINT.\n"+
1727 " First SIGINT the cpu profile is written to 'file'.\n"+
1728 " Second SIGINT the program aborts.")
1729
1730 firstValidHash := flag.Bool("first-valid-hash", false,
1731 "use the first valid hash instead of performing an exhaustive search (testing only, much faster)")
1732
1733 outputDir := flag.String("dir", filepath.Join(root, "internal", "tables"),
1734 "write generated tables to this directory")
1735 // outputDir := flag.String("dir", filepath.Join(root),
1736 // "write generated tables to this directory")
1737
1738 flag.Parse()
1739
1740 if flag.NArg() != 0 {
1741 flag.Usage()
1742 return 1
1743 }
1744
1745 // Validate Unicode version flag
1746
1747 var supportedVersions []string
1748 for v := range buildTags {
1749 supportedVersions = append(supportedVersions, v)
1750 }
1751 if _, ok := buildTags[gen.UnicodeVersion()]; !ok {
1752 slices.Sort(supportedVersions)
1753 log.Printf("The selected Unicode version %q is unsupported. Either the version\n"+
1754 "is incorrect or this code needs to updated to handle a new version of Go.\n"+
1755 "The supported Unicode versions are: %q.", gen.UnicodeVersion(), supportedVersions)
1756 return 1
1757 }
1758
1759 tablesFile := tablesFileName(*outputDir)
1760 // Use the Unicode version as the log prefix since we invoke this program
1761 // multiple times with different versions.
1762 log.SetPrefix("(" + gen.UnicodeVersion() + ") ")
1763
1764 log.Println("Tables file:", tablesFile)
1765
1766 if *cpuprofile != "" {
1767 f, err := os.Create(*cpuprofile)
1768 if err != nil {
1769 log.Fatal("could not create CPU profile: ", err)
1770 }
1771 if err := pprof.StartCPUProfile(f); err != nil {
1772 log.Fatal("could not start CPU profile: ", err)
1773 }
1774 defer pprof.StopCPUProfile()
1775 ch := make(chan os.Signal, 1)
1776 signal.Notify(ch, os.Interrupt)
1777 go func() {
1778 <-ch
1779 log.Println("writing CPU profile: next interrupt will stop the program")
1780 pprof.StopCPUProfile()
1781 if err := f.Close(); err != nil {
1782 log.Printf("error closing CPU profile: %v", err)
1783 }
1784 signal.Reset(os.Interrupt)
1785 }()
1786 }
1787
1788 if !*updateGenHash && *outputDir != "." {
1789 if err := os.MkdirAll(*outputDir, 0755); err != nil {
1790 log.Println("error:", err)
1791 return 1
1792 }
1793 }
1794
1795 buildTags := buildTags[gen.UnicodeVersion()].buildTags
1796 if buildTags == "" {
1797 log.Printf("missing build tags for unicode version: %q", gen.UnicodeVersion())
1798 return 1
1799 }
1800
1801 initTables(root, tablesFile)
1802 fileHash := hashGenFiles() // hash gentables source files
1803 foldHash := hashCaseFolds()
1804
1805 chop := func(s string, n int) string {
1806 if len(s) >= n {
1807 return s[:n]
1808 }
1809 return s
1810 }
1811
1812 if fileExists(tablesFile) &&
1813 gen.UnicodeVersion() == tableInfo.UnicodeVersion &&
1814 gen.CLDRVersion() == tableInfo.CLDRVersion &&
1815 foldHash == tableInfo.CaseFoldHash &&
1816 fileHash == tableInfo.GenGoHash {
1817
1818 log.Printf("gen: exiting - no changes:\n"+
1819 " unicode_version: %q\n"+
1820 " cldr_version: %q\n"+
1821 " case_fold_hash: %q\n"+
1822 " gen_go_hash: %q\n",
1823 tableInfo.UnicodeVersion, tableInfo.CLDRVersion,
1824 chop(tableInfo.CaseFoldHash, 8), chop(tableInfo.GenGoHash, 8))
1825 return 0
1826 }
1827
1828 isTerm := term.IsTerminal(1)
1829 ansi := func(color int, s string) string {
1830 if !isTerm {
1831 return s
1832 }
1833 return fmt.Sprintf("\x1b[%d;m%s\x1b[0;m", color, s)
1834 }
1835 colorize := func(args ...string) []any {
1836 if len(args)&1 != 0 {
1837 log.Panicf("number of args (%d) must be even!", len(args))
1838 }
1839 // Quote args since we can't use '%q' in log.Printf
1840 for i, s := range args {
1841 args[i] = strconv.Quote(s)
1842 }
1843 // Colorize args that have changed if output is a terminal
1844 if isTerm {
1845 for i := 0; i < len(args); i += 2 {
1846 if args[i] != args[i+1] {
1847 args[i] = ansi(32, args[i]) // green
1848 args[i+1] = ansi(31, args[i+1]) // red
1849 }
1850 }
1851 }
1852 a := make([]any, len(args))
1853 for i, s := range args {
1854 a[i] = s
1855 }
1856 return a
1857 }
1858
1859 // TODO: print a relative path
1860 log.Printf("gen: would update "+tablesFile+" due to the following changes:\n"+
1861 " unicode_version: %s => %s\n"+
1862 " cldr_version: %s => %s\n"+
1863 " case_fold_hash: %s => %s\n"+
1864 " gen_go_hash: %s => %s\n\n",
1865 colorize(tableInfo.UnicodeVersion, gen.UnicodeVersion(),
1866 tableInfo.CLDRVersion, gen.CLDRVersion(),
1867 chop(tableInfo.CaseFoldHash, 8), chop(foldHash, 8),
1868 chop(tableInfo.GenGoHash, 8), chop(fileHash, 8))...)
1869 if *dryRun {
1870 log.Printf("%s gen: would change %s "+
1871 "(remove -dry-run flag to update the generated files)\n",
1872 tablesFile, ansi(33, "WARN:"))
1873 log.Printf("%s gen: exiting now\n", ansi(33, "WARN:"))
1874
1875 return 1
1876 }
1877
1878 // NB: can't test or build if the Unicode version does not match
1879 // the version used by the Go binary running this.
1880 if !*updateGenHash {
1881 var w bytes.Buffer
1882
1883 w.WriteString("\n\nimport \"unicode\"\n\n")
1884 gen.WriteUnicodeVersion(&w)
1885
1886 writeInitGuard(&w)
1887 writeTypes(&w)
1888 writeFunctions(&w)
1889
1890 genCaseFolds(&w, *firstValidHash)
1891 genUpperLowerTable(&w, *firstValidHash)
1892 genFoldTable(&w, *firstValidHash)
1893
1894 writeGo(&w, tablesFile, buildTags)
1895 if *skipBuild {
1896 log.Println("gen: skipping go build")
1897 } else {
1898 if gen.UnicodeVersion() != unicode.Version {
1899 log.Printf("gen: \"go build\" is ineffective because the generated file "+
1900 "will be excluded due to Unicode version: %q != %q",
1901 tableInfo.UnicodeVersion, unicode.Version)
1902 }
1903 testBuild(tablesFile, w.Bytes(), *skipTests)
1904 }
1905
1906 // For dry runs only report if tables.go would be changed and
1907 // exit with an error if so.
1908 if *dryRun {
1909 // TODO: this might be unreachable
1910 if !dataEqual(tablesFile, w.Bytes()) {
1911 fmt.Printf("gen: would change %s", tablesFile)
1912 return 1
1913 }
1914 return 0
1915 }
1916
1917 writeFile(tablesFile, w.Bytes())
1918 }
1919
1920 updateTableInfoFile(root, tablesFile, fileHash, foldHash)
1921 log.Printf("Successfully generated tables:\n"+
1922 " unicode_version: %q\n"+
1923 " cldr_version: %q\n"+
1924 " case_fold_hash: %q\n"+
1925 " gen_go_hash: %q\n",
1926 tableInfo.UnicodeVersion, tableInfo.CLDRVersion,
1927 chop(tableInfo.CaseFoldHash, 8), chop(tableInfo.GenGoHash, 8))
1928
1929 // Exit 1 if we only update the hash of the generate files since this
1930 // is a development only flag.
1931 if *updateGenHash {
1932 return 1
1933 }
1934 return 0
1935 }
1936
1937 func main() {
1938 if code := realMain(); code != 0 {
1939 os.Exit(code)
1940 }
1941 }