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 constexpr ( order == Order::Pre )
146  return;
147 
148  next();
149  return;
150  }
151 
152  assert(p.child >= 0);
153 
154  if ( p.child < static_cast<int>(p.node.childs().size()) ) {
155  _path.emplace_back(p.node.childs()[p.child], -2);
156  next();
157  return;
158  }
159 
160  if ( p.child == static_cast<int>(p.node.childs().size()) ) {
161  if constexpr ( order == Order::Post )
162  return;
163 
164  p.child += 1;
165  }
166 
167  if ( p.child > static_cast<int>(p.node.childs().size()) ) {
168  _path.pop_back();
169  next();
170  return;
171  }
172  }
173 
174  Position current() const {
175  if ( _path.empty() )
176  throw std::runtime_error("invalid reference of visitor's iterator");
177 
178  auto& p = _path.back();
179 
180  if ( p.child < 0 ) // pre order
181  return Position{.node = p.node, .path = _path};
182 
183  if ( p.child == static_cast<int>(p.node.childs().size()) ) // post order
184  return Position{.node = p.node, .path = _path};
185 
186  assert(p.child < static_cast<int>(p.node.childs().size()));
187  return Position{.node = p.node.childs()[p.child], .path = _path};
188  }
189 
190  std::vector<Location> _path;
191 };
192 
193 template<typename Visitor>
194 class ConstView {
195 public:
196  using iterator_t = typename Visitor::const_iterator_t;
197 
198  ConstView(const typename Visitor::erased_t& root) : _root(root) {}
199 
200  auto begin() {
201  if constexpr ( Visitor::order_ == Order::Pre )
202  return iterator_t(_root);
203 
204  return ++iterator_t(_root);
205  }
206 
207  auto end() { return iterator_t(); }
208 
209 private:
210  const typename Visitor::erased_t& _root;
211 };
212 
213 template<typename Visitor>
215 public:
216  using iterator_t = typename Visitor::iterator_t;
217 
218  NonConstView(typename Visitor::erased_t& root) : _root(root) {}
219 
220  auto begin() {
221  if constexpr ( Visitor::order_ == Order::Pre )
222  return iterator_t(_root);
223 
224  return ++iterator_t(_root);
225  }
226 
227  auto end() { return iterator_t(); }
228 
229 private:
230  typename Visitor::erased_t& _root;
231 };
232 
241 template<typename Result, typename Dispatcher, typename Erased, Order order>
242 class Visitor {
243 public:
244  using result_t = Result;
245  using erased_t = Erased;
247  using visitor_t = Dispatcher;
250  using position_t = typename iterator_t::Position;
251  using const_position_t = typename const_iterator_t::Position;
252  static const Order order_ = order;
253 
254  Visitor() = default;
255  virtual ~Visitor() = default;
256 
257  virtual void preDispatch(const Erased& /* n */, int /* level */){};
258 
260  auto dispatch(position_t& i) {
261  bool no_match_so_far = true;
262  preDispatch(i.node, i.pathLength());
263  return do_dispatch<Result, Erased, Dispatcher, iterator_t>(i.node, *static_cast<Dispatcher*>(this), i,
264  no_match_so_far);
265  }
266 
268  auto dispatch(const_position_t& i) {
269  bool no_match_so_far = true;
270  preDispatch(i.node, i.pathLength());
271  return do_dispatch<Result, const Erased, Dispatcher, const_iterator_t>(i.node, *static_cast<Dispatcher*>(this),
272  i, no_match_so_far);
273  }
274 
281  auto dispatch(Erased* n) {
282  bool no_match_so_far = true;
283  std::vector<typename iterator_t::Location> path;
284  position_t i = {*n, path};
285  preDispatch(*n, 0);
286  return do_dispatch<Result, Erased, Dispatcher, iterator_t>(*n, *static_cast<Dispatcher*>(this), i,
287  no_match_so_far);
288  }
289 
296  auto dispatch(const Erased& n) {
297  Erased n_ = n;
298  bool no_match_so_far = true;
299  std::vector<typename iterator_t::Location> path;
300  position_t i = {n_, path};
301  preDispatch(n_, 0);
302  return do_dispatch<Result, Erased, Dispatcher, iterator_t>(n_, *static_cast<Dispatcher*>(this), i,
303  no_match_so_far);
304  }
305 
315  auto walk(const Erased& root) { return ConstView<Visitor>(root); }
316 
326  auto walk(Erased* root) { return NonConstView<Visitor>(*root); }
327 };
328 
329 using NoDispatcher = struct {};
330 
331 } // namespace detail::visitor
332 
336 namespace visitor {
337 template<typename Result = void, typename Dispatcher = detail::visitor::NoDispatcher, typename Erased = Node>
339 
343 template<typename Result = void, typename Dispatcher = detail::visitor::NoDispatcher, typename Erased = Node>
345 
346 } // namespace visitor
347 
348 } // namespace hilti
auto walk(Erased *root)
Definition: visitor.h:326
Definition: visitor-types.h:26
Definition: optional.h:79
auto dispatch(const_position_t &i)
Definition: visitor.h:268
E node
Definition: visitor-types.h:31
auto dispatch(position_t &i)
Definition: visitor.h:260
Definition: visitor.h:21
Definition: visitor.h:214
auto walk(const Erased &root)
Definition: visitor.h:315
Definition: visitor.h:110
Definition: visitor.h:194
auto dispatch(const Erased &n)
Definition: visitor.h:296
Definition: visitor.h:242
auto dispatch(Erased *n)
Definition: visitor.h:281
Definition: visitor-types.h:12
Definition: result.h:67