Searching the abstract form in erlang

[update: I've added the head matching version of the check funs as per the recommendations in the comments. Thanks Hynek!]

I imagine there’s a much better way to do this, but in the process of writing another parse_transform hack I wanted to search for specific things within the abstract form of a module which looks something like this:

[{attribute,1,file,{"./test2.erl",1}},
 {attribute,1,module,test2},
 {attribute,2,export,[{append,2},{prepend,2}]},
 {attribute,3,compile,[]},
 {attribute,6,after_exec,{[prepend,append],to_a_atom}},
 {function,8,before_prepend_to_a_atom,2,
     [{clause,8,
          [{var,8,'S1'},{var,8,'S2'}],
          [],
          [{op,9,'++',{var,9,'S1'},{var,9,'S2'}}]}]},
 {function,11,before_append_to_a_atom,2,
     [{clause,11,
          [{var,11,'S1'},{var,11,'S2'}],
          [],
          [{match,12,
               {var,12,'Fun'},
               {'fun',12,
                   {clauses,
                       [{clause,12,...

It's a bunch of recursive lists, tuples, atoms, etc. Which means you should be able to write a simple function to dive through it and find something like an atom or number, but what if you want to match a tuple where the third item is the value "Fred"?

Here's the hack I came up with this evening:

-module(util).

-export([find/2]). 

-define(call_check, fun({call,_,{atom,_,Name},_}) -> true;
                       (_) -> false
                    end).

-define(function_check, fun({_, _, Name, _, _}) -> true;
                           (_) -> false
                        end).
find(Form, CompareFun) ->
    find(Form, CompareFun, []). 

find(Form, CompareFun, Acc) when is_tuple(Form) ->
    case CompareFun(Form) of
        true -> Acc ++ [Form];
        _ -> find(tuple_to_list(Form), CompareFun, Acc)
    end;

find(Form, CompareFun, Acc) when is_list(Form) ->
    case CompareFun(Form) of
        true -> Acc ++ Form;
        _ -> Acc ++ [Y || X <- Form, Y <- find(X, CompareFun, Acc), Y =/= []]
    end;

find(Form, CompareFun, Acc) ->
    case CompareFun(Form) of
        true -> Acc ++ [Form];
        _ -> Acc
    end.

Its fairly easy to follow how the 3 clauses of find/3 work

• First Clause: If Form is a tuple check it with the comparison function. If the comparison function returns true add it to the accumulator and return the accumulator. If not convert it to a list and call find.
• Second Clause: If Form is a list check it with the comparison function. If the comparison function returns true add it to the accumulator and return the accumulator. If not call find on each of the elements of the list.
• Third Clause: If Form is anything else it can’t contain something so we simply check it with the comparison function, and add it to the accumulator if it matches otherwise return the current value of the accumulator.

The funs defined at the top as macros are the matching functions. They have to be custom built for whatever you’re looking for, and the variables you include within them must be bound in the scope where you use them.

Aside from that, there are 3 things I think this highlights: anonymous functions are a gateway drug, you only have to deal with a small set of possible data structures in Erlang, and I would love the ability to check for equality with the same syntax used for assignment/matching:

{foo, _dontcare, _alsodontcare} == Bar

In this case I ended up using the assignment, catching the badmatch error, and returning false unless it worked. This is not ideal (the try should probably match against the badmatch error at the very least), but it does work, its short and easy to read and its useful for searching complex data structures. Using find would look something like:

%% finds anything in Form that resembles {call,_,{atom,_,Name},_}
foo(Form, Name) ->
    find(Form, ?call_check).

Name fills its roll in the macro and the fun is used to check all the elements in Form. What you get back is a list of the matches. Not too shabby for 30 something lines of code!