renderdoc/3rdparty/glslang/glslang/MachineIndependent/linkValidate.cpp
//
// See if the call graph contains any static recursion, which is disallowed
// by the specification.
//
See if the call graph contains any static recursion, which is disallowed
by the specification.
See if the call graph contains any static recursion which is disallowed by the specification .
void TIntermediate::checkCallGraphCycles(TInfoSink& infoSink)
{
    for (TGraph::iterator call = callGraph.begin(); call != callGraph.end(); ++call) {
        call->visited = false;
        call->currentPath = false;
        call->errorGiven = false;
    }
     Loop, looking for a new connected subgraph.  One subgraph is handled per loop iteration.
    TCall* newRoot;
    do {
         See if we have unvisited parts of the graph.
        newRoot = 0;
        for (TGraph::iterator call = callGraph.begin(); call != callGraph.end(); ++call) {
            if (! call->visited) {
                newRoot = &(*call);
                break;
            }
        }
         If not, we are done.
        if (! newRoot)
            break;
         Otherwise, we found a new subgraph, process it:
         See what all can be reached by this new root, and if any of
         that is recursive.  This is done by depth-first traversals, seeing
         if a new call is found that was already in the currentPath (a back edge),
         thereby detecting recursion.
        std::list<TCall*> stack;
        newRoot->currentPath = true;  currentPath will be true iff it is on the stack
        stack.push_back(newRoot);
        while (! stack.empty()) {
             get a caller
            TCall* call = stack.back();
             Add to the stack just one callee.
             This algorithm always terminates, because only !visited and !currentPath causes a push
             and all pushes change currentPath to true, and all pops change visited to true.
            TGraph::iterator child = callGraph.begin();
            for (; child != callGraph.end(); ++child) {
                 If we already visited this node, its whole subgraph has already been processed, so skip it.
                if (child->visited)
                    continue;
                if (call->callee == child->caller) {
                    if (child->currentPath) {
                         Then, we found a back edge
                        if (! child->errorGiven) {
                            error(infoSink, "Recursion detected:");
                            infoSink.info << "    " << call->callee << " calling " << child->callee << "\n";
                            child->errorGiven = true;
                            recursive = true;
                        }
                    } else {
                        child->currentPath = true;
                        stack.push_back(&(*child));
                        break;
                    }
                }
            }
            if (child == callGraph.end()) {
                 no more callees, we bottomed out, never look at this node again
                stack.back()->currentPath = false;
                stack.back()->visited = true;
                stack.pop_back();
            }
        }   end while, meaning nothing left to process in this subtree
    } while (newRoot);   redundant loop check; should always exit via the 'break' above
}
void TIntermediate :: checkCallGraphCycles ( TInfoSink & infoSink ) { for ( TGraph :: iterator call = callGraph . begin ( ) ; call != callGraph . end ( ) ; ++ call ) { call -> visited = false ; call -> currentPath = false ; call -> errorGiven = false ; } TCall * newRoot ; do { newRoot = 0 ; for ( TGraph :: iterator call = callGraph . begin ( ) ; call != callGraph . end ( ) ; ++ call ) { if ( ! call -> visited ) { newRoot = & ( * call ) ; break ; } } if ( ! newRoot ) break ; std :: list < TCall * > stack ; newRoot -> currentPath = true ; stack . push_back ( newRoot ) ; while ( ! stack . empty ( ) ) { TCall * call = stack . back ( ) ; TGraph :: iterator child = callGraph . begin ( ) ; for ( ; child != callGraph . end ( ) ; ++ child ) { if ( child -> visited ) continue ; if ( call -> callee == child -> caller ) { if ( child -> currentPath ) { if ( ! child -> errorGiven ) { error ( infoSink , " " ) ; infoSink . info << " " << call -> callee << " " << child -> callee << " \n " ; child -> errorGiven = true ; recursive = true ; } } else { child -> currentPath = true ; stack . push_back ( & ( * child ) ) ; break ; } } } if ( child == callGraph . end ( ) ) { stack . back ( ) -> currentPath = false ; stack . back ( ) -> visited = true ; stack . pop_back ( ) ; } } } while ( newRoot ) ; }
See if the call graph contains any static recursion, which is disallowed
by the specification.
See if the call graph contains any static recursion which is disallowed by the specification .
// Clear fields we'll use for this. // // Loop, looking for a new connected subgraph.  One subgraph is handled per loop iteration. // // See if we have unvisited parts of the graph. // If not, we are done. // Otherwise, we found a new subgraph, process it: // See what all can be reached by this new root, and if any of // that is recursive.  This is done by depth-first traversals, seeing // if a new call is found that was already in the currentPath (a back edge), // thereby detecting recursion. // currentPath will be true iff it is on the stack // get a caller // Add to the stack just one callee. // This algorithm always terminates, because only !visited and !currentPath causes a push // and all pushes change currentPath to true, and all pops change visited to true. // If we already visited this node, its whole subgraph has already been processed, so skip it. // Then, we found a back edge // no more callees, we bottomed out, never look at this node again // end while, meaning nothing left to process in this subtree // redundant loop check; should always exit via the 'break' above