use std::collections::{HashMap, HashSet, hash_map::Entry};
use kcode_k1_kmap_format::ConnectionTier;
pub use kcode_k1_kmap_format::{Node, NodeId};
use kcode_k1_kmap_selection::score;
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;
type Ticket = (usize, f64, u64);
#[derive(Clone, Debug, PartialEq)]
pub struct LoadedNode {
pub node_id: NodeId,
pub source: Option<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, None, &root, true)];
let mut states = HashMap::from([(node_id, NodeState::Opened)]);
let root_targets = self.nav(node_id, &root, 1.0, &states)?;
for occurrence in root_targets {
let target = occurrence.target;
preview(
target,
occurrence.source,
self.required(target)?,
&mut outputs,
&mut states,
);
}
let mut frontier = self.edges(node_id, &root, 1.0, &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;
}
if !occurrence.strength.is_finite() || occurrence.strength <= 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
.nav(occurrence.target, node, occurrence.strength, &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, occurrence.strength, cost));
}
}
if candidates.is_empty() {
break;
}
let choice = self.choose(&candidates)?;
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.nav(occurrence.target, &node, occurrence.strength, &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 guarantee in guarantees {
let target = guarantee.target;
preview(
target,
guarantee.source,
self.required(target)?,
&mut outputs,
&mut states,
);
}
frontier.extend(self.edges(
occurrence.target,
&node,
occurrence.strength,
&states,
)?);
} else {
preview(
occurrence.target,
occurrence.source,
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, None, &root, false)];
let mut states = HashMap::from([(node_id, NodeState::Opened)]);
let root_targets = self.nav(node_id, &root, 1.0, &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 occurrence in root_targets {
let node = self.required(occurrence.target)?;
outputs.push(loaded(
occurrence.target,
Some(occurrence.source),
&node,
false,
));
let _ = states.insert(occurrence.target, NodeState::Opened);
root_nodes.push((occurrence.target, node, occurrence.strength));
}
let mut spent = root_cost;
let mut frontier = self.edges(node_id, &root, 1.0, &states)?;
for (node_id, node, strength) in &root_nodes {
frontier.extend(self.edges(*node_id, node, *strength, &states)?);
}
loop {
let candidates: Vec<Ticket> = frontier
.iter()
.enumerate()
.filter(|(_, occurrence)| !states.contains_key(&occurrence.target))
.filter_map(|(index, occurrence)| {
(occurrence.strength.is_finite() && occurrence.strength > 0.0).then_some((
index,
occurrence.strength,
0,
))
})
.collect();
if candidates.is_empty() {
break;
}
let choice = self.choose(&candidates)?;
let occurrence = frontier[candidates[choice].0].clone();
let node = self.required(occurrence.target)?;
let _ = states.insert(occurrence.target, NodeState::Opened);
let children = self.nav(occurrence.target, &node, occurrence.strength, &states)?;
let cost = preview_cost(attention(children.len().checked_add(1))?)?;
if !affordable(spent, cost, self.budget)? {
break;
}
outputs.push(loaded(
occurrence.target,
Some(occurrence.source),
&node,
false,
));
let mut child_nodes = Vec::with_capacity(children.len());
for child in children {
let node = self.required(child.target)?;
let _ = states.insert(child.target, NodeState::Opened);
outputs.push(loaded(child.target, Some(child.source), &node, false));
child_nodes.push((child.target, node, child.strength));
}
let mut additions =
self.edges(occurrence.target, &node, occurrence.strength, &states)?;
for (node_id, child, strength) in &child_nodes {
additions.extend(self.edges(*node_id, child, *strength, &states)?);
}
frontier.retain(|entry| !states.contains_key(&entry.target));
frontier.extend(additions);
spent = attention(spent.checked_add(cost))?;
}
Ok(result(outputs, spent))
}
fn choose(&mut self, candidates: &[Ticket]) -> Result<usize, String> {
kcode_k1_kmap_selection::choose(candidates, self.temperature, &mut self.random)
}
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 nav(
&mut self,
source: NodeId,
node: &Node,
inherited_strength: f64,
states: &HashMap<NodeId, NodeState>,
) -> Result<Vec<Occurrence>, 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| Occurrence {
source,
target: connection.target,
strength: score(connection.weight.value, inherited_strength),
})
.collect())
}
fn edges(
&mut self,
source: NodeId,
node: &Node,
inherited_strength: f64,
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 {
source,
target: connection.target,
strength: score(connection.weight.value, inherited_strength),
})
.collect())
}
}
#[derive(Clone)]
enum NodeState {
Previewed(Node),
Opened,
}
#[derive(Clone)]
struct Occurrence {
source: NodeId,
target: NodeId,
strength: f64,
}
fn loaded(node_id: NodeId, source: Option<NodeId>, node: &Node, opened: bool) -> LoadedNode {
LoadedNode {
node_id,
source,
title: node.title.clone(),
navigation_hint: node.navigation_hint.clone(),
narrative: opened.then(|| node.narrative.clone()),
}
}
fn preview(
node_id: NodeId,
source: 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, Some(source), &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 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},
collections::HashMap,
};
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 edge(target: NodeId, tier: ConnectionTier, weight: f64) -> Connection {
let mut connection = Connection::new(target, tier);
connection.weight.value = weight;
connection
}
fn filtered(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(), result.nodes[0].source), (1, None));
assert_eq!(filters.get(), 1);
}
#[test]
fn propagates_and_validates_filter_results() {
assert_eq!(
filtered(Err("Access unavailable".to_owned())).unwrap_err(),
"Kmap candidate filter failed: Access unavailable"
);
assert!(
filtered(Ok(vec![id(1), id(1)]))
.unwrap_err()
.contains("returned duplicate node")
);
assert!(
filtered(Ok(vec![id(2)]))
.unwrap_err()
.contains("returned unrequested node")
);
assert_eq!(filtered(Ok(Vec::new())).unwrap().nodes.len(), 1);
}
#[test]
fn memoizes_visibility_across_repeated_paths() {
let (root, a, f, x, b, c, e, d) = (id(0), id(1), id(2), id(3), id(4), id(5), id(6), id(7));
let nodes = HashMap::from([
(
root,
node(vec![
edge(a, ConnectionTier::Navigation, 0.5),
edge(f, ConnectionTier::Navigation, 0.1),
edge(x, ConnectionTier::Automated, 0.15),
]),
),
(a, node(vec![edge(b, ConnectionTier::Automated, 0.4)])),
(f, node(vec![edge(b, ConnectionTier::Automated, 0.9)])),
(
b,
node(vec![
edge(e, ConnectionTier::Automated, 0.8),
edge(c, ConnectionTier::Navigation, 0.5),
]),
),
(c, node(vec![edge(d, ConnectionTier::Automated, 1.0)])),
(x, node(Vec::new())),
(e, node(Vec::new())),
(d, node(Vec::new())),
]);
let batches = RefCell::new(Vec::new());
let result = open_node_with_random(
root,
2.1,
0.0,
OpenMode::NavigationOnly,
|node_id| Ok(nodes.get(&node_id).cloned()),
|targets| {
batches.borrow_mut().push(targets.to_vec());
Ok(targets.to_vec())
},
|| Ok(0.0),
)
.unwrap();
let ids = result
.nodes
.iter()
.map(|node| node.node_id)
.collect::<Vec<_>>();
let sources = result
.nodes
.iter()
.map(|node| node.source)
.collect::<Vec<_>>();
assert_eq!(ids, vec![root, a, f, b, c, e, x, d]);
assert_eq!(
sources,
vec![
None,
Some(root),
Some(root),
Some(a),
Some(b),
Some(b),
Some(root),
Some(c)
]
);
assert_eq!(
batches.into_inner(),
vec![vec![a, f, x], vec![b], vec![e, c], vec![d]]
);
}
}