Blender V5.3
ast.hh
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2026 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#pragma once
10
11#include "lexit/lexit.hh"
12
14
15using namespace lexit;
16
17struct ParserBase;
18struct Token;
19
20namespace ast {
21
23
89
90using TokenID = int;
91using NodeID = int;
92
93struct NodeData;
94using Nodes = std::vector<NodeData>;
95
103struct NodeData {
105
106 /* Boundary tokens. */
109
111 /* Neighbors. */
112 NodeID prev = -1, next = -1;
113 /* Children. */
115
116 NodeData() = default;
117
119 : type(type), front(tok.index_), back(tok.index_)
120 {
121 if (parent_id != -1) {
122 NodeData &parent = nodes[parent_id];
123 if (parent.child_last != -1) {
124 nodes[parent.child_last].next = id;
125 this->prev = parent.child_last;
126 }
127 if (parent.child_first == -1) {
129 }
131 }
132 this->parent = parent_id;
133 }
134
135 std::string location(const ParserBase &parser) const;
136};
137
144struct Node {
145 const ParserBase *p = nullptr;
146 NodeID id = -1;
147
148#ifdef LEXIT_DEBUG
149 NodeType debug_type;
150 const NodeData *debug_data;
151 std::string_view debug_str;
152#endif
153
154 Node() = default;
155 Node(const ParserBase *p, NodeID id) : p(p), id(id)
156 {
157#ifdef LEXIT_DEBUG
158 debug_str = str();
159 debug_type = type();
160 debug_data = data();
161#endif
162 }
163
164 const NodeData *data() const;
165 NodeType type() const;
166
167 /* Boundary tokens. */
168 Token front() const;
169 Token back() const;
170
171 /* Return the neighbor node or an invalid node if it doesn't exists. */
172 Node prev() const;
173 Node next() const;
174 Node parent() const;
175 Node children() const;
176 Node child_first() const;
177 Node child_last() const;
178
179 /* Return the first neighbor node of type or an invalid node if it doesn't exists. */
180 Node prev(NodeType type) const;
181 Node next(NodeType type) const;
182 Node parent(NodeType type) const;
185
186 int child_count() const;
187 bool is_empty() const;
188 bool has_single_child() const;
189 bool is_valid() const
190 {
191 return id != -1;
192 }
193
194 std::string_view str() const;
195 /* Same as str buf with trailing white-spaces. */
196 std::string_view str_full() const;
197
198 /* Print AST dump to the standard output. */
199 void print_ast() const;
200
202 {
203 return this->type() == type;
204 }
206 {
207 return this->type() != type;
208 }
209
210 std::ostream &operator<<(std::ostream &os)
211 {
212 os << str();
213 return os;
214 }
215
216 /* Traversal. */
217
218 struct ChildIterator;
219 struct ChildRange;
220 ChildRange children_range() const;
221
222 template<typename NodeT> struct TypedChildIterator;
223 template<typename NodeT> struct TypedChildRange;
224 template<typename NodeT> TypedChildRange<NodeT> children_of_type() const;
225
226 template<typename NodeT> struct RecursiveTypedIterator;
227 template<typename NodeT> struct RecursiveTypedRange;
228 template<typename NodeT> RecursiveTypedRange<NodeT> descendants_of_type() const;
229
230 private:
231 static Node first_node_of_type(Node node, NodeType type, Node end)
232 {
233 while (node.id != end.id && node.type() != type) {
234 node = Node(node.p, node.id + 1);
235 }
236 return node;
237 }
238
239 static Node next_node_of_type(Node node, NodeType type, Node end)
240 {
241 do {
242 node = Node(node.p, node.id + 1);
243 } while (node.id != end.id && node.type() != type);
244 return node;
245 }
246
247 Node find_recursion_end() const
248 {
249 {
250 /* Try using next first. */
251 Node node = *this;
252 if (node.next().is_valid()) {
253 return node.next();
254 }
255 }
256 {
257 /* Try using parent next. */
258 Node node = *this;
259 while (node.is_valid()) {
260 node = node.parent();
261 if (node.next().is_valid()) {
262 return node.next();
263 }
264 }
265 }
266 {
267 /* Using children in last resort. */
268 Node node = *this;
269 while (node.is_valid()) {
270 node = node.child_last();
271 if (!node.child_last().is_valid()) {
272 /* No children. Deepest latest node. */
273 return Node(p, node.id + 1);
274 }
275 }
276 }
277 /* Nothing to iterate on. */
278 return *this;
279 }
280};
281
283{
285 return (node.type() == type) ? node : node.next(type);
286}
287
289{
290 Node node = child_last();
291 return (node.type() == type) ? node : node.prev(type);
292}
293
296
298 {
299 current = current.next();
300 return *this;
301 }
303 {
304 ChildIterator tmp = *this;
305 ++(*this);
306 return tmp;
307 }
309 {
310 return current;
311 }
312 bool operator!=(const ChildIterator &other) const
313 {
314 return current.id != other.current.id;
315 }
316 bool operator==(const ChildIterator &other) const
317 {
318 return current.id == other.current.id;
319 }
320};
321
325 {
326 return {parent.child_first()};
327 }
329 {
330 return {Node()};
331 }
332};
333
335{
336 return {*this};
337}
338
339template<typename NodeT> struct Node::TypedChildIterator {
341
343 {
344 current = current.next(NodeT::NodeEnumVal);
345 return *this;
346 }
348 {
349 TypedChildIterator tmp = *this;
350 ++(*this);
351 return tmp;
352 }
353 NodeT operator*() const
354 {
355 return NodeT(current);
356 }
357 bool operator!=(const TypedChildIterator &other) const
358 {
359 return current.id != other.current.id;
360 }
361 bool operator==(const TypedChildIterator &other) const
362 {
363 return current.id == other.current.id;
364 }
365};
366
367template<typename NodeT> struct Node::TypedChildRange {
370 {
371 return {parent.child_first(NodeT::NodeEnumVal)};
372 }
374 {
375 return {Node()};
376 }
377};
378
379template<typename NodeT> inline Node::TypedChildRange<NodeT> Node::children_of_type() const
380{
381 return {*this};
382}
383
384template<typename NodeT> struct Node::RecursiveTypedIterator {
387
389 {
390 current = Node::next_node_of_type(current, NodeT::NodeEnumVal, end_node);
391 return *this;
392 }
394 {
395 RecursiveTypedIterator tmp = *this;
396 ++(*this);
397 return tmp;
398 }
399 NodeT operator*() const
400 {
401 return NodeT(current);
402 }
403 bool operator!=(const RecursiveTypedIterator &other) const
404 {
405 return current.id != other.current.id;
406 }
407 bool operator==(const RecursiveTypedIterator &other) const
408 {
409 return current.id == other.current.id;
410 }
411};
412
413template<typename NodeT> struct Node::RecursiveTypedRange {
417 {
418 return {Node::first_node_of_type(start.child_first(), NodeT::NodeEnumVal, end_node), end_node};
419 }
421 {
422 return {end_node, end_node};
423 }
424};
425
426template<typename NodeT> inline Node::RecursiveTypedRange<NodeT> Node::descendants_of_type() const
427{
428 return {*this, find_recursion_end()};
429}
430
431/* All typed nodes are implicitly convertible to each other an to the type-less #Node class.
432 * Converting a #Node into a typed node of the wrong type will create an invalid node. */
433#define NODE_COMMON(Type) \
434 static constexpr NodeType NodeEnumVal = NodeType::Type; \
435 Type() = default; \
436 Type(const Node &node) : Node(node.type() == NodeType::Type ? node : Node{}) {}
437
438using TokenRange = Token; /* TODO */
439
440struct FuncParamList;
441struct LocalScope;
442struct ClassDecl;
443struct InitializerList;
444struct TemplateParamList;
445
449
453
454struct Id : Node {
456
457 /* Return the next Id in an IdQualified. */
458 Id next_id() const
459 {
460 Node next_node = next();
461 next_node = (next_node.type() == NodeType::TemplateParamList) ? next_node.next() : next_node;
462 return next_node.type() == NodeType::NamespaceSeparator ? next_node.next() : Node{};
463 }
464
465 bool is_namespace() const
466 {
467 return next_id().is_valid();
468 }
469
471};
472
475
476 bool has_namespace() const
477 {
479 }
480
481 bool is_global() const
482 {
484 }
485
486 Id name() const
487 {
488 return child_last(NodeType::Id);
489 }
490
492 {
494 }
495
497};
498
502
507
509{
510 return next();
511}
512
516
520
524
528
531
533
534 bool is_function() const
535 {
536 return child_last().type() == NodeType::FuncDecl;
537 }
538
539 bool is_class() const
540 {
541 return child_last().type() == NodeType::ClassDecl;
542 }
543
544 Node decl() const
545 {
546 return child_last();
547 }
548};
549
552
554
555 bool is_function() const
556 {
558 }
559
560 bool is_class() const
561 {
562 return child_last().type() == NodeType::ClassDecl;
563 }
564
565 Node decl() const
566 {
567 return child_last();
568 }
569};
570
573
575 {
576 return child_first();
577 }
578
580 {
581 return child_last();
582 }
583};
584
588
591
593 {
594 return child_first();
595 }
596
597 bool is_function() const
598 {
599 return child_last().type() == NodeType::FuncDecl;
600 }
601
602 bool is_class() const
603 {
604 return child_last().type() == NodeType::ClassDecl;
605 }
606
607 Node decl() const
608 {
609 return child_last();
610 }
611};
612
613struct Const : Node {
615};
616
620
621struct Expr : Node {
623};
624
625struct ExprSub : Node {
627
629 {
630 return child_first();
631 }
632};
633
634struct UsingStmt : Node {
636
637 bool is_namespace() const;
638
640 {
641 return child_first();
642 }
643
645 {
646 return child_last();
647 }
648};
649
650struct LocalVar : Node {
652
654 {
655 return child_first();
656 }
657};
658
659struct ReturnStmt : Node {
661
663 {
664 return child_last();
665 }
666};
667
668struct IdType : Node {
670
671 bool is_const() const
672 {
673 return constant().is_valid();
674 }
675
676 bool is_constexpr() const;
677
678 bool is_static() const
679 {
681 }
682
684 {
686 }
687
689 {
691 }
692
694 {
696 }
697};
698
699struct Subscript : Node {
701
702 Expr expr() const
703 {
704 return child_first();
705 }
706};
707
708struct ArrayDecl : Node {
710
711 /* Return 0 if invalid. */
712 int dimensions() const
713 {
714 return is_valid() ? child_count() : 0;
715 }
716
718 {
719 return child_first();
720 }
721};
722
726
730
733
735 {
736 return child_first();
737 }
738
740 {
741 return child_last();
742 }
743};
744
745struct Attr : Node {
747
749 {
750 return child_first();
751 }
752
754};
755
756struct AttrList : Node {
758
759 bool contains_attr(std::string_view attr_name) const
760 {
761 if (!is_valid()) {
762 return false;
763 }
764 bool found = false;
765 for (Attr attr : children_of_type<Attr>()) {
766 if (attr.identifier().str() == attr_name) {
767 found = true;
768 }
769 }
770 return found;
771 }
772};
773
774struct LocalStmt : Node {
776
778 {
779 return child_first();
780 }
781
782 Expr expr() const
783 {
784 return child_last();
785 }
786};
787
788struct AssignStmt : Node {
790
792 {
793 return child_first();
794 }
795
796 Expr expr() const
797 {
798 return child_first();
799 }
800};
801
804
806 {
807 return child_first();
808 }
809
811 {
812 return child_last();
813 }
814};
815
818
819 /* Unique identified used to name the temporary variable. */
820 std::string tmp_id() const;
821
823 {
824 return child_last();
825 }
826};
827
828struct BitField : Node {
830
831 Expr expr() const
832 {
833 return child_first();
834 }
835};
836
837struct Declarator : Node {
839
840 bool is_reference() const
841 {
842 return reference().is_valid();
843 }
844
845 bool is_array() const
846 {
847 return array().is_valid();
848 }
849
850 IdType type() const
851 {
852 return prev(NodeType::IdType);
853 }
854
856 {
857 return child_first();
858 }
859
861 {
863 }
864
866 {
868 }
869
871 {
873 }
874
876 {
877 return child_last();
878 }
879
881 {
882 return child_last();
883 }
884};
885
886struct VarDecl : Node {
888
889 bool is_const() const
890 {
891 return type().is_const();
892 }
893
895 {
896 return child_first();
897 }
898
899 IdType type() const
900 {
902 }
903
904 /* Return true if the first declarator is a reference. */
905 bool is_reference() const
906 {
908 }
909
911 {
914 return d_first.is_valid() && d_first.id == d_last.id;
915 }
916};
917
918struct FuncArg : Node {
920
922 {
923 return child_first();
924 }
925
926 IdType type() const
927 {
929 }
930
932 {
934 }
935
936 bool is_reference() const
937 {
938 return declarator().is_reference();
939 }
940
941 bool is_const() const
942 {
943 return type().is_const();
944 }
945
947 {
948 return declarator().identifier();
949 }
950
952 {
953 return declarator().array();
954 }
955
957 {
958 return declarator().initializer_list();
959 }
960
962 {
963 return declarator().initial_value();
964 }
965};
966
970
973
974 bool is_empty() const;
975
976 struct Splat1 {
978 };
979 struct Splat2 {
981 };
982 struct Splat3 {
984 };
985 struct Splat4 {
987 };
988
990 {
991 return {child_first()};
992 }
993
995 {
997 return {node, node.next()};
998 }
999
1001 {
1002 Node node1 = child_first();
1003 Node node2 = node1.next();
1004 Node node3 = node2.next();
1005 return {node1, node2, node3};
1006 }
1007
1009 {
1010 Node node1 = child_first();
1011 Node node2 = node1.next();
1012 Node node3 = node2.next();
1013 Node node4 = node3.next();
1014 return {node1, node2, node3, node4};
1015 }
1016};
1017
1019{
1020 return FuncParamList(child_first().next());
1021}
1022
1025
1026 bool is_method() const
1027 {
1029 }
1030
1031 bool is_static() const
1032 {
1034 }
1035
1036 bool is_const() const
1037 {
1039 }
1040
1042 {
1043 return child_first();
1044 }
1045
1047 {
1049 }
1050
1052 {
1053 return return_type().next();
1054 }
1055
1057 {
1059 }
1060
1061 /* Associated class if this function is a class method. */
1063};
1064
1065struct FuncDecl : Node {
1067
1068 bool is_method() const
1069 {
1071 }
1072
1073 bool is_static() const
1074 {
1076 }
1077
1078 bool is_const() const
1079 {
1081 }
1082
1083 bool is_template() const
1084 {
1085 return TemplateDecl(parent()).is_valid();
1086 }
1087
1089 {
1090 return child_first();
1091 }
1092
1094 {
1096 }
1097
1099 {
1100 return return_type().next();
1101 }
1102
1104 {
1106 }
1107
1108 /* Associated class if this function is a class method. */
1109 ClassDecl parent_class() const;
1110
1111 LocalScope body() const;
1112};
1113
1114struct FuncCall : Node {
1116
1118 {
1119 return child_first();
1120 }
1121
1123 {
1124 return child_last();
1125 }
1126};
1127
1130
1132 {
1133 return child_first();
1134 }
1135
1137 {
1138 return type().next();
1139 }
1140
1142 {
1143 return child_last();
1144 }
1145};
1146
1147struct EnumValue : Node {
1149
1151 {
1152 return child_first();
1153 }
1154
1156 {
1157 return child_last();
1158 }
1159};
1160
1164
1165struct Condition : Node {
1167
1169 {
1170 return next();
1171 }
1172};
1173
1174struct IfStmt : Node {
1176
1178 {
1179 return child_first();
1180 }
1181
1183 {
1185 }
1186
1188 {
1189 return child_last();
1190 }
1191};
1192
1195
1197 {
1198 return child_first();
1199 }
1200
1202 {
1204 }
1205
1207 {
1208 return child_last();
1209 }
1210};
1211
1212struct ElseStmt : Node {
1214
1216 {
1217 return child_last();
1218 }
1219};
1220
1221struct ForLoop : Node {
1223
1225 {
1226 return child_first();
1227 }
1228
1230 {
1231 return child_last();
1232 }
1233};
1234
1235struct WhileLoop : Node {
1237
1239 {
1240 return child_first();
1241 }
1242
1244 {
1245 return child_last();
1246 }
1247};
1248
1251
1253 {
1254 return child_last();
1255 }
1256
1258 {
1259 return child_first();
1260 }
1261};
1262
1265
1267 {
1268 return child_first();
1269 }
1270};
1271
1274
1275 bool is_default_case() const
1276 {
1278 }
1279
1280 /* Either NumConst or IdQualified. */
1281 Node value() const
1282 {
1283 return child_first();
1284 }
1285
1287 {
1288 return child_last();
1289 }
1290};
1291
1292/* Enum, Struct, Class, Union. */
1293struct ClassDecl : Node {
1295
1296 bool is_enum() const;
1297 bool is_enum_class() const;
1298 bool is_union() const;
1299
1300 bool is_anonymous() const
1301 {
1302 return !identifier().is_valid();
1303 }
1304
1305 IdQualified identifier() const;
1306
1308 {
1309 return child_first();
1310 }
1311
1312 IdQualified parent_class() const;
1313
1315 {
1316 return child_last();
1317 }
1318};
1319
1321{
1322 return is_template() ? parent().parent().parent() : parent().parent();
1323}
1324
1326{
1328}
1329
1331{
1332 Node node = child_last();
1333 if (node.type() == NodeType::ClassDecl) {
1335 return decl.identifier().template_params();
1336 }
1337 if (node.type() == NodeType::FuncDecl) {
1339 return decl.identifier().template_params();
1340 }
1341 assert(0);
1342 return {};
1343}
1344
1346{
1347 Node node = child_last();
1348 if (node.type() == NodeType::ClassDecl) {
1350 return decl.identifier().template_params();
1351 }
1352 if (node.type() == NodeType::FuncForwardDecl) {
1354 return decl.identifier().template_params();
1355 }
1356 assert(0);
1357 return {};
1358}
1359
1360struct Namespace : Node {
1362
1364 {
1365 return child_last();
1366 }
1367
1369 {
1370 return child_first();
1371 }
1372};
1373
1374#undef NODE_COMMON
1375
1376} // namespace ast
1377} // namespace blender::gpu::shader::parser
#define str(s)
std::vector< NodeData > Nodes
Definition ast.hh:94
BMesh const char void * data
@ Invalid
Definition types.hh:42
InitializerList initializer_list() const
Definition ast.hh:791
bool contains_attr(std::string_view attr_name) const
Definition ast.hh:759
FuncParamList parameters() const
Definition ast.hh:1018
InitializerList initializer_list() const
Definition ast.hh:739
InitializerList initializer_list() const
Definition ast.hh:875
InitializerList initializer_list() const
Definition ast.hh:956
TemplateParamList template_params() const
Definition ast.hh:503
TemplateParamList template_params() const
Definition ast.hh:508
std::string location(const ParserBase &parser) const
Definition ast.cc:14
NodeData(Nodes &nodes, NodeID id, NodeID parent_id, lexit::Token tok, NodeType type)
Definition ast.hh:118
bool operator!=(const ChildIterator &other) const
Definition ast.hh:312
bool operator==(const ChildIterator &other) const
Definition ast.hh:316
bool operator!=(const RecursiveTypedIterator &other) const
Definition ast.hh:403
bool operator==(const RecursiveTypedIterator &other) const
Definition ast.hh:407
RecursiveTypedIterator< NodeT > begin() const
Definition ast.hh:416
RecursiveTypedIterator< NodeT > end() const
Definition ast.hh:420
bool operator!=(const TypedChildIterator &other) const
Definition ast.hh:357
bool operator==(const TypedChildIterator &other) const
Definition ast.hh:361
TypedChildIterator< NodeT > end() const
Definition ast.hh:373
TypedChildIterator< NodeT > begin() const
Definition ast.hh:369
RecursiveTypedRange< NodeT > descendants_of_type() const
Definition ast.hh:426
bool operator!=(NodeType type) const
Definition ast.hh:205
ChildRange children_range() const
Definition ast.hh:334
TypedChildRange< NodeT > children_of_type() const
Definition ast.hh:379
Node(const ParserBase *p, NodeID id)
Definition ast.hh:155
std::string_view str_full() const
Definition ast.cc:118
std::string_view str() const
Definition ast.cc:113
bool operator==(NodeType type) const
Definition ast.hh:201
const NodeData * data() const
Definition ast.cc:88
std::ostream & operator<<(std::ostream &os)
Definition ast.hh:210
TemplateParamList parameters() const
Definition ast.hh:1345
TemplateParamList parameters() const
Definition ast.hh:1330