use crate::hash::HashMap;
use crate::limits::{Limits, Refusal, Space};
use crate::linear::occurrences::Forest;
use crate::linear::sequents::{Atom, Term, TermId};
use crate::{Error, linear::Sequent};
#[derive(Clone, Debug)]
#[non_exhaustive]
pub struct Problem {
pub sequent: Sequent,
pub expected: Option<Safety>,
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Safety {
Safe,
Unsafe,
}
#[expect(
clippy::missing_panics_doc,
reason = "the expects state facts of the problem the reader has checked"
)]
pub fn read(text: &str, limits: &Limits) -> Result<Problem, Error> {
let expected = text.lines().next().and_then(|line| {
let line = line.trim().strip_prefix('#')?.trim();
match line.strip_prefix("expected result:")?.trim() {
"safe" => Some(Safety::Safe),
"unsafe" => Some(Safety::Unsafe),
_ => None,
}
});
let tokens = tokens(text)?;
let mut reader = Reader { tokens, at: 0 };
reader.keyword("vars")?;
let mut names = Vec::new();
while !reader.at_keyword("rules") {
let name = reader.name()?;
crate::linear::sequents::name::check(name)?;
names.push(name);
}
let index: HashMap<&str, usize> = names.iter().enumerate().map(|(i, &n)| (n, i)).collect();
let counter = |name: &str| {
index
.get(name)
.copied()
.ok_or_else(|| error(format!("the counter `{name}` is not declared")))
};
reader.keyword("rules")?;
let mut clauses = Vec::new();
while !reader.at_keyword("init") {
clauses.push(reader.rule(&names, &counter)?);
}
reader.keyword("init")?;
let mut tokens = vec![0u32; names.len()];
let mut parameters = Vec::new();
let mut initial = vec![false; names.len()];
while !reader.at_keyword("target") {
let name = reader.name()?;
let x = counter(name)?;
if std::mem::replace(&mut initial[x], true) {
return Err(error(format!(
"the counter `{name}` is given twice in `init`"
)));
}
let at_least = match reader.next()? {
Token::Word("=") => false,
Token::Word(">=") => true,
token => return Err(error(format!("expected `=` or `>=` at {token}"))),
};
tokens[x] = reader.number()?;
if at_least {
parameters.push(x);
}
reader.comma_or_line();
}
reader.keyword("target")?;
let mut targets = Vec::new();
let mut target = Vec::new();
while !reader.at_keyword("invariants") && reader.at < reader.tokens.len() {
let name = reader.name()?;
let x = counter(name)?;
reader.word(">=")?;
target.push((x, reader.number()?));
if !reader.comma_or_line() {
targets.push(merged(std::mem::take(&mut target)));
}
}
if !target.is_empty() {
targets.push(merged(target));
}
if targets.is_empty() {
return Err(error("no target".to_owned()));
}
let total = |counts: &[(usize, u32)]| counts.iter().map(|&(_, k)| u64::from(k)).sum::<u64>();
let tokens_written = tokens
.iter()
.map(|&k| u64::from(k))
.chain(clauses.iter().map(|(i, o)| total(i) + total(o)))
.chain(targets.iter().map(|t| total(t)))
.fold(0u64, u64::saturating_add);
if let Some(limit) = limits.occurrences
&& tokens_written > limit
{
return Err(Error::Refused(Refusal::Occurrences {
occurrences: tokens_written,
limit,
}));
}
if tokens_written > Forest::MOST {
return Err(Error::Refused(Refusal::Index {
what: Space::Occurrence,
count: tokens_written,
most: Forest::MOST,
}));
}
let mut arena = Arena::new(&names);
let mut roots = Vec::new();
for (inputs, outputs) in &clauses {
let (taken, given) = (arena.tensor(inputs), arena.par_of_duals(outputs));
let clause = arena.push(Term::Tensor(taken, given));
roots.push(arena.push(Term::Quest(clause)));
}
let goal = if let [target] = &targets[..] {
arena.tensor(target)
} else {
let name = (0..)
.map(|i| {
if i == 0 {
"goal".to_owned()
} else {
format!("goal_{i}")
}
})
.find(|name| !index.contains_key(name.as_str()))
.expect("some name is fresh");
let goal = arena.fresh(name);
for target in &targets {
let covered = arena.tensor(target);
let reached = arena.push(Term::DualAtom(goal));
let clause = arena.push(Term::Tensor(covered, reached));
roots.push(arena.push(Term::Quest(clause)));
}
arena.push(Term::Atom(goal))
};
for &x in ¶meters {
let dual = arena.dual(x);
roots.push(arena.push(Term::Quest(dual)));
}
for (x, &k) in tokens.iter().enumerate() {
if k > 0 {
let dual = arena.dual(x);
roots.extend(std::iter::repeat_n(dual, k as usize));
}
}
roots.push(goal);
let antecedents = Some(antecedents(roots.len())?);
let mut sequent = Sequent::from_parts(arena.terms, roots, arena.atoms, antecedents);
sequent.optimize();
Ok(Problem { sequent, expected })
}
fn antecedents(roots: usize) -> Result<u32, Error> {
let count = roots.saturating_sub(1);
u32::try_from(count).map_err(|_| {
Error::Refused(Refusal::Index {
what: Space::Member,
count: u64::try_from(count).unwrap_or(u64::MAX),
most: u64::from(u32::MAX),
})
})
}
struct Arena<'a> {
names: &'a [&'a str],
terms: Vec<Term>,
atoms: Vec<String>,
made: Vec<(Option<Atom>, Option<TermId>, Option<TermId>)>,
}
impl<'a> Arena<'a> {
fn new(names: &'a [&'a str]) -> Self {
Self {
names,
terms: Vec::new(),
atoms: Vec::new(),
made: vec![(None, None, None); names.len()],
}
}
fn push(&mut self, term: Term) -> TermId {
self.terms.push(term);
TermId::new(self.terms.len() as u32 - 1)
}
fn fresh(&mut self, name: String) -> Atom {
self.atoms.push(name);
Atom::new(self.atoms.len() as u32 - 1)
}
fn atom(&mut self, x: usize) -> Atom {
if let Some(atom) = self.made[x].0 {
return atom;
}
let atom = self.fresh(self.names[x].to_owned());
self.made[x].0 = Some(atom);
atom
}
fn var(&mut self, x: usize) -> TermId {
if let Some(var) = self.made[x].1 {
return var;
}
let atom = self.atom(x);
let var = self.push(Term::Atom(atom));
self.made[x].1 = Some(var);
var
}
fn dual(&mut self, x: usize) -> TermId {
if let Some(dual) = self.made[x].2 {
return dual;
}
let atom = self.atom(x);
let dual = self.push(Term::DualAtom(atom));
self.made[x].2 = Some(dual);
dual
}
fn tensor(&mut self, counts: &[(usize, u32)]) -> TermId {
let mut tensor = None;
for &(x, k) in counts {
let var = self.var(x);
for _ in 0..k {
tensor = Some(match tensor {
None => var,
Some(left) => self.push(Term::Tensor(left, var)),
});
}
}
tensor.unwrap_or_else(|| self.push(Term::One))
}
fn par_of_duals(&mut self, counts: &[(usize, u32)]) -> TermId {
let mut par = None;
for &(x, k) in counts {
let dual = self.dual(x);
for _ in 0..k {
par = Some(match par {
None => dual,
Some(left) => self.push(Term::Par(left, dual)),
});
}
}
par.unwrap_or_else(|| self.push(Term::Bot))
}
}
fn error(message: String) -> Error {
Error::Spec { message }
}
type Counts = Vec<(usize, u32)>;
fn merged(mut counts: Counts) -> Counts {
counts.sort_unstable();
let mut merged: Counts = Vec::with_capacity(counts.len());
for (x, k) in counts {
match merged.last_mut() {
Some((y, m)) if *y == x => *m = (*m).max(k),
_ => merged.push((x, k)),
}
}
merged.retain(|&(_, k)| k > 0);
merged
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Token<'a> {
Word(&'a str),
Line,
}
impl std::fmt::Display for Token<'_> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Token::Word(word) => write!(f, "`{word}`"),
Token::Line => f.write_str("the end of a line"),
}
}
}
fn tokens(text: &str) -> Result<Vec<Token<'_>>, Error> {
let mut tokens = Vec::new();
for line in text.lines() {
let line = line.split_once('#').map_or(line, |(code, _)| code);
let mut at = 0;
while at < line.len() {
let rest = &line[at..];
let c = rest.chars().next().expect("not at the end");
let length = if c.is_whitespace() {
at += c.len_utf8();
continue;
} else if c.is_ascii_alphanumeric() || c == '_' {
rest.find(|c: char| !(c.is_ascii_alphanumeric() || c == '_'))
.unwrap_or(rest.len())
} else if rest.starts_with(">=") || rest.starts_with("->") {
2
} else if "=+-,;'".contains(c) {
1
} else {
return Err(error(format!("unexpected `{c}`")));
};
tokens.push(Token::Word(&rest[..length]));
at += length;
}
tokens.push(Token::Line);
}
Ok(tokens)
}
struct Reader<'a> {
tokens: Vec<Token<'a>>,
at: usize,
}
impl<'a> Reader<'a> {
fn skip_lines(&mut self) {
while self.tokens.get(self.at) == Some(&Token::Line) {
self.at += 1;
}
}
fn next(&mut self) -> Result<Token<'a>, Error> {
self.skip_lines();
let token = *self
.tokens
.get(self.at)
.ok_or_else(|| error("the file ends early".to_owned()))?;
self.at += 1;
Ok(token)
}
fn at_keyword(&mut self, keyword: &str) -> bool {
self.skip_lines();
self.tokens.get(self.at) == Some(&Token::Word(keyword))
}
fn word(&mut self, word: &str) -> Result<(), Error> {
match self.next()? {
Token::Word(w) if w == word => Ok(()),
token => Err(error(format!("expected `{word}` at {token}"))),
}
}
fn keyword(&mut self, keyword: &str) -> Result<(), Error> {
self.word(keyword)
.map_err(|_| error(format!("expected the section `{keyword}`")))
}
fn name(&mut self) -> Result<&'a str, Error> {
match self.next()? {
Token::Word(w) if w.starts_with(|c: char| c.is_ascii_alphabetic() || c == '_') => Ok(w),
token => Err(error(format!("expected a name at {token}"))),
}
}
fn number(&mut self) -> Result<u32, Error> {
match self.next()? {
Token::Word(w) => w
.parse()
.map_err(|_| error(format!("expected a number below 2³² at `{w}`"))),
token => Err(error(format!("expected a number at {token}"))),
}
}
fn comma_or_line(&mut self) -> bool {
let mut at = self.at;
while self.tokens.get(at) == Some(&Token::Line) {
at += 1;
}
match self.tokens.get(at) {
Some(Token::Word(",")) => {
self.at = at + 1;
true
}
Some(Token::Word(_)) => at == self.at,
_ => false,
}
}
fn rule(
&mut self,
names: &[&str],
counter: &dyn Fn(&str) -> Result<usize, Error>,
) -> Result<(Counts, Counts), Error> {
let mut guards = Vec::new();
let mut changes: Vec<(usize, i64)> = Vec::new();
if !matches!(self.tokens.get(self.at), Some(Token::Word("->"))) {
loop {
let x = counter(self.name()?)?;
self.word(">=")?;
guards.push((x, self.number()?));
match self.next()? {
Token::Word(",") => {}
Token::Word("->") => break,
token => return Err(error(format!("expected `,` or `->` at {token}"))),
}
}
} else {
self.at += 1;
}
loop {
if let Ok(Token::Word(";")) = self.peek() {
self.at += 1;
break;
}
let name = self.name()?;
let x = counter(name)?;
self.word("'")?;
self.word("=")?;
if self.name()? != name {
return Err(error(format!("`{name}'` is updated from another counter")));
}
let sign = match self.next()? {
Token::Word("+") => 1,
Token::Word("-") => -1,
token => return Err(error(format!("expected `+` or `-` at {token}"))),
};
let k = i64::from(self.number()?);
changes.push((x, sign * k));
match self.next()? {
Token::Word(",") => {}
Token::Word(";") => break,
token => return Err(error(format!("expected `,` or `;` at {token}"))),
}
}
let guards = merged(guards);
changes.sort_unstable();
if let Some(pair) = changes.windows(2).find(|pair| pair[0].0 == pair[1].0) {
return Err(error(format!(
"a rule updates `{}` twice",
names[pair[0].0]
)));
}
let (mut inputs, mut outputs) = (Vec::new(), Vec::new());
let (mut g, mut c) = (0, 0);
while g < guards.len() || c < changes.len() {
let x = match (guards.get(g), changes.get(c)) {
(Some(&(a, _)), Some(&(b, _))) => a.min(b),
(Some(&(a, _)), None) => a,
(None, Some(&(b, _))) => b,
(None, None) => unreachable!("the loop's condition"),
};
let guard = match guards.get(g) {
Some(&(y, k)) if y == x => {
g += 1;
k
}
_ => 0,
};
let change = match changes.get(c) {
Some(&(y, d)) if y == x => {
c += 1;
d
}
_ => 0,
};
let taken = i64::from(guard).max(-change);
let given = u32::try_from(taken + change)
.map_err(|_| error(format!("a rule gives `{}` 2³² tokens or more", names[x])))?;
let taken = u32::try_from(taken).expect("a guard or a decrement");
if taken > 0 {
inputs.push((x, taken));
}
if given > 0 {
outputs.push((x, given));
}
}
Ok((inputs, outputs))
}
fn peek(&mut self) -> Result<Token<'a>, Error> {
let token = self.next()?;
self.at -= 1;
Ok(token)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
#[cfg(target_pointer_width = "64")]
fn refuses_more_antecedents_than_a_sequent_counts() {
let most = usize::try_from(u32::MAX).unwrap();
assert_eq!(antecedents(most + 1), Ok(u32::MAX));
assert_eq!(
antecedents(most + 2),
Err(Error::Refused(Refusal::Index {
what: Space::Member,
count: u64::from(u32::MAX) + 1,
most: u64::from(u32::MAX),
}))
);
}
#[test]
fn reads_problems() {
let text = "# a comment\n\
vars\n a b c\n\
rules\n a >= 2 ->\n a' = a - 1,\n b' = b + 1;\n\
\x20 b >= 1 -> c' = c - 1; # takes a c it does not test\n\
\x20 -> a' = a + 1;\n\
init\n a = 1\n , b >= 2\n\
target\n c >= 1,\n b >= 1\n a >= 3\n\
invariants\n a = 1, b = 1\n";
let problem = read(text, &Limits::default()).unwrap();
assert_eq!(problem.expected, None);
let expected: Sequent = "!(a * a -o a * b), !(b * c -o b), !(1 -o a), \
!(b * c -o goal), !(a * a * a -o goal), !b, a, b, b |- goal"
.parse()
.unwrap();
let formulas = |sequent: &Sequent| {
let mut formulas: Vec<String> = sequent.to_string()[4..]
.split(", ")
.map(str::to_owned)
.collect();
formulas.sort();
formulas
};
assert_eq!(formulas(&problem.sequent), formulas(&expected));
for bad in [
"rules init target a >= 1",
"vars a rules init a = 1",
"vars a rules a >= 1 -> b' = b + 1; init target a >= 1",
"vars a b rules a >= 1 -> a' = b + 1; init target a >= 1",
"vars a rules a >= 1 -> a' = a + 1, a' = a - 1; init target a >= 1",
"vars a b rules a >= 4 -> a' = a - 4, b' = b + 1; init a >= 1, a = 3 target b >= 1",
"vars a rules init a = 4294967296 target a >= 1",
] {
assert!(
matches!(read(bad, &Limits::default()), Err(Error::Spec { .. })),
"{bad:?}"
);
}
for bad in [
"vars top rules init target top >= 1",
"vars forall rules init target forall >= 1",
] {
assert!(
matches!(read(bad, &Limits::default()), Err(Error::AtomName { .. })),
"{bad:?}"
);
}
for (header, expected) in [
("# expected result: safe", Some(Safety::Safe)),
("#expected result: unsafe", Some(Safety::Unsafe)),
("# expected result: maybe", None),
] {
let text = format!("{header}\nvars a rules init a = 1 target a >= 1");
let problem = read(&text, &Limits::default()).unwrap();
assert_eq!(problem.expected, expected, "{header}");
}
let text = "vars a b rules a >= 1, a >= 3, b >= 0 -> b' = b + 1; init a = 3 target b >= 1";
let problem = read(text, &Limits::default()).unwrap();
let expected: Sequent = "!(a * a * a -o a * a * a * b), a, a, a |- b"
.parse()
.unwrap();
assert_eq!(formulas(&problem.sequent), formulas(&expected));
for (text, message) in [
(
"vars a rules a >= 1 -> a' - a + 1; init a = 1 target a >= 1",
"expected `=` at `-`",
),
(
"vars 1x rules init target a >= 1",
"expected a name at `1x`",
),
(
"vars a b rules a >= 1 -> a' = b + 1; init target a >= 1",
"`a'` is updated from another counter",
),
] {
match read(text, &Limits::default()) {
Err(Error::Spec { message: m }) => assert_eq!(m, message, "{text}"),
other => panic!("{text}: {other:?}"),
}
}
let big = "vars a rules init a = 99999 target a >= 1";
let limits = |n| Limits::default().with_occurrences(Some(n));
assert!(super::read(big, &limits(100_000)).is_ok());
assert!(matches!(
super::read(big, &limits(99_999)),
Err(Error::Refused(Refusal::Occurrences { .. }))
));
let rule = "vars a b rules a >= 2 -> a' = a - 2, b' = b + 3; init a = 4 target b >= 3";
assert!(super::read(rule, &limits(12)).is_ok());
assert!(matches!(
super::read(rule, &limits(11)),
Err(Error::Refused(Refusal::Occurrences {
occurrences: 12,
..
}))
));
}
}