[Sema][Typo] Fix assertion failure for expressions with multiple typos

[dgoldman]

Summary

As Typo Resolution can create new TypoExprs while resolving typos,
it is necessary to recurse through the expression to search for more
typos.

This should fix the assertion failure in clang::Sema::~Sema():

`DelayedTypos.empty() && "Uncorrected typos!"`

Notes:

• For expressions with multiple typos, we only give suggestions if we are able to resolve all typos in the expression
• This patch is similar to D37521 except that it does not eagerly commit to a correction for the first typo in the expression. Instead, it will search for corrections which fix all of the typos in the expression.

[rsmith]

lib/Sema/SemaExprCXX.cpp

7713–7714

What prevents diagnostics from being emitted for TypoExprs we create for an outer transform that we end up discarding? Eg, in:

struct Y {};
struct Z { int value; };
struct A {
  Y get_me_a_Y();
};
struct B {
  Z get_me_a_Z();
};
A make_an_A();
B make_a_B();
int f() {
  return make_an_E().get_me_a_Z().value;
}

I'm concerned that we will:

• try correcting make_me_an_E (TypoExpr T0) to make_me_an_A (because that correction has the minimum edit distance) and discover that there is no get_me_a_Z member, creating a new TypoExpr T1, and recurse:
  • try correcting get_me_a_Z (TypoExpr T1) to get_me_a_Y and discover that there is no value member
  • no correction works: bail out of recursive step
• try correcting make_me_an_E (TypoExpr T0) to make_me_a_B and succeed

But now we still have T1 in our list of TypoExprs, and will presumably diagnose it (and take action below if it turned out to be ambiguous etc).

7818–7820

What happens if an ambiguous TypoExpr is created as a result of one of the outer level transformations?

In that case, I think that we will try alternatives for that TypoExpr here, but that TypoExpr is not in the expression we're transforming (it was created within RecursiveTransformLoop and isn't part of E), so we're just redoing the same transformation we already did but with typo-correction disabled. This means that the transform will fail (because we hit a typo and can't correct it), so we'll accept the original set of corrections despite them being ambiguous.

[dgoldman]

• Fix diagnostics for ignored TypoExprs

[dgoldman]

lib/Sema/SemaExprCXX.cpp

7713–7714

Fixed by discarding the failed TypoExprs

7818–7820

So what do you recommend here? Checking for the non-ambiguity in RecursiveTransformLoop itself?

[dgoldman]

• Fix discarded correction test

[rsmith]

lib/Sema/SemaExprCXX.cpp

7818–7820

Suggestion: in the recursive transform, if we find a potential ambiguity, check whether it's actually ambiguous before returning. If it is ambiguous, fail out of the entire typo-correction process: one of our tied-for-best candidates was ambiguous, so we deem the overall typo-correction process to be ambiguous. And if not, then carry on as in your current patch.

[dgoldman]

lib/Sema/SemaExprCXX.cpp

7818–7820

Will submit a follow up patch to handle this, I think I'll likely rewrite the ambiguity handling to remove the AmbiguousTypoExprs bit.

[dgoldman]

• Remove unused State variable

[dgoldman]

• Move if empty check back

[dgoldman]

• Fix ambiguity handling and add more tests

[dgoldman]

• Add another test and fix up comment

[rsmith]

Thanks, this looks good; just some nits.

lib/Sema/SemaExprCXX.cpp

7616

Please capitalize this parameter name to match the surrounding code style.

7620–7621

Reflow to 80 columns.

7686

outIsAmbiguous -> IsAmbiguous (we don't use an out prefix for output parameters).

7694–7695

Use std::move here.

7696–7699

Call TypoExprs.clear() rather than copying from a default-constructed object.

7723–7724

And std::move here too.

7778–7779

Apply clang-format here. (Or: add space after while on the first line, and indent the second line so it begins in the same column as (Next =[...]).

7781–7785

Reverse the condition of this if so you can early-exit from the loop and remove the else.

7819

isAmbiguous -> IsAmbiguous.

[dgoldman]

• Minor fixes

[dgoldman]

lib/Sema/SemaExprCXX.cpp

7755–7757

Should I do the same std::move and clear here as well?

[rsmith]

lib/Sema/SemaExprCXX.cpp

7755–7757

Yes, please.

[dgoldman]

• Minor fixes

[dgoldman]

• Bug fixes

[rsmith]

Thanks, LGTM. Do you need someone to commit this for you?

[dgoldman]

In D62648#1596535, @rsmith wrote:

Thanks, LGTM. Do you need someone to commit this for you?

Nope, I can commit it. There's still one outstanding issue though: typo-correction-cxx11.cpp is still failing with the DelayedTypos.empty() && "Uncorrected typos!" error, looking into how I can handle it.

[dgoldman]

• Fix test failure: typo-correction-cxx11.cpp

Make sure that TryTransform clears any TypoExprs that are created
if it returns an invalid ExprResult (as the new TypoExprs are unreachable
from the result).

[rsmith]

I don't think you need to change the TreeTranform base class to support this; TreeTransform::TransformExpr is an extension point which you can override from TransformTypos to inject the custom logic you need. But I also don't think this TreeTransform::TransformExpr approach works in general anyway, as noted below.

lib/Sema/TreeTransform.h

3485–3489 ↗

(On Diff #211757)

It's not safe to assume that all created TypoExprs will be produced by TransformExpr. We might (for example) produce a new TypoExpr for the callee expression while transforming a CallExpr, and you won't catch that here.

It would seem cleaner and more robust to me to collect the typos produced during typo correction from within Sema::createDelayedTypo. (Eg, set some state on Sema for the duration of typo correction, and use that state to communicate any created typos back from createDelayedTypo to typo correction.)

[dgoldman]

Fix test failure via TransformTypos

• Add a new property on Sema to track newly created Typos and use this from within TransformTypos in order to delete any Typos that are unreachable (tested in typo-correction-cxx11.cpp)

[dgoldman]

• remove extra newline

lib/Sema/SemaExprCXX.cpp

class TransformTypos : public TreeTransform<TransformTypos> {
   llvm::SmallSetVector<TypoExpr *, 2> TypoExprs, AmbiguousTypoExprs;
   llvm::SmallDenseMap<TypoExpr *, ExprResult, 2> TransformCache;
   llvm::SmallDenseMap<OverloadExpr *, Expr *, 4> OverloadResolution;
 
   /// Emit diagnostics for all of the TypoExprs encountered.
   /// If the TypoExprs were successfully corrected, then the diagnostics should
   /// suggest the corrections. Otherwise the diagnostics will not suggest
   /// anything (having been passed an empty TypoCorrection).
-  void EmitAllDiagnostics() {
+  void EmitAllDiagnostics(bool isAmbiguous) {
     for (TypoExpr *TE : TypoExprs) {
       auto &State = SemaRef.getTypoExprState(TE);
       if (State.DiagHandler) {
-        TypoCorrection TC = State.Consumer->getCurrentCorrection();
-        ExprResult Replacement = TransformCache[TE];
+        TypoCorrection TC = isAmbiguous ? TypoCorrection() : State.Consumer->getCurrentCorrection();
+        ExprResult Replacement = isAmbiguous ? ExprError() : TransformCache[TE];
 
         // Extract the NamedDecl from the transformed TypoExpr and add it to the
         // TypoCorrection, replacing the existing decls. This ensures the right
         // NamedDecl is used in diagnostics e.g. in the case where overload
         // resolution was used to select one from several possible decls that
         // had been stored in the TypoCorrection.
         if (auto *ND = getDeclFromExpr(
                 Replacement.isInvalid() ? nullptr : Replacement.get()))
ExprResult TryTransform(Expr *E) {
     Sema::SFINAETrap Trap(SemaRef);
     ExprResult Res = TransformExpr(E);
     if (Trap.hasErrorOccurred() || Res.isInvalid())
       return ExprError();
 
     return ExprFilter(Res.get());
   }
 
+  // Since correcting typos may intoduce new TypoExprs, this function
+  // checks for new TypoExprs and recurses if it finds any. Note that it will
+  // only succeed if it is able to correct all typos in the given expression.
+  ExprResult CheckForRecursiveTypos(ExprResult Res, bool &outIsAmbiguous) {
+    if (Res.isInvalid()) {
+      return Res;
+    }
+    // Check to see if any new TypoExprs were created. If so, we need to recurse
+    // to check their validity.
+    Expr *FixedExpr = Res.get();
+
+    auto SavedTypoExprs = TypoExprs;
+    auto SavedAmbiguousTypoExprs = AmbiguousTypoExprs;
+    llvm::SmallSetVector<TypoExpr *, 2>
+        RecursiveTypoExprs, RecursiveAmbiguousTypoExprs;
+    TypoExprs = RecursiveTypoExprs;
+    AmbiguousTypoExprs = RecursiveAmbiguousTypoExprs;
+
+    FindTypoExprs(TypoExprs).TraverseStmt(FixedExpr);
+    if (!TypoExprs.empty()) {
+      // Recurse to handle newly created TypoExprs. If we're not able to
+      // handle them, discard these TypoExprs.
+      ExprResult RecurResult =
+          RecursiveTransformLoop(FixedExpr, outIsAmbiguous);
+      if (RecurResult.isInvalid()) {
+        Res = ExprError();
+        // Recursive corrections didn't work, wipe them away and don't add
+        // them to the TypoExprs set.
+        for (auto TE : TypoExprs) {
+          TransformCache.erase(TE);
+          SemaRef.clearDelayedTypo(TE);
+        }
+      } else {
+        // TypoExpr is valid: add newly created TypoExprs since we were
+        // able to correct them.
+        Res = RecurResult;
+        SavedTypoExprs.set_union(TypoExprs);
+      }
+    }
+
+    TypoExprs = SavedTypoExprs;
+    AmbiguousTypoExprs = SavedAmbiguousTypoExprs;
+
+    return Res;
+  }
+
+  // Try to transform the given expression, looping through the correction
+  // candidates with `CheckAndAdvanceTypoExprCorrectionStreams`.
+  //
+  // If valid ambiguous typo corrections are seen, `outIsAmbiguous` is set to
+  // true and this method immediately will return an `ExprError`.
+  ExprResult RecursiveTransformLoop(Expr *E, bool &outIsAmbiguous) {
+    ExprResult Res;
+    while (true) {
+      Res = CheckForRecursiveTypos(TryTransform(E), outIsAmbiguous);
+
+      // Recursion encountered an ambiguous correction. This means that our
+      // correction itself is ambiguous, so stop now.
+      if (outIsAmbiguous)
+        break;
+
+      // If the transform is still valid after checking for any new typos,
+      // it's good to go.
+      if (!Res.isInvalid())
+        break;
+
+      // The transform was invalid, see if we have any TypoExprs with untried
+      // correction candidates.
+      if (!CheckAndAdvanceTypoExprCorrectionStreams())
+        break;
+    }
+
+    // If we found a valid result, double check to make sure it's not ambiguous.
+    if (!outIsAmbiguous && !Res.isInvalid() && !AmbiguousTypoExprs.empty()) {
+      llvm::SmallDenseMap<TypoExpr *, ExprResult, 2> NewTransformCache;
+      auto SavedTransformCache = TransformCache;
+      TransformCache = NewTransformCache;
+      // Ensure none of the TypoExprs have multiple typo correction candidates
+      // with the same edit length that pass all the checks and filters.
+      while (!AmbiguousTypoExprs.empty()) {
+        auto TE  = AmbiguousTypoExprs.back();
+        auto &State = SemaRef.getTypoExprState(TE);
+        State.Consumer->saveCurrentPosition();
+
+        TypoCorrection TC = State.Consumer->peekNextCorrection();
+        TypoCorrection Next;
+        do {
+          ExprResult AmbigRes = CheckForRecursiveTypos(TryTransform(TE), outIsAmbiguous);
+          if (!AmbigRes.isInvalid() || outIsAmbiguous) {
+            State.Consumer->resetCorrectionStream();
+            SavedTransformCache.erase(TE);
+            Res = ExprError();
+            outIsAmbiguous = true;
+            break;
+          }
+        } while((Next = State.Consumer->peekNextCorrection()) &&
+            Next.getEditDistance(false) == TC.getEditDistance(false));
+
+        if (!outIsAmbiguous) {
+          AmbiguousTypoExprs.remove(TE);
+          State.Consumer->restoreSavedPosition();
+        } else
+          break;
+      }
+      TransformCache = SavedTransformCache;
+    }
+    return Res;
+  }
+
 public:
   TransformTypos(Sema &SemaRef, VarDecl *InitDecl, llvm::function_ref<ExprResult(Expr *)> Filter)
       : BaseTransform(SemaRef), InitDecl(InitDecl), ExprFilter(Filter) {}
 
   ExprResult RebuildCallExpr(Expr *Callee, SourceLocation LParenLoc,
                                    MultiExprArg Args,
                                    SourceLocation RParenLoc,
                                    Expr *ExecConfig = nullptr) {
ExprResult RebuildCallExpr(Expr *Callee, SourceLocation LParenLoc,
     }
     return Result;
   }
 
   ExprResult TransformLambdaExpr(LambdaExpr *E) { return Owned(E); }
 
   ExprResult TransformBlockExpr(BlockExpr *E) { return Owned(E); }
 
   ExprResult Transform(Expr *E) {
-    ExprResult Res;
-    while (true) {
-      Res = TryTransform(E);
-
-      // Exit if either the transform was valid or if there were no TypoExprs
-      // to transform that still have any untried correction candidates..
-      if (!Res.isInvalid() ||
-          !CheckAndAdvanceTypoExprCorrectionStreams())
-        break;
-    }
-
-    // Ensure none of the TypoExprs have multiple typo correction candidates
-    // with the same edit length that pass all the checks and filters.
-    // TODO: Properly handle various permutations of possible corrections when
-    // there is more than one potentially ambiguous typo correction.
-    // Also, disable typo correction while attempting the transform when
-    // handling potentially ambiguous typo corrections as any new TypoExprs will
-    // have been introduced by the application of one of the correction
-    // candidates and add little to no value if corrected.
-    SemaRef.DisableTypoCorrection = true;
-    while (!AmbiguousTypoExprs.empty()) {
-      auto TE  = AmbiguousTypoExprs.back();
-      auto Cached = TransformCache[TE];
-      auto &State = SemaRef.getTypoExprState(TE);
-      State.Consumer->saveCurrentPosition();
-      TransformCache.erase(TE);
-      if (!TryTransform(E).isInvalid()) {
-        State.Consumer->resetCorrectionStream();
-        TransformCache.erase(TE);
-        Res = ExprError();
-        break;
-      }
-      AmbiguousTypoExprs.remove(TE);
-      State.Consumer->restoreSavedPosition();
-      TransformCache[TE] = Cached;
-    }
-    SemaRef.DisableTypoCorrection = false;
+    bool isAmbiguous = false;
+    ExprResult Res = RecursiveTransformLoop(E, isAmbiguous);
 
-    // Ensure that all of the TypoExprs within the current Expr have been found.
     if (!Res.isUsable())
       FindTypoExprs(TypoExprs).TraverseStmt(E);
 
-    EmitAllDiagnostics();
+    EmitAllDiagnostics(isAmbiguous);
 
     return Res;
   }
 
   ExprResult TransformTypoExpr(TypoExpr *E) {
     // If the TypoExpr hasn't been seen before, record it. Otherwise, return the
     // cached transformation result if there is one and the TypoExpr isn't the
     // first one that was encountered.

test/Sema/typo-correction-recursive.cpp

+// RUN: %clang_cc1 -fsyntax-only -verify %s
+
+// Check the following typo correction behavior:
+// - multiple typos in a single member call chain are all diagnosed
+// - no typos are diagnosed for multiple typos in an expression when not all
+//   typos can be corrected
+
+class DeepClass
+{
+public:
+  void trigger() const;  // expected-note {{'trigger' declared here}}
+};
+
+class Y
+{
+public:
+  const DeepClass& getX() const { return m_deepInstance; }  // expected-note {{'getX' declared here}}
+private:
+  DeepClass m_deepInstance;
+  int m_n;
+};
+
+class Z
+{
+public:
+  const Y& getY0() const { return m_y0; }  // expected-note {{'getY0' declared here}}
+  const Y& getActiveY() const { return m_y0; }
+
+private:
+  Y m_y0;
+  Y m_y1;
+};
+
+Z z_obj;
+
+void testMultipleCorrections()
+{
+  z_obj.getY2().  // expected-error {{no member named 'getY2' in 'Z'; did you mean 'getY0'}}
+      getM().     // expected-error {{no member named 'getM' in 'Y'; did you mean 'getX'}}
+      triggee();  // expected-error {{no member named 'triggee' in 'DeepClass'; did you mean 'trigger'}}
+}
+
+void testNoCorrections()
+{
+  z_obj.getY2().  // expected-error {{no member named 'getY2' in 'Z'}}
+      getM().
+      thisDoesntSeemToMakeSense();
+}
+
+struct C {};
+struct D { int value; };
+struct A {
+  C get_me_a_C();
+};
+struct B {
+  D get_me_a_D();  // expected-note {{'get_me_a_D' declared here}}
+};
+class Scope {
+public:
+  A make_an_A();
+  B make_a_B();  // expected-note {{'make_a_B' declared here}}
+};
+
+Scope scope_obj;
+
+int testDiscardedCorrections() {
+  return scope_obj.make_an_E().  // expected-error {{no member named 'make_an_E' in 'Scope'; did you mean 'make_a_B'}}
+      get_me_a_Z().value;        // expected-error {{no member named 'get_me_a_Z' in 'B'; did you mean 'get_me_a_D'}}
+}
+
+class AmbiguousHelper {
+public:
+  int helpMe();
+  int helpBe();
+};
+class Ambiguous {
+public:
+  int calculateA();
+  int calculateB();
+
+  AmbiguousHelper getHelp1();
+  AmbiguousHelper getHelp2();
+};
+
+Ambiguous ambiguous_obj;
+
+int testDirectAmbiguousCorrection() {
+  return ambiguous_obj.calculateZ();  // expected-error {{no member named 'calculateZ' in 'Ambiguous'}}
+}
+
+int testRecursiveAmbiguousCorrection() {
+  return ambiguous_obj.getHelp3().    // expected-error {{no member named 'getHelp3' in 'Ambiguous'}}
+      helpCe();
+}
+
+
+class DeepAmbiguityHelper {
+public:
+  DeepAmbiguityHelper& help1();
+  DeepAmbiguityHelper& help2();
+
+  DeepAmbiguityHelper& methodA();
+  DeepAmbiguityHelper& somethingMethodB();
+  DeepAmbiguityHelper& functionC();
+  DeepAmbiguityHelper& deepMethodD();
+  DeepAmbiguityHelper& asDeepAsItGets();
+};
+
+DeepAmbiguityHelper deep_obj;
+
+int testDeepAmbiguity() {
+  deep_obj.
+      methodB(). // expected-error {{no member named 'methodB' in 'DeepAmbiguityHelper'}}
+      somethingMethodC().
+      functionD().
+      deepMethodD().
+      help3().
+      asDeepASItGet().
+      functionE();
+}