[DataFormatters] Make libc++ list loop detection linear

Summary:
Loop detection code is being called before every element access. Although it tries to cache some
of the data by remembering the loop-free initial segment, every time it needs to increase this
segment, it will start from scratch. For the typical usage pattern, where one accesses the
elements in order, the loop detection will need to be run after every access, resulting in
quadratic behavior. This behavior is noticable even for the default 255 element limit.

In this commit, I rewrite the algorithm to be truly incremental -- it maintains the state of its
loop-detection runners between calls, and reuses them when it needs to check another segment.
This way, each part of the list is scanned only once, resulting in linear behavior.

Also note that I have changed the operator== of ListEntry to do the comparison based on the
value() function (instead of relying on ValueObjectSP equality). In my experiments, I kept
getting different ValueObjectSPs when going through the same element twice.

Reviewers: granata.enrico

Subscribers: lldb-commits, sivachandra

Differential Revision: http://reviews.llvm.org/D13902

llvm-svn: 250890

3 files changed, 91 insertions, 0 deletions

diff --git a/lldb/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/Makefile b/lldb/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/Makefile
new file mode 100644
index 00000000000..a5dabdb6349
--- /dev/null
+++ b/lldb/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/Makefile
@@ -0,0 +1,7 @@
+LEVEL = ../../../../../../make
+
+CXX_SOURCES := main.cpp
+
+USE_LIBCPP := 1
+include $(LEVEL)/Makefile.rules
+CXXFLAGS += -O0
diff --git a/lldb/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/TestDataFormatterLibcxxListLoop.py b/lldb/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/TestDataFormatterLibcxxListLoop.py
new file mode 100644
index 00000000000..f89369c4c19
--- /dev/null
+++ b/lldb/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/TestDataFormatterLibcxxListLoop.py
@@ -0,0 +1,56 @@
+"""
+Test that the debugger handles loops in std::list (which can appear as a result of e.g. memory
+corruption).
+"""
+
+import os, time, re
+import unittest2
+import lldb
+from lldbtest import *
+import lldbutil
+
+class LibcxxListDataFormatterTestCase(TestBase):
+
+    mydir = TestBase.compute_mydir(__file__)
+
+    @skipIfGcc
+    @skipIfWindows # libc++ not ported to Windows yet
+    def test_with_run_command(self):
+        self.build()
+        exe = os.path.join(os.getcwd(), "a.out")
+        target = self.dbg.CreateTarget(exe)
+        self.assertTrue(target and target.IsValid(), "Target is valid")
+
+        file_spec = lldb.SBFileSpec ("main.cpp", False)
+        breakpoint1 = target.BreakpointCreateBySourceRegex('// Set break point at this line.', file_spec)
+        self.assertTrue(breakpoint1 and breakpoint1.IsValid())
+        breakpoint2 = target.BreakpointCreateBySourceRegex('// Set second break point at this line.', file_spec)
+        self.assertTrue(breakpoint2 and breakpoint2.IsValid())
+
+        # Run the program, it should stop at breakpoint 1.
+        process = target.LaunchSimple(None, None, self.get_process_working_directory())
+        lldbutil.skip_if_library_missing(self, target, lldbutil.PrintableRegex("libc\+\+"))
+        self.assertTrue(process and process.IsValid(), PROCESS_IS_VALID)
+        self.assertEquals(len(lldbutil.get_threads_stopped_at_breakpoint(process, breakpoint1)), 1)
+
+        # verify our list is displayed correctly
+        self.expect("frame variable *numbers_list", substrs=['[0] = 1', '[1] = 2', '[2] = 3', '[3] = 4', '[5] = 6'])
+
+        # Continue to breakpoint 2.
+        process.Continue()
+        self.assertTrue(process and process.IsValid(), PROCESS_IS_VALID)
+        self.assertEquals(len(lldbutil.get_threads_stopped_at_breakpoint(process, breakpoint2)), 1)
+
+        # The list is now inconsistent. However, we should be able to get the first three
+        # elements at least (and most importantly, not crash).
+        self.expect("frame variable *numbers_list", substrs=['[0] = 1', '[1] = 2', '[2] = 3'])
+
+        # Run to completion.
+        process.Continue()
+        self.assertEqual(process.GetState(), lldb.eStateExited, PROCESS_EXITED)
+
+if __name__ == '__main__':
+    import atexit
+    lldb.SBDebugger.Initialize()
+    atexit.register(lambda: lldb.SBDebugger.Terminate())
+    unittest2.main()
diff --git a/lldb/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/main.cpp b/lldb/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/main.cpp
new file mode 100644
index 00000000000..8b872398d4e
--- /dev/null
+++ b/lldb/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/main.cpp
@@ -0,0 +1,28 @@
+// Evil hack: To simulate memory corruption, we want to fiddle with some internals of std::list.
+// Make those accessible to us.
+#define private public
+#define protected public
+
+#ifdef _LIBCPP_INLINE_VISIBILITY
+#undef _LIBCPP_INLINE_VISIBILITY
+#endif
+#define _LIBCPP_INLINE_VISIBILITY
+#include <list>
+
+#include <assert.h>
+
+typedef std::list<int> int_list;
+
+int main()
+{
+    int_list *numbers_list = new int_list{1,2,3,4,5,6,7,8,9,10};
+
+    auto *third_elem = numbers_list->__end_.__next_->__next_->__next_; // Set break point at this line.
+    assert(third_elem->__value_ == 3);
+    auto *fifth_elem = third_elem->__next_->__next_;
+    assert(fifth_elem->__value_ == 5);
+    fifth_elem->__next_ = third_elem;
+
+    // Any attempt to free the list will probably crash the program. Let's just leak it.
+    return 0; // Set second break point at this line.
+}