300 lines · 12 KBtext/plain; charset=utf-8
Onset: version control where nobody waits and nothing gets lost. The on command, its core and onset-server.
| 6 |
| 7 | use crate::tree::{self, Entry, EntryKind}; |
| 8 | use crate::{Id, Result, Source, diff}; |
| 9 |
| 10 | /// What `entries` found: the path's entry in every tree, or the trees it |
| 11 | /// needs first (all of one level at once, so a host loads them together). |
| 12 | pub enum Found { |
| 13 | All(Vec<Option<Entry>>), |
| 14 | Need(Vec<Id>), |
| 15 | } |
| 16 |
| 17 | /// The entry at `path` in each of `trees` (None: not there), reading only |
| 18 | /// the folders on the path. |
| 19 | pub fn entries(src: &dyn Source, trees: &[Id], path: &str) -> Result<Found> { |
| 20 | let mut at: Vec<Option<Entry>> = trees.iter().map(|t| Some(Entry { kind: EntryKind::Tree, id: *t })).collect(); |
| 21 | for part in path.split('/').filter(|p| !p.is_empty()) { |
| 22 | let mut need: Vec<Id> = Vec::new(); |
| 23 | for e in at.iter().flatten() { |
| 24 | if e.kind == EntryKind::Tree && src.get(&e.id)?.is_none() { |
| 25 | need.push(e.id); |
| 26 | } |
| 27 | } |
| 28 | if !need.is_empty() { |
| 29 | need.sort(); |
| 30 | need.dedup(); |
| 31 | return Ok(Found::Need(need)); |
| 32 | } |
| 33 | // Versions share most folders: each is read once. |
| 34 | let mut seen: HashMap<Id, Option<Entry>> = HashMap::new(); |
| 35 | for slot in at.iter_mut() { |
| 36 | let next = match *slot { |
| 37 | Some(e) if e.kind == EntryKind::Tree => match seen.get(&e.id) { |
| 38 | Some(found) => *found, |
| 39 | None => { |
| 40 | let found = tree::read(src, &e.id)?.into_iter().find(|x| x.name == part).map(|x| Entry { kind: x.kind, id: x.id }); |
| 41 | seen.insert(e.id, found); |
| 42 | found |
| 43 | } |
| 44 | }, |
| 45 | _ => None, |
| 46 | }; |
| 47 | *slot = next; |
| 48 | } |
| 49 | } |
| 50 | Ok(Found::All(at)) |
| 51 | } |
| 52 |
| 53 | #[derive(Debug, Clone, Copy, PartialEq, Eq)] |
| 54 | pub enum Kind { |
| 55 | Added, |
| 56 | Modified, |
| 57 | Removed, |
| 58 | } |
| 59 |
| 60 | /// The versions that changed the path, newest first, from its entry in |
| 61 | /// each version (`versions` newest first). The oldest version given counts |
| 62 | /// as a change only when it's version 1 (`from_start`): otherwise what came |
| 63 | /// before it isn't known. |
| 64 | pub fn changes(versions: &[u64], entries: &[Option<Entry>], from_start: bool) -> Vec<(u64, Kind, Option<Entry>)> { |
| 65 | let mut out = Vec::new(); |
| 66 | for (i, (n, after)) in versions.iter().zip(entries).enumerate() { |
| 67 | let before = match entries.get(i + 1) { |
| 68 | Some(b) => *b, |
| 69 | None if from_start => None, |
| 70 | None => break, |
| 71 | }; |
| 72 | let kind = match (before, after) { |
| 73 | (None, Some(_)) => Kind::Added, |
| 74 | (Some(_), None) => Kind::Removed, |
| 75 | (Some(b), Some(a)) if b != *a => Kind::Modified, |
| 76 | _ => continue, |
| 77 | }; |
| 78 | out.push((*n, kind, *after)); |
| 79 | } |
| 80 | out |
| 81 | } |
| 82 |
| 83 | /// What `touched` found: for each pair, the paths it changes (None: more |
| 84 | /// than the most asked for), or the folders it needs first. |
| 85 | pub enum Touched { |
| 86 | All(Vec<Option<Vec<String>>>), |
| 87 | Need(Vec<Id>), |
| 88 | } |
| 89 |
| 90 | /// The paths each (before, after) pair of trees changes: files and links |
| 91 | /// that differ, and folders added or removed whole as just the folder. |
| 92 | /// Hosts keep this with each version, so a path's history reads only the |
| 93 | /// versions that touched it (git's changed-path filters do the same). |
| 94 | /// Works a level at a time across all pairs, naming every folder a level |
| 95 | /// needs at once. |
| 96 | pub fn touched(src: &dyn Source, pairs: &[(Option<Id>, Id)], most: usize) -> Result<Touched> { |
| 97 | let mut out: Vec<Option<Vec<String>>> = vec![Some(Vec::new()); pairs.len()]; |
| 98 | let mut level: Vec<(usize, String, Option<Id>, Option<Id>)> = |
| 99 | pairs.iter().enumerate().filter(|(_, (a, b))| a.as_ref() != Some(b)).map(|(i, (a, b))| (i, String::new(), *a, Some(*b))).collect(); |
| 100 | while !level.is_empty() { |
| 101 | let mut need: Vec<Id> = Vec::new(); |
| 102 | for (_, _, a, b) in &level { |
| 103 | for t in [a, b].into_iter().flatten() { |
| 104 | if src.get(t)?.is_none() { |
| 105 | need.push(*t); |
| 106 | } |
| 107 | } |
| 108 | } |
| 109 | if !need.is_empty() { |
| 110 | need.sort(); |
| 111 | need.dedup(); |
| 112 | return Ok(Touched::Need(need)); |
| 113 | } |
| 114 | let mut next = Vec::new(); |
| 115 | for (i, prefix, a, b) in level { |
| 116 | let Some(paths) = &mut out[i] else { continue }; |
| 117 | let read = |t: Option<Id>| -> Result<Vec<tree::TreeEntry>> { t.map(|t| tree::read(src, &t)).unwrap_or(Ok(Vec::new())) }; |
| 118 | let (ea, eb) = (read(a)?, read(b)?); |
| 119 | let path = |name: &str| if prefix.is_empty() { name.to_string() } else { format!("{prefix}/{name}") }; |
| 120 | // Both are sorted by name. |
| 121 | let (mut x, mut y) = (0, 0); |
| 122 | while x < ea.len() || y < eb.len() { |
| 123 | let order = match (ea.get(x), eb.get(y)) { |
| 124 | (Some(l), Some(r)) => l.name.as_bytes().cmp(r.name.as_bytes()), |
| 125 | (Some(_), None) => std::cmp::Ordering::Less, |
| 126 | _ => std::cmp::Ordering::Greater, |
| 127 | }; |
| 128 | match order { |
| 129 | std::cmp::Ordering::Less => { |
| 130 | paths.push(path(&ea[x].name)); |
| 131 | x += 1; |
| 132 | } |
| 133 | std::cmp::Ordering::Greater => { |
| 134 | paths.push(path(&eb[y].name)); |
| 135 | y += 1; |
| 136 | } |
| 137 | std::cmp::Ordering::Equal => { |
| 138 | let (l, r) = (&ea[x], &eb[y]); |
| 139 | if l.kind == EntryKind::Tree && r.kind == EntryKind::Tree && l.id != r.id { |
| 140 | next.push((i, path(&l.name), Some(l.id), Some(r.id))); |
| 141 | } else if l.kind != r.kind || l.id != r.id { |
| 142 | paths.push(path(&l.name)); |
| 143 | } |
| 144 | x += 1; |
| 145 | y += 1; |
| 146 | } |
| 147 | } |
| 148 | } |
| 149 | if paths.len() > most { |
| 150 | out[i] = None; |
| 151 | } |
| 152 | } |
| 153 | level = next.into_iter().filter(|(i, ..)| out[*i].is_some()).collect(); |
| 154 | } |
| 155 | Ok(Touched::All(out)) |
| 156 | } |
| 157 |
| 158 | /// Whether a version whose changed paths are `touched` (from [`touched`]) |
| 159 | /// may have changed `path`: a path it lists is the path, under it, or a |
| 160 | /// folder holding it. |
| 161 | pub fn may_touch(touched: &[String], path: &str) -> bool { |
| 162 | let under = |p: &str, folder: &str| folder.is_empty() || p == folder || (p.starts_with(folder) && p.as_bytes().get(folder.len()) == Some(&b'/')); |
| 163 | touched.iter().any(|t| under(t, path) || under(path, t)) |
| 164 | } |
| 165 |
| 166 | /// Which version last changed each line of a file. `points` are the |
| 167 | /// versions that changed it, newest first, with the file's content after |
| 168 | /// each (empty where it was removed); the last is where it began (or the |
| 169 | /// oldest known). Answers a version per line of the newest content. |
| 170 | pub fn blame(points: &[(u64, &[u8])]) -> Vec<u64> { |
| 171 | let Some((_, newest)) = points.first() else { return Vec::new() }; |
| 172 | let count = diff::lines(newest).len(); |
| 173 | let mut owner = vec![points.last().map(|p| p.0).unwrap_or(0); count]; |
| 174 | // Where each of the newest lines is in the version being looked at. |
| 175 | let mut track: Vec<Option<u32>> = (0..count as u32).map(Some).collect(); |
| 176 | for (k, (n, cur)) in points.iter().enumerate() { |
| 177 | let Some((_, prev)) = points.get(k + 1) else { break }; |
| 178 | // Lines the version didn't touch map to the version before it. |
| 179 | let mut map: Vec<Option<u32>> = vec![None; diff::lines(cur).len()]; |
| 180 | let (mut old, mut new) = (0u32, 0u32); |
| 181 | for h in diff::hunks(prev, cur) { |
| 182 | while new < h.after.start { |
| 183 | map[new as usize] = Some(old); |
| 184 | new += 1; |
| 185 | old += 1; |
| 186 | } |
| 187 | new = h.after.end; |
| 188 | old = h.before.end; |
| 189 | } |
| 190 | while (new as usize) < map.len() { |
| 191 | map[new as usize] = Some(old); |
| 192 | new += 1; |
| 193 | old += 1; |
| 194 | } |
| 195 | let mut left = false; |
| 196 | for (line, t) in track.iter_mut().enumerate() { |
| 197 | if let Some(at) = *t { |
| 198 | match map.get(at as usize).copied().flatten() { |
| 199 | Some(before) => { |
| 200 | *t = Some(before); |
| 201 | left = true; |
| 202 | } |
| 203 | None => { |
| 204 | owner[line] = *n; |
| 205 | *t = None; |
| 206 | } |
| 207 | } |
| 208 | } |
| 209 | } |
| 210 | if !left { |
| 211 | break; |
| 212 | } |
| 213 | } |
| 214 | owner |
| 215 | } |
| 216 |
| 217 | #[cfg(test)] |
| 218 | mod tests { |
| 219 | use super::*; |
| 220 | use crate::tree::Files; |
| 221 | use crate::{MemSource, Object}; |
| 222 |
| 223 | fn version(src: &mut MemSource, files: &[(&str, &str)]) -> Id { |
| 224 | let f: Files = files.iter().map(|(p, c)| (p.to_string(), Entry { kind: EntryKind::File, id: src.put(Object::blob(c.as_bytes().to_vec())) })).collect(); |
| 225 | let (root, objects) = tree::build(&f); |
| 226 | for o in objects { |
| 227 | src.put(o); |
| 228 | } |
| 229 | root |
| 230 | } |
| 231 |
| 232 | #[test] |
| 233 | fn history_of_a_file_and_a_folder() { |
| 234 | let mut src = MemSource::default(); |
| 235 | // Newest first: 4 removes it, 3 changes it, 2 leaves it, 1 adds it. |
| 236 | let trees = [ |
| 237 | version(&mut src, &[("other.txt", "o2")]), |
| 238 | version(&mut src, &[("src/a.txt", "a2"), ("other.txt", "o2")]), |
| 239 | version(&mut src, &[("src/a.txt", "a1"), ("other.txt", "o2")]), |
| 240 | version(&mut src, &[("src/a.txt", "a1"), ("other.txt", "o1")]), |
| 241 | ]; |
| 242 | let Found::All(found) = entries(&src, &trees, "src/a.txt").unwrap() else { panic!("all here") }; |
| 243 | let got: Vec<(u64, Kind)> = changes(&[4, 3, 2, 1], &found, true).into_iter().map(|(n, k, _)| (n, k)).collect(); |
| 244 | assert_eq!(got, vec![(4, Kind::Removed), (3, Kind::Modified), (1, Kind::Added)]); |
| 245 | // Without version 1, its start isn't known. |
| 246 | assert_eq!(changes(&[4, 3, 2], &found[..3], false).len(), 2); |
| 247 | let Found::All(dir) = entries(&src, &trees, "src").unwrap() else { panic!() }; |
| 248 | assert_eq!(changes(&[4, 3, 2, 1], &dir, true).len(), 3); |
| 249 |
| 250 | // Missing folders are named a level at a time. |
| 251 | let empty = MemSource::default(); |
| 252 | let Found::Need(need) = entries(&empty, &trees, "src/a.txt").unwrap() else { panic!("needs the roots") }; |
| 253 | assert_eq!(need.len(), 4); |
| 254 | } |
| 255 |
| 256 | #[test] |
| 257 | fn touched_paths() { |
| 258 | let mut src = MemSource::default(); |
| 259 | let v1 = version(&mut src, &[("README.md", "r"), ("src/a.txt", "a1"), ("src/deep/b.txt", "b")]); |
| 260 | let v2 = version(&mut src, &[("README.md", "r"), ("src/a.txt", "a2"), ("src/deep/b.txt", "b"), ("docs/x.md", "x")]); |
| 261 | let v3 = version(&mut src, &[("README.md", "r2"), ("src/a.txt", "a2"), ("docs/x.md", "x")]); |
| 262 | let Touched::All(got) = touched(&src, &[(None, v1), (Some(v1), v2), (Some(v2), v3), (Some(v3), v3)], 100).unwrap() else { panic!("all here") }; |
| 263 | let sorted = |p: &Option<Vec<String>>| { |
| 264 | let mut p = p.clone().unwrap(); |
| 265 | p.sort(); |
| 266 | p |
| 267 | }; |
| 268 | // A new or removed folder is named, not what's in it. |
| 269 | assert_eq!(sorted(&got[0]), vec!["README.md", "src"]); |
| 270 | assert_eq!(sorted(&got[1]), vec!["docs", "src/a.txt"]); |
| 271 | assert_eq!(sorted(&got[2]), vec!["README.md", "src/deep"]); |
| 272 | assert!(sorted(&got[3]).is_empty()); |
| 273 | // Past the most asked for, it's not listed. |
| 274 | let Touched::All(few) = touched(&src, &[(Some(v1), v2)], 1).unwrap() else { panic!() }; |
| 275 | assert!(few[0].is_none()); |
| 276 |
| 277 | let list = |p: &[&str]| p.iter().map(|s| s.to_string()).collect::<Vec<_>>(); |
| 278 | assert!(may_touch(&list(&["src"]), "src/deep/b.txt")); |
| 279 | assert!(may_touch(&list(&["src/a.txt"]), "src")); |
| 280 | assert!(may_touch(&list(&["src/a.txt"]), "")); |
| 281 | assert!(!may_touch(&list(&["src/a.txt"]), "src/a")); |
| 282 | assert!(!may_touch(&list(&["srcs/a.txt", "sr"]), "src")); |
| 283 |
| 284 | let empty = MemSource::default(); |
| 285 | let Touched::Need(need) = touched(&empty, &[(Some(v1), v2)], 100).unwrap() else { panic!("needs the roots") }; |
| 286 | assert_eq!(need.len(), 2); |
| 287 | } |
| 288 |
| 289 | #[test] |
| 290 | fn blame_follows_lines_back() { |
| 291 | let v1 = "one\ntwo\nthree\n"; |
| 292 | let v2 = "one\nTWO\nthree\n"; |
| 293 | let v3 = "zero\none\nTWO\nthree\nfour\n"; |
| 294 | let owners = blame(&[(30, v3.as_bytes()), (20, v2.as_bytes()), (10, v1.as_bytes())]); |
| 295 | assert_eq!(owners, vec![30, 10, 20, 10, 30]); |
| 296 | assert_eq!(blame(&[(5, b"a\nb\n")]), vec![5, 5]); |
| 297 | assert!(blame(&[]).is_empty()); |
| 298 | } |
| 299 | } |
| 300 |