[ADT] Generalize GraphTraits NodeType* to NodePtr

Hi llvm-dev,

Recently I try to specialize GraphTraits on my own graph. I found it hard to use, since it requires a hardcoded “NodeType *” in required function signatures. For example, for a graph like:

struct Graph {
struct Node {
MachineInstr *data;
unsigned EdgeBeginIndex, EdgeEndIndex;
struct Edge {
unsigned LeftNodeIndex, RightNodeIndex;
std::vector Nodes;
std::vector SortedEdges;

It can’t be easily represented via a GraphTraits specialization, Since it’s hard to let “NodeType *” carry necessary information - Nodes and SortedEdges - about its children. I can certainly add a SortedEdges vector pointer for each Node, but that seems unnecessary.

I propose to change the requirement from “NodeType*” to a typedef “NodePtr”, so that users can customize their own “smarter” pointers. In the case above a NodePtr could be:

struct NodePtr {
Graph* G;
unsigned Index;
MachineInstr &operator() {
return G->Nodes[Index];
// …

child_begin and child_end in GraphTraits will take NodePtr by value, and return ChildIteratorType. Dereferencing a ChildIteratorType returns a NodePtr by value. Dereferencing a nodes_iterator also returns a NodePtr by value.

Do you think this is a feasible change? If so, what is the preferred way to make this change/migration?