1use std::collections::{BTreeMap, BTreeSet, VecDeque};
41use std::sync::Arc;
42
43use schemars::JsonSchema;
44use serde::{Deserialize, Serialize};
45
46use crate::SemanticNode;
47
48#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize, JsonSchema)]
55#[serde(rename_all = "camelCase")]
56pub struct Dropped {
57 pub nodes_kept: usize,
58 pub nodes_present: usize,
59 pub bytes_kept: usize,
60 pub bytes_present: usize,
61}
62
63impl Dropped {
64 #[must_use]
66 pub fn node_ratio(&self) -> f64 {
67 ratio(self.nodes_kept, self.nodes_present)
68 }
69
70 #[must_use]
72 pub fn byte_ratio(&self) -> f64 {
73 ratio(self.bytes_kept, self.bytes_present)
74 }
75}
76
77fn ratio(kept: usize, present: usize) -> f64 {
78 if present == 0 {
79 1.0
80 } else {
81 kept as f64 / present as f64
82 }
83}
84
85#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, JsonSchema)]
87#[serde(rename_all = "camelCase")]
88pub struct Condensed<T> {
89 pub value: T,
90 pub dropped: Dropped,
91}
92
93#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, JsonSchema)]
95#[serde(rename_all = "camelCase")]
96pub struct RankedTerm {
97 pub term: String,
98 pub score: u32,
99}
100
101#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize, JsonSchema)]
103#[serde(rename_all = "camelCase")]
104pub struct PreviewNode {
105 pub id: u64,
106 pub role: String,
107 pub name: String,
108}
109
110#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize, JsonSchema)]
116#[serde(rename_all = "camelCase")]
117pub struct StructureNode {
118 pub id: u64,
119 pub role: String,
120 pub name: String,
121 pub children: Vec<StructureNode>,
122}
123
124#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, JsonSchema)]
130#[serde(rename_all = "camelCase")]
131pub struct CondensedPage {
132 pub keywords: Condensed<Vec<RankedTerm>>,
133 pub summary: Condensed<Vec<String>>,
134 pub preview: Condensed<Vec<PreviewNode>>,
135 pub structure: Condensed<Vec<StructureNode>>,
136 pub content: Condensed<String>,
137}
138
139#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, JsonSchema)]
149#[serde(tag = "level", content = "value", rename_all = "camelCase")]
150#[serde(rename_all_fields = "camelCase")]
151pub enum Condensation {
152 Keywords(Condensed<Vec<RankedTerm>>),
153 Summary(Condensed<Vec<String>>),
154 Preview(Condensed<Vec<PreviewNode>>),
155 Structure(Condensed<Vec<StructureNode>>),
156 Content(Condensed<String>),
157}
158
159impl Condensation {
160 #[must_use]
163 pub fn level_name(&self) -> &'static str {
164 match self {
165 Condensation::Keywords(_) => "keywords",
166 Condensation::Summary(_) => "summary",
167 Condensation::Preview(_) => "preview",
168 Condensation::Structure(_) => "structure",
169 Condensation::Content(_) => "content",
170 }
171 }
172}
173
174#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize, JsonSchema)]
177#[serde(rename_all = "camelCase")]
178pub struct CondenseOptions {
179 pub preview_nodes: usize,
180 pub summary_sentences: usize,
181 pub max_keywords: usize,
182}
183
184impl Default for CondenseOptions {
185 fn default() -> Self {
186 Self {
187 preview_nodes: 40,
188 summary_sentences: 4,
189 max_keywords: 24,
190 }
191 }
192}
193
194#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, Serialize, Deserialize, JsonSchema)]
197#[serde(rename_all = "camelCase")]
198pub enum Level {
199 #[default]
201 Keywords,
202 Summary,
204 Preview,
206 Structure,
208 Content,
210}
211
212impl Level {
213 #[must_use]
218 pub fn select(self, page: CondensedPage) -> Condensation {
219 match self {
220 Level::Keywords => Condensation::Keywords(page.keywords),
221 Level::Summary => Condensation::Summary(page.summary),
222 Level::Preview => Condensation::Preview(page.preview),
223 Level::Structure => Condensation::Structure(page.structure),
224 Level::Content => Condensation::Content(page.content),
225 }
226 }
227}
228
229const STOPLIST: &[&str] = &[
231 "the", "and", "for", "are", "but", "not", "you", "all", "any", "can", "her", "was", "one",
232 "our", "out", "day", "get", "has", "him", "his", "how", "its", "may", "new", "now", "old",
233 "see", "two", "way", "who", "boy", "did", "use", "that", "with", "this", "from", "they",
234 "will", "would", "there", "their", "what", "about", "which", "when", "make", "like", "time",
235 "just", "know", "take", "into", "your", "some", "them", "than", "then", "only", "come", "over",
236 "also", "back", "after", "could", "been", "have", "were", "more", "here", "does", "each",
237 "many", "most", "been", "such", "even", "much", "these", "those", "being", "where", "while",
238 "should", "because", "before", "between", "through", "during", "without",
239];
240
241fn role_weight(role: &str) -> u32 {
247 match role {
248 "h1" | "h2" | "h3" | "heading" | "title" => 5,
249 "h4" | "h5" | "h6" => 4,
250 "link" | "button" | "tab" | "menuitem" => 3,
251 "label" | "navigation" | "banner" | "main" | "article" | "table" | "listitem" => 2,
252 _ => 1,
253 }
254}
255
256fn words(text: &str) -> impl Iterator<Item = String> + '_ {
257 text.split(|c: char| !c.is_alphanumeric())
258 .filter(|word| word.len() >= 3)
259 .map(str::to_lowercase)
260 .filter(|word| !STOPLIST.contains(&word.as_str()))
261}
262
263fn visible_text(node: &SemanticNode) -> String {
264 match &node.value {
265 Some(value) if !value.is_empty() => format!("{} {}", node.name, value),
266 _ => node.name.clone(),
267 }
268}
269
270fn text_bytes(nodes: &[SemanticNode]) -> usize {
271 nodes
272 .iter()
273 .filter(|node| node.visible)
274 .map(|node| visible_text(node).len())
275 .sum()
276}
277
278fn ranked_terms(nodes: &[SemanticNode]) -> BTreeMap<String, u32> {
279 let mut scores: BTreeMap<String, u32> = BTreeMap::new();
280 for node in nodes.iter().filter(|node| node.visible) {
281 let weight = role_weight(&node.role);
282 for word in words(&visible_text(node)) {
283 *scores.entry(word).or_insert(0) += weight;
284 }
285 }
286 scores
287}
288
289#[must_use]
295pub fn keywords(nodes: &[SemanticNode]) -> Condensed<Vec<RankedTerm>> {
296 let scores = ranked_terms(nodes);
297 let present = text_bytes(nodes);
298 let contributing = nodes
299 .iter()
300 .filter(|node| node.visible && words(&visible_text(node)).next().is_some())
301 .count();
302 let mut terms: Vec<RankedTerm> = scores
303 .into_iter()
304 .map(|(term, score)| RankedTerm { term, score })
305 .collect();
306 terms.sort_by(|a, b| b.score.cmp(&a.score).then_with(|| a.term.cmp(&b.term)));
307 let kept = terms.iter().map(|term| term.term.len()).sum();
308 Condensed {
309 value: terms,
310 dropped: Dropped {
311 nodes_kept: contributing,
312 nodes_present: nodes.len(),
313 bytes_kept: kept,
314 bytes_present: present,
315 },
316 }
317}
318
319#[must_use]
326pub fn keyword_margin(target: &[RankedTerm], null: &[RankedTerm]) -> f64 {
327 if target.is_empty() {
328 return 0.0;
329 }
330 let null: BTreeSet<&str> = null.iter().map(|term| term.term.as_str()).collect();
331 let distinctive = target
332 .iter()
333 .filter(|term| !null.contains(term.term.as_str()))
334 .count();
335 distinctive as f64 / target.len() as f64
336}
337
338#[must_use]
345pub fn summary(nodes: &[SemanticNode], max_sentences: usize) -> Condensed<Vec<String>> {
346 let scores = ranked_terms(nodes);
347 let units: Vec<(usize, &SemanticNode)> = nodes
348 .iter()
349 .enumerate()
350 .filter(|(_, node)| node.visible && !visible_text(node).trim().is_empty())
351 .collect();
352 let mut scored: Vec<(usize, u32)> = units
353 .iter()
354 .map(|(index, node)| {
355 let score = words(&visible_text(node))
356 .filter_map(|word| scores.get(&word).copied())
357 .sum();
358 (*index, score)
359 })
360 .collect();
361 scored.sort_by(|a, b| b.1.cmp(&a.1).then_with(|| a.0.cmp(&b.0)));
362 let mut chosen: Vec<usize> = scored
363 .into_iter()
364 .take(max_sentences)
365 .map(|(index, _)| index)
366 .collect();
367 chosen.sort_unstable();
368 let sentences: Vec<String> = chosen
369 .into_iter()
370 .map(|index| visible_text(&nodes[index]).trim().to_string())
371 .collect();
372 let kept = sentences.iter().map(String::len).sum();
373 let kept_nodes = sentences.len();
374 Condensed {
375 value: sentences,
376 dropped: Dropped {
377 nodes_kept: kept_nodes,
378 nodes_present: nodes.len(),
379 bytes_kept: kept,
380 bytes_present: text_bytes(nodes),
381 },
382 }
383}
384
385#[must_use]
387pub fn preview(nodes: &[SemanticNode], limit: usize) -> Condensed<Vec<PreviewNode>> {
388 let kept: Vec<PreviewNode> = nodes
389 .iter()
390 .filter(|node| node.visible)
391 .take(limit)
392 .map(|node| PreviewNode {
393 id: node.id,
394 role: node.role.clone(),
395 name: node.name.clone(),
396 })
397 .collect();
398 let bytes = kept
399 .iter()
400 .map(|node| node.role.len() + node.name.len())
401 .sum();
402 Condensed {
403 value: kept,
404 dropped: Dropped {
405 nodes_kept: nodes.iter().filter(|node| node.visible).take(limit).count(),
406 nodes_present: nodes.len(),
407 bytes_kept: bytes,
408 bytes_present: text_bytes(nodes),
409 },
410 }
411}
412
413#[must_use]
415pub fn structure(nodes: &[SemanticNode]) -> Condensed<Vec<StructureNode>> {
416 let mut children: BTreeMap<u64, Vec<u64>> = BTreeMap::new();
417 let mut roots: Vec<u64> = Vec::new();
418 let known: BTreeSet<u64> = nodes.iter().map(|node| node.id).collect();
419 for node in nodes {
420 match node.parent {
421 Some(parent) if known.contains(&parent) => {
422 children.entry(parent).or_default().push(node.id);
423 }
424 _ => roots.push(node.id),
425 }
426 }
427 let by_id: BTreeMap<u64, &SemanticNode> = nodes.iter().map(|node| (node.id, node)).collect();
428 fn build(
429 id: u64,
430 by_id: &BTreeMap<u64, &SemanticNode>,
431 children: &BTreeMap<u64, Vec<u64>>,
432 ) -> StructureNode {
433 let node = by_id[&id];
434 StructureNode {
435 id,
436 role: node.role.clone(),
437 name: node.name.clone(),
438 children: children
439 .get(&id)
440 .map(|ids| {
441 ids.iter()
442 .map(|child| build(*child, by_id, children))
443 .collect()
444 })
445 .unwrap_or_default(),
446 }
447 }
448 let trees: Vec<StructureNode> = roots
449 .into_iter()
450 .map(|id| build(id, &by_id, &children))
451 .collect();
452 let kept = trees.iter().map(count_name).sum();
453 Condensed {
454 value: trees,
455 dropped: Dropped {
456 nodes_kept: nodes.len(),
457 nodes_present: nodes.len(),
458 bytes_kept: kept,
459 bytes_present: text_bytes(nodes),
460 },
461 }
462}
463
464fn count_name(node: &StructureNode) -> usize {
465 node.name.len() + node.children.iter().map(count_name).sum::<usize>()
466}
467
468#[must_use]
470pub fn content(nodes: &[SemanticNode]) -> Condensed<String> {
471 let text: Vec<String> = nodes
472 .iter()
473 .filter(|node| node.visible)
474 .map(visible_text)
475 .filter(|line| !line.trim().is_empty())
476 .collect();
477 let value = text.join("\n");
478 Condensed {
479 value,
480 dropped: Dropped {
481 nodes_kept: nodes.iter().filter(|node| node.visible).count(),
482 nodes_present: nodes.len(),
483 bytes_kept: text.iter().map(String::len).sum(),
484 bytes_present: text_bytes(nodes),
485 },
486 }
487}
488
489#[must_use]
491pub fn condense(nodes: &[SemanticNode], options: CondenseOptions) -> CondensedPage {
492 let mut keywords = keywords(nodes);
493 if keywords.value.len() > options.max_keywords {
494 keywords.value.truncate(options.max_keywords);
495 keywords.dropped.bytes_kept = keywords.value.iter().map(|term| term.term.len()).sum();
496 }
497 CondensedPage {
498 keywords,
499 summary: summary(nodes, options.summary_sentences),
500 preview: preview(nodes, options.preview_nodes),
501 structure: structure(nodes),
502 content: content(nodes),
503 }
504}
505
506#[derive(
512 Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize, JsonSchema,
513)]
514#[serde(rename_all = "camelCase")]
515pub struct SettleKey {
516 pub url: Option<String>,
517 pub revision: u64,
518}
519
520#[derive(Debug, Clone)]
527pub struct CondensationCache {
528 capacity: usize,
529 order: VecDeque<SettleKey>,
530 entries: BTreeMap<SettleKey, Arc<CondensedPage>>,
531}
532
533impl CondensationCache {
534 #[must_use]
535 pub fn new(capacity: usize) -> Self {
536 Self {
537 capacity: capacity.max(1),
538 order: VecDeque::new(),
539 entries: BTreeMap::new(),
540 }
541 }
542
543 #[must_use]
544 pub fn get(&self, key: &SettleKey) -> Option<Arc<CondensedPage>> {
545 self.entries.get(key).map(Arc::clone)
546 }
547
548 pub fn insert(
551 &mut self,
552 key: SettleKey,
553 page: Arc<CondensedPage>,
554 ) -> Option<(SettleKey, Arc<CondensedPage>)> {
555 if let Some(position) = self.order.iter().position(|existing| existing == &key) {
556 self.order.remove(position);
557 }
558 self.order.push_back(key.clone());
559 self.entries.insert(key, page);
560 if self.entries.len() <= self.capacity {
561 return None;
562 }
563 let evicted = self.order.pop_front()?;
564 let page = self.entries.remove(&evicted)?;
565 Some((evicted, page))
566 }
567
568 pub fn condense(
570 &mut self,
571 key: SettleKey,
572 nodes: &[SemanticNode],
573 options: CondenseOptions,
574 ) -> Arc<CondensedPage> {
575 let page = Arc::new(condense(nodes, options));
576 let _ = self.insert(key, Arc::clone(&page));
577 page
578 }
579
580 #[must_use]
581 pub fn len(&self) -> usize {
582 self.entries.len()
583 }
584
585 #[must_use]
586 pub fn is_empty(&self) -> bool {
587 self.entries.is_empty()
588 }
589}
590
591#[cfg(test)]
592mod tests {
593 use super::*;
594
595 fn node(id: u64, parent: Option<u64>, role: &str, name: &str) -> SemanticNode {
596 SemanticNode {
597 dom_id: None,
598 id,
599 parent,
600 role: role.to_string(),
601 name: name.to_string(),
602 value: None,
603 enabled: true,
604 focusable: false,
605 viewport_fixed: false,
606 visible: true,
607 selected: false,
608 bounds: None,
609 slot: None,
610 attributes: Default::default(),
611 }
612 }
613
614 fn page() -> Vec<SemanticNode> {
615 vec![
616 node(1, None, "h1", "Borrowing and ownership in Rust"),
617 node(
618 2,
619 Some(1),
620 "p",
621 "Ownership moves a value and borrowing lends it",
622 ),
623 node(3, Some(1), "h2", "Lifetimes"),
624 node(4, Some(3), "p", "Lifetimes bound how long a borrow lives"),
625 node(5, Some(1), "link", "Rustonomicon"),
626 ]
627 }
628
629 #[test]
630 fn keywords_rank_the_subject_above_the_chrome() {
631 let terms = keywords(&page());
632 let ranked: Vec<&str> = terms.value.iter().map(|term| term.term.as_str()).collect();
633 assert!(ranked.contains(&"borrowing"), "{ranked:?}");
634 assert!(ranked.contains(&"ownership"), "{ranked:?}");
635 assert!(!ranked.contains(&"and"), "stoplist ran");
636 assert!(terms.dropped.byte_ratio() < 1.0, "terms are not the page");
637 }
638
639 #[test]
640 fn a_summary_is_made_of_sentences_the_page_contains() {
641 let page = page();
642 let summary = summary(&page, 2);
643 assert_eq!(summary.value.len(), 2);
644 for sentence in &summary.value {
645 assert!(
646 page.iter().any(|node| node.name == *sentence),
647 "{sentence:?} is not on the page"
648 );
649 }
650 }
651
652 #[test]
653 fn a_preview_is_the_leading_nodes_and_says_how_many_it_dropped() {
654 let page = page();
655 let preview = preview(&page, 3);
656 assert_eq!(preview.value.len(), 3);
657 assert_eq!(preview.dropped.nodes_present, 5);
658 assert_eq!(preview.dropped.nodes_kept, 3);
659 }
660
661 #[test]
662 fn structure_keeps_the_tree_and_drops_the_bodies() {
663 let mut page = page();
664 page[1].value = Some(
665 "Ownership moves a value and borrowing lends it, which is a body a \
666 structure should not carry"
667 .to_string(),
668 );
669 let structure = structure(&page);
670 assert_eq!(structure.value.len(), 1, "one root");
671 assert_eq!(structure.dropped.node_ratio(), 1.0);
672 assert!(structure.dropped.byte_ratio() < 1.0, "bodies were dropped");
673 let root = &structure.value[0];
674 assert_eq!(root.role, "h1");
675 assert_eq!(root.children.len(), 3);
676 }
677
678 #[test]
679 fn content_is_the_escape_hatch_and_keeps_everything_visible() {
680 let content = content(&page());
681 assert!(content.value.contains("Borrowing"));
682 assert!(content.value.contains("Rustonomicon"));
683 assert_eq!(content.dropped.byte_ratio(), 1.0);
684 }
685
686 #[test]
687 fn the_null_margin_refuses_a_ranker_that_is_measuring_english() {
688 let target = keywords(&page());
689 let unrelated = keywords(&[node(1, None, "h1", "Weather and traffic in Osaka")]);
690 let margin = keyword_margin(&target.value, &unrelated.value);
691 assert!(
692 margin > 0.5,
693 "the pages should be mostly disjoint: {margin}"
694 );
695
696 assert_eq!(keyword_margin(&target.value, &target.value), 0.0);
698 }
699
700 #[test]
701 fn the_cache_is_keyed_on_settle_and_evicts_the_oldest() {
702 let mut cache = CondensationCache::new(1);
703 let one = SettleKey {
704 url: Some("https://example.test/".into()),
705 revision: 1,
706 };
707 let two = SettleKey {
708 url: Some("https://example.test/".into()),
709 revision: 2,
710 };
711 cache.condense(one.clone(), &page(), CondenseOptions::default());
712 assert!(cache.get(&one).is_some());
713 let evicted = cache.condense(two.clone(), &page(), CondenseOptions::default());
714 assert!(cache.get(&two).is_some());
715 assert!(cache.get(&one).is_none(), "same URL, different settle");
716 let _ = evicted;
718 assert_eq!(cache.len(), 1);
719 }
720
721 #[test]
722 fn reinserting_a_key_refreshes_rather_than_grows() {
723 let mut cache = CondensationCache::new(2);
724 let key = SettleKey {
725 url: None,
726 revision: 7,
727 };
728 cache.condense(key.clone(), &page(), CondenseOptions::default());
729 cache.condense(key.clone(), &page(), CondenseOptions::default());
730 assert_eq!(cache.len(), 1);
731 }
732}