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