Bug 1299489 - Change nsTArray to use a custom iterator based on index instead of pointers to improve iterator invalidation safety of ranged for loops, r=froydnj
authorMichael Layzell <michael@thelayzells.com>
Wed, 31 Aug 2016 18:42:12 -0400
changeset 325468 8cc548682ae3f4fede10b12f12b8d7874297c9b4
parent 325467 6106512db4baa60f3ef5909d22a661b2228e8052
child 325469 9f61239c41a03f33936e696e487a263336cf78b3
push id24
push usermaklebus@msu.edu
push dateTue, 20 Dec 2016 03:11:33 +0000
reviewersfroydnj
bugs1299489
milestone53.0a1
Bug 1299489 - Change nsTArray to use a custom iterator based on index instead of pointers to improve iterator invalidation safety of ranged for loops, r=froydnj MozReview-Commit-ID: CahPOcRYvES
dom/animation/KeyframeUtils.cpp
layout/generic/nsTextFrame.cpp
layout/style/RuleProcessorCache.cpp
toolkit/components/url-classifier/ChunkSet.cpp
xpcom/glue/nsTArray.h
--- a/dom/animation/KeyframeUtils.cpp
+++ b/dom/animation/KeyframeUtils.cpp
@@ -507,18 +507,18 @@ KeyframeUtils::ApplySpacing(nsTArray<Key
     firstElement.mComputedOffset = firstElement.mOffset.valueOr(0.0);
     // We will fill in the last keyframe's offset below
   } else {
     Keyframe& lastElement = aKeyframes.LastElement();
     lastElement.mComputedOffset = lastElement.mOffset.valueOr(1.0);
   }
 
   // Fill in remaining missing offsets.
-  const Keyframe* const last = aKeyframes.cend() - 1;
-  const RangedPtr<Keyframe> begin(aKeyframes.begin(), aKeyframes.Length());
+  const Keyframe* const last = &aKeyframes.LastElement();
+  const RangedPtr<Keyframe> begin(aKeyframes.Elements(), aKeyframes.Length());
   RangedPtr<Keyframe> keyframeA = begin;
   while (keyframeA != last) {
     // Find keyframe A and keyframe B *between* which we will apply spacing.
     RangedPtr<Keyframe> keyframeB = keyframeA + 1;
     while (keyframeB->mOffset.isNothing() && keyframeB != last) {
       ++keyframeB;
     }
     keyframeB->mComputedOffset = keyframeB->mOffset.valueOr(1.0);
--- a/layout/generic/nsTextFrame.cpp
+++ b/layout/generic/nsTextFrame.cpp
@@ -4996,17 +4996,17 @@ nsDisplayText::nsDisplayText(nsDisplayLi
     GlyphArray* g = mGlyphs.AppendElement();
     std::vector<Glyph> glyphs;
     Color color;
     if (!capture->ContainsOnlyColoredGlyphs(mFont, color, glyphs)) {
       mFont = nullptr;
       mGlyphs.Clear();
     } else {
       g->glyphs().SetLength(glyphs.size());
-      PodCopy(g->glyphs().begin(), glyphs.data(), glyphs.size());
+      PodCopy(g->glyphs().Elements(), glyphs.data(), glyphs.size());
       g->color() = color;
     }
   }
 }
 
 LayerState
 nsDisplayText::GetLayerState(nsDisplayListBuilder* aBuilder,
                              LayerManager* aManager,
--- a/layout/style/RuleProcessorCache.cpp
+++ b/layout/style/RuleProcessorCache.cpp
@@ -138,18 +138,18 @@ RuleProcessorCache::StopTracking(nsCSSRu
     return;
   }
   return gRuleProcessorCache->DoStopTracking(aRuleProcessor);
 }
 
 void
 RuleProcessorCache::DoRemoveSheet(CSSStyleSheet* aSheet)
 {
-  Entry* last = std::remove_if(mEntries.begin(), mEntries.end(),
-                               HasSheet_ThenRemoveRuleProcessors(this, aSheet));
+  auto last = std::remove_if(mEntries.begin(), mEntries.end(),
+                             HasSheet_ThenRemoveRuleProcessors(this, aSheet));
   mEntries.TruncateLength(last - mEntries.begin());
 }
 
 nsCSSRuleProcessor*
 RuleProcessorCache::DoGetRuleProcessor(const nsTArray<CSSStyleSheet*>& aSheets,
                                        nsPresContext* aPresContext)
 {
   for (Entry& e : mEntries) {
--- a/toolkit/components/url-classifier/ChunkSet.cpp
+++ b/toolkit/components/url-classifier/ChunkSet.cpp
@@ -9,25 +9,25 @@ namespace mozilla {
 namespace safebrowsing {
 
 const size_t ChunkSet::IO_BUFFER_SIZE;
 
 nsresult
 ChunkSet::Serialize(nsACString& aChunkStr)
 {
   aChunkStr.Truncate();
-  for (const Range* range = mRanges.begin(); range != mRanges.end(); range++) {
-    if (range != mRanges.begin()) {
+  for (const Range& range : mRanges) {
+    if (&range != &mRanges[0]) {
       aChunkStr.Append(',');
     }
 
-    aChunkStr.AppendInt((int32_t)range->Begin());
-    if (range->Begin() != range->End()) {
+    aChunkStr.AppendInt((int32_t)range.Begin());
+    if (range.Begin() != range.End()) {
       aChunkStr.Append('-');
-      aChunkStr.AppendInt((int32_t)range->End());
+      aChunkStr.AppendInt((int32_t)range.End());
     }
   }
 
   return NS_OK;
 }
 
 nsresult
 ChunkSet::Set(uint32_t aChunk)
@@ -70,20 +70,19 @@ ChunkSet::Has(uint32_t aChunk) const
                         // single-chunk range.
 }
 
 nsresult
 ChunkSet::Merge(const ChunkSet& aOther)
 {
   size_t oldLen = mRanges.Length();
 
-  for (const Range* mergeRange = aOther.mRanges.begin();
-       mergeRange != aOther.mRanges.end(); mergeRange++) {
-    if (!HasSubrange(*mergeRange)) {
-      if (!mRanges.InsertElementSorted(*mergeRange, fallible)) {
+  for (const Range& mergeRange : aOther.mRanges) {
+    if (!HasSubrange(mergeRange)) {
+      if (!mRanges.InsertElementSorted(mergeRange, fallible)) {
         return NS_ERROR_OUT_OF_MEMORY;
       }
     }
   }
 
   if (oldLen < mRanges.Length()) {
     for (size_t i = 1; i < mRanges.Length(); i++) {
       while (mRanges[i - 1].FoldLeft(mRanges[i])) {
@@ -98,44 +97,43 @@ ChunkSet::Merge(const ChunkSet& aOther)
 
   return NS_OK;
 }
 
 uint32_t
 ChunkSet::Length() const
 {
   uint32_t len = 0;
-  for (const Range* range = mRanges.begin(); range != mRanges.end(); range++) {
-    len += range->Length();
+  for (const Range& range : mRanges) {
+    len += range.Length();
   }
 
   return len;
 }
 
 nsresult
 ChunkSet::Remove(const ChunkSet& aOther)
 {
-  for (const Range* removalRange = aOther.mRanges.begin();
-       removalRange != aOther.mRanges.end(); removalRange++) {
+  for (const Range& removalRange : aOther.mRanges) {
 
     if (mRanges.Length() == 0) {
       return NS_OK;
     }
 
-    if (mRanges.LastElement().End() < removalRange->Begin() ||
+    if (mRanges.LastElement().End() < removalRange.Begin() ||
         aOther.mRanges.LastElement().End() < mRanges[0].Begin()) {
       return NS_OK;
     }
 
     size_t intersectionIdx;
     while (BinarySearchIf(mRanges, 0, mRanges.Length(),
-           Range::IntersectionComparator(*removalRange), &intersectionIdx)) {
+           Range::IntersectionComparator(removalRange), &intersectionIdx)) {
 
       ChunkSet remains;
-      nsresult rv = mRanges[intersectionIdx].Remove(*removalRange, remains);
+      nsresult rv = mRanges[intersectionIdx].Remove(removalRange, remains);
 
       if (NS_FAILED(rv)) {
         return rv;
       }
 
       mRanges.RemoveElementAt(intersectionIdx);
       if (!mRanges.InsertElementsAt(intersectionIdx, remains.mRanges,
                                     fallible)) {
@@ -153,18 +151,18 @@ ChunkSet::Clear()
   mRanges.Clear();
 }
 
 nsresult
 ChunkSet::Write(nsIOutputStream* aOut)
 {
   nsTArray<uint32_t> chunks(IO_BUFFER_SIZE);
 
-  for (const Range* range = mRanges.begin(); range != mRanges.end(); range++) {
-    for (uint32_t chunk = range->Begin(); chunk <= range->End(); chunk++) {
+  for (const Range& range : mRanges) {
+    for (uint32_t chunk = range.Begin(); chunk <= range.End(); chunk++) {
       chunks.AppendElement(chunk);
 
       if (chunks.Length() == chunks.Capacity()) {
         nsresult rv = WriteTArray(aOut, chunks);
 
         if (NS_FAILED(rv)) {
           return rv;
         }
@@ -196,36 +194,36 @@ ChunkSet::Read(nsIInputStream* aIn, uint
     nsresult rv = ReadTArray(aIn, &chunks, numToRead);
 
     if (NS_FAILED(rv)) {
       return rv;
     }
 
     aNumElements -= numToRead;
 
-    for (const uint32_t* c = chunks.begin(); c != chunks.end(); c++) {
-      rv = Set(*c);
+    for (uint32_t c : chunks) {
+      rv = Set(c);
 
       if (NS_FAILED(rv)) {
         return rv;
       }
     }
   }
 
   return NS_OK;
 }
 
 bool
 ChunkSet::HasSubrange(const Range& aSubrange) const
 {
-  for (const Range* range = mRanges.begin(); range != mRanges.end(); range++) {
-    if (range->Contains(aSubrange)) {
+  for (const Range& range : mRanges) {
+    if (range.Contains(aSubrange)) {
       return true;
-    } else if (!(aSubrange.Begin() > range->End() ||
-                 range->Begin() > aSubrange.End())) {
+    } else if (!(aSubrange.Begin() > range.End() ||
+                 range.Begin() > aSubrange.End())) {
       // In this case, aSubrange overlaps this range but is not a subrange.
       // because the ChunkSet implementation ensures that there are no
       // overlapping ranges, this means that aSubrange cannot be a subrange of
       // any of the following ranges
       return false;
     }
   }
 
--- a/xpcom/glue/nsTArray.h
+++ b/xpcom/glue/nsTArray.h
@@ -26,16 +26,17 @@
 #include "nscore.h"
 #include "nsQuickSort.h"
 #include "nsDebug.h"
 #include "nsISupportsImpl.h"
 #include "nsRegionFwd.h"
 #include <functional>
 #include <initializer_list>
 #include <new>
+#include <iterator>
 
 namespace JS {
 template<class T>
 class Heap;
 } /* namespace JS */
 
 class nsRegion;
 namespace mozilla {
@@ -350,16 +351,134 @@ struct nsTArray_SafeElementAtHelper<mozi
   {
     if (aIndex < static_cast<const Derived*>(this)->Length()) {
       return static_cast<const Derived*>(this)->ElementAt(aIndex);
     }
     return nullptr;
   }
 };
 
+// We have implemented a custom iterator class for nsTArray rather than using
+// raw pointers into the backing storage to improve the safety of C++11-style
+// range based iteration in the presence of array mutation, or script execution
+// (bug 1299489).
+//
+// Mutating an array which is being iterated is still wrong, and will either
+// cause elements to be missed or firefox to crash, but will not trigger memory
+// safety problems due to the release-mode bounds checking found in ElementAt.
+//
+// This iterator implements the full standard random access iterator spec, and
+// can be treated in may ways as though it is a pointer.
+template<class Element>
+class nsTArrayIterator
+{
+public:
+  typedef nsTArray<typename mozilla::RemoveConst<Element>::Type> array_type;
+  typedef nsTArrayIterator<Element>       iterator_type;
+  typedef typename array_type::index_type index_type;
+  typedef Element                         value_type;
+  typedef ptrdiff_t                       difference_type;
+  typedef value_type*                     pointer;
+  typedef value_type&                     reference;
+  typedef std::random_access_iterator_tag iterator_category;
+
+private:
+  const array_type* mArray;
+  index_type mIndex;
+
+public:
+  nsTArrayIterator() : mArray(nullptr), mIndex(0) {}
+  nsTArrayIterator(const iterator_type& aOther)
+    : mArray(aOther.mArray), mIndex(aOther.mIndex) {}
+  nsTArrayIterator(const array_type& aArray, index_type aIndex)
+    : mArray(&aArray), mIndex(aIndex) {}
+
+  iterator_type& operator=(const iterator_type& aOther) {
+    mArray = aOther.mArray;
+    mIndex = aOther.mIndex;
+    return *this;
+  }
+
+  bool operator==(const iterator_type& aRhs) const {
+    return mIndex == aRhs.mIndex;
+  }
+  bool operator!=(const iterator_type& aRhs) const {
+    return !(*this == aRhs);
+  }
+  bool operator<(const iterator_type& aRhs) const {
+    return mIndex < aRhs.mIndex;
+  }
+  bool operator>(const iterator_type& aRhs) const {
+    return mIndex > aRhs.mIndex;
+  }
+  bool operator<=(const iterator_type& aRhs) const {
+    return mIndex <= aRhs.mIndex;
+  }
+  bool operator>=(const iterator_type& aRhs) const {
+    return mIndex >= aRhs.mIndex;
+  }
+
+  // These operators depend on the release mode bounds checks in
+  // nsTArray::ElementAt for safety.
+  value_type* operator->() const {
+    return const_cast<value_type*>(&(*mArray)[mIndex]);
+  }
+  value_type& operator*() const {
+    return const_cast<value_type&>((*mArray)[mIndex]);
+  }
+
+  iterator_type& operator++() {
+    ++mIndex;
+    return *this;
+  }
+  iterator_type operator++(int) {
+    iterator_type it = *this;
+    ++*this;
+    return it;
+  }
+  iterator_type& operator--() {
+    --mIndex;
+    return *this;
+  }
+  iterator_type operator--(int) {
+    iterator_type it = *this;
+    --*this;
+    return it;
+  }
+
+  iterator_type& operator+=(difference_type aDiff) {
+    mIndex += aDiff;
+    return *this;
+  }
+  iterator_type& operator-=(difference_type aDiff) {
+    mIndex -= aDiff;
+    return *this;
+  }
+
+  iterator_type operator+(difference_type aDiff) const {
+    iterator_type it = *this;
+    it += aDiff;
+    return it;
+  }
+  iterator_type operator-(difference_type aDiff) const {
+    iterator_type it = *this;
+    it -= aDiff;
+    return it;
+  }
+
+  difference_type operator-(const iterator_type& aOther) const {
+    return static_cast<difference_type>(mIndex) -
+      static_cast<difference_type>(aOther.mIndex);
+  }
+
+  value_type& operator[](difference_type aIndex) const {
+    return *this->operator+(aIndex);
+  }
+};
+
 // Servo bindings.
 extern "C" void Gecko_EnsureTArrayCapacity(void* aArray,
                                            size_t aCapacity,
                                            size_t aElementSize);
 extern "C" void Gecko_ClearPODTArray(void* aArray,
                                      size_t aElementSize,
                                      size_t aElementAlign);
 
@@ -852,20 +971,20 @@ public:
   typedef typename nsTArray_CopyChooser<E>::Type     copy_type;
   typedef nsTArray_base<Alloc, copy_type>            base_type;
   typedef typename base_type::size_type              size_type;
   typedef typename base_type::index_type             index_type;
   typedef E                                          elem_type;
   typedef nsTArray_Impl<E, Alloc>                    self_type;
   typedef nsTArrayElementTraits<E>                   elem_traits;
   typedef nsTArray_SafeElementAtHelper<E, self_type> safeelementat_helper_type;
-  typedef elem_type*                                 iterator;
-  typedef const elem_type*                           const_iterator;
-  typedef mozilla::ReverseIterator<elem_type*>       reverse_iterator;
-  typedef mozilla::ReverseIterator<const elem_type*> const_reverse_iterator;
+  typedef nsTArrayIterator<elem_type>                iterator;
+  typedef nsTArrayIterator<const elem_type>          const_iterator;
+  typedef mozilla::ReverseIterator<iterator>         reverse_iterator;
+  typedef mozilla::ReverseIterator<const_iterator>   const_reverse_iterator;
 
   using safeelementat_helper_type::SafeElementAt;
   using base_type::EmptyHdr;
 
   // A special value that is used to indicate an invalid or unknown index
   // into the array.
   static const index_type NoIndex = index_type(-1);
 
@@ -1093,21 +1212,21 @@ public:
 
   // Shorthand for SafeElementAt(length - 1, def)
   const elem_type& SafeLastElement(const elem_type& aDef) const
   {
     return SafeElementAt(Length() - 1, aDef);
   }
 
   // Methods for range-based for loops.
-  iterator begin() { return Elements(); }
-  const_iterator begin() const { return Elements(); }
+  iterator begin() { return iterator(*this, 0); }
+  const_iterator begin() const { return const_iterator(*this, 0); }
   const_iterator cbegin() const { return begin(); }
-  iterator end() { return Elements() + Length(); }
-  const_iterator end() const { return Elements() + Length(); }
+  iterator end() { return iterator(*this, Length()); }
+  const_iterator end() const { return const_iterator(*this, Length()); }
   const_iterator cend() const { return end(); }
 
   // Methods for reverse iterating.
   reverse_iterator rbegin() { return reverse_iterator(end()); }
   const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
   const_reverse_iterator crbegin() const { return rbegin(); }
   reverse_iterator rend() { return reverse_iterator(begin()); }
   const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }