packed, delta: Implement thin packs

1 files changed, 212 insertions, 0 deletions

diff --git a/packed_write_test.go b/packed_write_test.go
index ccd81844..82e573b4 100644
--- a/packed_write_test.go
+++ b/packed_write_test.go
@@ -358,6 +358,90 @@ func TestPackWriteDeltas(t *testing.T) {
 	_ = gitCmd(t, repoPath, "fsck", "--full", "--strict")
 }
 
+func TestPackWriteThinPackReachable(t *testing.T) {
+	repoPath, cleanup := setupTestRepo(t)
+	defer cleanup()
+
+	workDir, cleanupWork := setupWorkDir(t)
+	defer cleanupWork()
+
+	base := bytes.Repeat([]byte("A"), 16384)
+	if err := os.WriteFile(filepath.Join(workDir, "file.txt"), base, 0o644); err != nil {
+		t.Fatalf("write base file: %v", err)
+	}
+	gitCmd(t, repoPath, "--work-tree="+workDir, "add", ".")
+	gitCmd(t, repoPath, "--work-tree="+workDir, "commit", "-m", "base")
+	haveHash := gitCmd(t, repoPath, "rev-parse", "HEAD")
+
+	mod := append([]byte(nil), base...)
+	mod[1024] = 'B'
+	if err := os.WriteFile(filepath.Join(workDir, "file.txt"), mod, 0o644); err != nil {
+		t.Fatalf("write mod file: %v", err)
+	}
+	gitCmd(t, repoPath, "--work-tree="+workDir, "add", ".")
+	gitCmd(t, repoPath, "--work-tree="+workDir, "commit", "-m", "target")
+	wantHash := gitCmd(t, repoPath, "rev-parse", "HEAD")
+
+	repo, err := OpenRepository(repoPath)
+	if err != nil {
+		t.Fatalf("OpenRepository failed: %v", err)
+	}
+	defer func() { _ = repo.Close() }()
+
+	wantID, _ := repo.ParseHash(wantHash)
+	haveID, _ := repo.ParseHash(haveHash)
+
+	query := ReachabilityQuery{
+		Wants:       []Hash{wantID},
+		Haves:       []Hash{haveID},
+		Mode:        ReachabilityAllObjects,
+		StopAtHaves: true,
+	}
+	var buf bytes.Buffer
+	if _, err := repo.packWriteReachable(&buf, query, packWriteOptions{
+		EnableDeltas:    true,
+		EnableThinPack:  true,
+		MinDeltaSavings: 1,
+	}); err != nil {
+		t.Fatalf("packWriteReachable failed: %v", err)
+	}
+
+	thinSeen, err := checkThinPackStream(buf.Bytes(), repo)
+	if err != nil {
+		t.Fatalf("thin pack stream invalid: %v", err)
+	}
+	if !thinSeen {
+		t.Fatalf("expected thin pack with ref-delta base outside pack")
+	}
+
+	packDir := filepath.Join(repoPath, "objects", "pack")
+	if err := os.MkdirAll(packDir, 0o755); err != nil {
+		t.Fatalf("failed to create pack dir: %v", err)
+	}
+	packPath := filepath.Join(packDir, "furgit-thin-test.pack")
+	idxPath := strings.TrimSuffix(packPath, ".pack") + ".idx"
+	_ = os.Remove(packPath)
+	_ = os.Remove(idxPath)
+
+	cmd := exec.Command("git", "index-pack", "--stdin", "--fix-thin", "-o", idxPath, packPath)
+	cmd.Dir = repoPath
+	cmd.Env = append(os.Environ(),
+		"GIT_CONFIG_GLOBAL=/dev/null",
+		"GIT_CONFIG_SYSTEM=/dev/null",
+	)
+	cmd.Stdin = bytes.NewReader(buf.Bytes())
+	output, err := cmd.CombinedOutput()
+	if err != nil {
+		t.Fatalf("git index-pack --fix-thin failed: %v\n%s", err, output)
+	}
+
+	_ = gitCmd(t, repoPath, "cat-file", "-p", wantHash)
+	_ = gitCmd(t, repoPath, "fsck", "--full", "--strict")
+
+	_ = os.Remove(packPath)
+	_ = os.Remove(idxPath)
+}
+
 func checkPackStream(path string, algo hashAlgorithm, objectCount int) error {
 	data, err := os.ReadFile(path)
 	if err != nil {
@@ -504,6 +588,134 @@ func checkPackStream(path string, algo hashAlgorithm, objectCount int) error {
 	return nil
 }
 
+func checkThinPackStream(data []byte, repo *Repository) (bool, error) {
+	if repo == nil {
+		return false, ErrInvalidObject
+	}
+	if len(data) < 12 {
+		return false, ErrInvalidObject
+	}
+	if binary.BigEndian.Uint32(data[0:4]) != packMagic || binary.BigEndian.Uint32(data[4:8]) != packVersion2 {
+		return false, ErrInvalidObject
+	}
+	count := int(binary.BigEndian.Uint32(data[8:12]))
+	pos := 12
+	hashSize := repo.hashAlgo.Size()
+	type objEntry struct {
+		offset uint64
+		ty     ObjectType
+		body   []byte
+	}
+	byOffset := make(map[uint64]objEntry, count)
+	byHash := make(map[string]objEntry, count)
+	thinSeen := false
+
+	for i := 0; i < count; i++ {
+		objOffset := uint64(pos)
+		ty, size, consumed, err := packHeaderParse(data[pos:])
+		if err != nil {
+			return thinSeen, fmt.Errorf("obj %d header at %d: %v", i, pos, err)
+		}
+		pos += consumed
+		baseTy := ObjectTypeInvalid
+		var baseBody []byte
+		switch ty {
+		case ObjectTypeOfsDelta:
+			dist, distConsumed, err := packDeltaReadOfsDistance(data[pos:])
+			if err != nil {
+				return thinSeen, fmt.Errorf("obj %d ofs at %d: %v", i, pos, err)
+			}
+			pos += distConsumed
+			if dist == 0 || dist > objOffset {
+				return thinSeen, fmt.Errorf("obj %d ofs at %d: invalid dist", i, pos)
+			}
+			baseOffset := objOffset - dist
+			base, ok := byOffset[baseOffset]
+			if !ok {
+				return thinSeen, fmt.Errorf("obj %d ofs at %d: missing base", i, pos)
+			}
+			baseTy = base.ty
+			baseBody = base.body
+		case ObjectTypeRefDelta:
+			if pos+hashSize > len(data) {
+				return thinSeen, ErrInvalidObject
+			}
+			var baseHash Hash
+			copy(baseHash.data[:], data[pos:pos+hashSize])
+			baseHash.algo = repo.hashAlgo
+			baseEntry, ok := byHash[baseHash.String()]
+			if ok {
+				baseTy = baseEntry.ty
+				baseBody = baseEntry.body
+			} else {
+				thinSeen = true
+				ty, body, err := repo.ReadObjectTypeRaw(baseHash)
+				if err != nil {
+					return thinSeen, err
+				}
+				baseTy = ty
+				baseBody = body
+			}
+			pos += hashSize
+		default:
+		}
+
+		payloadBuf, zconsumed, err := zlibx.DecompressSized(data[pos:], size)
+		if err != nil {
+			return thinSeen, fmt.Errorf("obj %d zlib at %d: %v", i, pos, err)
+		}
+		payload := append([]byte(nil), payloadBuf.Bytes()...)
+		payloadBuf.Release()
+		pos += zconsumed
+		switch ty {
+		case ObjectTypeOfsDelta, ObjectTypeRefDelta:
+			if baseBody == nil {
+				return thinSeen, fmt.Errorf("obj %d missing base body", i)
+			}
+			pos := 0
+			baseSize, err := packVarintRead(payload, &pos)
+			if err != nil {
+				return thinSeen, fmt.Errorf("obj %d delta base size: %v", i, err)
+			}
+			resultSize, err := packVarintRead(payload, &pos)
+			if err != nil {
+				return thinSeen, fmt.Errorf("obj %d delta result size: %v", i, err)
+			}
+			if baseSize != len(baseBody) {
+				return thinSeen, fmt.Errorf("obj %d delta base size mismatch: got %d want %d", i, baseSize, len(baseBody))
+			}
+			out, err := packDeltaApply(bufpool.FromOwned(baseBody), bufpool.FromOwned(payload))
+			if err != nil {
+				return thinSeen, fmt.Errorf("obj %d delta apply: %v", i, err)
+			}
+			body := append([]byte(nil), out.Bytes()...)
+			out.Release()
+			if resultSize != len(body) {
+				return thinSeen, fmt.Errorf("obj %d delta result size mismatch: got %d want %d", i, len(body), resultSize)
+			}
+			byOffset[objOffset] = objEntry{offset: objOffset, ty: baseTy, body: body}
+		default:
+			if size >= 0 && len(payload) != size {
+				return thinSeen, fmt.Errorf("obj %d size mismatch: got %d want %d", i, len(payload), size)
+			}
+			body := append([]byte(nil), payload...)
+			byOffset[objOffset] = objEntry{offset: objOffset, ty: ty, body: body}
+		}
+
+		entry := byOffset[objOffset]
+		if entry.body != nil && entry.ty != ObjectTypeInvalid {
+			hdr, err := headerForType(entry.ty, entry.body)
+			if err != nil {
+				return thinSeen, err
+			}
+			raw := append(hdr, entry.body...)
+			hash := repo.hashAlgo.Sum(raw)
+			byHash[hash.String()] = entry
+		}
+	}
+	return thinSeen, nil
+}
+
 func removeLooseObject(repoPath, oid string) error {
 	if len(oid) < 2 {
 		return ErrInvalidObject