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