Generate FileCheck checks for all module items (#3957)

Instead of only generating checks for functions, generate checks for all named top-level module items, such as types, tags, tables, and memories. Because module items can be in different orders in the input and the output but FileCheck checks must follow the order of the output, we need to be slightly clever about when we emit the checks. Consider these types in the input file:

```
  (type $A (...))
  (type $B (...))
```

If their order is reversed in the output file, then the checks for $B need to be emitted before the checks for $A, so the resulting module will look like this:

```
  ;; CHECK: (type $B (...))
  ;; CHECK: (type $A (...))
  (type $A (...))
  (type $B (...))
```

Rather than this, which looks nicer but would be incorrect:

```
  ;; CHECK: (type $A (...))
  (type $A (...))
  ;; CHECK: (type $B (...))
  (type $B (...))
```

1 files changed, 78 insertions, 31 deletions

diff --git a/scripts/update_lit_checks.py b/scripts/update_lit_checks.py
index d8446288a..bd3fbe208 100755
--- a/scripts/update_lit_checks.py
+++ b/scripts/update_lit_checks.py
@@ -31,9 +31,15 @@ import tempfile
 script_name = os.path.basename(__file__)
 NOTICE = (f';; NOTE: Assertions have been generated by {script_name} and ' +
           'should not be edited.')
+
+
 RUN_LINE_RE = re.compile(r'^\s*;;\s*RUN:\s*(.*)$')
 CHECK_PREFIX_RE = re.compile(r'.*--check-prefix[= ](\S+).*')
-FUNC_RE = re.compile(r'(^\s*)\(func \$(\S*).*$', re.MULTILINE)
+
+items = ['type', 'import', 'global', 'memory', 'data', 'table', 'elem', 'tag',
+         'export', 'start', 'func']
+ITEM_RE = re.compile(r'(^\s*)\((' + '|'.join(items) + r')\s+(\$?[^\s()]*).*$',
+                     re.MULTILINE)
 
 
 def warn(msg):
@@ -83,21 +89,30 @@ def run_command(args, test, tmp, command):
     return subprocess.check_output(command, shell=True, env=env).decode('utf-8')
 
 
-def find_funcs(module):
-    """Return a dict mapping each function name to lines in the function"""
-    result = {}
-    for match in FUNC_RE.finditer(module):
-        name = match.group(2)
-        depth = 1
-        for end in range(match.end(), len(module)):
-            if depth == 0:
-                break
-            elif module[end] == '(':
-                depth += 1
-            elif module[end] == ')':
-                depth -= 1
-        result[name] = module[match.start():end].split('\n')
-    return result
+def find_end(module, start):
+    # Find the index one past the closing parenthesis corresponding to the first
+    # open parenthesis at `start`.
+    assert module[start] == '('
+    depth = 1
+    for end in range(start + 1, len(module)):
+        if depth == 0:
+            break
+        elif module[end] == '(':
+            depth += 1
+        elif module[end] == ')':
+            depth -= 1
+    return end
+
+
+def split_output(module):
+    # Return a list of (name, [lines]) for module items
+    out = []
+    for match in ITEM_RE.finditer(module):
+        kind, name = match[2], match[3]
+        end = find_end(module, match.end(1))
+        lines = module[match.start():end].split('\n')
+        out.append(((kind, name), lines))
+    return out
 
 
 def main():
@@ -122,6 +137,7 @@ def main():
     tmp = tempfile.mktemp()
 
     for test, lines in itertests(args):
+        # List of (prefix, command)
         run_list = []
         for line in find_run_lines(test, lines):
             commands = [cmd.strip() for cmd in line.rsplit('|', 1)]
@@ -140,32 +156,63 @@ def main():
 
             run_list.append((check_prefix, commands[0]))
 
-        # Map check prefixes and function names to the corresponding output
-        func_dict = {}
+        # Map check prefixes to lists of ((kind, name), [lines])
+        output_modules = {}
         for prefix, command, in run_list:
             output = run_command(args, test, tmp, command)
             if prefix:
-                func_dict[prefix] = find_funcs(output)
+                output_modules[prefix] = split_output(output)
 
-        check_line_re = re.compile(r'^\s*;;\s*(' + '|'.join(func_dict.keys()) +
-                                   r')(?:-NEXT|-LABEL|-NOT)?: .*$')
+        any_prefix = '|'.join(output_modules.keys())
+        check_line_re = re.compile(r'^\s*;;\s*(' + any_prefix +
+                                   r')(?:-NEXT|-LABEL|-NOT)?:.*$')
         output_lines = [NOTICE]
+
+        def emit_checks(indent, prefix, lines):
+            output_lines.append(f'{indent};; {prefix}:     {lines[0]}')
+            for line in lines[1:]:
+                output_lines.append(f'{indent};; {prefix}-NEXT:{line}')
+
+        # Skip the notice if it is already in the output
         if lines and script_name in lines[0]:
             lines = lines[1:]
+
+        named_items = []
+        for line in lines:
+            match = ITEM_RE.match(line)
+            if match:
+                kind, name = match[2], match[3]
+                named_items.append((kind, name))
+
         for line in lines:
+            # Skip pre-existing check lines; we will regenerate them.
             if check_line_re.match(line):
                 continue
-            func_match = FUNC_RE.match(line)
-            if func_match:
-                indent, name = func_match.groups()
-                for prefix, funcs in func_dict.items():
-                    body = funcs.get(name, [])
-                    if not body:
-                        continue
-                    output_lines.append(f'{indent};; {prefix}:     {body[0]}')
-                    for l in body[1:]:
-                        output_lines.append(f'{indent};; {prefix}-NEXT:{l}')
+            match = ITEM_RE.match(line)
+            if match:
+                indent, kind, name = match.groups()
+                for prefix, items in output_modules.items():
+                    # If the output for this prefix contains an item with this
+                    # name, emit all the items up to and including the matching
+                    # item
+                    has_item = False
+                    for kind_name, lines in items:
+                        if name and (kind, name) == kind_name:
+                            has_item = True
+                            break
+                    if has_item:
+                        while True:
+                            kind_name, lines = items.pop(0)
+                            if kind_name in named_items:
+                                emit_checks(indent, prefix, lines)
+                            if name and (kind, name) == kind_name:
+                                break
             output_lines.append(line)
+        # Output any remaining checks for each prefix
+        for prefix, items in output_modules.items():
+            for kind_name, lines in items:
+                if kind_name in named_items:
+                    emit_checks('', prefix, lines)
 
         if args.dry_run:
             print('\n'.join(output_lines))