1732674 - Make nsLineIterator a lightweight wrapper for nsLineList_iterator, not an auxiliary array

Status: RESOLVED FIXED

(Core :: Layout: Block and Inline, defect)

Description

[Jonathan Kew [:jfkthame]]

Currently, when we create an nsLineIterator for a block that contains a list of lines, this involves counting the lines (walking the entire line list), allocating an array, and copying the line pointers into it. So for a large block, this is a bit expensive both in time (to walk the line list twice) and space (to allocate the auxiliary array).

If we then used this array to do a lot of random access by line number, that would be worthwhile -- but looking at how we actually use the nsLineIterator, that's not the case. Generally, once we've done all that work to create it, we then do a FindLineContaining call, which iterates through the array to find the target frame, followed by GetLine to retrieve info about the found line index.

We could have instead found the target during the initial iteration over the lines, without any need for the auxiliary array to be created.

Any further access usually involves iterating through the lines either forwards or backwards, one at a time. So again, we don't need a random-access array; following the nsLineList links to preceding or following lines will work fine.

Therefore, I propose to scrap the auxiliary array in nsLineIterator, and instead make it a thin wrapper around nsLineList_iterator, working directly on the linked list of lines. This will be no more expensive for the use patterns we have, and avoids the up-front time and space cost of initializing it.

Comment 1

[Jonathan Kew [:jfkthame]]

Attachment: Bug 1732674 - Make nsLineIterator a lightweight wrapper for an nsLineList_iterator instead of building a separate array. r=#layout-reviewers

Comment 2

[Jonathan Kew [:jfkthame]]

Profiles showing the effect of this on repeated down-arrow keypresses in a huge contenteditable area (tested on macOS):

current: https://share.firefox.dev/3zLLd0A
patched: https://share.firefox.dev/3uetr5h

Testcase: load the 40MB logfile from bug 1725555, and set contentEditable on the <pre> element containing the contents; then put the cursor at the start of document, and hold the down-arrow key to auto-repeat a "next line" cursor movement.

The profiles show that without the patch, it's handling just under 4 next-line events per second (and nsLineIterator initialization is overwhelmingly the heaviest function); with the patch, it handles 6 events per second.

Comment 3

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/43d9f690a94f
Make nsLineIterator a lightweight wrapper for an nsLineList_iterator instead of building a separate array. r=emilio

Comment 4

[Atila Butkovits]

https://hg.mozilla.org/mozilla-central/rev/43d9f690a94f

Comment 5

[Cristian Tuns]

Backed out to fix nsLineIterator crashes (Bug 1733047)

• Backout link

Comment 6

[Cristian Tuns]

Backout merged to central: https://hg.mozilla.org/mozilla-central/rev/744d1f488261

Comment 7

[Jonathan Kew [:jfkthame]]

Oh, I see how this would crash: if the line list is empty, nsLineIterator gets initialized with index=0 but is not in fact pointing to a valid line (because there isn't one); GetLineAt() will then return a bogus pointer. We need to recognize the case of an empty list and ensure the iterator never tries to return a line from it, even at index 0.

Comment 8

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/a4ebb978f792
Make nsLineIterator a lightweight wrapper for an nsLineList_iterator instead of building a separate array. r=emilio

Comment 9

[Marian-Vasile Laza]

https://hg.mozilla.org/mozilla-central/rev/a4ebb978f792

Comment 10

[Alexandru Michis [:malexandru]]

Backed out changeset a4ebb978f792 (Bug 1732674) for causing layout crashes (Bug 1733047). a=backout
Backout link: https://hg.mozilla.org/mozilla-central/rev/85b7b3d04d9f249418325f02d4b93046724b496b
Autoland backout link: https://hg.mozilla.org/integration/autoland/rev/85b7b3d04d9f249418325f02d4b93046724b496b

Comment 11

[Jonathan Kew [:jfkthame]]

Sigh -- so comment 7 wasn't the whole story, I guess. Leaving this until after the 94 soft-freeze at this point....

Comment 12

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/ce929d9e000a
Make nsLineIterator a lightweight wrapper for an nsLineList_iterator instead of building a separate array. r=emilio

Comment 13

[Iulian Moraru]

https://hg.mozilla.org/mozilla-central/rev/ce929d9e000a

Comment 14

[Pulsebot]

Backout by [e-mail]:
https://hg.mozilla.org/mozilla-central/rev/e4581e1d6e4b
Backed out changeset ce929d9e000a for causing nsLineIterator::FindLineContaining crashes (bug 1733047) . a=aryx

Comment 15

[Jonathan Kew [:jfkthame]]

Ugh.... still flaky, apparently. :-( Unfortunately I still haven't been able to reproduce the bug 1733047 (or bug 1733553) crash locally at all, which is making it hard to track down the root cause here.

Comment 16

[Emilio Cobos Álvarez (:emilio)]

Attachment: Bug 1732674 - Assert on tree mutations. r=jfkthame

This should hopefully help catch misuse. Fix an iterator that was living
for too long in ScrollIntoView.

Comment 17

[Emilio Cobos Álvarez (:emilio)]

I think comment 16 is worth a shot.

Comment 18

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/f529288a6dde
Make nsLineIterator a lightweight wrapper for an nsLineList_iterator instead of building a separate array. r=emilio
https://hg.mozilla.org/integration/autoland/rev/730555699380
Assert on tree mutations. r=jfkthame

Comment 19

[Marian-Vasile Laza]

https://hg.mozilla.org/mozilla-central/rev/f529288a6dde
https://hg.mozilla.org/mozilla-central/rev/730555699380

Comment 20

[Jonathan Kew [:jfkthame]]

The nsLineIterator crashes under HyperTextAccessible::CaretLineNumber() in bug 1733047 came right back, so we'll be backing this out again. :-(

Comment 21

[Norisz Fay [:noriszfay]]

Backed out 2 changesets (Bug 1732674) for line iterator crashes (Bug 1733047) a=backout

Backout link: https://hg.mozilla.org/mozilla-central/rev/e45ba61007d1f8771179c0cc258166930acd75a5

Comment 22

[Jonathan Kew [:jfkthame]]

In #developers:mozilla.org today, Itiel reports hitting the crash on https://web.whatsapp.com/:

It requires a login.. sort of. You need to pair the mobile WhatsApp version with the desktop one (in the url mentioned above), and after 2-3 minutes of use it crashes with the above signature
I don't have an exact STR though

Not having a whatsapp device, I'm not in a position to try and reproduce/debug this right now; Emilio, any chance you're able to try it?

Comment 23

[Emilio Cobos Álvarez (:emilio)]

I can give that a shot. Fwiw Itiel had a11y unexpectedly enabled, he should probably file that.

Comment 24

[Emilio Cobos Álvarez (:emilio)]

I force-enabled a11y and tried to reproduce, but couldn't... Itiel, do you know what should I do to repro this?

Comment 25

[Itiel]

I do not :-(
I can try to get a specific STR (it wasn't too hard for me to get it to crash last time I tried), but as the patch was backed out of central I guess this won't reproduce anymore.. unless a Try build can be generated for me to test? (I don't have dev environment set up on that machine so I can't just moz-phab patch to it)

Comment 26

[Emilio Cobos Álvarez (:emilio)]

https://treeherder.mozilla.org/jobs?repo=try&revision=dd4ffd576f3ec96ea68095069d49d0b5b8fec381 should have builds (there's some cert error it seems but we can retrigger if needed).

Comment 27

[Jonathan Kew [:jfkthame]]

In bug 1733553, the reporter was seeing this problem with Fastmail, so that may be another avenue to explore. (Though I wasn't able to reproduce the crash using fastmail when I tried locally, so it's not at all guaranteed...)

@Itiel, if you can come up with any more specific STR, that would be awesome; for now I'm at a loss how to debug this.

Comment 28

[Itiel]

I've tried the Try build both with a clean profile and with a clone of my current profile on the laptop this crashed on, with no success :(
Not sure what I'm missing here...

Comment 29

[blinky]

I can reproduce the crash.

Steps to reproduce:

1. Run Magnify.exe
2. Open this page.
3. Double-click on the video.

See https://youtu.be/QUvkcqxJVnE

Crash report: bp-6c4a095a-2306-4a52-a97d-d53570211108

Comment 30

[Emilio Cobos Álvarez (:emilio)]

Awesome, thanks a lot blinky! I'll try to repro myself, but fyi jonathan in case you get to it sooner.

Comment 31

[Emilio Cobos Álvarez (:emilio)]

Curious, does that crash happen only with the try build? Or does it happen on current Nightly too? Thanks.

Comment 32

[Jonathan Kew [:jfkthame]]

It reproduces for me with the try build, and not with Nightly. I'll see if I can pin down what's broken...

Comment 33

[blinky]

I can reproduce only with the try build.

Comment 34

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/a4796678352c
Make nsLineIterator a lightweight wrapper for an nsLineList_iterator instead of building a separate array. r=emilio
https://hg.mozilla.org/integration/autoland/rev/51e1fef63b7b
Assert on tree mutations. r=jfkthame

Comment 35

[Cristina Cozmuta (:CrissCozmuta)]

https://hg.mozilla.org/mozilla-central/rev/a4796678352c
https://hg.mozilla.org/mozilla-central/rev/51e1fef63b7b