use crate::lookup::RECORD_LEN;
use crate::{Rd, Result, bad};
const W: &str = "program selector";
const OPTIONS: usize = 0x30;
const NODES: usize = 0x3c;
const VALUES: usize = 0x48;
const ENTRIES: usize = 0x54;
const IDS: usize = 0x60;
const LEAF: u16 = 0x8000;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct SelectorOption {
pub name: u64,
pub kind: u32,
pub count: u16,
pub extra: u16,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Target {
Node(usize),
Permutation(usize),
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Edge {
pub value: u64,
pub to: Target,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Node {
pub option: usize,
pub edges: Vec<Edge>,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Leaf {
pub path: Vec<(usize, u64)>,
pub permutation: usize,
}
#[derive(Debug, PartialEq, Eq, thiserror::Error)]
pub enum WalkError {
#[error("{given} option values for {options} options")]
Count {
given: usize,
options: usize,
},
#[error("option {option} has no entry for the value {value:#018x} at node {node}")]
NoEdge {
node: usize,
option: usize,
value: u64,
},
#[error("the tree is malformed at node {node}")]
Malformed {
node: usize,
},
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Selector {
pub options: Vec<SelectorOption>,
pub nodes: Vec<Node>,
pub permutations: usize,
}
impl Selector {
pub fn read(section: &[u8], record: &[u8; RECORD_LEN]) -> Result<Self> {
let head = Rd::new(record, "program record");
let place = |at: usize| -> Result<(usize, usize)> {
let ptr = head.offset64le(at.saturating_add(4)).map_err(|_| {
bad(
W,
at,
"pointer out of range: expected an offset that fits the address space",
)
})?;
Ok((head.size32le(at)?, ptr))
};
let array = |at: usize, size: usize| -> Result<Rd<'_>> {
let (n, ptr) = place(at)?;
let bytes = n.checked_mul(size).ok_or_else(|| bad(W, at, "array size"))?;
Ok(Rd::new(Rd::new(section, W).bytes(ptr, bytes)?, W))
};
let (n_options, _) = place(OPTIONS)?;
let (n_nodes, _) = place(NODES)?;
let (n_values, _) = place(VALUES)?;
let (n_entries, _) = place(ENTRIES)?;
let (permutations, _) = place(IDS)?;
array(IDS, 8)?;
if n_options == 0 && n_nodes == 0 && n_values == 0 && n_entries == 0 {
if permutations != 1 {
return Err(bad(W, IDS, format!("{permutations} permutations and no options")));
}
return Ok(Self {
options: Vec::new(),
nodes: Vec::new(),
permutations,
});
}
if n_nodes == 0 || n_options == 0 {
return Err(bad(W, NODES, format!("{n_nodes} nodes and {n_options} options")));
}
if n_values != n_entries {
return Err(bad(
W,
VALUES,
format!("{n_values} values for {n_entries} entries"),
));
}
let (opts, nodes, values, entries) = (
array(OPTIONS, 16)?,
array(NODES, 6)?,
array(VALUES, 8)?,
array(ENTRIES, 2)?,
);
let options = (0..n_options)
.map(|i| {
let at = crate::at(0, i, 16);
Ok(SelectorOption {
name: opts.u64le(at)?,
kind: opts.u32le(crate::at(at, 2, 4))?,
count: opts.u16le(crate::at(at, 12, 1))?,
extra: opts.u16le(crate::at(at, 14, 1))?,
})
})
.collect::<Result<Vec<_>>>()?;
let mut tree = Vec::with_capacity(n_nodes);
let mut next = 0usize;
for i in 0..n_nodes {
let at = crate::at(0, i, 6);
let (k, start, len) = (
usize::from(nodes.u16le(at)?),
usize::from(nodes.u16le(crate::at(at, 2, 1))?),
usize::from(nodes.u16le(crate::at(at, 4, 1))?),
);
if start != next || len == 0 {
return Err(bad(
W,
at,
format!("node {i} starts at {start} with {len} entries, {next} expected"),
));
}
next = start
.checked_add(len)
.filter(|&end| end <= n_entries)
.ok_or_else(|| bad(W, at, format!("node {i} runs past the {n_entries} entries")))?;
if k >= n_options {
return Err(bad(W, at, format!("node {i} tests option {k} of {n_options}")));
}
let mut edges: Vec<Edge> = Vec::with_capacity(len);
for j in start..next {
let value = values.u64le(crate::at(0, j, 8))?;
let entry = entries.u16le(crate::at(0, j, 2))?;
if edges.iter().any(|e| e.value == value) {
return Err(bad(
W,
at,
format!("node {i} names the value {value:#018x} twice"),
));
}
let to = match entry.checked_sub(LEAF) {
Some(p) => Target::Permutation(usize::from(p)),
None => Target::Node(usize::from(entry)),
};
edges.push(Edge { value, to });
}
tree.push(Node { option: k, edges });
}
if next != n_entries {
return Err(bad(
W,
NODES,
format!("the nodes cover {next} of {n_entries} entries"),
));
}
let root = tree
.first()
.ok_or_else(|| bad(W, NODES, "no nodes: expected a root that tests option 0"))?;
if root.option != 0 {
return Err(bad(
W,
NODES,
format!("the root tests option {}, expected 0", root.option),
));
}
let mut named = vec![0usize; n_nodes];
let mut ended = vec![0usize; permutations];
for (i, node) in tree.iter().enumerate() {
for e in &node.edges {
match e.to {
Target::Node(c) => {
let child = tree.get(c).filter(|_| c != 0).ok_or_else(|| {
bad(W, NODES, format!("node {i} leads to node {c} of {n_nodes}"))
})?;
if child.option <= node.option {
return Err(bad(
W,
NODES,
format!(
"node {i} (option {}) leads to node {c} (option {})",
node.option, child.option
),
));
}
if let Some(n) = named.get_mut(c) {
*n = n.saturating_add(1);
}
}
Target::Permutation(p) => match ended.get_mut(p) {
Some(n) => *n = n.saturating_add(1),
None => {
return Err(bad(
W,
NODES,
format!("node {i} ends at permutation {p} of {permutations}"),
));
}
},
}
}
}
if let Some((i, n)) = named.iter().enumerate().skip(1).find(|&(_, &n)| n != 1) {
return Err(bad(
W,
NODES,
format!("node {i} is led to {n} times, expected once"),
));
}
if let Some((p, n)) = ended.iter().enumerate().find(|&(_, &n)| n != 1) {
return Err(bad(
W,
NODES,
format!("permutation {p} is ended at {n} times, expected once"),
));
}
Ok(Self {
options,
nodes: tree,
permutations,
})
}
pub fn walk(&self, values: &[u64]) -> std::result::Result<usize, WalkError> {
if values.len() != self.options.len() {
return Err(WalkError::Count {
given: values.len(),
options: self.options.len(),
});
}
if self.nodes.is_empty() {
return Ok(0);
}
let mut at = 0;
for _ in 0..=self.nodes.len() {
let node = self.nodes.get(at).ok_or(WalkError::Malformed { node: at })?;
let value = *values.get(node.option).ok_or(WalkError::Malformed { node: at })?;
match node.edges.iter().find(|e| e.value == value).map(|e| e.to) {
Some(Target::Permutation(p)) => return Ok(p),
Some(Target::Node(next)) => at = next,
None => {
return Err(WalkError::NoEdge {
node: at,
option: node.option,
value,
});
}
}
}
Err(WalkError::Malformed { node: at })
}
pub fn leaves(&self) -> Vec<Leaf> {
fn go(s: &Selector, at: usize, path: &mut Vec<(usize, u64)>, out: &mut Vec<Leaf>) {
let Some(node) = s.nodes.get(at).filter(|_| path.len() <= s.nodes.len()) else {
return;
};
for e in &node.edges {
path.push((node.option, e.value));
match e.to {
Target::Permutation(permutation) => out.push(Leaf {
path: path.clone(),
permutation,
}),
Target::Node(c) => go(s, c, path, out),
}
path.pop();
}
}
let mut out = Vec::new();
if self.nodes.is_empty() {
out.push(Leaf {
path: Vec::new(),
permutation: 0,
});
} else {
go(self, 0, &mut Vec::new(), &mut out);
}
out
}
pub fn values_of(&self, option: usize) -> Vec<u64> {
let mut v: Vec<u64> = (self.nodes.iter())
.filter(|n| n.option == option)
.flat_map(|n| n.edges.iter().map(|e| e.value))
.collect();
v.sort_unstable();
v.dedup();
v
}
}
#[cfg(test)]
mod tests {
use super::*;
#[derive(Default)]
struct Build {
options: Vec<(u64, u32)>,
nodes: Vec<(u16, u16, u16)>,
values: Vec<u64>,
entries: Vec<u16>,
ids: usize,
}
impl Build {
fn finish(&self) -> (Vec<u8>, [u8; RECORD_LEN]) {
let mut section = vec![0xEEu8; 16];
let mut record = [0u8; RECORD_LEN];
let mut put = |at: usize, count: usize, bytes: Vec<u8>| {
while !section.len().is_multiple_of(4) {
section.push(0);
}
let ptr = section.len() as u64;
section.extend(bytes);
record[at..at + 4].copy_from_slice(&(count as u32).to_le_bytes());
record[at + 4..at + 12].copy_from_slice(&ptr.to_le_bytes());
};
put(
OPTIONS,
self.options.len(),
(self.options.iter())
.flat_map(|&(name, kind)| {
let mut o = name.to_le_bytes().to_vec();
o.extend(kind.to_le_bytes());
o.extend(1u16.to_le_bytes());
o.extend(0u16.to_le_bytes());
o
})
.collect(),
);
put(
NODES,
self.nodes.len(),
(self.nodes.iter())
.flat_map(|&(k, s, l)| [k, s, l].into_iter().flat_map(u16::to_le_bytes))
.collect(),
);
put(
VALUES,
self.values.len(),
self.values.iter().flat_map(|v| v.to_le_bytes()).collect(),
);
put(
ENTRIES,
self.entries.len(),
self.entries.iter().flat_map(|e| e.to_le_bytes()).collect(),
);
put(
IDS,
self.ids,
(0..self.ids as u64)
.flat_map(|i| (0x1000 + i).to_le_bytes())
.collect(),
);
(section, record)
}
fn read(&self) -> Result<Selector> {
let (section, record) = self.finish();
Selector::read(§ion, &record)
}
}
const A: u64 = 0xA0A0_0000_0000_0001;
const B: u64 = 0xB0B0_0000_0000_0002;
fn full() -> Build {
Build {
options: vec![(A, 7), (B, 8)],
nodes: vec![(0, 0, 3), (1, 3, 2), (1, 5, 2), (1, 7, 2)],
values: vec![10, 11, 12, 20, 21, 20, 21, 20, 21],
entries: vec![1, 2, 3, LEAF, LEAF + 1, LEAF + 2, LEAF + 3, LEAF + 4, LEAF + 5],
ids: 6,
}
}
fn mixed() -> Build {
Build {
options: vec![(A, 7), (B, 8)],
nodes: vec![(0, 0, 2), (1, 2, 1)],
values: vec![10, 11, 20],
entries: vec![LEAF, 1, LEAF + 1],
ids: 2,
}
}
#[test]
fn a_full_tree_walks_each_assignment_to_its_permutation() {
let s = full().read().unwrap();
assert_eq!((s.options.len(), s.nodes.len(), s.permutations), (2, 4, 6));
assert_eq!(
s.options[0],
SelectorOption {
name: A,
kind: 7,
count: 1,
extra: 0
}
);
let mut seen = Vec::new();
for (a, first) in [(10, 0), (11, 2), (12, 4)] {
for (b, add) in [(20, 0), (21, 1)] {
assert_eq!(s.walk(&[a, b]), Ok(first + add), "{a} {b}");
seen.push(first + add);
}
}
seen.sort_unstable();
assert_eq!(seen, [0, 1, 2, 3, 4, 5]);
assert_eq!(s.values_of(0), [10, 11, 12]);
assert_eq!(s.values_of(1), [20, 21]);
let leaves = s.leaves();
assert_eq!(leaves.len(), 6);
assert_eq!(
leaves[3],
Leaf {
path: vec![(0, 11), (1, 21)],
permutation: 3
}
);
}
#[test]
fn a_leaf_above_the_last_option_ignores_the_options_after_it() {
let s = mixed().read().unwrap();
for b in [20, 21, 0xDEAD] {
assert_eq!(s.walk(&[10, b]), Ok(0));
}
assert_eq!(s.walk(&[11, 20]), Ok(1));
assert_eq!(s.leaves().len(), 2);
assert_eq!(s.leaves()[0].path, [(0, 10)]);
}
#[test]
fn a_walk_that_leaves_the_tree_is_refused_with_where() {
let s = mixed().read().unwrap();
assert_eq!(
s.walk(&[12, 20]),
Err(WalkError::NoEdge {
node: 0,
option: 0,
value: 12
})
);
assert_eq!(
s.walk(&[11, 21]),
Err(WalkError::NoEdge {
node: 1,
option: 1,
value: 21
})
);
assert_eq!(s.walk(&[10]), Err(WalkError::Count { given: 1, options: 2 }));
assert_eq!(
s.walk(&[10, 20, 30]),
Err(WalkError::Count { given: 3, options: 2 })
);
}
#[test]
fn a_record_with_no_options_has_one_permutation() {
let s = Build {
ids: 1,
..Build::default()
}
.read()
.unwrap();
assert_eq!(s.walk(&[]), Ok(0));
assert_eq!(
s.leaves(),
[Leaf {
path: Vec::new(),
permutation: 0
}]
);
assert!(s.nodes.is_empty());
assert!(
Build {
ids: 2,
..Build::default()
}
.read()
.is_err()
);
}
#[test]
fn what_cannot_be_placed_is_refused() {
let broken: Vec<(&str, Build)> = vec![
(
"gap between nodes",
Build {
nodes: vec![(0, 0, 1), (1, 2, 1)],
..mixed()
},
),
(
"nodes short of the entries",
Build {
nodes: vec![(0, 0, 2)],
entries: vec![LEAF, LEAF + 1, LEAF + 1],
values: vec![10, 11, 12],
..mixed()
},
),
(
"empty node",
Build {
nodes: vec![(0, 0, 0), (1, 0, 3)],
..mixed()
},
),
(
"option out of range",
Build {
nodes: vec![(0, 0, 2), (2, 2, 1)],
..mixed()
},
),
(
"root not at option 0",
Build {
nodes: vec![(1, 0, 2), (1, 2, 1)],
..mixed()
},
),
(
"child at the same option",
Build {
nodes: vec![(0, 0, 2), (0, 2, 1)],
..mixed()
},
),
(
"value named twice",
Build {
values: vec![10, 10, 20],
..mixed()
},
),
(
"child past the nodes",
Build {
entries: vec![LEAF, 5, LEAF + 1],
..mixed()
},
),
(
"root named as a child",
Build {
entries: vec![0, 1, LEAF + 1],
..mixed()
},
),
(
"node led to twice",
Build {
entries: vec![1, 1, LEAF],
..mixed()
},
),
(
"node never led to",
Build {
entries: vec![LEAF, LEAF + 1, LEAF + 1],
..mixed()
},
),
(
"permutation twice",
Build {
entries: vec![LEAF, 1, LEAF],
..mixed()
},
),
("permutation never", Build { ids: 3, ..mixed() }),
(
"permutation out of range",
Build {
entries: vec![LEAF, 1, LEAF + 2],
..mixed()
},
),
(
"values and entries differ in count",
Build {
values: vec![10, 11],
..mixed()
},
),
(
"nodes without options",
Build {
options: vec![],
..mixed()
},
),
];
for (what, b) in broken {
assert!(b.read().is_err(), "{what} was read");
}
let (section, record) = mixed().finish();
assert!(Selector::read(§ion[..section.len() - 1], &record).is_err());
assert!(Selector::read(&[], &record).is_err());
let mut far = record;
far[NODES + 4..NODES + 12].copy_from_slice(&u64::MAX.to_le_bytes());
assert!(Selector::read(§ion, &far).is_err());
}
}