dep-graph-new-design-backup.rs

enum DepNodeKind {
    Hir,
    Signature,
    ...
}

// A globally unique ID for a node in a DepGraph.
struct DepNode {
    kind: DepNodeKind,
    fingerprint: Fingerprint,
}

impl CurrentDepGraph {
    fn set_result_fingerprint(&mut self, DepNodeIndex, Fingerprint);
    fn contains(&mut self, DepNode) -> bool;
    fn read(&mut self, DepNodeIndex);
    fn push_as_current_task(&mut self, DepNode);
    fn pop_current_task(&mut self, DepNode) -> DepNodeIndex;
    fn push_anonymous_task(&mut self);
    fn pop_current_task(&mut self) -> DepNodeIndex;
}

impl PrevDepGraph {
    fn get_result_fingerprint(DepNode) -> Fingerprint;
    fn dependencies(DepNode) -> impl Iterator<Item=DepNode>;
}

// A unique ID for a DepNode in the *current* DepGraph. Allows for fast lookup.
struct DepNodeIndex(u32);

// An index into tcx.dep_node_cache
struct DepNodeCacheIndex(u32);

enum DepNodeColor {
    Red,
    Green(DepNodeIndex),
    Grey,
}

struct TyCtxt {

    queries,

    dep_graph: CurrentDepGraph,
    prev_dep_graph: PrevDepGraph,

    // Can be used by queries to cache DepNodes
    dep_node_cache: IndexedVec<DepNodeCacheIndex, DepNodeIndex>,

    // This is a mapping of DepNode to Color, where DepNode might be something
    // in the old or the new graph. Hence we have to use the globally valid
    // DepNode as key instead of a DepNodeIndex, which only exists for already
    // allocated things in the new graph.
    dep_graph_colors: HashMap<DepNode, DepNodeColor>,
}

trait Query {
    type Key;
    type Result;

    // Reads either from tcx.dep_node_cache or constructs the DepNode from the
    // Key if that is cheaper.
    fn get_cached_dep_node(tcx, k: &Self::Key, dep_node_cache_index: DepNodeCacheIndex) -> DepNodeIndex;
    // This can be a no-op, if it's simple to reconstruct a DepNode from the Query::Key.
    fn cache_dep_node(tcx, dep_node_index: DepNodeIndex) -> DepNodeCacheIndex;

    fn load_from_disk(&self, tcx, dep_node: DepNode) -> Self::Result;
    fn store_to_disk(&self, tcx, dep_node: DepNode, Self::Result);

    // Look something up in the in-memory cache.
    fn get_cached_result(&self, key: &Self::Key) -> Option<(Self::Result, DepNodeCacheIndex)>;

    // Caches the given result in-memory.
    fn cache_result(&mut self, key: Self::Key, dep_node_cache_index: DepNodeCacheIndex, result: Self::Result);

    // The "provider".
    fn compute_result(tcx, key: Self::Key) -> Self::Result;

    fn is_anon_dep_node_query() -> bool;
}

enum CachingPolicy {
    InMemoryOnly,
    FingerprintOnDisk,
    ResultOnDisk,
}

struct ForceResult<T> {
    result: T,
    color: DepNodeColor,
    dep_node_index: DepNodeIndex,
}

fn query<Q: Query>(
    query: &mut Q,
    tcx,
    query_key: Q::Key)
    -> Q::Result
  where Q: Query
{
    // In non-incremental, things are easy
    if !tcx.incremental {
        // FX-HASHTABLE LOOKUP
        return tcx.queries
                  .foo_cache_non_incr
                  .entry(query_key)
                  .or_insert_with(|| Q::compute_result(tcx, query_key));
    }

    // We have something cached, great!
    // FX-HASHTABLE LOOKUP
    if let Some(result, dep_node_cache_index) = query.get_cached_result(&query_key) {
        // FX-HASHTABLE LOOKUP or FREE
        let dep_node_index = Q::get_cached_dep_node(tcx, &query_key, dep_node_cache_index);
        // CACHE-FRIENDLY FX-HASHTABLE INSERT + VEC PUSH
        tcx.new_dep_graph.read(dep_node_index);
        return result.clone();
    }

    if Q::is_anon_dep_node_query() {
        tcx.dep_graph.push_anon_task();
        let result = Q::compute_result(tcx, &query_key);
        let dep_node_index = tcx.dep_graph.pop_anon_task();
        let dep_node_cache_index = Q::cache_dep_node(dep_node_index);
        query.cache_result(query_key, dep_node_cache_index, result.clone());
        tcx.new_dep_graph.read(dep_node_index);
        result
    } else {
        // Does not cache the node yet!
        // POSSIBLY EXPENSIVE OPERATION
        let dep_node = Q::create_dep_node(tcx, &query_key);

        // Don't have it in memory, but we might have it on disk and already
        // verified that it is still up-to-date
        // FX-HASHTABLE LOOKUP
        if let Green(dep_node_index) = tcx.dep_graph_colors.get(dep_node) {
            // CACHE-FRIENDLY FX-HASHTABLE INSERT + VEC PUSH
            tcx.new_dep_graph.read(dep_node_index);
            return load_from_disk_and_cache_in_memory(query, tcx, query_key, dep_node_index);
        }

        // We don't know yet if there is a valid result cached on disk.
        // We do this by trying to mark the corresponding dependency node as green,
        // which will only succeed if all its immediate dependencies are green and
        // might involve actually evaluating and caching transitive dependencies.
        if let Green(dep_node_index) = try_mark_green(tcx, dep_node) {
            // CACHE-FRIENDLY FX-HASHTABLE INSERT + VEC PUSH
            tcx.new_dep_graph.read(dep_node_index);
            load_from_disk_and_cache_in_memory(query, tcx, query_key, dep_node_index)
        } else {
            // One of the dependencies turned up red, we have to re-compute.
            let ForceResult {
                result,
                color: _,
                dep_node_index
            } = force(query, tcx, query_key, dep_node);

            // CACHE-FRIENDLY FX-HASHTABLE INSERT + VEC PUSH
            tcx.new_dep_graph.read(dep_node_index);

            result
        }
    }
}

fn load_from_disk_and_cache_in_memory<Q: Query>(
    query: &mut Q,
    tcx,
    query_key: Q::Key,
    dep_node_index: DepNodeIndex,
    )
    -> Q::Result
  where Q: Query
{
    let dep_node = tcx.dep_graph.index_to_dep_node(dep_node_index);
    let result = match query.caching_policy() {
        InMemoryOnly |
        FingerprintOnly => {
            assert!(tcx.dep_graph_colors.get(dep_node) == Green)
            // If it is already green, the correct edges should already exist
            tcx.new_dep_graph.ignoring(|| Q::compute_result(tcx, query_key))
        }
        OnDisk => {
            Q::load_from_disk(dep_node)
        }
    };
    let dep_node_cache_index = Q::cache_dep_node(tcx, dep_node_index);

    // FX-HASHTABLE INSERT + maybe cache DepNode (VEC PUSH)
    query.cache_result(query_key, dep_node_cache_index, result.clone());
    result
}

fn try_mark_green(tcx, dep_node: DepNode) -> DepNodeColor {
    // We are trying to mark this node as green, so it must still be grey
    assert!(tcx.dep_graph_colors.get(dep_node) == Grey);
    //
    assert!(!tcx.dep_graph.contains(dep_node));

    let mut dependencies: Vec<DepNodeIndex> = Vec::new();

                        // FX-HASHTABLE LOOKUPS (dep-list of dep_node)
                        // N array lookups (dep_node_index to dep_node)
    for dep_dep_node in tcx.prev_dep_graph.dependencies(dep_node) {
        // FX-HASHTABLE LOOKUP
        match tcx.dep_graph_colors.get(dep_dep_node) {
            Green(dep_dep_node_index) => {
                // This node checks out, take a look at the next
                dependencies.push(dep_dep_node_index);
            }
            Red => {
                // This node has changed compared to the last compilation
                // session, so we did not succeed in marking this node green
                return Red
            }
            Grey => {
                // We don't know the state of this dependency
                if let Green(dep_dep_node_index) = try_mark_green(tcx, dep_dep_node) {
                    dependencies.push(dep_dep_node_index);
                } else {
                    // We could not mark it as green without re-computing it,
                    // so we "force" it.
                    // NOTE: This involves some kind of dynamic dispatch, since
                    // the dependency/query could be of any type.
                    match force_from_dep_node(tcx, dep_dep_node) {
                        Ok((color, dep_dep_node_index)) => {
                            match color {
                                Green(_) => {
                                    dependencies.push(dep_dep_node_index);
                                }
                                Red => {
                                    assert!(tcx.dep_graph_colors.get(dep_dep_node) == Red);
                                    // We were able to re-compute the query result, but it
                                    // has changed from the last run.
                                    return Red
                                }
                            }
                        }
                        Err(_) => {
                            // We could not recompute the value. This might have one
                            // of two reasons:
                            //
                            // 1. The thing we are trying to recompute does not
                            //    exist anymore in the current session
                            // 2. We cannot reconstruct a query-key from the DepNode
                            assert!(tcx.dep_graph_colors.get(dep_dep_node) == Red);
                            return Red
                        }
                    }
                }
            }
        }
    }

    // Mirror dep-edges from old graph to new one
    // Note: We could provide a specialized CurrentDepGraph method, that skips
    //       the hash-table check, because we already know that edges are unique.
    tcx.dep_graph.push_as_current_task(dep_node);
    for dep_dep_node_index in dependencies {
        // CACHE-FRIENDLY FX-HASHTABLE INSERT + VEC PUSH
        tcx.dep_graph.read(dep_dep_node_index);
    }
    // FX-HASHTABLE insert (for dep_node)
    let dep_node_index = tcx.dep_graph.pop_current_task(dep_node);

    // FX-HASHTABLE INSERT
    tcx.dep_graph_colors.set(dep_node, Green(dep_node_index));

    Green(dep_node_index)
}

fn force<Q>(query: &mut Q, tcx, query_key: Q::Key, dep_node: DepNode) -> ForceResult<Q::Result> {
    assert!(!tcx.dep_graph.contains(dep_node));
    assert!(!tcx.dep_graph_colors.contains(dep_node));

    // DO CYCLE CHECK HERE

    tcx.dep_graph.push_as_current_task(dep_node);
    let result = Q::compute_result(tcx, query_key);
    let dep_node_index = tcx.dep_graph.pop_current_task();

    let dep_node_cache_index = Q::cache_dep_node(dep_node_index);
    // Cache the result for future queries.
    query.cache_result(query_key, dep_node_cache_index, result.clone());

    if Q::caching_policy() == InMemoryOnly {
        tcx.dep_graph_colors.set(dep_node, Red);
        return ForceResult {
            result,
            color: red,
            dep_node_index
        }
    }

    // Now we know the new value. Let's see if it has actually changed.
    let old_result_fingerprint = tcx.prev_dep_graph.get_result_fingerprint(dep_node);
    let new_result_fingerprint = result.fingerprint(tcx);

    let color = if old_result_fingerprint == new_result_fingerprint {
        // No actual change, which means:
        // - We can leave the on-disk cache untouched.
        // - We can mark this node as green.
        let color = Green(dep_node_index);
        tcx.dep_graph_colors.set(dep_node, color);
        color
    } else {
        // The value has changed, mark as red an store the new value in
        // on-disk cache
        tcx.dep_graph_colors.set(dep_node, Red);

        match Q::caching_policy() {
            FingerprintOnDisk => {}
            OnDisk => {
                assert!(!Q::is_input());
                // This will hopefully happen in a background thread:
                query.store_to_disk(tcx, dep_node, result.clone());
            }
        }

        Red
    };

    tcx.dep_graph.set_result_fingerprint(dep_node_index, new_result_fingerprint);

    ForceResult {
        result,
        color,
        dep_node_index
    }
}

// Do dynamic dispatch
fn force_from_dep_node(tcx, dep_node: DepNode) -> Result<(DepNodeColor, DepNodeIndex), ()> {

    // Try to do a reverse-lookup from DepNode fingerprint to DefId.
    let opt_def_id = dep_node.extract_def_id(tcx);

    let def_id = if let Some(def_id) = opt_def_id {
        def_id
    } else {
        // Extracting a DefId from the DepNode can have failed for two reasons:
        //
        // 1. The fingerprint in the DepNode does not correspond to a single DefPath fingerprint.
        // 2. The thing the DefId would have identified does not exist anymore
        //    in the current compilation session.
        //
        // Both cases prevent us from re-computing the query.
        tcx.dep_graph_colors.set(dep_dep_node, Red);
        return Err(())
    }

    match dep_node.kind {
        Hir => {
            let result = tcx.queries.hir.force(tcx, def_id, dep_node);
            return Ok((result.color, result.dep_node_index));
        }
        ItemSig => {
            let result = tcx.queries.item_sig.force(tcx, def_id, dep_node);
            return Ok((result.color, result.dep_node_index));
        }

        ...

        _ => bug!("extract_def_id() above should already have returned None.")
    }
}

//   - Cycle errors
//     - allocating graph nodes and then failing?
//     - special "probe_cycle"?

Oops; I forgot to reply to the earlier question. You asked about your algorithm, with this description:

Yes, this matches my understanding. To me this procedure also sounds totally analogous to "cleaning" in Adapton. Though, seems different in two subtle ways:

1. Adapton cleans and re-evaluates in one inter-leaved (possibly-nested) algorithm. Specifically, see this call to loc_produce for the specific step where cleaning switches to nested re-evaluation.
2. With names, nominal allocations in Adapton introduce dirtying to be inter-leaved with cleaning and re-evaluation. In some cases, these names play the role of "nominal firewalls", as mentioned above in our earlier comments.