note_units.rs (23731B)
1 use std::collections::{HashMap, HashSet}; 2 3 use nostrdb::NoteKey; 4 use notedeck::NoteRef; 5 6 use crate::timeline::{ 7 unit::{CompositeUnit, NoteUnit, NoteUnitFragment}, 8 MergeKind, 9 }; 10 11 type StorageIndex = usize; 12 13 /// Provides efficient access to `NoteUnit`s 14 /// Useful for threads and timelines 15 /// when reversed=false, sorts from newest to oldest 16 #[derive(Debug, Default)] 17 pub struct NoteUnits { 18 reversed: bool, 19 storage: Vec<NoteUnit>, 20 lookup: HashMap<UnitKey, StorageIndex>, // the key to index in `NoteUnits::storage` 21 order: Vec<StorageIndex>, // the sorted order of the `NoteUnit`s in `NoteUnits::storage` 22 } 23 24 impl NoteUnits { 25 pub fn values(&self) -> Values<'_> { 26 Values { 27 set: self, 28 front: 0, 29 back: self.order.len(), 30 } 31 } 32 33 pub fn contains_key(&self, k: &UnitKey) -> bool { 34 self.lookup.contains_key(k) 35 } 36 37 pub fn new_with_cap(cap: usize, reversed: bool) -> Self { 38 Self { 39 reversed, 40 storage: Vec::with_capacity(cap), 41 lookup: HashMap::with_capacity(cap), 42 order: Vec::with_capacity(cap), 43 } 44 } 45 46 pub fn len(&self) -> usize { 47 self.storage.len() 48 } 49 50 pub fn is_empty(&self) -> bool { 51 self.storage.is_empty() 52 } 53 54 /// Get the kth index from 0..Self::len 55 pub fn kth(&self, k: usize) -> Option<&NoteUnit> { 56 if k >= self.order.len() { 57 return None; 58 } 59 let idx = if self.reversed { 60 self.order[self.order.len() - 1 - k] 61 } else { 62 self.order[k] 63 }; 64 Some(&self.storage[idx]) 65 } 66 67 /// Core bulk insert for already-built `NoteUnit`s 68 /// Merges new `NoteUnit`s into `Self::storage` 69 /// Updates `Self::order` 70 fn merge_many_internal( 71 &mut self, 72 mut units: Vec<NoteUnit>, 73 touched_indices: &[usize], 74 ) -> InsertManyResponse { 75 units.retain(|e| !self.lookup.contains_key(&e.key())); 76 if units.is_empty() && touched_indices.is_empty() { 77 return InsertManyResponse::Zero; 78 } 79 80 let mut touched = Vec::new(); 81 if !touched_indices.is_empty() { 82 touched = touched_indices.to_vec(); 83 touched.sort_unstable(); // sort for later reinsertion 84 touched.dedup(); 85 self.order.retain(|i| touched.binary_search(i).is_err()); // temporarily remove touched from Self::order 86 } 87 88 units.sort_unstable(); 89 units.dedup_by_key(|u| u.key()); 90 91 let base = self.storage.len(); 92 let mut new_order = Vec::with_capacity(units.len()); 93 self.storage.reserve(units.len()); 94 for (i, unit) in units.into_iter().enumerate() { 95 let idx = base + i; 96 let key = unit.key(); 97 self.storage.push(unit); 98 self.lookup.insert(key, idx); 99 new_order.push(idx); 100 } 101 102 let inserted_new = new_order.len(); 103 104 let front_insertion = if self.order.is_empty() || new_order.is_empty() { 105 !new_order.is_empty() 106 } else if self.reversed { 107 // reversed is true, sorting should occur less recent to most recent (oldest to newest, opposite of `self.order`) 108 let first_new = *new_order.first().unwrap(); // most recent unit of the new order 109 let last_old = *self.order.last().unwrap(); // least recent unit of the current order 110 111 // if the most recent unit of the new order is less recent than the least recent unit of the current order, 112 // all current order units are less recent than the new order units. 113 // In other words, they are all being inserted in the front 114 self.storage[first_new] >= self.storage[last_old] 115 } else { 116 // reversed is false, sorting should occur most recent to least recent (newest to oldest, as it is in `self.order`) 117 let last_new = *new_order.last().unwrap(); // least recent unit of the new order 118 let first_old = *self.order.first().unwrap(); // most recent unit of the current order 119 120 // if the least recent unit of the new order is more recent than the most recent unit of the current order, 121 // all new units are more recent than the current units. 122 // In other words, they are all being inserted in the front 123 self.storage[last_new] <= self.storage[first_old] 124 }; 125 126 let mut merged = Vec::with_capacity(self.order.len() + new_order.len()); 127 let (mut i, mut j) = (0, 0); 128 while i < self.order.len() && j < new_order.len() { 129 let index_left = self.order[i]; 130 let index_right = new_order[j]; 131 let left_unit = &self.storage[index_left]; 132 let right_unit = &self.storage[index_right]; 133 if left_unit <= right_unit { 134 // the left unit is more recent than (or the same recency as) the right unit 135 merged.push(index_left); 136 i += 1; 137 } else { 138 merged.push(index_right); 139 j += 1; 140 } 141 } 142 merged.extend_from_slice(&self.order[i..]); 143 merged.extend_from_slice(&new_order[j..]); 144 145 // reinsert touched 146 for touched_index in touched { 147 let pos = merged 148 .binary_search_by(|&i2| self.storage[i2].cmp(&self.storage[touched_index])) 149 .unwrap_or_else(|p| p); 150 merged.insert(pos, touched_index); 151 } 152 153 self.order = merged; 154 155 if inserted_new == 0 { 156 InsertManyResponse::Zero 157 } else if front_insertion { 158 InsertManyResponse::Some { 159 entries_merged: inserted_new, 160 merge_kind: MergeKind::FrontInsert, 161 } 162 } else { 163 InsertManyResponse::Some { 164 entries_merged: inserted_new, 165 merge_kind: MergeKind::Spliced, 166 } 167 } 168 } 169 170 /// Merges `NoteUnitFragment`s 171 /// `NoteUnitFragment::Single` is added normally 172 /// if `NoteUnitFragment::Composite` exists already, it will fold the fragment into the `CompositeUnit` 173 /// otherwise, it will generate the `NoteUnit::CompositeUnit` from the `NoteUnitFragment::Composite` 174 pub fn merge_fragments(&mut self, frags: Vec<NoteUnitFragment>) -> InsertManyResponse { 175 let mut to_build: HashMap<CompositeKey, CompositeUnit> = HashMap::new(); // new composites by key 176 let mut singles_to_build: Vec<NoteRef> = Vec::new(); 177 let mut singles_seen: HashSet<NoteKey> = HashSet::new(); 178 179 let mut touched = Vec::new(); 180 for frag in frags { 181 match frag { 182 NoteUnitFragment::Single(note_ref) => { 183 let key = note_ref.key; 184 if self.lookup.contains_key(&UnitKey::Single(key)) { 185 continue; 186 } 187 if singles_seen.insert(key) { 188 singles_to_build.push(note_ref); 189 } 190 } 191 NoteUnitFragment::Composite(c_frag) => { 192 let key = c_frag.get_underlying_noteref().key; 193 let composite_type = c_frag.get_type(); 194 195 if let Some(&storage_idx) = self.lookup.get(&UnitKey::Composite(c_frag.key())) { 196 if let Some(NoteUnit::Composite(c_unit)) = self.storage.get_mut(storage_idx) 197 { 198 if c_frag.get_latest_ref() < c_unit.get_latest_ref() { 199 touched.push(storage_idx); 200 } 201 c_frag.fold_into(c_unit); 202 continue; 203 } 204 } 205 // aggregate for new composite 206 use std::collections::hash_map::Entry; 207 match to_build.entry(CompositeKey { 208 key, 209 composite_type, 210 }) { 211 Entry::Occupied(mut o) => { 212 c_frag.fold_into(o.get_mut()); 213 } 214 Entry::Vacant(v) => { 215 v.insert(c_frag.into()); 216 } 217 } 218 } 219 } 220 } 221 222 let mut items: Vec<NoteUnit> = Vec::with_capacity(singles_to_build.len() + to_build.len()); 223 items.extend(singles_to_build.into_iter().map(NoteUnit::Single)); 224 items.extend(to_build.into_values().map(NoteUnit::Composite)); 225 226 self.merge_many_internal(items, &touched) 227 } 228 229 /// Convienience method to merge a single note 230 pub fn merge_single_unit(&mut self, note_ref: NoteRef) -> InsertionResponse { 231 match self.merge_many_internal(vec![NoteUnit::Single(note_ref)], &[]) { 232 InsertManyResponse::Zero => InsertionResponse::AlreadyExists, 233 InsertManyResponse::Some { 234 entries_merged: _, 235 merge_kind, 236 } => InsertionResponse::Merged(merge_kind), 237 } 238 } 239 240 pub fn latest_ref(&self) -> Option<&NoteRef> { 241 if self.reversed { 242 self.order.last().map(|&i| &self.storage[i]) 243 } else { 244 self.order.first().map(|&i| &self.storage[i]) 245 } 246 .map(NoteUnit::get_latest_ref) 247 } 248 } 249 250 #[derive(Hash, PartialEq, Eq, Debug)] 251 pub struct CompositeKey { 252 pub key: NoteKey, 253 pub composite_type: CompositeType, 254 } 255 256 #[derive(Hash, PartialEq, Eq, Debug)] 257 pub enum CompositeType { 258 Reaction, 259 Repost, 260 } 261 262 #[derive(Hash, PartialEq, Eq, Debug)] 263 pub enum UnitKey { 264 Single(NoteKey), 265 Composite(CompositeKey), 266 } 267 268 pub enum InsertManyResponse { 269 Zero, 270 Some { 271 entries_merged: usize, 272 merge_kind: MergeKind, 273 }, 274 } 275 276 pub struct Values<'a> { 277 set: &'a NoteUnits, 278 front: usize, 279 back: usize, 280 } 281 282 impl<'a> Iterator for Values<'a> { 283 type Item = &'a NoteUnit; 284 fn next(&mut self) -> Option<Self::Item> { 285 if self.front >= self.back { 286 return None; 287 } 288 let idx = if !self.set.reversed { 289 let i = self.front; 290 self.front += 1; 291 self.set.order[i] 292 } else { 293 self.back -= 1; 294 self.set.order[self.back] 295 }; 296 Some(&self.set.storage[idx]) 297 } 298 } 299 300 impl<'a> DoubleEndedIterator for Values<'a> { 301 fn next_back(&mut self) -> Option<Self::Item> { 302 if self.front >= self.back { 303 return None; 304 } 305 let idx = if !self.set.reversed { 306 self.back -= 1; 307 self.set.order[self.back] 308 } else { 309 let i = self.front; 310 self.front += 1; 311 self.set.order[i] 312 }; 313 Some(&self.set.storage[idx]) 314 } 315 } 316 317 pub enum InsertionResponse { 318 AlreadyExists, 319 Merged(MergeKind), 320 } 321 322 #[cfg(test)] 323 mod tests { 324 use std::collections::{BTreeMap, HashSet}; 325 326 use egui::ahash::HashMap; 327 use enostr::Pubkey; 328 use nostrdb::NoteKey; 329 use notedeck::NoteRef; 330 use pretty_assertions::assert_eq; 331 332 use uuid::Uuid; 333 334 use crate::timeline::{ 335 unit::{ 336 CompositeFragment, CompositeUnit, NoteUnit, NoteUnitFragment, Reaction, 337 ReactionFragment, ReactionUnit, RepostFragment, 338 }, 339 NoteUnits, RepostUnit, 340 }; 341 342 #[derive(Default)] 343 struct UnitBuilder { 344 counter: u64, 345 frags: HashMap<String, NoteUnitFragment>, 346 units: NoteUnits, 347 } 348 349 impl UnitBuilder { 350 fn counter(&mut self) -> u64 { 351 let res = self.counter; 352 self.counter += 1; 353 res 354 } 355 356 fn random_sender(&mut self) -> Pubkey { 357 let mut out = [0u8; 32]; 358 out[..8].copy_from_slice(&self.counter().to_le_bytes()); 359 360 Pubkey::new(out) 361 } 362 363 fn build_reac_frag(&mut self, reacted_to: NoteRef) -> NoteUnitFragment { 364 NoteUnitFragment::Composite(CompositeFragment::Reaction(ReactionFragment { 365 noteref_reacted_to: reacted_to, 366 reaction_note_ref: NoteRef { 367 key: NoteKey::new(self.counter()), 368 created_at: self.counter(), 369 }, 370 reaction: Reaction { 371 reaction: "+".to_owned(), 372 sender: self.random_sender(), 373 sender_profilekey: None, 374 }, 375 })) 376 } 377 378 fn build_repost_frag(&mut self, reposting: NoteRef) -> NoteUnitFragment { 379 NoteUnitFragment::Composite(CompositeFragment::Repost(RepostFragment { 380 reposted_noteref: reposting, 381 repost_noteref: self.new_noteref(), 382 reposter: self.random_sender(), 383 })) 384 } 385 386 fn insert_repost(&mut self, reposting: NoteRef) -> String { 387 let repost = self.build_repost_frag(reposting); 388 389 let id = Uuid::new_v4().to_string(); 390 self.frags.insert(id.clone(), repost.clone()); 391 392 self.units.merge_fragments(vec![repost]); 393 394 id 395 } 396 397 fn insert_reac_frag(&mut self, reacted_to: NoteRef) -> String { 398 let frag = self.build_reac_frag(reacted_to); 399 let id = Uuid::new_v4().to_string(); 400 self.frags.insert(id.clone(), frag.clone()); 401 402 self.units.merge_fragments(vec![frag]); 403 404 id 405 } 406 407 fn insert_reac_frag_pair(&mut self, reacted_to: NoteRef) -> (String, String) { 408 let frag1 = self.build_reac_frag(reacted_to); 409 let frag2 = self.build_reac_frag(reacted_to); 410 411 self.units 412 .merge_fragments(vec![frag1.clone(), frag2.clone()]); 413 414 let id1 = Uuid::new_v4().to_string(); 415 self.frags.insert(id1.clone(), frag1); 416 let id2 = Uuid::new_v4().to_string(); 417 self.frags.insert(id2.clone(), frag2); 418 419 (id1, id2) 420 } 421 422 fn new_noteref(&mut self) -> NoteRef { 423 NoteRef { 424 key: NoteKey::new(self.counter()), 425 created_at: self.counter(), 426 } 427 } 428 429 fn insert_note(&mut self) -> String { 430 let note_ref = NoteRef { 431 key: NoteKey::new(self.counter()), 432 created_at: self.counter(), 433 }; 434 435 let id = Uuid::new_v4().to_string(); 436 self.frags 437 .insert(id.clone(), NoteUnitFragment::Single(note_ref.clone())); 438 439 self.units.merge_single_unit(note_ref); 440 441 id 442 } 443 444 fn expected_reactions(&mut self, ids: Vec<&String>) -> NoteUnit { 445 let mut reactions = BTreeMap::new(); 446 let mut reaction_id = None; 447 let mut senders = HashSet::new(); 448 for id in ids { 449 let NoteUnitFragment::Composite(CompositeFragment::Reaction(reac)) = 450 self.frags.get(id).unwrap() 451 else { 452 panic!("got something other than reaction"); 453 }; 454 455 if let Some(prev_reac_id) = reaction_id { 456 if prev_reac_id != reac.noteref_reacted_to { 457 panic!("internal error"); 458 } 459 } 460 461 reaction_id = Some(reac.noteref_reacted_to); 462 463 reactions.insert(reac.reaction_note_ref, reac.reaction.clone()); 464 senders.insert(reac.reaction.sender); 465 } 466 467 NoteUnit::Composite(CompositeUnit::Reaction(ReactionUnit { 468 note_reacted_to: reaction_id.unwrap(), 469 reactions, 470 senders: senders, 471 })) 472 } 473 474 fn expected_reposts(&mut self, ids: Vec<&String>) -> NoteUnit { 475 let mut reposts = BTreeMap::new(); 476 let mut reposted_id = None; 477 let mut senders = HashSet::new(); 478 for id in ids { 479 let NoteUnitFragment::Composite(CompositeFragment::Repost(repost)) = 480 self.frags.get(id).unwrap() 481 else { 482 panic!("got something other than repost"); 483 }; 484 485 if let Some(prev_reposted_id) = reposted_id { 486 if prev_reposted_id != repost.reposted_noteref { 487 panic!("internal error"); 488 } 489 } 490 491 reposted_id = Some(repost.reposted_noteref); 492 493 reposts.insert(repost.repost_noteref, repost.reposter); 494 senders.insert(repost.reposter); 495 } 496 497 NoteUnit::Composite(CompositeUnit::Repost(RepostUnit { 498 note_reposted: reposted_id.unwrap(), 499 reposts, 500 senders, 501 })) 502 } 503 504 fn expected_single(&mut self, id: &String) -> NoteUnit { 505 let Some(NoteUnitFragment::Single(note_ref)) = self.frags.get(id) else { 506 panic!("fail"); 507 }; 508 509 NoteUnit::Single(*note_ref) 510 } 511 512 fn asserted_at(&self, index: usize) -> NoteUnit { 513 self.units.kth(index).unwrap().clone() 514 } 515 516 fn aeq(&mut self, units_kth: usize, expect: Expect) { 517 assert_eq!( 518 self.asserted_at(units_kth), 519 match expect { 520 Expect::Single(id) => self.expected_single(id), 521 Expect::Reaction(items) => self.expected_reactions(items), 522 Expect::Repost(items) => self.expected_reposts(items), 523 } 524 ); 525 } 526 } 527 528 enum Expect<'a> { 529 Single(&'a String), 530 Reaction(Vec<&'a String>), 531 Repost(Vec<&'a String>), 532 } 533 534 #[test] 535 fn test_reactions1() { 536 let mut builder = UnitBuilder::default(); 537 let reaction_note = builder.new_noteref(); 538 539 let single0 = builder.insert_note(); 540 builder.aeq(0, Expect::Single(&single0)); 541 542 let reac1 = builder.insert_reac_frag(reaction_note); 543 builder.aeq(0, Expect::Reaction(vec![&reac1])); 544 builder.aeq(1, Expect::Single(&single0)); 545 546 let single1 = builder.insert_note(); 547 builder.aeq(0, Expect::Single(&single1)); 548 builder.aeq(1, Expect::Reaction(vec![&reac1])); 549 builder.aeq(2, Expect::Single(&single0)); 550 551 let reac2 = builder.insert_reac_frag(reaction_note); 552 builder.aeq(0, Expect::Reaction(vec![&reac2, &reac1])); 553 builder.aeq(1, Expect::Single(&single1)); 554 builder.aeq(2, Expect::Single(&single0)); 555 556 let single2 = builder.insert_note(); 557 builder.aeq(0, Expect::Single(&single2)); 558 builder.aeq(1, Expect::Reaction(vec![&reac2, &reac1])); 559 builder.aeq(2, Expect::Single(&single1)); 560 builder.aeq(3, Expect::Single(&single0)); 561 562 let reac3 = builder.insert_reac_frag(reaction_note); 563 builder.aeq(0, Expect::Reaction(vec![&reac1, &reac2, &reac3])); 564 builder.aeq(1, Expect::Single(&single2)); 565 builder.aeq(2, Expect::Single(&single1)); 566 builder.aeq(3, Expect::Single(&single0)); 567 } 568 569 #[test] 570 fn test_reactions2() { 571 let mut builder = UnitBuilder::default(); 572 let reaction_note1 = builder.new_noteref(); 573 let reaction_note2 = builder.new_noteref(); 574 575 let single0 = builder.insert_note(); 576 builder.aeq(0, Expect::Single(&single0)); 577 578 let reac1_1 = builder.insert_reac_frag(reaction_note1); 579 builder.aeq(0, Expect::Reaction(vec![&reac1_1])); 580 builder.aeq(1, Expect::Single(&single0)); 581 582 let reac2_1 = builder.insert_reac_frag(reaction_note2); 583 builder.aeq(0, Expect::Reaction(vec![&reac2_1])); 584 builder.aeq(1, Expect::Reaction(vec![&reac1_1])); 585 builder.aeq(2, Expect::Single(&single0)); 586 587 let single1 = builder.insert_note(); 588 builder.aeq(0, Expect::Single(&single1)); 589 builder.aeq(1, Expect::Reaction(vec![&reac2_1])); 590 builder.aeq(2, Expect::Reaction(vec![&reac1_1])); 591 builder.aeq(3, Expect::Single(&single0)); 592 593 let reac1_2 = builder.insert_reac_frag(reaction_note1); 594 builder.aeq(0, Expect::Reaction(vec![&reac1_2, &reac1_1])); 595 builder.aeq(1, Expect::Single(&single1)); 596 builder.aeq(2, Expect::Reaction(vec![&reac2_1])); 597 builder.aeq(3, Expect::Single(&single0)); 598 599 let single2 = builder.insert_note(); 600 builder.aeq(0, Expect::Single(&single2)); 601 builder.aeq(1, Expect::Reaction(vec![&reac1_2, &reac1_1])); 602 builder.aeq(2, Expect::Single(&single1)); 603 builder.aeq(3, Expect::Reaction(vec![&reac2_1])); 604 builder.aeq(4, Expect::Single(&single0)); 605 606 let reac1_3 = builder.insert_reac_frag(reaction_note1); 607 builder.aeq(0, Expect::Reaction(vec![&reac1_2, &reac1_1, &reac1_3])); 608 builder.aeq(1, Expect::Single(&single2)); 609 builder.aeq(2, Expect::Single(&single1)); 610 builder.aeq(3, Expect::Reaction(vec![&reac2_1])); 611 builder.aeq(4, Expect::Single(&single0)); 612 613 let reac2_2 = builder.insert_reac_frag(reaction_note2); 614 builder.aeq(0, Expect::Reaction(vec![&reac2_1, &reac2_2])); 615 builder.aeq(1, Expect::Reaction(vec![&reac1_2, &reac1_1, &reac1_3])); 616 builder.aeq(2, Expect::Single(&single2)); 617 builder.aeq(3, Expect::Single(&single1)); 618 builder.aeq(4, Expect::Single(&single0)); 619 } 620 621 #[test] 622 fn test_reactions3() { 623 let mut builder = UnitBuilder::default(); 624 let reaction_note1 = builder.new_noteref(); 625 626 let single1 = builder.insert_note(); 627 builder.aeq(0, Expect::Single(&single1)); 628 629 let reac0 = builder.insert_reac_frag(reaction_note1); 630 builder.aeq(0, Expect::Reaction(vec![&reac0])); 631 builder.aeq(1, Expect::Single(&single1)); 632 633 let (reac1, reac2) = builder.insert_reac_frag_pair(reaction_note1); 634 builder.aeq(0, Expect::Reaction(vec![&reac0, &reac1, &reac2])); 635 builder.aeq(1, Expect::Single(&single1)); 636 637 let single2 = builder.insert_note(); 638 builder.aeq(0, Expect::Single(&single2)); 639 builder.aeq(1, Expect::Reaction(vec![&reac0, &reac1, &reac2])); 640 builder.aeq(2, Expect::Single(&single1)); 641 } 642 643 #[test] 644 fn test_repost() { 645 let mut builder = UnitBuilder::default(); 646 let repost_note = builder.new_noteref(); 647 648 let single1 = builder.insert_note(); 649 builder.aeq(0, Expect::Single(&single1)); 650 651 let repost1 = builder.insert_repost(repost_note); 652 builder.aeq(0, Expect::Repost(vec![&repost1])); 653 builder.aeq(1, Expect::Single(&single1)); 654 655 let single2 = builder.insert_note(); 656 builder.aeq(0, Expect::Single(&single2)); 657 builder.aeq(1, Expect::Repost(vec![&repost1])); 658 builder.aeq(2, Expect::Single(&single1)); 659 660 let reac1 = builder.insert_reac_frag(repost_note); 661 builder.aeq(0, Expect::Reaction(vec![&reac1])); 662 builder.aeq(1, Expect::Single(&single2)); 663 builder.aeq(2, Expect::Repost(vec![&repost1])); 664 builder.aeq(3, Expect::Single(&single1)); 665 666 let repost2 = builder.insert_repost(repost_note); 667 builder.aeq(0, Expect::Repost(vec![&repost1, &repost2])); 668 builder.aeq(1, Expect::Reaction(vec![&reac1])); 669 builder.aeq(2, Expect::Single(&single2)); 670 builder.aeq(3, Expect::Single(&single1)); 671 672 let reac2 = builder.insert_reac_frag(repost_note); 673 builder.aeq(0, Expect::Reaction(vec![&reac1, &reac2])); 674 builder.aeq(1, Expect::Repost(vec![&repost1, &repost2])); 675 builder.aeq(2, Expect::Single(&single2)); 676 builder.aeq(3, Expect::Single(&single1)); 677 } 678 }