src/clone_signals/norm.rs
//! **The normalised body** — a function's text with every name the workspace
//! chose replaced by a role placeholder, literals by their kind, attributes,
//! doc comments, comments and layout gone.
//!
//! Tokens come from the ONE lexer this repo allows (`proc-macro2`, in
//! [`crate::mimir_subclone::flat_tokens`]) over the function's own text — the
//! lines of its driver span at the commit, cut exactly as the `embeddings`
//! feed cuts them ([`crate::vector::fnvec::cut`]). No second parser: an
//! identifier's ROLE is read from its neighbours only.
//!
//! | token | becomes |
//! |---|---|
//! | keyword (`let`, `match`, `self`, …) | itself |
//! | the language's own vocabulary ([`KEEP`]: primitives, prelude and common std types, std macros, common std methods) | itself |
//! | `pub`, `pub(crate)` … | nothing (visibility is not behaviour) |
//! | identifier before `!` + a group | `M1`, `M2` … (a macro the workspace named) |
//! | identifier before `(` or `::<` | `F1` … (a function or method) |
//! | identifier after `.` | `D1` … (a field) |
//! | identifier starting upper case | `T1` … (a type, trait or variant) |
//! | identifier after `'` | `L1` … (a lifetime / label) |
//! | any other identifier | `V1` … (a local, a parameter, a module) |
//! | literal | `#s` string, `#c` char, `#n` number |
//!
//! Numbers count first occurrences per role, so a CONSISTENT rename (every
//! `kill` → `delete`, every `pid` → `id`) gives the same text: the Type-2 clone
//! of the literature. The function's own name is the first `F`.
//!
//! The text is rendered in ONE canonical layout (a line per `;`, `{`, `}`;
//! four spaces per brace level), so a reformatted copy is the same text too.
//! Its SHA-256 is the function's **exact key** (`exact_clones`) and the key of
//! its vector in the normalised model space (`semantic_clones`); the role
//! classes without their numbers ([`NormBody::classes`]) are what the
//! MinHash of `near_clones` shingles.
use std::collections::HashMap;
use std::sync::OnceLock;
use crate::mimir_subclone::FlatTok;
/// The rule, part of every stored shape: a change of the rule is a new set
/// of shapes (the old ones are not read), never a mix of two rules.
pub const SHAPE: &str = "shape-v1";
/// Keywords, kept verbatim (the same list the subclone shapes keep, plus the
/// 2018+ reserved words that occur in code).
const KEYWORDS: &[&str] = &[
"as", "async", "await", "break", "const", "continue", "crate", "dyn", "else", "enum", "extern", "false", "fn", "for", "if", "impl", "in", "let", "loop",
"match", "mod", "move", "mut", "ref", "return", "self", "Self", "static", "struct", "super", "trait", "true", "type", "union", "unsafe", "use", "where",
"while", "yield", "_",
];
/// **The language's own vocabulary** — names nobody in the workspace chose,
/// whose meaning is the same everywhere: what a function DOES with them is
/// its behaviour, so they stay. A data list, decided once; every other name
/// is a placeholder.
pub const KEEP: &[&str] = &[
// primitives
"u8", "u16", "u32", "u64", "u128", "usize", "i8", "i16", "i32", "i64", "i128", "isize", "f32", "f64", "bool", "char", "str",
// prelude + common std types and traits
"Option", "Some", "None", "Result", "Ok", "Err", "Vec", "String", "Box", "Rc", "Arc", "Weak", "Cell", "RefCell", "Mutex", "RwLock", "HashMap", "HashSet",
"BTreeMap", "BTreeSet", "VecDeque", "BinaryHeap", "Path", "PathBuf", "File", "Duration", "Instant", "SystemTime", "Cow", "Iterator", "IntoIterator",
"Default", "Clone", "Copy", "Debug", "Display", "Fn", "FnMut", "FnOnce", "Send", "Sync", "Sized", "From", "Into", "TryFrom", "TryInto", "AsRef", "AsMut",
"PartialEq", "Eq", "PartialOrd", "Ord", "Ordering", "Hash", "Hasher", "ToString", "Formatter", "Error", "Read", "Write", "BufRead", "BufReader",
"BufWriter", "Command", "Stdio", "Ipv4Addr", "SocketAddr", "AtomicBool", "AtomicUsize", "AtomicU64", "Pin", "Future", "PhantomData",
// std modules (path segments)
"std", "core", "alloc", "fmt", "io", "fs", "mem", "ptr", "env", "process", "thread", "sync", "collections", "path", "time", "iter", "ops", "cmp", "str",
"string", "vec", "net", "atomic", "mpsc", "hash", "num", "slice", "char", "convert",
// std macros
"println", "print", "eprintln", "eprint", "format", "write", "writeln", "vec", "assert", "assert_eq", "assert_ne", "debug_assert", "debug_assert_eq",
"panic", "unreachable", "todo", "unimplemented", "matches", "format_args", "concat", "stringify", "include_str", "include_bytes", "env", "dbg",
];
/// **Common std methods / trait methods** — kept only where they are USED as
/// one (after `.`, before `(`, beside `::`). A local or a parameter that
/// happens to be called `min`, `map` or `count` is a name the workspace
/// chose: it becomes a placeholder like any other.
pub const METHODS: &[&str] = &[
"iter", "iter_mut", "into_iter", "map", "filter", "filter_map", "flat_map", "flatten", "fold", "collect", "len", "is_empty", "push", "push_str", "pop",
"insert", "remove", "get", "get_mut", "contains", "contains_key", "unwrap", "expect", "unwrap_or", "unwrap_or_else", "unwrap_or_default", "ok_or",
"ok_or_else", "ok", "err", "and_then", "or_else", "map_err", "map_or", "map_or_else", "as_ref", "as_mut", "as_str", "as_bytes", "as_slice", "to_string",
"to_owned", "to_vec", "clone", "into", "from", "new", "default", "sort", "sort_by", "sort_by_key", "sort_unstable", "dedup", "extend", "chain", "zip",
"enumerate", "rev", "take", "skip", "next", "any", "all", "find", "find_map", "position", "count", "sum", "min", "max", "min_by_key", "max_by_key",
"first", "last", "split", "split_once", "splitn", "trim", "trim_start", "trim_end", "starts_with", "ends_with", "strip_prefix", "strip_suffix", "join",
"lines", "chars", "bytes", "parse", "entry", "or_insert", "or_insert_with", "or_default", "keys", "values", "values_mut", "retain", "drain", "truncate",
"with_capacity", "cloned", "copied", "lock", "read", "borrow", "borrow_mut", "fmt", "eq", "cmp", "partial_cmp", "is_some", "is_none", "is_ok",
"is_err", "replace", "swap", "to_lowercase", "to_uppercase", "to_ascii_lowercase", "saturating_sub", "saturating_add", "wrapping_add", "wrapping_mul",
"checked_add", "checked_sub", "abs", "pow", "sqrt", "spawn", "send", "recv", "await", "display", "exists", "join", "read_to_string", "create_dir_all",
"with_extension", "file_name", "extension", "parent", "as_path", "to_path_buf", "elapsed", "now", "as_millis", "as_secs", "into_inner", "unwrap_err",
];
fn keep() -> &'static std::collections::HashSet<&'static str> {
static K: OnceLock<std::collections::HashSet<&'static str>> = OnceLock::new();
K.get_or_init(|| KEYWORDS.iter().chain(KEEP).copied().collect())
}
fn methods() -> &'static std::collections::HashSet<&'static str> {
static K: OnceLock<std::collections::HashSet<&'static str>> = OnceLock::new();
K.get_or_init(|| METHODS.iter().copied().collect())
}
/// The identifier at `i` is used as a method / path segment: after `.`,
/// before `(`, or beside `::`.
fn used_as_method(toks: &[FlatTok], i: usize) -> bool {
let colon = |t: Option<&FlatTok>| matches!(t, Some(FlatTok::Punct(':', _)));
let prev = i.checked_sub(1).map(|p| &toks[p]);
matches!(prev, Some(FlatTok::Punct('.', _)))
|| matches!(toks.get(i + 1), Some(FlatTok::Open('(')))
|| (colon(toks.get(i + 1)) && colon(toks.get(i + 2)))
|| (colon(prev) && colon(i.checked_sub(2).map(|p| &toks[p])))
}
/// One function's normalised body.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct NormBody {
/// The canonical text (what the normalised model is handed).
pub text: String,
/// SHA-256 of [`Self::text`]: the exact key.
pub exact: String,
/// Normalised tokens (attributes and `pub` left out).
pub tokens: usize,
/// Per token, its role CLASS hashed (`V`, `F`, `T`, a keyword, a kept name,
/// a punctuation, a literal kind) — the alphabet of the MinHash shingles.
pub classes: Vec<u64>,
}
fn fnv(s: &str) -> u64 {
s.bytes().fold(0xcbf2_9ce4_8422_2325u64, |h, b| (h ^ b as u64).wrapping_mul(0x0100_0000_01b3))
}
/// The role of the identifier at `i`.
fn role(toks: &[FlatTok], i: usize) -> char {
let prev = i.checked_sub(1).map(|p| &toks[p]);
let next = toks.get(i + 1);
let FlatTok::Ident(name) = &toks[i] else { return 'V' };
if matches!(prev, Some(FlatTok::Punct('\'', _))) {
return 'L';
}
if matches!(next, Some(FlatTok::Punct('!', _))) && matches!(toks.get(i + 2), Some(FlatTok::Open(_))) {
return 'M';
}
let turbofish = matches!(next, Some(FlatTok::Punct(':', true))) && matches!(toks.get(i + 2), Some(FlatTok::Punct(':', _))) && matches!(toks.get(i + 3), Some(FlatTok::Punct('<', _)));
let declared = matches!(prev, Some(FlatTok::Ident(k)) if k == "fn");
if declared || matches!(next, Some(FlatTok::Open('('))) || turbofish {
return 'F';
}
if matches!(prev, Some(FlatTok::Punct('.', _))) {
return 'D';
}
if name.trim_start_matches("r#").chars().next().is_some_and(char::is_uppercase) {
return 'T';
}
'V'
}
/// Normalise a function's text. `None` when it does not tokenise.
pub fn normalize(text: &str) -> Option<NormBody> {
let toks = crate::mimir_subclone::flat_tokens(text)?;
Some(normalize_tokens(&toks))
}
/// [`normalize`] over tokens already lexed.
pub fn normalize_tokens(toks: &[FlatTok]) -> NormBody {
let mut numbers: HashMap<(char, &str), usize> = HashMap::new();
let mut per_role: HashMap<char, usize> = HashMap::new();
let mut words: Vec<(String, String, bool)> = Vec::with_capacity(toks.len()); // (rendered, class, joint)
let mut i = 0usize;
while i < toks.len() {
match &toks[i] {
FlatTok::Ident(s) if s == "pub" => {
// `pub`, `pub(crate)`, `pub(in a::b)`: visibility is not behaviour
if matches!(toks.get(i + 1), Some(FlatTok::Open('('))) {
let mut depth = 0i32;
let mut j = i + 1;
while j < toks.len() {
match toks[j] {
FlatTok::Open(_) => depth += 1,
FlatTok::Close(_) => {
depth -= 1;
if depth == 0 {
break;
}
}
_ => {}
}
j += 1;
}
i = j + 1;
} else {
i += 1;
}
continue;
}
FlatTok::Ident(s) => {
let bare = s.trim_start_matches("r#");
if keep().contains(bare) || (methods().contains(bare) && used_as_method(toks, i)) {
words.push((bare.to_string(), bare.to_string(), false));
} else {
let r = role(toks, i);
let n = *numbers.entry((r, s.as_str())).or_insert_with(|| {
let c = per_role.entry(r).or_default();
*c += 1;
*c
});
words.push((format!("{r}{n}"), r.to_string(), false));
}
}
FlatTok::Lit(k) => words.push((format!("#{k}"), format!("#{k}"), false)),
FlatTok::Punct(c, joint) => words.push((c.to_string(), c.to_string(), *joint)),
FlatTok::Open(c) | FlatTok::Close(c) => words.push((c.to_string(), c.to_string(), false)),
}
i += 1;
}
// the canonical layout
let mut text = String::new();
let mut depth = 0usize;
let mut at_start = true;
let mut glue = false;
let newline = |text: &mut String, at_start: &mut bool| {
if !*at_start {
text.push('\n');
*at_start = true;
}
};
for (w, _, joint) in &words {
match w.as_str() {
"}" => {
depth = depth.saturating_sub(1);
newline(&mut text, &mut at_start);
}
_ => {}
}
if at_start {
text.push_str(&" ".repeat(depth));
} else if !glue {
text.push(' ');
}
text.push_str(w);
at_start = false;
// a lifetime's quote glues to its name; `::`, `->`, `=>`, `==` glue
glue = *joint || w == "'";
match w.as_str() {
"{" => {
depth += 1;
newline(&mut text, &mut at_start);
}
";" | "}" => newline(&mut text, &mut at_start),
_ => {}
}
}
let text = text.trim_end().to_string();
NormBody { exact: crate::vector::chunk::hash_text(&text), tokens: words.len(), classes: words.iter().map(|(_, c, _)| fnv(c)).collect(), text }
}
#[cfg(test)]
mod tests {
use super::*;
const KILL: &str = "pub fn kill(pid: u32, table: &mut HashMap<u32, Proc>) -> Option<Proc> {
let found = table.remove(&pid)?;
// stop it
found.stop_all();
Some(found)
}";
/// KILL consistently renamed, reformatted, commented differently, `pub(crate)`.
const ERASE: &str = "/// Erase one entry.
#[inline]
pub(crate) fn erase(id: u32, registry: &mut HashMap<u32, Proc>) -> Option<Proc> {
let hit = registry.remove(&id)?; hit.stop_all();
Some(hit)
}";
#[test]
fn a_consistent_rename_reformatted_and_recommented_is_the_same_normalised_text() {
let (a, b) = (normalize(KILL).unwrap(), normalize(ERASE).unwrap());
assert_eq!(a.text, b.text);
assert_eq!(a.exact, b.exact);
assert!(!a.text.contains("kill") && !a.text.contains("pid") && !a.text.contains("stop"), "{}", a.text);
// the language's own vocabulary stays: that is what the function DOES
assert!(a.text.contains("HashMap") && a.text.contains("remove") && a.text.contains("Some"), "{}", a.text);
assert!(a.text.starts_with("fn F1 ( V1 : u32"), "{}", a.text);
}
#[test]
fn an_inconsistent_rename_or_another_literal_kind_is_another_text() {
let a = normalize("fn a(x: u32, y: u32) -> u32 { x + y }").unwrap();
let b = normalize("fn b(p: u32, q: u32) -> u32 { p + p }").unwrap();
assert_ne!(a.exact, b.exact, "x + y is not x + x");
let c = normalize("fn c() -> u32 { 1 }").unwrap();
let d = normalize("fn d() -> &'static str { \"1\" }").unwrap();
assert_ne!(c.exact, d.exact);
let e = normalize("fn e() -> u32 { 7 }").unwrap();
assert_eq!(c.exact, e.exact, "a number is a number");
}
#[test]
fn roles_are_read_from_the_neighbours() {
let n = normalize("fn go<'a>(s: &'a Store) -> usize { let n = s.items.len(); my_mac!(n); helper::<u8>(n) }").unwrap();
assert!(n.text.contains("'L1"), "{}", n.text);
assert!(n.text.contains(". D1 . len"), "{}", n.text);
assert!(n.text.contains("M1 !"), "{}", n.text);
assert!(n.text.contains("F2 ::"), "{}", n.text);
assert!(n.text.contains("T1"), "{}", n.text);
}
/// `min` / `map` as a parameter are names the workspace chose; `.min(`
/// and `.map(` are the language's own.
#[test]
fn a_std_method_name_used_as_a_local_is_a_placeholder() {
let a = normalize("fn a(floor: u32, layout: &[u32]) -> usize { layout.iter().filter(|x| **x > floor).map(|x| x.min(&9)).count() }").unwrap();
let b = normalize("fn b(min: u32, map: &[u32]) -> usize { map.iter().filter(|x| **x > min).map(|x| x.min(&9)).count() }").unwrap();
assert_eq!(a.text, b.text);
assert!(a.text.contains(". map (") && a.text.contains(". min ("), "{}", a.text);
assert!(normalize("fn c() { std::mem::take(&mut v); }").unwrap().text.contains("mem"), "a module path stays");
}
#[test]
fn text_that_does_not_tokenise_is_none() {
assert!(normalize("fn broken( {").is_none());
}
}