[clangd] Handle duplicate enum constants in PopulateSwitch tweak

[njames93]

Summary

If an enum has different names for the same constant, make sure only the first one declared gets added into the switch. Failing to do so results in a compiler error as 2 case labels can't represent the same value.

enum Numbers{
One,
Un = One,
Two,
Deux = Two,
Three,
Trois = Three
};

// Old behaviour
switch (<Number>) {
  case One:
  case Un:
  case Two:
  case Duex:
  case Three:
  case Trois: break;
}

// New behaviour
switch (<Number>) {
  case One:
  case Two:
  case Three: break;
}

[njames93]

Fix bug where prepare would return true erroneously when enum contains duplicated constants

[sammccall]

Thanks!
This makes sense to me, I assumed at first that the expr could be something complicated that we'd have to const-evaluate, thought clearly this already happens (and we do assume it's a ConstantExpr).

clang-tools-extra/clangd/refactor/tweaks/PopulateSwitch.cpp

115

It would still be nice to keep a high-level comment about the strategy.
(Not *this* comment of course, as this patch changes the strategy!)

132–138

why is the special case needed?

141

It looks as if we're now doing (via prepare + apply combined):

1. Collect all constants into a SmallMapVector<APSInt,bool>.
2. Iterate over cases, marking covered constants
3. Prepare returns true if there are unmarked constants
4. Collect all cases into a SmallSet<APSInt>
5. Iterate over the constants, inserting text for those not in the set.

This seems equivalent, but less redundant:

1. Collect all constants into a MapVector<APSInt, EnumConstantDecl*> (e.g. MissingEnumerators)
2. Iterate over cases, deleting covered constants
3. Prepare returns true if any constant remains
4. Iterate over the map, inserting text for every element in the map

158–159

this comment no longer holds (we're not counting anymore).

Could just say // GNU range cases are rare, we don't support them

169

why can we not hit the APValue case?

188–191

Maybe just "Skip if value already covered (possibly under a different name)"?
("try to insert... if this fails" is just echoing the code)

[njames93]

Addressed comments.
Now using a MapVector to collect all uncovered cases in prepare, then just loop over that in apply.

[njames93]

clang-tools-extra/clangd/refactor/tweaks/PopulateSwitch.cpp

132–138

It wasn't was causing a bug early on then i fixed it and it was no longer needed

141

Thats a great suggestion. I did alter it slightly using a std::pair<EnumConstantDecl*, bool> for the value. This is because it would be nice to catch the case where the switch has a duplicated case value. The other reason is its linear time to call erase on a MapVector, so its potentially O(N^2) when looping through all the cases.

[sammccall]

clang-tools-extra/clangd/refactor/tweaks/PopulateSwitch.cpp

80

I'd make the values here a struct with named fields for readability, but up to you.

143

nit: I'd add a lambda here like

auto Normalize(llvm::APSInt Val) {
  Val = Val.extOrTrunc(EnumIntWidth);
  Val.setIsSigned(EnumIsSigned);
  return Val;
};

you'll use it twice, and the callsites will be more readable

145

it's already clear at this point.

177

this says if you ever have a case statement that doesn't match an enum value, then we don't offer the tweak. Why?

182

Do we really need to specially detect or handle this?

Seems like a blind

if (Iter != EnumConstants.end())
  Iter->second.second = true; // mark as covered

would be enough here

[njames93]

clang-tools-extra/clangd/refactor/tweaks/PopulateSwitch.cpp

143

Good point.

145

I didn't know how tweaks exactly worked, like if the tweak object is instantiated for each selection or if its reused. I'll remove this.

177

If the user puts in a case statement that doesn't directly match a value, chances are they are doing something funky. In which case the tweak is likely not going to help. WDYT?

182

What are the rules for clangd tweaks on ill-formed code. I'll remove this anyhow.

[njames93]

Address comments

[sammccall]

Fantastic, thanks!

Still LG, comments optional.

clang-tools-extra/clangd/refactor/tweaks/PopulateSwitch.cpp

61

for this kind of purpose, we'd typically just use struct EnumAndCovered { const ECD *Enumerator; bool Covered; } without encapsulation. But this is fine.

I think a name like ExpectedCase might hint a little more at the purpose. Up to you.

177

I agree it signals that exhaustively enumerating the cases *might* not be useful. (It still could be though, e.g. imagine an enum that can't easily be extended where someone's added a sentinel value).

Since this is a code action rather than a diagnostic, I'd lean towards still offering the action, but either seems reasonable.
If you're going to bail out in this case, it definitely deserves a comment.

182

Basically, don't crash on ill-formed code, try not to produce wildly invalid syntax.
Beyond that, we only really care about problems that come up a lot in practice.

(That said, if there are duplicated cases, I'm not sure that should stop us applying this tweak)

clang-tools-extra/clangd/refactor/tweaks/PopulateSwitch.cpp

 #include "refactor/Tweak.h"
 #include "support/Logger.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/Stmt.h"
 #include "clang/AST/Type.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Tooling/Core/Replacement.h"
-#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/MapVector.h"
+#include "llvm/ADT/STLExtras.h"
 #include <cassert>
 #include <string>
 
 namespace clang {
 namespace clangd {
 namespace {
 class PopulateSwitch : public Tweak {
   const char *id() const override;
   bool prepare(const Selection &Sel) override;
   Expected<Effect> apply(const Selection &Sel) override;
   std::string title() const override { return "Populate switch"; }
   llvm::StringLiteral kind() const override {
     return CodeAction::QUICKFIX_KIND;
   }
 
 private:
+  class ExpectedCase {
+  public:
+    ExpectedCase(const EnumConstantDecl *Decl) : Data(Decl, false) {}
+    bool isCovered() const { return Data.getInt(); }
+    void setCovered(bool Val = true) { Data.setInt(Val); }
+    const EnumConstantDecl *getEnumConstant() const {
+      return Data.getPointer();
+    }
+
+  private:
+    llvm::PointerIntPair<const EnumConstantDecl *, 1, bool> Data;
+  };
+
   const DeclContext *DeclCtx = nullptr;
   const SwitchStmt *Switch = nullptr;
   const CompoundStmt *Body = nullptr;
   const EnumType *EnumT = nullptr;
   const EnumDecl *EnumD = nullptr;
+  // Maps the Enum values to the EnumConstantDecl and a bool signifying if its
+  // covered in the switch.
+  llvm::MapVector<llvm::APSInt, ExpectedCase> ExpectedCases;
 };
 
 REGISTER_TWEAK(PopulateSwitch)
 
 bool PopulateSwitch::prepare(const Selection &Sel) {
   const SelectionTree::Node *CA = Sel.ASTSelection.commonAncestor();
   if (!CA)
     return false;
bool PopulateSwitch::prepare(const Selection &Sel) {
   EnumT = Cond->getType()->getAsAdjusted<EnumType>();
   if (!EnumT)
     return false;
 
   EnumD = EnumT->getDecl();
   if (!EnumD)
     return false;
 
-  // We trigger if there are fewer cases than enum values (and no case covers
-  // multiple values). This guarantees we'll have at least one case to insert.
-  // We don't yet determine what the cases are, as that means evaluating
-  // expressions.
-  auto I = EnumD->enumerator_begin();
-  auto E = EnumD->enumerator_end();
+  // We trigger if there are any values in the enum that aren't covered by the
+  // switch.
+
+  ASTContext &Ctx = Sel.AST->getASTContext();
+
+  unsigned EnumIntWidth = Ctx.getIntWidth(QualType(EnumT, 0));
+  bool EnumIsSigned = EnumT->isSignedIntegerOrEnumerationType();
+
+  auto Normalize = [&](llvm::APSInt Val) {
+    Val = Val.extOrTrunc(EnumIntWidth);
+    Val.setIsSigned(EnumIsSigned);
+    return Val;
+  };
+
+  for (auto *EnumConstant : EnumD->enumerators()) {
+    ExpectedCases.insert(
+        std::make_pair(Normalize(EnumConstant->getInitVal()), EnumConstant));
+  }
 
-  for (const SwitchCase *CaseList = Switch->getSwitchCaseList();
-       CaseList && I != E; CaseList = CaseList->getNextSwitchCase(), I++) {
+  for (const SwitchCase *CaseList = Switch->getSwitchCaseList(); CaseList;
+       CaseList = CaseList->getNextSwitchCase()) {
     // Default likely intends to cover cases we'd insert.
     if (isa<DefaultStmt>(CaseList))
       return false;
 
     const CaseStmt *CS = cast<CaseStmt>(CaseList);
-    // Case statement covers multiple values, so just counting doesn't work.
+
+    // GNU range cases are rare, we don't support them.
     if (CS->caseStmtIsGNURange())
       return false;
 
     // Case expression is not a constant expression or is value-dependent,
     // so we may not be able to work out which cases are covered.
     const ConstantExpr *CE = dyn_cast<ConstantExpr>(CS->getLHS());
     if (!CE || CE->isValueDependent())
       return false;
+
+    // Unsure if this case could ever come up, but prevents an unreachable
+    // executing in getResultAsAPSInt.
+    if (CE->getResultStorageKind() == ConstantExpr::RSK_None)
+      return false;
+    auto Iter = ExpectedCases.find(Normalize(CE->getResultAsAPSInt()));
+    if (Iter != ExpectedCases.end())
+      Iter->second.setCovered();
   }
 
-  // Only suggest tweak if we have more enumerators than cases.
-  return I != E;
+  return !llvm::all_of(ExpectedCases,
+                       [](auto &Pair) { return Pair.second.isCovered(); });
 }
 
 Expected<Tweak::Effect> PopulateSwitch::apply(const Selection &Sel) {
   ASTContext &Ctx = Sel.AST->getASTContext();
 
-  // Get the enum's integer width and signedness, for adjusting case literals.
-  unsigned EnumIntWidth = Ctx.getIntWidth(QualType(EnumT, 0));
-  bool EnumIsSigned = EnumT->isSignedIntegerOrEnumerationType();
-
-  llvm::SmallSet<llvm::APSInt, 32> ExistingEnumerators;
-  for (const SwitchCase *CaseList = Switch->getSwitchCaseList(); CaseList;
-       CaseList = CaseList->getNextSwitchCase()) {
-    const CaseStmt *CS = cast<CaseStmt>(CaseList);
-    assert(!CS->caseStmtIsGNURange());
-    const ConstantExpr *CE = cast<ConstantExpr>(CS->getLHS());
-    assert(!CE->isValueDependent());
-    llvm::APSInt Val = CE->getResultAsAPSInt();
-    Val = Val.extOrTrunc(EnumIntWidth);
-    Val.setIsSigned(EnumIsSigned);
-    ExistingEnumerators.insert(Val);
-  }
-
   SourceLocation Loc = Body->getRBracLoc();
   ASTContext &DeclASTCtx = DeclCtx->getParentASTContext();
 
-  std::string Text;
-  for (EnumConstantDecl *Enumerator : EnumD->enumerators()) {
-    if (ExistingEnumerators.contains(Enumerator->getInitVal()))
+  llvm::SmallString<256> Text;
+  for (auto &EnumConstant : ExpectedCases) {
+    // Skip any enum constants already covered
+    if (EnumConstant.second.isCovered())
       continue;
 
-    Text += "case ";
-    Text += getQualification(DeclASTCtx, DeclCtx, Loc, EnumD);
-    if (EnumD->isScoped()) {
-      Text += EnumD->getName();
-      Text += "::";
-    }
-    Text += Enumerator->getName();
-    Text += ":";
+    Text.append({"case ", getQualification(DeclASTCtx, DeclCtx, Loc, EnumD)});
+    if (EnumD->isScoped())
+      Text.append({EnumD->getName(), "::"});
+    Text.append({EnumConstant.second.getEnumConstant()->getName(), ":"});
   }
 
   assert(!Text.empty() && "No enumerators to insert!");
   Text += "break;";
 
   const SourceManager &SM = Ctx.getSourceManager();
   return Effect::mainFileEdit(
       SM, tooling::Replacements(tooling::Replacement(SM, Loc, 0, Text)));
 }
 } // namespace
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/unittests/TweakTests.cpp

Case Cases[]{
             namespace ns { enum Enum {A}; }
             void function() { ^switch (ns::A) {} }
           )"",
           R""(
             namespace ns { enum Enum {A}; }
             void function() { switch (ns::A) {case ns::A:break;} }
           )"",
       },
+      {
+          // Duplicated constant names
+          Function,
+          R""(enum Enum {A,B,b=B}; ^switch (A) {})"",
+          R""(enum Enum {A,B,b=B}; switch (A) {case A:case B:break;})"",
+      },
+      {
+          // Duplicated constant names all in switch
+          Function,
+          R""(enum Enum {A,B,b=B}; ^switch (A) {case A:case B:break;})"",
+          "unavailable",
+      },
   };
 
   for (const auto &Case : Cases) {
     Context = Case.Context;
     EXPECT_EQ(apply(Case.TestSource), Case.ExpectedSource);
   }
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang

llvm/include/llvm/ADT/DenseMapInfo.h

 //===- llvm/ADT/DenseMapInfo.h - Type traits for DenseMap -------*- 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 DenseMapInfo traits for DenseMap.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_DENSEMAPINFO_H
 #define LLVM_ADT_DENSEMAPINFO_H
 
 #include "llvm/ADT/APInt.h"
+#include "llvm/ADT/APSInt.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/StringRef.h"
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <utility>
 
static unsigned getHashValue(const APInt &Key) {
     return static_cast<unsigned>(hash_value(Key));
   }
 
   static bool isEqual(const APInt &LHS, const APInt &RHS) {
     return LHS.getBitWidth() == RHS.getBitWidth() && LHS == RHS;
   }
 };
 
+/// Provide DenseMapInfo for APSInt, using the DenseMapInfo for APInt.
+template <> struct DenseMapInfo<APSInt> {
+  static inline APSInt getEmptyKey() {
+    return APSInt(DenseMapInfo<APInt>::getEmptyKey());
+  }
+
+  static inline APSInt getTombstoneKey() {
+    return APSInt(DenseMapInfo<APInt>::getTombstoneKey());
+  }
+
+  static unsigned getHashValue(const APSInt &Key) {
+    return static_cast<unsigned>(hash_value(Key));
+  }
+
+  static bool isEqual(const APSInt &LHS, const APSInt &RHS) {
+    return LHS.getBitWidth() == RHS.getBitWidth() &&
+           LHS.isUnsigned() == RHS.isUnsigned() && LHS == RHS;
+  }
+};
+
 } // end namespace llvm
 
 #endif // LLVM_ADT_DENSEMAPINFO_H