unicode

Branch: main

Switch branches or tags

Branch: main
Go to file t

413 files indexed

History
Code

docs/plans/2026-10-16-segmentation-boundary-api.md

Segmentation boundary queries

Status: deferred on 2026-10-16. This is a design record, not a published API contract or a commitment to implement these interfaces.

Decision

Do not expose stateless next_* boundary queries yet. Remove the experimental next_line_break function and its LineBreakOffset result type. Keep the existing graphemes, word_segments, words, sentences, and line_breaks cursors unchanged. Internal boundary helpers are not public APIs and remain.

The main unresolved issue is efficient recovery of context at arbitrary positions. A query must not unconditionally preprocess the whole input just to find a nearby boundary. A stateful break iterator and streaming support remain possible future work.

Proposed interface and semantics

The explored signatures were:

next_grapheme_boundary(StringView, offset~ : Int) -> Int
next_word_boundary(StringView, offset~ : Int) -> Int
next_sentence_boundary(StringView, offset~ : Int) -> Int
next_line_break(StringView, offset~ : Int) -> LineBreakOffset?

For line breaking, the preferred result was an ordinary enum:

pub(all) enum LineBreakOffset {
  Allowed(Int)
  Mandatory(Int)
}
  • All offsets are UTF-16 code unit offsets relative to the supplied view, rather than code point ordinals or indices in its backing string.
  • Search strictly after offset, using the entire view as context.
  • The starting offset may be inside a segment or a valid surrogate pair. Returned boundaries must not split a valid pair.
  • The view is independent of surrounding text in its backing string.
  • For line breaks, reaching the end from an earlier position yields Some(Mandatory(length)); querying at or beyond the end yields None. Empty input yields None.
  • The experimental implementation treated negative offsets as zero. Reconsider out-of-range handling before publishing the API.
  • For the other three queries, returning length again at exhaustion was discussed, but their final return and exhaustion conventions are not settled.

For example, "ab cd" would produce Some(Allowed(3)) from offset 0, Some(Mandatory(5)) from offset 3, and None from offset 5.

BreakOpportunity::Prohibited remains meaningful when querying a particular position, such as a grapheme end. It is not a found result for a function that searches for the next allowed or mandatory opportunity. Using a payload-free Prohibited variant to mean exhaustion was considered, but conflates these two meanings. LineBreakOffset? separates absence from the kind of a boundary.

Separate next_allowed_line_break and next_mandatory_line_break functions were also considered. The former would need to include mandatory positions; otherwise it could skip a required break. Returning the kind together with the position avoids a second query to classify the result.

Why arbitrary offsets need context

The search offset is not the beginning of the segmentation context. Slicing away the prefix and segmenting the suffix independently can change results. For example, can't has no word boundary after the apostrophe, whereas the independent suffix 't does. WB7 needs the preceding letter.

There is no universal fixed number of code points that suffices for lookbehind when starting at an arbitrary position without cached state:

  • UAX #14 LB14 has OP SP* ×. In ( followed by an arbitrarily long space run and then a, the opening punctuation suppresses the break before a. Replacing the ( with x allows that break. A fixed local window near a cannot distinguish these inputs.
  • UAX #14 LB30a uses the parity of the preceding consecutive regional indicators. That run can be arbitrarily long. UAX #29 grapheme rules GB12/GB13 and word rules WB15/WB16 have the same pairing issue.

Unbounded context distance does not imply unbounded state: a sequential scanner can remember the relevant class before a space run and RI parity. Nor does it imply that every query must scan the entire input. It means a stateless query cannot promise constant lookbehind for arbitrary input. Searching forward to the next boundary can itself cover arbitrarily many characters, independently of the cost of recovering prior context.

Why the experimental implementation was removed

The implementation called prepare_units(text) on every query. This scanned the entire view and allocated an array of context records before searching for the first boundary after the offset. Each query therefore used O(n) time and space, even for a nearby result. Repeated calls over O(n) boundaries could take O(n²) time.

This is a limitation of that implementation, not a requirement of the API or Unicode. A future implementation should recover context on demand or use cached state, scan only as far forward as needed, and avoid unconditional whole-input allocation. Worst-case context distance must still be documented.

Before removal, the query was checked at every UTF-16 offset of all 19,346 official Unicode 18.0.0 LineBreakTest.txt cases, including surrogate interiors. Boundary positions matched the fixture; boundary kinds matched the existing cursor. These query-specific checks were removed with the experimental API; the original conformance tests remain.

Representation experiment: optional enums

A standalone experiment used MoonBit 0.1.20261012 (748b63c), native release output, and #inline(never) producer and consumer functions to preserve call boundaries. Generated C showed these allocations on a successful result:

Representation Heap allocations
Ordinary two-variant enum 1
Optional ordinary two-variant enum 1
#valtype two-variant enum 0
Optional #valtype two-variant enum 1
#valtype enum with Allowed(Int), Mandatory(Int), End 0

For the ordinary enum, None became a null pointer and Some(value) reused the enum object's pointer. The outer option did not allocate another box. For the value enum, the payload was returned by value, but wrapping it in Some allocated an object containing that value.

JS release output used undefined for None and reused the enum object for Some, for both ordinary and value-enum declarations. The enum payload still used an object. Wasm layouts were not checked. These are observations about this compiler and these call shapes, not permanent layout guarantees or performance benchmarks; inlining may remove allocations at other call sites.

The essential reproduction is to compile enum BreakIndex { Allowed(Int); Mandatory(Int) }, a non-inlined function returning it, and another returning Some of that function's result or None. Repeat with #valtype, consume results across a non-inlined call, and inspect native release C for moonbit_malloc and the option's representation. The original temporary experiment is not a repository dependency.

Stateful and streaming alternatives

A break iterator can retain position, rule state, lookahead, and the last boundary kind. This can avoid repeated context recovery during sequential traversal. Arbitrary seeking, reverse traversal, cache invalidation after edits, and memory costs still need explicit design. Wrapping the stateless query in a cursor does not by itself remove its costs.

Streaming needs a different input contract. A chunk end is not necessarily a text end: a trailing CR may be followed by LF in the next chunk, and a high surrogate may be followed by its low surrogate. The processor must preserve state and distinguish a found boundary, a need for more input, and completion after explicit end-of-input. None in a complete-text query only means no later boundary; it must not silently acquire a second meaning of "wait for another chunk". Boundary offsets would also need a documented stream-wide coordinate system and retained-input policy.

References

1# Segmentation boundary queries23Status: deferred on 2026-10-16. This is a design record, not a published API4contract or a commitment to implement these interfaces.56## Decision78Do not expose stateless `next_*` boundary queries yet. Remove the experimental9`next_line_break` function and its `LineBreakOffset` result type. Keep the10existing `graphemes`, `word_segments`, `words`, `sentences`, and `line_breaks`11cursors unchanged. Internal boundary helpers are not public APIs and remain.1213The main unresolved issue is efficient recovery of context at arbitrary14positions. A query must not unconditionally preprocess the whole input just15to find a nearby boundary. A stateful break iterator and streaming support16remain possible future work.1718## Proposed interface and semantics1920The explored signatures were:2122```text23next_grapheme_boundary(StringView, offset~ : Int) -> Int24next_word_boundary(StringView, offset~ : Int) -> Int25next_sentence_boundary(StringView, offset~ : Int) -> Int26next_line_break(StringView, offset~ : Int) -> LineBreakOffset?27```2829For line breaking, the preferred result was an ordinary enum:3031```moonbit32pub(all) enum LineBreakOffset {33  Allowed(Int)34  Mandatory(Int)35}36```3738- All offsets are UTF-16 code unit offsets relative to the supplied view,39  rather than code point ordinals or indices in its backing string.40- Search strictly after `offset`, using the entire view as context.41- The starting offset may be inside a segment or a valid surrogate pair.42  Returned boundaries must not split a valid pair.43- The view is independent of surrounding text in its backing string.44- For line breaks, reaching the end from an earlier position yields45  `Some(Mandatory(length))`; querying at or beyond the end yields `None`.46  Empty input yields `None`.47- The experimental implementation treated negative offsets as zero.48  Reconsider out-of-range handling before publishing the API.49- For the other three queries, returning `length` again at exhaustion was50  discussed, but their final return and exhaustion conventions are not settled.5152For example, `"ab cd"` would produce `Some(Allowed(3))` from offset 0,53`Some(Mandatory(5))` from offset 3, and `None` from offset 5.5455`BreakOpportunity::Prohibited` remains meaningful when querying a particular56position, such as a grapheme end. It is not a found result for a function that57searches for the next allowed or mandatory opportunity. Using a payload-free58`Prohibited` variant to mean exhaustion was considered, but conflates these59two meanings. `LineBreakOffset?` separates absence from the kind of a boundary.6061Separate `next_allowed_line_break` and `next_mandatory_line_break` functions62were also considered. The former would need to include mandatory positions;63otherwise it could skip a required break. Returning the kind together with64the position avoids a second query to classify the result.6566## Why arbitrary offsets need context6768The search offset is not the beginning of the segmentation context. Slicing69away the prefix and segmenting the suffix independently can change results.70For example, `can't` has no word boundary after the apostrophe, whereas the71independent suffix `'t` does. WB7 needs the preceding letter.7273There is no universal fixed number of code points that suffices for lookbehind74when starting at an arbitrary position without cached state:7576- UAX #14 LB14 has `OP SP* ×`. In `(` followed by an arbitrarily long space77  run and then `a`, the opening punctuation suppresses the break before `a`.78  Replacing the `(` with `x` allows that break. A fixed local window near `a`79  cannot distinguish these inputs.80- UAX #14 LB30a uses the parity of the preceding consecutive regional81  indicators. That run can be arbitrarily long. UAX #29 grapheme rules82  GB12/GB13 and word rules WB15/WB16 have the same pairing issue.8384Unbounded context distance does not imply unbounded state: a sequential85scanner can remember the relevant class before a space run and RI parity.86Nor does it imply that every query must scan the entire input. It means a87stateless query cannot promise constant lookbehind for arbitrary input.88Searching forward to the next boundary can itself cover arbitrarily many89characters, independently of the cost of recovering prior context.9091## Why the experimental implementation was removed9293The implementation called `prepare_units(text)` on every query. This scanned94the entire view and allocated an array of context records before searching95for the first boundary after the offset. Each query therefore used O(n) time96and space, even for a nearby result. Repeated calls over O(n) boundaries could97take O(n²) time.9899This is a limitation of that implementation, not a requirement of the API or100Unicode. A future implementation should recover context on demand or use101cached state, scan only as far forward as needed, and avoid unconditional102whole-input allocation. Worst-case context distance must still be documented.103104Before removal, the query was checked at every UTF-16 offset of all 19,346105official Unicode 18.0.0 `LineBreakTest.txt` cases, including surrogate interiors.106Boundary positions matched the fixture; boundary kinds matched the existing107cursor. These query-specific checks were removed with the experimental API;108the original conformance tests remain.109110## Representation experiment: optional enums111112A standalone experiment used MoonBit `0.1.20261012` (748b63c), native release113output, and `#inline(never)` producer and consumer functions to preserve call114boundaries. Generated C showed these allocations on a successful result:115116| Representation | Heap allocations |117| --- | ---: |118| Ordinary two-variant enum | 1 |119| Optional ordinary two-variant enum | 1 |120| `#valtype` two-variant enum | 0 |121| Optional `#valtype` two-variant enum | 1 |122| `#valtype` enum with `Allowed(Int)`, `Mandatory(Int)`, `End` | 0 |123124For the ordinary enum, `None` became a null pointer and `Some(value)` reused125the enum object's pointer. The outer option did not allocate another box.126For the value enum, the payload was returned by value, but wrapping it in127`Some` allocated an object containing that value.128129JS release output used `undefined` for `None` and reused the enum object for130`Some`, for both ordinary and value-enum declarations. The enum payload still131used an object. Wasm layouts were not checked. These are observations about132this compiler and these call shapes, not permanent layout guarantees or133performance benchmarks; inlining may remove allocations at other call sites.134135The essential reproduction is to compile `enum BreakIndex { Allowed(Int);136Mandatory(Int) }`, a non-inlined function returning it, and another returning137`Some` of that function's result or `None`. Repeat with `#valtype`, consume138results across a non-inlined call, and inspect native release C for139`moonbit_malloc` and the option's representation. The original temporary140experiment is not a repository dependency.141142## Stateful and streaming alternatives143144A break iterator can retain position, rule state, lookahead, and the last145boundary kind. This can avoid repeated context recovery during sequential146traversal. Arbitrary seeking, reverse traversal, cache invalidation after147edits, and memory costs still need explicit design. Wrapping the stateless148query in a cursor does not by itself remove its costs.149150Streaming needs a different input contract. A chunk end is not necessarily a151text end: a trailing CR may be followed by LF in the next chunk, and a high152surrogate may be followed by its low surrogate. The processor must preserve153state and distinguish a found boundary, a need for more input, and completion154after explicit end-of-input. `None` in a complete-text query only means no155later boundary; it must not silently acquire a second meaning of "wait for156another chunk". Boundary offsets would also need a documented stream-wide157coordinate system and retained-input policy.158159## References160161- [UAX #14, LB14](https://www.unicode.org/reports/tr14/tr14-57.html#LB14)162- [UAX #14, LB30a](https://www.unicode.org/reports/tr14/tr14-57.html#LB30a)163- [UAX #29, word boundary rules](https://www.unicode.org/reports/tr29/tr29-49.html#Default_Word_Boundaries)164- [UAX #29, random access](https://www.unicode.org/reports/tr29/tr29-49.html#Random_Access)165- [Rust unicode-linebreak: tuple items, optional iterator results](https://docs.rs/unicode-linebreak/0.1.5/unicode_linebreak/fn.linebreaks.html)166- [ICU BreakIterator: integer positions, DONE, separate rule status](https://unicode-org.github.io/icu-docs/apidoc/dev/icu4c/classicu_1_1BreakIterator.html)167