Debian Codegraph @

Data/Unicode/Internal/NormalizeStream.hs

raw
1 {-# OPTIONS_GHC -funbox-strict-fields #-}
2 {-# LANGUAGE BangPatterns #-}
3 {-# LANGUAGE CPP #-}
4 {-# LANGUAGE LambdaCase #-}
5 {-# LANGUAGE TupleSections #-}
6 -- |
7 -- Module : Data.Unicode.Internal.NormalizeStream
8 -- Copyright : (c) 2016 Harendra Kumar
9 -- (c) 2020 Andrew Lelechenko
10 --
11 -- License : BSD-3-Clause
12 -- Maintainer : [email protected]
13 -- Stability : experimental
14 --
15 -- Stream based normalization.
16 --
17 module Data.Unicode.Internal.NormalizeStream
18 (
19 UC.DecomposeMode(..)
20 , stream
21 , unstream
22 , unstreamC
23 )
24 where
25
26 import Data.Char (chr, ord)
27 import GHC.ST (ST(..))
28 import GHC.Types (SPEC(..))
29
30 import qualified Data.Text.Array as A
31 import qualified Unicode.Char as UC
32
33 #if MIN_VERSION_text(2,0,0)
34 import Data.Text.Internal.Fusion (stream)
35 #else
36 import Data.Bits (shiftR)
37 import Data.Text.Internal.Unsafe.Char (unsafeChr)
38 import Data.Text.Internal.Fusion.Size (betweenSize)
39 import Data.Text.Internal.Encoding.Utf16 (chr2)
40 #endif
41
42 -- Internal modules
43 import Data.Text.Internal (Text(..))
44 import Data.Text.Internal.Fusion.Size (upperBound)
45 import Data.Text.Internal.Fusion.Types (Step(..), Stream(..))
46 import Data.Text.Internal.Private (runText)
47 import Data.Text.Internal.Unsafe.Char (unsafeWrite)
48
49 -------------------------------------------------------------------------------
50 -- Reorder buffer to hold characters till the next starter boundary
51 -------------------------------------------------------------------------------
52
53 -- | A list of combining characters, ordered by 'UC.combiningClass'.
54 -- Couple of top levels are unrolled and unpacked for efficiency.
55 data ReBuf = Empty | One !Char | Many !Char !Char ![Char]
56
57 {-# INLINE insertIntoReBuf #-}
58 insertIntoReBuf :: Char -> ReBuf -> ReBuf
59 insertIntoReBuf c Empty = One c
60 insertIntoReBuf c (One c0)
61 | UC.combiningClass c < UC.combiningClass c0
62 = Many c c0 []
63 | otherwise
64 = Many c0 c []
65 insertIntoReBuf c (Many c0 c1 cs)
66 | cc < UC.combiningClass c0
67 = Many c c0 (c1 : cs)
68 | cc < UC.combiningClass c1
69 = Many c0 c (c1 : cs)
70 | otherwise
71 = Many c0 c1 (cs' ++ (c : cs''))
72 where
73 cc = UC.combiningClass c
74 (cs', cs'') = span ((<= cc) . UC.combiningClass) cs
75
76 writeStr :: A.MArray s -> Int -> [Char] -> ST s Int
77 writeStr marr di str = go di str
78 where
79 go i [] = return i
80 go i (c : cs) = do
81 n <- unsafeWrite marr i c
82 go (i + n) cs
83
84 {-# INLINE writeReorderBuffer #-}
85 writeReorderBuffer :: A.MArray s -> Int -> ReBuf -> ST s Int
86 writeReorderBuffer _ di Empty = return di
87
88 writeReorderBuffer marr di (One c) = do
89 n <- unsafeWrite marr di c
90 return (di + n)
91
92 writeReorderBuffer marr di (Many c1 c2 str) = do
93 n1 <- unsafeWrite marr di c1
94 n2 <- unsafeWrite marr (di + n1) c2
95 writeStr marr (di + n1 + n2) str
96
97 -------------------------------------------------------------------------------
98 -- Decomposition of Hangul characters is done algorithmically
99 -------------------------------------------------------------------------------
100
101 -- {-# INLINE decomposeCharHangul #-}
102 decomposeCharHangul :: A.MArray s -> Int -> Char -> ST s Int
103 decomposeCharHangul marr j c =
104 if t == chr UC.jamoTFirst then do
105 n1 <- unsafeWrite marr j l
106 n2 <- unsafeWrite marr (j + n1) v
107 return (j + n1 + n2)
108 else do
109 n1 <- unsafeWrite marr j l
110 n2 <- unsafeWrite marr (j + n1) v
111 n3 <- unsafeWrite marr (j + n1 + n2) t
112 return (j + n1 + n2 + n3)
113 where
114 (l, v, t) = UC.decomposeHangul c
115
116 {-# INLINE decomposeChar #-}
117 decomposeChar
118 :: UC.DecomposeMode
119 -> A.MArray s -- destination array for decomposition
120 -> Int -- array index
121 -> ReBuf -- reorder buffer
122 -> Char -- char to be decomposed
123 -> ST s (Int, ReBuf)
124 decomposeChar mode marr index reBuf ch
125 | UC.isHangul ch = do
126 j <- writeReorderBuffer marr index reBuf
127 (, Empty) <$> decomposeCharHangul marr j ch
128 | UC.isDecomposable mode ch =
129 decomposeAll marr index reBuf (UC.decompose mode ch)
130 | otherwise =
131 reorder marr index reBuf ch
132
133 where
134
135 {-# INLINE decomposeAll #-}
136 decomposeAll _ i rbuf [] = return (i, rbuf)
137 decomposeAll arr i rbuf (x : xs)
138 | UC.isDecomposable mode x = do
139 (i', rbuf') <- decomposeAll arr i rbuf (UC.decompose mode x)
140 decomposeAll arr i' rbuf' xs
141 | otherwise = do
142 (i', rbuf') <- reorder arr i rbuf x
143 decomposeAll arr i' rbuf' xs
144
145 {-# INLINE reorder #-}
146 reorder arr i rbuf c
147 | UC.isCombining c = return (i, insertIntoReBuf c rbuf)
148 | otherwise = do
149 j <- writeReorderBuffer arr i rbuf
150 n <- unsafeWrite arr j c
151 return (j + n, Empty)
152
153 #if !MIN_VERSION_text(2,0,0)
154 -- | /O(n)/ Convert a 'Text' into a 'Stream Char'.
155 stream :: Text -> Stream Char
156 stream (Text arr off len) = Stream next off (betweenSize (len `shiftR` 1) len)
157 where
158 !end = off+len
159 {-# INLINE next #-}
160 next !i
161 | i >= end = Done
162 -- shift generates only two branches instead of three in case of
163 -- range check, works quite a bit faster with llvm backend.
164 | (n `shiftR` 10) == 0x36 = Yield (chr2 n n2) (i + 2)
165 | otherwise = Yield (unsafeChr n) (i + 1)
166 where
167 n = A.unsafeIndex arr i
168 n2 = A.unsafeIndex arr (i + 1)
169 {-# INLINE [0] stream #-}
170 #endif
171
172 -- | /O(n)/ Convert a 'Stream Char' into a decompose-normalized 'Text'.
173 unstream :: UC.DecomposeMode -> Stream Char -> Text
174 unstream mode (Stream next0 s0 len) = runText $ \done -> do
175 -- Before encoding each char we perform a buffer realloc check assuming
176 -- worst case encoding size of two 16-bit units for the char. Just add an
177 -- extra space to the buffer so that we do not end up reallocating even when
178 -- all the chars are encoded as single unit.
179 let margin = 1 + maxDecomposeLen
180 mlen = (upperBound 4 len + margin)
181 arr0 <- A.new mlen
182 let outer !arr !maxi = encode
183 where
184 -- keep the common case loop as small as possible
185 encode !si !di rbuf =
186 -- simply check for the worst case
187 if maxi < di + margin
188 then realloc si di rbuf
189 else
190 case next0 si of
191 Done -> do
192 di' <- writeReorderBuffer arr di rbuf
193 done arr di'
194 Skip si' -> encode si' di rbuf
195 Yield c si' -> do
196 (di', rbuf') <- decomposeChar mode arr di rbuf c
197 encode si' di' rbuf'
198 -- n <- unsafeWrite arr di c
199 -- encode si' (di + n) rbuf
200
201 -- keep uncommon case separate from the common case code
202 {-# NOINLINE realloc #-}
203 realloc !si !di rbuf = do
204 let newlen = maxi * 2
205 arr' <- A.new newlen
206 A.copyM arr' 0 arr 0 di
207 outer arr' (newlen - 1) si di rbuf
208
209 outer arr0 (mlen - 1) s0 0 Empty
210 {-# INLINE [0] unstream #-}
211
212 -- we can generate this from UCD
213 maxDecomposeLen :: Int
214 maxDecomposeLen = 32
215
216 -------------------------------------------------------------------------------
217 -- Composition
218 -------------------------------------------------------------------------------
219
220 -- If we are composing we do not need to first decompose Hangul. We can just
221 -- compose assuming there could be some partially composed syllables e.g. LV
222 -- syllable followed by a jamo T. We need to compose this case as well.
223
224 -- Hold an L to wait for V, hold an LV to wait for T.
225 data JamoBuf
226 = Jamo !Char -- Jamo L, V or T
227 | Hangul !Char -- Hangul Syllable LV or LVT
228 | HangulLV !Char
229
230 data RegBuf
231 = RegOne !Char
232 | RegMany !Char !Char ![Char]
233
234 data ComposeState
235 = ComposeNone
236 | ComposeReg !RegBuf
237 | ComposeJamo !JamoBuf
238
239 -------------------------------------------------------------------------------
240 -- Composition of Jamo into Hangul syllables, done algorithmically
241 -------------------------------------------------------------------------------
242
243 {-# INLINE writeJamoBuf #-}
244 writeJamoBuf :: A.MArray s -> Int -> JamoBuf -> ST s Int
245 writeJamoBuf arr i jbuf = do
246 n <- unsafeWrite arr i (getCh jbuf)
247 return (i + n)
248
249 where
250
251 getCh (Jamo ch) = ch
252 getCh (Hangul ch) = ch
253 getCh (HangulLV ch) = ch
254
255 {-# INLINE initHangul #-}
256 initHangul :: Char -> Int -> ST s (Int, ComposeState)
257 initHangul c i = return (i, ComposeJamo (Hangul c))
258
259 {-# INLINE initJamo #-}
260 initJamo :: Char -> Int -> ST s (Int, ComposeState)
261 initJamo c i = return (i, ComposeJamo (Jamo c))
262
263 {-# INLINE insertJamo #-}
264 insertJamo
265 :: A.MArray s -> Int -> JamoBuf -> Char -> ST s (Int, ComposeState)
266 insertJamo arr i jbuf ch
267 | ich <= UC.jamoLLast = do
268 j <- writeJamoBuf arr i jbuf
269 return (j, ComposeJamo (Jamo ch))
270 | ich < UC.jamoVFirst =
271 flushAndWrite arr i jbuf ch
272 | ich <= UC.jamoVLast = do
273 case jbuf of
274 Jamo c ->
275 case UC.jamoLIndex c of
276 Just li ->
277 let vi = ich - UC.jamoVFirst
278 lvi = li * UC.jamoNCount + vi * UC.jamoTCount
279 lv = chr (UC.hangulFirst + lvi)
280 in return (i, ComposeJamo (HangulLV lv))
281 Nothing -> writeTwo arr i c ch
282 Hangul c -> writeTwo arr i c ch
283 HangulLV c -> writeTwo arr i c ch
284 | ich <= UC.jamoTFirst = do
285 flushAndWrite arr i jbuf ch
286 | otherwise = do
287 let ti = ich - UC.jamoTFirst
288 case jbuf of
289 Jamo c -> writeTwo arr i c ch
290 Hangul c
291 | UC.isHangulLV c -> do
292 writeLVT arr i c ti
293 | otherwise ->
294 writeTwo arr i c ch
295 HangulLV c ->
296 writeLVT arr i c ti
297
298 where
299
300 ich = ord ch
301
302 {-# INLINE flushAndWrite #-}
303 flushAndWrite marr ix jb c = do
304 j <- writeJamoBuf marr ix jb
305 n <- unsafeWrite marr j c
306 return (j + n, ComposeNone)
307
308 {-# INLINE writeLVT #-}
309 writeLVT marr ix lv ti = do
310 n <- unsafeWrite marr ix (chr ((ord lv) + ti))
311 return (ix + n, ComposeNone)
312
313 {-# INLINE writeTwo #-}
314 writeTwo marr ix c1 c2 = do
315 n <- unsafeWrite marr ix c1
316 m <- unsafeWrite marr (ix + n) c2
317 return ((ix + n + m), ComposeNone)
318
319 {-# INLINE insertHangul #-}
320 insertHangul
321 :: A.MArray s -> Int -> JamoBuf -> Char -> ST s (Int, ComposeState)
322 insertHangul arr i jbuf ch = do
323 j <- writeJamoBuf arr i jbuf
324 return (j, ComposeJamo (Hangul ch))
325
326 {-# INLINE insertIntoRegBuf #-}
327 insertIntoRegBuf :: Char -> RegBuf -> RegBuf
328 insertIntoRegBuf c (RegOne c0)
329 | UC.combiningClass c < UC.combiningClass c0
330 = RegMany c c0 []
331 | otherwise
332 = RegMany c0 c []
333 insertIntoRegBuf c (RegMany c0 c1 cs)
334 | cc < UC.combiningClass c0
335 = RegMany c c0 (c1 : cs)
336 | cc < UC.combiningClass c1
337 = RegMany c0 c (c1 : cs)
338 | otherwise
339 = RegMany c0 c1 (cs' ++ (c : cs''))
340 where
341 cc = UC.combiningClass c
342 (cs', cs'') = span ((<= cc) . UC.combiningClass) cs
343
344 {-# INLINE writeRegBuf #-}
345 writeRegBuf :: A.MArray s -> Int -> RegBuf -> ST s Int
346 writeRegBuf arr i = \case
347 RegOne c -> do
348 n <- unsafeWrite arr i c
349 return (i + n)
350 RegMany st c [] ->
351 case UC.compose st c of
352 Just x -> do
353 n <- unsafeWrite arr i x
354 return (i + n)
355 Nothing -> do
356 n <- unsafeWrite arr i st
357 m <- unsafeWrite arr (i + n) c
358 return (i + n + m)
359 RegMany st0 c0 cs0 -> go [] st0 (c0 : cs0)
360
361 where
362
363 -- arguments: uncombined chars, starter, unprocessed str
364 go uncs st [] = writeStr arr i (st : uncs)
365 go uncs st (c : cs) = case UC.compose st c of
366 Nothing -> go (uncs ++ (c : same)) st bigger
367 Just x -> go uncs x cs
368 where
369 cc = UC.combiningClass c
370 (same, bigger) = span ((== cc) . UC.combiningClass) cs
371
372 {-# INLINE flushComposeState #-}
373 flushComposeState :: A.MArray s -> Int -> ComposeState -> ST s Int
374 flushComposeState arr i = \case
375 ComposeNone -> pure i
376 ComposeReg rbuf -> writeRegBuf arr i rbuf
377 ComposeJamo jbuf -> writeJamoBuf arr i jbuf
378
379 {-# INLINE composeChar #-}
380 composeChar
381 :: UC.DecomposeMode
382 -> A.MArray s -- destination array for composition
383 -> Char -- input char
384 -> Int -- array index
385 -> ComposeState
386 -> ST s (Int, ComposeState)
387 composeChar mode marr = go0
388
389 where
390
391 go0 ch !i !st =
392 case st of
393 ComposeReg rbuf
394 | ich < UC.jamoLFirst ->
395 composeReg rbuf ch i st
396 | ich <= UC.jamoTLast -> do
397 j <- writeRegBuf marr i rbuf
398 initJamo ch j
399 | ich < UC.hangulFirst ->
400 composeReg rbuf ch i st
401 | ich <= UC.hangulLast -> do
402 j <- writeRegBuf marr i rbuf
403 initHangul ch j
404 | otherwise ->
405 composeReg rbuf ch i st
406 ComposeJamo jbuf
407 | ich < UC.jamoLFirst -> do
408 jamoToReg marr i jbuf ch
409 | ich <= UC.jamoTLast -> do
410 insertJamo marr i jbuf ch
411 | ich < UC.hangulFirst ->
412 jamoToReg marr i jbuf ch
413 | ich <= UC.hangulLast -> do
414 insertHangul marr i jbuf ch
415 | otherwise ->
416 jamoToReg marr i jbuf ch
417 ComposeNone
418 | ich < UC.jamoLFirst ->
419 initReg ch i
420 | ich <= UC.jamoTLast ->
421 initJamo ch i
422 | ich < UC.hangulFirst ->
423 initReg ch i
424 | ich <= UC.hangulLast ->
425 initHangul ch i
426 | otherwise ->
427 initReg ch i
428 where ich = ord ch
429
430 {-# INLINE jamoToReg #-}
431 jamoToReg arr i jbuf ch = do
432 j <- writeJamoBuf arr i jbuf
433 initReg ch j
434
435 {-# INLINE initReg #-}
436 initReg !ch !i
437 | UC.isDecomposable mode ch =
438 go (UC.decompose mode ch) i ComposeNone
439 | otherwise =
440 pure (i, ComposeReg (RegOne ch))
441
442 {-# INLINE composeReg #-}
443 composeReg rbuf !ch !i !st
444 | UC.isDecomposable mode ch =
445 go (UC.decompose mode ch) i st
446 | UC.isCombining ch = do
447 pure (i, ComposeReg (insertIntoRegBuf ch rbuf))
448 -- The first char in RegBuf may or may not be a starter. In
449 -- case it is not we rely on composeStarters failing.
450 | RegOne s <- rbuf
451 , UC.isCombiningStarter ch
452 , Just x <- UC.composeStarters s ch =
453 pure (i, (ComposeReg (RegOne x)))
454 | otherwise = do
455 j <- writeRegBuf marr i rbuf
456 pure (j, ComposeReg (RegOne ch))
457
458 go [] !i !st = pure (i, st)
459 go (ch : rest) i st =
460 case st of
461 ComposeReg rbuf
462 | UC.isHangul ch -> do
463 j <- writeRegBuf marr i rbuf
464 (k, s) <- initHangul ch j
465 go rest k s
466 | UC.isJamo ch -> do
467 j <- writeRegBuf marr i rbuf
468 (k, s) <- initJamo ch j
469 go rest k s
470 | UC.isDecomposable mode ch ->
471 go (UC.decompose mode ch ++ rest) i st
472 | UC.isCombining ch -> do
473 go rest i (ComposeReg (insertIntoRegBuf ch rbuf))
474 | RegOne s <- rbuf
475 , UC.isCombiningStarter ch
476 , Just x <- UC.composeStarters s ch ->
477 go rest i (ComposeReg (RegOne x))
478 | otherwise -> do
479 j <- writeRegBuf marr i rbuf
480 go rest j (ComposeReg (RegOne ch))
481 ComposeJamo jbuf
482 | UC.isJamo ch -> do
483 (j, s) <- insertJamo marr i jbuf ch
484 go rest j s
485 | UC.isHangul ch -> do
486 (j, s) <- insertHangul marr i jbuf ch
487 go rest j s
488 | otherwise -> do
489 j <- writeJamoBuf marr i jbuf
490 case () of
491 _
492 | UC.isDecomposable mode ch ->
493 go (UC.decompose mode ch ++ rest) j
494 ComposeNone
495 | otherwise ->
496 go rest j (ComposeReg (RegOne ch))
497 ComposeNone
498 | UC.isHangul ch -> do
499 (j, s) <- initHangul ch i
500 go rest j s
501 | UC.isJamo ch -> do
502 (j, s) <- initJamo ch i
503 go rest j s
504 | UC.isDecomposable mode ch ->
505 go (UC.decompose mode ch ++ rest) i st
506 | otherwise ->
507 go rest i (ComposeReg (RegOne ch))
508
509 -- | /O(n)/ Convert a 'Stream Char' into a composed normalized 'Text'.
510 unstreamC :: UC.DecomposeMode -> Stream Char -> Text
511 unstreamC mode (Stream next0 s0 len) = runText $ \done -> do
512 -- Before encoding each char we perform a buffer realloc check assuming
513 -- worst case encoding size of two 16-bit units for the char. Just add an
514 -- extra space to the buffer so that we do not end up reallocating even when
515 -- all the chars are encoded as single unit.
516 let margin = 1 + maxDecomposeLen
517 mlen = (upperBound 4 len + margin)
518 arr0 <- A.new mlen
519 let outer !arr !maxi = encode SPEC
520 where
521 -- keep the common case loop as small as possible
522 encode !_ !si !di st =
523 -- simply check for the worst case
524 if maxi < di + margin
525 then realloc si di st
526 else
527 case next0 si of
528 Done -> do
529 di' <- flushComposeState arr di st
530 done arr di'
531 Skip si' -> encode SPEC si' di st
532 Yield c si' -> do
533 (di', st') <- composeChar mode arr c di st
534 encode SPEC si' di' st'
535
536 -- keep uncommon case separate from the common case code
537 {-# NOINLINE realloc #-}
538 realloc !si !di st = do
539 let newlen = maxi * 2
540 arr' <- A.new newlen
541 A.copyM arr' 0 arr 0 di
542 outer arr' (newlen - 1) si di st
543
544 outer arr0 (mlen - 1) s0 0 ComposeNone
545 {-# INLINE [0] unstreamC #-}