Negative variable indexing do not work for lists

[anutosh491]

What works

def main0():
    l: list[i32] = [1, 2, 3]
    x: i32 = 2
    print(l[1], l[-1], l[x])

main0()

(lf) anutosh491@spbhat68:~/lpython/lpython$ ./src/bin/lpython examples/expr2.py 
2 3 3

What doesn't work

(lf) anutosh491@spbhat68:~/lpython/lpython$ cat examples/expr2.py 
def main0():
    l: list[i32] = [1, 2, 3]
    x: i32 = -2
    print(l[x])

main0()

(lf) anutosh491@spbhat68:~/lpython/lpython$ ./src/bin/lpython examples/expr2.py 
IndexError: List index is out of range. Index range is (0, 2), but the given index is -2

(lf) anutosh491@spbhat68:~/lpython/lpython$ python examples/expr2.py 
2

So basically what's happening is , it follows the expected code flow and through the code block responsible for handling negative indexing . But here the val comes out to be a null pointer when indexing is done through a variable .

lpython/src/lpython/semantics/python_ast_to_asr.cpp

Lines 3109 to 3114 in 8f62ac4

	} else if (ASR::is_a<ASR::List_t>(*type)) {
	index = ASRUtils::EXPR(tmp);
	ASR::expr_t* val = ASRUtils::expr_value(index);
	if (val && ASR::is_a<ASR::IntegerConstant_t>(*val)) {
	if (ASR::down_cast<ASR::IntegerConstant_t>(val)->m_n < 0) {
	// Replace `x[-1]` to `x[len(x)+(-1)]`

The positive index remains unaffected though (it skips this block ) and still works out well through the code which follows

tmp = make_ListItem_t(al, loc, value, index,
                                      ASR::down_cast<ASR::List_t>(type)->m_type, nullptr);
                return false;

[anutosh491]

I am not fully sure how we could approach this . Indexing for strings are pretty similar

            if (ASRUtils::is_character(*type)) {
                ASR::expr_t* val = ASRUtils::expr_value(index);
                if (val && ASR::is_a<ASR::IntegerConstant_t>(*val)) {
                    if (ASR::down_cast<ASR::IntegerConstant_t>(val)->m_n < 0) {
                        // Replace `x[-1]` to `x[len(x)+(-1)]`
                        ASR::ttype_t *int_type = ASRUtils::TYPE(ASR::make_Integer_t(
                                                        al, loc, 4, nullptr, 0));
                        ASR::expr_t *list_len = ASRUtils::EXPR(ASR::make_StringLen_t(
                                    al, loc, value, int_type, nullptr));
                        ASR::expr_t *neg_idx = ASRUtils::expr_value(index);
                        index = ASRUtils::EXPR(ASR::make_IntegerBinOp_t(al, loc,
                            list_len, ASR::binopType::Add, neg_idx, int_type, nullptr));
                    }
                }
                index = index_add_one(loc, index);
                ai.m_right = index;
                tmp = ASR::make_StringItem_t(al, loc, value, index, type, nullptr);
                return false;
            }

But here negative indexing through a variable works because of the index_add_one function implementation .

(lf) anutosh491@spbhat68:~/lpython/lpython$ cat examples/expr2.py 
def main0():
    s: str = "abc"
    x: i32 = -2
    print(s[x])

main0()

(lf) anutosh491@spbhat68:~/lpython/lpython$ ./src/bin/lpython examples/expr2.py 
b

So is this the correct way (implementing something similar to what has been done for strings) to go about this issue ?

[Thirumalai-Shaktivel]

We discussed this here: #1099 (comment)

[faze-geek]

Even case two - index value at runtime time isn't completely correct on my master

def main0():
    l: list[i32] = [1, 2, 3]
    print(l[-4])

main0()

(lp) C:\Users\kunni\lpython>src\bin\lpython try1.py
IndexError: List index is out of range. Index range is (0, 2), but the given index is -1    # given index is -4

print(l[-5]) 

(lp) C:\Users\kunni\lpython>src\bin\lpython try1.py
IndexError: List index is out of range. Index range is (0, 2), but the given index is -2    # given index is -5

print(l[-6]) 

(lp) C:\Users\kunni\lpython>src\bin\lpython try1.py
IndexError: List index is out of range. Index range is (0, 2), but the given index is -3    # given index is -6

@anutosh491 Can you check. If this is valid you can include this in your future pr !

[anutosh491]

We discussed this here: #1099 (comment)

This looks like a good thread to figure this issue out . I'll go through it !

[czgdp1807]

We discussed this in #1099. The final design decision was made in #1099 (review). I guess if we are allowing constant negative indices then we should also allow variable negative indices.

Here's how I would re-take the decision,

1. In --fast mode no negative indices (both constant and variables) should be allowed (as it slows things down).
2. In every other mode we should allow negative indices (again both constant and variables).

For now allowing only constant negative indices creates confusion and is non-intuitive.

cc: @certik

[certik]

I don't know if we should have a different semantics for --fast, that does not seam clean either.

My reasoning for tuples was that we can't index tuples at runtime anyway, because the type of the result depends on the index, so this is a fundamentally compile time operation, whether positive or negative. And it is done quickly, no runtime overhead.

For lists on the other hand, I think we should not allow negative indexing, since it cannot be done at runtime quickly.

[anutosh491]

Yeah I do agree with the points raised here.

For now allowing only constant negative indices creates confusion and is non-intuitive.
For lists on the other hand, I think we should not allow negative indexing, since it cannot be done at runtime quickly.

Would it make sense to comment out, how the constant negative indexing case is being solved and raise a SemanticError instead saying constant negative indexing in lists is not supported yet untill we have a decision on what needs to be done with variable negative indexing ?

[certik]

Assuming we are fine that indexing into tuples is only allowed for compile time indices (and forbidden for runtime indices), then why would it create confusion to take this concept further and allow compile time indices (but not runtime indices) for more data structures than just tuples?

[czgdp1807]

That makes sense. However runtime indexing (both positive and negative) for tuples is theoretically not possible (as discussed in #1534 (comment)). So tuples allow only compile time indices irrespective of whether the index is positive or negative.

The source of confusion in lists is that we are allowing runtime indices for positive values but not for negative values. On top of that compile time indices of any sign are allowed in lists. For compile time case one can use both positive and negative indexing in lists. So that will intuitively make one think that we can also do the same with runtime indices but then we face the out of bounds error.

Even if we are okay with current status in main, but I think users should receive a detailed error message when they use runtime negative indices in lists,

Something like, "Using negative indices with lists at runtime causes performance slowdowns (<probabaly a link to benchmark where slowdown is observed>), hence LPython doesn't allow such use cases".