use crate::Error;
use crate::linear::sequents::{Kind, Sequent};
use std::fmt::{Display, Formatter, Result as FmtResult};
use std::ops::{BitAnd, BitOr, BitOrAssign};
use std::str::FromStr;
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
pub struct Fragment(u8);
impl Fragment {
pub const EMPTY: Self = Self(0);
pub const MULTIPLICATIVES: Self = Self(1);
pub const MULTIPLICATIVE_UNITS: Self = Self(2);
pub const ADDITIVES: Self = Self(4);
pub const ADDITIVE_UNITS: Self = Self(8);
pub const EXPONENTIALS: Self = Self(16);
pub const QUANTIFIERS: Self = Self(32);
pub const MLL: Self = Self::MULTIPLICATIVES;
pub const MLL_WITH_UNITS: Self = Self::MLL.union(Self::MULTIPLICATIVE_UNITS);
pub const ADDITIVE: Self = Self::ADDITIVES.union(Self::ADDITIVE_UNITS);
pub const MALL: Self = Self::MLL_WITH_UNITS.union(Self::ADDITIVE);
pub const MELL: Self = Self::MLL_WITH_UNITS.union(Self::EXPONENTIALS);
pub const LL: Self = Self::MALL.union(Self::EXPONENTIALS);
pub const MLL1: Self = Self::MLL.union(Self::QUANTIFIERS);
pub const MLL1_WITH_UNITS: Self = Self::MLL_WITH_UNITS.union(Self::QUANTIFIERS);
pub const ADDITIVE1: Self = Self::ADDITIVE.union(Self::QUANTIFIERS);
pub const MALL1: Self = Self::MALL.union(Self::QUANTIFIERS);
pub const MELL1: Self = Self::MELL.union(Self::QUANTIFIERS);
pub const LL1: Self = Self::LL.union(Self::QUANTIFIERS);
pub const NAMED: &'static [Self] = &[
Self::MLL,
Self::MLL_WITH_UNITS,
Self::ADDITIVE,
Self::MALL,
Self::MELL,
Self::LL,
Self::MLL1,
Self::MLL1_WITH_UNITS,
Self::ADDITIVE1,
Self::MALL1,
Self::MELL1,
Self::LL1,
];
pub const NAMES: &'static [&'static str] = &[
"MLL",
"MLL with units",
"ALL",
"MALL",
"MELL",
"LL",
"MLL1",
"MLL1 with units",
"ALL1",
"MALL1",
"MELL1",
"LL1",
];
#[must_use]
pub const fn union(self, other: Self) -> Self {
Self(self.0 | other.0)
}
#[must_use]
pub const fn intersection(self, other: Self) -> Self {
Self(self.0 & other.0)
}
pub const fn contains(self, other: Self) -> bool {
self.0 & other.0 == other.0
}
pub const fn is_empty(self) -> bool {
self.0 == 0
}
pub const fn has_multiplicatives(self) -> bool {
self.contains(Self::MULTIPLICATIVES)
}
pub const fn has_multiplicative_units(self) -> bool {
self.contains(Self::MULTIPLICATIVE_UNITS)
}
pub const fn has_additives(self) -> bool {
self.contains(Self::ADDITIVES)
}
pub const fn has_additive_units(self) -> bool {
self.contains(Self::ADDITIVE_UNITS)
}
pub const fn has_exponentials(self) -> bool {
self.contains(Self::EXPONENTIALS)
}
pub const fn has_quantifiers(self) -> bool {
self.contains(Self::QUANTIFIERS)
}
pub const fn has_nets(self) -> bool {
Self::MLL.contains(self)
}
pub const fn name(self) -> &'static str {
let additive = self.has_additives() || self.has_additive_units();
let multiplicative = self.has_multiplicatives() || self.has_multiplicative_units();
let units = self.has_multiplicative_units();
match (
self.has_quantifiers(),
self.has_exponentials(),
additive,
multiplicative,
) {
(false, true, true, _) => "LL",
(false, true, false, _) => "MELL",
(false, false, true, true) => "MALL",
(false, false, true, false) => "ALL",
(false, false, false, _) if units => "MLL with units",
(false, false, false, _) => "MLL",
(true, true, true, _) => "LL1",
(true, true, false, _) => "MELL1",
(true, false, true, true) => "MALL1",
(true, false, true, false) => "ALL1",
(true, false, false, _) if units => "MLL1 with units",
(true, false, false, _) => "MLL1",
}
}
pub const fn name_in(self, mode: Mode) -> &'static str {
if !mode.is_intuitionistic() {
return self.name();
}
let additive = self.has_additives() || self.has_additive_units();
let multiplicative = self.has_multiplicatives() || self.has_multiplicative_units();
let units = self.has_multiplicative_units();
match (
self.has_quantifiers(),
self.has_exponentials(),
additive,
multiplicative,
) {
(false, true, true, _) => "ILL",
(false, true, false, _) => "IMELL",
(false, false, true, true) => "IMALL",
(false, false, true, false) => "IALL",
(false, false, false, _) if units => "IMLL with units",
(false, false, false, _) => "IMLL",
(true, true, true, _) => "ILL1",
(true, true, false, _) => "IMELL1",
(true, false, true, true) => "IMALL1",
(true, false, true, false) => "IALL1",
(true, false, false, _) if units => "IMLL1 with units",
(true, false, false, _) => "IMLL1",
}
}
}
impl FromStr for Fragment {
type Err = Error;
fn from_str(name: &str) -> Result<Self, Error> {
let classical = name.strip_prefix('I').unwrap_or(name);
Self::NAMES
.iter()
.position(|n| *n == classical)
.map(|i| Self::NAMED[i])
.ok_or_else(|| Error::UnknownName {
what: "fragment",
name: name.into(),
known: Self::NAMES,
})
}
}
impl BitOr for Fragment {
type Output = Self;
fn bitor(self, other: Self) -> Self {
self.union(other)
}
}
impl BitOrAssign for Fragment {
fn bitor_assign(&mut self, other: Self) {
*self = self.union(other);
}
}
impl BitAnd for Fragment {
type Output = Self;
fn bitand(self, other: Self) -> Self {
self.intersection(other)
}
}
impl Display for Fragment {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
f.write_str(self.name())
}
}
impl Kind {
pub const fn fragment(self) -> Fragment {
use Kind::*;
match self {
Atom | DualAtom => Fragment::EMPTY,
Tensor | Par => Fragment::MULTIPLICATIVES,
One | Bot => Fragment::MULTIPLICATIVE_UNITS,
With | Plus => Fragment::ADDITIVES,
Top | Zero => Fragment::ADDITIVE_UNITS,
Bang | Quest => Fragment::EXPONENTIALS,
Forall | Exists => Fragment::QUANTIFIERS,
}
}
}
impl Sequent {
#[cfg_attr(feature = "parse", doc = "```")]
#[cfg_attr(not(feature = "parse"), doc = "```ignore")]
pub fn fragment(&self) -> Fragment {
let mut fragment = Fragment::EMPTY;
let mut reachable = vec![false; self.terms.len()];
for root in self.roots.iter().chain(self.cuts.iter().flatten()) {
reachable[root.index()] = true;
}
for (n, term) in self.terms.iter().enumerate().rev() {
if !reachable[n] {
continue;
}
fragment |= term.kind().fragment();
for k in term.subterms() {
reachable[k.index()] = true;
}
}
fragment
}
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
#[non_exhaustive]
pub struct Mode {
pub(crate) intuitionistic: bool,
pub(crate) affine: bool,
pub(crate) mix: bool,
pub(crate) order: Order,
pub(crate) empty_antecedents: bool,
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
pub enum Order {
#[default]
Commutative,
Cyclic,
}
impl Mode {
pub const CLASSICAL: Self = Self {
intuitionistic: false,
affine: false,
mix: false,
order: Order::Commutative,
empty_antecedents: false,
};
pub const INTUITIONISTIC: Self = Self {
intuitionistic: true,
affine: false,
mix: false,
order: Order::Commutative,
empty_antecedents: false,
};
pub const CYCLIC: Self = Self {
intuitionistic: false,
affine: false,
mix: false,
order: Order::Cyclic,
empty_antecedents: false,
};
pub const LAMBEK: Self = Self {
intuitionistic: true,
affine: false,
mix: false,
order: Order::Cyclic,
empty_antecedents: false,
};
pub const NAMES: &'static [&'static str] = &[
"classical",
"affine",
"mix",
"affine-mix",
"intuitionistic",
"intuitionistic-affine",
"cyclic",
"lambek",
"lambek-star",
];
pub const fn is_intuitionistic(self) -> bool {
self.intuitionistic
}
pub const fn is_affine(self) -> bool {
self.affine
}
pub const fn has_mix(self) -> bool {
self.mix
}
pub const fn order(self) -> Order {
self.order
}
pub const fn is_ordered(self) -> bool {
!matches!(self.order, Order::Commutative)
}
#[must_use]
pub const fn with_affine(self) -> Self {
Self {
affine: true,
..self
}
}
#[must_use]
pub const fn with_mix(self) -> Self {
Self { mix: true, ..self }
}
#[must_use]
pub const fn with_empty_antecedents(self) -> Self {
Self {
empty_antecedents: self.intuitionistic && self.is_ordered(),
..self
}
}
pub const fn allows_empty_antecedents(self) -> bool {
!(self.intuitionistic && self.is_ordered()) || self.empty_antecedents
}
pub const fn name(self) -> &'static str {
let Self {
intuitionistic,
affine,
mix,
order,
empty_antecedents: star,
} = self;
match (order, intuitionistic, affine, mix) {
(Order::Commutative, false, false, false) => "classical",
(Order::Commutative, false, true, false) => "affine",
(Order::Commutative, false, false, true) => "mix",
(Order::Commutative, false, true, true) => "affine-mix",
(Order::Commutative, true, false, false) => "intuitionistic",
(Order::Commutative, true, true, false) => "intuitionistic-affine",
(Order::Commutative, true, false, true) => "intuitionistic-mix",
(Order::Commutative, true, true, true) => "intuitionistic-affine-mix",
(Order::Cyclic, false, false, false) => "cyclic",
(Order::Cyclic, false, true, false) => "cyclic-affine",
(Order::Cyclic, false, false, true) => "cyclic-mix",
(Order::Cyclic, false, true, true) => "cyclic-affine-mix",
(Order::Cyclic, true, false, false) if star => "lambek-star",
(Order::Cyclic, true, false, false) => "lambek",
(Order::Cyclic, true, true, false) if star => "lambek-star-affine",
(Order::Cyclic, true, true, false) => "lambek-affine",
(Order::Cyclic, true, false, true) if star => "lambek-star-mix",
(Order::Cyclic, true, false, true) => "lambek-mix",
(Order::Cyclic, true, true, true) if star => "lambek-star-affine-mix",
(Order::Cyclic, true, true, true) => "lambek-affine-mix",
}
}
pub const fn check(self) -> Result<(), Error> {
if self.is_ordered() && (self.affine || self.mix) {
Err(Error::OrderedMode { mode: self })
} else if self.intuitionistic && self.mix {
Err(Error::IntuitionisticMix)
} else {
Ok(())
}
}
}
impl FromStr for Mode {
type Err = Error;
fn from_str(name: &str) -> Result<Self, Error> {
let mode = match name {
"classical" => Self::CLASSICAL,
"affine" => Self::CLASSICAL.with_affine(),
"mix" => Self::CLASSICAL.with_mix(),
"affine-mix" => Self::CLASSICAL.with_affine().with_mix(),
"intuitionistic" => Self::INTUITIONISTIC,
"intuitionistic-affine" => Self::INTUITIONISTIC.with_affine(),
"cyclic" => Self::CYCLIC,
"lambek" => Self::LAMBEK,
"lambek-star" => Self::LAMBEK.with_empty_antecedents(),
_ => {
return Err(Error::UnknownName {
what: "mode",
name: name.into(),
known: Self::NAMES,
});
}
};
Ok(mode)
}
}
impl Display for Mode {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
f.write_str(match (self.is_ordered(), self.intuitionistic) {
(false, false) => "classical",
(false, true) => "intuitionistic",
(true, false) => "cyclic",
(true, true) => "Lambek",
})?;
if self.affine {
f.write_str(" affine")?;
}
if self.mix {
f.write_str(" with Mix")?;
}
if self.empty_antecedents {
f.write_str(" with empty antecedents")?;
}
Ok(())
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn named_fragments_nest() {
use Fragment as F;
assert!(F::MLL_WITH_UNITS.contains(F::MLL));
assert!(F::MALL.contains(F::MLL_WITH_UNITS));
assert!(F::MALL.contains(F::ADDITIVE));
assert!(F::MELL.contains(F::MLL_WITH_UNITS));
assert!(F::LL.contains(F::MALL));
assert!(F::LL.contains(F::MELL));
assert!(!F::MALL.contains(F::MELL));
assert!(!F::MELL.contains(F::ADDITIVE));
assert!(!F::MLL.contains(F::MULTIPLICATIVE_UNITS));
assert!(F::EMPTY.is_empty());
assert!(!F::MLL.is_empty());
assert_eq!(F::MALL & F::MELL, F::MLL_WITH_UNITS);
assert_eq!(F::ADDITIVE | F::EXPONENTIALS | F::MLL_WITH_UNITS, F::LL);
}
#[test]
fn names() {
use Fragment as F;
for (fragment, name) in [
(F::EMPTY, "MLL"),
(F::MLL, "MLL"),
(F::MULTIPLICATIVE_UNITS, "MLL with units"),
(F::MLL_WITH_UNITS, "MLL with units"),
(F::ADDITIVES, "ALL"),
(F::ADDITIVE_UNITS, "ALL"),
(F::ADDITIVE, "ALL"),
(F::MLL | F::ADDITIVES, "MALL"),
(F::MULTIPLICATIVE_UNITS | F::ADDITIVE_UNITS, "MALL"),
(F::MALL, "MALL"),
(F::EXPONENTIALS, "MELL"),
(F::MLL | F::EXPONENTIALS, "MELL"),
(F::MELL, "MELL"),
(F::ADDITIVES | F::EXPONENTIALS, "LL"),
(F::MELL | F::ADDITIVE_UNITS, "LL"),
(F::LL, "LL"),
] {
assert_eq!(fragment.to_string(), name, "{fragment:?}");
}
}
#[test]
fn intuitionistic_names() {
use Fragment as F;
for (fragment, name) in [
(F::EMPTY, "IMLL"),
(F::MLL, "IMLL"),
(F::MLL_WITH_UNITS, "IMLL with units"),
(F::ADDITIVE, "IALL"),
(F::MALL, "IMALL"),
(F::MELL, "IMELL"),
(F::LL, "ILL"),
] {
assert_eq!(fragment.name_in(Mode::INTUITIONISTIC), name, "{fragment:?}");
assert_eq!(
fragment.name_in(Mode::INTUITIONISTIC.with_affine()),
name,
"{fragment:?}"
);
assert_eq!(
fragment.name_in(Mode::CLASSICAL),
fragment.name(),
"{fragment:?}"
);
}
}
#[test]
fn names_read_back() {
let modes = [
Mode::CLASSICAL,
Mode::CLASSICAL.with_affine(),
Mode::CLASSICAL.with_mix(),
Mode::CLASSICAL.with_affine().with_mix(),
Mode::INTUITIONISTIC,
Mode::INTUITIONISTIC.with_affine(),
Mode::CYCLIC,
Mode::LAMBEK,
Mode::LAMBEK.with_empty_antecedents(),
];
assert_eq!(modes.map(Mode::name), Mode::NAMES);
for mode in modes {
assert_eq!(mode.name().parse::<Mode>().unwrap(), mode);
assert!(mode.check().is_ok(), "{mode}");
}
assert!(Mode::INTUITIONISTIC.with_mix().check().is_err());
for refused in [Mode::CYCLIC.with_affine(), Mode::CYCLIC.with_mix()] {
assert!(matches!(refused.check(), Err(Error::OrderedMode { mode }) if mode == refused));
}
assert!(matches!(
"planar".parse::<Mode>(),
Err(Error::UnknownName {
what: "mode",
known: Mode::NAMES,
..
})
));
for (&fragment, name) in Fragment::NAMED.iter().zip(Fragment::NAMES) {
assert_eq!(fragment.name(), *name);
assert_eq!(name.parse::<Fragment>().unwrap(), fragment);
assert_eq!(format!("I{name}").parse::<Fragment>().unwrap(), fragment);
}
assert!("MLLL".parse::<Fragment>().is_err());
}
#[cfg(feature = "parse")]
#[test]
fn detection() {
use Fragment as F;
for (input, fragment) in [
("|-", F::EMPTY),
("A |- A", F::EMPTY),
("A, A -o B |- B", F::MLL),
("A * B |- A par B", F::MLL),
("|- 1", F::MULTIPLICATIVE_UNITS),
("1 |-", F::MULTIPLICATIVE_UNITS),
("A * 1 |- A", F::MLL_WITH_UNITS),
("A & B |- A", F::ADDITIVES),
("|- A & B", F::ADDITIVES),
("|- top", F::ADDITIVE_UNITS),
("0 |- A", F::ADDITIVE_UNITS),
("A & B |- A + 0", F::ADDITIVE),
("A & B |- A * B", F::MLL | F::ADDITIVES),
("A * B, C par D |- A & B, C + D, 0, top, 1, bot", F::MALL),
("!A |- A", F::EXPONENTIALS),
("|- !A", F::EXPONENTIALS),
("!A, !(A -o B) |- !B", F::MLL | F::EXPONENTIALS),
("!A, !(A -o B) |- !B, 1", F::MELL),
("!(A & B) |- ?(A + B)", F::ADDITIVES | F::EXPONENTIALS),
("!(A & B) * 1 |- ?(A + B), top", F::LL),
] {
let s: Sequent = input.parse().unwrap();
assert_eq!(s.fragment(), fragment, "{input:?}");
}
}
#[test]
fn detection_ignores_unreachable_terms() {
use crate::linear::sequents::{Term, TermId};
let s = Sequent {
terms: vec![Term::One, Term::Bang(TermId::new(0)), Term::Top],
roots: vec![TermId::new(1)],
atoms: vec![],
antecedents: None,
cuts: vec![],
fo: Default::default(),
};
assert_eq!(
s.fragment(),
Fragment::MULTIPLICATIVE_UNITS | Fragment::EXPONENTIALS
);
}
#[test]
fn mode_names() {
assert_eq!(Mode::default(), Mode::CLASSICAL);
assert_eq!(Mode::CLASSICAL.to_string(), "classical");
assert_eq!(
Mode::INTUITIONISTIC.with_affine().to_string(),
"intuitionistic affine"
);
assert_eq!(
Mode::CLASSICAL.with_affine().with_mix().to_string(),
"classical affine with Mix"
);
assert_eq!(
Mode::INTUITIONISTIC.with_mix().to_string(),
"intuitionistic with Mix"
);
assert_eq!(Mode::CYCLIC.to_string(), "cyclic");
assert_eq!(Mode::LAMBEK.to_string(), "Lambek");
assert_eq!(
Mode::LAMBEK.with_empty_antecedents().to_string(),
"Lambek with empty antecedents"
);
}
#[test]
fn empty_antecedents() {
assert!(!Mode::LAMBEK.allows_empty_antecedents());
let star = Mode::LAMBEK.with_empty_antecedents();
assert!(star.allows_empty_antecedents() && star != Mode::LAMBEK);
for mode in [Mode::CLASSICAL, Mode::INTUITIONISTIC, Mode::CYCLIC] {
assert!(mode.allows_empty_antecedents());
assert_eq!(mode.with_empty_antecedents(), mode);
}
assert_eq!(Mode::LAMBEK.check(), Ok(()));
assert!(matches!(
Mode::LAMBEK.with_affine().check(),
Err(Error::OrderedMode { .. })
));
}
}