Correct for loop behavior with break statement #266

bjones1 · 2021-09-15T16:00:34Z

This PR makes two more tests (12.6.3_A15, 12.14_A11_T3) pass by fixing the for loop implementation in the JS to Python translator. It also improves the test framework by running more tests and producing a diff between the previous and current test runs.

Before this PR, code like this (from test 12.6.3_A15) produces incorrect results:

for(var i=0;i<10;i++){
  i*=2;
  break;	
}

Current output: i === 1, since the current implementation always runs the update statement (i++) after a break. The result should be i = 0.

Here's the diff output from the improved tests, showing that the previous run (existing code) has two more failures than the code in this PR.

PiotrDabkowski · 2021-09-15T20:20:12Z

Thanks a lot, the test diff is really cool! I need to integrate it with Github Actions as Travis stopped being free for public repos recently :(

Thanks a lot for the fix as well, it does work in this case and I think the bug being fixed is quite important.

A huge complication for translation is the label statement, consider the following:

a:for (i=0;i<10;i++) {
 continue a;
}

There is no obvious way to map it to python. It is easy to implement in the VM, but for translation I came up with a messy "solution" using exceptions:

class JS_CONTINUE_LABEL_61(Exception): pass
class JS_BREAK_LABEL_61(Exception): pass
try:
    #for JS loop
    var.put('i', Js(0.0))
    while (var.get('i')<Js(10.0)):
        try:
            try:
                raise JS_CONTINUE_LABEL_61("Continued")
            finally:
                    (var.put('i',Js(var.get('i').to_number())+Js(1))-Js(1))
        except JS_CONTINUE_LABEL_61:
            pass
except JS_BREAK_LABEL_61:
    pass

After the PR it will be converted to:

class JS_CONTINUE_LABEL_61(Exception): pass
class JS_BREAK_LABEL_61(Exception): pass
try:
    #for JS loop
    var.put('i', Js(0.0))
    while (var.get('i')<Js(10.0)):
        try:
            raise JS_CONTINUE_LABEL_61("Continued")
            (var.put('i',Js(var.get('i').to_number())+Js(1))-Js(1))
        except JS_CONTINUE_LABEL_61:
            pass
except JS_BREAK_LABEL_61:
    pass

and will result in the infinite loop. The test suite seems to have not caught this unfortunately, despite it being pretty comprehensive.

This is indeed a puzzle how to fix it properly :) The update needs to be executed on continue, but not on break. There are also things like:

a:for (i=0;i<10;i++) {
  b:for (j=0;j<10;j++) {
    continue a;
  }
}

where i should be 10 and j should be 0 at the end of the loop (js2py gets j wrong with 1).

I will try to think of some solution, but maybe you have some ideas :)

4144 · 2021-09-15T22:55:49Z

for github actions see this pr #257
and fix for for loops, not sure fix for same issue or other.

bjones1 · 2021-09-16T00:47:26Z

Here's my ideas, partly inspired by @4144's use of a variable to skip the for loop update in his PR. Does this make sense?

# This approach requires the compiler to walk the AST upwards to determine
# if the current loop is inside another loop. If so, then it must generate
# additional code in the loop conclusion.
#
# This same basic approach should work for ``while`` and ``do-while`` loops
# as well.
#
# a:for (i=0;i<10;i++) {
#   continue a;
# }
#
# Preable for every function
loop_label_sets = []
# Translation of ``a:for (i=0;i<10;i++) {``.
# For loop preamble:
continue_label = None
break_label = None
perform_for_update = True
loop_label_sets.append(set("a"))
try:
    # For loop init:
    i = 0
    # For loop test:
    while i<10:
        try:
            # Inner for loop body.
            #
            # Translation of ``continue a;``.
            continue_label = "a"
            if continue_label in loop_label_sets[-1]:
                # The continue should take place here.
                continue_label = None
                continue
            else:
                # The continue label wasn't in this loop. Break out to look for it
                # in the enclosing loop.
                perform_for_update = False
                break
        finally:
            # For loop update:
            if perform_for_update:
                i += 1
            perform_for_update = True
# For loop conclusion:
finally:
    loop_label_sets.pop()

print(i)



# a:for (i=0;i<10;i++) {
#   b:for (j=0;j<10;j++) {
#     continue a;
#   }
# }

# Preable for every function
loop_label_sets = []
# Translation of ``a:for (i=0;i<10;i++) {``.
# Outer for loop preamble:
continue_label = None
break_label = None
perform_for_update = True
loop_label_sets.append(set("a"))
try:
    # Outer for loop init:
    i = 0
    # Outer for loop test:
    while i<10:
        try:
            # Outer for loop body
            #
            # Translation of ``b:for (j=0;j<10;j++) {``.
            # Inner loop preable:
            continue_label = None
            break_label = None
            perform_for_update = True
            loop_label_sets.append(set("b"))
            try:
                # Inner for loop init:
                j = 0
                # Inner for loop test:
                while j<10:
                    try:
                        # Inner for loop body.
                        #
                        # Translation of ``// break a;``. To translate
                        # ``// break;``, omit the next line.
                        #break_label = "a"
                        #if break_label in loop_label_sets[-1]:
                            #break_label = None
                        #perform_for_update = False
                        #break

                        # Translation of ``continue a;``. To translate
                        # ``continue;``, replace the following lines with
                        # ``continue``.
                        continue_label = "a"
                        if continue_label in loop_label_sets[-1]:
                            # The continue should take place here.
                            continue_label = None
                            continue
                        else:
                            # The continue label wasn't in this loop. Break out to
                            # look for it in the enclosing loop.
                            perform_for_update = False
                            break
                    finally:
                        # Inner for loop update:
                        if perform_for_update:
                            j += 1
                        perform_for_update = True
            # Inner for loop conclusion:
            finally:
                loop_label_sets.pop()
            # Handle continuation still in progress.
            if continue_label in loop_label_sets[-1]:
                continue_label = None
                continue
            elif continue_label is not None:
                # The continue label wasn't in this loop. Break out to look for it
                # in the enclosing loop.
                perform_for_update = False
                break
            # Handle breaks still in progress.
            if break_label is not None:
                perform_for_update = False
                if break_label in loop_label_sets[-1]:
                    break_label = None
                break
        finally:
            # Outer for loop update
            if perform_for_update:
                i += 1
            perform_for_update = True
# Outer for loop conclusion:
finally:
    loop_label_sets.pop()

print(i, j)

bjones1 · 2021-09-16T00:49:49Z

I'd love to see the GH actions @4144 proposed merged!

bjones1 · 2021-09-16T06:40:31Z

Oops, this code is wrong: an exception inside the loop will (because of the finally clause) incorrectly run the loop update. Here's a fixed version, which requires repeating the loop update inside the continue code.

# This approach requires the compiler to walk the AST upwards to determine
# if the current loop is inside another loop. If so, then it must generate
# additional code in the loop conclusion.
#
# This same basic approach should work for ``while`` and ``do-while`` loops
# as well.
#
# a:for (i=0;i<10;i++) {
#   continue a;
# }
#
# Preable for every function
loop_label_sets = []
# Translation of ``a:for (i=0;i<10;i++) {``.
# For loop preamble:
continue_label = None
break_label = None
loop_label_sets.append(set("a"))
try:
    # For loop init:
    i = 0
    # For loop test:
    while i<10:
        # Inner for loop body.
        #
        # Translation of ``continue a;``.
        continue_label = "a"
        if continue_label in loop_label_sets[-1]:
            # The continue should take place here.
            continue_label = None
            # For loop update:
            i += 1
            continue
        else:
            # The continue label wasn't in this loop. Break out to look for it
            # in the enclosing loop.
            break
        # For loop update:
        i += 1
# For loop conclusion:
finally:
    loop_label_sets.pop()

print(i)



# a:for (i=0;i<10;i++) {
#   b:for (j=0;j<10;j++) {
#     continue a;
#   }
# }

# Preable for every function
loop_label_sets = []
# Translation of ``a:for (i=0;i<10;i++) {``.
# Outer for loop preamble:
continue_label = None
break_label = None
loop_label_sets.append(set("a"))
try:
    # Outer for loop init:
    i = 0
    # Outer for loop test:
    while i<10:
        # Outer for loop body
        #
        # Translation of ``b:for (j=0;j<10;j++) {``.
        # Inner loop preable:
        continue_label = None
        break_label = None
        loop_label_sets.append(set("b"))
        try:
            # Inner for loop init:
            j = 0
            # Inner for loop test:
            while j<10:
                # Inner for loop body.
                #
                # Translation of ``// break a;``. To translate
                # ``// break;``, omit the next line.
                #break_label = "a"
                #if break_label in loop_label_sets[-1]:
                    #break_label = None
                #break

                # Translation of ``continue a;``. To translate
                # ``continue;``, replace the following lines with
                # ``continue``.
                continue_label = "a"
                if continue_label in loop_label_sets[-1]:
                    # The continue should take place here.
                    continue_label = None
                    # Inner for loop update:
                    j += 1
                    continue
                else:
                    # The continue label wasn't in this loop. Break out to
                    # look for it in the enclosing loop.
                    break
                # Inner for loop update:
                j += 1
        # Inner for loop conclusion:
        finally:
            loop_label_sets.pop()
        # Handle continuation still in progress.
        if continue_label in loop_label_sets[-1]:
            continue_label = None
            # Outer for loop update
            i += 1
            continue
        elif continue_label is not None:
            # The continue label wasn't in this loop. Break out to look for it
            # in the enclosing loop.
            break
        # Handle breaks still in progress.
        if break_label is not None:
            if break_label in loop_label_sets[-1]:
                break_label = None
            break
        # Outer for loop update
        i += 1
# Outer for loop conclusion:
finally:
    loop_label_sets.pop()

print(i, j)

PiotrDabkowski · 2021-09-16T11:19:49Z

Thanks! I really like the idea of repeating the update code within continue. However rather than handling labels explicitly in the translated code (eg via loop_label_sets) we can do that in the transpiler.

With this idea in mind I have managed to get the following code:

class JS_CONTINUE_LABEL_61(Exception): pass
class JS_BREAK_LABEL_61(Exception): pass
try:
    #for JS loop
    var.put('i', Js(0.0))
    while (var.get('i')<Js(10.0)):
        try:
            class JS_CONTINUE_LABEL_62(Exception): pass
            class JS_BREAK_LABEL_62(Exception): pass
            try:
                #for JS loop
                var.put('j', Js(0.0))
                while (var.get('j')<Js(10.0)):
                    try:
                        # continue update
                        (var.put('i',Js(var.get('i').to_number())+Js(1))-Js(1))
                        raise JS_CONTINUE_LABEL_61("Continued")
                        
                        # update
                        (var.put('j',Js(var.get('j').to_number())+Js(1))-Js(1))
                    except JS_CONTINUE_LABEL_62:
                        pass
            except JS_BREAK_LABEL_62:
                pass
            
            # update
            (var.put('i',Js(var.get('i').to_number())+Js(1))-Js(1))
        except JS_CONTINUE_LABEL_61:
            pass
except JS_BREAK_LABEL_61:
    pass

This one seems to work, and without labels transpiles as in your original PR:

#for JS loop
var.put('i', Js(0.0))
while (var.get('i')<Js(10.0)):
    pass
    # update
    (var.put('i',Js(var.get('i').to_number())+Js(1))-Js(1))

Let me know what you think, I have created #267

bjones1 · 2021-09-16T13:38:50Z

Wow, I like it! I'll comment in #267.

PiotrDabkowski mentioned this pull request Sep 16, 2021

Fix for loop update after break #267

Merged

bjones1 closed this Sep 17, 2021

bjones1 force-pushed the master branch from 1b0561b to 19cce6a Compare September 17, 2021 09:24

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Correct for loop behavior with break statement #266

Correct for loop behavior with break statement #266

bjones1 commented Sep 15, 2021

PiotrDabkowski commented Sep 15, 2021

4144 commented Sep 15, 2021

bjones1 commented Sep 16, 2021

bjones1 commented Sep 16, 2021

bjones1 commented Sep 16, 2021

PiotrDabkowski commented Sep 16, 2021

bjones1 commented Sep 16, 2021

Correct for loop behavior with break statement #266

Correct for loop behavior with break statement #266

Conversation

bjones1 commented Sep 15, 2021

PiotrDabkowski commented Sep 15, 2021

4144 commented Sep 15, 2021

bjones1 commented Sep 16, 2021

bjones1 commented Sep 16, 2021

bjones1 commented Sep 16, 2021

PiotrDabkowski commented Sep 16, 2021

bjones1 commented Sep 16, 2021