vole
Clone
Read only, no credentials:
https://rodent.software/vole.git
Write over SSH with a registered key:
git clone ssh://git@rodent.software:2222/vole.git
A free and open-source forge that lives in your Git repo.
| 1 | package git |
| 2 | |
| 3 | import ( |
| 4 | "crypto/sha1" |
| 5 | "crypto/sha256" |
| 6 | "encoding/hex" |
| 7 | "fmt" |
| 8 | "hash" |
| 9 | "math/rand/v2" |
| 10 | "strings" |
| 11 | "time" |
| 12 | ) |
| 13 | |
| 14 | // FlatTree reads every blob under commit as a path -> content map. Callers mutate |
| 15 | // the map and hand it back to CommitFiles, which is the simplest way to express |
| 16 | // "update one file in a tree" without a worktree. |
| 17 | func (r *Repo) FlatTree(commit string) (map[string][]byte, error) { |
| 18 | files, _, err := r.flatTree(commit) |
| 19 | return files, err |
| 20 | } |
| 21 | |
| 22 | // flatTree reads the blobs and every entry, including directories, keyed by |
| 23 | // path. A writer that starts from an existing commit needs the directory ids as |
| 24 | // well as the content, because it reuses both for the parts it did not change. |
| 25 | func (r *Repo) flatTree(commit string) (map[string][]byte, map[string]Entry, error) { |
| 26 | files := map[string][]byte{} |
| 27 | entries := map[string]Entry{} |
| 28 | if commit == "" { |
| 29 | return files, entries, nil |
| 30 | } |
| 31 | list, err := r.LsTreeRT(commit) |
| 32 | if err != nil { |
| 33 | return nil, nil, err |
| 34 | } |
| 35 | shas := make([]string, 0, len(list)) |
| 36 | for _, e := range list { |
| 37 | entries[e.Name] = e |
| 38 | if e.Type == "blob" { |
| 39 | shas = append(shas, e.SHA) |
| 40 | } |
| 41 | } |
| 42 | blobs, err := r.BlobsBySHA(shas) |
| 43 | if err != nil { |
| 44 | return nil, nil, err |
| 45 | } |
| 46 | for _, e := range list { |
| 47 | if e.Type != "blob" { |
| 48 | continue |
| 49 | } |
| 50 | data, ok := blobs[e.SHA] |
| 51 | if !ok { |
| 52 | return nil, nil, fmt.Errorf("flat tree: %s has no content for %s", e.Name, e.SHA) |
| 53 | } |
| 54 | files[e.Name] = data |
| 55 | } |
| 56 | return files, entries, nil |
| 57 | } |
| 58 | |
| 59 | // WriteFlatTree writes a nested tree from flat paths and returns its id. It |
| 60 | // writes every blob it is given, so it is for a tree that does not exist yet; |
| 61 | // CommitFiles reuses the parts of an existing tree that did not change. |
| 62 | func WriteFlatTree(g *Repo, files map[string][]byte) (string, error) { |
| 63 | var entries []Entry |
| 64 | dirs := map[string]map[string][]byte{} |
| 65 | for path, content := range files { |
| 66 | parts := strings.SplitN(path, "/", 2) |
| 67 | if len(parts) == 1 { |
| 68 | blob, err := g.HashObject(content) |
| 69 | if err != nil { |
| 70 | return "", err |
| 71 | } |
| 72 | entries = append(entries, Entry{Mode: "100644", Type: "blob", SHA: blob, Name: parts[0]}) |
| 73 | continue |
| 74 | } |
| 75 | if dirs[parts[0]] == nil { |
| 76 | dirs[parts[0]] = map[string][]byte{} |
| 77 | } |
| 78 | dirs[parts[0]][parts[1]] = content |
| 79 | } |
| 80 | for name, sub := range dirs { |
| 81 | sha, err := WriteFlatTree(g, sub) |
| 82 | if err != nil { |
| 83 | return "", err |
| 84 | } |
| 85 | entries = append(entries, Entry{Mode: "040000", Type: "tree", SHA: sha, Name: name}) |
| 86 | } |
| 87 | return g.MkTree(entries) |
| 88 | } |
| 89 | |
| 90 | // CommitFiles applies mutate to the tree behind ref and moves the ref with a |
| 91 | // compare-and-swap, attributing the commit to author. It is the single write path |
| 92 | // for metadata refs; a second implementation would eventually disagree about |
| 93 | // ordering or retries, and that shows up as lost data. |
| 94 | // |
| 95 | // CommitFilesBy is the same write for a caller whose author is only known once the |
| 96 | // tree has been read. |
| 97 | func CommitFiles(g *Repo, ref string, mutate func(map[string][]byte) error, message, author string) (string, error) { |
| 98 | return CommitFilesBy(g, ref, func(files map[string][]byte) (string, error) { |
| 99 | return author, mutate(files) |
| 100 | }, message) |
| 101 | } |
| 102 | |
| 103 | // CommitFilesBy applies mutate to the tree behind ref and moves the ref with a |
| 104 | // compare-and-swap. mutate returns the name to record as the commit's author along |
| 105 | // with its change, because a caller with no account name of its own — a library, or |
| 106 | // an edit made offline against a clone — has only the author the file already names, |
| 107 | // and that is the one thing a caller would otherwise read the branch twice to learn. |
| 108 | // Both the author and the bytes are worked out again on a retry, which is what makes |
| 109 | // losing a compare-and-swap harmless. |
| 110 | // |
| 111 | // Only the files that changed are hashed, and only the directories on the way to |
| 112 | // them are written again. A comment on a branch with ten thousand unrelated |
| 113 | // files therefore costs one blob and one tree per path segment, not one process |
| 114 | // per file in the repository. |
| 115 | // |
| 116 | // Writers of the same ref take turns: the whole read-modify-write runs under |
| 117 | // lockWrites, so a write that arrives while another is in flight waits instead of |
| 118 | // reading a tree it is about to lose. The compare-and-swap and its retry are kept |
| 119 | // for the writers that went around the lock — a push that moved the ref, a |
| 120 | // hand-run git command, a second host — which is why losing one is still safe and |
| 121 | // still finishes. |
| 122 | // |
| 123 | // mutate must be a decision about the tree it is handed, not a replay of one read |
| 124 | // earlier, and it must not call CommitFiles: one writer holds the lock at a time. |
| 125 | func CommitFilesBy(g *Repo, ref string, mutate func(map[string][]byte) (string, error), message string) (string, error) { |
| 126 | unlock, err := g.lockWrites(ref) |
| 127 | if err != nil { |
| 128 | return "", err |
| 129 | } |
| 130 | defer unlock() |
| 131 | |
| 132 | const maxAttempts = 64 |
| 133 | for attempt := 1; attempt <= maxAttempts; attempt++ { |
| 134 | if attempt > 1 { |
| 135 | // The writer that beat us did not hold the lock, so waiting is the only |
| 136 | // way to let it finish writing its objects. Jittered so the writers that |
| 137 | // lost the same race do not line up again. |
| 138 | if err := g.pause(backoff(attempt)); err != nil { |
| 139 | return "", err |
| 140 | } |
| 141 | } |
| 142 | old, err := g.RevParseRaw(ref) |
| 143 | if err != nil { |
| 144 | return "", err |
| 145 | } |
| 146 | files, entries, err := g.flatTree(old) |
| 147 | if err != nil { |
| 148 | return "", err |
| 149 | } |
| 150 | author, err := mutate(files) |
| 151 | if err != nil { |
| 152 | return "", err |
| 153 | } |
| 154 | tree, err := writeChangedTree(g, entries, files) |
| 155 | if err != nil { |
| 156 | return "", err |
| 157 | } |
| 158 | commit, err := g.CommitTreeAs(tree, old, message, author) |
| 159 | if err != nil { |
| 160 | return "", err |
| 161 | } |
| 162 | ok, err := g.UpdateRefCAS(ref, commit, old) |
| 163 | if err != nil { |
| 164 | return "", err |
| 165 | } |
| 166 | if ok { |
| 167 | return commit, nil |
| 168 | } |
| 169 | } |
| 170 | return "", fmt.Errorf("%s: gave up after %d attempts because another writer kept moving the branch; try again", |
| 171 | ref, maxAttempts) |
| 172 | } |
| 173 | |
| 174 | // backoff is how long to wait after losing attempt n: it doubles from a |
| 175 | // millisecond to a quarter of a second and is jittered by up to half its length, |
| 176 | // so writers that were refused together do not all come back together. |
| 177 | func backoff(attempt int) time.Duration { |
| 178 | d := time.Millisecond << uint(min(attempt-2, 8)) |
| 179 | half := d / 2 |
| 180 | return half + time.Duration(rand.Int64N(int64(half)+1)) |
| 181 | } |
| 182 | |
| 183 | // pause waits between attempts without ignoring a cancelled request: a page that |
| 184 | // has gone away should not keep a writer waiting for a ref. |
| 185 | func (r *Repo) pause(d time.Duration) error { |
| 186 | if r.ctx == nil { |
| 187 | time.Sleep(d) |
| 188 | return nil |
| 189 | } |
| 190 | t := time.NewTimer(d) |
| 191 | defer t.Stop() |
| 192 | select { |
| 193 | case <-t.C: |
| 194 | return nil |
| 195 | case <-r.ctx.Done(): |
| 196 | return r.ctx.Err() |
| 197 | } |
| 198 | } |
| 199 | |
| 200 | // writeChangedTree builds the tree for files, reusing the blob and subtree ids |
| 201 | // in old for everything that still says the same thing. |
| 202 | func writeChangedTree(g *Repo, old map[string]Entry, files map[string][]byte) (string, error) { |
| 203 | sha256IDs := usesSHA256(old) |
| 204 | changed := changedPaths(old, files, sha256IDs) |
| 205 | return writeTree(g, buildTree(files), "", old, changed, changedDirectories(changed)) |
| 206 | } |
| 207 | |
| 208 | // changedPaths reports the files a write adds, removes, or changes. Content is |
| 209 | // hashed in memory rather than by a git process per file: the cost is the bytes |
| 210 | // on the branch, while the number of files no longer decides it. |
| 211 | func changedPaths(old map[string]Entry, files map[string][]byte, sha256IDs bool) map[string]bool { |
| 212 | changed := make(map[string]bool) |
| 213 | for path, content := range files { |
| 214 | e, ok := old[path] |
| 215 | if !ok || e.Type != "blob" || e.SHA != blobID(content, sha256IDs) { |
| 216 | changed[path] = true |
| 217 | } |
| 218 | } |
| 219 | for path, e := range old { |
| 220 | if e.Type != "blob" { |
| 221 | continue |
| 222 | } |
| 223 | if _, ok := files[path]; !ok { |
| 224 | changed[path] = true |
| 225 | } |
| 226 | } |
| 227 | return changed |
| 228 | } |
| 229 | |
| 230 | // blobID is the id git would give content as a blob, without writing it. It only |
| 231 | // decides whether a path needs a new blob; every changed blob is still written by |
| 232 | // git. Vole creates SHA-1 repositories, but a tree whose ids are 64 characters |
| 233 | // says the repository is SHA-256 and is answered in kind. |
| 234 | func blobID(content []byte, sha256IDs bool) string { |
| 235 | var h hash.Hash |
| 236 | if sha256IDs { |
| 237 | h = sha256.New() |
| 238 | } else { |
| 239 | h = sha1.New() |
| 240 | } |
| 241 | fmt.Fprintf(h, "blob %d\x00", len(content)) |
| 242 | h.Write(content) |
| 243 | return hex.EncodeToString(h.Sum(nil)) |
| 244 | } |
| 245 | |
| 246 | // usesSHA256 reads the object format from an existing tree id. An empty tree has |
| 247 | // nothing to say, and a repository created by Vole is SHA-1. |
| 248 | func usesSHA256(entries map[string]Entry) bool { |
| 249 | for _, e := range entries { |
| 250 | return len(e.SHA) == sha256.Size*2 |
| 251 | } |
| 252 | return false |
| 253 | } |
| 254 | |
| 255 | // treeNode is a directory while a flat path map is being turned back into trees. |
| 256 | type treeNode struct { |
| 257 | files map[string][]byte |
| 258 | dirs map[string]*treeNode |
| 259 | } |
| 260 | |
| 261 | func buildTree(files map[string][]byte) *treeNode { |
| 262 | root := &treeNode{files: map[string][]byte{}, dirs: map[string]*treeNode{}} |
| 263 | for path, content := range files { |
| 264 | parts := strings.Split(path, "/") |
| 265 | node := root |
| 266 | for _, part := range parts[:len(parts)-1] { |
| 267 | next := node.dirs[part] |
| 268 | if next == nil { |
| 269 | next = &treeNode{files: map[string][]byte{}, dirs: map[string]*treeNode{}} |
| 270 | node.dirs[part] = next |
| 271 | } |
| 272 | node = next |
| 273 | } |
| 274 | node.files[parts[len(parts)-1]] = content |
| 275 | } |
| 276 | return root |
| 277 | } |
| 278 | |
| 279 | // changedDirectories names every directory above a changed file, so the writer |
| 280 | // knows which subtrees have to be rebuilt. |
| 281 | func changedDirectories(changed map[string]bool) map[string]bool { |
| 282 | dirs := map[string]bool{} |
| 283 | for path := range changed { |
| 284 | for { |
| 285 | i := strings.LastIndexByte(path, '/') |
| 286 | if i < 0 { |
| 287 | break |
| 288 | } |
| 289 | path = path[:i] |
| 290 | dirs[path] = true |
| 291 | } |
| 292 | } |
| 293 | return dirs |
| 294 | } |
| 295 | |
| 296 | func writeTree(g *Repo, node *treeNode, prefix string, old map[string]Entry, changed, dirs map[string]bool) (string, error) { |
| 297 | entries := make([]Entry, 0, len(node.files)+len(node.dirs)) |
| 298 | for name, content := range node.files { |
| 299 | path := joinPath(prefix, name) |
| 300 | mode := "100644" |
| 301 | previous, had := old[path] |
| 302 | if had && previous.Type == "blob" { |
| 303 | mode = previous.Mode |
| 304 | } |
| 305 | if !changed[path] && had && previous.Type == "blob" { |
| 306 | entries = append(entries, Entry{Mode: mode, Type: "blob", SHA: previous.SHA, Name: name}) |
| 307 | continue |
| 308 | } |
| 309 | blob, err := g.HashObject(content) |
| 310 | if err != nil { |
| 311 | return "", err |
| 312 | } |
| 313 | entries = append(entries, Entry{Mode: mode, Type: "blob", SHA: blob, Name: name}) |
| 314 | } |
| 315 | for name, child := range node.dirs { |
| 316 | path := joinPath(prefix, name) |
| 317 | if !dirs[path] { |
| 318 | if previous, ok := old[path]; ok && previous.Type == "tree" { |
| 319 | entries = append(entries, Entry{Mode: previous.Mode, Type: "tree", SHA: previous.SHA, Name: name}) |
| 320 | continue |
| 321 | } |
| 322 | } |
| 323 | sha, err := writeTree(g, child, path, old, changed, dirs) |
| 324 | if err != nil { |
| 325 | return "", err |
| 326 | } |
| 327 | mode := "040000" |
| 328 | if previous, ok := old[path]; ok && previous.Type == "tree" { |
| 329 | mode = previous.Mode |
| 330 | } |
| 331 | entries = append(entries, Entry{Mode: mode, Type: "tree", SHA: sha, Name: name}) |
| 332 | } |
| 333 | return g.MkTree(entries) |
| 334 | } |
| 335 | |
| 336 | func joinPath(prefix, name string) string { |
| 337 | if prefix == "" { |
| 338 | return name |
| 339 | } |
| 340 | return prefix + "/" + name |
| 341 | } |
| 342 |