Add expression complexity and call stack depth limits.



git-svn-id: http://angleproject.googlecode.com/svn/trunk@2242 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 e32d3f0..b2b6e11 100644
--- a/include/GLSLANG/ShaderLang.h
+++ b/include/GLSLANG/ShaderLang.h
@@ -159,7 +159,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.
@@ -222,6 +228,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 7b664d3..456f6a2 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 5c02e64..ff43485 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.
@@ -267,24 +276,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;
     }
 }
 
@@ -326,6 +338,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 daecd86..f863e54 100644
--- a/src/compiler/ShHandle.h
+++ b/src/compiler/ShHandle.h
@@ -81,8 +81,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
@@ -104,6 +104,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;
 
@@ -116,6 +118,8 @@
     ShShaderSpec shaderSpec;
 
     int maxUniformVectors;
+    int maxExpressionComplexity;
+    int maxCallStackDepth;
 
     // Built-in symbol table for the given language, spec, and resources.
     // It is preserved from compile-to-compile.
diff --git a/src/compiler/intermediate.h b/src/compiler/intermediate.h
index f471063..80eeec0 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"
@@ -542,7 +543,8 @@
             inVisit(inVisit),
             postVisit(postVisit),
             rightToLeft(rightToLeft),
-            depth(0) {}
+            depth(0),
+            maxDepth(0) {}
     virtual ~TIntermTraverser() {};
 
     virtual void visitSymbol(TIntermSymbol*) {}
@@ -554,7 +556,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;
@@ -568,6 +571,7 @@
 
 protected:
     int depth;
+    int maxDepth;
 };
 
 #endif // __INTERMEDIATE_H
diff --git a/src/compiler/translator_common.vcxproj b/src/compiler/translator_common.vcxproj
index 9ddfc13..ad86751 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 2de9243..eddf9da 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">

@@ -151,7 +151,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));
+}
+