mirror of
https://github.com/Graphify-Labs/graphify.git
synced 2026-09-14 19:34:09 +08:00
himanshupatro-334
1214 lines
56 KiB
Python
1214 lines
56 KiB
Python
"""Entity deduplication pipeline for graphify knowledge graphs.
|
||
|
||
Pipeline: exact normalization → entropy gate → MinHash/LSH blocking →
|
||
Jaro-Winkler verification → same-community boost → union-find merge.
|
||
"""
|
||
from __future__ import annotations
|
||
import math
|
||
import re
|
||
import sys
|
||
import unicodedata
|
||
from collections import defaultdict
|
||
from pathlib import Path
|
||
|
||
from graphify._minhash import MinHash, MinHashLSH
|
||
from rapidfuzz.distance import DamerauLevenshtein, Jaro, JaroWinkler
|
||
|
||
|
||
# ── helpers ───────────────────────────────────────────────────────────────────
|
||
|
||
def _norm(label: str | None) -> str:
|
||
"""Lowercase + collapse non-alphanumeric runs to space (Unicode-aware)."""
|
||
if not isinstance(label, str):
|
||
label = "" if label is None else str(label)
|
||
label = unicodedata.normalize("NFKC", label)
|
||
return re.sub(r"[\W_]+", " ", label.casefold(), flags=re.UNICODE).strip()
|
||
|
||
|
||
def _entropy(label: str) -> float:
|
||
"""Shannon entropy in bits/char of the normalised label."""
|
||
s = _norm(label)
|
||
if not s:
|
||
return 0.0
|
||
freq: dict[str, int] = defaultdict(int)
|
||
for ch in s:
|
||
freq[ch] += 1
|
||
n = len(s)
|
||
return -sum((c / n) * math.log2(c / n) for c in freq.values())
|
||
|
||
|
||
def _shingles(text: str, k: int = 3) -> set[str]:
|
||
"""Return k-gram character shingles of text."""
|
||
if len(text) < k:
|
||
return {text}
|
||
return {text[i : i + k] for i in range(len(text) - k + 1)}
|
||
|
||
|
||
def _make_minhash(text: str, num_perm: int = 128) -> MinHash:
|
||
# Strip spaces so "graph extractor" and "graphextractor" share shingles
|
||
m = MinHash(num_perm=num_perm)
|
||
for shingle in _shingles(text.replace(" ", "")):
|
||
m.update(shingle.encode("utf-8"))
|
||
return m
|
||
|
||
|
||
# Matches labels whose trailing token is a version/variant suffix:
|
||
# digits optionally followed by letters (chip SKUs: ASR1603, M1, Cortex-A55)
|
||
# or 2+ letters (codename revisions: cranelr vs cranel).
|
||
# Requires the stem to end in a letter so plain words don't accidentally match.
|
||
_VARIANT_SUFFIX = re.compile(r"^(.*[a-z])([0-9]+[a-z]*|[a-z]{2,})$")
|
||
|
||
|
||
def _is_variant_pair(a: str, b: str) -> bool:
|
||
"""True if a and b are sibling model/SKU variants (same stem, different suffix).
|
||
|
||
Only applied to short labels (< 12 chars); long labels go through JW normally.
|
||
"""
|
||
if a == b:
|
||
return False
|
||
if max(len(a), len(b)) >= 12:
|
||
return False
|
||
ma, mb = _VARIANT_SUFFIX.match(a), _VARIANT_SUFFIX.match(b)
|
||
if not (ma and mb):
|
||
return False
|
||
return ma.group(1) == mb.group(1) and ma.group(2) != mb.group(2)
|
||
|
||
|
||
def _short_label_blocked(a: str, b: str, jw_score: float) -> bool:
|
||
"""Block fuzzy merge for short labels unless it's a same-length single-char substitution.
|
||
|
||
Insertions/deletions on short strings (cranel/cranelr, M1/M1 Pro) produce
|
||
high Jaro-Winkler scores due to the prefix bonus but are almost never true
|
||
duplicates — they're abbreviations or variants.
|
||
"""
|
||
if max(len(a), len(b)) >= 12:
|
||
return False
|
||
from rapidfuzz.distance import DamerauLevenshtein
|
||
# Allow only same-length single-char substitutions (true typos like "Extractor"/"Extractar").
|
||
# Block length-differing pairs regardless of score.
|
||
if jw_score >= 97.0 and len(a) == len(b) and DamerauLevenshtein.distance(a, b) <= 1:
|
||
return False
|
||
return True
|
||
|
||
|
||
_DIGIT_RUN = re.compile(r"\d+")
|
||
|
||
|
||
def _numeric_tokens_differ(a: str, b: str) -> bool:
|
||
"""True when two labels carry different embedded numbers (#1284).
|
||
|
||
Long labels that differ only in their digit runs ("ADR 0011 §D5" vs
|
||
"ADR 0013 D4", "3.1 Product Goals" vs "1.1 Product Goals", "block3" vs
|
||
"block13", "40%+ retention" vs "<20% retention") are numbered/versioned
|
||
siblings, not duplicates -- but the long shared boilerplate keeps
|
||
Jaro-Winkler above _MERGE_THRESHOLD, and _is_variant_pair only covers
|
||
short trailing suffixes. Digit runs are compared as multisets with
|
||
leading zeros stripped, so zero-padding ("09" vs "9") does not count as
|
||
a difference. (String comparison, not int(): a pathological label with a
|
||
>4300-digit run would crash int() on Python's conversion limit.) Labels
|
||
with identical numbers, or none at all, are unaffected.
|
||
"""
|
||
if a == b:
|
||
return False
|
||
return sorted(t.lstrip("0") or "0" for t in _DIGIT_RUN.findall(a)) != \
|
||
sorted(t.lstrip("0") or "0" for t in _DIGIT_RUN.findall(b))
|
||
|
||
|
||
# Function words. A restatement of one entity is what inserts or swaps these
|
||
# ("export a read-only ..." vs "export the read-only ..."); a content word
|
||
# carries the entity's identity and swapping one names something else.
|
||
_STOPWORDS = frozenset({
|
||
"a", "an", "the", "and", "or", "of", "for", "to", "in", "on", "at", "by",
|
||
"with", "from", "as", "is", "are", "be", "this", "that", "its",
|
||
})
|
||
|
||
|
||
def _same_word_variant(x: str, y: str) -> bool:
|
||
"""True when tokens x and y read as one word misspelt, not two words (#2576).
|
||
|
||
A same-length pair within one substitution/transposition is a typo
|
||
("manager"/"nanager") -- the same rationale _short_label_blocked applies
|
||
to whole short labels, and unlike Jaro-Winkler it holds at position 0,
|
||
where the prefix bonus gives no help (JW scores "manager"/"nanager" at
|
||
84.92, below threshold, yet it is as much a typo as "managr"). Below 6
|
||
chars JW cannot separate two words from a typo ("pane"/"plane" scores
|
||
94.0), so short length-differing pairs never read as variants. Longer
|
||
pairs fall back to Jaro-Winkler on the merge threshold, so
|
||
"manager"/"managr" (97.14) still reads as one word. Accepted trade, per
|
||
the never-merge-two-distinct-entities bar: "colour"/"color" (5 chars,
|
||
lengths differ) now reads as two words and stays unmerged -- a spelling
|
||
variant kept separate beats a fabricated merge.
|
||
"""
|
||
if len(x) == len(y) and DamerauLevenshtein.distance(x, y) <= 1:
|
||
return True # same-length 1-sub/transposition = typo, even at position 0
|
||
if min(len(x), len(y)) < 6:
|
||
return False # short tokens: JW can't separate pane/plane (94.0) from a typo
|
||
return JaroWinkler.normalized_similarity(x, y) * 100 >= _MERGE_THRESHOLD
|
||
|
||
|
||
def _content_token_swap(a: str, b: str) -> bool:
|
||
"""True when two equal-token-count labels differ in at least one swapped
|
||
content word rather than only typos or function words (#2576, adopted
|
||
from @wilyan09007's PR #2587 and generalized from exactly-one to any
|
||
number of differing positions).
|
||
|
||
Whole-string scoring cannot separate a legit restatement from a
|
||
distinguishing-token swap: both edit one short run in the middle of a long
|
||
shared string, so both land in the same Jaro band (#1243). Which token
|
||
differs does separate them. Structured prose names sibling sections from a
|
||
template ("Asset Contribution Flow" / "Asset Consumption Flow", four
|
||
consecutive headings of one operations doc), and those siblings are densest
|
||
inside a single file -- exactly where Jaro-Winkler's prefix bonus still
|
||
applies, and where the shared affixes it rewards are boilerplate.
|
||
|
||
Each same-position differing pair is judged on its own: a function word on
|
||
either side is what a restatement swaps, a _same_word_variant pair is one
|
||
word misspelt, and anything else is a distinct content word naming a
|
||
different entity -- one such pair blocks the merge. A restatement differs
|
||
only in stopwords/typos at every position; a template sibling differs in
|
||
at least one distinct content word ("... Contribution Flow Handler" vs
|
||
"... Consumption Flows Handler" blocks on either position). Pairs with
|
||
different token counts are left to the prefix-extension guard (#1201) and
|
||
whole-label scoring. Known gap, out of scope here: fused camelCase labels
|
||
("AssetContributionFlow" vs "AssetConsumptionFlow") normalize to single
|
||
tokens whose only differing "position" is the whole label, so this guard
|
||
reduces to whole-token _same_word_variant and long fused pairs can still
|
||
clear the JW fallback.
|
||
"""
|
||
tokens_a, tokens_b = a.split(), b.split()
|
||
if len(tokens_a) != len(tokens_b):
|
||
return False
|
||
for x, y in zip(tokens_a, tokens_b):
|
||
if x == y:
|
||
continue
|
||
if x in _STOPWORDS or y in _STOPWORDS:
|
||
continue # restatement: a function word swapped in or out
|
||
if _same_word_variant(x, y):
|
||
continue # one word misspelt/inflected, not a different word
|
||
return True
|
||
return False
|
||
|
||
|
||
# file_type values whose identity is anchored to their source location, not
|
||
# their label text. Like code (#1205), these must not be label-merged across
|
||
# files: rationale = module/class docstrings, document = headings/positional
|
||
# content. `concept` is intentionally excluded -- it is the type meant to unify
|
||
# across files (protected from over-merge by the numeric/Jaro guards instead).
|
||
_FILE_ANCHORED_NONCODE = frozenset({"rationale", "document"})
|
||
|
||
|
||
def _crossfile_fileanchored_blocked(node: dict, neighbor: dict) -> bool:
|
||
"""Block label-based merging of file-anchored non-code nodes across files (#1284).
|
||
|
||
rationale/document nodes are docstring- and heading-derived and as
|
||
file-anchored as the code they describe (#1205's reasoning, one layer up):
|
||
parallel modules carry near-identical boilerplate ("Django app config for
|
||
apps.<name>. No business logic here...") that differs by one word and sails
|
||
past the JW threshold. Same-file duplicates of these types may still merge.
|
||
"""
|
||
if (node.get("file_type") not in _FILE_ANCHORED_NONCODE
|
||
and neighbor.get("file_type") not in _FILE_ANCHORED_NONCODE):
|
||
return False
|
||
return (node.get("source_file") or "") != (neighbor.get("source_file") or "")
|
||
|
||
|
||
# ── union-find ────────────────────────────────────────────────────────────────
|
||
|
||
class _UF:
|
||
def __init__(self) -> None:
|
||
self._parent: dict[str, str] = {}
|
||
|
||
def find(self, x: str) -> str:
|
||
self._parent.setdefault(x, x)
|
||
while self._parent[x] != x:
|
||
self._parent[x] = self._parent[self._parent[x]]
|
||
x = self._parent[x]
|
||
return x
|
||
|
||
def union(self, x: str, y: str) -> None:
|
||
self._parent.setdefault(x, x)
|
||
self._parent.setdefault(y, y)
|
||
rx, ry = self.find(x), self.find(y)
|
||
if rx != ry:
|
||
self._parent[ry] = rx
|
||
|
||
def components(self) -> dict[str, list[str]]:
|
||
groups: dict[str, list[str]] = defaultdict(list)
|
||
for x in self._parent:
|
||
groups[self.find(x)].append(x)
|
||
return dict(groups)
|
||
|
||
|
||
# ── constants ─────────────────────────────────────────────────────────────────
|
||
|
||
_ENTROPY_THRESHOLD = 2.5
|
||
_LSH_THRESHOLD = 0.7
|
||
_MERGE_THRESHOLD = 92.0 # rapidfuzz normalized_similarity * 100
|
||
_COMMUNITY_BOOST = 5.0 # score bonus when both nodes share community
|
||
_NUM_PERM = 128
|
||
_CHUNK_SUFFIX = re.compile(r"_c\d+$")
|
||
|
||
|
||
def _is_code(node: dict) -> bool:
|
||
"""True for AST-extracted code symbols.
|
||
|
||
Code-node identity is the node ID (which already encodes the fully
|
||
qualified path: module/class/symbol). The label is only a display name
|
||
(e.g. a bare ``.draw()`` method name, or a function name shared by two
|
||
parallel backends), so label-based merging conflates distinct symbols
|
||
(#1205). Genuine duplicates — the same symbol re-extracted — share an ID
|
||
and are already collapsed by the exact-ID ``seen_ids`` pre-dedup above,
|
||
so code never needs label-based merging.
|
||
"""
|
||
return node.get("file_type") == "code"
|
||
|
||
|
||
# ── ID collisions ─────────────────────────────────────────────────────────────
|
||
|
||
_ID_SEGMENT = re.compile(r"[^a-z0-9]+")
|
||
_EXTENSION = re.compile(r"\.[^./]+$")
|
||
|
||
|
||
def _id_prefixes(source_file: str) -> set[str]:
|
||
"""The ID prefixes a node extracted from ``source_file`` may legitimately mint.
|
||
|
||
An ID is ``<path>_<entity>``, where the path is the extension-stripped source
|
||
path, each segment slugified and joined with ``_``. Every trailing slice of the
|
||
path counts as a prefix: the stored path may be absolute or repo-relative, and
|
||
graphs built under the pre-#1504 scheme keyed off the bare filename stem.
|
||
"""
|
||
stem = _EXTENSION.sub("", source_file.replace("\\", "/"))
|
||
segments = [s for s in (_ID_SEGMENT.sub("_", p.casefold()).strip("_")
|
||
for p in stem.split("/")) if s]
|
||
return {"_".join(segments[i:]) for i in range(len(segments))}
|
||
|
||
|
||
def _defines_id(node: dict) -> bool:
|
||
"""True when the node's own source_file is the file its ID encodes.
|
||
|
||
A doc that *references* an entity mints the ID of the entity's own file, not one
|
||
derived from the doc's path — so the referencing node collides with the defining
|
||
node by construction. This separates the two: the definer owns the ID.
|
||
"""
|
||
nid = node.get("id") or ""
|
||
source_file = node.get("source_file") or ""
|
||
if not nid or not source_file:
|
||
return False
|
||
# `nid == prefix` covers a bare file-level node whose id is exactly the
|
||
# slugified path with no `_entity` suffix (a semantic node for the file
|
||
# itself); `startswith(prefix + "_")` covers the usual `<path>_<entity>` id.
|
||
return any(nid == prefix or nid.startswith(f"{prefix}_")
|
||
for prefix in _id_prefixes(source_file))
|
||
|
||
|
||
# `node_kind` values marking a node that is STRUCTURE of its source file rather
|
||
# than an entity mentioned inside it: `page` is the file's own node, `heading`
|
||
# one of its sections. The markdown extractor stamps these precisely because
|
||
# `file_type` cannot carry the distinction, and both are file-anchored in the
|
||
# #1284 sense — two files' `## Decisions` sections are two sections (#3094).
|
||
#
|
||
# PRODUCER CONTRACT: an extractor that mints a node standing for a *part* of its
|
||
# source file (a section, a sheet, a slide) must stamp one of these. The gate
|
||
# below reads an unstamped node as an entity, so an unstamped structural node is
|
||
# eligible to merge with its namesake in another file.
|
||
_FILE_STRUCTURE_NODE_KINDS = frozenset({"page", "heading"})
|
||
|
||
|
||
def _reads_as_file_entity(node: dict) -> bool:
|
||
"""True when the node reads as an entity found inside its file, rather than
|
||
as the file itself or a stamped structural part of it (#296).
|
||
|
||
Be precise about what is proven and what is assumed, because the two halves
|
||
differ in strength:
|
||
|
||
* PROVEN — it is not its file's OWN node. ``_id_prefixes`` enumerates the ID
|
||
a node standing for ``source_file`` itself would carry, in every spelling
|
||
a stored path may take (absolute, repo-relative, or the pre-#1504 bare
|
||
stem). A file's own node IS one of those; an entity extracted from that
|
||
file carries an ``_<entity>`` suffix, so it never equals one. This is a
|
||
reconstruction, not a heuristic.
|
||
* ASSUMED — it is not a section of the file. That rests on ``node_kind``,
|
||
which only a producer that stamps it can attest. `heading`/`page` are
|
||
honoured when present, but ABSENCE OF THE MARKER IS NOT PROOF OF
|
||
ENTITY-NESS: a producer minting sub-file nodes without stamping
|
||
`node_kind` (see the contract above) yields structural nodes that this
|
||
returns True for, and two such nodes sharing a label in different files
|
||
would merge. The conservative fix is on the producer side — stamp
|
||
`node_kind` — not a guess here about what an unstamped node meant.
|
||
|
||
A node that cannot be checked at all (no ID, no provenance) answers False
|
||
and stays blocked.
|
||
"""
|
||
nid = node.get("id") or ""
|
||
source_file = node.get("source_file") or ""
|
||
if not nid or not source_file:
|
||
return False # uncheckable — leave the file-anchored block in place
|
||
if node.get("node_kind") in _FILE_STRUCTURE_NODE_KINDS:
|
||
return False # the extractor says this node is part of the file's structure
|
||
return nid not in _id_prefixes(source_file)
|
||
|
||
|
||
# Path-segment lifecycle markers used by _collision_rank (#2532). Lower penalty
|
||
# wins. Without them, pure lexical source_file order makes ``plans/_done/…``
|
||
# beat ``plans/in-progress/…`` because "_" < "i" in ASCII. Active-vs-archived
|
||
# marker idea by @michaelxer (#2540); matched against ROOT-RELATIVE directory
|
||
# segments only, so a checkout directory that happens to be named ``wip`` or
|
||
# ``done`` never leaks into the ranking.
|
||
_ACTIVE_PATH_SEGMENTS = frozenset({
|
||
"in-progress",
|
||
"in_progress",
|
||
"active",
|
||
"current",
|
||
"wip",
|
||
})
|
||
_ARCHIVED_PATH_SEGMENTS = frozenset({
|
||
"_done",
|
||
"done",
|
||
"archive",
|
||
"archived",
|
||
"backup",
|
||
"bak",
|
||
"old",
|
||
"attic",
|
||
"graveyard",
|
||
"completed",
|
||
})
|
||
|
||
|
||
def _lifecycle_penalty(rank_path: str) -> int:
|
||
"""0 for active/in-progress paths, 2 for archived/done paths, 1 otherwise.
|
||
|
||
Judged on the DIRECTORY segments of the root-relative rank path — a file
|
||
literally named ``done.md`` is not a marker. Among mixed markers the best
|
||
(lowest) score wins so an active segment is not drowned out by an unrelated
|
||
archive directory higher in the tree (#2532).
|
||
"""
|
||
segments = [s for s in rank_path.casefold().split("/") if s]
|
||
marked = [
|
||
0 if s in _ACTIVE_PATH_SEGMENTS else 2
|
||
for s in segments[:-1] # directories only, never the basename
|
||
if s in _ACTIVE_PATH_SEGMENTS or s in _ARCHIVED_PATH_SEGMENTS
|
||
]
|
||
return min(marked) if marked else 1
|
||
|
||
|
||
def _rank_path(source_file: str, root: Path | None) -> str:
|
||
"""The root-relative form of ``source_file`` used for collision ranking.
|
||
|
||
Mirrors ``_source_key`` in extractors/resolution.py: with a scan root, an
|
||
absolute stored path and its repo-relative twin rank identically, and the
|
||
checkout location's own segments never participate (#2532). Without a root
|
||
(or when relativizing fails) the normalized stored path is used as-is.
|
||
"""
|
||
normalized = source_file.replace("\\", "/")
|
||
if root is not None and normalized:
|
||
try:
|
||
return Path(normalized).resolve().relative_to(root).as_posix()
|
||
except Exception:
|
||
pass
|
||
return normalized
|
||
|
||
|
||
def _collision_rank(node: dict, root: Path | None = None) -> tuple:
|
||
"""A total order for choosing the survivor of an ID collision, independent of
|
||
the order the colliding nodes arrive in.
|
||
|
||
The winner is the node with the SMALLEST rank. A node whose ``source_file``
|
||
defines the ID always outranks a mere reference; among equally-(non-)defining
|
||
nodes an active/in-progress path outranks an archived/done one (#2532); then
|
||
it prefers the shorter, more canonical label over a longer qualified variant,
|
||
then breaks any remaining tie lexically on label and finally on the REVERSED
|
||
segments of the root-relative path. Basename-first comparison decides two
|
||
in-repo colliders by segments present in both path forms, so absolute and
|
||
repo-relative spellings of the same layout order identically — fully
|
||
deterministic regardless of arrival order (#1851) or checkout location.
|
||
"""
|
||
label = node.get("label") or ""
|
||
rank_path = _rank_path(node.get("source_file") or "", root)
|
||
return (
|
||
not _defines_id(node), # definers (False) sort before references (True)
|
||
_lifecycle_penalty(rank_path), # active paths beat archived ones (#2532)
|
||
len(label), # shorter, more canonical label first
|
||
label, # lexical tiebreak
|
||
tuple(reversed([s for s in rank_path.split("/") if s and s != "."])),
|
||
)
|
||
|
||
|
||
def _same_source_entity(survivor: dict, duplicate: dict) -> bool:
|
||
"""True when exact-ID records came from the same source file.
|
||
|
||
Exact IDs can also collide across files through references or slugged-path
|
||
ambiguity (#1504). Keep those records isolated rather than importing
|
||
attributes whose provenance belongs to another file.
|
||
"""
|
||
keep_file = survivor.get("source_file") or ""
|
||
lose_file = duplicate.get("source_file") or ""
|
||
# Require a non-empty source_file: two provenance-less records ("" == "")
|
||
# are NOT proof of the same symbol (#1178), and merging their attributes
|
||
# would be a cross-pollination bug in the opposite direction (#2091 review).
|
||
return bool(keep_file) and keep_file == lose_file
|
||
|
||
|
||
def _merge_missing_attributes(survivor: dict, duplicate: dict) -> dict:
|
||
"""Fill the survivor's absent/None attributes from a same-source duplicate,
|
||
without overriding values the survivor already has (#2091)."""
|
||
merged = dict(survivor)
|
||
for key, value in duplicate.items():
|
||
# Never inherit a provenance tag from a dropped record: a false
|
||
# _origin="ast" on an LLM survivor is read as an authority signal by the
|
||
# ghost-merge (#2068) and watch deletion logic (#2091 review).
|
||
if key == "_origin":
|
||
continue
|
||
if value is None:
|
||
continue
|
||
# Treat an explicit None on the survivor as absent — the codebase emits
|
||
# `source_location: None`, and that is exactly the attribute #2091 loses.
|
||
if merged.get(key) is None:
|
||
merged[key] = value
|
||
return merged
|
||
|
||
|
||
def _report_id_collision(nid: str, survivor: dict, losers: list[dict]) -> None:
|
||
"""Report an ID collision in proportion to what dropping the loser actually costs.
|
||
|
||
Cross-reference to a defining node: the structural entity and its edges survive;
|
||
foreign-file attributes stay isolated, so no collision warning is needed. Same
|
||
file, different labels: the extractor emitted two labels for one entity and one is
|
||
discarded — note it. Two files that both encode this ID: they are distinct entities
|
||
and one is genuinely lost — warn, and point at the extraction split that keeps them
|
||
apart (#1504).
|
||
"""
|
||
keep_file = survivor.get("source_file") or ""
|
||
keep_label = survivor.get("label") or ""
|
||
for loser in losers:
|
||
lose_file = loser.get("source_file") or ""
|
||
lose_label = loser.get("label") or ""
|
||
if lose_file == keep_file:
|
||
if _norm(lose_label) != _norm(keep_label):
|
||
print(
|
||
f"[graphify] note: node '{nid}' was extracted twice from "
|
||
f"'{keep_file}' under different labels — keeping '{keep_label}', "
|
||
f"dropping '{lose_label}'.",
|
||
file=sys.stderr,
|
||
)
|
||
elif _defines_id(survivor) and not _defines_id(loser):
|
||
continue # the loser only references the entity the survivor defines
|
||
else:
|
||
print(
|
||
f"[graphify] WARNING: node '{nid}' is minted by two different files — "
|
||
f"keeping '{keep_label}' from '{keep_file}', dropping '{lose_label}' "
|
||
f"from '{lose_file}'. An ID is derived from the source path plus the "
|
||
f"entity name, so this one does not identify a single entity and the "
|
||
f"dropped node is lost. To keep them distinct, run 'graphify extract' "
|
||
f"per subfolder and merge with 'graphify merge-graphs'.",
|
||
file=sys.stderr,
|
||
)
|
||
|
||
|
||
# ── main entry point ──────────────────────────────────────────────────────────
|
||
|
||
def _remap_hyperedge_members(hyperedges: list[dict], remap: dict[str, str]) -> None:
|
||
"""Rewire hyperedge member ids onto dedup survivors, in place.
|
||
|
||
Members come in both shapes the rest of the codebase tolerates — a bare id
|
||
string, or an object carrying one — so both are handled;
|
||
``_normalize_hyperedge_members`` fixes the SHAPE but never resolves a member
|
||
against surviving node ids, which is why this is needed as well.
|
||
|
||
Two members that remap onto the same survivor collapse to one entry. That
|
||
shrinks the group, but honestly: they were the same entity, and the previous
|
||
behaviour dropped the loser without promoting it, which shrank the group
|
||
*and* lost the participant. Order is preserved so a rebuilt graph does not
|
||
churn.
|
||
"""
|
||
for he in hyperedges:
|
||
if not isinstance(he, dict):
|
||
continue
|
||
members = he.get("nodes")
|
||
if not isinstance(members, list):
|
||
continue
|
||
seen: set = set()
|
||
rewired: list = []
|
||
for m in members:
|
||
if isinstance(m, str):
|
||
new_id = remap.get(m, m)
|
||
entry = new_id
|
||
elif isinstance(m, dict):
|
||
raw = m.get("id")
|
||
new_id = remap.get(raw, raw) if isinstance(raw, str) else raw
|
||
entry = dict(m, id=new_id) if new_id != raw else m
|
||
else:
|
||
new_id, entry = None, m
|
||
if isinstance(new_id, str):
|
||
if new_id in seen:
|
||
continue
|
||
seen.add(new_id)
|
||
rewired.append(entry)
|
||
he["nodes"] = rewired
|
||
|
||
|
||
def deduplicate_entities(
|
||
nodes: list[dict],
|
||
edges: list[dict],
|
||
*,
|
||
communities: dict[str, int],
|
||
dedup_llm_backend: str | None = None,
|
||
root: str | Path | None = None,
|
||
hyperedges: "list[dict] | None" = None,
|
||
protected_ids: "set[str] | None" = None,
|
||
) -> tuple[list[dict], list[dict]]:
|
||
"""Deduplicate near-identical entities in a knowledge graph.
|
||
|
||
Args:
|
||
nodes: list of node dicts with at minimum {"id": str, "label": str}
|
||
edges: list of edge dicts with {"source": str, "target": str, ...}
|
||
communities: mapping of node_id -> community_id (from cluster())
|
||
dedup_llm_backend: if set, use LLM to resolve ambiguous pairs
|
||
root: scan root; ID-collision ranking judges source paths relative to
|
||
it so path form and checkout location cannot flip the survivor (#2532)
|
||
hyperedges: when given, member ids are rewired to survivors IN PLACE,
|
||
the same way edge endpoints are. Optional and mutating rather than
|
||
returned so existing two-tuple callers are unaffected (#2805).
|
||
|
||
Returns:
|
||
(deduped_nodes, deduped_edges) with edges rewired to survivors
|
||
"""
|
||
# Guard: cross-project dedup is not supported — nodes from different repos
|
||
# share label names by coincidence and must never be merged by string similarity.
|
||
# If you need to dedup a global graph, run deduplicate_entities per-repo first.
|
||
repos_seen = {n.get("repo") for n in nodes if n.get("repo")}
|
||
if len(repos_seen) > 1:
|
||
raise ValueError(
|
||
f"deduplicate_entities: nodes span multiple repos {sorted(repos_seen)!r}. "
|
||
f"Cross-project dedup is disabled — run dedup per-repo before merging."
|
||
)
|
||
|
||
if len(nodes) <= 1:
|
||
return nodes, edges
|
||
|
||
# Resolve the scan root once: _collision_rank ranks each node's source_file
|
||
# relative to it, so an absolute stored path and its repo-relative twin rank
|
||
# identically and lifecycle markers in the checkout location's own segments
|
||
# cannot flip the survivor (#2532).
|
||
try:
|
||
root_resolved: Path | None = Path(root).resolve() if root else None
|
||
except Exception:
|
||
root_resolved = None
|
||
|
||
# Pre-deduplicate: one node per ID. The survivor is the node that *defines* the
|
||
# ID (its source_file is the file the ID encodes), not merely the first seen —
|
||
# otherwise chunk order decides whether an entity keeps its own attributes or a
|
||
# passing cross-reference's. Missing attributes from same-source records are
|
||
# retained so AST structure and semantic enrichment can coexist (#2091).
|
||
# Genuine cross-file ID collisions stay isolated and are reported below (#1504).
|
||
seen_ids: dict[str, dict] = {}
|
||
dropped: dict[str, list[dict]] = defaultdict(list)
|
||
for node in nodes:
|
||
nid = node.get("id", "")
|
||
if not nid:
|
||
continue
|
||
incumbent = seen_ids.get(nid)
|
||
if incumbent is None:
|
||
seen_ids[nid] = node
|
||
elif _collision_rank(node, root_resolved) < _collision_rank(incumbent, root_resolved):
|
||
# Smallest-ranked node wins; the min over a total order is independent
|
||
# of the order nodes arrive in, so the survivor no longer depends on
|
||
# chunk ordering (#1851).
|
||
seen_ids[nid] = node
|
||
dropped[nid].append(incumbent)
|
||
else:
|
||
dropped[nid].append(node)
|
||
|
||
# Gap-fill each survivor from its SAME-SOURCE losers, applied in deterministic
|
||
# _collision_rank order (best loser first). Merging here — not incrementally in
|
||
# the loop above — keeps the merged attributes independent of chunk arrival
|
||
# order with 3+ colliding records, preserving the #1851 order-independence
|
||
# contract (#2091 review).
|
||
for nid, losers in dropped.items():
|
||
survivor = seen_ids[nid]
|
||
same_source = sorted(
|
||
(l for l in losers if _same_source_entity(survivor, l)),
|
||
key=lambda l: _collision_rank(l, root_resolved),
|
||
)
|
||
for loser in same_source:
|
||
survivor = _merge_missing_attributes(survivor, loser)
|
||
seen_ids[nid] = survivor
|
||
|
||
for nid, losers in dropped.items():
|
||
_report_id_collision(nid, seen_ids[nid], losers)
|
||
|
||
unique_nodes = list(seen_ids.values())
|
||
|
||
if len(unique_nodes) <= 1:
|
||
return unique_nodes, edges
|
||
|
||
# ── pass 1: exact normalization ───────────────────────────────────────────
|
||
norm_to_nodes: dict[str, list[dict]] = defaultdict(list)
|
||
for node in unique_nodes:
|
||
# Code symbols are keyed by ID, never by label — skip them entirely so
|
||
# distinct same-named symbols are never merged by string similarity (#1205).
|
||
if _is_code(node):
|
||
continue
|
||
key = _norm(node.get("label", node.get("id", "")))
|
||
if key:
|
||
norm_to_nodes[key].append(node)
|
||
|
||
uf = _UF()
|
||
exact_merges = 0
|
||
|
||
protected_set: set[str] = set(protected_ids) if protected_ids is not None else set()
|
||
prot_by_root: dict[str, str] = {pid: pid for pid in protected_set}
|
||
|
||
def _get_prot(nid: str) -> str | None:
|
||
return prot_by_root.get(uf.find(nid))
|
||
|
||
def _union_with_prot(x: str, y: str) -> None:
|
||
px = _get_prot(x)
|
||
py = _get_prot(y)
|
||
uf.union(x, y)
|
||
new_root = uf.find(x)
|
||
prot = px or py
|
||
if prot is not None:
|
||
prot_by_root[new_root] = prot
|
||
|
||
for key, group in norm_to_nodes.items():
|
||
if len(group) <= 1:
|
||
continue
|
||
# Partition by source_file — same-file exact matches always merge here.
|
||
# Cross-file exact matches are handled just below, gated to `concept`
|
||
# nodes only: Pass 2 cannot form them because its candidate list keeps a
|
||
# single node per normalized label (#2182).
|
||
by_file: dict[str, list[dict]] = defaultdict(list)
|
||
for node in group:
|
||
sf = node.get("source_file") or ""
|
||
by_file[sf].append(node)
|
||
for sf, file_group in by_file.items():
|
||
if not sf:
|
||
# No source_file — cannot prove same symbol; skip to avoid
|
||
# collapsing distinct nodes that happen to share a label (#1178).
|
||
continue
|
||
if len(file_group) > 1:
|
||
if protected_set:
|
||
prot_file = [n for n in file_group if n.get("id") in protected_set]
|
||
inc_file = [n for n in file_group if n.get("id") not in protected_set]
|
||
if prot_file and not inc_file:
|
||
# All nodes belong exclusively to an untouched file — preserve all of them
|
||
continue
|
||
if prot_file and inc_file:
|
||
winner = _pick_winner(prot_file)
|
||
for node in inc_file:
|
||
px = _get_prot(winner["id"])
|
||
py = _get_prot(node["id"])
|
||
if px is not None and py is not None and px != py:
|
||
continue
|
||
if uf.find(winner["id"]) != uf.find(node["id"]):
|
||
_union_with_prot(winner["id"], node["id"])
|
||
exact_merges += 1
|
||
else:
|
||
winner = _pick_winner(file_group)
|
||
for node in file_group:
|
||
if uf.find(winner["id"]) != uf.find(node["id"]):
|
||
_union_with_prot(winner["id"], node["id"])
|
||
exact_merges += 1
|
||
else:
|
||
winner = _pick_winner(file_group)
|
||
for node in file_group:
|
||
uf.union(winner["id"], node["id"])
|
||
exact_merges += len(file_group) - 1
|
||
# Cross-file residue: union exact matches across files, but only where
|
||
# it is provably safe (#2182). `concept` is the one file_type meant to
|
||
# unify across files (#1284) — code is keyed by ID (#1205) and
|
||
# image/paper labels are often shared basenames (logo.png), so both stay
|
||
# blocked. rationale/document join `concept` here ONLY when the node
|
||
# reads as an entity inside its file (#296): a file-anchored
|
||
# *file_type* does not make an individual node file-anchored. An entity
|
||
# extracted from a note — a person, a project — inherits `document` from
|
||
# the file's extension, not from anything about itself, so in note-heavy
|
||
# corpora almost no entity node is typed `concept` and this merge never
|
||
# got to run on them. A file's own node and its headings still never
|
||
# merge (#1284, #3094).
|
||
# Provenance is required (#1178), and the entropy gate mirrors Pass 2 so
|
||
# short generic labels ("API") stay distinct — both untouched here.
|
||
# Scoped to this exact-normalization pass: Pass 2's fuzzy
|
||
# `_crossfile_fileanchored_blocked` is unchanged, so #1284's
|
||
# near-identical boilerplate and heading siblings stay blocked.
|
||
# Sorting by id keeps the winner order-independent.
|
||
mergeable = sorted(
|
||
(n for n in group
|
||
if (n.get("file_type") == "concept"
|
||
or (n.get("file_type") in _FILE_ANCHORED_NONCODE
|
||
and _reads_as_file_entity(n)))
|
||
and (n.get("source_file") or "")
|
||
and _entropy(n.get("label", "")) >= _ENTROPY_THRESHOLD),
|
||
key=lambda n: n["id"],
|
||
)
|
||
if len(mergeable) > 1:
|
||
if protected_set:
|
||
prot_members = [n for n in mergeable if n.get("id") in protected_set]
|
||
inc_members = [n for n in mergeable if n.get("id") not in protected_set]
|
||
if not inc_members:
|
||
# All participants belong exclusively to untouched files (#3477):
|
||
# NEVER collapse them during incremental merge.
|
||
continue
|
||
if prot_members:
|
||
# Mixed: pick AT MOST ONE protected survivor for incoming nodes to fold into.
|
||
# Multiple protected nodes must remain separate independent entities.
|
||
canonical_winner = _pick_winner(prot_members)
|
||
for inc in inc_members:
|
||
px = _get_prot(canonical_winner["id"])
|
||
py = _get_prot(inc["id"])
|
||
if px is not None and py is not None and px != py:
|
||
continue
|
||
if uf.find(canonical_winner["id"]) != uf.find(inc["id"]):
|
||
_union_with_prot(canonical_winner["id"], inc["id"])
|
||
exact_merges += 1
|
||
else:
|
||
# Incoming only: merge normally
|
||
winner = _pick_winner(inc_members)
|
||
for node in inc_members:
|
||
if uf.find(winner["id"]) != uf.find(node["id"]):
|
||
_union_with_prot(winner["id"], node["id"])
|
||
exact_merges += 1
|
||
else:
|
||
winner = _pick_winner(mergeable)
|
||
for node in mergeable:
|
||
if uf.find(winner["id"]) != uf.find(node["id"]):
|
||
uf.union(winner["id"], node["id"])
|
||
exact_merges += 1
|
||
|
||
# ── pass 2: MinHash/LSH + Jaro-Winkler (high-entropy nodes only) ─────────
|
||
candidates: list[dict] = []
|
||
seen_norms: set[str] = set()
|
||
for node in unique_nodes:
|
||
# Code symbols are excluded from fuzzy matching too: two functions with
|
||
# similar long names in different files (parallel backends, sibling
|
||
# classes) must not be fuzzy-merged, and a code↔concept fuzzy match must
|
||
# not transitively union two distinct code symbols via a concept (#1205).
|
||
if _is_code(node):
|
||
continue
|
||
key = _norm(node.get("label", node.get("id", "")))
|
||
if key and key not in seen_norms:
|
||
seen_norms.add(key)
|
||
if _entropy(node.get("label", "")) >= _ENTROPY_THRESHOLD:
|
||
candidates.append(node)
|
||
|
||
fuzzy_merges = 0
|
||
if len(candidates) >= 2:
|
||
lsh = MinHashLSH(threshold=_LSH_THRESHOLD, num_perm=_NUM_PERM)
|
||
minhashes: dict[str, MinHash] = {}
|
||
# Pre-build O(1) lookup structures so the query loop below doesn't scan
|
||
# the candidates list linearly for every LSH neighbor (was O(n²×B)).
|
||
candidates_by_id: dict[str, dict] = {}
|
||
norm_cache: dict[str, str] = {}
|
||
|
||
for node in candidates:
|
||
node_id = node["id"]
|
||
candidates_by_id[node_id] = node
|
||
nl = _norm(node.get("label", node.get("id", "")))
|
||
norm_cache[node_id] = nl
|
||
m = _make_minhash(nl)
|
||
minhashes[node_id] = m
|
||
try:
|
||
lsh.insert(node_id, m)
|
||
except ValueError:
|
||
pass # duplicate key in LSH — already inserted
|
||
|
||
for node in candidates:
|
||
node_id = node["id"]
|
||
norm_label = norm_cache[node_id]
|
||
neighbors = lsh.query(minhashes[node_id])
|
||
|
||
for neighbor_id in neighbors:
|
||
if neighbor_id == node_id:
|
||
continue
|
||
if uf.find(node_id) == uf.find(neighbor_id):
|
||
continue
|
||
|
||
if protected_set:
|
||
px = _get_prot(node_id)
|
||
py = _get_prot(neighbor_id)
|
||
if px is not None and py is not None and px != py:
|
||
# Prevent protected/protected unions and bridging across protected components
|
||
continue
|
||
|
||
neighbor = candidates_by_id.get(neighbor_id)
|
||
if neighbor is None:
|
||
continue
|
||
|
||
neighbor_norm = norm_cache.get(neighbor_id) or _norm(neighbor.get("label", neighbor.get("id", "")))
|
||
# Cross-file long labels score on plain Jaro (no prefix bonus).
|
||
# Jaro-Winkler's leading-prefix bonus lifts pairs that share a
|
||
# prefix but diverge in a distinguishing token ("testing-library
|
||
# jest-native" vs "react-native") past threshold, fabricating
|
||
# destructive cross-file merges; on Jaro alone they fall short
|
||
# while true cross-file duplicates still clear it (#1243). Same-file
|
||
# near-duplicates keep Jaro-Winkler (low-risk, and a mid-string
|
||
# stopword insertion needs the prefix bonus to merge); short labels
|
||
# keep Jaro-Winkler too (gated by _short_label_blocked).
|
||
_xfile = (node.get("source_file") or "") != (neighbor.get("source_file") or "")
|
||
if _xfile and max(len(norm_label), len(neighbor_norm)) >= 12:
|
||
score = Jaro.normalized_similarity(norm_label, neighbor_norm) * 100
|
||
else:
|
||
score = JaroWinkler.normalized_similarity(norm_label, neighbor_norm) * 100
|
||
|
||
if _is_variant_pair(norm_label, neighbor_norm):
|
||
continue
|
||
if _short_label_blocked(norm_label, neighbor_norm, score):
|
||
continue
|
||
# Prefix-extension pairs (getActiveSession / getActiveSessions,
|
||
# parseConfig / parseConfigFile) are almost never duplicates —
|
||
# one is a strict suffix-extension of the other. Block the merge
|
||
# regardless of JW score (#1201).
|
||
_lo, _hi = sorted((norm_label, neighbor_norm), key=len)
|
||
if _hi.startswith(_lo) and _hi != _lo:
|
||
continue
|
||
# Numbered/versioned siblings and cross-file file-anchored
|
||
# boilerplate (rationale/document) are decisively distinct
|
||
# regardless of score (#1284).
|
||
if _numeric_tokens_differ(norm_label, neighbor_norm):
|
||
continue
|
||
# Template-named siblings differing in a content word are
|
||
# distinct too, on either path: same-file pairs keep the prefix
|
||
# bonus, and a cross-file pair can still reach threshold on the
|
||
# community boost alone (#2576).
|
||
if _content_token_swap(norm_label, neighbor_norm):
|
||
continue
|
||
if _crossfile_fileanchored_blocked(node, neighbor):
|
||
continue
|
||
|
||
c1 = communities.get(node_id)
|
||
c2 = communities.get(neighbor_id)
|
||
if (c1 is not None and c2 is not None and c1 == c2
|
||
and min(len(norm_label), len(neighbor_norm)) >= 12):
|
||
score += _COMMUNITY_BOOST
|
||
|
||
if score >= _MERGE_THRESHOLD:
|
||
# Belt-and-braces (#1046, narrowed by #2182): candidates are
|
||
# norm-unique (`seen_norms` above), so two candidates can
|
||
# never share a normalized label and this branch is
|
||
# unreachable today. Retained in case candidate selection
|
||
# changes. Equal-norm cross-file pairs are handled in Pass 1
|
||
# instead, gated to `concept` nodes — the original #1046
|
||
# rationale (same-named code symbols) was obsoleted by code
|
||
# being excluded from label matching entirely (#1205, #1247).
|
||
if norm_label == neighbor_norm:
|
||
sf_a = node.get("source_file") or ""
|
||
sf_b = neighbor.get("source_file") or ""
|
||
if sf_a != sf_b:
|
||
continue
|
||
# Pick the winner from the verified pair only. Selecting it
|
||
# from the union of both normalized-label groups pulls
|
||
# never-compared nodes (same label, different source_file)
|
||
# into the merge, bypassing the #1046/#1178 guards.
|
||
if protected_set:
|
||
px = _get_prot(node_id)
|
||
py = _get_prot(neighbor_id)
|
||
if px is not None and py is not None and px != py:
|
||
continue
|
||
if node_id in protected_set:
|
||
winner = node
|
||
elif neighbor_id in protected_set:
|
||
winner = neighbor
|
||
else:
|
||
winner = _pick_winner([node, neighbor])
|
||
_union_with_prot(winner["id"], node_id)
|
||
_union_with_prot(winner["id"], neighbor_id)
|
||
else:
|
||
winner = _pick_winner([node, neighbor])
|
||
uf.union(winner["id"], node_id)
|
||
uf.union(winner["id"], neighbor_id)
|
||
fuzzy_merges += 1
|
||
|
||
# ── pass 3: LLM tiebreaker for ambiguous pairs (opt-in) ──────────────────
|
||
if dedup_llm_backend is not None:
|
||
_llm_tiebreak(
|
||
candidates, uf, communities, backend=dedup_llm_backend,
|
||
protected_set=protected_set, get_prot=_get_prot, union_with_prot=_union_with_prot,
|
||
)
|
||
|
||
# ── build remap table from union-find components ──────────────────────────
|
||
components = uf.components()
|
||
remap: dict[str, str] = {}
|
||
|
||
# id -> (position, node), built once. Previously each component re-scanned
|
||
# the whole unique_nodes list, making remap construction O(nodes x
|
||
# components) — 31% of dedup wall-clock on a 50k-node corpus.
|
||
# The position is carried so group_nodes keeps unique_nodes order: _pick_winner
|
||
# resolves ties (equal chunk-suffix status and equal id length) via min(),
|
||
# which returns the first minimum, so reordering here would silently change
|
||
# which node survives.
|
||
nodes_by_id: dict[str, tuple[int, dict]] = {
|
||
n["id"]: (i, n) for i, n in enumerate(unique_nodes)
|
||
}
|
||
|
||
# Survivors enriched with their losers' fields, substituted at the end.
|
||
enriched_by_id: dict[str, dict] = {}
|
||
for root, members in components.items():
|
||
if len(members) == 1:
|
||
continue
|
||
group_nodes = [
|
||
n for _, n in sorted(
|
||
(nodes_by_id[m] for m in members if m in nodes_by_id),
|
||
key=lambda pair: pair[0],
|
||
)
|
||
]
|
||
if protected_set:
|
||
prot_in_group = [n for n in group_nodes if n.get("id") in protected_set]
|
||
if prot_in_group:
|
||
winner = _pick_winner(prot_in_group)
|
||
else:
|
||
winner = _pick_winner(group_nodes) if group_nodes else {"id": root}
|
||
else:
|
||
winner = _pick_winner(group_nodes) if group_nodes else {"id": root}
|
||
winner_id = winner["id"]
|
||
# Even with the right survivor, dropping the losers wholesale loses
|
||
# whatever fields only they carried. Fill the survivor's absent
|
||
# fields from each loser — the same never-override merge the
|
||
# same-source collision path already applies (#2091/#3372); loser
|
||
# order follows unique_nodes order, so the fill is deterministic.
|
||
merged = winner
|
||
for node in group_nodes:
|
||
if node["id"] != winner_id:
|
||
merged = _merge_missing_attributes(merged, node)
|
||
if merged != winner:
|
||
enriched_by_id[winner_id] = merged
|
||
for member in members:
|
||
if member != winner_id:
|
||
remap[member] = winner_id
|
||
|
||
# ── apply remap ───────────────────────────────────────────────────────────
|
||
if not remap:
|
||
return unique_nodes, edges
|
||
|
||
total = len(remap)
|
||
msg = f"[graphify] Deduplicated {total} node(s)"
|
||
# Both counters are reported when non-zero. Previous form nested the fuzzy
|
||
# branch inside `if exact_merges`, silently dropping the fuzzy count on
|
||
# doc/semantic-heavy runs where Pass 1 finds nothing (#1857).
|
||
parts: list[str] = []
|
||
if exact_merges:
|
||
parts.append(f"{exact_merges} exact")
|
||
if fuzzy_merges:
|
||
parts.append(f"{fuzzy_merges} fuzzy")
|
||
if parts:
|
||
msg += f" ({', '.join(parts)})"
|
||
print(msg + ".", flush=True)
|
||
|
||
# Hyperedge members are node references exactly like edge endpoints, and
|
||
# must follow the survivor for the same reason. Without this the member
|
||
# naming a merged-away id was simply absent from the rebuilt graph: the
|
||
# group lost a participant silently, could fall under the 3-member threshold
|
||
# that makes it a hyperedge at all, and left NO dangling reference, so a
|
||
# referential-integrity check saw nothing wrong (#2805).
|
||
if hyperedges:
|
||
_remap_hyperedge_members(hyperedges, remap)
|
||
|
||
deduped_nodes = [
|
||
enriched_by_id.get(n["id"], n) for n in unique_nodes if n["id"] not in remap
|
||
]
|
||
deduped_edges = []
|
||
for edge in edges:
|
||
e = dict(edge)
|
||
# Tolerate "from"/"to" keys from LLM backends that don't follow the
|
||
# schema exactly — build_from_json normalises later but dedup runs
|
||
# first so bracket access would KeyError here (#803).
|
||
# Use explicit key presence check (not `or`) so empty-string src/tgt
|
||
# aren't silently replaced by the fallback key.
|
||
src = e["source"] if "source" in e else e.get("from")
|
||
tgt = e["target"] if "target" in e else e.get("to")
|
||
if src is None or tgt is None:
|
||
continue
|
||
e["source"] = remap.get(src, src)
|
||
e["target"] = remap.get(tgt, tgt)
|
||
# Remove legacy keys so they don't leak into edge attrs in graph.json.
|
||
e.pop("from", None)
|
||
e.pop("to", None)
|
||
if e["source"] != e["target"]:
|
||
deduped_edges.append(e)
|
||
|
||
return deduped_nodes, deduped_edges
|
||
|
||
|
||
# Keys every node carries (or that describe placement rather than content).
|
||
# They say nothing about which duplicate is the better-established record, so
|
||
# the richness score below ignores them.
|
||
_RICHNESS_IGNORED_KEYS = frozenset({
|
||
"id", "label", "norm_label", "file_type", "source_file", "source_location",
|
||
})
|
||
|
||
|
||
def _content_richness(n: dict) -> int:
|
||
"""How much actual content a node carries, for survivor selection (#3372).
|
||
|
||
Counts populated fields beyond the identity/placement baseline, weighting
|
||
``attributes`` by entry count and ``_merged_from`` by its history length —
|
||
a node that already absorbed prior merges is the established record.
|
||
"""
|
||
score = 0
|
||
for key, value in n.items():
|
||
if key in _RICHNESS_IGNORED_KEYS:
|
||
continue
|
||
if value is None or value == "" or value == [] or value == {}:
|
||
continue
|
||
score += 1
|
||
if key == "attributes" and isinstance(value, dict):
|
||
score += len(value)
|
||
elif key == "_merged_from" and isinstance(value, list):
|
||
score += len(value)
|
||
return score
|
||
|
||
|
||
def _pick_winner(nodes: list[dict]) -> dict:
|
||
"""Pick the canonical survivor: no chunk suffix, then richer content,
|
||
then shorter ID.
|
||
|
||
ID length used to be the primary signal after the chunk-suffix check,
|
||
which made a passing one-line mention on a shallow page (short id, one
|
||
fewer path segment) beat the dedicated, enriched page for the same entity
|
||
— every time the pattern occurred, the established node's content was
|
||
discarded (#3372). Content richness now decides first; ID shape only
|
||
breaks ties between equally-rich candidates, preserving the old
|
||
deterministic ordering there.
|
||
"""
|
||
if not nodes:
|
||
raise ValueError("Cannot pick winner from empty list")
|
||
|
||
def _score(n: dict) -> tuple[int, int, int]:
|
||
has_suffix = bool(_CHUNK_SUFFIX.search(n["id"]))
|
||
return (1 if has_suffix else 0, -_content_richness(n), len(n["id"]))
|
||
|
||
return min(nodes, key=_score)
|
||
|
||
|
||
def _llm_tiebreak(
|
||
candidates: list[dict],
|
||
uf: _UF,
|
||
communities: dict[str, int],
|
||
*,
|
||
backend: str,
|
||
batch_size: int = 30,
|
||
low: float = 75.0,
|
||
high: float = 92.0,
|
||
protected_set: set[str] | None = None,
|
||
get_prot=None,
|
||
union_with_prot=None,
|
||
) -> None:
|
||
"""Batch-resolve ambiguous pairs (score in [low, high)) via LLM."""
|
||
try:
|
||
from graphify.llm import BACKENDS, _format_backend_env_keys, _get_backend_api_key
|
||
if backend not in BACKENDS:
|
||
print(f"[graphify] --dedup-llm: unknown backend {backend!r}, skipping LLM tiebreaker.", flush=True)
|
||
return
|
||
if not _get_backend_api_key(backend):
|
||
env_keys = _format_backend_env_keys(backend)
|
||
print(f"[graphify] --dedup-llm: {env_keys} not set, skipping LLM tiebreaker.", flush=True)
|
||
return
|
||
except ImportError:
|
||
return
|
||
|
||
ambiguous: list[tuple[dict, dict, float]] = []
|
||
for i, node in enumerate(candidates):
|
||
norm_i = _norm(node.get("label", node.get("id", "")))
|
||
for j in range(i + 1, len(candidates)):
|
||
neighbor = candidates[j]
|
||
if uf.find(node["id"]) == uf.find(neighbor["id"]):
|
||
continue
|
||
norm_j = _norm(neighbor.get("label", neighbor.get("id", "")))
|
||
# Mirror pass 2: plain Jaro for cross-file long labels (#1243).
|
||
_xfile = (node.get("source_file") or "") != (neighbor.get("source_file") or "")
|
||
if _xfile and max(len(norm_i), len(norm_j)) >= 12:
|
||
score = Jaro.normalized_similarity(norm_i, norm_j) * 100
|
||
else:
|
||
score = JaroWinkler.normalized_similarity(norm_i, norm_j) * 100
|
||
if _is_variant_pair(norm_i, norm_j):
|
||
continue
|
||
if _short_label_blocked(norm_i, norm_j, score):
|
||
continue
|
||
_lo, _hi = sorted((norm_i, norm_j), key=len)
|
||
if _hi.startswith(_lo) and _hi != _lo:
|
||
continue
|
||
# Mirror pass 2: decisively-distinct pairs never reach the LLM
|
||
# (#1284, #2576).
|
||
if _numeric_tokens_differ(norm_i, norm_j):
|
||
continue
|
||
if _content_token_swap(norm_i, norm_j):
|
||
continue
|
||
if _crossfile_fileanchored_blocked(node, neighbor):
|
||
continue
|
||
c1 = communities.get(node["id"])
|
||
c2 = communities.get(neighbor["id"])
|
||
if (c1 is not None and c2 is not None and c1 == c2
|
||
and min(len(norm_i), len(norm_j)) >= 12):
|
||
score += _COMMUNITY_BOOST
|
||
if low <= score < high:
|
||
if protected_set and get_prot is not None:
|
||
px = get_prot(node["id"])
|
||
py = get_prot(neighbor["id"])
|
||
if px is not None and py is not None and px != py:
|
||
continue
|
||
ambiguous.append((node, neighbor, score))
|
||
|
||
if not ambiguous:
|
||
return
|
||
|
||
try:
|
||
from graphify.llm import _call_llm
|
||
except ImportError as exc:
|
||
# F-038: previously this silent fallback hid the fact that `_call_llm`
|
||
# didn't exist in `graphify.llm` at all, so `--dedup-llm` was a no-op.
|
||
# Surface the import failure so future regressions are visible.
|
||
print(
|
||
f"[graphify] --dedup-llm: cannot import _call_llm ({exc}); skipping LLM tiebreaker.",
|
||
flush=True,
|
||
)
|
||
return
|
||
|
||
for batch_start in range(0, len(ambiguous), batch_size):
|
||
batch = ambiguous[batch_start : batch_start + batch_size]
|
||
pairs_text = "\n".join(
|
||
f"{i+1}. \"{a['label']}\" vs \"{b['label']}\""
|
||
for i, (a, b, _) in enumerate(batch)
|
||
)
|
||
prompt = (
|
||
"For each pair below, answer only 'yes' or 'no': are they the same real-world concept?\n\n"
|
||
f"{pairs_text}\n\n"
|
||
"Reply with one line per pair: '1. yes', '2. no', etc."
|
||
)
|
||
try:
|
||
response = _call_llm(prompt, backend=backend, max_tokens=200)
|
||
lines = response.strip().splitlines()
|
||
for line in lines:
|
||
line = line.strip()
|
||
if not line:
|
||
continue
|
||
parts = line.split(".", 1)
|
||
if len(parts) != 2:
|
||
continue
|
||
try:
|
||
idx = int(parts[0].strip()) - 1
|
||
except ValueError:
|
||
continue
|
||
if 0 <= idx < len(batch):
|
||
answer = parts[1].strip().lower()
|
||
if answer.startswith("yes"):
|
||
a, b, _ = batch[idx]
|
||
if protected_set and get_prot is not None and union_with_prot is not None:
|
||
px = get_prot(a["id"])
|
||
py = get_prot(b["id"])
|
||
if px is not None and py is not None and px != py:
|
||
continue
|
||
if a["id"] in protected_set:
|
||
winner = a
|
||
elif b["id"] in protected_set:
|
||
winner = b
|
||
else:
|
||
winner = _pick_winner([a, b])
|
||
union_with_prot(winner["id"], a["id"])
|
||
union_with_prot(winner["id"], b["id"])
|
||
else:
|
||
winner = _pick_winner([a, b])
|
||
uf.union(winner["id"], a["id"])
|
||
uf.union(winner["id"], b["id"])
|
||
except Exception as exc:
|
||
print(f"[graphify] --dedup-llm batch failed: {exc}", flush=True)
|