CSY/reowolf Changeset - cd546710a6c9 · Centrum Wiskunde & Informatica (CWI)

Changeset - cd546710a6c9

Parent rev.

Child rev.

[Not reviewed]

0 4 1

MH - 4 years ago 2021-03-14 21:41:03
henger@cwi.nl

WIP on type inference: finishing linker part

5 files changed with 192 insertions and 19 deletions:

src/protocol/ast.rs

src/protocol/parser/mod.rs

src/protocol/parser/type_table.rs

src/protocol/parser/utils.rs

src/protocol/parser/visitor_linker.rs

0 comments (0 inline, 0 general)

src/protocol/ast.rs

➞

Show inline comments

@@ @@ -660,24 +660,29 @@ pub(crate) struct NamespacedIdentifierIter<'a> { @@
     cur_offset: usize,
     num_returned: u8,
     num_total: u8,
+}
 impl<'a> NamespacedIdentifierIter<'a> {
     pub(crate) fn num_returned(&self) -> u8 {
         return self.num_returned;
+    }
     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> {
     type Item = &'a [u8];
     fn next(&mut self) -> Option<Self::Item> {
         if self.cur_offset >= self.value.len() {
             debug_assert_eq!(self.num_returned, self.num_total);
             None
         } else {
             debug_assert!(self.num_returned < self.num_total);
             let start = self.cur_offset;
             let mut end = start;
@@ @@ -768,25 +773,26 @@ pub struct SymbolicParserType { @@
     pub poly_args: Vec<ParserTypeId>,
     // Phase 2: validation/linking (for types in function/component bodies) and
     //  type table construction (for embedded types of structs/unions)
     pub variant: Option<SymbolicParserTypeVariant>
+}
 /// Specifies whether the symbolic type points to an actual user-defined type,
 /// or whether it points to a polymorphic argument within the definition (e.g.
 /// a defined variable `T var` within a function `int func<T>()`
 #[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)]
 pub enum PrimitiveType {
     Input,
     Output,
     Message,
     Boolean,
     Byte,
     Short,
     Int,
     Long,

src/protocol/parser/mod.rs

➞

Show inline comments

 mod depth_visitor;
 mod symbol_table;
 // mod type_table_old;
 mod type_table;
 mod type_resolver;
 mod visitor;
 mod visitor_linker;
 mod utils;
 use depth_visitor::*;
 use symbol_table::SymbolTable;
 use visitor::Visitor2;
 use visitor_linker::ValidityAndLinkerVisitor;
 use type_table::{TypeTable, TypeCtx};
 use crate::protocol::ast::*;
 use crate::protocol::inputsource::*;
 use crate::protocol::lexer::*;
 use std::collections::HashMap;

src/protocol/parser/type_table.rs

➞

Show inline comments

@@ @@ -75,29 +75,29 @@ pub enum TypeClass { @@
 impl TypeClass {
     pub(crate) fn display_name(&self) -> &'static str {
         match self {
             TypeClass::Enum => "enum",
             TypeClass::Union => "enum",
             TypeClass::Struct => "struct",
             TypeClass::Function => "function",
             TypeClass::Component => "component",
+        }
+    }
     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
+    }
+}
 impl std::fmt::Display for TypeClass {
     fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
         write!(f, "{}", self.display_name())
+    }
+}
 /// Struct wrapping around a potentially polymorphic type. If the type does not
 /// have any polymorphic arguments then it will not have any monomorphs and
 /// `is_polymorph` will be set to `false`. A type with polymorphic arguments
@@ @@ -458,25 +458,25 @@ impl TypeTable { @@
                 })
+            }
             // Ensure union names and polymorphic args do not conflict
             self.check_identifier_collision(
                 ctx, root_id, &variants, |variant| &variant.identifier, "enum variant"
             )?;
             self.check_poly_args_collision(ctx, root_id, &definition.poly_vars)?;
             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);
             // Insert base definition in type table
             self.lookup.insert(definition_id, DefinedType {
                 ast_definition: definition_id,
                 definition: DefinedTypeVariant::Union(UnionType{
                     variants,
                     tag_representation: Self::enum_tag_type(-1, tag_value),
                 }),
                 poly_args,
@@ @@ -566,25 +566,25 @@ impl TypeTable { @@
             })
+        }
         // And make sure no conflicts exist in field names and/or polymorphic args
         self.check_identifier_collision(
             ctx, root_id, &fields, |field| &field.identifier, "struct field"
         )?;
         self.check_poly_args_collision(ctx, root_id, &definition.poly_vars)?;
         // 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);
         self.lookup.insert(definition_id, DefinedType{
             ast_definition: definition_id,
             definition: DefinedTypeVariant::Struct(StructType{
                 fields,
             }),
             poly_args,
             is_polymorph,
             is_pointerlike: false, // TODO: @cyclic
@@ @@ -632,27 +632,27 @@ impl TypeTable { @@
                 parser_type: param.parser_type,
             })
+        }
         // Check conflict of argument and polyarg identifiers
         self.check_identifier_collision(
             ctx, root_id, &arguments, |arg| &arg.identifier, "function argument"
         )?;
         self.check_poly_args_collision(ctx, root_id, &definition.poly_vars)?;
         // 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);
         // Construct entry in type table
         self.lookup.insert(definition_id, DefinedType{
             ast_definition: definition_id,
             definition: DefinedTypeVariant::Function(FunctionType{
                 return_type,
                 arguments,
             }),
             poly_args,
@@ @@ -695,25 +695,25 @@ impl TypeTable { @@
             })
+        }
         // Check conflict of argument and polyarg identifiers
         self.check_identifier_collision(
             ctx, root_id, &arguments, |arg| &arg.identifier, "component argument"
         )?;
         self.check_poly_args_collision(ctx, root_id, &definition.poly_vars)?;
         // 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);
         // Construct entry in type table
         self.lookup.insert(definition_id, DefinedType{
             ast_definition: definition_id,
             definition: DefinedTypeVariant::Component(ComponentType{
                 variant: component_variant,
                 arguments,
             }),
             poly_args,
@@ @@ -921,25 +921,27 @@ impl TypeTable { @@
     /// called on each node in this tree: we assume that each symbolic type was
     /// resolved to either a polymorphic arg or a definition.
     ///
     /// This function will also make sure that if the embedded type has
     /// polymorphic variables itself, that the number of polymorphic variables
     /// matches the number of arguments in the associated definition.
     ///
     /// Finally, for all embedded types (which includes function/component
     /// arguments and return types) in type definitions we will modify the AST
     /// 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;
         self.parser_type_iter.clear();
         self.parser_type_iter.push_back(embedded_type_id);
         'type_loop: while let Some(embedded_type_id) = self.parser_type_iter.pop_back() {
             let embedded_type = &mut ctx.heap[embedded_type_id];
             match &mut embedded_type.variant {
                 PTV::Message | PTV::Bool |
                 PTV::Byte | PTV::Short | PTV::Int | PTV::Long |
@@ @@ -958,25 +960,25 @@ impl TypeTable { @@
                     // Outer type is fixed, but inner type might be symbolix
                     self.parser_type_iter.push_back(*subtype_id);
                 },
                 PTV::Symbolic(symbolic) => {
                     for (poly_arg_idx, poly_arg) in poly_args.iter_mut().enumerate() {
                         if poly_arg.identifier.value == symbolic.identifier.value {
                             poly_arg.is_in_use = true;
                             // TODO: If we allow higher-kinded types in the future,
                             //  then we can't continue here, but must resolve the
                             //  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;
+                        }
+                    }
                     // Must match a definition
                     let symbol = ctx.symbols.resolve_namespaced_symbol(root_id, &symbolic.identifier);
                     debug_assert!(symbol.is_some(), "could not resolve symbolic parser type when determining poly args");
                     let (symbol, ident_iter) = symbol.unwrap();
                     debug_assert_eq!(ident_iter.num_remaining(), 0, "no exact symbol match when determining poly args");
                     let (_root_id, definition_id) = symbol.as_definition().unwrap();
                     // Must be a struct, enum, or union

src/protocol/parser/utils.rs

➞

Show inline comments

@@ new file 100644 @@
 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 @@

src/protocol/parser/visitor_linker.rs

➞

Show inline comments

 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,
     EXPR_BUFFER_INIT_CAPACITY,
     TYPE_BUFFER_INIT_CAPACITY,
     Ctx,
     Visitor2,
     VisitorResult
 };
 use crate::protocol::ast::ExpressionParent::ExpressionStmt;
 #[derive(PartialEq, Eq)]
 enum DefinitionType {
     None,
     Primitive(ComponentId),
     Composite(ComponentId),
     Function(FunctionId)
+}
 impl DefinitionType {
     fn is_primitive(&self) -> bool { if let Self::Primitive(_) = self { true } else { false } }
     fn is_composite(&self) -> bool { if let Self::Composite(_) = self { true } else { false } }
@@ @@ -858,57 +859,126 @@ impl Visitor2 for ValidityAndLinkerVisitor { @@
         // definition or symbolic type. Alternatively to throw an error if we
         // cannot resolve the ParserType to either of these (polymorphic) types.
         use ParserTypeVariant as PTV;
         debug_assert!(!self.performing_breadth_pass);
         let init_num_types = self.parser_type_buffer.len();
         self.parser_type_buffer.push(id);
         'resolve_loop: while self.parser_type_buffer.len() > init_num_types {
             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 |
                 PTV::IntegerLiteral | PTV::Inferred => {
                     // Builtin types or types that do not require recursion
                     continue 'resolve_loop;
                 },
                 PTV::Array(subtype_id) |
                 PTV::Input(subtype_id) |
                 PTV::Output(subtype_id) => {
                     // Requires recursing
                     self.parser_type_buffer.push(*subtype_id);
                     continue 'resolve_loop;
                 },
                 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(())
+    }
+}
 enum FindOfTypeResult {
     // Identifier was exactly matched, type matched as well
     Found(DefinitionId),
     // Identifier was matched, but the type differs from the expected one
     TypeMismatch(&'static str),
     // Identifier could not be found
     NotFound,

0 comments (0 inline, 0 general)