phpcpd-native

A native (C) reimplementation of phpcpd's clone-detection engine, built on top of PHP's own lexer (via libphptok/) and verified byte-for-byte against the shipped phpcpd code at every layer.

It detects Type-1/2 (Rabin-Karp), Type-3 / gapped (ConQAT suffix tree), and reordered (token-bag) clones, walks directories like phpcpd, and renders its exact text report. On phpcpd's own source tree it produces output identical to PHP's — 250 clones in 0.45s vs PHP's 44.8s (~100× faster) on the suffix-tree hot path (after a profile-guided optimization; see Performance).

Quick start

make                 # builds libphptok, then build/phpcpd-detect
make test            # runs every differential suite against real phpcpd

# scan a directory (walks it like phpcpd: --suffix .php, prune excludes):
build/phpcpd-detect --min-tokens 40 --format text src/

# Type-3 (suffix tree, edit-distance-bounded gapped clones):
build/phpcpd-detect --algorithm suffixtree --edit-distance 5 --format text src/

# reorder-tolerant, excluding a subtree:
build/phpcpd-detect --algorithm tokenbag --exclude '*/vendor/*' --format text .

Building

Prerequisites: a C compiler, re2c, and python3 (the last two only to (re)generate libphptok from the vendored grammar). php is needed only to run the differential tests — never to build or run the detector. No third-party C libraries. The default build is optimized (-O2) and dead-code-stripped.

macOS (Apple clang, brew install re2c):

make

Produces build/phpcpd-detect, a self-contained executable whose only dynamic dependency is /usr/lib/libSystem.B.dylib (the OS libc). macOS does not support fully-static executables — there is no static libSystem — so this is as standalone as macOS allows. make static there prints a note to that effect.

Linux (gcc/clang, apt install re2c / apk add re2c):

make                 # optimized dynamic binary (links the system libc)
make static          # fully-static binary — no dynamic deps at all

For a clean fully-static link, use a musl toolchain:

# Debian/Ubuntu
sudo apt install musl-tools
make static CC=musl-gcc

# Alpine (musl is the system libc)
apk add build-base musl-dev re2c python3
make static

The result is a single fully-static build/phpcpd-detect (ldd reports "not a dynamic executable") — copy it to any Linux box, no runtime deps, no PHP.

The toolchain (CC, CFLAGS, LDFLAGS) is threaded into the libphptok sub-build, so a musl/static build is consistent across both. A build system like ninja is unnecessary here — the target graph is small and make drives it directly; make -jN parallelizes it.

Options

Flag	Meaning
--min-tokens N	minimum clone length in tokens (default 70)
--min-lines M	minimum clone length in lines (default 5)
--max-file-size SIZE	skip files larger than SIZE (default 1M; K/M/G suffix; 0 disables). Skipped files are announced on stderr.
--algorithm rabin-karp|suffixtree|tokenbag	engine (default rabin-karp)
--edit-distance E	suffix-tree gap budget (Type-3)
--head-equality H	suffix-tree head-equality bound
--min-similarity S	token-bag overlap threshold (default 0.7)
--fuzzy / --type-anchored	Type-2 normalization modes
--suffix .ext	include files ending in .ext (repeatable; .php always on)
--exclude PATTERN	skip paths matching a glob or substring (repeatable)
--format text|json|sarif|pmd|ndjson	stdout report format (default ndjson)
--log-json FILE / --log-sarif FILE / --log-pmd FILE	also write that report to FILE
--verbose	include the duplicated source in text output
--list-files	print the resolved file list and exit

The --max-file-size guard (default 1M) exists because a single generated / minified / data-array PHP file — the kind that never holds meaningful duplication anyway — can dominate an exact matcher's cost, since its window count grows with its token count and self-matches inside it drive an O(matches²) merge. Skipping such files keeps a scan bounded and announces each skip on stderr so nothing is silently dropped. Pass --max-file-size 0 to scan everything.

Exit code: 1 when clones are found, 0 otherwise (and 1 on errors) — so it works directly as a CI gate:

# fail the build if any duplication is found, and publish a SARIF report:
build/phpcpd-detect --min-tokens 60 --exclude '*/vendor/*' \
    --format text --log-sarif cpd.sarif src/

Positional arguments may be files or directories. If any is a directory, the tool walks it like phpcpd's FileFinder — applying --suffix/--exclude, pruning excluded directories, then deduping and sorting. An explicit file list is processed in the given order (first occurrence of a window is side A of a clone).

Layers

Each layer is a faithful port of a specific piece of phpcpd, gated by its own differential test against the shipped code.

• libphptok/ — the PHP tokenizer, a self-contained subproject: vendors PHP's own lexer from php-src, compiles it free of the Zend runtime, and matches PhpToken::tokenize() byte-for-byte. Independently useful; its maintenance (tracking php-src versions) is decoupled from the detector. Also ships a tree-sitter compatibility shim.
• signature layer (src/signature.c) — port of DefaultStrategy::tokenize(): builds phpcpd's FileTokens (5-byte-per-token signature + line tables) from libphptok's stream. The shared input to every engine.
• Rabin-Karp detector (src/detector.c, src/clone.c, src/md5.c) — port of DefaultStrategy::scan() + the CodeCloneMap model (content-id dedup + multi-file merge, duplicated-line accounting). Type-1/2.
• suffix-tree engine (src/suffixtree.c) — port of SuffixTreeStrategy + ApproximateCloneDetectingSuffixTree (Ukkonen construction, banded edit-distance matcher, SubstitutionCost). Type-3 / gapped.
• token-bag engine (src/tokenbag.c) — port of TokenBagStrategy + BlockExtractor (SourcererCC-style: per-function token multisets, IDF stopword filtering, inverted-index candidate pruning). Catches reordered duplication the contiguous matchers miss.
• reporters (src/report.c) — ports of Log\Text, Log\Json, Log\Sarif, and Log\PMD. The JSON/SARIF emitters reproduce PHP's json_encode (4-space pretty-print, unescaped slashes, \uXXXX for non-ASCII); the PMD emitter reproduces DOMDocument's output. All hand-rolled (no serialization library) so the zero-dependency static binary is preserved, and each is differential-tested byte-for-byte.

Verification

The methodology is the same at every layer: a PHP oracle drives the real phpcpd class (DefaultStrategy, SuffixTreeStrategy, Log\Text) over a set of files and dumps its output; the native tool dumps the same; diff must be empty. Testing against shipped code (not a re-derivation) means a misreading of the algorithm cannot hide in both sides at once.

Suite	make target	What it proves
signature	test-sig	signature bytes + line tables == DefaultStrategy::tokenize() (177 checks: 59 files × 3 modes)
clone	test-clone	clone sets == real DefaultStrategy incl. 3-way merges (124 clones over phpcpd src/)
text	test-text	rendered report == Log\Text (3 modes × verbose/non)
suffix-tree	test-suffixtree	JSON + text == real SuffixTreeStrategy, incl. gapped fixtures & phpcpd src/ (250 clones)
token-bag	test-tokenbag	JSON + text == real TokenBagStrategy, incl. reordered-clone fixtures & phpcpd src/
finder	test-finder	resolved file list == real FileFinder (suffix/glob/substring excludes, whole tree)
reports	test-report	JSON / SARIF / PMD == real Log\Json/Sarif/PMD (empty, 3-way, gapped, whole tree)

Along the way the differential caught real behavioral quirks that had to be reproduced to match: the token_get_all() stale-line fallback, CodeClone's memoized-empty-indent in verbose mode, the CodeCloneMapIterator sort order, and the deduped-file-set participant counting.

Correctness anchors: MD5 and CRC-32 are bit-identical to PHP's md5()/crc32(); libphptok token ids are PHP's real T_* values.

Why this design

phpcpd's FileTokens isolates a clean seam: token_get_all() produces a flat token stream, and everything downstream (suffix tree, token-bag, clone map) is a pure algorithm over that stream with zero PHP semantics. The tokenizer is the one part that must match PHP exactly and is painful to reimplement — so it's vendored from php-src and verified (that's libphptok), while the algorithmic core is a direct port. The detector uses only libphptok's public API.

Performance

The suffix tree is the only CPU-heavy engine (Rabin-Karp and token-bag are ~0.01s on phpcpd's src/). A sampling profile of a heavy run pointed entirely at the edit-distance DP — fill_ed + match_word were ~85% of samples, while CRC-32, MD5, tokenization, and the edge hash table registered zero. So the win was in-tree, not a library: the DP matrix was switched from lazily-allocated rows (a function call + branch on every cell access) to a flat contiguous buffer (one index-multiply), and is_structural was precomputed per token. That cut the src/ run from 1.2s to 0.45s (~2.7×) with byte-identical output — proven by the unchanged test-suffixtree differential. No dependency added; the static binary is intact. (Lesson: profile before optimizing — every "obvious" library swap here would have bought nothing.)

Layout

Makefile                 builds libphptok, then the detector; test targets
src/
  signature.{h,c}        FileTokens builder (DefaultStrategy::tokenize)
  detector.{h,c}         Rabin-Karp scan (DefaultStrategy::scan)
  suffixtree.{h,c}       ConQAT suffix-tree engine (Type-3)
  tokenbag.{h,c}         SourcererCC token-bag engine (reorder-tolerant)
  finder.{h,c}           directory walker (Util\FileFinder)
  clone.{h,c}            CodeClone / CodeCloneMap model
  report.{h,c}           text reporter (Log\Text)
  md5.{h,c}              MD5 (window hash + clone content id)
  tool/
    phpcpd-detect.c      the CLI
    filetokens-dump.c    signature-layer dump (for test-sig)
bin/
  dump-*.php             PHP oracles driving the real phpcpd classes
  run-*-differential.sh  the differential runners (use /opt/homebrew/bin/bash)
tests/
  fixtures/              exact / 3-way / Type-2 / unique clone fixtures
  fixtures-t3/           Type-3 (gapped) fixtures
libphptok/               the tokenizer subproject (own README + tests)

Status

Feature-complete for practical use, all byte-exact vs phpcpd:

• all three engines — Rabin-Karp (Type-1/2), suffix tree (Type-3), token-bag (reorder-tolerant)
• directory walker (FileFinder) with --suffix / --exclude
• all four reporters — text / JSON / SARIF / PMD — plus --log-* files
• CI exit code (1 on clones)

Runs ~100× faster than the PHP original on the suffix-tree hot path, ships as a self-contained (macOS) or fully-static (Linux/musl) binary with no third-party dependencies.

The incremental-index cache is intentionally not ported — a full native run is already fast enough that per-file caching isn't worth the complexity. The only remaining niceties are cosmetic: framework presets and a --help/--version banner.