Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/dulwich/midx.py: 16%

1# midx.py -- Multi-Pack-Index (MIDX) support

4# SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later

5# Dulwich is dual-licensed under the Apache License, Version 2.0 and the GNU

6# General Public License as published by the Free Software Foundation; version 2.0

7# or (at your option) any later version. You can redistribute it and/or

8# modify it under the terms of either of these two licenses.

10# Unless required by applicable law or agreed to in writing, software

11# distributed under the License is distributed on an "AS IS" BASIS,

12# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

13# See the License for the specific language governing permissions and

14# limitations under the License.

15#

16# You should have received a copy of the licenses; if not, see

17# <http://www.gnu.org/licenses/> for a copy of the GNU General Public License

18# and <http://www.apache.org/licenses/LICENSE-2.0> for a copy of the Apache

19# License, Version 2.0.

20#

22"""Multi-Pack-Index (MIDX) support.

24A multi-pack-index (MIDX) provides a single index that covers multiple pack files,

25enabling fast object lookup across all packs without opening each pack index.

27The MIDX file format consists of:

28- A header with signature, version, and hash algorithm

29- A chunk lookup table

30- Multiple chunks containing pack names, OID fanout, OID lookup, and object offsets

31- A trailer with checksum

33This module provides:

34- Reading MIDX files

35- Writing MIDX files

36- Integration with pack-based object stores

38Limitations:

39- Incremental MIDX chains are not yet supported (base_midx_files must be 0)

40- BTMP (bitmapped packfiles) chunk is not yet implemented

41- RIDX (reverse index) chunk is not yet implemented

43Note: Incremental MIDX chains were introduced in Git 2.47 as an experimental

44feature, where multiple MIDX files can be chained together. The format includes

45a base_midx_files field in the header and uses a multi-pack-index.d/ directory

46with a multi-pack-index-chain file. This feature is not yet supported by Dulwich

47as the specification is still evolving.

48"""

50__all__ = [

51 "CHUNK_BTMP",

52 "CHUNK_LOFF",

53 "CHUNK_OIDF",

54 "CHUNK_OIDL",

55 "CHUNK_OOFF",

56 "CHUNK_PNAM",

57 "CHUNK_RIDX",

58 "HASH_ALGORITHM_SHA1",

59 "HASH_ALGORITHM_SHA256",

60 "MIDX_SIGNATURE",

61 "MIDX_VERSION",

62 "MultiPackIndex",

63 "load_midx",

64 "load_midx_file",

65 "write_midx",

66]

68import mmap

69import os

70import struct

71from collections.abc import Iterator

72from io import UnsupportedOperation

73from typing import IO, Any

75from .file import GitFile, _GitFile

76from .objects import ObjectID, RawObjectID

77from .pack import SHA1Writer

79has_mmap = True

81# MIDX signature

82MIDX_SIGNATURE = b"MIDX"

84# MIDX version

85MIDX_VERSION = 1

87# Chunk identifiers (4 bytes each)

88CHUNK_PNAM = b"PNAM" # Packfile names

89CHUNK_OIDF = b"OIDF" # OID fanout table

90CHUNK_OIDL = b"OIDL" # OID lookup table

91CHUNK_OOFF = b"OOFF" # Object offsets

92CHUNK_LOFF = b"LOFF" # Large offsets (optional)

93CHUNK_BTMP = b"BTMP" # Bitmapped packfiles (optional)

94CHUNK_RIDX = b"RIDX" # Reverse index (optional)

96# Hash algorithm identifiers

97HASH_ALGORITHM_SHA1 = 1

98HASH_ALGORITHM_SHA256 = 2

100

101class MultiPackIndex:

102 """Multi-pack-index for efficient object lookup across multiple pack files."""

103

104 def __init__(

105 self,

106 filename: str | os.PathLike[str],

107 file: IO[bytes] | _GitFile | None = None,

108 contents: bytes | None = None,

109 size: int | None = None,

110 ) -> None:

111 """Initialize a MultiPackIndex.

112

113 Args:

114 filename: Path to the MIDX file

115 file: Optional file object

116 contents: Optional mmap'd contents

117 size: Optional size of the MIDX file

118 """

119 self._filename = os.fspath(filename)

120 self._file = file

121 self._size = size

122

123 # Instance variables that will be set during parsing

124 self.version: int

125 self.hash_algorithm: int

126 self.hash_size: int

127 self.chunk_count: int

128 self.base_midx_files: int

129 self.pack_count: int

130 self.pack_names: list[str]

131 self.object_count: int

132 self._contents: bytes | Any

133 self._chunks: dict[bytes, int]

134 self._fanout_table: list[int]

135 self._oidl_offset: int

136 self._ooff_offset: int

137 self._loff_offset: int

138

139 # Load file contents

140 if contents is None:

141 if file is None:

142 with GitFile(filename, "rb") as f:

143 self._contents, self._size = self._load_file_contents(f, size)

144 else:

145 self._contents, self._size = self._load_file_contents(file, size)

146 else:

147 self._contents = contents

148

149 # Parse header

150 self._parse_header()

151

152 # Parse chunk lookup table

153 self._parse_chunk_table()

154

155 def _load_file_contents(

156 self, f: IO[bytes] | _GitFile, size: int | None = None

157 ) -> tuple[bytes | Any, int]:

158 """Load contents from a file, preferring mmap when possible.

159

160 Args:

161 f: File-like object to load

162 size: Expected size, or None to determine from file

163

164 Returns:

165 Tuple of (contents, size)

166 """

167 try:

168 fd = f.fileno()

169 except (UnsupportedOperation, AttributeError):

170 fd = None

171

172 # Attempt to use mmap if possible

173 if fd is not None:

174 if size is None:

175 size = os.fstat(fd).st_size

176 if has_mmap:

177 try:

178 contents = mmap.mmap(fd, size, access=mmap.ACCESS_READ)

179 except (OSError, ValueError):

180 # Can't mmap - perhaps a socket or invalid file descriptor

181 pass

182 else:

183 return contents, size

184

185 # Fall back to reading entire file into memory

186 contents_bytes = f.read()

187 size = len(contents_bytes)

188 return contents_bytes, size

189

190 def _parse_header(self) -> None:

191 """Parse the MIDX header."""

192 if len(self._contents) < 12:

193 raise ValueError("MIDX file too small")

194

195 # Check signature

196 signature = self._contents[0:4]

197 if signature != MIDX_SIGNATURE:

198 raise ValueError(f"Invalid MIDX signature: {signature!r}")

199

200 # Read version

201 self.version = self._contents[4]

202 if self.version != MIDX_VERSION:

203 raise ValueError(f"Unsupported MIDX version: {self.version}")

204

205 # Read object ID version (hash algorithm)

206 self.hash_algorithm = self._contents[5]

207 if self.hash_algorithm == HASH_ALGORITHM_SHA1:

208 self.hash_size = 20

209 elif self.hash_algorithm == HASH_ALGORITHM_SHA256:

210 self.hash_size = 32

211 else:

212 raise ValueError(f"Unknown hash algorithm: {self.hash_algorithm}")

213

214 # Read chunk count

215 self.chunk_count = self._contents[6]

216

217 # Read base MIDX files count (currently always 0)

218 self.base_midx_files = self._contents[7]

219 if self.base_midx_files != 0:

220 raise ValueError("Incremental MIDX not yet supported")

221

222 # Read pack file count

223 (self.pack_count,) = struct.unpack(">L", self._contents[8:12])

224

225 def _parse_chunk_table(self) -> None:

226 """Parse the chunk lookup table."""

227 self._chunks = {}

228

229 # Chunk table starts at offset 12

230 offset = 12

231

232 # Each chunk entry is 12 bytes (4-byte ID + 8-byte offset)

233 for i in range(self.chunk_count + 1): # +1 for terminator

234 chunk_id = self._contents[offset : offset + 4]

235 (chunk_offset,) = struct.unpack(

236 ">Q", self._contents[offset + 4 : offset + 12]

237 )

238

239 if chunk_id == b"\x00\x00\x00\x00":

240 # Terminator entry

241 break

242

243 self._chunks[chunk_id] = chunk_offset

244 offset += 12

245

246 # Parse required chunks

247 self._parse_pnam_chunk()

248 self._parse_oidf_chunk()

249 self._parse_oidl_chunk()

250 self._parse_ooff_chunk()

251

252 # Parse optional chunks

253 if CHUNK_LOFF in self._chunks:

254 self._parse_loff_chunk()

255

256 def _parse_pnam_chunk(self) -> None:

257 """Parse the Packfile Names (PNAM) chunk."""

258 if CHUNK_PNAM not in self._chunks:

259 raise ValueError("Required PNAM chunk not found")

260

261 offset = self._chunks[CHUNK_PNAM]

262 self.pack_names = []

263

264 # Find the end of the PNAM chunk (next chunk or end of chunks section)

265 next_offset = min(

266 (o for o in self._chunks.values() if o > offset),

267 default=len(self._contents),

268 )

269

270 # Parse null-terminated pack names

271 current = offset

272 while current < next_offset:

273 # Find the next null terminator

274 null_pos = self._contents.find(b"\x00", current, next_offset)

275 if null_pos == -1:

276 break

277

278 pack_name = self._contents[current:null_pos].decode("utf-8")

279 if pack_name: # Skip empty strings (padding)

280 self.pack_names.append(pack_name)

281 current = null_pos + 1

282

283 def _parse_oidf_chunk(self) -> None:

284 """Parse the OID Fanout (OIDF) chunk."""

285 if CHUNK_OIDF not in self._chunks:

286 raise ValueError("Required OIDF chunk not found")

287

288 offset = self._chunks[CHUNK_OIDF]

289 self._fanout_table = []

290

291 # Read 256 4-byte entries

292 for i in range(256):

293 (count,) = struct.unpack(

294 ">L", self._contents[offset + i * 4 : offset + i * 4 + 4]

295 )

296 self._fanout_table.append(count)

297

298 # Total object count is the last entry

299 self.object_count = self._fanout_table[255]

300

301 def _parse_oidl_chunk(self) -> None:

302 """Parse the OID Lookup (OIDL) chunk."""

303 if CHUNK_OIDL not in self._chunks:

304 raise ValueError("Required OIDL chunk not found")

305

306 self._oidl_offset = self._chunks[CHUNK_OIDL]

307

308 def _parse_ooff_chunk(self) -> None:

309 """Parse the Object Offsets (OOFF) chunk."""

310 if CHUNK_OOFF not in self._chunks:

311 raise ValueError("Required OOFF chunk not found")

312

313 self._ooff_offset = self._chunks[CHUNK_OOFF]

314

315 def _parse_loff_chunk(self) -> None:

316 """Parse the Large Offsets (LOFF) chunk."""

317 self._loff_offset = self._chunks[CHUNK_LOFF]

318

319 def __len__(self) -> int:

320 """Return the number of objects in this MIDX."""

321 return self.object_count

322

323 def _get_oid(self, index: int) -> RawObjectID:

324 """Get the object ID at the given index.

325

326 Args:

327 index: Index of the object

328

329 Returns:

330 Binary object ID

331 """

332 if index < 0 or index >= self.object_count:

333 raise IndexError(f"Index {index} out of range")

334

335 offset = self._oidl_offset + index * self.hash_size

336 return RawObjectID(self._contents[offset : offset + self.hash_size])

337

338 def _get_pack_info(self, index: int) -> tuple[int, int]:

339 """Get pack ID and offset for object at the given index.

340

341 Args:

342 index: Index of the object

343

344 Returns:

345 Tuple of (pack_id, offset)

346 """

347 if index < 0 or index >= self.object_count:

348 raise IndexError(f"Index {index} out of range")

349

350 # Each entry is 8 bytes (4-byte pack ID + 4-byte offset)

351 offset = self._ooff_offset + index * 8

352

353 (pack_id,) = struct.unpack(">L", self._contents[offset : offset + 4])

354 (pack_offset,) = struct.unpack(">L", self._contents[offset + 4 : offset + 8])

355

356 # Check if this is a large offset (MSB set)

357 if pack_offset & 0x80000000:

358 # Look up in LOFF chunk

359 if CHUNK_LOFF not in self._chunks:

360 raise ValueError("Large offset found but no LOFF chunk")

361

362 large_index = pack_offset & 0x7FFFFFFF

363 large_offset_pos = self._loff_offset + large_index * 8

364 (pack_offset,) = struct.unpack(

365 ">Q", self._contents[large_offset_pos : large_offset_pos + 8]

366 )

367

368 return pack_id, pack_offset

369

370 def object_offset(self, sha: ObjectID | RawObjectID) -> tuple[str, int] | None:

371 """Return the pack name and offset for the given object.

372

373 Args:

374 sha: Binary SHA-1 or SHA-256 hash

375

376 Returns:

377 Tuple of (pack_name, offset) or None if not found

378 """

379 if len(sha) != self.hash_size:

380 raise ValueError(

381 f"SHA size mismatch: expected {self.hash_size}, got {len(sha)}"

382 )

383

384 # Use fanout table to narrow search range

385 first_byte = sha[0]

386 start_idx = 0 if first_byte == 0 else self._fanout_table[first_byte - 1]

387 end_idx = self._fanout_table[first_byte]

388

389 # Binary search within the range

390 while start_idx < end_idx:

391 mid = (start_idx + end_idx) // 2

392 mid_sha = self._get_oid(mid)

393

394 if mid_sha == sha:

395 # Found it!

396 pack_id, offset = self._get_pack_info(mid)

397 return self.pack_names[pack_id], offset

398 elif mid_sha < sha:

399 start_idx = mid + 1

400 else:

401 end_idx = mid

402

403 return None

404

405 def __contains__(self, sha: ObjectID | RawObjectID) -> bool:

406 """Check if the given object SHA is in this MIDX.

407

408 Args:

409 sha: Binary SHA hash

410

411 Returns:

412 True if the object is in this MIDX

413 """

414 return self.object_offset(sha) is not None

415

416 def iterentries(self) -> Iterator[tuple[RawObjectID, str, int]]:

417 """Iterate over all entries in this MIDX.

418

419 Yields:

420 Tuples of (sha, pack_name, offset)

421 """

422 for i in range(self.object_count):

423 sha = self._get_oid(i)

424 pack_id, offset = self._get_pack_info(i)

425 pack_name = self.pack_names[pack_id]

426 yield sha, pack_name, offset

427

428 def close(self) -> None:

429 """Close the MIDX file and release mmap resources."""

430 # Close mmap'd contents first if it's an mmap object

431 if self._contents is not None and has_mmap:

432 if isinstance(self._contents, mmap.mmap):

433 self._contents.close()

434 self._contents = None

435

436 # Close file handle

437 if self._file is not None:

438 self._file.close()

439 self._file = None

440

441

442def load_midx(path: str | os.PathLike[str]) -> MultiPackIndex:

443 """Load a multi-pack-index file by path.

444

445 Args:

446 path: Path to the MIDX file

447

448 Returns:

449 A MultiPackIndex loaded from the given path

450 """

451 with GitFile(path, "rb") as f:

452 return load_midx_file(path, f)

453

454

455def load_midx_file(

456 path: str | os.PathLike[str], f: IO[bytes] | _GitFile

457) -> MultiPackIndex:

458 """Load a multi-pack-index from a file-like object.

459

460 Args:

461 path: Path for the MIDX file

462 f: File-like object

463

464 Returns:

465 A MultiPackIndex loaded from the given file

466 """

467 return MultiPackIndex(path, file=f)

468

469

470def write_midx(

471 f: IO[bytes],

472 pack_index_entries: list[tuple[str, list[tuple[RawObjectID, int, int | None]]]],

473 hash_algorithm: int = HASH_ALGORITHM_SHA1,

474) -> bytes:

475 """Write a multi-pack-index file.

476

477 Args:

478 f: File-like object to write to

479 pack_index_entries: List of (pack_name, entries) tuples where entries are

480 (sha, offset, crc32) tuples, sorted by SHA

481 hash_algorithm: Hash algorithm to use (1=SHA-1, 2=SHA-256)

482

483 Returns:

484 SHA-1 checksum of the written MIDX file

485 """

486 if hash_algorithm == HASH_ALGORITHM_SHA1:

487 hash_size = 20

488 elif hash_algorithm == HASH_ALGORITHM_SHA256:

489 hash_size = 32

490 else:

491 raise ValueError(f"Unknown hash algorithm: {hash_algorithm}")

492

493 # Wrap file in SHA1Writer to compute checksum

494 writer = SHA1Writer(f)

495

496 # Sort pack entries by pack name (required by Git)

497 pack_index_entries_sorted = sorted(pack_index_entries, key=lambda x: x[0])

498

499 # Collect all objects from all packs, deduplicating objects that appear

500 # in multiple packs. Git's MIDX format requires strictly increasing OIDs

501 # in the OIDL chunk, so duplicates must be resolved. When the same object

502 # is in multiple packs, we keep the occurrence from the first pack (in

503 # pack-name order), matching how Git itself handles duplicates.

504 seen: dict[RawObjectID, tuple[int, int]] = {} # sha -> (pack_id, offset)

505 pack_names: list[str] = []

506

507 for pack_id, (pack_name, entries) in enumerate(pack_index_entries_sorted):

508 pack_names.append(pack_name)

509 for sha, offset, _crc32 in entries:

510 if sha not in seen:

511 seen[sha] = (pack_id, offset)

512

513 all_objects: list[tuple[RawObjectID, int, int]] = [

514 (sha, pack_id, offset) for sha, (pack_id, offset) in seen.items()

515 ]

516

517 # Sort all objects by SHA

518 all_objects.sort(key=lambda x: x[0])

519

520 # Calculate offsets for chunks

521 num_packs = len(pack_names)

522 num_objects = len(all_objects)

523

524 # Header: 12 bytes

525 header_size = 12

526

527 # Chunk count: PNAM, OIDF, OIDL, OOFF, and optionally LOFF

528 # We'll determine if LOFF is needed later

529 chunk_count = 4 # PNAM, OIDF, OIDL, OOFF

530

531 # Check if we need LOFF chunk (for offsets >= 2^31)

532 need_loff = any(offset >= 2**31 for _sha, _pack_id, offset in all_objects)

533 if need_loff:

534 chunk_count += 1

535

536 # Chunk table: (chunk_count + 1) * 12 bytes (including terminator)

537 chunk_table_size = (chunk_count + 1) * 12

538

539 # Calculate chunk offsets

540 current_offset = header_size + chunk_table_size

541

542 # PNAM chunk: pack names as null-terminated strings, padded to 4-byte boundary

543 pnam_data = b"".join(name.encode("utf-8") + b"\x00" for name in pack_names)

544 # Pad to 4-byte boundary

545 pnam_padding = (4 - len(pnam_data) % 4) % 4

546 pnam_data += b"\x00" * pnam_padding

547 pnam_offset = current_offset

548 current_offset += len(pnam_data)

549

550 # OIDF chunk: 256 * 4 bytes

551 oidf_offset = current_offset

552 oidf_size = 256 * 4

553 current_offset += oidf_size

554

555 # OIDL chunk: num_objects * hash_size bytes

556 oidl_offset = current_offset

557 oidl_size = num_objects * hash_size

558 current_offset += oidl_size

559

560 # OOFF chunk: num_objects * 8 bytes (4 for pack_id + 4 for offset)

561 ooff_offset = current_offset

562 ooff_size = num_objects * 8

563 current_offset += ooff_size

564

565 # LOFF chunk (if needed): variable size

566 # We'll calculate the exact size when we know how many large offsets we have

567 loff_offset = current_offset if need_loff else 0

568 large_offsets: list[int] = []

569

570 # Calculate trailer offset (where checksum starts)

571 # We need to pre-calculate large offset count for accurate trailer offset

572 if need_loff:

573 # Count large offsets

574 large_offset_count = sum(1 for _, _, offset in all_objects if offset >= 2**31)

575 loff_size = large_offset_count * 8

576 trailer_offset = current_offset + loff_size

577 else:

578 trailer_offset = current_offset

579

580 # Write header

581 writer.write(MIDX_SIGNATURE) # 4 bytes: signature

582 writer.write(bytes([MIDX_VERSION])) # 1 byte: version

583 writer.write(bytes([hash_algorithm])) # 1 byte: hash algorithm

584 writer.write(bytes([chunk_count])) # 1 byte: chunk count

585 writer.write(bytes([0])) # 1 byte: base MIDX files (always 0)

586 writer.write(struct.pack(">L", num_packs)) # 4 bytes: pack count

587

588 # Write chunk table

589 chunk_table = [

590 (CHUNK_PNAM, pnam_offset),

591 (CHUNK_OIDF, oidf_offset),

592 (CHUNK_OIDL, oidl_offset),

593 (CHUNK_OOFF, ooff_offset),

594 ]

595 if need_loff:

596 chunk_table.append((CHUNK_LOFF, loff_offset))

597

598 for chunk_id, chunk_offset in chunk_table:

599 writer.write(chunk_id) # 4 bytes

600 writer.write(struct.pack(">Q", chunk_offset)) # 8 bytes

601

602 # Write terminator (points to where trailer/checksum starts)

603 writer.write(b"\x00\x00\x00\x00") # 4 bytes

604 writer.write(struct.pack(">Q", trailer_offset)) # 8 bytes

605

606 # Write PNAM chunk

607 writer.write(pnam_data)

608

609 # Write OIDF chunk (fanout table)

610 fanout: list[int] = [0] * 256

611 for sha, _pack_id, _offset in all_objects:

612 first_byte = sha[0]

613 fanout[first_byte] += 1

614

615 # Convert counts to cumulative

616 cumulative = 0

617 for i in range(256):

618 cumulative += fanout[i]

619 writer.write(struct.pack(">L", cumulative))

620

621 # Write OIDL chunk (object IDs)

622 for sha, _pack_id, _offset in all_objects:

623 writer.write(sha)

624

625 # Write OOFF chunk (pack ID and offset for each object)

626 for _sha, pack_id, offset in all_objects:

627 writer.write(struct.pack(">L", pack_id))

628

629 if offset >= 2**31:

630 # Use large offset table

631 large_offset_index = len(large_offsets)

632 large_offsets.append(offset)

633 # Set MSB to indicate large offset

634 writer.write(struct.pack(">L", 0x80000000 | large_offset_index))

635 else:

636 writer.write(struct.pack(">L", offset))

637

638 # Write LOFF chunk if needed

639 if need_loff:

640 for large_offset in large_offsets:

641 writer.write(struct.pack(">Q", large_offset))

642

643 # Write checksum

644 return writer.write_sha()

645

646

647def write_midx_file(

648 path: str | os.PathLike[str],

649 pack_index_entries: list[tuple[str, list[tuple[RawObjectID, int, int | None]]]],

650 hash_algorithm: int = HASH_ALGORITHM_SHA1,

651) -> bytes:

652 """Write a multi-pack-index file to disk.

653

654 Args:

655 path: Path where to write the MIDX file

656 pack_index_entries: List of (pack_name, entries) tuples where entries are

657 (sha, offset, crc32) tuples, sorted by SHA

658 hash_algorithm: Hash algorithm to use (1=SHA-1, 2=SHA-256)

659

660 Returns:

661 SHA-1 checksum of the written MIDX file

662 """

663 with GitFile(path, "wb") as f:

664 return write_midx(f, pack_index_entries, hash_algorithm)

665

666

667# TODO: Add support for incremental MIDX chains

668# TODO: Add support for BTMP and RIDX chunks for bitmap integration