82133 - nsSupportsArray::AppendElements and Equals do evil things

Status: RESOLVED FIXED

(Core :: XPCOM, defect)

Description

[David Baron :dbaron: (⌚️UTC-5, no longer working on Mozilla)]

nsSupportsArray::AppendElements and nsSupportsArray::Equals assume that their
argument (an nsISupportsArray*) is an nsSupportsArray.  This is a bad assumption
that has caused real crashes (bug 80057).  They should probably be rewritten
along the lines of nsSupportsArray::Clone.

Comment 1

[Jeffrey Baker]

Top of the stack in bug 80016 also.  Couldn't reproduce it, though.

Comment 2

[Edward Kandrot]

Attachment: Good catch. I have a patch with I will now get approved. (see attached)

Comment 3

[Scott Collins]

While you're in there, you should simplify code that compares against |0| to
just the expression being compared (and appropriately |!|-ed). You're starting
from crap here. Your changes are good, but they get covered in crap as soon as
you insert them into the file. For instance, there has been much debate about
the growth algorithm for lists. Maybe we want to keep the one exhibited here, I
don't know. I know it's computationally far worse in general than doubling the
list every time. Even if we do keep the growth mechanism as is, we could
replace that horrifying calculating loop with the appropriate constant-time
expression. Plainly the original author was even embarrassed to be writing the
loop. Use something like

  mArraySize += ((count-mArraySize+kGrowArrayBy-1)/kGrowArrayBy) * kGrowArrayBy;

or to split it up

  extraCapacityNeeded = count - mArraySize;
  extraChunksNeeded = (extraCapacityNeeded + kGrowArrayBy - 1) / kGrowArrayBy;
  mArraySize += extraChunksNeeded * kGrowArrayBy;

If |kGrowArray| by is a power of 2, or if we usually have to grow by more than
one chunk, then either form above is preferable to the loop. If we usually grow
by only one chunk, then the loop might be better. Maybe this doesn't even
matter in the face of how bad linear growth is for arrays of items that must be
copied when re-allocated.

Comment 4

[Edward Kandrot]

I know what you mean.  When looking at this code, I could not believe what I was
seeing.  I had thought about rewriting it (and was encourage to do this by
jaggernaut), but decided to just fix the problems defined in this bug for now,
since that was the worst of the problems.  I figured, fix this problem, then
file another bug against nsISupportsArry in general, since there are issues with
const and nonxpcom in the idl and methods (I had to do that horrible cast in
this patch to work around this, but I want to fix the whole problem at some point).

How does that sound, r=,sr= for this patch, then file a bug on the other crap? 
Does this patch fix this crashing bug?

Thanks.

Comment 5

[Scott Collins]

I'd hoist the declaration of the |nsCOMPtr| |other| out of the loop.  Something
I would do that I won't make you do is break the array assignment and increment
into two statements to avoid post-increment, i.e.,

  mArray[mCount] = element;
  ++mCount;

The compiler will produce the same code in either case, but I like to make a
good example.  In that loop, how does |aIndex| get incremented?  I hate that
|aIndex| is a local variable named to look like a parameter.  Perhaps this
should become a |for| loop (and fix |aIndex|):

  PRUint32 i;
  for ( i=0; i < countElements; ++i, ++mCount )
    {
        // Use |GetElementAt| to copy _and_ |AddRef|
      if ( NS_FAILED(aElements->GetElementAt(i, mArray+mCount)) )
        return PR_FALSE;
    }

That's closer to the canonical form.

Comment 6

[Edward Kandrot]

Attachment: Good ideas; Thanks! Here is a new patch incorporating your ideas.

Comment 7

[Edward Kandrot]

Attachment: Sorry, I missed the that loop we hated. Though it is expanding more than I was originally planning (I only wanted to touch what was the minimum needed), this is better than what was there, so I guess it is what should be done. Let me know. Thanks.

Comment 8

[Scott Collins]

I like it.  I would either add or delete a space so that your '- 1' doesn't look
like '-1'.  Add a comment near our enhanced calculation to the effect of

  // growth is linear; consider geometric (e.g., doubling) to avoid the n^2 
  //  (amortized) cost we are paying to copy elements now

After that, sr=scc.  Good work.

Comment 9

[jag (Peter Annema)]

What Scott said about the "-1", for the reason that it becomes unclear whether
you forgot to type a +, or meant the binary operator -, instead of the unary
operator - you're suggesting there.

And:

+  if (NS_FAILED(  aElements->Count( &countElements ) ))

extra space

+  if (0 < countElements) {

I would write this |if (countElements > 0)|, which IMO is more readable, but I
guess that falls under personal style rules, so feel free to keep it as is.

+    for (i=0; i<countElements; ++i, ++mCount) { 

Inconsistent space style with the rest of the code / your modifications.

Comment 10

[jag (Peter Annema)]

But with those changes made, r=jag.

Comment 11

[Edward Kandrot]

I will remove the extra space inside the NS_FAILED, since that was a typo.  All
of the other spacing was intentional.  The (0 < countElements) follows the
convention used in the rest of the file, which is why I did it that way
originally, so I will keep it, unless there is a policy against that ordering,
in which case I will change it.  I consider the for loop to be spaced
consistantly with my rules for spacing, but have changed it to what I believe
you think is consistant with the rest of the file.  I will attach a patch with
the changes (as well as the other comment scc recommended and making one of the
checks for non-null consistant with our rules).

Unless there is a typo, this latest patch I will assume is fine and check it in
in about an hour (since it approved changes).  Let me know if there is a
problem.  Thanks.

Comment 12

[Edward Kandrot]

Attachment: Added spacing changes et al, from r and sr comments.

Comment 13

[Scott Collins]

go for it

Comment 14

[Edward Kandrot]

Fix checked in.

Comment 15

[Daniel Bratell]

Kandrot, did you file a bug on the rest of the mess in the array class?