SkSLASTNode.h 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635
  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. #ifndef SKSL_ASTNODE
  8. #define SKSL_ASTNODE
  9. #include "src/sksl/SkSLLexer.h"
  10. #include "src/sksl/SkSLString.h"
  11. #include "src/sksl/ir/SkSLModifiers.h"
  12. #include <vector>
  13. namespace SkSL {
  14. // std::max isn't constexpr in some compilers
  15. static constexpr size_t Max(size_t a, size_t b) {
  16. return a > b ? a : b;
  17. }
  18. /**
  19. * Represents a node in the abstract syntax tree (AST). The AST is based directly on the parse tree;
  20. * it is a parsed-but-not-yet-analyzed version of the program.
  21. */
  22. struct ASTNode {
  23. class ID {
  24. public:
  25. static ID Invalid() {
  26. return ID();
  27. }
  28. bool operator==(const ID& other) {
  29. return fValue == other.fValue;
  30. }
  31. bool operator!=(const ID& other) {
  32. return fValue != other.fValue;
  33. }
  34. operator bool() const { return fValue >= 0; }
  35. private:
  36. ID()
  37. : fValue(-1) {}
  38. ID(int value)
  39. : fValue(value) {}
  40. int fValue;
  41. friend struct ASTFile;
  42. friend struct ASTNode;
  43. friend class Parser;
  44. };
  45. enum class Kind {
  46. // data: operator(Token), children: left, right
  47. kBinary,
  48. // children: statements
  49. kBlock,
  50. // data: value(bool)
  51. kBool,
  52. kBreak,
  53. // children: target, arg1, arg2...
  54. kCall,
  55. kContinue,
  56. kDiscard,
  57. // children: statement, test
  58. kDo,
  59. // data: name(StringFragment), children: enumCases
  60. kEnum,
  61. // data: name(StringFragment), children: value?
  62. kEnumCase,
  63. // data: name(StringFragment)
  64. kExtension,
  65. // data: field(StringFragment), children: base
  66. kField,
  67. // children: declarations
  68. kFile,
  69. // data: value(float)
  70. kFloat,
  71. // children: init, test, next, statement
  72. kFor,
  73. // data: FunctionData, children: returnType, parameters, statement?
  74. kFunction,
  75. // data: name(StringFragment)
  76. kIdentifier,
  77. // children: base, index?
  78. kIndex,
  79. // data: isStatic(bool), children: test, ifTrue, ifFalse?
  80. kIf,
  81. // value(data): int
  82. kInt,
  83. // data: InterfaceBlockData, children: declaration1, declaration2, ..., size1, size2, ...
  84. kInterfaceBlock,
  85. // data: Modifiers
  86. kModifiers,
  87. kNull,
  88. // data: ParameterData, children: type, arraySize1, arraySize2, ..., value?
  89. kParameter,
  90. // data: operator(Token), children: operand
  91. kPostfix,
  92. // data: operator(Token), children: operand
  93. kPrefix,
  94. // children: value
  95. kReturn,
  96. // ...
  97. kSection,
  98. // children: value, statement 1, statement 2...
  99. kSwitchCase,
  100. // children: value, case 1, case 2...
  101. kSwitch,
  102. // children: test, ifTrue, ifFalse
  103. kTernary,
  104. // data: TypeData, children: sizes
  105. kType,
  106. // data: VarData, children: arraySize1, arraySize2, ..., value?
  107. kVarDeclaration,
  108. // children: modifiers, type, varDeclaration1, varDeclaration2, ...
  109. kVarDeclarations,
  110. // children: test, statement
  111. kWhile,
  112. };
  113. class iterator {
  114. public:
  115. iterator operator++() {
  116. SkASSERT(fID);
  117. fID = (**this).fNext;
  118. return *this;
  119. }
  120. iterator operator++(int) {
  121. SkASSERT(fID);
  122. iterator old = *this;
  123. fID = (**this).fNext;
  124. return old;
  125. }
  126. iterator operator+=(int count) {
  127. SkASSERT(count >= 0);
  128. for (; count > 0; --count) {
  129. ++(*this);
  130. }
  131. return *this;
  132. }
  133. iterator operator+(int count) {
  134. iterator result(*this);
  135. return result += count;
  136. }
  137. bool operator==(const iterator& other) const {
  138. return fID == other.fID;
  139. }
  140. bool operator!=(const iterator& other) const {
  141. return fID != other.fID;
  142. }
  143. ASTNode& operator*() {
  144. SkASSERT(fID);
  145. return (*fNodes)[fID.fValue];
  146. }
  147. ASTNode* operator->() {
  148. SkASSERT(fID);
  149. return &(*fNodes)[fID.fValue];
  150. }
  151. private:
  152. iterator(std::vector<ASTNode>* nodes, ID id)
  153. : fNodes(nodes)
  154. , fID(id) {}
  155. std::vector<ASTNode>* fNodes;
  156. ID fID;
  157. friend struct ASTNode;
  158. };
  159. struct TypeData {
  160. TypeData() {}
  161. TypeData(StringFragment name, bool isStructDeclaration, bool isNullable)
  162. : fName(name)
  163. , fIsStructDeclaration(isStructDeclaration)
  164. , fIsNullable(isNullable) {}
  165. StringFragment fName;
  166. bool fIsStructDeclaration;
  167. bool fIsNullable;
  168. };
  169. struct ParameterData {
  170. ParameterData() {}
  171. ParameterData(Modifiers modifiers, StringFragment name, size_t sizeCount)
  172. : fModifiers(modifiers)
  173. , fName(name)
  174. , fSizeCount(sizeCount) {}
  175. Modifiers fModifiers;
  176. StringFragment fName;
  177. size_t fSizeCount;
  178. };
  179. struct VarData {
  180. VarData() {}
  181. VarData(StringFragment name, size_t sizeCount)
  182. : fName(name)
  183. , fSizeCount(sizeCount) {}
  184. StringFragment fName;
  185. size_t fSizeCount;
  186. };
  187. struct FunctionData {
  188. FunctionData() {}
  189. FunctionData(Modifiers modifiers, StringFragment name, size_t parameterCount)
  190. : fModifiers(modifiers)
  191. , fName(name)
  192. , fParameterCount(parameterCount) {}
  193. Modifiers fModifiers;
  194. StringFragment fName;
  195. size_t fParameterCount;
  196. };
  197. struct InterfaceBlockData {
  198. InterfaceBlockData() {}
  199. InterfaceBlockData(Modifiers modifiers, StringFragment typeName, size_t declarationCount,
  200. StringFragment instanceName, size_t sizeCount)
  201. : fModifiers(modifiers)
  202. , fTypeName(typeName)
  203. , fDeclarationCount(declarationCount)
  204. , fInstanceName(instanceName)
  205. , fSizeCount(sizeCount) {}
  206. Modifiers fModifiers;
  207. StringFragment fTypeName;
  208. size_t fDeclarationCount;
  209. StringFragment fInstanceName;
  210. size_t fSizeCount;
  211. };
  212. struct SectionData {
  213. SectionData() {}
  214. SectionData(StringFragment name, StringFragment argument, StringFragment text)
  215. : fName(name)
  216. , fArgument(argument)
  217. , fText(text) {}
  218. StringFragment fName;
  219. StringFragment fArgument;
  220. StringFragment fText;
  221. };
  222. struct NodeData {
  223. char fBytes[Max(sizeof(Token),
  224. Max(sizeof(StringFragment),
  225. Max(sizeof(bool),
  226. Max(sizeof(SKSL_INT),
  227. Max(sizeof(SKSL_FLOAT),
  228. Max(sizeof(Modifiers),
  229. Max(sizeof(TypeData),
  230. Max(sizeof(FunctionData),
  231. Max(sizeof(ParameterData),
  232. Max(sizeof(VarData),
  233. Max(sizeof(InterfaceBlockData),
  234. sizeof(SectionData))))))))))))];
  235. enum class Kind {
  236. kToken,
  237. kStringFragment,
  238. kBool,
  239. kInt,
  240. kFloat,
  241. kModifiers,
  242. kTypeData,
  243. kFunctionData,
  244. kParameterData,
  245. kVarData,
  246. kInterfaceBlockData,
  247. kSectionData
  248. } fKind;
  249. NodeData() = default;
  250. NodeData(Token data)
  251. : fKind(Kind::kToken) {
  252. memcpy(fBytes, &data, sizeof(data));
  253. }
  254. NodeData(StringFragment data)
  255. : fKind(Kind::kStringFragment) {
  256. memcpy(fBytes, &data, sizeof(data));
  257. }
  258. NodeData(bool data)
  259. : fKind(Kind::kBool) {
  260. memcpy(fBytes, &data, sizeof(data));
  261. }
  262. NodeData(SKSL_INT data)
  263. : fKind(Kind::kInt) {
  264. memcpy(fBytes, &data, sizeof(data));
  265. }
  266. NodeData(SKSL_FLOAT data)
  267. : fKind(Kind::kFloat) {
  268. memcpy(fBytes, &data, sizeof(data));
  269. }
  270. NodeData(Modifiers data)
  271. : fKind(Kind::kModifiers) {
  272. memcpy(fBytes, &data, sizeof(data));
  273. }
  274. NodeData(TypeData data)
  275. : fKind(Kind::kTypeData) {
  276. memcpy(fBytes, &data, sizeof(data));
  277. }
  278. NodeData(FunctionData data)
  279. : fKind(Kind::kFunctionData) {
  280. memcpy(fBytes, &data, sizeof(data));
  281. }
  282. NodeData(VarData data)
  283. : fKind(Kind::kVarData) {
  284. memcpy(fBytes, &data, sizeof(data));
  285. }
  286. NodeData(ParameterData data)
  287. : fKind(Kind::kParameterData) {
  288. memcpy(fBytes, &data, sizeof(data));
  289. }
  290. NodeData(InterfaceBlockData data)
  291. : fKind(Kind::kInterfaceBlockData) {
  292. memcpy(fBytes, &data, sizeof(data));
  293. }
  294. NodeData(SectionData data)
  295. : fKind(Kind::kSectionData) {
  296. memcpy(fBytes, &data, sizeof(data));
  297. }
  298. };
  299. ASTNode()
  300. : fOffset(-1)
  301. , fKind(Kind::kNull) {}
  302. ASTNode(std::vector<ASTNode>* nodes, int offset, Kind kind)
  303. : fNodes(nodes)
  304. , fOffset(offset)
  305. , fKind(kind) {
  306. switch (kind) {
  307. case Kind::kBinary:
  308. case Kind::kPostfix:
  309. case Kind::kPrefix:
  310. fData.fKind = NodeData::Kind::kToken;
  311. break;
  312. case Kind::kBool:
  313. case Kind::kIf:
  314. case Kind::kSwitch:
  315. fData.fKind = NodeData::Kind::kBool;
  316. break;
  317. case Kind::kEnum:
  318. case Kind::kEnumCase:
  319. case Kind::kExtension:
  320. case Kind::kField:
  321. case Kind::kIdentifier:
  322. fData.fKind = NodeData::Kind::kStringFragment;
  323. break;
  324. case Kind::kFloat:
  325. fData.fKind = NodeData::Kind::kFloat;
  326. break;
  327. case Kind::kFunction:
  328. fData.fKind = NodeData::Kind::kFunctionData;
  329. break;
  330. case Kind::kInt:
  331. fData.fKind = NodeData::Kind::kInt;
  332. break;
  333. case Kind::kInterfaceBlock:
  334. fData.fKind = NodeData::Kind::kInterfaceBlockData;
  335. break;
  336. case Kind::kModifiers:
  337. fData.fKind = NodeData::Kind::kModifiers;
  338. break;
  339. case Kind::kParameter:
  340. fData.fKind = NodeData::Kind::kParameterData;
  341. break;
  342. case Kind::kVarDeclaration:
  343. fData.fKind = NodeData::Kind::kVarData;
  344. break;
  345. case Kind::kType:
  346. fData.fKind = NodeData::Kind::kTypeData;
  347. break;
  348. default:
  349. break;
  350. }
  351. }
  352. ASTNode(std::vector<ASTNode>* nodes, int offset, Kind kind, Token t)
  353. : fNodes(nodes)
  354. , fData(t)
  355. , fOffset(offset)
  356. , fKind(kind) {}
  357. ASTNode(std::vector<ASTNode>* nodes, int offset, Kind kind, StringFragment s)
  358. : fNodes(nodes)
  359. , fData(s)
  360. , fOffset(offset)
  361. , fKind(kind) {}
  362. ASTNode(std::vector<ASTNode>* nodes, int offset, Kind kind, const char* s)
  363. : fNodes(nodes)
  364. , fData(StringFragment(s))
  365. , fOffset(offset)
  366. , fKind(kind) {}
  367. ASTNode(std::vector<ASTNode>* nodes, int offset, Kind kind, bool b)
  368. : fNodes(nodes)
  369. , fData(b)
  370. , fOffset(offset)
  371. , fKind(kind) {}
  372. ASTNode(std::vector<ASTNode>* nodes, int offset, Kind kind, SKSL_INT i)
  373. : fNodes(nodes)
  374. , fData(i)
  375. , fOffset(offset)
  376. , fKind(kind) {}
  377. ASTNode(std::vector<ASTNode>* nodes, int offset, Kind kind, SKSL_FLOAT f)
  378. : fNodes(nodes)
  379. , fData(f)
  380. , fOffset(offset)
  381. , fKind(kind) {}
  382. ASTNode(std::vector<ASTNode>* nodes, int offset, Kind kind, Modifiers m)
  383. : fNodes(nodes)
  384. , fData(m)
  385. , fOffset(offset)
  386. , fKind(kind) {}
  387. ASTNode(std::vector<ASTNode>* nodes, int offset, Kind kind, TypeData td)
  388. : fNodes(nodes)
  389. , fData(td)
  390. , fOffset(offset)
  391. , fKind(kind) {}
  392. ASTNode(std::vector<ASTNode>* nodes, int offset, Kind kind, SectionData s)
  393. : fNodes(nodes)
  394. , fData(s)
  395. , fOffset(offset)
  396. , fKind(kind) {}
  397. operator bool() const {
  398. return fKind != Kind::kNull;
  399. }
  400. Token getToken() const {
  401. SkASSERT(fData.fKind == NodeData::Kind::kToken);
  402. Token result;
  403. memcpy(&result, fData.fBytes, sizeof(result));
  404. return result;
  405. }
  406. bool getBool() const {
  407. SkASSERT(fData.fKind == NodeData::Kind::kBool);
  408. bool result;
  409. memcpy(&result, fData.fBytes, sizeof(result));
  410. return result;
  411. }
  412. SKSL_INT getInt() const {
  413. SkASSERT(fData.fKind == NodeData::Kind::kInt);
  414. SKSL_INT result;
  415. memcpy(&result, fData.fBytes, sizeof(result));
  416. return result;
  417. }
  418. SKSL_FLOAT getFloat() const {
  419. SkASSERT(fData.fKind == NodeData::Kind::kFloat);
  420. SKSL_FLOAT result;
  421. memcpy(&result, fData.fBytes, sizeof(result));
  422. return result;
  423. }
  424. StringFragment getString() const {
  425. SkASSERT(fData.fKind == NodeData::Kind::kStringFragment);
  426. StringFragment result;
  427. memcpy(&result, fData.fBytes, sizeof(result));
  428. return result;
  429. }
  430. Modifiers getModifiers() const {
  431. SkASSERT(fData.fKind == NodeData::Kind::kModifiers);
  432. Modifiers result;
  433. memcpy(&result, fData.fBytes, sizeof(result));
  434. return result;
  435. }
  436. void setModifiers(const Modifiers& m) {
  437. memcpy(fData.fBytes, &m, sizeof(m));
  438. }
  439. TypeData getTypeData() const {
  440. SkASSERT(fData.fKind == NodeData::Kind::kTypeData);
  441. TypeData result;
  442. memcpy(&result, fData.fBytes, sizeof(result));
  443. return result;
  444. }
  445. void setTypeData(const ASTNode::TypeData& td) {
  446. SkASSERT(fData.fKind == NodeData::Kind::kTypeData);
  447. memcpy(fData.fBytes, &td, sizeof(td));
  448. }
  449. ParameterData getParameterData() const {
  450. SkASSERT(fData.fKind == NodeData::Kind::kParameterData);
  451. ParameterData result;
  452. memcpy(&result, fData.fBytes, sizeof(result));
  453. return result;
  454. }
  455. void setParameterData(const ASTNode::ParameterData& pd) {
  456. SkASSERT(fData.fKind == NodeData::Kind::kParameterData);
  457. memcpy(fData.fBytes, &pd, sizeof(pd));
  458. }
  459. VarData getVarData() const {
  460. SkASSERT(fData.fKind == NodeData::Kind::kVarData);
  461. VarData result;
  462. memcpy(&result, fData.fBytes, sizeof(result));
  463. return result;
  464. }
  465. void setVarData(const ASTNode::VarData& vd) {
  466. SkASSERT(fData.fKind == NodeData::Kind::kVarData);
  467. memcpy(fData.fBytes, &vd, sizeof(vd));
  468. }
  469. FunctionData getFunctionData() const {
  470. SkASSERT(fData.fKind == NodeData::Kind::kFunctionData);
  471. FunctionData result;
  472. memcpy(&result, fData.fBytes, sizeof(result));
  473. return result;
  474. }
  475. void setFunctionData(const ASTNode::FunctionData& fd) {
  476. SkASSERT(fData.fKind == NodeData::Kind::kFunctionData);
  477. memcpy(fData.fBytes, &fd, sizeof(fd));
  478. }
  479. InterfaceBlockData getInterfaceBlockData() const {
  480. SkASSERT(fData.fKind == NodeData::Kind::kInterfaceBlockData);
  481. InterfaceBlockData result;
  482. memcpy(&result, fData.fBytes, sizeof(result));
  483. return result;
  484. }
  485. void setInterfaceBlockData(const ASTNode::InterfaceBlockData& id) {
  486. SkASSERT(fData.fKind == NodeData::Kind::kInterfaceBlockData);
  487. memcpy(fData.fBytes, &id, sizeof(id));
  488. }
  489. SectionData getSectionData() const {
  490. SkASSERT(fData.fKind == NodeData::Kind::kSectionData);
  491. SectionData result;
  492. memcpy(&result, fData.fBytes, sizeof(result));
  493. return result;
  494. }
  495. void addChild(ID id) {
  496. SkASSERT(!(*fNodes)[id.fValue].fNext);
  497. if (fLastChild) {
  498. SkASSERT(!(*fNodes)[fLastChild.fValue].fNext);
  499. (*fNodes)[fLastChild.fValue].fNext = id;
  500. } else {
  501. fFirstChild = id;
  502. }
  503. fLastChild = id;
  504. SkASSERT(!(*fNodes)[fLastChild.fValue].fNext);
  505. }
  506. iterator begin() const {
  507. return iterator(fNodes, fFirstChild);
  508. }
  509. iterator end() const {
  510. return iterator(fNodes, ID(-1));
  511. }
  512. String description() const;
  513. std::vector<ASTNode>* fNodes;
  514. NodeData fData;
  515. int fOffset;
  516. Kind fKind;
  517. ID fFirstChild;
  518. ID fLastChild;
  519. ID fNext;
  520. };
  521. } // namespace
  522. #endif