Make sure range based iteration of Vector<> still receives bounds checking
authoroliver@apple.com <oliver@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 15 Dec 2014 18:04:58 +0000 (18:04 +0000)
committeroliver@apple.com <oliver@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 15 Dec 2014 18:04:58 +0000 (18:04 +0000)
https://bugs.webkit.org/show_bug.cgi?id=138821

Reviewed by Mark Lam.

Source/JavaScriptCore:

Update code to deal with slightly changed iterator semantics.

* bytecode/UnlinkedCodeBlock.cpp:
(JSC::UnlinkedCodeBlock::visitChildren):
* bytecompiler/BytecodeGenerator.cpp:
(JSC::BytecodeGenerator::emitComplexPopScopes):
* dfg/DFGSpeculativeJIT.cpp:
(JSC::DFG::SpeculativeJIT::emitSwitchIntJump):
* ftl/FTLAbbreviations.h:
(JSC::FTL::mdNode):
(JSC::FTL::buildCall):
* llint/LLIntData.cpp:
(JSC::LLInt::Data::performAssertions):
* parser/Parser.h:
(JSC::Scope::Scope):
* runtime/JSArray.cpp:
(JSC::JSArray::setLengthWithArrayStorage):
(JSC::JSArray::sortCompactedVector):
* tools/ProfileTreeNode.h:
(JSC::ProfileTreeNode::dumpInternal):
* yarr/YarrJIT.cpp:
(JSC::Yarr::YarrGenerator::matchCharacterClass):

Source/WebCore:

Update to deal with different iterator type.

* bindings/js/SerializedScriptValue.cpp:
(WebCore::CloneDeserializer::deserializeString):
* editing/TextIterator.cpp:
(WebCore::SearchBuffer::isBadMatch):
* page/mac/ServicesOverlayController.mm:
(WebCore::ServicesOverlayController::buildSelectionHighlight):
* platform/graphics/SegmentedFontData.cpp:
(WebCore::SegmentedFontData::fontDataForCharacter):
(WebCore::SegmentedFontData::containsCharacter):
(WebCore::SegmentedFontData::isLoading):
* platform/graphics/WOFFFileFormat.cpp:
(WebCore::convertWOFFToSfnt):
* platform/graphics/cairo/GradientCairo.cpp:
(WebCore::Gradient::platformGradient):
* platform/image-decoders/gif/GIFImageDecoder.cpp:
(WebCore::GIFImageDecoder::clearFrameBufferCache):
* rendering/RenderBox.cpp:
(WebCore::RenderBox::paintFillLayers):
* rendering/style/GridResolvedPosition.cpp:
(WebCore::firstNamedGridLineBeforePosition):
(WebCore::GridResolvedPosition::resolveRowEndColumnEndNamedGridLinePositionAgainstOppositePosition):
* svg/SVGFontElement.cpp:
(WebCore::kerningForPairOfStringsAndGlyphs):
* svg/SVGPathByteStream.h:
(WebCore::SVGPathByteStream::append):
* xml/XPathNodeSet.h:
(WebCore::XPath::NodeSet::begin):
(WebCore::XPath::NodeSet::end):

Source/WTF:

Add a new IndexedIterator struct to WTF that wraps a
Vector type and index to provide pointer like semantics
while still performing runtime bounds checking, even in
release builds. We store a simple index into the vector
which means that this iterator allows vector resizing
during iteration. If the vector is resized such that the
iterator is out of bounds, then any attempt to dereference
the iterator will crash safely.

For the purpose of retaining semantically equivalent
behaviour, the iterator can be moved to m_index == size()
as that is the standard "end" terminator for these types.
Attempting to dereference at that point will still crash
rather than perform an unsafe memory operation.

By necessity there are many overrides for operator + and - as
we otherwise hit many different type promotion ambiguities when
performing arithmetic with iterators. These ambiguities are also
different for 32- vs. 64-bit, so duplicating the functions
and then forwarding to the core implementations that performed
the bounds checking and mutation seemed like the right call.

* WTF.vcxproj/WTF.vcxproj:
* WTF.vcxproj/WTF.vcxproj.filters:
* WTF.xcodeproj/project.pbxproj:
* wtf/IndexedIterator.h: Added.
(WTF::IndexedIterator::IndexedIterator):
(WTF::IndexedIterator::operator->):
(WTF::IndexedIterator::operator*):
(WTF::IndexedIterator::get):
(WTF::IndexedIterator::operator++):
(WTF::IndexedIterator::operator--):
(WTF::IndexedIterator::operator UnspecifiedBoolType):
(WTF::IndexedIterator::operator-):
(WTF::IndexedIterator::operator=):
(WTF::IndexedIterator::operator==):
(WTF::IndexedIterator::operator!=):
(WTF::IndexedIterator::operator<):
(WTF::IndexedIterator::operator<=):
(WTF::IndexedIterator::operator>):
(WTF::IndexedIterator::operator>=):
(WTF::IndexedIterator::operator const_iterator):
(WTF::IndexedIterator::unsafeGet):
(WTF::getPtr):
(WTF::operator-):
(WTF::operator==):
(WTF::operator!=):
(WTF::operator<=):
(WTF::operator>=):
(WTF::operator<):
(WTF::operator>):
(WTF::IndexedIteratorSelector::makeIterator):
(WTF::IndexedIteratorSelector::makeConstIterator):
* wtf/RefCountedArray.h:
(WTF::RefCountedArray::RefCountedArray):
* wtf/Vector.h:
(WTF::Vector::Vector):
(WTF::Vector::begin):
(WTF::Vector::end):
(WTF::OverflowHandler>::Vector):
(WTF::=):
(WTF::OverflowHandler>::fill):
(WTF::OverflowHandler>::expandCapacity):
(WTF::OverflowHandler>::tryExpandCapacity):
(WTF::OverflowHandler>::resize):
(WTF::OverflowHandler>::shrink):
(WTF::OverflowHandler>::grow):
(WTF::OverflowHandler>::reserveCapacity):
(WTF::OverflowHandler>::tryReserveCapacity):
(WTF::OverflowHandler>::shrinkCapacity):
(WTF::OverflowHandler>::append):
(WTF::OverflowHandler>::tryAppend):
(WTF::OverflowHandler>::appendSlowCase):
(WTF::OverflowHandler>::uncheckedAppend):
(WTF::OverflowHandler>::appendVector):
(WTF::OverflowHandler>::insert):
(WTF::OverflowHandler>::insertVector):
(WTF::OverflowHandler>::remove):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@177284 268f45cc-cd09-0410-ab3c-d52691b4dbfc

30 files changed:
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.cpp
Source/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp
Source/JavaScriptCore/ftl/FTLAbbreviations.h
Source/JavaScriptCore/llint/LLIntData.cpp
Source/JavaScriptCore/parser/Parser.h
Source/JavaScriptCore/runtime/JSArray.cpp
Source/JavaScriptCore/tools/ProfileTreeNode.h
Source/JavaScriptCore/yarr/YarrJIT.cpp
Source/WTF/ChangeLog
Source/WTF/WTF.vcxproj/WTF.vcxproj
Source/WTF/WTF.vcxproj/WTF.vcxproj.filters
Source/WTF/WTF.xcodeproj/project.pbxproj
Source/WTF/wtf/IndexedIterator.h [new file with mode: 0644]
Source/WTF/wtf/RefCountedArray.h
Source/WTF/wtf/Vector.h
Source/WebCore/ChangeLog
Source/WebCore/bindings/js/SerializedScriptValue.cpp
Source/WebCore/editing/TextIterator.cpp
Source/WebCore/page/mac/ServicesOverlayController.mm
Source/WebCore/platform/graphics/SegmentedFontData.cpp
Source/WebCore/platform/graphics/WOFFFileFormat.cpp
Source/WebCore/platform/graphics/cairo/GradientCairo.cpp
Source/WebCore/platform/image-decoders/gif/GIFImageDecoder.cpp
Source/WebCore/rendering/RenderBox.cpp
Source/WebCore/rendering/style/GridResolvedPosition.cpp
Source/WebCore/svg/SVGFontElement.cpp
Source/WebCore/svg/SVGPathByteStream.h
Source/WebCore/xml/XPathNodeSet.h

index c3fff96..7fe5464 100644 (file)
@@ -1,3 +1,33 @@
+2014-12-15  Oliver Hunt  <oliver@apple.com>
+
+        Make sure range based iteration of Vector<> still receives bounds checking
+        https://bugs.webkit.org/show_bug.cgi?id=138821
+
+        Reviewed by Mark Lam.
+
+        Update code to deal with slightly changed iterator semantics.
+
+        * bytecode/UnlinkedCodeBlock.cpp:
+        (JSC::UnlinkedCodeBlock::visitChildren):
+        * bytecompiler/BytecodeGenerator.cpp:
+        (JSC::BytecodeGenerator::emitComplexPopScopes):
+        * dfg/DFGSpeculativeJIT.cpp:
+        (JSC::DFG::SpeculativeJIT::emitSwitchIntJump):
+        * ftl/FTLAbbreviations.h:
+        (JSC::FTL::mdNode):
+        (JSC::FTL::buildCall):
+        * llint/LLIntData.cpp:
+        (JSC::LLInt::Data::performAssertions):
+        * parser/Parser.h:
+        (JSC::Scope::Scope):
+        * runtime/JSArray.cpp:
+        (JSC::JSArray::setLengthWithArrayStorage):
+        (JSC::JSArray::sortCompactedVector):
+        * tools/ProfileTreeNode.h:
+        (JSC::ProfileTreeNode::dumpInternal):
+        * yarr/YarrJIT.cpp:
+        (JSC::Yarr::YarrGenerator::matchCharacterClass):
+
 2014-12-14  Filip Pizlo  <fpizlo@apple.com>
 
         PutLocalSinkingPhase has an invalid assertion about incoming values, because both liveness and deferral analyses are conservative
index 740a244..0717ae8 100644 (file)
@@ -229,9 +229,9 @@ void UnlinkedCodeBlock::visitChildren(JSCell* cell, SlotVisitor& visitor)
     Base::visitChildren(thisObject, visitor);
     visitor.append(&thisObject->m_symbolTable);
     for (FunctionExpressionVector::iterator ptr = thisObject->m_functionDecls.begin(), end = thisObject->m_functionDecls.end(); ptr != end; ++ptr)
-        visitor.append(ptr);
+        visitor.append(WTF::getPtr(ptr));
     for (FunctionExpressionVector::iterator ptr = thisObject->m_functionExprs.begin(), end = thisObject->m_functionExprs.end(); ptr != end; ++ptr)
-        visitor.append(ptr);
+        visitor.append(WTF::getPtr(ptr));
     visitor.appendValues(thisObject->m_constantRegisters.data(), thisObject->m_constantRegisters.size());
     if (thisObject->m_rareData) {
         for (size_t i = 0, end = thisObject->m_rareData->m_regexps.size(); i != end; i++)
index 0b15658..5361f89 100644 (file)
@@ -2283,8 +2283,8 @@ void BytecodeGenerator::emitComplexPopScopes(RegisterID* scope, ControlFlowConte
             int topScopeIndex = -1;
             int bottomScopeIndex = -1;
             if (flipScopes) {
-                topScopeIndex = topScope - m_scopeContextStack.begin();
-                bottomScopeIndex = bottomScope - m_scopeContextStack.begin();
+                topScopeIndex = topScope - m_scopeContextStack.data();
+                bottomScopeIndex = bottomScope - m_scopeContextStack.data();
                 savedScopeContextStack = m_scopeContextStack;
                 m_scopeContextStack.shrink(finallyContext.scopeContextStackSize);
             }
@@ -2328,7 +2328,7 @@ void BytecodeGenerator::emitComplexPopScopes(RegisterID* scope, ControlFlowConte
             if (flipScopes) {
                 m_scopeContextStack = savedScopeContextStack;
                 topScope = &m_scopeContextStack[topScopeIndex]; // assert it's within bounds
-                bottomScope = m_scopeContextStack.begin() + bottomScopeIndex; // don't assert, since it the index might be -1.
+                bottomScope = m_scopeContextStack.data() + bottomScopeIndex; // don't assert, since it the index might be -1.
             }
             if (flipSwitches)
                 m_switchContextStack = savedSwitchContextStack;
index f0724df..3be18ea 100644 (file)
@@ -4910,7 +4910,7 @@ void SpeculativeJIT::emitSwitchIntJump(
     addBranch(
         m_jit.branch32(JITCompiler::AboveOrEqual, value, Imm32(table.ctiOffsets.size())),
         data->fallThrough.block);
-    m_jit.move(TrustedImmPtr(table.ctiOffsets.begin()), scratch);
+    m_jit.move(TrustedImmPtr(table.ctiOffsets.data()), scratch);
     m_jit.loadPtr(JITCompiler::BaseIndex(scratch, value, JITCompiler::timesPtr()), scratch);
     m_jit.jump(scratch);
     data->didUseJumpTable = true;
index fc7cb1b..7b1a1ce 100644 (file)
@@ -120,7 +120,7 @@ static inline LValue mdString(LContext context, const char* string, unsigned len
 static inline LValue mdString(LContext context, const char* string) { return mdString(context, string, std::strlen(string)); }
 static inline LValue mdNode(LContext context, LValue* args, unsigned numArgs) { return llvm->MDNodeInContext(context, args, numArgs); }
 template<typename VectorType>
-static inline LValue mdNode(LContext context, const VectorType& vector) { return mdNode(context, const_cast<LValue*>(vector.begin()), vector.size()); }
+static inline LValue mdNode(LContext context, const VectorType& vector) { return mdNode(context, const_cast<LValue*>(vector.data()), vector.size()); }
 static inline LValue mdNode(LContext context) { return mdNode(context, 0, 0); }
 static inline LValue mdNode(LContext context, LValue arg1) { return mdNode(context, &arg1, 1); }
 static inline LValue mdNode(LContext context, LValue arg1, LValue arg2)
@@ -288,7 +288,7 @@ static inline LValue buildCall(LBuilder builder, LValue function, const LValue*
 template<typename VectorType>
 inline LValue buildCall(LBuilder builder, LValue function, const VectorType& vector)
 {
-    return buildCall(builder, function, vector.begin(), vector.size());
+    return buildCall(builder, function, vector.data(), vector.size());
 }
 static inline LValue buildCall(LBuilder builder, LValue function)
 {
index 6919aea..44afca4 100644 (file)
@@ -161,7 +161,7 @@ void Data::performAssertions(VM& vm)
     Vector<int> testVector;
     testVector.resize(42);
     ASSERT(bitwise_cast<uint32_t*>(&testVector)[sizeof(void*)/sizeof(uint32_t) + 1] == 42);
-    ASSERT(bitwise_cast<int**>(&testVector)[0] == testVector.begin());
+    ASSERT(bitwise_cast<int**>(&testVector)[0] == testVector.data());
 #endif
 
     ASSERT(StringImpl::s_hashFlag8BitBuffer == 32);
index 764e3d3..936c8bc 100644 (file)
@@ -130,10 +130,8 @@ struct Scope {
         if (rhs.m_labels) {
             m_labels = std::make_unique<LabelStack>();
 
-            typedef LabelStack::const_iterator iterator;
-            iterator end = rhs.m_labels->end();
-            for (iterator it = rhs.m_labels->begin(); it != end; ++it)
-                m_labels->append(ScopeLabelInfo(it->m_ident, it->m_isLoop));
+            for (auto label : *rhs.m_labels)
+                m_labels->append(ScopeLabelInfo(label.m_ident, label.m_isLoop));
         }
     }
 
index 517721e..0f9eacc 100644 (file)
@@ -351,7 +351,7 @@ bool JSArray::setLengthWithArrayStorage(ExecState* exec, unsigned newLength, boo
             // properties, so we have to perform deletion with caution, if not we can
             // delete values in any order.
             if (map->sparseMode()) {
-                qsort(keys.begin(), keys.size(), sizeof(unsigned), compareKeysForQSort);
+                qsort(keys.data(), keys.size(), sizeof(unsigned), compareKeysForQSort);
                 unsigned i = keys.size();
                 while (i) {
                     unsigned index = keys[--i];
@@ -1190,13 +1190,13 @@ void JSArray::sortCompactedVector(ExecState* exec, ContiguousData<StorageType> d
         
 #if HAVE(MERGESORT)
     if (isSortingPrimitiveValues)
-        qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
+        qsort(values.data(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
     else
-        mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
+        mergesort(values.data(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
 #else
     // FIXME: The qsort library function is likely to not be a stable sort.
     // ECMAScript-262 does not specify a stable sort, but in practice, browsers perform a stable sort.
-    qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
+    qsort(values.data(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
 #endif
     
     // If the toString function changed the length of the array or vector storage,
index 88d57f3..dd3c121 100644 (file)
@@ -86,7 +86,7 @@ private:
         Vector<MapEntry*> entries;
         for (Map::iterator it = m_children->begin(); it != m_children->end(); ++it)
             entries.append(&*it);
-        qsort(entries.begin(), entries.size(), sizeof(MapEntry*), compareEntries);
+        qsort(entries.data(), entries.size(), sizeof(MapEntry*), compareEntries);
 
         // Iterate over the children in sample-frequency order.
         for (size_t e = 0; e < entries.size(); ++e) {
index e3a3a93..d268e59 100644 (file)
@@ -223,7 +223,7 @@ class YarrGenerator : private MacroAssembler {
         if (charClass->m_ranges.size()) {
             unsigned matchIndex = 0;
             JumpList failures;
-            matchCharacterClassRange(character, failures, matchDest, charClass->m_ranges.begin(), charClass->m_ranges.size(), &matchIndex, charClass->m_matches.begin(), charClass->m_matches.size());
+            matchCharacterClassRange(character, failures, matchDest, charClass->m_ranges.data(), charClass->m_ranges.size(), &matchIndex, charClass->m_matches.data(), charClass->m_matches.size());
             while (matchIndex < charClass->m_matches.size())
                 matchDest.append(branch32(Equal, character, Imm32((unsigned short)charClass->m_matches[matchIndex++])));
 
index 18d2a5c..689366a 100644 (file)
@@ -1,3 +1,89 @@
+2014-12-15  Oliver Hunt  <oliver@apple.com>
+
+        Make sure range based iteration of Vector<> still receives bounds checking
+        https://bugs.webkit.org/show_bug.cgi?id=138821
+
+        Reviewed by Mark Lam.
+
+        Add a new IndexedIterator struct to WTF that wraps a
+        Vector type and index to provide pointer like semantics
+        while still performing runtime bounds checking, even in
+        release builds. We store a simple index into the vector
+        which means that this iterator allows vector resizing
+        during iteration. If the vector is resized such that the
+        iterator is out of bounds, then any attempt to dereference
+        the iterator will crash safely.
+
+        For the purpose of retaining semantically equivalent
+        behaviour, the iterator can be moved to m_index == size()
+        as that is the standard "end" terminator for these types.
+        Attempting to dereference at that point will still crash
+        rather than perform an unsafe memory operation.
+
+        By necessity there are many overrides for operator + and - as
+        we otherwise hit many different type promotion ambiguities when
+        performing arithmetic with iterators. These ambiguities are also
+        different for 32- vs. 64-bit, so duplicating the functions
+        and then forwarding to the core implementations that performed
+        the bounds checking and mutation seemed like the right call.
+
+        * WTF.vcxproj/WTF.vcxproj:
+        * WTF.vcxproj/WTF.vcxproj.filters:
+        * WTF.xcodeproj/project.pbxproj:
+        * wtf/IndexedIterator.h: Added.
+        (WTF::IndexedIterator::IndexedIterator):
+        (WTF::IndexedIterator::operator->):
+        (WTF::IndexedIterator::operator*):
+        (WTF::IndexedIterator::get):
+        (WTF::IndexedIterator::operator++):
+        (WTF::IndexedIterator::operator--):
+        (WTF::IndexedIterator::operator UnspecifiedBoolType):
+        (WTF::IndexedIterator::operator-):
+        (WTF::IndexedIterator::operator=):
+        (WTF::IndexedIterator::operator==):
+        (WTF::IndexedIterator::operator!=):
+        (WTF::IndexedIterator::operator<):
+        (WTF::IndexedIterator::operator<=):
+        (WTF::IndexedIterator::operator>):
+        (WTF::IndexedIterator::operator>=):
+        (WTF::IndexedIterator::operator const_iterator):
+        (WTF::IndexedIterator::unsafeGet):
+        (WTF::getPtr):
+        (WTF::operator-):
+        (WTF::operator==):
+        (WTF::operator!=):
+        (WTF::operator<=):
+        (WTF::operator>=):
+        (WTF::operator<):
+        (WTF::operator>):
+        (WTF::IndexedIteratorSelector::makeIterator):
+        (WTF::IndexedIteratorSelector::makeConstIterator):
+        * wtf/RefCountedArray.h:
+        (WTF::RefCountedArray::RefCountedArray):
+        * wtf/Vector.h:
+        (WTF::Vector::Vector):
+        (WTF::Vector::begin):
+        (WTF::Vector::end):
+        (WTF::OverflowHandler>::Vector):
+        (WTF::=):
+        (WTF::OverflowHandler>::fill):
+        (WTF::OverflowHandler>::expandCapacity):
+        (WTF::OverflowHandler>::tryExpandCapacity):
+        (WTF::OverflowHandler>::resize):
+        (WTF::OverflowHandler>::shrink):
+        (WTF::OverflowHandler>::grow):
+        (WTF::OverflowHandler>::reserveCapacity):
+        (WTF::OverflowHandler>::tryReserveCapacity):
+        (WTF::OverflowHandler>::shrinkCapacity):
+        (WTF::OverflowHandler>::append):
+        (WTF::OverflowHandler>::tryAppend):
+        (WTF::OverflowHandler>::appendSlowCase):
+        (WTF::OverflowHandler>::uncheckedAppend):
+        (WTF::OverflowHandler>::appendVector):
+        (WTF::OverflowHandler>::insert):
+        (WTF::OverflowHandler>::insertVector):
+        (WTF::OverflowHandler>::remove):
+
 2014-12-14  Andreas Kling  <akling@apple.com>
 
         Minor follow-up tweaks suggested by Darin on bug 139587.
index ec73308..e757a5d 100644 (file)
     <ClInclude Include="..\wtf\HashTable.h" />
     <ClInclude Include="..\wtf\HashTraits.h" />
     <ClInclude Include="..\wtf\HexNumber.h" />
+    <ClInclude Include="..\wtf\IndexedIterator.h" />
     <ClInclude Include="..\wtf\IteratorAdaptors.h" />
     <ClInclude Include="..\wtf\IteratorRange.h" />
     <ClInclude Include="..\wtf\ListHashSet.h" />
index a14f3e0..b4db550 100644 (file)
     <ClInclude Include="..\wtf\HexNumber.h">
       <Filter>wtf</Filter>
     </ClInclude>
+    <ClInclude Include="..\wtf\IndexedIterator.h">
+      <Filter>wtf</Filter>
+    </ClInclude>
     <ClInclude Include="..\wtf\IteratorAdaptors.h">
       <Filter>wtf</Filter>
     </ClInclude>
index ea7b323..4a45b6f 100644 (file)
                A748745217A0BDAE00FA04CB /* SixCharacterHash.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A748744F17A0BDAE00FA04CB /* SixCharacterHash.cpp */; };
                A748745317A0BDAE00FA04CB /* SixCharacterHash.h in Headers */ = {isa = PBXBuildFile; fileRef = A748745017A0BDAE00FA04CB /* SixCharacterHash.h */; };
                A748745417A0BDAE00FA04CB /* StringHashDumpContext.h in Headers */ = {isa = PBXBuildFile; fileRef = A748745117A0BDAE00FA04CB /* StringHashDumpContext.h */; };
+               A7DC2F041A09A22D0072F4E3 /* IndexedIterator.h in Headers */ = {isa = PBXBuildFile; fileRef = A7DC2F031A099DE30072F4E3 /* IndexedIterator.h */; };
                A7E643C617C5423B003BB16B /* Compression.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A7E643C417C5423B003BB16B /* Compression.cpp */; };
                A7E643C717C5423B003BB16B /* Compression.h in Headers */ = {isa = PBXBuildFile; fileRef = A7E643C517C5423B003BB16B /* Compression.h */; };
                A876DBD8151816E500DADB95 /* Platform.h in Headers */ = {isa = PBXBuildFile; fileRef = A876DBD7151816E500DADB95 /* Platform.h */; };
                A748744F17A0BDAE00FA04CB /* SixCharacterHash.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SixCharacterHash.cpp; sourceTree = "<group>"; };
                A748745017A0BDAE00FA04CB /* SixCharacterHash.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SixCharacterHash.h; sourceTree = "<group>"; };
                A748745117A0BDAE00FA04CB /* StringHashDumpContext.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StringHashDumpContext.h; sourceTree = "<group>"; };
+               A7DC2F031A099DE30072F4E3 /* IndexedIterator.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = IndexedIterator.h; sourceTree = "<group>"; };
                A7E643C417C5423B003BB16B /* Compression.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Compression.cpp; sourceTree = "<group>"; };
                A7E643C517C5423B003BB16B /* Compression.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Compression.h; sourceTree = "<group>"; };
                A876DBD7151816E500DADB95 /* Platform.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Platform.h; sourceTree = "<group>"; };
                                974CFC8D16A4F327006D5404 /* WeakPtr.h */,
                                A8A4737A151A825B004123FF /* WTFThreadData.cpp */,
                                A8A4737B151A825B004123FF /* WTFThreadData.h */,
+                               A7DC2F031A099DE30072F4E3 /* IndexedIterator.h */,
                        );
                        path = wtf;
                        sourceTree = "<group>";
                                A8A473AD151A825B004123FF /* cached-powers.h in Headers */,
                                A8A4745E151A825B004123FF /* CharacterNames.h in Headers */,
                                A8A47394151A825B004123FF /* CheckedArithmetic.h in Headers */,
+                               A7DC2F041A09A22D0072F4E3 /* IndexedIterator.h in Headers */,
                                A8A47395151A825B004123FF /* CheckedBoolean.h in Headers */,
                                A8A4745F151A825B004123FF /* Collator.h in Headers */,
                                0FC4EDE61696149600F65041 /* CommaPrinter.h in Headers */,
diff --git a/Source/WTF/wtf/IndexedIterator.h b/Source/WTF/wtf/IndexedIterator.h
new file mode 100644 (file)
index 0000000..412244c
--- /dev/null
@@ -0,0 +1,358 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef WTF_IndexedIterator_h
+#define WTF_IndexedIterator_h
+
+namespace WTF {
+
+#define INDEXED_ITERATOR_OVERFLOW(check) do {\
+    if (!(check))\
+        OverflowHandler::overflowed();\
+} while (0)
+
+template <typename VectorType, typename T, typename OverflowHandler = CrashOnOverflow> struct IndexedIterator {
+    typedef struct IndexedIterator<const VectorType, const T, OverflowHandler> const_iterator;
+
+    typedef T ValueType;
+    typedef ptrdiff_t difference_type;
+    typedef ValueType value_type;
+    typedef ValueType* pointer;
+    typedef ValueType& reference;
+    typedef std::bidirectional_iterator_tag iterator_category;
+
+    IndexedIterator()
+        : m_vector(nullptr)
+        , m_position(0)
+    {
+    }
+
+    IndexedIterator(VectorType& vector, ValueType* position)
+        : m_vector(&vector)
+        , m_position(position - vector.data())
+    {
+    }
+
+    IndexedIterator(const IndexedIterator& other)
+        : m_vector(other.m_vector)
+        , m_position(other.m_position)
+    {
+    }
+
+    ValueType* operator->() const { return &m_vector->at(m_position); }
+    ValueType& operator*() const { return m_vector->at(m_position); }
+    ValueType* get() const
+    {
+        if (!m_vector)
+            return nullptr;
+        INDEXED_ITERATOR_OVERFLOW(m_position <= m_vector->size());
+        return m_vector->data() + m_position;
+    }
+
+    IndexedIterator& operator++()
+    {
+        m_position++;
+        return *this;
+    }
+
+    IndexedIterator operator++(int)
+    {
+        IndexedIterator result(*this);
+        m_position++;
+        return result;
+    }
+
+    IndexedIterator& operator--()
+    {
+        m_position--;
+        return *this;
+    }
+
+    IndexedIterator operator--(int)
+    {
+        IndexedIterator result(*this);
+        m_position--;
+        return result;
+    }
+
+    // This conversion operator allows implicit conversion to bool but not to other integer types.
+    typedef size_t (IndexedIterator::*UnspecifiedBoolType);
+    operator UnspecifiedBoolType() const { return m_vector ? &IndexedIterator::m_position : nullptr; }
+
+#if __SIZEOF_SIZE_T__ != __SIZEOF_INT__ || PLATFORM(COCOA)
+#define _UNSIGNED_If_DIFFERENT(macro) macro(unsigned)
+#else
+#define _UNSIGNED_If_DIFFERENT(macro)
+#endif
+
+#define FOR_EACH_INTEGER_TYPE(macro) \
+    macro(size_t) \
+    macro(int32_t) \
+    macro(long) \
+    macro(long long) \
+    macro(unsigned long long) \
+    _UNSIGNED_If_DIFFERENT(macro)
+
+#define MODIFIER_OPS(type) \
+    IndexedIterator& operator+=(type increment) \
+    { \
+        m_position += increment; \
+        return *this; \
+    } \
+\
+    IndexedIterator& operator-=(type decrement) \
+    { \
+        m_position -= decrement; \
+        return *this; \
+    }
+
+    FOR_EACH_INTEGER_TYPE(MODIFIER_OPS)
+
+#undef MODIFIER_OPS
+
+#define ARITHMETIC_OPS(type) \
+    IndexedIterator operator+(type increment) const \
+    { \
+        IndexedIterator result(*this); \
+        result.m_position += increment; \
+        return result; \
+    } \
+\
+    IndexedIterator operator-(type decrement) const \
+    { \
+        IndexedIterator result(*this); \
+        result.m_position -= decrement; \
+        return result; \
+    }
+
+
+    FOR_EACH_INTEGER_TYPE(ARITHMETIC_OPS)
+
+#undef ARITHMETIC_OPS
+
+    ptrdiff_t operator-(const const_iterator& right) const
+    {
+        return m_position - right.m_position;
+    }
+
+    ptrdiff_t operator-(const ValueType* right) const
+    {
+        return get() - right;
+    }
+
+    void operator=(const IndexedIterator& other)
+    {
+        m_vector = other.m_vector;
+        m_position = other.m_position;
+    }
+
+    bool operator==(const const_iterator& other) const
+    {
+        return unsafeGet() == other.unsafeGet();
+    }
+
+    bool operator!=(const const_iterator& other) const
+    {
+        return unsafeGet() != other.unsafeGet();
+    }
+
+    bool operator==(const ValueType* other) const
+    {
+        return unsafeGet() == other;
+    }
+
+    bool operator!=(const ValueType* other) const
+    {
+        return unsafeGet() != other;
+    }
+
+    bool operator<(const ValueType* other) const
+    {
+        return unsafeGet() < other;
+    }
+
+    bool operator<=(const ValueType* other) const
+    {
+        return unsafeGet() <= other;
+    }
+
+    bool operator<(const const_iterator& other) const
+    {
+        return unsafeGet() < other.unsafeGet();
+    }
+
+    bool operator<=(const const_iterator& other) const
+    {
+        return unsafeGet() <= other.unsafeGet();
+    }
+
+    bool operator>(const IndexedIterator& other) const
+    {
+        return unsafeGet() > other.unsafeGet();
+    }
+
+    bool operator>=(const const_iterator& other) const
+    {
+        return unsafeGet() >= other.unsafeGet();
+    }
+
+    bool operator>(const ValueType* other) const
+    {
+        return unsafeGet() > other;
+    }
+
+    bool operator>=(const ValueType* other) const
+    {
+        return unsafeGet() >= other;
+    }
+
+    operator const_iterator() const
+    {
+        const_iterator result;
+        result.m_vector = m_vector;
+        result.m_position = m_position;
+        return result;
+    }
+
+    VectorType* m_vector;
+    size_t m_position;
+
+    ValueType* unsafeGet() const
+    {
+        if (!m_vector)
+            return nullptr;
+        return get();
+    }
+};
+
+template <typename T, typename ValueType, typename OverflowHandler>
+inline typename IndexedIterator<T, ValueType, OverflowHandler>::ValueType* getPtr(IndexedIterator<T, ValueType, OverflowHandler> p)
+{
+    return p.get();
+}
+
+template <typename T, typename ValueType, typename OverflowHandler>
+inline ptrdiff_t operator-(const ValueType* left, const IndexedIterator<T, ValueType, OverflowHandler>& right)
+{
+    return left - right.get();
+}
+
+template <typename T, typename ValueType, typename OverflowHandler>
+inline ptrdiff_t operator-(ValueType* left, const IndexedIterator<T, ValueType, OverflowHandler>& right)
+{
+    return left - right.get();
+}
+
+template <typename T, typename ValueType, typename OverflowHandler>
+inline ptrdiff_t operator-(const ValueType* left, const IndexedIterator<const T, const ValueType, OverflowHandler>& right)
+{
+    return left - right.get();
+}
+
+template <typename T, typename ValueType, typename OverflowHandler>
+inline bool operator==(ValueType* left, const IndexedIterator<T, ValueType, OverflowHandler>& right)
+{
+    return right == left;
+}
+
+template <typename T, typename ValueType, typename OverflowHandler>
+inline bool operator==(const ValueType* left, const IndexedIterator<T, ValueType, OverflowHandler>& right)
+{
+    return right == left;
+}
+
+template <typename T, typename ValueType, typename OverflowHandler>
+inline bool operator!=(ValueType* left, const IndexedIterator<T, ValueType, OverflowHandler>& right)
+{
+    return right != left;
+}
+
+template <typename T, typename ValueType, typename OverflowHandler>
+inline bool operator!=(const ValueType* left, const IndexedIterator<T, ValueType, OverflowHandler>& right)
+{
+    return right != left;
+}
+
+template <typename T, typename ValueType, typename OverflowHandler>
+inline bool operator<=(ValueType* left, const IndexedIterator<T, ValueType, OverflowHandler>& right)
+{
+    return right >= left;
+}
+
+template <typename T, typename ValueType, typename OverflowHandler>
+inline bool operator<=(const ValueType* left, const IndexedIterator<T, ValueType, OverflowHandler>& right)
+{
+    return right >= left;
+}
+
+template <typename T, typename ValueType, typename OverflowHandler>
+inline bool operator>=(ValueType* left, const IndexedIterator<T, ValueType, OverflowHandler>& right)
+{
+    return right <= left;
+}
+
+template <typename T, typename ValueType, typename OverflowHandler>
+inline bool operator>=(const ValueType* left, const IndexedIterator<T, ValueType, OverflowHandler>& right)
+{
+    return right <= left;
+}
+
+template <typename T, typename ValueType, typename OverflowHandler>
+inline bool operator<(ValueType* left, const IndexedIterator<T, ValueType, OverflowHandler>& right)
+{
+    return right > left;
+}
+
+template <typename T, typename ValueType, typename OverflowHandler>
+inline bool operator<(const ValueType* left, const IndexedIterator<T, ValueType, OverflowHandler>& right)
+{
+    return right > left;
+}
+
+template <typename T, typename ValueType, typename OverflowHandler>
+inline bool operator>(ValueType* left, const IndexedIterator<T, ValueType, OverflowHandler>& right)
+{
+    return right < left;
+}
+
+template <typename T, typename ValueType, typename OverflowHandler>
+inline bool operator>(const ValueType* left, const IndexedIterator<T, ValueType, OverflowHandler>& right)
+{
+    return right < left;
+}
+
+template <typename VectorType, typename OverflowHandler> struct IndexedIteratorSelector {
+    typedef typename VectorType::ValueType ValueType;
+    typedef IndexedIterator<VectorType, ValueType, OverflowHandler> iterator;
+    typedef typename iterator::const_iterator const_iterator;
+    static iterator makeIterator(VectorType& vector, ValueType* p) { return iterator(vector, p); }
+    static const_iterator makeConstIterator(const VectorType& vector, const ValueType* p) { return const_iterator(vector, p); }
+};
+
+#undef INDEXED_ITERATOR_OVERFLOW
+
+}
+
+#endif
index a55d7ae..811e9ff 100644 (file)
@@ -83,7 +83,7 @@ public:
         Header::fromPayload(m_data)->refCount = 1;
         Header::fromPayload(m_data)->length = other.size();
         ASSERT(Header::fromPayload(m_data)->length == other.size());
-        VectorTypeOperations<T>::uninitializedCopy(other.begin(), other.end(), m_data);
+        VectorTypeOperations<T>::uninitializedCopy(getPtr(other.begin()), getPtr(other.end()), m_data);
     }
     
     RefCountedArray& operator=(const RefCountedArray& other)
index f31329e..5903fe4 100644 (file)
@@ -28,6 +28,8 @@
 #include <utility>
 #include <wtf/CheckedArithmetic.h>
 #include <wtf/FastMalloc.h>
+#include <wtf/GetPtr.h>
+#include <wtf/IndexedIterator.h>
 #include <wtf/MallocPtr.h>
 #include <wtf/Noncopyable.h>
 #include <wtf/StdLibExtras.h>
@@ -553,14 +555,17 @@ template<typename T, size_t inlineCapacity = 0, typename OverflowHandler = Crash
 class Vector : private VectorBuffer<T, inlineCapacity> {
     WTF_MAKE_FAST_ALLOCATED;
 private:
+
     typedef VectorBuffer<T, inlineCapacity> Base;
     typedef VectorTypeOperations<T> TypeOperations;
+    typedef IndexedIteratorSelector<Vector, OverflowHandler> IteratorSelector;
 
 public:
     typedef T ValueType;
 
-    typedef T* iterator;
-    typedef const T* const_iterator;
+    typedef typename IteratorSelector::iterator iterator;
+    typedef typename IteratorSelector::const_iterator const_iterator;
+
     typedef std::reverse_iterator<iterator> reverse_iterator;
     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 
@@ -573,14 +578,14 @@ public:
         : Base(size, size)
     {
         if (begin())
-            TypeOperations::initialize(begin(), end());
+            TypeOperations::initialize(getPtr(begin()), getPtr(end()));
     }
 
     Vector(size_t size, const T& val)
         : Base(size, size)
     {
         if (begin())
-            TypeOperations::uninitializedFill(begin(), end(), val);
+            TypeOperations::uninitializedFill(getPtr(begin()), getPtr(end()), val);
     }
 
     Vector(std::initializer_list<T> initializerList)
@@ -644,10 +649,10 @@ public:
     const T* data() const { return Base::buffer(); }
     static ptrdiff_t dataMemoryOffset() { return Base::bufferMemoryOffset(); }
 
-    iterator begin() { return data(); }
-    iterator end() { return begin() + m_size; }
-    const_iterator begin() const { return data(); }
-    const_iterator end() const { return begin() + m_size; }
+    iterator begin() { return IteratorSelector::makeIterator(*this, data()); }
+    iterator end() { return begin() + size(); }
+    const_iterator begin() const { return IteratorSelector::makeConstIterator(*this, data()); }
+    const_iterator end() const { return begin() + size(); }
 
     reverse_iterator rbegin() { return reverse_iterator(end()); }
     reverse_iterator rend() { return reverse_iterator(begin()); }
@@ -682,6 +687,7 @@ public:
 
     void clear() { shrinkCapacity(0); }
 
+    void append(const_iterator, size_t);
     template<typename U> void append(const U*, size_t);
     template<typename U> void append(U&&);
     template<typename U> void uncheckedAppend(U&& val);
@@ -745,7 +751,7 @@ Vector<T, inlineCapacity, OverflowHandler>::Vector(const Vector& other)
     : Base(other.capacity(), other.size())
 {
     if (begin())
-        TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
+        TypeOperations::uninitializedCopy(getPtr(other.begin()), getPtr(other.end()), getPtr(begin()));
 }
 
 template<typename T, size_t inlineCapacity, typename OverflowHandler>
@@ -754,7 +760,7 @@ Vector<T, inlineCapacity, OverflowHandler>::Vector(const Vector<T, otherCapacity
     : Base(other.capacity(), other.size())
 {
     if (begin())
-        TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
+        TypeOperations::uninitializedCopy(getPtr(other.begin()), getPtr(other.end()), getPtr(begin()));
 }
 
 template<typename T, size_t inlineCapacity, typename OverflowHandler>
@@ -771,8 +777,8 @@ Vector<T, inlineCapacity, OverflowHandler>& Vector<T, inlineCapacity, OverflowHa
         ASSERT(begin());
     }
     
-    std::copy(other.begin(), other.begin() + size(), begin());
-    TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
+    std::copy(getPtr(other.begin()), getPtr(other.begin() + size()), getPtr(begin()));
+    TypeOperations::uninitializedCopy(getPtr(other.begin() + size()), getPtr(other.end()), getPtr(end()));
     m_size = other.size();
 
     return *this;
@@ -796,9 +802,9 @@ Vector<T, inlineCapacity, OverflowHandler>& Vector<T, inlineCapacity, OverflowHa
         reserveCapacity(other.size());
         ASSERT(begin());
     }
-    
-    std::copy(other.begin(), other.begin() + size(), begin());
-    TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
+
+    std::copy(getPtr(other.begin()), getPtr(other.begin() + size()), getPtr(begin()));
+    TypeOperations::uninitializedCopy(getPtr(other.begin() + size()), getPtr(other.end()), getPtr(end()));
     m_size = other.size();
 
     return *this;
@@ -858,8 +864,8 @@ void Vector<T, inlineCapacity, OverflowHandler>::fill(const T& val, size_t newSi
         ASSERT(begin());
     }
     
-    std::fill(begin(), end(), val);
-    TypeOperations::uninitializedFill(end(), begin() + newSize, val);
+    std::fill(getPtr(begin()), getPtr(end()), val);
+    TypeOperations::uninitializedFill(getPtr(end()), getPtr(begin()) + newSize, val);
     m_size = newSize;
 }
 
@@ -880,13 +886,13 @@ void Vector<T, inlineCapacity, OverflowHandler>::expandCapacity(size_t newMinCap
 template<typename T, size_t inlineCapacity, typename OverflowHandler>
 T* Vector<T, inlineCapacity, OverflowHandler>::expandCapacity(size_t newMinCapacity, T* ptr)
 {
-    if (ptr < begin() || ptr >= end()) {
+    if (ptr < getPtr(begin()) || ptr >= getPtr(end())) {
         expandCapacity(newMinCapacity);
         return ptr;
     }
     size_t index = ptr - begin();
     expandCapacity(newMinCapacity);
-    return begin() + index;
+    return getPtr(begin() + index);
 }
 
 template<typename T, size_t inlineCapacity, typename OverflowHandler>
@@ -898,15 +904,15 @@ bool Vector<T, inlineCapacity, OverflowHandler>::tryExpandCapacity(size_t newMin
 template<typename T, size_t inlineCapacity, typename OverflowHandler>
 const T* Vector<T, inlineCapacity, OverflowHandler>::tryExpandCapacity(size_t newMinCapacity, const T* ptr)
 {
-    if (ptr < begin() || ptr >= end()) {
+    if (ptr < getPtr(begin()) || ptr >= getPtr(end())) {
         if (!tryExpandCapacity(newMinCapacity))
             return 0;
         return ptr;
     }
-    size_t index = ptr - begin();
+    size_t index = (ptr - begin());
     if (!tryExpandCapacity(newMinCapacity))
         return 0;
-    return begin() + index;
+    return getPtr(begin()) + index;
 }
 
 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
@@ -920,12 +926,12 @@ template<typename T, size_t inlineCapacity, typename OverflowHandler>
 inline void Vector<T, inlineCapacity, OverflowHandler>::resize(size_t size)
 {
     if (size <= m_size)
-        TypeOperations::destruct(begin() + size, end());
+        TypeOperations::destruct(getPtr(begin()) + size, getPtr(end()));
     else {
         if (size > capacity())
             expandCapacity(size);
         if (begin())
-            TypeOperations::initialize(end(), begin() + size);
+            TypeOperations::initialize(getPtr(end()), getPtr(begin()) + size);
     }
     
     m_size = size;
@@ -942,7 +948,7 @@ template<typename T, size_t inlineCapacity, typename OverflowHandler>
 void Vector<T, inlineCapacity, OverflowHandler>::shrink(size_t size)
 {
     ASSERT(size <= m_size);
-    TypeOperations::destruct(begin() + size, end());
+    TypeOperations::destruct(getPtr(begin()) + size, getPtr(end()));
     m_size = size;
 }
 
@@ -953,7 +959,7 @@ void Vector<T, inlineCapacity, OverflowHandler>::grow(size_t size)
     if (size > capacity())
         expandCapacity(size);
     if (begin())
-        TypeOperations::initialize(end(), begin() + size);
+        TypeOperations::initialize(getPtr(end()), getPtr(begin()) + size);
     m_size = size;
 }
 
@@ -962,11 +968,11 @@ void Vector<T, inlineCapacity, OverflowHandler>::reserveCapacity(size_t newCapac
 {
     if (newCapacity <= capacity())
         return;
-    T* oldBuffer = begin();
-    T* oldEnd = end();
+    T* oldBuffer = getPtr(begin());
+    T* oldEnd = getPtr(end());
     Base::allocateBuffer(newCapacity);
     ASSERT(begin());
-    TypeOperations::move(oldBuffer, oldEnd, begin());
+    TypeOperations::move(oldBuffer, oldEnd, getPtr(begin()));
     Base::deallocateBuffer(oldBuffer);
 }
 
@@ -975,12 +981,12 @@ bool Vector<T, inlineCapacity, OverflowHandler>::tryReserveCapacity(size_t newCa
 {
     if (newCapacity <= capacity())
         return true;
-    T* oldBuffer = begin();
-    T* oldEnd = end();
+    T* oldBuffer = getPtr(begin());
+    T* oldEnd = getPtr(end());
     if (!Base::tryAllocateBuffer(newCapacity))
         return false;
     ASSERT(begin());
-    TypeOperations::move(oldBuffer, oldEnd, begin());
+    TypeOperations::move(oldBuffer, oldEnd, getPtr(begin()));
     Base::deallocateBuffer(oldBuffer);
     return true;
 }
@@ -1003,17 +1009,17 @@ void Vector<T, inlineCapacity, OverflowHandler>::shrinkCapacity(size_t newCapaci
     if (newCapacity < size()) 
         shrink(newCapacity);
 
-    T* oldBuffer = begin();
+    T* oldBuffer = getPtr(begin());
     if (newCapacity > 0) {
         if (Base::shouldReallocateBuffer(newCapacity)) {
             Base::reallocateBuffer(newCapacity);
             return;
         }
 
-        T* oldEnd = end();
+        T* oldEnd = getPtr(end());
         Base::allocateBuffer(newCapacity);
         if (begin() != oldBuffer)
-            TypeOperations::move(oldBuffer, oldEnd, begin());
+            TypeOperations::move(oldBuffer, oldEnd, getPtr(begin()));
     }
 
     Base::deallocateBuffer(oldBuffer);
@@ -1033,11 +1039,17 @@ void Vector<T, inlineCapacity, OverflowHandler>::append(const U* data, size_t da
     }
     if (newSize < m_size)
         CRASH();
-    T* dest = end();
+    T* dest = getPtr(end());
     VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, &data[dataSize], dest);
     m_size = newSize;
 }
 
+template<typename T, size_t inlineCapacity, typename OverflowHandler>
+void Vector<T, inlineCapacity, OverflowHandler>::append(const_iterator data, size_t dataSize)
+{
+    append(getPtr(data), dataSize);
+}
+
 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
 bool Vector<T, inlineCapacity, OverflowHandler>::tryAppend(const U* data, size_t dataSize)
 {
@@ -1050,7 +1062,7 @@ bool Vector<T, inlineCapacity, OverflowHandler>::tryAppend(const U* data, size_t
     }
     if (newSize < m_size)
         return false;
-    T* dest = end();
+    T* dest = getPtr(end());
     VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, &data[dataSize], dest);
     m_size = newSize;
     return true;
@@ -1060,7 +1072,7 @@ template<typename T, size_t inlineCapacity, typename OverflowHandler> template<t
 ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler>::append(U&& value)
 {
     if (size() != capacity()) {
-        new (NotNull, end()) T(std::forward<U>(value));
+        new (NotNull, getPtr(end())) T(std::forward<U>(value));
         ++m_size;
         return;
     }
@@ -1077,7 +1089,7 @@ void Vector<T, inlineCapacity, OverflowHandler>::appendSlowCase(U&& value)
     ptr = expandCapacity(size() + 1, ptr);
     ASSERT(begin());
 
-    new (NotNull, end()) T(std::forward<U>(*ptr));
+    new (NotNull, getPtr(end())) T(std::forward<U>(*ptr));
     ++m_size;
 }
 
@@ -1090,14 +1102,14 @@ inline void Vector<T, inlineCapacity, OverflowHandler>::uncheckedAppend(U&& valu
     ASSERT(size() < capacity());
 
     auto ptr = std::addressof(value);
-    new (NotNull, end()) T(std::forward<U>(*ptr));
+    new (NotNull, getPtr(end())) T(std::forward<U>(*ptr));
     ++m_size;
 }
 
 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U, size_t otherCapacity>
 inline void Vector<T, inlineCapacity, OverflowHandler>::appendVector(const Vector<U, otherCapacity>& val)
 {
-    append(val.begin(), val.size());
+    append(getPtr(val.begin()), val.size());
 }
 
 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
@@ -1111,8 +1123,8 @@ void Vector<T, inlineCapacity, OverflowHandler>::insert(size_t position, const U
     }
     if (newSize < m_size)
         CRASH();
-    T* spot = begin() + position;
-    TypeOperations::moveOverlapping(spot, end(), spot + dataSize);
+    T* spot = getPtr(begin()) + position;
+    TypeOperations::moveOverlapping(spot, getPtr(end()), spot + dataSize);
     VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, &data[dataSize], spot);
     m_size = newSize;
 }
@@ -1128,8 +1140,8 @@ inline void Vector<T, inlineCapacity, OverflowHandler>::insert(size_t position,
         ASSERT(begin());
     }
 
-    T* spot = begin() + position;
-    TypeOperations::moveOverlapping(spot, end(), spot + 1);
+    T* spot = getPtr(begin()) + position;
+    TypeOperations::moveOverlapping(spot, getPtr(end()), spot + 1);
     new (NotNull, spot) T(std::forward<U>(*ptr));
     ++m_size;
 }
@@ -1137,16 +1149,16 @@ inline void Vector<T, inlineCapacity, OverflowHandler>::insert(size_t position,
 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U, size_t c>
 inline void Vector<T, inlineCapacity, OverflowHandler>::insertVector(size_t position, const Vector<U, c>& val)
 {
-    insert(position, val.begin(), val.size());
+    insert(position, getPtr(val.begin()), val.size());
 }
 
 template<typename T, size_t inlineCapacity, typename OverflowHandler>
 inline void Vector<T, inlineCapacity, OverflowHandler>::remove(size_t position)
 {
     ASSERT_WITH_SECURITY_IMPLICATION(position < size());
-    T* spot = begin() + position;
+    T* spot = getPtr(begin()) + position;
     spot->~T();
-    TypeOperations::moveOverlapping(spot + 1, end(), spot);
+    TypeOperations::moveOverlapping(spot + 1, getPtr(end()), spot);
     --m_size;
 }
 
@@ -1155,10 +1167,10 @@ inline void Vector<T, inlineCapacity, OverflowHandler>::remove(size_t position,
 {
     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
     ASSERT_WITH_SECURITY_IMPLICATION(position + length <= size());
-    T* beginSpot = begin() + position;
+    T* beginSpot = getPtr(begin()) + position;
     T* endSpot = beginSpot + length;
     TypeOperations::destruct(beginSpot, endSpot); 
-    TypeOperations::moveOverlapping(endSpot, end(), beginSpot);
+    TypeOperations::moveOverlapping(endSpot, getPtr(end()), beginSpot);
     m_size -= length;
 }
 
index 1d199ac..7197f35 100644 (file)
@@ -1,3 +1,41 @@
+2014-12-15  Oliver Hunt  <oliver@apple.com>
+
+        Make sure range based iteration of Vector<> still receives bounds checking
+        https://bugs.webkit.org/show_bug.cgi?id=138821
+
+        Reviewed by Mark Lam.
+
+        Update to deal with different iterator type.
+
+        * bindings/js/SerializedScriptValue.cpp:
+        (WebCore::CloneDeserializer::deserializeString):
+        * editing/TextIterator.cpp:
+        (WebCore::SearchBuffer::isBadMatch):
+        * page/mac/ServicesOverlayController.mm:
+        (WebCore::ServicesOverlayController::buildSelectionHighlight):
+        * platform/graphics/SegmentedFontData.cpp:
+        (WebCore::SegmentedFontData::fontDataForCharacter):
+        (WebCore::SegmentedFontData::containsCharacter):
+        (WebCore::SegmentedFontData::isLoading):
+        * platform/graphics/WOFFFileFormat.cpp:
+        (WebCore::convertWOFFToSfnt):
+        * platform/graphics/cairo/GradientCairo.cpp:
+        (WebCore::Gradient::platformGradient):
+        * platform/image-decoders/gif/GIFImageDecoder.cpp:
+        (WebCore::GIFImageDecoder::clearFrameBufferCache):
+        * rendering/RenderBox.cpp:
+        (WebCore::RenderBox::paintFillLayers):
+        * rendering/style/GridResolvedPosition.cpp:
+        (WebCore::firstNamedGridLineBeforePosition):
+        (WebCore::GridResolvedPosition::resolveRowEndColumnEndNamedGridLinePositionAgainstOppositePosition):
+        * svg/SVGFontElement.cpp:
+        (WebCore::kerningForPairOfStringsAndGlyphs):
+        * svg/SVGPathByteStream.h:
+        (WebCore::SVGPathByteStream::append):
+        * xml/XPathNodeSet.h:
+        (WebCore::XPath::NodeSet::begin):
+        (WebCore::XPath::NodeSet::end):
+
 2014-12-15  Chris Dumez  <cdumez@apple.com>
 
         Move '-webkit-text-decoration-skip' to the new StyleBuilder
index e6c8373..f78cb9c 100644 (file)
@@ -1442,8 +1442,8 @@ public:
     {
         if (buffer.isEmpty())
             return String();
-        const uint8_t* ptr = buffer.begin();
-        const uint8_t* end = buffer.end();
+        const uint8_t* ptr = getPtr(buffer.begin());
+        const uint8_t* end = getPtr(buffer.end());
         uint32_t version;
         if (!readLittleEndian(ptr, end, version) || version > CurrentVersion)
             return String();
index 84525be..427b6d2 100644 (file)
@@ -2073,11 +2073,11 @@ inline bool SearchBuffer::isBadMatch(const UChar* match, size_t matchLength) con
     // creating a new one each time.
     normalizeCharacters(match, matchLength, m_normalizedMatch);
 
-    const UChar* a = m_normalizedTarget.begin();
-    const UChar* aEnd = m_normalizedTarget.end();
+    const UChar* a = getPtr(m_normalizedTarget.begin());
+    const UChar* aEnd = getPtr(m_normalizedTarget.end());
 
-    const UChar* b = m_normalizedMatch.begin();
-    const UChar* bEnd = m_normalizedMatch.end();
+    const UChar* b = getPtr(m_normalizedMatch.begin());
+    const UChar* bEnd = getPtr(m_normalizedMatch.end());
 
     while (true) {
         // Skip runs of non-kana-letter characters. This is necessary so we can
index d51ca59..6cd34cf 100644 (file)
@@ -542,7 +542,7 @@ void ServicesOverlayController::buildSelectionHighlight()
 
         if (!cgRects.isEmpty()) {
             CGRect visibleRect = mainFrameView->visibleContentRect();
-            RetainPtr<DDHighlightRef> ddHighlight = adoptCF(DDHighlightCreateWithRectsInVisibleRectWithStyleAndDirection(nullptr, cgRects.begin(), cgRects.size(), visibleRect, DDHighlightStyleBubbleNone | DDHighlightStyleStandardIconArrow | DDHighlightStyleButtonShowAlways, YES, NSWritingDirectionNatural, NO, YES));
+            RetainPtr<DDHighlightRef> ddHighlight = adoptCF(DDHighlightCreateWithRectsInVisibleRectWithStyleAndDirection(nullptr, cgRects.data(), cgRects.size(), visibleRect, DDHighlightStyleBubbleNone | DDHighlightStyleStandardIconArrow | DDHighlightStyleButtonShowAlways, YES, NSWritingDirectionNatural, NO, YES));
             
             newPotentialHighlights.add(Highlight::createForSelection(*this, ddHighlight, selectionRange));
         }
index d1b92b7..503b0e8 100644 (file)
@@ -39,8 +39,8 @@ SegmentedFontData::~SegmentedFontData()
 
 const SimpleFontData* SegmentedFontData::fontDataForCharacter(UChar32 c) const
 {
-    Vector<FontDataRange>::const_iterator end = m_ranges.end();
-    for (Vector<FontDataRange>::const_iterator it = m_ranges.begin(); it != end; ++it) {
+    auto end = m_ranges.end();
+    for (auto it = m_ranges.begin(); it != end; ++it) {
         if (it->from() <= c && it->to() >= c)
             return it->fontData().get();
     }
@@ -49,8 +49,8 @@ const SimpleFontData* SegmentedFontData::fontDataForCharacter(UChar32 c) const
 
 bool SegmentedFontData::containsCharacter(UChar32 c) const
 {
-    Vector<FontDataRange>::const_iterator end = m_ranges.end();
-    for (Vector<FontDataRange>::const_iterator it = m_ranges.begin(); it != end; ++it) {
+    auto end = m_ranges.end();
+    for (auto it = m_ranges.begin(); it != end; ++it) {
         if (c >= it->from() && c <= it->to())
             return true;
     }
@@ -76,8 +76,8 @@ bool SegmentedFontData::isCustomFont() const
 
 bool SegmentedFontData::isLoading() const
 {
-    Vector<FontDataRange>::const_iterator end = m_ranges.end();
-    for (Vector<FontDataRange>::const_iterator it = m_ranges.begin(); it != end; ++it) {
+    auto end = m_ranges.end();
+    for (auto it = m_ranges.begin(); it != end; ++it) {
         if (it->fontData()->isLoading())
             return true;
     }
index 051871a..dd0963a 100644 (file)
@@ -200,7 +200,7 @@ bool convertWOFFToSfnt(SharedBuffer* woff, Vector<char>& sfnt)
             uLongf destLen = tableOrigLength;
             if (!sfnt.tryReserveCapacity(sfnt.size() + tableOrigLength))
                 return false;
-            Bytef* dest = reinterpret_cast<Bytef*>(sfnt.end());
+            Bytef* dest = reinterpret_cast<Bytef*>(getPtr(sfnt.end()));
             sfnt.grow(sfnt.size() + tableOrigLength);
             if (uncompress(dest, &destLen, reinterpret_cast<const Bytef*>(woff->data() + tableOffset), tableCompLength) != Z_OK)
                 return false;
index 5022c50..7516b0a 100644 (file)
@@ -59,7 +59,7 @@ cairo_pattern_t* Gradient::platformGradient(float globalAlpha)
     else
         m_gradient = cairo_pattern_create_linear(m_p0.x(), m_p0.y(), m_p1.x(), m_p1.y());
 
-    Vector<ColorStop>::iterator stopIterator = m_stops.begin();
+    auto stopIterator = m_stops.begin();
     while (stopIterator != m_stops.end()) {
         cairo_pattern_add_color_stop_rgba(m_gradient, stopIterator->stop,
                                           stopIterator->red, stopIterator->green, stopIterator->blue,
index de45509..3a931dd 100644 (file)
@@ -145,7 +145,7 @@ void GIFImageDecoder::clearFrameBufferCache(size_t clearBeforeFrame)
     // always use ImageSource::clear(true, ...) to completely free the memory in
     // this case.
     clearBeforeFrame = std::min(clearBeforeFrame, m_frameBufferCache.size() - 1);
-    const Vector<ImageFrame>::iterator end(m_frameBufferCache.begin() + clearBeforeFrame);
+    const auto end = m_frameBufferCache.begin() + clearBeforeFrame;
 
     // We need to preserve frames such that:
     //   * We don't clear |end|
@@ -165,14 +165,14 @@ void GIFImageDecoder::clearFrameBufferCache(size_t clearBeforeFrame)
     //   * If the frame is partial, we're decoding it, so don't clear it; if it
     //     has a disposal method other than DisposeOverwritePrevious, stop
     //     scanning, as we'll only need this frame when decoding the next one.
-    Vector<ImageFrame>::iterator i(end);
+    auto i = end;
     for (; (i != m_frameBufferCache.begin()) && ((i->status() == ImageFrame::FrameEmpty) || (i->disposalMethod() == ImageFrame::DisposeOverwritePrevious)); --i) {
         if ((i->status() == ImageFrame::FrameComplete) && (i != end))
             i->clearPixelData();
     }
 
     // Now |i| holds the last frame we need to preserve; clear prior frames.
-    for (Vector<ImageFrame>::iterator j(m_frameBufferCache.begin()); j != i; ++j) {
+    for (auto j = m_frameBufferCache.begin(); j != i; ++j) {
         ASSERT(j->status() != ImageFrame::FramePartial);
         if (j->status() != ImageFrame::FrameEmpty)
             j->clearPixelData();
index 42ca74f..ceef23d 100644 (file)
@@ -1577,8 +1577,8 @@ void RenderBox::paintFillLayers(const PaintInfo& paintInfo, const Color& c, cons
         context->beginTransparencyLayer(1);
     }
 
-    Vector<const FillLayer*>::const_reverse_iterator topLayer = layers.rend();
-    for (Vector<const FillLayer*>::const_reverse_iterator it = layers.rbegin(); it != topLayer; ++it)
+    auto topLayer = layers.rend();
+    for (auto it = layers.rbegin(); it != topLayer; ++it)
         paintFillLayer(paintInfo, c, *it, rect, bleedAvoidance, op, backgroundObject, baseBgColorUsage);
 
     if (shouldDrawBackgroundInSeparateBuffer)
index ccdc2a3..dc09509 100644 (file)
@@ -295,7 +295,7 @@ static inline unsigned firstNamedGridLineBeforePosition(unsigned position, const
     // already converted to an index in our grid representation (ie one was removed from the grid line to account for
     // the side).
     unsigned firstLineBeforePositionIndex = 0;
-    const unsigned* firstLineBeforePosition = std::lower_bound(gridLines.begin(), gridLines.end(), position);
+    auto firstLineBeforePosition = std::lower_bound(gridLines.begin(), gridLines.end(), position);
     if (firstLineBeforePosition != gridLines.end()) {
         if (*firstLineBeforePosition > position && firstLineBeforePosition != gridLines.begin())
             --firstLineBeforePosition;
@@ -316,9 +316,8 @@ std::unique_ptr<GridSpan> GridResolvedPosition::resolveRowStartColumnStartNamedG
 
 std::unique_ptr<GridSpan> GridResolvedPosition::resolveRowEndColumnEndNamedGridLinePositionAgainstOppositePosition(const GridResolvedPosition& resolvedOppositePosition, const GridPosition& position, const Vector<unsigned>& gridLines)
 {
-    ASSERT(gridLines.size());
     unsigned firstLineAfterOppositePositionIndex = gridLines.size() - 1;
-    const unsigned* firstLineAfterOppositePosition = std::upper_bound(gridLines.begin(), gridLines.end(), resolvedOppositePosition);
+    auto firstLineAfterOppositePosition = std::upper_bound(gridLines.begin(), gridLines.end(), resolvedOppositePosition);
     if (firstLineAfterOppositePosition != gridLines.end())
         firstLineAfterOppositePositionIndex = firstLineAfterOppositePosition - gridLines.begin();
 
index c33ffb7..a0bf501 100644 (file)
@@ -252,31 +252,31 @@ static inline float kerningForPairOfStringsAndGlyphs(const SVGKerningMap& kernin
 {
     if (!g1.isEmpty() && kerningMap.glyphMap.contains(g1)) {
         SVGKerningVector* kerningVector = kerningMap.glyphMap.get(g1);
-        SVGKerningVector::const_iterator it = kerningVector->end() - 1;
-        const SVGKerningVector::const_iterator begin = kerningVector->begin() - 1;
-        for (; it != begin; --it) {
-            if (matches(u2, g2, *it))
-                return it->kerning;
+        size_t it = kerningVector->size();
+        while (it-- > 0) {
+            auto& value = kerningVector->at(it);
+            if (matches(u2, g2, value))
+                return value.kerning;
         }
     }
 
     if (!u1.isEmpty()) {
         if (kerningMap.unicodeMap.contains(u1)) {
             SVGKerningVector* kerningVector = kerningMap.unicodeMap.get(u1);
-            SVGKerningVector::const_iterator it = kerningVector->end() - 1;
-            const SVGKerningVector::const_iterator begin = kerningVector->begin() - 1;
-            for (; it != begin; --it) {
-                if (matches(u2, g2, *it))
-                    return it->kerning;
+            size_t it = kerningVector->size();
+            while (it-- > 0) {
+                auto& value = kerningVector->at(it);
+                if (matches(u2, g2, value))
+                    return value.kerning;
             }
         }
 
         if (!kerningMap.kerningUnicodeRangeMap.isEmpty()) {
-            Vector<SVGKerningPair>::const_iterator it = kerningMap.kerningUnicodeRangeMap.end() - 1;
-            const Vector<SVGKerningPair>::const_iterator begin = kerningMap.kerningUnicodeRangeMap.begin() - 1;
-            for (; it != begin; --it) {
-                if (matches(u1, u2, g2, *it))
-                    return it->kerning;
+            size_t it = kerningMap.kerningUnicodeRangeMap.size();
+            while (it-- > 0) {
+                auto& value = kerningMap.kerningUnicodeRangeMap[it];
+                if (matches(u1, u2, g2, value))
+                    return value.kerning;
             }
         }
     }
index 9d9d2a2..b999554 100644 (file)
@@ -60,8 +60,8 @@ public:
     void append(unsigned char byte) { m_data.append(byte); }
     void append(SVGPathByteStream* other)
     {
-        for (DataIterator it = other->begin(); it != other->end(); ++it)
-            append(*it);
+        for (auto& byte : *other)
+            append(byte);
     }
     void clear() { m_data.clear(); }
     bool isEmpty() const { return !m_data.size(); }
index 3d89b8d..daf2b93 100644 (file)
@@ -64,8 +64,8 @@ namespace WebCore {
             void markSubtreesDisjoint(bool disjoint) { m_subtreesAreDisjoint = disjoint; }
             bool subtreesAreDisjoint() const { return m_subtreesAreDisjoint || m_nodes.size() < 2; }
 
-            const RefPtr<Node>* begin() const { return m_nodes.begin(); }
-            const RefPtr<Node>* end() const { return m_nodes.end(); }
+            const Vector<RefPtr<Node>>::iterator begin() const { return m_nodes.begin(); }
+            const Vector<RefPtr<Node>>::iterator end() const { return m_nodes.end(); }
 
         private:
             void traversalSort() const;