diff options
Diffstat (limited to 'src/op.cc')
-rw-r--r-- | src/op.cc | 589 |
1 files changed, 386 insertions, 203 deletions
@@ -1,5 +1,5 @@ /* - * Copyright (c) 2003-2010, John Wiegley. All rights reserved. + * Copyright (c) 2003-2012, John Wiegley. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are @@ -38,31 +38,41 @@ namespace ledger { -namespace { - value_t split_cons_expr(expr_t::ptr_op_t op) - { - if (op->kind == expr_t::op_t::O_CONS) { - value_t seq; - seq.push_back(expr_value(op->left())); - - expr_t::ptr_op_t next = op->right(); - while (next) { - expr_t::ptr_op_t value_op; - if (next->kind == expr_t::op_t::O_CONS) { - value_op = next->left(); - next = next->right(); - } else { - value_op = next; - next = NULL; - } - seq.push_back(expr_value(value_op)); +void intrusive_ptr_add_ref(const expr_t::op_t * op) +{ + op->acquire(); +} + +void intrusive_ptr_release(const expr_t::op_t * op) +{ + op->release(); +} + +value_t split_cons_expr(expr_t::ptr_op_t op) +{ + if (op->kind == expr_t::op_t::O_CONS) { + value_t seq; + seq.push_back(expr_value(op->left())); + + expr_t::ptr_op_t next = op->right(); + while (next) { + expr_t::ptr_op_t value_op; + if (next->kind == expr_t::op_t::O_CONS) { + value_op = next->left(); + next = next->has_right() ? next->right() : NULL; + } else { + value_op = next; + next = NULL; } - return seq; - } else { - return expr_value(op); + seq.push_back(expr_value(value_op)); } + return seq; + } else { + return expr_value(op); } +} +namespace { inline void check_type_context(scope_t& scope, value_t& result) { if (scope.type_required() && @@ -76,12 +86,31 @@ namespace { } } -expr_t::ptr_op_t expr_t::op_t::compile(scope_t& scope, const int depth) +expr_t::ptr_op_t expr_t::op_t::compile(scope_t& scope, const int depth, + scope_t * param_scope) { - if (is_ident()) { - DEBUG("expr.compile", "lookup: " << as_ident()); + scope_t * scope_ptr = &scope; + unique_ptr<scope_t> bound_scope; + expr_t::ptr_op_t result; + +#if defined(DEBUG_ON) + if (SHOW_DEBUG("expr.compile")) { + for (int i = 0; i < depth; i++) + ledger::_log_buffer << '.'; + DEBUG("expr.compile", ""); + } +#endif + + assert(kind < LAST); - if (ptr_op_t def = scope.lookup(symbol_t::FUNCTION, as_ident())) { + if (is_ident()) { + DEBUG("expr.compile", "Lookup: " << as_ident() << " in " << scope_ptr); + ptr_op_t def; + if (param_scope) + def = param_scope->lookup(symbol_t::FUNCTION, as_ident()); + if (! def) + def = scope_ptr->lookup(symbol_t::FUNCTION, as_ident()); + if (def) { // Identifier references are first looked up at the point of // definition, and then at the point of every use if they could // not be found there. @@ -91,70 +120,144 @@ expr_t::ptr_op_t expr_t::op_t::compile(scope_t& scope, const int depth) def->dump(*_log_stream, 0); } #endif // defined(DEBUG_ON) - return copy(def); + result = copy(def); } else if (left()) { - return copy(); + result = copy(); + } + else { + result = this; } - return this; } - - if (kind < TERMINALS) - return this; - - if (kind == O_DEFINE) { + else if (is_scope()) { + shared_ptr<scope_t> subscope(new symbol_scope_t(*scope_t::empty_scope)); + set_scope(subscope); + bound_scope.reset(new bind_scope_t(*scope_ptr, *subscope.get())); + scope_ptr = bound_scope.get(); + } + else if (kind < TERMINALS) { + result = this; + } + else if (kind == O_DEFINE) { switch (left()->kind) { - case IDENT: - scope.define(symbol_t::FUNCTION, left()->as_ident(), right()); + case IDENT: { + ptr_op_t node(right()->compile(*scope_ptr, depth + 1, param_scope)); + + DEBUG("expr.compile", + "Defining " << left()->as_ident() << " in " << scope_ptr); + scope_ptr->define(symbol_t::FUNCTION, left()->as_ident(), node); break; + } + case O_CALL: if (left()->left()->is_ident()) { ptr_op_t node(new op_t(op_t::O_LAMBDA)); node->set_left(left()->right()); node->set_right(right()); - scope.define(symbol_t::FUNCTION, left()->left()->as_ident(), node); - } else { - throw_(compile_error, _("Invalid function definition")); + node = node->compile(*scope_ptr, depth + 1, param_scope); + + DEBUG("expr.compile", + "Defining " << left()->left()->as_ident() << " in " << scope_ptr); + scope_ptr->define(symbol_t::FUNCTION, left()->left()->as_ident(), node); + break; } - break; + // fall through... + default: throw_(compile_error, _("Invalid function definition")); } - return wrap_value(value_t()); + result = wrap_value(NULL_VALUE); + } + else if (kind == O_LAMBDA) { + symbol_scope_t params(param_scope ? *param_scope : *scope_t::empty_scope); + + for (ptr_op_t sym = left(); + sym; + sym = sym->has_right() ? sym->right() : NULL) { + ptr_op_t varname = sym->kind == O_CONS ? sym->left() : sym; + + if (! varname->is_ident()) { + std::ostringstream buf; + varname->dump(buf, 0); + throw_(calc_error, + _("Invalid function or lambda parameter: %1") << buf.str()); + } else { + DEBUG("expr.compile", + "Defining function parameter " << varname->as_ident()); + params.define(symbol_t::FUNCTION, varname->as_ident(), + new op_t(PLUG)); + } + } + + ptr_op_t rhs(right()->compile(*scope_ptr, depth + 1, ¶ms)); + if (rhs == right()) + result = this; + else + result = copy(left(), rhs); } - ptr_op_t lhs(left()->compile(scope, depth)); - ptr_op_t rhs(kind > UNARY_OPERATORS && has_right() ? - (kind == O_LOOKUP ? right() : - right()->compile(scope, depth)) : NULL); + if (! result) { + if (! left()) + throw_(calc_error, _("Syntax error")); + + ptr_op_t lhs(left()->compile(*scope_ptr, depth + 1, param_scope)); + ptr_op_t rhs(kind > UNARY_OPERATORS && has_right() ? + (kind == O_LOOKUP ? right() : + right()->compile(*scope_ptr, depth + 1, param_scope)) : NULL); + + if (lhs == left() && (! rhs || rhs == right())) { + result = this; + } else { + ptr_op_t intermediate(copy(lhs, rhs)); + + // Reduce constants immediately if possible + if ((! lhs || lhs->is_value()) && (! rhs || rhs->is_value())) + result = wrap_value(intermediate->calc(*scope_ptr, NULL, depth + 1)); + else + result = intermediate; + } + } - if (lhs == left() && (! rhs || rhs == right())) - return this; +#if defined(DEBUG_ON) + if (SHOW_DEBUG("expr.compile")) { + for (int i = 0; i < depth; i++) + ledger::_log_buffer << '.'; + DEBUG("expr.compile", ""); + } +#endif - ptr_op_t intermediate(copy(lhs, rhs)); + return result; +} - // Reduce constants immediately if possible - if ((! lhs || lhs->is_value()) && (! rhs || rhs->is_value())) - return wrap_value(intermediate->calc(scope, NULL, depth)); +namespace { + expr_t::ptr_op_t lookup_ident(expr_t::ptr_op_t op, scope_t& scope) + { + expr_t::ptr_op_t def = op->left(); - return intermediate; + // If no definition was pre-compiled for this identifier, look it up + // in the current scope. + if (! def || def->kind == expr_t::op_t::PLUG) { + DEBUG("scope.symbols", "Looking for IDENT '" << op->as_ident() << "'"); + def = scope.lookup(symbol_t::FUNCTION, op->as_ident()); + } + if (! def) + throw_(calc_error, _("Unknown identifier '%1'") << op->as_ident()); + return def; + } } value_t expr_t::op_t::calc(scope_t& scope, ptr_op_t * locus, const int depth) { -#if defined(DEBUG_ON) - bool skip_debug = false; -#endif try { value_t result; #if defined(DEBUG_ON) - if (! skip_debug && SHOW_DEBUG("expr.calc")) { + if (SHOW_DEBUG("expr.calc")) { for (int i = 0; i < depth; i++) ledger::_log_buffer << '.'; - ledger::_log_buffer << op_context(this) << " => ..."; + ledger::_log_buffer << op_context(this) << " => ..."; DEBUG("expr.calc", ""); } #endif @@ -165,77 +268,38 @@ value_t expr_t::op_t::calc(scope_t& scope, ptr_op_t * locus, const int depth) break; case O_DEFINE: - //result = left()->calc(scope, locus, depth + 1); result = NULL_VALUE; break; - case IDENT: { - ptr_op_t definition = left(); - if (! definition) { - // If no definition was pre-compiled for this identifier, look it - // up in the current scope. - definition = scope.lookup(symbol_t::FUNCTION, as_ident()); + case IDENT: + if (ptr_op_t definition = lookup_ident(this, scope)) { + // Evaluating an identifier is the same as calling its definition + // directly + result = definition->calc(scope, locus, depth + 1); + check_type_context(scope, result); } - if (! definition) - throw_(calc_error, _("Unknown identifier '%1'") << as_ident()); - - // Evaluating an identifier is the same as calling its definition - // directly, so we create an empty call_scope_t to reflect the scope for - // this implicit call. - call_scope_t call_args(scope, locus, depth); - result = definition->compile(call_args, depth + 1) - ->calc(call_args, locus, depth + 1); - check_type_context(scope, result); break; - } case FUNCTION: { - // Evaluating a FUNCTION is the same as calling it directly; this happens - // when certain functions-that-look-like-variables (such as "amount") are - // resolved. - call_scope_t call_args(scope, locus, depth); + // Evaluating a FUNCTION is the same as calling it directly; this + // happens when certain functions-that-look-like-variables (such as + // "amount") are resolved. + call_scope_t call_args(scope, locus, depth + 1); result = as_function()(call_args); check_type_context(scope, result); -#if defined(DEBUG_ON) - skip_debug = true; -#endif break; } - case O_LAMBDA: { - call_scope_t& call_args(downcast<call_scope_t>(scope)); - std::size_t args_count(call_args.size()); - std::size_t args_index(0); - symbol_scope_t call_scope(call_args); - ptr_op_t sym(left()); - - for (; sym; sym = sym->has_right() ? sym->right() : NULL) { - ptr_op_t varname = sym; - if (sym->kind == O_CONS) - varname = sym->left(); - - if (! varname->is_ident()) { - throw_(calc_error, _("Invalid function definition")); - } - else if (args_index == args_count) { - call_scope.define(symbol_t::FUNCTION, varname->as_ident(), - wrap_value(NULL_VALUE)); - } - else { - DEBUG("expr.compile", - "Defining function parameter " << varname->as_ident()); - call_scope.define(symbol_t::FUNCTION, varname->as_ident(), - wrap_value(call_args[args_index++])); - } + case SCOPE: + assert(! is_scope_unset()); + if (is_scope_unset()) { + symbol_scope_t subscope(scope); + result = left()->calc(subscope, locus, depth + 1); + } else { + bind_scope_t bound_scope(scope, *as_scope()); + result = left()->calc(bound_scope, locus, depth + 1); } - - if (args_index < args_count) - throw_(calc_error, - _("Too few arguments in function call (saw %1)") << args_count); - - result = right()->calc(call_scope, locus, depth + 1); break; - } case O_LOOKUP: { context_scope_t context_scope(scope, value_t::SCOPE); @@ -252,43 +316,14 @@ value_t expr_t::op_t::calc(scope_t& scope, ptr_op_t * locus, const int depth) break; } - case O_CALL: { - call_scope_t call_args(scope, locus, depth); - if (has_right()) - call_args.set_args(split_cons_expr(right())); - - ptr_op_t func = left(); - const string& name(func->as_ident()); - - func = func->left(); - if (! func) - func = scope.lookup(symbol_t::FUNCTION, name); - if (! func) - throw_(calc_error, _("Calling unknown function '%1'") << name); - -#if defined(DEBUG_ON) - if (! skip_debug && SHOW_DEBUG("expr.calc")) { - for (int i = 0; i < depth; i++) - ledger::_log_buffer << '.'; - ledger::_log_buffer << " args: "; - if (call_args.args.is_sequence()) { - foreach (value_t& arg, call_args) - ledger::_log_buffer << arg << " "; - } else { - ledger::_log_buffer << call_args.args[0] << " "; - } - DEBUG("expr.calc", ""); - } -#endif - - if (func->is_function()) - result = func->as_function()(call_args); - else - result = func->calc(call_args, locus, depth + 1); - + case O_CALL: + result = calc_call(scope, locus, depth); check_type_context(scope, result); break; - } + + case O_LAMBDA: + result = expr_value(this); + break; case O_MATCH: result = (right()->calc(scope, locus, depth + 1).as_mask() @@ -358,7 +393,6 @@ value_t expr_t::op_t::calc(scope_t& scope, ptr_op_t * locus, const int depth) case O_QUERY: assert(right()); assert(right()->kind == O_COLON); - if (value_t temp = left()->calc(scope, locus, depth + 1)) result = right()->left()->calc(scope, locus, depth + 1); else @@ -370,63 +404,19 @@ value_t expr_t::op_t::calc(scope_t& scope, ptr_op_t * locus, const int depth) break; case O_CONS: - result = left()->calc(scope, locus, depth + 1); - DEBUG("op.cons", "car = " << result); - - if (has_right()) { - value_t temp; - temp.push_back(result); - - ptr_op_t next = right(); - while (next) { - ptr_op_t value_op; - if (next->kind == O_CONS) { - value_op = next->left(); - next = next->right(); - } else { - value_op = next; - next = NULL; - } - temp.push_back(value_op->calc(scope, locus, depth + 1)); - DEBUG("op.cons", "temp now = " << temp); - } - result = temp; - } + result = calc_cons(scope, locus, depth); break; - case O_SEQ: { - symbol_scope_t seq_scope(scope); - - // An O_SEQ is very similar to an O_CONS except that only the last result - // value in the series is kept. O_CONS builds up a list. - // - // Another feature of O_SEQ is that it pushes a new symbol scope onto the - // stack. - result = left()->calc(seq_scope, locus, depth + 1); - - if (has_right()) { - ptr_op_t next = right(); - while (next) { - ptr_op_t value_op; - if (next->kind == O_SEQ) { - value_op = next->left(); - next = next->right(); - } else { - value_op = next; - next = NULL; - } - result = value_op->calc(seq_scope, locus, depth + 1); - } - } + case O_SEQ: + result = calc_seq(scope, locus, depth); break; - } default: throw_(calc_error, _("Unexpected expr node '%1'") << op_context(this)); } #if defined(DEBUG_ON) - if (! skip_debug && SHOW_DEBUG("expr.calc")) { + if (SHOW_DEBUG("expr.calc")) { for (int i = 0; i < depth; i++) ledger::_log_buffer << '.'; ledger::_log_buffer << op_context(this) << " => "; @@ -446,6 +436,184 @@ value_t expr_t::op_t::calc(scope_t& scope, ptr_op_t * locus, const int depth) } namespace { + expr_t::ptr_op_t find_definition(expr_t::ptr_op_t op, scope_t& scope, + expr_t::ptr_op_t * locus, const int depth, + int recursion_depth = 0) + { + // If the object we are apply call notation to is a FUNCTION value + // or a O_LAMBDA expression, then this is the object we want to + // call. + if (op->is_function() || op->kind == expr_t::op_t::O_LAMBDA) + return op; + + if (recursion_depth > 256) + throw_(value_error, _("Function recursion_depth too deep (> 256)")); + + // If it's an identifier, look up its definition and see if it's a + // function. + if (op->is_ident()) + return find_definition(lookup_ident(op, scope), scope, + locus, depth, recursion_depth + 1); + + // Value objects might be callable if they contain an expression. + if (op->is_value()) { + value_t def(op->as_value()); + if (is_expr(def)) + return find_definition(as_expr(def), scope, locus, depth, + recursion_depth + 1); + else + throw_(value_error, _("Cannot call %1 as a function") << def.label()); + } + + // Resolve ordinary expressions. + return find_definition(expr_t::op_t::wrap_value(op->calc(scope, locus, + depth + 1)), + scope, locus, depth + 1, recursion_depth + 1); + } + + value_t call_lambda(expr_t::ptr_op_t func, scope_t& scope, + call_scope_t& call_args, expr_t::ptr_op_t * locus, + const int depth) + { + std::size_t args_index(0); + std::size_t args_count(call_args.size()); + + symbol_scope_t args_scope(*scope_t::empty_scope); + + for (expr_t::ptr_op_t sym = func->left(); + sym; + sym = sym->has_right() ? sym->right() : NULL) { + expr_t::ptr_op_t varname = + sym->kind == expr_t::op_t::O_CONS ? sym->left() : sym; + if (! varname->is_ident()) { + throw_(calc_error, _("Invalid function definition")); + } + else if (args_index == args_count) { + DEBUG("expr.calc", "Defining function argument as null: " + << varname->as_ident()); + args_scope.define(symbol_t::FUNCTION, varname->as_ident(), + expr_t::op_t::wrap_value(NULL_VALUE)); + } + else { + DEBUG("expr.calc", "Defining function argument from call_args: " + << varname->as_ident()); + args_scope.define(symbol_t::FUNCTION, varname->as_ident(), + expr_t::op_t::wrap_value(call_args[args_index++])); + } + } + + if (args_index < args_count) + throw_(calc_error, + _("Too few arguments in function call (saw %1, wanted %2)") + << args_count << args_index); + + if (func->right()->is_scope()) { + bind_scope_t outer_scope(scope, *func->right()->as_scope()); + bind_scope_t bound_scope(outer_scope, args_scope); + + return func->right()->left()->calc(bound_scope, locus, depth + 1); + } else { + return func->right()->calc(args_scope, locus, depth + 1); + } + } +} + + +value_t expr_t::op_t::call(const value_t& args, scope_t& scope, + ptr_op_t * locus, const int depth) +{ + call_scope_t call_args(scope, locus, depth + 1); + call_args.set_args(args); + + if (is_function()) + return as_function()(call_args); + else if (kind == O_LAMBDA) + return call_lambda(this, scope, call_args, locus, depth); + else + return find_definition(this, scope, locus, depth) + ->calc(call_args, locus, depth); +} + +value_t expr_t::op_t::calc_call(scope_t& scope, ptr_op_t * locus, + const int depth) +{ + ptr_op_t func = left(); + string name = func->is_ident() ? func->as_ident() : "<value expr>"; + + func = find_definition(func, scope, locus, depth); + + call_scope_t call_args(scope, locus, depth + 1); + if (has_right()) + call_args.set_args(split_cons_expr(right())); + + try { + if (func->is_function()) { + return func->as_function()(call_args); + } else { + assert(func->kind == O_LAMBDA); + return call_lambda(func, scope, call_args, locus, depth); + } + } + catch (const std::exception&) { + add_error_context(_("While calling function '%1 %2':" << name + << call_args.args)); + throw; + } +} + +value_t expr_t::op_t::calc_cons(scope_t& scope, ptr_op_t * locus, + const int depth) +{ + value_t result = left()->calc(scope, locus, depth + 1); + if (has_right()) { + value_t temp; + temp.push_back(result); + + ptr_op_t next = right(); + while (next) { + ptr_op_t value_op; + if (next->kind == O_CONS) { + value_op = next->left(); + next = next->has_right() ? next->right() : NULL; + } else { + value_op = next; + next = NULL; + } + temp.push_back(value_op->calc(scope, locus, depth + 1)); + } + result = temp; + } + return result; +} + +value_t expr_t::op_t::calc_seq(scope_t& scope, ptr_op_t * locus, + const int depth) +{ + // An O_SEQ is very similar to an O_CONS except that only the last + // result value in the series is kept. O_CONS builds up a list. + // + // Another feature of O_SEQ is that it pushes a new symbol scope onto + // the stack. We evaluate the left side here to catch any + // side-effects, such as definitions in the case of 'x = 1; x'. + value_t result = left()->calc(scope, locus, depth + 1); + if (has_right()) { + ptr_op_t next = right(); + while (next) { + ptr_op_t value_op; + if (next->kind == O_SEQ) { + value_op = next->left(); + next = next->right(); + } else { + value_op = next; + next = NULL; + } + result = value_op->calc(scope, locus, depth + 1); + } + } + return result; +} + +namespace { bool print_cons(std::ostream& out, const expr_t::const_ptr_op_t op, const expr_t::op_t::context_t& context) { @@ -476,9 +644,8 @@ namespace { if (op->has_right()) { out << "; "; - - if (op->right()->kind == expr_t::op_t::O_CONS) - found = print_cons(out, op->right(), context); + if (op->right()->kind == expr_t::op_t::O_SEQ) + found = print_seq(out, op->right(), context); else if (op->right()->print(out, context)) found = true; } @@ -515,6 +682,11 @@ bool expr_t::op_t::print(std::ostream& out, const context_t& context) const out << "<FUNCTION>"; break; + case SCOPE: + if (left() && left()->print(out, context)) + found = true; + break; + case O_NOT: out << "! "; if (left() && left()->print(out, context)) @@ -625,7 +797,6 @@ bool expr_t::op_t::print(std::ostream& out, const context_t& context) const case O_CONS: found = print_cons(out, this, context); break; - case O_SEQ: found = print_seq(out, this, context); break; @@ -713,6 +884,10 @@ void expr_t::op_t::dump(std::ostream& out, const int depth) const out << " "; switch (kind) { + case PLUG: + out << "PLUG"; + break; + case VALUE: out << "VALUE: "; as_value().dump(out); @@ -726,6 +901,14 @@ void expr_t::op_t::dump(std::ostream& out, const int depth) const out << "FUNCTION"; break; + case SCOPE: + out << "SCOPE: "; + if (is_scope_unset()) + out << "null"; + else + out << as_scope().get(); + break; + case O_DEFINE: out << "O_DEFINE"; break; case O_LOOKUP: out << "O_LOOKUP"; break; case O_LAMBDA: out << "O_LAMBDA"; break; @@ -765,7 +948,7 @@ void expr_t::op_t::dump(std::ostream& out, const int depth) const // An identifier is a special non-terminal, in that its left() can // hold the compiled definition of the identifier. - if (kind > TERMINALS || is_ident()) { + if (kind > TERMINALS || is_scope() || is_ident()) { if (left()) { left()->dump(out, depth + 1); if (kind > UNARY_OPERATORS && has_right()) |