Repository: fika-lang/fika (elixir)

Issue:
Add support for maps
Maps will have the following syntax:

```
{"foo" => 123} # Type: Map(String, Int)
```

Don't worry about empty maps for now. We'll handle that separately. Please refer the Fika language hacking guide inside `/docs` to understand the steps involved in adding new syntax to Fika.

Pull request description:
Add support for maps
Closes #25 

Patch:
diff --git a/example.fi b/example.fi
index aa66648..6b7df1b 100644
--- a/example.fi
+++ b/example.fi
@@ -54,6 +54,11 @@ fn rec : {foo: List(Int)} do
   {foo: [1, 2, 3]}
 end
 
+# Maps are useful for holding data when keys are only know at runtime
+# A map can hold key-value data that grows dynamically but have the same type
+fn map : Map(String, List(Int)) do
+  {"james-bond" => [0, 0, 7]}
+end
 
 # Logical operator - or
 fn or(a: Bool, b: Bool) : Bool do
diff --git a/lib/fika/erl_translate.ex b/lib/fika/erl_translate.ex
index 4b8bd62..0853927 100644
--- a/lib/fika/erl_translate.ex
+++ b/lib/fika/erl_translate.ex
@@ -137,6 +137,15 @@ defmodule Fika.ErlTranslate do
     {:map, line, k_vs}
   end
 
+  defp translate_exp({:map, {line, _, _}, key_values}) do
+    key_values =
+      Enum.map(key_values, fn {{_, {l, _, _}, _} = k, v} ->
+        {:map_field_assoc, l, translate_exp(k), translate_exp(v)}
+      end)
+
+    {:map, line, key_values}
+  end
+
   defp translate_exp({:function_ref, {line, _, _}, {module, function, arg_types}}) do
     arity = length(arg_types)
 
diff --git a/lib/fika/parser/helper.ex b/lib/fika/parser/helper.ex
index 6fa8677..25a70ff 100644
--- a/lib/fika/parser/helper.ex
+++ b/lib/fika/parser/helper.ex
@@ -123,6 +123,10 @@ defmodule Fika.Parser.Helper do
     {:tuple, line, result}
   end
 
+  def do_to_ast({key_values, line}, :map) do
+    {:map, line, key_values}
+  end
+
   def do_to_ast({[k, v], _line}, :key_value) do
     {k, v}
   end
diff --git a/lib/fika/parser/literal_exps.ex b/lib/fika/parser/literal_exps.ex
index 90d6da8..7a6a512 100644
--- a/lib/fika/parser/literal_exps.ex
+++ b/lib/fika/parser/literal_exps.ex
@@ -84,6 +84,30 @@ defmodule Fika.Parser.LiteralExps do
     |> label("record")
     |> Helper.to_ast(:record)
 
+  map_key_value =
+    allow_space
+    |> concat(exp)
+    |> concat(allow_space)
+    |> ignore(string("=>"))
+    |> concat(allow_space)
+    |> concat(exp)
+    |> label("map key value pair")
+    |> Helper.to_ast(:key_value)
+
+  map_content =
+    allow_space
+    |> ignore(string(","))
+    |> concat(allow_space)
+    |> concat(map_key_value)
+
+  map =
+    ignore(string("{"))
+    |> concat(map_key_value)
+    |> repeat(map_content)
+    |> optional(ignore(string(",")))
+    |> ignore(string("}"))
+    |> Helper.to_ast(:map)
+
   type_args_list =
     optional(
       allow_space
@@ -115,6 +139,7 @@ defmodule Fika.Parser.LiteralExps do
       exp_list,
       tuple,
       record,
+      map,
       function_ref,
       atom
     ])
diff --git a/lib/fika/parser/types.ex b/lib/fika/parser/types.ex
index 253f074..7ffcfae 100644
--- a/lib/fika/parser/types.ex
+++ b/lib/fika/parser/types.ex
@@ -67,6 +67,19 @@ defmodule Fika.Parser.Types do
     |> reduce({Enum, :join, []})
     |> label("record type")
 
+  # To parse functions with map return type
+  map_type =
+    string("Map")
+    |> string("(")
+    |> parsec(:type)
+    |> concat(allow_space)
+    |> string(",")
+    |> concat(allow_space)
+    |> parsec(:type)
+    |> concat(allow_space)
+    |> string(")")
+    |> label("map type")
+
   # To parse functions with tuple return type
   type_tuple_element =
     parsec(:type)
@@ -96,6 +109,7 @@ defmodule Fika.Parser.Types do
       |> optional(type_parens),
       atom,
       record_type,
+      map_type,
       tuple_type
     ])
 
diff --git a/lib/fika/type_checker.ex b/lib/fika/type_checker.ex
index 9fc711a..016abcb 100644
--- a/lib/fika/type_checker.ex
+++ b/lib/fika/type_checker.ex
@@ -219,6 +219,43 @@ defmodule Fika.TypeChecker do
     end
   end
 
+  # Map
+  # TODO: refactor this when union types are available
+  def infer_exp(env, {:map, _, [kv | rest_kvs]}) do
+    {key, value} = kv
+
+    with {:ok, key_type, env} <- infer_exp(env, key),
+         {:ok, val_type, env} <- infer_exp(env, value) do
+      final_type = "Map(#{key_type},#{val_type})"
+
+      Enum.reduce_while(rest_kvs, {:ok, final_type, env}, fn {k, v}, {:ok, acc_type, acc_env} ->
+        case infer_exp(acc_env, k) do
+          {:ok, ^key_type, env} ->
+            case infer_exp(env, v) do
+              {:ok, ^val_type, env} ->
+                acc = {:ok, acc_type, env}
+                {:cont, acc}
+
+              {:ok, diff_type, _} ->
+                error = {:error, "Expected map value of type #{val_type}, but got #{diff_type}"}
+
+                {:halt, error}
+
+              error ->
+                {:halt, error}
+            end
+
+          {:ok, diff_type, _} ->
+            error = {:error, "Expected map key of type #{key_type}, but got #{diff_type}"}
+            {:halt, error}
+
+          error ->
+            {:halt, error}
+        end
+      end)
+    end
+  end
+
   # Function ref
   def infer_exp(env, {:function_ref, _, {module, function_name, arg_types}}) do
     Logger.debug("Inferring type of function: #{function_name}")


Test patch:
diff --git a/test/fika/erl_translate_test.exs b/test/fika/erl_translate_test.exs
index d03d31e..cab5f4e 100644
--- a/test/fika/erl_translate_test.exs
+++ b/test/fika/erl_translate_test.exs
@@ -99,6 +99,15 @@ defmodule Fika.ErlTranslateTest do
               ]}
   end
 
+  test "map" do
+    str = ~s({"foo" => 1})
+    ast = TestParser.expression!(str)
+    result = ErlTranslate.translate_expression(ast)
+
+    assert result ==
+             {:map, 1, [{:map_field_assoc, 1, {:string, 1, 'foo'}, {:integer, 1, 1}}]}
+  end
+
   describe "function reference" do
     test "with module" do
       str = "&my_module.foo(Int, Int)"
diff --git a/test/fika/parser_test.exs b/test/fika/parser_test.exs
index cba3158..740aec6 100644
--- a/test/fika/parser_test.exs
+++ b/test/fika/parser_test.exs
@@ -666,6 +666,101 @@ defmodule Fika.ParserTest do
     end
   end
 
+  describe "map" do
+    test "parses map with key values" do
+      str = """
+      {"a" => 1}
+      """
+
+      result = TestParser.expression!(str)
+
+      assert result ==
+               {:map, {1, 0, 10}, [{{:string, {1, 0, 4}, ["a"]}, {:integer, {1, 0, 9}, 1}}]}
+    end
+
+    test "parses map with complex expression" do
+      str = """
+      {[1+1, 2] => {"1" => {1, 2, 3}}}
+      """
+
+      result = TestParser.expression!(str)
+
+      assert result ==
+               {
+                 :map,
+                 {1, 0, 32},
+                 [
+                   {
+                     {:list, {1, 0, 9},
+                      [
+                        {:call, {:+, {1, 0, 5}},
+                         [{:integer, {1, 0, 3}, 1}, {:integer, {1, 0, 5}, 1}], :kernel},
+                        {:integer, {1, 0, 8}, 2}
+                      ]},
+                     {:map, {1, 0, 31},
+                      [
+                        {{:string, {1, 0, 17}, ["1"]},
+                         {:tuple, {1, 0, 30},
+                          [
+                            {:integer, {1, 0, 23}, 1},
+                            {:integer, {1, 0, 26}, 2},
+                            {:integer, {1, 0, 29}, 3}
+                          ]}}
+                      ]}
+                   }
+                 ]
+               }
+
+      str = """
+      {true & false => false}
+      """
+
+      result = TestParser.expression!(str)
+
+      assert result ==
+               {:map, {1, 0, 23},
+                [
+                  {{:call, {:&, {1, 0, 13}},
+                    [{:boolean, {1, 0, 5}, true}, {:boolean, {1, 0, 13}, false}], :kernel},
+                   {:boolean, {1, 0, 22}, false}}
+                ]}
+    end
+
+    test "parses map with function as key-values" do
+      str = """
+      {foo(1, 2) => bar(true)}
+      """
+
+      result = TestParser.expression!(str)
+
+      assert result ==
+               {:map, {1, 0, 24},
+                [
+                  {{:call, {:foo, {1, 0, 10}},
+                    [{:integer, {1, 0, 6}, 1}, {:integer, {1, 0, 9}, 2}], nil},
+                   {:call, {:bar, {1, 0, 23}}, [{:boolean, {1, 0, 22}, true}], nil}}
+                ]}
+
+      str = """
+      {&foo.bar => jar(true)}
+      """
+
+      result = TestParser.expression!(str)
+
+      assert result ==
+               {
+                 :map,
+                 {1, 0, 23},
+                 [
+                   {
+                     {:function_ref, {1, 0, 9}, {:foo, :bar, []}},
+                     {:call, {:jar, {1, 0, 22}}, [{:boolean, {1, 0, 21}, true}], nil}
+                   }
+                 ]
+               }
+    end
+  end
+
   describe "tuple" do
     test "parses tuple with one element" do
       str = """
diff --git a/test/fika/type_checker_test.exs b/test/fika/type_checker_test.exs
index 6a26924..a8a5f87 100644
--- a/test/fika/type_checker_test.exs
+++ b/test/fika/type_checker_test.exs
@@ -335,6 +335,32 @@ defmodule Fika.TypeCheckerTest do
     end
   end
 
+  describe "map" do
+    test "type check for a valid expression" do
+      str = ~s({"foo" => 123, "bar" => 345})
+
+      ast = TestParser.expression!(str)
+
+      assert {:ok, "Map(String,Int)", _} = TypeChecker.infer_exp(Env.init(), ast)
+    end
+
+    test "type check for map with mixed type" do
+      str = ~s({1 => [1, 2], "foo" => 345})
+
+      ast = TestParser.expression!(str)
+
+      assert {:error, "Expected map key of type Int, but got String"} =
+               TypeChecker.infer_exp(Env.init(), ast)
+
+      str = ~s({"foo" => [1, 2], "bar" => 345})
+
+      ast = TestParser.expression!(str)
+
+      assert {:error, "Expected map value of type List(Int), but got Int"} =
+               TypeChecker.infer_exp(Env.init(), ast)
+    end
+  end
+
   describe "function reference" do
     test "with args" do
       str = "&bar.sum(Int, Int)"