llvm/unittests/ADT/EditDistanceTest.cpp

   1 //===- llvm/unittest/Support/EditDistanceTest.cpp - Edit distance tests ---===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/ADT/StringRef.h"
  10 #include "llvm/ADT/edit_distance.h"
  11 #include "gtest/gtest.h"
  12 #include <cstdlib>
  13
  14 using namespace llvm;
  15
  16 namespace {
  17
  18 struct Result {
  19   unsigned NumMaps;
  20   unsigned EditDist;
  21 };
  22 } // namespace
  23
  24 static Result editDistanceAndMaps(StringRef A, StringRef B,
  25                                   unsigned MaxEditDistance = 0) {
  26   unsigned NumMaps = 0;
  27   auto TrackMaps = [&](const char X) {
  28     ++NumMaps;
  29     return X;
  30   };
  31   unsigned EditDist = llvm::ComputeMappedEditDistance(
  32       ArrayRef(A.data(), A.size()), ArrayRef(B.data(), B.size()), TrackMaps,
  33       true, MaxEditDistance);
  34   return {NumMaps, EditDist};
  35 }
  36
  37 TEST(EditDistance, VerifyShortCircuit) {
  38   StringRef Hello = "Hello";
  39   StringRef HelloWorld = "HelloWorld";
  40   Result R = editDistanceAndMaps(Hello, HelloWorld, 5);
  41   EXPECT_EQ(R.EditDist, 5U);
  42   EXPECT_GT(R.NumMaps, 0U);
  43
  44   R = editDistanceAndMaps(Hello, HelloWorld);
  45   EXPECT_EQ(R.EditDist, 5U);
  46   EXPECT_GT(R.NumMaps, 0U);
  47
  48   R = editDistanceAndMaps(Hello, HelloWorld, 4);
  49   EXPECT_EQ(R.EditDist, 5U);
  50   EXPECT_EQ(R.NumMaps, 0U);
  51
  52   R = editDistanceAndMaps(HelloWorld, Hello, 4);
  53   EXPECT_EQ(R.EditDist, 5U);
  54   EXPECT_EQ(R.NumMaps, 0U);
  55
  56   R = editDistanceAndMaps(Hello, HelloWorld, 1);
  57   EXPECT_EQ(R.EditDist, 2U);
  58   EXPECT_EQ(R.NumMaps, 0U);
  59
  60   R = editDistanceAndMaps(HelloWorld, Hello, 1);
  61   EXPECT_EQ(R.EditDist, 2U);
  62   EXPECT_EQ(R.NumMaps, 0U);
  63 }