Current section
Files
Jump to
Current section
Files
src/khepri_pattern_tree.erl
%% This Source Code Form is subject to the terms of the Mozilla Public
%% License, v. 2.0. If a copy of the MPL was not distributed with this
%% file, You can obtain one at https://mozilla.org/MPL/2.0/.
%%
%% Copyright © 2024-2025 Broadcom. All Rights Reserved. The term "Broadcom"
%% refers to Broadcom Inc. and/or its subsidiaries.
%%
%% @doc
%% Khepri tree data structure where each tree node is a pattern component.
%%
%% The tree structure used to store data in the Khepri store (see {@link
%% khepri_tree}) uses path components for branches (see {@link
%% khepri_path:component()}).
%%
%% The tree structure in {@link khepri_tree} can find many matching paths given
%% a pattern while this tree structure can find many matching patterns given
%% a path.
%%
%% @hidden
-module(khepri_pattern_tree).
-include("src/khepri_node.hrl").
-record(pattern_node, {child_nodes = #{},
payload = ?NO_PAYLOAD}).
-opaque tree_node(Payload) ::
#pattern_node{child_nodes :: #{khepri_path:pattern_component() =>
tree_node(Payload)},
payload :: Payload | ?NO_PAYLOAD}.
%% A node in the tree structure.
-opaque tree(Payload) :: tree_node(Payload).
-type payload() :: any().
-type fold_acc() :: any().
-type fold_fun(Payload) :: fun((khepri_path:native_pattern(),
Payload,
fold_acc()) -> fold_acc()).
-type update_fun(Payload) :: fun((Payload) -> Payload).
-type find_fun(Payload) :: fun((Payload) -> boolean()).
-export_type([tree_node/1,
tree/1]).
-export([empty/0,
is_empty/1,
update/3,
fold/3,
fold_matching/5,
foreach/2,
compile/1,
map_fold/3,
any/2]).
-spec empty() -> TreeNode when
TreeNode :: khepri_pattern_tree:tree(Payload),
Payload :: ?NO_PAYLOAD.
%% @doc Returns a new empty tree node.
%%
%% @see tree().
%% @see tree_node().
empty() ->
#pattern_node{}.
-spec is_empty(PatternTree) -> IsEmpty when
PatternTree :: khepri_pattern_tree:tree(Payload),
IsEmpty :: boolean(),
Payload :: payload().
%% @doc Checks whether the given pattern tree is empty.
%%
%% A pattern tree node is empty if it contains no payload and has no children.
%%
%% @see empty/0.
is_empty(#pattern_node{payload = ?NO_PAYLOAD, child_nodes = ChildNodes})
when ChildNodes =:= #{} ->
true;
is_empty(_PatternTree) ->
false.
-spec update(PatternTree, PathPattern, UpdateFun) -> Ret when
PatternTree :: khepri_pattern_tree:tree(Payload),
PathPattern :: khepri_path:native_pattern(),
UpdateFun :: update_fun(Payload),
Ret :: khepri_pattern_tree:tree(Payload),
Payload :: payload().
%% @doc Updates the node of the given pattern tree with the given update
%% function.
%%
%% If any pattern components of `PathPattern' do not yet exist in the tree,
%% this function will add any necessary branches to the tree using empty tree
%% nodes.
%%
%% If the tree node for the given `PathPattern' does not yet exist, the
%% `?NO_PAYLOAD' constant will be passed to the `UpdateFun'.
%%
%% @see empty/0.
update(PatternTree, [], UpdateFun) ->
update_payload(PatternTree, UpdateFun);
update(
#pattern_node{child_nodes = ChildNodes0} = PatternTree,
[Component | Rest],
UpdateFun) ->
PatternSubtree = case ChildNodes0 of
#{Component := PatternNode} ->
PatternNode;
_ ->
empty()
end,
PatternSubtree1 = update(PatternSubtree, Rest, UpdateFun),
ChildNodes = maps:put(Component, PatternSubtree1, ChildNodes0),
PatternTree#pattern_node{child_nodes = ChildNodes}.
-spec update_payload(PatternTreeNode, UpdateFun) -> Ret when
PatternTreeNode :: khepri_pattern_tree:tree_node(Payload),
UpdateFun :: update_fun(Payload),
Ret :: khepri_pattern_tree:tree_node(Payload),
Payload :: payload().
%% @doc Updates the payload of the given node with the given update function.
%%
%% @private
update_payload(#pattern_node{payload = Payload} = PatternTree, UpdateFun) ->
Payload1 = UpdateFun(Payload),
PatternTree#pattern_node{payload = Payload1}.
-spec fold(PatternTree, Fun, Acc) -> Ret when
PatternTree :: khepri_pattern_tree:tree(Payload),
Fun :: fold_fun(Payload),
Acc :: fold_acc(),
Ret :: fold_acc(),
Payload :: payload().
%% @doc Folds over the pattern tree passing each pattern, payload and the
%% accumulator to the fold function.
%%
%% Unlike {@link fold_matching/5} all payloads are passed to the fold function.
fold(#pattern_node{} = PatternTree, Fun, Acc) ->
fold(PatternTree, Fun, [], Acc).
fold(
#pattern_node{payload = Payload, child_nodes = ChildNodes},
Fun, ReversedPath, Acc) ->
Acc1 = case Payload of
?NO_PAYLOAD ->
Acc;
_ ->
Pattern = lists:reverse(ReversedPath),
Fun(Pattern, Payload, Acc)
end,
maps:fold(
fun(PatternComponent, Child, Acc2) ->
ReversedPath1 = [PatternComponent | ReversedPath],
fold(Child, Fun, ReversedPath1, Acc2)
end, Acc1, ChildNodes).
-spec fold_matching(PatternTree, Tree, Path, FoldFun, Acc) -> Ret when
PatternTree :: khepri_pattern_tree:tree(Payload),
Tree :: khepri_tree:tree(),
Path :: khepri_path:native_path(),
FoldFun :: fold_fun(Payload),
Acc :: fold_acc(),
Ret :: fold_acc(),
Payload :: payload().
%% @doc Folds over the given pattern tree to find all patterns in the tree
%% which match the given path.
%%
%% The `FoldFun' function takes a path pattern, the payload stored in the
%% pattern tree at that tree node, and an accumulator as arguments. Only tree
%% nodes which have payloads are passed to this function.
%%
%% @see fold_fun().
%% @see fold_acc().
fold_matching(PatternTree, Tree, Path, FoldFun, Acc) ->
Path1 = khepri_path:realpath(Path),
case Path1 of
[] ->
fold_data(PatternTree, [], FoldFun, Acc);
_ ->
Root = khepri_tree:get_root(Tree),
fold_matching1(PatternTree, Root, Path, FoldFun, Acc, [])
end.
-spec fold_matching1(PatternTree, Node, Path, FoldFun, Acc, ReversedPath) ->
Ret when
PatternTree :: khepri_pattern_tree:tree(Payload),
Node :: khepri_tree:tree_node(),
Path :: khepri_path:native_path(),
FoldFun :: fold_fun(Payload),
Acc :: fold_acc(),
ReversedPath :: khepri_path:native_path(),
Ret :: fold_acc(),
Payload :: payload().
%% @private
fold_matching1(
_PatternTree, _Node, [], _FoldFun, Acc, _ReversedPath) ->
Acc;
fold_matching1(
PatternTree, Parent, [Component | Rest], FoldFun, Acc, ReversedPath) ->
case Parent of
#node{child_nodes = #{Component := Node}} ->
ReversedPath1 = [Component | ReversedPath],
maps:fold(
fun(Condition, PatternSubtree, Acc0) ->
CondMet = khepri_condition:is_met(
Condition, Component, Node),
AppliesToGrandchildren = (
khepri_condition:applies_to_grandchildren(
Condition)),
case CondMet of
true when Rest =:= [] ->
%% The pattern node matches the whole path
%% (there is no component left after). We can
%% apply the `FoldFun' and return.
CurrentPath = lists:reverse(ReversedPath1),
fold_data(
PatternSubtree, CurrentPath,
FoldFun, Acc0);
true when not AppliesToGrandchildren ->
%% The pattern node matches the path so far but
%% there are still components left after (we are
%% not at the end of the path).
%%
%% We continue with the next component.
fold_matching1(
PatternSubtree, Node, Rest,
FoldFun, Acc0, ReversedPath1);
true when AppliesToGrandchildren ->
%% Same as above, but because this condition can
%% be used on grand children, we two scenarios:
%% 1. The condition may still match grand
%% children, so we keep it and continue down
%% the tree. This is `Acc1' below.
%% 2. The condition won't match any grand
%% children (but it matched so far). We
%% evaluate the grand children with the
%% pattern sub tree. This is `Acc2' below.
%%
%% For scenario 1, we prepare a special pattern
%% tree with only that condition because we don't
%% want to evaluate siblings on grand children.
PatternTree1 = PatternTree#pattern_node{
child_nodes =
#{Condition => PatternSubtree}},
Acc1 = fold_matching1(
PatternTree1, Node, Rest,
FoldFun, Acc0, ReversedPath1),
Acc2 = fold_matching1(
PatternSubtree, Node, Rest,
FoldFun, Acc1, ReversedPath1),
Acc2;
{false, _} ->
Acc0
end
end, Acc, PatternTree#pattern_node.child_nodes);
_ChildNotFound ->
Acc
end.
-spec fold_data(PatternTreeNode, CurrentPath, FoldFun, Acc) -> Ret when
PatternTreeNode :: khepri_pattern_tree:tree_node(Payload),
CurrentPath :: khepri_path:native_path(),
FoldFun :: fold_fun(Payload),
Acc :: fold_acc(),
Ret :: fold_acc(),
Payload :: payload().
%% @doc Calls the given fold function with the given tree node's payload, if
%% the given tree node has a payload.
%%
%% @private
fold_data(PatternTreeNode, CurrentPath, FoldFun, Acc) ->
case PatternTreeNode of
#pattern_node{payload = ?NO_PAYLOAD} ->
Acc;
#pattern_node{payload = Payload} ->
FoldFun(CurrentPath, Payload, Acc)
end.
-spec foreach(PatternTree, Fun) -> Ret when
PatternTree :: khepri_pattern_tree:tree(Payload),
Fun :: fun((khepri_path:native_pattern(), Payload) -> any()),
Payload :: payload(),
Ret :: ok.
%% @doc Iterates over the path patterns and associated payloads for any
%% patterns in the given pattern tree with payloads.
foreach(PatternTree, Fun) ->
foreach(PatternTree, Fun, []).
foreach(
#pattern_node{child_nodes = ChildNodes, payload = Payload},
Fun, ReversedPathPattern) ->
CurrentPathPattern = lists:reverse(ReversedPathPattern),
case Payload of
?NO_PAYLOAD ->
ok;
_ ->
_ = Fun(CurrentPathPattern, Payload),
ok
end,
maps:foreach(
fun(Condition, Child) ->
ReversedPathPattern1 = [Condition | ReversedPathPattern],
foreach(Child, Fun, ReversedPathPattern1)
end, ChildNodes).
-spec compile(PatternTree) -> Ret when
PatternTree :: khepri_pattern_tree:tree(Payload),
Ret :: khepri_pattern_tree:tree(Payload),
Payload :: payload().
%% @doc Compiles conditions in the given pattern tree.
%%
%% Some conditions must be compiled before being checked against paths and tree
%% nodes such as ETS match specifications in the `#if_data_matches{}' condition
%% or regular expressions in the `#if_name_matches{}' condition.
%%
%% The pattern tree must be compiled before running {@link fold/5} against the
%% tree. Compiled trees should not be (de)serialized though since the compiled
%% information depends on the runtime system.
%%
%% @see khepri_condition:compile/1.
compile(#pattern_node{child_nodes = ChildNodes0} = PatternTree) ->
ChildNodes = maps:fold(
fun(Condition0, Child0, Acc) ->
Condition = khepri_condition:compile(Condition0),
Child = compile(Child0),
Acc#{Condition => Child}
end, #{}, ChildNodes0),
PatternTree#pattern_node{child_nodes = ChildNodes}.
-spec map_fold(Fun, Acc, PatternTree) -> Ret when
PatternTree :: khepri_pattern_tree:tree(Payload),
Fun :: fun((Pattern, Payload, Acc) -> {NewPayload, NewAcc}),
Pattern :: khepri_path:native_pattern(),
Acc :: fold_acc(),
NewAcc :: fold_acc(),
NewPatternTree :: khepri_pattern_tree:tree(NewPayload),
Ret :: {NewPatternTree, NewAcc},
Payload :: payload(),
NewPayload :: payload() | ?NO_PAYLOAD.
%% @doc Folds over a pattern tree, updating each payload and an accumulator
%% with the given `Fun'.
%%
%% The filter-map `Fun' receives each `PathPattern' and `Payload' pair in the
%% tree. If the function returns `false', the pair is removed from the tree.
%% If the function returns `true' the value is kept without changes. If the
%% function returns `{true, NewPayload}', the `PathPattern' is associated with
%% `NewPayload' in the returned tree.
%%
%% @param ProjectionTree the initial tree to update with the filter-map
%% function.
%% @param Fun the filter-map function to apply to each path-pattern and payload
%% pair.
%% @returns A new pattern tree with entries filtered by the filtered and
%% updated by the filter-map function.
map_fold(Fun, Acc, PatternTree) ->
map_fold(Fun, Acc, PatternTree, []).
map_fold(
Fun, Acc,
#pattern_node{child_nodes = ChildNodes, payload = Payload},
ReversedPattern) ->
{Payload1, Acc1} = case Payload of
?NO_PAYLOAD ->
{Payload, Acc};
_ ->
Pattern = lists:reverse(ReversedPattern),
Fun(Pattern, Payload, Acc)
end,
{ChildNodes1, Acc4} =
maps_filtermap_fold(
fun(PatternComponent, ChildNode, Acc2) ->
ReversedPattern1 = [PatternComponent | ReversedPattern],
{ChildNode1, Acc3} = map_fold(
Fun, Acc2, ChildNode,
ReversedPattern1),
MappedChild = case ChildNode1 of
#pattern_node{payload = ?NO_PAYLOAD,
child_nodes = Grandchildren}
when Grandchildren =:= #{} ->
%% Trim any children with no children and
%% no payload.
false;
_ ->
{true, ChildNode1}
end,
{MappedChild, Acc3}
end, Acc1, ChildNodes),
Node = #pattern_node{payload = Payload1, child_nodes = ChildNodes1},
{Node, Acc4}.
%% `maps:filtermap/2' modified to collect an accumulator
maps_filtermap_fold(Fun, Acc, Map) ->
maps_filtermap_fold(Fun, Acc, maps:next(maps:iterator(Map)), []).
maps_filtermap_fold(Fun, Acc, {K, V, Iter}, Pairs) ->
{Result, Acc1} = Fun(K, V, Acc),
Pairs1 = case Result of
%% This branch is unused by the only caller so the dialyzer
%% complains it is unreachable. The dialyzer is correct so
%% we leave this commented out for future use:
%% true ->
%% [{K, V} | Pairs];
{true, NewV} ->
[{K, NewV} | Pairs];
false ->
Pairs
end,
maps_filtermap_fold(Fun, Acc1, maps:next(Iter), Pairs1);
maps_filtermap_fold(_Fun, Acc, none, Pairs) ->
{maps:from_list(Pairs), Acc}.
-spec any(PatternTree, FindFun) -> Ret when
PatternTree :: khepri_pattern_tree:tree(Payload),
FindFun :: find_fun(Payload),
Ret :: payload() | undefined,
Payload :: payload().
%% @doc Determines whether the pattern tree contains a tree node with a payload
%% that matches the given predicate.
%%
%% @param PatternTree the tree to search.
%% @param FindFun the predicate with which to evaluate tree nodes.
%% @returns `true' if the predicate evaluates as `true' for any payload,
%% `false' otherwise.
any(#pattern_node{payload = Payload, child_nodes = Children}, FindFun) ->
(Payload =/= ?NO_PAYLOAD andalso FindFun(Payload)) orelse
lists:any(
fun(Child) -> any(Child, FindFun) end, maps:values(Children)).