use std::collections::{BTreeMap, BTreeSet, VecDeque};
use std::sync::Arc;
use schemars::JsonSchema;
use serde::{Deserialize, Serialize};
use crate::SemanticNode;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize, JsonSchema)]
#[serde(rename_all = "camelCase")]
pub struct Dropped {
pub nodes_kept: usize,
pub nodes_present: usize,
pub bytes_kept: usize,
pub bytes_present: usize,
}
impl Dropped {
#[must_use]
pub fn node_ratio(&self) -> f64 {
ratio(self.nodes_kept, self.nodes_present)
}
#[must_use]
pub fn byte_ratio(&self) -> f64 {
ratio(self.bytes_kept, self.bytes_present)
}
}
fn ratio(kept: usize, present: usize) -> f64 {
if present == 0 {
1.0
} else {
kept as f64 / present as f64
}
}
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, JsonSchema)]
#[serde(rename_all = "camelCase")]
pub struct Condensed<T> {
pub value: T,
pub dropped: Dropped,
}
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, JsonSchema)]
#[serde(rename_all = "camelCase")]
pub struct RankedTerm {
pub term: String,
pub score: u32,
}
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize, JsonSchema)]
#[serde(rename_all = "camelCase")]
pub struct PreviewNode {
pub id: u64,
pub role: String,
pub name: String,
}
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize, JsonSchema)]
#[serde(rename_all = "camelCase")]
pub struct StructureNode {
pub id: u64,
pub role: String,
pub name: String,
pub children: Vec<StructureNode>,
}
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, JsonSchema)]
#[serde(rename_all = "camelCase")]
pub struct CondensedPage {
pub keywords: Condensed<Vec<RankedTerm>>,
pub summary: Condensed<Vec<String>>,
pub preview: Condensed<Vec<PreviewNode>>,
pub structure: Condensed<Vec<StructureNode>>,
pub content: Condensed<String>,
}
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, JsonSchema)]
#[serde(tag = "level", content = "value", rename_all = "camelCase")]
#[serde(rename_all_fields = "camelCase")]
pub enum Condensation {
Keywords(Condensed<Vec<RankedTerm>>),
Summary(Condensed<Vec<String>>),
Preview(Condensed<Vec<PreviewNode>>),
Structure(Condensed<Vec<StructureNode>>),
Content(Condensed<String>),
}
impl Condensation {
#[must_use]
pub fn level_name(&self) -> &'static str {
match self {
Condensation::Keywords(_) => "keywords",
Condensation::Summary(_) => "summary",
Condensation::Preview(_) => "preview",
Condensation::Structure(_) => "structure",
Condensation::Content(_) => "content",
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize, JsonSchema)]
#[serde(rename_all = "camelCase")]
pub struct CondenseOptions {
pub preview_nodes: usize,
pub summary_sentences: usize,
pub max_keywords: usize,
}
impl Default for CondenseOptions {
fn default() -> Self {
Self {
preview_nodes: 40,
summary_sentences: 4,
max_keywords: 24,
}
}
}
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, Serialize, Deserialize, JsonSchema)]
#[serde(rename_all = "camelCase")]
pub enum Level {
#[default]
Keywords,
Summary,
Preview,
Structure,
Content,
}
impl Level {
#[must_use]
pub fn select(self, page: CondensedPage) -> Condensation {
match self {
Level::Keywords => Condensation::Keywords(page.keywords),
Level::Summary => Condensation::Summary(page.summary),
Level::Preview => Condensation::Preview(page.preview),
Level::Structure => Condensation::Structure(page.structure),
Level::Content => Condensation::Content(page.content),
}
}
}
const STOPLIST: &[&str] = &[
"the", "and", "for", "are", "but", "not", "you", "all", "any", "can", "her", "was", "one",
"our", "out", "day", "get", "has", "him", "his", "how", "its", "may", "new", "now", "old",
"see", "two", "way", "who", "boy", "did", "use", "that", "with", "this", "from", "they",
"will", "would", "there", "their", "what", "about", "which", "when", "make", "like", "time",
"just", "know", "take", "into", "your", "some", "them", "than", "then", "only", "come", "over",
"also", "back", "after", "could", "been", "have", "were", "more", "here", "does", "each",
"many", "most", "been", "such", "even", "much", "these", "those", "being", "where", "while",
"should", "because", "before", "between", "through", "during", "without",
];
fn role_weight(role: &str) -> u32 {
match role {
"h1" | "h2" | "h3" | "heading" | "title" => 5,
"h4" | "h5" | "h6" => 4,
"link" | "button" | "tab" | "menuitem" => 3,
"label" | "navigation" | "banner" | "main" | "article" | "table" | "listitem" => 2,
_ => 1,
}
}
fn words(text: &str) -> impl Iterator<Item = String> + '_ {
text.split(|c: char| !c.is_alphanumeric())
.filter(|word| word.len() >= 3)
.map(str::to_lowercase)
.filter(|word| !STOPLIST.contains(&word.as_str()))
}
fn visible_text(node: &SemanticNode) -> String {
match &node.value {
Some(value) if !value.is_empty() => format!("{} {}", node.name, value),
_ => node.name.clone(),
}
}
fn text_bytes(nodes: &[SemanticNode]) -> usize {
nodes
.iter()
.filter(|node| node.visible)
.map(|node| visible_text(node).len())
.sum()
}
fn ranked_terms(nodes: &[SemanticNode]) -> BTreeMap<String, u32> {
let mut scores: BTreeMap<String, u32> = BTreeMap::new();
for node in nodes.iter().filter(|node| node.visible) {
let weight = role_weight(&node.role);
for word in words(&visible_text(node)) {
*scores.entry(word).or_insert(0) += weight;
}
}
scores
}
#[must_use]
pub fn keywords(nodes: &[SemanticNode]) -> Condensed<Vec<RankedTerm>> {
let scores = ranked_terms(nodes);
let present = text_bytes(nodes);
let contributing = nodes
.iter()
.filter(|node| node.visible && words(&visible_text(node)).next().is_some())
.count();
let mut terms: Vec<RankedTerm> = scores
.into_iter()
.map(|(term, score)| RankedTerm { term, score })
.collect();
terms.sort_by(|a, b| b.score.cmp(&a.score).then_with(|| a.term.cmp(&b.term)));
let kept = terms.iter().map(|term| term.term.len()).sum();
Condensed {
value: terms,
dropped: Dropped {
nodes_kept: contributing,
nodes_present: nodes.len(),
bytes_kept: kept,
bytes_present: present,
},
}
}
#[must_use]
pub fn keyword_margin(target: &[RankedTerm], null: &[RankedTerm]) -> f64 {
if target.is_empty() {
return 0.0;
}
let null: BTreeSet<&str> = null.iter().map(|term| term.term.as_str()).collect();
let distinctive = target
.iter()
.filter(|term| !null.contains(term.term.as_str()))
.count();
distinctive as f64 / target.len() as f64
}
#[must_use]
pub fn summary(nodes: &[SemanticNode], max_sentences: usize) -> Condensed<Vec<String>> {
let scores = ranked_terms(nodes);
let units: Vec<(usize, &SemanticNode)> = nodes
.iter()
.enumerate()
.filter(|(_, node)| node.visible && !visible_text(node).trim().is_empty())
.collect();
let mut scored: Vec<(usize, u32)> = units
.iter()
.map(|(index, node)| {
let score = words(&visible_text(node))
.filter_map(|word| scores.get(&word).copied())
.sum();
(*index, score)
})
.collect();
scored.sort_by(|a, b| b.1.cmp(&a.1).then_with(|| a.0.cmp(&b.0)));
let mut chosen: Vec<usize> = scored
.into_iter()
.take(max_sentences)
.map(|(index, _)| index)
.collect();
chosen.sort_unstable();
let sentences: Vec<String> = chosen
.into_iter()
.map(|index| visible_text(&nodes[index]).trim().to_string())
.collect();
let kept = sentences.iter().map(String::len).sum();
let kept_nodes = sentences.len();
Condensed {
value: sentences,
dropped: Dropped {
nodes_kept: kept_nodes,
nodes_present: nodes.len(),
bytes_kept: kept,
bytes_present: text_bytes(nodes),
},
}
}
#[must_use]
pub fn preview(nodes: &[SemanticNode], limit: usize) -> Condensed<Vec<PreviewNode>> {
let kept: Vec<PreviewNode> = nodes
.iter()
.filter(|node| node.visible)
.take(limit)
.map(|node| PreviewNode {
id: node.id,
role: node.role.clone(),
name: node.name.clone(),
})
.collect();
let bytes = kept
.iter()
.map(|node| node.role.len() + node.name.len())
.sum();
Condensed {
value: kept,
dropped: Dropped {
nodes_kept: nodes.iter().filter(|node| node.visible).take(limit).count(),
nodes_present: nodes.len(),
bytes_kept: bytes,
bytes_present: text_bytes(nodes),
},
}
}
#[must_use]
pub fn structure(nodes: &[SemanticNode]) -> Condensed<Vec<StructureNode>> {
let mut children: BTreeMap<u64, Vec<u64>> = BTreeMap::new();
let mut roots: Vec<u64> = Vec::new();
let known: BTreeSet<u64> = nodes.iter().map(|node| node.id).collect();
for node in nodes {
match node.parent {
Some(parent) if known.contains(&parent) => {
children.entry(parent).or_default().push(node.id);
}
_ => roots.push(node.id),
}
}
let by_id: BTreeMap<u64, &SemanticNode> = nodes.iter().map(|node| (node.id, node)).collect();
fn build(
id: u64,
by_id: &BTreeMap<u64, &SemanticNode>,
children: &BTreeMap<u64, Vec<u64>>,
) -> StructureNode {
let node = by_id[&id];
StructureNode {
id,
role: node.role.clone(),
name: node.name.clone(),
children: children
.get(&id)
.map(|ids| {
ids.iter()
.map(|child| build(*child, by_id, children))
.collect()
})
.unwrap_or_default(),
}
}
let trees: Vec<StructureNode> = roots
.into_iter()
.map(|id| build(id, &by_id, &children))
.collect();
let kept = trees.iter().map(count_name).sum();
Condensed {
value: trees,
dropped: Dropped {
nodes_kept: nodes.len(),
nodes_present: nodes.len(),
bytes_kept: kept,
bytes_present: text_bytes(nodes),
},
}
}
fn count_name(node: &StructureNode) -> usize {
node.name.len() + node.children.iter().map(count_name).sum::<usize>()
}
#[must_use]
pub fn content(nodes: &[SemanticNode]) -> Condensed<String> {
let text: Vec<String> = nodes
.iter()
.filter(|node| node.visible)
.map(visible_text)
.filter(|line| !line.trim().is_empty())
.collect();
let value = text.join("\n");
Condensed {
value,
dropped: Dropped {
nodes_kept: nodes.iter().filter(|node| node.visible).count(),
nodes_present: nodes.len(),
bytes_kept: text.iter().map(String::len).sum(),
bytes_present: text_bytes(nodes),
},
}
}
#[must_use]
pub fn condense(nodes: &[SemanticNode], options: CondenseOptions) -> CondensedPage {
let mut keywords = keywords(nodes);
if keywords.value.len() > options.max_keywords {
keywords.value.truncate(options.max_keywords);
keywords.dropped.bytes_kept = keywords.value.iter().map(|term| term.term.len()).sum();
}
CondensedPage {
keywords,
summary: summary(nodes, options.summary_sentences),
preview: preview(nodes, options.preview_nodes),
structure: structure(nodes),
content: content(nodes),
}
}
#[derive(
Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize, JsonSchema,
)]
#[serde(rename_all = "camelCase")]
pub struct SettleKey {
pub url: Option<String>,
pub revision: u64,
}
#[derive(Debug, Clone)]
pub struct CondensationCache {
capacity: usize,
order: VecDeque<SettleKey>,
entries: BTreeMap<SettleKey, Arc<CondensedPage>>,
}
impl CondensationCache {
#[must_use]
pub fn new(capacity: usize) -> Self {
Self {
capacity: capacity.max(1),
order: VecDeque::new(),
entries: BTreeMap::new(),
}
}
#[must_use]
pub fn get(&self, key: &SettleKey) -> Option<Arc<CondensedPage>> {
self.entries.get(key).map(Arc::clone)
}
pub fn insert(
&mut self,
key: SettleKey,
page: Arc<CondensedPage>,
) -> Option<(SettleKey, Arc<CondensedPage>)> {
if let Some(position) = self.order.iter().position(|existing| existing == &key) {
self.order.remove(position);
}
self.order.push_back(key.clone());
self.entries.insert(key, page);
if self.entries.len() <= self.capacity {
return None;
}
let evicted = self.order.pop_front()?;
let page = self.entries.remove(&evicted)?;
Some((evicted, page))
}
pub fn condense(
&mut self,
key: SettleKey,
nodes: &[SemanticNode],
options: CondenseOptions,
) -> Arc<CondensedPage> {
let page = Arc::new(condense(nodes, options));
let _ = self.insert(key, Arc::clone(&page));
page
}
#[must_use]
pub fn len(&self) -> usize {
self.entries.len()
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.entries.is_empty()
}
}
#[cfg(test)]
mod tests {
use super::*;
fn node(id: u64, parent: Option<u64>, role: &str, name: &str) -> SemanticNode {
SemanticNode {
dom_id: None,
id,
parent,
role: role.to_string(),
name: name.to_string(),
value: None,
enabled: true,
focusable: false,
viewport_fixed: false,
visible: true,
selected: false,
bounds: None,
slot: None,
attributes: Default::default(),
}
}
fn page() -> Vec<SemanticNode> {
vec![
node(1, None, "h1", "Borrowing and ownership in Rust"),
node(
2,
Some(1),
"p",
"Ownership moves a value and borrowing lends it",
),
node(3, Some(1), "h2", "Lifetimes"),
node(4, Some(3), "p", "Lifetimes bound how long a borrow lives"),
node(5, Some(1), "link", "Rustonomicon"),
]
}
#[test]
fn keywords_rank_the_subject_above_the_chrome() {
let terms = keywords(&page());
let ranked: Vec<&str> = terms.value.iter().map(|term| term.term.as_str()).collect();
assert!(ranked.contains(&"borrowing"), "{ranked:?}");
assert!(ranked.contains(&"ownership"), "{ranked:?}");
assert!(!ranked.contains(&"and"), "stoplist ran");
assert!(terms.dropped.byte_ratio() < 1.0, "terms are not the page");
}
#[test]
fn a_summary_is_made_of_sentences_the_page_contains() {
let page = page();
let summary = summary(&page, 2);
assert_eq!(summary.value.len(), 2);
for sentence in &summary.value {
assert!(
page.iter().any(|node| node.name == *sentence),
"{sentence:?} is not on the page"
);
}
}
#[test]
fn a_preview_is_the_leading_nodes_and_says_how_many_it_dropped() {
let page = page();
let preview = preview(&page, 3);
assert_eq!(preview.value.len(), 3);
assert_eq!(preview.dropped.nodes_present, 5);
assert_eq!(preview.dropped.nodes_kept, 3);
}
#[test]
fn structure_keeps_the_tree_and_drops_the_bodies() {
let mut page = page();
page[1].value = Some(
"Ownership moves a value and borrowing lends it, which is a body a \
structure should not carry"
.to_string(),
);
let structure = structure(&page);
assert_eq!(structure.value.len(), 1, "one root");
assert_eq!(structure.dropped.node_ratio(), 1.0);
assert!(structure.dropped.byte_ratio() < 1.0, "bodies were dropped");
let root = &structure.value[0];
assert_eq!(root.role, "h1");
assert_eq!(root.children.len(), 3);
}
#[test]
fn content_is_the_escape_hatch_and_keeps_everything_visible() {
let content = content(&page());
assert!(content.value.contains("Borrowing"));
assert!(content.value.contains("Rustonomicon"));
assert_eq!(content.dropped.byte_ratio(), 1.0);
}
#[test]
fn the_null_margin_refuses_a_ranker_that_is_measuring_english() {
let target = keywords(&page());
let unrelated = keywords(&[node(1, None, "h1", "Weather and traffic in Osaka")]);
let margin = keyword_margin(&target.value, &unrelated.value);
assert!(
margin > 0.5,
"the pages should be mostly disjoint: {margin}"
);
assert_eq!(keyword_margin(&target.value, &target.value), 0.0);
}
#[test]
fn the_cache_is_keyed_on_settle_and_evicts_the_oldest() {
let mut cache = CondensationCache::new(1);
let one = SettleKey {
url: Some("https://example.test/".into()),
revision: 1,
};
let two = SettleKey {
url: Some("https://example.test/".into()),
revision: 2,
};
cache.condense(one.clone(), &page(), CondenseOptions::default());
assert!(cache.get(&one).is_some());
let evicted = cache.condense(two.clone(), &page(), CondenseOptions::default());
assert!(cache.get(&two).is_some());
assert!(cache.get(&one).is_none(), "same URL, different settle");
let _ = evicted;
assert_eq!(cache.len(), 1);
}
#[test]
fn reinserting_a_key_refreshes_rather_than_grows() {
let mut cache = CondensationCache::new(2);
let key = SettleKey {
url: None,
revision: 7,
};
cache.condense(key.clone(), &page(), CondenseOptions::default());
cache.condense(key.clone(), &page(), CondenseOptions::default());
assert_eq!(cache.len(), 1);
}
}