(test-group
 "Test history DAG serialisation"

 ;; A test graph for fold-history** is represented
 ;; as a list of nodes, each of which is a three-element list:
 ;; key, mtime, list of parent keys.

 (define ((get-parents graph) key)
   (third (assoc key graph)))

 (define ((get-props graph) key)
   (list (cons 'mtime (second (assoc key graph)))))

 (define (kons key name props knil)
   (cons (cons key name) knil))

 (define (test-fold name graph root-key expected)
   (test name
         expected
         (reverse ;; Reverse, as fold results are back to front
          (map (lambda (element)
                 ; Each kons-result element is (key . name)
                 ; The names are nasty timestamps,
                 ; so let's make it (key . suffix)
                 ; as that's what the expected results are.
                 ; the magic number to string-drop
                 ; is the length of "YYYY-MM-DD HH:MM:SS"
                 (let ((key (car element))
                       (name (cdr element)))
                   (cons key (string-drop name 19)))
                 )
           (fold-history**
            (get-parents graph)
            (get-props graph)
            root-key
            kons
            '())))))

 ;; Simple linear cases

 (test-fold "Single Element"
            '(("a" 1 ())) "a" '(("a" . "")))

 (test-fold "Two elements, ignore 1"
            '(("a" 1 ())
              ("b" 2 ("a"))) "a" '(("a" . "")))

 (test-fold "Two elements"
            '(("a" 1 ())
              ("b" 2 ("a"))) "b" '(("b" . "")
                                   ("a" . "")))

 (test-fold "Three elements"
            '(("a" 1 ())
              ("b" 2 ("a"))
              ("c" 3 ("b"))) "c" '(("c" . "")
                                   ("b" . "")
                                   ("a" . "")))

 ;; Merges

 (test-fold "Simple merge"
            '(("a" 1 ())
              ("b" 2 ())
              ("c" 3 ("a" "b"))) "c" '(("c" . "") 
                                       ("b" . "-1")
                                       ("a" . "")))

 (test-fold "Simple merge, out of order"
            '(("a" 1 ())
              ("b" 2 ())
              ("c" 3 ("b" "a"))) "c" '(("c" . "") 
                                       ("b" . "-1")
                                       ("a" . "")))

 (test-fold "Three-way merge"
            '(("a" 1 ())
              ("b" 2 ())
              ("c" 3 ())
              ("d" 4 ("a" "b" "c"))) "d" '(("d" . "")
                                           ("c" . "-1")
                                           ("b" . "-2")
                                           ("a" . "")))

 (test-fold "Long three-way merge"
            '(("a" 1 ())
              ("b" 2 ())
              ("c" 3 ())
              ("d" 4 ("a"))
              ("e" 5 ("b"))
              ("f" 6 ("c"))
              ("g" 7 ("f" "d" "e")))
            "g"
            '(("g" . "")
              ("f" . "-1")
              ("e" . "-2")
              ("d" . "-3")
              ("c" . "-1")
              ("b" . "-2")
              ("a" . "")))

 ;; Forks
 ;; (which have to merge again to create a SINGLE history)

 (test-fold "Simple fork/merge"
            '(("a" 1 ())
              ("b" 2 ("a"))
              ("c" 3 ("a"))
              ("d" 4 ("b" "c"))) "d" '(("d" . "")
                                       ("c" . "-1")
                                       ("b" . "-2")
                                       ("a" . "")))

 ;; a->(b,c), b->(d,e) (c,e)->f, (d,f)->g
 (test-fold "Double fork/merge"
            '(("a" 1 ())
              ("b" 2 ("a"))
              ("c" 3 ("a"))
              ("d" 4 ("b"))
              ("e" 5 ("b"))
              ("f" 6 ("e" "c"))
              ("g" 7 ("d" "f")))
            "g"
            '(("g" . "")
              ("f" . "-1")
              ("e" . "-2")
              ("d" . "-3")
              ("c" . "-4")
              ("b" . "-5")
              ("a" . "")))

 ;; a->(b,c) b->d c->e a->f (d,e,f)->g
 (test-fold "Fat fork/merge"
            '(("a" 1 ())
              ("b" 2 ("a"))
              ("c" 3 ("a"))
              ("d" 4 ("b"))
              ("e" 5 ("c"))
              ("f" 6 ("a"))
              ("g" 7 ("e" "d" "f")))
            "g"
            '(("g" . "") 
              ("f" . "-1")
              ("e" . "-2")
              ("d" . "-3")
              ("c" . "-2")
              ("b" . "-3")
              ("a" . ""))))