turbo_tasks/
persisted_graph.rs

1use anyhow::Result;
2use serde::{Deserialize, Serialize, ser::SerializeSeq};
3use smallvec::SmallVec;
4
5use crate::{
6    CellId, RawVc, TaskId,
7    backend::{CachedTaskType, CellContent},
8    task::shared_reference::TypedSharedReference,
9};
10
11#[derive(Clone, Debug)]
12pub enum TaskCell {
13    Content(CellContent),
14    NeedComputation,
15}
16
17impl Default for TaskCell {
18    fn default() -> Self {
19        TaskCell::Content(CellContent(None))
20    }
21}
22
23#[derive(Serialize, Deserialize, Debug)]
24pub struct TaskData {
25    pub children: SmallVec<[TaskId; 4]>,
26    pub dependencies: SmallVec<[RawVc; 1]>,
27    pub cells: TaskCells,
28    pub output: RawVc,
29}
30
31/// A newtype struct that intercepts serde. This is required
32/// because for safety reasons, TaskCell<()> is not allowed to
33/// be deserialized.
34///
35/// We augment it with type data then write it. This is inefficient
36/// on disk but could be alleviated later.
37#[derive(Debug)]
38pub struct TaskCells(pub Vec<(CellId, TaskCell)>);
39
40// the on-disk representation of a task cell. it is local to this impl
41// to prevent users accidentally ser/de the untyped data
42#[derive(Serialize, Deserialize)]
43struct SerializableTaskCell(Option<Option<TypedSharedReference>>);
44impl From<SerializableTaskCell> for TaskCell {
45    fn from(val: SerializableTaskCell) -> Self {
46        match val.0 {
47            Some(d) => TaskCell::Content(d.map(TypedSharedReference::into_untyped).into()),
48            None => TaskCell::NeedComputation,
49        }
50    }
51}
52
53impl Serialize for TaskCells {
54    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
55    where
56        S: serde::Serializer,
57    {
58        let mut seq = serializer.serialize_seq(Some(self.0.len()))?;
59        for (cell_id, cell) in &self.0 {
60            let task_cell = SerializableTaskCell(match cell {
61                TaskCell::Content(CellContent(opt)) => {
62                    Some(opt.clone().map(|d| d.into_typed(cell_id.type_id)))
63                }
64                TaskCell::NeedComputation => None,
65            });
66            seq.serialize_element(&(cell_id, task_cell))?;
67        }
68        seq.end()
69    }
70}
71
72impl<'de> Deserialize<'de> for TaskCells {
73    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
74    where
75        D: serde::Deserializer<'de>,
76    {
77        let data: Vec<(CellId, SerializableTaskCell)> = Vec::deserialize(deserializer)?;
78        Ok(TaskCells(
79            data.into_iter()
80                .map(|(id, cell)| (id, cell.into()))
81                .collect(),
82        ))
83    }
84}
85
86pub struct ReadTaskState {
87    pub clean: bool,
88    pub keeps_external_active: bool,
89}
90
91pub struct PersistTaskState {
92    pub externally_active: bool,
93}
94
95/*
96
97There are 4 kinds of task:
98
99(A) A task that exists only in memory.
100(B) A task that exists in persistent graph and in memory (either "store" or "read" has been called)
101(C) A task that exists only in persistent graph.
102
103Parent-child relationships:
104
105(A) as child: active_parents is tracked only in memory.
106(B) as child: active_parents is tracked in memory and either as internal_active_parents or external_active_parents in the persisted graph.
107(C) as child: either as internal_active_parents or external_active_parents in the persisted graph.
108
109(A) as parent: It will use external_active_parents for (B) or (C) as child.
110               update_active_parents() is used to modify the external_active_parents count.
111(B) as parent: It will use internal_active_parents for (B) or (C) as child.
112               compute_active() returns the changes needed for (A) or (C) as child
113(C) as parent: It will use internal_active_parents for (B) or (C) as child.
114               compute_active() returns the changes needed for (A) or (C) as child
115
116(A) as child of (B) or (C): active count tracked as external_active_children, have task ids assigned in persistent graph
117
118*/
119
120#[derive(Debug)]
121pub struct ActivateResult {
122    /// Keeps the external version of the task active
123    pub keeps_external_active: bool,
124
125    /// Task doesn't live in the persisted graph but
126    /// should be track externally
127    pub external: bool,
128
129    /// Task is dirty and need to be scheduled for execution
130    pub dirty: bool,
131
132    /// Further tasks that need to be activated that
133    /// didn't fit into that batch
134    pub more_tasks_to_activate: SmallVec<[TaskId; 4]>,
135}
136
137#[derive(Debug)]
138pub struct PersistResult {
139    /// Tasks that need to be activated
140    pub tasks_to_activate: SmallVec<[TaskId; 4]>,
141
142    /// Tasks that need to be deactivated
143    pub tasks_to_deactivate: SmallVec<[TaskId; 4]>,
144}
145
146#[derive(Debug)]
147pub struct DeactivateResult {
148    /// Further tasks that need to be deactivated that
149    /// didn't fit into that batch
150    pub more_tasks_to_deactivate: SmallVec<[TaskId; 4]>,
151}
152
153pub type TaskIds = SmallVec<[TaskId; 4]>;
154
155pub trait PersistedGraph: Sync + Send {
156    /// read task data and state for a specific task.
157    fn read(
158        &self,
159        task: TaskId,
160        api: &dyn PersistedGraphApi,
161    ) -> Result<Option<(TaskData, ReadTaskState)>>;
162
163    /// lookup all cache entries for a partial task type
164    /// returns true if all cache entries has been initialized
165    /// returns false if that were too many
166    fn lookup(
167        &self,
168        partial_task_type: &CachedTaskType,
169        api: &dyn PersistedGraphApi,
170    ) -> Result<bool>;
171
172    /// lookup one cache entry
173    fn lookup_one(
174        &self,
175        task_type: &CachedTaskType,
176        api: &dyn PersistedGraphApi,
177    ) -> Result<Option<TaskId>>;
178
179    /// checks if a task is persisted
180    fn is_persisted(&self, task: TaskId, api: &dyn PersistedGraphApi) -> Result<bool>;
181
182    /// store a completed task into the persisted graph
183    /// together with dependencies, children and cells.
184    /// Returns false, if the task failed to persist.
185    fn persist(
186        &self,
187        task: TaskId,
188        data: TaskData,
189        state: PersistTaskState,
190        api: &dyn PersistedGraphApi,
191    ) -> Result<Option<PersistResult>>;
192
193    /// Activate a task in the persisted graph when active_parents > 0 or it's
194    /// externally kept alive.
195    fn activate_when_needed(
196        &self,
197        task: TaskId,
198        api: &dyn PersistedGraphApi,
199    ) -> Result<Option<ActivateResult>>;
200
201    /// Deactivate a task in the persisted graph when active_parents == 0 and
202    /// it's not externally kept alive.
203    fn deactivate_when_needed(
204        &self,
205        task: TaskId,
206        api: &dyn PersistedGraphApi,
207    ) -> Result<Option<DeactivateResult>>;
208
209    /// Marks a task as kept alive by the consumer graph
210    /// (usually from memory to persisted graph)
211    /// Returns true when activate_when_needed should be called soonish
212    fn set_externally_active(&self, task: TaskId, api: &dyn PersistedGraphApi) -> Result<bool>;
213
214    /// No longer marks a task as kept alive by the consumer graph
215    /// (usually from memory to persisted graph)
216    /// Returns true when deactivate_when_needed should be called soonish
217    fn unset_externally_active(&self, task: TaskId, api: &dyn PersistedGraphApi) -> Result<bool>;
218
219    /// Removes all external keep alives that were not renewed this round.
220    /// This is usually called after the initial build has finished and all
221    /// external keep alives has been renewed.
222    fn remove_outdated_externally_active(
223        &self,
224        api: &dyn PersistedGraphApi,
225    ) -> Result<SmallVec<[TaskId; 4]>>;
226
227    /// update the dirty flag for a stored task
228    /// Returns true, when the task is active and should be scheduled
229    fn make_dirty(&self, task: TaskId, api: &dyn PersistedGraphApi) -> Result<bool>;
230
231    /// update the dirty flag for a stored task
232    fn make_clean(&self, task: TaskId, api: &dyn PersistedGraphApi) -> Result<()>;
233
234    /// make all tasks that depend on that vc dirty and
235    /// return a list of active tasks that should be scheduled
236    fn make_dependent_dirty(
237        &self,
238        vc: RawVc,
239        api: &dyn PersistedGraphApi,
240    ) -> Result<SmallVec<[TaskId; 4]>>;
241
242    /// Get all tasks that are active, but not persisted.
243    /// This is usually called at beginning to create and schedule
244    /// tasks that are missing in the persisted graph
245    fn get_active_external_tasks(
246        &self,
247        api: &dyn PersistedGraphApi,
248    ) -> Result<SmallVec<[TaskId; 4]>>;
249
250    /// Get all tasks that are dirty and active.
251    /// This is usually called at the beginning to schedule these tasks.
252    fn get_dirty_active_tasks(&self, api: &dyn PersistedGraphApi) -> Result<SmallVec<[TaskId; 4]>>;
253
254    /// Get tasks that have active update pending that need to be continued
255    /// returns (tasks_to_activate, tasks_to_deactivate)
256    fn get_pending_active_update(&self, api: &dyn PersistedGraphApi) -> Result<(TaskIds, TaskIds)>;
257
258    /// Stop operations
259    #[allow(unused_variables)]
260    fn stop(&self, api: &dyn PersistedGraphApi) -> Result<()> {
261        Ok(())
262    }
263}
264
265pub trait PersistedGraphApi {
266    fn get_or_create_task_type(&self, ty: CachedTaskType) -> TaskId;
267
268    fn lookup_task_type(&self, id: TaskId) -> &CachedTaskType;
269}
270
271/*
272
273read:
274
275  data: (TaskId) => (TaskData)
276  cache: (CachedTaskType) => (TaskId)
277  type: (TaskId) => (CachedTaskType)
278
279read_dependents:
280
281  dependents: (RawVc) => [TaskId]
282
283store:
284
285  external_active_parents: (TaskId) -> (usize)
286  internal_active_parents: (TaskId) -> (usize)
287  inactive_tasks: [TaskId]
288
289B+C?
290
291
292
293
294*/
295
296impl PersistedGraph for () {
297    fn read(
298        &self,
299        _task: TaskId,
300        _api: &dyn PersistedGraphApi,
301    ) -> Result<Option<(TaskData, ReadTaskState)>> {
302        Ok(None)
303    }
304
305    fn lookup(
306        &self,
307        _partial_task_type: &CachedTaskType,
308        _api: &dyn PersistedGraphApi,
309    ) -> Result<bool> {
310        Ok(false)
311    }
312
313    fn lookup_one(
314        &self,
315        _task_type: &CachedTaskType,
316        _api: &dyn PersistedGraphApi,
317    ) -> Result<Option<TaskId>> {
318        Ok(None)
319    }
320
321    fn is_persisted(&self, _task: TaskId, _api: &dyn PersistedGraphApi) -> Result<bool> {
322        Ok(false)
323    }
324
325    fn persist(
326        &self,
327        _task: TaskId,
328        _data: TaskData,
329        _state: PersistTaskState,
330        _api: &dyn PersistedGraphApi,
331    ) -> Result<Option<PersistResult>> {
332        Ok(None)
333    }
334
335    fn activate_when_needed(
336        &self,
337        _task: TaskId,
338        _api: &dyn PersistedGraphApi,
339    ) -> Result<Option<ActivateResult>> {
340        Ok(None)
341    }
342
343    fn deactivate_when_needed(
344        &self,
345        _task: TaskId,
346        _api: &dyn PersistedGraphApi,
347    ) -> Result<Option<DeactivateResult>> {
348        Ok(None)
349    }
350
351    fn set_externally_active(&self, _task: TaskId, _api: &dyn PersistedGraphApi) -> Result<bool> {
352        Ok(false)
353    }
354
355    fn unset_externally_active(&self, _task: TaskId, _api: &dyn PersistedGraphApi) -> Result<bool> {
356        Ok(false)
357    }
358
359    fn remove_outdated_externally_active(
360        &self,
361        _api: &dyn PersistedGraphApi,
362    ) -> Result<SmallVec<[TaskId; 4]>> {
363        Ok(Default::default())
364    }
365
366    fn make_dirty(&self, _task: TaskId, _api: &dyn PersistedGraphApi) -> Result<bool> {
367        Ok(false)
368    }
369
370    fn make_clean(&self, _task: TaskId, _api: &dyn PersistedGraphApi) -> Result<()> {
371        Ok(())
372    }
373
374    fn make_dependent_dirty(
375        &self,
376        _vc: RawVc,
377        _api: &dyn PersistedGraphApi,
378    ) -> Result<SmallVec<[TaskId; 4]>> {
379        Ok(Default::default())
380    }
381
382    fn get_active_external_tasks(
383        &self,
384        _api: &dyn PersistedGraphApi,
385    ) -> Result<SmallVec<[TaskId; 4]>> {
386        Ok(Default::default())
387    }
388
389    fn get_dirty_active_tasks(
390        &self,
391        _api: &dyn PersistedGraphApi,
392    ) -> Result<SmallVec<[TaskId; 4]>> {
393        Ok(Default::default())
394    }
395
396    fn get_pending_active_update(
397        &self,
398        _api: &dyn PersistedGraphApi,
399    ) -> Result<(SmallVec<[TaskId; 4]>, SmallVec<[TaskId; 4]>)> {
400        Ok((Default::default(), Default::default()))
401    }
402}
turbo_tasks/persisted_graph.rs

turbo_tasks/
persisted_graph.rs
