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_GSL_POINTER LLVM_NODISCARD ArrayRef { |

42 | public: |

43 | using value_type = T; |

44 | using pointer = value_type *; |

45 | using const_pointer = const value_type *; |

46 | using reference = value_type &; |

47 | using const_reference = const value_type &; |

48 | using iterator = const_pointer; |

49 | using const_iterator = const_pointer; |

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

51 | using const_reverse_iterator = std::reverse_iterator<const_iterator>; |

52 | using size_type = size_t; |

53 | using difference_type = ptrdiff_t; |

54 | |

55 | private: |

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

57 | const T *Data = nullptr; |

58 | |

59 | /// The number of elements. |

60 | size_type Length = 0; |

61 | |

62 | public: |

63 | /// @name Constructors |

64 | /// @{ |

65 | |

66 | /// Construct an empty ArrayRef. |

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

68 | |

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

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

71 | |

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

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

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

75 | |

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

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

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

79 | |

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

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

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

83 | |

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

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

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

87 | template<typename U> |

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

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

90 | } |

91 | |

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

93 | template<typename A> |

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

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

96 | |

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

98 | template <size_t N> |

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

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

101 | |

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

103 | template <size_t N> |

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

105 | |

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

107 | #if LLVM_GNUC_PREREQ(9, 0, 0) |

108 | // Disable gcc's warning in this constructor as it generates an enormous amount |

109 | // of messages. Anyone using ArrayRef should already be aware of the fact that |

110 | // it does not do lifetime extension. |

111 | #pragma GCC diagnostic push |

112 | #pragma GCC diagnostic ignored "-Winit-list-lifetime" |

113 | #endif |

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

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

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

117 | #if LLVM_GNUC_PREREQ(9, 0, 0) |

118 | #pragma GCC diagnostic pop |

119 | #endif |

120 | |

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

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

123 | template <typename U> |

124 | ArrayRef(const ArrayRef<U *> &A, |

125 | std::enable_if_t<std::is_convertible<U *const *, T const *>::value> |

126 | * = nullptr) |

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

128 | |

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

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

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

132 | template <typename U, typename DummyT> |

133 | /*implicit*/ ArrayRef( |

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

135 | std::enable_if_t<std::is_convertible<U *const *, T const *>::value> * = |

136 | nullptr) |

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

138 | |

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

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

141 | template <typename U, typename A> |

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

143 | std::enable_if_t<std::is_convertible<U *const *, T const *>::value> |

144 | * = 0) |

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

146 | |

147 | /// @} |

148 | /// @name Simple Operations |

149 | /// @{ |

150 | |

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

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

153 | |

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

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

156 | |

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

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

159 | |

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

161 | |

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

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

164 | |

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

166 | const T &front() const { |

167 | assert(!empty()); |

168 | return Data[0]; |

169 | } |

170 | |

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

172 | const T &back() const { |

173 | assert(!empty()); |

174 | return Data[Length-1]; |

175 | } |

176 | |

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

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

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

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

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

182 | } |

183 | |

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

185 | bool equals(ArrayRef RHS) const { |

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

187 | return false; |

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

189 | } |

190 | |

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

192 | /// elements in the array. |

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

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

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

196 | } |

197 | |

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

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

200 | |

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

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

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

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

205 | } |

206 | |

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

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

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

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

211 | } |

212 | |

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

214 | /// given predicate removed. |

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

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

217 | } |

218 | |

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

220 | /// the given predicate removed. |

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

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

223 | } |

224 | |

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

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

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

228 | return *this; |

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

230 | } |

231 | |

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

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

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

235 | return *this; |

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

237 | } |

238 | |

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

240 | /// predicate. |

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

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

243 | } |

244 | |

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

246 | /// given predicate. |

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

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

249 | } |

250 | |

251 | /// @} |

252 | /// @name Operator Overloads |

253 | /// @{ |

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

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

256 | return Data[Index]; |

257 | } |

258 | |

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

260 | /// |

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

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

263 | template <typename U> |

264 | std::enable_if_t<std::is_same<U, T>::value, ArrayRef<T>> & |

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

266 | |

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

268 | /// |

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

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

271 | template <typename U> |

272 | std::enable_if_t<std::is_same<U, T>::value, ArrayRef<T>> & |

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

274 | |

275 | /// @} |

276 | /// @name Expensive Operations |

277 | /// @{ |

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

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

280 | } |

281 | |

282 | /// @} |

283 | /// @name Conversion operators |

284 | /// @{ |

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

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

287 | } |

288 | |

289 | /// @} |

290 | }; |

291 | |

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

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

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

295 | /// conveniently. |

296 | /// |

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

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

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

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

301 | /// |

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

303 | /// value. |

304 | template<typename T> |

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

306 | public: |

307 | using value_type = T; |

308 | using pointer = value_type *; |

309 | using const_pointer = const value_type *; |

310 | using reference = value_type &; |

311 | using const_reference = const value_type &; |

312 | using iterator = pointer; |

313 | using const_iterator = const_pointer; |

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

315 | using const_reverse_iterator = std::reverse_iterator<const_iterator>; |

316 | using size_type = size_t; |

317 | using difference_type = ptrdiff_t; |

318 | |

319 | /// Construct an empty MutableArrayRef. |

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

321 | |

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

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

324 | |

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

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

327 | |

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

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

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

331 | |

332 | /// Construct a MutableArrayRef from a range. |

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

334 | |

335 | /// Construct a MutableArrayRef from a SmallVector. |

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

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

338 | |

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

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

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

342 | |

343 | /// Construct a MutableArrayRef from a std::array |

344 | template <size_t N> |

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

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

347 | |

348 | /// Construct a MutableArrayRef from a C array. |

349 | template <size_t N> |

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

351 | |

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

353 | |

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

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

356 | |

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

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

359 | |

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

361 | T &front() const { |

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

363 | return data()[0]; |

364 | } |

365 | |

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

367 | T &back() const { |

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

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

370 | } |

371 | |

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

373 | /// elements in the array. |

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

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

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

377 | } |

378 | |

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

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

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

382 | } |

383 | |

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

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

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

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

388 | } |

389 | |

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

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

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

393 | } |

394 | |

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

396 | /// given predicate removed. |

397 | template <class PredicateT> |

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

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

400 | } |

401 | |

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

403 | /// the given predicate removed. |

404 | template <class PredicateT> |

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

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

407 | } |

408 | |

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

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

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

412 | return *this; |

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

414 | } |

415 | |

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

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

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

419 | return *this; |

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

421 | } |

422 | |

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

424 | /// predicate. |

425 | template <class PredicateT> |

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

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

428 | } |

429 | |

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

431 | /// given predicate. |

432 | template <class PredicateT> |

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

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

435 | } |

436 | |

437 | /// @} |

438 | /// @name Operator Overloads |

439 | /// @{ |

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

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

442 | return data()[Index]; |

443 | } |

444 | }; |

445 | |

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

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

448 | public: |

449 | OwningArrayRef() = default; |

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

451 | |

452 | OwningArrayRef(ArrayRef<T> Data) |

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

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

455 | } |

456 | |

457 | OwningArrayRef(OwningArrayRef &&Other) { *this = std::move(Other); } |

458 | |

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

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

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

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

463 | return *this; |

464 | } |

465 | |

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

467 | }; |

468 | |

469 | /// @name ArrayRef Convenience constructors |

470 | /// @{ |

471 | |

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

473 | template<typename T> |

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

475 | return OneElt; |

476 | } |

477 | |

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

479 | template<typename T> |

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

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

482 | } |

483 | |

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

485 | template<typename T> |

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

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

488 | } |

489 | |

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

491 | template <typename T> |

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

493 | return Vec; |

494 | } |

495 | |

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

497 | template <typename T, unsigned N> |

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

499 | return Vec; |

500 | } |

501 | |

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

503 | template<typename T> |

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

505 | return Vec; |

506 | } |

507 | |

508 | /// Construct an ArrayRef from a std::array. |

509 | template <typename T, std::size_t N> |

510 | ArrayRef<T> makeArrayRef(const std::array<T, N> &Arr) { |

511 | return Arr; |

512 | } |

513 | |

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

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

516 | return Vec; |

517 | } |

518 | |

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

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

521 | return Vec; |

522 | } |

523 | |

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

525 | template<typename T, size_t N> |

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

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

528 | } |

529 | |

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

531 | template<typename T> |

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

533 | return OneElt; |

534 | } |

535 | |

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

537 | template<typename T> |

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

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

540 | } |

541 | |

542 | /// @} |

543 | /// @name ArrayRef Comparison Operators |

544 | /// @{ |

545 | |

546 | template<typename T> |

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

548 | return LHS.equals(RHS); |

549 | } |

550 | |

551 | template <typename T> |

552 | inline bool operator==(SmallVectorImpl<T> &LHS, ArrayRef<T> RHS) { |

553 | return ArrayRef<T>(LHS).equals(RHS); |

554 | } |

555 | |

556 | template <typename T> |

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

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

559 | } |

560 | |

561 | template <typename T> |

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

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

564 | } |

565 | |

566 | /// @} |

567 | |

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

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

570 | } |

571 | |

572 | } // end namespace llvm |

573 | |

574 | #endif // LLVM_ADT_ARRAYREF_H |

575 |