From eea7e55c97a333fece4889abee3d9a7b3dcb2a7c Mon Sep 17 00:00:00 2001
From: Timo Heister <timo.heister@gmail.com>
Date: Wed, 22 Jul 2015 15:42:31 -0400
Subject: [PATCH] fix invalid operation in DynamicSparsityPattern::iterator

We used to compare two std::vector iterators that might belong to
different std::vectors. This is obviously illegal.

This addresses issue #1175, see
https://github.com/dealii/dealii/issues/1175

Add a test that failed (with stl debug library only).
---
 doc/news/changes.h                            |   7 +
 .../deal.II/lac/dynamic_sparsity_pattern.h    |   5 +-
 .../dynamic_sparsity_pattern_iterator_04.cc   | 137 ++++++++++++++++++
 ...ynamic_sparsity_pattern_iterator_04.output |  29 ++++
 4 files changed, 175 insertions(+), 3 deletions(-)
 create mode 100644 tests/bits/dynamic_sparsity_pattern_iterator_04.cc
 create mode 100644 tests/bits/dynamic_sparsity_pattern_iterator_04.output

diff --git a/doc/news/changes.h b/doc/news/changes.h
index 8261c67da3..72afd555fb 100644
--- a/doc/news/changes.h
+++ b/doc/news/changes.h
@@ -74,6 +74,13 @@ inconvenience this causes.
 
 
 <ol>
+
+  <li> Fixed: bug in DynamicSparsityPattern::iterator would cause invalid
+  stl::vector::iterator comparison.
+  <br>
+  (Timo Heister, 2015/07/22)
+  </li>
+
   <li> New: FESystem now does some work in parallel if your system
   has multiple processors.
   <br>
diff --git a/include/deal.II/lac/dynamic_sparsity_pattern.h b/include/deal.II/lac/dynamic_sparsity_pattern.h
index d7e4629ca5..458c4cba1f 100644
--- a/include/deal.II/lac/dynamic_sparsity_pattern.h
+++ b/include/deal.II/lac/dynamic_sparsity_pattern.h
@@ -739,9 +739,8 @@ namespace DynamicSparsityPatternIterators
     // current_entry field may not point to a deterministic location
     return (sparsity_pattern == other.sparsity_pattern &&
             current_row == other.current_row &&
-            ((current_entry == other.current_entry)
-             ||
-             (current_row == numbers::invalid_unsigned_int)));
+            ((current_row == numbers::invalid_unsigned_int)
+             || (current_entry == other.current_entry)));
   }
 
 
diff --git a/tests/bits/dynamic_sparsity_pattern_iterator_04.cc b/tests/bits/dynamic_sparsity_pattern_iterator_04.cc
new file mode 100644
index 0000000000..37ed68dc60
--- /dev/null
+++ b/tests/bits/dynamic_sparsity_pattern_iterator_04.cc
@@ -0,0 +1,137 @@
+// ---------------------------------------------------------------------
+//
+// Copyright (C) 2004 - 2015 by the deal.II authors
+//
+// This file is part of the deal.II library.
+//
+// The deal.II library is free software; you can use it, redistribute
+// it, and/or modify it under the terms of the GNU Lesser General
+// Public License as published by the Free Software Foundation; either
+// version 2.1 of the License, or (at your option) any later version.
+// The full text of the license can be found in the file LICENSE at
+// the top level of the deal.II distribution.
+//
+// ---------------------------------------------------------------------
+
+
+
+// test DynamicSparsityPattern::iterator and document bug with std::vector iterators
+
+/*
+crash:
+/usr/include/c++/4.8/debug/safe_iterator.h:506:error: attempt to compare a 
+    singular iterator to a singular iterator.
+
+Objects involved in the operation:
+iterator "lhs" @ 0x0x7fffffffc860 {
+type = N11__gnu_debug14_Safe_iteratorIN9__gnu_cxx17__normal_iteratorIPKjSt6vectorIjSaIjEEEENSt7__debug6vectorIjS6_EEEE (constant iterator);
+  state = singular;
+}
+iterator "rhs" @ 0x0x7fffffffd670 {
+type = N11__gnu_debug14_Safe_iteratorIN9__gnu_cxx17__normal_iteratorIPKjSt6vectorIjSaIjEEEENSt7__debug6vectorIjS6_EEEE (constant iterator);
+  state = singular;
+}
+
+backtrace:
+#3  0x0000000000416c29 in __gnu_debug::operator==<__gnu_cxx::__normal_iterator<unsigned int const*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::__debug::vector<unsigned int, std::allocator<unsigned int> > > (__lhs=<error reading variable: Cannot access memory at address 0x0>, __rhs=<error reading variable: Cannot access memory at address 0x0>) at /usr/include/c++/4.8/debug/safe_iterator.h:503
+#4  0x000000000041075b in operator== (other=..., this=0x7fffffffc850) at /scratch/deal-git/include/deal.II/lac/dynamic_sparsity_pattern.h:743
+#5  operator== (other=..., this=0x7fffffffc850) at /scratch/deal-git/include/deal.II/lac/dynamic_sparsity_pattern.h:868
+#6  operator!= (other=..., this=0x7fffffffc850) at /scratch/deal-git/include/deal.II/lac/dynamic_sparsity_pattern.h:877
+#7  iterate (sp=...) at /scratch/deal-git/tests/bits/dynamic_sparsity_pattern_iterator_04.cc:30
+*/
+
+#include "../tests.h"
+#include <deal.II/lac/dynamic_sparsity_pattern.h>
+#include <fstream>
+#include <iomanip>
+
+
+void iterate(DynamicSparsityPattern &sp)
+{
+  DynamicSparsityPattern::const_iterator i = sp.begin();
+  for (; i!=sp.end(); ++i)
+    deallog << i->row() << ' ' << i->column() << std::endl;
+
+  deallog << "OK" << std::endl;
+
+  {
+    for (unsigned int row=0; row<sp.n_rows(); ++row)
+      {
+	DynamicSparsityPattern::iterator col = sp.begin(row),
+				     end_col = sp.end(row);
+	deallog << "row " << row << ":" << std::endl;
+	for (;col != end_col;++col)
+	  {
+	    deallog << "row= " << col->row()
+		    << ", col= "<< col->column()
+		    << ", index= " << col->index()
+		    << std::endl;
+	  }
+      }
+  }
+  deallog << "OK" << std::endl;
+}
+
+
+void test ()
+{
+  {
+    DynamicSparsityPattern sp (5,4);
+    sp.add (0,0);
+    sp.add (0,1);
+    sp.add (3,3);
+    sp.compress ();
+
+    deallog << "** 5 by 4 ** " << std::endl;
+    iterate (sp);
+  }
+  {
+    DynamicSparsityPattern sp (5,5);
+    sp.add (0,0);
+    sp.add (0,1);
+    sp.add (3,3);
+    sp.compress ();
+    
+    deallog << "** 5 by 5 ** " << std::endl;
+    iterate (sp);
+  }
+}
+
+
+
+int main ()
+{
+  std::ofstream logfile("output");
+  deallog.attach(logfile);
+  deallog.depth_console(0);
+  deallog.threshold_double(1.e-10);
+
+  try
+    {
+      test ();
+    }
+  catch (std::exception &exc)
+    {
+      deallog << std::endl << std::endl
+              << "----------------------------------------------------"
+              << std::endl;
+      deallog << "Exception on processing: " << std::endl
+              << exc.what() << std::endl
+              << "Aborting!" << std::endl
+              << "----------------------------------------------------"
+              << std::endl;
+
+      return 1;
+    }
+  catch (...)
+    {
+      deallog << std::endl << std::endl
+              << "----------------------------------------------------"
+              << std::endl;
+      deallog << "Unknown exception!" << std::endl
+              << "Aborting!" << std::endl
+              << "----------------------------------------------------"
+              << std::endl;
+      return 1;
+    };
+}
diff --git a/tests/bits/dynamic_sparsity_pattern_iterator_04.output b/tests/bits/dynamic_sparsity_pattern_iterator_04.output
new file mode 100644
index 0000000000..2cd6014642
--- /dev/null
+++ b/tests/bits/dynamic_sparsity_pattern_iterator_04.output
@@ -0,0 +1,29 @@
+
+DEAL::** 5 by 4 ** 
+DEAL::0 0
+DEAL::0 1
+DEAL::3 3
+DEAL::OK
+DEAL::row 0:
+DEAL::row= 0, col= 0, index= 0
+DEAL::row= 0, col= 1, index= 1
+DEAL::row 1:
+DEAL::row 2:
+DEAL::row 3:
+DEAL::row= 3, col= 3, index= 0
+DEAL::row 4:
+DEAL::OK
+DEAL::** 5 by 5 ** 
+DEAL::0 0
+DEAL::0 1
+DEAL::3 3
+DEAL::OK
+DEAL::row 0:
+DEAL::row= 0, col= 0, index= 0
+DEAL::row= 0, col= 1, index= 1
+DEAL::row 1:
+DEAL::row 2:
+DEAL::row 3:
+DEAL::row= 3, col= 3, index= 0
+DEAL::row 4:
+DEAL::OK
-- 
2.39.5