C-xrefactory - a C/Yacc refactoring and code browsing tool - Design Documentation

cxrefCore is the core container. It does all the work when it comes to finding and reporting references to symbols, communicating refactoring requests as well as storing reference information for longer term storage and caching.

Although c-xref can be used as a command line tool, which can be handy when debugging or exploring, it is normally used in "server" mode. In server mode the communication between the editor extension and the cxrefCore container is a back-and-forth communication using a non-standard protocol over standard pipes.

The responsibilities of cxrefCore can largely be divided into

At this point it seems like refactorings are performed as separate invocations of c-xref rather than through the server interface.

The EditorExtension container is responsible for plugging into an editor of choice and handle the user interface, buffer management and executing the refactoring edit operations.

Currently there is only one such extension supported, for Emacs, although there existed code, still available in the repo history, for an extension for jEdit which hasn’t been updated, modified or checked for a long time and no longer is a part of this project.

The References database stores crossreferencing information for symbols visible outside the module it is defined in. Information about local/static symbols are not stored but gathered by parsing that particular source file on demand.

Currently this information is stored in a somewhat cryptic, optimized text format.

This storage can be divided into multiple files, probably for faster access. Symbols are then hashed to know which of the "database" files it is stored in. As all crossreferencing information for a symbol is stored in the same "record", this allows reading only a single file when a symbol is looked up.

Lexing/scanning is performed in two layers, one in lexer.c which seems to be doing the actual lexing into lexems which are put in a lexembuffer. This contains a sequence of encoded and compressed symbols which first has a LexemCode which is followed by extra data, like Position. These seems to always be added but not always necessary.

The higher level "scanning" is performed, as per ususal, by yylex.c. lexembuffer defines some functions to put and get lexems, chars (identifiers and file names?) as well as integers and positions.

At this point the put/get lexem functions take a pointer to a pointer to chars (which presumably is the lexem stream in the lexembuffer) which it also advances. This requires the caller to manage the LexemBuffer’s internal pointers outside and finally set them right when done.

It would be much better to call the "putLexem()"-functions with a lexemBuffer but there seems to be a few cases where the destination (often dd) is not a lexem stream inside a lexemBuffer. These might be related to macro handling or caching.

As the refactoring functions need some amount of semantic information, in the sense of information gathered during parsing, this information is collected in various ways when c-xref calls the "sub-task" to do the parsing required.

Two structures hold information about various things, among which are the memory index at certain points of the parsing. Thus it is possible to verify e.g. that a editor region does not cover a break in block or function structure. This structure is, at the point of writing, called parsedInfo and definitely need to be tidied up.

The current implementation of the reference database is file based, with an optimized storage format.

There is limited support to automatically keep these updated during an edit-compile cycle, you might have to update manually now and then.

The project settings (or command line options) indicate where the file(s) are created and one option controls the number of files to be used, -refnum.

This file (or files) contains compact, but textual representations of the cross-reference information. Format is somewhat complex, but here are somethings that I think I have found out:

So a line might say

The line identifies the file with id 12205. The file was last included in an update of refs at sometime which is identified by 1522108169 (mtime), has not been part of a full update of xrefs, was mentioned on the command line. (I don’t know what the 'a' means…​) Finally, the file name itself is 84 characters long.

All information about an externally visible symbol is stored in one, and only one reference file, determined by hashing the linkname of the symbol. So it will always suffice to read one reference file when consulting the reference database (in the form of CXFILE) for a symbol.

The reading of the CXFILE format is controlled by `scanFunctionTable`s. These consists of a list of entries, one for each key/tag/recordCode (see format description above) that the scan will process.

As the reference file reading encounters a key/tag/recordCode it will consult the table and see if there is an entry pointing to a handler function for that key/tag/recordCode. If so, it will be called.

The editor invokes a new c-xref process for the following cases:

There is some magical editor buffer management happening inside of c-xref which is not clear to me at this point. Basically it looks like the editor-side tries to keep the server in sync with which buffers are opened with what file…​

At this point I suspect that -preload <file1> <file2> means that the editor has saved a copy of <file1> in <file2> and requests the server to set up a "buffer" describing that file and use it instead of the <file1> that recides on disk.

This is essential when doing refactoring since the version of the file most likely only exists in the editor, so the editor has to tell the server the current content somehow, this is the -preload option.

The initial invocation of the edit server creates a process with which communication is over stdin/stdout using a protocol which from the editor is basically a version of the command line options.

When the editor has delivered all information to the server it sends 'end-of-option' as a command and the edit server processes whatever it has and responds with <sync> which means that the editor can fetch the result in the file it named as the output file using the '-o' option.

Setting the emacs variable c-xref-debug-mode forces the editor to copy the content of such an output file to a separate temporary file before re-using it.

For some interactions the editor starts a completely new and fresh c-xref process, see below. And actually you can’t do refactorings using the server, they have to be separate calls. (Yes?) I have yet to discover why this design choice was made.

Communication between the editor and the server is performed using text through standard input/output to/from c-xref. The protocol is defined in src/protocol.tc and must match editor/emacs/c-xrefprotocol.el.

The definition of the protocol only caters for the server→editor part, the editor→server part consists of command lines resembling the command line options and arguments, and actually is handled by the same code.

The file protocol.tc is included in protocol.h and protocol.c which generates definitions and declarations for the elements through using some macros.

There is a similar structure with c-xrefprotocol.elt which includes protocol.tc to wrap the PROTOCOL_ITEMs into defvars.

There is also some Makefile trickery that ensures that the C and elisp impementations are in sync.

The editor fires up a server and keeps talking over the established channel (elisp function 'c-xref-start-server-process'). This probably puts extra demands on the memory management in the server, since it might need to handle multiple information sets and options (as read from a .cxrefrc-file) for multiple projects simultaneously over a longer period of time. (E.g. if the user enters the editor starting with one project and then continues to work on another then new project options need to be read, and new reference information be generated, read and cached.)

FINDINGS:

The editor server is started using the appropriate command line option and then it keeps the communication over stdin/stdout open.

The editor part sends command line options to the server, which looks something like (from the read_xrefs test case):

In this case the "-olcxpush" is the operative command which results in the following output

As we can see from this interaction, the server will handle (all?) input as a command line and manage the options as if it was a command line invocation.

This explains the intricate interactions between the main program and the option handling.

The reason behind this might be that a user of the editor might be editing files on multiple projects at once, so every interrogation/operation needs to clearly set the context of that operation, which is what a user would do with the command line options.

It seems that all on-line editing server functions have an olcx prefix, "On-Line C-Xrefactory", maybe…​

One thing that really confused me in the beginning was that the editor, primarily Emacs, don’t use the actual server that it has started for refactoring operations (and perhaps for other things also?). Instead it creates a separate instance with which it talks to about one refactoring.

I’ve just managed to create the first automatic test for refactorings, olcx_refactory_rename. It was created by running the sandboxed emacs to record the communication and thus finding the commands to use.

Based on this learning it seems that a refactoring typically is a single invocation of c-xref with appropriate arguments (start & stop markers, the operation, and so on) and the server then answers with a sequence of operations, like

I haven’t investigated the internal flow of such a sequence, but it is starting to look like c-xref is internally re-reading the initialization, I’m not at this point sure what this means, I hope it’s not internal recursion…​

Each type of refactoring has it’s own little "language". E.g. extracting a method/function using -refactory -rfct-extract-function will return something like

So there is much logic in the editor for this. I suspect that the three <str> parts are

If this is correct then all extractions copy the region verbatim and then the server only have to figure out how to "glue" that to a semantically correct call/argument list.

As a side note the editor asks for a new name for the function and then calls the edit server with a rename request (having preloaded the new source file(s) of course).

Dechiffrering the interaction between an editor and the edit server in c-xrefactory isn’t easy. The protocol isn’t very clear or concise. Here I’m starting to collect the important bits of the invocation, the required and relevant options and the returned information.

The test cases for various refactoring operations should give you some more details.

All of these require a -p (project) option to know which c-xref project options to read.

Mostly c-xrefactory does its own memory management. It uses a number of different strategies, which has/had its own macros.

The memory handling for options deserves special explanation and attention.

When defining options, from the command line, options file or piped from an editor process, the strings need to be preserved and stored. This is done by "dynamically" allocating such areas in the "options memory", optMemory.

But since this is a integral part of the options structure, whenever an Options structure is copied, special care has to be taken so that the fields in the target structure points into the memory area of the target structure and not, as they did in the original structure, into the memory of the source structure.

There are functions that, through tricky memory arithmetic, adjust all pointers to point correctly. To this end, all memory locations in an Options structure are collected in a linked list which can be traversed.

There are three possible sources for options.

Not all options are relevant in all cases.

All options sources uses exactly the same format so that the same code for decoding them can be used.

When the editor has a file open it needs to "belong" to a project. The logic for finding which is very intricate and complicated.

In this code there is also checks for things like if the file is already in the index, if the configuration file has changed since last time, indicating there are scenarios that are more complicated (the server, obviously).

But I also think this code should be simplified a lot.

The yylex module has the standard interface required by any yacc-based parser, which is a simple yylex(void) function.

Read and write the CXref database in "plain" text format.

The current file format for the cross-reference data consists of records with the general format

There are two important types of lines, a file information line and a symbol information line.

The actual keys are documented in cxfile.c, but here is an example file information line:

First we have two simple value/key pairs. We see "32571f" indicating that this is file information for file with file number 32571.

Secondly we have "1715027668m". This is the modification time of the file which is stored to be able to see if that file has been updated since the reference database was last written.

And the third part is "21:/usr/include/ctype.h", which is of a record type that is a bit more complex. The number is the length of the value. The ':' indicates that the record is a filename.

Options has its own allocation using optAlloc which allocates in a separate area, currently part of the options structure and utilizing "dynamic allocation" (dm_ functions on the Memory structure).

The Options structure are copied multiple times during a session, both as a backup (savedOptions) and into a separate options structure used by the Refactorer (refactoringOptions).

Since the options memory is then also copied, all pointers into the options memory need to be updated. To be able to do this, the options structure contains lists of addresses that needs to by "shifted".

When an option with a string or string list value is modified the option is registered in either the list of string valued options or the list of string list valued options. When an options structure is copied it must be performed using a deep copy function which "shifts" those options and their values (areas in the options memory) in the copy so that they point into the memory area of the copy, not the original.

After the deep copy the following point into the option memory of the copy

C-xref started (probably) as a cross-referencer for the languages supported (C, Java, C++), orginally had the name "xref" which became "xrefactory" when refactoring support was added. And when Mariàn released a "C only" version in 2009 most of all the "xref" references and names was changed to "c-xref". So, as most software, there is a history and a naming legacy to remember.

Here are some of the conventions in naming that are being used:

The source code for c-xrefactory was using a very old C style with a separate proto.h where all prototypes for all externally visible functions were placed. Definitions are all over the place and it was hard to see where data is actually declared. This must change into module-oriented include-strategy.

Of course this will have to change into the modern x.h/x.c externally visible interface model so that we get clean modules that can be unittested.

The function prototypes have been now moved out to header files for each "module". Some of the types have also done that, but this is still a work in progress.

There are very few unittests at this point, only covering single digit percent of the code. The "units" in this project are unclear and entangled so creating unittests is hard since it was not build to be tested, test driven or even clearly modularized.

All unittests use Cgreen as the unittest framework. If you are unfamiliar with it the most important point is that it can mock functions, so you will find mock implementations of all external functions for a module in a corresponding <module>.mock file.

Many modules are at least under test, meaning there is a <module>_tests.c in the unittest directory. Often only containing an empty test.

In the tests directory you will find tests that exercise the external behaviour of c-xref. Some tests actually do only that, they wouldn’t really count as tests.

Most acceptance tests are hacks at this point, Make-scripts tweaked until it produces some expected output. But at least they get the coverage up (working our way up to the mid 60%), and more are added as bugs are found so they provide increasing confidence when developing.

There are two basic strategies for the tests:

Some tests do not even test its output and only provide coverage.

Some tests do a very bad job at verifying, either because my understanding at that time was very low, or because it is hard to verify the output. E.g. the "test" for generate references are only grepping the CXrefs files for some strings, not verifying that they actually point to the correct place.

Hopefully this will change as the code gets into a better state and the understanding grows.

Since all(?) c-xref operation rely on an options file which must contain absolute file paths (because the server runs as a separate process) it must be generated whenever the tests are to be run in a different location (new clone, test was renamed, …​).

This is performed by using a common template in tests and a target in tests/Maefile.boilerplate.

Each test should have a clean target that removes any temporary and generated files, including the .c-xrefrc file and generated references. This way it is easy to ensure that all tests have updated .c-xrefrc files.

Since many operations are performed from the editor, and the editor starts an "edit server" process, many tests need to emulate this behaviour.

The edit server session is mostly used for navigation. Refactorings are actually performed as separate invocations of c-xref.

In utils there is a server_driver.py script, which will take as input a file containing a sequence of commands. You can use this to start an edit, refactory or reference server session and then feed it with commands in the same fashion as an editor would do. The script also handles the communication through the buffer file (see [Editor Interface](./Design:-Editor-Interface)).

You can relatively easy re-create a sequence of interactions by using the sandboxed Emacs in tests/sandboxed_emacs.

There are two ways to use it, "make spy" or "make pure". With the "spy" an intermediate spy is injected between the editor and the edit server, capturing the interaction to a file.

With "pure" you just get the editor setup with c-xref-debug-mode and c-xref-debug-preserve-tmp-files on. This means that you can do what ever editor interactions you want and see the communication in the *Messages* buffer. See [Editor Interface](./Design:-Editor-Interface) for details.

Once you have figure out which part of the *Messages* buffer are interesting you can copy that out to a file and run utils/messages2commands.py on it to get a file formatted for input to server_driver.py.

utils/covers.py is a Python script that, in some enviroments, can list which test cases execute a particular line.

This is handy when you want to debug or step through a particular part of the code. Find a test that covers that particular line and run it using the debugger (usually make debug in the test directory).

Synopsis:

utils/sandboxed starts a sandboxed Emacs that uses the current elisp code and the c-xref from src. This allows you to run a test changes without having to polute your own setup.

This actually runs the tests/sandboxed_emacs pure version, which also sets up a completely isolated Emacs environment with its own packages loaded, configuration etc. See below.

Synopsis:

Static memory (SM_ prefix) are static areas allocated by the compiler which is then indexed using a similarly named index variable (e.g. ftMemory and ftMemoryIndex), something the macros took advantage of. These are

One special case of static memory also exist:

These areas cannot be extended, when it overruns the program stops.

Once the FILL-macros was removed, we could move the enum-generation to use the actual c-xref. So from now on we build c-xref directly from the sources in the repo. Changes to any enums will trigger a re-generation of the enumTxt-files but since the enumTxt-files are only conversion of enum values to strings any mismatch will not prevent compilation, and it would even be possible to a manual update. This is a big improvement over the previous situation!

As indicated in FILL macros the bootstrapping of FILL-macros has finally and fully been removed.

Gone is also the compiler_defines.h, which was just removed without any obvious adverse effects. Maybe that will come back and bite me when we move to more platforms other than linux and MacOS…​

Left is, at this point, only the enumTxt generation, so most of the text below is kept for historical reasons.

c-xref uses a load of structures, and lists of them, that need to be created and initialized in a lot of places (such as the parsers). To make this somewhat manageable, c-xref itself parses the strucures and generates macros that can be used to fill them with one call.

c-xref is also bootstrapped into reading in a lot of predefined header files to get system definitions as "preloaded definitions".

Why this pre-loading was necessary, I don’t exactly know. It might be an optimization, or an idea that was born early and then just kept on and on. In any case it creates an extra complexity building and maintaining and to the structure of c-xref.

So this must be removed, see below.

The bootstrapping uses c-xref's own capability to parse C-code and parse those structures and spit out filling macros, and some other stuff.

This is done using options like `-task_regime_generate' which prints a lot of data structures on the standard output which is then fed into generated versions of strFill, strTdef(no longer exists) and enumTxt by the Makefile.

The process starts with building a c-xref.bs executable from checked in sources. This compile uses a BOOTSTRAP define that causes some header files to include pre-generated versions of the generated files (currently strFill.bs.h and enumTxt.bs.h) which should work in all environments.

After the c-xref.bs has been built, it is used to generate strFill and enumTxt which might include specific structures for the current environment.

HOWEVER: if FILL macros are used for structures which are different on some platforms, say a FILE structure, that FILL macro will have difference number of arguments, so I’m not sure how smart this "smart" generation technique actually is.

TODO: Investigate alternative approaches to this generate "regime", perhaps move to a "class"-oriented structure with initialization functions for each "class" instead of macros.

In options.h there are a number of definitions which somehow are sent to the compiler/preprocessor or used so that standard settings are the same as if a program will be compiled using the standard compiler on the platform. At this point I don’t know exactly how this conversion from C declarations to compile time definitions is done, maybe just entered as symbols in one of the many symboltables?

Typical examples include "__linux" but also on some platforms things like "fpos_t=long".

I’ve implemented a mechanism that uses "gcc -E -mD" to print out and catch all compiler defines in compiler_defines.h. This was necessary because of such definitions on Darwin which where not in the "pre-programmed" ones.

TODO?: As this is a more general approach it should possibly completely replace the "programmed" ones in options.c?

To be able to print the string values of enums the module generate.c (called when regime was RegimeGenerate) could also generate string arrays for all enums. By replacing that with some pre-processor magic for the few that was actually needed (mostly in log_trace() calls) we could do away with that whole "generate" functionality too.

(Last commit with enum generation intact is https://github.com/thoni56/c-xrefactory/commit/aafd7b1f813f2c17c684ea87ac87a0be31cdd4c4.)

For some cases the string representing the value of an Enum is needed. c-xref handles this using the "usual" 'parse code and generate' method. The module generate.c does this generation too.

Also in options.h some standard-like include paths are added, but there is a better attempt in getAndProcessGccOptions() which uses the compiler/preprocessor itself to figure out those paths.

TODO?: This is much better and should really be the only way, I think.

Since at bootstrap there must exist FILL-macros with the correct field names this strategy is an obstacle to cleaning up the code since every field is referenced in the FILL macros. When a field (in a structure which are filled using the FILL macro) changes name, this will make initial compilation impossible until the names of that field is also changed in the strFill.bs.h file.

One way to handle this is of course to use c-xrefactory itself and rename fields. This requires that the project settings also include a pass with BOOTSTRAP set, which it does.

I’ve started removing this step. In TODO.org I keep a hierarchical list of the actions to take (in a Mikado kind of style).

The basic strategy is to start with structures that no other structure depends on. Using the script utils/struct2dot.py you can generate a DOT graph that shows those dependencies.

Removal can be done in a couple of ways

The strTdef.h was generated using the option -typedefs as a part of the old -task_regime_generate strategy and generated typedef declarations for all types found in the parsed files.

I also think that you could actually merge the struct definition with the typedef so that strTdef.h would not be needed. But it seems that this design is because the structures in proto.h are not a directed graph, so loops makes that impossible. Instead the typedefs are included before the structs:

This is now ideomatically solved using the structs themselves: