1/*
2 * Copyright (C) 2016 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. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#pragma once
27
28#include <wtf/ListDump.h>
29#include <wtf/MathExtras.h>
30#include <wtf/StdLibExtras.h>
31#include <wtf/Vector.h>
32
33namespace WTF {
34
35// A RangeSet is a set of numerical ranges. A value belongs to the set if it is within any of the
36// ranges. A range belongs to the set if every value in the range belongs to the set. A range overlaps
37// the set if any value in the range belongs to the set. You can add ranges and query range
38// membership. The internal representation is a list of ranges that gets periodically compacted. This
39// representation is optimal so long as the number of distinct ranges tends to be small, and the
40// number of range sets tends to be small as well. This works reasonably well in a bunch of compiler
41// algorithms, where the top range ends up being used a lot.
42//
43// The initial user of this is JSC::B3::HeapRange, which is used to perform alias analysis. You can
44// model new users on that class. Basically, you need to define:
45//
46// T::Type - the type of the members of the range. HeapRange uses unsigned.
47// T(T::Type begin, T::Type end) - construct a new range.
48// T::Type T::begin() const - instance method giving the inclusive beginning of the range.
49// T::Type T::end() const - instance method giving the exclusive end of the range.
50// void T::dump(PrintStream&) const - some kind of dumping.
51
52template<typename RangeType>
53class RangeSet {
54public:
55 typedef RangeType Range;
56 typedef typename Range::Type Type;
57
58 typedef Vector<Range, 8> VectorType;
59
60 RangeSet()
61 {
62 }
63
64 ~RangeSet()
65 {
66 }
67
68 void add(const Range& range)
69 {
70 if (range.begin() == range.end())
71 return;
72
73 // We expect the range set to become top in a lot of cases. We also expect the same range to
74 // be added repeatedly. That's why this is here.
75 if (!m_ranges.isEmpty() && subsumesNonEmpty(m_ranges.last(), range))
76 return;
77
78 m_isCompact = false;
79
80 // We append without compacting only if doing so is guaranteed not to resize the vector.
81 // FIXME: This heuristic is almost certainly wrong, because we don't control the capacity. I
82 // think that this means that we will sometimes be rage-compacting when we are just shy of the
83 // capacity.
84 // https://bugs.webkit.org/show_bug.cgi?id=170308
85 if (m_ranges.size() + 1 < m_ranges.capacity()) {
86 m_ranges.append(range);
87 return;
88 }
89
90 m_ranges.append(range);
91 compact();
92 }
93
94 bool contains(const Range& range) const
95 {
96 if (range.begin() == range.end())
97 return false;
98
99 unsigned index = findRange(range);
100 if (index != UINT_MAX)
101 return subsumesNonEmpty(m_ranges[index], range);
102 return false;
103 }
104
105 bool overlaps(const Range& range) const
106 {
107 if (range.begin() == range.end())
108 return false;
109
110 return findRange(range) != UINT_MAX;
111 }
112
113 void clear()
114 {
115 m_ranges.clear();
116 m_isCompact = true;
117 }
118
119 void dump(PrintStream& out) const
120 {
121 const_cast<RangeSet*>(this)->compact();
122 out.print(listDump(m_ranges));
123 }
124
125 void dumpRaw(PrintStream& out) const
126 {
127 out.print("{", listDump(m_ranges), ", isCompact = ", m_isCompact, "}");
128 }
129
130 typename VectorType::const_iterator begin() const
131 {
132 return m_ranges.begin();
133 }
134
135 typename VectorType::const_iterator end() const
136 {
137 return m_ranges.end();
138 }
139
140 void addAll(const RangeSet& other)
141 {
142 for (Range range : other)
143 add(range);
144 }
145
146 void compact()
147 {
148 if (m_isCompact)
149 return;
150
151 if (m_ranges.isEmpty()) {
152 m_isCompact = true;
153 return;
154 }
155
156 std::sort(
157 m_ranges.begin(), m_ranges.end(),
158 [&] (const Range& a, const Range& b) -> bool {
159 return a.begin() < b.begin();
160 });
161
162 unsigned srcIndex = 1;
163 unsigned dstIndex = 1;
164 Range* lastRange = &m_ranges[0];
165 while (srcIndex < m_ranges.size()) {
166 Range range = m_ranges[srcIndex++];
167 ASSERT(range.begin() >= lastRange->begin());
168 if (range.end() <= lastRange->end())
169 continue;
170 if (range.begin() <= lastRange->end()) {
171 *lastRange = Range(lastRange->begin(), range.end());
172 continue;
173 }
174 ASSERT(!overlapsNonEmpty(*lastRange, range));
175 lastRange = &m_ranges[dstIndex++];
176 *lastRange = range;
177 }
178 m_ranges.shrink(dstIndex);
179
180 m_isCompact = true;
181 }
182
183private:
184 static bool overlapsNonEmpty(const Range& a, const Range& b)
185 {
186 return nonEmptyRangesOverlap(a.begin(), a.end(), b.begin(), b.end());
187 }
188
189 static bool subsumesNonEmpty(const Range& a, const Range& b)
190 {
191 return a.begin() <= b.begin() && a.end() >= b.end();
192 }
193
194 unsigned findRange(const Range& range) const
195 {
196 const_cast<RangeSet*>(this)->compact();
197
198 // FIXME: Once we start using this in anger, we will want this to be a binary search.
199 for (unsigned i = 0; i < m_ranges.size(); ++i) {
200 if (overlapsNonEmpty(m_ranges[i], range))
201 return i;
202 }
203
204 return UINT_MAX;
205 }
206
207 VectorType m_ranges;
208 bool m_isCompact { true };
209};
210
211} // namespace WTF
212
213using WTF::RangeSet;
214