oxedyne/fe2o3/fe2o3_text/tests/lineset.rs
9.4 KiB, 1 run
created by r1870400018:75889, which is this file's identity for as long as the history lasts, whatever it is later renamed to
download · who wrote it · its history
| 1 | //! `lineset::union_lines` and `lineset::missing_lines`: a file as a multiset of lines. |
| 2 | //! |
| 3 | //! Written for the Daimond page log (10 Oct 2026). On 7 Oct two devices each appended one row |
| 4 | //! to the same diet log while apart, and the merge kept one side's. The first case is that |
| 5 | //! shape, with synthetic rows. |
| 6 | |
| 7 | use oxedyne_fe2o3_text::lineset::{ |
| 8 | missing_lines, |
| 9 | union_lines, |
| 10 | Joined, |
| 11 | }; |
| 12 | |
| 13 | use std::collections::BTreeMap; |
| 14 | |
| 15 | |
| 16 | // The rows of a buffer as a multiset. |
| 17 | fn content(buf: &[u8]) -> BTreeMap<Vec<u8>, usize> { |
| 18 | let mut map = BTreeMap::new(); |
| 19 | for line in buf.split(|b| *b == b'\n') { |
| 20 | if !line.is_empty() { |
| 21 | *map.entry(line.to_vec()).or_insert(0) += 1; |
| 22 | } |
| 23 | } |
| 24 | map |
| 25 | } |
| 26 | |
| 27 | fn max_of(a: &BTreeMap<Vec<u8>, usize>, b: &BTreeMap<Vec<u8>, usize>) -> BTreeMap<Vec<u8>, usize> { |
| 28 | let mut out = a.clone(); |
| 29 | for (k, n) in b { |
| 30 | let e = out.entry(k.clone()).or_insert(0); |
| 31 | *e = (*e).max(*n); |
| 32 | } |
| 33 | out |
| 34 | } |
| 35 | |
| 36 | fn join(arriving: &str, here: &str) -> Joined { |
| 37 | union_lines(arriving.as_bytes(), here.as_bytes()) |
| 38 | } |
| 39 | |
| 40 | fn text(j: &Joined) -> String { |
| 41 | String::from_utf8_lossy(&j.bytes).into_owned() |
| 42 | } |
| 43 | |
| 44 | struct XorShift(u64); |
| 45 | |
| 46 | impl XorShift { |
| 47 | fn next(&mut self) -> u64 { |
| 48 | let mut x = self.0; |
| 49 | x ^= x << 13; |
| 50 | x ^= x >> 7; |
| 51 | x ^= x << 17; |
| 52 | self.0 = x; |
| 53 | x |
| 54 | } |
| 55 | fn below(&mut self, n: u64) -> u64 { |
| 56 | self.next() % n |
| 57 | } |
| 58 | } |
| 59 | |
| 60 | // A small vocabulary, so rows collide and repeat often. |
| 61 | const WORDS: [&[u8]; 7] = [b"a", b"b", b"c", b"a\r", b"a ", b"\xff\xfe", b"{\"id\":\"q\"}"]; |
| 62 | |
| 63 | fn random_file(rng: &mut XorShift) -> Vec<u8> { |
| 64 | let mut out = Vec::new(); |
| 65 | let n = rng.below(7); |
| 66 | for _ in 0..n { |
| 67 | match rng.below(9) { |
| 68 | 0 => out.push(b'\n'), // A blank line |
| 69 | _ => { |
| 70 | out.extend_from_slice(WORDS[rng.below(WORDS.len() as u64) as usize]); |
| 71 | out.push(b'\n'); |
| 72 | } |
| 73 | } |
| 74 | } |
| 75 | if !out.is_empty() && rng.below(4) == 0 { |
| 76 | out.pop(); // No final newline, or a torn last row |
| 77 | } |
| 78 | out |
| 79 | } |
| 80 | |
| 81 | #[test] |
| 82 | fn seven_oct_both_kept() { |
| 83 | let shared = concat!( |
| 84 | "{\"id\":\"t0brekfst001\",\"at\":\"2026-10-07T07:40:12+08:00\",\"day\":\"2026-10-07\",\"src\":\"scale\",\"f\":{\"food\":\"toast\",\"qty\":1},\"w\":1000000000001}\n", |
| 85 | "{\"id\":\"t0coffee0002\",\"at\":\"2026-10-07T08:02:47+08:00\",\"day\":\"2026-10-07\",\"src\":\"chat\",\"f\":{\"food\":\"coffee\",\"qty\":1},\"w\":1000000000002}\n", |
| 86 | ); |
| 87 | let oats = "{\"id\":\"t0oats000003\",\"at\":\"2026-10-07T11:06:05+08:00\",\"day\":\"2026-10-07\",\"src\":\"scale\",\"f\":{\"food\":\"oats\",\"qty\":1},\"w\":1000000000003}\n"; |
| 88 | let eggs = "{\"id\":\"t0eggs000004\",\"at\":\"2026-10-07T11:15:55+08:00\",\"day\":\"2026-10-07\",\"src\":\"scale\",\"f\":{\"food\":\"egg\",\"qty\":2},\"w\":1000000000004}\n"; |
| 89 | let arriving = format!("{}{}", shared, oats); |
| 90 | let here = format!("{}{}", shared, eggs); |
| 91 | let j = join(&arriving, &here); |
| 92 | assert_eq!(text(&j), format!("{}{}{}", shared, oats, eggs)); |
| 93 | assert_eq!((j.here_adds, j.arriving_adds), (1, 1)); |
| 94 | // From the other side, both rows are still kept. |
| 95 | let k = join(&here, &arriving); |
| 96 | assert_eq!(text(&k), format!("{}{}{}", shared, eggs, oats)); |
| 97 | assert_eq!((k.here_adds, k.arriving_adds), (1, 1)); |
| 98 | } |
| 99 | |
| 100 | #[test] |
| 101 | fn duplicates_by_occurrence() { |
| 102 | let j = join("x\nx\n", "x\n"); |
| 103 | assert_eq!((text(&j).as_str(), j.here_adds, j.arriving_adds), ("x\nx\n", 0, 1)); |
| 104 | let j = join("x\n", "x\nx\n"); |
| 105 | assert_eq!((text(&j).as_str(), j.here_adds, j.arriving_adds), ("x\nx\n", 1, 0)); |
| 106 | let j = join("x\n", "x\nx\nx\n"); |
| 107 | assert_eq!((text(&j).as_str(), j.here_adds, j.arriving_adds), ("x\nx\nx\n", 2, 0)); |
| 108 | let j = join("x\nx\nx\n", "x\n"); |
| 109 | assert_eq!((text(&j).as_str(), j.here_adds, j.arriving_adds), ("x\nx\nx\n", 0, 2)); |
| 110 | let j = join("x\nx\n", "x\nx\n"); |
| 111 | assert_eq!((text(&j).as_str(), j.here_adds, j.arriving_adds), ("x\nx\n", 0, 0)); |
| 112 | } |
| 113 | |
| 114 | #[test] |
| 115 | fn settles_bytes() { |
| 116 | for (arriving, here) in [ |
| 117 | ("b\na\nc\n", "a\nc\n"), |
| 118 | ("b\na\nc", "c\na\n"), // Order and the final newline do not matter |
| 119 | ("\n\na\n\nb\n", "b\n\n"), |
| 120 | ("a\nb\n", ""), |
| 121 | ("a\r\nb \n", "b \na\r\n"), |
| 122 | ] { |
| 123 | let j = join(arriving, here); |
| 124 | assert_eq!(j.bytes, arriving.as_bytes(), "{:?} against {:?}", arriving, here); |
| 125 | assert_eq!(j.here_adds, 0); |
| 126 | } |
| 127 | } |
| 128 | |
| 129 | #[test] |
| 130 | fn content_commutative_associative() { |
| 131 | let mut rng = XorShift(0x9E37_79B9_7F4A_7C15); |
| 132 | for _ in 0..20_000 { |
| 133 | let a = random_file(&mut rng); |
| 134 | let b = random_file(&mut rng); |
| 135 | let c = random_file(&mut rng); |
| 136 | let (ca, cb, cc) = (content(&a), content(&b), content(&c)); |
| 137 | |
| 138 | let ab = union_lines(&a, &b); |
| 139 | let ba = union_lines(&b, &a); |
| 140 | let want = max_of(&ca, &cb); |
| 141 | assert_eq!(content(&ab.bytes), want, "a={:?} b={:?}", a, b); |
| 142 | assert_eq!(content(&ba.bytes), want, "a={:?} b={:?}", a, b); |
| 143 | let only_b: usize = cb.iter().map(|(k, n)| n.saturating_sub(*ca.get(k).unwrap_or(&0))).sum(); |
| 144 | let only_a: usize = ca.iter().map(|(k, n)| n.saturating_sub(*cb.get(k).unwrap_or(&0))).sum(); |
| 145 | assert_eq!((ab.here_adds, ab.arriving_adds), (only_b, only_a)); |
| 146 | |
| 147 | let left = union_lines(&ab.bytes, &c); |
| 148 | let bc = union_lines(&b, &c); |
| 149 | let right = union_lines(&a, &bc.bytes); |
| 150 | let want3 = max_of(&want, &cc); |
| 151 | assert_eq!(content(&left.bytes), want3); |
| 152 | assert_eq!(content(&right.bytes), want3); |
| 153 | } |
| 154 | } |
| 155 | |
| 156 | #[test] |
| 157 | fn idempotent_bytes() { |
| 158 | let mut rng = XorShift(0x0123_4567_89AB_CDEF); |
| 159 | for _ in 0..5_000 { |
| 160 | let a = random_file(&mut rng); |
| 161 | let h = random_file(&mut rng); |
| 162 | let aa = union_lines(&a, &a); |
| 163 | assert_eq!(aa.bytes, a); |
| 164 | assert_eq!((aa.here_adds, aa.arriving_adds), (0, 0)); |
| 165 | let once = union_lines(&a, &h); |
| 166 | let twice = union_lines(&once.bytes, &h); |
| 167 | assert_eq!(twice.bytes, once.bytes, "a={:?} h={:?}", a, h); |
| 168 | assert_eq!(twice.here_adds, 0); |
| 169 | } |
| 170 | } |
| 171 | |
| 172 | #[test] |
| 173 | fn three_device_gossip_converges() { |
| 174 | let mut rng = XorShift(0xDEAD_BEEF_CAFE_F00D); |
| 175 | for _ in 0..2_000 { |
| 176 | let mut dev = [random_file(&mut rng), random_file(&mut rng), random_file(&mut rng)]; |
| 177 | let want = max_of(&max_of(&content(&dev[0]), &content(&dev[1])), &content(&dev[2])); |
| 178 | let mut rounds = 0; |
| 179 | loop { |
| 180 | let mut changed = false; |
| 181 | for i in 0..3 { |
| 182 | for j in 0..3 { |
| 183 | if i != j { |
| 184 | let next = union_lines(&dev[j], &dev[i]).bytes; // i pulls from j |
| 185 | if next != dev[i] { |
| 186 | dev[i] = next; |
| 187 | changed = true; |
| 188 | } |
| 189 | } |
| 190 | } |
| 191 | } |
| 192 | rounds += 1; |
| 193 | if !changed { |
| 194 | break; |
| 195 | } |
| 196 | assert!(rounds < 6, "no fixpoint after {} rounds: {:?}", rounds, dev); |
| 197 | } |
| 198 | assert_eq!(dev[0], dev[1]); |
| 199 | assert_eq!(dev[1], dev[2]); |
| 200 | assert_eq!(content(&dev[0]), want); |
| 201 | } |
| 202 | } |
| 203 | |
| 204 | #[test] |
| 205 | fn r4_order() { |
| 206 | for (arriving, here, want) in [ |
| 207 | // After the nearest preceding shared row, past arriving's own rows after it. |
| 208 | ("s1\na1\ns2\n", "s1\nh1\ns2\n", "s1\na1\nh1\ns2\n"), |
| 209 | // No shared row before: after the arriving-only rows that open arriving. |
| 210 | ("a0\ns1\n", "h0\ns1\n", "a0\nh0\ns1\n"), |
| 211 | ("s1\n", "h0\ns1\n", "h0\ns1\n"), |
| 212 | // The anchor is arriving's last row. |
| 213 | ("s1\na1\n", "s1\nh1\n", "s1\na1\nh1\n"), |
| 214 | // Several here rows in one place keep here's order. |
| 215 | ("s1\ns2\n", "s1\nh1\nh2\ns2\nh3\n", "s1\nh1\nh2\ns2\nh3\n"), |
| 216 | // The anchor is found in arriving wherever it sits there. |
| 217 | ("s2\ns1\n", "s1\nh1\ns2\n", "s2\ns1\nh1\n"), |
| 218 | // The anchor is a row by occurrence: here's second x is arriving's second x. |
| 219 | ("x\na\nx\n", "x\nx\nh\n", "x\na\nx\nh\n"), |
| 220 | // Blank lines after the run stay after the spliced rows. |
| 221 | ("s1\n\ns2\n", "s1\nh\ns2\n", "s1\nh\n\ns2\n"), |
| 222 | ] { |
| 223 | let j = join(arriving, here); |
| 224 | assert_eq!(text(&j), want, "{:?} against {:?}", arriving, here); |
| 225 | } |
| 226 | } |
| 227 | |
| 228 | #[test] |
| 229 | fn byte_exact() { |
| 230 | let j = join("a\r\n", "a\n"); |
| 231 | assert_eq!((text(&j).as_str(), j.here_adds, j.arriving_adds), ("a\r\na\n", 1, 1)); |
| 232 | let j = join("a \n", "a\n"); |
| 233 | assert_eq!((text(&j).as_str(), j.here_adds, j.arriving_adds), ("a \na\n", 1, 1)); |
| 234 | let j = union_lines(b"\xff\xfe\n", b"\xff\n"); |
| 235 | assert_eq!(j.bytes, b"\xff\xfe\n\xff\n".to_vec()); |
| 236 | let j = union_lines(b"\xff\n", b"\xff\n"); |
| 237 | assert_eq!((j.bytes, j.here_adds), (b"\xff\n".to_vec(), 0)); |
| 238 | } |
| 239 | |
| 240 | #[test] |
| 241 | fn newline_edges() { |
| 242 | let j = join("", ""); |
| 243 | assert_eq!((text(&j).as_str(), j.here_adds, j.arriving_adds), ("", 0, 0)); |
| 244 | let j = join("", "x"); |
| 245 | assert_eq!((text(&j).as_str(), j.here_adds), ("x\n", 1)); |
| 246 | let j = join("x", ""); |
| 247 | assert_eq!((text(&j).as_str(), j.arriving_adds), ("x", 1)); |
| 248 | // Arriving lacks a final newline, so one is added before the spliced row. |
| 249 | let j = join("a", "b\n"); |
| 250 | assert_eq!(text(&j), "a\nb\n"); |
| 251 | // Blank lines are never rows: never spliced, and arriving's kept as they are. |
| 252 | let j = join("a\n", "\n\na\n\n"); |
| 253 | assert_eq!((text(&j).as_str(), j.here_adds), ("a\n", 0)); |
| 254 | let j = join("\n\n", "x\n"); |
| 255 | assert_eq!((text(&j).as_str(), j.here_adds, j.arriving_adds), ("x\n\n\n", 1, 0)); |
| 256 | let j = join("a\n\n\n", "a\nb\n"); |
| 257 | assert_eq!(text(&j), "a\nb\n\n\n"); |
| 258 | } |
| 259 | |
| 260 | #[test] |
| 261 | fn torn_fragment_is_a_row() { |
| 262 | // A fragment equal to a whole row is that row. |
| 263 | let j = join("a\nb", "a\nb\n"); |
| 264 | assert_eq!((text(&j).as_str(), j.here_adds), ("a\nb", 0)); |
| 265 | // A fragment unequal to any row is a row of its own, on either side. |
| 266 | let j = join("a\n", "a\nbro"); |
| 267 | assert_eq!((text(&j).as_str(), j.here_adds), ("a\nbro\n", 1)); |
| 268 | let j = join("a\nbro", "a\nbrown\n"); |
| 269 | assert_eq!((text(&j).as_str(), j.here_adds, j.arriving_adds), ("a\nbro\nbrown\n", 1, 1)); |
| 270 | } |
| 271 | |
| 272 | #[test] |
| 273 | fn missing_lines_by_occurrence() { |
| 274 | let lost = missing_lines(b"x\ny\nx\nx\n", b"x\n"); |
| 275 | assert_eq!(lost, vec![b"y".to_vec(), b"x".to_vec(), b"x".to_vec()]); |
| 276 | assert!(missing_lines(b"x\nx\n", b"x\nx\nx\n").is_empty()); |
| 277 | assert!(missing_lines(b"\n\n\n", b"").is_empty()); // Blank lines are not rows |
| 278 | assert_eq!(missing_lines(b"a\r\n", b"a\n"), vec![b"a\r".to_vec()]); |
| 279 | assert_eq!(missing_lines(b"a\nfrag", b"a\n"), vec![b"frag".to_vec()]); |
| 280 | assert!(missing_lines(b"", b"a\n").is_empty()); |
| 281 | } |