dialyzer: Fix opaque bug

The "decoration" of opaque types works better than before when opaque
types are used by other opaque types.

4 files changed, 262 insertions, 45 deletions

diff --git a/lib/dialyzer/test/opaque_SUITE_data/results/para b/lib/dialyzer/test/opaque_SUITE_data/results/para
index 8fe67e39ad..b23d0cae3a 100644
--- a/lib/dialyzer/test/opaque_SUITE_data/results/para
+++ b/lib/dialyzer/test/opaque_SUITE_data/results/para
@@ -19,9 +19,9 @@ para3.erl:55: Invalid type specification for function para3:t2/0. The success ty
 para3.erl:65: The attempt to match a term of type {{{{{para3_adt:ot1(_,_,_,_,_)}}}}} against the pattern {{{{{17}}}}} breaks the opaqueness of para3_adt:ot1(_,_,_,_,_)
 para3.erl:68: The pattern {{{{17}}}} can never match the type {{{{{para3_adt:ot1(_,_,_,_,_)}}}}}
 para3.erl:74: Invalid type specification for function para3:exp_adt/0. The success typing is () -> 3
-para4.erl:21: Invalid type specification for function para4:a/1. The success typing is (dict:dict(atom() | integer(),atom() | integer()) | para4:d_all()) -> [{atom() | integer(),atom() | integer()}]
-para4.erl:26: Invalid type specification for function para4:i/1. The success typing is (dict:dict(atom() | integer(),atom() | integer()) | para4:d_all()) -> [{atom() | integer(),atom() | integer()}]
-para4.erl:31: Invalid type specification for function para4:t/1. The success typing is (dict:dict(atom() | integer(),atom() | integer()) | para4:d_all()) -> [{atom() | integer(),atom() | integer()}]
+para4.erl:21: Invalid type specification for function para4:a/1. The success typing is (para4:d_all() | para4:d_atom()) -> [{atom() | integer(),atom() | integer()}]
+para4.erl:26: Invalid type specification for function para4:i/1. The success typing is (para4:d_all() | para4:d_integer()) -> [{atom() | integer(),atom() | integer()}]
+para4.erl:31: Invalid type specification for function para4:t/1. The success typing is (para4:d_all() | para4:d_tuple()) -> [{atom() | integer(),atom() | integer()}]
 para4.erl:59: Attempt to test for equality between a term of type para4_adt:t(atom() | integer()) and a term of opaque type para4_adt:t(integer())
 para4.erl:64: Attempt to test for equality between a term of type para4_adt:t(atom() | integer()) and a term of opaque type para4_adt:t(atom())
 para4.erl:69: Attempt to test for equality between a term of type para4_adt:int(1 | 2 | 3 | 4) and a term of opaque type para4_adt:int(1 | 2)
diff --git a/lib/dialyzer/test/opaque_SUITE_data/src/hipe_vectors/hipe_ig_moves.erl b/lib/dialyzer/test/opaque_SUITE_data/src/hipe_vectors/hipe_ig_moves.erl
new file mode 100644
index 0000000000..2a70606dab
--- /dev/null
+++ b/lib/dialyzer/test/opaque_SUITE_data/src/hipe_vectors/hipe_ig_moves.erl
@@ -0,0 +1,83 @@
+%% -*- erlang-indent-level: 2 -*-
+%%
+%% %CopyrightBegin%
+%% 
+%% Copyright Ericsson AB 2001-2016. All Rights Reserved.
+%% 
+%% Licensed under the Apache License, Version 2.0 (the "License");
+%% you may not use this file except in compliance with the License.
+%% You may obtain a copy of the License at
+%%
+%%     http://www.apache.org/licenses/LICENSE-2.0
+%%
+%% Unless required by applicable law or agreed to in writing, software
+%% distributed under the License is distributed on an "AS IS" BASIS,
+%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+%% See the License for the specific language governing permissions and
+%% limitations under the License.
+%% 
+%% %CopyrightEnd%
+%%
+%%=============================================================================
+
+-module(hipe_ig_moves).
+-export([new/1,
+	 new_move/3,
+	 get_moves/1]).
+
+%%-----------------------------------------------------------------------------
+%% The main data structure; its fields are:
+%%  - movelist  : mapping from temp to set of associated move numbers
+%%  - nrmoves   : number of distinct move instructions seen so far
+%%  - moveinsns : list of move instructions, in descending move number order
+%%  - moveset   : set of move instructions
+
+-record(ig_moves, {movelist                    :: movelist(),
+		   nrmoves   = 0               :: non_neg_integer(),
+		   moveinsns = []              :: [{_,_}],
+		   moveset   = gb_sets:empty() :: gb_sets:set()}).
+
+-type movelist() :: hipe_vectors:vector(ordsets:ordset(non_neg_integer())).
+
+%%-----------------------------------------------------------------------------
+
+-spec new(non_neg_integer()) -> #ig_moves{}.
+
+new(NrTemps) ->
+  MoveList = hipe_vectors:new(NrTemps, ordsets:new()),
+  #ig_moves{movelist = MoveList}.
+
+-spec new_move(_, _, #ig_moves{}) -> #ig_moves{}.
+
+new_move(Dst, Src, IG_moves) ->
+  MoveSet = IG_moves#ig_moves.moveset,
+  MoveInsn = {Dst, Src},
+  case gb_sets:is_member(MoveInsn, MoveSet) of
+    true ->
+      IG_moves;
+    false ->
+      MoveNr = IG_moves#ig_moves.nrmoves,
+      Movelist0 = IG_moves#ig_moves.movelist,
+      Movelist1 = add_movelist(MoveNr, Dst,
+			       add_movelist(MoveNr, Src, Movelist0)),
+      IG_moves#ig_moves{nrmoves = MoveNr+1,
+			movelist = Movelist1,
+			moveinsns = [MoveInsn|IG_moves#ig_moves.moveinsns],
+			moveset = gb_sets:insert(MoveInsn, MoveSet)}
+  end.
+
+-spec add_movelist(non_neg_integer(), non_neg_integer(), movelist())
+		  -> movelist().
+
+add_movelist(MoveNr, Temp, MoveList) ->
+  AssocMoves = hipe_vectors:get(MoveList, Temp),
+  %% XXX: MoveNr does not occur in moveList[Temp], but the new list must be an
+  %% ordset due to the ordsets:union in hipe_coalescing_regalloc:combine().
+  hipe_vectors:set(MoveList, Temp, ordsets:add_element(MoveNr, AssocMoves)).
+
+-spec get_moves(#ig_moves{}) -> {movelist(), non_neg_integer(), tuple()}.
+
+get_moves(IG_moves) -> % -> {MoveList, NrMoves, MoveInsns}
+  {IG_moves#ig_moves.movelist,
+   IG_moves#ig_moves.nrmoves,
+   list_to_tuple(lists:reverse(IG_moves#ig_moves.moveinsns))}.
diff --git a/lib/dialyzer/test/opaque_SUITE_data/src/hipe_vectors/hipe_vectors.erl b/lib/dialyzer/test/opaque_SUITE_data/src/hipe_vectors/hipe_vectors.erl
new file mode 100644
index 0000000000..279f244586
--- /dev/null
+++ b/lib/dialyzer/test/opaque_SUITE_data/src/hipe_vectors/hipe_vectors.erl
@@ -0,0 +1,136 @@
+%% -*- erlang-indent-level: 2 -*-
+%%
+%% %CopyrightBegin%
+%% 
+%% Copyright Ericsson AB 2001-2016. All Rights Reserved.
+%% 
+%% Licensed under the Apache License, Version 2.0 (the "License");
+%% you may not use this file except in compliance with the License.
+%% You may obtain a copy of the License at
+%%
+%%     http://www.apache.org/licenses/LICENSE-2.0
+%%
+%% Unless required by applicable law or agreed to in writing, software
+%% distributed under the License is distributed on an "AS IS" BASIS,
+%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+%% See the License for the specific language governing permissions and
+%% limitations under the License.
+%% 
+%% %CopyrightEnd%
+%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%%			  VECTORS IN ERLANG
+%%
+%% Abstract interface to vectors, indexed from 0 to size-1.
+
+-module(hipe_vectors).
+-export([new/2,
+	 set/3,
+	 get/2,
+	 size/1,
+	 vector_to_list/1,
+	 %% list_to_vector/1,
+	 list/1]).
+
+%%-define(USE_TUPLES, true).
+%%-define(USE_GBTREES, true).
+-define(USE_ARRAYS, true).
+
+-type vector() :: vector(_).
+-export_type([vector/0, vector/1]).
+
+-spec new(non_neg_integer(), V) -> vector(E) when V :: E.
+-spec set(vector(E), non_neg_integer(), V :: E) -> vector(E).
+-spec get(vector(E), non_neg_integer()) -> E.
+-spec size(vector(_)) -> non_neg_integer().
+-spec vector_to_list(vector(E)) -> [E].
+%% -spec list_to_vector([E]) -> vector(E).
+-spec list(vector(E)) -> [{non_neg_integer(), E}].
+
+%% ---------------------------------------------------------------------
+
+-ifdef(USE_TUPLES).
+-opaque vector(_) :: tuple().
+
+new(N, V) ->
+    erlang:make_tuple(N, V).
+
+size(V) -> erlang:tuple_size(V).
+
+list(Vec) ->
+    index(tuple_to_list(Vec), 0).
+
+index([X|Xs],N) ->
+    [{N,X} | index(Xs,N+1)];
+index([],_) ->
+    [].
+
+%% list_to_vector(Xs) ->
+%%     list_to_tuple(Xs).
+
+vector_to_list(V) ->
+    tuple_to_list(V).
+
+set(Vec, Ix, V) ->
+    setelement(Ix+1, Vec, V).
+
+get(Vec, Ix) -> element(Ix+1, Vec).
+
+-endif. %% ifdef USE_TUPLES
+
+%% ---------------------------------------------------------------------
+
+-ifdef(USE_GBTREES).
+-opaque vector(E) :: gb_trees:tree(non_neg_integer(), E).
+
+new(N, V) when is_integer(N), N >= 0 ->
+    gb_trees:from_orddict(mklist(N, V)).
+
+mklist(N, V) ->
+    mklist(0, N, V).
+
+mklist(M, N, V) when M < N ->
+    [{M, V} | mklist(M+1, N, V)];
+mklist(_, _, _) ->
+    [].
+
+size(V) -> gb_trees:size(V).
+
+list(Vec) ->
+    gb_trees:to_list(Vec).
+
+%% list_to_vector(Xs) ->
+%%     gb_trees:from_orddict(index(Xs, 0)).
+%% 
+%% index([X|Xs], N) ->
+%%     [{N, X} | index(Xs, N+1)];
+%% index([],_) ->
+%%     [].
+
+vector_to_list(V) ->
+    gb_trees:values(V).
+
+set(Vec, Ix, V) ->
+    gb_trees:update(Ix, V, Vec).
+
+get(Vec, Ix) ->
+    gb_trees:get(Ix, Vec).
+
+-endif. %% ifdef USE_GBTREES
+
+%% ---------------------------------------------------------------------
+
+-ifdef(USE_ARRAYS).
+-opaque vector(E) :: array:array(E).
+%%-type vector(E) :: array:array(E). % Work around dialyzer bug
+
+new(N, V) -> array:new(N, {default, V}).
+size(V) -> array:size(V).
+list(Vec) -> array:to_orddict(Vec).
+%% list_to_vector(Xs) -> array:from_list(Xs).
+vector_to_list(V) -> array:to_list(V).
+set(Vec, Ix, V) -> array:set(Ix, V, Vec).
+get(Vec, Ix) -> array:get(Ix, Vec).
+
+-endif. %% ifdef USE_ARRAYS
diff --git a/lib/hipe/cerl/erl_types.erl b/lib/hipe/cerl/erl_types.erl
index a6a7efb1de..9ef119ba46 100644
--- a/lib/hipe/cerl/erl_types.erl
+++ b/lib/hipe/cerl/erl_types.erl
@@ -611,9 +611,13 @@ t_decorate_with_opaque(T1, T2, Opaques) ->
         false -> T1;
         true ->
           R = decorate(T1, T, Opaques),
-          ?debug(case catch t_is_equal(t_unopaque(R), t_unopaque(T1)) of
-                   true -> ok;
-                   false ->
+          ?debug(case catch
+                        not t_is_equal(t_unopaque(R), t_unopaque(T1))
+                        orelse
+                        t_is_equal(T1, T) andalso not t_is_equal(T1, R)
+                 of
+                   false -> ok;
+                   _ ->
                      io:format("T1 = ~p,\n", [T1]),
                      io:format("T2 = ~p,\n", [T2]),
                      io:format("O = ~p,\n", [Opaques]),
@@ -642,7 +646,6 @@ decorate(?tuple_set(List), ?tuple_set(L), Opaques) ->
 decorate(?union(List), T, Opaques) when T =/= ?any ->
   ?union(L) = force_union(T),
   union_decorate(List, L, Opaques);
-decorate(?opaque(_)=T, _, _Opaques) -> T;
 decorate(T, ?union(L), Opaques) when T =/= ?any ->
   ?union(List) = force_union(T),
   union_decorate(List, L, Opaques);
@@ -656,7 +659,7 @@ decorate_with_opaque(Type, ?opaque(Set2), Opaques) ->
   case decoration(set_to_list(Set2), Type, Opaques, [], false) of
     {[], false} -> Type;
     {List, All} when List =/= [] ->
-      NewType = ?opaque(ordsets:from_list(List)),
+      NewType = sup_opaque(List),
       case All of
         true -> NewType;
         false -> t_sup(NewType, Type)
@@ -670,9 +673,10 @@ decoration([#opaque{struct = S} = Opaque|OpaqueTypes], Type, Opaques,
   case not IsOpaque orelse t_is_none(I) of
     true -> decoration(OpaqueTypes, Type, Opaques, NewOpaqueTypes0, All);
     false ->
-      NewOpaque = Opaque#opaque{struct = decorate(I, S, Opaques)},
+      NewI = decorate(I, S, Opaques),
+      NewOpaque = combine(NewI, [Opaque]),
       NewAll = All orelse t_is_equal(I, Type),
-      NewOpaqueTypes = [NewOpaque|NewOpaqueTypes0],
+      NewOpaqueTypes = NewOpaque ++ NewOpaqueTypes0,
       decoration(OpaqueTypes, Type, Opaques, NewOpaqueTypes, NewAll)
   end;
 decoration([], _Type, _Opaques, NewOpaqueTypes, All) ->
@@ -2991,27 +2995,21 @@ inf_collect(_T1, [], _Opaques, OpL) ->
   OpL.
 
 combine(S, T1, T2) ->
-  #opaque{mod = Mod1, name = Name1, args = Args1} = T1,
-  #opaque{mod = Mod2, name = Name2, args = Args2} = T2,
-  Comb1 = comb(Mod1, Name1, Args1, S, T1),
-  case is_compat_opaque_names({Mod1, Name1, Args1}, {Mod2, Name2, Args2}) of
-    true  -> Comb1;
-    false -> Comb1 ++ comb(Mod2, Name2, Args2, S, T2)
+  case is_compat_opaque_names(T1, T2) of
+    true ->  combine(S, [T1]);
+    false -> combine(S, [T1, T2])
   end.
 
-comb(Mod, Name, Args, S, T) ->
-  case can_combine_opaque_names(Mod, Name, Args, S) of
-    true ->
-      ?opaque(Set) = S,
-      Set;
-    false ->
-      [T#opaque{struct = S}]
-  end.
+combine(?opaque(Set), Ts) ->
+  [comb2(O, T) || O <- Set, T <- Ts];
+combine(S, Ts) ->
+  [T#opaque{struct = S} || T <- Ts].
 
-can_combine_opaque_names(Mod1, Name1, Args1,
-               ?opaque([#opaque{mod = Mod2, name = Name2, args = Args2}])) ->
-  is_compat_opaque_names({Mod1, Name1, Args1}, {Mod2, Name2, Args2});
-can_combine_opaque_names(_, _, _, _) -> false.
+comb2(O, T) ->
+  case is_compat_opaque_names(O, T) of
+    true -> O;
+    false -> T#opaque{struct = ?opaque(set_singleton(O))}
+  end.
 
 %% Combining two lists this way can be very time consuming...
 %% Note: two parameterized opaque types are not the same if their
@@ -3020,32 +3018,27 @@ inf_opaque(Set1, Set2, Opaques) ->
   List1 = inf_look_up(Set1, Opaques),
   List2 = inf_look_up(Set2, Opaques),
   List0 = [combine(Inf, T1, T2) ||
-            {Is1, ModNameArgs1, T1} <- List1,
-            {Is2, ModNameArgs2, T2} <- List2,
-            not t_is_none(Inf = inf_opaque_types(Is1, ModNameArgs1, T1,
-                                                 Is2, ModNameArgs2, T2,
-                                                 Opaques))],
-  List = lists:sort(lists:append(List0)),
+            {Is1, T1} <- List1,
+            {Is2, T2} <- List2,
+            not t_is_none(Inf = inf_opaque_types(Is1, T1, Is2, T2, Opaques))],
+  List = lists:append(List0),
   sup_opaque(List).
 
 %% Optimization: do just one lookup.
 inf_look_up(Set, Opaques) ->
-  [{Opaques =:= 'universe' orelse inf_is_opaque_type2(T, Opaques),
-    {M, N, Args}, T} ||
-    #opaque{mod = M, name = N, args = Args} = T <- set_to_list(Set)].
+  [{Opaques =:= 'universe' orelse inf_is_opaque_type2(T, Opaques), T} ||
+    T <- set_to_list(Set)].
 
 inf_is_opaque_type2(T, {match, Opaques}) ->
   is_opaque_type2(T, Opaques);
 inf_is_opaque_type2(T, Opaques) ->
   is_opaque_type2(T, Opaques).
 
-inf_opaque_types(IsOpaque1, ModNameArgs1, T1,
-                 IsOpaque2, ModNameArgs2, T2, Opaques) ->
+inf_opaque_types(IsOpaque1, T1, IsOpaque2, T2, Opaques) ->
   #opaque{struct = S1}=T1,
   #opaque{struct = S2}=T2,
   case
-    Opaques =:= 'universe' orelse
-    is_compat_opaque_names(ModNameArgs1, ModNameArgs2)
+    Opaques =:= 'universe' orelse is_compat_opaque_names(T1, T2)
   of
     true -> t_inf(S1, S2, Opaques);
     false ->
@@ -3059,10 +3052,15 @@ inf_opaque_types(IsOpaque1, ModNameArgs1, T1,
       end
   end.
 
-is_compat_opaque_names(ModNameArgs, ModNameArgs) -> true;
-is_compat_opaque_names({Mod,Name,Args1}, {Mod,Name,Args2}) ->
-  is_compat_args(Args1, Args2);
-is_compat_opaque_names(_, _) -> false.
+is_compat_opaque_names(Opaque1, Opaque2) ->
+  #opaque{mod = Mod1, name = Name1, args = Args1} = Opaque1,
+  #opaque{mod = Mod2, name = Name2, args = Args2} = Opaque2,
+  case {{Mod1, Name1, Args1}, {Mod2, Name2, Args2}} of
+    {ModNameArgs, ModNameArgs} -> true;
+    {{Mod, Name, Args1}, {Mod, Name, Args2}} ->
+      is_compat_args(Args1, Args2);
+    _ -> false
+  end.
 
 is_compat_args([A1|Args1], [A2|Args2]) ->
   is_compat_arg(A1, A2) andalso is_compat_args(Args1, Args2);