Home / Docs / Specification
22. Text operations
Status: Normative, v0.2 (ADR 0070).
These prelude functions take a text apart, search it, change it and parse it. Text stays a value of Unicode scalar values (spec/03 §1), and every function here is pure.
Editions. The functions and the kind of this chapter exist only in packages of edition 0.2 and later (spec/13 §7). In edition 0.1, their names are ordinary names, and §6 does not apply.
1. Positions
- Scalar values. A position in a text counts Unicode scalar values from 0, as
.lendoes.t.lenis the number of scalar values oft. - Not bytes, not graphemes. No function takes or returns a byte offset or a grapheme index.
bytes()(§2) gives the UTF-8 encoding as a list.
2. Functions
They are prelude functions, called with method syntax, as line.split(on: ",") is split(line, on: ",") (spec/04 §3). In the table, n is the length of t in scalar values, b its length in UTF-8 bytes, and m the length in bytes of the other text argument.
| Function | Contract | Time |
|---|---|---|
split(t: Text, on: Text) -> List[Text] |
requires on.len > 0; ensures result.len >= 1 |
O(b + m) |
join(parts: List[Text], separator: Text) -> Text |
none | O(total bytes) |
ends_with(t: Text, suffix: Text) -> Bool |
none | O(m) |
contains_text(t: Text, part: Text) -> Bool |
none | O(b + m) |
find(t: Text, text: Text) -> Option[Int] |
result is Some exactly when contains_text(t, part: text) |
O(b + m) |
replace(t: Text, pattern: Text, by: Text) -> Text |
requires pattern.len > 0 |
O(b + m + result) |
slice(t: Text, start: Int, end: Int) -> Text |
requires 0 <= start and start <= end and end <= t.len; ensures result.len == end - start |
O(result) |
to_upper(t: Text) -> Text |
ensures result.len == t.len |
O(b) |
to_lower(t: Text) -> Text |
ensures result.len == t.len |
O(b) |
chars(t: Text) -> List[Text] |
ensures result.len == t.len |
O(b) |
parse_int(t: Text) -> Int fails ParseError |
§4 | O(b) |
trim_start(t: Text) -> Text |
ensures result.len <= t.len |
O(result + trimmed) |
trim_end(t: Text) -> Text |
ensures result.len <= t.len |
O(result + trimmed) |
bytes(t: Text) -> List[U8] |
ensures result.len >= t.len |
O(b) |
-
splitreturns the parts between non-overlapping occurrences ofon, left to right, including empty parts:"a,,b".split(on: ",")is["a", "", "b"], and a text withoutonis a list of itself.joinis its inverse:t.split(on: s).join(separator: s) == t. -
findreturns the position of the first occurrence oftext, andSome(0)for an emptytext. When it isSome(p),0 <= pandp + text.len <= t.len, which the verifier assumes after each call. -
replacereplaces every non-overlapping occurrence ofpatternbyby, left to right. Its precondition,pattern.len > 0, is an obligation at each call (spec/12 §3). -
slicereturns the scalar values at positionsstartup to, not including,end. Its precondition is an obligation at each call (spec/12 §3).A checked program never calls
replaceorsliceoutside its precondition, sinceuna run,una testanduna buildrefuse a package whose obligations are not proved. If such a call happens anyway, the run aborts at the call with U8001 and exit code 3, in the interpreter and in a native executable alike, as for any fault a checked program cannot reach (spec/11 §4). Neither backend clamps the positions or replaces an empty pattern (#693). -
charsreturns one text of length 1 per scalar value, in order. -
trim_startandtrim_endremove UnicodeWhite_Spaceat one end, astrimdoes at both (spec/14 §1). -
bytesreturns the UTF-8 encoding. -
The search algorithm is linear in the worst case, such as the two-way algorithm. A naive quadratic search is not allowed.
3. Case
to_upper maps the ASCII letters a to z to A to Z, and to_lower maps them back. Every other scalar value is left as it is, so the length never changes and the result does not depend on a Unicode version.
4. Parsing integers
- The prelude declares
kind ParseError = Empty | NotADigit(at: Int) | NoDigits | TooLong. (Security fix, 2026-10-18, #914:TooLongis new, in every edition that hasparse_int. Awhenover aParseErrorthat names each variant and has noelsearm becomes non-exhaustive, a check error and never a silent change.) parse_int(t)reads an optional-followed by one or more ASCII digits, asto_intdoes (spec/14 §1), and returns the integer. Otherwise it fails:Emptywhentis empty;NoDigitswhentis-alone;NotADigit(at: i)at the first positionithat is neither the leading-nor a digit;TooLongwhentis an optional-and more than 4300 digits, the sign excluded and leading zeros included, the bound of a JSON integer (spec/23 §3). Converting d digits to an integer takes O(d²), so a longer text is refused before any conversion, and the cost ofparse_intstays O(b) (security fix, 2026-10-18, #914). A text with a character that is not a digit fails withNotADigit, whatever its length.
- Space is not trimmed:
parse_int(trim(t))reads a padded number. - The result is an unbounded
Int. A fixed-width integer is parsed through a narrowing conversion, with itsoverflowobligation (spec/18 §4). to_intkeeps its meaning.
5. Information flow
- Results. The result of every function in §2 carries the join of every label of every argument. For
splitandchars, that includes the list's top label and every element, since their shape depends on every scalar value (spec/14 §1, "the other functions"). - Failures.
parse_intfails depending on its argument's value, so its failure is labeled like its result. Handling it raises the program counter by that label (spec/07 §3).
6. Dynamic semantics
- Representation. The interpreter and the native runtime keep a text as UTF-8 bytes together with its scalar count and whether every byte is ASCII, computed when the text is made. The first positional operation on a non-ASCII text builds an index of the byte offset of every 64th scalar value, kept with the value. These are not observable, but they bound the cost:
.lenis O(1);- a position is O(1) on an ASCII text, and O(1) on any text once its index is built, in O(b) at most once.
- Appending in place. An assignment that rebinds a text binding to an interpolation that begins with that binding, as
acc = "{acc}, {item}", appends to it.- When the binding's text is uniquely held, the append happens in place, in both engines, in amortized O(1) per scalar value appended. The scalar count and the ASCII flag are updated, not recomputed.
- Otherwise the text is copied first.
- This is the freedom of spec/17 §7 rule 3: it changes no output, failure or trace.
- So a loop of k such appends is O(total length), not O(k²).
- Equivalence. Both engines give the same text for every operation, by the rules of §2 to §4 (spec/16 §5).
- Writing integers (2026-10-27, #923). Interpolation and
to_textwrite anIntof at most 4300 digits, the bound of §4, in O(d) for its d digits; anIntof more digits is never written: the run aborts with U6003 at the interpolation or the call (spec/11 §7).
7. Verification
The contracts in §2 are hypotheses after each call, and slice's precondition is an obligation. There is no theory of strings: beyond the contracts, the functions are uninterpreted (spec/12 §2).