• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright 2019 Google LLC
3  *
4  * Use of this source code is governed by a BSD-style license that can be
5  * found in the LICENSE file.
6  */
7 
8 #ifndef SKSL_ASTNODE
9 #define SKSL_ASTNODE
10 
11 #include "src/sksl/SkSLLexer.h"
12 #include "src/sksl/SkSLString.h"
13 #include "src/sksl/ir/SkSLModifiers.h"
14 
15 #include <vector>
16 
17 namespace SkSL {
18 
19 // std::max isn't constexpr in some compilers
Max(size_t a,size_t b)20 static constexpr size_t Max(size_t a, size_t b) {
21     return a > b ? a : b;
22 }
23 
24 /**
25  * Represents a node in the abstract syntax tree (AST). The AST is based directly on the parse tree;
26  * it is a parsed-but-not-yet-analyzed version of the program.
27  */
28 struct ASTNode {
29     class ID {
30     public:
InvalidASTNode31         static ID Invalid() {
32             return ID();
33         }
34 
35         bool operator==(const ID& other) {
36             return fValue == other.fValue;
37         }
38 
39         bool operator!=(const ID& other) {
40             return fValue != other.fValue;
41         }
42 
43         operator bool() const { return fValue >= 0; }
44 
45     private:
IDASTNode46         ID()
47             : fValue(-1) {}
48 
IDASTNode49         ID(int value)
50             : fValue(value) {}
51 
52         int fValue;
53 
54         friend struct ASTFile;
55         friend struct ASTNode;
56         friend class Parser;
57     };
58 
59     enum class Kind {
60         // data: operator(Token), children: left, right
61         kBinary,
62         // children: statements
63         kBlock,
64         // data: value(bool)
65         kBool,
66         kBreak,
67         // children: target, arg1, arg2...
68         kCall,
69         kContinue,
70         kDiscard,
71         // children: statement, test
72         kDo,
73         // data: name(StringFragment), children: enumCases
74         kEnum,
75         // data: name(StringFragment), children: value?
76         kEnumCase,
77         // data: name(StringFragment)
78         kExtension,
79         // data: field(StringFragment), children: base
80         kField,
81         // children: declarations
82         kFile,
83         // data: value(float)
84         kFloat,
85         // children: init, test, next, statement
86         kFor,
87         // data: FunctionData, children: returnType, parameters, statement?
88         kFunction,
89         // data: name(StringFragment)
90         kIdentifier,
91         // children: base, index?
92         kIndex,
93         // data: isStatic(bool), children: test, ifTrue, ifFalse?
94         kIf,
95         // value(data): int
96         kInt,
97         // data: InterfaceBlockData, children: declaration1, declaration2, ..., size1, size2, ...
98         kInterfaceBlock,
99         // data: Modifiers
100         kModifiers,
101         kNull,
102         // data: ParameterData, children: type, arraySize1, arraySize2, ..., value?
103         kParameter,
104         // data: operator(Token), children: operand
105         kPostfix,
106         // data: operator(Token), children: operand
107         kPrefix,
108         // children: value
109         kReturn,
110         // ...
111         kSection,
112         // children: value, statement 1, statement 2...
113         kSwitchCase,
114         // children: value, case 1, case 2...
115         kSwitch,
116         // children: test, ifTrue, ifFalse
117         kTernary,
118         // data: TypeData, children: sizes
119         kType,
120         // data: VarData, children: arraySize1, arraySize2, ..., value?
121         kVarDeclaration,
122         // children: modifiers, type, varDeclaration1, varDeclaration2, ...
123         kVarDeclarations,
124         // children: test, statement
125         kWhile,
126     };
127 
128     class iterator {
129     public:
130         iterator operator++() {
131             SkASSERT(fID);
132             fID = (**this).fNext;
133             return *this;
134         }
135 
136         iterator operator++(int) {
137             SkASSERT(fID);
138             iterator old = *this;
139             fID = (**this).fNext;
140             return old;
141         }
142 
143         iterator operator+=(int count) {
144             SkASSERT(count >= 0);
145             for (; count > 0; --count) {
146                 ++(*this);
147             }
148             return *this;
149         }
150 
151         iterator operator+(int count) {
152             iterator result(*this);
153             return result += count;
154         }
155 
156         bool operator==(const iterator& other) const {
157             return fID == other.fID;
158         }
159 
160         bool operator!=(const iterator& other) const {
161             return fID != other.fID;
162         }
163 
164         ASTNode& operator*() {
165             SkASSERT(fID);
166             return (*fNodes)[fID.fValue];
167         }
168 
169         ASTNode* operator->() {
170             SkASSERT(fID);
171             return &(*fNodes)[fID.fValue];
172         }
173 
174     private:
iteratorASTNode175         iterator(std::vector<ASTNode>* nodes, ID id)
176             : fNodes(nodes)
177             , fID(id) {}
178 
179         std::vector<ASTNode>* fNodes;
180 
181         ID fID;
182 
183         friend struct ASTNode;
184     };
185 
186     struct TypeData {
TypeDataASTNode::TypeData187         TypeData() {}
188 
TypeDataASTNode::TypeData189         TypeData(StringFragment name, bool isStructDeclaration, bool isNullable)
190             : fName(name)
191             , fIsStructDeclaration(isStructDeclaration)
192             , fIsNullable(isNullable) {}
193 
194         StringFragment fName;
195         bool fIsStructDeclaration;
196         bool fIsNullable;
197     };
198 
199     struct ParameterData {
ParameterDataASTNode::ParameterData200         ParameterData() {}
201 
ParameterDataASTNode::ParameterData202         ParameterData(Modifiers modifiers, StringFragment name, size_t sizeCount)
203             : fModifiers(modifiers)
204             , fName(name)
205             , fSizeCount(sizeCount) {}
206 
207         Modifiers fModifiers;
208         StringFragment fName;
209         size_t fSizeCount;
210     };
211 
212     struct VarData {
VarDataASTNode::VarData213         VarData() {}
214 
VarDataASTNode::VarData215         VarData(StringFragment name, size_t sizeCount)
216             : fName(name)
217             , fSizeCount(sizeCount) {}
218 
219         StringFragment fName;
220         size_t fSizeCount;
221     };
222 
223     struct FunctionData {
FunctionDataASTNode::FunctionData224         FunctionData() {}
225 
FunctionDataASTNode::FunctionData226         FunctionData(Modifiers modifiers, StringFragment name, size_t parameterCount)
227             : fModifiers(modifiers)
228             , fName(name)
229             , fParameterCount(parameterCount) {}
230 
231         Modifiers fModifiers;
232         StringFragment fName;
233         size_t fParameterCount;
234     };
235 
236     struct InterfaceBlockData {
InterfaceBlockDataASTNode::InterfaceBlockData237         InterfaceBlockData() {}
238 
InterfaceBlockDataASTNode::InterfaceBlockData239         InterfaceBlockData(Modifiers modifiers, StringFragment typeName, size_t declarationCount,
240                            StringFragment instanceName, size_t sizeCount)
241             : fModifiers(modifiers)
242             , fTypeName(typeName)
243             , fDeclarationCount(declarationCount)
244             , fInstanceName(instanceName)
245             , fSizeCount(sizeCount) {}
246 
247         Modifiers fModifiers;
248         StringFragment fTypeName;
249         size_t fDeclarationCount;
250         StringFragment fInstanceName;
251         size_t fSizeCount;
252     };
253 
254     struct SectionData {
SectionDataASTNode::SectionData255         SectionData() {}
256 
SectionDataASTNode::SectionData257         SectionData(StringFragment name, StringFragment argument, StringFragment text)
258             : fName(name)
259             , fArgument(argument)
260             , fText(text) {}
261 
262         StringFragment fName;
263         StringFragment fArgument;
264         StringFragment fText;
265     };
266 
267     struct NodeData {
268         char fBytes[Max(sizeof(Token),
269                     Max(sizeof(StringFragment),
270                     Max(sizeof(bool),
271                     Max(sizeof(SKSL_INT),
272                     Max(sizeof(SKSL_FLOAT),
273                     Max(sizeof(Modifiers),
274                     Max(sizeof(TypeData),
275                     Max(sizeof(FunctionData),
276                     Max(sizeof(ParameterData),
277                     Max(sizeof(VarData),
278                     Max(sizeof(InterfaceBlockData),
279                         sizeof(SectionData))))))))))))];
280 
281         enum class Kind {
282             kToken,
283             kStringFragment,
284             kBool,
285             kInt,
286             kFloat,
287             kModifiers,
288             kTypeData,
289             kFunctionData,
290             kParameterData,
291             kVarData,
292             kInterfaceBlockData,
293             kSectionData
294         } fKind;
295 
296         NodeData() = default;
297 
NodeDataASTNode::NodeData298         NodeData(Token data)
299             : fKind(Kind::kToken) {
300             memcpy(fBytes, &data, sizeof(data));
301         }
302 
NodeDataASTNode::NodeData303         NodeData(StringFragment data)
304             : fKind(Kind::kStringFragment) {
305             memcpy(fBytes, &data, sizeof(data));
306         }
307 
NodeDataASTNode::NodeData308         NodeData(bool data)
309             : fKind(Kind::kBool) {
310             memcpy(fBytes, &data, sizeof(data));
311         }
312 
NodeDataASTNode::NodeData313         NodeData(SKSL_INT data)
314             : fKind(Kind::kInt) {
315             memcpy(fBytes, &data, sizeof(data));
316         }
317 
NodeDataASTNode::NodeData318         NodeData(SKSL_FLOAT data)
319             : fKind(Kind::kFloat) {
320             memcpy(fBytes, &data, sizeof(data));
321         }
322 
NodeDataASTNode::NodeData323         NodeData(Modifiers data)
324             : fKind(Kind::kModifiers) {
325             memcpy(fBytes, &data, sizeof(data));
326         }
327 
NodeDataASTNode::NodeData328         NodeData(TypeData data)
329             : fKind(Kind::kTypeData) {
330             memcpy(fBytes, &data, sizeof(data));
331         }
332 
NodeDataASTNode::NodeData333         NodeData(FunctionData data)
334             : fKind(Kind::kFunctionData) {
335             memcpy(fBytes, &data, sizeof(data));
336         }
337 
NodeDataASTNode::NodeData338         NodeData(VarData data)
339             : fKind(Kind::kVarData) {
340             memcpy(fBytes, &data, sizeof(data));
341         }
342 
NodeDataASTNode::NodeData343         NodeData(ParameterData data)
344             : fKind(Kind::kParameterData) {
345             memcpy(fBytes, &data, sizeof(data));
346         }
347 
NodeDataASTNode::NodeData348         NodeData(InterfaceBlockData data)
349             : fKind(Kind::kInterfaceBlockData) {
350             memcpy(fBytes, &data, sizeof(data));
351         }
352 
NodeDataASTNode::NodeData353         NodeData(SectionData data)
354             : fKind(Kind::kSectionData) {
355             memcpy(fBytes, &data, sizeof(data));
356         }
357     };
358 
ASTNodeASTNode359     ASTNode()
360         : fOffset(-1)
361         , fKind(Kind::kNull) {}
362 
ASTNodeASTNode363     ASTNode(std::vector<ASTNode>* nodes, int offset, Kind kind)
364         : fNodes(nodes)
365         , fOffset(offset)
366             , fKind(kind) {
367         switch (kind) {
368             case Kind::kBinary:
369             case Kind::kPostfix:
370             case Kind::kPrefix:
371                 fData.fKind = NodeData::Kind::kToken;
372                 break;
373 
374             case Kind::kBool:
375             case Kind::kIf:
376             case Kind::kSwitch:
377                 fData.fKind = NodeData::Kind::kBool;
378                 break;
379 
380             case Kind::kEnum:
381             case Kind::kEnumCase:
382             case Kind::kExtension:
383             case Kind::kField:
384             case Kind::kIdentifier:
385                 fData.fKind = NodeData::Kind::kStringFragment;
386                 break;
387 
388             case Kind::kFloat:
389                 fData.fKind = NodeData::Kind::kFloat;
390                 break;
391 
392             case Kind::kFunction:
393                 fData.fKind = NodeData::Kind::kFunctionData;
394                 break;
395 
396             case Kind::kInt:
397                 fData.fKind = NodeData::Kind::kInt;
398                 break;
399 
400             case Kind::kInterfaceBlock:
401                 fData.fKind = NodeData::Kind::kInterfaceBlockData;
402                 break;
403 
404             case Kind::kModifiers:
405                 fData.fKind = NodeData::Kind::kModifiers;
406                 break;
407 
408             case Kind::kParameter:
409                 fData.fKind = NodeData::Kind::kParameterData;
410                 break;
411 
412             case Kind::kVarDeclaration:
413                 fData.fKind = NodeData::Kind::kVarData;
414                 break;
415 
416             case Kind::kType:
417                 fData.fKind = NodeData::Kind::kTypeData;
418                 break;
419 
420             default:
421                 break;
422         }
423     }
424 
ASTNodeASTNode425     ASTNode(std::vector<ASTNode>* nodes, int offset, Kind kind, Token t)
426         : fNodes(nodes)
427         , fData(t)
428         , fOffset(offset)
429         , fKind(kind) {}
430 
ASTNodeASTNode431     ASTNode(std::vector<ASTNode>* nodes, int offset, Kind kind, StringFragment s)
432         : fNodes(nodes)
433         , fData(s)
434         , fOffset(offset)
435         , fKind(kind) {}
436 
ASTNodeASTNode437     ASTNode(std::vector<ASTNode>* nodes, int offset, Kind kind, const char* s)
438         : fNodes(nodes)
439         , fData(StringFragment(s))
440         , fOffset(offset)
441         , fKind(kind) {}
442 
ASTNodeASTNode443     ASTNode(std::vector<ASTNode>* nodes, int offset, Kind kind, bool b)
444         : fNodes(nodes)
445         , fData(b)
446         , fOffset(offset)
447         , fKind(kind) {}
448 
ASTNodeASTNode449     ASTNode(std::vector<ASTNode>* nodes, int offset, Kind kind, SKSL_INT i)
450         : fNodes(nodes)
451         , fData(i)
452         , fOffset(offset)
453         , fKind(kind) {}
454 
ASTNodeASTNode455     ASTNode(std::vector<ASTNode>* nodes, int offset, Kind kind, SKSL_FLOAT f)
456         : fNodes(nodes)
457         , fData(f)
458         , fOffset(offset)
459         , fKind(kind) {}
460 
ASTNodeASTNode461     ASTNode(std::vector<ASTNode>* nodes, int offset, Kind kind, Modifiers m)
462         : fNodes(nodes)
463         , fData(m)
464         , fOffset(offset)
465         , fKind(kind) {}
466 
ASTNodeASTNode467     ASTNode(std::vector<ASTNode>* nodes, int offset, Kind kind, TypeData td)
468         : fNodes(nodes)
469         , fData(td)
470         , fOffset(offset)
471         , fKind(kind) {}
472 
ASTNodeASTNode473     ASTNode(std::vector<ASTNode>* nodes, int offset, Kind kind, SectionData s)
474         : fNodes(nodes)
475         , fData(s)
476         , fOffset(offset)
477         , fKind(kind) {}
478 
479     operator bool() const {
480         return fKind != Kind::kNull;
481     }
482 
getTokenASTNode483     Token getToken() const {
484         SkASSERT(fData.fKind == NodeData::Kind::kToken);
485         Token result;
486         memcpy(&result, fData.fBytes, sizeof(result));
487         return result;
488     }
489 
getBoolASTNode490     bool getBool() const {
491         SkASSERT(fData.fKind == NodeData::Kind::kBool);
492         bool result;
493         memcpy(&result, fData.fBytes, sizeof(result));
494         return result;
495     }
496 
getIntASTNode497     SKSL_INT getInt() const {
498         SkASSERT(fData.fKind == NodeData::Kind::kInt);
499         SKSL_INT result;
500         memcpy(&result, fData.fBytes, sizeof(result));
501         return result;
502     }
503 
getFloatASTNode504     SKSL_FLOAT getFloat() const {
505         SkASSERT(fData.fKind == NodeData::Kind::kFloat);
506         SKSL_FLOAT result;
507         memcpy(&result, fData.fBytes, sizeof(result));
508         return result;
509     }
510 
getStringASTNode511     StringFragment getString() const {
512         SkASSERT(fData.fKind == NodeData::Kind::kStringFragment);
513         StringFragment result;
514         memcpy(&result, fData.fBytes, sizeof(result));
515         return result;
516     }
517 
getModifiersASTNode518     Modifiers getModifiers() const {
519         SkASSERT(fData.fKind == NodeData::Kind::kModifiers);
520         Modifiers result;
521         memcpy(&result, fData.fBytes, sizeof(result));
522         return result;
523     }
524 
setModifiersASTNode525     void setModifiers(const Modifiers& m) {
526         memcpy(fData.fBytes, &m, sizeof(m));
527     }
528 
getTypeDataASTNode529     TypeData getTypeData() const {
530         SkASSERT(fData.fKind == NodeData::Kind::kTypeData);
531         TypeData result;
532         memcpy(&result, fData.fBytes, sizeof(result));
533         return result;
534     }
535 
setTypeDataASTNode536     void setTypeData(const ASTNode::TypeData& td) {
537         SkASSERT(fData.fKind == NodeData::Kind::kTypeData);
538         memcpy(fData.fBytes, &td, sizeof(td));
539     }
540 
getParameterDataASTNode541     ParameterData getParameterData() const {
542         SkASSERT(fData.fKind == NodeData::Kind::kParameterData);
543         ParameterData result;
544         memcpy(&result, fData.fBytes, sizeof(result));
545         return result;
546     }
547 
setParameterDataASTNode548     void setParameterData(const ASTNode::ParameterData& pd) {
549         SkASSERT(fData.fKind == NodeData::Kind::kParameterData);
550         memcpy(fData.fBytes, &pd, sizeof(pd));
551     }
552 
getVarDataASTNode553     VarData getVarData() const {
554         SkASSERT(fData.fKind == NodeData::Kind::kVarData);
555         VarData result;
556         memcpy(&result, fData.fBytes, sizeof(result));
557         return result;
558     }
559 
setVarDataASTNode560     void setVarData(const ASTNode::VarData& vd) {
561         SkASSERT(fData.fKind == NodeData::Kind::kVarData);
562         memcpy(fData.fBytes, &vd, sizeof(vd));
563     }
564 
getFunctionDataASTNode565     FunctionData getFunctionData() const {
566         SkASSERT(fData.fKind == NodeData::Kind::kFunctionData);
567         FunctionData result;
568         memcpy(&result, fData.fBytes, sizeof(result));
569         return result;
570     }
571 
setFunctionDataASTNode572     void setFunctionData(const ASTNode::FunctionData& fd) {
573         SkASSERT(fData.fKind == NodeData::Kind::kFunctionData);
574         memcpy(fData.fBytes, &fd, sizeof(fd));
575     }
576 
getInterfaceBlockDataASTNode577     InterfaceBlockData getInterfaceBlockData() const {
578         SkASSERT(fData.fKind == NodeData::Kind::kInterfaceBlockData);
579         InterfaceBlockData result;
580         memcpy(&result, fData.fBytes, sizeof(result));
581         return result;
582     }
583 
setInterfaceBlockDataASTNode584     void setInterfaceBlockData(const ASTNode::InterfaceBlockData& id) {
585         SkASSERT(fData.fKind == NodeData::Kind::kInterfaceBlockData);
586         memcpy(fData.fBytes, &id, sizeof(id));
587     }
588 
getSectionDataASTNode589     SectionData getSectionData() const {
590         SkASSERT(fData.fKind == NodeData::Kind::kSectionData);
591         SectionData result;
592         memcpy(&result, fData.fBytes, sizeof(result));
593         return result;
594     }
595 
addChildASTNode596     void addChild(ID id) {
597         SkASSERT(!(*fNodes)[id.fValue].fNext);
598         if (fLastChild) {
599             SkASSERT(!(*fNodes)[fLastChild.fValue].fNext);
600             (*fNodes)[fLastChild.fValue].fNext = id;
601         } else {
602             fFirstChild = id;
603         }
604         fLastChild = id;
605         SkASSERT(!(*fNodes)[fLastChild.fValue].fNext);
606     }
607 
beginASTNode608     iterator begin() const {
609         return iterator(fNodes, fFirstChild);
610     }
611 
endASTNode612     iterator end() const {
613         return iterator(fNodes, ID(-1));
614     }
615 
616 #ifdef SK_DEBUG
617     String description() const;
618 #endif
619 
620     std::vector<ASTNode>* fNodes;
621 
622     NodeData fData;
623 
624     int fOffset;
625 
626     Kind fKind;
627 
628     ID fFirstChild;
629 
630     ID fLastChild;
631 
632     ID fNext;
633 };
634 
635 } // namespace
636 
637 #endif
638