From ac1e8f40d4a5c380d68bb6f1c7cef6f1e7987c1a Mon Sep 17 00:00:00 2001 From: Eelco Dolstra Date: Tue, 13 Apr 2010 12:25:42 +0000 Subject: * Use a symbol table to represent identifiers and attribute names efficiently. The symbol table ensures that there is only one copy of each symbol, thus allowing symbols to be compared efficiently using a pointer equality test. --- src/libexpr/parser.y | 69 ++++++++++++++++++++++++++++++---------------------- 1 file changed, 40 insertions(+), 29 deletions(-) (limited to 'src/libexpr/parser.y') diff --git a/src/libexpr/parser.y b/src/libexpr/parser.y index 07bf56a1c964..c1c17e2b2648 100644 --- a/src/libexpr/parser.y +++ b/src/libexpr/parser.y @@ -37,17 +37,23 @@ namespace nix { struct ParseData { + SymbolTable & symbols; Expr * result; Path basePath; Path path; string error; + Symbol sLetBody; + ParseData(SymbolTable & symbols) + : symbols(symbols) + , sLetBody(symbols.create("")) + { }; }; -static string showAttrPath(const vector & attrPath) +static string showAttrPath(const vector & attrPath) { string s; - foreach (vector::const_iterator, i, attrPath) { + foreach (vector::const_iterator, i, attrPath) { if (!s.empty()) s += '.'; s += *i; } @@ -55,10 +61,11 @@ static string showAttrPath(const vector & attrPath) } -static void addAttr(ExprAttrs * attrs, const vector & attrPath, Expr * e, const Pos & pos) +static void addAttr(ExprAttrs * attrs, const vector & attrPath, + Expr * e, const Pos & pos) { unsigned int n = 0; - foreach (vector::const_iterator, i, attrPath) { + foreach (vector::const_iterator, i, attrPath) { n++; if (attrs->attrs[*i]) { ExprAttrs * attrs2 = dynamic_cast(attrs->attrs[*i]); @@ -243,10 +250,10 @@ void yyerror(YYLTYPE * loc, yyscan_t scanner, ParseData * data, const char * err nix::Formals * formals; nix::Formal * formal; int n; - char * id; + char * id; // !!! -> Symbol char * path; char * uri; - std::vector * ids; + std::vector * ids; std::vector * string_parts; } @@ -287,19 +294,19 @@ expr: expr_function; expr_function : ID ':' expr_function - { $$ = new ExprLambda(CUR_POS, $1, false, 0, $3); /* checkPatternVars(CUR_POS, $1); $$ = makeFunction($1, $3, CUR_POS); */ } + { $$ = new ExprLambda(CUR_POS, data->symbols.create($1), false, 0, $3); /* checkPatternVars(CUR_POS, $1); */ } | '{' formals '}' ':' expr_function - { $$ = new ExprLambda(CUR_POS, "", true, $2, $5); } + { $$ = new ExprLambda(CUR_POS, data->symbols.create(""), true, $2, $5); } | '{' formals '}' '@' ID ':' expr_function - { $$ = new ExprLambda(CUR_POS, $5, true, $2, $7); } + { $$ = new ExprLambda(CUR_POS, data->symbols.create($5), true, $2, $7); } | ID '@' '{' formals '}' ':' expr_function - { $$ = new ExprLambda(CUR_POS, $1, true, $4, $7); } + { $$ = new ExprLambda(CUR_POS, data->symbols.create($1), true, $4, $7); } | ASSERT expr ';' expr_function { $$ = new ExprAssert(CUR_POS, $2, $4); } | WITH expr ';' expr_function { $$ = new ExprWith(CUR_POS, $2, $4); } | LET binds IN expr_function - { $2->attrs[""] = $4; $2->recursive = true; $$ = new ExprSelect($2, ""); } + { $2->attrs[data->sLetBody] = $4; $2->recursive = true; $$ = new ExprSelect($2, data->sLetBody); } | expr_if ; @@ -316,7 +323,7 @@ expr_op | expr_op OR expr_op { $$ = new ExprOpOr($1, $3); } | expr_op IMPL expr_op { $$ = new ExprOpImpl($1, $3); } | expr_op UPDATE expr_op { $$ = new ExprOpUpdate($1, $3); } - | expr_op '?' ID { $$ = new ExprOpHasAttr($1, $3); } + | expr_op '?' ID { $$ = new ExprOpHasAttr($1, data->symbols.create($3)); } | expr_op '+' expr_op { vector * l = new vector; l->push_back($1); @@ -335,12 +342,12 @@ expr_app expr_select : expr_select '.' ID - { $$ = new ExprSelect($1, $3); } + { $$ = new ExprSelect($1, data->symbols.create($3)); } | expr_simple { $$ = $1; } ; expr_simple - : ID { $$ = new ExprVar($1); } + : ID { $$ = new ExprVar(data->symbols.create($1)); } | INT { $$ = new ExprInt($1); } | '"' string_parts '"' { /* For efficiency, and to simplify parse trees a bit. */ @@ -357,7 +364,7 @@ expr_simple /* Let expressions `let {..., body = ...}' are just desugared into `(rec {..., body = ...}).body'. */ | LET '{' binds '}' - { $3->recursive = true; $$ = new ExprSelect($3, "body"); } + { $3->recursive = true; $$ = new ExprSelect($3, data->symbols.create("body")); } | REC '{' binds '}' { $3->recursive = true; $$ = $3; } | '{' binds '}' @@ -381,26 +388,26 @@ binds : binds attrpath '=' expr ';' { $$ = $1; addAttr($$, *$2, $4, CUR_POS); } | binds INHERIT ids ';' { $$ = $1; - foreach (vector::iterator, i, *$3) + foreach (vector::iterator, i, *$3) $$->inherited.push_back(*i); } | binds INHERIT '(' expr ')' ids ';' { $$ = $1; /* !!! Should ensure sharing of the expression in $4. */ - foreach (vector::iterator, i, *$6) + foreach (vector::iterator, i, *$6) $$->attrs[*i] = new ExprSelect($4, *i); } | { $$ = new ExprAttrs; } ; ids - : ids ID { $$ = $1; $1->push_back($2); /* !!! dangerous */ } - | { $$ = new vector; } + : ids ID { $$ = $1; $1->push_back(data->symbols.create($2)); /* !!! dangerous */ } + | { $$ = new vector; } ; attrpath - : attrpath '.' ID { $$ = $1; $1->push_back($3); } - | ID { $$ = new vector; $$->push_back($1); } + : attrpath '.' ID { $$ = $1; $1->push_back(data->symbols.create($3)); } + | ID { $$ = new vector; $$->push_back(data->symbols.create($1)); } ; expr_list @@ -420,8 +427,8 @@ formals ; formal - : ID { $$ = new Formal($1, 0); } - | ID '?' expr { $$ = new Formal($1, $3); } + : ID { $$ = new Formal(data->symbols.create($1), 0); } + | ID '?' expr { $$ = new Formal(data->symbols.create($1), $3); } ; %% @@ -432,14 +439,17 @@ formal #include #include +#include + namespace nix { -static Expr * parse(const char * text, const Path & path, const Path & basePath) +static Expr * parse(EvalState & state, const char * text, + const Path & path, const Path & basePath) { yyscan_t scanner; - ParseData data; + ParseData data(state.symbols); data.basePath = basePath; data.path = path; @@ -460,7 +470,7 @@ static Expr * parse(const char * text, const Path & path, const Path & basePath) } -Expr * parseExprFromFile(Path path) +Expr * parseExprFromFile(EvalState & state, Path path) { assert(path[0] == '/'); @@ -481,13 +491,14 @@ Expr * parseExprFromFile(Path path) path = canonPath(path + "/default.nix"); /* Read and parse the input file. */ - return parse(readFile(path).c_str(), path, dirOf(path)); + return parse(state, readFile(path).c_str(), path, dirOf(path)); } -Expr * parseExprFromString(const string & s, const Path & basePath) +Expr * parseExprFromString(EvalState & state, + const string & s, const Path & basePath) { - return parse(s.c_str(), "(string)", basePath); + return parse(state, s.c_str(), "(string)", basePath); } -- cgit 1.4.1