Add unit testsemj/types-split

4 files changed, 307 insertions, 41 deletions

diff --git a/lib/elixir/lib/module/types.ex b/lib/elixir/lib/module/types.ex
index c9af04f07..11b7472b7 100644
--- a/lib/elixir/lib/module/types.ex
+++ b/lib/elixir/lib/module/types.ex
@@ -86,6 +86,26 @@ defmodule Module.Types do
     type
   end
 
+  ## GUARDS
+
+  # TODO: Remove this and let multiple when be treated as multiple clauses,
+  #       meaning they will be intersection types
+  defp guards_to_or([]) do
+    []
+  end
+
+  defp guards_to_or(guards) do
+    Enum.reduce(guards, fn guard, acc -> {{:., [], [:erlang, :orelse]}, [], [guard, acc]} end)
+  end
+
+  defp guards_to_expr([], left) do
+    left
+  end
+
+  defp guards_to_expr([guard | guards], left) do
+    guards_to_expr(guards, {:when, [], [left, guard]})
+  end
+
   ## VARIABLE QUANTIFICATION
 
   # Lift type variable to its infered types from the context
@@ -148,24 +168,6 @@ defmodule Module.Types do
     {type, context}
   end
 
-  # TODO: Remove this and let multiple when be treated as multiple clauses,
-  #       meaning they will be intersection types
-  defp guards_to_or([]) do
-    []
-  end
-
-  defp guards_to_or(guards) do
-    Enum.reduce(guards, fn guard, acc -> {{:., [], [:erlang, :orelse]}, [], [guard, acc]} end)
-  end
-
-  defp guards_to_expr([], left) do
-    left
-  end
-
-  defp guards_to_expr([guard | guards], left) do
-    guards_to_expr(guards, {:when, [], [left, guard]})
-  end
-
   ## ERROR FORMATTING
 
   def format_warning({:unable_unify, left, right, expr, traces}) do
@@ -246,6 +248,16 @@ defmodule Module.Types do
     "[#{format_type(left)} | #{format_type(right)}]"
   end
 
+  def format_type({:map, pairs}) do
+    case List.keytake(pairs, :__struct__, 0) do
+      {{:__struct__, struct}, pairs} ->
+        "%#{inspect(struct)}{#{format_map_pairs(pairs)}}"
+
+      nil ->
+        "%{#{format_map_pairs(pairs)}}"
+    end
+  end
+
   def format_type({:literal, literal}) do
     inspect(literal)
   end
@@ -262,6 +274,12 @@ defmodule Module.Types do
     "var#{index}"
   end
 
+  defp format_map_pairs(pairs) do
+    Enum.map_join(pairs, ", ", fn {left, right} ->
+      "#{format_type(left)} => #{format_type(right)}"
+    end)
+  end
+
   defp expr_to_string(expr) do
     expr
     |> rewrite_guard()
diff --git a/lib/elixir/lib/module/types/infer.ex b/lib/elixir/lib/module/types/infer.ex
index 544e8f3cd..ade413a35 100644
--- a/lib/elixir/lib/module/types/infer.ex
+++ b/lib/elixir/lib/module/types/infer.ex
@@ -117,6 +117,7 @@ defmodule Module.Types.Infer do
     end
   end
 
+  # TODO: structs
   def of_pattern({:%, _meta, _args}, context) do
     {:ok, {:map, []}, context}
   end
@@ -382,7 +383,7 @@ defmodule Module.Types.Infer do
       _ ->
         case :maps.find(right, context.types) do
           {:ok, {:var, new_right}} -> variable_same?(left, new_right, context)
-          :error -> false
+          _ -> false
         end
     end
   end
@@ -391,7 +392,7 @@ defmodule Module.Types.Infer do
     %{context | unify_stack: [var | context.unify_stack]}
   end
 
-  defp new_var(var, context) do
+  def new_var(var, context) do
     case :maps.find(var_name(var), context.vars) do
       {:ok, type} ->
         {type, context}
@@ -434,7 +435,7 @@ defmodule Module.Types.Infer do
   # Check if a variable is recursive and incompatible with itself
   # Bad: `{var} = var`
   # Good: `x = y; y = z; z = x`
-  def recursive_type?({:var, var} = parent, parents, context) do
+  defp recursive_type?({:var, var} = parent, parents, context) do
     case :maps.get(var, context.types) do
       :unbound ->
         false
@@ -448,23 +449,23 @@ defmodule Module.Types.Infer do
     end
   end
 
-  def recursive_type?({:cons, left, right} = parent, parents, context) do
+  defp recursive_type?({:cons, left, right} = parent, parents, context) do
     recursive_type?(left, [parent | parents], context) or
       recursive_type?(right, [parent | parents], context)
   end
 
-  def recursive_type?({:tuple, types} = parent, parents, context) do
+  defp recursive_type?({:tuple, types} = parent, parents, context) do
     Enum.any?(types, &recursive_type?(&1, [parent | parents], context))
   end
 
-  def recursive_type?({:map, pairs} = parent, parents, context) do
+  defp recursive_type?({:map, pairs} = parent, parents, context) do
     Enum.any?(pairs, fn {key, value} ->
       recursive_type?(key, [parent | parents], context) or
         recursive_type?(value, [parent | parents], context)
     end)
   end
 
-  def recursive_type?(_other, _parents, _context) do
+  defp recursive_type?(_other, _parents, _context) do
     false
   end
 
@@ -486,12 +487,9 @@ defmodule Module.Types.Infer do
 
   def to_union(types, context) when types != [] do
     if :dynamic in types do
+      # NOTE: Or filter away dynamic()?
       :dynamic
     else
-      # Filter subtypes
-      # `boolean() | atom()` => `atom()`
-      # `:foo | atom()` => `atom()`
-      # Does not unify `true | false` => `boolean()`
       case unique_super_types(types, context) do
         [type] -> type
         types -> {:union, types}
@@ -499,6 +497,10 @@ defmodule Module.Types.Infer do
     end
   end
 
+  # Filter subtypes
+  # `boolean() | atom()` => `atom()`
+  # `:foo | atom()` => `atom()`
+  # Does not unify `true | false` => `boolean()`
   defp unique_super_types([type | types], context) do
     types = Enum.reject(types, &subtype?(&1, type, context))
 
@@ -516,7 +518,7 @@ defmodule Module.Types.Infer do
   # Collect relevant information from context and traces to report error
   defp error({:unable_unify, left, right}, context) do
     {fun, arity} = context.function
-    line = get_meta(Enum.at(context.expr_stack, 0))[:line]
+    line = get_meta(hd(context.expr_stack))[:line]
     location = {context.file, line, {context.module, fun, arity}}
 
     traces = type_traces(context)
diff --git a/lib/elixir/test/elixir/module/types/infer_test.exs b/lib/elixir/test/elixir/module/types/infer_test.exs
index 1ee69dd4b..228ea667c 100644
--- a/lib/elixir/test/elixir/module/types/infer_test.exs
+++ b/lib/elixir/test/elixir/module/types/infer_test.exs
@@ -2,18 +2,26 @@ Code.require_file("../../test_helper.exs", __DIR__)
 
 defmodule Module.Types.InferTest do
   use ExUnit.Case, async: true
+  import Module.Types.Infer
   alias Module.Types
-  alias Module.Types.Infer
 
   defmacrop quoted_pattern(expr) do
     quote do
-      Infer.of_pattern(unquote(Macro.escape(expr)), new_context())
+      of_pattern(unquote(Macro.escape(expr)), new_context())
       |> lift_result()
     end
   end
 
+  defp unify_lift(left, right, context \\ new_context()) do
+    unify(left, right, context)
+    |> lift_result()
+  end
+
   defp new_context() do
-    Types.context("types_test.ex", TypesTest, {:test, 0})
+    %{
+      Types.context("types_test.ex", TypesTest, {:test, 0})
+      | expr_stack: [{:foo, [], nil}]
+    }
   end
 
   defp lift_result({:ok, type, context}) do
@@ -29,7 +37,7 @@ defmodule Module.Types.InferTest do
       assert {:error, {{:unable_unify, :binary, :integer, expr, traces}, location}} =
                quoted_pattern(<<foo::integer, foo::binary>>)
 
-      assert location == [{"types_test.ex", 35, {TypesTest, :test, 0}}]
+      assert location == [{"types_test.ex", 38, {TypesTest, :test, 0}}]
 
       assert {:<<>>, _,
               [
@@ -40,14 +48,14 @@ defmodule Module.Types.InferTest do
       assert [
                {{:foo, _, nil},
                 {:type, :binary, {:"::", _, [{:foo, _, nil}, {:binary, _, nil}]},
-                 {"types_test.ex", 35}}},
+                 {"types_test.ex", 38}}},
                {{:foo, _, nil},
                 {:type, :integer, {:"::", _, [{:foo, _, nil}, {:integer, _, nil}]},
-                 {"types_test.ex", 35}}}
+                 {"types_test.ex", 38}}}
              ] = traces
     end
 
-    test "literals" do
+    test "literal" do
       assert quoted_pattern(true) == {:ok, {:literal, true}}
       assert quoted_pattern(false) == {:ok, {:literal, false}}
       assert quoted_pattern(:foo) == {:ok, {:literal, :foo}}
@@ -122,4 +130,240 @@ defmodule Module.Types.InferTest do
                quoted_pattern({x} = x)
     end
   end
+
+  describe "unify/3" do
+    test "literal" do
+      assert unify_lift({:literal, :foo}, {:literal, :foo}) == {:ok, {:literal, :foo}}
+
+      assert {:error, {{:unable_unify, {:literal, :foo}, {:literal, :bar}, _, _}, _}} =
+               unify_lift({:literal, :foo}, {:literal, :bar})
+    end
+
+    test "type" do
+      assert unify_lift(:integer, :integer) == {:ok, :integer}
+      assert unify_lift(:binary, :binary) == {:ok, :binary}
+      assert unify_lift(:atom, :atom) == {:ok, :atom}
+      assert unify_lift(:boolean, :boolean) == {:ok, :boolean}
+
+      assert {:error, {{:unable_unify, :integer, :boolean, _, _}, _}} =
+               unify_lift(:integer, :boolean)
+    end
+
+    test "subtype" do
+      assert unify_lift(:boolean, :atom) == {:ok, :boolean}
+      assert unify_lift(:atom, :boolean) == {:ok, :boolean}
+      assert unify_lift(:boolean, {:literal, true}) == {:ok, {:literal, true}}
+      assert unify_lift({:literal, true}, :boolean) == {:ok, {:literal, true}}
+      assert unify_lift(:atom, {:literal, true}) == {:ok, {:literal, true}}
+      assert unify_lift({:literal, true}, :atom) == {:ok, {:literal, true}}
+    end
+
+    test "tuple" do
+      assert unify_lift({:tuple, []}, {:tuple, []}) == {:ok, {:tuple, []}}
+      assert unify_lift({:tuple, [:integer]}, {:tuple, [:integer]}) == {:ok, {:tuple, [:integer]}}
+      assert unify_lift({:tuple, [:boolean]}, {:tuple, [:atom]}) == {:ok, {:tuple, [:boolean]}}
+
+      assert {:error, {{:unable_unify, {:tuple, [:integer]}, {:tuple, []}, _, _}, _}} =
+               unify_lift({:tuple, [:integer]}, {:tuple, []})
+
+      assert {:error, {{:unable_unify, :integer, :atom, _, _}, _}} =
+               unify_lift({:tuple, [:integer]}, {:tuple, [:atom]})
+    end
+
+    test "cons" do
+      assert unify_lift({:cons, :integer, :integer}, {:cons, :integer, :integer}) ==
+               {:ok, {:cons, :integer, :integer}}
+
+      assert unify_lift({:cons, :boolean, :atom}, {:cons, :atom, :boolean}) ==
+               {:ok, {:cons, :boolean, :boolean}}
+
+      assert {:error, {{:unable_unify, :atom, :integer, _, _}, _}} =
+               unify_lift({:cons, :integer, :atom}, {:cons, :integer, :integer})
+
+      assert {:error, {{:unable_unify, :atom, :integer, _, _}, _}} =
+               unify_lift({:cons, :atom, :integer}, {:cons, :integer, :integer})
+    end
+
+    test "map" do
+      assert unify_lift({:map, []}, {:map, []}) == {:ok, {:map, []}}
+
+      assert unify_lift({:map, [{:integer, :atom}]}, {:map, []}) ==
+               {:ok, {:map, [{:integer, :atom}]}}
+
+      assert unify_lift({:map, []}, {:map, [{:integer, :atom}]}) ==
+               {:ok, {:map, [{:integer, :atom}]}}
+
+      assert unify_lift({:map, [{:integer, :atom}]}, {:map, [{:integer, :atom}]}) ==
+               {:ok, {:map, [{:integer, :atom}]}}
+
+      assert unify_lift({:map, [{:integer, :atom}]}, {:map, [{:atom, :integer}]}) ==
+               {:ok, {:map, [{:integer, :atom}, {:atom, :integer}]}}
+
+      assert unify_lift(
+               {:map, [{{:literal, :foo}, :boolean}]},
+               {:map, [{{:literal, :foo}, :atom}]}
+             ) ==
+               {:ok, {:map, [{{:literal, :foo}, :boolean}]}}
+
+      assert {:error, {{:unable_unify, :integer, :atom, _, _}, _}} =
+               unify_lift(
+                 {:map, [{{:literal, :foo}, :integer}]},
+                 {:map, [{{:literal, :foo}, :atom}]}
+               )
+    end
+
+    test "union" do
+      assert unify_lift({:union, []}, {:union, []}) == {:ok, {:union, []}}
+      assert unify_lift({:union, [:integer]}, {:union, [:integer]}) == {:ok, {:union, [:integer]}}
+
+      assert unify_lift({:union, [:integer, :atom]}, {:union, [:integer, :atom]}) ==
+               {:ok, {:union, [:integer, :atom]}}
+
+      assert unify_lift({:union, [:integer, :atom]}, {:union, [:atom, :integer]}) ==
+               {:ok, {:union, [:integer, :atom]}}
+
+      assert unify_lift({:union, [:atom]}, {:union, [:boolean]}) == {:ok, {:union, [:boolean]}}
+      assert unify_lift({:union, [:boolean]}, {:union, [:atom]}) == {:ok, {:union, [:boolean]}}
+
+      assert {:error, {{:unable_unify, {:union, [:integer]}, {:union, [:atom]}, _, _}, _}} =
+               unify_lift({:union, [:integer]}, {:union, [:atom]})
+    end
+
+    test "dynamic" do
+      assert unify_lift({:literal, :foo}, :dynamic) == {:ok, {:literal, :foo}}
+      assert unify_lift(:dynamic, {:literal, :foo}) == {:ok, {:literal, :foo}}
+      assert unify_lift(:integer, :dynamic) == {:ok, :integer}
+      assert unify_lift(:dynamic, :integer) == {:ok, :integer}
+    end
+
+    test "vars" do
+      assert {{:var, 0}, var_context} = new_var({:foo, [], nil}, new_context())
+      assert {{:var, 1}, var_context} = new_var({:bar, [], nil}, var_context)
+
+      assert {:ok, {:var, 0}, context} = unify({:var, 0}, :integer, var_context)
+      assert Types.lift_type({:var, 0}, context) == :integer
+
+      assert {:ok, {:var, 0}, context} = unify(:integer, {:var, 0}, var_context)
+      assert Types.lift_type({:var, 0}, context) == :integer
+
+      assert {:ok, {:var, _}, context} = unify({:var, 0}, {:var, 1}, var_context)
+      assert {:var, _} = Types.lift_type({:var, 0}, context)
+      assert {:var, _} = Types.lift_type({:var, 1}, context)
+
+      assert {:ok, {:var, 0}, context} = unify({:var, 0}, :integer, var_context)
+      assert {:ok, {:var, 1}, context} = unify({:var, 1}, :integer, context)
+      assert {:ok, {:var, _}, context} = unify({:var, 0}, {:var, 1}, context)
+
+      assert {:ok, {:var, 0}, context} = unify({:var, 0}, :integer, var_context)
+      assert {:ok, {:var, 1}, context} = unify({:var, 1}, :integer, context)
+      assert {:ok, {:var, _}, context} = unify({:var, 1}, {:var, 0}, context)
+
+      assert {:ok, {:var, 0}, context} = unify({:var, 0}, :integer, var_context)
+      assert {:ok, {:var, 1}, context} = unify({:var, 1}, :binary, context)
+
+      assert {:error, {{:unable_unify, :binary, :integer, _, _}, _}} =
+               unify_lift({:var, 0}, {:var, 1}, context)
+
+      assert {:ok, {:var, 0}, context} = unify({:var, 0}, :integer, var_context)
+      assert {:ok, {:var, 1}, context} = unify({:var, 1}, :binary, context)
+
+      assert {:error, {{:unable_unify, :integer, :binary, _, _}, _}} =
+               unify_lift({:var, 1}, {:var, 0}, context)
+    end
+
+    test "vars inside tuples" do
+      assert {{:var, 0}, var_context} = new_var({:foo, [], nil}, new_context())
+      assert {{:var, 1}, var_context} = new_var({:bar, [], nil}, var_context)
+
+      assert {:ok, {:tuple, [{:var, 0}]}, context} =
+               unify({:tuple, [{:var, 0}]}, {:tuple, [:integer]}, var_context)
+
+      assert Types.lift_type({:var, 0}, context) == :integer
+
+      assert {:ok, {:var, 0}, context} = unify({:var, 0}, :integer, var_context)
+      assert {:ok, {:var, 1}, context} = unify({:var, 1}, :integer, context)
+
+      assert {:ok, {:tuple, [{:var, _}]}, context} =
+               unify({:tuple, [{:var, 0}]}, {:tuple, [{:var, 1}]}, context)
+
+      assert {:ok, {:var, 1}, context} = unify({:var, 1}, {:tuple, [{:var, 0}]}, var_context)
+      assert {:ok, {:var, 0}, context} = unify({:var, 0}, :integer, context)
+      assert Types.lift_type({:var, 1}, context) == {:tuple, [:integer]}
+
+      assert {:ok, {:var, 0}, context} = unify({:var, 0}, :integer, var_context)
+      assert {:ok, {:var, 1}, context} = unify({:var, 1}, :binary, context)
+
+      assert {:error, {{:unable_unify, :binary, :integer, _, _}, _}} =
+               unify_lift({:tuple, [{:var, 0}]}, {:tuple, [{:var, 1}]}, context)
+    end
+
+    # TODO: Vars inside unions
+
+    test "recursive type" do
+      assert {{:var, 0}, var_context} = new_var({:foo, [], nil}, new_context())
+      assert {{:var, 1}, var_context} = new_var({:bar, [], nil}, var_context)
+      assert {{:var, 2}, var_context} = new_var({:baz, [], nil}, var_context)
+
+      assert {:ok, {:var, _}, context} = unify({:var, 0}, {:var, 1}, var_context)
+      assert {:ok, {:var, _}, context} = unify({:var, 1}, {:var, 0}, context)
+
+      assert {:ok, {:var, _}, context} = unify({:var, 0}, {:var, 1}, var_context)
+      assert {:ok, {:var, _}, context} = unify({:var, 1}, {:var, 2}, context)
+      assert {:ok, {:var, _}, context} = unify({:var, 2}, {:var, 0}, context)
+
+      assert {:ok, {:var, _}, context} = unify({:var, 0}, {:var, 1}, var_context)
+
+      assert {:error, {{:unable_unify, {:tuple, [var: 0]}, {:var, 0}, _, _}, _}} =
+               unify_lift({:var, 1}, {:tuple, [{:var, 0}]}, context)
+
+      assert {:ok, {:var, _}, context} = unify({:var, 0}, {:var, 1}, var_context)
+      assert {:ok, {:var, _}, context} = unify({:var, 1}, {:var, 2}, context)
+
+      assert {:error, {{:unable_unify, {:tuple, [var: 0]}, {:var, 0}, _, _}, _}} =
+               unify_lift({:var, 2}, {:tuple, [{:var, 0}]}, context)
+    end
+  end
+
+  test "subtype?/3" do
+    assert subtype?({:literal, :foo}, :atom, new_context())
+    assert subtype?({:literal, true}, :boolean, new_context())
+    assert subtype?({:literal, true}, :atom, new_context())
+    assert subtype?(:boolean, :atom, new_context())
+
+    refute subtype?(:integer, :binary, new_context())
+    refute subtype?(:atom, {:literal, :foo}, new_context())
+    refute subtype?(:boolean, {:literal, true}, new_context())
+    refute subtype?(:atom, {:literal, true}, new_context())
+    refute subtype?(:atom, :boolean, new_context())
+  end
+
+  test "to_union/2" do
+    assert to_union([:atom], new_context()) == :atom
+    assert to_union([:integer, :integer], new_context()) == :integer
+    assert to_union([:boolean, :atom], new_context()) == :atom
+    assert to_union([{:literal, :foo}, :boolean, :atom], new_context()) == :atom
+
+    assert to_union([:binary, :atom], new_context()) == {:union, [:binary, :atom]}
+    assert to_union([:atom, :binary, :atom], new_context()) == {:union, [:atom, :binary]}
+
+    assert to_union([{:literal, :foo}, :binary, :atom], new_context()) ==
+             {:union, [:binary, :atom]}
+
+    assert {{:var, 0}, var_context} = new_var({:foo, [], nil}, new_context())
+    assert to_union([{:var, 0}], var_context) == {:var, 0}
+
+    # TODO: Add missing tests that uses variables and higher rank types.
+    #       We may have to change, to_union to use unify, check the return
+    #       type and throw away the returned context instead of using subtype?
+    #       since subtype? is incomplete when it comes to variables and higher
+    #       rank types.
+
+    # assert {:ok, {:var, _}, context} = unify({:var, 0}, :integer, var_context)
+    # assert to_union([{:var, 0}, :integer], context) == :integer
+
+    assert to_union([{:tuple, [:integer]}, {:tuple, [:integer]}], new_context()) ==
+             {:tuple, [:integer]}
+
+    # assert to_union([{:tuple, [:boolean]}, {:tuple, [:atom]}], new_context()) == {:tuple, [:atom]}
+  end
 end
diff --git a/lib/elixir/test/elixir/module/types_test.exs b/lib/elixir/test/elixir/module/types_test.exs
index c80c6c532..1120a8e23 100644
--- a/lib/elixir/test/elixir/module/types_test.exs
+++ b/lib/elixir/test/elixir/module/types_test.exs
@@ -26,10 +26,6 @@ defmodule Module.TypesTest do
     {:ok, Types.lift_types(types, context)}
   end
 
-  # defp lift_result({:ok, type, context}) do
-  #   {:ok, Types.lift_type(type, context)}
-  # end
-
   defp lift_result({:error, {Types, reason, location}}) do
     {:error, {reason, location}}
   end
@@ -131,5 +127,11 @@ defmodule Module.TypesTest do
     assert Types.format_type({:cons, :binary, :binary}) == "[binary() | binary()]"
     assert Types.format_type({:tuple, []}) == "{}"
     assert Types.format_type({:tuple, [:integer]}) == "{integer()}"
+    assert Types.format_type({:map, []}) == "%{}"
+    assert Types.format_type({:map, [{:integer, :atom}]}) == "%{integer() => atom()}"
+    assert Types.format_type({:map, [{:__struct__, Struct}]}) == "%Struct{}"
+
+    assert Types.format_type({:map, [{:__struct__, Struct}, {:integer, :atom}]}) ==
+             "%Struct{integer() => atom()}"
   end
 end