Repository: apple/swift-argument-parser (swift)

Issue:
Provide near-miss suggestions
If a user mistypes an option, flag, or command, the error message should include a suggestion for the near-miss.

Example:

```
% example --indx 5
Error: Unexpected argument '--indx'
       Did you mean '--index'?
Usage: example [--index <index>] [<values> ...]
```

Pull request description:
When an unknown option is encountered use levenshtein to find the closest matching option. Simply prints the error if there is no close match ([distance >= 7](https://github.com/git/git/blob/228f53135a4a41a37b6be8e4d6e2b6153db4a8ed/help.c#L592)).

Fixes #2

Patch:
diff --git a/Sources/ArgumentParser/Parsing/CommandParser.swift b/Sources/ArgumentParser/Parsing/CommandParser.swift
index 5027ff225..3a5b93688 100644
--- a/Sources/ArgumentParser/Parsing/CommandParser.swift
+++ b/Sources/ArgumentParser/Parsing/CommandParser.swift
@@ -78,6 +78,13 @@ extension CommandParser {
     
     // We should have used up all arguments at this point:
     guard split.isEmpty else {
+      // Check if one of the arguments is an unknown option
+      for (index, element) in split.elements {
+        if case .option(let argument) = element {
+          throw ParserError.unknownOption(InputOrigin.Element.argumentIndex(index), argument.name)
+        }
+      }
+       
       let extra = split.coalescedExtraElements()
       throw ParserError.unexpectedExtraValues(extra)
     }
diff --git a/Sources/ArgumentParser/Usage/UsageGenerator.swift b/Sources/ArgumentParser/Usage/UsageGenerator.swift
index bf826d78e..fd2514903 100644
--- a/Sources/ArgumentParser/Usage/UsageGenerator.swift
+++ b/Sources/ArgumentParser/Usage/UsageGenerator.swift
@@ -246,16 +246,35 @@ extension ErrorMessageGenerator {
   var invalidState: String {
     return "Internal error. Invalid state while parsing command line arguments."
   }
-  
+
+
   func unknownOptionMessage(origin: InputOrigin.Element, name: Name) -> String {
-    switch name {
-    case .long(let n):
-      return "Unknown option '--\(n)'"
-    case .short(let n):
-      return "Unknown option '-\(n)'"
-    case .longWithSingleDash(let n):
-      return "Unknown option '-\(n)'"
+    if case .short = name {
+      return "Unknown option '\(name.synopsisString)'"
+    }
+    
+    // An empirically derived magic number
+    let SIMILARITY_FLOOR = 4
+
+    let notShort: (Name) -> Bool = { (name: Name) in
+      switch name {
+      case .short: return false
+      case .long: return true
+      case .longWithSingleDash: return true
+      }
+    }
+    let suggestion = arguments
+      .flatMap({ $0.names })
+      .filter({ $0.synopsisString.editDistance(to: name.synopsisString) < SIMILARITY_FLOOR }) // only include close enough suggestion
+      .filter(notShort) // exclude short option suggestions
+      .min(by: { lhs, rhs in // find the suggestion closest to the argument
+        lhs.synopsisString.editDistance(to: name.synopsisString) < rhs.synopsisString.editDistance(to: name.synopsisString)
+      })
+    
+    if let suggestion = suggestion {
+        return "Unknown option '\(name.synopsisString)'. Did you mean '\(suggestion.synopsisString)'?"
     }
+    return "Unknown option '\(name.synopsisString)'"
   }
   
   func missingValueForOptionMessage(origin: InputOrigin, name: Name) -> String {
diff --git a/Sources/ArgumentParser/Utilities/StringExtensions.swift b/Sources/ArgumentParser/Utilities/StringExtensions.swift
index b02a18803..b7f9ded6c 100644
--- a/Sources/ArgumentParser/Utilities/StringExtensions.swift
+++ b/Sources/ArgumentParser/Utilities/StringExtensions.swift
@@ -144,4 +144,51 @@ extension String {
       self[range].lowercased()
     }.joined(separator: String(separator))
   }
+  
+  /// Returns the edit distance between this string and the provided target string.
+  ///
+  /// Uses the Levenshtein distance algorithm internally.
+  ///
+  /// See: https://en.wikipedia.org/wiki/Levenshtein_distance
+  ///
+  /// Examples:
+  ///
+  ///     "kitten".editDistance(to: "sitting")
+  ///     // 3
+  ///     "bar".editDistance(to: "baz")
+  ///     // 1
+
+  func editDistance(to target: String) -> Int {
+    let rows = self.count
+    let columns = target.count
+    
+    if rows <= 0 || columns <= 0 {
+      return max(rows, columns)
+    }
+    
+    var matrix = Array(repeating: Array(repeating: 0, count: columns + 1), count: rows + 1)
+    
+    for row in 1...rows {
+      matrix[row][0] = row
+    }
+    for column in 1...columns {
+      matrix[0][column] = column
+    }
+    
+    for row in 1...rows {
+      for column in 1...columns {
+        let source = self[self.index(self.startIndex, offsetBy: row - 1)]
+        let target = target[target.index(target.startIndex, offsetBy: column - 1)]
+        let cost = source == target ? 0 : 1
+        
+        matrix[row][column] = Swift.min(
+          matrix[row - 1][column] + 1,
+          matrix[row][column - 1] + 1,
+          matrix[row - 1][column - 1] + cost
+        )
+      }
+    }
+    
+    return matrix.last!.last!
+  }
 }


Test patch:
diff --git a/Tests/UnitTests/ErrorMessageTests.swift b/Tests/UnitTests/ErrorMessageTests.swift
index 613d8dc6b..371717bb8 100644
--- a/Tests/UnitTests/ErrorMessageTests.swift
+++ b/Tests/UnitTests/ErrorMessageTests.swift
@@ -32,19 +32,19 @@ extension ErrorMessageTests {
   }
   
   func testUnknownOption_1() {
-    AssertErrorMessage(Bar.self, ["--name", "a", "--format", "b", "--verbose"], "Unexpected argument '--verbose'")
+    AssertErrorMessage(Bar.self, ["--name", "a", "--format", "b", "--verbose"], "Unknown option '--verbose'")
   }
   
   func testUnknownOption_2() {
-    AssertErrorMessage(Bar.self, ["--name", "a", "--format", "b", "-q"], "Unexpected argument '-q'")
+    AssertErrorMessage(Bar.self, ["--name", "a", "--format", "b", "-q"], "Unknown option '-q'")
   }
   
   func testUnknownOption_3() {
-    AssertErrorMessage(Bar.self, ["--name", "a", "--format", "b", "-bar"], "Unexpected argument '-bar'")
+    AssertErrorMessage(Bar.self, ["--name", "a", "--format", "b", "-bar"], "Unknown option '-bar'")
   }
   
   func testUnknownOption_4() {
-    AssertErrorMessage(Bar.self, ["--name", "a", "-foz", "b"], "2 unexpected arguments: '-o', '-z'")
+    AssertErrorMessage(Bar.self, ["--name", "a", "-foz", "b"], "Unknown option '-o'")
   }
   
   func testMissingValue_1() {
@@ -109,3 +109,28 @@ extension ErrorMessageTests {
     AssertErrorMessage(Qux.self, ["--number-two", "a", "1"], "The value 'a' is invalid for '--number-two <number-two>'")
   }
 }
+
+fileprivate struct Qwz: ParsableArguments {
+  @Option() var name: String?
+  @Option(name: [.customLong("title", withSingleDash: true)]) var title: String?
+}
+
+extension ErrorMessageTests {
+  func testMispelledArgument_1() {
+    AssertErrorMessage(Qwz.self, ["--nme"], "Unknown option '--nme'. Did you mean '--name'?")
+    AssertErrorMessage(Qwz.self, ["-name"], "Unknown option '-name'. Did you mean '--name'?")
+  }
+  
+  func testMispelledArgument_2() {
+    AssertErrorMessage(Qwz.self, ["-ttle"], "Unknown option '-ttle'. Did you mean '-title'?")
+    AssertErrorMessage(Qwz.self, ["--title"], "Unknown option '--title'. Did you mean '-title'?")
+  }
+
+  func testMispelledArgument_3() {
+    AssertErrorMessage(Qwz.self, ["--not-similar"], "Unknown option '--not-similar'")
+  }
+
+  func testMispelledArgument_4() {
+    AssertErrorMessage(Qwz.self, ["-x"], "Unknown option '-x'")
+  }
+}
diff --git a/Tests/UnitTests/StringEditDistanceTests.swift b/Tests/UnitTests/StringEditDistanceTests.swift
new file mode 100644
index 000000000..5967c21e8
--- /dev/null
+++ b/Tests/UnitTests/StringEditDistanceTests.swift
@@ -0,0 +1,27 @@
+//===----------------------------------------------------------*- swift -*-===//
+//
+// This source file is part of the Swift Argument Parser open source project
+//
+// Copyright (c) 2020 Apple Inc. and the Swift project authors
+// Licensed under Apache License v2.0 with Runtime Library Exception
+//
+// See https://swift.org/LICENSE.txt for license information
+//
+//===----------------------------------------------------------------------===//
+
+import XCTest
+@testable import ArgumentParser
+
+final class StringEditDistanceTests: XCTestCase {}
+
+extension StringEditDistanceTests {
+  func testStringEditDistance() {
+    XCTAssertEqual("".editDistance(to: ""), 0)
+    XCTAssertEqual("".editDistance(to: "foo"), 3)
+    XCTAssertEqual("foo".editDistance(to: ""), 3)
+    XCTAssertEqual("foo".editDistance(to: "bar"), 3)
+    XCTAssertEqual("bar".editDistance(to: "foo"), 3)
+    XCTAssertEqual("bar".editDistance(to: "baz"), 1)
+    XCTAssertEqual("baz".editDistance(to: "bar"), 1)
+  }
+}