Merge branch 'master' into no-manifests

5 files changed, 179 insertions, 23 deletions

diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index 74f7560fe0ea..c10177223e5a 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -144,6 +144,8 @@ EvalState::EvalState()
 {
     nrEnvs = nrValuesInEnvs = nrValues = nrListElems = 0;
     nrAttrsets = nrOpUpdates = nrOpUpdateValuesCopied = 0;
+    nrListConcats = nrPrimOpCalls = nrFunctionCalls = 0;
+    countCalls = getEnv("NIX_COUNT_CALLS", "0") != "0";
 
 #if HAVE_BOEHMGC
     static bool gcInitialised = true;
@@ -300,8 +302,10 @@ inline Value * EvalState::lookupVar(Env * env, const VarRef & var)
     if (var.fromWith) {
         while (1) {
             Bindings::iterator j = env->values[0]->attrs->find(var.name);
-            if (j != env->values[0]->attrs->end())
+            if (j != env->values[0]->attrs->end()) {
+                if (countCalls && j->pos) attrSelects[*j->pos]++;
                 return j->value;
+            }
             if (env->prevWith == 0)
                 throwEvalError("undefined variable `%1%'", var.name);
             for (unsigned int l = env->prevWith; l; --l, env = env->up) ;
@@ -344,7 +348,7 @@ void EvalState::mkList(Value & v, unsigned int length)
 {
     v.type = tList;
     v.list.length = length;
-    v.list.elems = (Value * *) GC_MALLOC(length * sizeof(Value *));
+    v.list.elems = length ? (Value * *) GC_MALLOC(length * sizeof(Value *)) : 0;
     nrListElems += length;
 }
 
@@ -619,8 +623,10 @@ void ExprSelect::eval(EvalState & state, Env & env, Value & v)
             }
             vAttrs = j->value;
             pos = j->pos;
+            if (state.countCalls && pos) state.attrSelects[*pos]++;
         }
     
+
         state.forceValue(*vAttrs);
         
     } catch (Error & e) {
@@ -700,6 +706,8 @@ void EvalState::callFunction(Value & fun, Value & arg, Value & v)
                 vArgs[n--] = arg->primOpApp.right;
 
             /* And call the primop. */
+            nrPrimOpCalls++;
+            if (countCalls) primOpCalls[primOp->primOp->name]++;
             try {
                 primOp->primOp->fun(*this, vArgs, v);
             } catch (Error & e) {
@@ -716,7 +724,7 @@ void EvalState::callFunction(Value & fun, Value & arg, Value & v)
     }
     
     if (fun.type != tLambda)
-        throwTypeError("attempt to call something which is neither a function nor a primop (built-in operation) but %1%",
+        throwTypeError("attempt to call something which is not a function but %1%",
             showType(fun));
 
     unsigned int size =
@@ -760,6 +768,9 @@ void EvalState::callFunction(Value & fun, Value & arg, Value & v)
             throwTypeError("function at %1% called with unexpected argument", fun.lambda.fun->pos);
     }
 
+    nrFunctionCalls++;
+    if (countCalls) functionCalls[fun.lambda.fun->pos]++;
+
     try {
         fun.lambda.fun->body->eval(*this, env2, v);
     } catch (Error & e) {
@@ -902,14 +913,36 @@ void ExprOpUpdate::eval(EvalState & state, Env & env, Value & v)
 void ExprOpConcatLists::eval(EvalState & state, Env & env, Value & v)
 {
     Value v1; e1->eval(state, env, v1);
-    state.forceList(v1);
     Value v2; e2->eval(state, env, v2);
-    state.forceList(v2);
-    state.mkList(v, v1.list.length + v2.list.length);
-    for (unsigned int n = 0; n < v1.list.length; ++n)
-        v.list.elems[n] = v1.list.elems[n];
-    for (unsigned int n = 0; n < v2.list.length; ++n)
-        v.list.elems[n + v1.list.length] = v2.list.elems[n];
+    Value * lists[2] = { &v1, &v2 };
+    state.concatLists(v, 2, lists);
+}
+
+
+void EvalState::concatLists(Value & v, unsigned int nrLists, Value * * lists)
+{
+    nrListConcats++;
+
+    Value * nonEmpty = 0;
+    unsigned int len = 0;
+    for (unsigned int n = 0; n < nrLists; ++n) {
+        forceList(*lists[n]);
+        unsigned int l = lists[n]->list.length;
+        len += l;
+        if (l) nonEmpty = lists[n];
+    }
+
+    if (nonEmpty && len == nonEmpty->list.length) {
+        v = *nonEmpty;
+        return;
+    }
+
+    mkList(v, len);
+    for (unsigned int n = 0, pos = 0; n < nrLists; ++n) {
+        unsigned int l = lists[n]->list.length;
+        memcpy(v.list.elems + pos, lists[n]->list.elems, l * sizeof(Value *));
+        pos += l;
+    }
 }
 
 
@@ -932,7 +965,7 @@ void ExprConcatStrings::eval(EvalState & state, Env & env, Value & v)
             isPath = vStr.type == tPath;
             first = false;
         }
-            
+
         s << state.coerceToString(vStr, context, false, !isPath);
     }
         
@@ -1207,6 +1240,7 @@ void EvalState::printStats()
         % nrEnvs % (nrEnvs * sizeof(Env) + nrValuesInEnvs * sizeof(Value *)));
     printMsg(v, format("  list elements: %1% (%2% bytes)")
         % nrListElems % (nrListElems * sizeof(Value *)));
+    printMsg(v, format("  list concatenations: %1%") % nrListConcats);
     printMsg(v, format("  values allocated: %1% (%2% bytes)")
         % nrValues % (nrValues * sizeof(Value)));
     printMsg(v, format("  attribute sets allocated: %1%") % nrAttrsets);
@@ -1216,6 +1250,36 @@ void EvalState::printStats()
     printMsg(v, format("  number of thunks: %1%") % nrThunks);
     printMsg(v, format("  number of thunks avoided: %1%") % nrAvoided);
     printMsg(v, format("  number of attr lookups: %1%") % nrLookups);
+    printMsg(v, format("  number of primop calls: %1%") % nrPrimOpCalls);
+    printMsg(v, format("  number of function calls: %1%") % nrFunctionCalls);
+
+    if (countCalls) {
+
+        printMsg(v, format("calls to %1% primops:") % primOpCalls.size());
+        typedef std::multimap<unsigned int, Symbol> PrimOpCalls_;
+        std::multimap<unsigned int, Symbol> primOpCalls_;
+        foreach (PrimOpCalls::iterator, i, primOpCalls)
+            primOpCalls_.insert(std::pair<unsigned int, Symbol>(i->second, i->first));
+        foreach_reverse (PrimOpCalls_::reverse_iterator, i, primOpCalls_)
+            printMsg(v, format("%1$10d %2%") % i->first % i->second);
+
+        printMsg(v, format("calls to %1% functions:") % functionCalls.size());
+        typedef std::multimap<unsigned int, Pos> FunctionCalls_;
+        std::multimap<unsigned int, Pos> functionCalls_;
+        foreach (FunctionCalls::iterator, i, functionCalls)
+            functionCalls_.insert(std::pair<unsigned int, Pos>(i->second, i->first));
+        foreach_reverse (FunctionCalls_::reverse_iterator, i, functionCalls_)
+            printMsg(v, format("%1$10d %2%") % i->first % i->second);
+
+        printMsg(v, format("evaluations of %1% attributes:") % attrSelects.size());
+        typedef std::multimap<unsigned int, Pos> AttrSelects_;
+        std::multimap<unsigned int, Pos> attrSelects_;
+        foreach (AttrSelects::iterator, i, attrSelects)
+            attrSelects_.insert(std::pair<unsigned int, Pos>(i->second, i->first));
+        foreach_reverse (AttrSelects_::reverse_iterator, i, attrSelects_)
+            printMsg(v, format("%1$10d %2%") % i->first % i->second);
+
+    }
 }
 
 
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index 5103ae8cefe9..a1f26a0566d1 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -232,11 +232,13 @@ public:
     void mkAttrs(Value & v, unsigned int expected);
     void mkThunk_(Value & v, Expr * expr);
 
+    void concatLists(Value & v, unsigned int nrLists, Value * * lists);
+
     /* Print statistics. */
     void printStats();
 
 private:
-    
+
     unsigned long nrEnvs;
     unsigned long nrValuesInEnvs;
     unsigned long nrValues;
@@ -244,9 +246,25 @@ private:
     unsigned long nrAttrsets;
     unsigned long nrOpUpdates;
     unsigned long nrOpUpdateValuesCopied;
-    
-    friend class RecursionCounter;
+    unsigned long nrListConcats;
+    unsigned long nrPrimOpCalls;
+    unsigned long nrFunctionCalls;
+
+    bool countCalls;
+
+    typedef std::map<Symbol, unsigned int> PrimOpCalls;
+    PrimOpCalls primOpCalls;
+
+    typedef std::map<Pos, unsigned int> FunctionCalls;
+    FunctionCalls functionCalls;
+
+    typedef std::map<Pos, unsigned int> AttrSelects;
+    AttrSelects attrSelects;
+
     friend class ExprOpUpdate;
+    friend class ExprOpConcatLists;
+    friend class ExprSelect;
+    friend void prim_getAttr(EvalState & state, Value * * args, Value & v);
 };
 
 
diff --git a/src/libexpr/nixexpr.hh b/src/libexpr/nixexpr.hh
index 4c1a0bb2d5fb..bc6c3287c79d 100644
--- a/src/libexpr/nixexpr.hh
+++ b/src/libexpr/nixexpr.hh
@@ -27,6 +27,15 @@ struct Pos
     Pos() : line(0), column(0) { };
     Pos(const string & file, unsigned int line, unsigned int column)
         : file(file), line(line), column(column) { };
+    bool operator < (const Pos & p2) const
+    {
+        int d = file.compare(p2.file);
+        if (d < 0) return true;
+        if (d > 0) return false;
+        if (line < p2.line) return true;
+        if (line > p2.line) return false;
+        return column < p2.column;
+    }
 };
 
 extern Pos noPos;
diff --git a/src/libexpr/parser.y b/src/libexpr/parser.y
index 095e288430f6..1819da5e1caa 100644
--- a/src/libexpr/parser.y
+++ b/src/libexpr/parser.y
@@ -203,7 +203,7 @@ static Expr * stripIndentation(SymbolTable & symbols, vector<Expr *> & es)
         es2->push_back(new ExprString(symbols.create(s2)));
     }
 
-    return new ExprConcatStrings(es2);
+    return es2->size() == 1 ? (*es2)[0] : new ExprConcatStrings(es2);
 }
 
 
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index 7258c4cc0fa9..d3809e6984a0 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -719,7 +719,7 @@ static void prim_attrNames(EvalState & state, Value * * args, Value & v)
 
 
 /* Dynamic version of the `.' operator. */
-static void prim_getAttr(EvalState & state, Value * * args, Value & v)
+void prim_getAttr(EvalState & state, Value * * args, Value & v)
 {
     string attr = state.forceStringNoCtx(*args[0]);
     state.forceAttrs(*args[1]);
@@ -728,6 +728,7 @@ static void prim_getAttr(EvalState & state, Value * * args, Value & v)
     if (i == args[1]->attrs->end())
         throw EvalError(format("attribute `%1%' missing") % attr);
     // !!! add to stack trace?
+    if (state.countCalls && i->pos) state.attrSelects[*i->pos]++;
     state.forceValue(*i->value);
     v = *i->value;
 }
@@ -873,19 +874,33 @@ static void prim_isList(EvalState & state, Value * * args, Value & v)
 }
 
 
+static void elemAt(EvalState & state, Value & list, int n, Value & v)
+{
+    state.forceList(list);
+    if (n < 0 || n >= list.list.length)
+        throw Error(format("list index %1% is out of bounds") % n);
+    state.forceValue(*list.list.elems[n]);
+    v = *list.list.elems[n];
+}
+
+
+/* Return the n-1'th element of a list. */
+static void prim_elemAt(EvalState & state, Value * * args, Value & v)
+{
+    elemAt(state, *args[0], state.forceInt(*args[1]), v);
+}
+
+
 /* Return the first element of a list. */
 static void prim_head(EvalState & state, Value * * args, Value & v)
 {
-    state.forceList(*args[0]);
-    if (args[0]->list.length == 0)
-        throw Error("`head' called on an empty list");
-    state.forceValue(*args[0]->list.elems[0]);
-    v = *args[0]->list.elems[0];
+    elemAt(state, *args[0], 0, v);
 }
 
 
 /* Return a list consisting of everything but the the first element of
-   a list. */
+   a list.  Warning: this function takes O(n) time, so you probably
+   don't want to use it!  */
 static void prim_tail(EvalState & state, Value * * args, Value & v)
 {
     state.forceList(*args[0]);
@@ -911,6 +926,52 @@ static void prim_map(EvalState & state, Value * * args, Value & v)
 }
 
 
+/* Filter a list using a predicate; that is, return a list containing
+   every element from the list for which the predicate function
+   returns true. */
+static void prim_filter(EvalState & state, Value * * args, Value & v)
+{
+    state.forceFunction(*args[0]);
+    state.forceList(*args[1]);
+
+    // FIXME: putting this on the stack is risky.
+    Value * vs[args[1]->list.length];
+    unsigned int k = 0;
+
+    for (unsigned int n = 0; n < args[1]->list.length; ++n) {
+        Value res;
+        state.callFunction(*args[0], *args[1]->list.elems[n], res);
+        if (state.forceBool(res))
+            vs[k++] = args[1]->list.elems[n];
+    }
+
+    state.mkList(v, k);
+    for (unsigned int n = 0; n < k; ++n) v.list.elems[n] = vs[n];
+}
+
+
+/* Return true if a list contains a given element. */
+static void prim_elem(EvalState & state, Value * * args, Value & v)
+{
+    bool res = false;
+    state.forceList(*args[1]);
+    for (unsigned int n = 0; n < args[1]->list.length; ++n)
+        if (state.eqValues(*args[0], *args[1]->list.elems[n])) {
+            res = true;
+            break;
+        }
+    mkBool(v, res);
+}
+
+
+/* Concatenate a list of lists. */
+static void prim_concatLists(EvalState & state, Value * * args, Value & v)
+{
+    state.forceList(*args[0]);
+    state.concatLists(v, args[0]->list.length, args[0]->list.elems);
+}
+
+
 /* Return the length of a list.  This is an O(1) time operation. */
 static void prim_length(EvalState & state, Value * * args, Value & v)
 {
@@ -1122,11 +1183,15 @@ void EvalState::createBaseEnv()
 
     // Lists
     addPrimOp("__isList", 1, prim_isList);
+    addPrimOp("__elemAt", 2, prim_elemAt);
     addPrimOp("__head", 1, prim_head);
     addPrimOp("__tail", 1, prim_tail);
     addPrimOp("map", 2, prim_map);
+    addPrimOp("__filter", 2, prim_filter);
+    addPrimOp("__elem", 2, prim_elem);
+    addPrimOp("__concatLists", 1, prim_concatLists);
     addPrimOp("__length", 1, prim_length);
-    
+
     // Integer arithmetic
     addPrimOp("__add", 2, prim_add);
     addPrimOp("__sub", 2, prim_sub);