1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
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")
}
|
