Completion.cpp

Go to the documentation of this file.

/// \file
/// \brief Implementation of [Code Completion].
/// [Code Completion]:
/// https://microsoft.github.io/language-server-protocol/specifications/lsp/3.17/specification/#textDocument_completion
 
#include "AST.h"
#include "CheckReturn.h"
#include "Convert.h"
 
#include "lspserver/Protocol.h"
 
#include "nixd/Controller/Controller.h"
#include "nixd/Protocol/AttrSet.h"
 
#include <nixf/Sema/VariableLookup.h>
 
#include <boost/asio/post.hpp>
 
#include <exception>
#include <semaphore>
#include <set>
#include <utility>
 
using namespace nixd;
using namespace lspserver;
using namespace nixf;
 
namespace {
 
/// Set max completion size to this value, we don't want to send large lists
/// because of slow IO.
/// Items exceed this size should be marked "incomplete" and recomputed.
constexpr int MaxCompletionSize = 30;
 
CompletionItemKind OptionKind = CompletionItemKind::Constructor;
CompletionItemKind OptionAttrKind = CompletionItemKind::Class;
 
struct ExceedSizeError : std::exception {
  [[nodiscard]] const char *what() const noexcept override {
    return "Size exceeded";
  }
};
 
void addItem(std::vector<CompletionItem> &Items, CompletionItem Item) {
  if (Items.size() >= MaxCompletionSize) {
    throw ExceedSizeError();
  }
  Items.emplace_back(std::move(Item));
}
 
bool hasConcreteChild(const Node &N) {
  for (const Node *Child : N.children()) {
    if (Child)
      return true;
  }
  return false;
}
 
bool canCompleteAt(const Node &N) {
  if (!hasConcreteChild(N))
    return true;
  return N.kind() == Node::NK_Binds || N.kind() == Node::NK_ExprAttrs;
}
 
bool isKnownSelector(const Node &N, const VariableLookupAnalysis &VLA,
                     const ParentMapAnalysis &PM) {
  const Node *Expr = PM.upExpr(N);
  if (!Expr || Expr->kind() != Node::NK_ExprSelect)
    return false;
 
  try {
    idioms::mkSelector(static_cast<const nixf::ExprSelect &>(*Expr), VLA, PM);
    return true;
  } catch (const idioms::IdiomSelectorException &) {
    return false;
  } catch (const idioms::VLAException &) {
    return false;
  }
}
 
class VLACompletionProvider {
  const VariableLookupAnalysis &VLA;
 
  static CompletionItemKind getCompletionItemKind(const Definition &Def) {
    if (Def.isBuiltin()) {
      return CompletionItemKind::Keyword;
    }
    return CompletionItemKind::Variable;
  }
 
  /// Collect definition on some env, and also it's ancestors.
  void collectDef(std::vector<CompletionItem> &Items, const EnvNode *Env,
                  const std::string &Prefix) {
    if (!Env)
      return;
    collectDef(Items, Env->parent(), Prefix);
    for (const auto &[Name, Def] : Env->defs()) {
      if (Name.starts_with(
              "__")) // These names are nix internal implementation, skip.
        continue;
      assert(Def);
      if (Name.starts_with(Prefix)) {
        addItem(Items, CompletionItem{
                           .label = Name,
                           .kind = getCompletionItemKind(*Def),
                       });
      }
    }
  }
 
public:
  VLACompletionProvider(const VariableLookupAnalysis &VLA) : VLA(VLA) {}
 
  /// Perform code completion right after this node.
  void complete(const nixf::ExprVar &Desc, std::vector<CompletionItem> &Items,
                const ParentMapAnalysis &PM) {
    std::string Prefix = Desc.id().name();
    collectDef(Items, upEnv(Desc, VLA, PM), Prefix);
  }
};
 
/// \brief Provide completions by IPC. Asking nixpkgs provider.
/// We simply select nixpkgs in separate process, thus this value does not need
/// to be cached. (It is already cached in separate process.)
///
/// Currently, this procedure is explicitly blocked (synchronized). Because
/// query nixpkgs value is relatively fast. In the future there might be nixd
/// index, for performance.
class NixpkgsCompletionProvider {
 
  AttrSetClient &NixpkgsClient;
 
public:
  NixpkgsCompletionProvider(AttrSetClient &NixpkgsClient)
      : NixpkgsClient(NixpkgsClient) {}
 
  void resolvePackage(std::vector<std::string> Scope, std::string Name,
                      CompletionItem &Item) {
    std::binary_semaphore Ready(0);
    AttrPathInfoResponse Desc;
    auto OnReply = [&Ready, &Desc](llvm::Expected<AttrPathInfoResponse> Resp) {
      if (Resp)
        Desc = *Resp;
      Ready.release();
    };
    Scope.emplace_back(std::move(Name));
    NixpkgsClient.attrpathInfo(Scope, std::move(OnReply));
    Ready.acquire();
    // Format "detail" and document.
    const PackageDescription &PD = Desc.PackageDesc;
    Item.documentation = MarkupContent{
        .kind = MarkupKind::Markdown,
        .value = PD.Description.value_or("") + "\n\n" +
                 PD.LongDescription.value_or(""),
    };
    Item.detail = PD.Version.value_or("?");
  }
 
  /// \brief Ask nixpkgs provider, give us a list of names. (thunks)
  bool completePackages(const lspserver::Range EditRange,
                        const AttrPathCompleteParams &Params,
                        std::vector<CompletionItem> &Items) {
    std::binary_semaphore Ready(0);
    AttrPathCompleteResponse Names;
    auto OnReply = [&Ready,
                    &Names](llvm::Expected<AttrPathCompleteResponse> Resp) {
      if (!Resp) {
        lspserver::elog("nixpkgs evaluator reported: {0}", Resp.takeError());
        Ready.release();
        return;
      }
      Names = *Resp; // Copy response to waiting thread.
      Ready.release();
    };
    // Send request.
    NixpkgsClient.attrpathComplete(Params, std::move(OnReply));
    Ready.acquire();
    // Now we have "Names", use these to fill "Items".
    for (const auto &Name : Names.Items) {
      if (Name.starts_with(Params.Prefix)) {
        addItem(Items, CompletionItem{
                           .label = Name,
                           .kind = CompletionItemKind::Field,
                           .textEdit = lspserver::TextEdit{.range = EditRange,
                                                           .newText = Name},
                           .data = llvm::formatv("{0}", toJSON(Params)),
                       });
      }
    }
    return Names.IsIncomplete;
  }
};
 
/// \brief Provide completion list by nixpkgs module system (options).
class OptionCompletionProvider {
  AttrSetClient &OptionClient;
 
  // Where is the module set. (e.g. nixos)
  std::string ModuleOrigin;
 
  // Wheter the client support code snippets.
  bool ClientSupportSnippet;
 
  static std::string escapeCharacters(const std::set<char> &Charset,
                                      const std::string &Origin) {
    // Escape characters listed in charset.
    std::string Ret;
    Ret.reserve(Origin.size());
    for (const auto Ch : Origin) {
      if (Charset.contains(Ch)) {
        Ret += "\\";
        Ret += Ch;
      } else {
        Ret += Ch;
      }
    }
    return Ret;
  }
 
  void fillInsertText(CompletionItem &Item, const std::string &Name,
                      const std::string &Value) const {
    if (!ClientSupportSnippet) {
      Item.insertTextFormat = InsertTextFormat::PlainText;
      Item.insertText = Name + " = " + Value + ";";
      return;
    }
    Item.insertTextFormat = InsertTextFormat::Snippet;
    Item.insertText = Name + " = " +
                      "${1:" + escapeCharacters({'\\', '$', '}'}, Value) + "}" +
                      ";";
  }
 
public:
  OptionCompletionProvider(AttrSetClient &OptionClient,
                           std::string ModuleOrigin, bool ClientSupportSnippet)
      : OptionClient(OptionClient), ModuleOrigin(std::move(ModuleOrigin)),
        ClientSupportSnippet(ClientSupportSnippet) {}
 
  bool completeOptions(const lspserver::Range EditRange,
                       std::vector<std::string> Scope, std::string Prefix,
                       std::vector<CompletionItem> &Items) {
    std::binary_semaphore Ready(0);
    OptionCompleteResponse Names;
    auto OnReply = [&Ready,
                    &Names](llvm::Expected<OptionCompleteResponse> Resp) {
      if (!Resp) {
        lspserver::elog("option worker reported: {0}", Resp.takeError());
        Ready.release();
        return;
      }
      Names = *Resp; // Copy response to waiting thread.
      Ready.release();
    };
    // Send request.
    AttrPathCompleteParams Params{std::move(Scope), std::move(Prefix)};
    OptionClient.optionComplete(Params, std::move(OnReply));
    Ready.acquire();
    // Now we have "Names", use these to fill "Items".
    //
    // When Params.Prefix is empty, the cursor is inside an empty hole and
    // EditRange does not point at a real prefix to replace, so we omit the
    // textEdit and let the editor fall back to insertText/label.
    bool HasPrefix = !Params.Prefix.empty();
    auto MkTextEdit =
        [&](llvm::StringRef NewText) -> std::optional<lspserver::TextEdit> {
      if (!HasPrefix)
        return std::nullopt;
      return lspserver::TextEdit{.range = EditRange, .newText = NewText.str()};
    };
    for (const nixd::OptionField &Field : Names.Items) {
      if (!Field.Description) {
        addItem(Items, CompletionItem{
                           .label = Field.Name,
                           .kind = OptionAttrKind,
                           .detail = ModuleOrigin,
                           .textEdit = MkTextEdit(Field.Name),
                       });
        continue;
      }
 
      const OptionDescription &Desc = *Field.Description;
 
      // Build the shared bits (detail, documentation) once, then emit one
      // completion item per value source (`example`, `default`). This lets
      // the user pick between the sample code the option author suggested
      // and its default value - useful when an option only has one of the
      // two, or when the user wants the default as a starting point.
      std::string TypeDetail = ModuleOrigin + " | ";
      if (Desc.Type) {
        std::string TypeName = Desc.Type->Name.value_or("");
        std::string TypeDesc = Desc.Type->Description.value_or("");
        TypeDetail += llvm::formatv("{0} ({1})", TypeName, TypeDesc);
      } else {
        TypeDetail += "? (missing type)";
      }
      MarkupContent Doc{
          .kind = MarkupKind::Markdown,
          .value = Desc.Description.value_or(""),
      };
 
      // Check whether both variants will be emitted so we can decide
      // whether to disambiguate the labels with "(example)" / "(default)".
      bool HasExample = Desc.Example.has_value();
      // Only emit a separate `default` item when it would differ from the
      // example; otherwise the user would see two identical snippets.
      bool HasDefault =
          Desc.Default.has_value() && Desc.Default != Desc.Example;
      bool HasBoth = HasExample && HasDefault;
 
      auto emit = [&](const std::string &Value, llvm::StringRef Source,
                      llvm::StringRef SortPrefix) {
        // When both variants exist, append the source so users can tell
        // them apart. `filterText` is always the plain option name so
        // typing the name matches both items.
        std::string Label =
            HasBoth ? llvm::formatv("{0} ({1})", Field.Name, Source).str()
                    : Field.Name;
        CompletionItem Item{
            .label = std::move(Label),
            .kind = OptionKind,
            .detail = TypeDetail,
            .documentation = Doc,
            .sortText = (SortPrefix + Field.Name).str(),
            .filterText = Field.Name,
        };
        fillInsertText(Item, Field.Name, Value);
        Item.textEdit = MkTextEdit(Item.insertText);
        addItem(Items, std::move(Item));
      };
 
      bool Emitted = false;
      if (HasExample) {
        emit(*Desc.Example, "example", "0");
        Emitted = true;
      }
      if (HasDefault) {
        emit(*Desc.Default, "default", "1");
        Emitted = true;
      }
      if (!Emitted) {
        // No example or default to insert — still offer the option name
        // as a bare completion so users can discover it.
        CompletionItem Item{
            .label = Field.Name,
            .kind = OptionKind,
            .detail = TypeDetail,
            .documentation = Doc,
        };
        fillInsertText(Item, Field.Name, "");
        Item.textEdit = MkTextEdit(Item.insertText);
        addItem(Items, std::move(Item));
      }
    }
    return Names.IsIncomplete;
  }
};
 
bool completeAttrName(const lspserver::Range EditRange,
                      const std::vector<std::string> &Scope,
                      const std::string &Prefix,
                      Controller::OptionMapTy &Options, bool CompletionSnippets,
                      std::vector<CompletionItem> &List) {
  bool IsIncomplete = false;
  for (const auto &[Name, Provider] : Options) {
    AttrSetClient *Client = Options.at(Name)->client();
    if (!Client) [[unlikely]] {
      elog("skipped client {0} as it is dead", Name);
      continue;
    }
    OptionCompletionProvider OCP(*Client, Name, CompletionSnippets);
    IsIncomplete |= OCP.completeOptions(EditRange, Scope, Prefix, List);
  }
  return IsIncomplete;
}
 
bool completeAttrPath(const lspserver::Range EditRange, const Node &N,
                      const ParentMapAnalysis &PM, std::mutex &OptionsLock,
                      Controller::OptionMapTy &Options, bool Snippets,
                      std::vector<lspserver::CompletionItem> &Items) {
  std::vector<std::string> Scope;
  using PathResult = FindAttrPathResult;
  auto R = findAttrPathForOptions(N, PM, Scope);
  if (R == PathResult::OK) {
    // Construct request.
    std::string Prefix = Scope.back();
    Scope.pop_back();
    {
      std::lock_guard _(OptionsLock);
      return completeAttrName(EditRange, Scope, Prefix, Options, Snippets,
                              Items);
    }
  }
  return false;
}
 
AttrPathCompleteParams mkParams(nixd::Selector Sel, bool IsComplete) {
  if (IsComplete || Sel.empty()) {
    return {
        .Scope = std::move(Sel),
        .Prefix = "",
    };
  }
  std::string Back = std::move(Sel.back());
  Sel.pop_back();
  return {
      .Scope = Sel,
      .Prefix = std::move(Back),
  };
}
 
#define DBG DBGPREFIX ": "
 
bool completeVarName(const lspserver::Range EditRange,
                     const VariableLookupAnalysis &VLA,
                     const ParentMapAnalysis &PM, const nixf::ExprVar &N,
                     AttrSetClient &Client, std::vector<CompletionItem> &List) {
#define DBGPREFIX "completion/var"
 
  VLACompletionProvider VLAP(VLA);
  VLAP.complete(N, List, PM);
 
  // Try to complete the name by known idioms.
  try {
    Selector Sel = idioms::mkVarSelector(N, VLA, PM);
 
    // Clickling "pkgs" does not make sense for variable completion
    if (Sel.empty())
      return false;
 
    // Invoke nixpkgs provider to get the completion list.
    NixpkgsCompletionProvider NCP(Client);
    // Variable names are partial selector segments.
    return NCP.completePackages(EditRange, mkParams(Sel, /*IsComplete=*/false),
                                List);
  } catch (ExceedSizeError &) {
    // Let "onCompletion" catch this exception to set "inComplete" field.
    throw;
  } catch (std::exception &E) {
    log(DBG "skipped, reason: {0}", E.what());
    return false;
  }
 
#undef DBGPREFIX
}
 
/// \brief Complete a "select" expression.
/// \param IsComplete Whether or not the last element of the selector is
/// effectively incomplete.
/// e.g.
///      - incomplete: `lib.gen|`
///      - complete:   `lib.attrset.|`
bool completeSelect(const lspserver::Range EditRange,
                    const nixf::ExprSelect &Select, AttrSetClient &Client,
                    const nixf::VariableLookupAnalysis &VLA,
                    const nixf::ParentMapAnalysis &PM, bool IsComplete,
                    std::vector<CompletionItem> &List) {
#define DBGPREFIX "completion/select"
  // The base expr for selecting.
  const nixf::Expr &BaseExpr = Select.expr();
 
  // Determine that the name is one of special names interesting
  // for nix language. If it is not a simple variable, skip this
  // case.
  if (BaseExpr.kind() != Node::NK_ExprVar) {
    return false;
  }
 
  const auto &Var = static_cast<const nixf::ExprVar &>(BaseExpr);
  // Ask nixpkgs provider to get idioms completion.
  NixpkgsCompletionProvider NCP(Client);
 
  try {
    Selector Sel =
        idioms::mkSelector(Select, idioms::mkVarSelector(Var, VLA, PM));
    return NCP.completePackages(EditRange, mkParams(Sel, IsComplete), List);
  } catch (ExceedSizeError &) {
    // Let "onCompletion" catch this exception to set "inComplete" field.
    throw;
  } catch (std::exception &E) {
    log(DBG "skipped, reason: {0}", E.what());
    return false;
  }
 
#undef DBGPREFIX
}
 
} // namespace
 
void Controller::onCompletion(const CompletionParams &Params,
                              Callback<CompletionList> Reply) {
  using CheckTy = CompletionList;
  auto Action = [Reply = std::move(Reply), URI = Params.textDocument.uri,
                 Pos = toNixfPosition(Params.position),
                 Context = Params.context, this]() mutable {
    const auto File = URI.file().str();
    bool KnownSelector = false;
    auto Result = [&]() -> llvm::Expected<CompletionList> {
      const auto TU = CheckDefault(getTU(File));
      const auto AST = CheckDefault(getAST(*TU));
      const auto &PM = *TU->parentMap();
      const VariableLookupAnalysis &VLA = *TU->variableLookup();
 
      const auto *Desc = AST->descend({Pos, Pos});
      if (Desc)
        KnownSelector = isKnownSelector(*Desc, VLA, PM);
      CheckDefault(Desc && canCompleteAt(*Desc));
 
      const auto &N = *Desc;
      const auto &UpExpr = *CheckDefault(PM.upExpr(N));
 
      lspserver::Range EditRange = toLSPRange(TU->src(), N.range());
      if (N.kind() == Node::NK_Dot) {
        // If the node is a dot, insert after the dot
        EditRange.start = EditRange.end;
      }
 
      CompletionList List;
      bool ProviderIncomplete = false;
      try {
        switch (UpExpr.kind()) {
        // In these cases, assume the cursor have "variable" scoping.
        case Node::NK_ExprVar: {
          ProviderIncomplete = completeVarName(
              EditRange, VLA, PM, static_cast<const nixf::ExprVar &>(UpExpr),
              *nixpkgsClient(), List.items);
          break;
        }
        // A "select" expression. e.g.
        // foo.a|
        // foo.|
        // foo.a.bar|
        case Node::NK_ExprSelect: {
          const auto &Select = static_cast<const nixf::ExprSelect &>(UpExpr);
          ProviderIncomplete =
              completeSelect(EditRange, Select, *nixpkgsClient(), VLA, PM,
                             N.kind() == Node::NK_Dot, List.items);
          break;
        }
        case Node::NK_ExprAttrs: {
          ProviderIncomplete =
              completeAttrPath(EditRange, N, PM, OptionsLock, Options,
                               ClientCaps.CompletionSnippets, List.items);
          break;
        }
        default:
          break;
        }
      } catch (ExceedSizeError &Err) {
        List.isIncomplete = true;
        return List;
      }
      List.isIncomplete |= ProviderIncomplete;
      return List;
    }();
 
    // A recognized selector may have no candidates for the empty prefix. Keep
    // that trigger-character result retriggerable so a more specific prefix
    // can be requested as the user continues typing.
    if (Result &&
        Context.triggerKind == CompletionTriggerKind::TriggerCharacter &&
        Context.triggerCharacter == "." && KnownSelector &&
        Result->items.empty())
      Result->isIncomplete = true;
    return Reply(std::move(Result));
  };
  boost::asio::post(Pool, std::move(Action));
}
 
void Controller::onCompletionItemResolve(const CompletionItem &Params,
                                         Callback<CompletionItem> Reply) {
 
  auto Action = [Params, Reply = std::move(Reply), this]() mutable {
    if (Params.data.empty()) {
      Reply(Params);
      return;
    }
    AttrPathCompleteParams Req;
    auto EV = llvm::json::parse(Params.data);
    if (!EV) {
      // If the json value cannot be parsed, this is very unlikely to happen.
      Reply(EV.takeError());
      return;
    }
 
    llvm::json::Path::Root Root;
    fromJSON(*EV, Req, Root);
 
    // FIXME: handle null nixpkgsClient()
    NixpkgsCompletionProvider NCP(*nixpkgsClient());
    CompletionItem Resp = Params;
    NCP.resolvePackage(Req.Scope, Params.label, Resp);
 
    Reply(std::move(Resp));
  };
  boost::asio::post(Pool, std::move(Action));
}