| //===- llvm/ADT/SuffixTree.h - Tree for substrings --------------*- C++ -*-===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file defines the Suffix Tree class and Suffix Tree Node struct. |
| // |
| //===----------------------------------------------------------------------===// |
| #ifndef LLVM_SUPPORT_SUFFIXTREE_H |
| #define LLVM_SUPPORT_SUFFIXTREE_H |
| |
| #include "llvm/ADT/ArrayRef.h" |
| #include "llvm/ADT/DenseMap.h" |
| #include "llvm/Support/Allocator.h" |
| #include <vector> |
| |
| namespace llvm { |
| |
| /// Represents an undefined index in the suffix tree. |
| const unsigned EmptyIdx = -1; |
| |
| /// A node in a suffix tree which represents a substring or suffix. |
| /// |
| /// Each node has either no children or at least two children, with the root |
| /// being a exception in the empty tree. |
| /// |
| /// Children are represented as a map between unsigned integers and nodes. If |
| /// a node N has a child M on unsigned integer k, then the mapping represented |
| /// by N is a proper prefix of the mapping represented by M. Note that this, |
| /// although similar to a trie is somewhat different: each node stores a full |
| /// substring of the full mapping rather than a single character state. |
| /// |
| /// Each internal node contains a pointer to the internal node representing |
| /// the same string, but with the first character chopped off. This is stored |
| /// in \p Link. Each leaf node stores the start index of its respective |
| /// suffix in \p SuffixIdx. |
| struct SuffixTreeNode { |
| |
| /// The children of this node. |
| /// |
| /// A child existing on an unsigned integer implies that from the mapping |
| /// represented by the current node, there is a way to reach another |
| /// mapping by tacking that character on the end of the current string. |
| llvm::DenseMap<unsigned, SuffixTreeNode *> Children; |
| |
| /// The start index of this node's substring in the main string. |
| unsigned StartIdx = EmptyIdx; |
| |
| /// The end index of this node's substring in the main string. |
| /// |
| /// Every leaf node must have its \p EndIdx incremented at the end of every |
| /// step in the construction algorithm. To avoid having to update O(N) |
| /// nodes individually at the end of every step, the end index is stored |
| /// as a pointer. |
| unsigned *EndIdx = nullptr; |
| |
| /// For leaves, the start index of the suffix represented by this node. |
| /// |
| /// For all other nodes, this is ignored. |
| unsigned SuffixIdx = EmptyIdx; |
| |
| /// For internal nodes, a pointer to the internal node representing |
| /// the same sequence with the first character chopped off. |
| /// |
| /// This acts as a shortcut in Ukkonen's algorithm. One of the things that |
| /// Ukkonen's algorithm does to achieve linear-time construction is |
| /// keep track of which node the next insert should be at. This makes each |
| /// insert O(1), and there are a total of O(N) inserts. The suffix link |
| /// helps with inserting children of internal nodes. |
| /// |
| /// Say we add a child to an internal node with associated mapping S. The |
| /// next insertion must be at the node representing S - its first character. |
| /// This is given by the way that we iteratively build the tree in Ukkonen's |
| /// algorithm. The main idea is to look at the suffixes of each prefix in the |
| /// string, starting with the longest suffix of the prefix, and ending with |
| /// the shortest. Therefore, if we keep pointers between such nodes, we can |
| /// move to the next insertion point in O(1) time. If we don't, then we'd |
| /// have to query from the root, which takes O(N) time. This would make the |
| /// construction algorithm O(N^2) rather than O(N). |
| SuffixTreeNode *Link = nullptr; |
| |
| /// The length of the string formed by concatenating the edge labels from the |
| /// root to this node. |
| unsigned ConcatLen = 0; |
| |
| /// Returns true if this node is a leaf. |
| bool isLeaf() const { return SuffixIdx != EmptyIdx; } |
| |
| /// Returns true if this node is the root of its owning \p SuffixTree. |
| bool isRoot() const { return StartIdx == EmptyIdx; } |
| |
| /// Return the number of elements in the substring associated with this node. |
| size_t size() const { |
| |
| // Is it the root? If so, it's the empty string so return 0. |
| if (isRoot()) |
| return 0; |
| |
| assert(*EndIdx != EmptyIdx && "EndIdx is undefined!"); |
| |
| // Size = the number of elements in the string. |
| // For example, [0 1 2 3] has length 4, not 3. 3-0 = 3, so we have 3-0+1. |
| return *EndIdx - StartIdx + 1; |
| } |
| |
| SuffixTreeNode(unsigned StartIdx, unsigned *EndIdx, SuffixTreeNode *Link) |
| : StartIdx(StartIdx), EndIdx(EndIdx), Link(Link) {} |
| |
| SuffixTreeNode() {} |
| }; |
| |
| /// A data structure for fast substring queries. |
| /// |
| /// Suffix trees represent the suffixes of their input strings in their leaves. |
| /// A suffix tree is a type of compressed trie structure where each node |
| /// represents an entire substring rather than a single character. Each leaf |
| /// of the tree is a suffix. |
| /// |
| /// A suffix tree can be seen as a type of state machine where each state is a |
| /// substring of the full string. The tree is structured so that, for a string |
| /// of length N, there are exactly N leaves in the tree. This structure allows |
| /// us to quickly find repeated substrings of the input string. |
| /// |
| /// In this implementation, a "string" is a vector of unsigned integers. |
| /// These integers may result from hashing some data type. A suffix tree can |
| /// contain 1 or many strings, which can then be queried as one large string. |
| /// |
| /// The suffix tree is implemented using Ukkonen's algorithm for linear-time |
| /// suffix tree construction. Ukkonen's algorithm is explained in more detail |
| /// in the paper by Esko Ukkonen "On-line construction of suffix trees. The |
| /// paper is available at |
| /// |
| /// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf |
| class SuffixTree { |
| public: |
| /// Each element is an integer representing an instruction in the module. |
| llvm::ArrayRef<unsigned> Str; |
| |
| /// A repeated substring in the tree. |
| struct RepeatedSubstring { |
| /// The length of the string. |
| unsigned Length; |
| |
| /// The start indices of each occurrence. |
| std::vector<unsigned> StartIndices; |
| }; |
| |
| private: |
| /// Maintains each node in the tree. |
| llvm::SpecificBumpPtrAllocator<SuffixTreeNode> NodeAllocator; |
| |
| /// The root of the suffix tree. |
| /// |
| /// The root represents the empty string. It is maintained by the |
| /// \p NodeAllocator like every other node in the tree. |
| SuffixTreeNode *Root = nullptr; |
| |
| /// Maintains the end indices of the internal nodes in the tree. |
| /// |
| /// Each internal node is guaranteed to never have its end index change |
| /// during the construction algorithm; however, leaves must be updated at |
| /// every step. Therefore, we need to store leaf end indices by reference |
| /// to avoid updating O(N) leaves at every step of construction. Thus, |
| /// every internal node must be allocated its own end index. |
| llvm::BumpPtrAllocator InternalEndIdxAllocator; |
| |
| /// The end index of each leaf in the tree. |
| unsigned LeafEndIdx = -1; |
| |
| /// Helper struct which keeps track of the next insertion point in |
| /// Ukkonen's algorithm. |
| struct ActiveState { |
| /// The next node to insert at. |
| SuffixTreeNode *Node = nullptr; |
| |
| /// The index of the first character in the substring currently being added. |
| unsigned Idx = EmptyIdx; |
| |
| /// The length of the substring we have to add at the current step. |
| unsigned Len = 0; |
| }; |
| |
| /// The point the next insertion will take place at in the |
| /// construction algorithm. |
| ActiveState Active; |
| |
| /// Allocate a leaf node and add it to the tree. |
| /// |
| /// \param Parent The parent of this node. |
| /// \param StartIdx The start index of this node's associated string. |
| /// \param Edge The label on the edge leaving \p Parent to this node. |
| /// |
| /// \returns A pointer to the allocated leaf node. |
| SuffixTreeNode *insertLeaf(SuffixTreeNode &Parent, unsigned StartIdx, |
| unsigned Edge); |
| |
| /// Allocate an internal node and add it to the tree. |
| /// |
| /// \param Parent The parent of this node. Only null when allocating the root. |
| /// \param StartIdx The start index of this node's associated string. |
| /// \param EndIdx The end index of this node's associated string. |
| /// \param Edge The label on the edge leaving \p Parent to this node. |
| /// |
| /// \returns A pointer to the allocated internal node. |
| SuffixTreeNode *insertInternalNode(SuffixTreeNode *Parent, unsigned StartIdx, |
| unsigned EndIdx, unsigned Edge); |
| |
| /// Set the suffix indices of the leaves to the start indices of their |
| /// respective suffixes. |
| void setSuffixIndices(); |
| |
| /// Construct the suffix tree for the prefix of the input ending at |
| /// \p EndIdx. |
| /// |
| /// Used to construct the full suffix tree iteratively. At the end of each |
| /// step, the constructed suffix tree is either a valid suffix tree, or a |
| /// suffix tree with implicit suffixes. At the end of the final step, the |
| /// suffix tree is a valid tree. |
| /// |
| /// \param EndIdx The end index of the current prefix in the main string. |
| /// \param SuffixesToAdd The number of suffixes that must be added |
| /// to complete the suffix tree at the current phase. |
| /// |
| /// \returns The number of suffixes that have not been added at the end of |
| /// this step. |
| unsigned extend(unsigned EndIdx, unsigned SuffixesToAdd); |
| |
| public: |
| /// Construct a suffix tree from a sequence of unsigned integers. |
| /// |
| /// \param Str The string to construct the suffix tree for. |
| SuffixTree(const std::vector<unsigned> &Str); |
| |
| /// Iterator for finding all repeated substrings in the suffix tree. |
| struct RepeatedSubstringIterator { |
| private: |
| /// The current node we're visiting. |
| SuffixTreeNode *N = nullptr; |
| |
| /// The repeated substring associated with this node. |
| RepeatedSubstring RS; |
| |
| /// The nodes left to visit. |
| std::vector<SuffixTreeNode *> ToVisit; |
| |
| /// The minimum length of a repeated substring to find. |
| /// Since we're outlining, we want at least two instructions in the range. |
| /// FIXME: This may not be true for targets like X86 which support many |
| /// instruction lengths. |
| const unsigned MinLength = 2; |
| |
| /// Move the iterator to the next repeated substring. |
| void advance() { |
| // Clear the current state. If we're at the end of the range, then this |
| // is the state we want to be in. |
| RS = RepeatedSubstring(); |
| N = nullptr; |
| |
| // Each leaf node represents a repeat of a string. |
| std::vector<SuffixTreeNode *> LeafChildren; |
| |
| // Continue visiting nodes until we find one which repeats more than once. |
| while (!ToVisit.empty()) { |
| SuffixTreeNode *Curr = ToVisit.back(); |
| ToVisit.pop_back(); |
| LeafChildren.clear(); |
| |
| // Keep track of the length of the string associated with the node. If |
| // it's too short, we'll quit. |
| unsigned Length = Curr->ConcatLen; |
| |
| // Iterate over each child, saving internal nodes for visiting, and |
| // leaf nodes in LeafChildren. Internal nodes represent individual |
| // strings, which may repeat. |
| for (auto &ChildPair : Curr->Children) { |
| // Save all of this node's children for processing. |
| if (!ChildPair.second->isLeaf()) |
| ToVisit.push_back(ChildPair.second); |
| |
| // It's not an internal node, so it must be a leaf. If we have a |
| // long enough string, then save the leaf children. |
| else if (Length >= MinLength) |
| LeafChildren.push_back(ChildPair.second); |
| } |
| |
| // The root never represents a repeated substring. If we're looking at |
| // that, then skip it. |
| if (Curr->isRoot()) |
| continue; |
| |
| // Do we have any repeated substrings? |
| if (LeafChildren.size() >= 2) { |
| // Yes. Update the state to reflect this, and then bail out. |
| N = Curr; |
| RS.Length = Length; |
| for (SuffixTreeNode *Leaf : LeafChildren) |
| RS.StartIndices.push_back(Leaf->SuffixIdx); |
| break; |
| } |
| } |
| |
| // At this point, either NewRS is an empty RepeatedSubstring, or it was |
| // set in the above loop. Similarly, N is either nullptr, or the node |
| // associated with NewRS. |
| } |
| |
| public: |
| /// Return the current repeated substring. |
| RepeatedSubstring &operator*() { return RS; } |
| |
| RepeatedSubstringIterator &operator++() { |
| advance(); |
| return *this; |
| } |
| |
| RepeatedSubstringIterator operator++(int I) { |
| RepeatedSubstringIterator It(*this); |
| advance(); |
| return It; |
| } |
| |
| bool operator==(const RepeatedSubstringIterator &Other) const { |
| return N == Other.N; |
| } |
| bool operator!=(const RepeatedSubstringIterator &Other) const { |
| return !(*this == Other); |
| } |
| |
| RepeatedSubstringIterator(SuffixTreeNode *N) : N(N) { |
| // Do we have a non-null node? |
| if (N) { |
| // Yes. At the first step, we need to visit all of N's children. |
| // Note: This means that we visit N last. |
| ToVisit.push_back(N); |
| advance(); |
| } |
| } |
| }; |
| |
| typedef RepeatedSubstringIterator iterator; |
| iterator begin() { return iterator(Root); } |
| iterator end() { return iterator(nullptr); } |
| }; |
| |
| } // namespace llvm |
| |
| #endif // LLVM_SUPPORT_SUFFIXTREE_H |