[utils][filecheck-lint] Add filecheck-lint, a linter for FileCheck directives.

[bchetioui]

Summary

FileCheck is a versatile tool for testing compiler output regardless of syntax.
FileCheck achieves this versatility by processing only input lines in which it
detects a valid CHECK directive, and ignoring everything else.

This comes at a price: if a directive is not typed properly, it is not
processed by FileCheck, and the test code it precedes is effectively disabled.
This results in the illusion that the code is tested, while the test may have
actually never run.

This scenario is not hypothetical, see the fixes introduced in, e.g.
https://github.com/tensorflow/tensorflow/commit/48cacf049f3d6ed3f289ccc48ec50491b6d8d9a8,
https://reviews.llvm.org/D139698, https://reviews.llvm.org/D139636,
https://github.com/iree-org/iree/pull/11693.

The findings corrected in the above changes originate in filecheck-lint.
In a given test file, filecheck-lint uses the edit distance between anything
that looks like a FileCheck directive and the set of locally valid directives
to detect likely misspelled directives.

The tool is not yet feature complete---e.g. it does not parse custom comment
prefixes to exclude them from reporting---but it already yields useful results,
as demonstrated above.

[sammccall]

This seems to be spread over more files/directories than is typical for small tools like this.
Would you consider:

• folding main into filecheck_lint.py, under if __name__=='__main__' so it still works as a library
• dropping the filecheck_lint directory
• moving the contents of README.md into comments/docstring of the script itself

I think the test is OK sitting loose under utils next to the main file (but only if something actually runs it)

llvm/utils/filecheck_lint/README.md

3

replace with a normal space?

16

I don't see any reason users should care about customizing this - we should set a sensible default, and the set of directives doesn't vary wildly between tests.

Fine if you want to have it for testing or some external use, but I wouldn't document it - it's distracting.

[sammccall]

Sorry, hit enter too soon on previous round.

Generally this looks really useful, and finds real bugs!

Most of the comments below are of the form:

• the implementation seems overly complex and general, I think being short/simple/direct is more useful for maintenance than being "good python code", as this is not production code and will be read/edited by people who don't know much python
• for my taste there's too much boilerplate comments repeating the names of things, and not enough explaining how this piece of code is contributing to solving the probelm

llvm/utils/filecheck_lint/filecheck_lint.py

18

this isn't used anywhere - if there isn't a concrete need I'd suggest just making it a constant, then you can drop argparse and just iterate over argv?

(If you want to use a different config out of tree that's not unreasonable, but it's not clear to me why that would be the case)

llvm/utils/filecheck_lint/filecheck_lint/filecheck_lint.py

8

there are a lot of fine-grained comments here about the implementation (e.g. what a class represents) but it's hard to get an overall picture of what this library does and how.

I think an example would go a long way here, somethng like:

Consider a broken test foo.cpp:

// RUN: clang -cc1 -ast-dump %s | FileCheck %s --check-prefix=NEW
// RUN: clang -cc1 -ast-dump %s -std=c++98 | FileCheck %s --check-prefix=OLD
auto x = 42;
// NEWW: auto is a c++11 extension
// ODL-NOT: auto is a c++11 extension

First we detect FileCheck directive prefixes by looking for --check-prefix flags.
Here we get {CHECK, NEW, OLD}, so our directive names are
{CHECK, NEW, OLD, CHECK-NOT, NEW-NOT, ...}.

Then we look for lines that look like directives: these are of the form FOO: at the beginning of a line or a comment.
If any of these are a "near-miss" for a directive name, then we suspect this is a typo.

39

If there's nothing non-obvious to say about an arg (the type hints already say they're strings), don't say anything? Similarly the "Returns:" just echoes the first line.

(I'm not a python person, maybe there's some structural reason this comment needs to be this way, but other files seem mostly not to have them)

62

nit: FileRange? (both avoiding the abbreviation & the impression that it describes a point only)

83

"emit" doesn't belong here I think.

Maybe more precisely: "Stores information about one typo and possibly its fix" (is the fix optional?)

I'm not sure the second paragraph or the attributes adds anything nonobvious (Findings isn't a concept that makes sense here)

113

nit: US english is much more common in LLVM, so probably "misspelled"

124

We should also support the directive being at the start of a line-comment, even if the line is otherwise non-empty.

rg "\s*[^ ]\s*// CHECK" clang/test shows many examples e.g:

../clang/test/Refactor/LocalRename/NoSymbolSelectedError.cpp
4:class Baz { // CHECK: [[@LINE]]:1: error: there is no symbol at the given location

131

this seems overly complicated: why not just always accept all comment markers in any type of file?

Eyeballing "(?:^|#|//|;)\s*([A-Z0-9-_]+)\s*:", I don't see false positives.

140

it's not really clear what's to be done here: improved how? how can someone tell when it's time to delete this TODO?

143

I'd suggest restricting to uppercase as this is a ~universal convention and will avoid big classes of false positives, allowing to simplify elsewhere

148

up to you, but I'm not sure getting convenient access to the line number is worth doing everything linewise and looping.
You could make FilePos's constructor compute the line/column, then that class would do something useful!

(Not that it matters, but I suspect it also performs better in practice to run the regex over a big buffer, and actually needing the line number is the very rare error case)

187

This seems like it could be much simpler: just take the whole file, match against a regex, and always split the captured arg on , since a prefix will never have one.

def parse_custom_prefixes(code): 
  for m in re.finditer(r'--check-prefix(?:es)?[ =](\S+)', code):
    for prefix in m.group(1).split(','):
      yield prefix

188

this comment doesn't really say anything beyond what the function signature already says.

Maybe an example? (in the code: .... the prefixes are ...)

259

why have two functions here instead of one? can't we just have the caller pass in the file content?

268

this just echoes the function name

276

nit: make _suffixes = {"", "-NOT", "-DAG"} etc instead?

292

up to you, many of these functions could be slightly terser with yield rather than create/append/return an array

312

this is a redundant second check for _ignore, you already added it to all_directives above

llvm/utils/filecheck_lint/tests/filecheck_lint_test.py

1

this test isn't being run by anything.
you can leave it out (most utils aren't tested, this is already a tool for improving tests, recursion needs to stop at some point!)

But thinking about it more, I think it's harmless enough and probably helps when developing it.
There are a few other tools that use unittest.TestCase, AFAIK nothing runs those either.

[bchetioui]

Address review comments.

[bchetioui]

Thanks for the thorough review, Sam, I think this is much better!

I have addressed your comments in my latest revision. Let me know if something is still amiss.

llvm/utils/filecheck_lint/README.md

16

I removed the option and removed this line from the documentation.

llvm/utils/filecheck_lint/filecheck_lint/filecheck_lint.py

8

Thanks, that's indeed much better.
I added a slight variation of your comment there, hope that's OK.

39

The structure was meant to satisfy an overly eager linter.
That is not a good reason, and I agree it is not particularly useful. Removed.

83

Done. (The fix is not optional.)

124

Oops, in fact, this is a case of the documentation being out of date with regards to the code.
In fact, the very case that you are outlining is tested in test_find_potential_directives_comment_prefix and works properly.
Corrected the documentation to reflect that, thanks!

131

A comment marker is not strictly necessary for something to be parsed as a directive by FileCheck---meaning I'd like to keep the option for directive prefix to be optional. But if it is always optional, then I am afraid we may see a host of false positives, since anything preceding a colon would always be matched for every type of file.

I personally prefer it like this, but if you'd rather, I could change "directive_prefix" to a boolean "match_comment_marker". When enabled, I would match any comment marker. WDYT?

Apart from the comment markers, I think the regex you suggest will not yield false positives, but that it may allow more "false negatives" to pass through. E.g., in https://github.com/tensorflow/tensorflow/commit/48cacf049f3d6ed3f289ccc48ec50491b6d8d9a8, one of typos contained lowercase letters, and another contained a space instead of a dash. These would not be caught by the regex you suggest, so I would like to keep the regex as is. WDYT?

140

I removed this unclear TODO. One improvement I was thinking about (but that does not actually concern the regex directly) is that something like "// some inline comment CHCK:" gives us a match with "some inline comment CHCK:" right now. We should probably also match "inline comment CHCK:", "comment CHCK:", and "CHCK:", since FileCheck may match either of those.

While more correct, I haven't yet validated that this is fine wrt false positives, so I have chosen to omit this from the initial version of the code.

143

ACK, but I don't think restricting to uppercase will yield better results, as explained above in the "directive_prefix" comment.

By the way, I have run the linter over e.g. all the .ll test files in the LLVM repo, and I do not recall matching false positives related to case. (Either way, the number of false positives has actually been surprisingly low.)

148

I think you are right re. performance, and this is cleaner. Made the changes are you suggest, thanks!

187

Indeed, that's much better. I modified the regex slightly to match also other types of valid flag-settings that occur.
(That was actually one of the TODOs above, should have just done it :-)).

292

Thanks, I made find_potential_directives and find_directive_typos generators, as you suggest.

312

The purpose of this check is to not report on detected typos when the likely intended directive is one we would ignore anyway.
This is particularly useful if someone uses very short custom CHECK prefixes (e.g. given a check prefix "DO", "ToDo" would be close enough to "DO" that it could be a typo, but is actually closer to "TODO". Reporting it would likely be a false positive).

I suggest we leave it as is, WDYT?

llvm/utils/filecheck_lint/tests/filecheck_lint_test.py

1

If you think this is harmless enough, I would like to keep some tests next to the tool. (If not, I will keep them on my end for personal use, but that seems worse.)
They don't need to be run automatically, but I do find them helpful for development.

[sammccall]

Thanks! This all looks pretty good to me apart from the complexity around comment markers, detecting which comment markers to use for which language etc.
I'd really like if you could either:

• decide we don't care about comment markers, and drop them entirely
• decide we do care, and hardcode (any comment marker|start-of-line), dropping the optional-ness and language detection
• explain why it's important that this feature is sometimes on/sometimes off, we need to know exactly the per-language comment marker etc

llvm/utils/filecheck_lint/filecheck_lint/filecheck_lint.py

131

A comment marker is not strictly necessary for something to be parsed as a directive by FileCheck

Sure, but you're using heuristics, and have to make some decisions. If all filters are loose (don't require caps, allow spaces, don't require it to be at the start of a line/comment) then you're going to have lots of false positives.

In the code the comment marker is not optional: you always pass one at the callsite. So the code handling directive_prefix is None is dead & I think we should delete it. Alternatively, if you want to allow directives to appear anywhere, delete the case that handles directive_prefix. Unless it's really important, we don't need to define an API that lets you turn this on or off.

Sure, that's why we would have ^ in the alternation: it will match at the beginning of the line (I guess you have to set re.MULTILINE in python for this)

Apart from the comment markers, I think the regex you suggest will not yield false positives, but that it may allow more "false negatives" to pass through

Fair enough. Allowing spaces *and* lowercase letters seems very permissive. Matching too many things may not be a problem per se, though it could lead to missing the right match (e.g. blah CHEC: something won't match "CHEC" because it matches "blah CHEC"). But the details are up to you.

I would like to keep the regex as is.

Sure, the details of the regex don't bother me much as simplifying the code a bit - regardless of which characters you choose to match,

312

Ah, got it - sure.

[bchetioui]

Remove comment prefix derivation and hardcode prefixes instead.

[bchetioui]

Thinking about this more, I think that you are right and the added complexity of not hardcoding the comment prefixes may not be worth it.
I decided to go with "decide we do care, and hardcode (any comment marker|start-of-line), dropping the optional-ness and language detection".

Thanks a lot again for your review, Sam!

llvm/utils/filecheck_lint/filecheck_lint/filecheck_lint.py

131

Small note: the code path is not actually dead, as files with extensions that are not mapped to an inline comment prefix will have their directive_prefix set to None.

However, I take your point, and I am no longer sure if this is a net positive to add. In the worst case, if people start using the linter with new file formats that use different comment prefixes than the ones we match, they can always update the regex.

I deleted the code and hardcoded the inline comment prefixes in the regex.

(e.g. blah CHEC: something won't match "CHEC" because it matches "blah CHEC")

This can surely be improved, and I plan to do so in a later change.

[sammccall]

LG, thanks!

llvm/utils/filecheck_lint/filecheck_lint/filecheck_lint.py

131

the code path is not actually dead, as files with extensions that are not mapped to an inline comment prefix will have their directive_prefix set to None

The previous snapshot still had comment_prefix = comment_prefix or '//' - maybe an oversight and I was too eager to assume it was intentional!

[bchetioui]

llvm/utils/filecheck_lint/filecheck_lint/filecheck_lint.py

131

Oops, you're right, that was an oversight (I removed it now, and didn't even register it). Thanks for catching it, my bad!

llvm/utils/filecheck_lint/README.md

+# filecheck_lint
+
+##!About
+
+`filecheck_lint` is a tool for detecting invalid FileCheck directives that are
+likely to be due to typos in a given test file. `filecheck_lint` achieves that
+by computing the edit distance between the directives used and the set of
+directives that are valid within the test file. A invalid directive that is
+close to being a valid directive within a parameterizable edit distance is
+reported on the standard output as a likely typo, and a fix is suggested.
+
+## Usage
+
+```bash
+filecheck_lint path/to/test/file/1 ... path/to/test/file/n
+# With a custom edit distance reporting threshold (default: 3)
+filecheck_lint --threshold 4 path/to/test/file/1 ... path/to/test/file/n
+```
 No newline at end of file

llvm/utils/filecheck_lint/filecheck_lint.py

+# ===----------------------------------------------------------------------===##
+#
+# Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+# See https://llvm.org/LICENSE.txt for license information.
+# SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+#
+# ===----------------------------------------------------------------------===##
+"""Main file for the FileCheck linter."""
+import argparse
+import logging
+import pathlib
+
+import filecheck_lint.filecheck_lint as fcl
+
+
+def main() -> None:
+  parser = argparse.ArgumentParser(description=__doc__)
+  parser.add_argument(
+      '--distance-threshold',
+      default=3,
+      type=int,
+      help=(
+          'The largest string distance allowed for matching a custom directive'
+      ),
+  )
+  parser.add_argument(
+      'files', nargs='+', type=str, help='The files to check for typos'
+  )
+  args = parser.parse_args()
+
+  for filepath in args.files:
+    logging.info('Checking %s', filepath)
+    comment_prefix = fcl.comment_prefix_from_filename(filepath)
+    for diagnostic in fcl.find_directive_typos(
+        pathlib.Path(filepath),
+        threshold=args.distance_threshold,
+        comment_prefix=comment_prefix,
+    ):
+      print(diagnostic)
+
+
+if __name__ == '__main__':
+  main()

llvm/utils/filecheck_lint/filecheck_lint/filecheck_lint.py

+# ===----------------------------------------------------------------------===##
+#
+# Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+# See https://llvm.org/LICENSE.txt for license information.
+# SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+#
+# ===----------------------------------------------------------------------===##
+"""A linter that detects potential typos in FileCheck directive names."""
+
+import itertools
+import pathlib
+import re
+from typing import Callable, List, Optional, Sequence, Set, Tuple
+
+
+_prefixes = {'CHECK'}
+_suffixes = {'DAG', 'COUNT', 'EMPTY', 'LABEL', 'NEXT', 'NOT', 'SAME'}
+# 'NOTE' and 'TODO' are not directives, but are likely to be false positives
+# if encountered and to generate noise as a result. We filter them out also to
+# avoid this.
+_lit_directives = {
+    'RUN',
+    'REQUIRES',
+    'UNSUPPORTED',
+    'XFAIL',
+    'DEFINE',
+    'REDEFINE',
+}
+# 'COM' and 'RUN' are default comment prefixes for FileCheck.
+_comment_prefixes = {'COM', 'RUN'}
+_ignore = _lit_directives.union(_comment_prefixes).union({'NOTE', 'TODO'})
+
+
+def levenshtein(s1: str, s2: str) -> int:
+  """Computes the edit distance between two strings.
+
+  Additions, deletions, and substitutions all count as a single operation.
+
+  Args:
+    s1: a string
+    s2: another string
+
+  Returns:
+    The edit distance between the two input strings.
+  """
+  if not s1: return len(s2)
+  if not s2: return len(s1)
+
+  distances = range(len(s2) + 1)
+  for i in range(len(s1)):
+    new_distances = [i + 1]
+    for j in range(len(s2)):
+      cost = min(distances[j] + int(s1[i] != s2[j]),
+                 distances[j + 1] + 1,
+                 new_distances[-1] + 1)
+      new_distances.append(cost)
+    distances = new_distances
+  return distances[-1]
+
+
+class FilePos:
+  """Stores the coordinates of a span on a single line within a file.
+
+  Attributes:
+    line:         the line number
+    start_column: the (inclusive) column where the span starts
+    end_column:   the (inclusive) column where the span ends
+  """
+  line: int
+  start_column: int
+  end_column: int
+
+  def __init__(self, line: int, start_column: int, end_column: int):
+    self.line = line
+    self.start_column = start_column
+    self.end_column = end_column
+
+  def __str__(self) -> str:
+    return f'{self.line}:{self.start_column}-{self.end_column}'
+
+
+class Diagnostic:
+  """Stores information about typos and emit error diagnostics.
+
+  A diagnostic stores the information relevant for a given potential typo, and
+  provides facilities for emitting either Findings or textual error messages.
+
+  Attributes:
+    filepath: the path to the file in which the typo was found
+    filepos:  the position at which the typo was found in the file
+    typo:     the typo
+    fix:      a suggested fix
+  """
+
+  filepath: pathlib.Path
+  filepos: FilePos
+  typo: str
+  fix: str
+
+  def __init__(
+      self, filepath: pathlib.Path, filepos: FilePos, typo: str, fix: str
+  ):
+    self.filepath = filepath
+    self.filepos = filepos
+    self.typo = typo
+    self.fix = fix
+
+  def __str__(self) -> str:
+    return f'{self.filepath}:' + str(self.filepos) + f': {self.summary()}'
+
+  def summary(self) -> str:
+    return (
+        f'Found potentially misspelt directive "{self.typo}". Did you mean '
+        f'"{self.fix}"?'
+    )
+
+
+def find_potential_directives(
+    lines: Sequence[str], directive_prefix: Optional[str] = None
+) -> List[Tuple[FilePos, str]]:
+  """Filters a list for strings that could be potential FileCheck directives.
+
+  Finds all the strings that could be potential directives in a sequence of
+  strings. This assumes that lines containing the directive always start with
+  either whitespace, or the specified comment prefix. What constitutes a
+  potential directive is loosely defined---we err on the side of capturing
+  more strings than is necessary, rather than missing any.
+
+  Args:
+    lines: a sequence of strings
+    directive_prefix: an optional prefix associated with directives, e.g. '//'
+      or ';'. If not provided, the function does not attempt to match any prefix
+      before directives.
+
+  Returns:
+    A list of tuples (p, d) where p is the position of the potential directive
+    within the file and d is the potential directive.
+  """
+  matches = []
+  # TODO(bchetioui): regexes can be further improved to capture typoed
+  # directives more holistically. In practice, they seem to perform well as is.
+  if directive_prefix is None:
+    directive_pattern = re.compile(r'([\d\w\_][\s\d\w\-_]*):')
+  else:
+    directive_pattern = re.compile(
+        r'{}[^\d\w\-_]*([\d\w\-_][\s\d\w\-_]*):'.format(directive_prefix)
+    )
+  for lineno, line in enumerate(lines, start=1):
+    match = re.search(directive_pattern, line)
+    if match is None:
+      continue
+    potential_directive, span = match.group(1), match.span(1)
+    matches.append((FilePos(lineno, span[0] + 1, span[1]), potential_directive))
+  return matches
+
+
+def comment_prefix_from_filename(filename: str) -> Optional[str]:
+  """Returns the inline comment prefix corresponding to a file type.
+
+  Args:
+    filename: the name of a file including its extension
+
+  Returns:
+    The inline comment prefix corresponding to the file's extension, e.g.
+    '//' for '.cc' and '.mlir', or ';' for '.ll'.
+  """
+  language_to_comment_prefix = {
+      'cc': '//',
+      'cpp': '//',
+      'll': ';',
+      'mlir': '//',
+      'py': '#',
+  }
+
+  comment_prefix = None
+  if '.' in filename:
+    comment_prefix = language_to_comment_prefix.get(filename.split('.')[-1])
+
+  return comment_prefix
+
+
+# TODO(bchetioui): make parse_additional_prefixes cross line boundaries, or
+# have it take only one line as a parameter.
+# TODO(bchetioui): convert this code to use regexes as well.
+# TODO(bchetioui): factorize this to parse comment prefixes to ignore as well.
+# TODO(bchetioui): check that the argument is actually part of a CHECK command.
+def parse_additional_prefixes(lines: Sequence[str]) -> Set[str]:
+  """Parses custom prefixes defined in the list of strings provided.
+
+  Args:
+    lines: A list of strings in which to look for prefixes.
+
+  Returns:
+    A set of prefixes found in the input lines.
+  """
+
+  def parse_check_prefixes(
+      s: str, option_prefix: str, extract_prefixes: Callable[[str], List[str]]
+  ) -> List[str]:
+    prefix_groups = s.split(option_prefix)[1:]
+    join = lambda ll: [e for l in ll for e in l]  # pylint: disable=g-complex-comprehension
+    return join(
+        extract_prefixes(prefix_group) for prefix_group in prefix_groups
+    )
+
+  def extract_one_prefix(g: str) -> List[str]:
+    return [g.strip().split(' ')[0].replace('"', '').replace("'", '').strip()]
+
+  def extract_many_prefixes(g: str) -> List[str]:
+    prefixes = g.strip().split(' ')[0].replace('"', '').replace("'", '').strip()
+    return [prefix.strip() for prefix in prefixes.split(',')]
+
+  additional_prefixes = []
+
+  for line in lines:
+    line = line.strip()
+    # If the line ends with a backslash for line continuation, remove it. This
+    # avoids potentially parsing a prefix incorrectly if there is no space
+    # between the prefix and a line continuation, e.g. like in
+    # '-check-prefix=CHECK-PREFIX\'.
+    if line.endswith('\\'): line = line[:-1]
+    additional_prefixes.extend(
+        parse_check_prefixes(line, '-check-prefix=', extract_one_prefix)
+    )
+    additional_prefixes.extend(
+        parse_check_prefixes(line, '-check-prefix ', extract_one_prefix)
+    )
+    additional_prefixes.extend(
+        parse_check_prefixes(line, '-check-prefixes=', extract_many_prefixes)
+    )
+    additional_prefixes.extend(
+        parse_check_prefixes(line, '-check-prefixes ', extract_many_prefixes)
+    )
+
+  return set(additional_prefixes)
+
+
+def find_directive_typos(
+    filepath: pathlib.Path,
+    comment_prefix: Optional[str] = None,
+    threshold: int = 3,
+) -> Sequence[Diagnostic]:
+  """Detects potential typos in FileCheck directives.
+
+  Args:
+    filepath: the path to the file to check for typos in directives
+    comment_prefix: the prefix associated with directives, e.g. '//' or ';'
+      depending on the file type (optional, will be set to '//' if not provided)
+    threshold: the (inclusive) maximum Levenshtein distance between a potential
+      directive and an actual directive, such that the potential directive is
+      classified as a typo
+
+  Returns:
+    A list of diagnostics, sorted according to the order of typos from the
+    top of the file.
+  """
+  with open(filepath, 'rt') as f:
+    lines = f.readlines()
+  return find_directive_typos_impl(lines, filepath, comment_prefix, threshold)
+
+
+def find_directive_typos_impl(
+    lines: Sequence[str],
+    filepath: pathlib.Path,
+    comment_prefix: Optional[str] = None,
+    threshold: int = 3,
+) -> Sequence[Diagnostic]:
+  """Underlying implementation for `find_directive_typos`."""
+  all_prefixes = _prefixes.union(parse_additional_prefixes(lines))
+  all_directives = (
+      [
+          f'{prefix}-{suffix}'
+          for prefix, suffix in itertools.product(all_prefixes, _suffixes)
+      ]
+      + list(_ignore)
+      + list(all_prefixes)
+  )
+
+  def find_best_match(typo):
+    return min(
+        [(threshold + 1, typo)]
+        + [
+            (levenshtein(typo, d), d)
+            for d in all_directives
+            if abs(len(d) - len(typo)) <= threshold
+        ],
+        key=lambda tup: tup[0],
+    )
+
+  comment_prefix = comment_prefix or '//'
+  potential_directives = find_potential_directives(lines, comment_prefix)
+  diagnostics = []
+
+  for filepos, potential_directive in potential_directives:
+    # TODO(bchetioui): match count directives more finely. We skip directives
+    # starting with 'CHECK-COUNT-' for the moment as they require more complex
+    # logic to be handled correctly.
+    if any(
+        potential_directive.startswith(f'{prefix}-COUNT-')
+        for prefix in all_prefixes
+    ):
+      continue
+
+    # Ignoring potential typos that will not be matched later due to a too low
+    # threshold, in order to avoid potentially long computation times.
+    if len(potential_directive) > max(map(len, all_directives)) + threshold:
+      continue
+
+    score, best_match = find_best_match(potential_directive)
+    if score == 0:  # This is an actual directive, ignore.
+      continue
+    elif score <= threshold and best_match not in _ignore:
+      diagnostics.append(
+          Diagnostic(filepath, filepos, potential_directive, best_match)
+      )
+
+  return diagnostics

llvm/utils/filecheck_lint/tests/filecheck_lint_test.py

+# ===----------------------------------------------------------------------===##
+#
+# Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+# See https://llvm.org/LICENSE.txt for license information.
+# SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+#
+# ===----------------------------------------------------------------------===##
+import unittest
+
+import filecheck_lint.filecheck_lint as fcl
+
+
+class TestParser(unittest.TestCase):
+
+  def test_parse_all_additional_prefixes(self):
+
+    def run(lines, expected_prefixes):
+      prefixes = fcl.parse_additional_prefixes(lines)
+      for prefix in expected_prefixes:
+        self.assertIn(prefix, prefixes)
+
+    for lines, expected_prefixes in [
+        (['-check-prefix=PREFIX'], {'PREFIX'}),
+        (['-check-prefix PREFIX'], {'PREFIX'}),
+        (['-check-prefixes=PREFIX1,PREFIX2'], {'PREFIX1', 'PREFIX2'}),
+        (['-check-prefixes PREFIX1,PREFIX2'], {'PREFIX1', 'PREFIX2'}),
+        ([
+            '-check-prefix=PREFIX1 -check-prefix PREFIX2',
+            '-check-prefixes=PREFIX3,PREFIX4 -check-prefix=PREFIX5',
+            '-check-prefixes PREFIX6,PREFIX7 -check-prefixes=PREFIX8',
+         ],  # pylint: disable=bad-continuation
+         {f'PREFIX{i}' for i in range(1, 9)}),
+    ]:
+      run(lines, expected_prefixes)
+
+  def test_additional_prefixes_uniquely(self):
+    lines = ['--check-prefix=SOME-PREFIX', '--check-prefix=SOME-PREFIX']
+    prefixes = fcl.parse_additional_prefixes(lines)
+    assert len(prefixes) == 1
+
+  def test_additional_prefix_line_continuation(self):
+    lines = ['--check-prefix=SOME-PREFIX\\']
+    assert fcl.parse_additional_prefixes(lines) == {'SOME-PREFIX'}
+
+
+class TestTypoDetection(unittest.TestCase):
+
+  def test_find_potential_directives_comment_prefix(self):
+    lines = ['junk; CHCK1:', 'junk// CHCK2:', 'SOME CHCK3:']
+
+    semi_prefix_results = fcl.find_potential_directives(lines, ';')
+    assert len(semi_prefix_results) == 1
+    pos, match = semi_prefix_results[0]
+    assert (pos.line == 1 and
+            pos.start_column == len('junk; ') + 1 and
+            pos.end_column == len(lines[0]) - 1)
+    assert match == 'CHCK1'
+
+    doubleslash_prefix_results = fcl.find_potential_directives(lines, '//')
+    assert len(doubleslash_prefix_results) == 1
+    pos, match = doubleslash_prefix_results[0]
+    assert (pos.line == 2 and
+            pos.start_column == len('junk// ') + 1 and
+            pos.end_column == len(lines[1]) - 1)
+    assert match == 'CHCK2'
+
+    no_prefix_results = fcl.find_potential_directives(lines, None)
+    assert len(no_prefix_results) == 3
+    assert no_prefix_results[0][1] == 'CHCK1'
+    assert no_prefix_results[1][1] == 'CHCK2'
+    assert no_prefix_results[2][1] == 'SOME CHCK3'
+
+  def test_levenshtein(self):
+    for s1, s2, distance in [
+        ('Levenshtein', 'Levenstin', 2),  # 2 insertions
+        ('Levenshtein', 'Levenstherin', 3),  # 1 insertion, 2 deletions
+        ('Levenshtein', 'Lenvinshtein', 2),  # 1 deletion, 1 substitution
+        ('Levenshtein', 'Levenshtein', 0),  # identical strings
+    ]:
+      assert fcl.levenshtein(s1, s2) == distance