//===- LiveOrigins.h - Live Origins Analysis -------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file defines the LiveOriginAnalysis, a backward dataflow analysis that
// determines which origins are "live" at each program point. An origin is
// "live" at a program point if there's a potential future use of a pointer it
// is associated with. Liveness is "generated" by a use of an origin (e.g., a
// `UseFact` from a read of a pointer) and is "killed" (i.e., it stops being
// live) when the origin is replaced by flowing a different origin into it
// (e.g., an OriginFlow from an assignment that kills the destination).
//
// This information is used for detecting use-after-free errors, as it allows us
// to check if a live origin holds a loan to an object that has already expired.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_LIFETIMESAFETY_LIVE_ORIGINS_H
#define LLVM_CLANG_ANALYSIS_ANALYSES_LIFETIMESAFETY_LIVE_ORIGINS_H

#include "clang/Analysis/Analyses/LifetimeSafety/Facts.h"
#include "clang/Analysis/Analyses/LifetimeSafety/Origins.h"
#include "clang/Analysis/AnalysisDeclContext.h"
#include "clang/Analysis/CFG.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/ImmutableMap.h"
#include "llvm/Support/Debug.h"

namespace clang::lifetimes::internal {

using CausingFactType =
    ::llvm::PointerUnion<const UseFact *, const OriginEscapesFact *>;

enum class LivenessKind : uint8_t {
  Dead,  // Not alive
  Maybe, // Live on some path but not all paths (may-be-live)
  Must   // Live on all paths (must-be-live)
};

/// Information about why an origin is live at a program point.
struct LivenessInfo {
  /// The use that makes the origin live. If liveness is propagated from
  /// multiple uses along different paths, this will point to the use appearing
  /// earlier in the translation unit.
  /// This is 'null' when the origin is not live.
  CausingFactType CausingFact;

  /// The kind of liveness of the origin.
  /// `Must`: The origin is live on all control-flow paths from the current
  /// point to the function's exit (i.e. the current point is dominated by a set
  /// of uses).
  /// `Maybe`: indicates it is live on some but not all paths.
  ///
  /// This determines the diagnostic's confidence level.
  /// `Must`-be-alive at expiration implies a definite use-after-free,
  /// while `Maybe`-be-alive suggests a potential one on some paths.
  LivenessKind Kind;

  LivenessInfo() : CausingFact(nullptr), Kind(LivenessKind::Dead) {}
  LivenessInfo(CausingFactType CF, LivenessKind K) : CausingFact(CF), Kind(K) {}

  bool operator==(const LivenessInfo &Other) const {
    return CausingFact == Other.CausingFact && Kind == Other.Kind;
  }
  bool operator!=(const LivenessInfo &Other) const { return !(*this == Other); }

  void Profile(llvm::FoldingSetNodeID &IDBuilder) const {
    IDBuilder.AddPointer(CausingFact.getOpaqueValue());
    IDBuilder.Add(Kind);
  }
};

using LivenessMap = llvm::ImmutableMap<OriginID, LivenessInfo>;

class LiveOriginsAnalysis {
public:
  LiveOriginsAnalysis(const CFG &C, AnalysisDeclContext &AC, FactManager &F,
                      LivenessMap::Factory &SF);
  ~LiveOriginsAnalysis();

  /// Returns the set of origins that are live at a specific program point,
  /// along with the the details of the liveness.
  LivenessMap getLiveOriginsAt(ProgramPoint P) const;

  // Dump liveness values on all test points in the program.
  void dump(llvm::raw_ostream &OS,
            llvm::StringMap<ProgramPoint> TestPoints) const;

private:
  class Impl;
  std::unique_ptr<Impl> PImpl;
};

} // namespace clang::lifetimes::internal

#endif // LLVM_CLANG_ANALYSIS_ANALYSES_LIFETIMESAFETY_LIVE_ORIGINS_H