sqlx_sqlite/connection/
explain.rs

1// Bad casts in this module SHOULD NOT result in a SQL injection
2// https://github.com/launchbadge/sqlx/issues/3440
3#![allow(
4    clippy::cast_possible_truncation,
5    clippy::cast_possible_wrap,
6    clippy::cast_sign_loss
7)]
8use crate::connection::intmap::IntMap;
9use crate::connection::{execute, ConnectionState};
10use crate::error::Error;
11use crate::from_row::FromRow;
12use crate::logger::{BranchParent, BranchResult, DebugDiff};
13use crate::type_info::DataType;
14use crate::SqliteTypeInfo;
15use sqlx_core::{hash_map, HashMap};
16use std::fmt::Debug;
17use std::str::from_utf8;
18
19// affinity
20const SQLITE_AFF_NONE: u8 = 0x40; /* '@' */
21const SQLITE_AFF_BLOB: u8 = 0x41; /* 'A' */
22const SQLITE_AFF_TEXT: u8 = 0x42; /* 'B' */
23const SQLITE_AFF_NUMERIC: u8 = 0x43; /* 'C' */
24const SQLITE_AFF_INTEGER: u8 = 0x44; /* 'D' */
25const SQLITE_AFF_REAL: u8 = 0x45; /* 'E' */
26
27// opcodes
28const OP_INIT: &str = "Init";
29const OP_GOTO: &str = "Goto";
30const OP_DECR_JUMP_ZERO: &str = "DecrJumpZero";
31const OP_DELETE: &str = "Delete";
32const OP_ELSE_EQ: &str = "ElseEq";
33const OP_EQ: &str = "Eq";
34const OP_END_COROUTINE: &str = "EndCoroutine";
35const OP_FILTER: &str = "Filter";
36const OP_FK_IF_ZERO: &str = "FkIfZero";
37const OP_FOUND: &str = "Found";
38const OP_GE: &str = "Ge";
39const OP_GO_SUB: &str = "Gosub";
40const OP_GT: &str = "Gt";
41const OP_IDX_GE: &str = "IdxGE";
42const OP_IDX_GT: &str = "IdxGT";
43const OP_IDX_LE: &str = "IdxLE";
44const OP_IDX_LT: &str = "IdxLT";
45const OP_IF: &str = "If";
46const OP_IF_NO_HOPE: &str = "IfNoHope";
47const OP_IF_NOT: &str = "IfNot";
48const OP_IF_NOT_OPEN: &str = "IfNotOpen";
49const OP_IF_NOT_ZERO: &str = "IfNotZero";
50const OP_IF_NULL_ROW: &str = "IfNullRow";
51const OP_IF_POS: &str = "IfPos";
52const OP_IF_SMALLER: &str = "IfSmaller";
53const OP_INCR_VACUUM: &str = "IncrVacuum";
54const OP_INIT_COROUTINE: &str = "InitCoroutine";
55const OP_IS_NULL: &str = "IsNull";
56const OP_IS_NULL_OR_TYPE: &str = "IsNullOrType";
57const OP_LAST: &str = "Last";
58const OP_LE: &str = "Le";
59const OP_LT: &str = "Lt";
60const OP_MUST_BE_INT: &str = "MustBeInt";
61const OP_NE: &str = "Ne";
62const OP_NEXT: &str = "Next";
63const OP_NO_CONFLICT: &str = "NoConflict";
64const OP_NOT_EXISTS: &str = "NotExists";
65const OP_NOT_NULL: &str = "NotNull";
66const OP_ONCE: &str = "Once";
67const OP_PREV: &str = "Prev";
68const OP_PROGRAM: &str = "Program";
69const OP_RETURN: &str = "Return";
70const OP_REWIND: &str = "Rewind";
71const OP_ROW_DATA: &str = "RowData";
72const OP_ROW_SET_READ: &str = "RowSetRead";
73const OP_ROW_SET_TEST: &str = "RowSetTest";
74const OP_SEEK_GE: &str = "SeekGE";
75const OP_SEEK_GT: &str = "SeekGT";
76const OP_SEEK_LE: &str = "SeekLE";
77const OP_SEEK_LT: &str = "SeekLT";
78const OP_SEEK_ROW_ID: &str = "SeekRowid";
79const OP_SEEK_SCAN: &str = "SeekScan";
80const OP_SEQUENCE: &str = "Sequence";
81const OP_SEQUENCE_TEST: &str = "SequenceTest";
82const OP_SORT: &str = "Sort";
83const OP_SORTER_DATA: &str = "SorterData";
84const OP_SORTER_INSERT: &str = "SorterInsert";
85const OP_SORTER_NEXT: &str = "SorterNext";
86const OP_SORTER_OPEN: &str = "SorterOpen";
87const OP_SORTER_SORT: &str = "SorterSort";
88const OP_V_FILTER: &str = "VFilter";
89const OP_V_NEXT: &str = "VNext";
90const OP_YIELD: &str = "Yield";
91const OP_JUMP: &str = "Jump";
92const OP_COLUMN: &str = "Column";
93const OP_MAKE_RECORD: &str = "MakeRecord";
94const OP_INSERT: &str = "Insert";
95const OP_IDX_INSERT: &str = "IdxInsert";
96const OP_OPEN_DUP: &str = "OpenDup";
97const OP_OPEN_PSEUDO: &str = "OpenPseudo";
98const OP_OPEN_READ: &str = "OpenRead";
99const OP_OPEN_WRITE: &str = "OpenWrite";
100const OP_OPEN_EPHEMERAL: &str = "OpenEphemeral";
101const OP_OPEN_AUTOINDEX: &str = "OpenAutoindex";
102const OP_AGG_FINAL: &str = "AggFinal";
103const OP_AGG_VALUE: &str = "AggValue";
104const OP_AGG_STEP: &str = "AggStep";
105const OP_FUNCTION: &str = "Function";
106const OP_MOVE: &str = "Move";
107const OP_COPY: &str = "Copy";
108const OP_SCOPY: &str = "SCopy";
109const OP_NULL: &str = "Null";
110const OP_NULL_ROW: &str = "NullRow";
111const OP_INT_COPY: &str = "IntCopy";
112const OP_CAST: &str = "Cast";
113const OP_STRING8: &str = "String8";
114const OP_INT64: &str = "Int64";
115const OP_INTEGER: &str = "Integer";
116const OP_REAL: &str = "Real";
117const OP_NOT: &str = "Not";
118const OP_BLOB: &str = "Blob";
119const OP_VARIABLE: &str = "Variable";
120const OP_COUNT: &str = "Count";
121const OP_ROWID: &str = "Rowid";
122const OP_NEWROWID: &str = "NewRowid";
123const OP_OR: &str = "Or";
124const OP_AND: &str = "And";
125const OP_BIT_AND: &str = "BitAnd";
126const OP_BIT_OR: &str = "BitOr";
127const OP_SHIFT_LEFT: &str = "ShiftLeft";
128const OP_SHIFT_RIGHT: &str = "ShiftRight";
129const OP_ADD: &str = "Add";
130const OP_SUBTRACT: &str = "Subtract";
131const OP_MULTIPLY: &str = "Multiply";
132const OP_DIVIDE: &str = "Divide";
133const OP_REMAINDER: &str = "Remainder";
134const OP_CONCAT: &str = "Concat";
135const OP_OFFSET_LIMIT: &str = "OffsetLimit";
136const OP_RESULT_ROW: &str = "ResultRow";
137const OP_HALT: &str = "Halt";
138const OP_HALT_IF_NULL: &str = "HaltIfNull";
139
140const MAX_LOOP_COUNT: u8 = 2;
141const MAX_TOTAL_INSTRUCTION_COUNT: u32 = 100_000;
142
143#[derive(Clone, Eq, PartialEq, Hash)]
144enum ColumnType {
145    Single {
146        datatype: DataType,
147        nullable: Option<bool>,
148    },
149    Record(IntMap<ColumnType>),
150}
151
152impl Default for ColumnType {
153    fn default() -> Self {
154        Self::Single {
155            datatype: DataType::Null,
156            nullable: None,
157        }
158    }
159}
160
161impl ColumnType {
162    fn null() -> Self {
163        Self::Single {
164            datatype: DataType::Null,
165            nullable: Some(true),
166        }
167    }
168    fn map_to_datatype(&self) -> DataType {
169        match self {
170            Self::Single { datatype, .. } => *datatype,
171            Self::Record(_) => DataType::Null, //If we're trying to coerce to a regular Datatype, we can assume a Record is invalid for the context
172        }
173    }
174    fn map_to_nullable(&self) -> Option<bool> {
175        match self {
176            Self::Single { nullable, .. } => *nullable,
177            Self::Record(_) => None, //If we're trying to coerce to a regular Datatype, we can assume a Record is invalid for the context
178        }
179    }
180}
181
182impl core::fmt::Debug for ColumnType {
183    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
184        match self {
185            Self::Single { datatype, nullable } => {
186                let nullable_str = match nullable {
187                    Some(true) => "NULL",
188                    Some(false) => "NOT NULL",
189                    None => "NULL?",
190                };
191                write!(f, "{:?} {}", datatype, nullable_str)
192            }
193            Self::Record(columns) => {
194                f.write_str("Record(")?;
195                let mut column_iter = columns.iter();
196                if let Some(item) = column_iter.next() {
197                    write!(f, "{:?}", item)?;
198                    for item in column_iter {
199                        write!(f, ", {:?}", item)?;
200                    }
201                }
202                f.write_str(")")
203            }
204        }
205    }
206}
207
208#[derive(Debug, Clone, Eq, PartialEq, Hash)]
209enum RegDataType {
210    Single(ColumnType),
211    Int(i64),
212}
213
214impl RegDataType {
215    fn map_to_datatype(&self) -> DataType {
216        match self {
217            RegDataType::Single(d) => d.map_to_datatype(),
218            RegDataType::Int(_) => DataType::Integer,
219        }
220    }
221    fn map_to_nullable(&self) -> Option<bool> {
222        match self {
223            RegDataType::Single(d) => d.map_to_nullable(),
224            RegDataType::Int(_) => Some(false),
225        }
226    }
227    fn map_to_columntype(&self) -> ColumnType {
228        match self {
229            RegDataType::Single(d) => d.clone(),
230            RegDataType::Int(_) => ColumnType::Single {
231                datatype: DataType::Integer,
232                nullable: Some(false),
233            },
234        }
235    }
236}
237
238impl Default for RegDataType {
239    fn default() -> Self {
240        Self::Single(ColumnType::default())
241    }
242}
243
244#[derive(Debug, Clone, Eq, PartialEq, Hash)]
245struct TableDataType {
246    cols: IntMap<ColumnType>,
247    is_empty: Option<bool>,
248}
249
250#[derive(Debug, Clone, Eq, PartialEq, Hash)]
251enum CursorDataType {
252    Normal(i64),
253    Pseudo(i64),
254}
255
256impl CursorDataType {
257    fn columns(
258        &self,
259        tables: &IntMap<TableDataType>,
260        registers: &IntMap<RegDataType>,
261    ) -> IntMap<ColumnType> {
262        match self {
263            Self::Normal(i) => match tables.get(i) {
264                Some(tab) => tab.cols.clone(),
265                None => IntMap::new(),
266            },
267            Self::Pseudo(i) => match registers.get(i) {
268                Some(RegDataType::Single(ColumnType::Record(r))) => r.clone(),
269                _ => IntMap::new(),
270            },
271        }
272    }
273
274    fn columns_ref<'s, 'r, 'o>(
275        &'s self,
276        tables: &'r IntMap<TableDataType>,
277        registers: &'r IntMap<RegDataType>,
278    ) -> Option<&'o IntMap<ColumnType>>
279    where
280        's: 'o,
281        'r: 'o,
282    {
283        match self {
284            Self::Normal(i) => match tables.get(i) {
285                Some(tab) => Some(&tab.cols),
286                None => None,
287            },
288            Self::Pseudo(i) => match registers.get(i) {
289                Some(RegDataType::Single(ColumnType::Record(r))) => Some(r),
290                _ => None,
291            },
292        }
293    }
294
295    fn columns_mut<'s, 'r, 'o>(
296        &'s self,
297        tables: &'r mut IntMap<TableDataType>,
298        registers: &'r mut IntMap<RegDataType>,
299    ) -> Option<&'o mut IntMap<ColumnType>>
300    where
301        's: 'o,
302        'r: 'o,
303    {
304        match self {
305            Self::Normal(i) => match tables.get_mut(i) {
306                Some(tab) => Some(&mut tab.cols),
307                None => None,
308            },
309            Self::Pseudo(i) => match registers.get_mut(i) {
310                Some(RegDataType::Single(ColumnType::Record(r))) => Some(r),
311                _ => None,
312            },
313        }
314    }
315
316    fn table_mut<'s, 'r, 'o>(
317        &'s self,
318        tables: &'r mut IntMap<TableDataType>,
319    ) -> Option<&'o mut TableDataType>
320    where
321        's: 'o,
322        'r: 'o,
323    {
324        match self {
325            Self::Normal(i) => match tables.get_mut(i) {
326                Some(tab) => Some(tab),
327                None => None,
328            },
329            _ => None,
330        }
331    }
332
333    fn is_empty(&self, tables: &IntMap<TableDataType>) -> Option<bool> {
334        match self {
335            Self::Normal(i) => match tables.get(i) {
336                Some(tab) => tab.is_empty,
337                None => Some(true),
338            },
339            Self::Pseudo(_) => Some(false), //pseudo cursors have exactly one row
340        }
341    }
342}
343
344#[allow(clippy::wildcard_in_or_patterns)]
345fn affinity_to_type(affinity: u8) -> DataType {
346    match affinity {
347        SQLITE_AFF_BLOB => DataType::Blob,
348        SQLITE_AFF_INTEGER => DataType::Integer,
349        SQLITE_AFF_NUMERIC => DataType::Numeric,
350        SQLITE_AFF_REAL => DataType::Float,
351        SQLITE_AFF_TEXT => DataType::Text,
352
353        SQLITE_AFF_NONE | _ => DataType::Null,
354    }
355}
356
357#[allow(clippy::wildcard_in_or_patterns)]
358fn opcode_to_type(op: &str) -> DataType {
359    match op {
360        OP_REAL => DataType::Float,
361        OP_BLOB => DataType::Blob,
362        OP_AND | OP_OR => DataType::Bool,
363        OP_NEWROWID | OP_ROWID | OP_COUNT | OP_INT64 | OP_INTEGER => DataType::Integer,
364        OP_STRING8 => DataType::Text,
365        OP_COLUMN | _ => DataType::Null,
366    }
367}
368
369fn root_block_columns(
370    conn: &mut ConnectionState,
371) -> Result<HashMap<(i64, i64), IntMap<ColumnType>>, Error> {
372    let table_block_columns: Vec<(i64, i64, i64, String, bool)> = execute::iter(
373        conn,
374        "SELECT s.dbnum, s.rootpage, col.cid as colnum, col.type, col.\"notnull\"
375         FROM (
376             select 1 dbnum, tss.* from temp.sqlite_schema tss
377             UNION ALL select 0 dbnum, mss.* from main.sqlite_schema mss
378             ) s
379         JOIN pragma_table_info(s.name) AS col
380         WHERE s.type = 'table'
381         UNION ALL
382         SELECT s.dbnum, s.rootpage, idx.seqno as colnum, col.type, col.\"notnull\"
383         FROM (
384             select 1 dbnum, tss.* from temp.sqlite_schema tss
385             UNION ALL select 0 dbnum, mss.* from main.sqlite_schema mss
386             ) s
387         JOIN pragma_index_info(s.name) AS idx
388         LEFT JOIN pragma_table_info(s.tbl_name) as col
389           ON col.cid = idx.cid
390           WHERE s.type = 'index'",
391        None,
392        false,
393    )?
394    .filter_map(|res| res.map(|either| either.right()).transpose())
395    .map(|row| FromRow::from_row(&row?))
396    .collect::<Result<Vec<_>, Error>>()?;
397
398    let mut row_info: HashMap<(i64, i64), IntMap<ColumnType>> = HashMap::new();
399    for (dbnum, block, colnum, datatype, notnull) in table_block_columns {
400        let row_info = row_info.entry((dbnum, block)).or_default();
401        row_info.insert(
402            colnum,
403            ColumnType::Single {
404                datatype: datatype.parse().unwrap_or(DataType::Null),
405                nullable: Some(!notnull),
406            },
407        );
408    }
409
410    Ok(row_info)
411}
412
413struct Sequence(i64);
414
415impl Sequence {
416    pub fn new() -> Self {
417        Self(0)
418    }
419    pub fn next(&mut self) -> i64 {
420        let curr = self.0;
421        self.0 += 1;
422        curr
423    }
424}
425
426#[derive(Debug)]
427struct QueryState {
428    // The number of times each instruction has been visited
429    pub visited: Vec<u8>,
430    // A unique identifier of the query branch
431    pub branch_id: i64,
432    // How many instructions have been executed on this branch (NOT the same as program_i, which is the currently executing instruction of the program)
433    pub instruction_counter: i64,
434    // Parent branch this branch was forked from (if any)
435    pub branch_parent: Option<BranchParent>,
436    // State of the virtual machine
437    pub mem: MemoryState,
438    // Results published by the execution
439    pub result: Option<Vec<(Option<SqliteTypeInfo>, Option<bool>)>>,
440}
441
442impl From<&QueryState> for MemoryState {
443    fn from(val: &QueryState) -> Self {
444        val.mem.clone()
445    }
446}
447
448impl From<QueryState> for MemoryState {
449    fn from(val: QueryState) -> Self {
450        val.mem
451    }
452}
453
454impl From<&QueryState> for BranchParent {
455    fn from(val: &QueryState) -> Self {
456        Self {
457            id: val.branch_id,
458            idx: val.instruction_counter,
459        }
460    }
461}
462
463impl QueryState {
464    fn get_reference(&self) -> BranchParent {
465        BranchParent {
466            id: self.branch_id,
467            idx: self.instruction_counter,
468        }
469    }
470    fn new_branch(&self, branch_seq: &mut Sequence) -> Self {
471        Self {
472            visited: self.visited.clone(),
473            branch_id: branch_seq.next(),
474            instruction_counter: 0,
475            branch_parent: Some(BranchParent {
476                id: self.branch_id,
477                idx: self.instruction_counter - 1, //instruction counter is incremented at the start of processing an instruction, so need to subtract 1 to get the 'current' instruction
478            }),
479            mem: self.mem.clone(),
480            result: self.result.clone(),
481        }
482    }
483}
484
485#[derive(Debug, Clone, PartialEq, Eq, Hash)]
486struct MemoryState {
487    // Next instruction to execute
488    pub program_i: usize,
489    // Registers
490    pub r: IntMap<RegDataType>,
491    // Rows that pointers point to
492    pub p: IntMap<CursorDataType>,
493    // Table definitions pointed to by pointers
494    pub t: IntMap<TableDataType>,
495}
496
497impl DebugDiff for MemoryState {
498    fn diff(&self, prev: &Self) -> String {
499        let r_diff = self.r.diff(&prev.r);
500        let p_diff = self.p.diff(&prev.p);
501        let t_diff = self.t.diff(&prev.t);
502
503        let mut differences = String::new();
504        for (i, v) in r_diff {
505            if !differences.is_empty() {
506                differences.push('\n');
507            }
508            differences.push_str(&format!("r[{}]={:?}", i, v))
509        }
510        for (i, v) in p_diff {
511            if !differences.is_empty() {
512                differences.push('\n');
513            }
514            differences.push_str(&format!("p[{}]={:?}", i, v))
515        }
516        for (i, v) in t_diff {
517            if !differences.is_empty() {
518                differences.push('\n');
519            }
520            differences.push_str(&format!("t[{}]={:?}", i, v))
521        }
522        differences
523    }
524}
525
526struct BranchList {
527    states: Vec<QueryState>,
528    visited_branch_state: HashMap<MemoryState, BranchParent>,
529}
530
531impl BranchList {
532    pub fn new(state: QueryState) -> Self {
533        Self {
534            states: vec![state],
535            visited_branch_state: HashMap::new(),
536        }
537    }
538    pub fn push<R: Debug, P: Debug>(
539        &mut self,
540        mut state: QueryState,
541        logger: &mut crate::logger::QueryPlanLogger<'_, R, MemoryState, P>,
542    ) {
543        logger.add_branch(&state, &state.branch_parent.unwrap());
544        match self.visited_branch_state.entry(state.mem) {
545            hash_map::Entry::Vacant(entry) => {
546                //this state is not identical to another state, so it will need to be processed
547                state.mem = entry.key().clone(); //replace state.mem since .entry() moved it
548                entry.insert(state.get_reference());
549                self.states.push(state);
550            }
551            hash_map::Entry::Occupied(entry) => {
552                //already saw a state identical to this one, so no point in processing it
553                state.mem = entry.key().clone(); //replace state.mem since .entry() moved it
554                logger.add_result(state, BranchResult::Dedup(*entry.get()));
555            }
556        }
557    }
558    pub fn pop(&mut self) -> Option<QueryState> {
559        self.states.pop()
560    }
561}
562
563// Opcode Reference: https://sqlite.org/opcode.html
564pub(super) fn explain(
565    conn: &mut ConnectionState,
566    query: &str,
567) -> Result<(Vec<SqliteTypeInfo>, Vec<Option<bool>>), Error> {
568    let root_block_cols = root_block_columns(conn)?;
569    let program: Vec<(i64, String, i64, i64, i64, Vec<u8>)> =
570        execute::iter(conn, &format!("EXPLAIN {query}"), None, false)?
571            .filter_map(|res| res.map(|either| either.right()).transpose())
572            .map(|row| FromRow::from_row(&row?))
573            .collect::<Result<Vec<_>, Error>>()?;
574    let program_size = program.len();
575
576    let mut logger = crate::logger::QueryPlanLogger::new(query, &program);
577    let mut branch_seq = Sequence::new();
578    let mut states = BranchList::new(QueryState {
579        visited: vec![0; program_size],
580        branch_id: branch_seq.next(),
581        branch_parent: None,
582        instruction_counter: 0,
583        result: None,
584        mem: MemoryState {
585            program_i: 0,
586            r: IntMap::new(),
587            t: IntMap::new(),
588            p: IntMap::new(),
589        },
590    });
591
592    let mut gas = MAX_TOTAL_INSTRUCTION_COUNT;
593    let mut result_states = Vec::new();
594
595    while let Some(mut state) = states.pop() {
596        while state.mem.program_i < program_size {
597            let (_, ref opcode, p1, p2, p3, ref p4) = program[state.mem.program_i];
598
599            logger.add_operation(state.mem.program_i, &state);
600            state.instruction_counter += 1;
601
602            //limit the number of 'instructions' that can be evaluated
603            if gas > 0 {
604                gas -= 1;
605            } else {
606                logger.add_result(state, BranchResult::GasLimit);
607                break;
608            }
609
610            if state.visited[state.mem.program_i] > MAX_LOOP_COUNT {
611                logger.add_result(state, BranchResult::LoopLimit);
612                //avoid (infinite) loops by breaking if we ever hit the same instruction twice
613                break;
614            }
615
616            state.visited[state.mem.program_i] += 1;
617
618            match &**opcode {
619                OP_INIT => {
620                    // start at <p2>
621                    state.mem.program_i = p2 as usize;
622                    continue;
623                }
624
625                OP_GOTO => {
626                    // goto <p2>
627
628                    state.mem.program_i = p2 as usize;
629                    continue;
630                }
631
632                OP_GO_SUB => {
633                    // store current instruction in r[p1], goto <p2>
634                    state
635                        .mem
636                        .r
637                        .insert(p1, RegDataType::Int(state.mem.program_i as i64));
638                    state.mem.program_i = p2 as usize;
639                    continue;
640                }
641
642                OP_FK_IF_ZERO => {
643                    // goto <p2> if no constraints are unsatisfied (assumed to be true)
644
645                    state.mem.program_i = p2 as usize;
646                    continue;
647                }
648
649                OP_DECR_JUMP_ZERO | OP_ELSE_EQ | OP_EQ | OP_FILTER | OP_FOUND | OP_GE | OP_GT
650                | OP_IDX_GE | OP_IDX_GT | OP_IDX_LE | OP_IDX_LT | OP_IF_NO_HOPE | OP_IF_NOT
651                | OP_IF_NOT_OPEN | OP_IF_NOT_ZERO | OP_IF_NULL_ROW | OP_IF_SMALLER
652                | OP_INCR_VACUUM | OP_IS_NULL_OR_TYPE | OP_LE | OP_LT | OP_NE | OP_NEXT
653                | OP_NO_CONFLICT | OP_NOT_EXISTS | OP_ONCE | OP_PREV | OP_PROGRAM
654                | OP_ROW_SET_READ | OP_ROW_SET_TEST | OP_SEEK_GE | OP_SEEK_GT | OP_SEEK_LE
655                | OP_SEEK_LT | OP_SEEK_ROW_ID | OP_SEEK_SCAN | OP_SEQUENCE_TEST
656                | OP_SORTER_NEXT | OP_V_FILTER | OP_V_NEXT => {
657                    // goto <p2> or next instruction (depending on actual values)
658
659                    let mut branch_state = state.new_branch(&mut branch_seq);
660                    branch_state.mem.program_i = p2 as usize;
661                    states.push(branch_state, &mut logger);
662
663                    state.mem.program_i += 1;
664                    continue;
665                }
666
667                OP_IS_NULL => {
668                    // goto <p2> if p1 is null
669
670                    //branch if maybe null
671                    let might_branch = match state.mem.r.get(&p1) {
672                        Some(r_p1) => !matches!(r_p1.map_to_nullable(), Some(false)),
673                        _ => false,
674                    };
675
676                    //nobranch if maybe not null
677                    let might_not_branch = match state.mem.r.get(&p1) {
678                        Some(r_p1) => !matches!(r_p1.map_to_datatype(), DataType::Null),
679                        _ => false,
680                    };
681
682                    if might_branch {
683                        let mut branch_state = state.new_branch(&mut branch_seq);
684                        branch_state.mem.program_i = p2 as usize;
685                        branch_state
686                            .mem
687                            .r
688                            .insert(p1, RegDataType::Single(ColumnType::default()));
689
690                        states.push(branch_state, &mut logger);
691                    }
692
693                    if might_not_branch {
694                        state.mem.program_i += 1;
695                        if let Some(RegDataType::Single(ColumnType::Single { nullable, .. })) =
696                            state.mem.r.get_mut(&p1)
697                        {
698                            *nullable = Some(false);
699                        }
700                        continue;
701                    } else {
702                        logger.add_result(state, BranchResult::Branched);
703                        break;
704                    }
705                }
706
707                OP_NOT_NULL => {
708                    // goto <p2> if p1 is not null
709
710                    let might_branch = match state.mem.r.get(&p1) {
711                        Some(r_p1) => !matches!(r_p1.map_to_datatype(), DataType::Null),
712                        _ => false,
713                    };
714
715                    let might_not_branch = match state.mem.r.get(&p1) {
716                        Some(r_p1) => !matches!(r_p1.map_to_nullable(), Some(false)),
717                        _ => false,
718                    };
719
720                    if might_branch {
721                        let mut branch_state = state.new_branch(&mut branch_seq);
722                        branch_state.mem.program_i = p2 as usize;
723                        if let Some(RegDataType::Single(ColumnType::Single { nullable, .. })) =
724                            branch_state.mem.r.get_mut(&p1)
725                        {
726                            *nullable = Some(false);
727                        }
728
729                        states.push(branch_state, &mut logger);
730                    }
731
732                    if might_not_branch {
733                        state.mem.program_i += 1;
734                        state
735                            .mem
736                            .r
737                            .insert(p1, RegDataType::Single(ColumnType::default()));
738                        continue;
739                    } else {
740                        logger.add_result(state, BranchResult::Branched);
741                        break;
742                    }
743                }
744
745                OP_MUST_BE_INT => {
746                    // if p1 can be coerced to int, continue
747                    // if p1 cannot be coerced to int, error if p2 == 0, else jump to p2
748
749                    //don't bother checking actual types, just don't branch to instruction 0
750                    if p2 != 0 {
751                        let mut branch_state = state.new_branch(&mut branch_seq);
752                        branch_state.mem.program_i = p2 as usize;
753                        states.push(branch_state, &mut logger);
754                    }
755
756                    state.mem.program_i += 1;
757                    continue;
758                }
759
760                OP_IF => {
761                    // goto <p2> if r[p1] is true (1) or r[p1] is null and p3 is nonzero
762
763                    let might_branch = match state.mem.r.get(&p1) {
764                        Some(RegDataType::Int(r_p1)) => *r_p1 != 0,
765                        _ => true,
766                    };
767
768                    let might_not_branch = match state.mem.r.get(&p1) {
769                        Some(RegDataType::Int(r_p1)) => *r_p1 == 0,
770                        _ => true,
771                    };
772
773                    if might_branch {
774                        let mut branch_state = state.new_branch(&mut branch_seq);
775                        branch_state.mem.program_i = p2 as usize;
776                        if p3 == 0 {
777                            branch_state.mem.r.insert(p1, RegDataType::Int(1));
778                        }
779
780                        states.push(branch_state, &mut logger);
781                    }
782
783                    if might_not_branch {
784                        state.mem.program_i += 1;
785                        if p3 == 0 {
786                            state.mem.r.insert(p1, RegDataType::Int(0));
787                        }
788                        continue;
789                    } else {
790                        logger.add_result(state, BranchResult::Branched);
791                        break;
792                    }
793                }
794
795                OP_IF_POS => {
796                    // goto <p2> if r[p1] is true (1) or r[p1] is null and p3 is nonzero
797
798                    // as a workaround for large offset clauses, both branches will be attempted after 1 loop
799
800                    let might_branch = match state.mem.r.get(&p1) {
801                        Some(RegDataType::Int(r_p1)) => *r_p1 >= 1,
802                        _ => true,
803                    };
804
805                    let might_not_branch = match state.mem.r.get(&p1) {
806                        Some(RegDataType::Int(r_p1)) => *r_p1 < 1,
807                        _ => true,
808                    };
809
810                    let loop_detected = state.visited[state.mem.program_i] > 1;
811                    if might_branch || loop_detected {
812                        let mut branch_state = state.new_branch(&mut branch_seq);
813                        branch_state.mem.program_i = p2 as usize;
814                        if let Some(RegDataType::Int(r_p1)) = branch_state.mem.r.get_mut(&p1) {
815                            *r_p1 -= 1;
816                        }
817                        states.push(branch_state, &mut logger);
818                    }
819
820                    if might_not_branch {
821                        state.mem.program_i += 1;
822                        continue;
823                    } else if loop_detected {
824                        state.mem.program_i += 1;
825                        if matches!(state.mem.r.get_mut(&p1), Some(RegDataType::Int(..))) {
826                            //forget the exact value, in case some later cares
827                            state.mem.r.insert(
828                                p1,
829                                RegDataType::Single(ColumnType::Single {
830                                    datatype: DataType::Integer,
831                                    nullable: Some(false),
832                                }),
833                            );
834                        }
835                        continue;
836                    } else {
837                        logger.add_result(state, BranchResult::Branched);
838                        break;
839                    }
840                }
841
842                OP_REWIND | OP_LAST | OP_SORT | OP_SORTER_SORT => {
843                    // goto <p2> if cursor p1 is empty and p2 != 0, else next instruction
844
845                    if p2 == 0 {
846                        state.mem.program_i += 1;
847                        continue;
848                    }
849
850                    if let Some(cursor) = state.mem.p.get(&p1) {
851                        if matches!(cursor.is_empty(&state.mem.t), None | Some(true)) {
852                            //only take this branch if the cursor is empty
853
854                            let mut branch_state = state.new_branch(&mut branch_seq);
855                            branch_state.mem.program_i = p2 as usize;
856
857                            if let Some(cur) = branch_state.mem.p.get(&p1) {
858                                if let Some(tab) = cur.table_mut(&mut branch_state.mem.t) {
859                                    tab.is_empty = Some(true);
860                                }
861                            }
862                            states.push(branch_state, &mut logger);
863                        }
864
865                        if matches!(cursor.is_empty(&state.mem.t), None | Some(false)) {
866                            //only take this branch if the cursor is non-empty
867                            state.mem.program_i += 1;
868                            continue;
869                        } else {
870                            logger.add_result(state, BranchResult::Branched);
871                            break;
872                        }
873                    }
874
875                    logger.add_result(state, BranchResult::Branched);
876                    break;
877                }
878
879                OP_INIT_COROUTINE => {
880                    // goto <p2> or next instruction (depending on actual values)
881
882                    state.mem.r.insert(p1, RegDataType::Int(p3));
883
884                    if p2 != 0 {
885                        state.mem.program_i = p2 as usize;
886                    } else {
887                        state.mem.program_i += 1;
888                    }
889                    continue;
890                }
891
892                OP_END_COROUTINE => {
893                    // jump to p2 of the yield instruction pointed at by register p1
894
895                    if let Some(RegDataType::Int(yield_i)) = state.mem.r.get(&p1) {
896                        if let Some((_, yield_op, _, yield_p2, _, _)) =
897                            program.get(*yield_i as usize)
898                        {
899                            if OP_YIELD == yield_op.as_str() {
900                                state.mem.program_i = (*yield_p2) as usize;
901                                state.mem.r.remove(&p1);
902                                continue;
903                            } else {
904                                logger.add_result(state, BranchResult::Error);
905                                break;
906                            }
907                        } else {
908                            logger.add_result(state, BranchResult::Error);
909                            break;
910                        }
911                    } else {
912                        logger.add_result(state, BranchResult::Error);
913                        break;
914                    }
915                }
916
917                OP_RETURN => {
918                    // jump to the instruction after the instruction pointed at by register p1
919
920                    if let Some(RegDataType::Int(return_i)) = state.mem.r.get(&p1) {
921                        state.mem.program_i = (*return_i + 1) as usize;
922                        state.mem.r.remove(&p1);
923                        continue;
924                    } else if p3 == 1 {
925                        state.mem.program_i += 1;
926                        continue;
927                    } else {
928                        logger.add_result(state, BranchResult::Error);
929                        break;
930                    }
931                }
932
933                OP_YIELD => {
934                    // jump to p2 of the yield instruction pointed at by register p1, store prior instruction in p1
935
936                    if let Some(RegDataType::Int(yield_i)) = state.mem.r.get_mut(&p1) {
937                        let program_i: usize = state.mem.program_i;
938
939                        //if yielding to a yield operation, go to the NEXT instruction after that instruction
940                        if program
941                            .get(*yield_i as usize)
942                            .map(|(_, yield_op, _, _, _, _)| yield_op.as_str())
943                            == Some(OP_YIELD)
944                        {
945                            state.mem.program_i = (*yield_i + 1) as usize;
946                            *yield_i = program_i as i64;
947                            continue;
948                        } else {
949                            state.mem.program_i = *yield_i as usize;
950                            *yield_i = program_i as i64;
951                            continue;
952                        }
953                    } else {
954                        logger.add_result(state, BranchResult::Error);
955                        break;
956                    }
957                }
958
959                OP_JUMP => {
960                    // goto one of <p1>, <p2>, or <p3> based on the result of a prior compare
961
962                    let mut branch_state = state.new_branch(&mut branch_seq);
963                    branch_state.mem.program_i = p1 as usize;
964                    states.push(branch_state, &mut logger);
965
966                    let mut branch_state = state.new_branch(&mut branch_seq);
967                    branch_state.mem.program_i = p2 as usize;
968                    states.push(branch_state, &mut logger);
969
970                    let mut branch_state = state.new_branch(&mut branch_seq);
971                    branch_state.mem.program_i = p3 as usize;
972                    states.push(branch_state, &mut logger);
973                }
974
975                OP_COLUMN => {
976                    //Get the row stored at p1, or NULL; get the column stored at p2, or NULL
977                    let value: ColumnType = state
978                        .mem
979                        .p
980                        .get(&p1)
981                        .and_then(|c| c.columns_ref(&state.mem.t, &state.mem.r))
982                        .and_then(|cc| cc.get(&p2))
983                        .cloned()
984                        .unwrap_or_default();
985
986                    // insert into p3 the datatype of the col
987                    state.mem.r.insert(p3, RegDataType::Single(value));
988                }
989
990                OP_SEQUENCE => {
991                    //Copy sequence number from cursor p1 to register p2, increment cursor p1 sequence number
992
993                    //Cursor emulation doesn't sequence value, but it is an int
994                    state.mem.r.insert(
995                        p2,
996                        RegDataType::Single(ColumnType::Single {
997                            datatype: DataType::Integer,
998                            nullable: Some(false),
999                        }),
1000                    );
1001                }
1002
1003                OP_ROW_DATA | OP_SORTER_DATA => {
1004                    //Get entire row from cursor p1, store it into register p2
1005                    if let Some(record) = state
1006                        .mem
1007                        .p
1008                        .get(&p1)
1009                        .map(|c| c.columns(&state.mem.t, &state.mem.r))
1010                    {
1011                        state
1012                            .mem
1013                            .r
1014                            .insert(p2, RegDataType::Single(ColumnType::Record(record)));
1015                    } else {
1016                        state
1017                            .mem
1018                            .r
1019                            .insert(p2, RegDataType::Single(ColumnType::Record(IntMap::new())));
1020                    }
1021                }
1022
1023                OP_MAKE_RECORD => {
1024                    // p3 = Record([p1 .. p1 + p2])
1025                    let mut record = Vec::with_capacity(p2 as usize);
1026                    for reg in p1..p1 + p2 {
1027                        record.push(
1028                            state
1029                                .mem
1030                                .r
1031                                .get(&reg)
1032                                .map(|d| d.map_to_columntype())
1033                                .unwrap_or(ColumnType::default()),
1034                        );
1035                    }
1036                    state.mem.r.insert(
1037                        p3,
1038                        RegDataType::Single(ColumnType::Record(IntMap::from_dense_record(&record))),
1039                    );
1040                }
1041
1042                OP_INSERT | OP_IDX_INSERT | OP_SORTER_INSERT => {
1043                    if let Some(RegDataType::Single(columntype)) = state.mem.r.get(&p2) {
1044                        match columntype {
1045                            ColumnType::Record(record) => {
1046                                if let Some(TableDataType { cols, is_empty }) = state
1047                                    .mem
1048                                    .p
1049                                    .get(&p1)
1050                                    .and_then(|cur| cur.table_mut(&mut state.mem.t))
1051                                {
1052                                    // Insert the record into wherever pointer p1 is
1053                                    *cols = record.clone();
1054                                    *is_empty = Some(false);
1055                                }
1056                            }
1057                            ColumnType::Single {
1058                                datatype: DataType::Null,
1059                                nullable: _,
1060                            } => {
1061                                if let Some(TableDataType { is_empty, .. }) = state
1062                                    .mem
1063                                    .p
1064                                    .get(&p1)
1065                                    .and_then(|cur| cur.table_mut(&mut state.mem.t))
1066                                {
1067                                    // Insert a null record into wherever pointer p1 is
1068                                    *is_empty = Some(false);
1069                                }
1070                            }
1071                            _ => {}
1072                        }
1073                    }
1074                    //Noop if the register p2 isn't a record, or if pointer p1 does not exist
1075                }
1076
1077                OP_DELETE => {
1078                    // delete a record from cursor p1
1079                    if let Some(TableDataType { is_empty, .. }) = state
1080                        .mem
1081                        .p
1082                        .get(&p1)
1083                        .and_then(|cur| cur.table_mut(&mut state.mem.t))
1084                    {
1085                        if *is_empty == Some(false) {
1086                            *is_empty = None; //the cursor might be empty now
1087                        }
1088                    }
1089                }
1090
1091                OP_OPEN_PSEUDO => {
1092                    // Create a cursor p1 aliasing the record from register p2
1093                    state.mem.p.insert(p1, CursorDataType::Pseudo(p2));
1094                }
1095
1096                OP_OPEN_DUP => {
1097                    if let Some(cur) = state.mem.p.get(&p2) {
1098                        state.mem.p.insert(p1, cur.clone());
1099                    }
1100                }
1101
1102                OP_OPEN_READ | OP_OPEN_WRITE => {
1103                    //Create a new pointer which is referenced by p1, take column metadata from db schema if found
1104                    let table_info = if p3 == 0 || p3 == 1 {
1105                        if let Some(columns) = root_block_cols.get(&(p3, p2)) {
1106                            TableDataType {
1107                                cols: columns.clone(),
1108                                is_empty: None,
1109                            }
1110                        } else {
1111                            TableDataType {
1112                                cols: IntMap::new(),
1113                                is_empty: None,
1114                            }
1115                        }
1116                    } else {
1117                        TableDataType {
1118                            cols: IntMap::new(),
1119                            is_empty: None,
1120                        }
1121                    };
1122
1123                    state.mem.t.insert(state.mem.program_i as i64, table_info);
1124                    state
1125                        .mem
1126                        .p
1127                        .insert(p1, CursorDataType::Normal(state.mem.program_i as i64));
1128                }
1129
1130                OP_OPEN_EPHEMERAL | OP_OPEN_AUTOINDEX | OP_SORTER_OPEN => {
1131                    //Create a new pointer which is referenced by p1
1132                    let table_info = TableDataType {
1133                        cols: IntMap::from_elem(ColumnType::null(), p2 as usize),
1134                        is_empty: Some(true),
1135                    };
1136
1137                    state.mem.t.insert(state.mem.program_i as i64, table_info);
1138                    state
1139                        .mem
1140                        .p
1141                        .insert(p1, CursorDataType::Normal(state.mem.program_i as i64));
1142                }
1143
1144                OP_VARIABLE => {
1145                    // r[p2] = <value of variable>
1146                    state
1147                        .mem
1148                        .r
1149                        .insert(p2, RegDataType::Single(ColumnType::null()));
1150                }
1151
1152                // if there is a value in p3, and the query passes, then
1153                // we know that it is not nullable
1154                OP_HALT_IF_NULL => {
1155                    if let Some(RegDataType::Single(ColumnType::Single { nullable, .. })) =
1156                        state.mem.r.get_mut(&p3)
1157                    {
1158                        *nullable = Some(false);
1159                    }
1160                }
1161
1162                OP_FUNCTION => {
1163                    // r[p3] = func( _ ), registered function name is in p4
1164                    match from_utf8(p4).map_err(Error::protocol)? {
1165                        "last_insert_rowid(0)" => {
1166                            // last_insert_rowid() -> INTEGER
1167                            state.mem.r.insert(
1168                                p3,
1169                                RegDataType::Single(ColumnType::Single {
1170                                    datatype: DataType::Integer,
1171                                    nullable: Some(false),
1172                                }),
1173                            );
1174                        }
1175                        "date(-1)" | "time(-1)" | "datetime(-1)" | "strftime(-1)" => {
1176                            // date|time|datetime|strftime(...) -> TEXT
1177                            state.mem.r.insert(
1178                                p3,
1179                                RegDataType::Single(ColumnType::Single {
1180                                    datatype: DataType::Text,
1181                                    nullable: Some(p2 != 0), //never a null result if no argument provided
1182                                }),
1183                            );
1184                        }
1185                        "julianday(-1)" => {
1186                            // julianday(...) -> REAL
1187                            state.mem.r.insert(
1188                                p3,
1189                                RegDataType::Single(ColumnType::Single {
1190                                    datatype: DataType::Float,
1191                                    nullable: Some(p2 != 0), //never a null result if no argument provided
1192                                }),
1193                            );
1194                        }
1195                        "unixepoch(-1)" => {
1196                            // unixepoch(p2...) -> INTEGER
1197                            state.mem.r.insert(
1198                                p3,
1199                                RegDataType::Single(ColumnType::Single {
1200                                    datatype: DataType::Integer,
1201                                    nullable: Some(p2 != 0), //never a null result if no argument provided
1202                                }),
1203                            );
1204                        }
1205
1206                        _ => logger.add_unknown_operation(state.mem.program_i),
1207                    }
1208                }
1209
1210                OP_NULL_ROW => {
1211                    // all columns in cursor X are potentially nullable
1212                    if let Some(cols) = state
1213                        .mem
1214                        .p
1215                        .get_mut(&p1)
1216                        .and_then(|c| c.columns_mut(&mut state.mem.t, &mut state.mem.r))
1217                    {
1218                        for col in cols.values_mut() {
1219                            if let ColumnType::Single {
1220                                ref mut nullable, ..
1221                            } = col
1222                            {
1223                                *nullable = Some(true);
1224                            }
1225                        }
1226                    }
1227                    //else we don't know about the cursor
1228                }
1229
1230                OP_AGG_STEP | OP_AGG_VALUE => {
1231                    //assume that AGG_FINAL will be called
1232                    let p4 = from_utf8(p4).map_err(Error::protocol)?;
1233
1234                    if p4.starts_with("count(")
1235                        || p4.starts_with("row_number(")
1236                        || p4.starts_with("rank(")
1237                        || p4.starts_with("dense_rank(")
1238                        || p4.starts_with("ntile(")
1239                    {
1240                        // count(_) -> INTEGER
1241                        state.mem.r.insert(
1242                            p3,
1243                            RegDataType::Single(ColumnType::Single {
1244                                datatype: DataType::Integer,
1245                                nullable: Some(false),
1246                            }),
1247                        );
1248                    } else if p4.starts_with("percent_rank(") || p4.starts_with("cume_dist") {
1249                        // percent_rank(_) -> REAL
1250                        state.mem.r.insert(
1251                            p3,
1252                            RegDataType::Single(ColumnType::Single {
1253                                datatype: DataType::Float,
1254                                nullable: Some(false),
1255                            }),
1256                        );
1257                    } else if p4.starts_with("sum(") {
1258                        if let Some(r_p2) = state.mem.r.get(&p2) {
1259                            let datatype = match r_p2.map_to_datatype() {
1260                                // The result of a `SUM()` can be arbitrarily large
1261                                DataType::Integer | DataType::Int4 | DataType::Bool => {
1262                                    DataType::Integer
1263                                }
1264                                _ => DataType::Float,
1265                            };
1266                            let nullable = r_p2.map_to_nullable();
1267                            state.mem.r.insert(
1268                                p3,
1269                                RegDataType::Single(ColumnType::Single { datatype, nullable }),
1270                            );
1271                        }
1272                    } else if p4.starts_with("lead(") || p4.starts_with("lag(") {
1273                        if let Some(r_p2) = state.mem.r.get(&p2) {
1274                            let datatype = r_p2.map_to_datatype();
1275                            state.mem.r.insert(
1276                                p3,
1277                                RegDataType::Single(ColumnType::Single {
1278                                    datatype,
1279                                    nullable: Some(true),
1280                                }),
1281                            );
1282                        }
1283                    } else if let Some(v) = state.mem.r.get(&p2).cloned() {
1284                        // r[p3] = AGG ( r[p2] )
1285                        state.mem.r.insert(p3, v);
1286                    }
1287                }
1288
1289                OP_AGG_FINAL => {
1290                    let p4 = from_utf8(p4).map_err(Error::protocol)?;
1291
1292                    if p4.starts_with("count(")
1293                        || p4.starts_with("row_number(")
1294                        || p4.starts_with("rank(")
1295                        || p4.starts_with("dense_rank(")
1296                        || p4.starts_with("ntile(")
1297                    {
1298                        // count(_) -> INTEGER
1299                        state.mem.r.insert(
1300                            p1,
1301                            RegDataType::Single(ColumnType::Single {
1302                                datatype: DataType::Integer,
1303                                nullable: Some(false),
1304                            }),
1305                        );
1306                    } else if p4.starts_with("percent_rank(") || p4.starts_with("cume_dist") {
1307                        // percent_rank(_) -> REAL
1308                        state.mem.r.insert(
1309                            p3,
1310                            RegDataType::Single(ColumnType::Single {
1311                                datatype: DataType::Float,
1312                                nullable: Some(false),
1313                            }),
1314                        );
1315                    } else if p4.starts_with("lead(") || p4.starts_with("lag(") {
1316                        if let Some(r_p2) = state.mem.r.get(&p2) {
1317                            let datatype = r_p2.map_to_datatype();
1318                            state.mem.r.insert(
1319                                p3,
1320                                RegDataType::Single(ColumnType::Single {
1321                                    datatype,
1322                                    nullable: Some(true),
1323                                }),
1324                            );
1325                        }
1326                    }
1327                }
1328
1329                OP_CAST => {
1330                    // affinity(r[p1])
1331                    if let Some(v) = state.mem.r.get_mut(&p1) {
1332                        *v = RegDataType::Single(ColumnType::Single {
1333                            datatype: affinity_to_type(p2 as u8),
1334                            nullable: v.map_to_nullable(),
1335                        });
1336                    }
1337                }
1338
1339                OP_SCOPY | OP_INT_COPY => {
1340                    // r[p2] = r[p1]
1341                    if let Some(v) = state.mem.r.get(&p1).cloned() {
1342                        state.mem.r.insert(p2, v);
1343                    }
1344                }
1345
1346                OP_COPY => {
1347                    // r[p2..=p2+p3] = r[p1..=p1+p3]
1348                    if p3 >= 0 {
1349                        for i in 0..=p3 {
1350                            let src = p1 + i;
1351                            let dst = p2 + i;
1352                            if let Some(v) = state.mem.r.get(&src).cloned() {
1353                                state.mem.r.insert(dst, v);
1354                            }
1355                        }
1356                    }
1357                }
1358
1359                OP_MOVE => {
1360                    // r[p2..p2+p3] = r[p1..p1+p3]; r[p1..p1+p3] = null
1361                    if p3 >= 1 {
1362                        for i in 0..p3 {
1363                            let src = p1 + i;
1364                            let dst = p2 + i;
1365                            if let Some(v) = state.mem.r.get(&src).cloned() {
1366                                state.mem.r.insert(dst, v);
1367                                state
1368                                    .mem
1369                                    .r
1370                                    .insert(src, RegDataType::Single(ColumnType::null()));
1371                            }
1372                        }
1373                    }
1374                }
1375
1376                OP_INTEGER => {
1377                    // r[p2] = p1
1378                    state.mem.r.insert(p2, RegDataType::Int(p1));
1379                }
1380
1381                OP_BLOB | OP_COUNT | OP_REAL | OP_STRING8 | OP_ROWID | OP_NEWROWID => {
1382                    // r[p2] = <value of constant>
1383                    state.mem.r.insert(
1384                        p2,
1385                        RegDataType::Single(ColumnType::Single {
1386                            datatype: opcode_to_type(opcode),
1387                            nullable: Some(false),
1388                        }),
1389                    );
1390                }
1391
1392                OP_NOT => {
1393                    // r[p2] = NOT r[p1]
1394                    if let Some(a) = state.mem.r.get(&p1).cloned() {
1395                        state.mem.r.insert(p2, a);
1396                    }
1397                }
1398
1399                OP_NULL => {
1400                    // r[p2..p3] = null
1401                    let idx_range = if p2 < p3 { p2..=p3 } else { p2..=p2 };
1402
1403                    for idx in idx_range {
1404                        state
1405                            .mem
1406                            .r
1407                            .insert(idx, RegDataType::Single(ColumnType::null()));
1408                    }
1409                }
1410
1411                OP_OR | OP_AND | OP_BIT_AND | OP_BIT_OR | OP_SHIFT_LEFT | OP_SHIFT_RIGHT
1412                | OP_ADD | OP_SUBTRACT | OP_MULTIPLY | OP_DIVIDE | OP_REMAINDER | OP_CONCAT => {
1413                    // r[p3] = r[p1] + r[p2]
1414                    let value = match (state.mem.r.get(&p1), state.mem.r.get(&p2)) {
1415                        (Some(a), Some(b)) => RegDataType::Single(ColumnType::Single {
1416                            datatype: if matches!(a.map_to_datatype(), DataType::Null) {
1417                                b.map_to_datatype()
1418                            } else {
1419                                a.map_to_datatype()
1420                            },
1421                            nullable: match (a.map_to_nullable(), b.map_to_nullable()) {
1422                                (Some(a_n), Some(b_n)) => Some(a_n | b_n),
1423                                (Some(a_n), None) => Some(a_n),
1424                                (None, Some(b_n)) => Some(b_n),
1425                                (None, None) => None,
1426                            },
1427                        }),
1428                        (Some(v), None) => RegDataType::Single(ColumnType::Single {
1429                            datatype: v.map_to_datatype(),
1430                            nullable: None,
1431                        }),
1432                        (None, Some(v)) => RegDataType::Single(ColumnType::Single {
1433                            datatype: v.map_to_datatype(),
1434                            nullable: None,
1435                        }),
1436                        _ => RegDataType::default(),
1437                    };
1438
1439                    state.mem.r.insert(p3, value);
1440                }
1441
1442                OP_OFFSET_LIMIT => {
1443                    // r[p2] = if r[p2] < 0 { r[p1] } else if r[p1]<0 { -1 } else { r[p1] + r[p3] }
1444                    state.mem.r.insert(
1445                        p2,
1446                        RegDataType::Single(ColumnType::Single {
1447                            datatype: DataType::Integer,
1448                            nullable: Some(false),
1449                        }),
1450                    );
1451                }
1452
1453                OP_RESULT_ROW => {
1454                    // output = r[p1 .. p1 + p2]
1455                    let result: Vec<_> = (p1..p1 + p2)
1456                        .map(|i| {
1457                            state
1458                                .mem
1459                                .r
1460                                .get(&i)
1461                                .map(RegDataType::map_to_columntype)
1462                                .unwrap_or_default()
1463                        })
1464                        .collect();
1465
1466                    let mut branch_state = state.new_branch(&mut branch_seq);
1467                    branch_state.mem.program_i += 1;
1468                    states.push(branch_state, &mut logger);
1469
1470                    logger.add_result(
1471                        state,
1472                        BranchResult::Result(IntMap::from_dense_record(&result)),
1473                    );
1474
1475                    result_states.push(result);
1476                    break;
1477                }
1478
1479                OP_HALT => {
1480                    logger.add_result(state, BranchResult::Halt);
1481                    break;
1482                }
1483
1484                _ => {
1485                    // ignore unsupported operations
1486                    // if we fail to find an r later, we just give up
1487                    logger.add_unknown_operation(state.mem.program_i);
1488                }
1489            }
1490
1491            state.mem.program_i += 1;
1492        }
1493    }
1494
1495    let mut output: Vec<Option<SqliteTypeInfo>> = Vec::new();
1496    let mut nullable: Vec<Option<bool>> = Vec::new();
1497
1498    while let Some(result) = result_states.pop() {
1499        // find the datatype info from each ResultRow execution
1500        for (idx, this_col) in result.into_iter().enumerate() {
1501            let this_type = this_col.map_to_datatype();
1502            let this_nullable = this_col.map_to_nullable();
1503            if output.len() == idx {
1504                output.push(Some(SqliteTypeInfo(this_type)));
1505            } else if output[idx].is_none()
1506                || matches!(output[idx], Some(SqliteTypeInfo(DataType::Null)))
1507                    && !matches!(this_type, DataType::Null)
1508            {
1509                output[idx] = Some(SqliteTypeInfo(this_type));
1510            }
1511
1512            if nullable.len() == idx {
1513                nullable.push(this_nullable);
1514            } else if let Some(ref mut null) = nullable[idx] {
1515                //if any ResultRow's column is nullable, the final result is nullable
1516                if let Some(this_null) = this_nullable {
1517                    *null |= this_null;
1518                }
1519            } else {
1520                nullable[idx] = this_nullable;
1521            }
1522        }
1523    }
1524
1525    let output = output
1526        .into_iter()
1527        .map(|o| o.unwrap_or(SqliteTypeInfo(DataType::Null)))
1528        .collect();
1529
1530    Ok((output, nullable))
1531}
1532
1533#[test]
1534fn test_root_block_columns_has_types() {
1535    use crate::SqliteConnectOptions;
1536    use std::str::FromStr;
1537    let conn_options = SqliteConnectOptions::from_str("sqlite::memory:").unwrap();
1538    let mut conn = super::EstablishParams::from_options(&conn_options)
1539        .unwrap()
1540        .establish()
1541        .unwrap();
1542
1543    assert!(execute::iter(
1544        &mut conn,
1545        r"CREATE TABLE t(a INTEGER PRIMARY KEY, b_null TEXT NULL, b TEXT NOT NULL);",
1546        None,
1547        false
1548    )
1549    .unwrap()
1550    .next()
1551    .is_some());
1552    assert!(
1553        execute::iter(&mut conn, r"CREATE INDEX i1 on t (a,b_null);", None, false)
1554            .unwrap()
1555            .next()
1556            .is_some()
1557    );
1558    assert!(execute::iter(
1559        &mut conn,
1560        r"CREATE UNIQUE INDEX i2 on t (a,b_null);",
1561        None,
1562        false
1563    )
1564    .unwrap()
1565    .next()
1566    .is_some());
1567    assert!(execute::iter(
1568        &mut conn,
1569        r"CREATE TABLE t2(a INTEGER NOT NULL, b_null NUMERIC NULL, b NUMERIC NOT NULL);",
1570        None,
1571        false
1572    )
1573    .unwrap()
1574    .next()
1575    .is_some());
1576    assert!(execute::iter(
1577        &mut conn,
1578        r"CREATE INDEX t2i1 on t2 (a,b_null);",
1579        None,
1580        false
1581    )
1582    .unwrap()
1583    .next()
1584    .is_some());
1585    assert!(execute::iter(
1586        &mut conn,
1587        r"CREATE UNIQUE INDEX t2i2 on t2 (a,b);",
1588        None,
1589        false
1590    )
1591    .unwrap()
1592    .next()
1593    .is_some());
1594
1595    assert!(execute::iter(
1596        &mut conn,
1597        r"CREATE TEMPORARY TABLE t3(a TEXT PRIMARY KEY, b REAL NOT NULL, b_null REAL NULL);",
1598        None,
1599        false
1600    )
1601    .unwrap()
1602    .next()
1603    .is_some());
1604
1605    let table_block_nums: HashMap<String, (i64,i64)> = execute::iter(
1606        &mut conn,
1607        r"select name, 0 db_seq, rootpage from main.sqlite_schema UNION ALL select name, 1 db_seq, rootpage from temp.sqlite_schema",
1608        None,
1609        false,
1610    )
1611    .unwrap()
1612    .filter_map(|res| res.map(|either| either.right()).transpose())
1613    .map(|row| FromRow::from_row(row.as_ref().unwrap()))
1614    .map(|row| row.map(|(name,seq,block)|(name,(seq,block))))
1615    .collect::<Result<HashMap<_, _>, Error>>()
1616    .unwrap();
1617
1618    let root_block_cols = root_block_columns(&mut conn).unwrap();
1619
1620    // there should be 7 tables/indexes created explicitly, plus 1 autoindex for t3
1621    assert_eq!(8, root_block_cols.len());
1622
1623    //prove that we have some information for each table & index
1624    for (name, db_seq_block) in dbg!(&table_block_nums) {
1625        assert!(
1626            root_block_cols.contains_key(db_seq_block),
1627            "{:?}",
1628            (name, db_seq_block)
1629        );
1630    }
1631
1632    //prove that each block has the correct information
1633    {
1634        let table_db_block = table_block_nums["t"];
1635        assert_eq!(
1636            Some(&ColumnType::Single {
1637                datatype: DataType::Integer,
1638                nullable: Some(true) //sqlite primary key columns are nullable unless declared not null
1639            }),
1640            root_block_cols[&table_db_block].get(&0)
1641        );
1642        assert_eq!(
1643            Some(&ColumnType::Single {
1644                datatype: DataType::Text,
1645                nullable: Some(true)
1646            }),
1647            root_block_cols[&table_db_block].get(&1)
1648        );
1649        assert_eq!(
1650            Some(&ColumnType::Single {
1651                datatype: DataType::Text,
1652                nullable: Some(false)
1653            }),
1654            root_block_cols[&table_db_block].get(&2)
1655        );
1656    }
1657
1658    {
1659        let table_db_block = table_block_nums["i1"];
1660        assert_eq!(
1661            Some(&ColumnType::Single {
1662                datatype: DataType::Integer,
1663                nullable: Some(true) //sqlite primary key columns are nullable unless declared not null
1664            }),
1665            root_block_cols[&table_db_block].get(&0)
1666        );
1667        assert_eq!(
1668            Some(&ColumnType::Single {
1669                datatype: DataType::Text,
1670                nullable: Some(true)
1671            }),
1672            root_block_cols[&table_db_block].get(&1)
1673        );
1674    }
1675
1676    {
1677        let table_db_block = table_block_nums["i2"];
1678        assert_eq!(
1679            Some(&ColumnType::Single {
1680                datatype: DataType::Integer,
1681                nullable: Some(true) //sqlite primary key columns are nullable unless declared not null
1682            }),
1683            root_block_cols[&table_db_block].get(&0)
1684        );
1685        assert_eq!(
1686            Some(&ColumnType::Single {
1687                datatype: DataType::Text,
1688                nullable: Some(true)
1689            }),
1690            root_block_cols[&table_db_block].get(&1)
1691        );
1692    }
1693
1694    {
1695        let table_db_block = table_block_nums["t2"];
1696        assert_eq!(
1697            Some(&ColumnType::Single {
1698                datatype: DataType::Integer,
1699                nullable: Some(false)
1700            }),
1701            root_block_cols[&table_db_block].get(&0)
1702        );
1703        assert_eq!(
1704            Some(&ColumnType::Single {
1705                datatype: DataType::Null,
1706                nullable: Some(true)
1707            }),
1708            root_block_cols[&table_db_block].get(&1)
1709        );
1710        assert_eq!(
1711            Some(&ColumnType::Single {
1712                datatype: DataType::Null,
1713                nullable: Some(false)
1714            }),
1715            root_block_cols[&table_db_block].get(&2)
1716        );
1717    }
1718
1719    {
1720        let table_db_block = table_block_nums["t2i1"];
1721        assert_eq!(
1722            Some(&ColumnType::Single {
1723                datatype: DataType::Integer,
1724                nullable: Some(false)
1725            }),
1726            root_block_cols[&table_db_block].get(&0)
1727        );
1728        assert_eq!(
1729            Some(&ColumnType::Single {
1730                datatype: DataType::Null,
1731                nullable: Some(true)
1732            }),
1733            root_block_cols[&table_db_block].get(&1)
1734        );
1735    }
1736
1737    {
1738        let table_db_block = table_block_nums["t2i2"];
1739        assert_eq!(
1740            Some(&ColumnType::Single {
1741                datatype: DataType::Integer,
1742                nullable: Some(false)
1743            }),
1744            root_block_cols[&table_db_block].get(&0)
1745        );
1746        assert_eq!(
1747            Some(&ColumnType::Single {
1748                datatype: DataType::Null,
1749                nullable: Some(false)
1750            }),
1751            root_block_cols[&table_db_block].get(&1)
1752        );
1753    }
1754
1755    {
1756        let table_db_block = table_block_nums["t3"];
1757        assert_eq!(
1758            Some(&ColumnType::Single {
1759                datatype: DataType::Text,
1760                nullable: Some(true)
1761            }),
1762            root_block_cols[&table_db_block].get(&0)
1763        );
1764        assert_eq!(
1765            Some(&ColumnType::Single {
1766                datatype: DataType::Float,
1767                nullable: Some(false)
1768            }),
1769            root_block_cols[&table_db_block].get(&1)
1770        );
1771        assert_eq!(
1772            Some(&ColumnType::Single {
1773                datatype: DataType::Float,
1774                nullable: Some(true)
1775            }),
1776            root_block_cols[&table_db_block].get(&2)
1777        );
1778    }
1779}