bool finishedInDB;

    Build() : finishedInDB(false) { }

    std::atomic_bool finishedInDB{false};

    Sync<State> state;

    std::atomic_bool created{false}; // debugging
    std::atomic_bool finished{false}; // debugging

    std::atomic_bool destroyed;

    Sync<State> state;

    Step() : destroyed(false) { }
    ~Step() { }

    ~Step()
    {
        printMsg(lvlError, format("destroying step %1%") % drvPath);
    }

        Build::ptr referringBuild, Step::ptr referringStep,

    void destroyStep(Step::ptr step, bool proceed);
    /* Get the builds that depend on the given step. */
    std::set<Build::ptr> getDependentBuilds(Step::ptr step);

            assert(!build->finishedInDB);

        Step::ptr step = createStep(store, build->drvPath, newSteps, newRunnable);

        Step::ptr step = createStep(store, build->drvPath, build, 0, newSteps, newRunnable);

            printMsg(lvlInfo, format("marking build %1% as cached successful") % build->id);

            build->finishedInDB = true;

                assert(!build->finishedInDB);

            auto step_(step->state.lock());

            step_->builds.push_back(build);

        /* Prior to this, the build is not visible to
           getDependentBuilds().  Now it is, so the build can be
           failed if a dependency fails. (It can't succeed right away
           because its top-level is not runnable yet). */

    Build::ptr referringBuild, Step::ptr referringStep,

    /* Check if the requested step already exists. */

    /* Check if the requested step already exists. If not, create a
       new step. In any case, make the step reachable from
       referringBuild or referringStep. This is done atomically (with
       ‘steps’ locked), to ensure that this step can never become
       reachable from a new build after doBuildStep has removed it
       from ‘steps’. */
    Step::ptr step;
    bool isNew = false;

        /* See if the step already exists in ‘steps’ and is not
           stale. */

            auto step = prev->second.lock();

            step = prev->second.lock();

            if (step) return step;
            steps_->erase(drvPath); // remove stale entry

            if (!step) steps_->erase(drvPath); // remove stale entry
        }
        /* If it doesn't exist, create it. */
        if (!step) {
            step = std::make_shared<Step>();
            step->drvPath = drvPath;
            isNew = true;

        auto step_(step->state.lock());
        if (referringBuild)
            step_->builds.push_back(referringBuild);
        if (referringStep)
            step_->rdeps.push_back(referringStep);
        (*steps_)[drvPath] = step;

    auto step = std::make_shared<Step>();
    step->drvPath = drvPath;

    if (!isNew) {
        assert(step->created);
        return step;
    }
    /* Initialize the step. Note that the step may be visible in
       ‘steps’ before this point, but that doesn't matter because
       it's not runnable yet, and other threads won't make it
       runnable while step->created == false. */

    newSteps.insert(step);

    newSteps.insert(step);

    bool hasDeps = false;

        Step::ptr dep = createStep(store, i.first, newSteps, newRunnable);

        auto dep = createStep(store, i.first, 0, step, newSteps, newRunnable);

            hasDeps = true;

            auto dep_(dep->state.lock());

            dep_->rdeps.push_back(step);

    }
    {
        auto steps_(steps.lock());
        assert(steps_->find(drvPath) == steps_->end());
        (*steps_)[drvPath] = step;
    }
    if (!hasDeps) newRunnable.insert(step);
    return step;
}
void State::destroyStep(Step::ptr step, bool proceed)
{
    if (step->destroyed) return;
    step->destroyed = true;
    printMsg(lvlDebug, format("destroying build step ‘%1%’") % step->drvPath);
    nrStepsDone++;
    {
        auto steps_(steps.lock());
        steps_->erase(step->drvPath);

    std::vector<Step::wptr> rdeps;

    /* If the step has no (remaining) dependencies, make it
       runnable. */

        rdeps = step_->rdeps;
        /* Sanity checks. */
        for (auto & build_ : step_->builds) {
            auto build = build_.lock();
            if (!build) continue;
            assert(build->drvPath == step->drvPath);
            assert(build->finishedInDB);
        }

        assert(!step->created);
        step->created = true;
        if (step_->deps.empty())
            newRunnable.insert(step);

    for (auto & rdep_ : rdeps) {
        auto rdep = rdep_.lock();
        if (!rdep) continue;
        bool runnable = false;
        {
            auto rdep_(rdep->state.lock());
            assert(has(rdep_->deps, step));
            rdep_->deps.erase(step);
            if (rdep_->deps.empty()) runnable = true;
        }
        if (proceed) {
            /* If this rdep has no other dependencies, then we can now
               build it. */
            if (runnable)
                makeRunnable(rdep);
        } else
            /* If ‘step’ failed or was cancelled, then delete all
               dependent steps as well. */
            destroyStep(rdep, false);
    }

    return step;

std::set<Build::ptr> State::getDependentBuilds(Step::ptr step)

/* Get the steps and unfinished builds that depend on the given step. */
void getDependents(Step::ptr step, std::set<Build::ptr> & builds, std::set<Step::ptr> & steps)

    std::set<Step::ptr> done;
    std::set<Build::ptr> res;

        if (has(done, step)) return;
        done.insert(step);

        if (has(steps, step)) return;
        steps.insert(step);

                if (build_) res.insert(build_);

                if (build_ && !build_->finishedInDB) builds.insert(build_);

    return res;

        assert(step->created);
        assert(!step->finished);

                printMsg(lvlDebug, format("%1% runnable builds") % runnable_->size());

                //printMsg(lvlDebug, format("%1% runnable builds") % runnable_->size());

    {
        auto step_(step->state.lock());
        assert(step->created);
        assert(!step->finished);
    }

        auto dependents = getDependentBuilds(step);

        std::set<Build::ptr> dependents;
        std::set<Step::ptr> steps;
        getDependents(step, dependents, steps);

    /* Remove this step. After this, incoming builds that depend on
       drvPath will either see that the output paths exist, or will
       create a new build step for drvPath. The latter is fine - it
       won't conflict with this one, because we're removing it. In any
       case, the set of dependent builds for ‘step’ can't increase
       anymore because ‘step’ is no longer visible to createStep(). */
    auto steps_(steps.lock());
    steps_->erase(step->drvPath);

    if (result.status == RemoteResult::rrSuccess) {
        /* Register success in the database for all Build objects that
           have this step as the top-level step. Since the queue
           monitor thread may be creating new referring Builds
           concurrently, and updating the database may fail, we do
           this in a loop, marking all known builds, repeating until
           there are no unmarked builds.
        */
        while (true) {
            /* Get the builds that have this one as the top-level. */
            std::vector<Build::ptr> direct;
            {
                auto steps_(steps.lock());
                auto step_(step->state.lock());
                for (auto & b_ : step_->builds) {
                    auto b = b_.lock();
                    if (b && !b->finishedInDB) direct.push_back(b);
                }
                /* If there are no builds left to update in the DB,
                   then we're done. Delete the step from
                   ‘steps’. Since we've been holding the ‘steps’ lock,
                   no new referrers can have been added in the
                   meantime or be added afterwards. */
                if (direct.empty()) {
                    printMsg(lvlDebug, format("finishing build step ‘%1%’") % step->drvPath);
                    nrStepsDone++;
                    steps_->erase(step->drvPath);
                    break;
                }
            }
            /* Update the database. */
            {
                pqxx::work txn(*conn);
                finishBuildStep(txn, result.startTime, result.stopTime, build->id, stepNr, machine->sshName, bssSuccess);
                for (auto & b : direct)
                    markSucceededBuild(txn, b, res, build != b,
                        result.startTime, result.stopTime);

    /* Get the final set of dependent builds. */
    auto dependents = getDependentBuilds(step);

                txn.commit();
            }

    std::set<Build::ptr> direct;
    {
        auto step_(step->state.lock());
        for (auto & build : step_->builds) {
            auto build_ = build.lock();
            if (build_) direct.insert(build_);

            /* Remove the direct dependencies from ‘builds’. This will
               cause them to be destroyed. */
            for (auto & b : direct) {
                auto builds_(builds.lock());
                b->finishedInDB = true;
                builds_->erase(b->id);
            }

    }

    /* Update the database. */
    {
        pqxx::work txn(*conn);

        /* Wake up any dependent steps that have no other
           dependencies. */
        {
            auto step_(step->state.lock());
            for (auto & rdepWeak : step_->rdeps) {
                auto rdep = rdepWeak.lock();
                if (!rdep) continue;

        if (result.status == RemoteResult::rrSuccess) {

                bool runnable = false;
                {
                    auto rdep_(rdep->state.lock());
                    rdep_->deps.erase(step);
                    if (rdep_->deps.empty()) runnable = true;
                }

            finishBuildStep(txn, result.startTime, result.stopTime, build->id, stepNr, machine->sshName, bssSuccess);

                if (runnable) makeRunnable(rdep);
            }
        }

            /* Mark all builds of which this derivation is the top
               level as succeeded. */
            for (auto build2 : direct)
                markSucceededBuild(txn, build2, res, build != build2,
                  result.startTime, result.stopTime);

    } else {

        } else {
            /* Failure case. */

        /* Register failure in the database for all Build objects that
           directly or indirectly depend on this step. */

            BuildStatus buildStatus =
                result.status == RemoteResult::rrPermanentFailure ? bsFailed :
                result.status == RemoteResult::rrTimedOut ? bsTimedOut :
                bsAborted;
            BuildStepStatus buildStepStatus =
                result.status == RemoteResult::rrPermanentFailure ? bssFailed :
                result.status == RemoteResult::rrTimedOut ? bssTimedOut :
                bssAborted;

        while (true) {

            /* For regular failures, we don't care about the error
               message. */
            if (buildStatus != bsAborted) result.errorMsg = "";

            /* Get the builds and steps that depend on this step. */
            std::set<Build::ptr> indirect;
            {
                auto steps_(steps.lock());
                std::set<Step::ptr> steps;
                getDependents(step, indirect, steps);

            /* Create failed build steps for every build that depends
               on this. For cached failures, only create a step for
               builds that don't have this step as top-level
               (otherwise the user won't be able to see what caused
               the build to fail). */
            for (auto build2 : dependents) {
                if (build == build2) continue;
                if (cachedFailure && build2->drvPath == step->drvPath) continue;
                createBuildStep(txn, 0, build2, step, machine->sshName,
                    buildStepStatus, result.errorMsg, build->id);

                /* If there are no builds left, delete all referring
                   steps from ‘steps’. As for the success case, we can
                   be certain no new referrers can be added. */
                if (indirect.empty()) {
                    for (auto & s : steps) {
                        printMsg(lvlDebug, format("finishing build step ‘%1%’") % step->drvPath);
                        nrStepsDone++;
                        steps_->erase(s->drvPath);
                    }
                    break;
                }

            /* Update the database. */
            {
                pqxx::work txn(*conn);

            if (!cachedFailure)
                finishBuildStep(txn, result.startTime, result.stopTime, build->id,
                    stepNr, machine->sshName, buildStepStatus, result.errorMsg);

                BuildStatus buildStatus =
                    result.status == RemoteResult::rrPermanentFailure ? bsFailed :
                    result.status == RemoteResult::rrTimedOut ? bsTimedOut :
                    bsAborted;
                BuildStepStatus buildStepStatus =
                    result.status == RemoteResult::rrPermanentFailure ? bssFailed :
                    result.status == RemoteResult::rrTimedOut ? bssTimedOut :
                    bssAborted;
                /* For regular failures, we don't care about the error
                   message. */
                if (buildStatus != bsAborted) result.errorMsg = "";
                /* Create failed build steps for every build that depends
                   on this. For cached failures, only create a step for
                   builds that don't have this step as top-level
                   (otherwise the user won't be able to see what caused
                   the build to fail). */
                for (auto & build2 : indirect) {
                    if (build == build2) continue;
                    if (cachedFailure && build2->drvPath == step->drvPath) continue;
                    createBuildStep(txn, 0, build2, step, machine->sshName,
                        buildStepStatus, result.errorMsg, build->id);
                }
                if (!cachedFailure)
                    finishBuildStep(txn, result.startTime, result.stopTime, build->id,
                        stepNr, machine->sshName, buildStepStatus, result.errorMsg);
                /* Mark all builds that depend on this derivation as failed. */
                for (auto & build2 : indirect) {
                    printMsg(lvlError, format("marking build %1% as failed") % build2->id);
                    assert(!build->finishedInDB);
                    txn.parameterized
                        ("update Builds set finished = 1, busy = 0, buildStatus = $2, startTime = $3, stopTime = $4, isCachedBuild = $5 where id = $1")
                        (build2->id)
                        ((int) (build2->drvPath != step->drvPath && buildStatus == bsFailed ? bsDepFailed : buildStatus))
                        (result.startTime)
                        (result.stopTime)
                        (cachedFailure ? 1 : 0).exec();
                    nrBuildsDone++;
                }
                /* Remember failed paths in the database so that they
                   won't be built again. */
                if (!cachedFailure && result.status == RemoteResult::rrPermanentFailure)
                    for (auto & path : outputPaths(step->drv))
                        txn.parameterized("insert into FailedPaths values ($1)")(path).exec();

            /* Mark all builds that depend on this derivation as failed. */
            for (auto build2 : dependents) {
                printMsg(lvlError, format("marking build %1% as failed") % build2->id);
                txn.parameterized
                    ("update Builds set finished = 1, busy = 0, buildStatus = $2, startTime = $3, stopTime = $4, isCachedBuild = $5 where id = $1")
                    (build2->id)
                    ((int) (build2->drvPath != step->drvPath && buildStatus == bsFailed ? bsDepFailed : buildStatus))
                    (result.startTime)
                    (result.stopTime)
                    (cachedFailure ? 1 : 0).exec();
                build2->finishedInDB = true; // FIXME: txn might fail
                nrBuildsDone++;

                txn.commit();

            /* Remember failed paths in the database so that they
               won't be built again. */
            if (!cachedFailure && result.status == RemoteResult::rrPermanentFailure)
                for (auto & path : outputPaths(step->drv))
                    txn.parameterized("insert into FailedPaths values ($1)")(path).exec();

            /* Remove the indirect dependencies from ‘builds’. This
               will cause them to be destroyed. */
            for (auto & b : indirect) {
                auto builds_(builds.lock());
                b->finishedInDB = true;
                builds_->erase(b->id);
            }

        txn.commit();

    /* In case of success, destroy all Build objects of which ‘step’
       is the top-level derivation. In case of failure, destroy all
       dependent Build objects. Any Steps not referenced by other
       Builds will be destroyed as well. */
    for (auto build2 : dependents)
        if (build2->toplevel == step || result.status != RemoteResult::rrSuccess) {
            auto builds_(builds.lock());
            builds_->erase(build2->id);
        }

    /* Remove the step from the graph. In case of success, make
       dependent build steps runnable if they have no other
       dependencies. */
    destroyStep(step, result.status == RemoteResult::rrSuccess);

    assert(!build->finishedInDB);

    build->finishedInDB = true; // FIXME: txn might fail