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