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

Changeset - f34349cabe17

Parent rev.

Child rev.

[Not reviewed]

0 3 0

MH - 3 years ago 2022-02-25 11:54:59
contact@maxhenger.nl

WIP: Fix bug related to builtin procedure typechecking

3 files changed with 23 insertions and 12 deletions:

src/protocol/parser/mod.rs

src/protocol/parser/pass_typing.rs

src/protocol/parser/type_table.rs

0 comments (0 inline, 0 general)

src/protocol/parser/mod.rs

➞

Show inline comments

@@ @@ -208,224 +208,224 @@ impl Parser { @@
         insert_builtin_function(&mut parser, "create", &["T"], |id| (
             vec![
                 ("length", quick_type(&[PTV::IntegerLike]))
             ],
             quick_type(&[PTV::ArrayLike, PTV::PolymorphicArgument(id.upcast(), 0)])
         ));
         insert_builtin_function(&mut parser, "length", &["T"], |id| (
             vec![
                 ("array", quick_type(&[PTV::ArrayLike, PTV::PolymorphicArgument(id.upcast(), 0)]))
             ],
             quick_type(&[PTV::UInt32]) // TODO: @PtrInt
         ));
         insert_builtin_function(&mut parser, "assert", &[], |_id| (
             vec![
                 ("condition", quick_type(&[PTV::Bool])),
             ],
             quick_type(&[PTV::Void])
         ));
         insert_builtin_function(&mut parser, "print", &[], |_id| (
             vec![
                 ("message", quick_type(&[PTV::String])),
             ],
             quick_type(&[PTV::Void])
         ));
         parser
+    }
     pub fn feed(&mut self, mut source: InputSource) -> Result<(), ParseError> {
         let mut token_buffer = TokenBuffer::new();
         self.pass_tokenizer.tokenize(&mut source, &mut token_buffer)?;
         let module = Module{
             source,
             tokens: token_buffer,
             root_id: RootId::new_invalid(),
             name: None,
             version: None,
             phase: ModuleCompilationPhase::Tokenized,
         };
         self.modules.push(module);
         Ok(())
+    }
     pub fn parse(&mut self) -> Result<(), ParseError> {
         let mut pass_ctx = PassCtx{
             heap: &mut self.heap,
             symbols: &mut self.symbol_table,
             pool: &mut self.string_pool,
             arch: &self.arch,
         };
         // Advance all modules to the phase where all symbols are scanned
         for module_idx in 0..self.modules.len() {
             self.pass_symbols.parse(&mut self.modules, module_idx, &mut pass_ctx)?;
+        }
         // With all symbols scanned, perform further compilation until we can
         // add all base types to the type table.
         for module_idx in 0..self.modules.len() {
             self.pass_import.parse(&mut self.modules, module_idx, &mut pass_ctx)?;
             self.pass_definitions.parse(&mut self.modules, module_idx, &mut pass_ctx)?;
+        }
         // Add every known type to the type table
         self.type_table.build_base_types(&mut self.modules, &mut pass_ctx)?;
         // Continue compilation with the remaining phases now that the types
         // are all in the type table
         for module_idx in 0..self.modules.len() {
             let mut ctx = visitor::Ctx{
                 heap: &mut self.heap,
                 modules: &mut self.modules,
                 module_idx,
                 symbols: &mut self.symbol_table,
                 types: &mut self.type_table,
                 arch: &self.arch,
             };
             self.pass_validation.visit_module(&mut ctx)?;
+        }
         // Perform typechecking on all modules
         let mut queue = ResolveQueue::new();
         for module_idx in 0..self.modules.len() {
             let mut ctx = visitor::Ctx{
                 heap: &mut self.heap,
                 modules: &mut self.modules,
                 module_idx,
                 symbols: &mut self.symbol_table,
                 types: &mut self.type_table,
                 arch: &self.arch,
             };
             self.pass_typing.queue_module_definitions(&mut ctx, &mut queue);
         };
         while !queue.is_empty() {
-            let top = queue.pop().unwrap();
+            let top = queue.pop_front().unwrap();
             let mut ctx = visitor::Ctx{
                 heap: &mut self.heap,
                 modules: &mut self.modules,
                 module_idx: top.root_id.index as usize,
                 symbols: &mut self.symbol_table,
                 types: &mut self.type_table,
                 arch: &self.arch,
             };
             self.pass_typing.handle_module_definition(&mut ctx, &mut queue, top)?;
+        }
         // Rewrite nodes in tree, then prepare for execution of code
         for module_idx in 0..self.modules.len() {
             self.modules[module_idx].phase = ModuleCompilationPhase::Typed;
             let mut ctx = visitor::Ctx{
                 heap: &mut self.heap,
                 modules: &mut self.modules,
                 module_idx,
                 symbols: &mut self.symbol_table,
                 types: &mut self.type_table,
                 arch: &self.arch,
             };
             self.pass_rewriting.visit_module(&mut ctx)?;
             self.pass_stack_size.visit_module(&mut ctx)?;
+        }
         // Write out desired information
         if let Some(filename) = &self.write_ast_to {
             let mut writer = ASTWriter::new();
             let mut file = std::fs::File::create(std::path::Path::new(filename)).unwrap();
             writer.write_ast(&mut file, &self.heap);
+        }
         Ok(())
+    }
+}
 fn insert_builtin_type(type_table: &mut TypeTable, parts: Vec<ConcreteTypePart>, has_poly_var: bool, size: usize, alignment: usize) -> TypeId {
     const POLY_VARS: [PolymorphicVariable; 1] = [PolymorphicVariable{
         identifier: Identifier::new_empty(InputSpan::new()),
         is_in_use: false,
     }];
     let concrete_type = ConcreteType{ parts };
     let poly_var = if has_poly_var {
         POLY_VARS.as_slice()
     } else {
         &[]
     };
     return type_table.add_builtin_data_type(concrete_type, poly_var, size, alignment);
+}
 // Note: args and return type need to be a function because we need to know the function ID.
 fn insert_builtin_function<T: Fn(ProcedureDefinitionId) -> (Vec<(&'static str, ParserType)>, ParserType)> (
     p: &mut Parser, func_name: &str, polymorphic: &[&str], arg_and_return_fn: T
 ) {
     // Insert into AST (to get an ID), also prepare the polymorphic variables
     // we need later for the type table
     let mut ast_poly_vars = Vec::with_capacity(polymorphic.len());
     let mut type_poly_vars = Vec::with_capacity(polymorphic.len());
     for poly_var in polymorphic {
         let identifier = Identifier{ span: InputSpan::new(), value: p.string_pool.intern(poly_var.as_bytes()) } ;
         ast_poly_vars.push(identifier.clone());
         type_poly_vars.push(PolymorphicVariable{ identifier, is_in_use: false });
+    }
     let func_ident_ref = p.string_pool.intern(func_name.as_bytes());
     let procedure_id = p.heap.alloc_procedure_definition(|this| ProcedureDefinition {
         this,
         defined_in: RootId::new_invalid(),
         builtin: true,
         kind: ProcedureKind::Function,
         span: InputSpan::new(),
         identifier: Identifier{ span: InputSpan::new(), value: func_ident_ref.clone() },
         poly_vars: ast_poly_vars,
         return_type: None,
         parameters: Vec::new(),
         scope: ScopeId::new_invalid(),
         body: BlockStatementId::new_invalid(),
         monomorphs: Vec::new(),
     });
     // Modify AST with more information about the procedure
     let (arguments, return_type) = arg_and_return_fn(procedure_id);
     let mut parameters = Vec::with_capacity(arguments.len());
     for (arg_name, arg_type) in arguments {
         let identifier = Identifier{ span: InputSpan::new(), value: p.string_pool.intern(arg_name.as_bytes()) };
         let param_id = p.heap.alloc_variable(|this| Variable{
             this,
             kind: VariableKind::Parameter,
             parser_type: arg_type.clone(),
             identifier,
             relative_pos_in_parent: 0,
             unique_id_in_scope: 0
         });
         parameters.push(param_id);
+    }
     let func = &mut p.heap[procedure_id];
     func.parameters = parameters;
     func.return_type = Some(return_type);
     // Insert into symbol table
     p.symbol_table.insert_symbol(SymbolScope::Global, Symbol{
         name: func_ident_ref,
         variant: SymbolVariant::Definition(SymbolDefinition{
             defined_in_module: RootId::new_invalid(),
             defined_in_scope: SymbolScope::Global,
             definition_span: InputSpan::new(),
             identifier_span: InputSpan::new(),
             imported_at: None,
             class: DefinitionClass::Function,
             definition_id: procedure_id.upcast(),
         })
     }).unwrap();
     // Insert into type table
     let mut concrete_type = ConcreteType::default();
     concrete_type.parts.push(ConcreteTypePart::Function(procedure_id, type_poly_vars.len() as u32));
     for _ in 0..type_poly_vars.len() {
         concrete_type.parts.push(ConcreteTypePart::Void); // doesn't matter (I hope...)
+    }
     p.type_table.add_builtin_procedure_type(concrete_type, &type_poly_vars);
     // let mut concrete_type = ConcreteType::default();
     // concrete_type.parts.push(ConcreteTypePart::Function(procedure_id, type_poly_vars.len() as u32));
     //
     // for _ in 0..type_poly_vars.len() {
     //     concrete_type.parts.push(ConcreteTypePart::Void); // doesn't matter (I hope...)
     // }
     // p.type_table.add_builtin_procedure_type(concrete_type, &type_poly_vars);
+}
@@ \ No newline at end of file @@

src/protocol/parser/pass_typing.rs

➞

Show inline comments

 /// pass_typing
 ///
 /// Performs type inference and type checking. Type inference is implemented by
 /// applying constraints on (sub)trees of types. During this process the
 /// resolver takes the `ParserType` structs (the representation of the types
 /// written by the programmer), converts them to `InferenceType` structs (the
 /// temporary data structure used during type inference) and attempts to arrive
 /// at `ConcreteType` structs (the representation of a fully checked and
 /// validated type).
 ///
 /// The resolver will visit every statement and expression relevant to the
 /// procedure and insert and determine its initial type based on context (e.g. a
 /// return statement's expression must match the function's return type, an
 /// if statement's test expression must evaluate to a boolean). When all are
 /// visited we attempt to make progress in evaluating the types. Whenever a type
 /// is progressed we queue the related expressions for further type progression.
 /// Once no more expressions are in the queue the algorithm is finished. At this
 /// point either all types are inferred (or can be trivially implicitly
 /// determined), or we have incomplete types. In the latter case we return an
 /// error.
 ///
 /// TODO: Needs a thorough rewrite:
 ///  0. polymorph_progress is intentionally broken at the moment. Make it work
 ///     again and use a normal VecSomething.
 ///  1. The foundation for doing all of the work with predetermined indices
 ///     instead of with HashMaps is there, but it is not really used because of
 ///     time constraints. When time is available, rewrite the system such that
 ///     AST IDs are not needed, and only indices into arrays are used.
 ///  2. Remove the `msg` type?
 ///  3. Disallow certain types in certain operations (e.g. `Void`).
 macro_rules! debug_log_enabled {
     () => { false };
+}
 macro_rules! debug_log {
     ($format:literal) => {
         enabled_debug_print!(false, "types", $format);
     };
     ($format:literal, $($args:expr),*) => {
         enabled_debug_print!(false, "types", $format, $($args),*);
     };
+}
 use std::collections::VecDeque;
 use crate::collections::{ScopedBuffer, ScopedSection, DequeSet};
 use crate::protocol::ast::*;
 use crate::protocol::input_source::ParseError;
 use crate::protocol::parser::ModuleCompilationPhase;
 use crate::protocol::parser::type_table::*;
 use crate::protocol::parser::token_parsing::*;
 use super::visitor::{
     BUFFER_INIT_CAP_LARGE,
     BUFFER_INIT_CAP_SMALL,
     Ctx,
 };
 // -----------------------------------------------------------------------------
 // Inference type
 // -----------------------------------------------------------------------------
 const VOID_TEMPLATE: [InferenceTypePart; 1] = [ InferenceTypePart::Void ];
 const MESSAGE_TEMPLATE: [InferenceTypePart; 2] = [ InferenceTypePart::Message, InferenceTypePart::UInt8 ];
 const BOOL_TEMPLATE: [InferenceTypePart; 1] = [ InferenceTypePart::Bool ];
 const CHARACTER_TEMPLATE: [InferenceTypePart; 1] = [ InferenceTypePart::Character ];
 const STRING_TEMPLATE: [InferenceTypePart; 2] = [ InferenceTypePart::String, InferenceTypePart::Character ];
 const NUMBERLIKE_TEMPLATE: [InferenceTypePart; 1] = [ InferenceTypePart::NumberLike ];
 const INTEGERLIKE_TEMPLATE: [InferenceTypePart; 1] = [ InferenceTypePart::IntegerLike ];
 const ARRAY_TEMPLATE: [InferenceTypePart; 2] = [ InferenceTypePart::Array, InferenceTypePart::Unknown ];
 const SLICE_TEMPLATE: [InferenceTypePart; 2] = [ InferenceTypePart::Slice, InferenceTypePart::Unknown ];
 const ARRAYLIKE_TEMPLATE: [InferenceTypePart; 2] = [ InferenceTypePart::ArrayLike, InferenceTypePart::Unknown ];
 /// TODO: @performance Turn into PartialOrd+Ord to simplify checks
 #[derive(Debug, Clone, Eq, PartialEq)]
 pub(crate) enum InferenceTypePart {
     // When we infer types of AST elements that support polymorphic arguments,
     // then we might have the case that multiple embedded types depend on the
     // polymorphic type (e.g. func bla(T a, T[] b) -> T[][]). If we can infer
     // the type in one place (e.g. argument a), then we may propagate this
     // information to other types (e.g. argument b and the return type). For
     // this reason we place markers in the `InferenceType` instances such that
     // we know which part of the type was originally a polymorphic argument.
     Marker(u32),
     // Completely unknown type, needs to be inferred
     Unknown,
     // Partially known type, may be inferred to to be the appropriate related
     // type.
     // IndexLike,      // index into array/slice
     NumberLike,     // any kind of integer/float
     IntegerLike,    // any kind of integer
     ArrayLike,      // array or slice. Note that this must have a subtype
     PortLike,       // input or output port
     // Special types that cannot be instantiated by the user
     Void, // For builtin functions that do not return anything
     // Concrete types without subtypes
     Bool,
     UInt8,
     UInt16,
     UInt32,
     UInt64,
     SInt8,
     SInt16,
     SInt32,
     SInt64,
     Character,
     String,
     // One subtype
     Message,
     Array,
     Slice,
     Input,
     Output,
     // Tuple with any number of subtypes (for practical reasons 1 element is impossible)
     Tuple(u32),
     // A user-defined type with any number of subtypes
     Instance(DefinitionId, u32)
+}
 impl InferenceTypePart {
     fn is_marker(&self) -> bool {
         match self {
             InferenceTypePart::Marker(_) => true,
             _ => false,
+        }
+    }
     /// Checks if the type is concrete, markers are interpreted as concrete
     /// types.
     fn is_concrete(&self) -> bool {
         use InferenceTypePart as ITP;
         match self {
             ITP::Unknown | ITP::NumberLike |
             ITP::IntegerLike | ITP::ArrayLike | ITP::PortLike => false,
             _ => true
+        }
+    }
     fn is_concrete_number(&self) -> bool {
         use InferenceTypePart as ITP;
         match self {
             ITP::UInt8 | ITP::UInt16 | ITP::UInt32 | ITP::UInt64 |
@@ @@ -727,193 +729,193 @@ impl InferenceType { @@
 impl Default for InferenceType {
     fn default() -> Self {
         Self{
             has_marker: false,
             is_done: false,
             parts: Vec::new(),
+        }
+    }
+}
 /// Iterator over the subtrees that follow a marker in an `InferenceType`
 /// instance. Returns immutable slices over the internal parts
 struct InferenceTypeMarkerIter<'a> {
     parts: &'a [InferenceTypePart],
     idx: usize,
+}
 impl<'a> InferenceTypeMarkerIter<'a> {
     fn new(parts: &'a [InferenceTypePart]) -> Self {
         Self{ parts, idx: 0 }
+    }
+}
 impl<'a> Iterator for InferenceTypeMarkerIter<'a> {
     type Item = (u32, &'a [InferenceTypePart]);
     fn next(&mut self) -> Option<Self::Item> {
         // Iterate until we find a marker
         while self.idx < self.parts.len() {
             if let InferenceTypePart::Marker(marker) = self.parts[self.idx] {
                 // Found a marker, find the subtree end
                 let start_idx = self.idx + 1;
                 let end_idx = InferenceType::find_subtree_end_idx(self.parts, start_idx);
                 // Modify internal index, then return items
                 self.idx = end_idx;
                 return Some((marker, &self.parts[start_idx..end_idx]));
+            }
             self.idx += 1;
+        }
         None
+    }
+}
 #[derive(Debug, PartialEq, Eq)]
 enum DualInferenceResult {
     Neither,        // neither argument is clarified
     First,          // first argument is clarified using the second one
     Second,         // second argument is clarified using the first one
     Both,           // both arguments are clarified
     Incompatible,   // types are incompatible: programmer error
+}
 impl DualInferenceResult {
     fn modified_lhs(&self) -> bool {
         match self {
             DualInferenceResult::First | DualInferenceResult::Both => true,
             _ => false
+        }
+    }
     fn modified_rhs(&self) -> bool {
         match self {
             DualInferenceResult::Second | DualInferenceResult::Both => true,
             _ => false
+        }
+    }
+}
 #[derive(Debug, PartialEq, Eq)]
 enum SingleInferenceResult {
     Unmodified,
     Modified,
     Incompatible
+}
 // -----------------------------------------------------------------------------
 // PassTyping - Public Interface
 // -----------------------------------------------------------------------------
 type InferNodeIndex = usize;
 type PolyDataIndex = isize;
 type VarDataIndex = usize;
 pub(crate) struct ResolveQueueElement {
     // Note that using the `definition_id` and the `monomorph_idx` one may
     // query the type table for the full procedure type, thereby retrieving
     // the polymorphic arguments to the procedure.
     pub(crate) root_id: RootId,
     pub(crate) definition_id: DefinitionId,
     pub(crate) reserved_type_id: TypeId,
     pub(crate) reserved_monomorph_index: u32,
+}
-pub(crate) type ResolveQueue = Vec<ResolveQueueElement>;
+pub(crate) type ResolveQueue = VecDeque<ResolveQueueElement>;
 struct InferenceNode {
     // filled in during type inference
     expr_type: InferenceType,               // result type from expression
     expr_id: ExpressionId,                  // expression that is evaluated
     inference_rule: InferenceRule,          // rule used to infer node type
     parent_index: Option<InferNodeIndex>,   // parent of inference node
     field_index: i32,                       // index of struct field or tuple member
     poly_data_index: PolyDataIndex,         // index to inference data for polymorphic types
     // filled in once type inference is done
     info_type_id: TypeId,
     info_variant: ExpressionInfoVariant,
+}
 impl InferenceNode {
     #[inline]
     fn as_expression_info(&self) -> ExpressionInfo {
         return ExpressionInfo {
             type_id: self.info_type_id,
             variant: self.info_variant
+        }
+    }
+}
 /// Inferencing rule to apply. Some of these are reasonably generic. Other ones
 /// require so much custom logic that we'll not try to come up with an
 /// abstraction.
 enum InferenceRule {
     Noop,
     MonoTemplate(InferenceRuleTemplate),
     BiEqual(InferenceRuleBiEqual),
     TriEqualArgs(InferenceRuleTriEqualArgs),
     TriEqualAll(InferenceRuleTriEqualAll),
     Concatenate(InferenceRuleTwoArgs),
     IndexingExpr(InferenceRuleIndexingExpr),
     SlicingExpr(InferenceRuleSlicingExpr),
     SelectStructField(InferenceRuleSelectStructField),
     SelectTupleMember(InferenceRuleSelectTupleMember),
     LiteralStruct(InferenceRuleLiteralStruct),
     LiteralEnum,
     LiteralUnion(InferenceRuleLiteralUnion),
     LiteralArray(InferenceRuleLiteralArray),
     LiteralTuple(InferenceRuleLiteralTuple),
     CastExpr(InferenceRuleCastExpr),
     CallExpr(InferenceRuleCallExpr),
     VariableExpr(InferenceRuleVariableExpr),
+}
 impl InferenceRule {
     union_cast_method_impl!(as_mono_template, InferenceRuleTemplate, InferenceRule::MonoTemplate);
     union_cast_method_impl!(as_bi_equal, InferenceRuleBiEqual, InferenceRule::BiEqual);
     union_cast_method_impl!(as_tri_equal_args, InferenceRuleTriEqualArgs, InferenceRule::TriEqualArgs);
     union_cast_method_impl!(as_tri_equal_all, InferenceRuleTriEqualAll, InferenceRule::TriEqualAll);
     union_cast_method_impl!(as_concatenate, InferenceRuleTwoArgs, InferenceRule::Concatenate);
     union_cast_method_impl!(as_indexing_expr, InferenceRuleIndexingExpr, InferenceRule::IndexingExpr);
     union_cast_method_impl!(as_slicing_expr, InferenceRuleSlicingExpr, InferenceRule::SlicingExpr);
     union_cast_method_impl!(as_select_struct_field, InferenceRuleSelectStructField, InferenceRule::SelectStructField);
     union_cast_method_impl!(as_select_tuple_member, InferenceRuleSelectTupleMember, InferenceRule::SelectTupleMember);
     union_cast_method_impl!(as_literal_struct, InferenceRuleLiteralStruct, InferenceRule::LiteralStruct);
     union_cast_method_impl!(as_literal_union, InferenceRuleLiteralUnion, InferenceRule::LiteralUnion);
     union_cast_method_impl!(as_literal_array, InferenceRuleLiteralArray, InferenceRule::LiteralArray);
     union_cast_method_impl!(as_literal_tuple, InferenceRuleLiteralTuple, InferenceRule::LiteralTuple);
     union_cast_method_impl!(as_cast_expr, InferenceRuleCastExpr, InferenceRule::CastExpr);
     union_cast_method_impl!(as_call_expr, InferenceRuleCallExpr, InferenceRule::CallExpr);
     union_cast_method_impl!(as_variable_expr, InferenceRuleVariableExpr, InferenceRule::VariableExpr);
+}
 // Note: InferenceRuleTemplate is `Copy`, so don't add dynamically allocated
 // members in the future (or review places where this struct is copied)
 #[derive(Clone, Copy)]
 struct InferenceRuleTemplate {
     template: &'static [InferenceTypePart],
     application: InferenceRuleTemplateApplication,
+}
 impl InferenceRuleTemplate {
     fn new_none() -> Self {
         return Self{
             template: &[],
             application: InferenceRuleTemplateApplication::None,
         };
+    }
     fn new_forced(template: &'static [InferenceTypePart]) -> Self {
         return Self{
             template,
             application: InferenceRuleTemplateApplication::Forced,
         };
+    }
     fn new_template(template: &'static [InferenceTypePart]) -> Self {
         return Self{
             template,
             application: InferenceRuleTemplateApplication::Template,
+        }
+    }
@@ @@ -1052,193 +1054,193 @@ struct PolyData { @@
 // silly structure, just so we can use `PolyDataTypeIndex` ergonomically while
 // making sure we're still capable of borrowing from `poly_vars`.
 struct PolyDataTypes {
     /// Inferred types of associated types (e.g. struct fields, tuple members,
     /// function arguments). These types may depend on the polymorphic variables
     /// defined above.
     associated: Vec<InferenceType>,
     /// Inferred "returned" type (e.g. if a struct field is selected, then this
     /// contains the type of the selected field, for a function call it contains
     /// the return type). May depend on the polymorphic variables defined above.
     returned: InferenceType,
+}
 #[derive(Clone, Copy)]
 enum PolyDataTypeIndex {
     Associated(usize), // indexes into `PolyData.associated`
     Returned,
+}
 impl PolyDataTypes {
     fn get_type(&self, index: PolyDataTypeIndex) -> &InferenceType {
         match index {
             PolyDataTypeIndex::Associated(index) => return &self.associated[index],
             PolyDataTypeIndex::Returned => return &self.returned,
+        }
+    }
     fn get_type_mut(&mut self, index: PolyDataTypeIndex) -> &mut InferenceType {
         match index {
             PolyDataTypeIndex::Associated(index) => return &mut self.associated[index],
             PolyDataTypeIndex::Returned => return &mut self.returned,
+        }
+    }
+}
 struct VarData {
     var_id: VariableId,
     var_type: InferenceType,
     used_at: Vec<InferNodeIndex>, // of variable expressions
     linked_var: Option<VarDataIndex>,
+}
 impl PassTyping {
     pub(crate) fn new() -> Self {
         PassTyping {
             reserved_type_id: TypeId::new_invalid(),
             reserved_monomorph_index: u32::MAX,
             procedure_id: ProcedureDefinitionId::new_invalid(),
             procedure_kind: ProcedureKind::Function,
             poly_vars: Vec::new(),
             parent_index: None,
             var_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_LARGE),
             expr_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_LARGE),
             stmt_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_LARGE),
             bool_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_SMALL),
             index_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_SMALL),
             definition_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_LARGE),
             poly_progress_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_SMALL),
             infer_nodes: Vec::with_capacity(BUFFER_INIT_CAP_LARGE),
             poly_data: Vec::with_capacity(BUFFER_INIT_CAP_SMALL),
             var_data: Vec::with_capacity(BUFFER_INIT_CAP_SMALL),
             node_queued: DequeSet::new(),
+        }
+    }
     pub(crate) fn queue_module_definitions(&mut self, ctx: &mut Ctx, queue: &mut ResolveQueue) {
         debug_assert_eq!(ctx.module().phase, ModuleCompilationPhase::ValidatedAndLinked);
         let root_id = ctx.module().root_id;
         let root = &ctx.heap.protocol_descriptions[root_id];
         let definitions_section = self.definition_buffer.start_section_initialized(&root.definitions);
         for definition_id in definitions_section.iter_copied() {
             let definition = &ctx.heap[definition_id];
             let first_concrete_part_and_procedure_id = match definition {
                 Definition::Procedure(definition) => {
                     if definition.poly_vars.is_empty() {
                         if definition.kind == ProcedureKind::Function {
                             Some((ConcreteTypePart::Function(definition.this, 0), definition.this))
                         } else {
                             Some((ConcreteTypePart::Component(definition.this, 0), definition.this))
+                        }
                     } else {
                         None
+                    }
+                }
                 Definition::Enum(_) | Definition::Struct(_) | Definition::Union(_) => None,
             };
             if let Some((first_concrete_part, procedure_id)) = first_concrete_part_and_procedure_id {
                 let procedure = &mut ctx.heap[procedure_id];
                 let monomorph_index = procedure.monomorphs.len() as u32;
                 procedure.monomorphs.push(ProcedureDefinitionMonomorph::new_invalid());
                 let concrete_type = ConcreteType{ parts: vec![first_concrete_part] };
                 let type_id = ctx.types.reserve_procedure_monomorph_type_id(&definition_id, concrete_type, monomorph_index);
-                queue.push(ResolveQueueElement{
+                queue.push_back(ResolveQueueElement{
                     root_id,
                     definition_id,
                     reserved_type_id: type_id,
                     reserved_monomorph_index: monomorph_index,
                 })
+            }
+        }
         definitions_section.forget();
+    }
     pub(crate) fn handle_module_definition(
         &mut self, ctx: &mut Ctx, queue: &mut ResolveQueue, element: ResolveQueueElement
     ) -> VisitorResult {
         self.reset();
         debug_assert_eq!(ctx.module().root_id, element.root_id);
         debug_assert!(self.poly_vars.is_empty());
         // Prepare for visiting the definition
         self.reserved_type_id = element.reserved_type_id;
         self.reserved_monomorph_index = element.reserved_monomorph_index;
         let proc_base = ctx.types.get_base_definition(&element.definition_id).unwrap();
         if proc_base.is_polymorph {
             let monomorph = ctx.types.get_monomorph(element.reserved_type_id);
             for poly_arg in monomorph.concrete_type.embedded_iter(0) {
                 self.poly_vars.push(ConcreteType{ parts: Vec::from(poly_arg) });
+            }
+        }
         // Visit the definition, setting up the type resolving process, then
         // (attempt to) resolve all types
         self.visit_definition(ctx, element.definition_id)?;
         self.resolve_types(ctx, queue)?;
         Ok(())
+    }
     fn reset(&mut self) {
         self.reserved_type_id = TypeId::new_invalid();
         self.procedure_id = ProcedureDefinitionId::new_invalid();
         self.procedure_kind = ProcedureKind::Function;
         self.poly_vars.clear();
         self.parent_index = None;
         self.infer_nodes.clear();
         self.poly_data.clear();
         self.var_data.clear();
         self.node_queued.clear();
+    }
+}
 // -----------------------------------------------------------------------------
 // PassTyping - Visitor-like implementation
 // -----------------------------------------------------------------------------
 type VisitorResult = Result<(), ParseError>;
 type VisitExprResult = Result<InferNodeIndex, ParseError>;
 impl PassTyping {
     // Definitions
     fn visit_definition(&mut self, ctx: &mut Ctx, id: DefinitionId) -> VisitorResult {
         return visitor_recursive_definition_impl!(self, &ctx.heap[id], ctx);
+    }
     fn visit_enum_definition(&mut self, _: &mut Ctx, _: EnumDefinitionId) -> VisitorResult { return Ok(()) }
     fn visit_struct_definition(&mut self, _: &mut Ctx, _: StructDefinitionId) -> VisitorResult { return Ok(()) }
     fn visit_union_definition(&mut self, _: &mut Ctx, _: UnionDefinitionId) -> VisitorResult { return Ok(()) }
     fn visit_procedure_definition(&mut self, ctx: &mut Ctx, id: ProcedureDefinitionId) -> VisitorResult {
         let procedure_def = &ctx.heap[id];
         self.procedure_id = id;
         self.procedure_kind = procedure_def.kind;
         let body_id = procedure_def.body;
         debug_log!("{}", "-".repeat(50));
         debug_log!("Visiting procedure: '{}' (id: {}, kind: {:?})", procedure_def.identifier.value.as_str(), id.0.index, procedure_def.kind);
         debug_log!("{}", "-".repeat(50));
         // Visit parameters
         let section = self.var_buffer.start_section_initialized(procedure_def.parameters.as_slice());
         for param_id in section.iter_copied() {
             let param = &ctx.heap[param_id];
             let var_type = self.determine_inference_type_from_parser_type_elements(&param.parser_type.elements, true);
             debug_assert!(var_type.is_done, "expected function arguments to be concrete types");
             self.var_data.push(VarData{
                 var_id: param_id,
                 var_type,
                 used_at: Vec::new(),
                 linked_var: None
             })
+        }
         section.forget();
         // Visit all of the expressions within the body
@@ @@ -1978,223 +1980,233 @@ impl PassTyping { @@
             // Prepare storage vector
             let mut num_inference_parts = 0;
             for inference_type in inference_poly_args {
                 num_inference_parts += inference_type.parts.len();
+            }
             let mut concrete_type = ConcreteType{
                 parts: Vec::with_capacity(1 + num_inference_parts),
             };
             concrete_type.parts.push(first_concrete_part);
             // Go through all polymorphic arguments and add them to the concrete
             // types.
             for (poly_idx, poly_type) in inference_poly_args.iter().enumerate() {
                 if !poly_type.is_done {
                     let expr = &ctx.heap[expr_id];
                     let definition = match expr {
                         Expression::Call(expr) => expr.procedure.upcast(),
                         Expression::Literal(expr) => match &expr.value {
                             Literal::Enum(lit) => lit.definition,
                             Literal::Union(lit) => lit.definition,
                             Literal::Struct(lit) => lit.definition,
                             _ => unreachable!()
                         },
                         _ => unreachable!(),
                     };
                     let poly_vars = ctx.heap[definition].poly_vars();
                     return Err(ParseError::new_error_at_span(
                         &ctx.module().source, expr.operation_span(), format!(
                             "could not fully infer the type of polymorphic variable '{}' of this expression (got '{}')",
                             poly_vars[poly_idx].value.as_str(), poly_type.display_name(&ctx.heap)
+                        )
                     ));
+                }
                 poly_type.write_concrete_type(&mut concrete_type);
+            }
             Ok(concrete_type)
+        }
         // Every expression checked, and new monomorphs are queued. Transfer the
         // expression information to the AST. If this is the first time we're
         // visiting this procedure then we assign expression indices as well.
         let procedure = &ctx.heap[self.procedure_id];
         let num_infer_nodes = self.infer_nodes.len();
         let mut monomorph = ProcedureDefinitionMonomorph{
             argument_types: Vec::with_capacity(procedure.parameters.len()),
             expr_info: Vec::with_capacity(num_infer_nodes),
         };
         // For all of the expressions look up the TypeId (or create a new one).
         // For function calls and component instantiations figure out if they
         // need to be typechecked
         for infer_node in self.infer_nodes.iter_mut() {
             // Determine type ID
             let expr = &ctx.heap[infer_node.expr_id];
             // TODO: Maybe optimize? Split insertion up into lookup, then clone
             //  if needed?
             let mut concrete_type = ConcreteType::default();
             infer_node.expr_type.write_concrete_type(&mut concrete_type);
             let info_type_id = ctx.types.add_monomorphed_type(ctx.modules, ctx.heap, ctx.arch, concrete_type)?;
             // Determine procedure type ID, i.e. a called/instantiated
             // procedure's signature.
             let info_variant = if let Expression::Call(expr) = expr {
                 // Construct full function type. If not yet typechecked then
                 // queue it for typechecking.
                 let poly_data = &self.poly_data[infer_node.poly_data_index as usize];
                 debug_assert!(expr.method.is_user_defined() || expr.method.is_public_builtin());
                 let procedure_id = expr.procedure;
                 let num_poly_vars = poly_data.poly_vars.len() as u32;
                 let first_part = match expr.method {
                     Method::UserFunction => ConcreteTypePart::Function(procedure_id, num_poly_vars),
                     Method::UserComponent => ConcreteTypePart::Component(procedure_id, num_poly_vars),
                     _ => ConcreteTypePart::Function(procedure_id, num_poly_vars),
                 };
                 let definition_id = procedure_id.upcast();
                 let signature_type = poly_data_type_to_concrete_type(
                     ctx, infer_node.expr_id, &poly_data.poly_vars, first_part
                 )?;
                 let (type_id, monomorph_index) = if let Some(type_id) = ctx.types.get_procedure_monomorph_type_id(&definition_id, &signature_type.parts) {
                     // Procedure is already typechecked
                     let monomorph_index = ctx.types.get_monomorph(type_id).variant.as_procedure().monomorph_index;
                     (type_id, monomorph_index)
                 } else {
                     // Procedure is not yet typechecked, reserve a TypeID and a monomorph index
                     let procedure_to_check = &mut ctx.heap[procedure_id];
                     let monomorph_index = procedure_to_check.monomorphs.len() as u32;
                     procedure_to_check.monomorphs.push(ProcedureDefinitionMonomorph::new_invalid());
                     let type_id = ctx.types.reserve_procedure_monomorph_type_id(&definition_id, signature_type, monomorph_index);
                     queue.push(ResolveQueueElement{
                     if !procedure_to_check.builtin {
                         // Only perform typechecking on the user-defined
                         // procedures
                         queue.push_back(ResolveQueueElement{
                             root_id: ctx.heap[definition_id].defined_in(),
                             definition_id,
                             reserved_type_id: type_id,
                             reserved_monomorph_index: monomorph_index,
                         });
+                    }
                     (type_id, monomorph_index)
                 };
                 ExpressionInfoVariant::Procedure(type_id, monomorph_index)
             } else if let Expression::Select(_expr) = expr {
                 ExpressionInfoVariant::Select(infer_node.field_index)
             } else {
                 ExpressionInfoVariant::Generic
             };
             infer_node.info_type_id = info_type_id;
             infer_node.info_variant = info_variant;
+        }
         // Write the types of the arguments
         let procedure = &ctx.heap[self.procedure_id];
         for parameter_id in procedure.parameters.iter().copied() {
             let mut concrete = ConcreteType::default();
             let var_data = self.var_data.iter().find(|v| v.var_id == parameter_id).unwrap();
             var_data.var_type.write_concrete_type(&mut concrete);
             let type_id = ctx.types.add_monomorphed_type(ctx.modules, ctx.heap, ctx.arch, concrete)?;
             monomorph.argument_types.push(type_id)
+        }
         println!("DEBUG: For procedure {} with polyargs {:#?}", ctx.heap[self.procedure_id].identifier.value.as_str(), self.poly_vars);
         for infer_node in self.infer_nodes.iter() {
             println!("DEBUG: [{:?}] has type: {}", infer_node.expr_id, infer_node.expr_type.display_name(&ctx.heap));
+        }
         // Determine if we have already assigned type indices to the expressions
         // before (the indices that, for a monomorph, can retrieve the type of
         // the expression).
         let has_type_indices = self.reserved_monomorph_index > 0;
         if has_type_indices {
             // already have indices, so resize and then index into it
             debug_assert!(monomorph.expr_info.is_empty());
             monomorph.expr_info.resize(num_infer_nodes, ExpressionInfo::new_invalid());
             for infer_node in self.infer_nodes.iter() {
                 let type_index = ctx.heap[infer_node.expr_id].type_index();
                 monomorph.expr_info[type_index as usize] = infer_node.as_expression_info();
+            }
         } else {
             // no indices yet, need to be assigned in AST
             for infer_node in self.infer_nodes.iter() {
                 let type_index = monomorph.expr_info.len();
                 monomorph.expr_info.push(infer_node.as_expression_info());
                 *ctx.heap[infer_node.expr_id].type_index_mut() = type_index as i32;
+            }
+        }
         // Push the information into the AST
         let procedure = &mut ctx.heap[self.procedure_id];
         procedure.monomorphs[self.reserved_monomorph_index as usize] = monomorph;
         Ok(())
+    }
     fn progress_inference_rule(&mut self, ctx: &Ctx, node_index: InferNodeIndex) -> Result<(), ParseError> {
         use InferenceRule as IR;
         let node = &self.infer_nodes[node_index];
         match &node.inference_rule {
             IR::Noop =>
                 unreachable!(),
             IR::MonoTemplate(_) =>
                 self.progress_inference_rule_mono_template(ctx, node_index),
             IR::BiEqual(_) =>
                 self.progress_inference_rule_bi_equal(ctx, node_index),
             IR::TriEqualArgs(_) =>
                 self.progress_inference_rule_tri_equal_args(ctx, node_index),
             IR::TriEqualAll(_) =>
                 self.progress_inference_rule_tri_equal_all(ctx, node_index),
             IR::Concatenate(_) =>
                 self.progress_inference_rule_concatenate(ctx, node_index),
             IR::IndexingExpr(_) =>
                 self.progress_inference_rule_indexing_expr(ctx, node_index),
             IR::SlicingExpr(_) =>
                 self.progress_inference_rule_slicing_expr(ctx, node_index),
             IR::SelectStructField(_) =>
                 self.progress_inference_rule_select_struct_field(ctx, node_index),
             IR::SelectTupleMember(_) =>
                 self.progress_inference_rule_select_tuple_member(ctx, node_index),
             IR::LiteralStruct(_) =>
                 self.progress_inference_rule_literal_struct(ctx, node_index),
             IR::LiteralEnum =>
                 self.progress_inference_rule_literal_enum(ctx, node_index),
             IR::LiteralUnion(_) =>
                 self.progress_inference_rule_literal_union(ctx, node_index),
             IR::LiteralArray(_) =>
                 self.progress_inference_rule_literal_array(ctx, node_index),
             IR::LiteralTuple(_) =>
                 self.progress_inference_rule_literal_tuple(ctx, node_index),
             IR::CastExpr(_) =>
                 self.progress_inference_rule_cast_expr(ctx, node_index),
             IR::CallExpr(_) =>
                 self.progress_inference_rule_call_expr(ctx, node_index),
             IR::VariableExpr(_) =>
                 self.progress_inference_rule_variable_expr(ctx, node_index),
+        }
+    }
     fn progress_inference_rule_mono_template(&mut self, ctx: &Ctx, node_index: InferNodeIndex) -> Result<(), ParseError> {
         let node = &self.infer_nodes[node_index];
         let rule = *node.inference_rule.as_mono_template();
         let progress = self.progress_template(ctx, node_index, rule.application, rule.template)?;
         if progress { self.queue_node_parent(node_index); }
         return Ok(());
+    }
     fn progress_inference_rule_bi_equal(&mut self, ctx: &Ctx, node_index: InferNodeIndex) -> Result<(), ParseError> {
         let node = &self.infer_nodes[node_index];
         let rule = node.inference_rule.as_bi_equal();
         let template = rule.template;
         let arg_index = rule.argument_index;
         let base_progress = self.progress_template(ctx, node_index, template.application, template.template)?;
         let (node_progress, arg_progress) = self.apply_equal2_constraint(ctx, node_index, node_index, 0, arg_index, 0)?;
         if base_progress || node_progress { self.queue_node_parent(node_index); }
         if arg_progress { self.queue_node(arg_index); }
         return Ok(())
+    }

src/protocol/parser/type_table.rs

➞

Show inline comments

@@ @@ -383,193 +383,192 @@ impl MonoSearchKey { @@
         self.set_top_type(concrete_type_parts[0]);
         let mut poly_var_index = 0;
         for subtype in ConcreteTypeIter::new(concrete_type_parts, 0) {
             let in_use = poly_var_in_use[poly_var_index].is_in_use;
             poly_var_index += 1;
             self.push_subtype(subtype, in_use);
+        }
         debug_assert_eq!(poly_var_index, poly_var_in_use.len());
+    }
     /// Starts setting the search key based on an initial top-level type,
     /// programmer must call `push_subtype` the appropriate number of times
     /// after calling this function
     fn set_top_type(&mut self, type_part: ConcreteTypePart) {
         self.parts.clear();
         self.parts.push((Self::KEY_IN_USE, type_part));
         self.change_bit = Self::KEY_CHANGE_BIT;
+    }
     fn push_subtype(&mut self, concrete_type: &[ConcreteTypePart], in_use: bool) {
         let flag = self.change_bit | (if in_use { Self::KEY_IN_USE } else { 0 });
         for part in concrete_type {
             self.parts.push((flag, *part));
+        }
         self.change_bit ^= Self::KEY_CHANGE_BIT;
+    }
     fn push_subtree(&mut self, concrete_type: &[ConcreteTypePart], poly_var_in_use: &[PolymorphicVariable]) {
         self.parts.push((self.change_bit | Self::KEY_IN_USE, concrete_type[0]));
         self.change_bit ^= Self::KEY_CHANGE_BIT;
         let mut poly_var_index = 0;
         for subtype in ConcreteTypeIter::new(concrete_type, 0) {
             let in_use = poly_var_in_use[poly_var_index].is_in_use;
             poly_var_index += 1;
             self.push_subtype(subtype, in_use);
+        }
         debug_assert_eq!(poly_var_index, poly_var_in_use.len());
+    }
     // Utilities for hashing and comparison
     fn find_end_index(&self, start_index: usize) -> usize {
         // Check if we're already at the end
         let mut index = start_index;
         if index >= self.parts.len() {
             return index;
+        }
         // Iterate until bit flips, or until at end
         let expected_bit = self.parts[index].0 & Self::KEY_CHANGE_BIT;
         index += 1;
         while index < self.parts.len() {
             let current_bit = self.parts[index].0 & Self::KEY_CHANGE_BIT;
             if current_bit != expected_bit {
                 return index;
+            }
             index += 1;
+        }
         return index;
+    }
+}
 impl Hash for MonoSearchKey {
     fn hash<H: Hasher>(&self, state: &mut H) {
         for index in 0..self.parts.len() {
             let (flags, part) = self.parts[index];
             if flags & Self::KEY_IN_USE != 0 {
                 part.hash(state);
+            }
+        }
+    }
+}
 impl PartialEq for MonoSearchKey {
     fn eq(&self, other: &Self) -> bool {
         let mut self_index = 0;
         let mut other_index = 0;
         while self_index < self.parts.len() && other_index < other.parts.len() {
             // Retrieve part and flags
             let (self_bits, _) = self.parts[self_index];
             let (other_bits, _) = other.parts[other_index];
             let self_in_use = (self_bits & Self::KEY_IN_USE) != 0;
             let other_in_use = (other_bits & Self::KEY_IN_USE) != 0;
             // Determine ending indices
             let self_end_index = self.find_end_index(self_index);
             let other_end_index = other.find_end_index(other_index);
             if self_in_use == other_in_use {
                 if self_in_use {
                     // Both are in use, so both parts should be equal
                     let delta_self = self_end_index - self_index;
                     let delta_other = other_end_index - other_index;
                     if delta_self != delta_other {
                         // Both in use, but not of equal length, so the types
                         // cannot match
                         return false;
+                    }
                     for _ in 0..delta_self {
                         let (_, self_part) = self.parts[self_index];
                         let (_, other_part) = other.parts[other_index];
                         if self_part != other_part {
                             return false;
+                        }
                         self_index += 1;
                         other_index += 1;
+                    }
                 } else {
                     // Both not in use, so skip associated parts
                     self_index = self_end_index;
                     other_index = other_end_index;
+                }
             } else {
                 // No agreement on importance of parts. This is practically
                 // impossible
                 unreachable!();
+            }
+        }
         // Everything matched, so if we're at the end of both arrays then we're
         // certain that the two keys are equal.
         return self_index == self.parts.len() && other_index == other.parts.len();
+    }
+}
 impl Eq for MonoSearchKey{}
 //------------------------------------------------------------------------------
 // Type table
 //------------------------------------------------------------------------------
 const POLY_VARS_IN_USE: [PolymorphicVariable; 1] = [PolymorphicVariable{ identifier: Identifier::new_empty(InputSpan::new()), is_in_use: true }];
 // Programmer note: keep this struct free of dynamically allocated memory
 #[derive(Clone)]
 struct TypeLoopBreadcrumb {
     type_id: TypeId,
     next_member: u32,
     next_embedded: u32, // for unions, the index into the variant's embedded types
+}
 // Programmer note: keep this struct free of dynamically allocated memory
 #[derive(Clone)]
 struct MemoryBreadcrumb {
     type_id: TypeId,
     next_member: u32,
     next_embedded: u32,
     first_size_alignment_idx: u32,
+}
 #[derive(Debug, PartialEq, Eq)]
 enum TypeLoopResult {
     TypeExists,
     PushBreadcrumb(DefinitionId, ConcreteType),
     TypeLoop(usize), // index into vec of breadcrumbs at which the type matched
+}
 enum MemoryLayoutResult {
     TypeExists(usize, usize), // (size, alignment)
     PushBreadcrumb(MemoryBreadcrumb),
+}
 // TODO: @Optimize, initial memory-unoptimized implementation
 struct TypeLoopEntry {
     type_id: TypeId,
     is_union: bool,
+}
 struct TypeLoop {
     members: Vec<TypeLoopEntry>,
+}
 type DefinitionMap = HashMap<DefinitionId, DefinedType>;
 type MonoTypeMap = HashMap<MonoSearchKey, TypeId>;
 type MonoTypeArray = Vec<MonoType>;
 pub struct TypeTable {
     // Lookup from AST DefinitionId to a defined type. Also lookups for
     // concrete type to monomorphs
     pub(crate) definition_lookup: DefinitionMap,
     mono_type_lookup: MonoTypeMap,

0 comments (0 inline, 0 general)