[ADT] IntervalTree - Random unittests failures in a debug build

[CarlosAlbertoEnciso]

Summary

As reported by @antondaubert:

On a debug build with _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY enabled from 100 executions around 80 are failing.

More details in https://reviews.llvm.org/D125776#3820399

The issue is related to the use of std::sort.

[jryans]

Thanks, looks good to me! 😄

[probinson]

Hmmm. Does that mean the sorted result is dependent on the order of insertion? If so, is that really what you want?

[CarlosAlbertoEnciso]

In D134805#3820752, @probinson wrote:

Hmmm. Does that mean the sorted result is dependent on the order of insertion? If so, is that really what you want?

No. I changed the insertion order in the largest test case and the results are the same.

[probinson]

In D134805#3820776, @CarlosAlbertoEnciso wrote:

In D134805#3820752, @probinson wrote:

Hmmm. Does that mean the sorted result is dependent on the order of insertion? If so, is that really what you want?

No. I changed the insertion order in the largest test case and the results are the same.

SGTM.

[CarlosAlbertoEnciso]

@antondaubert, @jryans, @probinson Thanks for your reviews.

llvm/include/llvm/ADT/IntervalTree.h

for (int Index = ReferencesBeginIndex; Index < ReferencesRightIndex;) {
         continue;
       }
       ++Index;
     }
 
     // Sort intervals on the left and right of the middle point.
     if (NewBucketSize > 1) {
       // Sort the intervals in ascending order by their beginning point.
-      std::sort(IntervalsLeft.begin() + NewBucketStart,
+      std::stable_sort(IntervalsLeft.begin() + NewBucketStart,
                        IntervalsLeft.begin() + NewBucketStart + NewBucketSize,
                        [](const DataType *LHS, const DataType *RHS) {
                          return LHS->left() < RHS->left();
                        });
       // Sort the intervals in descending order by their ending point.
-      std::sort(IntervalsRight.begin() + NewBucketStart,
+      std::stable_sort(IntervalsRight.begin() + NewBucketStart,
                        IntervalsRight.begin() + NewBucketStart + NewBucketSize,
                        [](const DataType *LHS, const DataType *RHS) {
                          return LHS->right() > RHS->right();
                        });
     }
 
     if (PointsBeginIndex <= MiddleIndex - 1) {
       Root->Left = createTree(IntervalsSize, PointsBeginIndex, MiddleIndex - 1,
                               ReferencesBeginIndex, ReferencesRightIndex);
     }
 
     if (MiddleIndex + 1 <= PointsEndIndex) {
for (find_iterator Iter = find(Point), E = find_end(); Iter != E; ++Iter)
       IntervalSet.push_back(const_cast<DataType *>(&(*Iter)));
     return IntervalSet;
   }
 
   /// Sort the given intervals using the following sort options:
   /// Ascending: return the intervals with the smallest at the front.
   /// Descending: return the intervals with the biggest at the front.
   static void sortIntervals(IntervalReferences &IntervalSet, Sorting Sort) {
-    std::sort(IntervalSet.begin(), IntervalSet.end(),
+    std::stable_sort(IntervalSet.begin(), IntervalSet.end(),
                      [Sort](const DataType *RHS, const DataType *LHS) {
                        return Sort == Sorting::Ascending
                                   ? (LHS->right() - LHS->left()) >
                                         (RHS->right() - RHS->left())
                                   : (LHS->right() - LHS->left()) <
                                         (RHS->right() - RHS->left());
                      });
   }
 
   /// Print the interval tree.
   /// When \a HexFormat is true, the interval tree interval ranges and
   /// associated values are printed in hexadecimal format.
   void print(raw_ostream &OS, bool HexFormat = true) {
     printTree(OS, 0, Root, HexFormat);
   }
 
   /// Create the interval tree.
   void create() {
     assert(empty() && "Interval tree already constructed.");
     // Sorted vector of unique end points values of all the intervals.
     // Records references to the collected intervals.
     SmallVector<PointType, 4> Points;
     for (const DataType &Data : Intervals) {
       Points.push_back(Data.left());
       Points.push_back(Data.right());
       References.push_back(std::addressof(Data));
     }
-    std::sort(Points.begin(), Points.end());
+    std::stable_sort(Points.begin(), Points.end());
     auto Last = std::unique(Points.begin(), Points.end());
     Points.erase(Last, Points.end());
 
     EndPoints.assign(Points.begin(), Points.end());
 
     IntervalsLeft.resize(Intervals.size());
     IntervalsRight.resize(Intervals.size());