1739560 - Update cache when line boundaries change

Status: RESOLVED FIXED

(Core :: Disability Access APIs, task)

Description

[James Teh [:Jamie]]

Bug 1730093 implemented caching for line boundaries. However, if the line boundaries in a text leaf change without the text itself changing (e.g. text was inserted before that leaf on the line), I suspect the cache won't get updated. We'll need to get notified about that and push the cache.

My current thinking is that whenever line boundaries change, the bounds should change too. Since we already deal with bounds updates thanks to bug 1726227, I'm hoping we can push a text cache update if the bounds for a text leaf change.

One thing to watch is that if the text does change, we'll already push a text cache update. We won't want to push two updates for the same Accessible in that case. We'll probably need to add code to avoid a second text cache update if that Accessible was already handled as a text update.

Comment 1

[James Teh [:Jamie]]

We'll need this for Android.

Comment 2

[James Teh [:Jamie]]

This doesn't seem to be important for Android, so moving to m2. It will be needed to support Google Docs and Gmail message editing correctly.

Comment 3

[James Teh [:Jamie]]

This can be reproduced with:
data:text/html,<div contenteditable><br>
then typing a single letter at the beginning. The br still thinks it's at the start of a line, so if the caret is on the line feed, you get a blank line.

Comment 4

[James Teh [:Jamie]]

(In reply to James Teh [:Jamie] from comment #0)

My current thinking is that whenever line boundaries change, the bounds should change too.

Ug. That doesn't always hold. Consider this:

data:text/html,<div contenteditable style="word-break: break-word; width: 2ch;"><span>ac</span>def

That gives you this:

ac
de
f

The second text leaf (starting at d) spans two lines. Even though there is only a single character f on the last line, the rect has to cover e, so the rect is the width of two characters.

Now, if you insert b between a and c, you get this:

ab
cd
ef

The second text leaf reflows. It only includes one character on the second line now (d), but because it includes e, the rect's left coordinate is the first character. Because it includes f, the width is two characters. Unfortunately, that means the rect doesn't change... and the text hasn't changed either. :(

I don't know what to do about this. Sending cached lines every time we reflow seems bad for the same reason that sending bounds every time we reflow is bad. (That's why we cache bounds in LocalAccessible.) But caching lines in LocalAccessible as well seems really horrible.

I guess we could get the points for the first and last characters of the leaf and compare those. That's perhaps better than caching all the line starts, but it still means caching additional stuff in LocalAccessible.

Any thoughts, Morgan? I'm not asking you to come up with a solution here, more just to check my thinking in case I've missed something or if anything comes to mind without digging too much. Can we do polygons? :)

Comment 5

[James Teh [:Jamie]]

Ah. I think if any of the line starts are going to change (assuming the text and bounds haven't changed), the first line start must change. Therefore, we can probably get away with just caching the first line start in LocalAccessible. That's less bytes than any of the other caching options at least.

Still, if you have any other ideas that don't involve caching in LocalAccessible, I'm keen to hear them.

Comment 6

[James Teh [:Jamie]]

Note that we're probably going to hit a similar problem for text bounds, though we can likely depend on the same condition we come up with here.

Comment 7

[Morgan Reschenberg [:morgan]]

(In reply to James Teh [:Jamie] from comment #4)

(In reply to James Teh [:Jamie] from comment #0)

My current thinking is that whenever line boundaries change, the bounds should change too.

Ug. That doesn't always hold. Consider this:

data:text/html,<div contenteditable style="word-break: break-word; width: 2ch;"><span>ac</span>def

That gives you this:

ac
de
f

The second text leaf (starting at d) spans two lines. Even though there is only a single character f on the last line, the rect has to cover e, so the rect is the width of two characters.

So lineStarts would look like: [0] for the first leaf and [0, 2] for the second leaf

Now, if you insert b between a and c, you get this:

ab
cd
ef

The second text leaf reflows. It only includes one character on the second line now (d), but because it includes e, the rect's left coordinate is the first character. Because it includes f, the width is two characters. Unfortunately, that means the rect doesn't change... and the text hasn't changed either. :(

... And now lineStarts is [0, 2] and [1] for the leaves respectively.

So your point is the bounds (er, bounding rect, what we get from Bounds()) for the final text leaf wouldn't change, so we can't rely on that as an indicator to update our lineStarts array? Just wanna make sure I have this right 😀 I wonder if you could use text length to help with this. It seems like lineStarts would only be affected (a) in the leaf an insertion or deletion occurred in and (b) any leaves after that in the reading order that don't force a line break themselves. Is that fair to say?

If you have something like data:text/html,<div contenteditable style="word-break: break-word; width: 2ch;"><span>abc</span><br>def for example, inserting "b" in the same fashion doesn't change the lineStarts of the last leaf because the <br> means it isn't dependent on the leaf before.

It isn't super efficient, but if you're monitoring text-length changes, you at least have a narrowed range of leaves that may be affected. And, if we keep track of where "hard" linebreaks occur, that could narrow the range further. We'd have to do a traversal, and potentially reconcile/coalesce updates if multiple changes happened at once. This would also mean changes to acc A queue cache updates for accs B, C, D ... instead of our existing paradigm where changes to acc A queue updates for acc A only. Maybe we've already diverged from that though I dunno.

I don't know what to do about this. Sending cached lines every time we reflow seems bad for the same reason that sending bounds every time we reflow is bad. (That's why we cache bounds in LocalAccessible.) But caching lines in LocalAccessible as well seems really horrible.

I guess we could get the points for the first and last characters of the leaf and compare those. That's perhaps better than caching all the line starts, but it still means caching additional stuff in LocalAccessible.

Yeah this is immediately where my mind went. That, or caching the "empty" space within the bounds and checking if that changes? That's still (potentially) quite a lot of bookkeeping, and something we don't currently have logic for.

Any thoughts, Morgan? I'm not asking you to come up with a solution here, more just to check my thinking in case I've missed something or if anything comes to mind without digging too much. Can we do polygons? :)

You joke ;) but yeah, technically we could -- we've got a class for that. That class also has a nice BoundingBox() function, meaning if we decide to use Polygons internally, we can still easily send clients the rects they expect. Looks like for things that are actually rects (ie. text bounds that aren't multiline, and individual char bounds) we can just call Polygon::FromRect. Right now, we rely on the underlying nsTextFrame of a TextLeafAccessible to create its (cached) parent-relative bounds. If we're moving towards polygons, we'd want to override LocalAccessible::ParentRelativeBounds in TextLeafAccessible and do something similar to what I'm doing in the while/for loop in HyperTextAccessibleBase::TextBounds . Instead of creating a line rect, and then unioning that into result, we'd create a line rect, turn it into a polygon with FromRect(), and then (create and) call a union function. There's probably a way to avoid duplicating too much of the code, like I mentioned in the patch, that TextBounds loop should ultimately live in TextLeafRange, probably.

Famous last words but, seems doable if that's the route that makes the most sense 😀

Comment 8

[James Teh [:Jamie]]

(In reply to Morgan Reschenberg [:morgan] from comment #7)

So your point is the bounds (er, bounding rect, what we get from Bounds()) for the final text leaf wouldn't change, so we can't rely on that as an indicator to update our lineStarts array? Just wanna make sure I have this right 😀

Correct. :)

I wonder if you could use text length to help with this. It seems like lineStarts would only be affected (a) in the leaf an insertion or deletion occurred in and (b) any leaves after that in the reading order that don't force a line break themselves. Is that fair to say?

Yes. Text length probably isn't enough - I think some characters consume more space than others, especially when you deal with compound characters like emoji - so I think we'd need to assume that any text change affects all the wrapped lines thereafter.

And, if we keep track of where "hard" linebreaks occur, that could narrow the range further.

Yeah, I hadn't thought about tracking the hard line breaks. Though I wonder how expensive those repeated traversals would get, especially if we don't cache hard line breaks. And if we do cache hard line breaks, we're back to using more memory.

All that said, thanks for your thoughts. I at least feel more comfortable I'm not missing some cleaner solution. :)

Comment 9

[James Teh [:Jamie]]

So it turns out that layout fires text update notifications to a11y when text gets reflowed due to line wrapping changes. The text doesn't actually change, but we still get the notification. That means we don't actually have to worry about any of this non-rectangular text stuff. I couldn't fathom that before due to bug 1766560, which was messing up my testing.

Sorry for the unnecessary mind melt.

Comment 10

[James Teh [:Jamie]]

We don't get those notifications for br elements though, so we still need to do the bounds check there. But that's fairly straightforward; br elements are always rectangular.

Comment 11

[James Teh [:Jamie]]

(In reply to James Teh [:Jamie] from comment #9)

So it turns out that layout fires text update notifications to a11y when text gets reflowed due to line wrapping changes.

Sadly, that's not always true. It only seems to do this for a focused contentEditable. So we're back to ugliness.

Comment 12

[James Teh [:Jamie]]

Attachment: Bug 1739560: Update line starts in the cache when they change.

If text or bounds change, it's very likely that line starts have changed too, so we push an update for them.
However, if a non-rectangular text span changes its line wrapping without changing its text, the bounds might not change.
In that case, we still get a bounds cache update request; we just determine not to push bounds.
This happens a lot, though.
To limit this, we compare against the cached first line start in LocalAccessible and push an update only if it's different.

If text and bounds both change, we don't want to push two separate cache updates.
We use queued cache updates to prevent this.
This necessitated moving where we send queued cache updates so that we do it before firing mutation events, since clients might need the text to be up to date when handling those events.

Comment 13

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/7891234e69fb
Update line starts in the cache when they change. r=morgan

Comment 14

[Atila Butkovits]

https://hg.mozilla.org/mozilla-central/rev/7891234e69fb