<!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=iso-8859-1" />
<link href="style.css" rel="stylesheet" type="text/css" />
<title>LLDB Example - Python Scripting to Debug a Problem</title>
</head>

<body>
    <div class="www_title">
      Example - Using Scripting and Python to Debug in LLDB
    </div>
    
<div id="container">
	<div id="content">
         <!--#include virtual="sidebar.incl"-->
		<div id="middle">
			<div class="post">
				<h1 class ="postheader">Introduction</h1>
				<div class="postcontent">

                    <p>LLDB has been structured from the beginning to be scriptable in two ways 
                    -- a Unix Python session can initiate/run a debug session non-interactively 
                    using LLDB; and within the LLDB debugger tool, Python scripts can be used to 
                    help with many tasks, including inspecting program data, iterating over 
                    containers and determining if a breakpoint should stop execution or continue.  
                    This document will show how to do some of these things by going through an 
                    example, explaining how to use Python scripting to find a bug in a program 
                    that searches for text in a large binary tree.</p>

				</div>
				<div class="postfooter"></div>

			<div class="post">
				<h1 class ="postheader">The Test Program and Input</h1>
				<div class="postcontent">

                    <p>We have a simple C program (dictionary.c) that reads in a text file, and 
                    stores all the words from the file in a Binary Search Tree, sorted 
                    alphabetically.  It then enters a loop prompting the user for a word, searching
                    for the word in the tree (using Binary Search), and reporting to the user 
                    whether or not it found the word in the tree.</p>

                    <p>The input text file we are using to test our program contains the text for 
                    William Shakespeare's famous tragedy "Romeo and Juliet".</p>

				</div>
				<div class="postfooter"></div>

    			<div class="post">
    				<h1 class ="postheader">The Bug</h1>
    				<div class="postcontent">

		   <p>When we try running our program, we find there is a problem.  While it 
                   successfully finds some of the words we would expect to find, such as "love" 
                   or "sun", it fails to find the word "Romeo", which MUST be in the input text 
                   file:</p>

                   <code color=#ff0000>
                   % ./dictionary Romeo-and-Juliet.txt<br>
                   Dictionary loaded.<br>
                   Enter search word: love<br>
                   Yes!<br>
                   Enter search word: sun<br>
                   Yes!<br>
                   Enter search word: Romeo<br>
                   No!<br>
                   Enter search word: ^D<br>
                   %<br>
                   </code>

				</div>
				<div class="postfooter"></div>


    			<div class="post">
    				<h1 class ="postheader">Is the word in our tree: Using Depth First Search</h1>
    				<div class="postcontent">

                   <p>Our first job is to determine if the word "Romeo" actually got inserted into
                   the tree or not.  Since "Romeo and Juliet" has thousands of words, trying to 
                   examine our binary search tree by hand is completely impractical.  Therefore we 
                   will write a Python script to search the tree for us.  We will write a recursive
                   Depth First Search function that traverses the entire tree searching for a word,
                   and maintaining information about the path from the root of the tree to the 
                   current node.  If it finds the word in the tree, it returns the path from the 
                   root to the node containing the word.  This is what our DFS function in Python 
                   would look like, with line numbers added for easy reference in later 
                   explanations:</p>

                   <code>
<pre><tt>
 1: def DFS (root, word, cur_path):
 2:     root_word_ptr = root.GetChildMemberWithName ("word")
 3:     left_child_ptr = root.GetChildMemberWithName ("left")
 4:     right_child_ptr = root.GetChildMemberWithName ("right")
 5:     root_word = root_word_ptr.GetSummary()
 6:     end = len (root_word) - 1
 7:     if root_word[0] == '"' and root_word[end] == '"':
 8:         root_word = root_word[1:end]
 9:     end = len (root_word) - 1
10:     if root_word[0] == '\'' and root_word[end] == '\'':
11:        root_word = root_word[1:end]
12:     if root_word == word:
13:         return cur_path
14:     elif word < root_word:
15:         if left_child_ptr.GetValue() == None:
16:             return ""
17:         else:
18:             cur_path = cur_path + "L"
19:             return DFS (left_child_ptr, word, cur_path)
20:     else:
21:         if right_child_ptr.GetValue() == None:
22:             return ""
23:         else:
24:             cur_path = cur_path + "R"
25:             return DFS (right_child_ptr, word, cur_path)
</tt></pre>
                   </code>

				</div>
				<div class="postfooter"></div>


    			<div class="post">
    				<h1 class ="postheader"><a name="accessing-variables">Accessing & Manipulating <strong>Program</strong> Variables in Python</a>
</h1>
    				<div class="postcontent">

                   <p>Before we can call any Python function on any of our program's variables, we 
                   need to get the variable into a form that Python can access.  To show you how to
                   do this we will look at the parameters for the DFS function.  The first 
                   parameter is going to be a node in our binary search tree, put into a Python 
                   variable.  The second parameter is the word we are searching for (a string), and
                   the third parameter is a string representing the path from the root of the tree 
                   to our current node.</p>

                   <p>The most interesting parameter is the first one, the Python variable that
                   needs to contain a node in our search tree. How can we take a variable out of 
                   our program and put it into a Python variable?  What kind of Python variable 
                   will it be?  The answers are to use the LLDB API functions, provided as part of 
                   the LLDB Python module.  Running Python from inside LLDB, LLDB will 
                   automatically give us our current frame object as a Python variable, 
                   "lldb.frame".  This variable has the type "SBFrame" (see the LLDB API for
                   more information about SBFrame objects).  One of the things we can do with a 
                   frame object, is to ask it to find and return its local variable.  We will call 
                   the API function "FindVariable" on the lldb.frame object to give us our 
                   dictionary variable as a Python variable:</p>

                   <code>
                      root = lldb.frame.FindVariable ("dictionary")
                   </code>

                   <p>The line above, executed in the Python script interpreter in LLDB, asks the 
                   current frame to find the variable named "dictionary" and return it.  We then 
                   store the returned value in the Python variable named "root".  This answers the 
                   question of HOW to get the variable, but it still doesn't explain WHAT actually
                   gets put into "root".  If you examine the LLDB API, you will find that the 
                   SBFrame method "FindVariable" returns an object of type SBValue. SBValue 
                   objects are used, among other things, to wrap up program variables and values.
                   There are many useful methods defined in the SBValue class to allow you to get 
                   information or children values out of SBValues.  For complete information, see 
                   the header file <a href="http://llvm.org/svn/llvm-project/lldb/trunk/include/lldb/API/SBValue.h">SBValue.h</a>.  The 
                   SBValue methods that we use in our DFS function are 
                   <code>GetChildMemberWithName()</code>, 
                   <code>GetSummary()</code>, and <code>GetValue()</code>.</p>

				</div>
				<div class="postfooter"></div>


    			<div class="post">
    				<h1 class ="postheader">Explaining Depth First Search Script in Detail</h1>
    				<div class="postcontent">

                   <p><strong>"DFS" Overview.</strong>  Before diving into the details of this 
                   code, it would be best to give a high-level overview of what it does.  The nodes
                   in our binary search tree were defined to have type <code>tree_node *</code>, 
                   which is defined as:

                   <code>
<pre><tt>typedef struct tree_node
{
  const char *word;
  struct tree_node *left;
  struct tree_node *right;
} tree_node;</tt></pre></code>

                   <p>Lines 2-11 of DFS are getting data out of the current tree node and getting 
                   ready to do the actual search; lines 12-25 are the actual depth-first search.  
                   Lines 2-4 of our DFS function get the <code>word</code>, <code>left</code> and 
                   <code>right</code> fields out of the current node and store them in Python 
                   variables.  Since <code>root_word_ptr</code> is a pointer to our word, and we 
                   want the actual word, line 5 calls <code>GetSummary()</code> to get a string 
                   containing the value out of the pointer.  Since <code>GetSummary()</code> adds 
                   quotes around its result, lines 6-11 strip surrounding quotes off the word.</p>

                   <p>Line 12 checks to see if the word in the current node is the one we are 
                   searching for.  If so, we are done, and line 13 returns the current path.  
                   Otherwise, line 14 checks to see if we should go left (search word comes before 
                   the current word).  If we decide to go left, line 15 checks to see if the left 
                   pointer child is NULL ("None" is the Python equivalent of NULL). If the left 
                   pointer is NULL, then the word is not in this tree and we return an empty path 
                   (line 16).   Otherwise, we add an "L" to the end of our current path string, to 
                   indicate we are going left (line 18), and then recurse on the left child (line 
                   19).  Lines 20-25 are the same as lines 14-19, except for going right rather 
                   than going left.</p>

                   <p>One other note:  Typing something as long as our DFS function directly into 
                   the interpreter can be difficult, as making a single typing mistake means having
                   to start all over.  Therefore we recommend doing as we have done:  Writing your 
                   longer, more complicated script functions in a separate file (in this case 
                   tree_utils.py) and then importing it into your LLDB Python interpreter.</p>
                   
				</div>
				<div class="postfooter"></div>


    			<div class="post">
    				<h1 class ="postheader">Seeing the DFS Script in Action</h1>
    				<div class="postcontent">


                   <p>At this point we are ready to use the DFS function to see if the word "Romeo"
                   is in our tree or not.  To actually use it in LLDB on our dictionary program, 
                   you would do something like this:</p>

                   <code>
                     % <strong>lldb</strong><br>
                     (lldb) <strong>process attach -n "dictionary"</strong><br>
                     Architecture set to: x86_64.<br>
                     Process 521 stopped<br>
                     * thread #1: tid = 0x2c03, 0x00007fff86c8bea0 libSystem.B.dylib`read$NOCANCEL + 8, stop reason = signal SIGSTOP<br>
                     frame #0: 0x00007fff86c8bea0 libSystem.B.dylib`read$NOCANCEL + 8<br>
                     (lldb) <strong>breakpoint set -n find_word</strong><br>
                     Breakpoint created: 1: name = 'find_word', locations = 1, resolved = 1<br>
                     (lldb) <strong>continue</strong><br>
                     Process 521 resuming<br>
                     Process 521 stopped<br>
                     * thread #1: tid = 0x2c03, 0x0000000100001830 dictionary`find_word + 16 <br>
                     at dictionary.c:105, stop reason = breakpoint 1.1<br>
                     frame #0: 0x0000000100001830 dictionary`find_word + 16 at dictionary.c:105<br>
                     102 int<br>
                     103 find_word (tree_node *dictionary, char *word)<br>
                     104 {<br>
                     -> 105   if (!word || !dictionary)<br>
                     106     return 0;<br>
                     107 <br>
                     108   int compare_value = strcmp (word, dictionary->word);<br>
                     (lldb) <strong>script</strong><br>
                     Python Interactive Interpreter. To exit, type 'quit()', 'exit()' or Ctrl-D.<br>
                     >>> <strong>import tree_utils</strong><br>
                     >>> <strong>root = lldb.frame.FindVariable ("dictionary")</strong><br>
                     >>> <strong>current_path = ""</strong><br>
                     >>> <strong>path = tree_utils.DFS (root, "Romeo", current_path)</strong><br>
                     >>> <strong>print path</strong><br>
                     LLRRL<br>
                     >>> <strong>^D</strong><br>
                     (lldb) <br>
                   </code>

                   <p>The first bit of code above shows starting lldb, attaching to the dictionary 
                   program, and getting to the find_word function in LLDB.  The interesting part 
                   (as far as this example is concerned) begins when we enter the 
                   <code>script</code> command and drop into the embedded interactive Python 
                   interpreter.  We will go over this Python code line by line.  The first line</p>

                   <code>
                     import tree_utils
                   </code>

                   <p>imports the file where we wrote our DFS function, tree_utils.py, into Python. 
                   Notice that to import the file we leave off the ".py" extension.  We can now 
                   call any function in that file, giving it the prefix "tree_utils.", so that 
                   Python knows where to look for the function. The line</p>

                   <code>
                     root = lldb.frame.FindVariable ("dictionary")
                   </code>

                   <p>gets our program variable "dictionary" (which contains the binary search 
                   tree) and puts it into the Python variable "root".  See 
                   <a href="#accessing-variables">Accessing & Manipulating Program Variables in Python</a> 
                   above for more details about how this works. The next line is</p>

                   <code>
                     current_path = ""
                   </code>

                   <p>This line initializes the current_path from the root of the tree to our 
                   current node.  Since we are starting at the root of the tree, our current path 
                   starts as an empty string.  As we go right and left through the tree, the DFS 
                   function will append an 'R' or an 'L' to the current path, as appropriate. The 
                   line</p>

                   <code>
                     path = tree_utils.DFS (root, "Romeo", current_path)
                   </code>

                   <p>calls our DFS function (prefixing it with the module name so that Python can 
                   find it).  We pass in our binary tree stored in the variable <code>root</code>, 
                   the word we are searching for, and our current path.  We assign whatever path 
                   the DFS function returns to the Python variable <code>path</code>.</p>


                   <p>Finally, we want to see if the word was found or not, and if so we want to 
                   see the path through the tree to the word. So we do</p>

                   <code>
                     print path
                   </code>

                   <p>From this we can see that the word "Romeo" was indeed found in the tree, and
                   the path from the root of the tree to the node containing "Romeo" is 
                   left-left-right-right-left.</p>

				</div>
				<div class="postfooter"></div>


    			<div class="post">
    				<h1 class ="postheader">What next?  Using Breakpoint Command Scripts...</h1>
    				<div class="postcontent">

                   <p>We are halfway to figuring out what the problem is.  We know the word we are
                   looking for is in the binary tree, and we know exactly where it is in the binary
                   tree.  Now we need to figure out why our binary search algorithm is not finding 
                   the word.  We will do this using breakpoint command scripts.</p>


                   <p>The idea is as follows.  The binary search algorithm has two main decision 
                   points:  the decision to follow the right branch; and, the decision to follow 
                   the left branch.  We will set a breakpoint at each of these decision points, and
                   attach a Python breakpoint command script to each breakpoint.  The breakpoint
                   commands will use the global <code>path</code> Python variable that we got from 
                   our DFS function. Each time one of these decision breakpoints is hit, the script
                   will compare the actual decision with the decision the front of the 
                   <code>path</code> variable says should be made (the first character of the 
                   path).  If the actual decision and the path agree, then the front character is 
                   stripped off the path, and execution is resumed.  In this case the user never 
                   even sees the breakpoint being hit.  But if the decision differs from what the 
                   path says it should be, then the script prints out a message and does NOT resume
                   execution, leaving the user sitting at the first point where a wrong decision is
                   being made.</p>

				</div>
				<div class="postfooter"></div>


    			<div class="post">
    				<h1 class ="postheader">Side Note: Python Breakpoint Command Scripts are NOT What They Seem</h1>
    				<div class="postcontent">

				</div>
				<div class="postfooter"></div>

                   <p>What do we mean by that?  When you enter a Python breakpoint command in LLDB,
                   it appears that you are entering one or more plain lines of Python. BUT LLDB 
                   then takes what you entered and wraps it into a Python FUNCTION (just like using
                   the "def" Python command).   It automatically gives the function an obscure, 
                   unique, hard-to-stumble-across function name, and gives it two parameters: 
                   <code>frame</code> and <code>bp_loc</code>.  When the breakpoint gets hit, LLDB 
                   wraps up the frame object where the breakpoint was hit, and the breakpoint 
                   location object for the breakpoint that was hit, and puts them into Python 
                   variables for you.  It then calls the Python function that was created for the 
                   breakpoint command, and passes in the frame and breakpoint location objects.</p>

                   <p>So, being practical, what does this mean for you when you write your Python 
                   breakpoint commands?  It means that there are two things you need to keep in 
                   mind: 1. If you want to access any Python variables created outside your script,
                   <strong>you must declare such variables to be global</strong>.  If you do not
                   declare them as global, then the Python function will treat them as local 
                   variables, and you will get unexpected behavior.  2. <strong>All Python 
                   breakpoint command scripts automatically have a <code>frame</code> and a 
                   <code>bp_loc</code> variable.</strong>  The variables are pre-loaded by LLDB 
                   with the correct context for the breakpoint.  You do not have to use these 
                   variables, but they are there if you want them.</p>

				</div>
				<div class="postfooter"></div>


    			<div class="post">
    				<h1 class ="postheader">The Decision Point Breakpoint Commands</h1>
    				<div class="postcontent">

                   <p>This is what the Python breakpoint command script would look like for the 
                   decision to go right:<p>

<code><pre><tt>
global path
if path[0] == 'R':
    path = path[1:]
    thread = frame.GetThread()
    process = thread.GetProcess()
    process.Continue()
else:
    print "Here is the problem; going right, should go left!"
</tt></pre></code>

                   <p>Just as a reminder, LLDB is going to take this script and wrap it up in a 
                   function, like this:</p>

<code><pre><tt>
def some_unique_and_obscure_function_name (frame, bp_loc):
    global path
    if path[0] == 'R':
        path = path[1:]
        thread = frame.GetThread()
        process = thread.GetProcess()
        process.Continue()
    else:
        print "Here is the problem; going right, should go left!"
</tt></pre></code>

                   <p>LLDB will call the function, passing in the correct frame and breakpoint 
                   location whenever the breakpoint gets hit.  There are several things to notice 
                   about this function.  The first one is that we are accessing and updating a 
                   piece of state (the <code>path</code> variable), and actually conditioning our
                   behavior based upon this variable.  Since the variable was defined outside of 
                   our script (and therefore outside of the corresponding function) we need to tell
                   Python that we are accessing a global variable. That is what the first line of 
                   the script does.  Next we check where the path says we should go and compare it to 
                   our decision (recall that we are at the breakpoint for the decision to go 
                   right). If the path agrees with our decision, then  we strip the first character
                   off of the path.</p>

                   <p>Since the decision matched the path, we want to resume execution.  To do this
                   we make use of the <code>frame</code> parameter that LLDB guarantees will be 
                   there for us.  We use LLDB API functions to get the current thread from the 
                   current frame, and then to get the process from the thread.  Once we have the 
                   process, we tell it to resume execution (using the <code>Continue()</code> API 
                   function).</p>

                   <p>If the decision to go right does not agree with the path, then we do not 
                   resume execution.  We allow the breakpoint to remain stopped (by doing nothing),
                   and we print an informational message telling the user we have found the 
                   problem, and what the problem is.</p>

				</div>
				<div class="postfooter"></div>

    			<div class="post">
    				<h1 class ="postheader">Actually Using the Breakpoint Commands</h1>
    				<div class="postcontent">

                   <p>Now we will look at what happens when we actually use these breakpoint 
                   commands on our program.  Doing a <code>source list -n find_word</code> shows 
                   us the function containing our two decision points.  Looking at the code below, 
                   we see that we want to set our breakpoints on lines 113 and 115:</p>

<code><pre><tt>
(lldb) source list -n find_word
File: /Volumes/Data/HD2/carolinetice/Desktop/LLDB-Web-Examples/dictionary.c.
101 
102 int
103 find_word (tree_node *dictionary, char *word)
104 {
105   if (!word || !dictionary)
106     return 0;
107 
108   int compare_value = strcmp (word, dictionary->word);
109 
110   if (compare_value == 0)
111     return 1;
112   else if (compare_value < 0)
113     return find_word (dictionary->left, word);
114   else
115     return find_word (dictionary->right, word);
116 }
117 
</tt></pre></code>

                   <p>So, we set our breakpoints, enter our breakpoint command scripts, and see 
                   what happens:<p>

<code><pre><tt>
(lldb) breakpoint set -l 113
Breakpoint created: 2: file ='dictionary.c', line = 113, locations = 1, resolved = 1
(lldb) breakpoint set -l 115
Breakpoint created: 3: file ='dictionary.c', line = 115, locations = 1, resolved = 1
(lldb) breakpoint command add -s python 2
Enter your Python command(s). Type 'DONE' to end.
> global path
> if (path[0] == 'L'):
>     path = path[1:]
>     thread = frame.GetThread()
>     process = thread.GetProcess()
>     process.Continue()
> else:
>     print "Here is the problem. Going left, should go right!"
> DONE
(lldb) breakpoint command add -s python 3
Enter your Python command(s). Type 'DONE' to end.
> global path
> if (path[0] == 'R'):
>     path = path[1:]
>     thread = frame.GetThread()
>     process = thread.GetProcess()
>     process.Continue()
> else:
>     print "Here is the problem. Going right, should go left!"
> DONE
(lldb) continue
Process 696 resuming
Here is the problem. Going right, should go left!
Process 696 stopped
* thread #1: tid = 0x2d03, 0x000000010000189f dictionary`find_word + 127 at dictionary.c:115, stop reason = breakpoint 3.1
  frame #0: 0x000000010000189f dictionary`find_word + 127 at dictionary.c:115
    112   else if (compare_value < 0)
    113     return find_word (dictionary->left, word);
    114   else
 -> 115     return find_word (dictionary->right, word);
    116 }
    117 
    118 void
(lldb)
</tt></pre></code>


                   <p>After setting our breakpoints, adding our breakpoint commands and continuing,
                   we run for a little bit and then hit one of our breakpoints, printing out the 
                   error message from the breakpoint command.  Apparently at this point the the 
                   tree, our search algorithm decided to go right, but our path says the node we 
                   want is to the left. Examining the word at the node where we stopped, and our 
                   search word, we see:</p>

                   <code>
                     (lldb) expr dictionary->word<br>
                     (const char *) $1 = 0x0000000100100080 "dramatis"<br>
                     (lldb) expr word<br>
                     (char *) $2 = 0x00007fff5fbff108 "romeo"<br>
                   </code>

                   <p>So the word at our current node is "dramatis", and the word we are searching
                   for is "romeo".  "romeo" comes after "dramatis" alphabetically, so it seems like
                   going right would be the correct decision.  Let's ask Python what it thinks the
                   path from the current node to our word is:</p>

                   <code>
                     (lldb) script print path<br>
                     LLRRL<br>
                   </code>

                   <p>According to Python we need to go left-left-right-right-left from our current
                   node to find the word we are looking for.  Let's double check our tree, and see 
                   what word it has at that node:</p>

                   <code>
                     (lldb) expr dictionary->left->left->right->right->left->word<br>
                     (const char *) $4 = 0x0000000100100880 "Romeo"<br>
                   </code>

                   <p>So the word we are searching for is "romeo" and the word at our DFS location
                   is "Romeo".  Aha!  One is uppercase and the other is lowercase:  We seem to have
                   a case conversion problem somewhere in our program (we do).</p>

                   <p>This is the end of our example on how you might use Python scripting in LLDB 
                   to help you find bugs in your program.</p>

				</div>
				<div class="postfooter"></div>

    			<div class="post">
    				<h1 class ="postheader">Source Files for The Example</h1>
    				<div class="postcontent">


                </div>
          	    <div class="postfooter"></div>

                  <p> The complete code for the Dictionary program (with case-conversion bug), 
                  the DFS function and other Python script examples (tree_utils.py) used for this 
                  example are available via following file links:</p>

<a href="http://llvm.org/svn/llvm-project/lldb/trunk/examples/scripting/tree_utils.py">tree_utils.py</a>  -  Example Python functions using LLDB's API, including DFS<br>
<a href="http://llvm.org/svn/llvm-project/lldb/trunk/examples/scripting/dictionary.c">dictionary.c</a>  -  Sample dictionary program, with bug<br>
    			
                    <p>The text for "Romeo and Juliet" can be obtained from the Gutenberg Project
                    (http://www.gutenberg.org).</p>
            </div>
      	</div>
	</div>
</div>
</body>
</html>