Repository: tursodatabase/limbo (rust)

Issue:
Backwards iteration of table can hang
```sql
limbo> explain select * from users where id < 100 order by id desc;
addr  opcode             p1    p2    p3    p4             p5  comment
----  -----------------  ----  ----  ----  -------------  --  -------
0     Init               0     17    0                    0   Start at 17
1     OpenRead           0     2     0                    0   table=users, root=2
2     Integer            100   11    0                    0   r[11]=100
3     SeekLT             0     16    11                   0   key=[11..11]
4       RowId            0     1     0                    0   r[1]=users.rowid
5       Column           0     1     2                    0   r[2]=users.first_name
6       Column           0     2     3                    0   r[3]=users.last_name
7       Column           0     3     4                    0   r[4]=users.email
8       Column           0     4     5                    0   r[5]=users.phone_number
9       Column           0     5     6                    0   r[6]=users.address
10      Column           0     6     7                    0   r[7]=users.city
11      Column           0     7     8                    0   r[8]=users.state
12      Column           0     8     9                    0   r[9]=users.zipcode
13      Column           0     9     10                   0   r[10]=users.age
14      ResultRow        1     10    0                    0   output=r[1..10]
15    Prev               0     4     0                    0   
16    Halt               0     0     0                    0   
17    Transaction        0     0     0                    0   write=false
18    Goto               0     1     0                    0 
```

Executing this query (not the EXPLAIN) hangs for whatever reason.

This one, which uses an index scan, doesn't:

```sql
limbo> explain select * from users where age < 3 order by age desc;
addr  opcode             p1    p2    p3    p4             p5  comment
----  -----------------  ----  ----  ----  -------------  --  -------
0     Init               0     19    0                    0   Start at 19
1     OpenRead           0     2     0                    0   table=users, root=2
2     OpenRead           1     274   0                    0   table=age_idx, root=274
3     Integer            3     11    0                    0   r[11]=3
4     SeekLT             1     18    11                   0   key=[11..11]
5       DeferredSeek     1     0     0                    0   
6       IdxRowId         1     1     0                    0   r[1]=age_idx.rowid
7       Column           0     1     2                    0   r[2]=users.first_name
8       Column           0     2     3                    0   r[3]=users.last_name
9       Column           0     3     4                    0   r[4]=users.email
10      Column           0     4     5                    0   r[5]=users.phone_number
11      Column           0     5     6                    0   r[6]=users.address
12      Column           0     6     7                    0   r[7]=users.city
13      Column           0     7     8                    0   r[8]=users.state
14      Column           0     8     9                    0   r[9]=users.zipcode
15      Column           0     9     10                   0   r[10]=users.age
16      ResultRow        1     10    0                    0   output=r[1..10]
17    Prev               1     5     0                    0   
18    Halt               0     0     0                    0   
19    Transaction        0     0     0                    0   write=false
20    Goto               0     1     0                    0 
```

Pull request description:
btree: fix infinite looping in backwards iteration of btree table
Closes #1562 

Existing "fuzz test" (not really fuzz, but kinda) didn't catch this due to `LIMIT 3` clause

Patch:
diff --git a/core/storage/btree.rs b/core/storage/btree.rs
index 763b9340..febb08ad 100644
--- a/core/storage/btree.rs
+++ b/core/storage/btree.rs
@@ -576,6 +576,7 @@ impl BTreeCursor {
             } else {
                 cell_idx
             };
+
             let cell = contents.cell_get(
                 cell_idx,
                 payload_overflow_threshold_max(contents.page_type(), self.usable_space() as u16),
@@ -589,6 +590,7 @@ impl BTreeCursor {
                     _rowid,
                 }) => {
                     let mem_page = self.read_page(_left_child_page as usize)?;
+                    self.stack.retreat();
                     self.stack.push_backwards(mem_page);
                     continue;
                 }


Test patch:
diff --git a/testing/orderby.test b/testing/orderby.test
index b5b56cdd..d930bb38 100755
--- a/testing/orderby.test
+++ b/testing/orderby.test
@@ -199,4 +199,15 @@ do_execsql_test orderby_desc_with_filter_id_le {
 6665
 6664
 6663
-6662}
\ No newline at end of file
+6662}
+
+# regression test where backwards iteration used to hang indefinitely
+do_execsql_test orderby_desc_regression {
+    select count(1) from (select * from users where id < 100 order by id desc)
+} {99}
+
+do_execsql_test orderby_desc_regression_verify_order {
+    select id from users where id < 100 order by id desc limit 3;
+} {99
+98
+97}
\ No newline at end of file
diff --git a/tests/integration/fuzz/mod.rs b/tests/integration/fuzz/mod.rs
index a981ce4a..f7c3860d 100644
--- a/tests/integration/fuzz/mod.rs
+++ b/tests/integration/fuzz/mod.rs
@@ -51,7 +51,7 @@ mod tests {
 
         let insert = format!(
             "INSERT INTO t VALUES {}",
-            (1..10000)
+            (1..2000)
                 .map(|x| format!("({})", x))
                 .collect::<Vec<_>>()
                 .join(", ")
@@ -71,9 +71,9 @@ mod tests {
 
         for comp in COMPARISONS.iter() {
             for order_by in ORDER_BY.iter() {
-                for max in 0..=10000 {
+                for max in 0..=2000 {
                     let query = format!(
-                        "SELECT * FROM t WHERE x {} {} {} LIMIT 3",
+                        "SELECT * FROM t WHERE x {} {} {}",
                         comp,
                         max,
                         order_by.unwrap_or("")