278 lines · 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-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/Support/SuffixTree.h"10#include "gtest/gtest.h"11#include <vector>12 13using namespace llvm;14 15namespace {16 17// Each example vector has a unique element at the end to represent the end of18// the string19 20// Tests that The SuffixTree finds a simple repetition of the substring {1, 2}21// {1, 2} twice in the provided string.22TEST(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} at38// 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 is42// returned, this could be improved to return the longest repeated substring, as43// well as those that are smaller.44TEST(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} at78// indices 0 and 1.79//80// FIXME: Add support for detecting {1, 1} and {1, 1, 1}81// See Test TestSingleCharacterRepeatWithLeafDescendants for the fix82TEST(SuffixTreeTest, TestSingleCharacterRepeat) {83 std::vector<unsigned> RepeatedRepetitionData = {1, 1, 1, 1, 1, 1, 2};84 std::vector<unsigned>::iterator RRDIt, RRDIt2;85 SuffixTree ST(RepeatedRepetitionData);86 std::vector<SuffixTree::RepeatedSubstring> SubStrings;87 for (auto It = ST.begin(); It != ST.end(); It++)88 SubStrings.push_back(*It);89 EXPECT_EQ(SubStrings.size(), 1u);90 for (SuffixTree::RepeatedSubstring &RS : SubStrings) {91 EXPECT_EQ(RS.StartIndices.size(),92 RepeatedRepetitionData.size() - RS.Length);93 for (unsigned StartIdx : SubStrings[0].StartIndices) {94 RRDIt = RRDIt2 = RepeatedRepetitionData.begin();95 std::advance(RRDIt, StartIdx);96 std::advance(RRDIt2, StartIdx + SubStrings[0].Length);97 ASSERT_TRUE(98 all_of(make_range<std::vector<unsigned>::iterator>(RRDIt, RRDIt2),99 [](unsigned Elt) { return Elt == 1; }));100 }101 }102}103 104// Tests that the SuffixTree is able to find the following substrings:105// {1, 1} at indices 0, 1, 2, 3, and 4;106// {1, 1, 1} at indices 0, 1, 2, and 3;107// {1, 1, 1, 1} at indices 0, 1, and 2; and108// {1, 1, 1, 1, 1} at indices 0 and 1.109//110// This is the fix for TestSingleCharacterRepeat.111TEST(SuffixTreeTest, TestSingleCharacterRepeatWithLeafDescendants) {112 std::vector<unsigned> RepeatedRepetitionData = {1, 1, 1, 1, 1, 1, 2};113 std::vector<unsigned>::iterator RRDIt, RRDIt2;114 SuffixTree ST(RepeatedRepetitionData, /*OutlinerLeafDescendants=*/true);115 std::vector<SuffixTree::RepeatedSubstring> SubStrings;116 for (auto It = ST.begin(); It != ST.end(); It++)117 SubStrings.push_back(*It);118 EXPECT_EQ(SubStrings.size(), 4u);119 for (SuffixTree::RepeatedSubstring &RS : SubStrings) {120 EXPECT_EQ(RS.StartIndices.size(),121 RepeatedRepetitionData.size() - RS.Length);122 for (unsigned StartIdx : SubStrings[0].StartIndices) {123 RRDIt = RRDIt2 = RepeatedRepetitionData.begin();124 std::advance(RRDIt, StartIdx);125 std::advance(RRDIt2, StartIdx + SubStrings[0].Length);126 ASSERT_TRUE(127 all_of(make_range<std::vector<unsigned>::iterator>(RRDIt, RRDIt2),128 [](unsigned Elt) { return Elt == 1; }));129 }130 }131}132 133// The suffix tree cannot currently find repeated substrings in strings of the134// form {1, 2, 3, 1, 2, 3}, because the two {1, 2, 3}s are adjacent ("tandem135// repeats")136//137// FIXME: Teach the SuffixTree to recognize these cases.138TEST(SuffixTreeTest, TestTandemRepeat) {139 std::vector<unsigned> RepeatedRepetitionData = {1, 2, 3, 1, 2, 3};140 SuffixTree ST(RepeatedRepetitionData);141 std::vector<SuffixTree::RepeatedSubstring> SubStrings;142 for (auto It = ST.begin(); It != ST.end(); It++)143 SubStrings.push_back(*It);144 EXPECT_EQ(SubStrings.size(), 0u);145}146 147// Tests that the SuffixTree does not erroneously include values that are not148// in repeated substrings. That is, only finds {1, 1} at indices 0 and 3 and149// does not include 2 and 3.150TEST(SuffixTreeTest, TestExclusion) {151 std::vector<unsigned> RepeatedRepetitionData = {1, 1, 2, 1, 1, 3};152 std::vector<unsigned>::iterator RRDIt, RRDIt2;153 SuffixTree ST(RepeatedRepetitionData);154 std::vector<SuffixTree::RepeatedSubstring> SubStrings;155 for (auto It = ST.begin(); It != ST.end(); It++)156 SubStrings.push_back(*It);157 EXPECT_EQ(SubStrings.size(), 1u);158 bool IsExpectedIndex;159 for (SuffixTree::RepeatedSubstring &RS : SubStrings) {160 for (unsigned StartIdx : RS.StartIndices) {161 IsExpectedIndex = (StartIdx == 0u || StartIdx == 3u);162 EXPECT_TRUE(IsExpectedIndex);163 RRDIt = RRDIt2 = RepeatedRepetitionData.begin();164 std::advance(RRDIt, StartIdx);165 std::advance(RRDIt2, StartIdx + RS.Length);166 EXPECT_TRUE(167 all_of(make_range<std::vector<unsigned>::iterator>(RRDIt, RRDIt2),168 [](unsigned Elt) { return Elt == 1; }));169 }170 }171}172 173// Tests that the SuffixTree is able to find three substrings174// {1, 2, 3} at indices 6 and 10;175// {2, 3} at indices 7 and 11; and176// {1, 2} at indicies 0 and 3.177//178// FIXME: {1, 2} has indices 6 and 10 missing as it is a substring of {1, 2, 3}179// See Test TestSubstringRepeatsWithLeafDescendants for the fix180TEST(SuffixTreeTest, TestSubstringRepeats) {181 std::vector<unsigned> RepeatedRepetitionData = {1, 2, 100, 1, 2, 101, 1,182 2, 3, 103, 1, 2, 3, 104};183 SuffixTree ST(RepeatedRepetitionData);184 std::vector<SuffixTree::RepeatedSubstring> SubStrings;185 for (auto It = ST.begin(); It != ST.end(); It++)186 SubStrings.push_back(*It);187 EXPECT_EQ(SubStrings.size(), 3u);188 unsigned Len;189 for (SuffixTree::RepeatedSubstring &RS : SubStrings) {190 Len = RS.Length;191 bool IsExpectedLen = (Len == 3u || Len == 2u);192 ASSERT_TRUE(IsExpectedLen);193 bool IsExpectedIndex;194 195 if (Len == 3u) { // {1, 2, 3}196 EXPECT_EQ(RS.StartIndices.size(), 2u);197 for (unsigned StartIdx : RS.StartIndices) {198 IsExpectedIndex = (StartIdx == 6u || StartIdx == 10u);199 EXPECT_TRUE(IsExpectedIndex);200 EXPECT_EQ(RepeatedRepetitionData[StartIdx], 1u);201 EXPECT_EQ(RepeatedRepetitionData[StartIdx + 1], 2u);202 EXPECT_EQ(RepeatedRepetitionData[StartIdx + 2], 3u);203 }204 } else {205 if (RepeatedRepetitionData[RS.StartIndices[0]] == 1u) { // {1, 2}206 EXPECT_EQ(RS.StartIndices.size(), 2u);207 for (unsigned StartIdx : RS.StartIndices) {208 IsExpectedIndex = (StartIdx == 0u || StartIdx == 3u);209 EXPECT_TRUE(IsExpectedIndex);210 EXPECT_EQ(RepeatedRepetitionData[StartIdx + 1], 2u);211 }212 } else { // {2, 3}213 EXPECT_EQ(RS.StartIndices.size(), 2u);214 for (unsigned StartIdx : RS.StartIndices) {215 IsExpectedIndex = (StartIdx == 7u || StartIdx == 11u);216 EXPECT_TRUE(IsExpectedIndex);217 EXPECT_EQ(RepeatedRepetitionData[StartIdx], 2u);218 EXPECT_EQ(RepeatedRepetitionData[StartIdx + 1], 3u);219 }220 }221 }222 }223}224 225// Tests that the SuffixTree is able to find three substrings226// {1, 2, 3} at indices 6 and 10;227// {2, 3} at indices 7 and 11; and228// {1, 2} at indicies 0, 3, 6, and 10.229//230// This is the fix for TestSubstringRepeats231TEST(SuffixTreeTest, TestSubstringRepeatsWithLeafDescendants) {232 std::vector<unsigned> RepeatedRepetitionData = {1, 2, 100, 1, 2, 101, 1,233 2, 3, 103, 1, 2, 3, 104};234 SuffixTree ST(RepeatedRepetitionData, /*OutlinerLeafDescendants=*/true);235 std::vector<SuffixTree::RepeatedSubstring> SubStrings;236 for (auto It = ST.begin(); It != ST.end(); It++)237 SubStrings.push_back(*It);238 EXPECT_EQ(SubStrings.size(), 3u);239 unsigned Len;240 for (SuffixTree::RepeatedSubstring &RS : SubStrings) {241 Len = RS.Length;242 bool IsExpectedLen = (Len == 3u || Len == 2u);243 ASSERT_TRUE(IsExpectedLen);244 bool IsExpectedIndex;245 246 if (Len == 3u) { // {1, 2, 3}247 EXPECT_EQ(RS.StartIndices.size(), 2u);248 for (unsigned StartIdx : RS.StartIndices) {249 IsExpectedIndex = (StartIdx == 6u || StartIdx == 10u);250 EXPECT_TRUE(IsExpectedIndex);251 EXPECT_EQ(RepeatedRepetitionData[StartIdx], 1u);252 EXPECT_EQ(RepeatedRepetitionData[StartIdx + 1], 2u);253 EXPECT_EQ(RepeatedRepetitionData[StartIdx + 2], 3u);254 }255 } else {256 if (RepeatedRepetitionData[RS.StartIndices[0]] == 1u) { // {1, 2}257 EXPECT_EQ(RS.StartIndices.size(), 4u);258 for (unsigned StartIdx : RS.StartIndices) {259 IsExpectedIndex = (StartIdx == 0u || StartIdx == 3u ||260 StartIdx == 6u || StartIdx == 10u);261 EXPECT_TRUE(IsExpectedIndex);262 EXPECT_EQ(RepeatedRepetitionData[StartIdx + 1], 2u);263 }264 } else { // {2, 3}265 EXPECT_EQ(RS.StartIndices.size(), 2u);266 for (unsigned StartIdx : RS.StartIndices) {267 IsExpectedIndex = (StartIdx == 7u || StartIdx == 11u);268 EXPECT_TRUE(IsExpectedIndex);269 EXPECT_EQ(RepeatedRepetitionData[StartIdx], 2u);270 EXPECT_EQ(RepeatedRepetitionData[StartIdx + 1], 3u);271 }272 }273 }274 }275}276 277} // namespace278