1 files changed, 266 insertions, 0 deletions
diff --git a/Source/WebCore/contentextensions/MutableRangeList.h b/Source/WebCore/contentextensions/MutableRangeList.h
new file mode 100644
index 000000000..9b20687b8
--- /dev/null
+++ b/Source/WebCore/contentextensions/MutableRangeList.h
@@ -0,0 +1,266 @@
+/*
+ * Copyright (C) 2015 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. AND ITS CONTRIBUTORS ``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 ITS 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.
+ */
+
+#pragma once
+
+#include "MutableRange.h"
+
+#if ENABLE(CONTENT_EXTENSIONS)
+
+namespace WebCore {
+
+namespace ContentExtensions {
+
+// A range list keeps ranges sorted. Ranges are not sorted in the vector, but
+template <typename CharacterType, typename DataType, unsigned inlineCapacity = 0>
+class MutableRangeList {
+    typedef MutableRange<CharacterType, DataType> TypedMutableRange;
+public:
+    class ConstIterator {
+    public:
+        const MutableRangeList& rangeList;
+        uint32_t index;
+        bool atEnd;
+
+        const TypedMutableRange& operator*() const { return rangeList.m_ranges[index]; }
+        const TypedMutableRange* operator->() const { return &rangeList.m_ranges[index]; }
+
+        CharacterType first() const { return rangeList.m_ranges[index].first; }
+        CharacterType last() const { return rangeList.m_ranges[index].last; }
+        CharacterType data() const { return rangeList.m_ranges[index].data; }
+
+        bool operator==(const ConstIterator& other) const
+        {
+            ASSERT(&rangeList == &other.rangeList);
+            if (atEnd || other.atEnd)
+                return atEnd == other.atEnd;
+            return index == other.index;
+        }
+        bool operator!=(const ConstIterator& other) const { return !(*this == other); }
+
+        ConstIterator& operator++()
+        {
+            ASSERT(!atEnd);
+            index = rangeList.m_ranges[index].nextRangeIndex;
+            if (!index)
+                atEnd = true;
+            return *this;
+        }
+    };
+
+    ConstIterator begin() const { return ConstIterator { *this, 0, m_ranges.isEmpty() }; }
+    ConstIterator end() const { return ConstIterator { *this, 0, true }; }
+
+    uint32_t appendRange(uint32_t lastRangeIndex, CharacterType first, CharacterType last, const DataType& data)
+    {
+        uint32_t newRangeIndex = m_ranges.size();
+        m_ranges.append(TypedMutableRange(data, 0, first, last));
+        if (!newRangeIndex)
+            return 0;
+
+        ASSERT(!m_ranges[lastRangeIndex].nextRangeIndex);
+        ASSERT(m_ranges[lastRangeIndex].last < first);
+
+        m_ranges[lastRangeIndex].nextRangeIndex = newRangeIndex;
+        return newRangeIndex;
+    }
+
+    template <typename RangeIterator, typename DataConverter>
+    void extend(RangeIterator otherIterator, RangeIterator otherEnd, DataConverter dataConverter)
+    {
+        if (otherIterator == otherEnd)
+            return;
+
+        if (m_ranges.isEmpty()) {
+            initializeFrom(otherIterator, otherEnd, dataConverter);
+            return;
+        }
+
+        bool reachedSelfEnd = false;
+        uint32_t lastSelfRangeIndex = 0;
+        uint32_t selfRangeIndex = 0;
+
+        auto otherRangeOffset = otherIterator.first(); // To get the right type :)
+        otherRangeOffset = 0;
+
+        do {
+            TypedMutableRange* activeSelfRange = &m_ranges[selfRangeIndex];
+
+            // First, we move forward until we find something interesting.
+            if (activeSelfRange->last < otherIterator.first() + otherRangeOffset) {
+                lastSelfRangeIndex = selfRangeIndex;
+                selfRangeIndex = activeSelfRange->nextRangeIndex;
+                reachedSelfEnd = !selfRangeIndex;
+                continue;
+            }
+            if (otherIterator.last() < activeSelfRange->first) {
+                insertBetween(lastSelfRangeIndex, selfRangeIndex, otherIterator.first() + otherRangeOffset, otherIterator.last(), dataConverter.convert(otherIterator.data()));
+
+                ++otherIterator;
+                otherRangeOffset = 0;
+                continue;
+            }
+
+            // If we reached here, we have:
+            // 1) activeRangeA->last >= activeRangeB->first.
+            // 2) activeRangeA->first <= activeRangeB->last.
+            // But we don't know how they collide.
+
+            // Do we have a part on the left? Create a new range for it.
+            if (activeSelfRange->first < otherIterator.first() + otherRangeOffset) {
+                DataType copiedData = activeSelfRange->data;
+                CharacterType newRangeFirstCharacter = activeSelfRange->first;
+                activeSelfRange->first = otherIterator.first() + otherRangeOffset;
+                insertBetween(lastSelfRangeIndex, selfRangeIndex, newRangeFirstCharacter, otherIterator.first() + otherRangeOffset - 1, WTFMove(copiedData));
+                activeSelfRange = &m_ranges[selfRangeIndex];
+            } else if (otherIterator.first() + otherRangeOffset < activeSelfRange->first) {
+                insertBetween(lastSelfRangeIndex, selfRangeIndex, otherIterator.first() + otherRangeOffset, activeSelfRange->first - 1, dataConverter.convert(otherIterator.data()));
+
+                activeSelfRange = &m_ranges[selfRangeIndex];
+                ASSERT_WITH_MESSAGE(otherRangeOffset < activeSelfRange->first - otherIterator.first(), "The offset must move forward or we could get stuck on this operation.");
+                otherRangeOffset = activeSelfRange->first - otherIterator.first();
+            }
+
+            // Here, we know both ranges start at the same point, we need to create the part that intersect
+            // and merge the data.
+
+            if (activeSelfRange->last == otherIterator.last()) {
+                // If they finish together, things are really easy: we just add B to A.
+                dataConverter.extend(activeSelfRange->data, otherIterator.data());
+
+                lastSelfRangeIndex = selfRangeIndex;
+                selfRangeIndex = activeSelfRange->nextRangeIndex;
+                reachedSelfEnd = !selfRangeIndex;
+
+                ++otherIterator;
+                otherRangeOffset = 0;
+                continue;
+            }
+
+            if (activeSelfRange->last > otherIterator.last()) {
+                // If A is bigger than B, we add a merged version and move A to the right.
+
+                CharacterType combinedPartStart = activeSelfRange->first;
+                activeSelfRange->first = otherIterator.last() + 1;
+
+                DataType combinedData = activeSelfRange->data;
+                dataConverter.extend(combinedData, otherIterator.data());
+                insertBetween(lastSelfRangeIndex, selfRangeIndex, combinedPartStart, otherIterator.last(), WTFMove(combinedData));
+
+                ++otherIterator;
+                otherRangeOffset = 0;
+                continue;
+            }
+
+            // If we reached here, B ends after A. We merge the intersection and move on.
+            ASSERT(otherIterator.last() > activeSelfRange->last);
+            dataConverter.extend(activeSelfRange->data, otherIterator.data());
+
+            otherRangeOffset = activeSelfRange->last - otherIterator.first() + 1;
+            lastSelfRangeIndex = selfRangeIndex;
+            selfRangeIndex = activeSelfRange->nextRangeIndex;
+            reachedSelfEnd = !selfRangeIndex;
+        } while (!reachedSelfEnd && otherIterator != otherEnd);
+
+        while (otherIterator != otherEnd) {
+            lastSelfRangeIndex = appendRange(lastSelfRangeIndex, otherIterator.first() + otherRangeOffset, otherIterator.last(), dataConverter.convert(otherIterator.data()));
+            otherRangeOffset = 0;
+            ++otherIterator;
+        }
+    }
+
+    unsigned size() const
+    {
+        return m_ranges.size();
+    }
+
+    bool isEmpty() const
+    {
+        return m_ranges.isEmpty();
+    }
+
+    void clear()
+    {
+        m_ranges.clear();
+    }
+
+#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
+    void debugPrint() const
+    {
+        for (const TypedMutableRange& range : *this)
+            WTFLogAlways("    %d-%d", range.first, range.last);
+    }
+#endif
+
+    Vector<MutableRange<CharacterType, DataType>, inlineCapacity, ContentExtensionsOverflowHandler> m_ranges;
+private:
+    void insertBetween(uint32_t& leftRangeIndex, uint32_t& rightRangeIndex, CharacterType first, CharacterType last, DataType&& data)
+    {
+        ASSERT(m_ranges[rightRangeIndex].first > last);
+
+        if (!rightRangeIndex) {
+            // This is a special case. We always keep the first range as the first element in the vector.
+            uint32_t movedRangeIndex = m_ranges.size();
+            m_ranges.append(WTFMove(m_ranges.first()));
+            m_ranges[0] = TypedMutableRange(WTFMove(data), movedRangeIndex, first, last);
+            leftRangeIndex = 0;
+            rightRangeIndex = movedRangeIndex;
+            return;
+        }
+
+        ASSERT(m_ranges[leftRangeIndex].nextRangeIndex == rightRangeIndex);
+        ASSERT(m_ranges[leftRangeIndex].last < first);
+
+        uint32_t newRangeIndex = m_ranges.size();
+        m_ranges.append(TypedMutableRange(WTFMove(data), rightRangeIndex, first, last));
+        m_ranges[leftRangeIndex].nextRangeIndex = newRangeIndex;
+        leftRangeIndex = newRangeIndex;
+    }
+
+    template <typename RangeIterator, typename DataConverter>
+    void initializeFrom(RangeIterator otherIterator, RangeIterator otherEnd, DataConverter dataConverter)
+    {
+        ASSERT_WITH_MESSAGE(otherIterator != otherEnd, "We should never do anything when extending with a null range.");
+        ASSERT_WITH_MESSAGE(m_ranges.isEmpty(), "This code does not handle splitting, it can only be used on empty RangeList.");
+
+        uint32_t loopCounter = 0;
+        do {
+            m_ranges.append(TypedMutableRange(dataConverter.convert(otherIterator.data()),
+                loopCounter + 1,
+                otherIterator.first(),
+                otherIterator.last()));
+            ++loopCounter;
+            ++otherIterator;
+        } while (otherIterator != otherEnd);
+
+        if (!m_ranges.isEmpty())
+            m_ranges.last().nextRangeIndex = 0;
+    }
+};
+
+} // namespace ContentExtensions
+} // namespace WebCore
+
+#endif // ENABLE(CONTENT_EXTENSIONS)