`type_of(bar)` and encounter `Hir(bar)` which *has* changed. Consequently
the result of `type_of(bar)` might yield a different result than what we
have in the cache and, transitively, the result of `type_check_item(foo)`
might have changed too. We thus re-run `type_check_item(foo)`, which in
turn will re-run `type_of(bar)`, which will yield an up-to-date result
because it reads the up-to-date version of `Hir(bar)`. Also, we re-run
`type_check_item(bar)` because result of `type_of(bar)` might have changed.


## The Problem With The Basic Algorithm: False Positives

If you read the previous paragraph carefully you'll notice that it says that
`type_of(bar)` *might* have changed because one of its inputs has changed.
There's also the possibility that it might still yield exactly the same
result *even though* its input has changed. Consider an example with a
simple query that just computes the sign of an integer:

```ignore
  IntValue(x) <---- sign_of(x) <--- some_other_query(x)
```

Let's say that `IntValue(x)` starts out as `1000` and then is set to `2000`.
Even though `IntValue(x)` is different in the two cases, `sign_of(x)` yields
the result `+` in both cases.

If we follow the basic algorithm, however, `some_other_query(x)` would have to
(unnecessarily) be re-evaluated because it transitively depends on a changed
input. Change detection yields a "false positive" in this case because it has
to conservatively assume that `some_other_query(x)` might be affected by that
changed input.

Unfortunately it turns out that the actual queries in the compiler are full
of examples like this and small changes to the input often potentially affect
very large parts of the output binaries. As a consequence, we had to make the
change detection system smarter and more accurate.

## Improving Accuracy: The red-green Algorithm

The "false positives" problem can be solved by interleaving change detection
and query re-evaluation. Instead of walking the graph all the way to the
inputs when trying to find out if some cached result is still valid, we can
check if a result has *actually* changed after we were forced to re-evaluate
it.

We call this algorithm the red-green algorithm because nodes
in the dependency graph are assigned the color green if we were able to prove
that its cached result is still valid and the color red if the result has
turned out to be different after re-evaluating it.

The meat of red-green change tracking is implemented in the try-mark-green
algorithm, that, you've guessed it, tries to mark a given node as green:

```rust,ignore
fn try_mark_green(tcx, current_node) -> bool {

    // Fetch the inputs to `current_node`, i.e. get the nodes that the direct
    // edges from `node` lead to.
    let dependencies = tcx.dep_graph.get_dependencies_of(current_node);

    // Now check all the inputs for changes
    for dependency in dependencies {

        match tcx.dep_graph.get_node_color(dependency) {
            Green => {
                // This input has already been checked before and it has not
                // changed; so we can go on to check the next one
            }
            Red => {
                // We found an input that has changed. We cannot mark
                // `current_node` as green without re-running the
                // corresponding query.
                return false
            }
            Unknown => {
                // This is the first time we look at this node. Let's try
                // to mark it green by calling try_mark_green() recursively.
                if try_mark_green(tcx, dependency) {
                    // We successfully marked the input as green, on to the
                    // next.
                } else {
                    // We could *not* mark the input as green. This means we
                    // don't know if its value has changed. In order to find
                    // out, we re-run the corresponding query now!
                    tcx.run_query_for(dependency);