* Generalised the dependencyClosure primop to builtins.genericClosure,

  which is hopefully more useful.
* New primops: length, mul, div.

5 files changed, 442 insertions, 139 deletions

diff --git a/doc/manual/release-notes.xml b/doc/manual/release-notes.xml
index a3c33b5f7f6d..3559b12479e6 100644
--- a/doc/manual/release-notes.xml
+++ b/doc/manual/release-notes.xml
@@ -17,8 +17,13 @@
   <listitem><para><command>nix-store --dump-db / --load-db</command>.</para></listitem>
 
   <listitem><para>New primops:
-  <varname>builtins.parseDrvName</varname> and
-  <varname>builtins.compareVersions</varname>.</para></listitem>
+  <varname>builtins.parseDrvName</varname>,
+  <varname>builtins.compareVersions</varname>,
+  <varname>builtins.length</varname>,
+  <varname>builtins.add</varname>,
+  <varname>builtins.sub</varname>,
+  <varname>builtins.genericClosure</varname>.
+  </para></listitem>
 
 </itemizedlist>
 
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index fbef227223dc..c747f46c4677 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -128,59 +128,7 @@ static Expr prim_isFunction(EvalState & state, const ATermVector & args)
 }
 
 
-static Path findDependency(Path dir, string dep)
-{
-    if (dep[0] == '/') throw EvalError(
-        format("illegal absolute dependency `%1%'") % dep);
-
-    Path p = canonPath(dir + "/" + dep);
-
-    if (pathExists(p))
-        return p;
-    else
-        return "";
-}
-
-
-/* Make path `p' relative to directory `pivot'.  E.g.,
-   relativise("/a/b/c", "a/b/x/y") => "../x/y".  Both input paths
-   should be in absolute canonical form. */
-static string relativise(Path pivot, Path p)
-{
-    assert(pivot.size() > 0 && pivot[0] == '/');
-    assert(p.size() > 0 && p[0] == '/');
-        
-    if (pivot == p) return ".";
-
-    /* `p' is in `pivot'? */
-    Path pivot2 = pivot + "/";
-    if (p.substr(0, pivot2.size()) == pivot2) {
-        return p.substr(pivot2.size());
-    }
-
-    /* Otherwise, `p' is in a parent of `pivot'.  Find up till which
-       path component `p' and `pivot' match, and add an appropriate
-       number of `..' components. */
-    string::size_type i = 1;
-    while (1) {
-        string::size_type j = pivot.find('/', i);
-        if (j == string::npos) break;
-        j++;
-        if (pivot.substr(0, j) != p.substr(0, j)) break;
-        i = j;
-    }
-
-    string prefix;
-    unsigned int slashes = count(pivot.begin() + i, pivot.end(), '/') + 1;
-    while (slashes--) {
-        prefix += "../";
-    }
-
-    return prefix + p.substr(i);
-}
-
-
-static Expr prim_dependencyClosure(EvalState & state, const ATermVector & args)
+static Expr prim_genericClosure(EvalState & state, const ATermVector & args)
 {
     startNest(nest, lvlDebug, "finding dependencies");
 
@@ -191,87 +139,40 @@ static Expr prim_dependencyClosure(EvalState & state, const ATermVector & args)
     if (!startSet) throw EvalError("attribute `startSet' required");
     ATermList startSet2 = evalList(state, startSet);
 
-    Path pivot;
-    PathSet workSet;
-    for (ATermIterator i(startSet2); i; ++i) {
-        PathSet context; /* !!! what to do? */
-        Path p = coerceToPath(state, *i, context);
-        workSet.insert(p);
-        pivot = dirOf(p);
-    }
-
-    /* Get the search path. */
-    PathSet searchPath;
-    Expr e = queryAttr(attrs, "searchPath");
-    if (e) {
-        ATermList list = evalList(state, e);
-        for (ATermIterator i(list); i; ++i) {
-            PathSet context; /* !!! what to do? */
-            Path p = coerceToPath(state, *i, context);
-            searchPath.insert(p);
-        }
-    }
+    set<Expr> workSet; // !!! gc roots
+    for (ATermIterator i(startSet2); i; ++i) workSet.insert(*i);
 
-    Expr scanner = queryAttr(attrs, "scanner");
-    if (!scanner) throw EvalError("attribute `scanner' required");
+    /* Get the operator. */
+    Expr op = queryAttr(attrs, "operator");
+    if (!op) throw EvalError("attribute `operator' required");
     
-    /* Construct the dependency closure by querying the dependency of
-       each path in `workSet', adding the dependencies to
-       `workSet'. */
-    PathSet doneSet;
+    /* Construct the closure by applying the operator to element of
+       `workSet', adding the result to `workSet', continuing until
+       no new elements are found. */
+    ATermList res = ATempty;
+    set<Expr> doneKeys; // !!! gc roots
     while (!workSet.empty()) {
-	Path path = *(workSet.begin());
-	workSet.erase(path);
+	Expr e = *(workSet.begin());
+	workSet.erase(e);
 
-	if (doneSet.find(path) != doneSet.end()) continue;
-        doneSet.insert(path);
+        e = strictEvalExpr(state, e);
 
-        try {
-            
-            /* Call the `scanner' function with `path' as argument. */
-            debug(format("finding dependencies in `%1%'") % path);
-            ATermList deps = evalList(state, makeCall(scanner, makeStr(path)));
-
-            /* Try to find the dependencies relative to the `path'. */
-            for (ATermIterator i(deps); i; ++i) {
-                string s = evalStringNoCtx(state, *i);
-                
-                Path dep = findDependency(dirOf(path), s);
-
-                if (dep == "") {
-                    for (PathSet::iterator j = searchPath.begin();
-                         j != searchPath.end(); ++j)
-                    {
-                        dep = findDependency(*j, s);
-                        if (dep != "") break;
-                    }
-                }
-                
-                if (dep == "")
-                    debug(format("did NOT find dependency `%1%'") % s);
-                else {
-                    debug(format("found dependency `%1%'") % dep);
-                    workSet.insert(dep);
-                }
-            }
+        Expr key = queryAttr(e, "key");
+        if (!key) throw EvalError("attribute `key' required");
 
-        } catch (Error & e) {
-            e.addPrefix(format("while finding dependencies in `%1%':\n")
-                % path);
-            throw;
-        }
-    }
+	if (doneKeys.find(key) != doneKeys.end()) continue;
+        doneKeys.insert(key);
+        res = ATinsert(res, e);
+        
+        /* Call the `operator' function with `e' as argument. */
+        ATermList res = evalList(state, makeCall(op, e));
 
-    /* Return a list of the dependencies we've just found. */
-    ATermList deps = ATempty;
-    for (PathSet::iterator i = doneSet.begin(); i != doneSet.end(); ++i) {
-        deps = ATinsert(deps, makeStr(relativise(pivot, *i)));
-        deps = ATinsert(deps, makeStr(*i));
+        /* Try to find the dependencies relative to the `path'. */
+        for (ATermIterator i(res); i; ++i)
+            workSet.insert(evalExpr(state, *i));
     }
 
-    debug(format("dependency list is `%1%'") % makeList(deps));
-    
-    return makeList(deps);
+    return makeList(res);
 }
 
 
@@ -311,15 +212,6 @@ static Expr prim_trace(EvalState & state, const ATermVector & args)
 }
 
 
-static Expr prim_relativise(EvalState & state, const ATermVector & args)
-{
-    PathSet context; /* !!! what to do? */
-    Path pivot = coerceToPath(state, args[0], context);
-    Path path = coerceToPath(state, args[1], context);
-    return makeStr(relativise(pivot, path));
-}
-
-
 /*************************************************************
  * Derivations
  *************************************************************/
@@ -874,6 +766,14 @@ static Expr prim_map(EvalState & state, const ATermVector & args)
 }
 
 
+/* Return the length of a list.  This is an O(1) time operation. */
+static Expr prim_length(EvalState & state, const ATermVector & args)
+{
+    ATermList list = evalList(state, args[0]);
+    return makeInt(ATgetLength(list));
+}
+
+
 /*************************************************************
  * Integer arithmetic
  *************************************************************/
@@ -895,6 +795,23 @@ static Expr prim_sub(EvalState & state, const ATermVector & args)
 }
 
 
+static Expr prim_mul(EvalState & state, const ATermVector & args)
+{
+    int i1 = evalInt(state, args[0]);
+    int i2 = evalInt(state, args[1]);
+    return makeInt(i1 * i2);
+}
+
+
+static Expr prim_div(EvalState & state, const ATermVector & args)
+{
+    int i1 = evalInt(state, args[0]);
+    int i2 = evalInt(state, args[1]);
+    if (i2 == 0) throw EvalError("division by zero");
+    return makeInt(i1 / i2);
+}
+
+
 static Expr prim_lessThan(EvalState & state, const ATermVector & args)
 {
     int i1 = evalInt(state, args[0]);
@@ -1019,7 +936,7 @@ void EvalState::addPrimOps()
     addPrimOp("import", 1, prim_import);
     addPrimOp("isNull", 1, prim_isNull);
     addPrimOp("__isFunction", 1, prim_isFunction);
-    addPrimOp("dependencyClosure", 1, prim_dependencyClosure);
+    addPrimOp("__genericClosure", 1, prim_genericClosure);
     addPrimOp("abort", 1, prim_abort);
     addPrimOp("throw", 1, prim_throw);
     addPrimOp("__getEnv", 1, prim_getEnv);
@@ -1029,8 +946,6 @@ void EvalState::addPrimOps()
     addPrimOp("__exprToString", 1, prim_exprToString);
     addPrimOp("__stringToExpr", 1, prim_stringToExpr);
 
-    addPrimOp("relativise", 2, prim_relativise);
-
     // Derivations
     addPrimOp("derivation!", 1, prim_derivationStrict);
     addPrimOp("derivation", 1, prim_derivationLazy);
@@ -1060,10 +975,13 @@ void EvalState::addPrimOps()
     addPrimOp("__head", 1, prim_head);
     addPrimOp("__tail", 1, prim_tail);
     addPrimOp("map", 2, prim_map);
+    addPrimOp("__length", 1, prim_length);
 
     // Integer arithmetic
     addPrimOp("__add", 2, prim_add);
     addPrimOp("__sub", 2, prim_sub);
+    addPrimOp("__mul", 2, prim_mul);
+    addPrimOp("__div", 2, prim_div);
     addPrimOp("__lessThan", 2, prim_lessThan);
 
     // String manipulation
diff --git a/tests/lang/eval-okay-closure.exp.xml b/tests/lang/eval-okay-closure.exp.xml
new file mode 100644
index 000000000000..dffc03a99891
--- /dev/null
+++ b/tests/lang/eval-okay-closure.exp.xml
@@ -0,0 +1,343 @@
+<?xml version='1.0' encoding='utf-8'?>
+<expr>
+  <list>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="-13" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="-12" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="-11" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="-9" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="-8" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="-7" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="-5" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="-4" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="-3" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="key">
+        <int value="-1" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="0" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="1" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="2" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="4" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="5" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="6" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="key">
+        <int value="8" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="9" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="10" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="13" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="14" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="15" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="key">
+        <int value="17" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="18" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="19" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="22" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="23" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="key">
+        <int value="26" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="27" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="28" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="31" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="32" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="key">
+        <int value="35" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="36" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="40" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="41" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="key">
+        <int value="44" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="45" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="49" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="key">
+        <int value="53" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="54" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="58" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="key">
+        <int value="62" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="foo">
+        <bool value="true" />
+      </attr>
+      <attr name="key">
+        <int value="67" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="key">
+        <int value="71" />
+      </attr>
+    </attrs>
+    <attrs>
+      <attr name="key">
+        <int value="80" />
+      </attr>
+    </attrs>
+  </list>
+</expr>
diff --git a/tests/lang/eval-okay-closure.nix b/tests/lang/eval-okay-closure.nix
new file mode 100644
index 000000000000..cccd4dc35730
--- /dev/null
+++ b/tests/lang/eval-okay-closure.nix
@@ -0,0 +1,13 @@
+let
+
+  closure = builtins.genericClosure {
+    startSet = [{key = 80;}];
+    operator = {key, foo ? false}:
+      if builtins.lessThan key 0
+      then []
+      else [{key = builtins.sub key 9;} {key = builtins.sub key 13; foo = true;}];
+  };
+
+  sort = (import ./lib.nix).sortBy (a: b: builtins.lessThan a.key b.key);
+
+in sort closure
diff --git a/tests/lang/lib.nix b/tests/lang/lib.nix
index e508f28ba53f..551b67aed350 100644
--- a/tests/lang/lib.nix
+++ b/tests/lang/lib.nix
@@ -25,4 +25,28 @@ rec {
     in !(lessThan lenFileName lenExt) &&
        substring (sub lenFileName lenExt) lenFileName fileName == ext;
 
+  # Split a list at the given position.
+  splitAt = pos: list:
+    if pos == 0 then {first = []; second = list;} else
+    if list == [] then {first = []; second = [];} else
+    let res = splitAt (sub pos 1) (tail list);
+    in {first = [(head list)] ++ res.first; second = res.second;};
+
+  # Stable merge sort.
+  sortBy = comp: list:
+    if lessThan 1 (length list)
+    then
+      let
+        split = splitAt (div (length list) 2) list;
+        first = sortBy comp split.first;
+        second = sortBy comp split.second;
+      in mergeLists comp first second
+    else list;
+
+  mergeLists = comp: list1: list2:
+    if list1 == [] then list2 else
+    if list2 == [] then list1 else
+    if comp (head list2) (head list1) then [(head list2)] ++ mergeLists comp list1 (tail list2) else
+    [(head list1)] ++ mergeLists comp (tail list1) list2;
+
 }