Non-workspaced incremental builds

[Charles Bailey <cbailey32 bloomberg net>]

This is a summary of a proposed feature that would make use of "build
tree" caching (that is caching of the build-root after a completed
build) to enable faster rebuilding of dependent projects in BuildStream.
Much of the input to this feature came from a group discussion last
week. Please correct anything that I may have missed or misinterpreted
from that if you were involved in the discussion.

Use case:

- In a project which links multiple static libraries into an executable,
  when a code change is made to a dependent library, the executable only
  needs to be relinked, its object files do not always need to be
  recompiled.

Tentative design:

- For any build element, if we cache the build tree (the contents of
  /buildstream/build after a build) of previous builds of this build
  element, then we could optionally stage this tree instead of staging
  "fresh" sources to enable an incremental build, which potentially is
  just a relink.

- We would probably want to treat the built artifact as less trusted
  than an equivalent clean build of the same input. We might do this by
  including a data item indicating an incremental build in the cache key
  calculation. Incremental builds of other build elements could then
  fall back to using incremental builds of their dependencies if a clean
  build is not available.

Build tree timestamps:

  Currently, when sources are staged they are given a known mtime, if
  the same happens for staging a cached build tree then all files will
  have the same timestamp, rather than object files having a more recent
  time than the corresponding sources. This is not an issue for most
  build tools that rely on timestamps as an output having an identical
  timestamp to its sources is usually considered "up to date".

Unsolved issues:

- Locating a cached build-tree

  When running an incremental build, a cached build tree from any of the
  following might provide a benefit over a clean build:

  - a previous build of the same version of the source but with updated
    dependency versions. This could be found by looking up a "weak"
    cache key

  - a build of a different version of the source with the same
    dependencies. Using this would involve staging the cached build tree
    and updating the source to the required version

  - a build of a different version of the source with updated dependency
    versions

  These latter two are not easily found by a cache key lookup of the
  build element to be built.

  In theory, there may be many possible cached build trees that could be
  used as the base for an incremental build. The best candidate would
  depend on how different the source and dependency files of the
  candidate are from the build element to be built. You could view this
  as a metric space.

- Dependency timestamps

  This issue also affects workspaced incremental builds. If a new
  version of a dependency is staged, all of its files will be given a
  start-of-epoch timestamp. This means that any timestamp-based build
  tool will assume that all outputs in the incremental build area are up
  to date with respect to input files (e.g. header files) in the
  dependency, even if they have actually changed since the previous
  incremental build.