2 # Copyright 2013 The Chromium Authors. All rights reserved.
3 # Use of this source code is governed by a BSD-style license that can be
4 # found in the LICENSE file.
6 """Usage: %prog [options] [<commitref>]*
8 If no <commitref>'s are supplied, it defaults to HEAD.
10 Calculates the generation number for one or more commits in a git repo.
12 Generation number of a commit C with parents P is defined as:
13 generation_number(C, []) = 0
14 generation_number(C, P) = max(map(generation_number, P)) + 1
16 This number can be used to order commits relative to each other, as long as for
17 any pair of the commits, one is an ancestor of the other.
19 Since calculating the generation number of a commit requires walking that
20 commit's entire history, this script caches all calculated data inside the git
21 repo that it operates on in the ref 'refs/number/commits'.
33 import git_common as git
37 CHUNK_SIZE = struct.calcsize(CHUNK_FMT)
38 DIRTY_TREES = collections.defaultdict(int)
39 REF = 'refs/number/commits'
40 AUTHOR_NAME = 'git-number'
41 AUTHOR_EMAIL = 'chrome-infrastructure-team@google.com'
43 # Number of bytes to use for the prefix on our internal number structure.
44 # 0 is slow to deserialize. 2 creates way too much bookeeping overhead (would
45 # need to reimplement cache data structures to be a bit more sophisticated than
46 # dicts. 1 seems to be just right.
49 # Set this to 'threads' to gather coverage data while testing.
53 def pathlify(hash_prefix):
54 """Converts a binary object hash prefix into a posix path, one folder per
57 >>> pathlify('\xDE\xAD')
60 return '/'.join('%02x' % ord(b) for b in hash_prefix)
63 @git.memoize_one(threadsafe=False)
64 def get_number_tree(prefix_bytes):
65 """Returns a dictionary of the git-number registry specified by
68 This is in the form of {<full binary ref>: <gen num> ...}
70 >>> get_number_tree('\x83\xb4')
71 {'\x83\xb4\xe3\xe4W\xf9J*\x8f/c\x16\xecD\xd1\x04\x8b\xa9qz': 169, ...}
73 ref = '%s:%s' % (REF, pathlify(prefix_bytes))
76 raw = buffer(git.run('cat-file', 'blob', ref, autostrip=False))
77 return dict(struct.unpack_from(CHUNK_FMT, raw, i * CHUNK_SIZE)
78 for i in xrange(len(raw) / CHUNK_SIZE))
79 except subprocess2.CalledProcessError:
83 @git.memoize_one(threadsafe=False)
84 def get_num(commit_hash):
85 """Returns the generation number for a commit.
87 Returns None if the generation number for this commit hasn't been calculated
88 yet (see load_generation_numbers()).
90 return get_number_tree(commit_hash[:PREFIX_LEN]).get(commit_hash)
93 def clear_caches(on_disk=False):
94 """Clears in-process caches for e.g. unit testing."""
95 get_number_tree.clear()
98 git.run('update-ref', '-d', REF)
101 def intern_number_tree(tree):
102 """Transforms a number tree (in the form returned by |get_number_tree|) into
105 Returns the git blob id as hex-encoded string.
107 >>> d = {'\x83\xb4\xe3\xe4W\xf9J*\x8f/c\x16\xecD\xd1\x04\x8b\xa9qz': 169}
108 >>> intern_number_tree(d)
109 'c552317aa95ca8c3f6aae3357a4be299fbcb25ce'
111 with tempfile.TemporaryFile() as f:
112 for k, v in sorted(tree.iteritems()):
113 f.write(struct.pack(CHUNK_FMT, k, v))
115 return git.intern_f(f)
118 def leaf_map_fn((pre, tree)):
119 """Converts a prefix and number tree into a git index line."""
120 return '100644 blob %s\t%s\0' % (intern_number_tree(tree), pathlify(pre))
123 def finalize(targets):
124 """Saves all cache data to the git repository.
126 After calculating the generation number for |targets|, call finalize() to
127 save all the work to the git repository.
129 This in particular saves the trees referred to by DIRTY_TREES.
134 msg = 'git-number Added %s numbers' % sum(DIRTY_TREES.itervalues())
136 idx = os.path.join(git.run('rev-parse', '--git-dir'), 'number.idx')
137 env = os.environ.copy()
138 env['GIT_INDEX_FILE'] = idx
140 progress_message = 'Finalizing: (%%(count)d/%d)' % len(DIRTY_TREES)
141 with git.ProgressPrinter(progress_message) as inc:
142 git.run('read-tree', REF, env=env)
144 prefixes_trees = ((p, get_number_tree(p)) for p in sorted(DIRTY_TREES))
145 updater = subprocess2.Popen(['git', 'update-index', '-z', '--index-info'],
146 stdin=subprocess2.PIPE, env=env)
148 with git.ScopedPool(kind=POOL_KIND) as leaf_pool:
149 for item in leaf_pool.imap(leaf_map_fn, prefixes_trees):
150 updater.stdin.write(item)
153 updater.stdin.close()
155 assert updater.returncode == 0
157 tree_id = git.run('write-tree', env=env)
159 # Git user.name and/or user.email may not be configured, so specifying
160 # them explicitly. They are not used, but requried by Git.
161 '-c', 'user.name=%s' % AUTHOR_NAME,
162 '-c', 'user.email=%s' % AUTHOR_EMAIL,
165 '-p'] + git.hash_multi(REF)
167 commit_cmd.extend(['-p', binascii.hexlify(t)])
168 commit_cmd.append(tree_id)
169 commit_hash = git.run(*commit_cmd)
170 git.run('update-ref', REF, commit_hash)
174 def preload_tree(prefix):
175 """Returns the prefix and parsed tree object for the specified prefix."""
176 return prefix, get_number_tree(prefix)
179 def all_prefixes(depth=PREFIX_LEN):
180 for x in (chr(i) for i in xrange(255)):
181 # This isn't covered because PREFIX_LEN currently == 1
182 if depth > 1: # pragma: no cover
183 for r in all_prefixes(depth - 1):
189 def load_generation_numbers(targets):
190 """Populates the caches of get_num and get_number_tree so they contain
191 the results for |targets|.
193 Loads cached numbers from disk, and calculates missing numbers if one or
194 more of |targets| is newer than the cached calculations.
197 targets - An iterable of binary-encoded full git commit hashes.
199 # In case they pass us a generator, listify targets.
200 targets = list(targets)
202 if all(get_num(t) is not None for t in targets):
205 if git.tree(REF) is None:
206 empty = git.mktree({})
207 commit_hash = git.run('commit-tree', '-m', 'Initial commit from git-number',
209 git.run('update-ref', REF, commit_hash)
211 with git.ScopedPool(kind=POOL_KIND) as pool:
212 preload_iter = pool.imap_unordered(preload_tree, all_prefixes())
216 with git.ProgressPrinter('Loading commits: %(count)d') as inc:
217 # Curiously, buffering the list into memory seems to be the fastest
218 # approach in python (as opposed to iterating over the lines in the
219 # stdout as they're produced). GIL strikes again :/
221 'rev-list', '--topo-order', '--parents', '--reverse', '^' + REF,
222 ] + map(binascii.hexlify, targets)
223 for line in git.run(*cmd).splitlines():
224 tokens = map(binascii.unhexlify, line.split())
225 rev_list.append((tokens[0], tokens[1:]))
228 get_number_tree.update(preload_iter)
230 with git.ProgressPrinter('Counting: %%(count)d/%d' % len(rev_list)) as inc:
231 for commit_hash, pars in rev_list:
232 num = max(map(get_num, pars)) + 1 if pars else 0
234 prefix = commit_hash[:PREFIX_LEN]
235 get_number_tree(prefix)[commit_hash] = num
236 DIRTY_TREES[prefix] += 1
237 get_num.set(commit_hash, num)
242 def main(): # pragma: no cover
243 parser = optparse.OptionParser(usage=sys.modules[__name__].__doc__)
244 parser.add_option('--no-cache', action='store_true',
245 help='Do not actually cache anything we calculate.')
246 parser.add_option('--reset', action='store_true',
247 help='Reset the generation number cache and quit.')
248 parser.add_option('-v', '--verbose', action='count', default=0,
249 help='Be verbose. Use more times for more verbosity.')
250 opts, args = parser.parse_args()
252 levels = [logging.ERROR, logging.INFO, logging.DEBUG]
253 logging.basicConfig(level=levels[min(opts.verbose, len(levels) - 1)])
255 # 'git number' should only be used on bots.
256 if os.getenv('CHROME_HEADLESS') != '1':
257 logging.error("'git-number' is an infrastructure tool that is only "
258 "intended to be used internally by bots. Developers should "
259 "use the 'Cr-Commit-Position' value in the commit's message.")
264 clear_caches(on_disk=True)
268 targets = git.parse_commitrefs(*(args or ['HEAD']))
269 except git.BadCommitRefException as e:
272 load_generation_numbers(targets)
273 if not opts.no_cache:
276 print '\n'.join(map(str, map(get_num, targets)))
278 except KeyboardInterrupt:
282 if __name__ == '__main__': # pragma: no cover