[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!)

117

why is the special case needed?

126

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

141

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

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

151

why can we not hit the APValue case?

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

117

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

126

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

68

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

137

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

139

it's already clear at this point.

159

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

164

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

137

Good point.

139

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.

159

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?

164

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

62

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.

159

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.

164

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/MapVector.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallSet.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:
   const DeclContext *DeclCtx = nullptr;
   const SwitchStmt *Switch = nullptr;
   const CompoundStmt *Body = nullptr;
   const EnumType *EnumT = nullptr;
   const EnumDecl *EnumD = nullptr;
 };
 
 REGISTER_TWEAK(PopulateSwitch)
 
 bool PopulateSwitch::prepare(const Selection &Sel) {
   const SelectionTree::Node *CA = Sel.ASTSelection.commonAncestor();
   if (!CA)
     return false;
 
   const Stmt *CAStmt = CA->ASTNode.get<Stmt>();
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();
+  // Special case of the empty enum
+  if (EnumD->enumerator_begin() == EnumD->enumerator_end())
+    return false;
+
+  ASTContext &Ctx = Sel.AST->getASTContext();
+
+  unsigned EnumIntWidth = Ctx.getIntWidth(QualType(EnumT, 0));
+  bool EnumIsSigned = EnumT->isSignedIntegerOrEnumerationType();
+
+  llvm::SmallMapVector<llvm::APSInt, bool, 32> EnumConstants;
+  for (auto *EnumConstant : EnumD->enumerators()) {
+    llvm::APSInt Val = EnumConstant->getInitVal();
+    Val = Val.extOrTrunc(EnumIntWidth);
+    Val.setIsSigned(EnumIsSigned);
+    EnumConstants.insert(std::make_pair(Val, false));
+  }
 
-  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.
     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;
+
+    if (CE->getResultStorageKind() != ConstantExpr::RSK_Int64)
+      return false;
+    llvm::APSInt Val = CE->getResultAsAPSInt();
+    Val = Val.extOrTrunc(EnumIntWidth);
+    Val.setIsSigned(EnumIsSigned);
+    auto *Iter = EnumConstants.find(Val);
+    if (Iter == EnumConstants.end())
+      return false;
+    Iter->second = true;
+    continue;
   }
 
-  // Only suggest tweak if we have more enumerators than cases.
-  return I != E;
+  return !llvm::all_of(EnumConstants, [](auto &Pair) { return Pair.second; });
 }
 
 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();
 
for (const SwitchCase *CaseList = Switch->getSwitchCaseList(); CaseList;
     ExistingEnumerators.insert(Val);
   }
 
   SourceLocation Loc = Body->getRBracLoc();
   ASTContext &DeclASTCtx = DeclCtx->getParentASTContext();
 
   std::string Text;
   for (EnumConstantDecl *Enumerator : EnumD->enumerators()) {
-    if (ExistingEnumerators.contains(Enumerator->getInitVal()))
+    // Try to insert this Enumerator into the set. If this fails, the value was
+    // either already there to begin with or we have already added it using a
+    // different name.
+    if (!ExistingEnumerators.insert(Enumerator->getInitVal()).second)
       continue;
 
     Text += "case ";
     Text += getQualification(DeclASTCtx, DeclCtx, Loc, EnumD);
     if (EnumD->isScoped()) {
       Text += EnumD->getName();
       Text += "::";
     }

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