Cross-Indexing Assignment

You may have noticed that debuggers (e.g., gdb) do a remarkably good job of understanding source-code-level information entered from the keyboard.  Among other things, they know which declaration of a function, variable, or type is live at each point in a program.  This is because the compiler (when invoked with appropriate command-line switches) includes symbol table information in its assembly language output.  Your task in the current assignment is to leverage this information to implement a web-based cross-reference tool. 

Gcc is capable of producing symbol table information in a variety of formats.  One of the most comprehensive of these—and the one used by default on Linux—is known as DWARF.  It captures details about variables, functions, typedefs, etc., including the locations in the source code (file and the line number), at which they are declared.  To embed DWARF information in your object file, compile with

   gcc -g3 -o myprogram myfile1.c myfile2.c ...
The -g3 switch instructs gcc to include detailed debugging information, including macro definitions, in the symbol table. 

After compilation, DWARF information can be extracted from an executable or object file in any of several ways.  Arguably the easiest is to use the dwarfdump tool, which you can find in ~cs254/bin/ on the csug machines. 

You task in this assignment is to write a scripting program—call it xref—that uses the output of dwarfdump to construct a set of web pages, one per source file, that contain links from uses of identifiers to their declarations.  You may write your program in Perl, Python, Ruby, or (with instructor’s permission) some other scripting language.  If you’re undecided, I recommend either Perl (because of its ubiquity in systems administration) or Ruby (because of its elegant merger of imperative and functional programming).  Python has the disadvantage of substantially less succinct notation for pattern matching, which you’ll be doing a lot of in this assignment. 

Your xref program should be run in a directory containing an executable program (built with -g3) and a collection of C source files from which the program was built (all .c and .h files other than standard library header files).  When invoked with the name of the executable (e.g., myprogram) as a command-line argument, xref should

  1. run dwarfdump myprogram and examine the output to learn the names of the source files, the identifiers used in those files, the locations where those identifiers are declared (file, line), and the scopes in which they are visible. 
  2. convert the source code to HTML, one page per file.  Within each file, uses of a user-defined name should be links to the point of definition, which may be on a different page.  Clicking on an identifier will thus move your browser to the definition.  (The browser’s back button will return you to the use.) 
  3. assemble the HTML files into a subdirectory named HTML, with an extra file index.html that contains a list of all the source files (with links), a special link to main, and information about when and where the xref tool was run. 

Some parts of this assignment are more difficult than others.  Global variables and functions are relatively easy; you should get them working first, and then move on to more difficult parts.  For full credit you will also need to handle local variables and formal parameters.  For extra credit you can add typedef names, struct and union names (“tags”), struct and union field names, enum constants, labels, and/or macros, all with correct scoping.  Note that you should not create links for declarations and definitions. You may ignore uses of names that are built-in or defined in standard library header files.  You will get lots of partial credit for getting parts of this assignment working, even if you don’t get all of it. 

Extracting scope information from DWARF is somewhat tricky.  For each function (subprogram) or nested scope (lexical_block) in a source file, DWARF identifies the address ranges of the generated code.  More precisely, the DIE (debugging information entry) for the subprogram or lexical_block specifies the addresses of the first instruction in that scope and of the next instruction not in that scope.  A separate debug_line table indicates, for each line of the source file that generated instructions, the address of the first such instruction.  (The DWARF specification allows column numbers as well, but gcc produces zeros for these.)  As a general rule, if block B runs from address Bs to Be, then the source code of B runs from line i through line j, where i is the line with address Bs in the debug_line table and j is the line before the line with address Be.  Unfortunately, this rule is only approximate.  It can be off a little due to declarations, multiple statements on a single line, or blocks that start on the same line where the previous block ended.  You may need to experiment to produce a “what scope is this name in” function that works well most of the time. 

Be warned that building a perfect cross-indexer means performing all the syntactic and semantic analysis required by a real compiler for the source language.  You are not building a compiler, so your cross-indexer will not be perfect.  Your goal should be to make it work as well as possible given the information available from simple pattern matching in the source code and the dwarfdump output.

Note that the C preprocessor macro-expands both the contents of header files and the definitions of macros.  By default it produces line number tags in its output that allow the main compiler to know what came from each header file.  DWARF will thus capture type declarations, function headers (prototypes), and macros from header files, in a form where you can recover the source file name and line number.  It may not give you what you need if header files contain variable definitions or code, but that’s bad C programming style anyway, so you’re allowed to ignore it. 

Note also that C uses separate “name spaces” (unrelated to the namespaces of C++) for (1) labels, (2) struct/union tags, and (3) everything else.  Moreover the field (member) names of every struct and union type have, effectively, their own nested scope.  So it’s ok to have

    struct foo {int i; int j} my_foo;
    struct bar {int i; int j} my_bar;
    int foo;
    goto foo;
    foo: my_bar.i = 3
         my_foo.i = 4
all in the same scope.  The three meanings of foo (struct tag, integer variable, and label) are distinct, and the occurrence of a dot (.) after my_bar on the second-to-last line means that the following i is looked up in the scope of struct bar’s field names.  The extra credit portions of the assignment will require you to differentiate among the three meanings of foo in the above.  This can be hard to do correctly: consider things like
    struct foo my_func(int a, int b) { ...
    int n = my_func(sqrt(12345), 67890).i;  /* which i? */
Get the main assignment working before you try the extra credit. 

Division of labor and writeup

As in previous assignments, you may work alone or in teams of two.  If you choose to work in pairs, one possible division of labor is for one partner to write the code that inspects the dwarfdump output and the other to use this information to create the HTML files.  If you do this, be very careful to agree on the information you need, and read each other’s code to look for errors. 

Be sure to follow all the rules on the Grading page.  As with all assignments, use the turn-in script:  ~cs254/bin/TURN_IN.  Put your write-up in a README.txt or README.pdf file in the directory in which you run the script.  Be sure to describe any features of your code that the TAs might not immediately notice.  To illustrate the functionality of your code, you may want to include test data, contained in subdirectories. 


Extra Credit suggestions

  1. Extend your code to support additional kinds of identifiers:  typedef names, struct and union tags, structure and union field names, enum constants, labels, and/or macros. 
  2. Provide a search facility in your web pages, to quickly get to an identifier. 
  3. “Syntax-color” the code in your pages, so that comments, declarations, keywords, constants, etc., are visibly distinguished. 
  4. Provide links to names declared in standard header files. 
  5. Extend your work to support additional programming languages. 

Trivia Assignment

Before the end of the day on Wednesday, October 26, send e-mail to to containing answers to the following questions: 

  1. Are you working alone or in a team?  If a team, who is your partner? 
  2. The subprogram and lexical_block DIEs in DWARF specify their starting address as an absolute number and their ending address as an offset from the starting address.  In the output from dwarfdump what notation is used for these numbers (decimal?  hex?  octal?) 
  3. Give a regular expression in Perl that matches only with syntactically valid email addresses.  (A description of the syntax can be found on Wikipedia.  Note that you don't have to capture every nuance of the Internet standard.  The point is to make sure you have a basic grasp of the Perl RE syntax.) 
  4. How can you represent the characters ‘<’ and ‘>’ in HTML?  (Normally they delimit tags.) 


Wednesday November 9, 11:59 pm; no extensions. 
Last Change: 04 November 2016 / Michael Scott's email address