2 # Copyright 2017 The Chromium Authors
3 # Use of this source code is governed by a BSD-style license that can be
4 # found in the LICENSE file.
20 class TokenContext(object):
21 """Metadata about a token.
24 row: Row index of the token in the data file.
25 column: Column index of the token in the data file.
26 token: The token string.
27 commit: A Commit object that corresponds to the commit that added
31 def __init__(self, row, column, token, commit=None):
42 hash: The commit hash.
43 author_name: The author's name.
44 author_email: the author's email.
45 author_date: The date and time the author created this commit.
46 message: The commit message.
47 diff: The commit diff.
50 def __init__(self, hash, author_name, author_email, author_date, message,
53 self.author_name = author_name
54 self.author_email = author_email
55 self.author_date = author_date
56 self.message = message
60 def tokenize_data(data, tokenize_by_char, tokenize_whitespace):
64 data: String to tokenize.
65 tokenize_by_char: If true, individual characters are treated as tokens.
66 Otherwise, tokens are either symbols or strings of both alphanumeric
67 characters and underscores.
68 tokenize_whitespace: Treat non-newline whitespace characters as tokens.
71 A list of lists of TokenContexts. Each list represents a line.
82 if not tokenize_by_char and (c.isalnum() or c == '_'):
87 identifier_start = column
91 line_contexts.append(TokenContext(row, identifier_start, identifier))
93 if not c.isspace() or (tokenize_whitespace and c != '\n'):
94 line_contexts.append(TokenContext(row, column, c))
99 contexts.append(line_contexts)
104 contexts.append(line_contexts)
108 def compute_unified_diff(old_tokens, new_tokens):
109 """Computes the diff between |old_tokens| and |new_tokens|.
112 old_tokens: Token strings corresponding to the old data.
113 new_tokens: Token strings corresponding to the new data.
116 The diff, in unified diff format.
118 return difflib.unified_diff(old_tokens, new_tokens, n=0, lineterm='')
121 def parse_chunk_header_file_range(file_range):
122 """Parses a chunk header file range.
124 Diff chunk headers have the form:
125 @@ -<file-range> +<file-range> @@
126 File ranges have the form:
127 <start line number>,<number of lines changed>
130 file_range: A chunk header file range.
133 A tuple (range_start, range_end). The endpoints are adjusted such that
134 iterating over [range_start, range_end) will give the changed indices.
136 if ',' in file_range:
137 file_range_parts = file_range.split(',')
138 start = int(file_range_parts[0])
139 amount = int(file_range_parts[1])
141 return (start, start)
142 return (start - 1, start + amount - 1)
144 return (int(file_range) - 1, int(file_range))
147 def compute_changed_token_indices(previous_tokens, current_tokens):
148 """Computes changed and added tokens.
151 previous_tokens: Tokens corresponding to the old file.
152 current_tokens: Tokens corresponding to the new file.
155 A tuple (added_tokens, changed_tokens).
156 added_tokens: A list of indices into |current_tokens|.
157 changed_tokens: A map of indices into |current_tokens| to
158 indices into |previous_tokens|.
160 prev_file_chunk_end = 0
161 prev_patched_chunk_end = 0
164 for line in compute_unified_diff(previous_tokens, current_tokens):
165 if line.startswith("@@"):
166 parts = line.split(' ')
167 removed = parts[1].lstrip('-')
168 removed_start, removed_end = parse_chunk_header_file_range(removed)
169 added = parts[2].lstrip('+')
170 added_start, added_end = parse_chunk_header_file_range(added)
171 for i in range(added_start, added_end):
172 added_tokens.append(i)
173 for i in range(0, removed_start - prev_patched_chunk_end):
174 changed_tokens[prev_file_chunk_end + i] = prev_patched_chunk_end + i
175 prev_patched_chunk_end = removed_end
176 prev_file_chunk_end = added_end
177 for i in range(0, len(previous_tokens) - prev_patched_chunk_end):
178 changed_tokens[prev_file_chunk_end + i] = prev_patched_chunk_end + i
179 return added_tokens, changed_tokens
182 def flatten_nested_list(l):
183 """Flattens a list and provides a mapping from elements in the list back
184 into the nested list.
190 A tuple (flattened, index_to_position):
191 flattened: The flattened list.
192 index_to_position: A list of pairs (r, c) such that
193 index_to_position[i] == (r, c); flattened[i] == l[r][c]
196 index_to_position = {}
199 for nested_list in l:
200 for element in nested_list:
201 index_to_position[len(flattened)] = (r, c)
202 flattened.append(element)
206 return (flattened, index_to_position)
209 def compute_changed_token_positions(previous_tokens, current_tokens):
210 """Computes changed and added token positions.
213 previous_tokens: A list of lists of token strings. Lines in the file
214 correspond to the nested lists.
215 current_tokens: A list of lists of token strings. Lines in the file
216 correspond to the nested lists.
219 A tuple (added_token_positions, changed_token_positions):
220 added_token_positions: A list of pairs that index into |current_tokens|.
221 changed_token_positions: A map from pairs that index into
222 |current_tokens| to pairs that index into |previous_tokens|.
224 flat_previous_tokens, previous_index_to_position = flatten_nested_list(
226 flat_current_tokens, current_index_to_position = flatten_nested_list(
228 added_indices, changed_indices = compute_changed_token_indices(
229 flat_previous_tokens, flat_current_tokens)
230 added_token_positions = [current_index_to_position[i] for i in added_indices]
231 changed_token_positions = {
232 current_index_to_position[current_i]:
233 previous_index_to_position[changed_indices[current_i]]
234 for current_i in changed_indices
236 return (added_token_positions, changed_token_positions)
239 def parse_chunks_from_diff(diff):
240 """Returns a generator of chunk data from a diff.
243 diff: A list of strings, with each string being a line from a diff
244 in unified diff format.
247 A generator of tuples (added_lines_start, added_lines_end, removed_lines)
251 while not line.startswith('@@'):
253 parts = line.split(' ')
254 previous_start, previous_end = parse_chunk_header_file_range(
255 parts[1].lstrip('-'))
256 current_start, current_end = parse_chunk_header_file_range(
257 parts[2].lstrip('+'))
260 added_lines_start = None
261 added_lines_end = None
263 while previous_start < previous_end or current_start < current_end:
267 if not in_delta and (firstchar == '-' or firstchar == '+'):
269 added_lines_start = current_start
270 added_lines_end = current_start
274 removed_lines.append(line)
276 elif firstchar == '+':
278 added_lines_end = current_start
279 elif firstchar == ' ':
282 yield (added_lines_start, added_lines_end, removed_lines)
286 yield (added_lines_start, added_lines_end, removed_lines)
289 def should_skip_commit(commit):
290 """Decides if |commit| should be skipped when computing the blame.
292 Commit 5d4451e deleted all files in the repo except for DEPS. The
293 next commit, 1e7896, brought them back. This is a hack to skip
294 those commits (except for the files they modified). If we did not
295 do this, changes would be incorrectly attributed to 1e7896.
298 commit: A Commit object.
301 A boolean indicating if this commit should be skipped.
304 '1e78967ed2f1937b3809c19d91e7dd62d756d307',
305 '5d4451ebf298d9d71f716cc0135f465cec41fcd0',
307 if commit.hash not in banned_commits:
309 banned_commits_file_exceptions = [
311 'chrome/browser/ui/views/file_manager_dialog_browsertest.cc',
313 for line in commit.diff:
314 if line.startswith('---') or line.startswith('+++'):
315 if line.split(' ')[1] in banned_commits_file_exceptions:
317 elif line.startswith('@@'):
322 def generate_substrings(file):
323 """Generates substrings from a file stream, where substrings are
326 For example, the input:
328 would produce the output:
332 file: A readable file.
334 BUF_SIZE = 448 # Experimentally found to be pretty fast.
337 buf = file.read(BUF_SIZE)
338 parts = buf.split(b'\0')
339 data.append(parts[0])
341 joined = b''.join(data)
343 yield joined.decode()
344 for i in range(1, len(parts) - 1):
346 yield parts[i].decode()
348 if len(buf) < BUF_SIZE:
349 joined = b''.join(data)
351 yield joined.decode()
355 def generate_commits(git_log_stdout):
356 """Parses git log output into a stream of Commit objects.
358 substring_generator = generate_substrings(git_log_stdout)
361 hash = next(substring_generator)
362 author_name = next(substring_generator)
363 author_email = next(substring_generator)
364 author_date = next(substring_generator)
365 message = next(substring_generator).rstrip('\n')
366 diff = next(substring_generator).split('\n')[1:-1]
367 yield Commit(hash, author_name, author_email, author_date, message, diff)
368 except StopIteration:
372 def uberblame_aux(file_name, git_log_stdout, data, tokenization_method):
373 """Computes the uberblame of file |file_name|.
376 file_name: File to uberblame.
377 git_log_stdout: A file object that represents the git log output.
378 data: A string containing the data of file |file_name|.
379 tokenization_method: A function that takes a string and returns a list of
383 A tuple (data, blame).
385 blame: A list of TokenContexts.
387 blame = tokenization_method(data)
390 uber_blame = (data, blame[:])
392 for commit in generate_commits(git_log_stdout):
393 if should_skip_commit(commit):
397 for (added_lines_start, added_lines_end,
398 removed_lines) in parse_chunks_from_diff(commit.diff):
399 added_lines_start += offset
400 added_lines_end += offset
401 previous_contexts = [
403 for line_previous in removed_lines
404 for token_lines in tokenization_method(line_previous)
406 previous_tokens = [[context.token for context in contexts]
407 for contexts in previous_contexts]
408 current_contexts = blame[added_lines_start:added_lines_end]
409 current_tokens = [[context.token for context in contexts]
410 for contexts in current_contexts]
411 added_token_positions, changed_token_positions = (
412 compute_changed_token_positions(previous_tokens, current_tokens))
413 for r, c in added_token_positions:
414 current_contexts[r][c].commit = commit
416 for r, c in changed_token_positions:
417 pr, pc = changed_token_positions[(r, c)]
418 previous_contexts[pr][pc] = current_contexts[r][c]
420 assert added_lines_start <= added_lines_end <= len(blame)
421 current_blame_size = len(blame)
422 blame[added_lines_start:added_lines_end] = previous_contexts
423 offset += len(blame) - current_blame_size
425 assert blame == [] or blame == [[]]
429 def uberblame(file_name, revision, tokenization_method):
430 """Computes the uberblame of file |file_name|.
433 file_name: File to uberblame.
434 revision: The revision to start the uberblame at.
435 tokenization_method: A function that takes a string and returns a list of
439 A tuple (data, blame).
441 blame: A list of TokenContexts.
445 'git', 'log', '--minimal', '--no-prefix', '--follow', '-m',
446 '--first-parent', '-p',
447 '-U%d' % DIFF_CONTEXT, '-z', '--format=%x00%H%x00%an%x00%ae%x00%ad%x00%B',
448 revision, '--', file_name
450 git_log = subprocess.Popen(
451 cmd_git_log, stdout=subprocess.PIPE, stderr=subprocess.PIPE)
452 data = subprocess.check_output(
453 ['git', 'show', '%s:%s' % (revision, file_name)]).decode()
454 data, blame = uberblame_aux(file_name, git_log.stdout, data,
457 stderr = git_log.communicate()[1].decode()
458 if git_log.returncode != 0:
459 raise subprocess.CalledProcessError(git_log.returncode, cmd_git_log, stderr)
463 def generate_pastel_color():
464 """Generates a random color from a nice looking pastel palette.
467 The color, formatted as hex string. For example, white is "#FFFFFF".
469 (h, l, s) = (random.uniform(0, 1), random.uniform(0.8, 0.9), random.uniform(
471 (r, g, b) = colorsys.hls_to_rgb(h, l, s)
472 return "#%0.2X%0.2X%0.2X" % (int(r * 255), int(g * 255), int(b * 255))
475 def colorize_diff(diff):
476 """Colorizes a diff for use in an HTML page.
479 diff: The diff, in unified diff format, as a list of line strings.
482 The HTML-formatted diff, as a string. The diff will already be escaped.
487 escaped = html.escape(line.replace('\r', ''), quote=True)
488 if line.startswith('+'):
489 colorized.append('<span class=\\"addition\\">%s</span>' % escaped)
490 elif line.startswith('-'):
491 colorized.append('<span class=\\"deletion\\">%s</span>' % escaped)
492 elif line.startswith('@@'):
493 context_begin = escaped.find('@@', 2)
494 assert context_begin != -1
496 '<span class=\\"chunk_meta\\">%s</span>'
497 '<span class=\\"chunk_context\\">%s</span'
498 % (escaped[0:context_begin + 2], escaped[context_begin + 2:]))
499 elif line.startswith('diff') or line.startswith('index'):
500 colorized.append('<span class=\\"file_header\\">%s</span>' % escaped)
502 colorized.append('<span class=\\"context_line\\">%s</span>' % escaped)
503 return '\n'.join(colorized)
506 def create_visualization(data, blame):
507 """Creates a web page to visualize |blame|.
510 data: The data file as returned by uberblame().
511 blame: A list of TokenContexts as returned by uberblame().
514 The HTML for the generated page, as a string.
516 # Use the same seed for the color generator on each run so that
517 # loading the same blame of the same file twice will result in the
518 # same generated HTML page.
519 random.seed(0x52937865ec62d1ea)
525 font-family: monospace;
531 outline: 1pt solid #00000030;
532 outline-offset: -1pt;
544 .context_line .chunk_context {
561 #commit_display_container {
572 function display_commit(hash) {
573 var e = document.getElementById("commit_display");
574 e.innerHTML = commit_data[hash]
579 <div id="file_display">
583 <td valign="top" id="linenums">
593 <div id="commit_display_container" valign="top">
594 <pre id="commit_display" />
599 page = textwrap.dedent(page)
604 blame = [context for contexts in blame for context in contexts]
607 for line in data.split('\n'):
610 for c in line + '\n':
611 if blame_index < len(blame):
612 token_context = blame[blame_index]
613 if (row == token_context.row and
614 column == token_context.column + len(token_context.token)):
615 if (blame_index + 1 == len(blame) or blame[blame_index].commit.hash !=
616 blame[blame_index + 1].commit.hash):
617 lines.append('</span>')
619 if blame_index < len(blame):
620 token_context = blame[blame_index]
621 if row == token_context.row and column == token_context.column:
622 if (blame_index == 0 or blame[blame_index - 1].commit.hash !=
623 blame[blame_index].commit.hash):
624 hash = token_context.commit.hash
625 commits[hash] = token_context.commit
626 if hash not in commit_colors:
627 commit_colors[hash] = generate_pastel_color()
628 color = commit_colors[hash]
629 lines.append(('<span class="token" style="background-color: %s" ' +
630 'onclick="display_commit("%s")">') % (color,
632 lines.append(html.escape(c))
635 commit_data = ['{\n']
636 commit_display_format = """\
638 Author: {author_name} <{author_email}>
644 commit_display_format = textwrap.dedent(commit_display_format)
645 links = re.compile(r'(https?:\/\/\S+)')
647 commit = commits[hash]
648 commit_display = commit_display_format.format(
650 author_name=commit.author_name,
651 author_email=commit.author_email,
652 author_date=commit.author_date,
653 message=commit.message)
654 commit_display = html.escape(commit_display, quote=True)
655 commit_display += colorize_diff(commit.diff)
656 commit_display = re.sub(links, '<a href=\\"\\1\\">\\1</a>', commit_display)
657 commit_display = commit_display.replace('\n', '\\n')
658 commit_data.append('"%s": "%s",\n' % (hash, commit_display))
659 commit_data.append('}')
660 commit_data = ''.join(commit_data)
661 line_nums = range(1, row if lastline.strip() == '' else row + 1)
662 line_nums = '\n'.join([str(num) for num in line_nums])
663 lines = ''.join(lines)
664 return page % (commit_data, line_nums, lines)
667 def show_visualization(page):
668 """Display |html| in a web browser.
671 html: The contents of the file to display, as a string.
673 # Keep the temporary file around so the browser has time to open it.
674 # TODO(thomasanderson): spin up a temporary web server to serve this
675 # file so we don't have to leak it.
676 html_file = tempfile.NamedTemporaryFile(delete=False, suffix='.html')
677 html_file.write(page.encode())
679 if sys.platform.startswith('linux'):
680 # Don't show any messages when starting the browser.
681 saved_stdout = os.dup(1)
682 saved_stderr = os.dup(2)
685 os.open(os.devnull, os.O_RDWR)
686 os.open(os.devnull, os.O_RDWR)
687 webbrowser.open('file://' + html_file.name)
688 if sys.platform.startswith('linux'):
689 os.dup2(saved_stdout, 1)
690 os.dup2(saved_stderr, 2)
691 os.close(saved_stdout)
692 os.close(saved_stderr)
696 parser = argparse.ArgumentParser(
697 description='Show what revision last modified each token of a file.')
702 help='show only commits starting from a revision')
703 parser.add_argument('file', help='the file to uberblame')
705 '--skip-visualization',
707 help='do not display the blame visualization in a web browser')
709 '--tokenize-by-char',
711 help='treat individual characters as tokens')
713 '--tokenize-whitespace',
715 help='also blame non-newline whitespace characters')
716 args = parser.parse_args(argv)
718 def tokenization_method(data):
719 return tokenize_data(data, args.tokenize_by_char, args.tokenize_whitespace)
721 data, blame = uberblame(args.file, args.revision, tokenization_method)
722 html = create_visualization(data, blame)
723 if not args.skip_visualization:
724 show_visualization(html)
728 if __name__ == '__main__':
729 sys.exit(main(sys.argv[1:]))