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"?

I found this code really helpful for understanding the red-green algorithm in some detail. I have several questions, but my main ones are about the try_mark_green subroutine. I think that I understand it, and that it looks sound. My comments below try to relate it to Adapton in some detail.

In Adapton, our analogue of this algorithm is called "cleaning". In particular, the routine clean_comp is a close analogue of try_mark_green above:
https://github.com/Adapton/adapton.rust/blob/20af5e753d75f20f613d4f1056f438e7357dbea4/src/engine.rs#L967

During cleaning, a key step for soundness is comparing the old value produced by a dependency with the current value it produces. These old values are stored on each dependency edge. As noted in the gist above, and as in Adapton, the graph has heterogeneous types, so the Adapton cleaning algorithm only gets a bool that reflects the result of this comparison. Specifically, we use this DCGDep trait, and the DCGRes struct, which holds a boolean:
https://github.com/Adapton/adapton.rust/blob/20af5e753d75f20f613d4f1056f438e7357dbea4/src/engine.rs#L546

The bool in a DCGRes reflects whether the resulting value of a dependency has changed or not during the cleaning algorithm. A result of true means that the new value produced by the dependency has changed, and false means that it has not changed.

I think this is the analogue of the colors Red (meaning changed) and Green (meaning not changed). Is that right?

In particular, around line 223 (https://gist.github.com/michaelwoerister/e278b4ad3eb88d61e19b7ab066c44b25#file-dep-graph-new-design-backup-rs-L223), the algorithm fails to mark a dependency Green without recomputing it. In particular, some node consumes a value produced by another node, its dependency, and the algorithm is attempting to mark this dependency as Green in order to mark the dependent node as Green. (Let me know if I'm misstating something here).

Critically, when a result has changed, the cleaning algorithm reevaluates the dependent node:
https://github.com/Adapton/adapton.rust/blob/20af5e753d75f20f613d4f1056f438e7357dbea4/src/engine.rs#L981

That also seems to be happening above, too, in this line:
https://gist.github.com/michaelwoerister/e278b4ad3eb88d61e19b7ab066c44b25#file-dep-graph-new-design-backup-rs-L237

Some questions and comments

1. I don't see an analogue of these boolean tests in the code above. But I think that they are happening somehow in the call to force_from_dep_node, in this line: https://gist.github.com/michaelwoerister/e278b4ad3eb88d61e19b7ab066c44b25#file-dep-graph-new-design-backup-rs-L227. Can you confirm that this is the meaning of the color returned there?

2. Have you considered associating the prior results with the edges in the dependency graph, rather than the nodes? In a demand-driven setting, there are some advantages to arranging the cache this way, since it permits different dependent nodes to have different "views" of the nodes on which they depend. If these dependent nodes are not in demand, they need not be "cleaned", and their "old observations" remain in the cache. Later, if the dependencies "switch back" to a prior state, these observations may be consistent again, allowing you to mark them Green without recomputing them. I can imagine this being useful in a system like RLS, though I'd have to think more about a nice, concrete example.

3. If I understand correctly, the edges that I see in the gist above correspond to the Adapton analogue of "producer"/"observation"/"force" edges: They represent the target node producing a value that is consumed by the source node (for an edge from source --> target). Do you also have edges that correspond to "allocation" edges? These edges are particularly useful for making the dirtying algorithm in Adapton more precise, less aggressive and more incremental. In particular, by using these edges, the dirtying algorithm occurs during the cleaning and recomputation of the graph. I think there'd be a benefit in this setting too, though I'd have to think more about a concrete example.

Regarding question/comment #3 above, I've added a simple example to the Adapton documentation to help clarify what I mean here. I'm borrowing @nikomatsakis's term "firewall" to explain the benefit of this pattern.

Thanks a lot for taking a look at this, @matthewhammer! That's very helpful.

I think this is the analogue of the colors Red (meaning changed) and Green (meaning not changed). Is that right?

Yes, that's correct. The analogy between try_mark_green and clean_comp sounds right too.

In particular, around line 223 (https://gist.github.com/michaelwoerister/e278b4ad3eb88d61e19b7ab066c44b25#file-dep-graph-new-design-backup-rs-L223), the algorithm fails to mark a dependency Green without recomputing it. In particular, some node consumes a value produced by another node, its dependency, and the algorithm is attempting to mark this dependency as Green in order to mark the dependent node as Green. (Let me know if I'm misstating something here).

I'm not sure. The intended behavior of the code is:

• Walk the input nodes of a given node and see if it can be turned green:
  • Either it is already green because of some previous query (line 209),
  • or we have to re-evaluate the corresponding query (line 227) and compare results (line 301).
• If all of the input nodes turn out to be green, we can mark the current node as green too, without ever re-evaluating it (lines 257-271).

Does that fit with how you understood it?

1. I don't see an analogue of these boolean tests in the code above. But I think that they are happening somehow in the call to force_from_dep_node, in this line: https://gist.github.com/michaelwoerister/e278b4ad3eb88d61e19b7ab066c44b25#file-dep-graph-new-design-backup-rs-L227. Can you confirm that this is the meaning of the color returned there?

Yes that's correct. We could also "just" call force_from_dep_node() and then take a look at what color it registered for the node, but since we already have that color, we just return it and spare ourselves the hash table lookup.

2. Have you considered associating the prior results with the edges in the dependency graph, rather than the nodes? In a demand-driven setting, there are some advantages to arranging the cache this way, since it permits different dependent nodes to have different "views" of the nodes on which they depend. If these dependent nodes are not in demand, they need not be "cleaned", and their "old observations" remain in the cache. Later, if the dependencies "switch back" to a prior state, these observations may be consistent again, allowing you to mark them Green without recomputing them. I can imagine this being useful in a system like RLS, though I'd have to think more about a nice, concrete example.

I have not considered that, no. Some thoughts:

• First, to clarify, you store that boolean flag per edge, but you don't somehow store the view corresponding to that edge, right? In other words, you don't store the projection value -> actual part of the value used by a reader -- that just "falls out" during re-evaluation. When not re-evaluating a reader, the edge just stays untouched?
• At the moment, the system is geared towards completely recomputing everything. That is, we just keep things in the cache that have been used during the last complete re-compilation. I personally have not thought hard about the implications for cache management when only part of the graph is re-evaluated. We would probably need to run try_mark_green for all nodes for which we have a cached result in order not to lose most of the cache.
  I imagine that we would do another re-architecting of the caching/dep-tracking core, which should be a lot easier the next time around since everything should be nicely encapsulated by then. The approach we are taking now (a read-only view of the previous dep-graph where we copy things over into the new one, if possible) works well for bulk-recompilation but it might not be ideal for the RLS scenario.

3. If I understand correctly, the edges that I see in the gist above correspond to the Adapton analogue of "producer"/"observation"/"force" edges: They represent the target node producing a value that is consumed by the source node (for an edge from source --> target). Do you also have edges that correspond to "allocation" edges? These edges are particularly useful for making the dirtying algorithm in Adapton more precise, less aggressive and more incremental. In particular, by using these edges, the dirtying algorithm occurs during the cleaning and recomputation of the graph. I think there'd be a benefit in this setting too, though I'd have to think more about a concrete example.

@nikomatsakis mentioned that this might be related to the difference between regular and "anonymous" queries, which sounds right to me. Each regular query is a "nominal firewall" and should have the same effects on re-use as an alloc-edge/cell has.

First, to clarify, you store that boolean flag per edge, but you don't somehow store the view corresponding to that edge, right? In other words, you don't store the projection value -> actual part of the value used by a reader -- that just "falls out" during re-evaluation. When not re-evaluating a reader, the edge just stays untouched?

Yes, we do store this view on each edge: Each edge consists of a source node, a target node, an effect (either force or alloc), a dirty bit and a value/content. See Succ for details.

For get/force edges (that's one kind, with many interchangeable words), the value/content corresponds to the last seen value (the "view", as you call it above). For put/alloc edges, the value corresponds to the allocated value, or thunk closure (a static fn and argument values for its formal parameters).

@nikomatsakis mentioned that this might be related to the difference between regular and "anonymous" queries, which sounds right to me. Each regular query is a "nominal firewall" and should have the same effects on re-use as an alloc-edge/cell has.

Cool! Yes, @nikomatsakis and I discussed that connection too: In Adapton we call some nodes "structural" (when they are identified by their value/closure, and their dependencies, usually by a hash of those things), and other nodes are "nominal" --- when they have a name that is distinct from their content. Only nominal allocations induce these "firewalls", in Adapton. It sounds like a very direct connection of related ideas. :)

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.