MutableRangeList.h   [plain text]

/*
 * 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.
 */

#ifndef MutableRangeList_h
#define MutableRangeList_h

#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, WTF::move(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(), WTF::move(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(WTF::move(m_ranges.first()));
            m_ranges[0] = TypedMutableRange(WTF::move(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(WTF::move(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 WebCore

#endif // ENABLE(CONTENT_EXTENSIONS)

#endif // MutableRangeList_h