[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 ↗

(On Diff #488229)

replace with a normal space?

16 ↗

(On Diff #488229)

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

19

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 ↗

(On Diff #488229)

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 ↗

(On Diff #488229)

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 ↗

(On Diff #488229)

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

83 ↗

(On Diff #488229)

"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 ↗

(On Diff #488229)

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

124 ↗

(On Diff #488229)

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 ↗

(On Diff #488229)

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 ↗

(On Diff #488229)

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 ↗

(On Diff #488229)

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 ↗

(On Diff #488229)

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 ↗

(On Diff #488229)

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 ↗

(On Diff #488229)

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

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

259 ↗

(On Diff #488229)

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

268 ↗

(On Diff #488229)

this just echoes the function name

276 ↗

(On Diff #488229)

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

292 ↗

(On Diff #488229)

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

312 ↗

(On Diff #488229)

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 ↗

(On Diff #488229)

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 ↗

(On Diff #488229)

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

llvm/utils/filecheck_lint/filecheck_lint/filecheck_lint.py

8 ↗

(On Diff #488229)

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

39 ↗

(On Diff #488229)

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 ↗

(On Diff #488229)

Done. (The fix is not optional.)

124 ↗

(On Diff #488229)

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 ↗

(On Diff #488229)

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 ↗

(On Diff #488229)

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 ↗

(On Diff #488229)

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 ↗

(On Diff #488229)

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

187 ↗

(On Diff #488229)

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 ↗

(On Diff #488229)

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

312 ↗

(On Diff #488229)

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 ↗

(On Diff #488229)

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 ↗

(On Diff #488229)

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 ↗

(On Diff #488229)

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 ↗

(On Diff #488229)

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 ↗

(On Diff #488229)

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 ↗

(On Diff #488229)

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/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.
+
+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
+
+We first detect the locally valid FileCheck directive prefixes by parsing the
+--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:',
+usually 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 and report it.
+
+Usage: filecheck_lint path/to/test/file/1 ... path/to/test/file/n
+"""
+
+import itertools
+import logging
+import pathlib
+import re
+import sys
+from typing import Generator, Sequence, Tuple
+
+_distance_threshold = 3
+_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:  # pylint: disable=g-doc-args
+  """Computes the edit distance between two strings.
+
+  Additions, deletions, and substitutions all count as a single operation.
+  """
+  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 FileRange:
+  """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, content: str, start_byte: int, end_byte: int):  # pylint: disable=g-doc-args
+    """Derives a span's coordinates based on a string and start/end bytes.
+
+    `start_byte` and `end_byte` are assumed to be on the same line.
+    """
+    content_before_span = content[:start_byte]
+    self.line = content_before_span.count('\n') + 1
+    self.start_column = start_byte - content_before_span.rfind('\n')
+    self.end_column = self.start_column + (end_byte - start_byte - 1)
+
+  def __str__(self) -> str:
+    return f'{self.line}:{self.start_column}-{self.end_column}'
+
+
+class Diagnostic:
+  """Stores information about one typo and a suggested fix.
+
+  Attributes:
+    filepath:   the path to the file in which the typo was found
+    filerange:  the position at which the typo was found in the file
+    typo:       the typo
+    fix:        a suggested fix
+  """
+
+  filepath: pathlib.Path
+  filerange: FileRange
+  typo: str
+  fix: str
+
+  def __init__(
+      self,
+      filepath: pathlib.Path,
+      filerange: FileRange,
+      typo: str,
+      fix: str  # pylint: disable=redefined-outer-name
+  ):
+    self.filepath = filepath
+    self.filerange = filerange
+    self.typo = typo
+    self.fix = fix
+
+  def __str__(self) -> str:
+    return f'{self.filepath}:' + str(self.filerange) + f': {self.summary()}'
+
+  def summary(self) -> str:
+    return (
+        f'Found potentially misspelled directive "{self.typo}". Did you mean '
+        f'"{self.fix}"?')
+
+
+def find_potential_directives(
+    content: str,) -> Generator[Tuple[FileRange, str], None, None]:
+  """Extracts all the potential FileCheck directives from a string.
+
+  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:
+    content: the string in which to look for directives
+
+  Yields:
+    Tuples (p, d) where p is the span where the potential directive occurs
+    within the string and d is the potential directive.
+  """
+  directive_pattern = re.compile(
+      r'(?:^|//|;|#)[^\d\w\-_]*([\d\w\-_][\s\d\w\-_]*):', re.MULTILINE)
+  for match in re.finditer(directive_pattern, content):
+    potential_directive, span = match.group(1), match.span(1)
+    yield (FileRange(content, span[0], span[1]), potential_directive)
+
+
+# TODO(bchetioui): also parse comment prefixes to ignore.
+def parse_custom_prefixes(content: str) -> Generator[str, None, None]:  # pylint: disable=g-doc-args
+  """Parses custom prefixes defined in the string provided.
+
+  For example, given the following file content:
+    RUN: something | FileCheck %s -check-prefixes CHECK1,CHECK2
+    RUN: something_else | FileCheck %s -check-prefix 'CHECK3'
+
+  the custom prefixes are CHECK1, CHECK2, and CHECK3.
+  """
+  param_re = r'|'.join([r"'[^']*'", r'"[^"]*"', r'[^\'"\s]+'])
+  for m in re.finditer(r'-check-prefix(?:es)?(?:\s+|=)({})'.format(param_re),
+                       content):
+    prefixes = m.group(1)
+    if prefixes.startswith('\'') or prefixes.startswith('"'):
+      prefixes = prefixes[1:-1]
+    for prefix in prefixes.split(','):
+      yield prefix
+
+
+def find_directive_typos(
+    content: str,
+    filepath: pathlib.Path,
+    threshold: int = 3,
+) -> Generator[Diagnostic, None, None]:
+  """Detects potential typos in FileCheck directives.
+
+  Args:
+    content: the content of the file
+    filepath: the path to the file to check for typos in directives
+    threshold: the (inclusive) maximum edit distance between a potential
+      directive and an actual directive, such that the potential directive is
+      classified as a typo
+
+  Yields:
+    Diagnostics, in order from the top of the file.
+  """
+  all_prefixes = _prefixes.union(set(parse_custom_prefixes(content)))
+  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],
+    )
+
+  potential_directives = find_potential_directives(content)
+
+  for filerange, 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:
+      yield Diagnostic(filepath, filerange, potential_directive, best_match)
+
+
+def main(argv: Sequence[str]):
+  if len(argv) < 2:
+    print(f'Usage: {argv[0]} path/to/file/1 ... path/to/file/n')
+    exit(1)
+
+  for filepath in argv[1:]:
+    logging.info('Checking %s', filepath)
+    with open(filepath, 'rt') as f:
+      content = f.read()
+    for diagnostic in find_directive_typos(
+        content,
+        pathlib.Path(filepath),
+        threshold=_distance_threshold,
+    ):
+      print(diagnostic)
+
+
+if __name__ == '__main__':
+  main(sys.argv)

llvm/utils/filecheck_lint/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 as fcl
+
+
+class TestParser(unittest.TestCase):
+
+  def test_parse_all_additional_prefixes(self):
+
+    def run(content, expected_prefixes):
+      prefixes = set(fcl.parse_custom_prefixes(content))
+      for prefix in expected_prefixes:
+        self.assertIn(prefix, prefixes)
+
+    for content, expected_prefixes in [
+        ('-check-prefix=PREFIX', {'PREFIX'}),
+        ('-check-prefix=\'PREFIX\'', {'PREFIX'}),
+        ('-check-prefix="PREFIX"', {'PREFIX'}),
+        ('-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(content, expected_prefixes)
+
+  def test_additional_prefixes_uniquely(self):
+    lines = ['--check-prefix=SOME-PREFIX', '--check-prefix=SOME-PREFIX']
+    prefixes = set(fcl.parse_custom_prefixes('\n'.join(lines)))
+    assert len(prefixes) == 1
+
+
+class TestTypoDetection(unittest.TestCase):
+
+  def test_find_potential_directives_comment_prefix(self):
+    lines = ['junk; CHCK1:', 'junk// CHCK2:', 'SOME CHCK3:']
+    content = '\n'.join(lines)
+
+    results = list(fcl.find_potential_directives(content))
+    assert len(results) == 3
+    pos, match = results[0]
+    assert (pos.line == 1 and
+            pos.start_column == len('junk; ') + 1 and
+            pos.end_column == len(lines[0]) - 1)
+    assert match == 'CHCK1'
+
+    pos, match = results[1]
+    assert (pos.line == 2 and
+            pos.start_column == len('junk// ') + 1 and
+            pos.end_column == len(lines[1]) - 1)
+    assert match == 'CHCK2'
+
+    pos, match = results[2]
+    assert (pos.line == 3 and
+            pos.start_column == 1 and
+            pos.end_column == len(lines[2]) - 1)
+    assert match == '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