Writing a New Indexer

Kythe indexers emit directed graph data as a stream of entries that can represent either nodes or edges. These have various encodings, but for simplicity we’ll use JSON. To get started, let’s write a script kythe-browse.sh that will turn a stream of JSON-formatted Kythe entries into a format that our example code browser can read. Put it in your Kythe root; it will clobber the directories //graphstore and //tables.

You can test this with a very short entry stream. The only tricky part here is that Kythe fact values, when serialized to JSON, are base64-encoded. This ensures that they can be properly deserialized later, since fact values may contain arbitrary binary data, but JSON strings permit only UTF-8 characters. ZmlsZQ== is file and SGVsbG8sIHdvcmxkIQ== is Hello, world!.

You can check that http://localhost:8080/#hello?corpus=example shows ‘Hello, world!’.

A Kythe graph can be encoded using two basic data types. The first, called a VName, uniquely picks out a node in the graph. VNames have five string-valued fields. Entries record both facts about individual nodes and edges between them. As described in the documentation, we only need to emit the forward versions of edges (those that are described in the schema); the Kythe pipeline takes care of generating reverse edges as needed for efficiency.

We’ll encode VNames and entries in a straightforward way; in particular, we represent entries as objects, where the target’s presence or absence determines if the entry represents an edge between nodes or a fact about a single node (respectively). Our fact and edge convenience functions also assume that all of the fact and edge names we’ll use are underneath the /kythe prefix, since we’re following the Kythe schema. This prefix is a requirement of the schema, not of the data model.

You can follow along at home with node.js and the following definitions:

With this representation, our example database becomes:

VNames have an alternate URI-style encoding. VNames encoded in this way are called tickets; tickets and VNames are semantically interchangeable. This encoding is used where it is inconvenient or not possible to store VNames in a more structured format. You can use Kythe URIs when interacting with the Kythe command-line tool:

kythe://example?path=hello is the URI encoding of the VName used in the example graph above.

Kythe stores file content in its graph. The http_server binary used in our kythe-browse.sh script doesn’t look in your filesystem for a file to present to the Web browser; it instead reads the text fact off of a graph node.

Since every node in the graph has a VName, we’ll need to be able to build one for any source file your indexer might refer to. In our small example above, our test file had the path hello in the corpus example. It is up to you how to determine the corpus (and possibly root) to which a node belongs. It is best to keep this configurable; other Kythe indexers use a vnames.json file to choose the VName fields based on regular expressions over paths.

All Kythe graph nodes should have a node/kind fact. For files, this kind is file. This means that each file should have at least two associated facts. You can see the JSON representation of the resulting entries above, where we used them to test the kythe-browse.sh script.

Imagine we have the following simple program:

We want to record the relationship between the reference to foo on the second line and its definition on the first line. First, we should build a representation for the variable foo itself. To summon a node into existence, we need a VName and a node kind. The schema already defines a node kind for variables. If there is no existing way to model foo in the schema, you’re free to invent one of your own; the schema is intended to be open-ended. Be aware that tools that consume Kythe data may not be able to offer as much help with custom kinds, but should always be tolerant of them.

We’ve already seen that VNames for files contain path, root, and corpus components. (In fact, the schema requires that the other components of a file VName be empty.) We need to come up with assignments to these, plus signature and language, that uniquely refer to our variable foo. Getting this right can be subtle. Here are some guidelines:

We’ll use foo's defining file’s preset components, the language ex, and the signature foo#0 (to mean "the zeroth binding of foo at global scope"). Using the functions we’ve defined above, we emit the following entry:

We can see it in the graph with the kythe tool (after running kythe-browse.sh to generate ./tables):

Notice how the # was URI-encoded in the ticket.

Most of the work in testing a tool that produces Kythe data boils down to checking that different anchors in example source text are linked to the correct nodes and edges. From this starting point, you can make sure that other parts of the semantic graph are properly formed.

Given a description of these anchors and their desired relationships, performing the necessary checks doesn’t require any information specific to the language being analyzed. With this in mind, we built the Kythe verifier. The verifier accepts a stream of Kythe entries and source files, the latter of which have been annotated with goals. Each goal describes entries that the verifier must (or must not) find in its input stream. Since some parts of these entries are uninteresting to test—for example, the exact encoding used for a anchor’s VName is unimportant—parts of a goal may be replaced with variables for which the verifier will try to find an assignment.

Just as we were able to drive the Kythe pipeline with only a list of JSON entries, so too can we drive the verifier with only those entries and a list of goals. This script, kythe-verify-json.sh, reads JSON entries from standard in and passes them (and its arguments) to the verifier:

We can write a rule file that checks whether we have any file nodes at all and call it test.goals:

The //- prefix tells the verifier which lines to look for goals on. It’s meant to be ignored as a comment by most languages. Of course, some languages (like Python) use different character sequences to denote comments, so it can be changed with a command-line flag.

We ask the verifier to check that the goals can be met with the entries we wrote out earlier in this document:

Since we do have a node with kind file, the verifier exits with a zero error code without printing any diagnostics.

If we had written an unsatisfiable goal—let’s say we made a spelling mistake and asked for a node with kind elif instead:

the verifier will protest (and return a nonzero exit code):

If your graph is small, it can be useful to display it graphically:

This graph will render in xdot.py as something like:

There’s only one node in this graph, but it’s the file node that we asked the verifier to find; notice how it is outlined in blue. The verifier applies this highlighting to nodes that are matched against variables in the goals (here, FileNode).