Index: libstdc++-v3/include/bits/stl_algo.h
===================================================================
--- libstdc++-v3/include/bits/stl_algo.h	(revision 172360)
+++ libstdc++-v3/include/bits/stl_algo.h	(working copy)
@@ -318,6 +318,39 @@
   // count_if
   // search
 
+// Local modification: if __google_stl_debug_compare is defined to
+// non-zero value, check sort predicate for strict weak ordering.
+// Google ref b/1731200.
+#if __google_stl_debug_compare
+  template<typename _Compare>
+  struct _CheckedCompare {
+    _Compare _M_compare;
+
+    _CheckedCompare(const _Compare & __comp): _M_compare(__comp) { }
+
+    template <typename _Tp>
+    bool operator()(const _Tp& __x, const _Tp& __y) {
+      if (_M_compare(__x, __x))
+        __throw_runtime_error("strict weak ordering: (__x LT __x) != false");
+      if (_M_compare(__y, __y))
+        __throw_runtime_error("strict weak ordering: (__y LT __y) != false");
+      bool lt = _M_compare(__x, __y);
+      if (lt && _M_compare(__y, __x))
+        __throw_runtime_error("strict weak ordering: ((__x LT __y) && (__y LT __x)) != false");
+      return lt;
+    }
+
+    // Different types; can't perform any checks.
+    template <typename _Tp1, typename _Tp2>
+    bool operator()(const _Tp1& __x, const _Tp2& __y) {
+      return _M_compare(__x, __y);
+    }
+  };
+# define __CheckedCompare(__comp) _CheckedCompare<__typeof__(__comp)>(__comp)
+#else
+# define __CheckedCompare(__comp) __comp
+#endif
+
   /**
    *  This is an uglified
    *  search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
@@ -2041,18 +2074,20 @@
 	  ++__result_real_last;
 	  ++__first;
 	}
-      std::make_heap(__result_first, __result_real_last, __comp);
+      std::make_heap(__result_first, __result_real_last,
+                     __CheckedCompare(__comp));
       while (__first != __last)
 	{
-	  if (__comp(*__first, *__result_first))
+	  if (__CheckedCompare(__comp)(*__first, *__result_first))
 	    std::__adjust_heap(__result_first, _DistanceType(0),
 			       _DistanceType(__result_real_last
 					     - __result_first),
 			       _InputValueType(*__first),
-			       __comp);
+			       __CheckedCompare(__comp));
 	  ++__first;
 	}
-      std::sort_heap(__result_first, __result_real_last, __comp);
+      std::sort_heap(__result_first, __result_real_last,
+                     __CheckedCompare(__comp));
       return __result_real_last;
     }
 
@@ -2413,7 +2448,7 @@
 	  _DistanceType __half = __len >> 1;
 	  _ForwardIterator __middle = __first;
 	  std::advance(__middle, __half);
-	  if (__comp(*__middle, __val))
+	  if (__CheckedCompare(__comp)(*__middle, __val))
 	    {
 	      __first = __middle;
 	      ++__first;
@@ -2509,7 +2544,7 @@
 	  _DistanceType __half = __len >> 1;
 	  _ForwardIterator __middle = __first;
 	  std::advance(__middle, __half);
-	  if (__comp(__val, *__middle))
+	  if (__CheckedCompare(__comp)(__val, *__middle))
 	    __len = __half;
 	  else
 	    {
@@ -2628,13 +2663,13 @@
 	  _DistanceType __half = __len >> 1;
 	  _ForwardIterator __middle = __first;
 	  std::advance(__middle, __half);
-	  if (__comp(*__middle, __val))
+	  if (__CheckedCompare(__comp)(*__middle, __val))
 	    {
 	      __first = __middle;
 	      ++__first;
 	      __len = __len - __half - 1;
 	    }
-	  else if (__comp(__val, *__middle))
+	  else if (__CheckedCompare(__comp)(__val, *__middle))
 	    __len = __half;
 	  else
 	    {
@@ -2711,7 +2746,7 @@
 						__val, __comp);
 
       _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
-      return __i != __last && !bool(__comp(__val, *__i));
+      return __i != __last && !bool(__CheckedCompare(__comp)(__val, *__i));
     }
 
   // merge
@@ -3180,11 +3215,11 @@
 								  __last);
       if (__buf.begin() == 0)
 	std::__merge_without_buffer(__first, __middle, __last, __len1,
-				    __len2, __comp);
+				    __len2, __CheckedCompare(__comp));
       else
 	std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
 			      __buf.begin(), _DistanceType(__buf.size()),
-			      __comp);
+			      __CheckedCompare(__comp));
     }
 
   template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
@@ -3505,9 +3540,9 @@
       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
 
       while (__first1 != __last1 && __first2 != __last2)
-	if (__comp(*__first2, *__first1))
+	if (__CheckedCompare(__comp)(*__first2, *__first1))
 	  return false;
-	else if(__comp(*__first1, *__first2))
+	else if(__CheckedCompare(__comp)(*__first1, *__first2))
 	  ++__first1;
 	else
 	  ++__first1, ++__first2;
@@ -3620,10 +3655,10 @@
 	{
 	  _BidirectionalIterator __ii = __i;
 	  --__i;
-	  if (__comp(*__i, *__ii))
+	  if (__CheckedCompare(__comp)(*__i, *__ii))
 	    {
 	      _BidirectionalIterator __j = __last;
-	      while (!bool(__comp(*__i, *--__j)))
+	      while (!bool(__CheckedCompare(__comp)(*__i, *--__j)))
 		{}
 	      std::iter_swap(__i, __j);
 	      std::reverse(__ii, __last);
@@ -3733,10 +3768,10 @@
 	{
 	  _BidirectionalIterator __ii = __i;
 	  --__i;
-	  if (__comp(*__ii, *__i))
+	  if (__CheckedCompare(__comp)(*__ii, *__i))
 	    {
 	      _BidirectionalIterator __j = __last;
-	      while (!bool(__comp(*--__j, *__i)))
+	      while (!bool(__CheckedCompare(__comp)(*--__j, *__i)))
 		{}
 	      std::iter_swap(__i, __j);
 	      std::reverse(__ii, __last);
@@ -3909,7 +3944,7 @@
 
       _ForwardIterator __next = __first;
       for (++__next; __next != __last; __first = __next, ++__next)
-	if (__comp(*__next, *__first))
+	if (__CheckedCompare(__comp)(*__next, *__first))
 	  return __next;
       return __next;
     }
@@ -3944,8 +3979,9 @@
     inline pair<const _Tp&, const _Tp&>
     minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
     {
-      return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a)
-	                      : pair<const _Tp&, const _Tp&>(__a, __b);
+      return __CheckedCompare(__comp)(__b, __a)
+          ? pair<const _Tp&, const _Tp&>(__b, __a)
+          : pair<const _Tp&, const _Tp&>(__a, __b);
     }
 
   /**
@@ -4053,7 +4089,7 @@
 	return std::make_pair(__first, __first);
 
       _ForwardIterator __min, __max;
-      if (__comp(*__next, *__first))
+      if (__CheckedCompare(__comp)(*__next, *__first))
 	{
 	  __min = __next;
 	  __max = __first;
@@ -4072,25 +4108,25 @@
 	  __next = __first;
 	  if (++__next == __last)
 	    {
-	      if (__comp(*__first, *__min))
+	      if (__CheckedCompare(__comp)(*__first, *__min))
 		__min = __first;
-	      else if (!__comp(*__first, *__max))
+	      else if (!__CheckedCompare(__comp)(*__first, *__max))
 		__max = __first;
 	      break;
 	    }
 
-	  if (__comp(*__next, *__first))
+	  if (__CheckedCompare(__comp)(*__next, *__first))
 	    {
-	      if (__comp(*__next, *__min))
+	      if (__CheckedCompare(__comp)(*__next, *__min))
 		__min = __next;
-	      if (!__comp(*__first, *__max))
+	      if (!__CheckedCompare(__comp)(*__first, *__max))
 		__max = __first;
 	    }
 	  else
 	    {
-	      if (__comp(*__first, *__min))
+	      if (__CheckedCompare(__comp)(*__first, *__min))
 		__min = __first;
-	      if (!__comp(*__next, *__max))
+	      if (!__CheckedCompare(__comp)(*__next, *__max))
 		__max = __next;
 	    }
 
@@ -5215,8 +5251,8 @@
       __glibcxx_requires_valid_range(__first, __middle);
       __glibcxx_requires_valid_range(__middle, __last);
 
-      std::__heap_select(__first, __middle, __last, __comp);
-      std::sort_heap(__first, __middle, __comp);
+      std::__heap_select(__first, __middle, __last, __CheckedCompare(__comp));
+      std::sort_heap(__first, __middle, __CheckedCompare(__comp));
     }
 
   /**
@@ -5294,7 +5330,8 @@
 	return;
 
       std::__introselect(__first, __nth, __last,
-			 std::__lg(__last - __first) * 2, __comp);
+			 std::__lg(__last - __first) * 2,
+                         __CheckedCompare(__comp));
     }
 
 
@@ -5366,8 +5403,10 @@
       if (__first != __last)
 	{
 	  std::__introsort_loop(__first, __last,
-				std::__lg(__last - __first) * 2, __comp);
-	  std::__final_insertion_sort(__first, __last, __comp);
+				std::__lg(__last - __first) * 2,
+                                __CheckedCompare(__comp));
+	  std::__final_insertion_sort(__first, __last,
+                                      __CheckedCompare(__comp));
 	}
     }
 
@@ -5478,7 +5517,7 @@
 
       while (__first1 != __last1 && __first2 != __last2)
 	{
-	  if (__comp(*__first2, *__first1))
+	  if (__CheckedCompare(__comp)(*__first2, *__first1))
 	    {
 	      *__result = *__first2;
 	      ++__first2;
@@ -5575,10 +5614,11 @@
       _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
 								 __last);
       if (__buf.begin() == 0)
-	std::__inplace_stable_sort(__first, __last, __comp);
+	std::__inplace_stable_sort(__first, __last, __CheckedCompare(__comp));
       else
 	std::__stable_sort_adaptive(__first, __last, __buf.begin(),
-				    _DistanceType(__buf.size()), __comp);
+				    _DistanceType(__buf.size()),
+                                    __CheckedCompare(__comp));
     }
 
 
@@ -5695,12 +5735,12 @@
 
       while (__first1 != __last1 && __first2 != __last2)
 	{
-	  if (__comp(*__first1, *__first2))
+	  if (__CheckedCompare(__comp)(*__first1, *__first2))
 	    {
 	      *__result = *__first1;
 	      ++__first1;
 	    }
-	  else if (__comp(*__first2, *__first1))
+	  else if (__CheckedCompare(__comp)(*__first2, *__first1))
 	    {
 	      *__result = *__first2;
 	      ++__first2;
@@ -5816,9 +5856,9 @@
       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
 
       while (__first1 != __last1 && __first2 != __last2)
-	if (__comp(*__first1, *__first2))
+	if (__CheckedCompare(__comp)(*__first1, *__first2))
 	  ++__first1;
-	else if (__comp(*__first2, *__first1))
+	else if (__CheckedCompare(__comp)(*__first2, *__first1))
 	  ++__first2;
 	else
 	  {
@@ -5935,13 +5975,13 @@
       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
 
       while (__first1 != __last1 && __first2 != __last2)
-	if (__comp(*__first1, *__first2))
+	if (__CheckedCompare(__comp)(*__first1, *__first2))
 	  {
 	    *__result = *__first1;
 	    ++__first1;
 	    ++__result;
 	  }
-	else if (__comp(*__first2, *__first1))
+	else if (__CheckedCompare(__comp)(*__first2, *__first1))
 	  ++__first2;
 	else
 	  {
@@ -6062,13 +6102,13 @@
       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
 
       while (__first1 != __last1 && __first2 != __last2)
-	if (__comp(*__first1, *__first2))
+	if (__CheckedCompare(__comp)(*__first1, *__first2))
 	  {
 	    *__result = *__first1;
 	    ++__first1;
 	    ++__result;
 	  }
-	else if (__comp(*__first2, *__first1))
+	else if (__CheckedCompare(__comp)(*__first2, *__first1))
 	  {
 	    *__result = *__first2;
 	    ++__first2;
@@ -6135,7 +6175,7 @@
 	return __first;
       _ForwardIterator __result = __first;
       while (++__first != __last)
-	if (__comp(*__first, *__result))
+	if (__CheckedCompare(__comp)(*__first, *__result))
 	  __result = __first;
       return __result;
     }
@@ -6190,11 +6230,13 @@
       if (__first == __last) return __first;
       _ForwardIterator __result = __first;
       while (++__first != __last)
-	if (__comp(*__result, *__first))
+	if (__CheckedCompare(__comp)(*__result, *__first))
 	  __result = __first;
       return __result;
     }
 
+#undef __CheckedCompare
+
 _GLIBCXX_END_NAMESPACE_ALGO
 } // namespace std
 
Index: libstdc++-v3/include/bits/stl_tree.h
===================================================================
--- libstdc++-v3/include/bits/stl_tree.h	(revision 172360)
+++ libstdc++-v3/include/bits/stl_tree.h	(working copy)
@@ -461,7 +461,47 @@
 	  }	    
 	};
 
+      // Local modification: if __google_stl_debug_rbtree is defined to
+      // non-zero value, check sort predicate for strict weak ordering.
+      // Google ref b/1731200.
+#if __google_stl_debug_rbtree
+      template<typename _KeyCompare>
+      struct _CheckedCompare {
+        _KeyCompare _M_key_compare;
+
+        _CheckedCompare(): _M_key_compare() { }
+        _CheckedCompare(const _KeyCompare & __comp): _M_key_compare(__comp) { }
+
+	// Template arg required to avoid duplicating code in the two op()
+	// operators below.  User-provided _M_key_compare may not be const,
+	// but needs to be callable from our const op().
+	// Google ref. b/1731200.
+	template <typename _KeyCompareT>
+        static bool _M_compare_with(_KeyCompareT& __comp, const _Key& __x, const _Key& __y) {
+          if (__comp(__x, __x))
+            __throw_runtime_error("strict weak ordering: (__x LT __x) != false");
+          if (__comp(__y, __y))
+            __throw_runtime_error("strict weak ordering: (__y LT __y) != false");
+          bool lt = __comp(__x, __y);
+          if (lt && __comp(__y, __x))
+            __throw_runtime_error("strict weak ordering: ((__x LT __y) && (__y LT __x)) != false");
+          return lt;
+        }
+        bool operator()(const _Key& __x, const _Key& __y) const {
+	  return _M_compare_with(_M_key_compare, __x, __y);
+        }
+
+        bool operator()(const _Key& __x, const _Key& __y) {
+	  return _M_compare_with(_M_key_compare, __x, __y);
+        }
+
+        operator _KeyCompare() const { return _M_key_compare; }
+      };
+
+      _Rb_tree_impl<_CheckedCompare<_Compare> > _M_impl;
+#else
       _Rb_tree_impl<_Compare> _M_impl;
+#endif
 
     protected:
       _Base_ptr&
