Author: Zhijie Wang Date: 2026-03-03T19:50:02+01:00 New Revision: e379ad78203b32bb444c1ceab2869767a0de728c
URL: https://github.com/llvm/llvm-project/commit/e379ad78203b32bb444c1ceab2869767a0de728c DIFF: https://github.com/llvm/llvm-project/commit/e379ad78203b32bb444c1ceab2869767a0de728c.diff LOG: [LifetimeSafety] Use per-container invalidation rules to fix false positives (#183000) - Refactor `isContainerInvalidationMethod()` to per-container invalidation sets, based on https://en.cppreference.com/w/cpp/container#Iterator_invalidation. - Follow reference invalidation rules instead of iterator invalidation rules. Specifically: - Methods that only invalidate iterators but not references are excluded (e.g. `deque::push_back`, `unordered_map::emplace`). - Methods that only invalidate references to the removed element itself are excluded (e.g. `vector::pop_back`, `deque::pop_*`, and `erase`/`extract` on all node-based containers). - Fix false positives for `insert`/`emplace` etc on ordered associative containers (`set`, `map`, `multiset`, `multimap`), which never invalidate iterators per the standard. - Add previously missing methods: `emplace_hint`, `insert_or_assign`, `push_range`, `replace_with_range`, `resize_and_overwrite`, `merge`. - `operator[]` now only invalidates for `flat_map`. `map::operator[]` and `unordered_map::operator[]` may insert but don't invalidate references. Fixes #181912 Added: Modified: clang/include/clang/Analysis/Analyses/LifetimeSafety/LifetimeAnnotations.h clang/lib/Analysis/LifetimeSafety/LifetimeAnnotations.cpp clang/test/Sema/Inputs/lifetime-analysis.h clang/test/Sema/warn-lifetime-analysis-nocfg.cpp clang/test/Sema/warn-lifetime-safety-invalidations.cpp Removed: ################################################################################ diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/LifetimeAnnotations.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/LifetimeAnnotations.h index 984e9f87fef57..aa9ae4b2a5e6a 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/LifetimeAnnotations.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/LifetimeAnnotations.h @@ -71,8 +71,13 @@ bool isGslOwnerType(QualType QT); // when ownership is manually transferred. bool isUniquePtrRelease(const CXXMethodDecl &MD); -// Returns true if the given method invalidates iterators or references to -// container elements (e.g. vector::push_back). +// Returns true if the given method invalidates references to container +// elements (e.g. vector::push_back). Methods that only invalidate iterators +// but not references (e.g. unordered_map::emplace) are not considered +// invalidating here. +// +// Invalidation rules are based on: +// https://en.cppreference.com/w/cpp/container#Iterator_invalidation bool isContainerInvalidationMethod(const CXXMethodDecl &MD); } // namespace clang::lifetimes diff --git a/clang/lib/Analysis/LifetimeSafety/LifetimeAnnotations.cpp b/clang/lib/Analysis/LifetimeSafety/LifetimeAnnotations.cpp index 67d06f17ffd74..0d3da898137a6 100644 --- a/clang/lib/Analysis/LifetimeSafety/LifetimeAnnotations.cpp +++ b/clang/lib/Analysis/LifetimeSafety/LifetimeAnnotations.cpp @@ -277,23 +277,83 @@ bool isContainerInvalidationMethod(const CXXMethodDecl &MD) { if (!isInStlNamespace(RD)) return false; - StringRef ContainerName = getName(*RD); - static const llvm::StringSet<> Containers = { - // Sequence - "vector", "basic_string", "deque", - // Adaptors - // FIXME: Add queue and stack and check for underlying container (e.g. no - // invalidation for std::list). - "priority_queue", - // Associative - "set", "multiset", "map", "multimap", - // Unordered Associative - "unordered_set", "unordered_multiset", "unordered_map", - "unordered_multimap", - // C++23 Flat - "flat_map", "flat_set", "flat_multimap", "flat_multiset"}; - - if (!Containers.contains(ContainerName)) + // `pop_back` is excluded: it only invalidates references to the removed + // element, not to other elements. + static const llvm::StringSet<> Vector = {// Insertion + "insert", "emplace", "emplace_back", + "push_back", "insert_range", + "append_range", + // Removal + "erase", "clear", + // Memory management + "reserve", "resize", "shrink_to_fit", + // Assignment + "assign", "assign_range"}; + + // `pop_*` methods are excluded: they only invalidate references to the + // removed element, not to other elements. + static const llvm::StringSet<> Deque = {// Insertion + "insert", "emplace", "insert_range", + // Removal + "erase", "clear", + // Memory management + "resize", "shrink_to_fit", + // Assignment + "assign", "assign_range"}; + + static const llvm::StringSet<> String = { + // Insertion + "insert", "push_back", "append", "replace", "replace_with_range", + "insert_range", "append_range", + // Removal + "pop_back", "erase", "clear", + // Memory management + "reserve", "resize", "resize_and_overwrite", "shrink_to_fit", + // Assignment + "swap", "assign", "assign_range"}; + + // FIXME: Add queue and stack and check for underlying container + // (e.g. no invalidation for std::list). + static const llvm::StringSet<> PriorityQueue = {// Insertion + "push", "emplace", + "push_range", + // Removal + "pop"}; + + // `erase` and `extract` are excluded: they only affect the removed element, + // not to other elements. + static const llvm::StringSet<> NodeBased = {// Removal + "clear"}; + + // For `flat_*` container adaptors, `try_emplace` and `insert_or_assign` + // only exist on `flat_map`. Listing them here is harmless since the methods + // won't be found on other types. + static const llvm::StringSet<> Flat = {// Insertion + "insert", "emplace", "emplace_hint", + "try_emplace", "insert_or_assign", + "insert_range", "merge", + // Removal + "extract", "erase", "clear", + // Assignment + "replace"}; + + const StringRef ContainerName = getName(*RD); + // TODO: Consider caching this lookup by CXXMethodDecl pointer if this + // StringSwitch becomes a performance bottleneck. + const llvm::StringSet<> *InvalidatingMethods = + llvm::StringSwitch<const llvm::StringSet<> *>(ContainerName) + .Case("vector", &Vector) + .Case("basic_string", &String) + .Case("deque", &Deque) + .Case("priority_queue", &PriorityQueue) + .Cases({"set", "multiset", "map", "multimap", "unordered_set", + "unordered_multiset", "unordered_map", "unordered_multimap"}, + &NodeBased) + .Cases({"flat_map", "flat_set", "flat_multimap", "flat_multiset"}, + &Flat) + .Default(nullptr); + + if (!InvalidatingMethods) return false; // Handle Operators via OverloadedOperatorKind @@ -303,13 +363,10 @@ bool isContainerInvalidationMethod(const CXXMethodDecl &MD) { case OO_Equal: // operator= : Always invalidates (Assignment) case OO_PlusEqual: // operator+= : Append (String/Vector) return true; - case OO_Subscript: // operator[] : Invalidation only for Maps - // (Insert-or-access) - { - static const llvm::StringSet<> MapContainers = {"map", "unordered_map", - "flat_map"}; - return MapContainers.contains(ContainerName); - } + case OO_Subscript: // operator[] : Invalidation only for + // `flat_map` (Insert-or-access). + // `map` and `unordered_map` are excluded. + return ContainerName == "flat_map"; default: return false; } @@ -318,41 +375,6 @@ bool isContainerInvalidationMethod(const CXXMethodDecl &MD) { if (!MD.getIdentifier()) return false; - StringRef MethodName = MD.getName(); - - // Special handling for 'erase': - // It invalidates the whole container (effectively) for contiguous/flat - // storage, but is safe for other iterators in node-based containers. - if (MethodName == "erase") { - static const llvm::StringSet<> NodeBasedContainers = {"map", - "set", - "multimap", - "multiset", - "unordered_map", - "unordered_set", - "unordered_multimap", - "unordered_multiset"}; - - // 'erase' invalidates for non node-based containers (vector, deque, string, - // flat_map). - return !NodeBasedContainers.contains(ContainerName); - } - - static const llvm::StringSet<> InvalidatingMembers = { - // Basic Insertion/Emplacement - "push_front", "push_back", "emplace_front", "emplace_back", "insert", - "emplace", "push", - // Basic Removal/Clearing - "pop_front", "pop_back", "pop", "clear", - // Memory Management - "reserve", "resize", "shrink_to_fit", - // Assignment (Named) - "assign", "swap", - // String Specifics - "append", "replace", - // Modern C++ (C++17/23) - "extract", "try_emplace", "insert_range", "append_range", "assign_range"}; - - return InvalidatingMembers.contains(MethodName); + return InvalidatingMethods->contains(MD.getName()); } } // namespace clang::lifetimes diff --git a/clang/test/Sema/Inputs/lifetime-analysis.h b/clang/test/Sema/Inputs/lifetime-analysis.h index eaee12433342e..1b07f4f13467f 100644 --- a/clang/test/Sema/Inputs/lifetime-analysis.h +++ b/clang/test/Sema/Inputs/lifetime-analysis.h @@ -104,6 +104,48 @@ struct unordered_map { iterator erase(iterator); }; +template<class Key> +struct set { + using iterator = __gnu_cxx::basic_iterator<const Key>; + iterator begin(); + iterator end(); + void insert(const Key& key); + iterator erase(iterator); + void extract(iterator); + void clear(); +}; + +template<class Key> +struct multiset { + using iterator = __gnu_cxx::basic_iterator<const Key>; + iterator begin(); + iterator end(); + void insert(const Key& key); + void clear(); +}; + +template<class Key, class T> +struct map { + using iterator = __gnu_cxx::basic_iterator<std::pair<const Key, T>>; + T& operator[](const Key& key); + iterator begin(); + iterator end(); + void insert(const std::pair<const Key, T>& value); + template<class... Args> + void emplace(Args&&... args); + iterator erase(iterator); + void clear(); +}; + +template<class Key, class T> +struct multimap { + using iterator = __gnu_cxx::basic_iterator<std::pair<const Key, T>>; + iterator begin(); + iterator end(); + void insert(const std::pair<const Key, T>& value); + void clear(); +}; + template<typename T> struct basic_string_view { basic_string_view(); diff --git a/clang/test/Sema/warn-lifetime-analysis-nocfg.cpp b/clang/test/Sema/warn-lifetime-analysis-nocfg.cpp index 59edfc238cf6a..3305e9e270d86 100644 --- a/clang/test/Sema/warn-lifetime-analysis-nocfg.cpp +++ b/clang/test/Sema/warn-lifetime-analysis-nocfg.cpp @@ -831,23 +831,6 @@ void test13() { } // namespace GH100526 -namespace std { -template <typename T> -class __set_iterator {}; - -template<typename T> -struct BB { - typedef __set_iterator<T> iterator; -}; - -template <typename T> -class set { -public: - ~set(); - typedef typename BB<T>::iterator iterator; - iterator begin() const; -}; -} // namespace std namespace GH118064{ void test() { diff --git a/clang/test/Sema/warn-lifetime-safety-invalidations.cpp b/clang/test/Sema/warn-lifetime-safety-invalidations.cpp index 65d676cbe8361..c50c1e2d77d65 100644 --- a/clang/test/Sema/warn-lifetime-safety-invalidations.cpp +++ b/clang/test/Sema/warn-lifetime-safety-invalidations.cpp @@ -164,12 +164,12 @@ void IteratorInvalidationInAForeachLoop(std::vector<int> v) { } // namespace InvalidationInLoops namespace StdVectorPopBack { -void StdVectorPopBackInvalid(std::vector<int> v) { - auto it = v.begin(); // expected-warning {{object whose reference is captured is later invalidated}} +void StdVectorPopBackDoesNotInvalidateOthers(std::vector<int> v) { + auto it = v.begin(); if (it == v.end()) return; - *it; // ok - v.pop_back(); // expected-note {{invalidated here}} - *it; // expected-note {{later used here}} + *it; + v.pop_back(); + *it; } } // namespace StdVectorPopBack @@ -374,3 +374,97 @@ void ChangingRegionOwnedByContainerIsOk() { } } // namespace ContainersAsFields + +namespace AssociativeContainers { +void SetInsertDoesNotInvalidate() { + std::set<int> s; + s.insert(0); + auto it = s.begin(); + s.insert(2); + *it; +} + +void MapInsertDoesNotInvalidate() { + std::map<int, int> m; + auto it = m.begin(); + m.insert({1, 2}); + *it; +} + +void MapEmplaceDoesNotInvalidate() { + std::map<int, int> m; + auto it = m.begin(); + m.emplace(1, 2); + *it; +} + +void MultisetInsertDoesNotInvalidate() { + std::multiset<int> s; + auto it = s.begin(); + s.insert(1); + *it; +} + +void MultimapInsertDoesNotInvalidate() { + std::multimap<int, int> m; + auto it = m.begin(); + m.insert({1, 2}); + *it; +} + +void SetEraseDoesNotInvalidateOthers() { + std::set<int> s; + s.insert(1); + s.insert(2); + auto it1 = s.begin(); + auto it2 = it1; + ++it2; + s.erase(it2); + *it1; +} + +void SetExtractDoesNotInvalidateOthers() { + std::set<int> s; + s.insert(1); + s.insert(2); + auto it1 = s.begin(); + auto it2 = it1; + ++it2; + s.extract(it2); + *it1; +} + +void SetClearInvalidates() { + std::set<int> s; + auto it = s.begin(); // expected-warning {{object whose reference is captured is later invalidated}} + s.clear(); // expected-note {{invalidated here}} + *it; // expected-note {{later used here}} +} + +void MapClearInvalidates() { + std::map<int, int> m; + auto it = m.begin(); // expected-warning {{object whose reference is captured is later invalidated}} + m.clear(); // expected-note {{invalidated here}} + *it; // expected-note {{later used here}} +} + +void MapSubscriptDoesNotInvalidate() { + std::map<int, int> m; + auto it = m.begin(); + m[1]; + *it; +} + +void PrintMax(const int& a, const int& b); + +void MapSubscriptMultipleCallsDoesNotInvalidate(std::map<int, int> mp, int a, int b) { + PrintMax(mp[a], mp[b]); +} + +void FlatMapSubscriptMultipleCallsInvalidate(std::flat_map<int, int> mp, int a, int b) { + PrintMax(mp[a], mp[b]); // expected-warning {{object whose reference is captured is later invalidated}} \ + // expected-note {{invalidated here}} \ + // expected-note {{later used here}} +} + +} // namespace AssociativeContainers _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
