From a6db3bf0dc5d69e7980384015a509498f07db0f0 Mon Sep 17 00:00:00 2001 From: David Li Date: Tue, 7 Nov 2017 18:31:59 -0500 Subject: Move translation to analysis module --- src/main.rs | 2 +- src/semantic/analysis.rs | 248 ++++++++++++++++++++++++++++++++++++++++++++++ src/semantic/mod.rs | 2 + src/semantic/translate.rs | 248 ---------------------------------------------- 4 files changed, 251 insertions(+), 249 deletions(-) create mode 100644 src/semantic/analysis.rs diff --git a/src/main.rs b/src/main.rs index bb12399..0579fc8 100644 --- a/src/main.rs +++ b/src/main.rs @@ -21,7 +21,7 @@ fn main() { let program = taiga::parse_Program(&input); println!("{:?}", program); if let Ok(program) = program { - println!("{:?}", semantic::translate::translate(&program)); + println!("{:?}", semantic::analysis::translate(&program)); } } else { diff --git a/src/semantic/analysis.rs b/src/semantic/analysis.rs new file mode 100644 index 0000000..21a9eb8 --- /dev/null +++ b/src/semantic/analysis.rs @@ -0,0 +1,248 @@ +// Copyright ⓒ 2017 David Li. +// This Source Code Form is subject to the terms of the Mozilla Public +// License, v. 2.0. If a copy of the MPL was not distributed with this +// file, You can obtain one at http://mozilla.org/MPL/2.0/. + +use ::ast::{self, WithLocation}; +use super::environment; +use super::types::{self, Ty}; + +#[derive(Debug)] +pub enum TypeError { + Unimplemented, + LengthMismatch { + expected: usize, + actual: usize, + }, + Mismatch { + expected: Ty, + actual: Ty, + }, + UnboundName, +} + +type TypeEnvironment<'a> = environment::Environment<'a, String, Ty>; +pub type Result = ::std::result::Result>; + +pub fn translate(program: &ast::Program) -> Result { + let mut venv = TypeEnvironment::new(None); + let mut tenv = TypeEnvironment::new(None); + tenv.add_binding("int".into(), Ty::Int); + tenv.add_binding("string".into(), Ty::String); + trans_exp(&mut venv, &mut tenv, &*program.0) +} + +macro_rules! err { + ($exp: expr, $err: expr) => { + Err(WithLocation::new($err, $exp.start, $exp.end)) + } +} + +fn trans_ty<'a>( + venv: &mut TypeEnvironment<'a>, + tenv: &mut TypeEnvironment<'a>, + ty: &WithLocation) -> Result { + match ty.value { + ast::Ty::Name(ref name) => { + tenv.lookup(&name) + .map(|v| v.clone()) + .ok_or(WithLocation::new(TypeError::UnboundName, ty.start, ty.end)) + } + ast::Ty::Array(ref inner_ty) => { + trans_ty(venv, tenv, &inner_ty) + }, + ast::Ty::Record(ref fields) => { + let mut result = vec![]; + for field in fields { + result.push(types::RecordField::new( + field.name.clone(), + trans_ty(venv, tenv, &field.ty)?)); + } + Ok(Ty::Record(result)) + }, + } +} + +fn trans_decl<'a>( + venv: &mut TypeEnvironment<'a>, + tenv: &mut TypeEnvironment<'a>, + decl: &WithLocation) -> Result { + match decl.declaration { + ast::DeclarationBody::Fun { ref ty, ref params, ref body } => { + let declared_ty = if let &Some(ref ty) = ty { + Some(ast::WithLocation::new(trans_ty(venv, tenv, &ty)?, ty.start, ty.end)) + } else { None }; + + let mut new_venv = TypeEnvironment::new(Some(venv)); + let mut new_tenv = TypeEnvironment::new(Some(tenv)); + let mut arg_types = vec![]; + for param in params.iter() { + let arg_ty = trans_ty(&mut new_venv, &mut new_tenv, ¶m.ty)?; + arg_types.push(arg_ty.clone()); + new_venv.add_binding(param.name.value.clone(), arg_ty); + } + + let body_ty = trans_exp(&mut new_venv, &mut new_tenv, &*body)?; + + if let Some(decl_ty) = declared_ty { + if &decl_ty.value != &body_ty { + return err!(decl_ty, TypeError::Mismatch { + expected: decl_ty.value, + actual: body_ty, + }); + } + } + + Ok(Ty::Function(arg_types, Box::new(body_ty))) + } + ast::DeclarationBody::Ty { ref ty } => { + trans_ty(venv, tenv, ty) + } + ast::DeclarationBody::Var { ref ty, ref value } => { + let actual_ty = trans_exp(venv, tenv, &value)?; + if let &Some(ref ty) = ty { + let decl_ty = trans_ty(venv, tenv, &ty)?; + if decl_ty != actual_ty { + return err!(ty, TypeError::Mismatch { + expected: decl_ty, + actual: actual_ty, + }); + } + } + Ok(actual_ty) + } + } +} + +fn trans_exp<'a>( + venv: &mut TypeEnvironment<'a>, + tenv: &mut TypeEnvironment<'a>, + exp: &WithLocation) -> Result { + use ast::Expression::*; + + match &exp.value { + &Let(ref decls, ref body) => { + let mut new_venv = TypeEnvironment::new(Some(venv)); + let mut new_tenv = TypeEnvironment::new(Some(tenv)); + for decl in decls.iter() { + let decl_ty = trans_decl(&mut new_venv, &mut new_tenv, decl)?; + match decl.declaration { + ast::DeclarationBody::Fun { .. } | ast::DeclarationBody::Var { .. } => { + new_venv.add_binding(decl.name.clone(), decl_ty); + } + ast::DeclarationBody::Ty { .. } => { + new_tenv.add_binding(decl.name.clone(), decl_ty); + } + } + } + trans_exp(&mut new_venv, &mut new_tenv, &*body) + }, + &Call(ref name, ref args) => { + let mut arg_types = vec![]; + for arg in args { + arg_types.push(trans_exp(venv, tenv, arg)?); + } + + let fun_ty = venv.lookup(name) + .ok_or(WithLocation::new(TypeError::UnboundName, + exp.start, exp.end))?; + match fun_ty { + &Ty::Function(ref expected_args, ref result) => { + if expected_args.len() != arg_types.len() { + return err!(exp, TypeError::LengthMismatch { + expected: expected_args.len(), + actual: arg_types.len(), + }); + } + for (i, (provided_ty, expected_ty)) in + arg_types.iter().zip(expected_args).enumerate() { + if provided_ty != expected_ty { + return err!(args[i], TypeError::Mismatch { + expected: expected_ty.clone(), + actual: provided_ty.clone(), + }) + } + } + Ok((**result).clone()) + }, + otherwise => { + err!(exp, TypeError::Mismatch { + // TODO: better way to handle this + expected: Ty::Function(arg_types, Box::new(Ty::Nil)), + actual: otherwise.clone(), + }) + } + } + }, + &UnaryOp(ref op, ref operand) => { + use ast::UnaryOp::*; + let operand_ty = trans_exp(venv, tenv, operand)?; + match op { + &Neg | &Pos => { + match operand_ty { + Ty::Int => { + Ok(Ty::Int) + } + other => { + err!(operand, TypeError::Mismatch { + expected: Ty::Int, + actual: other, + }) + } + } + } + &Not => { + err!(exp, TypeError::Unimplemented) + } + } + }, + &BinOp(ref op, ref left, ref right) => { + use ast::BinOp::*; + let left_ty = trans_exp(venv, tenv, left)?; + let right_ty = trans_exp(venv, tenv, right)?; + match op { + &Add => { + match (left_ty, right_ty) { + (Ty::Int, Ty::Int) => { + Ok(Ty::Int) + } + (Ty::String, Ty::String) => { + Ok(Ty::String) + } + (Ty::Int, other) | (other, Ty::Int) => { + err!(right, TypeError::Mismatch { + expected: Ty::Int, + actual: other, + }) + } + (Ty::String, other) | (other, Ty::String) => { + err!(right, TypeError::Mismatch { + expected: Ty::String, + actual: other, + }) + } + _ => { + err!(exp, TypeError::Unimplemented) + } + } + } + _ => { + err!(exp, TypeError::Unimplemented) + } + } + }, + &Number(_) => Ok(Ty::Int), + &String(_) => Ok(Ty::String), + &Name(ref name) => { + if let Some(ty) = venv.lookup(name) { + Ok(ty.clone()) + } + else { + err!(exp, TypeError::UnboundName) + } + }, + &Nil => { + Err(WithLocation::new(TypeError::Unimplemented, exp.start, exp.end)) + }, + } +} diff --git a/src/semantic/mod.rs b/src/semantic/mod.rs index afc56ef..5fe773c 100644 --- a/src/semantic/mod.rs +++ b/src/semantic/mod.rs @@ -3,8 +3,10 @@ // License, v. 2.0. If a copy of the MPL was not distributed with this // file, You can obtain one at http://mozilla.org/MPL/2.0/. +pub mod analysis; pub mod environment; pub mod frame; +pub mod ir; pub mod temp; pub mod translate; pub mod types; diff --git a/src/semantic/translate.rs b/src/semantic/translate.rs index a5a9557..e69de29 100644 --- a/src/semantic/translate.rs +++ b/src/semantic/translate.rs @@ -1,248 +0,0 @@ -// Copyright ⓒ 2017 David Li. -// This Source Code Form is subject to the terms of the Mozilla Public -// License, v. 2.0. If a copy of the MPL was not distributed with this -// file, You can obtain one at http://mozilla.org/MPL/2.0/. - -use ::ast::{self, WithLocation}; -use super::environment; -use super::types::{self, Ty}; - -#[derive(Debug)] -pub enum TypeError { - Unimplemented, - LengthMismatch { - expected: usize, - actual: usize, - }, - Mismatch { - expected: Ty, - actual: Ty, - }, - UnboundName, -} - -type TypeEnvironment<'a> = environment::Environment<'a, String, Ty>; -pub type Result = ::std::result::Result>; - -pub fn translate(program: &ast::Program) -> Result { - let mut venv = TypeEnvironment::new(None); - let mut tenv = TypeEnvironment::new(None); - tenv.add_binding("int".into(), Ty::Int); - tenv.add_binding("string".into(), Ty::String); - trans_exp(&mut venv, &mut tenv, &*program.0) -} - -macro_rules! err { - ($exp: expr, $err: expr) => { - Err(WithLocation::new($err, $exp.start, $exp.end)) - } -} - -fn trans_ty<'a>( - venv: &mut TypeEnvironment<'a>, - tenv: &mut TypeEnvironment<'a>, - ty: &WithLocation) -> Result { - match ty.value { - ast::Ty::Name(ref name) => { - tenv.lookup(&name) - .map(|v| v.clone()) - .ok_or(WithLocation::new(TypeError::UnboundName, ty.start, ty.end)) - } - ast::Ty::Array(ref inner_ty) => { - trans_ty(venv, tenv, &inner_ty) - }, - ast::Ty::Record(ref fields) => { - let mut result = vec![]; - for field in fields { - result.push(types::RecordField::new( - field.name.clone(), - trans_ty(venv, tenv, &field.ty)?)); - } - Ok(Ty::Record(result)) - }, - } -} - -fn trans_decl<'a>( - venv: &mut TypeEnvironment<'a>, - tenv: &mut TypeEnvironment<'a>, - decl: &WithLocation) -> Result { - match decl.declaration { - ast::DeclarationBody::Fun { ref ty, ref params, ref body } => { - let declared_ty = if let &Some(ref ty) = ty { - Some(ast::WithLocation::new(trans_ty(venv, tenv, &ty)?, ty.start, ty.end)) - } else { None }; - - let mut new_venv = TypeEnvironment::new(Some(venv)); - let mut new_tenv = TypeEnvironment::new(Some(tenv)); - let mut arg_types = vec![]; - for param in params.iter() { - let arg_ty = trans_ty(&mut new_venv, &mut new_tenv, ¶m.ty)?; - arg_types.push(arg_ty.clone()); - new_venv.add_binding(param.name.value.clone(), arg_ty); - } - - let body_ty = trans_exp(&mut new_venv, &mut new_tenv, &*body)?; - - if let Some(decl_ty) = declared_ty { - if &decl_ty.value != &body_ty { - return err!(decl_ty, TypeError::Mismatch { - expected: decl_ty.value, - actual: body_ty, - }); - } - } - - Ok(Ty::Function(arg_types, Box::new(body_ty))) - } - ast::DeclarationBody::Ty { ref ty } => { - trans_ty(venv, tenv, ty) - } - ast::DeclarationBody::Var { ref ty, ref value } => { - let actual_ty = trans_exp(venv, tenv, &value)?; - if let &Some(ref ty) = ty { - let decl_ty = trans_ty(venv, tenv, &ty)?; - if decl_ty != actual_ty { - return err!(ty, TypeError::Mismatch { - expected: decl_ty, - actual: actual_ty, - }); - } - } - Ok(actual_ty) - } - } -} - -fn trans_exp<'a>( - venv: &mut TypeEnvironment<'a>, - tenv: &mut TypeEnvironment<'a>, - exp: &WithLocation) -> Result { - use ast::Expression::*; - - match &exp.value { - &Let(ref decls, ref body) => { - let mut new_venv = TypeEnvironment::new(Some(venv)); - let mut new_tenv = TypeEnvironment::new(Some(tenv)); - for decl in decls.iter() { - let decl_ty = trans_decl(&mut new_venv, &mut new_tenv, decl)?; - match decl.declaration { - ast::DeclarationBody::Fun { .. } | ast::DeclarationBody::Var { .. } => { - new_venv.add_binding(decl.name.clone(), decl_ty); - } - ast::DeclarationBody::Ty { .. } => { - new_tenv.add_binding(decl.name.clone(), decl_ty); - } - } - } - trans_exp(&mut new_venv, &mut new_tenv, &*body) - }, - &Call(ref name, ref args) => { - let mut arg_types = vec![]; - for arg in args { - arg_types.push(trans_exp(venv, tenv, arg)?); - } - - let fun_ty = venv.lookup(name) - .ok_or(WithLocation::new(TypeError::UnboundName, - exp.start, exp.end))?; - match fun_ty { - &Ty::Function(ref expected_args, ref result) => { - if expected_args.len() != arg_types.len() { - return err!(exp, TypeError::LengthMismatch { - expected: expected_args.len(), - actual: arg_types.len(), - }); - } - for (i, (provided_ty, expected_ty)) in - arg_types.iter().zip(expected_args).enumerate() { - if provided_ty != expected_ty { - return err!(args[i], TypeError::Mismatch { - expected: expected_ty.clone(), - actual: provided_ty.clone(), - }) - } - } - Ok((**result).clone()) - }, - otherwise => { - err!(exp, TypeError::Mismatch { - // TODO: better way to handle this - expected: Ty::Function(arg_types, Box::new(Ty::Nil)), - actual: otherwise.clone(), - }) - } - } - }, - &UnaryOp(ref op, ref operand) => { - use ast::UnaryOp::*; - let operand_ty = trans_exp(venv, tenv, operand)?; - match op { - &Neg | &Pos => { - match operand_ty { - Ty::Int => { - Ok(Ty::Int) - } - other => { - err!(operand, TypeError::Mismatch { - expected: Ty::Int, - actual: other, - }) - } - } - } - &Not => { - err!(exp, TypeError::Unimplemented) - } - } - }, - &BinOp(ref op, ref left, ref right) => { - use ast::BinOp::*; - let left_ty = trans_exp(venv, tenv, left)?; - let right_ty = trans_exp(venv, tenv, right)?; - match op { - &Add => { - match (left_ty, right_ty) { - (Ty::Int, Ty::Int) => { - Ok(Ty::Int) - } - (Ty::String, Ty::String) => { - Ok(Ty::String) - } - (Ty::Int, other) => { - err!(right, TypeError::Mismatch { - expected: Ty::Int, - actual: other, - }) - } - (Ty::String, other) => { - err!(right, TypeError::Mismatch { - expected: Ty::String, - actual: other, - }) - } - _ => { - err!(exp, TypeError::Unimplemented) - } - } - } - _ => { - err!(exp, TypeError::Unimplemented) - } - } - }, - &Number(_) => Ok(Ty::Int), - &String(_) => Ok(Ty::String), - &Name(ref name) => { - if let Some(ty) = venv.lookup(name) { - Ok(ty.clone()) - } - else { - err!(exp, TypeError::UnboundName) - } - }, - &Nil => { - Err(WithLocation::new(TypeError::Unimplemented, exp.start, exp.end)) - }, - } -} -- cgit v1.2.3