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