[libstdc++ data-formatters] Remove size limits and loop detector.

[granata.enrico]

Why are you removing the loop detection?

As for the size capping, yes, if you remove the loop detection it will be less of a problem because downstream commands (e.g. frame variable) will actually cap how many elements get fetched unless the user overrides that determination (or the API is used directly to retrieve values)

[sivachandra]

How can there be loops in an std::list?

1. If the implementation is flawed.
2. If someone messes with its implementation.

Should we protect for such cases at all? If #1, don't use that library in the first place. If #2, that is an unsupported use case :)

[granata.enrico]

Possibility number 3 (and the true reason why the check is there): if you stop at a place where the variable is not fully initialized/being torn down, and as a result, something is pointing back inside the list. For a list traversal, that is a deadly outcome.

This is (partially) the same reason why there's a cap on string summaries. It's fairly unlikely that a user will truly have a 3GB string (if they did, we might still want to cap it, but it's unlikely to begin with): an uninitialized string that claims to have a 3GB buffer.

I think there are ways to make this code smarter. For instance, if you have to get node #10, you could only check for a loop up until node #10, and so on..
If you store the state of the loop-checker as you get out, you might get away without having to check the same nodes multiple times as you progress deeper into the list

Drawback is that you would have already handed out at least some data by the time you find out the list is flawed. You can decide for yourself if that is a problem or not (the list might be partially valid, and returning some of the data is actually a good thing, maybe?)

[jingham]

I don't know about the std::list implementation in specific, but in the debugger you have to be aware of the possibility that you are looking at an entity that is in the middle of being modified. Note, it may not be obvious to the user that that is being done since it may be happening on another thread. Anyway, depending on how that is done the entity might be in a weird or weirder state. So it is good never to allow yourself to run off into the weeds if you can easily avoid it.

Jim

[sivachandra]

Is eliminating the size limits alone acceptable then?

[granata.enrico]

Removing the size limit would be acceptable, yes

It is a remnant of a time when LLDB lacked ways to actually cap data at the command-line level and the Xcode UI did not do lazy fetching of values

Given that these things now work properly, the ability to generate *all* children for large lists should be safe

[sivachandra]

Abandoning this in favor of http://reviews.llvm.org/D13682. It was easy to create a new diff than to edit the existing one.

examples/synthetic/gnu_libstdcpp.py

 class StdListSynthProvider:
 
   def __init__(self, valobj, dict):
     logger = lldb.formatters.Logger.Logger()
     self.valobj = valobj
     self.count = None
     logger >> "Providing synthetic children for a map 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()
-    return self.value(self.next_node(node)) != self.node_address
-
-  def value(self,node):
-    logger = lldb.formatters.Logger.Logger()
-    return node.GetValueAsUnsigned()
-
-  # Floyd's cycle-finding algorithm
-  # try to detect if this list has a loop
-  def has_loop(self):
-    global _list_uses_loop_detector
-    logger = lldb.formatters.Logger.Logger()
-    if _list_uses_loop_detector == False:
-      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):
-    global _list_capping_size
     logger = lldb.formatters.Logger.Logger()
     if self.count == None:
       self.count = self.num_children_impl()
-      if self.count > _list_capping_size:
-        self.count = _list_capping_size
     return self.count
 
   def num_children_impl(self):
     logger = lldb.formatters.Logger.Logger()
-    global _list_capping_size
     try:
       next_val = self.next.GetValueAsUnsigned(0)
       prev_val = self.prev.GetValueAsUnsigned(0)
       # After a std::list has been initialized, both next and prev will be non-NULL
       if next_val == 0 or prev_val == 0:
         return 0
       if next_val == self.node_address:
         return 0
       if next_val == prev_val:
         return 1
-      if self.has_loop():
-        return 0
       size = 2
       current = self.next
       while current.GetChildMemberWithName('_M_next').GetValueAsUnsigned(0) != self.node_address:
         size = size + 1
         current = current.GetChildMemberWithName('_M_next')
-        if size > _list_capping_size:
-          return _list_capping_size
       return (size - 1)
     except:
       return 0;
 
   def get_child_index(self,name):
     logger = lldb.formatters.Logger.Logger()
     try:
       return int(name.lstrip('[').rstrip(']'))
try:
       # from libstdc++ implementation of _M_root for rbtree
       self.Mroot = self.Mheader.GetChildMemberWithName('_M_parent')
       self.data_size = self.data_type.GetByteSize()
       self.skip_size = self.Mheader.GetType().GetByteSize()
     except:
       pass
 
   def num_children(self):
-    global _map_capping_size
     logger = lldb.formatters.Logger.Logger()
     if self.count == None:
       self.count = self.num_children_impl()
-      if self.count > _map_capping_size:
-        self.count = _map_capping_size
     return self.count
 
   def num_children_impl(self):
     logger = lldb.formatters.Logger.Logger()
     try:
       root_ptr_val = self.node_ptr_value(self.Mroot)
       if root_ptr_val == 0:
         return 0;
else:
           self.garbage = True
           return None
       if self.node_ptr_value(self.right(x)) != self.node_ptr_value(y):
         x = y;
       return x;
 
   def has_children(self):
     return True
-
-_map_capping_size = 255
-_list_capping_size = 255
-_list_uses_loop_detector = True