///| Rename detection for merge
///|
priv struct SideRenames {
/// old_path -> new_path
old_to_new : Map[String, String]
/// Paths where original content was replaced with new content (add-source)
add_source_paths : Map[String, Bool]
}
///|
/// Detect renames between base and a side (ours or theirs).
///
/// Phase 1: Exact OID matching (fast)
/// Phase 2: Content similarity matching for unmatched pairs (threshold 50%)
///
/// Handles add-source pattern: file at old_path has different OID in side
/// (replaced), and the base content appears at a new_path in side.
fn merge_detect_renames(
base : Map[String, TreeFileEntry],
side : Map[String, TreeFileEntry],
db : ObjectDb,
rfs : &@bit.RepoFileSystem,
) -> SideRenames {
// Potential rename sources: paths whose base content disappeared from that path
let sources : Array[(String, TreeFileEntry)] = []
let replaced_paths : Map[String, Bool] = Map([])
// merge-ort turns rename_empty off: an empty blob is never a rename
// source or destination.
let empty = @bit.hash_blob(Bytes::new(0))
for path, entry in base {
if entry.id == empty {
continue
}
// merge-ort does no break detection (break_opt = -1): only a path the
// side deleted can be a rename source, never one it only modified.
if !side.contains(path) {
sources.push((path, entry))
}
}
// Added paths: in side but not in base
let added : Array[(String, TreeFileEntry)] = []
for path, entry in side {
if !base.contains(path) && entry.id != empty {
added.push((path, entry))
}
}
let old_to_new : Map[String, String] = Map([])
let add_source_paths : Map[String, Bool] = Map([])
let matched_source : Map[String, Bool] = Map([])
let matched_added : Map[String, Bool] = Map([])
// Phase 1: Build OID index for exact matching
let source_by_oid : Map[String, Array[String]] = Map([])
for item in sources {
let (path, entry) = item
let hex = entry.id.to_hex()
match source_by_oid.get(hex) {
Some(arr) => arr.push(path)
None => source_by_oid[hex] = [path]
}
}
for item in added {
let (new_path, entry) = item
if matched_added.contains(new_path) {
continue
}
let hex = entry.id.to_hex()
match source_by_oid.get(hex) {
Some(candidates) =>
for old_path in candidates {
if !matched_source.contains(old_path) {
old_to_new[old_path] = new_path
matched_source[old_path] = true
matched_added[new_path] = true
if replaced_paths.contains(old_path) {
add_source_paths[old_path] = true
}
break
}
}
None => ()
}
}
// Phase 2: Content similarity for unmatched pairs
// Collect unmatched sources and added files
let unmatched_sources : Array[(String, TreeFileEntry)] = []
for item in sources {
let (path, _) = item
if !matched_source.contains(path) {
unmatched_sources.push(item)
}
}
let unmatched_added : Array[(String, TreeFileEntry)] = []
for item in added {
let (path, _) = item
if !matched_added.contains(path) {
unmatched_added.push(item)
}
}
if unmatched_sources.length() > 0 && unmatched_added.length() > 0 {
// Compute similarities and find best matches
let best_matches : Array[(String, String, Int)] = []
for src_item in unmatched_sources {
let (src_path, src_entry) = src_item
let src_text = get_blob_content(db, rfs, src_entry.id)
if src_text.length() == 0 {
continue
}
let mut best_score = 0
let mut best_path = ""
for add_item in unmatched_added {
let (add_path, add_entry) = add_item
if matched_added.contains(add_path) {
continue
}
let add_text = get_blob_content(db, rfs, add_entry.id)
if add_text.length() == 0 {
continue
}
let score = rename_similarity_score(src_text, add_text)
if score > best_score {
best_score = score
best_path = add_path
}
}
if best_score >= 50 && best_path.length() > 0 {
best_matches.push((src_path, best_path, best_score))
}
}
// Sort by score descending, then greedily assign
best_matches.sort_by(fn(a, b) { b.2.compare(a.2) })
for item in best_matches {
let (src_path, add_path, _) = item
if matched_source.contains(src_path) || matched_added.contains(add_path) {
continue
}
old_to_new[src_path] = add_path
matched_source[src_path] = true
matched_added[add_path] = true
if replaced_paths.contains(src_path) {
add_source_paths[src_path] = true
}
}
}
{ old_to_new, add_source_paths }
}
///|
/// Compute similarity score (0-100) between two text contents, weighted by
/// bytes like git's diffcore (bytes of shared lines over the larger size),
/// so a few short common lines do not make two files "renames".
fn rename_similarity_score(a : String, b : String) -> Int {
let a_lines : Array[String] = a.split("\n").map(l => l.to_owned()).collect()
let b_lines : Array[String] = b.split("\n").map(l => l.to_owned()).collect()
// Each line counts with its newline; a trailing "" after the final \n
// is not a line.
let weight = fn(l : String) { l.length() + 1 }
let total = fn(lines : Array[String]) {
let mut t = 0
for i, l in lines {
if i == lines.length() - 1 && l.length() == 0 {
continue
}
t += weight(l)
}
t
}
let total_a = total(a_lines)
let total_b = total(b_lines)
if total_a == 0 && total_b == 0 {
return 100
}
if total_a == 0 || total_b == 0 {
return 0
}
let b_set : Map[String, Int] = Map([])
for i, line in b_lines {
if i == b_lines.length() - 1 && line.length() == 0 {
continue
}
b_set[line] = b_set.get(line).unwrap_or(0) + 1
}
let mut common = 0
for i, line in a_lines {
if i == a_lines.length() - 1 && line.length() == 0 {
continue
}
let count = b_set.get(line).unwrap_or(0)
if count > 0 {
common += weight(line)
b_set[line] = count - 1
}
}
let max_total = if total_a > total_b { total_a } else { total_b }
100 * common / max_total
}
///|
/// Directory renames of one side, like merge-ort's: for each rename the
/// directory portion that changed (common trailing components stripped);
/// a base directory counts only when the side removed it entirely, and it
/// maps to the target most of its renames went to (a tie is no rename).
fn merge_dir_renames(
base : Map[String, TreeFileEntry],
side : Map[String, TreeFileEntry],
renames : SideRenames,
) -> Map[String, String] {
let counts : Map[String, Map[String, Int]] = Map([])
for old_path, new_path in renames.old_to_new {
let od = merge_dirname_parts(old_path)
let nd = merge_dirname_parts(new_path)
while od.length() > 0 && nd.length() > 0 && od[od.length() - 1] == nd[nd.length() - 1] {
ignore(od.pop())
ignore(nd.pop())
}
if od.length() == 0 {
continue
}
let o = od.join("/")
let n = nd.join("/")
let m = match counts.get(o) {
Some(m) => m
None => {
let m : Map[String, Int] = Map([])
counts[o] = m
m
}
}
m[n] = m.get(n).unwrap_or(0) + 1
}
let out : Map[String, String] = Map([])
for old_dir, targets in counts {
let prefix = old_dir + "/"
// The side must have removed the directory entirely.
if side.keys().any(p => p.has_prefix(prefix)) ||
!base.keys().any(p => p.has_prefix(prefix)) {
continue
}
let mut best = ""
let mut best_n = 0
let mut tie = false
for t, n in targets {
if n > best_n {
best = t
best_n = n
tie = false
} else if n == best_n {
tie = true
}
}
if !tie && best_n > 0 {
out[old_dir] = best
}
}
out
}
///|
fn merge_dirname_parts(path : String) -> Array[String] {
let parts = path.split("/").map(v => v.to_string()).collect()
ignore(parts.pop())
parts
}