diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/def_rules.rs | 24 | ||||
| -rw-r--r-- | src/lib.rs | 3 | ||||
| -rw-r--r-- | src/main.rs | 29 | ||||
| -rw-r--r-- | src/match_rules.rs | 103 | ||||
| -rw-r--r-- | src/sexpr.rs | 242 |
5 files changed, 401 insertions, 0 deletions
diff --git a/src/def_rules.rs b/src/def_rules.rs new file mode 100644 index 0000000..a2ba36e --- /dev/null +++ b/src/def_rules.rs @@ -0,0 +1,24 @@ +use crate::sexpr::{self, Atom, Expr}; + +#[derive(Debug, Clone)] +pub struct Rule { + pub lhs: Expr, + pub rhs: Expr +} + +impl TryFrom<Expr> for Rule { + type Error = (); + fn try_from(value: Expr) -> Result<Self, Self::Error> { + if let Expr::Application(v) = value && v[0] == Expr::Atom(Atom::Builtin(String::from("def-rule"))) && v.len() == 3 { + Ok(Rule { + lhs: v[1].clone(), + rhs: v[2].clone() + }) + } else {Err(())} + } +} + +pub fn parse_def_rules(input: String) -> Vec<Rule> { + let exprs = sexpr::Parser::new(&input).parse_all(); + exprs.iter().filter_map(|e| e.clone().try_into().ok()).collect() +} diff --git a/src/lib.rs b/src/lib.rs new file mode 100644 index 0000000..1bb3e41 --- /dev/null +++ b/src/lib.rs @@ -0,0 +1,3 @@ +pub mod sexpr; +pub mod def_rules; +pub mod match_rules; diff --git a/src/main.rs b/src/main.rs new file mode 100644 index 0000000..911948d --- /dev/null +++ b/src/main.rs @@ -0,0 +1,29 @@ +use difx::sexpr::Parser; +use difx::match_rules::{self, Bindings}; + +fn main() { + let input = include_str!("../test_rule"); + let rules = difx::def_rules::parse_def_rules(input.to_string()); + // println!("{:#?}", rules); + + let pat = rules[0].clone().lhs; + println!("{:?}", pat); + + loop { + let mut input = String::new(); + std::io::stdin() + .read_line(&mut input) + .unwrap(); + + let mut parser = Parser::new(&input); + let parsed = parser.parse_one(); + + let mut bindings = Bindings::default(); + + if match_rules::matches(&pat, &parsed, &mut bindings) { + println!("{:?}", &bindings); + println!("MATCH"); + } + } +} + diff --git a/src/match_rules.rs b/src/match_rules.rs new file mode 100644 index 0000000..938ee08 --- /dev/null +++ b/src/match_rules.rs @@ -0,0 +1,103 @@ +use std::collections::HashMap; + +use crate::sexpr::{Atom, Expr, Variable, VariableType}; + +#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)] +pub enum BindValue { + Integer(i64), + Expr(Expr), + Ellipsis(Vec<Expr>) +} + +#[derive(Default)] +pub struct Bindings<'b>(HashMap<&'b str, BindValue>); + +impl<'b> Bindings<'b> { + pub fn check_or_insert(&mut self, index: &'b String, bind_value: BindValue) -> bool { + if let Some(existing) = self.0.get(index.as_str()) { + existing == &bind_value + } else { + self.0.insert(index, bind_value); + true + } + } +} + +impl std::fmt::Debug for Bindings<'_> { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f, "{:?}", self.0) + } +} + +pub fn args_match<'b>(p_args: &'b [Expr], args: &'b [Expr], bindings: &mut Bindings<'b>) -> bool { + const ELLIPSIS: Expr = Expr::Atom(Atom::Ellipsis); + + if p_args.contains(&ELLIPSIS) { + let mut sorted_p: Vec<&Expr> = p_args.iter() + .filter(|p| **p != ELLIPSIS) + .collect(); + + let mut sorted_a: Vec<&Expr> = args.iter().collect(); + + if sorted_p.len() != sorted_a.len() { + return false; + } + + sorted_p.sort(); + sorted_a.sort(); + + std::iter::zip(sorted_p, sorted_a).all(|(p, a)| { + matches(p, a, bindings) + }) + } else { + if p_args.len() != args.len() { + return false; + } + std::iter::zip(p_args.iter(), args.iter()).all(|(a, b)| { + matches(a, b, bindings) + }) + } +} + +pub fn matches<'b>(p: &'b Expr, expr: &'b Expr, bindings: &mut Bindings<'b>) -> bool { + match expr { + Expr::Atom(Atom::Int(i)) => { + match p { + Expr::Atom(Atom::Int(pi)) => i == pi, + Expr::Atom(Atom::Variable(Variable { r#type: e @ (VariableType::Integer | VariableType::Expr), index })) => { + bindings.check_or_insert(index, match e { + VariableType::Integer => BindValue::Integer(*i), + VariableType::Expr => BindValue::Expr(Expr::Atom(Atom::Int(*i))) + }) + } + _ => false + } + } + Expr::Atom(Atom::Builtin(s)) => { + match p { + Expr::Atom(Atom::Builtin(ps)) => s == ps, + Expr::Atom(Atom::Variable(Variable { r#type: VariableType::Expr, index })) => { + bindings.check_or_insert(index, BindValue::Expr(Expr::Atom(Atom::Builtin(s.to_string())))) + } + _ => false + } + } + Expr::Application(exprs) => { + if let Expr::Atom(Atom::Builtin(f)) = &exprs[0] && + let Expr::Application(p_exprs) = p && + let Expr::Atom(Atom::Builtin(pf)) = &p_exprs[0] { + f == pf && args_match(&p_exprs[1..], &exprs[1..], bindings) + } else if exprs.len() == 1 { + matches(p, &exprs[0], bindings) + } else if let Expr::Atom(Atom::Variable(Variable { r#type: VariableType::Expr, index })) = p { + bindings.check_or_insert(index, BindValue::Expr(expr.clone())) + } else { + false + } + }, + Expr::Atom(Atom::Variable(_)) | Expr::Atom(Atom::Ellipsis) => { + // These should only appear in patterns, not in expressions being matched + false + } + } +} diff --git a/src/sexpr.rs b/src/sexpr.rs new file mode 100644 index 0000000..557bc5d --- /dev/null +++ b/src/sexpr.rs @@ -0,0 +1,242 @@ +use std::cmp::Ordering; +use std::iter::Peekable; +use std::str::{Chars, FromStr}; + +#[derive(Debug, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)] +pub struct Variable { + pub r#type: VariableType, + pub index: String +} + +impl FromStr for Variable { + type Err = (); + fn from_str(s: &str) -> Result<Self, Self::Err> { + match s.chars().nth(0) { + Some('$') => Ok(Variable { + r#type: VariableType::Integer, + index: s[1..].to_string() + }), + Some('@') => Ok(Variable { + r#type: VariableType::Expr, + index: s[1..].to_string() + }), + _ => Err(()), + } + } +} + +#[derive(Debug, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)] +pub enum VariableType { + Integer, + Expr +} + +#[derive(Debug, PartialEq, Clone, Eq, Hash)] +pub enum Atom { + Int(i64), + Builtin(String), + Variable(Variable), + Ellipsis, +} + +impl PartialOrd for Atom { + fn partial_cmp(&self, other: &Self) -> Option<Ordering> { + Some(self.cmp(other)) + } +} + +impl Ord for Atom { + fn cmp(&self, other: &Self) -> Ordering { + match (self, other) { + (Atom::Int(i1), Atom::Int(i2)) => i1.cmp(i2), + (Atom::Int(_), _) => Ordering::Less, + (_, Atom::Int(_)) => Ordering::Greater, + + (Atom::Builtin(b1), Atom::Builtin(b2)) => b1.cmp(b2), + (Atom::Builtin(_), Atom::Variable(_)) => Ordering::Less, + (Atom::Builtin(_), Atom::Ellipsis) => Ordering::Less, + + (Atom::Variable(v1), Atom::Variable(v2)) => { + v1.index.cmp(&v2.index) + } + (Atom::Variable(_), Atom::Builtin(_)) => Ordering::Greater, + (Atom::Variable(_), Atom::Ellipsis) => Ordering::Less, + + (Atom::Ellipsis, Atom::Ellipsis) => Ordering::Equal, + (Atom::Ellipsis, _) => Ordering::Greater, + } + } +} + +impl std::fmt::Display for Atom { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + match self { + Atom::Int(i) => write!(f, "{}", i), + Atom::Builtin(b) => write!(f, "{}", b), + Atom::Variable(v) => write!(f, "{}{}", + match v.r#type { + VariableType::Integer => "$", + VariableType::Expr => "@", + }, + v.index + ), + Atom::Ellipsis => write!(f, "."), + } + } +} + +#[derive(Debug, PartialEq, Clone, Eq, Hash)] +pub enum Expr { + Atom(Atom), + Application(Vec<Expr>), +} + +impl PartialOrd for Expr { + fn partial_cmp(&self, other: &Self) -> Option<Ordering> { + Some(self.cmp(other)) + } +} + +impl Ord for Expr { + fn cmp(&self, other: &Self) -> Ordering { + match (self, other) { + (Expr::Atom(_), Expr::Application(_)) => Ordering::Less, + (Expr::Application(_), Expr::Atom(_)) => Ordering::Greater, + (Expr::Atom(a1), Expr::Atom(a2)) => a1.cmp(a2), + (Expr::Application(v1), Expr::Application(v2)) => { + v1.len().cmp(&v2.len()) + .then_with(|| v1.cmp(v2)) + } + } + } +} + +impl std::fmt::Display for Expr { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + match self { + Expr::Atom(a) => write!(f, "{}", a), + Expr::Application(args) => { + let pieces: Vec<String> = args.into_iter().map(ToString::to_string).collect(); + write!(f, "({})", pieces.join(" ")) + } + } + } +} + +#[derive(Debug, PartialEq, Eq)] +enum ParseResult { + Expr(Expr), + Eof, +} + +pub struct Parser<'a> { + input: Peekable<Chars<'a>>, +} + +impl<'a> Parser<'a> { + pub fn new(input: &'a str) -> Self { + Parser { + input: input.chars().peekable(), + } + } + + pub fn parse_all(&mut self) -> Vec<Expr> { + let mut expressions = Vec::new(); + loop { + match self.parse_one_optional() { + ParseResult::Expr(expr) => expressions.push(expr), + ParseResult::Eof => break, + } + } + expressions + } + + fn parse_one_optional(&mut self) -> ParseResult { + self.skip_whitespace(); + + match self.input.peek() { + Some('(') => ParseResult::Expr(self.parse_list()), + Some(_) => ParseResult::Expr(self.parse_atom()), + None => ParseResult::Eof, + } + } + + pub fn parse_one(&mut self) -> Expr { + match self.parse_one_optional() { + ParseResult::Expr(expr) => expr, + ParseResult::Eof => panic!("Unexpected end of input during parse!"), + } + } + + fn skip_whitespace(&mut self) { + while let Some(&c) = self.input.peek() { + if c.is_whitespace() { + self.input.next(); + } else { + break; + } + } + } + + fn parse_list(&mut self) -> Expr { + if self.input.next() != Some('(') { + panic!("Parser error: Expected '('"); + } + + let mut expressions = Vec::new(); + + loop { + self.skip_whitespace(); + + match self.input.peek() { + Some(')') => { + self.input.next(); + break; + } + None => panic!("Parser error: Unexpected EOF, unclosed list"), + Some(_) => { + match self.parse_one_optional() { + ParseResult::Expr(expr) => expressions.push(expr), + ParseResult::Eof => panic!("Parser error: Unexpected EOF after space inside list"), + } + } + } + } + + Expr::Application(expressions) + } + + fn parse_atom(&mut self) -> Expr { + let mut buffer = String::new(); + + while let Some(&c) = self.input.peek() { + if c.is_whitespace() || c == '(' || c == ')' { + break; + } + buffer.push(c); + self.input.next(); + } + + if buffer.is_empty() { + panic!("Parser error: Tried to parse an atom, but it was empty."); + } + + // Check for ellipsis + if buffer == "." { + return Expr::Atom(Atom::Ellipsis); + } + + // Check for variable + if let Ok(v) = buffer.parse::<Variable>() { + return Expr::Atom(Atom::Variable(v)); + } + + // Check for integer + if let Ok(i) = buffer.parse::<i64>() { + return Expr::Atom(Atom::Int(i)); + } + + // Default to builtin + Expr::Atom(Atom::Builtin(buffer)) + } +} |