[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

180

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

133

remove

142

remove

151

don't forget to always return False

180

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

def num_children_impl(self):
             count = self.head.GetChildMemberWithName('_M_element_count').GetValueAsUnsigned(0)
             return count
         except:
             logger >> "Could not determine the size"
             return 0
 
 
 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
         '''
         logger = lldb.formatters.Logger.Logger()
         self.valobj = valobj
         self.count = None
         self.has_prev = has_prev
         self.list_capping_size = self.valobj.GetTarget().GetMaximumNumberOfChildrenToDisplay()
         logger >> "Providing synthetic children for a list named " + \
             str(valobj.GetName())
 
     def next_node(self, node):
         logger = lldb.formatters.Logger.Logger()
         return node.GetChildMemberWithName('_M_next')
 
     def is_valid(self, node):
         logger = lldb.formatters.Logger.Logger()
         valid = self.value(self.next_node(node)) != self.get_end_of_list_address()
         if valid:
             logger >> "%s is valid" % str(self.valobj.GetName())
         else:
             logger >> "synthetic value is not valid"
         return valid
 
def has_loop(self):
         if not _list_uses_loop_detector:
             logger >> "Asked not to use loop detection"
             return False
         slow = self.next
         fast1 = self.next
         fast2 = self.next
         while self.is_valid(slow):
             slow_value = self.value(slow)
             fast1 = self.next_node(fast2)
             fast2 = self.next_node(fast1)
             if self.value(fast1) == slow_value or self.value(
                     fast2) == slow_value:
                 return True
             slow = self.next_node(slow)
         return False
 
     def num_children(self):
def increment_node(self, node):
             if self.node_ptr_value(self.right(x)) != self.node_ptr_value(y):
                 x = y
             return x
 
     def has_children(self):
         return True
 
 _list_uses_loop_detector = True
+
+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

lldb/examples/synthetic/libcxx.py

def find_block_size(self):
         self.element_type = self.valobj.GetType().GetTemplateArgumentType(0)
         self.element_size = self.element_type.GetByteSize()
         # The code says this, but there must be a better way:
         # template <class _Tp, class _Allocator>
         # class __deque_base {
         #    static const difference_type __block_size = sizeof(value_type) < 256 ? 4096 / sizeof(value_type) : 16;
         # }
         if self.element_size < 256:
-            self.block_size = 4096 / self.element_size
+            self.block_size = 4096 // self.element_size
         else:
             self.block_size = 16
 
     def num_children(self):
-        global _deque_capping_size
         logger = lldb.formatters.Logger.Logger()
         if self.count is None:
             return 0
-        return min(self.count, _deque_capping_size)
+        return self.count
 
     def has_children(self):
         return True
 
     def get_child_index(self, name):
         logger = lldb.formatters.Logger.Logger()
         try:
             return int(name.lstrip('[').rstrip(']'))
         except:
             return -1
 
     def get_child_at_index(self, index):
         logger = lldb.formatters.Logger.Logger()
         logger.write("Fetching child " + str(index))
         if index < 0 or self.count is None:
             return None
         if index >= self.num_children():
             return None
         try:
             i, j = divmod(self.start + index, self.block_size)
+
             return self.first.CreateValueFromExpression(
                 '[' + str(index) + ']', '*(*(%s + %d) + %d)' %
-                (self.first.get_expr_path(), i, j))
+                (self.map_begin.get_expr_path(), i, j))
         except:
             return None
 
     def _get_value_of_compressed_pair(self, pair):
         value = pair.GetChildMemberWithName("__value_")
         if not value.IsValid():
             # pre-r300140 member name
             value = pair.GetChildMemberWithName("__first_")
def update(self):
             if self.block_size < 0:
                 logger.write("block_size < 0")
                 return
             map_ = self.valobj.GetChildMemberWithName('__map_')
             start = self.valobj.GetChildMemberWithName(
                 '__start_').GetValueAsUnsigned(0)
             first = map_.GetChildMemberWithName('__first_')
             map_first = first.GetValueAsUnsigned(0)
-            map_begin = map_.GetChildMemberWithName(
-                '__begin_').GetValueAsUnsigned(0)
+            self.map_begin = map_.GetChildMemberWithName(
+                '__begin_')
+            map_begin = self.map_begin.GetValueAsUnsigned(0)
             map_end = map_.GetChildMemberWithName(
                 '__end_').GetValueAsUnsigned(0)
             map_endcap = self._get_value_of_compressed_pair(
                     map_.GetChildMemberWithName( '__end_cap_'))
+
             # check consistency
             if not map_first <= map_begin <= map_end <= map_endcap:
                 logger.write("map pointers are not monotonic")
                 return
             total_rows, junk = divmod(
                 map_endcap - map_first, self.pointer_size)
             if junk:
                 logger.write("endcap-first doesnt align correctly")
                 return
             active_rows, junk = divmod(map_end - map_begin, self.pointer_size)
             if junk:
                 logger.write("end-begin doesnt align correctly")
                 return
             start_row, junk = divmod(map_begin - map_first, self.pointer_size)
             if junk:
                 logger.write("begin-first doesnt align correctly")
                 return
-            if not start_row * \
-                    self.block_size <= start < (start_row + 1) * self.block_size:
-                logger.write("0th element must be in the 'begin' row")
-                return
-            end_row = start_row + active_rows
-            if not count:
-                if active_rows:
-                    logger.write("empty deque but begin!=end")
-                    return
-            elif not (end_row - 1) * self.block_size <= start + count < end_row * self.block_size:
-                logger.write("nth element must be before the 'end' row")
-                return
+
             logger.write(
                 "update success: count=%r, start=%r, first=%r" %
                 (count, start, first))
             # if consistent, save all we really need:
             self.count = count
             self.start = start
             self.first = first
         except:
             self.count = None
             self.start = None
             self.map_first = None
             self.map_begin = None
+        return False
 
 
 class stdsharedptr_SynthProvider:
 
     def __init__(self, valobj, d):
         logger = lldb.formatters.Logger.Logger()
         logger.write("init")
         self.valobj = valobj
debugger.HandleCommand(
         'type synthetic add -l libcxx.stdsharedptr_SynthProvider -x "^(std::__1::)shared_ptr<.+>$" -w libcxx')
     # turns out the structs look the same, so weak_ptr can be handled the same!
     debugger.HandleCommand(
         'type synthetic add -l libcxx.stdsharedptr_SynthProvider -x "^(std::__1::)weak_ptr<.+>$" -w libcxx')
 
 _map_capping_size = 255
 _list_capping_size = 255
 _list_uses_loop_detector = True
-_deque_capping_size = 255

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

cpp_category_sp->GetRegexTypeSyntheticsContainer()->Add(
           stl_synth_flags,
           "lldb.formatters.cpp.gnu_libstdcpp.StdVectorSynthProvider")));
   cpp_category_sp->GetRegexTypeSyntheticsContainer()->Add(
       RegularExpression("^std::map<.+> >(( )?&)?$"),
       SyntheticChildrenSP(new ScriptedSyntheticChildren(
           stl_synth_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::set<.+> >(( )?&)?$"),
       SyntheticChildrenSP(new ScriptedSyntheticChildren(
           stl_deref_flags,
           "lldb.formatters.cpp.gnu_libstdcpp.StdMapLikeSynthProvider")));
   cpp_category_sp->GetRegexTypeSyntheticsContainer()->Add(
       RegularExpression("^std::multimap<.+> >(( )?&)?$"),
       SyntheticChildrenSP(new ScriptedSyntheticChildren(
           stl_deref_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
 
-USE_LIBCPP := 1
-
 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_size(self, var_name, size):
+        var = self.findVariable(var_name)
+        self.assertEqual(var.GetNumChildren(), size)
+
+
+    def do_test(self, stdlib_type):
+        self.build(dictionary={stdlib_type: '1'})
+        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_size("deque_200_small", 200)
+        for i in range(0, 100):
+            self.expect_var_path("deque_200_small[%d]"%(i), children=[
+                ValueCheck(name="a", value=str(-99 + i)),
+                ValueCheck(name="b", value=str(-100 + i)),
+                ValueCheck(name="c", value=str(-101 + i)),
+            ])
+            self.expect_var_path("deque_200_small[%d]"%(i + 100), children=[
+                ValueCheck(name="a", value=str(i)),
+                ValueCheck(name="b", value=str(1 + i)),
+                ValueCheck(name="c", value=str(2 + i)),
+            ])
+
+        self.check_size("deque_200_large", 200)
+        for i in range(0, 100):
+            self.expect_var_path("deque_200_large[%d]"%(i), children=[
+                ValueCheck(name="a", value=str(-99 + i)),
+                ValueCheck(name="b", value=str(-100 + i)),
+                ValueCheck(name="c", value=str(-101 + i)),
+                ValueCheck(name="d")
+            ])
+            self.expect_var_path("deque_200_large[%d]"%(i + 100), children=[
+                ValueCheck(name="a", value=str(i)),
+                ValueCheck(name="b", value=str(1 + i)),
+                ValueCheck(name="c", value=str(2 + i)),
+                ValueCheck(name="d")
+            ])
+
+    @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)

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

+#include <cstdio>
+#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
+}

lldb/test/API/functionalities/data-formatter/data-formatter-stl/libcxx/deque/TestDataFormatterLibcxxDeque.py

-import lldb
-from lldbsuite.test.decorators import *
-from lldbsuite.test.lldbtest import *
-from lldbsuite.test import lldbutil
-
-
-class LibcxxDequeDataFormatterTestCase(TestBase):
-
-    mydir = TestBase.compute_mydir(__file__)
-
-    @add_test_categories(["libc++"])
-    def test(self):
-        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")
-        ])

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

-#include <deque>
-
-int main() {
-  std::deque<int> empty;
-  std::deque<int> deque_1 = {1};
-  std::deque<int> deque_3 = {3, 1, 2};
-  return empty.size() + deque_1.front() + deque_3.front(); // break here
-}