macltok

public

Star0

Watch0

70 commits 3 branches 0 tags 0 releases3.0 MiB

use std::collections::{BTreeMap, BTreeSet};

use ruma::OwnedUserId;
use serde_json::Value;

use crate::{
    Error, ErrorKind, EventContext, MentionCaptureState, MentionCoverage, MentionEntry, MentionGap,
    MentionGapReason, MentionKey, MentionsBoundary, MentionsPage, SavedMentionContext,
    TimelineItem, normalise::MediaRegistration,
};

const CANDIDATE_LIFETIME_MS: u64 = 7 * 24 * 60 * 60 * 1000;

#[derive(Clone)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub(super) struct SavedEvent {
    pub item: TimelineItem,
    pub media: Vec<MediaRegistration>,
    pub raw: Option<Value>,
}

impl PartialEq for SavedEvent {
    fn eq(&self, other: &Self) -> bool {
        self.item == other.item
            && self.raw == other.raw
            && self
                .media
                .iter()
                .map(|media| &media.id)
                .eq(other.media.iter().map(|media| &media.id))
    }
}

#[derive(Clone, PartialEq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub(super) struct Candidate {
    pub room_id: ruma::OwnedRoomId,
    pub raw: Value,
    pub attempts: u32,
    pub retry_at_ms: u64,
    pub first_seen_ms: u64,
}

impl Candidate {
    pub fn new(room_id: ruma::OwnedRoomId, raw: Value, retry_at_ms: u64) -> Self {
        Self {
            room_id,
            raw,
            attempts: 0,
            retry_at_ms,
            first_seen_ms: now(),
        }
    }

    pub fn encrypted(&self) -> bool {
        self.raw["type"] == "m.room.encrypted"
    }
}

#[derive(Clone, PartialEq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub(super) struct Window {
    pub before: Vec<String>,
    pub target: Option<String>,
    pub after: Vec<String>,
    pub start: Option<String>,
    pub end: Option<String>,
}

#[derive(Clone, Default, PartialEq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub(super) struct Data {
    pub revision: u64,
    pub entries: BTreeMap<String, MentionEntry>,
    pub events: BTreeMap<String, SavedEvent>,
    pub windows: BTreeMap<String, Window>,
    pub capture_attempts: BTreeMap<String, u32>,
    pub candidates: BTreeMap<String, Candidate>,
    pub redacted: BTreeMap<String, u64>,
    pub edits: BTreeMap<String, Value>,
    pub coverage: MentionCoverage,
    pub history_cursor: Option<String>,
    pub history_exhausted: bool,
    pub latest_cursor: Option<String>,
    pub latest_anchor: Option<String>,
    pub latest_head: Option<String>,
}

#[derive(Clone, Default, PartialEq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub(super) struct SyncState {
    pub inbox_revision: u64,
    pub checkpoints: BTreeMap<String, Checkpoint>,
    pub observed_rooms: BTreeSet<ruma::OwnedRoomId>,
}

#[derive(Clone, Debug, PartialEq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub(super) struct Checkpoint {
    pub pos: String,
    pub previous: Option<String>,
}

pub(super) fn id(key: &MentionKey) -> String {
    format!("{}\n{}", key.room_id, key.event_id)
}

pub(super) fn now() -> u64 {
    matrix_sdk::ruma::MilliSecondsSinceUnixEpoch::now()
        .get()
        .into()
}

pub(super) fn invalid(message: &'static str) -> Error {
    Error::new(ErrorKind::Invalid, message)
}

#[cfg(feature = "serde")]
pub(super) fn json_len(value: &impl serde::Serialize) -> usize {
    struct Count(usize);
    impl std::io::Write for Count {
        fn write(&mut self, bytes: &[u8]) -> std::io::Result<usize> {
            self.0 += bytes.len();
            Ok(bytes.len())
        }
        fn flush(&mut self) -> std::io::Result<()> {
            Ok(())
        }
    }
    let mut count = Count(0);
    let _ = serde_json::to_writer(&mut count, value);
    count.0
}

#[cfg(not(feature = "serde"))]
pub(super) fn json_len<T>(_: &T) -> usize {
    0
}

fn timestamp(value: &Value) -> u64 {
    value["origin_server_ts"].as_u64().unwrap_or(0)
}

impl Data {
    pub fn gap(
        &mut self,
        room_id: Option<ruma::OwnedRoomId>,
        reason: MentionGapReason,
        token: Option<String>,
    ) {
        if self
            .coverage
            .gaps
            .iter()
            .any(|gap| gap.room_id == room_id && gap.reason == reason && gap.token == token)
        {
            return;
        }
        self.coverage.gaps.push(MentionGap {
            room_id,
            reason,
            token,
        });
        if self.coverage.gaps.len() > 128 {
            self.coverage.gaps.remove(0);
            self.coverage.truncated = true;
        }
    }

    pub fn expire_candidates(&mut self, now_ms: u64) -> bool {
        let expired: Vec<_> = self
            .candidates
            .iter()
            .filter(|(_, candidate)| {
                now_ms.saturating_sub(candidate.first_seen_ms) > CANDIDATE_LIFETIME_MS
            })
            .map(|(key, candidate)| (key.clone(), candidate.room_id.clone()))
            .collect();
        for (key, room_id) in &expired {
            self.candidates.remove(key);
            self.gap(
                Some(room_id.clone()),
                MentionGapReason::CandidateExpired,
                None,
            );
        }
        !expired.is_empty()
    }

    pub fn touch_contexts(&mut self, identity: &str) {
        for (key, window) in &self.windows {
            if window.target.as_deref() == Some(identity)
                || window
                    .before
                    .iter()
                    .chain(&window.after)
                    .any(|key| key == identity)
            {
                if let Some(entry) = self.entries.get_mut(key) {
                    entry.revision = self.revision + 1;
                }
            }
        }
    }

    pub fn page(
        &self,
        account: &OwnedUserId,
        cursor: Option<&str>,
        limit: u16,
    ) -> Result<MentionsPage, Error> {
        let (boundary, last) = if let Some(cursor) = cursor {
            let value: Value =
                serde_json::from_str(cursor).map_err(|_| invalid("invalid mentions cursor"))?;
            if value["account"].as_str() != Some(account.as_str()) {
                return Err(invalid("mentions cursor belongs to a different account"));
            }
            let boundary = value["revision"]
                .as_u64()
                .ok_or_else(|| invalid("invalid mentions cursor"))?;
            let timestamp = value["timestamp"]
                .as_u64()
                .ok_or_else(|| invalid("invalid mentions cursor"))?;
            let key = value["key"]
                .as_str()
                .ok_or_else(|| invalid("invalid mentions cursor"))?
                .to_owned();
            if boundary > self.revision {
                return Err(invalid("mentions cursor is newer than this store"));
            }
            (boundary, Some((timestamp, key)))
        } else {
            (self.revision, None)
        };
        let mut entries: Vec<_> = self
            .entries
            .iter()
            .filter(|(key, entry)| {
                entry.discovery_revision <= boundary
                    && last.as_ref().is_none_or(|last| {
                        (entry.timestamp_ms, key.as_str()) < (last.0, last.1.as_str())
                    })
            })
            .map(|(_, entry)| entry.clone())
            .collect();
        entries.sort_by(|a, b| (b.timestamp_ms, id(&b.key)).cmp(&(a.timestamp_ms, id(&a.key))));
        let limit = usize::from(limit.clamp(1, 50));
        let end_reached = entries.len() <= limit;
        entries.truncate(limit);
        let next_cursor = if end_reached {
            None
        } else {
            entries.last().map(|entry| serde_json::json!({
            "account": account.as_str(), "revision": boundary, "timestamp": entry.timestamp_ms, "key": id(&entry.key)
        }).to_string())
        };
        let mut coverage = self.coverage.clone();
        coverage.unresolved_candidates = self.candidates.len();
        Ok(MentionsPage {
            entries,
            next_cursor,
            end_reached,
            coverage,
            unread_count: self.entries.values().filter(|entry| !entry.read).count(),
            revision: self.revision,
            boundary: MentionsBoundary {
                account: account.clone(),
                revision: boundary,
            },
        })
    }

    pub fn context(
        &self,
        key: &MentionKey,
    ) -> Result<(SavedMentionContext, Vec<MediaRegistration>), Error> {
        let entry = self
            .entries
            .get(&id(key))
            .ok_or_else(|| Error::new(ErrorKind::EventNotFound, "mention was not found"))?;
        let mut media = Vec::new();
        let mut item = |key: &String| {
            self.events.get(key).map(|event| {
                media.extend(event.media.clone());
                event.item.clone()
            })
        };
        let context = self.windows.get(&id(key)).and_then(|window| {
            let event = window.target.as_ref().and_then(&mut item)?;
            Some(EventContext {
                events_before: window.before.iter().filter_map(&mut item).collect(),
                event,
                events_after: window.after.iter().filter_map(&mut item).collect(),
                start_token: window.start.clone(),
                end_token: window.end.clone(),
            })
        });
        Ok((
            SavedMentionContext {
                key: key.clone(),
                state: entry.capture.clone(),
                context,
                revision: self.revision,
            },
            media,
        ))
    }

    pub fn collect_events(&mut self) -> usize {
        let mut used: BTreeSet<String> = self.entries.keys().cloned().collect();
        for window in self.windows.values() {
            used.extend(window.before.iter().chain(&window.after).cloned());
            used.extend(window.target.iter().cloned());
        }
        let mut freed = 0;
        self.events.retain(|key, event| {
            let keep = used.contains(key);
            if !keep {
                freed += key.len() + json_len(event);
            }
            keep
        });
        self.capture_attempts
            .retain(|key, _| self.entries.contains_key(key));
        freed
    }

    /// returns roughly how many plaintext JSON bytes the eviction freed
    pub fn evict_one(&mut self) -> Option<usize> {
        let oldest = |keys: Vec<String>, entries: &BTreeMap<String, MentionEntry>| {
            keys.into_iter()
                .min_by_key(|key| entries.get(key).map_or(0, |entry| entry.timestamp_ms))
        };
        let freed = if let Some(key) = oldest(
            self.windows
                .keys()
                .filter(|key| self.entries.get(*key).is_some_and(|entry| entry.read))
                .cloned()
                .collect(),
            &self.entries,
        )
        .or_else(|| oldest(self.windows.keys().cloned().collect(), &self.entries))
        {
            let window = self.windows.remove(&key);
            if let Some(entry) = self.entries.get_mut(&key) {
                entry.capture = MentionCaptureState::Unavailable;
                entry.revision = self.revision;
            }
            key.len() + json_len(&window)
        } else if let Some(key) = self
            .entries
            .iter()
            .min_by_key(|(_, entry)| (!entry.read, entry.timestamp_ms))
            .map(|(key, _)| key.clone())
        {
            key.len() + json_len(&self.entries.remove(&key))
        } else if let Some(key) = self
            .candidates
            .iter()
            .min_by_key(|(_, candidate)| timestamp(&candidate.raw))
            .map(|(key, _)| key.clone())
        {
            key.len() + json_len(&self.candidates.remove(&key))
        } else if let Some(key) = self.edits.keys().next().cloned() {
            key.len() + json_len(&self.edits.remove(&key))
        } else {
            let key = self.redacted.keys().next().cloned()?;
            self.redacted.remove(&key);
            key.len() + 24
        };
        self.coverage.truncated = true;
        Some(freed + self.collect_events())
    }

    pub fn bound(&mut self, entries: usize, events: usize, candidates: usize) {
        while self.entries.len() > entries {
            if let Some(key) = self
                .entries
                .iter()
                .min_by_key(|(_, entry)| (!entry.read, entry.timestamp_ms))
                .map(|(key, _)| key.clone())
            {
                self.entries.remove(&key);
                self.windows.remove(&key);
                self.coverage.truncated = true;
            }
        }
        self.collect_events();
        while self.events.len() > events && self.evict_one().is_some() {}
        if self.candidates.len() > candidates {
            let mut oldest: Vec<_> = self
                .candidates
                .iter()
                .map(|(key, candidate)| (timestamp(&candidate.raw), key.clone()))
                .collect();
            oldest.sort();
            for (_, key) in oldest.into_iter().take(self.candidates.len() - candidates) {
                self.candidates.remove(&key);
            }
            self.coverage.truncated = true;
        }
        for map in [&mut self.redacted] {
            while map.len() > entries + candidates {
                let key = map
                    .iter()
                    .min_by_key(|(_, timestamp)| *timestamp)
                    .map(|(key, _)| key.clone())
                    .unwrap();
                map.remove(&key);
                self.coverage.truncated = true;
            }
        }
        while self.edits.len() > candidates {
            let key = self.edits.keys().next().cloned().unwrap();
            self.edits.remove(&key);
            self.coverage.truncated = true;
        }
        self.coverage.unresolved_candidates = self.candidates.len();
    }
}

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	pub observed_rooms: BTreeSet<ruma::OwnedRoomId>,
95	}
96
97	#[derive(Clone, Debug, PartialEq)]
98	#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
99	pub(super) struct Checkpoint {
100	pub pos: String,
101	pub previous: Option<String>,
102	}
103
104	pub(super) fn id(key: &MentionKey) -> String {
105	format!("{}\n{}", key.room_id, key.event_id)
106	}
107
108	pub(super) fn now() -> u64 {
109	matrix_sdk::ruma::MilliSecondsSinceUnixEpoch::now()
110	.get()
111	.into()
112	}
113
114	pub(super) fn invalid(message: &'static str) -> Error {
115	Error::new(ErrorKind::Invalid, message)
116	}
117
118	#[cfg(feature = "serde")]
119	pub(super) fn json_len(value: &impl serde::Serialize) -> usize {
120	struct Count(usize);
121	impl std::io::Write for Count {
122	fn write(&mut self, bytes: &[u8]) -> std::io::Result<usize> {
123	self.0 += bytes.len();
124	Ok(bytes.len())
125	}
126	fn flush(&mut self) -> std::io::Result<()> {
127	Ok(())
128	}
129	}
130	let mut count = Count(0);
131	let _ = serde_json::to_writer(&mut count, value);
132	count.0
133	}
134
135	#[cfg(not(feature = "serde"))]
136	pub(super) fn json_len<T>(_: &T) -> usize {
137	0
138	}
139
140	fn timestamp(value: &Value) -> u64 {
141	value["origin_server_ts"].as_u64().unwrap_or(0)
142	}
143
144	impl Data {
145	pub fn gap(
146	&mut self,
147	room_id: Option<ruma::OwnedRoomId>,
148	reason: MentionGapReason,
149	token: Option<String>,
150	) {
151	if self
152	.coverage
153	.gaps
154	.iter()
155	.any(\|gap\| gap.room_id == room_id && gap.reason == reason && gap.token == token)
156	{
157	return;
158	}
159	self.coverage.gaps.push(MentionGap {
160	room_id,
161	reason,
162	token,
163	});
164	if self.coverage.gaps.len() > 128 {
165	self.coverage.gaps.remove(0);
166	self.coverage.truncated = true;
167	}
168	}
169
170	pub fn expire_candidates(&mut self, now_ms: u64) -> bool {
171	let expired: Vec<_> = self
172	.candidates
173	.iter()
174	.filter(\|(_, candidate)\| {
175	now_ms.saturating_sub(candidate.first_seen_ms) > CANDIDATE_LIFETIME_MS
176	})
177	.map(\|(key, candidate)\| (key.clone(), candidate.room_id.clone()))
178	.collect();
179	for (key, room_id) in &expired {
180	self.candidates.remove(key);
181	self.gap(
182	Some(room_id.clone()),
183	MentionGapReason::CandidateExpired,
184	None,
185	);
186	}
187	!expired.is_empty()
188	}
189
190	pub fn touch_contexts(&mut self, identity: &str) {
191	for (key, window) in &self.windows {
192	if window.target.as_deref() == Some(identity)
193	\|\| window
194	.before
195	.iter()
196	.chain(&window.after)
197	.any(\|key\| key == identity)
198	{
199	if let Some(entry) = self.entries.get_mut(key) {
200	entry.revision = self.revision + 1;
201	}
202	}
203	}
204	}
205
206	pub fn page(
207	&self,
208	account: &OwnedUserId,
209	cursor: Option<&str>,
210	limit: u16,
211	) -> Result<MentionsPage, Error> {
212	let (boundary, last) = if let Some(cursor) = cursor {
213	let value: Value =
214	serde_json::from_str(cursor).map_err(\|_\| invalid("invalid mentions cursor"))?;
215	if value["account"].as_str() != Some(account.as_str()) {
216	return Err(invalid("mentions cursor belongs to a different account"));
217	}
218	let boundary = value["revision"]
219	.as_u64()
220	.ok_or_else(\|\| invalid("invalid mentions cursor"))?;
221	let timestamp = value["timestamp"]
222	.as_u64()
223	.ok_or_else(\|\| invalid("invalid mentions cursor"))?;
224	let key = value["key"]
225	.as_str()
226	.ok_or_else(\|\| invalid("invalid mentions cursor"))?
227	.to_owned();
228	if boundary > self.revision {
229	return Err(invalid("mentions cursor is newer than this store"));
230	}
231	(boundary, Some((timestamp, key)))
232	} else {
233	(self.revision, None)
234	};
235	let mut entries: Vec<_> = self
236	.entries
237	.iter()
238	.filter(\|(key, entry)\| {
239	entry.discovery_revision <= boundary
240	&& last.as_ref().is_none_or(\|last\| {
241	(entry.timestamp_ms, key.as_str()) < (last.0, last.1.as_str())
242	})
243	})
244	.map(\|(_, entry)\| entry.clone())
245	.collect();
246	entries.sort_by(\|a, b\| (b.timestamp_ms, id(&b.key)).cmp(&(a.timestamp_ms, id(&a.key))));
247	let limit = usize::from(limit.clamp(1, 50));
248	let end_reached = entries.len() <= limit;
249	entries.truncate(limit);
250	let next_cursor = if end_reached {
251	None
252	} else {
253	entries.last().map(\|entry\| serde_json::json!({
254	"account": account.as_str(), "revision": boundary, "timestamp": entry.timestamp_ms, "key": id(&entry.key)
255	}).to_string())
256	};
257	let mut coverage = self.coverage.clone();
258	coverage.unresolved_candidates = self.candidates.len();
259	Ok(MentionsPage {
260	entries,
261	next_cursor,
262	end_reached,
263	coverage,
264	unread_count: self.entries.values().filter(\|entry\| !entry.read).count(),
265	revision: self.revision,
266	boundary: MentionsBoundary {
267	account: account.clone(),
268	revision: boundary,
269	},
270	})
271	}
272
273	pub fn context(
274	&self,
275	key: &MentionKey,
276	) -> Result<(SavedMentionContext, Vec<MediaRegistration>), Error> {
277	let entry = self
278	.entries
279	.get(&id(key))
280	.ok_or_else(\|\| Error::new(ErrorKind::EventNotFound, "mention was not found"))?;
281	let mut media = Vec::new();
282	let mut item = \|key: &String\| {
283	self.events.get(key).map(\|event\| {
284	media.extend(event.media.clone());
285	event.item.clone()
286	})
287	};
288	let context = self.windows.get(&id(key)).and_then(\|window\| {
289	let event = window.target.as_ref().and_then(&mut item)?;
290	Some(EventContext {
291	events_before: window.before.iter().filter_map(&mut item).collect(),
292	event,
293	events_after: window.after.iter().filter_map(&mut item).collect(),
294	start_token: window.start.clone(),
295	end_token: window.end.clone(),
296	})
297	});
298	Ok((
299	SavedMentionContext {
300	key: key.clone(),
301	state: entry.capture.clone(),
302	context,
303	revision: self.revision,
304	},
305	media,
306	))
307	}
308
309	pub fn collect_events(&mut self) -> usize {
310	let mut used: BTreeSet<String> = self.entries.keys().cloned().collect();
311	for window in self.windows.values() {
312	used.extend(window.before.iter().chain(&window.after).cloned());
313	used.extend(window.target.iter().cloned());
314	}
315	let mut freed = 0;
316	self.events.retain(\|key, event\| {
317	let keep = used.contains(key);
318	if !keep {
319	freed += key.len() + json_len(event);
320	}
321	keep
322	});
323	self.capture_attempts
324	.retain(\|key, _\| self.entries.contains_key(key));
325	freed
326	}
327
328	/// returns roughly how many plaintext JSON bytes the eviction freed
329	pub fn evict_one(&mut self) -> Option<usize> {
330	let oldest = \|keys: Vec<String>, entries: &BTreeMap<String, MentionEntry>\| {
331	keys.into_iter()
332	.min_by_key(\|key\| entries.get(key).map_or(0, \|entry\| entry.timestamp_ms))
333	};
334	let freed = if let Some(key) = oldest(
335	self.windows
336	.keys()
337	.filter(\|key\| self.entries.get(*key).is_some_and(\|entry\| entry.read))
338	.cloned()
339	.collect(),
340	&self.entries,
341	)
342	.or_else(\|\| oldest(self.windows.keys().cloned().collect(), &self.entries))
343	{
344	let window = self.windows.remove(&key);
345	if let Some(entry) = self.entries.get_mut(&key) {
346	entry.capture = MentionCaptureState::Unavailable;
347	entry.revision = self.revision;
348	}
349	key.len() + json_len(&window)
350	} else if let Some(key) = self
351	.entries
352	.iter()
353	.min_by_key(\|(_, entry)\| (!entry.read, entry.timestamp_ms))
354	.map(\|(key, _)\| key.clone())
355	{
356	key.len() + json_len(&self.entries.remove(&key))
357	} else if let Some(key) = self
358	.candidates
359	.iter()
360	.min_by_key(\|(_, candidate)\| timestamp(&candidate.raw))
361	.map(\|(key, _)\| key.clone())
362	{
363	key.len() + json_len(&self.candidates.remove(&key))
364	} else if let Some(key) = self.edits.keys().next().cloned() {
365	key.len() + json_len(&self.edits.remove(&key))
366	} else {
367	let key = self.redacted.keys().next().cloned()?;
368	self.redacted.remove(&key);
369	key.len() + 24
370	};
371	self.coverage.truncated = true;
372	Some(freed + self.collect_events())
373	}
374
375	pub fn bound(&mut self, entries: usize, events: usize, candidates: usize) {
376	while self.entries.len() > entries {
377	if let Some(key) = self
378	.entries
379	.iter()
380	.min_by_key(\|(_, entry)\| (!entry.read, entry.timestamp_ms))
381	.map(\|(key, _)\| key.clone())
382	{
383	self.entries.remove(&key);
384	self.windows.remove(&key);
385	self.coverage.truncated = true;
386	}
387	}
388	self.collect_events();
389	while self.events.len() > events && self.evict_one().is_some() {}
390	if self.candidates.len() > candidates {
391	let mut oldest: Vec<_> = self
392	.candidates
393	.iter()
394	.map(\|(key, candidate)\| (timestamp(&candidate.raw), key.clone()))
395	.collect();
396	oldest.sort();
397	for (_, key) in oldest.into_iter().take(self.candidates.len() - candidates) {
398	self.candidates.remove(&key);
399	}
400	self.coverage.truncated = true;
401	}
402	for map in [&mut self.redacted] {
403	while map.len() > entries + candidates {
404	let key = map
405	.iter()
406	.min_by_key(\|(_, timestamp)\| *timestamp)
407	.map(\|(key, _)\| key.clone())
408	.unwrap();
409	map.remove(&key);
410	self.coverage.truncated = true;
411	}
412	}
413	while self.edits.len() > candidates {
414	let key = self.edits.keys().next().cloned().unwrap();
415	self.edits.remove(&key);
416	self.coverage.truncated = true;
417	}
418	self.coverage.unresolved_candidates = self.candidates.len();
419	}
420	}