Closed Bug 1149174 Opened 5 years ago Closed 5 years ago

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

Categories

(Core :: XPCOM, defect)

defect
Not set

Tracking

()

RESOLVED WONTFIX

People

(Reporter: ehsan, Assigned: ehsan)

Details

Attachments

(1 file)

No description provided.
Attachment #8585525 - Flags: review?(nfroyd) → review+
https://hg.mozilla.org/mozilla-central/rev/5527f72c5d34
Assignee: nobody → ehsan
Status: NEW → RESOLVED
Closed: 5 years ago
Flags: in-testsuite+
Resolution: --- → FIXED
Target Milestone: --- → mozilla40
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?
Flags: needinfo?(ehsan)
Hmm, so does this mean that these iterators are non-stable?  That was what I was trying to test here... :(
Flags: needinfo?(ehsan) → needinfo?(nfroyd)
(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"?
Flags: needinfo?(nfroyd) → needinfo?(ehsan)
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?
Flags: needinfo?(ehsan) → needinfo?(nfroyd)
(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?
Flags: needinfo?(nfroyd)
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.
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?
Resolution: FIXED → WONTFIX
Merge of backout:
https://hg.mozilla.org/mozilla-central/rev/cb5da5c1c209
Target Milestone: mozilla40 → ---
FYI: Bug 1147091 - nsTArray needs a stable sort algorithm (MergeSort)
You need to log in before you can comment on or make changes to this bug.