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
 326         try self.pckFile.seekTo(pos);
 327         const deltaData = try decompress(self.alloc, pckReader);
 328
 329         const objectData = try applyDelta(self.alloc, baseObject.data, deltaData);
 330         return Object.init(baseObject.kind, objectData);
 331     }
 332
 333     fn readObject(self: *PackFile, reader: Reader) anyerror!Object {
 334         const firstByte = try reader.readByte();
 335         const objectKind: u3 = @truncate(firstByte >> 4);
 336         try self.pckFile.seekBy(-1);
 337         const objectSize = try getSize(reader, true);
 338
 339         if (objectKind == 6) {
 340             const offset = try getOffset(reader);
 341
 342             return try self.ofsDelta(
 343                 @intCast(offset.offset + objectSize.bytelen + offset.bytelen),
 344             );
 345         } else {
 346             const objectData = try decompress(self.alloc, reader);
 347             return Object.init(objectKind, objectData);
 348         }
 349     }
 350
 351     pub fn getObject(self: *PackFile, id: Id) !?Object {
 352         if (self.objectOffsets.get(id)) |offset| {
 353             const pckReader = self.pckFile.reader().any();
 354             try self.pckFile.seekTo(offset);
 355
 356             const o = try self.readObject(pckReader);
 357
 358             return o;
 359         }
 360         return null;
 361     }
 362 };
 363
 364 const Repo = struct {
 365     alloc: Alloc,
 366     dir: std.fs.Dir,
 367     packfile: ?PackFile,
 368
 369     pub fn open(alloc: Alloc, path: []const u8) !Repo {
 370         const dir = try std.fs.cwd().openDir(path, .{});
 371
 372         const packfile = try PackFile.open(alloc, dir);
 373
 374         return .{
 375             .alloc = alloc,
 376             .dir = dir,
 377             .packfile = packfile,
 378         };
 379     }
 380
 381     pub fn close(self: *Repo) void {
 382         self.dir.close();
 383         if (self.packfile != null) {
 384             self.packfile.?.close();
 385         }
 386     }
 387
 388     pub fn getHead(self: *Repo) !Id {
 389         // read file HEAD
 390         const head = try self.dir.readFileAlloc(self.alloc, "HEAD", 1024);
 391
 392         // read file pointed at by HEAD
 393         const headPath = head[5 .. head.len - 1];
 394         var idBuffer: [40]u8 = undefined;
 395         const idStr = try self.dir.readFile(headPath, &idBuffer);
 396
 397         // parse id from file
 398         return try std.fmt.parseUnsigned(u160, idStr, 16);
 399     }
 400
 401     pub fn getObject(self: *Repo, id: Id) !?Object {
 402         if (self.packfile) |*packfile| {
 403             return packfile.getObject(id);
 404         }
 405         return null;
 406     }
 407 };
 408
 409 test "print HEAD" {
 410     var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
 411     defer arena.deinit();
 412     const alloc = arena.allocator();
 413
 414     var repo = try Repo.open(alloc, "../imgui/.git");
 415     defer repo.close();
 416
 417     const head = try repo.getHead();
 418
 419     std.debug.print("HEAD: {}\n", .{head});
 420 }
 421
 422 test "parse idx" {
 423     var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
 424     defer arena.deinit();
 425     const alloc = arena.allocator();
 426
 427     var repo = try Repo.open(alloc, "../imgui/.git");
 428     defer repo.close();
 429
 430     if (repo.packfile) |packfile| {
 431         std.debug.print("{}\n", .{packfile.objectOffsets.keys().len});
 432         std.debug.print("{}\n", .{packfile.objectOffsets.values().len});
 433     }
 434 }
 435
 436 test "get object" {
 437     var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
 438     defer arena.deinit();
 439     const alloc = arena.allocator();
 440
 441     var repo = try Repo.open(alloc, "../imgui/.git");
 442     defer repo.close();
 443
 444     const head = try repo.getHead();
 445
 446     if (try repo.getObject(head)) |o| {
 447         std.debug.print("object({}): {s}\n", .{ o.kind, o.data });
 448     }
 449 }
 450
 451 test "parse commit" {
 452     var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
 453     defer arena.deinit();
 454     const alloc = arena.allocator();
 455
 456     var repo = try Repo.open(alloc, "../imgui/.git");
 457     defer repo.close();
 458
 459     const head = try repo.getHead();
 460
 461     if (try repo.getObject(head)) |o| {
 462         switch (try o.parse(alloc)) {
 463             .c => |c| {
 464                 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 });
 465             },
 466             else => {},
 467         }
 468     }
 469 }
 470
 471 test "get tree" {
 472     var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
 473     defer arena.deinit();
 474     const alloc = arena.allocator();
 475
 476     var repo = try Repo.open(alloc, "../imgui/.git");
 477     defer repo.close();
 478
 479     if (try repo.getObject(0xceb2b2c62d6f8f3686dcacecd5be931839b02c77)) |o| {
 480         std.debug.print("tree({}): {any}\n", .{ o.kind, o.data });
 481     }
 482 }
 483
 484 test "parse tree" {
 485     var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
 486     defer arena.deinit();
 487     const alloc = arena.allocator();
 488
 489     var repo = try Repo.open(alloc, "../imgui/.git");
 490     defer repo.close();
 491
 492     if (try repo.getObject(0xceb2b2c62d6f8f3686dcacecd5be931839b02c77)) |o| {
 493         switch (try o.parse(alloc)) {
 494             .t => |t| {
 495                 defer t.deinit();
 496                 for (t.items) |treeEntry| {
 497                     std.debug.print("{s} {s} {x}\n", .{ treeEntry.permissions, treeEntry.name, treeEntry.id });
 498                 }
 499             },
 500             else => {},
 501         }
 502     }
 503 }
 504
 505 test "list commits" {
 506     var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
 507     defer arena.deinit();
 508     const alloc = arena.allocator();
 509
 510     var repo = try Repo.open(alloc, "../imgui/.git");
 511     defer repo.close();
 512
 513     const head = try repo.getHead();
 514
 515     var id = head;
 516
 517     for (0..3) |_| {
 518         if (try repo.getObject(id)) |o| {
 519             switch (try o.parse(alloc)) {
 520                 .c => |c| {
 521                     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 });
 522                     id = c.parent;
 523                 },
 524                 else => {},
 525             }
 526         }
 527     }
 528 }
 529
 530 test "list blobs" {
 531     var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
 532     defer arena.deinit();
 533     const alloc = arena.allocator();
 534
 535     var repo = try Repo.open(alloc, "../imgui/.git");
 536     defer repo.close();
 537
 538     if (try repo.getObject(0xceb2b2c62d6f8f3686dcacecd5be931839b02c77)) |o| {
 539         switch (try o.parse(alloc)) {
 540             .t => |t| {
 541                 defer t.deinit();
 542                 for (t.items) |treeEntry| {
 543                     if (try repo.getObject(treeEntry.id)) |bo| {
 544                         if (treeEntry.permissions.len == 6) {
 545                             std.debug.print("{s}: [{x} {}]{s}\n", .{ treeEntry.name, treeEntry.id, bo.data.len, bo.data[0..50] });
 546                         } else {
 547                             std.debug.print("[{s}]\n", .{treeEntry.name});
 548                         }
 549                     }
 550                 }
 551             },
 552             else => {},
 553         }
 554     }
 555 }
 556
 557 test "basic frontend" {
 558     var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
 559     defer arena.deinit();
 560     const alloc = arena.allocator();
 561
 562     var repo = try Repo.open(alloc, "../imgui/.git");
 563     defer repo.close();
 564
 565     const head = try repo.getHead();
 566
 567     var id = head;
 568
 569     for (0..3) |_| {
 570         if (try repo.getObject(id)) |o| {
 571             switch (try o.parse(alloc)) {
 572                 .c => |c| {
 573                     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 });
 574                     id = c.parent;
 575                 },
 576                 else => {},
 577             }
 578         }
 579     }
 580 }