1 | //===- ArrayRef.h - Array Reference Wrapper ---------------------*- 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_ARRAYREF_H |

10 | #define LLVM_ADT_ARRAYREF_H |

11 | |

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

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

14 | #include "llvm/ADT/SmallVector.h" |

15 | #include "llvm/ADT/STLExtras.h" |

16 | #include "llvm/Support/Compiler.h" |

17 | #include <algorithm> |

18 | #include <array> |

19 | #include <cassert> |

20 | #include <cstddef> |

21 | #include <initializer_list> |

22 | #include <iterator> |

23 | #include <memory> |

24 | #include <type_traits> |

25 | #include <vector> |

26 | |

27 | namespace llvm { |

28 | |

29 | /// ArrayRef - Represent a constant reference to an array (0 or more elements |

30 | /// consecutively in memory), i.e. a start pointer and a length. It allows |

31 | /// various APIs to take consecutive elements easily and conveniently. |

32 | /// |

33 | /// This class does not own the underlying data, it is expected to be used in |

34 | /// situations where the data resides in some other buffer, whose lifetime |

35 | /// extends past that of the ArrayRef. For this reason, it is not in general |

36 | /// safe to store an ArrayRef. |

37 | /// |

38 | /// This is intended to be trivially copyable, so it should be passed by |

39 | /// value. |

40 | template<typename T> |

41 | class LLVM_NODISCARD ArrayRef { |

42 | public: |

43 | using iterator = const T *; |

44 | using const_iterator = const T *; |

45 | using size_type = size_t; |

46 | using reverse_iterator = std::reverse_iterator<iterator>; |

47 | |

48 | private: |

49 | /// The start of the array, in an external buffer. |

50 | const T *Data = nullptr; |

51 | |

52 | /// The number of elements. |

53 | size_type Length = 0; |

54 | |

55 | public: |

56 | /// @name Constructors |

57 | /// @{ |

58 | |

59 | /// Construct an empty ArrayRef. |

60 | /*implicit*/ ArrayRef() = default; |

61 | |

62 | /// Construct an empty ArrayRef from None. |

63 | /*implicit*/ ArrayRef(NoneType) {} |

64 | |

65 | /// Construct an ArrayRef from a single element. |

66 | /*implicit*/ ArrayRef(const T &OneElt) |

67 | : Data(&OneElt), Length(1) {} |

68 | |

69 | /// Construct an ArrayRef from a pointer and length. |

70 | /*implicit*/ ArrayRef(const T *data, size_t length) |

71 | : Data(data), Length(length) {} |

72 | |

73 | /// Construct an ArrayRef from a range. |

74 | ArrayRef(const T *begin, const T *end) |

75 | : Data(begin), Length(end - begin) {} |

76 | |

77 | /// Construct an ArrayRef from a SmallVector. This is templated in order to |

78 | /// avoid instantiating SmallVectorTemplateCommon<T> whenever we |

79 | /// copy-construct an ArrayRef. |

80 | template<typename U> |

81 | /*implicit*/ ArrayRef(const SmallVectorTemplateCommon<T, U> &Vec) |

82 | : Data(Vec.data()), Length(Vec.size()) { |

83 | } |

84 | |

85 | /// Construct an ArrayRef from a std::vector. |

86 | template<typename A> |

87 | /*implicit*/ ArrayRef(const std::vector<T, A> &Vec) |

88 | : Data(Vec.data()), Length(Vec.size()) {} |

89 | |

90 | /// Construct an ArrayRef from a std::array |

91 | template <size_t N> |

92 | /*implicit*/ constexpr ArrayRef(const std::array<T, N> &Arr) |

93 | : Data(Arr.data()), Length(N) {} |

94 | |

95 | /// Construct an ArrayRef from a C array. |

96 | template <size_t N> |

97 | /*implicit*/ constexpr ArrayRef(const T (&Arr)[N]) : Data(Arr), Length(N) {} |

98 | |

99 | /// Construct an ArrayRef from a std::initializer_list. |

100 | /*implicit*/ ArrayRef(const std::initializer_list<T> &Vec) |

101 | : Data(Vec.begin() == Vec.end() ? (T*)nullptr : Vec.begin()), |

102 | Length(Vec.size()) {} |

103 | |

104 | /// Construct an ArrayRef<const T*> from ArrayRef<T*>. This uses SFINAE to |

105 | /// ensure that only ArrayRefs of pointers can be converted. |

106 | template <typename U> |

107 | ArrayRef( |

108 | const ArrayRef<U *> &A, |

109 | typename std::enable_if< |

110 | std::is_convertible<U *const *, T const *>::value>::type * = nullptr) |

111 | : Data(A.data()), Length(A.size()) {} |

112 | |

113 | /// Construct an ArrayRef<const T*> from a SmallVector<T*>. This is |

114 | /// templated in order to avoid instantiating SmallVectorTemplateCommon<T> |

115 | /// whenever we copy-construct an ArrayRef. |

116 | template<typename U, typename DummyT> |

117 | /*implicit*/ ArrayRef( |

118 | const SmallVectorTemplateCommon<U *, DummyT> &Vec, |

119 | typename std::enable_if< |

120 | std::is_convertible<U *const *, T const *>::value>::type * = nullptr) |

121 | : Data(Vec.data()), Length(Vec.size()) { |

122 | } |

123 | |

124 | /// Construct an ArrayRef<const T*> from std::vector<T*>. This uses SFINAE |

125 | /// to ensure that only vectors of pointers can be converted. |

126 | template<typename U, typename A> |

127 | ArrayRef(const std::vector<U *, A> &Vec, |

128 | typename std::enable_if< |

129 | std::is_convertible<U *const *, T const *>::value>::type* = 0) |

130 | : Data(Vec.data()), Length(Vec.size()) {} |

131 | |

132 | /// @} |

133 | /// @name Simple Operations |

134 | /// @{ |

135 | |

136 | iterator begin() const { return Data; } |

137 | iterator end() const { return Data + Length; } |

138 | |

139 | reverse_iterator rbegin() const { return reverse_iterator(end()); } |

140 | reverse_iterator rend() const { return reverse_iterator(begin()); } |

141 | |

142 | /// empty - Check if the array is empty. |

143 | bool empty() const { return Length == 0; } |

144 | |

145 | const T *data() const { return Data; } |

146 | |

147 | /// size - Get the array size. |

148 | size_t size() const { return Length; } |

149 | |

150 | /// front - Get the first element. |

151 | const T &front() const { |

152 | assert(!empty()); |

153 | return Data[0]; |

154 | } |

155 | |

156 | /// back - Get the last element. |

157 | const T &back() const { |

158 | assert(!empty()); |

159 | return Data[Length-1]; |

160 | } |

161 | |

162 | // copy - Allocate copy in Allocator and return ArrayRef<T> to it. |

163 | template <typename Allocator> ArrayRef<T> copy(Allocator &A) { |

164 | T *Buff = A.template Allocate<T>(Length); |

165 | std::uninitialized_copy(begin(), end(), Buff); |

166 | return ArrayRef<T>(Buff, Length); |

167 | } |

168 | |

169 | /// equals - Check for element-wise equality. |

170 | bool equals(ArrayRef RHS) const { |

171 | if (Length != RHS.Length) |

172 | return false; |

173 | return std::equal(begin(), end(), RHS.begin()); |

174 | } |

175 | |

176 | /// slice(n, m) - Chop off the first N elements of the array, and keep M |

177 | /// elements in the array. |

178 | ArrayRef<T> slice(size_t N, size_t M) const { |

179 | assert(N+M <= size() && "Invalid specifier"); |

180 | return ArrayRef<T>(data()+N, M); |

181 | } |

182 | |

183 | /// slice(n) - Chop off the first N elements of the array. |

184 | ArrayRef<T> slice(size_t N) const { return slice(N, size() - N); } |

185 | |

186 | /// Drop the first \p N elements of the array. |

187 | ArrayRef<T> drop_front(size_t N = 1) const { |

188 | assert(size() >= N && "Dropping more elements than exist"); |

189 | return slice(N, size() - N); |

190 | } |

191 | |

192 | /// Drop the last \p N elements of the array. |

193 | ArrayRef<T> drop_back(size_t N = 1) const { |

194 | assert(size() >= N && "Dropping more elements than exist"); |

195 | return slice(0, size() - N); |

196 | } |

197 | |

198 | /// Return a copy of *this with the first N elements satisfying the |

199 | /// given predicate removed. |

200 | template <class PredicateT> ArrayRef<T> drop_while(PredicateT Pred) const { |

201 | return ArrayRef<T>(find_if_not(*this, Pred), end()); |

202 | } |

203 | |

204 | /// Return a copy of *this with the first N elements not satisfying |

205 | /// the given predicate removed. |

206 | template <class PredicateT> ArrayRef<T> drop_until(PredicateT Pred) const { |

207 | return ArrayRef<T>(find_if(*this, Pred), end()); |

208 | } |

209 | |

210 | /// Return a copy of *this with only the first \p N elements. |

211 | ArrayRef<T> take_front(size_t N = 1) const { |

212 | if (N >= size()) |

213 | return *this; |

214 | return drop_back(size() - N); |

215 | } |

216 | |

217 | /// Return a copy of *this with only the last \p N elements. |

218 | ArrayRef<T> take_back(size_t N = 1) const { |

219 | if (N >= size()) |

220 | return *this; |

221 | return drop_front(size() - N); |

222 | } |

223 | |

224 | /// Return the first N elements of this Array that satisfy the given |

225 | /// predicate. |

226 | template <class PredicateT> ArrayRef<T> take_while(PredicateT Pred) const { |

227 | return ArrayRef<T>(begin(), find_if_not(*this, Pred)); |

228 | } |

229 | |

230 | /// Return the first N elements of this Array that don't satisfy the |

231 | /// given predicate. |

232 | template <class PredicateT> ArrayRef<T> take_until(PredicateT Pred) const { |

233 | return ArrayRef<T>(begin(), find_if(*this, Pred)); |

234 | } |

235 | |

236 | /// @} |

237 | /// @name Operator Overloads |

238 | /// @{ |

239 | const T &operator[](size_t Index) const { |

240 | assert(Index < Length && "Invalid index!"); |

241 | return Data[Index]; |

242 | } |

243 | |

244 | /// Disallow accidental assignment from a temporary. |

245 | /// |

246 | /// The declaration here is extra complicated so that "arrayRef = {}" |

247 | /// continues to select the move assignment operator. |

248 | template <typename U> |

249 | typename std::enable_if<std::is_same<U, T>::value, ArrayRef<T>>::type & |

250 | operator=(U &&Temporary) = delete; |

251 | |

252 | /// Disallow accidental assignment from a temporary. |

253 | /// |

254 | /// The declaration here is extra complicated so that "arrayRef = {}" |

255 | /// continues to select the move assignment operator. |

256 | template <typename U> |

257 | typename std::enable_if<std::is_same<U, T>::value, ArrayRef<T>>::type & |

258 | operator=(std::initializer_list<U>) = delete; |

259 | |

260 | /// @} |

261 | /// @name Expensive Operations |

262 | /// @{ |

263 | std::vector<T> vec() const { |

264 | return std::vector<T>(Data, Data+Length); |

265 | } |

266 | |

267 | /// @} |

268 | /// @name Conversion operators |

269 | /// @{ |

270 | operator std::vector<T>() const { |

271 | return std::vector<T>(Data, Data+Length); |

272 | } |

273 | |

274 | /// @} |

275 | }; |

276 | |

277 | /// MutableArrayRef - Represent a mutable reference to an array (0 or more |

278 | /// elements consecutively in memory), i.e. a start pointer and a length. It |

279 | /// allows various APIs to take and modify consecutive elements easily and |

280 | /// conveniently. |

281 | /// |

282 | /// This class does not own the underlying data, it is expected to be used in |

283 | /// situations where the data resides in some other buffer, whose lifetime |

284 | /// extends past that of the MutableArrayRef. For this reason, it is not in |

285 | /// general safe to store a MutableArrayRef. |

286 | /// |

287 | /// This is intended to be trivially copyable, so it should be passed by |

288 | /// value. |

289 | template<typename T> |

290 | class LLVM_NODISCARD MutableArrayRef : public ArrayRef<T> { |

291 | public: |

292 | using iterator = T *; |

293 | using reverse_iterator = std::reverse_iterator<iterator>; |

294 | |

295 | /// Construct an empty MutableArrayRef. |

296 | /*implicit*/ MutableArrayRef() = default; |

297 | |

298 | /// Construct an empty MutableArrayRef from None. |

299 | /*implicit*/ MutableArrayRef(NoneType) : ArrayRef<T>() {} |

300 | |

301 | /// Construct an MutableArrayRef from a single element. |

302 | /*implicit*/ MutableArrayRef(T &OneElt) : ArrayRef<T>(OneElt) {} |

303 | |

304 | /// Construct an MutableArrayRef from a pointer and length. |

305 | /*implicit*/ MutableArrayRef(T *data, size_t length) |

306 | : ArrayRef<T>(data, length) {} |

307 | |

308 | /// Construct an MutableArrayRef from a range. |

309 | MutableArrayRef(T *begin, T *end) : ArrayRef<T>(begin, end) {} |

310 | |

311 | /// Construct an MutableArrayRef from a SmallVector. |

312 | /*implicit*/ MutableArrayRef(SmallVectorImpl<T> &Vec) |

313 | : ArrayRef<T>(Vec) {} |

314 | |

315 | /// Construct a MutableArrayRef from a std::vector. |

316 | /*implicit*/ MutableArrayRef(std::vector<T> &Vec) |

317 | : ArrayRef<T>(Vec) {} |

318 | |

319 | /// Construct an ArrayRef from a std::array |

320 | template <size_t N> |

321 | /*implicit*/ constexpr MutableArrayRef(std::array<T, N> &Arr) |

322 | : ArrayRef<T>(Arr) {} |

323 | |

324 | /// Construct an MutableArrayRef from a C array. |

325 | template <size_t N> |

326 | /*implicit*/ constexpr MutableArrayRef(T (&Arr)[N]) : ArrayRef<T>(Arr) {} |

327 | |

328 | T *data() const { return const_cast<T*>(ArrayRef<T>::data()); } |

329 | |

330 | iterator begin() const { return data(); } |

331 | iterator end() const { return data() + this->size(); } |

332 | |

333 | reverse_iterator rbegin() const { return reverse_iterator(end()); } |

334 | reverse_iterator rend() const { return reverse_iterator(begin()); } |

335 | |

336 | /// front - Get the first element. |

337 | T &front() const { |

338 | assert(!this->empty()); |

339 | return data()[0]; |

340 | } |

341 | |

342 | /// back - Get the last element. |

343 | T &back() const { |

344 | assert(!this->empty()); |

345 | return data()[this->size()-1]; |

346 | } |

347 | |

348 | /// slice(n, m) - Chop off the first N elements of the array, and keep M |

349 | /// elements in the array. |

350 | MutableArrayRef<T> slice(size_t N, size_t M) const { |

351 | assert(N + M <= this->size() && "Invalid specifier"); |

352 | return MutableArrayRef<T>(this->data() + N, M); |

353 | } |

354 | |

355 | /// slice(n) - Chop off the first N elements of the array. |

356 | MutableArrayRef<T> slice(size_t N) const { |

357 | return slice(N, this->size() - N); |

358 | } |

359 | |

360 | /// Drop the first \p N elements of the array. |

361 | MutableArrayRef<T> drop_front(size_t N = 1) const { |

362 | assert(this->size() >= N && "Dropping more elements than exist"); |

363 | return slice(N, this->size() - N); |

364 | } |

365 | |

366 | MutableArrayRef<T> drop_back(size_t N = 1) const { |

367 | assert(this->size() >= N && "Dropping more elements than exist"); |

368 | return slice(0, this->size() - N); |

369 | } |

370 | |

371 | /// Return a copy of *this with the first N elements satisfying the |

372 | /// given predicate removed. |

373 | template <class PredicateT> |

374 | MutableArrayRef<T> drop_while(PredicateT Pred) const { |

375 | return MutableArrayRef<T>(find_if_not(*this, Pred), end()); |

376 | } |

377 | |

378 | /// Return a copy of *this with the first N elements not satisfying |

379 | /// the given predicate removed. |

380 | template <class PredicateT> |

381 | MutableArrayRef<T> drop_until(PredicateT Pred) const { |

382 | return MutableArrayRef<T>(find_if(*this, Pred), end()); |

383 | } |

384 | |

385 | /// Return a copy of *this with only the first \p N elements. |

386 | MutableArrayRef<T> take_front(size_t N = 1) const { |

387 | if (N >= this->size()) |

388 | return *this; |

389 | return drop_back(this->size() - N); |

390 | } |

391 | |

392 | /// Return a copy of *this with only the last \p N elements. |

393 | MutableArrayRef<T> take_back(size_t N = 1) const { |

394 | if (N >= this->size()) |

395 | return *this; |

396 | return drop_front(this->size() - N); |

397 | } |

398 | |

399 | /// Return the first N elements of this Array that satisfy the given |

400 | /// predicate. |

401 | template <class PredicateT> |

402 | MutableArrayRef<T> take_while(PredicateT Pred) const { |

403 | return MutableArrayRef<T>(begin(), find_if_not(*this, Pred)); |

404 | } |

405 | |

406 | /// Return the first N elements of this Array that don't satisfy the |

407 | /// given predicate. |

408 | template <class PredicateT> |

409 | MutableArrayRef<T> take_until(PredicateT Pred) const { |

410 | return MutableArrayRef<T>(begin(), find_if(*this, Pred)); |

411 | } |

412 | |

413 | /// @} |

414 | /// @name Operator Overloads |

415 | /// @{ |

416 | T &operator[](size_t Index) const { |

417 | assert(Index < this->size() && "Invalid index!"); |

418 | return data()[Index]; |

419 | } |

420 | }; |

421 | |

422 | /// This is a MutableArrayRef that owns its array. |

423 | template <typename T> class OwningArrayRef : public MutableArrayRef<T> { |

424 | public: |

425 | OwningArrayRef() = default; |

426 | OwningArrayRef(size_t Size) : MutableArrayRef<T>(new T[Size], Size) {} |

427 | |

428 | OwningArrayRef(ArrayRef<T> Data) |

429 | : MutableArrayRef<T>(new T[Data.size()], Data.size()) { |

430 | std::copy(Data.begin(), Data.end(), this->begin()); |

431 | } |

432 | |

433 | OwningArrayRef(OwningArrayRef &&Other) { *this = Other; } |

434 | |

435 | OwningArrayRef &operator=(OwningArrayRef &&Other) { |

436 | delete[] this->data(); |

437 | this->MutableArrayRef<T>::operator=(Other); |

438 | Other.MutableArrayRef<T>::operator=(MutableArrayRef<T>()); |

439 | return *this; |

440 | } |

441 | |

442 | ~OwningArrayRef() { delete[] this->data(); } |

443 | }; |

444 | |

445 | /// @name ArrayRef Convenience constructors |

446 | /// @{ |

447 | |

448 | /// Construct an ArrayRef from a single element. |

449 | template<typename T> |

450 | ArrayRef<T> makeArrayRef(const T &OneElt) { |

451 | return OneElt; |

452 | } |

453 | |

454 | /// Construct an ArrayRef from a pointer and length. |

455 | template<typename T> |

456 | ArrayRef<T> makeArrayRef(const T *data, size_t length) { |

457 | return ArrayRef<T>(data, length); |

458 | } |

459 | |

460 | /// Construct an ArrayRef from a range. |

461 | template<typename T> |

462 | ArrayRef<T> makeArrayRef(const T *begin, const T *end) { |

463 | return ArrayRef<T>(begin, end); |

464 | } |

465 | |

466 | /// Construct an ArrayRef from a SmallVector. |

467 | template <typename T> |

468 | ArrayRef<T> makeArrayRef(const SmallVectorImpl<T> &Vec) { |

469 | return Vec; |

470 | } |

471 | |

472 | /// Construct an ArrayRef from a SmallVector. |

473 | template <typename T, unsigned N> |

474 | ArrayRef<T> makeArrayRef(const SmallVector<T, N> &Vec) { |

475 | return Vec; |

476 | } |

477 | |

478 | /// Construct an ArrayRef from a std::vector. |

479 | template<typename T> |

480 | ArrayRef<T> makeArrayRef(const std::vector<T> &Vec) { |

481 | return Vec; |

482 | } |

483 | |

484 | /// Construct an ArrayRef from an ArrayRef (no-op) (const) |

485 | template <typename T> ArrayRef<T> makeArrayRef(const ArrayRef<T> &Vec) { |

486 | return Vec; |

487 | } |

488 | |

489 | /// Construct an ArrayRef from an ArrayRef (no-op) |

490 | template <typename T> ArrayRef<T> &makeArrayRef(ArrayRef<T> &Vec) { |

491 | return Vec; |

492 | } |

493 | |

494 | /// Construct an ArrayRef from a C array. |

495 | template<typename T, size_t N> |

496 | ArrayRef<T> makeArrayRef(const T (&Arr)[N]) { |

497 | return ArrayRef<T>(Arr); |

498 | } |

499 | |

500 | /// Construct a MutableArrayRef from a single element. |

501 | template<typename T> |

502 | MutableArrayRef<T> makeMutableArrayRef(T &OneElt) { |

503 | return OneElt; |

504 | } |

505 | |

506 | /// Construct a MutableArrayRef from a pointer and length. |

507 | template<typename T> |

508 | MutableArrayRef<T> makeMutableArrayRef(T *data, size_t length) { |

509 | return MutableArrayRef<T>(data, length); |

510 | } |

511 | |

512 | /// @} |

513 | /// @name ArrayRef Comparison Operators |

514 | /// @{ |

515 | |

516 | template<typename T> |

517 | inline bool operator==(ArrayRef<T> LHS, ArrayRef<T> RHS) { |

518 | return LHS.equals(RHS); |

519 | } |

520 | |

521 | template<typename T> |

522 | inline bool operator!=(ArrayRef<T> LHS, ArrayRef<T> RHS) { |

523 | return !(LHS == RHS); |

524 | } |

525 | |

526 | /// @} |

527 | |

528 | template <typename T> hash_code hash_value(ArrayRef<T> S) { |

529 | return hash_combine_range(S.begin(), S.end()); |

530 | } |

531 | |

532 | } // end namespace llvm |

533 | |

534 | #endif // LLVM_ADT_ARRAYREF_H |

535 |