package site

import (
	"bytes"
	"compress/gzip"
	"context"
	"crypto/sha256"
	"fmt"
	"html/template"
	"mime"
	"net/url"
	"path"
	"sort"
	"strconv"
	"strings"
	"sync"
	"unicode/utf8"

	"github.com/alecthomas/chroma/v2"
	"github.com/alecthomas/chroma/v2/formatters/html"
	"github.com/alecthomas/chroma/v2/lexers"
	"github.com/alecthomas/chroma/v2/styles"
	"github.com/npfaro/dumbforge/internal/gitutil"
	"github.com/npfaro/dumbforge/internal/s3store"
	"github.com/yuin/goldmark"
	"github.com/yuin/goldmark/extension"
	"github.com/yuin/goldmark/parser"
)

const (
	siteCache = "no-cache, max-age=0, must-revalidate"
	rawCache  = "no-cache, max-age=0, must-revalidate"
)

type Page struct {
	Route       string
	Body        []byte
	ContentType string
	Cache       string
	Root        bool
}

type Build struct {
	Pages   []Page
	Deletes []string
}

type Generator struct {
	Git            gitutil.Git
	BaseURL        string
	RepoName       string
	Owner          string
	CloneURL       string
	Branches       []string
	DefaultBranch  string
	AssetsCurrent  bool
	Progress       func(format string, args ...any)
	templates      *template.Template
	submoduleMu    sync.Mutex
	submoduleCache map[string]map[string]string
	commitMu       sync.Mutex
	generated      map[string]struct{}
	assetOnce      sync.Once
	assetVersion   string
}

type Commit struct {
	OID                string
	ShortOID           string
	Author             string
	Email              string
	Committer          string
	CommitterEmail     string
	Date               string
	DateTime           string
	Message            string
	Body               string
	Initials           string
	AvatarURL          string
	CommitterAvatarURL string
	DistinctCommitter  bool
	URL                string
	Parents            []string
}

type TreeEntry struct {
	Mode           string
	Type           string
	OID            string
	Size           int64
	Name           string
	URL            string
	CommitMessage  string
	CommitURL      string
	CommitDate     string
	CommitDateTime string
	SubmoduleURL   string
}

type Crumb struct {
	Name string
	URL  string
}

type pageData struct {
	Kind             string
	Title            string
	BaseURL          string
	RepoName         string
	RepoAvatarURL    string
	Owner            string
	CloneURL         string
	Branch           string
	Path             string
	ParentURL        string
	Breadcrumbs      []Crumb
	Entries          []TreeEntry
	Commit           Commit
	CommitCount      int
	CommitsURL       string
	CommitGroups     []CommitGroup
	ViewedCommit     CommitView
	BranchesURL      string
	BranchStyleURL   string
	FilesURL         string
	DefaultBranch    string
	GitHubImportURL  string
	Description      string
	Homepage         string
	HomepageLabel    string
	SourceURL        string
	Languages        []LanguageStat
	Contributors     []Contributor
	ContributorCount int
	ReadmeName       string
	Readme           template.HTML
	Markdown         template.HTML
	Code             template.HTML
	RawURL           string
	Language         string
	FileSize         int64
	IsImage          bool
	IsMarkdown       bool
	IsSubmodule      bool
	SubmoduleURL     string
	SubmoduleOID     string
	AssetVersion     string
}

func New(git gitutil.Git, baseURL, repoName, owner string) (*Generator, error) {
	if repoName == "" {
		repoName = "repository"
	}
	tmpl, err := template.New("page").Funcs(template.FuncMap{
		"humanSize": humanSize,
		"icon":      icon,
	}).Parse(pageTemplate)
	if err != nil {
		return nil, err
	}
	return &Generator{
		Git:       git,
		BaseURL:   strings.TrimRight(baseURL, "/"),
		RepoName:  strings.TrimSuffix(repoName, ".git"),
		Owner:     owner,
		CloneURL:  strings.TrimRight(baseURL, "/"),
		templates: tmpl,
		generated: make(map[string]struct{}),
	}, nil
}

func (g *Generator) AssetVersion() string {
	g.assetOnce.Do(func() {
		hash := sha256.New()
		_, _ = hash.Write([]byte(siteCSS))
		_, _ = hash.Write([]byte(g.chromaCSS()))
		_, _ = hash.Write(gabrielMarkSVG)
		_, _ = hash.Write(gabrielMarkPNG)
		g.assetVersion = fmt.Sprintf("%x", hash.Sum(nil))
	})
	return g.assetVersion
}

func (g *Generator) SetAssetsCurrent(current bool) {
	g.AssetsCurrent = current
}

// BuildBranch generates a full branch browser when oldOID is empty. For later
// pushes it only regenerates changed blobs and the directory pages that contain
// them. The repository landing page is refreshed when isHead is true.
func (g *Generator) BuildBranch(ctx context.Context, branch, oldOID, newOID string, isHead bool) (Build, error) {
	g.ensureBranch(branch, isHead)
	summary, err := g.branchSummary(ctx, branch, newOID)
	if err != nil {
		return Build{}, err
	}
	result := Build{}
	if !g.AssetsCurrent {
		result.Pages = append(result.Pages, Page{
			Route:       ".dumbforge/assets/site.css",
			Body:        []byte(siteCSS + g.chromaCSS()),
			ContentType: "text/css; charset=utf-8",
			Cache:       siteCache,
		})
		result.Pages = append(result.Pages, brandPages()...)
		result.Pages = append(result.Pages, Page{
			Route:       ".dumbforge/site-version",
			Body:        []byte(g.AssetVersion() + "\n"),
			ContentType: "text/plain; charset=utf-8",
			Cache:       siteCache,
		})
	}
	commitsPage, err := g.commitsPage(branch, summary)
	if err != nil {
		return Build{}, err
	}
	result.Pages = append(result.Pages, commitsPage, branchStylePage(branch, summary.Count))

	if oldOID == "" {
		filesPage, err := g.filesPage(ctx, branch, newOID)
		if err != nil {
			return Build{}, err
		}
		result.Pages = append(result.Pages, filesPage)
		entries, err := g.listTreeRecursive(ctx, newOID)
		if err != nil {
			return Build{}, err
		}
		g.decorateSubmodules(ctx, newOID, "", entries)
		dirs := map[string]struct{}{"": {}}
		for _, entry := range entries {
			if entry.Type == "tree" {
				dirs[entry.Name] = struct{}{}
				continue
			}
			pages, err := g.blobPages(ctx, branch, newOID, entry, summary)
			if err != nil {
				return Build{}, err
			}
			result.Pages = append(result.Pages, pages...)
		}
		for _, dir := range sortedKeys(dirs) {
			if dir == "" && isHead {
				continue
			}
			page, err := g.treePage(ctx, branch, newOID, dir, summary, false)
			if err != nil {
				return Build{}, err
			}
			result.Pages = append(result.Pages, page)
		}
	} else {
		changes, err := g.Git.DiffNameStatus(ctx, oldOID, newOID)
		if err != nil {
			g.progress("could not diff %s..%s; rebuilding branch", short(oldOID), short(newOID))
			return g.BuildBranch(ctx, branch, "", newOID, isHead)
		}
		if fileNavigationChanged(changes) {
			filesPage, err := g.filesPage(ctx, branch, newOID)
			if err != nil {
				return Build{}, err
			}
			result.Pages = append(result.Pages, filesPage)
		}
		dirs := map[string]struct{}{"": {}}
		for _, change := range changes {
			if change.OldPath != "" {
				result.Deletes = append(result.Deletes,
					path.Join("blob", branchRouteSegment(branch), change.OldPath),
					path.Join("raw", branchRouteSegment(branch), change.OldPath),
				)
				addAncestorDirs(dirs, change.OldPath)
			}
			if strings.HasPrefix(change.Status, "D") {
				result.Deletes = append(result.Deletes,
					path.Join("blob", branchRouteSegment(branch), change.Path),
					path.Join("raw", branchRouteSegment(branch), change.Path),
				)
				addAncestorDirs(dirs, change.Path)
				continue
			}
			entry, err := g.entry(ctx, newOID, change.Path)
			if err != nil {
				return Build{}, err
			}
			changedEntries := []TreeEntry{entry}
			g.decorateSubmodules(ctx, newOID, "", changedEntries)
			pages, err := g.blobPages(ctx, branch, newOID, changedEntries[0], summary)
			if err != nil {
				return Build{}, err
			}
			result.Pages = append(result.Pages, pages...)
			addAncestorDirs(dirs, change.Path)
		}
		for _, dir := range sortedKeys(dirs) {
			if dir == "" && isHead {
				continue
			}
			exists, err := g.treeExists(ctx, newOID, dir)
			if err != nil {
				return Build{}, err
			}
			if !exists {
				result.Deletes = append(result.Deletes, path.Join("tree", branchRouteSegment(branch), dir))
				continue
			}
			page, err := g.treePage(ctx, branch, newOID, dir, summary, false)
			if err != nil {
				return Build{}, err
			}
			result.Pages = append(result.Pages, page)
		}
	}

	if isHead {
		landing, err := g.treePage(ctx, branch, newOID, "", summary, true)
		if err != nil {
			return Build{}, err
		}
		result.Pages = append(result.Pages, landing)
	}
	commitPages, err := g.commitPages(ctx, branch, oldOID, newOID, summary)
	if err != nil {
		return Build{}, err
	}
	result.Pages = append(result.Pages, commitPages...)
	result.Deletes = uniqueStrings(result.Deletes)
	return result, nil
}

func fileNavigationChanged(changes []gitutil.NameStatus) bool {
	for _, change := range changes {
		if change.Status == "" || change.Status[0] != 'M' || change.Path == ".gitmodules" || change.OldPath == ".gitmodules" {
			return true
		}
	}
	return false
}

func (g *Generator) Publish(ctx context.Context, store *s3store.Store, build Build) error {
	for _, route := range build.Deletes {
		if err := store.Delete(ctx, route); err != nil {
			return err
		}
	}

	ctx, cancel := context.WithCancel(ctx)
	defer cancel()
	jobs := make(chan Page)
	errCh := make(chan error, 1)
	var once sync.Once
	var workers sync.WaitGroup
	for range 32 {
		workers.Add(1)
		go func() {
			defer workers.Done()
			for page := range jobs {
				body, encoding, err := compressedPage(page)
				if err != nil {
					once.Do(func() {
						errCh <- err
						cancel()
					})
					return
				}
				if page.Root {
					err = store.PutRootEncoded(ctx, body, page.ContentType, page.Cache, encoding)
				} else {
					err = store.PutEncoded(ctx, page.Route, body, page.ContentType, page.Cache, encoding)
				}
				if err != nil {
					once.Do(func() {
						errCh <- err
						cancel()
					})
					return
				}
			}
		}()
	}
sendPages:
	for _, page := range build.Pages {
		select {
		case jobs <- page:
		case <-ctx.Done():
			break sendPages
		}
	}
	close(jobs)
	workers.Wait()
	select {
	case err := <-errCh:
		return err
	default:
	}
	for _, page := range build.Pages {
		if strings.HasPrefix(page.Route, "commit/") {
			g.markCommitGenerated(strings.TrimPrefix(page.Route, "commit/"))
		}
	}
	g.progress("published %d site object(s), removed %d", len(build.Pages), len(build.Deletes))
	return nil
}

func compressedPage(page Page) ([]byte, string, error) {
	if len(page.Body) < 1024 || !compressibleContentType(page.ContentType) {
		return page.Body, "", nil
	}
	var compressed bytes.Buffer
	writer, err := gzip.NewWriterLevel(&compressed, gzip.BestSpeed)
	if err != nil {
		return nil, "", err
	}
	if _, err := writer.Write(page.Body); err != nil {
		return nil, "", err
	}
	if err := writer.Close(); err != nil {
		return nil, "", err
	}
	if compressed.Len() >= len(page.Body) {
		return page.Body, "", nil
	}
	return compressed.Bytes(), "gzip", nil
}

func compressibleContentType(contentType string) bool {
	return strings.HasPrefix(contentType, "text/") ||
		strings.HasPrefix(contentType, "application/json") ||
		strings.HasPrefix(contentType, "application/javascript") ||
		strings.HasPrefix(contentType, "image/svg+xml")
}

func (g *Generator) treePage(ctx context.Context, branch, oid, dir string, summary branchSummary, root bool) (Page, error) {
	entries, err := g.listTree(ctx, oid, dir)
	if err != nil {
		return Page{}, err
	}
	g.decorateSubmodules(ctx, oid, dir, entries)
	for i := range entries {
		fullPath := path.Join(dir, entries[i].Name)
		if entries[i].Type == "tree" {
			entries[i].URL = routeURL(g.BaseURL, path.Join("tree", branchRouteSegment(branch), fullPath))
		} else if entries[i].SubmoduleURL != "" {
			entries[i].URL = entries[i].SubmoduleURL
		} else {
			entries[i].URL = routeURL(g.BaseURL, path.Join("blob", branchRouteSegment(branch), fullPath))
		}
	}
	if err := g.populateEntryCommits(ctx, oid, dir, entries); err != nil {
		return Page{}, err
	}
	data := g.pageData("tree", g.RepoName, branch, summary)
	data.Path = dir
	data.Breadcrumbs = g.breadcrumbs(branch, dir, "tree")
	data.Entries = entries
	if dir != "" {
		data.Title = path.Base(dir) + " · " + g.RepoName
		parent := path.Dir(dir)
		if parent == "." && branch == g.DefaultBranch {
			data.ParentURL = g.BaseURL
		} else {
			data.ParentURL = routeURL(g.BaseURL, path.Join("tree", branchRouteSegment(branch), parent))
		}
	}
	if root {
		data.Kind = "repo"
		readmeName, readme, err := g.readme(ctx, oid, entries)
		if err != nil {
			return Page{}, err
		}
		data.ReadmeName = readmeName
		data.Readme = readme
	}
	body, err := g.render(data)
	if err != nil {
		return Page{}, err
	}
	if root {
		return Page{Body: body, ContentType: "text/html; charset=utf-8", Cache: siteCache, Root: true}, nil
	}
	return Page{Route: path.Join("tree", branchRouteSegment(branch), dir), Body: body, ContentType: "text/html; charset=utf-8", Cache: siteCache}, nil
}

func (g *Generator) populateEntryCommits(ctx context.Context, oid, dir string, entries []TreeEntry) error {
	if len(entries) == 0 {
		return nil
	}
	ctx, cancel := context.WithCancel(ctx)
	defer cancel()
	workers := min(8, len(entries))
	jobs := make(chan int)
	var wait sync.WaitGroup
	var once sync.Once
	var firstErr error
	for range workers {
		wait.Add(1)
		go func() {
			defer wait.Done()
			for index := range jobs {
				commit, err := g.entryCommit(ctx, oid, path.Join(dir, entries[index].Name))
				if err != nil {
					once.Do(func() {
						firstErr = err
						cancel()
					})
					continue
				}
				entries[index].CommitMessage = commit.Message
				entries[index].CommitURL = routeURL(g.BaseURL, path.Join("commit", commit.OID))
				entries[index].CommitDate = commit.Date
				entries[index].CommitDateTime = commit.DateTime
			}
		}()
	}
sendJobs:
	for index := range entries {
		select {
		case jobs <- index:
		case <-ctx.Done():
			break sendJobs
		}
	}
	close(jobs)
	wait.Wait()
	return firstErr
}

func (g *Generator) entryCommit(ctx context.Context, oid, filePath string) (Commit, error) {
	out, err := g.Git.Run(ctx, "--literal-pathspecs", "log", "-1", "--format=%H%x00%s%x00%aI", oid, "--", filePath)
	if err != nil {
		return Commit{}, err
	}
	fields := strings.Split(strings.TrimSpace(string(out)), "\x00")
	if len(fields) != 3 || fields[0] == "" {
		return Commit{}, fmt.Errorf("could not find the latest commit for %s", filePath)
	}
	return Commit{OID: fields[0], Message: fields[1], Date: displayDate(fields[2]), DateTime: fields[2]}, nil
}

func (g *Generator) blobPages(ctx context.Context, branch, oid string, entry TreeEntry, summary branchSummary) ([]Page, error) {
	var content []byte
	var err error
	if entry.Type == "commit" {
		content = []byte("Submodule commit " + entry.OID + "\n")
	} else {
		content, err = g.Git.Run(ctx, "show", oid+":"+entry.Name)
		if err != nil {
			return nil, err
		}
	}
	rawRoute := path.Join("raw", branchRouteSegment(branch), entry.Name)
	contentType, previewImage := safeRawContentType(entry.Name, content)
	data := g.pageData("blob", path.Base(entry.Name)+" · "+g.RepoName, branch, summary)
	data.Path = entry.Name
	data.Breadcrumbs = g.breadcrumbs(branch, entry.Name, "blob")
	data.RawURL = routeURL(g.BaseURL, rawRoute)
	data.FileSize = int64(len(content))
	data.IsSubmodule = entry.Type == "commit"
	data.SubmoduleURL = entry.SubmoduleURL
	data.SubmoduleOID = entry.OID
	data.IsImage = previewImage
	if data.IsSubmodule {
		data.Language = "Submodule"
	} else if data.IsImage {
		data.Language = "Image"
	} else if bytes.IndexByte(content, 0) >= 0 || !utf8.Valid(content) {
		data.Language = "Binary"
	} else if len(content) > 2*1024*1024 {
		data.Language = "Large text file"
	} else if isMarkdownFile(entry.Name) {
		data.Markdown, err = renderMarkdown(content)
		if err != nil {
			return nil, err
		}
		data.IsMarkdown = true
		data.Language = "Markdown"
	} else {
		code, language, err := highlight(entry.Name, content)
		if err != nil {
			return nil, err
		}
		data.Code = code
		data.Language = language
	}
	body, err := g.render(data)
	if err != nil {
		return nil, err
	}
	return []Page{
		{Route: path.Join("blob", branchRouteSegment(branch), entry.Name), Body: body, ContentType: "text/html; charset=utf-8", Cache: siteCache},
		{Route: rawRoute, Body: content, ContentType: contentType, Cache: rawCache},
	}, nil
}

// Raw files share an origin with the generated repository browser. Serving
// user-controlled HTML, JavaScript, or SVG with an executable media type would
// let a repository run script in that origin, so only inert raster formats are
// previewed as images. Other UTF-8 files are deliberately served as plain text.
func safeRawContentType(filename string, content []byte) (string, bool) {
	contentType := mime.TypeByExtension(path.Ext(filename))
	mediaType, _, _ := mime.ParseMediaType(contentType)
	switch mediaType {
	case "image/avif", "image/bmp", "image/gif", "image/jpeg", "image/png", "image/webp", "image/x-icon", "image/vnd.microsoft.icon":
		return contentType, true
	}
	if bytes.IndexByte(content, 0) < 0 && utf8.Valid(content) {
		return "text/plain; charset=utf-8", false
	}
	return "application/octet-stream", false
}

func (g *Generator) readme(ctx context.Context, oid string, entries []TreeEntry) (string, template.HTML, error) {
	for _, entry := range entries {
		if entry.Type != "blob" || !strings.HasPrefix(strings.ToLower(entry.Name), "readme") {
			continue
		}
		content, err := g.Git.Run(ctx, "show", oid+":"+entry.Name)
		if err != nil {
			return "", "", err
		}
		rendered, err := renderMarkdown(content)
		if err != nil {
			return "", "", err
		}
		return entry.Name, rendered, nil
	}
	return "", "", nil
}

func isMarkdownFile(filename string) bool {
	switch strings.ToLower(path.Ext(filename)) {
	case ".md", ".markdown", ".mdown", ".mkd", ".mkdn":
		return true
	default:
		return false
	}
}

func renderMarkdown(content []byte) (template.HTML, error) {
	var rendered bytes.Buffer
	markdown := goldmark.New(
		goldmark.WithExtensions(extension.GFM),
		goldmark.WithParserOptions(parser.WithAutoHeadingID()),
	)
	if err := markdown.Convert(content, &rendered); err != nil {
		return "", err
	}
	// #nosec G203 -- Goldmark's safe renderer filters raw HTML and dangerous URLs.
	return template.HTML(rendered.String()), nil
}

func highlight(filename string, content []byte) (template.HTML, string, error) {
	lexer := lexers.Match(filename)
	if lexer == nil {
		lexer = lexers.Analyse(string(content))
	}
	if lexer == nil {
		lexer = lexers.Fallback
	}
	lexer = chroma.Coalesce(lexer)
	iterator, err := lexer.Tokenise(nil, string(content))
	if err != nil {
		return "", "", err
	}
	formatter := html.New(
		html.WithClasses(true),
		html.WithLineNumbers(true),
		html.LineNumbersInTable(true),
		html.WithLinkableLineNumbers(true, "L"),
		html.TabWidth(4),
	)
	var rendered bytes.Buffer
	if err := formatter.Format(&rendered, styles.Get("github"), iterator); err != nil {
		return "", "", err
	}
	// #nosec G203 -- Chroma escapes source tokens before producing this HTML.
	return template.HTML(rendered.String()), lexer.Config().Name, nil
}

func (g *Generator) chromaCSS() string {
	formatter := html.New(html.WithClasses(true), html.WithAllClasses(true))
	diffFormatter := html.New(html.WithClasses(true), html.WithAllClasses(true), html.ClassPrefix("diff-"))
	var light, diffLight, dark, diffDark bytes.Buffer
	_ = formatter.WriteCSS(&light, styles.Get("github"))
	_ = diffFormatter.WriteCSS(&diffLight, styles.Get("github"))
	_ = formatter.WriteCSS(&dark, styles.Get("github-dark"))
	_ = diffFormatter.WriteCSS(&diffDark, styles.Get("github-dark"))
	// Keep the light rules out of the dark cascade. Some dark Chroma tokens
	// intentionally inherit the theme's base colour, so there is no explicit
	// dark rule to override an always-on light token rule.
	return "\n@media (prefers-color-scheme: light) {\n" + light.String() + diffLight.String() + "}\n" +
		"@media (prefers-color-scheme: dark) {\n" + dark.String() + diffDark.String() + "}\n"
}

func (g *Generator) render(data pageData) ([]byte, error) {
	var result bytes.Buffer
	if err := g.templates.Execute(&result, data); err != nil {
		return nil, err
	}
	return result.Bytes(), nil
}

func (g *Generator) pageData(kind, title, branch string, summary branchSummary) pageData {
	data := pageData{
		Kind:             kind,
		Title:            title,
		BaseURL:          g.BaseURL,
		RepoName:         g.RepoName,
		Owner:            g.Owner,
		CloneURL:         g.CloneURL,
		Branch:           branch,
		Commit:           summary.Latest,
		CommitCount:      summary.Count,
		CommitsURL:       summary.CommitsURL,
		CommitGroups:     summary.Groups,
		BranchesURL:      routeURL(g.BaseURL, ".dumbforge/repository.json"),
		BranchStyleURL:   routeURL(g.BaseURL, path.Join(".dumbforge/branches", branchRouteSegment(branch)+".css")),
		FilesURL:         routeURL(g.BaseURL, path.Join(".dumbforge/files", branchRouteSegment(branch)+".json")),
		DefaultBranch:    g.DefaultBranch,
		GitHubImportURL:  "https://github.com/new/import",
		Description:      summary.Repository.Description,
		Homepage:         summary.Repository.Homepage,
		HomepageLabel:    summary.Repository.HomepageLabel,
		SourceURL:        summary.Repository.SourceURL,
		Languages:        summary.Repository.Languages,
		Contributors:     summary.Repository.Contributors,
		ContributorCount: summary.Repository.ContributorCount,
		AssetVersion:     g.AssetVersion(),
	}
	if len(summary.Repository.Contributors) > 0 {
		data.RepoAvatarURL = summary.Repository.Contributors[0].AvatarURL
	}
	return data
}

func (g *Generator) commitsPage(branch string, summary branchSummary) (Page, error) {
	data := g.pageData("commits", "Commits · "+g.RepoName, branch, summary)
	body, err := g.render(data)
	if err != nil {
		return Page{}, err
	}
	return Page{
		Route:       path.Join("commits", branchRouteSegment(branch)),
		Body:        body,
		ContentType: "text/html; charset=utf-8",
		Cache:       siteCache,
	}, nil
}

func (g *Generator) listTree(ctx context.Context, oid, dir string) ([]TreeEntry, error) {
	treeish := oid
	if dir != "" {
		treeish += ":" + dir
	}
	out, err := g.Git.Run(ctx, "ls-tree", "-z", "-l", treeish)
	if err != nil {
		return nil, err
	}
	entries, err := parseTree(out)
	if err != nil {
		return nil, err
	}
	sortTree(entries)
	return entries, nil
}

func (g *Generator) listTreeRecursive(ctx context.Context, oid string) ([]TreeEntry, error) {
	out, err := g.Git.Run(ctx, "ls-tree", "-r", "-t", "-z", "-l", oid)
	if err != nil {
		return nil, err
	}
	return parseTree(out)
}

func (g *Generator) entry(ctx context.Context, oid, name string) (TreeEntry, error) {
	out, err := g.Git.Run(ctx, "--literal-pathspecs", "ls-tree", "-z", "-l", oid, "--", name)
	if err != nil {
		return TreeEntry{}, err
	}
	entries, err := parseTree(out)
	if err != nil {
		return TreeEntry{}, err
	}
	if len(entries) != 1 {
		return TreeEntry{}, fmt.Errorf("path %s is not a file at %s", name, short(oid))
	}
	return entries[0], nil
}

func (g *Generator) treeExists(ctx context.Context, oid, dir string) (bool, error) {
	if dir == "" || dir == "." {
		return true, nil
	}
	out, err := g.Git.Run(ctx, "cat-file", "-t", oid+":"+dir)
	if err != nil {
		return false, nil
	}
	return strings.TrimSpace(string(out)) == "tree", nil
}

func parseTree(data []byte) ([]TreeEntry, error) {
	var result []TreeEntry
	for _, record := range bytes.Split(data, []byte{0}) {
		if len(record) == 0 {
			continue
		}
		parts := bytes.SplitN(record, []byte{'\t'}, 2)
		if len(parts) != 2 {
			return nil, fmt.Errorf("malformed ls-tree record")
		}
		fields := strings.Fields(string(parts[0]))
		if len(fields) != 4 {
			return nil, fmt.Errorf("malformed ls-tree header %q", parts[0])
		}
		size := int64(-1)
		if fields[3] != "-" {
			var err error
			size, err = strconv.ParseInt(fields[3], 10, 64)
			if err != nil {
				return nil, err
			}
		}
		result = append(result, TreeEntry{Mode: fields[0], Type: fields[1], OID: fields[2], Size: size, Name: string(parts[1])})
	}
	return result, nil
}

func sortTree(entries []TreeEntry) {
	sort.Slice(entries, func(i, j int) bool {
		if (entries[i].Type == "tree") != (entries[j].Type == "tree") {
			return entries[i].Type == "tree"
		}
		return strings.ToLower(entries[i].Name) < strings.ToLower(entries[j].Name)
	})
}

func (g *Generator) breadcrumbs(branch, filePath, leafKind string) []Crumb {
	crumbs := []Crumb{{Name: g.RepoName, URL: g.BaseURL}}
	parts := strings.Split(strings.Trim(filePath, "/"), "/")
	for i, part := range parts {
		if part == "" {
			continue
		}
		prefix := path.Join(parts[:i+1]...)
		routeKind := "tree"
		if i == len(parts)-1 {
			routeKind = leafKind
		}
		crumbs = append(crumbs, Crumb{Name: part, URL: routeURL(g.BaseURL, path.Join(routeKind, branchRouteSegment(branch), prefix))})
	}
	return crumbs
}

func routeURL(base, route string) string {
	parts := strings.Split(strings.Trim(route, "/"), "/")
	for i := range parts {
		parts[i] = url.PathEscape(parts[i])
	}
	if len(parts) == 1 && parts[0] == "" {
		return strings.TrimRight(base, "/")
	}
	return strings.TrimRight(base, "/") + "/" + strings.Join(parts, "/")
}

// Git ref names cannot contain '~', so it is an unambiguous stand-in for '/'
// when a branch name must occupy one component of the static URL hierarchy.
func branchRouteSegment(branch string) string {
	return strings.ReplaceAll(branch, "/", "~")
}

func addAncestorDirs(dirs map[string]struct{}, filePath string) {
	dir := path.Dir(filePath)
	for dir != "." && dir != "/" && dir != "" {
		dirs[dir] = struct{}{}
		dir = path.Dir(dir)
	}
	dirs[""] = struct{}{}
}

func sortedKeys(values map[string]struct{}) []string {
	result := make([]string, 0, len(values))
	for value := range values {
		result = append(result, value)
	}
	sort.Strings(result)
	return result
}

func uniqueStrings(values []string) []string {
	seen := map[string]struct{}{}
	result := make([]string, 0, len(values))
	for _, value := range values {
		if _, ok := seen[value]; ok {
			continue
		}
		seen[value] = struct{}{}
		result = append(result, value)
	}
	sort.Strings(result)
	return result
}

func initials(name string) string {
	fields := strings.Fields(name)
	if len(fields) == 0 {
		return "?"
	}
	result := string([]rune(fields[0])[0])
	if len(fields) > 1 {
		result += string([]rune(fields[len(fields)-1])[0])
	}
	return strings.ToUpper(result)
}

func humanSize(size int64) string {
	if size < 0 {
		return ""
	}
	if size < 1024 {
		return fmt.Sprintf("%d B", size)
	}
	units := []string{"KB", "MB", "GB"}
	value := float64(size)
	for _, unit := range units {
		value /= 1024
		if value < 1024 {
			return fmt.Sprintf("%.1f %s", value, unit)
		}
	}
	return fmt.Sprintf("%.1f TB", value/1024)
}

func short(oid string) string {
	if len(oid) > 7 {
		return oid[:7]
	}
	return oid
}

func (g *Generator) progress(format string, args ...any) {
	if g.Progress != nil {
		g.Progress(format, args...)
	}
}