Current section
Files
Jump to
Current section
Files
src/khepri_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 © 2021-2025 Broadcom. All Rights Reserved. The term "Broadcom"
%% refers to Broadcom Inc. and/or its subsidiaries.
%%
%% @doc
%% Khepri tree manipulation API.
%%
%% @hidden
-module(khepri_tree).
-include_lib("stdlib/include/assert.hrl").
-include("include/khepri.hrl").
-include("src/khepri_error.hrl").
-include("src/khepri_node.hrl").
-export([new/0,
get_root/1,
get_keep_while_conds/1,
assert_equal/2,
are_keep_while_conditions_met/2,
collect_node_props_cb/3,
count_node_cb/3,
find_matching_nodes/3,
fold/5,
delete_matching_nodes/4,
insert_or_update_node/5,
does_path_match/3,
walk_down_the_tree/5,
convert_tree/3]).
-record(tree, {root = #node{} :: khepri_tree:tree_node(),
keep_while_conds = #{} :: khepri_tree:keep_while_conds_map(),
keep_while_conds_revidx = #{}}).
-type tree_node() :: #node{}.
%% A node in the tree structure.
-type tree(KeepWhileCondsRevIdxType) :: #tree{keep_while_conds_revidx ::
KeepWhileCondsRevIdxType}.
-opaque tree_v0() :: tree(khepri_tree:keep_while_conds_revidx_v0()).
-opaque tree_v1() :: tree(khepri_tree:keep_while_conds_revidx_v1()).
-type tree() :: tree_v0() | tree_v1().
-type keep_while_conds_map() :: #{khepri_path:native_path() =>
khepri_condition:native_keep_while()}.
%% Per-node `keep_while' conditions.
-opaque keep_while_conds_revidx_v0() :: #{khepri_path:native_path() =>
#{khepri_path:native_path() => ok}}.
-opaque keep_while_conds_revidx_v1() :: khepri_prefix_tree:tree(
#{khepri_path:native_path() => ok}).
-type keep_while_conds_revidx() :: keep_while_conds_revidx_v0() |
keep_while_conds_revidx_v1().
%% Internal reverse index of the keep_while conditions.
%%
%% If node A depends on a condition on node B, then this reverse index will
%% have a "node B => node A" association. The version 0 of this type used a map
%% and folded over the entries in the map using `lists:prefix/2' to find
%% matching conditions. In version 1 this type was replaced with a prefix tree
%% which improves lookup time when the reverse index contains many entries.
-type applied_changes() :: #{khepri_path:native_path() =>
{create, khepri:node_props()} |
{update, khepri:node_props()} |
delete}.
%% Internal index of the per-node changes which happened during a traversal.
%% This is used when the tree is walked back up to determine the list of tree
%% nodes to remove after some keep_while condition evaluates to false.
-type walk_down_the_tree_fun() ::
fun((khepri_path:native_path(),
tree_node() | {interrupted, any(), map()},
Acc :: any()) ->
ok(tree_node() | keep | delete, any()) |
khepri:error()).
%% Function called to handle a node found (or an error) and used in {@link
%% walk_down_the_tree/6}.
-type ok(Type1, Type2) :: {ok, Type1, Type2}.
-type ok(Type1, Type2, Type3) :: {ok, Type1, Type2, Type3}.
-export_type([tree_node/0,
tree_v0/0,
tree_v1/0,
tree/0,
keep_while_conds_map/0,
keep_while_conds_revidx_v0/0,
keep_while_conds_revidx_v1/0,
keep_while_conds_revidx/0,
applied_changes/0]).
%% -------------------------------------------------------------------
%% Tree node functions.
%% -------------------------------------------------------------------
-spec new() -> tree().
new() ->
#tree{}.
-spec get_root(Tree) -> Root when
Tree :: khepri_tree:tree(),
Root :: khepri_tree:tree_node().
get_root(#tree{root = Root}) ->
Root.
-spec get_keep_while_conds(Tree) -> KeepWhileConds when
Tree :: khepri_tree:tree(),
KeepWhileConds :: khepri_tree:keep_while_conds_map().
get_keep_while_conds(#tree{keep_while_conds = KeepWhileConds}) ->
KeepWhileConds.
-spec assert_equal(Tree1, Tree2) -> ok when
Tree1 :: khepri_tree:tree(),
Tree2 :: khepri_tree:tree().
assert_equal(#tree{} = Tree1, #tree{} = Tree2) ->
?assertEqual(Tree1, Tree2),
ok.
-spec create_node_record(Payload) -> Node when
Payload :: khepri_payload:payload(),
Node :: tree_node().
%% @private
create_node_record(Payload) ->
#node{props = ?INIT_NODE_PROPS,
payload = Payload}.
-spec set_node_payload(Node, Payload) -> Node when
Node :: tree_node(),
Payload :: khepri_payload:payload().
%% @private
set_node_payload(#node{payload = Payload} = Node, Payload) ->
Node;
set_node_payload(#node{props = #{payload_version := DVersion} = Stat} = Node,
Payload) ->
Stat1 = Stat#{payload_version => DVersion + 1},
Node#node{props = Stat1, payload = Payload}.
-spec remove_node_payload(Node) -> Node when
Node :: tree_node().
%% @private
remove_node_payload(
#node{payload = ?NO_PAYLOAD} = Node) ->
Node;
remove_node_payload(
#node{props = #{payload_version := DVersion} = Stat} = Node) ->
Stat1 = Stat#{payload_version => DVersion + 1},
Node#node{props = Stat1, payload = khepri_payload:none()}.
-spec add_node_child(Node, ChildName, Child) -> Node when
Node :: tree_node(),
Child :: tree_node(),
ChildName :: khepri_path:component().
add_node_child(#node{props = #{child_list_version := CVersion} = Stat,
child_nodes = Children} = Node,
ChildName, Child) ->
Children1 = Children#{ChildName => Child},
Stat1 = Stat#{child_list_version => CVersion + 1},
Node#node{props = Stat1, child_nodes = Children1}.
-spec update_node_child(Node, ChildName, Child) -> Node when
Node :: tree_node(),
Child :: tree_node(),
ChildName :: khepri_path:component().
update_node_child(#node{child_nodes = Children} = Node, ChildName, Child) ->
Children1 = Children#{ChildName => Child},
Node#node{child_nodes = Children1}.
-spec remove_node_child(Node, ChildName) -> Node when
Node :: tree_node(),
ChildName :: khepri_path:component().
remove_node_child(#node{props = #{child_list_version := CVersion} = Stat,
child_nodes = Children} = Node,
ChildName) ->
?assert(maps:is_key(ChildName, Children)),
Stat1 = Stat#{child_list_version => CVersion + 1},
Children1 = maps:remove(ChildName, Children),
Node#node{props = Stat1, child_nodes = Children1}.
-spec remove_node_child_nodes(Node) -> Node when
Node :: tree_node().
remove_node_child_nodes(
#node{child_nodes = Children} = Node) when Children =:= #{} ->
Node;
remove_node_child_nodes(
#node{props = #{child_list_version := CVersion} = Stat} = Node) ->
Stat1 = Stat#{child_list_version => CVersion + 1},
Node#node{props = Stat1, child_nodes = #{}}.
-spec gather_node_props(Node, TreeOptions) -> NodeProps when
Node :: tree_node(),
TreeOptions :: khepri:tree_options(),
NodeProps :: khepri:node_props().
gather_node_props(#node{props = #{payload_version := PVersion,
child_list_version := CVersion},
payload = Payload,
child_nodes = Children},
#{props_to_return := WantedProps}) ->
lists:foldl(
fun
(payload_version, Acc) ->
Acc#{payload_version => PVersion};
(child_list_version, Acc) ->
Acc#{child_list_version => CVersion};
(child_list_length, Acc) ->
Acc#{child_list_length => maps:size(Children)};
(child_names, Acc) ->
Acc#{child_names => maps:keys(Children)};
(payload, Acc) ->
case Payload of
#p_data{data = Data} -> Acc#{data => Data};
#p_sproc{sproc = Fun} -> Acc#{sproc => Fun};
_ -> Acc
end;
(has_payload, Acc) ->
case Payload of
#p_data{data = _} -> Acc#{has_data => true};
#p_sproc{sproc = _} -> Acc#{is_sproc => true};
_ -> Acc
end;
(raw_payload, Acc) ->
Acc#{raw_payload => Payload};
(_Unknown, Acc) ->
%% We ignore props we don't know about. It might be a new one in
%% a future version of the machine.
Acc
end, #{}, WantedProps);
gather_node_props(#node{}, _Options) ->
#{}.
gather_node_props_for_error(Node) ->
gather_node_props(Node, #{props_to_return => ?DEFAULT_PROPS_TO_RETURN}).
-spec reset_versions(Node) -> Node when
Node :: tree_node().
%% @private
reset_versions(#node{props = Stat} = CurrentNode) ->
Stat1 = Stat#{payload_version => ?INIT_DATA_VERSION,
child_list_version => ?INIT_CHILD_LIST_VERSION},
CurrentNode#node{props = Stat1}.
-spec squash_version_bumps(OldNode, NewNode) -> Node when
OldNode :: tree_node(),
NewNode :: tree_node(),
Node :: tree_node().
%% @private
squash_version_bumps(
#node{props = #{payload_version := DVersion,
child_list_version := CVersion}},
#node{props = #{payload_version := DVersion,
child_list_version := CVersion}} = CurrentNode) ->
CurrentNode;
squash_version_bumps(
#node{props = #{payload_version := OldDVersion,
child_list_version := OldCVersion}},
#node{props = #{payload_version := NewDVersion,
child_list_version := NewCVersion} = Stat} = CurrentNode) ->
DVersion = case NewDVersion > OldDVersion of
true -> OldDVersion + 1;
false -> OldDVersion
end,
CVersion = case NewCVersion > OldCVersion of
true -> OldCVersion + 1;
false -> OldCVersion
end,
Stat1 = Stat#{payload_version => DVersion,
child_list_version => CVersion},
CurrentNode#node{props = Stat1}.
squash_version_bumps_after_keep_while(
Path,
#node{props = #{child_list_version := CVersion} = Props} = Node,
AppliedChanges) ->
ChildPathLength = length(Path) + 1,
WasModified = maps:fold(
fun
(P, {create, _NP}, false) ->
lists:prefix(Path, P) andalso
length(P) =:= ChildPathLength;
(_P, _TaNP, Acc) ->
Acc
end, false, AppliedChanges),
case WasModified of
false ->
Node;
true ->
CVersion1 = CVersion - 1,
?assert(CVersion1 >= 1),
Props1 = Props#{child_list_version => CVersion1},
Node#node{props = Props1}
end.
%% -------------------------------------------------------------------
%% Keep-while functions.
%% -------------------------------------------------------------------
-spec to_absolute_keep_while(BasePath, KeepWhile) -> AbsKeepWhile when
BasePath :: khepri_path:native_path(),
KeepWhile :: khepri_condition:native_keep_while(),
AbsKeepWhile :: khepri_condition:native_keep_while().
%% @private
to_absolute_keep_while(BasePath, KeepWhile) ->
maps:fold(
fun(Path, Cond, Acc) ->
AbsPath = khepri_path:abspath(Path, BasePath),
Acc#{AbsPath => Cond}
end, #{}, KeepWhile).
-spec are_keep_while_conditions_met(Tree, KeepWhile) -> Ret when
Tree :: tree(),
KeepWhile :: khepri_condition:native_keep_while(),
Ret :: true | {false, any()}.
%% @private
are_keep_while_conditions_met(_, KeepWhile)
when KeepWhile =:= #{} ->
true;
are_keep_while_conditions_met(Tree, KeepWhile) ->
TreeOptions = #{props_to_return => [payload,
payload_version,
child_list_version,
child_list_length]},
maps:fold(
fun
(Path, Condition, true) ->
case find_matching_nodes(Tree, Path, TreeOptions) of
{ok, Result} when Result =/= #{} ->
are_keep_while_conditions_met1(Result, Condition);
{ok, Result}
when Result =:= #{} andalso
Condition =:= #if_node_exists{exists = false} ->
%% The path pattern of the `keep_while' condition
%% matched no tree nodes. The condition indicates the
%% target node/pattern should not exist, therefore the
%% condition is met.
true;
{ok, _} ->
{false, {pattern_matches_no_nodes, Path}};
{error, Reason} ->
{false, Reason}
end;
(_, _, False) ->
False
end, true, KeepWhile).
are_keep_while_conditions_met1(Result, Condition) ->
maps:fold(
fun
(Path, NodeProps, true) ->
khepri_condition:is_met(Condition, Path, NodeProps);
(_, _, False) ->
False
end, true, Result).
is_keep_while_condition_met_on_self(
#tree{keep_while_conds = KeepWhileConds}, Path, Node) ->
case KeepWhileConds of
#{Path := #{Path := Condition}} ->
khepri_condition:is_met(Condition, Path, Node);
_ ->
true
end.
-spec update_keep_while_conds(Tree, Watcher, KeepWhile) -> NewTree when
Tree :: khepri_tree:tree(),
Watcher :: khepri_path:native_path(),
KeepWhile :: khepri_condition:native_keep_while(),
NewTree :: khepri_tree:tree().
update_keep_while_conds(Tree, Watcher, KeepWhile) ->
AbsKeepWhile = to_absolute_keep_while(Watcher, KeepWhile),
Tree1 = update_keep_while_conds_revidx(Tree, Watcher, AbsKeepWhile),
KeepWhileConds = get_keep_while_conds(Tree1),
KeepWhileConds1 = KeepWhileConds#{Watcher => AbsKeepWhile},
Tree1#tree{keep_while_conds = KeepWhileConds1}.
-spec update_keep_while_conds_revidx(Tree, Watcher, KeepWhile) -> NewTree when
Tree :: tree(),
Watcher :: khepri_path:native_path(),
KeepWhile :: khepri_condition:native_keep_while(),
NewTree :: tree().
update_keep_while_conds_revidx(
#tree{keep_while_conds_revidx = KeepWhileCondsRevIdx} = Tree,
Watcher, KeepWhile) ->
case is_v1_keep_while_conds_revidx(KeepWhileCondsRevIdx) of
true ->
update_keep_while_conds_revidx_v1(Tree, Watcher, KeepWhile);
false ->
update_keep_while_conds_revidx_v0(Tree, Watcher, KeepWhile)
end.
is_v1_keep_while_conds_revidx(KeepWhileCondsRevIdx) ->
khepri_prefix_tree:is_prefix_tree(KeepWhileCondsRevIdx).
update_keep_while_conds_revidx_v0(
#tree{keep_while_conds = KeepWhileConds,
keep_while_conds_revidx = KeepWhileCondsRevIdx} = Tree,
Watcher, KeepWhile) ->
%% First, clean up reversed index where a watched path isn't watched
%% anymore in the new keep_while.
OldWatcheds = maps:get(Watcher, KeepWhileConds, #{}),
KeepWhileCondsRevIdx1 = maps:fold(
fun(Watched, _, KWRevIdx) ->
Watchers = maps:get(Watched, KWRevIdx),
Watchers1 = maps:remove(Watcher, Watchers),
case maps:size(Watchers1) of
0 -> maps:remove(Watched, KWRevIdx);
_ -> KWRevIdx#{Watched => Watchers1}
end
end, KeepWhileCondsRevIdx, OldWatcheds),
%% Then, record the watched paths.
KeepWhileCondsRevIdx2 = maps:fold(
fun(Watched, _, KWRevIdx) ->
Watchers = maps:get(Watched, KWRevIdx, #{}),
Watchers1 = Watchers#{Watcher => ok},
KWRevIdx#{Watched => Watchers1}
end, KeepWhileCondsRevIdx1, KeepWhile),
Tree#tree{keep_while_conds_revidx = KeepWhileCondsRevIdx2}.
update_keep_while_conds_revidx_v1(
#tree{keep_while_conds = KeepWhileConds,
keep_while_conds_revidx = KeepWhileCondsRevIdx} = Tree,
Watcher, KeepWhile) ->
%% First, clean up reversed index where a watched path isn't watched
%% anymore in the new keep_while.
OldWatcheds = maps:get(Watcher, KeepWhileConds, #{}),
KeepWhileCondsRevIdx1 = maps:fold(
fun(Watched, _, KWRevIdx) ->
khepri_prefix_tree:update(
fun(Watchers) ->
Watchers1 = maps:remove(
Watcher, Watchers),
case maps:size(Watchers1) of
0 -> ?NO_PAYLOAD;
_ -> Watchers1
end
end, Watched, KWRevIdx)
end, KeepWhileCondsRevIdx, OldWatcheds),
%% Then, record the watched paths.
KeepWhileCondsRevIdx2 = maps:fold(
fun(Watched, _, KWRevIdx) ->
khepri_prefix_tree:update(
fun (?NO_PAYLOAD) ->
#{Watcher => ok};
(Watchers) ->
Watchers#{Watcher => ok}
end, Watched, KWRevIdx)
end, KeepWhileCondsRevIdx1, KeepWhile),
Tree#tree{keep_while_conds_revidx = KeepWhileCondsRevIdx2}.
%% -------------------------------------------------------------------
%% Find matching nodes.
%% -------------------------------------------------------------------
-spec find_matching_nodes(Tree, PathPattern, TreeOptions) ->
Ret when
Tree :: tree(),
PathPattern :: khepri_path:native_pattern(),
TreeOptions :: khepri:tree_options(),
Ret :: khepri_machine:write_ret().
%% @private
find_matching_nodes(Tree, PathPattern, TreeOptions) ->
fold(
Tree, PathPattern,
fun collect_node_props_cb/3, #{},
TreeOptions).
-spec collect_node_props_cb(Path, NodeProps, Map) ->
Ret when
Path :: khepri_path:native_path(),
NodeProps :: khepri:node_props(),
Map :: khepri:node_props_map(),
Ret :: Map.
%% @private
collect_node_props_cb(Path, NodeProps, Map) when is_map(Map) ->
Map#{Path => NodeProps}.
-spec count_node_cb(Path, NodeProps, Count) ->
Ret when
Path :: khepri_path:native_path(),
NodeProps :: khepri:node_props(),
Count :: non_neg_integer(),
Ret :: Count.
%% @private
count_node_cb(_Path, _NodeProps, Count) when is_integer(Count) ->
Count + 1.
-spec fold(Tree, PathPattern, Fun, Acc, TreeOptions) ->
Ret when
Tree :: tree(),
PathPattern :: khepri_path:native_pattern(),
Fun :: khepri:fold_fun(),
Acc :: khepri:fold_acc(),
TreeOptions :: khepri:tree_options(),
Ret :: khepri:ok(Acc) | khepri:error().
%% @doc Folds the given `Fun' over each tree node which matches the path
%% pattern.
%%
%% @private
fold(Tree, PathPattern, Fun, Acc, TreeOptions) ->
WalkFun = fun(Path, Node, Acc1) ->
find_matching_nodes_cb(
Path, Node, Fun, Acc1, TreeOptions)
end,
Ret = walk_down_the_tree(
Tree, PathPattern, TreeOptions, WalkFun, Acc),
case Ret of
{ok, NewTree, _AppliedChanges, Acc2} ->
?assertEqual(Tree, NewTree),
{ok, Acc2};
Error ->
Error
end.
find_matching_nodes_cb(Path, #node{} = Node, Fun, Acc, TreeOptions) ->
NodeProps = gather_node_props(Node, TreeOptions),
Acc1 = Fun(Path, NodeProps, Acc),
{ok, keep, Acc1};
find_matching_nodes_cb(
_,
{interrupted, node_not_found = Reason, Info},
_Fun, _Acc,
#{expect_specific_node := true}) ->
%% If we are collecting node properties (the result is a map) and the path
%% targets a specific node which is not found, we return an error.
%%
%% If we are counting nodes, that's fine and the next function clause will
%% run. The walk won't be interrupted.
Reason1 = ?khepri_error(Reason, Info),
{error, Reason1};
find_matching_nodes_cb(_, {interrupted, _, _}, _, Acc, _) ->
{ok, keep, Acc}.
%% -------------------------------------------------------------------
%% Delete matching nodes.
%% -------------------------------------------------------------------
-spec delete_matching_nodes(Tree, PathPattern, AppliedChanges, TreeOptions) ->
Ret when
Tree :: khepri_tree:tree(),
PathPattern :: khepri_path:pattern(),
AppliedChanges :: applied_changes(),
TreeOptions :: khepri:tree_options(),
Ret :: {ok, NewTree, NewAppliedChanges, Result} | khepri:error(),
NewTree :: khepri_tree:tree(),
NewAppliedChanges :: applied_changes(),
Result :: any().
delete_matching_nodes(Tree, PathPattern, AppliedChanges, TreeOptions) ->
Fun = fun(Path, Node, Result) ->
delete_matching_nodes_cb(
Path, Node, TreeOptions, explicit, Result)
end,
walk_down_the_tree(
Tree, PathPattern, TreeOptions, AppliedChanges, Fun, #{}).
delete_matching_nodes_cb(
[] = Path, #node{} = Node, TreeOptions, DeleteReason, Result) ->
Result1 = add_deleted_node_to_result(
Path, Node, TreeOptions, DeleteReason, Result),
Node1 = remove_node_payload(Node),
Node2 = remove_node_child_nodes(Node1),
{ok, Node2, Result1};
delete_matching_nodes_cb(
Path, #node{} = Node, TreeOptions, DeleteReason, Result) ->
Result1 = add_deleted_node_to_result(
Path, Node, TreeOptions, DeleteReason, Result),
{ok, delete, Result1};
delete_matching_nodes_cb(
_, {interrupted, _, _}, _Options, _DeleteReason, Result) ->
{ok, keep, Result}.
add_deleted_node_to_result(
Path, Node, TreeOptions, explicit = DeleteReason, Result) ->
add_deleted_node_to_result1(
Path, Node, TreeOptions, DeleteReason, Result);
add_deleted_node_to_result(
_Path, _Node, #{return_indirect_deletes := false}, _DeleteReason,
Result) ->
Result;
add_deleted_node_to_result(
Path, Node, TreeOptions, DeleteReason, Result) ->
add_deleted_node_to_result1(
Path, Node, TreeOptions, DeleteReason, Result).
add_deleted_node_to_result1(Path, Node, TreeOptions, DeleteReason, Result) ->
NodeProps1 = gather_node_props(Node, TreeOptions),
NodeProps2 = maybe_add_delete_reason_prop(
NodeProps1, TreeOptions, DeleteReason),
Result#{Path => NodeProps2}.
maybe_add_delete_reason_prop(
NodeProps, #{props_to_return := WantedProps}, DeleteReason) ->
case lists:member(delete_reason, WantedProps) of
true ->
NodeProps#{delete_reason => DeleteReason};
false ->
NodeProps
end;
maybe_add_delete_reason_prop(NodeProps, _TreeOptions, _DeleteReason) ->
NodeProps.
%% -------------------------------------------------------------------
%% Insert or update a tree node.
%% -------------------------------------------------------------------
-spec insert_or_update_node(
Tree, PathPattern, Payload, PutOptions, TreeOptions) -> Ret when
Tree :: khepri_tree:tree(),
PathPattern :: khepri_path:native_pattern(),
Payload :: khepri_payload:payload(),
PutOptions :: khepri:put_options(),
TreeOptions :: khepri:tree_options(),
NodeProps :: khepri:node_props_map(),
AppliedChanges :: applied_changes(),
Ret :: ok(Tree, AppliedChanges, NodeProps) | khepri:error().
insert_or_update_node(
Tree, PathPattern, Payload, #{keep_while := KeepWhile}, TreeOptions) ->
Fun = fun(Path, Node, {_, _, Result}) ->
Ret = insert_or_update_node_cb(
Path, Node, Payload, TreeOptions, Result),
case Ret of
{ok, Node1, Result1} when Result1 =/= #{} ->
AbsKeepWhile0 = to_absolute_keep_while(
Path, KeepWhile),
AbsKeepWhile1 = (
filter_out_irrelevant_keep_while_conds(
Path, Node, AbsKeepWhile0)),
KWMet = are_keep_while_conditions_met(
Tree, AbsKeepWhile1),
case KWMet of
true ->
{ok, Node1, {updated, Path, Result1}};
{false, Reason} ->
%% The keep_while condition is not met. We
%% can't insert the node and return an
%% error instead.
NodeName = case Path of
[] -> ?KHEPRI_ROOT_NODE;
_ -> lists:last(Path)
end,
Reason1 = ?khepri_error(
keep_while_conditions_not_met,
#{node_name => NodeName,
node_path => Path,
keep_while_reason => Reason}),
{error, Reason1}
end;
{ok, Node1, Result1} ->
{ok, Node1, {updated, Path, Result1}};
Error ->
Error
end
end,
Ret1 = walk_down_the_tree(
Tree, PathPattern, TreeOptions, Fun, {undefined, [], #{}}),
case Ret1 of
{ok, Tree1, AppliedChanges, {updated, ResolvedPath, Ret2}} ->
Tree2 = update_keep_while_conds(
Tree1, ResolvedPath, KeepWhile),
{ok, Tree2, AppliedChanges, Ret2};
Error ->
?assertMatch({error, _}, Error),
Error
end;
insert_or_update_node(
Tree, PathPattern, Payload, _PutOptions, TreeOptions) ->
Fun = fun(Path, Node, Result) ->
insert_or_update_node_cb(
Path, Node, Payload, TreeOptions, Result)
end,
walk_down_the_tree(Tree, PathPattern, TreeOptions, Fun, #{}).
insert_or_update_node_cb(
Path, #node{} = Node, Payload, TreeOptions, Result) ->
case maps:is_key(Path, Result) of
false ->
%% After a node is modified, we collect properties from the updated
%% `#node{}', except the payload which is from the old one.
Node1 = set_node_payload(Node, Payload),
NodeProps = gather_node_props_from_old_and_new_nodes(
Node, Node1, TreeOptions),
{ok, Node1, Result#{Path => NodeProps}};
true ->
{ok, Node, Result}
end;
insert_or_update_node_cb(
Path, {interrupted, node_not_found = Reason, Info}, Payload, TreeOptions,
Result) ->
%% We store the payload when we reached the target node only, not in the
%% parent nodes we have to create in between.
IsTarget = maps:get(node_is_target, Info),
case can_continue_update_after_node_not_found(Info) of
true when IsTarget ->
Node = create_node_record(Payload),
NodeProps = gather_node_props_from_old_and_new_nodes(
undefined, Node, TreeOptions),
{ok, Node, Result#{Path => NodeProps}};
true ->
Node = create_node_record(khepri_payload:none()),
{ok, Node, Result};
false ->
Reason1 = ?khepri_error(Reason, Info),
{error, Reason1}
end;
insert_or_update_node_cb(_, {interrupted, Reason, Info}, _, _, _) ->
Reason1 = ?khepri_error(Reason, Info),
{error, Reason1}.
filter_out_irrelevant_keep_while_conds(
Path, {interrupted, node_not_found, #{node_is_target := true}}, KeepWhile) ->
%% A `keep_while' condition on self is irrelevant if the node does not
%% exist yet.
KeepWhile1 = maps:remove(Path, KeepWhile),
%% Likewise for `keep_while' conditions that apply to children of the
%% node.
KeepWhile2 = maps:filter(
fun(KWPath, _) ->
not lists:prefix(Path, KWPath)
end, KeepWhile1),
KeepWhile2;
filter_out_irrelevant_keep_while_conds(
_Path, _Node, KeepWhile) ->
KeepWhile.
gather_node_props_from_old_and_new_nodes(OldNode, NewNode, TreeOptions) ->
OldNodeProps = case OldNode of
undefined ->
#{};
_ ->
gather_node_props(OldNode, TreeOptions)
end,
NewNodeProps0 = gather_node_props(NewNode, TreeOptions),
NewNodeProps1 = maps:remove(data, NewNodeProps0),
NewNodeProps2 = maps:remove(sproc, NewNodeProps1),
maps:merge(OldNodeProps, NewNodeProps2).
can_continue_update_after_node_not_found(#{condition := Condition}) ->
can_continue_update_after_node_not_found1(Condition);
can_continue_update_after_node_not_found(#{node_name := NodeName}) ->
can_continue_update_after_node_not_found1(NodeName).
can_continue_update_after_node_not_found1(ChildName)
when ?IS_KHEPRI_PATH_COMPONENT(ChildName) ->
true;
can_continue_update_after_node_not_found1(#if_node_exists{exists = false}) ->
true;
can_continue_update_after_node_not_found1(#if_all{conditions = Conds}) ->
lists:all(fun can_continue_update_after_node_not_found1/1, Conds);
can_continue_update_after_node_not_found1(#if_any{conditions = Conds}) ->
lists:any(fun can_continue_update_after_node_not_found1/1, Conds);
can_continue_update_after_node_not_found1(_) ->
false.
%% -------------------------------------------------------------------
%% Does path match.
%% -------------------------------------------------------------------
does_path_match(Path, PathPattern, Tree) ->
PathPattern1 = khepri_path:compile(PathPattern),
does_path_match(Path, PathPattern1, [], Tree).
does_path_match(PathRest, PathRest, _ReversedPath, _Tree) ->
true;
does_path_match([], _PathPatternRest, _ReversedPath, _Tree) ->
false;
does_path_match(_PathRest, [], _ReversedPath, _Tree) ->
false;
does_path_match(
[Component | Path], [Component | PathPattern], ReversedPath, Tree)
when ?IS_KHEPRI_PATH_COMPONENT(Component) ->
does_path_match(Path, PathPattern, [Component | ReversedPath], Tree);
does_path_match(
[Component | _Path], [Condition | _PathPattern], _ReversedPath, _Tree)
when ?IS_KHEPRI_PATH_COMPONENT(Component) andalso
?IS_KHEPRI_PATH_COMPONENT(Condition) ->
false;
does_path_match(
[Component | Path], [Condition | PathPattern], ReversedPath, Tree) ->
%% Query the tree node, required to evaluate the condition.
ReversedPath1 = [Component | ReversedPath],
CurrentPath = lists:reverse(ReversedPath1),
TreeOptions = #{expect_specific_node => true,
props_to_return => [payload,
payload_version,
child_list_version,
child_list_length]},
{ok, #{CurrentPath := Node}} = find_matching_nodes(
Tree,
lists:reverse([Component | ReversedPath]),
TreeOptions),
case khepri_condition:is_met(Condition, Component, Node) of
true ->
ConditionMatchesGrandchildren =
case khepri_condition:applies_to_grandchildren(Condition) of
true ->
does_path_match(
Path, [Condition | PathPattern], ReversedPath1, Tree);
false ->
false
end,
ConditionMatchesGrandchildren orelse
does_path_match(Path, PathPattern, ReversedPath1, Tree);
{false, _} ->
false
end.
%% -------------------------------------------------------------------
%% Tree traversal functions.
%% -------------------------------------------------------------------
-record(walk,
{tree :: #tree{},
node :: #node{} | delete,
path_pattern :: khepri_path:native_pattern(),
tree_options :: khepri:tree_options(),
%% Used to remember the path of the node the walk is currently on.
reversed_path = [] :: khepri_path:native_path(),
%% Used to update parents up in the tree in a tail-recursive function.
reversed_parent_tree = [] :: [#node{} | {#node{}, child_created}],
'fun' :: walk_down_the_tree_fun(),
fun_acc :: any(),
applied_changes :: applied_changes()}).
-spec walk_down_the_tree(
Tree, PathPattern, TreeOptions, Fun, FunAcc) -> Ret when
Tree :: tree(),
PathPattern :: khepri_path:native_pattern(),
TreeOptions :: khepri:tree_options(),
Fun :: walk_down_the_tree_fun(),
FunAcc :: any(),
AppliedChanges :: applied_changes(),
Ret :: ok(Tree, AppliedChanges, FunAcc) | khepri:error().
%% @private
walk_down_the_tree(Tree, PathPattern, TreeOptions, Fun, FunAcc) ->
walk_down_the_tree(Tree, PathPattern, TreeOptions, #{}, Fun, FunAcc).
-spec walk_down_the_tree(
Tree, PathPattern, TreeOptions,
AppliedChanges, Fun, FunAcc) -> Ret when
Tree :: tree(),
PathPattern :: khepri_path:native_pattern(),
TreeOptions :: khepri:tree_options(),
AppliedChanges :: applied_changes(),
Fun :: walk_down_the_tree_fun(),
FunAcc :: any(),
Ret :: ok(Tree, AppliedChanges, FunAcc) | khepri:error().
%% @private
walk_down_the_tree(
Tree, PathPattern, TreeOptions, AppliedChanges, Fun, FunAcc) ->
CompiledPathPattern = khepri_path:compile(PathPattern),
TreeOptions1 = case TreeOptions of
#{expect_specific_node := true} ->
TreeOptions;
_ ->
TreeOptions#{expect_specific_node => false}
end,
Walk = #walk{tree = Tree,
node = Tree#tree.root,
path_pattern = CompiledPathPattern,
tree_options = TreeOptions1,
'fun' = Fun,
fun_acc = FunAcc,
applied_changes = AppliedChanges},
case walk_down_the_tree1(Walk) of
{ok, #walk{tree = Tree1,
node = Root1,
applied_changes = AppliedChanges1,
fun_acc = FunAcc1}} ->
Tree2 = Tree1#tree{root = Root1},
{ok, Tree2, AppliedChanges1, FunAcc1};
Error ->
Error
end.
-spec walk_down_the_tree1(Walk) -> Ret when
Walk :: #walk{},
Ret :: khepri:ok(Walk) | khepri:error().
%% @private
walk_down_the_tree1(
#walk{path_pattern = [?KHEPRI_ROOT_NODE | PathPattern],
reversed_path = ReversedPath,
reversed_parent_tree = ReversedParentTree} = Walk) ->
?assertEqual([], ReversedPath),
?assertEqual([], ReversedParentTree),
Walk1 = Walk#walk{path_pattern = PathPattern},
walk_down_the_tree1(Walk1);
walk_down_the_tree1(
#walk{path_pattern = [?THIS_KHEPRI_NODE | PathPattern]} = Walk) ->
Walk1 = Walk#walk{path_pattern = PathPattern},
walk_down_the_tree1(Walk1);
walk_down_the_tree1(
#walk{path_pattern = [?PARENT_KHEPRI_NODE | PathPattern],
reversed_path = [_CurrentName | ReversedPath],
reversed_parent_tree = [ParentNode0 | ReversedParentTree]} = Walk) ->
ParentNode = case ParentNode0 of
{PN, child_created} -> PN;
_ -> ParentNode0
end,
Walk1 = Walk#walk{node = ParentNode,
path_pattern = PathPattern,
reversed_path = ReversedPath,
reversed_parent_tree = ReversedParentTree},
walk_down_the_tree1(Walk1);
walk_down_the_tree1(
#walk{path_pattern = [?PARENT_KHEPRI_NODE | PathPattern],
reversed_path = [],
reversed_parent_tree = []} = Walk) ->
%% The path tries to go above the root node, like "cd /..". In this case,
%% we stay on the root node.
Walk1 = Walk#walk{path_pattern = PathPattern},
walk_down_the_tree1(Walk1);
walk_down_the_tree1(
#walk{node = #node{child_nodes = Children} = CurrentNode,
path_pattern = [ChildName | PathPattern],
reversed_path = ReversedPath,
reversed_parent_tree = ReversedParentTree} = Walk)
when ?IS_KHEPRI_NODE_ID(ChildName) ->
Walk1 = Walk#walk{path_pattern = PathPattern,
reversed_path = [ChildName | ReversedPath],
reversed_parent_tree =
[CurrentNode | ReversedParentTree]},
case Children of
#{ChildName := Child} ->
Walk2 = Walk1#walk{node = Child},
walk_down_the_tree1(Walk2);
_ ->
interrupted_walk_down(
Walk1, node_not_found,
#{node_name => ChildName,
node_path => lists:reverse([ChildName | ReversedPath])})
end;
walk_down_the_tree1(
#walk{node = #node{child_nodes = Children} = CurrentNode,
path_pattern = [Condition | PathPattern],
tree_options = #{expect_specific_node := true},
reversed_path = ReversedPath,
reversed_parent_tree = ReversedParentTree} = Walk)
when ?IS_KHEPRI_CONDITION(Condition) ->
%% We distinguish the case where the condition must be verified against the
%% current node (i.e. the node name is ?KHEPRI_ROOT_NODE or
%% ?THIS_KHEPRI_NODE in the condition) instead of its child nodes.
SpecificNode = khepri_path:component_targets_specific_node(Condition),
case SpecificNode of
{true, NodeName}
when NodeName =:= ?KHEPRI_ROOT_NODE orelse
NodeName =:= ?THIS_KHEPRI_NODE ->
CurrentName = special_component_to_node_name(
NodeName, ReversedPath),
CondMet = khepri_condition:is_met(
Condition, CurrentName, CurrentNode),
case CondMet of
true ->
Walk1 = Walk#walk{path_pattern = PathPattern},
walk_down_the_tree1(Walk1);
{false, Cond} ->
Walk1 = Walk#walk{path_pattern = PathPattern},
interrupted_walk_down(
Walk1, mismatching_node,
#{node_name => CurrentName,
node_path => lists:reverse(ReversedPath),
node_props => gather_node_props_for_error(CurrentNode),
condition => Cond})
end;
{true, ChildName} when ChildName =/= ?PARENT_KHEPRI_NODE ->
Walk1 = Walk#walk{path_pattern = PathPattern,
reversed_path = [ChildName | ReversedPath],
reversed_parent_tree =
[CurrentNode | ReversedParentTree]},
case Children of
#{ChildName := Child} ->
Walk2 = Walk1#walk{node = Child},
CondMet = khepri_condition:is_met(
Condition, ChildName, Child),
case CondMet of
true ->
walk_down_the_tree1(Walk2);
{false, Cond} ->
interrupted_walk_down(
Walk2, mismatching_node,
#{node_name => ChildName,
node_path => lists:reverse(
[ChildName | ReversedPath]),
node_props => gather_node_props_for_error(
Child),
condition => Cond})
end;
_ ->
interrupted_walk_down(
Walk1, node_not_found,
#{node_name => ChildName,
node_path => lists:reverse([ChildName | ReversedPath]),
condition => Condition})
end;
{true, ?PARENT_KHEPRI_NODE} ->
%% TODO: Support calling Fun() with parent node based on
%% conditions on child nodes.
BadPathPattern =
lists:reverse(ReversedPath, [Condition | PathPattern]),
Exception = ?khepri_exception(
condition_targets_parent_node,
#{path => BadPathPattern,
condition => Condition}),
{error, Exception};
false ->
%% The caller expects that the path matches a single specific node
%% (no matter if it exists or not), but the condition could match
%% several nodes.
BadPathPattern =
lists:reverse(ReversedPath, [Condition | PathPattern]),
Exception = ?khepri_exception(
possibly_matching_many_nodes_denied,
#{path => BadPathPattern}),
{error, Exception}
end;
walk_down_the_tree1(
#walk{node = #node{child_nodes = Children} = CurrentNode,
path_pattern = [Condition | PathPattern] = WholePathPattern,
tree_options = #{expect_specific_node := false} = TreeOptions,
reversed_path = ReversedPath,
reversed_parent_tree = ReversedParentTree,
applied_changes = AppliedChanges} = Walk)
when ?IS_KHEPRI_CONDITION(Condition) ->
%% Like with "expect_specific_node =:= true" function clause above, We
%% distinguish the case where the condition must be verified against the
%% current node (i.e. the node name is ?KHEPRI_ROOT_NODE or
%% ?THIS_KHEPRI_NODE in the condition) instead of its child nodes.
SpecificNode = khepri_path:component_targets_specific_node(Condition),
case SpecificNode of
{true, NodeName}
when NodeName =:= ?KHEPRI_ROOT_NODE orelse
NodeName =:= ?THIS_KHEPRI_NODE ->
CurrentName = special_component_to_node_name(
NodeName, ReversedPath),
CondMet = khepri_condition:is_met(
Condition, CurrentName, CurrentNode),
case CondMet of
true ->
Walk1 = Walk#walk{path_pattern = PathPattern},
walk_down_the_tree1(Walk1);
{false, _} ->
StartingNode = starting_node_in_rev_parent_tree(
ReversedParentTree, CurrentNode),
Walk1 = Walk#walk{node = StartingNode},
{ok, Walk1}
end;
{true, ?PARENT_KHEPRI_NODE} ->
%% TODO: Support calling Fun() with parent node based on
%% conditions on child nodes.
BadPathPattern =
lists:reverse(ReversedPath, [Condition | PathPattern]),
Exception = ?khepri_exception(
condition_targets_parent_node,
#{path => BadPathPattern,
condition => Condition}),
{error, Exception};
_ ->
%% There is a special case if the current node is the root node.
%% The caller can request that the root node's properties are
%% included. This is true by default if the path is `[]'. This
%% allows to get its props and payload atomically in a single
%% query.
IsRoot = ReversedPath =:= [],
IncludeRootProps = maps:get(
include_root_props, TreeOptions, false),
Ret0 = case IsRoot andalso IncludeRootProps of
true ->
Walk1 = Walk#walk{path_pattern = [],
reversed_path = [],
reversed_parent_tree = []},
walk_down_the_tree1(Walk1);
_ ->
{ok, Walk}
end,
%% The result of the first part (the special case for the root
%% node if relevant) is used as a starting point for handling all
%% child nodes.
Ret1 = maps:fold(
fun
(ChildName, Child,
{ok, Walk1}) ->
Walk2 = Walk1#walk{path_pattern =
WholePathPattern,
reversed_path = ReversedPath},
handle_branch(Walk2, ChildName, Child);
(_, _, Error) ->
Error
end, Ret0, Children),
case Ret1 of
{ok,
#walk{node = CurrentNode,
applied_changes = AppliedChanges} = Walk2} ->
%% The current node didn't change, no need to update the
%% tree and evaluate keep_while conditions.
StartingNode = starting_node_in_rev_parent_tree(
ReversedParentTree, CurrentNode),
Walk3 = Walk2#walk{node = StartingNode},
{ok, Walk3};
{ok, #walk{node = CurrentNode1} = Walk2} ->
CurrentNode2 = case CurrentNode1 of
CurrentNode ->
CurrentNode;
delete ->
CurrentNode1;
_ ->
%% Because of the loop, payload &
%% child list versions may have
%% been increased multiple times.
%% We want them to increase once
%% for the whole (atomic)
%% operation.
squash_version_bumps(
CurrentNode, CurrentNode1)
end,
Walk3 = Walk2#walk{node = CurrentNode2,
reversed_path = ReversedPath,
reversed_parent_tree =
ReversedParentTree},
walk_back_up_the_tree(Walk3);
Error ->
Error
end
end;
walk_down_the_tree1(
#walk{node = #node{} = CurrentNode,
path_pattern = [],
'fun' = Fun,
fun_acc = FunAcc,
reversed_path = ReversedPath,
reversed_parent_tree = ReversedParentTree} = Walk) ->
CurrentPath = lists:reverse(ReversedPath),
case Fun(CurrentPath, CurrentNode, FunAcc) of
{ok, keep, FunAcc1} ->
StartingNode = starting_node_in_rev_parent_tree(
ReversedParentTree, CurrentNode),
Walk1 = Walk#walk{node = StartingNode, fun_acc = FunAcc1},
{ok, Walk1};
{ok, delete, FunAcc1} ->
Walk1 = Walk#walk{node = delete, fun_acc = FunAcc1},
walk_back_up_the_tree(Walk1);
{ok, #node{} = CurrentNode1, FunAcc1} ->
Walk1 = Walk#walk{node = CurrentNode1, fun_acc = FunAcc1},
walk_back_up_the_tree(Walk1);
Error ->
Error
end.
-spec special_component_to_node_name(SpecialComponent, ReversedPath) ->
NodeName when
SpecialComponent :: ?KHEPRI_ROOT_NODE | ?THIS_KHEPRI_NODE,
ReversedPath :: khepri_path:native_path(),
NodeName :: khepri_path:component().
special_component_to_node_name(?KHEPRI_ROOT_NODE = NodeName, []) ->
NodeName;
special_component_to_node_name(?THIS_KHEPRI_NODE, [NodeName | _]) ->
NodeName;
special_component_to_node_name(?THIS_KHEPRI_NODE, []) ->
?KHEPRI_ROOT_NODE.
-spec starting_node_in_rev_parent_tree(ReversedParentTree) -> Node when
Node :: tree_node(),
ReversedParentTree :: [Node].
%% @private
starting_node_in_rev_parent_tree(ReversedParentTree) ->
hd(lists:reverse(ReversedParentTree)).
-spec starting_node_in_rev_parent_tree(ReversedParentTree, Node) -> Node when
Node :: tree_node(),
ReversedParentTree :: [Node].
%% @private
starting_node_in_rev_parent_tree([], CurrentNode) ->
CurrentNode;
starting_node_in_rev_parent_tree(ReversedParentTree, _) ->
starting_node_in_rev_parent_tree(ReversedParentTree).
-spec handle_branch(Walk, ChildName, Child) -> Ret when
Walk :: #walk{},
ChildName :: khepri_path:component(),
Child :: tree_node(),
Ret :: khepri:ok(Walk) | khepri:error().
%% @private
handle_branch(
#walk{node = CurrentNode,
path_pattern = [Condition | PathPattern] = WholePathPattern,
reversed_path = ReversedPath} = Walk,
ChildName, Child) ->
CondMet = khepri_condition:is_met(Condition, ChildName, Child),
Ret = case CondMet of
true ->
Walk1 = Walk#walk{node = Child,
path_pattern = PathPattern,
reversed_path = [ChildName | ReversedPath],
reversed_parent_tree = [CurrentNode]},
walk_down_the_tree1(Walk1);
{false, _} ->
{ok, Walk}
end,
case Ret of
{ok,
#walk{node = #node{child_nodes = Children} = CurrentNode1} = Walk2}
when is_map_key(ChildName, Children) ->
case khepri_condition:applies_to_grandchildren(Condition) of
false ->
Ret;
true ->
Walk3 = Walk2#walk{node = Child,
path_pattern = WholePathPattern,
reversed_path =
[ChildName | ReversedPath],
reversed_parent_tree = [CurrentNode1]},
walk_down_the_tree1(Walk3)
end;
{ok, _Walk} ->
%% The child node is gone, no need to test if the condition
%% applies to it or recurse.
Ret;
Error ->
Error
end.
-spec interrupted_walk_down(Walk, Reason, Info) -> Ret when
Walk :: #walk{},
Reason :: mismatching_node | node_not_found,
Info :: map(),
Ret :: khepri:ok(Walk) | khepri:error().
%% @private
interrupted_walk_down(
#walk{tree = Tree,
path_pattern = PathPattern,
reversed_path = ReversedPath,
reversed_parent_tree = ReversedParentTree,
'fun' = Fun,
fun_acc = FunAcc} = Walk,
Reason, Info) ->
NodePath = lists:reverse(ReversedPath),
IsTarget = khepri_path:realpath(PathPattern) =:= [],
Info1 = Info#{node_is_target => IsTarget},
ErrorTuple = {interrupted, Reason, Info1},
case Fun(NodePath, ErrorTuple, FunAcc) of
{ok, ToDo, FunAcc1}
when ToDo =:= keep orelse ToDo =:= delete ->
?assertNotEqual([], ReversedParentTree),
StartingNode = starting_node_in_rev_parent_tree(
ReversedParentTree),
Walk1 = Walk#walk{node = StartingNode,
fun_acc = FunAcc1},
{ok, Walk1};
{ok, #node{} = NewNode, FunAcc1} ->
ReversedParentTree1 =
case Reason of
node_not_found ->
%% We record the fact the child is a new node. This is used
%% to reset the child's stats if it got new payload or
%% child nodes at the same time.
[{hd(ReversedParentTree), child_created}
| tl(ReversedParentTree)];
_ ->
ReversedParentTree
end,
case PathPattern of
[] ->
%% We reached the target node. We could call
%% walk_down_the_tree1() again, but it would call Fun() a
%% second time.
Walk1 = Walk#walk{node = NewNode,
reversed_parent_tree =
ReversedParentTree1,
fun_acc = FunAcc1},
walk_back_up_the_tree(Walk1);
_ ->
%% We created a tree node automatically on our way to the
%% target. We want to add a `keep_while' condition for it
%% so it is automatically reclaimed when it becomes
%% useless (i.e., no payload and no child nodes).
Cond = #if_any{conditions =
[#if_child_list_length{count = {gt, 0}},
#if_has_payload{has_payload = true}]},
KeepWhile = #{NodePath => Cond},
Tree1 = update_keep_while_conds(Tree, NodePath, KeepWhile),
Walk1 = Walk#walk{tree = Tree1,
node = NewNode,
reversed_parent_tree =
ReversedParentTree1,
fun_acc = FunAcc1},
walk_down_the_tree1(Walk1)
end;
Error ->
Error
end.
-spec walk_back_up_the_tree(Walk) -> Ret when
Walk :: #walk{},
Ret :: khepri:ok(Walk).
%% @private
walk_back_up_the_tree(Walk) ->
walk_back_up_the_tree(Walk, #{}).
-spec walk_back_up_the_tree(Walk, AppliedChangesAcc) -> Ret when
Walk :: #walk{},
AppliedChangesAcc :: applied_changes(),
Ret :: khepri:ok(Walk).
%% @private
walk_back_up_the_tree(
#walk{node = delete,
reversed_path = [ChildName | ReversedPath] = WholeReversedPath,
reversed_parent_tree = [ParentNode | ReversedParentTree],
applied_changes = AppliedChanges} = Walk,
AppliedChangesAcc) ->
%% Evaluate keep_while of nodes which depended on ChildName (it is
%% removed) at the end of walk_back_up_the_tree().
Path = lists:reverse(WholeReversedPath),
AppliedChangesAcc1 = AppliedChangesAcc#{Path => delete},
%% Evaluate keep_while of parent node on itself right now (its child_count
%% has changed).
ParentNode1 = remove_node_child(ParentNode, ChildName),
%% If we are handling deletes as part of a `keep_while', it is possible
%% that this parent node's child list version was bumped if a node was
%% added in the first pass. In this case, we don't want to bump that
%% version twice (add + delete), but just once.
ParentNode2 = squash_version_bumps_after_keep_while(
lists:reverse(ReversedPath), ParentNode1, AppliedChanges),
Walk1 = Walk#walk{node = ParentNode2,
reversed_path = ReversedPath,
reversed_parent_tree = ReversedParentTree},
handle_keep_while_for_parent_update(Walk1, AppliedChangesAcc1);
walk_back_up_the_tree(
#walk{node = Child,
reversed_path = [ChildName | ReversedPath] = WholeReversedPath,
reversed_parent_tree =
[{ParentNode, child_created} | ReversedParentTree]} = Walk,
AppliedChangesAcc) ->
Child1 = reset_versions(Child),
%% Evaluate keep_while of nodes which depend on ChildName (it is
%% created) at the end of walk_back_up_the_tree().
Path = lists:reverse(WholeReversedPath),
TreeOptions = #{props_to_return => [payload,
payload_version,
child_list_version,
child_list_length]},
NodeProps = gather_node_props(Child1, TreeOptions),
AppliedChangesAcc1 = AppliedChangesAcc#{Path => {create, NodeProps}},
%% Evaluate keep_while of parent node on itself right now (its child_count
%% has changed).
ParentNode1 = add_node_child(ParentNode, ChildName, Child1),
Walk1 = Walk#walk{node = ParentNode1,
reversed_path = ReversedPath,
reversed_parent_tree = ReversedParentTree},
handle_keep_while_for_parent_update(Walk1, AppliedChangesAcc1);
walk_back_up_the_tree(
#walk{node = Child,
reversed_path = [ChildName | ReversedPath] = WholeReversedPath,
reversed_parent_tree = [ParentNode | ReversedParentTree]} = Walk,
AppliedChangesAcc) ->
%% Evaluate keep_while of nodes which depend on ChildName (it is
%% modified) at the end of walk_back_up_the_tree().
Path = lists:reverse(WholeReversedPath),
TreeOptions = #{props_to_return => [payload,
payload_version,
child_list_version,
child_list_length]},
InitialNodeProps = gather_node_props(
maps:get(ChildName, ParentNode#node.child_nodes),
TreeOptions),
NodeProps = gather_node_props(Child, TreeOptions),
AppliedChangesAcc1 = case NodeProps of
InitialNodeProps ->
AppliedChangesAcc;
_ ->
AppliedChangesAcc#{
Path => {update, NodeProps}}
end,
%% No need to evaluate keep_while of ParentNode, its child_count is
%% unchanged.
ParentNode1 = update_node_child(ParentNode, ChildName, Child),
Walk1 = Walk#walk{node = ParentNode1,
reversed_path = ReversedPath,
reversed_parent_tree = ReversedParentTree},
walk_back_up_the_tree(Walk1, AppliedChangesAcc1);
walk_back_up_the_tree(
#walk{reversed_path = [], %% <-- We reached the root (i.e. not a branch,
%% see handle_branch())
reversed_parent_tree = [],
applied_changes = AppliedChanges} = Walk,
AppliedChangesAcc) ->
AppliedChanges1 = merge_applied_changes(AppliedChanges, AppliedChangesAcc),
Walk1 = Walk#walk{applied_changes = AppliedChanges1},
handle_applied_changes(Walk1);
walk_back_up_the_tree(
#walk{reversed_parent_tree = [],
applied_changes = AppliedChanges} = Walk,
AppliedChangesAcc) ->
AppliedChanges1 = merge_applied_changes(AppliedChanges, AppliedChangesAcc),
Walk1 = Walk#walk{applied_changes = AppliedChanges1},
{ok, Walk1}.
handle_keep_while_for_parent_update(
#walk{reversed_parent_tree = [{_GrandParentNode, child_created} | _]} = Walk,
AppliedChangesAcc) ->
%% This is a freshly created node, we don't want to get rid of it right
%% away.
walk_back_up_the_tree(Walk, AppliedChangesAcc);
handle_keep_while_for_parent_update(
#walk{tree = Tree,
node = ParentNode,
reversed_path = ReversedPath,
tree_options = TreeOptions,
fun_acc = Acc} = Walk,
AppliedChangesAcc) ->
ParentPath = lists:reverse(ReversedPath),
IsMet = is_keep_while_condition_met_on_self(
Tree, ParentPath, ParentNode),
case IsMet of
true ->
%% We continue with the update.
walk_back_up_the_tree(Walk, AppliedChangesAcc);
{false, _Reason} ->
%% This parent node must be removed because it doesn't meet its
%% own keep_while condition. keep_while conditions for nodes
%% depending on this one will be evaluated with the recursion.
{ok, delete, Acc1} = delete_matching_nodes_cb(
ParentPath, ParentNode,
TreeOptions, keep_while, Acc),
Walk1 = Walk#walk{node = delete,
fun_acc = Acc1},
walk_back_up_the_tree(Walk1, AppliedChangesAcc)
end.
merge_applied_changes(AppliedChanges1, AppliedChanges2) ->
maps:fold(
fun
(Path, delete, KWA1) ->
KWA1#{Path => delete};
(Path, {_, _} = TypeAndNodeProps, KWA1) ->
case KWA1 of
#{Path := delete} -> KWA1;
_ -> KWA1#{Path => TypeAndNodeProps}
end
end, AppliedChanges1, AppliedChanges2).
handle_applied_changes(
#walk{applied_changes = AppliedChanges} = Walk)
when AppliedChanges =:= #{} ->
{ok, Walk};
handle_applied_changes(
#walk{tree = Tree,
node = Root,
applied_changes = AppliedChanges} = Walk) ->
Tree1 = Tree#tree{root = Root},
ToDelete = eval_keep_while_conditions(Tree1, AppliedChanges),
Tree2 = maps:fold(
fun
(RemovedPath, delete, T) ->
KW1 = maps:remove(
RemovedPath, T#tree.keep_while_conds),
T1 = update_keep_while_conds_revidx(T, RemovedPath, #{}),
T1#tree{keep_while_conds = KW1};
(_, {_, _}, T) ->
T
end, Tree1, AppliedChanges),
ToDelete1 = filter_and_sort_paths_to_delete(ToDelete, AppliedChanges),
Walk1 = Walk#walk{tree = Tree2},
remove_expired_nodes(ToDelete1, Walk1).
eval_keep_while_conditions(
#tree{keep_while_conds_revidx = KeepWhileCondsRevIdx} = Tree,
AppliedChanges) ->
%% AppliedChanges lists all nodes which were modified or removed. We
%% want to transform that into a list of nodes to remove.
%%
%% Those marked as `delete' in AppliedChanges are already gone. We
%% need to find the nodes which depended on them, i.e. their keep_while
%% condition is not met anymore. Note that removed nodes' child nodes are
%% gone as well and must be handled (they are not specified in
%% AppliedChanges).
%%
%% Those modified in AppliedChanges must be evaluated again to decide
%% if they should be removed.
case is_v1_keep_while_conds_revidx(KeepWhileCondsRevIdx) of
true ->
eval_keep_while_conditions_v1(Tree, AppliedChanges);
false ->
eval_keep_while_conditions_v0(Tree, AppliedChanges)
end.
eval_keep_while_conditions_v0(
#tree{keep_while_conds_revidx = KeepWhileCondsRevIdx} = Tree,
AppliedChanges) ->
maps:fold(
fun
(RemovedPath, delete, ToDelete) ->
maps:fold(
fun(Path, Watchers, ToDelete1) ->
case lists:prefix(RemovedPath, Path) of
true ->
eval_keep_while_conditions_after_removal(
Tree, Watchers, ToDelete1);
false ->
ToDelete1
end
end, ToDelete, KeepWhileCondsRevIdx);
(UpdatedPath, {_Type, NodeProps}, ToDelete) ->
case KeepWhileCondsRevIdx of
#{UpdatedPath := Watchers} ->
eval_keep_while_conditions_after_update(
Tree, UpdatedPath, NodeProps, Watchers, ToDelete);
_ ->
ToDelete
end
end, #{}, AppliedChanges).
eval_keep_while_conditions_v1(
#tree{keep_while_conds_revidx = KeepWhileCondsRevIdx} = Tree,
AppliedChanges) ->
maps:fold(
fun
(RemovedPath, delete, ToDelete) ->
khepri_prefix_tree:fold_prefixes_of(
fun(Watchers, ToDelete1) ->
eval_keep_while_conditions_after_removal(
Tree, Watchers, ToDelete1)
end, ToDelete, RemovedPath, KeepWhileCondsRevIdx);
(UpdatedPath, {_Type, NodeProps}, ToDelete) ->
Result = khepri_prefix_tree:find_path(
UpdatedPath, KeepWhileCondsRevIdx),
case Result of
{ok, Watchers} ->
eval_keep_while_conditions_after_update(
Tree, UpdatedPath, NodeProps, Watchers, ToDelete);
error ->
ToDelete
end
end, #{}, AppliedChanges).
eval_keep_while_conditions_after_update(
#tree{keep_while_conds = KeepWhileConds} = Tree,
UpdatedPath, NodeProps, Watchers, ToDelete) ->
maps:fold(
fun(Watcher, ok, ToDelete1) ->
KeepWhile = maps:get(Watcher, KeepWhileConds),
CondOnUpdated = maps:get(UpdatedPath, KeepWhile),
IsMet = khepri_condition:is_met(
CondOnUpdated, UpdatedPath, NodeProps),
case IsMet of
true ->
ToDelete1;
{false, _} ->
case are_keep_while_conditions_met(Tree, KeepWhile) of
true -> ToDelete1;
{false, _} -> ToDelete1#{Watcher => delete}
end
end
end, ToDelete, Watchers).
eval_keep_while_conditions_after_removal(
#tree{keep_while_conds = KeepWhileConds} = Tree,
Watchers, ToDelete) ->
maps:fold(
fun(Watcher, ok, ToDelete1) ->
KeepWhile = maps:get(Watcher, KeepWhileConds),
case are_keep_while_conditions_met(Tree, KeepWhile) of
true -> ToDelete1;
{false, _} -> ToDelete1#{Watcher => delete}
end
end, ToDelete, Watchers).
filter_and_sort_paths_to_delete(ToDelete, AppliedChanges) ->
Paths1 = lists:sort(
fun
(A, B) when length(A) =:= length(B) ->
A < B;
(A, B) ->
length(A) < length(B)
end,
maps:keys(ToDelete)),
Paths2 = lists:foldl(
fun(Path, Map) ->
case AppliedChanges of
#{Path := delete} ->
Map;
_ ->
case is_parent_being_removed(Path, Map) of
false -> Map#{Path => delete};
true -> Map
end
end
end, #{}, Paths1),
maps:keys(Paths2).
is_parent_being_removed([], _) ->
false;
is_parent_being_removed(Path, Map) ->
is_parent_being_removed1(lists:reverse(Path), Map).
is_parent_being_removed1([_ | Parent], Map) ->
case maps:is_key(lists:reverse(Parent), Map) of
true -> true;
false -> is_parent_being_removed1(Parent, Map)
end;
is_parent_being_removed1([], _) ->
false.
remove_expired_nodes([], Walk) ->
{ok, Walk};
remove_expired_nodes(
[PathToDelete | Rest],
#walk{tree = Tree,
applied_changes = AppliedChanges,
tree_options = TreeOptions,
fun_acc = Acc} = Walk) ->
%% See `delete_matching_nodes/4'. This is the same except that the
%% accumulator is passed through and the `DeleteReason' is provided as
%% `keep_while'.
Fun = fun(Path, Node, Result) ->
delete_matching_nodes_cb(
Path, Node, TreeOptions, keep_while, Result)
end,
Result = walk_down_the_tree(
Tree, PathToDelete, TreeOptions, AppliedChanges, Fun, Acc),
case Result of
{ok, Tree1, AppliedChanges1, Acc1} ->
AppliedChanges2 = merge_applied_changes(
AppliedChanges, AppliedChanges1),
Walk1 = Walk#walk{tree = Tree1,
node = Tree1#tree.root,
applied_changes = AppliedChanges2,
fun_acc = Acc1},
remove_expired_nodes(Rest, Walk1)
end.
%% -------------------------------------------------------------------
%% Conversion between tree versions.
%% -------------------------------------------------------------------
convert_tree(Tree, MacVer, MacVer) ->
Tree;
convert_tree(Tree, 0, 1) ->
Tree;
convert_tree(Tree, 1, 2) ->
%% In version 2 the reverse index for keep while conditions was converted
%% into a prefix tree. See the `keep_while_conds_revidx_v0()' and
%% `keep_while_conds_revidx_v1()` types.
#tree{keep_while_conds_revidx = KeepWhileCondsRevIdxV0} = Tree,
KeepWhileCondsRevIdxV1 = khepri_prefix_tree:from_map(
KeepWhileCondsRevIdxV0),
Tree#tree{keep_while_conds_revidx = KeepWhileCondsRevIdxV1}.