be/src/runtime/string-search-test.cc

// Licensed to the Apache Software Foundation (ASF) under one
// or more contributor license agreements.  See the NOTICE file
// distributed with this work for additional information
// regarding copyright ownership.  The ASF licenses this file
// to you under the Apache License, Version 2.0 (the
// "License"); you may not use this file except in compliance
// with the License.  You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing,
// software distributed under the License is distributed on an
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, either express or implied.  See the License for the
// specific language governing permissions and limitations
// under the License.

#include <gtest/gtest.h>

#include "runtime/string-search.h"

namespace impala {

StringValue StrValFromCString(const char* str, int len) {
  if (len == -1) len = strlen(str);
  return StringValue(const_cast<char*>(str), len);
}

// Test string search for haystack/needle, up to len for each.
// If the length is -1, use the full string length.
// Searching in a substring allows checking whether the search respects the
// length stored in the StringValue or also reads parts of the string which
// should be excluded.
int TestSearch(const char* haystack, const char* needle, int haystack_len = -1,
    int needle_len = -1) {
  StringValue needle_str_val = StrValFromCString(needle, needle_len);
  StringValue haystack_str_val = StrValFromCString(haystack, haystack_len);
  StringSearch search(&needle_str_val);
  return search.Search(&haystack_str_val);
}

// Test reverse string search for haystack/needle, up to len for each.
// If the length is -1, use the full string length.
// Searching in a substring allows checking whether the search respects the
// length stored in the StringValue or also reads parts of the string which
// should be excluded.
int TestRSearch(const char* haystack, const char* needle, int haystack_len = -1,
    int needle_len = -1) {
  StringValue needle_str_val = StrValFromCString(needle, needle_len);
  StringValue haystack_str_val = StrValFromCString(haystack, haystack_len);
  StringSearch search(&needle_str_val);
  return search.RSearch(&haystack_str_val);
}

TEST(StringSearchTest, RegularSearch) {
  // Basic Tests
  EXPECT_EQ(0, TestSearch("abcdabcd", "a"));
  EXPECT_EQ(0, TestSearch("abcdabcd", "ab"));
  EXPECT_EQ(2, TestSearch("abcdabcd", "c"));
  EXPECT_EQ(2, TestSearch("abcdabcd", "cd"));
  EXPECT_EQ(-1, TestSearch("", ""));
  EXPECT_EQ(-1, TestSearch("abc", ""));
  EXPECT_EQ(-1, TestSearch("", "a"));

  // Test single chars
  EXPECT_EQ(0, TestSearch("a", "a"));
  EXPECT_EQ(-1, TestSearch("a", "b"));
  EXPECT_EQ(1, TestSearch("abc", "b"));

  // Test searching in a substring of the haystack
  EXPECT_EQ(0, TestSearch("abcabcd", "abc", 5));
  EXPECT_EQ(-1, TestSearch("abcabcd", "abcd", 5));
  EXPECT_EQ(-1, TestSearch("abcabcd", "abcd", 0));

  // Test searching a substring of the needle in a substring of the haystack.
  EXPECT_EQ(0, TestSearch("abcde", "abaaaaaa", 4, 2));
  EXPECT_EQ(-1, TestSearch("abcde", "abaaaaaa", 4, 3));
  EXPECT_EQ(-1, TestSearch("abcdabaaaaa", "abaaaaaa", 4, 3));
  EXPECT_EQ(-1, TestSearch("abcdabaaaaa", "abaaaaaa", 4, 0));
  EXPECT_EQ(-1, TestSearch("abcdabaaaaa", "abaaaaaa"));

  // Test with needle matching the end of the substring.
  EXPECT_EQ(4, TestSearch("abcde", "e"));
  EXPECT_EQ(3, TestSearch("abcde", "de"));
  EXPECT_EQ(2, TestSearch("abcdede", "cde"));
  EXPECT_EQ(5, TestSearch("abcdacde", "cde"));

  // Test correct skip_ handling, which depends on which char of the needle is
  // the same as the last one.
  EXPECT_EQ(2, TestSearch("ababcacac", "abcacac"));
}

TEST(StringSearchTest, ReverseSearch) {
  // Basic Tests
  EXPECT_EQ(4, TestRSearch("abcdabcd", "a"));
  EXPECT_EQ(4, TestRSearch("abcdabcd", "ab"));
  EXPECT_EQ(6, TestRSearch("abcdabcd", "c"));
  EXPECT_EQ(6, TestRSearch("abcdabcd", "cd"));
  EXPECT_EQ(-1, TestRSearch("", ""));
  EXPECT_EQ(-1, TestRSearch("abc", ""));
  EXPECT_EQ(-1, TestRSearch("", "a"));

  // Test single chars
  EXPECT_EQ(0, TestRSearch("a", "a"));
  EXPECT_EQ(-1, TestRSearch("a", "b"));
  EXPECT_EQ(1, TestRSearch("abc", "b"));

  // Test searching in a substring of the haystack
  EXPECT_EQ(0, TestRSearch("abcabcd", "abc", 5));
  EXPECT_EQ(-1, TestRSearch("abcabcd", "abcd", 5));
  EXPECT_EQ(-1, TestRSearch("abcabcd", "abcd", 0));

  // Test searching a substring of the needle in a substring of the haystack.
  EXPECT_EQ(0, TestRSearch("abcde", "abaaaaaa", 4, 2));
  EXPECT_EQ(-1, TestRSearch("abcde", "abaaaaaa", 4, 3));
  EXPECT_EQ(-1, TestRSearch("abcdabaaaaa", "abaaaaaa", 4, 3));
  EXPECT_EQ(-1, TestRSearch("abcdabaaaaa", "abaaaaaa", 4, 0));
  EXPECT_EQ(-1, TestRSearch("abcdabaaaaa", "abaaaaaa"));

  // Test with needle matching the end of the substring.
  EXPECT_EQ(4, TestRSearch("abcde", "e"));
  EXPECT_EQ(3, TestRSearch("abcde", "de"));
  EXPECT_EQ(2, TestRSearch("abcdede", "cde"));
  EXPECT_EQ(5, TestRSearch("abcdacde", "cde"));

  // Test correct rskip_ handling, which depends on which char of the needle is
  // the same as the first one.
  EXPECT_EQ(0, TestRSearch("cacacbaba", "cacacba"));
}
}