606080 - (64bit) fix unique id casting to NS_PTR_TO_INT32 issue

Status: RESOLVED FIXED

(Core :: Disability Access APIs, defect)

Description

[alexander :surkov (:asurkov)]

The follow up from bug 570275:

   // Yes, this means we're only compatibible with 32 bit
   // MSAA is only available for 32 bit windows, so it's okay
-  return - NS_PTR_TO_INT32(uniqueID);
+  return aAccessible ? - NS_PTR_TO_INT32(aAccessible->UniqueID()) : 0;

Was this comment meant to be Firefox specific (i.e. MSAA Is only available for
32 bit Windows in Firefox)? MSAA is most certainly available for 64 bit Windows
applications, but the IDs must be 32 bit, so a bug needs to be filed to follow
this up if one hasn't been already. I assume this is what was meant by:
> (Do we have a bug filed for this?)

In a 64 bit environment, I assume you *could* have 64 bit
pointers which don't fit into 32 bits. Does NS_PTR_TO_INT32 simply cast the
value or does it create a map somewhere? If it just casts, this will
potentially break in 64 bit environments, as you could conceivably have two
memory addresses with the same 32 bit ID.

Comment 1

[alexander :surkov (:asurkov)]

we need to get it fixed in Firefox 4. It's might be serious issue.

Comment 2

[James Teh [:Jamie]]

Just to clarify, this is only an issue for 64 bit builds of Firefox. As I understand it, Firefox is only officially built as a 32 bit application on Windows, even though there are unofficial builds.

There are two solutions to this problem:
1. Don't use pointers as unique IDs. Instead, generate unique IDs using a cycling counter and perhaps a reuse pool.
2. Continue to use pointers, but when an ID conflicts with another ID (due to overflowing 32 bits), use some algorithm to resolve this. I think this solution is actually more complicated, though.

Comment 3

[alexander :surkov (:asurkov)]

(In reply to comment #2)
> Just to clarify, this is only an issue for 64 bit builds of Firefox. As I
> understand it, Firefox is only officially built as a 32 bit application on
> Windows, even though there are unofficial builds.

I missed this point. Perhaps it shouldn't be blocking then. David, is 64bit Firefox 4 expected?

Comment 4

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

Jim Mathies tells me not officially. I think we'd approve a safe patch for sure.

We can't capture a 64 bit pointer in 32 bits obviously. I'm not sure we want to keep a counter as reclaiming is tricky. I think we should ping Pete on this.

Comment 5

[James Teh [:Jamie]]

(In reply to comment #4)
> We can't capture a 64 bit pointer in 32 bits obviously. I'm not sure we want to
> keep a counter as reclaiming is tricky. I think we should ping Pete on this.
I don't think there is any other choice.

Here's a snippet from the IA2 spec:
> One means of implementing this would be to create a factory with a 32 bit number generator and a reuse pool.  The number generator would emit numbers starting at 1.  Each time an object's life cycle ended, its number would be saved into a reuse pool.  The number generator would be used whenever the reuse pool was empty.

Comment 6

[Trevor Saunders (:tbsaunde)]

approach using a free list

struct range {
uint32 min;
uint32 max;
};
list<range> freeIDs = { { 0, 0xffffffff } };
uint32 GetID()
{
if (list[0].in == list[0].max){
id = list[0].min;
freeIDs.Remove(0);
return id;
}

id = list[0].min;
list[0].min++;
return id;
}

 freeID(id)
{
i = 0;
while(list[i].min > id)
i++;

if(id + 1 == list[i].min){
list[i].min = id;
}else{
list.InsertBefore(i, {id, id});
}
}

the idea here is that the accessible will call GetID() at creation and freeID() on destruction and hold the id in its object inbetween.

there are a bunch of little things here that can be fiddled with to try and make this as performant as possible.

note that creating an accessilbe and getting its id will always be fast, but destruction might be slow (O(n)) in the number of chunks).
list<range> freeIDs;

Comment 7

[alexander :surkov (:asurkov)]

soon or less we end up with o(n) where n is amount of accessible objects, if we are not running in background the code that combines ranges then it's likely not working.

I wonder if there's another way like a bijection finding, i.e. one-to-one mapping PRUint64 <-> PRUint32. Can Knuth's multiplicative method or similar algorithms be used here? Do we have any reasonable assumptions about address space available for us?

Comment 8

[Andrzej Skalski]

Ok, I dig for a while, and here are my thoughts:

Worst case scenario (to all solutions I think of) is allocating a lot of objects (say 2^30) and freeing every with odd number. We end up with 2^29 single-objects that cannot be stored in any kind of ranges without some serious AI. This worst case scenario kills all optimizations I can think of, and if it would be the only one considered, Trevor's solution would be optimal.

If we don't need the re-used IDs to be feed in any particular order (and I can't think of the reason why they should be), I can propose a following solution:

A counter + modified Interval Tree (see wikipedia) for reuse-pool. All you need to know is expected performance (all worst cases):

d - number of IDs in reuse pool.
computation:
Taking a fresh_id: O(1)
Taking a ID from reuse-pool: O(log(d))
Freeing an ID: O(log(d))
memory consumption: O(log(d))
constants will not be very high. I can also apply some heuristics to cut the tree in a intelligent manner, to make it smaller and shorter (at least I think so right now).

I can also write this option and run some performance tests on randomized data, or data that mimic the typical execution (if someone tells me how do they look like).

Comment 9

[Trevor Saunders (:tbsaunde)]

(In reply to Andrzej Skalski from comment #8)
> Ok, I dig for a while, and here are my thoughts:
> 
> Worst case scenario (to all solutions I think of) is allocating a lot of
> objects (say 2^30) and freeing every with odd number. We end up with 2^29
> single-objects that cannot be stored in any kind of ranges without some
> serious AI. This worst case scenario kills all optimizations I can think of,
> and if it would be the only one considered, Trevor's solution would be
> optimal.

yeah, fortunately that case  *really* shouldn't happen.

> If we don't need the re-used IDs to be feed in any particular order (and I
> can't think of the reason why they should be), I can propose a following
> solution:

I'd agree

> A counter + modified Interval Tree (see wikipedia) for reuse-pool. All you
> need to know is expected performance (all worst cases):

we know that ranges don't overlap, so the naive  approach works here right? which means basically we are using $tree

> d - number of IDs in reuse pool.
> computation:
> Taking a fresh_id: O(1)
> Taking a ID from reuse-pool: O(log(d))
> Freeing an ID: O(log(d))
> memory consumption: O(log(d))

that can't be a worst case.  since  in the worst case you mention you now have d intervals non of which overlap meaning your tree is size d.

> constants will not be very high. I can also apply some heuristics to cut the
> tree in a intelligent manner, to make it smaller and shorter (at least I
> think so right now).
> 
> I can also write this option and run some performance tests on randomized
> data, or data that mimic the typical execution (if someone tells me how do
> they look like).

I dn't think we have sample data here, but its probably not that hard to get some if we need it.

another interesting idea that I don't really want to consider until we know we need it is freeing ids off the main thread.

Comment 10

[Andrzej Skalski]

> 
> > A counter + modified Interval Tree (see wikipedia) for reuse-pool. All you
> > need to know is expected performance (all worst cases):
> 
> we know that ranges don't overlap, so the naive  approach works here right?
> which means basically we are using $tree

What is $tree? It's a bit more less memory consuming than naive, since we aggregate siblings into higher-order nodes, eliminating child nodes. So memory is pretty much only gain.
 
> > d - number of IDs in reuse pool.

> > memory consumption: O(log(d))
> 
> that can't be a worst case.  since  in the worst case you mention you now
> have d intervals non of which overlap meaning your tree is size d.
> 

You're absolutely right Trevor, for some reason I thought only about it's height, not summarized size.
 
> I dn't think we have sample data here, but its probably not that hard to get
> some if we need it.
> 
> another interesting idea that I don't really want to consider until we know
> we need it is freeing ids off the main thread.

Another key-optimisation that we could consider is group-freeing (doing structure update lazily after 100 free's or once it really necessary), here the telemetry might be useful as well.

Comment 11

[Trevor Saunders (:tbsaunde)]

(In reply to Andrzej Skalski from comment #10)
> > 
> > > A counter + modified Interval Tree (see wikipedia) for reuse-pool. All you
> > > need to know is expected performance (all worst cases):
> > 
> > we know that ranges don't overlap, so the naive  approach works here right?
> > which means basically we are using $tree
> 
> What is $tree? It's a bit more less memory consuming than naive, since we
> aggregate siblings into higher-order nodes, eliminating child nodes. So
> memory is pretty much only gain.

yeah, by $tree I meant substitute here the tree of your choice, using $foo to    like a variable.

> > > d - number of IDs in reuse pool.
> 
> > > memory consumption: O(log(d))
> > 
> > that can't be a worst case.  since  in the worst case you mention you now
> > have d intervals non of which overlap meaning your tree is size d.
> > 
> 
> You're absolutely right Trevor, for some reason I thought only about it's
> height, not summarized size.

ok, that makes sense

> > I dn't think we have sample data here, but its probably not that hard to get
> > some if we need it.
> > 
> > another interesting idea that I don't really want to consider until we know
> > we need it is freeing ids off the main thread.
> 
> Another key-optimisation that we could consider is group-freeing (doing
> structure update lazily after 100 free's or once it really necessary), here
> the telemetry might be useful as well.

ok

Comment 12

[Andrzej Skalski]

Yeah, I just got group-freeing figured out. We just aggregate freed ID's in a fixed-sized array (say of 128), once it fill's up, we do qsort(), then from sorted data we extract ranges (linear time) and we insert entire ranges into the tree instead of single nodes. This minimizes number of operations on tree, making constant lower. It would have a lot of sense, if my presumption that IDs will be freed in groups is right. It does not change O() notation, just constant.

Comment 13

[alexander :surkov (:asurkov)]

tree usage to keep IDs intervals is a good idea since operations are fast. I'm not clear about group-freeing because when tree is small then it's rather harmful than good but the same time I doesn't look like panacea of tree bloating. It might be good idea to keep running interruptable tree collapser what supposed to combine ranges.

Comment 14

[alexander :surkov (:asurkov)]

(In reply to alexander :surkov from comment #13)
> It might be good idea to keep running interruptable tree
> collapser what supposed to combine ranges.

alternatively you can combine sibling ranges as you free ID

btw, could you put code illustration to see how your approach works?

Comment 15

[Andrzej Skalski]

yes, I'll write proof-of-concept in C++ and post it here to discuss. Combining siblings is usually done immediately after modifying tree (not lazily) to keep O(log(n)) true. My suggestion to aggregate frees() will be tested for performance as well.

Meanwhile, can someone think of "where to get example data from"? I mean a simulation of actual usage.

Comment 16

[alexander :surkov (:asurkov)]

(In reply to Andrzej Skalski from comment #15)

> Meanwhile, can someone think of "where to get example data from"? I mean a
> simulation of actual usage.

the best simulation is a real life. maybe we could expose XPCOM interface for debugging proposes or reuse telemetry and then we can compare two builds? Trevor?

Comment 17

[Lawrence Mandel [:lmandel] (use needinfo)]

Tracking as I understand that this bug needs to be fixed to support a11y in Win64 builds.

Comment 18

[Sylvestre Ledru [:Sylvestre]]

Andrew, any idea who could work on this bug? Thanks

Comment 19

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

Trevor is looking at it.

Comment 20

[Sylvestre Ledru [:Sylvestre]]

Trevor, any news? We are past the middle of the beta cycle.

Comment 21

[Trevor Saunders (:tbsaunde)]

Ok, I think I have something working in https://treeherder.mozilla.org/#/jobs?repo=try&revision=a22e9405e228 Marco and Jamie can you test that?

Comment 22

[James Teh [:Jamie]]

Is there a try build? I've never been clear on how to get build URLs from that interface...

Comment 23

[Trevor Saunders (:tbsaunde)]

(In reply to James Teh [:Jamie] from comment #22)
> Is there a try build? I've never been clear on how to get build URLs from
> that interface...

yeah, I think its here http://ftp.mozilla.org/pub/mozilla.org/firefox/try-builds/[e-mail]-a22e9405e228/try-win64/

Comment 24

[James Teh [:Jamie]]

This is better. IAccessible::accChild now fetches the correct objects. However:
1. Ids are now positive instead of negative, which is different to how things are with 32 bit (thus probably breaking some xpectations) and also conflicts with positive child ids meaning to fetch the nth child.
2. accChild on the document can no longer be used to test whether a given child is a descendant of that document, which is behaviour that NVDA relies upon. We always get E_INVALIDARG. Possibly due to (1).
3. We get blank browse mode documents (buffers) in NVDA. I'm not entirely sure why this is, but it sounds a lot like bug 649236 (previously fixed). It could also be another side effect of (1).

Comment 25

[Trevor Saunders (:tbsaunde)]

(In reply to James Teh [:Jamie] from comment #24)
> This is better. IAccessible::accChild now fetches the correct objects.

based on the below I guess you mean IAccessible::accChild works if you call it on something other than a document? or are you manually flipping the sign?

> However:
> 1. Ids are now positive instead of negative, which is different to how
> things are with 32 bit (thus probably breaking some xpectations) and also
> conflicts with positive child ids meaning to fetch the nth child.

that's a bug somewhere in AccessibleWrap::GetChildIDFor() but I'm completely at a loss for where without debugging somehow.

> 2. accChild on the document can no longer be used to test whether a given
> child is a descendant of that document, which is behaviour that NVDA relies
> upon. We always get E_INVALIDARG. Possibly due to (1).

hrm, but you can do lookup of ids on non document accessibles?

> 3. We get blank browse mode documents (buffers) in NVDA. I'm not entirely
> sure why this is, but it sounds a lot like bug 649236 (previously fixed). It
> could also be another side effect of (1).

lets see about 1 and 2 first and see where we get.

Comment 26

[Marco Zehe (:MarcoZ)]

(In reply to Trevor Saunders (:tbsaunde) from comment #25)
> (In reply to James Teh [:Jamie] from comment #24)
> > This is better. IAccessible::accChild now fetches the correct objects.
> 
> based on the below I guess you mean IAccessible::accChild works if you call
> it on something other than a document? or are you manually flipping the sign?

No, we are flipping the sign on any child ID to a negative in the original return line:

>@@ -1259,17 +1280,29 @@ AccessibleWrap::GetChildIDFor(Accessible
> {
>   // A child ID of the window is required, when we use NotifyWinEvent,
>   // so that the 3rd party application can call back and get the IAccessible
>   // the event occurred on.
> 
>   // Yes, this means we're only compatibible with 32 bit
>   // MSAA is only available for 32 bit windows, so it's okay
>   // XXX: bug 606080
>-  return aAccessible ? - NS_PTR_TO_INT32(aAccessible->UniqueID()) : 0;

In the replaced line above, after the question mark, there is a minus sign before the call to NS_PTR_TO_INT32. In other words, we are grabbing our internal child IDs and just unconditionally negate them to a negative value to satisfy the IAccessible2 requirement for negative child IDs.

In the code you wrote, you are using unsigned integers and not doing the flipping of signs any more, resulting in the problem that all child IDs are now positive.

> > 1. Ids are now positive instead of negative, which is different to how
> > things are with 32 bit (thus probably breaking some xpectations) and also
> > conflicts with positive child ids meaning to fetch the nth child.
> that's a bug somewhere in AccessibleWrap::GetChildIDFor() but I'm completely
> at a loss for where without debugging somehow.

Hope the above explanation helps.

I suggest fixing this and then looking at any remaining problems that might still be around.

Comment 27

[Trevor Saunders (:tbsaunde)]

(In reply to Marco Zehe (:MarcoZ) from comment #26)
> (In reply to Trevor Saunders (:tbsaunde) from comment #25)
> > (In reply to James Teh [:Jamie] from comment #24)
> > > This is better. IAccessible::accChild now fetches the correct objects.
> > 
> > based on the below I guess you mean IAccessible::accChild works if you call
> > it on something other than a document? or are you manually flipping the sign?
> 
> No, we are flipping the sign on any child ID to a negative in the original
> return line:

my question was trying to understand what exactly he's seeing.

> >@@ -1259,17 +1280,29 @@ AccessibleWrap::GetChildIDFor(Accessible
> > {
> >   // A child ID of the window is required, when we use NotifyWinEvent,
> >   // so that the 3rd party application can call back and get the IAccessible
> >   // the event occurred on.
> > 
> >   // Yes, this means we're only compatibible with 32 bit
> >   // MSAA is only available for 32 bit windows, so it's okay
> >   // XXX: bug 606080
> >-  return aAccessible ? - NS_PTR_TO_INT32(aAccessible->UniqueID()) : 0;
> 
> In the replaced line above, after the question mark, there is a minus sign
> before the call to NS_PTR_TO_INT32. In other words, we are grabbing our
> internal child IDs and just unconditionally negate them to a negative value
> to satisfy the IAccessible2 requirement for negative child IDs.

Well, that only actually works out if you only have pointers values in the range [0, 2^31 - 1] though I think you may have to work to get other address in win32.

> In the code you wrote, you are using unsigned integers and not doing the
> flipping of signs any more, resulting in the problem that all child IDs are
> now positive.

no, that's not the cause (at least its not that simple).  sIDGen should be returning uint32_ts in the range [0, 2^31 - 1] then we take the complement of that value, and return it as an int32_t which should mean its negative (I'm not totally sure that's defined behavior to convert unsigned to signed but I think it is).

Comment 28

[James Teh [:Jamie]]

(In reply to Trevor Saunders (:tbsaunde) from comment #25)
> based on the below I guess you mean IAccessible::accChild works if you call
> it on something other than a document?
Correct. If you call it on the root accessible for the HWND (the top level frame), it works. However, IAccessible2::uniqueID and win event child ids are all positive.

Comment 29

[alexander :surkov (:asurkov)]

as Jamie pointed out the problem cause is IAccessible::accChild treats positive value as child indexes, negative values as unique IDs.

Comment 30

[Trevor Saunders (:tbsaunde)]

(In reply to alexander :surkov from comment #29)
> as Jamie pointed out the problem cause is IAccessible::accChild treats
> positive value as child indexes, negative values as unique IDs.

yes, but do you have any idea why they are positive, or can you debug it?  debugging on try is not exactly efficient.

Comment 31

[alexander :surkov (:asurkov)]

(In reply to Trevor Saunders (:tbsaunde) from comment #30)
> (In reply to alexander :surkov from comment #29)
> > as Jamie pointed out the problem cause is IAccessible::accChild treats
> > positive value as child indexes, negative values as unique IDs.
> 
> yes, but do you have any idea why they are positive, or can you debug it? 
> debugging on try is not exactly efficient.

I'm not sure whether flip bits operator is reliable way to convert from positive to negative numbers and vise versa. Why don't you make sure instead that generated ID is in proper range to use -operator?

Comment 32

[Trevor Saunders (:tbsaunde)]

(In reply to alexander :surkov from comment #31)
> (In reply to Trevor Saunders (:tbsaunde) from comment #30)
> > (In reply to alexander :surkov from comment #29)
> > > as Jamie pointed out the problem cause is IAccessible::accChild treats
> > > positive value as child indexes, negative values as unique IDs.
> > 
> > yes, but do you have any idea why they are positive, or can you debug it? 
> > debugging on try is not exactly efficient.
> 
> I'm not sure whether flip bits operator is reliable way to convert from
> positive to negative numbers and vise versa. Why don't you make sure instead
> that generated ID is in proper range to use -operator?

it is as I said in comment 27, or you could go read http://en.wikipedia.org/wiki/Two%27s_complement the ranges are basically identical which ever operator you use, but msvc doesn't like it when you use - on a unsigned type.



(In reply to Trevor Saunders (:tbsaunde) from comment #30)
> (In reply to alexander :surkov from comment #29)
> > as Jamie pointed out the problem cause is IAccessible::accChild treats
> > positive value as child indexes, negative values as unique IDs.
> 
> yes, but do you have any idea why they are positive, or can you debug it? 
> debugging on try is not exactly efficient.

interestingly the log at http://mozilla-releng-blobs.s3.amazonaws.com/blobs/try/sha512/e710c7973cde2c25bcaacc37f77678375e75022d1cd7ebdb0d99343228c7a50c108ce4533ee33a53397d47134de47b2598ab998b25f66faa1828d037e4f540f7 really suggests the returned ids are negative and there's no bug???

Comment 33

[alexander :surkov (:asurkov)]

(In reply to Trevor Saunders (:tbsaunde) from comment #32)
> (In reply to alexander :surkov from comment #31)
> > (In reply to Trevor Saunders (:tbsaunde) from comment #30)
> > > (In reply to alexander :surkov from comment #29)
> > > > as Jamie pointed out the problem cause is IAccessible::accChild treats
> > > > positive value as child indexes, negative values as unique IDs.
> > > 
> > > yes, but do you have any idea why they are positive, or can you debug it? 
> > > debugging on try is not exactly efficient.
> > 
> > I'm not sure whether flip bits operator is reliable way to convert from
> > positive to negative numbers and vise versa. Why don't you make sure instead
> > that generated ID is in proper range to use -operator?
> 
> it is as I said in comment 27, or you could go read
> http://en.wikipedia.org/wiki/Two%27s_complement the ranges are basically
> identical which ever operator you use, but msvc doesn't like it when you use
> - on a unsigned type.

the point was result of ~operator is implementation dependent, if it's not true then it's cool


> (In reply to Trevor Saunders (:tbsaunde) from comment #30)
> > (In reply to alexander :surkov from comment #29)
> > > as Jamie pointed out the problem cause is IAccessible::accChild treats
> > > positive value as child indexes, negative values as unique IDs.
> > 
> > yes, but do you have any idea why they are positive, or can you debug it? 
> > debugging on try is not exactly efficient.
> 
> interestingly the log at
> http://mozilla-releng-blobs.s3.amazonaws.com/blobs/try/sha512/
> e710c7973cde2c25bcaacc37f77678375e75022d1cd7ebdb0d99343228c7a50c108ce4533ee33
> a53397d47134de47b2598ab998b25f66faa1828d037e4f540f7 really suggests the
> returned ids are negative and there's no bug???

what is "id is 0xffffffff returned id is 0"?

Comment 34

[Trevor Saunders (:tbsaunde)]

> 
> > (In reply to Trevor Saunders (:tbsaunde) from comment #30)
> > > (In reply to alexander :surkov from comment #29)
> > > > as Jamie pointed out the problem cause is IAccessible::accChild treats
> > > > positive value as child indexes, negative values as unique IDs.
> > > 
> > > yes, but do you have any idea why they are positive, or can you debug it? 
> > > debugging on try is not exactly efficient.
> > 
> > interestingly the log at
> > http://mozilla-releng-blobs.s3.amazonaws.com/blobs/try/sha512/
> > e710c7973cde2c25bcaacc37f77678375e75022d1cd7ebdb0d99343228c7a50c108ce4533ee33
> > a53397d47134de47b2598ab998b25f66faa1828d037e4f540f7 really suggests the
> > returned ids are negative and there's no bug???
> 
> what is "id is 0xffffffff returned id is 0"?

what happens when a id hasn't yet been allocated for that object.

Comment 35

[Marco Zehe (:MarcoZ)]

Hi Jamie, can you double-check that the unique IDs are really negative in the try build? I am running with it right now, commenting here, and the NVDA object info for the Additional Comments field looks as follows:

INFO - globalCommands.GlobalCommands.script_navigatorObject_devInfo (10:13:40):
Developer info for navigator object:
name: u'Additional Comments'
role: ROLE_EDITABLETEXT
states: STATE_FOCUSABLE, STATE_EDITABLE, STATE_FOCUSED, STATE_MULTILINE
isFocusable: True
hasFocus: True
Python object: <NVDAObjects.Dynamic_EditableTextWithAutoSelectDetectionMozillaIAccessible object at 0x05DA7790>
Python class mro: (<class 'NVDAObjects.Dynamic_EditableTextWithAutoSelectDetectionMozillaIAccessible'>, <class 'NVDAObjects.behaviors.EditableTextWithAutoSelectDetection'>, <class 'NVDAObjects.behaviors.EditableText'>, <class 'editableText.EditableText'>, <class 'NVDAObjects.IAccessible.mozilla.Mozilla'>, <class 'NVDAObjects.IAccessible.IAccessible'>, <class 'NVDAObjects.window.Window'>, <class 'NVDAObjects.NVDAObject'>, <class 'baseObject.ScriptableObject'>, <class 'baseObject.AutoPropertyObject'>, <type 'object'>)
description: u''
location: (33, 227, 1279, 276)
value: None
appModule: <'firefox' (appName u'firefox', process ID 6952) at address 5da7430>
appModule.productName: u'Nightly'
appModule.productVersion: u'40.0a1'
TextInfo: <class 'NVDAObjects.IAccessible.IA2TextTextInfo'>
windowHandle: 1246164L
windowClassName: u'MozillaWindowClass'
windowControlID: 0
windowStyle: 399441920
windowThreadID: 6524
windowText: u'606080 \u2013 (64bit) fix unique id casting to NS_PTR_TO_INT32 issue - Nightly'
displayText: u''
IAccessibleObject: <POINTER(IAccessible2) ptr=0x5abe34 at 5bc2da0>
IAccessibleChildID: 0
IAccessible event parameters: windowHandle=1246164, objectID=-4, childID=-505
IAccessible accName: u'Additional Comments'
IAccessible accRole: ROLE_SYSTEM_TEXT
IAccessible accState: STATE_SYSTEM_FOCUSED, STATE_SYSTEM_FOCUSABLE, STATE_SYSTEM_VALID (1048580)
IAccessible accDescription: u''
IAccessible accValue: None
IAccessible2 windowHandle: 1246164
IAccessible2 uniqueID: -318068320
IAccessible2 role: ROLE_SYSTEM_TEXT
IAccessible2 states: IA2_STATE_MULTI_LINE, IA2_STATE_OPAQUE, IA2_STATE_EDITABLE (1544)
IAccessible2 attributes: u'margin-left:0px;text-align:start;text-indent:0px;id:comment;tag:textarea;margin-right:0px;margin-top:0px;margin-bottom:13px;display:inline;line-number:1;explicit-name:true;'

As you can see above, the IAccessible2UniqueID is indeed negative. And the text field is definitely part of the document.

I can confirm that the virtual buffer remains empty, but after re-testing, and making sure no other Firefox instances can interfere (e. g. not running with the -no-remote option), the IDs look correct.

Comment 36

[Marco Zehe (:MarcoZ)]

Additional info: When setting NVDA's logging level to Debug, and returning to an empty vitual document of this bug, I get this in the log viewer:

DEBUGWARNING - NVDAObjects.IAccessible.Dynamic_DocumentBrokenFocusedStateMozillaIAccessible._get_IA2Attributes (10:16:46):
IAccessibleObject.attributes COMError (-2147220995, 'Object is not connected to server', (None, None, None, 0, None))
DEBUGWARNING - NVDAObjects.IAccessible.Dynamic_DocumentBrokenFocusedStateMozillaIAccessible._get_IA2Attributes (10:16:46):
IAccessibleObject.attributes COMError (-2147220995, 'Object is not connected to server', (None, None, None, 0, None))
DEBUGWARNING - NVDAObjects.IAccessible.Dynamic_DocumentBrokenFocusedStateMozillaIAccessible._get_IA2Attributes (10:16:46):
IAccessibleObject.attributes COMError (-2147220995, 'Object is not connected to server', (None, None, None, 0, None))
IO - speech.speak (10:16:46):
Speaking [LangChangeCommand ('de_DE'), u'606080 \u2013 (64bit) fix unique id casting to NS_PTR_TO_INT32 issue - Nightly']
IO - braille.BrailleBuffer.update (10:16:46):
Braille regions text: [u'606080 \u2013 (64bit) fix unique id casting to NS_PTR_TO_INT32 issue - Nightly']
IO - braille.BrailleHandler.update (10:16:46):
Braille window dots: 1246 346 1246 346 1256 346 - 36 - 236 1246 1456 12 24 2345 356 - 124 24 1346 - 136 1345 24 12345 136 15 - 24 145 - 14 1 234 2345 24 1345 1245 -
DEBUGWARNING - NVDAObjects.IAccessible.Dynamic_DocumentBrokenFocusedStateMozillaIAccessible._get_IA2Attributes (10:16:46):
IAccessibleObject.attributes COMError (-2147220995, 'Object is not connected to server', (None, None, None, 0, None))
DEBUGWARNING - NVDAObjects.IAccessible.Dynamic_DocumentBrokenFocusedStateMozillaIAccessible._get_IA2Attributes (10:16:46):
IAccessibleObject.attributes COMError (-2147220995, 'Object is not connected to server', (None, None, None, 0, None))
DEBUGWARNING - NVDAObjects.IAccessible.Dynamic_DocumentBrokenFocusedStateMozillaIAccessible._get_IA2Attributes (10:16:46):
IAccessibleObject.attributes COMError (-2147220995, 'Object is not connected to server', (None, None, None, 0, None))
IO - speech.speak (10:16:46):
Speaking [LangChangeCommand ('de_DE'), u'606080 \u2013 (64bit) fix unique id casting to NS_PTR_TO_INT32 issue  document']
DEBUGWARNING - RPC process 6952 (firefox.exe) (10:16:46):
Thread 5580, build\x86_64\vbufBase\storage.cpp, VBufStorage_buffer_t::getLineOffsets, 985:
Offset of 0 too big for buffer, returning false

IO - speech.speak (10:16:46):
Speaking [LangChangeCommand ('de_DE'), u'blank']
DEBUGWARNING - RPC process 6952 (firefox.exe) (10:16:46):
Thread 5580, build\x86_64\vbufBase\storage.cpp, VBufStorage_buffer_t::getLineOffsets, 985:
Offset of 0 too big for buffer, returning false

IO - braille.BrailleBuffer.update (10:16:46):
Braille regions text: [u'606080 \u2013 (64bit) fix unique id casting to NS_PTR_TO_INT32 issue - Nightly ', u'606080 \u2013 (64bit) fix unique id casting to NS_PTR_TO_INT32 issue document ', ' ']
IO - braille.BrailleHandler.update (10:16:46):
Braille window dots: -
IO - braille.BrailleHandler.update (10:16:46):
Braille window dots: -

Comment 37

[Trevor Saunders (:tbsaunde)]

> I can confirm that the virtual buffer remains empty, but after re-testing,
> and making sure no other Firefox instances can interfere (e. g. not running
> with the -no-remote option), the IDs look correct.

actually the interesting one is the childID that came with the event arguments, which is also negative and looks about right.  This does make me realize an issue though while I changed the code that gets id for events I forgot about IAccessible2::UniqueID and didn't update that.  the ia2 unique id does happen to be null in this case, but I think that's a fluke (and trying to get the accessible for it definitely wont work).  I could easily believe Jamie is seeing positive ids come out of the ia2 unique id.

Comment 38

[Marco Zehe (:MarcoZ)]

Cool that this helped! OK, Trev, let me know when you've got a fix and a new try build kicked off so we can re-test. :)

Comment 39

[James Teh [:Jamie]]

I just re-tested. I'm seeing both positive and negative values from IAccessible2::uniqueID. And yeah, the event child id does look more correct; I was quite surprised that the ids still looked like memory locations. :)

Comment 40

[Trevor Saunders (:tbsaunde)]

lets see how https://treeherder.mozilla.org/#/jobs?repo=try&revision=5f5076c7ba32 works out

Comment 41

[Marco Zehe (:MarcoZ)]

Direct link to Win64 try builds: http://ftp.mozilla.org/pub/mozilla.org/firefox/try-builds/[e-mail]-5f5076c7ba32/try-win64/

Comment 42

[Marco Zehe (:MarcoZ)]

Success! This new try build works with NVDA including the virtual buffer. All web navigation is possible as in the 32 bit version. Menus, context menus, the surrounding browser chrome, all work as expected.

Comment 43

[Marco Zehe (:MarcoZ)]

JAWS, on the other hand, does not get its virtual buffers sorted out. I suspect that we're not starting the special window emulation mode for them correctly. However, that is an issue that can be dealt with in a separate bug. NVDA works, and that's the most important step to get accessibility working in 64 bit in principle.

Comment 44

[Trevor Saunders (:tbsaunde)]

Attachment: add class to generate unique 32 bit ids

Comment 45

[Nathan Froyd [:froydnj]]

Comment on attachment 8598164 [details] [diff] [review]
add class to generate unique 32 bit ids

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

I don't think this is the right data structure for what you're trying to do.  A radix tree seems like a better fit: you get logarithmic time GetID and ReleaseID, and you have some assurances that your GetID operation is efficient.

::: mfbt/IDSet.h
@@ +38,5 @@
> +    do {
> +      if (elt->bitvec[0] != UINT64_MAX) {
> +        uint32_t i = 0;
> +        while (elt->bitvec[0] & (1ull << i))
> +          i++;

This is expressed more concisely, if not quite as clearly, as:

uint32_t i = CountTrailingZeros64(~elt->bitvec[0]);

@@ +62,5 @@
> +      if (nextIdx == firstIdx) {
> +        MOZ_CRASH("used up all the available ids");
> +      }
> +
> +      elt = mBitSet.LookupOrAdd(BitSetElt(nextIdx));

Seems like this is going to miss the case when the root is full and there are available bits in elements to the left of the root: we'll create a whole new element for no good reason.

@@ +77,5 @@
> +    MOZ_ASSERT(elt);
> +
> +    uint32_t vecIdx = (aID % bitsPerElt) / 64;
> +    elt->bitvec[vecIdx] &= ~(1ull << (aID % 64));
> +    if (elt->bitvec[0] == 0 && elt->bitvec[1] == 0) {

I feel like some of these accesses into BitSetElt should really be methods on BitSetElt itself.

@@ +91,5 @@
> +    explicit BitSetElt(uint32_t aIdx) :
> +      mIdx(aIdx)
> +    { bitvec[0] = bitvec[1] = 0; }
> +
> +    uint64_t bitvec[2];

mBitVec or mBitvec, please.

@@ +108,5 @@
> +    }
> +  };
> +
> +  static const unsigned int bitsPerWord = 64;
> +  static const unsigned int bitsPerElt = 2 * bitsPerWord;

Seems better to do something like:

typedef uint64_t BitvecType;
BitvecType mBitvec[2];
...
static const unsigned int bitsPerWord = sizeof(BitvecType) * CHAR_BIT;
static const unsigned int bitsPerElt = ArrayLength(mBitVec) * bitsPerWord;

::: mfbt/moz.build
@@ +36,5 @@
>      'EnumSet.h',
>      'FloatingPoint.h',
>      'GuardObjects.h',
>      'HashFunctions.h',
> +    'IDSet.h',

I don't think this is general enough to belong in MFBT.

Comment 46

[Trevor Saunders (:tbsaunde)]

> I don't think this is the right data structure for what you're trying to do.
> A radix tree seems like a better fit: you get logarithmic time GetID and
> ReleaseID, and you have some assurances that your GetID operation is
> efficient.

yeah quiet possible, but I don't think I want to spend the time to implement that.

> @@ +62,5 @@
> > +      if (nextIdx == firstIdx) {
> > +        MOZ_CRASH("used up all the available ids");
> > +      }
> > +
> > +      elt = mBitSet.LookupOrAdd(BitSetElt(nextIdx));
> 
> Seems like this is going to miss the case when the root is full and there
> are available bits in elements to the left of the root: we'll create a whole
> new element for no good reason.

that's true, though I'm not really sure how you generically avoid that (though I did consider alternating between looking right and left) but I'm not sure it really matters in practice.  The root should almost always have a empty bit since after each release the root will have at least one empty slot, and if you are forced to create a new node you'll leave a root with many free slots.  That said yeah it could in a really bad case be N/2 but for that to happen you need to have tons of objects allocated for it to really matter.

> >      'FloatingPoint.h',
> >      'GuardObjects.h',
> >      'HashFunctions.h',
> > +    'IDSet.h',
> 
> I don't think this is general enough to belong in MFBT.

that's reasonable, I was mostly thinking of it as a protobitmap.  I guess I'll just drop this somewhere in accessible/windows/ then.

Comment 47

[Nathan Froyd [:froydnj]]

(In reply to Trevor Saunders (:tbsaunde) from comment #46)
> > I don't think this is the right data structure for what you're trying to do.
> > A radix tree seems like a better fit: you get logarithmic time GetID and
> > ReleaseID, and you have some assurances that your GetID operation is
> > efficient.
> 
> yeah quiet possible, but I don't think I want to spend the time to implement
> that.

Fair point.

Another possibility is that you use a little pseudo-random-number generator that generates numbers from 0 to 2^31-1 (these are relatively easy to construct), and for GetID, you write something like:

  bitsPerElt = 64;
next:
  n = getNextRandomNumber();
  eltIndex = n / bitsPerElt;
  elt = mBitSet.lookup(BitSetElt(eltIndex));
  if !elt:
     elt = mBitSet.add(BitSetElt(eltIndex));
  bitIndex = n % 64;
  if elt.hasBit(bitIndex):
     goto next;
  elt.setBit(bitIndex);
  return n;

Sure, it's linear in the worst case, but that would require a very full tree.  And you can adjust your walk through [0, 2^31-1) so that the numbers stay sorta-close together, and maybe you get some locality.

Making GetID efficient is the hard part, and I think you may just have to accept worst-case linear time, even if average is pretty good.  (Or write some complex data structure.)  Depends too on what the usage patterns are like.

> > >      'FloatingPoint.h',
> > >      'GuardObjects.h',
> > >      'HashFunctions.h',
> > > +    'IDSet.h',
> > 
> > I don't think this is general enough to belong in MFBT.
> 
> that's reasonable, I was mostly thinking of it as a protobitmap.  I guess
> I'll just drop this somewhere in accessible/windows/ then.

I think the requirement for [0, 2^31-1) is too specific for this particular bug.

Comment 48

[Nathan Froyd [:froydnj]]

Then again, why use a random number generator?  Just start counting from 0 and wraparound.

I guess that may not make effective use of earlier bitset elements, but maybe you can work around that with a small cache of "non-full bitset elements" or something...

Comment 49

[Trevor Saunders (:tbsaunde)]

(In reply to Nathan Froyd [:froydnj] [:nfroyd] from comment #47)
> (In reply to Trevor Saunders (:tbsaunde) from comment #46)
> > > I don't think this is the right data structure for what you're trying to do.
> > > A radix tree seems like a better fit: you get logarithmic time GetID and
> > > ReleaseID, and you have some assurances that your GetID operation is
> > > efficient.
> > 
> > yeah quiet possible, but I don't think I want to spend the time to implement
> > that.
> 
> Fair point.
> 
> Another possibility is that you use a little pseudo-random-number generator
> that generates numbers from 0 to 2^31-1 (these are relatively easy to
> construct), and for GetID, you write something like:
> 
>   bitsPerElt = 64;
> next:
>   n = getNextRandomNumber();
>   eltIndex = n / bitsPerElt;
>   elt = mBitSet.lookup(BitSetElt(eltIndex));
>   if !elt:
>      elt = mBitSet.add(BitSetElt(eltIndex));
>   bitIndex = n % 64;
>   if elt.hasBit(bitIndex):
>      goto next;
>   elt.setBit(bitIndex);
>   return n;
> 
> Sure, it's linear in the worst case, but that would require a very full
> tree.  And you can adjust your walk through [0, 2^31-1) so that the numbers
> stay sorta-close together, and maybe you get some locality.

that might be faster (though I kind of wonder about that on one hand your more likely to not start at a fully allocated node, but your more likely to need to malloc I think) but I think that approach is worse because it'll probably use more memory.

I think if you always start at 0 and go up you'll end up doing the linear case much more often.  Keeping a counter and incrementing it every 128 allocations would work, but I think your node reuse would be worse than the start at the root approach.

That said I guess I can get away without adding root() to SplayTree by recording the last index I used in either GetID or ReleaseID.

> Making GetID efficient is the hard part, and I think you may just have to
> accept worst-case linear time, even if average is pretty good.  (Or write
> some complex data structure.)  Depends too on what the usage patterns are
> like.

yeah, fast and not use gobs of memory is hard and I think average fast, but there's a rare linear time case is probably acceptable.

> > > >      'FloatingPoint.h',
> > > >      'GuardObjects.h',
> > > >      'HashFunctions.h',
> > > > +    'IDSet.h',
> > > 
> > > I don't think this is general enough to belong in MFBT.
> > 
> > that's reasonable, I was mostly thinking of it as a protobitmap.  I guess
> > I'll just drop this somewhere in accessible/windows/ then.
> 
> I think the requirement for [0, 2^31-1) is too specific for this particular
> bug.

yeah, so I'll agree dumping it in accessible/windows makes sense, and if someone else ever needs a sparse bitset type thing we can think about merging them or something.

Comment 50

[Trevor Saunders (:tbsaunde)]

Attachment: add SplayTree::LookupOrAdd

Comment 51

[Trevor Saunders (:tbsaunde)]

Attachment: add class to generate unique 32 bit ids

Comment 52

[Trevor Saunders (:tbsaunde)]

Attachment: on windows give accessibles a unique 32 bit id

Comment 53

[Nathan Froyd [:froydnj]]

Comment on attachment 8599286 [details] [diff] [review]
add SplayTree::LookupOrAdd

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

Ugh, I wish there was a good way to make |insert| do this, since it could tell you whether the node has been inserted into the tree, but that gets into issues of memory management that probably aren't appropriate for this patch.  And you want access to the node if it was already present, which means |insert| would have to be re-worked.

I can see why the STL does everything with references instead of pointers.

Please file a followup bug for figuring out how to unify |insert| and |findOrInsert|.  Thanks.

::: mfbt/SplayTree.h
@@ +95,5 @@
>      splay(aValue);
>      return true;
>    }
>  
> +  T* LookupOrAdd(const T& aValue)

Nit: mfbt is still using JS style for method names.  I think the name should be consistent with the operations it seeks to combine, so the name should be findOrInsert.

Please also move the definition of the method out-of-line.  I think that will make SplayTree continue to be usable with types that are not copy constructable, so long as you're not using findOrInsert.  If you felt so inclined, a test to ensure that would be great.

@@ +98,5 @@
>  
> +  T* LookupOrAdd(const T& aValue)
> +  {
> +    if (!mRoot) {
> +      return mRoot = new T(aValue);

Nit: Please make this multiple statements.

@@ +109,5 @@
> +    }
> +
> +    T** parentPointer = (cmp < 0) ? &last->mLeft : &last->mRight;
> +    MOZ_ASSERT(!*parentPointer);
> +    T* inserted = new T(aValue);

Might as well make this block of code:

  return finishInsertion(last, cmp, new T(aValue));

and use it in |insert| so that we're not copy-pasting the *whole* function. ;)

Comment 54

[alexander :surkov (:asurkov)]

Comment on attachment 8599287 [details] [diff] [review]
add class to generate unique 32 bit ids

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

Nathan is probably better reviewer for this

::: accessible/windows/msaa/IDSet.h
@@ +16,5 @@
> +#include "mozilla/SplayTree.h"
> +
> +namespace mozilla {
> +
> +class IDSet

located in accessible folder but no in a11y namespace, a bit strange

Comment 55

[alexander :surkov (:asurkov)]

Comment on attachment 8599288 [details] [diff] [review]
on windows give accessibles a unique 32 bit id

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

::: accessible/windows/msaa/AccessibleWrap.cpp
@@ +67,5 @@
>  ////////////////////////////////////////////////////////////////////////////////
> +AccessibleWrap::AccessibleWrap(nsIContent* aContent, DocAccessible* aDoc) :
> +  Accessible(aContent, aDoc)
> +#ifdef _WIN64
> +  , mID(UINT32_MAX)

might be nice to have constant for this like
const kUnitializedID = UINT32_MAX

@@ +72,5 @@
> +#endif
> +{
> +}
> +
> +  AccessibleWrap::~AccessibleWrap()

style: indentation

@@ +85,5 @@
>  
>  NS_IMPL_ISUPPORTS_INHERITED0(AccessibleWrap, Accessible)
>  
> +  void
> +  AccessibleWrap::Shutdown()

style: indentation

@@ +89,5 @@
> +  AccessibleWrap::Shutdown()
> +{
> +#ifdef _WIN64
> +  if (mID != UINT32_MAX)
> +    static_cast<DocAccessibleWrap*>(mDoc)->RemoveID(mID);

I think we should keep ID even after shutdown, let's get back it into the pull when object is destroyed

@@ +1296,5 @@
> +    return 0;
> +
> +  uint32_t* id = & static_cast<AccessibleWrap*>(aAccessible)->mID;
> +  if (*id != UINT32_MAX)
> +    return ~*id;

can you incapsulate that ~ in IDSet?

@@ +1410,5 @@
>      void* uniqueID = reinterpret_cast<void*>(-aVarChild.lVal);
>  
>      DocAccessible* document = Document();
>      Accessible* child =
> +#ifndef _WIN64

nit: I would stay consistent and used #ifdef

@@ +1415,3 @@
>        document->GetAccessibleByUniqueIDInSubtree(uniqueID);
> +#else
> +    GetAccessibleInSubtree(document, ~static_cast<uint32_t>(aVarChild.lVal));

you could have overloaded GetAccessibleByUniqueIDInSubtree(uint32_t), same naming, one style, or if you don't like overloads then you could have GetAccessibleByMSAAUniqueIDInSubtree

::: accessible/windows/msaa/DocAccessibleWrap.h
@@ +38,5 @@
> +   * Manage the mapping from id to Accessible.
> +   */
> +#ifdef _WIN64
> +  void AddID(uint32_t aID, AccessibleWrap* aAcc)
> +  { mIDToAccessibleMap.Put(aID, aAcc); }

style: two spaces indent before {

Comment 56

[Nathan Froyd [:froydnj]]

Comment on attachment 8599287 [details] [diff] [review]
add class to generate unique 32 bit ids

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

No problems with the code, but I think it could more clearly separate IDSet-things from BitSetElt-things.  I wish we could use std::bitset or std::vector<bool>, but I doubt they'd be efficient enough; std::bitset also doesn't have the bits we need.

::: accessible/windows/msaa/IDSet.h
@@ +4,5 @@
> + * License, v. 2.0. If a copy of the MPL was not distributed with this
> + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
> +
> +/**
> + * A class to generate unique integers in the range [ 0, 2^31 - 1 ]

Some additional commentary on why we want this class would be good and a sketch of the implementation.  Something like (bearing in mind that I'm hardly knowledgeable about accessibility stuff):

"Accessible elements must have 32-bit unique IDs, and the unique IDs must be negative.  Since elements may be added and removed from the page at any time, it is important to support recycling IDs that are no longer in use.  IDSet therefore provides two operations: generating a unique ID in the range [0, 2^31-1] and releasing a previously generated ID, making it eligible to be generated again.  We track previously generated IDs using a sparse bitmap, implemented as a splay tree.  Nodes in the tree are keyed by the upper N bits of IDs, and each node tracks the usage of 2^(32 - N) IDs in a small bitmap."

That's probably abusing "unique" and could use a little more polish, but that's the idea.

@@ +8,5 @@
> + * A class to generate unique integers in the range [ 0, 2^31 - 1 ]
> + */
> +
> +#ifndef MOZILLA_IDSet_h_
> +#define MOZILLA_IDSet_h_

Nit: I think these guards should be "mozilla_a11y_IDSet_h".

@@ +29,5 @@
> +  {
> +    uint32_t idx = mIdx;
> +    while (true) {
> +      BitSetElt* elt = mBitSet.LookupOrAdd(BitSetElt(idx));
> +      if (elt->mBitvec[0] != UINT64_MAX) {

I think these next two blocks should be replaced with:

uint32_t bitIndex = 0;

if (elt->findFreeBit(&bitIndex)) {
  mIdx = idx;
  return idx + bitIndex;
}

// Otherwise, no free bits for that element.  Try the next one.
...

I don't know if we'll be able to completely keep BitSetElt innards out of IDSet, but I think it'd be good to try.

@@ +46,5 @@
> +        return elt->mIdx * bitsPerElt + bitsPerWord + i;
> +      }
> +
> +      idx++;
> +      if ((idx * bitsPerElt) > INT32_MAX) {

I think this is clearer as:

// Find next index and wraparound if we need to.
idx++;
if (idx > sMaxIndex) {
  idx = 0;
}

and sMaxIndex should be defined appropriately below.

@@ +61,5 @@
> +   * Free a no longer required id so it may be allocated again.
> +   */
> +  void ReleaseID(uint32_t aID)
> +  {
> +    uint32_t idx = aID / bitsPerElt;

Maybe |idx = BitSetElt::indexForId(aID)|?

Probably not a bad idea to:

MOZ_ASSERT(aID <= INT32_MAX);

or similar.

@@ +67,5 @@
> +    BitSetElt* elt = mBitSet.find(BitSetElt(idx));
> +    MOZ_ASSERT(elt);
> +
> +    uint32_t vecIdx = (aID % bitsPerElt) / 64;
> +    elt->mBitvec[vecIdx] &= ~(1ull << (aID % 64));

These bare 64s should be |bitsPerWord|.

Please rewrite as:

elt->clearBitForID(aID);

with the obvious implementation of BitSetElt::clearBitForID.

@@ +68,5 @@
> +    MOZ_ASSERT(elt);
> +
> +    uint32_t vecIdx = (aID % bitsPerElt) / 64;
> +    elt->mBitvec[vecIdx] &= ~(1ull << (aID % 64));
> +    if (elt->mBitvec[0] == 0 && elt->mBitvec[1] == 0) {

Please make this a predicate on BitSetElt:

bool isEmpty() const;

with the obvious implementation.

@@ +80,5 @@
> +    explicit BitSetElt(uint32_t aIdx) :
> +      mIdx(aIdx)
> +    { mBitvec[0] = mBitvec[1] = 0; }
> +
> +    uint64_t mBitvec[2];

Please |static const size_t sNumElements = 2;| somewhere, and use it here and in the definition of |bitsPerElt| below.

If you want to typedef uint64_t and then use that name in defining |bitsPerWord| below, that'd be great too.

@@ +81,5 @@
> +      mIdx(aIdx)
> +    { mBitvec[0] = mBitvec[1] = 0; }
> +
> +    uint64_t mBitvec[2];
> +    uint32_t mIdx;

Total nit: let's move this before mBitvec to pack better on 64-bit systems.

Comment 57

[Trevor Saunders (:tbsaunde)]

(In reply to Nathan Froyd [:froydnj] [:nfroyd] from comment #56)
> Comment on attachment 8599287 [details] [diff] [review]
> add class to generate unique 32 bit ids
> 
> Review of attachment 8599287 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> No problems with the code, but I think it could more clearly separate
> IDSet-things from BitSetElt-things.  I wish we could use std::bitset or
> std::vector<bool>, but I doubt they'd be efficient enough; std::bitset also
> doesn't have the bits we need.


I'm not actually that convinced its worth separating the bitset implementation from the rest of this, but maybe you want to  use it for something else?

I was digging around in libstdc++'s bitset a little while ago for something else and I suspect it might be fast enough, but not having the methods we need is important and it just didn't seem like enough code for me to really think about it when writing this.

> @@ +81,5 @@
> > +      mIdx(aIdx)
> > +    { mBitvec[0] = mBitvec[1] = 0; }
> > +
> > +    uint64_t mBitvec[2];
> > +    uint32_t mIdx;
> 
> Total nit: let's move this before mBitvec to pack better on 64-bit systems.

does it actually pack better? we're going to have

T*
T*
T*
uint64_t[2]
uint32_t
32 bit pad

and if we switch it I'd sort of guess the uint64_t will want to be 8 byte aligned?  Even if that's not required does that help use sse instructions to do both elements at once?

Comment 58

[Nathan Froyd [:froydnj]]

(In reply to Trevor Saunders (:tbsaunde) from comment #57)
> (In reply to Nathan Froyd [:froydnj] [:nfroyd] from comment #56)
> > Comment on attachment 8599287 [details] [diff] [review]
> > add class to generate unique 32 bit ids
> > 
> > Review of attachment 8599287 [details] [diff] [review]:
> > -----------------------------------------------------------------
> > 
> > No problems with the code, but I think it could more clearly separate
> > IDSet-things from BitSetElt-things.  I wish we could use std::bitset or
> > std::vector<bool>, but I doubt they'd be efficient enough; std::bitset also
> > doesn't have the bits we need.
> 
> I'm not actually that convinced its worth separating the bitset
> implementation from the rest of this, but maybe you want to  use it for
> something else?

I don't mean separate them in terms of making BitSetElt a standalone thing, I mean separating them so IDSet isn't digging around in BitSetElt's internals all the time.  I think it's helpful if there's as much delineation as possible between the two, even if they are tightly coupled in terms of what they're being used for.

> I was digging around in libstdc++'s bitset a little while ago for something
> else and I suspect it might be fast enough, but not having the methods we
> need is important and it just didn't seem like enough code for me to really
> think about it when writing this.

Fair enough.  I was going to ask you to use bitset, but I double-checked and discovered it didn't have a "find first zero element" operation, which makes it unsuitable for this case.

> > @@ +81,5 @@
> > > +      mIdx(aIdx)
> > > +    { mBitvec[0] = mBitvec[1] = 0; }
> > > +
> > > +    uint64_t mBitvec[2];
> > > +    uint32_t mIdx;
> > 
> > Total nit: let's move this before mBitvec to pack better on 64-bit systems.
> 
> does it actually pack better? we're going to have
> 
> T*
> T*
> T*
> uint64_t[2]
> uint32_t
> 32 bit pad

Doh.  I mixed things up and thought the T* would be 32-bit, but that'd be pretty dumb on a 64-bit system, wouldn't it?  The current variable ordering is fine.

Comment 59

[Trevor Saunders (:tbsaunde)]

(In reply to Nathan Froyd [:froydnj] [:nfroyd] from comment #58)
> (In reply to Trevor Saunders (:tbsaunde) from comment #57)
> > (In reply to Nathan Froyd [:froydnj] [:nfroyd] from comment #56)
> > > Comment on attachment 8599287 [details] [diff] [review]
> > > add class to generate unique 32 bit ids
> > > 
> > > Review of attachment 8599287 [details] [diff] [review]:
> > > -----------------------------------------------------------------
> > > 
> > > No problems with the code, but I think it could more clearly separate
> > > IDSet-things from BitSetElt-things.  I wish we could use std::bitset or
> > > std::vector<bool>, but I doubt they'd be efficient enough; std::bitset also
> > > doesn't have the bits we need.
> > 
> > I'm not actually that convinced its worth separating the bitset
> > implementation from the rest of this, but maybe you want to  use it for
> > something else?
> 
> I don't mean separate them in terms of making BitSetElt a standalone thing,
> I mean separating them so IDSet isn't digging around in BitSetElt's
> internals all the time.  I think it's helpful if there's as much delineation
> as possible between the two, even if they are tightly coupled in terms of
> what they're being used for.

I can see that being good in principal, but in practice I find it hard to care enough to want to bother do that.

> > > @@ +81,5 @@
> > > > +      mIdx(aIdx)
> > > > +    { mBitvec[0] = mBitvec[1] = 0; }
> > > > +
> > > > +    uint64_t mBitvec[2];
> > > > +    uint32_t mIdx;
> > > 
> > > Total nit: let's move this before mBitvec to pack better on 64-bit systems.
> > 
> > does it actually pack better? we're going to have
> > 
> > T*
> > T*
> > T*
> > uint64_t[2]
> > uint32_t
> > 32 bit pad
> 
> Doh.  I mixed things up and thought the T* would be 32-bit, but that'd be
> pretty dumb on a 64-bit system, wouldn't it?  The current variable ordering
> is fine.

yeah, if that was the case we wouldn't be jumping through these crazy hoops ;)

Comment 60

[Nathan Froyd [:froydnj]]

(In reply to Trevor Saunders (:tbsaunde) from comment #59)
> (In reply to Nathan Froyd [:froydnj] [:nfroyd] from comment #58)
> > I don't mean separate them in terms of making BitSetElt a standalone thing,
> > I mean separating them so IDSet isn't digging around in BitSetElt's
> > internals all the time.  I think it's helpful if there's as much delineation
> > as possible between the two, even if they are tightly coupled in terms of
> > what they're being used for.
> 
> I can see that being good in principal, but in practice I find it hard to
> care enough to want to bother do that.

*shrug* OK.

I talked with Alexander offline about this and he indicated getting this landed is more important than crossing all the t's and dotting all the i's.  If you could address the parts of the review not related to separating IDSet and BitSetElt, I think we can r+ this and move on.  Thanks.

Comment 61

[Trevor Saunders (:tbsaunde)]

(In reply to Nathan Froyd [:froydnj] [:nfroyd] from comment #60)
> (In reply to Trevor Saunders (:tbsaunde) from comment #59)
> > (In reply to Nathan Froyd [:froydnj] [:nfroyd] from comment #58)
> > > I don't mean separate them in terms of making BitSetElt a standalone thing,
> > > I mean separating them so IDSet isn't digging around in BitSetElt's
> > > internals all the time.  I think it's helpful if there's as much delineation
> > > as possible between the two, even if they are tightly coupled in terms of
> > > what they're being used for.
> > 
> > I can see that being good in principal, but in practice I find it hard to
> > care enough to want to bother do that.
> 
> *shrug* OK.

thanks, fwiw I am curious to understand what you think the benefits are.

Comment 62

[Sylvestre Ledru [:Sylvestre]]

This is too late for 38 but we would be happy to take a patch for 39.

Comment 63

[alexander :surkov (:asurkov)]

Comment on attachment 8599288 [details] [diff] [review]
on windows give accessibles a unique 32 bit id

cancelling until comment 55 is addressed

Comment 64

[Trevor Saunders (:tbsaunde)]

> @@ +89,5 @@
> > +  AccessibleWrap::Shutdown()
> > +{
> > +#ifdef _WIN64
> > +  if (mID != UINT32_MAX)
> > +    static_cast<DocAccessibleWrap*>(mDoc)->RemoveID(mID);
> 
> I think we should keep ID even after shutdown, let's get back it into the
> pull when object is destroyed

the object still has the id, the documents mapping for it has just been removed, and you can't do that any later because Accessible::Shutdown makes mDoc null.

> @@ +1296,5 @@
> > +    return 0;
> > +
> > +  uint32_t* id = & static_cast<AccessibleWrap*>(aAccessible)->mID;
> > +  if (*id != UINT32_MAX)
> > +    return ~*id;
> 
> can you incapsulate that ~ in IDSet?

I guess at his point that makes sense.

> @@ +1410,5 @@
> >      void* uniqueID = reinterpret_cast<void*>(-aVarChild.lVal);
> >  
> >      DocAccessible* document = Document();
> >      Accessible* child =
> > +#ifndef _WIN64
> 
> nit: I would stay consistent and used #ifdef

*shrug* ok

> @@ +1415,3 @@
> >        document->GetAccessibleByUniqueIDInSubtree(uniqueID);
> > +#else
> > +    GetAccessibleInSubtree(document, ~static_cast<uint32_t>(aVarChild.lVal));
> 
> you could have overloaded GetAccessibleByUniqueIDInSubtree(uint32_t), same
> naming, one style, or if you don't like overloads then you could have
> GetAccessibleByMSAAUniqueIDInSubtree

having over loads for uint32_t and void * seems close enough together to be dangerious, and its not msaa only.

Comment 65

[Trevor Saunders (:tbsaunde)]

Attachment: add SplayTree::findOrInsert

Comment 66

[Trevor Saunders (:tbsaunde)]

Attachment: add class to generate unique 32 bit ids

Comment 67

[Trevor Saunders (:tbsaunde)]

Attachment: on windows give accessibles a unique 32 bit id

Comment 68

[alexander :surkov (:asurkov)]

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

> > I think we should keep ID even after shutdown, let's get back it into the
> > pull when object is destroyed
> 
> the object still has the id, the documents mapping for it has just been
> removed, and you can't do that any later because Accessible::Shutdown makes
> mDoc null.

I see, what is probability of having two objects with same ID?

> > @@ +1415,3 @@
> > >        document->GetAccessibleByUniqueIDInSubtree(uniqueID);
> > > +#else
> > > +    GetAccessibleInSubtree(document, ~static_cast<uint32_t>(aVarChild.lVal));
> > 
> > you could have overloaded GetAccessibleByUniqueIDInSubtree(uint32_t), same
> > naming, one style, or if you don't like overloads then you could have
> > GetAccessibleByMSAAUniqueIDInSubtree
> 
> having over loads for uint32_t and void * seems close enough together to be
> dangerious, and its not msaa only.

who else needs that? My concern is method naming feels quite different but they do basically same thing.

Comment 69

[Trevor Saunders (:tbsaunde)]

(In reply to alexander :surkov from comment #68)
> (In reply to Trevor Saunders (:tbsaunde) from comment #64)
> 
> > > I think we should keep ID even after shutdown, let's get back it into the
> > > pull when object is destroyed
> > 
> > the object still has the id, the documents mapping for it has just been
> > removed, and you can't do that any later because Accessible::Shutdown makes
> > mDoc null.
> 
> I see, what is probability of having two objects with same ID?

0? the id isn't released back to be reallocated till the destructor, but you just can't look it up after this.

> > > @@ +1415,3 @@
> > > >        document->GetAccessibleByUniqueIDInSubtree(uniqueID);
> > > > +#else
> > > > +    GetAccessibleInSubtree(document, ~static_cast<uint32_t>(aVarChild.lVal));
> > > 
> > > you could have overloaded GetAccessibleByUniqueIDInSubtree(uint32_t), same
> > > naming, one style, or if you don't like overloads then you could have
> > > GetAccessibleByMSAAUniqueIDInSubtree
> > 
> > having over loads for uint32_t and void * seems close enough together to be
> > dangerious, and its not msaa only.
> 
> who else needs that? My concern is method naming feels quite different but
> they do basically same thing.

and that's a problem because?  The problem is its not clear how you do lookup if it isn't clear which function you call.

Comment 70

[alexander :surkov (:asurkov)]

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

> > I see, what is probability of having two objects with same ID?
> 
> 0? the id isn't released back to be reallocated till the destructor, but you
> just can't look it up after this.

I missed you've changed this part from the last patch. Ignore it.

> > > > @@ +1415,3 @@
> > > > >        document->GetAccessibleByUniqueIDInSubtree(uniqueID);
> > > > > +#else
> > > > > +    GetAccessibleInSubtree(document, ~static_cast<uint32_t>(aVarChild.lVal));
> > > > 
> > > > you could have overloaded GetAccessibleByUniqueIDInSubtree(uint32_t), same
> > > > naming, one style, or if you don't like overloads then you could have
> > > > GetAccessibleByMSAAUniqueIDInSubtree
> > > 
> > > having over loads for uint32_t and void * seems close enough together to be
> > > dangerious, and its not msaa only.
> > 
> > who else needs that? My concern is method naming feels quite different but
> > they do basically same thing.
> 
> and that's a problem because?  The problem is its not clear how you do
> lookup if it isn't clear which function you call.

GetAccessibleByUniqueIDInSubtree says me that this method finds an accessible by unique id, GetAccessibleInSubtree says me if finds an accessible I-don't-know-how. So I see that win32 search is prepared by uniqueid, win64 is different, and I can't say what difference is. So that's why I wanted to be more specific and I would prefer longer name if it was more descriptive. If you dislike GetAccessibleByMSAAUniqueIDInSubtree then GetAccessibleBy32BitUniqueIDInSubtree might be better. Alternatively GetAccessibleByUniqueIDInSubtree could be changed on something shorter. Anyway it doesn't feel like a stopper, it's just code style issue.

Comment 71

[Nathan Froyd [:froydnj]]

Comment on attachment 8601071 [details] [diff] [review]
add SplayTree::findOrInsert

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

::: mfbt/SplayTree.h
@@ +203,5 @@
> +  *parentPointer = aNew;
> +  aNew->mParent = aLast;
> +
> +  splay(aNew);
> +  return aNew;

Nit: indentation for these last four lines of code seems wrong.

Comment 72

[Nathan Froyd [:froydnj]]

Comment on attachment 8601072 [details] [diff] [review]
add class to generate unique 32 bit ids

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

r=me with the changes below.

::: accessible/windows/msaa/IDSet.h
@@ +3,5 @@
> +/* This Source Code Form is subject to the terms of the Mozilla Public
> + * License, v. 2.0. If a copy of the MPL was not distributed with this
> + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
> +
> +/**

Please put back the

/* A class to generate unique integers in the range [ -2^31, 0 ) */

comment from the previous patch back in prior to this block comment, for the benefit of MXR and company.

@@ +4,5 @@
> + * License, v. 2.0. If a copy of the MPL was not distributed with this
> + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
> +
> +/**
> + * On windows accessible's id must be a negative 32 bit integer.  It is

Nit: "On Windows, an accessible's id..."

@@ +7,5 @@
> +/**
> + * On windows accessible's id must be a negative 32 bit integer.  It is
> + * important to support recycling arbitrary IDs because accessibles can be
> + * created and destroyed at any time in the life of a page.  IDSet provides 2
> + * operations generate an ID in the range [ - 2^31, 0 ], and release an ID so

Nit: "operations: generate an ID in the range [ -2^31, 0 ), and..."

@@ +10,5 @@
> + * created and destroyed at any time in the life of a page.  IDSet provides 2
> + * operations generate an ID in the range [ - 2^31, 0 ], and release an ID so
> + * it can be allocated again.  Allocated ID are tracked by a sparse bitmap
> + * implemented with a splay tree.  Nodes in the tree are keyed by the upper N
> + * bits of the ID, and the node contains a bitmap tracking the allocation of

Let's say "N bits of the bitwise negation of the ID..." here.

@@ +54,5 @@
> +        return ~(elt->mIdx * bitsPerElt + bitsPerWord + i);
> +      }
> +
> +      idx++;
> +      if (idx > sMaxID) {

This constant should really be called sMaxIndex, since it's not an ID.

@@ +70,5 @@
> +   */
> +  void ReleaseID(uint32_t aID)
> +  {
> +  aID = ~aID;
> +  MOZ_ASSERT(aID < static_cast<uint32_t>(INT32_MAX));

Nit: indentation on these lines seems wrong.

Comment 73

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/ed3aed8b899f
https://hg.mozilla.org/integration/mozilla-inbound/rev/28c2b07d197c
https://hg.mozilla.org/integration/mozilla-inbound/rev/ffa79d70878f

Comment 74

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/ed3aed8b899f
https://hg.mozilla.org/mozilla-central/rev/28c2b07d197c
https://hg.mozilla.org/mozilla-central/rev/ffa79d70878f

Comment 75

[Liz Henry (:lizzard) (relman/hg->git project)]

Trevor since this affects 39 as well as 40, do you want to request uplift to beta? 
If so I would want to make sure that someone can commit to test and verify the fix on 39.

Comment 76

[Marco Zehe (:MarcoZ)]

Liz, I can test the fix once it lands in a build on 39.

Comment 77

[Trevor Saunders (:tbsaunde)]

(In reply to Liz Henry (:lizzard) from comment #75)
> Trevor since this affects 39 as well as 40, do you want to request uplift to
> beta? 
> If so I would want to make sure that someone can commit to test and verify
> the fix on 39.

I've delegated deciding that to david.

Comment 78

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

At this time WONTFIX for 39 is the way to go.

I'm not sure how to track it but depending on the 64 bit FF Windows 10 ESR schedule/plan (TBD) we *may* need to revisit this.

Comment 79

[Sylvestre Ledru [:Sylvestre]]

Added to the release notes with "Accessibility Support for Windows 64 Bit" as wording.

Comment 80

[Sylvestre Ledru [:Sylvestre]]

Or not as we are not officially supporting Windows 64 bit yet!