1from __future__ import division
2import re
3import lldb.formatters.Logger
4
5# C++ STL formatters for LLDB
6# These formatters are based upon the version of the GNU libstdc++
7# as it ships with Mac OS X 10.6.8 thru 10.8.0
8# You are encouraged to look at the STL implementation for your platform
9# before relying on these formatters to do the right thing for your setup
10
11
12class StdListSynthProvider:
13
14    def __init__(self, valobj, dict):
15        logger = lldb.formatters.Logger.Logger()
16        self.valobj = valobj
17        self.count = None
18        logger >> "Providing synthetic children for a list named " + \
19            str(valobj.GetName())
20
21    def next_node(self, node):
22        logger = lldb.formatters.Logger.Logger()
23        return node.GetChildMemberWithName('_M_next')
24
25    def is_valid(self, node):
26        logger = lldb.formatters.Logger.Logger()
27        valid = self.value(self.next_node(node)) != self.node_address
28        if valid:
29            logger >> "%s is valid" % str(self.valobj.GetName())
30        else:
31            logger >> "synthetic value is not valid"
32        return valid
33
34    def value(self, node):
35        logger = lldb.formatters.Logger.Logger()
36        value = node.GetValueAsUnsigned()
37        logger >> "synthetic value for {}: {}".format(
38            str(self.valobj.GetName()), value)
39        return value
40
41    # Floyd's cycle-finding algorithm
42    # try to detect if this list has a loop
43    def has_loop(self):
44        global _list_uses_loop_detector
45        logger = lldb.formatters.Logger.Logger()
46        if not _list_uses_loop_detector:
47            logger >> "Asked not to use loop detection"
48            return False
49        slow = self.next
50        fast1 = self.next
51        fast2 = self.next
52        while self.is_valid(slow):
53            slow_value = self.value(slow)
54            fast1 = self.next_node(fast2)
55            fast2 = self.next_node(fast1)
56            if self.value(fast1) == slow_value or self.value(
57                    fast2) == slow_value:
58                return True
59            slow = self.next_node(slow)
60        return False
61
62    def num_children(self):
63        logger = lldb.formatters.Logger.Logger()
64        if self.count is None:
65            # libstdc++ 6.0.21 added dedicated count field.
66            count_child = self.node.GetChildMemberWithName('_M_data')
67            if count_child and count_child.IsValid():
68                self.count = count_child.GetValueAsUnsigned(0)
69            if self.count is None:
70                self.count = self.num_children_impl()
71        return self.count
72
73    def num_children_impl(self):
74        logger = lldb.formatters.Logger.Logger()
75        try:
76            next_val = self.next.GetValueAsUnsigned(0)
77            prev_val = self.prev.GetValueAsUnsigned(0)
78            # After a std::list has been initialized, both next and prev will
79            # be non-NULL
80            if next_val == 0 or prev_val == 0:
81                return 0
82            if next_val == self.node_address:
83                return 0
84            if next_val == prev_val:
85                return 1
86            if self.has_loop():
87                return 0
88            size = 2
89            current = self.next
90            while current.GetChildMemberWithName(
91                    '_M_next').GetValueAsUnsigned(0) != self.node_address:
92                size = size + 1
93                current = current.GetChildMemberWithName('_M_next')
94            return (size - 1)
95        except:
96            return 0
97
98    def get_child_index(self, name):
99        logger = lldb.formatters.Logger.Logger()
100        try:
101            return int(name.lstrip('[').rstrip(']'))
102        except:
103            return -1
104
105    def get_child_at_index(self, index):
106        logger = lldb.formatters.Logger.Logger()
107        logger >> "Fetching child " + str(index)
108        if index < 0:
109            return None
110        if index >= self.num_children():
111            return None
112        try:
113            offset = index
114            current = self.next
115            while offset > 0:
116                current = current.GetChildMemberWithName('_M_next')
117                offset = offset - 1
118            return current.CreateChildAtOffset(
119                '[' + str(index) + ']',
120                2 * current.GetType().GetByteSize(),
121                self.data_type)
122        except:
123            return None
124
125    def extract_type(self):
126        logger = lldb.formatters.Logger.Logger()
127        list_type = self.valobj.GetType().GetUnqualifiedType()
128        if list_type.IsReferenceType():
129            list_type = list_type.GetDereferencedType()
130        if list_type.GetNumberOfTemplateArguments() > 0:
131            data_type = list_type.GetTemplateArgumentType(0)
132        else:
133            data_type = None
134        return data_type
135
136    def update(self):
137        logger = lldb.formatters.Logger.Logger()
138        # preemptively setting this to None - we might end up changing our mind
139        # later
140        self.count = None
141        try:
142            impl = self.valobj.GetChildMemberWithName('_M_impl')
143            self.node = impl.GetChildMemberWithName('_M_node')
144            self.node_address = self.valobj.AddressOf().GetValueAsUnsigned(0)
145            self.next = self.node.GetChildMemberWithName('_M_next')
146            self.prev = self.node.GetChildMemberWithName('_M_prev')
147            self.data_type = self.extract_type()
148            self.data_size = self.data_type.GetByteSize()
149        except:
150            pass
151        return False
152
153    def has_children(self):
154        return True
155
156
157class StdVectorSynthProvider:
158
159    class StdVectorImplementation(object):
160
161        def __init__(self, valobj):
162            self.valobj = valobj
163            self.count = None
164
165        def num_children(self):
166            if self.count is None:
167                self.count = self.num_children_impl()
168            return self.count
169
170        def num_children_impl(self):
171            try:
172                start_val = self.start.GetValueAsUnsigned(0)
173                finish_val = self.finish.GetValueAsUnsigned(0)
174                end_val = self.end.GetValueAsUnsigned(0)
175                # Before a vector has been constructed, it will contain bad values
176                # so we really need to be careful about the length we return since
177                # uninitialized data can cause us to return a huge number. We need
178                # to also check for any of the start, finish or end of storage values
179                # being zero (NULL). If any are, then this vector has not been
180                # initialized yet and we should return zero
181
182                # Make sure nothing is NULL
183                if start_val == 0 or finish_val == 0 or end_val == 0:
184                    return 0
185                # Make sure start is less than finish
186                if start_val >= finish_val:
187                    return 0
188                # Make sure finish is less than or equal to end of storage
189                if finish_val > end_val:
190                    return 0
191
192                # if we have a struct (or other data type that the compiler pads to native word size)
193                # this check might fail, unless the sizeof() we get is itself incremented to take the
194                # padding bytes into account - on current clang it looks like
195                # this is the case
196                num_children = (finish_val - start_val)
197                if (num_children % self.data_size) != 0:
198                    return 0
199                else:
200                    num_children = num_children // self.data_size
201                return num_children
202            except:
203                return 0
204
205        def get_child_at_index(self, index):
206            logger = lldb.formatters.Logger.Logger()
207            logger >> "Retrieving child " + str(index)
208            if index < 0:
209                return None
210            if index >= self.num_children():
211                return None
212            try:
213                offset = index * self.data_size
214                return self.start.CreateChildAtOffset(
215                    '[' + str(index) + ']', offset, self.data_type)
216            except:
217                return None
218
219        def update(self):
220            # preemptively setting this to None - we might end up changing our
221            # mind later
222            self.count = None
223            try:
224                impl = self.valobj.GetChildMemberWithName('_M_impl')
225                self.start = impl.GetChildMemberWithName('_M_start')
226                self.finish = impl.GetChildMemberWithName('_M_finish')
227                self.end = impl.GetChildMemberWithName('_M_end_of_storage')
228                self.data_type = self.start.GetType().GetPointeeType()
229                self.data_size = self.data_type.GetByteSize()
230                # if any of these objects is invalid, it means there is no
231                # point in trying to fetch anything
232                if self.start.IsValid() and self.finish.IsValid(
233                ) and self.end.IsValid() and self.data_type.IsValid():
234                    self.count = None
235                else:
236                    self.count = 0
237            except:
238                pass
239            return False
240
241    class StdVBoolImplementation(object):
242
243        def __init__(self, valobj, bool_type):
244            self.valobj = valobj
245            self.bool_type = bool_type
246            self.valid = False
247
248        def num_children(self):
249            if self.valid:
250                start = self.start_p.GetValueAsUnsigned(0)
251                finish = self.finish_p.GetValueAsUnsigned(0)
252                offset = self.offset.GetValueAsUnsigned(0)
253                if finish >= start:
254                    return (finish - start) * 8 + offset
255            return 0
256
257        def get_child_at_index(self, index):
258            if index >= self.num_children():
259                return None
260            element_type = self.start_p.GetType().GetPointeeType()
261            element_bits = 8 * element_type.GetByteSize()
262            element_offset = (index // element_bits) * \
263                element_type.GetByteSize()
264            bit_offset = index % element_bits
265            element = self.start_p.CreateChildAtOffset(
266                '[' + str(index) + ']', element_offset, element_type)
267            bit = element.GetValueAsUnsigned(0) & (1 << bit_offset)
268            if bit != 0:
269                value_expr = "(bool)true"
270            else:
271                value_expr = "(bool)false"
272            return self.valobj.CreateValueFromExpression(
273                "[%d]" % index, value_expr)
274
275        def update(self):
276            try:
277                m_impl = self.valobj.GetChildMemberWithName('_M_impl')
278                self.m_start = m_impl.GetChildMemberWithName('_M_start')
279                self.m_finish = m_impl.GetChildMemberWithName('_M_finish')
280                self.start_p = self.m_start.GetChildMemberWithName('_M_p')
281                self.finish_p = self.m_finish.GetChildMemberWithName('_M_p')
282                self.offset = self.m_finish.GetChildMemberWithName('_M_offset')
283                self.valid = True
284            except:
285                self.valid = False
286            return False
287
288    def __init__(self, valobj, dict):
289        logger = lldb.formatters.Logger.Logger()
290        first_template_arg_type = valobj.GetType().GetTemplateArgumentType(0)
291        if str(first_template_arg_type.GetName()) == "bool":
292            self.impl = self.StdVBoolImplementation(
293                valobj, first_template_arg_type)
294        else:
295            self.impl = self.StdVectorImplementation(valobj)
296        logger >> "Providing synthetic children for a vector named " + \
297            str(valobj.GetName())
298
299    def num_children(self):
300        return self.impl.num_children()
301
302    def get_child_index(self, name):
303        try:
304            return int(name.lstrip('[').rstrip(']'))
305        except:
306            return -1
307
308    def get_child_at_index(self, index):
309        return self.impl.get_child_at_index(index)
310
311    def update(self):
312        return self.impl.update()
313
314    def has_children(self):
315        return True
316
317    """
318     This formatter can be applied to all
319     map-like structures (map, multimap, set, multiset)
320    """
321class StdMapLikeSynthProvider:
322
323    def __init__(self, valobj, dict):
324        logger = lldb.formatters.Logger.Logger()
325        self.valobj = valobj
326        self.count = None
327        self.kind = self.get_object_kind(valobj)
328        logger >> "Providing synthetic children for a " + self.kind + " named " + \
329            str(valobj.GetName())
330
331    def get_object_kind(self, valobj):
332        type_name = valobj.GetTypeName()
333        for kind in ["multiset", "multimap", "set", "map"]:
334           if kind in type_name:
335              return kind
336        return type_name
337
338    # we need this function as a temporary workaround for rdar://problem/10801549
339    # which prevents us from extracting the std::pair<K,V> SBType out of the template
340    # arguments for _Rep_Type _M_t in the object itself - because we have to make up the
341    # typename and then find it, we may hit the situation were std::string has multiple
342    # names but only one is actually referenced in the debug information. hence, we need
343    # to replace the longer versions of std::string with the shorter one in order to be able
344    # to find the type name
345    def fixup_class_name(self, class_name):
346        logger = lldb.formatters.Logger.Logger()
347        if class_name == 'std::basic_string<char, std::char_traits<char>, std::allocator<char> >':
348            return 'std::basic_string<char>', True
349        if class_name == 'basic_string<char, std::char_traits<char>, std::allocator<char> >':
350            return 'std::basic_string<char>', True
351        if class_name == 'std::basic_string<char, std::char_traits<char>, std::allocator<char> >':
352            return 'std::basic_string<char>', True
353        if class_name == 'basic_string<char, std::char_traits<char>, std::allocator<char> >':
354            return 'std::basic_string<char>', True
355        return class_name, False
356
357    def update(self):
358        logger = lldb.formatters.Logger.Logger()
359        # preemptively setting this to None - we might end up changing our mind
360        # later
361        self.count = None
362        try:
363            # 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
364            # if this gets set to True, then we will merrily return None for
365            # any child from that moment on
366            self.garbage = False
367            self.Mt = self.valobj.GetChildMemberWithName('_M_t')
368            self.Mimpl = self.Mt.GetChildMemberWithName('_M_impl')
369            self.Mheader = self.Mimpl.GetChildMemberWithName('_M_header')
370
371            map_type = self.valobj.GetType()
372            if map_type.IsReferenceType():
373                logger >> "Dereferencing type"
374                map_type = map_type.GetDereferencedType()
375
376            # Get the type of std::pair<key, value>. It is the first template
377            # argument type of the 4th template argument to std::map.
378            allocator_type = map_type.GetTemplateArgumentType(3)
379            self.data_type = allocator_type.GetTemplateArgumentType(0)
380            if not self.data_type:
381                # GCC does not emit DW_TAG_template_type_parameter for
382                # std::allocator<...>. For such a case, get the type of
383                # std::pair from a member of std::map.
384                rep_type = self.valobj.GetChildMemberWithName('_M_t').GetType()
385                self.data_type = rep_type.GetTypedefedType().GetTemplateArgumentType(1)
386
387            # from libstdc++ implementation of _M_root for rbtree
388            self.Mroot = self.Mheader.GetChildMemberWithName('_M_parent')
389            self.data_size = self.data_type.GetByteSize()
390            self.skip_size = self.Mheader.GetType().GetByteSize()
391        except:
392            pass
393        return False
394
395    def num_children(self):
396        logger = lldb.formatters.Logger.Logger()
397        if self.count is None:
398            self.count = self.num_children_impl()
399        return self.count
400
401    def num_children_impl(self):
402        logger = lldb.formatters.Logger.Logger()
403        try:
404            root_ptr_val = self.node_ptr_value(self.Mroot)
405            if root_ptr_val == 0:
406                return 0
407            count = self.Mimpl.GetChildMemberWithName(
408                '_M_node_count').GetValueAsUnsigned(0)
409            logger >> "I have " + str(count) + " children available"
410            return count
411        except:
412            return 0
413
414    def get_child_index(self, name):
415        logger = lldb.formatters.Logger.Logger()
416        try:
417            return int(name.lstrip('[').rstrip(']'))
418        except:
419            return -1
420
421    def get_child_at_index(self, index):
422        logger = lldb.formatters.Logger.Logger()
423        logger >> "Being asked to fetch child[" + str(index) + "]"
424        if index < 0:
425            return None
426        if index >= self.num_children():
427            return None
428        if self.garbage:
429            logger >> "Returning None since we are a garbage tree"
430            return None
431        try:
432            offset = index
433            current = self.left(self.Mheader)
434            while offset > 0:
435                current = self.increment_node(current)
436                offset = offset - 1
437            # skip all the base stuff and get at the data
438            return current.CreateChildAtOffset(
439                '[' + str(index) + ']', self.skip_size, self.data_type)
440        except:
441            return None
442
443    # utility functions
444    def node_ptr_value(self, node):
445        logger = lldb.formatters.Logger.Logger()
446        return node.GetValueAsUnsigned(0)
447
448    def right(self, node):
449        logger = lldb.formatters.Logger.Logger()
450        return node.GetChildMemberWithName("_M_right")
451
452    def left(self, node):
453        logger = lldb.formatters.Logger.Logger()
454        return node.GetChildMemberWithName("_M_left")
455
456    def parent(self, node):
457        logger = lldb.formatters.Logger.Logger()
458        return node.GetChildMemberWithName("_M_parent")
459
460    # from libstdc++ implementation of iterator for rbtree
461    def increment_node(self, node):
462        logger = lldb.formatters.Logger.Logger()
463        max_steps = self.num_children()
464        if self.node_ptr_value(self.right(node)) != 0:
465            x = self.right(node)
466            max_steps -= 1
467            while self.node_ptr_value(self.left(x)) != 0:
468                x = self.left(x)
469                max_steps -= 1
470                logger >> str(max_steps) + " more to go before giving up"
471                if max_steps <= 0:
472                    self.garbage = True
473                    return None
474            return x
475        else:
476            x = node
477            y = self.parent(x)
478            max_steps -= 1
479            while(self.node_ptr_value(x) == self.node_ptr_value(self.right(y))):
480                x = y
481                y = self.parent(y)
482                max_steps -= 1
483                logger >> str(max_steps) + " more to go before giving up"
484                if max_steps <= 0:
485                    self.garbage = True
486                    return None
487            if self.node_ptr_value(self.right(x)) != self.node_ptr_value(y):
488                x = y
489            return x
490
491    def has_children(self):
492        return True
493
494_list_uses_loop_detector = True
495