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
18using namespace llvm;
19
20/// \returns the number of elements in the substring associated with \p N.
21static 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
29SuffixTree::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
56SuffixTreeNode *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
69SuffixTreeInternalNode *
70SuffixTree::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
86SuffixTreeInternalNode *SuffixTree::insertRoot() {
87 return insertInternalNode(/*Parent = */ nullptr, StartIdx: SuffixTreeNode::EmptyIdx,
88 EndIdx: SuffixTreeNode::EmptyIdx, /*Edge = */ 0);
89}
90
91void 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
161unsigned 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
288void 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