diff options
| -rw-r--r-- | src/vytree.ml | 36 | ||||
| -rw-r--r-- | src/vytree.mli | 2 | ||||
| -rw-r--r-- | test/vytree_test.ml | 25 |
3 files changed, 63 insertions, 0 deletions
diff --git a/src/vytree.ml b/src/vytree.ml index 0e379ee..b27aea6 100644 --- a/src/vytree.ml +++ b/src/vytree.ml @@ -81,6 +81,42 @@ let rec insert ?(position=Default) node path data = | None -> raise (Insert_error "Path does not exist") +(** Given a node N check if it has children with duplicate names, + and merge subsequent children's children into the first child by + that name. + + While all insert functions maintain the "every child has unique name" + invariant, for nodes constructed manually with make/make_full and adopt + it may not hold, and constructing nodes this way is a sensible approach + for config parsing. Depending on the config format, duplicate node names + may be normal and even expected, such as "ethernet eth0" and "ethernet eth1" + in the "curly" format. + *) +let merge_children node = + (* Given a node N and a list of nodes NS, find all nodes in NS that + have the same name as N and merge their children into N *) + let rec merge_into n ns = + match ns with + | [] -> n + | n' :: ns' -> + if n.name = n'.name then + let children = List.append n.children n'.children in + let n = {n with children=children} in + merge_into n ns' + else merge_into n ns' + in + (* Given a list of nodes, for every node, find subsequent children with + the same name and merge them into the first node, then delete remaining + nodes from the list *) + let rec aux ns = + match ns with + | [] -> [] + | n :: ns -> + let n = merge_into n ns in + let ns = List.filter (fun x -> x.name <> n.name) ns in + n :: (aux ns) + in {node with children=(aux node.children)} + (* When inserting at a path that, entirely or partially, does not exist yet, create missing nodes on the way with default data *) let rec insert_multi_level default_data node path_done path_remaining data = diff --git a/src/vytree.mli b/src/vytree.mli index 6de65c5..d00d3ff 100644 --- a/src/vytree.mli +++ b/src/vytree.mli @@ -23,6 +23,8 @@ val insert : ?position:position -> 'a t -> string list -> 'a -> 'a t val insert_multi_level : 'a -> 'a t -> string list -> string list -> 'a -> 'a t +val merge_children : 'a t -> 'a t + val delete : 'a t -> string list -> 'a t val update : 'a t -> string list -> 'a -> 'a t diff --git a/test/vytree_test.ml b/test/vytree_test.ml index 5fb51ff..3cf3ae6 100644 --- a/test/vytree_test.ml +++ b/test/vytree_test.ml @@ -132,6 +132,29 @@ let test_get_data test_ctxt = let node = insert node ["foo"; "bar"] 42 in assert_equal (get_data node ["foo"; "bar"]) 42 +(* merge_children should have no effect if there are + no children with duplicate names *) +let test_merge_children_no_duplicates test_ctxt = + let node = make_full () "root" + [make_full () "foo" [make () "bar"]; + make () "bar"; + make_full () "baz" [make () "quuz"]] in + let node' = merge_children node in + assert_equal (list_children node') ["foo"; "bar"; "baz"] + + +(* If node has children with duplicate names, then + 1. Only the first should be left + 2. Children of all other nodes should be appended to its own *) +let test_merge_children_has_duplicates test_ctxt = + let node = make_full () "root" + [make_full () "foo" [make () "bar"]; + make () "quux"; + make_full () "foo" [make () "baz"]] in + let node' = merge_children node in + assert_equal (list_children node') ["foo"; "quux"]; + assert_equal (get node' ["foo"] |> list_children) ["bar"; "baz"] + let suite = "VyConf tree tests" >::: [ "test_make_node" >:: test_make_node; @@ -152,6 +175,8 @@ let suite = "test_exists_existent" >:: test_exists_existent; "test_exists_nonexistent" >:: test_exists_nonexistent; "test_get_data" >:: test_get_data; + "test_merge_children_has_duplicates" >:: test_merge_children_has_duplicates; + "test_merge_children_no_duplicates" >:: test_merge_children_no_duplicates; ] let () = |