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

Changeset - 72ffb92a766c

Parent rev.

Child rev.

[Not reviewed]

0 6 0

MH - 4 years ago 2021-03-15 13:19:16
contact@maxhenger.nl

temporarily remove type resolver from modules

6 files changed with 135 insertions and 103 deletions:

notes_max.md

src/protocol/ast_printer.rs

src/protocol/parser/mod.rs

src/protocol/parser/type_resolver.rs

src/protocol/parser/visitor_linker.rs

src/runtime/tests.rs

0 comments (0 inline, 0 general)

notes_max.md

➞

Show inline comments

     In the polymorphic case the inference works the other way around: once we know the output type of the expression that is used as a polymorphic variable, then we can fix that particular polymorphic argument and feed that information to all places where that polymorphic argument is used.
     The same is true for the return type: if the return type of the call is polymorphic then the place where this return type is used determines the type of the polymorphic argument.
 - **constant expression**: *This requires a lot of rework at some point.*
     A constant expression contains a literal of a specific type. Hence the output type of the literal is the type of the literal itself. In case of literal `struct`, `enum` and `union` instances the output type is that exact datatype.
     For the embedded types we have two cases: if the embedded type is not polymorphic and some expression is used at that position, then the embedded type must match the output type of the expression. If the embedded type is polymorphic then the output type of the expression determines the polymorphic argument.
     In case of `string` literals the output type is also a `string`. However, in the case of integer literals we can only determine that the output type is some integer, the place where the literal is employed determines the integer type. It is valid to use this for byteshifting, but also for operating on floating-point types. In the case of decimal literals we can use these for operations on floating point types. But again: whether it is a `float` or a `double` depends on the place where the literal is used.
 - **variable expression**:
     Refers to some variable declared somewhere. Hence the return type is the same as the type of the variable.
@@ \ No newline at end of file @@
     Refers to some variable declared somewhere. Hence the return type is the same as the type of the variable.
 ## Type Inference - The Concrete Algorithmic Steps
 Lets start with places where the parser types (i.e. not the types assigned to the nodes in the expression trees) are actually specified:
 - Function and component arguments
 - Function return types
 - Local variable declarations (from both regular and channel variables)
 - Struct fields
 - Enum variants
 For now we do not consider struct/enum/union literals yet. We perform type inference in bodies of functions/components. Whenever we actually lay out a monomorphed proctype we already know the polymorphic arguments of that proctype. Hence, by definition, we know all the types of the proctype arguments and function return types of the proctype we're resolving.
 Hence we encounter:
 - Inferred types of variable declarations: These may be fully inferred, partially inferred, or depend on the polymorphic variables of the wrapping proctype's polymorphic arguments (which are determined). Hence if they're somehow inferred, then we mark them as such.
 - Inferred types of polyargs of called functions/components: Special case where we use the return type of the proctype and the expressions used as arguments to determine the polymorphic types. Once we know the polymorphic types we may determine other types, or the other way around. Now that I think about it, this seems like a special case of inference in the call/literal expression itself. So there seems to be no reason to pay particular attention to this.
@@ \ No newline at end of file @@

src/protocol/ast_printer.rs

➞

Show inline comments

@@ @@ -265,48 +265,78 @@ impl ASTWriter { @@
     //--------------------------------------------------------------------------
     // Top-level definition writing
     //--------------------------------------------------------------------------
     fn write_definition(&mut self, heap: &Heap, def_id: DefinitionId, indent: usize) {
         let indent2 = indent + 1;
         let indent3 = indent2 + 1;
         let indent4 = indent3 + 1;
         match &heap[def_id] {
             Definition::Struct(_) => todo!("implement Definition::Struct"),
             Definition::Enum(_) => todo!("implement Definition::Enum"),
             Definition::Function(_) => todo!("implement Definition::Function"),
             Definition::Function(def) => {
                 self.kv(indent).with_id(PREFIX_FUNCTION_ID, def.this.0.index)
                     .with_s_key("DefinitionFunction");
                 self.kv(indent2).with_s_key("Name").with_ascii_val(&def.identifier.value);
                 for poly_var_id in &def.poly_vars {
                     self.kv(indent3).with_s_key("PolyVar");
                     self.kv(indent4).with_s_key("Name").with_ascii_val(&poly_var_id.value);
+                }
                 self.kv(indent2).with_s_key("ReturnType").with_custom_val(|s| write_type(s, heap, &heap[def.return_type]));
                 self.kv(indent2).with_s_key("Parameters");
                 for param_id in &def.parameters {
                     self.write_parameter(heap, *param_id, indent3);
+                }
                 self.kv(indent2).with_s_key("Body");
                 self.write_stmt(heap, def.body, indent3);
             },
             Definition::Component(def) => {
                 self.kv(indent).with_id(PREFIX_COMPONENT_ID,def.this.0.index)
                     .with_s_key("DefinitionComponent");
                 self.kv(indent2).with_s_key("Name").with_ascii_val(&def.identifier.value);
                 self.kv(indent2).with_s_key("Variant").with_debug_val(&def.variant);
                 self.kv(indent2).with_s_key("PolymorphicVariables");
                 for poly_var_id in &def.poly_vars {
                     self.kv(indent3).with_s_key("PolyVar");
                     self.kv(indent4).with_s_key("Name").with_ascii_val(&poly_var_id.value);
+                }
                 self.kv(indent2).with_s_key("Parameters");
                 for param_id in &def.parameters {
                     let param = &heap[*param_id];
                     self.kv(indent3).with_id(PREFIX_PARAMETER_ID, param_id.0.index)
                         .with_s_key("Parameter");
                     self.kv(indent4).with_s_key("Name").with_ascii_val(&param.identifier.value);
                     self.kv(indent4).with_s_key("Type").with_custom_val(|w| write_type(w, heap, &heap[param.parser_type]));
                     self.write_parameter(heap, *param_id, indent3)
+                }
                 self.kv(indent2).with_s_key("Body");
                 self.write_stmt(heap, def.body, indent3);
+            }
+        }
+    }
     fn write_parameter(&mut self, heap: &Heap, param_id: ParameterId, indent: usize) {
         let indent2 = indent + 1;
         let param = &heap[param_id];
         self.kv(indent).with_id(PREFIX_PARAMETER_ID, param_id.0.index)
             .with_s_key("Parameter");
         self.kv(indent2).with_s_key("Name").with_ascii_val(&param.identifier.value);
         self.kv(indent2).with_s_key("Type").with_custom_val(|w| write_type(w, heap, &heap[param.parser_type]));
+    }
     fn write_stmt(&mut self, heap: &Heap, stmt_id: StatementId, indent: usize) {
         let stmt = &heap[stmt_id];
         let indent2 = indent + 1;
         let indent3 = indent2 + 1;
         match stmt {
             Statement::Block(stmt) => {
                 self.kv(indent).with_id(PREFIX_BLOCK_STMT_ID, stmt.this.0.index)
                     .with_s_key("Block");
                 for stmt_id in &stmt.statements {
                     self.write_stmt(heap, *stmt_id, indent2);
         PTV::Array(id) => { target.write_str("array"); embedded.push(*id) }
         PTV::Message => { target.write_str("msg"); }
         PTV::Bool => { target.write_str("bool"); }
         PTV::Byte => { target.write_str("byte"); }
         PTV::Short => { target.write_str("short"); }
         PTV::Int => { target.write_str("int"); }
         PTV::Long => { target.write_str("long"); }
         PTV::String => { target.write_str("str"); }
         PTV::IntegerLiteral => { target.write_str("int_lit"); }
         PTV::Inferred => { target.write_str("auto"); }
         PTV::Symbolic(symbolic) => {
             target.write_str(&String::from_utf8_lossy(&symbolic.identifier.value));
             match symbolic.variant {
                 Some(SymbolicParserTypeVariant::PolyArg(def_id, idx)) => {
                     target.write_str(&format!("{{def: {}, idx: {}}}", def_id.index, idx));
                 },
                 Some(SymbolicParserTypeVariant::Definition(def_id)) => {
                     target.write_str(&format!("{{def: {}}}", def_id.index));
                 },
                 None => {
                     target.write_str("{None}");
+                }
+            }
             embedded.extend(&symbolic.poly_args);
+        }
     };
     if !embedded.is_empty() {
         target.write_str("<");
         for (idx, embedded_id) in embedded.into_iter().enumerate() {
             if idx != 0 { target.write_str(", "); }
             write_type(target, heap, &heap[embedded_id]);
+        }
         target.write_str(">");
+    }

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 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::*;

src/protocol/parser/type_resolver.rs

➞

Show inline comments

@@ @@ -46,33 +46,35 @@ impl From<ConcreteTypeVariant> for InferredPart { @@
             CTV::String => IP::String,
             CTV::Array => IP::Array,
             CTV::Slice => IP::Slice,
             CTV::Input => IP::Input,
             CTV::Output => IP::Output,
             CTV::Instance(definition_id, num_sub) => IP::Instance(definition_id, num_sub),
+        }
+    }
+}
 pub(crate) struct InferenceType {
     origin: ParserTypeId,
     done: bool,
     inferred: Vec<InferredPart>,
+}
 impl InferenceType {
     fn new(inferred_type: ParserTypeId) -> Self {
         Self{ origin: inferred_type, inferred: vec![InferredPart::Unknown] }
+        Self{ origin: inferred_type, done: false, inferred: vec![InferredPart::Unknown] }
+    }
     fn assign_concrete(&mut self, concrete_type: &ConcreteType) {
         self.done = true;
         self.inferred.clear();
         self.inferred.reserve(concrete_type.v.len());
         for variant in concrete_type.v {
             self.inferred.push(InferredPart::from(variant))
+        }
+    }
+}
 // TODO: @cleanup I will do a very dirty implementation first, because I have no idea
 //  what I am doing.
 // Very rough idea:
 //  - go through entire AST first, find all places where we have inferred types
@@ @@ -89,38 +91,40 @@ impl InferenceType { @@
 ///     - Type checking arguments to unary and binary operators.
 ///     - Type checking assignment, indexing, slicing and select expressions.
 ///     - Checking arguments to functions and component instantiations.
 ///
 /// This will be achieved by slowly descending into the AST. At any given
 /// expression we may depend on
 pub(crate) struct TypeResolvingVisitor {
     // Buffers for iteration over substatements and subexpressions
     stmt_buffer: Vec<StatementId>,
     expr_buffer: Vec<ExpressionId>,
     // If instantiating a monomorph of a polymorphic proctype, then we store the
     // values of the polymorphic values here.
     polyvars: Vec<(Identifier, ConcreteTypeVariant)>,
     // values of the polymorphic values here. There should be as many, and in
     // the same order as, in the definition's polyargs.
     polyvars: Vec<ConcreteType>,
     // Mapping from parser type to inferred type. We attempt to continue to
     // specify these types until we're stuck or we've fully determined the type.
     infer_types: HashMap<ParserTypeId, InferenceType>,
     // Mapping from variable ID to parser type, optionally inferred, so then
     var_types: HashMap<VariableId, ParserTypeId>,
+}
 impl TypeResolvingVisitor {
     pub(crate) fn new() -> Self {
         TypeResolvingVisitor{
             stmt_buffer: Vec::with_capacity(STMT_BUFFER_INIT_CAPACITY),
             expr_buffer: Vec::with_capacity(EXPR_BUFFER_INIT_CAPACITY),
             polyvars: Vec::new(),
             infer_types: HashMap::new(),
             var_types: HashMap::new(),
+        }
+    }
     fn reset(&mut self) {
         self.stmt_buffer.clear();
         self.expr_buffer.clear();
         self.infer_types.clear();
         self.var_types.clear();
+    }
+}
@@ @@ -171,120 +175,64 @@ impl Visitor2 for TypeResolvingVisitor { @@
         let local = &ctx.heap[memory_stmt.variable];
         self.var_types.insert(memory_stmt.variable, )
         Ok(())
+    }
     fn visit_local_channel_stmt(&mut self, ctx: &mut Ctx, id: ChannelStatementId) -> VisitorResult {
         Ok(())
+    }
+}
 impl TypeResolvingVisitor {
     /// Checks if the `ParserType` contains any inferred variables. If so then
     /// they will be inserted into the `infer_types` variable. Here we assume
     /// we're parsing the body of a proctype, so any reference to polymorphic
     /// variables must refer to the polymorphic arguments of the proctype's
     /// definition.
     /// TODO: @cleanup: The symbol_table -> type_table pattern appears quite
     ///     a lot, will likely need to create some kind of function for this
     // We have a function that traverses the types of variable expressions. If
     // we do not know the type yet we insert it in the "infer types" list.
     // If we do know the type then we can return it and assign it in the
     // variable expression.
     // Hence although the parser types are recursive structures with nested
     // ParserType IDs, here we need to traverse the type all at once.
     fn insert_parser_type_if_needs_inference(
         &mut self, ctx: &mut Ctx, root_id: RootId, parser_type_id: ParserTypeId
     ) -> Result<(), ParseError2> {
         use ParserTypeVariant as PTV;
         let mut to_consider = vec![parser_type_id];
         while !to_consider.is_empty() {
             let parser_type_id = to_consider.pop().unwrap();
-            let parser_type = &mut ctx.heap[parser_type_id];
             let parser_type = &ctx.heap[parser_type_id];
-            match &mut parser_type.variant {
             match &parser_type.variant {
                 PTV::Inferred => {
                     self.env.insert(parser_type_id, InferenceType::new(parser_type_id));
                 },
                 PTV::Array(subtype_id) => { to_consider.push(*subtype_id); },
                 PTV::Input(subtype_id) => { to_consider.push(*subtype_id); },
                 PTV::Output(subtype_id) => { to_consider.push(*subtype_id); },
                 PTV::Symbolic(symbolic) => {
                     // If not yet resolved, try to resolve
                     if symbolic.variant.is_none() {
                         let mut found = false;
                         for (poly_idx, (poly_var, _)) in self.polyvars.iter().enumerate() {
                             if symbolic.identifier.value == poly_var.value {
                                 // Found a match
                                 symbolic.variant = Some(SymbolicParserTypeVariant::PolyArg(poly_idx))
                                 found = true;
                                 break;
+                            }
+                        }
                         if !found {
                             // Attempt to find in symbol/type table
                             let symbol = ctx.symbols.resolve_namespaced_symbol(root_id, &symbolic.identifier);
                             if symbol.is_none() {
                                 let module_source = &ctx.module.source;
                                 return Err(ParseError2::new_error(
                                     module_source, symbolic.identifier.position,
                                     "Could not resolve symbol to a type"
                                 ));
+                            }
                             // Check if symbol was fully resolved
                             let (symbol, ident_iter) = symbol.unwrap();
                             if ident_iter.num_remaining() != 0 {
                                 let module_source = &ctx.module.source;
                                 ident_iter.
                                 return Err(ParseError2::new_error(
                                     module_source, symbolic.identifier.position,
                                     "Could not resolve symbol to a type"
                                 ).with_postfixed_info(
                                     module_source, symbol.position,
                                     "Could resolve part of the identifier to this symbol"
                                 ));
+                            }
                             // Check if symbol resolves to struct/enum
                             let definition_id = match symbol.symbol {
                                 Symbol::Namespace(_) => {
                                     let module_source = &ctx.module.source;
                                     return Err(ParseError2::new_error(
                                         module_source, symbolic.identifier.position,
                                         "Symbol resolved to a module instead of a type"
                                     ));
                                 },
                                 Symbol::Definition((_, definition_id)) => definition_id
                             };
                             // Retrieve from type table and make sure it is a
                             // reference to a struct/enum/union
                             // TODO: @types Allow function pointers
                             let def_type = ctx.types.get_base_definition(&definition_id);
                             debug_assert!(def_type.is_some(), "Expected to resolve definition ID to type definition in type table");
                             let def_type = def_type.unwrap();
                             let def_type_class = def_type.definition.type_class();
                             if !def_type_class.is_data_type() {
                                 return Err(ParseError2::new_error(
                                     &ctx.module.source, symbolic.identifier.position,
                                     &format!("Symbol refers to a {}, only data types are supported", def_type_class)
                                 ));
+                            }
                             // Now that we're certain it is a datatype, make
                             // sure that the number of polyargs in the symbolic
                             // type matches that of the definition, or conclude
                             // that all polyargs need to be inferred.
                             if symbolic.poly_args.len() != def_type.poly_args.len() {
                                 if symbolic.poly_args.is_empty() {
                                     // Modify ParserType to have auto-inferred
                                     // polymorphic arguments
                                     symbolic.poly_args.
+                                }
+                            }
                     // variant is resolved in type table if a type definition,
                     // or in the linker phase if in a function body.
                     debug_assert!(symbolic.variant.is_some());
                     match symbolic.variant.unwrap() {
                         SymbolicParserTypeVariant::PolyArg(_, arg_idx) => {
                             // Points to polyarg, which is resolved by definition
                             debug_assert!(arg_idx < self.polyvars.len());
                             debug_assert!(symbolic.poly_args.is_empty()); // TODO: @hkt
                             let mut inferred = InferenceType::new(parser_type_id);
                             inferred.assign_concrete(&self.polyvars[arg_idx]);
                             self.infer_types.insert(parser_type_id, inferred);
                         },
                         SymbolicParserTypeVariant::Definition(definition_id) => {
                             // Points to a type definition, but if it has poly-
                             // morphic arguments then these need to be inferred.
+                        }
+                    }
                 },
                 _ => {} // Builtin, doesn't require inference
+            }
+        }
         Ok(())
+    }
+}
@@ \ No newline at end of file @@

src/protocol/parser/visitor_linker.rs

➞

Show inline comments

@@ @@ -859,25 +859,25 @@ 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];
             let (symbolic_variant, num_inferred_to_allocate) = match &parser_type.variant {
+            let (symbolic_pos, 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);
@@ @@ -900,25 +900,26 @@ impl Visitor2 for ValidityAndLinkerVisitor { @@
                             // 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)
                         // Identifier points to a symbolic type
                         (symbolic.identifier.position, 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,
@@ @@ -927,57 +928,76 @@ impl Visitor2 for ValidityAndLinkerVisitor { @@
                                     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
+                            (
                                 symbolic.identifier.position,
                                 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)
+                            (
                                 symbolic.identifier.position,
                                 SymbolicParserTypeVariant::Definition(found_type.ast_definition),
+                            )
+                        }
+                    }
+                }
             };
             // 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 {
                 // TODO: @hack, not very user friendly to manually allocate
                 //  `inferred` ParserTypes with the InputPosition of the
                 //  symbolic type's identifier.
                 // We reuse the `parser_type_buffer` to temporarily store these
                 // and we'll take them out later
                 self.parser_type_buffer.push(ctx.heap.alloc_parser_type(|this| ParserType{
                     this,
                     position:
                 }))
                     pos: symbolic_pos,
                     variant: ParserTypeVariant::Inferred,
                 }));
+            }
             if let PTV::Symbolic(symbolic) = &mut ctx.heap[id].variant {
                 for _ in 0..num_inferred_to_allocate {
                     symbolic.poly_args.push(self.parser_type_buffer.pop().unwrap());
+                }
                 symbolic.variant = Some(symbolic_variant);
             } else {
                 unreachable!();
+            }
             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

src/runtime/tests.rs

➞

Show inline comments

@@ @@ -1388,26 +1388,33 @@ fn eq_no_causality() { @@
                     put(leftfirsto, ma);
                     get(leftfirsti);
                 } else {
                     // right first! DON'T USE DUMMY
                     mb = get(b);
                     put(c, mb);
                     ma = get(a);
+                }
                 assert(ma == mb);
+            }
+        }
+    }
     T some_function<T>(msg a, msg b) {
         T something = a;
         return something;
+    }
     primitive quick_test(in<msg> a, in<msg> b) {
         msg ma = null;
         // msg ma = null;
         msg test1 = null;
         msg test2 = null;
         msg ma = some_function(test1, test2);
         while(true) synchronous {
             if (fires(a)) {
                 ma = get(a);
+            }
             if (fires(b)) {
                 ma = get(b);
+            }
             if (fires(a) && fires(b)) {
                 ma = get(a) + get(b);
+            }
+        }
+    }

0 comments (0 inline, 0 general)