IntegersSubsetMapping: implemented "diff" operation. Operation allows at the same time perform up to three operations:

- LHS exclude RHS
- LHS intersect RHS (LHS successors will keeped)
- RHS exclude LHS
The complexity is N+M, where
  N is size of LHS
  M is size of RHS.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159201 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 401 insertions, 3 deletions

diff --git a/include/llvm/Support/IntegersSubsetMapping.h b/include/llvm/Support/IntegersSubsetMapping.h
index 4a771331ba..87d0755c51 100644
--- a/include/llvm/Support/IntegersSubsetMapping.h
+++ b/include/llvm/Support/IntegersSubsetMapping.h
@@ -31,6 +31,10 @@ template <class SuccessorClass,
           class IntegersSubsetTy = IntegersSubset,
           class IntTy = IntItem>
 class IntegersSubsetMapping {
+  // FIXME: To much similar iterators typedefs, similar names. 
+  //        - Rename RangeIterator to the cluster iterator.
+  //        - Remove unused "add" methods.
+  //        - Class contents needs cleaning.
 public:
   
   typedef IntRange<IntTy> RangeTy;
@@ -47,15 +51,17 @@ public:
 
   typedef std::pair<RangeEx, SuccessorClass*> Cluster;
 
+  typedef std::list<RangeTy> RangesCollection;
+  typedef typename RangesCollection::iterator RangesCollectionIt;
+  typedef typename RangesCollection::const_iterator RangesCollectionConstIt;
+  typedef IntegersSubsetMapping<SuccessorClass, IntegersSubsetTy, IntTy> self;
+  
 protected:
 
   typedef std::list<Cluster> CaseItems;
   typedef typename CaseItems::iterator CaseItemIt;
   typedef typename CaseItems::const_iterator CaseItemConstIt;
   
-  typedef std::list<RangeTy> RangesCollection;
-  typedef typename RangesCollection::iterator RangesCollectionIt;
-  
   // TODO: Change unclean CRS prefixes to SubsetMap for example.
   typedef std::map<SuccessorClass*, RangesCollection > CRSMap;
   typedef typename CRSMap::iterator CRSMapIt;
@@ -96,6 +102,149 @@ protected:
       Sorted = true;
     }
   }
+  
+  enum DiffProcessState {
+    L_OPENED,
+    INTERSECT_OPENED,
+    R_OPENED,
+    ALL_IS_CLOSED
+  };
+  
+  class DiffStateMachine {
+    
+    DiffProcessState State;
+    IntTy OpenPt;
+    SuccessorClass *CurrentLSuccessor;
+    SuccessorClass *CurrentRSuccessor;
+    
+    self *LeftMapping;
+    self *IntersectionMapping;
+    self *RightMapping;
+
+  public:
+    
+    typedef
+      IntegersSubsetMapping<SuccessorClass, IntegersSubsetTy, IntTy> MappingTy;
+    
+    DiffStateMachine(MappingTy *L,
+                                 MappingTy *Intersection,
+                                 MappingTy *R) :
+                                 State(ALL_IS_CLOSED),
+                                 LeftMapping(L),
+                                 IntersectionMapping(Intersection),
+                                 RightMapping(R)
+                                 {}
+    
+    void onLOpen(const IntTy &Pt, SuccessorClass *S) {
+      switch (State) {
+      case R_OPENED:
+        if (Pt > OpenPt/*Don't add empty ranges.*/ && RightMapping) 
+          RightMapping->add(OpenPt, Pt-1, CurrentRSuccessor);
+        State = INTERSECT_OPENED;
+        break;
+      case ALL_IS_CLOSED:
+        State = L_OPENED;
+        break;
+      default:
+        assert(0 && "Got unexpected point.");
+        break;
+      }
+      CurrentLSuccessor = S;
+      OpenPt = Pt;
+    }
+    
+    void onLClose(const IntTy &Pt) {
+      switch (State) {
+      case L_OPENED:
+        assert(Pt >= OpenPt &&
+               "Subset is not sorted or contains overlapped ranges");
+        if (LeftMapping)
+          LeftMapping->add(OpenPt, Pt, CurrentLSuccessor);
+        State = ALL_IS_CLOSED;
+        break;
+      case INTERSECT_OPENED:
+        if (IntersectionMapping)
+          IntersectionMapping->add(OpenPt, Pt, CurrentLSuccessor);
+        OpenPt = Pt + 1;
+        State = R_OPENED;
+        break;
+      default:
+        assert(0 && "Got unexpected point.");
+        break;
+      }
+    }
+    
+    void onROpen(const IntTy &Pt, SuccessorClass *S) {
+      switch (State) {
+      case L_OPENED:
+        if (Pt > OpenPt && LeftMapping)
+          LeftMapping->add(OpenPt, Pt-1, CurrentLSuccessor);
+        State = INTERSECT_OPENED;
+        break;
+      case ALL_IS_CLOSED:
+        State = R_OPENED;
+        break;
+      default:
+        assert(0 && "Got unexpected point.");
+        break;
+      }
+      CurrentRSuccessor = S;
+      OpenPt = Pt;      
+    }
+    
+    void onRClose(const IntTy &Pt) {
+      switch (State) {
+      case R_OPENED:
+        assert(Pt >= OpenPt &&
+               "Subset is not sorted or contains overlapped ranges");
+        if (RightMapping)
+          RightMapping->add(OpenPt, Pt, CurrentRSuccessor);
+        State = ALL_IS_CLOSED;
+        break;
+      case INTERSECT_OPENED:
+        if (IntersectionMapping)
+          IntersectionMapping->add(OpenPt, Pt, CurrentLSuccessor);
+        OpenPt = Pt + 1;
+        State = L_OPENED;
+        break;
+      default:
+        assert(0 && "Got unexpected point.");
+        break;
+      }
+    }
+    
+    void onRLOpen(const IntTy &Pt,
+                  SuccessorClass *LS,
+                  SuccessorClass *RS) {
+      switch (State) {
+      case ALL_IS_CLOSED:
+        State = INTERSECT_OPENED;
+        break;
+      default:
+        assert(0 && "Got unexpected point.");
+        break;
+      }
+      CurrentLSuccessor = LS;
+      CurrentRSuccessor = RS;
+      OpenPt = Pt;        
+    }
+    
+    void onRLClose(const IntTy &Pt) {
+      switch (State) {
+      case INTERSECT_OPENED:
+        if (IntersectionMapping)
+          IntersectionMapping->add(OpenPt, Pt, CurrentLSuccessor);
+        State = ALL_IS_CLOSED;
+        break;
+      default:
+        assert(0 && "Got unexpected point.");
+        break;        
+      }
+    }
+    
+    bool isLOpened() { return State == L_OPENED; }
+    bool isROpened() { return State == R_OPENED; }
+  };
 
 public:
   
@@ -187,9 +336,110 @@ public:
     }
   }
   
+  void add(self& RHS) {
+    Items.insert(Items.end(), RHS.Items.begin(), RHS.Items.end());
+  }
+  
+  void add(const RangesCollection& RHS, SuccessorClass *S = 0) {
+    for (RangesCollectionConstIt i = RHS.begin(), e = RHS.end(); i != e; ++i)
+      add(*i, S);
+  }  
+  
   /// Removes items from set.
   void removeItem(RangeIterator i) { Items.erase(i); }
   
+  /// Calculates the difference between this mapping and RHS.
+  /// THIS without RHS is placed into LExclude,
+  /// RHS without THIS is placed into RExclude,
+  /// THIS intersect RHS is placed into Intersection.
+  void diff(self *LExclude, self *Intersection, self *RExclude,
+                             const self& RHS) {
+    
+    DiffStateMachine Machine(LExclude, Intersection, RExclude);
+    
+    CaseItemConstIt L = Items.begin(), R = RHS.Items.begin();
+    while (L != Items.end() && R != RHS.Items.end()) {
+      const Cluster &LCluster = *L;
+      const RangeEx &LRange = LCluster.first;
+      const Cluster &RCluster = *R;
+      const RangeEx &RRange = RCluster.first;
+      
+      if (LRange.getHigh() < RRange.getLow()) {
+        Machine.onLOpen(LRange.getLow(), LCluster.second);
+        Machine.onLClose(LRange.getHigh());
+        ++L;
+        continue;
+      }
+      
+      if (LRange.getLow() > RRange.getHigh()) {
+        Machine.onROpen(RRange.getLow(), RCluster.second);
+        Machine.onRClose(RRange.getHigh());
+        ++R;
+        continue;
+      }
+      
+      if (LRange.getLow() < RRange.getLow()) {
+        // May be opened in previous iteration.
+        if (!Machine.isLOpened())
+          Machine.onLOpen(LRange.getLow(), LCluster.second);
+        Machine.onROpen(RRange.getLow(), RCluster.second);
+      }
+      else if (RRange.getLow() < LRange.getLow()) {
+        if (!Machine.isROpened())
+          Machine.onROpen(RRange.getLow(), RCluster.second);
+        Machine.onLOpen(LRange.getLow(), LCluster.second);
+      }
+      else
+        Machine.onRLOpen(LRange.getLow(), LCluster.second, RCluster.second);
+      
+      if (LRange.getHigh() < RRange.getHigh()) {
+        Machine.onLClose(LRange.getHigh());
+        ++L;
+        while(L != Items.end() && L->first.getHigh() < RRange.getHigh()) {
+          Machine.onLOpen(L->first.getLow(), L->second);
+          Machine.onLClose(L->first.getHigh());
+          ++L;
+        }
+      }
+      else if (RRange.getHigh() < LRange.getHigh()) {
+        Machine.onRClose(RRange.getHigh());
+        ++R;
+        while(R != RHS.Items.end() && R->first.getHigh() < LRange.getHigh()) {
+          Machine.onROpen(R->first.getLow(), R->second);
+          Machine.onRClose(R->first.getHigh());
+          ++R;
+        }
+      }
+      else {
+        Machine.onRLClose(LRange.getHigh());
+        ++L;
+        ++R;
+      }
+    }
+    
+    if (L != Items.end()) {
+      if (Machine.isLOpened()) {
+        Machine.onLClose(L->first.getHigh());
+        ++L;
+      }
+      if (LExclude)
+        while (L != Items.end()) {
+          LExclude->add(L->first, L->second);
+          ++L;
+        }
+    } else if (R != RHS.Items.end()) {
+      if (Machine.isROpened()) {
+        Machine.onRClose(R->first.getHigh());
+        ++R;
+      }
+      if (RExclude)
+        while (R != RHS.Items.end()) {
+          RExclude->add(R->first, R->second);
+          ++R;
+        }
+    }
+  }  
+  
   /// Builds the finalized case objects.
   void getCases(Cases& TheCases) {
     CRSMap TheCRSMap;
@@ -218,6 +468,11 @@ public:
     // 2. After first item will added Sorted flag will cleared.
   }  
   
+  // Returns number of clusters
+  unsigned size() const {
+    return Items.size();
+  }
+  
   RangeIterator begin() { return Items.begin(); }
   RangeIterator end() { return Items.end(); }
 };
diff --git a/unittests/Support/IntegersSubsetTest.cpp b/unittests/Support/IntegersSubsetTest.cpp
index 836f29a269..2d0e357894 100644
--- a/unittests/Support/IntegersSubsetTest.cpp
+++ b/unittests/Support/IntegersSubsetTest.cpp
@@ -21,6 +21,7 @@ namespace {
   
   class Int : public APInt {
   public:
+    Int() {}
     Int(uint64_t V) : APInt(64, V) {}
     Int(const APInt& Src) : APInt(Src) {}
     bool operator < (const APInt& RHS) const { return ult(RHS); }
@@ -178,4 +179,146 @@ namespace {
       EXPECT_EQ(CaseIt->second.getItem(0), Range(Int(i * 10), Int(i * 10 + 9)));
     }
   }
+  
+  typedef unsigned unsigned_pair[2];
+  typedef unsigned_pair unsigned_ranges[];
+  
+  void TestDiff(
+      const unsigned_ranges LHS,
+      unsigned LSize,
+      const unsigned_ranges RHS,
+      unsigned RSize,
+      const unsigned_ranges ExcludeRes,
+      unsigned ExcludeResSize,
+      const unsigned_ranges IntersectRes,
+      unsigned IntersectResSize
+      ) {
+    Mapping::RangesCollection Ranges;
+    
+    Mapping LHSMapping;
+    for (unsigned i = 0; i < LSize; ++i)
+      Ranges.push_back(Range(Int(LHS[i][0]), Int(LHS[i][1])));
+    LHSMapping.add(Ranges);
+    
+    Ranges.clear();
+
+    Mapping RHSMapping;
+    for (unsigned i = 0; i < RSize; ++i)
+      Ranges.push_back(Range(Int(RHS[i][0]), Int(RHS[i][1])));
+    RHSMapping.add(Ranges);
+    
+    Mapping LExclude, Intersection;
+    
+    LHSMapping.diff(&LExclude, &Intersection, 0, RHSMapping);
+    
+    if (ExcludeResSize) {
+      EXPECT_EQ(LExclude.size(), ExcludeResSize);
+      
+      unsigned i = 0;
+      for (Mapping::RangeIterator rei = LExclude.begin(),
+           e = LExclude.end(); rei != e; ++rei, ++i)
+        EXPECT_EQ(rei->first, Range(ExcludeRes[i][0], ExcludeRes[i][1]));
+    } else
+      EXPECT_TRUE(LExclude.empty());
+    
+    if (IntersectResSize) {
+      EXPECT_EQ(Intersection.size(), IntersectResSize);
+      
+      unsigned i = 0;
+      for (Mapping::RangeIterator ii = Intersection.begin(),
+           e = Intersection.end(); ii != e; ++ii, ++i)
+        EXPECT_EQ(ii->first, Range(IntersectRes[i][0], IntersectRes[i][1]));
+    } else
+      EXPECT_TRUE(Intersection.empty());
+
+    LExclude.clear();
+    Intersection.clear();
+    RHSMapping.diff(0, &Intersection, &LExclude, LHSMapping);
+    
+    // Check LExclude again.
+    if (ExcludeResSize) {
+      EXPECT_EQ(LExclude.size(), ExcludeResSize);
+      
+      unsigned i = 0;
+      for (Mapping::RangeIterator rei = LExclude.begin(),
+           e = LExclude.end(); rei != e; ++rei, ++i)
+        EXPECT_EQ(rei->first, Range(ExcludeRes[i][0], ExcludeRes[i][1]));
+    } else
+      EXPECT_TRUE(LExclude.empty());    
+  }  
+  
+  TEST(IntegersSubsetTest, DiffTest) {
+    {
+      unsigned_ranges LHS = { { 0, 4 }, { 7, 10 }, { 13, 17 } };
+      unsigned_ranges RHS = { { 3, 14 } };
+      unsigned_ranges ExcludeRes = { { 0, 2 }, { 15, 17 } };
+      unsigned_ranges IntersectRes = { { 3, 4 }, { 7, 10 }, { 13, 14 } };
+
+      TestDiff(LHS, 3, RHS, 1, ExcludeRes, 2, IntersectRes, 3);
+    }
+
+    {
+      unsigned_ranges LHS = { { 0, 4 }, { 7, 10 }, { 13, 17 } };
+      unsigned_ranges RHS = { { 0, 4 }, { 13, 17 } };
+      unsigned_ranges ExcludeRes = { { 7, 10 } };
+      unsigned_ranges IntersectRes = { { 0, 4 }, { 13, 17 } };
+
+      TestDiff(LHS, 3, RHS, 2, ExcludeRes, 1, IntersectRes, 2);
+    }
+
+    {
+      unsigned_ranges LHS = { { 0, 17 } };
+      unsigned_ranges RHS = { { 1, 5 }, { 10, 12 }, { 15, 16 } };
+      unsigned_ranges ExcludeRes =
+          { { 0, 0 }, { 6, 9 }, { 13, 14 }, { 17, 17 } };
+      unsigned_ranges IntersectRes = { { 1, 5 }, { 10, 12 }, { 15, 16 } };
+
+      TestDiff(LHS, 1, RHS, 3, ExcludeRes, 4, IntersectRes, 3);
+    }
+
+    {
+      unsigned_ranges LHS = { { 2, 4 } };
+      unsigned_ranges RHS = { { 0, 5 } };
+      unsigned_ranges ExcludeRes = { {-1UL, -1UL} };
+      unsigned_ranges IntersectRes = { { 2, 4 } };
+
+      TestDiff(LHS, 1, RHS, 1, ExcludeRes, 0, IntersectRes, 1);
+    }
+
+    {
+      unsigned_ranges LHS = { { 2, 4 } };
+      unsigned_ranges RHS = { { 7, 8 } };
+      unsigned_ranges ExcludeRes = { { 2, 4 } };
+      unsigned_ranges IntersectRes = { {-1UL, -1UL} };
+
+      TestDiff(LHS, 1, RHS, 1, ExcludeRes, 1, IntersectRes, 0);
+    }
+
+    {
+      unsigned_ranges LHS = { { 3, 7 } };
+      unsigned_ranges RHS = { { 1, 4 } };
+      unsigned_ranges ExcludeRes = { { 5, 7 } };
+      unsigned_ranges IntersectRes = { { 3, 4 } };
+
+      TestDiff(LHS, 1, RHS, 1, ExcludeRes, 1, IntersectRes, 1);
+    }
+    
+    {
+      unsigned_ranges LHS = { { 0, 7 } };
+      unsigned_ranges RHS = { { 0, 5 }, { 6, 9 } };
+      unsigned_ranges ExcludeRes = { {-1UL, -1UL} };
+      unsigned_ranges IntersectRes = { { 0, 5 }, {6, 7} };
+
+      TestDiff(LHS, 1, RHS, 2, ExcludeRes, 0, IntersectRes, 2);
+    }
+    
+    {
+      unsigned_ranges LHS = { { 17, 17 } };
+      unsigned_ranges RHS = { { 4, 4 } };
+      unsigned_ranges ExcludeRes = { {17, 17} };
+      unsigned_ranges IntersectRes = { { -1UL, -1UL } };
+
+      TestDiff(LHS, 1, RHS, 1, ExcludeRes, 1, IntersectRes, 0);
+    }     
+  }   
 }