diff options
| -rw-r--r-- | Cargo.lock | 44 | ||||
| -rw-r--r-- | atuin-common/Cargo.toml | 1 | ||||
| -rw-r--r-- | atuin-common/src/record.rs | 214 |
3 files changed, 259 insertions, 0 deletions
@@ -176,6 +176,7 @@ name = "atuin-common" version = "15.0.0" dependencies = [ "chrono", + "pretty_assertions", "rand", "serde", "typed-builder", @@ -601,6 +602,22 @@ dependencies = [ ] [[package]] +name = "ctor" +version = "0.1.26" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6d2301688392eb071b0bf1a37be05c469d3cc4dbbd95df672fe28ab021e6a096" +dependencies = [ + "quote", + "syn 1.0.99", +] + +[[package]] +name = "diff" +version = "0.1.13" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "56254986775e3233ffa9c4d7d3faaf6d36a2c09d30b20687e9f88bc8bafc16c8" + +[[package]] name = "digest" version = "0.10.5" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -1435,6 +1452,15 @@ source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "ff011a302c396a5197692431fc1948019154afc178baf7d8e37367442a4601cf" [[package]] +name = "output_vt100" +version = "0.1.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "628223faebab4e3e40667ee0b2336d34a5b960ff60ea743ddfdbcf7770bcfb66" +dependencies = [ + "winapi", +] + +[[package]] name = "overload" version = "0.1.1" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -1599,6 +1625,18 @@ source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "eb9f9e6e233e5c4a35559a617bf40a4ec447db2e84c20b55a6f83167b7e57872" [[package]] +name = "pretty_assertions" +version = "1.3.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a25e9bcb20aa780fd0bb16b72403a9064d6b3f22f026946029acb941a50af755" +dependencies = [ + "ctor", + "diff", + "output_vt100", + "yansi", +] + +[[package]] name = "proc-macro2" version = "1.0.56" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -2977,6 +3015,12 @@ dependencies = [ ] [[package]] +name = "yansi" +version = "0.5.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "09041cd90cf85f7f8b2df60c646f853b7f535ce68f85244eb6731cf89fa498ec" + +[[package]] name = "zeroize" version = "1.6.0" source = "registry+https://github.com/rust-lang/crates.io-index" diff --git a/atuin-common/Cargo.toml b/atuin-common/Cargo.toml index 918b5b5f..b693a464 100644 --- a/atuin-common/Cargo.toml +++ b/atuin-common/Cargo.toml @@ -17,3 +17,4 @@ serde = { workspace = true } uuid = { workspace = true } rand = { workspace = true } typed-builder = { workspace = true } +pretty_assertions = "1.3.0" diff --git a/atuin-common/src/record.rs b/atuin-common/src/record.rs index 1fb60e55..a9c177c0 100644 --- a/atuin-common/src/record.rs +++ b/atuin-common/src/record.rs @@ -1,3 +1,5 @@ +use std::collections::HashMap; + use serde::{Deserialize, Serialize}; use typed_builder::TypedBuilder; @@ -47,3 +49,215 @@ impl Record { .build() } } + +/// An index representing the current state of the record stores +/// This can be both remote, or local, and compared in either direction +pub struct RecordIndex { + // A map of host -> tag -> tail + pub hosts: HashMap<String, HashMap<String, String>>, +} + +impl Default for RecordIndex { + fn default() -> Self { + Self::new() + } +} + +impl RecordIndex { + pub fn new() -> RecordIndex { + RecordIndex { + hosts: HashMap::new(), + } + } + + /// Insert a new tail record into the store + pub fn set(&mut self, tail: Record) { + self.hosts + .entry(tail.host) + .or_default() + .insert(tail.tag, tail.id); + } + + pub fn get(&self, host: String, tag: String) -> Option<String> { + self.hosts.get(&host).and_then(|v| v.get(&tag)).cloned() + } + + /// Diff this index with another, likely remote index. + /// The two diffs can then be reconciled, and the optimal change set calculated + /// Returns a tuple, with (host, tag, Option(OTHER)) + /// OTHER is set to the value of the tail on the other machine. For example, if the + /// other machine has a different tail, it will be the differing tail. This is useful to + /// check if the other index is ahead of us, or behind. + /// If the other index does not have the (host, tag) pair, then the other value will be None. + pub fn diff(&self, other: &Self) -> Vec<(String, String, Option<String>)> { + let mut ret = Vec::new(); + + // First, we check if other has everything that self has + for (host, tag_map) in self.hosts.iter() { + for (tag, tail) in tag_map.iter() { + match other.get(host.clone(), tag.clone()) { + // The other store is all up to date! No diff. + Some(t) if t.eq(tail) => continue, + + // The other store does exist, but it is either ahead or behind us. A diff regardless + Some(t) => ret.push((host.clone(), tag.clone(), Some(t))), + + // The other store does not exist :O + None => ret.push((host.clone(), tag.clone(), None)), + }; + } + } + + // At this point, there is a single case we have not yet considered. + // If the other store knows of a tag that we are not yet aware of, then the diff will be missed + + // account for that! + for (host, tag_map) in other.hosts.iter() { + for (tag, tail) in tag_map.iter() { + match self.get(host.clone(), tag.clone()) { + // If we have this host/tag combo, the comparison and diff will have already happened above + Some(_) => continue, + + None => ret.push((host.clone(), tag.clone(), Some(tail.clone()))), + }; + } + } + + ret.sort(); + ret + } +} + +#[cfg(test)] +mod tests { + use super::{Record, RecordIndex}; + use pretty_assertions::{assert_eq, assert_ne}; + + fn test_record() -> Record { + Record::builder() + .host(crate::utils::uuid_v7().simple().to_string()) + .version("v1".into()) + .tag(crate::utils::uuid_v7().simple().to_string()) + .data(vec![0, 1, 2, 3]) + .build() + } + + #[test] + fn record_index() { + let mut index = RecordIndex::new(); + let record = test_record(); + + index.set(record.clone()); + + let tail = index.get(record.host, record.tag); + + assert_eq!( + record.id, + tail.expect("tail not in store"), + "tail in store did not match" + ); + } + + #[test] + fn record_index_overwrite() { + let mut index = RecordIndex::new(); + let record = test_record(); + let child = record.new_child(vec![1, 2, 3]); + + index.set(record.clone()); + index.set(child.clone()); + + let tail = index.get(record.host, record.tag); + + assert_eq!( + child.id, + tail.expect("tail not in store"), + "tail in store did not match" + ); + } + + #[test] + fn record_index_no_diff() { + // Here, they both have the same version and should have no diff + + let mut index1 = RecordIndex::new(); + let mut index2 = RecordIndex::new(); + + let record1 = test_record(); + + index1.set(record1.clone()); + index2.set(record1); + + let diff = index1.diff(&index2); + + assert_eq!(0, diff.len(), "expected empty diff"); + } + + #[test] + fn record_index_single_diff() { + // Here, they both have the same stores, but one is ahead by a single record + + let mut index1 = RecordIndex::new(); + let mut index2 = RecordIndex::new(); + + let record1 = test_record(); + let record2 = record1.new_child(vec![1, 2, 3]); + + index1.set(record1); + index2.set(record2.clone()); + + let diff = index1.diff(&index2); + + assert_eq!(1, diff.len(), "expected single diff"); + assert_eq!(diff[0], (record2.host, record2.tag, Some(record2.id))); + } + + #[test] + fn record_index_multi_diff() { + // A much more complex case, with a bunch more checks + let mut index1 = RecordIndex::new(); + let mut index2 = RecordIndex::new(); + + let store1record1 = test_record(); + let store1record2 = store1record1.new_child(vec![1, 2, 3]); + + let store2record1 = test_record(); + let store2record2 = store2record1.new_child(vec![1, 2, 3]); + + let store3record1 = test_record(); + + let store4record1 = test_record(); + + // index1 only knows about the first two entries of the first two stores + index1.set(store1record1); + index1.set(store2record1); + + // index2 is fully up to date with the first two stores, and knows of a third + index2.set(store1record2); + index2.set(store2record2); + index2.set(store3record1); + + // index1 knows of a 4th store + index1.set(store4record1); + + let diff1 = index1.diff(&index2); + let diff2 = index2.diff(&index1); + + // both diffs the same length + assert_eq!(4, diff1.len()); + assert_eq!(4, diff2.len()); + + // both diffs should be ALMOST the same. They will agree on which hosts and tags + // require updating, but the "other" value will not be the same. + let smol_diff_1: Vec<(String, String)> = + diff1.iter().map(|v| (v.0.clone(), v.1.clone())).collect(); + let smol_diff_2: Vec<(String, String)> = + diff1.iter().map(|v| (v.0.clone(), v.1.clone())).collect(); + + assert_eq!(smol_diff_1, smol_diff_2); + + // diffing with yourself = no diff + assert_eq!(index1.diff(&index1).len(), 0); + assert_eq!(index2.diff(&index2).len(), 0); + } +} |