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 
53 template<class T, decltype(auto) Default_>
54 class Allocator {
55 public:
56  using value_type = T;
57 
58  value_type* allocate(std::size_t n) { return static_cast<value_type*>(::operator new(n * sizeof(value_type))); }
59 
60  void deallocate(value_type* p, std::size_t) noexcept { ::operator delete(p); }
61 
62  template<typename U>
63  void construct(U* p) noexcept(std::is_nothrow_default_constructible<U>::value) {
64  ::new (static_cast<void*>(p)) U(Default_);
65  }
66 
67  template<typename U, typename... Args>
68  void construct(U* p, Args&&... args) {
69  ::new (p) U(std::forward<Args>(args)...);
70  }
71 
72  template<class U>
73  struct rebind {
75  };
76 };
77 
78 template<class T, decltype(auto) D1, class U, decltype(auto) D2>
79 bool operator==(Allocator<T, D1> const&, Allocator<U, D2> const&) noexcept {
80  return true;
81 }
82 
83 template<class T, decltype(auto) D1, class U, decltype(auto) D2>
84 bool operator!=(Allocator<T, D1> const&, Allocator<U, D2> const&) noexcept {
85  return false;
86 }
87 
88 template<typename T, typename Allocator>
89 class Iterator {
90  using V = Vector<T, Allocator>;
91  friend V;
92 
93  std::weak_ptr<V*> _control;
94  typename V::size_type _index = 0;
95 
96 public:
97  using difference_type = typename V::V::iterator::difference_type;
98  using value_type = typename V::V::iterator::value_type;
99  using pointer = typename V::V::iterator::pointer;
100  using reference = typename V::V::iterator::reference;
101  using const_reference = typename V::V::const_reference;
102  using iterator_category = typename V::V::iterator::iterator_category;
103 
104  Iterator() = default;
105  Iterator(typename V::size_type&& index, const typename V::C& control)
106  : _control(control), _index(std::move(index)) {}
107 
108  reference operator*();
109  const_reference operator*() const;
110 
111  Iterator& operator++() {
112  ++_index;
113  return *this;
114  }
115 
116  Iterator operator++(int) {
117  auto ret = *this;
118  ++(*this);
119  return ret;
120  }
121 
122  friend bool operator==(const Iterator& a, const Iterator& b) {
123  if ( a._control.lock() != b._control.lock() )
124  throw InvalidArgument("cannot compare iterators into different vectors");
125  return a._index == b._index;
126  }
127 
128  friend bool operator!=(const Iterator& a, const Iterator& b) { return ! (a == b); }
129 
130  friend auto operator<(const Iterator& a, const Iterator& b) {
131  if ( a._control.lock() != b._control.lock() )
132  throw InvalidArgument("cannot compare iterators into different vectors");
133  return a._index < b._index;
134  }
135 
136  friend auto operator<=(const Iterator& a, const Iterator& b) {
137  if ( a._control.lock() != b._control.lock() )
138  throw InvalidArgument("cannot compare iterators into different vectors");
139  return a._index <= b._index;
140  }
141 
142  friend auto operator>(const Iterator& a, const Iterator& b) {
143  if ( a._control.lock() != b._control.lock() )
144  throw InvalidArgument("cannot compare iterators into different vectors");
145  return a._index > b._index;
146  }
147 
148  friend auto operator>=(const Iterator& a, const Iterator& b) {
149  if ( a._control.lock() != b._control.lock() )
150  throw InvalidArgument("cannot compare iterators into different vectors");
151  return a._index >= b._index;
152  }
153 
154  friend difference_type operator-(const Iterator& a, const Iterator& b) {
155  if ( a._control.lock() != b._control.lock() )
156  throw InvalidArgument("cannot perform arithmetic with iterators into different vectors");
157  return a._index - b._index;
158  }
159 
160 private:
161  // NOTE: This function returns a mutable reference so calling functions need
162  // to ensure to produce correct `const` semantics in the API exposed to users.
163  std::optional<std::reference_wrapper<V>> _container() const;
164 };
165 
166 template<typename T, typename Allocator>
168  using V = Vector<T, Allocator>;
169 
170  std::weak_ptr<Vector<T, Allocator>*> _control;
171  typename V::size_type _index = 0;
172 
173 public:
174  using difference_type = typename V::V::const_iterator::difference_type;
175  using value_type = typename V::V::const_iterator::value_type;
176  using pointer = typename V::V::const_iterator::pointer;
177  using reference = typename V::V::const_iterator::reference;
178  using const_reference = typename V::V::iterator::reference;
179  using iterator_category = typename V::V::const_iterator::iterator_category;
180 
181  ConstIterator() = default;
182  ConstIterator(typename V::size_type&& index, const typename V::C& control)
183  : _control(control), _index(std::move(index)) {}
184 
185  const_reference operator*() const;
186 
187  ConstIterator& operator++() {
188  ++_index;
189  return *this;
190  }
191 
192  ConstIterator operator++(int) {
193  auto ret = *this;
194  ++(*this);
195  return ret;
196  }
197 
198  friend bool operator==(const ConstIterator& a, const ConstIterator& b) {
199  if ( a._control.lock() != b._control.lock() )
200  throw InvalidArgument("cannot compare iterators into different vectors");
201  return a._index == b._index;
202  }
203 
204  friend bool operator!=(const ConstIterator& a, const ConstIterator& b) { return ! (a == b); }
205 
206  friend auto operator<(const ConstIterator& a, const ConstIterator& b) {
207  if ( a._control.lock() != b._control.lock() )
208  throw InvalidArgument("cannot compare iterators into different vectors");
209  return a._index < b._index;
210  }
211 
212  friend auto operator<=(const ConstIterator& a, const ConstIterator& b) {
213  if ( a._control.lock() != b._control.lock() )
214  throw InvalidArgument("cannot compare iterators into different vectors");
215  return a._index <= b._index;
216  }
217 
218  friend auto operator>(const ConstIterator& a, const ConstIterator& b) {
219  if ( a._control.lock() != b._control.lock() )
220  throw InvalidArgument("cannot compare iterators into different vectors");
221  return a._index > b._index;
222  }
223 
224  friend auto operator>=(const ConstIterator& a, const ConstIterator& b) {
225  if ( a._control.lock() != b._control.lock() )
226  throw InvalidArgument("cannot compare iterators into different vectors");
227  return a._index >= b._index;
228  }
229 
230  friend difference_type operator-(const ConstIterator& a, const ConstIterator& b) {
231  if ( a._control.lock() != b._control.lock() )
232  throw InvalidArgument("cannot perform arithmetic with iterators into different vectors");
233  return a._index - b._index;
234  }
235 
236 private:
237  // NOTE: This function returns a mutable reference so calling functions need
238  // to ensure to produce correct `const` semantics in the API exposed to users.
239  std::optional<std::reference_wrapper<V>> _container() const;
240 };
241 
242 } // namespace vector
243 
255 template<typename T, typename Allocator>
256 class Vector : protected std::vector<T, Allocator> {
257 public:
258  // We do not allow `Vector<bool>` since `std::vector::bool` is not a proper container but a proxy.
259  static_assert(! std::is_same_v<T, bool>, "'Vector' cannot be used with naked booleans, use 'Bool'");
260 
261  using V = std::vector<T, Allocator>;
262 
263  using size_type = integer::safe<uint64_t>;
264  using reference = T&;
265  using const_reference = const T&;
268 
269  using C = std::shared_ptr<Vector*>;
270  C _control = std::make_shared<Vector<T, Allocator>*>(this);
271 
272  Vector() = default;
273 
274  // Constructing from other `Vector` updates the data, but keeps the control block alive.
275  Vector(const Vector& other) : V(other) {}
276  Vector(Vector&& other) noexcept : V(std::move(other)) {}
277 
278  Vector(std::initializer_list<T> init, const Allocator& alloc = Allocator()) : V(std::move(init), alloc) {}
279 
280  ~Vector() = default;
281 
287  const T& front() const {
288  if ( V::empty() )
289  throw IndexError("vector is empty");
290 
291  return V::front();
292  }
293 
299  const T& back() const {
300  if ( V::empty() )
301  throw IndexError("vector is empty");
302 
303  return V::back();
304  }
305 
311  void pop_back() {
312  if ( V::empty() )
313  throw IndexError("vector is empty");
314 
315  V::pop_back();
316  }
317 
324  const_iterator iteratorAt(uint64_t i) const {
325  if ( i >= V::size() )
326  throw IndexError(fmt("vector index %" PRIu64 " out of range", i));
327 
328  return const_iterator(static_cast<size_type>(i), _control);
329  }
330 
338  Vector<T> sub(uint64_t start, uint64_t end) const {
339  if ( end <= start || start >= V::size() )
340  return {};
341 
342  if ( end >= V::size() )
343  end = V::size();
344 
345  Vector<T> v;
346  std::copy(V::begin() + start, V::begin() + end, std::back_inserter(v));
347  return v;
348  }
349 
356  Vector<T> sub(uint64_t end) const {
357  if ( end >= V::size() )
358  end = V::size();
359 
360  Vector<T> v;
361  std::copy(V::begin(), V::begin() + end, std::back_inserter(v));
362  return v;
363  }
364 
373  Vector& operator=(const Vector& other) {
374  if ( &other == this )
375  return *this;
376 
377  static_cast<V&>(*this) = static_cast<const V&>(other);
378  return *this;
379  }
380 
389  Vector& operator=(Vector&& other) noexcept {
390  static_cast<V&>(*this) = static_cast<V&&>(std::move(other));
391  return *this;
392  }
393 
400  const T& operator[](uint64_t i) const& {
401  if ( i >= V::size() )
402  throw IndexError(fmt("vector index %" PRIu64 " out of range", i));
403 
404  return V::data()[i];
405  }
406 
413  T operator[](uint64_t i) && {
414  if ( i >= V::size() )
415  throw IndexError(fmt("vector index %" PRIu64 " out of range", i));
416 
417  return V::data()[i];
418  }
419 
426  T& operator[](uint64_t i) & {
427  if ( i >= V::size() )
428  throw IndexError(fmt("vector index %" PRIu64 " out of range", i));
429 
430  return V::data()[i];
431  }
432 
433  /* Assigns a value to an element.
434  *
435  * If the element is not present in the vector, it is resized to contain
436  * at i + 1 values. The other added values are default-initialized.
437  *
438  * @param i position of the element to assign
439  * @param x value to assign
440  */
441  void assign(uint64_t i, T x) {
442  if ( i >= V::size() )
443  V::resize(i + 1);
444 
445  V::data()[i] = std::move(x);
446  }
447 
453  Vector operator+(const Vector& other) const {
454  Vector v(*this);
455  v += other;
456  return v;
457  }
458 
464  Vector& operator+=(const Vector& other) {
465  V::insert(V::end(), other.V::begin(), other.V::end());
466  return *this;
467  }
468 
475  iterator insert(iterator pos, const T& value) {
476  const auto index = pos._index;
477  if ( index > size() )
478  throw InvalidIterator(fmt("index %s out of bounds", index));
479 
480  V::insert(V::begin() + index.Ref(), value);
481  return pos;
482  }
483 
484  auto begin() { return iterator(0U, _control); }
485  auto end() { return iterator(size(), _control); }
486 
487  auto begin() const { return const_iterator(0U, _control); }
488  auto end() const { return const_iterator(size(), _control); }
489 
490  auto cbegin() const { return const_iterator(0U, _control); }
491  auto cend() const { return const_iterator(size(), _control); }
492 
493  size_type size() const { return V::size(); }
494 
495  // Methods of `std::vector`.
496  using typename V::value_type;
497  using V::at;
498  using V::clear;
499  using V::emplace_back;
500  using V::empty;
501  using V::pop_back;
502  using V::push_back;
503  using V::reserve;
504  using V::resize;
505 
506  friend bool operator==(const Vector& a, const Vector& b) {
507  return static_cast<const V&>(a) == static_cast<const V&>(b);
508  }
509 };
510 
511 namespace vector {
513 struct Empty {
514  auto begin() const& { return this; }
515  auto end() const& { return this; }
516  auto empty() const { return true; }
517  auto size() const { return integer::safe<uint64_t>(0); }
518 };
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 template<typename T, typename Allocator>
529 inline bool operator!=(const Vector<T, Allocator>& v, const Empty& /*unused*/) {
530  return ! v.empty();
531 }
532 template<typename T, typename Allocator>
533 inline bool operator!=(const Empty& /*unused*/, const Vector<T, Allocator>& v) {
534  return ! v.empty();
535 }
536 
537 template<typename Allocator, typename I, typename O, typename C>
538 Vector<O, Allocator> make(const C& input, std::function<O(I)> func) {
539  Vector<O, Allocator> output;
540  for ( auto&& i : input )
541  output.emplace_back(func(i));
542 
543  return output;
544 }
545 
546 template<typename Allocator, typename I, typename O, typename C>
547 Vector<O, Allocator> make(const C& input, std::function<O(I)> func, std::function<bool(I)> pred) {
548  Vector<O, Allocator> output;
549  for ( auto&& i : input )
550  if ( pred(i) )
551  output.emplace_back(func(i));
552 
553  return output;
554 }
555 
556 } // namespace vector
557 
558 namespace detail::adl {
559 template<typename T, typename Allocator>
560 inline std::string to_string(const Vector<T, Allocator>& x, adl::tag /*unused*/) {
561  using detail::adl::to_string;
562  return fmt("[%s]", rt::join(rt::transform(x, [](const T& y) { return rt::to_string(y); }), ", "));
563 }
564 
565 inline std::string to_string(const vector::Empty& /* x */, adl::tag /*unused*/) { return "[]"; }
566 
567 template<typename T, typename Allocator>
568 inline std::string to_string(const vector::Iterator<T, Allocator>& /*unused*/, adl::tag /*unused*/) {
569  return "<vector iterator>";
570 }
571 
572 template<typename T, typename Allocator>
573 inline std::string to_string(const vector::ConstIterator<T, Allocator>& /*unused*/, adl::tag /*unused*/) {
574  return "<const vector iterator>";
575 }
576 } // namespace detail::adl
577 
578 template<typename T, typename Allocator>
579 inline std::ostream& operator<<(std::ostream& out, const Vector<T, Allocator>& x) {
580  out << to_string(x);
581  return out;
582 }
583 
584 inline std::ostream& operator<<(std::ostream& out, const vector::Empty& x) {
585  out << to_string(x);
586  return out;
587 }
588 
589 template<typename T, typename Allocator>
590 bool operator!=(const Vector<T, Allocator>& a, const Vector<T, Allocator>& b) {
591  return ! (a == b);
592 }
593 
594 template<typename T, typename Allocator>
595 typename vector::Iterator<T, Allocator>::reference vector::Iterator<T, Allocator>::operator*() {
596  if ( auto&& c = _container() ) {
597  auto&& data = c->get();
598 
599  if ( _index >= data.size() ) {
600  throw InvalidIterator(fmt("index %s out of bounds", _index));
601  }
602 
603  return data[_index];
604  }
605 
606  throw InvalidIterator("bound object has expired");
607 }
608 
609 template<typename T, typename Allocator>
610 typename vector::Iterator<T, Allocator>::const_reference vector::Iterator<T, Allocator>::operator*() const {
611  if ( auto&& c = _container() ) {
612  auto&& data = c->get();
613 
614  if ( _index >= data.size() ) {
615  throw InvalidIterator(fmt("index %s out of bounds", _index));
616  }
617 
618  return data[_index];
619  }
620 
621  throw InvalidIterator("bound object has expired");
622 }
623 
624 namespace vector {
625 
626 template<typename T, typename Allocator>
627 inline std::ostream& operator<<(std::ostream& out, const vector::Iterator<T, Allocator>& /*unused*/) {
628  return out << "<vector iterator>";
629 }
630 
631 template<typename T, typename Allocator>
632 inline std::ostream& operator<<(std::ostream& out, const vector::ConstIterator<T, Allocator>& /*unused*/) {
633  return out << "<const vector iterator>";
634 }
635 
636 } // namespace vector
637 
638 template<typename T, typename Allocator>
639 std::optional<std::reference_wrapper<Vector<T, Allocator>>> vector::Iterator<T, Allocator>::_container() const {
640  if ( auto l = _control.lock() ) {
641  return {std::ref(**l)};
642  }
643 
644  return std::nullopt;
645 }
646 
647 template<typename T, typename Allocator>
648 typename vector::ConstIterator<T, Allocator>::const_reference vector::ConstIterator<T, Allocator>::operator*() const {
649  if ( auto&& c = _container() ) {
650  auto&& data = c->get();
651 
652  if ( _index >= data.size() ) {
653  throw InvalidIterator(fmt("index %s out of bounds", _index));
654  }
655 
656  return data[_index];
657  }
658 
659  throw InvalidIterator("bound object has expired");
660 }
661 
662 template<typename T, typename Allocator>
663 std::optional<std::reference_wrapper<Vector<T, Allocator>>> vector::ConstIterator<T, Allocator>::_container() const {
664  if ( auto l = _control.lock() ) {
665  return {std::ref(**l)};
666  }
667 
668  return std::nullopt;
669 }
670 
671 } // namespace hilti::rt
Vector< T > sub(uint64_t start, uint64_t end) const
Definition: vector.h:338
std::string to_string(T &&x)
Definition: extension-points.h:26
void init()
Definition: init.cc:22
auto transform(const C &x, F f)
Definition: util.h:362
Vector< T > sub(uint64_t end) const
Definition: vector.h:356
const_iterator iteratorAt(uint64_t i) const
Definition: vector.h:324
Vector & operator=(const Vector &other)
Definition: vector.h:373
Definition: any.h:7
Definition: vector.h:167
Definition: vector.h:54
void pop_back()
Definition: vector.h:311
T operator[](uint64_t i) &&
Definition: vector.h:413
Vector operator+(const Vector &other) const
Definition: vector.h:453
const T & back() const
Definition: vector.h:299
const T & front() const
Definition: vector.h:287
const T & operator[](uint64_t i) const &
Definition: vector.h:400
Definition: vector.h:513
Vector & operator+=(const Vector &other)
Definition: vector.h:464
Vector & operator=(Vector &&other) noexcept
Definition: vector.h:389
std::string join(const T &l, const std::string &delim="")
Definition: util.h:312
Definition: vector.h:256
Definition: vector.h:89
iterator insert(iterator pos, const T &value)
Definition: vector.h:475
T & operator[](uint64_t i) &
Definition: vector.h:426
std::string fmt(const char *fmt, const Args &... args)
Definition: fmt.h:13