1 //
2 // Copyright 2019 The ANGLE Project Authors. All rights reserved.
3 // Use of this source code is governed by a BSD-style license that can be
4 // found in the LICENSE file.
5 //
6
7 #include "compiler/translator/ValidateAST.h"
8
9 #include "compiler/translator/Diagnostics.h"
10 #include "compiler/translator/ImmutableStringBuilder.h"
11 #include "compiler/translator/Symbol.h"
12 #include "compiler/translator/tree_util/IntermTraverse.h"
13 #include "compiler/translator/tree_util/SpecializationConstant.h"
14
15 namespace sh
16 {
17
18 namespace
19 {
20
21 class ValidateAST : public TIntermTraverser
22 {
23 public:
24 static bool validate(TIntermNode *root,
25 TDiagnostics *diagnostics,
26 const ValidateASTOptions &options);
27
28 void visitSymbol(TIntermSymbol *node) override;
29 void visitConstantUnion(TIntermConstantUnion *node) override;
30 bool visitSwizzle(Visit visit, TIntermSwizzle *node) override;
31 bool visitBinary(Visit visit, TIntermBinary *node) override;
32 bool visitUnary(Visit visit, TIntermUnary *node) override;
33 bool visitTernary(Visit visit, TIntermTernary *node) override;
34 bool visitIfElse(Visit visit, TIntermIfElse *node) override;
35 bool visitSwitch(Visit visit, TIntermSwitch *node) override;
36 bool visitCase(Visit visit, TIntermCase *node) override;
37 void visitFunctionPrototype(TIntermFunctionPrototype *node) override;
38 bool visitFunctionDefinition(Visit visit, TIntermFunctionDefinition *node) override;
39 bool visitAggregate(Visit visit, TIntermAggregate *node) override;
40 bool visitBlock(Visit visit, TIntermBlock *node) override;
41 bool visitGlobalQualifierDeclaration(Visit visit,
42 TIntermGlobalQualifierDeclaration *node) override;
43 bool visitDeclaration(Visit visit, TIntermDeclaration *node) override;
44 bool visitLoop(Visit visit, TIntermLoop *node) override;
45 bool visitBranch(Visit visit, TIntermBranch *node) override;
46 void visitPreprocessorDirective(TIntermPreprocessorDirective *node) override;
47
48 private:
49 ValidateAST(TIntermNode *root, TDiagnostics *diagnostics, const ValidateASTOptions &options);
50
51 // Visit as a generic node
52 void visitNode(Visit visit, TIntermNode *node);
53 // Visit a structure or interface block, and recursively visit its fields of structure type.
54 void visitStructOrInterfaceBlockDeclaration(const TType &type, const TSourceLoc &location);
55 void visitStructInDeclarationUsage(const TType &type, const TSourceLoc &location);
56 // Visit a unary or aggregate node and validate it's built-in op against it's built-in function.
57 void visitBuiltIn(TIntermOperator *op, const TFunction *function);
58
59 void scope(Visit visit);
60 bool isVariableDeclared(const TVariable *variable);
61 bool variableNeedsDeclaration(const TVariable *variable);
62 const TFieldListCollection *getStructOrInterfaceBlock(const TType &type,
63 ImmutableString *typeNameOut);
64
65 void expectNonNullChildren(Visit visit, TIntermNode *node, size_t least_count);
66
67 bool validateInternal();
68
69 ValidateASTOptions mOptions;
70 TDiagnostics *mDiagnostics;
71
72 // For validateSingleParent:
73 std::map<TIntermNode *, TIntermNode *> mParent;
74 bool mSingleParentFailed = false;
75
76 // For validateVariableReferences:
77 std::vector<std::set<const TVariable *>> mDeclaredVariables;
78 std::set<const TInterfaceBlock *> mNamelessInterfaceBlocks;
79 bool mVariableReferencesFailed = false;
80
81 // For validateBuiltInOps:
82 bool mBuiltInOpsFailed = false;
83
84 // For validateNullNodes:
85 bool mNullNodesFailed = false;
86
87 // For validateStructUsage:
88 std::vector<std::map<ImmutableString, const TFieldListCollection *>> mStructsAndBlocksByName;
89 bool mStructUsageFailed = false;
90
91 // For validateMultiDeclarations:
92 bool mMultiDeclarationsFailed = false;
93 };
94
validate(TIntermNode * root,TDiagnostics * diagnostics,const ValidateASTOptions & options)95 bool ValidateAST::validate(TIntermNode *root,
96 TDiagnostics *diagnostics,
97 const ValidateASTOptions &options)
98 {
99 ValidateAST validate(root, diagnostics, options);
100 root->traverse(&validate);
101 return validate.validateInternal();
102 }
103
ValidateAST(TIntermNode * root,TDiagnostics * diagnostics,const ValidateASTOptions & options)104 ValidateAST::ValidateAST(TIntermNode *root,
105 TDiagnostics *diagnostics,
106 const ValidateASTOptions &options)
107 : TIntermTraverser(true, false, true, nullptr), mOptions(options), mDiagnostics(diagnostics)
108 {
109 bool isTreeRoot = root->getAsBlock() && root->getAsBlock()->isTreeRoot();
110
111 // Some validations are not applicable unless run on the entire tree.
112 if (!isTreeRoot)
113 {
114 mOptions.validateVariableReferences = false;
115 }
116
117 if (mOptions.validateSingleParent)
118 {
119 mParent[root] = nullptr;
120 }
121 }
122
visitNode(Visit visit,TIntermNode * node)123 void ValidateAST::visitNode(Visit visit, TIntermNode *node)
124 {
125 if (visit == PreVisit && mOptions.validateSingleParent)
126 {
127 size_t childCount = node->getChildCount();
128 for (size_t i = 0; i < childCount; ++i)
129 {
130 TIntermNode *child = node->getChildNode(i);
131 if (mParent.find(child) != mParent.end())
132 {
133 // If child is visited twice but through the same parent, the problem is in one of
134 // the ancestors.
135 if (mParent[child] != node)
136 {
137 mDiagnostics->error(node->getLine(), "Found child with two parents",
138 "<validateSingleParent>");
139 mSingleParentFailed = true;
140 }
141 }
142
143 mParent[child] = node;
144 }
145 }
146 }
147
visitStructOrInterfaceBlockDeclaration(const TType & type,const TSourceLoc & location)148 void ValidateAST::visitStructOrInterfaceBlockDeclaration(const TType &type,
149 const TSourceLoc &location)
150 {
151 if (type.getStruct() == nullptr && type.getInterfaceBlock() == nullptr)
152 {
153 return;
154 }
155
156 // Make sure the structure or interface block is not doubly defined.
157 ImmutableString typeName("");
158 const TFieldListCollection *structOrBlock = getStructOrInterfaceBlock(type, &typeName);
159
160 if (structOrBlock)
161 {
162 ASSERT(!typeName.empty());
163
164 if (mStructsAndBlocksByName.back().find(typeName) != mStructsAndBlocksByName.back().end())
165 {
166 mDiagnostics->error(location,
167 "Found redeclaration of struct or interface block with the same "
168 "name in the same scope <validateStructUsage>",
169 typeName.data());
170 mStructUsageFailed = true;
171 }
172 else
173 {
174 // First encounter.
175 mStructsAndBlocksByName.back()[typeName] = structOrBlock;
176 }
177 }
178
179 // Recurse the fields of the structure or interface block and check members of structure type.
180 // Note that structOrBlock was previously only set for named structures, so make sure nameless
181 // structs are also recursed.
182 if (structOrBlock == nullptr)
183 {
184 structOrBlock = type.getStruct();
185 }
186 ASSERT(structOrBlock != nullptr);
187
188 for (const TField *field : structOrBlock->fields())
189 {
190 visitStructInDeclarationUsage(*field->type(), field->line());
191 }
192 }
193
visitStructInDeclarationUsage(const TType & type,const TSourceLoc & location)194 void ValidateAST::visitStructInDeclarationUsage(const TType &type, const TSourceLoc &location)
195 {
196 if (type.getStruct() == nullptr)
197 {
198 return;
199 }
200
201 // Make sure the structure being referenced has the same pointer as the closest (in scope)
202 // definition.
203 const TStructure *structure = type.getStruct();
204 const ImmutableString &typeName = structure->name();
205
206 bool foundDeclaration = false;
207 for (size_t scopeIndex = mStructsAndBlocksByName.size(); scopeIndex > 0; --scopeIndex)
208 {
209 const std::map<ImmutableString, const TFieldListCollection *> &scopeDecls =
210 mStructsAndBlocksByName[scopeIndex - 1];
211
212 auto iter = scopeDecls.find(typeName);
213 if (iter != scopeDecls.end())
214 {
215 foundDeclaration = true;
216
217 if (iter->second != structure)
218 {
219 mDiagnostics->error(location,
220 "Found reference to struct or interface block with doubly "
221 "created type <validateStructUsage>",
222 typeName.data());
223 mStructUsageFailed = true;
224 }
225 }
226 }
227
228 if (!foundDeclaration)
229 {
230 mDiagnostics->error(location,
231 "Found reference to struct or interface block with no declaration "
232 "<validateStructUsage>",
233 typeName.data());
234 mStructUsageFailed = true;
235 }
236 }
237
visitBuiltIn(TIntermOperator * node,const TFunction * function)238 void ValidateAST::visitBuiltIn(TIntermOperator *node, const TFunction *function)
239 {
240 const TOperator op = node->getOp();
241 if (!BuiltInGroup::IsBuiltIn(op))
242 {
243 return;
244 }
245
246 ImmutableStringBuilder opValueBuilder(16);
247 opValueBuilder << "op: ";
248 opValueBuilder.appendDecimal(op);
249
250 ImmutableString opValue = opValueBuilder;
251
252 if (function == nullptr)
253 {
254 mDiagnostics->error(node->getLine(),
255 "Found node calling built-in without a reference to the built-in "
256 "function <validateBuiltInOps>",
257 opValue.data());
258 mVariableReferencesFailed = true;
259 }
260 else if (function->getBuiltInOp() != op)
261 {
262 mDiagnostics->error(node->getLine(),
263 "Found node calling built-in with a reference to a different function "
264 "<validateBuiltInOps>",
265 opValue.data());
266 mVariableReferencesFailed = true;
267 }
268 }
269
scope(Visit visit)270 void ValidateAST::scope(Visit visit)
271 {
272 if (mOptions.validateVariableReferences)
273 {
274 if (visit == PreVisit)
275 {
276 mDeclaredVariables.push_back({});
277 }
278 else if (visit == PostVisit)
279 {
280 mDeclaredVariables.pop_back();
281 }
282 }
283
284 if (mOptions.validateStructUsage)
285 {
286 if (visit == PreVisit)
287 {
288 mStructsAndBlocksByName.push_back({});
289 }
290 else if (visit == PostVisit)
291 {
292 mStructsAndBlocksByName.pop_back();
293 }
294 }
295 }
296
isVariableDeclared(const TVariable * variable)297 bool ValidateAST::isVariableDeclared(const TVariable *variable)
298 {
299 ASSERT(mOptions.validateVariableReferences);
300
301 for (const std::set<const TVariable *> &scopeVariables : mDeclaredVariables)
302 {
303 if (scopeVariables.count(variable) > 0)
304 {
305 return true;
306 }
307 }
308
309 return false;
310 }
311
variableNeedsDeclaration(const TVariable * variable)312 bool ValidateAST::variableNeedsDeclaration(const TVariable *variable)
313 {
314 // Don't expect declaration for built-in variables.
315 if (variable->name().beginsWith("gl_"))
316 {
317 return false;
318 }
319
320 // Additionally, don't expect declaration for Vulkan specialization constants if not enabled.
321 // The declaration of these variables is deferred.
322 if (variable->getType().getQualifier() == EvqSpecConst)
323 {
324 return mOptions.validateSpecConstReferences;
325 }
326
327 return true;
328 }
329
getStructOrInterfaceBlock(const TType & type,ImmutableString * typeNameOut)330 const TFieldListCollection *ValidateAST::getStructOrInterfaceBlock(const TType &type,
331 ImmutableString *typeNameOut)
332 {
333 const TStructure *structure = type.getStruct();
334 const TInterfaceBlock *interfaceBlock = type.getInterfaceBlock();
335
336 ASSERT(structure != nullptr || interfaceBlock != nullptr);
337
338 // Make sure the structure or interface block is not doubly defined.
339 const TFieldListCollection *structOrBlock = nullptr;
340 if (structure != nullptr && structure->symbolType() != SymbolType::Empty)
341 {
342 structOrBlock = structure;
343 *typeNameOut = structure->name();
344 }
345 else if (interfaceBlock != nullptr)
346 {
347 structOrBlock = interfaceBlock;
348 *typeNameOut = interfaceBlock->name();
349 }
350
351 return structOrBlock;
352 }
353
expectNonNullChildren(Visit visit,TIntermNode * node,size_t least_count)354 void ValidateAST::expectNonNullChildren(Visit visit, TIntermNode *node, size_t least_count)
355 {
356 if (visit == PreVisit && mOptions.validateNullNodes)
357 {
358 size_t childCount = node->getChildCount();
359 if (childCount < least_count)
360 {
361 mDiagnostics->error(node->getLine(), "Too few children", "<validateNullNodes>");
362 mNullNodesFailed = true;
363 }
364
365 for (size_t i = 0; i < childCount; ++i)
366 {
367 if (node->getChildNode(i) == nullptr)
368 {
369 mDiagnostics->error(node->getLine(), "Found nullptr child", "<validateNullNodes>");
370 mNullNodesFailed = true;
371 }
372 }
373 }
374 }
375
visitSymbol(TIntermSymbol * node)376 void ValidateAST::visitSymbol(TIntermSymbol *node)
377 {
378 visitNode(PreVisit, node);
379
380 const TVariable *variable = &node->variable();
381 const TType &type = node->getType();
382
383 if (mOptions.validateVariableReferences && variableNeedsDeclaration(variable))
384 {
385 // If it's a reference to a field of a nameless interface block, match it by index and name.
386 if (type.getInterfaceBlock() && !type.isInterfaceBlock())
387 {
388 const TInterfaceBlock *interfaceBlock = type.getInterfaceBlock();
389 const TFieldList &fieldList = interfaceBlock->fields();
390 const size_t fieldIndex = type.getInterfaceBlockFieldIndex();
391
392 if (mNamelessInterfaceBlocks.count(interfaceBlock) == 0)
393 {
394 mDiagnostics->error(node->getLine(),
395 "Found reference to undeclared or inconsistenly transformed "
396 "nameless interface block <validateVariableReferences>",
397 node->getName().data());
398 mVariableReferencesFailed = true;
399 }
400 else if (fieldIndex >= fieldList.size() ||
401 node->getName() != fieldList[fieldIndex]->name())
402 {
403 mDiagnostics->error(node->getLine(),
404 "Found reference to inconsistenly transformed nameless "
405 "interface block field <validateVariableReferences>",
406 node->getName().data());
407 mVariableReferencesFailed = true;
408 }
409 }
410 else
411 {
412 const bool isStructDeclaration =
413 type.isStructSpecifier() && variable->symbolType() == SymbolType::Empty;
414
415 if (!isStructDeclaration && !isVariableDeclared(variable))
416 {
417 mDiagnostics->error(node->getLine(),
418 "Found reference to undeclared or inconsistently transformed "
419 "variable <validateVariableReferences>",
420 node->getName().data());
421 mVariableReferencesFailed = true;
422 }
423 }
424 }
425 }
426
visitConstantUnion(TIntermConstantUnion * node)427 void ValidateAST::visitConstantUnion(TIntermConstantUnion *node)
428 {
429 visitNode(PreVisit, node);
430 }
431
visitSwizzle(Visit visit,TIntermSwizzle * node)432 bool ValidateAST::visitSwizzle(Visit visit, TIntermSwizzle *node)
433 {
434 visitNode(visit, node);
435 return true;
436 }
437
visitBinary(Visit visit,TIntermBinary * node)438 bool ValidateAST::visitBinary(Visit visit, TIntermBinary *node)
439 {
440 visitNode(visit, node);
441 return true;
442 }
443
visitUnary(Visit visit,TIntermUnary * node)444 bool ValidateAST::visitUnary(Visit visit, TIntermUnary *node)
445 {
446 visitNode(visit, node);
447
448 if (visit == PreVisit && mOptions.validateBuiltInOps)
449 {
450 visitBuiltIn(node, node->getFunction());
451 }
452
453 return true;
454 }
455
visitTernary(Visit visit,TIntermTernary * node)456 bool ValidateAST::visitTernary(Visit visit, TIntermTernary *node)
457 {
458 visitNode(visit, node);
459 return true;
460 }
461
visitIfElse(Visit visit,TIntermIfElse * node)462 bool ValidateAST::visitIfElse(Visit visit, TIntermIfElse *node)
463 {
464 visitNode(visit, node);
465 return true;
466 }
467
visitSwitch(Visit visit,TIntermSwitch * node)468 bool ValidateAST::visitSwitch(Visit visit, TIntermSwitch *node)
469 {
470 visitNode(visit, node);
471 return true;
472 }
473
visitCase(Visit visit,TIntermCase * node)474 bool ValidateAST::visitCase(Visit visit, TIntermCase *node)
475 {
476 visitNode(visit, node);
477 return true;
478 }
479
visitFunctionPrototype(TIntermFunctionPrototype * node)480 void ValidateAST::visitFunctionPrototype(TIntermFunctionPrototype *node)
481 {
482 visitNode(PreVisit, node);
483 }
484
visitFunctionDefinition(Visit visit,TIntermFunctionDefinition * node)485 bool ValidateAST::visitFunctionDefinition(Visit visit, TIntermFunctionDefinition *node)
486 {
487 visitNode(visit, node);
488 scope(visit);
489
490 if (mOptions.validateVariableReferences && visit == PreVisit)
491 {
492 const TFunction *function = node->getFunction();
493
494 size_t paramCount = function->getParamCount();
495 for (size_t paramIndex = 0; paramIndex < paramCount; ++paramIndex)
496 {
497 const TVariable *variable = function->getParam(paramIndex);
498
499 if (isVariableDeclared(variable))
500 {
501 mDiagnostics->error(node->getLine(),
502 "Found two declarations of the same function argument "
503 "<validateVariableReferences>",
504 variable->name().data());
505 mVariableReferencesFailed = true;
506 break;
507 }
508
509 mDeclaredVariables.back().insert(variable);
510 }
511 }
512
513 return true;
514 }
515
visitAggregate(Visit visit,TIntermAggregate * node)516 bool ValidateAST::visitAggregate(Visit visit, TIntermAggregate *node)
517 {
518 visitNode(visit, node);
519 expectNonNullChildren(visit, node, 0);
520
521 if (visit == PreVisit && mOptions.validateBuiltInOps)
522 {
523 visitBuiltIn(node, node->getFunction());
524 }
525
526 return true;
527 }
528
visitBlock(Visit visit,TIntermBlock * node)529 bool ValidateAST::visitBlock(Visit visit, TIntermBlock *node)
530 {
531 visitNode(visit, node);
532 scope(visit);
533 expectNonNullChildren(visit, node, 0);
534 return true;
535 }
536
visitGlobalQualifierDeclaration(Visit visit,TIntermGlobalQualifierDeclaration * node)537 bool ValidateAST::visitGlobalQualifierDeclaration(Visit visit,
538 TIntermGlobalQualifierDeclaration *node)
539 {
540 visitNode(visit, node);
541
542 const TVariable *variable = &node->getSymbol()->variable();
543
544 if (mOptions.validateVariableReferences && variableNeedsDeclaration(variable))
545 {
546 if (!isVariableDeclared(variable))
547 {
548 mDiagnostics->error(node->getLine(),
549 "Found reference to undeclared or inconsistently transformed "
550 "variable <validateVariableReferences>",
551 variable->name().data());
552 mVariableReferencesFailed = true;
553 }
554 }
555 return true;
556 }
557
visitDeclaration(Visit visit,TIntermDeclaration * node)558 bool ValidateAST::visitDeclaration(Visit visit, TIntermDeclaration *node)
559 {
560 visitNode(visit, node);
561 expectNonNullChildren(visit, node, 0);
562
563 const TIntermSequence &sequence = *(node->getSequence());
564
565 if (mOptions.validateMultiDeclarations && sequence.size() > 1)
566 {
567 mMultiDeclarationsFailed = true;
568 }
569
570 if (visit == PreVisit)
571 {
572 bool validateStructUsage = mOptions.validateStructUsage;
573
574 for (TIntermNode *instance : sequence)
575 {
576 TIntermSymbol *symbol = instance->getAsSymbolNode();
577 if (symbol == nullptr)
578 {
579 TIntermBinary *init = instance->getAsBinaryNode();
580 ASSERT(init && init->getOp() == EOpInitialize);
581 symbol = init->getLeft()->getAsSymbolNode();
582 }
583 ASSERT(symbol);
584
585 const TVariable *variable = &symbol->variable();
586
587 if (mOptions.validateVariableReferences)
588 {
589 if (isVariableDeclared(variable))
590 {
591 mDiagnostics->error(
592 node->getLine(),
593 "Found two declarations of the same variable <validateVariableReferences>",
594 variable->name().data());
595 mVariableReferencesFailed = true;
596 break;
597 }
598
599 mDeclaredVariables.back().insert(variable);
600
601 const TInterfaceBlock *interfaceBlock = variable->getType().getInterfaceBlock();
602
603 if (variable->symbolType() == SymbolType::Empty && interfaceBlock != nullptr)
604 {
605 // Nameless interface blocks can only be declared at the top level. Their
606 // fields are matched by field index, and then verified to match by name.
607 // Conflict in names should have already generated a compile error.
608 ASSERT(mDeclaredVariables.size() == 1);
609 ASSERT(mNamelessInterfaceBlocks.count(interfaceBlock) == 0);
610
611 mNamelessInterfaceBlocks.insert(interfaceBlock);
612 }
613 }
614
615 if (validateStructUsage)
616 {
617 // Only declare the struct once.
618 validateStructUsage = false;
619
620 const TType &type = variable->getType();
621 if (type.isStructSpecifier() || type.isInterfaceBlock())
622 visitStructOrInterfaceBlockDeclaration(type, node->getLine());
623 }
624 }
625 }
626
627 return true;
628 }
629
visitLoop(Visit visit,TIntermLoop * node)630 bool ValidateAST::visitLoop(Visit visit, TIntermLoop *node)
631 {
632 visitNode(visit, node);
633 return true;
634 }
635
visitBranch(Visit visit,TIntermBranch * node)636 bool ValidateAST::visitBranch(Visit visit, TIntermBranch *node)
637 {
638 visitNode(visit, node);
639 return true;
640 }
641
visitPreprocessorDirective(TIntermPreprocessorDirective * node)642 void ValidateAST::visitPreprocessorDirective(TIntermPreprocessorDirective *node)
643 {
644 visitNode(PreVisit, node);
645 }
646
validateInternal()647 bool ValidateAST::validateInternal()
648 {
649 return !mSingleParentFailed && !mVariableReferencesFailed && !mBuiltInOpsFailed &&
650 !mNullNodesFailed && !mStructUsageFailed && !mMultiDeclarationsFailed;
651 }
652
653 } // anonymous namespace
654
ValidateAST(TIntermNode * root,TDiagnostics * diagnostics,const ValidateASTOptions & options)655 bool ValidateAST(TIntermNode *root, TDiagnostics *diagnostics, const ValidateASTOptions &options)
656 {
657 return ValidateAST::validate(root, diagnostics, options);
658 }
659
660 } // namespace sh
661