git/odb/tree.go

   1 package odb
   2
   3 import (
   4         "bufio"
   5         "bytes"
   6         "fmt"
   7         "io"
   8         "sort"
   9         "strconv"
  10         "strings"
  11         "syscall"
  12 )
  13
  14 // Tree encapsulates a Git tree object.
  15 type Tree struct {
  16         // Entries is the list of entries held by this tree.
  17         Entries []*TreeEntry
  18 }
  19
  20 // Type implements Object.ObjectType by returning the correct object type for
  21 // Trees, TreeObjectType.
  22 func (t *Tree) Type() ObjectType { return TreeObjectType }
  23
  24 // Decode implements Object.Decode and decodes the uncompressed tree being
  25 // read. It returns the number of uncompressed bytes being consumed off of the
  26 // stream, which should be strictly equal to the size given.
  27 //
  28 // If any error was encountered along the way, that will be returned, along with
  29 // the number of bytes read up to that point.
  30 func (t *Tree) Decode(from io.Reader, size int64) (n int, err error) {
  31         buf := bufio.NewReader(from)
  32
  33         var entries []*TreeEntry
  34         for {
  35                 modes, err := buf.ReadString(' ')
  36                 if err != nil {
  37                         if err == io.EOF {
  38                                 break
  39                         }
  40                         return n, err
  41                 }
  42                 n += len(modes)
  43                 modes = strings.TrimSuffix(modes, " ")
  44
  45                 mode, _ := strconv.ParseInt(modes, 8, 32)
  46
  47                 fname, err := buf.ReadString('\x00')
  48                 if err != nil {
  49                         return n, err
  50                 }
  51                 n += len(fname)
  52                 fname = strings.TrimSuffix(fname, "\x00")
  53
  54                 var sha [20]byte
  55                 if _, err = io.ReadFull(buf, sha[:]); err != nil {
  56                         return n, err
  57                 }
  58                 n += 20
  59
  60                 entries = append(entries, &TreeEntry{
  61                         Name:     fname,
  62                         Oid:      sha[:],
  63                         Filemode: int32(mode),
  64                 })
  65         }
  66
  67         t.Entries = entries
  68
  69         return n, nil
  70 }
  71
  72 // Encode encodes the tree's contents to the given io.Writer, "w". If there was
  73 // any error copying the tree's contents, that error will be returned.
  74 //
  75 // Otherwise, the number of bytes written will be returned.
  76 func (t *Tree) Encode(to io.Writer) (n int, err error) {
  77         const entryTmpl = "%s %s\x00%s"
  78
  79         for _, entry := range t.Entries {
  80                 fmode := strconv.FormatInt(int64(entry.Filemode), 8)
  81
  82                 ne, err := fmt.Fprintf(to, entryTmpl,
  83                         fmode,
  84                         entry.Name,
  85                         entry.Oid)
  86
  87                 if err != nil {
  88                         return n, err
  89                 }
  90
  91                 n = n + ne
  92         }
  93         return
  94 }
  95
  96 // Merge performs a merge operation against the given set of `*TreeEntry`'s by
  97 // either replacing existing tree entries of the same name, or appending new
  98 // entries in sub-tree order.
  99 //
 100 // It returns a copy of the tree, and performs the merge in O(n*log(n)) time.
 101 func (t *Tree) Merge(others ...*TreeEntry) *Tree {
 102         unseen := make(map[string]*TreeEntry)
 103
 104         // Build a cache of name+filemode to *TreeEntry.
 105         for _, other := range others {
 106                 key := fmt.Sprintf("%s\x00%o", other.Name, other.Filemode)
 107
 108                 unseen[key] = other
 109         }
 110
 111         // Map the existing entries ("t.Entries") into a new set by either
 112         // copying an existing entry, or replacing it with a new one.
 113         entries := make([]*TreeEntry, 0, len(t.Entries))
 114         for _, entry := range t.Entries {
 115                 key := fmt.Sprintf("%s\x00%o", entry.Name, entry.Filemode)
 116
 117                 if other, ok := unseen[key]; ok {
 118                         entries = append(entries, other)
 119                         delete(unseen, key)
 120                 } else {
 121                         oid := make([]byte, len(entry.Oid))
 122                         copy(oid, entry.Oid)
 123
 124                         entries = append(entries, &TreeEntry{
 125                                 Filemode: entry.Filemode,
 126                                 Name:     entry.Name,
 127                                 Oid:      oid,
 128                         })
 129                 }
 130         }
 131
 132         // For all the items we haven't replaced into the new set, append them
 133         // to the entries.
 134         for _, remaining := range unseen {
 135                 entries = append(entries, remaining)
 136         }
 137
 138         // Call sort afterwords, as a tradeoff between speed and spacial
 139         // complexity. As a future point of optimization, adding new elements
 140         // (see: above) could be done as a linear pass of the "entries" set.
 141         //
 142         // In order to do that, we must have a constant-time lookup of both
 143         // entries in the existing and new sets. This requires building a
 144         // map[string]*TreeEntry for the given "others" as well as "t.Entries".
 145         //
 146         // Trees can be potentially large, so trade this spacial complexity for
 147         // an O(n*log(n)) sort.
 148         sort.Sort(SubtreeOrder(entries))
 149
 150         return &Tree{Entries: entries}
 151 }
 152
 153 // Equal returns whether the receiving and given trees are equal, or in other
 154 // words, whether they are represented by the same SHA-1 when saved to the
 155 // object database.
 156 func (t *Tree) Equal(other *Tree) bool {
 157         if (t == nil) != (other == nil) {
 158                 return false
 159         }
 160
 161         if t != nil {
 162                 if len(t.Entries) != len(other.Entries) {
 163                         return false
 164                 }
 165
 166                 for i := 0; i < len(t.Entries); i++ {
 167                         e1 := t.Entries[i]
 168                         e2 := other.Entries[i]
 169
 170                         if !e1.Equal(e2) {
 171                                 return false
 172                         }
 173                 }
 174         }
 175         return true
 176 }
 177
 178 // TreeEntry encapsulates information about a single tree entry in a tree
 179 // listing.
 180 type TreeEntry struct {
 181         // Name is the entry name relative to the tree in which this entry is
 182         // contained.
 183         Name string
 184         // Oid is the object ID for this tree entry.
 185         Oid []byte
 186         // Filemode is the filemode of this tree entry on disk.
 187         Filemode int32
 188 }
 189
 190 // Equal returns whether the receiving and given TreeEntry instances are
 191 // identical in name, filemode, and OID.
 192 func (e *TreeEntry) Equal(other *TreeEntry) bool {
 193         if (e == nil) != (other == nil) {
 194                 return false
 195         }
 196
 197         if e != nil {
 198                 return e.Name == other.Name &&
 199                         bytes.Equal(e.Oid, other.Oid) &&
 200                         e.Filemode == other.Filemode
 201         }
 202         return true
 203 }
 204
 205 // Type is the type of entry (either blob: BlobObjectType, or a sub-tree:
 206 // TreeObjectType).
 207 func (e *TreeEntry) Type() ObjectType {
 208         switch e.Filemode & syscall.S_IFMT {
 209         case syscall.S_IFREG:
 210                 return BlobObjectType
 211         case syscall.S_IFDIR:
 212                 return TreeObjectType
 213         case syscall.S_IFLNK:
 214                 return BlobObjectType
 215         default:
 216                 if e.Filemode == 0xe000 {
 217                         // Mode 0xe000, or a gitlink, has no formal filesystem
 218                         // (`syscall.S_IF<t>`) equivalent.
 219                         //
 220                         // Safeguard that catch here, or otherwise panic.
 221                         return CommitObjectType
 222                 } else {
 223                         panic(fmt.Sprintf("git/odb: unknown object type: %o",
 224                                 e.Filemode))
 225                 }
 226         }
 227 }
 228
 229 // SubtreeOrder is an implementation of sort.Interface that sorts a set of
 230 // `*TreeEntry`'s according to "subtree" order. This ordering is required to
 231 // write trees in a correct, readable format to the Git object database.
 232 //
 233 // The format is as follows: entries are sorted lexicographically in byte-order,
 234 // with subtrees (entries of Type() == git/odb.TreeObjectType) being sorted as
 235 // if their `Name` fields ended in a "/".
 236 //
 237 // See: https://github.com/git/git/blob/v2.13.0/fsck.c#L492-L525 for more
 238 // details.
 239 type SubtreeOrder []*TreeEntry
 240
 241 // Len implements sort.Interface.Len() and return the length of the underlying
 242 // slice.
 243 func (s SubtreeOrder) Len() int { return len(s) }
 244
 245 // Swap implements sort.Interface.Swap() and swaps the two elements at i and j.
 246 func (s SubtreeOrder) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
 247
 248 // Less implements sort.Interface.Less() and returns whether the element at "i"
 249 // is compared as "less" than the element at "j". In other words, it returns if
 250 // the element at "i" should be sorted ahead of that at "j".
 251 //
 252 // It performs this comparison in lexicographic byte-order according to the
 253 // rules above (see SubtreeOrder).
 254 func (s SubtreeOrder) Less(i, j int) bool {
 255         return s.Name(i) < s.Name(j)
 256 }
 257
 258 // Name returns the name for a given entry indexed at "i", which is a C-style
 259 // string ('\0' terminated unless it's a subtree), optionally terminated with
 260 // '/' if it's a subtree.
 261 //
 262 // This is done because '/' sorts ahead of '\0', and is compatible with the
 263 // tree order in upstream Git.
 264 func (s SubtreeOrder) Name(i int) string {
 265         if i < 0 || i >= len(s) {
 266                 return ""
 267         }
 268
 269         entry := s[i]
 270         if entry == nil {
 271                 return ""
 272         }
 273
 274         if entry.Type() == TreeObjectType {
 275                 return entry.Name + "/"
 276         }
 277         return entry.Name + "\x00"
 278 }