use super::counts::Predicates;
use crate::linear::occurrences::{Forest, Sign};
use crate::linear::search::Bias;
use crate::linear::sequents::{Atom, Kind};
use std::cmp::Ordering;
pub(crate) fn signs(forest: &Forest, rule: Bias) -> Box<[Sign]> {
let num_atoms = forest.sequent().atom_names().len();
let by_factors = match rule {
Bias::Auto => !forest
.ids()
.any(|o| matches!(forest.kind(o), Kind::Bang | Kind::Quest)),
Bias::Rarer => false,
Bias::Factors => true,
};
let mut factors = vec![0u64; forest.lists()];
if by_factors {
const WHOLE: u64 = 1 << 31;
let mut choices = vec![0u8; forest.len()];
for o in forest.ids() {
let Some(p) = forest.parent(o) else {
continue;
};
let additive = matches!(forest.kind(p), Kind::With | Kind::Plus);
choices[o.index()] = choices[p.index()].saturating_add(u8::from(additive));
if let (Some(atom), Some(s)) = (forest.atom(o), forest.sign(o))
&& forest.kind(p) == Kind::Tensor
{
factors[Forest::list(atom, s)] += WHOLE
.checked_shr(u32::from(choices[o.index()]))
.unwrap_or(0);
}
}
}
let predicates = Predicates::of(forest.sequent());
let mut literals = |a: usize| {
let atom = Atom::new(a as u32);
[Sign::Atom, Sign::Dual].map(|sign| forest.literals(atom, sign).len())
};
let mut merged: Vec<[usize; 2]> = Vec::new();
if let Some(predicates) = &predicates {
merged = (0..num_atoms).map(&mut literals).collect();
for a in 0..num_atoms {
let counted = predicates.counted(Atom::new(a as u32)).index();
if counted != a {
for sign in [Sign::Atom, Sign::Dual] {
let (from, to) = (
Forest::list(Atom::new(a as u32), sign),
Forest::list(Atom::new(counted as u32), sign),
);
factors[to] += std::mem::take(&mut factors[from]);
merged[counted][sign as usize] += merged[a][sign as usize];
}
}
}
}
let sign_of = |a: usize, [vars, duals]: [usize; 2]| {
let atom = Atom::new(a as u32);
match factors[Forest::list(atom, Sign::Atom)].cmp(&factors[Forest::list(atom, Sign::Dual)])
{
Ordering::Greater => Sign::Atom,
Ordering::Less => Sign::Dual,
Ordering::Equal if duals < vars => Sign::Dual,
Ordering::Equal => Sign::Atom,
}
};
match &predicates {
None => (0..num_atoms).map(|a| sign_of(a, literals(a))).collect(),
Some(predicates) => (0..num_atoms)
.map(|a| {
let counted = predicates.counted(Atom::new(a as u32)).index();
sign_of(counted, merged[counted])
})
.collect(),
}
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::*;
fn sign(input: &str, atom: &str, rule: Bias) -> Sign {
let forest = Forest::new(&input.parse().unwrap()).unwrap();
signs(&forest, rule)[forest.sequent().atom(atom).unwrap().index()]
}
#[test]
fn rarer_literal() {
let input = "A, A |- A, B, C -o C, C -o C";
assert_eq!(
sign(input, "A", Bias::Auto),
Sign::Atom,
"one A against two ~A"
);
assert_eq!(
sign(input, "B", Bias::Auto),
Sign::Dual,
"no ~B at all, so ~B is the rarer one"
);
assert_eq!(sign(input, "C", Bias::Auto), Sign::Atom, "two of each");
assert_eq!(sign("|- A, A, ~A", "A", Bias::Auto), Sign::Dual);
}
#[test]
fn tensor_factors() {
let horn = "|- ~A, A * ~B, A * ~B, B";
assert_eq!(sign(horn, "A", Bias::Auto), Sign::Atom);
assert_eq!(sign(horn, "B", Bias::Auto), Sign::Dual);
let choice = "|- (A * ~D) + (B * ~D), D * C, ~A, ~B, ~C";
assert_eq!(sign(choice, "D", Bias::Auto), Sign::Atom);
let exponential = "|- ?~A, A * ~B, A * ~B, B";
assert_eq!(sign(exponential, "A", Bias::Auto), Sign::Dual);
assert_eq!(sign(exponential, "A", Bias::Factors), Sign::Atom);
assert_eq!(sign(horn, "A", Bias::Rarer), Sign::Dual);
}
}