705404 - build separate accessible tree on mac

Status: RESOLVED FIXED

(Core :: Disability Access APIs, defect)

Description

[alexander :surkov (:asurkov)]

Currently we create mac accessible objects for every internal (crossplatform) object and mark them as ignored or unignored. Mac parent is not cached what causes perf problems (bug 455443), mac children are cached and supposed to be invalidated when internal tree is changed. Children invalidation doesn't always work (see bug 689105).

We need a build complete accessible tree on mac, i.e. create mac accessible objects for unignored accessible and connect them by parent-child relation. When internal tree mutates then mac tree should be updated. That is correct fix for bug 455443 and bug 689105. Also this should improve much performance on mac a11y because VoiceOver seems doesn't have tree caching and navigates the tree over and over.

Comment 1

[James Teh [:Jamie]]

I know little of Mac accessibility, so this is way outside my territory and expertise. Nevertheless, I'm curious. :) Please correct me on any points below (or feel free to ignore this altogether).

I'd assume one performance hit is caused by VoiceOver having to crawl up the tree looking for unignored objects cross-process, hence the desire to build a separate tree. However, crawling up Gecko's own internal a11y tree is probably going to be much faster and more efficient. Why do the Mac proxy accessibles not just crawl the Gecko a11y tree and return only unignored parents/children? It's still not going to be 100% efficient, but surely it's much better than VoiceOver crawling all of the ignored objects cross-process.

I'm also curious as to what the Mac proxy accessibles really contain. Are they just weak proxies which pass all queries to Gecko a11y or do they maintain their own internal state? If the latter, why? I assume there are performance implications I'm missing. Is creating the proxies on-demand slow?

Comment 2

[alexander :surkov (:asurkov)]

(In reply to James Teh [:Jamie] from comment #1)
> I know little of Mac accessibility, so this is way outside my territory and
> expertise. Nevertheless, I'm curious. :) Please correct me on any points
> below (or feel free to ignore this altogether).
> 
> I'd assume one performance hit is caused by VoiceOver having to crawl up the
> tree looking for unignored objects cross-process, hence the desire to build
> a separate tree. However, crawling up Gecko's own internal a11y tree is
> probably going to be much faster and more efficient. Why do the Mac proxy
> accessibles not just crawl the Gecko a11y tree and return only unignored
> parents/children? It's still not going to be 100% efficient, but surely it's
> much better than VoiceOver crawling all of the ignored objects cross-process.

That's what we do currently. When VoiceOver asks us for a parent then we get native Gecko accessible object, get its parent, get parents mac accessible object, check if it's ignored and then continue the process until we find unignored parent.

Current implementation creates mac accessible object for every internal accessible object and that's why we get ignored/unignored accessible object concept. Therefore I suggested to build mac tree, i.e. create mac accessible objects for unignored internal objects only and connect mac objects by parent-child relations (do not crawl internal hierarchy to calculate it). This approach must consume less memory and be performant.

> I'm also curious as to what the Mac proxy accessibles really contain. Are
> they just weak proxies which pass all queries to Gecko a11y or do they
> maintain their own internal state? If the latter, why? I assume there are
> performance implications I'm missing.

All they do is nsAccessibility protocol implementation and that's similar to what we have for ATK and MSAA. So yes, basically they are just weak proxies. However you can say they maintain own properties like mac accessible object keeps an array of children (unignored direct and not direct children in subtree).

> Is creating the proxies on-demand slow?

I think we could build mac accessible tree on demand. That's a nice feature for accessibility that doesn't use OS X accessibility interfaces (like DOM Inspector).

Comment 3

[Hubert Figuiere [:hub]]

Does that mean I should just fix this and bug 689105 and bug 455443 should just go away?

Comment 4

[alexander :surkov (:asurkov)]

(In reply to Hub Figuiere [:hub] from comment #3)
> Does that mean I should just fix this and bug 689105 and bug 455443 should
> just go away?

correct

Comment 5

[Hubert Figuiere [:hub]]

Regression.

It is cause by the patch for bug 646368

Essentially removing EnsureChildren() from a lot of places.

Comment 6

[alexander :surkov (:asurkov)]

(In reply to Hub Figuiere [:hub] from comment #5)
> Regression.
> 
> It is cause by the patch for bug 646368
> 
> Essentially removing EnsureChildren() from a lot of places.

for the record: the regression of bug 689105.

Comment 7

[Hubert Figuiere [:hub]]

oops. I mixed up bug numbers. once again. I meant to comment bug 689105.

Comment 8

[David Bolter [:davidb] (NeedInfo me for attention)]

(In reply to alexander :surkov from comment #2)
> (In reply to James Teh [:Jamie] from comment #1)
> > Is creating the proxies on-demand slow?
> 
> I think we could build mac accessible tree on demand. That's a nice feature
> for accessibility that doesn't use OS X accessibility interfaces (like DOM
> Inspector).

I think on-demand usually means "when someone asks for it", is that the intended meaning here?

I'm also curious if we know data like what percentage of our tree would typically contain objects with the ignored property on OSX?

Comment 9

[alexander :surkov (:asurkov)]

(In reply to David Bolter [:davidb] from comment #8)
> (In reply to alexander :surkov from comment #2)
> > (In reply to James Teh [:Jamie] from comment #1)
> > > Is creating the proxies on-demand slow?
> > 
> > I think we could build mac accessible tree on demand. That's a nice feature
> > for accessibility that doesn't use OS X accessibility interfaces (like DOM
> > Inspector).
> 
> I think on-demand usually means "when someone asks for it", is that the
> intended meaning here?

correct

> I'm also curious if we know data like what percentage of our tree would
> typically contain objects with the ignored property on OSX?

Is it sort of vacuous question or does it have practice background? Why do you care?

Comment 10

[David Bolter [:davidb] (NeedInfo me for attention)]

I care too much :)

My question came out of couple of things:
1. probably not fully understanding the bug.
2. having a different tree feels like it would have long lasting engineering cost.
3. wondering if we know there are lots of ignored objects (perf impact).

If we could reduce the tree for all platforms that would be nice - is that the idea?

Otherwise maybe we could just keep the full tree and the shortcuts (cached parent/children pointers essentially), essentially a tree within a tree.

Comment 11

[alexander :surkov (:asurkov)]

(In reply to David Bolter [:davidb] from comment #10)
> I care too much :)
> 
> My question came out of couple of things:
> 1. probably not fully understanding the bug.
> 2. having a different tree feels like it would have long lasting engineering
> cost.
> 3. wondering if we know there are lots of ignored objects (perf impact).

Technically we have a own tree on mac (at least when bug 455443 is fixed and hub is active on it). So then we should address here two problems:

1) make sure the mac tree is updated correctly (that doesnt' happen now)
2) don't create mac accessible for ignored children because it's memory wasting

I don't think there's big number of ignored object that'll be just a move clever design.

> If we could reduce the tree for all platforms that would be nice - is that
> the idea?

no, that's different. Some roles are ignored on mac because of unfinished os x support and difference between APIs. 

> Otherwise maybe we could just keep the full tree and the shortcuts (cached
> parent/children pointers essentially), essentially a tree within a tree.

I'm not sure I follow you here but that should be addressed by answers above I think :)

Comment 12

[Hubert Figuiere [:hub]]

(In reply to David Bolter [:davidb] from comment #10)

> 2. having a different tree feels like it would have long lasting engineering
> cost.

There is this comment in the nsAccessibleWrap.mm about the tree:

bool
nsAccessibleWrap::AncestorIsFlat()
{
  // We don't create a native object if we're child of a "flat" accessible;
  // for example, on OS X buttons shouldn't have any children, because that
  // makes the OS confused. 
  //
  // To maintain a scripting environment where the XPCOM accessible hierarchy
  // look the same on all platforms, we still let the C++ objects be created
  // though.

The rationale is that we want to keep the same accessibility tree in Gecko because it can be used for other things like scripting.

[...]

> Otherwise maybe we could just keep the full tree and the shortcuts (cached
> parent/children pointers essentially), essentially a tree within a tree.

That's what I think too.

Note: I have a patch that lazily create the mozAccessible objects on demand instead of upfront.

Comment 13

[Hubert Figuiere [:hub]]

Attachment: proposed patch

This patch creates the native objects on demand.

Comment 14

[Hubert Figuiere [:hub]]

Comment on attachment 580268 [details] [diff] [review]
proposed patch

Review of attachment 580268 [details] [diff] [review]:
-----------------------------------------------------------------

::: accessible/src/mac/nsAccessibleWrap.h
@@ +94,2 @@
>  
> +    

this empty should have been skipped already. I removed it here.

Comment 15

[Trevor Saunders (:tbsaunde)]

Comment on attachment 580268 [details] [diff] [review]
proposed patch


> #if defined(__OBJC__)
>-    mozAccessible* mNativeObject;
>+  mozAccessible* GetNativeObject();
> #else
>-    id mNativeObject;  
>+  id GetNativeObject();
> #endif

We've started using Foo() instead of GetFoo() for this sort of method.  I guess davidb has questions about that, but I don't understand what they are so I still tend to think its a good pattern.

>+  bool mNativeShutdown;

why not just use IsDefunct() here? its a little slower, but I think having two different ways to do this is bad, and making IsDefunct()  as fast shouldn't be very hard.

>+  /**
>+   * We have created our native. This does not mean there is one.
>+   * This can never go back to false.
>+   */
>+  bool mNativeInited;

This seems kind of pointless, if your not defunct and you don't have a native then you should create one otherwise not.

>+  mozAccessible* nativeObject = GetNativeObject();
>+  if (nativeObject) {
>+    *aOutInterface = static_cast<void*>(nativeObject);
>     return NS_OK;
>-  }
>+  }  
>   *aOutInterface = nsnull;
>   return NS_ERROR_FAILURE;
> }

*aOutInterface = static_cast<void*>(NativeObject());
return mNativeObject ? NS_OK : NS_ERROR_FAILURE;

>+  mozAccessible* nativeObject = GetNativeObject();
>+  return (nativeObject == nil) || [nativeObject accessibilityIsIgnored];

return NativeObject() || [mNativeObject IsIgnored()];

Comment 16

[Hubert Figuiere [:hub]]

(In reply to Trevor Saunders (:tbsaunde) from comment #15)
> >+  bool mNativeShutdown;
> 
> why not just use IsDefunct() here? its a little slower, but I think having
> two different ways to do this is bad, and making IsDefunct()  as fast
> shouldn't be very hard.

Because it does not work. Tried it at first and the object got reinitialized before IsDefunct() was returning true.

> >+  /**
> >+   * We have created our native. This does not mean there is one.
> >+   * This can never go back to false.
> >+   */
> >+  bool mNativeInited;
> 
> This seems kind of pointless, if your not defunct and you don't have a
> native then you should create one otherwise not.

This is actually to speed up. Otherwise I have to call AncestorIsFlat() every time as there is no native object. mNativeInited mean that we know whether we have a native or not.

> 
> >+  mozAccessible* nativeObject = GetNativeObject();
> >+  if (nativeObject) {
> >+    *aOutInterface = static_cast<void*>(nativeObject);
> >     return NS_OK;
> >-  }
> >+  }  
> >   *aOutInterface = nsnull;
> >   return NS_ERROR_FAILURE;
> > }
> 
> *aOutInterface = static_cast<void*>(NativeObject());
> return mNativeObject ? NS_OK : NS_ERROR_FAILURE;
>
> >+  mozAccessible* nativeObject = GetNativeObject();
> >+  return (nativeObject == nil) || [nativeObject accessibilityIsIgnored];
> 
> return NativeObject() || [mNativeObject IsIgnored()];

These two break the encapsulation I explicitely put. That's why I wrote it the way I did.
mNativeObject is no longer meant to be accessed directly.

Comment 17

[Trevor Saunders (:tbsaunde)]

(In reply to Hub Figuiere [:hub] from comment #16)
> (In reply to Trevor Saunders (:tbsaunde) from comment #15)
> > >+  bool mNativeShutdown;
> > 
> > why not just use IsDefunct() here? its a little slower, but I think having
> > two different ways to do this is bad, and making IsDefunct()  as fast
> > shouldn't be very hard.
> 
> Because it does not work. Tried it at first and the object got reinitialized
> before IsDefunct() was returning true.

that's concerning, do you understand what's going on in more dtail?

> > >+  /**
> > >+   * We have created our native. This does not mean there is one.
> > >+   * This can never go back to false.
> > >+   */
> > >+  bool mNativeInited;
> > 
> > This seems kind of pointless, if your not defunct and you don't have a
> > native then you should create one otherwise not.
> 
> This is actually to speed up. Otherwise I have to call AncestorIsFlat()
> every time as there is no native object. mNativeInited mean that we know
> whether we have a native or not.

I guess that's fair, but please comment why.

> > *aOutInterface = static_cast<void*>(NativeObject());
> > return mNativeObject ? NS_OK : NS_ERROR_FAILURE;

ok, change mNativeObject to *aOutInterface and the same thing works.

> > >+  mozAccessible* nativeObject = GetNativeObject();
> > >+  return (nativeObject == nil) || [nativeObject accessibilityIsIgnored];
> > 
> > return NativeObject() || [mNativeObject IsIgnored()];

gecko style is to not compare against null or 0, so you should atleast get rid of the == nil.

> These two break the encapsulation I explicitely put. That's why I wrote it
> the way I did.
> mNativeObject is no longer meant to be accessed directly.

I'm not a huge fan though I can live with it, but that really needs to be commented more.

Comment 18

[Hubert Figuiere [:hub]]

Attachment: proposed patch v2

with all the feedback integrated.

Comment 19

[Hubert Figuiere [:hub]]

Note: this is does not solve all the problems.

Comment 20

[Trevor Saunders (:tbsaunde)]

(In reply to Trevor Saunders (:tbsaunde) from comment #17)
> (In reply to Hub Figuiere [:hub] from comment #16)
> > (In reply to Trevor Saunders (:tbsaunde) from comment #15)
> > > >+  bool mNativeShutdown;
> > > 
> > > why not just use IsDefunct() here? its a little slower, but I think having
> > > two different ways to do this is bad, and making IsDefunct()  as fast
> > > shouldn't be very hard.
> > 
> > Because it does not work. Tried it at first and the object got reinitialized
> > before IsDefunct() was returning true.
> 
> that's concerning, do you understand what's going on in more dtail?

I'd really like to understand why IsDefunct() isn't returning true when called on a shutdown accessible,  because that seems like a bug that your just working around here.

> 
> > > *aOutInterface = static_cast<void*>(NativeObject());
> > > return mNativeObject ? NS_OK : NS_ERROR_FAILURE;
> 
> ok, change mNativeObject to *aOutInterface and the same thing works.

not really addressed in the new patch

Comment 21

[Trevor Saunders (:tbsaunde)]

Comment on attachment 580535 [details] [diff] [review]
proposed patch v2

(Alex asked me to take his reviews since he's out for a couple days)

>+  id mNativeObject;
> #endif
>+  /**

blank line before comment.

>+  bool mNativeShutdown;
>+  /**

same

>+  if (!mNativeInited && !mNativeObject && !mNativeShutdown && !IsDefunct() && !AncestorIsFlat())
>     mNativeObject = [[GetNativeType() alloc] initWithAccessible:this];

break at 80 chars.

>+  mozAccessible* nativeObject = GetNativeObject();
>+  if (nativeObject)
>+    *aOutInterface = static_cast<void*>(nativeObject);
>+    
>   return NS_ERROR_FAILURE;

this method now always returns failure.

I'd suggest

writing it as
{
  NS_ENSURE_ARG_POINTER(aOutInterface);
  *aOutInterface = static_cast<void*>(GetNativeObject());
  return *aOutInterface ? NS_OK : NS_ERROR_FAILURE;
}

Comment 22

[Hubert Figuiere [:hub]]

(In reply to Trevor Saunders (:tbsaunde) from comment #21)

> this method now always returns failure.

gahh. how did I even let that one slide? It wouldn't have passed the test.

Comment 23

[Hubert Figuiere [:hub]]

> I'd really like to understand why IsDefunct() isn't returning true when
> called on a shutdown accessible,  because that seems like a bug that your
> just working around here.

IsDefunct() is a check whether mContent is NULL or not. This is in nsAccessNode.
mContent is set to NULL on nsAccessNode::Shutdown()

Now, when calling nsAccessible::Shutdown() it calls InvalidateChildren(), which in nsAccessibleWrap::InvalidateChildren() override (Mac) call the following:
  [GetNativeObject() invalidateChildren];
If I don't check that we are defunct, then it will recreate a native object for a defunct object (and crash try to dereference a null pointer).

Not a bug. A perfectly normal flow.

Now, as I think of it, I should just need mNativeInited.

Comment 24

[Hubert Figuiere [:hub]]

Attachment: proposed patch v2.1

Comment 25

[Trevor Saunders (:tbsaunde)]

(In reply to Hub Figuiere [:hub] from comment #23)
> > I'd really like to understand why IsDefunct() isn't returning true when
> > called on a shutdown accessible,  because that seems like a bug that your
> > just working around here.
> 
> IsDefunct() is a check whether mContent is NULL or not. This is in
> nsAccessNode.
> mContent is set to NULL on nsAccessNode::Shutdown()
> 
> Now, when calling nsAccessible::Shutdown() it calls InvalidateChildren(),
> which in nsAccessibleWrap::InvalidateChildren() override (Mac) call the
> following:
>   [GetNativeObject() invalidateChildren];
> If I don't check that we are defunct, then it will recreate a native object
> for a defunct object (and crash try to dereference a null pointer).

yeah, ok, thanks for explaining.

> Now, as I think of it, I should just need mNativeInited.

what about the case that we  shutdown an accessible who never had a native created (I don't think this can happen now, but worth considering for the future).  I think the answer right now is that you create a native object and basically immediately destroy it.

calling GetNative() in InvalidateChildren() should work, but I wonder if we need to eagerly create the natives.

Comment 26

[Hubert Figuiere [:hub]]

> > Now, as I think of it, I should just need mNativeInited.
> 
> what about the case that we  shutdown an accessible who never had a native
> created (I don't think this can happen now, but worth considering for the
> future).  I think the answer right now is that you create a native object
> and basically immediately destroy it.
> 
> calling GetNative() in InvalidateChildren() should work, but I wonder if we
> need to eagerly create the natives.

Good point. Setting mNativeInited to true in Shutdown() should be enough. Simple enough to get it covered.

Comment 27

[Hubert Figuiere [:hub]]

Attachment: proposed patch v2.2

Make sure we don't try to create the native in shutdown if it has ever been.

Comment 28

[Trevor Saunders (:tbsaunde)]

Comment on attachment 581342 [details] [diff] [review]
proposed patch v2.2


>+  if (!mNativeInited && !mNativeObject && !IsDefunct() && !AncestorIsFlat())

I'm pretty sure you don't need the IsDefunct() check now right?  If you agree I'm fine with changing that when I push.

Comment 29

[Hubert Figuiere [:hub]]

Here is the try build.

https://tbpl.mozilla.org/?tree=Try&rev=9831dfe58756


(In reply to Trevor Saunders (:tbsaunde) from comment #28)
> Comment on attachment 581342 [details] [diff] [review]
> proposed patch v2.2
> 
> 
> >+  if (!mNativeInited && !mNativeObject && !IsDefunct() && !AncestorIsFlat())
> 
> I'm pretty sure you don't need the IsDefunct() check now right?  If you
> agree I'm fine with changing that when I push.

I'd rather keep it around. Better be safe than sorry.

Comment 30

[Trevor Saunders (:tbsaunde)]

> > I'm pretty sure you don't need the IsDefunct() check now right?  If you
> > agree I'm fine with changing that when I push.
> 
> I'd rather keep it around. Better be safe than sorry.

I tend to not really like the it shouldn't be needed because other invariants should make it meaningless, but lets check it anyway approach.  Mostly on the  grounds it can hide a bug where the other things we believe to be true aren't actually, but the other check catches it for some reason.

Comment 31

[Ed Morley [:emorley]]

Comment on attachment 581342 [details] [diff] [review]
proposed patch v2.2

In my queue with a few other checkin-neededs that are being sent to try first and then onto inbound :-)
https://tbpl.mozilla.org/?tree=Try&rev=fd440327d5e4

Comment 32

[Ed Morley [:emorley]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/a2b2e75ab77b

Comment 33

[Ed Morley [:emorley]]

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