1735970 - (a11y-ctw-tables) New table implementation which can work with the cache

Status: RESOLVED FIXED

(Core :: Disability Access APIs, task)

Description

[James Teh [:Jamie]]

As part of the Cache the World project, we need to be able to cache table information from content processes in the parent process.

Trying to calculate counts, indexes, headers, etc. in the content process and send them up to the parent process would be very expensive and difficult to keep updated after mutations. Instead, we will send only what is absolutely necessary (spans and explicitly associated headers). We will then lazily create a cache data structure only when table information is requested by a client, looping through the entire table and calculating all the information we need. Whenever there is a mutation of the table structure, we throw away the entire cache, rebuilding it next time the client requests information. While building the cache is expensive, this ends up being a lot cheaper than continually trying to calculate the information we need on every client request. In addition, there are certain things that are very difficult (if not impossible) to implement without walking the entire table; e.g. handling row spans.

Aside from supporting CTW, this allows us to finally eliminate our dependency on layout for table info (bug 1686391), resolving a lot of dependent bugs, and make ARIA tables faster (bug 1591326).

Comment 1

[James Teh [:Jamie]]

We will need this for Android, so ctw-m1.

Comment 2

[James Teh [:Jamie]]

I've done all the work here in one chunk, since it required an entirely new table implementation. I'll update comment 0 with more info.

Comment 3

[James Teh [:Jamie]]

Attachment: Bug 1735970 part 1: Templatise ConvertToNSArray so it can take an array of Accessible*.

Previously, there were variants for LocalAccessible and RemoteAccessible, but they did exactly the same thing anyway.

Comment 4

[James Teh [:Jamie]]

Attachment: Bug 1735970 part 3: Add TableAccessibleBase and TableCellAccessibleBase.

These are needed to support RemoteAccessible tables.
Stuff specific to LocalAccessible is still in TableAccessible and TableCellAccessible, which now inherit from the new Base classes.

Covariant return types have been used to minimise changes in LocalAccessible callers.

Comment 5

[James Teh [:Jamie]]

Attachment: Bug 1735970 part 4: Introduce CachedTableAccessible and CachedTableCellAccessible.

This is a completely new table implementation which can work with the cache.
We lazily create a cache data structure only when table information is requested by a client, looping through the entire table and calculating all the information we need (counts, coordinates, implicit headers, etc.).
Whenever the cache is invalidated due to a mutation of the table structure, we throw away the entire cache, rebuilding it next time the client requests information.

Comment 6

[James Teh [:Jamie]]

Attachment: Bug 1735970 part 2: Add methods to unify querying an Accessible's id and retrieval of an Accessible from a document given an id.

There is no base class for local (DocAccessible) and remote (DocAccessibleParent) documents, so this adds nsAccUtils::GetAccessibleByID.

Comment 7

[James Teh [:Jamie]]

Attachment: Bug 1735970 part 5: Use CachedTableAccessible for cached RemoteAccessible.

This gets/creates the CachedTableAccessible when AsTableBase/AsTableCellBase is called.
It also invalidates the table cache when mutations occur.

Comment 8

[James Teh [:Jamie]]

Attachment: Bug 1735970 part 6: Retrieve row/column extent for both local and remote cells.

CachedTableAccessible already knew how to support extents (AKA spans), but it didn't know how to retrieve them yet.

Comment 9

[James Teh [:Jamie]]

Attachment: Bug 1735970 part 7: Make AccIterable::Next return an Accessible.

We need to be able to iterate through explicitly associated headers for both local and remote Accessibles.
AccIterable will serve nicely as a base class, but it needs to support the Accessible base class to do that.

Comment 10

[James Teh [:Jamie]]

Attachment: Bug 1735970 part 8: Enable AccAttributes to store an array of uint64_t.

We need this to cache explicitly associated headers.
This should also be useful later for relations.

Comment 11

[James Teh [:Jamie]]

Attachment: Bug 1735970 part 9: Support explicitly associated headers for both local and remote cells.

Headers are associated using the headers DOM attribute, which is a list of DOM node ids.
For the cache, we send and store these as Accessible ids.

Comment 12

[James Teh [:Jamie]]

Attachment: Bug 1735970 part 10: Cache whether a table is probably a layout table.

Comment 13

[James Teh [:Jamie]]

Attachment: Bug 1735970 part 11: Use CachedTableAccessible for LocalAccessible tables if the cache is enabled.

This allows us to test CachedTableAccessible against our mochitest suite.
We'll eventually want to switch LocalAccessible to use this anyway, as it provides advantages beyond support for cached RemoteAccessibles.
This also ensures the experience is consistent between local and remote.

Comment 14

[James Teh [:Jamie]]

Attachment: Bug 1735970 part 12: Implement selection setter methods in CachedTableAccessible for LocalAccessibles.

This just redirects to the local TableAccessible methods.
This allows us to test selection in our mochitests.
As far as I know, real clients don't actually use these methods , so they haven't been implemented for cached RemoteAccessibles yet.

Comment 15

[James Teh [:Jamie]]

Attachment: Bug 1735970 part 13: Support TableAccessibleBase and TableCellAccessibleBase in XPCOM.

This doesn't work for non-cached RemoteAccessibles, but this wasn't previously implemented anyway.
With this patch (and all earlier patches in the stack) applied, all the tests in accessible/tests/mochitest pass with the cache enabled, thus testing CachedTableAccessible.

Comment 16

[James Teh [:Jamie]]

Attachment: Bug 1735970 part 14: Support TableAccessibleBase and TableCellAccessibleBase on Windows.

Comment 17

[James Teh [:Jamie]]

Attachment: Bug 1735970 part 15: Support TableAccessibleBase and TableCellAccessibleBase for ATK.

We can use the base classes for both local and cached remote Accessibles.
However, non-cached RemoteAccessibles need to be handled separately still because we can't implement the table interfaces for those.

Comment 18

[James Teh [:Jamie]]

Attachment: Bug 1735970 part 16: Support TableAccessibleBase and TableCellAccessibleBase on Mac.

We can use the base classes for both local and cached remote Accessibles.
However, non-cached RemoteAccessibles need to be handled separately still because we can't implement the table interfaces for those.

Comment 19

[James Teh [:Jamie]]

Attachment: Bug 1735970 part 17: Load a11y browser test snippets in standards mode instead of quirks mode.

This is needed to make rowspan="0" work, as this is ignored in quirks mode.

Comment 20

[James Teh [:Jamie]]

Attachment: Bug 1735970 part 18: Add browser tests to exercise table support for both local and remote Accessibles.

Comment 21

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/e506a5b04bf4
part 1: Templatise ConvertToNSArray so it can take an array of Accessible*. r=morgan
https://hg.mozilla.org/integration/autoland/rev/d82660fb5408
part 2: Add methods to unify querying an Accessible's id and retrieval of an Accessible from a document given an id. r=morgan
https://hg.mozilla.org/integration/autoland/rev/6d0f4821ddcf
part 3: Add TableAccessibleBase and TableCellAccessibleBase. r=morgan
https://hg.mozilla.org/integration/autoland/rev/b17a1182539b
part 4: Introduce CachedTableAccessible and CachedTableCellAccessible. r=morgan
https://hg.mozilla.org/integration/autoland/rev/00f1fbedc774
part 5: Use CachedTableAccessible for cached RemoteAccessible. r=morgan
https://hg.mozilla.org/integration/autoland/rev/003bbf7f5f24
part 6: Retrieve row/column extent for both local and remote cells. r=morgan
https://hg.mozilla.org/integration/autoland/rev/cf84daf9e40f
part 7: Make AccIterable::Next return an Accessible. r=morgan
https://hg.mozilla.org/integration/autoland/rev/9e2e11ea1a3d
part 8: Enable AccAttributes to store an array of uint64_t. r=morgan
https://hg.mozilla.org/integration/autoland/rev/50a2ee53b763
part 9: Support explicitly associated headers for both local and remote cells. r=morgan
https://hg.mozilla.org/integration/autoland/rev/d498d61c8f5a
part 10: Cache whether a table is probably a layout table. r=morgan
https://hg.mozilla.org/integration/autoland/rev/5dbfbf341ff8
part 11: Use CachedTableAccessible for LocalAccessible tables if the cache is enabled. r=morgan
https://hg.mozilla.org/integration/autoland/rev/945ef21895ec
part 12: Implement selection setter methods in CachedTableAccessible for LocalAccessibles. r=morgan
https://hg.mozilla.org/integration/autoland/rev/16ac3bec2412
part 13: Support TableAccessibleBase and TableCellAccessibleBase in XPCOM. r=morgan
https://hg.mozilla.org/integration/autoland/rev/3e4697e57570
part 14: Support TableAccessibleBase and TableCellAccessibleBase on Windows. r=morgan
https://hg.mozilla.org/integration/autoland/rev/30f61cdfd3c0
part 15: Support TableAccessibleBase and TableCellAccessibleBase for ATK. r=morgan
https://hg.mozilla.org/integration/autoland/rev/7e48716784d2
part 16: Support TableAccessibleBase and TableCellAccessibleBase on Mac. r=morgan
https://hg.mozilla.org/integration/autoland/rev/73c93a18f65b
part 17: Load a11y browser test snippets in standards mode instead of quirks mode. r=morgan
https://hg.mozilla.org/integration/autoland/rev/e7af2be486ce
part 18: Add browser tests to exercise table support for both local and remote Accessibles. r=morgan

Comment 22

[Cristina Cozmuta (:CrissCozmuta)]

Backed out for causing hazard bustages. CLOSED TREE

Backout link: https://hg.mozilla.org/integration/autoland/rev/f32acad83e867678efa786e344fbdcda5ed8f954

Push with failures : https://treeherder.mozilla.org/jobs?repo=autoland&resultStatus=testfailed%2Cbusted%2Cexception%2Crunnable&revision=e7af2be486ce42bc3d9c0424121ab4ee34a83bb5&selectedTaskRun=J-SMqb4mRV2cRwyxixEycg.0

Link to failure log:
https://treeherder.mozilla.org/logviewer?job_id=372028980&repo=autoland&lineNumber=14535
https://treeherder.mozilla.org/logviewer?job_id=372027848&repo=autoland&lineNumber=14443

Failure messages:
gmake[4]: *** Deleting file 'AccessibleWrap.o'
gmake[4]: *** [/builds/worker/checkouts/gecko/config/rules.mk:660: AccessibleWrap.o] Error 1

gmake[4]: *** Deleting file 'DocAccessibleChild.o'
gmake[4]: *** [/builds/worker/checkouts/gecko/config/rules.mk:659: DocAccessibleChild.o] Error 1

Comment 23

[James Teh [:Jamie]]

:sfink, are you able to help me figure out what's going on here? We get this:
internal compiler error: in XIL_GetFunctionFields, at type.c:597
for this line of code:
virtual ~RelatedAccIterator() {}
I think the patch in question is this patch. While I did touch the base class, I didn't touch RelatedAccIterator. Also,in both cases, we had raw pointers, though LocalAccessible supports ref-counting and Accessible doesn't.

Comment 24

[James Teh [:Jamie]]

We don't really need the ~RelatedAccIterator destructor, since the base class destructor is already virtual (and so I think it should handle destroying fields in subclasses without a default destructor being explicitly defined). So, I removed that and that instance of the error went away. However, we then get the same error in TableAccessible::Caption (from this patch). I can't remove that one because although it just returns null like the base class implementation, it is a covariant return type, which is needed in order for callers to work as expected.

Comment 25

[James Teh [:Jamie]]

Moving these functions into the cpp file so there's a separate declaration and definition seems to help; this try run shows we got past the TableAccessible::Caption problem, but there are still a bunch more. This feels pretty extreme, though, and it's a long tail of work.

Comment 26

[Steve Fink [:sfink] [:s:]]

I'm back now, and should be able to track this down. I'd definitely prefer not causing the code to be written differently just for the sake of the hazard analysis. Usually things like this just mean that the code has managed to trigger a rare construct or optimization that hadn't been hit previously, and it's just a matter of slightly expanding what sixgill is expecting to see (the compiler's output is severely underdocumented, so I can't just write to a spec or anything.)

Comment 27

[Steve Fink [:sfink] [:s:]]

Whoa, weird. It's unhappy with virtual mozilla::a11y::RelatedAccIterator::Next() because it is overriding the virtual method but finding it at a different place in the vtable in the subclass than it found it in the base class.

Base class: virtual mozilla::a11y::AccIterable::Next() found at index 2.

Subclass: virtual mozilla::a11y::RelatedAccIterator::Next() found at index 3.

When constructing the vtable for the subclass, slot 2 was used for a thunk. Thunks don't get an index in their gcc tree representation, because they're never called. (I don't actually know what I'm talking about, I'm just repeating what I've gleaned from comments and am writing this down for my tomorrow self.)

Comment 28

[James Teh [:Jamie]]

Maybe a thunk gets used for covariant return types? AccIterable::Next returns an Accessible*, but RelatedAccIterator::Next returns a LocalAccessible*. That is legal and deliberate, but perhaps why the compiler has to do strange things here.

If that's the case, though, I wonder why LocalAccessible::EmbeddedChildAt didn't trigger this problem. It also uses a covariant return type and I landed that a while back.

Comment 29

[Steve Fink [:sfink] [:s:]]

Attachment: Bug 1735970 - Remove assert to allow covariant return value fixup thunks, r=jonco

Comment 30

[Steve Fink [:sfink] [:s:]]

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

Maybe a thunk gets used for covariant return types? AccIterable::Next returns an Accessible*, but RelatedAccIterator::Next returns a LocalAccessible*. That is legal and deliberate, but perhaps why the compiler has to do strange things here.

Yes, you are correct.

It requires not just a covariant return type, but also that the return type is a non-primary base type (the primary base type is the one that shares the pointer value with the derived type).

Specifically, in this new case LocalAccessible inherits from both nsISupports and Accessible. RelatedAccIterator::Next returns a pointer to a LocalAccessible, which must be cast to Accessible* if called through a base class pointer, and that cast needs the thunk to adjust the returned pointer's value.

If that's the case, though, I wonder why LocalAccessible::EmbeddedChildAt didn't trigger this problem. It also uses a covariant return type and I landed that a while back.

That is a very good point! It does look like it's doing exactly the same thing.

I may try to track that down, but for now, it appears that all I need to do here is remove an assert. (Well, not exactly -- I also need to make it do the same thing as it does in the non-asserting code path. But it's still just removing code.)

Comment 31

[Steve Fink [:sfink] [:s:]]

Attachment: Bug 1735970 - [hazards] Update sixgill to fix covariant return value problem

Comment 32

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/f853e437a975
[hazards] Update sixgill to fix covariant return value problem

Comment 33

[Steve Fink [:sfink] [:s:]]

Oops, sorry, I should've used a separate bug. Marking [leave-open].

Comment 34

[Steve Fink [:sfink] [:s:]]

LocalAccessible::EmbeddedChildAt doesn't trigger the same behavior because Accessible is not the primary base of LocalAccessible, so no interfering vtable index gets stored. RelactedAccIterator singly inherits from AccIterable, so it does store the vtable index of Next() when it is encountered.

Comment 35

[Natalia Csoregi [:nataliaCs]]

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

Comment 36

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/71e4a5e4263f
part 1: Templatise ConvertToNSArray so it can take an array of Accessible*. r=morgan
https://hg.mozilla.org/integration/autoland/rev/477c59860bba
part 2: Add methods to unify querying an Accessible's id and retrieval of an Accessible from a document given an id. r=morgan
https://hg.mozilla.org/integration/autoland/rev/48dc94da9565
part 3: Add TableAccessibleBase and TableCellAccessibleBase. r=morgan
https://hg.mozilla.org/integration/autoland/rev/70a037a8f802
part 4: Introduce CachedTableAccessible and CachedTableCellAccessible. r=morgan
https://hg.mozilla.org/integration/autoland/rev/e9808857d2da
part 5: Use CachedTableAccessible for cached RemoteAccessible. r=morgan
https://hg.mozilla.org/integration/autoland/rev/ab455b33852d
part 6: Retrieve row/column extent for both local and remote cells. r=morgan
https://hg.mozilla.org/integration/autoland/rev/6859eacfcbff
part 7: Make AccIterable::Next return an Accessible. r=morgan
https://hg.mozilla.org/integration/autoland/rev/95a3f5dc2598
part 8: Enable AccAttributes to store an array of uint64_t. r=morgan
https://hg.mozilla.org/integration/autoland/rev/fe03da6ebcdd
part 9: Support explicitly associated headers for both local and remote cells. r=morgan
https://hg.mozilla.org/integration/autoland/rev/ef27332ca35f
part 10: Cache whether a table is probably a layout table. r=morgan
https://hg.mozilla.org/integration/autoland/rev/97435ef5a516
part 11: Use CachedTableAccessible for LocalAccessible tables if the cache is enabled. r=morgan
https://hg.mozilla.org/integration/autoland/rev/44183d0b55a8
part 12: Implement selection setter methods in CachedTableAccessible for LocalAccessibles. r=morgan
https://hg.mozilla.org/integration/autoland/rev/ea9039617803
part 13: Support TableAccessibleBase and TableCellAccessibleBase in XPCOM. r=morgan
https://hg.mozilla.org/integration/autoland/rev/03e98595f217
part 14: Support TableAccessibleBase and TableCellAccessibleBase on Windows. r=morgan
https://hg.mozilla.org/integration/autoland/rev/e807c6507634
part 15: Support TableAccessibleBase and TableCellAccessibleBase for ATK. r=morgan
https://hg.mozilla.org/integration/autoland/rev/d44d0f67bbaa
part 16: Support TableAccessibleBase and TableCellAccessibleBase on Mac. r=morgan
https://hg.mozilla.org/integration/autoland/rev/a1e12cbe28e8
part 17: Load a11y browser test snippets in standards mode instead of quirks mode. r=morgan
https://hg.mozilla.org/integration/autoland/rev/7130953e8f93
part 18: Add browser tests to exercise table support for both local and remote Accessibles. r=morgan

Comment 37

[James Teh [:Jamie]]

Thanks for fixing the hazard issue, :sfink.

Comment 38

[Narcis Beleuzu [:NarcisB]]

https://hg.mozilla.org/mozilla-central/rev/71e4a5e4263f
https://hg.mozilla.org/mozilla-central/rev/477c59860bba
https://hg.mozilla.org/mozilla-central/rev/48dc94da9565
https://hg.mozilla.org/mozilla-central/rev/70a037a8f802
https://hg.mozilla.org/mozilla-central/rev/e9808857d2da
https://hg.mozilla.org/mozilla-central/rev/ab455b33852d
https://hg.mozilla.org/mozilla-central/rev/6859eacfcbff
https://hg.mozilla.org/mozilla-central/rev/95a3f5dc2598
https://hg.mozilla.org/mozilla-central/rev/fe03da6ebcdd
https://hg.mozilla.org/mozilla-central/rev/ef27332ca35f
https://hg.mozilla.org/mozilla-central/rev/97435ef5a516
https://hg.mozilla.org/mozilla-central/rev/44183d0b55a8
https://hg.mozilla.org/mozilla-central/rev/ea9039617803
https://hg.mozilla.org/mozilla-central/rev/03e98595f217
https://hg.mozilla.org/mozilla-central/rev/e807c6507634
https://hg.mozilla.org/mozilla-central/rev/d44d0f67bbaa
https://hg.mozilla.org/mozilla-central/rev/a1e12cbe28e8
https://hg.mozilla.org/mozilla-central/rev/7130953e8f93