1 | //===- iterator.h - Utilities for using and defining iterators --*- C++ -*-===// |
---|---|

2 | // |

3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |

4 | // See https://llvm.org/LICENSE.txt for license information. |

5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |

6 | // |

7 | //===----------------------------------------------------------------------===// |

8 | |

9 | #ifndef LLVM_ADT_ITERATOR_H |

10 | #define LLVM_ADT_ITERATOR_H |

11 | |

12 | #include "llvm/ADT/iterator_range.h" |

13 | #include <algorithm> |

14 | #include <cstddef> |

15 | #include <iterator> |

16 | #include <type_traits> |

17 | #include <utility> |

18 | |

19 | namespace llvm { |

20 | |

21 | /// CRTP base class which implements the entire standard iterator facade |

22 | /// in terms of a minimal subset of the interface. |

23 | /// |

24 | /// Use this when it is reasonable to implement most of the iterator |

25 | /// functionality in terms of a core subset. If you need special behavior or |

26 | /// there are performance implications for this, you may want to override the |

27 | /// relevant members instead. |

28 | /// |

29 | /// Note, one abstraction that this does *not* provide is implementing |

30 | /// subtraction in terms of addition by negating the difference. Negation isn't |

31 | /// always information preserving, and I can see very reasonable iterator |

32 | /// designs where this doesn't work well. It doesn't really force much added |

33 | /// boilerplate anyways. |

34 | /// |

35 | /// Another abstraction that this doesn't provide is implementing increment in |

36 | /// terms of addition of one. These aren't equivalent for all iterator |

37 | /// categories, and respecting that adds a lot of complexity for little gain. |

38 | /// |

39 | /// Classes wishing to use `iterator_facade_base` should implement the following |

40 | /// methods: |

41 | /// |

42 | /// Forward Iterators: |

43 | /// (All of the following methods) |

44 | /// - DerivedT &operator=(const DerivedT &R); |

45 | /// - bool operator==(const DerivedT &R) const; |

46 | /// - const T &operator*() const; |

47 | /// - T &operator*(); |

48 | /// - DerivedT &operator++(); |

49 | /// |

50 | /// Bidirectional Iterators: |

51 | /// (All methods of forward iterators, plus the following) |

52 | /// - DerivedT &operator--(); |

53 | /// |

54 | /// Random-access Iterators: |

55 | /// (All methods of bidirectional iterators excluding the following) |

56 | /// - DerivedT &operator++(); |

57 | /// - DerivedT &operator--(); |

58 | /// (and plus the following) |

59 | /// - bool operator<(const DerivedT &RHS) const; |

60 | /// - DifferenceTypeT operator-(const DerivedT &R) const; |

61 | /// - DerivedT &operator+=(DifferenceTypeT N); |

62 | /// - DerivedT &operator-=(DifferenceTypeT N); |

63 | /// |

64 | template <typename DerivedT, typename IteratorCategoryT, typename T, |

65 | typename DifferenceTypeT = std::ptrdiff_t, typename PointerT = T *, |

66 | typename ReferenceT = T &> |

67 | class iterator_facade_base |

68 | : public std::iterator<IteratorCategoryT, T, DifferenceTypeT, PointerT, |

69 | ReferenceT> { |

70 | protected: |

71 | enum { |

72 | IsRandomAccess = std::is_base_of<std::random_access_iterator_tag, |

73 | IteratorCategoryT>::value, |

74 | IsBidirectional = std::is_base_of<std::bidirectional_iterator_tag, |

75 | IteratorCategoryT>::value, |

76 | }; |

77 | |

78 | /// A proxy object for computing a reference via indirecting a copy of an |

79 | /// iterator. This is used in APIs which need to produce a reference via |

80 | /// indirection but for which the iterator object might be a temporary. The |

81 | /// proxy preserves the iterator internally and exposes the indirected |

82 | /// reference via a conversion operator. |

83 | class ReferenceProxy { |

84 | friend iterator_facade_base; |

85 | |

86 | DerivedT I; |

87 | |

88 | ReferenceProxy(DerivedT I) : I(std::move(I)) {} |

89 | |

90 | public: |

91 | operator ReferenceT() const { return *I; } |

92 | }; |

93 | |

94 | public: |

95 | DerivedT operator+(DifferenceTypeT n) const { |

96 | static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value, |

97 | "Must pass the derived type to this template!"); |

98 | static_assert( |

99 | IsRandomAccess, |

100 | "The '+' operator is only defined for random access iterators."); |

101 | DerivedT tmp = *static_cast<const DerivedT *>(this); |

102 | tmp += n; |

103 | return tmp; |

104 | } |

105 | friend DerivedT operator+(DifferenceTypeT n, const DerivedT &i) { |

106 | static_assert( |

107 | IsRandomAccess, |

108 | "The '+' operator is only defined for random access iterators."); |

109 | return i + n; |

110 | } |

111 | DerivedT operator-(DifferenceTypeT n) const { |

112 | static_assert( |

113 | IsRandomAccess, |

114 | "The '-' operator is only defined for random access iterators."); |

115 | DerivedT tmp = *static_cast<const DerivedT *>(this); |

116 | tmp -= n; |

117 | return tmp; |

118 | } |

119 | |

120 | DerivedT &operator++() { |

121 | static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value, |

122 | "Must pass the derived type to this template!"); |

123 | return static_cast<DerivedT *>(this)->operator+=(1); |

124 | } |

125 | DerivedT operator++(int) { |

126 | DerivedT tmp = *static_cast<DerivedT *>(this); |

127 | ++*static_cast<DerivedT *>(this); |

128 | return tmp; |

129 | } |

130 | DerivedT &operator--() { |

131 | static_assert( |

132 | IsBidirectional, |

133 | "The decrement operator is only defined for bidirectional iterators."); |

134 | return static_cast<DerivedT *>(this)->operator-=(1); |

135 | } |

136 | DerivedT operator--(int) { |

137 | static_assert( |

138 | IsBidirectional, |

139 | "The decrement operator is only defined for bidirectional iterators."); |

140 | DerivedT tmp = *static_cast<DerivedT *>(this); |

141 | --*static_cast<DerivedT *>(this); |

142 | return tmp; |

143 | } |

144 | |

145 | bool operator!=(const DerivedT &RHS) const { |

146 | return !static_cast<const DerivedT *>(this)->operator==(RHS); |

147 | } |

148 | |

149 | bool operator>(const DerivedT &RHS) const { |

150 | static_assert( |

151 | IsRandomAccess, |

152 | "Relational operators are only defined for random access iterators."); |

153 | return !static_cast<const DerivedT *>(this)->operator<(RHS) && |

154 | !static_cast<const DerivedT *>(this)->operator==(RHS); |

155 | } |

156 | bool operator<=(const DerivedT &RHS) const { |

157 | static_assert( |

158 | IsRandomAccess, |

159 | "Relational operators are only defined for random access iterators."); |

160 | return !static_cast<const DerivedT *>(this)->operator>(RHS); |

161 | } |

162 | bool operator>=(const DerivedT &RHS) const { |

163 | static_assert( |

164 | IsRandomAccess, |

165 | "Relational operators are only defined for random access iterators."); |

166 | return !static_cast<const DerivedT *>(this)->operator<(RHS); |

167 | } |

168 | |

169 | PointerT operator->() { return &static_cast<DerivedT *>(this)->operator*(); } |

170 | PointerT operator->() const { |

171 | return &static_cast<const DerivedT *>(this)->operator*(); |

172 | } |

173 | ReferenceProxy operator[](DifferenceTypeT n) { |

174 | static_assert(IsRandomAccess, |

175 | "Subscripting is only defined for random access iterators."); |

176 | return ReferenceProxy(static_cast<DerivedT *>(this)->operator+(n)); |

177 | } |

178 | ReferenceProxy operator[](DifferenceTypeT n) const { |

179 | static_assert(IsRandomAccess, |

180 | "Subscripting is only defined for random access iterators."); |

181 | return ReferenceProxy(static_cast<const DerivedT *>(this)->operator+(n)); |

182 | } |

183 | }; |

184 | |

185 | /// CRTP base class for adapting an iterator to a different type. |

186 | /// |

187 | /// This class can be used through CRTP to adapt one iterator into another. |

188 | /// Typically this is done through providing in the derived class a custom \c |

189 | /// operator* implementation. Other methods can be overridden as well. |

190 | template < |

191 | typename DerivedT, typename WrappedIteratorT, |

192 | typename IteratorCategoryT = |

193 | typename std::iterator_traits<WrappedIteratorT>::iterator_category, |

194 | typename T = typename std::iterator_traits<WrappedIteratorT>::value_type, |

195 | typename DifferenceTypeT = |

196 | typename std::iterator_traits<WrappedIteratorT>::difference_type, |

197 | typename PointerT = typename std::conditional< |

198 | std::is_same<T, typename std::iterator_traits< |

199 | WrappedIteratorT>::value_type>::value, |

200 | typename std::iterator_traits<WrappedIteratorT>::pointer, T *>::type, |

201 | typename ReferenceT = typename std::conditional< |

202 | std::is_same<T, typename std::iterator_traits< |

203 | WrappedIteratorT>::value_type>::value, |

204 | typename std::iterator_traits<WrappedIteratorT>::reference, T &>::type> |

205 | class iterator_adaptor_base |

206 | : public iterator_facade_base<DerivedT, IteratorCategoryT, T, |

207 | DifferenceTypeT, PointerT, ReferenceT> { |

208 | using BaseT = typename iterator_adaptor_base::iterator_facade_base; |

209 | |

210 | protected: |

211 | WrappedIteratorT I; |

212 | |

213 | iterator_adaptor_base() = default; |

214 | |

215 | explicit iterator_adaptor_base(WrappedIteratorT u) : I(std::move(u)) { |

216 | static_assert(std::is_base_of<iterator_adaptor_base, DerivedT>::value, |

217 | "Must pass the derived type to this template!"); |

218 | } |

219 | |

220 | const WrappedIteratorT &wrapped() const { return I; } |

221 | |

222 | public: |

223 | using difference_type = DifferenceTypeT; |

224 | |

225 | DerivedT &operator+=(difference_type n) { |

226 | static_assert( |

227 | BaseT::IsRandomAccess, |

228 | "The '+=' operator is only defined for random access iterators."); |

229 | I += n; |

230 | return *static_cast<DerivedT *>(this); |

231 | } |

232 | DerivedT &operator-=(difference_type n) { |

233 | static_assert( |

234 | BaseT::IsRandomAccess, |

235 | "The '-=' operator is only defined for random access iterators."); |

236 | I -= n; |

237 | return *static_cast<DerivedT *>(this); |

238 | } |

239 | using BaseT::operator-; |

240 | difference_type operator-(const DerivedT &RHS) const { |

241 | static_assert( |

242 | BaseT::IsRandomAccess, |

243 | "The '-' operator is only defined for random access iterators."); |

244 | return I - RHS.I; |

245 | } |

246 | |

247 | // We have to explicitly provide ++ and -- rather than letting the facade |

248 | // forward to += because WrappedIteratorT might not support +=. |

249 | using BaseT::operator++; |

250 | DerivedT &operator++() { |

251 | ++I; |

252 | return *static_cast<DerivedT *>(this); |

253 | } |

254 | using BaseT::operator--; |

255 | DerivedT &operator--() { |

256 | static_assert( |

257 | BaseT::IsBidirectional, |

258 | "The decrement operator is only defined for bidirectional iterators."); |

259 | --I; |

260 | return *static_cast<DerivedT *>(this); |

261 | } |

262 | |

263 | bool operator==(const DerivedT &RHS) const { return I == RHS.I; } |

264 | bool operator<(const DerivedT &RHS) const { |

265 | static_assert( |

266 | BaseT::IsRandomAccess, |

267 | "Relational operators are only defined for random access iterators."); |

268 | return I < RHS.I; |

269 | } |

270 | |

271 | ReferenceT operator*() const { return *I; } |

272 | }; |

273 | |

274 | /// An iterator type that allows iterating over the pointees via some |

275 | /// other iterator. |

276 | /// |

277 | /// The typical usage of this is to expose a type that iterates over Ts, but |

278 | /// which is implemented with some iterator over T*s: |

279 | /// |

280 | /// \code |

281 | /// using iterator = pointee_iterator<SmallVectorImpl<T *>::iterator>; |

282 | /// \endcode |

283 | template <typename WrappedIteratorT, |

284 | typename T = typename std::remove_reference< |

285 | decltype(**std::declval<WrappedIteratorT>())>::type> |

286 | struct pointee_iterator |

287 | : iterator_adaptor_base< |

288 | pointee_iterator<WrappedIteratorT, T>, WrappedIteratorT, |

289 | typename std::iterator_traits<WrappedIteratorT>::iterator_category, |

290 | T> { |

291 | pointee_iterator() = default; |

292 | template <typename U> |

293 | pointee_iterator(U &&u) |

294 | : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {} |

295 | |

296 | T &operator*() const { return **this->I; } |

297 | }; |

298 | |

299 | template <typename RangeT, typename WrappedIteratorT = |

300 | decltype(std::begin(std::declval<RangeT>()))> |

301 | iterator_range<pointee_iterator<WrappedIteratorT>> |

302 | make_pointee_range(RangeT &&Range) { |

303 | using PointeeIteratorT = pointee_iterator<WrappedIteratorT>; |

304 | return make_range(PointeeIteratorT(std::begin(std::forward<RangeT>(Range))), |

305 | PointeeIteratorT(std::end(std::forward<RangeT>(Range)))); |

306 | } |

307 | |

308 | template <typename WrappedIteratorT, |

309 | typename T = decltype(&*std::declval<WrappedIteratorT>())> |

310 | class pointer_iterator |

311 | : public iterator_adaptor_base< |

312 | pointer_iterator<WrappedIteratorT, T>, WrappedIteratorT, |

313 | typename std::iterator_traits<WrappedIteratorT>::iterator_category, |

314 | T> { |

315 | mutable T Ptr; |

316 | |

317 | public: |

318 | pointer_iterator() = default; |

319 | |

320 | explicit pointer_iterator(WrappedIteratorT u) |

321 | : pointer_iterator::iterator_adaptor_base(std::move(u)) {} |

322 | |

323 | T &operator*() { return Ptr = &*this->I; } |

324 | const T &operator*() const { return Ptr = &*this->I; } |

325 | }; |

326 | |

327 | template <typename RangeT, typename WrappedIteratorT = |

328 | decltype(std::begin(std::declval<RangeT>()))> |

329 | iterator_range<pointer_iterator<WrappedIteratorT>> |

330 | make_pointer_range(RangeT &&Range) { |

331 | using PointerIteratorT = pointer_iterator<WrappedIteratorT>; |

332 | return make_range(PointerIteratorT(std::begin(std::forward<RangeT>(Range))), |

333 | PointerIteratorT(std::end(std::forward<RangeT>(Range)))); |

334 | } |

335 | |

336 | // Wrapper iterator over iterator ItType, adding DataRef to the type of ItType, |

337 | // to create NodeRef = std::pair<InnerTypeOfItType, DataRef>. |

338 | template <typename ItType, typename NodeRef, typename DataRef> |

339 | class WrappedPairNodeDataIterator |

340 | : public iterator_adaptor_base< |

341 | WrappedPairNodeDataIterator<ItType, NodeRef, DataRef>, ItType, |

342 | typename std::iterator_traits<ItType>::iterator_category, NodeRef, |

343 | std::ptrdiff_t, NodeRef *, NodeRef &> { |

344 | using BaseT = iterator_adaptor_base< |

345 | WrappedPairNodeDataIterator, ItType, |

346 | typename std::iterator_traits<ItType>::iterator_category, NodeRef, |

347 | std::ptrdiff_t, NodeRef *, NodeRef &>; |

348 | |

349 | const DataRef DR; |

350 | mutable NodeRef NR; |

351 | |

352 | public: |

353 | WrappedPairNodeDataIterator(ItType Begin, const DataRef DR) |

354 | : BaseT(Begin), DR(DR) { |

355 | NR.first = DR; |

356 | } |

357 | |

358 | NodeRef &operator*() const { |

359 | NR.second = *this->I; |

360 | return NR; |

361 | } |

362 | }; |

363 | |

364 | } // end namespace llvm |

365 | |

366 | #endif // LLVM_ADT_ITERATOR_H |

367 |