1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<link href="../style.css" rel="stylesheet" type="text/css" />
<title>LLDB Homepage</title>
</head>
<body>
<div class="www_title">
<strong>LLDB</strong> Data Formatters Architecture
</div>
<div id="container">
<div id="content">
<!--#include virtual="../sidebar.incl"-->
<div id="middle">
<div class="post">
<h1 class ="postheader">Bird's eye view</h1>
<div class="postcontent">
<p>The LLDB data formatters subsystem is used to allow the debugger as well as the end-users to customize the way
their variables look upon inspection in the user interface (be it the command line tool, or one of the several
GUIs that are backed by LLDB)
<p>To this aim, they are hooked into the ValueObjects model, in order to provide entry points through which such customization
questions can be answered as <i>what format should this number be printed as?</i>, <i>how many child elements does this
std::vector have?</i> and more along those lines
<p>The architecture of the subsystem is layered, with the highest level layer being the user visible interaction features
(e.g. the "type ***" commands, the SB classes, ...). Other layers of interest that will be analyzed in this document include
<ul>
<li>Classes implementing individual data formatter types</li>
<li>Classes implementing formatters navigation, discovery and categorization</li>
<li>The FormatManager layer</li>
<li>The DataVisualization layer</li>
<li>The SWIG LLDB <---> communication layer</li>
</ul>
</div>
<div class="postfooter"></div>
</div>
<div class="post">
<h1 class ="postheader">Data formatter types</h1>
<div class="postcontent">
<p> As described in the user documentation, there are four types of formatters
<ul>
<li>formats</li>
<li>summaries</li>
<li>filters</li>
<li>synthetic children</li>
</ul>
<p>Architecturally, these are implemented by classes in the source/DataFormatters/ folder<br/>
Formatters have descriptor classes, Type*Impl, which contain at least a "Flags" nested object, which contains both rules to be used
by the matching algorithm (e.g. should the formatter for type Foo apply to a Foo*?) or rules to be used
by the formatter itself (e.g. is this summary a oneliner?)
<p>Individual formatter descriptor classes then also contain data items useful to them for performing their functionality.
For instance TypeFormatImpl (backing formats) contains an lldb::Format that is the format to then be applied
were this formatter to be selected. Upon issuing a "type format add", a new TypeFormatImpl is created that wraps
the user-specified format, and matching options:<br/><br/>
<code>entry.reset(new TypeFormatImpl(format,
TypeFormatImpl::Flags().SetCascades(m_command_options.m_cascade).
SetSkipPointers(m_command_options.m_skip_pointers).
SetSkipReferences(m_command_options.m_skip_references)));</code><br/><br/>
<p>While formats are fairly simple and only implemented by one class, the other formatter types are backed by a class hierarchy
<p>Summaries, for instance, can exist in one of three "flavors":
<ul>
<li>summary strings</li>
<li>Python script</li>
<li>native C++</li>
</ul>
<p>The base class for summaries, TypeSummaryImpl, is a pure virtual class that wraps, again, the Flags, and exports among others a
<br/><br/><code>
virtual bool
FormatObject (ValueObject *valobj,
std::string& dest) = 0;
</code><br/><br/>
<p>This is the core entry point, which allows subclasses to specify their mode of operation
<p>StringSummaryFormat, which is the class that implements summary strings, does a check as to whether
the summary is a one-liner, and if not, then uses its stored summary string to call into
Debugger::FormatPrompt, and obtain a string back, which it returns in dest as the resulting summary
<p>For a Python summary, implemented in ScriptSummaryFormat, FormatObject() calls into the ScriptInterpreter
which is supposed to hold the knowledge on how to bridge back and forth with the scripting language
(Python in the case of LLDB) in order to produce a valid string. Implementors of new ScriptInterpreters for other
languages are expected to provide a GetScriptedSummary() entrypoint for this purpose, if they desire to allow
users to provide formatters in the new language
<p> Lastly, C++ summaries (CXXFunctionSummaryFormat), wrap a function pointer and call into it to execute their duty.
It should be noted that there are no facilities for users to interact with C++ formatters, and as such they are extremely
opaque, effectively being a thin wrapper between plain function pointers and the LLDB formatters subsystem.<br/>
Also, dynamic loading of C++ formatters in LLDB is currently not implemented, and as such it is safe and reasonable
for these formatters to deal with internal ValueObjects instances instead of public SBValue objects
<p>An interesting data point is that summaries are expected to be stateless. While at the Python layer they are handed
an SBValue (since nothing else could be visible for scripts), it is not expected that the SBValue should be cached
and reused - any and all caching occurs on the LLDB side, completely transparent to the formatter itself<br/><br/><br/>
<p>The design of synthetic children is somewhat more intricate, due to them being stateful objects.<br/>
The core idea of the design is that synthetic children act like a two-tier model, in which there is a <i>backend</i>
dataset (the underlying unformatted ValueObject), and an higher level view (<i>frontend</i>) which vends the computed
representation
<p>To implement a new type of synthetic children one would implement a subclass of SyntheticChildren, which akin to the TypeFormatImpl,
contains Flags for matching, and data items to be used for formatting. For instance, TypeFilterImpl (which implements filters),
stores the list of expression paths of the children to be displayed. <br/>Filters are themselves synthetic children. Since all they
do is provide child values for a ValueObject, it does not truly matter whether these come from the real set of children or are
crafted through some intricate algorithm. As such, they perfectly fit within the realm of synthetic children and are only
shown as separate entities for user friendliness (to a user, picking a subset of elements to be shown with relative ease is a
valuable task, and they should not be concerned with writing scripts to do so)
<p>Once the descriptor of the synthetic children has been coded, in order to hook it up, one has to implement a subclass of
SyntheticChildrenFrontEnd. For a given type of synthetic children, there is a deep coupling with the matching front-end class,
given that the front-end usually needs data stored in the descriptor (e.g. a filter needs the list of child elements)
<p>The front-end answers the interesting questions that are the true <i>raison d'être</i> of synthetic children:
<br/>
<code>
<ul>
<li>
virtual size_t
CalculateNumChildren () = 0;
</li>
<li>
virtual lldb::ValueObjectSP
GetChildAtIndex (size_t idx) = 0;
</li>
<li>
virtual size_t
GetIndexOfChildWithName (const ConstString &name) = 0;
</li>
<li>
virtual bool
Update () = 0;
</li>
<li>
virtual bool
MightHaveChildren () = 0;
</li>
</ul>
</code><br/>
<p> Synthetic children providers (their front-ends) will be queried by LLDB for a number of children, and then for each of them
as necessary, they should be prepared to return a ValueObject describing the child. They might also be asked to provide a
name-to-index mapping (e.g. to allow LLDB to resolve queries like <code>myFoo.myChild</code>)<br/>
Update() and MightHaveChildren() are described in the user documentation, and they mostly serve bookkeeping purposes
<p>LLDB provides three kinds of synthetic children: filters, scripted synthetics, and the native C++ providers<br/>
Filters are implemented by TypeFilterImpl/TypeFilterImpl::FrontEnd<br/><br/>
Scripted synthetics are implemented by ScriptedSyntheticChildren/ScriptedSyntheticChildren::FrontEnd, plus
a set of callbacks provided by the ScriptInterpteter infrastructure to allow LLDB to pass the front-end queries
down to the scripting languages<br/><br/>
As for C++ native synthetics, there is a CXXSyntheticChildren, but no corresponding FrontEnd class. The reason for this design is
that CXXSyntheticChildren store a callback to a creator function, which is responsible for providing a FrontEnd.
Each individual formatter (e.g. LibstdcppMapIteratorSyntheticFrontEnd, NSDictionaryMSyntheticFrontEnd, ...) is a standalone
frontend, and once created retains to relation to its underlying SyntheticChildren object
<p>On a ValueObject level, upon being asked to generate synthetic children for a ValueObject, LLDB spawns a ValueObjectSynthetic object
which is a subclass of ValueObject. Building upon the ValueObject infrastructure, it stores a backend, and a shared pointer to
the SyntheticChildren. <br/>
Upon being asked queries about children, it will use the SyntheticChildren to generate a front-end for itself
and will let the front-end answer questions. The reason for not storing the FrontEnd itself is that there is no guarantee that across
updates, the same FrontEnd will be used over and over (e.g. a SyntheticChildren object could serve an entire class hierarchy
and vend different frontends for different subclasses)
</div>
<div class="postfooter"></div>
</div>
<div class="post">
<h1 class ="postheader">Formatters matching</h1>
<div class="postcontent">
<p>The problem of formatters matching is going from
"I have a ValueObject" to "these are the formatters to be used for it"<br/>
There is a rather intricate set of user rules that are involved, and a rather intricate implementation of this model. All of these
relate to the type of the ValueObject. It is assumed that types are a strong enough contract that it is possible to format an object
entirely depending on its type. If this turns out to not be correct, then the existing model will have to be changed fairly deeply.
<p>The basic building block is that formatters can match by exact type name or by regular expressions, i.e. one can describe matching
by saying things like "this formatters matches type __NSDictionaryI", or "this formatter matches all type names like ^std::__1::vector<.+>(( )?&)?$"<br/>This match happens in class FormattersContainer. For exact matches, this goes straight to the FormatMap
(the actual storage area for formatters), whereas for regular expression matches the regular expression is matched against the
provided candidate type name. If one were to introduce a new type of matching (say, match against number of $ signs present
in the typename, FormattersContainer is the place where such a change would have to be introduced).<br/>It should be noted that this
code involves template specialization, and as such is somewhat trickier than other formatters code to update.
<p>On top of the string matching mechanism (exact or regex), there are a set of more advanced rules implemented
by the FormattersContainer,
with the aid of the FormattersMatchCandidate. Namely, it is assumed that any formatter class will have flags to say whether
it allows <i>cascading</i> (i.e. seeing through typedefs), allowing pointers-to-object and reference-to-object to be formatted.
<br/>Upon verifying that a formatter would be a textual match, the Flags are checked, and if they do not allow the formatter
to be used (e.g. pointers are not allowed, and one is looking at a Foo*), then the formatter is rejected and the search continues.
If the flags also match, then the formatter is returned upstream and the search is over.
<p>One relevant fact to notice is that this entire mechanism is not dependent on the kind of formatter to be returned, which makes it
easier to devise new types of formatters as the lowest layers of the system. The demands on individual formatters are that they
define a few typedefs, and export a Flags object, and then they can be freely matched against types as needed.
<p>This mechanism is replicated across a number of <i>categories</i>. A category is a named bucket where formatters are grouped on
some basis. The most common reason for a category to exist is a library (e.g. libcxx formatters vs. libstdcpp formatters).
<br/>
Categories can be enabled or disabled, and they have a priority number, called position. The priority sets a strong order among
enabled categories. A category named "default" is always the highest priority one and it's the category where all formatters that
do not ask for a category of their own end up (e.g. "type summary add ...." without a "-w somecategory" flag passed)<br/>
The algorithm inquires each category, in the order of their priorities, for a formatter for a type, and upon receiving a positive
answer from a category, ends the search. Of course, no search occurs in disabled categories.
<p>At the individual category level, there is the first dependence on the type of formatter to be returned. Since both filters and
synthetic children proper are implemented through the same backing store, the matching code needs to ensure that, were both a
synthetic children provider and a filter to match a type, only the most recently added one is actually used.
<br/>The details of the algorithm used are to be found in TypeCategoryImpl::Get().<br/>
<p>It is quite obvious, even to a casual reader, that there are a number of complexities involved in this algorithm.<br/>
For starters, the entire search process has to be repeated for every variable.<br/>
Moreover, for each category, one has to repeat the entire process of crawling the types (go to pointee, ...).<br/>
This is exactly the algorithm initially implemented by LLDB. Over the course of the life of the formatters subsystem,
two main evolutions have been made to the matching mechanism:
<ul>
<li>A caching mechanism</li>
<li>A pregeneration of all possible type matches</li>
</ul>
<p>The cache is a layer that sits between the FormatManager and the TypeCategoryMap. Upon being asked to figure out a formatter,
the FormatManager will first query the cache layer, and only if that fails, will the categories be queried using the full
search algorithm. The result of that full search will then be stored in the cache. Even a negative answer (no formatter)
gets stored. The negative answer is actually the most beneficial to cache as obtaining it requires traversing all possible
formatters in all categories just to get a no-op back.<br/>
Of course, once an answer is cached, getting it will be much quicker than going to a full category search, as the cached
answers are of the form "type foo" --> "formatter bar". But given how formatters can be edited or removed by the user,
either at the command line or via the API, there needs to be a way to invalidate the cache.<br/>
This happens through the FormatManager::Changed() method. In general, anything that changes the formatters causes
FormatManager::Changed() to be called through the IFormatChangeListener interface. This call increases the
FormatManager's revision and clears the cache. The revision number is a monotonically increasing integer counter
that essentially corresponds to the number of changes made to the formatters throughout the current LLDB session.
This counter is used by ValueObjects to know when their formatters are out of date. Since a search is a potentially
expensive operation, before caching was introduced, individual ValueObjects remembered which revision of the FormatManager
they used to search for their formatter, and stored it, so that they would not repeat the search unless a change in the
formatters had occurred. While caching has made this less critical of an optimization, it is still sensible and thus is kept.
<br/>Lastly, as a side note, it is worth highlighting that <strong>any</strong> change in the formatters invalidates the
<strong>entire</strong> cache. It would likely not be impossible to be smarter and figure out a subset of cache entries
to be deleted, letting others persist, instead of having to rebuild the entire cache from scratch. However, given that formatters
are not that frequently changed during a debug session, and the algorithmic complexity to "get it right" seems larger than the
potential benefit to be had from doing it, the full cache invalidation is the chosen policy. The algorithm to selectively invalidate
entries is probably one of the major areas for improvements in formatters performance.
<p>The second major optimization, introduced fairly recently, is the pregeneration of type matches. The original algorithm was based upon
the notion of a FormatNavigator as a smart object, aware of all the intricacies of the matching rules. For each category, the
FormatNavigator would generate the possible matches (e.g. dynamic type, pointee type, ...), and check each one, one at a time.
If that failed for a category, the next one would again generate the same matches.<br/>
This worked well, but was of course inefficient. The FormattersMatchCandidate is the solution to this performance issue.
In top-of-tree LLDB, the FormatManager has the centralized notion of the matching rules, and the former FormatNavigators are now
FormattersContainers, whose only job is to guarantee a centralized storage of formatters, and thread-safe access to such storage.
<br/>FormatManager::GetPossibleMatches() fills a vector of possible matches. The way it works is by applying each rule,
generating the corresponding typename, and storing the typename, plus the required Flags for that rule to be accepted
as a match candidate (e.g. if the match comes by fetching the pointee type, a formatter that matches will have to allow pointees
as part of its Flags object). The TypeCategoryMap, when tasked with finding a formatter for a type, generates all possible matches
and passes them down to each category. In this model, the type system only does its (expensive) job once, and textual or regex
matches are the core of the work.
</div>
<div class="postfooter"></div>
</div>
<div class="post">
<h1 class ="postheader">FormatManager and DataVisualization</h1>
<div class="postcontent">
<p>There are two main entry points in the data formatters: the FormatManager and the DataVisualization<br/>
The FormatManager is the <i>internal</i> such entry point. In this context, internal refers to data formatters code
itself, compared to other parts of LLDB. For other components of the debugger, the DataVisualization provides a more
stable entry point. On the other hand, the FormatManager is an aggregator of all moving parts, and as such is less stable
in the face of refactoring.<br/>People involved in the data formatters code itself, however, will most likely have to confront
the FormatManager for significant architecture changes.
<p>The FormatManager wraps a TypeCategoryMap (the list of all existing categories, enabled and not), the FormatCache, and several
utility objects. Plus, it is the repository of named summaries, since these don't logically belong anywhere else.<br/>
It is also responsible for creating all builtin formatters upon the launch of LLDB. It does so through a bunch
of methods Load***Formatters(), invoked as part of its constructor. The original design of data formatters anticipated
that individual libraries would load their formatters as part of their debug information. This work however has largely been
left unattended in practice, and as such core system libraries (mostly those for OSX/iOS development as of today) load their
formatters in an hardcoded fashion.
<p>For performance reasons, the FormatManager is constructed upon being first required.
This happens through the DataVisualization layer. Upon first being inquired for anything formatters, DataVisualization
calls its own local static function GetFormatManager(), which in turns constructs and returns a local static FormatManager.<br/>
Unlike most things in LLDB, the lifetime of the FormatManager is the same as the entire session, rather than a specific Debugger
or Target instance. This is an area to be improved, but as of now it has not caused enough grief to warrant action. If this work
were to be undertaken, one could conceivably devise a per-architecture-triple model, upon the assumption that an OS and CPU
combination are a good enough key to decide which formatters apply (e.g. Linux i386 is probably different from OSX x86_64, but two
OSX x86_64 targets will probably have the same formatters; of course versioning of the underlying OS is also to be considered,
but experience with OSX has shown that formatters can take care of that internally in most cases of interest).
<p>The public entry point is the DataVisualization layer. DataVisualization is a static class on which questions can be asked
in a relatively refactoring-safe manner.
<br/>The main question asked of it is to obtain formatters for ValueObjects (or typenames).
One can also query DataVisualization for named summaries or individual categories, but of course those queries delve deeper
in the internal object model.<br/>As said, the FormatManager holds a notion of revision number, which changes every time
formatters are edited (added, deleted, categories enabled or disabled, ...). Through DataVisualization::ForceUpdate() one
can cause the same effects of a formatters edit to happen without it actually having happened.<br/>
The main reason for this feature is that formatters can be dynamically created in Python, and one can then enter the
ScriptInterpreter and edit the formatter function or class. If formatters were not updated, one could find them to be out of sync
with the new definitions of these objects. To avoid the issue, whenever the user exits the scripting mode, formatters force
an update to make sure new potential definitions are reloaded on demand.
</div>
<div class="postfooter"></div>
</div>
<div class="post">
<h1 class ="postheader">The SWIG layer</h1>
<div class="postcontent">
<p>In order to implement formatters written in Python, LLDB requires that ScriptInterpreter implementations provide a set
of functions that one can call to ask formatting questions of scripts.<br/>
For instance, in order to obtain a scripting summary, LLDB calls
<code><br/>
virtual bool<br/>
GetScriptedSummary (const char *function_name,<br/>
llldb::ValueObjectSP valobj,<br/>
lldb::ScriptInterpreterObjectSP& callee_wrapper_sp,<br/>
std::string& retval)<br/>
</code><br/>
<p>For Python, this function is implemented by first checking if the callee_wrapper_sp is valid.
If so, LLDB knows that it does not need to search a function with the passed name, and can directly
call the wrapped Python function object. Either way, the call is routed to a global callback <code>g_swig_typescript_callback</code>
<p>This callback pointer points to <code>LLDBSwigPythonCallTypeScript</code>, defined in python-wrapper.swig<br/>
The details of the implementation require familiarity with the Python C API, plus a few utility objects defined
by LLDB to ease the burden of dealing with the scripting world. However, as a sketch of what happens, the code
tries to find a Python function object with the given name (i.e. if you say "type summary add -F module.function", LLDB will scan
for "module" module, and then for a function named "function" inside the module's namespace). If the function object is found,
it is wrapped in a PyCallable, which is an LLDB utility class that wraps the callable and allows for easier calling.
The callable gets invoked, and the return value, if any, is cast into a string. Originally, if a non-string object was returned,
LLDB would refuse to use it. This disallowed such simple construct as
<code><br/>def getSummary(value,*args):<br/> return 1</br></code> from working
<p>Similar considerations apply to other formatter (and non-formatter related) scripting callbacks
</div>
<div class="postfooter"></div>
</div>
<div class="post">
<h1 class ="postheader">Conclusion</h1>
<div class="postcontent">
<p>This document is an introduction to the design of the LLDB data formatters subsystem<br/>
The intended target audience are people interested in understanding or modifying the formatters themselves
rather than writing a specific data formatter. For this latter purpose, the user documentation about formatters
is the main relevant document which one should refer to.
<p>On the other hand, this one page highlights some open areas for improvement to the general subsystem, and more evolutions
not anticipated here are certainly possible. As usual, the lldb-dev mailing list is the point of first contact for
discussing desired new features or changes of existing features.
</div>
<div class="postfooter"></div>
</div>
</div>
</div>
</div>
</body>
</html>
|
