Testing gen_fsm – Part 6 ATG engine – Implementation


Finally, after all this thinking and all the discussing with ourselves, the moment of implementation is here. Of course, I have been writing this up during the ever so minimal spare time, and will present the final result for your pleasure, and also walk you through the interesting bits and pieces while commenting it. Enjoy!

Overview

The ATG machine consists of 2 application modules and 2 user-supplied modules

  • atg_parsetrans.erl
  • atg_machine.erl
  • test module
  • gen_fsm implementation module

The general idea is that the test module will include the atg_parsetrans as a parse transformation, and the state representation of the gen_fsm (often a record). The test module will then define a set of 3-tuples which act as a kind of Hoare-triples. The atg_machine is then used for using the test module-defined rules and auxiliary functions to randomly test sequences of transitions through the gen_fsm.

In detail – atg_parsetrans.erl

The atg_parsetrans module is the parse_transform library that your test-module should import (for your convenience).  atg_parsetrans will convert the kind-of Hoare Triples to an atg_machine friendly format. The transformation of your test module will then be roughly

  • Encase all expressions in fun’s
  • Store a string representation of the original expression, used for failure reports
  • Put the fun encased Expr and the String representation  into internal atg record
  • Drop the ‘$RULES’ tuple and replace with a list of all the records

The code follows

%%% @author Gianfranco <zenon@zen.home>
%%% @copyright (C) 2010, Gianfranco
%%% The Automated Test Generator (ATG) parse transformer
%%% Transforms the 3-tuples in the list as second elements of
%%% {'$RULES',[RULES]} into funs() -> RULE end, and creates accessors
%%% for state etc.
%%% Created : 20 Oct 2010 by Gianfranco <zenon@zen.home>
-module(atg_parsetrans).
-export([parse_transform/2]).

%% t(X)        = transformation of X
%% t('$ID')   => erlang:get('$ID')
%% t('$STATE')=> (fun......end)()
%% t('$PROGRAM_RESULT') => erlang:get('$PROGRAM_RESULT')
%% t({'$RULES',[RULE]})=> [t(R) || R <- [RULE]]
parse_transform([File,Module|Rest],_Options) ->
%% Transform with sneaked in rule_fun record
    transform([File,Module,abstr_rule_fun_record()|Rest]).

%% For inserting the used record into the file :)
abstr_rule_fun_record() ->
    {attribute,1,record,
      {rule_fun,
       [{record_field,1,{atom,1,function}},
        {record_field,1,{atom,1,string}}]}}.

%% All occurrences of '$STATE' must be replaced with this
%% call.
% ((fun() ->
%    {status,_,_,[_,_,_,_,Misc]} = sys:get_status(erlang:get('$ID')),
%    AllDatas = lists:flatten([ X || {data,X} <- Misc]),
%    proplists:get_value("StateData",AllData)
%  end)())
transform({atom,_Line,'$STATE'}) ->
    StrFunExp =
        "((fun() ->
            {status,_,_,[_,_,_,_,Misc]} = sys:get_status(erlang:get('$ID')),
            AllDatas = lists:flatten([ X || {data,X} <- Misc]),
            proplists:get_value(\"StateData\",AllDatas)
        end)()).",
    {ok,FunTkns,_} = erl_scan:string(StrFunExp),
    {ok,[FunForm]} = erl_parse:parse_exprs(FunTkns),
    FunForm;
%% All calls to use the other atoms acting as variables need to be changed to
%% proper erlang:get/1 from the process dictionary
transform({atom,_Line,'$PROGRAM_RESULT'}) ->
    StrFunExp = "erlang:get('$PROGRAM_RESULT').",
    {ok,FunTkns,_} = erl_scan:string(StrFunExp),
    {ok,[FunForm]} = erl_parse:parse_exprs(FunTkns),
    FunForm;
transform({atom,_Line,'$ID'}) ->
    StrFunExp = "erlang:get('$ID').",
    {ok,FunTkns,_} = erl_scan:string(StrFunExp),
    {ok,[FunForm]} = erl_parse:parse_exprs(FunTkns),
    FunForm;
transform({tuple,_,[{atom,_,'$RULES'},RuleList]}) ->
    rule_transform(RuleList);
transform(X) when is_tuple(X) ->
    list_to_tuple(lists:map(fun transform/1,tuple_to_list(X)));
transform(X) when is_list(X) ->
    lists:map(fun transform/1,X);
transform(X) -> X.

rule_transform({cons,L1,{tuple,L2,[A,B,C]},Rest}) ->
    {cons,L1,
     {tuple,L2,
      lists:map(
      fun({Expr,OrigExpr}) ->
              ExprStr   = erl_prettypr:format(Expr),
              OrigExprSt= erl_prettypr:format(OrigExpr),
              StructStr = "#rule_fun{function = fun()-> "++ExprStr++" end, "
                          "string = \""++OrigExprSt++"\"}.",
              {ok,Tkns,_} = erl_scan:string(StructStr),
              {ok,[Form]} = erl_parse:parse_exprs(Tkns),
              Form
      end,[{transform(A),A},{transform(B),B},{transform(C),C}])},
     rule_transform(Rest)};
rule_transform(X) -> X.


In order to fully understand this, the prerequisite knowledge is ‘The Abstract Format’. The key parts to know is that the entry-point of this module is the exported one (of course) and that it works on a list of abstract format terms. I then let each function clause of my transform/1 function take care of each specific thing that interests me.

transform({atom,_Line,'$STATE'}) ->
transform({atom,_Line,'$PROGRAM_RESULT'}) ->
transform({atom,_Line,'$ID'}) ->
transform({tuple,_,[{atom,_,'$RULES'},RuleList]}) ->

Besides this, the last three clauses work for traversing the Abstract Format

transform(X) when is_tuple(X) ->
    list_to_tuple(lists:map(fun transform/1,tuple_to_list(X)));
transform(X) when is_list(X) ->
    lists:map(fun transform/1,X);

and identity for let-through on the stuff that is not interesting.

transform(X) -> X.

Also, there is a specific function for traversing the list of 3-tuples holding the rules.  That function is interesting as it shows how I rewrite the code to be fun()-encapsulated and stringified. For this, I use erl_prettypr a very handy Abstract Form to String library, erl_scan the Erlang tokenizer (I hope you understand parsers and programming languages), and the erl_parse for generating replacement Abstract Form code.

Away we go

rule_transform({cons,L1,{tuple,L2,[A,B,C]},Rest}) ->
    {cons,L1,
     {tuple,L2,
      lists:map(
      fun({Expr,OrigExpr}) ->
              ExprStr   = erl_prettypr:format(Expr),
              OrigExprSt= erl_prettypr:format(OrigExpr),
              StructStr = "#rule_fun{function = fun()-> "++ExprStr++" end, "
                          "string = \""++OrigExprSt++"\"}.",
              {ok,Tkns,_} = erl_scan:string(StructStr),
              {ok,[Form]} = erl_parse:parse_exprs(Tkns),
              Form
      end,[{transform(A),A},{transform(B),B},{transform(C),C}])},
     rule_transform(Rest)};
rule_transform(X) -> X.

As can be seen, this function replaces each tuple element Expr with a #rule_fun record where the function field is bound to a fun encasing a parse-transformed version of the original Expr, and the string field is bound to the original un-parse-transformed Expr.

In detail – atg_machine.erl

The atg_machine is the whole .. yeah, machinery. Pumping through the different #rule_fun records, finding the matching ones, selecting one at random and executing.  The coarse steps of the atg_machine are

  • Check if end condition is met
  • Check if maximum iterations are met
  • Find matching set of accessible Rules
  • Pick one Rule at random from accessible rules
  • Execute the program of the picked Rule
  • Check postcondition of the picked Rule

One specially interesting thing is that if no rule can be applied before any endcondition is met, it will be considered a failure.

%%% @author Gianfranco <zenon@zen.home>
%%% @copyright (C) 2010, Gianfranco
%%% The Automated Test Generator (ATG) machinery, which handles
%%% rule execution and selecetion.
%%% Created : 20 Oct 2010 by Gianfranco <zenon@zen.home>
-module(atg_machine).
-export([run/3]).
-define(MAX_RUNS,100).

-record(rule_fun,{function :: fun() ,
               string   :: string() }).

-record(atg_triple,{pre  :: #rule_fun{},
                prog :: #rule_fun{},
                post :: #rule_fun{}}).

-record(atg_state,{remaining :: integer(),
               passed    :: integer(),
               log       :: [#atg_triple{}],
               state_log :: [any()],
               rules     :: [{#rule_fun{},#rule_fun{},#rule_fun{}}],
               stop_pred :: fun()}).

%------------------------------------------------------------------------------
-spec run([#rule_fun{}],fun(),fun()) -> ok | {error,any()} | true.
run(BaseSetOfRules, GenFsm_Setup,StopPred) ->
    case (catch GenFsm_Setup()) of
        {'EXIT',Reason} -> exit({setup,Reason});
        Result ->
            {A,B,C} = now(),
            random:seed(A,B,C),
            bind_to_id(Result),
            run_until(#atg_state{remaining = ?MAX_RUNS,
                                 passed    = 0,
                                 log       = [],
                                 state_log = [],
                                 rules     = BaseSetOfRules,
                                 stop_pred = StopPred})
    end.

%------------------------------------------------------------------------------
run_until(#atg_state{remaining=0}) -> report_success();
run_until(State) -> check_stopcondition(State).

check_stopcondition(#atg_state{stop_pred = StopPred} = State) ->
    case (catch StopPred()) of
        {'EXIT',Reason} -> exit({stop_predicate,Reason});
        true -> report_success();
        false -> check_hitset(State)
    end.

check_hitset(#atg_state{rules = RuleSet} = State) ->
    HitSet = [ X || X={P,_,_} <- RuleSet, (P#rule_fun.function)() ],
    case HitSet of
        [] -> exit({empty_hitset,fsm_state()});
        _ -> pick_rule(HitSet,State)
    end.

pick_rule(HitSet,State) ->
    {X,Y,Z} = lists:nth(random:uniform(length(HitSet)),HitSet),
    Triple = #atg_triple{pre=X, prog=Y, post=Z},
    use_rule(Triple,State).

use_rule(Triple = #atg_triple{prog=Y},State) ->
    io:format(".",[]),
    case (catch (Y#rule_fun.function)()) of
        {'EXIT',Reason} -> report_error(program,{Reason,Triple},State);
        Result ->
            bind_to_program_result(Result),
            test_postcondition(Triple,State)
    end.

test_postcondition(Triple = #atg_triple{post=Z},
                   #atg_state{remaining = Remaining,
                              passed = Passed,
                              log = Log,
                              state_log = SLog}=State) ->
    case (catch (Z#rule_fun.function)()) of
        {'EXIT',Reason} -> report_error(postcondition,{Reason,Triple},State);
        false-> report_error(postcondition,{postcondition_false,Triple},State);
        true -> run_until(State#atg_state{remaining=Remaining-1,
                                          passed=Passed+1,
                                          log=[Triple|Log],
                                          state_log=[fsm_state()|SLog]})
    end.

%------------------------------------------------------------------------------
bind_to_id(Value) -> erlang:put('$ID',Value).
bind_to_program_result(Value) -> erlang:put('$PROGRAM_RESULT',Value).    

report_success() ->
    io:format("~n~n*** Automated Testing Successfull ***~n~n",[]),
    ok.

report_error(Phase,{Cause,Triple},#atg_state{passed=Passed,
                                             log=Log,
                                             state_log=SLog}) ->
    io:format("~n~n*** ERROR: Automated Testing Failure ***~n"
              " Failed after: ~p ~n"
              " Failure phase: ~p~n"
              " Cause: ~p~n"
              " Rule: ~p~n"
              " State: ~p~n"
              " Log: ~p~n"
              " States: ~p~n"
              " $ID: ~p~n"
              " $PROGRAM_RESULT: ~p~n",
              [Passed,Phase,Cause,triple_to_str(Triple),
               fsm_state(),[triple_to_str(T) || T <- Log],SLog,
               erlang:get('$ID'),
               erlang:get('$PROGRAM_RESULT')]),
    % Kill the gen_fsm?
    exit(erlang:get('$ID'),kill),
    {error,Cause}.

fsm_state() ->
    ((fun() ->
              {status,_,_,[_,_,_,_,Misc]} = sys:get_status(erlang:get('$ID')),
              AllDatas = lists:flatten([ X || {data,X} <- Misc]),
              proplists:get_value("StateData",AllDatas)
      end)()).   

triple_to_str(#atg_triple{pre=#rule_fun{string=PreStr},
                          prog=#rule_fun{string=ProgStr},
                          post=#rule_fun{string=PostStr}}) ->
    {PreStr,ProgStr,PostStr}.

Some interesting things to discuss could be that this machinery does not need parse_transforming and never needs to know the internal format of the gen_fsm. So, it’s gen_fsm implementation agnostic. It will run until the first thing happens of [condition failure, end condition success, 100 iterations passed].

Other than that, I believe the code is fairly self explanatory. Of course, be welcome to ask in the comments.

A test module

A user supplied test module (call it what you want, for example: demo.erl) should define that parse-transformation is to be done with the atg_parsetrans module.

-compile({parse_transform, atg_parsetrans}).

The test module must also define the internally used state record of the gen_fsm if such a record is used and it will be very handy if the following functions are exported from the test module

-export([rules/0,is_done/0,start/0]).

why are these functions so handy, and what should they contain?

The rules() function is an obvious way to pass the Rule-list to the machinery, thus, this function is defined to return {‘$RULES’,  [....]} where the dots ‘.’ in the list are the 3-tuples. Something like this

rules() ->
  {'$RULES',
    [
     { not reg(seller), do_reg(seller), reg(seller,'$PROGRAM_RESULT')},
     { not reg(buyer), do_reg(buyer),reg(buyer,'$PROGRAM_RESULT')}
    ]}.

The is_done/0 function will serve as the end predicate for the machinery, so it will know when it’s “done”, can be set to return false if MAX_ITERATIONS of tests are wanted.
Example could be

is_done() -> '$STATE'#state.deal_done == true.

And the final export start/0 will serve as the function that return the value that will be bound for the gen_fsm accessing.
Example

start() ->
    {ok,Pid} = tradepost:start_link(),
    Pid.

Thus, we understand, that the majority of the work lies in writing the rules/0 function and all the 3-tuples defining the rules. The programmer will have to tip in some extra work into the predicates.  Now for the example test module.

Usage examples

My own test module (demo.erl) will be posted below, together with the success output and some error examples when we do some bad modifications to the tradepost.erl code.
First the demo.erl code

-module(demo).
-export([rules/0,is_done/0,start/0]).
-compile({parse_transform, atg_parsetrans}).

%% Must be included for gen_fsm
-record(state,{item,cash,seller,buyer,seller_accept,buyer_accept,deal_done}).

start() ->
    {ok,Pid} = tradepost:start_link(),
    Pid.

% ------------------------------------------------------------------------------
% List of all rules - mock code!
% ------------------------------------------------------------------------------
rules() ->
    {'$RULES',
     [
      % Seller and buyer registration,
      { not reg(seller), do_reg(seller), reg(seller,'$PROGRAM_RESULT')},
      { not reg(buyer),  do_reg(buyer),  reg(buyer,'$PROGRAM_RESULT')},
      { reg(seller), insert(item), item_is('$PROGRAM_RESULT')},
      { reg(buyer),  insert(cash),  cash_is('$PROGRAM_RESULT')},
      { tradepost_has(cash), remove(cash), not tradepost_has(cash) },
      { tradepost_has(item), remove(item), not tradepost_has(item) },
      { tradepost_has(cash) andalso
        tradepost_has(item), closedeal(), return_value_is([item,100])}
     ]
    }.

% Deal is done when deal_done is true
is_done() -> '$STATE'#state.deal_done == true.

reg(seller) -> '$STATE'#state.seller =/= undefined;
reg(buyer) ->  '$STATE'#state.buyer =/= undefined.

reg(seller,Passwd) -> '$STATE'#state.seller == Passwd;
reg(buyer,Passwd) -> '$STATE'#state.buyer == Passwd.

% The identifier of the gen_fsm is accessed through '$ID'
do_reg(buyer) ->
    Password = generate_passwd(buyer),
    tradepost:buyer_identify('$ID',Password),
    Password;
do_reg(seller) ->
    Password = generate_passwd(seller),
    tradepost:seller_identify('$ID',Password),
    Password. % This line ensures that '$PROGRAM_RESULT' is bound to
              % the generated password, for the Postcondition to access.

insert(item) ->
    Password = '$STATE'#state.seller,
    Item = generate_item(),
    tradepost:seller_insert('$ID',Item,Password),
    Item; % Ensure '$PROGRAM_RESULT is Item
insert(cash) ->
    Password = '$STATE'#state.buyer,
    Cash = generate_cash(),
    tradepost:buyer_insert('$ID',Cash,Password),
    Cash. % Ensure '$PROGRAM_RESULT is Cash

% Check that item is the specified item (argument).
item_is(GivenItem) -> '$STATE'#state.item == GivenItem.

% Check that cash is specified amount (argument)
cash_is(GivenAmount) -> '$STATE'#state.cash == GivenAmount.

% Testing state to contain cash xor item
tradepost_has(cash) -> '$STATE'#state.cash =/= undefined;
tradepost_has(item) -> '$STATE'#state.item =/= undefined.

remove(cash) ->
    Passwd = '$STATE'#state.buyer,
    tradepost:buyer_withdraw('$ID',Passwd);
remove(item) ->
    Passwd = '$STATE'#state.seller,
    tradepost:seller_withdraw('$ID',Passwd).

% Deal closing, is a parallelized action.
% therefore I have to bind the value of '$ID' to the atom '$ID' in the
% new process without writing '$ID' as an atom when doing so! o<:D
closedeal() ->
    ID   = '$ID',
    Self = self(),
    spawn_link(fun() ->
                       erlang:put(list_to_atom("$ID"),ID),
                       Passwd = '$STATE'#state.buyer,
                       ItemAndCash = tradepost:get_contents('$ID',Passwd),
                       Self ! tradepost:buyer_deal('$ID',Passwd,ItemAndCash)
               end),
    spawn_link(fun() ->
                       erlang:put(list_to_atom("$ID"),ID),
                       Passwd = '$STATE'#state.seller,
                       ItemAndCash = tradepost:get_contents('$ID',Passwd),
                       Self ! tradepost:seller_deal('$ID',Passwd,ItemAndCash)
               end),
    [receive X -> X end,receive Y -> Y end].                            

return_value_is(X)-> lists:sort(X) == lists:sort('$PROGRAM_RESULT').

generate_passwd(buyer) -> buyer;
generate_passwd(seller) -> seller.

generate_item() -> item.
generate_cash() -> 100.

There, this is the test module I have for the tradepost.erl module, and here comes the compilation and running. I have already compile atg_parsetrans and atg_machine to ebin/ and therefore add ebin/ to the path when compiling demo.erl

zen:EUnitFSM zenon$ erlc -o ebin/ src/demo.erl -pa ebin/
zen:EUnitFSM zenon$ erl -pa ebin/
Erlang R13B04 (erts-5.7.5) [source] [64-bit] [smp:4:4] [rq:4]
[async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.7.5  (abort with ^G)
1> atg_machine:run(demo:rules(),fun demo:start/0, fun demo:is_done/0).
...........

*** Automated Testing Successfull ***

ok
2>

The 11 dots seen show that 11 cycles where run before the is_done/0 predicate returned true. Now, if we wish to see some errors, let’s make a small modification (that actually was a bug I discovered thanks to my own tool) in tradepost.erl

On line 118, change the last don’t care to undefined.

{cash_received,item,Pwd,_,_,_} -> {ok, cash_received, undef(item,LoopD)};

like this, and save + recompile

{cash_received,item,Pwd,_,_,undefined} -> {ok, cash_received, undef(item,LoopD)};

now, running should produce the nice error output format

16> atg_machine:run(demo:rules(),fun demo:start/0, fun demo:is_done/0).
........

*** ERROR: Automated Testing Failure ***
 Failed after: 7
 Failure phase: postcondition
 Cause: postcondition_false
 Rule: {"tradepost_has(item)","remove(item)","not tradepost_has(item)"}
 State: {state,item,100,seller,buyer,undefined,undefined,false}
 Log: [{"reg(buyer)","insert(cash)","cash_is('$PROGRAM_RESULT')"},
       {"tradepost_has(cash)","remove(cash)","not tradepost_has(cash)"},
       {"reg(buyer)","insert(cash)","cash_is('$PROGRAM_RESULT')"},
       {"reg(seller)","insert(item)","item_is('$PROGRAM_RESULT')"},
       {"not reg(buyer)","do_reg(buyer)","reg(buyer, '$PROGRAM_RESULT')"},
       {"reg(seller)","insert(item)","item_is('$PROGRAM_RESULT')"},
       {"not reg(seller)","do_reg(seller)","reg(seller, '$PROGRAM_RESULT')"}]
 States: [{state,item,100,seller,buyer,undefined,undefined,false},
          {state,item,undefined,seller,buyer,undefined,undefined,false},
          {state,item,100,seller,buyer,undefined,undefined,false},
          {state,item,undefined,seller,buyer,undefined,undefined,false},
          {state,item,undefined,seller,buyer,undefined,undefined,false},
          {state,item,undefined,seller,undefined,undefined,undefined,false},
          {state,undefined,undefined,seller,undefined,undefined,undefined,
                 false}]
 $ID: <0.88.0>
 $PROGRAM_RESULT: error
** exception exit: killed
17>

Now, first of, the 8 dots say that 8 cycles where performed, and the Error output says that we failed on the 8th cycle, that is, after 7 completed. The phase of the error was the postcondition of the selected rule. The selected rule is shown on the “Rule:” line. The current state in which we failed is shown after “State:”.

The “Log:” shows a list of all the processed and passed rules, most recent nearest the top of the screen. This is also true for the “States:” output, which serves as a log for us. The internal process dictionary bindings for ‘$ID’ and ‘$PROGRAM_RESULT’ are also shown.
In short, almost everything we need for debugging is here.

Now for a really terrifyingly delicious comment! I had to run this several (6 times) before this error was shown.

Why? Because the testing is randomised. And some of the corner cases will thus not be triggered easily during short runs.  Let us undo the faulty change and introduce an easier one into the program. Let’s forget that buyer inserts cash and not item. (Line 42, change cash  to item : and recompile!)

4> atg_machine:run(demo:rules(),fun demo:start/0, fun demo:is_done/0).
...

*** ERROR: Automated Testing Failure ***
 Failed after: 2
 Failure phase: postcondition
 Cause: postcondition_false
 Rule: {"reg(buyer)","insert(cash)","cash_is('$PROGRAM_RESULT')"}
 State: {state,undefined,undefined,seller,buyer,undefined,undefined,false}
 Log: [{"not reg(buyer)","do_reg(buyer)","reg(buyer, '$PROGRAM_RESULT')"},
       {"not reg(seller)","do_reg(seller)","reg(seller, '$PROGRAM_RESULT')"}]
 States: [{state,undefined,undefined,seller,buyer,undefined,undefined,false},
          {state,undefined,undefined,seller,undefined,undefined,undefined,
                 false}]
 $ID: <0.43.0>
 $PROGRAM_RESULT: 100
** exception exit: killed
5>

Bam! Reading the error reason, it becomes apparent that something is not working in the cash insertion! the cash in the state does not match ‘$PROGRAM_RESULT’ which was 100! Looking at the State, it’s undefined. Bummer! :)

This was the final part of the home-written ATG, I will presumably put in on git if the demand is high enough.

Cheers

/G

About these ads
Leave a comment

1 Comment

  1. Thanks for the great article. Got some solid pieces of missing information for my code before releasing it into production. Your article is very much appreciated.

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: