1149174 - Add a test to ensure that XPCOM nsTArray range iterators are stable

Status: RESOLVED WONTFIX

(Core :: XPCOM, defect)

Comment 1

[(no longer active)]

Attachment: Add a test to ensure that XPCOM nsTArray range iterators are stable

Comment 2

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/5527f72c5d34

Comment 3

[Nathan Froyd [:froydnj]]

Actually, hm, I didn't think through this one enough.  What is this test really trying to say?  It's not exactly safe to remove elements from inside range-based for loops with our current iterators for nsTArray.  The test is:

    var.AppendElement(2);          \
    var.AppendElement(3);          \
    var.AppendElement(4);          \
    int count = 0;                 \
    for (const auto& elem : var) { \
      if (elem == 2) {             \
        var.RemoveElementAt(1);    \
      }                            \
      ++count;                     \
    }                              \
    if (count != 3) {              \
      return false;                \
    }                              \

So we do:

first iteration: read 2 from the array, remove the next element, increment count
second iteration: read 4 from the array, increment count
third iteration: read 4 (out of bounds!) from the array, increment count

So I guess we've tested for the right thing, but we're doing bad things on iteration 3, right?

Comment 4

[(no longer active)]

Hmm, so does this mean that these iterators are non-stable?  That was what I was trying to test here... :(

Comment 5

[Nathan Froyd [:froydnj]]

(In reply to :Ehsan Akhgari (not reading bugmail, needinfo? me!) from comment #4)
> Hmm, so does this mean that these iterators are non-stable?  That was what I
> was trying to test here... :(

I guess I should have asked what "stable" meant!

This was partly prompted by a discussion I was having with Aryeh on IRC where I realized that something like:

  for (auto& x : Reversed(array)) {
    ...
    if (condition) {
      array.AppendElement(...);
    }
  }

is going to break rather badly, because our iterators for |array| are pointer based, but AppendElement can resize the array.  And if the array gets resized, then the bounds that the for loop is holding onto are pointing into freed memory...

I guess by "stable" you mean "won't get invalidated by twiddling with parts of the array that we've already iterated over"?

Comment 6

[(no longer active)]

Yes, that's what I meant.  Sorry for the confusion, I thought this is a common phrase, but perhaps not!

So this tells me that I need to revert this patch.  Correct?

Comment 7

[Nathan Froyd [:froydnj]]

(In reply to :Ehsan Akhgari (not reading bugmail, needinfo? me!) from comment #6)
> Yes, that's what I meant.  Sorry for the confusion, I thought this is a
> common phrase, but perhaps not!
> 
> So this tells me that I need to revert this patch.  Correct?

Yeah, I think so.

Maybe we should have a discussion on what the iterators for nsTArray should look like.  I thought pointers would make the most sense (most akin to what <vector> uses, anyway), but I see that vector::iterator is actually implementation defined.  So maybe we should change nsTArray's to something a little less footgun-y, even if the performance is not quite as good?

Comment 8

[Aryeh Gregor (:ayg) (no longer with Mozilla)]

IMO it should work the same as

  for (uint32_t i = 0; i < array.Length(); i++) {

An argument can be made for behaving like

  uint32_t len = array.Length();
  for (uint32_t i = 0; i < len; i++) {

but I'd prefer safety over performance for an abstraction like this, to avoid bugs.

Comment 9

[(no longer active)]

I'm pretty sure that vector::iterator is not stable either (this is an example of a vector class with stable iterators: http://www.boost.org/doc/libs/1_48_0/doc/html/boost/container/stable_vector.html).  Stable iterators are much less performant in general, so it's not obvious to me if that should be the default.

But before we get ahead of ourselves, why don't we check in the iterator in debug builds whether you're accessing out of bounds?

Comment 10

[Pulsebot]

Backout:
https://hg.mozilla.org/integration/mozilla-inbound/rev/cb5da5c1c209

Comment 11

[Ryan VanderMeulen [:RyanVM]]

Merge of backout:
https://hg.mozilla.org/mozilla-central/rev/cb5da5c1c209

Comment 12

[Mats Palmgren (inactive)]

FYI: Bug 1147091 - nsTArray needs a stable sort algorithm (MergeSort)