[clang][dataflow] Add a lattice to track source locations.

[ymandel]

Summary

This patch adds a simpe lattice used to collect source loctions. An intended application is to track errors found in code during an analysis.

[sgatev]

clang/include/clang/Analysis/FlowSensitive/SourceLocationsLattice.h

14

Remove the last _ for consistency with the other headers.

47

Add an empty line after this member to separate it from the next?

clang/lib/Analysis/FlowSensitive/SourceLocationsLattice.cpp

46

Call this OS? It seems to be common.

[sgatev]

clang/include/clang/Analysis/FlowSensitive/SourceLocationsLattice.h

27

Doc comments start with ///.

56

Doc comments start with ///.

57

Can you please add tests for this too?

[ymandel]

Address comments

[ymandel]

clang/include/clang/Analysis/FlowSensitive/SourceLocationsLattice.h

57

I'm not sure what I would test, since it (intentionally) has no guaranteed API. Do you have something particular in mind? I generally avoid testing things like DebugString because we don't want users to rely on them.

[xazax.hun]

Is there anything special about SourceLocations? I wonder whether we just want a templated PowerSet lattice and instantiate it with SourceLocations.

[ymandel]

In D120890#3357438, @xazax.hun wrote:

Is there anything special about SourceLocations? I wonder whether we just want a templated PowerSet lattice and instantiate it with SourceLocations.

Not really. Just that we use this lattice in a bunch of analyses for "unsafe access", like std::optional and absl::Statusor and (eventually) pointers. So, it seems generally useful as is. I agree that we should have core powerset lattice, its just that doing so will require a little more design effort (similar to the map lattice I added). Happy to add that as a FIXME (which we plan to start tacking with github issues soon!), if that sounds good to you.

[xazax.hun]

In D120890#3357454, @ymandel wrote:

In D120890#3357438, @xazax.hun wrote:

Is there anything special about SourceLocations? I wonder whether we just want a templated PowerSet lattice and instantiate it with SourceLocations.

Not really. Just that we use this lattice in a bunch of analyses for "unsafe access", like std::optional and absl::Statusor and (eventually) pointers. So, it seems generally useful as is. I agree that we should have core powerset lattice, its just that doing so will require a little more design effort (similar to the map lattice I added). Happy to add that as a FIXME (which we plan to start tacking with github issues soon!), if that sounds good to you.

Sounds good, thanks!

[ymandel]

added FIXME

[sgatev]

clang/include/clang/Analysis/FlowSensitive/SourceLocationsLattice.h

57

Fair point. Let's keep it as is.

clang/include/clang/Analysis/FlowSensitive/SourceLocationsLattice.h

+//===-- SourceLocationsLattice.h --------------------------------*- 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 a lattice that collects source locations of interest.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_SOURCELOCATIONS_LATTICE_H
+#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_SOURCELOCATIONS_LATTICE_H
+
+#include "clang/AST/ASTContext.h"
+#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
+#include "clang/Basic/SourceLocation.h"
+#include "llvm/ADT/DenseSet.h"
+#include <string>
+#include <utility>
+
+namespace clang {
+namespace dataflow {
+
+/// Lattice for dataflow analysis that keeps track of a set of source locations.
+///
+/// Bottom is the empty set, join is set union, and equality is set equality.
+///
+/// FIXME: Generalize into a (templated) PowerSetLattice.
+class SourceLocationsLattice {
+public:
+  SourceLocationsLattice() = default;
+
+  explicit SourceLocationsLattice(llvm::DenseSet<SourceLocation> Locs)
+      : Locs(std::move(Locs)) {}
+
+  bool operator==(const SourceLocationsLattice &Other) const {
+    return Locs == Other.Locs;
+  }
+
+  bool operator!=(const SourceLocationsLattice &Other) const {
+    return !(*this == Other);
+  }
+
+  LatticeJoinEffect join(const SourceLocationsLattice &Other);
+
+  llvm::DenseSet<SourceLocation> &getSourceLocations() { return Locs; }
+
+  const llvm::DenseSet<SourceLocation> &getSourceLocations() const {
+    return Locs;
+  }
+
+private:
+  llvm::DenseSet<SourceLocation> Locs;
+};
+
+/// Returns a string that represents the source locations of the lattice.
+std::string DebugString(const SourceLocationsLattice &Lattice,
+                        const ASTContext &Context);
+
+} // namespace dataflow
+} // namespace clang
+
+#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_SOURCELOCATIONS_LATTICE_H

clang/lib/Analysis/FlowSensitive/CMakeLists.txt

 add_clang_library(clangAnalysisFlowSensitive
   ControlFlowContext.cpp
   DataflowAnalysisContext.cpp
   DataflowEnvironment.cpp
+  SourceLocationsLattice.cpp
   Transfer.cpp
   TypeErasedDataflowAnalysis.cpp
   WatchedLiteralsSolver.cpp
 
   LINK_LIBS
   clangAnalysis
   clangAST
+  clangBasic
   )

clang/lib/Analysis/FlowSensitive/SourceLocationsLattice.cpp

+//===- SourceLocationsLattice.cpp -----------------------------------------===//
+//
+// 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 implements a lattice that collects source locations of interest.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/FlowSensitive/SourceLocationsLattice.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/raw_ostream.h"
+#include <algorithm>
+#include <string>
+#include <vector>
+
+namespace clang {
+namespace dataflow {
+
+LatticeJoinEffect
+SourceLocationsLattice::join(const SourceLocationsLattice &Other) {
+  auto SizeBefore = Locs.size();
+  Locs.insert(Other.Locs.begin(), Other.Locs.end());
+  return SizeBefore == Locs.size() ? LatticeJoinEffect::Unchanged
+                                   : LatticeJoinEffect::Changed;
+}
+
+std::string DebugString(const SourceLocationsLattice &Lattice,
+                        const ASTContext &Context) {
+  if (Lattice.getSourceLocations().empty())
+    return "";
+
+  std::vector<std::string> Locations;
+  Locations.reserve(Lattice.getSourceLocations().size());
+  for (const clang::SourceLocation &Loc : Lattice.getSourceLocations()) {
+    Locations.push_back(Loc.printToString(Context.getSourceManager()));
+  }
+  std::sort(Locations.begin(), Locations.end());
+  std::string result;
+  llvm::raw_string_ostream OS(result);
+  llvm::interleaveComma(Locations, OS);
+  return result;
+}
+
+} // namespace dataflow
+} // namespace clang

clang/unittests/Analysis/FlowSensitive/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   FrontendOpenMP
   Support
   )
 
 add_clang_unittest(ClangAnalysisFlowSensitiveTests
   DataflowAnalysisContextTest.cpp
   DataflowEnvironmentTest.cpp
   MapLatticeTest.cpp
   MultiVarConstantPropagationTest.cpp
   SingleVarConstantPropagationTest.cpp
+  SourceLocationsLatticeTest.cpp
   TestingSupport.cpp
   TestingSupportTest.cpp
   TransferTest.cpp
   TypeErasedDataflowAnalysisTest.cpp
   SolverTest.cpp
   )
 
 clang_target_link_libraries(ClangAnalysisFlowSensitiveTests

clang/unittests/Analysis/FlowSensitive/SourceLocationsLatticeTest.cpp

+//===- unittests/Analysis/FlowSensitive/SourceLocationsLatticeTest.cpp ----===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/FlowSensitive/SourceLocationsLattice.h"
+
+#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
+#include "clang/Basic/SourceLocation.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace dataflow {
+namespace {
+
+TEST(SourceLocationsLatticeTest, Comparison) {
+  const SourceLocationsLattice Bottom;
+  const SourceLocationsLattice NonBottom(
+      {SourceLocation::getFromRawEncoding(0)});
+
+  EXPECT_TRUE(Bottom == Bottom);
+  EXPECT_FALSE(Bottom == NonBottom);
+  EXPECT_FALSE(NonBottom == Bottom);
+  EXPECT_TRUE(NonBottom == NonBottom);
+
+  EXPECT_FALSE(Bottom != Bottom);
+  EXPECT_TRUE(Bottom != NonBottom);
+  EXPECT_TRUE(NonBottom != Bottom);
+  EXPECT_FALSE(NonBottom != NonBottom);
+}
+
+TEST(SourceLocationsLatticeTest, Join) {
+  const SourceLocationsLattice Bottom;
+  const SourceLocationsLattice NonBottom(
+      {SourceLocation::getFromRawEncoding(0)});
+  {
+    SourceLocationsLattice LHS = Bottom;
+    const SourceLocationsLattice RHS = Bottom;
+    EXPECT_EQ(LHS.join(RHS), LatticeJoinEffect::Unchanged);
+    EXPECT_EQ(LHS, Bottom);
+  }
+  {
+    SourceLocationsLattice LHS = NonBottom;
+    const SourceLocationsLattice RHS = Bottom;
+    EXPECT_EQ(LHS.join(RHS), LatticeJoinEffect::Unchanged);
+    EXPECT_EQ(LHS, NonBottom);
+  }
+  {
+    SourceLocationsLattice LHS = Bottom;
+    const SourceLocationsLattice RHS = NonBottom;
+    EXPECT_EQ(LHS.join(RHS), LatticeJoinEffect::Changed);
+    EXPECT_EQ(LHS, NonBottom);
+  }
+  {
+    SourceLocationsLattice LHS = NonBottom;
+    const SourceLocationsLattice RHS = NonBottom;
+    EXPECT_EQ(LHS.join(RHS), LatticeJoinEffect::Unchanged);
+    EXPECT_EQ(LHS, NonBottom);
+  }
+}
+
+} // namespace
+} // namespace dataflow
+} // namespace clang