reference, declarationdefinition
definition → references, declarations, derived classes, virtual overrides
reference to multiple definitions → definitions
unreferenced
    1
    2
    3
    4
    5
    6
    7
    8
    9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24
   25
   26
   27
   28
   29
   30
   31
   32
   33
   34
   35
   36
   37
   38
   39
   40
   41
   42
   43
   44
   45
   46
   47
   48
   49
   50
   51
   52
   53
   54
   55
   56
   57
   58
   59
   60
   61
   62
   63
   64
   65
   66
   67
   68
   69
   70
   71
   72
   73
   74
   75
   76
   77
   78
   79
   80
   81
   82
   83
   84
   85
   86
   87
   88
   89
   90
   91
   92
   93
   94
   95
   96
   97
   98
   99
  100
  101
  102
  103
  104
  105
  106
  107
  108
  109
  110
  111
  112
  113
  114
  115
  116
  117
  118
  119
  120
  121
  122
  123
  124
  125
  126
  127
  128
  129
  130
  131
  132
  133
  134
  135
  136
  137
  138
  139
  140
  141
  142
  143
//===- llvm/ADT/GraphTraits.h - Graph traits template -----------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// 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/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 {
  // Elements to provide:

  // typedef NodeRef           - Type of Node token in the graph, which should
  //                             be cheap to copy.
  // typedef ChildIteratorType - Type used to iterate over children in graph,
  //                             dereference to a NodeRef.

  // static NodeRef getEntryNode(const GraphType &)
  //    Return the entry node of the graph

  // static ChildIteratorType child_begin(NodeRef)
  // static ChildIteratorType child_end  (NodeRef)
  //    Return iterators that point to the beginning and ending of the child
  //    node list for the specified node.

  // typedef  ...iterator nodes_iterator; - dereference to a NodeRef
  // static nodes_iterator nodes_begin(GraphType *G)
  // static nodes_iterator nodes_end  (GraphType *G)
  //    nodes_iterator/begin/end - Allow iteration over all nodes in the graph

  // typedef EdgeRef           - Type of Edge token in the graph, which should
  //                             be cheap to copy.
  // typedef ChildEdgeIteratorType - Type used to iterate over children edges in
  //                             graph, dereference to a EdgeRef.

  // static ChildEdgeIteratorType child_edge_begin(NodeRef)
  // static ChildEdgeIteratorType child_edge_end(NodeRef)
  //     Return iterators that point to the beginning and ending of the
  //     edge list for the given callgraph node.
  //
  // static NodeRef edge_dest(EdgeRef)
  //     Return the destination node of an edge.

  // static unsigned       size       (GraphType *G)
  //    Return total number of nodes in the graph

  // If anyone tries to use this class without having an appropriate
  // specialization, make an error.  If you get this error, it's because you
  // need to include the appropriate specialization of GraphTraits<> for your
  // graph, or you need to define it for a new graph type. Either that or
  // your argument to XXX_begin(...) is unknown or needs to have the proper .h
  // file #include'd.
  using NodeRef = typename GraphType::UnknownGraphTypeError;
};

// 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 {
  const GraphType &Graph;

  inline Inverse(const GraphType &G) : Graph(G) {}
};

// Provide a partial specialization of GraphTraits so that the inverse of an
// inverse falls back to the original graph.
template <class T> struct GraphTraits<Inverse<Inverse<T>>> : GraphTraits<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) {
  return make_range(GraphTraits<GraphType>::nodes_begin(G),
                    GraphTraits<GraphType>::nodes_end(G));
}
template <class GraphType>
iterator_range<typename GraphTraits<Inverse<GraphType>>::nodes_iterator>
inverse_nodes(const GraphType &G) {
  return make_range(GraphTraits<Inverse<GraphType>>::nodes_begin(G),
                    GraphTraits<Inverse<GraphType>>::nodes_end(G));
}

template <class GraphType>
iterator_range<typename GraphTraits<GraphType>::ChildIteratorType>
children(const typename GraphTraits<GraphType>::NodeRef &G) {
  return make_range(GraphTraits<GraphType>::child_begin(G),
                    GraphTraits<GraphType>::child_end(G));
}

template <class GraphType>
iterator_range<typename GraphTraits<Inverse<GraphType>>::ChildIteratorType>
inverse_children(const typename GraphTraits<GraphType>::NodeRef &G) {
  return make_range(GraphTraits<Inverse<GraphType>>::child_begin(G),
                    GraphTraits<Inverse<GraphType>>::child_end(G));
}

template <class GraphType>
iterator_range<typename GraphTraits<GraphType>::ChildEdgeIteratorType>
children_edges(const typename GraphTraits<GraphType>::NodeRef &G) {
  return make_range(GraphTraits<GraphType>::child_edge_begin(G),
                    GraphTraits<GraphType>::child_edge_end(G));
}

} // end namespace llvm

#endif // LLVM_ADT_GRAPHTRAITS_H