Patchwork Compare iterators, not values, in filtered_iterator::operator{==,!=}

login
register
mail settings
Submitter Simon Marchi
Date Nov. 27, 2019, 3:47 a.m.
Message ID <20191127034707.423030-1-simon.marchi@polymtl.ca>
Download mbox | patch
Permalink /patch/36293/
State New
Headers show

Comments

Simon Marchi - Nov. 27, 2019, 3:47 a.m.
From: Simon Marchi <simon.marchi@efficios.com>

The == and != operators on filtered_iterator are not doing the
right thing, they compare values pointed by the wrapped iterators
instead of comparing the iterators themselves.

As a result, operator== will return true if the two iterators point to
two equal values at different positions.  operator!= will fail
similarly.

Also, this causes it to deference past-the-end iterators when doing.
For example, in

  for (iter = ...; iter != end_iter; ++iter)

the != comparison dereferences end_iter.  I don't think this should
happen.

I don't think it's a problem today, given that we only use
filtered_iterator to wrap linked lists of threads and inferiors.
Dereferencing past-the-end iterators of these types is not fatal, it
just returns NULL, which is not a value we otherwise find in the lists.
But in other contexts, it could become problematic.

I have added a simple self test that fails without the fix applied.

gdb/ChangeLog:

	* filtered-iterator.h (filtered_iterator) <operator==,
	operator!=>: Compare wrapped iterators, not wrapped pointers.
	* Makefile.in (SUBDIR_UNITTESTS_SRCS): Add
	unittests/filtered_iterator-selftests.c.
	* unittests/filtered_iterator-selftests.c: New file.

Change-Id: I45de07c4772b4cb661fa2d9186379c2c13581972
---
 gdb/Makefile.in                             |   1 +
 gdb/gdbsupport/filtered-iterator.h          |   4 +-
 gdb/unittests/filtered_iterator-selftests.c | 165 ++++++++++++++++++++
 3 files changed, 168 insertions(+), 2 deletions(-)
 create mode 100644 gdb/unittests/filtered_iterator-selftests.c
Tom Tromey - Dec. 4, 2019, 6:09 p.m.
>>>>> "Simon" == Simon Marchi <simon.marchi@polymtl.ca> writes:

Simon> The == and != operators on filtered_iterator are not doing the
Simon> right thing, they compare values pointed by the wrapped iterators
Simon> instead of comparing the iterators themselves.

Simon> gdb/ChangeLog:

Simon> 	* filtered-iterator.h (filtered_iterator) <operator==,
Simon> 	operator!=>: Compare wrapped iterators, not wrapped pointers.
Simon> 	* Makefile.in (SUBDIR_UNITTESTS_SRCS): Add
Simon> 	unittests/filtered_iterator-selftests.c.
Simon> 	* unittests/filtered_iterator-selftests.c: New file.

This looks reasonable to me.  Thanks for doing this.

Tom
Simon Marchi - Dec. 4, 2019, 6:30 p.m.
On 2019-12-04 1:09 p.m., Tom Tromey wrote:
>>>>>> "Simon" == Simon Marchi <simon.marchi@polymtl.ca> writes:
> 
> Simon> The == and != operators on filtered_iterator are not doing the
> Simon> right thing, they compare values pointed by the wrapped iterators
> Simon> instead of comparing the iterators themselves.
> 
> Simon> gdb/ChangeLog:
> 
> Simon> 	* filtered-iterator.h (filtered_iterator) <operator==,
> Simon> 	operator!=>: Compare wrapped iterators, not wrapped pointers.
> Simon> 	* Makefile.in (SUBDIR_UNITTESTS_SRCS): Add
> Simon> 	unittests/filtered_iterator-selftests.c.
> Simon> 	* unittests/filtered_iterator-selftests.c: New file.
> 
> This looks reasonable to me.  Thanks for doing this.
> 
> Tom
> 

Thanks, I pushed it.

Simon

Patch

diff --git a/gdb/Makefile.in b/gdb/Makefile.in
index 58f5f93c54f0..2f4513006172 100644
--- a/gdb/Makefile.in
+++ b/gdb/Makefile.in
@@ -422,6 +422,7 @@  SUBDIR_UNITTESTS_SRCS = \
 	unittests/common-utils-selftests.c \
 	unittests/copy_bitwise-selftests.c \
 	unittests/environ-selftests.c \
+	unittests/filtered_iterator-selftests.c \
 	unittests/format_pieces-selftests.c \
 	unittests/function-view-selftests.c \
 	unittests/help-doc-selftests.c \
diff --git a/gdb/gdbsupport/filtered-iterator.h b/gdb/gdbsupport/filtered-iterator.h
index e1b486d6f08e..c3e8f38257b0 100644
--- a/gdb/gdbsupport/filtered-iterator.h
+++ b/gdb/gdbsupport/filtered-iterator.h
@@ -64,10 +64,10 @@  public:
   }
 
   bool operator== (const self_type &other) const
-  { return *m_it == *other.m_it; }
+  { return m_it == other.m_it; }
 
   bool operator!= (const self_type &other) const
-  { return *m_it != *other.m_it; }
+  { return m_it != other.m_it; }
 
 private:
 
diff --git a/gdb/unittests/filtered_iterator-selftests.c b/gdb/unittests/filtered_iterator-selftests.c
new file mode 100644
index 000000000000..1905bd74a4c6
--- /dev/null
+++ b/gdb/unittests/filtered_iterator-selftests.c
@@ -0,0 +1,165 @@ 
+/* Self tests for the filtered_iterator class.
+
+   Copyright (C) 2019 Free Software Foundation, Inc.
+
+   This file is part of GDB.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+#include "gdbsupport/common-defs.h"
+#include "gdbsupport/selftest.h"
+#include "gdbsupport/filtered-iterator.h"
+
+#include <iterator>
+
+namespace selftests {
+
+/* An iterator class that iterates on integer arrays.  */
+
+struct int_array_iterator
+{
+  using value_type = int;
+  using reference = int &;
+  using pointer = int *;
+  using iterator_category = std::forward_iterator_tag;
+  using difference_type = int;
+
+  /* Create an iterator that points at the first element of an integer
+     array at ARRAY of size SIZE.  */
+  int_array_iterator (int *array, size_t size)
+    : m_array (array), m_size (size)
+  {}
+
+  /* Create a past-the-end iterator.  */
+  int_array_iterator ()
+    : m_array (nullptr), m_size (0)
+  {}
+
+  bool operator== (const int_array_iterator &other) const
+  {
+    /* If both are past-the-end, they are equal.  */
+    if (m_array == nullptr && other.m_array == nullptr)
+      return true;
+
+    /* If just one of them is past-the-end, they are not equal.  */
+    if (m_array == nullptr || other.m_array == nullptr)
+      return false;
+
+    /* If they are both not past-the-end, make sure they iterate on the
+       same array (we shouldn't compare iterators that iterate on different
+       things).  */
+    gdb_assert (m_array == other.m_array);
+
+    /* They are equal if they have the same current index.  */
+    return m_cur_idx == other.m_cur_idx;
+  }
+
+  bool operator!= (const int_array_iterator &other) const
+  {
+    return !(*this == other);
+  }
+
+  void operator++ ()
+  {
+    /* Make sure nothing tries to increment a past the end iterator. */
+    gdb_assert (m_cur_idx < m_size);
+
+    m_cur_idx++;
+
+    /* Mark the iterator as "past-the-end" if we have reached the end.  */
+    if (m_cur_idx == m_size)
+      m_array = nullptr;
+  }
+
+  int operator* () const
+  {
+    /* Make sure nothing tries to dereference a past the end iterator.  */
+    gdb_assert (m_cur_idx < m_size);
+
+    return m_array[m_cur_idx];
+  }
+
+private:
+  /* A nullptr value in M_ARRAY indicates a past-the-end iterator.  */
+  int *m_array;
+  size_t m_size;
+  size_t m_cur_idx = 0;
+};
+
+/* Filter to only keep the even numbers.  */
+
+struct even_numbers_only
+{
+  bool operator() (int n)
+  {
+    return n % 2 == 0;
+  }
+};
+
+/* Test typical usage.  */
+
+static void
+test_filtered_iterator ()
+{
+  int array[] = { 4, 4, 5, 6, 7, 8, 9 };
+  std::vector<int> even_ints;
+  const std::vector<int> expected_even_ints { 4, 4, 6, 8 };
+
+  filtered_iterator<int_array_iterator, even_numbers_only>
+    iter (array, ARRAY_SIZE (array));
+  filtered_iterator<int_array_iterator, even_numbers_only> end;
+
+  for (; iter != end; ++iter)
+    even_ints.push_back (*iter);
+
+  gdb_assert (even_ints == expected_even_ints);
+}
+
+/* Test operator== and operator!=. */
+
+static void
+test_filtered_iterator_eq ()
+{
+  int array[] = { 4, 4, 5, 6, 7, 8, 9 };
+
+  filtered_iterator<int_array_iterator, even_numbers_only>
+    iter1(array, ARRAY_SIZE (array));
+  filtered_iterator<int_array_iterator, even_numbers_only>
+    iter2(array, ARRAY_SIZE (array));
+
+  /* They start equal.  */
+  gdb_assert (iter1 == iter2);
+  gdb_assert (!(iter1 != iter2));
+
+  /* Advance 1, now they aren't equal (despite pointing to equal values).  */
+  ++iter1;
+  gdb_assert (!(iter1 == iter2));
+  gdb_assert (iter1 != iter2);
+
+  /* Advance 2, now they are equal again.  */
+  ++iter2;
+  gdb_assert (iter1 == iter2);
+  gdb_assert (!(iter1 != iter2));
+}
+
+} /* namespace selftests */
+
+void
+_initialize_filtered_iterator_selftests ()
+{
+  selftests::register_test ("filtered_iterator",
+			    selftests::test_filtered_iterator);
+  selftests::register_test ("filtered_iterator_eq",
+			    selftests::test_filtered_iterator_eq);
+}