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
6import collections
7import re
8import urllib2
9
10MATCHERS_FILE = '../../include/clang/ASTMatchers/ASTMatchers.h'
11
12# Each matcher is documented in one row of the form:
13#   result | name | argA
14# The subsequent row contains the documentation and is hidden by default,
15# becoming visible via javascript when the user clicks the matcher name.
16TD_TEMPLATE="""
17<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>
18<tr><td colspan="4" class="doc" id="%(id)s"><pre>%(comment)s</pre></td></tr>
19"""
20
21# We categorize the matchers into these three categories in the reference:
22node_matchers = {}
23narrowing_matchers = {}
24traversal_matchers = {}
25
26# We output multiple rows per matcher if the matcher can be used on multiple
27# node types. Thus, we need a new id per row to control the documentation
28# pop-up. ids[name] keeps track of those ids.
29ids = collections.defaultdict(int)
30
31# Cache for doxygen urls we have already verified.
32doxygen_probes = {}
33
34def esc(text):
35  """Escape any html in the given text."""
36  text = re.sub(r'&', '&amp;', text)
37  text = re.sub(r'<', '&lt;', text)
38  text = re.sub(r'>', '&gt;', text)
39  def link_if_exists(m):
40    name = m.group(1)
41    url = 'http://clang.llvm.org/doxygen/classclang_1_1%s.html' % name
42    if url not in doxygen_probes:
43      try:
44        print 'Probing %s...' % url
45        urllib2.urlopen(url)
46        doxygen_probes[url] = True
47      except:
48        doxygen_probes[url] = False
49    if doxygen_probes[url]:
50      return r'Matcher&lt<a href="%s">%s</a>&gt;' % (url, name)
51    else:
52      return m.group(0)
53  text = re.sub(
54    r'Matcher&lt;([^\*&]+)&gt;', link_if_exists, text)
55  return text
56
57def extract_result_types(comment):
58  """Extracts a list of result types from the given comment.
59
60     We allow annotations in the comment of the matcher to specify what
61     nodes a matcher can match on. Those comments have the form:
62       Usable as: Any Matcher | (Matcher<T1>[, Matcher<t2>[, ...]])
63
64     Returns ['*'] in case of 'Any Matcher', or ['T1', 'T2', ...].
65     Returns the empty list if no 'Usable as' specification could be
66     parsed.
67  """
68  result_types = []
69  m = re.search(r'Usable as: Any Matcher[\s\n]*$', comment, re.S)
70  if m:
71    return ['*']
72  while True:
73    m = re.match(r'^(.*)Matcher<([^>]+)>\s*,?[\s\n]*$', comment, re.S)
74    if not m:
75      if re.search(r'Usable as:\s*$', comment):
76        return result_types
77      else:
78        return None
79    result_types += [m.group(2)]
80    comment = m.group(1)
81
82def strip_doxygen(comment):
83  """Returns the given comment without \-escaped words."""
84  # If there is only a doxygen keyword in the line, delete the whole line.
85  comment = re.sub(r'^\\[^\s]+\n', r'', comment, flags=re.M)
86  # Delete the doxygen command and the following whitespace.
87  comment = re.sub(r'\\[^\s]+\s+', r'', comment)
88  return comment
89
90def unify_arguments(args):
91  """Gets rid of anything the user doesn't care about in the argument list."""
92  args = re.sub(r'internal::', r'', args)
93  args = re.sub(r'const\s+', r'', args)
94  args = re.sub(r'&', r' ', args)
95  args = re.sub(r'(^|\s)M\d?(\s)', r'\1Matcher<*>\2', args)
96  return args
97
98def add_matcher(result_type, name, args, comment, is_dyncast=False):
99  """Adds a matcher to one of our categories."""
100  if name == 'id':
101     # FIXME: Figure out whether we want to support the 'id' matcher.
102     return
103  matcher_id = '%s%d' % (name, ids[name])
104  ids[name] += 1
105  args = unify_arguments(args)
106  matcher_html = TD_TEMPLATE % {
107    'result': esc('Matcher<%s>' % result_type),
108    'name': name,
109    'args': esc(args),
110    'comment': esc(strip_doxygen(comment)),
111    'id': matcher_id,
112  }
113  if is_dyncast:
114    node_matchers[result_type + name] = matcher_html
115  # Use a heuristic to figure out whether a matcher is a narrowing or
116  # traversal matcher. By default, matchers that take other matchers as
117  # arguments (and are not node matchers) do traversal. We specifically
118  # exclude known narrowing matchers that also take other matchers as
119  # arguments.
120  elif ('Matcher<' not in args or
121        name in ['allOf', 'anyOf', 'anything', 'unless']):
122    narrowing_matchers[result_type + name + esc(args)] = matcher_html
123  else:
124    traversal_matchers[result_type + name + esc(args)] = matcher_html
125
126def act_on_decl(declaration, comment, allowed_types):
127  """Parse the matcher out of the given declaration and comment.
128
129     If 'allowed_types' is set, it contains a list of node types the matcher
130     can match on, as extracted from the static type asserts in the matcher
131     definition.
132  """
133  if declaration.strip():
134    # Node matchers are defined by writing:
135    #   VariadicDynCastAllOfMatcher<ResultType, ArgumentType> name;
136    m = re.match(r""".*Variadic(?:DynCast)?AllOfMatcher\s*<
137                       \s*([^\s,]+)\s*(?:,
138                       \s*([^\s>]+)\s*)?>
139                       \s*([^\s;]+)\s*;\s*$""", declaration, flags=re.X)
140    if m:
141      result, inner, name = m.groups()
142      if not inner:
143        inner = result
144      add_matcher(result, name, 'Matcher<%s>...' % inner,
145                  comment, is_dyncast=True)
146      return
147
148    # Parse the various matcher definition macros.
149    m = re.match(""".*AST_TYPE_MATCHER\(
150                       \s*([^\s,]+\s*),
151                       \s*([^\s,]+\s*)
152                     \)\s*;\s*$""", declaration, flags=re.X)
153    if m:
154      inner, name = m.groups()
155      add_matcher('Type', name, 'Matcher<%s>...' % inner,
156                  comment, is_dyncast=True)
157      # FIXME: re-enable once we have implemented casting on the TypeLoc
158      # hierarchy.
159      # add_matcher('TypeLoc', '%sLoc' % name, 'Matcher<%sLoc>...' % inner,
160      #             comment, is_dyncast=True)
161      return
162
163    m = re.match(""".*AST_TYPE(LOC)?_TRAVERSE_MATCHER\(
164                       \s*([^\s,]+\s*),
165                       \s*(?:[^\s,]+\s*),
166                       \s*AST_POLYMORPHIC_SUPPORTED_TYPES_([^(]*)\(([^)]*)\)
167                     \)\s*;\s*$""", declaration, flags=re.X)
168    if m:
169      loc, name, n_results, results = m.groups()[0:4]
170      result_types = [r.strip() for r in results.split(',')]
171
172      comment_result_types = extract_result_types(comment)
173      if (comment_result_types and
174          sorted(result_types) != sorted(comment_result_types)):
175        raise Exception('Inconsistent documentation for: %s' % name)
176      for result_type in result_types:
177        add_matcher(result_type, name, 'Matcher<Type>', comment)
178        if loc:
179          add_matcher('%sLoc' % result_type, '%sLoc' % name, 'Matcher<TypeLoc>',
180                      comment)
181      return
182
183    m = re.match(r"""^\s*AST_POLYMORPHIC_MATCHER(_P)?(.?)(?:_OVERLOAD)?\(
184                          \s*([^\s,]+)\s*,
185                          \s*AST_POLYMORPHIC_SUPPORTED_TYPES_([^(]*)\(([^)]*)\)
186                       (?:,\s*([^\s,]+)\s*
187                          ,\s*([^\s,]+)\s*)?
188                       (?:,\s*([^\s,]+)\s*
189                          ,\s*([^\s,]+)\s*)?
190                       (?:,\s*\d+\s*)?
191                      \)\s*{\s*$""", declaration, flags=re.X)
192
193    if m:
194      p, n, name, n_results, results = m.groups()[0:5]
195      args = m.groups()[5:]
196      result_types = [r.strip() for r in results.split(',')]
197      if allowed_types and allowed_types != result_types:
198        raise Exception('Inconsistent documentation for: %s' % name)
199      if n not in ['', '2']:
200        raise Exception('Cannot parse "%s"' % declaration)
201      args = ', '.join('%s %s' % (args[i], args[i+1])
202                       for i in range(0, len(args), 2) if args[i])
203      for result_type in result_types:
204        add_matcher(result_type, name, args, comment)
205      return
206
207    m = re.match(r"""^\s*AST_MATCHER_FUNCTION(_P)?(.?)(?:_OVERLOAD)?\(
208                       (?:\s*([^\s,]+)\s*,)?
209                          \s*([^\s,]+)\s*
210                       (?:,\s*([^\s,]+)\s*
211                          ,\s*([^\s,]+)\s*)?
212                       (?:,\s*([^\s,]+)\s*
213                          ,\s*([^\s,]+)\s*)?
214                       (?:,\s*\d+\s*)?
215                      \)\s*{\s*$""", declaration, flags=re.X)
216    if m:
217      p, n, result, name = m.groups()[0:4]
218      args = m.groups()[4:]
219      if n not in ['', '2']:
220        raise Exception('Cannot parse "%s"' % declaration)
221      args = ', '.join('%s %s' % (args[i], args[i+1])
222                       for i in range(0, len(args), 2) if args[i])
223      add_matcher(result, name, args, comment)
224      return
225
226    m = re.match(r"""^\s*AST_MATCHER(_P)?(.?)(?:_OVERLOAD)?\(
227                       (?:\s*([^\s,]+)\s*,)?
228                          \s*([^\s,]+)\s*
229                       (?:,\s*([^\s,]+)\s*
230                          ,\s*([^\s,]+)\s*)?
231                       (?:,\s*([^\s,]+)\s*
232                          ,\s*([^\s,]+)\s*)?
233                       (?:,\s*\d+\s*)?
234                      \)\s*{\s*$""", declaration, flags=re.X)
235    if m:
236      p, n, result, name = m.groups()[0:4]
237      args = m.groups()[4:]
238      if not result:
239        if not allowed_types:
240          raise Exception('Did not find allowed result types for: %s' % name)
241        result_types = allowed_types
242      else:
243        result_types = [result]
244      if n not in ['', '2']:
245        raise Exception('Cannot parse "%s"' % declaration)
246      args = ', '.join('%s %s' % (args[i], args[i+1])
247                       for i in range(0, len(args), 2) if args[i])
248      for result_type in result_types:
249        add_matcher(result_type, name, args, comment)
250      return
251
252    # Parse ArgumentAdapting matchers.
253    m = re.match(
254        r"""^.*ArgumentAdaptingMatcherFunc<.*>\s*(?:LLVM_ATTRIBUTE_UNUSED\s*)
255              ([a-zA-Z]*)\s*=\s*{};$""",
256        declaration, flags=re.X)
257    if m:
258      name = m.groups()[0]
259      add_matcher('*', name, 'Matcher<*>', comment)
260      return
261
262    # Parse Variadic operator matchers.
263    m = re.match(
264        r"""^.*VariadicOperatorMatcherFunc\s*<\s*([^,]+),\s*([^\s>]+)\s*>\s*
265              ([a-zA-Z]*)\s*=\s*{.*};$""",
266        declaration, flags=re.X)
267    if m:
268      min_args, max_args, name = m.groups()[:3]
269      if max_args == '1':
270        add_matcher('*', name, 'Matcher<*>', comment)
271        return
272      elif max_args == 'UINT_MAX':
273        add_matcher('*', name, 'Matcher<*>, ..., Matcher<*>', comment)
274        return
275
276
277    # Parse free standing matcher functions, like:
278    #   Matcher<ResultType> Name(Matcher<ArgumentType> InnerMatcher) {
279    m = re.match(r"""^\s*(.*)\s+
280                     ([^\s\(]+)\s*\(
281                     (.*)
282                     \)\s*{""", declaration, re.X)
283    if m:
284      result, name, args = m.groups()
285      args = ', '.join(p.strip() for p in args.split(','))
286      m = re.match(r'.*\s+internal::(Bindable)?Matcher<([^>]+)>$', result)
287      if m:
288        result_types = [m.group(2)]
289      else:
290        result_types = extract_result_types(comment)
291      if not result_types:
292        if not comment:
293          # Only overloads don't have their own doxygen comments; ignore those.
294          print 'Ignoring "%s"' % name
295        else:
296          print 'Cannot determine result type for "%s"' % name
297      else:
298        for result_type in result_types:
299          add_matcher(result_type, name, args, comment)
300    else:
301      print '*** Unparsable: "' + declaration + '" ***'
302
303def sort_table(matcher_type, matcher_map):
304  """Returns the sorted html table for the given row map."""
305  table = ''
306  for key in sorted(matcher_map.keys()):
307    table += matcher_map[key] + '\n'
308  return ('<!-- START_%(type)s_MATCHERS -->\n' +
309          '%(table)s' +
310          '<!--END_%(type)s_MATCHERS -->') % {
311    'type': matcher_type,
312    'table': table,
313  }
314
315# Parse the ast matchers.
316# We alternate between two modes:
317# body = True: We parse the definition of a matcher. We need
318#   to parse the full definition before adding a matcher, as the
319#   definition might contain static asserts that specify the result
320#   type.
321# body = False: We parse the comments and declaration of the matcher.
322comment = ''
323declaration = ''
324allowed_types = []
325body = False
326for line in open(MATCHERS_FILE).read().splitlines():
327  if body:
328    if line.strip() and line[0] == '}':
329      if declaration:
330        act_on_decl(declaration, comment, allowed_types)
331        comment = ''
332        declaration = ''
333        allowed_types = []
334      body = False
335    else:
336      m = re.search(r'is_base_of<([^,]+), NodeType>', line)
337      if m and m.group(1):
338        allowed_types += [m.group(1)]
339    continue
340  if line.strip() and line.lstrip()[0] == '/':
341    comment += re.sub(r'/+\s?', '', line) + '\n'
342  else:
343    declaration += ' ' + line
344    if ((not line.strip()) or
345        line.rstrip()[-1] == ';' or
346        (line.rstrip()[-1] == '{' and line.rstrip()[-3:] != '= {')):
347      if line.strip() and line.rstrip()[-1] == '{':
348        body = True
349      else:
350        act_on_decl(declaration, comment, allowed_types)
351        comment = ''
352        declaration = ''
353        allowed_types = []
354
355node_matcher_table = sort_table('DECL', node_matchers)
356narrowing_matcher_table = sort_table('NARROWING', narrowing_matchers)
357traversal_matcher_table = sort_table('TRAVERSAL', traversal_matchers)
358
359reference = open('../LibASTMatchersReference.html').read()
360reference = re.sub(r'<!-- START_DECL_MATCHERS.*END_DECL_MATCHERS -->',
361                   '%s', reference, flags=re.S) % node_matcher_table
362reference = re.sub(r'<!-- START_NARROWING_MATCHERS.*END_NARROWING_MATCHERS -->',
363                   '%s', reference, flags=re.S) % narrowing_matcher_table
364reference = re.sub(r'<!-- START_TRAVERSAL_MATCHERS.*END_TRAVERSAL_MATCHERS -->',
365                   '%s', reference, flags=re.S) % traversal_matcher_table
366
367with open('../LibASTMatchersReference.html', 'w') as output:
368  output.write(reference)
369
370