#![forbid(unsafe_code)]
use std::collections::{HashMap, HashSet, hash_map::Entry};
pub use kcode_k1_kmap_format::{ConnectionTier, 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;
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum LoadOrigin {
Root,
Connection {
source: NodeId,
tier: ConnectionTier,
},
}
#[derive(Clone, Debug, PartialEq)]
pub struct LoadedNode {
pub node_id: NodeId,
pub title: String,
pub navigation_hint: String,
pub narrative: Option<String>,
pub preview_origin: LoadOrigin,
pub narrative_origin: Option<LoadOrigin>,
}
#[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".into());
}
if !temperature.is_finite() || temperature < 0.0 {
return Err("temperature must be finite and nonnegative".into());
}
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, root_id: NodeId, root: Node) -> Result<OpenResult, String> {
let mut outputs = vec![loaded(root_id, &root, true, LoadOrigin::Root)];
let mut states = HashMap::from([(root_id, NodeState::Opened)]);
for occurrence in self.navigation_targets(root_id, &root, 1.0, &states)? {
let node = self.required(occurrence.target)?;
insert_preview(occurrence, node, &mut outputs, &mut states);
}
let mut frontier = self.outgoing(root_id, &root, 1.0, &states)?;
let mut spent = 0;
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))
|| !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
.navigation_targets(
occurrence.target,
node,
occurrence.strength,
&states,
)?
.len();
let cost =
attention(preview_cost(previews)?.checked_add(NARRATIVE_TENTHS))?;
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 =
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() {
states.insert(occurrence.target, NodeState::Opened);
let guarantees = self.navigation_targets(
occurrence.target,
&node,
occurrence.strength,
&states,
)?;
let output = outputs
.iter_mut()
.find(|node| node.node_id == occurrence.target)
.ok_or_else(|| "previewed Kmap node had no output".to_owned())?;
output.narrative = Some(node.narrative.clone());
output.narrative_origin = Some(occurrence.origin());
frontier.retain(|entry| entry.target != occurrence.target);
for guarantee in guarantees {
let node = self.required(guarantee.target)?;
insert_preview(guarantee, node, &mut outputs, &mut states);
}
frontier.extend(self.outgoing(
occurrence.target,
&node,
occurrence.strength,
&states,
)?);
} else {
let node = self.required(occurrence.target)?;
insert_preview(occurrence, node, &mut outputs, &mut states);
}
spent = attention(spent.checked_add(cost))?;
}
Ok(result(outputs, spent))
}
fn navigation_only(&mut self, root_id: NodeId, root: Node) -> Result<OpenResult, String> {
let mut outputs = vec![loaded(root_id, &root, false, LoadOrigin::Root)];
let mut states = HashMap::from([(root_id, NodeState::Opened)]);
let root_targets = self.navigation_targets(root_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, &node, false, occurrence.origin()));
states.insert(occurrence.target, NodeState::Opened);
root_nodes.push((occurrence, node));
}
let mut spent = root_cost;
let mut frontier = self.outgoing(root_id, &root, 1.0, &states)?;
for (occurrence, node) in &root_nodes {
frontier.extend(self.outgoing(
occurrence.target,
node,
occurrence.strength,
&states,
)?);
}
loop {
let candidates = 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::<Vec<_>>();
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 children =
self.navigation_targets(occurrence.target, &node, occurrence.strength, &states)?;
let cost = preview_cost(attention(children.len().checked_add(1))?)?;
if !affordable(spent, cost, self.budget)? {
break;
}
states.insert(occurrence.target, NodeState::Opened);
outputs.push(loaded(occurrence.target, &node, false, occurrence.origin()));
let mut child_nodes = Vec::with_capacity(children.len());
for child in children {
let child_node = self.required(child.target)?;
states.insert(child.target, NodeState::Opened);
outputs.push(loaded(child.target, &child_node, false, child.origin()));
child_nodes.push((child, child_node));
}
let mut additions =
self.outgoing(occurrence.target, &node, occurrence.strength, &states)?;
for (child, node) in &child_nodes {
additions.extend(self.outgoing(child.target, node, 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 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 = node
.connections
.iter()
.map(|connection| connection.target)
.filter(|target| !self.decisions.contains_key(target) && expected.insert(*target))
.collect::<Vec<_>>();
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,
source: NodeId,
node: &Node,
inherited_strength: f64,
states: &HashMap<NodeId, NodeState>,
) -> Result<Vec<Occurrence>, String> {
self.occurrences(source, node, inherited_strength, states, true)
}
fn outgoing(
&mut self,
source: NodeId,
node: &Node,
inherited_strength: f64,
states: &HashMap<NodeId, NodeState>,
) -> Result<Vec<Occurrence>, String> {
self.occurrences(source, node, inherited_strength, states, false)
}
fn occurrences(
&mut self,
source: NodeId,
node: &Node,
inherited_strength: f64,
states: &HashMap<NodeId, NodeState>,
navigation_only: bool,
) -> Result<Vec<Occurrence>, String> {
self.resolve_candidates(node)?;
Ok(node
.connections
.iter()
.filter(|connection| {
let state_allows = if navigation_only {
!states.contains_key(&connection.target)
} else {
!matches!(states.get(&connection.target), Some(NodeState::Opened))
};
state_allows
&& self.decisions.get(&connection.target) == Some(&true)
&& (!navigation_only || connection.tier == ConnectionTier::Navigation)
})
.map(|connection| Occurrence {
source,
target: connection.target,
tier: connection.tier,
strength: score(connection.weight.value, inherited_strength),
})
.collect())
}
}
#[derive(Clone)]
enum NodeState {
Previewed(Node),
Opened,
}
#[derive(Clone)]
struct Occurrence {
source: NodeId,
target: NodeId,
tier: ConnectionTier,
strength: f64,
}
impl Occurrence {
fn origin(&self) -> LoadOrigin {
LoadOrigin::Connection {
source: self.source,
tier: self.tier,
}
}
}
fn loaded(node_id: NodeId, node: &Node, opened: bool, origin: LoadOrigin) -> LoadedNode {
LoadedNode {
node_id,
title: node.title.clone(),
navigation_hint: node.navigation_hint.clone(),
narrative: opened.then(|| node.narrative.clone()),
preview_origin: origin,
narrative_origin: opened.then_some(origin),
}
}
fn insert_preview(
occurrence: Occurrence,
node: Node,
outputs: &mut Vec<LoadedNode>,
states: &mut HashMap<NodeId, NodeState>,
) {
if let Entry::Vacant(entry) = states.entry(occurrence.target) {
outputs.push(loaded(occurrence.target, &node, false, occurrence.origin()));
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 super::*;
use kcode_k1_kmap_format::Connection;
fn id(value: u8) -> NodeId {
let mut bytes = [0; 12];
bytes[0] = value;
NodeId(bytes)
}
fn node(connections: Vec<Connection>) -> Node {
Node {
title: String::new(),
navigation_hint: String::new(),
narrative: "n".into(),
connections,
}
}
fn edge(target: NodeId, tier: ConnectionTier, weight: f64) -> Connection {
let mut connection = Connection::new(target, tier);
connection.weight.value = weight;
connection
}
#[test]
fn records_exact_origins_after_filtering() {
let (root, preview, automatic, denied) = (id(0), id(1), id(2), id(3));
let graph = HashMap::from([
(
root,
node(vec![
edge(preview, ConnectionTier::Navigation, 0.1),
edge(automatic, ConnectionTier::Automated, 1.0),
edge(denied, ConnectionTier::Automated, 0.5),
]),
),
(preview, node(Vec::new())),
(
automatic,
node(vec![edge(preview, ConnectionTier::Automated, 1.0)]),
),
]);
let result = open_node_with_random(
root,
2.3,
0.0,
OpenMode::Full,
|value| Ok(graph.get(&value).cloned()),
|values| {
Ok(values
.iter()
.copied()
.filter(|value| *value != denied)
.collect())
},
|| Ok(0.0),
)
.unwrap();
assert_eq!(result.nodes[0].preview_origin, LoadOrigin::Root);
let loaded = result
.nodes
.iter()
.find(|node| node.node_id == preview)
.unwrap();
assert_eq!(
loaded.preview_origin,
LoadOrigin::Connection {
source: root,
tier: ConnectionTier::Navigation,
}
);
assert_eq!(
loaded.narrative_origin,
Some(LoadOrigin::Connection {
source: automatic,
tier: ConnectionTier::Automated,
})
);
assert!(result.nodes.iter().all(|node| node.node_id != denied));
}
}