diff options
Diffstat (limited to 'users/grfn/achilles/src/passes/hir')
| -rw-r--r-- | users/grfn/achilles/src/passes/hir/mod.rs | 211 | ||||
| -rw-r--r-- | users/grfn/achilles/src/passes/hir/monomorphize.rs | 139 | ||||
| -rw-r--r-- | users/grfn/achilles/src/passes/hir/strip_positive_units.rs | 191 |
3 files changed, 0 insertions, 541 deletions
diff --git a/users/grfn/achilles/src/passes/hir/mod.rs b/users/grfn/achilles/src/passes/hir/mod.rs deleted file mode 100644 index 872c449eb020..000000000000 --- a/users/grfn/achilles/src/passes/hir/mod.rs +++ /dev/null @@ -1,211 +0,0 @@ -use std::collections::HashMap; - -use crate::ast::hir::{Binding, Decl, Expr, Pattern}; -use crate::ast::{BinaryOperator, Ident, Literal, UnaryOperator}; - -pub(crate) mod monomorphize; -pub(crate) mod strip_positive_units; - -pub(crate) trait Visitor<'a, 'ast, T: 'ast>: Sized + 'a { - type Error; - - fn visit_type(&mut self, _type: &mut T) -> Result<(), Self::Error> { - Ok(()) - } - - fn visit_ident(&mut self, _ident: &mut Ident<'ast>) -> Result<(), Self::Error> { - Ok(()) - } - - fn visit_literal(&mut self, _literal: &mut Literal<'ast>) -> Result<(), Self::Error> { - Ok(()) - } - - fn visit_unary_operator(&mut self, _op: &mut UnaryOperator) -> Result<(), Self::Error> { - Ok(()) - } - - fn visit_binary_operator(&mut self, _op: &mut BinaryOperator) -> Result<(), Self::Error> { - Ok(()) - } - - fn visit_pattern(&mut self, _pat: &mut Pattern<'ast, T>) -> Result<(), Self::Error> { - Ok(()) - } - - fn visit_binding(&mut self, binding: &mut Binding<'ast, T>) -> Result<(), Self::Error> { - self.visit_pattern(&mut binding.pat)?; - self.visit_expr(&mut binding.body)?; - Ok(()) - } - - fn post_visit_call( - &mut self, - _fun: &mut Expr<'ast, T>, - _type_args: &mut HashMap<Ident<'ast>, T>, - _args: &mut Vec<Expr<'ast, T>>, - ) -> Result<(), Self::Error> { - Ok(()) - } - - fn pre_visit_call( - &mut self, - _fun: &mut Expr<'ast, T>, - _type_args: &mut HashMap<Ident<'ast>, T>, - _args: &mut Vec<Expr<'ast, T>>, - ) -> Result<(), Self::Error> { - Ok(()) - } - - fn visit_tuple(&mut self, members: &mut Vec<Expr<'ast, T>>) -> Result<(), Self::Error> { - for expr in members { - self.visit_expr(expr)?; - } - Ok(()) - } - - fn pre_visit_expr(&mut self, _expr: &mut Expr<'ast, T>) -> Result<(), Self::Error> { - Ok(()) - } - - fn visit_expr(&mut self, expr: &mut Expr<'ast, T>) -> Result<(), Self::Error> { - self.pre_visit_expr(expr)?; - match expr { - Expr::Ident(id, t) => { - self.visit_ident(id)?; - self.visit_type(t)?; - } - Expr::Literal(lit, t) => { - self.visit_literal(lit)?; - self.visit_type(t)?; - } - Expr::UnaryOp { op, rhs, type_ } => { - self.visit_unary_operator(op)?; - self.visit_expr(rhs)?; - self.visit_type(type_)?; - } - Expr::BinaryOp { - lhs, - op, - rhs, - type_, - } => { - self.visit_expr(lhs)?; - self.visit_binary_operator(op)?; - self.visit_expr(rhs)?; - self.visit_type(type_)?; - } - Expr::Let { - bindings, - body, - type_, - } => { - for binding in bindings.iter_mut() { - self.visit_binding(binding)?; - } - self.visit_expr(body)?; - self.visit_type(type_)?; - } - Expr::If { - condition, - then, - else_, - type_, - } => { - self.visit_expr(condition)?; - self.visit_expr(then)?; - self.visit_expr(else_)?; - self.visit_type(type_)?; - } - Expr::Fun { - args, - body, - type_args, - type_, - } => { - for (ident, t) in args { - self.visit_ident(ident)?; - self.visit_type(t)?; - } - for ta in type_args { - self.visit_ident(ta)?; - } - self.visit_expr(body)?; - self.visit_type(type_)?; - } - Expr::Call { - fun, - args, - type_args, - type_, - } => { - self.pre_visit_call(fun, type_args, args)?; - self.visit_expr(fun)?; - for arg in args.iter_mut() { - self.visit_expr(arg)?; - } - self.visit_type(type_)?; - self.post_visit_call(fun, type_args, args)?; - } - Expr::Tuple(tup, type_) => { - self.visit_tuple(tup)?; - self.visit_type(type_)?; - } - } - - Ok(()) - } - - fn post_visit_decl(&mut self, _decl: &'a Decl<'ast, T>) -> Result<(), Self::Error> { - Ok(()) - } - - fn post_visit_fun_decl( - &mut self, - _name: &mut Ident<'ast>, - _type_args: &mut Vec<Ident>, - _args: &mut Vec<(Ident, T)>, - _body: &mut Box<Expr<T>>, - _type_: &mut T, - ) -> Result<(), Self::Error> { - Ok(()) - } - - fn visit_decl(&mut self, decl: &'a mut Decl<'ast, T>) -> Result<(), Self::Error> { - match decl { - Decl::Fun { - name, - type_args, - args, - body, - type_, - } => { - self.visit_ident(name)?; - for type_arg in type_args.iter_mut() { - self.visit_ident(type_arg)?; - } - for (arg, t) in args.iter_mut() { - self.visit_ident(arg)?; - self.visit_type(t)?; - } - self.visit_expr(body)?; - self.visit_type(type_)?; - self.post_visit_fun_decl(name, type_args, args, body, type_)?; - } - Decl::Extern { - name, - arg_types, - ret_type, - } => { - self.visit_ident(name)?; - for arg_t in arg_types { - self.visit_type(arg_t)?; - } - self.visit_type(ret_type)?; - } - } - - self.post_visit_decl(decl)?; - Ok(()) - } -} diff --git a/users/grfn/achilles/src/passes/hir/monomorphize.rs b/users/grfn/achilles/src/passes/hir/monomorphize.rs deleted file mode 100644 index 251a988f4f6f..000000000000 --- a/users/grfn/achilles/src/passes/hir/monomorphize.rs +++ /dev/null @@ -1,139 +0,0 @@ -use std::cell::RefCell; -use std::collections::{HashMap, HashSet}; -use std::convert::TryInto; -use std::mem; - -use void::{ResultVoidExt, Void}; - -use crate::ast::hir::{Decl, Expr}; -use crate::ast::{self, Ident}; - -use super::Visitor; - -#[derive(Default)] -pub(crate) struct Monomorphize<'a, 'ast> { - decls: HashMap<&'a Ident<'ast>, &'a Decl<'ast, ast::Type<'ast>>>, - extra_decls: Vec<Decl<'ast, ast::Type<'ast>>>, - remove_decls: HashSet<Ident<'ast>>, -} - -impl<'a, 'ast> Monomorphize<'a, 'ast> { - pub(crate) fn new() -> Self { - Default::default() - } -} - -impl<'a, 'ast> Visitor<'a, 'ast, ast::Type<'ast>> for Monomorphize<'a, 'ast> { - type Error = Void; - - fn post_visit_call( - &mut self, - fun: &mut Expr<'ast, ast::Type<'ast>>, - type_args: &mut HashMap<Ident<'ast>, ast::Type<'ast>>, - args: &mut Vec<Expr<'ast, ast::Type<'ast>>>, - ) -> Result<(), Self::Error> { - let new_fun = match fun { - Expr::Ident(id, _) => { - let decl: Decl<_> = (**self.decls.get(id).unwrap()).clone(); - let name = RefCell::new(id.to_string()); - let type_args = mem::take(type_args); - let mut monomorphized = decl - .traverse_type(|ty| -> Result<_, Void> { - Ok(ty.clone().traverse_type_vars(|v| { - let concrete = type_args.get(&v).unwrap(); - name.borrow_mut().push_str(&concrete.to_string()); - concrete.clone() - })) - }) - .void_unwrap(); - let name: Ident = name.into_inner().try_into().unwrap(); - if name != *id { - self.remove_decls.insert(id.clone()); - monomorphized.set_name(name.clone()); - let type_ = monomorphized.type_().unwrap().clone(); - self.extra_decls.push(monomorphized); - Some(Expr::Ident(name, type_)) - } else { - None - } - } - _ => todo!(), - }; - if let Some(new_fun) = new_fun { - *fun = new_fun; - } - Ok(()) - } - - fn post_visit_decl( - &mut self, - decl: &'a Decl<'ast, ast::Type<'ast>>, - ) -> Result<(), Self::Error> { - self.decls.insert(decl.name(), decl); - Ok(()) - } -} - -pub(crate) fn run_toplevel<'a>(toplevel: &mut Vec<Decl<'a, ast::Type<'a>>>) { - let mut pass = Monomorphize::new(); - for decl in toplevel.iter_mut() { - pass.visit_decl(decl).void_unwrap(); - } - let remove_decls = mem::take(&mut pass.remove_decls); - let mut extra_decls = mem::take(&mut pass.extra_decls); - toplevel.retain(|decl| !remove_decls.contains(decl.name())); - extra_decls.append(toplevel); - *toplevel = extra_decls; -} - -#[cfg(test)] -mod tests { - use std::convert::TryFrom; - - use super::*; - use crate::parser::toplevel; - use crate::tc::typecheck_toplevel; - - #[test] - fn call_id_decl() { - let (_, program) = toplevel( - "ty id : fn a -> a - fn id x = x - - ty main : fn -> int - fn main = id 0", - ) - .unwrap(); - let mut program = typecheck_toplevel(program).unwrap(); - run_toplevel(&mut program); - - let find_decl = |ident: &str| { - program.iter().find(|decl| { - matches!(decl, Decl::Fun {name, ..} if name == &Ident::try_from(ident).unwrap()) - }).unwrap() - }; - - let main = find_decl("main"); - let body = match main { - Decl::Fun { body, .. } => body, - _ => unreachable!(), - }; - - let expected_type = ast::Type::Function(ast::FunctionType { - args: vec![ast::Type::Int], - ret: Box::new(ast::Type::Int), - }); - - match &**body { - Expr::Call { fun, .. } => { - let fun = match &**fun { - Expr::Ident(fun, _) => fun, - _ => unreachable!(), - }; - let called_decl = find_decl(fun.into()); - assert_eq!(called_decl.type_().unwrap(), &expected_type); - } - _ => unreachable!(), - } - } -} diff --git a/users/grfn/achilles/src/passes/hir/strip_positive_units.rs b/users/grfn/achilles/src/passes/hir/strip_positive_units.rs deleted file mode 100644 index 85ee1cce4859..000000000000 --- a/users/grfn/achilles/src/passes/hir/strip_positive_units.rs +++ /dev/null @@ -1,191 +0,0 @@ -use std::collections::HashMap; -use std::mem; - -use ast::hir::{Binding, Pattern}; -use ast::Literal; -use void::{ResultVoidExt, Void}; - -use crate::ast::hir::{Decl, Expr}; -use crate::ast::{self, Ident}; - -use super::Visitor; - -/// Strip all values with a unit type in positive (non-return) position -pub(crate) struct StripPositiveUnits {} - -impl<'a, 'ast> Visitor<'a, 'ast, ast::Type<'ast>> for StripPositiveUnits { - type Error = Void; - - fn pre_visit_expr( - &mut self, - expr: &mut Expr<'ast, ast::Type<'ast>>, - ) -> Result<(), Self::Error> { - let mut extracted = vec![]; - if let Expr::Call { args, .. } = expr { - // TODO(grfn): replace with drain_filter once it's stabilized - let mut i = 0; - while i != args.len() { - if args[i].type_() == &ast::Type::Unit { - let expr = args.remove(i); - if !matches!(expr, Expr::Literal(Literal::Unit, _)) { - extracted.push(expr) - }; - } else { - i += 1 - } - } - } - - if !extracted.is_empty() { - let body = mem::replace(expr, Expr::Literal(Literal::Unit, ast::Type::Unit)); - *expr = Expr::Let { - bindings: extracted - .into_iter() - .map(|expr| Binding { - pat: Pattern::Id( - Ident::from_str_unchecked("___discarded"), - expr.type_().clone(), - ), - body: expr, - }) - .collect(), - type_: body.type_().clone(), - body: Box::new(body), - }; - } - - Ok(()) - } - - fn post_visit_call( - &mut self, - _fun: &mut Expr<'ast, ast::Type<'ast>>, - _type_args: &mut HashMap<Ident<'ast>, ast::Type<'ast>>, - args: &mut Vec<Expr<'ast, ast::Type<'ast>>>, - ) -> Result<(), Self::Error> { - args.retain(|arg| arg.type_() != &ast::Type::Unit); - Ok(()) - } - - fn visit_type(&mut self, type_: &mut ast::Type<'ast>) -> Result<(), Self::Error> { - if let ast::Type::Function(ft) = type_ { - ft.args.retain(|a| a != &ast::Type::Unit); - } - Ok(()) - } - - fn post_visit_fun_decl( - &mut self, - _name: &mut Ident<'ast>, - _type_args: &mut Vec<Ident>, - args: &mut Vec<(Ident, ast::Type<'ast>)>, - _body: &mut Box<Expr<ast::Type<'ast>>>, - _type_: &mut ast::Type<'ast>, - ) -> Result<(), Self::Error> { - args.retain(|(_, ty)| ty != &ast::Type::Unit); - Ok(()) - } -} - -pub(crate) fn run_toplevel<'a>(toplevel: &mut Vec<Decl<'a, ast::Type<'a>>>) { - let mut pass = StripPositiveUnits {}; - for decl in toplevel.iter_mut() { - pass.visit_decl(decl).void_unwrap(); - } -} - -#[cfg(test)] -mod tests { - use super::*; - use crate::parser::toplevel; - use crate::tc::typecheck_toplevel; - use pretty_assertions::assert_eq; - - #[test] - fn unit_only_arg() { - let (_, program) = toplevel( - "ty f : fn () -> int - fn f _ = 1 - - ty main : fn -> int - fn main = f ()", - ) - .unwrap(); - - let (_, expected) = toplevel( - "ty f : fn -> int - fn f = 1 - - ty main : fn -> int - fn main = f()", - ) - .unwrap(); - let expected = typecheck_toplevel(expected).unwrap(); - - let mut program = typecheck_toplevel(program).unwrap(); - run_toplevel(&mut program); - - assert_eq!(program, expected); - } - - #[test] - fn unit_and_other_arg() { - let (_, program) = toplevel( - "ty f : fn (), int -> int - fn f _ x = x - - ty main : fn -> int - fn main = f () 1", - ) - .unwrap(); - - let (_, expected) = toplevel( - "ty f : fn int -> int - fn f x = x - - ty main : fn -> int - fn main = f 1", - ) - .unwrap(); - let expected = typecheck_toplevel(expected).unwrap(); - - let mut program = typecheck_toplevel(program).unwrap(); - run_toplevel(&mut program); - - assert_eq!(program, expected); - } - - #[test] - fn unit_expr_and_other_arg() { - let (_, program) = toplevel( - "ty f : fn (), int -> int - fn f _ x = x - - ty g : fn int -> () - fn g _ = () - - ty main : fn -> int - fn main = f (g 2) 1", - ) - .unwrap(); - - let (_, expected) = toplevel( - "ty f : fn int -> int - fn f x = x - - ty g : fn int -> () - fn g _ = () - - ty main : fn -> int - fn main = let ___discarded = g 2 in f 1", - ) - .unwrap(); - assert_eq!(expected.len(), 6); - let expected = typecheck_toplevel(expected).unwrap(); - - let mut program = typecheck_toplevel(program).unwrap(); - run_toplevel(&mut program); - - assert_eq!(program, expected); - } -} |