Spicy
visitor.h
1 // Copyright (c) 2020-2021 by the Zeek Project. See LICENSE for details.
2 
3 #pragma once
4 
5 #include <type_traits>
6 #include <vector>
7 
8 #include <hilti/base/logger.h>
9 #include <hilti/base/visitor-types.h>
10 
11 namespace hilti {
12 namespace detail::visitor {
13 
14 enum class Order { Pre, Post };
15 
16 // hasCallback<C,FuncSig>
17 // Test if Visitor class C has specific operator() 'callback' type
18 // (uses detection idiom SFINAE; in C++20 just use a requires clause)
19 //
20 template<class C, typename FuncSig, typename = void>
21 struct hasCallback : std::false_type {};
22 
23 template<class C, typename FuncSig> // remove_cv used as type_identity
24 struct hasCallback<C, FuncSig, std::void_t<decltype(std::remove_cv_t<FuncSig C::*>{&C::operator()})>> : std::true_type {
25 };
26 
27 template<class C, typename... FuncSig>
28 inline constexpr bool has_callback = (hasCallback<C, FuncSig>::value || ...);
29 
30 template<typename Result>
31 using DispatchResult = std::conditional_t<std::is_void_v<Result>, bool, std::optional<Result>>;
32 
33 template<typename Result, typename Erased, typename Dispatcher, typename Iterator>
34 DispatchResult<Result> do_dispatch(Erased& n, Dispatcher& d, typename Iterator::Position& i, // NOLINT
35  bool& no_match_so_far); // NOLINT
36 
37 template<typename Result, typename Type, typename Erased, typename Dispatcher, typename Iterator>
38 DispatchResult<Result> do_dispatch_one(Erased& n, const std::type_info& ti, Dispatcher& d,
39  typename Iterator::Position& i, bool& no_match_so_far) { // NOLINT
40  if ( ti != typeid(Type) )
41  return {};
42 
43  using T = std::conditional_t<std::is_const_v<Erased>, const Type, Type>;
44 
45  using CBc = Result(T const&);
46  using CBcIP = Result(T const&, typename Iterator::Position);
47 
48  auto& x = n.template as<Type>();
49  DispatchResult<Result> result = {};
50 
51  // Prefer most specific callback, so climb down first.
52  if constexpr ( std::is_base_of_v<util::type_erasure::trait::TypeErased, Type> )
53  result = do_dispatch<Result, T, Dispatcher, Iterator>(x, d, i, no_match_so_far);
54 
55  if constexpr ( std::is_void_v<Result> ) {
56  // No result expected, call all matching methods.
57  (void)result;
58  if constexpr ( has_callback<Dispatcher, CBc> ) {
59  no_match_so_far = false;
60  d(x);
61  }
62 
63  if constexpr ( has_callback<Dispatcher, CBcIP> ) {
64  no_match_so_far = false;
65  d(x, i);
66  }
67 
68  return false; // Continue matching.
69  }
70 
71  else { // NOLINT
72  // Single result expected, stop at first matching method.
73  if ( result )
74  return result;
75 
76  if constexpr ( has_callback<Dispatcher, CBc> ) {
77  no_match_so_far = false;
78  return {d(x)};
79  }
80 
81  if constexpr ( has_callback<Dispatcher, CBcIP> ) {
82  no_match_so_far = false;
83  return {d(x, i)};
84  }
85  }
86 
87  return {};
88 }
89 
90 template<typename Result, typename Erased, typename Dispatcher, typename Iterator>
91 DispatchResult<Result> do_dispatch(Erased& n, Dispatcher& d, typename Iterator::Position& i, // NOLINT
92  bool& no_match_so_far) { // NOLINT
93  auto& tn = n.typeid_();
94 
95 #ifdef VISITOR_DISPATCHERS
96  VISITOR_DISPATCHERS
97 #else
98 #error "VISITOR_DISPATCHERS not defined, did you include 'autogen/dispatchers.h'?"
99 #endif
100 
101  if constexpr ( std::is_void_v<Result> )
102  return ! no_match_so_far;
103  else // NOLINT
104  return std::nullopt;
105 }
106 
108 
109 template<typename Erased, Order order, bool isConst>
110 class Iterator {
111 public:
112  using E = std::conditional_t<isConst, const Erased&, Erased&>;
115 
116  Iterator() = default;
117  Iterator(E root) { _path.emplace_back(root, -1); }
118 
119  Iterator(const Iterator& other) = default;
120  Iterator(Iterator&& other) noexcept = default;
121 
122  ~Iterator() = default;
123 
124  Iterator& operator++() {
125  next();
126  return *this;
127  }
128  Position operator*() const { return current(); }
129 
130  Iterator& operator=(const Iterator& other) = default;
131  Iterator& operator=(Iterator&& other) noexcept = default;
132  bool operator==(const Iterator& other) const { return _path.empty() && other._path.empty(); }
133 
134  bool operator!=(const Iterator& other) const { return ! (*this == other); }
135 
136 private:
137  void next() {
138  if ( _path.empty() )
139  return;
140 
141  auto& p = _path.back();
142  p.child += 1;
143 
144  if ( p.child == -1 ) {
145  if ( order == Order::Pre || p.node.pruneWalk() )
146  return;
147 
148  next();
149  return;
150  }
151 
152  if ( p.node.pruneWalk() ) {
153  _path.pop_back();
154  next();
155  return;
156  }
157 
158  assert(p.child >= 0);
159 
160  if ( p.child < static_cast<int>(p.node.children().size()) ) {
161  _path.emplace_back(p.node.children()[p.child], -2);
162  next();
163  return;
164  }
165 
166  if ( p.child == static_cast<int>(p.node.children().size()) ) {
167  if constexpr ( order == Order::Post )
168  return;
169 
170  p.child += 1;
171  }
172 
173  if ( p.child > static_cast<int>(p.node.children().size()) ) {
174  _path.pop_back();
175  next();
176  return;
177  }
178  }
179 
180  Position current() const {
181  if ( _path.empty() )
182  throw std::runtime_error("invalid reference of visitor's iterator");
183 
184  auto& p = _path.back();
185 
186  if ( p.child < 0 ) // pre order
187  return Position{.node = p.node, .path = _path};
188 
189  if ( p.child == static_cast<int>(p.node.children().size()) ) // post order
190  return Position{.node = p.node, .path = _path};
191 
192  assert(p.child < static_cast<int>(p.node.children().size()));
193  return Position{.node = p.node.children()[p.child], .path = _path};
194  }
195 
196  std::vector<Location> _path;
197 };
198 
199 template<typename Visitor>
200 class ConstView {
201 public:
202  using iterator_t = typename Visitor::const_iterator_t;
203 
204  ConstView(const typename Visitor::erased_t& root) : _root(root) {}
205 
206  auto begin() {
207  if constexpr ( Visitor::order_ == Order::Pre )
208  return iterator_t(_root);
209 
210  return ++iterator_t(_root);
211  }
212 
213  auto end() { return iterator_t(); }
214 
215 private:
216  const typename Visitor::erased_t& _root;
217 };
218 
219 template<typename Visitor>
221 public:
222  using iterator_t = typename Visitor::iterator_t;
223 
224  NonConstView(typename Visitor::erased_t& root) : _root(root) {}
225 
226  auto begin() {
227  if constexpr ( Visitor::order_ == Order::Pre )
228  return iterator_t(_root);
229 
230  return ++iterator_t(_root);
231  }
232 
233  auto end() { return iterator_t(); }
234 
235 private:
236  typename Visitor::erased_t& _root;
237 };
238 
247 template<typename Result, typename Dispatcher, typename Erased, Order order>
248 class Visitor {
249 public:
250  using result_t = Result;
251  using erased_t = Erased;
253  using visitor_t = Dispatcher;
256  using position_t = typename iterator_t::Position;
257  using const_position_t = typename const_iterator_t::Position;
258  static const Order order_ = order;
259 
260  Visitor() = default;
261  virtual ~Visitor() = default;
262 
263  virtual void preDispatch(const Erased& /* n */, int /* level */){};
264 
266  auto dispatch(position_t& i) {
267  bool no_match_so_far = true;
268  preDispatch(i.node, i.pathLength());
269  return do_dispatch<Result, Erased, Dispatcher, iterator_t>(i.node, *static_cast<Dispatcher*>(this), i,
270  no_match_so_far);
271  }
272 
274  auto dispatch(const_position_t& i) {
275  bool no_match_so_far = true;
276  preDispatch(i.node, i.pathLength());
277  return do_dispatch<Result, const Erased, Dispatcher, const_iterator_t>(i.node, *static_cast<Dispatcher*>(this),
278  i, no_match_so_far);
279  }
280 
287  auto dispatch(Erased* n) {
288  bool no_match_so_far = true;
289  std::vector<typename iterator_t::Location> path;
290  position_t i = {*n, path};
291  preDispatch(*n, 0);
292  return do_dispatch<Result, Erased, Dispatcher, iterator_t>(*n, *static_cast<Dispatcher*>(this), i,
293  no_match_so_far);
294  }
295 
302  auto dispatch(const Erased& n) {
303  Erased n_ = n;
304  bool no_match_so_far = true;
305  std::vector<typename iterator_t::Location> path;
306  position_t i = {n_, path};
307  preDispatch(n_, 0);
308  return do_dispatch<Result, Erased, Dispatcher, iterator_t>(n_, *static_cast<Dispatcher*>(this), i,
309  no_match_so_far);
310  }
311 
321  auto walk(const Erased& root) { return ConstView<Visitor>(root); }
322 
332  auto walk(Erased* root) { return NonConstView<Visitor>(*root); }
333 };
334 
335 using NoDispatcher = struct {};
336 
337 } // namespace detail::visitor
338 
342 namespace visitor {
343 template<typename Result = void, typename Dispatcher = detail::visitor::NoDispatcher, typename Erased = Node>
345 
349 template<typename Result = void, typename Dispatcher = detail::visitor::NoDispatcher, typename Erased = Node>
351 
352 } // namespace visitor
353 
354 } // namespace hilti
auto walk(Erased *root)
Definition: visitor.h:332
Definition: visitor-types.h:28
Definition: optional.h:79
auto dispatch(const_position_t &i)
Definition: visitor.h:274
E node
Definition: visitor-types.h:33
auto dispatch(position_t &i)
Definition: visitor.h:266
Definition: visitor.h:21
Definition: visitor.h:220
auto walk(const Erased &root)
Definition: visitor.h:321
Definition: type.h:159
Definition: visitor.h:110
Definition: visitor.h:200
auto dispatch(const Erased &n)
Definition: visitor.h:302
Definition: visitor.h:248
auto dispatch(Erased *n)
Definition: visitor.h:287
Definition: visitor-types.h:14
Definition: result.h:67