Code as Data and Machine Learning on Source Code

#CodeAsData
#MLonCode

Vadim Markovtsev

@vadimlearning

Plan

Code as Data ➙ MLonCode ➙ Tools

Code as Data

Source code

a = b * 2

Git

Graphs

graphs everywhere

So you have got graphs...

Measures, e.g. PageRank
- SourceCred
Node embeddings
- node2vec
Clustering, community detection
Gated Graph Neural Networks

Huge codebases

	LoC, 10⁶
Chrome	20
Windows 10	50
Facebook	70
Eclipse Foundation	160
Apache Foundation	190
Google	2,000
GitHub

Huge codebases

	LoC, 10⁶
Chrome	20
Windows 10	50
Facebook	70
Eclipse Foundation	160
Apache Foundation	190
Google	2,000
GitHub	>56,000

Code Lake

github.com/src-d/gitbase

SELECT refs.repository_id
FROM refs
NATURAL JOIN commits
WHERE commits.commit_author_name = 'Johnny Bravo'
    AND refs.ref_name = 'HEAD';

Parsing code

Imports for each commit

SELECT repository_id, commit_hash, file_path,
    uast_extract(uast(blob_content,
                      language(file_path),
                      '//uast:Import/Path'),
                 "Value") AS imports
FROM commit_files NATURAL JOIN blobs
WHERE language(file_path) = 'Go'
    AND array_length(imports) > 0;

Diffs

By line: O(N×D)
By tree node: O(N×D)
By tree node which you really want*: NP-hard, active research

*with "move" operation

AST-annotated line diffs

Flexible, interoperable, fast: choose any two

	Flexible	Interoperable	Fast
Spark	✔	❌	❌
Gitbase	✔	✔	❌
PostgreSQL	❌	✔	😐
ClickHouse	❌	✔	✔
* graph DB	✔	❌	?

1 GB Git -> 1.5 TB SQL

Flattened AST

SELECT r.repo, meta.stars FROM (
    DISTINCT repo FROM uasts WHERE lang='go'
    AND value LIKE 'gopkg.in/src-d/%'
    AND type='Import' AND repo NOT LIKE 'src-d/%'
) r JOIN meta ON r.repo=meta.repo;

sourced.tech/products/
community-edition/

MLonCode

Couples

Idea

If developers often change the same files, there must be something in common.
If files often appear in the same commits, there must be something in common.

word2vec

Context: sentences
Embedding: optimize Pointwise Mutual Information
There are algorithms for explicit co-occurrence matrix
- GloVe
- Swivel

Let's optimize

Pointwise Mutual Information

t-SNE over the embeddings

Lines

Line burndown

git blame foo.go

●2014

func foo() {
  println("bar")
}

●2015

func foo() {
  println("bar")
}
func qux() {
  println("baz")
}

●2016

func foo() {
  println("waldo")
}
const X = 10
func spam() {
  println("baz")
}

Line burndown

Linux

Kaplan-Meier, Erik Bernhardsson

Ownership

Overwrites

To a man with a hammer...

Swivel on the similarity matrix
t-SNE to visualize the embeddings

Time series

CPython contributors

*some are hidden, e.g. Guido

CPython contributors

Use cases

How many active contributors are today?
How did contributors come and leave?
(enterprise) Who worked with who?

Plan

Define the distance
Order by distance (1D)
Cluster by distance (2D)
Query nearest neighbors

Euclidean distance

d₁ = d₂

Dynamic Time Warping

Fast Dynamic Time Warping

Original complexity: O(n²)

Approximation's complexity: O(n)

Python package: fastdtw

"Distance" matrix: O(n²)

Agglomerative clustering?

`seaborn.clustermap?`

Make Patterns Pop Out of Heatmaps with Seriation
by Nicolas Kruchten

Let's get scientific

$$ \min \sum{d_{i,i+1}} $$

Seriation

Ideal for heatmaps and 1D ordering of series
Python package: seriate
Is not always better than agglomerative clustering

HDBSCAN

aka I could not be bothered more by clustering

Beyond 1D

Both t-SNE and UMAP work with an explicit distance matrix
t-SNE works better for 2D (kNN+rank loss)
UMAP works better for 3+D
Best embedding dimensionality: 14 (85% 20NN)

Identifier embeddings

Code naturalness

class ???:
    def connect(self, dbname, user, password, host, port):
        # ...
    def query(self, sql):
        # ...
    def close(self):
        # ...

class Database:
    def connect(self, user, password, host, port):
        self._tcp_socket_connect(host, port)
        try:
            self._authenticate(user, password)
        except AuthenticationError as e:
            self.socket.close()
            raise e from None

Splitting and normalization

            _tcp_socket_connect -> [tcp, socket, connect]
            AuthenticationError -> [authentication, error]
            authentication, authenticate -> authenticate

class Database:
    def connect(self, user, password, host, port):
        self._tcp_socket_connect(host, port)
        try:
            self._authenticate(user, password)
        except AuthenticationError as e:
            self.socket.close()
            raise e from None

database, connect², user², password², host², port², tcp, socket², authenticate², error, close

class Database:
    def connect(self, user, password, host, port):
        self._tcp_socket_connect(host, port)
        try:
            self._authenticate(user, password)
        except AuthenticationError as e:
            self.socket.close()
            raise e from None

connect², user², password², host², port², tcp, socket², authenticate², error, close

class Database:
    def connect(self, user, password, host, port):
        self._tcp_socket_connect(host, port)
        try:
            self._authenticate(user, password)
        except AuthenticationError as e:
            self.socket.close()
            raise e from None

connect, user, password, host, port

class Database:
    def connect(self, user, password, host, port):
        self._tcp_socket_connect(host, port)
        try:
            self._authenticate(user, password)
        except AuthenticationError as e:
            self.socket.close()
            raise e from None

tcp, socket, connect, host, port

class Database:
    def connect(self, user, password, host, port):
        self._tcp_socket_connect(host, port)
        try:
            self._authenticate(user, password)
        except AuthenticationError as e:
            self.socket.close()
            raise e from None

authenticate², user, password, error, socket, close

class Database:
    def connect(self, user, password, host, port):
        self._tcp_socket_connect(host, port)
        try:
            self._authenticate(user, password)
        except AuthenticationError as e:
            self.socket.close()
            raise e from None

authenticate, user, password

class Database:
    def connect(self, user, password, host, port):
        self._tcp_socket_connect(host, port)
        try:
            self._authenticate(user, password)
        except AuthenticationError as e:
            self.socket.close()
            raise e from None

authenticate, error, socket, close

class Database:
    def connect(self, user, password, host, port):
        self._tcp_socket_connect(host, port)
        try:
            self._authenticate(user, password)
        except AuthenticationError as e:
            self.socket.close()
            raise e from None

authenticate, error

class Database:
    def connect(self, user, password, host, port):
        self._tcp_socket_connect(host, port)
        try:
            self._authenticate(user, password)
        except AuthenticationError as e:
            self.socket.close()
            raise e from None

socket, close

Swivel one more time

Nearest to “foo”

afoo
qux
myfoo
baz
mfoo
wibble
dofoo
quux
dfoo
testing
ifoo

Analogies

“bug” - “test” + “expect” = “suppress”

“database” - “query” + “tune” = “settings”

“send” - “receive” + “pop” = “push”

Typos

recieve = receive
grey = gray
calback = callbak = callback

source{d} Enterprise Edition

Tools

github.com/src-d/hercules

Command-line playground for trying new ideas
Data processing: Go (go-git)
Data analysis: Python

github.com/src-d/ml-core

github.com/src-d/ml-mining

>>> from sourced.ml.core.algorithms.token_parser import TokenParser
>>> parser = TokenParser(use_nn=True)
>>> list(parser.split("progressbar"))
['progress', 'bar']
>>> list(parser.split("bigLITTLE"))
['big', 'LITTLE']
>>> list(parser.split("PreSet"))
['preset']

Examples

# Lines evolution
hercules --burndown | labours -m burndown-project

# Couples
hercules --couples | labours -m couples

# Commit time series
hercules --devs | labours -m devs

Datasets

Why?

What to clone?
Cloning many repositories is hard
We don't always need source code

GDPR ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★

Software Heritage Graph Dataset

85mm repositories, 1.1m unique commits
PostgreSQL, Parquet
zenodo.org/record/2583978

Public Git Archive

260k repositories
Git packfile-s
≥50🟊 on GitHub (early 2019)
pga.sourced.tech

Summary

Code-as-Data requires serious infra
src-d/sourced-ce: DIY observability + batteries
MLonCode is much fun
- Couples
- Overwrites
- Time series
- Identifier embeddings
source{d} EE: with MLonCode

Mining Software Repositories

msrconf.org

Thank you

bit.ly/3402LH5

#CodeAsData#MLonCode

Plan

Code as Data

Source code

Git

Graphs

graphs everywhere

So you have got graphs...

Huge codebases

Huge codebases

Code Lake

github.com/src-d/gitbase

Parsing code

Imports for each commit

Diffs

AST-annotated line diffs

Flexible, interoperable, fast: choose any two

1 GB Git -> 1.5 TB SQL

Flattened AST

sourced.tech/products/community-edition/

MLonCode

Couples

Idea

word2vec

Let's optimizePointwise Mutual Information

t-SNE over the embeddings

Lines

Line burndown

Line burndown

Linux

Ownership

Overwrites

To a man with a hammer...

Time series

CPython contributors

CPython contributors

CPython contributors

Use cases

Plan

Euclidean distance

d1 = d2

Dynamic Time Warping

Fast Dynamic Time Warping

"Distance" matrix: O(n2)

Agglomerative clustering?seaborn.clustermap?

Let's get scientific

$$ \min \sum{d_{i,i+1}} $$

Seriation

HDBSCAN

Beyond 1D

Identifier embeddings

Code naturalness

Splitting and normalization

Swivel one more time

Nearest to “foo”

Analogies

Typos

source{d} Enterprise Edition

Tools

github.com/src-d/hercules

github.com/src-d/ml-core

github.com/src-d/ml-mining

Examples

Datasets

Why?

GDPR ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★

Software Heritage Graph Dataset

Public Git Archive

Summary

Summary

Mining Software Repositories

Thank you

#CodeAsData
#MLonCode

sourced.tech/products/
community-edition/

Let's optimize

Pointwise Mutual Information

d₁ = d₂

"Distance" matrix: O(n²)

Agglomerative clustering?

`seaborn.clustermap?`