Problem may in lua-parser/parser.lua:binaryOp

[hnes]

Hi Andre, there may be something not right in lua-parser/parser.lua:binaryOp:

local function binaryOp (e1, op, e2)
  if not op then
    return e1
  end

  local node = { tag = "Op", pos = e1.pos, [1] = op, [2] = e1, [3] = e2 }

  if op == "ne" then
    node[1] = "eq"
    node = unaryOp("not", node)
  elseif op == "gt" then
    node[1], node[2], node[3] = "lt", e2, e1     --<-- problem
  elseif op == "ge" then
    node[1], node[2], node[3] = "le", e2, e1     --<-- problem
  end

  return node
end

$ cat t.lua
gl_f_ct = 0

function f()
    if gl_f_ct <= 0 then
        gl_f_ct=1
        return 1000
    end
    return -1000
end

print( f("1st call") > f("2nd call") ) --> in lua-parser's ast: lt f("2nd call") f("1st call")  | wrong
gl_f_ct = 0
print( f("1st call") < f("2nd call") ) --> in lua-parser's ast: lt f("1st call") f("2nd call")  | right

$ luajit -bl t.lua
-- BYTECODE -- t.lua:3-9
0001    GGET     0   0      ; "gl_f_ct"
0002    KSHORT   1   0
0003    ISGT     0   1
0004    JMP      0 => 0009
0005    KSHORT   0   1
0006    GSET     0   0      ; "gl_f_ct"
0007    KSHORT   0 1000
0008    RET1     0   2
0009 => KSHORT   0 -1000
0010    RET1     0   2

-- BYTECODE -- t.lua:0-15
0001    KSHORT   0   0
0002    GSET     0   0      ; "gl_f_ct"
0003    FNEW     0   1      ; t.lua:3
0004    GSET     0   2      ; "f"
0005    GGET     0   3      ; "print"
0006    GGET     1   2      ; "f"
0007    KSTR     2   4      ; "1st call"   <-- right
0008    CALL     1   2   2
0009    GGET     2   2      ; "f"
0010    KSTR     3   5      ; "2nd call"   <-- right
0011    CALL     2   2   2
0012    ISLT     2   1
0013    JMP      1 => 0016
0014    KPRI     1   1
0015    JMP      2 => 0017
0016 => KPRI     1   2
0017 => CALL     0   1   2
0018    KSHORT   0   0
0019    GSET     0   0      ; "gl_f_ct"
0020    GGET     0   3      ; "print"
0021    GGET     1   2      ; "f"
0022    KSTR     2   4      ; "1st call"  <-- right
0023    CALL     1   2   2
0024    GGET     2   2      ; "f"
0025    KSTR     3   5      ; "2nd call"  <-- right
0026    CALL     2   2   2
0027    ISLT     1   2
0028    JMP      1 => 0031
0029    KPRI     1   1
0030    JMP      2 => 0032
0031 => KPRI     1   2
0032 => CALL     0   1   2
0033    RET0     0   1

$ lua parse_str.lua 'print( f("1st call") > f("2nd call") ) ; print( f("1st call") < f("2nd call") )'
{
  [tag] = Block
  [pos] = 1
  [1] = {
    [tag] = Call
    [pos] = 1
    [1] = {
      [tag] = Id
      [pos] = 1
      [1] = print
    }
    [2] = {
      [tag] = Op
      [pos] = 8
      [1] = lt
      [2] = {
        [tag] = Call
        [pos] = 24
        [1] = {
          [tag] = Id
          [pos] = 24
          [1] = f
        }
        [2] = {
          [tag] = String
          [pos] = 26
          [1] = 2nd call     <-- wrong
        }
      }
      [3] = {
        [tag] = Call
        [pos] = 8
        [1] = {
          [tag] = Id
          [pos] = 8
          [1] = f
        }
        [2] = {
          [tag] = String
          [pos] = 10
          [1] = 1st calll     <-- wrong
        }
      }
    }
  }
  [2] = {
    [tag] = Call
    [pos] = 42
    [1] = {
      [tag] = Id
      [pos] = 42
      [1] = print
    }
    [2] = {
      [tag] = Op
      [pos] = 49
      [1] = lt
      [2] = {
        [tag] = Call
        [pos] = 49
        [1] = {
          [tag] = Id
          [pos] = 49
          [1] = f
        }
        [2] = {
          [tag] = String
          [pos] = 51
          [1] = 1st calll     <-- right
        }
      }
      [3] = {
        [tag] = Call
        [pos] = 65
        [1] = {
          [tag] = Id
          [pos] = 65
          [1] = f
        }
        [2] = {
          [tag] = String
          [pos] = 67
          [1] = 2nd call    <-- right
        }
      }
    }
  }
}

I think the AST shouldn't consider too much about the constraints of latter IR phase. And there maybe two possible solutions:

1. Add 'gt' & 'ge' to the opid (which is used in PR11).

2. Use the mathematical transformation below to solve it lazily (but which would cause some more unnecessarily complexity):

( f1 > f2  ) == ( not ( f1 <= f2 ) )
( f1 >= f2  ) == ( not ( f1 < f2 ) )

Thanks a lot and all best :)

[hnes]

Sorry for that I had make a mistake. The 2nd solution is not right at all because for floating-point comparisons (x < y) is not the same as not (x >= y) in the presence of NaNs.

Proof:

#lua
Lua 5.1.4  Copyright (C) 1994-2008 Lua.org, PUC-Rio
> z = 0/0
> =z
-nan
> return z>z
false
> return z<z
false
> return z>=z
false
> return not (z>=z)
true
>

So that seems the 1st solution is the only choice after then :(

[andremm]

The function binaryOp is coded that way because the parser reproduces the same behavior of the Lua parser itself, as it is expressed by the Lua manual: A comparison a > b is translated to b < a and a >= b is translated to b <= a.

[hnes]

Hi Andre, thanks for your reply, but I still insist on my idea.

A comparison a > b is translated to b < a and a >= b is translated to b <= a.>

I approve this statement but that is not mean you could simply swap them in the AST generating phase. I think you may actually misunderstand it because this kinda AST lt transformation is fatally wrong in semantic which will lead the wrong result of computation later based on the AST tree.

For example:

$ cat t.lua
gl_f_ct = 0

function f()
    if gl_f_ct <= 0 then
        gl_f_ct=1
        return 1000
    end
    return -1000
end

print( f("1st call") > f("2nd call") ) --> in lua-parser's ast: lt f("2nd call") f("1st call")  | wrong
gl_f_ct = 0
print( f("1st call") < f("2nd call") ) --> in lua-parser's ast: lt f("1st call") f("2nd call")  | right
$ lua t.lua
true
false

But after execution in the AST lua-parser generated, it's result is:

$ lua-parser gen_ast_and_execute_it.lua t.lua
fasle
false

This kinda of error is due to the lt transformation had changed the sub-AST tree's execution order mistakenly.

[hnes]

    [2] = {
      [tag] = Op
      [pos] = 8
      [1] = lt
      [2] = {
        [tag] = Call
        [pos] = 24
        [1] = {
          [tag] = Id
          [pos] = 24
          [1] = f
        }
        [2] = {
          [tag] = String
          [pos] = 26
          [1] = 2nd call     <-- wrong
        }
      }
      [3] = {
        [tag] = Call
        [pos] = 8
        [1] = {
          [tag] = Id
          [pos] = 8
          [1] = f
        }
        [2] = {
          [tag] = String
          [pos] = 10
          [1] = 1st calll     <-- wrong
        }
      }
    }

If you only have this kinda AST tree which may had been with some lt transformation, you will never know which function should execute first without making some mistake in semantic.

[andremm]

You have a good point: we cannot assume that values are always evaluated or never have collateral effects before applying relational operators.

It looks like Metalua has the same issue, as

local mlc = require "metalua.compiler".new()

local test = [[
gl_f_ct = 0

function f()
    if gl_f_ct <= 0 then
        gl_f_ct=1
        return 1000
    end
    return -1000
end

print( f("1st call") > f("2nd call") )
gl_f_ct = 0
print( f("1st call") < f("2nd call") )
]]

local ast = mlc:src_to_ast(test)

local f = mlc:ast_to_function(ast)

f()

produces the same error.

I just pushed a commit that adds all relational operators to the AST. Can you please check whether this issue is solved?

[hnes]

Yes, Metalua does have the same issue, but it seems Metalua has no maintenance anymore for a quite long time.

Thanks Andre for your time and good patience :)

( I have checked and tested the commit and it works just as fine as it could possible being :D )

[andremm]

Thanks Andre for your time and good patience :)

Thank you for the bug report!

( I have checked and tested the commit and it works just as fine as it could > possible being :D )

Sounds great! I'm closing this issue then.