qleisli 0.2.2

Experimental quantum language with linear ownership, exact contracts and independent finite IR verification
Documentation
//! Bounded exact linear implication by rational relaxation of integer constraints.
//! Unsatisfiability proves an obligation; incomplete search never supplies evidence.
use super::ast::{Compare, NatKind, Natural, Predicate};
use super::{Error, Result, Span};
use std::collections::{BTreeMap, BTreeSet};

#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub(super) struct Linear {
    pub constant: i128,
    pub terms: BTreeMap<String, i128>,
}
impl Linear {
    pub fn constant(n: i128) -> Self {
        Self {
            constant: n,
            terms: BTreeMap::new(),
        }
    }
    pub fn variable(name: &str) -> Self {
        Self {
            constant: 0,
            terms: BTreeMap::from([(name.into(), 1)]),
        }
    }
    pub fn scale(&self, n: i128) -> Result<Self> {
        let overflow = || Error::new("limit", Span::default(), "linear arithmetic overflow");
        Ok(Self {
            constant: self.constant.checked_mul(n).ok_or_else(overflow)?,
            terms: self
                .terms
                .iter()
                .filter_map(|(key, value)| {
                    let value = value.checked_mul(n);
                    match value {
                        Some(0) => None,
                        Some(n) => Some(Ok((key.clone(), n))),
                        None => Some(Err(overflow())),
                    }
                })
                .collect::<Result<_>>()?,
        })
    }
    pub fn add(&self, b: &Self) -> Result<Self> {
        let mut r = self.clone();
        r.constant = r
            .constant
            .checked_add(b.constant)
            .ok_or_else(|| Error::new("limit", Span::default(), "linear constant overflow"))?;
        for (key, value) in &b.terms {
            let previous = r.terms.get(key).copied().unwrap_or(0);
            let n = previous.checked_add(*value).ok_or_else(|| {
                Error::new("limit", Span::default(), "linear coefficient overflow")
            })?;
            if n == 0 {
                r.terms.remove(key);
            } else {
                r.terms.insert(key.clone(), n);
            }
        }
        Ok(r)
    }
    pub fn sub(&self, b: &Self) -> Result<Self> {
        self.add(&b.scale(-1)?)
    }
}
#[derive(Clone, Debug)]
pub(super) struct Context {
    pub alternatives: Vec<Vec<Linear>>,
}
impl Context {
    pub fn natural(names: impl IntoIterator<Item = String>) -> Result<Self> {
        Ok(Self {
            alternatives: vec![
                names
                    .into_iter()
                    .map(|n| Linear::variable(&n).scale(-1))
                    .collect::<Result<_>>()?,
            ],
        })
    }
    pub fn push(&self, inequalities: &[Linear]) -> Self {
        Self {
            alternatives: self
                .alternatives
                .iter()
                .map(|a| a.iter().chain(inequalities).cloned().collect())
                .collect(),
        }
    }
    pub fn compare(&self, left: Linear, op: Compare, right: Linear, truth: bool) -> Result<Self> {
        let difference = left.sub(&right)?;
        let neg = difference.scale(-1)?;
        let one = Linear::constant(1);
        let op = if truth {
            op
        } else {
            match op {
                Compare::Eq => Compare::Ne,
                Compare::Ne => Compare::Eq,
                Compare::Le => Compare::Gt,
                Compare::Lt => Compare::Ge,
                Compare::Ge => Compare::Lt,
                Compare::Gt => Compare::Le,
            }
        };
        let branches = match op {
            Compare::Eq => vec![vec![difference, neg]],
            Compare::Ne => vec![vec![difference.add(&one)?], vec![neg.add(&one)?]],
            Compare::Le => vec![vec![difference]],
            Compare::Lt => vec![vec![difference.add(&one)?]],
            Compare::Ge => vec![vec![neg]],
            Compare::Gt => vec![vec![neg.add(&one)?]],
        };
        if self.alternatives.len().saturating_mul(branches.len()) > 64 {
            return Err(Error::new(
                "limit",
                Span::default(),
                "static branch alternatives exceed 64",
            ));
        }
        Ok(Self {
            alternatives: self
                .alternatives
                .iter()
                .flat_map(|a| {
                    branches
                        .iter()
                        .map(move |b| a.iter().chain(b).cloned().collect())
                })
                .collect(),
        })
    }
    pub fn proves_le(&self, a: &Linear, b: &Linear) -> Result<bool> {
        let counterexample = b.sub(a)?.add(&Linear::constant(1))?;
        for context in &self.alternatives {
            let mut constraints = context.clone();
            constraints.push(counterexample.clone());
            if !unsatisfiable(constraints)? {
                return Ok(false);
            }
        }
        Ok(true)
    }
    pub fn feasible(&self) -> Result<bool> {
        for a in &self.alternatives {
            if !unsatisfiable(a.clone())? {
                return Ok(true);
            }
        }
        Ok(false)
    }
}
fn normalized(mut x: Linear) -> Result<Linear> {
    let mut divisor = 0u128;
    for n in std::iter::once(&x.constant).chain(x.terms.values()) {
        let mut a = divisor;
        let mut b = n.unsigned_abs();
        while b != 0 {
            let r = a % b;
            a = b;
            b = r;
        }
        divisor = a;
    }
    if divisor > 1 {
        let divisor = i128::try_from(divisor)
            .map_err(|_| Error::new("limit", Span::default(), "linear normalization overflow"))?;
        x.constant /= divisor;
        for value in x.terms.values_mut() {
            *value /= divisor;
        }
    }
    Ok(x)
}
fn unsatisfiable(mut constraints: Vec<Linear>) -> Result<bool> {
    let mut work = 0usize;
    loop {
        if constraints
            .iter()
            .any(|c| c.terms.is_empty() && c.constant > 0)
        {
            return Ok(true);
        }
        let variables: BTreeSet<_> = constraints
            .iter()
            .flat_map(|c| c.terms.keys().cloned())
            .collect();
        if variables.is_empty() {
            return Ok(false);
        }
        if variables.len() > 32 {
            return Err(Error::new(
                "limit",
                Span::default(),
                "linear implication exceeds 32 variables",
            ));
        }
        let name = variables
            .into_iter()
            .min_by_key(|name| {
                let p = constraints
                    .iter()
                    .filter(|c| c.terms.get(name).is_some_and(|x| *x > 0))
                    .count();
                let n = constraints
                    .iter()
                    .filter(|c| c.terms.get(name).is_some_and(|x| *x < 0))
                    .count();
                p.saturating_mul(n)
            })
            .unwrap();
        let mut positive = Vec::new();
        let mut negative = Vec::new();
        let mut retained = BTreeSet::new();
        for mut c in constraints {
            let n = c.terms.remove(&name).unwrap_or(0);
            match n.cmp(&0) {
                std::cmp::Ordering::Greater => positive.push((n, c)),
                std::cmp::Ordering::Less => negative.push((n, c)),
                std::cmp::Ordering::Equal => {
                    retained.insert(normalized(c)?);
                }
            }
        }
        for (p, a) in &positive {
            for (n, b) in &negative {
                work += 1;
                if work > 50_000 || retained.len() >= 4096 {
                    return Err(Error::new(
                        "limit",
                        Span::default(),
                        "linear implication work exhausted",
                    ));
                }
                retained.insert(normalized(
                    a.scale(n.checked_neg().ok_or_else(|| {
                        Error::new("limit", Span::default(), "linear elimination overflow")
                    })?)?
                    .add(&b.scale(*p)?)?,
                )?);
            }
        }
        constraints = retained.into_iter().collect();
    }
}
pub(super) fn natural(
    expr: &Natural,
    names: &BTreeMap<String, Linear>,
    context: &Context,
) -> Result<Linear> {
    let result = match &expr.kind {
        NatKind::Number(n) => Linear::constant(*n),
        NatKind::Name(name) => names.get(name).cloned().ok_or_else(|| {
            Error::new("static", expr.span, format!("unknown natural name {name}"))
        })?,
        NatKind::Add(a, b) => natural(a, names, context)?.add(&natural(b, names, context)?)?,
        NatKind::Sub(a, b) => {
            let a = natural(a, names, context)?;
            let b = natural(b, names, context)?;
            if !context.proves_le(&b, &a)? {
                return Err(Error::new(
                    "size",
                    expr.span,
                    "subtraction lacks a nonnegative guard",
                ));
            }
            a.sub(&b)?
        }
        NatKind::Mul(a, b) => {
            let a = natural(a, names, context)?;
            let b = natural(b, names, context)?;
            if a.terms.is_empty() {
                b.scale(a.constant)?
            } else if b.terms.is_empty() {
                a.scale(b.constant)?
            } else {
                return Err(Error::new(
                    "unsupported",
                    expr.span,
                    "multiplication of two symbolic sizes is nonlinear",
                ));
            }
        }
    };
    Ok(result)
}
pub(super) fn predicate(
    p: &Predicate,
    names: &BTreeMap<String, Linear>,
    context: &Context,
    truth: bool,
) -> Result<Context> {
    context.compare(
        natural(&p.left, names, context)?,
        p.comparison,
        natural(&p.right, names, context)?,
        truth,
    )
}