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/doc-string.h>
25 #include <hilti/ast/meta.h>
26 #include <hilti/ast/node-ref.h>
27 #include <hilti/ast/scope.h>
28 #include <hilti/base/type_erase.h>
29 #include <hilti/base/util.h>
30 
31 namespace hilti {
32 
33 class Node;
34 
35 namespace node {
36 
37 template<typename T>
38 class Range;
39 
40 template<typename T>
41 class Set;
42 
43 namespace detail {
44 
46 using PropertyValue = std::variant<bool, const char*, double, int, int64_t, unsigned int, uint64_t, std::string>;
47 
49 inline std::string to_string(const PropertyValue& v) {
50  struct Visitor {
51  auto operator()(bool s) { return std::string(s ? "true" : "false"); }
52  auto operator()(const char* s) { return util::escapeUTF8(s); }
53  auto operator()(double d) { return util::fmt("%.6f", d); }
54  auto operator()(int i) { return util::fmt("%d", i); }
55  auto operator()(int64_t i) { return util::fmt("%" PRId64, i); }
56  auto operator()(const std::string& s) { return util::escapeUTF8(s); }
57  auto operator()(unsigned int u) { return util::fmt("%u", u); }
58  auto operator()(uint64_t u) { return util::fmt("%" PRIu64, u); }
59  };
60 
61  return std::visit(Visitor(), v);
62 };
63 
64 } // namespace detail
65 
67 enum class ErrorPriority {
68  High = 3,
69  Normal = 2,
70  Low = 1,
71  NoError = 0
72 };
73 
74 inline bool operator<(ErrorPriority x, ErrorPriority y) {
75  return static_cast<std::underlying_type_t<ErrorPriority>>(x) <
76  static_cast<std::underlying_type_t<ErrorPriority>>(y);
77 }
78 
80 struct Error {
81  std::string message;
83  std::vector<std::string> context;
84  ErrorPriority priority = ErrorPriority::Normal;
86  // Comparison considers message & location, so that we can unique based
87  // on those two.
88  bool operator<(const Error& other) const {
89  return std::tie(message, location) < std::tie(other.message, other.location);
90  }
91 };
92 
98 using Properties = std::map<std::string, node::detail::PropertyValue>;
99 
100 namespace detail {
101 #include <hilti/autogen/__node.h>
102 
103 } // namespace detail
104 } // namespace node
105 
112 class Node final : public node::detail::Node {
113 public:
115  template<typename T, typename std::enable_if_t<std::is_base_of<trait::isNode, T>::value>* = nullptr>
116  Node(T t) : node::detail::Node(std::move(t)) {}
117 
118  Node(const Node& other) : node::detail::Node::Node(other), _scope(other._scope) {}
119 
120  Node(Node&& other) noexcept
121  : node::detail::Node::Node(std::move(other)),
122  _control_ptr(std::move(other._control_ptr)),
123  _scope(std::move(other._scope)),
124  _errors(std::move(other._errors)) {
125  if ( _control_ptr )
126  _control_ptr->_node = this;
127  }
128 
129  Node() = delete;
130 
131  ~Node() final {
132  if ( _control_ptr )
133  _control_ptr->_node = nullptr;
134  }
135 
143  uint64_t rid() const { return _control_ptr ? _control_ptr->_rid : 0; }
144 
150  std::string renderedRid() const { return rid() ? util::fmt("%%%" PRIu64, rid()) : "%???"; };
151 
159  if ( ! _scope )
160  _scope = make_intrusive<Scope>();
161 
162  return _scope;
163  }
164 
168  void setScope(IntrusivePtr<Scope> new_scope) { _scope = std::move(new_scope); }
169 
171  void clearScope() {
172  if ( ! _scope )
173  return;
174 
175  // Don't just clear the items because the scope might be shared with
176  // other nodes.
177  _scope = make_intrusive<Scope>();
178  }
179 
181  std::vector<node::Error> errors() const {
182  if ( _errors )
183  return *_errors;
184  else
185  return {};
186  }
187 
189  bool hasErrors() const { return _errors && _errors->size(); }
190 
192  void clearErrors() {
193  if ( _errors )
194  _errors.reset();
195  }
196 
205  void addError(std::string msg, std::vector<std::string> context = {}) {
206  addError(std::move(msg), location(), std::move(context));
207  }
208 
218  void addError(std::string msg, node::ErrorPriority priority, std::vector<std::string> context = {}) {
219  addError(std::move(msg), location(), priority, std::move(context));
220  }
221 
230  void addError(std::string msg, const Location& l, std::vector<std::string> context = {}) {
231  addError(std::move(msg), location(), node::ErrorPriority::Normal, std::move(context));
232  }
233 
242  void addError(std::string msg, Location l, node::ErrorPriority priority, std::vector<std::string> context = {}) {
243  node::Error error;
244  error.message = std::move(msg);
245  error.location = std::move(l);
246  error.context = std::move(context);
247  error.priority = priority;
248 
249  if ( ! _errors )
250  _errors = std::make_unique<std::vector<node::Error>>();
251 
252  _errors->push_back(std::move(error));
253  }
254 
259  void destroyChildren();
260 
268  std::string render(bool include_location = true) const;
269 
280  void print(std::ostream& out, bool compact = false) const;
281 
286  std::string print() const;
287 
289  const Location& location() const { return meta().location(); }
290 
292  template<typename T>
293  void assertIsA() {
294  if ( ! isA<T>() ) {
295  std::cerr << "Assertion failure: Node expected to be a " << typeid(T).name() << " but is a "
296  << typeid_().name() << std::endl;
297  util::abort_with_backtrace();
298  }
299  }
300 
302  operator std::string() const { return print(); }
303 
308  Node& operator=(const Node& n) {
309  if ( &n == this )
310  return *this;
311 
312  _scope = n._scope;
313  node::detail::ErasedBase::operator=(n);
314  return *this;
315  }
316 
321  Node& operator=(Node&& n) noexcept {
322  _scope = std::move(n._scope);
323  node::detail::ErasedBase::operator=(std::move(n));
324  return *this;
325  }
326 
332  template<typename T>
333  Node& operator=(const T& t) {
334  node::detail::ErasedBase::operator=(to_node(t));
335  return *this;
336  }
337 
338 private:
339  friend class NodeRef;
340 
341  // Returns (and potentially creates) the control block for this node that
342  // `NodeRef` uses to maintain links to it.
343  IntrusivePtr<node_ref::detail::Control> _control() const {
344  if ( ! _control_ptr )
345  _control_ptr = make_intrusive<node_ref::detail::Control>(this);
346 
347  return _control_ptr;
348  }
349 
350  mutable IntrusivePtr<node_ref::detail::Control> _control_ptr = nullptr;
351  mutable IntrusivePtr<Scope> _scope = nullptr;
352  std::unique_ptr<std::vector<node::Error>> _errors = nullptr;
353 };
354 
360 class NodeBase : public trait::isNode {
361 public:
367  NodeBase(Meta meta) : _meta(std::move(meta)) {}
368 
375  NodeBase(std::vector<Node> children, Meta meta) : _meta(std::move(meta)) {
376  for ( auto& c : children )
377  addChild(std::move(c));
378  }
379 
380  NodeBase() = default;
381 
389  template<typename T>
390  const T& child(int i) const {
391  return _children[i].as<T>();
392  }
393 
400  template<typename T>
401  void assertChildIsA(int i) {
402  _children[i].template assertIsA<T>();
403  }
404 
414  template<typename T>
415  auto children(int begin, int end) const {
416  auto end_ = (end < 0) ? _children.end() : _children.begin() + end;
417  return hilti::node::Range<T>(_children.begin() + begin, end_);
418  }
419 
428  auto childRefs(int begin, int end) {
429  auto end_ = (end < 0) ? _children.end() : _children.begin() + end;
430 
431  std::vector<NodeRef> refs;
432  for ( auto c = _children.begin(); c != end_; c = std::next(c) )
433  refs.emplace_back(*c);
434 
435  return refs;
436  }
437 
444  template<typename T>
445  hilti::node::Set<T> childrenOfType() const;
446 
454  template<typename T>
455  std::vector<NodeRef> childRefsOfType() const;
456 
461  void addChild(Node n) {
462  if ( _meta.location() && ! n.location() ) {
463  auto m = n.meta();
464  m.setLocation(_meta.location());
465  n.setMeta(std::move(m));
466  }
467 
468  _children.push_back(std::move(n));
469  }
470 
472  const auto& children() const { return _children; }
474  auto& children() { return _children; }
476  auto& meta() const { return _meta; }
478  void setMeta(Meta m) { _meta = std::move(m); }
480  bool pruneWalk() const { return false; }
481 
482 private:
483  std::vector<::hilti::Node> _children;
484  Meta _meta;
485  NodeRef _orig;
486 };
487 
488 namespace node {
489 
492 public:
494  const std::optional<DocString>& documentation() const { return _doc; }
495 
497  void clearDocumentation() { _doc.reset(); }
498 
501  if ( doc )
502  _doc = std::move(doc);
503  else
504  _doc.reset();
505  }
506 
507 private:
508  std::optional<DocString> _doc;
509 };
510 
513 public:
515  auto properties() const { return node::Properties{}; }
516 
521  static None create() { return None(); }
522 
523 private:
524  None() : NodeBase(Meta()) {}
525 };
526 
528 extern const Node none;
529 
535 template<typename T>
537  using BaseIterator = std::vector<Node>::const_iterator;
538 
539 public:
540  using value_type = BaseIterator::value_type;
541  using difference_type = BaseIterator::difference_type;
542  using pointer = BaseIterator::pointer;
543  using reference = BaseIterator::reference;
544  using iterator_category = BaseIterator::iterator_category;
545 
546  explicit RangeIterator(BaseIterator i) : _iter(i) {}
547  RangeIterator(const RangeIterator& other) = default;
548  RangeIterator(RangeIterator&& other) noexcept = default;
549  RangeIterator() {}
550  ~RangeIterator() = default;
551 
552  const Node& node() const { return *_iter; }
553 
554  RangeIterator& operator=(const RangeIterator& other) = default;
555  RangeIterator& operator=(RangeIterator&& other) noexcept = default;
556  const T& operator*() const { return value(); }
557  const T* operator->() const { return &value(); }
558  bool operator==(const RangeIterator& other) const { return _iter == other._iter; }
559  bool operator!=(const RangeIterator& other) const { return ! (*this == other); }
560 
561  RangeIterator operator++(int) {
562  auto x = RangeIterator(_iter);
563  ++_iter;
564  return x;
565  }
566 
567  RangeIterator& operator++() {
568  ++_iter;
569  return *this;
570  }
571 
572  RangeIterator& operator+=(difference_type i) {
573  _iter += i;
574  return *this;
575  }
576 
577  RangeIterator& operator-=(difference_type i) {
578  _iter -= i;
579  return *this;
580  }
581 
582  difference_type operator-(const RangeIterator& other) const { return _iter - other._iter; }
583  RangeIterator operator-(difference_type i) const { return RangeIterator(_iter - i); }
584  RangeIterator operator+(difference_type i) const { return RangeIterator(_iter + i); }
585 
586 private:
587  const T& value() const { return (*_iter).template as<std::remove_const_t<T>>(); }
588 
589  BaseIterator _iter;
590 };
591 
597 template<typename T>
598 class Range {
599 public:
600  using iterator = RangeIterator<T>;
601  using const_iterator = RangeIterator<T>;
602 
603  explicit Range() {}
604  Range(std::vector<Node>::const_iterator begin, std::vector<Node>::const_iterator end) : _begin(begin), _end(end) {}
605 
606  explicit Range(const std::vector<Node>& nodes) : Range(nodes.begin(), nodes.end()) {}
607 
608  Range(const Range& other) = default;
609  Range(Range&& other) noexcept = default;
610  ~Range() = default;
611 
612  auto begin() const { return const_iterator(_begin); }
613  auto end() const { return const_iterator(_end); }
614  size_t size() const { return static_cast<size_t>(_end - _begin); }
615  const T& front() const { return *_begin; }
616  bool empty() const { return _begin == _end; }
617 
622  std::vector<T> copy() const {
623  std::vector<T> x;
624  for ( auto i = _begin; i != _end; i++ )
625  x.push_back(*i);
626 
627  return x;
628  }
629 
630  const T& operator[](size_t i) const {
631  assert(static_cast<typename RangeIterator<T>::difference_type>(i) < std::distance(_begin, _end));
632  return *(_begin + i);
633  }
634 
635  bool operator==(const Range& other) const {
636  if ( this == &other )
637  return true;
638 
639  if ( size() != other.size() )
640  return false;
641 
642  auto x = _begin;
643  auto y = other._begin;
644  while ( x != _end ) {
645  if ( ! (*x++ == *y++) )
646  return false;
647  }
648 
649  return true;
650  }
651 
652  Range& operator=(const Range& other) = default;
653  Range& operator=(Range&& other) noexcept = default;
654 
655 private:
656  RangeIterator<T> _begin;
657  RangeIterator<T> _end;
658 };
659 
666 template<typename T>
667 class SetIterator {
668  using BaseIterator = typename std::vector<std::reference_wrapper<const T>>::const_iterator;
669 
670 public:
671  // Previously provided by std::iterator
672  using value_type = T;
673  using difference_type = typename BaseIterator::difference_type;
674  using pointer = typename BaseIterator::pointer;
675  using reference = typename BaseIterator::reference;
676  using iterator_category = typename BaseIterator::iterator_category;
677 
678  explicit SetIterator(BaseIterator i) : _iter(std::move(i)) {}
679  SetIterator(const SetIterator& other) = default;
680  SetIterator(SetIterator&& other) noexcept = default;
681  SetIterator() {}
682  ~SetIterator() = default;
683 
684  const Node& node() const { return *_iter; }
685 
686  SetIterator& operator=(const SetIterator& other) = default;
687  SetIterator& operator=(SetIterator&& other) noexcept = default;
688  const T& operator*() const { return value(); }
689  const T* operator->() const { return &value(); }
690  bool operator==(const SetIterator& other) const { return _iter == other._iter; }
691  bool operator!=(const SetIterator& other) const { return ! (*this == other); }
692 
693  SetIterator operator++(int) {
694  auto x = SetIterator(_iter);
695  ++_iter;
696  return x;
697  }
698 
699  SetIterator& operator++() {
700  ++_iter;
701  return *this;
702  }
703 
704  SetIterator& operator+=(difference_type i) {
705  _iter += i;
706  return *this;
707  }
708 
709  SetIterator& operator-=(difference_type i) {
710  _iter -= i;
711  return *this;
712  }
713 
714  difference_type operator-(const SetIterator& other) const { return _iter - other._iter; }
715  SetIterator operator-(difference_type i) const { return SetIterator(_iter - i); }
716  SetIterator operator+(difference_type i) const { return SetIterator(_iter + i); }
717 
718 private:
719  const T& value() const { return ((*_iter).get()); }
720 
721  BaseIterator _iter;
722 };
723 
730 template<typename T>
731 class Set {
732 public:
733  using iterator = SetIterator<T>;
734  using const_iterator = SetIterator<T>;
735 
736  Set() {}
737  Set(const Set& other) = default;
738  Set(Set&& other) noexcept = default;
739  ~Set() = default;
740 
741  auto begin() const { return const_iterator(_set.begin()); }
742  auto end() const { return const_iterator(_set.end()); }
743  size_t size() const { return _set.size(); }
744  bool empty() const { return _set.empty(); }
745  void insert(const T& t) { _set.push_back(t); }
746 
751  std::vector<T> copy() const {
752  std::vector<T> x;
753  for ( auto i = begin(); i != end(); i++ )
754  x.push_back(*i);
755 
756  return x;
757  }
758 
759  const T& operator[](size_t i) const { return *(begin() + i); }
760 
761  bool operator==(const Set& other) const {
762  if ( this == &other )
763  return true;
764 
765  if ( size() != other.size() )
766  return false;
767 
768  auto x = begin();
769  auto y = other.begin();
770  while ( x != end() ) {
771  if ( ! (*x++ == *y++) )
772  return false;
773  }
774 
775  return true;
776  }
777 
778  Set& operator=(const Set& other) = default;
779  Set& operator=(Set&& other) noexcept = default;
780 
781 private:
782  std::vector<std::reference_wrapper<const T>> _set;
783 };
784 
785 
786 } // namespace node
787 
788 inline const Node& to_node(const node::None& /* n */) { return node::none; }
789 
794 template<typename T, IF_SAME(T, Node)> // Don't allow derived classes.
795 inline Node to_node(const T& n) {
796  return n;
797 }
798 
800 template<typename T>
801 Node to_node(std::optional<T> t) {
802  if ( t )
803  return to_node(std::move(*t));
804 
805  return to_node(node::none);
806 }
807 
812 template<typename T>
813 std::vector<Node> nodes(std::vector<T> t) {
814  std::vector<Node> v;
815  v.reserve(t.size());
816  for ( const auto& i : t )
817  v.emplace_back(std::move(i));
818 
819  return v;
820 }
821 
826 template<typename T>
827 std::vector<Node> nodes(std::list<T> t) {
828  std::vector<Node> v;
829  for ( const auto& i : t )
830  v.emplace_back(std::move(i));
831 
832  return v;
833 }
834 
839 template<typename T>
840 std::vector<Node> nodes(hilti::node::Range<T> t) {
841  std::vector<Node> v;
842  v.reserve(t.size());
843  for ( const auto& i : t )
844  v.emplace_back(std::move(i));
845 
846  return v;
847 }
848 
850 template<typename T>
851 std::vector<Node> nodes(T t) {
852  return {to_node(std::move(t))};
853 }
854 
859 template<typename T, typename... Ts>
860 std::vector<Node> nodes(T t, Ts... ts) {
861  return util::concat(std::move(nodes(t)), nodes(std::move(ts)...));
862 }
863 
870 namespace node {
871 template<typename T, typename Other, IF_DERIVED_FROM(T, trait::isNode), IF_DERIVED_FROM(Other, trait::isNode)>
872 bool isEqual(const T* this_, const Other& other) {
873  if ( const auto o = other.template tryAs<T>() )
874  return *this_ == *o;
875 
876  return false;
877 }
878 
883 template<typename X, typename F>
884 auto filter(const hilti::node::Range<X>& x, F f) {
886  for ( const auto& i : x ) {
887  if ( f(i) )
888  y.push_back(i);
889  }
890 
891  return y;
892 }
893 
898 template<typename X, typename F>
899 auto filter(const hilti::node::Set<X>& x, F f) {
901  for ( const auto& i : x ) {
902  if ( f(i) )
903  y.insert(i);
904  }
905 
906  return y;
907 }
908 
913 template<typename X, typename F>
914 auto transform(const hilti::node::Range<X>& x, F f) {
915  using Y = typename std::invoke_result_t<F, X&>;
916  std::vector<Y> y;
917  y.reserve(x.size());
918  for ( const auto& i : x )
919  y.push_back(f(i));
920 
921  return y;
922 }
923 
928 template<typename X, typename F>
929 auto transform(const hilti::node::Set<X>& x, F f) {
930  using Y = typename std::invoke_result_t<F, X&>;
931  std::vector<Y> y;
932  y.reserve(x.size());
933  for ( const auto& i : x )
934  y.push_back(f(i));
935 
936  return y;
937 }
938 
939 
940 } // namespace node
941 
943 inline std::ostream& operator<<(std::ostream& out, const Node& n) {
944  n.print(out, true);
945  return out;
946 }
947 
948 template<typename T>
950  typename hilti::node::Set<T> n;
951  for ( auto c = _children.begin(); c != _children.end(); c = std::next(c) ) {
952  if ( auto t = c->tryAs<T>() )
953  n.insert(*t);
954  }
955 
956  return n;
957 }
958 
959 template<typename T>
960 std::vector<NodeRef> NodeBase::childRefsOfType() const {
961  typename std::vector<NodeRef> n;
962  for ( auto c = _children.begin(); c != _children.end(); c = std::next(c) ) {
963  if ( c->isA<T>() )
964  n.emplace_back(*c);
965  }
966 
967  return n;
968 }
969 
970 namespace node {
971 namespace detail {
972 // Backend to NodeBase::flattenedChildren.
973 void flattenedChildren(const hilti::Node& n, node::Set<hilti::Node>* dst);
974 } // namespace detail
975 
980 inline node::Set<Node> flattenedChildren(const Node& n) {
981  node::Set<Node> dst;
982  detail::flattenedChildren(n, &dst);
983  return dst;
984 }
985 
986 } // namespace node
987 
988 } // namespace hilti
std::vector< T > copy() const
Definition: node.h:622
ErrorPriority priority
Definition: node.h:84
std::vector< std::string > context
Definition: node.h:83
uint64_t rid() const
Definition: node.h:143
bool pruneWalk() const
Definition: node.h:480
IntrusivePtr< Scope > scope() const
Definition: node.h:158
NodeBase(Meta meta)
Definition: node.h:367
Definition: node.h:38
void assertIsA()
Definition: node.h:293
void addError(std::string msg, const Location &l, std::vector< std::string > context={})
Definition: node.h:230
Node & operator=(const T &t)
Definition: node.h:333
Definition: doc-string.h:15
void clearDocumentation()
Definition: node.h:497
Definition: node.h:667
const Node none
Definition: node.cc:14
auto filter(const hilti::node::Range< X > &x, F f)
Definition: node.h:884
auto childRefs(int begin, int end)
Definition: node.h:428
bool hasErrors() const
Definition: node.h:189
Definition: optional.h:79
const auto & children() const
Definition: node.h:472
static None create()
Definition: node.h:521
void addChild(Node n)
Definition: node.h:461
Definition: node.h:512
void clearScope()
Definition: node.h:171
auto & children()
Definition: node.h:474
void addError(std::string msg, std::vector< std::string > context={})
Definition: node.h:205
void setScope(IntrusivePtr< Scope > new_scope)
Definition: node.h:168
const Location & location() const
Definition: node.h:289
const std::optional< DocString > & documentation() const
Definition: node.h:494
Location location
Definition: node.h:82
Node & operator=(Node &&n) noexcept
Definition: node.h:321
Definition: meta.h:19
std::vector< NodeRef > childRefsOfType() const
Definition: node.h:960
std::vector< T > copy() const
Definition: node.h:751
Definition: node.h:491
Definition: node.h:80
std::string renderedRid() const
Definition: node.h:150
Definition: node.h:41
void clearErrors()
Definition: node.h:192
void addError(std::string msg, Location l, node::ErrorPriority priority, std::vector< std::string > context={})
Definition: node.h:242
auto properties() const
Definition: node.h:515
std::vector< node::Error > errors() const
Definition: node.h:181
Definition: intrusive-ptr.h:69
auto children(int begin, int end) const
Definition: node.h:415
Definition: node.h:536
void setMeta(Meta m)
Definition: node.h:478
void print(std::ostream &out, bool compact=false) const
Definition: node.cc:133
std::map< std::string, node::detail::PropertyValue > Properties
Definition: node.h:98
std::string message
Definition: node.h:81
hilti::node::Set< T > childrenOfType() const
Definition: node.h:949
const T & child(int i) const
Definition: node.h:390
NodeBase(std::vector< Node > children, Meta meta)
Definition: node.h:375
Definition: node.h:112
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:218
Definition: node.h:21
Node & operator=(const Node &n)
Definition: node.h:308
void setDocumentation(DocString doc)
Definition: node.h:500
ErrorPriority
Definition: node.h:67
auto & meta() const
Definition: node.h:476
Definition: location.h:94
Node(T t)
Definition: node.h:116
void assertChildIsA(int i)
Definition: node.h:401
Definition: node.h:360