1use std::collections::VecDeque;
2use std::str;
3use std::time::{SystemTime, UNIX_EPOCH};
4
5use indexmap::{IndexMap, IndexSet};
6use uuid::Uuid;
7
8mod rating;
9pub use rating::*;
10
11const BINARY_FORMAT_VERSION: u64 = 3;
12const BINARY_FORMAT_VERSION_V2: u64 = 2;
13const BINARY_CHUNK_SIZE: usize = 16 * 1024;
14const MAX_FUTURE_EVENT_SECONDS: u64 = 10 * 60;
15const UNKNOWN_FOLLOW_DISTANCE: u32 = 1000;
16const BINARY_NODE_ID_PUBKEY: u64 = 0;
17const BINARY_NODE_ID_UUID: u64 = 1;
18const BINARY_NODE_ID_STRING: u64 = 2;
19
20#[derive(Debug, thiserror::Error)]
21pub enum SocialGraphError {
22 #[error("cannot store empty or whitespace-only strings")]
23 EmptyString,
24 #[error("invalid id {0}")]
25 InvalidId(u32),
26 #[error("invalid binary version {0}")]
27 InvalidVersion(u64),
28 #[error("unexpected end of binary data")]
29 UnexpectedEof,
30 #[error("invalid binary node id type {0}")]
31 InvalidBinaryNodeIdType(u64),
32 #[error("invalid UTF-8 binary node id")]
33 InvalidBinaryNodeIdUtf8,
34 #[error("invalid UUID binary node id")]
35 InvalidBinaryNodeIdUuid,
36 #[error("rating range must have min_rating < max_rating (got {min_rating}..{max_rating})")]
37 InvalidRatingRange { min_rating: i64, max_rating: i64 },
38 #[error("rating {rating} is outside range {min_rating}..{max_rating}")]
39 RatingOutOfRange {
40 rating: i64,
41 min_rating: i64,
42 max_rating: i64,
43 },
44 #[error("rating window_start {window_start} is after window_end {window_end}")]
45 InvalidRatingWindow { window_start: u64, window_end: u64 },
46}
47
48pub type Result<T> = std::result::Result<T, SocialGraphError>;
49
50pub trait SocialGraphBackend {
51 type Error: std::error::Error + Send + Sync + 'static;
52
53 fn get_root(&self) -> std::result::Result<String, Self::Error>;
54
55 fn set_root(&mut self, root: &str) -> std::result::Result<(), Self::Error>;
56
57 fn handle_event(
58 &mut self,
59 event: &NostrEvent,
60 allow_unknown_authors: bool,
61 overmute_threshold: f64,
62 ) -> std::result::Result<(), Self::Error>;
63
64 fn get_follow_distance(&self, user: &str) -> std::result::Result<u32, Self::Error>;
65
66 fn is_following(
67 &self,
68 follower: &str,
69 followed_user: &str,
70 ) -> std::result::Result<bool, Self::Error>;
71
72 fn get_followed_by_user(&self, user: &str) -> std::result::Result<Vec<String>, Self::Error>;
73
74 fn get_followers_by_user(&self, user: &str) -> std::result::Result<Vec<String>, Self::Error>;
75
76 fn get_muted_by_user(&self, user: &str) -> std::result::Result<Vec<String>, Self::Error>;
77
78 fn get_user_muted_by(&self, user: &str) -> std::result::Result<Vec<String>, Self::Error>;
79
80 fn get_follow_list_created_at(
81 &self,
82 user: &str,
83 ) -> std::result::Result<Option<u64>, Self::Error>;
84
85 fn get_mute_list_created_at(&self, user: &str)
86 -> std::result::Result<Option<u64>, Self::Error>;
87
88 fn is_overmuted(&self, user: &str, threshold: f64) -> std::result::Result<bool, Self::Error>;
89
90 fn flush(&mut self) -> std::result::Result<(), Self::Error> {
91 Ok(())
92 }
93
94 fn has_unflushed_changes(&self) -> bool {
95 false
96 }
97}
98
99#[derive(Debug, Clone, PartialEq, Eq)]
100pub struct SocialGraphState {
101 pub root: String,
102 pub unique_ids: Vec<(String, u32)>,
103 pub follow_distance_by_user: Vec<(u32, u32)>,
104 pub users_by_follow_distance: Vec<(u32, Vec<u32>)>,
105 pub followed_by_user: Vec<(u32, Vec<u32>)>,
106 pub followers_by_user: Vec<(u32, Vec<u32>)>,
107 pub follow_list_created_at: Vec<(u32, u64)>,
108 pub muted_by_user: Vec<(u32, Vec<u32>)>,
109 pub user_muted_by: Vec<(u32, Vec<u32>)>,
110 pub mute_list_created_at: Vec<(u32, u64)>,
111}
112
113#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
114pub struct BinaryBudget {
115 pub max_nodes: Option<usize>,
116 pub max_edges: Option<usize>,
117 pub max_distance: Option<u32>,
118 pub max_edges_per_node: Option<usize>,
119}
120
121impl BinaryBudget {
122 fn has_active_limits(self) -> bool {
123 self.max_nodes.is_some_and(|value| value > 0)
124 || self.max_edges.is_some_and(|value| value > 0)
125 || self.max_distance.is_some()
126 || self.max_edges_per_node.is_some_and(|value| value > 0)
127 }
128}
129
130#[derive(Debug, Clone, PartialEq, Eq)]
131pub struct GraphStats {
132 pub users: usize,
133 pub follows: usize,
134 pub mutes: usize,
135 pub size_by_distance: IndexMap<u32, usize>,
136}
137
138#[derive(Debug, Clone, PartialEq, Eq)]
139pub struct NostrEvent {
140 pub created_at: u64,
141 pub content: String,
142 pub tags: Vec<Vec<String>>,
143 pub kind: u32,
144 pub pubkey: String,
145 pub id: String,
146 pub sig: String,
147}
148
149#[derive(Debug, Clone, Default)]
150struct UniqueIds {
151 str_to_unique_id: IndexMap<String, u32>,
152 unique_id_to_str: IndexMap<u32, String>,
153 current_unique_id: u32,
154}
155
156impl UniqueIds {
157 fn id(&mut self, value: &str) -> Result<u32> {
158 if value.trim().is_empty() {
159 return Err(SocialGraphError::EmptyString);
160 }
161 if let Some(id) = self.str_to_unique_id.get(value) {
162 return Ok(*id);
163 }
164 let id = self.current_unique_id;
165 self.current_unique_id = self.current_unique_id.saturating_add(1);
166 self.str_to_unique_id.insert(value.to_owned(), id);
167 self.unique_id_to_str.insert(id, value.to_owned());
168 Ok(id)
169 }
170
171 fn existing_id(&self, value: &str) -> Option<u32> {
172 self.str_to_unique_id.get(value).copied()
173 }
174
175 fn str(&self, id: u32) -> Result<&str> {
176 self.unique_id_to_str
177 .get(&id)
178 .map(String::as_str)
179 .ok_or(SocialGraphError::InvalidId(id))
180 }
181
182 fn clear(&mut self) {
183 self.str_to_unique_id.clear();
184 self.unique_id_to_str.clear();
185 self.current_unique_id = 0;
186 }
187
188 fn insert_with_id(&mut self, value: String, id: u32) {
189 self.current_unique_id = self.current_unique_id.max(id.saturating_add(1));
190 self.str_to_unique_id.insert(value.clone(), id);
191 self.unique_id_to_str.insert(id, value);
192 }
193
194 fn remove(&mut self, id: u32) {
195 if let Some(value) = self.unique_id_to_str.shift_remove(&id) {
196 self.str_to_unique_id.shift_remove(&value);
197 }
198 }
199}
200
201#[derive(Debug, Clone, Default)]
202pub struct SocialGraph {
203 root: u32,
204 follow_distance_by_user: IndexMap<u32, u32>,
205 users_by_follow_distance: IndexMap<u32, IndexSet<u32>>,
206 followed_by_user: IndexMap<u32, IndexSet<u32>>,
207 followers_by_user: IndexMap<u32, IndexSet<u32>>,
208 follow_list_created_at: IndexMap<u32, u64>,
209 muted_by_user: IndexMap<u32, IndexSet<u32>>,
210 user_muted_by: IndexMap<u32, IndexSet<u32>>,
211 mute_list_created_at: IndexMap<u32, u64>,
212 ids: UniqueIds,
213}
214
215#[derive(Debug)]
216struct BinaryPlan {
217 used_ids: IndexSet<u32>,
218 follow_edge_count: IndexMap<u32, usize>,
219 mute_edge_count: IndexMap<u32, usize>,
220 follow_owners: Vec<u32>,
221 mute_owners: Vec<u32>,
222}
223
224#[derive(Debug, Clone, Copy)]
225struct PotentialEdge {
226 owner: u32,
227 target: u32,
228 is_follow: bool,
229}
230
231impl SocialGraph {
232 pub fn new(root: &str) -> Self {
233 let mut ids = UniqueIds::default();
234 let root_id = ids.id(root).expect("root must not be empty");
235 let mut follow_distance_by_user = IndexMap::new();
236 follow_distance_by_user.insert(root_id, 0);
237 let mut users_by_follow_distance = IndexMap::new();
238 let mut bucket = IndexSet::new();
239 bucket.insert(root_id);
240 users_by_follow_distance.insert(0, bucket);
241 Self {
242 root: root_id,
243 follow_distance_by_user,
244 users_by_follow_distance,
245 followed_by_user: IndexMap::new(),
246 followers_by_user: IndexMap::new(),
247 follow_list_created_at: IndexMap::new(),
248 muted_by_user: IndexMap::new(),
249 user_muted_by: IndexMap::new(),
250 mute_list_created_at: IndexMap::new(),
251 ids,
252 }
253 }
254
255 pub fn get_root(&self) -> &str {
256 self.ids
257 .str(self.root)
258 .expect("root id should always exist")
259 }
260
261 pub fn set_root(&mut self, root: &str) -> Result<()> {
262 let root_id = self.ids.id(root)?;
263 if root_id == self.root {
264 return Ok(());
265 }
266 self.root = root_id;
267 self.recalculate_follow_distances();
268 Ok(())
269 }
270
271 pub fn handle_event(
272 &mut self,
273 event: &NostrEvent,
274 allow_unknown_authors: bool,
275 overmute_threshold: f64,
276 ) {
277 if !matches!(event.kind, 3 | 10_000) {
278 return;
279 }
280
281 let now = SystemTime::now()
282 .duration_since(UNIX_EPOCH)
283 .unwrap_or_default()
284 .as_secs();
285 if event.created_at > now.saturating_add(MAX_FUTURE_EVENT_SECONDS) {
286 return;
287 }
288
289 let author = if allow_unknown_authors {
290 let Ok(author) = self.ids.id(&event.pubkey) else {
291 return;
292 };
293 author
294 } else {
295 let Some(author) = self.ids.existing_id(&event.pubkey) else {
296 return;
297 };
298 if !self.follow_distance_by_user.contains_key(&author) {
299 return;
300 }
301 author
302 };
303
304 if self.is_overmuted(&event.pubkey, overmute_threshold) {
305 return;
306 }
307
308 match event.kind {
309 3 => self.handle_follow_list(author, event.created_at, &event.tags),
310 10_000 => self.handle_mute_list(author, event.created_at, &event.tags),
311 _ => {}
312 }
313 }
314
315 pub fn add_positive_relation(
316 &mut self,
317 rater: &str,
318 target: &str,
319 created_at: u64,
320 ) -> Result<bool> {
321 let rater_id = self.ids.id(rater)?;
322 let target_id = self.ids.id(target)?;
323 if rater_id == target_id {
324 return Ok(false);
325 }
326
327 let already_present = self
328 .followed_by_user
329 .get(&rater_id)
330 .is_some_and(|targets| targets.contains(&target_id));
331 self.private_add_follower(target_id, rater_id);
332 self.follow_list_created_at
333 .entry(rater_id)
334 .and_modify(|existing| *existing = (*existing).max(created_at))
335 .or_insert(created_at);
336 Ok(!already_present)
337 }
338
339 pub fn add_negative_relation(
340 &mut self,
341 rater: &str,
342 target: &str,
343 created_at: u64,
344 ) -> Result<bool> {
345 let rater_id = self.ids.id(rater)?;
346 let target_id = self.ids.id(target)?;
347 if rater_id == target_id {
348 return Ok(false);
349 }
350
351 let entry = self.muted_by_user.entry(rater_id).or_default();
352 let changed = entry.insert(target_id);
353 if changed {
354 self.user_muted_by
355 .entry(target_id)
356 .or_default()
357 .insert(rater_id);
358 }
359 self.mute_list_created_at
360 .entry(rater_id)
361 .and_modify(|existing| *existing = (*existing).max(created_at))
362 .or_insert(created_at);
363 Ok(changed)
364 }
365
366 pub fn recalculate_follow_distances(&mut self) {
367 self.follow_distance_by_user.clear();
368 self.users_by_follow_distance.clear();
369 self.follow_distance_by_user.insert(self.root, 0);
370 let mut root_bucket = IndexSet::new();
371 root_bucket.insert(self.root);
372 self.users_by_follow_distance.insert(0, root_bucket);
373
374 let mut queue = VecDeque::from([self.root]);
375 while let Some(user) = queue.pop_front() {
376 let Some(distance) = self.follow_distance_by_user.get(&user).copied() else {
377 continue;
378 };
379 let Some(followed) = self.followed_by_user.get(&user).cloned() else {
380 continue;
381 };
382 let next_distance = distance.saturating_add(1);
383 for target in followed {
384 if self.follow_distance_by_user.contains_key(&target) {
385 continue;
386 }
387 self.follow_distance_by_user.insert(target, next_distance);
388 self.users_by_follow_distance
389 .entry(next_distance)
390 .or_default()
391 .insert(target);
392 queue.push_back(target);
393 }
394 }
395 }
396
397 pub fn get_follow_distance(&self, user: &str) -> u32 {
398 let Some(user_id) = self.ids.existing_id(user) else {
399 return UNKNOWN_FOLLOW_DISTANCE;
400 };
401 self.follow_distance_by_user
402 .get(&user_id)
403 .copied()
404 .unwrap_or(UNKNOWN_FOLLOW_DISTANCE)
405 }
406
407 pub fn is_following(&self, follower: &str, followed_user: &str) -> bool {
408 let Some(follower_id) = self.ids.existing_id(follower) else {
409 return false;
410 };
411 let Some(followed_id) = self.ids.existing_id(followed_user) else {
412 return false;
413 };
414 self.followed_by_user
415 .get(&follower_id)
416 .is_some_and(|set| set.contains(&followed_id))
417 }
418
419 pub fn get_followed_by_user(&self, user: &str) -> Vec<String> {
420 let Some(user_id) = self.ids.existing_id(user) else {
421 return Vec::new();
422 };
423 self.followed_by_user
424 .get(&user_id)
425 .into_iter()
426 .flat_map(|set| set.iter())
427 .filter_map(|id| self.ids.str(*id).ok().map(ToOwned::to_owned))
428 .collect()
429 }
430
431 pub fn get_followers_by_user(&self, user: &str) -> Vec<String> {
432 let Some(user_id) = self.ids.existing_id(user) else {
433 return Vec::new();
434 };
435 self.followers_by_user
436 .get(&user_id)
437 .into_iter()
438 .flat_map(|set| set.iter())
439 .filter_map(|id| self.ids.str(*id).ok().map(ToOwned::to_owned))
440 .collect()
441 }
442
443 pub fn get_muted_by_user(&self, user: &str) -> Vec<String> {
444 let Some(user_id) = self.ids.existing_id(user) else {
445 return Vec::new();
446 };
447 self.muted_by_user
448 .get(&user_id)
449 .into_iter()
450 .flat_map(|set| set.iter())
451 .filter_map(|id| self.ids.str(*id).ok().map(ToOwned::to_owned))
452 .collect()
453 }
454
455 pub fn get_user_muted_by(&self, user: &str) -> Vec<String> {
456 let Some(user_id) = self.ids.existing_id(user) else {
457 return Vec::new();
458 };
459 self.user_muted_by
460 .get(&user_id)
461 .into_iter()
462 .flat_map(|set| set.iter())
463 .filter_map(|id| self.ids.str(*id).ok().map(ToOwned::to_owned))
464 .collect()
465 }
466
467 pub fn get_follow_list_created_at(&self, user: &str) -> Option<u64> {
468 let user_id = self.ids.existing_id(user)?;
469 self.follow_list_created_at.get(&user_id).copied()
470 }
471
472 pub fn get_mute_list_created_at(&self, user: &str) -> Option<u64> {
473 let user_id = self.ids.existing_id(user)?;
474 self.mute_list_created_at.get(&user_id).copied()
475 }
476
477 pub fn size(&self) -> GraphStats {
478 let follows = self
479 .followed_by_user
480 .values()
481 .map(IndexSet::len)
482 .sum::<usize>();
483 let mutes = self
484 .muted_by_user
485 .values()
486 .map(IndexSet::len)
487 .sum::<usize>();
488 let size_by_distance = self
489 .users_by_follow_distance
490 .iter()
491 .map(|(distance, users)| (*distance, users.len()))
492 .collect();
493
494 GraphStats {
495 users: if self.follow_distance_by_user.is_empty() {
496 self.ids.unique_id_to_str.len()
497 } else {
498 self.follow_distance_by_user.len()
499 },
500 follows,
501 mutes,
502 size_by_distance,
503 }
504 }
505
506 pub fn get_users_by_follow_distance(&self, distance: u32) -> Vec<String> {
507 self.users_by_follow_distance
508 .get(&distance)
509 .into_iter()
510 .flat_map(|users| users.iter())
511 .filter_map(|id| self.ids.str(*id).ok().map(ToOwned::to_owned))
512 .collect()
513 }
514
515 pub fn users_in_distance_order(&self, up_to_distance: Option<u32>) -> Vec<String> {
516 let mut distances: Vec<u32> = self.users_by_follow_distance.keys().copied().collect();
517 distances.sort_unstable();
518 let mut users = Vec::new();
519 for distance in distances {
520 if up_to_distance.is_some_and(|max_distance| distance > max_distance) {
521 break;
522 }
523 users.extend(self.get_users_by_follow_distance(distance));
524 }
525 users
526 }
527
528 pub fn remove_muted_not_followed_users(&mut self) -> usize {
529 let mut has_followers = IndexSet::new();
530 for followed_users in self.followed_by_user.values() {
531 for user in followed_users {
532 has_followers.insert(*user);
533 }
534 }
535
536 let users_to_remove: Vec<u32> = self
537 .user_muted_by
538 .iter()
539 .filter_map(|(user, muters)| {
540 if *user != self.root && !muters.is_empty() && !has_followers.contains(user) {
541 Some(*user)
542 } else {
543 None
544 }
545 })
546 .collect();
547
548 if users_to_remove.is_empty() {
549 return 0;
550 }
551
552 for user in users_to_remove.iter().copied() {
553 if let Some(distance) = self.follow_distance_by_user.shift_remove(&user)
554 && let Some(bucket) = self.users_by_follow_distance.get_mut(&distance)
555 {
556 bucket.shift_remove(&user);
557 }
558 self.followed_by_user.shift_remove(&user);
559 self.followers_by_user.shift_remove(&user);
560 self.follow_list_created_at.shift_remove(&user);
561 self.muted_by_user.shift_remove(&user);
562 self.user_muted_by.shift_remove(&user);
563 self.mute_list_created_at.shift_remove(&user);
564 self.ids.remove(user);
565 }
566
567 for followed_users in self.followed_by_user.values_mut() {
568 for user in &users_to_remove {
569 followed_users.shift_remove(user);
570 }
571 }
572 for followers in self.followers_by_user.values_mut() {
573 for user in &users_to_remove {
574 followers.shift_remove(user);
575 }
576 }
577 for muted_users in self.muted_by_user.values_mut() {
578 for user in &users_to_remove {
579 muted_users.shift_remove(user);
580 }
581 }
582 for muters in self.user_muted_by.values_mut() {
583 for user in &users_to_remove {
584 muters.shift_remove(user);
585 }
586 }
587
588 users_to_remove.len()
589 }
590
591 pub fn export_state(&self) -> SocialGraphState {
592 SocialGraphState {
593 root: self.get_root().to_string(),
594 unique_ids: self
595 .ids
596 .unique_id_to_str
597 .iter()
598 .map(|(id, value)| (value.clone(), *id))
599 .collect(),
600 follow_distance_by_user: self
601 .follow_distance_by_user
602 .iter()
603 .map(|(id, distance)| (*id, *distance))
604 .collect(),
605 users_by_follow_distance: self
606 .users_by_follow_distance
607 .iter()
608 .map(|(distance, users)| (*distance, users.iter().copied().collect()))
609 .collect(),
610 followed_by_user: self
611 .followed_by_user
612 .iter()
613 .map(|(user, followed)| (*user, followed.iter().copied().collect()))
614 .collect(),
615 followers_by_user: self
616 .followers_by_user
617 .iter()
618 .map(|(user, followers)| (*user, followers.iter().copied().collect()))
619 .collect(),
620 follow_list_created_at: self
621 .follow_list_created_at
622 .iter()
623 .map(|(user, created_at)| (*user, *created_at))
624 .collect(),
625 muted_by_user: self
626 .muted_by_user
627 .iter()
628 .map(|(user, muted)| (*user, muted.iter().copied().collect()))
629 .collect(),
630 user_muted_by: self
631 .user_muted_by
632 .iter()
633 .map(|(user, muters)| (*user, muters.iter().copied().collect()))
634 .collect(),
635 mute_list_created_at: self
636 .mute_list_created_at
637 .iter()
638 .map(|(user, created_at)| (*user, *created_at))
639 .collect(),
640 }
641 }
642
643 pub fn from_state(state: SocialGraphState) -> Result<Self> {
644 let mut graph = Self::new(&state.root);
645 graph.ids.clear();
646 graph.follow_distance_by_user.clear();
647 graph.users_by_follow_distance.clear();
648 graph.followed_by_user.clear();
649 graph.followers_by_user.clear();
650 graph.follow_list_created_at.clear();
651 graph.muted_by_user.clear();
652 graph.user_muted_by.clear();
653 graph.mute_list_created_at.clear();
654
655 for (value, id) in state.unique_ids {
656 graph.ids.insert_with_id(value, id);
657 }
658
659 graph.root = graph.ids.id(&state.root)?;
660
661 for (user, distance) in state.follow_distance_by_user {
662 graph.follow_distance_by_user.insert(user, distance);
663 }
664 for (distance, users) in state.users_by_follow_distance {
665 graph
666 .users_by_follow_distance
667 .insert(distance, users.into_iter().collect());
668 }
669 for (user, followed) in state.followed_by_user {
670 graph
671 .followed_by_user
672 .insert(user, followed.into_iter().collect());
673 }
674 for (user, followers) in state.followers_by_user {
675 graph
676 .followers_by_user
677 .insert(user, followers.into_iter().collect());
678 }
679 for (user, created_at) in state.follow_list_created_at {
680 graph.follow_list_created_at.insert(user, created_at);
681 }
682 for (user, muted) in state.muted_by_user {
683 graph
684 .muted_by_user
685 .insert(user, muted.into_iter().collect());
686 }
687 for (user, muters) in state.user_muted_by {
688 graph
689 .user_muted_by
690 .insert(user, muters.into_iter().collect());
691 }
692 for (user, created_at) in state.mute_list_created_at {
693 graph.mute_list_created_at.insert(user, created_at);
694 }
695
696 Ok(graph)
697 }
698
699 pub fn to_binary(&self) -> Result<Vec<u8>> {
700 self.to_binary_with_budget(BinaryBudget::default())
701 }
702
703 pub fn to_binary_with_budget(&self, budget: BinaryBudget) -> Result<Vec<u8>> {
704 let plan = self.plan_binary(budget)?;
705 self.serialize_binary(&plan)
706 }
707
708 pub fn to_binary_chunks(&self) -> Result<Vec<Vec<u8>>> {
709 self.to_binary_chunks_with_budget(BinaryBudget::default())
710 }
711
712 pub fn to_binary_chunks_with_budget(&self, budget: BinaryBudget) -> Result<Vec<Vec<u8>>> {
713 let binary = self.to_binary_with_budget(budget)?;
714 Ok(binary
715 .chunks(BINARY_CHUNK_SIZE)
716 .map(|chunk| chunk.to_vec())
717 .collect())
718 }
719
720 fn serialize_binary(&self, plan: &BinaryPlan) -> Result<Vec<u8>> {
721 let BinaryPlan {
722 used_ids,
723 follow_edge_count,
724 mute_edge_count,
725 follow_owners,
726 mute_owners,
727 } = plan;
728
729 let mut out = Vec::new();
730 write_varint(&mut out, BINARY_FORMAT_VERSION);
731 write_varint(&mut out, used_ids.len() as u64);
732 for id in used_ids.iter().copied() {
733 write_varint(&mut out, id as u64);
734 write_binary_node_id(&mut out, self.ids.str(id)?);
735 }
736
737 write_varint(&mut out, follow_owners.len() as u64);
738 for owner in follow_owners.iter().copied() {
739 let limit = follow_edge_count
740 .get(&owner)
741 .copied()
742 .expect("follow owner must have edge count");
743 write_varint(&mut out, owner as u64);
744 write_varint(
745 &mut out,
746 self.follow_list_created_at
747 .get(&owner)
748 .copied()
749 .unwrap_or(0),
750 );
751 write_varint(&mut out, limit as u64);
752 if let Some(targets) = self.followed_by_user.get(&owner) {
753 for target in targets.iter().take(limit) {
754 write_varint(&mut out, *target as u64);
755 }
756 }
757 }
758
759 write_varint(&mut out, mute_owners.len() as u64);
760 for owner in mute_owners.iter().copied() {
761 let limit = mute_edge_count
762 .get(&owner)
763 .copied()
764 .expect("mute owner must have edge count");
765 write_varint(&mut out, owner as u64);
766 write_varint(
767 &mut out,
768 self.mute_list_created_at.get(&owner).copied().unwrap_or(0),
769 );
770 write_varint(&mut out, limit as u64);
771 if let Some(targets) = self.muted_by_user.get(&owner) {
772 for target in targets.iter().take(limit) {
773 write_varint(&mut out, *target as u64);
774 }
775 }
776 }
777
778 Ok(out)
779 }
780
781 fn plan_binary(&self, budget: BinaryBudget) -> Result<BinaryPlan> {
782 if !budget.has_active_limits() {
783 return Ok(self.plan_full_binary());
784 }
785
786 let max_nodes = budget.max_nodes.filter(|value| *value > 0);
787 let max_edges = budget.max_edges.filter(|value| *value > 0);
788 let max_edges_per_node = budget.max_edges_per_node.filter(|value| *value > 0);
789
790 let mut distances: Vec<u32> = self.users_by_follow_distance.keys().copied().collect();
791 distances.sort_unstable();
792
793 let mut potential_edges = Vec::new();
794 for distance in distances {
795 if budget
796 .max_distance
797 .is_some_and(|max_distance| distance > max_distance)
798 {
799 continue;
800 }
801 let Some(users) = self.users_by_follow_distance.get(&distance) else {
802 continue;
803 };
804
805 for owner in users.iter().copied() {
806 let mut owner_edge_count = 0usize;
807
808 if let Some(followed_users) = self.followed_by_user.get(&owner) {
809 for target in followed_users.iter().copied() {
810 if max_edges_per_node.is_none_or(|limit| owner_edge_count < limit) {
811 potential_edges.push(PotentialEdge {
812 owner,
813 target,
814 is_follow: true,
815 });
816 owner_edge_count += 1;
817 }
818 }
819 }
820
821 if let Some(muted_users) = self.muted_by_user.get(&owner) {
822 for target in muted_users.iter().copied() {
823 if max_edges_per_node.is_none_or(|limit| owner_edge_count < limit) {
824 potential_edges.push(PotentialEdge {
825 owner,
826 target,
827 is_follow: false,
828 });
829 owner_edge_count += 1;
830 }
831 }
832 }
833 }
834 }
835
836 let mut used_ids = IndexSet::new();
837 let mut follow_edge_count = IndexMap::new();
838 let mut mute_edge_count = IndexMap::new();
839 let mut edge_count = 0usize;
840
841 for edge in potential_edges {
842 if max_edges.is_some_and(|limit| edge_count >= limit) {
843 break;
844 }
845
846 if self.ids.str(edge.owner).is_err() || self.ids.str(edge.target).is_err() {
847 continue;
848 }
849
850 if let Some(limit) = max_nodes {
851 let new_nodes_count = usize::from(!used_ids.contains(&edge.owner))
852 + usize::from(!used_ids.contains(&edge.target));
853 if used_ids.len() + new_nodes_count > limit {
854 break;
855 }
856 }
857
858 used_ids.insert(edge.owner);
859 used_ids.insert(edge.target);
860 edge_count += 1;
861
862 let edge_counts = if edge.is_follow {
863 &mut follow_edge_count
864 } else {
865 &mut mute_edge_count
866 };
867 *edge_counts.entry(edge.owner).or_insert(0) += 1;
868 }
869
870 let follow_owners = follow_edge_count.keys().copied().collect();
871 let mute_owners = mute_edge_count.keys().copied().collect();
872 Ok(BinaryPlan {
873 used_ids,
874 follow_edge_count,
875 mute_edge_count,
876 follow_owners,
877 mute_owners,
878 })
879 }
880
881 fn plan_full_binary(&self) -> BinaryPlan {
882 let mut used_ids = IndexSet::new();
883 let mut follow_edge_count = IndexMap::new();
884 let mut mute_edge_count = IndexMap::new();
885
886 for (user, followed_users) in &self.followed_by_user {
887 used_ids.insert(*user);
888 follow_edge_count.insert(*user, followed_users.len());
889 for followed in followed_users {
890 used_ids.insert(*followed);
891 }
892 }
893
894 for (user, muted_users) in &self.muted_by_user {
895 used_ids.insert(*user);
896 mute_edge_count.insert(*user, muted_users.len());
897 for muted in muted_users {
898 used_ids.insert(*muted);
899 }
900 }
901
902 let follow_owners = follow_edge_count.keys().copied().collect();
903 let mute_owners = mute_edge_count.keys().copied().collect();
904
905 BinaryPlan {
906 used_ids,
907 follow_edge_count,
908 mute_edge_count,
909 follow_owners,
910 mute_owners,
911 }
912 }
913
914 pub fn from_binary(root: &str, data: &[u8]) -> Result<Self> {
915 let mut offset = 0usize;
916 let version = read_varint(data, &mut offset)?;
917 if !matches!(version, BINARY_FORMAT_VERSION | BINARY_FORMAT_VERSION_V2) {
918 return Err(SocialGraphError::InvalidVersion(version));
919 }
920
921 let ids_count = read_varint(data, &mut offset)? as usize;
922 let mut unique_ids = Vec::with_capacity(ids_count);
923 for _ in 0..ids_count {
924 let (value, id) = read_binary_node_id(version, data, &mut offset)?;
925 if value.trim().is_empty() {
926 return Err(SocialGraphError::EmptyString);
927 }
928 unique_ids.push((value, id));
929 }
930
931 let follow_lists_count = read_varint(data, &mut offset)? as usize;
932 let mut follow_lists = Vec::with_capacity(follow_lists_count);
933 for _ in 0..follow_lists_count {
934 let user = read_varint(data, &mut offset)? as u32;
935 let timestamp = read_varint(data, &mut offset)?;
936 let followed_count = read_varint(data, &mut offset)? as usize;
937 let mut followed = Vec::with_capacity(followed_count);
938 for _ in 0..followed_count {
939 followed.push(read_varint(data, &mut offset)? as u32);
940 }
941 follow_lists.push((user, followed, timestamp));
942 }
943
944 let mute_lists_count = read_varint(data, &mut offset)? as usize;
945 let mut mute_lists = Vec::with_capacity(mute_lists_count);
946 for _ in 0..mute_lists_count {
947 let user = read_varint(data, &mut offset)? as u32;
948 let timestamp = read_varint(data, &mut offset)?;
949 let muted_count = read_varint(data, &mut offset)? as usize;
950 let mut muted = Vec::with_capacity(muted_count);
951 for _ in 0..muted_count {
952 muted.push(read_varint(data, &mut offset)? as u32);
953 }
954 mute_lists.push((user, muted, timestamp));
955 }
956
957 let mut graph = Self::new(root);
958 graph.ids.clear();
959 graph.follow_distance_by_user.clear();
960 graph.users_by_follow_distance.clear();
961 graph.followed_by_user.clear();
962 graph.followers_by_user.clear();
963 graph.follow_list_created_at.clear();
964 graph.muted_by_user.clear();
965 graph.user_muted_by.clear();
966 graph.mute_list_created_at.clear();
967
968 for (value, id) in unique_ids {
969 graph.ids.insert_with_id(value, id);
970 }
971
972 graph.root = graph.ids.id(root)?;
973
974 for (follower, followed_users, created_at) in follow_lists {
975 graph
976 .followed_by_user
977 .insert(follower, followed_users.iter().copied().collect());
978 for followed_user in followed_users {
979 graph
980 .followers_by_user
981 .entry(followed_user)
982 .or_default()
983 .insert(follower);
984 }
985 graph.follow_list_created_at.insert(follower, created_at);
986 }
987
988 for (muter, muted_users, created_at) in mute_lists {
989 let entry = graph.muted_by_user.entry(muter).or_default();
990 for muted_user in muted_users {
991 entry.insert(muted_user);
992 graph
993 .user_muted_by
994 .entry(muted_user)
995 .or_default()
996 .insert(muter);
997 }
998 graph.mute_list_created_at.insert(muter, created_at);
999 }
1000
1001 graph.recalculate_follow_distances();
1002
1003 Ok(graph)
1004 }
1005
1006 pub fn is_overmuted(&self, user: &str, threshold: f64) -> bool {
1007 if user == self.get_root() {
1008 return false;
1009 }
1010
1011 let Some(user_id) = self.ids.existing_id(user) else {
1012 return false;
1013 };
1014 let Some(muters) = self.user_muted_by.get(&user_id) else {
1015 return false;
1016 };
1017 if muters.is_empty() {
1018 return false;
1019 }
1020 if muters.contains(&self.root) {
1021 return true;
1022 }
1023
1024 let mut stats = IndexMap::<u32, (u32, u32)>::new();
1025 if let Some(followers) = self.followers_by_user.get(&user_id) {
1026 for follower in followers {
1027 if let Some(distance) = self.follow_distance_by_user.get(follower).copied() {
1028 let entry = stats.entry(distance).or_insert((0, 0));
1029 entry.0 += 1;
1030 }
1031 }
1032 }
1033 for muter in muters {
1034 if let Some(distance) = self.follow_distance_by_user.get(muter).copied() {
1035 let entry = stats.entry(distance).or_insert((0, 0));
1036 entry.1 += 1;
1037 }
1038 }
1039
1040 let mut distances: Vec<u32> = stats.keys().copied().collect();
1041 distances.sort_unstable();
1042 for distance in distances {
1043 let (followers, muters) = stats[&distance];
1044 if followers + muters > 0 {
1045 return (muters as f64) * threshold > followers as f64;
1046 }
1047 }
1048 false
1049 }
1050
1051 fn handle_follow_list(&mut self, author: u32, created_at: u64, tags: &[Vec<String>]) {
1052 if self
1053 .follow_list_created_at
1054 .get(&author)
1055 .is_some_and(|existing| created_at <= *existing)
1056 {
1057 return;
1058 }
1059 self.follow_list_created_at.insert(author, created_at);
1060
1061 let mut followed_in_event = IndexSet::new();
1062 for tag in tags {
1063 if tag.first().is_some_and(|value| value == "p")
1064 && tag.get(1).is_some_and(|pk| is_valid_pubkey(pk))
1065 {
1066 let Ok(followed_user) = self.ids.id(&tag[1]) else {
1067 continue;
1068 };
1069 if followed_user != author {
1070 followed_in_event.insert(followed_user);
1071 }
1072 }
1073 }
1074
1075 let currently_followed = self
1076 .followed_by_user
1077 .get(&author)
1078 .cloned()
1079 .unwrap_or_default();
1080 for user in currently_followed {
1081 if !followed_in_event.contains(&user) {
1082 self.private_remove_follower(user, author);
1083 }
1084 }
1085 for user in followed_in_event {
1086 self.private_add_follower(user, author);
1087 }
1088 }
1089
1090 fn handle_mute_list(&mut self, author: u32, created_at: u64, tags: &[Vec<String>]) {
1091 if self
1092 .mute_list_created_at
1093 .get(&author)
1094 .is_some_and(|existing| created_at <= *existing)
1095 {
1096 return;
1097 }
1098 self.mute_list_created_at.insert(author, created_at);
1099
1100 let mut muted_in_event = IndexSet::new();
1101 for tag in tags {
1102 if tag.first().is_some_and(|value| value == "p")
1103 && tag.get(1).is_some_and(|pk| is_valid_pubkey(pk))
1104 {
1105 let Ok(muted_user) = self.ids.id(&tag[1]) else {
1106 continue;
1107 };
1108 if muted_user != author {
1109 muted_in_event.insert(muted_user);
1110 }
1111 }
1112 }
1113
1114 let currently_muted = self.muted_by_user.get(&author).cloned().unwrap_or_default();
1115 for user in currently_muted {
1116 if !muted_in_event.contains(&user) {
1117 if let Some(set) = self.muted_by_user.get_mut(&author) {
1118 set.shift_remove(&user);
1119 }
1120 if let Some(set) = self.user_muted_by.get_mut(&user) {
1121 set.shift_remove(&author);
1122 }
1123 }
1124 }
1125
1126 for user in muted_in_event {
1127 self.muted_by_user.entry(author).or_default().insert(user);
1128 self.user_muted_by.entry(user).or_default().insert(author);
1129 }
1130 }
1131
1132 fn private_add_follower(&mut self, followed_user: u32, follower: u32) {
1133 self.followed_by_user
1134 .entry(follower)
1135 .or_default()
1136 .insert(followed_user);
1137 self.followers_by_user
1138 .entry(followed_user)
1139 .or_default()
1140 .insert(follower);
1141
1142 if followed_user == self.root {
1143 return;
1144 }
1145
1146 if follower == self.root {
1147 self.follow_distance_by_user.insert(followed_user, 1);
1148 self.add_user_by_follow_distance(1, followed_user);
1149 return;
1150 }
1151
1152 let existing = self.follow_distance_by_user.get(&followed_user).copied();
1153 let follower_distance = self.follow_distance_by_user.get(&follower).copied();
1154 let new_distance = follower_distance.map(|distance| distance.saturating_add(1));
1155 if let Some(distance) = new_distance
1156 .filter(|distance| existing.is_none() || *distance < existing.unwrap_or(u32::MAX))
1157 {
1158 self.follow_distance_by_user.insert(followed_user, distance);
1159 self.add_user_by_follow_distance(distance, followed_user);
1160 }
1161 }
1162
1163 fn private_remove_follower(&mut self, unfollowed_user: u32, follower: u32) {
1164 if let Some(set) = self.followed_by_user.get_mut(&follower) {
1165 set.shift_remove(&unfollowed_user);
1166 }
1167 if let Some(set) = self.followers_by_user.get_mut(&unfollowed_user) {
1168 set.shift_remove(&follower);
1169 }
1170
1171 if unfollowed_user == self.root {
1172 return;
1173 }
1174
1175 let mut smallest = None;
1176 if let Some(followers) = self.followers_by_user.get(&unfollowed_user) {
1177 for follower in followers {
1178 if let Some(distance) = self.follow_distance_by_user.get(follower).copied() {
1179 let candidate = distance.saturating_add(1);
1180 smallest =
1181 Some(smallest.map_or(candidate, |current: u32| current.min(candidate)));
1182 }
1183 }
1184 }
1185
1186 match smallest {
1187 Some(distance) => {
1188 self.follow_distance_by_user
1189 .insert(unfollowed_user, distance);
1190 self.add_user_by_follow_distance(distance, unfollowed_user);
1191 }
1192 None => {
1193 self.follow_distance_by_user.shift_remove(&unfollowed_user);
1194 for bucket in self.users_by_follow_distance.values_mut() {
1195 bucket.shift_remove(&unfollowed_user);
1196 }
1197 }
1198 }
1199 }
1200
1201 fn add_user_by_follow_distance(&mut self, distance: u32, user: u32) {
1202 self.users_by_follow_distance
1203 .entry(distance)
1204 .or_default()
1205 .insert(user);
1206 let keys: Vec<u32> = self.users_by_follow_distance.keys().copied().collect();
1207 for key in keys.into_iter().filter(|key| *key > distance) {
1208 if let Some(bucket) = self.users_by_follow_distance.get_mut(&key) {
1209 bucket.shift_remove(&user);
1210 }
1211 }
1212 }
1213}
1214
1215impl SocialGraphBackend for SocialGraph {
1216 type Error = SocialGraphError;
1217
1218 fn get_root(&self) -> std::result::Result<String, Self::Error> {
1219 Ok(SocialGraph::get_root(self).to_string())
1220 }
1221
1222 fn set_root(&mut self, root: &str) -> std::result::Result<(), Self::Error> {
1223 SocialGraph::set_root(self, root)
1224 }
1225
1226 fn handle_event(
1227 &mut self,
1228 event: &NostrEvent,
1229 allow_unknown_authors: bool,
1230 overmute_threshold: f64,
1231 ) -> std::result::Result<(), Self::Error> {
1232 SocialGraph::handle_event(self, event, allow_unknown_authors, overmute_threshold);
1233 Ok(())
1234 }
1235
1236 fn get_follow_distance(&self, user: &str) -> std::result::Result<u32, Self::Error> {
1237 Ok(SocialGraph::get_follow_distance(self, user))
1238 }
1239
1240 fn is_following(
1241 &self,
1242 follower: &str,
1243 followed_user: &str,
1244 ) -> std::result::Result<bool, Self::Error> {
1245 Ok(SocialGraph::is_following(self, follower, followed_user))
1246 }
1247
1248 fn get_followed_by_user(&self, user: &str) -> std::result::Result<Vec<String>, Self::Error> {
1249 Ok(SocialGraph::get_followed_by_user(self, user))
1250 }
1251
1252 fn get_followers_by_user(&self, user: &str) -> std::result::Result<Vec<String>, Self::Error> {
1253 Ok(SocialGraph::get_followers_by_user(self, user))
1254 }
1255
1256 fn get_muted_by_user(&self, user: &str) -> std::result::Result<Vec<String>, Self::Error> {
1257 Ok(SocialGraph::get_muted_by_user(self, user))
1258 }
1259
1260 fn get_user_muted_by(&self, user: &str) -> std::result::Result<Vec<String>, Self::Error> {
1261 Ok(SocialGraph::get_user_muted_by(self, user))
1262 }
1263
1264 fn get_follow_list_created_at(
1265 &self,
1266 user: &str,
1267 ) -> std::result::Result<Option<u64>, Self::Error> {
1268 Ok(SocialGraph::get_follow_list_created_at(self, user))
1269 }
1270
1271 fn get_mute_list_created_at(
1272 &self,
1273 user: &str,
1274 ) -> std::result::Result<Option<u64>, Self::Error> {
1275 Ok(SocialGraph::get_mute_list_created_at(self, user))
1276 }
1277
1278 fn is_overmuted(&self, user: &str, threshold: f64) -> std::result::Result<bool, Self::Error> {
1279 Ok(SocialGraph::is_overmuted(self, user, threshold))
1280 }
1281}
1282
1283fn is_valid_pubkey(key: &str) -> bool {
1284 key.len() == 64 && key.bytes().all(|byte| byte.is_ascii_hexdigit())
1285}
1286
1287fn is_canonical_uuid(value: &str) -> Option<Uuid> {
1288 let uuid = Uuid::parse_str(value).ok()?;
1289 (uuid.to_string() == value).then_some(uuid)
1290}
1291
1292fn write_binary_node_id(out: &mut Vec<u8>, value: &str) {
1293 if is_valid_pubkey(value) {
1294 write_varint(out, BINARY_NODE_ID_PUBKEY);
1295 let bytes = hex::decode(value).expect("validated pubkey hex should decode");
1296 out.extend_from_slice(&bytes);
1297 return;
1298 }
1299
1300 if let Some(uuid) = is_canonical_uuid(value) {
1301 write_varint(out, BINARY_NODE_ID_UUID);
1302 out.extend_from_slice(uuid.as_bytes());
1303 return;
1304 }
1305
1306 write_varint(out, BINARY_NODE_ID_STRING);
1307 write_varint(out, value.len() as u64);
1308 out.extend_from_slice(value.as_bytes());
1309}
1310
1311fn read_binary_node_id(version: u64, data: &[u8], offset: &mut usize) -> Result<(String, u32)> {
1312 if version == BINARY_FORMAT_VERSION_V2 {
1313 let hex_bytes = read_bytes(data, offset, 32)?;
1314 let id = read_varint(data, offset)? as u32;
1315 return Ok((hex::encode(hex_bytes), id));
1316 }
1317
1318 let id = read_varint(data, offset)? as u32;
1319 let node_id_type = read_varint(data, offset)?;
1320 let value = match node_id_type {
1321 BINARY_NODE_ID_PUBKEY => {
1322 let bytes = read_bytes(data, offset, 32)?;
1323 hex::encode(bytes)
1324 }
1325 BINARY_NODE_ID_UUID => {
1326 let bytes = read_bytes(data, offset, 16)?;
1327 Uuid::from_slice(bytes)
1328 .map_err(|_| SocialGraphError::InvalidBinaryNodeIdUuid)?
1329 .to_string()
1330 }
1331 BINARY_NODE_ID_STRING => {
1332 let len = read_varint(data, offset)? as usize;
1333 let bytes = read_bytes(data, offset, len)?;
1334 str::from_utf8(bytes)
1335 .map_err(|_| SocialGraphError::InvalidBinaryNodeIdUtf8)?
1336 .to_owned()
1337 }
1338 other => return Err(SocialGraphError::InvalidBinaryNodeIdType(other)),
1339 };
1340 Ok((value, id))
1341}
1342
1343fn write_varint(out: &mut Vec<u8>, mut value: u64) {
1344 while value >= 0x80 {
1345 out.push(((value as u8) & 0x7f) | 0x80);
1346 value >>= 7;
1347 }
1348 out.push((value & 0x7f) as u8);
1349}
1350
1351fn read_varint(data: &[u8], offset: &mut usize) -> Result<u64> {
1352 let mut value = 0u64;
1353 let mut shift = 0u32;
1354 loop {
1355 let byte = *data.get(*offset).ok_or(SocialGraphError::UnexpectedEof)?;
1356 *offset += 1;
1357 value |= u64::from(byte & 0x7f) << shift;
1358 if byte & 0x80 == 0 {
1359 return Ok(value);
1360 }
1361 shift += 7;
1362 }
1363}
1364
1365fn read_bytes<'a>(data: &'a [u8], offset: &mut usize, len: usize) -> Result<&'a [u8]> {
1366 let end = offset.saturating_add(len);
1367 if end > data.len() {
1368 return Err(SocialGraphError::UnexpectedEof);
1369 }
1370 let slice = &data[*offset..end];
1371 *offset = end;
1372 Ok(slice)
1373}
1374
1375#[cfg(test)]
1376mod tests {
1377 use super::*;
1378
1379 const ADAM: &str = "020f2d21ae09bf35fcdfb65decf1478b846f5f728ab30c5eaabcd6d081a81c3e";
1380 const FIATJAF: &str = "3bf0c63fcb93463407af97a5e5ee64fa883d107ef9e558472c4eb9aaaefa459d";
1381
1382 fn event(pubkey: &str, kind: u32, created_at: u64, tagged: Vec<&str>) -> NostrEvent {
1383 NostrEvent {
1384 created_at,
1385 content: String::new(),
1386 tags: tagged
1387 .into_iter()
1388 .map(|pk| vec!["p".to_string(), pk.to_string()])
1389 .collect(),
1390 kind,
1391 pubkey: pubkey.to_string(),
1392 id: format!("{pubkey}:{kind}:{created_at}"),
1393 sig: "00".repeat(64),
1394 }
1395 }
1396
1397 #[test]
1398 fn read_queries_do_not_intern_unknown_users() {
1399 let graph = SocialGraph::new(ADAM);
1400 let before = graph.export_state();
1401
1402 assert_eq!(
1403 graph.get_follow_distance("ff".repeat(32).as_str()),
1404 UNKNOWN_FOLLOW_DISTANCE
1405 );
1406 assert!(!graph.is_following(ADAM, &"ee".repeat(32)));
1407 assert!(graph.get_followed_by_user(&"dd".repeat(32)).is_empty());
1408 assert!(graph.get_followers_by_user(&"cc".repeat(32)).is_empty());
1409 assert!(graph.get_muted_by_user(&"bb".repeat(32)).is_empty());
1410 assert!(graph.get_user_muted_by(&"aa".repeat(32)).is_empty());
1411 assert_eq!(graph.get_follow_list_created_at(&"11".repeat(32)), None);
1412 assert_eq!(graph.get_mute_list_created_at(&"22".repeat(32)), None);
1413 assert!(!graph.is_overmuted(&"33".repeat(32), 1.0));
1414
1415 let after = graph.export_state();
1416 assert_eq!(after.unique_ids, before.unique_ids);
1417 }
1418
1419 #[test]
1420 fn unique_ids_round_trip_and_reuse_existing_ids() {
1421 let mut ids = UniqueIds::default();
1422
1423 let adam = ids.id(ADAM).unwrap();
1424 let fiatjaf = ids.id(FIATJAF).unwrap();
1425
1426 assert_eq!(adam, 0);
1427 assert_eq!(fiatjaf, 1);
1428 assert_eq!(ids.id(ADAM).unwrap(), adam);
1429 assert_eq!(ids.str(adam).unwrap(), ADAM);
1430 assert_eq!(ids.str(fiatjaf).unwrap(), FIATJAF);
1431 }
1432
1433 #[test]
1434 fn unique_ids_reject_empty_strings_and_invalid_ids() {
1435 let mut ids = UniqueIds::default();
1436
1437 assert_eq!(
1438 ids.id(" ").unwrap_err().to_string(),
1439 "cannot store empty or whitespace-only strings"
1440 );
1441 assert_eq!(ids.str(99).unwrap_err().to_string(), "invalid id 99");
1442 }
1443
1444 #[test]
1445 fn from_binary_rejects_invalid_version() {
1446 let error = SocialGraph::from_binary(ADAM, &[99]).unwrap_err();
1447 assert!(matches!(error, SocialGraphError::InvalidVersion(99)));
1448 }
1449
1450 #[test]
1451 fn from_binary_rejects_truncated_binary() {
1452 let error = SocialGraph::from_binary(ADAM, &[BINARY_FORMAT_VERSION as u8]).unwrap_err();
1453 assert!(matches!(error, SocialGraphError::UnexpectedEof));
1454 }
1455
1456 #[test]
1457 fn from_binary_reads_v2_pubkey_tables() {
1458 let mut binary = Vec::new();
1459 write_varint(&mut binary, BINARY_FORMAT_VERSION_V2);
1460 write_varint(&mut binary, 2);
1461 binary.extend_from_slice(&hex::decode(ADAM).unwrap());
1462 write_varint(&mut binary, 0);
1463 binary.extend_from_slice(&hex::decode(FIATJAF).unwrap());
1464 write_varint(&mut binary, 1);
1465 write_varint(&mut binary, 1);
1466 write_varint(&mut binary, 0);
1467 write_varint(&mut binary, 1_000);
1468 write_varint(&mut binary, 1);
1469 write_varint(&mut binary, 1);
1470 write_varint(&mut binary, 0);
1471
1472 let restored = SocialGraph::from_binary(ADAM, &binary).unwrap();
1473 assert!(restored.is_following(ADAM, FIATJAF));
1474 assert_eq!(restored.get_follow_distance(FIATJAF), 1);
1475 }
1476
1477 #[test]
1478 fn binary_v3_round_trips_non_hex_authors() {
1479 let mut graph = SocialGraph::new(ADAM);
1480 graph.handle_event(
1481 &event("not-a-hex-pubkey", 3, 1_000, vec![FIATJAF]),
1482 true,
1483 1.0,
1484 );
1485
1486 let binary = graph.to_binary().unwrap();
1487 assert_eq!(binary[0], BINARY_FORMAT_VERSION as u8);
1488
1489 let restored = SocialGraph::from_binary(ADAM, &binary).unwrap();
1490 assert!(restored.is_following("not-a-hex-pubkey", FIATJAF));
1491 assert_eq!(
1492 restored.get_follow_distance(FIATJAF),
1493 UNKNOWN_FOLLOW_DISTANCE
1494 );
1495
1496 let restored_from_author = SocialGraph::from_binary("not-a-hex-pubkey", &binary).unwrap();
1497 assert_eq!(restored_from_author.get_follow_distance(FIATJAF), 1);
1498 }
1499
1500 #[test]
1501 fn binary_v3_round_trips_uuid_and_string_nodes() {
1502 let uuid = "6b7f5df4-1d2d-43a7-9b87-873e41a2d99a";
1503 let external = "external:nvpn-peer:exit-a";
1504
1505 let mut graph = SocialGraph::new(ADAM);
1506 let root = graph.ids.existing_id(ADAM).unwrap();
1507 let uuid_id = graph.ids.id(uuid).unwrap();
1508 let external_id = graph.ids.id(external).unwrap();
1509 graph.private_add_follower(uuid_id, root);
1510 graph.private_add_follower(external_id, uuid_id);
1511
1512 let binary = graph.to_binary().unwrap();
1513 assert_eq!(binary[0], BINARY_FORMAT_VERSION as u8);
1514
1515 let restored = SocialGraph::from_binary(ADAM, &binary).unwrap();
1516 assert!(restored.is_following(ADAM, uuid));
1517 assert!(restored.is_following(uuid, external));
1518 assert_eq!(restored.get_follow_distance(uuid), 1);
1519 assert_eq!(restored.get_follow_distance(external), 2);
1520 }
1521}