Detect function recursion and reject a shader if detected.

Detect function recursion and reject a shader if detected.

ANGLEBUG=191
TEST=shaders with function recursion are rejected.
Committed: http://code.google.com/p/angleproject/source/detail?r=711

[Zhenyao Mo, 2011-07-29 23:24:57]

Please review.

[kbr1, 2011-07-30 00:57:19]

This looks great overall -- LGTM and thanks for taking care of it -- but we
definitely need tests for it. At a minimum we should add something to the WebGL
conformance suite. Perhaps gman can advise offline about adding something to the
real GLES2 conformance suite.

http://codereview.appspot.com/4808061/diff/1/src/compiler/DetectRecursion.cpp
File src/compiler/DetectRecursion.cpp (right):

http://codereview.appspot.com/4808061/diff/1/src/compiler/DetectRecursion.cpp...
src/compiler/DetectRecursion.cpp:115: if (func == NULL) {
Should func ever be NULL? If it is, that means that the function didn't have a
prototype and wasn't defined before the call site, so I think that compilation
will ultimately fail. I think we should fail the recursion detection step in
this case. (Or does this happen for builtins?)

http://codereview.appspot.com/4808061/diff/1/src/compiler/DetectRecursion.h
File src/compiler/DetectRecursion.h (right):

http://codereview.appspot.com/4808061/diff/1/src/compiler/DetectRecursion.h#n...
src/compiler/DetectRecursion.h:15: class FunctionNode {
I think this class should be defined inside the DetectRecursion class. As a
matter of fact this can be done in the private section of the DetectRecursion
class to eliminate the leakage of this name.

http://codereview.appspot.com/4808061/diff/1/src/compiler/DetectRecursion.h#n...
src/compiler/DetectRecursion.h:37: // Traverses intermediate tree to detect
statis function recursions.
statis -> static
recursions -> recursion

[Zhenyao Mo, 2011-07-30 01:09:10]

I'll add a test case to webgl conformance test suite.  In the long run, we
should add unittests to ANGLE.

http://codereview.appspot.com/4808061/diff/1/src/compiler/DetectRecursion.cpp
File src/compiler/DetectRecursion.cpp (right):

http://codereview.appspot.com/4808061/diff/1/src/compiler/DetectRecursion.cpp...
src/compiler/DetectRecursion.cpp:115: if (func == NULL) {
On 2011/07/30 00:57:20, kbr1 wrote:
> Should func ever be NULL? If it is, that means that the function didn't have a
> prototype and wasn't defined before the call site, so I think that compilation
> will ultimately fail. I think we should fail the recursion detection step in
> this case. (Or does this happen for builtins?)

I agree with you.  The issue is that EOpPrototype part wasn't hit at all in my
testing, so I have to add code here.  Yes, this will unnecessarily include
built-in functions into the detection.

Maybe Alok or Nicolas can shed some lights here?  Is it a bug or is it by
design?  When I declare a function prototype, the case EOpPrototype here wasn't
hit.  If it's a bug, I'll fix it before landing this CL.

http://codereview.appspot.com/4808061/diff/1/src/compiler/DetectRecursion.h
File src/compiler/DetectRecursion.h (right):

http://codereview.appspot.com/4808061/diff/1/src/compiler/DetectRecursion.h#n...
src/compiler/DetectRecursion.h:15: class FunctionNode {
On 2011/07/30 00:57:20, kbr1 wrote:
> I think this class should be defined inside the DetectRecursion class. As a
> matter of fact this can be done in the private section of the DetectRecursion
> class to eliminate the leakage of this name.

Done.

http://codereview.appspot.com/4808061/diff/1/src/compiler/DetectRecursion.h#n...
src/compiler/DetectRecursion.h:37: // Traverses intermediate tree to detect
statis function recursions.
On 2011/07/30 00:57:20, kbr1 wrote:
> statis -> static
> recursions -> recursion

Done.

[Zhenyao Mo, 2011-07-30 01:46:35]

http://codereview.appspot.com/4808061/diff/1/src/compiler/DetectRecursion.cpp
File src/compiler/DetectRecursion.cpp (right):

http://codereview.appspot.com/4808061/diff/1/src/compiler/DetectRecursion.cpp...
src/compiler/DetectRecursion.cpp:115: if (func == NULL) {
Further investigation: EOpPrototype path does get hit.  Only that the function
names here are unmangled (i.e., the original name), and in EOpFunction and
EOpFunctionCall, the function names are mangled and unique.

Instead of mangle the function names in EOpPrototype, the code is much simpler
if we add functions to the list as we define them and call them.  This is OK
because we already compiled the shader, so any invalid function calls should
already cause rejection.

[nicolas, 2011-08-01 13:45:20]

The approach looks good to me.

http://codereview.appspot.com/4808061/diff/7002/src/compiler/DetectRecursion.h
File src/compiler/DetectRecursion.h (right):

http://codereview.appspot.com/4808061/diff/7002/src/compiler/DetectRecursion....
src/compiler/DetectRecursion.h:27: virtual void visitSymbol(TIntermSymbol*);
Visiting methods which don't perform any actions don't have to be overloaded.
TIntermTraverser already provides defaults for them.

[Zhenyao Mo, 2011-08-01 17:02:01]

On 2011/08/01 13:45:20, nicolas wrote:
> The approach looks good to me.
> 
> http://codereview.appspot.com/4808061/diff/7002/src/compiler/DetectRecursion.h
> File src/compiler/DetectRecursion.h (right):
> 
>
http://codereview.appspot.com/4808061/diff/7002/src/compiler/DetectRecursion....
> src/compiler/DetectRecursion.h:27: virtual void visitSymbol(TIntermSymbol*);
> Visiting methods which don't perform any actions don't have to be overloaded.
> TIntermTraverser already provides defaults for them.

Thanks.  I'll do a cleanup CL then, for this and a few other classes with the
same unnecessary overloading.