Fix for right-to-left associativity of ternary operator

Signed-off-by: Patrick WEBER <patrick.weber@live.com>
Signed-off-by: Steve Bennett <steveb@workware.net.au>

3 files changed, 175 insertions, 10 deletions

diff --git a/BUGS b/BUGS
index b515fa5..b084318 100644
--- a/BUGS
+++ b/BUGS
@@ -1,8 +1,4 @@
 Known bugs
 ==========
 
-expr
-----
-
-right-to-left associativity of ?: is not 100% correct.
-1?2:0?3:4 should be 2, not 3.
+None!
diff --git a/jim.c b/jim.c
index 573656f..16b7d58 100644
--- a/jim.c
+++ b/jim.c
@@ -7806,6 +7806,164 @@ static void ExprAddOperator(Jim_Interp *interp, ExprByteCode * expr, ParseToken
     }
 }
 
+/**
+ * Returns the index of the COLON_LEFT to the left of 'right_index'
+ * taking into account nesting.
+ * 
+ * The expression *must* be well formed, thus a COLON_LEFT will always be found.
+ */
+static int ExprTernaryGetColonLeftIndex(ExprByteCode *expr, int right_index)
+{
+    int ternary_count = 1;
+
+    right_index--;
+
+    while (right_index > 1) {
+        if (expr->token[right_index].type == JIM_EXPROP_TERNARY_LEFT) {
+            ternary_count--;
+        }
+        else if (expr->token[right_index].type == JIM_EXPROP_COLON_RIGHT) {
+            ternary_count++;
+        }
+        else if (expr->token[right_index].type == JIM_EXPROP_COLON_LEFT && ternary_count == 1) {
+            return right_index;
+        }
+        right_index--;
+    }
+
+    /*notreached*/
+    return -1;
+}
+
+/**
+ * Find the left/right indices for the ternary expression to the left of 'right_index'.
+ *
+ * Returns 1 if found, and fills in *prev_right_index and *prev_left_index.
+ * Otherwise returns 0.
+ */
+static int ExprTernaryGetMoveIndices(ExprByteCode *expr, int right_index, int *prev_right_index, int *prev_left_index)
+{
+    int i = right_index - 1;
+    int ternary_count = 1;
+
+    while (i > 1) {
+        if (expr->token[i].type == JIM_EXPROP_TERNARY_LEFT) {
+            if (--ternary_count == 0 && expr->token[i - 2].type == JIM_EXPROP_COLON_RIGHT) {
+                *prev_right_index = i - 2;
+                *prev_left_index = ExprTernaryGetColonLeftIndex(expr, *prev_right_index);
+                return 1;
+            }
+        }
+        else if (expr->token[i].type == JIM_EXPROP_COLON_RIGHT) {
+            if (ternary_count == 0) {
+                return 0;
+            }
+            ternary_count++;
+        }
+        i--;
+    }
+    return 0;
+}
+
+/*
+* ExprTernaryReorderExpression description
+* ========================================
+*
+* ?: is right-to-left associative which doesn't work with the stack-based
+* expression engine. The fix is to reorder the bytecode.
+*
+* The expression:
+* 
+*    expr 1?2:0?3:4
+*
+* Has initial bytecode:
+*
+*    '1' '2' (40=TERNARY_LEFT) '2' (41=TERNARY_RIGHT) '2' (43=COLON_LEFT) '0' (44=COLON_RIGHT)
+*    '2' (40=TERNARY_LEFT) '3' (41=TERNARY_RIGHT) '2' (43=COLON_LEFT) '4' (44=COLON_RIGHT)
+*
+* The fix involves simulating this expression instead:
+*
+*    expr 1?2:(0?3:4)
+*
+* With the following bytecode:
+*
+*    '1' '2' (40=TERNARY_LEFT) '2' (41=TERNARY_RIGHT) '10' (43=COLON_LEFT) '0' '2' (40=TERNARY_LEFT)
+*    '3' (41=TERNARY_RIGHT) '2' (43=COLON_LEFT) '4' (44=COLON_RIGHT) (44=COLON_RIGHT)
+*
+* i.e. The token COLON_RIGHT at index 8 is moved towards the end of the stack, all tokens above 8
+*      are shifted down and the skip count of the token JIM_EXPROP_COLON_LEFT at index 5 is
+*      incremented by the amount tokens shifted down. The token JIM_EXPROP_COLON_RIGHT that is moved
+*      is identified as immediately preceeding a token JIM_EXPROP_TERNARY_LEFT
+*
+* ExprTernaryReorderExpression works thus as follows :
+* - start from the end of the stack
+* - while walking towards the beginning of the stack
+*     if token=JIM_EXPROP_COLON_RIGHT then
+*        find the associated token JIM_EXPROP_TERNARY_LEFT, which allows to
+*            find the associated token previous(JIM_EXPROP_COLON_RIGHT)
+*            find the associated token previous(JIM_EXPROP_LEFT_RIGHT)
+*        if all found then
+*            perform the rotation
+*            update the skip count of the token previous(JIM_EXPROP_LEFT_RIGHT)
+*        end if
+*    end if
+*
+* Note: care has to be taken for nested ternary constructs!!!
+*/
+static void ExprTernaryReorderExpression(Jim_Interp *interp, ExprByteCode *expr)
+{
+    int i;
+
+    for (i = expr->len - 1; i > 1; i--) {
+        int prev_right_index;
+        int prev_left_index;
+        int j;
+        ScriptToken tmp;
+
+        if (expr->token[i].type != JIM_EXPROP_COLON_RIGHT) {
+            continue;
+        }
+
+        /* COLON_RIGHT found: get the indexes needed to move the tokens in the stack (if any) */
+        if (ExprTernaryGetMoveIndices(expr, i, &prev_right_index, &prev_left_index) == 0) {
+            continue;
+        }
+
+        /*
+        ** rotate tokens down
+        **
+        ** +->  [i]                         : JIM_EXPROP_COLON_RIGHT
+        ** |     |                             |
+        ** |     V                             V
+        ** |   [...]                        : ...
+        ** |     |                             |
+        ** |     V                             V
+        ** |   [...]                        : ...
+        ** |     |                             |
+        ** |     V                             V
+        ** +-  [prev_right_index]           : JIM_EXPROP_COLON_RIGHT
+        */
+        tmp = expr->token[prev_right_index];
+        for (j = prev_right_index; j < i; j++) {
+            expr->token[j] = expr->token[j + 1];
+        }
+        expr->token[i] = tmp;
+
+        /* Increment the 'skip' count associated to the previous JIM_EXPROP_COLON_LEFT token
+         * 
+         * This is 'colon left increment' = i - prev_right_index
+         *
+         * [prev_left_index]      : JIM_EXPROP_LEFT_RIGHT
+         * [prev_left_index-1]    : skip_count
+         *
+         */
+        JimWideValue(expr->token[prev_left_index-1].objPtr) += (i - prev_right_index);
+
+        /* Adjust for i-- in the loop */
+        i++;
+    }
+}
+
 static ExprByteCode *ExprCreateByteCode(Jim_Interp *interp, const ParseTokenList *tokenlist)
 {
     Jim_Stack stack;
@@ -7813,6 +7971,7 @@ static ExprByteCode *ExprCreateByteCode(Jim_Interp *interp, const ParseTokenList
     int ok = 1;
     int i;
     int prevtt = JIM_TT_NONE;
+    int have_ternary = 0;
 
     /* -1 for EOL */
     int count = tokenlist->count - 1;
@@ -7823,12 +7982,18 @@ static ExprByteCode *ExprCreateByteCode(Jim_Interp *interp, const ParseTokenList
 
     Jim_InitStack(&stack);
 
-    /* Need extra bytecodes for lazy operators */
+    /* Need extra bytecodes for lazy operators.
+     * Also check for the ternary operator
+     */
     for (i = 0; i < tokenlist->count; i++) {
         ParseToken *t = &tokenlist->list[i];
 
         if (JimExprOperatorInfoByOpcode(t->type)->lazy == LAZY_OP) {
             count += 2;
+            /* Ternary is a lazy op but also needs reordering */
+            if (t->type == JIM_EXPROP_TERNARY) {
+                have_ternary = 1;
+            }
         }
     }
 
@@ -7913,7 +8078,7 @@ static ExprByteCode *ExprCreateByteCode(Jim_Interp *interp, const ParseTokenList
                         const struct Jim_ExprOperator *tt_op =
                             JimExprOperatorInfoByOpcode(tt->type);
 
-                        /* XXX: Should handle right-to-left associativity of ?: operator */
+                        /* Note that right-to-left associativity of ?: operator is handled later */
 
                         if (op->arity != 1 && tt_op->precedence >= op->precedence) {
                             ExprAddOperator(interp, expr, tt);
@@ -7942,6 +8107,10 @@ static ExprByteCode *ExprCreateByteCode(Jim_Interp *interp, const ParseTokenList
         ExprAddOperator(interp, expr, tt);
     }
 
+    if (have_ternary) {
+        ExprTernaryReorderExpression(interp, expr);
+    }
+
   err:
     /* Free the stack used for the compilation. */
     Jim_FreeStack(&stack);
diff --git a/tests/expr-old.test b/tests/expr-old.test
index 2aacf77..c5deb0e 100644
--- a/tests/expr-old.test
+++ b/tests/expr-old.test
@@ -316,12 +316,12 @@ test expr-old-19.4 {precedence checks} {expr 1||1&&0} 1
 
 test expr-old-20.1 {precedence checks} {expr 1||0?3:4} 3
 test expr-old-20.2 {precedence checks} {expr 1?0:4||1} 0
-# REVISIT: tinytcl gets the following horribly wrong
-# at least jim only gets 20.3 wrong
-# test expr-old-20.3 {precedence checks} {expr 1?2:0?3:4} 2
+test expr-old-20.3 {precedence checks} {expr 1?2:0?3:4} 2
 test expr-old-20.4 {precedence checks} {expr 0?2:0?3:4} 4
 test expr-old-20.5 {precedence checks} {expr 1?2?3:4:0} 3
 test expr-old-20.6 {precedence checks} {expr 0?2?3:4:0} 0
+test expr-old-20.7 {precedence checks} {expr 0?1?1?2:3:0?4:5:1?0?6:7:0?8:9} 7
+
 
 # Parentheses.