package cli

import (
	"context"
	"sort"
	"strings"
	"time"
)

type remoteEntry struct {
	path        string
	size        int
	lastChanged time.Time
	isDir       bool
	deleted     bool

	// orderKey is path with '/' replaced by 0x00, precomputed so the sort
	// compares native strings. '/' and 0x00 are the only two bytes that can
	// never appear in a path, and 0x00 sorts below every other byte, so this
	// orders a directory's descendants ("a/...") as a contiguous run immediately
	// after the directory ("a") and before any sibling that shares its base name
	// ("a.js", "ab"). emptyDirs relies on that contiguity.
	orderKey string
}

// listRemoteEntries fetches all remote entries from the api. The returned list
// is sorted by orderKey (see remoteEntry.orderKey), which is the ordering
// emptyDirs requires. Callers must not re-sort it by path.
func listRemoteEntries(ctx context.Context, api storageAPI, prefix string) ([]remoteEntry, error) {
	entries := make([]remoteEntry, 0, 64)
	it := api.List(ctx, prefix)
	for it.Next() {
		o := it.Object()
		entries = append(entries, remoteEntry{
			path:        o.Path,
			size:        o.Size,
			isDir:       o.IsDirectory,
			lastChanged: o.LastChanged,
			orderKey:    pathOrderKey(o.Path),
		})
	}
	if err := it.Err(); err != nil {
		return nil, err
	}
	sort.Slice(entries, func(i, j int) bool {
		return entries[i].orderKey < entries[j].orderKey
	})
	return entries, nil
}

// emptyDirs returns the directory entries whose subtree holds no surviving
// file. entries must be sorted by orderKey (see remoteEntry.orderKey), so a
// directory's subtree is the contiguous run of following entries sharing its
// path prefix. A directory exists only to hold files, so it survives iff some
// file beneath it survives. This makes the bottom-up cascade (a parent emptied
// by removing its last child directory) fall out without extra bookkeeping.
// A file survives unless it was deleted.
func emptyDirs(entries []remoteEntry) []*remoteEntry {
	n := len(entries)
	empty := make([]*remoteEntry, 0, n/4)
	for i := 0; i < n; {
		dir := &entries[i]
		i++
		if !dir.isDir {
			continue
		}

		existingFiles := 0
		c := i
		for prefix := dir.path + "/"; c < n; c++ {
			child := &entries[c]
			if !strings.HasPrefix(child.path, prefix) {
				break
			}
			if !child.isDir && !child.deleted {
				existingFiles++
			}
		}

		if existingFiles == 0 {
			// Emit only the top of the empty subtree and skip its descendants.
			// Deleting a Bunny directory removes the subtree recursively, so
			// deleting `dir` also removes any empty sub-dirs beneath it.
			empty = append(empty, dir)
			i = c
		}
	}

	return empty
}

func pathOrderKey(path string) string {
	return strings.ReplaceAll(path, "/", "\x00")
}