Spicy
map.h
1 // Copyright (c) 2020-2021 by the Zeek Project. See LICENSE for details.
2 
12 #pragma once
13 
14 #include <algorithm>
15 #include <functional>
16 #include <initializer_list>
17 #include <map>
18 #include <memory>
19 #include <string>
20 #include <utility>
21 #include <vector>
22 
23 #include <hilti/rt/extension-points.h>
24 #include <hilti/rt/iterator.h>
25 #include <hilti/rt/safe-int.h>
26 #include <hilti/rt/util.h>
27 
28 namespace hilti::rt {
29 
30 template<typename K, typename V>
31 class Map;
32 
33 namespace map {
34 
35 template<typename K, typename V>
36 class Iterator {
37  using M = Map<K, V>;
38 
39  std::weak_ptr<M*> _control;
40  typename M::M::iterator _iterator;
41 
42 public:
43  Iterator() = default;
44 
45  friend class Map<K, V>;
46 
47  friend bool operator==(const Iterator& a, const Iterator& b) {
48  if ( a._control.lock() != b._control.lock() )
49  throw InvalidArgument("cannot compare iterators into different maps");
50 
51  return a._iterator == b._iterator;
52  }
53 
54  friend bool operator!=(const Iterator& a, const Iterator& b) { return ! (a == b); }
55 
56  Iterator& operator++() {
57  if ( ! _control.lock() ) {
58  throw IndexError("iterator is invalid");
59  }
60 
61  ++_iterator;
62  return *this;
63  }
64 
65  Iterator operator++(int) {
66  auto ret = *this;
67  ++(*this);
68  return ret;
69  }
70 
71  const typename M::M::value_type* operator->() const { return &operator*(); }
72 
73  typename M::M::const_reference operator*() const {
74  if ( auto&& l = _control.lock() ) {
75  // Iterators to `end` cannot be dereferenced.
76  if ( _iterator == static_cast<const typename M::M&>(**l).cend() )
77  throw IndexError("iterator is invalid");
78 
79  return *_iterator;
80  }
81 
82  throw IndexError("iterator is invalid");
83  }
84 
85 private:
86  friend class Map<K, V>;
87 
88  Iterator(typename M::M::iterator iterator, const typename M::C& control)
89  : _control(control), _iterator(std::move(iterator)) {}
90 };
91 
92 template<typename K, typename V>
94  using M = Map<K, V>;
95 
96  std::weak_ptr<M*> _control;
97  typename M::M::const_iterator _iterator;
98 
99 public:
100  ConstIterator() = default;
101 
102  friend bool operator==(const ConstIterator& a, const ConstIterator& b) {
103  if ( a._control.lock() != b._control.lock() )
104  throw InvalidArgument("cannot compare iterators into different sets");
105 
106  return a._iterator == b._iterator;
107  }
108 
109  friend bool operator!=(const ConstIterator& a, const ConstIterator& b) { return ! (a == b); }
110 
111  ConstIterator& operator++() {
112  if ( ! _control.lock() ) {
113  throw IndexError("iterator is invalid");
114  }
115 
116  ++_iterator;
117  return *this;
118  }
119 
120  ConstIterator operator++(int) {
121  auto ret = *this;
122  ++(*this);
123  return ret;
124  }
125 
126  const typename M::M::value_type* operator->() const { return &operator*(); }
127 
128  typename M::M::const_reference operator*() const {
129  if ( auto&& l = _control.lock() ) {
130  // Iterators to `end` cannot be dereferenced.
131  if ( _iterator == static_cast<const typename M::M&>(**l).cend() )
132  throw IndexError("iterator is invalid");
133 
134  return *_iterator;
135  }
136 
137  throw IndexError("iterator is invalid");
138  }
139 
140 private:
141  friend class Map<K, V>;
142 
143  ConstIterator(typename M::M::const_iterator iterator, const typename M::C& control)
144  : _control(control), _iterator(std::move(iterator)) {}
145 };
146 
147 } // namespace map
148 
170 template<typename K, typename V>
171 class Map : protected std::map<K, V> {
172 public:
173  using M = std::map<K, V>;
174  using C = std::shared_ptr<Map<K, V>*>;
175 
176  C _control = std::make_shared<Map<K, V>*>(this);
177 
178  using key_type = typename M::key_type;
179  using value_type = typename M::value_type;
180  using size_type = integer::safe<uint64_t>;
181 
182  using iterator = typename map::Iterator<K, V>;
183  using const_iterator = typename map::ConstIterator<K, V>;
184 
185  Map() = default;
186  Map(std::initializer_list<value_type> init) : M(std::move(init)) {}
187 
193  bool contains(const K& k) const { return this->find(k) != static_cast<const M&>(*this).end(); }
194 
202  const V& get(const K& k) const& {
203  try {
204  return this->at(k);
205  } catch ( const std::out_of_range& ) {
206  throw IndexError("key is unset");
207  }
208  }
209 
217  V& get(const K& k) & {
218  try {
219  return this->at(k);
220  } catch ( const std::out_of_range& ) {
221  throw IndexError("key is unset");
222  }
223  }
224 
231  auto& operator[](const K& k) & { return this->get(k); }
232 
239  const auto& operator[](const K& k) const& { return this->get(k); }
240 
249  auto operator[](const K& k) && { return this->get(k); }
250 
251  void index_assign(const K& key, V value) {
252  if ( ! contains(key) )
253  this->invalidateIterators();
254 
255  this->insert_or_assign(key, std::move(value));
256  }
257 
258  auto begin() const { return this->cbegin(); }
259  auto end() const { return this->cend(); }
260 
261  auto begin() { return iterator(static_cast<M&>(*this).begin(), _control); }
262  auto end() { return iterator(static_cast<M&>(*this).end(), _control); }
263 
264  auto cbegin() const { return const_iterator(static_cast<const M&>(*this).begin(), _control); }
265  auto cend() const { return const_iterator(static_cast<const M&>(*this).end(), _control); }
266 
267  size_type size() const { return M::size(); }
268 
273  auto clear() {
274  this->invalidateIterators();
275 
276  return static_cast<M&>(*this).clear();
277  }
278 
286  auto erase(const key_type& key) {
287  auto removed = static_cast<M&>(*this).erase(key);
288 
289  if ( removed ) {
290  this->invalidateIterators();
291  }
292 
293  return removed;
294  }
295 
296  friend bool operator==(const Map& a, const Map& b) { return static_cast<const M&>(a) == static_cast<const M&>(b); }
297  friend bool operator!=(const Map& a, const Map& b) { return ! (a == b); }
298 
299 private:
300  friend map::Iterator<K, V>;
302 
303  void invalidateIterators() {
304  // Update control block to invalidate all iterators previously created from it.
305  _control = std::make_shared<Map<K, V>*>(this);
306  }
307 }; // namespace hilti::rt
308 
309 namespace map {
311 class Empty : public Map<bool, bool> {};
312 
313 template<typename K, typename V>
314 inline bool operator==(const Map<K, V>& v, const Empty& /*unused*/) {
315  return v.empty();
316 }
317 template<typename K, typename V>
318 inline bool operator==(const Empty& /*unused*/, const Map<K, V>& v) {
319  return v.empty();
320 }
321 template<typename K, typename V>
322 inline bool operator!=(const Map<K, V>& v, const Empty& /*unused*/) {
323  return ! v.empty();
324 }
325 template<typename K, typename V>
326 inline bool operator!=(const Empty& /*unused*/, const Map<K, V>& v) {
327  return ! v.empty();
328 }
329 
330 template<typename K, typename V>
331 inline std::ostream& operator<<(std::ostream& out, const map::Iterator<K, V>& it) {
332  return out << to_string(it);
333 }
334 
335 template<typename K, typename V>
336 inline std::ostream& operator<<(std::ostream& out, const map::ConstIterator<K, V>& it) {
337  return out << to_string(it);
338 }
339 } // namespace map
340 
341 namespace detail::adl {
342 template<typename K, typename V>
343 inline std::string to_string(const Map<K, V>& x, adl::tag /*unused*/) {
344  std::vector<std::string> r;
345 
346  for ( const auto& i : x )
347  r.push_back(fmt("%s: %s", hilti::rt::to_string(i.first), hilti::rt::to_string(i.second)));
348 
349  return fmt("{%s}", rt::join(r, ", "));
350 }
351 
352 inline std::string to_string(const map::Empty& x, adl::tag /*unused*/) { return "{}"; }
353 
354 template<typename K, typename V>
355 inline std::string to_string(const map::Iterator<K, V>& /*unused*/, adl::tag /*unused*/) {
356  return "<map iterator>";
357 }
358 
359 template<typename K, typename V>
360 inline std::string to_string(const map::ConstIterator<K, V>& /*unused*/, adl::tag /*unused*/) {
361  return "<const map iterator>";
362 }
363 
364 } // namespace detail::adl
365 
366 template<typename K, typename V>
367 inline std::ostream& operator<<(std::ostream& out, const Map<K, V>& x) {
368  return out << to_string(x);
369 }
370 
371 inline std::ostream& operator<<(std::ostream& out, const map::Empty& x) { return out << to_string(x); }
372 
373 } // namespace hilti::rt
std::string to_string(T &&x)
Definition: extension-points.h:26
void init()
Definition: init.cc:18
Definition: map.h:311
Definition: map.h:93
Definition: any.h:7
auto & operator[](const K &k) &
Definition: map.h:231
auto erase(const key_type &key)
Definition: map.h:286
bool contains(const K &k) const
Definition: map.h:193
Definition: map.h:31
Definition: map.h:36
auto clear()
Definition: map.h:273
std::string join(const T &l, const std::string &delim="")
Definition: util.h:281
auto operator[](const K &k) &&
Definition: map.h:249
const auto & operator[](const K &k) const &
Definition: map.h:239
std::string fmt(const char *fmt, const Args &... args)
Definition: fmt.h:13