Add LifetimeConstraints to the lattice.

First step of a UnifyLifetimes -> constraint system migration for inference.

PiperOrigin-RevId: 465551174

lifetime_analysis/BUILD

diff --git a/lifetime_analysis/BUILD b/lifetime_analysis/BUILD
index 6c90377..ebfdfa8 100644
--- a/lifetime_analysis/BUILD
+++ b/lifetime_analysis/BUILD
@@ -83,10 +83,22 @@
 )
 
 cc_library(
+    name = "lifetime_constraints",
+    srcs = ["lifetime_constraints.cc"],
+    hdrs = ["lifetime_constraints.h"],
+    deps = [
+        "//lifetime_annotations:lifetime",
+        "@llvm-project//clang:analysis",
+        "@llvm-project//llvm:Support",
+    ],
+)
+
+cc_library(
     name = "lifetime_lattice",
     srcs = ["lifetime_lattice.cc"],
     hdrs = ["lifetime_lattice.h"],
     deps = [
+        ":lifetime_constraints",
         ":points_to_map",
         "@llvm-project//clang:analysis",
         "@llvm-project//llvm:Support",

lifetime_analysis/lifetime_constraints.cc

diff --git a/lifetime_analysis/lifetime_constraints.cc b/lifetime_analysis/lifetime_constraints.cc
new file mode 100644
index 0000000..fe0e00e
--- /dev/null
+++ b/lifetime_analysis/lifetime_constraints.cc
@@ -0,0 +1,23 @@
+// Part of the Crubit project, under the Apache License v2.0 with LLVM
+// Exceptions. See /LICENSE for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+
+#include "lifetime_analysis/lifetime_constraints.h"
+
+namespace clang {
+namespace tidy {
+namespace lifetimes {
+
+clang::dataflow::LatticeJoinEffect LifetimeConstraints::join(
+    const LifetimeConstraints& other) {
+  bool changed = false;
+  for (auto p : other.outlives_constraints_) {
+    changed |= outlives_constraints_.insert(p).second;
+  }
+  return changed ? clang::dataflow::LatticeJoinEffect::Changed
+                 : clang::dataflow::LatticeJoinEffect::Unchanged;
+}
+
+}  // namespace lifetimes
+}  // namespace tidy
+}  // namespace clang

lifetime_analysis/lifetime_constraints.h

diff --git a/lifetime_analysis/lifetime_constraints.h b/lifetime_analysis/lifetime_constraints.h
new file mode 100644
index 0000000..43bf77c
--- /dev/null
+++ b/lifetime_analysis/lifetime_constraints.h
@@ -0,0 +1,39 @@
+// Part of the Crubit project, under the Apache License v2.0 with LLVM
+// Exceptions. See /LICENSE for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+
+#ifndef THIRD_PARTY_CRUBIT_LIFETIME_ANALYSIS_LIFETIME_CONSTRAINTS_H_
+#define THIRD_PARTY_CRUBIT_LIFETIME_ANALYSIS_LIFETIME_CONSTRAINTS_H_
+
+#include "lifetime_annotations/lifetime.h"
+#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
+#include "llvm/ADT/DenseSet.h"
+
+namespace clang {
+namespace tidy {
+namespace lifetimes {
+
+class LifetimeConstraints {
+ public:
+  // Creates empty constraints.
+  LifetimeConstraints() {}
+
+  // Imposes the constraint shorter <= longer.
+  void AddOutlivesConstraint(Lifetime shorter, Lifetime longer) {
+    outlives_constraints_.insert({shorter, longer});
+  }
+
+  // Merges this set of constraints with the provided constraints, returning
+  // the effect of the operation.
+  clang::dataflow::LatticeJoinEffect join(const LifetimeConstraints& other);
+
+ private:
+  // Constraints of the form p.first <= p.second
+  llvm::DenseSet<std::pair<Lifetime, Lifetime>> outlives_constraints_;
+};
+
+}  // namespace lifetimes
+}  // namespace tidy
+}  // namespace clang
+
+#endif  // THIRD_PARTY_CRUBIT_LIFETIME_ANALYSIS_LIFETIME_CONSTRAINTS_H_

lifetime_analysis/lifetime_lattice.cc

diff --git a/lifetime_analysis/lifetime_lattice.cc b/lifetime_analysis/lifetime_lattice.cc
index 03478d0..81d85ff 100644
--- a/lifetime_analysis/lifetime_lattice.cc
+++ b/lifetime_analysis/lifetime_lattice.cc
@@ -26,12 +26,22 @@
 
 PointsToMap& LifetimeLattice::PointsTo() {
   assert(!IsError());
-  return std::get<PointsToMap>(var_);
+  return std::get<0>(var_).first;
 }
 
 const PointsToMap& LifetimeLattice::PointsTo() const {
   assert(!IsError());
-  return std::get<PointsToMap>(var_);
+  return std::get<0>(var_).first;
+}
+
+LifetimeConstraints& LifetimeLattice::Constraints() {
+  assert(!IsError());
+  return std::get<0>(var_).second;
+}
+
+const LifetimeConstraints& LifetimeLattice::Constraints() const {
+  assert(!IsError());
+  return std::get<0>(var_).second;
 }
 
 llvm::StringRef LifetimeLattice::Error() const {
@@ -53,12 +63,15 @@
     return clang::dataflow::LatticeJoinEffect::Changed;
   }
 
+  auto constraints_effect = Constraints().join(other.Constraints());
+
   PointsToMap joined_points_to_map = PointsTo().Union(other.PointsTo());
-  if (PointsTo() == joined_points_to_map) {
+  if (PointsTo() == joined_points_to_map &&
+      constraints_effect == clang::dataflow::LatticeJoinEffect::Unchanged) {
     return clang::dataflow::LatticeJoinEffect::Unchanged;
   }
 
-  *this = LifetimeLattice(std::move(joined_points_to_map));
+  PointsTo() = std::move(joined_points_to_map);
   return clang::dataflow::LatticeJoinEffect::Changed;
 }
 

lifetime_analysis/lifetime_lattice.h

diff --git a/lifetime_analysis/lifetime_lattice.h b/lifetime_analysis/lifetime_lattice.h
index 68e8a0e..9830d20 100644
--- a/lifetime_analysis/lifetime_lattice.h
+++ b/lifetime_analysis/lifetime_lattice.h
@@ -9,6 +9,7 @@
 #include <utility>
 #include <variant>
 
+#include "lifetime_analysis/lifetime_constraints.h"
 #include "lifetime_analysis/points_to_map.h"
 #include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
@@ -20,7 +21,7 @@
 
 class LifetimeLattice {
  public:
-  // Creates a lattice holding an empty points-to map.
+  // Creates a lattice holding an empty points-to map and empty constraints.
   LifetimeLattice() = default;
 
   LifetimeLattice(const LifetimeLattice&) = default;
@@ -28,9 +29,9 @@
   LifetimeLattice& operator=(const LifetimeLattice&) = default;
   LifetimeLattice& operator=(LifetimeLattice&&) = default;
 
-  // Creates a lattice containing the given points-to map.
+  // Creates a lattice containing the given points-to map and empty constraints.
   explicit LifetimeLattice(PointsToMap points_to_map)
-      : var_(std::move(points_to_map)) {}
+      : var_(std::make_pair(std::move(points_to_map), LifetimeConstraints())) {}
 
   // Creates an error state containing the error message `err`.
   explicit LifetimeLattice(std::string err) : var_(err) {}
@@ -40,6 +41,11 @@
   PointsToMap& PointsTo();
   const PointsToMap& PointsTo() const;
 
+  // Returns the lifetime constraints.
+  // Precondition: !IsError().
+  LifetimeConstraints& Constraints();
+  const LifetimeConstraints& Constraints() const;
+
   // Returns whether the lattice is in the error state.
   bool IsError() const { return std::holds_alternative<std::string>(var_); }
 
@@ -64,7 +70,7 @@
   }
 
  private:
-  std::variant<PointsToMap, std::string> var_;
+  std::variant<std::pair<PointsToMap, LifetimeConstraints>, std::string> var_;
 };
 
 }  // namespace lifetimes