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

2 | // |

3 | // The LLVM Compiler Infrastructure |

4 | // |

5 | // This file is distributed under the University of Illinois Open Source |

6 | // License. See LICENSE.TXT for details. |

7 | // |

8 | //===----------------------------------------------------------------------===// |

9 | |

10 | #ifndef LLVM_ADT_ITERATOR_H |

11 | #define LLVM_ADT_ITERATOR_H |

12 | |

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

14 | #include <algorithm> |

15 | #include <cstddef> |

16 | #include <iterator> |

17 | #include <type_traits> |

18 | #include <utility> |

19 | |

20 | namespace llvm { |

21 | |

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

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

24 | /// |

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

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

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

28 | /// relevant members instead. |

29 | /// |

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

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

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

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

34 | /// boilerplate anyways. |

35 | /// |

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

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

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

39 | /// |

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

41 | /// methods: |

42 | /// |

43 | /// Forward Iterators: |

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

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

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

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

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

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

50 | /// |

51 | /// Bidirectional Iterators: |

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

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

54 | /// |

55 | /// Random-access Iterators: |

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

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

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

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

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

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

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

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

64 | /// |

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

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

67 | typename ReferenceT = T &> |

68 | class iterator_facade_base |

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

70 | ReferenceT> { |

71 | protected: |

72 | enum { |

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

74 | IteratorCategoryT>::value, |

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

76 | IteratorCategoryT>::value, |

77 | }; |

78 | |

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

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

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

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

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

84 | class ReferenceProxy { |

85 | friend iterator_facade_base; |

86 | |

87 | DerivedT I; |

88 | |

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

90 | |

91 | public: |

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

93 | }; |

94 | |

95 | public: |

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

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

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

99 | static_assert( |

100 | IsRandomAccess, |

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

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

103 | tmp += n; |

104 | return tmp; |

105 | } |

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

107 | static_assert( |

108 | IsRandomAccess, |

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

110 | return i + n; |

111 | } |

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

113 | static_assert( |

114 | IsRandomAccess, |

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

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

117 | tmp -= n; |

118 | return tmp; |

119 | } |

120 | |

121 | DerivedT &operator++() { |

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

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

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

125 | } |

126 | DerivedT operator++(int) { |

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

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

129 | return tmp; |

130 | } |

131 | DerivedT &operator--() { |

132 | static_assert( |

133 | IsBidirectional, |

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

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

136 | } |

137 | DerivedT operator--(int) { |

138 | static_assert( |

139 | IsBidirectional, |

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

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

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

143 | return tmp; |

144 | } |

145 | |

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

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

148 | } |

149 | |

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

151 | static_assert( |

152 | IsRandomAccess, |

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

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

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

156 | } |

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

158 | static_assert( |

159 | IsRandomAccess, |

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

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

162 | } |

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

164 | static_assert( |

165 | IsRandomAccess, |

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

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

168 | } |

169 | |

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

171 | PointerT operator->() const { |

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

173 | } |

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

175 | static_assert(IsRandomAccess, |

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

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

178 | } |

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

180 | static_assert(IsRandomAccess, |

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

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

183 | } |

184 | }; |

185 | |

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

187 | /// |

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

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

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

191 | template < |

192 | typename DerivedT, typename WrappedIteratorT, |

193 | typename IteratorCategoryT = |

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

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

196 | typename DifferenceTypeT = |

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

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

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

200 | WrappedIteratorT>::value_type>::value, |

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

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

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

204 | WrappedIteratorT>::value_type>::value, |

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

206 | class iterator_adaptor_base |

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

208 | DifferenceTypeT, PointerT, ReferenceT> { |

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

210 | |

211 | protected: |

212 | WrappedIteratorT I; |

213 | |

214 | iterator_adaptor_base() = default; |

215 | |

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

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

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

219 | } |

220 | |

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

222 | |

223 | public: |

224 | using difference_type = DifferenceTypeT; |

225 | |

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

227 | static_assert( |

228 | BaseT::IsRandomAccess, |

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

230 | I += n; |

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

232 | } |

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

234 | static_assert( |

235 | BaseT::IsRandomAccess, |

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

237 | I -= n; |

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

239 | } |

240 | using BaseT::operator-; |

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

242 | static_assert( |

243 | BaseT::IsRandomAccess, |

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

245 | return I - RHS.I; |

246 | } |

247 | |

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

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

250 | using BaseT::operator++; |

251 | DerivedT &operator++() { |

252 | ++I; |

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

254 | } |

255 | using BaseT::operator--; |

256 | DerivedT &operator--() { |

257 | static_assert( |

258 | BaseT::IsBidirectional, |

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

260 | --I; |

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

262 | } |

263 | |

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

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

266 | static_assert( |

267 | BaseT::IsRandomAccess, |

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

269 | return I < RHS.I; |

270 | } |

271 | |

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

273 | }; |

274 | |

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

276 | /// other iterator. |

277 | /// |

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

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

280 | /// |

281 | /// \code |

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

283 | /// \endcode |

284 | template <typename WrappedIteratorT, |

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

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

287 | struct pointee_iterator |

288 | : iterator_adaptor_base< |

289 | pointee_iterator<WrappedIteratorT, T>, WrappedIteratorT, |

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

291 | T> { |

292 | pointee_iterator() = default; |

293 | template <typename U> |

294 | pointee_iterator(U &&u) |

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

296 | |

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

298 | }; |

299 | |

300 | template <typename RangeT, typename WrappedIteratorT = |

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

302 | iterator_range<pointee_iterator<WrappedIteratorT>> |

303 | make_pointee_range(RangeT &&Range) { |

304 | using PointeeIteratorT = pointee_iterator<WrappedIteratorT>; |

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

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

307 | } |

308 | |

309 | template <typename WrappedIteratorT, |

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

311 | class pointer_iterator |

312 | : public iterator_adaptor_base< |

313 | pointer_iterator<WrappedIteratorT, T>, WrappedIteratorT, |

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

315 | T> { |

316 | mutable T Ptr; |

317 | |

318 | public: |

319 | pointer_iterator() = default; |

320 | |

321 | explicit pointer_iterator(WrappedIteratorT u) |

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

323 | |

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

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

326 | }; |

327 | |

328 | template <typename RangeT, typename WrappedIteratorT = |

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

330 | iterator_range<pointer_iterator<WrappedIteratorT>> |

331 | make_pointer_range(RangeT &&Range) { |

332 | using PointerIteratorT = pointer_iterator<WrappedIteratorT>; |

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

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

335 | } |

336 | |

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

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

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

340 | class WrappedPairNodeDataIterator |

341 | : public iterator_adaptor_base< |

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

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

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

345 | using BaseT = iterator_adaptor_base< |

346 | WrappedPairNodeDataIterator, ItType, |

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

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

349 | |

350 | const DataRef DR; |

351 | mutable NodeRef NR; |

352 | |

353 | public: |

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

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

356 | NR.first = DR; |

357 | } |

358 | |

359 | NodeRef &operator*() const { |

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

361 | return NR; |

362 | } |

363 | }; |

364 | |

365 | } // end namespace llvm |

366 | |

367 | #endif // LLVM_ADT_ITERATOR_H |

368 |