Bug 193348 – AX: Introduce isolated accessibility tree

• Component: Accessibility
• Status: RESOLVED FIXED

[chris fleizach]

In order to improve performance when requesting the accessibility hierarchy, we introduce the idea of a "static accessibility tree" which could be accessed on a different thread by assistive technologies.

That is accomplished by storing all the data needed to answer accessibility attribute queries in a static object that mirrors the "live" AccessibilityObjects (which interact with both DOM and Render trees).

These static objects are generally created after layout is done and final tasks are being performed. They are then stored in the static tree representation and able to be read from anywhere.

Tactically this is done with AXStaticTreeNodes inside of an AXStaticTreeCache. The TreeNodes implement an AccessibilityObjectInterface shared with AccessibilityObject

This allows the wrappers to access either one depending on conditions and platforms without significant code duplication or re-organization.

This first patch, outline the architecture. The remaining work is 

1) Store remaining attributes that are accessed within the wrappers
2) Allow accessibility to access this static tree on a different thread
3) Handle parameterized attributes that may require sync back to main thread

[Radar WebKit Bug Importer]

<rdar://problem/47203295>

[chris fleizach]

Created attachment 358884 [details]
patch

[chris fleizach]

Created attachment 358885 [details]
patch

[EWS Watchlist]

Attachment 358885 [details] did not pass style-queue:


ERROR: Source/WebCore/accessibility/AXStaticTree/AXStaticTreeCache.h:36:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/WebCore/accessibility/mac/AXObjectCacheMac.mm:33:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/WebCore/accessibility/mac/WebAccessibilityObjectWrapperBase.mm:35:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/WebCore/accessibility/AXStaticTree/AXStaticTreeCache.cpp:79:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/WebCore/accessibility/AXStaticTree/AXStaticTreeCache.cpp:85:  An else if statement should be written as an if statement when the prior "if" concludes with a return, break, continue or goto statement.  [readability/control_flow] [4]
ERROR: Source/WebCore/accessibility/AXObjectCache.cpp:65:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/WebCore/accessibility/AXObjectCache.cpp:65:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/WebCore/accessibility/AXStaticTree/AXStaticTreeNode.h:93:  The parameter name "value" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/WebCore/accessibility/AXStaticTree/AXStaticTreeNode.cpp:28:  Found other header before WebCore config.h. Should be: config.h, primary header, blank line, and then alphabetically sorted.  [build/include_order] [4]
ERROR: Source/WebCore/accessibility/AXStaticTree/AXStaticTreeNode.cpp:29:  Found header this file implements after other header. Should be: config.h, primary header, blank line, and then alphabetically sorted.  [build/include_order] [4]
ERROR: Source/WebCore/accessibility/AXStaticTree/AXStaticTreeNode.cpp:47:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
Total errors found: 11 in 27 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[chris fleizach]

Created attachment 358886 [details]
patch

[EWS Watchlist]

Attachment 358886 [details] did not pass style-queue:


ERROR: Source/WebCore/accessibility/mac/WebAccessibilityObjectWrapperBase.mm:36:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/WebCore/accessibility/AXObjectCache.cpp:35:  Alphabetical sorting problem.  [build/include_order] [4]
Total errors found: 2 in 28 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[chris fleizach]

Created attachment 358896 [details]
patch

[chris fleizach]

Created attachment 358899 [details]
patch

[chris fleizach]

Created attachment 358900 [details]
patch

[Ryosuke Niwa]

Comment on attachment 358900 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=358900&action=review

> Source/WebCore/accessibility/AXObjectCache.cpp:2917
> +RefPtr<AXStaticTreeNode> AXObjectCache::walkAccessibilityTreeForStaticTree(AccessibilityObject* object)

I would call this createStaticAccessibilityTree

> Source/WebCore/accessibility/AXStaticTree/AXStaticTreeCache.cpp:80
> +static bool searchTreeAndReplace(RefPtr<AXStaticTreeNode> searchNode, RefPtr<AXStaticTreeNode> newRoot)

This is a very inefficient way of finding a node in a tree. It basically traverses the entire tree.
Maybe we want to have a HashMap of a state node ID to its node?

> Source/WebCore/accessibility/AXStaticTree/AXStaticTreeCache.cpp:86
> +            children.insert(index, newRoot);

It's problematic that this code can mutate Vector while another thread is accessing Vector.
We probably need a lock around each vector instead.

> Source/WebCore/accessibility/AXStaticTree/AXStaticTreeCache.cpp:101
> +    if (!m_rootNode)
> +        m_rootNode = subRoot;

It's a bit strange that we assume subRoot to be root if m_rootNode is not set.
What guarantees that a subsequent update doesn't create ancestor nodes for m_rootNode?

> Source/WebCore/accessibility/AXStaticTree/AXStaticTreeCache.h:39
> +class AXStaticTreeCache : public RefCounted<AXStaticTreeCache> {

Why not use ThreadSafeRefCounted?

> Source/WebCore/accessibility/AXStaticTree/AXStaticTreeNode.h:42
> +class AXStaticTreeNode final : public AccessibilityObjectInterface, public RefCounted<AXStaticTreeNode> {

Use ThreadSafeRefCounted?

> Source/WebCore/accessibility/AXStaticTree/AXStaticTreeNode.h:44
> +enum class AXPropertyName : int {

Use uint8_t or uint16_t?
Nit: the class content should be indented.

> Source/WebCore/accessibility/AXStaticTree/AXStaticTreeNode.h:51
> +struct AXPropertyHashTraits : WTF::GenericHashTraits<AXPropertyName> {

Use WTF::StrongEnumHashTraits<AXPropertyName> instead?

> Source/WebCore/accessibility/AXStaticTree/AXStaticTreeNode.h:68
> +    static Ref<AXStaticTreeNode> create(AccessibilityObject*);

Use a reference instead of a pointer?
It makes no sense to create a static node when accessibility object is null, right?

> Source/WebCore/accessibility/AXStaticTree/AXStaticTreeNode.h:73
> +    Vector<RefPtr<AXStaticTreeNode>>& children() { return m_children; };

If we want to make this class thread safe, it's problematic that we expose mutable Vector like this.
In fact, reading Vector while another thread is mutating it isn't safe either as I pointed out earlier.

> Source/WebCore/accessibility/AXStaticTree/AXStaticTreeNode.h:78
> +    AccessibilityObjectWrapper* wrapper() const { return m_wrapper.get(); }

Presumably this should be inside PLATFORM(COCOA) as well?

> Source/WebCore/accessibility/AXStaticTree/AXStaticTreeNode.h:103
> +    AXStaticTreeNode* m_parent;

Please use WeakPtr instead of a raw pointer.

> Source/WebCore/accessibility/mac/WebAccessibilityObjectWrapperBase.h:53
> +    WebCore::AXStaticTreeNode* m_staticTreeNode;

Please use WeakPtr or RefPtr.

[chris fleizach]

Comment on attachment 358900 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=358900&action=review

>> Source/WebCore/accessibility/AXStaticTree/AXStaticTreeNode.h:73
>> +    Vector<RefPtr<AXStaticTreeNode>>& children() { return m_children; };
> 
> If we want to make this class thread safe, it's problematic that we expose mutable Vector like this.
> In fact, reading Vector while another thread is mutating it isn't safe either as I pointed out earlier.

I was hoping that we would be able to create the whole tree and then pass it over to the static tree cache and leave it there immutable.

when changes are needed, we would make a new static tree node and pass over that sub-tree (instead of having lots of locks and guaranteeing access from any thread)

do you think that can work?

[Ryosuke Niwa]

(In reply to chris fleizach from comment #11)
> Comment on attachment 358900 [details]
> patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=358900&action=review
> 
> >> Source/WebCore/accessibility/AXStaticTree/AXStaticTreeNode.h:73
> >> +    Vector<RefPtr<AXStaticTreeNode>>& children() { return m_children; };
> > 
> > If we want to make this class thread safe, it's problematic that we expose mutable Vector like this.
> > In fact, reading Vector while another thread is mutating it isn't safe either as I pointed out earlier.
> 
> I was hoping that we would be able to create the whole tree and then pass it
> over to the static tree cache and leave it there immutable.
> 
> when changes are needed, we would make a new static tree node and pass over
> that sub-tree (instead of having lots of locks and guaranteeing access from
> any thread)
> 
> do you think that can work?

Such a design work but it would mean that we can't add or remove any node to an existing static node; because that would mutate the state of the tree. That's not what your patch does currently though.

The most naive approach would result in the re-generation of the entire static AX tree each time. As in we have to create a new static AX node for the entire tree each time. That seems too inefficient.

A more memory/time efficient approach is to re-generate every static AX node whose state had changed and its ancestors (since child-parent relationship needs to be updated). That might be efficient enough.

[Ryosuke Niwa]

Yet another approach is to de-couple child-parent relationship information from actual nodes. So each static AX node only stores readonly immutable data which can be read from any thread, and its values are set exactly once at the time of creation. Then the update step would create a new static AX node for any AX node whose state had changed since the last tree generation. The children and the parent of a static AX tree node are then stored in a separate hash map, which is cloned & updated in each update.

This approach would involve less static AX node generation but more copying & hash table lookups so it may or may not be less efficient than re-generating ancestors.

[Ryosuke Niwa]

Maybe Antti has an idea as to how to manage & update static AX tree.

[chris fleizach]

(In reply to Ryosuke Niwa from comment #13)
> Yet another approach is to de-couple child-parent relationship information
> from actual nodes. So each static AX node only stores readonly immutable
> data which can be read from any thread, and its values are set exactly once
> at the time of creation. Then the update step would create a new static AX
> node for any AX node whose state had changed since the last tree generation.
> The children and the parent of a static AX tree node are then stored in a
> separate hash map, which is cloned & updated in each update.

I think I was trying to go for this sort of model (where nodes are only created for changed states) and then insert those static tree nodes into the tree (behind the lock) when we need to

> 
> This approach would involve less static AX node generation but more copying
> & hash table lookups so it may or may not be less efficient than
> re-generating ancestors.

Yea, I'd also want to avoid anything that relied on big copy operations

[chris fleizach]

(In reply to Ryosuke Niwa from comment #12)
> (In reply to chris fleizach from comment #11)
> > Comment on attachment 358900 [details]
> > patch
> > 
> > View in context:
> > https://bugs.webkit.org/attachment.cgi?id=358900&action=review
> > 
> > >> Source/WebCore/accessibility/AXStaticTree/AXStaticTreeNode.h:73
> > >> +    Vector<RefPtr<AXStaticTreeNode>>& children() { return m_children; };
> > > 
> > > If we want to make this class thread safe, it's problematic that we expose mutable Vector like this.
> > > In fact, reading Vector while another thread is mutating it isn't safe either as I pointed out earlier.
> > 
> > I was hoping that we would be able to create the whole tree and then pass it
> > over to the static tree cache and leave it there immutable.
> > 
> > when changes are needed, we would make a new static tree node and pass over
> > that sub-tree (instead of having lots of locks and guaranteeing access from
> > any thread)
> > 
> > do you think that can work?
> 
> Such a design work but it would mean that we can't add or remove any node to
> an existing static node; because that would mutate the state of the tree.
> That's not what your patch does currently though.

The flow right now is that generateStaticAccessibilityTreeIfNeeded() is called after layout, which makes a new static tree
   (this needs to be updated to only do partial trees -- still a WIP)
- then we stick that into the cache which stores it behind a lock
- later when we access it, we grab the lock first before accessing
- At that point each AXStaticNode is immutable with immutable data

> 
> The most naive approach would result in the re-generation of the entire
> static AX tree each time. As in we have to create a new static AX node for
> the entire tree each time. That seems too inefficient.
> 
> A more memory/time efficient approach is to re-generate every static AX node
> whose state had changed and its ancestors (since child-parent relationship
> needs to be updated). That might be efficient enough.

[Ryosuke Niwa]

> (In reply to Ryosuke Niwa from comment #13)
> > Yet another approach is to de-couple child-parent relationship information
> > from actual nodes. So each static AX node only stores readonly immutable
> > data which can be read from any thread, and its values are set exactly once
> > at the time of creation. Then the update step would create a new static AX
> > node for any AX node whose state had changed since the last tree generation.
> > The children and the parent of a static AX tree node are then stored in a
> > separate hash map, which is cloned & updated in each update.
> 
> I think I was trying to go for this sort of model (where nodes are only
> created for changed states) and then insert those static tree nodes into the
> tree (behind the lock) when we need to

Okay. So the problem is that holding a lock to mutate the tree isn't enough. The thread which is reading / accessing the tree also needs to hold the same lock. Otherwise, the reader can access things while the tree is in a bad state.

One native approach is to have a single global lock for accessing any part of the tree at all. In this exclusive access model, a single lock is held whenever the tree is accessed (for reading) or mutated. This isn't great because it would mean that if accessing the tree or updating the tree takes a significant amount of time, then each thread must wait for the other thread to finish its work.

If we wanted to allow the creation of a new tree / updating of a tree while the existing tree is being accessed from another thread while keeping the tree immutable at any given time, then we need to do something else. As I suggested above, one way to achieve that is to create new ancestors each time a node's state changes, or separate child-parent information into its own data structure.

My gut feeling is that copying ancestors is probably faster just because we tend to have pretty shallow trees, and ancestors tend to converge pretty fast (as in there tend to be more nodes closer to leaves than nodes closer to the root), and the child-parent relationship of the entire tree is probably big.

> > This approach would involve less static AX node generation but more copying
> > & hash table lookups so it may or may not be less efficient than
> > re-generating ancestors.
> 
> Yea, I'd also want to avoid anything that relied on big copy operations

While copying ancestors is probably adequate, using a versioned data structure may avoid all copying. In this approach, each node remembers child-parent for multiple versions; e.g. HashMap of a version number to a Vector of nodes. When a node needs be inserted or removed, a new version of the child node list / parent pointer is created, and only that version has the mutated state. In this model, each node's versioned copy of child-parent relationship needs to have its own lock as a new version is inserted.

The tricky thing about this approach is that we need to know which versions are currently being used, and then discard the old versions as needed, which is quite a bit of code complexity.

[chris fleizach]

(In reply to Ryosuke Niwa from comment #17)
> > (In reply to Ryosuke Niwa from comment #13)
> > > Yet another approach is to de-couple child-parent relationship information
> > > from actual nodes. So each static AX node only stores readonly immutable
> > > data which can be read from any thread, and its values are set exactly once
> > > at the time of creation. Then the update step would create a new static AX
> > > node for any AX node whose state had changed since the last tree generation.
> > > The children and the parent of a static AX tree node are then stored in a
> > > separate hash map, which is cloned & updated in each update.
> > 
> > I think I was trying to go for this sort of model (where nodes are only
> > created for changed states) and then insert those static tree nodes into the
> > tree (behind the lock) when we need to
> 
> Okay. So the problem is that holding a lock to mutate the tree isn't enough.
> The thread which is reading / accessing the tree also needs to hold the same
> lock. Otherwise, the reader can access things while the tree is in a bad
> state.
> 
> One native approach is to have a single global lock for accessing any part
> of the tree at all. In this exclusive access model, a single lock is held
> whenever the tree is accessed (for reading) or mutated. This isn't great
> because it would mean that if accessing the tree or updating the tree takes
> a significant amount of time, then each thread must wait for the other
> thread to finish its work.

This was what I was going for, but I see a flaw in my current code. While we can swap in a static node behind a lock, and retrieve the static root tree behind the lock, we exit the lock protection after retrieving the node (on the other thread). at that point, it's possible the tree could be mutated (behind a lock, but the other thread might be accessibility children() outside that lock)



> 
> If we wanted to allow the creation of a new tree / updating of a tree while
> the existing tree is being accessed from another thread while keeping the
> tree immutable at any given time, then we need to do something else. As I
> suggested above, one way to achieve that is to create new ancestors each
> time a node's state changes, or separate child-parent information into its
> own data structure.
> 
> My gut feeling is that copying ancestors is probably faster just because we
> tend to have pretty shallow trees, and ancestors tend to converge pretty
> fast (as in there tend to be more nodes closer to leaves than nodes closer
> to the root), and the child-parent relationship of the entire tree is
> probably big.
> 
> > > This approach would involve less static AX node generation but more copying
> > > & hash table lookups so it may or may not be less efficient than
> > > re-generating ancestors.
> > 
> > Yea, I'd also want to avoid anything that relied on big copy operations
> 
> While copying ancestors is probably adequate, using a versioned data
> structure may avoid all copying. In this approach, each node remembers
> child-parent for multiple versions; e.g. HashMap of a version number to a
> Vector of nodes. When a node needs be inserted or removed, a new version of
> the child node list / parent pointer is created, and only that version has
> the mutated state. In this model, each node's versioned copy of child-parent
> relationship needs to have its own lock as a new version is inserted.

I think I can make this idea work. We can probably avoid the state where we'd be accessing a vector while being mutated with some appropriate locking

> 
> The tricky thing about this approach is that we need to know which versions
> are currently being used, and then discard the old versions as needed, which
> is quite a bit of code complexity.

[Ryosuke Niwa]

(In reply to chris fleizach from comment #18)
> (In reply to Ryosuke Niwa from comment #17)
> > If we wanted to allow the creation of a new tree / updating of a tree while
> > the existing tree is being accessed from another thread while keeping the
> > tree immutable at any given time, then we need to do something else. As I
> > suggested above, one way to achieve that is to create new ancestors each
> > time a node's state changes, or separate child-parent information into its
> > own data structure.
> > 
> > My gut feeling is that copying ancestors is probably faster just because we
> > tend to have pretty shallow trees, and ancestors tend to converge pretty
> > fast (as in there tend to be more nodes closer to leaves than nodes closer
> > to the root), and the child-parent relationship of the entire tree is
> > probably big.
> > 
> > > > This approach would involve less static AX node generation but more copying
> > > > & hash table lookups so it may or may not be less efficient than
> > > > re-generating ancestors.
> > > 
> > > Yea, I'd also want to avoid anything that relied on big copy operations
> > 
> > While copying ancestors is probably adequate, using a versioned data
> > structure may avoid all copying. In this approach, each node remembers
> > child-parent for multiple versions; e.g. HashMap of a version number to a
> > Vector of nodes. When a node needs be inserted or removed, a new version of
> > the child node list / parent pointer is created, and only that version has
> > the mutated state. In this model, each node's versioned copy of child-parent
> > relationship needs to have its own lock as a new version is inserted.
> 
> I think I can make this idea work. We can probably avoid the state where
> we'd be accessing a vector while being mutated with some appropriate locking

The key for this approach is that multiple versions are maintained; the one being accessed can't change until the entire tree moves to a new version. In theory, we might be able to get away by having two versions; one being accessed, and one being written / updated.

[chris fleizach]

Created attachment 359627 [details]
patch

[chris fleizach]

Created attachment 359628 [details]
patch

[EWS Watchlist]

Attachment 359628 [details] did not pass style-queue:


ERROR: Source/WebKit/Configurations/FeatureDefines.xcconfig:0:  Any changes made to FeatureDefines should be made to all of them (changed file does not match Source/JavaScriptCore/Configurations/FeatureDefines.xcconfig). Use sync-feature-defines if possible.  [featuredefines/equality] [5]
ERROR: Source/WebKit/Configurations/FeatureDefines.xcconfig:0:  Any changes made to FeatureDefines should be made to all of them (changed file does not match Source/WebKitLegacy/mac/Configurations/FeatureDefines.xcconfig). Use sync-feature-defines if possible.  [featuredefines/equality] [5]
ERROR: Source/WebKit/Configurations/FeatureDefines.xcconfig:0:  Any changes made to FeatureDefines should be made to all of them (changed file does not match Tools/TestWebKitAPI/Configurations/FeatureDefines.xcconfig). Use sync-feature-defines if possible.  [featuredefines/equality] [5]
ERROR: Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:33:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/WebCore/PAL/Configurations/FeatureDefines.xcconfig:0:  Any changes made to FeatureDefines should be made to all of them (changed file does not match Source/JavaScriptCore/Configurations/FeatureDefines.xcconfig). Use sync-feature-defines if possible.  [featuredefines/equality] [5]
ERROR: Source/WebCore/PAL/Configurations/FeatureDefines.xcconfig:0:  Any changes made to FeatureDefines should be made to all of them (changed file does not match Source/WebKitLegacy/mac/Configurations/FeatureDefines.xcconfig). Use sync-feature-defines if possible.  [featuredefines/equality] [5]
ERROR: Source/WebCore/PAL/Configurations/FeatureDefines.xcconfig:0:  Any changes made to FeatureDefines should be made to all of them (changed file does not match Tools/TestWebKitAPI/Configurations/FeatureDefines.xcconfig). Use sync-feature-defines if possible.  [featuredefines/equality] [5]
ERROR: Source/WebCore/accessibility/mac/WebAccessibilityObjectWrapperBase.h:33:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/WebCore/Configurations/FeatureDefines.xcconfig:0:  Any changes made to FeatureDefines should be made to all of them (changed file does not match Source/JavaScriptCore/Configurations/FeatureDefines.xcconfig). Use sync-feature-defines if possible.  [featuredefines/equality] [5]
ERROR: Source/WebCore/Configurations/FeatureDefines.xcconfig:0:  Any changes made to FeatureDefines should be made to all of them (changed file does not match Source/WebKitLegacy/mac/Configurations/FeatureDefines.xcconfig). Use sync-feature-defines if possible.  [featuredefines/equality] [5]
ERROR: Source/WebCore/Configurations/FeatureDefines.xcconfig:0:  Any changes made to FeatureDefines should be made to all of them (changed file does not match Tools/TestWebKitAPI/Configurations/FeatureDefines.xcconfig). Use sync-feature-defines if possible.  [featuredefines/equality] [5]
ERROR: Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:38:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/WebCore/accessibility/mac/WebAccessibilityObjectWrapperBase.mm:35:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/WebCore/accessibility/mac/WebAccessibilityObjectWrapperBase.mm:299:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
ERROR: Source/JavaScriptCore/Configurations/FeatureDefines.xcconfig:0:  Any changes made to FeatureDefines should be made to all of them (changed file does not match Tools/TestWebKitAPI/Configurations/FeatureDefines.xcconfig). Use sync-feature-defines if possible.  [featuredefines/equality] [5]
ERROR: Source/WebKitLegacy/mac/Configurations/FeatureDefines.xcconfig:0:  Any changes made to FeatureDefines should be made to all of them (changed file does not match Tools/TestWebKitAPI/Configurations/FeatureDefines.xcconfig). Use sync-feature-defines if possible.  [featuredefines/equality] [5]
ERROR: Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeCache.h:32:  Alphabetical sorting problem.  [build/include_order] [4]
Total errors found: 17 in 27 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[chris fleizach]

Created attachment 359629 [details]
patch

[EWS Watchlist]

Attachment 359629 [details] did not pass style-queue:


ERROR: Source/WebKit/Configurations/FeatureDefines.xcconfig:0:  Any changes made to FeatureDefines should be made to all of them (changed file does not match Tools/TestWebKitAPI/Configurations/FeatureDefines.xcconfig). Use sync-feature-defines if possible.  [featuredefines/equality] [5]
ERROR: Source/WebCore/PAL/Configurations/FeatureDefines.xcconfig:0:  Any changes made to FeatureDefines should be made to all of them (changed file does not match Tools/TestWebKitAPI/Configurations/FeatureDefines.xcconfig). Use sync-feature-defines if possible.  [featuredefines/equality] [5]
ERROR: Source/WebCore/Configurations/FeatureDefines.xcconfig:0:  Any changes made to FeatureDefines should be made to all of them (changed file does not match Tools/TestWebKitAPI/Configurations/FeatureDefines.xcconfig). Use sync-feature-defines if possible.  [featuredefines/equality] [5]
ERROR: Source/JavaScriptCore/Configurations/FeatureDefines.xcconfig:0:  Any changes made to FeatureDefines should be made to all of them (changed file does not match Tools/TestWebKitAPI/Configurations/FeatureDefines.xcconfig). Use sync-feature-defines if possible.  [featuredefines/equality] [5]
ERROR: Source/WebKitLegacy/mac/Configurations/FeatureDefines.xcconfig:0:  Any changes made to FeatureDefines should be made to all of them (changed file does not match Tools/TestWebKitAPI/Configurations/FeatureDefines.xcconfig). Use sync-feature-defines if possible.  [featuredefines/equality] [5]
Total errors found: 5 in 27 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[chris fleizach]

Created attachment 359634 [details]
patch

[EWS Watchlist]

Attachment 359634 [details] did not pass style-queue:


ERROR: Source/WebCore/accessibility/mac/WebAccessibilityObjectWrapperBase.mm:271:  Should not have spaces around = in property synthesis.  [whitespace/property] [4]
Total errors found: 1 in 29 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[chris fleizach]

Created attachment 359635 [details]
patch

[chris fleizach]

Created attachment 359637 [details]
patch

[Ryosuke Niwa]

Comment on attachment 359637 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=359637&action=review

> Source/WebCore/accessibility/AXObjectCache.cpp:2943
> +    root->setIsRootNode(true);

So root node never changes?

> Source/WebCore/accessibility/AXObjectCache.cpp:2945
> +    cache->appendNodeChanges(nodes);

It seems a bit inefficient that all nodes created in the initial tree has to go through the change list.
In fact, there is no need to have each descendent node of the root node go through the change log.
As soon as the root is inserted, the rest appears as a result of them appearing in the tree relationship of the root.
In fact, in any node insertion, its sub tree doesn't need to show up in the change log
as long as all of its sub tree are newly created nodes.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeCache.cpp:110
> +    appendCopy = m_appendChangeLog;

Use WTFMove or std::swap?

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:142
> +    RefPtr<AXIsolatedTreeRelationship> m_relationship;

Since it makes no sense for the true relationship to be empty, why don't we use Ref?

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:143
> +    bool m_isRootNode;

It would pack better in 64-bit if this bool was placed next to AXID.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:149
> +    HashMap<AXPropertyName, AttributeValueVariant, WTF::IntHash<AXPropertyName>, AXPropertyHashTraits> m_attributeMap;

Why don't we put const here since this should never change once the node is created?

[chris fleizach]

(In reply to Ryosuke Niwa from comment #29)
> Comment on attachment 359637 [details]
> patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=359637&action=review
> 
> > Source/WebCore/accessibility/AXObjectCache.cpp:2943
> > +    root->setIsRootNode(true);
> 
> So root node never changes?

Correct

> 
> > Source/WebCore/accessibility/AXObjectCache.cpp:2945
> > +    cache->appendNodeChanges(nodes);
> 
> It seems a bit inefficient that all nodes created in the initial tree has to
> go through the change list.
> In fact, there is no need to have each descendent node of the root node go
> through the change log.
> As soon as the root is inserted, the rest appears as a result of them
> appearing in the tree relationship of the root.
> In fact, in any node insertion, its sub tree doesn't need to show up in the
> change log
> as long as all of its sub tree are newly created nodes.
> 

I still need to get the nodes into the AXID -> Node cache, since the relationships are just AXIDs

I could change the relationships to hold onto the children, however, I think I will still need an AXID -> Node cache so that we can do fast lookup when we need to replace a sub tree, so I'll have to iterate the nodes at some point I think

> > Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeCache.cpp:110
> > +    appendCopy = m_appendChangeLog;
> 
> Use WTFMove or std::swap?
> 
> > Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:142
> > +    RefPtr<AXIsolatedTreeRelationship> m_relationship;
> 
> Since it makes no sense for the true relationship to be empty, why don't we
> use Ref?

Ok

> 
> > Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:143
> > +    bool m_isRootNode;
> 
> It would pack better in 64-bit if this bool was placed next to AXID.
> 

Ok

> > Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:149
> > +    HashMap<AXPropertyName, AttributeValueVariant, WTF::IntHash<AXPropertyName>, AXPropertyHashTraits> m_attributeMap;
> 
> Why don't we put const here since this should never change once the node is
> created?

Ok

[chris fleizach]

Created attachment 359768 [details]
patch

[Ryosuke Niwa]

Comment on attachment 359768 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=359768&action=review

> Source/WebCore/ChangeLog:9
> +        In order to improve performance when requesting the accessibility hierarchy, we introduce the idea of a "static accessibility tree" which could be accessed on a different thread by assistive technologies.

Can we wrap lines at some point earlier?
It's super long. Also rename static -> isolated?

> Source/WebCore/ChangeLog:10
> +        That is accomplished by storing all the data needed to answer accessibility attribute queries in a static object that mirrors the "live" AccessibilityObjects (which interact with both DOM and Render trees).

Ditto.

> Source/WebCore/ChangeLog:11
> +        These static objects are generally created after layout is done and final tasks are being performed. They are then stored in the static tree representation and able to be read from anywhere.

Ditto.

> Source/WebCore/ChangeLog:12
> +        Tactically this is done with AXIsolatedTreeNodes inside of an AXIsolatedTreeCache. The TreeNodes implement an AccessibilityObjectInterface shared with AccessibilityObject

Ditto.

> Source/WebCore/accessibility/AXObjectCache.cpp:2916
> +RefPtr<AXIsolatedTreeNode> AXObjectCache::createStaticAccessibilityTree(AccessibilityObject& object, AXID parentID, AXIsolatedTreeCache& cache, Vector<RefPtr<AXIsolatedTreeNode>>& nodes)

Make this return Ref.

> Source/WebCore/accessibility/AXObjectCache.cpp:2940
> +    RefPtr<AXIsolatedTreeCache> cache = AXIsolatedTreeCache::cacheForPage(m_document.page());

Use auto.

> Source/WebCore/accessibility/AXObjectCache.cpp:2942
> +    RefPtr<AXIsolatedTreeNode> root = createStaticAccessibilityTree(*rootObject(), 0, *cache, nodes);

Ditto. Hm... can we define InvalidAXID or something instead of hard-coding the magic number of 0?

> Source/WebCore/accessibility/AXObjectCache.cpp:2944
> +    

Nit: whitespaces.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeCache.cpp:38
> +HashMap<Page*, RefPtr<AXIsolatedTreeCache>>& AXIsolatedTreeCache::pageRootMap()

I think this map should be a static local variable in AXIsolatedTreeCache::cacheForPage
since any caller of this function would have to grab a lock.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeCache.cpp:69
> +    RefPtr<AXIsolatedTreeCache> cache = pageRootMap().get(page);

This code needs a lock since this function can run concurrently in multiple threads.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeCache.h:48
> +    WEBCORE_EXPORT static RefPtr<AXIsolatedTreeCache> cacheForPage(Page*);

This function should return Ref since it never returns nullptr.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeCache.h:66
> +    static HashMap<Page*, RefPtr<AXIsolatedTreeCache>>& pageRootMap();

Since we never insert a null AXIsolatedTreeCache into this map, it should be Ref<AXIsolatedTreeCache>.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeCache.h:67
> +    static HashMap<AXIsolatedCacheID, RefPtr<AXIsolatedTreeCache>>& treeCache();

Ditto.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeCache.h:70
> +    HashMap<AXID, RefPtr<AXIsolatedTreeNode>> m_cache;

Ditto. Use Ref<AXIsolatedTreeNode>.
Why don't we call this m_readerThreadNodeMap to make the intent clear without a comment?
Also, there is no need to say this is the cache since the entire class is called AXIsolatedTree*Cache*.
But it's almost misleading that this class is called AXIsolatedTree*Cache* since AT exclusively accesses the accessibility tree via this "cache".
I think I would prefer calling this simply AXIsolatedTree altogether.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeCache.h:73
> +    Vector<RefPtr<AXIsolatedTreeNode>> m_appendChangeLog;

Ditto. Also, why don't we call this something like m_pendingAppends to convey
the semantics that these changes haven't taken place yet.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeCache.h:74
> +    Vector<AXID> m_removeChangeLog;

Ditto.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:127
> +    

Nit: Whitespace.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:131
> +    

Ditto.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:134
> +    

Ditto.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:140
> +    

Ditto.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:144
> +    

Ditto.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:148
> +    

Ditto.

> Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:53
> +    WebCore::Page* page = m_page->corePage();

This code is definitely not safe to run in non-main thread.
We can't access WebKit::WebPage in non-main thread.
r- because of this thread safety issue.
One way to make this code more thread safe is to key the mapping based on PageID.

So when WKAccessibilityWebPageObjectBase is created in the main thread, it could store its PageID

> Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:59
> +    

Nit: Whitespace.

> Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:75
>      WebCore::Page* page = m_page->corePage();

It's not safe to access WebCore::Page object in a separate thread like this because page can be deleted meanwhile.

> Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:79
> +    AXObjectCache* cache = [self axObjectCache];

I think this whole logic to get WebCore::Page & accessing the map should be moved to the dispatchBlock below.

> Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:92
> +            dispatch_sync(dispatch_get_main_queue(), dispatchBlock);

Do we really need to dispatch sync?
Can we, for example, dispatch_async then return nil for now until the tree becomes available?
We can keep it this way if an alternative is hard to implement. I was just wondering.

> Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:95
> +    auto isolatedCache = AXIsolatedTreeCache::cacheForPage(page);

This code is definitely not safe to run in non-main thread.
AXIsolatedTreeCache::cacheForPage accesses HashMap which is mutated in the main thread without a lock.
r- because of this thread safety issue. We need a lock in cacheForPage.

> Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:96
> +    if (!isolatedCache) {

It appears to me that this would never be true since we never return nullptr in cacheForPage.

> Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:105
> +    

Nit: whitespace.

[chris fleizach]

(In reply to Ryosuke Niwa from comment #32)
> Comment on attachment 359768 [details]
> patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=359768&action=review
> 
> > Source/WebCore/ChangeLog:9
> > +        In order to improve performance when requesting the accessibility hierarchy, we introduce the idea of a "static accessibility tree" which could be accessed on a different thread by assistive technologies.
> 
> Can we wrap lines at some point earlier?
> It's super long. Also rename static -> isolated?
> 
> > Source/WebCore/ChangeLog:10
> > +        That is accomplished by storing all the data needed to answer accessibility attribute queries in a static object that mirrors the "live" AccessibilityObjects (which interact with both DOM and Render trees).
> 
> Ditto.
> 
> > Source/WebCore/ChangeLog:11
> > +        These static objects are generally created after layout is done and final tasks are being performed. They are then stored in the static tree representation and able to be read from anywhere.
> 
> Ditto.
> 
> > Source/WebCore/ChangeLog:12
> > +        Tactically this is done with AXIsolatedTreeNodes inside of an AXIsolatedTreeCache. The TreeNodes implement an AccessibilityObjectInterface shared with AccessibilityObject
> 
> Ditto.
> 
> > Source/WebCore/accessibility/AXObjectCache.cpp:2916
> > +RefPtr<AXIsolatedTreeNode> AXObjectCache::createStaticAccessibilityTree(AccessibilityObject& object, AXID parentID, AXIsolatedTreeCache& cache, Vector<RefPtr<AXIsolatedTreeNode>>& nodes)
> 
> Make this return Ref.
> 
> > Source/WebCore/accessibility/AXObjectCache.cpp:2940
> > +    RefPtr<AXIsolatedTreeCache> cache = AXIsolatedTreeCache::cacheForPage(m_document.page());
> 
> Use auto.
> 
> > Source/WebCore/accessibility/AXObjectCache.cpp:2942
> > +    RefPtr<AXIsolatedTreeNode> root = createStaticAccessibilityTree(*rootObject(), 0, *cache, nodes);
> 
> Ditto. Hm... can we define InvalidAXID or something instead of hard-coding
> the magic number of 0?
> 
> > Source/WebCore/accessibility/AXObjectCache.cpp:2944
> > +    
> 
> Nit: whitespaces.
> 
> > Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeCache.cpp:38
> > +HashMap<Page*, RefPtr<AXIsolatedTreeCache>>& AXIsolatedTreeCache::pageRootMap()
> 
> I think this map should be a static local variable in
> AXIsolatedTreeCache::cacheForPage
> since any caller of this function would have to grab a lock.
> 
> > Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeCache.cpp:69
> > +    RefPtr<AXIsolatedTreeCache> cache = pageRootMap().get(page);
> 
> This code needs a lock since this function can run concurrently in multiple
> threads.
> 
> > Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeCache.h:48
> > +    WEBCORE_EXPORT static RefPtr<AXIsolatedTreeCache> cacheForPage(Page*);
> 
> This function should return Ref since it never returns nullptr.
> 
> > Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeCache.h:66
> > +    static HashMap<Page*, RefPtr<AXIsolatedTreeCache>>& pageRootMap();
> 
> Since we never insert a null AXIsolatedTreeCache into this map, it should be
> Ref<AXIsolatedTreeCache>.
> 
> > Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeCache.h:67
> > +    static HashMap<AXIsolatedCacheID, RefPtr<AXIsolatedTreeCache>>& treeCache();
> 
> Ditto.
> 
> > Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeCache.h:70
> > +    HashMap<AXID, RefPtr<AXIsolatedTreeNode>> m_cache;
> 
> Ditto. Use Ref<AXIsolatedTreeNode>.
> Why don't we call this m_readerThreadNodeMap to make the intent clear
> without a comment?
> Also, there is no need to say this is the cache since the entire class is
> called AXIsolatedTree*Cache*.
> But it's almost misleading that this class is called AXIsolatedTree*Cache*
> since AT exclusively accesses the accessibility tree via this "cache".
> I think I would prefer calling this simply AXIsolatedTree altogether.
> 
> > Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeCache.h:73
> > +    Vector<RefPtr<AXIsolatedTreeNode>> m_appendChangeLog;
> 
> Ditto. Also, why don't we call this something like m_pendingAppends to convey
> the semantics that these changes haven't taken place yet.
> 
> > Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeCache.h:74
> > +    Vector<AXID> m_removeChangeLog;
> 
> Ditto.
> 
> > Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:127
> > +    
> 
> Nit: Whitespace.
> 
> > Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:131
> > +    
> 
> Ditto.
> 
> > Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:134
> > +    
> 
> Ditto.
> 
> > Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:140
> > +    
> 
> Ditto.
> 
> > Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:144
> > +    
> 
> Ditto.
> 
> > Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:148
> > +    
> 
> Ditto.
> 
> > Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:53
> > +    WebCore::Page* page = m_page->corePage();
> 
> This code is definitely not safe to run in non-main thread.
> We can't access WebKit::WebPage in non-main thread.
> r- because of this thread safety issue.
> One way to make this code more thread safe is to key the mapping based on
> PageID.
> 
> So when WKAccessibilityWebPageObjectBase is created in the main thread, it
> could store its PageID
> 
> > Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:59
> > +    
> 
> Nit: Whitespace.
> 
> > Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:75
> >      WebCore::Page* page = m_page->corePage();
> 
> It's not safe to access WebCore::Page object in a separate thread like this
> because page can be deleted meanwhile.
> 
> > Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:79
> > +    AXObjectCache* cache = [self axObjectCache];
> 
> I think this whole logic to get WebCore::Page & accessing the map should be
> moved to the dispatchBlock below.
> 
> > Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:92
> > +            dispatch_sync(dispatch_get_main_queue(), dispatchBlock);
> 
> Do we really need to dispatch sync?
> Can we, for example, dispatch_async then return nil for now until the tree
> becomes available?
> We can keep it this way if an alternative is hard to implement. I was just
> wondering.

Will work on all these changes. Thanks for review

Per this comment above, we need to return data here on initial usage, otherwise we'll get bugs and VO is going to be flaky if the first access to a webpage always fails. So hard to avoid the dispatch_sync in this case

> 
> > Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:95
> > +    auto isolatedCache = AXIsolatedTreeCache::cacheForPage(page);
> 
> This code is definitely not safe to run in non-main thread.
> AXIsolatedTreeCache::cacheForPage accesses HashMap which is mutated in the
> main thread without a lock.
> r- because of this thread safety issue. We need a lock in cacheForPage.
> 
> > Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:96
> > +    if (!isolatedCache) {
> 
> It appears to me that this would never be true since we never return nullptr
> in cacheForPage.
> 
> > Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:105
> > +    
> 
> Nit: whitespace.

[chris fleizach]

Created attachment 359863 [details]
patch

Did my best to convert to using Ref<> instead of RefPtr<> but had some difficulty with vector copies/swaps because the operator for = for Ref is delete. But that said, I got most of them using Ref.

[EWS Watchlist]

Attachment 359863 [details] did not pass style-queue:


ERROR: Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:68:  An else statement can be removed when the prior "if" concludes with a return, break, continue or goto statement.  [readability/control_flow] [4]
ERROR: Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:133:  An else should appear on the same line as the preceding }  [whitespace/newline] [4]
Total errors found: 2 in 32 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[chris fleizach]

Created attachment 359864 [details]
patch

[chris fleizach]

Created attachment 359879 [details]
patch

[chris fleizach]

Created attachment 359896 [details]
patch

[Ryosuke Niwa]

Comment on attachment 359896 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=359896&action=review

> Source/WebCore/accessibility/AXObjectCache.cpp:734
> +    

Nit: whitespace.

> Source/WebCore/accessibility/AXObjectCache.cpp:2922
> +    nodes.append(isolatedTreeNode.ptr());

Like I mentioned in the previous patch, there is no need to make each node go through the change list.
We can simply insert the root node.

> Source/WebCore/accessibility/AXObjectCache.cpp:2923
> +    

Nit: whitespace.

> Source/WebCore/accessibility/AXObjectCache.cpp:2927
> +    

Ditto.

> Source/WebCore/accessibility/AXObjectCache.cpp:2932
> +    

Ditto.

> Source/WebCore/accessibility/AXObjectCache.cpp:2936
> +Ref<AXIsolatedTree> AXObjectCache::generateStaticAccessibilityTreeIfNeeded()

Given this function is now only called when there is no root node, we should remove IfNeeded suffix.

> Source/WebCore/accessibility/AXObjectCache.cpp:2938
> +    auto tree = AXIsolatedTree::treeForPageID(*m_document.pageID());

Let's release-assert that we're in the main thread here.

> Source/WebCore/accessibility/AXObjectCache.cpp:2941
> +    auto root = createIsolatedAccessibilityTree(*rootObject(), InvalidAXID, tree, nodes);
> +    root->setIsRootNode(true);

There is no need to pass nodes to createIsolatedAccessibilityTree. Since they're already in the tree.

> Source/WebCore/accessibility/AXObjectCache.cpp:2943
> +    

Nit: whitespace.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:67
> +    cacheLock.lock();

Let's use Locker class instead of manually locking & unlocking.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:73
> +    

Nit: whitespace.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:83
> +    if (!axID)

Let's assert that this is not the main thread.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:95
> +    m_changeLogLock.lock();

Let's use Locker.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:102
> +    m_changeLogLock.lock();

Ditto.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:108
> +{

Let's release-assert that we're in the reader thread.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:110
> +    Vector<RefPtr<AXIsolatedTreeNode>> appendCopy(WTFMove(m_pendingAppends));

Use appendCopy { ~ }.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:111
> +    Vector<AXID> removeCopy(WTFMove(m_pendingRemovals));

Ditto.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.h:60
> +    

Nit: whitespace.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.h:62
> +    

Ditto.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.h:67
> +    

Ditto.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.h:70
> +    

Ditto.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.cpp:58
> +    if (shouldRemove)

Let's assert that we're in the main thread here. Otherwise, we'd have a threading bug.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:48
> +class AXIsolatedTreeRelationship : public ThreadSafeRefCounted<AXIsolatedTreeRelationship> {

I think with our new design, we don't need this class to be separated from AXIsolatedTreeNode.
That should result in a slightly better packing and 16 bytes or so of space saved.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:81
> +enum class AXPropertyName : uint16_t {

Please indent the class content. Also, it seems like this can be uint8_t?

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:98
> +    static const bool emptyValueIsZero = false;
> +    static AXPropertyName emptyValue() { return AXPropertyName::None; };
> +    static void constructDeletedValue(AXPropertyName& slot)
> +    {
> +        slot = static_cast<AXPropertyName>(static_cast<int>(AXPropertyName::None) - 1);
> +    }
> +    static bool isDeletedValue(AXPropertyName value)
> +    {
> +        return static_cast<int>(value) == static_cast<int>(AXPropertyName::None) - 1;
> +    }

You shouldn't have to define any of this once you inserted from StrongEnumHashTraits.
In fact, you should be able to just specify WTF::StrongEnumHashTraits<AXPropertyName> where you specify AXPropertyHashTraits.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:109
> +    

Nit: whitespace

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:111
> +    

Ditto.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:114
> +    

Ditto.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:120
> +    void setWrapper(WebAccessibilityObjectWrapper* wrapper)
> +    {
> +        m_wrapper = wrapper;
> +    }

Seems like this can be one-liner?

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:149
> +    // We don't mark this const because even though attributes don't change after initial creation,
> +    // we may copy an existing node and replace specific values,

Okay, you can just put this in change log since it seems like this is a kind of thing that would be obvious once such a code exists.

> Source/WebCore/accessibility/mac/AXObjectCacheMac.mm:244
> +    object.wrapper().isolatedTreeIdentifier = treeID;

Let's assert that object.wrapper().isolatedTreeIdentifier is not already set.

> Source/WebCore/accessibility/mac/AXObjectCacheMac.mm:248
> +    

Nit: whitespace.

> Source/WebCore/accessibility/mac/WebAccessibilityObjectWrapperBase.mm:291
> +    return AXIsolatedTree::treeForID(_isolatedTreeIdentifier)->nodeForID(_identifier);

Can this be called from non-main thread?
If so, we need a lock here.
Otherwise, let's release assert that we're in the main thread in AXIsolatedTree::treeForID

> Source/WebCore/accessibility/mac/WebAccessibilityObjectWrapperBase.mm:306
> +    AXIsolatedTree::treeForID(self.isolatedTreeIdentifier)->applyPendingChanges();
> +    return _identifier;

Ditto.

> Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:72
> +        if (RunLoop::isMain())

Let's use isMainThread() instead since RunLoop::isMain() is problematic in iOS WK1
even though I don't think we have a plan to enable this in WK1?

> Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:75
> +            dispatch_sync(dispatch_get_main_queue(), dispatchBlock);

Let's use callOnMainThreadAndWait instead.

> Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:85
> +    if (!WebCore::AXObjectCache::accessibilityEnabled())
> +        WebCore::AXObjectCache::enableAccessibility();

It seems like this code is technically concurrency ready in most architectures,
it's quite subtle that enableAccessibility() would run in a non-main thread.
Perhaps we should adda comment in AXObjectCache.h around accessibilityEnabled() / enableAccessibility().

> Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:95
> +                tree->applyPendingChanges();

We can't do this in the main thread. The only reason the reader thread can access things fast
is because nobody is touching reader thread's data structure in the main thread.
This invocation of applyPendingChanges in the main thread would violate that invariant.

> Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:99
> +        if (RunLoop::isMain())

Ditto about using isMainThread() instead.

> Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:102
> +            dispatch_sync(dispatch_get_main_queue(), dispatchBlock);

Ditto about using callOnMainThreadAndWait instead.

> Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:108
> +        generateBlock();

After this call to generateBlock, we'd have to call applyPendingChanges in this thread.

[chris fleizach]

Created attachment 360093 [details]
Patch

@Ryosuke, all comments addressed.

[EWS Watchlist]

Attachment 360093 [details] did not pass style-queue:


ERROR: Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:95:  One line control clauses should not use braces.  [whitespace/braces] [4]
Total errors found: 1 in 32 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[chris fleizach]

Created attachment 360097 [details]
patch

[EWS Watchlist]

Attachment 360097 [details] did not pass style-queue:


ERROR: Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:75:  More than one command on the same line  [whitespace/newline] [4]
ERROR: Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:93:  The parameter name "cache" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:100:  More than one command on the same line  [whitespace/newline] [4]
Total errors found: 3 in 32 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Ryosuke Niwa]

Comment on attachment 360097 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=360097&action=review

There is one minor thread issue but the rest looks good.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:46
> +    : m_treeID(++s_treeIDCount)

This isn't right. In the current design, AXIsolatedTree::create() can be invoked in multiple threads.
As such, it's not safe to increment s_treeIDCount without a lock.
I think a simpler design would be to make sure AXIsolatedTree::create is only called in the main thread.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:67
> +    Locker<Lock> locker(cacheLock);

Just use LockHolder which is typedef of Locker<Lock>

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:69
> +    cacheLock.lock();

No need to call lock once you have Locker.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:75
> +    Ref<AXIsolatedTree> newTree = AXIsolatedTree::create();

I think we should change the design and make this function return nullptr when there is no tree.
Then only create AXIsolatedTree in the main thread.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:96
> +    Locker<Lock> locker(m_changeLogLock);

Use LockHolder instead of Locker<Lock>.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:102
> +    Locker<Lock> locker(m_changeLogLock);

Ditto.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:110
> +    m_changeLogLock.lock();

Use LockHolder and invoke unlock() early.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.cpp:39
> +}

Let's also add ASSERT(isMainThread()) here.
Also let's add another member like m_initialized behind #if !ASSERT_DISABLED
which is set to true once initializeAttributeData is called.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.cpp:57
> +    ASSERT(isMainThread());

and then let's assert that m_initialized is false here.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:64
> +    void setIsRootNode(bool value) { m_isRootNode = value; }

Let's assert that this is only called in the main thread.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:66
> +    void setParent(AXID parent) { m_parent = parent; }

Ditto.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:69
> +    Vector<AXID>& children() { return m_children; };

Let's make this return const Vector<AXID>& then add another function like appendChild
which asserts that it's only called in the main thread so that we can be sure that
nobody is trying to mutate this vector in non-main thread.

[chris fleizach]

Created attachment 360161 [details]
patch

[EWS Watchlist]

Attachment 360161 [details] did not pass style-queue:


ERROR: Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:72:  One line control clauses should not use braces.  [whitespace/braces] [4]
ERROR: Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:75:  More than one command on the same line  [whitespace/newline] [4]
ERROR: Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:93:  The parameter name "cache" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:100:  More than one command on the same line  [whitespace/newline] [4]
Total errors found: 4 in 32 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Ryosuke Niwa]

Comment on attachment 360161 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=360161&action=review

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:72
> +    if (auto tree = pageMap.get().get(pageID)) {
> +        return makeRefPtr(tree);
> +    }

Nit: No curly braces around a single line statement.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:75
> +    if (!create)
> +        return nullptr;

I think it's cleaner to have a separate function which creates the tree.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:76
> +    

Nit: whitespace.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:77
> +    RefPtr<AXIsolatedTree> newTree = AXIsolatedTree::create();

Use auto?

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.cpp:42
> +    initializeAttributeData(object);

Oh I mean that set m_initialized AFTER initializeAttributeData.
Otherwise, setProperty in initializeAttributeData would hit its assertion, right?

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.cpp:63
> +    

Nit: whitespace.

> Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:103
> +    auto tree = AXIsolatedTree::treeForPageID(m_pageID);

We need to check null-ness of the tree here.

> Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:106
> +    auto rootNode = tree->rootNode();
> +    if (!rootNode)
> +        generateBlock();

This check is now unnecessary because we'd always create the root node as we create the tree.

> Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:108
> +    tree->applyPendingChanges();

Since it's only safe to invoke this function in the reader thread,
we might as well as assert that we're not in the main thread
instead of having a fallback for the main thread case.

[Simon Fraser (smfr)]

Comment on attachment 360161 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=360161&action=review

> Source/WebCore/accessibility/AXObjectCache.cpp:2919
> +Ref<AXIsolatedTreeNode> AXObjectCache::createIsolatedAccessibilityTree(AccessibilityObject& object, AXID parentID, AXIsolatedTree& tree, Vector<RefPtr<AXIsolatedTreeNode>>& nodes)

Should that be Vector<RefPtr<AXIsolatedTreeNode>>&& if ownership is being transferred.

I'm confused about this function. It's called createIsolatedAccessibilityTree() but it takes a tree, rather than returning a tree. Is it really appending nodes to the tree? Maybe it should have "recursive" in the name too?

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:37
> +static unsigned s_treeIDCount = 0;

Is this a count of IDs? Maybe call it currentTreeID? Would be cleaner to wrap this in a function that provides unique IDs.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:63
> +RefPtr<AXIsolatedTree> AXIsolatedTree::treeForPageID(uint64_t pageID, bool create)

Do you really want a tree per Page? Page outlives navigations, so do you swap out the tree on navigation? What's the lifetime of trees which aren't for the current document?

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:85
> +    ASSERT(!isMainThread());

Can you assert that this is the reader thread?

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.h:49
> +    WEBCORE_EXPORT static RefPtr<AXIsolatedTree> treeForPageID(uint64_t, bool create);

Name uint64_t here.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:63
> +    bool isRootNode() const { return m_isRootNode; }

Can you tell that it's the root node because it has no parent?

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:78
> +    const Vector<AXID>& children() { return m_children; };

Function should be const.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:115
> +    AXID m_parent;
> +    AXID m_identifier;
> +    bool m_isRootNode;
> +    bool m_initialized;
> +    Vector<AXID> m_children;
> +
> +#if PLATFORM(COCOA)
> +    RetainPtr<WebAccessibilityObjectWrapper> m_wrapper;
> +#endif
> +
> +    HashMap<AXPropertyName, AttributeValueVariant, WTF::IntHash<AXPropertyName>, WTF::StrongEnumHashTraits<AXPropertyName>> m_attributeMap;

You can probably pack this better. Use dump-class-layout to optimize.

[Ryosuke Niwa]

Comment on attachment 360161 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=360161&action=review

>> Source/WebCore/accessibility/AXObjectCache.cpp:2919
>> +Ref<AXIsolatedTreeNode> AXObjectCache::createIsolatedAccessibilityTree(AccessibilityObject& object, AXID parentID, AXIsolatedTree& tree, Vector<RefPtr<AXIsolatedTreeNode>>& nodes)
> 
> Should that be Vector<RefPtr<AXIsolatedTreeNode>>&& if ownership is being transferred.
> 
> I'm confused about this function. It's called createIsolatedAccessibilityTree() but it takes a tree, rather than returning a tree. Is it really appending nodes to the tree? Maybe it should have "recursive" in the name too?

Oh, no, nodes is the out argument so & is right but we should use Vector<Ref<AXIsolatedTreeNode>> instead since we never insert a nullptr.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.h:73
> +    Vector<RefPtr<AXIsolatedTreeNode>> m_pendingAppends;

This should be Vector<Ref<AXIsolatedTreeNode>>

[chris fleizach]

Comment on attachment 360161 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=360161&action=review

>> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:63
>> +RefPtr<AXIsolatedTree> AXIsolatedTree::treeForPageID(uint64_t pageID, bool create)
> 
> Do you really want a tree per Page? Page outlives navigations, so do you swap out the tree on navigation? What's the lifetime of trees which aren't for the current document?

Yes I think so. That's the unit of interaction that accessibility deals with on incoming queries (the root object is based off of a WebPage thing)
when a page changes, the nodes are removed and recreated, the tree can hang around.

>> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:85
>> +    ASSERT(!isMainThread());
> 
> Can you assert that this is the reader thread?

I will need to add SPI to HIServices to verify which thread I'm on and whether it's the right one. I can work on that separately

>> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.h:63
>> +    bool isRootNode() const { return m_isRootNode; }
> 
> Can you tell that it's the root node because it has no parent?

It's possible that a node becomes orphaned but is in the cache for a short time (at least it's happened in the AccessibilityObject infrastructure). I wanted to be more explicit about which one is the root node to avoid something like that from happening

[chris fleizach]

Comment on attachment 360161 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=360161&action=review

>> Source/WebCore/accessibility/isolatedtree/AXIsolatedTreeNode.cpp:63
>> +    
> 
> Nit: whitespace.

there's an Xcode setting for this! wish I knew that before...

[chris fleizach]

Created attachment 360262 [details]
Landing patch

[EWS Watchlist]

Attachment 360262 [details] did not pass style-queue:


ERROR: Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:75:  More than one command on the same line  [whitespace/newline] [4]
ERROR: Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:93:  The parameter name "cache" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/WebKit/WebProcess/WebPage/mac/WKAccessibilityWebPageObjectBase.mm:100:  More than one command on the same line  [whitespace/newline] [4]
Total errors found: 3 in 32 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[chris fleizach]

Created attachment 360263 [details]
landing patch

[Ryosuke Niwa]

Comment on attachment 360263 [details]
landing patch

View in context: https://bugs.webkit.org/attachment.cgi?id=360263&action=review

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:128
> +    Vector<Ref<AXIsolatedTreeNode>> appendCopy = WTF::map(m_pendingAppends, [&] (const auto& node) {
> +        return node.copyRef();
> +    });

Why are we making a copy here?? We do need to clear m_pendingAppends at some point.

[chris fleizach]

(In reply to Ryosuke Niwa from comment #55)
> Comment on attachment 360263 [details]
> landing patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=360263&action=review
> 
> > Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:128
> > +    Vector<Ref<AXIsolatedTreeNode>> appendCopy = WTF::map(m_pendingAppends, [&] (const auto& node) {
> > +        return node.copyRef();
> > +    });
> 
> Why are we making a copy here?? We do need to clear m_pendingAppends at some
> point.

It is challenging to move something around with Ref instead of RefPtr

Ref override = to be delete, so Vector move and other operations don't compile

[Ryosuke Niwa]

(In reply to chris fleizach from comment #56)
> (In reply to Ryosuke Niwa from comment #55)
> > Comment on attachment 360263 [details]
> > landing patch
> > 
> > View in context:
> > https://bugs.webkit.org/attachment.cgi?id=360263&action=review
> > 
> > > Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:128
> > > +    Vector<Ref<AXIsolatedTreeNode>> appendCopy = WTF::map(m_pendingAppends, [&] (const auto& node) {
> > > +        return node.copyRef();
> > > +    });
> > 
> > Why are we making a copy here?? We do need to clear m_pendingAppends at some
> > point.
> 
> It is challenging to move something around with Ref instead of RefPtr
> 
> Ref override = to be delete, so Vector move and other operations don't
> compile

Surely std::swap or Vector::swap would work?

[chris fleizach]

Created attachment 360271 [details]
landing patch

[chris fleizach]

> 
> Surely std::swap or Vector::swap would work?

thanks. working

[WebKit Commit Bot]

Comment on attachment 360271 [details]
landing patch

Clearing flags on attachment: 360271

Committed r240552: <https://trac.webkit.org/changeset/240552>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.