Repository: fika-lang/fika
Pull request #76 (2021-01-08 22:06:04)

Function call type inference should respect subtyping


Patch:
diff --git a/lib/fika/compiler/code_server.ex b/lib/fika/compiler/code_server.ex
index 7a0cae6..57fed47 100644
--- a/lib/fika/compiler/code_server.ex
+++ b/lib/fika/compiler/code_server.ex
@@ -6,7 +6,8 @@ defmodule Fika.Compiler.CodeServer do
   alias Fika.Compiler.{
     DefaultTypes,
     ModuleCompiler,
-    ErlTranslate
+    ErlTranslate,
+    TypeChecker
   }
 
   def start_link(_) do
@@ -108,15 +109,19 @@ defmodule Fika.Compiler.CodeServer do
 
   def handle_call({:get_type, signature}, from, state) do
     module = signature.module
+    function = signature.function
+    signature_map = get_in(state, [:public_functions, module, function])
 
     state =
-      if result = get_in(state, [:public_functions, module, signature]) do
-        GenServer.reply(from, result)
-        state
-      else
-        state
-        |> maybe_compile(module)
-        |> wait_for(module, signature, from)
+      case TypeChecker.find_by_call(signature_map, signature) do
+        {_, result} ->
+          GenServer.reply(from, result)
+          state
+
+        _ ->
+          state
+          |> async_compile(module)
+          |> wait_for(module, signature, from)
       end
 
     {:noreply, state}
@@ -168,89 +173,72 @@ defmodule Fika.Compiler.CodeServer do
   end
 
   defp set_type(state, signature, result) do
-    update_in(state, [:public_functions, signature.module], fn
-      nil -> %{signature => result}
-      signatures -> Map.put(signatures, signature, result)
-    end)
+    nested_put(
+      state,
+      [:public_functions, signature.module, signature.function, signature],
+      result
+    )
   end
 
   defp notify_waiting_type_checks(state, module, signature, result) do
-    {waitlist, waiting} = Map.pop(state.waiting, {module, signature})
-
-    if waitlist do
-      Enum.each(waitlist, fn from ->
-        GenServer.reply(from, result)
+    keys = [
+      Access.key(:waiting, %{}),
+      Access.key(module, %{}),
+      Access.key(signature.function, [])
+    ]
+
+    update_in(state, keys, fn waitlist ->
+      Enum.reject(waitlist, fn {s, from} ->
+        TypeChecker.signature_matches_call?(signature, s) &&
+          GenServer.reply(from, result)
       end)
-    end
-
-    Map.put(state, :waiting, waiting)
+    end)
   end
 
   defp fail_waiting_type_checks(state, module, reason) do
-    {waitlist, rest} =
-      Enum.reduce(state.waiting, {[], []}, fn {{waited_module, _}, waitlist} = k_v,
-                                              {from_acc, rest} ->
-        if waited_module == module do
-          {waitlist ++ from_acc, rest}
-        else
-          {from_acc, [k_v | rest]}
-        end
-      end)
+    {fn_map, state} = pop_in(state, [:waiting, module])
 
-    Enum.each(waitlist, fn from ->
-      GenServer.reply(from, {:error, reason})
+    Enum.each(fn_map || [], fn {_, waitlist} ->
+      Enum.each(waitlist, fn {_, from} ->
+        GenServer.reply(from, {:error, reason})
+      end)
     end)
 
-    Map.put(state, :waiting, Map.new(rest))
+    state
   end
 
-  defp maybe_compile(state, module) do
+  defp async_compile(state, module) do
     state
     |> start_module_compile(module)
-    |> update_in([:public_functions, module], fn
-      nil ->
-        %{}
-
-      other ->
-        other
-    end)
+    |> nested_put([:public_functions, module], %{})
   end
 
   defp wait_for(state, module, signature, from) do
-    update_in(state, [:waiting, {module, signature}], fn
-      nil -> [from]
-      list -> [from | list]
-    end)
+    keys = [
+      Access.key(:waiting, %{}),
+      Access.key(module, %{}),
+      Access.key(signature.function, [])
+    ]
+
+    update_in(state, keys, fn list -> [{signature, from} | list] end)
   end
 
   defp init_state do
     %{
-      public_functions: default_functions(),
+      public_functions: %{},
       waiting: %{},
       compile_result: %{},
       parent_pid: nil,
       binaries: []
     }
+    |> put_default_types(DefaultTypes.kernel())
+    |> put_default_types(DefaultTypes.io())
   end
 
   defp reset_binaries(state) do
     Map.put(state, :binaries, [])
   end
 
-  defp default_functions do
-    %{
-      "fika/kernel" => insert_ok(DefaultTypes.kernel()),
-      "fika/io" => insert_ok(DefaultTypes.io())
-    }
-  end
-
-  defp insert_ok(signature_map) do
-    Enum.map(signature_map, fn {k, v} ->
-      {k, {:ok, v}}
-    end)
-    |> Map.new()
-  end
-
   defp start_module_compile(state, module) do
     Task.start(fn ->
       ModuleCompiler.compile(module)
@@ -279,4 +267,14 @@ defmodule Fika.Compiler.CodeServer do
       GenServer.reply(parent_pid, result)
     end
   end
+
+  defp put_default_types(state, signatures) do
+    Enum.reduce(signatures, state, fn s, acc ->
+      set_type(acc, s, {:ok, s.return})
+    end)
+  end
+
+  defp nested_put(map, keys, value) do
+    put_in(map, Enum.map(keys, &Access.key(&1, %{})), value)
+  end
 end
diff --git a/lib/fika/compiler/default_types.ex b/lib/fika/compiler/default_types.ex
index d5013e0..03d7a36 100644
--- a/lib/fika/compiler/default_types.ex
+++ b/lib/fika/compiler/default_types.ex
@@ -10,48 +10,48 @@ defmodule Fika.Compiler.DefaultTypes do
   def kernel do
     m = "fika/kernel"
 
-    %{
-      s(m, "+", [:Int, :Int]) => :Int,
-      s(m, "+", [:Int, :Float]) => :Float,
-      s(m, "+", [:Float, :Int]) => :Float,
-      s(m, "+", [:Float, :Float]) => :Float,
-      s(m, "-", [:Int, :Int]) => :Int,
-      s(m, "-", [:Int, :Float]) => :Float,
-      s(m, "-", [:Float, :Int]) => :Float,
-      s(m, "-", [:Float, :Float]) => :Float,
-      s(m, "*", [:Int, :Int]) => :Int,
-      s(m, "*", [:Int, :Float]) => :Float,
-      s(m, "*", [:Float, :Int]) => :Float,
-      s(m, "*", [:Float, :Float]) => :Float,
-      s(m, "/", [:Int, :Int]) => :Float,
-      s(m, "/", [:Int, :Float]) => :Float,
-      s(m, "/", [:Float, :Int]) => :Float,
-      s(m, "/", [:Float, :Float]) => :Float,
-      s(m, "|", [:Bool, :Bool]) => :Bool,
-      s(m, "&", [:Bool, :Bool]) => :Bool,
-      s(m, "!", [:Bool]) => :Bool,
-      s(m, "-", [:Int]) => :Int,
-      s(m, "<", [:Int, :Int]) => :Bool,
-      s(m, ">", [:Int, :Int]) => :Bool,
-      s(m, "<=", [:Int, :Int]) => :Bool,
-      s(m, ">=", [:Int, :Int]) => :Bool,
-      s(m, "==", [:Int, :Int]) => :Bool,
-      s(m, "!=", [:Int, :Int]) => :Bool
-    }
+    [
+      s(m, "+", [:Int, :Int], :Int),
+      s(m, "+", [:Int, :Float], :Float),
+      s(m, "+", [:Float, :Int], :Float),
+      s(m, "+", [:Float, :Float], :Float),
+      s(m, "-", [:Int, :Int], :Int),
+      s(m, "-", [:Int, :Float], :Float),
+      s(m, "-", [:Float, :Int], :Float),
+      s(m, "-", [:Float, :Float], :Float),
+      s(m, "*", [:Int, :Int], :Int),
+      s(m, "*", [:Int, :Float], :Float),
+      s(m, "*", [:Float, :Int], :Float),
+      s(m, "*", [:Float, :Float], :Float),
+      s(m, "/", [:Int, :Int], :Float),
+      s(m, "/", [:Int, :Float], :Float),
+      s(m, "/", [:Float, :Int], :Float),
+      s(m, "/", [:Float, :Float], :Float),
+      s(m, "|", [:Bool, :Bool], :Bool),
+      s(m, "&", [:Bool, :Bool], :Bool),
+      s(m, "!", [:Bool], :Bool),
+      s(m, "-", [:Int], :Int),
+      s(m, "<", [:Int, :Int], :Bool),
+      s(m, ">", [:Int, :Int], :Bool),
+      s(m, "<=", [:Int, :Int], :Bool),
+      s(m, ">=", [:Int, :Int], :Bool),
+      s(m, "==", [:Int, :Int], :Bool),
+      s(m, "!=", [:Int, :Int], :Bool)
+    ]
   end
 
   def io do
     m = "fika/io"
 
-    %{
-      s(m, "gets", [:String]) => %T.Effect{type: :String},
-      s(m, "puts", [:String]) => %T.Effect{type: :String}
-    }
+    [
+      s(m, "gets", [:String], %T.Effect{type: :String}),
+      s(m, "puts", [:String], %T.Effect{type: :String})
+    ]
   end
 
-  # Helper function to create signature structs out of module, function and
-  # arg types.
-  defp s(m, f, t) do
-    %FunctionSignature{module: m, function: f, types: t}
+  # Helper function to create signature structs out of module, function,
+  # arg types and return type.
+  defp s(m, f, t, r) do
+    %FunctionSignature{module: m, function: f, types: t, return: r}
   end
 end
diff --git a/lib/fika/compiler/function_signature.ex b/lib/fika/compiler/function_signature.ex
index c14d40c..78752e7 100644
--- a/lib/fika/compiler/function_signature.ex
+++ b/lib/fika/compiler/function_signature.ex
@@ -1,12 +1,26 @@
 defmodule Fika.Compiler.FunctionSignature do
-  defstruct [:module, :function, types: []]
+  defstruct [:module, :function, :return, types: []]
 
   alias Fika.Compiler.TypeChecker.Types, as: T
 
   defimpl String.Chars, for: __MODULE__ do
-    def to_string(%{module: m, function: f, types: ts}) do
+    def to_string(%{module: m, function: f, types: ts, return: r}) do
       types_str = T.Helper.join_list(ts)
-      "#{m}.#{f}(#{types_str})"
+
+      str =
+        if m do
+          "#{m}."
+        else
+          ""
+        end
+
+      str = "#{str}#{f}(#{types_str})"
+
+      if r do
+        "#{str} -> #{r}"
+      else
+        str
+      end
     end
   end
 end
diff --git a/lib/fika/compiler/parser/pattern.ex b/lib/fika/compiler/parser/pattern.ex
index b3096bd..fd8259f 100644
--- a/lib/fika/compiler/parser/pattern.ex
+++ b/lib/fika/compiler/parser/pattern.ex
@@ -1,10 +1,6 @@
 defmodule Fika.Compiler.Parser.Pattern do
   import NimbleParsec
 
-  # TODO: We need to add other patterns like records and matches.
-  # See https://erlang.org/doc/apps/erts/absform.html#patterns
-  # Also, we can organize the parser modules better.
-
   alias Fika.Compiler.Parser.{Common, Helper}
 
   allow_space = parsec({Common, :allow_space})
diff --git a/lib/fika/compiler/type_checker.ex b/lib/fika/compiler/type_checker.ex
index 595a399..8d0afdd 100644
--- a/lib/fika/compiler/type_checker.ex
+++ b/lib/fika/compiler/type_checker.ex
@@ -318,6 +318,56 @@ defmodule Fika.Compiler.TypeChecker do
     %{ast: ast, scope: %{}}
   end
 
+  # Given a map of signatures to values and a signature,
+  # finds the value for the signature which is a supertype of the second arg.
+  def find_by_call(map, signature) when is_map(map) do
+    Enum.find(map, fn {s, _} ->
+      signature_matches_call?(s, signature)
+    end)
+  end
+
+  def find_by_call(_, _), do: nil
+
+  def signature_matches_call?(s1, s2) do
+    if s1.module == s2.module && s1.function == s2.function &&
+         length(s1.types) == length(s2.types) do
+      all_subtype?(s2.types, s1.types)
+    end
+  end
+
+  defp all_subtype?([], []) do
+    true
+  end
+
+  defp all_subtype?([t1 | t1s], [t2 | t2s]) do
+    if subtype?(t1, t2) do
+      all_subtype?(t1s, t2s)
+    else
+      false
+    end
+  end
+
+  # Returns true if t1 is a subtype of t2 (t1 <: t2)
+  # Cheese <: Food
+  # Food -> Int <: Cheese -> Int
+  # Int -> Cheese <: Int -> Food
+  def subtype?(t1, t2) do
+    do_subtype?(t1, t2)
+  end
+
+  defp do_subtype?(t1, t2) when t1 == t2 do
+    true
+  end
+
+  defp do_subtype?(t1, %T.Union{types: ts}) do
+    Enum.any?(ts, &do_subtype?(t1, &1))
+  end
+
+  # TODO: also check subtypes of remaining types
+  defp do_subtype?(_, _) do
+    false
+  end
+
   # TODO: made it work, now make it pretty.
   defp infer_case_clauses(env, rhs, clauses) do
     all_rhs_types = Match.expand_unions(rhs)
diff --git a/lib/fika/compiler/type_checker/parallel_type_checker.ex b/lib/fika/compiler/type_checker/parallel_type_checker.ex
index a154ddf..2de07dd 100644
--- a/lib/fika/compiler/type_checker/parallel_type_checker.ex
+++ b/lib/fika/compiler/type_checker/parallel_type_checker.ex
@@ -68,12 +68,12 @@ defmodule Fika.Compiler.TypeChecker.ParallelTypeChecker do
   end
 
   def handle_call({:get_result, signature}, from, state) do
-    if Map.has_key?(state.local_functions, signature) do
-      if result = Map.get(state.checked_functions, signature) do
+    if {s, _} = TypeChecker.find_by_call(state.local_functions, signature) do
+      if {_, result} = TypeChecker.find_by_call(state.checked_functions, signature) do
         {:reply, result, state}
       else
         state =
-          update_in(state, [:waiting, signature], fn
+          update_in(state, [:waiting, s], fn
             nil -> [from]
             list -> [from | list]
           end)
diff --git a/lib/fika/compiler/type_checker/sequential_type_checker.ex b/lib/fika/compiler/type_checker/sequential_type_checker.ex
index 645c0fb..9b55d04 100644
--- a/lib/fika/compiler/type_checker/sequential_type_checker.ex
+++ b/lib/fika/compiler/type_checker/sequential_type_checker.ex
@@ -11,7 +11,9 @@ defmodule Fika.Compiler.TypeChecker.SequentialTypeChecker do
 
   defp find_by_signature(function_defs, signature) do
     Enum.find(function_defs, fn function ->
-      TypeChecker.function_ast_signature(signature.module, function) == signature
+      signature.module
+      |> TypeChecker.function_ast_signature(function)
+      |> TypeChecker.signature_matches_call?(signature)
     end)
   end
 end


Test patch:
diff --git a/test/fika/compiler/code_server_test.exs b/test/fika/compiler/code_server_test.exs
index 068a450..0bb7e23 100644
--- a/test/fika/compiler/code_server_test.exs
+++ b/test/fika/compiler/code_server_test.exs
@@ -3,6 +3,10 @@ defmodule Fika.Compiler.CodeServerTest do
 
   alias Fika.Compiler.CodeServer
 
+  setup do
+    CodeServer.reset()
+  end
+
   test "when module has a dependency" do
     tmp_dir = System.tmp_dir!()
     temp_file_1 = Path.join(tmp_dir, "foo.fi")
@@ -11,7 +15,7 @@ defmodule Fika.Compiler.CodeServerTest do
     use bar
 
     fn foo : String do
-      bar.hello()
+      bar.hello(:a)
     end
     """
 
@@ -20,8 +24,11 @@ defmodule Fika.Compiler.CodeServerTest do
     temp_file_2 = Path.join(tmp_dir, "bar.fi")
 
     str = """
-    fn hello : String do
-      "Hello world"
+    fn hello(x: :a | :b) : String do
+      case x do
+        :a -> "A"
+        :b -> "B"
+      end
     end
     """
 
diff --git a/test/fika/compiler/type_checker_test.exs b/test/fika/compiler/type_checker_test.exs
index 9d55423..23b7f89 100644
--- a/test/fika/compiler/type_checker_test.exs
+++ b/test/fika/compiler/type_checker_test.exs
@@ -10,6 +10,10 @@ defmodule Fika.Compiler.TypeCheckerTest do
 
   alias Fika.Compiler.TypeChecker.Types, as: T
 
+  setup do
+    CodeServer.reset()
+  end
+
   test "infer type of integer literals" do
     str = "123"
 
@@ -196,6 +200,25 @@ defmodule Fika.Compiler.TypeCheckerTest do
     assert {:ok, :Float} = TypeChecker.check(function, %{})
   end
 
+  test "infer function calls considering union types" do
+    str = """
+    use test2
+
+    fn foo : :ok do
+      test2.div(:a)
+    end
+    """
+
+    {:ok, ast} = Parser.parse_module(str)
+
+    arg_type = T.Union.new([:a, :b])
+    CodeServer.set_type(signature("test2", "div", [arg_type]), {:ok, :ok})
+
+    [function] = ast[:function_defs]
+
+    assert {:ok, :ok} = TypeChecker.infer(function, %{})
+  end
+
   describe "string" do
     test "string" do
       str = "\"Hello world\""
@@ -626,7 +649,6 @@ defmodule Fika.Compiler.TypeCheckerTest do
       """
 
       {:ok, ast} = Parser.parse_module(str)
-      CodeServer.reset()
       CodeServer.set_type(signature("test2", "bar", [:String, :Int]), {:ok, :Bool})
       types = MapSet.new([:ok, :error])
       [function] = ast[:function_defs]
@@ -649,7 +671,6 @@ defmodule Fika.Compiler.TypeCheckerTest do
       env = TypeChecker.init_env(ast)
 
       types = MapSet.new([:error, :ok])
-      CodeServer.reset()
 
       CodeServer.set_type(
         signature("test2", "bar", [:String, :Int]),
@@ -688,7 +709,6 @@ defmodule Fika.Compiler.TypeCheckerTest do
 
       {:ok, ast} = Parser.parse_module(str)
       [function] = ast[:function_defs]
-      CodeServer.reset()
       CodeServer.set_type(signature("test2", "bar", [:String, :Int]), {:ok, :Bool})
 
       error =
@@ -734,7 +754,6 @@ defmodule Fika.Compiler.TypeCheckerTest do
       """
 
       {:ok, ast} = Parser.parse_module(str)
-      CodeServer.reset()
       CodeServer.set_type(signature("test", "to_int", [:String]), {:ok, %T.Effect{type: :Int}})
 
       [function] = ast[:function_defs]
@@ -757,7 +776,6 @@ defmodule Fika.Compiler.TypeCheckerTest do
       [function] = ast[:function_defs]
       env = TypeChecker.init_env(ast)
 
-      CodeServer.reset()
       CodeServer.set_type(signature("test2", "bar", []), {:ok, %T.Effect{type: :String}})
 
       assert {:ok, %T.Effect{type: :String}} = TypeChecker.infer(function, env)
@@ -783,6 +801,22 @@ defmodule Fika.Compiler.TypeCheckerTest do
     end
   end
 
+  test "find_by_call" do
+    s1 = signature("foo", "bar", [T.Union.new([:a, :b]), :Int])
+    s2 = signature("foo", "baz", [T.Union.new([:c, :d])])
+
+    map = %{
+      s1 => "value1",
+      s2 => "value2"
+    }
+
+    assert TypeChecker.find_by_call(map, signature("foo", "bar", [:d])) == nil
+    assert TypeChecker.find_by_call(map, signature("foo", "bar", [:a, :Int])) == {s1, "value1"}
+    assert TypeChecker.find_by_call(map, signature("foo", "bar", [:b, :Int])) == {s1, "value1"}
+    assert TypeChecker.find_by_call(map, signature("foo", "baz", [:c])) == {s2, "value2"}
+    assert TypeChecker.find_by_call(map, signature("foo", "baz", [:d])) == {s2, "value2"}
+  end
+
   defp signature(m, f, t) do
     %FunctionSignature{module: m, function: f, types: t}
   end