text:
# This file is a part of Julia. License is MIT: https://julialang.org/license

module LineEdit

using ..Terminals

import ..Terminals: raw!, width, height, cmove, getX,
                       getY, clear_line, beep

import Base: ensureroom, peek, show, AnyDict

abstract type TextInterface end
abstract type ModeState end

export run_interface, Prompt, ModalInterface, transition, reset_state, edit_insert, keymap

struct ModalInterface <: TextInterface
    modes::Array{Base.LineEdit.TextInterface,1}
end

mutable struct Prompt <: TextInterface
    # A string or function to be printed as the prompt.
    prompt::Union{String,Function}
    # A string or function to be printed before the prompt. May not change the length of the prompt.
    # This may be used for changing the color, issuing other terminal escape codes, etc.
    prompt_prefix::Union{String,Function}
    # Same as prefix except after the prompt
    prompt_suffix::Union{String,Function}
    keymap_dict::Dict{Char}
    keymap_func_data # ::AbstractREPL
    complete # ::REPLCompletionProvider
    on_enter::Function
    on_done::Function
    hist # ::REPLHistoryProvider
    sticky::Bool
end

show(io::IO, x::Prompt) = show(io, string("Prompt(\"", prompt_string(x.prompt), "\",...)"))

mutable struct MIState
    interface::ModalInterface
    current_mode::TextInterface
    aborted::Bool
    mode_state::Dict
    kill_buffer::String
    previous_key::Array{Char,1}
    key_repeats::Int
end
MIState(i, c, a, m) = MIState(i, c, a, m, "", Char[], 0)

function show(io::IO, s::MIState)
    print(io, "MI State (", s.current_mode, " active)")
end

struct InputAreaState
    num_rows::Int64
    curs_row::Int64
end

mutable struct PromptState <: ModeState
    terminal::AbstractTerminal
    p::Prompt
    input_buffer::IOBuffer
    ias::InputAreaState
    # indentation of lines which do not include the prompt
    # if negative, the width of the prompt is used
    indent::Int
end

input_string(s::PromptState) = String(take!(copy(s.input_buffer)))

input_string_newlines(s::PromptState) = count(c->(c == '\n'), input_string(s))
function input_string_newlines_aftercursor(s::PromptState)
    str = input_string(s)
    isempty(str) && return 0
    rest = str[nextind(str, position(s.input_buffer)):end]
    return count(c->(c == '\n'), rest)
end

abstract type HistoryProvider end
abstract type CompletionProvider end

struct EmptyCompletionProvider <: CompletionProvider end
struct EmptyHistoryProvider <: HistoryProvider end

reset_state(::EmptyHistoryProvider) = nothing

complete_line(c::EmptyCompletionProvider, s) = [], true, true

terminal(s::IO) = s
terminal(s::PromptState) = s.terminal

for f in [:terminal, :edit_insert, :edit_insert_newline, :on_enter, :add_history,
          :buffer, :edit_backspace, :(Base.isempty), :replace_line, :refresh_multi_line,
          :input_string, :edit_move_left, :edit_move_right,
          :edit_move_word_left, :edit_move_word_right, :update_display_buffer]
    @eval ($f)(s::MIState, args...) = $(f)(s.mode_state[s.current_mode], args...)
end

function common_prefix(completions)
    ret = ""
    c1 = completions[1]
    isempty(c1) && return ret
    i = 1
    cc, nexti = next(c1, i)
    while true
        for c in completions
            (i > endof(c) || c[i] != cc) && return ret
        end
        ret = string(ret, cc)
        i >= endof(c1) && return ret
        i = nexti
        cc, nexti = next(c1, i)
    end
end

# Show available completions
function show_completions(s::PromptState, completions)
    colmax = maximum(map(length, completions))
    num_cols = max(div(width(terminal(s)), colmax+2), 1)
    entries_per_col, r = divrem(length(completions), num_cols)
    entries_per_col += r != 0
    # skip any lines of input after the cursor
    cmove_down(terminal(s), input_string_newlines_aftercursor(s))
    println(terminal(s))
    for row = 1:entries_per_col
        for col = 0:num_cols
            idx = row + col*entries_per_col
            if idx <= length(completions)
                cmove_col(terminal(s), (colmax+2)*col)
                print(terminal(s), completions[idx])
            end
        end
        println(terminal(s))
    end
    # make space for the prompt
    for i = 1:input_string_newlines(s)
        println(terminal(s))
    end
end

# Prompt Completions
complete_line(s::MIState) = complete_line(s.mode_state[s.current_mode], s.key_repeats)
function complete_line(s::PromptState, repeats)
    completions, partial, should_complete = complete_line(s.p.complete, s)
    if isempty(completions)
        beep(terminal(s))
    elseif !should_complete
        # should_complete is false for cases where we only want to show
        # a list of possible completions but not complete, e.g. foo(\t
        show_completions(s, completions)
    elseif length(completions) == 1
        # Replace word by completion
        prev_pos = position(s.input_buffer)
        seek(s.input_buffer, prev_pos-sizeof(partial))
        edit_replace(s, position(s.input_buffer), prev_pos, completions[1])
    else
        p = common_prefix(completions)
        if !isempty(p) && p != partial
            # All possible completions share the same prefix, so we might as
            # well complete that
            prev_pos = position(s.input_buffer)
            seek(s.input_buffer, prev_pos-sizeof(partial))
            edit_replace(s, position(s.input_buffer), prev_pos, p)
        elseif repeats > 0
            show_completions(s, completions)
        end
    end
end

clear_input_area(terminal, s) = (_clear_input_area(terminal, s.ias); s.ias = InputAreaState(0, 0))
clear_input_area(s) = clear_input_area(s.terminal, s)
function _clear_input_area(terminal, state::InputAreaState)
    # Go to the last line
    if state.curs_row < state.num_rows
        cmove_down(terminal, state.num_rows - state.curs_row)
    end

    # Clear lines one by one going up
    for j = 2:state.num_rows
        clear_line(terminal)
        cmove_up(terminal)
    end

    # Clear top line
    clear_line(terminal)
end

prompt_string(s::PromptState) = prompt_string(s.p)
prompt_string(p::Prompt) = prompt_string(p.prompt)
prompt_string(s::AbstractString) = s
prompt_string(f::Function) = Base.invokelatest(f)

refresh_multi_line(s::ModeState) = refresh_multi_line(terminal(s), s)
refresh_multi_line(termbuf::TerminalBuffer, s::ModeState) = refresh_multi_line(termbuf, terminal(s), s)
refresh_multi_line(termbuf::TerminalBuffer, term, s::ModeState) = (@assert term == terminal(s); refresh_multi_line(termbuf,s))
function refresh_multi_line(termbuf::TerminalBuffer, terminal::UnixTerminal, buf, state::InputAreaState, prompt = ""; indent = 0)
    _clear_input_area(termbuf, state)

    cols = width(terminal)
    curs_row = -1 # relative to prompt (1-based)
    curs_pos = -1 # 1-based column position of the cursor
    cur_row = 0   # count of the number of rows
    buf_pos = position(buf)
    line_pos = buf_pos
    # Write out the prompt string
    lindent = write_prompt(termbuf, prompt)
    # Count the '\n' at the end of the line if the terminal emulator does (specific to DOS cmd prompt)
    miscountnl = @static Sys.iswindows() ? (isa(Terminals.pipe_reader(terminal), Base.TTY) && !Base.ispty(Terminals.pipe_reader(terminal))) : false

    # Now go through the buffer line by line
    seek(buf, 0)
    moreinput = true # add a blank line if there is a trailing newline on the last line
    while moreinput
        l = readline(buf, chomp=false)
        moreinput = endswith(l, "\n")
        # We need to deal with on-screen characters, so use strwidth to compute occupied columns
        llength = strwidth(l)
        slength = sizeof(l)
        cur_row += 1
        cmove_col(termbuf, lindent + 1)
        write(termbuf, l)
        # We expect to be line after the last valid output line (due to
        # the '\n' at the end of the previous line)
        if curs_row == -1
            # in this case, we haven't yet written the cursor position
            line_pos -= slength # '\n' gets an extra pos
            if line_pos < 0 || !moreinput
                num_chars = (line_pos >= 0 ? llength : strwidth(l[1:(line_pos + slength)]))
                curs_row, curs_pos = divrem(lindent + num_chars - 1, cols)
                curs_row += cur_row
                curs_pos += 1
                # There's an issue if the cursor is after the very right end of the screen. In that case we need to
                # move the cursor to the next line, and emit a newline if needed
                if curs_pos == cols
                    # only emit the newline if the cursor is at the end of the line we're writing
                    if line_pos == 0
                        write(termbuf, "\n")
                        cur_row += 1
                    end
                    curs_row += 1
                    curs_pos = 0
                    cmove_col(termbuf, 1)
                end
            end
        end
        cur_row += div(max(lindent + llength + miscountnl - 1, 0), cols)
        lindent = indent < 0 ? lindent : indent
    end
    seek(buf, buf_pos)

    # Let's move the cursor to the right position
    # The line first
    n = cur_row - curs_row
    if n > 0
        cmove_up(termbuf, n)
    end

    #columns are 1 based
    cmove_col(termbuf, curs_pos + 1)

    # Updated cur_row,curs_row
    return InputAreaState(cur_row, curs_row)
end

function refresh_multi_line(terminal::UnixTerminal, args...; kwargs...)
    outbuf = IOBuffer()
    termbuf = TerminalBuffer(outbuf)
    ret = refresh_multi_line(termbuf, terminal, args...;kwargs...)
    # Output the entire refresh at once
    write(terminal, take!(outbuf))
    flush(terminal)
    return ret
end

# Edit functionality
is_non_word_char(c) = c in """ \t\n\"\\'`@\$><=:;|&{}()[].,+-*/?%^~"""

function reset_key_repeats(f::Function, s::MIState)
    key_repeats_sav = s.key_repeats
    try
        s.key_repeats = 0
        f()
    finally
        s.key_repeats = key_repeats_sav
    end
end

char_move_left(s::PromptState) = char_move_left(s.input_buffer)
function char_move_left(buf::IOBuffer)
    while position(buf) > 0
        seek(buf, position(buf)-1)
        c = peek(buf)
        (((c & 0x80) == 0) || ((c & 0xc0) == 0xc0)) && break
    end
    pos = position(buf)
    c = read(buf, Char)
    seek(buf, pos)
    c
end

function edit_move_left(buf::IOBuffer)
    if position(buf) > 0
        #move to the next base UTF8 character to the left
        while true
            c = char_move_left(buf)
            if charwidth(c) != 0 || c == '\n' || position(buf) == 0
                break
            end
        end
        return true
    end
    return false
end
edit_move_left(s::PromptState) = edit_move_left(s.input_buffer) && refresh_line(s)

function edit_move_word_left(s)
    if position(s.input_buffer) > 0
        char_move_word_left(s.input_buffer)
        refresh_line(s)
    end
end

char_move_right(s) = char_move_right(buffer(s))
function char_move_right(buf::IOBuffer)
    !eof(buf) && read(buf, Char)
end

function char_move_word_right(buf::IOBuffer, is_delimiter=is_non_word_char)
    while !eof(buf) && is_delimiter(char_move_right(buf))
    end
    while !eof(buf)
        pos = position(buf)
        if is_delimiter(char_move_right(buf))
            seek(buf, pos)
            break
        end
    end
end

function char_move_word_left(buf::IOBuffer, is_delimiter=is_non_word_char)
    while position(buf) > 0 && is_delimiter(char_move_left(buf))
    end
    while position(buf) > 0
        pos = position(buf)
        if is_delimiter(char_move_left(buf))
            seek(buf, pos)
            break
        end
    end
end

char_move_word_right(s) = char_move_word_right(buffer(s))
char_move_word_left(s) = char_move_word_left(buffer(s))

function edit_move_right(buf::IOBuffer)
    if !eof(buf)
        # move to the next base UTF8 character to the right
        while true
            c = char_move_right(buf)
            eof(buf) && break
            pos = position(buf)
            nextc = read(buf,Char)
            seek(buf,pos)
            (charwidth(nextc) != 0 || nextc == '\n') && break
        end
        return true
    end
    return false
end
edit_move_right(s::PromptState) = edit_move_right(s.input_buffer) && refresh_line(s)

function edit_move_word_right(s)
    if !eof(s.input_buffer)
        char_move_word_right(s)
        refresh_line(s)
    end
end

## Move line up/down
# Querying the terminal is expensive, memory access is cheap
# so to find the current column, we find the offset for the start
# of the line.

function edit_move_up(buf::IOBuffer)
    npos = rsearch(buf.data, '\n', position(buf))
    npos == 0 && return false # we're in the first line
    # We're interested in character count, not byte count
    offset = length(String(buf.data[(npos+1):(position(buf))]))
    npos2 = rsearch(buf.data, '\n', npos-1)
    seek(buf, npos2)
    for _ = 1:offset
        pos = position(buf)
        if read(buf, Char) == '\n'
            seek(buf, pos)
            break
        end
    end
    return true
end
function edit_move_up(s)
    changed = edit_move_up(buffer(s))
    changed && refresh_line(s)
    changed
end

function edit_move_down(buf::IOBuffer)
    npos = rsearch(buf.data[1:buf.size], '\n', position(buf))
    # We're interested in character count, not byte count
    offset = length(String(buf.data[(npos+1):(position(buf))]))
    npos2 = search(buf.data[1:buf.size], '\n', position(buf)+1)
    if npos2 == 0 #we're in the last line
        return false
    end
    seek(buf, npos2)
    for _ = 1:offset
        pos = position(buf)
        if eof(buf) || read(buf, Char) == '\n'
            seek(buf, pos)
            break
        end
    end
    return true
end
function edit_move_down(s)
    changed = edit_move_down(buffer(s))
    changed && refresh_line(s)
    changed
end

# splice! for IOBuffer: convert from 0-indexed positions, update the size,
# and keep the cursor position stable with the text
function splice_buffer!(buf::IOBuffer, r::UnitRange{<:Integer}, ins::AbstractString = "")
    pos = position(buf)
    if !isempty(r) && pos in r
        seek(buf, first(r))
    elseif pos > last(r)
        seek(buf, pos - length(r))
    end
    splice!(buf.data, r + 1, Vector{UInt8}(ins)) # position(), etc, are 0-indexed
    buf.size = buf.size + sizeof(ins) - length(r)
    seek(buf, position(buf) + sizeof(ins))
end

function edit_replace(s, from, to, str)
    splice_buffer!(buffer(s), from:to-1, str)
end

function edit_insert(s::PromptState, c)
    buf = s.input_buffer
    str = string(c)
    edit_insert(buf, str)
    offset = s.ias.curs_row == 1 || s.indent < 0 ?
        sizeof(prompt_string(s.p.prompt)) : s.indent
    if !('\n' in str) && eof(buf) &&
        ((position(buf) - beginofline(buf) + # size of current line
          offset + sizeof(str) - 1) < width(terminal(s)))
        # Avoid full update when appending characters to the end
        # and an update of curs_row isn't necessary (conservatively estimated)
        write(terminal(s), str)
    else
        refresh_line(s)
    end
end

function edit_insert(buf::IOBuffer, c)
    if eof(buf)
        return write(buf, c)
    else
        s = string(c)
        splice_buffer!(buf, position(buf):position(buf)-1, s)
        return sizeof(s)
    end
end

# align: number of ' ' to insert after '\n'
# if align < 0: align like line above
function edit_insert_newline(s::PromptState, align=-1)
    buf = buffer(s)
    if align < 0
        beg = beginofline(buf)
        align = findnext(_notspace, buf.data[beg+1:buf.size], 1) - 1
        align < 0 && (align = buf.size-beg)
    end
    edit_insert(buf, '\n' * ' '^align)
    refresh_line(s)
end

# align: delete up to 4 spaces to align to a multiple of 4 chars
# adjust: also delete spaces on the right of the cursor to try to keep aligned what is
# on the right
edit_backspace(s::PromptState, align::Bool=false, adjust=align) =
    edit_backspace(s.input_buffer, align) ? refresh_line(s) : beep(terminal(s))

const _newline =  UInt8('\n')
const _space = UInt8(' ')

_notspace(c) = c != _space

beginofline(buf, pos=position(buf)) = findprev(buf.data, _newline, pos)

function endofline(buf, pos=position(buf))
    eol = findnext(buf.data[pos+1:buf.size], _newline, 1)
    eol == 0 ? buf.size : pos + eol - 1
end

function edit_backspace(buf::IOBuffer, align::Bool=false, adjust::Bool=align)
    !align && adjust &&
        throw(DomainError((align, adjust),
                          "if `adjust` is `true`, `align` must be `true`"))
    oldpos = position(buf)
    oldpos == 0 && return false
    c = char_move_left(buf)
    newpos = position(buf)
    if align && c == ' ' # maybe delete multiple spaces
        beg = beginofline(buf, newpos)
        align = strwidth(String(buf.data[1+beg:newpos])) % 4
        nonspace = findprev(_notspace, buf.data, newpos)
        if newpos - align >= nonspace
            newpos -= align
            seek(buf, newpos)
            if adjust
                spaces = findnext(_notspace, buf.data[newpos+2:buf.size], 1)
                oldpos = spaces == 0 ? buf.size :
                    buf.data[newpos+1+spaces] == _newline ? newpos+spaces :
                    newpos + min(spaces, 4)
            end
        end
    end
    splice_buffer!(buf, newpos:oldpos-1)
    return true
end

edit_delete(s) = edit_delete(buffer(s)) ? refresh_line(s) : beep(terminal(s))
function edit_delete(buf::IOBuffer)
    eof(buf) && return false
    oldpos = position(buf)
    char_move_right(buf)
    splice_buffer!(buf, oldpos:position(buf)-1)
    true
end

function edit_werase(buf::IOBuffer)
    pos1 = position(buf)
    char_move_word_left(buf, isspace)
    pos0 = position(buf)
    pos0 < pos1 || return false
    splice_buffer!(buf, pos0:pos1-1)
    true
end
function edit_werase(s)
    edit_werase(buffer(s)) && refresh_line(s)
end

function edit_delete_prev_word(buf::IOBuffer)
    pos1 = position(buf)
    char_move_word_left(buf)
    pos0 = position(buf)
    pos0 < pos1 || return false
    splice_buffer!(buf, pos0:pos1-1)
    true
end
function edit_delete_prev_word(s)
    edit_delete_prev_word(buffer(s)) && refresh_line(s)
end

function edit_delete_next_word(buf::IOBuffer)
    pos0 = position(buf)
    char_move_word_right(buf)
    pos1 = position(buf)
    pos0 < pos1 || return false
    splice_buffer!(buf, pos0:pos1-1)
    true
end
function edit_delete_next_word(s)
    edit_delete_next_word(buffer(s)) && refresh_line(s)
end

function edit_yank(s::MIState)
    edit_insert(buffer(s), s.kill_buffer)
    refresh_line(s)
end

function edit_kill_line(s::MIState)
    buf = buffer(s)
    pos = position(buf)
    killbuf = readline(buf, chomp=false)
    if length(killbuf) > 1 && killbuf[end] == '\n'
        killbuf = killbuf[1:end-1]
        char_move_left(buf)
    end
    s.kill_buffer = s.key_repeats > 0 ? s.kill_buffer * killbuf : killbuf

    splice_buffer!(buf, pos:position(buf)-1)
    refresh_line(s)
end

edit_transpose_chars(s) = edit_transpose_chars(buffer(s)) && refresh_line(s)

function edit_transpose_chars(buf::IOBuffer)
    position(buf) == 0 && return false
    eof(buf) && char_move_left(buf)
    char_move_left(buf)
    pos = position(buf)
    a, b = read(buf, Char), read(buf, Char)
    seek(buf, pos)
    write(buf, b, a)
    return true
end

edit_transpose_words(s) = edit_transpose_words(buffer(s)) && refresh_line(s)

function edit_transpose_words(buf::IOBuffer, mode=:emacs)
    mode in [:readline, :emacs] ||
        throw(ArgumentError("`mode` must be `:readline` or `:emacs`"))
    pos = position(buf)
    if mode == :emacs
        char_move_word_left(buf)
        char_move_word_right(buf)
    end
    char_move_word_right(buf)
    e2 = position(buf)
    char_move_word_left(buf)
    b2 = position(buf)
    char_move_word_left(buf)
    b1 = position(buf)
    char_move_word_right(buf)
    e1 = position(buf)
    e1 >= b2 && (seek(buf, pos); return false)
    word2 = splice!(buf.data, b2+1:e2, buf.data[b1+1:e1])
    splice!(buf.data, b1+1:e1, word2)
    seek(buf, e2)
    true
end

edit_clear(buf::IOBuffer) = truncate(buf, 0)

function edit_clear(s::MIState)
    edit_clear(buffer(s))
    refresh_line(s)
end

function replace_line(s::PromptState, l::IOBuffer)
    s.input_buffer = copy(l)
end

function replace_line(s::PromptState, l)
    s.input_buffer.ptr = 1
    s.input_buffer.size = 0
    write(s.input_buffer, l)
end

history_prev(::EmptyHistoryProvider) = ("", false)
history_next(::EmptyHistoryProvider) = ("", false)
history_first(::EmptyHistoryProvider) = ("", false)
history_last(::EmptyHistoryProvider) = ("", false)
history_search(::EmptyHistoryProvider, args...) = false
add_history(::EmptyHistoryProvider, s) = nothing
add_history(s::PromptState) = add_history(mode(s).hist, s)
history_next_prefix(s, hist, prefix) = false
history_prev_prefix(s, hist, prefix) = false

function history_prev(s, hist)
    l, ok = history_prev(mode(s).hist)
    if ok
        replace_line(s, l)
        move_input_start(s)
        refresh_line(s)
    else
        beep(terminal(s))
    end
end
function history_next(s, hist)
    l, ok = history_next(mode(s).hist)
    if ok
        replace_line(s, l)
        move_input_end(s)
        refresh_line(s)
    else
        beep(terminal(s))
    end
end

refresh_line(s) = refresh_multi_line(s)
refresh_line(s, termbuf) = refresh_multi_line(termbuf, s)

default_completion_cb(::IOBuffer) = []
default_enter_cb(_) = true

write_prompt(terminal, s::PromptState) = write_prompt(terminal, s.p)

function write_prompt(terminal, p::Prompt)
    prefix = prompt_string(p.prompt_prefix)
    suffix = prompt_string(p.prompt_suffix)
    write(terminal, prefix)
    write(terminal, Base.text_colors[:bold])
    width = write_prompt(terminal, p.prompt)
    write(terminal, Base.text_colors[:normal])
    write(terminal, suffix)
    width
end

# returns the width of the written prompt
function write_prompt(terminal, s::Union{AbstractString,Function})
    promptstr = prompt_string(s)
    write(terminal, promptstr)
    strwidth(promptstr)
end

### Keymap Support

normalize_key(key::Char) = string(key)
normalize_key(key::Integer) = normalize_key(Char(key))
function normalize_key(key::AbstractString)
    '\0' in key && error("Matching \\0 not currently supported.")
    buf = IOBuffer()
    i = start(key)
    while !done(key, i)
        c, i = next(key, i)
        if c == '*'
            write(buf, '\0')
        elseif c == '^'
            c, i = next(key, i)
            write(buf, uppercase(c)-64)
        elseif c == '\\'
            c, i = next(key, i)
            if c == 'C'
                c, i = next(key, i)
                @assert c == '-'
                c, i = next(key, i)
                write(buf, uppercase(c)-64)
            elseif c == 'M'
                c, i = next(key, i)
                @assert c == '-'
                c, i = next(key, i)
                write(buf, '\e')
                write(buf, c)
            end
        else
            write(buf, c)
        end
    end
    return String(take!(buf))
end

function normalize_keys(keymap::Dict)
    ret = Dict{Any,Any}()
    for (k,v) in keymap
        normalized = normalize_key(k)
        if haskey(ret,normalized)
            error("""Multiple spellings of a key in a single keymap
                     (\"$k\" conflicts with existing mapping)""")
        end
        ret[normalized] = v
    end
    return ret
end

function add_nested_key!(keymap::Dict, key, value; override = false)
    i = start(key)
    while !done(key, i)
        c, i = next(key, i)
        if c in keys(keymap)
            if done(key, i) && override
                # isa(keymap[c], Dict) - In this case we're overriding a prefix of an existing command
                keymap[c] = value
                break
            else
                if !isa(keymap[c], Dict)
                    error("Conflicting definitions for keyseq " * escape_string(key) * " within one keymap")
                end
            end
        elseif done(key, i)
            keymap[c] = value
            break
        else
            keymap[c] = Dict{Char,Any}()
        end
        keymap = keymap[c]
    end
end

# Redirect a key as if `seq` had been the keysequence instead in a lazy fashion.
# This is different from the default eager redirect, which only looks at the current and lower
# layers of the stack.
struct KeyAlias
    seq::String
    KeyAlias(seq) = new(normalize_key(seq))
end

match_input(k::Function, s, term, cs, keymap) = (update_key_repeats(s, cs); return keymap_fcn(k, String(cs)))
match_input(k::Void, s, term, cs, keymap) = (s,p) -> return :ok
match_input(k::KeyAlias, s, term, cs, keymap) = match_input(keymap, s, IOBuffer(k.seq), Char[], keymap)
function match_input(k::Dict, s, term=terminal(s), cs=Char[], keymap = k)
    # if we run out of characters to match before resolving an action,
    # return an empty keymap function
    eof(term) && return keymap_fcn(nothing, "")
    c = read(term, Char)
    # Ignore any '\0' (eg, CTRL-space in xterm), as this is used as a
    # placeholder for the wildcard (see normalize_key("*"))
    c != '\0' || return keymap_fcn(nothing, "")
    push!(cs, c)
    key = haskey(k, c) ? c : '\0'
    # if we don't match on the key, look for a default action then fallback on 'nothing' to ignore
    return match_input(get(k, key, nothing), s, term, cs, keymap)
end

keymap_fcn(f::Void, c) = (s, p) -> return :ok
function keymap_fcn(f::Function, c)
    return function (s, p)
        r = eval(Expr(:call,f,s, p, c))
        if isa(r, Symbol)
            return r
        else
            return :ok
        end
    end
end

update_key_repeats(s, keystroke) = nothing
function update_key_repeats(s::MIState, keystroke)
    s.key_repeats  = s.previous_key == keystroke ? s.key_repeats + 1 : 0
    s.previous_key = keystroke
    return
end

## Conflict fixing
# Consider a keymap of the form
#
# {
#   "**" => f
#   "ab" => g
# }
#
# Naively this is transformed into a tree as
#
# {
#   '*' => {
#       '*' => f
#   }
#   'a' => {
#       'b' => g
#   }
# }
#
# However, that's not what we want, because now "ac" is
# is not defined. We need to fix this up and turn it into
#
# {
#   '*' => {
#       '*' => f
#   }
#   'a' => {
#       '*' => f
#       'b' => g
#   }
# }
#
# i.e. copy over the appropraite default subdict
#

# deep merge where target has higher precedence
function keymap_merge!(target::Dict, source::Dict)
    for k in keys(source)
        if !haskey(target, k)
            target[k] = source[k]
        elseif isa(target[k], Dict)
            keymap_merge!(target[k], source[k])
        else
            # Ignore, target has higher precedence
        end
    end
end

fixup_keymaps!(d, l, s, sk) = nothing
function fixup_keymaps!(dict::Dict, level, s, subkeymap)
    if level > 0
        for d in values(dict)
            fixup_keymaps!(d, level-1, s, subkeymap)
        end
    else
        if haskey(dict, s)
            if isa(dict[s], Dict) && isa(subkeymap, Dict)
                keymap_merge!(dict[s], subkeymap)
            end
        else
            dict[s] = deepcopy(subkeymap)
        end
    end
end

function add_specialisations(dict, subdict, level)
    default_branch = subdict['\0']
    if isa(default_branch, Dict)
        # Go through all the keymaps in the default branch
        # and copy them over to dict
        for s in keys(default_branch)
            s == '\0' && add_specialisations(dict, default_branch, level+1)
            fixup_keymaps!(dict, level, s, default_branch[s])
        end
    end
end

postprocess!(others) = nothing
function postprocess!(dict::Dict)
    # needs to be done first for every branch
    if haskey(dict, '\0')
        add_specialisations(dict, dict, 1)
    end
    for (k,v) in dict
        k == '\0' && continue
        postprocess!(v)
    end
end

function getEntry(keymap,key)
    v = keymap
    for c in key
        if !haskey(v,c)
            return nothing
        end
        v = v[c]
    end
    return v
end

# `target` is the total keymap being built up, already being a nested tree of Dicts.
# source is the keymap specified by the user (with normalized keys)
function keymap_merge(target,source)
    ret = copy(target)
    direct_keys = filter(p -> isa(p.second, Union{Function, KeyAlias, Void}), source)
    # first direct entries
    for key in keys(direct_keys)
        add_nested_key!(ret, key, source[key]; override = true)
    end
    # then redirected entries
    for key in setdiff(keys(source), keys(direct_keys))
        # We first resolve redirects in the source
        value = source[key]
        visited = Vector{Any}(0)
        while isa(value, Union{Char,AbstractString})
            value = normalize_key(value)
            if value in visited
                error("Eager redirection cycle detected for key " * escape_string(key))
            end
            push!(visited,value)
            if !haskey(source,value)
                break
            end
            value = source[value]
        end

        if isa(value, Union{Char,AbstractString})
            value = getEntry(ret, value)
            if value === nothing
                error("Could not find redirected value " * escape_string(source[key]))
            end
        end
        add_nested_key!(ret, key, value; override = true)
    end
    ret
end

function keymap_unify(keymaps)
    ret = Dict{Char,Any}()
    for keymap in keymaps
        ret = keymap_merge(ret, keymap)
    end
    postprocess!(ret)
    return ret
end

function validate_keymap(keymap)
    for key in keys(keymap)
        visited_keys = Any[key]
        v = getEntry(keymap,key)
        while isa(v,KeyAlias)
            if v.seq in visited_keys
                error("Alias cycle detected in keymap")
            end
            push!(visited_keys,v.seq)
            v = getEntry(keymap,v.seq)
        end
    end
end

function keymap(keymaps::Array{<:Dict})
    # keymaps is a vector of prioritized keymaps, with highest priority first
    ret = keymap_unify(map(normalize_keys, reverse(keymaps)))
    validate_keymap(ret)
    ret
end

const escape_defaults = merge!(
    AnyDict(Char(i) => nothing for i=vcat(1:26, 28:31)), # Ignore control characters by default
    AnyDict( # And ignore other escape sequences by default
        "\e*" => nothing,
        "\e[*" => nothing,
        "\eO*" => nothing,
        # Also ignore extended escape sequences
        # TODO: Support ranges of characters
        "\e[1**" => nothing,
        "\e[2**" => nothing,
        "\e[3**" => nothing,
        "\e[4**" => nothing,
        "\e[5**" => nothing,
        "\e[6**" => nothing,
        # less commonly used VT220 editing keys
        "\e[2~" => nothing, # insert
        "\e[3~" => nothing, # delete
        "\e[5~" => nothing, # page up
        "\e[6~" => nothing, # page down
        # These are different spellings of arrow keys, home keys, etc.
        # and should always do the same as the canonical key sequence
        "\e[1~" => KeyAlias("\e[H"), # home
        "\e[4~" => KeyAlias("\e[F"), # end
        "\e[7~" => KeyAlias("\e[H"), # home
        "\e[8~" => KeyAlias("\e[F"), # end
        "\eOA"  => KeyAlias("\e[A"),
        "\eOB"  => KeyAlias("\e[B"),
        "\eOC"  => KeyAlias("\e[C"),
        "\eOD"  => KeyAlias("\e[D"),
        "\eOH"  => KeyAlias("\e[H"),
        "\eOF"  => KeyAlias("\e[F"),
    ),
    # set mode commands
    AnyDict("\e[$(c)h" => nothing for c in 1:20),
    # reset mode commands
    AnyDict("\e[$(c)l" => nothing for c in 1:20)
    )

function write_response_buffer(s::PromptState, data)
    offset = s.input_buffer.ptr
    ptr = data.response_buffer.ptr
    seek(data.response_buffer, 0)
    write(s.input_buffer, read(data.response_buffer, String))
    s.input_buffer.ptr = offset + ptr - 2
    data.response_buffer.ptr = ptr
    refresh_line(s)
end

mutable struct SearchState <: ModeState
    terminal::AbstractTerminal
    histprompt # ::HistoryPrompt
    #rsearch (true) or ssearch (false)
    backward::Bool
    query_buffer::IOBuffer
    response_buffer::IOBuffer
    ias::InputAreaState
    #The prompt whose input will be replaced by the matched history
    parent::Prompt
    SearchState(terminal, histprompt, backward, query_buffer, response_buffer) =
        new(terminal, histprompt, backward, query_buffer, response_buffer, InputAreaState(0,0))
end

terminal(s::SearchState) = s.terminal

function update_display_buffer(s::SearchState, data)
    history_search(data.histprompt.hp, data.query_buffer, data.response_buffer, data.backward, false) || beep(terminal(s))
    refresh_line(s)
end

function history_next_result(s::MIState, data::SearchState)
    history_search(data.histprompt.hp, data.query_buffer, data.response_buffer, data.backward, true) || beep(terminal(s))
    refresh_line(data)
end

function history_set_backward(s::SearchState, backward)
    s.backward = backward
end

input_string(s::SearchState) = String(take!(copy(s.query_buffer)))

function reset_state(s::SearchState)
    if s.query_buffer.size != 0
        s.query_buffer.size = 0
        s.query_buffer.ptr = 1
    end
    if s.response_buffer.size != 0
        s.response_buffer.size = 0
        s.response_buffer.ptr = 1
    end
    reset_state(s.histprompt.hp)
end

mutable struct HistoryPrompt{T<:HistoryProvider} <: TextInterface
    hp::T
    complete # ::CompletionProvider
    keymap_dict::Dict{Char,Any}
    HistoryPrompt{T}(hp) where T<:HistoryProvider = new(hp, EmptyCompletionProvider())
end

HistoryPrompt(hp::T) where T<:HistoryProvider = HistoryPrompt{T}(hp)
init_state(terminal, p::HistoryPrompt) = SearchState(terminal, p, true, IOBuffer(), IOBuffer())

mutable struct PrefixSearchState <: ModeState
    terminal::AbstractTerminal
    histprompt # ::HistoryPrompt
    prefix::String
    response_buffer::IOBuffer
    ias::InputAreaState
    indent::Int
    # The modal interface state, if present
    mi::MIState
    #The prompt whose input will be replaced by the matched history
    parent::Prompt
    PrefixSearchState(terminal, histprompt, prefix, response_buffer) =
        new(terminal, histprompt, prefix, response_buffer, InputAreaState(0,0), 0)
end

function show(io::IO, s::PrefixSearchState)
    print(io, "PrefixSearchState ", isdefined(s,:parent) ?
     string("(", s.parent, " active)") : "(no parent)", " for ",
     isdefined(s,:mi) ? s.mi : "no MI")
end

refresh_multi_line(termbuf::TerminalBuffer, terminal::UnixTerminal,
    s::Union{PromptState,PrefixSearchState}) = s.ias =
    refresh_multi_line(termbuf, terminal, buffer(s), s.ias, s, indent = s.indent)

input_string(s::PrefixSearchState) = String(take!(copy(s.response_buffer)))

# a meta-prompt that presents itself as parent_prompt, but which has an independent keymap
# for prefix searching
mutable struct PrefixHistoryPrompt{T<:HistoryProvider} <: TextInterface
    hp::T
    parent_prompt::Prompt
    complete # ::CompletionProvider
    keymap_dict::Dict{Char,Any}
    PrefixHistoryPrompt{T}(hp, parent_prompt) where T<:HistoryProvider =
        new(hp, parent_prompt, EmptyCompletionProvider())
end

PrefixHistoryPrompt(hp::T, parent_prompt) where T<:HistoryProvider = PrefixHistoryPrompt{T}(hp, parent_prompt)
init_state(terminal, p::PrefixHistoryPrompt) = PrefixSearchState(terminal, p, "", IOBuffer())

write_prompt(terminal, s::PrefixSearchState) = write_prompt(terminal, s.histprompt.parent_prompt)
prompt_string(s::PrefixSearchState) = prompt_string(s.histprompt.parent_prompt.prompt)

terminal(s::PrefixSearchState) = s.terminal

function reset_state(s::PrefixSearchState)
    if s.response_buffer.size != 0
        s.response_buffer.size = 0
        s.response_buffer.ptr = 1
    end
    reset_state(s.histprompt.hp)
end

function transition(f::Function, s::PrefixSearchState, mode)
    if isdefined(s, :mi)
        transition(s.mi, mode)
    end
    s.parent = mode
    s.histprompt.parent_prompt = mode
    if isdefined(s, :mi)
        transition(f, s.mi, s.histprompt)
    else
        f()
    end
end

replace_line(s::PrefixSearchState, l::IOBuffer) = s.response_buffer = l
function replace_line(s::PrefixSearchState, l)
    s.response_buffer.ptr = 1
    s.response_buffer.size = 0
    write(s.response_buffer, l)
end

function refresh_multi_line(termbuf::TerminalBuffer, s::SearchState)
    buf = IOBuffer()
    unsafe_write(buf, pointer(s.query_buffer.data), s.query_buffer.ptr-1)
    write(buf, "': ")
    offset = buf.ptr
    ptr = s.response_buffer.ptr
    seek(s.response_buffer, 0)
    write(buf, read(s.response_buffer, String))
    buf.ptr = offset + ptr - 1
    s.response_buffer.ptr = ptr
    s.ias = refresh_multi_line(termbuf, s.terminal, buf, s.ias, s.backward ? "(reverse-i-search)`" : "(forward-i-search)`")
end

state(s::MIState, p) = s.mode_state[p]
state(s::PromptState, p) = (@assert s.p == p; s)
mode(s::MIState) = s.current_mode
mode(s::PromptState) = s.p
mode(s::SearchState) = @assert false
mode(s::PrefixSearchState) = s.histprompt.parent_prompt

# Search Mode completions
function complete_line(s::SearchState, repeats)
    completions, partial, should_complete = complete_line(s.histprompt.complete, s)
    # For now only allow exact completions in search mode
    if length(completions) == 1
        prev_pos = position(s.query_buffer)
        seek(s.query_buffer, prev_pos-sizeof(partial))
        edit_replace(s, position(s.query_buffer), prev_pos, completions[1])
    end
end

function accept_result(s, p)
    parent = state(s, p).parent
    transition(s, parent) do
        replace_line(state(s, parent), state(s, p).response_buffer)
    end
end

function copybuf!(dst::IOBuffer, src::IOBuffer)
    n = src.size
    ensureroom(dst, n)
    copy!(dst.data, 1, src.data, 1, n)
    dst.size = src.size
    dst.ptr = src.ptr
end

function enter_search(s::MIState, p::HistoryPrompt, backward::Bool)
    # a bit of hack to help fix #6325
    buf = copy(buffer(s))
    parent = mode(s)
    p.hp.last_mode = mode(s)
    p.hp.last_buffer = buf

    transition(s, p) do
        ss = state(s, p)
        ss.parent = parent
        ss.backward = backward
        truncate(ss.query_buffer, 0)
        copybuf!(ss.response_buffer, buf)
    end
end

function enter_prefix_search(s::MIState, p::PrefixHistoryPrompt, backward::Bool)
    buf = copy(buffer(s))
    parent = mode(s)

    transition(s, p) do
        pss = state(s, p)
        pss.parent = parent
        pss.histprompt.parent_prompt = parent
        pss.prefix = String(buf.data[1:position(buf)])
        copybuf!(pss.response_buffer, buf)
        pss.indent = state(s, parent).indent
        pss.mi = s
    end
    pss = state(s, p)
    if backward
        history_prev_prefix(pss, pss.histprompt.hp, pss.prefix)
    else
        history_next_prefix(pss, pss.histprompt.hp, pss.prefix)
    end
end

function setup_search_keymap(hp)
    p = HistoryPrompt(hp)
    pkeymap = AnyDict(
        "^R"      => (s,data,c)->(history_set_backward(data, true); history_next_result(s, data)),
        "^S"      => (s,data,c)->(history_set_backward(data, false); history_next_result(s, data)),
        '\r'      => (s,o...)->accept_result(s, p),
        '\n'      => '\r',
        # Limited form of tab completions
        '\t'      => (s,data,c)->(complete_line(s); update_display_buffer(s, data)),
        "^L"      => (s,data,c)->(Terminals.clear(terminal(s)); update_display_buffer(s, data)),

        # Backspace/^H
        '\b'      => (s,data,c)->(edit_backspace(data.query_buffer) ?
                        update_display_buffer(s, data) : beep(terminal(s))),
        127       => KeyAlias('\b'),
        # Meta Backspace
        "\e\b"    => (s,data,c)->(edit_delete_prev_word(data.query_buffer) ?
                        update_display_buffer(s, data) : beep(terminal(s))),
        "\e\x7f"  => "\e\b",
        # Word erase to whitespace
        "^W"      => (s,data,c)->(edit_werase(data.query_buffer) ?
                        update_display_buffer(s, data) : beep(terminal(s))),
        # ^C and ^D
        "^C"      => (s,data,c)->(edit_clear(data.query_buffer);
                       edit_clear(data.response_buffer);
                       update_display_buffer(s, data);
                       reset_state(data.histprompt.hp);
                       transition(s, data.parent)),
        "^D"      => "^C",
        # Other ways to cancel search mode (it's difficult to bind \e itself)
        "^G"      => "^C",
        "\e\e"    => "^C",
        "^K"      => (s,o...)->transition(s, state(s, p).parent),
        "^Y"      => (s,data,c)->(edit_yank(s); update_display_buffer(s, data)),
        "^U"      => (s,data,c)->(edit_clear(data.query_buffer);
                     edit_clear(data.response_buffer);
                     update_display_buffer(s, data)),
        # Right Arrow
        "\e[C"    => (s,o...)->(accept_result(s, p); edit_move_right(s)),
        # Left Arrow
        "\e[D"    => (s,o...)->(accept_result(s, p); edit_move_left(s)),
        # Up Arrow
        "\e[A"    => (s,o...)->(accept_result(s, p); edit_move_up(s)),
        # Down Arrow
        "\e[B"    => (s,o...)->(accept_result(s, p); edit_move_down(s)),
        "^B"      => (s,o...)->(accept_result(s, p); edit_move_left(s)),
        "^F"      => (s,o...)->(accept_result(s, p); edit_move_right(s)),
        # Meta B
        "\eb"     => (s,o...)->(accept_result(s, p); edit_move_word_left(s)),
        # Meta F
        "\ef"     => (s,o...)->(accept_result(s, p); edit_move_word_right(s)),
        # Ctrl-Left Arrow
        "\e[1;5D" => "\eb",
        # Ctrl-Left Arrow on rxvt
        "\eOd" => "\eb",
        # Ctrl-Right Arrow
        "\e[1;5C" => "\ef",
        # Ctrl-Right Arrow on rxvt
        "\eOc" => "\ef",
        "^A"         => (s,o...)->(accept_result(s, p); move_line_start(s); refresh_line(s)),
        "^E"         => (s,o...)->(accept_result(s, p); move_line_end(s); refresh_line(s)),
        "^Z"      => (s,o...)->(return :suspend),
        # Try to catch all Home/End keys
        "\e[H"    => (s,o...)->(accept_result(s, p); move_input_start(s); refresh_line(s)),
        "\e[F"    => (s,o...)->(accept_result(s, p); move_input_end(s); refresh_line(s)),
        # Use ^N and ^P to change search directions and iterate through results
        "^N"      => (s,data,c)->(history_set_backward(data, false); history_next_result(s, data)),
        "^P"      => (s,data,c)->(history_set_backward(data, true); history_next_result(s, data)),
        # Bracketed paste mode
        "\e[200~" => (s,data,c)-> begin
            ps = state(s, mode(s))
            input = readuntil(ps.terminal, "\e[201~")[1:(end-6)]
            edit_insert(data.query_buffer, input); update_display_buffer(s, data)
        end,
        "*"       => (s,data,c)->(edit_insert(data.query_buffer, c); update_display_buffer(s, data))
    )
    p.keymap_dict = keymap([pkeymap, escape_defaults])
    skeymap = AnyDict(
        "^R"    => (s,o...)->(enter_search(s, p, true)),
        "^S"    => (s,o...)->(enter_search(s, p, false)),
    )
    (p, skeymap)
end

keymap(state, p::Union{HistoryPrompt,PrefixHistoryPrompt}) = p.keymap_dict
keymap_data(state, ::Union{HistoryPrompt, PrefixHistoryPrompt}) = state

Base.isempty(s::PromptState) = s.input_buffer.size == 0

on_enter(s::PromptState) = s.p.on_enter(s)

move_input_start(s) = (seek(buffer(s), 0))
move_input_end(buf::IOBuffer) = seekend(buf)
move_input_end(s) = move_input_end(buffer(s))
function move_line_start(s::MIState)
    buf = buffer(s)
    curpos = position(buf)
    curpos == 0 && return
    if s.key_repeats > 0
        move_input_start(s)
    else
        seek(buf, rsearch(buf.data, '\n', curpos))
    end
end
function move_line_end(s::MIState)
    s.key_repeats > 0 ?
        move_input_end(s) :
        move_line_end(buffer(s))
end
function move_line_end(buf::IOBuffer)
    eof(buf) && return
    pos = search(buf.data, '\n', position(buf)+1)
    if pos == 0
        move_input_end(buf)
        return
    end
    seek(buf, pos-1)
end

function commit_line(s)
    move_input_end(s)
    refresh_line(s)
    println(terminal(s))
    add_history(s)
    state(s, mode(s)).ias = InputAreaState(0, 0)
end

"""
`Base.LineEdit.tabwidth` controls the presumed tab width of code pasted into the REPL.

You can modify it by doing `@eval Base.LineEdit tabwidth = 4`, for example.

Must satisfy `0 < tabwidth <= 16`.
"""
global tabwidth = 8

function bracketed_paste(s)
    ps = state(s, mode(s))
    input = readuntil(ps.terminal, "\e[201~")[1:(end-6)]
    input = replace(input, '\r', '\n')
    if position(buffer(s)) == 0
        indent = Base.indentation(input; tabwidth=tabwidth)[1]
        input = Base.unindent(input, indent; tabwidth=tabwidth)
    end
    return replace(input, '\t', " "^tabwidth)
end

function tab_should_complete(s)
    # Yes, we are ignoring the possiblity
    # the we could be in the middle of a multi-byte
    # sequence, here but that's ok, since any
    # whitespace we're interested in is only one byte
    buf = buffer(s)
    pos = position(buf)
    pos == 0 && return true
    c = buf.data[pos]
    c != _newline && c != UInt8('\t') &&
        # hack to allow path completion in cmds
        # after a space, e.g., `cd <tab>`, while still
        # allowing multiple indent levels
        (c != _space || pos <= 3 || buf.data[pos-1] != _space)
end

# jump_spaces: if cursor is on a ' ', move it to the first non-' ' char on the right
# if `delete_trailing`, ignore trailing ' ' by deleting them
function edit_tab(s, jump_spaces=false, delete_trailing=jump_spaces)
    tab_should_complete(s) ?
        complete_line(s) :
        edit_tab(buffer(s), jump_spaces, delete_trailing)
    refresh_line(s)
end

function edit_tab(buf::IOBuffer, jump_spaces=false, delete_trailing=jump_spaces)
    i = position(buf)
    if jump_spaces && i < buf.size && buf.data[i+1] == _space
        spaces = findnext(_notspace, buf.data[i+1:buf.size], 1)
        if delete_trailing && (spaces == 0 || buf.data[i+spaces] == _newline)
            splice_buffer!(buf, i:(spaces == 0 ? buf.size-1 : i+spaces-2))
        else
            jump = spaces == 0 ? buf.size : i+spaces-1
            return seek(buf, jump)
        end
    end
    # align to multiples of 4:
    align = 4 - strwidth(String(buf.data[1+beginofline(buf, i):i])) % 4
    return edit_insert(buf, ' '^align)
end

const default_keymap =
AnyDict(
    # Tab
    '\t' => (s,o...)->edit_tab(s, true),
    # Enter
    '\r' => (s,o...)->begin
        if on_enter(s) || (eof(buffer(s)) && s.key_repeats > 1)
            commit_line(s)
            return :done
        else
            edit_insert_newline(s)
        end
    end,
    '\n' => KeyAlias('\r'),
    # Backspace/^H
    '\b' => (s,o...)->edit_backspace(s, true),
    127 => KeyAlias('\b'),
    # Meta Backspace
    "\e\b" => (s,o...)->edit_delete_prev_word(s),
    "\e\x7f" => "\e\b",
    # ^D
    "^D" => (s,o...)->begin
        if buffer(s).size > 0
            edit_delete(s)
        else
            println(terminal(s))
            return :abort
        end
    end,
    "^B" => (s,o...)->edit_move_left(s),
    "^F" => (s,o...)->edit_move_right(s),
    # Meta B
    "\eb" => (s,o...)->edit_move_word_left(s),
    # Meta F
    "\ef" => (s,o...)->edit_move_word_right(s),
    # Ctrl-Left Arrow
    "\e[1;5D" => "\eb",
    # Ctrl-Left Arrow on rxvt
    "\eOd" => "\eb",
    # Ctrl-Right Arrow
    "\e[1;5C" => "\ef",
    # Ctrl-Right Arrow on rxvt
    "\eOc" => "\ef",
    # Meta Enter
    "\e\r" => (s,o...)->edit_insert_newline(s),
    "\e\n" => "\e\r",
    # Simply insert it into the buffer by default
    "*" => (s,data,c)->(edit_insert(s, c)),
    "^U" => (s,o...)->edit_clear(s),
    "^K" => (s,o...)->edit_kill_line(s),
    "^Y" => (s,o...)->edit_yank(s),
    "^A" => (s,o...)->(move_line_start(s); refresh_line(s)),
    "^E" => (s,o...)->(move_line_end(s); refresh_line(s)),
    # Try to catch all Home/End keys
    "\e[H"  => (s,o...)->(move_input_start(s); refresh_line(s)),
    "\e[F"  => (s,o...)->(move_input_end(s); refresh_line(s)),
    "^L" => (s,o...)->(Terminals.clear(terminal(s)); refresh_line(s)),
    "^W" => (s,o...)->edit_werase(s),
    # Meta D
    "\ed" => (s,o...)->edit_delete_next_word(s),
    "^C" => (s,o...)->begin
        try # raise the debugger if present
            ccall(:jl_raise_debugger, Int, ())
        end
        move_input_end(s)
        refresh_line(s)
        print(terminal(s), "^C\n\n")
        transition(s, :reset)
        refresh_line(s)
    end,
    "^Z" => (s,o...)->(return :suspend),
    # Right Arrow
    "\e[C" => (s,o...)->edit_move_right(s),
    # Left Arrow
    "\e[D" => (s,o...)->edit_move_left(s),
    # Up Arrow
    "\e[A" => (s,o...)->edit_move_up(s),
    # Down Arrow
    "\e[B" => (s,o...)->edit_move_down(s),
    # Delete
    "\e[3~" => (s,o...)->edit_delete(s),
    # Bracketed Paste Mode
    "\e[200~" => (s,o...)->begin
        input = bracketed_paste(s)
        edit_insert(s, input)
    end,
    "^T" => (s,o...)->edit_transpose_chars(s),
    "\et" => (s,o...)->edit_transpose_words(s),
)

const history_keymap = AnyDict(
    "^P" => (s,o...)->(history_prev(s, mode(s).hist)),
    "^N" => (s,o...)->(history_next(s, mode(s).hist)),
    # Up Arrow
    "\e[A" => (s,o...)->(edit_move_up(s) || history_prev(s, mode(s).hist)),
    # Down Arrow
    "\e[B" => (s,o...)->(edit_move_down(s) || history_next(s, mode(s).hist)),
    # Page Up
    "\e[5~" => (s,o...)->(history_prev(s, mode(s).hist)),
    # Page Down
    "\e[6~" => (s,o...)->(history_next(s, mode(s).hist)),
    "\e<" => (s,o...)->(history_first(s, mode(s).hist)),
    "\e>" => (s,o...)->(history_last(s, mode(s).hist)),
)

const prefix_history_keymap = merge!(
    AnyDict(
        # Up Arrow
        "\e[A" => (s,data,c)->history_prev_prefix(data, data.histprompt.hp, data.prefix),
        # Down Arrow
        "\e[B" => (s,data,c)->history_next_prefix(data, data.histprompt.hp, data.prefix),
        # by default, pass thru to the parent mode
        "*"    => (s,data,c)->begin
            accept_result(s, data.histprompt);
            ps = state(s, mode(s))
            map = keymap(ps, mode(s))
            match_input(map, s, IOBuffer(c))(s, keymap_data(ps, mode(s)))
        end,
        # match escape sequences for pass thru
        "\e*" => "*",
        "\e[*" => "*",
        "\eO*"  => "*",
        "\e[1;5*" => "*", # Ctrl-Arrow
        "\e[200~" => "*"
    ),
    # VT220 editing commands
    AnyDict("\e[$(n)~" => "*" for n in 1:8),
    # set mode commands
    AnyDict("\e[$(c)h" => "*" for c in 1:20),
    # reset mode commands
    AnyDict("\e[$(c)l" => "*" for c in 1:20)
)

function setup_prefix_keymap(hp, parent_prompt)
    p = PrefixHistoryPrompt(hp, parent_prompt)
    p.keymap_dict = keymap([prefix_history_keymap])
    pkeymap = AnyDict(
        # Up Arrow
        "\e[A" => (s,o...)->(edit_move_up(s) || enter_prefix_search(s, p, true)),
        # Down Arrow
        "\e[B" => (s,o...)->(edit_move_down(s) || enter_prefix_search(s, p, false)),
    )
    (p, pkeymap)
end

function deactivate(p::TextInterface, s::ModeState, termbuf, term::TextTerminal)
    clear_input_area(termbuf, s)
    s
end

function activate(p::TextInterface, s::ModeState, termbuf, term::TextTerminal)
    s.ias = InputAreaState(0, 0)
    refresh_line(s, termbuf)
end

function activate(p::TextInterface, s::MIState, termbuf, term::TextTerminal)
    @assert p == s.current_mode
    activate(p, s.mode_state[s.current_mode], termbuf, term)
end
activate(m::ModalInterface, s::MIState, termbuf, term::TextTerminal) =
    activate(s.current_mode, s, termbuf, term)

commit_changes(t::UnixTerminal, termbuf) = write(t, take!(termbuf.out_stream))
function transition(f::Function, s::MIState, mode)
    if mode === :abort
        s.aborted = true
        return
    end
    if mode === :reset
        reset_state(s)
        return
    end
    if !haskey(s.mode_state,mode)
        s.mode_state[mode] = init_state(terminal(s), mode)
    end
    termbuf = TerminalBuffer(IOBuffer())
    t = terminal(s)
    s.mode_state[s.current_mode] = deactivate(s.current_mode, s.mode_state[s.current_mode], termbuf, t)
    s.current_mode = mode
    f()
    activate(mode, s.mode_state[mode], termbuf, t)
    commit_changes(t, termbuf)
end
transition(s::MIState, mode) = transition((args...)->nothing, s, mode)

function reset_state(s::PromptState)
    if s.input_buffer.size != 0
        s.input_buffer.size = 0
        s.input_buffer.ptr = 1
    end
    s.ias = InputAreaState(0, 0)
end

function reset_state(s::MIState)
    for (mode,state) in s.mode_state
        reset_state(state)
    end
end

const default_keymap_dict = keymap([default_keymap, escape_defaults])

function Prompt(prompt;
    prompt_prefix = "",
    prompt_suffix = "",
    keymap_dict = default_keymap_dict,
    keymap_func_data = nothing,
    complete = EmptyCompletionProvider(),
    on_enter = default_enter_cb,
    on_done = ()->nothing,
    hist = EmptyHistoryProvider(),
    sticky = false)

    Prompt(prompt, prompt_prefix, prompt_suffix, keymap_dict, keymap_func_data,
        complete, on_enter, on_done, hist, sticky)
end

run_interface(::Prompt) = nothing

init_state(terminal, prompt::Prompt) =
    PromptState(terminal, prompt, IOBuffer(), InputAreaState(1, 1),
    #=indent(spaces)=# -1)

function init_state(terminal, m::ModalInterface)
    s = MIState(m, m.modes[1], false, Dict{Any,Any}())
    for mode in m.modes
        s.mode_state[mode] = init_state(terminal, mode)
    end
    s
end

function run_interface(terminal, m::ModalInterface)
    s::MIState = init_state(terminal, m)
    while !s.aborted
        buf, ok, suspend = prompt!(terminal, m, s)
        while suspend
            @static if Sys.isunix(); ccall(:jl_repl_raise_sigtstp, Cint, ()); end
            buf, ok, suspend = prompt!(terminal, m, s)
        end
        eval(Main,
            Expr(:body,
                Expr(:return,
                     Expr(:call,
                          QuoteNode(mode(state(s, s.current_mode)).on_done),
                          QuoteNode(s),
                          QuoteNode(buf),
                          QuoteNode(ok)))))
    end
end

buffer(s::PromptState) = s.input_buffer
buffer(s::SearchState) = s.query_buffer
buffer(s::PrefixSearchState) = s.response_buffer

keymap(s::PromptState, prompt::Prompt) = prompt.keymap_dict
keymap_data(s::PromptState, prompt::Prompt) = prompt.keymap_func_data
keymap(ms::MIState, m::ModalInterface) = keymap(ms.mode_state[ms.current_mode], ms.current_mode)
keymap_data(ms::MIState, m::ModalInterface) = keymap_data(ms.mode_state[ms.current_mode], ms.current_mode)

function prompt!(term, prompt, s = init_state(term, prompt))
    Base.reseteof(term)
    raw!(term, true)
    enable_bracketed_paste(term)
    try
        activate(prompt, s, term, term)
        old_state = mode(s)
        while true
            kmap = keymap(s, prompt)
            fcn = match_input(kmap, s)
            kdata = keymap_data(s, prompt)
            # errors in keymaps shouldn't cause the REPL to fail, so wrap in a
            # try/catch block
            local state
            try
                state = fcn(s, kdata)
            catch e
                bt = catch_backtrace()
                warn(e, bt = bt, prefix = "ERROR (in the keymap): ")
                # try to cleanup and get `s` back to its original state before returning
                transition(s, :reset)
                transition(s, old_state)
                state = :done
            end
            if state === :abort
                return buffer(s), false, false
            elseif state === :done
                return buffer(s), true, false
            elseif state === :suspend
                if Sys.isunix()
                    return buffer(s), true, true
                end
            else
                @assert state === :ok
            end
        end
    finally
        raw!(term, false) && disable_bracketed_paste(term)
    end
end

end # module

max_stars_repo_name: baggepinnen/julia

max_issues_repo_name: baggepinnen/julia

max_forks_repo_name: afniedermayer/julia


text:
"""
    IndependentMOKernel(k::Kernel)

Kernel for multiple independent outputs with kernel `k` each.

# Definition

For inputs ``x, x'`` and output dimensions ``p, p'``, the kernel ``\\widetilde{k}``
for independent outputs with kernel ``k`` each is defined as
```math
\\widetilde{k}\\big((x, p), (x', p')\\big) = \\begin{cases}
    k(x, x') & \\text{if } p = p', \\\\
    0 & \\text{otherwise}.
\\end{cases}
```
Mathematically, it is equivalent to a matrix-valued kernel defined as
```math
\\widetilde{K}(x, x') = \\mathrm{diag}\\big(k(x, x'), \\ldots, k(x, x')\\big) \\in \\mathbb{R}^{m \\times m},
```
where ``m`` is the number of outputs.
"""
struct IndependentMOKernel{Tkernel<:Kernel} <: MOKernel
    kernel::Tkernel
end

function (κ::IndependentMOKernel)((x, px)::Tuple{Any,Int}, (y, py)::Tuple{Any,Int})
    return κ.kernel(x, y) * (px == py)
end

_mo_output_covariance(k::IndependentMOKernel, out_dim) = Eye{Bool}(out_dim)

function kernelmatrix(
    k::IndependentMOKernel, x::MOI, y::MOI
) where {MOI<:IsotopicMOInputsUnion}
    x.out_dim == y.out_dim ||
        throw(DimensionMismatch("`x` and `y` must have the same `out_dim`"))
    Kfeatures = kernelmatrix(k.kernel, x.x, y.x)
    Koutputs = _mo_output_covariance(k, x.out_dim)
    return _kernelmatrix_kron_helper(MOI, Kfeatures, Koutputs)
end

if VERSION >= v"1.6"
    function kernelmatrix!(
        K::AbstractMatrix, k::IndependentMOKernel, x::MOI, y::MOI
    ) where {MOI<:IsotopicMOInputsUnion}
        x.out_dim == y.out_dim ||
            throw(DimensionMismatch("`x` and `y` must have the same `out_dim`"))
        Kfeatures = kernelmatrix(k.kernel, x.x, y.x)
        Koutputs = _mo_output_covariance(k, x.out_dim)
        return _kernelmatrix_kron_helper!(K, MOI, Kfeatures, Koutputs)
    end
end

function Base.show(io::IO, k::IndependentMOKernel)
    return print(io, string("Independent Multi-Output Kernel\n\t", string(k.kernel)))
end

ext: jl


text:
"""
Monte carlo integration is a very easy and scalable way to do multidimentional integrals.
However, only single variable integrals are considered.

This function takes three outputs:
	- `f`: the function to integrate. (at the momment only single variable is suported)
	- `N`: Number of points to sample. For most simple functions, 1000 to 10,000 should be okay.
	- `span`: a tuple (start, end) for the integration limits

Examples:
```julia
julia> monte_carlo_integration(x->3*x^2,100000,(0,1)) # integrate a polynomial
1.0000037602209

julia> monte_carlo_integration(x->sin(x),1000,(0,pi)) # integrate the sin function
2.0018927826323756

```
	Refereces:
-https://www.scratchapixel.com/lessons/mathematics-physics-for-computer-graphics/monte-carlo-methods-in-practice/monte-carlo-integration
-https://kingaa.github.io/sbied/pfilter/monteCarlo.html

Contributed By-: [Ved Mahajan](https://github.com/Ved-Mahajan)
"""
function monte_carlo_integration(f,N,span)
	x_start,x_end = span
	rand_array = rand(x_start:0.0001:x_end,N)
	return sum(f.(rand_array))*(x_end - x_start)/float(N)
end

max_stars_repo_name: KohRongSoon/Julia

max_issues_repo_name: KohRongSoon/Julia

max_forks_repo_name: KohRongSoon/Julia


text:
function julia_startup_file()
    config_dir = abspath(homedir(), ".julia", "config")
    !isdir(config_dir) && mkpath(config_dir)
    res = abspath(config_dir,"startup.jl")
    !isfile(res) && open(res,"w") do io
        println(io,"")
    end
    res
end

function StartupTracer()
    """
    # FezzikAutoGenStart
    # to remove remove entire block
    try
        using Fezzik
        try
            Fezzik.trace()
        catch err
            @info "Something went wrong" err
        end
    catch e
        try
            using Pkg
            Pkg.add("Fezzik")
            import Fezzik
            try
                Fezzik.trace()
            catch err
                @info "Something went wrong" err
            end
        catch err
            @info "Something went wrong" err
        end
    end

    # FezzikAutoGenEnd
    """
end
function auto_trace(b::Bool = true)
    auto_trace(Val(b))
end

function auto_trace(::Val{true})
    startup = read(julia_startup_file(),String)
    !occursin("FezzikAutoGenStart",startup) &&
        (startup = StartupTracer() * "\n" * startup)
    open(julia_startup_file(),"w") do io
        println(io,startup)
    end
end

function auto_trace(::Val{false})
    skip = false
    startup = Vector{String}()
    for line in eachline(julia_startup_file())
        occursin("FezzikAutoGenStart",line) && (skip = true)
        if occursin("FezzikAutoGenEnd",line)
            skip = false
            continue;
        end
        !skip && push!(startup,line)
    end
    open(julia_startup_file(),"w") do io
        for line in startup
            println(io,line)
        end
    end
    rm(trace_dir;force=true , recursive = true)
    nothing
end


text:
mutable struct SuperObjCollision
    superObj::Vector{Object3D}
    function SuperObjCollision()
        new(Vector{Object3D}[])
    end
end

mutable struct SuperObjMass
    superObj::Vector{Object3D}
    function SuperObjMass()
        new(Vector{Object3D}[])
    end
end

mutable struct SuperObjMovable
    superObj::Vector{Object3D}
    function SuperObjMovable()
        new(Vector{Object3D}[])
    end
end

mutable struct SuperObjForce
    superObj::Vector{Object3D}
    function SuperObjForce()
        new(Vector{Object3D}[])
    end
end

mutable struct SuperObjVisu
    superObj::Vector{Object3D}
    function SuperObjVisu()
        new(Vector{Object3D}[])
    end
end

mutable struct SuperObjsRow
    superObjCollision::SuperObjCollision
    superObjMass::SuperObjMass
    superObjMovable::SuperObjMovable
    superObjForce::SuperObjForce
    superObjVisu::SuperObjVisu
    noCPair::Vector{Int64}
    function SuperObjsRow()
        new(SuperObjCollision(), SuperObjMass(), SuperObjMovable(), SuperObjForce(), SuperObjVisu(),  Vector{Int64}[])
    end
end


text:
module SoftPosit

export AbstractPosit, Posit8, Posit16, Posit32,
    Posit8_1, Posit16_1, Posit24_1,
    Posit8_2, Posit16_2, Posit24_2,
    notareal, minusone,
    AbstractQuire, Quire8, Quire16, Quire32, fms

import Base: Float64, Float32, Float16, Int32, Int64,
    UInt8, UInt16, UInt32,
    (+), (-), (*), (/), (<), (<=), (==), sqrt,
    bitstring, round, one, zero, promote_rule, eps,
    floatmin, floatmax, signbit, sign, isfinite,
    nextfloat, prevfloat, fma,
    exp, exp2, exp10, log, log2, log10, cos, sin, tan,
    expm1,log1p

# Load in `deps.jl`, complaining if it does not exist
const depsjl_path = joinpath(@__DIR__, "..", "deps", "deps.jl")
if !isfile(depsjl_path)
    error("SoftPosit not installed properly, run \"]build SoftPosit\", restart Julia and try again")
end
include(depsjl_path)

include("typedef.jl")
include("conversionFloatToPosit.jl")
include("conversionPositToFloat.jl")
include("conversionPositToPosit.jl")
include("conversionIntToPosit.jl")
include("conversionPositToInt.jl")
include("conversionHexBinToPosit.jl")
include("conversionBoolToPosit.jl")
include("conversionQuire.jl")
include("arithmetic.jl")
include("comparison.jl")
include("constants.jl")
include("round.jl")
include("print.jl")
include("nextprevfloat.jl")
include("eps.jl")
include("quire.jl")
include("explog_trigonometric.jl")

end


text:
using Treesitter
# using Test

parser = Treesitter.Parser()
Treesitter.set_language(parser, tree_sitter_c())
source_code = read(joinpath(@__DIR__, "corpus/easystruct.h"), String)

tree = parse_string(parser, source_code)
rootnode = node_rootof(tree)

srtpt = node_startpoint(rootnode)
endpt = node_endpoint(rootnode)


text:
# run 4 processor tests

push!(LOAD_PATH, abspath(joinpath(pwd(), "..")))

using PDESolver
#using Base.Test
using Base.Test
using ODLCommonTools
using PdePumiInterface  # common mesh interface - pumi
using SummationByParts  # SBP operators
using AdvectionEquationMod
using LinearSolvers
using NonlinearSolvers   # non-linear solvers
using OptimizationInterface
using ArrayViews
import ArrayViews.view
using Utils
using Input
using PETSc2

#------------------------------------------------------------------------------
# define tests and tags

#include("../TestSystem.jl")
using TestSystem
# define tags that will be used
include("../tags.jl")

# test list
global const AdvectionTests = TestList()

include("Nonlinearsolvers/crank_nicolson_PETSc_parallel/runtests.jl")
include("test_parallel4.jl")
"""
  Test energy stability in parallel
"""
function runtests_parallel4()
  @testset "----- Testing Parallel 4 -----" begin

    start_dir = pwd()
    cd("./energy")
    include(joinpath(pwd(), "runtests_parallel.jl"))
    cd(start_dir)
  end

  return nothing
end

#runtests_parallel4()
add_func1!(AdvectionTests, runtests_parallel4, [TAG_SHORTTEST])

#------------------------------------------------------------------------------
# run tests
@testset "----- Running Advection 4 processor tests -----" begin
  runTestSystem(AdvectionTests, solvePDE, ARGS)
end

#------------------------------------------------------------------------------
# cleanup


text:
# Use baremodule to shave off a few KB from the serialized `.ji` file
baremodule ViennaRNA_jll
using Base
using Base: UUID
import JLLWrappers

JLLWrappers.@generate_main_file_header("ViennaRNA")
JLLWrappers.@generate_main_file("ViennaRNA", UUID("b7a990de-7fa3-5a2e-8a39-d875e4dafecd"))
end  # module ViennaRNA_jll


text:
using Documenter, Contour

makedocs()

deploydocs(
    repo = "github.com/tlycken/Contour.jl",
    julia = "0.5",
    deps = Deps.pip("pygments", "mkdocs", "python-markdown-math")
)


text:
@testset "DataLoader" begin
    X = reshape([1:10;], (2, 5))
    Y = [1:5;]

    d = DataLoader(X, batchsize=2)
    @inferred first(d)
    batches = collect(d)
    @test eltype(batches) == eltype(d) == typeof(X)
    @test length(batches) == 3
    @test batches[1] == X[:,1:2]
    @test batches[2] == X[:,3:4]
    @test batches[3] == X[:,5:5]

    d = DataLoader(X, batchsize=2, partial=false)
    @inferred first(d)
    batches = collect(d)
    @test eltype(batches) == eltype(d) == typeof(X)
    @test length(batches) == 2
    @test batches[1] == X[:,1:2]
    @test batches[2] == X[:,3:4]

    d = DataLoader((X,), batchsize=2, partial=false)
    @inferred first(d)
    batches = collect(d)
    @test eltype(batches) == eltype(d) == Tuple{typeof(X)}
    @test length(batches) == 2
    @test batches[1] == (X[:,1:2],)
    @test batches[2] == (X[:,3:4],)

    d = DataLoader((X, Y), batchsize=2)
    @inferred first(d)
    batches = collect(d)
    @test eltype(batches) == eltype(d) == Tuple{typeof(X), typeof(Y)}
    @test length(batches) == 3
    @test length(batches[1]) == 2
    @test length(batches[2]) == 2
    @test length(batches[3]) == 2
    @test batches[1][1] == X[:,1:2]
    @test batches[1][2] == Y[1:2]
    @test batches[2][1] == X[:,3:4]
    @test batches[2][2] == Y[3:4]
    @test batches[3][1] == X[:,5:5]
    @test batches[3][2] == Y[5:5]

    # test with NamedTuple
    d = DataLoader((x=X, y=Y), batchsize=2)
    @inferred first(d)
    batches = collect(d)
    @test eltype(batches) == eltype(d) == NamedTuple{(:x, :y), Tuple{typeof(X), typeof(Y)}}
    @test length(batches) == 3
    @test length(batches[1]) == 2
    @test length(batches[2]) == 2
    @test length(batches[3]) == 2
    @test batches[1][1] == batches[1].x == X[:,1:2]
    @test batches[1][2] == batches[1].y == Y[1:2]
    @test batches[2][1] == batches[2].x == X[:,3:4]
    @test batches[2][2] == batches[2].y == Y[3:4]
    @test batches[3][1] == batches[3].x == X[:,5:5]
    @test batches[3][2] == batches[3].y == Y[5:5]

    # test interaction with `train!`
    θ = ones(2)
    X = zeros(2, 10)
    loss(x) = sum((x .- θ).^2)
    d  = DataLoader(X)
    Flux.train!(loss, [θ], ncycle(d, 10), Descent(0.1))
    @test norm(θ) < 1e-4

    # test interaction with `train!`
    θ = zeros(2)
    X = ones(2, 10)
    Y = fill(2, 10)
    loss(x, y) = sum((y - x'*θ).^2)
    d  = DataLoader((X, Y))
    Flux.train!(loss, [θ], ncycle(d, 10), Descent(0.1))
    @test norm(θ .- 1) < 1e-10
end

@testset "CMUDict" begin
    @test cmudict()["CATASTROPHE"] == :[K,AH0,T,AE1,S,T,R,AH0,F,IY0].args

    @test length(CMUDict.phones()) == 39

    @test length(CMUDict.symbols()) == 84
end

@testset "MNIST" begin
    @test MNIST.images()[1] isa Matrix
    @test MNIST.labels() isa Vector{Int64}
end

@testset "FashionMNIST" begin
    @test FashionMNIST.images()[1] isa Matrix
    @test FashionMNIST.labels() isa Vector{Int64}
end

@testset "Sentiment" begin
    @test Data.Sentiment.train() isa Vector{Data.Tree{Any}}
end

@testset "Iris" begin
    @test Iris.features() isa Matrix
    @test size(Iris.features()) == (4,150)

    @test Iris.labels() isa Vector{String}
    @test size(Iris.labels()) == (150,)
end

@testset "Housing" begin
    @test Housing.features() isa Matrix # test broken due to SSL certifate expiration problem
    @test size(Housing.features()) == (506, 13)

    @test Housing.targets() isa Array{Float64}
    @test size(Housing.targets()) == (506, 1)
end

@testset "Tree show" begin
    # testcase for issue #1354
    # testing that methods(Base.show) does not throw. Having something more specific would be too fragile
    buf = IOBuffer()
    Base.show(buf, filter(x->x.module == Flux, methods(Base.show).ms))
    str_repr = String(take!(buf))
    @test !isempty(str_repr)
end


text:
"""
    reflector!(y, k) → τ

Implicit representation of a Householder reflection H = I - τ [v; 1] [vᵀ 1]
such that H*y = eₖβ, 1 ≤ real(τ) ≤ 2 and abs(τ - 1) ≤ 1. Updates `y` in-place,
in the sense that: `v := y[1:k-1]` and y[k] = β.

In the edge case iszero(y[1:k-1]) and iszero(imag(y[k])) then τ = 0.

Based on LAPACK 3.8 clarfg.

Another nice reference is Mezzadri, Francesco. "How to generate
random matrices from the classical compact groups." arXiv preprint
math-ph/0609050 (2006).
"""
function reflector!(y::AbstractVector{T}, k::Integer) where {T}
    @inbounds begin
        k ≤ 0 || k > length(y) && return zero(T)

        # Norm except the last entry.
        xnrm = zero(real(T))
        @simd for idx in OneTo(k-1)
            xnrm += abs2(y[idx])
        end

        α = y[k]

        iszero(xnrm) && iszero(imag(α)) && return zero(T)

        xnrm = √xnrm

        β = -copysign(hypot(α, xnrm), real(α))
        τ = (β - α) / β
        α = inv(α - β)

        # Rescale
        @simd for i = OneTo(k-1)
            y[i] *= α
        end

        y[k] = β

        return τ'
    end
end

struct Reflector{T}
    vec::Vector{T}
    offset::RefValue{Int}
    len::RefValue{Int}
    τ::RefValue{T}

    Reflector{T}(max_len::Int) where {T} = new{T}(
        Vector{T}(undef, max_len),
        Base.RefValue(1),
        Base.RefValue(0),
        Base.RefValue(zero(T))
    )
end

function reflector!(z::Reflector, k::Integer)
    z.len[] = k
    z.τ[] = reflector!(z.vec, k)
    return z.τ[];
end

"""
We have the Krylov relation

A[VQ₁ VQ₂] = [VQ₁ VQ₂][R₁₁ R₁₂; + hv[. eₖᵀQ₂]
                       .   R₂₂]

Column VQ₂ has column indices from:to
"""
function restore_arnoldi!(H::AbstractMatrix{T}, from::Integer, to::Integer, Q, G::Reflector{T}) where {T}
    m, n = size(H)

    @inbounds begin

        # Size of the initial reflector
        len = length(from:to)

        len ≤ 2 && return nothing

        G.offset[] = from

        # Copy over the last row of Q
        @simd for i = OneTo(len)
            G.vec[i] = Q[n,i+from-1]'
        end

        # Zero out entries 1:len-1
        τ₁ = reflector!(G, len)

        # Apply to Q from the right.
        rmul!(Q, G, 1, n - 1)

        # Handle the last row by hand
        @simd for i = from:to-1
            Q[n,i] = zero(T)
        end
        Q[n,to] = G.vec[len]'

        # Then apply to H from both sides.
        rmul!(H, G, 1, to)
        lmul!(G, H, from, to)

        # Then restore the Hessenberg structure in H, which is now a full matrix.
        for i = len-1:-1:2
            row = from + i

            # Copy over row `row`
            @simd for j = OneTo(i)
                G.vec[j] = H[row,j+from-1]'
            end

            # Construct a reflector from it
            τ₂ = reflector!(G, i)

            # Apply it to the right to H
            rmul!(H, G, 1, row-1)

            # Zero out things by hand
            @simd for j = OneTo(i - 1)
                H[row,j+from-1] = zero(T)
            end
            H[row, i-1+from] = G.vec[i]'

            # Apply if from the left.
            lmul!(G, H, from, to)

            # Accumulate the reflectors
            rmul!(Q, G, 1, n)
        end

        # Finally in the Arnoldi decomp we want a last residual term of the form
        # h * vₖ₊₁ * eₖᵀ, so we absorb the last Q-entry in the Hessenberg matrix!
        H[to+1,to] = Q[end,to] * H[m, n]

    end

    nothing
end

# Implementations are terrible here :(

function lmul!(G::Reflector, H::AbstractMatrix{T}, from::Int, to::Int) where {T}

    len = G.len[]
    offset = G.offset[]
    z = G.vec
    τ = G.τ[]

    iszero(τ) && return nothing

    @inbounds for col = from:to
        dot = zero(T)
        @simd for i = 1 : len - 1
            dot += z[i]' * H[i + offset - 1, col]
        end
        dot += H[len + offset - 1, col]
        dot *= τ
        @simd for i = 1 : len - 1
            H[i + offset - 1, col] -= dot * z[i]
        end
        H[len + offset - 1, col] -= dot
    end
end

function rmul!(H::AbstractMatrix{T}, G::Reflector, from::Int, to::Int) where {T}

    len = G.len[]
    offset = G.offset[]
    z = G.vec
    τ = G.τ[]

    iszero(τ) && return nothing

    @inbounds for row = from:to
        dot = zero(T)
        @simd for i = 1:len-1
            dot += H[row, i + offset - 1] * z[i]
        end
        dot += H[row, offset + len - 1]
        dot *= τ'
        @simd for i = 1 : len - 1
            H[row,i+offset-1] -= dot * z[i]'
        end
        H[row, offset + len - 1] -= dot
    end
end


text:
using ModelingToolkit, DiffEqOperators, OrdinaryDiffEq

# This works after PR in DiffEqOperators for Neumann/Robin BCS gets merged.

# Constants -- these are left out of the parameter list and passed as hard coded
# coefficient values for now.
dx = 1.0e-4 # compartment size (1 µm in cm)
Iapp = 5e-9 # in mA
Vinit = -65.0 # mV
a = 2.0e-4 # 2 µm given in cm
r_L = 10000 # 10 kΩ*cm longitudinal resistance
area = 2*pi*a*dx # area of one compartment in cm^2
gl = 30*area # mS/cm^2 we increase ̅gₗfor illustrative purposes
El  = -54.4 # mV
Cm  = 1.0e-3*area # mF / cm^2

@parameters t x
@variables V(..)
@derivatives Dt'~t
@derivatives Dxx''~x
@derivatives Dx'~x

# The Cable Equation with passive leak conductance
eqs = [Dt(V(t,x)) ~ a/(2*r_L*Cm) * Dxx(V(t,x)) - (gl/Cm)*(V(t,x) - El)]

# Cable equation BCs + ICs
bcs = [V(0.0,x) ~ Vinit,
       Dx(V(t,0.0)) ~ -(r_L*Iapp)/(pi*a^2), # Neumann BC for current injection
       Dx(V(t,0.2)) ~ 0.0] # Neumann BC for "sealed end"

domains = [t ∈ IntervalDomain(0.0, 200.0), # simulate 200ms
           x ∈ IntervalDomain(0.0, 0.2)] # over a cable of length 2000 µm

sys = PDESystem(eqs, bcs, domains, [t, x], [V])

order = 2
discretization = MOLFiniteDifference(dx,order)
prob = discretize(sys,discretization)

sol = solve(prob, KenCarp47())

max_stars_repo_name: wsphillips/FutureNeuralSimulation

max_issues_repo_name: wsphillips/FutureNeuralSimulation

max_forks_repo_name: wsphillips/FutureNeuralSimulation


text:
### A Pluto.jl notebook ###
# v0.12.21

using Markdown
using InteractiveUtils

# ╔═╡ 5bc68900-7ecf-11eb-0d3a-f7f997d8e14a
begin
	using LinearAlgebra
	using Printf
	using PlutoUI
end

# ╔═╡ f3cbdd70-836d-11eb-19d2-25a48489f506
Base.show(io::IO, f::Float64) = @printf io "%.3f" f

# ╔═╡ b90f4c50-7f79-11eb-1552-e997256fd09f
md"
## MapView and it's application to simulating quantum computations
"

# ╔═╡ 79824ea0-7f7b-11eb-2ef3-4d04e143ecfb
md"
#### 1. MapView's declaration and interfaces

MapView is similar to a regular Julia view. However, the data it accesses is determined by an internal map. This allows for a reorganization of the array in question. Used in cases where it is convenient to have two different orderings of the same array at the same time.
"

# ╔═╡ 722db420-7ecf-11eb-063d-b359e7a9020b
struct MapView{T, N} <: AbstractArray{T, N}
	indices::Array{Int, N}
	original::Array{T, N}
end

# ╔═╡ daa83220-7ed2-11eb-0180-bd81ab5dd09d
# AbstractArray interfaces for MapView
begin
	Base.IndexStyle(::Type{MapView}) = IndexLinear()
	Base.getindex(X::MapView, i::Int) = X.original[X.indices[i]]

	function Base.setindex!(X::MapView{T}, v::V, i::Int) where {T, V}
		X.original[X.indices[i]] = v
	end

	Base.firstindex(X::MapView) = 1
	Base.lastindex(X::MapView) = length(X)
end

# ╔═╡ f1909b30-7ed2-11eb-1d69-0371f218c6c1
# Iterator interfaces for MapView
begin
	function Base.iterate(iter::MapView)
		if length(iter) == 0
			nothing
		else
			iter[1], 1
		end
	end

	function Base.iterate(iter::MapView, state)
		if state >= length(iter)
			nothing
		else
			iter[state + 1], state + 1
		end
	end

	Base.eltype(::Type{MapView{T}}) where T = T
	Base.size(iter::MapView) = size(iter.indices)
end

# ╔═╡ cc9bb1c0-7f7c-11eb-09a9-bb1854c107d8
md"
#### 2. A more efficient way to simulate quantum computation

Below is a use case of MapView, at the same time showcasing a more efficient way to simulate quantum gate operations on a set of qBits.
"

# ╔═╡ 3e690bc0-7eee-11eb-346e-4573f4f5fbd0
⊗(x, y) = kron(x, y)

# ╔═╡ ffd7b6b0-7ef0-11eb-2bdd-67ef92238d66
# Generates a mapping that moves qBit k in N qBits to the top
# If k is negative, treat k as NOT'ed
# O(2^N) complexity
function bubble(k::Int, N::Int)
	index_list = collect(1:2^N)
	part_size = 2^(N - abs(k))
	partitions = collect(Iterators.partition(index_list, part_size))

	odds  = 1:2:length(partitions)
	evens = 2:2:length(partitions)

	if k > 0
		part_map = collect(Iterators.flatten((odds, evens)))
	# if k < 0 generate a map correspond to the qBit in question being NOT'ed
	else
		part_map = collect(Iterators.flatten((evens, odds)))
	end

	mapped_parts = MapView(part_map, partitions)

	collect(Iterators.flatten(mapped_parts))
end

# ╔═╡ 69d6e370-7ef5-11eb-3a2b-a7802a5adc8b
# Generates a mapping such that the qbits in ks are at the top of N qBits
# With the top to bottom ordering corresponds to begin to end of ks
# Example:
# 	Let there be 5 qBit lines in order:
#		ψ₁ ψ₂ ψ₃ ψ₄ ψ₅
#   multibubble([2, 4], 5) would generate a mapping that corresponds to:
#		ψ₂ ψ₄ ψ₁ ψ₃ ψ₅
#
# Complexity: O(n * 2^N + n^2)
# where:
#  		N is the number of qBits
#       n is the number of qBits to be bubbled

function multibubble(ks::Vector{Int}, N::Int)
	final_map = collect(1:2^N)

	push_down_list = []
	for k in reverse(ks)
		# separate sign from value
		(sign, k) = (div(k, abs(k)), abs(k))

		push_down = 0
		for i in push_down_list
			if k < i
				push_down += 1
			elseif k == i
				throw("bubbling list has dublicate entry")
			end
		end
		push!(push_down_list, k)

		map = bubble(sign * (k + push_down), N)
		final_map = collect(MapView(map, final_map))
	end

	final_map
end

# ╔═╡ 8d46e6ce-7f99-11eb-1cb4-3358ca6564b5
function applygate!(
		ψ::V,
		Gate::M,
		target::Vector{Int};
		control::Vector{Int} = Vector{Int}()
		) where {V <: AbstractVector{<: Number}, M <: AbstractMatrix{<: Number}}

	N = Int(log2(length(ψ)))
	n = length(target)

	@assert size(Gate)[1] == size(Gate)[2] "Invalid gate"
	@assert size(Gate)[1] == 2^n "Mismatch gate and # of input"

	top_qbit_list = [control; target]
	partition_size = div(length(ψ), 2^length(top_qbit_list))

	# Generate a mapping that bubbles all relevent qBits to the top
	# Since in controlled gates' operations,
	# 	only the bottom right of the matrix (the Gate application) is non-trivial,
	#   only takes the end side of ψ that corresponds to the Gate
	bubble_map = multibubble(top_qbit_list, N)
	gate_index = length(ψ) - size(Gate)[1] * partition_size + 1
	map_ψ = MapView(bubble_map[gate_index:end], ψ)

	# Apply Gate on ψ
	map_ψ_part = collect(Iterators.partition(map_ψ, partition_size))
	map_ψ .= collect(Iterators.flatten(Gate * map_ψ_part)) # ψ mutated here
end

# ╔═╡ 2e692000-7fbd-11eb-0778-d319c4e81810
md"
#### 3. Examples
"

# ╔═╡ 1f485320-7eeb-11eb-2088-1d5554d6d065
# Initialize 3 qBits
begin
	q₁ = [1, 1] / sqrt(2)
	q₂ = [1, 1] / sqrt(2)
	q₃ = [1, -1] / sqrt(2)
end

# ╔═╡ fbfe7840-7fad-11eb-3160-c994a748ae2a
# This routine below simulates the following configuration
#
# |ψ₁⟩ -------x---------
#             |
# |ψ₂⟩ -------|---------
#             |
# |ψ₃⟩ -------x---------
begin
	ψ = q₁ ⊗ q₂ ⊗ q₃
	# This is the swapping operator
	SWAP = [1 0 0 0;
		    0 0 1 0;
		    0 1 0 0;
		    0 0 0 1]

	applygate!(ψ, SWAP, [3, 1])
	ψ == q₃ ⊗ q₂ ⊗ q₁
end

# ╔═╡ 45191f7e-7fb3-11eb-1a83-49475fe38f82
# This routine below simulates the following configuration
#
# |ψ₁⟩ -------•---------
#             |
# |ψ₂⟩ -------|---------
#             |
# |ψ₃⟩ -------⊗---------
begin
	ψ2 = q₁ ⊗ q₂ ⊗ q₃
	ψ3 = q₁ ⊗ q₂ ⊗ q₃
	NOT = [0 1;
		   1 0]

	applygate!(ψ2, NOT, [3], control=[1])
	applygate!(ψ3, NOT, [3])
	ψ2, ψ3
end

# ╔═╡ 881ecd30-7f85-11eb-3d93-55b1a6dd7039
md"
#### 4. Complexity analysis

##### 4.1. Complexity

Let:
*  $N$ be the number of qBits
*  $n$ be the size of the quantum gate

First, the generation of a `MapView` of $\psi$ involves the function `multibubble`, which has a complexity of $\mathcal{O}(n2^N + n^2)$

The application of the quantum gate involves a matrix to vector multiplication with a matrix size of $2^{2n}$ and the same number of operations. However, each operation is actually a scalar to vector multiplication with vector size of $2^{N-n}$, which results in $\mathcal{O}(2^{N+n})$ complexity.

Since $2^{N+n} > n2^{N} > n^2$ for large enough $N$ and $n$, the complexity of the whole routine is $\mathcal{O}(2^{N+n})$.

##### 4.2. Comparison to the naive implementation

With the naive implementation, the application of the quantum gate involves matrix to vector multiplications with matrix size $2^{2N}$. This leads to a complexity of $\mathcal{O}(2^{2N})$.

Because $n \leq N$, the above routine is more efficient than the naive implementation. How much of a performance improvement depends on how many qBits involved in an operation compared to the total number of qBits. In the case of $n = N$, that is if the quantum gate involves all available qBits, this method performs no better than the naive implementation. That said, most basic operations only operate on a couple of qBits at a time, and bigger operations can usually be decomposed to a series of smaller ones.

This method is also compatible with a different method that optimizes controled gates, which is not specified in this notebook. This is to be addressed in the future.

"

# ╔═╡ e77cd580-80eb-11eb-2686-016c6fdd8bf1
md"
#### 5. Implementation of the quip syntax

"

# ╔═╡ fa0e3580-8164-11eb-05da-d10765d23a9a
const GATES = Dict(:I => () -> [1 0;
								0 1],

				   :X => () -> [0 1;
								1 0],
				   :RX => γ -> exp(im * γ * GATES[:X]()),

				   :Y => () -> [0 -im;
								im 0],
				   :RY => β -> exp(im * β * GATES[:Y]()),

				   :Z => () -> [1  0;
								0 -1],
				   :RZ => α -> exp(im * α * GATES[:Z]()),

				   :H => () -> [1  1;
								1 -1] / sqrt(2),

				   :S => () -> [1 0;
						        0 im],

				   :T => () -> [1 0;
						        0 exp(im * π / 4)],

				   :PHASE => θ -> [1 0; 0 exp(im * θ)],

				   :SWAP => () -> [1 0 0 0;
		                           0 0 1 0;
		 						   0 1 0 0;
		                           0 0 0 1],
)

# ╔═╡ d233fcf0-813e-11eb-0a37-e54e39a36073
# Quantum Instruction each gate represents an operation on the state of the wave function
struct QInstr
	op::Symbol             # Operation code
	func::Function         # Store the subroutine when op == :callfun

	param::Vector{Float64} # Parameters for op or func

	# Specify qBits that are acted on
	# In measurement mode, specify [target qbit, target cbit]
	target::Vector{Int}

	# specify control bits
	# negative value indicates control-on-zero
	control::Vector{Int}
	cbit_ctrl::Bool        # True means the control bits are classical
end

# ╔═╡ 43811d70-813f-11eb-3614-1315573f2d76
# Show interface for gate
function Base.show(io::IO, g::QInstr)
	op = g.op
	param = g.param

	# Function call mode
	if op == :funcall
		funcall = Expr(:call, g.func, param...)
		show(io, "$funcall")

	# Measurement mode
	elseif op == :measure
		qbit = g.target[1]
		cbit = Expr(:ref, :C, g.target[2])
		show(io, "$qbit => $cbit")
	# Standard gate mode
	else
		op_param = isempty(param) ? op : Expr(:call, op, param...)

		target = length(g.target) == 1 ? g.target[1] : tuple(g.target...)

		ctrl_expr = g.cbit_ctrl ? [Expr(:ref, :C, i) for i in g.control] : g.control
		control = length(ctrl_expr) == 1 ? ctrl_expr[1] : tuple(ctrl_expr...)

		if isempty(ctrl_expr)
			show(io, "$op_param >> $target")
		else
			show(io, "$op_param >> $target | $control")
		end
	end
end

# ╔═╡ 61436fd0-7ed7-11eb-23d6-ed68bf61a769
# Show interface for MapView
Base.show(io::IO, x::MapView) = Base.show(io, collect(x))

# ╔═╡ d0eb8520-8143-11eb-1f1b-27c008fd716d
# Functions that helps streamline the parsing procedure
begin
	force_params(s::Symbol) = Expr(:call, s)
	force_params(e::Expr) = e

	force_tuple(n::Number) = Expr(:tuple, n)
	force_tuple(s::Symbol) = Expr(:tuple, s)
	function force_tuple(e::Expr)
		if e.head == :tuple
			e
		else
			Expr(:tuple, e)
		end
	end

	# Flatten instruction collections
	flatten(i::QInstr) = [i]
	function flatten(a::AbstractArray)
		flattened = [flatten(i) for i in a]
		vcat(flattened...)
	end

	dummyfun() = 1 # dummy function
end

# ╔═╡ 7f4adfc0-85aa-11eb-288e-fdf2569ed30b
# Parsing classical bit expressions: C[i]
begin
	function parse_cbit(expr::Expr)
		@assert expr.head == :ref "Not a classical bit: $expr"
		@assert expr.args[1] == :C "Bits can only take the form C[i]"
		expr.args[2]
	end

	parse_cbit(other) = throw("Not a classical bit: $other")
end

# ╔═╡ 44603d30-886e-11eb-1313-4d8adc9702da
# Parsing "not" expressions: !Expr
begin
	function parse_not(expr::Expr)
		if expr.head == :call && expr.args[1] == :!
			(-1, expr.args[2])
		else
			(1, expr)
		end
	end

	parse_not(other) = (1, other)
end

# ╔═╡ d89eb340-8153-11eb-1341-6518040a962d
begin
	function parse_entry(entry::Expr)
		##############################################
		# List expresion:
		# 	[sub expression 1, sub expression 2, ...]
		if entry.head == :vcat || entry.head == :vect
			parsed = [parse_entry(e) for e in entry.args]
			return Expr(:vcat, parsed...)

		##############################################
		# List comprehension expression:
		# 	[sub_expr for_expr if_expr]
		elseif entry.head == :comprehension
			generator = entry.args[1]
			generator.args[1] = parse_entry(generator.args[1])
			generator.args[2] = esc(generator.args[2])
			return Expr(:comprehension, generator)

		###############################
		# QInstr expression
		# 	+ Measure mode
		#	+ Standard gate mode
		#	+ Function call mode
		elseif entry.head == :call
			control = []
			classical = []
			cbit_ctrl = false
			funcall = dummyfun # dummy function

			####################################
			# Measure mode: qBit => cBit
			if entry.args[1] == :(=>)
				op = Meta.quot(:measure)
				qbit = entry.args[2]
				cbit = parse_cbit(entry.args[3])
				target = Expr(:vect, qbit, cbit)

				return :(QInstr($op, $funcall, [], $target, $control, $cbit_ctrl))
			end

			###################################################
			# Standard gate mode: OP(param) >> target | control
			if entry.args[1] == :| # Parsing control
				control_expr = force_tuple(entry.args[3]).args

				# Parsing NOT'ed expressions
				control_expr = parse_not.(control_expr)

				# Check for classical control mode
				if typeof(control_expr[1][2]) == Expr
					cbit_ctrl = control_expr[1][2].head == :ref
				end

				# Process control bit expressions depends on cbit_mode
				if cbit_ctrl
					# Parse cBit values
					control_expr = [(mult, parse_cbit(expr))
						for (mult, expr) in control_expr]

				# qbit mode
				else
					# sanity check
					for expr in control_expr
						if typeof(expr) == Expr
							@assert expr.head != :ref "not a qBit $expr"
						end
					end
				end
				# Applying NOT'ed expressions
				control_expr = [Expr(:call, :*, mult, expr)
					for (mult, expr) in control_expr]

				control = esc(Expr(:vect, control_expr...))
				entry = entry.args[2]
			end

			@assert entry.head == :call "Invalid quip entry $entry"
			if entry.args[1] == :>> # Parsing Operation
				# Parse target
				target = esc(Expr(:vect, force_tuple(entry.args[3]).args...))

				# Parse op and param
				op_and_param = force_params(entry.args[2]).args
				op = Meta.quot(op_and_param[1])
				param = esc(Expr(:vect, op_and_param[2:end]...))

				return :(QInstr($op, $funcall, $param, $target, $control, $cbit_ctrl))
			end

			##################################
			# Function call mode: func(param)
			op_and_param = entry.args
			op = Meta.quot(:funcall)
			param = esc(Expr(:vect, op_and_param[2:end]...))

			func = esc(op_and_param[1])

			return :(QInstr($op, $func, $param, [], $control, $cbit_ctrl))

		# Branch expression a ? b : c
		elseif entry.head == :if
			a = entry.args[1]
			b = entry.args[2]
			c = entry.args[3]
			return Expr(:if, esc(a), parse_entry(b), parse_entry(c))

		# Dot expression a.b
		elseif entry.head == :(.)
			return entry
		end

		throw("can't parse $entry")
	end

	function parse_entry(entry::Symbol)
		esc(entry)
	end
end

# ╔═╡ 317c8920-813f-11eb-2048-f1ff2bafeab5
macro quip(expr)
	if expr.head == :(=)
		lhs = expr.args[1]
		rhs = expr.args[2]
	else
		rhs = expr
	end

	if rhs.head == :block
		rhs = rhs.args[2]
	end

	rhs = parse_entry(rhs)

	rhs = Expr(:call, :flatten, rhs)
	if expr.head == :(=)
		:($(esc(lhs)) = $rhs)
	else
		:($rhs)
	end
end

# ╔═╡ 5a916b00-80a9-11eb-2cc6-93f42781e1b6
####################################
# Quip declaration example
begin
	quip1(rx_param) = @quip [
		RX(rx_param) >> 3 | 1  ;
		H            >> 1 | 2  ;
		1 => C[2]]

	quip2 = @quip [
	 	H >> 2;
	 	quip1(1)]

	quip3(a) = @quip [iseven(i) ? H >> (i % 3 + 1) : quip2 for i in 1:a]

	(quip1(π / 4), quip2, quip3(10))
end

# ╔═╡ c73aafc0-8287-11eb-1a3e-2de3296a35dc
# Type aliases
const Quip = Vector{QInstr}

# ╔═╡ 114b56c0-8240-11eb-15bc-dd322c881361
# The Quantum Virtual Machine,
# 	a Turing machine that holds the instruction set
#	as well as the current state of the wave function
struct QVM{R <: Real}
	# Stacks, each element is a stack frame
	stack::Vector{Quip}
	pc_stack::Vector{Int}

	# Classical memory
	reg::Vector{Bool}

	# Wavefunction
	wfn::Vector{Complex{R}}

	# A dictionary of primitive operations
	dict::Dict{Symbol, Function}

	function QVM{R}(quip::Vector{QInstr}, nbit::Int;
			dict=GATES, nreg=32 ) where R <: Real

		wfn = zeros(Complex{R}, 2^nbit)
		wfn[1] = 1

		registers = zeros(Int, nreg)
		new([quip], [1], registers, wfn, dict)
	end
end

# ╔═╡ 6929cfb0-82c8-11eb-3857-8df1ea9a3a88
# pretty print the current stack
# for internal use by showstate
function showstack(stack::Vector{QInstr}, pc::Int, n::Int; io::IO=stdout)
	len = length(stack)

	# Checking boundaries
	if pc - n < 1
		s = 1
		e = 1 + 2n > len ? len : 1 + 2n
	elseif pc + n > len
		e = len
		s = 1 - 2n < 1 ? 1 : len - 2n
	else
		s = pc - n
		e = pc + n
	end

	# Print stack
	if s != 1
		println(io, "...")
	end

	for i in s:e
		print(io, "$i: $(stack[i])")
		if i == pc
			println(io, "   <--- pc")
		else
			println(io)
		end
	end

	if e != len
		println(io, "...")
	end

	if pc > len
		println(io, "$(len + 1):  <- pc")
	end
end

# ╔═╡ 4faadd40-82c8-11eb-2d7e-f7e533a7e495

function showstate(vm::QVM, n=2; io::IO=stdout)
	println(io, "##########################")
	for i in eachindex(vm.stack)
		stack = vm.stack[i]
		pc = vm.pc_stack[i]

		println(io, "$i ---------------------------")
		showstack(stack, pc, n, io=io)
		println(io)
	end
end

# ╔═╡ f593d63e-823b-11eb-2f6b-a91be5d313bf
function step!(vm::QVM)
	dict = vm.dict
	quip = vm.stack[end]
	pc = vm.pc_stack[end]

	################################################
	# PC reached the end of the current stack frame
	#
	if pc > length(quip)
		# VM reached the end of program do nothing
		if length(vm.stack) == 1
			return false
		end

		# pop stack frame
		pop!(vm.stack)
		pop!(vm.pc_stack)
		vm.pc_stack[end] += 1 # increment pc
		return true
	end

	instr = quip[pc]
	op = instr.op
	func = instr.func
	param = instr.param
	target = instr.target
	control = instr.control
	cbit_ctrl = instr.cbit_ctrl

	#####################################
	# Function call push new stack frame
	#
	if op == :funcall
		new_quip = func(param...)
		push!(vm.stack, new_quip)
		push!(vm.pc_stack, 1)

	##########################################################
	# Measurement, collapse wave function and save to register
	#
	elseif op == :measure
		qbit = target[1]
		cbit = target[2]
		# Bases
		bas0 = [1; 0]
		bas1 = [0; 1]

		wfn0 = deepcopy(vm.wfn)
		applygate!(wfn0, bas0 * bas0', [qbit])
		P0 = vm.wfn' * wfn0

		# collapse to 0 state
		if rand() < norm(P0)
			vm.reg[cbit] = false
			vm.wfn .= wfn0 / sqrt(P0)

		# collapse to 1 state
		else
			wfn1 = vm.wfn - wfn0
			P1 = 1 - P0

			vm.reg[cbit] = true
			vm.wfn .= wfn1 / sqrt(P1)
		end
		vm.pc_stack[end] += 1 # increment pc

	##################################
	# Gate operation, call applygate!
	#
	else
		operator = get(dict, op) do
			throw("$op not in dict, this should not happen")
		end

		# cBit control
		if cbit_ctrl
			conds = [vm.reg[abs(i)] ⊻ (i < 0) for i in control]
			if reduce((a, b) -> a && b, conds)
				applygate!(vm.wfn, operator(param...), target)
			end

		# qBit control
		else
			applygate!(vm.wfn, operator(param...), target, control=control)
		end
		vm.pc_stack[end] += 1 # increment pc
	end

	true
end

# ╔═╡ ea7a2ed0-8600-11eb-2497-bb23e393d273
begin
	qft_rotations(n, k, o) = @quip [j==k ?
										H >> k :
										PHASE(2π / 2^(j-k+1)) >> k | j
									for j in k:(n+o)]

	qft_swaps(n, o) = @quip [SWAP >> (j+o, n-j+1+o) for j in 1:div(n, 2)]

	qft(n, o=0) = @quip [qft_rotations(n, k, o) for k in (1+o):(n+o)]

end

# ╔═╡ a59e1620-828e-11eb-2a19-15b99805ac4d
with_terminal() do
	N = 2
	quip = @quip [
		X >> 1            ;
		1 => C[1]         ;
		X >> 2 | !C[1]    ;
	]

	for i in 1:1
		vm = QVM{Float64}(quip, N)
		while step!(vm)
			# showstate(vm)
		end
		for (i, j) in enumerate([norm(x)^2 for x in vm.wfn])
			println("$i: $j")
		end
	end
end

# ╔═╡ ae503700-88db-11eb-2c85-5574fe9aeca5
 @quip [i == 3 ? H >> i : X >> i | (i + 1) for i in 1:3]

# ╔═╡ Cell order:
# ╠═5bc68900-7ecf-11eb-0d3a-f7f997d8e14a
# ╠═f3cbdd70-836d-11eb-19d2-25a48489f506
# ╟─b90f4c50-7f79-11eb-1552-e997256fd09f
# ╟─79824ea0-7f7b-11eb-2ef3-4d04e143ecfb
# ╠═722db420-7ecf-11eb-063d-b359e7a9020b
# ╠═daa83220-7ed2-11eb-0180-bd81ab5dd09d
# ╠═f1909b30-7ed2-11eb-1d69-0371f218c6c1
# ╠═61436fd0-7ed7-11eb-23d6-ed68bf61a769
# ╟─cc9bb1c0-7f7c-11eb-09a9-bb1854c107d8
# ╠═3e690bc0-7eee-11eb-346e-4573f4f5fbd0
# ╠═ffd7b6b0-7ef0-11eb-2bdd-67ef92238d66
# ╠═69d6e370-7ef5-11eb-3a2b-a7802a5adc8b
# ╠═8d46e6ce-7f99-11eb-1cb4-3358ca6564b5
# ╟─2e692000-7fbd-11eb-0778-d319c4e81810
# ╠═1f485320-7eeb-11eb-2088-1d5554d6d065
# ╠═fbfe7840-7fad-11eb-3160-c994a748ae2a
# ╠═45191f7e-7fb3-11eb-1a83-49475fe38f82
# ╟─881ecd30-7f85-11eb-3d93-55b1a6dd7039
# ╟─e77cd580-80eb-11eb-2686-016c6fdd8bf1
# ╠═fa0e3580-8164-11eb-05da-d10765d23a9a
# ╠═d233fcf0-813e-11eb-0a37-e54e39a36073
# ╠═43811d70-813f-11eb-3614-1315573f2d76
# ╠═d0eb8520-8143-11eb-1f1b-27c008fd716d
# ╠═7f4adfc0-85aa-11eb-288e-fdf2569ed30b
# ╠═44603d30-886e-11eb-1313-4d8adc9702da
# ╠═d89eb340-8153-11eb-1341-6518040a962d
# ╠═317c8920-813f-11eb-2048-f1ff2bafeab5
# ╠═5a916b00-80a9-11eb-2cc6-93f42781e1b6
# ╠═c73aafc0-8287-11eb-1a3e-2de3296a35dc
# ╠═114b56c0-8240-11eb-15bc-dd322c881361
# ╠═6929cfb0-82c8-11eb-3857-8df1ea9a3a88
# ╠═4faadd40-82c8-11eb-2d7e-f7e533a7e495
# ╠═f593d63e-823b-11eb-2f6b-a91be5d313bf
# ╠═ea7a2ed0-8600-11eb-2497-bb23e393d273
# ╠═a59e1620-828e-11eb-2a19-15b99805ac4d
# ╠═ae503700-88db-11eb-2c85-5574fe9aeca5


text:
include("../roblib.jl")

function find_entrance(r)
    n = 0
    side = Right
    while isborder(r, Up)
        n += 1
        movements!(r, side, n)
        side = inverse(side)
    end
end


text:
# sample.jl
println(ARGS[1])
println(ARGS[2])