docs/buildengine.rst

==============
 Build Engine
==============

This document currently only provides additional information on some aspects of
the build engine design. See the source code documentation comments for
information on the actual ``BuildEngine`` APIs.

Order-only Dependencies
=======================

The build engine supports "order-only" dependencies (in the style of Ninja)
through a "must-follow" input request or barrier. Internally, this is treated
much the same as a normal input request, in that the task is responsible for
calling ``taskMustFollow()`` on the engine during its preparation phase.

However, these input requests do not need to be scanned or persisted. This is
because the dependency is only relevant when the dependee is executing, and in
those cases the task will be responsible for dynamically supplying the
barrier. Thus, the implementation can piggy-back on the existing mechanisms for
ensuring input requests are available prior to executing the task, and simply
discard the order-only input request once satisfied.

Parallelism
===========

There are two obvious approaches to introducing parallelism into the core build
engine.

1. The first approach (which is taken currently) changes the task definition so
   that it gets a callback ``inputsAvailable()``, and adds a new task API on the
   ``BuildEngine`` called ``taskIsComplete()`` which is allowed to be called
   concurrently.

   When the task gets all of its inputs, then it is responsible for dispatching
   its work in a parallel fashion and informing the engine when that is
   complete. The engine tracks the task as pending completion until it received
   that callback.

   This keeps the engine simple, as it doesn't really deal with concurrency at
   all except for in specific cases that should be easy to reason about. It also
   makes the engine separable from the specific concurrency model, which may
   make it easier to plug in schedulers and the like (for example, it is
   somewhat clear how a posix_spawn + ppoll/pselect concurrency model works in
   this system).

2. The alternate approach is to change the engine so that it manages all of the
   concurrency, changing the Task contract such that it stays synchronous but
   can be called on any thread.

   This means that all clients of the engine get concurrency automatically, but
   also more intimately ties the engine implementation to the concurrency model.


Dependency Scanning
===================

The engine is designed to scan dependencies concurrently with other build
work. This introduces a fair amount of complexity into the engine, but is
important because we want to ensure that the engine is able to dispatch any
identified tasks as soon they are found.

Recursive Dependency Scanning
-----------------------------

The current design of the engine handles dependency scanning in the same manner
as other tasks, it associates a scan request with a rule and then enqueues the
actual scanning work so that it can proceed in parallel with other work.

Currently, the dependency scanning processes each input for an individual rule
in sequence, and it suspends itself when it is waiting on an individual input to
complete. This is made more complex by the need to sometimes execute a task
before being able to determine that its downstream clients need to rerun (when
the result has not changed). To manage that, the engine tracks for each task
which other tasks are waiting for it to complete as well as which tasks are
waiting for it to be scanned.

The current implementation is not yet capable of scanning multiple inputs for a
particular task concurrently, because when doing it is necessary to track
additional state about whether or not the input was *actually* requested by a
task or just a dependency present on a previous iteration. For example, consider
the case where a task depended upon **A** and **B** in the last build. If a
concurrent scan indicates the task should rerun because **B** has changed, it is
not necessarily true that **B** itself should rerun (because the task may no
longer request **B** as an input). The current implementation side-steps this
problem by scanning dependencies one at a time.