edge_xmin_at_yinterval_double_compare is not a strict weak ordering

[rocallahan]

LLVM's libc++ produces fatal assertions like this in debug builds:

strict_weak_ordering_check.h:59: assertion __comp(*(__first + __a), *(__first + __b)) failed: Your comparator is not a valid strict-weak ordering

in the first call to sort() in get_intersections_per_band_any in dbEdgeProcessor.cc.

The problem can be seen by applying the following patch:

diff --git a/src/db/db/dbEdgeProcessor.cc b/src/db/db/dbEdgeProcessor.cc
index fd3ffb113..ce2db34b9 100644
--- a/src/db/db/dbEdgeProcessor.cc
+++ b/src/db/db/dbEdgeProcessor.cc
@@ -1338,6 +1338,22 @@ public:
   double m_y1, m_y2;
 };
 
+void do_test() {
+  std::vector<db::Edge> edges = {
+    db::Edge(259306, 21099, 259200, 21135),
+    db::Edge(260453, 21114, 260452, 21113),
+    db::Edge(260452, 21131, 260453, 21114),
+    db::Edge(260452, 21243, 260452, 21131),
+  };
+  edge_xmin_at_yinterval_double_compare<db::Coord> cmp(21113.5, 21135.5);
+  for (int i = 0; i < 4; ++i) {
+    for (int j = 0; j < 4; ++j) {
+      std::cout << "i: " << i << " j: " << j << " " << cmp(edges[i], edges[j]) << "\n";
+    }
+  }
+  std::sort(edges.begin(), edges.end(), cmp);
+}
+
 static void 
 get_intersections_per_band_any (std::vector <CutPoints> &cutpoints, std::vector <WorkEdge>::iterator current, std::vector <WorkEdge>::iterator future, db::Coord y, db::Coord yy, bool with_h)
 {
@@ -1345,6 +1361,8 @@ get_intersections_per_band_any (std::vector <CutPoints> &cutpoints, std::vector
   double dyy = yy + 0.5;
   std::vector <std::pair<const WorkEdge *, WorkEdge *> > p1_weak;   // holds weak interactions of edge endpoints with other edges
 
+  do_test();
+  
   std::sort (current, future, edge_xmin_at_yinterval_double_compare<db::Coord> (dy, dyy));
 
 #ifdef DEBUG_EDGE_PROCESSOR

and then running on any system. The output I get is

i: 0 j: 0 0
i: 0 j: 1 1
i: 0 j: 2 1
i: 0 j: 3 1
i: 1 j: 0 0
i: 1 j: 1 0
i: 1 j: 2 1
i: 1 j: 3 0
i: 2 j: 0 0
i: 2 j: 1 0
i: 2 j: 2 0
i: 2 j: 3 0
i: 3 j: 0 0
i: 3 j: 1 0
i: 3 j: 2 0
i: 3 j: 3 0

So the ordering relation is 0 < 1,2,3 and 1 < 2. This is not a strict weak ordering because it violates transitivity of equivalence: 1 is equivalent to 3 (because 1<3 and 3<1 are both false); 3 is equivalent to 2 (because 3<2 and 2<3 are both false); but 1 is not equivalent to 2 (because 1<2 is true).

[rocallahan]

I think this means the results of the sort are unreliable, which sounds bad, although we have not yet seen this causing a problem in the output.

[rocallahan]

(Element 0 is irrelevant, sorry for including that.)

[klayoutmatthias]

Thanks for debugging this problem.

I guess this patch fixes it:

--- a/src/db/db/dbEdgeProcessor.cc
+++ b/src/db/db/dbEdgeProcessor.cc
@@ -1321,7 +1321,7 @@ struct edge_xmin_at_yinterval_double_compare
   {
     if (edge_xmax (a) < edge_xmin (b)) {
       return true;
-    } else if (edge_xmin (a) >= edge_xmax (b)) {
+    } else if (edge_xmin (a) > edge_xmax (b)) {
       return false;
     } else {
       C xa = edge_xmin_at_yinterval_double (a, m_y1, m_y2);

Can you try?

Matthias

[rocallahan]

Yes, that fixes my testcases. Thanks!!!