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