Spicy
vector.h
1 // Copyright (c) 2020-2021 by the Zeek Project. See LICENSE for details.
2 
13 #pragma once
14 
15 #include <algorithm>
16 #include <cinttypes>
17 #include <cstddef>
18 #include <cstdint>
19 #include <functional>
20 #include <initializer_list>
21 #include <iterator>
22 #include <memory>
23 #include <new>
24 #include <optional>
25 #include <ostream>
26 #include <string>
27 #include <type_traits>
28 #include <utility>
29 #include <vector>
30 
31 #include <hilti/rt/extension-points.h>
32 #include <hilti/rt/fmt.h>
33 #include <hilti/rt/iterator.h>
34 #include <hilti/rt/types/vector_fwd.h>
35 #include <hilti/rt/util.h>
36 
37 namespace hilti::rt {
38 
39 namespace vector {
40 
47 template<class T, T Default_>
48 class Allocator {
49 public:
50  using value_type = T;
51 
52  value_type* allocate(std::size_t n) { return static_cast<value_type*>(::operator new(n * sizeof(value_type))); }
53 
54  void deallocate(value_type* p, std::size_t) noexcept { ::operator delete(p); }
55 
56  template<typename U>
57  void construct(U* p) noexcept(std::is_nothrow_default_constructible<U>::value) {
58  ::new (static_cast<void*>(p)) U(Default_);
59  }
60 
61  template<typename U, typename... Args>
62  void construct(U* p, Args&&... args) {
63  ::new (p) U(std::forward<Args>(args)...);
64  }
65 
66  template<class U>
67  struct rebind {
69  };
70 };
71 
72 template<class T, T D1, class U, U D2>
73 bool operator==(Allocator<T, D1> const&, Allocator<U, D2> const&) noexcept {
74  return true;
75 }
76 
77 template<class T, T D1, class U, U D2>
78 bool operator!=(Allocator<T, D1> const&, Allocator<U, D2> const&) noexcept {
79  return false;
80 }
81 
82 template<typename T, typename Allocator>
83 class Iterator {
84  using V = Vector<T, Allocator>;
85 
86  std::weak_ptr<V*> _control;
87  typename V::size_type _index = 0;
88 
89 public:
90  using difference_type = typename V::V::iterator::difference_type;
91  using value_type = typename V::V::iterator::value_type;
92  using pointer = typename V::V::iterator::pointer;
93  using reference = typename V::V::iterator::reference;
94  using const_reference = typename V::V::const_reference;
95  using iterator_category = typename V::V::iterator::iterator_category;
96 
97  Iterator() = default;
98  Iterator(typename V::size_type&& index, const typename V::C& control)
99  : _control(control), _index(std::move(index)) {}
100 
101  reference operator*();
102  const_reference operator*() const;
103 
104  Iterator& operator++() {
105  ++_index;
106  return *this;
107  }
108 
109  Iterator operator++(int) {
110  auto ret = *this;
111  ++(*this);
112  return ret;
113  }
114 
115  friend bool operator==(const Iterator& a, const Iterator& b) {
116  if ( a._control.lock() != b._control.lock() )
117  throw InvalidArgument("cannot compare iterators into different vectors");
118  return a._index == b._index;
119  }
120 
121  friend bool operator!=(const Iterator& a, const Iterator& b) { return ! (a == b); }
122 
123  friend auto operator<(const Iterator& a, const Iterator& b) {
124  if ( a._control.lock() != b._control.lock() )
125  throw InvalidArgument("cannot compare iterators into different vectors");
126  return a._index < b._index;
127  }
128 
129  friend auto operator<=(const Iterator& a, const Iterator& b) {
130  if ( a._control.lock() != b._control.lock() )
131  throw InvalidArgument("cannot compare iterators into different vectors");
132  return a._index <= b._index;
133  }
134 
135  friend auto operator>(const Iterator& a, const Iterator& b) {
136  if ( a._control.lock() != b._control.lock() )
137  throw InvalidArgument("cannot compare iterators into different vectors");
138  return a._index > b._index;
139  }
140 
141  friend auto operator>=(const Iterator& a, const Iterator& b) {
142  if ( a._control.lock() != b._control.lock() )
143  throw InvalidArgument("cannot compare iterators into different vectors");
144  return a._index >= b._index;
145  }
146 
147  friend difference_type operator-(const Iterator& a, const Iterator& b) {
148  if ( a._control.lock() != b._control.lock() )
149  throw InvalidArgument("cannot perform arithmetic with iterators into different vectors");
150  return a._index - b._index;
151  }
152 
153 private:
154  // NOTE: This function returns a mutable reference so calling functions need
155  // to ensure to produce correct `const` semantics in the API exposed to users.
156  std::optional<std::reference_wrapper<V>> _container() const;
157 };
158 
159 template<typename T, typename Allocator>
161  using V = Vector<T, Allocator>;
162 
163  std::weak_ptr<Vector<T, Allocator>*> _control;
164  typename V::size_type _index = 0;
165 
166 public:
167  using difference_type = typename V::V::const_iterator::difference_type;
168  using value_type = typename V::V::const_iterator::value_type;
169  using pointer = typename V::V::const_iterator::pointer;
170  using reference = typename V::V::const_iterator::reference;
171  using const_reference = typename V::V::iterator::reference;
172  using iterator_category = typename V::V::const_iterator::iterator_category;
173 
174  ConstIterator() = default;
175  ConstIterator(typename V::size_type&& index, const typename V::C& control)
176  : _control(control), _index(std::move(index)) {}
177 
178  const_reference operator*() const;
179 
180  ConstIterator& operator++() {
181  ++_index;
182  return *this;
183  }
184 
185  ConstIterator operator++(int) {
186  auto ret = *this;
187  ++(*this);
188  return ret;
189  }
190 
191  friend bool operator==(const ConstIterator& a, const ConstIterator& b) {
192  if ( a._control.lock() != b._control.lock() )
193  throw InvalidArgument("cannot compare iterators into different vectors");
194  return a._index == b._index;
195  }
196 
197  friend bool operator!=(const ConstIterator& a, const ConstIterator& b) { return ! (a == b); }
198 
199  friend auto operator<(const ConstIterator& a, const ConstIterator& b) {
200  if ( a._control.lock() != b._control.lock() )
201  throw InvalidArgument("cannot compare iterators into different vectors");
202  return a._index < b._index;
203  }
204 
205  friend auto operator<=(const ConstIterator& a, const ConstIterator& b) {
206  if ( a._control.lock() != b._control.lock() )
207  throw InvalidArgument("cannot compare iterators into different vectors");
208  return a._index <= b._index;
209  }
210 
211  friend auto operator>(const ConstIterator& a, const ConstIterator& b) {
212  if ( a._control.lock() != b._control.lock() )
213  throw InvalidArgument("cannot compare iterators into different vectors");
214  return a._index > b._index;
215  }
216 
217  friend auto operator>=(const ConstIterator& a, const ConstIterator& b) {
218  if ( a._control.lock() != b._control.lock() )
219  throw InvalidArgument("cannot compare iterators into different vectors");
220  return a._index >= b._index;
221  }
222 
223  friend difference_type operator-(const ConstIterator& a, const ConstIterator& b) {
224  if ( a._control.lock() != b._control.lock() )
225  throw InvalidArgument("cannot perform arithmetic with iterators into different vectors");
226  return a._index - b._index;
227  }
228 
229 private:
230  // NOTE: This function returns a mutable reference so calling functions need
231  // to ensure to produce correct `const` semantics in the API exposed to users.
232  std::optional<std::reference_wrapper<V>> _container() const;
233 };
234 
235 } // namespace vector
236 
248 template<typename T, typename Allocator>
249 class Vector : protected std::vector<T, Allocator> {
250 public:
251  // We do not allow `Vector<bool>` since `std::vector::bool` is not a proper container but a proxy.
252  static_assert(! std::is_same_v<T, bool>, "'Vector' cannot be used with naked booleans, use 'Bool'");
253 
254  using V = std::vector<T, Allocator>;
255 
256  using size_type = uint64_t;
257  using reference = T&;
258  using const_reference = const T&;
261 
262  using C = std::shared_ptr<Vector*>;
263  C _control = std::make_shared<Vector<T, Allocator>*>(this);
264 
265  Vector() = default;
266 
267  // Constructing from other `Vector` updates the data, but keeps the control block alive.
268  Vector(const Vector& other) : V(other) {}
269  Vector(Vector&& other) noexcept : V(std::move(other)) {}
270 
271  Vector(std::initializer_list<T> init, const Allocator& alloc = Allocator()) : V(std::move(init), alloc) {}
272 
273  ~Vector() = default;
274 
280  const T& front() const {
281  if ( V::empty() )
282  throw IndexError("vector is empty");
283 
284  return V::front();
285  }
286 
292  const T& back() const {
293  if ( V::empty() )
294  throw IndexError("vector is empty");
295 
296  return V::back();
297  }
298 
304  void pop_back() {
305  if ( V::empty() )
306  throw IndexError("vector is empty");
307 
308  V::pop_back();
309  }
310 
317  const_iterator iteratorAt(uint64_t i) const {
318  if ( i >= V::size() )
319  throw IndexError(fmt("vector index %" PRIu64 " out of range", i));
320 
321  return const_iterator(static_cast<size_type>(i), _control);
322  }
323 
331  Vector<T> sub(uint64_t start, uint64_t end) const {
332  if ( end <= start || start >= V::size() )
333  return {};
334 
335  if ( end >= V::size() )
336  end = V::size();
337 
338  Vector<T> v;
339  std::copy(V::begin() + start, V::begin() + end, std::back_inserter(v));
340  return v;
341  }
342 
349  Vector<T> sub(uint64_t end) const {
350  if ( end >= V::size() )
351  end = V::size();
352 
353  Vector<T> v;
354  std::copy(V::begin(), V::begin() + end, std::back_inserter(v));
355  return v;
356  }
357 
366  Vector& operator=(const Vector& other) {
367  static_cast<V&>(*this) = static_cast<const V&>(other);
368  return *this;
369  }
370 
379  Vector& operator=(Vector&& other) noexcept {
380  static_cast<V&>(*this) = static_cast<V&&>(std::move(other));
381  return *this;
382  }
383 
390  const T& operator[](uint64_t i) const& {
391  if ( i >= V::size() )
392  throw IndexError(fmt("vector index %" PRIu64 " out of range", i));
393 
394  return V::data()[i];
395  }
396 
403  T operator[](uint64_t i) && {
404  if ( i >= V::size() )
405  throw IndexError(fmt("vector index %" PRIu64 " out of range", i));
406 
407  return V::data()[i];
408  }
409 
416  T& operator[](uint64_t i) & {
417  if ( i >= V::size() )
418  throw IndexError(fmt("vector index %" PRIu64 " out of range", i));
419 
420  return V::data()[i];
421  }
422 
423  /* Assigns a value to an element.
424  *
425  * If the element is not present in the vector, it is resized to contain
426  * at i + 1 values. The other added values are default-initialized.
427  *
428  * @param i position of the element to assign
429  * @param x value to assign
430  */
431  void assign(uint64_t i, T x) {
432  if ( i >= V::size() )
433  V::resize(i + 1);
434 
435  V::data()[i] = std::move(x);
436  }
437 
443  Vector operator+(const Vector& other) const {
444  Vector v(*this);
445  v += other;
446  return v;
447  }
448 
454  Vector& operator+=(const Vector& other) {
455  V::insert(V::end(), other.V::begin(), other.V::end());
456  return *this;
457  }
458 
459  auto begin() { return iterator(0u, _control); }
460  auto end() { return iterator(size(), _control); }
461 
462  auto begin() const { return const_iterator(0u, _control); }
463  auto end() const { return const_iterator(size(), _control); }
464 
465  auto cbegin() const { return const_iterator(0u, _control); }
466  auto cend() const { return const_iterator(size(), _control); }
467 
468  size_t size() const { return V::size(); }
469 
470  // Methods of `std::vector`.
471  using typename V::value_type;
472  using V::at;
473  using V::clear;
474  using V::emplace_back;
475  using V::empty;
476  using V::pop_back;
477  using V::push_back;
478  using V::reserve;
479  using V::resize;
480 
481  friend bool operator==(const Vector& a, const Vector& b) {
482  return static_cast<const V&>(a) == static_cast<const V&>(b);
483  }
484 };
485 
486 namespace vector {
488 struct Empty {
489  auto begin() const& { return this; }
490  auto end() const& { return this; }
491  auto empty() const { return true; }
492  auto size() const { return 0u; }
493 };
494 
495 template<typename T, typename Allocator>
496 inline bool operator==(const Vector<T, Allocator>& v, const Empty& /*unused*/) {
497  return v.empty();
498 }
499 template<typename T, typename Allocator>
500 inline bool operator==(const Empty& /*unused*/, const Vector<T, Allocator>& v) {
501  return v.empty();
502 }
503 template<typename T, typename Allocator>
504 inline bool operator!=(const Vector<T, Allocator>& v, const Empty& /*unused*/) {
505  return ! v.empty();
506 }
507 template<typename T, typename Allocator>
508 inline bool operator!=(const Empty& /*unused*/, const Vector<T, Allocator>& v) {
509  return ! v.empty();
510 }
511 
512 template<typename Allocator, typename I, typename O, typename C>
513 Vector<O, Allocator> make(const C& input, std::function<O(I)> func) {
514  Vector<O, Allocator> output;
515  for ( auto&& i : input )
516  output.emplace_back(func(i));
517 
518  return output;
519 }
520 
521 template<typename Allocator, typename I, typename O, typename C>
522 Vector<O, Allocator> make(const C& input, std::function<O(I)> func, std::function<bool(I)> pred) {
523  Vector<O, Allocator> output;
524  for ( auto&& i : input )
525  if ( pred(i) )
526  output.emplace_back(func(i));
527 
528  return output;
529 }
530 
531 } // namespace vector
532 
533 namespace detail::adl {
534 template<typename T, typename Allocator>
535 inline std::string to_string(const Vector<T, Allocator>& x, adl::tag /*unused*/) {
536  using detail::adl::to_string;
537  return fmt("[%s]", rt::join(rt::transform(x, [](const T& y) { return rt::to_string(y); }), ", "));
538 }
539 
540 inline std::string to_string(const vector::Empty& /* x */, adl::tag /*unused*/) { return "[]"; }
541 
542 template<typename T, typename Allocator>
543 inline std::string to_string(const vector::Iterator<T, Allocator>& /*unused*/, adl::tag /*unused*/) {
544  return "<vector iterator>";
545 }
546 
547 template<typename T, typename Allocator>
548 inline std::string to_string(const vector::ConstIterator<T, Allocator>& /*unused*/, adl::tag /*unused*/) {
549  return "<const vector iterator>";
550 }
551 } // namespace detail::adl
552 
553 template<typename T, typename Allocator>
554 inline std::ostream& operator<<(std::ostream& out, const Vector<T, Allocator>& x) {
555  out << to_string(x);
556  return out;
557 }
558 
559 inline std::ostream& operator<<(std::ostream& out, const vector::Empty& x) {
560  out << to_string(x);
561  return out;
562 }
563 
564 template<typename T, typename Allocator>
565 bool operator!=(const Vector<T, Allocator>& a, const Vector<T, Allocator>& b) {
566  return ! (a == b);
567 }
568 
569 template<typename T, typename Allocator>
570 typename vector::Iterator<T, Allocator>::reference vector::Iterator<T, Allocator>::operator*() {
571  if ( auto&& c = _container() ) {
572  auto&& data = c->get();
573 
574  if ( _index >= data.size() ) {
575  throw InvalidIterator(fmt("index %s out of bounds", _index));
576  }
577 
578  return data[_index];
579  }
580 
581  throw InvalidIterator("bound object has expired");
582 }
583 
584 template<typename T, typename Allocator>
585 typename vector::Iterator<T, Allocator>::const_reference vector::Iterator<T, Allocator>::operator*() const {
586  if ( auto&& c = _container() ) {
587  auto&& data = c->get();
588 
589  if ( _index >= data.size() ) {
590  throw InvalidIterator(fmt("index %s out of bounds", _index));
591  }
592 
593  return data[_index];
594  }
595 
596  throw InvalidIterator("bound object has expired");
597 }
598 
599 namespace vector {
600 
601 template<typename T, typename Allocator>
602 inline std::ostream& operator<<(std::ostream& out, const vector::Iterator<T, Allocator>& /*unused*/) {
603  return out << "<vector iterator>";
604 }
605 
606 template<typename T, typename Allocator>
607 inline std::ostream& operator<<(std::ostream& out, const vector::ConstIterator<T, Allocator>& /*unused*/) {
608  return out << "<const vector iterator>";
609 }
610 
611 } // namespace vector
612 
613 template<typename T, typename Allocator>
614 std::optional<std::reference_wrapper<Vector<T, Allocator>>> vector::Iterator<T, Allocator>::_container() const {
615  if ( auto l = _control.lock() ) {
616  return {std::ref(**l)};
617  }
618 
619  return std::nullopt;
620 }
621 
622 template<typename T, typename Allocator>
623 typename vector::ConstIterator<T, Allocator>::const_reference vector::ConstIterator<T, Allocator>::operator*() const {
624  if ( auto&& c = _container() ) {
625  auto&& data = c->get();
626 
627  if ( _index >= data.size() ) {
628  throw InvalidIterator(fmt("index %s out of bounds", _index));
629  }
630 
631  return data[_index];
632  }
633 
634  throw InvalidIterator("bound object has expired");
635 }
636 
637 template<typename T, typename Allocator>
638 std::optional<std::reference_wrapper<Vector<T, Allocator>>> vector::ConstIterator<T, Allocator>::_container() const {
639  if ( auto l = _control.lock() ) {
640  return {std::ref(**l)};
641  }
642 
643  return std::nullopt;
644 }
645 
646 } // namespace hilti::rt
Vector< T > sub(uint64_t start, uint64_t end) const
Definition: vector.h:331
std::string to_string(T &&x)
Definition: extension-points.h:26
void init()
Definition: init.cc:19
Vector< T > sub(uint64_t end) const
Definition: vector.h:349
const_iterator iteratorAt(uint64_t i) const
Definition: vector.h:317
Vector & operator=(const Vector &other)
Definition: vector.h:366
Definition: any.h:7
Definition: vector.h:160
auto transform(const std::vector< X > &x, F f)
Definition: util.h:299
Definition: vector.h:48
void pop_back()
Definition: vector.h:304
T operator[](uint64_t i) &&
Definition: vector.h:403
Vector operator+(const Vector &other) const
Definition: vector.h:443
const T & back() const
Definition: vector.h:292
const T & front() const
Definition: vector.h:280
const T & operator[](uint64_t i) const &
Definition: vector.h:390
Definition: vector.h:488
Vector & operator+=(const Vector &other)
Definition: vector.h:454
Vector & operator=(Vector &&other) noexcept
Definition: vector.h:379
std::string join(const T &l, const std::string &delim="")
Definition: util.h:281
Definition: vector.h:249
Definition: vector.h:83
T & operator[](uint64_t i) &
Definition: vector.h:416
std::string fmt(const char *fmt, const Args &... args)
Definition: fmt.h:13