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