-
Notifications
You must be signed in to change notification settings - Fork 70
/
oauth2_priv_set.erl
108 lines (95 loc) · 4.6 KB
/
oauth2_priv_set.erl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Copyright (c) 2012-2014 Kivra
%%%
%%% 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 Erlang OAuth 2.0 implementation
%%% @end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%_* Module declaration ===============================================
-module(oauth2_priv_set).
%%%_* Exports ==========================================================
%%%_ * API -------------------------------------------------------------
-export([new/1]).
-export([union/2]).
-export([is_subset/2]).
-export([is_member/2]).
%%%_ * Types -----------------------------------------------------------
%% Invariant: Children are sorted increasingly by name.
-type priv_tree() :: {node, Name :: binary(), Children :: [priv_tree()]} | '*'.
%% Invariant:
%% The list of trees is sorted increasingly by the name of the root node.
-type priv_set() :: [priv_tree()].
%%%_* Code =============================================================
%%%_ * API -------------------------------------------------------------
%% @doc Constructs a new priv_set from a single path or a list of paths.
%% A path denotes a single privilege.
-spec new(binary() | [binary()]) -> priv_set().
new(Paths) when is_list(Paths) ->
lists:foldl(fun union/2, [], [make_forest(Path) || Path <- Paths]);
new(Path) when is_binary(Path) ->
make_forest(Path).
%% @doc Returns the union of Set1 and Set2, i.e., a set such that
%% any path present in either Set1 or Set2 is also present in the result.
-spec union(priv_set(), priv_set()) -> priv_set().
union([H1={node, Name1, _}|T1], [H2={node, Name2, _}|T2]) when Name1 < Name2 ->
[H1|union(T1, [H2|T2])];
union([H1={node, Name1, _}|T1], [H2={node, Name2, _}|T2]) when Name1 > Name2 ->
[H2|union([H1|T1], T2)];
union([{node, Name, S1}|T1], [{node, Name, S2}|T2]) ->
[{node, Name, union(S1, S2)}|union(T1, T2)];
union(['*'|_], _) -> ['*']; %% '*' in union with anything is still '*'.
union(_, ['*'|_]) -> ['*'];
union([], Set) -> Set;
union(Set, []) -> Set.
%% @doc Return true if Set1 is a subset of Set2, i.e., if
%% every privilege held by Set1 is also held by Set2.
-spec is_subset(priv_set(), priv_set()) -> boolean().
is_subset([{node, N1, _}|_], [{node, N2, _}|_]) when N1 < N2 ->
false; %% This tree isn't present in Set2 as per the invariant.
is_subset(Set1 = [{node, N1, _}|_], [{node, N2, _}|T2]) when N1 > N2 ->
is_subset(Set1, T2);
is_subset([{node, Name, S1}|T1], [{node, Name, S2}|T2]) ->
case is_subset(S1, S2) of
true -> is_subset(T1, T2);
false -> false
end;
is_subset(['*'|_], ['*'|_]) -> true; %% '*' is only a subset of '*'.
is_subset(_, ['*'|_]) -> true; %% Everything is a subset of '*'.
is_subset([], _) -> true; %% The empty set is a subset of every set.
is_subset(_, _) -> false.
%% @doc Returns true if Path is present in Set, i.e, if
%% the privilege denoted by Path is contained within Set.
-spec is_member(binary(), priv_set()) -> boolean().
is_member(Path, Set) -> is_subset(make_forest(Path), Set).
%%%_* Private functions ================================================
-spec make_forest(binary() | list()) -> priv_set().
make_forest(Path) when is_binary(Path) ->
make_forest(binary:split(Path, <<".">>, [global]));
make_forest(Path) when is_list(Path) ->
[make_tree(Path)].
-spec make_tree([binary()]) -> priv_tree().
make_tree([<<"*">>|_]) -> '*';
make_tree([N]) -> make_node(N, []);
make_tree([H|T]) -> make_node(H, [make_tree(T)]).
-spec make_node(binary(), [priv_tree()]) -> priv_tree().
make_node(Name, Children) -> {node, Name, Children}.
%%%_* Tests ============================================================
-ifdef(TEST).
-include_lib("eunit/include/eunit.hrl").
-endif.
%%%_* Emacs ============================================================
%%% Local Variables:
%%% allout-layout: t
%%% erlang-indent-level: 4
%%% End: