Local code intelligence for developers and AI agents. Connect code, docs and infrastructure in a persistent graph, with CBM Lens, MCP tools, agent integrations and change-aware test selection.
C aiderastclaude-codecode-analysiscode-intelligencecodexcursorcypherdeveloper-toolsgemini-cligraph-visualizationkilocodeknowledge-graphmcpmcp-servermodel-context-protocolopencodesqlitetree-sitterwindsurf
/*
* minhash.h — MinHash fingerprinting + LSH for near-clone detection.
*
* Computes K=64 MinHash signatures from AST node-type trigrams using
* xxHash with distinct seeds. No external dependencies — xxHash is
* vendored. Pure functions — thread-safe, no shared state.
*
* Workflow:
* 1. cbm_minhash_compute() — during AST extraction (per function)
* 2. cbm_minhash_jaccard() — pairwise similarity (K=64 agreement)
* 3. cbm_lsh_* — locality-sensitive hashing for O(n)
* candidate generation
*/
#ifndef CBM_MINHASH_H
#define CBM_MINHASH_H
#include <stdint.h>
#include <stdbool.h>
/* Number of hash permutations (seeds). Larger K = more accurate Jaccard
* estimate, but more memory per function. 64 gives ±0.12 standard
* error on Jaccard — sufficient for a 0.95 threshold. */
#define CBM_MINHASH_K 64
/* Minimum number of leaf AST tokens required to compute a fingerprint.
* Leaf-only counting is language-agnostic: leaf nodes correspond to
* actual source tokens (identifiers, literals, keywords, operators),
* not grammar-internal structure that varies across parsers.
* 30 leaf tokens ≈ BigCloneBench standard of 50 raw source tokens. */
#define CBM_MINHASH_MIN_NODES 30
/* Default Jaccard threshold for SIMILAR_TO edge emission. */
#define CBM_MINHASH_JACCARD_THRESHOLD 0.95
/* Maximum SIMILAR_TO edges per node (prevents utility function explosion). */
#define CBM_MINHASH_MAX_EDGES_PER_NODE 10
/* LSH parameters: b bands × r rows. Threshold ≈ (1/b)^(1/r). */
#define CBM_LSH_BANDS 32
#define CBM_LSH_ROWS 2
/* ── MinHash fingerprint ─────────────────────────────────────────── */
/* A MinHash signature: K minimum hash values, one per seed. */
typedef struct {
uint32_t values[CBM_MINHASH_K];
} cbm_minhash_t;
/* Opaque tree-sitter node — forward declared to avoid pulling in
* tree_sitter/api.h from every consumer. */
typedef struct TSNode TSNode;
/* Compute MinHash fingerprint for a function body's AST.
*
* Walks the subtree rooted at `func_body`, normalises leaf node types
* (identifiers → "I", strings → "S", numbers → "N", type annotations
* → "T"), builds trigrams, and hashes each trigram with K seeds.
*
* Returns true and fills `out` on success.
* Returns false if the body has fewer than CBM_MINHASH_MIN_NODES
* normalised tokens (fingerprint not meaningful). */
bool cbm_minhash_compute(TSNode func_body, const char *source, int language, cbm_minhash_t *out);
/* Compute exact Jaccard similarity between two MinHash signatures.
* Returns value in [0.0, 1.0]. */
double cbm_minhash_jaccard(const cbm_minhash_t *a, const cbm_minhash_t *b);
/* Hex encoding: K uint32 values × 8 hex chars each = 512 chars. */
enum { CBM_MINHASH_HEX_LEN = 512 };
/* Buffer size for hex-encoded fingerprint including NUL. */
enum { CBM_MINHASH_HEX_BUF = 513 };
/* JSON overhead for ,"fp":"..." wrapper (key + quotes + comma + colon). */
enum { CBM_MINHASH_JSON_OVERHEAD = 10 };
void cbm_minhash_to_hex(const cbm_minhash_t *fp, char *buf, int bufsize);
/* Decode a hex string back to a MinHash signature.
* Returns true on success. */
bool cbm_minhash_from_hex(const char *hex, cbm_minhash_t *out);
/* ── LSH index ───────────────────────────────────────────────────── */
/* Opaque LSH index handle. */
typedef struct cbm_lsh_index cbm_lsh_index_t;
/* Entry stored in the LSH index. */
typedef struct {
int64_t node_id;
const cbm_minhash_t *fingerprint;
const char *file_path; /* for same-file tagging */
const char *file_ext; /* for same-language filtering */
const char *qualified_name; /* canonical pair-ownership tie-break: node ids
vary run-to-run under parallel extraction,
qualified names do not (determinism) */
} cbm_lsh_entry_t;
/* Create a new LSH index. */
cbm_lsh_index_t *cbm_lsh_new(void);
/* Insert an entry into the LSH index. */
void cbm_lsh_insert(cbm_lsh_index_t *idx, const cbm_lsh_entry_t *entry);
/* Query candidates similar to the given fingerprint.
* Returns candidate entries via `out` (caller does NOT free the array
* — it is owned by the index). Sets `count`.
* NOT thread-safe: uses index-internal result buffer. */
void cbm_lsh_query(const cbm_lsh_index_t *idx, const cbm_minhash_t *fp,
const cbm_lsh_entry_t ***out, int *count);
/* Thread-safe variant: writes candidates into caller-provided buffer.
* `out_buf` must have room for at least `out_cap` pointers.
* Returns the actual candidate count (may exceed out_cap — result is truncated). */
int cbm_lsh_query_into(const cbm_lsh_index_t *idx, const cbm_minhash_t *fp,
const cbm_lsh_entry_t **out_buf, int out_cap);
/* A dedup set one thread reuses across many queries. Starting a query costs a
* generation increment, not a fresh 131 KB zeroed table: the similarity pass
* allocated one per query, 5.3 GB of churn over 42 k queries on the Go corpus
* (waste sanitizer, 2026-09-17). Not shareable between threads. */
typedef struct cbm_lsh_seen cbm_lsh_seen_t;
cbm_lsh_seen_t *cbm_lsh_seen_new(void);
void cbm_lsh_seen_free(cbm_lsh_seen_t *seen);
/* cbm_lsh_query_into with a caller-owned dedup set: same candidates, same order. */
int cbm_lsh_query_into_seen(const cbm_lsh_index_t *idx, const cbm_minhash_t *fp,
const cbm_lsh_entry_t **out_buf, int out_cap, cbm_lsh_seen_t *seen);
/* Free the LSH index and all internal storage. */
void cbm_lsh_free(cbm_lsh_index_t *idx);
#endif /* CBM_MINHASH_H */