Test iOS edit distance on a cloud Mac with Unicode and compute limits

When a search field needs to suggest corrections for misspelled words, edit distance often takes only a few dozen lines of code—but those lines can easily produce incorrect results for Chinese text, combining accents, and emoji. Keeping tests in a fixed working directory on a cloud Mac lets team members across time zones reuse the same Swift fixtures. The goal is not to compare machine speeds, but to define what counts as “one character” and how much computation a single comparison may perform.

Define the distance and character contract

This article uses Levenshtein distance: each insertion, deletion, and substitution costs one, while swapping adjacent characters does not count as a single operation. The distance from ab to ba is therefore two, not one. If autocorrect needs to support transpositions, use a different algorithm rather than just changing the expected result.

Strings are split into Swift Character values, which represent extended grapheme clusters. A family emoji may contain several scalars, but it participates in the comparison as one character. Equivalent accented characters in precomposed and decomposed forms can compare equal under Swift’s character equality semantics.

Case folding, full-width/half-width conversion, and accent removal are not part of the distance function. If the product requires these rules, implement a separate preprocessing layer and retain the original text as well.

A smaller distance means only that fewer edits are needed under the chosen operation model. It does not imply that two words have similar meanings, and it is not, on its own, a basis for identity matching or security decisions.

Implement rolling rows with a compute budget

On the cloud Mac, confirm that xcrun swift --version runs successfully, then save the following code as edit-distance.swift. The implementation keeps only the previous and current rows and uses the shorter input for the columns, avoiding storage of the full matrix.

Three limits apply to the inputs: at most 16384 UTF-8 bytes and 512 characters per string, and a maximum of 65536 for the product of the two character counts. These numbers are example engineering budgets, not benchmark findings. In production, adjust them to suit the number of candidates and the target interaction latency.

enum DistanceError: Error {
    case inputLimit
    case workLimit
}

func distance(_ lhs: String, _ rhs: String) throws -> Int {
    guard lhs.utf8.count <= 16_384,
          rhs.utf8.count <= 16_384 else {
        throw DistanceError.inputLimit
    }

    let a = Array(lhs)
    let b = Array(rhs)
    guard a.count <= 512, b.count <= 512 else {
        throw DistanceError.inputLimit
    }

    if a.isEmpty { return b.count }
    if b.isEmpty { return a.count }

    guard a.count <= 65_536 / b.count else {
        throw DistanceError.workLimit
    }

    let columns = a.count <= b.count ? a : b
    let rows = a.count <= b.count ? b : a
    var previous = Array(0...columns.count)
    var current = Array(repeating: 0, count: columns.count + 1)

    for i in rows.indices {
        current[0] = i + 1
        for j in columns.indices {
            let substitution = previous[j]
                + (rows[i] == columns[j] ? 0 : 1)
            current[j + 1] = min(
                previous[j + 1] + 1,
                min(current[j] + 1, substitution)
            )
        }
        swap(&previous, &current)
    }
    return previous[columns.count]
}

The division-based check avoids the integer overflow that could occur if the lengths were multiplied before checking the limit. Empty strings return before the division, eliminating the risk of division by zero. The byte limit is checked before constructing the arrays: a character-count limit alone could otherwise accept oversized input consisting of a few characters with large numbers of combining marks.

Add runnable acceptance fixtures

Append the following code to the same file, then run xcrun swift edit-distance.swift. It uses an explicit failure function rather than assertions, which may be disabled in optimized builds.

func require(_ condition: Bool) {
    if !condition { fatalError("Distance contract failed") }
}

let fixtures: [(String, String, Int)] = [
    ("", "", 0),
    ("", "构建", 2),
    ("kitten", "sitting", 3),
    ("构建", "构件", 1),
    ("ab", "ba", 2),
    ("\u{00E9}", "e\u{0301}", 0),
    ("👨‍👩‍👧‍👦", "", 1)
]

for (a, b, expected) in fixtures {
    let forward = try distance(a, b)
    let backward = try distance(b, a)
    require(forward == expected)
    require(backward == expected)
}

do {
    _ = try distance(
        String(repeating: "a", count: 257),
        String(repeating: "b", count: 257)
    )
    fatalError("Expected work limit")
} catch DistanceError.workLimit {
}

These fixtures check initialization, substitution, transposition semantics, and the Unicode unit used for comparison. The budget-rejection test accepts only the specified error. Any other error continues to propagate rather than being swallowed by a broad catch and incorrectly treated as a pass.

Cover input combinations with property tests

Fixed fixtures catch known errors; testing combinations helps uncover defects in row swapping, boundary initialization, and repeated-character handling. Using a, b, and one Chinese character, generate every string of up to three characters. For every pair, verify that:

• The distance from a string to itself is zero, and swapping the arguments does not change the result.
• The distance is at least the absolute difference between the character counts.
• The distance is no greater than the larger of the two character counts.

Also check the triangle inequality for a small set of triples. Satisfying these properties does not prove the algorithm is fully correct, so use them alongside known results. Inputs that exceed the budget should not be required to return a distance or take part in these property comparisons.

Test the preprocessing layer separately

If search is case-insensitive, verify the preprocessing output separately, then verify the distance between those outputs. Do not call locale-dependent conversions inside the dynamic programming loop: the result for the same pair of words could vary with the environment, and every cell would incur the conversion cost again.

Integrate with the pipeline and cap total work

Commit the script alongside the application code and run it before the unit tests, blocking subsequent steps if it exits with a nonzero status. Record the source commit identifier, Swift version, and failing fixture. There is no need to impose millisecond-level thresholds based on wall-clock time; changing workloads on a shared machine make such thresholds noisy.

A budget for one comparison does not provide a budget for the entire search request. First narrow the candidate pool by business category or length difference, then cap the number of candidates. If cancellation is needed, check for it between candidates. A synchronous distance function does not stop automatically when its enclosing task is cancelled.

Before release, address four items: the empty-input policy, how limit errors are presented, the total candidate budget, and the preprocessing version. When a limit is exceeded, explicitly return “not computed” rather than disguising it as a very large distance. This keeps search ranking from mistaking resource-protection measures for evidence that two texts are dissimilar.

Frequently asked questions