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