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 <cstddef> |

14 | #include <iterator> |

15 | #include <type_traits> |

16 | #include <utility> |

17 | |

18 | namespace llvm { |

19 | |

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

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

22 | /// |

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

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

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

26 | /// relevant members instead. |

27 | /// |

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

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

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

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

32 | /// boilerplate anyways. |

33 | /// |

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

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

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

37 | /// |

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

39 | /// methods: |

40 | /// |

41 | /// Forward Iterators: |

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

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

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

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

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

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

48 | /// |

49 | /// Bidirectional Iterators: |

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

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

52 | /// |

53 | /// Random-access Iterators: |

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

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

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

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

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

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

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

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

62 | /// |

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

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

65 | typename ReferenceT = T &> |

66 | class iterator_facade_base { |

67 | public: |

68 | using iterator_category = IteratorCategoryT; |

69 | using value_type = T; |

70 | using difference_type = DifferenceTypeT; |

71 | using pointer = PointerT; |

72 | using reference = ReferenceT; |

73 | |

74 | protected: |

75 | enum { |

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

77 | IteratorCategoryT>::value, |

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

79 | IteratorCategoryT>::value, |

80 | }; |

81 | |

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

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

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

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

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

87 | class ReferenceProxy { |

88 | friend iterator_facade_base; |

89 | |

90 | DerivedT I; |

91 | |

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

93 | |

94 | public: |

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

96 | }; |

97 | |

98 | public: |

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

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

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

102 | static_assert( |

103 | IsRandomAccess, |

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

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

106 | tmp += n; |

107 | return tmp; |

108 | } |

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

110 | static_assert( |

111 | IsRandomAccess, |

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

113 | return i + n; |

114 | } |

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

116 | static_assert( |

117 | IsRandomAccess, |

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

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

120 | tmp -= n; |

121 | return tmp; |

122 | } |

123 | |

124 | DerivedT &operator++() { |

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

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

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

128 | } |

129 | DerivedT operator++(int) { |

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

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

132 | return tmp; |

133 | } |

134 | DerivedT &operator--() { |

135 | static_assert( |

136 | IsBidirectional, |

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

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

139 | } |

140 | DerivedT operator--(int) { |

141 | static_assert( |

142 | IsBidirectional, |

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

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

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

146 | return tmp; |

147 | } |

148 | |

149 | #ifndef __cpp_impl_three_way_comparison |

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

151 | return !(static_cast<const DerivedT &>(*this) == RHS); |

152 | } |

153 | #endif |

154 | |

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

156 | static_assert( |

157 | IsRandomAccess, |

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

159 | return !(static_cast<const DerivedT &>(*this) < RHS) && |

160 | !(static_cast<const DerivedT &>(*this) == 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) > RHS); |

167 | } |

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

169 | static_assert( |

170 | IsRandomAccess, |

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

172 | return !(static_cast<const DerivedT &>(*this) < RHS); |

173 | } |

174 | |

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

176 | PointerT operator->() const { |

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

178 | } |

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

180 | static_assert(IsRandomAccess, |

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

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

183 | } |

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

185 | static_assert(IsRandomAccess, |

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

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

188 | } |

189 | }; |

190 | |

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

192 | /// |

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

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

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

196 | template < |

197 | typename DerivedT, typename WrappedIteratorT, |

198 | typename IteratorCategoryT = |

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

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

201 | typename DifferenceTypeT = |

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

203 | typename PointerT = std::conditional_t< |

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

205 | WrappedIteratorT>::value_type>::value, |

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

207 | typename ReferenceT = std::conditional_t< |

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

209 | WrappedIteratorT>::value_type>::value, |

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

211 | class iterator_adaptor_base |

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

213 | DifferenceTypeT, PointerT, ReferenceT> { |

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

215 | |

216 | protected: |

217 | WrappedIteratorT I; |

218 | |

219 | iterator_adaptor_base() = default; |

220 | |

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

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

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

224 | } |

225 | |

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

227 | |

228 | public: |

229 | using difference_type = DifferenceTypeT; |

230 | |

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

232 | static_assert( |

233 | BaseT::IsRandomAccess, |

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

235 | I += n; |

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

237 | } |

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

239 | static_assert( |

240 | BaseT::IsRandomAccess, |

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

242 | I -= n; |

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

244 | } |

245 | using BaseT::operator-; |

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

247 | static_assert( |

248 | BaseT::IsRandomAccess, |

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

250 | return I - RHS.I; |

251 | } |

252 | |

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

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

255 | using BaseT::operator++; |

256 | DerivedT &operator++() { |

257 | ++I; |

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

259 | } |

260 | using BaseT::operator--; |

261 | DerivedT &operator--() { |

262 | static_assert( |

263 | BaseT::IsBidirectional, |

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

265 | --I; |

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

267 | } |

268 | |

269 | friend bool operator==(const iterator_adaptor_base &LHS, |

270 | const iterator_adaptor_base &RHS) { |

271 | return LHS.I == RHS.I; |

272 | } |

273 | friend bool operator<(const iterator_adaptor_base &LHS, |

274 | const iterator_adaptor_base &RHS) { |

275 | static_assert( |

276 | BaseT::IsRandomAccess, |

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

278 | return LHS.I < RHS.I; |

279 | } |

280 | |

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

282 | }; |

283 | |

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

285 | /// other iterator. |

286 | /// |

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

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

289 | /// |

290 | /// \code |

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

292 | /// \endcode |

293 | template <typename WrappedIteratorT, |

294 | typename T = std::remove_reference_t<decltype( |

295 | **std::declval<WrappedIteratorT>())>> |

296 | struct pointee_iterator |

297 | : iterator_adaptor_base< |

298 | pointee_iterator<WrappedIteratorT, T>, WrappedIteratorT, |

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

300 | T> { |

301 | pointee_iterator() = default; |

302 | template <typename U> |

303 | pointee_iterator(U &&u) |

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

305 | |

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

307 | }; |

308 | |

309 | template <typename RangeT, typename WrappedIteratorT = |

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

311 | iterator_range<pointee_iterator<WrappedIteratorT>> |

312 | make_pointee_range(RangeT &&Range) { |

313 | using PointeeIteratorT = pointee_iterator<WrappedIteratorT>; |

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

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

316 | } |

317 | |

318 | template <typename WrappedIteratorT, |

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

320 | class pointer_iterator |

321 | : public iterator_adaptor_base< |

322 | pointer_iterator<WrappedIteratorT, T>, WrappedIteratorT, |

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

324 | T> { |

325 | mutable T Ptr; |

326 | |

327 | public: |

328 | pointer_iterator() = default; |

329 | |

330 | explicit pointer_iterator(WrappedIteratorT u) |

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

332 | |

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

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

335 | }; |

336 | |

337 | template <typename RangeT, typename WrappedIteratorT = |

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

339 | iterator_range<pointer_iterator<WrappedIteratorT>> |

340 | make_pointer_range(RangeT &&Range) { |

341 | using PointerIteratorT = pointer_iterator<WrappedIteratorT>; |

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

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

344 | } |

345 | |

346 | template <typename WrappedIteratorT, |

347 | typename T1 = std::remove_reference_t<decltype( |

348 | **std::declval<WrappedIteratorT>())>, |

349 | typename T2 = std::add_pointer_t<T1>> |

350 | using raw_pointer_iterator = |

351 | pointer_iterator<pointee_iterator<WrappedIteratorT, T1>, T2>; |

352 | |

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

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

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

356 | class WrappedPairNodeDataIterator |

357 | : public iterator_adaptor_base< |

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

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

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

361 | using BaseT = iterator_adaptor_base< |

362 | WrappedPairNodeDataIterator, ItType, |

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

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

365 | |

366 | const DataRef DR; |

367 | mutable NodeRef NR; |

368 | |

369 | public: |

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

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

372 | NR.first = DR; |

373 | } |

374 | |

375 | NodeRef &operator*() const { |

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

377 | return NR; |

378 | } |

379 | }; |

380 | |

381 | } // end namespace llvm |

382 | |

383 | #endif // LLVM_ADT_ITERATOR_H |

384 |