Stabilize HashMap.an

jfecher · Jun 30, 2022 · 758935d · 758935d
1 parent ea67b72
commit 758935d
Show file tree

Hide file tree

Showing 5 changed files with 68 additions and 48 deletions.
diff --git a/README.md b/README.md
@@ -26,37 +26,8 @@ In general, ante is low-level (no GC, values aren't boxed by default) while also
 be as readable as possible by encouraging high-level approaches that can be optimized with
 low-level details later on.
 
-See the [website](https://antelang.org) and [language tour](https://antelang.org/docs/language/) for more information.
-
----
-
-### Roadmap
-
-- [x] Whitespace-sensitive lexer
-- [x] Parser
-- [x] Name Resolution
-- [x] Full type inference
-    - [x] Traits with multiple parameters and limited functional dependencies
-    - [ ] Compiler option to write inferred types into program source after successful compilation
-- [x] LLVM Codegen
-- [x] No Garbage Collector
-    - [ ] Region Inference for `ref`s
-    - [ ] RAII to allow `Rc t` or `Box t` when necessary
-- [x] Language [Documentation](https://antelang.org/docs/language/):
-    - [x] [Article on Ante's use of whitespace for line continuations](https://antelang.org/docs/language/#line-continuations)
-    - [x] [Article on the sugar for immediately invoked recursive functions (loop/recur)](https://antelang.org/docs/language/#loops)
-    - [ ] Article on interactions between `mut`, `ref`, and passing by reference
-    - [ ] Article on autoboxing recursive types for polymorphic pointer types
-- [~] Refinement Types (in progress)
-- [x] Cranelift backend for faster debug builds
-- [ ] Algebraic Effects
-- [ ] Incremental compilation metadata
-- [ ] REPL
-
-Nice to have but not currently required:
-- [ ] Reasonable automatic C/C++ interop with clang api
-- [ ] Build system built into standard library
-    - Ante should always be able to build itself along with any required libraries, the main question is how should a build system facilitate the more complex tasks of building other languages or running arbitrary programs like yacc/bison.
+See the [website](https://antelang.org), [language tour](https://antelang.org/docs/language/),
+and [roadmap](https://antelang.org/docs/roadmap) for more information.
 
 ---
 

diff --git a/examples/codegen/map.an b/examples/codegen/map.an
@@ -0,0 +1,23 @@
+import HashMap
+
+impl Hash u8 with
+    hash x = cast x
+
+map = mut empty ()
+
+// Test several inserts. HashMap is linear-scan so it 
+// should keep resizing so that it is at least half-empty 
+// (ie. its capacity should be >= 2 * its length).
+insert map 1u8 3u16
+insert map 2 6
+insert map 3 9
+insert map 4 12
+insert map 5 15
+insert map 6 18
+insert map 7 21
+
+print map
+
+// args: --delete-binary
+// expected stdout:
+// [1 -> 3, 2 -> 6, 3 -> 9, 4 -> 12, 5 -> 15, 6 -> 18, 7 -> 21]
diff --git a/src/types/traits.rs b/src/types/traits.rs
@@ -124,9 +124,24 @@ impl RequiredTrait {
         TraitConstraint { required, scope }
     }
 
+    pub fn find_all_typevars<'b>(&self, cache: &ModuleCache<'b>) -> Vec<TypeVariableId> {
+        self.signature.find_all_typevars(cache)
+    }
+
+    pub fn display<'a, 'b>(&self, cache: &'a ModuleCache<'b>) -> ConstraintSignaturePrinter<'a, 'b> {
+        self.signature.display(cache)
+    }
+
+    #[allow(dead_code)]
+    pub fn debug<'a, 'b>(&self, cache: &'a ModuleCache<'b>) -> ConstraintSignaturePrinter<'a, 'b> {
+        self.signature.debug(cache)
+    }
+}
+
+impl ConstraintSignature {
     pub fn find_all_typevars<'b>(&self, cache: &ModuleCache<'b>) -> Vec<TypeVariableId> {
         let mut typevars = vec![];
-        for typ in &self.signature.args {
+        for typ in &self.args {
             typevars.append(&mut find_all_typevars(typ, false, cache));
         }
         typevars
@@ -145,14 +160,14 @@ impl RequiredTrait {
             }
         }
 
-        ConstraintSignaturePrinter { signature: self.signature.clone(), typevar_names, debug: false, cache }
+        ConstraintSignaturePrinter { signature: self.clone(), typevar_names, debug: false, cache }
     }
 
     #[allow(dead_code)]
     pub fn debug<'a, 'b>(&self, cache: &'a ModuleCache<'b>) -> ConstraintSignaturePrinter<'a, 'b> {
         let mut typevar_names = HashMap::new();
 
-        for typ in &self.signature.args {
+        for typ in &self.args {
             let typevars = find_all_typevars(typ, false, cache);
 
             for typevar in typevars {
@@ -162,7 +177,7 @@ impl RequiredTrait {
             }
         }
 
-        ConstraintSignaturePrinter { signature: self.signature.clone(), typevar_names, debug: true, cache }
+        ConstraintSignaturePrinter { signature: self.clone(), typevar_names, debug: true, cache }
     }
 }
 

diff --git a/src/types/typechecker.rs b/src/types/typechecker.rs
@@ -1329,10 +1329,9 @@ fn check_impl_propagated_traits(
                     Some(used)
                 } else {
                     let constraint = TraitConstraint { required: used, scope: variable.impl_scope.unwrap() };
-                    traitchecker::force_resolve_trait(constraint, cache);
+                    // Any traits used that are not in the 'given' clause must be resolved
                     // TODO: Should issue this error earlier to give a better callsite for the error
-                    // error!(variable.location, "This definition requires {}, but the trait isn't given in the impl or the type signature for {} in the trait that defines it.",
-                    //        used.display(cache), variable);
+                    traitchecker::force_resolve_trait(constraint, cache);
                     None
                 }
             })
@@ -1356,8 +1355,10 @@ fn find_matching_trait(
                 cache,
                 "error never shown",
             ) {
-                bindings.perform(cache);
-                return Some(useable.signature.id);
+                if bindings.bindings.is_empty() {
+                    // bindings.perform(cache);
+                    return Some(useable.signature.id);
+                }
             }
         }
     }
@@ -1372,8 +1373,10 @@ fn find_matching_trait(
                 cache,
                 "error never shown",
             ) {
-                bindings.perform(cache);
-                return Some(useable.id);
+                if bindings.bindings.is_empty() {
+                    // bindings.perform(cache);
+                    return Some(useable.id);
+                }
             }
         }
     }
@@ -1824,7 +1827,13 @@ impl<'a> Inferable<'a> for ast::TraitImpl<'a> {
 
         // Need to replace all typevars here so we do not rebind over them.
         // E.g. an impl for `Cmp a given Int a` could be accidentally bound to `Cmp usz`
-        let (trait_arg_types, _) = replace_all_typevars(&self.trait_arg_types, cache);
+        // TODO: Is the above comment correct? replace_all_typevars causes `impl Print (HashMap a b)`
+        //       in the stdlib to fail (the given list would need to use the same type bindings) 
+        //       and removing it still lets all tests pass, despite builtin_int.an
+        //       testing several traits like `Add a given Int a` for several integer types.
+        // let (trait_arg_types, _) = replace_all_typevars(&self.trait_arg_types, cache);
+
+        let trait_arg_types = self.trait_arg_types.clone();
 
         // Instantiate the typevars in the parent trait to bind their definition
         // types against the types in this trait impl. This needs to be done once

diff --git a/stdlib/future/HashMap.an → stdlib/HashMap.an b/stdlib/future/HashMap.an → stdlib/HashMap.an
@@ -46,7 +46,7 @@ should_resize (map: HashMap k v) : bool =
 
 insert (map: ref (HashMap k v)) (key: k) (value: v) : unit =
     if should_resize @map then
-        resize map (map.capacity * 2 + 1)
+        resize map ((map.capacity + 1) * 2)
 
     iter_until (map: ref (HashMap k v)) (key: k) (value: v) (start: usz) (end: usz) : bool =
         if start >= end then
@@ -116,10 +116,12 @@ remove (map: ref (HashMap k v)) (key: k) : Maybe v =
         Some entry.value
 
 impl Print (HashMap k v) given Print k, Print v with
-    printne map =
-        putchar '['
-        print_helper map false 0
-        putchar ']'
+    printne map = printne_map map
+
+printne_map (map: HashMap k v) =
+    putchar '['
+    print_helper map false 0
+    putchar ']'
 
 print_helper (map: HashMap k v) (did_first: bool) (i: usz) =
     if i < map.capacity then