Why doesn't Dialyzer find this code wrong?

Question

I've created the snippet below based on this tutorial. The last two lines (feed_squid(FeederRP) and feed_red_panda(FeederSquid)) are obviously violating the defined constraints, yet Dialyzer finds them okay. This is quite disappointing, because this is exactly the type of error I want to catch with a tool performing static analysis.

There is an explanation provided in the tutorial:

Before the functions are called with the wrong kind of feeder, they're first called with the right kind. As of R15B01, Dialyzer would not find an error with this code. The observed behaviour is that as soon as a call to a given function succeeds within the function's body, Dialyzer will ignore later errors within the same unit of code.

What is the rationale for this behavior? I understand that the philosophy behind success typing is "to never cry wolf", but in the current scenario Dialyzer plainly ignores the intentionally defined function specifications (after it sees that the functions have been called correctly earlier). I understand that the code does not result in a runtime crash. Can I somehow force Dialyzer to always take my function specifications seriously? If not, is there a tool that can do it?

-module(zoo).
-export([main/0]).

-type red_panda() :: bamboo | birds | eggs | berries.
-type squid() :: sperm_whale.
-type food(A) :: fun(() -> A).

-spec feeder(red_panda) -> food(red_panda());
            (squid) -> food(squid()).
feeder(red_panda) ->
    fun() ->
            element(random:uniform(4), {bamboo, birds, eggs, berries})
    end;
feeder(squid) ->
    fun() -> sperm_whale end.

-spec feed_red_panda(food(red_panda())) -> red_panda().
feed_red_panda(Generator) ->
    Food = Generator(),
    io:format("feeding ~p to the red panda~n", [Food]),
    Food.

-spec feed_squid(food(squid())) -> squid().
feed_squid(Generator) ->
    Food = Generator(),
    io:format("throwing ~p in the squid's aquarium~n", [Food]),
    Food.

main() ->
    %% Random seeding
    <<A:32, B:32, C:32>> = crypto:rand_bytes(12),
    random:seed(A, B, C),
    %% The zoo buys a feeder for both the red panda and squid
    FeederRP = feeder(red_panda),
    FeederSquid = feeder(squid),
    %% Time to feed them!
    feed_squid(FeederSquid),
    feed_red_panda(FeederRP),
    %% This should not be right!
    feed_squid(FeederRP),
    feed_red_panda(FeederSquid).

Shelli

I'm the author of that chapter/example and I would like an answer, but I couldn't get feedback from the Dialyzer team before publishing the chapter. – Ferric

I apologize for the delay. I will try to give an 'insider' answer to this question and send some feedback to the author. – Ben

Answer 1

Minimizing the example quite a bit I have these two versions:

First one that Dialyzer can catch:

-module(zoo).
-export([main/0]).

-type red_panda_food() :: bamboo.
-type squid_food()     :: sperm_whale.

-spec feed_squid(fun(() -> squid_food())) -> squid_food().
feed_squid(Generator) -> Generator().

main() ->
    %% The zoo buys a feeder for both the red panda and squid
    FeederRP = fun() -> bamboo end,
    FeederSquid = fun() -> sperm_whale end,
    %% CRITICAL POINT %%
    %% This should not be right!
    feed_squid(FeederRP),
    %% Time to feed them!
    feed_squid(FeederSquid)

Then the one with no warnings:

    [...]
    %% CRITICAL POINT %%
    %% Time to feed them!
    feed_squid(FeederSquid)
    %% This should not be right!
    feed_squid(FeederRP).

Dialyzer's warnings for the version it can catch are:

zoo.erl:7: The contract zoo:feed_squid(fun(() -> squid_food())) -> squid_food() cannot be right because the inferred return for feed_squid(FeederRP::fun(() -> 'bamboo')) on line 15 is 'bamboo'
zoo.erl:10: Function main/0 has no local return

... and is a case of preferring to trust its own judgement against a user's tighter spec.

For the version it doesn't catch, Dialyzer assumes that the feed_squid/1 argument's type fun() -> bamboo is a supertype of fun() -> none() (a closure that will crash, which, if not called within feed_squid/1, is still a valid argument). After the types have been inferred, Dialyzer cannot know if a passed closure is actually called within a function or not.

Dialyzer still gives a warning if the option -Woverspecs is used:

zoo.erl:7: Type specification zoo:feed_squid(fun(() -> squid_food())) -> squid_food() is a subtype of the success typing: zoo:feed_squid(fun(() -> 'bamboo' | 'sperm_whale')) -> 'bamboo' | 'sperm_whale'

... warning that nothing prevents this function to handle the other feeder or any given feeder! If that code did check for the closure's expected input/output, instead of being generic, then I am pretty sure that Dialyzer would catch the abuse. From my point of view, it is much better if your actual code checks for erroneous input instead of you relying on type specs and Dialyzer (which never promised to find all the errors anyway).

WARNING: DEEP ESOTERIC PART FOLLOWS!

The reason why the error is reported in the first case but not the second has to do with the progress of module-local refinement. Initially the function feed_squid/1 has success typing (fun() -> any()) -> any(). In the first case the function feed_squid/1 will first be refined with just the FeederRP and will definitely return bamboo, immediately falsifying the spec and stopping further analysis of main/0. In the second, the function feed_squid/1 will first be refined with just the FeederSquid and will definitely return sperm_whale, then refined with both FeederSquid and FeederRP and return sperm_whale OR bamboo. When then called with FeederRP the expected return value success-typing-wise is sperm_whale OR bamboo. The spec then promises that it will be sperm_whale and Dialyzer accepts it. On the other hand, the argument should be fun() -> bamboo | sperm_whale success-typing-wise, it is fun() -> bamboo so that leaves it with just fun() -> bamboo. When that is checked against the spec (fun() -> sperm_whale), Dialyzer assumes that the argument could be fun() -> none(). If you never call the passed function within feed_squid/1 (something that Dialyzer's type system doesn't keep as information), and you promise in the spec that you will always return sperm_whale, everything is fine!

What can be 'fixed' is for the type system to be extended to note when a closure that is passed as an argument is actually used in a call and warn in cases where the only way to 'survive' some part of the type inference is to be fun(...) -> none().

Ben

Answer 2

(Note, I am speculating a bit here. I have not read the dialyzer code in detail).

A "Normal" full-fledged type checker has the advantage that type checking is decidable. We can ask "Is this program well-typed" and get either a Yes or a No back when the type checker terminates. Not so for the dialyzer. It is essentially in the business of solving the halting problem. The consequence is that there will be programs which are blatantly wrong, but still slips through the grips of the dialyzer.

However, this is not one of those cases :)

The problem is two-fold. A success type says "If this function terminates normally, what is its type?". In the above, our feed_red_panda/1 function terminates for any argument matching fun (() -> A) for an arbitrary type A. We could call feed_red_panda(fun erlang:now/0) and it should also work. Thus our two calls to the function in main/0 does not give rise to a problem. They both terminate.

The second part of the problem is "Did you violate the spec?". Note that often, specs are not used in the dialyzer as a fact. It infers the types itself and uses the inference patterns instead of your spec. Whenever a function is called, it is annotated with the parameters. In our case, it will be annotated with the two generator types: food(red_panda()), food(squid()). Then a function local analysis is made based on these annotations in order to figure out if you violated the spec. Since the correct parameters are present in the annotations, we must assume the function is used correctly in some part of the code. That it is also called with squids could be an artifact of code which are never called due to other circumstances. Since we are function-local we don't know and give the benefit of doubt to the programmer.

If you change the code to only make the wrong call with a squid-generator, then we find the spec-discrepancy. Because we know the only possible call site violates the spec. If you move the wrong call to another function, it is not found either. Because the annotation is still on the function and not on the call site.

One could imagine a future variant of the dialyzer which accounted for the fact that each call-site can be handled individually. Since the dialyzer is changing as well over time, it may be that it will be able to handle this situation in the future. But currently, it is one of the errors that will slip through.

The key is to notice that the dialyzer cannot be used as a "Checker of well-typedness". You can't use it to enforce structure on your programs. You need to do that yourself. If you would like more static checking, it would probably be possible to write a type checker for Erlang and run it on parts of your code base. But you will run into trouble with code upgrades and distribution, which are not easy to handle.

Tamboura

Just as a side-note, an extension similar to "each call-site can be handled individually" is already implemented. It is just a little bit slow. Now that Dialyzer has turned parallel however things might change...! – Ben