1//===--- Core.cpp - Core ORC APIs (MaterializationUnit, JITDylib, etc.) ---===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "llvm/ExecutionEngine/Orc/Core.h"
10
11#include "llvm/ADT/STLExtras.h"
12#include "llvm/Config/llvm-config.h"
13#include "llvm/ExecutionEngine/Orc/OrcError.h"
14#include "llvm/IR/Mangler.h"
15#include "llvm/Support/CommandLine.h"
16#include "llvm/Support/Debug.h"
17#include "llvm/Support/Format.h"
18
19#if LLVM_ENABLE_THREADS
20#include <future>
21#endif
22
23#define DEBUG_TYPE "orc"
24
25using namespace llvm;
26
27namespace {
28
29#ifndef NDEBUG
30
31cl::opt<bool> PrintHidden("debug-orc-print-hidden", cl::init(true),
32                          cl::desc("debug print hidden symbols defined by "
33                                   "materialization units"),
34                          cl::Hidden);
35
36cl::opt<bool> PrintCallable("debug-orc-print-callable", cl::init(true),
37                            cl::desc("debug print callable symbols defined by "
38                                     "materialization units"),
39                            cl::Hidden);
40
41cl::opt<bool> PrintData("debug-orc-print-data", cl::init(true),
42                        cl::desc("debug print data symbols defined by "
43                                 "materialization units"),
44                        cl::Hidden);
45
46#endif // NDEBUG
47
48// SetPrinter predicate that prints every element.
49template <typename T> struct PrintAll {
50  bool operator()(const T &E) { return true; }
51};
52
53bool anyPrintSymbolOptionSet() {
54#ifndef NDEBUG
55  return PrintHidden || PrintCallable || PrintData;
56#else
57  return false;
58#endif // NDEBUG
59}
60
61bool flagsMatchCLOpts(const JITSymbolFlags &Flags) {
62#ifndef NDEBUG
63  // Bail out early if this is a hidden symbol and we're not printing hiddens.
64  if (!PrintHidden && !Flags.isExported())
65    return false;
66
67  // Return true if this is callable and we're printing callables.
68  if (PrintCallable && Flags.isCallable())
69    return true;
70
71  // Return true if this is data and we're printing data.
72  if (PrintData && !Flags.isCallable())
73    return true;
74
75  // otherwise return false.
76  return false;
77#else
78  return false;
79#endif // NDEBUG
80}
81
82// Prints a sequence of items, filtered by an user-supplied predicate.
83template <typename Sequence,
84          typename Pred = PrintAll<typename Sequence::value_type>>
85class SequencePrinter {
86public:
87  SequencePrinter(const Sequence &S, char OpenSeq, char CloseSeq,
88                  Pred ShouldPrint = Pred())
89      : S(S), OpenSeq(OpenSeq), CloseSeq(CloseSeq),
90        ShouldPrint(std::move(ShouldPrint)) {}
91
92  void printTo(llvm::raw_ostream &OS) const {
93    bool PrintComma = false;
94    OS << OpenSeq;
95    for (auto &E : S) {
96      if (ShouldPrint(E)) {
97        if (PrintComma)
98          OS << ',';
99        OS << ' ' << E;
100        PrintComma = true;
101      }
102    }
103    OS << ' ' << CloseSeq;
104  }
105
106private:
107  const Sequence &S;
108  char OpenSeq;
109  char CloseSeq;
110  mutable Pred ShouldPrint;
111};
112
113template <typename Sequence, typename Pred>
114SequencePrinter<Sequence, Pred> printSequence(const Sequence &S, char OpenSeq,
115                                              char CloseSeq, Pred P = Pred()) {
116  return SequencePrinter<Sequence, Pred>(S, OpenSeq, CloseSeq, std::move(P));
117}
118
119// Render a SequencePrinter by delegating to its printTo method.
120template <typename Sequence, typename Pred>
121llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
122                              const SequencePrinter<Sequence, Pred> &Printer) {
123  Printer.printTo(OS);
124  return OS;
125}
126
127struct PrintSymbolFlagsMapElemsMatchingCLOpts {
128  bool operator()(const orc::SymbolFlagsMap::value_type &KV) {
129    return flagsMatchCLOpts(KV.second);
130  }
131};
132
133struct PrintSymbolMapElemsMatchingCLOpts {
134  bool operator()(const orc::SymbolMap::value_type &KV) {
135    return flagsMatchCLOpts(KV.second.getFlags());
136  }
137};
138
139} // end anonymous namespace
140
141namespace llvm {
142namespace orc {
143
144char FailedToMaterialize::ID = 0;
145char SymbolsNotFound::ID = 0;
146char SymbolsCouldNotBeRemoved::ID = 0;
147
148RegisterDependenciesFunction NoDependenciesToRegister =
149    RegisterDependenciesFunction();
150
151void MaterializationUnit::anchor() {}
152
153raw_ostream &operator<<(raw_ostream &OS, const SymbolStringPtr &Sym) {
154  return OS << *Sym;
155}
156
157raw_ostream &operator<<(raw_ostream &OS, const SymbolNameSet &Symbols) {
158  return OS << printSequence(Symbols, '{', '}', PrintAll<SymbolStringPtr>());
159}
160
161raw_ostream &operator<<(raw_ostream &OS, const SymbolNameVector &Symbols) {
162  return OS << printSequence(Symbols, '[', ']', PrintAll<SymbolStringPtr>());
163}
164
165raw_ostream &operator<<(raw_ostream &OS, const JITSymbolFlags &Flags) {
166  if (Flags.hasError())
167    OS << "[*ERROR*]";
168  if (Flags.isCallable())
169    OS << "[Callable]";
170  else
171    OS << "[Data]";
172  if (Flags.isWeak())
173    OS << "[Weak]";
174  else if (Flags.isCommon())
175    OS << "[Common]";
176
177  if (!Flags.isExported())
178    OS << "[Hidden]";
179
180  return OS;
181}
182
183raw_ostream &operator<<(raw_ostream &OS, const JITEvaluatedSymbol &Sym) {
184  return OS << format("0x%016" PRIx64, Sym.getAddress()) << " "
185            << Sym.getFlags();
186}
187
188raw_ostream &operator<<(raw_ostream &OS, const SymbolFlagsMap::value_type &KV) {
189  return OS << "(\"" << KV.first << "\", " << KV.second << ")";
190}
191
192raw_ostream &operator<<(raw_ostream &OS, const SymbolMap::value_type &KV) {
193  return OS << "(\"" << KV.first << "\": " << KV.second << ")";
194}
195
196raw_ostream &operator<<(raw_ostream &OS, const SymbolFlagsMap &SymbolFlags) {
197  return OS << printSequence(SymbolFlags, '{', '}',
198                             PrintSymbolFlagsMapElemsMatchingCLOpts());
199}
200
201raw_ostream &operator<<(raw_ostream &OS, const SymbolMap &Symbols) {
202  return OS << printSequence(Symbols, '{', '}',
203                             PrintSymbolMapElemsMatchingCLOpts());
204}
205
206raw_ostream &operator<<(raw_ostream &OS,
207                        const SymbolDependenceMap::value_type &KV) {
208  return OS << "(" << KV.first << ", " << KV.second << ")";
209}
210
211raw_ostream &operator<<(raw_ostream &OS, const SymbolDependenceMap &Deps) {
212  return OS << printSequence(Deps, '{', '}',
213                             PrintAll<SymbolDependenceMap::value_type>());
214}
215
216raw_ostream &operator<<(raw_ostream &OS, const MaterializationUnit &MU) {
217  OS << "MU@" << &MU << " (\"" << MU.getName() << "\"";
218  if (anyPrintSymbolOptionSet())
219    OS << ", " << MU.getSymbols();
220  return OS << ")";
221}
222
223raw_ostream &operator<<(raw_ostream &OS, const LookupKind &K) {
224  switch (K) {
225  case LookupKind::Static:
226    return OS << "Static";
227  case LookupKind::DLSym:
228    return OS << "DLSym";
229  }
230  llvm_unreachable("Invalid lookup kind");
231}
232
233raw_ostream &operator<<(raw_ostream &OS,
234                        const JITDylibLookupFlags &JDLookupFlags) {
235  switch (JDLookupFlags) {
236  case JITDylibLookupFlags::MatchExportedSymbolsOnly:
237    return OS << "MatchExportedSymbolsOnly";
238  case JITDylibLookupFlags::MatchAllSymbols:
239    return OS << "MatchAllSymbols";
240  }
241  llvm_unreachable("Invalid JITDylib lookup flags");
242}
243
244raw_ostream &operator<<(raw_ostream &OS, const SymbolLookupFlags &LookupFlags) {
245  switch (LookupFlags) {
246  case SymbolLookupFlags::RequiredSymbol:
247    return OS << "RequiredSymbol";
248  case SymbolLookupFlags::WeaklyReferencedSymbol:
249    return OS << "WeaklyReferencedSymbol";
250  }
251  llvm_unreachable("Invalid symbol lookup flags");
252}
253
254raw_ostream &operator<<(raw_ostream &OS,
255                        const SymbolLookupSet::value_type &KV) {
256  return OS << "(" << KV.first << ", " << KV.second << ")";
257}
258
259raw_ostream &operator<<(raw_ostream &OS, const SymbolLookupSet &LookupSet) {
260  return OS << printSequence(LookupSet, '{', '}',
261                             PrintAll<SymbolLookupSet::value_type>());
262}
263
264raw_ostream &operator<<(raw_ostream &OS,
265                        const JITDylibSearchOrder &SearchOrder) {
266  OS << "[";
267  if (!SearchOrder.empty()) {
268    assert(SearchOrder.front().first &&
269           "JITDylibList entries must not be null");
270    OS << " (\"" << SearchOrder.front().first->getName() << "\", "
271       << SearchOrder.begin()->second << ")";
272    for (auto &KV :
273         make_range(std::next(SearchOrder.begin(), 1), SearchOrder.end())) {
274      assert(KV.first && "JITDylibList entries must not be null");
275      OS << ", (\"" << KV.first->getName() << "\", " << KV.second << ")";
276    }
277  }
278  OS << " ]";
279  return OS;
280}
281
282raw_ostream &operator<<(raw_ostream &OS, const SymbolAliasMap &Aliases) {
283  OS << "{";
284  for (auto &KV : Aliases)
285    OS << " " << *KV.first << ": " << KV.second.Aliasee << " "
286       << KV.second.AliasFlags;
287  OS << " }";
288  return OS;
289}
290
291raw_ostream &operator<<(raw_ostream &OS, const SymbolState &S) {
292  switch (S) {
293  case SymbolState::Invalid:
294    return OS << "Invalid";
295  case SymbolState::NeverSearched:
296    return OS << "Never-Searched";
297  case SymbolState::Materializing:
298    return OS << "Materializing";
299  case SymbolState::Resolved:
300    return OS << "Resolved";
301  case SymbolState::Emitted:
302    return OS << "Emitted";
303  case SymbolState::Ready:
304    return OS << "Ready";
305  }
306  llvm_unreachable("Invalid state");
307}
308
309FailedToMaterialize::FailedToMaterialize(
310    std::shared_ptr<SymbolDependenceMap> Symbols)
311    : Symbols(std::move(Symbols)) {
312  assert(!this->Symbols->empty() && "Can not fail to resolve an empty set");
313}
314
315std::error_code FailedToMaterialize::convertToErrorCode() const {
316  return orcError(OrcErrorCode::UnknownORCError);
317}
318
319void FailedToMaterialize::log(raw_ostream &OS) const {
320  OS << "Failed to materialize symbols: " << *Symbols;
321}
322
323SymbolsNotFound::SymbolsNotFound(SymbolNameSet Symbols) {
324  for (auto &Sym : Symbols)
325    this->Symbols.push_back(Sym);
326  assert(!this->Symbols.empty() && "Can not fail to resolve an empty set");
327}
328
329SymbolsNotFound::SymbolsNotFound(SymbolNameVector Symbols)
330    : Symbols(std::move(Symbols)) {
331  assert(!this->Symbols.empty() && "Can not fail to resolve an empty set");
332}
333
334std::error_code SymbolsNotFound::convertToErrorCode() const {
335  return orcError(OrcErrorCode::UnknownORCError);
336}
337
338void SymbolsNotFound::log(raw_ostream &OS) const {
339  OS << "Symbols not found: " << Symbols;
340}
341
342SymbolsCouldNotBeRemoved::SymbolsCouldNotBeRemoved(SymbolNameSet Symbols)
343    : Symbols(std::move(Symbols)) {
344  assert(!this->Symbols.empty() && "Can not fail to resolve an empty set");
345}
346
347std::error_code SymbolsCouldNotBeRemoved::convertToErrorCode() const {
348  return orcError(OrcErrorCode::UnknownORCError);
349}
350
351void SymbolsCouldNotBeRemoved::log(raw_ostream &OS) const {
352  OS << "Symbols could not be removed: " << Symbols;
353}
354
355AsynchronousSymbolQuery::AsynchronousSymbolQuery(
356    const SymbolLookupSet &Symbols, SymbolState RequiredState,
357    SymbolsResolvedCallback NotifyComplete)
358    : NotifyComplete(std::move(NotifyComplete)), RequiredState(RequiredState) {
359  assert(RequiredState >= SymbolState::Resolved &&
360         "Cannot query for a symbols that have not reached the resolve state "
361         "yet");
362
363  OutstandingSymbolsCount = Symbols.size();
364
365  for (auto &KV : Symbols)
366    ResolvedSymbols[KV.first] = nullptr;
367}
368
369void AsynchronousSymbolQuery::notifySymbolMetRequiredState(
370    const SymbolStringPtr &Name, JITEvaluatedSymbol Sym) {
371  auto I = ResolvedSymbols.find(Name);
372  assert(I != ResolvedSymbols.end() &&
373         "Resolving symbol outside the requested set");
374  assert(I->second.getAddress() == 0 && "Redundantly resolving symbol Name");
375  I->second = std::move(Sym);
376  --OutstandingSymbolsCount;
377}
378
379void AsynchronousSymbolQuery::handleComplete() {
380  assert(OutstandingSymbolsCount == 0 &&
381         "Symbols remain, handleComplete called prematurely");
382
383  auto TmpNotifyComplete = std::move(NotifyComplete);
384  NotifyComplete = SymbolsResolvedCallback();
385  TmpNotifyComplete(std::move(ResolvedSymbols));
386}
387
388bool AsynchronousSymbolQuery::canStillFail() { return !!NotifyComplete; }
389
390void AsynchronousSymbolQuery::handleFailed(Error Err) {
391  assert(QueryRegistrations.empty() && ResolvedSymbols.empty() &&
392         OutstandingSymbolsCount == 0 &&
393         "Query should already have been abandoned");
394  NotifyComplete(std::move(Err));
395  NotifyComplete = SymbolsResolvedCallback();
396}
397
398void AsynchronousSymbolQuery::addQueryDependence(JITDylib &JD,
399                                                 SymbolStringPtr Name) {
400  bool Added = QueryRegistrations[&JD].insert(std::move(Name)).second;
401  (void)Added;
402  assert(Added && "Duplicate dependence notification?");
403}
404
405void AsynchronousSymbolQuery::removeQueryDependence(
406    JITDylib &JD, const SymbolStringPtr &Name) {
407  auto QRI = QueryRegistrations.find(&JD);
408  assert(QRI != QueryRegistrations.end() &&
409         "No dependencies registered for JD");
410  assert(QRI->second.count(Name) && "No dependency on Name in JD");
411  QRI->second.erase(Name);
412  if (QRI->second.empty())
413    QueryRegistrations.erase(QRI);
414}
415
416void AsynchronousSymbolQuery::detach() {
417  ResolvedSymbols.clear();
418  OutstandingSymbolsCount = 0;
419  for (auto &KV : QueryRegistrations)
420    KV.first->detachQueryHelper(*this, KV.second);
421  QueryRegistrations.clear();
422}
423
424MaterializationResponsibility::MaterializationResponsibility(
425    JITDylib &JD, SymbolFlagsMap SymbolFlags, VModuleKey K)
426    : JD(JD), SymbolFlags(std::move(SymbolFlags)), K(std::move(K)) {
427  assert(!this->SymbolFlags.empty() && "Materializing nothing?");
428}
429
430MaterializationResponsibility::~MaterializationResponsibility() {
431  assert(SymbolFlags.empty() &&
432         "All symbols should have been explicitly materialized or failed");
433}
434
435SymbolNameSet MaterializationResponsibility::getRequestedSymbols() const {
436  return JD.getRequestedSymbols(SymbolFlags);
437}
438
439Error MaterializationResponsibility::notifyResolved(const SymbolMap &Symbols) {
440  LLVM_DEBUG({
441    dbgs() << "In " << JD.getName() << " resolving " << Symbols << "\n";
442  });
443#ifndef NDEBUG
444  for (auto &KV : Symbols) {
445    auto WeakFlags = JITSymbolFlags::Weak | JITSymbolFlags::Common;
446    auto I = SymbolFlags.find(KV.first);
447    assert(I != SymbolFlags.end() &&
448           "Resolving symbol outside this responsibility set");
449    assert((KV.second.getFlags() & ~WeakFlags) == (I->second & ~WeakFlags) &&
450           "Resolving symbol with incorrect flags");
451  }
452#endif
453
454  return JD.resolve(Symbols);
455}
456
457Error MaterializationResponsibility::notifyEmitted() {
458
459  LLVM_DEBUG({
460    dbgs() << "In " << JD.getName() << " emitting " << SymbolFlags << "\n";
461  });
462
463  if (auto Err = JD.emit(SymbolFlags))
464    return Err;
465
466  SymbolFlags.clear();
467  return Error::success();
468}
469
470Error MaterializationResponsibility::defineMaterializing(
471    SymbolFlagsMap NewSymbolFlags) {
472
473  LLVM_DEBUG({
474      dbgs() << "In " << JD.getName() << " defining materializing symbols "
475             << NewSymbolFlags << "\n";
476    });
477  if (auto AcceptedDefs = JD.defineMaterializing(std::move(NewSymbolFlags))) {
478    // Add all newly accepted symbols to this responsibility object.
479    for (auto &KV : *AcceptedDefs)
480      SymbolFlags.insert(KV);
481    return Error::success();
482  } else
483    return AcceptedDefs.takeError();
484}
485
486void MaterializationResponsibility::failMaterialization() {
487
488  LLVM_DEBUG({
489    dbgs() << "In " << JD.getName() << " failing materialization for "
490           << SymbolFlags << "\n";
491  });
492
493  JITDylib::FailedSymbolsWorklist Worklist;
494
495  for (auto &KV : SymbolFlags)
496    Worklist.push_back(std::make_pair(&JD, KV.first));
497  SymbolFlags.clear();
498
499  JD.notifyFailed(std::move(Worklist));
500}
501
502void MaterializationResponsibility::replace(
503    std::unique_ptr<MaterializationUnit> MU) {
504  for (auto &KV : MU->getSymbols())
505    SymbolFlags.erase(KV.first);
506
507  LLVM_DEBUG(JD.getExecutionSession().runSessionLocked([&]() {
508    dbgs() << "In " << JD.getName() << " replacing symbols with " << *MU
509           << "\n";
510  }););
511
512  JD.replace(std::move(MU));
513}
514
515MaterializationResponsibility
516MaterializationResponsibility::delegate(const SymbolNameSet &Symbols,
517                                        VModuleKey NewKey) {
518
519  if (NewKey == VModuleKey())
520    NewKey = K;
521
522  SymbolFlagsMap DelegatedFlags;
523
524  for (auto &Name : Symbols) {
525    auto I = SymbolFlags.find(Name);
526    assert(I != SymbolFlags.end() &&
527           "Symbol is not tracked by this MaterializationResponsibility "
528           "instance");
529
530    DelegatedFlags[Name] = std::move(I->second);
531    SymbolFlags.erase(I);
532  }
533
534  return MaterializationResponsibility(JD, std::move(DelegatedFlags),
535                                       std::move(NewKey));
536}
537
538void MaterializationResponsibility::addDependencies(
539    const SymbolStringPtr &Name, const SymbolDependenceMap &Dependencies) {
540  assert(SymbolFlags.count(Name) &&
541         "Symbol not covered by this MaterializationResponsibility instance");
542  JD.addDependencies(Name, Dependencies);
543}
544
545void MaterializationResponsibility::addDependenciesForAll(
546    const SymbolDependenceMap &Dependencies) {
547  for (auto &KV : SymbolFlags)
548    JD.addDependencies(KV.first, Dependencies);
549}
550
551AbsoluteSymbolsMaterializationUnit::AbsoluteSymbolsMaterializationUnit(
552    SymbolMap Symbols, VModuleKey K)
553    : MaterializationUnit(extractFlags(Symbols), std::move(K)),
554      Symbols(std::move(Symbols)) {}
555
556StringRef AbsoluteSymbolsMaterializationUnit::getName() const {
557  return "<Absolute Symbols>";
558}
559
560void AbsoluteSymbolsMaterializationUnit::materialize(
561    MaterializationResponsibility R) {
562  // No dependencies, so these calls can't fail.
563  cantFail(R.notifyResolved(Symbols));
564  cantFail(R.notifyEmitted());
565}
566
567void AbsoluteSymbolsMaterializationUnit::discard(const JITDylib &JD,
568                                                 const SymbolStringPtr &Name) {
569  assert(Symbols.count(Name) && "Symbol is not part of this MU");
570  Symbols.erase(Name);
571}
572
573SymbolFlagsMap
574AbsoluteSymbolsMaterializationUnit::extractFlags(const SymbolMap &Symbols) {
575  SymbolFlagsMap Flags;
576  for (const auto &KV : Symbols)
577    Flags[KV.first] = KV.second.getFlags();
578  return Flags;
579}
580
581ReExportsMaterializationUnit::ReExportsMaterializationUnit(
582    JITDylib *SourceJD, JITDylibLookupFlags SourceJDLookupFlags,
583    SymbolAliasMap Aliases, VModuleKey K)
584    : MaterializationUnit(extractFlags(Aliases), std::move(K)),
585      SourceJD(SourceJD), SourceJDLookupFlags(SourceJDLookupFlags),
586      Aliases(std::move(Aliases)) {}
587
588StringRef ReExportsMaterializationUnit::getName() const {
589  return "<Reexports>";
590}
591
592void ReExportsMaterializationUnit::materialize(
593    MaterializationResponsibility R) {
594
595  auto &ES = R.getTargetJITDylib().getExecutionSession();
596  JITDylib &TgtJD = R.getTargetJITDylib();
597  JITDylib &SrcJD = SourceJD ? *SourceJD : TgtJD;
598
599  // Find the set of requested aliases and aliasees. Return any unrequested
600  // aliases back to the JITDylib so as to not prematurely materialize any
601  // aliasees.
602  auto RequestedSymbols = R.getRequestedSymbols();
603  SymbolAliasMap RequestedAliases;
604
605  for (auto &Name : RequestedSymbols) {
606    auto I = Aliases.find(Name);
607    assert(I != Aliases.end() && "Symbol not found in aliases map?");
608    RequestedAliases[Name] = std::move(I->second);
609    Aliases.erase(I);
610  }
611
612  LLVM_DEBUG({
613    ES.runSessionLocked([&]() {
614      dbgs() << "materializing reexports: target = " << TgtJD.getName()
615             << ", source = " << SrcJD.getName() << " " << RequestedAliases
616             << "\n";
617    });
618  });
619
620  if (!Aliases.empty()) {
621    if (SourceJD)
622      R.replace(reexports(*SourceJD, std::move(Aliases), SourceJDLookupFlags));
623    else
624      R.replace(symbolAliases(std::move(Aliases)));
625  }
626
627  // The OnResolveInfo struct will hold the aliases and responsibilty for each
628  // query in the list.
629  struct OnResolveInfo {
630    OnResolveInfo(MaterializationResponsibility R, SymbolAliasMap Aliases)
631        : R(std::move(R)), Aliases(std::move(Aliases)) {}
632
633    MaterializationResponsibility R;
634    SymbolAliasMap Aliases;
635  };
636
637  // Build a list of queries to issue. In each round we build the largest set of
638  // aliases that we can resolve without encountering a chain definition of the
639  // form Foo -> Bar, Bar -> Baz. Such a form would deadlock as the query would
640  // be waitin on a symbol that it itself had to resolve. Usually this will just
641  // involve one round and a single query.
642
643  std::vector<std::pair<SymbolLookupSet, std::shared_ptr<OnResolveInfo>>>
644      QueryInfos;
645  while (!RequestedAliases.empty()) {
646    SymbolNameSet ResponsibilitySymbols;
647    SymbolLookupSet QuerySymbols;
648    SymbolAliasMap QueryAliases;
649
650    // Collect as many aliases as we can without including a chain.
651    for (auto &KV : RequestedAliases) {
652      // Chain detected. Skip this symbol for this round.
653      if (&SrcJD == &TgtJD && (QueryAliases.count(KV.second.Aliasee) ||
654                               RequestedAliases.count(KV.second.Aliasee)))
655        continue;
656
657      ResponsibilitySymbols.insert(KV.first);
658      QuerySymbols.add(KV.second.Aliasee);
659      QueryAliases[KV.first] = std::move(KV.second);
660    }
661
662    // Remove the aliases collected this round from the RequestedAliases map.
663    for (auto &KV : QueryAliases)
664      RequestedAliases.erase(KV.first);
665
666    assert(!QuerySymbols.empty() && "Alias cycle detected!");
667
668    auto QueryInfo = std::make_shared<OnResolveInfo>(
669        R.delegate(ResponsibilitySymbols), std::move(QueryAliases));
670    QueryInfos.push_back(
671        make_pair(std::move(QuerySymbols), std::move(QueryInfo)));
672  }
673
674  // Issue the queries.
675  while (!QueryInfos.empty()) {
676    auto QuerySymbols = std::move(QueryInfos.back().first);
677    auto QueryInfo = std::move(QueryInfos.back().second);
678
679    QueryInfos.pop_back();
680
681    auto RegisterDependencies = [QueryInfo,
682                                 &SrcJD](const SymbolDependenceMap &Deps) {
683      // If there were no materializing symbols, just bail out.
684      if (Deps.empty())
685        return;
686
687      // Otherwise the only deps should be on SrcJD.
688      assert(Deps.size() == 1 && Deps.count(&SrcJD) &&
689             "Unexpected dependencies for reexports");
690
691      auto &SrcJDDeps = Deps.find(&SrcJD)->second;
692      SymbolDependenceMap PerAliasDepsMap;
693      auto &PerAliasDeps = PerAliasDepsMap[&SrcJD];
694
695      for (auto &KV : QueryInfo->Aliases)
696        if (SrcJDDeps.count(KV.second.Aliasee)) {
697          PerAliasDeps = {KV.second.Aliasee};
698          QueryInfo->R.addDependencies(KV.first, PerAliasDepsMap);
699        }
700    };
701
702    auto OnComplete = [QueryInfo](Expected<SymbolMap> Result) {
703      auto &ES = QueryInfo->R.getTargetJITDylib().getExecutionSession();
704      if (Result) {
705        SymbolMap ResolutionMap;
706        for (auto &KV : QueryInfo->Aliases) {
707          assert(Result->count(KV.second.Aliasee) &&
708                 "Result map missing entry?");
709          ResolutionMap[KV.first] = JITEvaluatedSymbol(
710              (*Result)[KV.second.Aliasee].getAddress(), KV.second.AliasFlags);
711        }
712        if (auto Err = QueryInfo->R.notifyResolved(ResolutionMap)) {
713          ES.reportError(std::move(Err));
714          QueryInfo->R.failMaterialization();
715          return;
716        }
717        if (auto Err = QueryInfo->R.notifyEmitted()) {
718          ES.reportError(std::move(Err));
719          QueryInfo->R.failMaterialization();
720          return;
721        }
722      } else {
723        ES.reportError(Result.takeError());
724        QueryInfo->R.failMaterialization();
725      }
726    };
727
728    ES.lookup(LookupKind::Static,
729              JITDylibSearchOrder({{&SrcJD, SourceJDLookupFlags}}),
730              QuerySymbols, SymbolState::Resolved, std::move(OnComplete),
731              std::move(RegisterDependencies));
732  }
733}
734
735void ReExportsMaterializationUnit::discard(const JITDylib &JD,
736                                           const SymbolStringPtr &Name) {
737  assert(Aliases.count(Name) &&
738         "Symbol not covered by this MaterializationUnit");
739  Aliases.erase(Name);
740}
741
742SymbolFlagsMap
743ReExportsMaterializationUnit::extractFlags(const SymbolAliasMap &Aliases) {
744  SymbolFlagsMap SymbolFlags;
745  for (auto &KV : Aliases)
746    SymbolFlags[KV.first] = KV.second.AliasFlags;
747
748  return SymbolFlags;
749}
750
751Expected<SymbolAliasMap>
752buildSimpleReexportsAliasMap(JITDylib &SourceJD, const SymbolNameSet &Symbols) {
753  SymbolLookupSet LookupSet(Symbols);
754  auto Flags = SourceJD.lookupFlags(
755      LookupKind::Static, JITDylibLookupFlags::MatchAllSymbols, LookupSet);
756
757  if (!Flags)
758    return Flags.takeError();
759
760  if (!LookupSet.empty()) {
761    LookupSet.sortByName();
762    return make_error<SymbolsNotFound>(LookupSet.getSymbolNames());
763  }
764
765  SymbolAliasMap Result;
766  for (auto &Name : Symbols) {
767    assert(Flags->count(Name) && "Missing entry in flags map");
768    Result[Name] = SymbolAliasMapEntry(Name, (*Flags)[Name]);
769  }
770
771  return Result;
772}
773
774ReexportsGenerator::ReexportsGenerator(JITDylib &SourceJD,
775                                       JITDylibLookupFlags SourceJDLookupFlags,
776                                       SymbolPredicate Allow)
777    : SourceJD(SourceJD), SourceJDLookupFlags(SourceJDLookupFlags),
778      Allow(std::move(Allow)) {}
779
780Error ReexportsGenerator::tryToGenerate(LookupKind K, JITDylib &JD,
781                                        JITDylibLookupFlags JDLookupFlags,
782                                        const SymbolLookupSet &LookupSet) {
783  assert(&JD != &SourceJD && "Cannot re-export from the same dylib");
784
785  // Use lookupFlags to find the subset of symbols that match our lookup.
786  auto Flags = SourceJD.lookupFlags(K, JDLookupFlags, LookupSet);
787  if (!Flags)
788    return Flags.takeError();
789
790  // Create an alias map.
791  orc::SymbolAliasMap AliasMap;
792  for (auto &KV : *Flags)
793    if (!Allow || Allow(KV.first))
794      AliasMap[KV.first] = SymbolAliasMapEntry(KV.first, KV.second);
795
796  if (AliasMap.empty())
797    return Error::success();
798
799  // Define the re-exports.
800  return JD.define(reexports(SourceJD, AliasMap, SourceJDLookupFlags));
801}
802
803JITDylib::DefinitionGenerator::~DefinitionGenerator() {}
804
805void JITDylib::removeGenerator(DefinitionGenerator &G) {
806  ES.runSessionLocked([&]() {
807    auto I = std::find_if(DefGenerators.begin(), DefGenerators.end(),
808                          [&](const std::unique_ptr<DefinitionGenerator> &H) {
809                            return H.get() == &G;
810                          });
811    assert(I != DefGenerators.end() && "Generator not found");
812    DefGenerators.erase(I);
813  });
814}
815
816Expected<SymbolFlagsMap>
817JITDylib::defineMaterializing(SymbolFlagsMap SymbolFlags) {
818
819  return ES.runSessionLocked([&]() -> Expected<SymbolFlagsMap> {
820    std::vector<SymbolTable::iterator> AddedSyms;
821    std::vector<SymbolFlagsMap::iterator> RejectedWeakDefs;
822
823    for (auto SFItr = SymbolFlags.begin(), SFEnd = SymbolFlags.end();
824         SFItr != SFEnd; ++SFItr) {
825
826      auto &Name = SFItr->first;
827      auto &Flags = SFItr->second;
828
829      auto EntryItr = Symbols.find(Name);
830
831      // If the entry already exists...
832      if (EntryItr != Symbols.end()) {
833
834        // If this is a strong definition then error out.
835        if (!Flags.isWeak()) {
836          // Remove any symbols already added.
837          for (auto &SI : AddedSyms)
838            Symbols.erase(SI);
839
840          // FIXME: Return all duplicates.
841          return make_error<DuplicateDefinition>(*Name);
842        }
843
844        // Otherwise just make a note to discard this symbol after the loop.
845        RejectedWeakDefs.push_back(SFItr);
846        continue;
847      } else
848        EntryItr =
849          Symbols.insert(std::make_pair(Name, SymbolTableEntry(Flags))).first;
850
851      AddedSyms.push_back(EntryItr);
852      EntryItr->second.setState(SymbolState::Materializing);
853    }
854
855    // Remove any rejected weak definitions from the SymbolFlags map.
856    while (!RejectedWeakDefs.empty()) {
857      SymbolFlags.erase(RejectedWeakDefs.back());
858      RejectedWeakDefs.pop_back();
859    }
860
861    return SymbolFlags;
862  });
863}
864
865void JITDylib::replace(std::unique_ptr<MaterializationUnit> MU) {
866  assert(MU != nullptr && "Can not replace with a null MaterializationUnit");
867
868  auto MustRunMU =
869      ES.runSessionLocked([&, this]() -> std::unique_ptr<MaterializationUnit> {
870
871#ifndef NDEBUG
872        for (auto &KV : MU->getSymbols()) {
873          auto SymI = Symbols.find(KV.first);
874          assert(SymI != Symbols.end() && "Replacing unknown symbol");
875          assert(SymI->second.isInMaterializationPhase() &&
876                 "Can not call replace on a symbol that is not materializing");
877          assert(!SymI->second.hasMaterializerAttached() &&
878                 "Symbol should not have materializer attached already");
879          assert(UnmaterializedInfos.count(KV.first) == 0 &&
880                 "Symbol being replaced should have no UnmaterializedInfo");
881        }
882#endif // NDEBUG
883
884        // If any symbol has pending queries against it then we need to
885        // materialize MU immediately.
886        for (auto &KV : MU->getSymbols()) {
887          auto MII = MaterializingInfos.find(KV.first);
888          if (MII != MaterializingInfos.end()) {
889            if (MII->second.hasQueriesPending())
890              return std::move(MU);
891          }
892        }
893
894        // Otherwise, make MU responsible for all the symbols.
895        auto UMI = std::make_shared<UnmaterializedInfo>(std::move(MU));
896        for (auto &KV : UMI->MU->getSymbols()) {
897          auto SymI = Symbols.find(KV.first);
898          assert(SymI->second.getState() == SymbolState::Materializing &&
899                 "Can not replace a symbol that is not materializing");
900          assert(!SymI->second.hasMaterializerAttached() &&
901                 "Can not replace a symbol that has a materializer attached");
902          assert(UnmaterializedInfos.count(KV.first) == 0 &&
903                 "Unexpected materializer entry in map");
904          SymI->second.setAddress(SymI->second.getAddress());
905          SymI->second.setMaterializerAttached(true);
906          UnmaterializedInfos[KV.first] = UMI;
907        }
908
909        return nullptr;
910      });
911
912  if (MustRunMU)
913    ES.dispatchMaterialization(*this, std::move(MustRunMU));
914}
915
916SymbolNameSet
917JITDylib::getRequestedSymbols(const SymbolFlagsMap &SymbolFlags) const {
918  return ES.runSessionLocked([&]() {
919    SymbolNameSet RequestedSymbols;
920
921    for (auto &KV : SymbolFlags) {
922      assert(Symbols.count(KV.first) && "JITDylib does not cover this symbol?");
923      assert(Symbols.find(KV.first)->second.isInMaterializationPhase() &&
924             "getRequestedSymbols can only be called for symbols that have "
925             "started materializing");
926      auto I = MaterializingInfos.find(KV.first);
927      if (I == MaterializingInfos.end())
928        continue;
929
930      if (I->second.hasQueriesPending())
931        RequestedSymbols.insert(KV.first);
932    }
933
934    return RequestedSymbols;
935  });
936}
937
938void JITDylib::addDependencies(const SymbolStringPtr &Name,
939                               const SymbolDependenceMap &Dependencies) {
940  assert(Symbols.count(Name) && "Name not in symbol table");
941  assert(Symbols[Name].isInMaterializationPhase() &&
942         "Can not add dependencies for a symbol that is not materializing");
943
944  // If Name is already in an error state then just bail out.
945  if (Symbols[Name].getFlags().hasError())
946    return;
947
948  auto &MI = MaterializingInfos[Name];
949  assert(Symbols[Name].getState() != SymbolState::Emitted &&
950         "Can not add dependencies to an emitted symbol");
951
952  bool DependsOnSymbolInErrorState = false;
953
954  // Register dependencies, record whether any depenendency is in the error
955  // state.
956  for (auto &KV : Dependencies) {
957    assert(KV.first && "Null JITDylib in dependency?");
958    auto &OtherJITDylib = *KV.first;
959    auto &DepsOnOtherJITDylib = MI.UnemittedDependencies[&OtherJITDylib];
960
961    for (auto &OtherSymbol : KV.second) {
962
963      // Check the sym entry for the dependency.
964      auto OtherSymI = OtherJITDylib.Symbols.find(OtherSymbol);
965
966#ifndef NDEBUG
967      // Assert that this symbol exists and has not reached the ready state
968      // already.
969      assert(OtherSymI != OtherJITDylib.Symbols.end() &&
970             (OtherSymI->second.getState() != SymbolState::Ready &&
971              "Dependency on emitted/ready symbol"));
972#endif
973
974      auto &OtherSymEntry = OtherSymI->second;
975
976      // If the dependency is in an error state then note this and continue,
977      // we will move this symbol to the error state below.
978      if (OtherSymEntry.getFlags().hasError()) {
979        DependsOnSymbolInErrorState = true;
980        continue;
981      }
982
983      // If the dependency was not in the error state then add it to
984      // our list of dependencies.
985      assert(OtherJITDylib.MaterializingInfos.count(OtherSymbol) &&
986             "No MaterializingInfo for dependency");
987      auto &OtherMI = OtherJITDylib.MaterializingInfos[OtherSymbol];
988
989      if (OtherSymEntry.getState() == SymbolState::Emitted)
990        transferEmittedNodeDependencies(MI, Name, OtherMI);
991      else if (&OtherJITDylib != this || OtherSymbol != Name) {
992        OtherMI.Dependants[this].insert(Name);
993        DepsOnOtherJITDylib.insert(OtherSymbol);
994      }
995    }
996
997    if (DepsOnOtherJITDylib.empty())
998      MI.UnemittedDependencies.erase(&OtherJITDylib);
999  }
1000
1001  // If this symbol dependended on any symbols in the error state then move
1002  // this symbol to the error state too.
1003  if (DependsOnSymbolInErrorState)
1004    Symbols[Name].setFlags(Symbols[Name].getFlags() | JITSymbolFlags::HasError);
1005}
1006
1007Error JITDylib::resolve(const SymbolMap &Resolved) {
1008  SymbolNameSet SymbolsInErrorState;
1009  AsynchronousSymbolQuerySet CompletedQueries;
1010
1011  ES.runSessionLocked([&, this]() {
1012    struct WorklistEntry {
1013      SymbolTable::iterator SymI;
1014      JITEvaluatedSymbol ResolvedSym;
1015    };
1016
1017    std::vector<WorklistEntry> Worklist;
1018    Worklist.reserve(Resolved.size());
1019
1020    // Build worklist and check for any symbols in the error state.
1021    for (const auto &KV : Resolved) {
1022
1023      assert(!KV.second.getFlags().hasError() &&
1024             "Resolution result can not have error flag set");
1025
1026      auto SymI = Symbols.find(KV.first);
1027
1028      assert(SymI != Symbols.end() && "Symbol not found");
1029      assert(!SymI->second.hasMaterializerAttached() &&
1030             "Resolving symbol with materializer attached?");
1031      assert(SymI->second.getState() == SymbolState::Materializing &&
1032             "Symbol should be materializing");
1033      assert(SymI->second.getAddress() == 0 &&
1034             "Symbol has already been resolved");
1035
1036      if (SymI->second.getFlags().hasError())
1037        SymbolsInErrorState.insert(KV.first);
1038      else {
1039        auto Flags = KV.second.getFlags();
1040        Flags &= ~(JITSymbolFlags::Weak | JITSymbolFlags::Common);
1041        assert(Flags == (SymI->second.getFlags() &
1042                         ~(JITSymbolFlags::Weak | JITSymbolFlags::Common)) &&
1043               "Resolved flags should match the declared flags");
1044
1045        Worklist.push_back(
1046            {SymI, JITEvaluatedSymbol(KV.second.getAddress(), Flags)});
1047      }
1048    }
1049
1050    // If any symbols were in the error state then bail out.
1051    if (!SymbolsInErrorState.empty())
1052      return;
1053
1054    while (!Worklist.empty()) {
1055      auto SymI = Worklist.back().SymI;
1056      auto ResolvedSym = Worklist.back().ResolvedSym;
1057      Worklist.pop_back();
1058
1059      auto &Name = SymI->first;
1060
1061      // Resolved symbols can not be weak: discard the weak flag.
1062      JITSymbolFlags ResolvedFlags = ResolvedSym.getFlags();
1063      SymI->second.setAddress(ResolvedSym.getAddress());
1064      SymI->second.setFlags(ResolvedFlags);
1065      SymI->second.setState(SymbolState::Resolved);
1066
1067      auto &MI = MaterializingInfos[Name];
1068      for (auto &Q : MI.takeQueriesMeeting(SymbolState::Resolved)) {
1069        Q->notifySymbolMetRequiredState(Name, ResolvedSym);
1070        Q->removeQueryDependence(*this, Name);
1071        if (Q->isComplete())
1072          CompletedQueries.insert(std::move(Q));
1073      }
1074    }
1075  });
1076
1077  assert((SymbolsInErrorState.empty() || CompletedQueries.empty()) &&
1078         "Can't fail symbols and completed queries at the same time");
1079
1080  // If we failed any symbols then return an error.
1081  if (!SymbolsInErrorState.empty()) {
1082    auto FailedSymbolsDepMap = std::make_shared<SymbolDependenceMap>();
1083    (*FailedSymbolsDepMap)[this] = std::move(SymbolsInErrorState);
1084    return make_error<FailedToMaterialize>(std::move(FailedSymbolsDepMap));
1085  }
1086
1087  // Otherwise notify all the completed queries.
1088  for (auto &Q : CompletedQueries) {
1089    assert(Q->isComplete() && "Q not completed");
1090    Q->handleComplete();
1091  }
1092
1093  return Error::success();
1094}
1095
1096Error JITDylib::emit(const SymbolFlagsMap &Emitted) {
1097  AsynchronousSymbolQuerySet CompletedQueries;
1098  SymbolNameSet SymbolsInErrorState;
1099
1100  ES.runSessionLocked([&, this]() {
1101    std::vector<SymbolTable::iterator> Worklist;
1102
1103    // Scan to build worklist, record any symbols in the erorr state.
1104    for (const auto &KV : Emitted) {
1105      auto &Name = KV.first;
1106
1107      auto SymI = Symbols.find(Name);
1108      assert(SymI != Symbols.end() && "No symbol table entry for Name");
1109
1110      if (SymI->second.getFlags().hasError())
1111        SymbolsInErrorState.insert(Name);
1112      else
1113        Worklist.push_back(SymI);
1114    }
1115
1116    // If any symbols were in the error state then bail out.
1117    if (!SymbolsInErrorState.empty())
1118      return;
1119
1120    // Otherwise update dependencies and move to the emitted state.
1121    while (!Worklist.empty()) {
1122      auto SymI = Worklist.back();
1123      Worklist.pop_back();
1124
1125      auto &Name = SymI->first;
1126      auto &SymEntry = SymI->second;
1127
1128      // Move symbol to the emitted state.
1129      assert(SymEntry.getState() == SymbolState::Resolved &&
1130             "Emitting from state other than Resolved");
1131      SymEntry.setState(SymbolState::Emitted);
1132
1133      auto MII = MaterializingInfos.find(Name);
1134      assert(MII != MaterializingInfos.end() &&
1135             "Missing MaterializingInfo entry");
1136      auto &MI = MII->second;
1137
1138      // For each dependant, transfer this node's emitted dependencies to
1139      // it. If the dependant node is ready (i.e. has no unemitted
1140      // dependencies) then notify any pending queries.
1141      for (auto &KV : MI.Dependants) {
1142        auto &DependantJD = *KV.first;
1143        for (auto &DependantName : KV.second) {
1144          auto DependantMII =
1145              DependantJD.MaterializingInfos.find(DependantName);
1146          assert(DependantMII != DependantJD.MaterializingInfos.end() &&
1147                 "Dependant should have MaterializingInfo");
1148
1149          auto &DependantMI = DependantMII->second;
1150
1151          // Remove the dependant's dependency on this node.
1152          assert(DependantMI.UnemittedDependencies.count(this) &&
1153                 "Dependant does not have an unemitted dependencies record for "
1154                 "this JITDylib");
1155          assert(DependantMI.UnemittedDependencies[this].count(Name) &&
1156                 "Dependant does not count this symbol as a dependency?");
1157
1158          DependantMI.UnemittedDependencies[this].erase(Name);
1159          if (DependantMI.UnemittedDependencies[this].empty())
1160            DependantMI.UnemittedDependencies.erase(this);
1161
1162          // Transfer unemitted dependencies from this node to the dependant.
1163          DependantJD.transferEmittedNodeDependencies(DependantMI,
1164                                                      DependantName, MI);
1165
1166          auto DependantSymI = DependantJD.Symbols.find(DependantName);
1167          assert(DependantSymI != DependantJD.Symbols.end() &&
1168                 "Dependant has no entry in the Symbols table");
1169          auto &DependantSymEntry = DependantSymI->second;
1170
1171          // If the dependant is emitted and this node was the last of its
1172          // unemitted dependencies then the dependant node is now ready, so
1173          // notify any pending queries on the dependant node.
1174          if (DependantSymEntry.getState() == SymbolState::Emitted &&
1175              DependantMI.UnemittedDependencies.empty()) {
1176            assert(DependantMI.Dependants.empty() &&
1177                   "Dependants should be empty by now");
1178
1179            // Since this dependant is now ready, we erase its MaterializingInfo
1180            // and update its materializing state.
1181            DependantSymEntry.setState(SymbolState::Ready);
1182
1183            for (auto &Q : DependantMI.takeQueriesMeeting(SymbolState::Ready)) {
1184              Q->notifySymbolMetRequiredState(
1185                  DependantName, DependantSymI->second.getSymbol());
1186              if (Q->isComplete())
1187                CompletedQueries.insert(Q);
1188              Q->removeQueryDependence(DependantJD, DependantName);
1189            }
1190
1191            DependantJD.MaterializingInfos.erase(DependantMII);
1192          }
1193        }
1194      }
1195
1196      MI.Dependants.clear();
1197      if (MI.UnemittedDependencies.empty()) {
1198        SymI->second.setState(SymbolState::Ready);
1199        for (auto &Q : MI.takeQueriesMeeting(SymbolState::Ready)) {
1200          Q->notifySymbolMetRequiredState(Name, SymI->second.getSymbol());
1201          if (Q->isComplete())
1202            CompletedQueries.insert(Q);
1203          Q->removeQueryDependence(*this, Name);
1204        }
1205        MaterializingInfos.erase(MII);
1206      }
1207    }
1208  });
1209
1210  assert((SymbolsInErrorState.empty() || CompletedQueries.empty()) &&
1211         "Can't fail symbols and completed queries at the same time");
1212
1213  // If we failed any symbols then return an error.
1214  if (!SymbolsInErrorState.empty()) {
1215    auto FailedSymbolsDepMap = std::make_shared<SymbolDependenceMap>();
1216    (*FailedSymbolsDepMap)[this] = std::move(SymbolsInErrorState);
1217    return make_error<FailedToMaterialize>(std::move(FailedSymbolsDepMap));
1218  }
1219
1220  // Otherwise notify all the completed queries.
1221  for (auto &Q : CompletedQueries) {
1222    assert(Q->isComplete() && "Q is not complete");
1223    Q->handleComplete();
1224  }
1225
1226  return Error::success();
1227}
1228
1229void JITDylib::notifyFailed(FailedSymbolsWorklist Worklist) {
1230  AsynchronousSymbolQuerySet FailedQueries;
1231  auto FailedSymbolsMap = std::make_shared<SymbolDependenceMap>();
1232
1233  // Failing no symbols is a no-op.
1234  if (Worklist.empty())
1235    return;
1236
1237  auto &ES = Worklist.front().first->getExecutionSession();
1238
1239  ES.runSessionLocked([&]() {
1240    while (!Worklist.empty()) {
1241      assert(Worklist.back().first && "Failed JITDylib can not be null");
1242      auto &JD = *Worklist.back().first;
1243      auto Name = std::move(Worklist.back().second);
1244      Worklist.pop_back();
1245
1246      (*FailedSymbolsMap)[&JD].insert(Name);
1247
1248      assert(JD.Symbols.count(Name) && "No symbol table entry for Name");
1249      auto &Sym = JD.Symbols[Name];
1250
1251      // Move the symbol into the error state.
1252      // Note that this may be redundant: The symbol might already have been
1253      // moved to this state in response to the failure of a dependence.
1254      Sym.setFlags(Sym.getFlags() | JITSymbolFlags::HasError);
1255
1256      // FIXME: Come up with a sane mapping of state to
1257      // presence-of-MaterializingInfo so that we can assert presence / absence
1258      // here, rather than testing it.
1259      auto MII = JD.MaterializingInfos.find(Name);
1260
1261      if (MII == JD.MaterializingInfos.end())
1262        continue;
1263
1264      auto &MI = MII->second;
1265
1266      // Move all dependants to the error state and disconnect from them.
1267      for (auto &KV : MI.Dependants) {
1268        auto &DependantJD = *KV.first;
1269        for (auto &DependantName : KV.second) {
1270          assert(DependantJD.Symbols.count(DependantName) &&
1271                 "No symbol table entry for DependantName");
1272          auto &DependantSym = DependantJD.Symbols[DependantName];
1273          DependantSym.setFlags(DependantSym.getFlags() |
1274                                JITSymbolFlags::HasError);
1275
1276          assert(DependantJD.MaterializingInfos.count(DependantName) &&
1277                 "No MaterializingInfo for dependant");
1278          auto &DependantMI = DependantJD.MaterializingInfos[DependantName];
1279
1280          auto UnemittedDepI = DependantMI.UnemittedDependencies.find(&JD);
1281          assert(UnemittedDepI != DependantMI.UnemittedDependencies.end() &&
1282                 "No UnemittedDependencies entry for this JITDylib");
1283          assert(UnemittedDepI->second.count(Name) &&
1284                 "No UnemittedDependencies entry for this symbol");
1285          UnemittedDepI->second.erase(Name);
1286          if (UnemittedDepI->second.empty())
1287            DependantMI.UnemittedDependencies.erase(UnemittedDepI);
1288
1289          // If this symbol is already in the emitted state then we need to
1290          // take responsibility for failing its queries, so add it to the
1291          // worklist.
1292          if (DependantSym.getState() == SymbolState::Emitted) {
1293            assert(DependantMI.Dependants.empty() &&
1294                   "Emitted symbol should not have dependants");
1295            Worklist.push_back(std::make_pair(&DependantJD, DependantName));
1296          }
1297        }
1298      }
1299      MI.Dependants.clear();
1300
1301      // Disconnect from all unemitted depenencies.
1302      for (auto &KV : MI.UnemittedDependencies) {
1303        auto &UnemittedDepJD = *KV.first;
1304        for (auto &UnemittedDepName : KV.second) {
1305          auto UnemittedDepMII =
1306              UnemittedDepJD.MaterializingInfos.find(UnemittedDepName);
1307          assert(UnemittedDepMII != UnemittedDepJD.MaterializingInfos.end() &&
1308                 "Missing MII for unemitted dependency");
1309          assert(UnemittedDepMII->second.Dependants.count(&JD) &&
1310                 "JD not listed as a dependant of unemitted dependency");
1311          assert(UnemittedDepMII->second.Dependants[&JD].count(Name) &&
1312                 "Name is not listed as a dependant of unemitted dependency");
1313          UnemittedDepMII->second.Dependants[&JD].erase(Name);
1314          if (UnemittedDepMII->second.Dependants[&JD].empty())
1315            UnemittedDepMII->second.Dependants.erase(&JD);
1316        }
1317      }
1318      MI.UnemittedDependencies.clear();
1319
1320      // Collect queries to be failed for this MII.
1321      AsynchronousSymbolQueryList ToDetach;
1322      for (auto &Q : MII->second.pendingQueries()) {
1323        // Add the query to the list to be failed and detach it.
1324        FailedQueries.insert(Q);
1325        ToDetach.push_back(Q);
1326      }
1327      for (auto &Q : ToDetach)
1328        Q->detach();
1329
1330      assert(MI.Dependants.empty() &&
1331             "Can not delete MaterializingInfo with dependants still attached");
1332      assert(MI.UnemittedDependencies.empty() &&
1333             "Can not delete MaterializingInfo with unemitted dependencies "
1334             "still attached");
1335      assert(!MI.hasQueriesPending() &&
1336             "Can not delete MaterializingInfo with queries pending");
1337      JD.MaterializingInfos.erase(MII);
1338    }
1339  });
1340
1341  for (auto &Q : FailedQueries)
1342    Q->handleFailed(make_error<FailedToMaterialize>(FailedSymbolsMap));
1343}
1344
1345void JITDylib::setSearchOrder(JITDylibSearchOrder NewSearchOrder,
1346                              bool SearchThisJITDylibFirst) {
1347  ES.runSessionLocked([&]() {
1348    if (SearchThisJITDylibFirst) {
1349      SearchOrder.clear();
1350      if (NewSearchOrder.empty() || NewSearchOrder.front().first != this)
1351        SearchOrder.push_back(
1352            std::make_pair(this, JITDylibLookupFlags::MatchAllSymbols));
1353      SearchOrder.insert(SearchOrder.end(), NewSearchOrder.begin(),
1354                         NewSearchOrder.end());
1355    } else
1356      SearchOrder = std::move(NewSearchOrder);
1357  });
1358}
1359
1360void JITDylib::addToSearchOrder(JITDylib &JD,
1361                                JITDylibLookupFlags JDLookupFlags) {
1362  ES.runSessionLocked([&]() { SearchOrder.push_back({&JD, JDLookupFlags}); });
1363}
1364
1365void JITDylib::replaceInSearchOrder(JITDylib &OldJD, JITDylib &NewJD,
1366                                    JITDylibLookupFlags JDLookupFlags) {
1367  ES.runSessionLocked([&]() {
1368    for (auto &KV : SearchOrder)
1369      if (KV.first == &OldJD) {
1370        KV = {&NewJD, JDLookupFlags};
1371        break;
1372      }
1373  });
1374}
1375
1376void JITDylib::removeFromSearchOrder(JITDylib &JD) {
1377  ES.runSessionLocked([&]() {
1378    auto I = std::find_if(SearchOrder.begin(), SearchOrder.end(),
1379                          [&](const JITDylibSearchOrder::value_type &KV) {
1380                            return KV.first == &JD;
1381                          });
1382    if (I != SearchOrder.end())
1383      SearchOrder.erase(I);
1384  });
1385}
1386
1387Error JITDylib::remove(const SymbolNameSet &Names) {
1388  return ES.runSessionLocked([&]() -> Error {
1389    using SymbolMaterializerItrPair =
1390        std::pair<SymbolTable::iterator, UnmaterializedInfosMap::iterator>;
1391    std::vector<SymbolMaterializerItrPair> SymbolsToRemove;
1392    SymbolNameSet Missing;
1393    SymbolNameSet Materializing;
1394
1395    for (auto &Name : Names) {
1396      auto I = Symbols.find(Name);
1397
1398      // Note symbol missing.
1399      if (I == Symbols.end()) {
1400        Missing.insert(Name);
1401        continue;
1402      }
1403
1404      // Note symbol materializing.
1405      if (I->second.isInMaterializationPhase()) {
1406        Materializing.insert(Name);
1407        continue;
1408      }
1409
1410      auto UMII = I->second.hasMaterializerAttached()
1411                      ? UnmaterializedInfos.find(Name)
1412                      : UnmaterializedInfos.end();
1413      SymbolsToRemove.push_back(std::make_pair(I, UMII));
1414    }
1415
1416    // If any of the symbols are not defined, return an error.
1417    if (!Missing.empty())
1418      return make_error<SymbolsNotFound>(std::move(Missing));
1419
1420    // If any of the symbols are currently materializing, return an error.
1421    if (!Materializing.empty())
1422      return make_error<SymbolsCouldNotBeRemoved>(std::move(Materializing));
1423
1424    // Remove the symbols.
1425    for (auto &SymbolMaterializerItrPair : SymbolsToRemove) {
1426      auto UMII = SymbolMaterializerItrPair.second;
1427
1428      // If there is a materializer attached, call discard.
1429      if (UMII != UnmaterializedInfos.end()) {
1430        UMII->second->MU->doDiscard(*this, UMII->first);
1431        UnmaterializedInfos.erase(UMII);
1432      }
1433
1434      auto SymI = SymbolMaterializerItrPair.first;
1435      Symbols.erase(SymI);
1436    }
1437
1438    return Error::success();
1439  });
1440}
1441
1442Expected<SymbolFlagsMap>
1443JITDylib::lookupFlags(LookupKind K, JITDylibLookupFlags JDLookupFlags,
1444                      SymbolLookupSet LookupSet) {
1445  return ES.runSessionLocked([&, this]() -> Expected<SymbolFlagsMap> {
1446    SymbolFlagsMap Result;
1447    lookupFlagsImpl(Result, K, JDLookupFlags, LookupSet);
1448
1449    // Run any definition generators.
1450    for (auto &DG : DefGenerators) {
1451
1452      // Bail out early if we found everything.
1453      if (LookupSet.empty())
1454        break;
1455
1456      // Run this generator.
1457      if (auto Err = DG->tryToGenerate(K, *this, JDLookupFlags, LookupSet))
1458        return std::move(Err);
1459
1460      // Re-try the search.
1461      lookupFlagsImpl(Result, K, JDLookupFlags, LookupSet);
1462    }
1463
1464    return Result;
1465  });
1466}
1467
1468void JITDylib::lookupFlagsImpl(SymbolFlagsMap &Result, LookupKind K,
1469                               JITDylibLookupFlags JDLookupFlags,
1470                               SymbolLookupSet &LookupSet) {
1471
1472  LookupSet.forEachWithRemoval(
1473      [&](const SymbolStringPtr &Name, SymbolLookupFlags Flags) -> bool {
1474        auto I = Symbols.find(Name);
1475        if (I == Symbols.end())
1476          return false;
1477        assert(!Result.count(Name) && "Symbol already present in Flags map");
1478        Result[Name] = I->second.getFlags();
1479        return true;
1480      });
1481}
1482
1483Error JITDylib::lodgeQuery(MaterializationUnitList &MUs,
1484                           std::shared_ptr<AsynchronousSymbolQuery> &Q,
1485                           LookupKind K, JITDylibLookupFlags JDLookupFlags,
1486                           SymbolLookupSet &Unresolved) {
1487  assert(Q && "Query can not be null");
1488
1489  if (auto Err = lodgeQueryImpl(MUs, Q, K, JDLookupFlags, Unresolved))
1490    return Err;
1491
1492  // Run any definition generators.
1493  for (auto &DG : DefGenerators) {
1494
1495    // Bail out early if we have resolved everything.
1496    if (Unresolved.empty())
1497      break;
1498
1499    // Run the generator.
1500    if (auto Err = DG->tryToGenerate(K, *this, JDLookupFlags, Unresolved))
1501      return Err;
1502
1503    // Lodge query. This can not fail as any new definitions were added
1504    // by the generator under the session locked. Since they can't have
1505    // started materializing yet they can not have failed.
1506    cantFail(lodgeQueryImpl(MUs, Q, K, JDLookupFlags, Unresolved));
1507  }
1508
1509  return Error::success();
1510}
1511
1512Error JITDylib::lodgeQueryImpl(MaterializationUnitList &MUs,
1513                               std::shared_ptr<AsynchronousSymbolQuery> &Q,
1514                               LookupKind K, JITDylibLookupFlags JDLookupFlags,
1515                               SymbolLookupSet &Unresolved) {
1516
1517  return Unresolved.forEachWithRemoval(
1518      [&](const SymbolStringPtr &Name,
1519          SymbolLookupFlags SymLookupFlags) -> Expected<bool> {
1520        // Search for name in symbols. If not found then continue without
1521        // removal.
1522        auto SymI = Symbols.find(Name);
1523        if (SymI == Symbols.end())
1524          return false;
1525
1526        // If this is a non exported symbol and we're matching exported symbols
1527        // only then skip this symbol without removal.
1528        if (!SymI->second.getFlags().isExported() &&
1529            JDLookupFlags == JITDylibLookupFlags::MatchExportedSymbolsOnly)
1530          return false;
1531
1532        // If we matched against this symbol but it is in the error state then
1533        // bail out and treat it as a failure to materialize.
1534        if (SymI->second.getFlags().hasError()) {
1535          auto FailedSymbolsMap = std::make_shared<SymbolDependenceMap>();
1536          (*FailedSymbolsMap)[this] = {Name};
1537          return make_error<FailedToMaterialize>(std::move(FailedSymbolsMap));
1538        }
1539
1540        // If this symbol already meets the required state for then notify the
1541        // query, then remove the symbol and continue.
1542        if (SymI->second.getState() >= Q->getRequiredState()) {
1543          Q->notifySymbolMetRequiredState(Name, SymI->second.getSymbol());
1544          return true;
1545        }
1546
1547        // Otherwise this symbol does not yet meet the required state. Check
1548        // whether it has a materializer attached, and if so prepare to run it.
1549        if (SymI->second.hasMaterializerAttached()) {
1550          assert(SymI->second.getAddress() == 0 &&
1551                 "Symbol not resolved but already has address?");
1552          auto UMII = UnmaterializedInfos.find(Name);
1553          assert(UMII != UnmaterializedInfos.end() &&
1554                 "Lazy symbol should have UnmaterializedInfo");
1555          auto MU = std::move(UMII->second->MU);
1556          assert(MU != nullptr && "Materializer should not be null");
1557
1558          // Move all symbols associated with this MaterializationUnit into
1559          // materializing state.
1560          for (auto &KV : MU->getSymbols()) {
1561            auto SymK = Symbols.find(KV.first);
1562            SymK->second.setMaterializerAttached(false);
1563            SymK->second.setState(SymbolState::Materializing);
1564            UnmaterializedInfos.erase(KV.first);
1565          }
1566
1567          // Add MU to the list of MaterializationUnits to be materialized.
1568          MUs.push_back(std::move(MU));
1569        }
1570
1571        // Add the query to the PendingQueries list and continue, deleting the
1572        // element.
1573        assert(SymI->second.isInMaterializationPhase() &&
1574               "By this line the symbol should be materializing");
1575        auto &MI = MaterializingInfos[Name];
1576        MI.addQuery(Q);
1577        Q->addQueryDependence(*this, Name);
1578        return true;
1579      });
1580}
1581
1582Expected<SymbolNameSet>
1583JITDylib::legacyLookup(std::shared_ptr<AsynchronousSymbolQuery> Q,
1584                       SymbolNameSet Names) {
1585  assert(Q && "Query can not be null");
1586
1587  ES.runOutstandingMUs();
1588
1589  bool QueryComplete = false;
1590  std::vector<std::unique_ptr<MaterializationUnit>> MUs;
1591
1592  SymbolLookupSet Unresolved(Names);
1593  auto Err = ES.runSessionLocked([&, this]() -> Error {
1594    QueryComplete = lookupImpl(Q, MUs, Unresolved);
1595
1596    // Run any definition generators.
1597    for (auto &DG : DefGenerators) {
1598
1599      // Bail out early if we have resolved everything.
1600      if (Unresolved.empty())
1601        break;
1602
1603      assert(!QueryComplete && "query complete but unresolved symbols remain?");
1604      if (auto Err = DG->tryToGenerate(LookupKind::Static, *this,
1605                                       JITDylibLookupFlags::MatchAllSymbols,
1606                                       Unresolved))
1607        return Err;
1608
1609      if (!Unresolved.empty())
1610        QueryComplete = lookupImpl(Q, MUs, Unresolved);
1611    }
1612    return Error::success();
1613  });
1614
1615  if (Err)
1616    return std::move(Err);
1617
1618  assert((MUs.empty() || !QueryComplete) &&
1619         "If action flags are set, there should be no work to do (so no MUs)");
1620
1621  if (QueryComplete)
1622    Q->handleComplete();
1623
1624  // FIXME: Swap back to the old code below once RuntimeDyld works with
1625  //        callbacks from asynchronous queries.
1626  // Add MUs to the OutstandingMUs list.
1627  {
1628    std::lock_guard<std::recursive_mutex> Lock(ES.OutstandingMUsMutex);
1629    for (auto &MU : MUs)
1630      ES.OutstandingMUs.push_back(make_pair(this, std::move(MU)));
1631  }
1632  ES.runOutstandingMUs();
1633
1634  // Dispatch any required MaterializationUnits for materialization.
1635  // for (auto &MU : MUs)
1636  //  ES.dispatchMaterialization(*this, std::move(MU));
1637
1638  SymbolNameSet RemainingSymbols;
1639  for (auto &KV : Unresolved)
1640    RemainingSymbols.insert(KV.first);
1641
1642  return RemainingSymbols;
1643}
1644
1645bool JITDylib::lookupImpl(
1646    std::shared_ptr<AsynchronousSymbolQuery> &Q,
1647    std::vector<std::unique_ptr<MaterializationUnit>> &MUs,
1648    SymbolLookupSet &Unresolved) {
1649  bool QueryComplete = false;
1650
1651  std::vector<SymbolStringPtr> ToRemove;
1652  Unresolved.forEachWithRemoval(
1653      [&](const SymbolStringPtr &Name, SymbolLookupFlags Flags) -> bool {
1654        // Search for the name in Symbols. Skip without removing if not found.
1655        auto SymI = Symbols.find(Name);
1656        if (SymI == Symbols.end())
1657          return false;
1658
1659        // If the symbol is already in the required state then notify the query
1660        // and remove.
1661        if (SymI->second.getState() >= Q->getRequiredState()) {
1662          Q->notifySymbolMetRequiredState(Name, SymI->second.getSymbol());
1663          if (Q->isComplete())
1664            QueryComplete = true;
1665          return true;
1666        }
1667
1668        // If the symbol is lazy, get the MaterialiaztionUnit for it.
1669        if (SymI->second.hasMaterializerAttached()) {
1670          assert(SymI->second.getAddress() == 0 &&
1671                 "Lazy symbol should not have a resolved address");
1672          auto UMII = UnmaterializedInfos.find(Name);
1673          assert(UMII != UnmaterializedInfos.end() &&
1674                 "Lazy symbol should have UnmaterializedInfo");
1675          auto MU = std::move(UMII->second->MU);
1676          assert(MU != nullptr && "Materializer should not be null");
1677
1678          // Kick all symbols associated with this MaterializationUnit into
1679          // materializing state.
1680          for (auto &KV : MU->getSymbols()) {
1681            auto SymK = Symbols.find(KV.first);
1682            assert(SymK != Symbols.end() && "Missing symbol table entry");
1683            SymK->second.setState(SymbolState::Materializing);
1684            SymK->second.setMaterializerAttached(false);
1685            UnmaterializedInfos.erase(KV.first);
1686          }
1687
1688          // Add MU to the list of MaterializationUnits to be materialized.
1689          MUs.push_back(std::move(MU));
1690        }
1691
1692        // Add the query to the PendingQueries list.
1693        assert(SymI->second.isInMaterializationPhase() &&
1694               "By this line the symbol should be materializing");
1695        auto &MI = MaterializingInfos[Name];
1696        MI.addQuery(Q);
1697        Q->addQueryDependence(*this, Name);
1698        return true;
1699      });
1700
1701  return QueryComplete;
1702}
1703
1704void JITDylib::dump(raw_ostream &OS) {
1705  ES.runSessionLocked([&, this]() {
1706    OS << "JITDylib \"" << JITDylibName << "\" (ES: "
1707       << format("0x%016" PRIx64, reinterpret_cast<uintptr_t>(&ES)) << "):\n"
1708       << "Search order: " << SearchOrder << "\n"
1709       << "Symbol table:\n";
1710
1711    for (auto &KV : Symbols) {
1712      OS << "    \"" << *KV.first << "\": ";
1713      if (auto Addr = KV.second.getAddress())
1714        OS << format("0x%016" PRIx64, Addr) << ", " << KV.second.getFlags()
1715           << " ";
1716      else
1717        OS << "<not resolved> ";
1718
1719      OS << KV.second.getState();
1720
1721      if (KV.second.hasMaterializerAttached()) {
1722        OS << " (Materializer ";
1723        auto I = UnmaterializedInfos.find(KV.first);
1724        assert(I != UnmaterializedInfos.end() &&
1725               "Lazy symbol should have UnmaterializedInfo");
1726        OS << I->second->MU.get() << ")\n";
1727      } else
1728        OS << "\n";
1729    }
1730
1731    if (!MaterializingInfos.empty())
1732      OS << "  MaterializingInfos entries:\n";
1733    for (auto &KV : MaterializingInfos) {
1734      OS << "    \"" << *KV.first << "\":\n"
1735         << "      " << KV.second.pendingQueries().size()
1736         << " pending queries: { ";
1737      for (const auto &Q : KV.second.pendingQueries())
1738        OS << Q.get() << " (" << Q->getRequiredState() << ") ";
1739      OS << "}\n      Dependants:\n";
1740      for (auto &KV2 : KV.second.Dependants)
1741        OS << "        " << KV2.first->getName() << ": " << KV2.second << "\n";
1742      OS << "      Unemitted Dependencies:\n";
1743      for (auto &KV2 : KV.second.UnemittedDependencies)
1744        OS << "        " << KV2.first->getName() << ": " << KV2.second << "\n";
1745    }
1746  });
1747}
1748
1749void JITDylib::MaterializingInfo::addQuery(
1750    std::shared_ptr<AsynchronousSymbolQuery> Q) {
1751
1752  auto I = std::lower_bound(
1753      PendingQueries.rbegin(), PendingQueries.rend(), Q->getRequiredState(),
1754      [](const std::shared_ptr<AsynchronousSymbolQuery> &V, SymbolState S) {
1755        return V->getRequiredState() <= S;
1756      });
1757  PendingQueries.insert(I.base(), std::move(Q));
1758}
1759
1760void JITDylib::MaterializingInfo::removeQuery(
1761    const AsynchronousSymbolQuery &Q) {
1762  // FIXME: Implement 'find_as' for shared_ptr<T>/T*.
1763  auto I =
1764      std::find_if(PendingQueries.begin(), PendingQueries.end(),
1765                   [&Q](const std::shared_ptr<AsynchronousSymbolQuery> &V) {
1766                     return V.get() == &Q;
1767                   });
1768  assert(I != PendingQueries.end() &&
1769         "Query is not attached to this MaterializingInfo");
1770  PendingQueries.erase(I);
1771}
1772
1773JITDylib::AsynchronousSymbolQueryList
1774JITDylib::MaterializingInfo::takeQueriesMeeting(SymbolState RequiredState) {
1775  AsynchronousSymbolQueryList Result;
1776  while (!PendingQueries.empty()) {
1777    if (PendingQueries.back()->getRequiredState() > RequiredState)
1778      break;
1779
1780    Result.push_back(std::move(PendingQueries.back()));
1781    PendingQueries.pop_back();
1782  }
1783
1784  return Result;
1785}
1786
1787JITDylib::JITDylib(ExecutionSession &ES, std::string Name)
1788    : ES(ES), JITDylibName(std::move(Name)) {
1789  SearchOrder.push_back({this, JITDylibLookupFlags::MatchAllSymbols});
1790}
1791
1792Error JITDylib::defineImpl(MaterializationUnit &MU) {
1793  SymbolNameSet Duplicates;
1794  std::vector<SymbolStringPtr> ExistingDefsOverridden;
1795  std::vector<SymbolStringPtr> MUDefsOverridden;
1796
1797  for (const auto &KV : MU.getSymbols()) {
1798    auto I = Symbols.find(KV.first);
1799
1800    if (I != Symbols.end()) {
1801      if (KV.second.isStrong()) {
1802        if (I->second.getFlags().isStrong() ||
1803            I->second.getState() > SymbolState::NeverSearched)
1804          Duplicates.insert(KV.first);
1805        else {
1806          assert(I->second.getState() == SymbolState::NeverSearched &&
1807                 "Overridden existing def should be in the never-searched "
1808                 "state");
1809          ExistingDefsOverridden.push_back(KV.first);
1810        }
1811      } else
1812        MUDefsOverridden.push_back(KV.first);
1813    }
1814  }
1815
1816  // If there were any duplicate definitions then bail out.
1817  if (!Duplicates.empty())
1818    return make_error<DuplicateDefinition>(**Duplicates.begin());
1819
1820  // Discard any overridden defs in this MU.
1821  for (auto &S : MUDefsOverridden)
1822    MU.doDiscard(*this, S);
1823
1824  // Discard existing overridden defs.
1825  for (auto &S : ExistingDefsOverridden) {
1826
1827    auto UMII = UnmaterializedInfos.find(S);
1828    assert(UMII != UnmaterializedInfos.end() &&
1829           "Overridden existing def should have an UnmaterializedInfo");
1830    UMII->second->MU->doDiscard(*this, S);
1831  }
1832
1833  // Finally, add the defs from this MU.
1834  for (auto &KV : MU.getSymbols()) {
1835    auto &SymEntry = Symbols[KV.first];
1836    SymEntry.setFlags(KV.second);
1837    SymEntry.setState(SymbolState::NeverSearched);
1838    SymEntry.setMaterializerAttached(true);
1839  }
1840
1841  return Error::success();
1842}
1843
1844void JITDylib::detachQueryHelper(AsynchronousSymbolQuery &Q,
1845                                 const SymbolNameSet &QuerySymbols) {
1846  for (auto &QuerySymbol : QuerySymbols) {
1847    assert(MaterializingInfos.count(QuerySymbol) &&
1848           "QuerySymbol does not have MaterializingInfo");
1849    auto &MI = MaterializingInfos[QuerySymbol];
1850    MI.removeQuery(Q);
1851  }
1852}
1853
1854void JITDylib::transferEmittedNodeDependencies(
1855    MaterializingInfo &DependantMI, const SymbolStringPtr &DependantName,
1856    MaterializingInfo &EmittedMI) {
1857  for (auto &KV : EmittedMI.UnemittedDependencies) {
1858    auto &DependencyJD = *KV.first;
1859    SymbolNameSet *UnemittedDependenciesOnDependencyJD = nullptr;
1860
1861    for (auto &DependencyName : KV.second) {
1862      auto &DependencyMI = DependencyJD.MaterializingInfos[DependencyName];
1863
1864      // Do not add self dependencies.
1865      if (&DependencyMI == &DependantMI)
1866        continue;
1867
1868      // If we haven't looked up the dependencies for DependencyJD yet, do it
1869      // now and cache the result.
1870      if (!UnemittedDependenciesOnDependencyJD)
1871        UnemittedDependenciesOnDependencyJD =
1872            &DependantMI.UnemittedDependencies[&DependencyJD];
1873
1874      DependencyMI.Dependants[this].insert(DependantName);
1875      UnemittedDependenciesOnDependencyJD->insert(DependencyName);
1876    }
1877  }
1878}
1879
1880ExecutionSession::ExecutionSession(std::shared_ptr<SymbolStringPool> SSP)
1881    : SSP(SSP ? std::move(SSP) : std::make_shared<SymbolStringPool>()) {
1882}
1883
1884JITDylib *ExecutionSession::getJITDylibByName(StringRef Name) {
1885  return runSessionLocked([&, this]() -> JITDylib * {
1886    for (auto &JD : JDs)
1887      if (JD->getName() == Name)
1888        return JD.get();
1889    return nullptr;
1890  });
1891}
1892
1893JITDylib &ExecutionSession::createJITDylib(std::string Name) {
1894  assert(!getJITDylibByName(Name) && "JITDylib with that name already exists");
1895  return runSessionLocked([&, this]() -> JITDylib & {
1896    JDs.push_back(
1897        std::unique_ptr<JITDylib>(new JITDylib(*this, std::move(Name))));
1898    return *JDs.back();
1899  });
1900}
1901
1902void ExecutionSession::legacyFailQuery(AsynchronousSymbolQuery &Q, Error Err) {
1903  assert(!!Err && "Error should be in failure state");
1904
1905  bool SendErrorToQuery;
1906  runSessionLocked([&]() {
1907    Q.detach();
1908    SendErrorToQuery = Q.canStillFail();
1909  });
1910
1911  if (SendErrorToQuery)
1912    Q.handleFailed(std::move(Err));
1913  else
1914    reportError(std::move(Err));
1915}
1916
1917Expected<SymbolMap> ExecutionSession::legacyLookup(
1918    LegacyAsyncLookupFunction AsyncLookup, SymbolNameSet Names,
1919    SymbolState RequiredState,
1920    RegisterDependenciesFunction RegisterDependencies) {
1921#if LLVM_ENABLE_THREADS
1922  // In the threaded case we use promises to return the results.
1923  std::promise<SymbolMap> PromisedResult;
1924  Error ResolutionError = Error::success();
1925  auto NotifyComplete = [&](Expected<SymbolMap> R) {
1926    if (R)
1927      PromisedResult.set_value(std::move(*R));
1928    else {
1929      ErrorAsOutParameter _(&ResolutionError);
1930      ResolutionError = R.takeError();
1931      PromisedResult.set_value(SymbolMap());
1932    }
1933  };
1934#else
1935  SymbolMap Result;
1936  Error ResolutionError = Error::success();
1937
1938  auto NotifyComplete = [&](Expected<SymbolMap> R) {
1939    ErrorAsOutParameter _(&ResolutionError);
1940    if (R)
1941      Result = std::move(*R);
1942    else
1943      ResolutionError = R.takeError();
1944  };
1945#endif
1946
1947  auto Query = std::make_shared<AsynchronousSymbolQuery>(
1948      SymbolLookupSet(Names), RequiredState, std::move(NotifyComplete));
1949  // FIXME: This should be run session locked along with the registration code
1950  // and error reporting below.
1951  SymbolNameSet UnresolvedSymbols = AsyncLookup(Query, std::move(Names));
1952
1953  // If the query was lodged successfully then register the dependencies,
1954  // otherwise fail it with an error.
1955  if (UnresolvedSymbols.empty())
1956    RegisterDependencies(Query->QueryRegistrations);
1957  else {
1958    bool DeliverError = runSessionLocked([&]() {
1959      Query->detach();
1960      return Query->canStillFail();
1961    });
1962    auto Err = make_error<SymbolsNotFound>(std::move(UnresolvedSymbols));
1963    if (DeliverError)
1964      Query->handleFailed(std::move(Err));
1965    else
1966      reportError(std::move(Err));
1967  }
1968
1969#if LLVM_ENABLE_THREADS
1970  auto ResultFuture = PromisedResult.get_future();
1971  auto Result = ResultFuture.get();
1972  if (ResolutionError)
1973    return std::move(ResolutionError);
1974  return std::move(Result);
1975
1976#else
1977  if (ResolutionError)
1978    return std::move(ResolutionError);
1979
1980  return Result;
1981#endif
1982}
1983
1984void ExecutionSession::lookup(
1985    LookupKind K, const JITDylibSearchOrder &SearchOrder,
1986    SymbolLookupSet Symbols, SymbolState RequiredState,
1987    SymbolsResolvedCallback NotifyComplete,
1988    RegisterDependenciesFunction RegisterDependencies) {
1989
1990  LLVM_DEBUG({
1991    runSessionLocked([&]() {
1992      dbgs() << "Looking up " << Symbols << " in " << SearchOrder
1993             << " (required state: " << RequiredState << ")\n";
1994    });
1995  });
1996
1997  // lookup can be re-entered recursively if running on a single thread. Run any
1998  // outstanding MUs in case this query depends on them, otherwise this lookup
1999  // will starve waiting for a result from an MU that is stuck in the queue.
2000  runOutstandingMUs();
2001
2002  auto Unresolved = std::move(Symbols);
2003  std::map<JITDylib *, MaterializationUnitList> CollectedMUsMap;
2004  auto Q = std::make_shared<AsynchronousSymbolQuery>(Unresolved, RequiredState,
2005                                                     std::move(NotifyComplete));
2006  bool QueryComplete = false;
2007
2008  auto LodgingErr = runSessionLocked([&]() -> Error {
2009    auto LodgeQuery = [&]() -> Error {
2010      for (auto &KV : SearchOrder) {
2011        assert(KV.first && "JITDylibList entries must not be null");
2012        assert(!CollectedMUsMap.count(KV.first) &&
2013               "JITDylibList should not contain duplicate entries");
2014
2015        auto &JD = *KV.first;
2016        auto JDLookupFlags = KV.second;
2017        if (auto Err = JD.lodgeQuery(CollectedMUsMap[&JD], Q, K, JDLookupFlags,
2018                                     Unresolved))
2019          return Err;
2020      }
2021
2022      // Strip any weakly referenced symbols that were not found.
2023      Unresolved.forEachWithRemoval(
2024          [&](const SymbolStringPtr &Name, SymbolLookupFlags Flags) {
2025            if (Flags == SymbolLookupFlags::WeaklyReferencedSymbol) {
2026              Q->dropSymbol(Name);
2027              return true;
2028            }
2029            return false;
2030          });
2031
2032      if (!Unresolved.empty())
2033        return make_error<SymbolsNotFound>(Unresolved.getSymbolNames());
2034
2035      return Error::success();
2036    };
2037
2038    if (auto Err = LodgeQuery()) {
2039      // Query failed.
2040
2041      // Disconnect the query from its dependencies.
2042      Q->detach();
2043
2044      // Replace the MUs.
2045      for (auto &KV : CollectedMUsMap)
2046        for (auto &MU : KV.second)
2047          KV.first->replace(std::move(MU));
2048
2049      return Err;
2050    }
2051
2052    // Query lodged successfully.
2053
2054    // Record whether this query is fully ready / resolved. We will use
2055    // this to call handleFullyResolved/handleFullyReady outside the session
2056    // lock.
2057    QueryComplete = Q->isComplete();
2058
2059    // Call the register dependencies function.
2060    if (RegisterDependencies && !Q->QueryRegistrations.empty())
2061      RegisterDependencies(Q->QueryRegistrations);
2062
2063    return Error::success();
2064  });
2065
2066  if (LodgingErr) {
2067    Q->handleFailed(std::move(LodgingErr));
2068    return;
2069  }
2070
2071  if (QueryComplete)
2072    Q->handleComplete();
2073
2074  // Move the MUs to the OutstandingMUs list, then materialize.
2075  {
2076    std::lock_guard<std::recursive_mutex> Lock(OutstandingMUsMutex);
2077
2078    for (auto &KV : CollectedMUsMap)
2079      for (auto &MU : KV.second)
2080        OutstandingMUs.push_back(std::make_pair(KV.first, std::move(MU)));
2081  }
2082
2083  runOutstandingMUs();
2084}
2085
2086Expected<SymbolMap>
2087ExecutionSession::lookup(const JITDylibSearchOrder &SearchOrder,
2088                         const SymbolLookupSet &Symbols, LookupKind K,
2089                         SymbolState RequiredState,
2090                         RegisterDependenciesFunction RegisterDependencies) {
2091#if LLVM_ENABLE_THREADS
2092  // In the threaded case we use promises to return the results.
2093  std::promise<SymbolMap> PromisedResult;
2094  Error ResolutionError = Error::success();
2095
2096  auto NotifyComplete = [&](Expected<SymbolMap> R) {
2097    if (R)
2098      PromisedResult.set_value(std::move(*R));
2099    else {
2100      ErrorAsOutParameter _(&ResolutionError);
2101      ResolutionError = R.takeError();
2102      PromisedResult.set_value(SymbolMap());
2103    }
2104  };
2105
2106#else
2107  SymbolMap Result;
2108  Error ResolutionError = Error::success();
2109
2110  auto NotifyComplete = [&](Expected<SymbolMap> R) {
2111    ErrorAsOutParameter _(&ResolutionError);
2112    if (R)
2113      Result = std::move(*R);
2114    else
2115      ResolutionError = R.takeError();
2116  };
2117#endif
2118
2119  // Perform the asynchronous lookup.
2120  lookup(K, SearchOrder, Symbols, RequiredState, NotifyComplete,
2121         RegisterDependencies);
2122
2123#if LLVM_ENABLE_THREADS
2124  auto ResultFuture = PromisedResult.get_future();
2125  auto Result = ResultFuture.get();
2126
2127  if (ResolutionError)
2128    return std::move(ResolutionError);
2129
2130  return std::move(Result);
2131
2132#else
2133  if (ResolutionError)
2134    return std::move(ResolutionError);
2135
2136  return Result;
2137#endif
2138}
2139
2140Expected<JITEvaluatedSymbol>
2141ExecutionSession::lookup(const JITDylibSearchOrder &SearchOrder,
2142                         SymbolStringPtr Name) {
2143  SymbolLookupSet Names({Name});
2144
2145  if (auto ResultMap = lookup(SearchOrder, std::move(Names), LookupKind::Static,
2146                              SymbolState::Ready, NoDependenciesToRegister)) {
2147    assert(ResultMap->size() == 1 && "Unexpected number of results");
2148    assert(ResultMap->count(Name) && "Missing result for symbol");
2149    return std::move(ResultMap->begin()->second);
2150  } else
2151    return ResultMap.takeError();
2152}
2153
2154Expected<JITEvaluatedSymbol>
2155ExecutionSession::lookup(ArrayRef<JITDylib *> SearchOrder,
2156                         SymbolStringPtr Name) {
2157  return lookup(makeJITDylibSearchOrder(SearchOrder), Name);
2158}
2159
2160Expected<JITEvaluatedSymbol>
2161ExecutionSession::lookup(ArrayRef<JITDylib *> SearchOrder, StringRef Name) {
2162  return lookup(SearchOrder, intern(Name));
2163}
2164
2165void ExecutionSession::dump(raw_ostream &OS) {
2166  runSessionLocked([this, &OS]() {
2167    for (auto &JD : JDs)
2168      JD->dump(OS);
2169  });
2170}
2171
2172void ExecutionSession::runOutstandingMUs() {
2173  while (1) {
2174    std::pair<JITDylib *, std::unique_ptr<MaterializationUnit>> JITDylibAndMU;
2175
2176    {
2177      std::lock_guard<std::recursive_mutex> Lock(OutstandingMUsMutex);
2178      if (!OutstandingMUs.empty()) {
2179        JITDylibAndMU = std::move(OutstandingMUs.back());
2180        OutstandingMUs.pop_back();
2181      }
2182    }
2183
2184    if (JITDylibAndMU.first) {
2185      assert(JITDylibAndMU.second && "JITDylib, but no MU?");
2186      dispatchMaterialization(*JITDylibAndMU.first,
2187                              std::move(JITDylibAndMU.second));
2188    } else
2189      break;
2190  }
2191}
2192
2193MangleAndInterner::MangleAndInterner(ExecutionSession &ES, const DataLayout &DL)
2194    : ES(ES), DL(DL) {}
2195
2196SymbolStringPtr MangleAndInterner::operator()(StringRef Name) {
2197  std::string MangledName;
2198  {
2199    raw_string_ostream MangledNameStream(MangledName);
2200    Mangler::getNameWithPrefix(MangledNameStream, Name, DL);
2201  }
2202  return ES.intern(MangledName);
2203}
2204
2205} // End namespace orc.
2206} // End namespace llvm.
2207