The Tor Browser / file revision

 //

 // Copyright (c) 2012 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_DEPGRAPH_DEPENDENCY_GRAPH_H

 #define COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_H

 #include "compiler/intermediate.h"

 #include <set>

 #include <stack>

 class TGraphNode;

 class TGraphParentNode;

 class TGraphArgument;

 class TGraphFunctionCall;

 class TGraphSymbol;

 class TGraphSelection;

 class TGraphLoop;

 class TGraphLogicalOp;

 class TDependencyGraphTraverser;

 class TDependencyGraphOutput;

 typedef std::set<TGraphNode*> TGraphNodeSet;

 typedef std::vector<TGraphNode*> TGraphNodeVector;

 typedef std::vector<TGraphSymbol*> TGraphSymbolVector;

 typedef std::vector<TGraphFunctionCall*> TFunctionCallVector;

 //

 // Base class for all dependency graph nodes.

 //

 class TGraphNode {

 public:

     TGraphNode(TIntermNode* node) : intermNode(node) {}

     virtual ~TGraphNode() {}

     virtual void traverse(TDependencyGraphTraverser* graphTraverser);

 protected:

     TIntermNode* intermNode;

 };

 //

 // Base class for dependency graph nodes that may have children.

 //

 class TGraphParentNode : public TGraphNode {

 public:

     TGraphParentNode(TIntermNode* node) : TGraphNode(node) {}

     virtual ~TGraphParentNode() {}

     void addDependentNode(TGraphNode* node) { if (node != this) mDependentNodes.insert(node); }

     virtual void traverse(TDependencyGraphTraverser* graphTraverser);

 private:

     TGraphNodeSet mDependentNodes;

 };

 //

 // Handle function call arguments.

 //

 class TGraphArgument : public TGraphParentNode {

 public:

     TGraphArgument(TIntermAggregate* intermFunctionCall, int argumentNumber)

         : TGraphParentNode(intermFunctionCall)

         , mArgumentNumber(argumentNumber) {}

     virtual ~TGraphArgument() {}

     const TIntermAggregate* getIntermFunctionCall() const { return intermNode->getAsAggregate(); }

     int getArgumentNumber() const { return mArgumentNumber; }

     virtual void traverse(TDependencyGraphTraverser* graphTraverser);

 private:

     int mArgumentNumber;

 };

 //

 // Handle function calls.

 //

 class TGraphFunctionCall : public TGraphParentNode {

 public:

     TGraphFunctionCall(TIntermAggregate* intermFunctionCall)

         : TGraphParentNode(intermFunctionCall) {}

     virtual ~TGraphFunctionCall() {}

     const TIntermAggregate* getIntermFunctionCall() const { return intermNode->getAsAggregate(); }

     virtual void traverse(TDependencyGraphTraverser* graphTraverser);

 };

 //

 // Handle symbols.

 //

 class TGraphSymbol : public TGraphParentNode {

 public:

     TGraphSymbol(TIntermSymbol* intermSymbol) : TGraphParentNode(intermSymbol) {}

     virtual ~TGraphSymbol() {}

     const TIntermSymbol* getIntermSymbol() const { return intermNode->getAsSymbolNode(); }

     virtual void traverse(TDependencyGraphTraverser* graphTraverser);

 };

 //

 // Handle if statements and ternary operators.

 //

 class TGraphSelection : public TGraphNode {

 public:

     TGraphSelection(TIntermSelection* intermSelection) : TGraphNode(intermSelection) {}

     virtual ~TGraphSelection() {}

     const TIntermSelection* getIntermSelection() const { return intermNode->getAsSelectionNode(); }

     virtual void traverse(TDependencyGraphTraverser* graphTraverser);

 };

 //

 // Handle for, do-while, and while loops.

 //

 class TGraphLoop : public TGraphNode {

 public:

     TGraphLoop(TIntermLoop* intermLoop) : TGraphNode(intermLoop) {}

     virtual ~TGraphLoop() {}

     const TIntermLoop* getIntermLoop() const { return intermNode->getAsLoopNode(); }

     virtual void traverse(TDependencyGraphTraverser* graphTraverser);

 };

 //

 // Handle logical and, or.

 //

 class TGraphLogicalOp : public TGraphNode {

 public:

     TGraphLogicalOp(TIntermBinary* intermLogicalOp) : TGraphNode(intermLogicalOp) {}

     virtual ~TGraphLogicalOp() {}

     const TIntermBinary* getIntermLogicalOp() const { return intermNode->getAsBinaryNode(); }

     const char* getOpString() const;

     virtual void traverse(TDependencyGraphTraverser* graphTraverser);

 };

 //

 // A dependency graph of symbols, function calls, conditions etc.

 //

 // This class provides an interface to the entry points of the dependency graph.

 //

 // Dependency graph nodes should be created by using one of the provided "create..." methods.

 // This class (and nobody else) manages the memory of the created nodes.

 // Nodes may not be removed after being added, so all created nodes will exist while the

 // TDependencyGraph instance exists.

 //

 class TDependencyGraph {

 public:

     TDependencyGraph(TIntermNode* intermNode);

     ~TDependencyGraph();

     TGraphNodeVector::const_iterator begin() const { return mAllNodes.begin(); }

     TGraphNodeVector::const_iterator end() const { return mAllNodes.end(); }

     TGraphSymbolVector::const_iterator beginSamplerSymbols() const

     {

         return mSamplerSymbols.begin();

     }

     TGraphSymbolVector::const_iterator endSamplerSymbols() const

     {

         return mSamplerSymbols.end();

     }

     TFunctionCallVector::const_iterator beginUserDefinedFunctionCalls() const

     {

         return mUserDefinedFunctionCalls.begin();

     }

     TFunctionCallVector::const_iterator endUserDefinedFunctionCalls() const

     {

         return mUserDefinedFunctionCalls.end();

     }

     TGraphArgument* createArgument(TIntermAggregate* intermFunctionCall, int argumentNumber);

     TGraphFunctionCall* createFunctionCall(TIntermAggregate* intermFunctionCall);

     TGraphSymbol* getOrCreateSymbol(TIntermSymbol* intermSymbol);

     TGraphSelection* createSelection(TIntermSelection* intermSelection);

     TGraphLoop* createLoop(TIntermLoop* intermLoop);

     TGraphLogicalOp* createLogicalOp(TIntermBinary* intermLogicalOp);

 private:

     typedef TMap<int, TGraphSymbol*> TSymbolIdMap;

     typedef std::pair<int, TGraphSymbol*> TSymbolIdPair;

     TGraphNodeVector mAllNodes;

     TGraphSymbolVector mSamplerSymbols;

     TFunctionCallVector mUserDefinedFunctionCalls;

     TSymbolIdMap mSymbolIdMap;

 };

 //

 // For traversing the dependency graph. Users should derive from this,

 // put their traversal specific data in it, and then pass it to a

 // traverse method.

 //

 // When using this, just fill in the methods for nodes you want visited.

 //

 class TDependencyGraphTraverser {

 public:

     TDependencyGraphTraverser() : mDepth(0) {}

     virtual void visitSymbol(TGraphSymbol* symbol) {};

     virtual void visitArgument(TGraphArgument* selection) {};

     virtual void visitFunctionCall(TGraphFunctionCall* functionCall) {};

     virtual void visitSelection(TGraphSelection* selection) {};

     virtual void visitLoop(TGraphLoop* loop) {};

     virtual void visitLogicalOp(TGraphLogicalOp* logicalOp) {};

     int getDepth() const { return mDepth; }

     void incrementDepth() { ++mDepth; }

     void decrementDepth() { --mDepth; }

     void clearVisited() { mVisited.clear(); }

     void markVisited(TGraphNode* node) { mVisited.insert(node); }

     bool isVisited(TGraphNode* node) const { return mVisited.find(node) != mVisited.end(); }

 private:

     int mDepth;

     TGraphNodeSet mVisited;

 };

 #endif