Initial import of libraries from Vyconf and old libvyosconfig.

11 files changed, 815 insertions, 0 deletions

diff --git a/src/config_tree.ml b/src/config_tree.ml
new file mode 100644
index 0000000..463eb4b
--- /dev/null
+++ b/src/config_tree.ml
@@ -0,0 +1,214 @@
+type value_behaviour = AddValue | ReplaceValue
+
+exception Duplicate_value
+exception Node_has_no_value
+exception No_such_value
+exception Useless_set
+
+type config_node_data = {
+    values: string list;
+    comment: string option;
+    tag: bool;
+} [@@deriving yojson]
+
+type t = config_node_data Vytree.t [@@deriving yojson]
+
+let default_data = {
+    values = [];
+    comment = None;
+    tag = false;
+}
+
+let make name = Vytree.make default_data name
+
+let replace_value node path value =
+  let data = {default_data with values=[value]} in
+  Vytree.update node path data
+
+let add_value node path value =
+  let node' = Vytree.get node path in
+  let data = Vytree.data_of_node node' in
+  let values = data.values in
+  match (Vylist.find (fun x -> x = value) values) with
+  | Some _ -> raise Duplicate_value
+  | None ->
+    let values = values @ [value] in
+    Vytree.update node path ({data with values=values})
+
+let delete_value node path value =
+    let data = Vytree.data_of_node @@ Vytree.get node path in
+    let values = Vylist.remove (fun x -> x = value) data.values in
+    Vytree.update node path {data with values=values}
+
+let set_value node path value behaviour =
+    match behaviour with
+    | AddValue -> add_value node path value
+    | ReplaceValue -> replace_value node path value
+
+let set node path value behaviour =
+    if (Vytree.exists node path) then
+        (match value with
+         | None -> raise Useless_set
+         | Some v -> set_value node path v behaviour)
+    else
+        let path_existing = Vytree.get_existent_path node path in
+        let path_remaining = Vylist.complement path path_existing in
+        let values = match value with None -> [] | Some v -> [v] in
+        Vytree.insert_multi_level default_data node path_existing path_remaining {default_data with values=values}
+
+let get_values node path =
+    let node' = Vytree.get node path in
+    let data = Vytree.data_of_node node' in
+    data.values
+
+let get_value node path =
+    let values = get_values node path in
+    match values with
+    | [] -> raise Node_has_no_value
+    | x :: _ -> x
+
+let delete node path value =
+    match value with
+    | Some v ->
+        (let values = get_values node path in
+        if Vylist.in_list values v then
+        (match values with
+        | [_] -> Vytree.delete node path
+        | _ -> delete_value node path v)
+        else raise No_such_value)
+    | None ->
+	Vytree.delete node path
+
+let set_comment node path comment =
+    let data = Vytree.get_data node path in
+    Vytree.update node path {data with comment=comment}
+
+let get_comment node path =
+    let data = Vytree.get_data node path in
+    data.comment
+
+let set_tag node path tag =
+    let data = Vytree.get_data node path in
+    Vytree.update node path {data with tag=tag}
+
+let is_tag node path =
+    let data = Vytree.get_data node path in
+    data.tag
+
+module Renderer =
+struct
+    (* Rendering configs as set commands *)
+    let render_set_path path value =
+        let v = Printf.sprintf "\'%s\'" value in
+        List.append path [v] |> String.concat " " |> Printf.sprintf "set %s"
+
+    let rec render_commands path ct =
+        let new_path = List.append path [Vytree.name_of_node ct] in
+        let new_path_str = String.concat " " new_path in
+        let data = Vytree.data_of_node ct in
+        (* Get the node comment, if any *)
+        let comment = Util.default "" data.comment in 
+        let comment_cmd = (if comment = "" then "" else Printf.sprintf "comment %s \'%s\'" new_path_str comment) in
+        let child_names = Vytree.list_children ct in
+        (* Now handle the different cases for nodes with and without children *)
+        match child_names with
+        | [] ->
+             (* This is a leaf node *)
+             let values = List.map String.escaped data.values in
+             let cmds =
+                 begin
+                 match values with
+                 | [] ->
+                      (* Valueless leaf node *)
+                      String.concat " " new_path |> Printf.sprintf "set %s"
+                 | [v] ->
+                      (* Single value, just one command *)
+                      render_set_path new_path v
+                 | vs ->
+                      (* A leaf node with multiple values *)
+                      List.map (render_set_path new_path) vs |> String.concat "\n"
+                  end
+              in
+              if comment_cmd = "" then cmds else Printf.sprintf "%s\n%s" cmds comment_cmd
+        | _ :: _ ->
+            (* A node with children *)
+            let children = List.map (fun n -> Vytree.get ct [n]) child_names in
+            let rendered_children = List.map (render_commands new_path) children in
+            let cmds = String.concat "\n" rendered_children in
+            if comment_cmd = "" then cmds else Printf.sprintf "%s\n%s" cmds comment_cmd
+
+  (* Rendering config as a VyOS/EdgeOS config file *)
+  let make_indent indent level = String.make (level * indent) ' '
+
+  let render_values indent_str name values =
+    match values with
+    | [] -> Printf.sprintf "%s%s { }\n" indent_str name
+    | [v] -> Printf.sprintf "%s%s \"%s\"\n" indent_str name (String.escaped v)
+    | _  -> 
+      let rendered = List.map (fun s -> Printf.sprintf "%s%s \"%s\"" indent_str name (String.escaped s)) values in
+      let rendered = String.concat "\n" rendered in
+      Printf.sprintf "%s\n" rendered
+
+  let render_comment indent c =
+    match c with
+    | None -> ""
+    | Some c ->  Printf.sprintf "%s/* %s */\n" indent c
+
+  let rec render_node indent level node =
+    let indent_str = make_indent indent level in
+    let name = Vytree.name_of_node node in
+    let data = Vytree.data_of_node node in
+    let is_tag = data.tag in 
+    let comment = render_comment indent_str data.comment in
+    let values = render_values indent_str name data.values in
+    let children = Vytree.children_of_node node in
+    match children with
+    | [] -> Printf.sprintf "%s%s" comment values
+    | _ :: _ ->
+      if is_tag then 
+        begin
+          let inner = List.map (render_tag_node_child indent level name) children in
+          String.concat "" inner
+        end
+      else
+        begin
+          let inner = List.map (render_node indent (level + 1)) children in
+          let inner = String.concat "" inner in
+          Printf.sprintf "%s%s%s {\n%s%s}\n" comment indent_str name inner indent_str
+        end
+  and render_tag_node_child indent level parent node =
+    let indent_str = make_indent indent level in
+    let name = Vytree.name_of_node node in
+    let data = Vytree.data_of_node node in
+    let comment = render_comment indent_str data.comment in
+    let values = render_values indent_str name data.values in
+    let children = Vytree.children_of_node node in
+    match children with
+    (* This produces too much whitespace due to indent_str from values,
+       but the issue is cosmetic *)
+    | [] -> Printf.sprintf "%s%s%s %s" comment indent_str parent values
+    | _ ->
+        (* Exploiting the fact that immediate children of tag nodes are
+           never themselves tag nodes *)
+        let inner = List.map (render_node indent (level + 1)) children in
+        let inner = String.concat "" inner in
+        Printf.sprintf "%s%s%s %s {\n%s%s}\n" comment indent_str parent name inner indent_str
+
+  let render_config node =
+    let children = Vytree.children_of_node node in
+    let child_configs = List.map (render_node 4 0) children in
+    String.concat "" child_configs
+
+end (* Renderer *)
+
+let render_commands node path =
+    let node =
+	match path with
+        | [] -> node
+        | _ -> Vytree.get node path
+    in
+    let children = Vytree.children_of_node node in
+    let commands = List.map (Renderer.render_commands path) children in
+    String.concat "\n" commands
+
+let render_config = Renderer.render_config
diff --git a/src/config_tree.mli b/src/config_tree.mli
new file mode 100644
index 0000000..c01e299
--- /dev/null
+++ b/src/config_tree.mli
@@ -0,0 +1,38 @@
+type value_behaviour = AddValue | ReplaceValue
+
+exception Duplicate_value
+exception Node_has_no_value
+exception No_such_value
+exception Useless_set
+
+type config_node_data = {
+  values : string list;
+  comment : string option;
+  tag : bool;
+} [@@deriving yojson]
+
+type t = config_node_data Vytree.t [@@deriving yojson]
+
+val default_data : config_node_data
+
+val make : string -> t
+
+val set : t -> string list -> string option -> value_behaviour -> t
+
+val delete : t -> string list -> string option -> t
+
+val get_values : t -> string list -> string list
+
+val get_value : t -> string list -> string
+
+val set_comment : t -> string list -> string option -> t
+
+val get_comment : t -> string list -> string option
+
+val set_tag : t -> string list -> bool -> t
+
+val is_tag : t -> string list -> bool
+
+val render_commands : t -> string list -> string
+
+val render_config : t -> string
diff --git a/src/dune b/src/dune
new file mode 100644
index 0000000..7b39748
--- /dev/null
+++ b/src/dune
@@ -0,0 +1,10 @@
+(ocamllex vyos1x_lexer)
+(menhir
+ (flags --table)
+ (modules vyos1x_parser))
+
+(library
+ (name vyos1x)
+ (public_name vyos1x-config)
+ (libraries yojson menhirLib)
+ (preprocess (pps ppx_deriving_yojson)))
diff --git a/src/util.ml b/src/util.ml
new file mode 100644
index 0000000..c2ec4c4
--- /dev/null
+++ b/src/util.ml
@@ -0,0 +1,4 @@
+let default default_value opt =
+  match opt with
+  | None -> default_value
+  | Some value -> value
diff --git a/src/util.mli b/src/util.mli
new file mode 100644
index 0000000..5316e90
--- /dev/null
+++ b/src/util.mli
@@ -0,0 +1 @@
+val default : 'a -> 'a option -> 'a
diff --git a/src/vylist.ml b/src/vylist.ml
new file mode 100644
index 0000000..cd4a32e
--- /dev/null
+++ b/src/vylist.ml
@@ -0,0 +1,46 @@
+let rec find p xs =
+    match xs with
+    | [] -> None
+    | y :: ys -> if (p y) then (Some y)
+                 else find p ys
+
+let rec remove p xs =
+    match xs with
+    | [] -> []
+    | y :: ys -> if (p y) then ys
+                 else y :: (remove p ys)
+
+let rec replace p x xs =
+    match xs with
+    | [] -> raise Not_found
+    | y :: ys -> if (p y) then x :: ys
+                 else y :: (replace p x ys)
+
+let rec insert_before p x xs =
+    match xs with
+    | [] -> raise Not_found
+    | y :: ys -> if (p y) then x :: y :: ys
+                 else y :: (insert_before p x ys)
+
+let rec insert_after p x xs =
+    match xs with
+    | [] -> raise Not_found
+    | y :: ys -> if (p y) then y :: x :: ys
+                 else y :: (insert_after p x ys)
+
+let complement xs ys =
+    let rec aux xs ys =
+        match xs, ys with
+        | [], _ -> ys
+        | _, [] -> assert false (* Can't happen *)
+        | p :: ps, q :: qs -> if p = q then aux ps qs
+                              else []
+    in
+    if List.length xs < List.length ys then aux xs ys
+    else aux ys xs
+
+let in_list xs x =
+    let x' = find ((=) x) xs in
+    match x' with
+    | None -> false
+    | Some _ -> true
diff --git a/src/vylist.mli b/src/vylist.mli
new file mode 100644
index 0000000..9135bf6
--- /dev/null
+++ b/src/vylist.mli
@@ -0,0 +1,7 @@
+val find : ('a -> bool) -> 'a list -> 'a option
+val remove : ('a -> bool) -> 'a list -> 'a list
+val replace : ('a -> bool) -> 'a -> 'a list -> 'a list
+val insert_before : ('a -> bool) -> 'a -> 'a list -> 'a list
+val insert_after : ('a -> bool) -> 'a -> 'a list -> 'a	list
+val complement : 'a list -> 'a list -> 'a list
+val in_list : 'a list -> 'a -> bool
diff --git a/src/vyos1x_lexer.mll b/src/vyos1x_lexer.mll
new file mode 100644
index 0000000..a996642
--- /dev/null
+++ b/src/vyos1x_lexer.mll
@@ -0,0 +1,138 @@
+{
+
+open Vyos1x_parser
+
+exception Error of string
+
+(*
+
+The language of the VyOS 1.x config file has multiple ambiguities that
+make it not even context free.
+
+The main issue is lack of explicit statement separators, so if we ignore whitespace,
+a parser is left to guess if, for example
+
+address dhcp # leaf node with a value
+disable      # valueless leaf node
+
+is three valueless nodes, a valueless node followed by a node with a value,
+or a node with a value followed by a valueless node.
+
+The only cue is the newline, which means that newlines are sometimes significant,
+and sometimes they aren't.
+
+interfaces { # doesn't matter
+  ethernet 'eth0' { # doesn't matter
+    address '192.0.2.1/24' # significant!
+    disable # significant!
+
+    # empty line -- doesn't matter
+    hw-id 00:aa:bb:cc:dd:ee # significant!
+  } # doesn't matter
+}
+
+If there were explicit terminators (like we do in VyConf, or like JunOS does),
+the language would be context free. Enter the lexer hack: let's emit newlines only
+when they are significant, so that the parser can use them as terminators.
+
+The informal idea is that a newline is only significant if it follows a leaf node.
+So we need rules for finding out if we are inside a leaf node or not.
+
+These are the formal rules. A newline is significant if and only if
+1. Preceding token is an identifier
+2. Preceding token is a quoted string
+
+We set the vy_inside_node flag to true when we enter a leaf node and reset it when
+we reach the end of it.
+
+*)
+
+let vy_inside_node = ref false
+
+}
+
+rule token = parse
+| [' ' '\t' '\r']
+    { token lexbuf }
+| '\n'
+    { Lexing.new_line lexbuf; if !vy_inside_node then (vy_inside_node := false; NEWLINE) else token lexbuf }
+| '"'
+    { vy_inside_node := true; read_string (Buffer.create 16) lexbuf }
+| '''
+    { vy_inside_node := true; read_single_quoted_string (Buffer.create 16) lexbuf }
+| "/*"
+    { vy_inside_node := false; read_comment (Buffer.create 16) lexbuf }
+| '{'
+    { vy_inside_node := false; LEFT_BRACE }
+| '}'
+    { vy_inside_node := false; RIGHT_BRACE }
+| "//" [^ '\n']*
+    { token lexbuf }
+| [^ ' ' '\t' '\n' '\r' '{' '}' '"' ''' ]+ as s
+    { vy_inside_node := true; IDENTIFIER s}
+| eof
+    { EOF }
+| _
+{ raise (Error (Printf.sprintf "At offset %d: unexpected character.\n" (Lexing.lexeme_start lexbuf))) }
+
+and read_string buf =
+  parse
+  | '"'       { STRING (Buffer.contents buf) }
+  | '\\' '/'  { Buffer.add_char buf '/'; read_string buf lexbuf }
+  | '\\' '\\' { Buffer.add_char buf '\\'; read_string buf lexbuf }
+  | '\\' 'b'  { Buffer.add_char buf '\b'; read_string buf lexbuf }
+  | '\\' 'f'  { Buffer.add_char buf '\012'; read_string buf lexbuf }
+  | '\\' 'n'  { Buffer.add_char buf '\n'; read_string buf lexbuf }
+  | '\\' 'r'  { Buffer.add_char buf '\r'; read_string buf lexbuf }
+  | '\\' 't'  { Buffer.add_char buf '\t'; read_string buf lexbuf }
+  | '\\' '\'' { Buffer.add_char buf '\''; read_string buf lexbuf }
+  | '\\' '"' { Buffer.add_char buf '"'; read_string buf lexbuf }
+  | '\n'      { Lexing.new_line lexbuf; Buffer.add_char buf '\n'; read_string buf lexbuf }
+  | [^ '"' '\\']+
+    { Buffer.add_string buf (Lexing.lexeme lexbuf);
+      read_string buf lexbuf
+    }
+  | _ { raise (Error (Printf.sprintf "Illegal string character: %s" (Lexing.lexeme lexbuf))) }
+  | eof { raise (Error ("String is not terminated")) }
+
+and read_single_quoted_string buf =
+  parse
+  | '''       { STRING (Buffer.contents buf) }
+  | '\\' '/'  { Buffer.add_char buf '/'; read_string buf lexbuf }
+  | '\\' '\\' { Buffer.add_char buf '\\'; read_string buf lexbuf }
+  | '\\' 'b'  { Buffer.add_char buf '\b'; read_string buf lexbuf }
+  | '\\' 'f'  { Buffer.add_char buf '\012'; read_string buf lexbuf }
+  | '\\' 'n'  { Buffer.add_char buf '\n'; read_string buf lexbuf }
+  | '\\' 'r'  { Buffer.add_char buf '\r'; read_string buf lexbuf }
+  | '\\' 't'  { Buffer.add_char buf '\t'; read_string buf lexbuf }
+  | '\\' '\'' { Buffer.add_char buf '\''; read_string buf lexbuf }
+  | '\\' '"' { Buffer.add_char buf '"'; read_string buf lexbuf }
+  | '\n'      { Lexing.new_line lexbuf; Buffer.add_char buf '\n'; read_string buf lexbuf }
+  | [^ ''' '\\']+
+    { Buffer.add_string buf (Lexing.lexeme lexbuf);
+      read_single_quoted_string buf lexbuf
+    }
+  | _ { raise (Error (Printf.sprintf "Illegal string character: %s" (Lexing.lexeme lexbuf))) }
+  | eof { raise (Error ("String is not terminated")) }
+
+and read_comment buf =
+  parse
+  | "*/"
+      { COMMENT (Buffer.contents buf) }
+  | _
+      { Buffer.add_string buf (Lexing.lexeme lexbuf);
+        read_comment buf lexbuf
+      }
+
+(*
+
+If you are curious how the original parsers handled the issue: they did not.
+The CStore parser cheated by reading data from command definitions to resolve
+the ambiguities, which made it impossible to use in standalone config
+manipulation programs like migration scripts.
+
+The XorpConfigParser could not tell tag nodes' name and tag from
+a leaf node with a value, which made it impossible to manipulate
+tag nodes or change values properly.
+
+*)
diff --git a/src/vyos1x_parser.mly b/src/vyos1x_parser.mly
new file mode 100644
index 0000000..c31552f
--- /dev/null
+++ b/src/vyos1x_parser.mly
@@ -0,0 +1,115 @@
+%{
+    open Config_tree
+
+    exception Duplicate_child of (string * string)
+
+    (* Used for checking if after merging immediate children,
+       any of them have duplicate children inside,
+       e.g. "interfaces { ethernet eth0 {...} ethernet eth0 {...} }" *)
+    let find_duplicate_children n =
+        let rec aux xs =
+            let xs = List.sort compare xs in
+            match xs with
+            | [] | [_] -> ()
+            | x :: x' :: xs ->
+                if x = x' then raise (Duplicate_child (Vytree.name_of_node n, x))
+                else aux (x' :: xs)
+        in
+        aux @@ Vytree.list_children n
+
+    (* 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)}
+%}
+
+%token <string> IDENTIFIER
+%token <string> STRING
+%token <string> COMMENT
+%token LEFT_BRACE
+%token RIGHT_BRACE
+%token NEWLINE
+%token EOF
+
+%start <Config_tree.t> config
+%%
+
+(* If there are multiple comments before a node, consider the last one its real comment *)
+comments: 
+    cs = list(COMMENT) { match cs with [] -> None | _ -> Some (List.rev cs |> List.hd |> String.trim) }
+
+value:
+  | v = STRING
+    { v }
+  | v = IDENTIFIER
+    { v }
+;
+
+
+leaf_node_body:
+  | comment = comments;
+    name = IDENTIFIER; value = value;
+    { Vytree.make_full {default_data with values=[value]; comment=comment} name []}
+  | comment = comments;
+    name = IDENTIFIER; (* valueless node *)
+    { Vytree.make_full {default_data with comment=comment} name [] }
+;
+
+leaf_node:
+  | n = leaf_node_body; NEWLINE;
+    { n }
+  | n = leaf_node_body; EOF;
+    { n }
+
+node:
+  | comment = comments;
+    name = IDENTIFIER; LEFT_BRACE; children = list(node_content); RIGHT_BRACE;
+    {
+        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
+        try
+            List.iter find_duplicate_children (Vytree.children_of_node node);
+            node
+        with
+        | Duplicate_child (child, dup) ->
+            failwith (Printf.sprintf "Node \"%s %s\" has two children named \"%s\"" name child dup)
+    }
+;
+
+(* XXX: for the config to be loadable with the old CStore backend, what was formatted as a tag node
+   in the original config, must remain formatted that way.
+   This is why the tag field is set.     
+ *)
+tag_node:
+  | comment = comments;
+    name = IDENTIFIER; tag = value; LEFT_BRACE; children = list(node_content); RIGHT_BRACE
+  {
+      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 node = Vytree.adopt outer_node inner_node in
+      try
+          List.iter find_duplicate_children (Vytree.children_of_node inner_node);
+          node
+      with
+      | Duplicate_child (child, dup) ->
+          failwith (Printf.sprintf "Node \"%s %s %s\" has two children named \"%s\"" name tag child dup)
+  }
+
+node_content: n = node { n } | n = leaf_node { n } | n = tag_node { n };
+
+
+%public config:
+ | ns = list(node_content); EOF
+ {
+    let root = make "root" in
+    let root = List.fold_left Vytree.adopt root (List.rev ns) |> Vytree.merge_children merge_data in
+        try
+            List.iter find_duplicate_children (Vytree.children_of_node root);
+            root
+        with
+        | Duplicate_child (child, dup) ->
+            failwith (Printf.sprintf "Node \"%s\" has two children named \"%s\"" child dup)
+  }
+;
diff --git a/src/vytree.ml b/src/vytree.ml
new file mode 100644
index 0000000..a3e2750
--- /dev/null
+++ b/src/vytree.ml
@@ -0,0 +1,192 @@
+type 'a	t = {
+    name: string;
+    data: 'a;
+    children: 'a t list
+} [@@deriving yojson]
+
+type position = Before of string | After of string | End | Default
+
+exception Empty_path
+exception Duplicate_child
+exception Nonexistent_path
+exception Insert_error of string
+
+let make data name = { name = name; data = data; children = [] }
+
+let make_full data name children = { name = name; data = data; children = children }
+
+let name_of_node node = node.name
+let data_of_node node = node.data
+let children_of_node node = node.children
+
+let insert_immediate ?(position=Default) node name data children =
+    let new_node = make_full data name children in
+    let children' =
+        match position with
+        | Default -> new_node :: node.children
+        | End -> node.children @ [new_node]
+        | Before s -> Vylist.insert_before (fun x -> x.name = s) new_node node.children
+        | After s -> Vylist.insert_after (fun x -> x.name = s) new_node node.children
+    in { node with children = children' }
+
+let delete_immediate node name =
+    let children' = Vylist.remove (fun x -> x.name = name) node.children in
+    { node with children = children' }
+
+let adopt node child =
+    { node with children = child :: node.children }
+
+let replace node child =
+    let children = node.children in
+    let name = child.name in
+    let children' = Vylist.replace (fun x -> x.name = name) child children in
+    { node with children = children' }
+
+let replace_full node child name =
+    let children = node.children in
+    let children' = Vylist.replace (fun x -> x.name = name) child children in
+    { node with children = children' }
+
+let find node name =
+    Vylist.find (fun x -> x.name = name) node.children
+
+let find_or_fail node name =
+    let child = find node name in
+    match child with
+    | None -> raise Nonexistent_path
+    | Some child' -> child'
+
+let list_children node =
+    List.map (fun x -> x.name) node.children
+
+let rec do_with_child fn node path =
+    match path with
+    | [] -> raise Empty_path
+    | [name] -> fn node name
+    | name :: names ->
+        let next_child = find_or_fail node name in
+        let new_node = do_with_child fn next_child names in
+        replace node new_node
+
+let rec insert ?(position=Default) ?(children=[]) node path data =
+    match path with
+    | [] -> raise Empty_path
+    | [name] ->
+       (let last_child = find node name in
+        match last_child with
+        | None -> insert_immediate ~position:position node name data children
+        | (Some _) -> raise Duplicate_child)
+    | name :: names ->
+        let next_child = find node name in
+        match next_child with
+        | Some next_child' ->
+            let new_node = insert ~position:position ~children:children next_child' names data in
+            replace node new_node
+        | 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 merge_data 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 data = merge_data n.data n'.data in
+                let n = {n with children=children; data=data} 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 =
+    match path_remaining with
+    | [] | [_] -> insert node (path_done @ path_remaining) data
+    | name :: names ->
+        let path_done = path_done @ [name] in
+        let node = insert node path_done default_data in
+        insert_multi_level default_data node path_done names data
+
+let delete node path =
+    do_with_child delete_immediate node path
+
+let rename node path newname =
+    let rename_immediate newname' node' name' =
+        let child = find_or_fail node' name' in
+        let child = { child with name=newname' } in
+        replace_full node' child name'
+    in do_with_child (rename_immediate newname) node path
+
+let update node path data =
+    let update_data data' node' name =
+        let child = find_or_fail node' name in
+        let child = { child with data=data' } in
+        replace node' child
+    in do_with_child (update_data data) node path
+
+let rec get node path =
+    match path with
+    | [] -> raise Empty_path
+    | [name] -> find_or_fail node name
+    | name :: names -> get (find_or_fail node name) names
+
+let get_data node path = data_of_node @@ get node path
+
+let exists node path =
+    try ignore (get node path); true
+    with Nonexistent_path -> false
+
+let get_existent_path node path =
+    let rec aux node path acc =
+        match path with
+        | [] -> acc
+        | name :: names ->
+            let child = find node name in
+            match child with
+            | None -> acc
+            | Some c -> aux c names (name :: acc)
+    in List.rev (aux node path [])
+
+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
+    insert ~position:End ~children:child.children node new_path child.data
+
+let move node path position =
+    let child = get node path in
+    let node = delete node path in
+    insert ~position:position ~children:child.children node path child.data
diff --git a/src/vytree.mli b/src/vytree.mli
new file mode 100644
index 0000000..451e130
--- /dev/null
+++ b/src/vytree.mli
@@ -0,0 +1,50 @@
+type 'a t [@@deriving yojson]
+
+exception Empty_path
+exception Duplicate_child
+exception Nonexistent_path
+exception Insert_error of string
+
+type position = Before of string | After of string | End | Default
+
+val make : 'a -> string -> 'a t
+val make_full : 'a -> string -> ('a t) list -> 'a t
+
+val name_of_node : 'a t -> string
+val data_of_node : 'a t -> 'a
+val children_of_node : 'a t -> 'a t list
+
+val find : 'a t -> string -> 'a t option
+val find_or_fail : 'a t -> string -> 'a t
+
+val adopt : 'a t -> 'a t -> 'a t
+
+val insert : ?position:position -> ?children:('a t list) -> '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 -> 'a -> 'a) -> 'a t -> 'a t
+
+val delete : 'a t -> string list -> 'a t
+
+val update : 'a t -> string list -> 'a -> 'a t
+
+val rename : 'a t -> string list -> string -> 'a t
+
+val list_children : 'a t -> string list
+
+val get : 'a t -> string list -> 'a t
+
+val get_existent_path : 'a t -> string list -> string list
+
+val get_data : 'a t -> string list -> 'a
+
+val exists : 'a t -> string list -> bool
+
+val children_of_path : 'a t -> string list -> string list
+
+val sorted_children_of_node : (string -> string -> int) -> 'a t -> ('a t) list
+
+val copy : 'a t -> string list -> string list -> 'a t
+
+val move : 'a t -> string list -> position -> 'a t