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
87  # If there is a doxygen \see command, change the \see prefix into "See also:".
88  # FIXME: it would be better to turn this into a link to the target instead.
89  comment = re.sub(r'\\see', r'See also:', comment)
90
91  # Delete the doxygen command and the following whitespace.
92  comment = re.sub(r'\\[^\s]+\s+', r'', comment)
93  return comment
94
95def unify_arguments(args):
96  """Gets rid of anything the user doesn't care about in the argument list."""
97  args = re.sub(r'internal::', r'', args)
98  args = re.sub(r'const\s+(.*)&', r'\1 ', args)
99  args = re.sub(r'&', r' ', args)
100  args = re.sub(r'(^|\s)M\d?(\s)', r'\1Matcher<*>\2', args)
101  return args
102
103def add_matcher(result_type, name, args, comment, is_dyncast=False):
104  """Adds a matcher to one of our categories."""
105  if name == 'id':
106     # FIXME: Figure out whether we want to support the 'id' matcher.
107     return
108  matcher_id = '%s%d' % (name, ids[name])
109  ids[name] += 1
110  args = unify_arguments(args)
111  matcher_html = TD_TEMPLATE % {
112    'result': esc('Matcher<%s>' % result_type),
113    'name': name,
114    'args': esc(args),
115    'comment': esc(strip_doxygen(comment)),
116    'id': matcher_id,
117  }
118  if is_dyncast:
119    node_matchers[result_type + name] = matcher_html
120  # Use a heuristic to figure out whether a matcher is a narrowing or
121  # traversal matcher. By default, matchers that take other matchers as
122  # arguments (and are not node matchers) do traversal. We specifically
123  # exclude known narrowing matchers that also take other matchers as
124  # arguments.
125  elif ('Matcher<' not in args or
126        name in ['allOf', 'anyOf', 'anything', 'unless']):
127    narrowing_matchers[result_type + name + esc(args)] = matcher_html
128  else:
129    traversal_matchers[result_type + name + esc(args)] = matcher_html
130
131def act_on_decl(declaration, comment, allowed_types):
132  """Parse the matcher out of the given declaration and comment.
133
134     If 'allowed_types' is set, it contains a list of node types the matcher
135     can match on, as extracted from the static type asserts in the matcher
136     definition.
137  """
138  if declaration.strip():
139    # Node matchers are defined by writing:
140    #   VariadicDynCastAllOfMatcher<ResultType, ArgumentType> name;
141    m = re.match(r""".*Variadic(?:DynCast)?AllOfMatcher\s*<
142                       \s*([^\s,]+)\s*(?:,
143                       \s*([^\s>]+)\s*)?>
144                       \s*([^\s;]+)\s*;\s*$""", declaration, flags=re.X)
145    if m:
146      result, inner, name = m.groups()
147      if not inner:
148        inner = result
149      add_matcher(result, name, 'Matcher<%s>...' % inner,
150                  comment, is_dyncast=True)
151      return
152
153    # Parse the various matcher definition macros.
154    m = re.match(""".*AST_TYPE_MATCHER\(
155                       \s*([^\s,]+\s*),
156                       \s*([^\s,]+\s*)
157                     \)\s*;\s*$""", declaration, flags=re.X)
158    if m:
159      inner, name = m.groups()
160      add_matcher('Type', name, 'Matcher<%s>...' % inner,
161                  comment, is_dyncast=True)
162      # FIXME: re-enable once we have implemented casting on the TypeLoc
163      # hierarchy.
164      # add_matcher('TypeLoc', '%sLoc' % name, 'Matcher<%sLoc>...' % inner,
165      #             comment, is_dyncast=True)
166      return
167
168    m = re.match(""".*AST_TYPE(LOC)?_TRAVERSE_MATCHER\(
169                       \s*([^\s,]+\s*),
170                       \s*(?:[^\s,]+\s*),
171                       \s*AST_POLYMORPHIC_SUPPORTED_TYPES\(([^)]*)\)
172                     \)\s*;\s*$""", declaration, flags=re.X)
173    if m:
174      loc, name, results = m.groups()[0:3]
175      result_types = [r.strip() for r in results.split(',')]
176
177      comment_result_types = extract_result_types(comment)
178      if (comment_result_types and
179          sorted(result_types) != sorted(comment_result_types)):
180        raise Exception('Inconsistent documentation for: %s' % name)
181      for result_type in result_types:
182        add_matcher(result_type, name, 'Matcher<Type>', comment)
183        if loc:
184          add_matcher('%sLoc' % result_type, '%sLoc' % name, 'Matcher<TypeLoc>',
185                      comment)
186      return
187
188    m = re.match(r"""^\s*AST_POLYMORPHIC_MATCHER(_P)?(.?)(?:_OVERLOAD)?\(
189                          \s*([^\s,]+)\s*,
190                          \s*AST_POLYMORPHIC_SUPPORTED_TYPES\(([^)]*)\)
191                       (?:,\s*([^\s,]+)\s*
192                          ,\s*([^\s,]+)\s*)?
193                       (?:,\s*([^\s,]+)\s*
194                          ,\s*([^\s,]+)\s*)?
195                       (?:,\s*\d+\s*)?
196                      \)\s*{\s*$""", declaration, flags=re.X)
197
198    if m:
199      p, n, name, results = m.groups()[0:4]
200      args = m.groups()[4:]
201      result_types = [r.strip() for r in results.split(',')]
202      if allowed_types and allowed_types != result_types:
203        raise Exception('Inconsistent documentation for: %s' % name)
204      if n not in ['', '2']:
205        raise Exception('Cannot parse "%s"' % declaration)
206      args = ', '.join('%s %s' % (args[i], args[i+1])
207                       for i in range(0, len(args), 2) if args[i])
208      for result_type in result_types:
209        add_matcher(result_type, name, args, comment)
210      return
211
212    m = re.match(r"""^\s*AST_MATCHER_FUNCTION(_P)?(.?)(?:_OVERLOAD)?\(
213                       (?:\s*([^\s,]+)\s*,)?
214                          \s*([^\s,]+)\s*
215                       (?:,\s*([^\s,]+)\s*
216                          ,\s*([^\s,]+)\s*)?
217                       (?:,\s*([^\s,]+)\s*
218                          ,\s*([^\s,]+)\s*)?
219                       (?:,\s*\d+\s*)?
220                      \)\s*{\s*$""", declaration, flags=re.X)
221    if m:
222      p, n, result, name = m.groups()[0:4]
223      args = m.groups()[4:]
224      if n not in ['', '2']:
225        raise Exception('Cannot parse "%s"' % declaration)
226      args = ', '.join('%s %s' % (args[i], args[i+1])
227                       for i in range(0, len(args), 2) if args[i])
228      add_matcher(result, name, args, comment)
229      return
230
231    m = re.match(r"""^\s*AST_MATCHER(_P)?(.?)(?:_OVERLOAD)?\(
232                       (?:\s*([^\s,]+)\s*,)?
233                          \s*([^\s,]+)\s*
234                       (?:,\s*([^,]+)\s*
235                          ,\s*([^\s,]+)\s*)?
236                       (?:,\s*([^\s,]+)\s*
237                          ,\s*([^\s,]+)\s*)?
238                       (?:,\s*\d+\s*)?
239                      \)\s*{\s*$""", declaration, flags=re.X)
240    if m:
241      p, n, result, name = m.groups()[0:4]
242      args = m.groups()[4:]
243      if not result:
244        if not allowed_types:
245          raise Exception('Did not find allowed result types for: %s' % name)
246        result_types = allowed_types
247      else:
248        result_types = [result]
249      if n not in ['', '2']:
250        raise Exception('Cannot parse "%s"' % declaration)
251      args = ', '.join('%s %s' % (args[i], args[i+1])
252                       for i in range(0, len(args), 2) if args[i])
253      for result_type in result_types:
254        add_matcher(result_type, name, args, comment)
255      return
256
257    # Parse ArgumentAdapting matchers.
258    m = re.match(
259        r"""^.*ArgumentAdaptingMatcherFunc<.*>\s*(?:LLVM_ATTRIBUTE_UNUSED\s*)
260              ([a-zA-Z]*)\s*=\s*{};$""",
261        declaration, flags=re.X)
262    if m:
263      name = m.groups()[0]
264      add_matcher('*', name, 'Matcher<*>', comment)
265      return
266
267    # Parse Variadic functions.
268    m = re.match(
269        r"""^.*internal::VariadicFunction\s*<\s*([^,]+),\s*([^,]+),\s*[^>]+>\s*
270              ([a-zA-Z]*)\s*=\s*{.*};$""",
271        declaration, flags=re.X)
272    if m:
273      result, arg, name = m.groups()[:3]
274      add_matcher(result, name, '%s, ..., %s' % (arg, arg), comment)
275      return
276
277    # Parse Variadic operator matchers.
278    m = re.match(
279        r"""^.*VariadicOperatorMatcherFunc\s*<\s*([^,]+),\s*([^\s>]+)\s*>\s*
280              ([a-zA-Z]*)\s*=\s*{.*};$""",
281        declaration, flags=re.X)
282    if m:
283      min_args, max_args, name = m.groups()[:3]
284      if max_args == '1':
285        add_matcher('*', name, 'Matcher<*>', comment)
286        return
287      elif max_args == 'UINT_MAX':
288        add_matcher('*', name, 'Matcher<*>, ..., Matcher<*>', comment)
289        return
290
291
292    # Parse free standing matcher functions, like:
293    #   Matcher<ResultType> Name(Matcher<ArgumentType> InnerMatcher) {
294    m = re.match(r"""^\s*(.*)\s+
295                     ([^\s\(]+)\s*\(
296                     (.*)
297                     \)\s*{""", declaration, re.X)
298    if m:
299      result, name, args = m.groups()
300      args = ', '.join(p.strip() for p in args.split(','))
301      m = re.match(r'.*\s+internal::(Bindable)?Matcher<([^>]+)>$', result)
302      if m:
303        result_types = [m.group(2)]
304      else:
305        result_types = extract_result_types(comment)
306      if not result_types:
307        if not comment:
308          # Only overloads don't have their own doxygen comments; ignore those.
309          print 'Ignoring "%s"' % name
310        else:
311          print 'Cannot determine result type for "%s"' % name
312      else:
313        for result_type in result_types:
314          add_matcher(result_type, name, args, comment)
315    else:
316      print '*** Unparsable: "' + declaration + '" ***'
317
318def sort_table(matcher_type, matcher_map):
319  """Returns the sorted html table for the given row map."""
320  table = ''
321  for key in sorted(matcher_map.keys()):
322    table += matcher_map[key] + '\n'
323  return ('<!-- START_%(type)s_MATCHERS -->\n' +
324          '%(table)s' +
325          '<!--END_%(type)s_MATCHERS -->') % {
326    'type': matcher_type,
327    'table': table,
328  }
329
330# Parse the ast matchers.
331# We alternate between two modes:
332# body = True: We parse the definition of a matcher. We need
333#   to parse the full definition before adding a matcher, as the
334#   definition might contain static asserts that specify the result
335#   type.
336# body = False: We parse the comments and declaration of the matcher.
337comment = ''
338declaration = ''
339allowed_types = []
340body = False
341for line in open(MATCHERS_FILE).read().splitlines():
342  if body:
343    if line.strip() and line[0] == '}':
344      if declaration:
345        act_on_decl(declaration, comment, allowed_types)
346        comment = ''
347        declaration = ''
348        allowed_types = []
349      body = False
350    else:
351      m = re.search(r'is_base_of<([^,]+), NodeType>', line)
352      if m and m.group(1):
353        allowed_types += [m.group(1)]
354    continue
355  if line.strip() and line.lstrip()[0] == '/':
356    comment += re.sub(r'/+\s?', '', line) + '\n'
357  else:
358    declaration += ' ' + line
359    if ((not line.strip()) or
360        line.rstrip()[-1] == ';' or
361        (line.rstrip()[-1] == '{' and line.rstrip()[-3:] != '= {')):
362      if line.strip() and line.rstrip()[-1] == '{':
363        body = True
364      else:
365        act_on_decl(declaration, comment, allowed_types)
366        comment = ''
367        declaration = ''
368        allowed_types = []
369
370node_matcher_table = sort_table('DECL', node_matchers)
371narrowing_matcher_table = sort_table('NARROWING', narrowing_matchers)
372traversal_matcher_table = sort_table('TRAVERSAL', traversal_matchers)
373
374reference = open('../LibASTMatchersReference.html').read()
375reference = re.sub(r'<!-- START_DECL_MATCHERS.*END_DECL_MATCHERS -->',
376                   node_matcher_table, reference, flags=re.S)
377reference = re.sub(r'<!-- START_NARROWING_MATCHERS.*END_NARROWING_MATCHERS -->',
378                   narrowing_matcher_table, reference, flags=re.S)
379reference = re.sub(r'<!-- START_TRAVERSAL_MATCHERS.*END_TRAVERSAL_MATCHERS -->',
380                   traversal_matcher_table, reference, flags=re.S)
381
382with open('../LibASTMatchersReference.html', 'wb') as output:
383  output.write(reference)
384
385