Home | History | Annotate | Download | only in Sema 
      1 //===--- TypoCorrection.h - Class for typo correction results ---*- C++ -*-===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This file defines the TypoCorrection class, which stores the results of
     11 // Sema's typo correction (Sema::CorrectTypo).
     12 //
     13 //===----------------------------------------------------------------------===//
     14 
     15 #ifndef LLVM_CLANG_SEMA_TYPOCORRECTION_H
     16 #define LLVM_CLANG_SEMA_TYPOCORRECTION_H
     17 
     18 #include "clang/AST/DeclCXX.h"
     19 #include "clang/Sema/DeclSpec.h"
     20 #include "clang/Sema/Ownership.h"
     21 #include "llvm/ADT/SmallVector.h"
     22 
     23 namespace clang {
     24 
     25 /// @brief Simple class containing the result of Sema::CorrectTypo
     26 class TypoCorrection {
     27 public:
     28   // "Distance" for unusable corrections
     29   static const unsigned InvalidDistance = ~0U;
     30   // The largest distance still considered valid (larger edit distances are
     31   // mapped to InvalidDistance by getEditDistance).
     32   static const unsigned MaximumDistance = 10000U;
     33 
     34   // Relative weightings of the "edit distance" components. The higher the
     35   // weight, the more of a penalty to fitness the component will give (higher
     36   // weights mean greater contribution to the total edit distance, with the
     37   // best correction candidates having the lowest edit distance).
     38   static const unsigned CharDistanceWeight = 100U;
     39   static const unsigned QualifierDistanceWeight = 110U;
     40   static const unsigned CallbackDistanceWeight = 150U;
     41 
     42   TypoCorrection(const DeclarationName &Name, NamedDecl *NameDecl,
     43                  NestedNameSpecifier *NNS = nullptr, unsigned CharDistance = 0,
     44                  unsigned QualifierDistance = 0)
     45       : CorrectionName(Name), CorrectionNameSpec(NNS),
     46         CharDistance(CharDistance), QualifierDistance(QualifierDistance),
     47         CallbackDistance(0), ForceSpecifierReplacement(false),
     48         RequiresImport(false) {
     49     if (NameDecl)
     50       CorrectionDecls.push_back(NameDecl);
     51   }
     52 
     53   TypoCorrection(NamedDecl *Name, NestedNameSpecifier *NNS = nullptr,
     54                  unsigned CharDistance = 0)
     55       : CorrectionName(Name->getDeclName()), CorrectionNameSpec(NNS),
     56         CharDistance(CharDistance), QualifierDistance(0), CallbackDistance(0),
     57         ForceSpecifierReplacement(false), RequiresImport(false) {
     58     if (Name)
     59       CorrectionDecls.push_back(Name);
     60   }
     61 
     62   TypoCorrection(DeclarationName Name, NestedNameSpecifier *NNS = nullptr,
     63                  unsigned CharDistance = 0)
     64       : CorrectionName(Name), CorrectionNameSpec(NNS),
     65         CharDistance(CharDistance), QualifierDistance(0), CallbackDistance(0),
     66         ForceSpecifierReplacement(false), RequiresImport(false) {}
     67 
     68   TypoCorrection()
     69       : CorrectionNameSpec(nullptr), CharDistance(0), QualifierDistance(0),
     70         CallbackDistance(0), ForceSpecifierReplacement(false),
     71         RequiresImport(false) {}
     72 
     73   /// \brief Gets the DeclarationName of the typo correction
     74   DeclarationName getCorrection() const { return CorrectionName; }
     75   IdentifierInfo *getCorrectionAsIdentifierInfo() const {
     76     return CorrectionName.getAsIdentifierInfo();
     77   }
     78 
     79   /// \brief Gets the NestedNameSpecifier needed to use the typo correction
     80   NestedNameSpecifier *getCorrectionSpecifier() const {
     81     return CorrectionNameSpec;
     82   }
     83   void setCorrectionSpecifier(NestedNameSpecifier *NNS) {
     84     CorrectionNameSpec = NNS;
     85     ForceSpecifierReplacement = (NNS != nullptr);
     86   }
     87 
     88   void WillReplaceSpecifier(bool ForceReplacement) {
     89     ForceSpecifierReplacement = ForceReplacement;
     90   }
     91 
     92   bool WillReplaceSpecifier() const {
     93     return ForceSpecifierReplacement;
     94   }
     95 
     96   void setQualifierDistance(unsigned ED) {
     97     QualifierDistance = ED;
     98   }
     99 
    100   void setCallbackDistance(unsigned ED) {
    101     CallbackDistance = ED;
    102   }
    103 
    104   // Convert the given weighted edit distance to a roughly equivalent number of
    105   // single-character edits (typically for comparison to the length of the
    106   // string being edited).
    107   static unsigned NormalizeEditDistance(unsigned ED) {
    108     if (ED > MaximumDistance)
    109       return InvalidDistance;
    110     return (ED + CharDistanceWeight / 2) / CharDistanceWeight;
    111   }
    112 
    113   /// \brief Gets the "edit distance" of the typo correction from the typo.
    114   /// If Normalized is true, scale the distance down by the CharDistanceWeight
    115   /// to return the edit distance in terms of single-character edits.
    116   unsigned getEditDistance(bool Normalized = true) const {
    117     if (CharDistance > MaximumDistance || QualifierDistance > MaximumDistance ||
    118         CallbackDistance > MaximumDistance)
    119       return InvalidDistance;
    120     unsigned ED =
    121         CharDistance * CharDistanceWeight +
    122         QualifierDistance * QualifierDistanceWeight +
    123         CallbackDistance * CallbackDistanceWeight;
    124     if (ED > MaximumDistance)
    125       return InvalidDistance;
    126     // Half the CharDistanceWeight is added to ED to simulate rounding since
    127     // integer division truncates the value (i.e. round-to-nearest-int instead
    128     // of round-to-zero).
    129     return Normalized ? NormalizeEditDistance(ED) : ED;
    130   }
    131 
    132   /// \brief Get the correction declaration found by name lookup (before we
    133   /// looked through using shadow declarations and the like).
    134   NamedDecl *getFoundDecl() const {
    135     return hasCorrectionDecl() ? *(CorrectionDecls.begin()) : nullptr;
    136   }
    137 
    138   /// \brief Gets the pointer to the declaration of the typo correction
    139   NamedDecl *getCorrectionDecl() const {
    140     auto *D = getFoundDecl();
    141     return D ? D->getUnderlyingDecl() : nullptr;
    142   }
    143   template <class DeclClass>
    144   DeclClass *getCorrectionDeclAs() const {
    145     return dyn_cast_or_null<DeclClass>(getCorrectionDecl());
    146   }
    147 
    148   /// \brief Clears the list of NamedDecls.
    149   void ClearCorrectionDecls() {
    150     CorrectionDecls.clear();
    151   }
    152 
    153   /// \brief Clears the list of NamedDecls before adding the new one.
    154   void setCorrectionDecl(NamedDecl *CDecl) {
    155     CorrectionDecls.clear();
    156     addCorrectionDecl(CDecl);
    157   }
    158 
    159   /// \brief Clears the list of NamedDecls and adds the given set.
    160   void setCorrectionDecls(ArrayRef<NamedDecl*> Decls) {
    161     CorrectionDecls.clear();
    162     CorrectionDecls.insert(CorrectionDecls.begin(), Decls.begin(), Decls.end());
    163   }
    164 
    165   /// \brief Add the given NamedDecl to the list of NamedDecls that are the
    166   /// declarations associated with the DeclarationName of this TypoCorrection
    167   void addCorrectionDecl(NamedDecl *CDecl);
    168 
    169   std::string getAsString(const LangOptions &LO) const;
    170   std::string getQuoted(const LangOptions &LO) const {
    171     return "'" + getAsString(LO) + "'";
    172   }
    173 
    174   /// \brief Returns whether this TypoCorrection has a non-empty DeclarationName
    175   explicit operator bool() const { return bool(CorrectionName); }
    176 
    177   /// \brief Mark this TypoCorrection as being a keyword.
    178   /// Since addCorrectionDeclsand setCorrectionDecl don't allow NULL to be
    179   /// added to the list of the correction's NamedDecl pointers, NULL is added
    180   /// as the only element in the list to mark this TypoCorrection as a keyword.
    181   void makeKeyword() {
    182     CorrectionDecls.clear();
    183     CorrectionDecls.push_back(nullptr);
    184     ForceSpecifierReplacement = true;
    185   }
    186 
    187   // Check if this TypoCorrection is a keyword by checking if the first
    188   // item in CorrectionDecls is NULL.
    189   bool isKeyword() const {
    190     return !CorrectionDecls.empty() && CorrectionDecls.front() == nullptr;
    191   }
    192 
    193   // Check if this TypoCorrection is the given keyword.
    194   template<std::size_t StrLen>
    195   bool isKeyword(const char (&Str)[StrLen]) const {
    196     return isKeyword() && getCorrectionAsIdentifierInfo()->isStr(Str);
    197   }
    198 
    199   // Returns true if the correction either is a keyword or has a known decl.
    200   bool isResolved() const { return !CorrectionDecls.empty(); }
    201 
    202   bool isOverloaded() const {
    203     return CorrectionDecls.size() > 1;
    204   }
    205 
    206   void setCorrectionRange(CXXScopeSpec *SS,
    207                           const DeclarationNameInfo &TypoName) {
    208     CorrectionRange = TypoName.getSourceRange();
    209     if (ForceSpecifierReplacement && SS && !SS->isEmpty())
    210       CorrectionRange.setBegin(SS->getBeginLoc());
    211   }
    212 
    213   SourceRange getCorrectionRange() const {
    214     return CorrectionRange;
    215   }
    216 
    217   typedef SmallVectorImpl<NamedDecl *>::iterator decl_iterator;
    218   decl_iterator begin() {
    219     return isKeyword() ? CorrectionDecls.end() : CorrectionDecls.begin();
    220   }
    221   decl_iterator end() { return CorrectionDecls.end(); }
    222   typedef SmallVectorImpl<NamedDecl *>::const_iterator const_decl_iterator;
    223   const_decl_iterator begin() const {
    224     return isKeyword() ? CorrectionDecls.end() : CorrectionDecls.begin();
    225   }
    226   const_decl_iterator end() const { return CorrectionDecls.end(); }
    227 
    228   /// \brief Returns whether this typo correction is correcting to a
    229   /// declaration that was declared in a module that has not been imported.
    230   bool requiresImport() const { return RequiresImport; }
    231   void setRequiresImport(bool Req) { RequiresImport = Req; }
    232 
    233 private:
    234   bool hasCorrectionDecl() const {
    235     return (!isKeyword() && !CorrectionDecls.empty());
    236   }
    237 
    238   // Results.
    239   DeclarationName CorrectionName;
    240   NestedNameSpecifier *CorrectionNameSpec;
    241   SmallVector<NamedDecl *, 1> CorrectionDecls;
    242   unsigned CharDistance;
    243   unsigned QualifierDistance;
    244   unsigned CallbackDistance;
    245   SourceRange CorrectionRange;
    246   bool ForceSpecifierReplacement;
    247   bool RequiresImport;
    248 };
    249 
    250 /// @brief Base class for callback objects used by Sema::CorrectTypo to check
    251 /// the validity of a potential typo correction.
    252 class CorrectionCandidateCallback {
    253 public:
    254   static const unsigned InvalidDistance = TypoCorrection::InvalidDistance;
    255 
    256   explicit CorrectionCandidateCallback(IdentifierInfo *Typo = nullptr,
    257                                        NestedNameSpecifier *TypoNNS = nullptr)
    258       : WantTypeSpecifiers(true), WantExpressionKeywords(true),
    259         WantCXXNamedCasts(true), WantFunctionLikeCasts(true),
    260         WantRemainingKeywords(true), WantObjCSuper(false),
    261         IsObjCIvarLookup(false), IsAddressOfOperand(false), Typo(Typo),
    262         TypoNNS(TypoNNS) {}
    263 
    264   virtual ~CorrectionCandidateCallback() {}
    265 
    266   /// \brief Simple predicate used by the default RankCandidate to
    267   /// determine whether to return an edit distance of 0 or InvalidDistance.
    268   /// This can be overrided by validators that only need to determine if a
    269   /// candidate is viable, without ranking potentially viable candidates.
    270   /// Only ValidateCandidate or RankCandidate need to be overriden by a
    271   /// callback wishing to check the viability of correction candidates.
    272   /// The default predicate always returns true if the candidate is not a type
    273   /// name or keyword, true for types if WantTypeSpecifiers is true, and true
    274   /// for keywords if WantTypeSpecifiers, WantExpressionKeywords,
    275   /// WantCXXNamedCasts, WantRemainingKeywords, or WantObjCSuper is true.
    276   virtual bool ValidateCandidate(const TypoCorrection &candidate);
    277 
    278   /// \brief Method used by Sema::CorrectTypo to assign an "edit distance" rank
    279   /// to a candidate (where a lower value represents a better candidate), or
    280   /// returning InvalidDistance if the candidate is not at all viable. For
    281   /// validation callbacks that only need to determine if a candidate is viable,
    282   /// the default RankCandidate returns either 0 or InvalidDistance depending
    283   /// whether ValidateCandidate returns true or false.
    284   virtual unsigned RankCandidate(const TypoCorrection &candidate) {
    285     return (!MatchesTypo(candidate) && ValidateCandidate(candidate))
    286                ? 0
    287                : InvalidDistance;
    288   }
    289 
    290   void setTypoName(IdentifierInfo *II) { Typo = II; }
    291   void setTypoNNS(NestedNameSpecifier *NNS) { TypoNNS = NNS; }
    292 
    293   // Flags for context-dependent keywords. WantFunctionLikeCasts is only
    294   // used/meaningful when WantCXXNamedCasts is false.
    295   // TODO: Expand these to apply to non-keywords or possibly remove them.
    296   bool WantTypeSpecifiers;
    297   bool WantExpressionKeywords;
    298   bool WantCXXNamedCasts;
    299   bool WantFunctionLikeCasts;
    300   bool WantRemainingKeywords;
    301   bool WantObjCSuper;
    302   // Temporary hack for the one case where a CorrectTypoContext enum is used
    303   // when looking up results.
    304   bool IsObjCIvarLookup;
    305   bool IsAddressOfOperand;
    306 
    307 protected:
    308   bool MatchesTypo(const TypoCorrection &candidate) {
    309     return Typo && candidate.isResolved() && !candidate.requiresImport() &&
    310            candidate.getCorrectionAsIdentifierInfo() == Typo &&
    311            // FIXME: This probably does not return true when both
    312            // NestedNameSpecifiers have the same textual representation.
    313            candidate.getCorrectionSpecifier() == TypoNNS;
    314   }
    315 
    316   IdentifierInfo *Typo;
    317   NestedNameSpecifier *TypoNNS;
    318 };
    319 
    320 /// @brief Simple template class for restricting typo correction candidates
    321 /// to ones having a single Decl* of the given type.
    322 template <class C>
    323 class DeclFilterCCC : public CorrectionCandidateCallback {
    324 public:
    325   bool ValidateCandidate(const TypoCorrection &candidate) override {
    326     return candidate.getCorrectionDeclAs<C>();
    327   }
    328 };
    329 
    330 // @brief Callback class to limit the allowed keywords and to only accept typo
    331 // corrections that are keywords or whose decls refer to functions (or template
    332 // functions) that accept the given number of arguments.
    333 class FunctionCallFilterCCC : public CorrectionCandidateCallback {
    334 public:
    335   FunctionCallFilterCCC(Sema &SemaRef, unsigned NumArgs,
    336                         bool HasExplicitTemplateArgs,
    337                         MemberExpr *ME = nullptr);
    338 
    339   bool ValidateCandidate(const TypoCorrection &candidate) override;
    340 
    341  private:
    342   unsigned NumArgs;
    343   bool HasExplicitTemplateArgs;
    344   DeclContext *CurContext;
    345   MemberExpr *MemberFn;
    346 };
    347 
    348 // @brief Callback class that effectively disabled typo correction
    349 class NoTypoCorrectionCCC : public CorrectionCandidateCallback {
    350 public:
    351   NoTypoCorrectionCCC() {
    352     WantTypeSpecifiers = false;
    353     WantExpressionKeywords = false;
    354     WantCXXNamedCasts = false;
    355     WantFunctionLikeCasts = false;
    356     WantRemainingKeywords = false;
    357   }
    358 
    359   bool ValidateCandidate(const TypoCorrection &candidate) override {
    360     return false;
    361   }
    362 };
    363 
    364 }
    365 
    366 #endif
    367