add_header.py 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486
  1. #!/usr/bin/env python3
  2. # Copyright 2021 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.
  5. """Helper for adding or removing an include to/from source file(s).
  6. clang-format already provides header sorting functionality; however, the
  7. functionality is limited to sorting headers within a block of headers surrounded
  8. by blank lines (these are a heuristic to avoid clang breaking ordering for
  9. headers sensitive to inclusion order, e.g. <windows.h>).
  10. As a result, inserting a new header is a bit more complex than simply inserting
  11. the new header at the top and running clang-format.
  12. This script implements additional logic to:
  13. - classify different blocks of headers by type (C system, C++ system, user)
  14. - find the appropriate insertion point for the new header
  15. - creating a new header block if necessary
  16. As a bonus, it does *also* sort the includes, though any sorting disagreements
  17. with clang-format should be resolved in favor of clang-format.
  18. It also supports removing a header with option `--remove`.
  19. Usage:
  20. tools/add_header.py --header '<utility>' foo/bar.cc foo/baz.cc foo/baz.h
  21. tools/add_header.py --header '<vector>' --remove foo/bar.cc foo/baz.cc foo/baz.h
  22. """
  23. import argparse
  24. import difflib
  25. import os.path
  26. import re
  27. import sys
  28. # The specific values of these constants are also used as a sort key for
  29. # ordering different header types in the correct relative order.
  30. _HEADER_TYPE_C_SYSTEM = 0
  31. _HEADER_TYPE_CXX_SYSTEM = 1
  32. _HEADER_TYPE_USER = 2
  33. _HEADER_TYPE_INVALID = -1
  34. def ClassifyHeader(decorated_name):
  35. if IsCSystemHeader(decorated_name):
  36. return _HEADER_TYPE_C_SYSTEM
  37. elif IsCXXSystemHeader(decorated_name):
  38. return _HEADER_TYPE_CXX_SYSTEM
  39. elif IsUserHeader(decorated_name):
  40. return _HEADER_TYPE_USER
  41. else:
  42. return _HEADER_TYPE_INVALID
  43. def UndecoratedName(decorated_name):
  44. """Returns the undecorated version of decorated_name by removing "" or <>."""
  45. assert IsSystemHeader(decorated_name) or IsUserHeader(decorated_name)
  46. return decorated_name[1:-1]
  47. def IsSystemHeader(decorated_name):
  48. """Returns true if decorated_name looks like a system header."""
  49. return decorated_name[0] == '<' and decorated_name[-1] == '>'
  50. def IsCSystemHeader(decorated_name):
  51. """Returns true if decoraed_name looks like a C system header."""
  52. return IsSystemHeader(decorated_name) and UndecoratedName(
  53. decorated_name).endswith('.h')
  54. def IsCXXSystemHeader(decorated_name):
  55. """Returns true if decoraed_name looks like a C++ system header."""
  56. return IsSystemHeader(
  57. decorated_name) and not UndecoratedName(decorated_name).endswith('.h')
  58. def IsUserHeader(decorated_name):
  59. """Returns true if decoraed_name looks like a user header."""
  60. return decorated_name[0] == '"' and decorated_name[-1] == '"'
  61. _EMPTY_LINE_RE = re.compile(r'\s*$')
  62. _COMMENT_RE = re.compile(r'\s*//(.*)$')
  63. _INCLUDE_RE = re.compile(
  64. r'\s*#(import|include)\s+([<"].+?[">])\s*?(?://(.*))?$')
  65. def FindIncludes(lines):
  66. """Finds the block of #includes, assuming Google+Chrome C++ style source.
  67. Note that this doesn't simply return a slice of the input lines, because
  68. having the actual indices simplifies things when generatingn the updated
  69. source text.
  70. Args:
  71. lines: The source text split into lines.
  72. Returns:
  73. A tuple of begin, end indices that can be used to slice the input lines to
  74. contain the includes to process. Returns -1, -1 if no such block of
  75. input lines could be found.
  76. """
  77. begin = end = -1
  78. for idx, line in enumerate(lines):
  79. # Skip over any initial comments (e.g. the copyright boilerplate) or empty
  80. # lines.
  81. # TODO(dcheng): This means that any preamble comment associated with the
  82. # first header will be dropped. So far, this hasn't broken anything, but
  83. # maybe this needs to be more clever.
  84. # TODO(dcheng): #define and #undef should probably also be allowed.
  85. if _EMPTY_LINE_RE.match(line) or _COMMENT_RE.match(line):
  86. continue
  87. m = _INCLUDE_RE.match(line)
  88. if not m:
  89. if begin < 0:
  90. # No match, but no #includes have been seen yet. Keep scanning for the
  91. # first #include.
  92. continue
  93. # Give up, it's something weird that probably requires manual
  94. # intervention.
  95. break
  96. if begin < 0:
  97. begin = idx
  98. end = idx + 1
  99. return begin, end
  100. class Include(object):
  101. """Represents an #include/#import and any interesting metadata for it.
  102. Attributes:
  103. decorated_name: The name of the header file, decorated with <> for system
  104. headers or "" for user headers.
  105. directive: 'include' or 'import'
  106. TODO(dcheng): In the future, this may need to support C++ modules.
  107. preamble: Any comment lines that precede this include line, e.g.:
  108. // This is a preamble comment
  109. // for a header file.
  110. #include <windows.h>
  111. would have a preamble of
  112. ['// This is a preamble comment', '// for a header file.'].
  113. inline_comment: Any comment that comes after the #include on the same line,
  114. e.g.
  115. #include <windows.h> // For CreateWindowExW()
  116. would be parsed with an inline comment of ' For CreateWindowExW'.
  117. header_type: The header type corresponding to decorated_name as determined
  118. by ClassifyHeader().
  119. is_primary_header: True if this is the primary related header of a C++
  120. implementation file. Any primary header will be sorted to the top in its
  121. own separate block.
  122. """
  123. def __init__(self, decorated_name, directive, preamble, inline_comment):
  124. self.decorated_name = decorated_name
  125. assert directive == 'include' or directive == 'import'
  126. self.directive = directive
  127. self.preamble = preamble
  128. self.inline_comment = inline_comment
  129. self.header_type = ClassifyHeader(decorated_name)
  130. assert self.header_type != _HEADER_TYPE_INVALID
  131. self.is_primary_header = False
  132. def __repr__(self):
  133. return str((self.decorated_name, self.directive, self.preamble,
  134. self.inline_comment, self.header_type, self.is_primary_header))
  135. def ShouldInsertNewline(self, previous_include):
  136. # Per the Google C++ style guide, different blocks of headers should be
  137. # separated by an empty line.
  138. return (self.is_primary_header != previous_include.is_primary_header
  139. or self.header_type != previous_include.header_type)
  140. def ToSource(self):
  141. """Generates a C++ source representation of this include."""
  142. source = []
  143. source.extend(self.preamble)
  144. include_line = '#%s %s' % (self.directive, self.decorated_name)
  145. if self.inline_comment:
  146. include_line = include_line + ' //' + self.inline_comment
  147. source.append(include_line)
  148. return [line.rstrip() for line in source]
  149. def ParseIncludes(lines):
  150. """Parses lines into a list of Include objects. Returns None on failure.
  151. Args:
  152. lines: A list of strings representing C++ source text.
  153. Returns:
  154. A list of Include objects representing the parsed input lines, or None if
  155. the input lines could not be parsed.
  156. """
  157. includes = []
  158. preamble = []
  159. for line in lines:
  160. if _EMPTY_LINE_RE.match(line):
  161. if preamble:
  162. # preamble contents are flushed when an #include directive is matched.
  163. # If preamble is non-empty, that means there is a preamble separated
  164. # from its #include directive by at least one newline. Just give up,
  165. # since the sorter has no idea how to preserve structure in this case.
  166. return None
  167. continue
  168. m = _INCLUDE_RE.match(line)
  169. if not m:
  170. preamble.append(line)
  171. continue
  172. includes.append(Include(m.group(2), m.group(1), preamble, m.group(3)))
  173. preamble = []
  174. # In theory, the caller should never pass a list of lines with a dangling
  175. # preamble. But there's a test case that exercises this, and just in case it
  176. # actually happens, fail a bit more gracefully.
  177. if preamble:
  178. return None
  179. return includes
  180. def _DecomposePath(filename):
  181. """Decomposes a filename into a list of directories and the basename.
  182. Args:
  183. filename: A filename!
  184. Returns:
  185. A tuple of a list of directories and a string basename.
  186. """
  187. dirs = []
  188. dirname, basename = os.path.split(filename)
  189. while dirname:
  190. dirname, last = os.path.split(dirname)
  191. dirs.append(last)
  192. dirs.reverse()
  193. # Remove the extension from the basename.
  194. basename = os.path.splitext(basename)[0]
  195. return dirs, basename
  196. _PLATFORM_SUFFIX = (
  197. r'(?:_(?:android|aura|chromeos|fuchsia|ios|linux|mac|ozone|posix|win|x11))?'
  198. )
  199. _TEST_SUFFIX = r'(?:_(?:browser|interactive_ui|perf|ui|unit)?test)?'
  200. def MarkPrimaryInclude(includes, filename):
  201. """Finds the primary header in includes and marks it as such.
  202. Per the style guide, if moo.cc's main purpose is to implement or test the
  203. functionality in moo.h, moo.h should be ordered first in the includes.
  204. Args:
  205. includes: A list of Include objects.
  206. filename: The filename to use as the basis for finding the primary header.
  207. """
  208. # Header files never have a primary include.
  209. if filename.endswith('.h'):
  210. return
  211. # First pass. Looking for exact match primary header.
  212. exact_match_primary_header = f'{os.path.splitext(filename)[0]}.h'
  213. for include in includes:
  214. if IsUserHeader(include.decorated_name) and UndecoratedName(
  215. include.decorated_name) == exact_match_primary_header:
  216. include.is_primary_header = True
  217. return
  218. basis = _DecomposePath(filename)
  219. # Second pass. The list of includes is searched in reverse order of length.
  220. # Even though matching is fuzzy, moo_posix.h should take precedence over moo.h
  221. # when considering moo_posix.cc.
  222. includes.sort(key=lambda i: -len(i.decorated_name))
  223. for include in includes:
  224. if include.header_type != _HEADER_TYPE_USER:
  225. continue
  226. to_test = _DecomposePath(UndecoratedName(include.decorated_name))
  227. # If the basename to test is longer than the basis, just skip it and
  228. # continue. moo.c should never match against moo_posix.h.
  229. if len(to_test[1]) > len(basis[1]):
  230. continue
  231. # The basename in the two paths being compared need to fuzzily match.
  232. # This allows for situations where moo_posix.cc implements the interfaces
  233. # defined in moo.h.
  234. escaped_basename = re.escape(to_test[1])
  235. if not (re.match(escaped_basename + _PLATFORM_SUFFIX + _TEST_SUFFIX + '$',
  236. basis[1]) or
  237. re.match(escaped_basename + _TEST_SUFFIX + _PLATFORM_SUFFIX + '$',
  238. basis[1])):
  239. continue
  240. # The topmost directory name must match, and the rest of the directory path
  241. # should be 'substantially similar'.
  242. s = difflib.SequenceMatcher(None, to_test[0], basis[0])
  243. first_matched = False
  244. total_matched = 0
  245. for match in s.get_matching_blocks():
  246. if total_matched == 0 and match.a == 0 and match.b == 0:
  247. first_matched = True
  248. total_matched += match.size
  249. if not first_matched:
  250. continue
  251. # 'Substantially similar' is defined to be:
  252. # - no more than two differences
  253. # - at least one match besides the topmost directory
  254. total_differences = abs(total_matched -
  255. len(to_test[0])) + abs(total_matched -
  256. len(basis[0]))
  257. # Note: total_differences != 0 is mainly intended to allow more succinct
  258. # tests (otherwise tests with just a basename would always trip the
  259. # total_matched < 2 check).
  260. if total_differences != 0 and (total_differences > 2 or total_matched < 2):
  261. continue
  262. include.is_primary_header = True
  263. return
  264. def SerializeIncludes(includes):
  265. """Turns includes back into the corresponding C++ source text.
  266. Args:
  267. includes: a list of Include objects.
  268. Returns:
  269. A list of strings representing C++ source text.
  270. """
  271. source = []
  272. special_headers = [
  273. # Must be included before ws2tcpip.h.
  274. # Doesn't need to be included before <windows.h> with
  275. # WIN32_LEAN_AND_MEAN but why chance it?
  276. '<winsock2.h>',
  277. # Must be before lots of things, e.g. shellapi.h, winbase.h,
  278. # versionhelpers.h, memoryapi.h, hidclass.h, ncrypt.h., ...
  279. '<windows.h>',
  280. # Must be before iphlpapi.h.
  281. '<ws2tcpip.h>',
  282. # Must be before propkey.h.
  283. '<shobjidl.h>',
  284. # Must be before atlapp.h.
  285. '<atlbase.h>',
  286. # Must be before intshcut.h.
  287. '<ole2.h>',
  288. # Must be before intshcut.h.
  289. '<unknwn.h>',
  290. # Must be before uiautomation.h.
  291. '<objbase.h>',
  292. # Must be before tpcshrd.h.
  293. '<tchar.h>',
  294. ]
  295. # Ensure that headers are sorted as follows:
  296. #
  297. # 1. The primary header, if any, appears first.
  298. # 2. All headers of the same type (e.g. C system, C++ system headers, et
  299. # cetera) are grouped contiguously.
  300. # 3. Any special sorting rules needed within each group for satisfying
  301. # platform header idiosyncrasies. In practice, this only applies to C
  302. # system headers.
  303. # 4. The remaining headers without special sorting rules are sorted
  304. # lexicographically.
  305. #
  306. # The for loop below that outputs the actual source text depends on #2 above
  307. # to insert newlines between different groups of headers.
  308. def SortKey(include):
  309. def SpecialSortKey(include):
  310. lower_name = include.decorated_name.lower()
  311. for i in range(len(special_headers)):
  312. if special_headers[i] == lower_name:
  313. return i
  314. return len(special_headers)
  315. return (not include.is_primary_header, include.header_type,
  316. SpecialSortKey(include), include.decorated_name)
  317. includes.sort(key=SortKey)
  318. # Assume there's always at least one include.
  319. previous_include = None
  320. for include in includes:
  321. if previous_include and include.ShouldInsertNewline(previous_include):
  322. source.append('')
  323. source.extend(include.ToSource())
  324. previous_include = include
  325. return source
  326. def AddHeaderToSource(filename, source, decorated_name, remove=False):
  327. """Adds or removes the specified header into/from the source text, if needed.
  328. Args:
  329. filename: The name of the source file.
  330. source: A string containing the contents of the source file.
  331. decorated_name: The decorated name of the header to add or remove.
  332. remove: If true, remove instead of adding.
  333. Returns:
  334. None if no changes are needed or the modified source text otherwise.
  335. """
  336. lines = source.splitlines()
  337. begin, end = FindIncludes(lines)
  338. # No #includes in this file. Just give up.
  339. # TODO(dcheng): Be more clever and insert it after the file-level comment or
  340. # include guard as appropriate.
  341. if begin < 0:
  342. print(f'Skipping {filename}: unable to find includes!')
  343. return None
  344. includes = ParseIncludes(lines[begin:end])
  345. if not includes:
  346. print(f'Skipping {filename}: unable to parse includes!')
  347. return None
  348. if remove:
  349. for i in includes:
  350. if decorated_name == i.decorated_name:
  351. includes.remove(i)
  352. break
  353. else:
  354. print(f'Skipping {filename}: unable to find {decorated_name}')
  355. return None
  356. else:
  357. if decorated_name in [i.decorated_name for i in includes]:
  358. # Nothing to do.
  359. print(f'Skipping {filename}: no changes required!')
  360. return None
  361. else:
  362. includes.append(Include(decorated_name, 'include', [], None))
  363. MarkPrimaryInclude(includes, filename)
  364. lines[begin:end] = SerializeIncludes(includes)
  365. lines.append('') # To avoid eating the newline at the end of the file.
  366. return '\n'.join(lines)
  367. def main():
  368. parser = argparse.ArgumentParser(
  369. description='Mass add (or remove) a new header into a bunch of files.')
  370. parser.add_argument(
  371. '--header',
  372. help='The decorated filename of the header to insert (e.g. "a" or <a>)',
  373. required=True)
  374. parser.add_argument('--remove',
  375. help='Remove the header file instead of adding it',
  376. action='store_true')
  377. parser.add_argument('files', nargs='+')
  378. args = parser.parse_args()
  379. if ClassifyHeader(args.header) == _HEADER_TYPE_INVALID:
  380. print('--header argument must be a decorated filename, e.g.')
  381. print(' --header "<utility>"')
  382. print('or')
  383. print(' --header \'"moo.h"\'')
  384. return 1
  385. operation = 'Removing' if args.remove else 'Inserting'
  386. print(f'{operation} #include {args.header}...')
  387. for filename in args.files:
  388. with open(filename, 'r') as f:
  389. new_source = AddHeaderToSource(os.path.normpath(filename), f.read(),
  390. args.header, args.remove)
  391. if not new_source:
  392. continue
  393. with open(filename, 'w', newline='\n') as f:
  394. f.write(new_source)
  395. if __name__ == '__main__':
  396. sys.exit(main())