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 {
21 namespace trait {
22 class isNode {};
23 } // namespace trait
24 } // namespace hilti
25 
26 #include <hilti/ast/meta.h>
27 #include <hilti/ast/node-ref.h>
28 #include <hilti/ast/scope.h>
29 #include <hilti/base/type_erase.h>
30 #include <hilti/base/util.h>
31 
32 namespace hilti {
33 
34 class Node;
35 
36 namespace node {
37 
38 template<typename T>
39 class Range;
40 
41 template<typename T>
42 class Set;
43 
44 namespace detail {
45 
47 using PropertyValue = std::variant<bool, const char*, double, int, int64_t, unsigned int, uint64_t, std::string>;
48 
50 inline std::string to_string(PropertyValue v) {
51  struct Visitor {
52  auto operator()(bool s) { return std::string(s ? "true" : "false"); }
53  auto operator()(const char* s) { return util::escapeUTF8(s); }
54  auto operator()(double d) { return util::fmt("%.6f", d); }
55  auto operator()(int i) { return util::fmt("%d", i); }
56  auto operator()(int64_t i) { return util::fmt("%" PRId64, i); }
57  auto operator()(std::string s) { return util::escapeUTF8(s); }
58  auto operator()(unsigned int u) { return util::fmt("%u", u); }
59  auto operator()(uint64_t u) { return util::fmt("%" PRIu64, u); }
60  };
61 
62  return std::visit(Visitor(), v);
63 };
64 
65 } // namespace detail
66 
68 enum class ErrorPriority {
69  High = 3,
70  Normal = 2,
71  Low = 1,
72  NoError = 0
73 };
74 
75 inline bool operator<(ErrorPriority x, ErrorPriority y) {
76  return static_cast<std::underlying_type_t<ErrorPriority>>(x) <
77  static_cast<std::underlying_type_t<ErrorPriority>>(y);
78 }
79 
81 struct Error {
82  std::string message;
84  std::vector<std::string> context;
85  ErrorPriority priority = ErrorPriority::Normal;
87  // Comparision considers message & location, so that we can unique based
88  // on those two.
89  bool operator<(const Error& other) const {
90  return std::tie(message, location) < std::tie(other.message, other.location);
91  }
92 };
93 
99 using Properties = std::map<std::string, node::detail::PropertyValue>;
100 
101 namespace detail {
102 #include <hilti/autogen/__node.h>
103 
104 } // namespace detail
105 } // namespace node
106 
113 class Node final : public node::detail::Node {
114 public:
116  template<typename T, typename std::enable_if_t<std::is_base_of<trait::isNode, T>::value>* = nullptr>
117  Node(T t) : node::detail::Node(std::move(t)) {}
118 
119  Node(const Node& other) : node::detail::Node::Node(other), _scope(other._scope) {}
120 
121  Node(Node&& other) noexcept
122  : node::detail::Node::Node(std::move(other)),
123  _control_ptr(std::move(other._control_ptr)),
124  _scope(std::move(other._scope)),
125  _errors(std::move(other._errors)) {
126  if ( _control_ptr )
127  _control_ptr->_node = this;
128  }
129 
130  Node() = delete;
131 
132  ~Node() final {
133  if ( _control_ptr )
134  _control_ptr->_node = nullptr;
135  }
136 
144  uint64_t rid() const { return _control_ptr ? _control_ptr->_rid : 0; }
145 
151  std::string renderedRid() const { return rid() ? util::fmt("%%%" PRIu64, rid()) : "%???"; };
152 
160  if ( ! _scope )
161  _scope = make_intrusive<Scope>();
162 
163  return _scope;
164  }
165 
169  void setScope(IntrusivePtr<Scope> new_scope) { _scope = std::move(new_scope); }
170 
172  void clearScope() {
173  if ( ! _scope )
174  return;
175 
176  // Don't just clear the items because the scope might be shared with
177  // other nodes.
178  _scope = make_intrusive<Scope>();
179  }
180 
182  std::vector<node::Error> errors() const {
183  if ( _errors )
184  return *_errors;
185  else
186  return {};
187  }
188 
190  bool hasErrors() const { return _errors && _errors->size(); }
191 
193  void clearErrors() {
194  if ( _errors )
195  _errors.reset();
196  }
197 
206  void addError(std::string msg, std::vector<std::string> context = {}) {
207  addError(std::move(msg), location(), std::move(context));
208  }
209 
219  void addError(std::string msg, node::ErrorPriority priority, std::vector<std::string> context = {}) {
220  addError(std::move(msg), location(), priority, std::move(context));
221  }
222 
231  void addError(std::string msg, Location l, std::vector<std::string> context = {}) {
232  addError(std::move(msg), location(), node::ErrorPriority::Normal, std::move(context));
233  }
234 
243  void addError(std::string msg, Location l, node::ErrorPriority priority, std::vector<std::string> context = {}) {
244  node::Error error;
245  error.message = std::move(msg);
246  error.location = std::move(l);
247  error.context = std::move(context);
248  error.priority = priority;
249 
250  if ( ! _errors )
251  _errors = std::make_unique<std::vector<node::Error>>();
252 
253  _errors->push_back(std::move(error));
254  }
255 
260  void destroyChilds();
261 
269  std::string render(bool include_location = true) const;
270 
281  void print(std::ostream& out, bool compact = false) const;
282 
287  std::string print() const;
288 
290  const Location& location() const { return meta().location(); }
291 
293  template<typename T>
294  void assertIsA() {
295  if ( ! isA<T>() ) {
296  std::cerr << "Assertion failure: Node expected to be a " << typeid(T).name() << " but is a "
297  << typeid_().name() << std::endl;
299  }
300  }
301 
303  operator std::string() const { return print(); }
304 
309  Node& operator=(const Node& n) {
310  _scope = n._scope;
311  node::detail::ErasedBase::operator=(n);
312  return *this;
313  }
314 
319  Node& operator=(Node&& n) noexcept {
320  _scope = std::move(n._scope);
321  node::detail::ErasedBase::operator=(std::move(n));
322  return *this;
323  }
324 
330  template<typename T>
331  Node& operator=(const T& t) {
332  node::detail::ErasedBase::operator=(to_node(t));
333  return *this;
334  }
335 
336 private:
337  friend class NodeRef;
338 
339  // Returns (and potentially creates) the control block for this node that
340  // `NodeRef` uses to maintain links to it.
341  IntrusivePtr<node_ref::detail::Control> _control() const {
342  if ( ! _control_ptr )
343  _control_ptr = make_intrusive<node_ref::detail::Control>(this);
344 
345  return _control_ptr;
346  }
347 
348  mutable IntrusivePtr<node_ref::detail::Control> _control_ptr = nullptr;
349  mutable IntrusivePtr<Scope> _scope = nullptr;
350  std::unique_ptr<std::vector<node::Error>> _errors = nullptr;
351 };
352 
358 class NodeBase : public trait::isNode {
359 public:
365  NodeBase(Meta meta) : _meta(std::move(meta)) {}
366 
373  NodeBase(std::vector<Node> childs, Meta meta) : _meta(std::move(meta)) {
374  for ( auto& c : childs )
375  addChild(std::move(c));
376  }
377 
378  NodeBase() = default;
379 
387  template<typename T>
388  const T& child(int i) const {
389  return _childs[i].as<T>();
390  }
391 
398  template<typename T>
399  void assertChildIsA(int i) {
400  _childs[i].template assertIsA<T>();
401  }
402 
412  template<typename T>
413  auto childs(int begin, int end) const {
414  auto end_ = (end < 0) ? _childs.end() : _childs.begin() + end;
415  return hilti::node::Range<T>(_childs.begin() + begin, end_);
416  }
417 
426  auto childRefs(int begin, int end) {
427  auto end_ = (end < 0) ? _childs.end() : _childs.begin() + end;
428 
429  std::vector<NodeRef> refs;
430  for ( auto c = _childs.begin(); c != end_; c = std::next(c) )
431  refs.push_back(NodeRef(*c));
432 
433  return refs;
434  }
435 
442  template<typename T>
443  hilti::node::Set<T> childsOfType() const;
444 
452  template<typename T>
453  std::vector<NodeRef> childRefsOfType() const;
454 
459  void addChild(Node n) {
460  if ( _meta.location() && ! n.location() ) {
461  auto m = n.meta();
462  m.setLocation(_meta.location());
463  n.setMeta(std::move(m));
464  }
465 
466  _childs.push_back(std::move(n));
467  }
468 
470  const auto& childs() const { return _childs; }
472  auto& childs() { return _childs; }
474  auto& meta() const { return _meta; }
476  void setMeta(Meta m) { _meta = std::move(m); }
478  bool pruneWalk() const { return false; }
479 
480 private:
481  std::vector<::hilti::Node> _childs;
482  Meta _meta;
483  NodeRef _orig;
484 };
485 
486 namespace node {
487 
490 public:
492  auto properties() const { return node::Properties{}; }
493 
498  static None create() { return None(); }
499 
500 private:
501  None() : NodeBase(Meta()) {}
502 };
503 
505 extern const Node none;
506 
512 template<typename T>
514  using BaseIterator = std::vector<Node>::const_iterator;
515 
516 public:
517  using value_type = BaseIterator::value_type;
518  using difference_type = BaseIterator::difference_type;
519  using pointer = BaseIterator::pointer;
520  using reference = BaseIterator::reference;
521  using iterator_category = BaseIterator::iterator_category;
522 
523  explicit RangeIterator(BaseIterator i) : _iter(std::move(i)) {}
524  RangeIterator(const RangeIterator& other) = default;
525  RangeIterator(RangeIterator&& other) = default;
526  RangeIterator() {}
527  ~RangeIterator() = default;
528 
529  const Node& node() const { return *_iter; }
530 
531  RangeIterator& operator=(const RangeIterator& other) = default;
532  RangeIterator& operator=(RangeIterator&& other) = default;
533  const T& operator*() const { return value(); }
534  const T* operator->() const { return &value(); }
535  bool operator==(const RangeIterator& other) const { return _iter == other._iter; }
536  bool operator!=(const RangeIterator& other) const { return ! (*this == other); }
537 
538  RangeIterator operator++(int) {
539  auto x = RangeIterator(_iter);
540  ++_iter;
541  return x;
542  }
543 
544  RangeIterator& operator++() {
545  ++_iter;
546  return *this;
547  }
548 
549  RangeIterator& operator+=(difference_type i) {
550  _iter += i;
551  return *this;
552  }
553 
554  RangeIterator& operator-=(difference_type i) {
555  _iter -= i;
556  return *this;
557  }
558 
559  difference_type operator-(const RangeIterator& other) const { return _iter - other._iter; }
560  RangeIterator operator-(difference_type i) const { return RangeIterator(_iter - i); }
561  RangeIterator operator+(difference_type i) const { return RangeIterator(_iter + i); }
562 
563 private:
564  const T& value() const { return (*_iter).template as<std::remove_const_t<T>>(); }
565 
566  BaseIterator _iter;
567 };
568 
574 template<typename T>
575 class Range {
576 public:
577  using iterator = RangeIterator<T>;
578  using const_iterator = RangeIterator<T>;
579 
580  explicit Range() {}
581  Range(std::vector<Node>::const_iterator begin, std::vector<Node>::const_iterator end)
582  : _begin(std::move(begin)), _end(std::move(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) = 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(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) = 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) = 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) = 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) = 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) = 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::result_of<F(X&)>::type;
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::result_of<F(X&)>::type;
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 = _childs.begin(); c != _childs.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 = _childs.begin(); c != _childs.end(); c = std::next(c) ) {
941  if ( c->isA<T>() )
942  n.push_back(NodeRef(*c));
943  }
944 
945  return n;
946 }
947 
948 namespace node {
949 namespace detail {
950 // Backend to NodeBase::flattenedChilds.
951 void flattenedChilds(const hilti::Node& n, node::Set<const hilti::Node>* dst);
952 } // namespace detail
953 
958 inline node::Set<const Node> flattenedChilds(const Node& n) {
960  detail::flattenedChilds(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:85
std::vector< std::string > context
Definition: node.h:84
uint64_t rid() const
Definition: node.h:144
bool pruneWalk() const
Definition: node.h:478
IntrusivePtr< Scope > scope() const
Definition: node.h:159
NodeBase(Meta meta)
Definition: node.h:365
Definition: node.h:39
void assertIsA()
Definition: node.h:294
Node & operator=(const T &t)
Definition: node.h:331
void addError(std::string msg, Location l, std::vector< std::string > context={})
Definition: node.h:231
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
void abort_with_backtrace()
Definition: util.cc:179
auto childRefs(int begin, int end)
Definition: node.h:426
bool hasErrors() const
Definition: node.h:190
auto & childs()
Definition: node.h:472
Definition: optional.h:79
hilti::node::Set< T > childsOfType() const
Definition: node.h:927
static None create()
Definition: node.h:498
void addChild(Node n)
Definition: node.h:459
Definition: node.h:489
std::vector< T > concat(std::vector< T > v1, const std::vector< T > &v2)
Definition: util.h:530
void clearScope()
Definition: node.h:172
void addError(std::string msg, std::vector< std::string > context={})
Definition: node.h:206
void setScope(IntrusivePtr< Scope > new_scope)
Definition: node.h:169
const Location & location() const
Definition: node.h:290
Location location
Definition: node.h:83
Node & operator=(Node &&n) noexcept
Definition: node.h:319
Definition: meta.h:18
std::vector< NodeRef > childRefsOfType() const
Definition: node.h:938
std::vector< T > copy() const
Definition: node.h:729
Definition: node.h:81
std::string renderedRid() const
Definition: node.h:151
Definition: node.h:42
auto childs(int begin, int end) const
Definition: node.h:413
void clearErrors()
Definition: node.h:193
std::string fmt(const char *fmt, const Args &... args)
Definition: util.h:80
void addError(std::string msg, Location l, node::ErrorPriority priority, std::vector< std::string > context={})
Definition: node.h:243
auto properties() const
Definition: node.h:492
std::vector< node::Error > errors() const
Definition: node.h:182
Definition: intrusive-ptr.h:69
Definition: node.h:513
void setMeta(Meta m)
Definition: node.h:476
void print(std::ostream &out, bool compact=false) const
Definition: node.cc:103
std::map< std::string, node::detail::PropertyValue > Properties
Definition: node.h:99
std::string message
Definition: node.h:82
const T & child(int i) const
Definition: node.h:388
Definition: node.h:113
Definition: node-ref.h:44
Definition: location.h:17
void addError(std::string msg, node::ErrorPriority priority, std::vector< std::string > context={})
Definition: node.h:219
const auto & childs() const
Definition: node.h:470
Definition: node.h:22
Node & operator=(const Node &n)
Definition: node.h:309
ErrorPriority
Definition: node.h:68
auto & meta() const
Definition: node.h:474
Definition: location.h:93
Node(T t)
Definition: node.h:117
void assertChildIsA(int i)
Definition: node.h:399
NodeBase(std::vector< Node > childs, Meta meta)
Definition: node.h:373
Definition: node.h:358