From 5904738b98e9756e362ed9a81f2d831621493311 Mon Sep 17 00:00:00 2001
From: Linus Nordberg <linus@nordu.net>
Date: Fri, 25 Apr 2014 13:25:04 +0200
Subject: Allow for empty hash trees.

---
 src/ht.erl | 39 ++++++++++++++++++++++++++++++---------
 1 file changed, 30 insertions(+), 9 deletions(-)

diff --git a/src/ht.erl b/src/ht.erl
index 68c3c67..5f41991 100644
--- a/src/ht.erl
+++ b/src/ht.erl
@@ -9,23 +9,24 @@
                tree :: tree()}).                % the tree
 
 -type head() :: #head{}.
--type tree() :: inner() | leaf().
+-type tree() :: inner() | leaf() | undefined.
 -type leaf() :: #leaf{}.
 -type inner() :: #inner{}.
 
 -export_type([head/0, tree/0, inner/0, leaf/0]).
--export([create/1, append/2, tree_hash/1, tree_version/1,
+-export([create/0, append/2, tree_hash/1, tree_version/1,
         audit_path/2]).
 
 %% Public interface.
--spec create(iolist() | binary()) -> head().
-create(D) ->
-    mkhead(1, mkleaf(D)).
+-spec create() -> head().
+create() ->
+    mkhead(0, undefined).
 
 -spec tree_hash(head()) -> binary();
                (tree()) -> binary().
 tree_hash(#head{tree=T}) ->
     case T of
+        undefined -> hashfun(<<>>);
         #inner{hash=H} -> H;
         #leaf{hash=H} -> H
     end.
@@ -55,14 +56,18 @@ tree_version(#head{version=Ver}) ->
 %% Example: N=4 (100) => l=2, the root (soon not to be root).
 %% Example: N=5 (101) => l=0, the rightmost leaf.
 %% Example: N=6 (110) => l=1, the last and rightmost inner node.
--spec append(head(), leaf()) -> head().
+-spec append(head(), leaf() | iolist() | binary()) -> head().
+append(#head{version = 0}, Leaf) when is_record(Leaf, leaf) ->
+    mkhead(0, Leaf);
 append(Head, Leaf) when is_record(Leaf, leaf) ->
     N = Head#head.version,
     %Depth = depth(Head),
     Level = fls(N),
     RBD = rightbranchdepth(Head#head.tree),
     %io:format("N=~p, Depth=~p, Level=~p, RBD=~p~n", [N, Depth, Level, RBD]),
-    #head{version = N + 1, tree = append(Head#head.tree, Leaf, RBD-Level-1)}.
+    #head{version = N + 1, tree = append(Head#head.tree, Leaf, RBD-Level-1)};
+append(Head, Data) ->
+    append(Head, mkleaf(Data)).
 
 -spec append(tree(), tree(), pos_integer()) -> tree().
 append(Dest, Newtree, _) when is_record(Dest, leaf) ->
@@ -158,6 +163,18 @@ rightbranchdepth(Tree, Acc) ->
 
 %%%%%%%%%%%%%%%%%%%%
 %% Internal tests.
+
+-define(TEST_VECTOR_TREES,
+        [<<148,242,40,0,3,172,180,106,111,230,146,161,32,40,128,38,103,8,194,
+           102,72,68, 126,70,108,47,8,216,208,146,178,107>>]).
+basic_tree_test_() ->
+    TestVectorTree = #leaf{hash = hd(?TEST_VECTOR_TREES)},
+    [?_assertEqual(#head{version = 0, tree = undefined},
+                   create()),
+     ?_assertEqual(#head{version = 1, tree = TestVectorTree},
+                   create("a foo is a bar"))].
+
+%% Test vectors from certificate-transparency/src/python/ct/crypto/merkle_test.py.
 -define(EMPTY_HASH, "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855").
 -define(TEST_VECTOR_LEAVES, ["", "\x00", "\x10", " !", "01", "@ABC", "PQRSTUVW", "`abcdefghijklmno"]).
 -define(TEST_VECTOR_HASHES, ["6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d",
@@ -169,8 +186,8 @@ rightbranchdepth(Tree, Acc) ->
 			     "ddb89be403809e325750d3d263cd78929c2942b7942a34b77e122c9594a74c8c",
 			     "5dc9da79a70659a9ad559cb701ded9a2ab9d823aad2f4960cfe370eff4604328"]).
 
-empty_hash_test() ->
-    ?assertEqual(hex:hexstr_to_bin(?EMPTY_HASH), mth([])).
+empty_hash_test_() ->
+    [?_assertEqual(hex:hexstr_to_bin(?EMPTY_HASH), mth([]))].
 
 mth_test() ->
     lists:foreach(
@@ -226,6 +243,10 @@ mth(L) ->
              hashfun([<<"\x01">>, mth(L1), mth(L2)])
     end.
 
+-spec create(iolist() | binary()) -> head().
+create(D) ->
+    mkhead(1, mkleaf(D)).
+
 -spec mkhead(list()) -> head().
 mkhead([]) ->
     mkhead(1, mkleaf([]));
-- 
cgit v1.1