haskell / haskell/text

Decoupling byte-level encoding

Open
#535 20 comments 0 reactions 0 assignees View on GitHub
Dominant language
Haskell
Stars
421
Forks
163
PR merge metrics
No merged PRs in 30d

Description

When writing a JSON parser (GaloisInc/json#17) I needed some way to decode UTF-8 and to my dismay I found all existing solutions do not fit my expectations:
- `GHC.Encoding.UTF8` and `GHC.IO.Encoding` are `IO`-based and I don't want that in a parser;
- `Data.Text.Internal.Encoding.Utf8`, while pure, appears to both return `Reject` as an error and has a rather complex interface;
- `Data.Text.Encoding.*` and `Data.Text.Lazy.Encoding.*` are already parsers themselves, too high-level for this task;
- `utf-string`'s `Codec.Binary.UTF8.String` consumes and returns lists, so it isn't parser-compatible.

I decided to handroll the UTF-8 decoding, which allowed me to categorize the errors (see [Encoding.Mixed.Error](https://github.com/BurningWitness/json/blob/ea8d0c80/src/Encoding/Mixed/Error.hs#L7-L51)) and resulted in a lot of code on the parser side that has little to do with consuming bytes per se (see [Codec.Web.JSON.Parse.String](https://github.com/BurningWitness/json/blob/ea8d0c80/src/Codec/Web/JSON/Parse/String.hs#L64-L286)).

However the code I wrote can instead be generalized to:

```haskell
-- Assume Error is Encoding.Mixed.Error.Error

data UTF8 a = UTF8_1 a
| Part_2 (Word8 -> UTF8_2 a)
| Part_3_1 (Word8 -> Part_3_1 a)
| Part_4_1 (Word8 -> Part_4_1 a)
| Error_1 Error

data UTF8_2 a = UTF8_2 a
| Error_2 Error

data Part_3_1 a = Part_3_2 (Word8 -> UTF8_3 a)
| Error_3_1 Error

data UTF8_3 a = UTF8_3 a
| Error_3_2 Error

data Part_4_1 a = Part_4_2 (Word8 -> Part_4_2 a)
| Error_4_1 Error

data Part_4_2 a = Part_4_3 (Word8 -> UTF8_4 a)
| Error_4_2 Error

data UTF8_4 a = UTF8_4 a
| Error_4_3 Error

newtype Conv1 a = Conv1 (Word8 -> a)
newtype Conv2 a = Conv2 (Word8 -> Word8 -> a)
newtype Conv3 a = Conv3 (Word8 -> Word8 -> Word8 -> a)
newtype Conv4 a = Conv4 (Word8 -> Word8 -> Word8 -> Word8 -> a)

utf8 :: Conv1 a -> Conv2 a -> Conv3 a -> Conv4 a -> Word8 -> UTF8 a
utf8 = -- I'm omitting the implementation, but it's only 50 lines long
```

Parsing then is simply unwrapping `UTF8`. This decouples character validation and conversion, the only part of decoding left is ensuring only the maximal subpart of an ill-formed sequence is consumed, which is the responsibility of the parser.

---

My proposal is creating a separate package with a focus specifically on decoding/encoding UTF-8/UTF-16/UTF-32 on byte-level. Then `text` can drop some internal modules in favor of a simpler common interface.

This proposal is however naive: I do not know whether GHC can inline these datatypes reliably or, indeed, at all. Based on my cursory reading of the [Secrets of the Glasgow Haskell Compiler inliner](https://www.microsoft.com/en-us/research/wp-content/uploads/2002/07/inline.pdf) paper it should, as each of these expressions is *trivial*.

This doesn't clash with the issue of *GHC's many UTF-8 implementations* (outlined in [`GHC.Encoding.UTF8`](https://hackage.haskell.org/package/base-4.18.0.0/docs/src/GHC.Encoding.UTF8.html)) as all other algorithms are in `IO`.

Other concerns:
- `text` is a core library, so I assume an extra dependency can't just be added on a whim;
- Package named [`utf`](https://hackage.haskell.org/package/utf) already exists and is deprecated. I don't know how hard reclaiming deprecated packages is.

Contributor guide

No contributing guide indexed for this repository

Research direction

Start by reading the referenced GHC.Encoding.UTF8 and Data.Text.Internal.Encoding.Utf8 implementations, then compare the linked json parser code in Encoding.Mixed.Error and Codec.Web.JSON.Parse.String. The proposal is complete only after the package boundary, API, dependency approach, and implementation plan are agreed; this issue leaves those decisions open.

Written by the indexing model from the issue text.

Assessment

Tech stack
haskell
Domain
internationalization
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
20/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.