llvm/unittests/Support/SuffixTreeTest.cpp

   1 //===- unittests/Support/SuffixTreeTest.cpp - suffix tree 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/Support/SuffixTree.h"
  10 #include "gtest/gtest.h"
  11 #include <vector>
  12
  13 using namespace llvm;
  14
  15 namespace {
  16
  17 // Each example vector has a unique element at the end to represent the end of
  18 // the string
  19
  20 // Tests that The SuffixTree finds a simple repetition of the substring {1, 2}
  21 // {1, 2} twice in the provided string.
  22 TEST(SuffixTreeTest, TestSingleRepetition) {
  23   std::vector<unsigned> SimpleRepetitionData = {1, 2, 1, 2, 3};
  24   SuffixTree ST(SimpleRepetitionData);
  25   std::vector<SuffixTree::RepeatedSubstring> SubStrings;
  26   for (auto It = ST.begin(); It != ST.end(); It++)
  27     SubStrings.push_back(*It);
  28   ASSERT_EQ(SubStrings.size(), 1u);
  29   EXPECT_EQ(SubStrings[0].Length, 2u);
  30   EXPECT_EQ(SubStrings[0].StartIndices.size(), 2u);
  31   for (unsigned StartIdx : SubStrings[0].StartIndices) {
  32     EXPECT_EQ(SimpleRepetitionData[StartIdx], 1u);
  33     EXPECT_EQ(SimpleRepetitionData[StartIdx + 1], 2u);
  34   }
  35 }
  36
  37 // Tests that the SuffixTree is able to find the substrings {1, 2, 3} at
  38 // at indices 0 and 3 as well as the substrings {2, 3} at indices 1 and 4.
  39 // This test also serves as a flag for improvements to the suffix tree.
  40 //
  41 // FIXME: Right now, the longest repeated substring from a specific index is
  42 // returned, this could be improved to return the longest repeated substring, as
  43 // well as those that are smaller.
  44 TEST(SuffixTreeTest, TestLongerRepetition) {
  45   std::vector<unsigned> RepeatedRepetitionData = {1, 2, 3, 1, 2, 3, 4};
  46   SuffixTree ST(RepeatedRepetitionData);
  47   std::vector<SuffixTree::RepeatedSubstring> SubStrings;
  48   for (auto It = ST.begin(); It != ST.end(); It++)
  49     SubStrings.push_back(*It);
  50   EXPECT_EQ(SubStrings.size(), 2u);
  51   unsigned Len;
  52   for (SuffixTree::RepeatedSubstring &RS : SubStrings) {
  53     Len = RS.Length;
  54     bool IsExpectedLen = (Len == 3u || Len == 2u);
  55     bool IsExpectedIndex;
  56     ASSERT_TRUE(IsExpectedLen);
  57
  58     if (Len == 3u) {
  59       for (unsigned StartIdx : RS.StartIndices) {
  60         IsExpectedIndex = (StartIdx == 0u || StartIdx == 3u);
  61         EXPECT_TRUE(IsExpectedIndex);
  62         EXPECT_EQ(RepeatedRepetitionData[StartIdx], 1u);
  63         EXPECT_EQ(RepeatedRepetitionData[StartIdx + 1], 2u);
  64         EXPECT_EQ(RepeatedRepetitionData[StartIdx + 2], 3u);
  65       }
  66     } else {
  67       for (unsigned StartIdx : RS.StartIndices) {
  68         IsExpectedIndex = (StartIdx == 1u || StartIdx == 4u);
  69         EXPECT_TRUE(IsExpectedIndex);
  70         EXPECT_EQ(RepeatedRepetitionData[StartIdx], 2u);
  71         EXPECT_EQ(RepeatedRepetitionData[StartIdx + 1], 3u);
  72       }
  73     }
  74   }
  75 }
  76
  77 // Tests that the SuffixTree is able to find substring {1, 1, 1, 1, 1} at
  78 // indices 0 and 1.
  79 //
  80 // FIXME: Add support for detecting {1, 1} and {1, 1, 1}
  81 TEST(SuffixTreeTest, TestSingleCharacterRepeat) {
  82   std::vector<unsigned> RepeatedRepetitionData = {1, 1, 1, 1, 1, 1, 2};
  83   std::vector<unsigned>::iterator RRDIt, RRDIt2;
  84   SuffixTree ST(RepeatedRepetitionData);
  85   std::vector<SuffixTree::RepeatedSubstring> SubStrings;
  86   for (auto It = ST.begin(); It != ST.end(); It++)
  87     SubStrings.push_back(*It);
  88   EXPECT_EQ(SubStrings.size(), 1u);
  89   for (SuffixTree::RepeatedSubstring &RS : SubStrings) {
  90     EXPECT_EQ(RS.StartIndices.size(),
  91               RepeatedRepetitionData.size() - RS.Length);
  92     for (unsigned StartIdx : SubStrings[0].StartIndices) {
  93       RRDIt = RRDIt2 = RepeatedRepetitionData.begin();
  94       std::advance(RRDIt, StartIdx);
  95       std::advance(RRDIt2, StartIdx + SubStrings[0].Length);
  96       ASSERT_TRUE(
  97           all_of(make_range<std::vector<unsigned>::iterator>(RRDIt, RRDIt2),
  98                  [](unsigned Elt) { return Elt == 1; }));
  99     }
 100   }
 101 }
 102
 103 // The suffix tree cannot currently find repeated substrings in strings of the
 104 // form {1, 2, 3, 1, 2, 3}, because the two {1, 2, 3}s are adjacent ("tandem
 105 // repeats")
 106 //
 107 // FIXME: Teach the SuffixTree to recognize these cases.
 108 TEST(SuffixTreeTest, TestTandemRepeat) {
 109   std::vector<unsigned> RepeatedRepetitionData = {1, 2, 3, 1, 2, 3};
 110   SuffixTree ST(RepeatedRepetitionData);
 111   std::vector<SuffixTree::RepeatedSubstring> SubStrings;
 112   for (auto It = ST.begin(); It != ST.end(); It++)
 113     SubStrings.push_back(*It);
 114   EXPECT_EQ(SubStrings.size(), 0u);
 115 }
 116
 117 // Tests that the SuffixTree does not erroneously include values that are not
 118 // in repeated substrings.  That is, only finds {1, 1} at indices 0 and 3 and
 119 // does not include 2 and 3.
 120 TEST(SuffixTreeTest, TestExclusion) {
 121   std::vector<unsigned> RepeatedRepetitionData = {1, 1, 2, 1, 1, 3};
 122   std::vector<unsigned>::iterator RRDIt, RRDIt2;
 123   SuffixTree ST(RepeatedRepetitionData);
 124   std::vector<SuffixTree::RepeatedSubstring> SubStrings;
 125   for (auto It = ST.begin(); It != ST.end(); It++)
 126     SubStrings.push_back(*It);
 127   EXPECT_EQ(SubStrings.size(), 1u);
 128   bool IsExpectedIndex;
 129   for (SuffixTree::RepeatedSubstring &RS : SubStrings) {
 130     for (unsigned StartIdx : RS.StartIndices) {
 131       IsExpectedIndex = (StartIdx == 0u || StartIdx == 3u);
 132       EXPECT_TRUE(IsExpectedIndex);
 133       RRDIt = RRDIt2 = RepeatedRepetitionData.begin();
 134       std::advance(RRDIt, StartIdx);
 135       std::advance(RRDIt2, StartIdx + RS.Length);
 136       EXPECT_TRUE(
 137           all_of(make_range<std::vector<unsigned>::iterator>(RRDIt, RRDIt2),
 138                  [](unsigned Elt) { return Elt == 1; }));
 139     }
 140   }
 141 }
 142
 143 } // namespace