[formatters] Add a deque formatter for libstdcpp and fix the libcxx one

[wallace]

Summary

This adds the formatter for libstdcpp's deque as a python
implementation. It adds comprehensive tests for the two different
storage strategies deque uses. Besides that, this fixes a couple of bugs
in the libcxx implementation. Finally, both implementation run against
the same tests.

This is a minor improvement on top of Danil Stefaniuc's formatter.

[danilashtefan]

lldb/examples/synthetic/gnu_libstdcpp.py

60

This method does not currently work. I simply tried to calculate the size from start and finish pointers. When it did not, I investigated further and this was my founding:

This is when we get the iterator value this comes out:

`_Deque_iterator(const _Deque_iterator& __x) noexcept

169 	       : _M_cur(__x._M_cur), _M_first(__x._M_first),
170 		 _M_last(__x._M_last), _M_node(__x._M_node) { }`

And when it++ is done this is what happens behind:

operator++()

189       {
190    ++_M_cur;
191    if (_M_cur == _M_last)
192      {
193        _M_set_node(_M_node + 1);
194        _M_cur = _M_first;
195      }
196    return *this;
197        }

[danilashtefan]

When I mocked the num_children to return 4, formatter works for any structure with size <= 4. here is the example:

std::deque<int> d;
 d.push_front(7);
 d.push_front(5);   
 d.push_front(13);
 d.push_front(25);

(std::deque<int, std::allocator<int> >) $0 = size=4 {

[0] = 25
[1] = 13
[2] = 5
[3] = 7

}

[wallace]

discussed offline how to traverse each individual subarray. This might make it impossible to reuse it for queue and stack

lldb/examples/synthetic/gnu_libstdcpp.py

13

remove

22

remove

31

don't forget to always return False

60

discussed offline how to handle this

[danilashtefan]

Hi Walter :)

I added the size determination here. The commented out set_node node method should switch the nodes, but, unfortunately, after numerous of tries, I did not succeed. The prints are left only for a draft PR and I will delete them in the final diff update, thank you!

[danilashtefan]

Unified tests added

[danilashtefan]

As we discussed offline, I add the print tests, since SBValue.GetValue() doesn't work for complex structures

[labath]

In D114008#3153211, @danilashtefan wrote:

As we discussed offline, I add the print tests, since SBValue.GetValue() doesn't work for complex structures

There are different ways you can do that depending on what you want to test precisely. You can (programatically, using loops?) construct nested ValueCheck structures and pass that to the expect_var_path .

Or you can, issue a bunch of smaller expect_var_path commands targetting individual subobjects, again using loops (expect_var_path("myobj[%d]"%i, ...).

[danilashtefan]

Hi @labath, Thank you so much for your comment and correction. The initial version of the test was the following, with array of ValueCheck objects:

`def check(self, var_name, size):

var = self.findVariable(var_name)
self.assertEqual(var.GetNumChildren(), size)
children = []
for i in range(100):
    children.insert(0,ValueCheck(value={i, i + 1, i + 2}))
    children.append(ValueCheck(value={-i, -(i + 1), -(i + 2)}))
self.expect_var_path(var_name, type=self.getVariableType(var_name), children=children)`

However, the following error pops up in the expected_var_path: AssertionError: {99, 100, 101} != None : Checking child with index 0:. The reason is that child.GetValue()that is invoked inside gives None in case it is a complex structure. This is why me and @wallace decided to go with a printing test.

If I did not get you right, I would be glad if you could describe your solution more, so I can implement it. Many thanks!

[labath]

You need to construct issue appropriately nested ValueCheck objects. Something like this:

children.insert(0,ValueCheck(children=[ValueCheck(value=i), ValueCheck(value=i+1), ValueCheck(i + 2)])

If that doesn't work then that's probably a bug in the ValueCheck matching implementation, as it was definitely written with that mind.

[wallace]

Fix the few issues in Danil's implementation

[wallace]

committed as 2ea3c8a50add5436cf939d59c3235408ca0255c1

lldb/examples/synthetic/gnu_libstdcpp.py

 from __future__ import division
 import re
 import lldb.formatters.Logger
 
 # C++ STL formatters for LLDB
 # These formatters are based upon the version of the GNU libstdc++
 # as it ships with Mac OS X 10.6.8 thru 10.8.0
 # You are encouraged to look at the STL implementation for your platform
 # before relying on these formatters to do the right thing for your setup
 
+class StdDequeSynthProvider:
+    def __init__(self, valobj, d):
+        self.valobj = valobj
+        self.pointer_size = self.valobj.GetProcess().GetAddressByteSize()
+        self.count = None
+        self.block_size = -1
+        self.element_size = -1
+        self.find_block_size()
+ 
+ 
+    def find_block_size(self):
+        # in order to use the deque we must have the block size, or else
+        # it's impossible to know what memory addresses are valid
+        self.element_type = self.valobj.GetType().GetTemplateArgumentType(0)
+        if not self.element_type.IsValid():
+            return
+        self.element_size = self.element_type.GetByteSize()
+        # The block size (i.e. number of elements per subarray) is defined in
+        # this piece of code, so we need to replicate it.
+        #
+        # #define _GLIBCXX_DEQUE_BUF_SIZE 512
+        #
+        # return (__size < _GLIBCXX_DEQUE_BUF_SIZE
+        #   ? size_t(_GLIBCXX_DEQUE_BUF_SIZE / __size) : size_t(1));
+        if self.element_size < 512:
+            self.block_size = 512 // self.element_size
+        else:
+            self.block_size = 1
+ 
+    def num_children(self):
+        if self.count is None:
+            return 0
+        return self.count
+ 
+    def has_children(self):
+        return True
+ 
+    def get_child_index(self, name):
+        try:
+            return int(name.lstrip('[').rstrip(']'))
+        except:
+            return -1
+ 
+    def get_child_at_index(self, index):
+        if index < 0 or self.count is None:
+            return None
+        if index >= self.num_children():
+            return None
+        try:
+            name = '[' + str(index) + ']'
+            # We first look for the element in the first subarray,
+            # which might be incomplete.
+            if index < self.first_node_size:
+                # The following statement is valid because self.first_elem is the pointer
+                # to the first element
+                return self.first_elem.CreateChildAtOffset(name, index * self.element_size, self.element_type)
+ 
+            # Now the rest of the subarrays except for maybe the last one
+            # are going to be complete, so the final expression is simpler
+            i, j = divmod(index - self.first_node_size, self.block_size)
+ 
+            # We first move to the beginning of the node/subarray were our element is
+            node = self.start_node.CreateChildAtOffset(
+                '',
+                (1 + i) * self.valobj.GetProcess().GetAddressByteSize(),
+                self.element_type.GetPointerType())
+            return node.CreateChildAtOffset(name, j * self.element_size, self.element_type)
+ 
+        except:
+            return None
+ 
+    def update(self):
+        logger = lldb.formatters.Logger.Logger()
+        self.count = 0
+        try:
+            # A deque is effectively a two-dim array, with fixed width.
+            # However, only a subset of this memory contains valid data
+            # since a deque may have some slack at the front and back in
+            # order to have O(1) insertion at both ends.
+            # The rows in active use are delimited by '_M_start' and
+            # '_M_finish'.
+            #
+            # To find the elements that are actually constructed, the 'start'
+            # variable tells which element in this NxM array is the 0th
+            # one.
+            if self.block_size < 0 or self.element_size < 0:
+                return False
+ 
+            count = 0
+ 
+            impl = self.valobj.GetChildMemberWithName('_M_impl')
+ 
+            # we calculate the size of the first node (i.e. first internal array)
+            self.start = impl.GetChildMemberWithName('_M_start')
+            self.start_node = self.start.GetChildMemberWithName('_M_node')
+            first_node_address = self.start_node.GetValueAsUnsigned(0)
+            first_node_last_elem = self.start.GetChildMemberWithName('_M_last').GetValueAsUnsigned(0)
+            self.first_elem = self.start.GetChildMemberWithName('_M_cur')
+            first_node_first_elem = self.first_elem.GetValueAsUnsigned(0)
+ 
+ 
+            finish = impl.GetChildMemberWithName('_M_finish')
+            last_node_address = finish.GetChildMemberWithName('_M_node').GetValueAsUnsigned(0)
+            last_node_first_elem = finish.GetChildMemberWithName('_M_first').GetValueAsUnsigned(0)
+            last_node_last_elem = finish.GetChildMemberWithName('_M_cur').GetValueAsUnsigned(0)
+ 
+            if first_node_first_elem == 0 or first_node_last_elem == 0 or first_node_first_elem > first_node_last_elem:
+                return False
+            if last_node_first_elem == 0 or last_node_last_elem == 0 or last_node_first_elem > last_node_last_elem:
+                return False
+ 
+ 
+            if last_node_address == first_node_address:
+                self.first_node_size = (last_node_last_elem - first_node_first_elem) // self.element_size
+                count += self.first_node_size
+            else:
+                self.first_node_size = (first_node_last_elem - first_node_first_elem) // self.element_size
+                count += self.first_node_size
+ 
+                # we calculate the size of the last node
+                finish = impl.GetChildMemberWithName('_M_finish')
+                last_node_address = finish.GetChildMemberWithName('_M_node').GetValueAsUnsigned(0)
+                count += (last_node_last_elem - last_node_first_elem) // self.element_size
+ 
+                # we calculate the size of the intermediate nodes
+                num_intermediate_nodes = (last_node_address - first_node_address - 1) // self.valobj.GetProcess().GetAddressByteSize()
+                count += self.block_size * num_intermediate_nodes
+            self.count = count
+        except:
+            pass
+        return False
 
 class AbstractListSynthProvider:
     def __init__(self, valobj, dict, has_prev):
         '''
         :param valobj: The value object of the list
         :param dict: A dict with metadata provided by LLDB
         :param has_prev: Whether the list supports a 'prev' pointer besides a 'next' one
         '''

lldb/source/Plugins/Language/CPlusPlus/CPlusPlusLanguage.cpp

cpp_category_sp->GetRegexTypeSyntheticsContainer()->Add(
           stl_deref_flags,
           "lldb.formatters.cpp.gnu_libstdcpp.StdMapLikeSynthProvider")));
   cpp_category_sp->GetRegexTypeSyntheticsContainer()->Add(
       RegularExpression("^std::multiset<.+> >(( )?&)?$"),
       SyntheticChildrenSP(new ScriptedSyntheticChildren(
           stl_deref_flags,
           "lldb.formatters.cpp.gnu_libstdcpp.StdMapLikeSynthProvider")));
   cpp_category_sp->GetRegexTypeSyntheticsContainer()->Add(
+      RegularExpression("^std::deque<.+>(( )?&)?$"),
+      SyntheticChildrenSP(new ScriptedSyntheticChildren(
+          stl_deref_flags,
+          "lldb.formatters.cpp.gnu_libstdcpp.StdDequeSynthProvider")));
+  cpp_category_sp->GetRegexTypeSyntheticsContainer()->Add(
       RegularExpression("^std::(__cxx11::)?list<.+>(( )?&)?$"),
       SyntheticChildrenSP(new ScriptedSyntheticChildren(
           stl_synth_flags,
           "lldb.formatters.cpp.gnu_libstdcpp.StdListSynthProvider")));
   cpp_category_sp->GetRegexTypeSyntheticsContainer()->Add(
       RegularExpression("^std::(__cxx11::)?forward_list<.+>(( )?&)?$"),
       SyntheticChildrenSP(new ScriptedSyntheticChildren(
           stl_synth_flags,
cpp_category_sp->GetRegexTypeSummariesContainer()->Add(
       RegularExpression("^std::map<.+> >(( )?&)?$"),
       TypeSummaryImplSP(
           new StringSummaryFormat(stl_summary_flags, "size=${svar%#}")));
   cpp_category_sp->GetRegexTypeSummariesContainer()->Add(
       RegularExpression("^std::set<.+> >(( )?&)?$"),
       TypeSummaryImplSP(
           new StringSummaryFormat(stl_summary_flags, "size=${svar%#}")));
   cpp_category_sp->GetRegexTypeSummariesContainer()->Add(
+      RegularExpression("^std::deque<.+>(( )?&)?$"),
+      TypeSummaryImplSP(
+          new StringSummaryFormat(stl_summary_flags, "size=${svar%#}")));
+  cpp_category_sp->GetRegexTypeSummariesContainer()->Add(
       RegularExpression("^std::multimap<.+> >(( )?&)?$"),
       TypeSummaryImplSP(
           new StringSummaryFormat(stl_summary_flags, "size=${svar%#}")));
   cpp_category_sp->GetRegexTypeSummariesContainer()->Add(
       RegularExpression("^std::multiset<.+> >(( )?&)?$"),
       TypeSummaryImplSP(
           new StringSummaryFormat(stl_summary_flags, "size=${svar%#}")));
   cpp_category_sp->GetRegexTypeSummariesContainer()->Add(

lldb/test/API/functionalities/data-formatter/data-formatter-stl/generic/deque/Makefile

+CXX_SOURCES := main.cpp
+
+include Makefile.rules

lldb/test/API/functionalities/data-formatter/data-formatter-stl/generic/deque/TestDataFormatterGenericDeque.py

+import lldb
+from lldbsuite.test.decorators import *
+from lldbsuite.test.lldbtest import *
+from lldbsuite.test import lldbutil
+
+USE_LIBSTDCPP = "USE_LIBSTDCPP"
+USE_LIBCPP = "USE_LIBCPP"
+
+class GenericDequeDataFormatterTestCase(TestBase):
+
+    mydir = TestBase.compute_mydir(__file__)
+
+    def findVariable(self, name):
+        var = self.frame().FindVariable(name)
+        self.assertTrue(var.IsValid())
+        return var
+
+    def getVariableType(self, name):
+        var = self.findVariable(name)
+        return var.GetType().GetDisplayTypeName()
+
+    def check(self, var_name, size):
+        var = self.findVariable(var_name)
+        self.assertEqual(var.GetNumChildren(), size)
+        children = []
+        for i in range(size):
+            child = var.GetChildAtIndex(i)
+            children.append(ValueCheck(value=child.GetValue()))
+        self.expect_var_path(var_name, type=self.getVariableType(var_name), children=children)
+
+    def do_test(self, stdlib_type):
+        self.build()
+        lldbutil.run_to_source_breakpoint(self, "break here",
+                                          lldb.SBFileSpec("main.cpp"))
+
+        self.expect_expr("empty", result_children=[])
+        self.expect_expr("deque_1", result_children=[
+            ValueCheck(name="[0]", value="1"),
+        ])
+        self.expect_expr("deque_3", result_children=[
+            ValueCheck(name="[0]", value="3"),
+            ValueCheck(name="[1]", value="1"),
+            ValueCheck(name="[2]", value="2")
+        ])
+
+        self.check("deque_200_small", 200)
+        self.check("deque_200_large", 200)
+    
+    @add_test_categories(["libstdcxx"])
+    def test_libstdcpp(self):
+        self.do_test(USE_LIBSTDCPP)
+
+    @add_test_categories(["libc++"])
+    def test_libcpp(self):
+         self.do_test(USE_LIBCPP)
 No newline at end of file

lldb/test/API/functionalities/data-formatter/data-formatter-stl/generic/deque/main.cpp

+#include <deque>
+
+struct Foo_small {
+  int a;
+  int b;
+  int c;
+
+  Foo_small(int a, int b, int c) : a(a), b(b), c(c) {}
+};
+
+struct Foo_large {
+  int a;
+  int b;
+  int c;
+  char d[1000] = {0};
+
+  Foo_large(int a, int b, int c) : a(a), b(b), c(c) {}
+};
+
+template <typename T> T fill(T deque) {
+  for (int i = 0; i < 100; i++) {
+    deque.push_back({i, i + 1, i + 2});
+    deque.push_front({-i, -(i + 1), -(i + 2)});
+  }
+  return deque;
+}
+
+int main() {
+  std::deque<int> empty;
+  std::deque<int> deque_1 = {1};
+  std::deque<int> deque_3 = {3, 1, 2};
+
+  std::deque<Foo_small> deque_200_small;
+  deque_200_small = fill<std::deque<Foo_small>>(deque_200_small);
+
+  std::deque<Foo_large> deque_200_large;
+  deque_200_large = fill<std::deque<Foo_large>>(deque_200_large);
+
+  return empty.size() + deque_1.front() + deque_3.front(); // break here
+}