use std::collections::{HashMap, HashSet, hash_map::Entry};
use kcode_k1_kmap_format::ConnectionTier;
pub use kcode_k1_kmap_format::{Node, NodeId};
pub use kcode_k1_kmap_selection::DEPTH_DECAY;
pub const PREVIEW_COST: f64 = 0.3;
pub const NARRATIVE_COST: f64 = 1.0;
const PREVIEW_TENTHS: u64 = 3;
const NARRATIVE_TENTHS: u64 = 10;
type CandidateFilter<'a> = dyn FnMut(&[NodeId]) -> Result<Vec<NodeId>, String> + 'a;
#[derive(Clone, Debug, PartialEq)]
pub struct LoadedNode {
pub node_id: NodeId,
pub title: String,
pub navigation_hint: String,
pub narrative: Option<String>,
}
#[derive(Clone, Debug, PartialEq)]
pub struct OpenResult {
pub nodes: Vec<LoadedNode>,
pub automatic_attention_spent: f64,
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum OpenMode {
Full,
NavigationOnly,
}
pub fn open_node(
node_id: NodeId,
budget: f64,
temperature: f64,
mode: OpenMode,
load_node: impl FnMut(NodeId) -> Result<Option<Node>, String>,
candidate_filter: impl FnMut(&[NodeId]) -> Result<Vec<NodeId>, String>,
) -> Result<OpenResult, String> {
open_node_with_random(
node_id,
budget,
temperature,
mode,
load_node,
candidate_filter,
kcode_k1_kmap_selection::os_random_unit,
)
}
fn open_node_with_random(
node_id: NodeId,
budget: f64,
temperature: f64,
mode: OpenMode,
mut load_node: impl FnMut(NodeId) -> Result<Option<Node>, String>,
mut candidate_filter: impl FnMut(&[NodeId]) -> Result<Vec<NodeId>, String>,
mut random: impl FnMut() -> Result<f64, String>,
) -> Result<OpenResult, String> {
if !budget.is_finite() || budget < 0.0 {
return Err("budget must be finite and nonnegative".to_owned());
}
if !temperature.is_finite() || temperature < 0.0 {
return Err("temperature must be finite and nonnegative".to_owned());
}
let mut engine = Engine {
budget,
temperature,
load_node: &mut load_node,
candidate_filter: &mut candidate_filter,
random: &mut random,
decisions: HashMap::from([(node_id, true)]),
};
let root = engine.required(node_id)?;
match mode {
OpenMode::Full => engine.full(node_id, root),
OpenMode::NavigationOnly => engine.navigation_only(node_id, root),
}
}
struct Engine<'a> {
budget: f64,
temperature: f64,
load_node: &'a mut dyn FnMut(NodeId) -> Result<Option<Node>, String>,
candidate_filter: &'a mut CandidateFilter<'a>,
random: &'a mut dyn FnMut() -> Result<f64, String>,
decisions: HashMap<NodeId, bool>,
}
impl Engine<'_> {
fn full(&mut self, node_id: NodeId, root: Node) -> Result<OpenResult, String> {
let mut outputs = vec![loaded(node_id, &root, true)];
let mut states = HashMap::from([(node_id, NodeState::Opened)]);
let root_targets = self.navigation_targets(&root, &states)?;
for target in root_targets {
insert_preview(target, self.required(target)?, &mut outputs, &mut states);
}
let mut frontier = self.outgoing(&root, 1, &states)?;
let mut spent = 0_u64;
loop {
let mut candidates = Vec::new();
let mut opening_costs = HashMap::new();
for (index, occurrence) in frontier.iter().enumerate() {
if matches!(states.get(&occurrence.target), Some(NodeState::Opened)) {
continue;
}
let effective = kcode_k1_kmap_selection::score(occurrence.value, occurrence.depth);
if !effective.is_finite() || effective <= 0.0 {
continue;
}
let cost = match states.get(&occurrence.target) {
None => PREVIEW_TENTHS,
Some(NodeState::Previewed(node)) => {
if let Some(cost) = opening_costs.get(&occurrence.target) {
*cost
} else {
let previews = self.navigation_targets(node, &states)?.len();
let cost =
attention(preview_cost(previews)?.checked_add(NARRATIVE_TENTHS))?;
let _ = opening_costs.insert(occurrence.target, cost);
cost
}
}
Some(NodeState::Opened) => continue,
};
if affordable(spent, cost, self.budget)? {
candidates.push((index, effective, cost));
}
}
if candidates.is_empty() {
break;
}
let choice =
kcode_k1_kmap_selection::choose(&candidates, self.temperature, &mut self.random)?;
let (selected, _, cost) = candidates[choice];
let occurrence = frontier[selected].clone();
if let Some(NodeState::Previewed(node)) = states.get(&occurrence.target).cloned() {
let _ = states.insert(occurrence.target, NodeState::Opened);
let guarantees = self.navigation_targets(&node, &states)?;
outputs
.iter_mut()
.find(|node| node.node_id == occurrence.target)
.ok_or_else(|| "previewed Kmap node had no output".to_owned())?
.narrative = Some(node.narrative.clone());
frontier.retain(|entry| entry.target != occurrence.target);
for target in guarantees {
insert_preview(target, self.required(target)?, &mut outputs, &mut states);
}
frontier.extend(self.outgoing(
&node,
increment_depth(occurrence.depth)?,
&states,
)?);
} else {
insert_preview(
occurrence.target,
self.required(occurrence.target)?,
&mut outputs,
&mut states,
);
}
spent = attention(spent.checked_add(cost))?;
}
Ok(result(outputs, spent))
}
fn navigation_only(&mut self, node_id: NodeId, root: Node) -> Result<OpenResult, String> {
let mut outputs = vec![loaded(node_id, &root, false)];
let mut states = HashMap::from([(node_id, NodeState::Opened)]);
let root_targets = self.navigation_targets(&root, &states)?;
let root_cost = preview_cost(root_targets.len())?;
if !affordable(0, root_cost, self.budget)? {
return Ok(result(outputs, 0));
}
let mut root_nodes = Vec::with_capacity(root_targets.len());
for target in root_targets {
let node = self.required(target)?;
outputs.push(loaded(target, &node, false));
let _ = states.insert(target, NodeState::Opened);
root_nodes.push(node);
}
let mut spent = root_cost;
let mut frontier = self.outgoing(&root, 1, &states)?;
for node in &root_nodes {
frontier.extend(self.outgoing(node, 2, &states)?);
}
loop {
let candidates: Vec<(usize, f64, u64)> = frontier
.iter()
.enumerate()
.filter(|(_, occurrence)| !states.contains_key(&occurrence.target))
.filter_map(|(index, occurrence)| {
let effective =
kcode_k1_kmap_selection::score(occurrence.value, occurrence.depth);
(effective.is_finite() && effective > 0.0).then_some((index, effective, 0))
})
.collect();
if candidates.is_empty() {
break;
}
let choice =
kcode_k1_kmap_selection::choose(&candidates, self.temperature, &mut self.random)?;
let occurrence = frontier[candidates[choice].0].clone();
let node = self.required(occurrence.target)?;
let _ = states.insert(occurrence.target, NodeState::Opened);
let children = self.navigation_targets(&node, &states)?;
let cost = preview_cost(attention(children.len().checked_add(1))?)?;
if !affordable(spent, cost, self.budget)? {
break;
}
outputs.push(loaded(occurrence.target, &node, false));
let mut child_nodes = Vec::with_capacity(children.len());
for target in children {
let child = self.required(target)?;
let _ = states.insert(target, NodeState::Opened);
outputs.push(loaded(target, &child, false));
child_nodes.push(child);
}
let next_depth = increment_depth(occurrence.depth)?;
let mut additions = self.outgoing(&node, next_depth, &states)?;
for child in &child_nodes {
additions.extend(self.outgoing(child, increment_depth(next_depth)?, &states)?);
}
frontier.retain(|entry| !states.contains_key(&entry.target));
frontier.extend(additions);
spent = attention(spent.checked_add(cost))?;
}
Ok(result(outputs, spent))
}
fn required(&mut self, node_id: NodeId) -> Result<Node, String> {
(self.load_node)(node_id)?
.ok_or_else(|| format!("authorized Kmap target {node_id:?} is missing"))
}
fn resolve_candidates(&mut self, node: &Node) -> Result<(), String> {
let mut expected = HashSet::with_capacity(node.connections.len());
let requested: Vec<NodeId> = node
.connections
.iter()
.map(|connection| connection.target)
.filter(|target| !self.decisions.contains_key(target) && expected.insert(*target))
.collect();
if requested.is_empty() {
return Ok(());
}
let returned = (self.candidate_filter)(&requested)
.map_err(|error| format!("Kmap candidate filter failed: {error}"))?;
let mut allowed = HashSet::with_capacity(returned.len());
for target in returned {
if !expected.contains(&target) {
return Err(format!(
"Kmap candidate filter returned unrequested node {target:?}"
));
}
if !allowed.insert(target) {
return Err(format!(
"Kmap candidate filter returned duplicate node {target:?}"
));
}
}
self.decisions.extend(
requested
.into_iter()
.map(|target| (target, allowed.contains(&target))),
);
Ok(())
}
fn navigation_targets(
&mut self,
node: &Node,
states: &HashMap<NodeId, NodeState>,
) -> Result<Vec<NodeId>, String> {
self.resolve_candidates(node)?;
Ok(node
.connections
.iter()
.filter(|connection| {
!states.contains_key(&connection.target)
&& self.decisions.get(&connection.target) == Some(&true)
&& connection.tier == ConnectionTier::Navigation
})
.map(|connection| connection.target)
.collect())
}
fn outgoing(
&mut self,
node: &Node,
depth: usize,
states: &HashMap<NodeId, NodeState>,
) -> Result<Vec<Occurrence>, String> {
self.resolve_candidates(node)?;
Ok(node
.connections
.iter()
.filter(|connection| {
!matches!(states.get(&connection.target), Some(NodeState::Opened))
&& self.decisions.get(&connection.target) == Some(&true)
})
.map(|connection| Occurrence {
target: connection.target,
value: connection.weight.value,
depth,
})
.collect())
}
}
#[derive(Clone)]
enum NodeState {
Previewed(Node),
Opened,
}
#[derive(Clone)]
struct Occurrence {
target: NodeId,
value: f64,
depth: usize,
}
fn loaded(node_id: NodeId, node: &Node, opened: bool) -> LoadedNode {
LoadedNode {
node_id,
title: node.title.clone(),
navigation_hint: node.navigation_hint.clone(),
narrative: opened.then(|| node.narrative.clone()),
}
}
fn insert_preview(
node_id: NodeId,
node: Node,
outputs: &mut Vec<LoadedNode>,
states: &mut HashMap<NodeId, NodeState>,
) {
if let Entry::Vacant(entry) = states.entry(node_id) {
outputs.push(loaded(node_id, &node, false));
entry.insert(NodeState::Previewed(node));
}
}
fn result(nodes: Vec<LoadedNode>, spent: u64) -> OpenResult {
OpenResult {
nodes,
automatic_attention_spent: spent as f64 / 10.0,
}
}
fn increment_depth(depth: usize) -> Result<usize, String> {
depth
.checked_add(1)
.ok_or_else(|| "Kmap traversal depth overflow".to_owned())
}
fn attention<T>(value: Option<T>) -> Result<T, String> {
value.ok_or_else(|| "Kmap attention cost overflow".to_owned())
}
fn preview_cost(count: usize) -> Result<u64, String> {
let count = attention(u64::try_from(count).ok())?;
attention(count.checked_mul(PREVIEW_TENTHS))
}
fn affordable(spent: u64, cost: u64, budget: f64) -> Result<bool, String> {
let total = attention(spent.checked_add(cost))? as f64 / 10.0;
let tolerance = 8.0 * f64::EPSILON * total.abs().max(budget.abs()).max(1.0);
Ok(total <= budget || total - budget <= tolerance)
}
#[cfg(test)]
mod tests {
use std::cell::{Cell, RefCell};
use kcode_k1_kmap_format::{Connection, ConnectionTier};
use super::{Node, NodeId, OpenMode, OpenResult, open_node_with_random};
fn id(value: u64) -> NodeId {
let mut bytes = [0; 12];
bytes[..8].copy_from_slice(&value.to_le_bytes());
NodeId(bytes)
}
fn node(connections: Vec<Connection>) -> Node {
Node {
title: String::new(),
navigation_hint: String::new(),
narrative: String::new(),
connections,
}
}
fn run_filter(returned: Result<Vec<NodeId>, String>) -> Result<OpenResult, String> {
let root = id(0);
let root_node = node(vec![Connection::new(id(1), ConnectionTier::Automated)]);
open_node_with_random(
root,
1.0,
1.0,
OpenMode::NavigationOnly,
|node_id| Ok((node_id == root).then(|| root_node.clone())),
move |_| returned.clone(),
|| panic!("RNG invoked for rejected or denied candidates"),
)
}
#[test]
fn batches_large_denial_before_reads_and_randomness() {
let root = id(0);
let root_node = node(
(1..=10_000)
.map(|value| Connection::new(id(value), ConnectionTier::Automated))
.collect(),
);
let filters = Cell::new(0);
let result = open_node_with_random(
root,
10_000.0,
1.0,
OpenMode::NavigationOnly,
|node_id| Ok((node_id == root).then(|| root_node.clone())),
|targets| {
filters.set(filters.get() + 1);
assert_eq!(targets.len(), 10_000);
assert_eq!((targets[0], targets[9_999]), (id(1), id(10_000)));
Ok(Vec::new())
},
|| panic!("RNG invoked after every candidate was denied"),
)
.unwrap();
assert_eq!(result.nodes.len(), 1);
assert_eq!(filters.get(), 1);
}
#[test]
fn propagates_and_validates_filter_results() {
assert_eq!(
run_filter(Err("Access unavailable".to_owned())).unwrap_err(),
"Kmap candidate filter failed: Access unavailable"
);
assert!(
run_filter(Ok(vec![id(1), id(1)]))
.unwrap_err()
.contains("returned duplicate node")
);
assert!(
run_filter(Ok(vec![id(2)]))
.unwrap_err()
.contains("returned unrequested node")
);
assert_eq!(run_filter(Ok(Vec::new())).unwrap().nodes.len(), 1);
}
#[test]
fn memoizes_visibility_across_repeated_paths() {
let (root, a, b, target) = (id(0), id(1), id(2), id(3));
let root_node = node(vec![
Connection::new(a, ConnectionTier::Navigation),
Connection::new(b, ConnectionTier::Navigation),
]);
let branch = node(vec![Connection::new(target, ConnectionTier::Automated)]);
let target_node = node(Vec::new());
let batches = RefCell::new(Vec::new());
open_node_with_random(
root,
0.6,
1.0,
OpenMode::NavigationOnly,
|node_id| {
Ok(match node_id {
value if value == root => Some(root_node.clone()),
value if value == a || value == b => Some(branch.clone()),
value if value == target => Some(target_node.clone()),
_ => None,
})
},
|targets| {
batches.borrow_mut().push(targets.to_vec());
Ok(targets.to_vec())
},
|| Ok(0.0),
)
.unwrap();
assert_eq!(batches.into_inner(), vec![vec![a, b], vec![target]]);
}
}