nix search: Add a cache

The package list is now cached in
~/.cache/nix/package-search.json. This gives a substantial speedup to
"nix search" queries. For example (on an SSD):

First run: (no package search cache, cold page cache)

  $ time nix search blender
  Attribute name: nixpkgs.blender
  Package name: blender
  Version: 2.78c
  Description: 3D Creation/Animation/Publishing System

  real    0m6.516s

Second run: (package search cache populated)

  $ time nix search blender
  Attribute name: nixpkgs.blender
  Package name: blender
  Version: 2.78c
  Description: 3D Creation/Animation/Publishing System

  real    0m0.143s

3 files changed, 92 insertions, 20 deletions

diff --git a/src/libutil/json.cc b/src/libutil/json.cc
index b8b8ef9c8cca..813b257016e4 100644
--- a/src/libutil/json.cc
+++ b/src/libutil/json.cc
@@ -50,20 +50,22 @@ template<> void toJSON<std::nullptr_t>(std::ostream & str, const std::nullptr_t
 JSONWriter::JSONWriter(std::ostream & str, bool indent)
     : state(new JSONState(str, indent))
 {
-    state->stack.push_back(this);
+    state->stack++;
 }
 
 JSONWriter::JSONWriter(JSONState * state)
     : state(state)
 {
-    state->stack.push_back(this);
+    state->stack++;
 }
 
 JSONWriter::~JSONWriter()
 {
-    assertActive();
-    state->stack.pop_back();
-    if (state->stack.empty()) delete state;
+    if (state) {
+        assertActive();
+        state->stack--;
+        if (state->stack == 0) delete state;
+    }
 }
 
 void JSONWriter::comma()
@@ -121,9 +123,11 @@ void JSONObject::open()
 
 JSONObject::~JSONObject()
 {
-    state->depth--;
-    if (state->indent && !first) indent();
-    state->str << "}";
+    if (state) {
+        state->depth--;
+        if (state->indent && !first) indent();
+        state->str << "}";
+    }
 }
 
 void JSONObject::attr(const std::string & s)
diff --git a/src/libutil/json.hh b/src/libutil/json.hh
index 595e9bbe3491..02a39917fb5c 100644
--- a/src/libutil/json.hh
+++ b/src/libutil/json.hh
@@ -21,11 +21,11 @@ protected:
         std::ostream & str;
         bool indent;
         size_t depth = 0;
-        std::vector<JSONWriter *> stack;
+        size_t stack = 0;
         JSONState(std::ostream & str, bool indent) : str(str), indent(indent) { }
         ~JSONState()
         {
-            assert(stack.empty());
+            assert(stack == 0);
         }
     };
 
@@ -41,7 +41,7 @@ protected:
 
     void assertActive()
     {
-        assert(!state->stack.empty() && state->stack.back() == this);
+        assert(state->stack != 0);
     }
 
     void comma();
@@ -117,6 +117,14 @@ public:
         open();
     }
 
+    JSONObject(const JSONObject & obj) = delete;
+
+    JSONObject(JSONObject && obj)
+        : JSONWriter(obj.state)
+    {
+        obj.state = 0;
+    }
+
     ~JSONObject();
 
     template<typename T>
diff --git a/src/nix/search.cc b/src/nix/search.cc
index 970dcb9834b9..d3e018876a09 100644
--- a/src/nix/search.cc
+++ b/src/nix/search.cc
@@ -6,8 +6,10 @@
 #include "get-drvs.hh"
 #include "common-args.hh"
 #include "json.hh"
+#include "json-to-value.hh"
 
 #include <regex>
+#include <fstream>
 
 using namespace nix;
 
@@ -25,9 +27,23 @@ struct CmdSearch : SourceExprCommand, MixJSON
 {
     std::string re;
 
+    bool writeCache = true;
+    bool useCache = true;
+
     CmdSearch()
     {
         expectArg("regex", &re, true);
+
+        mkFlag()
+            .longName("update-cache")
+            .shortName('u')
+            .description("update the package search cache")
+            .handler([&](Strings ss) { writeCache = true; useCache = false; });
+
+        mkFlag()
+            .longName("no-cache")
+            .description("do not use or update the package search cache")
+            .handler([&](Strings ss) { writeCache = false; useCache = false; });
     }
 
     std::string name() override
@@ -48,15 +64,18 @@ struct CmdSearch : SourceExprCommand, MixJSON
 
         auto state = getEvalState();
 
-        std::function<void(Value *, std::string, bool)> doExpr;
-
         bool first = true;
 
         auto jsonOut = json ? std::make_unique<JSONObject>(std::cout, true) : nullptr;
 
         auto sToplevel = state->symbols.create("_toplevel");
+        auto sRecurse = state->symbols.create("recurseForDerivations");
+
+        bool fromCache = false;
 
-        doExpr = [&](Value * v, std::string attrPath, bool toplevel) {
+        std::function<void(Value *, std::string, bool, JSONObject *)> doExpr;
+
+        doExpr = [&](Value * v, std::string attrPath, bool toplevel, JSONObject * cache) {
             debug("at attribute ‘%s’", attrPath);
 
             try {
@@ -115,23 +134,41 @@ struct CmdSearch : SourceExprCommand, MixJSON
                                 hilite(description, descriptionMatch));
                         }
                     }
+
+                    if (cache) {
+                        cache->attr("type", "derivation");
+                        cache->attr("name", drv.queryName());
+                        cache->attr("system", drv.querySystem());
+                        if (description != "") {
+                            auto meta(cache->object("meta"));
+                            meta.attr("description", description);
+                        }
+                    }
                 }
 
                 else if (v->type == tAttrs) {
 
                     if (!toplevel) {
                         auto attrs = v->attrs;
-                        Bindings::iterator j = attrs->find(state->symbols.create("recurseForDerivations"));
-                        if (j == attrs->end() || !state->forceBool(*j->value, *j->pos)) return;
+                        Bindings::iterator j = attrs->find(sRecurse);
+                        if (j == attrs->end() || !state->forceBool(*j->value, *j->pos)) {
+                            debug("skip attribute ‘%s’", attrPath);
+                            return;
+                        }
                     }
 
-                    Bindings::iterator j = v->attrs->find(sToplevel);
-                    bool toplevel2 = j != v->attrs->end() && state->forceBool(*j->value, *j->pos);
+                    bool toplevel2 = false;
+                    if (!fromCache) {
+                        Bindings::iterator j = v->attrs->find(sToplevel);
+                        toplevel2 = j != v->attrs->end() && state->forceBool(*j->value, *j->pos);
+                    }
 
                     for (auto & i : *v->attrs) {
+                        auto cache2 =
+                            cache ? std::make_unique<JSONObject>(cache->object(i.name)) : nullptr;
                         doExpr(i.value,
                             attrPath == "" ? (std::string) i.name : attrPath + "." + (std::string) i.name,
-                            toplevel2);
+                            toplevel2 || fromCache, cache2 ? cache2.get() : nullptr);
                     }
                 }
 
@@ -144,7 +181,30 @@ struct CmdSearch : SourceExprCommand, MixJSON
             }
         };
 
-        doExpr(getSourceExpr(*state), "", true);
+        Path jsonCacheFileName = getCacheDir() + "/nix/package-search.json";
+
+        if (useCache && pathExists(jsonCacheFileName)) {
+
+            Value vRoot;
+            parseJSON(*state, readFile(jsonCacheFileName), vRoot);
+
+            fromCache = true;
+
+            doExpr(&vRoot, "", true, nullptr);
+        }
+
+        else {
+            Path tmpFile = fmt("%s.tmp.%d", jsonCacheFileName, getpid());
+
+            std::ofstream jsonCacheFile(tmpFile);
+
+            auto cache = writeCache ? std::make_unique<JSONObject>(jsonCacheFile, false) : nullptr;
+
+            doExpr(getSourceExpr(*state), "", true, cache.get());
+
+            if (rename(tmpFile.c_str(), jsonCacheFileName.c_str()) == -1)
+                throw SysError("cannot rename ‘%s’ to ‘%s’", tmpFile, jsonCacheFileName);
+        }
     }
 };