The code behind GitHub's new Code Navigation
Tags: github, devtools, codeanalysis
Published: 2019-08-26 13:33:00

---
title: The code behind GitHub's new Code Navigation
published: true
tags: github,dev-tools,code analysis,opensource
canonical_url: https://blog.codenamev.com/the-code-behind-github-code-navigation/
---

GitHub [recently announced two new code navigation features](https://help.github.com/en/articles/navigating-code-on-github):

1. Jump to definition – quickly view the source for any given method.
2. Find all references – Identify all references of a function within the same repo.

![The code behind GitHub's new Code Navigation](https://blog.codenamev.com/content/images/2019/08/jump-to-definition-tab.png)


I have been waiting a long time for these features to surface, and best of all, the code behind all this is open source!

From the top-level, they're using a Haskell library called [Semantic](https://github.com/github/semantic).  Semantic can _parse_, _analyze_, and _compare_ source code.  As of the last update to this post, it supports Ruby, JavaScript, TypeScript, Python, Go, PHP, Java, JSON, JSX, Haskell, and Markdown.

For a full list of examples, check out the [Semantic usage docs](https://github.com/github/semantic/blob/master/docs/examples.md).  It comes with a great CLI that allows you to:

### Generate parse trees

```
$ semantic parse test.A.py
(Statements
  (Annotation
    (Function
      (Identifier)
      (Identifier)
      (Return
        (Identifier)))
    (Empty))
  (Call
    (Identifier)
    (Call
      (Identifier)
      (TextElement)
      (Empty))
    (Empty)))
```
<figcaption>Generate an abstract syntax tree (AST)</figcaption>

### Generate syntax aware diffs

```
$ semantic diff test.A.py test.B.py
(Statements
  (Annotation
    (Function
    { (Identifier)
    ->(Identifier) }
      (Identifier)
      (Return
        (Identifier)))
    (Empty))
  (Call
    (Identifier)
    (Call
    { (Identifier)
    ->(Identifier) }
      (TextElement)
      (Empty))
    (Empty)))
```

### Display import call graphs

```
semantic graph main.py | dot -Tsvg > main.html && open main.html
```

![The code behind GitHub's new Code Navigation](https://blog.codenamev.com/content/images/2019/08/import_graph.svg)

### Display call graphs

```
semantic graph --calls main.py | dot -Tsvg > main.html && open main.html
```

![The code behind GitHub's new Code Navigation](https://blog.codenamev.com/content/images/2019/08/call_graph.svg)

## Making Sense of Your Code

The code parsing is done with the [tree-sitter](https://github.com/tree-sitter/tree-sitter) library which appears to be C with a handful of language bindings ([the cli is in Rust](https://github.com/tree-sitter/tree-sitter/tree/master/cli)!).

> [Tree-sitter] can build a concrete syntax tree for a source file and efficiently update the syntax tree as the source file is edited

Languages are supported by writing language-specific parsers.  These parsers primarily consist of two parts:

1. **Grammar** –  contains various rules for how the language is formatted
2. **Lexical Analysis** – patterning individual character groups (for [lexing](https://en.wikipedia.org/wiki/Lexical_analysis)).

Example Grammar for parsing simple ruby methods from [tree-sitter-ruby](https://github.com/tree-sitter/tree-sitter-ruby):


```
{
  "name": "ruby",
  "word": "identifier",
  "rules": {
    "method": {
      "type": "SEQ",
      "members": [
        {
          "type": "STRING",
          "value": "def"
        },
        {
          "type": "SYMBOL",
          "name": "_method_rest"
        }
      ]
    }
  }
}
```
<figcaption><a href="https://github.com/tree-sitter/tree-sitter-ruby/blob/master/src/grammar.json#L5-L46">https://github.com/tree-sitter/tree-sitter-ruby/blob/master/src/grammar.json</a></figcaption>

Tree-sitter has [an _awesome_ Playground](http://tree-sitter.github.io/tree-sitter/playground) where you can explore the parse trees it generates for any given code.

When you feed code to the Semantic library, it generates parse trees using tree-sitter, and then uses the [language's grammar](https://github.com/github/semantic/blob/master/docs/grammar-development-guide.md) (e.g. from tree-sitter-ruby) to parse the parse trees and map AST nodes  (many of which are already available from the library itself for: [literals](https://github.com/github/semantic/blob/master/src/Data/Syntax/Literal.hs), [expressions](https://github.com/github/semantic/blob/master/src/Data/Syntax/Expression.hs), [statements](https://github.com/github/semantic/blob/master/src/Data/Syntax/Statement.hs), and [types](https://github.com/github/semantic/blob/master/src/Data/Syntax/Type.hs)).

While they hope to [drop this step in the future](https://github.com/github/semantic/blob/master/docs/adding-new-languages.md#faqs), once the AST nodes are mapped, a second round of parsing is done to wrap them into data structures the library can comprehend (for more on this, [see the "Assignment" documentation](https://github.com/github/semantic/blob/master/docs/assignment.md)).

There are quite a few more things that happen to _analyze_ and _compare_ source code, but I'll leave the explanation it to their [great documentation on program analysis](https://github.com/github/semantic/blob/master/docs/program-analysis.md).

Thank you GitHub :heart:  Keep up the solid work :smile: