Tcl Source Code

View Ticket
Login
Ticket UUID: db36fa5122259be74d0ccadd102e076094703052
Title: compiled lindex botches index artihmetic
Type: Bug Created on: 2018-03-01 18:24:04
Submitter: dgp Assigned to: dgp
Subsystem: 47. Bytecode Compiler Severity: Severe
Priority: 5 Medium Last modified: 2024-10-02 07:47:28
Status: Closed Closed by: pooryorick
Resolution: Fixed Closed on: 2024-10-02 07:47:28
Version: 8.6
Description:
% lindex {a b c} -1-1
c

Correct answer should be the empty string.

The bytecode compiler for [lindex] tries to
encode the indices "end", "end-1", .... etc.
as the immediate bytecode arguments -2, -3, ....

It ignores the possibility that TclGetIntForIndex()
can return those values as legit index values
resulting from index arithmetic.  In this example
the index "-2" is getting interpreted as if it were "end".
User Comments:
dgp added on 2018-03-01 19:10:37:
% lrange {a b c} 0-3 0-2
b c

Same fundamental cause.

traces back to:

https://core.tcl.tk/tcl/info/533a2ba7b7d13364

sebres added on 2018-03-01 23:16:44:

Same here:

% lsort -index -1-1 {{1 . c} {2 . b} {3 . a}}
{3 . a} {2 . b} {1 . c}

But still worse (I think it is similar to your fix [650f9e6c7c]):

% lsort -index -2 {{1 . c} {2 . b} {3 . a}}
{3 . a} {2 . b} {1 . c}

The main issue here is - TclGetIntForIndex can not distinguish between
end?[+-]index? and integer?[+-]integer?.
So by fixed length values like INDEX_END/SORTIDX_END it cannot be used properly.

Rather we need still one command, like TclGetIntForIndexC which will return
TCL_ERROR in case of result <= INDEX_END (usable for compiled only).
Or the byte-code of several commands should be rewritten to differentiate end?[+-]index? case.

I assume both may be needed.

I've one minimalistic fix for it as well as one own branch, where it is already correct implemented, will try to back-port it tomorrow to 8.6th.


dgp added on 2018-03-06 14:31:48:
Tcl 8.5 had two opcodes which took integer operands representing
index values determined at compile time (OPERAND_IDX4).

INST_LIST_INDEX_IMM
INST_LIST_RANGE_IMM

They agree on an encoding that the operand values

-1, 0, 1, ..., INT_MAX

stand for the same index values, while the operand values

-2, -3, ..., INT_MIN

stand for the index values

end, end-1, ... end-(INT_MIN+2)

If a command compiler encounters an index value known at
compile time that doesn't fit in these supported ranges,
it will have to emit the other instruction

INST_LIST_INDEX

or fallback to runtime invocation.

dgp added on 2018-03-06 14:41:43:
It's an unfortunate property of that encoding that it has
no room to encode useful and fairly common index values such as

end+1, end+2, ...

dgp added on 2018-03-06 14:48:22:
...although for these instructions, they can be translated
into functional equivalents with values in the supported range.

lindex $l end+1

can become

"PUSH $l"
INST_LIST_INDEX_IMM -1

because taking the value (none, empty) just before
the start of the list is functionally the same as
taking the value (none, empty) just after the end
of the list.

dgp added on 2018-03-06 14:51:03:
In the cases where we know at compile time the index
points outside the list, we might be tempted to replace
the whole thing with just

"PUSH $empty"

but that would miss out on any bytecode that
creates $l, and miss out on the check the $l
is a valid list.

dgp added on 2018-03-06 15:31:13:
In Tcl 8.5, although LIST_INDEX_IMM will accept
negative operand values, none of the compiled
commands generate them.  It's an unused facility
of the bytecode execution engine.

dgp added on 2018-03-06 15:36:13:
In Tcl 8.5 the opcode INST_LIST_RANGE_IMM is issued only
in the compilation of [lassign] to determine the return value
of the command as, effectively, [lrange $l $last+1 end].
The integer value $last+1 is an operand and "-2" is used for "end",
making use of the encoding facility.

The same effect could have been achieved with operand values
of either LIST_MAX or INT_MAX.

Conclusion: Tcl 8.5 makes little use of the index encoding, and
no necessary use.  Lots of excess unused capability in the
execution engine.

dgp added on 2018-03-06 15:39:39:
In Tcl 8.6, the new instruction INST_STR_RANGE_IMM also
makes use of index value operands (OPERAND_IDX4). It
respects the same encoding.

dgp added on 2018-03-06 15:49:00:
Tcl 8.6 also added an assembler and provides in it access to
the INST_LIST_INDEX_IMM instruction.  It botches index compiling
in the same way -- misusing TclGetIntForIndex(), like so:

% tcl::unsupported::assemble {
push {a b c};
listIndexImm end+2
}
a
% tcl::unsupported::assemble {
push {a b c};
listIndexImm -1-1
}
c

The other index-value-using instructions are not in the
instruction set of the assembler. I guess it lags.

dgp added on 2018-03-06 15:53:38:
The common fix needed for all these command compilers
is access to a TclGetEndOffsetFromObj() routine that can
detect exactly the end+/-N format the compilers need to
detect as a separate case to properly encode.  This is
not difficult.  Practically already done in the TIP 445 branch.

dgp added on 2018-03-06 17:41:26:
After reviewing the command compilers that generate these opcodes,
some of them are a true mess.

The good news is that except the assembler they all route through
a common routine TclGetIndexFromToken to parse index values, so
we should be able to do all the fixing there.

sebres added on 2018-03-06 17:44:22:
> "PUSH $empty"
> miss out on the check the $l is a valid list.

Don't need use it, because another hack may be applied very easy.

Normally, INST_LIST_INDEX_IMM expected operand >= 0 and < -1.
But, if you'll use -1 and put following code, you'll always get an 
empty return-value, as well as do the list validation inside:
```tcl-byte-code
  (0) push1 0
  (2) listIndexImm -1
  (7) done
```

> Practically already done in the TIP 445 branch.

Are you sure, Don? I see nothing about this in this branch...


WiP. I'll push soon a new branch with fix and test cases for all this mentioned.

dgp added on 2018-03-06 20:08:30:
That's what I meant to say, so I think we're in agreement.

I knew that TIP445 had a GetEndOffsetFromObj() routine.
Now that I've had a look, it wasn't precisely what I needed.

sebres added on 2018-03-06 20:31:35:
Still one inconsistency round about indices by lreplace:

Negative out of range (before start) is allowed. 
Positive out of range (after end) is disallowed.

% lreplace {a b c d} end-10 end-9
a b c d
% lreplace {a b c d} -3 -2
a b c d

% lreplace {a b c d} 6 7
list doesn't contain element 6
% lreplace {a b c d} end+2 end+3
list doesn't contain element end+2

But it allows exactly +1 after end:

% lreplace {a b c d} end+1 end+3
a b c d

Which is IMHO wrong and at least inconsistent at all.

Rather it should throw an error in both cases, or (I prefer it) it should ignore out of range (in both cases also).

I assume it is not really a bug, but if it is feature, then IMHO very-very questionable.

dgp added on 2018-03-07 15:29:22:
I see [lsort] uses a parallel scheme of encoding
index values as integers.

dgp added on 2018-03-07 15:31:17:
If anything is clear from this and related tickets,
[lreplace] is a complete abomination.

sebres added on 2018-03-07 16:14:02:
> [lreplace] is a complete abomination.

Yeap, IMHO it should rather get own instruction.
For example considering the performance of resulting construct for the
byte-code, it is hardly faster as direct invocation (by special cases like remove) and 
even slower! as not compiled invoke-variant (by replace).

## remove:

% tcl::unsupported::disassemble script {lreplace a 1 2}
ByteCode ...
  Source "lreplace a 1 2"
  Cmds 1, src 14, inst 52, litObjs 4, aux 0, stkDepth 3, code/src 0.00
  Commands 1:
      1: pc 0-50, src 0-13
  Command 1: "lreplace a 1 2"
    (0) push1 0         # "a"
    (2) dup
    (3) listLength
    (4) push1 1         # "1"
    (6) ge
    (7) jumpTrue1 +19   # pc 26
    (9) dup
    (10) listLength
    (11) jumpFalse1 +15         # pc 26
    (13) push1 2        # "list doesn't contain element 1"
    (15) push1 3        # "-errorcode {TCL OPERATION LREPLACE BADID..."
    (17) returnImm +1 0
    (26) dup
    (27) listRangeImm 0 0
    (36) reverse 2
    (41) listRangeImm 3 end
    (50) listConcat
    (51) done

% tcl::unsupported::disassemble script {lreplace a end+1 end+2}
ByteCode ...
  Source "lreplace a end+1 end+2"
  Cmds 1, src 22, inst 11, litObjs 4, aux 0, stkDepth 4, code/src 0.00
  Commands 1:
      1: pc 0-9, src 0-21
  Command 1: "lreplace a end+1 end+2"
    (0) push1 0         # "lreplace"
    (2) push1 1         # "a"
    (4) push1 2         # "end+1"
    (6) push1 3         # "end+2"
    (8) invokeStk1 4
    (10) done


% timerate {lreplace a 1 2}; # compiled
0.176311 µs/# 4526429 # 5671797 #/sec 798.059 nett-ms
% timerate {lreplace a end+1 end+2}; # invoke
0.205086 µs/# 4004816 # 4876013 #/sec 821.330 nett-ms

## replace:

% tcl::unsupported::disassemble script {lreplace a 1 2 x}
ByteCode ...
  Source "lreplace a 1 2 x"
  Cmds 1, src 16, inst 75, litObjs 5, aux 0, stkDepth 4, code/src 0.00
  Commands 1:
      1: pc 0-73, src 0-15
  Command 1: "lreplace a 1 2 x"
    (0) push1 0         # "a"
    (2) push1 1         # "x"
    (4) list 1
    (9) reverse 2
    (14) dup
    (15) listLength
    (16) push1 2        # "1"
    (18) ge
    (19) jumpTrue1 +19  # pc 38
    (21) dup
    (22) listLength
    (23) jumpFalse1 +15         # pc 38
    (25) push1 3        # "list doesn't contain element 1"
    (27) push1 4        # "-errorcode {TCL OPERATION LREPLACE BADID..."
    (29) returnImm +1 0
    (38) dup
    (39) listRangeImm 0 0
    (48) reverse 2
    (53) listRangeImm 3 end
    (62) reverse 3
    (67) listConcat
    (68) reverse 2
    (73) listConcat
    (74) done

% tcl::unsupported::disassemble script {lreplace a end+1 end+2 x}
ByteCode ...
  Source "lreplace a end+1 end+2 x"
  Cmds 1, src 24, inst 13, litObjs 5, aux 0, stkDepth 5, code/src 0.00
  Commands 1:
      1: pc 0-11, src 0-23
  Command 1: "lreplace a end+1 end+2 x"
    (0) push1 0         # "lreplace"
    (2) push1 1         # "a"
    (4) push1 2         # "end+1"
    (6) push1 3         # "end+2"
    (8) push1 4         # "x"
    (10) invokeStk1 5
    (12) done


% timerate {lreplace a 1 2 x}; # compiled
0.303333 µs/# 2874003 # 3296706 #/sec 871.780 nett-ms
% timerate {lreplace a end+1 end+2 x}; # invoke
0.223937 µs/# 3723690 # 4465541 #/sec 833.872 nett-ms


Note that by invoke it does additionally NRE-, stack to local normalization (decache stack info, etc),
TEBC_YIELD, then exits from TEBCResume.

Let alone the code complexity, the growth of the byte-code size, CPU-cache washouts, etc.
It is very questionable why such constructs should be implemented with tcl byte-code instead of pure C.


> I see [lsort] uses a parallel scheme of encoding index values as integers.

Yes, as you possibly saw, I have already added a test cases for it. 
Unfortunately, it affects basically many other things, that using TclGetIntForIndexM (TclGetIntForIndex) 
with fixed (supplied before known) value of `endValue`,
like TCL_INDEX_END, SORTIDX_END, etc.

sebres added on 2018-03-07 20:41:51:

To [31a078bec7]:    index = opnd + (opnd <= TCL_INDEX_END)*(objc - 1 - TCL_INDEX_END); Please don't do such optimizations, Don!
You are not compiler (which will do it better as you, believe me;)

See https://godbolt.org/g/T8HB8w (gcc 7.3),
   https://godbolt.org/g/bwhU45 (gcc trunk).
In case that link does not work (expired): Following C code:
#define TCL_INDEX_END		(-2)

int test1(int opnd, int objc) {
  int index;

  index = opnd + (opnd <= TCL_INDEX_END)*(objc - 1 - TCL_INDEX_END);

  return index;
}


int test2(int opnd, int objc) {
  int index;

  if ((index = opnd) <= TCL_INDEX_END) {
    index += (objc - 1 - TCL_INDEX_END);
  }

  return index;
}
will get:

```asm # -m64
test1(int, int):
  xor eax, eax
  cmp edi, -1
  setl al
  add esi, 1
  imul eax, esi
  add eax, edi
  ret
test2(int, int):
  lea ecx, [rdi+1+rsi]
  mov eax, edi
  cmp edi, -1
  cmovl eax, ecx
  ret
```

```asm # -m32
test1(int, int):
  mov ecx, DWORD PTR [esp+4]
  mov edx, DWORD PTR [esp+8]
  xor eax, eax
  cmp ecx, -1
  setl al
  add edx, 1
  imul eax, edx
  add eax, ecx
  ret
test2(int, int):
  mov eax, DWORD PTR [esp+4]
  mov edx, DWORD PTR [esp+8]
  lea edx, [eax+1+edx]
  cmp eax, -1
  cmovl eax, edx
  ret
```
Thus just use it as suggested in test2 above. ;)


dgp added on 2018-03-09 12:31:27:
Another variant where the encoded index value is escaping to script level:

% lsearch -subindices -index end-1 {{a 1}} a
0 -3

Correct answer should be:
0 0

dgp added on 2018-03-09 22:19:26:
Fixed for 8.6.9

pooryorick added on 2024-10-02 07:47:28:

For reference, the commit for the fix is [02721ee263bbe32a].