1// SPDX-License-Identifier: MIT
2
3package expr
4
5import (
6 "strings"
7 "unicode"
8 "unicode/utf16"
9 "unicode/utf8"
10)
11
12// The tables in casing_tables.go are generated; see go:generate in doc.go.
13
14// This file reproduces the JavaScript string functions the reference
15// implementation relies on: toUpperCase and toLowerCase (full Unicode case
16// mapping, including multi-character results such as "ß" to "SS" and the
17// Final_Sigma rule), trim, and the \s character class.
18
19// isJSSpace reports whether r is in JavaScript's WhiteSpace or
20// LineTerminator sets. It is both the \s regular expression class and the
21// set removed by String.prototype.trim and by Number().
22func isJSSpace(r rune) bool {
23 switch r {
24 case '\t', '\n', '\v', '\f', '\r', ' ', 0xA0, 0x1680, 0x2028, 0x2029, 0x202F, 0x205F, 0x3000, 0xFEFF:
25 return true
26 }
27 return r >= 0x2000 && r <= 0x200A
28}
29
30func isASCII(s string) bool {
31 for i := 0; i < len(s); i++ {
32 if s[i] >= utf8.RuneSelf {
33 return false
34 }
35 }
36 return true
37}
38
39// Strings are Go strings, so text that JavaScript would hold as a lone
40// UTF-16 surrogate (from fromJSON('"\ud800"')) is kept in WTF-8: the
41// three-byte form 0xED 0xA0-0xBF 0x80-0xBF that UTF-8 forbids. The helpers
42// below make every case and comparison function treat such a sequence as one
43// code unit and copy it unchanged, as JavaScript does, instead of letting Go
44// turn each byte into U+FFFD.
45
46// wtf8Surrogate reports whether s starts with a WTF-8 lone surrogate and
47// returns its code unit.
48func wtf8Surrogate(s string) (rune, bool) {
49 if len(s) >= 3 && s[0] == 0xED && s[1] >= 0xA0 && s[1] <= 0xBF && s[2]&0xC0 == 0x80 {
50 return rune(s[0]&0x0F)<<12 | rune(s[1]&0x3F)<<6 | rune(s[2]&0x3F), true
51 }
52 return 0, false
53}
54
55// decodeRune is utf8.DecodeRuneInString that also decodes a WTF-8 lone
56// surrogate (width 3) to its code unit value.
57func decodeRune(s string) (rune, int) {
58 r, w := utf8.DecodeRuneInString(s)
59 if r == utf8.RuneError && w == 1 {
60 if sur, ok := wtf8Surrogate(s); ok {
61 return sur, 3
62 }
63 }
64 return r, w
65}
66
67// writeRune writes r, using the WTF-8 form for a surrogate code unit.
68func writeRune(b *strings.Builder, r rune) {
69 if r >= 0xD800 && r < 0xE000 {
70 b.WriteByte(0xE0 | byte(r>>12))
71 b.WriteByte(0x80 | byte(r>>6)&0x3F)
72 b.WriteByte(0x80 | byte(r)&0x3F)
73 return
74 }
75 b.WriteRune(r)
76}
77
78// normalizeWTF8 joins a lone high surrogate immediately followed by a lone low
79// surrogate into the supplementary character they form, as concatenating two
80// JavaScript strings does. Strings built by concatenation (format, join) go
81// through it.
82func normalizeWTF8(s string) string {
83 if !strings.Contains(s, "\xed") {
84 return s
85 }
86 var b strings.Builder
87 b.Grow(len(s))
88 for i := 0; i < len(s); {
89 r, w := decodeRune(s[i:])
90 if r >= 0xD800 && r < 0xDC00 {
91 if lo, lw := decodeRune(s[i+w:]); lo >= 0xDC00 && lo < 0xE000 && lw == 3 && i+w < len(s) {
92 b.WriteRune(0x10000 + (r-0xD800)<<10 + (lo - 0xDC00))
93 i += w + lw
94 continue
95 }
96 }
97 b.WriteString(s[i : i+w])
98 i += w
99 }
100 return b.String()
101}
102
103func writeUpper(b *strings.Builder, r rune, keepDotlessI bool) {
104 if keepDotlessI && r == 'ı' {
105 b.WriteRune(r)
106 return
107 }
108 if s, ok := jsUpperDelta[r]; ok {
109 b.WriteString(s)
110 return
111 }
112 writeRune(b, unicode.ToUpper(r))
113}
114
115func upperWith(s string, keepDotlessI bool) string {
116 if isASCII(s) {
117 return strings.ToUpper(s)
118 }
119 var b strings.Builder
120 b.Grow(len(s))
121 for i := 0; i < len(s); {
122 r, w := decodeRune(s[i:])
123 i += w
124 writeUpper(&b, r, keepDotlessI)
125 }
126 return b.String()
127}
128
129// jsToUpper is String.prototype.toUpperCase.
130func jsToUpper(s string) string { return upperWith(s, false) }
131
132// toUpperSpecial upper-cases s like jsToUpper but leaves the dotless i
133// (U+0131) alone, as the reference implementation does for its
134// case-insensitive comparisons and for startsWith and endsWith.
135func toUpperSpecial(s string) string { return upperWith(s, true) }
136
137// jsToLower is String.prototype.toLowerCase, including the Final_Sigma
138// context rule (a capital sigma at the end of a word becomes ς).
139func jsToLower(s string) string {
140 if isASCII(s) {
141 return strings.ToLower(s)
142 }
143 runes := make([]rune, 0, len(s))
144 for i := 0; i < len(s); {
145 r, w := decodeRune(s[i:])
146 runes = append(runes, r)
147 i += w
148 }
149 var b strings.Builder
150 b.Grow(len(s))
151 for i, r := range runes {
152 switch r {
153 case 0x3A3:
154 if finalSigma(runes, i) {
155 b.WriteRune('ς')
156 } else {
157 b.WriteRune('σ')
158 }
159 default:
160 if m, ok := jsLowerDelta[r]; ok {
161 b.WriteString(m)
162 } else {
163 writeRune(&b, unicode.ToLower(r))
164 }
165 }
166 }
167 return b.String()
168}
169
170// finalSigma implements the Final_Sigma condition of Unicode SpecialCasing:
171// the sigma is preceded by a cased letter, ignoring case-ignorable
172// characters, and is not followed by one.
173func finalSigma(runes []rune, i int) bool {
174 before := false
175 for j := i - 1; j >= 0; j-- {
176 if isCaseIgnorable(runes[j]) {
177 continue
178 }
179 before = isCased(runes[j])
180 break
181 }
182 if !before {
183 return false
184 }
185 for j := i + 1; j < len(runes); j++ {
186 if isCaseIgnorable(runes[j]) {
187 continue
188 }
189 return !isCased(runes[j])
190 }
191 return true
192}
193
194func isCased(r rune) bool {
195 return unicode.IsUpper(r) || unicode.IsLower(r) || unicode.IsTitle(r) ||
196 unicode.Is(unicode.Other_Lowercase, r) || unicode.Is(unicode.Other_Uppercase, r)
197}
198
199func isCaseIgnorable(r rune) bool {
200 switch r {
201 case '\'', '.', ':', '^', '`', 0xA8, 0xAD, 0xAF, 0xB4, 0xB7, 0xB8, 0x2018, 0x2019, 0x2024, 0x2027, 0xFE13, 0xFE52, 0xFE55, 0xFF07, 0xFF0E, 0xFF1A:
202 return true
203 }
204 return unicode.In(r, unicode.Mn, unicode.Me, unicode.Cf, unicode.Lm, unicode.Sk)
205}
206
207// utf16Units encodes s as the UTF-16 code units a JavaScript string holds,
208// WTF-8 lone surrogates included.
209func utf16Units(s string) []uint16 {
210 out := make([]uint16, 0, len(s))
211 for i := 0; i < len(s); {
212 r, w := decodeRune(s[i:])
213 i += w
214 if r >= 0xD800 && r < 0xE000 {
215 out = append(out, uint16(r))
216 continue
217 }
218 if r >= 0x10000 {
219 hi, lo := utf16.EncodeRune(r)
220 out = append(out, uint16(hi), uint16(lo))
221 continue
222 }
223 out = append(out, uint16(r))
224 }
225 return out
226}
227
228// compareUTF16 compares two strings by UTF-16 code unit, which is how
229// JavaScript orders strings with < and >. It differs from byte or rune order
230// only for supplementary-plane characters against U+E000..U+FFFF.
231func compareUTF16(a, b string) int {
232 if isASCII(a) && isASCII(b) {
233 return strings.Compare(a, b)
234 }
235 ua, ub := utf16Units(a), utf16Units(b)
236 for i := 0; i < len(ua) && i < len(ub); i++ {
237 if ua[i] != ub[i] {
238 if ua[i] < ub[i] {
239 return -1
240 }
241 return 1
242 }
243 }
244 switch {
245 case len(ua) > len(ub):
246 return 1
247 case len(ua) < len(ub):
248 return -1
249 }
250 return 0
251}
252
253// exceedsUTF16Len reports whether s is longer than max UTF-16 code units. It
254// stops counting at max and allocates nothing. Invalid UTF-8 bytes count as
255// one unit each (U+FFFD), like the conversion Lex applies.
256func exceedsUTF16Len(s string, max int) bool {
257 n := 0
258 for _, r := range s {
259 n++
260 if r >= 0x10000 {
261 n++
262 }
263 if n > max {
264 return true
265 }
266 }
267 return false
268}
269
270// hasWTF8 reports whether s holds a lone surrogate in WTF-8 form.
271func hasWTF8(s string) bool {
272 for i := 0; i < len(s); i++ {
273 if s[i] == 0xED {
274 if _, ok := wtf8Surrogate(s[i:]); ok {
275 return true
276 }
277 }
278 }
279 return false
280}
281
282// jsIncludes, jsHasPrefix and jsHasSuffix are String.prototype.includes,
283// startsWith and endsWith. They work on bytes, which is equivalent to UTF-16
284// code units except around lone surrogates (a lone high surrogate is found
285// inside a supplementary character), where they switch to code units.
286func jsIncludes(s, sub string) bool {
287 if !hasWTF8(s) && !hasWTF8(sub) {
288 return strings.Contains(s, sub)
289 }
290 us, usub := utf16Units(s), utf16Units(sub)
291 for i := 0; i+len(usub) <= len(us); i++ {
292 if unitsEqual(us[i:i+len(usub)], usub) {
293 return true
294 }
295 }
296 return false
297}
298
299func jsHasPrefix(s, prefix string) bool {
300 if !hasWTF8(s) && !hasWTF8(prefix) {
301 return strings.HasPrefix(s, prefix)
302 }
303 us, up := utf16Units(s), utf16Units(prefix)
304 return len(up) <= len(us) && unitsEqual(us[:len(up)], up)
305}
306
307func jsHasSuffix(s, suffix string) bool {
308 if !hasWTF8(s) && !hasWTF8(suffix) {
309 return strings.HasSuffix(s, suffix)
310 }
311 us, up := utf16Units(s), utf16Units(suffix)
312 return len(up) <= len(us) && unitsEqual(us[len(us)-len(up):], up)
313}
314
315func unitsEqual(a, b []uint16) bool {
316 for i := range a {
317 if a[i] != b[i] {
318 return false
319 }
320 }
321 return len(a) == len(b)
322}