Closed Bug 1735970 (a11y-ctw-tables) Opened 1 year ago Closed 8 months ago

New table implementation which can work with the cache

Categories

(Core :: Disability Access APIs, task)

task

Tracking

()

RESOLVED FIXED
100 Branch
Tracking Status
firefox100 --- fixed

People

(Reporter: Jamie, Assigned: Jamie)

References

(Blocks 3 open bugs)

Details

(Whiteboard: [ctw-m1])

Attachments

(20 files)

48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review

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).

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

Whiteboard: [ctw-m1]
Depends on: 1686391
Blocks: 1686391
No longer depends on: 1686391

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.

Assignee: nobody → jteh
Keywords: meta
Summary: [meta] Cache table information → New table implementation which can work with the cache
Blocks: 1591326

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

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.

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.

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

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

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

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.

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

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.

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.

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.

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.

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.

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.

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

Attachment #9268034 - Attachment description: Bug 1735970 part 4: Add methods to unify querying an Accessible's id and retrieval of an Accessible from a document given an id. → Bug 1735970 part 2: Add methods to unify querying an Accessible's id and retrieval of an Accessible from a document given an id.
Attachment #9268032 - Attachment description: Bug 1735970 part 2: Add TableAccessibleBase and TableCellAccessibleBase. → Bug 1735970 part 3: Add TableAccessibleBase and TableCellAccessibleBase.
Attachment #9268033 - Attachment description: Bug 1735970 part 3: Introduce CachedTableAccessible and CachedTableCellAccessible. → Bug 1735970 part 4: Introduce CachedTableAccessible and CachedTableCellAccessible.
Attachment #9268031 - Attachment description: Bug 1735970 part 1: Unify ConvertToNSArray to take an array of Accessible*. → Bug 1735970 part 1: Templatise ConvertToNSArray so it can take an array of Accessible*.
Blocks: 1760735
Pushed by jteh@mozilla.com:
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

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

Flags: needinfo?(jteh)

: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.

Flags: needinfo?(jteh) → needinfo?(sphink)

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.

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.

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.)

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.)

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.

(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.)

Flags: needinfo?(sphink)
Attachment #9270169 - Attachment description: Bug 1735970 - Remove assert to allow covariant return value fixup thunks → Bug 1735970 - Remove assert to allow covariant return value fixup thunks, r=jonco
Pushed by sfink@mozilla.com:
https://hg.mozilla.org/integration/autoland/rev/f853e437a975
[hazards] Update sixgill to fix covariant return value problem

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

Keywords: leave-open

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.

Keywords: leave-open
Pushed by jteh@mozilla.com:
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

Thanks for fixing the hazard issue, :sfink.

Depends on: 1766514
Regressions: 1772476
Blocks: 1723195
Blocks: 789253
Regressions: 1794719
You need to log in before you can comment on or make changes to this bug.