Add logical_die_tree_iteratorpmachata/iterators

5 files changed, 270 insertions, 9 deletions

diff --git a/libdw/Makefile.am b/libdw/Makefile.am
index 43e83b58..2d1f3001 100644
--- a/libdw/Makefile.am
+++ b/libdw/Makefile.am
@@ -107,6 +107,7 @@ libdw_a_SOURCES = dwarf_begin.c dwarf_begin_elf.c dwarf_end.c dwarf_getelf.c \
 
 if HAVE_CXX
 libdwpp_a_SOURCES = c++/unit_iterator.cc c++/die_tree_iterator.cc	\
+		    c++/logical_die_tree_iterator.cc			\
 		    c++/child_iterator.cc c++/attr_iterator.cc
 endif
 
diff --git a/libdw/c++/libdw b/libdw/c++/libdw
index e9bd4bb2..b4a99f5d 100644
--- a/libdw/c++/libdw
+++ b/libdw/c++/libdw
@@ -208,6 +208,43 @@ namespace v1
   // returned stack is the CU DIE, the last one the current DIE.
   std::vector <Dwarf_Die> path_from_root (die_tree_iterator &it);
 
+  class logical_die_tree_iterator
+    : public std::iterator <std::input_iterator_tag, Dwarf_Die>
+  {
+    // m_stack.last is the current iterator, the rest is import
+    // history.
+    std::vector <std::pair <die_tree_iterator, die_tree_iterator> > m_stack;
+
+    struct end_it {};
+    logical_die_tree_iterator (end_it);
+
+    bool move ();
+
+  public:
+    logical_die_tree_iterator (Dwarf *dw);
+    logical_die_tree_iterator (unit_iterator const &cuit);
+
+    static logical_die_tree_iterator end ();
+
+    bool operator== (logical_die_tree_iterator const &that) const;
+    bool operator!= (logical_die_tree_iterator const &that) const;
+
+    logical_die_tree_iterator &operator++ ();
+    logical_die_tree_iterator operator++ (int);
+
+    // N.B. see top of the file for explanation of non-constness of
+    // operators * and ->.
+
+    Dwarf_Die &operator* ();
+    Dwarf_Die *operator-> ();
+
+    // Return a logical_die_tree_iterator referencing a parent of a
+    // DIE that this iterator points at.  Returns an end iterator if
+    // there is no parent.  Technically a const, but can't be one due
+    // to dwarf_tag call inside.
+    logical_die_tree_iterator parent ();
+  };
+
   // An attribute iterator goes through attributes of a given DIE.
   class attr_iterator
     : public std::iterator <std::input_iterator_tag, Dwarf_Attribute>
diff --git a/libdw/c++/logical_die_tree_iterator.cc b/libdw/c++/logical_die_tree_iterator.cc
new file mode 100644
index 00000000..0aec755a
--- /dev/null
+++ b/libdw/c++/logical_die_tree_iterator.cc
@@ -0,0 +1,156 @@
+/* -*-c++-*-
+   Copyright (C) 2015 Red Hat, Inc.
+   This file is part of elfutils.
+
+   This file is free software; you can redistribute it and/or modify
+   it under the terms of either
+
+     * the GNU Lesser General Public License as published by the Free
+       Software Foundation; either version 3 of the License, or (at
+       your option) any later version
+
+   or
+
+     * the GNU General Public License as published by the Free
+       Software Foundation; either version 2 of the License, or (at
+       your option) any later version
+
+   or both in parallel, as here.
+
+   elfutils 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 copies of the GNU General Public License and
+   the GNU Lesser General Public License along with this program.  If
+   not, see <http://www.gnu.org/licenses/>.  */
+
+#ifdef HAVE_CONFIG_H
+# include <config.h>
+#endif
+
+#include <dwarf.h>
+
+#include "libdw"
+#include "libdwP.hh"
+
+namespace
+{
+  bool
+  advance (std::pair <elfutils::v1::die_tree_iterator,
+		      elfutils::v1::die_tree_iterator> &p)
+  {
+    return ++p.first != p.second;
+  }
+}
+
+attribute_hidden
+bool
+elfutils::v1::logical_die_tree_iterator::move ()
+{
+  while (true)
+    if (m_stack.empty ())
+      return false;
+    else if (advance (m_stack.back ()))
+      {
+	Dwarf_Die &die = **this;
+	Dwarf_Attribute at_import;
+	Dwarf_Die cudie;
+	if (dwarf_tag (&die) == DW_TAG_imported_unit
+	    && dwarf_hasattr (&die, DW_AT_import)
+	    && dwarf_attr (&die, DW_AT_import, &at_import) != NULL
+	    && dwarf_formref_die (&at_import, &cudie) != NULL)
+	  {
+	    unit_iterator uit_end (dwarf_cu_getdwarf (cudie.cu), cudie);
+	    unit_iterator uit = uit_end++;
+	    m_stack.push_back (std::make_pair (die_tree_iterator (uit),
+					       die_tree_iterator (uit_end)));
+	    // Now m_stack.back() references a CU DIE.  Go around once
+	    // more to advance to the first child.  If there is none,
+	    // it will get popped again and the whole process continues.
+	  }
+	else
+	  return true;
+      }
+    else
+      m_stack.pop_back ();
+}
+
+elfutils::v1::logical_die_tree_iterator::logical_die_tree_iterator (end_it)
+{}
+
+elfutils::v1::logical_die_tree_iterator::logical_die_tree_iterator (Dwarf *dw)
+{
+  die_tree_iterator it = die_tree_iterator (dw);
+  if (it != die_tree_iterator::end ())
+    m_stack.push_back (std::make_pair (it, die_tree_iterator::end ()));
+}
+
+elfutils::v1::logical_die_tree_iterator
+	::logical_die_tree_iterator (unit_iterator const &cuit)
+{
+  die_tree_iterator it = die_tree_iterator (cuit);
+  if (it != die_tree_iterator::end ())
+    m_stack.push_back (std::make_pair (it, die_tree_iterator::end ()));
+}
+
+elfutils::v1::logical_die_tree_iterator
+elfutils::v1::logical_die_tree_iterator::end ()
+{
+  return logical_die_tree_iterator (end_it ());
+}
+
+bool
+elfutils::v1::logical_die_tree_iterator
+	::operator== (logical_die_tree_iterator const &that) const
+{
+  return m_stack == that.m_stack;
+}
+
+bool
+elfutils::v1::logical_die_tree_iterator
+	::operator!= (logical_die_tree_iterator const &that) const
+{
+  return ! (*this == that);
+}
+
+
+elfutils::v1::logical_die_tree_iterator &
+elfutils::v1::logical_die_tree_iterator::operator++ ()
+{
+  assert (! m_stack.empty ());
+
+  if (! move ())
+    *this = end ();
+
+  return *this;
+}
+
+elfutils::v1::logical_die_tree_iterator
+elfutils::v1::logical_die_tree_iterator::operator++ (int)
+{
+  logical_die_tree_iterator ret = *this;
+  ++*this;
+  return ret;
+}
+
+Dwarf_Die &
+elfutils::v1::logical_die_tree_iterator::operator* ()
+{
+  assert (! m_stack.empty ());
+  return *m_stack.back ().first;
+}
+
+Dwarf_Die *
+elfutils::v1::logical_die_tree_iterator::operator-> ()
+{
+  return &**this;
+}
+
+elfutils::v1::logical_die_tree_iterator
+elfutils::v1::logical_die_tree_iterator::parent ()
+{
+  // XXX
+  assert (! "implement me");
+}
diff --git a/tests/run-test-iterators.sh b/tests/run-test-iterators.sh
index 69425704..39681f72 100755
--- a/tests/run-test-iterators.sh
+++ b/tests/run-test-iterators.sh
@@ -17,13 +17,19 @@
 
 . $srcdir/test-subr.sh
 
-testfiles testfile39 testfile-debug-types
+testfiles testfile39 testfile-debug-types testfile_multi_main testfile_multi.dwz
 
 testrun_compare ${abs_top_builddir}/tests/test-iterators testfile39 <<\EOF
 0xb
 0x9e
 0x135
 0x1c8
+--- raw ---
+0 7
+0 7
+0 7
+0 7
+--- logical ---
 0 7
 0 7
 0 7
@@ -34,6 +40,21 @@ testrun_compare ${abs_top_builddir}/tests/test-iterators testfile-debug-types <<
 0xb
 0x17
 0x5a
+--- raw ---
+4 6
+0 9
+0 3
+0 6
+0 6
+2 3
+1 4
+0 2
+0 5
+1 3
+2 4
+0 3
+0 5
+--- logical ---
 4 6
 0 9
 0 3
@@ -49,4 +70,39 @@ testrun_compare ${abs_top_builddir}/tests/test-iterators testfile-debug-types <<
 0 5
 EOF
 
+testrun_compare ${abs_top_builddir}/tests/test-iterators testfile_multi_main <<\EOF
+0xb
+--- raw ---
+4 7
+0 1
+0 2
+3 11
+0 5
+0 5
+0 5
+0 2
+--- logical ---
+4 7
+0 3
+0 3
+0 3
+0 3
+0 3
+0 3
+0 3
+0 3
+0 3
+0 3
+2 5
+0 5
+0 5
+0 2
+0 2
+3 11
+0 5
+0 5
+0 5
+0 2
+EOF
+
 exit 0
diff --git a/tests/test-iterators.cc b/tests/test-iterators.cc
index 987bc6af..5e89cf84 100644
--- a/tests/test-iterators.cc
+++ b/tests/test-iterators.cc
@@ -28,6 +28,19 @@
 #include "../libdw/c++/libdwP.hh"
 #include "../libdwfl/c++/libdwflP.hh"
 
+template <class T>
+void
+traverse_tree (T const &begin, T const &end)
+{
+  for (T it = begin; it != end; ++it)
+    std::cerr << std::dec
+	      << std::distance (elfutils::child_iterator (*it),
+				elfutils::child_iterator::end ()) << ' '
+	      << std::distance (elfutils::attr_iterator (&*it),
+				elfutils::attr_iterator::end ())
+	      << std::endl;
+}
+
 int
 main (int, char *argv[])
 {
@@ -73,14 +86,12 @@ main (int, char *argv[])
       assert (elfutils::die_tree_iterator (elfutils::unit_iterator::end ())
 	      == elfutils::die_tree_iterator::end ());
 
-      for (elfutils::die_tree_iterator it (dw);
-	   it != elfutils::die_tree_iterator::end (); ++it)
-	std::cerr << std::dec
-		  << std::distance (elfutils::child_iterator (*it),
-				    elfutils::child_iterator::end ()) << ' '
-		  << std::distance (elfutils::attr_iterator (&*it),
-				    elfutils::attr_iterator::end ())
-		  << std::endl;
+      std::cerr << "--- raw ---\n";
+      traverse_tree (elfutils::die_tree_iterator (dw),
+		     elfutils::die_tree_iterator::end ());
+      std::cerr << "--- logical ---\n";
+      traverse_tree (elfutils::logical_die_tree_iterator (dw),
+		     elfutils::logical_die_tree_iterator::end ());
     }
 
   dwfl_end (dwfl);