text: //
  // 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_TRANSLATOR_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H
  #define COMPILER_TRANSLATOR_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H
  
  #include "compiler/translator/depgraph/DependencyGraph.h"
  
  //
  // Creates a dependency graph of symbols, function calls, conditions etc. by
  // traversing a intermediate tree.
  //
  class TDependencyGraphBuilder : public TIntermTraverser
  {
    public:
      static void build(TIntermNode *node, TDependencyGraph *graph);
  
      virtual void visitSymbol(TIntermSymbol *);
      virtual bool visitBinary(Visit visit, TIntermBinary *);
      virtual bool visitSelection(Visit visit, TIntermSelection *);
      virtual bool visitAggregate(Visit visit, TIntermAggregate *);
      virtual bool visitLoop(Visit visit, TIntermLoop *);
  
    private:
      typedef std::stack<TGraphSymbol *> TSymbolStack;
      typedef std::set<TGraphParentNode *> TParentNodeSet;
  
      //
      // For collecting the dependent nodes of assignments, conditions, etc.
      // while traversing the intermediate tree.
      //
      // This data structure is stack of sets. Each set contains dependency graph
      // parent nodes.
      //
      class TNodeSetStack
      {
        public:
          TNodeSetStack() {};
          ~TNodeSetStack() { clear(); }
  
          // This should only be called after a pushSet.
          // Returns NULL if the top set is empty.
          TParentNodeSet *getTopSet() const
          {
              ASSERT(!mNodeSets.empty());
              TParentNodeSet *topSet = mNodeSets.top();
              return !topSet->empty() ? topSet : NULL;
          }
  
          void pushSet() { mNodeSets.push(new TParentNodeSet()); }
          void popSet()
          {
              ASSERT(!mNodeSets.empty());
              delete mNodeSets.top();
              mNodeSets.pop();
          }
  
          // Pops the top set and adds its contents to the new top set.
          // This should only be called after a pushSet.
          // If there is no set below the top set, the top set is just deleted.
          void popSetIntoNext()
          {
              ASSERT(!mNodeSets.empty());
              TParentNodeSet *oldTopSet = mNodeSets.top();
              mNodeSets.pop();
  
              if (!mNodeSets.empty())
              {
                  TParentNodeSet *newTopSet = mNodeSets.top();
                  newTopSet->insert(oldTopSet->begin(), oldTopSet->end());
              }
  
              delete oldTopSet;
          }
  
          // Does nothing if there is no top set.
          // This can be called when there is no top set if we are visiting
          // symbols that are not under an assignment or condition.
          // We don't need to track those symbols.
          void insertIntoTopSet(TGraphParentNode *node)
          {
              if (mNodeSets.empty())
                  return;
  
              mNodeSets.top()->insert(node);
          }
  
          void clear()
          {
              while (!mNodeSets.empty())
                  popSet();
          }
  
        private:
          typedef std::stack<TParentNodeSet *> TParentNodeSetStack;
  
          TParentNodeSetStack mNodeSets;
      };
  
      //
      // An instance of this class pushes a new node set when instantiated.
      // When the instance goes out of scope, it and pops the node set.
      //
      class TNodeSetMaintainer
      {
        public:
          TNodeSetMaintainer(TDependencyGraphBuilder *factory)
              : mSets(factory->mNodeSets)
          {
              mSets.pushSet();
          }
          ~TNodeSetMaintainer() { mSets.popSet(); }
        protected:
          TNodeSetStack &mSets;
      };
  
      //
      // An instance of this class pushes a new node set when instantiated.
      // When the instance goes out of scope, it and pops the top node set and adds
      // its contents to the new top node set.
      //
      class TNodeSetPropagatingMaintainer
      {
        public:
          TNodeSetPropagatingMaintainer(TDependencyGraphBuilder *factory)
              : mSets(factory->mNodeSets)
          {
              mSets.pushSet();
          }
          ~TNodeSetPropagatingMaintainer() { mSets.popSetIntoNext(); }
        protected:
          TNodeSetStack &mSets;
      };
  
      //
      // An instance of this class keeps track of the leftmost symbol while we're
      // exploring an assignment.
      // It will push the placeholder symbol kLeftSubtree when instantiated under a
      // left subtree, and kRightSubtree under a right subtree.
      // When it goes out of scope, it will pop the leftmost symbol at the top of the
      // scope.
      // During traversal, the TDependencyGraphBuilder will replace kLeftSubtree with
      // a real symbol.
      // kRightSubtree will never be replaced by a real symbol because we are tracking
      // the leftmost symbol.
      //
      class TLeftmostSymbolMaintainer
      {
        public:
          TLeftmostSymbolMaintainer(
              TDependencyGraphBuilder *factory, TGraphSymbol &subtree)
              : mLeftmostSymbols(factory->mLeftmostSymbols)
          {
              mNeedsPlaceholderSymbol =
                  mLeftmostSymbols.empty() || mLeftmostSymbols.top() != &subtree;
              if (mNeedsPlaceholderSymbol)
                  mLeftmostSymbols.push(&subtree);
          }
  
          ~TLeftmostSymbolMaintainer()
          {
              if (mNeedsPlaceholderSymbol)
                  mLeftmostSymbols.pop();
          }
  
        protected:
          TSymbolStack& mLeftmostSymbols;
          bool mNeedsPlaceholderSymbol;
      };
  
      TDependencyGraphBuilder(TDependencyGraph *graph)
          : TIntermTraverser(true, false, false),
            mLeftSubtree(NULL),
            mRightSubtree(NULL),
            mGraph(graph) {}
      void build(TIntermNode *intermNode) { intermNode->traverse(this); }
  
      void connectMultipleNodesToSingleNode(
          TParentNodeSet *nodes, TGraphNode *node) const;
  
      void visitAssignment(TIntermBinary *);
      void visitLogicalOp(TIntermBinary *);
      void visitBinaryChildren(TIntermBinary *);
      void visitFunctionDefinition(TIntermAggregate *);
      void visitFunctionCall(TIntermAggregate *intermFunctionCall);
      void visitAggregateChildren(TIntermAggregate *);
  
      TGraphSymbol mLeftSubtree;
      TGraphSymbol mRightSubtree;
  
      TDependencyGraph *mGraph;
      TNodeSetStack mNodeSets;
      TSymbolStack mLeftmostSymbols;
  };
  
  #endif  // COMPILER_TRANSLATOR_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H
  