Token-based authorship information from Git

At LinuxCon North America 2016, Daniel German presented some research that he and others have done to extract more fine-grained authorship information from Git. Instead of the traditional line-based attribution for changes, they took things to the next level by looking at individual tokens in the source code and attributing changes to individuals. This kind of analysis may be helpful in establishing code provenance for copyright and other purposes.

German, who is from the University of Victoria, worked on the project with Kate Stewart of the Linux Foundation and Bram Adams of Polytechnique Montréal. It was a "combination of research plus hacking", he said, and the results were fascinating.

Git and blame

Git is in widespread use and not just for software development. Its pervasiveness is "proof enough that it is an excellent tool". It is also a great archival tool for historical research. Each revision gets stored away and can be compared against other versions using diff and similar utilities. That allows users to see some interesting differences between the versions.

The git blame command is often used to determine who changed a particular line or section of a code file. The GitHub web interface to the blame command gives a side-by-side view of authors and the lines they changed, with links to the revisions where the change was made. It is line-based, which is "sufficiently good for most of the tasks we have", German said.

It is now common for authors of text documents to use Git for version control. He uses it when working on papers with his students and other collaborators. All of the advantages that it provides for source code, such as branching, merging, and blaming, can be applied equally well to text, he said.

But Git allows its users to rewrite history; it provides a lot of tools to clean up the commits in a repository before pushing them to the master. He is a software archaeologist, though, so he would like to see more of the raw history. Quoting Indiana Jones, he said that archaeology is a search for facts, not truth. The more facts there are available, the more history that can be reconstructed.

So the history in Git is likely to be incomplete, but there is still a lot there; what can be done with that? The line-oriented information is fine for many uses, but perhaps looking more deeply inside the lines of code would provide other insights. To research that idea, the project first looked at Git itself. The Git project is likely to be one of the better users of the Git tool, he said. Plus, there was a certain symmetry to using Git to recursively study its own repository.

Tokenize

The idea was to tokenize the source code to track changes at that level. The first step was to decide what the tokens are. The equality operator (==) is an obvious token, as are function and variable names and the like. Strings and comments might be considered a series of tokens, but the project ultimately decided to treat them as a single token.

He showed an example of a line in the Git source repository that had been originally authored by Linus Torvalds in 2006. It was changed twice in 2014, but those changes simply altered the argument list, whereas a look at the tokens would show the actual tokens that changed and in which commits (as shown on the left). German said that he wanted to be able to get that level of detail, "whether it is good or not is a different question".

A tokenizer was developed for C code that essentially acts as a filter on an input file, producing the tokenized output, which German called a "view" of the file. Each language needs its own tokenizer; beyond C, there are tokenizers for Java and Python. C++ is harder, he said, since the researchers didn't want to build a full-blown parser for the languages.

After early experiments with the Git source, the researchers turned to the Linux kernel. The filter was run on every version of every file that appears in the Linux kernel repository. It is not a difficult thing to do, but it takes a few days to do it. The filter produces a file with one token per line.

Then the token files were matched up with the commits in the kernel repository to create views of those commits that were, naturally, checked into a Git repository that mirrored that of the mainline kernel. The goal was to create a repository with history by token, then all of the Git (and GitHub) tools can be used to look at that history.

The kernel project had no version control system until the adoption of BitKeeper in 2001. Some subsystems used CVS, but Linus Torvalds never liked the existing choices, so the net became the repository and changes were sent to him as patches. But there is a repository that Yoann Padioleau put together that covers 0.01 up until 2001. At that point, the BitKeeper era started, which ran until Git was created in 2005. Thomas Gleixner has a Git repository for the BitKeeper period and Torvalds, of course, has a repository from 2005 on.

The earliest repository has low granularity for changes (as it is based on the release tarballs), while the BitKeeper granularity is generally good; the best commit history comes from the Git-era repository, unsurprisingly. Unlike other repositories, PostgreSQL for example, the Linux Git history is not simply made up of squash commits of features without merges. That allows the history to be followed.

Git allows concatenating these three separate repositories into one, effectively. Git also has some other features that were useful for historical analysis. In particular, the rename detection was valuable for the project, German said.

There is one warning he provided about the data: the "author" in Git terms may not actually be the author of the code. It may be that the Git author is simply passing the code along from elsewhere. In addition, refactoring or moving code around within the tree may credit the wrong person with authorship. Refactoring is an area that needs more research, he said, since even lawyers are not able to decide who holds the copyright for refactored code.

Findings

He then presented some of the findings of the research, which looked at changes up through the 4.7 release. The number of tokens was roughly six times larger than the number of non-blank, non-comment lines of code. The number of people that occur in git blame for 4.7 is roughly the same, though (12,005 by lines, 12,087 by tokens).

He was curious to see what function had remained closest to its 0.01 version. It turns out that skip_atoi() contains the most code from 0.01. That kind of makes sense, he said, since the mechanism to convert a string to an integer hasn't needed much change. He put up a slide (seen on the right) that demonstrated the user interface to look at token-level changes. It lists three commits and the number of tokens changed; each commit has its changes in a different color and you can hover over a change to see what the commit message was.

A file that has not changed a whole lot is ctype.c, which consists of a table that maps character values to their types (white space, digits, letters, etc.). If you look at the line-level git blame output, it would seem that Andre Rosa updated most of the file in 2009, but that is not really the case. It turns out that a const was added and tabs were changed to spaces, which made Rosa the "owner" of much of the file. In fact, the bulk of the file tokens date back to the days before version control for the kernel (called "pre-git" in the slides [SlideShare]). In 1996, though, some additional mappings were added, but the commas are still there from the original file, which calls into question who has the copyright for that piece, he said.

At the beginning of the project, he wondered if token-level attribution would make a real difference in the authorship numbers. As it turns out, he was surprised to find that comparing authorship by lines versus tokens does not change things much. "Some people win, some lose", but it all comes out as a wash. He showed a graph of the year of origin of code in Linux as counted by lines and tokens—the graphed points were nearly identical. He also looked only at the kernel directory to see if the core code showed anything different. Again, he was surprised to see that there was essentially no difference.

He produced "top twenty" lists of committers to both Linux and to just the kernel directory by tokens versus lines and the lists looked much the same. There are some differences and a bit of reordering to be sure, but little that stands out. For Linux, the pre-git commits are 5.15% by token, while only 3.81% by line. Two examples did show some differences, though: Joe Perches made 0.64% of changes when measured by lines (number ten on the list), but did not appear in the top twenty (so less than 0.44%) by tokens; on the flip side, Arend van Spriel was number thirteen by tokens (0.6%) but was not present on the lines list (so less than 0.5%). Results for the top twenty committers in the kernel directory showed much the same for tokens versus lines.

German also reported some overall statistics on tokens in commits, which show that the repository is made up of mostly small changes. For non-merge commits that modified .c or .h files, 9.5% added three or fewer tokens and removed three or fewer. 7% only removed tokens, while 3.8% added and removed exactly one token. Adding or removing up to ten tokens was 22.4% and half of all commits added/removed up to 60 tokens. On the other hand, two commits added or removed more than one million tokens.

To measure "churn", the researchers calculated the number of tokens added and subtracted the tokens removed. 10% of commits had zero churn, while 48% had a positive churn value of ten or less; 26% had a negative churn.

He concluded his presentation by saying that the research had shown that there is not much difference between lines and tokens at the large scale. But on the small scale, doing that analysis can provide a more fine-grained view of the evolution of the code.

In answer to some audience questions, German said that there is no reason this feature could not be built into Git itself if that was desirable. As to the intellectual property and legal ramifications of the work, he was a bit non-committal. The output of this work simply adds more information that the courts can work with when deciding those kinds of cases; it is the job of the courts to find the truth, he said.

The code is not currently available. The team plans to release it as open source in the next three to four months. In the meantime, though, for projects that do not have the scale of the kernel, he is willing to process them and make the repositories available to interested projects.

[I would like to thank the Linux Foundation for travel assistance to attend LinuxCon North America in Toronto.]