dulwich.bitmap

module documentation

Support for Git packfile bitmaps.

Bitmaps store reachability information for packfiles, enabling faster object counting and enumeration operations without full graph traversal.

The bitmap format uses EWAH (Enhanced Word-Aligned Hybrid) compression for efficient storage and fast bitwise operations.

Class	`BitmapEntry`	A single bitmap entry for a commit.
Class	`EWAHBitmap`	EWAH (Enhanced Word-Aligned Hybrid) compressed bitmap.
Class	`PackBitmap`	A pack bitmap index.
Function	`apply_xor_compression`	Apply XOR compression to bitmaps.
Function	`bitmap_to_object_shas`	Convert a bitmap to a set of object SHAs.
Function	`build_name_hash_cache`	Build name-hash cache for all objects in a pack.
Function	`build_reachability_bitmap`	Build a reachability bitmap for a commit.
Function	`build_type_bitmaps`	Build type bitmaps for all objects in a pack.
Function	`find_commit_bitmaps`	Find which packs have bitmaps for the given commits.
Function	`generate_bitmap`	Generate a complete bitmap for a pack.
Function	`read_bitmap`	Read a bitmap index file.
Function	`read_bitmap_file`	Read bitmap data from a file object.
Function	`select_bitmap_commits`	Select commits for bitmap generation.
Function	`write_bitmap`	Write a bitmap index file.
Function	`write_bitmap_file`	Write bitmap data to a file object.
Constant	`BITMAP_OPT_FULL_DAG`	Undocumented
Constant	`BITMAP_OPT_HASH_CACHE`	Undocumented
Constant	`BITMAP_OPT_LOOKUP_TABLE`	Undocumented
Constant	`BITMAP_OPT_PSEUDO_MERGES`	Undocumented
Constant	`BITMAP_SIGNATURE`	Undocumented
Constant	`BITMAP_VERSION`	Undocumented
Constant	`DEFAULT_COMMIT_INTERVAL`	Undocumented
Constant	`MAX_LITERAL_WORDS`	Undocumented
Constant	`MAX_XOR_OFFSET`	Undocumented
Function	`_compute_name_hash`	Compute the name hash for a tree entry.
Function	`_encode_ewah_words`	Encode a list of 64-bit words using EWAH run-length compression.

def apply_xor_compression(bitmaps: list[tuple[ObjectID, EWAHBitmap]], max_xor_offset: int = MAX_XOR_OFFSET) -> list[tuple[ObjectID, EWAHBitmap, int]]: ¶

Apply XOR compression to bitmaps.

XOR compression stores some bitmaps as XOR differences from previous bitmaps, reducing storage size when bitmaps are similar.

Parameters
bitmaps:`list[tuple[ObjectID, EWAHBitmap]]`	List of (commit_sha, bitmap) tuples
max_xor_offset:`int`	Maximum offset to search for XOR base

Returns
`list[tuple[ObjectID, EWAHBitmap, int]]`	List of (commit_sha, bitmap, xor_offset) tuples

def bitmap_to_object_shas(bitmap: EWAHBitmap, pack_index: PackIndex, type_filter: EWAHBitmap | None = None) -> set[ObjectID]: ¶

Convert a bitmap to a set of object SHAs.

Parameters
bitmap:`EWAHBitmap`	The EWAH bitmap with set bits for objects
pack_index:`PackIndex`	Pack index to map positions to SHAs
type_filter:`EWAHBitmap \| None`	Optional type bitmap to filter results (e.g., commits only)

Returns
`set[ObjectID]`	Set of object SHAs (hex format)

def build_name_hash_cache(sha_to_pos: dict[RawObjectID, int], object_store: BaseObjectStore) -> list[int]: ¶

Build name-hash cache for all objects in a pack.

The name-hash cache stores a hash of the name for each object, which can speed up path-based operations.

Parameters
sha_to_pos:`dict[RawObjectID, int]`	Pre-built mapping from SHA to position in pack
object_store:`BaseObjectStore`	Object store to read objects

Returns
`list[int]`	List of 32-bit hash values, one per object in the pack

def build_reachability_bitmap(commit_sha: ObjectID, sha_to_pos: dict[RawObjectID, int], object_store: BaseObjectStore) -> EWAHBitmap: ¶

Build a reachability bitmap for a commit.

The bitmap has a bit set for each object that is reachable from the commit. The bit position corresponds to the object's position in the pack index.

Parameters
commit_sha:`ObjectID`	The commit to build a bitmap for
sha_to_pos:`dict[RawObjectID, int]`	Pre-built mapping from SHA to position in pack
object_store:`BaseObjectStore`	Object store to traverse objects

Returns
`EWAHBitmap`	EWAH bitmap with bits set for reachable objects

def build_type_bitmaps(sha_to_pos: dict[RawObjectID, int], object_store: BaseObjectStore) -> tuple[EWAHBitmap, EWAHBitmap, EWAHBitmap, EWAHBitmap]: ¶

Build type bitmaps for all objects in a pack.

Type bitmaps classify objects by type: commit, tree, blob, or tag.

Parameters
sha_to_pos:`dict[RawObjectID, int]`	Pre-built mapping from SHA to position in pack
object_store:`BaseObjectStore`	Object store to read object types

Returns
`tuple[EWAHBitmap, EWAHBitmap, EWAHBitmap, EWAHBitmap]`	Tuple of (commit_bitmap, tree_bitmap, blob_bitmap, tag_bitmap)

def find_commit_bitmaps(commit_shas: set[ObjectID], packs: Iterable[Pack]) -> dict[ObjectID, tuple[Pack, PackBitmap, dict[RawObjectID, int]]]: ¶

Find which packs have bitmaps for the given commits.

Parameters
commit_shas:`set[ObjectID]`	Set of commit SHAs to look for
packs:`Iterable[Pack]`	Iterable of Pack objects to search

Returns
`dict[ObjectID, tuple[Pack, PackBitmap, dict[RawObjectID, int]]]`	Dict mapping commit SHA to (pack, pack_bitmap, position) tuple

def generate_bitmap(pack_index: PackIndex, object_store: BaseObjectStore, refs: dict[Ref, ObjectID], pack_checksum: bytes, include_hash_cache: bool = True, include_lookup_table: bool = True, commit_interval: int | None = None, progress: Callable[[str], None] | None = None) -> PackBitmap: ¶

Generate a complete bitmap for a pack.

Parameters
pack_index:`PackIndex`	Pack index for the pack
object_store:`BaseObjectStore`	Object store to read objects from
refs:`dict[Ref, ObjectID]`	Dictionary of ref names to commit SHAs
pack_checksum:`bytes`	SHA-1 checksum of the pack file
include_hash_cache:`bool`	Whether to include name-hash cache
include_lookup_table:`bool`	Whether to include lookup table
commit_interval:`int \| None`	Include every Nth commit in history (None for default)
progress:`Callable[[str], None] \| None`	Optional progress reporting callback

Returns
`PackBitmap`	Complete PackBitmap ready to write to disk

def read_bitmap(filename: str | os.PathLike[str], pack_index: PackIndex | None = None) -> PackBitmap: ¶

Read a bitmap index file.

Parameters
filename:`str \| os.PathLike[str]`	Path to the .bitmap file
pack_index:`PackIndex \| None`	Optional PackIndex to resolve object positions to SHAs

Returns
`PackBitmap`	Loaded PackBitmap

Raises
`ValueError`	If file format is invalid
`ChecksumMismatch`	If checksum verification fails

def read_bitmap_file(f: IO[bytes], pack_index: PackIndex | None = None) -> PackBitmap: ¶

Read bitmap data from a file object.

Parameters
f:`IO[bytes]`	File object to read from
pack_index:`PackIndex \| None`	Optional PackIndex to resolve object positions to SHAs

Returns
`PackBitmap`	Loaded PackBitmap

Raises
`ValueError`	If file format is invalid

def select_bitmap_commits(refs: dict[Ref, ObjectID], object_store: BaseObjectStore, commit_interval: int = DEFAULT_COMMIT_INTERVAL) -> list[ObjectID]: ¶

Select commits for bitmap generation.

Uses Git's strategy: - All branch and tag tips - Every Nth commit in history

Parameters
refs:`dict[Ref, ObjectID]`	Dictionary of ref names to commit SHAs
object_store:`BaseObjectStore`	Object store to read commits from
commit_interval:`int`	Include every Nth commit in history

Returns
`list[ObjectID]`	List of commit SHAs to create bitmaps for

def write_bitmap(filename: str | os.PathLike[str], bitmap: PackBitmap): ¶

Write a bitmap index file.

Parameters
filename:`str \| os.PathLike[str]`	Path to write the .bitmap file
bitmap:`PackBitmap`	PackBitmap to write

def write_bitmap_file(f: IO[bytes], bitmap: PackBitmap): ¶

Write bitmap data to a file object.

Parameters
f:`IO[bytes]`	File object to write to
bitmap:`PackBitmap`	PackBitmap to write

BITMAP_OPT_FULL_DAG: int = ¶

Undocumented

Value

BITMAP_OPT_HASH_CACHE: int = ¶

Undocumented

Value

BITMAP_OPT_LOOKUP_TABLE: int = ¶

Undocumented

Value

BITMAP_OPT_PSEUDO_MERGES: int = ¶

Undocumented

Value

BITMAP_SIGNATURE: bytes = ¶

Undocumented

Value

b'BITM'

BITMAP_VERSION: int = ¶

Undocumented

Value

DEFAULT_COMMIT_INTERVAL: int = ¶

Undocumented

Value

MAX_LITERAL_WORDS: int = ¶

Undocumented

Value

2147483647

MAX_XOR_OFFSET: int = ¶

Undocumented

Value

def _compute_name_hash(name: bytes) -> int: ¶

Compute the name hash for a tree entry.

This is the same algorithm Git uses for the name-hash cache.

Parameters
name:`bytes`	The name of the tree entry

Returns
`int`	32-bit hash value

def _encode_ewah_words(words: list[int]) -> list[int]: ¶

Encode a list of 64-bit words using EWAH run-length compression.

Parameters
words:`list[int]`	List of 64-bit words to encode

Returns
`list[int]`	List of compressed words (RLWs followed by literals)