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