[GraphTraits] Make nodes_iterator dereference to NodeType*

[timshen]

Summary

Currently nodes_iterator may dereference to a NodeType* or a NodeType&. Make them all dereference to NodeType*, which is NodeRef later. Corresponding LLVM change: D23704

[dblaikie]

Consider renaming and/or generalizing the handlers.

Also, in a follow-up or preliminary commit, could you remove all the DerefFun stuff. Move the definition of CGdereference (if they remain) above the typedef of nodes_iterator and use decltype(&CGdereference), and you can drop the "DerefFun(...)" around the CGdereference). That way the change only needs to change the deref function and everything else falls out.

(you could also change the calls to map_iterator to just directly call nodes_iterator(...) since you have the specific type, there's no need to call the deduction-powered generic function)

(idle rambling: This is why I really want the ability to decltype stateless lambdas:

typedef mapped_iterator<..., decltype([](PairTy P) { return P.second; })> nodes_iterator

)

include/clang/Analysis/CallGraph.h

219

I don't have enough context - but presumably this name should be changed now that the function doesn't actually dereference? (perhaps this is just get<1, PairTy::first_type, PairTy::second_type> - but could be useful to have a generic utility, something like 'firster' and 'seconder' - I thought there might already be, but couldn't find one. Could generalize it like get<> but just allow the actual tuple/pair type to be passed, rather than having to decompose it)

[timshen]

include/clang/Analysis/CallGraph.h

219

I'll add a GetNthFunctor or something to STLExtras.h in the next patch, so that we don't need to create a specific one.

[timshen]

Landed as r279326.

include/clang/Analysis/Analyses/Dominators.h

template <> struct GraphTraits< ::clang::DomTreeNode* > {
   }
   static inline ChildIteratorType child_begin(NodeType *N) {
     return N->begin();
   }
   static inline ChildIteratorType child_end(NodeType *N) {
     return N->end();
   }
 
-  typedef df_iterator< ::clang::DomTreeNode* > nodes_iterator;
+  typedef llvm::pointer_iterator<df_iterator<::clang::DomTreeNode *>>
+      nodes_iterator;
 
   static nodes_iterator nodes_begin(::clang::DomTreeNode *N) {
-    return df_begin(getEntryNode(N));
+    return nodes_iterator(df_begin(getEntryNode(N)));
   }
 
   static nodes_iterator nodes_end(::clang::DomTreeNode *N) {
-    return df_end(getEntryNode(N));
+    return nodes_iterator(df_end(getEntryNode(N)));
   }
 };
 
 template <> struct GraphTraits< ::clang::DominatorTree* >
   : public GraphTraits< ::clang::DomTreeNode* > {
   static NodeType *getEntryNode(::clang::DominatorTree *DT) {
     return DT->getRootNode();
   }
 
   static nodes_iterator nodes_begin(::clang::DominatorTree *N) {
-    return df_begin(getEntryNode(N));
+    return nodes_iterator(df_begin(getEntryNode(N)));
   }
 
   static nodes_iterator nodes_end(::clang::DominatorTree *N) {
-    return df_end(getEntryNode(N));
+    return nodes_iterator(df_end(getEntryNode(N)));
   }
 };
 } // end namespace llvm
 
 #endif

include/clang/Analysis/CFG.h

public:
     BuildOptions()
       : forcedBlkExprs(nullptr), Observer(nullptr),
         PruneTriviallyFalseEdges(true), AddEHEdges(false),
         AddInitializers(false), AddImplicitDtors(false),
         AddTemporaryDtors(false), AddStaticInitBranches(false),
         AddCXXNewAllocator(false), AddCXXDefaultInitExprInCtors(false) {}
   };
 
-  /// \brief Provides a custom implementation of the iterator class to have the
-  /// same interface as Function::iterator - iterator returns CFGBlock
-  /// (not a pointer to CFGBlock).
-  class graph_iterator {
-  public:
-    typedef CFGBlock                        value_type;
-    typedef value_type&                     reference;
-    typedef value_type*                     pointer;
-    typedef BumpVector<CFGBlock*>::iterator ImplTy;
-
-    graph_iterator(const ImplTy &i) : I(i) {}
-
-    bool operator==(const graph_iterator &X) const { return I == X.I; }
-    bool operator!=(const graph_iterator &X) const { return I != X.I; }
-
-    reference operator*()    const { return **I; }
-    pointer operator->()     const { return  *I; }
-    operator CFGBlock* ()          { return  *I; }
-
-    graph_iterator &operator++() { ++I; return *this; }
-    graph_iterator &operator--() { --I; return *this; }
-
-  private:
-    ImplTy I;
-  };
-
-  class const_graph_iterator {
-  public:
-    typedef const CFGBlock                  value_type;
-    typedef value_type&                     reference;
-    typedef value_type*                     pointer;
-    typedef BumpVector<CFGBlock*>::const_iterator ImplTy;
-
-    const_graph_iterator(const ImplTy &i) : I(i) {}
-
-    bool operator==(const const_graph_iterator &X) const { return I == X.I; }
-    bool operator!=(const const_graph_iterator &X) const { return I != X.I; }
-
-    reference operator*() const { return **I; }
-    pointer operator->()  const { return  *I; }
-    operator CFGBlock* () const { return  *I; }
-
-    const_graph_iterator &operator++() { ++I; return *this; }
-    const_graph_iterator &operator--() { --I; return *this; }
-
-  private:
-    ImplTy I;
-  };
-
   /// buildCFG - Builds a CFG from an AST.
   static std::unique_ptr<CFG> buildCFG(const Decl *D, Stmt *AST, ASTContext *C,
                                        const BuildOptions &BO);
 
   /// createBlock - Create a new block in the CFG.  The CFG owns the block;
   ///  the caller should not directly free it.
   CFGBlock *createBlock();
 
public:
   CFGBlock &                front()                { return *Blocks.front(); }
   CFGBlock &                back()                 { return *Blocks.back(); }
 
   iterator                  begin()                { return Blocks.begin(); }
   iterator                  end()                  { return Blocks.end(); }
   const_iterator            begin()       const    { return Blocks.begin(); }
   const_iterator            end()         const    { return Blocks.end(); }
 
-  graph_iterator nodes_begin() { return graph_iterator(Blocks.begin()); }
-  graph_iterator nodes_end() { return graph_iterator(Blocks.end()); }
-  const_graph_iterator nodes_begin() const {
-    return const_graph_iterator(Blocks.begin());
-  }
-  const_graph_iterator nodes_end() const {
-    return const_graph_iterator(Blocks.end());
-  }
+  iterator nodes_begin() { return iterator(Blocks.begin()); }
+  iterator nodes_end() { return iterator(Blocks.end()); }
+  const_iterator nodes_begin() const { return const_iterator(Blocks.begin()); }
+  const_iterator nodes_end() const { return const_iterator(Blocks.end()); }
 
   reverse_iterator          rbegin()               { return Blocks.rbegin(); }
   reverse_iterator          rend()                 { return Blocks.rend(); }
   const_reverse_iterator    rbegin()      const    { return Blocks.rbegin(); }
   const_reverse_iterator    rend()        const    { return Blocks.rend(); }
 
   CFGBlock &                getEntry()             { return *Entry; }
   const CFGBlock &          getEntry()    const    { return *Entry; }
template <> struct GraphTraits<Inverse<const ::clang::CFGBlock*> > {
   { return N->pred_end(); }
 };
 
 // Traits for: CFG
 
 template <> struct GraphTraits< ::clang::CFG* >
     : public GraphTraits< ::clang::CFGBlock *>  {
 
-  typedef ::clang::CFG::graph_iterator nodes_iterator;
+  typedef ::clang::CFG::iterator nodes_iterator;
 
   static NodeType     *getEntryNode(::clang::CFG* F) { return &F->getEntry(); }
   static nodes_iterator nodes_begin(::clang::CFG* F) { return F->nodes_begin();}
   static nodes_iterator   nodes_end(::clang::CFG* F) { return F->nodes_end(); }
   static unsigned              size(::clang::CFG* F) { return F->size(); }
 };
 
 template <> struct GraphTraits<const ::clang::CFG* >
     : public GraphTraits<const ::clang::CFGBlock *>  {
 
-  typedef ::clang::CFG::const_graph_iterator nodes_iterator;
+  typedef ::clang::CFG::const_iterator nodes_iterator;
 
   static NodeType *getEntryNode( const ::clang::CFG* F) {
     return &F->getEntry();
   }
   static nodes_iterator nodes_begin( const ::clang::CFG* F) {
     return F->nodes_begin();
   }
   static nodes_iterator nodes_end( const ::clang::CFG* F) {
     return F->nodes_end();
   }
   static unsigned size(const ::clang::CFG* F) {
     return F->size();
   }
 };
 
 template <> struct GraphTraits<Inverse< ::clang::CFG*> >
   : public GraphTraits<Inverse< ::clang::CFGBlock*> > {
 
-  typedef ::clang::CFG::graph_iterator nodes_iterator;
+  typedef ::clang::CFG::iterator nodes_iterator;
 
   static NodeType *getEntryNode( ::clang::CFG* F) { return &F->getExit(); }
   static nodes_iterator nodes_begin( ::clang::CFG* F) {return F->nodes_begin();}
   static nodes_iterator nodes_end( ::clang::CFG* F) { return F->nodes_end(); }
 };
 
 template <> struct GraphTraits<Inverse<const ::clang::CFG*> >
   : public GraphTraits<Inverse<const ::clang::CFGBlock*> > {
 
-  typedef ::clang::CFG::const_graph_iterator nodes_iterator;
+  typedef ::clang::CFG::const_iterator nodes_iterator;
 
   static NodeType *getEntryNode(const ::clang::CFG* F) { return &F->getExit(); }
   static nodes_iterator nodes_begin(const ::clang::CFG* F) {
     return F->nodes_begin();
   }
   static nodes_iterator nodes_end(const ::clang::CFG* F) {
     return F->nodes_end();
   }
 };
 } // end llvm namespace
 
 #endif // LLVM_CLANG_ANALYSIS_CFG_H

include/clang/Analysis/CallGraph.h

 
 template <> struct GraphTraits<clang::CallGraph*>
   : public GraphTraits<clang::CallGraphNode*> {
 
   static NodeType *getEntryNode(clang::CallGraph *CGN) {
     return CGN->getRoot();  // Start at the external node!
   }
   typedef std::pair<const clang::Decl*, clang::CallGraphNode*> PairTy;
-  typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode&> DerefFun;
+  typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode *>
+      DerefFun;
   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
   typedef mapped_iterator<clang::CallGraph::iterator, DerefFun> nodes_iterator;
 
   static nodes_iterator nodes_begin(clang::CallGraph *CG) {
     return map_iterator(CG->begin(), DerefFun(CGdereference));
   }
   static nodes_iterator nodes_end  (clang::CallGraph *CG) {
     return map_iterator(CG->end(), DerefFun(CGdereference));
   }
-  static clang::CallGraphNode &CGdereference(PairTy P) {
-    return *(P.second);
-  }
+  static clang::CallGraphNode *CGdereference(PairTy P) { return P.second; }
 
   static unsigned size(clang::CallGraph *CG) {
     return CG->size();
   }
 };
 
 template <> struct GraphTraits<const clang::CallGraph*> :
   public GraphTraits<const clang::CallGraphNode*> {
   static NodeType *getEntryNode(const clang::CallGraph *CGN) {
     return CGN->getRoot();
   }
   typedef std::pair<const clang::Decl*, clang::CallGraphNode*> PairTy;
-  typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode&> DerefFun;
+  typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode *>
+      DerefFun;
   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
   typedef mapped_iterator<clang::CallGraph::const_iterator,
                           DerefFun> nodes_iterator;
 
   static nodes_iterator nodes_begin(const clang::CallGraph *CG) {
     return map_iterator(CG->begin(), DerefFun(CGdereference));
   }
   static nodes_iterator nodes_end(const clang::CallGraph *CG) {
     return map_iterator(CG->end(), DerefFun(CGdereference));
   }
-  static clang::CallGraphNode &CGdereference(PairTy P) {
-    return *(P.second);
-  }
+  static clang::CallGraphNode *CGdereference(PairTy P) { return P.second; }
 
   static unsigned size(const clang::CallGraph *CG) {
     return CG->size();
   }
 };
 
 } // end llvm namespace
 
 #endif