Coverage for coverage / numbits.py: 100.000%

42 statements  

« prev     ^ index     » next       coverage.py v7.12.1a0.dev1, created at 2025-11-30 17:57 +0000

1# Licensed under the Apache License: http://www.apache.org/licenses/LICENSE-2.0 

2# For details: https://github.com/coveragepy/coveragepy/blob/main/NOTICE.txt 

3 

4""" 

5Functions to manipulate packed binary representations of number sets. 

6 

7To save space, coverage stores sets of line numbers in SQLite using a packed 

8binary representation called a numbits. A numbits is a set of positive 

9integers. 

10 

11A numbits is stored as a blob in the database. The exact meaning of the bytes 

12in the blobs should be considered an implementation detail that might change in 

13the future. Use these functions to work with those binary blobs of data. 

14 

15""" 

16 

17from __future__ import annotations 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

18 

19import json 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

20import sqlite3 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

21from collections.abc import Iterable 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

22from itertools import zip_longest 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

23 

24 

25def nums_to_numbits(nums: Iterable[int]) -> bytes: 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

26 """Convert `nums` into a numbits. 

27 

28 Arguments: 

29 nums: a reusable iterable of integers, the line numbers to store. 

30 

31 Returns: 

32 A binary blob. 

33 """ 

34 try: 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

35 nbytes = max(nums) // 8 + 1 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

36 except ValueError: 1abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ01234

37 # nums was empty. 

38 return b"" 1abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ01234

39 b = bytearray(nbytes) 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

40 for num in nums: 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

41 b[num // 8] |= 1 << num % 8 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

42 return bytes(b) 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

43 

44 

45def numbits_to_nums(numbits: bytes) -> list[int]: 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

46 """Convert a numbits into a list of numbers. 

47 

48 Arguments: 

49 numbits: a binary blob, the packed number set. 

50 

51 Returns: 

52 A list of ints. 

53 

54 When registered as a SQLite function by :func:`register_sqlite_functions`, 

55 this returns a string, a JSON-encoded list of ints. 

56 

57 """ 

58 nums = [] 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

59 for byte_i, byte in enumerate(numbits): 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

60 for bit_i in range(8): 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

61 if byte & (1 << bit_i): 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

62 nums.append(byte_i * 8 + bit_i) 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

63 return nums 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

64 

65 

66def numbits_union(numbits1: bytes, numbits2: bytes) -> bytes: 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

67 """Compute the union of two numbits. 

68 

69 Returns: 

70 A new numbits, the union of `numbits1` and `numbits2`. 

71 """ 

72 byte_pairs = zip_longest(numbits1, numbits2, fillvalue=0) 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

73 return bytes(b1 | b2 for b1, b2 in byte_pairs) 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

74 

75 

76def numbits_intersection(numbits1: bytes, numbits2: bytes) -> bytes: 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

77 """Compute the intersection of two numbits. 

78 

79 Returns: 

80 A new numbits, the intersection `numbits1` and `numbits2`. 

81 """ 

82 byte_pairs = zip_longest(numbits1, numbits2, fillvalue=0) 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

83 intersection_bytes = bytes(b1 & b2 for b1, b2 in byte_pairs) 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

84 return intersection_bytes.rstrip(b"\0") 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

85 

86 

87def numbits_any_intersection(numbits1: bytes, numbits2: bytes) -> bool: 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

88 """Is there any number that appears in both numbits? 

89 

90 Determine whether two number sets have a non-empty intersection. This is 

91 faster than computing the intersection. 

92 

93 Returns: 

94 A bool, True if there is any number in both `numbits1` and `numbits2`. 

95 """ 

96 byte_pairs = zip_longest(numbits1, numbits2, fillvalue=0) 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

97 return any(b1 & b2 for b1, b2 in byte_pairs) 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

98 

99 

100def num_in_numbits(num: int, numbits: bytes) -> bool: 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

101 """Does the integer `num` appear in `numbits`? 

102 

103 Returns: 

104 A bool, True if `num` is a member of `numbits`. 

105 """ 

106 nbyte, nbit = divmod(num, 8) 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

107 if nbyte >= len(numbits): 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

108 return False 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

109 return bool(numbits[nbyte] & (1 << nbit)) 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

110 

111 

112def register_sqlite_functions(connection: sqlite3.Connection) -> None: 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

113 """ 

114 Define numbits functions in a SQLite connection. 

115 

116 This defines these functions for use in SQLite statements: 

117 

118 * :func:`numbits_union` 

119 * :func:`numbits_intersection` 

120 * :func:`numbits_any_intersection` 

121 * :func:`num_in_numbits` 

122 * :func:`numbits_to_nums` 

123 

124 `connection` is a :class:`sqlite3.Connection <python:sqlite3.Connection>` 

125 object. After creating the connection, pass it to this function to 

126 register the numbits functions. Then you can use numbits functions in your 

127 queries:: 

128 

129 import sqlite3 

130 from coverage.numbits import register_sqlite_functions 

131 

132 conn = sqlite3.connect("example.db") 

133 register_sqlite_functions(conn) 

134 c = conn.cursor() 

135 # Kind of a nonsense query: 

136 # Find all the files and contexts that executed line 47 in any file: 

137 c.execute( 

138 "select file_id, context_id from line_bits where num_in_numbits(?, numbits)", 

139 (47,) 

140 ) 

141 """ 

142 connection.create_function("numbits_union", 2, numbits_union) 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

143 connection.create_function("numbits_intersection", 2, numbits_intersection) 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

144 connection.create_function("numbits_any_intersection", 2, numbits_any_intersection) 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

145 connection.create_function("num_in_numbits", 2, num_in_numbits) 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234

146 connection.create_function("numbits_to_nums", 1, lambda b: json.dumps(numbits_to_nums(b))) 1abcdefghijklmnopqrstuvwxyzABCDEF5GH6IJ7KL8MN9OP!QR#ST$UV%WX'YZ(01)234