lldb/examples/synthetic/gnu_libstdcpp.py

   1 import lldb.formatters.Logger
   2
   3 # C++ STL formatters for LLDB
   4 # As there are many versions of the libstdc++, you are encouraged to look at the STL
   5 # implementation for your platform before relying on these formatters to do the right
   6 # thing for your setup
   7
   8 def ForwardListSummaryProvider(valobj, dict):
   9     list_capping_size = valobj.GetTarget().GetMaximumNumberOfChildrenToDisplay()
  10     text = "size=" + str(valobj.GetNumChildren())
  11     if valobj.GetNumChildren() > list_capping_size:
  12         return "(capped) " + text
  13     else:
  14         return text
  15
  16 def StdOptionalSummaryProvider(valobj, dict):
  17     has_value = valobj.GetNumChildren() > 0
  18     # We add wrapping spaces for consistency with the libcxx formatter
  19     return " Has Value=" + ("true" if has_value else "false") + " "
  20
  21
  22 class StdOptionalSynthProvider:
  23     def __init__(self, valobj, dict):
  24         self.valobj = valobj
  25
  26     def update(self):
  27         try:
  28             self.payload = self.valobj.GetChildMemberWithName('_M_payload')
  29             self.value = self.payload.GetChildMemberWithName('_M_payload')
  30             self.has_value = self.payload.GetChildMemberWithName('_M_engaged').GetValueAsUnsigned(0) != 0
  31         except:
  32             self.has_value = False
  33         return False
  34
  35
  36     def num_children(self):
  37         return 1 if self.has_value else 0
  38
  39     def get_child_index(self, name):
  40         return 0
  41
  42     def get_child_at_index(self, index):
  43         # some versions of libstdcpp have an additional _M_value child with the actual value
  44         possible_value = self.value.GetChildMemberWithName('_M_value')
  45         if possible_value.IsValid():
  46             return possible_value.Clone('Value')
  47         return self.value.Clone('Value')
  48
  49 """
  50  This formatter can be applied to all
  51  unordered map-like structures (unordered_map, unordered_multimap, unordered_set, unordered_multiset)
  52 """
  53 class StdUnorderedMapSynthProvider:
  54     def __init__(self, valobj, dict):
  55         self.valobj = valobj
  56         self.count = None
  57         self.kind = self.get_object_kind(valobj)
  58
  59     def get_object_kind(self, valobj):
  60         type_name = valobj.GetTypeName()
  61         return "set" if "set" in type_name else "map"
  62
  63     def extract_type(self):
  64         type = self.valobj.GetType()
  65         # type of std::pair<key, value> is the first template
  66         # argument type of the 4th template argument to std::map and
  67         # 3rd template argument for std::set. That's why
  68         # we need to know kind of the object
  69         template_arg_num = 4 if self.kind == "map" else 3
  70         allocator_type = type.GetTemplateArgumentType(template_arg_num)
  71         data_type = allocator_type.GetTemplateArgumentType(0)
  72         return data_type
  73
  74     def update(self):
  75         # preemptively setting this to None - we might end up changing our mind
  76         # later
  77         self.count = None
  78         try:
  79             self.head = self.valobj.GetChildMemberWithName('_M_h')
  80             self.before_begin = self.head.GetChildMemberWithName('_M_before_begin')
  81             self.next = self.before_begin.GetChildMemberWithName('_M_nxt')
  82             self.data_type = self.extract_type()
  83             self.skip_size = self.next.GetType().GetByteSize()
  84             self.data_size = self.data_type.GetByteSize()
  85             if (not self.data_type.IsValid()) or (not self.next.IsValid()):
  86                 self.count = 0
  87         except:
  88             self.count = 0
  89         return False
  90
  91     def get_child_index(self, name):
  92         try:
  93             return int(name.lstrip('[').rstrip(']'))
  94         except:
  95             return -1
  96
  97     def get_child_at_index(self, index):
  98         logger = lldb.formatters.Logger.Logger()
  99         logger >> "Being asked to fetch child[" + str(index) + "]"
 100         if index < 0:
 101             return None
 102         if index >= self.num_children():
 103             return None
 104         try:
 105             offset = index
 106             current = self.next
 107             while offset > 0:
 108                 current = current.GetChildMemberWithName('_M_nxt')
 109                 offset = offset - 1
 110             return current.CreateChildAtOffset( '[' + str(index) + ']', self.skip_size, self.data_type)
 111
 112         except:
 113             logger >> "Cannot get child"
 114             return None
 115
 116     def num_children(self):
 117         if self.count is None:
 118             self.count = self.num_children_impl()
 119         return self.count
 120
 121     def num_children_impl(self):
 122         logger = lldb.formatters.Logger.Logger()
 123         try:
 124             count = self.head.GetChildMemberWithName('_M_element_count').GetValueAsUnsigned(0)
 125             return count
 126         except:
 127             logger >> "Could not determine the size"
 128             return 0
 129
 130
 131 class AbstractListSynthProvider:
 132     def __init__(self, valobj, dict, has_prev):
 133         '''
 134         :param valobj: The value object of the list
 135         :param dict: A dict with metadata provided by LLDB
 136         :param has_prev: Whether the list supports a 'prev' pointer besides a 'next' one
 137         '''
 138         logger = lldb.formatters.Logger.Logger()
 139         self.valobj = valobj
 140         self.count = None
 141         self.has_prev = has_prev
 142         self.list_capping_size = self.valobj.GetTarget().GetMaximumNumberOfChildrenToDisplay()
 143         logger >> "Providing synthetic children for a list named " + \
 144             str(valobj.GetName())
 145
 146     def next_node(self, node):
 147         logger = lldb.formatters.Logger.Logger()
 148         return node.GetChildMemberWithName('_M_next')
 149
 150     def is_valid(self, node):
 151         logger = lldb.formatters.Logger.Logger()
 152         valid = self.value(self.next_node(node)) != self.get_end_of_list_address()
 153         if valid:
 154             logger >> "%s is valid" % str(self.valobj.GetName())
 155         else:
 156             logger >> "synthetic value is not valid"
 157         return valid
 158
 159     def value(self, node):
 160         logger = lldb.formatters.Logger.Logger()
 161         value = node.GetValueAsUnsigned()
 162         logger >> "synthetic value for {}: {}".format(
 163             str(self.valobj.GetName()), value)
 164         return value
 165
 166     # Floyd's cycle-finding algorithm
 167     # try to detect if this list has a loop
 168     def has_loop(self):
 169         global _list_uses_loop_detector
 170         logger = lldb.formatters.Logger.Logger()
 171         if not _list_uses_loop_detector:
 172             logger >> "Asked not to use loop detection"
 173             return False
 174         slow = self.next
 175         fast1 = self.next
 176         fast2 = self.next
 177         while self.is_valid(slow):
 178             slow_value = self.value(slow)
 179             fast1 = self.next_node(fast2)
 180             fast2 = self.next_node(fast1)
 181             if self.value(fast1) == slow_value or self.value(
 182                     fast2) == slow_value:
 183                 return True
 184             slow = self.next_node(slow)
 185         return False
 186
 187     def num_children(self):
 188         logger = lldb.formatters.Logger.Logger()
 189         if self.count is None:
 190             # libstdc++ 6.0.21 added dedicated count field.
 191             count_child = self.node.GetChildMemberWithName('_M_data')
 192             if count_child and count_child.IsValid():
 193                 self.count = count_child.GetValueAsUnsigned(0)
 194             if self.count is None:
 195                 self.count = self.num_children_impl()
 196         return self.count
 197
 198     def num_children_impl(self):
 199         logger = lldb.formatters.Logger.Logger()
 200         try:
 201             # After a std::list has been initialized, both next and prev will
 202             # be non-NULL
 203             next_val = self.next.GetValueAsUnsigned(0)
 204             if next_val == 0:
 205                 return 0
 206             if self.has_loop():
 207                 return 0
 208             if self.has_prev:
 209                 prev_val = self.prev.GetValueAsUnsigned(0)
 210                 if prev_val == 0:
 211                     return 0
 212                 if next_val == self.node_address:
 213                     return 0
 214                 if next_val == prev_val:
 215                     return 1
 216             size = 1
 217             current = self.next
 218             while current.GetChildMemberWithName(
 219                     '_M_next').GetValueAsUnsigned(0) != self.get_end_of_list_address():
 220                 current = current.GetChildMemberWithName('_M_next')
 221                 if not current.IsValid():
 222                     break
 223                 size = size + 1
 224                 if size >= self.list_capping_size:
 225                     break
 226
 227             return size
 228         except:
 229             logger >> "Error determining the size"
 230             return 0
 231
 232     def get_child_index(self, name):
 233         logger = lldb.formatters.Logger.Logger()
 234         try:
 235             return int(name.lstrip('[').rstrip(']'))
 236         except:
 237             return -1
 238
 239     def get_child_at_index(self, index):
 240         logger = lldb.formatters.Logger.Logger()
 241         logger >> "Fetching child " + str(index)
 242         if index < 0:
 243             return None
 244         if index >= self.num_children():
 245             return None
 246         try:
 247             offset = index
 248             current = self.next
 249             while offset > 0:
 250                 current = current.GetChildMemberWithName('_M_next')
 251                 offset = offset - 1
 252             # C++ lists store the data of a node after its pointers. In the case of a forward list, there's just one pointer (next), and
 253             # in the case of a double-linked list, there's an additional pointer (prev).
 254             return current.CreateChildAtOffset(
 255                 '[' + str(index) + ']',
 256                (2 if self.has_prev else 1) * current.GetType().GetByteSize(),
 257                 self.data_type)
 258         except:
 259             return None
 260
 261     def extract_type(self):
 262         logger = lldb.formatters.Logger.Logger()
 263         list_type = self.valobj.GetType().GetUnqualifiedType()
 264         if list_type.IsReferenceType():
 265             list_type = list_type.GetDereferencedType()
 266         if list_type.GetNumberOfTemplateArguments() > 0:
 267             return list_type.GetTemplateArgumentType(0)
 268         return lldb.SBType()
 269
 270     def update(self):
 271         logger = lldb.formatters.Logger.Logger()
 272         # preemptively setting this to None - we might end up changing our mind
 273         # later
 274         self.count = None
 275         try:
 276             self.impl = self.valobj.GetChildMemberWithName('_M_impl')
 277             self.data_type = self.extract_type()
 278             if (not self.data_type.IsValid()) or (not self.impl.IsValid()):
 279                 self.count = 0
 280             elif not self.updateNodes():
 281                 self.count = 0
 282             else:
 283                 self.data_size = self.data_type.GetByteSize()
 284         except:
 285             self.count = 0
 286         return False
 287
 288     '''
 289     Method is used to extract the list pointers into the variables (e.g self.node, self.next, and optionally to self.prev)
 290     and is mandatory to be overriden in each AbstractListSynthProvider subclass.
 291     This should return True or False depending on wheter it found valid data.
 292     '''
 293     def updateNodes(self):
 294         raise NotImplementedError
 295
 296     def has_children(self):
 297         return True
 298
 299     '''
 300      Method is used to identify if a node traversal has reached its end
 301      and is mandatory to be overriden in each AbstractListSynthProvider subclass
 302     '''
 303     def get_end_of_list_address(self):
 304         raise NotImplementedError
 305
 306
 307 class StdForwardListSynthProvider(AbstractListSynthProvider):
 308
 309     def __init__(self, valobj, dict):
 310         has_prev = False
 311         super().__init__(valobj, dict, has_prev)
 312
 313     def updateNodes(self):
 314         self.node = self.impl.GetChildMemberWithName('_M_head')
 315         self.next = self.node.GetChildMemberWithName('_M_next')
 316         if (not self.node.IsValid()) or (not self.next.IsValid()):
 317             return False
 318         return True
 319
 320     def get_end_of_list_address(self):
 321         return 0
 322
 323
 324 class StdListSynthProvider(AbstractListSynthProvider):
 325
 326     def __init__(self, valobj, dict):
 327         has_prev = True
 328         super().__init__(valobj, dict, has_prev)
 329
 330     def updateNodes(self):
 331         self.node_address = self.valobj.AddressOf().GetValueAsUnsigned(0)
 332         self.node = self.impl.GetChildMemberWithName('_M_node')
 333         self.prev = self.node.GetChildMemberWithName('_M_prev')
 334         self.next = self.node.GetChildMemberWithName('_M_next')
 335         if self.node_address == 0 or (not self.node.IsValid()) or (not self.next.IsValid()) or (not self.prev.IsValid()):
 336             return False
 337         return True
 338
 339     def get_end_of_list_address(self):
 340         return self.node_address
 341
 342
 343 class StdVectorSynthProvider:
 344
 345     class StdVectorImplementation(object):
 346
 347         def __init__(self, valobj):
 348             self.valobj = valobj
 349             self.count = None
 350
 351         def num_children(self):
 352             if self.count is None:
 353                 self.count = self.num_children_impl()
 354             return self.count
 355
 356         def num_children_impl(self):
 357             try:
 358                 start_val = self.start.GetValueAsUnsigned(0)
 359                 finish_val = self.finish.GetValueAsUnsigned(0)
 360                 end_val = self.end.GetValueAsUnsigned(0)
 361                 # Before a vector has been constructed, it will contain bad values
 362                 # so we really need to be careful about the length we return since
 363                 # uninitialized data can cause us to return a huge number. We need
 364                 # to also check for any of the start, finish or end of storage values
 365                 # being zero (NULL). If any are, then this vector has not been
 366                 # initialized yet and we should return zero
 367
 368                 # Make sure nothing is NULL
 369                 if start_val == 0 or finish_val == 0 or end_val == 0:
 370                     return 0
 371                 # Make sure start is less than finish
 372                 if start_val >= finish_val:
 373                     return 0
 374                 # Make sure finish is less than or equal to end of storage
 375                 if finish_val > end_val:
 376                     return 0
 377
 378                 # if we have a struct (or other data type that the compiler pads to native word size)
 379                 # this check might fail, unless the sizeof() we get is itself incremented to take the
 380                 # padding bytes into account - on current clang it looks like
 381                 # this is the case
 382                 num_children = (finish_val - start_val)
 383                 if (num_children % self.data_size) != 0:
 384                     return 0
 385                 else:
 386                     num_children = num_children // self.data_size
 387                 return num_children
 388             except:
 389                 return 0
 390
 391         def get_child_at_index(self, index):
 392             logger = lldb.formatters.Logger.Logger()
 393             logger >> "Retrieving child " + str(index)
 394             if index < 0:
 395                 return None
 396             if index >= self.num_children():
 397                 return None
 398             try:
 399                 offset = index * self.data_size
 400                 return self.start.CreateChildAtOffset(
 401                     '[' + str(index) + ']', offset, self.data_type)
 402             except:
 403                 return None
 404
 405         def update(self):
 406             # preemptively setting this to None - we might end up changing our
 407             # mind later
 408             self.count = None
 409             try:
 410                 impl = self.valobj.GetChildMemberWithName('_M_impl')
 411                 self.start = impl.GetChildMemberWithName('_M_start')
 412                 self.finish = impl.GetChildMemberWithName('_M_finish')
 413                 self.end = impl.GetChildMemberWithName('_M_end_of_storage')
 414                 self.data_type = self.start.GetType().GetPointeeType()
 415                 self.data_size = self.data_type.GetByteSize()
 416                 # if any of these objects is invalid, it means there is no
 417                 # point in trying to fetch anything
 418                 if self.start.IsValid() and self.finish.IsValid(
 419                 ) and self.end.IsValid() and self.data_type.IsValid():
 420                     self.count = None
 421                 else:
 422                     self.count = 0
 423             except:
 424                 self.count = 0
 425             return False
 426
 427     class StdVBoolImplementation(object):
 428
 429         def __init__(self, valobj, bool_type):
 430             self.valobj = valobj
 431             self.bool_type = bool_type
 432             self.valid = False
 433
 434         def num_children(self):
 435             if self.valid:
 436                 start = self.start_p.GetValueAsUnsigned(0)
 437                 finish = self.finish_p.GetValueAsUnsigned(0)
 438                 offset = self.offset.GetValueAsUnsigned(0)
 439                 if finish >= start:
 440                     return (finish - start) * 8 + offset
 441             return 0
 442
 443         def get_child_at_index(self, index):
 444             if index >= self.num_children():
 445                 return None
 446             element_type = self.start_p.GetType().GetPointeeType()
 447             element_bits = 8 * element_type.GetByteSize()
 448             element_offset = (index // element_bits) * \
 449                 element_type.GetByteSize()
 450             bit_offset = index % element_bits
 451             element = self.start_p.CreateChildAtOffset(
 452                 '[' + str(index) + ']', element_offset, element_type)
 453             bit = element.GetValueAsUnsigned(0) & (1 << bit_offset)
 454             if bit != 0:
 455                 value_expr = "(bool)true"
 456             else:
 457                 value_expr = "(bool)false"
 458             return self.valobj.CreateValueFromExpression(
 459                 "[%d]" % index, value_expr)
 460
 461         def update(self):
 462             try:
 463                 m_impl = self.valobj.GetChildMemberWithName('_M_impl')
 464                 self.m_start = m_impl.GetChildMemberWithName('_M_start')
 465                 self.m_finish = m_impl.GetChildMemberWithName('_M_finish')
 466                 self.start_p = self.m_start.GetChildMemberWithName('_M_p')
 467                 self.finish_p = self.m_finish.GetChildMemberWithName('_M_p')
 468                 self.offset = self.m_finish.GetChildMemberWithName('_M_offset')
 469                 if self.offset.IsValid() and self.start_p.IsValid() and self.finish_p.IsValid():
 470                     self.valid = True
 471                 else:
 472                     self.valid = False
 473             except:
 474                 self.valid = False
 475             return False
 476
 477     def __init__(self, valobj, dict):
 478         logger = lldb.formatters.Logger.Logger()
 479         first_template_arg_type = valobj.GetType().GetTemplateArgumentType(0)
 480         if str(first_template_arg_type.GetName()) == "bool":
 481             self.impl = self.StdVBoolImplementation(
 482                 valobj, first_template_arg_type)
 483         else:
 484             self.impl = self.StdVectorImplementation(valobj)
 485         logger >> "Providing synthetic children for a vector named " + \
 486             str(valobj.GetName())
 487
 488     def num_children(self):
 489         return self.impl.num_children()
 490
 491     def get_child_index(self, name):
 492         try:
 493             return int(name.lstrip('[').rstrip(']'))
 494         except:
 495             return -1
 496
 497     def get_child_at_index(self, index):
 498         return self.impl.get_child_at_index(index)
 499
 500     def update(self):
 501         return self.impl.update()
 502
 503     def has_children(self):
 504         return True
 505
 506     """
 507      This formatter can be applied to all
 508      map-like structures (map, multimap, set, multiset)
 509     """
 510 class StdMapLikeSynthProvider:
 511
 512     def __init__(self, valobj, dict):
 513         logger = lldb.formatters.Logger.Logger()
 514         self.valobj = valobj
 515         self.count = None
 516         self.kind = self.get_object_kind(valobj)
 517         logger >> "Providing synthetic children for a " + self.kind + " named " + \
 518             str(valobj.GetName())
 519
 520     def get_object_kind(self, valobj):
 521         type_name = valobj.GetTypeName()
 522         for kind in ["multiset", "multimap", "set", "map"]:
 523            if kind in type_name:
 524               return kind
 525         return type_name
 526
 527     # we need this function as a temporary workaround for rdar://problem/10801549
 528     # which prevents us from extracting the std::pair<K,V> SBType out of the template
 529     # arguments for _Rep_Type _M_t in the object itself - because we have to make up the
 530     # typename and then find it, we may hit the situation were std::string has multiple
 531     # names but only one is actually referenced in the debug information. hence, we need
 532     # to replace the longer versions of std::string with the shorter one in order to be able
 533     # to find the type name
 534     def fixup_class_name(self, class_name):
 535         logger = lldb.formatters.Logger.Logger()
 536         if class_name == 'std::basic_string<char, std::char_traits<char>, std::allocator<char> >':
 537             return 'std::basic_string<char>', True
 538         if class_name == 'basic_string<char, std::char_traits<char>, std::allocator<char> >':
 539             return 'std::basic_string<char>', True
 540         if class_name == 'std::basic_string<char, std::char_traits<char>, std::allocator<char> >':
 541             return 'std::basic_string<char>', True
 542         if class_name == 'basic_string<char, std::char_traits<char>, std::allocator<char> >':
 543             return 'std::basic_string<char>', True
 544         return class_name, False
 545
 546     def update(self):
 547         logger = lldb.formatters.Logger.Logger()
 548         # preemptively setting this to None - we might end up changing our mind
 549         # later
 550         self.count = None
 551         try:
 552             # we will set this to True if we find out that discovering a node in the object takes more steps than the overall size of the RB tree
 553             # if this gets set to True, then we will merrily return None for
 554             # any child from that moment on
 555             self.garbage = False
 556             self.Mt = self.valobj.GetChildMemberWithName('_M_t')
 557             self.Mimpl = self.Mt.GetChildMemberWithName('_M_impl')
 558             self.Mheader = self.Mimpl.GetChildMemberWithName('_M_header')
 559             if not self.Mheader.IsValid():
 560                 self.count = 0
 561             else:
 562                 map_type = self.valobj.GetType()
 563                 if map_type.IsReferenceType():
 564                     logger >> "Dereferencing type"
 565                     map_type = map_type.GetDereferencedType()
 566
 567                 # Get the type of std::pair<key, value>. It is the first template
 568                 # argument type of the 4th template argument to std::map.
 569                 allocator_type = map_type.GetTemplateArgumentType(3)
 570                 self.data_type = allocator_type.GetTemplateArgumentType(0)
 571                 if not self.data_type:
 572                     # GCC does not emit DW_TAG_template_type_parameter for
 573                     # std::allocator<...>. For such a case, get the type of
 574                     # std::pair from a member of std::map.
 575                     rep_type = self.valobj.GetChildMemberWithName('_M_t').GetType()
 576                     self.data_type = rep_type.GetTypedefedType().GetTemplateArgumentType(1)
 577
 578                 # from libstdc++ implementation of _M_root for rbtree
 579                 self.Mroot = self.Mheader.GetChildMemberWithName('_M_parent')
 580                 self.data_size = self.data_type.GetByteSize()
 581                 self.skip_size = self.Mheader.GetType().GetByteSize()
 582         except:
 583             self.count = 0
 584         return False
 585
 586     def num_children(self):
 587         logger = lldb.formatters.Logger.Logger()
 588         if self.count is None:
 589             self.count = self.num_children_impl()
 590         return self.count
 591
 592     def num_children_impl(self):
 593         logger = lldb.formatters.Logger.Logger()
 594         try:
 595             root_ptr_val = self.node_ptr_value(self.Mroot)
 596             if root_ptr_val == 0:
 597                 return 0
 598             count = self.Mimpl.GetChildMemberWithName(
 599                 '_M_node_count').GetValueAsUnsigned(0)
 600             logger >> "I have " + str(count) + " children available"
 601             return count
 602         except:
 603             return 0
 604
 605     def get_child_index(self, name):
 606         logger = lldb.formatters.Logger.Logger()
 607         try:
 608             return int(name.lstrip('[').rstrip(']'))
 609         except:
 610             return -1
 611
 612     def get_child_at_index(self, index):
 613         logger = lldb.formatters.Logger.Logger()
 614         logger >> "Being asked to fetch child[" + str(index) + "]"
 615         if index < 0:
 616             return None
 617         if index >= self.num_children():
 618             return None
 619         if self.garbage:
 620             logger >> "Returning None since we are a garbage tree"
 621             return None
 622         try:
 623             offset = index
 624             current = self.left(self.Mheader)
 625             while offset > 0:
 626                 current = self.increment_node(current)
 627                 offset = offset - 1
 628             # skip all the base stuff and get at the data
 629             return current.CreateChildAtOffset(
 630                 '[' + str(index) + ']', self.skip_size, self.data_type)
 631         except:
 632             return None
 633
 634     # utility functions
 635     def node_ptr_value(self, node):
 636         logger = lldb.formatters.Logger.Logger()
 637         return node.GetValueAsUnsigned(0)
 638
 639     def right(self, node):
 640         logger = lldb.formatters.Logger.Logger()
 641         return node.GetChildMemberWithName("_M_right")
 642
 643     def left(self, node):
 644         logger = lldb.formatters.Logger.Logger()
 645         return node.GetChildMemberWithName("_M_left")
 646
 647     def parent(self, node):
 648         logger = lldb.formatters.Logger.Logger()
 649         return node.GetChildMemberWithName("_M_parent")
 650
 651     # from libstdc++ implementation of iterator for rbtree
 652     def increment_node(self, node):
 653         logger = lldb.formatters.Logger.Logger()
 654         max_steps = self.num_children()
 655         if self.node_ptr_value(self.right(node)) != 0:
 656             x = self.right(node)
 657             max_steps -= 1
 658             while self.node_ptr_value(self.left(x)) != 0:
 659                 x = self.left(x)
 660                 max_steps -= 1
 661                 logger >> str(max_steps) + " more to go before giving up"
 662                 if max_steps <= 0:
 663                     self.garbage = True
 664                     return None
 665             return x
 666         else:
 667             x = node
 668             y = self.parent(x)
 669             max_steps -= 1
 670             while(self.node_ptr_value(x) == self.node_ptr_value(self.right(y))):
 671                 x = y
 672                 y = self.parent(y)
 673                 max_steps -= 1
 674                 logger >> str(max_steps) + " more to go before giving up"
 675                 if max_steps <= 0:
 676                     self.garbage = True
 677                     return None
 678             if self.node_ptr_value(self.right(x)) != self.node_ptr_value(y):
 679                 x = y
 680             return x
 681
 682     def has_children(self):
 683         return True
 684
 685 _list_uses_loop_detector = True
 686
 687 class StdDequeSynthProvider:
 688     def __init__(self, valobj, d):
 689         self.valobj = valobj
 690         self.pointer_size = self.valobj.GetProcess().GetAddressByteSize()
 691         self.count = None
 692         self.block_size = -1
 693         self.element_size = -1
 694         self.find_block_size()
 695
 696
 697     def find_block_size(self):
 698         # in order to use the deque we must have the block size, or else
 699         # it's impossible to know what memory addresses are valid
 700         self.element_type = self.valobj.GetType().GetTemplateArgumentType(0)
 701         if not self.element_type.IsValid():
 702             return
 703         self.element_size = self.element_type.GetByteSize()
 704         # The block size (i.e. number of elements per subarray) is defined in
 705         # this piece of code, so we need to replicate it.
 706         #
 707         # #define _GLIBCXX_DEQUE_BUF_SIZE 512
 708         #
 709         # return (__size < _GLIBCXX_DEQUE_BUF_SIZE
 710             #   ? size_t(_GLIBCXX_DEQUE_BUF_SIZE / __size) : size_t(1));
 711         if self.element_size < 512:
 712             self.block_size = 512 // self.element_size
 713         else:
 714             self.block_size = 1
 715
 716     def num_children(self):
 717         if self.count is None:
 718             return 0
 719         return self.count
 720
 721     def has_children(self):
 722         return True
 723
 724     def get_child_index(self, name):
 725         try:
 726             return int(name.lstrip('[').rstrip(']'))
 727         except:
 728             return -1
 729
 730     def get_child_at_index(self, index):
 731         if index < 0 or self.count is None:
 732             return None
 733         if index >= self.num_children():
 734             return None
 735         try:
 736             name = '[' + str(index) + ']'
 737             # We first look for the element in the first subarray,
 738             # which might be incomplete.
 739             if index < self.first_node_size:
 740                 # The following statement is valid because self.first_elem is the pointer
 741                 # to the first element
 742                 return self.first_elem.CreateChildAtOffset(name, index * self.element_size, self.element_type)
 743
 744             # Now the rest of the subarrays except for maybe the last one
 745             # are going to be complete, so the final expression is simpler
 746             i, j = divmod(index - self.first_node_size, self.block_size)
 747
 748             # We first move to the beginning of the node/subarray were our element is
 749             node = self.start_node.CreateChildAtOffset(
 750                 '',
 751                 (1 + i) * self.valobj.GetProcess().GetAddressByteSize(),
 752                 self.element_type.GetPointerType())
 753             return node.CreateChildAtOffset(name, j * self.element_size, self.element_type)
 754
 755         except:
 756             return None
 757
 758     def update(self):
 759         logger = lldb.formatters.Logger.Logger()
 760         self.count = 0
 761         try:
 762             # A deque is effectively a two-dim array, with fixed width.
 763             # However, only a subset of this memory contains valid data
 764             # since a deque may have some slack at the front and back in
 765             # order to have O(1) insertion at both ends.
 766             # The rows in active use are delimited by '_M_start' and
 767             # '_M_finish'.
 768             #
 769             # To find the elements that are actually constructed, the 'start'
 770             # variable tells which element in this NxM array is the 0th
 771             # one.
 772             if self.block_size < 0 or self.element_size < 0:
 773                 return False
 774
 775             count = 0
 776
 777             impl = self.valobj.GetChildMemberWithName('_M_impl')
 778
 779             # we calculate the size of the first node (i.e. first internal array)
 780             self.start = impl.GetChildMemberWithName('_M_start')
 781             self.start_node = self.start.GetChildMemberWithName('_M_node')
 782             first_node_address = self.start_node.GetValueAsUnsigned(0)
 783             first_node_last_elem = self.start.GetChildMemberWithName('_M_last').GetValueAsUnsigned(0)
 784             self.first_elem = self.start.GetChildMemberWithName('_M_cur')
 785             first_node_first_elem = self.first_elem.GetValueAsUnsigned(0)
 786
 787
 788             finish = impl.GetChildMemberWithName('_M_finish')
 789             last_node_address = finish.GetChildMemberWithName('_M_node').GetValueAsUnsigned(0)
 790             last_node_first_elem = finish.GetChildMemberWithName('_M_first').GetValueAsUnsigned(0)
 791             last_node_last_elem = finish.GetChildMemberWithName('_M_cur').GetValueAsUnsigned(0)
 792
 793             if first_node_first_elem == 0 or first_node_last_elem == 0 or first_node_first_elem > first_node_last_elem:
 794                 return False
 795             if last_node_first_elem == 0 or last_node_last_elem == 0 or last_node_first_elem > last_node_last_elem:
 796                 return False
 797
 798
 799             if last_node_address == first_node_address:
 800                 self.first_node_size = (last_node_last_elem - first_node_first_elem) // self.element_size
 801                 count += self.first_node_size
 802             else:
 803                 self.first_node_size = (first_node_last_elem - first_node_first_elem) // self.element_size
 804                 count += self.first_node_size
 805
 806                 # we calculate the size of the last node
 807                 finish = impl.GetChildMemberWithName('_M_finish')
 808                 last_node_address = finish.GetChildMemberWithName('_M_node').GetValueAsUnsigned(0)
 809                 count += (last_node_last_elem - last_node_first_elem) // self.element_size
 810
 811                 # we calculate the size of the intermediate nodes
 812                 num_intermediate_nodes = (last_node_address - first_node_address - 1) // self.valobj.GetProcess().GetAddressByteSize()
 813                 count += self.block_size * num_intermediate_nodes
 814             self.count = count
 815         except:
 816             pass
 817         return False