[flang] Runtime: implement INDEX intrinsic function

[klausler]

Summary

Implement INDEX in the runtime, reusing some infrastructure
(with generalization and renaming as needed) put into place
for its cousins SCAN and VERIFY.

I did not implement full Boyer-Moore substring searching
for the forward case, but did accelerate some advancement on
mismatches.

I (re)implemented unit testing for INDEX in the new gtest
framework, combining it with the tests that have recently
been ported to gtest for SCAN and VERIFY.

[ashermancinelli]

LGTM

flang/unittests/RuntimeGTest/CharacterTest.cpp

191–195

This approach is far more concise and readable IMO. I'm impressed it's generic enough to work for all three SUT functions for all char types!

[jeanPerier]

LGTM

flang/runtime/character.h

void RTNAME(CharacterMinVal)(Descriptor &result, const Descriptor &x,
     const char *sourceFile = nullptr, int sourceLine = 0);
 void RTNAME(CharacterMaxLoc)(Descriptor &result, const Descriptor &x,
     int dim = 0, const Descriptor *mask = nullptr, int kind = sizeof(int),
     bool back = false, const char *sourceFile = nullptr, int sourceLine = 0);
 void RTNAME(CharacterMinLoc)(Descriptor &result, const Descriptor &x,
     int dim = 0, const Descriptor *mask = nullptr, int kind = sizeof(int),
     bool back = false, const char *sourceFile = nullptr, int sourceLine = 0);
 
+std::size_t RTNAME(Index1)(const char *, std::size_t, const char *substring,
+    std::size_t, bool back = false);
+std::size_t RTNAME(Index2)(const char16_t *, std::size_t,
+    const char16_t *substring, std::size_t, bool back = false);
+std::size_t RTNAME(Index4)(const char32_t *, std::size_t,
+    const char32_t *substring, std::size_t, bool back = false);
+void RTNAME(Index)(Descriptor &result, const Descriptor &string,
+    const Descriptor &substring, const Descriptor *back /*can be null*/,
+    int kind, const char *sourceFile = nullptr, int sourceLine = 0);
+
 std::size_t RTNAME(Scan1)(
     const char *, std::size_t, const char *set, std::size_t, bool back = false);
 std::size_t RTNAME(Scan2)(const char16_t *, std::size_t, const char16_t *set,
     std::size_t, bool back = false);
 std::size_t RTNAME(Scan4)(const char32_t *, std::size_t, const char32_t *set,
     std::size_t, bool back = false);
 void RTNAME(Scan)(Descriptor &result, const Descriptor &string,
     const Descriptor &set, const Descriptor *back /*can be null*/, int kind,

flang/runtime/character.cpp

static void LenTrimKind(Descriptor &result, const Descriptor &string, int kind,
   case 16:
     LenTrim<common::uint128_t, CHAR>(result, string, terminator);
     break;
   default:
     terminator.Crash("LEN_TRIM: bad KIND=%d", kind);
   }
 }
 
+// Utility for dealing with elemental LOGICAL arguments
+static bool IsLogicalElementTrue(
+    const Descriptor &logical, const SubscriptValue at[]) {
+  // A LOGICAL value is false if and only if all of its bytes are zero.
+  const char *p{logical.Element<char>(at)};
+  for (std::size_t j{logical.ElementBytes()}; j-- > 0; ++p) {
+    if (*p) {
+      return true;
+    }
+  }
+  return false;
+}
+
+// INDEX implementation
+template <typename CHAR>
+inline std::size_t Index(const CHAR *x, std::size_t xLen, const CHAR *want,
+    std::size_t wantLen, bool back) {
+  if (xLen < wantLen) {
+    return 0;
+  }
+  if (xLen == 0) {
+    return 1; // wantLen is also 0, so trivial match
+  }
+  if (back) {
+    // If wantLen==0, returns xLen + 1 per standard (and all other compilers)
+    std::size_t at{xLen - wantLen + 1};
+    for (; at > 0; --at) {
+      std::size_t j{1};
+      for (; j <= wantLen; ++j) {
+        if (x[at + j - 2] != want[j - 1]) {
+          break;
+        }
+      }
+      if (j > wantLen) {
+        return at;
+      }
+    }
+    return 0;
+  }
+  // Non-trivial forward substring search: use a simplified form of
+  // Boyer-Moore substring searching.
+  for (std::size_t at{1}; at + wantLen - 1 <= xLen;) {
+    // Compare x(at:at+wantLen-1) with want(1:wantLen).
+    // The comparison proceeds from the ends of the substrings forward
+    // so that we can skip ahead by multiple positions on a miss.
+    std::size_t j{wantLen};
+    CHAR ch;
+    for (; j > 0; --j) {
+      ch = x[at + j - 2];
+      if (ch != want[j - 1]) {
+        break;
+      }
+    }
+    if (j == 0) {
+      return at; // found a match
+    }
+    // Suppose we have at==2:
+    // "THAT FORTRAN THAT I RAN" <- the string (x) in which we search
+    //   "THAT I RAN"            <- the string (want) for which we search
+    //          ^------------------ j==7, ch=='T'
+    // We can shift ahead 3 positions to at==5 to align the 'T's:
+    // "THAT FORTRAN THAT I RAN"
+    //      "THAT I RAN"
+    std::size_t shift{1};
+    for (; shift < j; ++shift) {
+      if (want[j - shift - 1] == ch) {
+        break;
+      }
+    }
+    at += shift;
+  }
+  return 0;
+}
+
 // SCAN and VERIFY implementation help.  These intrinsic functions
 // do pretty much the same thing, so they're templatized with a
 // distinguishing flag.
 
-template <typename CHAR, bool IS_VERIFY = false>
+enum class CharFunc { Index, Scan, Verify };
+
+template <typename CHAR, CharFunc FUNC>
 inline std::size_t ScanVerify(const CHAR *x, std::size_t xLen, const CHAR *set,
     std::size_t setLen, bool back) {
   std::size_t at{back ? xLen : 1};
   int increment{back ? -1 : 1};
   for (; xLen-- > 0; at += increment) {
     CHAR ch{x[at - 1]};
     bool inSet{false};
     // TODO: If set is sorted, could use binary search
     for (std::size_t j{0}; j < setLen; ++j) {
       if (set[j] == ch) {
         inSet = true;
         break;
       }
     }
-    if (inSet != IS_VERIFY) {
+    if (inSet != (FUNC == CharFunc::Verify)) {
       return at;
     }
   }
   return 0;
 }
 
 // Specialization for one-byte characters
 template <bool IS_VERIFY = false>
for (; xLen-- > 0; at += increment) {
       if (inSet != IS_VERIFY) {
         return at;
       }
     }
   }
   return 0;
 }
 
-static bool IsLogicalElementTrue(
-    const Descriptor &logical, const SubscriptValue at[]) {
-  // A LOGICAL value is false if and only if all of its bytes are zero.
-  const char *p{logical.Element<char>(at)};
-  for (std::size_t j{logical.ElementBytes()}; j-- > 0; ++p) {
-    if (*p) {
-      return true;
-    }
-  }
-  return false;
-}
-
-template <typename INT, typename CHAR, bool IS_VERIFY = false>
-static void ScanVerify(Descriptor &result, const Descriptor &string,
-    const Descriptor &set, const Descriptor *back,
+template <typename INT, typename CHAR, CharFunc FUNC>
+static void GeneralCharFunc(Descriptor &result, const Descriptor &string,
+    const Descriptor &arg, const Descriptor *back,
     const Terminator &terminator) {
   int rank{string.rank() ? string.rank()
-                         : set.rank() ? set.rank() : back ? back->rank() : 0};
-  SubscriptValue lb[maxRank], ub[maxRank], stringAt[maxRank], setAt[maxRank],
+          : arg.rank()   ? arg.rank()
+          : back         ? back->rank()
+                         : 0};
+  SubscriptValue lb[maxRank], ub[maxRank], stringAt[maxRank], argAt[maxRank],
       backAt[maxRank];
   SubscriptValue elements{1};
   for (int j{0}; j < rank; ++j) {
     lb[j] = 1;
-    ub[j] = string.rank()
-        ? string.GetDimension(j).Extent()
-        : set.rank() ? set.GetDimension(j).Extent()
-                     : back ? back->GetDimension(j).Extent() : 1;
+    ub[j] = string.rank() ? string.GetDimension(j).Extent()
+        : arg.rank()      ? arg.GetDimension(j).Extent()
+        : back            ? back->GetDimension(j).Extent()
+                          : 1;
     elements *= ub[j];
-    stringAt[j] = setAt[j] = backAt[j] = 1;
+    stringAt[j] = argAt[j] = backAt[j] = 1;
   }
   result.Establish(TypeCategory::Integer, sizeof(INT), nullptr, rank, ub,
       CFI_attribute_allocatable);
   if (result.Allocate(lb, ub) != CFI_SUCCESS) {
     terminator.Crash("SCAN/VERIFY: could not allocate storage for result");
   }
   std::size_t stringElementChars{string.ElementBytes() >> shift<CHAR>};
-  std::size_t setElementChars{set.ElementBytes() >> shift<CHAR>};
+  std::size_t argElementChars{arg.ElementBytes() >> shift<CHAR>};
   for (SubscriptValue resultAt{0}; elements-- > 0; resultAt += sizeof(INT),
-       string.IncrementSubscripts(stringAt), set.IncrementSubscripts(setAt),
+       string.IncrementSubscripts(stringAt), arg.IncrementSubscripts(argAt),
        back && back->IncrementSubscripts(backAt)) {
+    if constexpr (FUNC == CharFunc::Index) {
+      *result.OffsetElement<INT>(resultAt) =
+          Index<CHAR>(string.Element<CHAR>(stringAt), stringElementChars,
+              arg.Element<CHAR>(argAt), argElementChars,
+              back && IsLogicalElementTrue(*back, backAt));
+    } else if constexpr (FUNC == CharFunc::Scan) {
       *result.OffsetElement<INT>(resultAt) =
-        ScanVerify<CHAR, IS_VERIFY>(string.Element<CHAR>(stringAt),
-            stringElementChars, set.Element<CHAR>(setAt), setElementChars,
+          ScanVerify<CHAR, CharFunc::Scan>(string.Element<CHAR>(stringAt),
+              stringElementChars, arg.Element<CHAR>(argAt), argElementChars,
               back && IsLogicalElementTrue(*back, backAt));
+    } else if constexpr (FUNC == CharFunc::Verify) {
+      *result.OffsetElement<INT>(resultAt) =
+          ScanVerify<CHAR, CharFunc::Verify>(string.Element<CHAR>(stringAt),
+              stringElementChars, arg.Element<CHAR>(argAt), argElementChars,
+              back && IsLogicalElementTrue(*back, backAt));
+    } else {
+      static_assert(FUNC == CharFunc::Index || FUNC == CharFunc::Scan ||
+          FUNC == CharFunc::Verify);
+    }
   }
 }
 
-template <typename CHAR, bool IS_VERIFY = false>
-static void ScanVerifyKind(Descriptor &result, const Descriptor &string,
-    const Descriptor &set, const Descriptor *back, int kind,
+template <typename CHAR, CharFunc FUNC>
+static void GeneralCharFuncKind(Descriptor &result, const Descriptor &string,
+    const Descriptor &arg, const Descriptor *back, int kind,
     const Terminator &terminator) {
   switch (kind) {
   case 1:
-    ScanVerify<std::int8_t, CHAR, IS_VERIFY>(
-        result, string, set, back, terminator);
+    GeneralCharFunc<std::int8_t, CHAR, FUNC>(
+        result, string, arg, back, terminator);
     break;
   case 2:
-    ScanVerify<std::int16_t, CHAR, IS_VERIFY>(
-        result, string, set, back, terminator);
+    GeneralCharFunc<std::int16_t, CHAR, FUNC>(
+        result, string, arg, back, terminator);
     break;
   case 4:
-    ScanVerify<std::int32_t, CHAR, IS_VERIFY>(
-        result, string, set, back, terminator);
+    GeneralCharFunc<std::int32_t, CHAR, FUNC>(
+        result, string, arg, back, terminator);
     break;
   case 8:
-    ScanVerify<std::int64_t, CHAR, IS_VERIFY>(
-        result, string, set, back, terminator);
+    GeneralCharFunc<std::int64_t, CHAR, FUNC>(
+        result, string, arg, back, terminator);
     break;
   case 16:
-    ScanVerify<common::uint128_t, CHAR, IS_VERIFY>(
-        result, string, set, back, terminator);
+    GeneralCharFunc<common::uint128_t, CHAR, FUNC>(
+        result, string, arg, back, terminator);
     break;
   default:
-    terminator.Crash("SCAN/VERIFY: bad KIND=%d", kind);
+    terminator.Crash("INDEX/SCAN/VERIFY: bad KIND=%d", kind);
   }
 }
 
 template <typename TO, typename FROM>
 static void CopyAndPad(
     TO *to, const FROM *from, std::size_t toChars, std::size_t fromChars) {
   if constexpr (sizeof(TO) != sizeof(FROM)) {
     std::size_t copyChars{std::min(toChars, fromChars)};
void RTNAME(AdjustL)(Descriptor &result, const Descriptor &string,
   AdjustLR<false>(result, string, sourceFile, sourceLine);
 }
 
 void RTNAME(AdjustR)(Descriptor &result, const Descriptor &string,
     const char *sourceFile, int sourceLine) {
   AdjustLR<true>(result, string, sourceFile, sourceLine);
 }
 
+std::size_t RTNAME(Index1)(const char *x, std::size_t xLen, const char *set,
+    std::size_t setLen, bool back) {
+  return Index<char>(x, xLen, set, setLen, back);
+}
+std::size_t RTNAME(Index2)(const char16_t *x, std::size_t xLen,
+    const char16_t *set, std::size_t setLen, bool back) {
+  return Index<char16_t>(x, xLen, set, setLen, back);
+}
+std::size_t RTNAME(Index4)(const char32_t *x, std::size_t xLen,
+    const char32_t *set, std::size_t setLen, bool back) {
+  return Index<char32_t>(x, xLen, set, setLen, back);
+}
+
+void RTNAME(Index)(Descriptor &result, const Descriptor &string,
+    const Descriptor &substring, const Descriptor *back, int kind,
+    const char *sourceFile, int sourceLine) {
+  Terminator terminator{sourceFile, sourceLine};
+  switch (string.raw().type) {
+  case CFI_type_char:
+    GeneralCharFuncKind<char, CharFunc::Index>(
+        result, string, substring, back, kind, terminator);
+    break;
+  case CFI_type_char16_t:
+    GeneralCharFuncKind<char16_t, CharFunc::Index>(
+        result, string, substring, back, kind, terminator);
+    break;
+  case CFI_type_char32_t:
+    GeneralCharFuncKind<char32_t, CharFunc::Index>(
+        result, string, substring, back, kind, terminator);
+    break;
+  default:
+    terminator.Crash(
+        "INDEX: bad string type code %d", static_cast<int>(string.raw().type));
+  }
+}
+
 std::size_t RTNAME(LenTrim1)(const char *x, std::size_t chars) {
   return LenTrim(x, chars);
 }
 std::size_t RTNAME(LenTrim2)(const char16_t *x, std::size_t chars) {
   return LenTrim(x, chars);
 }
 std::size_t RTNAME(LenTrim4)(const char32_t *x, std::size_t chars) {
   return LenTrim(x, chars);
void RTNAME(LenTrim)(Descriptor &result, const Descriptor &string, int kind,
   default:
     terminator.Crash("LEN_TRIM: bad string type code %d",
         static_cast<int>(string.raw().type));
   }
 }
 
 std::size_t RTNAME(Scan1)(const char *x, std::size_t xLen, const char *set,
     std::size_t setLen, bool back) {
-  return ScanVerify<char, false>(x, xLen, set, setLen, back);
+  return ScanVerify<char, CharFunc::Scan>(x, xLen, set, setLen, back);
 }
 std::size_t RTNAME(Scan2)(const char16_t *x, std::size_t xLen,
     const char16_t *set, std::size_t setLen, bool back) {
-  return ScanVerify<char16_t, false>(x, xLen, set, setLen, back);
+  return ScanVerify<char16_t, CharFunc::Scan>(x, xLen, set, setLen, back);
 }
 std::size_t RTNAME(Scan4)(const char32_t *x, std::size_t xLen,
     const char32_t *set, std::size_t setLen, bool back) {
-  return ScanVerify<char32_t, false>(x, xLen, set, setLen, back);
+  return ScanVerify<char32_t, CharFunc::Scan>(x, xLen, set, setLen, back);
 }
 
 void RTNAME(Scan)(Descriptor &result, const Descriptor &string,
     const Descriptor &set, const Descriptor *back, int kind,
     const char *sourceFile, int sourceLine) {
   Terminator terminator{sourceFile, sourceLine};
   switch (string.raw().type) {
   case CFI_type_char:
-    ScanVerifyKind<char, false>(result, string, set, back, kind, terminator);
+    GeneralCharFuncKind<char, CharFunc::Scan>(
+        result, string, set, back, kind, terminator);
     break;
   case CFI_type_char16_t:
-    ScanVerifyKind<char16_t, false>(
+    GeneralCharFuncKind<char16_t, CharFunc::Scan>(
         result, string, set, back, kind, terminator);
     break;
   case CFI_type_char32_t:
-    ScanVerifyKind<char32_t, false>(
+    GeneralCharFuncKind<char32_t, CharFunc::Scan>(
         result, string, set, back, kind, terminator);
     break;
   default:
     terminator.Crash(
         "SCAN: bad string type code %d", static_cast<int>(string.raw().type));
   }
 }
 
void RTNAME(Trim)(Descriptor &result, const Descriptor &string,
   result.Establish(string.type(), resultBytes, nullptr, 0, nullptr,
       CFI_attribute_allocatable);
   RUNTIME_CHECK(terminator, result.Allocate(nullptr, nullptr) == CFI_SUCCESS);
   std::memcpy(result.OffsetElement(), string.OffsetElement(), resultBytes);
 }
 
 std::size_t RTNAME(Verify1)(const char *x, std::size_t xLen, const char *set,
     std::size_t setLen, bool back) {
-  return ScanVerify<char, true>(x, xLen, set, setLen, back);
+  return ScanVerify<char, CharFunc::Verify>(x, xLen, set, setLen, back);
 }
 std::size_t RTNAME(Verify2)(const char16_t *x, std::size_t xLen,
     const char16_t *set, std::size_t setLen, bool back) {
-  return ScanVerify<char16_t, true>(x, xLen, set, setLen, back);
+  return ScanVerify<char16_t, CharFunc::Verify>(x, xLen, set, setLen, back);
 }
 std::size_t RTNAME(Verify4)(const char32_t *x, std::size_t xLen,
     const char32_t *set, std::size_t setLen, bool back) {
-  return ScanVerify<char32_t, true>(x, xLen, set, setLen, back);
+  return ScanVerify<char32_t, CharFunc::Verify>(x, xLen, set, setLen, back);
 }
 
 void RTNAME(Verify)(Descriptor &result, const Descriptor &string,
     const Descriptor &set, const Descriptor *back, int kind,
     const char *sourceFile, int sourceLine) {
   Terminator terminator{sourceFile, sourceLine};
   switch (string.raw().type) {
   case CFI_type_char:
-    ScanVerifyKind<char, true>(result, string, set, back, kind, terminator);
+    GeneralCharFuncKind<char, CharFunc::Verify>(
+        result, string, set, back, kind, terminator);
     break;
   case CFI_type_char16_t:
-    ScanVerifyKind<char16_t, true>(result, string, set, back, kind, terminator);
+    GeneralCharFuncKind<char16_t, CharFunc::Verify>(
+        result, string, set, back, kind, terminator);
     break;
   case CFI_type_char32_t:
-    ScanVerifyKind<char32_t, true>(result, string, set, back, kind, terminator);
+    GeneralCharFuncKind<char32_t, CharFunc::Verify>(
+        result, string, set, back, kind, terminator);
     break;
   default:
     terminator.Crash(
         "VERIFY: bad string type code %d", static_cast<int>(string.raw().type));
   }
 }
 
 void RTNAME(CharacterMax)(Descriptor &accumulator, const Descriptor &x,

flang/unittests/RuntimeGTest/CharacterTest.cpp

 //===-- flang/unittests/RuntimeGTest/CharacterTest.cpp ----------*- C++ -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
+// Basic sanity tests of CHARACTER API; exhaustive testing will be done
+// in Fortran.
+
 #include "../../runtime/character.h"
 #include "gtest/gtest.h"
 #include <cstring>
 #include <functional>
 #include <tuple>
 #include <vector>
 
 using namespace Fortran::runtime;
for (auto &[x, y, xBytes, yBytes, expect] : this->parameters) {
     std::memcpy(buf[0], x, xBytes);
     std::memcpy(buf[1], y, yBytes);
     ASSERT_EQ(cmp, expect) << "compare '" << x << "'(" << xBytes << ") to '"
                            << y << "'(" << yBytes << "), got " << cmp
                            << ", should be " << expect << '\n';
   }
 }
 
-//------------------------------------------------------------------------------
-/// Tests and infrastructure for Scan functions
-//------------------------------------------------------------------------------
-
-template <typename CHAR>
-using ScanFuncTy = std::function<int(
-    const CHAR *, std::size_t, const CHAR *, std::size_t, bool)>;
-
-using ScanFuncsTy =
-    std::tuple<ScanFuncTy<char>, ScanFuncTy<char16_t>, ScanFuncTy<char32_t>>;
-
-// These functions are the systems under test in CharacterScanTests test cases.
-static ScanFuncsTy scanFuncs{
-    RTNAME(Scan1),
-    RTNAME(Scan2),
-    RTNAME(Scan4),
-};
-
-// Types of _values_ over which tests are parameterized
-template <typename CHAR>
-using ScanParametersTy =
-    std::vector<std::tuple<const CHAR *, const CHAR *, bool, int>>;
-
-using ScanTestCasesTy = std::tuple<ScanParametersTy<char>,
-    ScanParametersTy<char16_t>, ScanParametersTy<char32_t>>;
-
-static ScanTestCasesTy scanTestCases{
-    {
-        std::make_tuple("abc", "abc", false, 1),
-        std::make_tuple("abc", "abc", true, 3),
-        std::make_tuple("abc", "cde", false, 3),
-        std::make_tuple("abc", "cde", true, 3),
-        std::make_tuple("abc", "x", false, 0),
-        std::make_tuple("", "x", false, 0),
-    },
-    {
-        std::make_tuple(u"abc", u"abc", false, 1),
-        std::make_tuple(u"abc", u"abc", true, 3),
-        std::make_tuple(u"abc", u"cde", false, 3),
-        std::make_tuple(u"abc", u"cde", true, 3),
-        std::make_tuple(u"abc", u"x", false, 0),
-        std::make_tuple(u"", u"x", false, 0),
-    },
-    {
-        std::make_tuple(U"abc", U"abc", false, 1),
-        std::make_tuple(U"abc", U"abc", true, 3),
-        std::make_tuple(U"abc", U"cde", false, 3),
-        std::make_tuple(U"abc", U"cde", true, 3),
-        std::make_tuple(U"abc", U"x", false, 0),
-        std::make_tuple(U"", U"x", false, 0),
-    }};
-
-template <typename CHAR> struct CharacterScanTests : public ::testing::Test {
-  CharacterScanTests()
-      : parameters{std::get<ScanParametersTy<CHAR>>(scanTestCases)},
-        characterScanFunc{std::get<ScanFuncTy<CHAR>>(scanFuncs)} {}
-  ScanParametersTy<CHAR> parameters;
-  ScanFuncTy<CHAR> characterScanFunc;
-};
-
-// Type-parameterized over the same character types as CharacterComparisonTests
-TYPED_TEST_CASE(CharacterScanTests, CharacterTypes);
+// Test search functions INDEX(), SCAN(), and VERIFY()
 
-TYPED_TEST(CharacterScanTests, ScanCharacters) {
-  for (auto const &[str, set, back, expect] : this->parameters) {
-    auto res{
-        this->characterScanFunc(str, std::char_traits<TypeParam>::length(str),
-            set, std::char_traits<TypeParam>::length(set), back)};
-    ASSERT_EQ(res, expect) << "Scan(" << str << ',' << set << ",back=" << back
-                           << "): got " << res << ", should be " << expect;
-  }
-}
-
-//------------------------------------------------------------------------------
-/// Tests and infrastructure for Verify functions
-//------------------------------------------------------------------------------
 template <typename CHAR>
-using VerifyFuncTy = std::function<int(
+using SearchFunction = std::function<std::size_t(
     const CHAR *, std::size_t, const CHAR *, std::size_t, bool)>;
-
-using VerifyFuncsTy = std::tuple<VerifyFuncTy<char>, VerifyFuncTy<char16_t>,
-    VerifyFuncTy<char32_t>>;
-
-// These functions are the systems under test in CharacterVerifyTests test cases
-static VerifyFuncsTy verifyFuncs{
-    RTNAME(Verify1),
-    RTNAME(Verify2),
-    RTNAME(Verify4),
-};
-
-// Types of _values_ over which tests are parameterized
-template <typename CHAR>
-using VerifyParametersTy =
-    std::vector<std::tuple<const CHAR *, const CHAR *, bool, int>>;
-
-using VerifyTestCasesTy = std::tuple<VerifyParametersTy<char>,
-    VerifyParametersTy<char16_t>, VerifyParametersTy<char32_t>>;
-
-static VerifyTestCasesTy verifyTestCases{
-    {
-        std::make_tuple("abc", "abc", false, 0),
-        std::make_tuple("abc", "abc", true, 0),
-        std::make_tuple("abc", "cde", false, 1),
-        std::make_tuple("abc", "cde", true, 2),
-        std::make_tuple("abc", "x", false, 1),
-        std::make_tuple("", "x", false, 0),
-    },
-    {
-        std::make_tuple(u"abc", u"abc", false, 0),
-        std::make_tuple(u"abc", u"abc", true, 0),
-        std::make_tuple(u"abc", u"cde", false, 1),
-        std::make_tuple(u"abc", u"cde", true, 2),
-        std::make_tuple(u"abc", u"x", false, 1),
-        std::make_tuple(u"", u"x", false, 0),
-    },
-    {
-        std::make_tuple(U"abc", U"abc", false, 0),
-        std::make_tuple(U"abc", U"abc", true, 0),
-        std::make_tuple(U"abc", U"cde", false, 1),
-        std::make_tuple(U"abc", U"cde", true, 2),
-        std::make_tuple(U"abc", U"x", false, 1),
-        std::make_tuple(U"", U"x", false, 0),
-    }};
-
-template <typename CHAR> struct CharacterVerifyTests : public ::testing::Test {
-  CharacterVerifyTests()
-      : parameters{std::get<VerifyParametersTy<CHAR>>(verifyTestCases)},
-        characterVerifyFunc{std::get<VerifyFuncTy<CHAR>>(verifyFuncs)} {}
-  VerifyParametersTy<CHAR> parameters;
-  VerifyFuncTy<CHAR> characterVerifyFunc;
+template <template <typename> class FUNC>
+using CharTypedFunctions =
+    std::tuple<FUNC<char>, FUNC<char16_t>, FUNC<char32_t>>;
+using SearchFunctions = CharTypedFunctions<SearchFunction>;
+struct SearchTestCase {
+  const char *x, *y;
+  bool back;
+  std::size_t expect;
+};
+
+template <typename CHAR>
+void RunSearchTests(const char *which,
+    const std::vector<SearchTestCase> &testCases,
+    const SearchFunction<CHAR> &function) {
+  for (const auto &t : testCases) {
+    // Convert default character to desired kind
+    std::size_t xLen{std::strlen(t.x)}, yLen{std::strlen(t.y)};
+    std::basic_string<CHAR> x{t.x, t.x + xLen};
+    std::basic_string<CHAR> y{t.y, t.y + yLen};
+    auto got{function(x.data(), xLen, y.data(), yLen, t.back)};
+    ASSERT_EQ(got, t.expect)
+        << which << "('" << t.x << "','" << t.y << "',back=" << t.back
+        << ") for CHARACTER(kind=" << sizeof(CHAR) << "): got " << got
+        << ", expected " << t.expect;
+  }
+}
+
+template <typename CHAR> struct SearchTests : public ::testing::Test {};
+TYPED_TEST_CASE(SearchTests, CharacterTypes);
+
+TYPED_TEST(SearchTests, IndexTests) {
+  static SearchFunctions functions{
+      RTNAME(Index1), RTNAME(Index2), RTNAME(Index4)};
+  static std::vector<SearchTestCase> tests{
+      {"", "", false, 1},
+      {"", "", true, 1},
+      {"a", "", false, 1},
+      {"a", "", true, 2},
+      {"", "a", false, 0},
+      {"", "a", true, 0},
+      {"aa", "a", false, 1},
+      {"aa", "a", true, 2},
+      {"Fortran that I ran", "that I ran", false, 9},
+      {"Fortran that I ran", "that I ran", true, 9},
+      {"Fortran that you ran", "that I ran", false, 0},
+      {"Fortran that you ran", "that I ran", true, 0},
+  };
+  RunSearchTests(
+      "INDEX", tests, std::get<SearchFunction<TypeParam>>(functions));
+}
+
+TYPED_TEST(SearchTests, ScanTests) {
+  static SearchFunctions functions{RTNAME(Scan1), RTNAME(Scan2), RTNAME(Scan4)};
+  static std::vector<SearchTestCase> tests{
+      {"abc", "abc", false, 1},
+      {"abc", "abc", true, 3},
+      {"abc", "cde", false, 3},
+      {"abc", "cde", true, 3},
+      {"abc", "x", false, 0},
+      {"", "x", false, 0},
+  };
+  RunSearchTests("SCAN", tests, std::get<SearchFunction<TypeParam>>(functions));
+}
+
+TYPED_TEST(SearchTests, VerifyTests) {
+  static SearchFunctions functions{
+      RTNAME(Verify1), RTNAME(Verify2), RTNAME(Verify4)};
+  static std::vector<SearchTestCase> tests{
+      {"abc", "abc", false, 0},
+      {"abc", "abc", true, 0},
+      {"abc", "cde", false, 1},
+      {"abc", "cde", true, 2},
+      {"abc", "x", false, 1},
+      {"", "x", false, 0},
   };
-
-// Type-parameterized over the same character types as CharacterComparisonTests
-TYPED_TEST_CASE(CharacterVerifyTests, CharacterTypes);
-
-TYPED_TEST(CharacterVerifyTests, VerifyCharacters) {
-  for (auto const &[str, set, back, expect] : this->parameters) {
-    auto res{
-        this->characterVerifyFunc(str, std::char_traits<TypeParam>::length(str),
-            set, std::char_traits<TypeParam>::length(set), back)};
-    ASSERT_EQ(res, expect) << "Verify(" << str << ',' << set << ",back=" << back
-                           << "): got " << res << ", should be " << expect;
-  }
+  RunSearchTests(
+      "VERIFY", tests, std::get<SearchFunction<TypeParam>>(functions));
 }