T5089: order nodes on configtree parsing from string

This is a conservative application of lexical_numeric ordering for
configtree: order nodes on instantiation in 'from_string'

3 files changed, 24 insertions, 11 deletions

diff --git a/src/vyos1x_parser.mly b/src/vyos1x_parser.mly
index ba1c5a7..8b2d7d8 100644
--- a/src/vyos1x_parser.mly
+++ b/src/vyos1x_parser.mly
@@ -20,6 +20,7 @@
     (* When merging nodes with values, append values of subsequent nodes to the
        first one *)
     let merge_data l r = {l with values=(List.append l.values r.values)}
+    let order = Util.lexical_numeric_compare
 %}
 
 %token <string> IDENTIFIER
@@ -66,7 +67,8 @@ node:
     {
         let node =
             Vytree.make_full {default_data with comment=comment} name [] in
-        let node = List.fold_left Vytree.adopt node (List.rev children) |> Vytree.merge_children merge_data in
+        let node = List.fold_left Vytree.adopt node (List.rev children) |> Vytree.merge_children merge_data order in
+        let node = Vytree.sort_children order node in
         try
             List.iter find_duplicate_children (Vytree.children_of_node node);
             node
@@ -87,8 +89,10 @@ tag_node:
       let outer_node = Vytree.make_full {default_data with tag=true} name [] in
       let inner_node =
           Vytree.make_full {default_data with comment=comment} tag [] in
-      let inner_node = List.fold_left Vytree.adopt inner_node (List.rev children) |> Vytree.merge_children merge_data in
+      let inner_node = List.fold_left Vytree.adopt inner_node (List.rev children) |> Vytree.merge_children merge_data order in
+      let inner_node = Vytree.sort_children order inner_node in
       let node = Vytree.adopt outer_node inner_node in
+      let node = Vytree.sort_children order node in
       try
           List.iter find_duplicate_children (Vytree.children_of_node inner_node);
           node
@@ -104,7 +108,8 @@ node_content: n = node { n } | n = leaf_node { n } | n = tag_node { n };
  | ns = list(node_content); EOF
  {
     let root = make "" in
-    let root = List.fold_left Vytree.adopt root (List.rev ns) |> Vytree.merge_children merge_data in
+    let root = List.fold_left Vytree.adopt root (List.rev ns) |> Vytree.merge_children merge_data order in
+    let root = Vytree.sort_children order root in
         try
             List.iter find_duplicate_children (Vytree.children_of_node root);
             root
diff --git a/src/vytree.ml b/src/vytree.ml
index 905f12b..bd73776 100644
--- a/src/vytree.ml
+++ b/src/vytree.ml
@@ -88,6 +88,14 @@ let rec insert ?(position=Default) ?(children=[]) node path data =
             let s = Printf.sprintf "Non-existent intermediary node: \'%s\'" name in
             raise (Insert_error s)
 
+let sorted_children_of_node cmp node =
+    let names = list_children node in
+    let names = List.sort cmp names in
+    List.map (find_or_fail node) names
+
+let sort_children cmp node =
+    {node with children = (sorted_children_of_node cmp node)}
+
 (** 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.
@@ -99,9 +107,11 @@ let rec insert ?(position=Default) ?(children=[]) node path data =
     may be normal and even expected, such as "ethernet eth0" and "ethernet eth1"
     in the "curly" format.
  *)
-let merge_children merge_data node =
+let merge_children merge_data cmp 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 *)
+       have the same name as N and merge their children into N, sorting
+       children by a comparison function cmp (string -> string -> int) on
+       node names *)
     let rec merge_into n ns =
         match ns with
         | [] -> n
@@ -110,6 +120,7 @@ let merge_children merge_data node =
                 let children = List.append n.children n'.children in
                 let data = merge_data n.data n'.data in
                 let n = {n with children=children; data=data} in
+                let n = sort_children cmp n in
                 merge_into n ns'
             else merge_into n ns'
     in
@@ -179,11 +190,6 @@ let children_of_path node path =
     let node' = get node path in
     list_children node'
 
-let sorted_children_of_node cmp node =
-    let names = list_children node in
-    let names = List.sort cmp names in
-    List.map (find_or_fail node) names
-
 let copy node old_path new_path =
     if exists node new_path then raise Duplicate_child else
     let child = get node old_path in
diff --git a/src/vytree.mli b/src/vytree.mli
index c30ff3f..377c9aa 100644
--- a/src/vytree.mli
+++ b/src/vytree.mli
@@ -25,7 +25,7 @@ val insert : ?position:position -> ?children:('a t list) -> 'a t -> string list
 
 val insert_multi_level : 'a -> 'a t -> string list -> string list -> 'a -> 'a t
 
-val merge_children : ('a -> 'a -> 'a) -> 'a t -> 'a t
+val merge_children : ('a -> 'a -> 'a) -> (string -> string -> int) -> 'a t -> 'a t
 
 val delete : 'a t -> string list -> 'a t
 
@@ -47,6 +47,8 @@ val children_of_path : 'a t -> string list -> string list
 
 val sorted_children_of_node : (string -> string -> int) -> 'a t -> ('a t) list
 
+val sort_children : (string -> string -> int) -> 'a t -> 'a t
+
 val copy : 'a t -> string list -> string list -> 'a t
 
 val move : 'a t -> string list -> position -> 'a t