33 Text and encodings — strings, fmt, utf8, codec, hash

33 Text and encodings — `strings`, `fmt`, `utf8`, `codec`, `hash`

What to know first

chapter 9, Sequences · a string is not a type but slice u8

chapter 32, A map of the standard library · the caller’s buffer, failure as a value, all or nothing

Looking back

How did chapter 9 answer the question “is there no separate string type”?

A. A string literal is slice u8, and how many characters it has or whether it is valid UTF-8 is answered by library ops, not by the type. It is a choice to avoid the defects that arise the moment bytes and characters are treated as the same. This chapter tours that library.

The need for this chapter, and its context

Almost every program cuts, searches and joins strings, turns numbers into text, and moves bytes into hex or base64. In C, null-terminated strings and overflowing buffers follow all of these. Lowent’s text modules do not allocate, return results as views or into the caller’s buffer, and report failure as values. The shared conventions of chapter 32 show up here most often, so this is the first group of modules in the tour.

By the end of this chapter

You will learn to handle strings as views with strings and to assemble text into the caller’s buffer with fmt. You will see that utf8 reports invalid bytes as none without replacement characters, and what codec’s hex and base64 and hash’s three kinds of hash (choosing slots, detecting damage, SHA-256) are each for. You will also see where the other text modules (strbuf, utf16, unicode, regex) fit.

The questions this chapter answers

Isn’t writing guard is_some every time you call fmt.put_str tedious?

33.1 Cut, find, assemble#

examples/ch33/request.low

module request .
rem run: main

use strings .
use fmt .

proc main input out cap io . input al cap allocator . output u8 . effects io alloc .
do
  let line slice u8 be "GET /users/42 HTTP/1.1" .
  guard strings.starts_with line "GET " . else return 1 .
  let rest slice u8 be strings.remove_prefix line "GET " .
  let sp option u64 be strings.find rest " " 0 .
  guard is_some sp . else return 2 .
  let path slice u8 be subslice rest 0 (some_value sp) .
  let g option mut slice u8 be alloc_bytes al capacity 64 .
  guard is_some g . else return 3 .
  let buf mut slice u8 be some_value g .
  let p1 option u64 be fmt.put_str buf 0 "path=" .
  guard is_some p1 . else return 4 .
  let p2 option u64 be fmt.put_str buf (some_value p1) path .
  guard is_some p2 . else return 4 .
  let p3 option u64 be fmt.put_str buf (some_value p2) " len=" .
  guard is_some p3 . else return 4 .
  let p4 option u64 be fmt.put_u64 buf (some_value p3) (len path) .
  guard is_some p4 . else return 4 .
  let p5 option u64 be fmt.put_nl buf (some_value p4) .
  guard is_some p5 . else return 4 .
  let w u64 be write_out out 1 (subslice buf 0 (some_value p5)) .
  return 0 .
end

Output

$ lowentc --run main request.low
path=/users/42 len=9
main() = 0

strings.starts_with, strings.remove_prefix and strings.find all take slice u8. What remove_prefix and subslice return is not a new buffer but a view pointing at the original bytes. There is no copy.
fmt.put_str buf pos s and fmt.put_u64 buf pos n write into the caller’s buffer buf from position pos, and give the next position to write as an option. If there is not enough room, not one character is written and it is none.
When assembly is done, subslice buf 0 end is written to standard output.

The buffer was obtained with cap allocator, so alloc shows in the head. strings and fmt themselves do not allocate. Where the buffer comes from is the caller’s business.

Q. Isn’t writing guard is_some every time you call fmt.put_str tedious?

A. It is. In exchange, the moment room runs out it stops right there, and half-written output never goes out. To take a generous buffer and reduce repetition, use strbuf. strbuf.append appends to an owned buffer and gives failure as a result. If strings is reading (views), strbuf is writing.

33.2 UTF-8 — no replacement characters#

examples/ch33/chars.low

module chars .
rem run: characters [236,149,136,235,133,149]
rem run: characters [97,98,99]
rem run: characters [236,149]
rem run: first_char [236,149,136,235,133,149]

use utf8 .

fn characters input s slice u8 . output u64 .
do
  let n option u64 be utf8.count_chars s .
  guard is_some n . else return 999 .
  return some_value n .
end

fn first_char input s slice u8 . output u64 .
do
  let c option u64 be utf8.decode s 0 .
  guard is_some c . else return 0 .
  return some_value c .
end

Output

$ lowentc --run characters chars.low [236,149,136,235,133,149]
characters([236,149,136,235,133,149]) = 2
  arg0 (written) = [236,149,136,235,133,149]
$ lowentc --run characters chars.low [97,98,99]
characters([97,98,99]) = 3
  arg0 (written) = [97,98,99]
$ lowentc --run characters chars.low [236,149]
characters([236,149]) = 999
  arg0 (written) = [236,149]
$ lowentc --run first_char chars.low [236,149,136,235,133,149]
first_char([236,149,136,235,133,149]) = 50504
  arg0 (written) = [236,149,136,235,133,149]

utf8.count_chars counts characters. The Korean “안녕” is 6 bytes and 2 characters.
The truncated [236,149] is not valid UTF-8, so it is none, and the example returns 999.
utf8.decode s 0 gives the one character at position 0 as a code point. 50504 is U+C548, “안”.

Many libraries insert a replacement character (U+FFFD) when they meet invalid bytes and carry on. Then the fact that the input was broken is buried in the output. utf8 reports none. How to handle broken input is decided by the caller.

When exchanging values with the UTF-16 world (Windows APIs, Java, JavaScript), utf16 joins and splits surrogate pairs over slice u16. Unmatched pairs are none too. Tables asking whether something is a letter, digit, space or zero-width are in the unicode module. Those tables were extracted mechanically from Unicode data, because hand-picked judgements silently give false instead of an error in ranges they missed.

33.3 Hex and base64#

examples/ch33/hexout.low

module hexout .
rem run: main

use codec .

proc main input out cap io . input al cap allocator . output u8 . effects io alloc .
do
  let g option mut slice u8 be alloc_bytes al capacity 16 .
  guard is_some g . else return 1 .
  let dst mut slice u8 be some_value g .
  let n option u64 be codec.hex_enc "Lowent" dst .
  guard is_some n . else return 2 .
  let w u64 be write_out out 1 (subslice dst 0 (some_value n)) .
  let nl u64 be write_out out 1 "\n" .
  let small option u64 be codec.hex_enc "too long for eight" (subslice dst 0 8) .
  guard not (is_some small) . else return 3 .
  return 0 .
end

Output

$ lowentc --run main hexout.low
4c6f77656e74
main() = 0

codec.hex_enc src dst writes src as hex characters into dst and gives the number of bytes actually written. The result is the first n bytes, not all of dst. The six characters “Lowent” become the twelve characters 4c6f77656e74. Trying to encode 18 characters into 8 bytes of room gives none and writes nothing — all or nothing. hex_dec, b64_enc and b64_dec have the same shape.

A common misconception. Encoding is a kind of encryption

Hex and base64 are only ways of transcribing bytes as text; they keep no secrets. Anyone can reverse them. When secrecy is needed, use aead, which seals (chapter 36). codec and aead are different modules for the same reason as the charter’s “separate computation from authority” — different jobs do not get one name.

33.4 Hashes — three questions, three answers#

examples/ch33/codes.low

module codes .
rem run: checksum [104,101,108,108,111]
rem run: slot [104,101,108,108,111] 16

use hash .

fn checksum input data slice u8 . output u64 .
do
  return hash.crc data .
end

fn slot input key slice u8 . input nslots u64 . output u64 .
  requires gt nslots 0 .
do
  return hash.bucket_of key nslots .
end

Output

$ lowentc --run checksum codes.low [104,101,108,108,111]
checksum([104,101,108,108,111]) = 907060870
  arg0 (written) = [104,101,108,108,111]
$ lowentc --run slot codes.low [104,101,108,108,111] 16
slot([104,101,108,108,111], 16) = 11
  arg0 (written) = [104,101,108,108,111]

The hash module gives different hashes to different questions.

Question	op	Hash used
Which slot of a hash map does it go in	`of` · `bucket_of` · `bucket_mask`	FNV-1a — fast and even
Was it damaged in storage or transit	`crc` · `crc_ok`	CRC-32 — catches accidental bit errors
Did someone change it on purpose	`digest` · `digest_ok`	SHA-256 — collisions are hard to find

Table 33.1 — Questions the hash module answers

slot puts the key “hello” into slot 11 of 16. bucket_of picks the slot with the remainder mod, so the result is always smaller than the slot count (chapter 4), and so the index bounds check of the hash table is removed. Using a slot-choosing hash to prevent tampering, or a cryptographic hash to choose hash map slots, are both the wrong tool. The names separate the questions.

33.5 Regular expressions — no backtracking#

regex compiles a pattern once into a program (slice u64) and matches many inputs with the same program. The compiled result and the workspace are both the caller’s slices, so there is no allocation.

Common regex engines backtrack — at a fork they go down one path to the end and come back when stuck — so for some patterns and inputs time grows exponentially in input length (ReDoS). regex uses the Pike VM approach, advancing all forks together one step at a time, so time is proportional to input length. In exchange, features that require backtracking, such as backreferences, are absent. What it does not do is written at the top of the module document.

33.6 Common mistakes#

Counter-example. Trusting the result of removing a prefix without asking whether it was there

examples/ch33/mistake_removeprefix.low

module mistake_removeprefix .
rem run: path_len [71,69,84,32,47,97]
rem run: path_len [80,79,83,84,32,47,97]

use strings .

rem ✘ trusts the result of removing without asking whether the prefix was there --- if absent, the original comes back
fn path_len input line slice u8 . output u64 .
do
  let rest slice u8 be strings.remove_prefix line "GET " .
  return len rest .
end

Output

$ lowentc --run path_len mistake_removeprefix.low [71,69,84,32,47,97]
path_len([71,69,84,32,47,97]) = 2
  arg0 (written) = [71,69,84,32,47,97]
$ lowentc --run path_len mistake_removeprefix.low [80,79,83,84,32,47,97]
path_len([80,79,83,84,32,47,97]) = 7
  arg0 (written) = [80,79,83,84,32,47,97]

strings.remove_prefix returns the original unchanged when the prefix is absent. The design gives up reporting failure so that the result is always a usable view. So given POST /a, seven bytes come back as if “GET “ had been removed. Where the prefix must be present for the meaning to hold, ask with starts_with first.

examples/ch33/removeprefix_fixed.low

module removeprefix_fixed .
rem run: path_len [71,69,84,32,47,97]
rem run: path_len [80,79,83,84,32,47,97]

use strings .

rem ask first, and answer separately when it is absent
fn path_len input line slice u8 . output u64 .
do
  guard strings.starts_with line "GET " . else return 0 .
  return len (strings.remove_prefix line "GET ") .
end

Output

$ lowentc --run path_len removeprefix_fixed.low [71,69,84,32,47,97]
path_len([71,69,84,32,47,97]) = 2
  arg0 (written) = [71,69,84,32,47,97]
$ lowentc --run path_len removeprefix_fixed.low [80,79,83,84,32,47,97]
path_len([80,79,83,84,32,47,97]) = 0
  arg0 (written) = [80,79,83,84,32,47,97]

Counter-example. Treating the whole output buffer as the result of encoding

examples/ch33/mistake_wholedst.low

module mistake_wholedst .
rem run: sizes 0

use codec .

proc sizes input al cap allocator . output u64 . effects alloc .
do
  let g option mut slice u8 be alloc_bytes al capacity 16 .
  guard is_some g . else return 1 .
  let dst mut slice u8 be some_value g .
  let n option u64 be codec.hex_enc "Lowent" dst .
  guard is_some n . else return 2 .
  rem ✘ treating all of `dst` as the result adds four unwritten bytes --- 12 were written, the buffer is 16
  return add (mul (len dst) 100) (some_value n) .
end

Output

$ lowentc --run sizes mistake_wholedst.low 0
sizes(0) = 1612

codec.hex_enc writes 12 bytes into the 16-byte buffer and returns 12 (the result 1612 puts the buffer size 16 and the count 12 side by side). Using all of dst as the result tacks four unwritten bytes onto the end. It is the same mistake as discarding the return value of C’s sprintf and sending the whole buffer. The result is always subslice dst 0 n.

A common misconception. len is the number of characters, and a byte position is a character position

examples/ch33/bytes_not_chars.low

module bytes_not_chars .
rem run: lengths [236,149,136,235,133,149]
rem run: decode_at [236,149,136,235,133,149] 1
rem run: decode_at [236,149,136,235,133,149] 3

use utf8 .

rem `len` counts bytes --- "안녕" is 6 bytes, 2 characters
fn lengths input s slice u8 . output u64 .
do
  let chars option u64 be utf8.count_chars s .
  guard is_some chars . else return 0 .
  return add (mul (len s) 10) (some_value chars) .
end

rem no character starts at byte 1 --- the second character starts at byte 3
fn decode_at input s slice u8 . input at u64 . output u64 .
do
  let c option u64 be utf8.decode s at .
  guard is_some c . else return 0 .
  return some_value c .
end

Output

$ lowentc --run lengths bytes_not_chars.low [236,149,136,235,133,149]
lengths([236,149,136,235,133,149]) = 62
  arg0 (written) = [236,149,136,235,133,149]
$ lowentc --run decode_at bytes_not_chars.low [236,149,136,235,133,149] 1
decode_at([236,149,136,235,133,149], 1) = 0
  arg0 (written) = [236,149,136,235,133,149]
$ lowentc --run decode_at bytes_not_chars.low [236,149,136,235,133,149] 3
decode_at([236,149,136,235,133,149], 3) = 45397
  arg0 (written) = [236,149,136,235,133,149]

len counts bytes. “안녕” is 6 bytes and 2 characters, so lengths returns 62. Byte 1 lies in the middle of the first character, so utf8.decode returns none (0 here), and the second character “녕” (U+B155, 45397) starts at byte 3. To count or step through characters, use the ops of utf8; the number of columns a character takes on screen is yet another matter (chapter 37).

33.7 This chapter’s syntax at a glance#

Shape	Meaning	Why
`strings.starts_with s p` · `strings.find hay needle from`	ask · search (`option u64`)	on views — no copying
`strings.remove_prefix s p`	a view without the prefix — the original if absent	always a usable view, no failure
`fmt.put_str buf pos s` · `fmt.put_u64 buf pos n`	assemble into the caller’s buffer — next position as `option`	all or nothing
`utf8.count_chars s` · `utf8.decode s at`	character count · code point at that position	invalid input gives `none`, not a replacement character
`codec.hex_enc src dst` · `b64_enc`	transcribe and return the count	the result is `subslice dst 0 n` — not encryption
`hash.bucket_of key n` · `hash.crc data` · `hash.digest`	choosing a slot · detecting damage · detecting tampering	a different hash per question
`regex`	compile once, match many inputs	no backtracking — time proportional to input length

Table 33.2 — Shapes of the text modules — shape · meaning · why it looks this way

Recap

strings gives copy-free views, fmt assembles into the caller’s buffer and returns the next position as an option, and strbuf appends to an owned buffer. utf8 and utf16 report invalid input as none without replacement characters, and unicode’s tables were extracted mechanically. codec transcribes hex and base64 all or nothing. hash gives different hashes for slot choice, damage detection and tamper detection, and regex does not backtrack.

← PrevContentsNext →