| 1 | use std::collections::{BTreeMap, BTreeSet}; |
| 2 | |
| 3 | use ruma::OwnedUserId; |
| 4 | use serde_json::Value; |
| 5 | |
| 6 | use crate::{ |
| 7 | Error, ErrorKind, EventContext, MentionCaptureState, MentionCoverage, MentionEntry, MentionGap, |
| 8 | MentionGapReason, MentionKey, MentionsBoundary, MentionsPage, SavedMentionContext, |
| 9 | TimelineItem, normalise::MediaRegistration, |
| 10 | }; |
| 11 | |
| 12 | const CANDIDATE_LIFETIME_MS: u64 = 7 * 24 * 60 * 60 * 1000; |
| 13 | |
| 14 | #[derive(Clone)] |
| 15 | #[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))] |
| 16 | pub(super) struct SavedEvent { |
| 17 | pub item: TimelineItem, |
| 18 | pub media: Vec<MediaRegistration>, |
| 19 | pub raw: Option<Value>, |
| 20 | } |
| 21 | |
| 22 | impl PartialEq for SavedEvent { |
| 23 | fn eq(&self, other: &Self) -> bool { |
| 24 | self.item == other.item |
| 25 | && self.raw == other.raw |
| 26 | && self |
| 27 | .media |
| 28 | .iter() |
| 29 | .map(|media| &media.id) |
| 30 | .eq(other.media.iter().map(|media| &media.id)) |
| 31 | } |
| 32 | } |
| 33 | |
| 34 | #[derive(Clone, PartialEq)] |
| 35 | #[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))] |
| 36 | pub(super) struct Candidate { |
| 37 | pub room_id: ruma::OwnedRoomId, |
| 38 | pub raw: Value, |
| 39 | pub attempts: u32, |
| 40 | pub retry_at_ms: u64, |
| 41 | pub first_seen_ms: u64, |
| 42 | } |
| 43 | |
| 44 | impl Candidate { |
| 45 | pub fn new(room_id: ruma::OwnedRoomId, raw: Value, retry_at_ms: u64) -> Self { |
| 46 | Self { |
| 47 | room_id, |
| 48 | raw, |
| 49 | attempts: 0, |
| 50 | retry_at_ms, |
| 51 | first_seen_ms: now(), |
| 52 | } |
| 53 | } |
| 54 | |
| 55 | pub fn encrypted(&self) -> bool { |
| 56 | self.raw["type"] == "m.room.encrypted" |
| 57 | } |
| 58 | } |
| 59 | |
| 60 | #[derive(Clone, PartialEq)] |
| 61 | #[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))] |
| 62 | pub(super) struct Window { |
| 63 | pub before: Vec<String>, |
| 64 | pub target: Option<String>, |
| 65 | pub after: Vec<String>, |
| 66 | pub start: Option<String>, |
| 67 | pub end: Option<String>, |
| 68 | } |
| 69 | |
| 70 | #[derive(Clone, Default, PartialEq)] |
| 71 | #[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))] |
| 72 | pub(super) struct Data { |
| 73 | pub revision: u64, |
| 74 | pub entries: BTreeMap<String, MentionEntry>, |
| 75 | pub events: BTreeMap<String, SavedEvent>, |
| 76 | pub windows: BTreeMap<String, Window>, |
| 77 | pub capture_attempts: BTreeMap<String, u32>, |
| 78 | pub candidates: BTreeMap<String, Candidate>, |
| 79 | pub redacted: BTreeMap<String, u64>, |
| 80 | pub edits: BTreeMap<String, Value>, |
| 81 | pub coverage: MentionCoverage, |
| 82 | pub history_cursor: Option<String>, |
| 83 | pub history_exhausted: bool, |
| 84 | pub latest_cursor: Option<String>, |
| 85 | pub latest_anchor: Option<String>, |
| 86 | pub latest_head: Option<String>, |
| 87 | } |
| 88 | |
| 89 | #[derive(Clone, Default, PartialEq)] |
| 90 | #[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))] |
| 91 | pub(super) struct SyncState { |
| 92 | pub inbox_revision: u64, |
| 93 | pub checkpoints: BTreeMap<String, Checkpoint>, |
| 94 | } |
| 95 | |
| 96 | /// what a set of rooms holds in the inbox, compared before and after a change so an |
| 97 | /// unchanged inbox costs only the rooms it touched |
| 98 | #[derive(PartialEq)] |
| 99 | pub(super) struct Scope { |
| 100 | rooms: Vec<RoomScope>, |
| 101 | coverage: MentionCoverage, |
| 102 | cursors: ( |
| 103 | Option<String>, |
| 104 | bool, |
| 105 | Option<String>, |
| 106 | Option<String>, |
| 107 | Option<String>, |
| 108 | ), |
| 109 | } |
| 110 | |
| 111 | #[derive(PartialEq)] |
| 112 | struct RoomScope { |
| 113 | entries: Vec<MentionEntry>, |
| 114 | events: Vec<SavedEvent>, |
| 115 | windows: Vec<Window>, |
| 116 | capture_attempts: Vec<u32>, |
| 117 | candidates: Vec<Candidate>, |
| 118 | redacted: Vec<u64>, |
| 119 | edits: Vec<Value>, |
| 120 | keys: Vec<String>, |
| 121 | } |
| 122 | |
| 123 | fn in_room<V: Clone>( |
| 124 | map: &BTreeMap<String, V>, |
| 125 | room: &ruma::RoomId, |
| 126 | keys: &mut Vec<String>, |
| 127 | ) -> Vec<V> { |
| 128 | // no room id holds a newline, so a room's "room\nevent" keys sit below "room\x0b" |
| 129 | map.range(format!("{room}\n")..format!("{room}\u{b}")) |
| 130 | .map(|(key, value)| { |
| 131 | keys.push(key.clone()); |
| 132 | value.clone() |
| 133 | }) |
| 134 | .collect() |
| 135 | } |
| 136 | |
| 137 | #[derive(Clone, Debug, PartialEq)] |
| 138 | #[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))] |
| 139 | pub(super) struct Checkpoint { |
| 140 | pub pos: String, |
| 141 | pub previous: Option<String>, |
| 142 | } |
| 143 | |
| 144 | pub(super) fn id(key: &MentionKey) -> String { |
| 145 | format!("{}\n{}", key.room_id, key.event_id) |
| 146 | } |
| 147 | |
| 148 | pub(super) fn now() -> u64 { |
| 149 | matrix_sdk::ruma::MilliSecondsSinceUnixEpoch::now() |
| 150 | .get() |
| 151 | .into() |
| 152 | } |
| 153 | |
| 154 | pub(super) fn invalid(message: &'static str) -> Error { |
| 155 | Error::new(ErrorKind::Invalid, message) |
| 156 | } |
| 157 | |
| 158 | #[cfg(feature = "serde")] |
| 159 | pub(super) fn json_len(value: &impl serde::Serialize) -> usize { |
| 160 | struct Count(usize); |
| 161 | impl std::io::Write for Count { |
| 162 | fn write(&mut self, bytes: &[u8]) -> std::io::Result<usize> { |
| 163 | self.0 += bytes.len(); |
| 164 | Ok(bytes.len()) |
| 165 | } |
| 166 | fn flush(&mut self) -> std::io::Result<()> { |
| 167 | Ok(()) |
| 168 | } |
| 169 | } |
| 170 | let mut count = Count(0); |
| 171 | let _ = serde_json::to_writer(&mut count, value); |
| 172 | count.0 |
| 173 | } |
| 174 | |
| 175 | #[cfg(not(feature = "serde"))] |
| 176 | pub(super) fn json_len<T>(_: &T) -> usize { |
| 177 | 0 |
| 178 | } |
| 179 | |
| 180 | fn timestamp(value: &Value) -> u64 { |
| 181 | value["origin_server_ts"].as_u64().unwrap_or(0) |
| 182 | } |
| 183 | |
| 184 | impl Data { |
| 185 | pub fn scope<'a>(&self, rooms: impl IntoIterator<Item = &'a ruma::OwnedRoomId>) -> Scope { |
| 186 | Scope { |
| 187 | rooms: rooms |
| 188 | .into_iter() |
| 189 | .map(|room| { |
| 190 | let mut keys = Vec::new(); |
| 191 | RoomScope { |
| 192 | entries: in_room(&self.entries, room, &mut keys), |
| 193 | events: in_room(&self.events, room, &mut keys), |
| 194 | windows: in_room(&self.windows, room, &mut keys), |
| 195 | capture_attempts: in_room(&self.capture_attempts, room, &mut keys), |
| 196 | candidates: in_room(&self.candidates, room, &mut keys), |
| 197 | redacted: in_room(&self.redacted, room, &mut keys), |
| 198 | edits: in_room(&self.edits, room, &mut keys), |
| 199 | keys, |
| 200 | } |
| 201 | }) |
| 202 | .collect(), |
| 203 | coverage: self.coverage.clone(), |
| 204 | cursors: ( |
| 205 | self.history_cursor.clone(), |
| 206 | self.history_exhausted, |
| 207 | self.latest_cursor.clone(), |
| 208 | self.latest_anchor.clone(), |
| 209 | self.latest_head.clone(), |
| 210 | ), |
| 211 | } |
| 212 | } |
| 213 | |
| 214 | /// folds an inbox built in memory while the store was unreachable into the one the |
| 215 | /// store held, keeping the newer side where both have a key |
| 216 | pub fn absorb(&mut self, newer: Data) { |
| 217 | self.revision = self.revision.max(newer.revision); |
| 218 | self.entries.extend(newer.entries); |
| 219 | self.events.extend(newer.events); |
| 220 | self.windows.extend(newer.windows); |
| 221 | self.capture_attempts.extend(newer.capture_attempts); |
| 222 | self.candidates.extend(newer.candidates); |
| 223 | self.redacted.extend(newer.redacted); |
| 224 | self.edits.extend(newer.edits); |
| 225 | for gap in newer.coverage.gaps { |
| 226 | self.gap(gap.room_id, gap.reason, gap.token); |
| 227 | } |
| 228 | self.coverage.earliest_timestamp_ms = self |
| 229 | .coverage |
| 230 | .earliest_timestamp_ms |
| 231 | .into_iter() |
| 232 | .chain(newer.coverage.earliest_timestamp_ms) |
| 233 | .min(); |
| 234 | self.coverage.truncated |= newer.coverage.truncated; |
| 235 | self.history_cursor = newer.history_cursor.or(self.history_cursor.take()); |
| 236 | self.latest_cursor = newer.latest_cursor.or(self.latest_cursor.take()); |
| 237 | self.latest_anchor = newer.latest_anchor.or(self.latest_anchor.take()); |
| 238 | self.latest_head = newer.latest_head.or(self.latest_head.take()); |
| 239 | } |
| 240 | |
| 241 | pub fn gap( |
| 242 | &mut self, |
| 243 | room_id: Option<ruma::OwnedRoomId>, |
| 244 | reason: MentionGapReason, |
| 245 | token: Option<String>, |
| 246 | ) { |
| 247 | if self |
| 248 | .coverage |
| 249 | .gaps |
| 250 | .iter() |
| 251 | .any(|gap| gap.room_id == room_id && gap.reason == reason && gap.token == token) |
| 252 | { |
| 253 | return; |
| 254 | } |
| 255 | self.coverage.gaps.push(MentionGap { |
| 256 | room_id, |
| 257 | reason, |
| 258 | token, |
| 259 | }); |
| 260 | if self.coverage.gaps.len() > 128 { |
| 261 | self.coverage.gaps.remove(0); |
| 262 | self.coverage.truncated = true; |
| 263 | } |
| 264 | } |
| 265 | |
| 266 | pub fn expire_candidates(&mut self, now_ms: u64) -> bool { |
| 267 | let expired: Vec<_> = self |
| 268 | .candidates |
| 269 | .iter() |
| 270 | .filter(|(_, candidate)| { |
| 271 | now_ms.saturating_sub(candidate.first_seen_ms) > CANDIDATE_LIFETIME_MS |
| 272 | }) |
| 273 | .map(|(key, candidate)| (key.clone(), candidate.room_id.clone())) |
| 274 | .collect(); |
| 275 | for (key, room_id) in &expired { |
| 276 | self.candidates.remove(key); |
| 277 | self.gap( |
| 278 | Some(room_id.clone()), |
| 279 | MentionGapReason::CandidateExpired, |
| 280 | None, |
| 281 | ); |
| 282 | } |
| 283 | !expired.is_empty() |
| 284 | } |
| 285 | |
| 286 | pub fn touch_contexts(&mut self, identity: &str) { |
| 287 | for (key, window) in &self.windows { |
| 288 | if window.target.as_deref() == Some(identity) |
| 289 | || window |
| 290 | .before |
| 291 | .iter() |
| 292 | .chain(&window.after) |
| 293 | .any(|key| key == identity) |
| 294 | { |
| 295 | if let Some(entry) = self.entries.get_mut(key) { |
| 296 | entry.revision = self.revision + 1; |
| 297 | } |
| 298 | } |
| 299 | } |
| 300 | } |
| 301 | |
| 302 | pub fn page( |
| 303 | &self, |
| 304 | account: &OwnedUserId, |
| 305 | cursor: Option<&str>, |
| 306 | limit: u16, |
| 307 | ) -> Result<MentionsPage, Error> { |
| 308 | let (boundary, last) = if let Some(cursor) = cursor { |
| 309 | let value: Value = |
| 310 | serde_json::from_str(cursor).map_err(|_| invalid("invalid mentions cursor"))?; |
| 311 | if value["account"].as_str() != Some(account.as_str()) { |
| 312 | return Err(invalid("mentions cursor belongs to a different account")); |
| 313 | } |
| 314 | let boundary = value["revision"] |
| 315 | .as_u64() |
| 316 | .ok_or_else(|| invalid("invalid mentions cursor"))?; |
| 317 | let timestamp = value["timestamp"] |
| 318 | .as_u64() |
| 319 | .ok_or_else(|| invalid("invalid mentions cursor"))?; |
| 320 | let key = value["key"] |
| 321 | .as_str() |
| 322 | .ok_or_else(|| invalid("invalid mentions cursor"))? |
| 323 | .to_owned(); |
| 324 | if boundary > self.revision { |
| 325 | return Err(invalid("mentions cursor is newer than this store")); |
| 326 | } |
| 327 | (boundary, Some((timestamp, key))) |
| 328 | } else { |
| 329 | (self.revision, None) |
| 330 | }; |
| 331 | let mut entries: Vec<_> = self |
| 332 | .entries |
| 333 | .iter() |
| 334 | .filter(|(key, entry)| { |
| 335 | entry.discovery_revision <= boundary |
| 336 | && last.as_ref().is_none_or(|last| { |
| 337 | (entry.timestamp_ms, key.as_str()) < (last.0, last.1.as_str()) |
| 338 | }) |
| 339 | }) |
| 340 | .map(|(_, entry)| entry.clone()) |
| 341 | .collect(); |
| 342 | entries.sort_by(|a, b| (b.timestamp_ms, id(&b.key)).cmp(&(a.timestamp_ms, id(&a.key)))); |
| 343 | let limit = usize::from(limit.clamp(1, 50)); |
| 344 | let end_reached = entries.len() <= limit; |
| 345 | entries.truncate(limit); |
| 346 | let next_cursor = if end_reached { |
| 347 | None |
| 348 | } else { |
| 349 | entries.last().map(|entry| serde_json::json!({ |
| 350 | "account": account.as_str(), "revision": boundary, "timestamp": entry.timestamp_ms, "key": id(&entry.key) |
| 351 | }).to_string()) |
| 352 | }; |
| 353 | let mut coverage = self.coverage.clone(); |
| 354 | coverage.unresolved_candidates = self.candidates.len(); |
| 355 | Ok(MentionsPage { |
| 356 | entries, |
| 357 | next_cursor, |
| 358 | end_reached, |
| 359 | coverage, |
| 360 | unread_count: self.entries.values().filter(|entry| !entry.read).count(), |
| 361 | revision: self.revision, |
| 362 | boundary: MentionsBoundary { |
| 363 | account: account.clone(), |
| 364 | revision: boundary, |
| 365 | }, |
| 366 | }) |
| 367 | } |
| 368 | |
| 369 | pub fn context( |
| 370 | &self, |
| 371 | key: &MentionKey, |
| 372 | ) -> Result<(SavedMentionContext, Vec<MediaRegistration>), Error> { |
| 373 | let entry = self |
| 374 | .entries |
| 375 | .get(&id(key)) |
| 376 | .ok_or_else(|| Error::new(ErrorKind::EventNotFound, "mention was not found"))?; |
| 377 | let mut media = Vec::new(); |
| 378 | let mut item = |key: &String| { |
| 379 | self.events.get(key).map(|event| { |
| 380 | media.extend(event.media.clone()); |
| 381 | event.item.clone() |
| 382 | }) |
| 383 | }; |
| 384 | let context = self.windows.get(&id(key)).and_then(|window| { |
| 385 | let event = window.target.as_ref().and_then(&mut item)?; |
| 386 | Some(EventContext { |
| 387 | events_before: window.before.iter().filter_map(&mut item).collect(), |
| 388 | event, |
| 389 | events_after: window.after.iter().filter_map(&mut item).collect(), |
| 390 | start_token: window.start.clone(), |
| 391 | end_token: window.end.clone(), |
| 392 | }) |
| 393 | }); |
| 394 | Ok(( |
| 395 | SavedMentionContext { |
| 396 | key: key.clone(), |
| 397 | state: entry.capture.clone(), |
| 398 | context, |
| 399 | revision: self.revision, |
| 400 | }, |
| 401 | media, |
| 402 | )) |
| 403 | } |
| 404 | |
| 405 | pub fn collect_events(&mut self) -> usize { |
| 406 | let mut used: BTreeSet<String> = self.entries.keys().cloned().collect(); |
| 407 | for window in self.windows.values() { |
| 408 | used.extend(window.before.iter().chain(&window.after).cloned()); |
| 409 | used.extend(window.target.iter().cloned()); |
| 410 | } |
| 411 | let mut freed = 0; |
| 412 | self.events.retain(|key, event| { |
| 413 | let keep = used.contains(key); |
| 414 | if !keep { |
| 415 | freed += key.len() + json_len(event); |
| 416 | } |
| 417 | keep |
| 418 | }); |
| 419 | self.capture_attempts |
| 420 | .retain(|key, _| self.entries.contains_key(key)); |
| 421 | freed |
| 422 | } |
| 423 | |
| 424 | /// returns roughly how many plaintext JSON bytes the eviction freed |
| 425 | pub fn evict_one(&mut self) -> Option<usize> { |
| 426 | let oldest = |keys: Vec<String>, entries: &BTreeMap<String, MentionEntry>| { |
| 427 | keys.into_iter() |
| 428 | .min_by_key(|key| entries.get(key).map_or(0, |entry| entry.timestamp_ms)) |
| 429 | }; |
| 430 | let freed = if let Some(key) = oldest( |
| 431 | self.windows |
| 432 | .keys() |
| 433 | .filter(|key| self.entries.get(*key).is_some_and(|entry| entry.read)) |
| 434 | .cloned() |
| 435 | .collect(), |
| 436 | &self.entries, |
| 437 | ) |
| 438 | .or_else(|| oldest(self.windows.keys().cloned().collect(), &self.entries)) |
| 439 | { |
| 440 | let window = self.windows.remove(&key); |
| 441 | if let Some(entry) = self.entries.get_mut(&key) { |
| 442 | entry.capture = MentionCaptureState::Unavailable; |
| 443 | entry.revision = self.revision; |
| 444 | } |
| 445 | key.len() + json_len(&window) |
| 446 | } else if let Some(key) = self |
| 447 | .entries |
| 448 | .iter() |
| 449 | .min_by_key(|(_, entry)| (!entry.read, entry.timestamp_ms)) |
| 450 | .map(|(key, _)| key.clone()) |
| 451 | { |
| 452 | key.len() + json_len(&self.entries.remove(&key)) |
| 453 | } else if let Some(key) = self |
| 454 | .candidates |
| 455 | .iter() |
| 456 | .min_by_key(|(_, candidate)| timestamp(&candidate.raw)) |
| 457 | .map(|(key, _)| key.clone()) |
| 458 | { |
| 459 | key.len() + json_len(&self.candidates.remove(&key)) |
| 460 | } else if let Some(key) = self.edits.keys().next().cloned() { |
| 461 | key.len() + json_len(&self.edits.remove(&key)) |
| 462 | } else { |
| 463 | let key = self.redacted.keys().next().cloned()?; |
| 464 | self.redacted.remove(&key); |
| 465 | key.len() + 24 |
| 466 | }; |
| 467 | self.coverage.truncated = true; |
| 468 | Some(freed + self.collect_events()) |
| 469 | } |
| 470 | |
| 471 | pub fn bound(&mut self, entries: usize, events: usize, candidates: usize) { |
| 472 | while self.entries.len() > entries { |
| 473 | if let Some(key) = self |
| 474 | .entries |
| 475 | .iter() |
| 476 | .min_by_key(|(_, entry)| (!entry.read, entry.timestamp_ms)) |
| 477 | .map(|(key, _)| key.clone()) |
| 478 | { |
| 479 | self.entries.remove(&key); |
| 480 | self.windows.remove(&key); |
| 481 | self.coverage.truncated = true; |
| 482 | } |
| 483 | } |
| 484 | self.collect_events(); |
| 485 | while self.events.len() > events && self.evict_one().is_some() {} |
| 486 | if self.candidates.len() > candidates { |
| 487 | let mut oldest: Vec<_> = self |
| 488 | .candidates |
| 489 | .iter() |
| 490 | .map(|(key, candidate)| (timestamp(&candidate.raw), key.clone())) |
| 491 | .collect(); |
| 492 | oldest.sort(); |
| 493 | for (_, key) in oldest.into_iter().take(self.candidates.len() - candidates) { |
| 494 | self.candidates.remove(&key); |
| 495 | } |
| 496 | self.coverage.truncated = true; |
| 497 | } |
| 498 | for map in [&mut self.redacted] { |
| 499 | while map.len() > entries + candidates { |
| 500 | let key = map |
| 501 | .iter() |
| 502 | .min_by_key(|(_, timestamp)| *timestamp) |
| 503 | .map(|(key, _)| key.clone()) |
| 504 | .unwrap(); |
| 505 | map.remove(&key); |
| 506 | self.coverage.truncated = true; |
| 507 | } |
| 508 | } |
| 509 | while self.edits.len() > candidates { |
| 510 | let key = self.edits.keys().next().cloned().unwrap(); |
| 511 | self.edits.remove(&key); |
| 512 | self.coverage.truncated = true; |
| 513 | } |
| 514 | self.coverage.unresolved_candidates = self.candidates.len(); |
| 515 | } |
| 516 | } |