From 8377563a0d0d20f1e7f67b7cfcec4c27a02b7a3f Mon Sep 17 00:00:00 2001
From: Daniil Baturin <daniil@baturin.org>
Date: Mon, 9 Jan 2017 11:52:13 +0700
Subject: T245: add Vytree.merge_children function for de-duplicating children
 that share the same name by merging subsequent nodes into the first one. Bad
 thing: the comments of the outer nodes will be lost, but then again one
 should attach them to the inner node anyway, in non-pathological cases.

---
 src/vytree.ml       | 36 ++++++++++++++++++++++++++++++++++++
 src/vytree.mli      |  2 ++
 test/vytree_test.ml | 25 +++++++++++++++++++++++++
 3 files changed, 63 insertions(+)

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 () =
-- 
cgit v1.2.3