Googler | 858c86e | 2021-11-26 14:19:41 +0000 | [diff] [blame] | 1 | // Part of the Crubit project, under the Apache License v2.0 with LLVM |
| 2 | // Exceptions. See /LICENSE for license information. |
| 3 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 4 | |
| 5 | #include "lifetime_annotations/function_lifetimes.h" |
| 6 | |
| 7 | #include <string> |
| 8 | |
Googler | 858c86e | 2021-11-26 14:19:41 +0000 | [diff] [blame] | 9 | #include "third_party/absl/strings/str_cat.h" |
| 10 | #include "third_party/absl/strings/str_join.h" |
Marcel Hlopko | 97a68a1 | 2022-03-09 11:38:51 +0000 | [diff] [blame] | 11 | #include "lifetime_annotations/lifetime.h" |
| 12 | #include "lifetime_annotations/type_lifetimes.h" |
Luca Versari | edf553b | 2022-01-26 14:10:32 +0000 | [diff] [blame] | 13 | #include "third_party/llvm/llvm-project/clang/include/clang/AST/DeclCXX.h" |
Luca Versari | 95ce68f | 2022-03-24 14:44:19 +0000 | [diff] [blame] | 14 | #include "third_party/llvm/llvm-project/clang/include/clang/AST/Type.h" |
Luca Versari | edf553b | 2022-01-26 14:10:32 +0000 | [diff] [blame] | 15 | #include "third_party/llvm/llvm-project/clang/include/clang/Basic/LLVM.h" |
Luca Versari | 95ce68f | 2022-03-24 14:44:19 +0000 | [diff] [blame] | 16 | #include "third_party/llvm/llvm-project/llvm/include/llvm/ADT/SmallVector.h" |
| 17 | #include "third_party/llvm/llvm-project/llvm/include/llvm/Support/Error.h" |
Googler | 858c86e | 2021-11-26 14:19:41 +0000 | [diff] [blame] | 18 | |
Martin Brænne | 1a207c5 | 2022-04-19 00:05:38 -0700 | [diff] [blame^] | 19 | namespace clang { |
| 20 | namespace tidy { |
| 21 | namespace lifetimes { |
Googler | 858c86e | 2021-11-26 14:19:41 +0000 | [diff] [blame] | 22 | |
Luca Versari | 95ce68f | 2022-03-24 14:44:19 +0000 | [diff] [blame] | 23 | namespace { |
Googler | 858c86e | 2021-11-26 14:19:41 +0000 | [diff] [blame] | 24 | // Track a bijective mapping between 2 sets of Lifetimes. |
| 25 | class LifetimeBijection { |
| 26 | public: |
| 27 | // Returns true if the bidirectional mapping between lifetimes could be added |
| 28 | // to the bijection, or is already present. Returns false if the lifetimes |
| 29 | // conflict with other mappings already recorded in the bijection. |
| 30 | bool Add(Lifetime lifetime_in_a, Lifetime lifetime_in_b) { |
Googler | 727e97b | 2021-11-30 14:38:37 +0000 | [diff] [blame] | 31 | auto [a_to_b_iter, a_to_b_inserted] = |
| 32 | a_to_b_.try_emplace(lifetime_in_a, lifetime_in_b); |
| 33 | if (!a_to_b_inserted) { |
| 34 | return a_to_b_iter->second == lifetime_in_b; |
Googler | 858c86e | 2021-11-26 14:19:41 +0000 | [diff] [blame] | 35 | } |
Googler | 727e97b | 2021-11-30 14:38:37 +0000 | [diff] [blame] | 36 | auto [_, b_to_a_inserted] = |
| 37 | b_to_a_.try_emplace(lifetime_in_b, lifetime_in_a); |
| 38 | return b_to_a_inserted; |
Googler | 858c86e | 2021-11-26 14:19:41 +0000 | [diff] [blame] | 39 | } |
| 40 | |
| 41 | private: |
| 42 | llvm::DenseMap<Lifetime, Lifetime> a_to_b_; |
| 43 | llvm::DenseMap<Lifetime, Lifetime> b_to_a_; |
| 44 | }; |
| 45 | |
| 46 | } // namespace |
| 47 | |
Luca Versari | 95ce68f | 2022-03-24 14:44:19 +0000 | [diff] [blame] | 48 | llvm::Expected<FunctionLifetimes> FunctionLifetimes::CreateForDecl( |
| 49 | const clang::FunctionDecl* func, |
| 50 | const FunctionLifetimeFactory& lifetime_factory) { |
| 51 | clang::QualType this_type; |
| 52 | if (auto method = clang::dyn_cast<clang::CXXMethodDecl>(func); |
| 53 | method && !method->isStatic()) { |
| 54 | this_type = method->getThisType(); |
| 55 | } |
| 56 | return Create(func->getType()->getAs<clang::FunctionProtoType>(), this_type, |
| 57 | lifetime_factory); |
| 58 | } |
| 59 | |
Luca Versari | cc7e6cb | 2022-04-05 08:08:23 -0700 | [diff] [blame] | 60 | llvm::Expected<FunctionLifetimes> FunctionLifetimes::CreateForFunctionType( |
| 61 | const clang::FunctionProtoType* func, |
| 62 | const FunctionLifetimeFactory& lifetime_factory) { |
| 63 | return Create(func, clang::QualType(), lifetime_factory); |
| 64 | } |
| 65 | |
Luca Versari | 95ce68f | 2022-03-24 14:44:19 +0000 | [diff] [blame] | 66 | bool FunctionLifetimes::IsValidForDecl(const clang::FunctionDecl* function) { |
| 67 | // TODO(veluca): also validate the types of the arguments, and/or the type of |
| 68 | // the function itself. |
| 69 | if (auto method = clang::dyn_cast<clang::CXXMethodDecl>(function); |
| 70 | method && !method->isStatic()) { |
| 71 | if (!this_lifetimes_.has_value()) return false; |
| 72 | } |
| 73 | return param_lifetimes_.size() == function->param_size(); |
| 74 | } |
| 75 | |
| 76 | llvm::Expected<FunctionLifetimes> FunctionLifetimes::Create( |
| 77 | const clang::FunctionProtoType* type, const clang::QualType this_type, |
| 78 | const FunctionLifetimeFactory& lifetime_factory) { |
| 79 | FunctionLifetimes ret; |
| 80 | |
| 81 | if (!this_type.isNull()) { |
| 82 | ValueLifetimes tmp; |
| 83 | if (llvm::Error err = |
| 84 | ValueLifetimes::Create(this_type, [&](clang::QualType type, |
| 85 | llvm::StringRef param) { |
| 86 | return lifetime_factory.CreateParamLifetime(type, param); |
| 87 | }).moveInto(tmp)) { |
| 88 | return std::move(err); |
Googler | 858c86e | 2021-11-26 14:19:41 +0000 | [diff] [blame] | 89 | } |
Luca Versari | 95ce68f | 2022-03-24 14:44:19 +0000 | [diff] [blame] | 90 | ret.this_lifetimes_ = std::move(tmp); |
Googler | 858c86e | 2021-11-26 14:19:41 +0000 | [diff] [blame] | 91 | } |
| 92 | |
Luca Versari | 95ce68f | 2022-03-24 14:44:19 +0000 | [diff] [blame] | 93 | ret.param_lifetimes_.reserve(type->getNumParams()); |
| 94 | for (size_t i = 0; i < type->getNumParams(); i++) { |
| 95 | ValueLifetimes tmp; |
| 96 | if (llvm::Error err = ValueLifetimes::Create( |
| 97 | type->getParamType(i), |
| 98 | [&](clang::QualType type, llvm::StringRef param) { |
| 99 | return lifetime_factory.CreateParamLifetime( |
| 100 | type, param); |
| 101 | }) |
| 102 | .moveInto(tmp)) { |
| 103 | return std::move(err); |
| 104 | } |
| 105 | ret.param_lifetimes_.push_back(std::move(tmp)); |
| 106 | } |
| 107 | |
| 108 | if (llvm::Error err = ValueLifetimes::Create( |
| 109 | type->getReturnType(), |
| 110 | [&](clang::QualType type, llvm::StringRef param) { |
| 111 | return lifetime_factory.CreateReturnLifetime( |
| 112 | type, param, ret.param_lifetimes_, |
| 113 | ret.this_lifetimes_); |
| 114 | }) |
| 115 | .moveInto(ret.return_lifetimes_)) { |
| 116 | return std::move(err); |
| 117 | } |
| 118 | |
| 119 | return ret; |
| 120 | } |
| 121 | |
Luca Versari | 043a36e | 2022-04-08 00:55:36 -0700 | [diff] [blame] | 122 | bool FunctionLifetimes::HasAny( |
| 123 | const std::function<bool(Lifetime)>& predicate) const { |
| 124 | return std::any_of(param_lifetimes_.begin(), param_lifetimes_.end(), |
| 125 | [&predicate](const ValueLifetimes& v) { |
| 126 | return v.HasAny(predicate); |
| 127 | }) || |
| 128 | return_lifetimes_.HasAny(predicate) || |
| 129 | (this_lifetimes_.has_value() && this_lifetimes_->HasAny(predicate)); |
| 130 | } |
| 131 | |
Luca Versari | d690116 | 2022-04-08 02:59:33 -0700 | [diff] [blame] | 132 | llvm::DenseSet<Lifetime> FunctionLifetimes::AllFreeLifetimes() const { |
| 133 | // TODO(veluca): this is incorrect in the presence of HRTBs. |
| 134 | llvm::DenseSet<Lifetime> all_lifetimes; |
| 135 | Traverse([&all_lifetimes](Lifetime l, Variance) { |
| 136 | if (l != Lifetime::Static()) { |
| 137 | all_lifetimes.insert(l); |
| 138 | } |
| 139 | }); |
| 140 | return all_lifetimes; |
| 141 | } |
| 142 | |
Luca Versari | c523163 | 2022-04-11 07:36:35 -0700 | [diff] [blame] | 143 | void FunctionLifetimes::SubstituteLifetimes( |
| 144 | const LifetimeSubstitutions& subst) { |
| 145 | // TODO(veluca): this is incorrect in the presence of HRTBs. |
| 146 | std::for_each(param_lifetimes_.begin(), param_lifetimes_.end(), |
| 147 | [&subst](ValueLifetimes& v) { v.SubstituteLifetimes(subst); }); |
| 148 | return_lifetimes_.SubstituteLifetimes(subst); |
| 149 | if (this_lifetimes_.has_value()) { |
| 150 | this_lifetimes_->SubstituteLifetimes(subst); |
| 151 | } |
| 152 | } |
| 153 | |
Luca Versari | 95ce68f | 2022-03-24 14:44:19 +0000 | [diff] [blame] | 154 | void FunctionLifetimes::Traverse( |
| 155 | std::function<void(Lifetime&, Variance)> visitor) { |
| 156 | for (auto& param : param_lifetimes_) { |
| 157 | param.Traverse(visitor); |
| 158 | } |
| 159 | return_lifetimes_.Traverse(visitor); |
| 160 | if (this_lifetimes_.has_value()) { |
| 161 | this_lifetimes_->Traverse(visitor); |
| 162 | } |
| 163 | } |
| 164 | |
| 165 | void FunctionLifetimes::Traverse( |
| 166 | std::function<void(const Lifetime&, Variance)> visitor) const { |
| 167 | const_cast<FunctionLifetimes*>(this)->Traverse( |
| 168 | [visitor](Lifetime& l, Variance v) { visitor(l, v); }); |
Googler | 858c86e | 2021-11-26 14:19:41 +0000 | [diff] [blame] | 169 | } |
| 170 | |
| 171 | bool FunctionLifetimes::IsIsomorphic(const FunctionLifetimes& other) const { |
| 172 | // We expect this function to only be called for 2 FunctionLifetime objects |
| 173 | // that are for the same function, thus the number of parameters, and the |
| 174 | // number of Lifetimes for each type, should always match. |
Luca Versari | 95ce68f | 2022-03-24 14:44:19 +0000 | [diff] [blame] | 175 | assert(param_lifetimes_.size() == other.param_lifetimes_.size()); |
| 176 | assert(this_lifetimes_.has_value() == other.this_lifetimes_.has_value()); |
Googler | 858c86e | 2021-11-26 14:19:41 +0000 | [diff] [blame] | 177 | |
| 178 | // Map of equivalent lifetimes between `*this` and `other`. |
| 179 | LifetimeBijection bijection; |
| 180 | |
Luca Versari | 95ce68f | 2022-03-24 14:44:19 +0000 | [diff] [blame] | 181 | llvm::SmallVector<Lifetime> my_lifetimes; |
| 182 | Traverse( |
| 183 | [&my_lifetimes](Lifetime l, Variance) { my_lifetimes.push_back(l); }); |
| 184 | llvm::SmallVector<Lifetime> other_lifetimes; |
| 185 | other.Traverse([&other_lifetimes](Lifetime l, Variance) { |
| 186 | other_lifetimes.push_back(l); |
| 187 | }); |
Googler | 858c86e | 2021-11-26 14:19:41 +0000 | [diff] [blame] | 188 | |
Luca Versari | 95ce68f | 2022-03-24 14:44:19 +0000 | [diff] [blame] | 189 | assert(my_lifetimes.size() == other_lifetimes.size()); |
| 190 | for (size_t i = 0; i < my_lifetimes.size(); ++i) { |
| 191 | if (!bijection.Add(my_lifetimes[i], other_lifetimes[i])) { |
Googler | 858c86e | 2021-11-26 14:19:41 +0000 | [diff] [blame] | 192 | return false; |
Luca Versari | 95ce68f | 2022-03-24 14:44:19 +0000 | [diff] [blame] | 193 | } |
Googler | 858c86e | 2021-11-26 14:19:41 +0000 | [diff] [blame] | 194 | } |
| 195 | return true; |
| 196 | } |
| 197 | |
| 198 | std::string FunctionLifetimes::DebugString(LifetimeFormatter formatter) const { |
| 199 | std::vector<std::string> formatted_param_lifetimes; |
| 200 | |
Luca Versari | cc7e6cb | 2022-04-05 08:08:23 -0700 | [diff] [blame] | 201 | // Add parenteses to non-trivial nested lifetimes, i.e. fn parameters with >1 |
| 202 | // lifetimes, as their DebugString does not contain parentheses. |
Luca Versari | 6ee6b34 | 2022-04-05 05:40:52 -0700 | [diff] [blame] | 203 | auto maybe_add_parentheses = [&](std::string s) { |
| 204 | if (s.find_first_of(",()") != std::string::npos || s.empty()) { |
| 205 | return absl::StrCat("(", s, ")"); |
| 206 | } |
| 207 | return s; |
| 208 | }; |
| 209 | |
Luca Versari | 95ce68f | 2022-03-24 14:44:19 +0000 | [diff] [blame] | 210 | for (const auto& param : param_lifetimes_) { |
Luca Versari | 6ee6b34 | 2022-04-05 05:40:52 -0700 | [diff] [blame] | 211 | formatted_param_lifetimes.push_back( |
| 212 | maybe_add_parentheses(param.DebugString(formatter))); |
Googler | 858c86e | 2021-11-26 14:19:41 +0000 | [diff] [blame] | 213 | } |
| 214 | |
| 215 | std::string result; |
Luca Versari | 95ce68f | 2022-03-24 14:44:19 +0000 | [diff] [blame] | 216 | if (this_lifetimes_.has_value()) { |
Luca Versari | 6ee6b34 | 2022-04-05 05:40:52 -0700 | [diff] [blame] | 217 | result = absl::StrCat( |
| 218 | maybe_add_parentheses(this_lifetimes_->DebugString(formatter)), ":"); |
Googler | 858c86e | 2021-11-26 14:19:41 +0000 | [diff] [blame] | 219 | } |
| 220 | if (!result.empty() && !formatted_param_lifetimes.empty()) { |
| 221 | absl::StrAppend(&result, " "); |
| 222 | } |
| 223 | absl::StrAppend(&result, absl::StrJoin(formatted_param_lifetimes, ", ")); |
| 224 | |
Luca Versari | 95ce68f | 2022-03-24 14:44:19 +0000 | [diff] [blame] | 225 | if (return_lifetimes_.HasLifetimes()) { |
Googler | 858c86e | 2021-11-26 14:19:41 +0000 | [diff] [blame] | 226 | if (!result.empty()) { |
| 227 | absl::StrAppend(&result, " "); |
| 228 | } |
Luca Versari | 6ee6b34 | 2022-04-05 05:40:52 -0700 | [diff] [blame] | 229 | absl::StrAppend( |
| 230 | &result, "-> ", |
| 231 | maybe_add_parentheses(return_lifetimes_.DebugString(formatter))); |
Googler | 858c86e | 2021-11-26 14:19:41 +0000 | [diff] [blame] | 232 | } |
| 233 | |
| 234 | return result; |
| 235 | } |
| 236 | |
Googler | 858c86e | 2021-11-26 14:19:41 +0000 | [diff] [blame] | 237 | std::ostream& operator<<(std::ostream& os, |
| 238 | const FunctionLifetimes& func_lifetimes) { |
| 239 | return os << func_lifetimes.DebugString(); |
| 240 | } |
| 241 | |
Martin Brænne | 1a207c5 | 2022-04-19 00:05:38 -0700 | [diff] [blame^] | 242 | } // namespace lifetimes |
| 243 | } // namespace tidy |
| 244 | } // namespace clang |