[clangd] Desugar template parameter aliases in type hints

[zyounan]

Summary

This patch alleviates https://github.com/clangd/clangd/issues/1298.

Containers in C++ such as std::vector or llvm::SmallVector,
introduce a series of type aliases to adapt to generic algorithms.

Currently, If we write an declarator involving expressions with
these containers and auto placeholder, we probably obtain opaque
type alias like following:

std::vector<int> v = {1, 2, 3};
auto value = v[1]; // hint for `value`: value_type
auto *ptr = &v[0]; // hint for `ptr`: value_type *

These hints are useless for most of the time. It would be nice if we
desugar the type of value_type and print int, int * respectively
in this situation. But note we can't always prefer desugared type
since user might introduce type-aliases for brevity, where printing
sugared types makes more sense.

This patch introduces a heuristic method that displays the desugared
type that is an alias of template parameter. It merges
analogous method shouldPrintCanonicalType into maybeDesugar as well.

Previous commit for shouldPrintCanonicalType: dde8a0fe91cc

[zyounan]

Before

After

(Sorry for posting screenshots directly and bringing any inconvenience for email users.)

[zyounan]

clang-tools-extra/clangd/InlayHints.cpp

279

PrintCanonicalTypes turns on printing default template arguments, which would prevent the patch from printing, e.g., std::basic_string<char>, within the default length limitation.

std::map<std::string, int> Map;

for (auto &[Key, Value] : Map) // Key: basic_string<char, char_traits<char>, allocator<char>>, whose length exceeds the default threshold.

Is it safe to drop it now? I believe this patch can handle the case the comment mentioned.

[nridge]

Thanks, this is a nice improvement.

A couple of general comments:

• We have an existing heuristic here, should we move the logic into maybeDesugar() so it's all in one place?
• I don't think "dependent type" is the right terminology, "dependent type" means "depends on a template parameter whose value is not yet known", for example vector<T>::value_type where we don't know the value of T. But here we are talking about things like vector<int>::value_type. Maybe in place of "dependent type alias" we can say "alias for template parameter"?

clang-tools-extra/clangd/InlayHints.cpp

198

nit: it sounds like this name (PeelQualifier) is using "qualifier" to mean "pointer or reference", which is different from the meaning of the word in "QualType" (where it means "const or volatile")

maybe PeelWrappers would be a better name, since we can think of PointerType and ReferenceType as wrapping an underlying type?

201

a possible reformulation:

QualType Next;
while (!(Next = QT->getPointeeType()).isNull()) {
  QT = Next;
}
return QT;

this seems slightly cleaner to me, but I'll leave it up to you

207

this loop can also be reformulated to avoid repeating the update step:

while (true) {
  QualType Desugared = Peel(...);
  if (Desugared == QT)
    break;
  if (Desugared->getAs<...>)
    return true;
  QT = Desugared;
}

215

The only test case that seems to rely on this BuiltinType heuristic is getting int instead of size_type for array.size().

size_type doesn't seem so bad, maybe we can leave this out for now? Or do you have a more compelling motivating case for it?

235

name suggestion: maybeDesugar

(try sounds like it might fail and return something that needs to be checked like optional or Expected)

279

Unfortunately, I don't think it works in general. I tried commenting out this line and
TypeHints.StructuredBindings_TupleLike failed.

(Note, this was with the BuiltinType heuristic removed. If we keep the BuilinType heuristic, a modified version of the testcase (e.g. struct members are changed from int to a class type) still fails.)

[zyounan]

clang-tools-extra/clangd/InlayHints.cpp

279

Thank you for providing me with the case. I think the flag PrintCanonicalTypes actually controls two aspects of styles, if I understand TypePrinter correctly:

1. For type aliases (a.k.a. typedefs and using alias), the 'canonical' type (i.e., the "most" desugared type) is obtained before printing.

2. For template arguments, print default parameters even they weren't specified.

For 1, we could achieve the same goal at the caller site: For DecompositionDecl, instead of creating another different printing policy, call QualType::getCanonicalType() to get the QualType to be passed into addTypeHint. I did a modification and found that test cases from TypeHints are all passed even we disable StructuredBindingPolicy.PrintCanonicalTypes.

For 2, I think for most of the cases, printing default template parameters is an unexpected side effect. (I didn't see any test cases requiring default template parameters on structure bindings, but please correct me if I'm missing something.)

What do you think? I'd like to submit another review addressing this if it looks fine to you.

[nridge]

clang-tools-extra/clangd/InlayHints.cpp

279

What do you think? I'd like to submit another review addressing this if it looks fine to you.

+1, it sounds reasonable to me

[zyounan]

Address many comments

[zyounan]

Thank you very much for the insightful review! Regarding to your suggestion,

We have an existing heuristic here, should we move the logic into maybeDesugar() so it's all in one place?

once we merge these two functions, the overloaded addTypeHint without a PrintingPolicy parameter will merely remains one line for forwarding. As we're going to use a single PrintingPolicy after D152520, I think it would be better to eventually drop the parameter PrintingPolicy in addTypeHint in that patch.

clang-tools-extra/clangd/InlayHints.cpp

198

Good catch! I looked up the standard and found out that pointers or references are of compound types, and that 'qualified' usually goes along with 'const or volatile'.

201

Rephrased as the suggestion. (TBH, I didn't realize storing the Next instead of the Prev could make it more terse. Thanks for the hint!)

207

Cool.

215

Not that I could think of except that case. It's possible that size_type varies across different platforms, so it seems okay to remove it.

235

Frankly speaking I used to mix up these two and just learned the differences. Thank you!

279

Link to the proposed review.

[nridge]

Thanks, LGTM!

clang-tools-extra/clangd/InlayHints.cpp

196

nit: "of substituted template parameter" --> "a substituted template parmeter"

(or "of substituted template parameter type")

[zyounan]

Final update

[zyounan]

Oops. Remove extra debugging statement

[kstoimenov]

Looks like this might have broken a couple of sanitizer builds. Here is one of them: https://lab.llvm.org/buildbot/#/builders/5/builds/34387. Could you please revert or fix?
Thanks!

[zyounan]

In D151785#4417973, @kstoimenov wrote:

Looks like this might have broken a couple of sanitizer builds. Here is one of them: https://lab.llvm.org/buildbot/#/builders/5/builds/34387. Could you please revert or fix?
Thanks!

Sorry for the inconvenience. I think this issue had been fixed by https://github.com/llvm/llvm-project/commit/0e8384a0fe4f03d60cd92aba1cae074512481ca2. Does it work now? Please let me know if we still have problems.

[kstoimenov]

In D151785#4418037, @zyounan wrote:

In D151785#4417973, @kstoimenov wrote:

Looks like this might have broken a couple of sanitizer builds. Here is one of them: https://lab.llvm.org/buildbot/#/builders/5/builds/34387. Could you please revert or fix?
Thanks!

Sorry for the inconvenience. I think this issue had been fixed by https://github.com/llvm/llvm-project/commit/0e8384a0fe4f03d60cd92aba1cae074512481ca2. Does it work now? Please let me know if we still have problems.

The bot went green after the fix. Thanks.

clang-tools-extra/clangd/InlayHints.cpp

 //===--- InlayHints.cpp ------------------------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 #include "InlayHints.h"
 #include "AST.h"
 #include "Config.h"
 #include "HeuristicResolver.h"
 #include "ParsedAST.h"
 #include "SourceCode.h"
+#include "clang/AST/ASTDiagnostic.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclarationName.h"
 #include "clang/AST/ExprCXX.h"
 #include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/AST/Type.h"
 #include "clang/Basic/Builtins.h"
 #include "clang/Basic/SourceManager.h"
 #include "llvm/ADT/ScopeExit.h"
 #include <optional>
 
 namespace clang {
 namespace clangd {
 namespace {
getDesignators(const InitListExpr *Syn) {
   // We use their SourceLocation to correlate with the syntactic form later.
   llvm::DenseMap<SourceLocation, std::string> Designators;
   std::string EmptyPrefix;
   collectDesignators(Syn->isSemanticForm() ? Syn : Syn->getSemanticForm(),
                      Designators, NestedBraces, EmptyPrefix);
   return Designators;
 }
 
+// Determines if any intermediate type in desugaring QualType QT is of
+// substituted template parameter type. Ignore pointer or reference wrappers.
+bool isSugaredTemplateParameter(QualType QT) {
+  static auto PeelWrappers = [](QualType QT) {
+    // Neither `PointerType` nor `ReferenceType` is considered as sugared
+    // type. Peel it.
+    QualType Next;
+    while (!(Next = QT->getPointeeType()).isNull())
+      QT = Next;
+    return QT;
+  };
+  while (true) {
+    QualType Desugared =
+        PeelWrappers(QT->getLocallyUnqualifiedSingleStepDesugaredType());
+    if (Desugared == QT)
+      break;
+    if (Desugared->getAs<SubstTemplateTypeParmType>())
+      return true;
+    QT = Desugared;
+  }
+  return false;
+}
+
+// A simple wrapper for `clang::desugarForDiagnostic` that provides optional
+// semantic.
+std::optional<QualType> desugar(ASTContext &AST, QualType QT) {
+  bool ShouldAKA;
+  auto Desugared = clang::desugarForDiagnostic(AST, QT, ShouldAKA);
+  if (!ShouldAKA)
+    return std::nullopt;
+  return Desugared;
+}
+
+// Apply a series of heuristic methods to determine whether or not a QualType QT
+// is suitable for desugaring (e.g. getting the real name behind the using-alias
+// name). If so, return the desugared type. Otherwise, return the unchanged
+// parameter QT.
+//
+// This could be refined further. See
+// https://github.com/clangd/clangd/issues/1298.
+QualType maybeDesugar(ASTContext &AST, QualType QT) {
+  // Prefer desugared type for name that aliases the template parameters.
+  // This can prevent things like printing opaque `: type` when accessing std
+  // containers.
+  if (isSugaredTemplateParameter(QT))
+    return desugar(AST, QT).value_or(QT);
+
+  // Prefer desugared type for `decltype(expr)` specifiers.
+  if (QT->isDecltypeType())
+    return QT.getCanonicalType();
+  if (const AutoType *AT = QT->getContainedAutoType())
+    if (!AT->getDeducedType().isNull() &&
+        AT->getDeducedType()->isDecltypeType())
+      return QT.getCanonicalType();
+
+  return QT;
+}
+
 class InlayHintVisitor : public RecursiveASTVisitor<InlayHintVisitor> {
 public:
   InlayHintVisitor(std::vector<InlayHint> &Results, ParsedAST &AST,
                    const Config &Cfg, std::optional<Range> RestrictRange)
       : Results(Results), AST(AST.getASTContext()), Tokens(AST.getTokens()),
         Cfg(Cfg), RestrictRange(std::move(RestrictRange)),
         MainFileID(AST.getSourceManager().getMainFileID()),
         Resolver(AST.getHeuristicResolver()),
InlayHintVisitor(std::vector<InlayHint> &Results, ParsedAST &AST,
 
     // For structured bindings, print canonical types. This is important because
     // for bindings that use the tuple_element protocol, the non-canonical types
     // would be "tuple_element<I, A>::type".
     // For "auto", we often prefer sugared types.
     // Not setting PrintCanonicalTypes for "auto" allows
     // SuppressDefaultTemplateArgs (set by default) to have an effect.
     StructuredBindingPolicy = TypeHintPolicy;
     StructuredBindingPolicy.PrintCanonicalTypes = true;
   }
 
   bool VisitTypeLoc(TypeLoc TL) {
     if (const auto *DT = llvm::dyn_cast<DecltypeType>(TL.getType()))
       if (QualType UT = DT->getUnderlyingType(); !UT->isDependentType())
         addTypeHint(TL.getSourceRange(), UT, ": ");
     return true;
   }
std::optional<Range> getHintRange(SourceRange R) {
     // Hint must be within the main file, not e.g. a non-preamble include.
     if (SM.getFileID(Spelled->front().location()) != SM.getMainFileID() ||
         SM.getFileID(Spelled->back().location()) != SM.getMainFileID())
       return std::nullopt;
     return Range{sourceLocToPosition(SM, Spelled->front().location()),
                  sourceLocToPosition(SM, Spelled->back().endLocation())};
   }
 
-  static bool shouldPrintCanonicalType(QualType QT) {
-    // The sugared type is more useful in some cases, and the canonical
-    // type in other cases. For now, prefer the sugared type unless
-    // we are printing `decltype(expr)`. This could be refined further
-    // (see https://github.com/clangd/clangd/issues/1298).
-    if (QT->isDecltypeType())
-      return true;
-    if (const AutoType *AT = QT->getContainedAutoType())
-      if (!AT->getDeducedType().isNull() &&
-          AT->getDeducedType()->isDecltypeType())
-        return true;
-    return false;
-  }
-
   void addTypeHint(SourceRange R, QualType T, llvm::StringRef Prefix) {
-    TypeHintPolicy.PrintCanonicalTypes = shouldPrintCanonicalType(T);
     addTypeHint(R, T, Prefix, TypeHintPolicy);
   }
 
   void addTypeHint(SourceRange R, QualType T, llvm::StringRef Prefix,
                    const PrintingPolicy &Policy) {
     if (!Cfg.InlayHints.DeducedTypes || T.isNull())
       return;
 
-    std::string TypeName = T.getAsString(Policy);
-    if (Cfg.InlayHints.TypeNameLimit == 0 ||
-        TypeName.length() < Cfg.InlayHints.TypeNameLimit)
+    // The sugared type is more useful in some cases, and the canonical
+    // type in other cases.
+    auto Desugared = maybeDesugar(AST, T);
+    std::string TypeName = Desugared.getAsString(Policy);
+    if (T != Desugared && !shouldPrintTypeHint(TypeName)) {
+      // If the desugared type is too long to display, fallback to the sugared
+      // type.
+      TypeName = T.getAsString(Policy);
+    }
+    if (shouldPrintTypeHint(TypeName))
       addInlayHint(R, HintSide::Right, InlayHintKind::Type, Prefix, TypeName,
                    /*Suffix=*/"");
   }
 
   void addDesignatorHint(SourceRange R, llvm::StringRef Text) {
     addInlayHint(R, HintSide::Left, InlayHintKind::Designator,
                  /*Prefix=*/"", Text, /*Suffix=*/"=");
   }
 
+  bool shouldPrintTypeHint(llvm::StringRef TypeName) const noexcept {
+    return Cfg.InlayHints.TypeNameLimit == 0 ||
+           TypeName.size() < Cfg.InlayHints.TypeNameLimit;
+  }
+
   std::vector<InlayHint> &Results;
   ASTContext &AST;
   const syntax::TokenBuffer &Tokens;
   const Config &Cfg;
   std::optional<Range> RestrictRange;
   FileID MainFileID;
   StringRef MainFileBuf;
   const HeuristicResolver *Resolver;

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

assertTypeHints(R"cpp(
     auto $j[[s]];
   )cpp",
                   ExpectedHint{": int", "a"}, ExpectedHint{": int", "b"},
                   ExpectedHint{": int", "c"}, ExpectedHint{": int", "e"},
                   ExpectedHint{": int", "f"}, ExpectedHint{": int", "g"},
                   ExpectedHint{": int", "h"}, ExpectedHint{": int", "i"});
 }
 
+TEST(TypeHints, SubstTemplateParameterAliases) {
+  assertTypeHints(
+      R"cpp(
+  template <class T> struct allocator {};
+
+  template <class T, class A>
+  struct vector_base {
+    using pointer = T*;
+  };
+
+  template <class T, class A>
+  struct internal_iterator_type_template_we_dont_expect {};
+
+  struct my_iterator {};
+
+  template <class T, class A = allocator<T>>
+  struct vector : vector_base<T, A> {
+    using base = vector_base<T, A>;
+    typedef T value_type;
+    typedef base::pointer pointer;
+    using allocator_type = A;
+    using size_type = int;
+    using iterator = internal_iterator_type_template_we_dont_expect<T, A>;
+    using non_template_iterator = my_iterator;
+
+    value_type& operator[](int index) { return elements[index]; }
+    const value_type& at(int index) const { return elements[index]; }
+    pointer data() { return &elements[0]; }
+    allocator_type get_allocator() { return A(); }
+    size_type size() const { return 10; }
+    iterator begin() { return iterator(); }
+    non_template_iterator end() { return non_template_iterator(); }
+
+    T elements[10];
+  };
+
+  vector<int> array;
+
+  auto $no_modifier[[by_value]] = array[3];
+  auto* $ptr_modifier[[ptr]] = &array[3];
+  auto& $ref_modifier[[ref]] = array[3];
+  auto& $at[[immutable]] = array.at(3);
+
+  auto $data[[data]] = array.data();
+  auto $allocator[[alloc]] = array.get_allocator();
+  auto $size[[size]] = array.size();
+  auto $begin[[begin]] = array.begin();
+  auto $end[[end]] = array.end();
+
+
+  // If the type alias is not of substituted template parameter type,
+  // do not show desugared type.
+  using VeryLongLongTypeName = my_iterator;
+  using Short = VeryLongLongTypeName;
+
+  auto $short_name[[my_value]] = Short();
+
+  // Same applies with templates.
+  template <typename T, typename A>
+  using basic_static_vector = vector<T, A>;
+  template <typename T>
+  using static_vector = basic_static_vector<T, allocator<T>>;
+
+  auto $vector_name[[vec]] = static_vector<int>();
+  )cpp",
+      ExpectedHint{": int", "no_modifier"},
+      ExpectedHint{": int *", "ptr_modifier"},
+      ExpectedHint{": int &", "ref_modifier"},
+      ExpectedHint{": const int &", "at"}, ExpectedHint{": int *", "data"},
+      ExpectedHint{": allocator<int>", "allocator"},
+      ExpectedHint{": size_type", "size"}, ExpectedHint{": iterator", "begin"},
+      ExpectedHint{": non_template_iterator", "end"},
+      ExpectedHint{": Short", "short_name"},
+      ExpectedHint{": static_vector<int>", "vector_name"});
+}
+
 TEST(DesignatorHints, Basic) {
   assertDesignatorHints(R"cpp(
     struct S { int x, y, z; };
     S s {$x[[1]], $y[[2+2]]};
 
     int x[] = {$0[[0]], $1[[1]]};
   )cpp",
                         ExpectedHint{".x=", "x"}, ExpectedHint{".y=", "y"},