note.go

     1  // Copyright 2019 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package tlog
     6  
     7  import (
     8  	"bytes"
     9  	"encoding/base64"
    10  	"errors"
    11  	"fmt"
    12  	"strconv"
    13  	"strings"
    14  	"unicode/utf8"
    15  )
    16  
    17  // A Tree is a tree description, to be signed by a go.sum database server.
    18  type Tree struct {
    19  	N    int64
    20  	Hash Hash
    21  }
    22  
    23  // FormatTree formats a tree description for inclusion in a note.
    24  //
    25  // The encoded form is three lines, each ending in a newline (U+000A):
    26  //
    27  //	go.sum database tree
    28  //	N
    29  //	Hash
    30  //
    31  // where N is in decimal and Hash is in base64.
    32  //
    33  // A future backwards-compatible encoding may add additional lines,
    34  // which the parser can ignore.
    35  // A future backwards-incompatible encoding would use a different
    36  // first line (for example, "go.sum database tree v2").
    37  func FormatTree(tree Tree) []byte {
    38  	return []byte(fmt.Sprintf("go.sum database tree\n%d\n%s\n", tree.N, tree.Hash))
    39  }
    40  
    41  var errMalformedTree = errors.New("malformed tree note")
    42  var treePrefix = []byte("go.sum database tree\n")
    43  
    44  // ParseTree parses a formatted tree root description.
    45  func ParseTree(text []byte) (tree Tree, err error) {
    46  	// The message looks like:
    47  	//
    48  	//	go.sum database tree
    49  	//	2
    50  	//	nND/nri/U0xuHUrYSy0HtMeal2vzD9V4k/BO79C+QeI=
    51  	//
    52  	// For forwards compatibility, extra text lines after the encoding are ignored.
    53  	if !bytes.HasPrefix(text, treePrefix) || bytes.Count(text, []byte("\n")) < 3 || len(text) > 1e6 {
    54  		return Tree{}, errMalformedTree
    55  	}
    56  
    57  	lines := strings.SplitN(string(text), "\n", 4)
    58  	n, err := strconv.ParseInt(lines[1], 10, 64)
    59  	if err != nil || n < 0 || lines[1] != strconv.FormatInt(n, 10) {
    60  		return Tree{}, errMalformedTree
    61  	}
    62  
    63  	h, err := base64.StdEncoding.DecodeString(lines[2])
    64  	if err != nil || len(h) != HashSize {
    65  		return Tree{}, errMalformedTree
    66  	}
    67  
    68  	var hash Hash
    69  	copy(hash[:], h)
    70  	return Tree{n, hash}, nil
    71  }
    72  
    73  var errMalformedRecord = errors.New("malformed record data")
    74  
    75  // FormatRecord formats a record for serving to a client
    76  // in a lookup response.
    77  //
    78  // The encoded form is the record ID as a single number,
    79  // then the text of the record, and then a terminating blank line.
    80  // Record text must be valid UTF-8 and must not contain any ASCII control
    81  // characters (those below U+0020) other than newline (U+000A).
    82  // It must end in a terminating newline and not contain any blank lines.
    83  //
    84  // Responses to data tiles consist of concatenated formatted records from each of
    85  // which the first line, with the record ID, is removed.
    86  func FormatRecord(id int64, text []byte) (msg []byte, err error) {
    87  	if !isValidRecordText(text) {
    88  		return nil, errMalformedRecord
    89  	}
    90  	msg = []byte(fmt.Sprintf("%d\n", id))
    91  	msg = append(msg, text...)
    92  	msg = append(msg, '\n')
    93  	return msg, nil
    94  }
    95  
    96  // isValidRecordText reports whether text is syntactically valid record text.
    97  func isValidRecordText(text []byte) bool {
    98  	var last rune
    99  	for i := 0; i < len(text); {
   100  		r, size := utf8.DecodeRune(text[i:])
   101  		if r < 0x20 && r != '\n' || r == utf8.RuneError && size == 1 || last == '\n' && r == '\n' {
   102  			return false
   103  		}
   104  		i += size
   105  		last = r
   106  	}
   107  	if last != '\n' {
   108  		return false
   109  	}
   110  	return true
   111  }
   112  
   113  // ParseRecord parses a record description at the start of text,
   114  // stopping immediately after the terminating blank line.
   115  // It returns the record id, the record text, and the remainder of text.
   116  func ParseRecord(msg []byte) (id int64, text, rest []byte, err error) {
   117  	// Leading record id.
   118  	i := bytes.IndexByte(msg, '\n')
   119  	if i < 0 {
   120  		return 0, nil, nil, errMalformedRecord
   121  	}
   122  	id, err = strconv.ParseInt(string(msg[:i]), 10, 64)
   123  	if err != nil {
   124  		return 0, nil, nil, errMalformedRecord
   125  	}
   126  	msg = msg[i+1:]
   127  
   128  	// Record text.
   129  	i = bytes.Index(msg, []byte("\n\n"))
   130  	if i < 0 {
   131  		return 0, nil, nil, errMalformedRecord
   132  	}
   133  	text, rest = msg[:i+1], msg[i+2:]
   134  	if !isValidRecordText(text) {
   135  		return 0, nil, nil, errMalformedRecord
   136  	}
   137  	return id, text, rest, nil
   138  }
   139
View as plain text