Replace WTF::move with WTFMove
[WebKit-https.git] / Source / WebCore / contentextensions / MutableRangeList.h
1 /*
2  * Copyright (C) 2015 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #ifndef MutableRangeList_h
27 #define MutableRangeList_h
28
29 #include "MutableRange.h"
30
31 #if ENABLE(CONTENT_EXTENSIONS)
32
33 namespace WebCore {
34
35 namespace ContentExtensions {
36
37 // A range list keeps ranges sorted. Ranges are not sorted in the vector, but
38 template <typename CharacterType, typename DataType, unsigned inlineCapacity = 0>
39 class MutableRangeList {
40     typedef MutableRange<CharacterType, DataType> TypedMutableRange;
41 public:
42     class ConstIterator {
43     public:
44         const MutableRangeList& rangeList;
45         uint32_t index;
46         bool atEnd;
47
48         const TypedMutableRange& operator*() const { return rangeList.m_ranges[index]; }
49         const TypedMutableRange* operator->() const { return &rangeList.m_ranges[index]; }
50
51         CharacterType first() const { return rangeList.m_ranges[index].first; }
52         CharacterType last() const { return rangeList.m_ranges[index].last; }
53         CharacterType data() const { return rangeList.m_ranges[index].data; }
54
55         bool operator==(const ConstIterator& other) const
56         {
57             ASSERT(&rangeList == &other.rangeList);
58             if (atEnd || other.atEnd)
59                 return atEnd == other.atEnd;
60             return index == other.index;
61         }
62         bool operator!=(const ConstIterator& other) const { return !(*this == other); }
63
64         ConstIterator& operator++()
65         {
66             ASSERT(!atEnd);
67             index = rangeList.m_ranges[index].nextRangeIndex;
68             if (!index)
69                 atEnd = true;
70             return *this;
71         }
72     };
73
74     ConstIterator begin() const { return ConstIterator { *this, 0, m_ranges.isEmpty() }; }
75     ConstIterator end() const { return ConstIterator { *this, 0, true }; }
76
77     uint32_t appendRange(uint32_t lastRangeIndex, CharacterType first, CharacterType last, const DataType& data)
78     {
79         uint32_t newRangeIndex = m_ranges.size();
80         m_ranges.append(TypedMutableRange(data, 0, first, last));
81         if (!newRangeIndex)
82             return 0;
83
84         ASSERT(!m_ranges[lastRangeIndex].nextRangeIndex);
85         ASSERT(m_ranges[lastRangeIndex].last < first);
86
87         m_ranges[lastRangeIndex].nextRangeIndex = newRangeIndex;
88         return newRangeIndex;
89     }
90
91     template <typename RangeIterator, typename DataConverter>
92     void extend(RangeIterator otherIterator, RangeIterator otherEnd, DataConverter dataConverter)
93     {
94         if (otherIterator == otherEnd)
95             return;
96
97         if (m_ranges.isEmpty()) {
98             initializeFrom(otherIterator, otherEnd, dataConverter);
99             return;
100         }
101
102         bool reachedSelfEnd = false;
103         uint32_t lastSelfRangeIndex = 0;
104         uint32_t selfRangeIndex = 0;
105
106         auto otherRangeOffset = otherIterator.first(); // To get the right type :)
107         otherRangeOffset = 0;
108
109         do {
110             TypedMutableRange* activeSelfRange = &m_ranges[selfRangeIndex];
111
112             // First, we move forward until we find something interesting.
113             if (activeSelfRange->last < otherIterator.first() + otherRangeOffset) {
114                 lastSelfRangeIndex = selfRangeIndex;
115                 selfRangeIndex = activeSelfRange->nextRangeIndex;
116                 reachedSelfEnd = !selfRangeIndex;
117                 continue;
118             }
119             if (otherIterator.last() < activeSelfRange->first) {
120                 insertBetween(lastSelfRangeIndex, selfRangeIndex, otherIterator.first() + otherRangeOffset, otherIterator.last(), dataConverter.convert(otherIterator.data()));
121
122                 ++otherIterator;
123                 otherRangeOffset = 0;
124                 continue;
125             }
126
127             // If we reached here, we have:
128             // 1) activeRangeA->last >= activeRangeB->first.
129             // 2) activeRangeA->first <= activeRangeB->last.
130             // But we don't know how they collide.
131
132             // Do we have a part on the left? Create a new range for it.
133             if (activeSelfRange->first < otherIterator.first() + otherRangeOffset) {
134                 DataType copiedData = activeSelfRange->data;
135                 CharacterType newRangeFirstCharacter = activeSelfRange->first;
136                 activeSelfRange->first = otherIterator.first() + otherRangeOffset;
137                 insertBetween(lastSelfRangeIndex, selfRangeIndex, newRangeFirstCharacter, otherIterator.first() + otherRangeOffset - 1, WTFMove(copiedData));
138                 activeSelfRange = &m_ranges[selfRangeIndex];
139             } else if (otherIterator.first() + otherRangeOffset < activeSelfRange->first) {
140                 insertBetween(lastSelfRangeIndex, selfRangeIndex, otherIterator.first() + otherRangeOffset, activeSelfRange->first - 1, dataConverter.convert(otherIterator.data()));
141
142                 activeSelfRange = &m_ranges[selfRangeIndex];
143                 ASSERT_WITH_MESSAGE(otherRangeOffset < activeSelfRange->first - otherIterator.first(), "The offset must move forward or we could get stuck on this operation.");
144                 otherRangeOffset = activeSelfRange->first - otherIterator.first();
145             }
146
147             // Here, we know both ranges start at the same point, we need to create the part that intersect
148             // and merge the data.
149
150             if (activeSelfRange->last == otherIterator.last()) {
151                 // If they finish together, things are really easy: we just add B to A.
152                 dataConverter.extend(activeSelfRange->data, otherIterator.data());
153
154                 lastSelfRangeIndex = selfRangeIndex;
155                 selfRangeIndex = activeSelfRange->nextRangeIndex;
156                 reachedSelfEnd = !selfRangeIndex;
157
158                 ++otherIterator;
159                 otherRangeOffset = 0;
160                 continue;
161             }
162
163             if (activeSelfRange->last > otherIterator.last()) {
164                 // If A is bigger than B, we add a merged version and move A to the right.
165
166                 CharacterType combinedPartStart = activeSelfRange->first;
167                 activeSelfRange->first = otherIterator.last() + 1;
168
169                 DataType combinedData = activeSelfRange->data;
170                 dataConverter.extend(combinedData, otherIterator.data());
171                 insertBetween(lastSelfRangeIndex, selfRangeIndex, combinedPartStart, otherIterator.last(), WTFMove(combinedData));
172
173                 ++otherIterator;
174                 otherRangeOffset = 0;
175                 continue;
176             }
177
178             // If we reached here, B ends after A. We merge the intersection and move on.
179             ASSERT(otherIterator.last() > activeSelfRange->last);
180             dataConverter.extend(activeSelfRange->data, otherIterator.data());
181
182             otherRangeOffset = activeSelfRange->last - otherIterator.first() + 1;
183             lastSelfRangeIndex = selfRangeIndex;
184             selfRangeIndex = activeSelfRange->nextRangeIndex;
185             reachedSelfEnd = !selfRangeIndex;
186         } while (!reachedSelfEnd && otherIterator != otherEnd);
187
188         while (otherIterator != otherEnd) {
189             lastSelfRangeIndex = appendRange(lastSelfRangeIndex, otherIterator.first() + otherRangeOffset, otherIterator.last(), dataConverter.convert(otherIterator.data()));
190             otherRangeOffset = 0;
191             ++otherIterator;
192         }
193     }
194
195     unsigned size() const
196     {
197         return m_ranges.size();
198     }
199
200     bool isEmpty() const
201     {
202         return m_ranges.isEmpty();
203     }
204
205     void clear()
206     {
207         m_ranges.clear();
208     }
209
210 #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
211     void debugPrint() const
212     {
213         for (const TypedMutableRange& range : *this)
214             WTFLogAlways("    %d-%d", range.first, range.last);
215     }
216 #endif
217
218     Vector<MutableRange<CharacterType, DataType>, inlineCapacity, ContentExtensionsOverflowHandler> m_ranges;
219 private:
220     void insertBetween(uint32_t& leftRangeIndex, uint32_t& rightRangeIndex, CharacterType first, CharacterType last, DataType&& data)
221     {
222         ASSERT(m_ranges[rightRangeIndex].first > last);
223
224         if (!rightRangeIndex) {
225             // This is a special case. We always keep the first range as the first element in the vector.
226             uint32_t movedRangeIndex = m_ranges.size();
227             m_ranges.append(WTFMove(m_ranges.first()));
228             m_ranges[0] = TypedMutableRange(WTFMove(data), movedRangeIndex, first, last);
229             leftRangeIndex = 0;
230             rightRangeIndex = movedRangeIndex;
231             return;
232         }
233
234         ASSERT(m_ranges[leftRangeIndex].nextRangeIndex == rightRangeIndex);
235         ASSERT(m_ranges[leftRangeIndex].last < first);
236
237         uint32_t newRangeIndex = m_ranges.size();
238         m_ranges.append(TypedMutableRange(WTFMove(data), rightRangeIndex, first, last));
239         m_ranges[leftRangeIndex].nextRangeIndex = newRangeIndex;
240         leftRangeIndex = newRangeIndex;
241     }
242
243     template <typename RangeIterator, typename DataConverter>
244     void initializeFrom(RangeIterator otherIterator, RangeIterator otherEnd, DataConverter dataConverter)
245     {
246         ASSERT_WITH_MESSAGE(otherIterator != otherEnd, "We should never do anything when extending with a null range.");
247         ASSERT_WITH_MESSAGE(m_ranges.isEmpty(), "This code does not handle splitting, it can only be used on empty RangeList.");
248
249         uint32_t loopCounter = 0;
250         do {
251             m_ranges.append(TypedMutableRange(dataConverter.convert(otherIterator.data()),
252                 loopCounter + 1,
253                 otherIterator.first(),
254                 otherIterator.last()));
255             ++loopCounter;
256             ++otherIterator;
257         } while (otherIterator != otherEnd);
258
259         if (!m_ranges.isEmpty())
260             m_ranges.last().nextRangeIndex = 0;
261     }
262 };
263
264 }
265
266 } // namespace WebCore
267
268 #endif // ENABLE(CONTENT_EXTENSIONS)
269
270 #endif // MutableRangeList_h