← Back to branch summary

~ubuntu-branches/ubuntu/karmic/erlang/karmic

« back to all changes in this revision

Viewing changes to lib/dialyzer/src/dialyzer_dep.erl

  • Committer: Bazaar Package Importer
  • Author(s): Sergei Golovan
  • Date: 2009-05-01 10:14:38 UTC
  • mfrom: (3.1.4 sid)
  • Revision ID: james.westby@ubuntu.com-20090501101438-6qlr6rsdxgyzrg2z
Tags: 1:13.b-dfsg-2
* Cleaned up patches: removed unneeded patch which helped to support
  different SCTP library versions, made sure that changes for m68k
  architecture applied only when building on this architecture.
* Removed duplicated information from binary packages descriptions.
* Don't require libsctp-dev build-dependency on solaris-i386 architecture
  which allows to build Erlang on Nexenta (thanks to Tim Spriggs for
  the suggestion).

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/dialyzer/src/dialyzer_dep.erl
1
1
%% -*- erlang-indent-level: 2 -*-
2
2
%%-----------------------------------------------------------------------
3
 
%% ``The contents of this file are subject to the Erlang Public License,
 
3
%% %CopyrightBegin%
 
4
%% 
 
5
%% Copyright Ericsson AB 2006-2009. All Rights Reserved.
 
6
%% 
 
7
%% The contents of this file are subject to the Erlang Public License,
4
8
%% Version 1.1, (the "License"); you may not use this file except in
5
9
%% compliance with the License. You should have received a copy of the
6
10
%% Erlang Public License along with this software. If not, it can be
7
 
%% retrieved via the world wide web at http://www.erlang.org/.
 
11
%% retrieved online at http://www.erlang.org/.
8
12
%% 
9
13
%% Software distributed under the License is distributed on an "AS IS"
10
14
%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
11
15
%% the License for the specific language governing rights and limitations
12
16
%% under the License.
13
17
%% 
14
 
%% Copyright 2006, 2007 Tobias Lindahl and Kostis Sagonas
15
 
%% 
16
 
%% $Id$
 
18
%% %CopyrightEnd%
17
19
%%
18
20
 
19
21
%%%-------------------------------------------------------------------
38
40
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
39
41
%%
40
42
%% analyze(CoreTree) -> {Deps, Esc, Calls}.
41
 
%%                
 
43
%%
42
44
%% Deps =  a dict mapping labels of functions to an ordset of functions
43
45
%%         it calls.
44
46
%%
47
49
%%         i.e., this analysis is not module-local but rather
48
50
%%         function-local.
49
51
%%
50
 
%% Calls = a dict mapping apply:s to a ordset of function labels to which
51
 
%%         the operation can refer to. If 'external' is part of the
52
 
%%         set the operation can be externally defined.
 
52
%% Calls = a dict mapping apply:s to an ordset of function labels to
 
53
%%         which the operation can refer to. If 'external' is part of
 
54
%%         the set the operation can be externally defined.
53
55
%%
54
56
 
55
 
-spec analyze(core_module()) -> {dict(), [_], dict()}.
 
57
-spec analyze(core_module()) -> {dict(), ['external' | label()], dict()}.
56
58
 
57
59
analyze(Tree) ->
58
60
  %% io:format("Handling ~w\n", [cerl:atom_val(cerl:module_name(Tree))]),
107
109
      %%io:format("Entering fun: ~w\n", [cerl_trees:get_label(Tree)]),
108
110
      Body = cerl:fun_body(Tree),
109
111
      Label = cerl_trees:get_label(Tree),
110
 
      if CurrentFun =:= top -> 
111
 
          State1 = state__add_deps(top, output(set__singleton(Label)), State);
112
 
         true -> 
113
 
          O1 = output(set__singleton(CurrentFun)),
114
 
          O2 = output(set__singleton(Label)),
115
 
          TmpState = state__add_deps(Label, O1, State),
116
 
          State1 = state__add_deps(CurrentFun, O2,TmpState)
117
 
      end,
 
112
      State1 =
 
113
        if CurrentFun =:= top -> 
 
114
            state__add_deps(top, output(set__singleton(Label)), State);
 
115
           true -> 
 
116
            O1 = output(set__singleton(CurrentFun)),
 
117
            O2 = output(set__singleton(Label)),
 
118
            TmpState = state__add_deps(Label, O1, State),
 
119
            state__add_deps(CurrentFun, O2,TmpState)
 
120
        end,
118
121
      {BodyFuns, State2} = traverse(Body, Out, State1, 
119
122
                                    cerl_trees:get_label(Tree)),
120
123
      {output(set__singleton(Label)), state__add_esc(BodyFuns, State2)};
284
287
    false -> {ArgFuns, State1}
285
288
  end.
286
289
 
287
 
%%____________________________________________________________
288
 
%%
 
290
%%------------------------------------------------------------
289
291
%% Set
290
292
%%
291
293
 
292
294
-record(set, {set :: set()}).
293
295
 
294
296
set__singleton(Val) ->
295
 
  #set{set=sets:add_element(Val, sets:new())}.
 
297
  #set{set = sets:add_element(Val, sets:new())}.
296
298
 
297
299
set__from_list(List) ->
298
 
  #set{set=sets:from_list(List)}.
 
300
  #set{set = sets:from_list(List)}.
299
301
 
300
302
set__is_element(_El, none) ->
301
303
  false;
302
 
set__is_element(El, #set{set=Set}) ->
 
304
set__is_element(El, #set{set = Set}) ->
303
305
  sets:is_element(El, Set).
304
306
 
305
 
set__union(none, X) -> X;
306
 
set__union(X, none) -> X;
307
 
set__union(#set{set=X}, #set{set=Y}) -> #set{set=sets:union(X, Y)}.
 
307
set__union(none, Set) -> Set;
 
308
set__union(Set, none) -> Set;
 
309
set__union(#set{set = S1}, #set{set = S2}) -> #set{set = sets:union(S1, S2)}.
308
310
 
309
311
set__to_ordsets(none) -> [];
310
 
set__to_ordsets(#set{set=Set}) -> ordsets:from_list(sets:to_list(Set)).
 
312
set__to_ordsets(#set{set = Set}) -> ordsets:from_list(sets:to_list(Set)).
311
313
 
312
314
set__size(none) -> 0;
313
 
set__size(#set{set=X}) -> sets:size(X).
 
315
set__size(#set{set = Set}) -> sets:size(Set).
314
316
 
315
 
set__filter(#set{set=X}, Fun) -> 
316
 
  NewSet = sets:filter(Fun, X),
 
317
set__filter(#set{set = Set}, Fun) ->
 
318
  NewSet = sets:filter(Fun, Set),
317
319
  case sets:size(NewSet) =:= 0 of
318
320
    true -> none;
319
 
    false -> #set{set=NewSet}
 
321
    false -> #set{set = NewSet}
320
322
  end.
321
 
       
322
323
 
323
 
%%____________________________________________________________
324
 
%%
 
324
%%------------------------------------------------------------
325
325
%% Outputs
326
326
%%
327
327
 
328
328
-record(output, {type    :: 'single' | 'list', 
329
329
                 content :: 'none' | #set{} | [{output,_,_}]}).
330
330
 
331
 
output(none) -> #output{type=single, content=none};
332
 
output(S = #set{}) -> #output{type=single, content=S};
333
 
output(List) when is_list(List) -> #output{type=list, content=List}.
 
331
output(none) -> #output{type = single, content = none};
 
332
output(S = #set{}) -> #output{type = single, content = S};
 
333
output(List) when is_list(List) -> #output{type = list, content = List}.
334
334
 
335
335
merge_outs([H|T]) ->
336
336
  merge_outs(T, H);
337
 
merge_outs(#output{type=list, content=[H|T]}) ->
 
337
merge_outs(#output{type = list, content = [H|T]}) ->
338
338
  merge_outs(T, H);
339
 
merge_outs(#output{type=list, content=[]}) ->
 
339
merge_outs(#output{type = list, content = []}) ->
340
340
  output(none).
341
341
 
342
 
merge_outs([#output{content=none}|Left], O) ->
343
 
  merge_outs(Left, O);
344
 
merge_outs([O|Left], #output{content=none}) ->
345
 
  merge_outs(Left, O);
346
 
merge_outs([#output{type=single, content=S1}|Left], 
347
 
           #output{type=single, content=S2}) ->
 
342
merge_outs([#output{content = none}|Left], O) ->
 
343
  merge_outs(Left, O);
 
344
merge_outs([O|Left], #output{content = none}) ->
 
345
  merge_outs(Left, O);
 
346
merge_outs([#output{type = single, content = S1}|Left], 
 
347
           #output{type = single, content = S2}) ->
348
348
  merge_outs(Left, output(set__union(S1, S2)));
349
 
merge_outs([#output{type=list, content=L1}|Left],
350
 
           #output{type=list, content=L2}) ->
 
349
merge_outs([#output{type = list, content = L1}|Left],
 
350
           #output{type = list, content = L2}) ->
351
351
  NewList = [merge_outs([X, Y]) || {X, Y} <- lists:zip(L1, L2)],
352
352
  merge_outs(Left, output(NewList));
353
353
merge_outs([], Res) ->
354
354
  Res.
355
355
 
356
 
filter_outs(#output{type=single, content=S}, Fun) -> 
 
356
filter_outs(#output{type = single, content = S}, Fun) -> 
357
357
  output(set__filter(S, Fun)).
358
358
 
359
 
add_external(#output{type=single, content=Set}) ->
 
359
add_external(#output{type = single, content = Set}) ->
360
360
  output(set__union(Set, set__singleton(external)));
361
 
add_external(#output{type=list, content=List}) ->
 
361
add_external(#output{type = list, content = List}) ->
362
362
  output([add_external(O) || O <- List]).
363
363
 
364
 
is_only_external(#output{type=single, content=Set}) ->
 
364
is_only_external(#output{type = single, content = Set}) ->
365
365
  set__is_element(external, Set) andalso (set__size(Set) =:= 1).
366
366
 
367
 
%%____________________________________________________________
368
 
%%
 
367
%%------------------------------------------------------------
369
368
%% Map
370
369
%%
371
370
 
393
392
  end.
394
393
 
395
394
map__finalize(Map) ->
396
 
  dict:map(fun(_Key, Set = #set{}) -> set__to_ordsets(Set);
397
 
              (_Key, #output{type=single, content=Set}) -> set__to_ordsets(Set)
 
395
  dict:map(fun (_Key, #set{} = Set) -> set__to_ordsets(Set);
 
396
               (_Key, #output{type = single, content = Set}) ->
 
397
                   set__to_ordsets(Set)
398
398
           end, Map).
399
399
 
400
 
%%____________________________________________________________
401
 
%%
 
400
%%------------------------------------------------------------
402
401
%% Binding outs in the map
403
402
%%
404
403
 
405
 
bind_pats_list(_Pats, #output{content=none}, Map) ->
 
404
bind_pats_list(_Pats, #output{content = none}, Map) ->
406
405
  Map;
407
 
bind_pats_list([Pat], O = #output{type=single}, Map) ->
 
406
bind_pats_list([Pat], #output{type = single} = O, Map) ->
408
407
  bind_single(all_vars(Pat), O, Map);
409
 
bind_pats_list(Pats, #output{type=list, content=List}, Map) ->
 
408
bind_pats_list(Pats, #output{type = list, content = List}, Map) ->
410
409
  bind_pats_list(Pats, List, Map);
411
410
bind_pats_list([Pat|PatLeft],
412
 
               [O = #output{type=single}|SetLeft], Map)->
 
411
               [#output{type = single} = O|SetLeft], Map)->
413
412
  Map1 = bind_single(all_vars(Pat), O, Map),
414
413
  bind_pats_list(PatLeft, SetLeft, Map1);
415
414
bind_pats_list([Pat|PatLeft],
416
 
               [#output{type=list, content=List}|SetLeft], Map)->
417
 
  case cerl:is_c_values(Pat) of
418
 
    true -> Map1 = bind_pats_list(cerl:values_es(Pat), List, Map);
419
 
    false -> Map1 = bind_single(all_vars(Pat), merge_outs(List), Map)
420
 
  end,
 
415
               [#output{type = list, content = List}|SetLeft], Map) ->
 
416
  Map1 = case cerl:is_c_values(Pat) of
 
417
           true -> bind_pats_list(cerl:values_es(Pat), List, Map);
 
418
           false -> bind_single(all_vars(Pat), merge_outs(List), Map)
 
419
         end,
421
420
  bind_pats_list(PatLeft, SetLeft, Map1);
422
421
bind_pats_list([], [], Map) ->
423
422
  Map.
427
426
bind_single([], _O, Map) ->
428
427
  Map.
429
428
 
430
 
bind_list(List, O = #output{type=single}, Map) ->
 
429
bind_list(List, #output{type = single} = O, Map) ->
431
430
  bind_single(List, O, Map);
432
 
bind_list(List1, #output{type=list, content=List2}, Map) ->
 
431
bind_list(List1, #output{type = list, content = List2}, Map) ->
433
432
  bind_list1(List1, List2, Map).
434
433
 
435
434
bind_list1([Var|VarLeft], [O|OLeft], Map) ->
455
454
                      end
456
455
                  end, AccIn, Tree).
457
456
 
458
 
%%____________________________________________________________
459
 
%%
 
457
%%------------------------------------------------------------
460
458
%% The state
 
459
%%
461
460
 
462
461
-type local_set() :: 'none' | #set{}.
463
462
 
472
471
                            || {Var, Fun} <- cerl:module_defs(Tree),
473
472
                               set__is_element(Var, Exports)]),
474
473
  Arities = cerl_trees:fold(fun find_arities/2, dict:new(), Tree),
475
 
  #state{deps=map__new(), esc=InitEsc, call=map__new(), arities=Arities}.
 
474
  #state{deps = map__new(), esc = InitEsc, call = map__new(), arities = Arities}.
476
475
 
477
476
find_arities(Tree, AccMap) ->
478
477
  case cerl:is_c_fun(Tree) of
484
483
      AccMap
485
484
  end.
486
485
 
487
 
state__add_deps(_From, #output{content=none}, State) ->
 
486
state__add_deps(_From, #output{content = none}, State) ->
488
487
  State;
489
 
state__add_deps(From, #output{type=single, content=To}, 
490
 
                State = #state{deps=Map}) ->
491
 
  %%io:format("Adding deps from ~w to ~w\n", [From, set__to_ordsets(To)]),
492
 
  State#state{deps=map__add(From, To, Map)}.
 
488
state__add_deps(From, #output{type = single, content=To}, 
 
489
                #state{deps = Map} = State) ->
 
490
  %% io:format("Adding deps from ~w to ~w\n", [From, set__to_ordsets(To)]),
 
491
  State#state{deps = map__add(From, To, Map)}.
493
492
 
494
 
state__deps(#state{deps=Deps}) ->
 
493
state__deps(#state{deps = Deps}) ->
495
494
  Deps.
496
495
 
497
 
state__add_esc(#output{content=none}, State) ->
 
496
state__add_esc(#output{content = none}, State) ->
498
497
  State;
499
 
state__add_esc(#output{type=single, content=Set}, State = #state{esc=Esc}) ->
500
 
  State#state{esc=set__union(Set, Esc)}.
 
498
state__add_esc(#output{type = single, content = Set},
 
499
               #state{esc = Esc} = State) ->
 
500
  State#state{esc = set__union(Set, Esc)}.
501
501
 
502
 
state__esc(#state{esc=Esc}) ->
 
502
state__esc(#state{esc = Esc}) ->
503
503
  Esc.
504
504
 
505
 
state__store_callsite(_From, #output{content=none}, _CallArity, State) ->
 
505
state__store_callsite(_From, #output{content = none}, _CallArity, State) ->
506
506
  State;
507
507
state__store_callsite(From, To, CallArity, 
508
 
                      State = #state{call=Calls, arities=Arities}) ->
 
508
                      #state{call = Calls, arities = Arities} = State) ->
509
509
  Filter = fun(external) -> true;
510
510
              (Fun) -> CallArity =:= dict:fetch(Fun, Arities) 
511
511
           end,
512
512
  case filter_outs(To, Filter) of
513
 
    #output{content=none} -> State;
514
 
    To1 -> State#state{call=map__store(From, To1, Calls)}
 
513
    #output{content = none} -> State;
 
514
    To1 -> State#state{call = map__store(From, To1, Calls)}
515
515
  end.
516
516
 
517
 
state__calls(#state{call=Calls}) ->
 
517
state__calls(#state{call = Calls}) ->
518
518
  Calls.
519
519
 
520
 
%%____________________________________________________________
521
 
%%
 
520
%%------------------------------------------------------------
522
521
%% A test function. Not part of the intended interface.
523
522
%%
524
523
 
525
524
-ifndef(NO_UNUSED).
526
525
 
527
526
test(Mod) ->
528
 
  {ok, _, Code} = compile:file(Mod, [to_core,binary]), 
 
527
  {ok, _, Code} = compile:file(Mod, [to_core, binary]), 
529
528
  Tree = cerl:from_records(Code),
530
529
  {LabeledTree, _} = cerl_trees:label(Tree),
531
 
 
532
 
  %%io:put_chars(cerl_prettypr:format(LabeledTree)),
533
 
  %%io:nl(),
534
 
 
535
530
  {Deps, Esc, Calls} = analyze(LabeledTree),
536
531
  Edges0 = dict:fold(fun(Caller, Set, Acc) ->
537
532
                         [[{Caller, Callee} || Callee <- Set]|Acc]
572
567
  NamedEsc = [dict:fetch(X, NameMap) || X <- Esc],
573
568
  %% Color the edges
574
569
  ColorEsc = [{X, {color, red}} || X <- NamedEsc],
575
 
 
576
570
  CallEdges0 = dict:fold(fun(Caller, Set, Acc) ->
577
571
                             [[{Caller, Callee} || Callee <- Set]|Acc]
578
572
                         end, [], Calls),
579
573
  CallEdges = lists:flatten(CallEdges0),
580
574
  NamedCallEdges = [{X, dict:fetch(Y, NameMap)} || {X, Y} <- CallEdges],
581
 
 
582
 
  hipe_dot:translate_list(NamedEdges ++ NamedCallEdges, "/tmp/cg.dot", "CG", 
583
 
                          ColorEsc),
 
575
  AllNamedEdges = NamedEdges ++ NamedCallEdges,
 
576
  hipe_dot:translate_list(AllNamedEdges, "/tmp/cg.dot", "CG", ColorEsc),
584
577
  os:cmd("dot -T ps -o /tmp/cg.ps /tmp/cg.dot"),
585
 
 
586
578
  ok.
587
579
 
588
580
-endif.