Implement Unicode 17 UAX #9 bidi analysis and per-line reordering

[lukewilliamboswell]

Summary

Add a complete Unicode Bidirectional Algorithm implementation for Unicode 17.0.0, conforming to UAX #9 revision 51. The primary API should analyze logical-order text into paragraph direction, resolved levels, directional runs, line-reordering permutations, logical/visual mappings, bracket information, and mirroring facts.

A convenience function may construct display-order text, but it must not be the only or foundational result. Rendering, shaping, hit testing, selection, editing, and line layout need the analysis facts and a stable connection to the original text.

The current package has no bidi module, data, or tests, and no existing issue requests this capability.

Background for implementers

Unicode strings are stored in logical order: the order in which the text is read and edited. Most scripts flow left-to-right (LTR), while Hebrew, Arabic, and several related scripts flow right-to-left (RTL). Arabic and Hebrew text still contains LTR numbers and can contain embedded LTR words, so reversing an RTL string is not correct.

UAX #9 resolves this by assigning each scalar a Bidi_Class and then an integer embedding level:

• even levels have LTR direction;
• odd levels have RTL direction;
• higher levels represent nested directional context.

Bidi classes include strong types (L, R, AL), weak types such as European/Arabic numbers and separators (EN, AN, ES, ET, CS, NSM, BN), neutral types (B, S, WS, ON), and explicit formatting controls.

Each paragraph has a base direction, represented by paragraph level 0 for LTR or 1 for RTL. In auto mode, rules P2/P3 choose it from the first strong L, R, or AL outside isolates, defaulting to LTR. A higher-level caller must also be able to force LTR or RTL as permitted by HL1.

Directional formatting controls change how enclosed text is resolved:

• LRE/RLE begin embeddings; PDF ends an embedding.
• LRO/RLO begin overrides that force enclosed bidi types; overrides have security implications but are required for full conformance.
• LRI/RLI begin isolates whose contents cannot affect surrounding text.
• FSI chooses an isolate direction from its first strong character; PDI ends an isolate.
• LRM, RLM, and ALM are invisible strong characters.

UAX #9 resolves explicit scopes (X rules), isolating run sequences, weak types (W rules), paired brackets and neutrals (N rules), and implicit levels (I rules). It then applies L1/L2 separately to each line after line breaking. A paragraph-wide reordered string is therefore insufficient: trailing whitespace levels reset per line and the visual order can change when the same paragraph wraps at different places.

Paired brackets are semantic pairs used by rule N0. They come from the normative Bidi_Paired_Bracket and Bidi_Paired_Bracket_Type properties, not from guessing character names or adjacent code points. Mirroring is a separate display fact: rule L4 calls for a mirrored glyph when resolved direction is RTL and Bidi_Mirrored=Yes. BidiMirroring.txt offers an informative substitute character for many, but not all, mirrored characters. The API should report that a mirrored glyph is needed and optionally report the mapped scalar; it should not silently replace the original text.

Normative scope and data

Implement full bidirectionality under UAX9-C1: BD1-BD16, P1-P3, X1-X10, W1-W7, N0-N2, I1-I2, and L1-L4, including explicit embeddings, overrides, isolates, paired brackets, paragraph splitting, and per-line reordering.

Use the final Unicode 17 files:

• DerivedBidiClass.txt for complete Bidi_Class values and important @missing defaults for unassigned RTL ranges
• BidiBrackets.txt for normative paired-bracket mappings and types
• UnicodeData.txt for the normative Bidi_Mirrored property
• BidiMirroring.txt for informative mirror-character mappings
• BidiTest.txt, exhaustive bidi-class sequences up to length four plus longer pitfalls
• BidiCharacterTest.txt, explicit scalar cases including brackets and formatting controls

Integrate these files into the single Unicode 17 version/provenance manifest proposed in #36, including stable URLs, hashes, header validation, Unicode License v3 notices, deterministic generation, and mixed-version CI rejection. Do not create a separate version authority for bidi.

Proposed API shape

Exact Roc names may follow package conventions, but the behavior and information model should support the following layers.

Paragraph analysis

Provide an operation equivalent to:

Bidi.analyze_paragraph(
    text,
    base_direction: [AutoLtr, LeftToRight, RightToLeft],
    limits,
) -> Result(ParagraphAnalysis, BidiError)

Also provide paragraph splitting/analysis for a full string under P1, or a deterministic helper returning paragraph byte ranges. Specify whether a paragraph separator is included with the preceding paragraph, as P1 requires.

ParagraphAnalysis should retain the original text by ranges and expose at least:

• paragraph UTF-8 byte range and scalar range;
• requested base-direction policy and resolved paragraph level/direction;
• one entry per original scalar with its scalar index, half-open UTF-8 byte range, original Bidi_Class, resolved level (or explicit RemovedByX9 state), and whether it is a non-rendering format control;
• maximal logical directional/level runs, each with byte/scalar ranges, level, and direction;
• matched isolate/control information where useful for diagnostics;
• paired-bracket positions resolved by BD16/N0;
• needs_mirrored_glyph from L4 and optional Bidi_Mirroring_Glyph for each relevant scalar.

Resolved working types may be exposed for diagnostics, but callers must not have to rerun or infer algorithm stages.

Per-line reordering

Provide a separate operation equivalent to:

Bidi.reorder_line(analysis, line_scalar_range) -> Result(LineOrder, BidiError)

The line is a logical-order subrange of exactly one analyzed paragraph. This operation applies L1 and L2 for those actual line boundaries and returns:

• the line-local levels after L1;
• visual-to-logical scalar indices;
• logical-to-visual inverse entries, with an explicit None/removed state where UAX Updating headers of all files #9 does not assign display order;
• maximal visual runs with logical ranges, level, and direction;
• mirroring flags/facts aligned with original scalar identities.

Document whether zero-width isolate controls are present in the L2 permutation and separately flag that they have no visible representation. X9-removed controls must remain represented in paragraph metadata even when omitted from the display permutation, so editors/debuggers do not lose their identity. UAX #9 section 5.2 describes why retaining these controls can matter.

A convenience display-order helper must be built from these mappings and preserve the original logical text. It must not perform Arabic shaping, glyph selection, or destructive substitution.

Offset and boundary contract

All public ranges should be half-open [start, end) offsets into the unchanged input. Use UTF-8 byte offsets as the stable slicing identity and also expose scalar indices where permutations need dense integer indices.

Define and test these rules:

• every byte boundary is a valid UTF-8 scalar boundary;
• scalar index 0 is the first scalar of the analyzed paragraph, independent of byte width;
• paragraph separators belong to the preceding paragraph under P1;
• line ranges must be ordered, scalar-aligned, contained within one paragraph, and non-overlapping when supplied as a line set;
• mappings refer to original logical scalar indices, never indices in an incidental filtered buffer;
• X9-removed controls and invisible isolates have explicit states rather than causing indices to shift silently;
• empty text, empty paragraphs, empty lines, CR/LF/CRLF policy, and a final paragraph without a separator have documented deterministic results.

These contracts make analysis reusable without copying or reconstructing strings.

Limits, errors, and performance

The normative limits are behavior, not errors:

• BD2 fixes max_depth at 125. Inputs nested beyond this must follow the UAX overflow-isolate/overflow-embedding rules, not panic or be rejected merely for exceeding 125.
• BD16 requires a fixed bracket stack of exactly 63 entries and specifies the result on overflow. Implement that behavior exactly.

If the API adds resource limits such as maximum scalars, paragraphs, output entries, or work, make them explicit inputs with documented defaults. Exceeding an application limit should return a structured error containing the limit, observed/requested amount, paragraph range, and stage. Invalid line/paragraph boundaries should likewise return structured errors. No valid Unicode string or formatting-control sequence may reach crash or an unreachable branch.

Target linear time in the number of scalars plus output size, with bounded 126/127-entry directional state and 63-entry bracket stacks. Avoid quadratic rescanning for nested FSI/PDI, isolating run sequences, unmatched controls, or long neutral/bracket sequences. Build dense buffers in logical order; avoid one allocation or reconstructed Str per scalar/run. Document expected complexity and add adversarial scaling evidence.

Conformance and deterministic tests

1. Parse and execute every applicable case in both Unicode 17 conformance files:
   • every paragraph-mode bit selected by each BidiTest.txt row;
   • every row and specified paragraph mode in BidiCharacterTest.txt;
   • exact resolved paragraph level, per-scalar levels including x, and visual reorder indices.
2. Assert parsed and executed case counts. Unknown directives, properties, malformed rows, unsupported modes, or truncated files must fail generation/CI rather than be skipped.
3. Exhaustively compare generated Bidi_Class, bracket type/pair, Bidi_Mirrored, and mirror mapping lookups with the source data for every Unicode scalar, including all @missing defaults.
4. Add focused tests not fully covered by the official files:
   • P1 with multiple paragraphs and separators at start/end, including the documented CR/LF/CRLF policy;
   • auto, forced LTR, and forced RTL base direction, including no-strong text and strong text hidden inside isolates;
   • matched, unmatched, overflowed, and deeply nested embeddings, overrides, isolates, PDF, and PDI around levels 124-126;
   • FSI with nested isolates and missing PDI;
   • exactly 62, 63, and 64 nested opening brackets, mismatched/crossing brackets, canonical U+3008/U+2329 equivalence, and bracket NSMs;
   • European and Arabic numbers with separators/terminators and surrounding strong types;
   • BN, ZWJ, ZWNJ, combining marks, noncharacters, private-use, unassigned RTL-range scalars, and supplementary-plane text;
   • L1 trailing whitespace/isolates at several different line breaks within the same analyzed paragraph;
   • L4 mirrored characters both with and without a Bidi_Mirroring_Glyph mapping.
5. Run data generation twice and require byte-for-byte identical output.

The official files test through L2; L3 is rendering-engine dependent and L4 needs separate property/mirroring assertions, as their headers explain.

Fuzzing, metamorphic, and regression tests

Create deterministic seed-based fuzz targets over valid scalar sequences, weighted toward every bidi class, brackets, separators, NSM, BN, explicit controls, and nested isolates. Seed with all official character cases and the UAX examples. Report/minimize the scalar sequence, base policy, line ranges, seed, and first differing stage.

For every input assert:

• no panic, hang, out-of-bounds access, or unbounded recursion;
• every original scalar appears exactly once in paragraph metadata with an exact byte range;
• resolved levels are within the UAX range and level parity agrees with reported direction;
• every line permutation contains exactly the eligible logical indices once, and logical-to-visual/visual-to-logical mappings are inverses;
• joining original byte ranges in logical order reproduces the input byte-for-byte;
• all reported runs are nonempty, ordered, contiguous in their stated coordinate space, and cover exactly their promised domain;
• mirroring is requested exactly when L4 applies; a missing mirror-character mapping never suppresses the mirrored-glyph requirement;
• analyzing a multi-paragraph string is equivalent to analyzing each P1 paragraph separately with the same base policy;
• inserting a complete isolate changes neither resolved levels nor relative visual order outside that isolate, after accounting for shifted logical indices;
• splitting a paragraph into different valid lines changes only L1/L2 line results, not paragraph resolution;
• forced-LTR text consisting only of L characters has identity visual order, and analogous simple RTL/number fixtures have their mathematically expected permutations.

Run differential randomized tests against the official Unicode 17 C or Java reference implementation as an additional oracle. Keep the Unicode conformance files normative. Persist every minimized failure as a named regression.

Complexity and allocation evidence

Add benchmarks or deterministic work counters for:

• all-LTR fast path;
• mixed Arabic/Hebrew/Latin/numbers;
• long neutrals and NSMs;
• deeply nested valid and overflowed isolates/embeddings;
• repeated FSI;
• maximum/overflow bracket nesting;
• many short runs and alternating levels;
• one long paragraph reordered at many line boundaries.

Acceptance should demonstrate linear scaling, no quadratic adversarial case, bounded control/bracket stacks, and allocations proportional to retained analysis/output buffers rather than temporary lists per rule pass or scalar.

Acceptance criteria

• Public docs state Unicode 17.0.0 / UAX Updating headers of all files #9 revision 51 and the UAX9-C1 conformance scope.
• Bidi data and test files are registered in Upgrade Unicode data and algorithms to 17.0.0 and make the version auditable #36's single version/provenance mechanism and cannot be mixed with another Unicode version.
• Generated Bidi_Class, paired-bracket, Bidi_Mirrored, and optional mirror-glyph tables are exhaustively verified against Unicode 17 source data and defaults.
• P1-P3, X1-X10, W1-W7, N0-N2, I1-I2, and L1-L4 are implemented, including embeddings, overrides, isolates, FSI, bracket pairing, and overflow rules.
• All applicable rows/modes from BidiTest.txt and BidiCharacterTest.txt pass with exact levels and reorder indices, with asserted counts and no skips/silent parser recovery.
• Analysis returns paragraph base level, per-scalar original identity/ranges and levels, logical runs, bracket facts, and mirroring facts rather than only a reordered string.
• Per-line L1/L2 reordering accepts validated logical line ranges and returns invertible logical/visual mappings and visual runs.
• UTF-8 byte offsets, scalar indices, paragraph ownership, line-boundary requirements, X9-removed controls, and zero-width controls have documented deterministic semantics.
• Nesting beyond max depth 125 and bracket depth beyond 63 follow UAX Updating headers of all files #9 exactly; optional application resource limits return structured errors and never become conformance shortcuts.
• Valid input has no reachable panic. Invalid ranges/explicit resource exhaustion return structured, diagnostic errors.
• The deterministic property/metamorphic suite runs in normal CI; a larger seeded, minimized differential fuzz campaign runs on a schedule.
• Adversarial benchmarks/work counters demonstrate documented linear-time behavior, bounded normative stacks, and allocation growth proportional to analysis/output size.
• Examples show mixed Hebrew/Arabic/Latin/numbers, explicit base direction, isolates, line-specific reordering, mappings, and mirroring without destructively changing logical text.

References

• UAX #9 revision 51
• Basic Display Algorithm
• Reordering Resolved Levels
• Bidirectional conformance testing
• Unicode 17 UCD

[lukewilliamboswell]

Codex triage note: I am Codex, assisting Luke with a triage of the open issues against current main at f5cd8d6. Main now contains a meaningful part of the required substrate: public BidiClass and BidiProperties queries, exact Unicode 17 default handling, paired-bracket facts, mirrored flags, optional mirroring glyphs, and shared manifest-backed tables. These are the character-data services that a conformant UAX #9 implementation should consume rather than rebuilding a second property database.

The paragraph algorithm itself is not implemented. There is no Bidi.analyze_paragraph, retained analysis tape, P/X/W/N/I resolution, embedding or isolate handling, line-specific L1/L2 reordering, mappings, limits, or conformance suite from BidiTest.txt and BidiCharacterTest.txt. This issue should remain open, but its current-state section can now be read as substrate complete and algorithm work remaining. Future bidi fuzz targets should be added to #50 only after the retained analysis API exists.