notary/internal/tlog: add Go signed tree head format

This is part of a design sketch for a Go module notary.
Eventually the code will live outside golang.org/x/exp.

Everything here is subject to change! Don't depend on it!

This CL adds support for formatting and parsing
Go "signed tree head" messages to be signed by
notary/internal/note.

Change-Id: Ib1f05467de439d9793d49734bcbd8bc23178b219
Reviewed-on: https://go-review.googlesource.com/c/exp/+/162897
Run-TryBot: Russ Cox <rsc@golang.org>
Reviewed-by: Filippo Valsorda <filippo@golang.org>
diff --git a/notary/internal/tlog/note.go b/notary/internal/tlog/note.go
new file mode 100644
index 0000000..a22c290
--- /dev/null
+++ b/notary/internal/tlog/note.go
@@ -0,0 +1,70 @@
+// Copyright 2019 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package tlog
+
+import (
+	"bytes"
+	"encoding/base64"
+	"errors"
+	"fmt"
+	"strconv"
+	"strings"
+)
+
+// A Tree is a tree description signed by a notary.
+type Tree struct {
+	N    int64
+	Hash Hash
+}
+
+// FormatTree formats a tree description for inclusion in a note.
+//
+// The encoded form is three lines, each ending in a newline (U+000A):
+//
+//	go notary tree
+//	N
+//	Hash
+//
+// where N is in decimal and Hash is in base64.
+//
+// A future backwards-compatible encoding may add additional lines,
+// which the parser can ignore.
+// A future backwards-incompatible encoding would use a different
+// first line (for example, "go notary tree v2").
+func FormatTree(tree Tree) []byte {
+	return []byte(fmt.Sprintf("go notary tree\n%d\n%s\n", tree.N, tree.Hash))
+}
+
+var errMalformedTree = errors.New("malformed tree note")
+var treePrefix = []byte("go notary tree\n")
+
+// ParseTree parses a tree root description.
+func ParseTree(text []byte) (tree Tree, err error) {
+	// The message looks like:
+	//
+	//	go notary tree
+	//	2
+	//	nND/nri/U0xuHUrYSy0HtMeal2vzD9V4k/BO79C+QeI=
+	//
+	// For forwards compatibility, extra text lines after the encoding are ignored.
+	if !bytes.HasPrefix(text, treePrefix) || bytes.Count(text, []byte("\n")) < 3 || len(text) > 1e6 {
+		return Tree{}, errMalformedTree
+	}
+
+	lines := strings.SplitN(string(text), "\n", 4)
+	n, err := strconv.ParseInt(lines[1], 10, 64)
+	if err != nil || n < 0 || lines[1] != strconv.FormatInt(n, 10) {
+		return Tree{}, errMalformedTree
+	}
+
+	h, err := base64.StdEncoding.DecodeString(lines[2])
+	if err != nil || len(h) != HashSize {
+		return Tree{}, errMalformedTree
+	}
+
+	var hash Hash
+	copy(hash[:], h)
+	return Tree{n, hash}, nil
+}
diff --git a/notary/internal/tlog/note_test.go b/notary/internal/tlog/note_test.go
new file mode 100644
index 0000000..97a21e1
--- /dev/null
+++ b/notary/internal/tlog/note_test.go
@@ -0,0 +1,56 @@
+// Copyright 2019 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package tlog
+
+import (
+	"strings"
+	"testing"
+)
+
+func TestFormatTree(t *testing.T) {
+	n := int64(123456789012)
+	h := RecordHash([]byte("hello world"))
+	golden := "go notary tree\n123456789012\nTszzRgjTG6xce+z2AG31kAXYKBgQVtCSCE40HmuwBb0=\n"
+	b := FormatTree(Tree{n, h})
+	if string(b) != golden {
+		t.Errorf("FormatTree(...) = %q, want %q", b, golden)
+	}
+}
+
+func TestParseTree(t *testing.T) {
+	in := "go notary tree\n123456789012\nTszzRgjTG6xce+z2AG31kAXYKBgQVtCSCE40HmuwBb0=\n"
+	goldH := RecordHash([]byte("hello world"))
+	goldN := int64(123456789012)
+	tree, err := ParseTree([]byte(in))
+	if tree.N != goldN || tree.Hash != goldH || err != nil {
+		t.Fatalf("ParseTree(...) = Tree{%d, %v}, %v, want Tree{%d, %v}, nil", tree.N, tree.Hash, err, goldN, goldH)
+	}
+
+	// Check invalid trees.
+	var badTrees = []string{
+		"not-" + in,
+		"go notary tree\n0xabcdef\nTszzRgjTG6xce+z2AG31kAXYKBgQVtCSCE40HmuwBb0=\n",
+		"go notary tree\n123456789012\nTszzRgjTG6xce+z2AG31kAXYKBgQVtCSCE40HmuwBTOOBIG=\n",
+	}
+	for _, bad := range badTrees {
+		_, err := ParseTree([]byte(bad))
+		if err == nil {
+			t.Fatalf("ParseTree(%q) succeeded, want failure", in)
+		}
+	}
+
+	// Check junk on end is ignored.
+	var goodTrees = []string{
+		in + "JOE",
+		in + "JOE\n",
+		in + strings.Repeat("JOE\n", 1000),
+	}
+	for _, good := range goodTrees {
+		_, err := ParseTree([]byte(good))
+		if tree.N != goldN || tree.Hash != goldH || err != nil {
+			t.Fatalf("ParseTree(...+%q) = Tree{%d, %v}, %v, want Tree{%d, %v}, nil", good[len(in):], tree.N, tree.Hash, err, goldN, goldH)
+		}
+	}
+}