| 1 | //===- llvm/Support/SuffixTree.cpp - Implement Suffix Tree ------*- C++ -*-===// |
| 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 | // This file implements the Suffix Tree class. |
| 10 | // |
| 11 | //===----------------------------------------------------------------------===// |
| 12 | |
| 13 | #include "llvm/Support/SuffixTree.h" |
| 14 | #include "llvm/Support/Allocator.h" |
| 15 | #include "llvm/Support/Casting.h" |
| 16 | #include "llvm/Support/SuffixTreeNode.h" |
| 17 | |
| 18 | using namespace llvm; |
| 19 | |
| 20 | /// \returns the number of elements in the substring associated with \p N. |
| 21 | static size_t numElementsInSubstring(const SuffixTreeNode *N) { |
| 22 | assert(N && "Got a null node?" ); |
| 23 | if (auto *Internal = dyn_cast<SuffixTreeInternalNode>(Val: N)) |
| 24 | if (Internal->isRoot()) |
| 25 | return 0; |
| 26 | return N->getEndIdx() - N->getStartIdx() + 1; |
| 27 | } |
| 28 | |
| 29 | SuffixTree::SuffixTree(const ArrayRef<unsigned> &Str, |
| 30 | bool OutlinerLeafDescendants, |
| 31 | std::optional<unsigned> BoundaryStart) |
| 32 | : Str(Str), OutlinerLeafDescendants(OutlinerLeafDescendants), |
| 33 | BoundaryStart(BoundaryStart) { |
| 34 | Root = insertRoot(); |
| 35 | Active.Node = Root; |
| 36 | |
| 37 | // Keep track of the number of suffixes we have to add of the current |
| 38 | // prefix. |
| 39 | unsigned SuffixesToAdd = 0; |
| 40 | |
| 41 | // Construct the suffix tree iteratively on each prefix of the string. |
| 42 | // PfxEndIdx is the end index of the current prefix. |
| 43 | // End is one past the last element in the string. |
| 44 | for (unsigned PfxEndIdx = 0, End = Str.size(); PfxEndIdx < End; PfxEndIdx++) { |
| 45 | SuffixesToAdd++; |
| 46 | LeafEndIdx = PfxEndIdx; // Extend each of the leaves. |
| 47 | SuffixesToAdd = extend(EndIdx: PfxEndIdx, SuffixesToAdd); |
| 48 | } |
| 49 | |
| 50 | // Collect all leaf nodes of the suffix tree. And for each internal node, |
| 51 | // record the range of leaf nodes that are descendants of it. |
| 52 | if (OutlinerLeafDescendants) |
| 53 | setLeafNodes(); |
| 54 | } |
| 55 | |
| 56 | SuffixTreeNode *SuffixTree::insertLeaf(SuffixTreeInternalNode &Parent, |
| 57 | unsigned StartIdx, unsigned Edge) { |
| 58 | assert(StartIdx <= LeafEndIdx && "String can't start after it ends!" ); |
| 59 | auto *N = new (LeafNodeAllocator.Allocate()) |
| 60 | SuffixTreeLeafNode(StartIdx, &LeafEndIdx); |
| 61 | // The suffix starts Parent.getConcatLen() elements before this edge. |
| 62 | // A later split advances the child's StartIdx by the same length added |
| 63 | // to its parent path, so the suffix start remains unchanged. |
| 64 | N->setSuffixIdx(StartIdx - Parent.getConcatLen()); |
| 65 | Parent.Children[Edge] = N; |
| 66 | return N; |
| 67 | } |
| 68 | |
| 69 | SuffixTreeInternalNode * |
| 70 | SuffixTree::insertInternalNode(SuffixTreeInternalNode *Parent, |
| 71 | unsigned StartIdx, unsigned EndIdx, |
| 72 | unsigned Edge) { |
| 73 | assert(StartIdx <= EndIdx && "String can't start after it ends!" ); |
| 74 | assert(!(!Parent && StartIdx != SuffixTreeNode::EmptyIdx) && |
| 75 | "Non-root internal nodes must have parents!" ); |
| 76 | auto *N = new (InternalNodeAllocator.Allocate()) |
| 77 | SuffixTreeInternalNode(StartIdx, EndIdx, Root); |
| 78 | if (Parent) { |
| 79 | // Path length = parent path length + edge length. |
| 80 | N->setConcatLen(Parent->getConcatLen() + (EndIdx - StartIdx + 1)); |
| 81 | Parent->Children[Edge] = N; |
| 82 | } |
| 83 | return N; |
| 84 | } |
| 85 | |
| 86 | SuffixTreeInternalNode *SuffixTree::insertRoot() { |
| 87 | return insertInternalNode(/*Parent = */ nullptr, StartIdx: SuffixTreeNode::EmptyIdx, |
| 88 | EndIdx: SuffixTreeNode::EmptyIdx, /*Edge = */ 0); |
| 89 | } |
| 90 | |
| 91 | void SuffixTree::setLeafNodes() { |
| 92 | // A stack that keeps track of nodes to visit for post-order DFS traversal. |
| 93 | SmallVector<SuffixTreeNode *> ToVisit; |
| 94 | ToVisit.push_back(Elt: Root); |
| 95 | |
| 96 | // This keeps track of the index of the next leaf node to be added to |
| 97 | // the LeafNodes vector of the suffix tree. |
| 98 | unsigned LeafCounter = 0; |
| 99 | |
| 100 | // This keeps track of nodes whose children have been added to the stack. |
| 101 | // The value is a pair, representing a node's first and last children. |
| 102 | DenseMap<SuffixTreeInternalNode *, |
| 103 | std::pair<SuffixTreeNode *, SuffixTreeNode *>> |
| 104 | ChildrenMap; |
| 105 | |
| 106 | // Traverse the tree in post-order. |
| 107 | while (!ToVisit.empty()) { |
| 108 | SuffixTreeNode *CurrNode = ToVisit.pop_back_val(); |
| 109 | if (auto *CurrInternalNode = dyn_cast<SuffixTreeInternalNode>(Val: CurrNode)) { |
| 110 | // The current node is an internal node. |
| 111 | auto I = ChildrenMap.find(Val: CurrInternalNode); |
| 112 | if (I == ChildrenMap.end()) { |
| 113 | // This is the first time we visit this node. |
| 114 | // Its children have not been added to the stack yet. |
| 115 | // We add current node back, and add its children to the stack. |
| 116 | // We keep track of the first and last children of the current node. |
| 117 | auto J = CurrInternalNode->Children.begin(); |
| 118 | if (J != CurrInternalNode->Children.end()) { |
| 119 | ToVisit.push_back(Elt: CurrNode); |
| 120 | SuffixTreeNode *FirstChild = J->second; |
| 121 | SuffixTreeNode *LastChild = nullptr; |
| 122 | for (; J != CurrInternalNode->Children.end(); ++J) { |
| 123 | LastChild = J->second; |
| 124 | ToVisit.push_back(Elt: LastChild); |
| 125 | } |
| 126 | ChildrenMap[CurrInternalNode] = {FirstChild, LastChild}; |
| 127 | } |
| 128 | } else { |
| 129 | // This is the second time we visit this node. |
| 130 | // All of its children have already been processed. |
| 131 | // With MinLength == 2, pruning can leave empty internal nodes with path |
| 132 | // length 1. Only the root can have such children, so skip computing its |
| 133 | // unused leaf range. |
| 134 | if (CurrInternalNode->isRoot()) |
| 135 | continue; |
| 136 | |
| 137 | // Now, we can set its LeftLeafIdx and RightLeafIdx; |
| 138 | auto [FirstChild, LastChild] = I->second; |
| 139 | // Get the first child to use its RightLeafIdx. |
| 140 | // The first child is the first one added to the stack, so it is |
| 141 | // the last one to be processed. Hence, the leaf descendants |
| 142 | // of the first child are assigned the largest index numbers. |
| 143 | CurrNode->setRightLeafIdx(FirstChild->getRightLeafIdx()); |
| 144 | // Get the last child to use its LeftLeafIdx. |
| 145 | CurrNode->setLeftLeafIdx(LastChild->getLeftLeafIdx()); |
| 146 | assert(CurrNode->getLeftLeafIdx() <= CurrNode->getRightLeafIdx() && |
| 147 | "LeftLeafIdx should not be larger than RightLeafIdx" ); |
| 148 | } |
| 149 | } else { |
| 150 | // The current node is a leaf node. |
| 151 | // We can simply set its LeftLeafIdx and RightLeafIdx. |
| 152 | CurrNode->setLeftLeafIdx(LeafCounter); |
| 153 | CurrNode->setRightLeafIdx(LeafCounter); |
| 154 | ++LeafCounter; |
| 155 | auto *CurrLeafNode = cast<SuffixTreeLeafNode>(Val: CurrNode); |
| 156 | LeafNodes.push_back(x: CurrLeafNode); |
| 157 | } |
| 158 | } |
| 159 | } |
| 160 | |
| 161 | unsigned SuffixTree::extend(unsigned EndIdx, unsigned SuffixesToAdd) { |
| 162 | SuffixTreeInternalNode *NeedsLink = nullptr; |
| 163 | |
| 164 | while (SuffixesToAdd > 0) { |
| 165 | |
| 166 | // Are we waiting to add anything other than just the last character? |
| 167 | if (Active.Len == 0) { |
| 168 | // If not, then say the active index is the end index. |
| 169 | Active.Idx = EndIdx; |
| 170 | } |
| 171 | |
| 172 | assert(Active.Idx <= EndIdx && "Start index can't be after end index!" ); |
| 173 | |
| 174 | // The first character in the current substring we're looking at. |
| 175 | unsigned FirstChar = Str[Active.Idx]; |
| 176 | |
| 177 | // Have we inserted anything starting with FirstChar at the current node? |
| 178 | // Each boundary symbol is unique, so no child has this key. |
| 179 | // Skip the child lookup. |
| 180 | if (auto It = isBoundary(Value: FirstChar) ? Active.Node->Children.end() |
| 181 | : Active.Node->Children.find(Val: FirstChar); |
| 182 | It == Active.Node->Children.end()) { |
| 183 | // If not, then we can just insert a leaf and move to the next step. |
| 184 | // Short boundary leaves cannot contribute to repeated substrings, |
| 185 | // so prune them on paths shorter than MinLength. |
| 186 | if (!isBoundary(Value: FirstChar) || Active.Node->getConcatLen() >= MinLength) |
| 187 | insertLeaf(Parent&: *Active.Node, StartIdx: EndIdx, Edge: FirstChar); |
| 188 | |
| 189 | // The active node is an internal node, and we visited it, so it must |
| 190 | // need a link if it doesn't have one. |
| 191 | if (NeedsLink) { |
| 192 | NeedsLink->setLink(Active.Node); |
| 193 | NeedsLink = nullptr; |
| 194 | } |
| 195 | } else { |
| 196 | // There's a match with FirstChar, so look for the point in the tree to |
| 197 | // insert a new node. |
| 198 | SuffixTreeNode *NextNode = It->second; |
| 199 | |
| 200 | unsigned SubstringLen = numElementsInSubstring(N: NextNode); |
| 201 | |
| 202 | // Is the current suffix we're trying to insert longer than the size of |
| 203 | // the child we want to move to? |
| 204 | if (Active.Len >= SubstringLen) { |
| 205 | // If yes, then consume the characters we've seen and move to the next |
| 206 | // node. |
| 207 | assert(isa<SuffixTreeInternalNode>(NextNode) && |
| 208 | "Expected an internal node?" ); |
| 209 | Active.Idx += SubstringLen; |
| 210 | Active.Len -= SubstringLen; |
| 211 | Active.Node = cast<SuffixTreeInternalNode>(Val: NextNode); |
| 212 | continue; |
| 213 | } |
| 214 | |
| 215 | // Otherwise, the suffix we're trying to insert must be contained in the |
| 216 | // next node we want to move to. |
| 217 | unsigned LastChar = Str[EndIdx]; |
| 218 | |
| 219 | // Is the string we're trying to insert a substring of the next node? |
| 220 | if (Str[NextNode->getStartIdx() + Active.Len] == LastChar) { |
| 221 | // If yes, then we're done for this step. Remember our insertion point |
| 222 | // and move to the next end index. At this point, we have an implicit |
| 223 | // suffix tree. |
| 224 | if (NeedsLink && !Active.Node->isRoot()) { |
| 225 | NeedsLink->setLink(Active.Node); |
| 226 | NeedsLink = nullptr; |
| 227 | } |
| 228 | |
| 229 | Active.Len++; |
| 230 | break; |
| 231 | } |
| 232 | |
| 233 | // The string we're trying to insert isn't a substring of the next node, |
| 234 | // but matches up to a point. Split the node. |
| 235 | // |
| 236 | // For example, say we ended our search at a node n and we're trying to |
| 237 | // insert ABD. Then we'll create a new node s for AB, reduce n to just |
| 238 | // representing C, and insert a new leaf node l to represent d. This |
| 239 | // allows us to ensure that if n was a leaf, it remains a leaf. |
| 240 | // |
| 241 | // | ABC ---split---> | AB |
| 242 | // n s |
| 243 | // C / \ D |
| 244 | // n l |
| 245 | |
| 246 | // The node s from the diagram |
| 247 | SuffixTreeInternalNode *SplitNode = insertInternalNode( |
| 248 | Parent: Active.Node, StartIdx: NextNode->getStartIdx(), |
| 249 | EndIdx: NextNode->getStartIdx() + Active.Len - 1, Edge: FirstChar); |
| 250 | |
| 251 | // Insert the new node representing the new substring into the tree as |
| 252 | // a child of the split node. This is the node l from the diagram. |
| 253 | if (!isBoundary(Value: LastChar) || SplitNode->getConcatLen() >= MinLength) |
| 254 | insertLeaf(Parent&: *SplitNode, StartIdx: EndIdx, Edge: LastChar); |
| 255 | |
| 256 | // Make the old node a child of the split node and update its start |
| 257 | // index. This is the node n from the diagram. |
| 258 | NextNode->incrementStartIdx(Inc: Active.Len); |
| 259 | unsigned Edge = Str[NextNode->getStartIdx()]; |
| 260 | if (!isBoundary(Value: Edge) || SplitNode->getConcatLen() >= MinLength) |
| 261 | SplitNode->Children[Edge] = NextNode; |
| 262 | |
| 263 | // SplitNode is an internal node, update the suffix link. |
| 264 | if (NeedsLink) |
| 265 | NeedsLink->setLink(SplitNode); |
| 266 | |
| 267 | NeedsLink = SplitNode; |
| 268 | } |
| 269 | |
| 270 | // We've added something new to the tree, so there's one less suffix to |
| 271 | // add. |
| 272 | SuffixesToAdd--; |
| 273 | |
| 274 | if (Active.Node->isRoot()) { |
| 275 | if (Active.Len > 0) { |
| 276 | Active.Len--; |
| 277 | Active.Idx = EndIdx - SuffixesToAdd + 1; |
| 278 | } |
| 279 | } else { |
| 280 | // Start the next phase at the next smallest suffix. |
| 281 | Active.Node = Active.Node->getLink(); |
| 282 | } |
| 283 | } |
| 284 | |
| 285 | return SuffixesToAdd; |
| 286 | } |
| 287 | |
| 288 | void SuffixTree::RepeatedSubstringIterator::advance() { |
| 289 | // Clear the current state. If we're at the end of the range, then this |
| 290 | // is the state we want to be in. |
| 291 | RS = RepeatedSubstring(); |
| 292 | N = nullptr; |
| 293 | |
| 294 | // Each leaf node represents a repeat of a string. |
| 295 | SmallVector<unsigned> RepeatedSubstringStarts; |
| 296 | |
| 297 | // Continue visiting nodes until we find one which repeats more than once. |
| 298 | while (!InternalNodesToVisit.empty()) { |
| 299 | RepeatedSubstringStarts.clear(); |
| 300 | auto *Curr = InternalNodesToVisit.pop_back_val(); |
| 301 | |
| 302 | // Keep track of the length of the string associated with the node. If |
| 303 | // it's too short, we'll quit. |
| 304 | unsigned Length = Curr->getConcatLen(); |
| 305 | |
| 306 | // Iterate over each child, saving internal nodes for visiting. |
| 307 | // Internal nodes represent individual strings, which may repeat. |
| 308 | for (auto &ChildPair : Curr->Children) |
| 309 | // Save all of this node's children for processing. |
| 310 | if (auto *InternalChild = |
| 311 | dyn_cast<SuffixTreeInternalNode>(Val: ChildPair.second)) |
| 312 | InternalNodesToVisit.push_back(Elt: InternalChild); |
| 313 | |
| 314 | // If length of repeated substring is below threshold, then skip it. |
| 315 | if (Length < MinLength) |
| 316 | continue; |
| 317 | |
| 318 | // The root never represents a repeated substring. If we're looking at |
| 319 | // that, then skip it. |
| 320 | if (Curr->isRoot()) |
| 321 | continue; |
| 322 | |
| 323 | // Collect leaf children or leaf descendants by OutlinerLeafDescendants. |
| 324 | if (OutlinerLeafDescendants) { |
| 325 | for (unsigned I = Curr->getLeftLeafIdx(); I <= Curr->getRightLeafIdx(); |
| 326 | ++I) |
| 327 | RepeatedSubstringStarts.push_back(Elt: LeafNodes[I]->getSuffixIdx()); |
| 328 | } else { |
| 329 | for (auto &ChildPair : Curr->Children) |
| 330 | if (auto *Leaf = dyn_cast<SuffixTreeLeafNode>(Val: ChildPair.second)) |
| 331 | RepeatedSubstringStarts.push_back(Elt: Leaf->getSuffixIdx()); |
| 332 | } |
| 333 | |
| 334 | // Do we have any repeated substrings? |
| 335 | if (RepeatedSubstringStarts.size() < 2) |
| 336 | continue; |
| 337 | |
| 338 | // Yes. Update the state to reflect this, and then bail out. |
| 339 | N = Curr; |
| 340 | RS.Length = Length; |
| 341 | llvm::append_range(C&: RS.StartIndices, R&: RepeatedSubstringStarts); |
| 342 | break; |
| 343 | } |
| 344 | // At this point, either NewRS is an empty RepeatedSubstring, or it was |
| 345 | // set in the above loop. Similarly, N is either nullptr, or the node |
| 346 | // associated with NewRS. |
| 347 | } |
| 348 | |