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  const 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  const 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  static_cast<V&>(*this) = static_cast<const V&>(other);
370  return *this;
371  }
372 
381  Vector& operator=(Vector&& other) noexcept {
382  static_cast<V&>(*this) = static_cast<V&&>(std::move(other));
383  return *this;
384  }
385 
392  const T& operator[](uint64_t i) const& {
393  if ( i >= V::size() )
394  throw IndexError(fmt("vector index %" PRIu64 " out of range", i));
395 
396  return V::data()[i];
397  }
398 
405  T operator[](uint64_t i) && {
406  if ( i >= V::size() )
407  throw IndexError(fmt("vector index %" PRIu64 " out of range", i));
408 
409  return V::data()[i];
410  }
411 
418  T& operator[](uint64_t i) & {
419  if ( i >= V::size() )
420  throw IndexError(fmt("vector index %" PRIu64 " out of range", i));
421 
422  return V::data()[i];
423  }
424 
425  /* Assigns a value to an element.
426  *
427  * If the element is not present in the vector, it is resized to contain
428  * at i + 1 values. The other added values are default-initialized.
429  *
430  * @param i position of the element to assign
431  * @param x value to assign
432  */
433  void assign(uint64_t i, T x) {
434  if ( i >= V::size() )
435  V::resize(i + 1);
436 
437  V::data()[i] = std::move(x);
438  }
439 
445  Vector operator+(const Vector& other) const {
446  Vector v(*this);
447  v += other;
448  return v;
449  }
450 
456  Vector& operator+=(const Vector& other) {
457  V::insert(V::end(), other.V::begin(), other.V::end());
458  return *this;
459  }
460 
467  iterator insert(iterator pos, const T& value) {
468  const auto index = pos._index;
469  if ( index > size() )
470  throw InvalidIterator(fmt("index %s out of bounds", index));
471 
472  V::insert(V::begin() + index.Ref(), value);
473  return pos;
474  }
475 
476  auto begin() { return iterator(0u, _control); }
477  auto end() { return iterator(size(), _control); }
478 
479  auto begin() const { return const_iterator(0u, _control); }
480  auto end() const { return const_iterator(size(), _control); }
481 
482  auto cbegin() const { return const_iterator(0u, _control); }
483  auto cend() const { return const_iterator(size(), _control); }
484 
485  size_type size() const { return V::size(); }
486 
487  // Methods of `std::vector`.
488  using typename V::value_type;
489  using V::at;
490  using V::clear;
491  using V::emplace_back;
492  using V::empty;
493  using V::pop_back;
494  using V::push_back;
495  using V::reserve;
496  using V::resize;
497 
498  friend bool operator==(const Vector& a, const Vector& b) {
499  return static_cast<const V&>(a) == static_cast<const V&>(b);
500  }
501 };
502 
503 namespace vector {
505 struct Empty {
506  auto begin() const& { return this; }
507  auto end() const& { return this; }
508  auto empty() const { return true; }
509  auto size() const { return integer::safe<uint64_t>(0); }
510 };
511 
512 template<typename T, typename Allocator>
513 inline bool operator==(const Vector<T, Allocator>& v, const Empty& /*unused*/) {
514  return v.empty();
515 }
516 template<typename T, typename Allocator>
517 inline bool operator==(const Empty& /*unused*/, const Vector<T, Allocator>& v) {
518  return v.empty();
519 }
520 template<typename T, typename Allocator>
521 inline bool operator!=(const Vector<T, Allocator>& v, const Empty& /*unused*/) {
522  return ! v.empty();
523 }
524 template<typename T, typename Allocator>
525 inline bool operator!=(const Empty& /*unused*/, const Vector<T, Allocator>& v) {
526  return ! v.empty();
527 }
528 
529 template<typename Allocator, typename I, typename O, typename C>
530 Vector<O, Allocator> make(const C& input, std::function<O(I)> func) {
531  Vector<O, Allocator> output;
532  for ( auto&& i : input )
533  output.emplace_back(func(i));
534 
535  return output;
536 }
537 
538 template<typename Allocator, typename I, typename O, typename C>
539 Vector<O, Allocator> make(const C& input, std::function<O(I)> func, std::function<bool(I)> pred) {
540  Vector<O, Allocator> output;
541  for ( auto&& i : input )
542  if ( pred(i) )
543  output.emplace_back(func(i));
544 
545  return output;
546 }
547 
548 } // namespace vector
549 
550 namespace detail::adl {
551 template<typename T, typename Allocator>
552 inline std::string to_string(const Vector<T, Allocator>& x, adl::tag /*unused*/) {
553  using detail::adl::to_string;
554  return fmt("[%s]", rt::join(rt::transform(x, [](const T& y) { return rt::to_string(y); }), ", "));
555 }
556 
557 inline std::string to_string(const vector::Empty& /* x */, adl::tag /*unused*/) { return "[]"; }
558 
559 template<typename T, typename Allocator>
560 inline std::string to_string(const vector::Iterator<T, Allocator>& /*unused*/, adl::tag /*unused*/) {
561  return "<vector iterator>";
562 }
563 
564 template<typename T, typename Allocator>
565 inline std::string to_string(const vector::ConstIterator<T, Allocator>& /*unused*/, adl::tag /*unused*/) {
566  return "<const vector iterator>";
567 }
568 } // namespace detail::adl
569 
570 template<typename T, typename Allocator>
571 inline std::ostream& operator<<(std::ostream& out, const Vector<T, Allocator>& x) {
572  out << to_string(x);
573  return out;
574 }
575 
576 inline std::ostream& operator<<(std::ostream& out, const vector::Empty& x) {
577  out << to_string(x);
578  return out;
579 }
580 
581 template<typename T, typename Allocator>
582 bool operator!=(const Vector<T, Allocator>& a, const Vector<T, Allocator>& b) {
583  return ! (a == b);
584 }
585 
586 template<typename T, typename Allocator>
587 typename vector::Iterator<T, Allocator>::reference vector::Iterator<T, Allocator>::operator*() {
588  if ( auto&& c = _container() ) {
589  auto&& data = c->get();
590 
591  if ( _index >= data.size() ) {
592  throw InvalidIterator(fmt("index %s out of bounds", _index));
593  }
594 
595  return data[_index];
596  }
597 
598  throw InvalidIterator("bound object has expired");
599 }
600 
601 template<typename T, typename Allocator>
602 typename vector::Iterator<T, Allocator>::const_reference vector::Iterator<T, Allocator>::operator*() const {
603  if ( auto&& c = _container() ) {
604  auto&& data = c->get();
605 
606  if ( _index >= data.size() ) {
607  throw InvalidIterator(fmt("index %s out of bounds", _index));
608  }
609 
610  return data[_index];
611  }
612 
613  throw InvalidIterator("bound object has expired");
614 }
615 
616 namespace vector {
617 
618 template<typename T, typename Allocator>
619 inline std::ostream& operator<<(std::ostream& out, const vector::Iterator<T, Allocator>& /*unused*/) {
620  return out << "<vector iterator>";
621 }
622 
623 template<typename T, typename Allocator>
624 inline std::ostream& operator<<(std::ostream& out, const vector::ConstIterator<T, Allocator>& /*unused*/) {
625  return out << "<const vector iterator>";
626 }
627 
628 } // namespace vector
629 
630 template<typename T, typename Allocator>
631 std::optional<std::reference_wrapper<Vector<T, Allocator>>> vector::Iterator<T, Allocator>::_container() const {
632  if ( auto l = _control.lock() ) {
633  return {std::ref(**l)};
634  }
635 
636  return std::nullopt;
637 }
638 
639 template<typename T, typename Allocator>
640 typename vector::ConstIterator<T, Allocator>::const_reference vector::ConstIterator<T, Allocator>::operator*() const {
641  if ( auto&& c = _container() ) {
642  auto&& data = c->get();
643 
644  if ( _index >= data.size() ) {
645  throw InvalidIterator(fmt("index %s out of bounds", _index));
646  }
647 
648  return data[_index];
649  }
650 
651  throw InvalidIterator("bound object has expired");
652 }
653 
654 template<typename T, typename Allocator>
655 std::optional<std::reference_wrapper<Vector<T, Allocator>>> vector::ConstIterator<T, Allocator>::_container() const {
656  if ( auto l = _control.lock() ) {
657  return {std::ref(**l)};
658  }
659 
660  return std::nullopt;
661 }
662 
663 } // 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:332
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:405
Vector operator+(const Vector &other) const
Definition: vector.h:445
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:392
Definition: vector.h:505
Vector & operator+=(const Vector &other)
Definition: vector.h:456
Vector & operator=(Vector &&other) noexcept
Definition: vector.h:381
std::string join(const T &l, const std::string &delim="")
Definition: util.h:282
Definition: vector.h:251
Definition: vector.h:84
iterator insert(iterator pos, const T &value)
Definition: vector.h:467
T & operator[](uint64_t i) &
Definition: vector.h:418
std::string fmt(const char *fmt, const Args &... args)
Definition: fmt.h:13