sbt/sbt — pull request #1002 by gkossakowski (2013-11-24 23:46:02+00:00)
Title: Extract dependencies by tree walking

_This is follow up on #996. I consider this PR to be ready for review._

At very high level this PR introduces a new source dependency tracking mechanism based on tree walking and collecting symbols. Here are two commit messages which describe the best this PR in detail:

---

#### Introduce `memberRef` and `inheritance` relations.

Those relations are very similar to existing `direct` and `publicInherited` relations in some subtle ways. Those differences will be highlighted in the description below.

Dependencies between source files are tracked in two distinct categories:

* dependencies introduced by inheriting from a class/trait defined in other source file
* dependencies introduced by referring (selecting) a member defined in other source file (that covers all other kinds of dependencies)

Due to invalidation algorithm implementation details sbt would need to track inheritance dependencies of public classes only. Thus, we had relation called `publicInherited`. The name hashing algorithm which improves invalidation logic will need more precise information about dependencies introduced by inheritance including dependencies of non-public classes. That's one difference between `inheritance` and `publicInherited` relations.

One surprising (to me) thing about `publicInherited` is that it includes all base classes of a given class and not just parents. In that sense `publicInherited` is transitive. This is a bit irregular because everything else in Relations doesn't include transitive dependencies.

Since we are introducing new relations we have an excellent chance to make things more regular. Therefore `inheritance` relation is non-transitive and includes only extracted parent classes.

The access to `direct`, `publicInherited`, `memberRef` and `inheritance` relations is dependent upon the value of `memberRefAndInheritanceDeps` flag. Check documentation of that flag for details.

---

#### Extract source code dependencies by tree walking.

Previously incremental compiler was extracting source code dependencies by inspecting `CompilationUnit.depends` set. This set is constructed by Scala compiler and it contains all symbols that given compilation unit refers or even saw (in case of implicit search). There are a few problems with this approach:

* The contract for `CompilationUnit.depend` is not clearly defined in Scala compiler and there are no tests around it. Read: it's not an official, maintained API.
* Improvements to incremental compiler require more context information about given dependency. For example, we want to distinguish between dependency on a class when you just select members from it or inherit from it. The other example is that we might want to know dependencies of a given class instead of the whole compilation unit to make the invalidation logic more precise.

That led to the idea of pushing dependency extracting logic to incremental compiler side so it can evolve indepedently from Scala compiler releases and can be refined as needed. We extract dependencies of a compilation unit by walking a type-checked tree and gathering symbols attached to them.

Specifically, the tree walk is implemented as a separate phase that runs after pickler and extracts symbols from following tree nodes:

* `Import` so we can track dependencies on unused imports
* `Select` which is used for selecting all terms
* `Ident` used for referring to local terms, package-local terms and top-level packages
* `TypeTree` which is used for referring to all types

Note that we do not extract just a single symbol assigned to `TypeTree` node because it might represent a complex type that mentions several symbols. We collect all those symbols by traversing the type with CollectTypeTraverser. The implementation of the traverser is inspired by `CollectTypeCollector` from Scala 2.10. The `source-dependencies/typeref-only` test covers a scenario where the dependency is introduced through a TypeRef only.