Cross-Indexing Assignment

You may have used tags in emacs or vi.  These provide a cross-referencing mechanism whereby the user can jump from a use of a variable in a program source file to that variable’s definition.  Tags are supported by special index files, typically generated by the standard etags utility. 

As it turns out, etags is a fairly simply pattern-matching tool, with little understanding of the syntax or semantics of the source files that it reads.  In particular, it doesn’t understand scopes.  If you have six variables named i in your program, etags creates an index entry for each, and emacs (and some variants of vi) will cycle through them on demand.  This may be better than searching for the right declaration without the help of tags, but it isn’t as handy as finding the right tag automatically. 

You may also have noticed that debuggers (e.g. gdb) are aware of which declaration of a variable 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 smarter, web-based cross-reference tool. 

Gcc is capable of producing symbol table information in a variety of formats (see the man page).  One of the most comprehensive of these is known as DWARF.  It captures details about variables, functions, typedefs, etc. and where in the source code (file and the line number), they are declared.  To embed DWARF information in your object file, compile with

   gcc -gdwarf-2 -g3 myfile1 myfile2 ...
The -g3 switch instructs gcc to include macro definitions in the symbol table. 

One way to obtain the information you will need for your cross-reference tool would be to parse the DWARF directives in the compiler’s assembly language output.  If you want to see what this looks like, compile with

   gcc -S -gdwarf-2 -g3 -fverbose-asm myfile1 myfile2 ...
This would require, however, that you examine each file of a multi-file linked program.  Better is to use the combined information found in the final object file.  There are library packages that allow you to read this information from C or other languages. 

For this assignment you are to take a third approach.  The readelf program reads an ELF (Executable and Linking Format) object file and outputs a textual representation of all the symbolic information it contains, including the DWARF information.  You are to write a scripting program, xref, that uses the output of readelf to construct a set of web pages, one per source file, that contain links from uses of identifiers to their declarations. 

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

  1. run readelf --debug-dump object_file and parse 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 active. 
  2. convert the source code to HTML, one page per file.  Each identifier in an HTML file should be a link to the point of definition, which may be on a different page.  Clicking on an identifier will thus move your browser to the definition. 
  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 need to handle variables, formal parameters, functions, typedef names, and struct and union names, with correct scoping.  You will get lots of partial credit for getting some of this working, even if you don’t get all of it.  You will get extra credit for additional kinds of identifiers (see below). 

Extracting scopes from DWARF is difficult.  The TA will be posting some hints soon; keep an eye on the Blackboard discussion group.

The C preprocessor macro-expands both the contents of include 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 include file.  DWARF will capture type declarations, function headers (prototypes), and macros from include files, in a form where you can recover the source file name and line number.  It may not give you what you need if include files contain variable declarations or code, but that’s bad C programming style anyway, so you’re allowed to ignore it. 

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 parses the readelf 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. 

Resources

Extra Credit suggestions

  1. Extend your code to support additional kinds of indentifiers:  structure and union field names, enum constants, macros, labels. 
  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. Extend your work to support additional programming languages. 

Trivia Assignment

Trivia questions for this assignment can be found in Blackboard.  They are due before the beginning of class on Tuesday, October 23

MAIN DUE DATE:

Friday November 5, 5:00 pm; no (more) extensions.  (Don’t forget to do the A5 trivia by next Tuesday.) 
Last Change: 01 November 2007 / Michael Scott's email address