[CFG] Introduce CFGElementRef, a wrapper that knows it's position in a CFGBlock

[Szelethus]

Summary

Previously, collecting CFGElements in a set was practially impossible, because both CFGBlock::operator[] and both the iterators returned it by value. One workaround would be to collect the iterators instead, but they don't really capture the concept of an element, and elements from different iterator types are incomparable.

This patch introduces CFGElementRef, a wrapper around a (CFGBlock, Index) pair, and a variety of new iterators and iterator ranges to solve this problem.

I guess you could say that this patch took a couple iterations to get right :^)

[NoQ]

Oof.

Someone had to do it.

clang/include/clang/Analysis/CFG.h

617

Yeah, kinda shocking that you needed to go that far >.<

I suggest CFGElementRefBase or CFGElementRefImpl or something like that, because otherwise it looks to me as if it's some sort of a generic reference to an element of arbitrary collection.

648–650

For lexicographic comparisons i personally enjoy std::make_pair(Parent, Index) < std::make_pair(Other.Parent, Other.Index).

clang/include/clang/Analysis/CFG.h

CFGElement operator[](size_t i) const  {
       assert(i < Impl.size());
       return Impl[Impl.size() - 1 - i];
     }
 
     size_t size() const { return Impl.size(); }
     bool empty() const { return Impl.empty(); }
   };
 
+  /// A convenience class for comparing CFGElements, since methods of CFGBlock
+  /// like operator[] return CFGElements by value. This is practically a wrapper
+  /// around a (CFGBlock, Index) pair.
+  template <bool IsConst>
+  class ElementRef {
+
+    template <bool IsOtherConst> friend class ElementRef;
+
+    using CFGBlockPtr =
+        typename std::conditional<IsConst, const CFGBlock *, CFGBlock *>::type;
+
+    using CFGElementPtr =
+        typename std::conditional<
+            IsConst, const CFGElement *, CFGElement *>::type;
+
+  protected:
+    CFGBlockPtr Parent;
+    size_t Index;
+
+  public:
+    ElementRef(CFGBlockPtr Parent, size_t Index)
+      : Parent(Parent), Index(Index) {}
+
+    template <bool IsOtherConst>
+    ElementRef(ElementRef<IsOtherConst> Other)
+      : ElementRef(Other.Parent, Other.Index) {}
+
+    size_t getIndexInBlock() const {
+      return Index;
+    }
+
+    CFGBlockPtr getParent() { return Parent; }
+    CFGBlockPtr getParent() const { return Parent; }
+
+    bool operator<(ElementRef Other) const {
+      if (Parent == Other.Parent)
+        return Index < Other.Index;
+      return Parent < Other.Parent;
+    }
+
+    bool operator==(ElementRef Other) const {
+      return Parent == Other.Parent && Index == Other.Index;
+    }
+
+    bool operator!=(ElementRef Other) const { return !(*this == Other); }
+    CFGElement operator*() { return (*Parent)[Index]; }
+    CFGElementPtr operator->() { return &*(Parent->begin() + Index); }
+  };
+
+public:
+  template <bool IsReverse, bool IsConst>
+  class ElementRefIterator {
+
+    template <bool IsOtherReverse, bool IsOtherConst>
+    friend class ElementRefIterator;
+
+    using CFGBlockRef =
+        typename std::conditional<IsConst, const CFGBlock *, CFGBlock *>::type;
+
+    using UnderlayingIteratorTy =
+        typename std::conditional<
+            IsConst,
+            typename std::conditional<
+                IsReverse,
+                ElementList::const_reverse_iterator,
+                ElementList::const_iterator>::type,
+            typename std::conditional<
+                IsReverse,
+                ElementList::reverse_iterator,
+                ElementList::iterator>::type>::type;
+
+    using IteratorTraits = typename std::iterator_traits<UnderlayingIteratorTy>;
+    using ElementRef = typename CFGBlock::ElementRef<IsConst>;
+
+  public:
+    using difference_type = typename IteratorTraits::difference_type;
+    using value_type = ElementRef;
+    using pointer = ElementRef *;
+    using iterator_category = typename IteratorTraits::iterator_category;
+
+  private:
+    CFGBlockRef Parent;
+    UnderlayingIteratorTy Pos;
+
+  public:
+    ElementRefIterator(CFGBlockRef Parent, UnderlayingIteratorTy Pos)
+      : Parent(Parent), Pos(Pos) {}
+
+    template <bool IsOtherConst>
+    ElementRefIterator(ElementRefIterator<false, IsOtherConst> E)
+      : ElementRefIterator(E.Parent, E.Pos.base()) {}
+
+    template <bool IsOtherConst>
+    ElementRefIterator(ElementRefIterator<true, IsOtherConst> E)
+      : ElementRefIterator(E.Parent, llvm::make_reverse_iterator(E.Pos)) {}
+
+    bool operator<(ElementRefIterator Other) const {
+      assert(Parent == Other.Parent);
+      return Pos < Other.Pos;
+    }
+
+    bool operator==(ElementRefIterator Other) const {
+      return Parent == Other.Parent && Pos == Other.Pos;
+    }
+
+    bool operator!=(ElementRefIterator Other) const {
+      return !(*this == Other);
+    }
+
+  private:
+    template <bool IsOtherConst>
+    static size_t getIndexInBlock(
+        CFGBlock::ElementRefIterator<true, IsOtherConst> E) {
+        return E.Parent->size() - (E.Pos - E.Parent->rbegin()) - 1;
+    }
+
+    template <bool IsOtherConst>
+    static size_t getIndexInBlock(
+        CFGBlock::ElementRefIterator<false, IsOtherConst> E) {
+        return E.Pos - E.Parent->begin();
+    }
+
+  public:
+    value_type operator*() { return {Parent, getIndexInBlock(*this)}; }
+
+    difference_type operator-(ElementRefIterator Other) const {
+      return Pos - Other.Pos;
+    }
+
+    ElementRefIterator operator++() {
+      ++this->Pos;
+      return *this;
+    }
+    ElementRefIterator operator++(int) {
+      ElementRefIterator Ret = *this;
+      ++*this;
+      return Ret;
+    }
+    ElementRefIterator operator+(size_t count) {
+      this->Pos += count;
+      return *this;
+    }
+    ElementRefIterator operator-(size_t count) {
+      this->Pos -= count;
+      return *this;
+    }
+  };
+
+public:
   /// The set of statements in the basic block.
   ElementList Elements;
 
   /// An (optional) label that prefixes the executable statements in the block.
   /// When this variable is non-NULL, it is either an instance of LabelStmt,
   /// SwitchCase or CXXCatchStmt.
   Stmt *Label = nullptr;
 
explicit CFGBlock(unsigned blockid, BumpVectorContext &C, CFG *parent)
         Succs(C, 1), HasNoReturnElement(false), Parent(parent) {}
 
   // Statement iterators
   using iterator = ElementList::iterator;
   using const_iterator = ElementList::const_iterator;
   using reverse_iterator = ElementList::reverse_iterator;
   using const_reverse_iterator = ElementList::const_reverse_iterator;
 
+  size_t getIndexInCFG() const;
+
   CFGElement                 front()       const { return Elements.front();   }
   CFGElement                 back()        const { return Elements.back();    }
 
   iterator                   begin()             { return Elements.begin();   }
   iterator                   end()               { return Elements.end();     }
   const_iterator             begin()       const { return Elements.begin();   }
   const_iterator             end()         const { return Elements.end();     }
 
   reverse_iterator           rbegin()            { return Elements.rbegin();  }
   reverse_iterator           rend()              { return Elements.rend();    }
   const_reverse_iterator     rbegin()      const { return Elements.rbegin();  }
   const_reverse_iterator     rend()        const { return Elements.rend();    }
 
+  using CFGElementRef = ElementRef<false>;
+  using ConstCFGElementRef = ElementRef<true>;
+
+  using ref_iterator = ElementRefIterator<false, false>;
+  using ref_iterator_range = llvm::iterator_range<ref_iterator>;
+  using const_ref_iterator = ElementRefIterator<false, true>;
+  using const_ref_iterator_range = llvm::iterator_range<const_ref_iterator>;
+
+  using reverse_ref_iterator = ElementRefIterator<true, false>;
+  using reverse_ref_iterator_range = llvm::iterator_range<reverse_ref_iterator>;
+
+  using const_reverse_ref_iterator = ElementRefIterator<true, true>;
+  using const_reverse_ref_iterator_range =
+      llvm::iterator_range<const_reverse_ref_iterator>;
+
+  ref_iterator ref_begin() { return {this, begin()}; }
+  ref_iterator ref_end() { return {this, end()}; }
+  const_ref_iterator ref_begin() const { return {this, begin()}; }
+  const_ref_iterator ref_end() const { return {this, end()}; }
+
+  reverse_ref_iterator rref_begin() { return {this, rbegin()}; }
+  reverse_ref_iterator rref_end() { return {this, rend()}; }
+  const_reverse_ref_iterator rref_begin() const { return {this, rbegin()}; }
+  const_reverse_ref_iterator rref_end() const { return {this, rend()}; }
+
+  ref_iterator_range refs() { return {ref_begin(), ref_end()}; }
+  const_ref_iterator_range refs() const { return {ref_begin(), ref_end()}; }
+  reverse_ref_iterator_range rrefs() { return {rref_begin(), rref_end()}; }
+  const_reverse_ref_iterator_range rrefs() const {
+    return {rref_begin(), rref_end()};
+  }
+
   unsigned                   size()        const { return Elements.size();    }
   bool                       empty()       const { return Elements.empty();   }
 
   CFGElement operator[](size_t i) const  { return Elements[i]; }
 
   // CFG iterators
   using pred_iterator = AdjacentBlocks::iterator;
   using const_pred_iterator = AdjacentBlocks::const_iterator;
public:
 
   void dump(const CFG *cfg, const LangOptions &LO, bool ShowColors = false) const;
   void print(raw_ostream &OS, const CFG* cfg, const LangOptions &LO,
              bool ShowColors) const;
 
   void printTerminator(raw_ostream &OS, const LangOptions &LO) const;
   void printTerminatorJson(raw_ostream &Out, const LangOptions &LO,
                            bool AddQuotes) const;
-  
   void printAsOperand(raw_ostream &OS, bool /*PrintType*/) {
     OS << "BB#" << getBlockID();
   }
 
   /// Adds a (potentially unreachable) successor block to the current block.
   void addSuccessor(AdjacentBlock Succ, BumpVectorContext &C);
 
   void appendStmt(Stmt *statement, BumpVectorContext &C) {
public:
   iterator beginScopeEndInsert(iterator I, size_t Cnt, BumpVectorContext &C) {
     return iterator(
         Elements.insert(I.base(), Cnt, CFGScopeEnd(nullptr, nullptr), C));
   }
   iterator insertScopeEnd(iterator I, VarDecl *VD, Stmt *S) {
     *I = CFGScopeEnd(VD, S);
     return ++I;
   }
-
 };
 
 /// CFGCallback defines methods that should be called when a logical
 /// operator error is found when building the CFG.
 class CFGCallback {
 public:
   CFGCallback() = default;
   virtual ~CFGCallback() = default;

clang/lib/Analysis/CFG.cpp

void CFG::print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const {
   }
 
   // Print the exit block.
   print_block(OS, this, getExit(), Helper, true, ShowColors);
   OS << '\n';
   OS.flush();
 }
 
+size_t CFGBlock::getIndexInCFG() const {
+  return llvm::find(*getParent(), this) - getParent()->begin();
+}
+
 /// dump - A simply pretty printer of a CFGBlock that outputs to stderr.
 void CFGBlock::dump(const CFG* cfg, const LangOptions &LO,
                     bool ShowColors) const {
   print(llvm::errs(), cfg, LO, ShowColors);
 }
 
 LLVM_DUMP_METHOD void CFGBlock::dump() const {
   dump(getParent(), LangOptions(), false);

clang/unittests/Analysis/CFGTest.cpp

TEST(CFG, IsLinear) {
   expectLinear(true,  "void foo() { if constexpr (false); }");
   expectLinear(false, "void foo(bool coin) { if (coin) return; }");
   expectLinear(false, "void foo() { for(;;); }");
   expectLinear(false, "void foo() { do {} while (true); }");
   expectLinear(true,  "void foo() { do {} while (false); }");
   expectLinear(true,  "void foo() { foo(); }"); // Recursion is not our problem.
 }
 
+TEST(CFG, ElementRefIterator) {
+  const char *Code = R"(void f() {
+                          int i;
+                          int j;
+                          i = 5;
+                          i = 6;
+                          j = 7;
+                        })";
+
+  BuildResult B = BuildCFG(Code);
+  EXPECT_EQ(BuildResult::BuiltCFG, B.getStatus());
+  CFG *Cfg = B.getCFG();
+
+  // [B2 (ENTRY)]
+  //   Succs (1): B1
+
+  // [B1]
+  //   1: int i;
+  //   2: int j;
+  //   3: i = 5
+  //   4: i = 6
+  //   5: j = 7
+  //   Preds (1): B2
+  //   Succs (1): B0
+
+  // [B0 (EXIT)]
+  //   Preds (1): B1
+  CFGBlock *MainBlock = *(Cfg->begin() + 1);
+
+  constexpr CFGBlock::ref_iterator::difference_type MainBlockSize = 4;
+
+  // The rest of this test looks totally insane, but there iterators are
+  // templates under the hood, to it's important to instantiate everything for
+  // proper converage.
+
+  // Non-reverse, non-const version
+  long Index = 0;
+  for (CFGBlock::CFGElementRef ElementRef : MainBlock->refs()) {
+    EXPECT_EQ(ElementRef.getParent(), MainBlock);
+    EXPECT_EQ(ElementRef.getIndexInBlock(), Index);
+    EXPECT_TRUE(ElementRef->getAs<CFGStmt>());
+    EXPECT_TRUE((*ElementRef).getAs<CFGStmt>());
+    EXPECT_EQ(ElementRef.getParent(), MainBlock);
+    ++Index;
+  }
+  EXPECT_TRUE(*MainBlock->ref_begin() < *(MainBlock->ref_begin() + 1));
+  EXPECT_TRUE(*MainBlock->ref_begin() == *MainBlock->ref_begin());
+  EXPECT_FALSE(*MainBlock->ref_begin() != *MainBlock->ref_begin());
+
+  EXPECT_TRUE(MainBlock->ref_begin() < MainBlock->ref_begin() + 1);
+  EXPECT_TRUE(MainBlock->ref_begin() == MainBlock->ref_begin());
+  EXPECT_FALSE(MainBlock->ref_begin() != MainBlock->ref_begin());
+  EXPECT_EQ(MainBlock->ref_end() - MainBlock->ref_begin(), MainBlockSize + 1);
+  EXPECT_EQ(MainBlock->ref_end() - MainBlockSize - 1, MainBlock->ref_begin());
+  EXPECT_EQ(MainBlock->ref_begin() + MainBlockSize + 1, MainBlock->ref_end());
+  EXPECT_EQ(MainBlock->ref_begin()++, MainBlock->ref_begin());
+  EXPECT_EQ(++(MainBlock->ref_begin()), MainBlock->ref_begin() + 1);
+
+  // Non-reverse, non-const version
+  const CFGBlock *CMainBlock = MainBlock;
+  Index = 0;
+  for (CFGBlock::ConstCFGElementRef ElementRef : CMainBlock->refs()) {
+    EXPECT_EQ(ElementRef.getParent(), CMainBlock);
+    EXPECT_EQ(ElementRef.getIndexInBlock(), Index);
+    EXPECT_TRUE(ElementRef->getAs<CFGStmt>());
+    EXPECT_TRUE((*ElementRef).getAs<CFGStmt>());
+    EXPECT_EQ(ElementRef.getParent(), MainBlock);
+    ++Index;
+  }
+  EXPECT_TRUE(*CMainBlock->ref_begin() < *(CMainBlock->ref_begin() + 1));
+  EXPECT_TRUE(*CMainBlock->ref_begin() == *CMainBlock->ref_begin());
+  EXPECT_FALSE(*CMainBlock->ref_begin() != *CMainBlock->ref_begin());
+
+  EXPECT_TRUE(CMainBlock->ref_begin() < CMainBlock->ref_begin() + 1);
+  EXPECT_TRUE(CMainBlock->ref_begin() == CMainBlock->ref_begin());
+  EXPECT_FALSE(CMainBlock->ref_begin() != CMainBlock->ref_begin());
+  EXPECT_EQ(CMainBlock->ref_end() - CMainBlock->ref_begin(), MainBlockSize + 1);
+  EXPECT_EQ(CMainBlock->ref_end() - MainBlockSize - 1, CMainBlock->ref_begin());
+  EXPECT_EQ(CMainBlock->ref_begin() + MainBlockSize + 1, CMainBlock->ref_end());
+  EXPECT_EQ(CMainBlock->ref_begin()++, CMainBlock->ref_begin());
+  EXPECT_EQ(++(CMainBlock->ref_begin()), CMainBlock->ref_begin() + 1);
+
+  // Reverse, non-const version
+  Index = MainBlockSize;
+  for (CFGBlock::CFGElementRef ElementRef : MainBlock->rrefs()) {
+    llvm::errs() << Index << '\n';
+    EXPECT_EQ(ElementRef.getParent(), MainBlock);
+    EXPECT_EQ(ElementRef.getIndexInBlock(), Index);
+    EXPECT_TRUE(ElementRef->getAs<CFGStmt>());
+    EXPECT_TRUE((*ElementRef).getAs<CFGStmt>());
+    EXPECT_EQ(ElementRef.getParent(), MainBlock);
+    --Index;
+  }
+  EXPECT_FALSE(*MainBlock->rref_begin() < *(MainBlock->rref_begin() + 1));
+  EXPECT_TRUE(*MainBlock->rref_begin() == *MainBlock->rref_begin());
+  EXPECT_FALSE(*MainBlock->rref_begin() != *MainBlock->rref_begin());
+
+  EXPECT_TRUE(MainBlock->rref_begin() < MainBlock->rref_begin() + 1);
+  EXPECT_TRUE(MainBlock->rref_begin() == MainBlock->rref_begin());
+  EXPECT_FALSE(MainBlock->rref_begin() != MainBlock->rref_begin());
+  EXPECT_EQ(MainBlock->rref_end() - MainBlock->rref_begin(), MainBlockSize + 1);
+  EXPECT_EQ(MainBlock->rref_end() - MainBlockSize - 1, MainBlock->rref_begin());
+  EXPECT_EQ(MainBlock->rref_begin() + MainBlockSize + 1, MainBlock->rref_end());
+  EXPECT_EQ(MainBlock->rref_begin()++, MainBlock->rref_begin());
+  EXPECT_EQ(++(MainBlock->rref_begin()), MainBlock->rref_begin() + 1);
+
+  // Reverse, const version
+  Index = MainBlockSize;
+  for (CFGBlock::ConstCFGElementRef ElementRef : CMainBlock->rrefs()) {
+    EXPECT_EQ(ElementRef.getParent(), CMainBlock);
+    EXPECT_EQ(ElementRef.getIndexInBlock(), Index);
+    EXPECT_TRUE(ElementRef->getAs<CFGStmt>());
+    EXPECT_TRUE((*ElementRef).getAs<CFGStmt>());
+    EXPECT_EQ(ElementRef.getParent(), MainBlock);
+    --Index;
+  }
+  EXPECT_FALSE(*CMainBlock->rref_begin() < *(CMainBlock->rref_begin() + 1));
+  EXPECT_TRUE(*CMainBlock->rref_begin() == *CMainBlock->rref_begin());
+  EXPECT_FALSE(*CMainBlock->rref_begin() != *CMainBlock->rref_begin());
+
+  EXPECT_TRUE(CMainBlock->rref_begin() < CMainBlock->rref_begin() + 1);
+  EXPECT_TRUE(CMainBlock->rref_begin() == CMainBlock->rref_begin());
+  EXPECT_FALSE(CMainBlock->rref_begin() != CMainBlock->rref_begin());
+  EXPECT_EQ(CMainBlock->rref_end() - CMainBlock->rref_begin(),
+            MainBlockSize + 1);
+  EXPECT_EQ(CMainBlock->rref_end() - MainBlockSize - 1,
+            CMainBlock->rref_begin());
+  EXPECT_EQ(CMainBlock->rref_begin() + MainBlockSize + 1,
+            CMainBlock->rref_end());
+  EXPECT_EQ(CMainBlock->rref_begin()++, CMainBlock->rref_begin());
+  EXPECT_EQ(++(CMainBlock->rref_begin()), CMainBlock->rref_begin() + 1);
+}
+
 } // namespace
 } // namespace analysis
 } // namespace clang