use super::context::Context;
use super::memo::{REPEATED, decoded};
use crate::linear::occurrences::{Forest, OccId, OccSet, Reading, Side};
#[derive(Clone, Debug)]
pub(crate) struct Classes {
class: Box<[OccId]>,
renamed: OccSet,
distinct: bool,
}
fn mark(words: &mut [OccId], at: usize, class: OccId, copies: u32) -> usize {
if copies == 1 {
words[at] = class;
1
} else {
words[at] = OccId::new(class.get() | REPEATED);
words[at + 1] = OccId::new(copies);
2
}
}
impl Classes {
pub(crate) fn new(forest: &Forest, reading: Option<&Reading>) -> Self {
const NONE: u32 = u32::MAX;
let mut first = vec![[NONE; 2]; forest.sequent().terms().len()];
let class: Box<[OccId]> = forest
.ids()
.map(|o| {
let output = reading.is_some_and(|r| r.position(o) == Side::Output);
let slot = &mut first[forest.term(o).index()][usize::from(output)];
if *slot == NONE {
*slot = o.get();
}
OccId::new(*slot)
})
.collect();
let mut renamed = OccSet::empty(forest.len());
renamed.extend(forest.ids().filter(|&o| class[o.index()] != o));
let distinct = renamed.is_empty();
Self {
class,
renamed,
distinct,
}
}
#[cfg(test)]
pub(crate) fn distinct(&self) -> bool {
self.distinct
}
pub(crate) fn bytes(&self) -> usize {
self.class.len() * size_of::<OccId>() + size_of_val(self.renamed.words())
}
pub(crate) fn renames(&self, gamma: &Context) -> bool {
!self.distinct && gamma.meets(&self.renamed)
}
pub(crate) fn renames_any(&self, key: &[OccId]) -> bool {
!self.distinct && decoded(key).any(|(o, _)| self.renamed.contains(o))
}
pub(crate) fn canonical(&self, key: &[OccId], repeats: bool, canonical: &mut Vec<OccId>) {
canonical.clear();
if !repeats {
canonical.extend(key.iter().map(|&o| self.of(o)));
canonical.sort_unstable();
let words = canonical.as_mut_slice();
let (mut written, mut at) = (0, 0);
while at < words.len() {
let class = words[at];
let mut end = at + 1;
while end < words.len() && words[end] == class {
end += 1;
}
written += mark(words, written, class, (end - at) as u32);
at = end;
}
canonical.truncate(written);
return;
}
for (o, copies) in decoded(key) {
canonical.extend([self.of(o), OccId::new(copies)]);
}
canonical
.as_chunks_mut::<2>()
.0
.sort_unstable_by_key(|[class, _]| *class);
let pairs = canonical.len() / 2;
let words = canonical.as_mut_slice();
let (mut written, mut at) = (0, 0);
while at < pairs {
let class = words[2 * at];
let mut copies = 0u32;
while at < pairs && words[2 * at] == class {
copies = copies
.checked_add(words[2 * at + 1].get())
.expect("fewer than 2³² copies of a class, as of a member");
at += 1;
}
written += mark(words, written, class, copies);
}
canonical.truncate(written);
}
pub(crate) fn of(&self, o: OccId) -> OccId {
self.class[o.index()]
}
pub(crate) fn same(&self, x: OccId, y: OccId) -> bool {
self.of(x) == self.of(y)
}
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::*;
use crate::linear::Sequent;
use crate::linear::search::focus::context::Context;
#[test]
fn classes() {
use crate::linear::sequents::Kind;
let s: Sequent = "0, a, a |- top".parse().unwrap();
let forest = Forest::new(&s).unwrap();
let roots = |kind| -> Vec<OccId> {
let roots = forest.roots().iter().copied();
roots.filter(|&r| forest.kind(r) == kind).collect()
};
let (tops, literals) = (roots(Kind::Top), roots(Kind::DualAtom));
assert_eq!((tops.len(), literals.len()), (2, 2));
let classes = Classes::new(&forest, None);
assert!(classes.same(tops[0], tops[1]));
assert!(classes.same(literals[0], literals[1]));
assert!(!classes.same(tops[0], literals[0]));
assert_eq!(classes.of(literals[1]), literals[0]);
assert!(!classes.distinct());
let mut gamma = Context::empty(forest.len());
for o in [literals[1], literals[1], literals[0], tops[1]] {
gamma.insert(o);
}
let mut words = Vec::new();
gamma.key_into(&mut words);
assert!(classes.renames(&gamma) && classes.renames_any(&words));
let mut canonical = Vec::new();
classes.canonical(&words, true, &mut canonical);
let three = [OccId::new(literals[0].get() | REPEATED), OccId::new(3)];
let expected = if literals[0] < tops[0] {
[three.as_slice(), &[tops[0]]].concat()
} else {
[[tops[0]].as_slice(), &three].concat()
};
assert_eq!(canonical, expected);
assert!(!classes.renames_any(&canonical));
let mut again = Vec::new();
classes.canonical(&canonical, true, &mut again);
assert_eq!(again, canonical);
let pair = [literals[0], literals[1]];
classes.canonical(&pair, false, &mut again);
assert_eq!(
again,
[OccId::new(literals[0].get() | REPEATED), OccId::new(2)]
);
let reading = Reading::new(&forest).unwrap();
let classes = Classes::new(&forest, Some(&reading));
assert!(!classes.same(tops[0], tops[1]));
assert!(classes.same(literals[0], literals[1]));
}
}