clone_detect Namespace Reference

Functions
	is_excluded (path)
	tokenize (text, normalise)
	fingerprints (tokens, k, w)
	scan (root, k, w, normalise)
	compare (name_a, a_files, a_corpus, name_b, b_files, b_corpus, a_tokens, b_tokens)
	main ()

Variables
tuple	SOURCE_SUFFIXES = (".c", ".cc", ".cpp", ".cxx", ".h", ".hpp", ".m", ".mm")
tuple	EXCLUDED_DIR_PARTS
	TOKEN_RE = re.compile(, re.VERBOSE | re.DOTALL)
	C_KEYWORDS = frozenset(.split())
tuple	MOD = (1 << 61) - 1
int	BASE = 1000003

Detailed Description

Token-level clone detection between two source trees.

Answers "how much code do these two codebases actually share?" in a way a line diff
cannot. A line diff calls a reindented line changed, a reflowed argument list changed,
and a renamed local variable changed. On a fork that has restyled its tree - Ansel
converted 245 headers from `#pragma once` to include guards, so not one file is
byte-identical to darktable - line comparison understates sharing badly.

This works on TOKENS instead, using winnowing (Schleimer, Wilkerson & Aiken 2003), the
algorithm behind MOSS:

  1. tokenize, discarding whitespace and comments entirely
  2. hash every k-gram of consecutive tokens
  3. in each window of w consecutive hashes keep the minimum

Step 3 is what makes it work. Selecting fingerprints by a property of the hashes rather
than by position means the same code selects the same fingerprints wherever it sits in a
file, so insertions and deletions elsewhere do not shift the match. It guarantees
detecting any shared run of at least k + w - 1 tokens, while storing only about 1/w of
the hashes.

Two normalisations are reported, because they answer different questions:

  strict      identifiers kept. "Is this the same code?" Copy-paste with renaming
              counts as different.
  normalised  identifiers, numbers and strings replaced by placeholders, keywords and
              punctuation kept. "Is this the same code shape?" Catches a function
              carried across and renamed, which for a fork is still inherited code.

Usage:
  python3 tools/clone_detect.py --a /path/to/tree-a --b /path/to/tree-b -o clones.json

Function Documentation

compare()

clone_detect.compare	(		name_a,
			a_files,
			a_corpus,
			name_b,
			b_files,
			b_corpus,
			a_tokens,
			b_tokens
	)

Definition at line 160 of file clone_detect.py.

References max.

Referenced by main().

fingerprints()

clone_detect.fingerprints	(		tokens,
			k,
			w
	)

Winnowed fingerprints of a token list, as a set of hashes.

The k-gram hashes are produced with a rolling polynomial hash, then winnowed with a
monotonic deque so the whole pass is linear rather than O(n*w).

Definition at line 96 of file clone_detect.py.

Referenced by scan().

is_excluded()

clone_detect.is_excluded

(

path

)

Definition at line 72 of file clone_detect.py.

Referenced by scan().

main()

clone_detect.main

(

void

)

Definition at line 194 of file clone_detect.py.

References compare(), main(), and scan().

Referenced by main().

scan()

clone_detect.scan	(		root,
			k,
			w,
			normalise
	)

Fingerprint every production file under root.

Definition at line 131 of file clone_detect.py.

References fingerprints(), is_excluded(), and tokenize().

Referenced by main().

tokenize()

clone_detect.tokenize	(		text,
			normalise
	)

Token strings, with comments and whitespace dropped.

Definition at line 77 of file clone_detect.py.

Referenced by scan().

Variable Documentation

BASE

int clone_detect.BASE = 1000003

Definition at line 69 of file clone_detect.py.

C_KEYWORDS

clone_detect.C_KEYWORDS = frozenset(.split())

Definition at line 59 of file clone_detect.py.

EXCLUDED_DIR_PARTS

tuple clone_detect.EXCLUDED_DIR_PARTS

Initial value:

=  ("/external/", "/tests/integration/", "/image_test/samples/",
                      "/apps/ansel-chart/", "/doxygen-awesome-css/", "/.git/")

Definition at line 43 of file clone_detect.py.

MOD

tuple clone_detect.MOD = (1 << 61) - 1

Definition at line 68 of file clone_detect.py.

SOURCE_SUFFIXES

tuple clone_detect.SOURCE_SUFFIXES = (".c", ".cc", ".cpp", ".cxx", ".h", ".hpp", ".m", ".mm")

Definition at line 42 of file clone_detect.py.

TOKEN_RE

clone_detect.TOKEN_RE = re.compile(, re.VERBOSE | re.DOTALL)

Definition at line 48 of file clone_detect.py.