Skip to content

to_line_index loops forever when an empty text run is alone on its own visual line #864

Open

Description

@strigeus

What happens

TextPosition::to_line_index() in accesskit_consumer never returns when a text run with no text sits alone on its own visual line (no previous_on_line / next_on_line) and the next line starts with a populated run. In the macOS adapter this method serves accessibilityLineForIndex:, so an affected request blocks the application's main thread at 100% CPU. In my case the caller was macOS's own Assistive Control process (the Accessibility Keyboard's text tracker) asking about the focused document.

This is related to #837, which reports the same endless loop for an empty run on the same visual line as a populated run, linked with next_on_line. Here the empty run has no line links at all, so as far as I can tell a fix that only handles linked runs on one line would not cover it.

Expected

The position is on the first visual line, so the method returns 0 promptly (and, in general, returns for any position in a valid tree).

Platforms

The failure is in platform-independent accesskit_consumer code. Reproduced with the published accesskit 0.25.1 / accesskit_consumer 0.39.1 on macOS ARM64 with Rust 1.98.1, using no platform accessibility API or screen reader. It affects whichever adapter calls to_line_index (the macOS one does, for accessibilityLineForIndex:).

Minimal reproduction

A document with one heading holding two text runs: an empty run, then "ab\n".

Cargo.toml:

[package]
name = "akrepro"
version = "0.1.0"
edition = "2021"

[dependencies]
accesskit = "=0.25.1"
accesskit_consumer = "=0.39.1"

src/main.rs:

use accesskit::{Node, NodeId, Role, TextDirection, TreeId, TreeInfo, TreeUpdate};
use accesskit_consumer::Tree;

fn run(node: &mut Node, v: &str, lens: Vec<u8>) {
    node.set_value(v);
    node.set_character_lengths(lens);
    node.set_text_direction(TextDirection::LeftToRight);
}

fn main() {
    let mut doc = Node::new(Role::Document);
    doc.set_children([NodeId(1)]);
    let mut heading = Node::new(Role::Heading);
    heading.set_children([NodeId(2), NodeId(3)]);
    let mut empty = Node::new(Role::TextRun);
    run(&mut empty, "", vec![]);
    let mut text = Node::new(Role::TextRun);
    run(&mut text, "ab\n", vec![1, 1, 1]);
    let tree = Tree::new(
        TreeUpdate {
            nodes: vec![(NodeId(0), doc), (NodeId(1), heading), (NodeId(2), empty), (NodeId(3), text)],
            tree: Some(TreeInfo::new(NodeId(0))),
            tree_id: TreeId::ROOT,
            focus: NodeId(0),
        },
        true,
    );
    let node = tree.state().root();
    let pos = node.text_position_from_global_utf16_index(0).unwrap();
    eprintln!("computing line index for utf16 index 0 (expected 0)");
    println!("{}", pos.to_line_index());
}

cargo run prints the eprintln! line and never finishes (I stopped it after 8 seconds). Expected output: 0.

Cause

to_line_index calls backward_to_line_start() repeatedly until is_document_start() is true. At the first character of the run after the empty one, backward_to_line_start() biases back into the empty run, finds that run as the line start, then biases forward again to the same character index of the same populated run. The result equals the input position, is_document_start() is still false (there is a preceding run), and the loop repeats forever.

Real-world source

WordCraft (storytold/wordcraft) emits an empty TextRun for a paragraph that starts with a column break (<w:br w:type="column"/>), followed by the paragraph's text as the next run. That is common in Word-made templates. WordCraft side: storytold/wordcraft#6893. Because of this, an empty run alone on its line is something a real application produces.

Suggested approach

  • Make to_line_index stop when backward_to_line_start() returns the same position (or otherwise guarantee progress), or compute the index by counting line starts forward from the document start. Either would also cover the shape in to_line_index loops indefinitely when a visual line starts with an empty text run #837.
  • Separately, the method walks back to the document start one line at a time, and each step goes through next_filtered_sibling / FollowingSiblings::new / child_ids, which allocates a Vec per sibling step. A client that asks for the line of many positions in a long document is quadratic even without the empty-run bug (I did not measure how many positions the macOS client asks about).

Activity

  1. strigeus commented on Nov 17, 2026

    @strigeus
    Author

    A second real-world source, and a more common one: in WordCraft a paragraph that contains only a page break (what Word's Ctrl+Enter inserts) produces the same tree, an empty text run followed by a "\n" run.

    WordCraft tree around such a paragraph (from storytold/wordcraft#6893):

    RUN start=0  len=18  prev=false next=false  text="Before the break.\n"
    RUN start=18 len=0   prev=false next=false  text=""        <- empty run, alone on its line
    RUN start=18 len=1   prev=false next=false  text="\n"
    RUN start=19 len=17  prev=false next=false  text="After the break.\n"
    

    to_line_index does not return for utf16 index 18 there.

    The same hang reproduces in AccessKit alone with the program in the description changed in two lines: make the second run "\n" (run(&mut text, "\n", vec![1]);) and use Role::Paragraph instead of Role::Heading. It still never finishes (I stopped it after 8 seconds; accesskit 0.25.1 / accesskit_consumer 0.39.1). So the text of the second run does not matter, only that an empty run with no line links comes before it.

    On macOS I saw this freeze the application's main thread twice with two different documents, each time with an affected request from the Accessibility Keyboard's text tracker.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions