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#pragma once
27
28#include "MutableRange.h"
29
30#if ENABLE(CONTENT_EXTENSIONS)
31
32namespace WebCore {
33
34namespace ContentExtensions {
35
36// A range list keeps ranges sorted. Ranges are not sorted in the vector, but
37template <typename CharacterType, typename DataType, unsigned inlineCapacity = 0>
38class MutableRangeList {
39 typedef MutableRange<CharacterType, DataType> TypedMutableRange;
40public:
41 class ConstIterator {
42 public:
43 const MutableRangeList& rangeList;
44 uint32_t index;
45 bool atEnd;
46
47 const TypedMutableRange& operator*() const { return rangeList.m_ranges[index]; }
48 const TypedMutableRange* operator->() const { return &rangeList.m_ranges[index]; }
49
50 CharacterType first() const { return rangeList.m_ranges[index].first; }
51 CharacterType last() const { return rangeList.m_ranges[index].last; }
52 CharacterType data() const { return rangeList.m_ranges[index].data; }
53
54 bool operator==(const ConstIterator& other) const
55 {
56 ASSERT(&rangeList == &other.rangeList);
57 if (atEnd || other.atEnd)
58 return atEnd == other.atEnd;
59 return index == other.index;
60 }
61 bool operator!=(const ConstIterator& other) const { return !(*this == other); }
62
63 ConstIterator& operator++()
64 {
65 ASSERT(!atEnd);
66 index = rangeList.m_ranges[index].nextRangeIndex;
67 if (!index)
68 atEnd = true;
69 return *this;
70 }
71 };
72
73 ConstIterator begin() const { return ConstIterator { *this, 0, m_ranges.isEmpty() }; }
74 ConstIterator end() const { return ConstIterator { *this, 0, true }; }
75
76 uint32_t appendRange(uint32_t lastRangeIndex, CharacterType first, CharacterType last, const DataType& data)
77 {
78 uint32_t newRangeIndex = m_ranges.size();
79 m_ranges.append(TypedMutableRange(data, 0, first, last));
80 if (!newRangeIndex)
81 return 0;
82
83 ASSERT(!m_ranges[lastRangeIndex].nextRangeIndex);
84 ASSERT(m_ranges[lastRangeIndex].last < first);
85
86 m_ranges[lastRangeIndex].nextRangeIndex = newRangeIndex;
87 return newRangeIndex;
88 }
89
90 template <typename RangeIterator, typename DataConverter>
91 void extend(RangeIterator otherIterator, RangeIterator otherEnd, DataConverter dataConverter)
92 {
93 if (otherIterator == otherEnd)
94 return;
95
96 if (m_ranges.isEmpty()) {
97 initializeFrom(otherIterator, otherEnd, dataConverter);
98 return;
99 }
100
101 bool reachedSelfEnd = false;
102 uint32_t lastSelfRangeIndex = 0;
103 uint32_t selfRangeIndex = 0;
104
105 auto otherRangeOffset = otherIterator.first(); // To get the right type :)
106 otherRangeOffset = 0;
107
108 do {
109 TypedMutableRange* activeSelfRange = &m_ranges[selfRangeIndex];
110
111 // First, we move forward until we find something interesting.
112 if (activeSelfRange->last < otherIterator.first() + otherRangeOffset) {
113 lastSelfRangeIndex = selfRangeIndex;
114 selfRangeIndex = activeSelfRange->nextRangeIndex;
115 reachedSelfEnd = !selfRangeIndex;
116 continue;
117 }
118 if (otherIterator.last() < activeSelfRange->first) {
119 insertBetween(lastSelfRangeIndex, selfRangeIndex, otherIterator.first() + otherRangeOffset, otherIterator.last(), dataConverter.convert(otherIterator.data()));
120
121 ++otherIterator;
122 otherRangeOffset = 0;
123 continue;
124 }
125
126 // If we reached here, we have:
127 // 1) activeRangeA->last >= activeRangeB->first.
128 // 2) activeRangeA->first <= activeRangeB->last.
129 // But we don't know how they collide.
130
131 // Do we have a part on the left? Create a new range for it.
132 if (activeSelfRange->first < otherIterator.first() + otherRangeOffset) {
133 DataType copiedData = activeSelfRange->data;
134 CharacterType newRangeFirstCharacter = activeSelfRange->first;
135 activeSelfRange->first = otherIterator.first() + otherRangeOffset;
136 insertBetween(lastSelfRangeIndex, selfRangeIndex, newRangeFirstCharacter, otherIterator.first() + otherRangeOffset - 1, WTFMove(copiedData));
137 activeSelfRange = &m_ranges[selfRangeIndex];
138 } else if (otherIterator.first() + otherRangeOffset < activeSelfRange->first) {
139 insertBetween(lastSelfRangeIndex, selfRangeIndex, otherIterator.first() + otherRangeOffset, activeSelfRange->first - 1, dataConverter.convert(otherIterator.data()));
140
141 activeSelfRange = &m_ranges[selfRangeIndex];
142 ASSERT_WITH_MESSAGE(otherRangeOffset < activeSelfRange->first - otherIterator.first(), "The offset must move forward or we could get stuck on this operation.");
143 otherRangeOffset = activeSelfRange->first - otherIterator.first();
144 }
145
146 // Here, we know both ranges start at the same point, we need to create the part that intersect
147 // and merge the data.
148
149 if (activeSelfRange->last == otherIterator.last()) {
150 // If they finish together, things are really easy: we just add B to A.
151 dataConverter.extend(activeSelfRange->data, otherIterator.data());
152
153 lastSelfRangeIndex = selfRangeIndex;
154 selfRangeIndex = activeSelfRange->nextRangeIndex;
155 reachedSelfEnd = !selfRangeIndex;
156
157 ++otherIterator;
158 otherRangeOffset = 0;
159 continue;
160 }
161
162 if (activeSelfRange->last > otherIterator.last()) {
163 // If A is bigger than B, we add a merged version and move A to the right.
164
165 CharacterType combinedPartStart = activeSelfRange->first;
166 activeSelfRange->first = otherIterator.last() + 1;
167
168 DataType combinedData = activeSelfRange->data;
169 dataConverter.extend(combinedData, otherIterator.data());
170 insertBetween(lastSelfRangeIndex, selfRangeIndex, combinedPartStart, otherIterator.last(), WTFMove(combinedData));
171
172 ++otherIterator;
173 otherRangeOffset = 0;
174 continue;
175 }
176
177 // If we reached here, B ends after A. We merge the intersection and move on.
178 ASSERT(otherIterator.last() > activeSelfRange->last);
179 dataConverter.extend(activeSelfRange->data, otherIterator.data());
180
181 otherRangeOffset = activeSelfRange->last - otherIterator.first() + 1;
182 lastSelfRangeIndex = selfRangeIndex;
183 selfRangeIndex = activeSelfRange->nextRangeIndex;
184 reachedSelfEnd = !selfRangeIndex;
185 } while (!reachedSelfEnd && otherIterator != otherEnd);
186
187 while (otherIterator != otherEnd) {
188 lastSelfRangeIndex = appendRange(lastSelfRangeIndex, otherIterator.first() + otherRangeOffset, otherIterator.last(), dataConverter.convert(otherIterator.data()));
189 otherRangeOffset = 0;
190 ++otherIterator;
191 }
192 }
193
194 unsigned size() const
195 {
196 return m_ranges.size();
197 }
198
199 bool isEmpty() const
200 {
201 return m_ranges.isEmpty();
202 }
203
204 void clear()
205 {
206 m_ranges.clear();
207 }
208
209#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
210 void debugPrint() const
211 {
212 for (const TypedMutableRange& range : *this)
213 WTFLogAlways(" %d-%d", range.first, range.last);
214 }
215#endif
216
217 Vector<MutableRange<CharacterType, DataType>, inlineCapacity, ContentExtensionsOverflowHandler> m_ranges;
218private:
219 void insertBetween(uint32_t& leftRangeIndex, uint32_t& rightRangeIndex, CharacterType first, CharacterType last, DataType&& data)
220 {
221 ASSERT(m_ranges[rightRangeIndex].first > last);
222
223 if (!rightRangeIndex) {
224 // This is a special case. We always keep the first range as the first element in the vector.
225 uint32_t movedRangeIndex = m_ranges.size();
226 m_ranges.append(WTFMove(m_ranges.first()));
227 m_ranges[0] = TypedMutableRange(WTFMove(data), movedRangeIndex, first, last);
228 leftRangeIndex = 0;
229 rightRangeIndex = movedRangeIndex;
230 return;
231 }
232
233 ASSERT(m_ranges[leftRangeIndex].nextRangeIndex == rightRangeIndex);
234 ASSERT(m_ranges[leftRangeIndex].last < first);
235
236 uint32_t newRangeIndex = m_ranges.size();
237 m_ranges.append(TypedMutableRange(WTFMove(data), rightRangeIndex, first, last));
238 m_ranges[leftRangeIndex].nextRangeIndex = newRangeIndex;
239 leftRangeIndex = newRangeIndex;
240 }
241
242 template <typename RangeIterator, typename DataConverter>
243 void initializeFrom(RangeIterator otherIterator, RangeIterator otherEnd, DataConverter dataConverter)
244 {
245 ASSERT_WITH_MESSAGE(otherIterator != otherEnd, "We should never do anything when extending with a null range.");
246 ASSERT_WITH_MESSAGE(m_ranges.isEmpty(), "This code does not handle splitting, it can only be used on empty RangeList.");
247
248 uint32_t loopCounter = 0;
249 do {
250 m_ranges.append(TypedMutableRange(dataConverter.convert(otherIterator.data()),
251 loopCounter + 1,
252 otherIterator.first(),
253 otherIterator.last()));
254 ++loopCounter;
255 ++otherIterator;
256 } while (otherIterator != otherEnd);
257
258 if (!m_ranges.isEmpty())
259 m_ranges.last().nextRangeIndex = 0;
260 }
261};
262
263} // namespace ContentExtensions
264} // namespace WebCore
265
266#endif // ENABLE(CONTENT_EXTENSIONS)
267