You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@couchdb.apache.org by be...@apache.org on 2014/02/13 17:35:39 UTC
[06/23] goldrush commit: updated refs/heads/import-master to 71e6321
Add initial processing functions as glc_lib
Project: http://git-wip-us.apache.org/repos/asf/couchdb-goldrush/repo
Commit: http://git-wip-us.apache.org/repos/asf/couchdb-goldrush/commit/2a63e722
Tree: http://git-wip-us.apache.org/repos/asf/couchdb-goldrush/tree/2a63e722
Diff: http://git-wip-us.apache.org/repos/asf/couchdb-goldrush/diff/2a63e722
Branch: refs/heads/import-master
Commit: 2a63e722d864d658880acfc9ad8eba8bb814d175
Parents: eb42579
Author: Magnus Klaar <kl...@ninenines.fr>
Authored: Fri Apr 27 04:15:40 2012 +0200
Committer: Magnus Klaar <kl...@ninenines.fr>
Committed: Fri Apr 27 04:15:40 2012 +0200
----------------------------------------------------------------------
src/glc.erl | 112 ++++++++++++--------
src/glc_lib.erl | 291 +++++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 358 insertions(+), 45 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/couchdb-goldrush/blob/2a63e722/src/glc.erl
----------------------------------------------------------------------
diff --git a/src/glc.erl b/src/glc.erl
index b0e7f40..a444e7b 100644
--- a/src/glc.erl
+++ b/src/glc.erl
@@ -78,6 +78,10 @@
with/2
]).
+-export([
+ union/1
+]).
+
-record(module, {
'query' :: term(),
tables :: [{atom(), ets:tid()}],
@@ -107,28 +111,50 @@ eq(Key, Term) when is_atom(Key) -> {Key, '=', Term}.
gt(Key, Term) when is_atom(Key) -> {Key, '>', Term}.
-%% @doc Apply multiple conditions to the input.
-%% For an event to be considered valid output the condition of all filters
-%% specified in the input must hold for the input event.
+%% @doc Filter the input using multiple filters.
+%%
+%% For an input to be considered valid output the all filters specified
+%% in the list must hold for the input event. The list is expected to
+%% be a non-empty list. If the list of filters is an empty list a `badarg'
+%% error will be thrown.
-spec all([q()]) -> q().
-all(Conds) when is_list(Conds) ->
- {all, Conds}.
+all([_|_]=Conds) ->
+ {all, Conds};
+all(Other) ->
+ erlang:error(badarg, [Other]).
-%% @doc Apply one of multiple conditions to the input.
+%% @doc Filter the input using one of multiple filters.
+%%
+%% For an input to be considered valid output on of the filters specified
+%% in the list must hold for the input event. The list is expected to be
+%% a non-empty list. If the list of filters is an empty list a `badarg'
+%% error will be thrown.
-spec any([q()]) -> q().
-any(Conds) when is_list(Conds) ->
- {any, Conds}.
+any([_|_]=Conds) ->
+ {any, Conds};
+any(Other) ->
+ erlang:error(badarg, [Other]).
+
%% @doc Always return `true' or `false'.
-spec null(boolean()) -> q().
null(Result) when is_boolean(Result) ->
{null, Result}.
-%% @doc Apply a function to each output.
+%% @doc Apply a function to each output of a query.
+%%
+%% Updating the output action of a query finalizes it. Attempting
+%% to use a finalized query to construct a new query will result
+%% in a `badarg' error.
-spec with(q(), fun((gre:event()) -> term())) -> q().
with(Query, Fun) when is_function(Fun, 1) ->
{with, Query, Fun}.
+%% @doc Return a union of multiple queries.
+-spec union([q()]) -> q().
+union(Queries) ->
+ {union, Queries}.
+
%% @doc Compile a query to a module.
%%
@@ -176,8 +202,8 @@ module_data(Query) ->
%% tables are referred to by name in the generated code. the table/1
%% function maps names to tids.
Tables = [{params,Params}, {counters,Counters}],
- Tree = query_tree(Query),
- {ok, #module{'query'=Query, tables=Tables, qtree=Tree}}.
+ Query2 = glc_lib:reduce(Query),
+ {ok, #module{'query'=Query, tables=Tables, qtree=Query2}}.
%% @private Map a query to a simplified query tree term.
@@ -208,11 +234,7 @@ module_data(Query) ->
{atom(), '>', term()} |
{any, [qcond()]} |
{all, [qcond()]}.
--type qbody() :: tuple().
--type qtree() :: [{qcond(), qbody()}].
--spec query_tree(term()) -> qtree().
-query_tree(Query) ->
- Query.
+
%% abstract code geneation functions
@@ -256,20 +278,14 @@ abstract_module_(Module, #module{tables=Tables, qtree=Tree}=Data) ->
abstract_info(Data) ++
[erl_syntax:clause(
[erl_syntax:underscore()], none,
- [erl_syntax:application(
- erl_syntax:atom(erlang),
- erl_syntax:atom(error),
- [erl_syntax:atom(badarg)])])]),
+ [abstract_apply(erlang, error, [erl_syntax:atom(badarg)])])]),
%% table(Name) -> ets:tid().
erl_syntax:function(
erl_syntax:atom(table),
abstract_tables(Tables) ++
[erl_syntax:clause(
[erl_syntax:underscore()], none,
- [erl_syntax:application(
- erl_syntax:atom(erlang),
- erl_syntax:atom(error),
- [erl_syntax:atom(badarg)])])]),
+ [abstract_apply(erlang, error, [erl_syntax:atom(badarg)])])]),
%% handle(Event) - entry function
erl_syntax:function(
erl_syntax:atom(handle),
@@ -417,9 +433,7 @@ abstract_getkey(Key, OnMatch, OnNomatch, #state{fields=Fields}=State) ->
abstract_getkey_(Key, OnMatch, OnNomatch, #state{
event=Event, fields=Fields}=State) ->
[erl_syntax:case_expr(
- erl_syntax:application(
- erl_syntax:atom(gre), erl_syntax:atom(find),
- [erl_syntax:atom(Key), Event]),
+ abstract_apply(gre, find, [erl_syntax:atom(Key), Event]),
[erl_syntax:clause([
erl_syntax:tuple([
erl_syntax:atom(true),
@@ -457,12 +471,8 @@ abstract_getparam_(Term, OnBound, #state{paramstab=Table,
end,
[erl_syntax:match_expr(
param_variable(Key),
- erl_syntax:application(
- erl_syntax:atom(ets),
- erl_syntax:atom(lookup_element),
- [erl_syntax:application(
- erl_syntax:atom(table),
- [erl_syntax:atom(params)]),
+ abstract_apply(ets, lookup_element,
+ [abstract_apply(table, [erl_syntax:atom(params)]),
erl_syntax:abstract(Key),
erl_syntax:abstract(2)]))
] ++ OnBound(State#state{paramvars=[{Term, param_variable(Key)}|Params]}).
@@ -483,12 +493,8 @@ param_variable(Key) ->
%% @todo Pass state record. Only Generate code if `statistics' is enabled.
-spec abstract_count(atom()) -> syntaxTree().
abstract_count(Counter) ->
- erl_syntax:application(
- erl_syntax:atom(ets),
- erl_syntax:atom(update_counter),
- [erl_syntax:application(
- erl_syntax:atom(table),
- [erl_syntax:atom(counters)]),
+ abstract_apply(ets, update_counter,
+ [abstract_apply(table, [erl_syntax:atom(counters)]),
erl_syntax:abstract(Counter),
erl_syntax:abstract({2,1})]).
@@ -497,12 +503,8 @@ abstract_count(Counter) ->
%% @todo Pass state record. Only Generate code if `statistics' is enabled.
-spec abstract_getcount(atom()) -> [syntaxTree()].
abstract_getcount(Counter) ->
- [erl_syntax:application(
- erl_syntax:atom(ets),
- erl_syntax:atom(lookup_element),
- [erl_syntax:application(
- erl_syntax:atom(table),
- [erl_syntax:atom(counters)]),
+ [abstract_apply(ets, lookup_element,
+ [abstract_apply(table, [erl_syntax:atom(counters)]),
erl_syntax:abstract(Counter),
erl_syntax:abstract(2)])].
@@ -530,6 +532,21 @@ load_binary(Module, Binary) ->
{error, Reason} -> exit({error_loading_module, Module, Reason})
end.
+%% @private Apply an exported function.
+-spec abstract_apply(atom(), atom(), [syntaxTree()]) -> syntaxTree().
+abstract_apply(Module, Function, Arguments) ->
+ erl_syntax:application(
+ erl_syntax:atom(Module),
+ erl_syntax:atom(Function),
+ Arguments).
+
+%% @private Apply a module local function.
+-spec abstract_apply(atom(), [syntaxTree()]) -> syntaxTree().
+abstract_apply(Function, Arguments) ->
+ erl_syntax:application(
+ erl_syntax:atom(Function),
+ Arguments).
+
-ifdef(TEST).
-include_lib("eunit/include/eunit.hrl").
@@ -654,4 +671,9 @@ with_function_test() ->
?assertEqual(1, receive Msg -> Msg after 0 -> notcalled end),
done.
+union_single_test() ->
+ {compiled, _Mod} = setup_query(testmod13,
+ glc:union([glc:eq(a, 1)])),
+ done.
+
-endif.
http://git-wip-us.apache.org/repos/asf/couchdb-goldrush/blob/2a63e722/src/glc_lib.erl
----------------------------------------------------------------------
diff --git a/src/glc_lib.erl b/src/glc_lib.erl
new file mode 100644
index 0000000..97b7786
--- /dev/null
+++ b/src/glc_lib.erl
@@ -0,0 +1,291 @@
+%% Copyright (c) 2012, Magnus Klaar <kl...@ninenines.eu>
+%%
+%% Permission to use, copy, modify, and/or distribute this software for any
+%% purpose with or without fee is hereby granted, provided that the above
+%% copyright notice and this permission notice appear in all copies.
+%%
+%% THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+%% WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+%% MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+%% ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+%% WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+%% ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+%% OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+
+%% @doc Query processing functions.
+-module(glc_lib).
+
+-export([
+ reduce/1
+]).
+
+%% @doc Return a reduced version of a query.
+%%
+%% The purpose of this function is to ensure that a query filter
+%% is in the simplest possible form. The query filter returned
+%% from this function is functionally equivalent to the original.
+reduce(Query) ->
+ repeat(Query, fun(Q0) ->
+ Q1 = flatten(Q0),
+ Q2 = required(Q1),
+ Q3 = flatten(Q2),
+ Q4 = common(Q3),
+ Q4
+ end).
+
+%% @private Repeatedly apply a function to a query.
+%% This is used for query transformation functions
+%% applied multiple times
+repeat(Query, Fun) ->
+ case Fun(Query) of
+ Query -> Query;
+ Query2 -> repeat(Query2, Fun)
+ end.
+
+%% @private Flatten a condition tree.
+flatten({all, [Cond]}) ->
+ Cond;
+flatten({any, [Cond]}) ->
+ Cond;
+flatten({all, Conds}) ->
+ flatten_all([flatten(Cond) || Cond <- Conds]);
+flatten({any, [_|_]=Conds}) ->
+ flatten_any([flatten(Cond) || Cond <- Conds]);
+flatten({with, Cond, Action}) ->
+ {with, flatten(Cond), Action};
+flatten(Other) ->
+ return_valid(Other).
+
+
+%% @private Flatten and remove duplicate members of an "all" filter.
+flatten_all(Conds) ->
+ {all, lists:usort(flatten_all_(Conds))}.
+
+flatten_all_([{all, Conds}|T]) ->
+ Conds ++ flatten_all_(T);
+flatten_all_([H|T]) ->
+ [H|flatten_all_(T)];
+flatten_all_([]) ->
+ [].
+
+%% @private Flatten and remove duplicate members of an "any" filter.
+flatten_any(Conds) ->
+ {any, lists:usort(flatten_any_(Conds))}.
+
+flatten_any_([{any, Conds}|T]) ->
+ Conds ++ flatten_any_(T);
+flatten_any_([H|T]) ->
+ [H|flatten_any_(T)];
+flatten_any_([]) ->
+ [].
+
+%% @private Factor out required filters.
+%%
+%% Identical conditions may occur in all sub-filters of an "any" filter. These
+%% filters can be tested once before testing the conditions that are unique to
+%% each sub-filter.
+%%
+%% Assume that the input has been flattened first in order to eliminate all
+%% occurances of an "any" filters being "sub-filters" of "any" filters.
+required({any, [H|_]=Conds}) ->
+ Init = ordsets:from_list(case H of {all, Init2} -> Init2; H -> [H] end),
+ case required(Conds, Init) of
+ [] ->
+ Conds2 = [required(Cond) || Cond <- Conds],
+ {any, Conds2};
+ [_|_]=Req ->
+ Conds2 = [required(deleteall(Cond, Req)) || Cond <- Conds],
+ {all, [{all, Req}, {any, Conds2}]}
+ end;
+required({all, Conds}) ->
+ {all, [required(Cond) || Cond <- Conds]};
+required(Other) ->
+ Other.
+
+required([{all, Conds}|T], Acc) ->
+ required(T, ordsets:intersection(ordsets:from_list(Conds), Acc));
+required([{any, _}|_]=Cond, Acc) ->
+ erlang:error(badarg, [Cond, Acc]);
+required([H|T], Acc) ->
+ required(T, ordsets:intersection(ordsets:from_list([H]), Acc));
+required([], Acc) ->
+ Acc.
+
+%% @private Factor our common filters.
+%%
+%% Identical conditions may occur in some sub-filters of an "all" filter. These
+%% filters can be tested once before testing the conditions that are unique to
+%% each sub-filter. This is different from factoring out common sub-filters
+%% in an "any" filter where the only those sub-filters that exist in all
+%% members.
+%%
+%% Assume that the input has been flattened first in order to eliminate all
+%% occurances of an "any" filters being "sub-filters" of "any" filters.
+common({all, Conds}) ->
+ case common_(Conds, []) of
+ {found, Found} ->
+ {all, [Found|[delete(Cond, Found) || Cond <- Conds]]};
+ nonefound ->
+ {all, [common(Cond) || Cond <- Conds]}
+ end;
+common({any, Conds}) ->
+ {any, [common(Cond) || Cond <- Conds]};
+common(Other) ->
+ Other.
+
+
+common_([{any, Conds}|T], Seen) ->
+ Set = ordsets:from_list(Conds),
+ case ordsets:intersection(Set, Seen) of
+ [] -> common_(T, ordsets:union(Set, Seen));
+ [H|_] -> {found, H}
+ end;
+common_([H|T], Seen) ->
+ case ordsets:is_element(H, Seen) of
+ false -> common_(T, ordsets:union(ordsets:from_list([H]), Seen));
+ true -> {found, H}
+ end;
+common_([], _Seen) ->
+ nonefound.
+
+
+
+
+%% @private Delete all occurances of a filter.
+%%
+%% Assume that the function is called because a filter is tested
+%% by a parent filter. It is therefore safe to replace occurances
+%% with a null filter that always returns true.
+delete({all, Conds}, Filter) ->
+ {all, [delete(Cond, Filter) || Cond <- Conds, Cond =/= Filter]};
+delete({any, Conds}, Filter) ->
+ {any, [delete(Cond, Filter) || Cond <- Conds, Cond =/= Filter]};
+delete(Filter, Filter) ->
+ {null, true};
+delete(Cond, _Filter) ->
+ Cond.
+
+%% @private Delete all occurances of multiple filters.
+deleteall(Filter, [H|T]) ->
+ deleteall(delete(Filter, H), T);
+deleteall(Filter, []) ->
+ Filter.
+
+
+
+%% @private Test if a term is a valid filter.
+is_valid({Field, '<', _Term}) when is_atom(Field) ->
+ true;
+is_valid({Field, '=', _Term}) when is_atom(Field) ->
+ true;
+is_valid({Field, '>', _Term}) when is_atom(Field) ->
+ true;
+is_valid({null, true}) ->
+ true;
+is_valid({null, false}) ->
+ true;
+is_valid(_Other) ->
+ false.
+
+%% @private Assert that a term is a valid filter.
+%% If the term is a valid filter. The original term will be returned.
+%% If the term is not a valid filter. A `badarg' error is thrown.
+return_valid(Term) ->
+ case is_valid(Term) of
+ true -> Term;
+ false ->
+ io:format(user, "~w~n", [Term]),
+ erlang:error(badarg, [Term])
+ end.
+
+
+-ifdef(TEST).
+-include_lib("eunit/include/eunit.hrl").
+
+all_one_test() ->
+ ?assertEqual(glc:eq(a, 1),
+ glc_lib:reduce(glc:all([glc:eq(a, 1)]))
+ ).
+
+all_sort_test() ->
+ ?assertEqual(glc:all([glc:eq(a, 1), glc:eq(b, 2)]),
+ glc_lib:reduce(glc:all([glc:eq(b, 2), glc:eq(a, 1)]))
+ ).
+
+any_one_test() ->
+ ?assertEqual(glc:eq(a, 1),
+ glc_lib:reduce(glc:any([glc:eq(a, 1)]))
+ ).
+
+any_sort_test() ->
+ ?assertEqual(glc:any([glc:eq(a, 1), glc:eq(b, 2)]),
+ glc_lib:reduce(glc:any([glc:eq(b, 2), glc:eq(a, 1)]))
+ ).
+
+all_nest_test() ->
+ ?assertEqual(glc:all([glc:eq(a, 1), glc:eq(b, 2)]),
+ glc_lib:reduce(glc:all([glc:eq(a, 1), glc:all([glc:eq(b, 2)])]))
+ ),
+ ?assertEqual(glc:all([glc:eq(a, 1), glc:eq(b, 2), glc:eq(c, 3)]),
+ glc_lib:reduce(glc:all([glc:eq(c, 3),
+ glc:all([glc:eq(a, 1),
+ glc:all([glc:eq(b, 2)])])]))
+ ).
+
+any_nest_test() ->
+ ?assertEqual(glc:any([glc:eq(a, 1), glc:eq(b, 2)]),
+ glc_lib:reduce(glc:any([glc:eq(a, 1), glc:any([glc:eq(b, 2)])]))
+ ),
+ ?assertEqual(glc:any([glc:eq(a, 1), glc:eq(b, 2), glc:eq(c, 3)]),
+ glc_lib:reduce(glc:any([glc:eq(c, 3),
+ glc:any([glc:eq(a, 1),
+ glc:any([glc:eq(b, 2)])])]))
+ ).
+
+all_equiv_test() ->
+ ?assertEqual(glc:eq(a, 1),
+ glc_lib:reduce(glc:all([glc:eq(a, 1), glc:eq(a, 1)]))
+ ).
+
+any_equiv_test() ->
+ ?assertEqual(glc:eq(a, 1),
+ glc_lib:reduce(glc:any([glc:eq(a, 1), glc:eq(a, 1)]))
+ ).
+
+any_required_test() ->
+ ?assertEqual(
+ glc:all([
+ glc:any([glc:eq(b, 2), glc:eq(c, 3)]),
+ glc:eq(a, 1)
+ ]),
+ glc_lib:reduce(
+ glc:any([
+ glc:all([glc:eq(a, 1), glc:eq(b, 2)]),
+ glc:all([glc:eq(a, 1), glc:eq(c, 3)])]))
+ ).
+
+
+all_common_test() ->
+ ?assertEqual(
+ glc:all([glc:eq(a, 1), glc:eq(b, 2), glc:eq(c, 3)]),
+ glc_lib:reduce(
+ glc:all([
+ glc:any([glc:eq(a, 1), glc:eq(b, 2)]),
+ glc:any([glc:eq(a, 1), glc:eq(c, 3)])]))
+ ).
+
+delete_from_all_test() ->
+ ?assertEqual(
+ glc:all([glc:eq(b,2)]),
+ deleteall(
+ glc:all([glc:eq(a, 1),glc:eq(b,2)]), [glc:eq(a, 1)])
+ ).
+
+delete_from_any_test() ->
+ ?assertEqual(
+ glc:any([glc:eq(b,2)]),
+ deleteall(
+ glc:any([glc:eq(a, 1),glc:eq(b,2)]), [glc:eq(a, 1)])
+ ).
+
+-endif.