path: root/plumbing/format/idxfile/idxfile.go

package idxfile

import (
	"bytes"
	"io"

	"gopkg.in/src-d/go-git.v4/plumbing"
	"gopkg.in/src-d/go-git.v4/utils/binary"
)

const (
	// VersionSupported is the only idx version supported.
	VersionSupported = 2

	noMapping = -1
)

var (
	idxHeader = []byte{255, 't', 'O', 'c'}
)

// Index represents an index of a packfile.
type Index interface {
	// Contains checks whether the given hash is in the index.
	Contains(h plumbing.Hash) (bool, error)
	// FindOffset finds the offset in the packfile for the object with
	// the given hash.
	FindOffset(h plumbing.Hash) (int64, error)
	// FindCRC32 finds the CRC32 of the object with the given hash.
	FindCRC32(h plumbing.Hash) (uint32, error)
	// FindHash finds the hash for the object with the given offset.
	FindHash(o int64) (plumbing.Hash, error)
	// Count returns the number of entries in the index.
	Count() (int64, error)
	// Entries returns an iterator to retrieve all index entries.
	Entries() (EntryIter, error)
}

// MemoryIndex is the in memory representation of an idx file.
type MemoryIndex struct {
	Version uint32
	Fanout  [256]uint32
	// FanoutMapping maps the position in the fanout table to the position
	// in the Names, Offset32 and Crc32 slices. This improves the memory
	// usage by not needing an array with unnecessary empty slots.
	FanoutMapping    [256]int
	Names            [][]byte
	Offset32         [][]byte
	Crc32            [][]byte
	Offset64         []byte
	PackfileChecksum [20]byte
	IdxChecksum      [20]byte

	offsetHash map[int64]plumbing.Hash
}

var _ Index = (*MemoryIndex)(nil)

// NewMemoryIndex returns an instance of a new MemoryIndex.
func NewMemoryIndex() *MemoryIndex {
	return &MemoryIndex{}
}

func (idx *MemoryIndex) findHashIndex(h plumbing.Hash) int {
	k := idx.FanoutMapping[h[0]]
	if k == noMapping {
		return -1
	}

	data := idx.Names[k]
	high := uint64(len(idx.Offset32[k])) >> 2
	if high == 0 {
		return -1
	}

	low := uint64(0)
	for {
		mid := (low + high) >> 1
		offset := mid * objectIDLength

		cmp := bytes.Compare(h[:], data[offset:offset+objectIDLength])
		if cmp < 0 {
			high = mid
		} else if cmp == 0 {
			return int(mid)
		} else {
			low = mid + 1
		}

		if low >= high {
			break
		}
	}

	return -1
}

// Contains implements the Index interface.
func (idx *MemoryIndex) Contains(h plumbing.Hash) (bool, error) {
	i := idx.findHashIndex(h)
	return i >= 0, nil
}

// FindOffset implements the Index interface.
func (idx *MemoryIndex) FindOffset(h plumbing.Hash) (int64, error) {
	k := idx.FanoutMapping[h[0]]
	i := idx.findHashIndex(h)
	if i < 0 {
		return 0, plumbing.ErrObjectNotFound
	}

	return idx.getOffset(k, i)
}

const isO64Mask = uint64(1) << 31

func (idx *MemoryIndex) getOffset(firstLevel, secondLevel int) (int64, error) {
	offset := secondLevel << 2
	buf := bytes.NewBuffer(idx.Offset32[firstLevel][offset : offset+4])
	ofs, err := binary.ReadUint32(buf)
	if err != nil {
		return -1, err
	}

	if (uint64(ofs) & isO64Mask) != 0 {
		offset := 8 * (uint64(ofs) & ^isO64Mask)
		buf := bytes.NewBuffer(idx.Offset64[offset : offset+8])
		n, err := binary.ReadUint64(buf)
		if err != nil {
			return -1, err
		}

		return int64(n), nil
	}

	return int64(ofs), nil
}

// FindCRC32 implements the Index interface.
func (idx *MemoryIndex) FindCRC32(h plumbing.Hash) (uint32, error) {
	k := idx.FanoutMapping[h[0]]
	i := idx.findHashIndex(h)
	if i < 0 {
		return 0, plumbing.ErrObjectNotFound
	}

	return idx.getCrc32(k, i)
}

func (idx *MemoryIndex) getCrc32(firstLevel, secondLevel int) (uint32, error) {
	offset := secondLevel << 2
	buf := bytes.NewBuffer(idx.Crc32[firstLevel][offset : offset+4])
	return binary.ReadUint32(buf)
}

// FindHash implements the Index interface.
func (idx *MemoryIndex) FindHash(o int64) (plumbing.Hash, error) {
	// Lazily generate the reverse offset/hash map if required.
	if idx.offsetHash == nil {
		err := idx.genOffsetHash()
		if err != nil {
			return plumbing.ZeroHash, nil
		}
	}

	hash, ok := idx.offsetHash[o]
	if !ok {
		return plumbing.ZeroHash, plumbing.ErrObjectNotFound
	}

	return hash, nil
}

// genOffsetHash generates the offset/hash mapping for reverse search.
func (idx *MemoryIndex) genOffsetHash() error {
	count, err := idx.Count()
	if err != nil {
		return err
	}

	idx.offsetHash = make(map[int64]plumbing.Hash, count)

	iter, err := idx.Entries()
	if err != nil {
		return err
	}

	var entry *Entry
	for err != nil {
		entry, err = iter.Next()
		if err == nil {
			idx.offsetHash[int64(entry.Offset)] = entry.Hash
		}
	}

	if err == io.EOF {
		return nil
	}

	return err
}

// Count implements the Index interface.
func (idx *MemoryIndex) Count() (int64, error) {
	return int64(idx.Fanout[fanout-1]), nil
}

// Entries implements the Index interface.
func (idx *MemoryIndex) Entries() (EntryIter, error) {
	return &idxfileEntryIter{idx, 0, 0, 0}, nil
}

// EntryIter is an iterator that will return the entries in a packfile index.
type EntryIter interface {
	// Next returns the next entry in the packfile index.
	Next() (*Entry, error)
	// Close closes the iterator.
	Close() error
}

type idxfileEntryIter struct {
	idx                     *MemoryIndex
	total                   int
	firstLevel, secondLevel int
}

func (i *idxfileEntryIter) Next() (*Entry, error) {
	for {
		if i.firstLevel >= fanout {
			return nil, io.EOF
		}

		if i.total >= int(i.idx.Fanout[i.firstLevel]) {
			i.firstLevel++
			i.secondLevel = 0
			continue
		}

		entry := new(Entry)
		ofs := i.secondLevel * objectIDLength
		copy(entry.Hash[:], i.idx.Names[i.idx.FanoutMapping[i.firstLevel]][ofs:])

		pos := i.idx.FanoutMapping[entry.Hash[0]]

		offset, err := i.idx.getOffset(pos, i.secondLevel)
		if err != nil {
			return nil, err
		}
		entry.Offset = uint64(offset)

		entry.CRC32, err = i.idx.getCrc32(pos, i.secondLevel)
		if err != nil {
			return nil, err
		}

		i.secondLevel++
		i.total++

		return entry, nil
	}
}

func (i *idxfileEntryIter) Close() error {
	i.firstLevel = fanout
	return nil
}

// Entry is the in memory representation of an object entry in the idx file.
type Entry struct {
	Hash   plumbing.Hash
	CRC32  uint32
	Offset uint64
}