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