use super::{compositions::Compositions, integer_queries, syntax};
use crate::{Context, Error, ModelPosition, Outcome, Plugin, re};
use num_bigint::BigInt;
use num_rational::BigRational;
use num_traits::{One, ToPrimitive, Zero};
mod declared_formula;
mod wording;
const MATRIX_LIMIT: usize = 8;
const ENTRY_BITS: u64 = 4_096;
const RATIONAL_BITS: u64 = 65_536;
type Matrix = Vec<Vec<BigRational>>;
#[derive(Default)]
pub struct AlgebraQueries {
engine: Compositions,
}
impl Plugin for AlgebraQueries {
fn rewrite_call(
&self,
name: &str,
arguments: &str,
context: &Context,
position: ModelPosition,
) -> Outcome {
if !matches!(
name.to_ascii_lowercase().as_str(),
"determinant" | "matrix_rank" | "solve_linear_component"
) {
return None;
}
Some(
self.compute(name, arguments, context)
.and_then(|value| literal(&value, position == ModelPosition::Standalone)),
)
}
fn rewrite_model(&self, input: &str, context: &Context, position: ModelPosition) -> Outcome {
if let Some(result) = wording::rewrite(self, input, context, position) {
return Some(result);
}
self.wording(input, context).map(|result| {
result.and_then(|value| literal(&value, position == ModelPosition::Standalone))
})
}
fn rewrite(&self, input: &str, context: &Context) -> Outcome {
if let Some(result) = wording::rewrite(
self,
syntax::ungroup(input),
context,
ModelPosition::Standalone,
) {
return Some(result);
}
if let Some(result) = self.wording(syntax::ungroup(input), context) {
return Some(result.and_then(|value| literal(&value, true)));
}
let expression = match syntax::rewrite_groups(input, |part| {
if let Some(result) = wording::rewrite(self, part, context, ModelPosition::Operand) {
return Some(result);
}
self.wording(part, context)
.map(|result| result.and_then(|value| literal(&value, false)))
}) {
Some(Ok(expression)) => expression,
Some(Err(error)) => return Some(Err(error)),
None => input.into(),
};
let calls = re!(r"(?i)\b(?:determinant|matrix_rank|solve_linear_component)\(");
if let Some((name, arguments)) = whole_call(&expression) {
return Some(
self.compute(name, arguments, context)
.and_then(|value| literal(&value, true)),
);
}
match syntax::rewrite_calls(&expression, calls, |name, arguments| {
self.compute(name, arguments, context)
.and_then(|value| literal(&value, false))
}) {
Ok(lowered) if lowered != input => Some(Ok(lowered)),
Err(error) => Some(Err(error)),
_ => None,
}
}
fn evaluate(&self, input: &str, context: &Context) -> Outcome {
wording::evaluate(self, syntax::ungroup(input), context)
}
}
impl AlgebraQueries {
fn compute(
&self,
name: &str,
arguments: &str,
context: &Context,
) -> Result<BigRational, Error> {
let args = structural_arguments(arguments)?;
let name = name.to_ascii_lowercase();
if args.len()
!= if name == "solve_linear_component" {
3
} else {
1
}
{
return Err(error("invalid_matrix"));
}
let matrix = self.matrix(args[0], context)?;
match name.as_str() {
"determinant" => {
if matrix.len() != matrix[0].len() {
return Err(error("invalid_matrix"));
}
let columns = matrix.len();
let reduced = eliminate(matrix, columns)?;
Ok(if reduced.pivots.len() == columns {
reduced.determinant
} else {
BigRational::zero()
})
}
"matrix_rank" => {
let columns = matrix[0].len();
Ok(BigRational::from_integer(BigInt::from(
eliminate(matrix, columns)?.pivots.len(),
)))
}
"solve_linear_component" => {
let rhs = self.vector(args[1], context)?;
let index = self.scalar(args[2], context)?;
let index = index
.is_integer()
.then(|| index.to_integer().to_usize())
.flatten()
.filter(|index| (1..=matrix[0].len()).contains(index))
.ok_or_else(|| error("invalid_matrix_index"))?;
Ok(solution(matrix, rhs)?[index - 1].clone())
}
_ => Err(error("invalid_matrix")),
}
}
fn wording(&self, input: &str, context: &Context) -> Option<Result<BigRational, Error>> {
let input = input.trim().trim_end_matches(['.', '?']);
if let Some(c) = re!(
r"(?i)^(?:find|calculate|compute|what is) (?:the )?(determinant|rank) (?:of|for) (.+)$"
)
.captures(input)
{
return Some(self.compute(
if c[1].eq_ignore_ascii_case("rank") {
"matrix_rank"
} else {
"determinant"
},
&c[2],
context,
));
}
if let Some(c) = re!(r"(?i)^for ([a-z])\s*=\s*(.+) and ([a-z])\s*=\s*(.+?), (?:solve|calculate) ([a-z])([a-z])\s*=\s*([a-z]) and (?:calculate|find|give) the sum of (?:the )?solution's components$").captures(input) {
return Some((|| {
if c[1] != c[5] || c[3] != c[7] || c[1] == c[3] || c[6] == c[1] || c[6] == c[3] {
return Err(error("invalid_matrix"));
}
let matrix = self.matrix(&c[2], context)?;
let rhs = self.vector(c[4].trim().trim_end_matches(['áµ€']), context)?;
solution(matrix, rhs)?.into_iter().try_fold(BigRational::zero(), |sum, value| bounded(sum + value))
})());
}
None
}
fn scalar(&self, input: &str, context: &Context) -> Result<BigRational, Error> {
let lowered = syntax::rewrite_calls(
input,
re!(r"(?i)\b(?:determinant|matrix_rank|solve_linear_component)\("),
|name, arguments| {
self.compute(name, arguments, context)
.and_then(|value| literal(&value, false))
},
)?;
let (numerator, denominator) =
integer_queries::ratio_value(&lowered).map_err(|exact_error| {
if exact_error.0 == "invalid_integer_expression"
&& let Err(typed_error) = self.engine.quantity_value(input, "1", context)
&& typed_error.0 == "incompatible_units"
{
return typed_error;
}
exact_error
})?;
if numerator.bits().max(denominator.bits()) > ENTRY_BITS {
return Err(error("integer_limit"));
}
bounded(BigRational::new(numerator, denominator))
}
fn vector(&self, input: &str, context: &Context) -> Result<Vec<BigRational>, Error> {
let entries = list(input)?;
entries
.into_iter()
.map(|entry| self.scalar(entry, context))
.collect()
}
fn matrix(&self, input: &str, context: &Context) -> Result<Matrix, Error> {
let rows = list(input)?;
let matrix = rows
.into_iter()
.map(|row| self.vector(row, context))
.collect::<Result<Matrix, _>>()?;
if matrix.iter().any(|row| row.len() != matrix[0].len()) {
return Err(error("invalid_matrix"));
}
Ok(matrix)
}
}
fn error(code: &str) -> Error {
Error(code.into())
}
fn bounded(value: BigRational) -> Result<BigRational, Error> {
if value.numer().bits().max(value.denom().bits()) > RATIONAL_BITS {
Err(error("integer_limit"))
} else {
Ok(value)
}
}
fn literal(value: &BigRational, standalone: bool) -> Result<String, Error> {
let literal = if standalone && value.is_integer() {
format!("{} in decimal", value.numer())
} else {
format!("rational({},{})", value.numer(), value.denom())
};
if literal.len() > 4_096 {
Err(error("integer_limit"))
} else {
Ok(literal)
}
}
fn whole_call(input: &str) -> Option<(&str, &str)> {
let input = syntax::ungroup(input.trim());
let (name, _) = input.split_once('(')?;
if !matches!(
name.to_ascii_lowercase().as_str(),
"determinant" | "matrix_rank" | "solve_linear_component"
) {
return None;
}
let groups = syntax::groups(input)?;
let group = groups.first()?;
(groups.len() == 1 && group.start == name.len() + 1 && group.end + 1 == input.len())
.then(|| (name, &input[group.clone()]))
}
fn list(input: &str) -> Result<Vec<&str>, Error> {
let inner = input
.trim()
.strip_prefix('[')
.and_then(|s| s.strip_suffix(']'))
.ok_or_else(|| error("invalid_matrix"))?;
let values = structural_arguments(inner)?;
if values.len() > MATRIX_LIMIT {
return Err(error("integer_limit"));
}
Ok(values)
}
fn structural_arguments(input: &str) -> Result<Vec<&str>, Error> {
let (mut groups, mut values, mut start) = (Vec::new(), Vec::new(), 0);
for (at, ch) in input.char_indices() {
match ch {
'[' | '(' => {
groups.push(ch);
if groups.len() > 64 {
return Err(error("expression_too_deep"));
}
}
']' | ')' => {
let opening = if ch == ']' { '[' } else { '(' };
if groups.pop() != Some(opening) {
return Err(error("invalid_matrix"));
}
}
',' if groups.is_empty() => {
values.push(input[start..at].trim());
start = at + 1;
}
_ => {}
}
}
values.push(input[start..].trim());
if !groups.is_empty() || values.iter().any(|value| value.is_empty()) {
return Err(error("invalid_matrix"));
}
Ok(values)
}
struct Reduced {
matrix: Matrix,
pivots: Vec<usize>,
determinant: BigRational,
}
fn eliminate(mut matrix: Matrix, columns: usize) -> Result<Reduced, Error> {
let (mut row, mut pivots, mut determinant) = (0, Vec::new(), BigRational::one());
for column in 0..columns {
let Some(pivot) = (row..matrix.len()).find(|r| !matrix[*r][column].is_zero()) else {
continue;
};
if pivot != row {
matrix.swap(pivot, row);
determinant = -determinant;
}
let divisor = matrix[row][column].clone();
determinant = bounded(determinant * &divisor)?;
for entry in &mut matrix[row][column..] {
*entry = bounded(&*entry / &divisor)?;
}
let normalized = matrix[row].clone();
for (r, entries) in matrix.iter_mut().enumerate() {
if r == row || entries[column].is_zero() {
continue;
}
let factor = entries[column].clone();
for (entry, pivot_entry) in entries[column..].iter_mut().zip(&normalized[column..]) {
let product = bounded(&factor * pivot_entry)?;
*entry = bounded(&*entry - product)?;
}
}
pivots.push(column);
row += 1;
if row == matrix.len() {
break;
}
}
Ok(Reduced {
matrix,
pivots,
determinant,
})
}
fn solution(mut matrix: Matrix, rhs: Vec<BigRational>) -> Result<Vec<BigRational>, Error> {
if matrix.len() != rhs.len() {
return Err(error("invalid_matrix"));
}
let columns = matrix[0].len();
for (row, value) in matrix.iter_mut().zip(rhs) {
row.push(value)
}
let reduced = eliminate(matrix, columns)?;
if reduced
.matrix
.iter()
.any(|row| row[..columns].iter().all(Zero::is_zero) && !row[columns].is_zero())
{
return Err(error("inconsistent_system"));
}
if reduced.pivots.len() != columns {
return Err(error("no_unique_solution"));
}
let mut values = vec![BigRational::zero(); columns];
for (row, column) in reduced.pivots.into_iter().enumerate() {
values[column] = reduced.matrix[row][columns].clone();
}
Ok(values)
}