blob: 650a739cfc745655c41c8af007c77980da3b90bd [file] [log] [blame]
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
* vim: set ts=8 sts=4 et sw=4 tw=99:
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
#include "frontend/FoldConstants.h"
#include "mozilla/FloatingPoint.h"
#include "jslibmath.h"
#include "frontend/ParseNode.h"
#include "frontend/Parser.h"
#include "vm/NumericConversions.h"
using namespace js;
using namespace js::frontend;
using mozilla::IsNaN;
using mozilla::IsNegative;
static ParseNode *
ContainsVarOrConst(ParseNode *pn)
{
if (!pn)
return NULL;
if (pn->isKind(PNK_VAR) || pn->isKind(PNK_CONST))
return pn;
switch (pn->getArity()) {
case PN_LIST:
for (ParseNode *pn2 = pn->pn_head; pn2; pn2 = pn2->pn_next) {
if (ParseNode *pnt = ContainsVarOrConst(pn2))
return pnt;
}
break;
case PN_TERNARY:
if (ParseNode *pnt = ContainsVarOrConst(pn->pn_kid1))
return pnt;
if (ParseNode *pnt = ContainsVarOrConst(pn->pn_kid2))
return pnt;
return ContainsVarOrConst(pn->pn_kid3);
case PN_BINARY:
/*
* Limit recursion if pn is a binary expression, which can't contain a
* var statement.
*/
if (!pn->isOp(JSOP_NOP))
return NULL;
if (ParseNode *pnt = ContainsVarOrConst(pn->pn_left))
return pnt;
return ContainsVarOrConst(pn->pn_right);
case PN_UNARY:
if (!pn->isOp(JSOP_NOP))
return NULL;
return ContainsVarOrConst(pn->pn_kid);
case PN_NAME:
return ContainsVarOrConst(pn->maybeExpr());
default:;
}
return NULL;
}
/*
* Fold from one constant type to another.
* XXX handles only strings and numbers for now
*/
static bool
FoldType(JSContext *cx, ParseNode *pn, ParseNodeKind kind)
{
if (!pn->isKind(kind)) {
switch (kind) {
case PNK_NUMBER:
if (pn->isKind(PNK_STRING)) {
double d;
if (!ToNumber(cx, StringValue(pn->pn_atom), &d))
return false;
pn->pn_dval = d;
pn->setKind(PNK_NUMBER);
pn->setOp(JSOP_DOUBLE);
}
break;
case PNK_STRING:
if (pn->isKind(PNK_NUMBER)) {
JSString *str = js_NumberToString<CanGC>(cx, pn->pn_dval);
if (!str)
return false;
pn->pn_atom = AtomizeString<CanGC>(cx, str);
if (!pn->pn_atom)
return false;
pn->setKind(PNK_STRING);
pn->setOp(JSOP_STRING);
}
break;
default:;
}
}
return true;
}
/*
* Fold two numeric constants. Beware that pn1 and pn2 are recycled, unless
* one of them aliases pn, so you can't safely fetch pn2->pn_next, e.g., after
* a successful call to this function.
*/
static bool
FoldBinaryNumeric(JSContext *cx, JSOp op, ParseNode *pn1, ParseNode *pn2,
ParseNode *pn)
{
double d, d2;
int32_t i, j;
JS_ASSERT(pn1->isKind(PNK_NUMBER) && pn2->isKind(PNK_NUMBER));
d = pn1->pn_dval;
d2 = pn2->pn_dval;
switch (op) {
case JSOP_LSH:
case JSOP_RSH:
i = ToInt32(d);
j = ToInt32(d2);
j &= 31;
d = (op == JSOP_LSH) ? i << j : i >> j;
break;
case JSOP_URSH:
j = ToInt32(d2);
j &= 31;
d = ToUint32(d) >> j;
break;
case JSOP_ADD:
d += d2;
break;
case JSOP_SUB:
d -= d2;
break;
case JSOP_MUL:
d *= d2;
break;
case JSOP_DIV:
if (d2 == 0) {
#if defined(XP_WIN)
/* XXX MSVC miscompiles such that (NaN == 0) */
if (IsNaN(d2))
d = js_NaN;
else
#endif
if (d == 0 || IsNaN(d))
d = js_NaN;
else if (IsNegative(d) != IsNegative(d2))
d = js_NegativeInfinity;
else
d = js_PositiveInfinity;
} else {
d /= d2;
}
break;
case JSOP_MOD:
if (d2 == 0) {
d = js_NaN;
} else {
d = js_fmod(d, d2);
}
break;
default:;
}
/* Take care to allow pn1 or pn2 to alias pn. */
pn->setKind(PNK_NUMBER);
pn->setOp(JSOP_DOUBLE);
pn->setArity(PN_NULLARY);
pn->pn_dval = d;
return true;
}
// Remove a ParseNode, **pnp, from a parse tree, putting another ParseNode,
// *pn, in its place.
//
// pnp points to a ParseNode pointer. This must be the only pointer that points
// to the parse node being replaced. The replacement, *pn, is unchanged except
// for its pn_next pointer; updating that is necessary if *pn's new parent is a
// list node.
void
ReplaceNode(ParseNode **pnp, ParseNode *pn)
{
pn->pn_next = (*pnp)->pn_next;
*pnp = pn;
}
enum Truthiness { Truthy, Falsy, Unknown };
static Truthiness
Boolish(ParseNode *pn)
{
switch (pn->getKind()) {
case PNK_NUMBER:
return (pn->pn_dval != 0 && !IsNaN(pn->pn_dval)) ? Truthy : Falsy;
case PNK_STRING:
return (pn->pn_atom->length() > 0) ? Truthy : Falsy;
case PNK_TRUE:
case PNK_FUNCTION:
case PNK_GENEXP:
return Truthy;
case PNK_FALSE:
case PNK_NULL:
return Falsy;
default:
return Unknown;
}
}
namespace js {
namespace frontend {
template <>
bool
FoldConstants<FullParseHandler>(JSContext *cx, ParseNode **pnp,
Parser<FullParseHandler> *parser,
bool inGenexpLambda, bool inCond)
{
ParseNode *pn = *pnp;
ParseNode *pn1 = NULL, *pn2 = NULL, *pn3 = NULL;
JS_CHECK_RECURSION(cx, return false);
// Don't fold constants if the code has requested "use asm" as
// constant-folding will misrepresent the source text for the purpose
// of type checking. (Also guard against entering a function containing
// "use asm", see PN_FUNC case below.)
if (parser->pc->useAsmOrInsideUseAsm() && cx->hasOption(JSOPTION_ASMJS))
return true;
switch (pn->getArity()) {
case PN_CODE:
if (pn->isKind(PNK_FUNCTION) &&
pn->pn_funbox->useAsmOrInsideUseAsm() && cx->hasOption(JSOPTION_ASMJS))
{
return true;
}
if (pn->getKind() == PNK_MODULE) {
if (!FoldConstants(cx, &pn->pn_body, parser))
return false;
} else {
// Note: pn_body is NULL for functions which are being lazily parsed.
JS_ASSERT(pn->getKind() == PNK_FUNCTION);
if (pn->pn_body) {
if (!FoldConstants(cx, &pn->pn_body, parser, pn->pn_funbox->inGenexpLambda))
return false;
}
}
break;
case PN_LIST:
{
/* Propagate inCond through logical connectives. */
bool cond = inCond && (pn->isKind(PNK_OR) || pn->isKind(PNK_AND));
/* Don't fold a parenthesized call expression. See bug 537673. */
ParseNode **listp = &pn->pn_head;
if ((pn->isKind(PNK_CALL) || pn->isKind(PNK_NEW)) && (*listp)->isInParens())
listp = &(*listp)->pn_next;
for (; *listp; listp = &(*listp)->pn_next) {
if (!FoldConstants(cx, listp, parser, inGenexpLambda, cond))
return false;
}
/* If the last node in the list was replaced, pn_tail points into the wrong node. */
pn->pn_tail = listp;
/* Save the list head in pn1 for later use. */
pn1 = pn->pn_head;
pn2 = NULL;
break;
}
case PN_TERNARY:
/* Any kid may be null (e.g. for (;;)). */
if (pn->pn_kid1) {
if (!FoldConstants(cx, &pn->pn_kid1, parser, inGenexpLambda, pn->isKind(PNK_IF)))
return false;
}
pn1 = pn->pn_kid1;
if (pn->pn_kid2) {
if (!FoldConstants(cx, &pn->pn_kid2, parser, inGenexpLambda, pn->isKind(PNK_FORHEAD)))
return false;
if (pn->isKind(PNK_FORHEAD) && pn->pn_kid2->isOp(JSOP_TRUE)) {
parser->handler.freeTree(pn->pn_kid2);
pn->pn_kid2 = NULL;
}
}
pn2 = pn->pn_kid2;
if (pn->pn_kid3) {
if (!FoldConstants(cx, &pn->pn_kid3, parser, inGenexpLambda))
return false;
}
pn3 = pn->pn_kid3;
break;
case PN_BINARY:
/* Propagate inCond through logical connectives. */
if (pn->isKind(PNK_OR) || pn->isKind(PNK_AND)) {
if (!FoldConstants(cx, &pn->pn_left, parser, inGenexpLambda, inCond))
return false;
if (!FoldConstants(cx, &pn->pn_right, parser, inGenexpLambda, inCond))
return false;
} else {
/* First kid may be null (for default case in switch). */
if (pn->pn_left) {
bool isWhile = pn->isKind(PNK_WHILE);
if (!FoldConstants(cx, &pn->pn_left, parser, inGenexpLambda, isWhile))
return false;
}
if (!FoldConstants(cx, &pn->pn_right, parser, inGenexpLambda, pn->isKind(PNK_DOWHILE)))
return false;
}
pn1 = pn->pn_left;
pn2 = pn->pn_right;
break;
case PN_UNARY:
/*
* Kludge to deal with typeof expressions: because constant folding
* can turn an expression into a name node, we have to check here,
* before folding, to see if we should throw undefined name errors.
*
* NB: We know that if pn->pn_op is JSOP_TYPEOF, pn1 will not be
* null. This assumption does not hold true for other unary
* expressions.
*/
if (pn->isOp(JSOP_TYPEOF) && !pn->pn_kid->isKind(PNK_NAME))
pn->setOp(JSOP_TYPEOFEXPR);
if (pn->pn_kid) {
if (!FoldConstants(cx, &pn->pn_kid, parser, inGenexpLambda, pn->isOp(JSOP_NOT)))
return false;
}
pn1 = pn->pn_kid;
break;
case PN_NAME:
/*
* Skip pn1 down along a chain of dotted member expressions to avoid
* excessive recursion. Our only goal here is to fold constants (if
* any) in the primary expression operand to the left of the first
* dot in the chain.
*/
if (!pn->isUsed()) {
ParseNode **lhsp = &pn->pn_expr;
while (*lhsp && (*lhsp)->isArity(PN_NAME) && !(*lhsp)->isUsed())
lhsp = &(*lhsp)->pn_expr;
if (*lhsp && !FoldConstants(cx, lhsp, parser, inGenexpLambda))
return false;
pn1 = *lhsp;
}
break;
case PN_NULLARY:
break;
}
switch (pn->getKind()) {
case PNK_IF:
if (ContainsVarOrConst(pn2) || ContainsVarOrConst(pn3))
break;
/* FALL THROUGH */
case PNK_CONDITIONAL:
/* Reduce 'if (C) T; else E' into T for true C, E for false. */
switch (pn1->getKind()) {
case PNK_NUMBER:
if (pn1->pn_dval == 0 || IsNaN(pn1->pn_dval))
pn2 = pn3;
break;
case PNK_STRING:
if (pn1->pn_atom->length() == 0)
pn2 = pn3;
break;
case PNK_TRUE:
break;
case PNK_FALSE:
case PNK_NULL:
pn2 = pn3;
break;
default:
/* Early return to dodge common code that copies pn2 to pn. */
return true;
}
#if JS_HAS_GENERATOR_EXPRS
/* Don't fold a trailing |if (0)| in a generator expression. */
if (!pn2 && inGenexpLambda)
break;
#endif
if (pn2 && !pn2->isDefn()) {
ReplaceNode(pnp, pn2);
pn = pn2;
}
if (!pn2 || (pn->isKind(PNK_SEMI) && !pn->pn_kid)) {
/*
* False condition and no else, or an empty then-statement was
* moved up over pn. Either way, make pn an empty block (not an
* empty statement, which does not decompile, even when labeled).
* NB: pn must be a PNK_IF as PNK_CONDITIONAL can never have a null
* kid or an empty statement for a child.
*/
pn->setKind(PNK_STATEMENTLIST);
pn->setArity(PN_LIST);
pn->makeEmpty();
}
if (pn3 && pn3 != pn2)
parser->handler.freeTree(pn3);
break;
case PNK_OR:
case PNK_AND:
if (inCond) {
if (pn->isArity(PN_LIST)) {
ParseNode **listp = &pn->pn_head;
JS_ASSERT(*listp == pn1);
uint32_t orig = pn->pn_count;
do {
Truthiness t = Boolish(pn1);
if (t == Unknown) {
listp = &pn1->pn_next;
continue;
}
if ((t == Truthy) == pn->isKind(PNK_OR)) {
for (pn2 = pn1->pn_next; pn2; pn2 = pn3) {
pn3 = pn2->pn_next;
parser->handler.freeTree(pn2);
--pn->pn_count;
}
pn1->pn_next = NULL;
break;
}
JS_ASSERT((t == Truthy) == pn->isKind(PNK_AND));
if (pn->pn_count == 1)
break;
*listp = pn1->pn_next;
parser->handler.freeTree(pn1);
--pn->pn_count;
} while ((pn1 = *listp) != NULL);
// We may have to change arity from LIST to BINARY.
pn1 = pn->pn_head;
if (pn->pn_count == 2) {
pn2 = pn1->pn_next;
pn1->pn_next = NULL;
JS_ASSERT(!pn2->pn_next);
pn->setArity(PN_BINARY);
pn->pn_left = pn1;
pn->pn_right = pn2;
} else if (pn->pn_count == 1) {
ReplaceNode(pnp, pn1);
pn = pn1;
} else if (orig != pn->pn_count) {
// Adjust list tail.
pn2 = pn1->pn_next;
for (; pn1; pn2 = pn1, pn1 = pn1->pn_next)
;
pn->pn_tail = &pn2->pn_next;
}
} else {
Truthiness t = Boolish(pn1);
if (t != Unknown) {
if ((t == Truthy) == pn->isKind(PNK_OR)) {
parser->handler.freeTree(pn2);
ReplaceNode(pnp, pn1);
pn = pn1;
} else {
JS_ASSERT((t == Truthy) == pn->isKind(PNK_AND));
parser->handler.freeTree(pn1);
ReplaceNode(pnp, pn2);
pn = pn2;
}
}
}
}
break;
case PNK_SUBASSIGN:
case PNK_BITORASSIGN:
case PNK_BITXORASSIGN:
case PNK_BITANDASSIGN:
case PNK_LSHASSIGN:
case PNK_RSHASSIGN:
case PNK_URSHASSIGN:
case PNK_MULASSIGN:
case PNK_DIVASSIGN:
case PNK_MODASSIGN:
/*
* Compound operators such as *= should be subject to folding, in case
* the left-hand side is constant, and so that the decompiler produces
* the same string that you get from decompiling a script or function
* compiled from that same string. += is special and so must be
* handled below.
*/
goto do_binary_op;
case PNK_ADDASSIGN:
JS_ASSERT(pn->isOp(JSOP_ADD));
/* FALL THROUGH */
case PNK_ADD:
if (pn->isArity(PN_LIST)) {
/*
* Any string literal term with all others number or string means
* this is a concatenation. If any term is not a string or number
* literal, we can't fold.
*/
JS_ASSERT(pn->pn_count > 2);
if (pn->pn_xflags & PNX_CANTFOLD)
return true;
if (pn->pn_xflags != PNX_STRCAT)
goto do_binary_op;
/* Ok, we're concatenating: convert non-string constant operands. */
size_t length = 0;
for (pn2 = pn1; pn2; pn2 = pn2->pn_next) {
if (!FoldType(cx, pn2, PNK_STRING))
return false;
/* XXX fold only if all operands convert to string */
if (!pn2->isKind(PNK_STRING))
return true;
length += pn2->pn_atom->length();
}
/* Allocate a new buffer and string descriptor for the result. */
jschar *chars = cx->pod_malloc<jschar>(length + 1);
if (!chars)
return false;
chars[length] = 0;
JSString *str = js_NewString<CanGC>(cx, chars, length);
if (!str) {
js_free(chars);
return false;
}
/* Fill the buffer, advancing chars and recycling kids as we go. */
for (pn2 = pn1; pn2; pn2 = parser->handler.freeTree(pn2)) {
JSAtom *atom = pn2->pn_atom;
size_t length2 = atom->length();
js_strncpy(chars, atom->chars(), length2);
chars += length2;
}
JS_ASSERT(*chars == 0);
/* Atomize the result string and mutate pn to refer to it. */
pn->pn_atom = AtomizeString<CanGC>(cx, str);
if (!pn->pn_atom)
return false;
pn->setKind(PNK_STRING);
pn->setOp(JSOP_STRING);
pn->setArity(PN_NULLARY);
break;
}
/* Handle a binary string concatenation. */
JS_ASSERT(pn->isArity(PN_BINARY));
if (pn1->isKind(PNK_STRING) || pn2->isKind(PNK_STRING)) {
if (!FoldType(cx, !pn1->isKind(PNK_STRING) ? pn1 : pn2, PNK_STRING))
return false;
if (!pn1->isKind(PNK_STRING) || !pn2->isKind(PNK_STRING))
return true;
RootedString left(cx, pn1->pn_atom);
RootedString right(cx, pn2->pn_atom);
RootedString str(cx, ConcatStrings<CanGC>(cx, left, right));
if (!str)
return false;
pn->pn_atom = AtomizeString<CanGC>(cx, str);
if (!pn->pn_atom)
return false;
pn->setKind(PNK_STRING);
pn->setOp(JSOP_STRING);
pn->setArity(PN_NULLARY);
parser->handler.freeTree(pn1);
parser->handler.freeTree(pn2);
break;
}
/* Can't concatenate string literals, let's try numbers. */
goto do_binary_op;
case PNK_SUB:
case PNK_STAR:
case PNK_LSH:
case PNK_RSH:
case PNK_URSH:
case PNK_DIV:
case PNK_MOD:
do_binary_op:
if (pn->isArity(PN_LIST)) {
JS_ASSERT(pn->pn_count > 2);
for (pn2 = pn1; pn2; pn2 = pn2->pn_next) {
if (!FoldType(cx, pn2, PNK_NUMBER))
return false;
}
for (pn2 = pn1; pn2; pn2 = pn2->pn_next) {
/* XXX fold only if all operands convert to number */
if (!pn2->isKind(PNK_NUMBER))
break;
}
if (!pn2) {
JSOp op = pn->getOp();
pn2 = pn1->pn_next;
pn3 = pn2->pn_next;
if (!FoldBinaryNumeric(cx, op, pn1, pn2, pn))
return false;
while ((pn2 = pn3) != NULL) {
pn3 = pn2->pn_next;
if (!FoldBinaryNumeric(cx, op, pn, pn2, pn))
return false;
}
}
} else {
JS_ASSERT(pn->isArity(PN_BINARY));
if (!FoldType(cx, pn1, PNK_NUMBER) ||
!FoldType(cx, pn2, PNK_NUMBER)) {
return false;
}
if (pn1->isKind(PNK_NUMBER) && pn2->isKind(PNK_NUMBER)) {
if (!FoldBinaryNumeric(cx, pn->getOp(), pn1, pn2, pn))
return false;
}
}
break;
case PNK_TYPEOF:
case PNK_VOID:
case PNK_NOT:
case PNK_BITNOT:
case PNK_POS:
case PNK_NEG:
if (pn1->isKind(PNK_NUMBER)) {
double d;
/* Operate on one numeric constant. */
d = pn1->pn_dval;
switch (pn->getKind()) {
case PNK_BITNOT:
d = ~ToInt32(d);
break;
case PNK_NEG:
d = -d;
break;
case PNK_POS:
break;
case PNK_NOT:
if (d == 0 || IsNaN(d)) {
pn->setKind(PNK_TRUE);
pn->setOp(JSOP_TRUE);
} else {
pn->setKind(PNK_FALSE);
pn->setOp(JSOP_FALSE);
}
pn->setArity(PN_NULLARY);
/* FALL THROUGH */
default:
/* Return early to dodge the common PNK_NUMBER code. */
return true;
}
pn->setKind(PNK_NUMBER);
pn->setOp(JSOP_DOUBLE);
pn->setArity(PN_NULLARY);
pn->pn_dval = d;
parser->handler.freeTree(pn1);
} else if (pn1->isKind(PNK_TRUE) || pn1->isKind(PNK_FALSE)) {
if (pn->isOp(JSOP_NOT)) {
ReplaceNode(pnp, pn1);
pn = pn1;
if (pn->isKind(PNK_TRUE)) {
pn->setKind(PNK_FALSE);
pn->setOp(JSOP_FALSE);
} else {
pn->setKind(PNK_TRUE);
pn->setOp(JSOP_TRUE);
}
}
}
break;
default:;
}
if (inCond) {
Truthiness t = Boolish(pn);
if (t != Unknown) {
/*
* We can turn function nodes into constant nodes here, but mutating function
* nodes is tricky --- in particular, mutating a function node that appears on
* a method list corrupts the method list. However, methods are M's in
* statements of the form 'this.foo = M;', which we never fold, so we're okay.
*/
parser->handler.prepareNodeForMutation(pn);
if (t == Truthy) {
pn->setKind(PNK_TRUE);
pn->setOp(JSOP_TRUE);
} else {
pn->setKind(PNK_FALSE);
pn->setOp(JSOP_FALSE);
}
pn->setArity(PN_NULLARY);
}
}
return true;
}
template <>
bool
FoldConstants<SyntaxParseHandler>(JSContext *cx, SyntaxParseHandler::Node *pnp,
Parser<SyntaxParseHandler> *parser,
bool inGenexpLambda, bool inCond)
{
return true;
}
} /* namespace frontend */
} /* namespace js */