From cd546710a6c97645bf7128bf07af0a08408e477d 2021-03-14 21:41:03 From: MH Date: 2021-03-14 21:41:03 Subject: [PATCH] WIP on type inference: finishing linker part --- diff --git a/src/protocol/ast.rs b/src/protocol/ast.rs index 8bd519561abcbe43e9ae72b072cb647cf56d877b..e293677ea5b26a0c226fbca3ba5572bcf4810408 100644 --- a/src/protocol/ast.rs +++ b/src/protocol/ast.rs @@ -669,6 +669,11 @@ impl<'a> NamespacedIdentifierIter<'a> { pub(crate) fn num_remaining(&self) -> u8 { return self.num_total - self.num_returned } + pub(crate) fn returned_section(&self) -> &[u8] { + // Offset always includes the two trailing ':' characters + let end = if self.cur_offset >= 2 { self.cur_offset - 2 } else { self.cur_offset }; + return &self.value[..end] + } } impl<'a> Iterator for NamespacedIdentifierIter<'a> { @@ -777,7 +782,8 @@ pub struct SymbolicParserType { #[derive(Debug, Clone, serde::Serialize, serde::Deserialize)] pub enum SymbolicParserTypeVariant { Definition(DefinitionId), - PolyArg(usize), // index of polyarg in the definition + // TODO: figure out if I need the DefinitionId here + PolyArg(DefinitionId, usize), // index of polyarg in the definition } #[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)] diff --git a/src/protocol/parser/mod.rs b/src/protocol/parser/mod.rs index cfae1b9fce0e6870ffbba6f0c1667b8c4708aac9..55863e937755362f19a0a6deb35d74b09b6751d1 100644 --- a/src/protocol/parser/mod.rs +++ b/src/protocol/parser/mod.rs @@ -5,6 +5,7 @@ mod type_table; mod type_resolver; mod visitor; mod visitor_linker; +mod utils; use depth_visitor::*; use symbol_table::SymbolTable; diff --git a/src/protocol/parser/type_table.rs b/src/protocol/parser/type_table.rs index f26598128f29e2ea9ae212ee0f08edc8bad3e0df..6a1acd0e24e14d773634aa79191664fb8b0c7433 100644 --- a/src/protocol/parser/type_table.rs +++ b/src/protocol/parser/type_table.rs @@ -84,11 +84,11 @@ impl TypeClass { } pub(crate) fn is_data_type(&self) -> bool { - self == TypeClass::Enum || self == TypeClass::Union || self == TypeClass::Struct + *self == TypeClass::Enum || *self == TypeClass::Union || *self == TypeClass::Struct } pub(crate) fn is_proc_type(&self) -> bool { - self == TypeClass::Function || self == TypeClass::Component + *self == TypeClass::Function || *self == TypeClass::Component } } @@ -467,7 +467,7 @@ impl TypeTable { let mut poly_args = self.create_initial_poly_args(&definition.poly_vars); for variant in &variants { if let Some(embedded) = variant.parser_type { - self.check_and_resolve_embedded_type_and_modify_poly_args(ctx, &mut poly_args, root_id, embedded)?; + self.check_and_resolve_embedded_type_and_modify_poly_args(ctx, definition_id, &mut poly_args, root_id, embedded)?; } } let is_polymorph = poly_args.iter().any(|arg| arg.is_in_use); @@ -575,7 +575,7 @@ impl TypeTable { // Construct representation of polymorphic arguments let mut poly_args = self.create_initial_poly_args(&definition.poly_vars); for field in &fields { - self.check_and_resolve_embedded_type_and_modify_poly_args(ctx, &mut poly_args, root_id, field.parser_type)?; + self.check_and_resolve_embedded_type_and_modify_poly_args(ctx, definition_id, &mut poly_args, root_id, field.parser_type)?; } let is_polymorph = poly_args.iter().any(|arg| arg.is_in_use); @@ -641,9 +641,9 @@ impl TypeTable { // Construct polymorphic arguments let mut poly_args = self.create_initial_poly_args(&definition.poly_vars); - self.check_and_resolve_embedded_type_and_modify_poly_args(ctx, &mut poly_args, root_id, definition.return_type)?; + self.check_and_resolve_embedded_type_and_modify_poly_args(ctx, definition_id, &mut poly_args, root_id, definition.return_type)?; for argument in &arguments { - self.check_and_resolve_embedded_type_and_modify_poly_args(ctx, &mut poly_args, root_id, argument.parser_type)?; + self.check_and_resolve_embedded_type_and_modify_poly_args(ctx, definition_id, &mut poly_args, root_id, argument.parser_type)?; } let is_polymorph = poly_args.iter().any(|arg| arg.is_in_use); @@ -704,7 +704,7 @@ impl TypeTable { // Construct polymorphic arguments let mut poly_args = self.create_initial_poly_args(&definition.poly_vars); for argument in &arguments { - self.check_and_resolve_embedded_type_and_modify_poly_args(ctx, &mut poly_args, root_id, argument.parser_type)?; + self.check_and_resolve_embedded_type_and_modify_poly_args(ctx, definition_id, &mut poly_args, root_id, argument.parser_type)?; } let is_polymorph = poly_args.iter().any(|v| v.is_in_use); @@ -930,7 +930,9 @@ impl TypeTable { /// when the embedded type is a polymorphic variable or points to another /// user-defined type. fn check_and_resolve_embedded_type_and_modify_poly_args( - &mut self, ctx: &mut TypeCtx, poly_args: &mut [PolyArg], root_id: RootId, embedded_type_id: ParserTypeId, + &mut self, ctx: &mut TypeCtx, + type_definition_id: DefinitionId, poly_args: &mut [PolyArg], + root_id: RootId, embedded_type_id: ParserTypeId, ) -> Result<(), ParseError2> { use ParserTypeVariant as PTV; @@ -967,7 +969,7 @@ impl TypeTable { // polyargs as well debug_assert!(symbolic.poly_args.is_empty(), "got polymorphic arguments to a polymorphic variable"); debug_assert!(symbolic.variant.is_none(), "symbolic parser type's variant already resolved"); - symbolic.variant = Some(SymbolicParserTypeVariant::PolyArg(poly_arg_idx)); + symbolic.variant = Some(SymbolicParserTypeVariant::PolyArg(type_definition_id, poly_arg_idx)); continue 'type_loop; } } diff --git a/src/protocol/parser/utils.rs b/src/protocol/parser/utils.rs new file mode 100644 index 0000000000000000000000000000000000000000..5650c9ba98491e455cc50756aa1501f339135777 --- /dev/null +++ b/src/protocol/parser/utils.rs @@ -0,0 +1,94 @@ +use crate::protocol::ast::*; +use crate::protocol::inputsource::*; +use super::symbol_table::*; +use super::type_table::*; + +/// Utility result type. +pub(crate) enum FindTypeResult<'t, 'i> { + // Found the type exactly + Found(&'t DefinedType), + // Could not match symbol + SymbolNotFound{ident_pos: InputPosition}, + // Matched part of the namespaced identifier, but not completely + SymbolPartial{ident_pos: InputPosition, symbol_pos: InputPosition, ident_iter: NamespacedIdentifierIter<'i>}, + // Symbol matched, but points to a namespace/module instead of a type + SymbolNamespace{ident_pos: InputPosition, symbol_pos: InputPosition}, +} + +impl<'t, 'i> FindTypeResult<'t, 'i> { + /// Utility function to transform the `FindTypeResult` into a `Result` where + /// `Ok` contains the resolved type, and `Err` contains a `ParseError` which + /// can be readily returned. This is the most common use. + pub(crate) fn as_parse_error(self, module_source: &InputSource) -> Result<&'t DefinedType, ParseError2> { + match self { + FindTypeResult::Found(defined_type) => Ok(defined_type), + FindTypeResult::SymbolNotFound{ident_pos} => { + Err(ParseError2::new_error( + module_source, ident_pos, + "Could not resolve this identifier to a symbol" + )) + }, + FindTypeResult::SymbolPartial{ident_pos, symbol_pos, ident_iter} => { + Err(ParseError2::new_error( + module_source, ident_pos, + "Could not fully resolve this identifier to a symbol" + ).with_postfixed_info( + module_source, symbol_pos, + &format!( + "The partial identifier '{}' was matched to this symbol", + String::from_utf8_lossy(ident_iter.returned_section()), + ) + )) + }, + FindTypeResult::SymbolNamespace{ident_pos, symbol_pos} => { + Err(ParseError2::new_error( + module_source, ident_pos, + "This identifier was resolved to a namespace instead of a type" + ).with_postfixed_info( + module_source, symbol_pos, + "This is the referenced namespace" + )) + } + } + } +} + +/// Attempt to find the type pointer to by a (root, identifier) combination. The +/// type must match exactly (no parts in the namespace iterator remaining) and +/// must be a type, not a namespace. +pub(crate) fn find_type_definition<'t, 'i>( + symbols: &SymbolTable, types: &'t TypeTable, + root_id: RootId, identifier: &'i NamespacedIdentifier +) -> FindTypeResult<'t, 'i> { + // Lookup symbol + let symbol = symbols.resolve_namespaced_symbol(root_id, identifier); + if symbol.is_none() { + return FindTypeResult::SymbolNotFound{ident_pos: identifier.position}; + } + + // Make sure we resolved it exactly + let (symbol, ident_iter) = symbol.unwrap(); + if ident_iter.num_remaining() != 0 { + return FindTypeResult::SymbolPartial{ + ident_pos: identifier.position, + symbol_pos: symbol.position, + ident_iter + }; + } + + match symbol.symbol { + Symbol::Namespace(_) => { + FindTypeResult::SymbolNamespace{ + ident_pos: identifier.position, + symbol_pos: symbol.position + } + }, + Symbol::Definition((_, definition_id)) => { + // If this function is called correctly, then we should always be + // able to match the definition's ID to an entry in the type table. + let definition = types.get_base_definition(&definition_id); + debug_assert!(definition.is_some()); + FindTypeResult::Found(definition.unwrap()) + } + } +} \ No newline at end of file diff --git a/src/protocol/parser/visitor_linker.rs b/src/protocol/parser/visitor_linker.rs index 32cc8bc151f81871d6ebd72780ef6861198296bf..89421241b027c69b4debabdcaec58f62fdfdf124 100644 --- a/src/protocol/parser/visitor_linker.rs +++ b/src/protocol/parser/visitor_linker.rs @@ -1,8 +1,10 @@ -use std::mem::{replace, swap}; - use crate::protocol::ast::*; use crate::protocol::inputsource::*; -use crate::protocol::parser::{symbol_table::*, type_table::*}; +use crate::protocol::parser::{ + symbol_table::*, + type_table::*, + utils::*, +}; use super::visitor::{ STMT_BUFFER_INIT_CAPACITY, @@ -12,7 +14,6 @@ use super::visitor::{ Visitor2, VisitorResult }; -use crate::protocol::ast::ExpressionParent::ExpressionStmt; #[derive(PartialEq, Eq)] enum DefinitionType { @@ -867,7 +868,7 @@ impl Visitor2 for ValidityAndLinkerVisitor { let parser_type_id = self.parser_type_buffer.pop().unwrap(); let parser_type = &ctx.heap[parser_type_id]; - match &parser_type.variant { + let (symbolic_variant, num_inferred_to_allocate) = match &parser_type.variant { PTV::Message | PTV::Bool | PTV::Byte | PTV::Short | PTV::Int | PTV::Long | PTV::String | @@ -885,20 +886,89 @@ impl Visitor2 for ValidityAndLinkerVisitor { PTV::Symbolic(symbolic) => { // Retrieve poly_vars from function/component definition to // match against. - let poly_vars = match self.def_type { + let (definition_id, poly_vars) = match self.def_type { DefinitionType::None => unreachable!(), - DefinitionType::Primitive(id) => &ctx.heap[id].poly_vars, - DefinitionType::Composite(id) => &ctx.heap[id].poly_vars, - DefinitionType::Function(id) => &ctx.heap[id].poly_vars, + DefinitionType::Primitive(id) => (id.upcast(), &ctx.heap[id].poly_vars), + DefinitionType::Composite(id) => (id.upcast(), &ctx.heap[id].poly_vars), + DefinitionType::Function(id) => (id.upcast(), &ctx.heap[id].poly_vars), }; + let mut symbolic_variant = None; for (poly_var_idx, poly_var) in poly_vars.iter().enumerate() { if symbolic.identifier.value == poly_var.value { + // Type refers to a polymorphic variable. + // TODO: @hkt Maybe allow higher-kinded types? + if !symbolic.poly_args.is_empty() { + return Err(ParseError2::new_error( + &ctx.module.source, symbolic.identifier.position, + "Polymorphic arguments to a polymorphic variable (higher-kinded types) are not allowed (yet)" + )); + } + symbolic_variant = Some(SymbolicParserTypeVariant::PolyArg(definition_id, poly_var_idx)); + } + } + if let Some(symbolic_variant) = symbolic_variant { + (symbolic_variant, 0) + } else { + // Must be a user-defined type, otherwise an error + let found_type = find_type_definition( + &ctx.symbols, &ctx.types, ctx.module.root_id, &symbolic.identifier + ).as_parse_error(&ctx.module.source)?; + symbolic_variant = Some(SymbolicParserTypeVariant::Definition(found_type.ast_definition)); + + // TODO: @function_ptrs: Allow function pointers at some + // point in the future + if found_type.definition.type_class().is_proc_type() { + return Err(ParseError2::new_error( + &ctx.module.source, symbolic.identifier.position, + &format!( + "This identifier points to a {} type, expected a datatype", + found_type.definition.type_class() + ) + )); + } + + // If the type is polymorphic then we have two cases: if + // the programmer did not specify the polyargs then we + // assume we're going to infer all of them. Otherwise we + // make sure that they match in count. + if !found_type.poly_args.is_empty() && symbolic.poly_args.is_empty() { + // All inferred + ( + SymbolicParserTypeVariant::Definition(found_type.ast_definition), + found_type.poly_args.len() + ) + } else if symbolic.poly_args.len() != found_type.poly_args.len() { + return Err(ParseError2::new_error( + &ctx.module.source, symbolic.identifier.position, + &format!( + "Expected {} polymorpic arguments (or none, to infer them), but {} were specified", + found_type.poly_args.len(), symbolic.poly_args.len() + ) + )) + } else { + // If here then the type is not polymorphic, or all + // types are properly specified by the user. + for specified_poly_arg in &symbolic.poly_args { + self.parser_type_buffer.push(*specified_poly_arg); + } + + (SymbolicParserTypeVariant::Definition(found_type.ast_definition), 0) } } } + }; + + // If here then type is symbolic, perform a mutable borrow to set + // the target of the symbolic type. + for _ in 0..num_inferred_to_allocate { + self.parser_type_buffer.push(ctx.heap.alloc_parser_type(|this| ParserType{ + this, + position: + })) } + if let PTV::Symbolic(symbolic) = } Ok(())