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