9f9b1b7126590173b3063d31157d059e24a94085
[lldb.git] / clang-tools-extra / clangd / index / Background.h
1 //===--- Background.h - Build an index in a background thread ----*- C++-*-===//
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 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_BACKGROUND_H
10 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_BACKGROUND_H
11
12 #include "GlobalCompilationDatabase.h"
13 #include "SourceCode.h"
14 #include "index/BackgroundRebuild.h"
15 #include "index/FileIndex.h"
16 #include "index/Index.h"
17 #include "index/Serialization.h"
18 #include "support/Context.h"
19 #include "support/Path.h"
20 #include "support/Threading.h"
21 #include "support/ThreadsafeFS.h"
22 #include "clang/Tooling/CompilationDatabase.h"
23 #include "llvm/ADT/StringMap.h"
24 #include "llvm/Support/Threading.h"
25 #include <atomic>
26 #include <condition_variable>
27 #include <deque>
28 #include <mutex>
29 #include <queue>
30 #include <string>
31 #include <thread>
32 #include <vector>
33
34 namespace clang {
35 namespace clangd {
36
37 // Handles storage and retrieval of index shards. Both store and load
38 // operations can be called from multiple-threads concurrently.
39 class BackgroundIndexStorage {
40 public:
41   virtual ~BackgroundIndexStorage() = default;
42
43   // Shards of the index are stored and retrieved independently, keyed by shard
44   // identifier - in practice this is a source file name
45   virtual llvm::Error storeShard(llvm::StringRef ShardIdentifier,
46                                  IndexFileOut Shard) const = 0;
47
48   // Tries to load shard with given identifier, returns nullptr if shard
49   // couldn't be loaded.
50   virtual std::unique_ptr<IndexFileIn>
51   loadShard(llvm::StringRef ShardIdentifier) const = 0;
52
53   // The factory provides storage for each File.
54   // It keeps ownership of the storage instances, and should manage caching
55   // itself. Factory must be threadsafe and never returns nullptr.
56   using Factory = llvm::unique_function<BackgroundIndexStorage *(PathRef)>;
57
58   // Creates an Index Storage that saves shards into disk. Index storage uses
59   // CDBDirectory + ".clangd/index/" as the folder to save shards. CDBDirectory
60   // is the first directory containing a CDB in parent directories of a file, or
61   // user's home directory if none was found, e.g. standard library headers.
62   static Factory createDiskBackedStorageFactory(
63       std::function<llvm::Optional<ProjectInfo>(PathRef)> GetProjectInfo);
64 };
65
66 // A priority queue of tasks which can be run on (external) worker threads.
67 class BackgroundQueue {
68 public:
69   /// A work item on the thread pool's queue.
70   struct Task {
71     explicit Task(std::function<void()> Run) : Run(std::move(Run)) {}
72
73     std::function<void()> Run;
74     llvm::ThreadPriority ThreadPri = llvm::ThreadPriority::Background;
75     unsigned QueuePri = 0; // Higher-priority tasks will run first.
76     std::string Tag;       // Allows priority to be boosted later.
77
78     bool operator<(const Task &O) const { return QueuePri < O.QueuePri; }
79   };
80
81   // Describes the number of tasks processed by the queue.
82   struct Stats {
83     unsigned Enqueued = 0;  // Total number of tasks ever enqueued.
84     unsigned Active = 0;    // Tasks being currently processed by a worker.
85     unsigned Completed = 0; // Tasks that have been finished.
86     unsigned LastIdle = 0;  // Number of completed tasks when last empty.
87   };
88
89   BackgroundQueue(std::function<void(Stats)> OnProgress = nullptr)
90       : OnProgress(OnProgress) {}
91
92   // Add tasks to the queue.
93   void push(Task);
94   void append(std::vector<Task>);
95   // Boost priority of current and new tasks with matching Tag, if they are
96   // lower priority.
97   // Reducing the boost of a tag affects future tasks but not current ones.
98   void boost(llvm::StringRef Tag, unsigned NewPriority);
99
100   // Process items on the queue until the queue is stopped.
101   // If the queue becomes empty, OnIdle will be called (on one worker).
102   void work(std::function<void()> OnIdle = nullptr);
103
104   // Stop processing new tasks, allowing all work() calls to return soon.
105   void stop();
106
107   // Disables thread priority lowering to ensure progress on loaded systems.
108   // Only affects tasks that run after the call.
109   static void preventThreadStarvationInTests();
110   LLVM_NODISCARD bool
111   blockUntilIdleForTest(llvm::Optional<double> TimeoutSeconds);
112
113 private:
114   void notifyProgress() const; // Requires lock Mu
115
116   std::mutex Mu;
117   Stats Stat;
118   std::condition_variable CV;
119   bool ShouldStop = false;
120   std::vector<Task> Queue; // max-heap
121   llvm::StringMap<unsigned> Boosts;
122   std::function<void(Stats)> OnProgress;
123 };
124
125 // Builds an in-memory index by by running the static indexer action over
126 // all commands in a compilation database. Indexing happens in the background.
127 // FIXME: it should also persist its state on disk for fast start.
128 // FIXME: it should watch for changes to files on disk.
129 class BackgroundIndex : public SwapIndex {
130 public:
131   /// If BuildIndexPeriodMs is greater than 0, the symbol index will only be
132   /// rebuilt periodically (one per \p BuildIndexPeriodMs); otherwise, index is
133   /// rebuilt for each indexed file.
134   BackgroundIndex(
135       Context BackgroundContext, const ThreadsafeFS &,
136       const GlobalCompilationDatabase &CDB,
137       BackgroundIndexStorage::Factory IndexStorageFactory,
138       // Arbitrary value to ensure some concurrency in tests.
139       // In production an explicit value is passed.
140       size_t ThreadPoolSize = 4,
141       std::function<void(BackgroundQueue::Stats)> OnProgress = nullptr,
142       std::function<Context(PathRef)> ContextProvider = nullptr);
143   ~BackgroundIndex(); // Blocks while the current task finishes.
144
145   // Enqueue translation units for indexing.
146   // The indexing happens in a background thread, so the symbols will be
147   // available sometime later.
148   void enqueue(const std::vector<std::string> &ChangedFiles) {
149     Queue.push(changedFilesTask(ChangedFiles));
150   }
151
152   /// Boosts priority of indexing related to Path.
153   /// Typically used to index TUs when headers are opened.
154   void boostRelated(llvm::StringRef Path);
155
156   // Cause background threads to stop after ther current task, any remaining
157   // tasks will be discarded.
158   void stop() {
159     Rebuilder.shutdown();
160     Queue.stop();
161   }
162
163   // Wait until the queue is empty, to allow deterministic testing.
164   LLVM_NODISCARD bool
165   blockUntilIdleForTest(llvm::Optional<double> TimeoutSeconds = 10) {
166     return Queue.blockUntilIdleForTest(TimeoutSeconds);
167   }
168
169 private:
170   /// Represents the state of a single file when indexing was performed.
171   struct ShardVersion {
172     FileDigest Digest{{0}};
173     bool HadErrors = false;
174   };
175
176   /// Given index results from a TU, only update symbols coming from files with
177   /// different digests than \p ShardVersionsSnapshot. Also stores new index
178   /// information on IndexStorage.
179   void update(llvm::StringRef MainFile, IndexFileIn Index,
180               const llvm::StringMap<ShardVersion> &ShardVersionsSnapshot,
181               bool HadErrors);
182
183   // configuration
184   const ThreadsafeFS &TFS;
185   const GlobalCompilationDatabase &CDB;
186   Context BackgroundContext;
187   std::function<Context(PathRef)> ContextProvider;
188
189   llvm::Error index(tooling::CompileCommand);
190
191   FileSymbols IndexedSymbols;
192   BackgroundIndexRebuilder Rebuilder;
193   llvm::StringMap<ShardVersion> ShardVersions; // Key is absolute file path.
194   std::mutex ShardVersionsMu;
195
196   BackgroundIndexStorage::Factory IndexStorageFactory;
197   // Tries to load shards for the MainFiles and their dependencies.
198   std::vector<std::string> loadProject(std::vector<std::string> MainFiles);
199
200   BackgroundQueue::Task
201   changedFilesTask(const std::vector<std::string> &ChangedFiles);
202   BackgroundQueue::Task indexFileTask(std::string Path);
203
204   // from lowest to highest priority
205   enum QueuePriority {
206     IndexFile,
207     IndexBoostedFile,
208     LoadShards,
209   };
210   BackgroundQueue Queue;
211   AsyncTaskRunner ThreadPool;
212   GlobalCompilationDatabase::CommandChanged::Subscription CommandsChanged;
213 };
214
215 } // namespace clangd
216 } // namespace clang
217
218 #endif