clang/docs/tools/dump_ast_matchers.py

   1 #!/usr/bin/env python
   2 # A tool to parse ASTMatchers.h and update the documentation in
   3 # ../LibASTMatchersReference.html automatically. Run from the
   4 # directory in which this file is located to update the docs.
   5
   6 import collections
   7 import re
   8 try:
   9     from urllib.request import urlopen
  10 except ImportError:
  11     from urllib2 import urlopen
  12
  13 MATCHERS_FILE = '../../include/clang/ASTMatchers/ASTMatchers.h'
  14
  15 # Each matcher is documented in one row of the form:
  16 #   result | name | argA
  17 # The subsequent row contains the documentation and is hidden by default,
  18 # becoming visible via javascript when the user clicks the matcher name.
  19 TD_TEMPLATE="""
  20 <tr><td>%(result)s</td><td class="name" onclick="toggle('%(id)s')"><a name="%(id)sAnchor">%(name)s</a></td><td>%(args)s</td></tr>
  21 <tr><td colspan="4" class="doc" id="%(id)s"><pre>%(comment)s</pre></td></tr>
  22 """
  23
  24 # We categorize the matchers into these three categories in the reference:
  25 node_matchers = {}
  26 narrowing_matchers = {}
  27 traversal_matchers = {}
  28
  29 # We output multiple rows per matcher if the matcher can be used on multiple
  30 # node types. Thus, we need a new id per row to control the documentation
  31 # pop-up. ids[name] keeps track of those ids.
  32 ids = collections.defaultdict(int)
  33
  34 # Cache for doxygen urls we have already verified.
  35 doxygen_probes = {}
  36
  37 def esc(text):
  38   """Escape any html in the given text."""
  39   text = re.sub(r'&', '&amp;', text)
  40   text = re.sub(r'<', '&lt;', text)
  41   text = re.sub(r'>', '&gt;', text)
  42   def link_if_exists(m):
  43     name = m.group(1)
  44     url = 'https://clang.llvm.org/doxygen/classclang_1_1%s.html' % name
  45     if url not in doxygen_probes:
  46       try:
  47         print('Probing %s...' % url)
  48         urlopen(url)
  49         doxygen_probes[url] = True
  50       except:
  51         doxygen_probes[url] = False
  52     if doxygen_probes[url]:
  53       return r'Matcher&lt;<a href="%s">%s</a>&gt;' % (url, name)
  54     else:
  55       return m.group(0)
  56   text = re.sub(
  57     r'Matcher&lt;([^\*&]+)&gt;', link_if_exists, text)
  58   return text
  59
  60 def extract_result_types(comment):
  61   """Extracts a list of result types from the given comment.
  62
  63      We allow annotations in the comment of the matcher to specify what
  64      nodes a matcher can match on. Those comments have the form:
  65        Usable as: Any Matcher | (Matcher<T1>[, Matcher<t2>[, ...]])
  66
  67      Returns ['*'] in case of 'Any Matcher', or ['T1', 'T2', ...].
  68      Returns the empty list if no 'Usable as' specification could be
  69      parsed.
  70   """
  71   result_types = []
  72   m = re.search(r'Usable as: Any Matcher[\s\n]*$', comment, re.S)
  73   if m:
  74     return ['*']
  75   while True:
  76     m = re.match(r'^(.*)Matcher<([^>]+)>\s*,?[\s\n]*$', comment, re.S)
  77     if not m:
  78       if re.search(r'Usable as:\s*$', comment):
  79         return result_types
  80       else:
  81         return None
  82     result_types += [m.group(2)]
  83     comment = m.group(1)
  84
  85 def strip_doxygen(comment):
  86   """Returns the given comment without \-escaped words."""
  87   # If there is only a doxygen keyword in the line, delete the whole line.
  88   comment = re.sub(r'^\\[^\s]+\n', r'', comment, flags=re.M)
  89
  90   # If there is a doxygen \see command, change the \see prefix into "See also:".
  91   # FIXME: it would be better to turn this into a link to the target instead.
  92   comment = re.sub(r'\\see', r'See also:', comment)
  93
  94   # Delete the doxygen command and the following whitespace.
  95   comment = re.sub(r'\\[^\s]+\s+', r'', comment)
  96   return comment
  97
  98 def unify_arguments(args):
  99   """Gets rid of anything the user doesn't care about in the argument list."""
 100   args = re.sub(r'internal::', r'', args)
 101   args = re.sub(r'extern const\s+(.*)&', r'\1 ', args)
 102   args = re.sub(r'&', r' ', args)
 103   args = re.sub(r'(^|\s)M\d?(\s)', r'\1Matcher<*>\2', args)
 104   args = re.sub(r'BindableMatcher', r'Matcher', args)
 105   args = re.sub(r'const Matcher', r'Matcher', args)
 106   return args
 107
 108 def unify_type(result_type):
 109   """Gets rid of anything the user doesn't care about in the type name."""
 110   result_type = re.sub(r'^internal::(Bindable)?Matcher<([a-zA-Z_][a-zA-Z0-9_]*)>$', r'\2', result_type)
 111   return result_type
 112
 113 def add_matcher(result_type, name, args, comment, is_dyncast=False):
 114   """Adds a matcher to one of our categories."""
 115   if name == 'id':
 116      # FIXME: Figure out whether we want to support the 'id' matcher.
 117      return
 118   matcher_id = '%s%d' % (name, ids[name])
 119   ids[name] += 1
 120   args = unify_arguments(args)
 121   result_type = unify_type(result_type)
 122
 123   docs_result_type = esc('Matcher<%s>' % result_type);
 124
 125   if name == 'mapAnyOf':
 126     args = "nodeMatcherFunction..."
 127     docs_result_type = "<em>unspecified</em>"
 128
 129   matcher_html = TD_TEMPLATE % {
 130     'result': docs_result_type,
 131     'name': name,
 132     'args': esc(args),
 133     'comment': esc(strip_doxygen(comment)),
 134     'id': matcher_id,
 135   }
 136   if is_dyncast:
 137     dict = node_matchers
 138     lookup = result_type + name
 139   # Use a heuristic to figure out whether a matcher is a narrowing or
 140   # traversal matcher. By default, matchers that take other matchers as
 141   # arguments (and are not node matchers) do traversal. We specifically
 142   # exclude known narrowing matchers that also take other matchers as
 143   # arguments.
 144   elif ('Matcher<' not in args or
 145         name in ['allOf', 'anyOf', 'anything', 'unless', 'mapAnyOf']):
 146     dict = narrowing_matchers
 147     lookup = result_type + name + esc(args)
 148   else:
 149     dict = traversal_matchers
 150     lookup = result_type + name + esc(args)
 151
 152   if dict.get(lookup) is None or len(dict.get(lookup)) < len(matcher_html):
 153     dict[lookup] = matcher_html
 154
 155 def act_on_decl(declaration, comment, allowed_types):
 156   """Parse the matcher out of the given declaration and comment.
 157
 158      If 'allowed_types' is set, it contains a list of node types the matcher
 159      can match on, as extracted from the static type asserts in the matcher
 160      definition.
 161   """
 162   if declaration.strip():
 163
 164     if re.match(r'^\s?(#|namespace|using)', declaration): return
 165
 166     # Node matchers are defined by writing:
 167     #   VariadicDynCastAllOfMatcher<ResultType, ArgumentType> name;
 168     m = re.match(r""".*Variadic(?:DynCast)?AllOfMatcher\s*<
 169                        \s*([^\s,]+)\s*(?:,
 170                        \s*([^\s>]+)\s*)?>
 171                        \s*([^\s;]+)\s*;\s*$""", declaration, flags=re.X)
 172     if m:
 173       result, inner, name = m.groups()
 174       if not inner:
 175         inner = result
 176       add_matcher(result, name, 'Matcher<%s>...' % inner,
 177                   comment, is_dyncast=True)
 178       return
 179
 180     # Special case of type matchers:
 181     #   AstTypeMatcher<ArgumentType> name
 182     m = re.match(r""".*AstTypeMatcher\s*<
 183                        \s*([^\s>]+)\s*>
 184                        \s*([^\s;]+)\s*;\s*$""", declaration, flags=re.X)
 185     if m:
 186       inner, name = m.groups()
 187       add_matcher('Type', name, 'Matcher<%s>...' % inner,
 188                   comment, is_dyncast=True)
 189       # FIXME: re-enable once we have implemented casting on the TypeLoc
 190       # hierarchy.
 191       # add_matcher('TypeLoc', '%sLoc' % name, 'Matcher<%sLoc>...' % inner,
 192       #             comment, is_dyncast=True)
 193       return
 194
 195     # Parse the various matcher definition macros.
 196     m = re.match(""".*AST_TYPE(LOC)?_TRAVERSE_MATCHER(?:_DECL)?\(
 197                        \s*([^\s,]+\s*),
 198                        \s*(?:[^\s,]+\s*),
 199                        \s*AST_POLYMORPHIC_SUPPORTED_TYPES\(([^)]*)\)
 200                      \)\s*;\s*$""", declaration, flags=re.X)
 201     if m:
 202       loc, name, results = m.groups()[0:3]
 203       result_types = [r.strip() for r in results.split(',')]
 204
 205       comment_result_types = extract_result_types(comment)
 206       if (comment_result_types and
 207           sorted(result_types) != sorted(comment_result_types)):
 208         raise Exception('Inconsistent documentation for: %s' % name)
 209       for result_type in result_types:
 210         add_matcher(result_type, name, 'Matcher<Type>', comment)
 211         # if loc:
 212         #   add_matcher('%sLoc' % result_type, '%sLoc' % name, 'Matcher<TypeLoc>',
 213         #               comment)
 214       return
 215
 216     m = re.match(r"""^\s*AST_POLYMORPHIC_MATCHER(_P)?(.?)(?:_OVERLOAD)?\(
 217                           \s*([^\s,]+)\s*,
 218                           \s*AST_POLYMORPHIC_SUPPORTED_TYPES\(([^)]*)\)
 219                        (?:,\s*([^\s,]+)\s*
 220                           ,\s*([^\s,]+)\s*)?
 221                        (?:,\s*([^\s,]+)\s*
 222                           ,\s*([^\s,]+)\s*)?
 223                        (?:,\s*\d+\s*)?
 224                       \)\s*{\s*$""", declaration, flags=re.X)
 225
 226     if m:
 227       p, n, name, results = m.groups()[0:4]
 228       args = m.groups()[4:]
 229       result_types = [r.strip() for r in results.split(',')]
 230       if allowed_types and allowed_types != result_types:
 231         raise Exception('Inconsistent documentation for: %s' % name)
 232       if n not in ['', '2']:
 233         raise Exception('Cannot parse "%s"' % declaration)
 234       args = ', '.join('%s %s' % (args[i], args[i+1])
 235                        for i in range(0, len(args), 2) if args[i])
 236       for result_type in result_types:
 237         add_matcher(result_type, name, args, comment)
 238       return
 239
 240     m = re.match(r"""^\s*AST_POLYMORPHIC_MATCHER_REGEX(?:_OVERLOAD)?\(
 241                           \s*([^\s,]+)\s*,
 242                           \s*AST_POLYMORPHIC_SUPPORTED_TYPES\(([^)]*)\),
 243                           \s*([^\s,]+)\s*
 244                        (?:,\s*\d+\s*)?
 245                       \)\s*{\s*$""", declaration, flags=re.X)
 246
 247     if m:
 248       name, results, arg_name = m.groups()[0:3]
 249       result_types = [r.strip() for r in results.split(',')]
 250       if allowed_types and allowed_types != result_types:
 251         raise Exception('Inconsistent documentation for: %s' % name)
 252       arg = "StringRef %s, Regex::RegexFlags Flags = NoFlags" % arg_name
 253       comment += """
 254 If the matcher is used in clang-query, RegexFlags parameter
 255 should be passed as a quoted string. e.g: "NoFlags".
 256 Flags can be combined with '|' example \"IgnoreCase | BasicRegex\"
 257 """
 258       for result_type in result_types:
 259         add_matcher(result_type, name, arg, comment)
 260       return
 261
 262     m = re.match(r"""^\s*AST_MATCHER_FUNCTION(_P)?(.?)(?:_OVERLOAD)?\(
 263                        (?:\s*([^\s,]+)\s*,)?
 264                           \s*([^\s,]+)\s*
 265                        (?:,\s*([^\s,]+)\s*
 266                           ,\s*([^\s,]+)\s*)?
 267                        (?:,\s*([^\s,]+)\s*
 268                           ,\s*([^\s,]+)\s*)?
 269                        (?:,\s*\d+\s*)?
 270                       \)\s*{\s*$""", declaration, flags=re.X)
 271     if m:
 272       p, n, result, name = m.groups()[0:4]
 273       args = m.groups()[4:]
 274       if n not in ['', '2']:
 275         raise Exception('Cannot parse "%s"' % declaration)
 276       args = ', '.join('%s %s' % (args[i], args[i+1])
 277                        for i in range(0, len(args), 2) if args[i])
 278       add_matcher(result, name, args, comment)
 279       return
 280
 281     m = re.match(r"""^\s*AST_MATCHER(_P)?(.?)(?:_OVERLOAD)?\(
 282                        (?:\s*([^\s,]+)\s*,)?
 283                           \s*([^\s,]+)\s*
 284                        (?:,\s*([^,]+)\s*
 285                           ,\s*([^\s,]+)\s*)?
 286                        (?:,\s*([^\s,]+)\s*
 287                           ,\s*([^\s,]+)\s*)?
 288                        (?:,\s*\d+\s*)?
 289                       \)\s*{""", declaration, flags=re.X)
 290     if m:
 291       p, n, result, name = m.groups()[0:4]
 292       args = m.groups()[4:]
 293       if not result:
 294         if not allowed_types:
 295           raise Exception('Did not find allowed result types for: %s' % name)
 296         result_types = allowed_types
 297       else:
 298         result_types = [result]
 299       if n not in ['', '2']:
 300         raise Exception('Cannot parse "%s"' % declaration)
 301       args = ', '.join('%s %s' % (args[i], args[i+1])
 302                        for i in range(0, len(args), 2) if args[i])
 303       for result_type in result_types:
 304         add_matcher(result_type, name, args, comment)
 305       return
 306
 307     m = re.match(r"""^\s*AST_MATCHER_REGEX(?:_OVERLOAD)?\(
 308                        \s*([^\s,]+)\s*,
 309                        \s*([^\s,]+)\s*,
 310                        \s*([^\s,]+)\s*
 311                        (?:,\s*\d+\s*)?
 312                       \)\s*{""", declaration, flags=re.X)
 313     if m:
 314       result, name, arg_name = m.groups()[0:3]
 315       if not result:
 316         if not allowed_types:
 317           raise Exception('Did not find allowed result types for: %s' % name)
 318         result_types = allowed_types
 319       else:
 320         result_types = [result]
 321       arg = "StringRef %s, Regex::RegexFlags Flags = NoFlags" % arg_name
 322       comment += """
 323 If the matcher is used in clang-query, RegexFlags parameter
 324 should be passed as a quoted string. e.g: "NoFlags".
 325 Flags can be combined with '|' example \"IgnoreCase | BasicRegex\"
 326 """
 327
 328       for result_type in result_types:
 329         add_matcher(result_type, name, arg, comment)
 330       return
 331
 332     # Parse ArgumentAdapting matchers.
 333     m = re.match(
 334         r"""^.*ArgumentAdaptingMatcherFunc<.*>\s*
 335               ([a-zA-Z]*);$""",
 336         declaration, flags=re.X)
 337     if m:
 338       name = m.groups()[0]
 339       add_matcher('*', name, 'Matcher<*>', comment)
 340       return
 341
 342     # Parse Variadic functions.
 343     m = re.match(
 344         r"""^.*internal::VariadicFunction\s*<\s*([^,]+),\s*([^,]+),\s*[^>]+>\s*
 345               ([a-zA-Z]*);$""",
 346         declaration, flags=re.X)
 347     if m:
 348       result, arg, name = m.groups()[:3]
 349       add_matcher(result, name, '%s, ..., %s' % (arg, arg), comment)
 350       return
 351
 352     m = re.match(
 353         r"""^.*internal::VariadicFunction\s*<\s*
 354               internal::PolymorphicMatcher<[\S\s]+
 355               AST_POLYMORPHIC_SUPPORTED_TYPES\(([^)]*)\),\s*(.*);$""",
 356         declaration, flags=re.X)
 357
 358     if m:
 359       results, trailing = m.groups()
 360       trailing, name = trailing.rsplit(">", 1)
 361       name = name.strip()
 362       trailing, _ = trailing.rsplit(",", 1)
 363       _, arg = trailing.rsplit(",", 1)
 364       arg = arg.strip()
 365
 366       result_types = [r.strip() for r in results.split(',')]
 367       for result_type in result_types:
 368         add_matcher(result_type, name, '%s, ..., %s' % (arg, arg), comment)
 369       return
 370
 371
 372     # Parse Variadic operator matchers.
 373     m = re.match(
 374         r"""^.*VariadicOperatorMatcherFunc\s*<\s*([^,]+),\s*([^\s]+)\s*>\s*
 375               ([a-zA-Z]*);$""",
 376         declaration, flags=re.X)
 377     if m:
 378       min_args, max_args, name = m.groups()[:3]
 379       if max_args == '1':
 380         add_matcher('*', name, 'Matcher<*>', comment)
 381         return
 382       elif max_args == 'std::numeric_limits<unsigned>::max()':
 383         add_matcher('*', name, 'Matcher<*>, ..., Matcher<*>', comment)
 384         return
 385
 386     m = re.match(
 387         r"""^.*MapAnyOfMatcher<.*>\s*
 388               ([a-zA-Z]*);$""",
 389         declaration, flags=re.X)
 390     if m:
 391       name = m.groups()[0]
 392       add_matcher('*', name, 'Matcher<*>...Matcher<*>', comment)
 393       return
 394
 395     # Parse free standing matcher functions, like:
 396     #   Matcher<ResultType> Name(Matcher<ArgumentType> InnerMatcher) {
 397     m = re.match(r"""^\s*(?:template\s+<\s*(?:class|typename)\s+(.+)\s*>\s+)?
 398                      (.*)\s+
 399                      ([^\s\(]+)\s*\(
 400                      (.*)
 401                      \)\s*{""", declaration, re.X)
 402     if m:
 403       template_name, result, name, args = m.groups()
 404       if template_name:
 405         matcherTemplateArgs = re.findall(r'Matcher<\s*(%s)\s*>' % template_name, args)
 406         templateArgs = re.findall(r'(?:^|[\s,<])(%s)(?:$|[\s,>])' % template_name, args)
 407         if len(matcherTemplateArgs) < len(templateArgs):
 408           # The template name is used naked, so don't replace with `*`` later on
 409           template_name = None
 410         else :
 411           args = re.sub(r'(^|[\s,<])%s($|[\s,>])' % template_name, r'\1*\2', args)
 412       args = ', '.join(p.strip() for p in args.split(','))
 413       m = re.match(r'(?:^|.*\s+)internal::(?:Bindable)?Matcher<([^>]+)>$', result)
 414       if m:
 415         result_types = [m.group(1)]
 416         if template_name and len(result_types) is 1 and result_types[0] == template_name:
 417           result_types = ['*']
 418       else:
 419         result_types = extract_result_types(comment)
 420       if not result_types:
 421         if not comment:
 422           # Only overloads don't have their own doxygen comments; ignore those.
 423           print('Ignoring "%s"' % name)
 424         else:
 425           print('Cannot determine result type for "%s"' % name)
 426       else:
 427         for result_type in result_types:
 428           add_matcher(result_type, name, args, comment)
 429     else:
 430       print('*** Unparsable: "' + declaration + '" ***')
 431
 432 def sort_table(matcher_type, matcher_map):
 433   """Returns the sorted html table for the given row map."""
 434   table = ''
 435   for key in sorted(matcher_map.keys()):
 436     table += matcher_map[key] + '\n'
 437   return ('<!-- START_%(type)s_MATCHERS -->\n' +
 438           '%(table)s' +
 439           '<!--END_%(type)s_MATCHERS -->') % {
 440     'type': matcher_type,
 441     'table': table,
 442   }
 443
 444 # Parse the ast matchers.
 445 # We alternate between two modes:
 446 # body = True: We parse the definition of a matcher. We need
 447 #   to parse the full definition before adding a matcher, as the
 448 #   definition might contain static asserts that specify the result
 449 #   type.
 450 # body = False: We parse the comments and declaration of the matcher.
 451 comment = ''
 452 declaration = ''
 453 allowed_types = []
 454 body = False
 455 for line in open(MATCHERS_FILE).read().splitlines():
 456   if body:
 457     if line.strip() and line[0] == '}':
 458       if declaration:
 459         act_on_decl(declaration, comment, allowed_types)
 460         comment = ''
 461         declaration = ''
 462         allowed_types = []
 463       body = False
 464     else:
 465       m = re.search(r'is_base_of<([^,]+), NodeType>', line)
 466       if m and m.group(1):
 467         allowed_types += [m.group(1)]
 468     continue
 469   if line.strip() and line.lstrip()[0] == '/':
 470     comment += re.sub(r'^/+\s?', '', line) + '\n'
 471   else:
 472     declaration += ' ' + line
 473     if ((not line.strip()) or
 474         line.rstrip()[-1] == ';' or
 475         (line.rstrip()[-1] == '{' and line.rstrip()[-3:] != '= {')):
 476       if line.strip() and line.rstrip()[-1] == '{':
 477         body = True
 478       else:
 479         act_on_decl(declaration, comment, allowed_types)
 480         comment = ''
 481         declaration = ''
 482         allowed_types = []
 483
 484 node_matcher_table = sort_table('DECL', node_matchers)
 485 narrowing_matcher_table = sort_table('NARROWING', narrowing_matchers)
 486 traversal_matcher_table = sort_table('TRAVERSAL', traversal_matchers)
 487
 488 reference = open('../LibASTMatchersReference.html').read()
 489 reference = re.sub(r'<!-- START_DECL_MATCHERS.*END_DECL_MATCHERS -->',
 490                    node_matcher_table, reference, flags=re.S)
 491 reference = re.sub(r'<!-- START_NARROWING_MATCHERS.*END_NARROWING_MATCHERS -->',
 492                    narrowing_matcher_table, reference, flags=re.S)
 493 reference = re.sub(r'<!-- START_TRAVERSAL_MATCHERS.*END_TRAVERSAL_MATCHERS -->',
 494                    traversal_matcher_table, reference, flags=re.S)
 495
 496 with open('../LibASTMatchersReference.html', 'wb') as output:
 497   output.write(reference)
 498