Add expression complexity and call stack depth limits.
git-svn-id: http://angleproject.googlecode.com/svn/branches/dx11proto@2254 736b8ea6-26fd-11df-bfd4-992fa37f6226
diff --git a/build/common.gypi b/build/common.gypi
index 3ae185e..fc9f295 100644
--- a/build/common.gypi
+++ b/build/common.gypi
@@ -110,6 +110,10 @@
'LinkIncremental': '2',
},
},
+ 'xcode_settings': {
+ 'COPY_PHASE_STRIP': 'NO',
+ 'GCC_OPTIMIZATION_LEVEL': '0',
+ },
}, # Debug
'Release': {
'inherit_from': ['Common'],
diff --git a/include/GLSLANG/ShaderLang.h b/include/GLSLANG/ShaderLang.h
index da0f87a..f0459b5 100644
--- a/include/GLSLANG/ShaderLang.h
+++ b/include/GLSLANG/ShaderLang.h
@@ -162,7 +162,13 @@
// vec234, or mat234 type. The ShArrayIndexClampingStrategy enum,
// specified in the ShBuiltInResources when constructing the
// compiler, selects the strategy for the clamping implementation.
- SH_CLAMP_INDIRECT_ARRAY_BOUNDS = 0x1000
+ SH_CLAMP_INDIRECT_ARRAY_BOUNDS = 0x1000,
+
+ // This flag limits the complexity of an expression.
+ SH_LIMIT_EXPRESSION_COMPLEXITY = 0x2000,
+
+ // This flag limits the depth of the call stack.
+ SH_LIMIT_CALL_STACK_DEPTH = 0x4000,
} ShCompileOptions;
// Defines alternate strategies for implementing array index clamping.
@@ -225,6 +231,12 @@
// Selects a strategy to use when implementing array index clamping.
// Default is SH_CLAMP_WITH_CLAMP_INTRINSIC.
ShArrayIndexClampingStrategy ArrayIndexClampingStrategy;
+
+ // The maximum complexity an expression can be.
+ int MaxExpressionComplexity;
+
+ // The maximum depth a call stack can be.
+ int MaxCallStackDepth;
} ShBuiltInResources;
//
diff --git a/src/build_angle.gypi b/src/build_angle.gypi
index d822c36..405c671 100644
--- a/src/build_angle.gypi
+++ b/src/build_angle.gypi
@@ -72,8 +72,8 @@
'compiler/ConstantUnion.h',
'compiler/debug.cpp',
'compiler/debug.h',
- 'compiler/DetectRecursion.cpp',
- 'compiler/DetectRecursion.h',
+ 'compiler/DetectCallDepth.cpp',
+ 'compiler/DetectCallDepth.h',
'compiler/Diagnostics.h',
'compiler/Diagnostics.cpp',
'compiler/DirectiveHandler.h',
diff --git a/src/compiler/Compiler.cpp b/src/compiler/Compiler.cpp
index 395fb2a..349cd5f 100644
--- a/src/compiler/Compiler.cpp
+++ b/src/compiler/Compiler.cpp
@@ -5,7 +5,7 @@
//
#include "compiler/BuiltInFunctionEmulator.h"
-#include "compiler/DetectRecursion.h"
+#include "compiler/DetectCallDepth.h"
#include "compiler/ForLoopUnroll.h"
#include "compiler/Initialize.h"
#include "compiler/InitializeParseContext.h"
@@ -104,6 +104,9 @@
TCompiler::TCompiler(ShShaderType type, ShShaderSpec spec)
: shaderType(type),
shaderSpec(spec),
+ maxUniformVectors(0),
+ maxExpressionComplexity(0),
+ maxCallStackDepth(0),
fragmentPrecisionHigh(false),
clampingStrategy(SH_CLAMP_WITH_CLAMP_INTRINSIC),
builtInFunctionEmulator(type)
@@ -122,6 +125,8 @@
maxUniformVectors = (shaderType == SH_VERTEX_SHADER) ?
resources.MaxVertexUniformVectors :
resources.MaxFragmentUniformVectors;
+ maxExpressionComplexity = resources.MaxExpressionComplexity;
+ maxCallStackDepth = resources.MaxCallStackDepth;
TScopedPoolAllocator scopedAlloc(&allocator, false);
// Generate built-in symbol table.
@@ -185,7 +190,7 @@
success = intermediate.postProcess(root);
if (success)
- success = detectRecursion(root);
+ success = detectCallDepth(root, infoSink, (compileOptions & SH_LIMIT_CALL_STACK_DEPTH) != 0);
if (success && (compileOptions & SH_VALIDATE_LOOP_INDEXING))
success = validateLimitations(root);
@@ -208,6 +213,10 @@
if (success && (compileOptions & SH_CLAMP_INDIRECT_ARRAY_BOUNDS))
arrayBoundsClamper.MarkIndirectArrayBoundsForClamping(root);
+ // Disallow expressions deemed too complex.
+ if (success && (compileOptions & SH_LIMIT_EXPRESSION_COMPLEXITY))
+ success = limitExpressionComplexity(root);
+
// Call mapLongVariableNames() before collectAttribsUniforms() so in
// collectAttribsUniforms() we already have the mapped symbol names and
// we could composite mapped and original variable names.
@@ -268,24 +277,27 @@
nameMap.clear();
}
-bool TCompiler::detectRecursion(TIntermNode* root)
+bool TCompiler::detectCallDepth(TIntermNode* root, TInfoSink& infoSink, bool limitCallStackDepth)
{
- DetectRecursion detect;
+ DetectCallDepth detect(infoSink, limitCallStackDepth, maxCallStackDepth);
root->traverse(&detect);
- switch (detect.detectRecursion()) {
- case DetectRecursion::kErrorNone:
+ switch (detect.detectCallDepth()) {
+ case DetectCallDepth::kErrorNone:
return true;
- case DetectRecursion::kErrorMissingMain:
+ case DetectCallDepth::kErrorMissingMain:
infoSink.info.prefix(EPrefixError);
infoSink.info << "Missing main()";
return false;
- case DetectRecursion::kErrorRecursion:
+ case DetectCallDepth::kErrorRecursion:
infoSink.info.prefix(EPrefixError);
infoSink.info << "Function recursion detected";
return false;
+ case DetectCallDepth::kErrorMaxDepthExceeded:
+ infoSink.info.prefix(EPrefixError);
+ infoSink.info << "Function call stack too deep";
+ return false;
default:
UNREACHABLE();
- return false;
}
}
@@ -327,6 +339,28 @@
}
}
+bool TCompiler::limitExpressionComplexity(TIntermNode* root)
+{
+ TIntermTraverser traverser;
+ root->traverse(&traverser);
+ TDependencyGraph graph(root);
+
+ for (TFunctionCallVector::const_iterator iter = graph.beginUserDefinedFunctionCalls();
+ iter != graph.endUserDefinedFunctionCalls();
+ ++iter)
+ {
+ TGraphFunctionCall* samplerSymbol = *iter;
+ TDependencyGraphTraverser graphTraverser;
+ samplerSymbol->traverse(&graphTraverser);
+ }
+
+ if (traverser.getMaxDepth() > maxExpressionComplexity) {
+ infoSink.info << "Expression too complex.";
+ return false;
+ }
+ return true;
+}
+
bool TCompiler::enforceFragmentShaderTimingRestrictions(const TDependencyGraph& graph)
{
RestrictFragmentShaderTiming restrictor(infoSink.info);
diff --git a/src/compiler/DetectCallDepth.cpp b/src/compiler/DetectCallDepth.cpp
new file mode 100644
index 0000000..99f810b
--- /dev/null
+++ b/src/compiler/DetectCallDepth.cpp
@@ -0,0 +1,187 @@
+//
+// Copyright (c) 2002-2011 The ANGLE Project Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+//
+
+#include "compiler/DetectCallDepth.h"
+#include "compiler/InfoSink.h"
+
+const int DetectCallDepth::FunctionNode::kInfiniteCallDepth;
+
+DetectCallDepth::FunctionNode::FunctionNode(const TString& fname)
+ : name(fname),
+ visit(PreVisit)
+{
+}
+
+const TString& DetectCallDepth::FunctionNode::getName() const
+{
+ return name;
+}
+
+void DetectCallDepth::FunctionNode::addCallee(
+ DetectCallDepth::FunctionNode* callee)
+{
+ for (size_t i = 0; i < callees.size(); ++i) {
+ if (callees[i] == callee)
+ return;
+ }
+ callees.push_back(callee);
+}
+
+int DetectCallDepth::FunctionNode::detectCallDepth(DetectCallDepth* detectCallDepth, int depth)
+{
+ ASSERT(visit == PreVisit);
+ ASSERT(detectCallDepth);
+
+ int maxDepth = depth;
+ visit = InVisit;
+ for (size_t i = 0; i < callees.size(); ++i) {
+ switch (callees[i]->visit) {
+ case InVisit:
+ // cycle detected, i.e., recursion detected.
+ return kInfiniteCallDepth;
+ case PostVisit:
+ break;
+ case PreVisit: {
+ // Check before we recurse so we don't go too depth
+ if (detectCallDepth->checkExceedsMaxDepth(depth))
+ return depth;
+ int callDepth = callees[i]->detectCallDepth(detectCallDepth, depth + 1);
+ // Check after we recurse so we can exit immediately and provide info.
+ if (detectCallDepth->checkExceedsMaxDepth(callDepth)) {
+ detectCallDepth->getInfoSink().info << "<-" << callees[i]->getName();
+ return callDepth;
+ }
+ maxDepth = std::max(callDepth, maxDepth);
+ break;
+ }
+ default:
+ UNREACHABLE();
+ break;
+ }
+ }
+ visit = PostVisit;
+ return maxDepth;
+}
+
+void DetectCallDepth::FunctionNode::reset()
+{
+ visit = PreVisit;
+}
+
+DetectCallDepth::DetectCallDepth(TInfoSink& infoSink, bool limitCallStackDepth, int maxCallStackDepth)
+ : TIntermTraverser(true, false, true, false),
+ currentFunction(NULL),
+ infoSink(infoSink),
+ maxDepth(limitCallStackDepth ? maxCallStackDepth : FunctionNode::kInfiniteCallDepth)
+{
+}
+
+DetectCallDepth::~DetectCallDepth()
+{
+ for (size_t i = 0; i < functions.size(); ++i)
+ delete functions[i];
+}
+
+bool DetectCallDepth::visitAggregate(Visit visit, TIntermAggregate* node)
+{
+ switch (node->getOp())
+ {
+ case EOpPrototype:
+ // Function declaration.
+ // Don't add FunctionNode here because node->getName() is the
+ // unmangled function name.
+ break;
+ case EOpFunction: {
+ // Function definition.
+ if (visit == PreVisit) {
+ currentFunction = findFunctionByName(node->getName());
+ if (currentFunction == NULL) {
+ currentFunction = new FunctionNode(node->getName());
+ functions.push_back(currentFunction);
+ }
+ } else if (visit == PostVisit) {
+ currentFunction = NULL;
+ }
+ break;
+ }
+ case EOpFunctionCall: {
+ // Function call.
+ if (visit == PreVisit) {
+ FunctionNode* func = findFunctionByName(node->getName());
+ if (func == NULL) {
+ func = new FunctionNode(node->getName());
+ functions.push_back(func);
+ }
+ if (currentFunction)
+ currentFunction->addCallee(func);
+ }
+ break;
+ }
+ default:
+ break;
+ }
+ return true;
+}
+
+bool DetectCallDepth::checkExceedsMaxDepth(int depth)
+{
+ return depth >= maxDepth;
+}
+
+void DetectCallDepth::resetFunctionNodes()
+{
+ for (size_t i = 0; i < functions.size(); ++i) {
+ functions[i]->reset();
+ }
+}
+
+DetectCallDepth::ErrorCode DetectCallDepth::detectCallDepthForFunction(FunctionNode* func)
+{
+ currentFunction = NULL;
+ resetFunctionNodes();
+
+ int maxCallDepth = func->detectCallDepth(this, 1);
+
+ if (maxCallDepth == FunctionNode::kInfiniteCallDepth)
+ return kErrorRecursion;
+
+ if (maxCallDepth >= maxDepth)
+ return kErrorMaxDepthExceeded;
+
+ return kErrorNone;
+}
+
+DetectCallDepth::ErrorCode DetectCallDepth::detectCallDepth()
+{
+ if (maxDepth != FunctionNode::kInfiniteCallDepth) {
+ // Check all functions because the driver may fail on them
+ // TODO: Before detectingRecursion, strip unused functions.
+ for (size_t i = 0; i < functions.size(); ++i) {
+ ErrorCode error = detectCallDepthForFunction(functions[i]);
+ if (error != kErrorNone)
+ return error;
+ }
+ } else {
+ FunctionNode* main = findFunctionByName("main(");
+ if (main == NULL)
+ return kErrorMissingMain;
+
+ return detectCallDepthForFunction(main);
+ }
+
+ return kErrorNone;
+}
+
+DetectCallDepth::FunctionNode* DetectCallDepth::findFunctionByName(
+ const TString& name)
+{
+ for (size_t i = 0; i < functions.size(); ++i) {
+ if (functions[i]->getName() == name)
+ return functions[i];
+ }
+ return NULL;
+}
+
diff --git a/src/compiler/DetectCallDepth.h b/src/compiler/DetectCallDepth.h
new file mode 100644
index 0000000..89e85f8
--- /dev/null
+++ b/src/compiler/DetectCallDepth.h
@@ -0,0 +1,80 @@
+//
+// Copyright (c) 2002-2011 The ANGLE Project Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+//
+
+#ifndef COMPILER_DETECT_RECURSION_H_
+#define COMPILER_DETECT_RECURSION_H_
+
+#include "GLSLANG/ShaderLang.h"
+
+#include <limits.h>
+#include "compiler/intermediate.h"
+#include "compiler/VariableInfo.h"
+
+class TInfoSink;
+
+// Traverses intermediate tree to detect function recursion.
+class DetectCallDepth : public TIntermTraverser {
+public:
+ enum ErrorCode {
+ kErrorMissingMain,
+ kErrorRecursion,
+ kErrorMaxDepthExceeded,
+ kErrorNone
+ };
+
+ DetectCallDepth(TInfoSink& infoSync, bool limitCallStackDepth, int maxCallStackDepth);
+ ~DetectCallDepth();
+
+ virtual bool visitAggregate(Visit, TIntermAggregate*);
+
+ bool checkExceedsMaxDepth(int depth);
+
+ ErrorCode detectCallDepth();
+
+private:
+ class FunctionNode {
+ public:
+ static const int kInfiniteCallDepth = INT_MAX;
+
+ FunctionNode(const TString& fname);
+
+ const TString& getName() const;
+
+ // If a function is already in the callee list, this becomes a no-op.
+ void addCallee(FunctionNode* callee);
+
+ // Returns kInifinityCallDepth if recursive function calls are detected.
+ int detectCallDepth(DetectCallDepth* detectCallDepth, int depth);
+
+ // Reset state.
+ void reset();
+
+ private:
+ // mangled function name is unique.
+ TString name;
+
+ // functions that are directly called by this function.
+ TVector<FunctionNode*> callees;
+
+ Visit visit;
+ };
+
+ ErrorCode detectCallDepthForFunction(FunctionNode* func);
+ FunctionNode* findFunctionByName(const TString& name);
+ void resetFunctionNodes();
+
+ TInfoSink& getInfoSink() { return infoSink; }
+
+ TVector<FunctionNode*> functions;
+ FunctionNode* currentFunction;
+ TInfoSink& infoSink;
+ int maxDepth;
+
+ DetectCallDepth(const DetectCallDepth&);
+ void operator=(const DetectCallDepth&);
+};
+
+#endif // COMPILER_DETECT_RECURSION_H_
diff --git a/src/compiler/DetectRecursion.cpp b/src/compiler/DetectRecursion.cpp
deleted file mode 100644
index c09780d..0000000
--- a/src/compiler/DetectRecursion.cpp
+++ /dev/null
@@ -1,125 +0,0 @@
-//
-// Copyright (c) 2002-2011 The ANGLE Project Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style license that can be
-// found in the LICENSE file.
-//
-
-#include "compiler/DetectRecursion.h"
-
-DetectRecursion::FunctionNode::FunctionNode(const TString& fname)
- : name(fname),
- visit(PreVisit)
-{
-}
-
-const TString& DetectRecursion::FunctionNode::getName() const
-{
- return name;
-}
-
-void DetectRecursion::FunctionNode::addCallee(
- DetectRecursion::FunctionNode* callee)
-{
- for (size_t i = 0; i < callees.size(); ++i) {
- if (callees[i] == callee)
- return;
- }
- callees.push_back(callee);
-}
-
-bool DetectRecursion::FunctionNode::detectRecursion()
-{
- ASSERT(visit == PreVisit);
- visit = InVisit;
- for (size_t i = 0; i < callees.size(); ++i) {
- switch (callees[i]->visit) {
- case InVisit:
- // cycle detected, i.e., recursion detected.
- return true;
- case PostVisit:
- break;
- case PreVisit: {
- bool recursion = callees[i]->detectRecursion();
- if (recursion)
- return true;
- break;
- }
- default:
- UNREACHABLE();
- break;
- }
- }
- visit = PostVisit;
- return false;
-}
-
-DetectRecursion::DetectRecursion()
- : currentFunction(NULL)
-{
-}
-
-DetectRecursion::~DetectRecursion()
-{
- for (size_t i = 0; i < functions.size(); ++i)
- delete functions[i];
-}
-
-bool DetectRecursion::visitAggregate(Visit visit, TIntermAggregate* node)
-{
- switch (node->getOp())
- {
- case EOpPrototype:
- // Function declaration.
- // Don't add FunctionNode here because node->getName() is the
- // unmangled function name.
- break;
- case EOpFunction: {
- // Function definition.
- if (visit == PreVisit) {
- currentFunction = findFunctionByName(node->getName());
- if (currentFunction == NULL) {
- currentFunction = new FunctionNode(node->getName());
- functions.push_back(currentFunction);
- }
- }
- break;
- }
- case EOpFunctionCall: {
- // Function call.
- if (visit == PreVisit) {
- ASSERT(currentFunction != NULL);
- FunctionNode* func = findFunctionByName(node->getName());
- if (func == NULL) {
- func = new FunctionNode(node->getName());
- functions.push_back(func);
- }
- currentFunction->addCallee(func);
- }
- break;
- }
- default:
- break;
- }
- return true;
-}
-
-DetectRecursion::ErrorCode DetectRecursion::detectRecursion()
-{
- FunctionNode* main = findFunctionByName("main(");
- if (main == NULL)
- return kErrorMissingMain;
- if (main->detectRecursion())
- return kErrorRecursion;
- return kErrorNone;
-}
-
-DetectRecursion::FunctionNode* DetectRecursion::findFunctionByName(
- const TString& name)
-{
- for (size_t i = 0; i < functions.size(); ++i) {
- if (functions[i]->getName() == name)
- return functions[i];
- }
- return NULL;
-}
-
diff --git a/src/compiler/DetectRecursion.h b/src/compiler/DetectRecursion.h
deleted file mode 100644
index bbac79d..0000000
--- a/src/compiler/DetectRecursion.h
+++ /dev/null
@@ -1,60 +0,0 @@
-//
-// Copyright (c) 2002-2011 The ANGLE Project Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style license that can be
-// found in the LICENSE file.
-//
-
-#ifndef COMPILER_DETECT_RECURSION_H_
-#define COMPILER_DETECT_RECURSION_H_
-
-#include "GLSLANG/ShaderLang.h"
-
-#include "compiler/intermediate.h"
-#include "compiler/VariableInfo.h"
-
-// Traverses intermediate tree to detect function recursion.
-class DetectRecursion : public TIntermTraverser {
-public:
- enum ErrorCode {
- kErrorMissingMain,
- kErrorRecursion,
- kErrorNone
- };
-
- DetectRecursion();
- ~DetectRecursion();
-
- virtual bool visitAggregate(Visit, TIntermAggregate*);
-
- ErrorCode detectRecursion();
-
-private:
- class FunctionNode {
- public:
- FunctionNode(const TString& fname);
-
- const TString& getName() const;
-
- // If a function is already in the callee list, this becomes a no-op.
- void addCallee(FunctionNode* callee);
-
- // Return true if recursive function calls are detected.
- bool detectRecursion();
-
- private:
- // mangled function name is unique.
- TString name;
-
- // functions that are directly called by this function.
- TVector<FunctionNode*> callees;
-
- Visit visit;
- };
-
- FunctionNode* findFunctionByName(const TString& name);
-
- TVector<FunctionNode*> functions;
- FunctionNode* currentFunction;
-};
-
-#endif // COMPILER_DETECT_RECURSION_H_
diff --git a/src/compiler/ShHandle.h b/src/compiler/ShHandle.h
index 2804930..eaf6f68 100644
--- a/src/compiler/ShHandle.h
+++ b/src/compiler/ShHandle.h
@@ -83,8 +83,8 @@
bool InitBuiltInSymbolTable(const ShBuiltInResources& resources);
// Clears the results from the previous compilation.
void clearResults();
- // Return true if function recursion is detected.
- bool detectRecursion(TIntermNode* root);
+ // Return true if function recursion is detected or call depth exceeded.
+ bool detectCallDepth(TIntermNode* root, TInfoSink& infoSink, bool limitCallStackDepth);
// Rewrites a shader's intermediate tree according to the CSS Shaders spec.
void rewriteCSSShader(TIntermNode* root);
// Returns true if the given shader does not exceed the minimum
@@ -106,6 +106,8 @@
// Returns true if the shader does not use sampler dependent values to affect control
// flow or in operations whose time can depend on the input values.
bool enforceFragmentShaderTimingRestrictions(const TDependencyGraph& graph);
+ // Return true if the maximum expression complexity below the limit.
+ bool limitExpressionComplexity(TIntermNode* root);
// Get built-in extensions with default behavior.
const TExtensionBehavior& getExtensionBehavior() const;
// Get the resources set by InitBuiltInSymbolTable
@@ -120,6 +122,8 @@
ShShaderSpec shaderSpec;
int maxUniformVectors;
+ int maxExpressionComplexity;
+ int maxCallStackDepth;
ShBuiltInResources compileResources;
diff --git a/src/compiler/intermediate.h b/src/compiler/intermediate.h
index b5955bf..b1d20f7 100644
--- a/src/compiler/intermediate.h
+++ b/src/compiler/intermediate.h
@@ -18,6 +18,7 @@
#include "GLSLANG/ShaderLang.h"
+#include <algorithm>
#include "compiler/Common.h"
#include "compiler/Types.h"
#include "compiler/ConstantUnion.h"
@@ -546,7 +547,8 @@
inVisit(inVisit),
postVisit(postVisit),
rightToLeft(rightToLeft),
- depth(0) {}
+ depth(0),
+ maxDepth(0) {}
virtual ~TIntermTraverser() {};
virtual void visitSymbol(TIntermSymbol*) {}
@@ -558,7 +560,8 @@
virtual bool visitLoop(Visit visit, TIntermLoop*) {return true;}
virtual bool visitBranch(Visit visit, TIntermBranch*) {return true;}
- void incrementDepth() {depth++;}
+ int getMaxDepth() const {return maxDepth;}
+ void incrementDepth() {depth++; maxDepth = std::max(maxDepth, depth); }
void decrementDepth() {depth--;}
// Return the original name if hash function pointer is NULL;
@@ -572,6 +575,7 @@
protected:
int depth;
+ int maxDepth;
};
#endif // __INTERMEDIATE_H
diff --git a/src/compiler/translator_common.vcxproj b/src/compiler/translator_common.vcxproj
index 7d0195b..3800094 100644
--- a/src/compiler/translator_common.vcxproj
+++ b/src/compiler/translator_common.vcxproj
@@ -141,7 +141,7 @@
<ClCompile Include="BuiltInFunctionEmulator.cpp" />
<ClCompile Include="Compiler.cpp" />
<ClCompile Include="debug.cpp" />
- <ClCompile Include="DetectRecursion.cpp" />
+ <ClCompile Include="DetectCallDepth.cpp" />
<ClCompile Include="Diagnostics.cpp" />
<ClCompile Include="DirectiveHandler.cpp" />
<ClCompile Include="ForLoopUnroll.cpp" />
@@ -231,7 +231,7 @@
<ClInclude Include="Common.h" />
<ClInclude Include="ConstantUnion.h" />
<ClInclude Include="debug.h" />
- <ClInclude Include="DetectRecursion.h" />
+ <ClInclude Include="DetectCallDepth.h" />
<ClInclude Include="Diagnostics.h" />
<ClInclude Include="DirectiveHandler.h" />
<ClInclude Include="ForLoopUnroll.h" />
diff --git a/src/compiler/translator_common.vcxproj.filters b/src/compiler/translator_common.vcxproj.filters
index a6fa99c..e5692b4 100644
--- a/src/compiler/translator_common.vcxproj.filters
+++ b/src/compiler/translator_common.vcxproj.filters
@@ -38,7 +38,7 @@
<ClCompile Include="debug.cpp">
<Filter>Source Files</Filter>
</ClCompile>
- <ClCompile Include="DetectRecursion.cpp">
+ <ClCompile Include="DetectCallDepth.cpp">
<Filter>Source Files</Filter>
</ClCompile>
<ClCompile Include="Diagnostics.cpp">
@@ -154,7 +154,7 @@
<ClInclude Include="debug.h">
<Filter>Header Files</Filter>
</ClInclude>
- <ClInclude Include="DetectRecursion.h">
+ <ClInclude Include="DetectCallDepth.h">
<Filter>Header Files</Filter>
</ClInclude>
<ClInclude Include="Diagnostics.h">
diff --git a/tests/build_tests.gyp b/tests/build_tests.gyp
index 7927f05..c80a444 100644
--- a/tests/build_tests.gyp
+++ b/tests/build_tests.gyp
@@ -67,7 +67,7 @@
'target_name': 'compiler_tests',
'type': 'executable',
'dependencies': [
- '../src/build_angle.gyp:translator_common',
+ '../src/build_angle.gyp:translator_glsl',
'gtest',
'gmock',
],
@@ -79,6 +79,7 @@
],
'sources': [
'../third_party/googlemock/src/gmock_main.cc',
+ 'compiler_tests/ExpressionLimit_test.cpp',
'compiler_tests/VariablePacker_test.cpp',
],
},
diff --git a/tests/compiler_tests/ExpressionLimit_test.cpp b/tests/compiler_tests/ExpressionLimit_test.cpp
new file mode 100644
index 0000000..3af099d
--- /dev/null
+++ b/tests/compiler_tests/ExpressionLimit_test.cpp
@@ -0,0 +1,512 @@
+//
+// Copyright (c) 2002-2013 The ANGLE Project Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+//
+#include <sstream>
+#include <string>
+#include <vector>
+#include "GLSLANG/ShaderLang.h"
+#include "gtest/gtest.h"
+
+#define SHADER(Src) #Src
+
+class ExpressionLimitTest : public testing::Test {
+protected:
+ static const int kMaxExpressionComplexity = 16;
+ static const int kMaxCallStackDepth = 16;
+ static const char* kExpressionTooComplex;
+ static const char* kCallStackTooDeep;
+ static const char* kHasRecursion;
+
+ virtual void SetUp()
+ {
+ memset(&resources, 0, sizeof(resources));
+
+ ASSERT_TRUE(ShInitialize() != 0) << "Could not ShInitialize";
+
+ GenerateResources(&resources);
+ }
+
+ virtual void TearDown()
+ {
+ ASSERT_TRUE(ShFinalize() != 0);
+ }
+
+ // Set up the per compile resources
+ void GenerateResources(ShBuiltInResources* resources)
+ {
+ ShInitBuiltInResources(resources);
+
+ resources->MaxVertexAttribs = 8;
+ resources->MaxVertexUniformVectors = 128;
+ resources->MaxVaryingVectors = 8;
+ resources->MaxVertexTextureImageUnits = 0;
+ resources->MaxCombinedTextureImageUnits = 8;
+ resources->MaxTextureImageUnits = 8;
+ resources->MaxFragmentUniformVectors = 16;
+ resources->MaxDrawBuffers = 1;
+
+ resources->OES_standard_derivatives = 0;
+ resources->OES_EGL_image_external = 0;
+
+ resources->MaxExpressionComplexity = kMaxExpressionComplexity;
+ resources->MaxCallStackDepth = kMaxCallStackDepth;
+ }
+
+ void GenerateLongExpression(int length, std::stringstream* ss)
+ {
+ for (int ii = 0; ii < length; ++ii) {
+ *ss << "+ vec4(" << ii << ")";
+ }
+ }
+
+ std::string GenerateShaderWithLongExpression(int length)
+ {
+ static const char* shaderStart = SHADER(
+ precision mediump float;
+ uniform vec4 u_color;
+ void main()
+ {
+ gl_FragColor = u_color
+ );
+
+ std::stringstream ss;
+ ss << shaderStart;
+ GenerateLongExpression(length, &ss);
+ ss << "; }";
+
+ return ss.str();
+ }
+
+ std::string GenerateShaderWithUnusedLongExpression(int length)
+ {
+ static const char* shaderStart = SHADER(
+ precision mediump float;
+ uniform vec4 u_color;
+ void main()
+ {
+ gl_FragColor = u_color;
+ }
+ vec4 someFunction() {
+ return u_color
+ );
+
+ std::stringstream ss;
+
+ ss << shaderStart;
+ GenerateLongExpression(length, &ss);
+ ss << "; }";
+
+ return ss.str();
+ }
+
+ void GenerateDeepFunctionStack(int length, std::stringstream* ss)
+ {
+ static const char* shaderStart = SHADER(
+ precision mediump float;
+ uniform vec4 u_color;
+ vec4 function0() {
+ return u_color;
+ }
+ );
+
+ *ss << shaderStart;
+ for (int ii = 0; ii < length; ++ii) {
+ *ss << "vec4 function" << (ii + 1) << "() {\n"
+ << " return function" << ii << "();\n"
+ << "}\n";
+ }
+ }
+
+ std::string GenerateShaderWithDeepFunctionStack(int length)
+ {
+ std::stringstream ss;
+
+ GenerateDeepFunctionStack(length, &ss);
+
+ ss << "void main() {\n"
+ << " gl_FragColor = function" << length << "();\n"
+ << "}";
+
+ return ss.str();
+ }
+
+ std::string GenerateShaderWithUnusedDeepFunctionStack(int length)
+ {
+ std::stringstream ss;
+
+ GenerateDeepFunctionStack(length, &ss);
+
+ ss << "void main() {\n"
+ << " gl_FragColor = vec4(0,0,0,0);\n"
+ << "}";
+
+
+ return ss.str();
+ }
+
+ // Compiles a shader and if there's an error checks for a specific
+ // substring in the error log. This way we know the error is specific
+ // to the issue we are testing.
+ bool CheckShaderCompilation(ShHandle compiler,
+ const char* source,
+ int compileOptions,
+ const char* expected_error) {
+ bool success = ShCompile(compiler, &source, 1, compileOptions);
+ if (success) {
+ success = !expected_error;
+ } else {
+ size_t bufferLen = 0;
+ ShGetInfo(compiler, SH_INFO_LOG_LENGTH, &bufferLen);
+ char* buffer(new char [bufferLen]);
+ ShGetInfoLog(compiler, buffer);
+ std::string log(buffer, buffer + bufferLen);
+ delete [] buffer;
+ if (expected_error)
+ success = log.find(expected_error) != std::string::npos;
+
+ EXPECT_TRUE(success) << log << "\n----shader----\n" << source;
+ }
+ return success;
+ }
+
+ ShBuiltInResources resources;
+};
+
+const char* ExpressionLimitTest::kExpressionTooComplex =
+ "Expression too complex";
+const char* ExpressionLimitTest::kCallStackTooDeep =
+ "call stack too deep";
+const char* ExpressionLimitTest::kHasRecursion =
+ "Function recursion detected";
+
+TEST_F(ExpressionLimitTest, ExpressionComplexity)
+{
+ ShShaderSpec spec = SH_WEBGL_SPEC;
+ ShShaderOutput output = SH_ESSL_OUTPUT;
+ ShHandle vertexCompiler = ShConstructCompiler(
+ SH_FRAGMENT_SHADER, spec, output, &resources);
+ int compileOptions = SH_LIMIT_EXPRESSION_COMPLEXITY;
+
+ // Test expression under the limit passes.
+ EXPECT_TRUE(CheckShaderCompilation(
+ vertexCompiler,
+ GenerateShaderWithLongExpression(
+ kMaxExpressionComplexity - 10).c_str(),
+ compileOptions, NULL));
+ // Test expression over the limit fails.
+ EXPECT_TRUE(CheckShaderCompilation(
+ vertexCompiler,
+ GenerateShaderWithLongExpression(
+ kMaxExpressionComplexity + 10).c_str(),
+ compileOptions, kExpressionTooComplex));
+ // Test expression over the limit without a limit does not fail.
+ EXPECT_TRUE(CheckShaderCompilation(
+ vertexCompiler,
+ GenerateShaderWithLongExpression(
+ kMaxExpressionComplexity + 10).c_str(),
+ compileOptions & ~SH_LIMIT_EXPRESSION_COMPLEXITY, NULL));
+}
+
+TEST_F(ExpressionLimitTest, UnusedExpressionComplexity)
+{
+ ShShaderSpec spec = SH_WEBGL_SPEC;
+ ShShaderOutput output = SH_ESSL_OUTPUT;
+ ShHandle vertexCompiler = ShConstructCompiler(
+ SH_FRAGMENT_SHADER, spec, output, &resources);
+ int compileOptions = SH_LIMIT_EXPRESSION_COMPLEXITY;
+
+ // Test expression under the limit passes.
+ EXPECT_TRUE(CheckShaderCompilation(
+ vertexCompiler,
+ GenerateShaderWithUnusedLongExpression(
+ kMaxExpressionComplexity - 10).c_str(),
+ compileOptions, NULL));
+ // Test expression over the limit fails.
+ EXPECT_TRUE(CheckShaderCompilation(
+ vertexCompiler,
+ GenerateShaderWithUnusedLongExpression(
+ kMaxExpressionComplexity + 10).c_str(),
+ compileOptions, kExpressionTooComplex));
+ // Test expression over the limit without a limit does not fail.
+ EXPECT_TRUE(CheckShaderCompilation(
+ vertexCompiler,
+ GenerateShaderWithUnusedLongExpression(
+ kMaxExpressionComplexity + 10).c_str(),
+ compileOptions & ~SH_LIMIT_EXPRESSION_COMPLEXITY, NULL));
+}
+
+TEST_F(ExpressionLimitTest, CallStackDepth)
+{
+ ShShaderSpec spec = SH_WEBGL_SPEC;
+ ShShaderOutput output = SH_ESSL_OUTPUT;
+ ShHandle vertexCompiler = ShConstructCompiler(
+ SH_FRAGMENT_SHADER, spec, output, &resources);
+ int compileOptions = SH_LIMIT_CALL_STACK_DEPTH;
+
+ // Test call stack under the limit passes.
+ EXPECT_TRUE(CheckShaderCompilation(
+ vertexCompiler,
+ GenerateShaderWithDeepFunctionStack(
+ kMaxCallStackDepth - 10).c_str(),
+ compileOptions, NULL));
+ // Test call stack over the limit fails.
+ EXPECT_TRUE(CheckShaderCompilation(
+ vertexCompiler,
+ GenerateShaderWithDeepFunctionStack(
+ kMaxCallStackDepth + 10).c_str(),
+ compileOptions, kCallStackTooDeep));
+ // Test call stack over the limit without limit does not fail.
+ EXPECT_TRUE(CheckShaderCompilation(
+ vertexCompiler,
+ GenerateShaderWithDeepFunctionStack(
+ kMaxCallStackDepth + 10).c_str(),
+ compileOptions & ~SH_LIMIT_CALL_STACK_DEPTH, NULL));
+}
+
+TEST_F(ExpressionLimitTest, UnusedCallStackDepth)
+{
+ ShShaderSpec spec = SH_WEBGL_SPEC;
+ ShShaderOutput output = SH_ESSL_OUTPUT;
+ ShHandle vertexCompiler = ShConstructCompiler(
+ SH_FRAGMENT_SHADER, spec, output, &resources);
+ int compileOptions = SH_LIMIT_CALL_STACK_DEPTH;
+
+ // Test call stack under the limit passes.
+ EXPECT_TRUE(CheckShaderCompilation(
+ vertexCompiler,
+ GenerateShaderWithUnusedDeepFunctionStack(
+ kMaxCallStackDepth - 10).c_str(),
+ compileOptions, NULL));
+ // Test call stack over the limit fails.
+ EXPECT_TRUE(CheckShaderCompilation(
+ vertexCompiler,
+ GenerateShaderWithUnusedDeepFunctionStack(
+ kMaxCallStackDepth + 10).c_str(),
+ compileOptions, kCallStackTooDeep));
+ // Test call stack over the limit without limit does not fail.
+ EXPECT_TRUE(CheckShaderCompilation(
+ vertexCompiler,
+ GenerateShaderWithUnusedDeepFunctionStack(
+ kMaxCallStackDepth + 10).c_str(),
+ compileOptions & ~SH_LIMIT_CALL_STACK_DEPTH, NULL));
+}
+
+TEST_F(ExpressionLimitTest, Recursion)
+{
+ ShShaderSpec spec = SH_WEBGL_SPEC;
+ ShShaderOutput output = SH_ESSL_OUTPUT;
+ ShHandle vertexCompiler = ShConstructCompiler(
+ SH_FRAGMENT_SHADER, spec, output, &resources);
+ int compileOptions = 0;
+
+ static const char* shaderWithRecursion0 = SHADER(
+ precision mediump float;
+ uniform vec4 u_color;
+ vec4 someFunc() {
+ return someFunc();
+ }
+
+ void main() {
+ gl_FragColor = u_color * someFunc();
+ }
+ );
+
+ static const char* shaderWithRecursion1 = SHADER(
+ precision mediump float;
+ uniform vec4 u_color;
+
+ vec4 someFunc();
+
+ vec4 someFunc1() {
+ return someFunc();
+ }
+
+ vec4 someFunc() {
+ return someFunc1();
+ }
+
+ void main() {
+ gl_FragColor = u_color * someFunc();
+ }
+ );
+
+ static const char* shaderWithRecursion2 = SHADER(
+ precision mediump float;
+ uniform vec4 u_color;
+ vec4 someFunc() {
+ if (u_color.x > 0.5) {
+ return someFunc();
+ } else {
+ return vec4(1);
+ }
+ }
+
+ void main() {
+ gl_FragColor = someFunc();
+ }
+ );
+
+ static const char* shaderWithRecursion3 = SHADER(
+ precision mediump float;
+ uniform vec4 u_color;
+ vec4 someFunc() {
+ if (u_color.x > 0.5) {
+ return vec4(1);
+ } else {
+ return someFunc();
+ }
+ }
+
+ void main() {
+ gl_FragColor = someFunc();
+ }
+ );
+
+ static const char* shaderWithRecursion4 = SHADER(
+ precision mediump float;
+ uniform vec4 u_color;
+ vec4 someFunc() {
+ return (u_color.x > 0.5) ? vec4(1) : someFunc();
+ }
+
+ void main() {
+ gl_FragColor = someFunc();
+ }
+ );
+
+ static const char* shaderWithRecursion5 = SHADER(
+ precision mediump float;
+ uniform vec4 u_color;
+ vec4 someFunc() {
+ return (u_color.x > 0.5) ? someFunc() : vec4(1);
+ }
+
+ void main() {
+ gl_FragColor = someFunc();
+ }
+ );
+
+ static const char* shaderWithRecursion6 = SHADER(
+ precision mediump float;
+ uniform vec4 u_color;
+ vec4 someFunc() {
+ return someFunc();
+ }
+
+ void main() {
+ gl_FragColor = u_color;
+ }
+ );
+
+ static const char* shaderWithNoRecursion = SHADER(
+ precision mediump float;
+ uniform vec4 u_color;
+
+ vec3 rgb(int r, int g, int b) {
+ return vec3(float(r) / 255.0, float(g) / 255.0, float(b) / 255.0);
+ }
+
+ // these external calls used to incorrectly trigger
+ // recursion detection.
+ vec3 hairColor0 = rgb(151, 200, 234);
+ vec3 faceColor2 = rgb(183, 148, 133);
+
+ void main() {
+ gl_FragColor = u_color + vec4(hairColor0 + faceColor2, 0);
+ }
+ );
+
+ static const char* shaderWithRecursion7 = SHADER(
+ precision mediump float;
+ uniform vec4 u_color;
+
+ vec4 function2() {
+ return u_color;
+ }
+
+ vec4 function1() {
+ vec4 a = function2();
+ vec4 b = function1();
+ return a + b;
+ }
+
+ void main() {
+ gl_FragColor = function1();
+ }
+ );
+
+ static const char* shaderWithRecursion8 = SHADER(
+ precision mediump float;
+ uniform vec4 u_color;
+
+ vec4 function1();
+
+ vec4 function3() {
+ return function1();
+ }
+
+ vec4 function2() {
+ return function3();
+ }
+
+ vec4 function1() {
+ return function2();
+ }
+
+ void main() {
+ gl_FragColor = function1();
+ }
+ );
+
+ // Check simple recursions fails.
+ EXPECT_TRUE(CheckShaderCompilation(
+ vertexCompiler, shaderWithRecursion0,
+ compileOptions, kHasRecursion));
+ // Check simple recursions fails.
+ EXPECT_TRUE(CheckShaderCompilation(
+ vertexCompiler, shaderWithRecursion1,
+ compileOptions, kHasRecursion));
+ // Check if recursions fails.
+ EXPECT_TRUE(CheckShaderCompilation(
+ vertexCompiler, shaderWithRecursion2,
+ compileOptions, kHasRecursion));
+ // Check if recursions fails.
+ EXPECT_TRUE(CheckShaderCompilation(
+ vertexCompiler, shaderWithRecursion3,
+ compileOptions, kHasRecursion));
+ // Check ternary recursions fails.
+ EXPECT_TRUE(CheckShaderCompilation(
+ vertexCompiler, shaderWithRecursion4,
+ compileOptions, kHasRecursion));
+ // Check ternary recursions fails.
+ EXPECT_TRUE(CheckShaderCompilation(
+ vertexCompiler, shaderWithRecursion5,
+ compileOptions, kHasRecursion));
+ // Check unused recursions passes.
+ EXPECT_TRUE(CheckShaderCompilation(
+ vertexCompiler, shaderWithRecursion6,
+ compileOptions, NULL));
+ EXPECT_TRUE(CheckShaderCompilation(
+ vertexCompiler, shaderWithRecursion7,
+ compileOptions, kHasRecursion));
+ EXPECT_TRUE(CheckShaderCompilation(
+ vertexCompiler, shaderWithRecursion8,
+ compileOptions, kHasRecursion));
+ // Check unused recursions fails if limiting call stack
+ // since we check all paths.
+ EXPECT_TRUE(CheckShaderCompilation(
+ vertexCompiler, shaderWithRecursion6,
+ compileOptions | SH_LIMIT_CALL_STACK_DEPTH, kHasRecursion));
+
+ // Check unused recursions passes.
+ EXPECT_TRUE(CheckShaderCompilation(
+ vertexCompiler, shaderWithNoRecursion,
+ compileOptions, NULL));
+ // Check unused recursions passes if limiting call stack.
+ EXPECT_TRUE(CheckShaderCompilation(
+ vertexCompiler, shaderWithNoRecursion,
+ compileOptions | SH_LIMIT_CALL_STACK_DEPTH, NULL));
+}
+