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.

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.

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.

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

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

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

Oops, sorry, I should've used a separate bug. Marking [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.

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

Thanks for fixing the hazard issue, :sfink.

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