[SemaObjC] Add a warning for dictionary literals with duplicate keys

[erik.pilkington]

Summary

Duplicate keys in a literal break NSDictionary's invariants.

Fixes rdar://50454461

[erik.pilkington]

Ping!

[rjmccall]

Some part of me wishes we could use expression profiling or ODR hashing or something like that for this, but I guess the semantics we're going for don't really match.

clang/lib/Sema/SemaExprObjC.cpp

948

Does EvaluateAsInt really just fail cleanly if the argument doesn't have integral type?

[bendjones]

This addresses what we had an issue with on the tin. I’ll defer to @rjmccall for the specifics at the clang level.

clang/lib/Sema/SemaExprObjC.cpp

948

I thought it fails if a type can’t be “some how” converted to an integral type. The loose quotes are key here.

[erik.pilkington]

clang/lib/Sema/SemaExprObjC.cpp

948

Yeah, it checks if the expression has an integral type before evaluating: https://github.com/llvm/llvm-project/blob/1de4e5693317c1e34cae4740d6c9c6733e5ed3fd/clang/lib/AST/ExprConstant.cpp#L13830

[rjmccall]

Anyway, LGTM.

clang/lib/Sema/SemaExprObjC.cpp

948

Alright. That's interesting, I would've given even odds that it would assert.

clang/include/clang/Basic/DiagnosticSemaKinds.td

def warn_concatenated_nsarray_literal : Warning<
   "possibly missing a comma">,
   InGroup<ObjCStringConcatenation>;
 def note_objc_literal_comparison_isequal : Note<
   "use 'isEqual:' instead">;
 def warn_objc_collection_literal_element : Warning<
   "object of type %0 is not compatible with "
   "%select{array element type|dictionary key type|dictionary value type}1 %2">,
   InGroup<ObjCLiteralConversion>;
+def warn_nsdictionary_duplicate_key : Warning<
+  "duplicate key in dictionary literal">,
+  InGroup<DiagGroup<"objc-dictionary-duplicate-keys">>;
+def note_nsdictionary_duplicate_key_here : Note<
+  "previous equal key is here">;
 def err_swift_param_attr_not_swiftcall : Error<
   "'%0' parameter can only be used with swiftcall calling convention">;
 def err_swift_indirect_result_not_first : Error<
   "'swift_indirect_result' parameters must be first parameters of function">;
 def err_swift_error_result_not_after_swift_context : Error<
   "'swift_error_result' parameter must follow 'swift_context' parameter">;
 def err_swift_abi_parameter_wrong_type : Error<
   "'%0' parameter must have pointer%select{| to unqualified pointer}1 type; "

clang/lib/Sema/SemaExprObjC.cpp

QualType Ty
     = Context.getObjCObjectPointerType(
                                     Context.getObjCInterfaceType(NSArrayDecl));
 
   return MaybeBindToTemporary(
            ObjCArrayLiteral::Create(Context, Elements, Ty,
                                     ArrayWithObjectsMethod, SR));
 }
 
+/// Check for duplicate keys in an ObjC dictionary literal. For instance:
+///   NSDictionary *nd = @{ @"foo" : @"bar", @"foo" : @"baz" };
+static void
+CheckObjCDictionaryLiteralDuplicateKeys(Sema &S,
+                                        ObjCDictionaryLiteral *Literal) {
+  if (Literal->isValueDependent() || Literal->isTypeDependent())
+    return;
+
+  // NSNumber has quite relaxed equality semantics (for instance, @YES is
+  // considered equal to @1.0). For now, ignore floating points and just do a
+  // bit-width and sign agnostic integer compare.
+  struct APSIntCompare {
+    bool operator()(const llvm::APSInt &LHS, const llvm::APSInt &RHS) const {
+      return llvm::APSInt::compareValues(LHS, RHS) < 0;
+    }
+  };
+
+  llvm::DenseMap<StringRef, SourceLocation> StringKeys;
+  std::map<llvm::APSInt, SourceLocation, APSIntCompare> IntegralKeys;
+
+  auto checkOneKey = [&](auto &Map, const auto &Key, SourceLocation Loc) {
+    auto Pair = Map.insert({Key, Loc});
+    if (!Pair.second) {
+      S.Diag(Loc, diag::warn_nsdictionary_duplicate_key);
+      S.Diag(Pair.first->second, diag::note_nsdictionary_duplicate_key_here);
+    }
+  };
+
+  for (unsigned Idx = 0, End = Literal->getNumElements(); Idx != End; ++Idx) {
+    Expr *Key = Literal->getKeyValueElement(Idx).Key->IgnoreParenImpCasts();
+
+    if (auto *StrLit = dyn_cast<ObjCStringLiteral>(Key)) {
+      StringRef Bytes = StrLit->getString()->getBytes();
+      SourceLocation Loc = StrLit->getExprLoc();
+      checkOneKey(StringKeys, Bytes, Loc);
+    }
+
+    if (auto *BE = dyn_cast<ObjCBoxedExpr>(Key)) {
+      Expr *Boxed = BE->getSubExpr();
+      SourceLocation Loc = BE->getExprLoc();
+
+      // Check for @("foo").
+      if (auto *Str = dyn_cast<StringLiteral>(Boxed->IgnoreParenImpCasts())) {
+        checkOneKey(StringKeys, Str->getBytes(), Loc);
+        continue;
+      }
+
+      Expr::EvalResult Result;
+      if (Boxed->EvaluateAsInt(Result, S.getASTContext(),
+                               Expr::SE_AllowSideEffects)) {
+        checkOneKey(IntegralKeys, Result.Val.getInt(), Loc);
+      }
+    }
+  }
+}
+
 ExprResult Sema::BuildObjCDictionaryLiteral(SourceRange SR,
                               MutableArrayRef<ObjCDictionaryElement> Elements) {
   SourceLocation Loc = SR.getBegin();
 
   if (!NSDictionaryDecl) {
     NSDictionaryDecl = LookupObjCInterfaceDeclForLiteral(*this, Loc,
                                                          Sema::LK_Dictionary);
     if (!NSDictionaryDecl) {
if (!Element.Key->containsUnexpandedParameterPack() &&
           << SourceRange(Element.Key->getBeginLoc(),
                          Element.Value->getEndLoc());
       return ExprError();
     }
 
     HasPackExpansions = true;
   }
 
-  QualType Ty
-    = Context.getObjCObjectPointerType(
-                                Context.getObjCInterfaceType(NSDictionaryDecl));
-  return MaybeBindToTemporary(ObjCDictionaryLiteral::Create(
-      Context, Elements, HasPackExpansions, Ty,
-      DictionaryWithObjectsMethod, SR));
+  QualType Ty = Context.getObjCObjectPointerType(
+
+  auto *Literal =
+      ObjCDictionaryLiteral::Create(Context, Elements, HasPackExpansions, Ty,
+                                    DictionaryWithObjectsMethod, SR);
+  CheckObjCDictionaryLiteralDuplicateKeys(*this, Literal);
+  return MaybeBindToTemporary(Literal);
 }
 
 ExprResult Sema::BuildObjCEncodeExpression(SourceLocation AtLoc,
                                       TypeSourceInfo *EncodedTypeInfo,
                                       SourceLocation RParenLoc) {
   QualType EncodedType = EncodedTypeInfo->getType();
   QualType StrTy;
   if (EncodedType->isDependentType())

clang/test/SemaObjC/dictionary-literal-duplicates.m

+// RUN: %clang_cc1 -Wno-objc-root-class %s -verify
+// RUN: %clang_cc1 -xobjective-c++ -Wno-objc-root-class %s -verify
+
+#define YES __objc_yes
+#define NO __objc_no
+
+@interface NSNumber
++(instancetype)numberWithChar:(char)value;
++(instancetype)numberWithInt:(int)value;
++(instancetype)numberWithDouble:(double)value;
++(instancetype)numberWithBool:(unsigned char)value;
++(instancetype)numberWithUnsignedLong:(unsigned long)value;
++(instancetype)numberWithLongLong:(long long) value;
++(instancetype)numberWithUnsignedInt:(unsigned)value;
+@end
+
+@interface NSString
+@end
+
+@interface NSDictionary
++ (instancetype)dictionaryWithObjects:(const id[])objects
+                              forKeys:(const id[])keys
+                                count:(unsigned long)cnt;
+@end
+
+void test() {
+  NSDictionary *t1 = @{
+    @"foo" : @0, // expected-note 2 {{previous equal key is here}}
+    @"foo" : @0, // expected-warning{{duplicate key in dictionary literal}}
+    @("foo") : @0, // expected-warning{{duplicate key in dictionary literal}}
+    @"foo\0" : @0,
+
+    @1 : @0, // expected-note + {{previous equal key is here}}
+    @YES : @0, // expected-warning{{duplicate key in dictionary literal}}
+    @'\1' : @0, // expected-warning{{duplicate key in dictionary literal}}
+    @1 : @0, // expected-warning{{duplicate key in dictionary literal}}
+    @1ul : @0, // expected-warning{{duplicate key in dictionary literal}}
+    @1ll : @0, // expected-warning{{duplicate key in dictionary literal}}
+#ifdef __cplusplus
+    @true : @0, // expected-warning{{duplicate key in dictionary literal}}
+#endif
+    @1.0 : @0, // FIXME: should warn
+
+    @-1 : @0, // expected-note + {{previous equal key is here}}
+    @4294967295u : @0, // no warning
+    @-1ll : @0, // expected-warning{{duplicate key in dictionary literal}}
+    @(NO-YES) : @0, // expected-warning{{duplicate key in dictionary literal}}
+  };
+}
+
+#ifdef __cplusplus
+template <class... Ts> void variadic(Ts... ts) {
+  NSDictionary *nd = @{
+    ts : @0 ...,
+    @0 : ts ... // expected-warning 2 {{duplicate key in dictionary literal}} expected-note 2 {{previous equal key is here}}
+  };
+}
+
+void call_variadic() {
+  variadic(@0, @1, @2); // expected-note {{in instantiation}}
+}
+#endif