Onset: version control where nobody waits and nothing gets lost. The on command, its core and onset-server.
| 1 | //! Renames: files that moved between two trees, found by their content, as |
| 2 | //! git finds them. A removed path and an added one are the same file when |
| 3 | //! the content is identical, or (for text) when at least half the lines are |
| 4 | //! the same. Merges use them so an edit follows a file to its new name, and |
| 5 |
| 6 |
| 7 | use std::collections::{BTreeMap, HashMap}; |
| 8 |
| 9 | use crate::object::{Kind, Object}; |
| 10 | use crate::tree::{self, Change, Entry, EntryKind, TreeEntry}; |
| 11 | use crate::{Id, Result, Source, chunk, diff}; |
| 12 |
| 13 | /// How alike two files must be (shared lines over all lines) to be one file that moved. |
| 14 | const SIMILAR: f64 = 0.5; |
| 15 | /// Similar-content pairs compared at most; past this only identical content counts. |
| 16 | const MOST_PAIRS: usize = 2500; |
| 17 | /// Files bigger than this only count when identical. |
| 18 | const MOST_BYTES: u64 = 512 * 1024; |
| 19 |
| 20 | /// The renames in `changes` (from `tree::diff_trees`): (from, to) pairs. |
| 21 | pub fn renames(src: &dyn Source, changes: &BTreeMap<String, Change>) -> Result<Vec<(String, String)>> { |
| 22 | let file = |e: &Entry| e.kind != EntryKind::Tree && e.kind != EntryKind::Gitlink; |
| 23 | let removed: Vec<(&String, &Entry)> = changes.iter().filter_map(|(p, c)| if let Change::Removed(e) = c { file(e).then_some((p, e)) } else { None }).collect(); |
| 24 | let added: Vec<(&String, &Entry)> = changes.iter().filter_map(|(p, c)| if let Change::Added(e) = c { file(e).then_some((p, e)) } else { None }).collect(); |
| 25 | if removed.is_empty() || added.is_empty() { |
| 26 | return Ok(Vec::new()); |
| 27 | } |
| 28 | let mut out = Vec::new(); |
| 29 | let mut used_from = vec![false; removed.len()]; |
| 30 | let mut used_to = vec![false; added.len()]; |
| 31 | // Identical content first. |
| 32 | let mut by_id: HashMap<Id, Vec<usize>> = HashMap::new(); |
| 33 | for (i, (_, e)) in removed.iter().enumerate() { |
| 34 | by_id.entry(e.id).or_default().push(i); |
| 35 | } |
| 36 | for (j, (to, e)) in added.iter().enumerate() { |
| 37 | if let Some(i) = by_id.get_mut(&e.id).and_then(|v| (!v.is_empty()).then(|| v.remove(0))) { |
| 38 | used_from[i] = true; |
| 39 | used_to[j] = true; |
| 40 | out.push((removed[i].0.clone(), (*to).clone())); |
| 41 | } |
| 42 | } |
| 43 | // Then similar text, best pairs first. |
| 44 | let from_left: Vec<usize> = (0..removed.len()).filter(|i| !used_from[*i]).collect(); |
| 45 | let to_left: Vec<usize> = (0..added.len()).filter(|j| !used_to[*j]).collect(); |
| 46 | if from_left.is_empty() || to_left.is_empty() || from_left.len() * to_left.len() > MOST_PAIRS { |
| 47 | return Ok(out); |
| 48 | } |
| 49 | let lines_of = |id: &Id| -> Result<Option<HashMap<Vec<u8>, usize>>> { |
| 50 | let Some(o) = src.get(id)? else { return Ok(None) }; |
| 51 | if o.kind == Kind::Chunks && chunk::file_size(src, id)? > MOST_BYTES { |
| 52 | return Ok(None); |
| 53 | } |
| 54 | let data = chunk::read_file(src, id)?; |
| 55 | if data.len() as u64 > MOST_BYTES || diff::is_binary(&data) { |
| 56 | return Ok(None); |
| 57 | } |
| 58 | let mut counts: HashMap<Vec<u8>, usize> = HashMap::new(); |
| 59 | for line in diff::lines(&data) { |
| 60 | *counts.entry(line.to_vec()).or_default() += 1; |
| 61 | } |
| 62 | Ok(Some(counts)) |
| 63 | }; |
| 64 | let froms: Vec<Option<HashMap<Vec<u8>, usize>>> = from_left.iter().map(|i| lines_of(&removed[*i].1.id)).collect::<Result<_>>()?; |
| 65 | let tos: Vec<Option<HashMap<Vec<u8>, usize>>> = to_left.iter().map(|j| lines_of(&added[*j].1.id)).collect::<Result<_>>()?; |
| 66 | let mut scored: Vec<(f64, usize, usize)> = Vec::new(); |
| 67 | for (a, fa) in froms.iter().enumerate() { |
| 68 | let Some(fa) = fa else { continue }; |
| 69 | let total_a: usize = fa.values().sum(); |
| 70 | for (b, tb) in tos.iter().enumerate() { |
| 71 | let Some(tb) = tb else { continue }; |
| 72 | let total_b: usize = tb.values().sum(); |
| 73 | if total_a + total_b == 0 { |
| 74 | continue; |
| 75 | } |
| 76 | let common: usize = fa.iter().map(|(line, n)| (*n).min(*tb.get(line).unwrap_or(&0))).sum(); |
| 77 | let score = 2.0 * common as f64 / (total_a + total_b) as f64; |
| 78 | if score >= SIMILAR { |
| 79 | scored.push((score, a, b)); |
| 80 | } |
| 81 | } |
| 82 | } |
| 83 | scored.sort_by(|x, y| y.0.total_cmp(&x.0).then(x.1.cmp(&y.1)).then(x.2.cmp(&y.2))); |
| 84 | let (mut taken_a, mut taken_b) = (vec![false; froms.len()], vec![false; tos.len()]); |
| 85 | for (_, a, b) in scored { |
| 86 | if taken_a[a] || taken_b[b] { |
| 87 | continue; |
| 88 | } |
| 89 | taken_a[a] = true; |
| 90 | taken_b[b] = true; |
| 91 | out.push((removed[from_left[a]].0.clone(), added[to_left[b]].0.clone())); |
| 92 | } |
| 93 | out.sort(); |
| 94 | Ok(out) |
| 95 | } |
| 96 |
| 97 | /// Where `path` in `new` came from, when it's a file that moved there from `old`. |
| 98 | pub fn renamed_from(src: &dyn Source, old: &Id, new: &Id, path: &str) -> Result<Option<String>> { |
| 99 | let changes = tree::diff_trees(src, old, new)?; |
| 100 | if !matches!(changes.get(path), Some(Change::Added(_))) { |
| 101 | return Ok(None); |
| 102 | } |
| 103 | Ok(renames(src, &changes)?.into_iter().find(|(_, to)| to == path).map(|(from, _)| from)) |
| 104 | } |
| 105 |
| 106 | /// `tree` with `from` gone and `entry` at `to` (a file moved), and the new trees. |
| 107 | pub fn moved(src: &dyn Source, tree: &Id, from: &str, to: &str, entry: Entry) -> Result<(Id, Vec<Object>)> { |
| 108 | let mut objects = Vec::new(); |
| 109 | let without = set(src, Some(tree), from, None, &mut objects)?.unwrap_or_else(tree::empty_id); |
| 110 | let id = set(src, Some(&without), to, Some(entry), &mut objects)?.unwrap_or_else(tree::empty_id); |
| 111 | Ok((id, objects)) |
| 112 | } |
| 113 |
| 114 | /// `tree` with `path` set to `entry` (None: removed); None when that leaves it empty. |
| 115 | fn set(src: &dyn Source, tree: Option<&Id>, path: &str, entry: Option<Entry>, objects: &mut Vec<Object>) -> Result<Option<Id>> { |
| 116 | let read = |id: &Id, objects: &[Object]| -> Result<Vec<TreeEntry>> { |
| 117 | match objects.iter().find(|o| o.id() == *id) { |
| 118 | Some(o) => tree::decode(&o.data), |
| 119 | None => tree::read(src, id), |
| 120 | } |
| 121 | }; |
| 122 | let mut entries = match tree { |
| 123 | Some(t) => read(t, objects)?, |
| 124 | None => Vec::new(), |
| 125 | }; |
| 126 | let (head, rest) = match path.split_once('/') { |
| 127 | Some((h, r)) => (h, Some(r)), |
| 128 | None => (path, None), |
| 129 | }; |
| 130 | let at = entries.iter().position(|e| e.name == head); |
| 131 | let next = match rest { |
| 132 | None => entry, |
| 133 | Some(rest) => { |
| 134 | let inner = at.and_then(|i| (entries[i].kind == EntryKind::Tree).then_some(entries[i].id)); |
| 135 | set(src, inner.as_ref(), rest, entry, objects)?.map(|id| Entry { kind: EntryKind::Tree, id }) |
| 136 | } |
| 137 | }; |
| 138 | match (at, next) { |
| 139 | (Some(i), Some(e)) => entries[i] = TreeEntry { name: head.to_string(), kind: e.kind, id: e.id }, |
| 140 | (Some(i), None) => { |
| 141 | entries.remove(i); |
| 142 | } |
| 143 | (None, Some(e)) => entries.push(TreeEntry { name: head.to_string(), kind: e.kind, id: e.id }), |
| 144 | (None, None) => {} |
| 145 | } |
| 146 | if entries.is_empty() { |
| 147 | return Ok(None); |
| 148 | } |
| 149 | entries.sort_by(|a, b| a.name.cmp(&b.name)); |
| 150 | let object = Object::new(Kind::Tree, tree::encode(&entries)); |
| 151 | let id = object.id(); |
| 152 | objects.push(object); |
| 153 | Ok(Some(id)) |
| 154 | } |
| 155 |
| 156 | #[cfg(test)] |
| 157 | mod tests { |
| 158 | use super::*; |
| 159 | use crate::MemSource; |
| 160 |
| 161 | fn files(src: &mut MemSource, list: &[(&str, &str)]) -> Id { |
| 162 | let mut map = tree::Files::new(); |
| 163 | for (path, content) in list { |
| 164 | let objects = chunk::file_objects(content.as_bytes()); |
| 165 | let id = objects[0].id(); |
| 166 | for o in objects { |
| 167 | src.put(o); |
| 168 | } |
| 169 | map.insert(path.to_string(), Entry { kind: EntryKind::File, id }); |
| 170 | } |
| 171 | let (id, objects) = tree::build(&map); |
| 172 | for o in objects { |
| 173 | src.put(o); |
| 174 | } |
| 175 | id |
| 176 | } |
| 177 |
| 178 | #[test] |
| 179 | fn finds_moves() { |
| 180 | let mut src = MemSource::default(); |
| 181 | let text: String = (0..40).map(|i| format!("line {i}\n")).collect(); |
| 182 | let edited = text.replace("line 3\n", "line three\n"); |
| 183 | let a = files(&mut src, &[("src/old.rs", &text), ("same.txt", "same\n"), ("gone.txt", "bye\n")]); |
| 184 | let b = files(&mut src, &[("src/new.rs", &edited), ("lib/same.txt", "same\n"), ("other.txt", "unrelated\nstuff\n")]); |
| 185 | let changes = tree::diff_trees(&src, &a, &b).unwrap(); |
| 186 | let found = renames(&src, &changes).unwrap(); |
| 187 | assert_eq!(found, vec![("same.txt".to_string(), "lib/same.txt".to_string()), ("src/old.rs".to_string(), "src/new.rs".to_string())]); |
| 188 | assert_eq!(renamed_from(&src, &a, &b, "src/new.rs").unwrap().as_deref(), Some("src/old.rs")); |
| 189 | assert_eq!(renamed_from(&src, &a, &b, "other.txt").unwrap(), None); |
| 190 | } |
| 191 |
| 192 | #[test] |
| 193 | fn moves_entries() { |
| 194 | let mut src = MemSource::default(); |
| 195 | let a = files(&mut src, &[("a/x.txt", "x\n"), ("b.txt", "b\n")]); |
| 196 | let x = tree::lookup(&src, &a, "a/x.txt").unwrap().unwrap(); |
| 197 | let (moved_tree, objects) = moved(&src, &a, "a/x.txt", "c/d/x.txt", x).unwrap(); |
| 198 | for o in objects { |
| 199 | src.put(o); |
| 200 | } |
| 201 | let flat = tree::flatten(&src, &moved_tree).unwrap(); |
| 202 | assert_eq!(flat.keys().cloned().collect::<Vec<_>>(), vec!["b.txt".to_string(), "c/d/x.txt".to_string()]); |
| 203 | } |
| 204 | } |
| 205 |