Closed Bug 1135708 Opened 9 years ago Closed 9 years ago

Implement exponentiation operator (ES7 proposal)

Categories

(Core :: JavaScript Engine, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla42
Tracking Status
firefox42 --- fixed

People

(Reporter: rwaldron, Assigned: mkierski)

References

Details

(Keywords: dev-doc-complete, Whiteboard: [DocArea=JS])

Attachments

(2 files, 1 obsolete file)

Proposal: https://github.com/rwaldron/exponentiation-operator
Tracking: https://github.com/tc39/ecma262

Status: 

- Currently accepted at Stage 0
- Available in: 
  - Traceur
  - Babel
Blocks: es7
Keywords: dev-doc-needed
OS: Mac OS X → All
Hardware: x86 → All
Whiteboard: [DocArea=JS]
Getting this basically working is 50 lines of code; that much was a fun quick hack:

    js> two = 2
    2
    js> four = 4
    4
    js> two**four
    16
    js> (two + 1)**four
    81
    js> (1 + 1/1e9) ** 1e9
    2.7182820308145095

But it can't land this way, because I cheated: it's parsing it as left-associative (which happens to be easier the way our parser is currently written). This is wrong. The spec is that ** is right-associative.

Also remaining to do: jit support. Which also seems like it should be fairly quick, but who knows.

Adding asm.js support will require a handful of decisions (like whether to permit float**int) that I'm content to leave to those who know it best.
oh yeah and tests
Assignee: nobody → jorendorff
Status: NEW → ASSIGNED
This work-in-progress patch goes on top of my Reflect patches, forthcoming in bug 987514.

Notes for Mariusz:

1.  This needs tests. See js/src/tests/README.txt.

    The functionality shares the implementation of the existing function Math.pow(). So
    extensive numerical tests won't be valuable. Don't waste your time.

    Instead, focus on testing other aspects of behavior:

    *   operator precedence is correct: a**b/c**d => (a**b)/(c**d)
    *   associativity is correct: a**b**c**d => a**(b**(c**d))
    *   still correct when there are extra parentheses, as in (a**b)**c vs. a**(b**c)
    *   the **= assignment operator works
    *   two stars separated by a space (* *) do not count as a ** operator
    *   (**) is never confused with comments, as in a**/**b**/c/**/**/**d**/e
    *   Constant-folding works. (The bytecode compiler produces exactly the same bytecode
        for `3**4` as for `81`, doing the computation at compile time rather than runtime
        since both operands are constants.)
    *   The JITs work. (Each JIT is a completely separate implementation of certain parts of
        the language! Ask Eric for help testing them.)
    *   Reflect.parse('a**b') works and generates a correct tree. (See 
        <https://developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey/Parser_API>
        for more about Reflect.parse.)

2.  I left a silly bug in this patch for you to discover and fix. (That's in addition to any
    unintentional ones.) A good test suite will detect it.

3.  Implementation note:

    The JS parser does not represent `a + b + c + d` as a tree of binary parse nodes,
    like `(+ (+ (+ a b) c) d)`, to use Lisp notation. Instead it creates a single
    linked-list node, `(+ a b c d)`. We originally did this to avoid stack overflow
    when compiling very long addition chains.

    But it means the parser just *ignores* operator associativity.

    Therefore we can parse (**) just like the other arithmetic and relational operators:
        + - * / > >= < <= == === != !== instanceof >>> >> <<
    even though all those are left-associative.

    (Assignment is right-associative; but unlike the above operators we *do* represent
    assignment using binary-tree ParseNodes, and assignment is parsed separately.)

    The downside is that all code that uses (**) ParseNodes must know that you have to
    walk them just a bit differently from all other ParseNodes. The differences are not
    just inherent in the structure of the parse tree. This explains most of the "tricky
    parts" in the patch. I had to look at every place where ParseNodes are used.

    How do I know that I found them all? I used grep a lot. This is not great! Ideally,
    we prefer code that's "obviously correct", right? So maybe my patch is stupid. If you
    want to reimplement it a different way, go for it! If not, I think this approach is
    good enough to land. Some extra comments might help, though.
Assignee: jorendorff → mkierski
Attachment #8631184 - Flags: review?(efaustbmo)
Comment on attachment 8631184 [details] [diff] [review]
Fix for Reflect.parse AST generation

Review of attachment 8631184 [details] [diff] [review]:
-----------------------------------------------------------------

OK, good news and bad news.

The good news is: This looks much much much better than my first patch as an intern. The code quality is good, and, apart from little stylistic things, ready to land. The tests are mostly complete and thoughtful, as well.

The bad news is: This patch is still incomplete. While we took care of the Baseline stubs, and all the tests will pass, it will be significantly slower to use ** instead of Math.pow, and that's silly. We need to implement JSOP_POW in Ion. The good news is, this work is already mostly done, and it shouldn't be that bad to do, I don't think. I would take a look at MCallOptimize.cpp in js/src/jit/ to see how we inline calls to math_pow, and try to refactor or leverage that code to implement JSOP_POW. I will be there to help you if things get confusing. Ion is a big and sometimes scary place.

Cancelling review for now, pending the Ion work, but adding an enthusiastic f+!

::: js/src/builtin/ReflectParse.cpp
@@ +2797,5 @@
> +{
> +    MOZ_ASSERT(pn->isArity(PN_LIST));
> +    MOZ_ASSERT(pn->pn_count >= 1);
> +
> +    // first we need to reverse the list...

Please enhance this comment to include that it's OK to destructively modify the list, because there are no other consumers. Also, as a general rule, SM comments are complete sentences, properly capitalized, with a period at the end.

@@ +2804,5 @@
> +    ParseNode* prev = nullptr;
> +    ParseNode* current = head;
> +    ParseNode* next;
> +    while (current != nullptr)
> +    {

nit: put this brace on the same line as the while and condition

@@ +2806,5 @@
> +    ParseNode* next;
> +    while (current != nullptr)
> +    {
> +        next = current->pn_next;  
> +        current->pn_next = prev;   

nit:trailing whitespace on this and the previous line.

::: js/src/jit/BaselineIC.cpp
@@ +2007,5 @@
>          return true;
>      }
>  
>      // Handle only int32 or double.
> +    if (!lhs.isNumber() || !rhs.isNumber() && op != JSOP_POW) {

Even though I wrote this, it's not quite right, yet. It yields a compile time warning. Please parenthesize appropriately.

@@ +2023,5 @@
>            case JSOP_ADD:
>            case JSOP_SUB:
>            case JSOP_MUL:
>            case JSOP_DIV:
> +          case JSOP_MOD: {

I think there's another one with a "// ???" somewhere? If so, we should also remove that.

::: js/src/tests/ecma_7/Math/Pow.js
@@ +26,5 @@
> +
> +// With parentheses
> +assertEq((2 ** 3) ** 2, 64);
> +assertEq(2 ** (3 ** 2), 512);
> +assertEq(2 ** (3 ** 2), 512);

This line is identical to the line above. Was this intentional?

@@ +28,5 @@
> +assertEq((2 ** 3) ** 2, 64);
> +assertEq(2 ** (3 ** 2), 512);
> +assertEq(2 ** (3 ** 2), 512);
> +
> +// this is to test the baseline and ION

no need for "the" in the comment. This block should also include tests of the assignment operator.

@@ +49,5 @@
> +// Two stars separated should not parse as exp operator
> +assertThrows(function() { return Reflect.parse("2 * * 3"); }, SyntaxError);
> +
> +// Check if error propagation works
> +__defineGetter__("thrower", function() { throw new Error(); });

Cute :). I think I would prefer to do this with an object, though, as __defineGetter__ is deprecated.

var a = { get prop() { throw new Error(); } };
assertThrowsInstanceOf(function() { return a.prop ** 2; }, Error);

kind of thing.

@@ +58,5 @@
> +var convertibleToPrimitive = {
> +    valueOf: function() {
> +        throw new Error("oops");
> +    }
> +};

This is really good. Let's make sure to also test some other types. Try using NaN and "3", for example.

@@ +88,5 @@
> +function assertFalse(v) {
> +    assertEq(v, false);
> +}
> +
> +function assertThrows(f, type) {

We can replace this. There is a function already in the environment called |assertThrowsInstanceOf| that works identically. We should use that instead.

@@ +96,5 @@
> +        assertEq(e instanceof type, true);
> +    }
> +}
> +
> +function staticIncludes(o, v, f) {

This function is dead. Please remove it.
Attachment #8631184 - Flags: review?(efaustbmo) → feedback+
Attachment #8631184 - Attachment is obsolete: true
Attachment #8631350 - Flags: review?(efaustbmo)
Comment on attachment 8631350 [details] [diff] [review]
Addressed comments from review + works with Ion now

Review of attachment 8631350 [details] [diff] [review]:
-----------------------------------------------------------------

Looks great!

Flagging Jan for feedback juuust to double check on that inlineMathPow stuff. Since we wrote it together, I want another opinion :).

::: js/src/jit/IonBuilder.cpp
@@ +1604,5 @@
>        case JSOP_DIV:
>        case JSOP_MOD:
>          return jsop_binary(op);
>  
> +      case JSOP_POW: 

nit: trailing whitespace after colon

@@ +4551,5 @@
>  bool
> +IonBuilder::jsop_pow() {
> +    MDefinition* exponent = current->pop();
> +    MDefinition* base = current->pop();
> +    if (inlineMathPowHelper(base, exponent, MIRType_Double) == InliningStatus_Inlined) {

Add a comment here (always put a line of whitespace before comments) that reads something like

// First, try to specialize based on type information.

@@ +4556,5 @@
> +        base->setImplicitlyUsedUnchecked();
> +        exponent->setImplicitlyUsedUnchecked();
> +        return true;
> +    }
> +    MPow* pow = MPow::New(alloc(), base, exponent, MIRType_Double);

micro-nit: I might add one line of whitespace between the closing brace and this line, with a comment:

// Barring that, we'll have to call math_pow()

::: js/src/tests/ecma_7/Math/Pow.js
@@ +75,5 @@
> +assertEq(2 ** "3", 8);
> +assertEq("2" ** 3, 8);
> +
> +// Reflect.parse generates a correct parse tree for simplest case
> +

nit: We can nestle this right against the code it describes.
Attachment #8631350 - Flags: review?(efaustbmo)
Attachment #8631350 - Flags: review+
Attachment #8631350 - Flags: feedback?(jdemooij)
Should this land as non-release-only for now, or are we sufficiently sure it'll make ES2016 (or whatever) as-is to ship it?
I'm talking with Rick about trying to advance this to Stage 3 in the next face-to-face. I'm thinking we should probably treat Stage 3 as a strong signal that things are ready to enable preffed on in release, but I'll ask what others at TC39 think.

For this particular feature, I would say it's in good enough shape you could pref it on in release anyway.

Dave
Comment on attachment 8631350 [details] [diff] [review]
Addressed comments from review + works with Ion now

Review of attachment 8631350 [details] [diff] [review]:
-----------------------------------------------------------------

Ion changes look good to me.

::: js/src/jit/BaselineIC.cpp
@@ +2040,5 @@
>              break;
>          }
>      }
>  
> +    if (lhs.isInt32() && rhs.isInt32() && op != JSOP_POW) {

File a follow-up bug to add Baseline stubs for JSOP_POW? :)

@@ +2267,5 @@
>          masm.passABIArg(FloatReg1, MoveOp::DOUBLE);
>          masm.callWithABI(JS_FUNC_TO_DATA_PTR(void*, NumberMod), MoveOp::DOUBLE);
>          MOZ_ASSERT(ReturnDoubleReg == FloatReg0);
>          break;
> +

Uber nit: remove this blank line.

::: js/src/jit/IonBuilder.cpp
@@ +4548,5 @@
>      return maybeInsertResume();
>  }
>  
>  bool
> +IonBuilder::jsop_pow() {

Nit: { should go on the next line.

@@ +4551,5 @@
>  bool
> +IonBuilder::jsop_pow() {
> +    MDefinition* exponent = current->pop();
> +    MDefinition* base = current->pop();
> +    if (inlineMathPowHelper(base, exponent, MIRType_Double) == InliningStatus_Inlined) {

Using MIRType_Double here and below is fine for now, but later it might be nice if we could do the same thing as the Math.pow inlining does: use MToInt32 if we expect an int32, so we don't unnecessarily end up using doubles elsewhere. Maybe file a follow-up bug?

::: js/src/jit/MCallOptimize.cpp
@@ +1337,5 @@
>      return InliningStatus_Inlined;
>  }
>  
>  IonBuilder::InliningStatus
> +IonBuilder::inlineMathPowHelper(MDefinition* lhs, MDefinition* rhs, MIRType outputType) {

Nit: { should go on the next line
Attachment #8631350 - Flags: feedback?(jdemooij) → feedback+
(In reply to Dave Herman [:dherman] from comment #10)
> For this particular feature, I would say it's in good enough shape you could
> pref it on in release anyway.

Agreed. Let's land it.
(In reply to Jan de Mooij [:jandem] from comment #11)
> Comment on attachment 8631350 [details] [diff] [review]
> Addressed comments from review + works with Ion now
> 
> Review of attachment 8631350 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Ion changes look good to me.
> 
> ::: js/src/jit/BaselineIC.cpp
> @@ +2040,5 @@
> >              break;
> >          }
> >      }
> >  
> > +    if (lhs.isInt32() && rhs.isInt32() && op != JSOP_POW) {
> 
> File a follow-up bug to add Baseline stubs for JSOP_POW? :)

Yep.

> @@ +4551,5 @@
> >  bool
> > +IonBuilder::jsop_pow() {
> > +    MDefinition* exponent = current->pop();
> > +    MDefinition* base = current->pop();
> > +    if (inlineMathPowHelper(base, exponent, MIRType_Double) == InliningStatus_Inlined) {
> 
> Using MIRType_Double here and below is fine for now, but later it might be
> nice if we could do the same thing as the Math.pow inlining does: use
> MToInt32 if we expect an int32, so we don't unnecessarily end up using
> doubles elsewhere. Maybe file a follow-up bug?
> 

Shouldn't this be the same bug as adding the BC caches? The arithmetic ops aren't JOF_TYPESET, so the way we get the return type for them is via the BaselineInspector. Since we don't have baseline stubs, we can't get a type, right? I agree that making it always a double is unsavory, but it's the only safe thing to do, barring other information, I think.
Flags: needinfo?(jdemooij)
(In reply to Eric Faust [:efaust] from comment #13)
> Since we don't have baseline stubs, we can't get a type,
> right? I agree that making it always a double is unsavory, but it's the only
> safe thing to do, barring other information, I think.

There's this code in DoBinaryArithFallback:

    if (ret.isDouble())
        stub->setSawDoubleResult();

So presumably you could check that flag (via the BaselineInspector) and use MIRType_Double only in that case. But we can also wait until we have Baseline stubs and check these stubs for int32/double, I don't have a strong opinion.
Flags: needinfo?(jdemooij)
I think we should make this Nightly only.
Looks like this stuck. Clearing ni? from Mariusz
Flags: needinfo?(mkierski)
https://hg.mozilla.org/mozilla-central/rev/c0d0135b9860
Status: ASSIGNED → RESOLVED
Closed: 9 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla42
Depends on: 1198453
You need to log in before you can comment on or make changes to this bug.