genericClosure

lib.trivial.genericClosure

Primop

Docs pulled from | This Revision | 12 minutes ago

Nix manual

Takes 1 arguments

attrset

builtins.genericClosure iteratively computes the transitive closure over an arbitrary relation defined by a function.

It takes attrset with two attributes named startSet and operator, and returns a list of attribute sets:

startSet: The initial list of attribute sets.
operator: A function that takes an attribute set and returns a list of attribute sets. It defines how each item in the current set is processed and expanded into more items.

Each attribute set in the list startSet and the list returned by operator must have an attribute key, which must support equality comparison. The value of key can be one of the following types:

The result is produced by calling the operator on each item that has not been called yet, including newly added items, until no new items are added. Items are compared by their key attribute.

Common usages are:

Generating unique collections of items, such as dependency graphs.
Traversing through structures that may contain cycles or loops.
Processing data structures with complex internal relationships.

Example

builtins.genericClosure {
  startSet = [ {key = 5;} ];
  operator = item: [{
    key = if (item.key / 2 ) * 2 == item.key
         then item.key / 2
         else 3 * item.key + 1;
  }];
}

evaluates to

[ { key = 5; } { key = 16; } { key = 8; } { key = 4; } { key = 2; } { key = 1; } ]

Noogle detected

Aliases

Detected Type

genericClosure :: AttrSet -> [AttrSet]

Implementation

This function is implemented in c++ and is part of the native nix runtime.

src/libexpr/primops.cc:788

static void prim_genericClosure(EvalState & state, const PosIdx pos, Value ** args, Value & v)
{
    state.forceAttrs(*args[0], noPos, "while evaluating the first argument passed to builtins.genericClosure");

    /* Get the start set. */
    auto startSet = state.getAttr(
        state.s.startSet, args[0]->attrs(), "in the attrset passed as argument to builtins.genericClosure");

    state.forceList(
        *startSet->value,
        noPos,
        "while evaluating the 'startSet' attribute passed as argument to builtins.genericClosure");

    ValueList workSet;
    for (auto elem : startSet->value->listView())
        workSet.push_back(elem);

    if (startSet->value->listSize() == 0) {
        v = *startSet->value;
        return;
    }

    /* Get the operator. */
    auto op = state.getAttr(
        state.s.operator_, args[0]->attrs(), "in the attrset passed as argument to builtins.genericClosure");
    state.forceFunction(
        *op->value, noPos, "while evaluating the 'operator' attribute passed as argument to builtins.genericClosure");

    /* Construct the closure by applying the operator to elements of
       `workSet', adding the result to `workSet', continuing until
       no new elements are found. */
    ValueList res;
    // Track which element each key came from
    auto cmp = CompareValues(state, noPos, "");
    std::map<Value *, Value *, decltype(cmp)> keyToElem(cmp);
    while (!workSet.empty()) {
        Value * e = *(workSet.begin());
        workSet.pop_front();

        try {
            state.forceAttrs(*e, noPos, "");
        } catch (Error & err) {
            err.addTrace(nullptr, "in genericClosure element %s", ValuePrinter(state, *e, errorPrintOptions));
            throw;
        }

        const Attr * key;
        try {
            key = state.getAttr(state.s.key, e->attrs(), "");
        } catch (Error & err) {
            err.addTrace(nullptr, "in genericClosure element %s", ValuePrinter(state, *e, errorPrintOptions));
            throw;
        }
        state.forceValue(*key->value, noPos);

        try {
            auto [it, inserted] = keyToElem.insert({key->value, e});
            if (!inserted)
                continue;
        } catch (Error & err) {
            // Try to find which element we're comparing against
            Value * otherElem = nullptr;
            for (auto & [otherKey, elem] : keyToElem) {
                try {
                    cmp(key->value, otherKey);
                } catch (Error &) {
                    // Found the element we're comparing against
                    otherElem = elem;
                    break;
                }
            }
            if (otherElem) {
                // Traces are printed in reverse order; pre-swap them.
                err.addTrace(nullptr, "with element %s", ValuePrinter(state, *otherElem, errorPrintOptions));
                err.addTrace(nullptr, "while comparing element %s", ValuePrinter(state, *e, errorPrintOptions));
            } else {
                // Couldn't find the specific element, just show current
                err.addTrace(nullptr, "while checking key of element %s", ValuePrinter(state, *e, errorPrintOptions));
            }
            throw;
        }
        res.push_back(e);

        /* Call the `operator' function with `e' as argument. */
        Value newElements;
        try {
            state.callFunction(*op->value, {&e, 1}, newElements, noPos);
            state.forceList(
                newElements,
                noPos,
                "while evaluating the return value of the `operator` passed to builtins.genericClosure");

            /* Add the values returned by the operator to the work set. */
            for (auto elem : newElements.listView()) {
                state.forceValue(*elem, noPos); // "while evaluating one one of the elements returned by the `operator`
                                                // passed to builtins.genericClosure");
                workSet.push_back(elem);
            }
        } catch (Error & err) {
            err.addTrace(
                nullptr,
                "while calling %s on genericClosure element %s",
                state.symbols[state.s.operator_],
                ValuePrinter(state, *e, errorPrintOptions));
            throw;
        }
    }

    /* Create the result list. */
    auto list = state.buildList(res.size());
    for (const auto & [n, i] : enumerate(res))
        list[n] = i;
    v.mkList(list);
}

Implementation

The following is the current implementation of this function.

genericClosure