* Implemented `map'.

4 files changed, 139 insertions, 108 deletions

diff --git a/src/libexpr/eval-test.cc b/src/libexpr/eval-test.cc
index 8aade1298f3d..0b20883a33d4 100644
--- a/src/libexpr/eval-test.cc
+++ b/src/libexpr/eval-test.cc
@@ -68,6 +68,8 @@ void run(Strings args)
     doTest("let x = x; in if true || x then 1 else 2");
     doTest("/etc/passwd");
     doTest("import ./foo.nix");
+    doTest("map (x: __add 1 x) [ 1 2 3 ]");
+    doTest("map (__add 1) [ 1 2 3 ]");
 }
 
 
diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index 86484031b1e5..f1437e465709 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -328,106 +328,9 @@ void EvalState::eval(Env & env, Expr e, Value & v)
     Expr fun, arg;
     if (matchCall(e, fun, arg)) {
         eval(env, fun, v);
-
-        if (v.type == tPrimOp || v.type == tPrimOpApp) {
-            unsigned int argsLeft =
-                v.type == tPrimOp ? v.primOp.arity : v.primOpApp.argsLeft;
-            if (argsLeft == 1) {
-                /* We have all the arguments, so call the primop.
-                   First find the primop. */
-                Value * primOp = &v;
-                while (primOp->type == tPrimOpApp) primOp = primOp->primOpApp.left;
-                assert(primOp->type == tPrimOp);
-                unsigned int arity = primOp->primOp.arity;
-                
-                Value vLastArg;
-                mkThunk(vLastArg, env, arg);
-
-                /* Put all the arguments in an array. */
-                Value * vArgs[arity];
-                unsigned int n = arity - 1;
-                vArgs[n--] = &vLastArg;
-                for (Value * arg = &v; arg->type == tPrimOpApp; arg = arg->primOpApp.left)
-                    vArgs[n--] = arg->primOpApp.right;
-
-                /* And call the primop. */
-                primOp->primOp.fun(*this, vArgs, v);
-            } else {
-                Value * v2 = allocValues(2);
-                v2[0] = v;
-                mkThunk(v2[1], env, arg);
-                v.type = tPrimOpApp;
-                v.primOpApp.left = &v2[0];
-                v.primOpApp.right = &v2[1];
-                v.primOpApp.argsLeft = argsLeft - 1;
-            }
-            return;
-        }
-        
-        if (v.type != tLambda) throw TypeError("expected function");
-
-        Env & env2(allocEnv());
-        env2.up = &env;
-
-        ATermList formals; ATerm ellipsis;
-
-        if (matchVarPat(v.lambda.pat, name)) {
-            Value & vArg = env2.bindings[name];
-            nrValues++;
-            mkThunk(vArg, env, arg);
-        }
-
-        else if (matchAttrsPat(v.lambda.pat, formals, ellipsis, name)) {
-            Value * vArg;
-            Value vArg_;
-
-            if (name == sNoAlias)
-                vArg = &vArg_;
-            else {
-                vArg = &env2.bindings[name];
-                nrValues++;
-            }                
-
-            eval(env, arg, *vArg);
-            forceAttrs(*vArg);
-            
-            /* For each formal argument, get the actual argument.  If
-               there is no matching actual argument but the formal
-               argument has a default, use the default. */
-            unsigned int attrsUsed = 0;
-            for (ATermIterator i(formals); i; ++i) {
-                Expr def; Sym name;
-                DefaultValue def2;
-                if (!matchFormal(*i, name, def2)) abort(); /* can't happen */
-
-                Bindings::iterator j = vArg->attrs->find(name);
-                
-                Value & v = env2.bindings[name];
-                nrValues++;
-                
-                if (j == vArg->attrs->end()) {
-                    if (!matchDefaultValue(def2, def)) def = 0;
-                    if (def == 0) throw TypeError(format("the argument named `%1%' required by the function is missing")
-                        % aterm2String(name));
-                    mkThunk(v, env2, def);
-                } else {
-                    attrsUsed++;
-                    v.type = tCopy;
-                    v.val = &j->second;
-                }
-            }
-
-            /* Check that each actual argument is listed as a formal
-               argument (unless the attribute match specifies a
-               `...').  TODO: show the names of the
-               expected/unexpected arguments. */
-            if (ellipsis == eFalse && attrsUsed != vArg->attrs->size())
-                throw TypeError("function called with unexpected argument");
-        }
-
-        else abort();
-        
-        eval(env2, v.lambda.body, v);
+        Value vArg;
+        mkThunk(vArg, env, arg); // !!! should this be on the heap?
+        callFunction(v, vArg, v);
         return;
     }
 
@@ -519,6 +422,103 @@ void EvalState::eval(Env & env, Expr e, Value & v)
 }
 
 
+void EvalState::callFunction(Value & fun, Value & arg, Value & v)
+{
+    if (fun.type == tPrimOp || fun.type == tPrimOpApp) {
+        unsigned int argsLeft =
+            fun.type == tPrimOp ? fun.primOp.arity : fun.primOpApp.argsLeft;
+        if (argsLeft == 1) {
+            /* We have all the arguments, so call the primop.  First
+               find the primop. */
+            Value * primOp = &fun;
+            while (primOp->type == tPrimOpApp) primOp = primOp->primOpApp.left;
+            assert(primOp->type == tPrimOp);
+            unsigned int arity = primOp->primOp.arity;
+                
+            /* Put all the arguments in an array. */
+            Value * vArgs[arity];
+            unsigned int n = arity - 1;
+            vArgs[n--] = &arg;
+            for (Value * arg = &fun; arg->type == tPrimOpApp; arg = arg->primOpApp.left)
+                vArgs[n--] = arg->primOpApp.right;
+
+            /* And call the primop. */
+            primOp->primOp.fun(*this, vArgs, v);
+        } else {
+            Value * v2 = allocValues(2);
+            v2[0] = fun;
+            v2[1] = arg;
+            v.type = tPrimOpApp;
+            v.primOpApp.left = &v2[0];
+            v.primOpApp.right = &v2[1];
+            v.primOpApp.argsLeft = argsLeft - 1;
+        }
+        return;
+    }
+    
+    if (fun.type != tLambda)
+        throwTypeError("attempt to call something which is neither a function nor a primop (built-in operation) but %1%",
+            showType(fun));
+
+    Env & env2(allocEnv());
+    env2.up = fun.lambda.env;
+
+    ATermList formals; ATerm ellipsis, name;
+
+    if (matchVarPat(fun.lambda.pat, name)) {
+        Value & vArg = env2.bindings[name];
+        nrValues++;
+        vArg = arg;
+    }
+
+    else if (matchAttrsPat(fun.lambda.pat, formals, ellipsis, name)) {
+        forceAttrs(arg);
+        
+        if (name != sNoAlias) {
+            env2.bindings[name] = arg;
+            nrValues++;
+        }                
+
+        /* For each formal argument, get the actual argument.  If
+           there is no matching actual argument but the formal
+           argument has a default, use the default. */
+        unsigned int attrsUsed = 0;
+        for (ATermIterator i(formals); i; ++i) {
+            Expr def; Sym name;
+            DefaultValue def2;
+            if (!matchFormal(*i, name, def2)) abort(); /* can't happen */
+
+            Bindings::iterator j = arg.attrs->find(name);
+                
+            Value & v = env2.bindings[name];
+            nrValues++;
+                
+            if (j == arg.attrs->end()) {
+                if (!matchDefaultValue(def2, def)) def = 0;
+                if (def == 0) throw TypeError(format("the argument named `%1%' required by the function is missing")    
+                    % aterm2String(name));
+                mkThunk(v, env2, def);
+            } else {
+                attrsUsed++;
+                v.type = tCopy;
+                v.val = &j->second;
+            }
+        }
+
+        /* Check that each actual argument is listed as a formal
+           argument (unless the attribute match specifies a `...').
+           TODO: show the names of the expected/unexpected
+           arguments. */
+        if (ellipsis == eFalse && attrsUsed != arg.attrs->size())
+            throw TypeError("function called with unexpected argument");
+    }
+
+    else abort();
+        
+    eval(env2, fun.lambda.body, v);
+}
+
+
 void EvalState::eval(Expr e, Value & v)
 {
     eval(baseEnv, e, v);
@@ -567,6 +567,8 @@ void EvalState::forceValue(Value & v)
         forceValue(*v.val);
         v = *v.val;
     }
+    else if (v.type == tApp)
+        callFunction(*v.app.left, *v.app.right, v);
     else if (v.type == tBlackhole)
         throw EvalError("infinite recursion encountered");
 }
@@ -597,6 +599,14 @@ void EvalState::forceList(Value & v)
 }
 
 
+void EvalState::forceFunction(Value & v)
+{
+    forceValue(v);
+    if (v.type != tLambda && v.type != tPrimOp && v.type != tPrimOpApp)
+        throw TypeError(format("value is %1% while a function was expected") % showType(v));
+}
+
+
 string EvalState::coerceToString(Value & v, PathSet & context,
     bool coerceMore, bool copyToStore)
 {
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index 4706602d59fa..385c2d78da5b 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -36,6 +36,7 @@ typedef enum {
     tAttrs,
     tList,
     tThunk,
+    tApp,
     tLambda,
     tCopy,
     tBlackhole,
@@ -69,6 +70,9 @@ struct Value
             Expr expr;
         } thunk;
         struct {
+            Value * left, * right;
+        } app;
+        struct {
             Env * env;
             Pattern pat;
             Expr body;
@@ -161,13 +165,16 @@ struct EvalState
     void strictEval(Env & env, Expr e, Value & v);
 
     /* If `v' is a thunk, enter it and overwrite `v' with the result
-       of the evaluation of the thunk.  Otherwise, this is a no-op. */
+       of the evaluation of the thunk.  If `v' is a delayed function
+       application, call the function and overwrite `v' with the
+       result.  Otherwise, this is a no-op. */
     void forceValue(Value & v);
 
     /* Force `v', and then verify that it has the expected type. */
     int forceInt(Value & v);
     void forceAttrs(Value & v);
     void forceList(Value & v);
+    void forceFunction(Value & v); // either lambda or primop
 
     /* String coercion.  Converts strings, paths and derivations to a
        string.  If `coerceMore' is set, also converts nulls, integers,
@@ -196,6 +203,10 @@ private:
        elements and attributes are compared recursively. */
     bool eqValues(Value & v1, Value & v2);
 
+    void callFunction(Value & fun, Value & arg, Value & v);
+
+public:
+    
     /* Allocation primitives. */
     Value * allocValues(unsigned int count);
     Env & allocEnv();
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index 2815567e5d15..bf8271b130d9 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -913,22 +913,28 @@ static Expr prim_tail(EvalState & state, const ATermVector & args)
         throw Error("`tail' called on an empty list");
     return makeList(ATgetNext(list));
 }
+#endif
 
 
 /* Apply a function to every element of a list. */
-static Expr prim_map(EvalState & state, const ATermVector & args)
+static void prim_map(EvalState & state, Value * * args, Value & v)
 {
-    Expr fun = evalExpr(state, args[0]);
-    ATermList list = evalList(state, args[1]);
+    state.forceFunction(*args[0]);
+    state.forceList(*args[1]);
 
-    ATermList res = ATempty;
-    for (ATermIterator i(list); i; ++i)
-        res = ATinsert(res, makeCall(fun, *i));
+    v.type = tList;
+    v.list.length = args[1]->list.length;
+    v.list.elems = state.allocValues(v.list.length);
 
-    return makeList(ATreverse(res));
+    for (unsigned int n = 0; n < v.list.length; ++n) {
+        v.list.elems[n].type = tApp;
+        v.list.elems[n].app.left = args[0];
+        v.list.elems[n].app.right = &args[1]->list.elems[n];
+    }
 }
 
 
+#if 0
 /* Return the length of a list.  This is an O(1) time operation. */
 static Expr prim_length(EvalState & state, const ATermVector & args)
 {
@@ -1189,7 +1195,9 @@ void EvalState::createBaseEnv()
     addPrimOp("__head", 1, prim_head);
 #if 0
     addPrimOp("__tail", 1, prim_tail);
+#endif
     addPrimOp("map", 2, prim_map);
+#if 0
     addPrimOp("__length", 1, prim_length);
 #endif