gitweb.ps.run Git - ziggit/blob - git.zig

   1 const std = @import("std");
   2
   3 const Alloc = std.mem.Allocator;
   4 const Reader = std.io.AnyReader;
   5 const Writer = std.io.AnyWriter;
   6
   7 const MaxFileSize = 1024 * 1024;
   8
   9 const Id = u160;
  10 const Commit = struct {
  11     tree: Id,
  12     parent: Id,
  13     author: []u8,
  14     committer: []u8,
  15     message: []u8,
  16 };
  17 const TreeEntry = struct {
  18     permissions: []u8,
  19     name: []u8,
  20     id: Id,
  21 };
  22 const Tree = std.ArrayList(TreeEntry);
  23 const Blob = struct {
  24     data: []u8,
  25 };
  26 const ParsedObject = union(enum) {
  27     c: Commit,
  28     t: Tree,
  29     b: Blob,
  30 };
  31 const Object = struct {
  32     kind: u3,
  33     data: []u8,
  34
  35     pub fn init(kind: u3, data: []u8) Object {
  36         return .{
  37             .kind = kind,
  38             .data = data,
  39         };
  40     }
  41     pub fn parse(self: Object, alloc: Alloc) !ParsedObject {
  42         switch (self.kind) {
  43             1 => {
  44                 const authorOffset = std.mem.indexOf(u8, self.data, "author ") orelse return error.InvalidCommitFormat;
  45                 const authorNewline = std.mem.indexOfScalarPos(u8, self.data, authorOffset, '\n') orelse return error.InvalidCommitFormat;
  46                 const committerOffset = std.mem.indexOf(u8, self.data, "committer ") orelse return error.InvalidCommitFormat;
  47                 const committerNewline = std.mem.indexOfScalarPos(u8, self.data, committerOffset, '\n') orelse return error.InvalidCommitFormat;
  48
  49                 return .{
  50                     .c = Commit{
  51                         .tree = try std.fmt.parseUnsigned(Id, self.data[5..45], 16),
  52                         .parent = try std.fmt.parseUnsigned(Id, self.data[53..93], 16),
  53                         .author = self.data[authorOffset..authorNewline],
  54                         .committer = self.data[committerOffset..committerNewline],
  55                         .message = self.data[committerNewline + 1 .. self.data.len],
  56                     },
  57                 };
  58             },
  59             2 => {
  60                 var t = Tree.init(alloc);
  61
  62                 var offset: usize = 0;
  63
  64                 while (offset < self.data.len - 1) {
  65                     const spaceOffset = std.mem.indexOfScalarPos(u8, self.data, offset, ' ') orelse return error.InvalidTreeFormat;
  66                     const zeroOffset = std.mem.indexOfScalarPos(u8, self.data, spaceOffset, 0) orelse return error.InvalidTreeFormat;
  67
  68                     try t.append(.{
  69                         .permissions = self.data[offset..spaceOffset],
  70                         .name = self.data[spaceOffset + 1 .. zeroOffset],
  71                         .id = std.mem.readVarInt(Id, self.data[zeroOffset + 1 .. zeroOffset + 21], .big),
  72                     });
  73
  74                     offset = zeroOffset + 21;
  75                 }
  76
  77                 return .{ .t = t };
  78             },
  79             3 => {
  80                 return .{
  81                     .b = Blob{ .data = self.data },
  82                 };
  83             },
  84             4 => {
  85                 return error.TagNotImplemented;
  86             },
  87             else => return error.UnknownGitObjectType,
  88         }
  89     }
  90     // pub fn getCommit(self: *Object) Commit {}
  91     // pub fn getBlob(self: *Object) Blob {}
  92 };
  93
  94 fn decompress(alloc: Alloc, r: Reader) ![]u8 {
  95     var buffer = std.ArrayList(u8).init(alloc);
  96
  97     try std.compress.zlib.decompress(r, buffer.writer().any());
  98
  99     return alloc.realloc(buffer.allocatedSlice(), buffer.items.len);
 100 }
 101
 102 const PackFile = struct {
 103     alloc: Alloc,
 104     idxFile: std.fs.File,
 105     pckFile: std.fs.File,
 106     objectOffsets: std.AutoArrayHashMap(Id, u32),
 107
 108     pub fn open(alloc: Alloc, dir: std.fs.Dir) !?PackFile {
 109         var self = PackFile{
 110             .alloc = alloc,
 111             .idxFile = undefined,
 112             .pckFile = undefined,
 113             .objectOffsets = std.AutoArrayHashMap(Id, u32).init(alloc),
 114         };
 115
 116         var packDir = try dir.openDir("objects/pack", .{ .iterate = true });
 117         defer packDir.close();
 118
 119         var packFileFound = false;
 120
 121         var packIt = packDir.iterate();
 122         while (try packIt.next()) |f| {
 123             if (std.mem.endsWith(u8, f.name, ".idx")) {
 124                 const idxFilename = f.name;
 125                 var pckFilename = try std.BoundedArray(u8, std.fs.max_path_bytes).init(0);
 126                 try std.fmt.format(
 127                     pckFilename.writer(),
 128                     "{s}.pack",
 129                     .{idxFilename[0 .. idxFilename.len - 4]},
 130                 );
 131
 132                 self.idxFile = try packDir.openFile(idxFilename, .{});
 133                 self.pckFile = try packDir.openFile(pckFilename.constSlice(), .{});
 134
 135                 try self.parseIndex();
 136
 137                 packFileFound = true;
 138             }
 139         }
 140
 141         if (!packFileFound)
 142             return null;
 143
 144         return self;
 145     }
 146
 147     pub fn close(self: *PackFile) void {
 148         self.objectOffsets.deinit();
 149         self.idxFile.close();
 150         self.pckFile.close();
 151     }
 152
 153     pub fn parseIndex(self: *PackFile) !void {
 154         const idxReader = self.idxFile.reader().any();
 155
 156         var fanoutTable: [256]u32 = undefined;
 157
 158         for (0..256) |i| {
 159             try self.idxFile.seekTo(8 + i * 4);
 160             fanoutTable[i] = try idxReader.readVarInt(u32, .big, 4);
 161
 162             const numObjects =
 163                 if (i > 0) fanoutTable[i] - fanoutTable[i - 1] else fanoutTable[i];
 164
 165             for (0..numObjects) |j| {
 166                 const idOffset =
 167                     4 + 4 + 4 * 256 + (j + if (i > 0) fanoutTable[i - 1] else 0) * 20;
 168                 try self.idxFile.seekTo(idOffset);
 169                 const id = try idxReader.readVarInt(Id, .big, 20);
 170
 171                 try self.objectOffsets.put(id, 0);
 172             }
 173         }
 174
 175         const numObjects = self.objectOffsets.keys().len;
 176         for (0..numObjects) |i| {
 177             const offsetOffset =
 178                 4 + 4 + 4 * 256 + numObjects * (20 + 4) + i * 4;
 179             try self.idxFile.seekTo(offsetOffset);
 180             const offset = try idxReader.readVarInt(u32, .big, 4);
 181
 182             self.objectOffsets.values()[i] = offset;
 183         }
 184     }
 185
 186     fn getSize(reader: Reader, ignoreTypeBits: bool) !struct { size: u64, bytelen: u64 } {
 187         var size: u64 = 0;
 188         var counter: u6 = 0;
 189         while (true) {
 190             const byte = try reader.readByte();
 191
 192             if (counter == 0) {
 193                 if (ignoreTypeBits) {
 194                     const bits: u4 = @truncate(byte);
 195                     size = bits;
 196                 } else {
 197                     const bits: u7 = @truncate(byte);
 198                     size = bits;
 199                 }
 200             } else {
 201                 if (ignoreTypeBits) {
 202                     const bits: u7 = @truncate(byte);
 203                     size += @as(u64, bits) << (7 * (counter - 1) + 4);
 204                 } else {
 205                     const bits: u7 = @truncate(byte);
 206                     size += @as(u64, bits) << (7 * (counter));
 207                 }
 208             }
 209
 210             if (byte & 0b10000000 == 0) {
 211                 break;
 212             }
 213
 214             counter += 1;
 215         }
 216
 217         const nBytes = counter + 1;
 218
 219         return .{
 220             .size = size,
 221             .bytelen = nBytes,
 222         };
 223     }
 224
 225     fn getOffset(reader: Reader) !struct { offset: u64, bytelen: u64 } {
 226         var offset: u64 = 0;
 227         var counter: u4 = 0;
 228         while (true) {
 229             const byte = try reader.readByte();
 230
 231             const bits: u7 = @truncate(byte);
 232             offset <<= 7;
 233             offset += @as(u64, bits);
 234
 235             if (byte & 0b10000000 == 0) {
 236                 break;
 237             }
 238
 239             counter += 1;
 240         }
 241
 242         const nBytes = counter + 1;
 243
 244         if (nBytes >= 2) {
 245             for (1..nBytes) |i| {
 246                 offset += std.math.pow(u64, 2, 7 * i);
 247             }
 248         }
 249         return .{
 250             .offset = offset,
 251             .bytelen = nBytes,
 252         };
 253     }
 254
 255     fn applyDelta(alloc: Alloc, baseData: []const u8, deltData: []const u8) ![]u8 {
 256         var fbs = std.io.fixedBufferStream(deltData);
 257         const deltDataReader = fbs.reader().any();
 258         const baseObjectSize = try getSize(deltDataReader, false);
 259         const resultObjectSize = try getSize(deltDataReader, false);
 260         const deltaDataOffset = baseObjectSize.bytelen + resultObjectSize.bytelen;
 261
 262         const result = try alloc.alloc(u8, resultObjectSize.size);
 263         var resultCounter: u64 = 0;
 264
 265         var counter: u64 = 0;
 266         while (true) {
 267             const b = deltData[deltaDataOffset + counter];
 268
 269             if (b & 0b10000000 != 0) {
 270                 var dataOffset: u64 = 0;
 271                 var dataSize: u64 = 0;
 272                 var bitsSet: u8 = 0;
 273                 for (0..4) |i| { // offset bits
 274                     if (b & (@as(u64, 1) << @min(3, i)) != 0) {
 275                         dataOffset += @as(u64, deltData[deltaDataOffset + counter + 1 + bitsSet]) << @min(3 * 8, i * 8);
 276                         bitsSet += 1;
 277                     }
 278                 }
 279                 for (4..7) |i| { // size bits
 280                     if (b & (@as(u64, 1) << @min(6, i)) != 0) {
 281                         dataSize += @as(u64, deltData[deltaDataOffset + counter + 1 + bitsSet]) << @min(6 * 8, (i - 4) * 8);
 282                         bitsSet += 1;
 283                     }
 284                 }
 285                 counter += bitsSet;
 286
 287                 if (dataSize == 0)
 288                     dataSize = 0x10000;
 289
 290                 std.mem.copyForwards(
 291                     u8,
 292                     result[resultCounter..result.len],
 293                     baseData[dataOffset .. dataOffset + dataSize],
 294                 );
 295
 296                 resultCounter += dataSize;
 297             } else {
 298                 const dataSize: u7 = @truncate(b);
 299
 300                 std.mem.copyForwards(
 301                     u8,
 302                     result[resultCounter..result.len],
 303                     deltData[deltaDataOffset + counter + 1 .. deltaDataOffset + counter + 1 + dataSize],
 304                 );
 305
 306                 resultCounter += dataSize;
 307                 counter += dataSize;
 308             }
 309
 310             counter += 1;
 311             if (deltaDataOffset + counter >= deltData.len)
 312                 break;
 313         }
 314
 315         return result;
 316     }
 317
 318     fn ofsDelta(self: *PackFile, offset: i64) anyerror!Object {
 319         const pckReader = self.pckFile.reader().any();
 320
 321         const pos = try self.pckFile.getPos();
 322
 323         try self.pckFile.seekBy(-offset);
 324         const baseObject = try self.readObject(pckReader);
 325         defer self.alloc.free(baseObject.data);
 326
 327         try self.pckFile.seekTo(pos);
 328         const deltaData = try decompress(self.alloc, pckReader);
 329         defer self.alloc.free(deltaData);
 330
 331         const objectData = try applyDelta(self.alloc, baseObject.data, deltaData);
 332         return Object.init(baseObject.kind, objectData);
 333     }
 334
 335     fn readObject(self: *PackFile, reader: Reader) anyerror!Object {
 336         const firstByte = try reader.readByte();
 337         const objectKind: u3 = @truncate(firstByte >> 4);
 338         try self.pckFile.seekBy(-1);
 339         const objectSize = try getSize(reader, true);
 340
 341         if (objectKind == 6) {
 342             const offset = try getOffset(reader);
 343
 344             return try self.ofsDelta(
 345                 @intCast(offset.offset + objectSize.bytelen + offset.bytelen),
 346             );
 347         } else {
 348             const objectData = try decompress(self.alloc, reader);
 349             return Object.init(objectKind, objectData);
 350         }
 351     }
 352
 353     pub fn getObject(self: *PackFile, id: Id) !?Object {
 354         if (self.objectOffsets.get(id)) |offset| {
 355             const pckReader = self.pckFile.reader().any();
 356             try self.pckFile.seekTo(offset);
 357
 358             const o = try self.readObject(pckReader);
 359
 360             return o;
 361         }
 362         return null;
 363     }
 364 };
 365
 366 const Repo = struct {
 367     alloc: Alloc,
 368     dir: std.fs.Dir,
 369     packfile: ?PackFile,
 370
 371     pub fn open(alloc: Alloc, path: []const u8) !Repo {
 372         const dir = try std.fs.cwd().openDir(path, .{});
 373
 374         const packfile = try PackFile.open(alloc, dir);
 375
 376         return .{
 377             .alloc = alloc,
 378             .dir = dir,
 379             .packfile = packfile,
 380         };
 381     }
 382
 383     pub fn close(self: *Repo) void {
 384         self.dir.close();
 385         if (self.packfile != null) {
 386             self.packfile.?.close();
 387         }
 388     }
 389
 390     pub fn getHead(self: *Repo) !Id {
 391         // read file HEAD
 392         const head = try self.dir.readFileAlloc(self.alloc, "HEAD", 1024);
 393         defer self.alloc.free(head);
 394
 395         // read file pointed at by HEAD
 396         const headPath = head[5 .. head.len - 1];
 397         var idBuffer: [40]u8 = undefined;
 398         const idStr = try self.dir.readFile(headPath, &idBuffer);
 399
 400         // parse id from file
 401         return try std.fmt.parseUnsigned(u160, idStr, 16);
 402     }
 403
 404     pub fn getObject(self: *Repo, id: Id) !?Object {
 405         if (self.packfile) |*packfile| {
 406             return packfile.getObject(id);
 407         }
 408         return null;
 409     }
 410 };
 411
 412 test "print HEAD" {
 413     var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
 414     defer arena.deinit();
 415     const alloc = arena.allocator();
 416
 417     var repo = try Repo.open(alloc, "../imgui/.git");
 418     defer repo.close();
 419
 420     const head = try repo.getHead();
 421
 422     std.debug.print("HEAD: {}\n", .{head});
 423 }
 424
 425 test "parse idx" {
 426     var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
 427     defer arena.deinit();
 428     const alloc = arena.allocator();
 429
 430     var repo = try Repo.open(alloc, "../imgui/.git");
 431     defer repo.close();
 432
 433     if (repo.packfile) |packfile| {
 434         std.debug.print("{}\n", .{packfile.objectOffsets.keys().len});
 435         std.debug.print("{}\n", .{packfile.objectOffsets.values().len});
 436     }
 437 }
 438
 439 test "get object" {
 440     var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
 441     defer arena.deinit();
 442     const alloc = arena.allocator();
 443
 444     var repo = try Repo.open(alloc, "../imgui/.git");
 445     defer repo.close();
 446
 447     const head = try repo.getHead();
 448
 449     if (try repo.getObject(head)) |o| {
 450         defer alloc.free(o.data);
 451
 452         std.debug.print("object({}): {s}\n", .{ o.kind, o.data });
 453     }
 454 }
 455
 456 test "parse commit" {
 457     var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
 458     defer arena.deinit();
 459     const alloc = arena.allocator();
 460
 461     var repo = try Repo.open(alloc, "../imgui/.git");
 462     defer repo.close();
 463
 464     const head = try repo.getHead();
 465
 466     if (try repo.getObject(head)) |o| {
 467         defer alloc.free(o.data);
 468
 469         switch (try o.parse(alloc)) {
 470             .c => |c| {
 471                 std.debug.print("commit:\n  tree: {x}\n  parent: {x}\n  author: {s}\n  committer: {s}\n  message: {s}\n", .{ c.tree, c.parent, c.author, c.committer, c.message });
 472             },
 473             else => {},
 474         }
 475     }
 476 }
 477
 478 test "get tree" {
 479     var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
 480     defer arena.deinit();
 481     const alloc = arena.allocator();
 482
 483     var repo = try Repo.open(alloc, "../imgui/.git");
 484     defer repo.close();
 485
 486     if (try repo.getObject(0xceb2b2c62d6f8f3686dcacecd5be931839b02c77)) |o| {
 487         defer alloc.free(o.data);
 488
 489         // std.debug.print("tree({}): {any}\n", .{ o.kind, o.data });
 490     }
 491 }
 492
 493 test "parse tree" {
 494     var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
 495     defer arena.deinit();
 496     const alloc = arena.allocator();
 497
 498     var repo = try Repo.open(alloc, "../imgui/.git");
 499     defer repo.close();
 500
 501     if (try repo.getObject(0xceb2b2c62d6f8f3686dcacecd5be931839b02c77)) |o| {
 502         defer alloc.free(o.data);
 503
 504         switch (try o.parse(alloc)) {
 505             .t => |t| {
 506                 defer t.deinit();
 507                 for (t.items) |treeEntry| {
 508                     std.debug.print("{s} {s} {x}\n", .{ treeEntry.permissions, treeEntry.name, treeEntry.id });
 509                 }
 510             },
 511             else => {},
 512         }
 513     }
 514 }
 515
 516 test "list commits" {
 517     var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
 518     defer arena.deinit();
 519     const alloc = arena.allocator();
 520
 521     var repo = try Repo.open(alloc, "../imgui/.git");
 522     defer repo.close();
 523
 524     const head = try repo.getHead();
 525
 526     var id = head;
 527
 528     for (0..3) |_| {
 529         if (try repo.getObject(id)) |o| {
 530             defer alloc.free(o.data);
 531
 532             switch (try o.parse(alloc)) {
 533                 .c => |c| {
 534                     std.debug.print("commit {x}:\n  tree: {x}\n  parent: {x}\n  author: {s}\n  committer: {s}\n  message: {s}\n", .{ id, c.tree, c.parent, c.author, c.committer, c.message });
 535                     id = c.parent;
 536                 },
 537                 else => {},
 538             }
 539         }
 540     }
 541 }
 542
 543 test "list blobs" {
 544     var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
 545     defer arena.deinit();
 546     const alloc = arena.allocator();
 547
 548     var repo = try Repo.open(alloc, "../imgui/.git");
 549     defer repo.close();
 550
 551     if (try repo.getObject(0xceb2b2c62d6f8f3686dcacecd5be931839b02c77)) |o| {
 552         defer alloc.free(o.data);
 553
 554         switch (try o.parse(alloc)) {
 555             .t => |t| {
 556                 defer t.deinit();
 557                 for (t.items) |treeEntry| {
 558                     if (try repo.getObject(treeEntry.id)) |bo| {
 559                         defer alloc.free(bo.data);
 560
 561                         if (treeEntry.permissions.len == 6) {
 562                             std.debug.print("{s}: [{x} {}]{s}\n", .{ treeEntry.name, treeEntry.id, bo.data.len, bo.data[0..50] });
 563                         } else {
 564                             std.debug.print("[{s}]\n", .{treeEntry.name});
 565                         }
 566                     }
 567                 }
 568             },
 569             else => {},
 570         }
 571     }
 572 }
 573
 574 test "basic frontend" {
 575     var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
 576     defer arena.deinit();
 577     const alloc = arena.allocator();
 578
 579     var repo = try Repo.open(alloc, "../imgui/.git");
 580     defer repo.close();
 581
 582     const head = try repo.getHead();
 583
 584     var id = head;
 585
 586     for (0..3) |_| {
 587         if (try repo.getObject(id)) |o| {
 588             defer alloc.free(o.data);
 589
 590             switch (try o.parse(alloc)) {
 591                 .c => |c| {
 592                     std.debug.print("commit {x}:\n  tree: {x}\n  parent: {x}\n  author: {s}\n  committer: {s}\n  message: {s}\n", .{ id, c.tree, c.parent, c.author, c.committer, c.message });
 593                     id = c.parent;
 594                 },
 595                 else => {},
 596             }
 597         }
 598     }
 599 }