head 1.1; branch 1.1.1; access; symbols netbsd-11-0-RC4:1.1.1.5 netbsd-11-0-RC3:1.1.1.5 netbsd-11-0-RC2:1.1.1.5 netbsd-11-0-RC1:1.1.1.5 perseant-exfatfs-base-20250801:1.1.1.5 netbsd-11:1.1.1.5.0.10 netbsd-11-base:1.1.1.5 netbsd-10-1-RELEASE:1.1.1.5 perseant-exfatfs-base-20240630:1.1.1.5 perseant-exfatfs:1.1.1.5.0.8 perseant-exfatfs-base:1.1.1.5 netbsd-8-3-RELEASE:1.1.1.3 netbsd-9-4-RELEASE:1.1.1.4 netbsd-10-0-RELEASE:1.1.1.5 netbsd-10-0-RC6:1.1.1.5 netbsd-10-0-RC5:1.1.1.5 netbsd-10-0-RC4:1.1.1.5 netbsd-10-0-RC3:1.1.1.5 netbsd-10-0-RC2:1.1.1.5 netbsd-10-0-RC1:1.1.1.5 netbsd-10:1.1.1.5.0.6 netbsd-10-base:1.1.1.5 netbsd-9-3-RELEASE:1.1.1.4 cjep_sun2x:1.1.1.5.0.4 cjep_sun2x-base:1.1.1.5 cjep_staticlib_x-base1:1.1.1.5 netbsd-9-2-RELEASE:1.1.1.4 cjep_staticlib_x:1.1.1.5.0.2 cjep_staticlib_x-base:1.1.1.5 netbsd-9-1-RELEASE:1.1.1.4 phil-wifi-20200421:1.1.1.5 phil-wifi-20200411:1.1.1.5 phil-wifi-20200406:1.1.1.5 netbsd-8-2-RELEASE:1.1.1.3 netbsd-9-0-RELEASE:1.1.1.4 netbsd-9-0-RC2:1.1.1.4 netbsd-9-0-RC1:1.1.1.4 netbsd-9:1.1.1.4.0.2 netbsd-9-base:1.1.1.4 phil-wifi-20190609:1.1.1.4 netbsd-8-1-RELEASE:1.1.1.3 netbsd-8-1-RC1:1.1.1.3 pgoyette-compat-merge-20190127:1.1.1.3.14.1 pgoyette-compat-20190127:1.1.1.4 pgoyette-compat-20190118:1.1.1.4 pgoyette-compat-1226:1.1.1.4 pgoyette-compat-1126:1.1.1.4 pgoyette-compat-1020:1.1.1.4 pgoyette-compat-0930:1.1.1.4 pgoyette-compat-0906:1.1.1.4 netbsd-7-2-RELEASE:1.1.1.2 pgoyette-compat-0728:1.1.1.4 clang-337282:1.1.1.4 netbsd-8-0-RELEASE:1.1.1.3 phil-wifi:1.1.1.3.0.16 phil-wifi-base:1.1.1.3 pgoyette-compat-0625:1.1.1.3 netbsd-8-0-RC2:1.1.1.3 pgoyette-compat-0521:1.1.1.3 pgoyette-compat-0502:1.1.1.3 pgoyette-compat-0422:1.1.1.3 netbsd-8-0-RC1:1.1.1.3 pgoyette-compat-0415:1.1.1.3 pgoyette-compat-0407:1.1.1.3 pgoyette-compat-0330:1.1.1.3 pgoyette-compat-0322:1.1.1.3 pgoyette-compat-0315:1.1.1.3 netbsd-7-1-2-RELEASE:1.1.1.2 pgoyette-compat:1.1.1.3.0.14 pgoyette-compat-base:1.1.1.3 netbsd-7-1-1-RELEASE:1.1.1.2 clang-319952:1.1.1.3 matt-nb8-mediatek:1.1.1.3.0.12 matt-nb8-mediatek-base:1.1.1.3 clang-309604:1.1.1.3 perseant-stdc-iso10646:1.1.1.3.0.10 perseant-stdc-iso10646-base:1.1.1.3 netbsd-8:1.1.1.3.0.8 netbsd-8-base:1.1.1.3 prg-localcount2-base3:1.1.1.3 prg-localcount2-base2:1.1.1.3 prg-localcount2-base1:1.1.1.3 prg-localcount2:1.1.1.3.0.6 prg-localcount2-base:1.1.1.3 pgoyette-localcount-20170426:1.1.1.3 bouyer-socketcan-base1:1.1.1.3 pgoyette-localcount-20170320:1.1.1.3 netbsd-7-1:1.1.1.2.0.10 netbsd-7-1-RELEASE:1.1.1.2 netbsd-7-1-RC2:1.1.1.2 clang-294123:1.1.1.3 netbsd-7-nhusb-base-20170116:1.1.1.2 bouyer-socketcan:1.1.1.3.0.4 bouyer-socketcan-base:1.1.1.3 clang-291444:1.1.1.3 pgoyette-localcount-20170107:1.1.1.3 netbsd-7-1-RC1:1.1.1.2 pgoyette-localcount-20161104:1.1.1.3 netbsd-7-0-2-RELEASE:1.1.1.2 localcount-20160914:1.1.1.3 netbsd-7-nhusb:1.1.1.2.0.8 netbsd-7-nhusb-base:1.1.1.2 clang-280599:1.1.1.3 pgoyette-localcount-20160806:1.1.1.3 pgoyette-localcount-20160726:1.1.1.3 pgoyette-localcount:1.1.1.3.0.2 pgoyette-localcount-base:1.1.1.3 netbsd-7-0-1-RELEASE:1.1.1.2 clang-261930:1.1.1.3 netbsd-7-0:1.1.1.2.0.6 netbsd-7-0-RELEASE:1.1.1.2 netbsd-7-0-RC3:1.1.1.2 netbsd-7-0-RC2:1.1.1.2 netbsd-7-0-RC1:1.1.1.2 clang-237755:1.1.1.2 clang-232565:1.1.1.2 clang-227398:1.1.1.2 tls-maxphys-base:1.1.1.2 tls-maxphys:1.1.1.2.0.4 netbsd-7:1.1.1.2.0.2 netbsd-7-base:1.1.1.2 clang-215315:1.1.1.2 clang-209886:1.1.1.2 yamt-pagecache:1.1.1.1.0.4 yamt-pagecache-base9:1.1.1.1 tls-earlyentropy:1.1.1.1.0.2 tls-earlyentropy-base:1.1.1.2 riastradh-xf86-video-intel-2-7-1-pre-2-21-15:1.1.1.1 riastradh-drm2-base3:1.1.1.1 clang-202566:1.1.1.1 clang-201163:1.1.1.1 clang-199312:1.1.1.1 clang-198450:1.1.1.1 clang-196603:1.1.1.1 clang-195771:1.1.1.1 LLVM:1.1.1; locks; strict; comment @// @; 1.1 date 2013.11.28.14.14.54; author joerg; state Exp; branches 1.1.1.1; next ; commitid ow8OybrawrB1f3fx; 1.1.1.1 date 2013.11.28.14.14.54; author joerg; state Exp; branches 1.1.1.1.2.1 1.1.1.1.4.1; next 1.1.1.2; commitid ow8OybrawrB1f3fx; 1.1.1.2 date 2014.05.30.18.14.45; author joerg; state Exp; branches 1.1.1.2.4.1; next 1.1.1.3; commitid 8q0kdlBlCn09GACx; 1.1.1.3 date 2016.02.27.22.11.49; author joerg; state Exp; branches 1.1.1.3.14.1 1.1.1.3.16.1; next 1.1.1.4; commitid tIimz3oDlh1NpBWy; 1.1.1.4 date 2018.07.17.18.31.14; author joerg; state Exp; branches; next 1.1.1.5; commitid wDzL46ALjrCZgwKA; 1.1.1.5 date 2019.11.13.22.19.29; author joerg; state dead; branches; next ; commitid QD8YATxuNG34YJKB; 1.1.1.1.2.1 date 2014.08.10.07.08.10; author tls; state Exp; branches; next ; commitid t01A1TLTYxkpGMLx; 1.1.1.1.4.1 date 2013.11.28.14.14.54; author yamt; state dead; branches; next 1.1.1.1.4.2; commitid WSrDtL5nYAUyiyBx; 1.1.1.1.4.2 date 2014.05.22.16.18.31; author yamt; state Exp; branches; next ; commitid WSrDtL5nYAUyiyBx; 1.1.1.2.4.1 date 2014.05.30.18.14.45; author tls; state dead; branches; next 1.1.1.2.4.2; commitid jTnpym9Qu0o4R1Nx; 1.1.1.2.4.2 date 2014.08.19.23.47.32; author tls; state Exp; branches; next ; commitid jTnpym9Qu0o4R1Nx; 1.1.1.3.14.1 date 2018.07.28.04.33.24; author pgoyette; state Exp; branches; next ; commitid 1UP1xAIUxv1ZgRLA; 1.1.1.3.16.1 date 2019.06.10.21.45.29; author christos; state Exp; branches; next 1.1.1.3.16.2; commitid jtc8rnCzWiEEHGqB; 1.1.1.3.16.2 date 2020.04.13.07.46.39; author martin; state dead; branches; next ; commitid X01YhRUPVUDaec4C; desc @@ 1.1 log @Initial revision @ text @//===--- FileMatchTrie.cpp - ----------------------------------------------===// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This file contains the implementation of a FileMatchTrie. // //===----------------------------------------------------------------------===// #include "clang/Tooling/FileMatchTrie.h" #include "llvm/ADT/StringMap.h" #include "llvm/Support/FileSystem.h" #include "llvm/Support/Path.h" #include "llvm/Support/raw_ostream.h" #include namespace clang { namespace tooling { /// \brief Default \c PathComparator using \c llvm::sys::fs::equivalent(). struct DefaultPathComparator : public PathComparator { virtual ~DefaultPathComparator() {} virtual bool equivalent(StringRef FileA, StringRef FileB) const { return FileA == FileB || llvm::sys::fs::equivalent(FileA, FileB); } }; /// \brief A node of the \c FileMatchTrie. /// /// Each node has storage for up to one path and a map mapping a path segment to /// child nodes. The trie starts with an empty root node. class FileMatchTrieNode { public: /// \brief Inserts 'NewPath' into this trie. \c ConsumedLength denotes /// the number of \c NewPath's trailing characters already consumed during /// recursion. /// /// An insert of a path /// 'p'starts at the root node and does the following: /// - If the node is empty, insert 'p' into its storage and abort. /// - If the node has a path 'p2' but no children, take the last path segment /// 's' of 'p2', put a new child into the map at 's' an insert the rest of /// 'p2' there. /// - Insert a new child for the last segment of 'p' and insert the rest of /// 'p' there. /// /// An insert operation is linear in the number of a path's segments. void insert(StringRef NewPath, unsigned ConsumedLength = 0) { // We cannot put relative paths into the FileMatchTrie as then a path can be // a postfix of another path, violating a core assumption of the trie. if (llvm::sys::path::is_relative(NewPath)) return; if (Path.empty()) { // This is an empty leaf. Store NewPath and return. Path = NewPath; return; } if (Children.empty()) { // This is a leaf, ignore duplicate entry if 'Path' equals 'NewPath'. if (NewPath == Path) return; // Make this a node and create a child-leaf with 'Path'. StringRef Element(llvm::sys::path::filename( StringRef(Path).drop_back(ConsumedLength))); Children[Element].Path = Path; } StringRef Element(llvm::sys::path::filename( StringRef(NewPath).drop_back(ConsumedLength))); Children[Element].insert(NewPath, ConsumedLength + Element.size() + 1); } /// \brief Tries to find the node under this \c FileMatchTrieNode that best /// matches 'FileName'. /// /// If multiple paths fit 'FileName' equally well, \c IsAmbiguous is set to /// \c true and an empty string is returned. If no path fits 'FileName', an /// empty string is returned. \c ConsumedLength denotes the number of /// \c Filename's trailing characters already consumed during recursion. /// /// To find the best matching node for a given path 'p', the /// \c findEquivalent() function is called recursively for each path segment /// (back to fron) of 'p' until a node 'n' is reached that does not .. /// - .. have children. In this case it is checked /// whether the stored path is equivalent to 'p'. If yes, the best match is /// found. Otherwise continue with the parent node as if this node did not /// exist. /// - .. a child matching the next path segment. In this case, all children of /// 'n' are an equally good match for 'p'. All children are of 'n' are found /// recursively and their equivalence to 'p' is determined. If none are /// equivalent, continue with the parent node as if 'n' didn't exist. If one /// is equivalent, the best match is found. Otherwise, report and ambigiuity /// error. StringRef findEquivalent(const PathComparator& Comparator, StringRef FileName, bool &IsAmbiguous, unsigned ConsumedLength = 0) const { if (Children.empty()) { if (Comparator.equivalent(StringRef(Path), FileName)) return StringRef(Path); return StringRef(); } StringRef Element(llvm::sys::path::filename(FileName.drop_back( ConsumedLength))); llvm::StringMap::const_iterator MatchingChild = Children.find(Element); if (MatchingChild != Children.end()) { StringRef Result = MatchingChild->getValue().findEquivalent( Comparator, FileName, IsAmbiguous, ConsumedLength + Element.size() + 1); if (!Result.empty() || IsAmbiguous) return Result; } std::vector AllChildren; getAll(AllChildren, MatchingChild); StringRef Result; for (unsigned i = 0; i < AllChildren.size(); i++) { if (Comparator.equivalent(AllChildren[i], FileName)) { if (Result.empty()) { Result = AllChildren[i]; } else { IsAmbiguous = true; return StringRef(); } } } return Result; } private: /// \brief Gets all paths under this FileMatchTrieNode. void getAll(std::vector &Results, llvm::StringMap::const_iterator Except) const { if (Path.empty()) return; if (Children.empty()) { Results.push_back(StringRef(Path)); return; } for (llvm::StringMap::const_iterator It = Children.begin(), E = Children.end(); It != E; ++It) { if (It == Except) continue; It->getValue().getAll(Results, Children.end()); } } // The stored absolute path in this node. Only valid for leaf nodes, i.e. // nodes where Children.empty(). std::string Path; // The children of this node stored in a map based on the next path segment. llvm::StringMap Children; }; FileMatchTrie::FileMatchTrie() : Root(new FileMatchTrieNode), Comparator(new DefaultPathComparator()) {} FileMatchTrie::FileMatchTrie(PathComparator *Comparator) : Root(new FileMatchTrieNode), Comparator(Comparator) {} FileMatchTrie::~FileMatchTrie() { delete Root; } void FileMatchTrie::insert(StringRef NewPath) { Root->insert(NewPath); } StringRef FileMatchTrie::findEquivalent(StringRef FileName, raw_ostream &Error) const { if (llvm::sys::path::is_relative(FileName)) { Error << "Cannot resolve relative paths"; return StringRef(); } bool IsAmbiguous = false; StringRef Result = Root->findEquivalent(*Comparator, FileName, IsAmbiguous); if (IsAmbiguous) Error << "Path is ambiguous"; return Result; } } // end namespace tooling } // end namespace clang @ 1.1.1.1 log @Import Clang 3.4rc1 r195771. @ text @@ 1.1.1.1.2.1 log @Rebase. @ text @d27 1 a27 1 bool equivalent(StringRef FileA, StringRef FileB) const override { @ 1.1.1.2 log @Import Clang 3.5svn r209886. @ text @d27 1 a27 1 bool equivalent(StringRef FileA, StringRef FileB) const override { @ 1.1.1.3 log @Import Clang 3.8.0rc3 r261930. @ text @a19 2 using namespace clang; using namespace tooling; d21 3 a23 1 namespace { d26 1 a30 1 } a31 2 namespace clang { namespace tooling { a158 2 } // end namespace tooling } // end namespace clang d186 3 @ 1.1.1.3.16.1 log @Sync with HEAD @ text @d1 1 a1 1 //===- FileMatchTrie.cpp --------------------------------------------------===// a15 1 #include "llvm/ADT/StringRef.h" d19 1 a19 3 #include #include d24 1 a24 2 /// Default \c PathComparator using \c llvm::sys::fs::equivalent(). d30 1 a30 2 } // namespace d34 1 a34 2 /// A node of the \c FileMatchTrie. d40 1 a40 1 /// Inserts 'NewPath' into this trie. \c ConsumedLength denotes d78 1 a78 1 /// Tries to find the node under this \c FileMatchTrieNode that best d88 1 a88 1 /// (back to front) of 'p' until a node 'n' is reached that does not .. d106 1 a106 1 return {}; d122 2 a123 2 for (const auto &Child : AllChildren) { if (Comparator.equivalent(Child, FileName)) { d125 1 a125 1 Result = Child; d128 1 a128 1 return {}; d136 1 a136 1 /// Gets all paths under this FileMatchTrieNode. d161 2 a162 3 } // namespace tooling } // namespace clang d165 1 a165 1 : Root(new FileMatchTrieNode), Comparator(new DefaultPathComparator()) {} d168 1 a168 1 : Root(new FileMatchTrieNode), Comparator(Comparator) {} d182 1 a182 1 return {}; @ 1.1.1.3.16.2 log @Mostly merge changes from HEAD upto 20200411 @ text @@ 1.1.1.3.14.1 log @Sync with HEAD @ text @d1 1 a1 1 //===- FileMatchTrie.cpp --------------------------------------------------===// a15 1 #include "llvm/ADT/StringRef.h" d19 1 a19 3 #include #include d24 1 a24 2 /// Default \c PathComparator using \c llvm::sys::fs::equivalent(). d30 1 a30 2 } // namespace d34 1 a34 2 /// A node of the \c FileMatchTrie. d40 1 a40 1 /// Inserts 'NewPath' into this trie. \c ConsumedLength denotes d78 1 a78 1 /// Tries to find the node under this \c FileMatchTrieNode that best d88 1 a88 1 /// (back to front) of 'p' until a node 'n' is reached that does not .. d106 1 a106 1 return {}; d122 2 a123 2 for (const auto &Child : AllChildren) { if (Comparator.equivalent(Child, FileName)) { d125 1 a125 1 Result = Child; d128 1 a128 1 return {}; d136 1 a136 1 /// Gets all paths under this FileMatchTrieNode. d161 2 a162 3 } // namespace tooling } // namespace clang d165 1 a165 1 : Root(new FileMatchTrieNode), Comparator(new DefaultPathComparator()) {} d168 1 a168 1 : Root(new FileMatchTrieNode), Comparator(Comparator) {} d182 1 a182 1 return {}; @ 1.1.1.4 log @Import clang r337282 from trunk @ text @d1 1 a1 1 //===- FileMatchTrie.cpp --------------------------------------------------===// a15 1 #include "llvm/ADT/StringRef.h" d19 1 a19 3 #include #include d24 1 a24 2 /// Default \c PathComparator using \c llvm::sys::fs::equivalent(). d30 1 a30 2 } // namespace d34 1 a34 2 /// A node of the \c FileMatchTrie. d40 1 a40 1 /// Inserts 'NewPath' into this trie. \c ConsumedLength denotes d78 1 a78 1 /// Tries to find the node under this \c FileMatchTrieNode that best d88 1 a88 1 /// (back to front) of 'p' until a node 'n' is reached that does not .. d106 1 a106 1 return {}; d122 2 a123 2 for (const auto &Child : AllChildren) { if (Comparator.equivalent(Child, FileName)) { d125 1 a125 1 Result = Child; d128 1 a128 1 return {}; d136 1 a136 1 /// Gets all paths under this FileMatchTrieNode. d161 2 a162 3 } // namespace tooling } // namespace clang d165 1 a165 1 : Root(new FileMatchTrieNode), Comparator(new DefaultPathComparator()) {} d168 1 a168 1 : Root(new FileMatchTrieNode), Comparator(Comparator) {} d182 1 a182 1 return {}; @ 1.1.1.5 log @Mark old LLVM instance as dead. @ text @@ 1.1.1.2.4.1 log @file FileMatchTrie.cpp was added on branch tls-maxphys on 2014-08-19 23:47:32 +0000 @ text @d1 188 @ 1.1.1.2.4.2 log @Rebase to HEAD as of a few days ago. @ text @a0 188 //===--- FileMatchTrie.cpp - ----------------------------------------------===// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This file contains the implementation of a FileMatchTrie. // //===----------------------------------------------------------------------===// #include "clang/Tooling/FileMatchTrie.h" #include "llvm/ADT/StringMap.h" #include "llvm/Support/FileSystem.h" #include "llvm/Support/Path.h" #include "llvm/Support/raw_ostream.h" #include namespace clang { namespace tooling { /// \brief Default \c PathComparator using \c llvm::sys::fs::equivalent(). struct DefaultPathComparator : public PathComparator { virtual ~DefaultPathComparator() {} bool equivalent(StringRef FileA, StringRef FileB) const override { return FileA == FileB || llvm::sys::fs::equivalent(FileA, FileB); } }; /// \brief A node of the \c FileMatchTrie. /// /// Each node has storage for up to one path and a map mapping a path segment to /// child nodes. The trie starts with an empty root node. class FileMatchTrieNode { public: /// \brief Inserts 'NewPath' into this trie. \c ConsumedLength denotes /// the number of \c NewPath's trailing characters already consumed during /// recursion. /// /// An insert of a path /// 'p'starts at the root node and does the following: /// - If the node is empty, insert 'p' into its storage and abort. /// - If the node has a path 'p2' but no children, take the last path segment /// 's' of 'p2', put a new child into the map at 's' an insert the rest of /// 'p2' there. /// - Insert a new child for the last segment of 'p' and insert the rest of /// 'p' there. /// /// An insert operation is linear in the number of a path's segments. void insert(StringRef NewPath, unsigned ConsumedLength = 0) { // We cannot put relative paths into the FileMatchTrie as then a path can be // a postfix of another path, violating a core assumption of the trie. if (llvm::sys::path::is_relative(NewPath)) return; if (Path.empty()) { // This is an empty leaf. Store NewPath and return. Path = NewPath; return; } if (Children.empty()) { // This is a leaf, ignore duplicate entry if 'Path' equals 'NewPath'. if (NewPath == Path) return; // Make this a node and create a child-leaf with 'Path'. StringRef Element(llvm::sys::path::filename( StringRef(Path).drop_back(ConsumedLength))); Children[Element].Path = Path; } StringRef Element(llvm::sys::path::filename( StringRef(NewPath).drop_back(ConsumedLength))); Children[Element].insert(NewPath, ConsumedLength + Element.size() + 1); } /// \brief Tries to find the node under this \c FileMatchTrieNode that best /// matches 'FileName'. /// /// If multiple paths fit 'FileName' equally well, \c IsAmbiguous is set to /// \c true and an empty string is returned. If no path fits 'FileName', an /// empty string is returned. \c ConsumedLength denotes the number of /// \c Filename's trailing characters already consumed during recursion. /// /// To find the best matching node for a given path 'p', the /// \c findEquivalent() function is called recursively for each path segment /// (back to fron) of 'p' until a node 'n' is reached that does not .. /// - .. have children. In this case it is checked /// whether the stored path is equivalent to 'p'. If yes, the best match is /// found. Otherwise continue with the parent node as if this node did not /// exist. /// - .. a child matching the next path segment. In this case, all children of /// 'n' are an equally good match for 'p'. All children are of 'n' are found /// recursively and their equivalence to 'p' is determined. If none are /// equivalent, continue with the parent node as if 'n' didn't exist. If one /// is equivalent, the best match is found. Otherwise, report and ambigiuity /// error. StringRef findEquivalent(const PathComparator& Comparator, StringRef FileName, bool &IsAmbiguous, unsigned ConsumedLength = 0) const { if (Children.empty()) { if (Comparator.equivalent(StringRef(Path), FileName)) return StringRef(Path); return StringRef(); } StringRef Element(llvm::sys::path::filename(FileName.drop_back( ConsumedLength))); llvm::StringMap::const_iterator MatchingChild = Children.find(Element); if (MatchingChild != Children.end()) { StringRef Result = MatchingChild->getValue().findEquivalent( Comparator, FileName, IsAmbiguous, ConsumedLength + Element.size() + 1); if (!Result.empty() || IsAmbiguous) return Result; } std::vector AllChildren; getAll(AllChildren, MatchingChild); StringRef Result; for (unsigned i = 0; i < AllChildren.size(); i++) { if (Comparator.equivalent(AllChildren[i], FileName)) { if (Result.empty()) { Result = AllChildren[i]; } else { IsAmbiguous = true; return StringRef(); } } } return Result; } private: /// \brief Gets all paths under this FileMatchTrieNode. void getAll(std::vector &Results, llvm::StringMap::const_iterator Except) const { if (Path.empty()) return; if (Children.empty()) { Results.push_back(StringRef(Path)); return; } for (llvm::StringMap::const_iterator It = Children.begin(), E = Children.end(); It != E; ++It) { if (It == Except) continue; It->getValue().getAll(Results, Children.end()); } } // The stored absolute path in this node. Only valid for leaf nodes, i.e. // nodes where Children.empty(). std::string Path; // The children of this node stored in a map based on the next path segment. llvm::StringMap Children; }; FileMatchTrie::FileMatchTrie() : Root(new FileMatchTrieNode), Comparator(new DefaultPathComparator()) {} FileMatchTrie::FileMatchTrie(PathComparator *Comparator) : Root(new FileMatchTrieNode), Comparator(Comparator) {} FileMatchTrie::~FileMatchTrie() { delete Root; } void FileMatchTrie::insert(StringRef NewPath) { Root->insert(NewPath); } StringRef FileMatchTrie::findEquivalent(StringRef FileName, raw_ostream &Error) const { if (llvm::sys::path::is_relative(FileName)) { Error << "Cannot resolve relative paths"; return StringRef(); } bool IsAmbiguous = false; StringRef Result = Root->findEquivalent(*Comparator, FileName, IsAmbiguous); if (IsAmbiguous) Error << "Path is ambiguous"; return Result; } } // end namespace tooling } // end namespace clang @ 1.1.1.1.4.1 log @file FileMatchTrie.cpp was added on branch yamt-pagecache on 2014-05-22 16:18:31 +0000 @ text @d1 188 @ 1.1.1.1.4.2 log @sync with head. for a reference, the tree before this commit was tagged as yamt-pagecache-tag8. this commit was splitted into small chunks to avoid a limitation of cvs. ("Protocol error: too many arguments") @ text @a0 188 //===--- FileMatchTrie.cpp - ----------------------------------------------===// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This file contains the implementation of a FileMatchTrie. // //===----------------------------------------------------------------------===// #include "clang/Tooling/FileMatchTrie.h" #include "llvm/ADT/StringMap.h" #include "llvm/Support/FileSystem.h" #include "llvm/Support/Path.h" #include "llvm/Support/raw_ostream.h" #include namespace clang { namespace tooling { /// \brief Default \c PathComparator using \c llvm::sys::fs::equivalent(). struct DefaultPathComparator : public PathComparator { virtual ~DefaultPathComparator() {} virtual bool equivalent(StringRef FileA, StringRef FileB) const { return FileA == FileB || llvm::sys::fs::equivalent(FileA, FileB); } }; /// \brief A node of the \c FileMatchTrie. /// /// Each node has storage for up to one path and a map mapping a path segment to /// child nodes. The trie starts with an empty root node. class FileMatchTrieNode { public: /// \brief Inserts 'NewPath' into this trie. \c ConsumedLength denotes /// the number of \c NewPath's trailing characters already consumed during /// recursion. /// /// An insert of a path /// 'p'starts at the root node and does the following: /// - If the node is empty, insert 'p' into its storage and abort. /// - If the node has a path 'p2' but no children, take the last path segment /// 's' of 'p2', put a new child into the map at 's' an insert the rest of /// 'p2' there. /// - Insert a new child for the last segment of 'p' and insert the rest of /// 'p' there. /// /// An insert operation is linear in the number of a path's segments. void insert(StringRef NewPath, unsigned ConsumedLength = 0) { // We cannot put relative paths into the FileMatchTrie as then a path can be // a postfix of another path, violating a core assumption of the trie. if (llvm::sys::path::is_relative(NewPath)) return; if (Path.empty()) { // This is an empty leaf. Store NewPath and return. Path = NewPath; return; } if (Children.empty()) { // This is a leaf, ignore duplicate entry if 'Path' equals 'NewPath'. if (NewPath == Path) return; // Make this a node and create a child-leaf with 'Path'. StringRef Element(llvm::sys::path::filename( StringRef(Path).drop_back(ConsumedLength))); Children[Element].Path = Path; } StringRef Element(llvm::sys::path::filename( StringRef(NewPath).drop_back(ConsumedLength))); Children[Element].insert(NewPath, ConsumedLength + Element.size() + 1); } /// \brief Tries to find the node under this \c FileMatchTrieNode that best /// matches 'FileName'. /// /// If multiple paths fit 'FileName' equally well, \c IsAmbiguous is set to /// \c true and an empty string is returned. If no path fits 'FileName', an /// empty string is returned. \c ConsumedLength denotes the number of /// \c Filename's trailing characters already consumed during recursion. /// /// To find the best matching node for a given path 'p', the /// \c findEquivalent() function is called recursively for each path segment /// (back to fron) of 'p' until a node 'n' is reached that does not .. /// - .. have children. In this case it is checked /// whether the stored path is equivalent to 'p'. If yes, the best match is /// found. Otherwise continue with the parent node as if this node did not /// exist. /// - .. a child matching the next path segment. In this case, all children of /// 'n' are an equally good match for 'p'. All children are of 'n' are found /// recursively and their equivalence to 'p' is determined. If none are /// equivalent, continue with the parent node as if 'n' didn't exist. If one /// is equivalent, the best match is found. Otherwise, report and ambigiuity /// error. StringRef findEquivalent(const PathComparator& Comparator, StringRef FileName, bool &IsAmbiguous, unsigned ConsumedLength = 0) const { if (Children.empty()) { if (Comparator.equivalent(StringRef(Path), FileName)) return StringRef(Path); return StringRef(); } StringRef Element(llvm::sys::path::filename(FileName.drop_back( ConsumedLength))); llvm::StringMap::const_iterator MatchingChild = Children.find(Element); if (MatchingChild != Children.end()) { StringRef Result = MatchingChild->getValue().findEquivalent( Comparator, FileName, IsAmbiguous, ConsumedLength + Element.size() + 1); if (!Result.empty() || IsAmbiguous) return Result; } std::vector AllChildren; getAll(AllChildren, MatchingChild); StringRef Result; for (unsigned i = 0; i < AllChildren.size(); i++) { if (Comparator.equivalent(AllChildren[i], FileName)) { if (Result.empty()) { Result = AllChildren[i]; } else { IsAmbiguous = true; return StringRef(); } } } return Result; } private: /// \brief Gets all paths under this FileMatchTrieNode. void getAll(std::vector &Results, llvm::StringMap::const_iterator Except) const { if (Path.empty()) return; if (Children.empty()) { Results.push_back(StringRef(Path)); return; } for (llvm::StringMap::const_iterator It = Children.begin(), E = Children.end(); It != E; ++It) { if (It == Except) continue; It->getValue().getAll(Results, Children.end()); } } // The stored absolute path in this node. Only valid for leaf nodes, i.e. // nodes where Children.empty(). std::string Path; // The children of this node stored in a map based on the next path segment. llvm::StringMap Children; }; FileMatchTrie::FileMatchTrie() : Root(new FileMatchTrieNode), Comparator(new DefaultPathComparator()) {} FileMatchTrie::FileMatchTrie(PathComparator *Comparator) : Root(new FileMatchTrieNode), Comparator(Comparator) {} FileMatchTrie::~FileMatchTrie() { delete Root; } void FileMatchTrie::insert(StringRef NewPath) { Root->insert(NewPath); } StringRef FileMatchTrie::findEquivalent(StringRef FileName, raw_ostream &Error) const { if (llvm::sys::path::is_relative(FileName)) { Error << "Cannot resolve relative paths"; return StringRef(); } bool IsAmbiguous = false; StringRef Result = Root->findEquivalent(*Comparator, FileName, IsAmbiguous); if (IsAmbiguous) Error << "Path is ambiguous"; return Result; } } // end namespace tooling } // end namespace clang @