oxedyne/fe2o3/fe2o3_text/src/lineset.rs
5.2 KiB, 1 run
created by r1870400018:75887, 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 | //! Text as a multiset of lines, for joining two copies of an append-mostly file. |
| 2 | //! |
| 3 | //! Written for the Daimond page log (10 Oct 2026), where two devices each appended a line to |
| 4 | //! the same day's log while apart and the merge kept only one side's. A row is a non-empty |
| 5 | //! line compared by its bytes, so `"a\r"` and `"a"` are two rows and a blank line is none. The |
| 6 | //! k-th equal line is its own row, so a join keeps the larger count of each line and never |
| 7 | //! their sum: two devices holding the same entry once hold it once after joining, while an |
| 8 | //! entry made twice on purpose survives as two. |
| 9 | //! |
| 10 | //! The content of a join commutes and associates; its bytes do not. The bytes follow the |
| 11 | //! arriving side, with the rows only here spliced in, so a join that adds nothing returns the |
| 12 | //! arriving bytes exactly and repeated gossip settles. |
| 13 | |
| 14 | use std::collections::HashMap; |
| 15 | |
| 16 | |
| 17 | #[derive(Clone, Debug, Default, Eq, PartialEq)] |
| 18 | pub struct Joined { |
| 19 | pub bytes: Vec<u8>, |
| 20 | pub here_adds: usize, // Rows only here had |
| 21 | pub arriving_adds: usize, // Rows only arriving had |
| 22 | } |
| 23 | |
| 24 | // One non-empty line: its bytes without the LF, and the offset just past its LF. |
| 25 | #[derive(Clone, Copy, Debug)] |
| 26 | struct Row<'a> { |
| 27 | text: &'a [u8], |
| 28 | next: usize, |
| 29 | } |
| 30 | |
| 31 | fn rows(buf: &[u8]) -> Vec<Row<'_>> { |
| 32 | let mut out = Vec::new(); |
| 33 | let mut start = 0; |
| 34 | while start < buf.len() { |
| 35 | let (end, next) = match buf[start..].iter().position(|b| *b == b'\n') { |
| 36 | Some(i) => (start + i, start + i + 1), |
| 37 | None => (buf.len(), buf.len()), // A torn fragment |
| 38 | }; |
| 39 | if end > start { |
| 40 | out.push(Row { text: &buf[start..end], next }); |
| 41 | } |
| 42 | start = next; |
| 43 | } |
| 44 | out |
| 45 | } |
| 46 | |
| 47 | fn counts<'a>(rows: &[Row<'a>]) -> HashMap<&'a [u8], usize> { |
| 48 | let mut map = HashMap::new(); |
| 49 | for row in rows { |
| 50 | *map.entry(row.text).or_insert(0) += 1; |
| 51 | } |
| 52 | map |
| 53 | } |
| 54 | |
| 55 | // For each row, its occurrence number (1-based) and whether the other side holds that |
| 56 | // occurrence too. |
| 57 | fn shared<'a>( |
| 58 | rows: &[Row<'a>], |
| 59 | other: &HashMap<&'a [u8], usize>, |
| 60 | ) |
| 61 | -> Vec<(usize, bool)> |
| 62 | { |
| 63 | let mut seen: HashMap<&[u8], usize> = HashMap::new(); |
| 64 | rows.iter().map(|row| { |
| 65 | let k = seen.entry(row.text).or_insert(0); |
| 66 | *k += 1; |
| 67 | (*k, *k <= other.get(row.text).copied().unwrap_or(0)) |
| 68 | }).collect() |
| 69 | } |
| 70 | |
| 71 | /// Joins two copies of a file as multisets of lines, holding each row as many times as the |
| 72 | /// side with more of it does. |
| 73 | /// |
| 74 | /// The bytes are `arriving`'s, byte for byte when `here` has no row of its own. Otherwise each |
| 75 | /// row only `here` has is placed after its nearest preceding shared row (in `here`'s order) and |
| 76 | /// after the run of arriving-only rows that follows that row in `arriving`; a row with no |
| 77 | /// shared row before it goes after the arriving-only rows that open `arriving`. Rows sharing a |
| 78 | /// place keep `here`'s order. Each spliced row ends with LF, and an LF is added first where |
| 79 | /// `arriving` ends without one. |
| 80 | pub fn union_lines(arriving: &[u8], here: &[u8]) -> Joined { |
| 81 | let rows_a = rows(arriving); |
| 82 | let rows_h = rows(here); |
| 83 | let count_a = counts(&rows_a); |
| 84 | let count_h = counts(&rows_h); |
| 85 | let shared_a = shared(&rows_a, &count_h); |
| 86 | let shared_h = shared(&rows_h, &count_a); |
| 87 | |
| 88 | let arriving_adds = shared_a.iter().filter(|(_, s)| !s).count(); |
| 89 | let here_adds = shared_h.iter().filter(|(_, s)| !s).count(); |
| 90 | if here_adds == 0 { |
| 91 | return Joined { bytes: arriving.to_vec(), here_adds, arriving_adds }; |
| 92 | } |
| 93 | |
| 94 | // Where each shared row sits in arriving, by (line, occurrence). |
| 95 | let mut place: HashMap<(&[u8], usize), usize> = HashMap::new(); |
| 96 | for (i, row) in rows_a.iter().enumerate() { |
| 97 | if shared_a[i].1 { |
| 98 | place.insert((row.text, shared_a[i].0), i); |
| 99 | } |
| 100 | } |
| 101 | // The byte offset after the run of arriving-only rows starting at index `from`. |
| 102 | let after_run = |from: usize| -> usize { |
| 103 | let mut i = from; |
| 104 | while i < rows_a.len() && !shared_a[i].1 { |
| 105 | i += 1; |
| 106 | } |
| 107 | if i == 0 { 0 } else { rows_a[i - 1].next } |
| 108 | }; |
| 109 | |
| 110 | let mut splices: Vec<(usize, &[u8])> = Vec::with_capacity(here_adds); |
| 111 | let mut anchor: Option<usize> = None; // Index in arriving of the last shared row seen |
| 112 | for (j, row) in rows_h.iter().enumerate() { |
| 113 | let (k, is_shared) = shared_h[j]; |
| 114 | if is_shared { |
| 115 | anchor = place.get(&(row.text, k)).copied(); |
| 116 | } else { |
| 117 | let at = match anchor { |
| 118 | Some(i) => after_run(i + 1), |
| 119 | None => after_run(0), |
| 120 | }; |
| 121 | splices.push((at, row.text)); |
| 122 | } |
| 123 | } |
| 124 | splices.sort_by_key(|(at, _)| *at); // Stable, so here's order holds within a place |
| 125 | |
| 126 | let extra: usize = splices.iter().map(|(_, t)| t.len() + 1).sum(); |
| 127 | let mut bytes = Vec::with_capacity(arriving.len() + extra + 1); |
| 128 | let mut from = 0; |
| 129 | for (at, text) in splices { |
| 130 | if at > from { |
| 131 | bytes.extend_from_slice(&arriving[from..at]); |
| 132 | from = at; |
| 133 | } |
| 134 | if bytes.last().is_some_and(|b| *b != b'\n') { |
| 135 | bytes.push(b'\n'); |
| 136 | } |
| 137 | bytes.extend_from_slice(text); |
| 138 | bytes.push(b'\n'); |
| 139 | } |
| 140 | bytes.extend_from_slice(&arriving[from..]); |
| 141 | Joined { bytes, here_adds, arriving_adds } |
| 142 | } |
| 143 | |
| 144 | /// The rows of `old` that `new` does not hold, by occurrence and in `old`'s order: an `old` |
| 145 | /// with a line three times against a `new` with it once yields that line twice. |
| 146 | pub fn missing_lines(old: &[u8], new: &[u8]) -> Vec<Vec<u8>> { |
| 147 | let rows_o = rows(old); |
| 148 | let count_n = counts(&rows(new)); |
| 149 | shared(&rows_o, &count_n).into_iter() |
| 150 | .zip(rows_o.iter()) |
| 151 | .filter(|((_, is_shared), _)| !is_shared) |
| 152 | .map(|(_, row)| row.text.to_vec()) |
| 153 | .collect() |
| 154 | } |