blob: 2e74cb6aed6dfc3c3916166edf8610098eddb818 [file] [log] [blame]
Googler858c86e2021-11-26 14:19:41 +00001// 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
Googler858c86e2021-11-26 14:19:41 +00009#include "third_party/absl/strings/str_cat.h"
10#include "third_party/absl/strings/str_join.h"
Marcel Hlopko97a68a12022-03-09 11:38:51 +000011#include "lifetime_annotations/lifetime.h"
12#include "lifetime_annotations/type_lifetimes.h"
Luca Versariedf553b2022-01-26 14:10:32 +000013#include "third_party/llvm/llvm-project/clang/include/clang/AST/DeclCXX.h"
Luca Versari95ce68f2022-03-24 14:44:19 +000014#include "third_party/llvm/llvm-project/clang/include/clang/AST/Type.h"
Luca Versariedf553b2022-01-26 14:10:32 +000015#include "third_party/llvm/llvm-project/clang/include/clang/Basic/LLVM.h"
Luca Versari95ce68f2022-03-24 14:44:19 +000016#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"
Googler858c86e2021-11-26 14:19:41 +000018
Martin Brænne1a207c52022-04-19 00:05:38 -070019namespace clang {
20namespace tidy {
21namespace lifetimes {
Googler858c86e2021-11-26 14:19:41 +000022
Luca Versari95ce68f2022-03-24 14:44:19 +000023namespace {
Googler858c86e2021-11-26 14:19:41 +000024// Track a bijective mapping between 2 sets of Lifetimes.
25class 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) {
Googler727e97b2021-11-30 14:38:37 +000031 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;
Googler858c86e2021-11-26 14:19:41 +000035 }
Googler727e97b2021-11-30 14:38:37 +000036 auto [_, b_to_a_inserted] =
37 b_to_a_.try_emplace(lifetime_in_b, lifetime_in_a);
38 return b_to_a_inserted;
Googler858c86e2021-11-26 14:19:41 +000039 }
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 Versari95ce68f2022-03-24 14:44:19 +000048llvm::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 Versaricc7e6cb2022-04-05 08:08:23 -070060llvm::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 Versari95ce68f2022-03-24 14:44:19 +000066bool 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
76llvm::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);
Googler858c86e2021-11-26 14:19:41 +000089 }
Luca Versari95ce68f2022-03-24 14:44:19 +000090 ret.this_lifetimes_ = std::move(tmp);
Googler858c86e2021-11-26 14:19:41 +000091 }
92
Luca Versari95ce68f2022-03-24 14:44:19 +000093 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 Versari043a36e2022-04-08 00:55:36 -0700122bool 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 Versarid6901162022-04-08 02:59:33 -0700132llvm::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 Versaric5231632022-04-11 07:36:35 -0700143void 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 Versari95ce68f2022-03-24 14:44:19 +0000154void 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
165void 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); });
Googler858c86e2021-11-26 14:19:41 +0000169}
170
171bool 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 Versari95ce68f2022-03-24 14:44:19 +0000175 assert(param_lifetimes_.size() == other.param_lifetimes_.size());
176 assert(this_lifetimes_.has_value() == other.this_lifetimes_.has_value());
Googler858c86e2021-11-26 14:19:41 +0000177
178 // Map of equivalent lifetimes between `*this` and `other`.
179 LifetimeBijection bijection;
180
Luca Versari95ce68f2022-03-24 14:44:19 +0000181 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 });
Googler858c86e2021-11-26 14:19:41 +0000188
Luca Versari95ce68f2022-03-24 14:44:19 +0000189 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])) {
Googler858c86e2021-11-26 14:19:41 +0000192 return false;
Luca Versari95ce68f2022-03-24 14:44:19 +0000193 }
Googler858c86e2021-11-26 14:19:41 +0000194 }
195 return true;
196}
197
198std::string FunctionLifetimes::DebugString(LifetimeFormatter formatter) const {
199 std::vector<std::string> formatted_param_lifetimes;
200
Luca Versaricc7e6cb2022-04-05 08:08:23 -0700201 // Add parenteses to non-trivial nested lifetimes, i.e. fn parameters with >1
202 // lifetimes, as their DebugString does not contain parentheses.
Luca Versari6ee6b342022-04-05 05:40:52 -0700203 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 Versari95ce68f2022-03-24 14:44:19 +0000210 for (const auto& param : param_lifetimes_) {
Luca Versari6ee6b342022-04-05 05:40:52 -0700211 formatted_param_lifetimes.push_back(
212 maybe_add_parentheses(param.DebugString(formatter)));
Googler858c86e2021-11-26 14:19:41 +0000213 }
214
215 std::string result;
Luca Versari95ce68f2022-03-24 14:44:19 +0000216 if (this_lifetimes_.has_value()) {
Luca Versari6ee6b342022-04-05 05:40:52 -0700217 result = absl::StrCat(
218 maybe_add_parentheses(this_lifetimes_->DebugString(formatter)), ":");
Googler858c86e2021-11-26 14:19:41 +0000219 }
220 if (!result.empty() && !formatted_param_lifetimes.empty()) {
221 absl::StrAppend(&result, " ");
222 }
223 absl::StrAppend(&result, absl::StrJoin(formatted_param_lifetimes, ", "));
224
Luca Versari95ce68f2022-03-24 14:44:19 +0000225 if (return_lifetimes_.HasLifetimes()) {
Googler858c86e2021-11-26 14:19:41 +0000226 if (!result.empty()) {
227 absl::StrAppend(&result, " ");
228 }
Luca Versari6ee6b342022-04-05 05:40:52 -0700229 absl::StrAppend(
230 &result, "-> ",
231 maybe_add_parentheses(return_lifetimes_.DebugString(formatter)));
Googler858c86e2021-11-26 14:19:41 +0000232 }
233
234 return result;
235}
236
Googler858c86e2021-11-26 14:19:41 +0000237std::ostream& operator<<(std::ostream& os,
238 const FunctionLifetimes& func_lifetimes) {
239 return os << func_lifetimes.DebugString();
240}
241
Martin Brænne1a207c52022-04-19 00:05:38 -0700242} // namespace lifetimes
243} // namespace tidy
244} // namespace clang