Brainfuck interpreter in SQL

bf.sql

--
-- Brainfuck interpreter in SQL,
-- specifically SQLite dialect.
-- Code is the code string.
-- Input is in the inp string.
--

--EXPLAIN
--QUERY PLAN
WITH RECURSIVE
    code(s) AS
    (
        --VALUES('++++++++++>++++<[[->>+<<]]')
        --VALUES('>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.-.,.')
        --VALUES('++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.') -- Hello world!
        VALUES('>++++++++[-<+++++++++>]<.>>+>-[+]++>++>+++[>[->+++<<+++>]<<]>-----.>->+++..+++.>-.<<+[>[+>+]>>]<--------------.>>.+++.------.--------.>+.>+.')
        --VALUES('--<-<<+[+[<+>--->->->-<<<]>]<<--.<++++++.<<-..<<.<+.>>.>>.<<<.+++.>>.>>-.<<<+.') -- Another Hello world!
        --VALUES('+[[->]-[-<]>-]>.>>>>.<<<<-.>>-.>.<<.>>>>-.<<<<<++.>>++.')
    ),
    inp(s) AS
    (
        VALUES('xxx')
    ),
    nibble(ni, nh) AS
    (
        SELECT
            0,
            '0'
        UNION ALL
        SELECT
            ni + 1,
            CASE WHEN ni + 1 < 10 THEN char(ni + 1 + 0x30) -- 0x30 = '0'
                 ELSE char(ni + 1 + 0x41 - 10)             -- 0x41 = 'A'
            END AS nh
        FROM nibble
        LIMIT 16
    ),
    asciitable(i, c, h) AS
    (
        SELECT
            0,
            char(0),
            '00'
        UNION ALL
        SELECT
            i + 1,
            char(i + 1),
            CASE WHEN i + 1 < 128 THEN hex(char(i + 1))
                 ELSE (SELECT nh FROM nibble WHERE ni = ((i + 1) / 16)) ||
                      (SELECT nh FROM nibble WHERE ni = ((i + 1) % 16))
            END AS h
        FROM asciitable
        LIMIT 256
    ),
    plus_table(id, pinp, poutp) AS
    (
        SELECT
            0,
            '00',
            '01'
        UNION ALL
        SELECT
            id + 1,
            (SELECT h FROM asciitable WHERE i = id + 1),
            CASE WHEN id + 1 = 255 THEN '00'
                 ELSE (SELECT h FROM asciitable WHERE i = id + 2) -- id + 2 = (id + 1) + 1
            END AS poutp
        FROM plus_table
        LIMIT 256
    ),
    minus_table(id, minp, moutp) AS
    (
        SELECT
            0,
            '00',
            'FF'
        UNION ALL
        SELECT
            id + 1,
            (SELECT h FROM asciitable WHERE i = id + 1),
            (SELECT h FROM asciitable WHERE i = id) -- id = (id + 1) - 1
        FROM minus_table
        LIMIT 256
    ),
    while_opening_search(i, ci) AS
    (
        SELECT
            instr((SELECT s FROM code), '[') AS i,
            instr((SELECT s FROM code), '[') AS ci
        UNION ALL
        SELECT
            i + instr(substr((SELECT s FROM code), i + 1), '[') AS i,
            instr(substr((SELECT s FROM code), i + 1), '[') AS ci
        FROM while_opening_search
        WHERE ci > 0
    ),
    while_opening(i) AS
    (
        SELECT i
        FROM while_opening_search
        WHERE ci > 0
    ),
    while_closing_search(i, ci) AS
    (
        SELECT
            instr((SELECT s FROM code), ']') AS i,
            instr((SELECT s FROM code), ']') AS ci
        UNION ALL
        SELECT
            i + instr(substr((SELECT s FROM code), i + 1), ']') AS i,
            instr(substr((SELECT s FROM code), i + 1), ']') AS ci
        FROM while_closing_search
        WHERE ci > 0
    ),
    while_closing(i) AS
    (
        SELECT i
        FROM while_closing_search
        WHERE ci > 0
    ),
    while_table(wi, wo) AS
    (
        SELECT
            wo.i,
            wc.i
        FROM while_opening AS wo
        CROSS JOIN while_closing AS wc
        WHERE (SELECT COUNT(i)
                FROM while_opening
                WHERE i > wo.i
                AND i < wc.i) = (SELECT COUNT(i)
                                    FROM while_closing
                                    WHERE i > wo.i
                                    AND i < wc.i)
        AND wc.i > wo.i
        GROUP BY wo.i
        HAVING MIN(wc.i - wo.i)
    ),
    memory(v, l) AS
    (
        SELECT
            '00',
            length('00')
        UNION ALL
        SELECT
            v || '00',
            length(v || '00')
        FROM memory
        LIMIT 100  -- 30000 -- normally
    ),
    state(step, code_idx, mem, mem_idx, inp_idx, outp) AS
    (
        SELECT
            1,
            1,
            (SELECT v FROM memory ORDER BY l DESC LIMIT 1), -- Longest memory string
            1,
            1,
            ''
        UNION ALL
        SELECT
            -- Step
            step + 1,
            -- Code index code_idx
            CASE (SELECT substr(s, code_idx, 1) FROM code)
                WHEN '[' THEN CASE substr(mem, mem_idx, 2)
                                  WHEN '00' THEN (SELECT wo + 1 FROM while_table WHERE wi = code_idx)
                                  ELSE code_idx + 1
                              END
                WHEN ']' THEN CASE substr(mem, mem_idx, 2)
                                  WHEN '00' THEN code_idx + 1
                                  ELSE (SELECT wi + 1 FROM while_table WHERE wo = code_idx)
                              END
                ELSE code_idx + 1
            END AS code_idx,
            -- Memory mem
            CASE (SELECT substr(s, code_idx, 1) FROM code)
                WHEN '+' THEN substr(mem, 1, mem_idx - 1) ||
                              (SELECT poutp FROM plus_table WHERE pinp = substr(mem, mem_idx, 2)) ||
                              substr(mem, mem_idx + 2)
                WHEN '-' THEN substr(mem, 1, mem_idx - 1) ||
                              (SELECT moutp FROM minus_table WHERE minp = substr(mem, mem_idx, 2)) ||
                              substr(mem, mem_idx + 2)
                WHEN ',' THEN substr(mem, 1, mem_idx - 1) ||
                              (SELECT h FROM asciitable WHERE c = (SELECT substr(s, inp_idx, 1) FROM inp)) ||
                              substr(mem, mem_idx + 2)
                ELSE mem
            END AS mem,
            -- Memory index mem_idx
            CASE (SELECT substr(s, code_idx, 1) FROM code)
                WHEN '<' THEN CASE mem_idx
                                  WHEN 1 THEN length(mem) - 1 -- Memory wrapping
                                  ELSE mem_idx - 2
                              END
                WHEN '>' THEN CASE mem_idx
                                  WHEN length(mem) - 1 THEN 1 -- Memory wrapping
                                  ELSE mem_idx + 2
                              END
                ELSE mem_idx
            END AS mem_idx,
            -- Input index inp_idx
            CASE (SELECT substr(s, code_idx, 1) FROM code)
                WHEN ',' THEN inp_idx + 1
                ELSE inp_idx
            END AS inp_idx,
            -- Output outp
            CASE (SELECT substr(s, code_idx, 1) FROM code)
                WHEN '.' THEN outp || (SELECT c FROM asciitable WHERE h = substr(mem, mem_idx, 2))
                ELSE outp
            END AS outp
        FROM state
        WHERE code_idx BETWEEN 1 AND (SELECT length(s) FROM code)
        AND mem_idx BETWEEN 1 AND 60000                       -- 60000 = 30000 * 2 (nibbles)
    )
SELECT outp
FROM state
WHERE step = (SELECT COUNT(*) FROM state);

--SELECT *
--FROM state;

--SELECT *
--FROM while_table;

--SELECT *
--FROM minus_table;

--SELECT *
--FROM asciitable;

--SELECT *
--FROM nibble;