Spicy
node.h
1 // Copyright (c) 2020-2021 by the Zeek Project. See LICENSE for details.
2 
3 #pragma once
4 
5 #include <algorithm>
6 #include <cinttypes>
7 #include <functional>
8 #include <iostream>
9 #include <list>
10 #include <map>
11 #include <memory>
12 #include <optional>
13 #include <set>
14 #include <string>
15 #include <type_traits>
16 #include <utility>
17 #include <variant>
18 #include <vector>
19 
20 namespace hilti::trait {
21 class isNode {};
22 } // namespace hilti::trait
23 
24 #include <hilti/ast/meta.h>
25 #include <hilti/ast/node-ref.h>
26 #include <hilti/ast/scope.h>
27 #include <hilti/base/type_erase.h>
28 #include <hilti/base/util.h>
29 
30 namespace hilti {
31 
32 class Node;
33 
34 namespace node {
35 
36 template<typename T>
37 class Range;
38 
39 template<typename T>
40 class Set;
41 
42 namespace detail {
43 
45 using PropertyValue = std::variant<bool, const char*, double, int, int64_t, unsigned int, uint64_t, std::string>;
46 
48 inline std::string to_string(const PropertyValue& v) {
49  struct Visitor {
50  auto operator()(bool s) { return std::string(s ? "true" : "false"); }
51  auto operator()(const char* s) { return util::escapeUTF8(s); }
52  auto operator()(double d) { return util::fmt("%.6f", d); }
53  auto operator()(int i) { return util::fmt("%d", i); }
54  auto operator()(int64_t i) { return util::fmt("%" PRId64, i); }
55  auto operator()(const std::string& s) { return util::escapeUTF8(s); }
56  auto operator()(unsigned int u) { return util::fmt("%u", u); }
57  auto operator()(uint64_t u) { return util::fmt("%" PRIu64, u); }
58  };
59 
60  return std::visit(Visitor(), v);
61 };
62 
63 } // namespace detail
64 
66 enum class ErrorPriority {
67  High = 3,
68  Normal = 2,
69  Low = 1,
70  NoError = 0
71 };
72 
73 inline bool operator<(ErrorPriority x, ErrorPriority y) {
74  return static_cast<std::underlying_type_t<ErrorPriority>>(x) <
75  static_cast<std::underlying_type_t<ErrorPriority>>(y);
76 }
77 
79 struct Error {
80  std::string message;
82  std::vector<std::string> context;
83  ErrorPriority priority = ErrorPriority::Normal;
85  // Comparison considers message & location, so that we can unique based
86  // on those two.
87  bool operator<(const Error& other) const {
88  return std::tie(message, location) < std::tie(other.message, other.location);
89  }
90 };
91 
97 using Properties = std::map<std::string, node::detail::PropertyValue>;
98 
99 namespace detail {
100 #include <hilti/autogen/__node.h>
101 
102 } // namespace detail
103 } // namespace node
104 
111 class Node final : public node::detail::Node {
112 public:
114  template<typename T, typename std::enable_if_t<std::is_base_of<trait::isNode, T>::value>* = nullptr>
115  Node(T t) : node::detail::Node(std::move(t)) {}
116 
117  Node(const Node& other) : node::detail::Node::Node(other), _scope(other._scope) {}
118 
119  Node(Node&& other) noexcept
120  : node::detail::Node::Node(std::move(other)),
121  _control_ptr(std::move(other._control_ptr)),
122  _scope(std::move(other._scope)),
123  _errors(std::move(other._errors)) {
124  if ( _control_ptr )
125  _control_ptr->_node = this;
126  }
127 
128  Node() = delete;
129 
130  ~Node() final {
131  if ( _control_ptr )
132  _control_ptr->_node = nullptr;
133  }
134 
142  uint64_t rid() const { return _control_ptr ? _control_ptr->_rid : 0; }
143 
149  std::string renderedRid() const { return rid() ? util::fmt("%%%" PRIu64, rid()) : "%???"; };
150 
158  if ( ! _scope )
159  _scope = make_intrusive<Scope>();
160 
161  return _scope;
162  }
163 
167  void setScope(IntrusivePtr<Scope> new_scope) { _scope = std::move(new_scope); }
168 
170  void clearScope() {
171  if ( ! _scope )
172  return;
173 
174  // Don't just clear the items because the scope might be shared with
175  // other nodes.
176  _scope = make_intrusive<Scope>();
177  }
178 
180  std::vector<node::Error> errors() const {
181  if ( _errors )
182  return *_errors;
183  else
184  return {};
185  }
186 
188  bool hasErrors() const { return _errors && _errors->size(); }
189 
191  void clearErrors() {
192  if ( _errors )
193  _errors.reset();
194  }
195 
204  void addError(std::string msg, std::vector<std::string> context = {}) {
205  addError(std::move(msg), location(), std::move(context));
206  }
207 
217  void addError(std::string msg, node::ErrorPriority priority, std::vector<std::string> context = {}) {
218  addError(std::move(msg), location(), priority, std::move(context));
219  }
220 
229  void addError(std::string msg, const Location& l, std::vector<std::string> context = {}) {
230  addError(std::move(msg), location(), node::ErrorPriority::Normal, std::move(context));
231  }
232 
241  void addError(std::string msg, Location l, node::ErrorPriority priority, std::vector<std::string> context = {}) {
242  node::Error error;
243  error.message = std::move(msg);
244  error.location = std::move(l);
245  error.context = std::move(context);
246  error.priority = priority;
247 
248  if ( ! _errors )
249  _errors = std::make_unique<std::vector<node::Error>>();
250 
251  _errors->push_back(std::move(error));
252  }
253 
258  void destroyChildren();
259 
267  std::string render(bool include_location = true) const;
268 
279  void print(std::ostream& out, bool compact = false) const;
280 
285  std::string print() const;
286 
288  const Location& location() const { return meta().location(); }
289 
291  template<typename T>
292  void assertIsA() {
293  if ( ! isA<T>() ) {
294  std::cerr << "Assertion failure: Node expected to be a " << typeid(T).name() << " but is a "
295  << typeid_().name() << std::endl;
296  util::abort_with_backtrace();
297  }
298  }
299 
301  operator std::string() const { return print(); }
302 
307  Node& operator=(const Node& n) {
308  if ( &n == this )
309  return *this;
310 
311  _scope = n._scope;
312  node::detail::ErasedBase::operator=(n);
313  return *this;
314  }
315 
320  Node& operator=(Node&& n) noexcept {
321  _scope = std::move(n._scope);
322  node::detail::ErasedBase::operator=(std::move(n));
323  return *this;
324  }
325 
331  template<typename T>
332  Node& operator=(const T& t) {
333  node::detail::ErasedBase::operator=(to_node(t));
334  return *this;
335  }
336 
337 private:
338  friend class NodeRef;
339 
340  // Returns (and potentially creates) the control block for this node that
341  // `NodeRef` uses to maintain links to it.
342  IntrusivePtr<node_ref::detail::Control> _control() const {
343  if ( ! _control_ptr )
344  _control_ptr = make_intrusive<node_ref::detail::Control>(this);
345 
346  return _control_ptr;
347  }
348 
349  mutable IntrusivePtr<node_ref::detail::Control> _control_ptr = nullptr;
350  mutable IntrusivePtr<Scope> _scope = nullptr;
351  std::unique_ptr<std::vector<node::Error>> _errors = nullptr;
352 };
353 
359 class NodeBase : public trait::isNode {
360 public:
366  NodeBase(Meta meta) : _meta(std::move(meta)) {}
367 
374  NodeBase(std::vector<Node> children, Meta meta) : _meta(std::move(meta)) {
375  for ( auto& c : children )
376  addChild(std::move(c));
377  }
378 
379  NodeBase() = default;
380 
388  template<typename T>
389  const T& child(int i) const {
390  return _children[i].as<T>();
391  }
392 
399  template<typename T>
400  void assertChildIsA(int i) {
401  _children[i].template assertIsA<T>();
402  }
403 
413  template<typename T>
414  auto children(int begin, int end) const {
415  auto end_ = (end < 0) ? _children.end() : _children.begin() + end;
416  return hilti::node::Range<T>(_children.begin() + begin, end_);
417  }
418 
427  auto childRefs(int begin, int end) {
428  auto end_ = (end < 0) ? _children.end() : _children.begin() + end;
429 
430  std::vector<NodeRef> refs;
431  for ( auto c = _children.begin(); c != end_; c = std::next(c) )
432  refs.emplace_back(*c);
433 
434  return refs;
435  }
436 
443  template<typename T>
444  hilti::node::Set<T> childrenOfType() const;
445 
453  template<typename T>
454  std::vector<NodeRef> childRefsOfType() const;
455 
460  void addChild(Node n) {
461  if ( _meta.location() && ! n.location() ) {
462  auto m = n.meta();
463  m.setLocation(_meta.location());
464  n.setMeta(std::move(m));
465  }
466 
467  _children.push_back(std::move(n));
468  }
469 
471  const auto& children() const { return _children; }
473  auto& children() { return _children; }
475  auto& meta() const { return _meta; }
477  void setMeta(Meta m) { _meta = std::move(m); }
479  bool pruneWalk() const { return false; }
480 
481 private:
482  std::vector<::hilti::Node> _children;
483  Meta _meta;
484  NodeRef _orig;
485 };
486 
487 namespace node {
488 
491 public:
493  auto properties() const { return node::Properties{}; }
494 
499  static None create() { return None(); }
500 
501 private:
502  None() : NodeBase(Meta()) {}
503 };
504 
506 extern const Node none;
507 
513 template<typename T>
515  using BaseIterator = std::vector<Node>::const_iterator;
516 
517 public:
518  using value_type = BaseIterator::value_type;
519  using difference_type = BaseIterator::difference_type;
520  using pointer = BaseIterator::pointer;
521  using reference = BaseIterator::reference;
522  using iterator_category = BaseIterator::iterator_category;
523 
524  explicit RangeIterator(BaseIterator i) : _iter(i) {}
525  RangeIterator(const RangeIterator& other) = default;
526  RangeIterator(RangeIterator&& other) noexcept = default;
527  RangeIterator() {}
528  ~RangeIterator() = default;
529 
530  const Node& node() const { return *_iter; }
531 
532  RangeIterator& operator=(const RangeIterator& other) = default;
533  RangeIterator& operator=(RangeIterator&& other) noexcept = default;
534  const T& operator*() const { return value(); }
535  const T* operator->() const { return &value(); }
536  bool operator==(const RangeIterator& other) const { return _iter == other._iter; }
537  bool operator!=(const RangeIterator& other) const { return ! (*this == other); }
538 
539  RangeIterator operator++(int) {
540  auto x = RangeIterator(_iter);
541  ++_iter;
542  return x;
543  }
544 
545  RangeIterator& operator++() {
546  ++_iter;
547  return *this;
548  }
549 
550  RangeIterator& operator+=(difference_type i) {
551  _iter += i;
552  return *this;
553  }
554 
555  RangeIterator& operator-=(difference_type i) {
556  _iter -= i;
557  return *this;
558  }
559 
560  difference_type operator-(const RangeIterator& other) const { return _iter - other._iter; }
561  RangeIterator operator-(difference_type i) const { return RangeIterator(_iter - i); }
562  RangeIterator operator+(difference_type i) const { return RangeIterator(_iter + i); }
563 
564 private:
565  const T& value() const { return (*_iter).template as<std::remove_const_t<T>>(); }
566 
567  BaseIterator _iter;
568 };
569 
575 template<typename T>
576 class Range {
577 public:
578  using iterator = RangeIterator<T>;
579  using const_iterator = RangeIterator<T>;
580 
581  explicit Range() {}
582  Range(std::vector<Node>::const_iterator begin, std::vector<Node>::const_iterator end) : _begin(begin), _end(end) {}
583 
584  explicit Range(const std::vector<Node>& nodes) : Range(nodes.begin(), nodes.end()) {}
585 
586  Range(const Range& other) = default;
587  Range(Range&& other) noexcept = default;
588  ~Range() = default;
589 
590  auto begin() const { return const_iterator(_begin); }
591  auto end() const { return const_iterator(_end); }
592  size_t size() const { return static_cast<size_t>(_end - _begin); }
593  const T& front() const { return *_begin; }
594  bool empty() const { return _begin == _end; }
595 
600  std::vector<T> copy() const {
601  std::vector<T> x;
602  for ( auto i = _begin; i != _end; i++ )
603  x.push_back(*i);
604 
605  return x;
606  }
607 
608  const T& operator[](size_t i) const {
609  assert(static_cast<typename RangeIterator<T>::difference_type>(i) < std::distance(_begin, _end));
610  return *(_begin + i);
611  }
612 
613  bool operator==(const Range& other) const {
614  if ( this == &other )
615  return true;
616 
617  if ( size() != other.size() )
618  return false;
619 
620  auto x = _begin;
621  auto y = other._begin;
622  while ( x != _end ) {
623  if ( ! (*x++ == *y++) )
624  return false;
625  }
626 
627  return true;
628  }
629 
630  Range& operator=(const Range& other) = default;
631  Range& operator=(Range&& other) noexcept = default;
632 
633 private:
634  RangeIterator<T> _begin;
635  RangeIterator<T> _end;
636 };
637 
644 template<typename T>
645 class SetIterator {
646  using BaseIterator = typename std::vector<std::reference_wrapper<const T>>::const_iterator;
647 
648 public:
649  // Previously provided by std::iterator
650  using value_type = T;
651  using difference_type = typename BaseIterator::difference_type;
652  using pointer = typename BaseIterator::pointer;
653  using reference = typename BaseIterator::reference;
654  using iterator_category = typename BaseIterator::iterator_category;
655 
656  explicit SetIterator(BaseIterator i) : _iter(std::move(i)) {}
657  SetIterator(const SetIterator& other) = default;
658  SetIterator(SetIterator&& other) noexcept = default;
659  SetIterator() {}
660  ~SetIterator() = default;
661 
662  const Node& node() const { return *_iter; }
663 
664  SetIterator& operator=(const SetIterator& other) = default;
665  SetIterator& operator=(SetIterator&& other) noexcept = default;
666  const T& operator*() const { return value(); }
667  const T* operator->() const { return &value(); }
668  bool operator==(const SetIterator& other) const { return _iter == other._iter; }
669  bool operator!=(const SetIterator& other) const { return ! (*this == other); }
670 
671  SetIterator operator++(int) {
672  auto x = SetIterator(_iter);
673  ++_iter;
674  return x;
675  }
676 
677  SetIterator& operator++() {
678  ++_iter;
679  return *this;
680  }
681 
682  SetIterator& operator+=(difference_type i) {
683  _iter += i;
684  return *this;
685  }
686 
687  SetIterator& operator-=(difference_type i) {
688  _iter -= i;
689  return *this;
690  }
691 
692  difference_type operator-(const SetIterator& other) const { return _iter - other._iter; }
693  SetIterator operator-(difference_type i) const { return SetIterator(_iter - i); }
694  SetIterator operator+(difference_type i) const { return SetIterator(_iter + i); }
695 
696 private:
697  const T& value() const { return ((*_iter).get()); }
698 
699  BaseIterator _iter;
700 };
701 
708 template<typename T>
709 class Set {
710 public:
711  using iterator = SetIterator<T>;
712  using const_iterator = SetIterator<T>;
713 
714  Set() {}
715  Set(const Set& other) = default;
716  Set(Set&& other) noexcept = default;
717  ~Set() = default;
718 
719  auto begin() const { return const_iterator(_set.begin()); }
720  auto end() const { return const_iterator(_set.end()); }
721  size_t size() const { return _set.size(); }
722  bool empty() const { return _set.empty(); }
723  void insert(const T& t) { _set.push_back(t); }
724 
729  std::vector<T> copy() const {
730  std::vector<T> x;
731  for ( auto i = begin(); i != end(); i++ )
732  x.push_back(*i);
733 
734  return x;
735  }
736 
737  const T& operator[](size_t i) const { return *(begin() + i); }
738 
739  bool operator==(const Set& other) const {
740  if ( this == &other )
741  return true;
742 
743  if ( size() != other.size() )
744  return false;
745 
746  auto x = begin();
747  auto y = other.begin();
748  while ( x != end() ) {
749  if ( ! (*x++ == *y++) )
750  return false;
751  }
752 
753  return true;
754  }
755 
756  Set& operator=(const Set& other) = default;
757  Set& operator=(Set&& other) noexcept = default;
758 
759 private:
760  std::vector<std::reference_wrapper<const T>> _set;
761 };
762 
763 
764 } // namespace node
765 
766 inline const Node& to_node(const node::None& /* n */) { return node::none; }
767 
772 template<typename T, IF_SAME(T, Node)> // Don't allow derived classes.
773 inline Node to_node(const T& n) {
774  return n;
775 }
776 
778 template<typename T>
779 Node to_node(std::optional<T> t) {
780  if ( t )
781  return to_node(std::move(*t));
782 
783  return to_node(node::none);
784 }
785 
790 template<typename T>
791 std::vector<Node> nodes(std::vector<T> t) {
792  std::vector<Node> v;
793  v.reserve(t.size());
794  for ( const auto& i : t )
795  v.emplace_back(std::move(i));
796 
797  return v;
798 }
799 
804 template<typename T>
805 std::vector<Node> nodes(std::list<T> t) {
806  std::vector<Node> v;
807  for ( const auto& i : t )
808  v.emplace_back(std::move(i));
809 
810  return v;
811 }
812 
817 template<typename T>
818 std::vector<Node> nodes(hilti::node::Range<T> t) {
819  std::vector<Node> v;
820  v.reserve(t.size());
821  for ( const auto& i : t )
822  v.emplace_back(std::move(i));
823 
824  return v;
825 }
826 
828 template<typename T>
829 std::vector<Node> nodes(T t) {
830  return {to_node(std::move(t))};
831 }
832 
837 template<typename T, typename... Ts>
838 std::vector<Node> nodes(T t, Ts... ts) {
839  return util::concat(std::move(nodes(t)), nodes(std::move(ts)...));
840 }
841 
848 namespace node {
849 template<typename T, typename Other, IF_DERIVED_FROM(T, trait::isNode), IF_DERIVED_FROM(Other, trait::isNode)>
850 bool isEqual(const T* this_, const Other& other) {
851  if ( const auto o = other.template tryAs<T>() )
852  return *this_ == *o;
853 
854  return false;
855 }
856 
861 template<typename X, typename F>
862 auto filter(const hilti::node::Range<X>& x, F f) {
864  for ( const auto& i : x ) {
865  if ( f(i) )
866  y.push_back(i);
867  }
868 
869  return y;
870 }
871 
876 template<typename X, typename F>
877 auto filter(const hilti::node::Set<X>& x, F f) {
879  for ( const auto& i : x ) {
880  if ( f(i) )
881  y.insert(i);
882  }
883 
884  return y;
885 }
886 
891 template<typename X, typename F>
892 auto transform(const hilti::node::Range<X>& x, F f) {
893  using Y = typename std::invoke_result_t<F, X&>;
894  std::vector<Y> y;
895  y.reserve(x.size());
896  for ( const auto& i : x )
897  y.push_back(f(i));
898 
899  return y;
900 }
901 
906 template<typename X, typename F>
907 auto transform(const hilti::node::Set<X>& x, F f) {
908  using Y = typename std::invoke_result_t<F, X&>;
909  std::vector<Y> y;
910  y.reserve(x.size());
911  for ( const auto& i : x )
912  y.push_back(f(i));
913 
914  return y;
915 }
916 
917 
918 } // namespace node
919 
921 inline std::ostream& operator<<(std::ostream& out, const Node& n) {
922  n.print(out, true);
923  return out;
924 }
925 
926 template<typename T>
928  typename hilti::node::Set<T> n;
929  for ( auto c = _children.begin(); c != _children.end(); c = std::next(c) ) {
930  if ( auto t = c->tryAs<T>() )
931  n.insert(*t);
932  }
933 
934  return n;
935 }
936 
937 template<typename T>
938 std::vector<NodeRef> NodeBase::childRefsOfType() const {
939  typename std::vector<NodeRef> n;
940  for ( auto c = _children.begin(); c != _children.end(); c = std::next(c) ) {
941  if ( c->isA<T>() )
942  n.emplace_back(*c);
943  }
944 
945  return n;
946 }
947 
948 namespace node {
949 namespace detail {
950 // Backend to NodeBase::flattenedChildren.
951 void flattenedChildren(const hilti::Node& n, node::Set<const hilti::Node>* dst);
952 } // namespace detail
953 
958 inline node::Set<const Node> flattenedChildren(const Node& n) {
960  detail::flattenedChildren(n, &dst);
961  return dst;
962 }
963 
964 } // namespace node
965 
966 } // namespace hilti
std::vector< T > copy() const
Definition: node.h:600
ErrorPriority priority
Definition: node.h:83
std::vector< std::string > context
Definition: node.h:82
uint64_t rid() const
Definition: node.h:142
bool pruneWalk() const
Definition: node.h:479
IntrusivePtr< Scope > scope() const
Definition: node.h:157
NodeBase(Meta meta)
Definition: node.h:366
Definition: node.h:37
void assertIsA()
Definition: node.h:292
void addError(std::string msg, const Location &l, std::vector< std::string > context={})
Definition: node.h:229
Node & operator=(const T &t)
Definition: node.h:332
Definition: node.h:645
const Node none
Definition: node.cc:14
auto filter(const hilti::node::Range< X > &x, F f)
Definition: node.h:862
auto childRefs(int begin, int end)
Definition: node.h:427
bool hasErrors() const
Definition: node.h:188
Definition: optional.h:79
const auto & children() const
Definition: node.h:471
static None create()
Definition: node.h:499
void addChild(Node n)
Definition: node.h:460
Definition: node.h:490
void clearScope()
Definition: node.h:170
auto & children()
Definition: node.h:473
void addError(std::string msg, std::vector< std::string > context={})
Definition: node.h:204
void setScope(IntrusivePtr< Scope > new_scope)
Definition: node.h:167
const Location & location() const
Definition: node.h:288
Location location
Definition: node.h:81
Node & operator=(Node &&n) noexcept
Definition: node.h:320
Definition: meta.h:19
std::vector< NodeRef > childRefsOfType() const
Definition: node.h:938
std::vector< T > copy() const
Definition: node.h:729
Definition: node.h:79
std::string renderedRid() const
Definition: node.h:149
Definition: node.h:40
void clearErrors()
Definition: node.h:191
void addError(std::string msg, Location l, node::ErrorPriority priority, std::vector< std::string > context={})
Definition: node.h:241
auto properties() const
Definition: node.h:493
std::vector< node::Error > errors() const
Definition: node.h:180
Definition: intrusive-ptr.h:69
auto children(int begin, int end) const
Definition: node.h:414
Definition: node.h:514
void setMeta(Meta m)
Definition: node.h:477
void print(std::ostream &out, bool compact=false) const
Definition: node.cc:103
std::map< std::string, node::detail::PropertyValue > Properties
Definition: node.h:97
std::string message
Definition: node.h:80
hilti::node::Set< T > childrenOfType() const
Definition: node.h:927
const T & child(int i) const
Definition: node.h:389
NodeBase(std::vector< Node > children, Meta meta)
Definition: node.h:374
Definition: node.h:111
Definition: node-ref.h:45
Definition: location.h:18
Definition: ctor.h:13
void addError(std::string msg, node::ErrorPriority priority, std::vector< std::string > context={})
Definition: node.h:217
Definition: node.h:21
Node & operator=(const Node &n)
Definition: node.h:307
ErrorPriority
Definition: node.h:66
auto & meta() const
Definition: node.h:475
Definition: location.h:94
Node(T t)
Definition: node.h:115
void assertChildIsA(int i)
Definition: node.h:400
Definition: node.h:359