bool sourcekitd::compareDictKeys(UIdent LHS, UIdent RHS) {
  if (LHS == RHS)
    return false;
  unsigned LHSOrder = findPrintOrderForDictKey(LHS);
  unsigned RHSOrder = findPrintOrderForDictKey(RHS);
  if (LHSOrder == RHSOrder)
    return LHS.getName() < RHS.getName();
  return LHSOrder < RHSOrder;
}

sourcekitd_uid_t sourcekitd::SKDUIDFromUIdent(UIdent UID) {
  if (void *Tag = UID.getTag())
    return reinterpret_cast<sourcekitd_uid_t>(Tag);

  if (UidMappingHandler) {
    sourcekitd_uid_t skduid = UidMappingHandler(UID.c_str());
    if (skduid) {
      UID.setTag(skduid);
      return skduid;
    }
  }

  return reinterpret_cast<sourcekitd_uid_t>(UID.getAsOpaqueValue());
}

void CompactArrayBuilderImpl::addImpl(UIdent Val) {
  if (Val.isValid()) {
    sourcekitd_uid_t uid = SKDUIDFromUIdent(Val);
    addScalar(uid, EntriesBuffer);
  } else {
    addScalar(sourcekitd_uid_t(nullptr), EntriesBuffer);
  }
}

static void reportSemanticAnnotations(const SourceTextInfo &IFaceInfo,
                                      EditorConsumer &Consumer) {
  for (auto &Ref : IFaceInfo.References) {
    UIdent Kind;
    bool IsSystem;
    if (Ref.Mod) {
      Kind = SwiftLangSupport::getUIDForModuleRef();
      IsSystem = Ref.Mod.isSystemModule();
    } else if (Ref.Dcl) {
      Kind = SwiftLangSupport::getUIDForDecl(Ref.Dcl, /*IsRef=*/true);
      IsSystem = Ref.Dcl->getModuleContext()->isSystemModule();
    }
    if (Kind.isInvalid())
      continue;
    unsigned Offset = Ref.Range.Offset;
    unsigned Length = Ref.Range.Length;
    Consumer.handleSemanticAnnotation(Offset, Length, Kind, IsSystem);
  }
}

bool IndexSwiftASTWalker::visitImports(SourceFileOrModule TopMod,
                                     llvm::SmallPtrSet<Module *, 16> &Visited) {
  // Dependencies of the stdlib module (like SwiftShims module) are
  // implementation details.
  if (TopMod.getModule().isStdlibModule())
    return true;

  bool IsNew = Visited.insert(&TopMod.getModule()).second;
  if (!IsNew)
    return true;

  SmallVector<Module::ImportedModule, 8> Imports;
  TopMod.getImportedModules(Imports);

  llvm::SmallPtrSet<Module *, 8> Reported;
  for (auto Import : Imports) {
    Module *Mod = Import.second;
    bool NewReport = Reported.insert(Mod).second;
    if (!NewReport)
      continue;

    // FIXME: Handle modules with multiple source files; these will fail on
    // getModuleFilename() (by returning an empty path). Note that such modules
    // may be heterogeneous.
    StringRef Path = Mod->getModuleFilename();
    if (Path.empty() || Path == TopMod.getFilename())
      continue; // this is a submodule.

    UIdent ImportKind;
    for (auto File : Mod->getFiles()) {
      switch (File->getKind()) {
      case FileUnitKind::Source:
        assert(ImportKind.isInvalid() && "cannot handle multi-file modules");
        ImportKind = KindImportSourceFile;
        break;
      case FileUnitKind::Builtin:
      case FileUnitKind::Derived:
        break;
      case FileUnitKind::SerializedAST:
        assert(ImportKind.isInvalid() && "cannot handle multi-file modules");
        ImportKind = KindImportModuleSwift;
        break;
      case FileUnitKind::ClangModule:
        assert(ImportKind.isInvalid() && "cannot handle multi-file modules");
        ImportKind = KindImportModuleClang;
        break;
      }
    }
    if (ImportKind.isInvalid())
      continue;

    StringRef Hash;
    SmallString<32> HashBuf;
    if (ImportKind != KindImportModuleClang) {
      llvm::raw_svector_ostream HashOS(HashBuf);
      getModuleHash(*Mod, HashOS);
      Hash = HashOS.str();
    }

    if (!IdxConsumer.startDependency(ImportKind, Mod->getName().str(), Path,
                                     Mod->isSystemModule(), Hash))
      return false;
    if (ImportKind != KindImportModuleClang)
      if (!visitImports(*Mod, Visited))
        return false;
    if (!IdxConsumer.finishDependency(ImportKind))
      return false;
  }

  return true;
}