https://github.com/aeft created https://github.com/llvm/llvm-project/pull/183000
- Refactor `isContainerInvalidationMethod()` to per-container invalidation sets, based on https://en.cppreference.com/w/cpp/container#Iterator_invalidation. - 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`, `rehash`, `replace_with_range`, `resize_and_overwrite`, `merge` (unordered/flat only). - Lists track iterator invalidation only, which is a conservative superset of reference invalidation (e.g. `unordered_map::insert` invalidates iterators on rehash but never references). >From 53a73e7acd3dba6ea1b3ba5b666f8c81eaa6a5d6 Mon Sep 17 00:00:00 2001 From: Alex Wang <[email protected]> Date: Mon, 23 Feb 2026 21:49:51 -0800 Subject: [PATCH] [LifetimeSafety] Use per-container invalidation rules to fix false positives --- .../LifetimeSafety/LifetimeAnnotations.cpp | 150 ++++++++++++------ clang/test/Sema/Inputs/lifetime-analysis.h | 42 +++++ .../warn-lifetime-safety-invalidations.cpp | 75 +++++++++ 3 files changed, 215 insertions(+), 52 deletions(-) diff --git a/clang/lib/Analysis/LifetimeSafety/LifetimeAnnotations.cpp b/clang/lib/Analysis/LifetimeSafety/LifetimeAnnotations.cpp index 67d06f17ffd74..4b754059946b4 100644 --- a/clang/lib/Analysis/LifetimeSafety/LifetimeAnnotations.cpp +++ b/clang/lib/Analysis/LifetimeSafety/LifetimeAnnotations.cpp @@ -272,28 +272,109 @@ bool isUniquePtrRelease(const CXXMethodDecl &MD) { MD.getNumParams() == 0 && isStdUniquePtr(*MD.getParent()); } +/// Returns the set of methods that invalidate iterators for the given +/// container, or nullptr if the container is not recognized. +/// +/// Iterator invalidation rules per the C++ standard: +/// https://en.cppreference.com/w/cpp/container#Iterator_invalidation +static const llvm::StringSet<> * +getInvalidatingMethods(StringRef ContainerName) { + static const llvm::StringSet<> Vector = {// Insertion + "insert", "emplace", "emplace_back", + "push_back", "insert_range", + "append_range", + // Removal + "pop_back", "erase", "clear", + // Memory management + "reserve", "resize", "shrink_to_fit", + // Assignment + "swap", "assign", "assign_range"}; + + static const llvm::StringSet<> Deque = { + // Insertion + "insert", "emplace", "emplace_back", "push_back", "push_front", + "emplace_front", "insert_range", "append_range", + // Removal + "pop_back", "pop_front", "erase", "clear", + // Memory management + "resize", "shrink_to_fit", + // Assignment + "swap", "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", + // Assignment + "swap"}; + + static const llvm::StringSet<> Associative = {// Removal + "clear", + // Assignment + "swap"}; + + // For unordered associative containers, `try_emplace` and `insert_or_assign` + // only exist on `unordered_map`. Listing them here is harmless since the + // methods won't be found on other types. + static const llvm::StringSet<> UnorderedAssociative = { + // Insertion + "insert", "emplace", "emplace_hint", "try_emplace", "insert_or_assign", + "insert_range", "merge", + // Removal + "clear", + // Hash policy + "rehash", "reserve", + // Assignment + "swap"}; + + // 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 + "swap", "replace"}; + + return 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"}, &Associative) + .Cases({"unordered_set", "unordered_multiset", "unordered_map", + "unordered_multimap"}, + &UnorderedAssociative) + .Cases({"flat_map", "flat_set", "flat_multimap", "flat_multiset"}, &Flat) + .Default(nullptr); +} + bool isContainerInvalidationMethod(const CXXMethodDecl &MD) { const CXXRecordDecl *RD = MD.getParent(); 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)) + const llvm::StringSet<> *InvalidatingMethods = + getInvalidatingMethods(ContainerName); + if (!InvalidatingMethods) return false; // Handle Operators via OverloadedOperatorKind @@ -318,41 +399,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-safety-invalidations.cpp b/clang/test/Sema/warn-lifetime-safety-invalidations.cpp index 65d676cbe8361..f7185ba7b9255 100644 --- a/clang/test/Sema/warn-lifetime-safety-invalidations.cpp +++ b/clang/test/Sema/warn-lifetime-safety-invalidations.cpp @@ -374,3 +374,78 @@ 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}} +} + +} // namespace AssociativeContainers _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
