store Symbols in a table as well, like positions

this slightly increases the amount of memory used for any given symbol, but this
increase is more than made up for if the symbol is referenced more than once in
the EvalState that holds it. on average every symbol should be referenced at
least twice (once to introduce a binding, once to use it), so we expect no
increase in memory on average.

symbol tables are limited to 2³² entries like position tables, and similar
arguments apply to why overflow is not likely: 2³² symbols would require as many
string instances (at 24 bytes each) and map entries (at 24 bytes or more each,
assuming that the map holds on average at most one item per bucket as the docs
say). a full symbol table would require at least 192GB of memory just for
symbols, which is well out of reach. (an ofborg eval of nixpks today creates
less than a million symbols!)

6 files changed, 68 insertions, 57 deletions

diff --git a/src/nix/app.cc b/src/nix/app.cc
index df7303e15..95ac1cf5c 100644
--- a/src/nix/app.cc
+++ b/src/nix/app.cc
@@ -85,9 +85,9 @@ UnresolvedApp Installable::toApp(EvalState & state)
 
     else if (type == "derivation") {
         auto drvPath = cursor->forceDerivation();
-        auto outPath = cursor->getAttr(state.sOutPath)->getString();
-        auto outputName = cursor->getAttr(state.sOutputName)->getString();
-        auto name = cursor->getAttr(state.sName)->getString();
+        auto outPath = cursor->getAttr("outPath")->getString();
+        auto outputName = cursor->getAttr("outputName")->getString();
+        auto name = cursor->getAttr("name")->getString();
         auto aPname = cursor->maybeGetAttr("pname");
         auto aMeta = cursor->maybeGetAttr("meta");
         auto aMainProgram = aMeta ? aMeta->maybeGetAttr("mainProgram") : nullptr;
diff --git a/src/nix/eval.cc b/src/nix/eval.cc
index 81474c2d3..967dc8519 100644
--- a/src/nix/eval.cc
+++ b/src/nix/eval.cc
@@ -88,17 +88,19 @@ struct CmdEval : MixJSON, InstallableCommand
                 else if (v.type() == nAttrs) {
                     if (mkdir(path.c_str(), 0777) == -1)
                         throw SysError("creating directory '%s'", path);
-                    for (auto & attr : *v.attrs)
+                    for (auto & attr : *v.attrs) {
+                        std::string_view name = state->symbols[attr.name];
                         try {
-                            if (attr.name == "." || attr.name == "..")
-                                throw Error("invalid file name '%s'", attr.name);
-                            recurse(*attr.value, attr.pos, path + "/" + std::string(attr.name));
+                            if (name == "." || name == "..")
+                                throw Error("invalid file name '%s'", name);
+                            recurse(*attr.value, attr.pos, concatStrings(path, "/", name));
                         } catch (Error & e) {
                             e.addTrace(
                                 state->positions[attr.pos],
-                                hintfmt("while evaluating the attribute '%s'", attr.name));
+                                hintfmt("while evaluating the attribute '%s'", name));
                             throw;
                         }
+                    }
                 }
                 else
                     throw TypeError("value at '%s' is not a string or an attribute set", state->positions[pos]);
@@ -119,7 +121,7 @@ struct CmdEval : MixJSON, InstallableCommand
 
         else {
             state->forceValueDeep(*v);
-            logger->cout("%s", *v);
+            logger->cout("%s", printValue(*state, *v));
         }
     }
 };
diff --git a/src/nix/flake.cc b/src/nix/flake.cc
index 23e5cd24e..c8d8461e4 100644
--- a/src/nix/flake.cc
+++ b/src/nix/flake.cc
@@ -139,11 +139,11 @@ static void enumerateOutputs(EvalState & state, Value & vFlake,
        else. This way we can disable IFD for hydraJobs and then enable
        it for other outputs. */
     if (auto attr = aOutputs->value->attrs->get(sHydraJobs))
-        callback(attr->name, *attr->value, attr->pos);
+        callback(state.symbols[attr->name], *attr->value, attr->pos);
 
     for (auto & attr : *aOutputs->value->attrs) {
         if (attr.name != sHydraJobs)
-            callback(attr.name, *attr.value, attr.pos);
+            callback(state.symbols[attr.name], *attr.value, attr.pos);
     }
 }
 
@@ -254,14 +254,6 @@ struct CmdFlakeInfo : CmdFlakeMetadata
     }
 };
 
-static bool argHasName(std::string_view arg, std::string_view expected)
-{
-    return
-        arg == expected
-        || arg == "_"
-        || (hasPrefix(arg, "_") && arg.substr(1) == expected);
-}
-
 struct CmdFlakeCheck : FlakeCommand
 {
     bool build = true;
@@ -319,6 +311,14 @@ struct CmdFlakeCheck : FlakeCommand
             return state->positions[p];
         };
 
+        auto argHasName = [&] (SymbolIdx arg, std::string_view expected) {
+            std::string_view name = state->symbols[arg];
+            return
+                name == expected
+                || name == "_"
+                || (hasPrefix(name, "_") && name.substr(1) == expected);
+        };
+
         auto checkSystemName = [&](const std::string & system, const PosIdx pos) {
             // FIXME: what's the format of "system"?
             if (system.find('-') == std::string::npos)
@@ -390,7 +390,7 @@ struct CmdFlakeCheck : FlakeCommand
                         } catch (Error & e) {
                             e.addTrace(
                                 state->positions[attr.pos],
-                                hintfmt("while evaluating the option '%s'", attr.name));
+                                hintfmt("while evaluating the option '%s'", state->symbols[attr.name]));
                             throw;
                         }
                 } else
@@ -414,7 +414,7 @@ struct CmdFlakeCheck : FlakeCommand
 
                 for (auto & attr : *v.attrs) {
                     state->forceAttrs(*attr.value, attr.pos);
-                    auto attrPath2 = attrPath + "." + (std::string) attr.name;
+                    auto attrPath2 = concatStrings(attrPath, ".", state->symbols[attr.name]);
                     if (state->isDerivation(*attr.value)) {
                         Activity act(*logger, lvlChatty, actUnknown,
                             fmt("checking Hydra job '%s'", attrPath2));
@@ -468,7 +468,7 @@ struct CmdFlakeCheck : FlakeCommand
                     throw Error("template '%s' lacks attribute 'description'", attrPath);
 
                 for (auto & attr : *v.attrs) {
-                    std::string name(attr.name);
+                    std::string_view name(state->symbols[attr.name]);
                     if (name != "path" && name != "description" && name != "welcomeText")
                         throw Error("template '%s' has unsupported attribute '%s'", attrPath, name);
                 }
@@ -522,13 +522,14 @@ struct CmdFlakeCheck : FlakeCommand
                         if (name == "checks") {
                             state->forceAttrs(vOutput, pos);
                             for (auto & attr : *vOutput.attrs) {
-                                checkSystemName(attr.name, attr.pos);
+                                const auto & attr_name = state->symbols[attr.name];
+                                checkSystemName(attr_name, attr.pos);
                                 state->forceAttrs(*attr.value, attr.pos);
                                 for (auto & attr2 : *attr.value->attrs) {
                                     auto drvPath = checkDerivation(
-                                        fmt("%s.%s.%s", name, attr.name, attr2.name),
+                                        fmt("%s.%s.%s", name, attr_name, state->symbols[attr2.name]),
                                         *attr2.value, attr2.pos);
-                                    if (drvPath && (std::string) attr.name == settings.thisSystem.get())
+                                    if (drvPath && attr_name == settings.thisSystem.get())
                                         drvPaths.push_back(DerivedPath::Built{*drvPath});
                                 }
                             }
@@ -537,9 +538,10 @@ struct CmdFlakeCheck : FlakeCommand
                         else if (name == "formatter") {
                             state->forceAttrs(vOutput, pos);
                             for (auto & attr : *vOutput.attrs) {
-                                checkSystemName(attr.name, attr.pos);
+                                const auto & attr_name = state->symbols[attr.name];
+                                checkSystemName(attr_name, attr.pos);
                                 checkApp(
-                                    fmt("%s.%s", name, attr.name),
+                                    fmt("%s.%s", name, attr_name),
                                     *attr.value, attr.pos);
                             }
                         }
@@ -547,11 +549,12 @@ struct CmdFlakeCheck : FlakeCommand
                         else if (name == "packages" || name == "devShells") {
                             state->forceAttrs(vOutput, pos);
                             for (auto & attr : *vOutput.attrs) {
-                                checkSystemName(attr.name, attr.pos);
+                                const auto & attr_name = state->symbols[attr.name];
+                                checkSystemName(attr_name, attr.pos);
                                 state->forceAttrs(*attr.value, attr.pos);
                                 for (auto & attr2 : *attr.value->attrs)
                                     checkDerivation(
-                                        fmt("%s.%s.%s", name, attr.name, attr2.name),
+                                        fmt("%s.%s.%s", name, attr_name, state->symbols[attr2.name]),
                                         *attr2.value, attr2.pos);
                             }
                         }
@@ -559,11 +562,12 @@ struct CmdFlakeCheck : FlakeCommand
                         else if (name == "apps") {
                             state->forceAttrs(vOutput, pos);
                             for (auto & attr : *vOutput.attrs) {
-                                checkSystemName(attr.name, attr.pos);
+                                const auto & attr_name = state->symbols[attr.name];
+                                checkSystemName(attr_name, attr.pos);
                                 state->forceAttrs(*attr.value, attr.pos);
                                 for (auto & attr2 : *attr.value->attrs)
                                     checkApp(
-                                        fmt("%s.%s.%s", name, attr.name, attr2.name),
+                                        fmt("%s.%s.%s", name, attr_name, state->symbols[attr2.name]),
                                         *attr2.value, attr2.pos);
                             }
                         }
@@ -571,9 +575,10 @@ struct CmdFlakeCheck : FlakeCommand
                         else if (name == "defaultPackage" || name == "devShell") {
                             state->forceAttrs(vOutput, pos);
                             for (auto & attr : *vOutput.attrs) {
-                                checkSystemName(attr.name, attr.pos);
+                                const auto & attr_name = state->symbols[attr.name];
+                                checkSystemName(attr_name, attr.pos);
                                 checkDerivation(
-                                    fmt("%s.%s", name, attr.name),
+                                    fmt("%s.%s", name, attr_name),
                                     *attr.value, attr.pos);
                             }
                         }
@@ -581,9 +586,10 @@ struct CmdFlakeCheck : FlakeCommand
                         else if (name == "defaultApp") {
                             state->forceAttrs(vOutput, pos);
                             for (auto & attr : *vOutput.attrs) {
-                                checkSystemName(attr.name, attr.pos);
+                                const auto & attr_name = state->symbols[attr.name];
+                                checkSystemName(attr_name, attr.pos);
                                 checkApp(
-                                    fmt("%s.%s", name, attr.name),
+                                    fmt("%s.%s", name, attr_name),
                                     *attr.value, attr.pos);
                             }
                         }
@@ -591,7 +597,7 @@ struct CmdFlakeCheck : FlakeCommand
                         else if (name == "legacyPackages") {
                             state->forceAttrs(vOutput, pos);
                             for (auto & attr : *vOutput.attrs) {
-                                checkSystemName(attr.name, attr.pos);
+                                checkSystemName(state->symbols[attr.name], attr.pos);
                                 // FIXME: do getDerivations?
                             }
                         }
@@ -602,7 +608,7 @@ struct CmdFlakeCheck : FlakeCommand
                         else if (name == "overlays") {
                             state->forceAttrs(vOutput, pos);
                             for (auto & attr : *vOutput.attrs)
-                                checkOverlay(fmt("%s.%s", name, attr.name),
+                                checkOverlay(fmt("%s.%s", name, state->symbols[attr.name]),
                                     *attr.value, attr.pos);
                         }
 
@@ -612,14 +618,14 @@ struct CmdFlakeCheck : FlakeCommand
                         else if (name == "nixosModules") {
                             state->forceAttrs(vOutput, pos);
                             for (auto & attr : *vOutput.attrs)
-                                checkModule(fmt("%s.%s", name, attr.name),
+                                checkModule(fmt("%s.%s", name, state->symbols[attr.name]),
                                     *attr.value, attr.pos);
                         }
 
                         else if (name == "nixosConfigurations") {
                             state->forceAttrs(vOutput, pos);
                             for (auto & attr : *vOutput.attrs)
-                                checkNixOSConfiguration(fmt("%s.%s", name, attr.name),
+                                checkNixOSConfiguration(fmt("%s.%s", name, state->symbols[attr.name]),
                                     *attr.value, attr.pos);
                         }
 
@@ -632,16 +638,17 @@ struct CmdFlakeCheck : FlakeCommand
                         else if (name == "templates") {
                             state->forceAttrs(vOutput, pos);
                             for (auto & attr : *vOutput.attrs)
-                                checkTemplate(fmt("%s.%s", name, attr.name),
+                                checkTemplate(fmt("%s.%s", name, state->symbols[attr.name]),
                                     *attr.value, attr.pos);
                         }
 
                         else if (name == "defaultBundler") {
                             state->forceAttrs(vOutput, pos);
                             for (auto & attr : *vOutput.attrs) {
-                                checkSystemName(attr.name, attr.pos);
+                                const auto & attr_name = state->symbols[attr.name];
+                                checkSystemName(attr_name, attr.pos);
                                 checkBundler(
-                                    fmt("%s.%s", name, attr.name),
+                                    fmt("%s.%s", name, attr_name),
                                     *attr.value, attr.pos);
                             }
                         }
@@ -649,11 +656,12 @@ struct CmdFlakeCheck : FlakeCommand
                         else if (name == "bundlers") {
                             state->forceAttrs(vOutput, pos);
                             for (auto & attr : *vOutput.attrs) {
-                                checkSystemName(attr.name, attr.pos);
+                                const auto & attr_name = state->symbols[attr.name];
+                                checkSystemName(attr_name, attr.pos);
                                 state->forceAttrs(*attr.value, attr.pos);
                                 for (auto & attr2 : *attr.value->attrs) {
                                     checkBundler(
-                                        fmt("%s.%s.%s", name, attr.name, attr2.name),
+                                        fmt("%s.%s.%s", name, attr_name, state->symbols[attr2.name]),
                                         *attr2.value, attr2.pos);
                                 }
                             }
@@ -1000,7 +1008,7 @@ struct CmdFlakeShow : FlakeCommand, MixJSON
 
                 auto showDerivation = [&]()
                 {
-                    auto name = visitor.getAttr(state->sName)->getString();
+                    auto name = visitor.getAttr("name")->getString();
                     if (json) {
                         std::optional<std::string> description;
                         if (auto aMeta = visitor.maybeGetAttr("meta")) {
diff --git a/src/nix/main.cc b/src/nix/main.cc
index 6198681e7..6d0f6ce6e 100644
--- a/src/nix/main.cc
+++ b/src/nix/main.cc
@@ -302,7 +302,7 @@ void mainWrapped(int argc, char * * argv)
             b["arity"] = primOp->arity;
             b["args"] = primOp->args;
             b["doc"] = trim(stripIndentation(primOp->doc));
-            res[(std::string) builtin.name] = std::move(b);
+            res[state.symbols[builtin.name]] = std::move(b);
         }
         std::cout << res.dump() << "\n";
         return;
diff --git a/src/nix/repl.cc b/src/nix/repl.cc
index fd1b95afa..998ff7328 100644
--- a/src/nix/repl.cc
+++ b/src/nix/repl.cc
@@ -73,7 +73,7 @@ struct NixRepl
     void initEnv();
     void reloadFiles();
     void addAttrsToScope(Value & attrs);
-    void addVarToScope(const Symbol & name, Value & v);
+    void addVarToScope(const SymbolIdx name, Value & v);
     Expr * parseString(std::string s);
     void evalString(std::string s, Value & v);
 
@@ -347,9 +347,9 @@ StringSet NixRepl::completePrefix(const std::string & prefix)
             state->forceAttrs(v, noPos);
 
             for (auto & i : *v.attrs) {
-                std::string name = i.name;
+                std::string_view name = state->symbols[i.name];
                 if (name.substr(0, cur2.size()) != cur2) continue;
-                completions.insert(prev + expr + "." + name);
+                completions.insert(concatStrings(prev, expr, ".", name));
             }
 
         } catch (ParseError & e) {
@@ -464,8 +464,9 @@ bool NixRepl::processLine(std::string line)
         const auto [file, line] = [&] () -> std::pair<std::string, uint32_t> {
             if (v.type() == nPath || v.type() == nString) {
                 PathSet context;
-                auto filename = state->coerceToString(noPos, v, context);
-                return {state->symbols.create(*filename), 0};
+                auto filename = state->coerceToString(noPos, v, context).toOwned();
+                state->symbols.create(filename);
+                return {filename, 0};
             } else if (v.isLambda()) {
                 auto pos = state->positions[v.lambda.fun->pos];
                 return {pos.file, pos.line};
@@ -672,7 +673,7 @@ void NixRepl::initEnv()
 
     varNames.clear();
     for (auto & i : state->staticBaseEnv.vars)
-        varNames.insert(i.first);
+        varNames.emplace(state->symbols[i.first]);
 }
 
 
@@ -702,7 +703,7 @@ void NixRepl::addAttrsToScope(Value & attrs)
     for (auto & i : *attrs.attrs) {
         staticEnv.vars.emplace_back(i.name, displ);
         env->values[displ++] = i.value;
-        varNames.insert((std::string) i.name);
+        varNames.emplace(state->symbols[i.name]);
     }
     staticEnv.sort();
     staticEnv.deduplicate();
@@ -710,7 +711,7 @@ void NixRepl::addAttrsToScope(Value & attrs)
 }
 
 
-void NixRepl::addVarToScope(const Symbol & name, Value & v)
+void NixRepl::addVarToScope(const SymbolIdx name, Value & v)
 {
     if (displ >= envSize)
         throw Error("environment full; cannot add more variables");
@@ -719,7 +720,7 @@ void NixRepl::addVarToScope(const Symbol & name, Value & v)
     staticEnv.vars.emplace_back(name, displ);
     staticEnv.sort();
     env->values[displ++] = &v;
-    varNames.insert((std::string) name);
+    varNames.emplace(state->symbols[name]);
 }
 
 
@@ -812,7 +813,7 @@ std::ostream & NixRepl::printValue(std::ostream & str, Value & v, unsigned int m
             typedef std::map<std::string, Value *> Sorted;
             Sorted sorted;
             for (auto & i : *v.attrs)
-                sorted[i.name] = i.value;
+                sorted.emplace(state->symbols[i.name], i.value);
 
             for (auto & i : sorted) {
                 if (isVarName(i.first))
diff --git a/src/nix/search.cc b/src/nix/search.cc
index e284de95c..8b1e9ae6c 100644
--- a/src/nix/search.cc
+++ b/src/nix/search.cc
@@ -154,7 +154,7 @@ struct CmdSearch : InstallableCommand, MixJSON
                     recurse();
 
                 else if (attrPath[0] == "legacyPackages" && attrPath.size() > 2) {
-                    auto attr = cursor.maybeGetAttr(state->sRecurseForDerivations);
+                    auto attr = cursor.maybeGetAttr("recurseForDerivations");
                     if (attr && attr->getBool())
                         recurse();
                 }