replaceStrings

lib.replaceStrings

Primop

Docs pulled from | This Revision | about 1 hour ago

Nix manual

Takes 3 arguments

from, to, s

Given string s, replace every occurrence of the strings in from with the corresponding string in to.

The argument to is lazy, that is, it is only evaluated when its corresponding pattern in from is matched in the string s

Example:

builtins.replaceStrings ["oo" "a"] ["a" "i"] "foobar"

evaluates to "fabir".

Time Complexity

O(n * k * c) (worst case) where:

n = length of input string k = number of replacement patterns c = average length of patterns in 'from' list

Noogle detected

Aliases

Detected Type

replaceStrings :: [String] -> [String] -> String -> String

Implementation

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

src/libexpr/primops.cc:5163

static void prim_replaceStrings(EvalState & state, const PosIdx pos, Value ** args, Value & v)
{
    state.forceList(*args[0], pos, "while evaluating the first argument passed to builtins.replaceStrings");
    state.forceList(*args[1], pos, "while evaluating the second argument passed to builtins.replaceStrings");
    if (args[0]->listSize() != args[1]->listSize())
        state.error<EvalError>("'from' and 'to' arguments passed to builtins.replaceStrings have different lengths")
            .atPos(pos)
            .debugThrow();

    std::vector<std::string_view> from;
    from.reserve(args[0]->listSize());
    for (auto elem : args[0]->listView())
        from.emplace_back(state.forceString(
            *elem, pos, "while evaluating one of the strings to replace passed to builtins.replaceStrings"));

    boost::unordered_flat_map<size_t, std::string_view> cache;
    auto to = args[1]->listView();

    NixStringContext context;
    auto s = state.forceString(
        *args[2], context, pos, "while evaluating the third argument passed to builtins.replaceStrings");

    std::string res;
    // Loops one past last character to handle the case where 'from' contains an empty string.
    for (size_t p = 0; p <= s.size();) {
        bool found = false;
        auto i = from.begin();
        auto j = to.begin();
        size_t j_index = 0;
        for (; i != from.end(); ++i, ++j, ++j_index)
            if (s.compare(p, i->size(), *i) == 0) {
                found = true;
                auto v = cache.find(j_index);
                if (v == cache.end()) {
                    NixStringContext ctx;
                    auto ts = state.forceString(
                        **j,
                        ctx,
                        pos,
                        "while evaluating one of the replacement strings passed to builtins.replaceStrings");
                    v = (cache.emplace(j_index, ts)).first;
                    for (auto & path : ctx)
                        context.insert(path);
                }
                res += v->second;
                if (i->empty()) {
                    if (p < s.size())
                        res += s[p];
                    p++;
                } else {
                    p += i->size();
                }
                break;
            }
        if (!found) {
            if (p < s.size())
                res += s[p];
            p++;
        }
    }

    v.mkString(res, context, state.mem);
}