//===- llvm/ADT/GraphTraits.h - Graph traits template -----------*- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// /// \file /// This file defines the little GraphTraits<X> template class that should be /// specialized by classes that want to be iteratable by generic graph /// iterators. /// /// This file also defines the marker class Inverse that is used to iterate over /// graphs in a graph defined, inverse ordering... /// //===----------------------------------------------------------------------===// #ifndef LLVM_ADT_GRAPHTRAITS_H #define LLVM_ADT_GRAPHTRAITS_H #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/iterator_range.h" namespace llvm { // GraphTraits - This class should be specialized by different graph types... // which is why the default version is empty. // // This template evolved from supporting `BasicBlock` to also later supporting // more complex types (e.g. CFG and DomTree). // // GraphTraits can be used to create a view over a graph interpreting it // differently without requiring a copy of the original graph. This could // be achieved by carrying more data in NodeRef. See LoopBodyTraits for one // example. template<class GraphType> struct GraphTraits { … }; namespace detail { has_number_t; } // namespace detail /// Indicate whether a GraphTraits<NodeT>::getNumber() is supported. GraphHasNodeNumbers; // Inverse - This class is used as a little marker class to tell the graph // iterator to iterate over the graph in a graph defined "Inverse" ordering. // Not all graphs define an inverse ordering, and if they do, it depends on // the graph exactly what that is. Here's an example of usage with the // df_iterator: // // idf_iterator<Method*> I = idf_begin(M), E = idf_end(M); // for (; I != E; ++I) { ... } // // Which is equivalent to: // df_iterator<Inverse<Method*>> I = idf_begin(M), E = idf_end(M); // for (; I != E; ++I) { ... } // template <class GraphType> struct Inverse { … }; // Provide a partial specialization of GraphTraits so that the inverse of an // inverse falls back to the original graph. GraphTraits<Inverse<Inverse<T>>>; // Provide iterator ranges for the graph traits nodes and children template <class GraphType> iterator_range<typename GraphTraits<GraphType>::nodes_iterator> nodes(const GraphType &G) { … } template <class GraphType> iterator_range<typename GraphTraits<Inverse<GraphType>>::nodes_iterator> inverse_nodes(const GraphType &G) { … } template <class GraphType> iterator_range<typename GraphTraits<GraphType>::ChildIteratorType> children(const typename GraphTraits<GraphType>::NodeRef &G) { … } template <class GraphType> iterator_range<typename GraphTraits<Inverse<GraphType>>::ChildIteratorType> inverse_children(const typename GraphTraits<GraphType>::NodeRef &G) { … } template <class GraphType> iterator_range<typename GraphTraits<GraphType>::ChildEdgeIteratorType> children_edges(const typename GraphTraits<GraphType>::NodeRef &G) { … } } // end namespace llvm #endif // LLVM_ADT_GRAPHTRAITS_H