gyson / ex_type Goto Github PK

View Code? Open in Web Editor NEW

33.0 1.0 1.0 151 KB

A type checker for Elixir

License: MIT License

Elixir 100.00%

type checker elixir gradual-typing

ex_type's People

Stargazers

Watchers

Forkers

turion

ex_type's Issues

Exhaustiveness Checking

Curious about ex_type run on a little demo app I'm trying to put together for a talk I'm giving this Tuesday about opaque types in Elixir.
The repo is here
https://github.com/erlandsona/opaque
when I run mix type I get this output

❌  Controller.handle/1
   |
   | type error for Email._/1 with Email._(%Phone{_: bitstring()} | %Email{_: bitstring()} | %Address{city: bitstring(), state: %St{_: :washington | :tennessee | :oregon | :new_york | :colorado}, street: bitstring(), unit: nil | bitstring()})
   |
   | at ~/code/messin/lib/contact.ex:132

❌  Controller.handle/1
   |
   | type error for Address.format/1 with Address.format(%Phone{_: bitstring()} | %Email{_: bitstring()} | %Address{city: bitstring(), state: %St{_: :washington | :tennessee | :oregon | :new_york | :colorado}, street: bitstring(), unit: nil | bitstring()})
   |
   | at ~/code/messin/lib/contact.ex:131

What that's telling me is ex_type is not using pattern matching to allow the subset of a union type to pass down as just it's branch. Curious if exhaustiveness checking is implemented and if so, whether or not it supports this use case, why or why not?

Union types and `case` constructions don't interact correctly

test_case_1 and test_case_2 in test/ex_type/checker_test_case.ex don't succeed because union types and case constructions don't yet work properly. For a case expression to typecheck correctly, one has to subtract the types of the previous cases from the union for further cases.

unsupported match_typespec for structs

defmodule Foo do
  defstruct [:foo]
  @spec foo(t) :: %Foo{ foo: t } when t: any()

  def foo(t) do
    %Foo{foo: t}
  end
end

$ mix type
Compiling 1 file (.ex)
❌  Foo.foo/1
   |
   | unsupported match_typespec(map, %Foo{foo: t}, %Foo{foo: any()})
   |
   | at unknown_file:?

I believe this should typecheck.

Function with no arguments erroneously typechecks

defmodule Foo do
  @spec foo() :: :nope

  def foo() do
    :ok
  end
end

$ mix type
✅  Foo.foo/0

The function is not typecorrect, though. This should be a type error.

Not sure what it's called?

I've got a function in my demo app which I have spec'd to take any atom, and a branch which checks if it's in a subset of terms to create my struct, otherwise it will raise an ArgumentError. But this won't type check I'm assuming for similar reasons as my previous issue... But for reference, here's the snippet I changed to a stack of or's cause I thought it might have to do with st in [:a, :b, :c, :d, :etc] but same error either way.

  @spec new!(atom()) :: t() | no_return()
  def new!(st) do
    if st == :oregon or
         st == :washington or
         st == :colorado or
         st == :tennessee or
         st == :new_york do
      %__MODULE__{_: st}
    else
      raise(ArgumentError, "Unrecognized state")
    end
  end

errors with

❌  St.new!/1
   |
   | type `%St{_: atom()}` not match with union type `%St{_: :washington | :tennessee | :oregon | :new_york | :colorado}`
   |
   | at unknown_file:?

Support umbrella project

Crashes with unhelpful error message when using `send`

Consider the following minimal example:

defmodule Foo do
  @spec foo(:foo) :: :bar
  def foo(:foo) do
    send(self(), "hello")
    :bar
  end
end

Type-checking it results in this error:

$ mix type
Compiling 1 file (.ex)
** (Protocol.UndefinedError) protocol ExType.Typespecable not implemented for %ExType.Type.Port{} of type ExType.Type.Port (a struct)
    lib/ex_type/typespecable.ex:5: ExType.Typespecable.impl_for!/1
    lib/ex_type/typespecable.ex:10: ExType.Typespecable.to_quote/1
    lib/ex_type/typespec.ex:908: ExType.Typespec.match_typespec/3
    lib/ex_type/typespec.ex:885: anonymous fn/4 in ExType.Typespec.match_typespec/3
    (elixir 1.10.4) lib/enum.ex:2111: Enum."-reduce/3-lists^foldl/2-0-"/3
    lib/ex_type/typespec.ex:883: ExType.Typespec.match_typespec/3
    (elixir 1.10.4) lib/enum.ex:2111: Enum."-reduce/3-lists^foldl/2-0-"/3
    lib/ex_type/typespec.ex:691: anonymous fn/2 in ExType.Typespec.eval_spec/3

If you want I can try and fix it in a PR.

Recursive types cause endless loop

Discovered by @evnu.

defmodule IWantToSeeTheWorldBurn do
  @type a :: a
  @spec foo(a) :: a()
  def foo(a) do
    a
  end

  @type forest :: [tree]
  @type tree :: {integer, forest}
  @spec flatten(forest) :: [integer]
  def flatten(forest) do
    Enum.map(forest, fn {int, subforest} -> [int | flatten(subforest)] end)
    |> Enum.concat()
  end
end

The first example is a minimal example that should type check, but hangs. The second one is an actually useful thing people might do in practice.

Like in #39 , the problem is in the treatment of local types. They are evaluated directly, causing an endless loop of variable lookup. Maybe it's possible to stop this by making references to local types lazy. Instead of evaluating them, insert a closure, and only compute it when you need to compare the type spec to something else.

Make ExTypeTest test suite fail when typechecking finds an error

Currently, mix test succeeds, regardless of whether the files read from ExTypeTest typecheck or not. This only ensures that the typechecker doesn't crash, but it doesn't ensure that it stops typechecking correctly.

Support inline modules

Consider this minimal example:

defmodule Foo do
  defmodule Bar do
    defstruct [:bar]
  end

  @spec hello(%Bar{}) :: :world
  def hello(_) do
    :world
  end
end

$ mix type
==> ex_type
Compiling 2 files (.ex)
✅  Foo.hello/1
** (CompileError) lib/foo.ex:6: Bar.__struct__/0 is undefined, cannot expand struct Bar. Make sure the struct name is correct. If the struct name exists and is correct but it still cannot be found, you likely have cyclic module usage in your code
    (elixir 1.10.4) lib/kernel/typespec.ex:549: Kernel.Typespec.typespec/4
    (stdlib 3.12) lists.erl:1354: :lists.mapfoldl/3
    (elixir 1.10.4) lib/kernel/typespec.ex:950: Kernel.Typespec.fn_args/5
    (elixir 1.10.4) lib/kernel/typespec.ex:936: Kernel.Typespec.fn_args/6
    (elixir 1.10.4) lib/kernel/typespec.ex:377: Kernel.Typespec.translate_spec/8
    (stdlib 3.12) lists.erl:1354: :lists.mapfoldl/3
    (elixir 1.10.4) lib/kernel/typespec.ex:229: Kernel.Typespec.translate_typespecs_for_module/2

I'll try and submit a PR.

Debug mode

Often during development I find myself adding a lot of IO.inspect everywhere to understand what the type checker is doing, and removing them again. Maybe it would be good to add a debug mode, possibly by using the elixir logger. It could log on :info or :debug level and add a short comment to every function call.

Map update syntax causes error

Consider this example module:

defmodule Foo do
  @spec foo(t, map()) :: %{ :foo => t } when t: any()

  def foo(t, some_map) do
    %{some_map | foo: t}
  end
end

It causes this error:

$ mix type
** (CaseClauseError) no case clause matching: {%ExType.Context{}, %ExType.Type.List{type: %ExType.Type.Union{types: [%ExType.Type.TypedTuple{types: [%ExType.Type.Atom{literal: true, value: :foo}, %ExType.Type.Any{}]}, %ExType.Type.Map{key: %ExType.Type.Any{}, value: %ExType.Type.Any{}}]}}}
    lib/ex_type/checker.ex:37: ExType.Checker.eval/2
    lib/ex_type/typespec.ex:795: anonymous fn/3 in ExType.Typespec.match_typespec/3
    (elixir 1.10.4) lib/enum.ex:3343: Enum.flat_map_list/2
    lib/ex_type/typespec.ex:778: anonymous fn/4 in ExType.Typespec.match_typespec/3
    (elixir 1.10.4) lib/enum.ex:3343: Enum.flat_map_list/2
    lib/ex_type/typespec.ex:776: ExType.Typespec.match_typespec/3
    lib/ex_type/custom_env.ex:164: ExType.CustomEnv.process_defs/5
    (elixir 1.10.4) lib/enum.ex:1400: anonymous fn/3 in Enum.map/2

do...rescue causes crash

defmodule Foo do
  @spec foo() :: any()

  def foo() do
    raise "Oh noez"
  rescue
    e -> IO.inspect(e)
  end
end

$ mix type
** (FunctionClauseError) no function clause matching in ExType.CustomEnv.save_def/3    
    
    The following arguments were given to ExType.CustomEnv.save_def/3:
    
        # 1
        ExType.Module.Foo
    
        # 2
        {:foo, [line: 4], []}
    
        # 3
        [do: {:raise, [line: 5], ["Oh noez"]}, rescue: [{:->, [line: 7], [[{:e, [line: 7], nil}], {{:., [line: 7], [{:__aliases__, [counter: -576460752303423325, line: 7], [:IO]}, :inspect]}, [line: 7], [{:e, [line: 7], nil}]}]}]]
    
    Attempted function clauses (showing 1 out of 1):
    
        def save_def(module, call, [do: block])
    
    lib/ex_type/custom_env.ex:129: ExType.CustomEnv.save_def/3
    lib/foo.ex:4: (module)
    (stdlib 3.12) erl_eval.erl:680: :erl_eval.do_apply/6

Functions returning map literals erroneously typecheck

defmodule TypeFailures.Map.Empty do
  @spec foo() :: integer()
  def foo() do
    %{}
  end
end

This typechecks although it shouldn't.

Does not support & capture

The following module does not type check:

defmodule TypeChecks.Enum.Map do
  @spec add_one(Enum.t()) :: Enum.t()
  def add_one(enum) do
    Enum.map(enum, &(&1 + 1))
  end
end

    ❌  TypeChecks.Enum.Map.add_one/1
        |
        | unknown call &/1

Alias %MODULE breaks submodules

I have two files:

defmodule Foo.Bar do
  alias __MODULE__

  @type t :: %Bar.Baz{}
end

defmodule Foo.Bar.Baz do
  defstruct []
end

mix compile works, but mix type doesn't:

$ mix type
Compiling 1 file (.ex)
** (CompileError) lib/foo/bar.ex:4: ExType.Module.Foo.Bar.Baz.__struct__/0 is undefined, cannot expand struct ExType.Module.Foo.Bar.Baz. Make sure the struct name is correct. If the struct name exists and is correct but it still cannot be found, you likely have cyclic module usage in your code
    (elixir 1.10.4) lib/kernel/typespec.ex:549: Kernel.Typespec.typespec/4
    (elixir 1.10.4) lib/kernel/typespec.ex:294: Kernel.Typespec.translate_type/2
    (stdlib 3.12) lists.erl:1354: :lists.mapfoldl/3
    (elixir 1.10.4) lib/kernel/typespec.ex:228: Kernel.Typespec.translate_typespecs_for_module/2
    (elixir 1.10.4) src/elixir_erl_compiler.erl:12: anonymous fn/3 in :elixir_erl_compiler.spawn/2

It seems like mix compile creates the modules in a cleverer order.

More context

When we put both modules in one file, some variants work and others don't:

Doesn't work

defmodule Foo.Bar do
  alias Foo.Bar # Also with __MODULE__

  @type t :: %Bar.Baz{}
end

defmodule Foo.Bar.Baz do
  defstruct []
end

Works

defmodule Foo.Bar.Baz do
  defstruct []
end

defmodule Foo.Bar do
  alias Foo.Bar # Also with __MODULE__

  @type t :: %Bar.Baz{}
end

defmodule Foo.Bar do
  defmodule Baz do
    defstruct []
  end

  alias __MODULE__

  @type t :: %Bar.Baz{}
end

defmodule Foo.Bar do
  alias __MODULE__

  defmodule Baz do
    defstruct []
  end

  @type t :: %Bar.Baz{}
end

defmodule Foo.Bar do
  alias __MODULE__

  @type t :: %Bar.Baz{}

  defmodule Baz do
    defstruct []
  end
end

Maybe support inline type hint

We should already be able to do type hint with T.assert( expr :: type ). For example,

map = %{} 

# type is empty map

T.assert(map :: %{optional(String.t) => integer})

# type is updated to %{optional(String.t) => integer} now.

if we support inline type hint like expr ~> type annotation. it may be easier (syntax sugar) to do type declaration, especially in pattern match.

we can do

{first ~> integer(), second ~> String.t} = something_untyped

instead of

{first, second} = something_untyped
T.assert first :: integer
T.assert second :: String.t

^^ benefit is to avoid write first and second twice.

Implementation concern

need to do some hacky thing to make it work. not sure if it worths the cost.

Support "or in guard" and "if ... else... "

It currently does not support or in guard at the moment.
Since "if ... else ..." would be compiled to case ... x == false or x == nil (use or in guard), it cannot support "if ... else ...".

Advanced support for union type + pattern match

from #8 and #9, we have basic support for union type and pattern match, like following:

@spec example({:a, t1} | {:b, t2} | {:c, t3}) :: any

def example({:a, x}) do
  # ex type should be able to know that `x` is t1 type
end

def example({:b, x}) do
  # ex type should be able to know that `x` is t2 type
end

def example({:c, x}) do
  # ex type should be able to know that `x` is t3 type
end

it could be nice if we can have more advanced support like following:

@spec example({:a, t1} | {:b, t2} | {:c, t3}) :: any

def example({:a, x}) do
  # ex type should be able to know that `x` is t1 type
end

def example({:b, x}) do
  # ex type should be able to know that `x` is t2 type
end

def example(y) do
  # ex type should be able to know that `y` is `{:c, t3}` type
end

also, similarly, for case special form:

# when x is type `{:ok, integer} | {:error, String.t()} | :error`
case x do
  {:ok, y} -> 
    # ex type should be able to figure out that `y` is `integer` type

  e ->
    # ex type should be able to figure out that `e` is `{:error, String.t()} | :error` type
end

This advanced support should cover

multi clauses functions
case special form
anonymous function

Crashes on new project

In order to more reliably test #18, I did the following simple steps:

mix new foo
cd foo
Edit mix.exs so that it contains:

  defp deps do
    [
      {:ex_type, "~> 0.5.0"}
    ]
  end

mix type

Error:

$ mix type
Compiling 1 file (.ex)
Generated foo app
** (ArgumentError) argument error
    :erlang.length(nil)
    lib/ex_type/custom_env.ex:42: anonymous fn/1 in ExType.CustomEnv.BeforeCompile."MACRO-__before_compile__"/2
    (elixir 1.10.4) lib/enum.ex:1396: Enum."-map/2-lists^map/1-0-"/2
    expanding macro: ExType.CustomEnv.BeforeCompile.__before_compile__/1
    lib/foo.ex:1: ExType.Module.Foo (module)
    (elixir 1.10.4) lib/code.ex:341: Code.eval_string_with_error_handling/3

Put existing typechecking projects on CI

Proposal

Projects that already typecheck (you seem to have two) could be added as git submodules, or checked out in a CI script. Future runs of the type checker should keep checking them without crashes. That way we're less likely to introduce new type checker bugs.

Type error for number arithmetic function

Hey! Super cool project! I'm interested in seeing what comes from it.

When playing around with it, I found that the following code:

defmodule Client do

  @spec add(number(), number()) :: number()
  def add(x, y) do
    x + y
  end
end

produces the following type error:

❯ mix type
Compiling 1 file (.ex)
❌  Client.add/2
   |
   | type error for :erlang.+/2 with :erlang.+(integer() | float(), integer() | float())
   |
   | at /home/shayne/elixir/type_hooks/lib/client.ex:5

Is there a reason why this type check fails? Does ex_type require stricter types than unions like number()? If this is not a bug, what could the error message be to make the type issue more clear?

Thanks!

Create tests for failing type checks

There could be a test for functions that should not typecheck. For example:

@spec foo(:foo | :bar) :: :foo
def foo(:foo) do
  :foo
end

This fails because the :bar case isn't matched, which is awesome. It would be great if it was possible to add this to to the tests so it isn't accidentally broken.

defmodule Foo do
  defstruct [:foo]
  @spec foo(t) :: %Foo{ foo: t } when t: any()

  def foo(t) do
    %Foo{foo(23) | foo: t}
  end
end

$ mix type
Compiling 1 file (.ex)
** (FunctionClauseError) no function clause matching in anonymous fn/1 in ExType.Checker.eval/2    
    
    The following arguments were given to anonymous fn/1 in ExType.Checker.eval/2:
    
        # 1
        {:|, [line: 6], [{:foo, [line: 6], [23]}, [foo: {:t, [line: 6], nil}]]}
    
    lib/ex_type/checker.ex:66: anonymous fn/1 in ExType.Checker.eval/2
    (elixir 1.10.4) lib/enum.ex:1396: Enum."-map/2-lists^map/1-0-"/2
    lib/ex_type/checker.ex:66: ExType.Checker.eval/2
    lib/ex_type/typespec.ex:795: anonymous fn/3 in ExType.Typespec.match_typespec/3
    (elixir 1.10.4) lib/enum.ex:3343: Enum.flat_map_list/2
    lib/ex_type/typespec.ex:778: anonymous fn/4 in ExType.Typespec.match_typespec/3
    (elixir 1.10.4) lib/enum.ex:3343: Enum.flat_map_list/2
    lib/ex_type/typespec.ex:776: ExType.Typespec.match_typespec/3

Cannot use var as type variable

Consider this example:

defmodule Foo do
  defstruct [:foo]
  @type t(foo) :: %__MODULE__{
    foo: foo
  }

  @spec get_foo(t(foo)) :: foo when foo: var
  def get_foo(%Foo{foo: foo}) do
    foo
  end
end

$ mix type
==> ex_type
Compiling 12 files (.ex)
warning: Code.ensure_compiled?/1 is deprecated. Use Code.ensure_compiled/1 instead (see the proper disclaimers in its docs)
  lib/ex_type/typespec.ex:831: ExType.Typespec.match_typespec/3

** (CaseClauseError) no case clause matching: {:error, {:not_found_type, Foo, :var, 0}}
    lib/ex_type/typespec.ex:616: ExType.Typespec.eval_type/2
    lib/ex_type/typespec.ex:657: anonymous fn/5 in ExType.Typespec.fetch_specs/3
    (elixir 1.10.4) lib/enum.ex:1396: Enum."-map/2-lists^map/1-0-"/2
    lib/ex_type/typespec.ex:653: anonymous fn/4 in ExType.Typespec.fetch_specs/3
    (elixir 1.10.4) lib/enum.ex:1396: Enum."-map/2-lists^map/1-0-"/2
    lib/ex_type/typespec.ex:648: ExType.Typespec.fetch_specs/3
    lib/ex_type/custom_env.ex:169: ExType.CustomEnv.process_defs/5
    (elixir 1.10.4) lib/enum.ex:1400: anonymous fn/3 in Enum.map/2

When I change the spec to @spec get_foo(t(foo)) :: foo when foo: term(), it works.

Local parametrised types are broken

defmodule Foo do
  @type t(elem) :: [elem]

  @spec mylength(t(term())) :: integer()

  def mylength(_) do
    23
  end
end

$ mix type
** (FunctionClauseError) no function clause matching in ExType.Typespec.eval_type/2    
    
    The following arguments were given to ExType.Typespec.eval_type/2:
    
        # 1
        %ExType.Type.Any{}
    
        # 2
        {Foo, %{elem: %ExType.Type.Any{}}}
    
    Attempted function clauses (showing 10 out of 57):
    
        def eval_type({:any, _, []}, _)
        def eval_type({:none, _, []}, _)
        def eval_type({:atom, _, []}, _)
        def eval_type({:map, _, []}, _)
        def eval_type({:pid, _, []}, _)
        def eval_type({:port, _, []}, _)
        def eval_type({:reference, _, []}, _)
        def eval_type({:struct, _, []}, _)
        def eval_type({:tuple, _, []}, _)
        def eval_type({:float, _, []}, _)
        ...
        (47 clauses not shown)
    
    lib/ex_type/typespec.ex:249: ExType.Typespec.eval_type/2
    lib/ex_type/typespec.ex:342: ExType.Typespec.eval_type/2
    (elixir 1.10.4) lib/enum.ex:1396: Enum."-map/2-lists^map/1-0-"/2
    lib/ex_type/typespec.ex:666: anonymous fn/4 in ExType.Typespec.fetch_specs/3
    (elixir 1.10.4) lib/enum.ex:1396: Enum."-map/2-lists^map/1-0-"/2
    lib/ex_type/typespec.ex:648: ExType.Typespec.fetch_specs/3
    lib/ex_type/custom_env.ex:154: ExType.CustomEnv.process_defs/5
    (elixir 1.10.4) lib/enum.ex:1400: anonymous fn/3 in Enum.map/2

Deprecation warning with elixir 1.10

Elixir 1.10 gives this deprecation warning:

warning: Code.ensure_compiled?/1 is deprecated. Use Code.ensure_compiled/1 instead (see the proper disclaimers in its docs)
  lib/ex_type/typespec.ex:831: ExType.Typespec.match_typespec/3

Support custom typespec

Support custom typespec in type.exs conf file. (kind of like type definitions from Typescript)
The scope of this custom typespec should be limited to the package.
It would override exist typespec.

example type.exs file:

[
  typespec: %{
    Enum => quote do 
      @type some_special_type :: any()

      @spec map(T.p(Enumerable, x), (x -> y)) :: [y] when x: any(), y: any()
    end
  }
]

Support "def name do" syntax

Currently, it only supports def name() do but not def name do (because they have different ast tree).

Need to support def/defp name do as well.