src/Streamly/Internal/Unicode/Stream.hs · streamly

git.iko.soy/streamly

on 0780dbb help sign in

streamly/src/Streamly/Internal/Unicode/Stream.hs

1138 lines 42 kB history raw

1-- |

2-- Module : Streamly.Internal.Unicode.Stream

4-- (c) Bjoern Hoehrmann 2008-2009

5--

6-- License : BSD-3-Clause

7-- Maintainer : streamly@composewell.com

8-- Stability : experimental

9-- Portability : GHC

10--

12module Streamly.Internal.Unicode.Stream

13 (

14 -- * Construction (Decoding)

15 decodeLatin1

17 -- ** UTF-8 Decoding

18 , CodingFailureMode(..)

19 , writeCharUtf8'

20 , parseCharUtf8With

21 , decodeUtf8

22 , decodeUtf8'

23 , decodeUtf8_

25 -- ** Resumable UTF-8 Decoding

26 , DecodeError(..)

27 , DecodeState

28 , CodePoint

29 , decodeUtf8Either

30 , resumeDecodeUtf8Either

32 -- ** UTF-8 Array Stream Decoding

33 , decodeUtf8Arrays

34 , decodeUtf8Arrays'

35 , decodeUtf8Arrays_

37 -- * Elimination (Encoding)

38 -- ** Latin1 Encoding

39 , encodeLatin1

40 , encodeLatin1'

41 , encodeLatin1_

43 -- ** UTF-8 Encoding

44 , readCharUtf8'

45 , encodeUtf8

46 , encodeUtf8'

47 , encodeUtf8_

48 , encodeStrings

49 {-

50 -- * Operations on character strings

51 , strip -- (dropAround isSpace)

52 , stripEnd

53 -}

55 -- * Transformation

56 , stripHead

57 , lines

58 , words

59 , unlines

60 , unwords

62 -- * StreamD UTF8 Encoding / Decoding transformations.

63 , decodeUtf8D

64 , decodeUtf8D'

65 , decodeUtf8D_

66 , encodeUtf8D

67 , encodeUtf8D'

68 , encodeUtf8D_

69 , decodeUtf8EitherD

70 , resumeDecodeUtf8EitherD

71 , decodeUtf8ArraysD

72 , decodeUtf8ArraysD'

73 , decodeUtf8ArraysD_

75 -- * Decoding String Literals

76 , fromStr#

78 -- * Deprecations

79 , decodeUtf8Lax

80 , encodeLatin1Lax

81 , encodeUtf8Lax

82 )

83where

85#include "inline.hs"

87import Control.Monad (void)

88import Control.Monad.Catch (MonadThrow(..), MonadCatch)

89import Control.Monad.IO.Class (MonadIO, liftIO)

90import Data.Bits (shiftR, shiftL, (.|.), (.&.))

91import Data.Char (chr, ord)

92#if MIN_VERSION_base(4,17,0)

93import Data.Char (generalCategory, GeneralCategory(Space))

94#endif

95import Data.Word (Word8)

96import Foreign.Marshal.Alloc (mallocBytes)

97import Foreign.Storable (Storable(..))

98import Fusion.Plugin.Types (Fuse(..))

99import GHC.Base (assert, unsafeChr)

100import GHC.Exts (Addr#)

101import GHC.IO.Encoding.Failure (isSurrogate)

102import GHC.Ptr (Ptr (..), plusPtr)

103import System.IO.Unsafe (unsafePerformIO)

104import Streamly.Internal.Data.Array.Unboxed (Array)

105import Streamly.Internal.Data.Array.Unboxed.Mut.Type (MutableByteArray)

106import Streamly.Internal.Data.Fold (Fold)

107import Streamly.Internal.Data.Stream.IsStream.Type

108 (IsStream, fromStreamD, toStreamD, adapt)

109import Streamly.Internal.Data.Stream (Stream)

110import Streamly.Internal.Data.Stream.StreamD (Step (..))

111import Streamly.Internal.Data.SVar (adaptState)

112import Streamly.Internal.Data.Tuple.Strict (Tuple'(..))

113import Streamly.Internal.Data.Unboxed (peekWith)

114import Streamly.Internal.Data.Unfold.Type (Unfold(..))

115import Streamly.Internal.System.IO (unsafeInlineIO)

116

117import qualified Streamly.Data.Fold as Fold

118import qualified Streamly.Data.Unfold as Unfold

119import qualified Streamly.Internal.Data.Parser as Parser (Parser)

120import qualified Streamly.Internal.Data.Parser.ParserD as ParserD

121 (Parser(..), Step(..), Initial(..), toParserK, toFold)

122import qualified Streamly.Internal.Data.Stream as Stream (fromByteStr#)

123import qualified Streamly.Internal.Data.Stream.Serial as Serial

124import qualified Streamly.Data.Array.Unboxed as Array

125import qualified Streamly.Internal.Data.Array.Unboxed.Type as A (Array (..))

126import qualified Streamly.Internal.Data.Stream.IsStream as S

127import qualified Streamly.Internal.Data.Stream.StreamD as D

128

129import Prelude hiding (lines, words, unlines, unwords)

130

131-- $setup

132-- >>> :m

133-- >>> :set -XMagicHash

134-- >>> import Prelude hiding (lines, words, unlines, unwords)

135-- >>> import qualified Streamly.Prelude as Stream

136-- >>> import qualified Streamly.Data.Fold as Fold

137-- >>> import qualified Streamly.Internal.Unicode.Stream as Unicode

138-- >>> import Streamly.Internal.Unicode.Stream

139

140-------------------------------------------------------------------------------

141-- Latin1 decoding

142-------------------------------------------------------------------------------

143

144-- | Decode a stream of bytes to Unicode characters by mapping each byte to a

145-- corresponding Unicode 'Char' in 0-255 range.

146--

147-- /Since: 0.7.0 ("Streamly.Data.Unicode.Stream")/

148--

149-- @since 0.8.0

150{-# INLINE decodeLatin1 #-}

151decodeLatin1 :: (IsStream t, Monad m) => t m Word8 -> t m Char

152decodeLatin1 = S.map (unsafeChr . fromIntegral)

153

154-------------------------------------------------------------------------------

155-- Latin1 encoding

156-------------------------------------------------------------------------------

157

158-- | Encode a stream of Unicode characters to bytes by mapping each character

159-- to a byte in 0-255 range. Throws an error if the input stream contains

160-- characters beyond 255.

161--

162-- @since 0.8.0

163{-# INLINE encodeLatin1' #-}

164encodeLatin1' :: (IsStream t, Monad m) => t m Char -> t m Word8

165encodeLatin1' = S.map convert

166 where

167 convert c =

168 let codepoint = ord c

169 in if codepoint > 255

170 then error $ "Streamly.Unicode.encodeLatin1 invalid " ++

171 "input char codepoint " ++ show codepoint

172 else fromIntegral codepoint

173

174-- XXX Should we instead replace the invalid chars by NUL or whitespace or some

175-- other control char? That may affect the perf a bit but may be a better

176-- behavior.

177--

178-- | Like 'encodeLatin1'' but silently maps input codepoints beyond 255 to

179-- arbitrary Latin1 chars in 0-255 range. No error or exception is thrown when

180-- such mapping occurs.

181--

182-- /Since: 0.7.0 ("Streamly.Data.Unicode.Stream")/

183--

184-- /Since: 0.8.0 (Lenient Behaviour)/

185{-# INLINE encodeLatin1 #-}

186encodeLatin1 :: (IsStream t, Monad m) => t m Char -> t m Word8

187encodeLatin1 = S.map (fromIntegral . ord)

188

189-- | Like 'encodeLatin1' but drops the input characters beyond 255.

190--

191-- @since 0.8.0

192{-# INLINE encodeLatin1_ #-}

193encodeLatin1_ :: (IsStream t, Monad m) => t m Char -> t m Word8

194encodeLatin1_ = S.map (fromIntegral . ord) . S.filter (<= chr 255)

195

196-- | Same as 'encodeLatin1'

197--

198{-# DEPRECATED encodeLatin1Lax "Please use 'encodeLatin1' instead" #-}

199{-# INLINE encodeLatin1Lax #-}

200encodeLatin1Lax :: (IsStream t, Monad m) => t m Char -> t m Word8

201encodeLatin1Lax = encodeLatin1

202

203-------------------------------------------------------------------------------

204-- UTF-8 decoding

205-------------------------------------------------------------------------------

206

207-- Int helps in cheaper conversion from Int to Char

208type CodePoint = Int

209type DecodeState = Word8

210

211-- We can divide the errors in three general categories:

212-- * A non-starter was encountered in a begin state

213-- * A starter was encountered without completing a codepoint

214-- * The last codepoint was not complete (input underflow)

215--

216-- Need to separate resumable and non-resumable error. In case of non-resumable

217-- error we can also provide the failing byte. In case of resumable error the

218-- state can be opaque.

219--

220data DecodeError = DecodeError !DecodeState !CodePoint deriving Show

221

222-- See http://bjoern.hoehrmann.de/utf-8/decoder/dfa/ for details.

223

224-- XXX Use names decodeSuccess = 0, decodeFailure = 12

225

226decodeTable :: [Word8]

227decodeTable = [

228 -- The first part of the table maps bytes to character classes that

229 -- to reduce the size of the transition table and create bitmasks.

230 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

231 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

232 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

233 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

234 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,

235 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,

236 8,8,2,2,2,2,2,2,2,2,2,2,2,2,2,2, 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,

237 10,3,3,3,3,3,3,3,3,3,3,3,3,4,3,3, 11,6,6,6,5,8,8,8,8,8,8,8,8,8,8,8,

238

239 -- The second part is a transition table that maps a combination

240 -- of a state of the automaton and a character class to a state.

241 0,12,24,36,60,96,84,12,12,12,48,72, 12,12,12,12,12,12,12,12,12,12,12,12,

242 12, 0,12,12,12,12,12, 0,12, 0,12,12, 12,24,12,12,12,12,12,24,12,24,12,12,

243 12,12,12,12,12,12,12,24,12,12,12,12, 12,24,12,12,12,12,12,12,12,24,12,12,

244 12,12,12,12,12,12,12,36,12,36,12,12, 12,36,12,12,12,12,12,36,12,36,12,12,

245 12,36,12,12,12,12,12,12,12,12,12,12

246 ]

247

248{-# INLINE utf8dLength #-}

249utf8dLength :: Int

250utf8dLength = length decodeTable

251

252-- | We do not want to garbage collect this and free the memory, we want to

253-- keep this persistent. We don't know how to do that with GHC without having a

254-- reference in some global structure. So we use a hack, use mallocBytes so

255-- that the GC has no way to free it.

256{-# NOINLINE utf8d #-}

257utf8d :: Ptr Word8

258utf8d = unsafePerformIO $ do

259 let size = utf8dLength

260 p <- liftIO $ mallocBytes size

261 void $ D.fold

262 (Fold.foldlM' (\b a -> poke b a >> return (b `plusPtr` 1)) (return p))

263 (D.fromList decodeTable)

264 return p

265

266-- | Return element at the specified index without checking the bounds.

267-- and without touching the foreign ptr.

268{-# INLINE_NORMAL unsafePeekElemOff #-}

269unsafePeekElemOff :: forall a. Storable a => Ptr a -> Int -> a

270unsafePeekElemOff p i =

271 let !x = unsafeInlineIO $ peekElemOff p i

272 in x

273

274-- XXX We can use a fromPtr stream to implement it.

275{-# INLINE showMemory #-}

276showMemory ::

277 forall a. (Show a, Storable a) => Ptr a -> Ptr a -> String

278showMemory cur end

279 | cur < end =

280 let cur1 = cur `plusPtr` sizeOf (undefined :: a)

281 in show (unsafeInlineIO $ peek cur) ++ " " ++ showMemory cur1 end

282showMemory _ _ = ""

283

284-- decode is split into two separate cases to avoid branching instructions.

285-- From the higher level flow we already know which case we are in so we can

286-- call the appropriate decode function.

287--

288-- When the state is 0

289{-# INLINE decode0 #-}

290decode0 :: Ptr Word8 -> Word8 -> Tuple' DecodeState CodePoint

291decode0 table byte =

292 let !t = table `unsafePeekElemOff` fromIntegral byte

293 !codep' = (0xff `shiftR` fromIntegral t) .&. fromIntegral byte

294 !state' = table `unsafePeekElemOff` (256 + fromIntegral t)

295 in assert ((byte > 0x7f || error showByte)

296 && (state' /= 0 || error (showByte ++ showTable)))

297 (Tuple' state' codep')

298

299 where

300

301 utf8tableEnd = table `plusPtr` 364

302 showByte = "Streamly: decode0: byte: " ++ show byte

303 showTable = " table: " ++ showMemory table utf8tableEnd

304

305-- When the state is not 0

306{-# INLINE decode1 #-}

307decode1

308 :: Ptr Word8

309 -> DecodeState

310 -> CodePoint

311 -> Word8

312 -> Tuple' DecodeState CodePoint

313decode1 table state codep byte =

314 -- Remember codep is Int type!

315 -- Can it be unsafe to convert the resulting Int to Char?

316 let !t = table `unsafePeekElemOff` fromIntegral byte

317 !codep' = (fromIntegral byte .&. 0x3f) .|. (codep `shiftL` 6)

318 !state' = table `unsafePeekElemOff`

319 (256 + fromIntegral state + fromIntegral t)

320 in assert (codep' <= 0x10FFFF

321 || error (showByte ++ showState state codep))

322 (Tuple' state' codep')

323 where

324

325 utf8tableEnd = table `plusPtr` 364

326 showByte = "Streamly: decode1: byte: " ++ show byte

327 showState st cp =

328 " state: " ++ show st ++

329 " codepoint: " ++ show cp ++

330 " table: " ++ showMemory table utf8tableEnd

331

332-------------------------------------------------------------------------------

333-- Resumable UTF-8 decoding

334-------------------------------------------------------------------------------

335

336-- Strangely, GHCJS hangs linking template-haskell with this

337#ifndef __GHCJS__

338{-# ANN type UTF8DecodeState Fuse #-}

339#endif

340data UTF8DecodeState s a

341 = UTF8DecodeInit s

342 | UTF8DecodeInit1 s Word8

343 | UTF8DecodeFirst s Word8

344 | UTF8Decoding s !DecodeState !CodePoint

345 | YieldAndContinue a (UTF8DecodeState s a)

346 | Done

347

348{-# INLINE_NORMAL resumeDecodeUtf8EitherD #-}

349resumeDecodeUtf8EitherD

350 :: Monad m

351 => DecodeState

352 -> CodePoint

353 -> D.Stream m Word8

354 -> D.Stream m (Either DecodeError Char)

355resumeDecodeUtf8EitherD dst codep (D.Stream step state) =

356 let stt =

357 if dst == 0

358 then UTF8DecodeInit state

359 else UTF8Decoding state dst codep

360 in D.Stream (step' utf8d) stt

361 where

362 {-# INLINE_LATE step' #-}

363 step' _ gst (UTF8DecodeInit st) = do

364 r <- step (adaptState gst) st

365 return $ case r of

366 Yield x s -> Skip (UTF8DecodeInit1 s x)

367 Skip s -> Skip (UTF8DecodeInit s)

368 Stop -> Skip Done

369

370 step' _ _ (UTF8DecodeInit1 st x) = do

371 -- Note: It is important to use a ">" instead of a "<=" test

372 -- here for GHC to generate code layout for default branch

373 -- prediction for the common case. This is fragile and might

374 -- change with the compiler versions, we need a more reliable

375 -- "likely" primitive to control branch predication.

376 case x > 0x7f of

377 False ->

378 return $ Skip $ YieldAndContinue

379 (Right $ unsafeChr (fromIntegral x))

380 (UTF8DecodeInit st)

381 -- Using a separate state here generates a jump to a

382 -- separate code block in the core which seems to perform

383 -- slightly better for the non-ascii case.

384 True -> return $ Skip $ UTF8DecodeFirst st x

385

386 -- XXX should we merge it with UTF8DecodeInit1?

387 step' table _ (UTF8DecodeFirst st x) = do

388 let (Tuple' sv cp) = decode0 table x

389 return $

390 case sv of

391 12 ->

392 Skip $ YieldAndContinue (Left $ DecodeError 0 (fromIntegral x))

393 (UTF8DecodeInit st)

394 0 -> error "unreachable state"

395 _ -> Skip (UTF8Decoding st sv cp)

396

397 -- We recover by trying the new byte x a starter of a new codepoint.

398 -- XXX on error need to report the next byte "x" as well.

399 -- XXX need to use the same recovery in array decoding routine as well

400 step' table gst (UTF8Decoding st statePtr codepointPtr) = do

401 r <- step (adaptState gst) st

402 case r of

403 Yield x s -> do

404 let (Tuple' sv cp) = decode1 table statePtr codepointPtr x

405 return $

406 case sv of

407 0 -> Skip $ YieldAndContinue (Right $ unsafeChr cp)

408 (UTF8DecodeInit s)

409 12 ->

410 Skip $ YieldAndContinue (Left $ DecodeError statePtr codepointPtr)

411 (UTF8DecodeInit1 s x)

412 _ -> Skip (UTF8Decoding s sv cp)

413 Skip s -> return $ Skip (UTF8Decoding s statePtr codepointPtr)

414 Stop -> return $ Skip $ YieldAndContinue (Left $ DecodeError statePtr codepointPtr) Done

415

416 step' _ _ (YieldAndContinue c s) = return $ Yield c s

417 step' _ _ Done = return Stop

418

419-- XXX We can use just one API, and define InitState = 0 and InitCodePoint = 0

420-- to use as starting state.

421--

422{-# INLINE_NORMAL decodeUtf8EitherD #-}

423decodeUtf8EitherD :: Monad m

424 => D.Stream m Word8 -> D.Stream m (Either DecodeError Char)

425decodeUtf8EitherD = resumeDecodeUtf8EitherD 0 0

426

427-- |

428--

429-- /Pre-release/

430{-# INLINE decodeUtf8Either #-}

431decodeUtf8Either :: (Monad m, IsStream t)

432 => t m Word8 -> t m (Either DecodeError Char)

433decodeUtf8Either = fromStreamD . decodeUtf8EitherD . toStreamD

434

435-- |

436--

437-- /Pre-release/

438{-# INLINE resumeDecodeUtf8Either #-}

439resumeDecodeUtf8Either

440 :: (Monad m, IsStream t)

441 => DecodeState

442 -> CodePoint

443 -> t m Word8

444 -> t m (Either DecodeError Char)

445resumeDecodeUtf8Either st cp =

446 fromStreamD . resumeDecodeUtf8EitherD st cp . toStreamD

447

448-------------------------------------------------------------------------------

449-- One shot decoding

450-------------------------------------------------------------------------------

451

452data CodingFailureMode

453 = TransliterateCodingFailure

454 | ErrorOnCodingFailure

455 | DropOnCodingFailure

456 deriving (Show)

457

458{-# INLINE replacementChar #-}

459replacementChar :: Char

460replacementChar = '\xFFFD'

461

462data UTF8CharDecodeState a

463 = UTF8CharDecodeInit

464 | UTF8CharDecoding !DecodeState !CodePoint

465

466{-# INLINE parseCharUtf8WithD #-}

467parseCharUtf8WithD ::

468 MonadThrow m => CodingFailureMode -> ParserD.Parser m Word8 Char

469parseCharUtf8WithD cfm = ParserD.Parser (step' utf8d) initial extract

470

471 where

472

473 prefix = "Streamly.Internal.Data.Stream.parseCharUtf8WithD:"

474

475 {-# INLINE initial #-}

476 initial = return $ ParserD.IPartial UTF8CharDecodeInit

477

478 handleError err souldBackTrack =

479 case cfm of

480 ErrorOnCodingFailure -> ParserD.Error err

481 TransliterateCodingFailure ->

482 case souldBackTrack of

483 True -> ParserD.Done 1 replacementChar

484 False -> ParserD.Done 0 replacementChar

485 DropOnCodingFailure ->

486 case souldBackTrack of

487 True -> ParserD.Continue 1 UTF8CharDecodeInit

488 False -> ParserD.Continue 0 UTF8CharDecodeInit

489

490 {-# INLINE step' #-}

491 step' table UTF8CharDecodeInit x =

492 -- Note: It is important to use a ">" instead of a "<=" test

493 -- here for GHC to generate code layout for default branch

494 -- prediction for the common case. This is fragile and might

495 -- change with the compiler versions, we need a more reliable

496 -- "likely" primitive to control branch predication.

497 return $ case x > 0x7f of

498 False -> ParserD.Done 0 $ unsafeChr $ fromIntegral x

499 True ->

500 let (Tuple' sv cp) = decode0 table x

501 in case sv of

502 12 ->

503 let msg = prefix

504 ++ "Invalid first UTF8 byte" ++ show x

505 in handleError msg False

506 0 -> error $ prefix ++ "unreachable state"

507 _ -> ParserD.Continue 0 (UTF8CharDecoding sv cp)

508

509 step' table (UTF8CharDecoding statePtr codepointPtr) x = return $

510 let (Tuple' sv cp) = decode1 table statePtr codepointPtr x

511 in case sv of

512 0 -> ParserD.Done 0 $ unsafeChr cp

513 12 ->

514 let msg = prefix

515 ++ "Invalid subsequent UTF8 byte"

516 ++ show x

517 ++ "in state"

518 ++ show statePtr

519 ++ "accumulated value"

520 ++ show codepointPtr

521 in handleError msg True

522 _ -> ParserD.Continue 0 (UTF8CharDecoding sv cp)

523

524 {-# INLINE extract #-}

525 extract UTF8CharDecodeInit = error $ prefix ++ "Not enough input"

526 extract (UTF8CharDecoding _ _) =

527 case cfm of

528 ErrorOnCodingFailure ->

529 return $ ParserD.Error $ prefix ++ "Not enough input"

530 TransliterateCodingFailure ->

531 return (ParserD.Done 0 replacementChar)

532 -- XXX We shouldn't error out here. There is no way to represent an

533 -- empty parser result unless we return a "Maybe" type.

534 DropOnCodingFailure -> error $ prefix ++ "Not enough input"

535

536-- XXX This should ideally accept a "CodingFailureMode" and perform appropriate

537-- error handling. This isn't possible now as "TransliterateCodingFailure"'s

538-- workflow requires backtracking 1 element. This can be revisited once "Fold"

539-- supports backtracking.

540{-# INLINE writeCharUtf8' #-}

541writeCharUtf8' :: MonadThrow m => Fold m Word8 Char

542writeCharUtf8' = ParserD.toFold (parseCharUtf8WithD ErrorOnCodingFailure)

543

544-- XXX The initial idea was to have "parseCharUtf8" and offload the error

545-- handling to another parser. So, say we had "parseCharUtf8'",

546--

547-- >>> parseCharUtf8Smart = parseCharUtf8' <|> Parser.fromPure replacementChar

548--

549-- But unfortunately parseCharUtf8Smart used in conjunction with "parseMany" -

550-- that is "parseMany parseCharUtf8Smart" on a stream causes the heap to

551-- overflow. Even a heap size of 500 MB was not sufficient.

552--

553-- This needs to be investigated futher.

554{-# INLINE parseCharUtf8With #-}

555parseCharUtf8With ::

556 MonadCatch m => CodingFailureMode -> Parser.Parser m Word8 Char

557parseCharUtf8With = ParserD.toParserK . parseCharUtf8WithD

558

559-- XXX write it as a parser and use parseMany to decode a stream, need to check

560-- if that preserves the same performance. Or we can use a resumable parser

561-- that parses a chunk at a time.

562--

563-- XXX Implement this in terms of decodeUtf8Either. Need to make sure that

564-- decodeUtf8Either preserves the performance characterstics.

565--

566{-# INLINE_NORMAL decodeUtf8WithD #-}

567decodeUtf8WithD :: Monad m

568 => CodingFailureMode -> D.Stream m Word8 -> D.Stream m Char

569decodeUtf8WithD cfm (D.Stream step state) =

570 D.Stream (step' utf8d) (UTF8DecodeInit state)

571

572 where

573

574 prefix = "Streamly.Internal.Data.Stream.StreamD.decodeUtf8With: "

575

576 {-# INLINE handleError #-}

577 handleError e s =

578 case cfm of

579 ErrorOnCodingFailure -> error e

580 TransliterateCodingFailure -> YieldAndContinue replacementChar s

581 DropOnCodingFailure -> s

582

583 {-# INLINE handleUnderflow #-}

584 handleUnderflow =

585 case cfm of

586 ErrorOnCodingFailure -> error $ prefix ++ "Not enough input"

587 TransliterateCodingFailure -> YieldAndContinue replacementChar Done

588 DropOnCodingFailure -> Done

589

590 {-# INLINE_LATE step' #-}

591 step' _ gst (UTF8DecodeInit st) = do

592 r <- step (adaptState gst) st

593 return $ case r of

594 Yield x s -> Skip (UTF8DecodeInit1 s x)

595 Skip s -> Skip (UTF8DecodeInit s)

596 Stop -> Skip Done

597

598 step' _ _ (UTF8DecodeInit1 st x) = do

599 -- Note: It is important to use a ">" instead of a "<=" test

600 -- here for GHC to generate code layout for default branch

601 -- prediction for the common case. This is fragile and might

602 -- change with the compiler versions, we need a more reliable

603 -- "likely" primitive to control branch predication.

604 case x > 0x7f of

605 False ->

606 return $ Skip $ YieldAndContinue

607 (unsafeChr (fromIntegral x))

608 (UTF8DecodeInit st)

609 -- Using a separate state here generates a jump to a

610 -- separate code block in the core which seems to perform

611 -- slightly better for the non-ascii case.

612 True -> return $ Skip $ UTF8DecodeFirst st x

613

614 -- XXX should we merge it with UTF8DecodeInit1?

615 step' table _ (UTF8DecodeFirst st x) = do

616 let (Tuple' sv cp) = decode0 table x

617 return $

618 case sv of

619 12 ->

620 let msg = prefix ++ "Invalid first UTF8 byte " ++ show x

621 in Skip $ handleError msg (UTF8DecodeInit st)

622 0 -> error "unreachable state"

623 _ -> Skip (UTF8Decoding st sv cp)

624

625 -- We recover by trying the new byte x as a starter of a new codepoint.

626 -- XXX need to use the same recovery in array decoding routine as well

627 step' table gst (UTF8Decoding st statePtr codepointPtr) = do

628 r <- step (adaptState gst) st

629 case r of

630 Yield x s -> do

631 let (Tuple' sv cp) = decode1 table statePtr codepointPtr x

632 return $ case sv of

633 0 -> Skip $ YieldAndContinue

634 (unsafeChr cp) (UTF8DecodeInit s)

635 12 ->

636 let msg = prefix

637 ++ "Invalid subsequent UTF8 byte "

638 ++ show x

639 ++ " in state "

640 ++ show statePtr

641 ++ " accumulated value "

642 ++ show codepointPtr

643 in Skip $ handleError msg (UTF8DecodeInit1 s x)

644 _ -> Skip (UTF8Decoding s sv cp)

645 Skip s -> return $

646 Skip (UTF8Decoding s statePtr codepointPtr)

647 Stop -> return $ Skip handleUnderflow

648

649 step' _ _ (YieldAndContinue c s) = return $ Yield c s

650 step' _ _ Done = return Stop

651

652{-# INLINE decodeUtf8D #-}

653decodeUtf8D :: Monad m => D.Stream m Word8 -> D.Stream m Char

654decodeUtf8D = decodeUtf8WithD TransliterateCodingFailure

655

656-- | Decode a UTF-8 encoded bytestream to a stream of Unicode characters.

657-- Any invalid codepoint encountered is replaced with the unicode replacement

658-- character.

659--

660-- /Since: 0.7.0 ("Streamly.Data.Unicode.Stream")/

661--

662-- /Since: 0.8.0 (Lenient Behaviour)/

663{-# INLINE decodeUtf8 #-}

664decodeUtf8 :: (Monad m, IsStream t) => t m Word8 -> t m Char

665decodeUtf8 = fromStreamD . decodeUtf8D . toStreamD

666

667{-# INLINE decodeUtf8D' #-}

668decodeUtf8D' :: Monad m => D.Stream m Word8 -> D.Stream m Char

669decodeUtf8D' = decodeUtf8WithD ErrorOnCodingFailure

670

671-- | Decode a UTF-8 encoded bytestream to a stream of Unicode characters.

672-- The function throws an error if an invalid codepoint is encountered.

673--

674-- @since 0.8.0

675{-# INLINE decodeUtf8' #-}

676decodeUtf8' :: (Monad m, IsStream t) => t m Word8 -> t m Char

677decodeUtf8' = fromStreamD . decodeUtf8D' . toStreamD

678

679{-# INLINE decodeUtf8D_ #-}

680decodeUtf8D_ :: Monad m => D.Stream m Word8 -> D.Stream m Char

681decodeUtf8D_ = decodeUtf8WithD DropOnCodingFailure

682

683-- | Decode a UTF-8 encoded bytestream to a stream of Unicode characters.

684-- Any invalid codepoint encountered is dropped.

685--

686-- @since 0.8.0

687{-# INLINE decodeUtf8_ #-}

688decodeUtf8_ :: (Monad m, IsStream t) => t m Word8 -> t m Char

689decodeUtf8_ = fromStreamD . decodeUtf8D_ . toStreamD

690

691-- | Same as 'decodeUtf8'

692--

693{-# DEPRECATED decodeUtf8Lax "Please use 'decodeUtf8' instead" #-}

694{-# INLINE decodeUtf8Lax #-}

695decodeUtf8Lax :: (IsStream t, Monad m) => t m Word8 -> t m Char

696decodeUtf8Lax = decodeUtf8

697

698-------------------------------------------------------------------------------

699-- Decoding Array Streams

700-------------------------------------------------------------------------------

701

702#ifndef __GHCJS__

703{-# ANN type FlattenState Fuse #-}

704#endif

705data FlattenState s a

706 = OuterLoop s !(Maybe (DecodeState, CodePoint))

707 | InnerLoopDecodeInit s (MutableByteArray a) !Int !Int

708 | InnerLoopDecodeFirst s (MutableByteArray a) !Int !Int Word8

709 | InnerLoopDecoding s (MutableByteArray a) !Int !Int

710 !DecodeState !CodePoint

711 | YAndC !Char (FlattenState s a) -- These constructors can be

712 -- encoded in the UTF8DecodeState

713 -- type, I prefer to keep these

714 -- flat even though that means

715 -- coming up with new names

716 | D

717

718-- The normal decodeUtf8 above should fuse with flattenArrays

719-- to create this exact code but it doesn't for some reason, as of now this

720-- remains the fastest way I could figure out to decodeUtf8.

721--

722-- XXX Add Proper error messages

723{-# INLINE_NORMAL decodeUtf8ArraysWithD #-}

724decodeUtf8ArraysWithD ::

725 MonadIO m

726 => CodingFailureMode

727 -> D.Stream m (A.Array Word8)

728 -> D.Stream m Char

729decodeUtf8ArraysWithD cfm (D.Stream step state) =

730 D.Stream (step' utf8d) (OuterLoop state Nothing)

731 where

732 {-# INLINE transliterateOrError #-}

733 transliterateOrError e s =

734 case cfm of

735 ErrorOnCodingFailure -> error e

736 TransliterateCodingFailure -> YAndC replacementChar s

737 DropOnCodingFailure -> s

738 {-# INLINE inputUnderflow #-}

739 inputUnderflow =

740 case cfm of

741 ErrorOnCodingFailure ->

742 error $

743 show "Streamly.Internal.Data.Stream.StreamD."

744 ++ "decodeUtf8ArraysWith: Input Underflow"

745 TransliterateCodingFailure -> YAndC replacementChar D

746 DropOnCodingFailure -> D

747 {-# INLINE_LATE step' #-}

748 step' _ gst (OuterLoop st Nothing) = do

749 r <- step (adaptState gst) st

750 return $

751 case r of

752 Yield A.Array {..} s ->

753 Skip (InnerLoopDecodeInit s arrContents arrStart arrEnd)

754 Skip s -> Skip (OuterLoop s Nothing)

755 Stop -> Skip D

756 step' _ gst (OuterLoop st dst@(Just (ds, cp))) = do

757 r <- step (adaptState gst) st

758 return $

759 case r of

760 Yield A.Array {..} s ->

761 Skip (InnerLoopDecoding s arrContents arrStart arrEnd ds cp)

762 Skip s -> Skip (OuterLoop s dst)

763 Stop -> Skip inputUnderflow

764 step' _ _ (InnerLoopDecodeInit st _ p end)

765 | p == end = do

766 return $ Skip $ OuterLoop st Nothing

767 step' _ _ (InnerLoopDecodeInit st contents p end) = do

768 x <- liftIO $ peekWith contents p

769 -- Note: It is important to use a ">" instead of a "<=" test here for

770 -- GHC to generate code layout for default branch prediction for the

771 -- common case. This is fragile and might change with the compiler

772 -- versions, we need a more reliable "likely" primitive to control

773 -- branch predication.

774 case x > 0x7f of

775 False ->

776 return $ Skip $ YAndC

777 (unsafeChr (fromIntegral x))

778 (InnerLoopDecodeInit st contents (p + 1) end)

779 -- Using a separate state here generates a jump to a separate code

780 -- block in the core which seems to perform slightly better for the

781 -- non-ascii case.

782 True -> return $ Skip $ InnerLoopDecodeFirst st contents p end x

783

784 step' table _ (InnerLoopDecodeFirst st contents p end x) = do

785 let (Tuple' sv cp) = decode0 table x

786 return $

787 case sv of

788 12 ->

789 Skip $

790 transliterateOrError

791 (

792 "Streamly.Internal.Data.Stream.StreamD."

793 ++ "decodeUtf8ArraysWith: Invalid UTF8"

794 ++ " codepoint encountered"

795 )

796 (InnerLoopDecodeInit st contents (p + 1) end)

797 0 -> error "unreachable state"

798 _ -> Skip (InnerLoopDecoding st contents (p + 1) end sv cp)

799 step' _ _ (InnerLoopDecoding st _ p end sv cp)

800 | p == end = return $ Skip $ OuterLoop st (Just (sv, cp))

801 step' table _ (InnerLoopDecoding st contents p end statePtr codepointPtr) = do

802 x <- liftIO $ peekWith contents p

803 let (Tuple' sv cp) = decode1 table statePtr codepointPtr x

804 return $

805 case sv of

806 0 ->

807 Skip $

808 YAndC

809 (unsafeChr cp)

810 (InnerLoopDecodeInit st contents (p + 1) end)

811 12 ->

812 Skip $

813 transliterateOrError

814 (

815 "Streamly.Internal.Data.Stream.StreamD."

816 ++ "decodeUtf8ArraysWith: Invalid UTF8"

817 ++ " codepoint encountered"

818 )

819 (InnerLoopDecodeInit st contents (p + 1) end)

820 _ ->

821 Skip

822 (InnerLoopDecoding st contents (p + 1) end sv cp)

823 step' _ _ (YAndC c s) = return $ Yield c s

824 step' _ _ D = return Stop

825

826{-# INLINE decodeUtf8ArraysD #-}

827decodeUtf8ArraysD ::

828 MonadIO m

829 => D.Stream m (A.Array Word8)

830 -> D.Stream m Char

831decodeUtf8ArraysD = decodeUtf8ArraysWithD TransliterateCodingFailure

832

833-- |

834--

835-- /Pre-release/

836{-# INLINE decodeUtf8Arrays #-}

837decodeUtf8Arrays ::

838 (MonadIO m, IsStream t) => t m (Array Word8) -> t m Char

839decodeUtf8Arrays =

840 fromStreamD . decodeUtf8ArraysD . toStreamD

841

842{-# INLINE decodeUtf8ArraysD' #-}

843decodeUtf8ArraysD' ::

844 MonadIO m

845 => D.Stream m (A.Array Word8)

846 -> D.Stream m Char

847decodeUtf8ArraysD' = decodeUtf8ArraysWithD ErrorOnCodingFailure

848

849-- |

850--

851-- /Pre-release/

852{-# INLINE decodeUtf8Arrays' #-}

853decodeUtf8Arrays' :: (MonadIO m, IsStream t) => t m (Array Word8) -> t m Char

854decodeUtf8Arrays' = fromStreamD . decodeUtf8ArraysD' . toStreamD

855

856{-# INLINE decodeUtf8ArraysD_ #-}

857decodeUtf8ArraysD_ ::

858 MonadIO m

859 => D.Stream m (A.Array Word8)

860 -> D.Stream m Char

861decodeUtf8ArraysD_ = decodeUtf8ArraysWithD DropOnCodingFailure

862

863-- |

864--

865-- /Pre-release/

866{-# INLINE decodeUtf8Arrays_ #-}

867decodeUtf8Arrays_ ::

868 (MonadIO m, IsStream t) => t m (Array Word8) -> t m Char

869decodeUtf8Arrays_ =

870 fromStreamD . decodeUtf8ArraysD_ . toStreamD

871

872-------------------------------------------------------------------------------

873-- Encoding Unicode (UTF-8) Characters

874-------------------------------------------------------------------------------

875

876data WList = WCons !Word8 !WList | WNil

877

878-- UTF-8 primitives, Lifted from GHC.IO.Encoding.UTF8.

879

880{-# INLINE ord2 #-}

881ord2 :: Char -> WList

882ord2 c = assert (n >= 0x80 && n <= 0x07ff) (WCons x1 (WCons x2 WNil))

883 where

884 n = ord c

885 x1 = fromIntegral $ (n `shiftR` 6) + 0xC0

886 x2 = fromIntegral $ (n .&. 0x3F) + 0x80

887

888{-# INLINE ord3 #-}

889ord3 :: Char -> WList

890ord3 c = assert (n >= 0x0800 && n <= 0xffff) (WCons x1 (WCons x2 (WCons x3 WNil)))

891 where

892 n = ord c

893 x1 = fromIntegral $ (n `shiftR` 12) + 0xE0

894 x2 = fromIntegral $ ((n `shiftR` 6) .&. 0x3F) + 0x80

895 x3 = fromIntegral $ (n .&. 0x3F) + 0x80

896

897{-# INLINE ord4 #-}

898ord4 :: Char -> WList

899ord4 c = assert (n >= 0x10000) (WCons x1 (WCons x2 (WCons x3 (WCons x4 WNil))))

900 where

901 n = ord c

902 x1 = fromIntegral $ (n `shiftR` 18) + 0xF0

903 x2 = fromIntegral $ ((n `shiftR` 12) .&. 0x3F) + 0x80

904 x3 = fromIntegral $ ((n `shiftR` 6) .&. 0x3F) + 0x80

905 x4 = fromIntegral $ (n .&. 0x3F) + 0x80

906

907{-# INLINE_NORMAL readCharUtf8With #-}

908readCharUtf8With :: Monad m => WList -> Unfold m Char Word8

909readCharUtf8With surr = Unfold step inject

910

911 where

912

913 inject c =

914 return $ case ord c of

915 x | x <= 0x7F -> fromIntegral x `WCons` WNil

916 | x <= 0x7FF -> ord2 c

917 | x <= 0xFFFF -> if isSurrogate c then surr else ord3 c

918 | otherwise -> ord4 c

919

920 {-# INLINE_LATE step #-}

921 step WNil = return Stop

922 step (WCons x xs) = return $ Yield x xs

923

924{-# INLINE_NORMAL readCharUtf8' #-}

925readCharUtf8' :: Monad m => Unfold m Char Word8

926readCharUtf8' =

927 readCharUtf8With $

928 error "Streamly.Internal.Unicode.readCharUtf8': Encountered a surrogate"

929

930-- More yield points improve performance, but I am not sure if they can cause

931-- too much code bloat or some trouble with fusion. So keeping only two yield

932-- points for now, one for the ascii chars (fast path) and one for all other

933-- paths (slow path).

934{-# INLINE_NORMAL encodeUtf8D' #-}

935encodeUtf8D' :: Monad m => D.Stream m Char -> D.Stream m Word8

936encodeUtf8D' = D.unfoldMany readCharUtf8'

937

938-- | Encode a stream of Unicode characters to a UTF-8 encoded bytestream. When

939-- any invalid character (U+D800-U+D8FF) is encountered in the input stream the

940-- function errors out.

941--

942-- @since 0.8.0

943{-# INLINE encodeUtf8' #-}

944encodeUtf8' :: (Monad m, IsStream t) => t m Char -> t m Word8

945encodeUtf8' = fromStreamD . encodeUtf8D' . toStreamD

946

947{-# INLINE_NORMAL readCharUtf8 #-}

948readCharUtf8 :: Monad m => Unfold m Char Word8

949readCharUtf8 = readCharUtf8With $ WCons 239 (WCons 191 (WCons 189 WNil))

950

951-- | See section "3.9 Unicode Encoding Forms" in

952-- https://www.unicode.org/versions/Unicode13.0.0/UnicodeStandard-13.0.pdf

953--

954{-# INLINE_NORMAL encodeUtf8D #-}

955encodeUtf8D :: Monad m => D.Stream m Char -> D.Stream m Word8

956encodeUtf8D = D.unfoldMany readCharUtf8

957

958-- | Encode a stream of Unicode characters to a UTF-8 encoded bytestream. Any

959-- Invalid characters (U+D800-U+D8FF) in the input stream are replaced by the

960-- Unicode replacement character U+FFFD.

961--

962-- /Since: 0.7.0 ("Streamly.Data.Unicode.Stream")/

963--

964-- /Since: 0.8.0 (Lenient Behaviour)/

965{-# INLINE encodeUtf8 #-}

966encodeUtf8 :: (Monad m, IsStream t) => t m Char -> t m Word8

967encodeUtf8 = fromStreamD . encodeUtf8D . toStreamD

968

969{-# INLINE_NORMAL readCharUtf8_ #-}

970readCharUtf8_ :: Monad m => Unfold m Char Word8

971readCharUtf8_ = readCharUtf8With WNil

972

973{-# INLINE_NORMAL encodeUtf8D_ #-}

974encodeUtf8D_ :: Monad m => D.Stream m Char -> D.Stream m Word8

975encodeUtf8D_ = D.unfoldMany readCharUtf8_

976

977-- | Encode a stream of Unicode characters to a UTF-8 encoded bytestream. Any

978-- Invalid characters (U+D800-U+D8FF) in the input stream are dropped.

979--

980-- @since 0.8.0

981{-# INLINE encodeUtf8_ #-}

982encodeUtf8_ :: (Monad m, IsStream t) => t m Char -> t m Word8

983encodeUtf8_ = fromStreamD . encodeUtf8D_ . toStreamD

984

985-- | Same as 'encodeUtf8'

986--

987{-# DEPRECATED encodeUtf8Lax "Please use 'encodeUtf8' instead" #-}

988{-# INLINE encodeUtf8Lax #-}

989encodeUtf8Lax :: (IsStream t, Monad m) => t m Char -> t m Word8

990encodeUtf8Lax = encodeUtf8

991

992-------------------------------------------------------------------------------

993-- Decoding string literals

994-------------------------------------------------------------------------------

995

996-- | Read UTF-8 encoded bytes as chars from an 'Addr#' until a 0 byte is

997-- encountered, the 0 byte is not included in the stream.

998--

999-- /Unsafe:/ The caller is responsible for safe addressing.

1000--

1001-- Note that this is completely safe when reading from Haskell string

1002-- literals because they are guaranteed to be NULL terminated:

1003--

1004-- >>> Stream.fold Fold.toList (Unicode.fromStr# "Haskell"#)

1005-- "Haskell"

1006--

1007{-# INLINE fromStr# #-}

1008fromStr# :: MonadIO m => Addr# -> Stream m Char

1009fromStr# addr = decodeUtf8 $ Stream.fromByteStr# addr

1010

1011-------------------------------------------------------------------------------

1012-- Encode streams of containers

1013-------------------------------------------------------------------------------

1014

1015-- | Encode a container to @Array Word8@ provided an unfold to covert it to a

1016-- Char stream and an encoding function.

1017--

1018-- /Internal/

1019{-# INLINE encodeObject #-}

1020encodeObject :: MonadIO m =>

1021 (Stream m Char -> Stream m Word8)

1022 -> Unfold m a Char

1023 -> a

1024 -> m (Array Word8)

1025encodeObject encode u = S.fold Array.write . encode . S.unfold u

1026

1027-- | Encode a stream of container objects using the supplied encoding scheme.

1028-- Each object is encoded as an @Array Word8@.

1029--

1030-- /Internal/

1031{-# INLINE encodeObjects #-}

1032encodeObjects :: (MonadIO m, IsStream t) =>

1033 (Stream m Char -> Stream m Word8)

1034 -> Unfold m a Char

1035 -> t m a

1036 -> t m (Array Word8)

1037encodeObjects encode u = adapt . Serial.mapM (encodeObject encode u) . adapt

1038

1039-- | Encode a stream of 'String' using the supplied encoding scheme. Each

1040-- string is encoded as an @Array Word8@.

1041--

1042-- @since 0.8.0

1043{-# INLINE encodeStrings #-}

1044encodeStrings :: (MonadIO m, IsStream t) =>

1045 (Stream m Char -> Stream m Word8) -> t m String -> t m (Array Word8)

1046encodeStrings encode = encodeObjects encode Unfold.fromList

1047

1048{-

1049-------------------------------------------------------------------------------

1050-- Utility operations on strings

1051-------------------------------------------------------------------------------

1052

1053strip :: IsStream t => t m Char -> t m Char

1054strip = undefined

1055

1056stripTail :: IsStream t => t m Char -> t m Char

1057stripTail = undefined

1058-}

1059

1060-- | Remove leading whitespace from a string.

1061--

1062-- > stripHead = S.dropWhile isSpace

1063--

1064-- /Pre-release/

1065{-# INLINE stripHead #-}

1066stripHead :: (Monad m, IsStream t) => t m Char -> t m Char

1067stripHead = S.dropWhile isSpace

1068

1069-- | Fold each line of the stream using the supplied 'Fold'

1070-- and stream the result.

1071--

1072-- >>> Stream.toList $ lines Fold.toList (Stream.fromList "lines\nthis\nstring\n\n\n")

1073-- ["lines","this","string","",""]

1074--

1075-- > lines = S.splitOnSuffix (== '\n')

1076--

1077-- /Pre-release/

1078{-# INLINE lines #-}

1079lines :: (Monad m, IsStream t) => Fold m Char b -> t m Char -> t m b

1080lines = S.splitOnSuffix (== '\n')

1081

1082#if !MIN_VERSION_base(4,17,0)

1083foreign import ccall unsafe "u_iswspace"

1084 iswspace :: Int -> Int

1085#endif

1086

1087-- | Code copied from base/Data.Char to INLINE it

1088{-# INLINE isSpace #-}

1089isSpace :: Char -> Bool

1090isSpace c

1091 | uc <= 0x377 = uc == 32 || uc - 0x9 <= 4 || uc == 0xa0

1092#if MIN_VERSION_base(4,17,0)

1093 | otherwise = generalCategory c == Space

1094#else

1095 | otherwise = iswspace (ord c) /= 0

1096#endif

1097 where

1098 uc = fromIntegral (ord c) :: Word

1099

1100-- | Fold each word of the stream using the supplied 'Fold'

1101-- and stream the result.

1102--

1103-- >>> Stream.toList $ words Fold.toList (Stream.fromList "fold these words")

1104-- ["fold","these","words"]

1105--

1106-- > words = S.wordsBy isSpace

1107--

1108-- /Pre-release/

1109{-# INLINE words #-}

1110words :: (Monad m, IsStream t) => Fold m Char b -> t m Char -> t m b

1111words = S.wordsBy isSpace

1112

1113-- | Unfold a stream to character streams using the supplied 'Unfold'

1114-- and concat the results suffixing a newline character @\\n@ to each stream.

1115--

1116-- @

1117-- unlines = Stream.interposeSuffix '\n'

1118-- unlines = Stream.intercalateSuffix Unfold.fromList "\n"

1119-- @

1120--

1121-- /Pre-release/

1122{-# INLINE unlines #-}

1123unlines :: (MonadIO m, IsStream t) => Unfold m a Char -> t m a -> t m Char

1124unlines = S.interposeSuffix '\n'

1125

1126-- | Unfold the elements of a stream to character streams using the supplied

1127-- 'Unfold' and concat the results with a whitespace character infixed between

1128-- the streams.

1129--

1130-- @

1131-- unwords = Stream.interpose ' '

1132-- unwords = Stream.intercalate Unfold.fromList " "

1133-- @

1134--

1135-- /Pre-release/

1136{-# INLINE unwords #-}

1137unwords :: (MonadIO m, IsStream t) => Unfold m a Char -> t m a -> t m Char

1138unwords = S.interpose ' '