text:
# TODO:
# - remove after from get (nextind with state and i)
# - (Feedback appreciated: Would is be more efficient change the `iterate_state` internal API for the first match to arity 4?)
# - Base.get(parser, sequence, till, after, i, state) to
#   Base.get(parser, sequence, i, after, till, state)
"""
A package for combining parsers and transforming strings into julia types.

Compose parsers with the functional [parser combinator paradigm](https://en.wikipedia.org/wiki/Parser_combinator),
utilize Julia's type inferrence for transformations,
log conveniently for debugging, and let Julia compile your parser for good performance.
"""
module CombinedParsers
using Nullables
using AutoHashEquals
import Base: ==, hash
import Base: lowercase
import Base: cat, get

import TextParse
import TextParse: AbstractToken

include("ind.jl")

using LazyStrings
import LazyStrings: reversed, reverse_index

using AbstractTrees
import AbstractTrees: children
import AbstractTrees: print_tree, printnode

export CombinedParser
export result_type

"Julia types that provide CombinedParser methods result_type, state_type, iterate_state, get, nextind, prevind."
## Pair{<:Union{AbstractToken, AbstractString, Char, Regex, Pair},<:Any} }
export parser
import Base: convert

"""
    CombinedParser{S,T} <: AbstractToken{T}

Abstract parser type for parsers returning matches transformed to `::T` and
state::`S`.
"""
abstract type CombinedParser{S,T} <: AbstractToken{T} end

"""
    (x::CombinedParser)(str;kw...)

`parse(x,str;kw...)`

See also [`parse`](@ref).
"""
(x::CombinedParser)(str;kw...) = parse(x,str;kw...)
(x::CombinedParser)(prefix,str;kw...) = parse(Sequence(2,prefix,x),str;kw...)
(x::CombinedParser)(f::Function,a...;kw...) = map(f,x,a...;kw...)

"""
    result_type(x::CombinedParser)

returns the result type of a parser.

The result type is a CombinedParser type parameter.
Most of the time it is type-inferred within constructors
by [`infer_result_type`](@ref).
"""
result_type(x::CombinedParser) = result_type(typeof(x))
result_type(::Type{<:CombinedParser{<:Any,T}}) where T = T

"""
    CombinedParsers.state_type(x::CombinedParser{S}) where S

Return `S`, the state type of `x`
"""
@inline state_type(::Type{<:CombinedParser{S}}) where {S} = S
@inline state_type(x::CombinedParser) = state_type(typeof(x))

include("state.jl")

export regex_string

"""
    regex_string(x::CombinedParser)

`regex_prefix(x)*regex_inner(x)*regex_suffix(x)`
"""
regex_string(x::CombinedParser) = regex_prefix(x)*regex_inner(x)*regex_suffix(x)
regex_prefix(x::CombinedParser) = ""
regex_suffix(x::CombinedParser) = ""
regex_inner(x::CombinedParser) = ""

if VERSION>=v"1.6"
    constructor_name(x) = typeof(x).name.name
else
    constructor_name(x) = typeof(x).name.name
end

"""
    print_constructor(io::IO,x)

Print constructor pipeline in parser tree node.
"""
print_constructor(io::IO,x) =
    if x isa CombinedParser
        print(io, constructor_name(x))
    else
    end

export iterate_state

"""
    iterate_state(parser, sequence[, till::Int=lastindex(sequence)[, posi::Int=firstindex(sequence)[, next_i=posi[, state=nothing]]]])

Return position `after` next match of `parser` in `sequence` at `posi`.
The next match is following current match `state` (first match iif `state==nothing`).

If no next match is found, return `nothing`.

!!! note
    `next_i` is the index in `sequence` after `parser` match at `posi` with `state`.

    - `leftof(sequence,next_i,parser,state)==posi`, the start of the `state`-matching subsequence.
    - `rightof(sequence,posi,parser,state)==next_i`, the position after the `state`-matching subsequence.
    - `sequence[leftof(sequence,next_i,parser,state):_prevind(sequence,next_i)]` is the matched subsequence.

!!! note
    Writing a custom `iterate_state` implementations *must* return
    - `nothing` if no match is found
    - `Tuple{Int64,state_type(parser)}` with next position, match state if a match is found.

"""
@inline iterate_state(parser::CombinedParser, sequence, till=lastindex(sequence), posi=firstindex(sequence)) =
    iterate_state(parser, sequence,till,posi,posi,nothing)

"""
    WrappedParser{P,S,T}

Abstract type for parser wrappers, providing default methods."
"""
abstract type WrappedParser{P,S,T} <: CombinedParser{S,T} end
children(x::WrappedParser) = children(x.parser)
children_char = '\U1F5C4'
function print_constructor(io::IO,x::WrappedParser)
    print_constructor(io, x.parser)
    print(io, " |> ", constructor_name(x))
end
regex_prefix(x::WrappedParser) = regex_prefix(x.parser)
regex_suffix(x::WrappedParser) = regex_suffix(x.parser)
regex_inner(x::WrappedParser) = regex_inner(x.parser)

"""
    _leftof(str,i,parser::WrappedParser,x)

Convienience function for overriding [`leftof`](@ref) that guarantees that not `x isa Nothing` (returning `i`).
"""
@inline _leftof(str,i,parser::WrappedParser,x) = _leftof(str,i,parser.parser,x)

"""
    _rightof(str,i,parser::WrappedParser,x)

Convienience function for overriding [`rightof`](@ref) that guarantees that not `x isa Nothing` (returning `i`).
"""
@inline _rightof(str,i,parser::WrappedParser,x) = _rightof(str,i,parser.parser,x)

@inline _leftof(str,i,parser::WrappedParser,x::NCodeunitsState) = i-x.nc
@inline _rightof(str,i,parser::WrappedParser,x::NCodeunitsState) = i+x.nc

@inline iterate_state(parser::WrappedParser, sequence, till, posi, after, state) =
    iterate_state(parser.parser, sequence, till, posi, after, state)

export FilterParser
"""
A parser succeeds ony if
1. the wrapped `parser` succeeds
2. and a predicate function `state_filter(sequence, till, posi, r...)` returns `true` the `after,state = r` tuple.
"""
struct FilterParser{P,S,F,T} <: WrappedParser{P,S,T}
    parser::P
    state_filter::F
    FilterParser(f::Function,parser_) =
        let p = parser(parser_)
            new{typeof(p),state_type(p),typeof(f),result_type(p)}(p,f)
        end
end
Base.filter(f::Function, x::Union{TextParse.AbstractToken,CombinedParser}) =
    FilterParser(f,parser(x))

export filter_result
filter_result(f::Function, x) =
    filter(parser(x)) do sequence,till,posi,after,state
        f(get(parser(x),sequence,till,posi,after,state))
    end

@inline function iterate_state(parser::FilterParser, sequence, till, posi, next_i, state)
    r::Union{Nothing,Tuple{Int,state_type(parser.parser)}} = nothing
    while r === nothing
        r = iterate_state(parser.parser, sequence, till, posi, next_i, state)
        if r === nothing
            return nothing
        elseif !parser.state_filter(sequence, till, posi, r...)
            next_i,state=r
            r = nothing
        end
    end
    r
end

"""
    LeafParser{T} <: CombinedParser{T}

Abstract parser type for parsers that have no sub-parser (e.g. [`ConstantParser`](@ref)).
Used for dispatch in [`deepmap_parser`](@ref).
"""
abstract type LeafParser{S,T} <: CombinedParser{S,T} end

# for convenience
iterate_state(parser::LeafParser, sequence, till, posi, next_i, state::MatchState)  = nothing

"""
    NIndexParser{N,T} <: LeafParser{MatchState,T}

Abstract type for stepping `N` indices with [`_leftof`](@ref) and [`_rightof`](@ref),
accounting for `Base.ncodeunits` length of unicode chars.

See [`Bytes`](@ref) and [`ValueMatcher`](@ref).
"""
abstract type NIndexParser{N,T} <: LeafParser{MatchState,T} end
@inline _leftof(str,i,parser::NIndexParser{0},state) = i
@inline _rightof(str,i,parser::NIndexParser{0},state) = i
@inline _leftof(str,i,parser::NIndexParser{L},state) where L =
    _prevind(str,i,L)
@inline _rightof(str,i,parser::NIndexParser{L},state) where L =
    _nextind(str,i,L)

@inline function iterate_state(parser::NIndexParser, sequence, till, posi, next_i, state::Nothing)
    posi > till && return nothing # prevents BoundsError
    ni = rightof(sequence,posi,parser,MatchState())
    if ni <= till+1
        (ni, MatchState())
    else
        nothing
    end
end

export Bytes
"""
    Bytes{N,T} <: NIndexParser{N,T}

Fast parsing of a fixed number `N` of indices,
`reinterpret(T,match)[1]` the parsed vector as `T`, if `isbitstype`, or `T(match)` constructor otherwise.

Provide `Base.get(parser::Bytes{N,T}, sequence, till, after, i, state) where {N,T}` for custom conversion.

!!! note

    Endianness can be achieved by just mapping `bswap`
    ```jldoctest
    julia> map(bswap, Bytes(2,UInt16))([0x16,0x11])
    0x1611

    julia> Bytes(2,UInt16)([0x16,0x11])
    0x1116
    ```

"""
struct Bytes{N,T} <: NIndexParser{N,T} end

"""
    Bytes(N::Integer, T::Type=Vector{UInt8})

If available before end of sequence, parse `N` bytes successfully with `result_type` `T`, fail otherwise.
"""
Bytes(N::Integer, T::Type=Vector{UInt8}) = Bytes{N,T}()

@deprecate Bytes{T}(N::Integer) where T Bytes(N,T)

include("parser.jl")
include("textparse.jl")
include("constant.jl")
include("valuematcher.jl")
include("assertions.jl")

@auto_hash_equals struct PartialMatchException{S,P} <: Exception
    index::Int
    str::S
    delta::Int
    pattern::P
    PartialMatchException(i,str::S,p::P) where {S<:AbstractString,P} =
        new{S,P}(i,str,200,p)
    PartialMatchException(i,str::S,p::P) where {S,P} =
        new{S,P}(i,str,6,p)
end
export context
context(x::PartialMatchException) =
    x.str[min(x.index,end):min(end, _nextind(x.str,x.index,x.delta))]
import Base: showerror
function Base.showerror(io::IO, x::PartialMatchException)
    println(io, "parsing stopped at postion $(x.index) in:")
    println(io, "$(x.str)")
    println(io, "."^(x.index-1),"^")
    ##println(io, x.pattern)
end

@auto_hash_equals struct SideeffectParser{P,S,T,A} <: WrappedParser{P,S,T}
    parser::P
    args::A
    effect::Function
    SideeffectParser(f::Function, p::CombinedParser,a...) =
        new{typeof(p),state_type(p),result_type(p),typeof(a)}(p,a,f)
end
children(x::SideeffectParser) = children(x.parser)
function print_constructor(io::IO,x::SideeffectParser)
    print_constructor(io,x.parser)
    c = if x.effect == log_effect
        "with_log(;nomatch=true)"
    elseif x.effect == log_effect_match
        "with_log"
    else
        "with_effect($(x.effect))"
    end
    print(io," |> $c")
end
regex_string(x::SideeffectParser) = regex_string(x.parser)

export with_log, with_effect
"""
    with_effect(f::Function,p,a...)

Call `f(sequence,before_i,after_i,state,a...)` if `p` matches,
 `f(sequence,before_i,before_i,nothing,a...)` otherwise.
"""
with_effect(f::Function,p,a...) =
    SideeffectParser(f,p,a...)

@inline function iterate_state(parser::SideeffectParser, sequence, till, posi, next_i, state)
    r = iterate_state(parser.parser, sequence, till, posi, next_i, state)
    if r!==nothing
        parser.effect(sequence,posi,r...,parser.args...)
    else
        parser.effect(sequence,posi,posi,nothing,parser.args...)
    end
    r
end

"""
    Base.escape_string(x::AbstractVector)

for printing a non-string sequence when parsing.
!!! note
    type piracy? module local `_escape_string`?
"""
Base.escape_string(x::AbstractVector) = "["*join(repr.(x),",")*"]"

"""
    with_log(s::AbstractString,p, delta=5;nomatch=false)

Log matching process of parser `p`, displaying `delta` characters left of and right of match.

If `nomatch==true`, also log when parser does not match.

See also: [`log_names`](@ref), [`with_effect`](@ref)
"""
with_log(s::AbstractString,p_, delta_char::Integer=5;nomatch=false) =
    let p = parser(p_), log=s
        SideeffectParser(nomatch ? log_effect : log_effect_match ,p, log, delta_char)
    end

function log_effect(s,start,after,state,log,delta)
    at = "@$(start)-$(after)"
    if state === nothing
        printstyled("no match ", color=:underline)
    else
        print("   ")
        printstyled("match";
                    bold=false,color=:underline)
        print(" ")
    end
    printstyled(log,color=:green, bold=false)
    print(at,": ")
    firsti = _prevind(s,start,delta)
    lasti = (_prevind(s,start))
    before, matched = if _prevind(s,start)<start
        escape_string(s[max(1,firsti):lasti]), escape_string(s[start:_prevind(s,after)])
    else
        "",""
    end
    if lastindex(matched)>100
        matched=matched[1:_nextind(matched,1,20)]*"[...]"*matched[_prevind(matched,end,20):end]
    end
    printstyled(before; bold=true)
    printstyled(matched; bold=true,color=:underline)
    li = after>lastindex(s) ? lastindex(s) : _nextind(s,after,delta)
    if state === nothing
        printstyled(escape_string(s[after:min(end,li)]),
                    bold=true,color=:underline)
    elseif after<=lastindex(s)
        printstyled(escape_string(s[after:min(end,li)]),
                    color=:darkgray)
    end
    println()
    if !get(stdout,:color,false)
        print(" "^(11+length(at)+length(log)+length(before)),"^")
        if length(matched)>1
            print("_"^(length(matched)-2),"^")
        end
        println()
    end
end

function log_effect_match(s,start,after,state,log,delta)
    if state!==nothing && start!=after
        log_effect(s,start,after,state,log,delta)
    end
end

export NamedParser, with_name
"""
    NamedParser{P,S,T} <: WrappedParser{P,S,T}

if doc!="", printing will print the node with this label, and hides constructors.
Struct with
```julia
    name::Symbol
    parser::P
    doc::String
```
"""
@auto_hash_equals struct NamedParser{P,S,T} <: WrappedParser{P,S,T}
    name::Symbol
    parser::P
    doc::String ## rename -> label
    NamedParser(name::Symbol,p_,doc="") =
        let p=parser(p_)
            new{typeof(p),state_type(p),result_type(p)}(name,p,doc)
        end
end
function print_constructor(io::IO,x::NamedParser)
    if x.doc==""
        print_constructor(io,x.parser)
        print(io, " |> ")
    end
    print(io, "with_name(:")
    printstyled(io, x.name, bold=true,color=:red)
    print(io, ")")
end

children(x::NamedParser)     = x.doc=="" ? children(x.parser)     : tuple()
regex_prefix(x::NamedParser) = x.doc=="" ? regex_prefix(x.parser) : ""
regex_inner(x::NamedParser)  = x.doc=="" ? regex_inner(x.parser)  : x.doc
regex_suffix(x::NamedParser) = x.doc=="" ? regex_suffix(x.parser) : ""

"""
    with_name(name::Symbol,x; doc="")

A parser labelled with `name`.
Labels are useful in printing and logging.

See also: [`@with_names`](@ref), [`with_name`](@ref), [`log_names`](@ref)
"""
with_name(name::Symbol, x, doc="") =
    NamedParser(name,parser(x),doc)

with_name(name::AbstractString,x, doc="") =
    name=="" && doc=="" ? x : NamedParser(Symbol(name),parser(x),doc)

export @with_names
with_names(x) = x
function with_names(node::Expr)
    if node.head == :(=) && length(node.args) == 2 && isa(node.args[1], Symbol)
        node.args[2] = Expr(:call, :with_name, QuoteNode(node.args[1]), node.args[2])
    end
    if node.head != :call
        node.args = map(with_names, node.args)
    end
    node
end

"""
    @with_names

Sets names of parsers within begin/end block to match the variables they are asigned to.

so, for example
```jldoctest
julia> @with_names foo = AnyChar()
. AnyValue |> with_name(:foo)
::Char

julia> parse(log_names(foo),"ab")
   match foo@1-2: ab
                  ^
'a': ASCII/Unicode U+0061 (category Ll: Letter, lowercase)
```

See also [`log_names`](@ref) and [`@syntax`](@ref).
"""
macro with_names(block)
    esc(with_names(block))
end

export @seq
"""
    @seq(x...)

Create a sequence interleaved with whitespace (horizontal or vertical).
The result_type is omitting whitespace.
"""
macro seq(x...)
    r = if length(x)==1
        x
    else
        quote
            x_ = [$(x...)]
            sSequence( (i < lastindex(x_) ? (e*CombinedParsers.Regexp.whitespace_newline)[1] : e for (i,e) in enumerate(x_))...)
        end
    end
    esc(r)
end

export @syntax
"""
    @syntax name = expr
Convenience macro defining a CombinedParser `name=expr` and custom parsing macro `@name_str`.

```@meta
DocTestFilters = r"map\\(.+\\)"
```

```jldoctest
julia> @syntax a = AnyChar();

julia> a"char"
'c': ASCII/Unicode U+0063 (category Ll: Letter, lowercase)

```

    @syntax for name in either; expr; end
Parser `expr` is [`pushfirst!`](@ref) to `either`.
If `either` is undefined, it will be created.
If `either == :text || either == Symbol(:)` the parser will be added to `CombinedParser_globals` variable in your module.

```jldoctest
julia> @syntax street_address = Either(Any[]);

julia> @syntax for german_street_address in street_address
            Sequence(!!Repeat(AnyChar()),
                     " ",
                     TextParse.Numeric(Int)) do v
                (street = v[1], no=v[3])
            end
       end
🗄 Sequence |> map(#50) |> with_name(:german_street_address)
├─ .* AnyValue |> Repeat |> ! |> map(intern)
├─ \\
└─ <Int64>
::NamedTuple{(:street, :no), Tuple{String, Int64}}

julia> german_street_address"Some Avenue 42"
(street = "Some Avenue", no = 42)

julia> @syntax for us_street_address in street_address
            Sequence(TextParse.Numeric(Int),
                     " ",
                     !!Repeat(AnyChar())) do v
                (street = v[3], no=v[1])
            end
       end
🗄 Sequence |> map(#52) |> with_name(:us_street_address)
├─ <Int64>
├─ \\
└─ .* AnyValue |> Repeat |> ! |> map(intern)
::NamedTuple{(:street, :no), Tuple{String, Int64}}

julia> street_address"50 Oakland Ave"
(street = "Oakland Ave", no = 50)

julia> street_address"Oakland Ave 50"
(street = "Oakland Ave", no = 50)
```
"""
macro syntax(block)
    R = if block.head == :for
        name, within = block.args[1].args
        within_expr = if within === :texts || within === Symbol(":") ## parser is global
            quote
                if isdefined($__module__,:CombinedParser_globals)
                    CombinedParser_globals
                else
                    global CombinedParser_globals
                    CombinedParser_globals = Repeat(Either{Any}())
                end
            end
        elseif __module__.eval( :(isdefined($__module__,$(QuoteNode(within))) && $within isa CombinedParser ))
            :($within)
        else ## new Either
            quote
                @syntax $within = Either{Any}()
            end
        end
        body = block.args[2]
        if body.head==:block
            expr = Any[]
            for e in body.args
                if e isa LineNumberNode
                    push!(expr,e)
                elseif e isa Symbol
                    push!(expr,e)
                elseif e.head==Symbol("=") && e.args[1]==:examples
                    @warn "examples currently ignored"
                else
                    push!(expr,with_names(Expr(Symbol("="), name, e)))
                end
            end
            quote
                macro $(Symbol(string(name)*"_str"))(x)
                    $name(x)
                end
                global $name = begin
                    $(expr...)
                end
                pushfirst!($within_expr, $name)
                $name
            end
        else
            dump(block)
            error()
        end
    elseif block.head==Symbol("=")
        name = block.args[1]
        quote
            macro $(Symbol(string(name)*"_str"))(x)
                $name(x)
            end
            $(with_names(block))
        end
    elseif block.head == :block
        with_names(block)
    else
        dump(block)
        error()
    end
    esc(R)
end

import Base: in

export Repeat_stop, Repeat_until
"""
    Repeat_stop(p,stop)
    Repeat_stop(p,stop; min=0, max=Repeat_max)

Repeat `p` until `stop` (`NegativeLookahead`), not matching `stop`.
Sets cursor **before** `stop`. Tries `min:max` times
Returns results of `p`.

```jldoctest
julia> p = Repeat_stop(AnyChar(),'b') * AnyChar()
🗄 Sequence
├─ 🗄* Sequence[2] |> Repeat
│  ├─ (?!b) NegativeLookahead
│  └─ . AnyValue
└─ . AnyValue
::Tuple{Vector{Char}, Char}

julia> parse(p,"acbX")
(['a', 'c'], 'b')
```

See also [`NegativeLookahead`](@ref)
"""
Repeat_stop(p,stop; min=0, max=Repeat_max) =
    Repeat(map(IndexAt(2),Sequence(NegativeLookahead(parser(stop)),parser(p)));min=min,max=max)

@deprecate rep_stop(a...;kw...) Repeat_stop(a...;kw...)

"""
    Repeat_until(p,until, with_until=false; wrap=identity, min=0, max=Repeat_max)

Repeat `p` until `stop` (with [`Repeat_stop`](@ref)).
and set point **after** `stop`.

Return a `Vector{result_type(p)}` if `wrap_until==false`, otherwise a `Tuple{Vector{result_type(p)},result_type(until)}`.

To transform the `Repeat_stop(p)` parser head, provide a function(::Vector{result_type(p)}) in `wrap` keyword argument, e.g.
```jldoctest
julia> p = Repeat_until(AnyChar(),'b') * AnyChar()
🗄 Sequence
├─ 🗄 Sequence[1]
│  ├─ (?>🗄*) Sequence[2] |> Repeat |> Atomic
│  │  ├─ (?!b) NegativeLookahead
│  │  └─ . AnyValue
│  └─ b
└─ . AnyValue
::Tuple{Vector{Char}, Char}

julia> parse(p,"acbX")
(['a', 'c'], 'X')

julia> parse(Repeat_until(AnyChar(),'b';wrap=MatchedSubSequence),"acbX")
"ac"
```

See also [`NegativeLookahead`](@ref)
"""
Repeat_until(p,until, with_until=false;wrap=identity,min=0,max=Repeat_max) =
    if with_until
        Sequence(map(wrap,Atomic(Repeat_stop(p,until;min=min,max=max))), until)
    else
        map(IndexAt(1),Sequence(map(wrap,Atomic(Repeat_stop(p,until;min=min,max=max))), until))
    end

@deprecate rep_until(p,until) Repeat_until(p,until)

export FlatMap,after
"""
    FlatMap{P,S,Q<:Function,T} <: CombinedParser{S,T}

Like Scala's [fastparse FlatMap](https://www.lihaoyi.com/fastparse/#FlatMap).
See [`after`](@ref)
"""
@auto_hash_equals struct FlatMap{P,S,Q<:Function,T} <: CombinedParser{S,T}
    left::P
    right::Q
    function FlatMap{T}(right::Q, left::P) where {T, P<:CombinedParser, Q<:Function}
        new{P,Tuple{<:Any,<:Any,<:Any},Q,T}(left, right)
    end
end
flatmap_state(old,ls,rp,rs) = tuple_pos(rs), (ls,rp,tuple_state(rs))
left_state(state::Tuple) = state[1]
right_parser(state::Tuple) = state[2]
right_state(state::Tuple) = state[3]

children(x::FlatMap) = ( x.left, x.right )
function print_constructor(io::IO,x::FlatMap)
    print(io, "FlatMap" )
end
FlatMap(right::Function, left, T::Type=Any) = FlatMap{T}(right,parser(left))
FlatMap(right::Function, T::Type, left) = FlatMap{T}(right,parser(left))

"""
    after(right::Function,left::AbstractToken)
    after(right::Function,left::AbstractToken,T::Type)

Like Scala's fastparse [`FlatMap`](@ref)

```jldoctest
julia> saying(v) = v == "same" ? v : "different";

julia> p = after(saying, String, "same"|"but")
🗄 FlatMap
├─ |🗄 Either
│  ├─ same
│  └─ but
└─ saying
::String

julia> p("samesame")
"same"

julia> p("butdifferent")
"different"

```
"""
after(a...) = FlatMap(a...)

regex_inner(x::FlatMap)  = error("regex determined at runtime!")

@inline _rightof(str,i,parser::FlatMap,x::Tuple) =
    let li = rightof(str,i,parser.left,tuple_pos(x))
        rightof(str,li,x[2],x[3])
    end

@inline _leftof(str,i,parser::FlatMap,x::Tuple) =
    let li = leftof(str,i,x[2],x[3])
        leftof(str,li,parser.left,tuple_pos(x))
    end

function iterate_state(tokf::FlatMap, str, till, posi, next_i, state::Nothing)
    posi = next_i
    lr = iterate_state(tokf.left, str, till, posi, next_i, nothing)
    lr === nothing && return nothing
    next_i_ = tuple_pos(lr)
    rightp = parser(tokf.right(get(tokf.left, str, till, next_i_,next_i,tuple_state(lr))))
    rr = nothing
    while rr === nothing
        rr = iterate_state(rightp, str, till, next_i_, next_i_, nothing)
        if rr === nothing
            lr = iterate_state(tokf.left, str, till, posi, next_i_, tuple_state(lr))
            lr === nothing && return nothing
            next_i_ = tuple_pos(lr)
            rightp = parser(tokf.right(get(tokf.left, str, till, next_i_,posi,tuple_state(lr))))
        else
            return flatmap_state(nothing,tuple_state(lr), rightp, rr)
        end
    end
    nothing
end

function iterate_state(tokf::FlatMap, str, till, posi, next_i, state)
    lstate,rightp,rstate = left_state(state), right_parser(state), right_state(state)

    next_i_=next_i
    posi_ = leftof(str,next_i_,rightp,rstate)
    rr = nothing
    while rr === nothing
        rr = iterate_state(rightp, str, till, posi_, next_i_, rstate)
        if rr === nothing
            lr = iterate_state(tokf.left, str, till, posi, next_i_, lstate)
            lr === nothing && return nothing
            next_i_,lstate = lr
            rightp = parser(tokf.right(get(tokf.left, str, till, next_i_,posi,lstate)))
            rstate = nothing
        else
            return flatmap_state(state,lstate, rightp, rr)
        end
    end
end

export ParserPair
"""
    Sequence{P,S,T}

of `parts::P`, [`sequence_state_type`](@ref)==S and [`sequence_result_type`](@ref).
"""
@auto_hash_equals struct ParserPair{P,Q,S,T} <: CombinedParser{S,T}
    first::P
    second::Q
    ParserPair(first::CombinedParser, second::CombinedParser) =
        new{typeof(first),typeof(second),Tuple{first,second},sequence_result_type(typeof((first,second)))}(p)
end

export Sequence
"""
    Sequence{P,S,T}

of `parts::P`, [`sequence_state_type`](@ref)`==S` with [`sequence_result_type`](@ref)`==T`.

    Sequence(parts::CombinedParser...; tuplestate=true)

of `parts`, [`sequence_state_type`](@ref)`(p; tuplestate=tuplestate)` with [`sequence_result_type`](@ref).

Sequences can alternatively created with [`*`](@ref)
```jldoctest
julia> german_street_address = !Repeat(AnyChar()) * ' ' * TextParse.Numeric(Int)
🗄 Sequence
├─ .* AnyValue |> Repeat |> !
├─ \\
└─ <Int64>
::Tuple{SubString{String}, Char, Int64}

julia> german_street_address("Some Avenue 42")
("Some Avenue", ' ', 42)
```
Indexing (transformation) can be defined with
```jldoctest
julia> e1 = Sequence(!Repeat(AnyChar()), ' ',TextParse.Numeric(Int))[1]
🗄 Sequence[1]
├─ .* AnyValue |> Repeat |> !
├─ \\
└─ <Int64>
::SubString{String}

julia> e1("Some Avenue 42")
"Some Avenue"
```

!!! note
    State is managed as [`sequence_state_type`](@ref)`(parts; tuplestate)`.
    Overwrite to optimize state types special cases.
"""
@auto_hash_equals struct Sequence{P,S,T} <: CombinedParser{S,T}
    parts::P
    function Sequence(p::CombinedParser...; tuplestate=true)
        if VERSION>=v"1.6" && length(p)>4
            Sequence(Sequence(p[1:2]...; tuplestate=tuplestate),
                     Sequence(p[3:end]...; tuplestate=tuplestate);
                     tuplestate=tuplestate) do v
                         tuple(v[1]..., v[2]...)
                     end
        else
            new{typeof(p),sequence_state_type(p; tuplestate=tuplestate),sequence_result_type(typeof.(p)...)}(p)
        end
    end
end
print_constructor(io::IO,x::Sequence) = print(io,"Sequence")
children(x::Sequence) = isliteralsequence(x) ? tuple() : x.parts
regex_inner(x::Sequence)  = join([ regex_string(p) for p in x.parts])

isliteralsequence(c::ConstantParser) = true
isliteralsequence(c) = false
function isliteralsequence(c::Sequence)
    (&)(isliteralsequence.(c.parts)...)
end

sequence_state_type(x; kw...) = sequence_state_type(typeof(x); kw...)

"""
    sequence_state_type(pts::Type; tuplestate=true)

- `MatchState` if all `fieldtypes` are `MatchState`,
- otherwise if `tuplestate`, a tuple type with the `state_type` of `parts`,
- or `Vector{Any}` if `!tuplestate`.

!!! note
    Todo: NCodeunitsState instead of MatchState might increase performance.
"""
function sequence_state_type(pts::Type; tuplestate=true)
    if isempty(fieldtypes(pts)) || all(t->state_type(t)<:MatchState, fieldtypes(pts))
        MatchState
    elseif tuplestate
        Tuple{(state_type(p) for p in fieldtypes(pts))...}
    else
        Vector{Any}
    end
end

"""
    sequence_result_type(::Type{T}) where {T<:Tuple}

`Tuple` type, internally used for `Sequence` result_type.
"""
sequence_result_type(T::Type{<:CombinedParser}...) =
    Tuple{ (result_type(t) for t in T)... }

@deprecate Sequence(p::Vector; kw...) Sequence(p...; kw...)

"""
    Sequence(parts...; kw...)

Parts that are not `::CombinedParser` are converted with [`parser`](@ref).
```jldoctest
julia> german_street_address = Sequence(!Repeat(AnyChar()), ' ', TextParse.Numeric(Int))
🗄 Sequence
├─ .* AnyValue |> Repeat |> !
├─ \\
└─ <Int64>
::Tuple{SubString{String}, Char, Int64}

julia> german_street_address("Some Avenue 42")
("Some Avenue", ' ', 42)
```

!!! note
    Returns a NamedTuple [`Base.map`](@ref) transformation if any part was `Pair{Symbol}`.

    ```jldoctest
    julia> german_street_address =  Sequence(:street => !Repeat(AnyChar()), " ", :no => TextParse.Numeric(Int))
    🗄 Sequence |> map(ntuple)
    ├─ .* AnyValue |> Repeat |> ! |> with_name(:street)
    ├─ \\
    └─  <Int64> |> with_name(:no)
    ::NamedTuple{(:street, :no), Tuple{SubString{String}, Int64}}

    julia> german_street_address("Some Avenue 42")
    (street = "Some Avenue", no = 42)
    ```
"""
function Sequence(p...; kw...)
    s = Sequence(( parser(x) for x = p )...; kw...)
    T = fieldtypes(result_type(s))
    names = ( t.first=>i
              for (i,t) in enumerate(p)
              if t isa Pair{Symbol} )
    isempty(names) && return s
    NT= NamedTuple{ tuple( (n.first for n in names)...),
                    Tuple{ (T[n.second] for n in names)... }}
    NTn = NamedTuple{ tuple( (n.first for n in names)...) }
    function ntuple(v)
        NT( tuple( (v[k.second] for k in names )... ))
    end
    map(ntuple, NT, s)
end

Base.lastindex(x::Sequence) = lastindex(x.parts)

"""
    Sequence(;kw...)

Sequence keyword argument constructors transform the parsing into a named tuple.
"""
Sequence(;tuplestate=true, kw...) =
    isempty(kw) ? Always() : Sequence(kw...; tuplestate=tuplestate)

Sequence(transform::Function, T::Type, a...; kw...) =
    map(transform, T, Sequence(a...; kw...))

Sequence(transform::Function, a...; kw...) =
    map(transform, Sequence(a...; kw...))

Sequence(transform::Integer,tokens...; kw...) =
    Sequence(Val{transform}(),parser.(tokens)...; kw...)

function Sequence(::Val{transform},tokens...; kw...) where {transform}
    s = Sequence(tokens...)
    map(v -> v[transform], fieldtype(result_type(s),transform), s; kw...)
    # map(IndexAt(transform), s)
end

Base.getindex(x::CombinedParser, i) = map(IndexAt(i),x)

_sSequence(x::Sequence) = _sSequence(x.parts...)
_sSequence(x::Always) = tuple()
_sSequence() = tuple()
_sSequence(x1) = tuple(parser(x1))
_sSequence(x1,x...) =
    Iterators.flatten(tuple( _sSequence(x1), collect(Iterators.flatten( ( _sSequence(e) for e in x ) ))))

export sSequence
"""
    sSequence(x...)

Simplifying `Sequence`, flatten `Sequence`s, remove `Always` assertions.

```jldoctest
julia> Sequence('a',CharIn("AB")*'b')
🗄 Sequence
├─ a
└─ 🗄 Sequence
   ├─ [AB] ValueIn
   └─ b
::Tuple{Char, Tuple{Char, Char}}

julia> sSequence('a',CharIn("AB")*'b')
🗄 Sequence
├─ a
├─ [AB] ValueIn
└─ b
::Tuple{Char, Char, Char}
```
See also [`Sequence`](@ref)

!!! note
    This function will be removed and replaced with a keyword argument
"""
function sSequence(x...)
    sSequence(_sSequence(parser.(x)...)...)
end

sSequence(x::CombinedParser) = x
function sSequence(x::CombinedParser...)
    Sequence(_sSequence(x...)...)
end

@inline function _leftof(str,i,parser::Sequence,x::MatchState)
    for p in length(parser.parts):-1:1
        i=leftof(str,i,parser.parts[p],x)
    end
    i
end

@inline function _leftof(str,i,parser::Sequence,x)
    for j in lastindex(x):-1:1
        (p,e) = parser.parts[j],x[j]
        i=leftof(str,i,p,e)
    end
    i
end

@inline function _rightof(str,i,parser::Sequence,x::MatchState)
    for p in parser.parts
        i=rightof(str,i,p,MatchState())
    end
    i
end

@inline function _rightof(str,i,parser::Sequence,x)
    for (p,e) in zip(parser.parts,x)
        i=rightof(str,i,p,e)
    end
    i
end

function prune_captures(sequence,after_i)
end

Base.getindex(A::MatchState, i::Int) = MatchState()
Base.setindex!(A::MatchState, ::MatchState, i::Int) = nothing
Base.setindex!(A::MatchState, v, i::Int) = error("MatchState elements can only be ::MatchState")

sequence_state(statettype::Type{MatchState}, states) = MatchState()
sequence_state(statettype::Type{<:Tuple}, states) = tuple( (s for s in states...) )
sequence_state(statettype::Type, states) = states

sequence_state(statettype::Type{MatchState}) = MatchState()
sequence_state(statettype::Type{<:Tuple}) = tuple( )
sequence_state(statettype::Type) = Any[]

function iterate_state_(parser::Sequence, sequence, till, posi, next_i, states::Nothing)
    length(parser.parts) == 0 && return next_i, sequence_state(state_type(parser))
    sss = Vector{Any}(undef,length(parser.parts))
    sss[1] = nothing
    iterate_state(parser, sequence, till, posi, next_i, sss, 1)
end

function iterate_state_(parser::Sequence, sequence, till, posi, next_i, substate::Vector{Any}, p=length(substate))
    next_i_ = next_i
    part=parser.parts
    length(part) == 0 && return nothing
    pposi = [ 0 for _ in 1:(length(substate)+1)]
    pposi[1]=posi
    if p==length(substate)
        pposi[end]=next_i
    end
    while p<=length(substate)
        if iszero(pposi[p])
            pposi[p] = leftof(sequence, pposi[p+1], part[p], @inbounds substate[p])
        end
        if (@inbounds substate[p]) === nothing
            pposi[p+1] = pposi[p]
        end
        r = iterate_state(part[p], sequence, till, pposi[p], pposi[p+1], substate[p])

        if r === nothing
            prune_captures(sequence, pposi[p])
            @inbounds substate[p] = nothing
            pposi[p+1] = pposi[p]
            p == 1 && return nothing
            p -= 1
        else
            pposi[p+1] = tuple_pos(r)
            @inbounds substate[p] = tuple_state(r)
            if p < length(substate)
                @inbounds substate[p+1]=nothing
            end
            p += 1
        end
    end
    pposi[end], sequence_state(state_type(parser), substate)
end

# unambigously
@generated function iterate_state(parser::Sequence{pts,sts}, sequence, till, posi, next_i, states::MatchState) where {pts<:Tuple,sts}
    nothing
end

@generated function iterate_state(parser::Sequence{pts,sts}, sequence, till, posi, next_i, states)::Union{Nothing,Tuple{Int,sts}} where {pts<:Tuple,sts}
    fpts = fieldtypes(pts)
    spts = Type[ Union{Nothing,state_type(t)} for t in fpts ]
    n = length(fpts)
    subsearch = Symbol[ gensym(:subsearch) for p in fpts ]
    subresult = Symbol[ gensym(:r) for p in fpts ]
    part = Symbol[ gensym(:part) for p in fpts ]
    pposi = Symbol[ gensym(:pos) for p in 1:(n+1) ]
    substate,init = if states<:Nothing
        substate = Symbol[ gensym(:s) for i in fpts ]
        substate, [
            quote
            $(substate[i])::$t = nothing
            @inbounds $(part[i])::$p = parser.parts[$i]
            $(pposi[i])::Int = 0
            end
            for (i,(p,t)) in enumerate(zip(fpts,spts))
        ]
    elseif states<:Vector
        substate = Expr[ Expr(Symbol("::"), Expr(:ref,:states,i), t) for (i,(p,t)) in enumerate(zip(fpts,spts)) ]
        ## substate = Symbol[ gensym(:s) for i in fpts ]
        substate, [
            quote
            ## @inbounds $(substate[i])::$t = states[$i]
            @inbounds $(part[i])::$p = parser.parts[$i]
            $(pposi[i])::Int = 0
            end
            for (i,(p,t)) in enumerate(zip(fpts,spts))
        ]
    elseif states<:Tuple
        substate = Symbol[ gensym(:s) for i in fpts ]
        substate, [
            quote
            @inbounds $(substate[i])::$t = states[$i]
            @inbounds $(part[i])::$p = parser.parts[$i]
            $(pposi[i])::Int = 0
            end
            for (i,(p,t)) in enumerate(zip(fpts,spts))
        ]
    else
        error("strange sequence state type")
    end

    ret_state = if state_type(parser) <: MatchState
        :(MatchState())
    elseif state_type(parser) <: Tuple
        :(tuple( $([ :(($(s))) for s in substate ]...) ) )
    elseif states <: Nothing
        :(Any[ $([ :(($(s))) for s in substate ]...) ] )
    elseif states <: Vector
        quote
            ## $( [ :(@inbounds states[$i]=$(substate[i])) for i in 1:n ]...)
            states
        end
    else
        error("invalid state_type")
    end
    parseparts = [
        quote
        @label $(subsearch[p])
        if iszero($(pposi[p]))
            $(pposi[p]) = leftof(sequence, $(pposi[p+1]), $(part[p]), @inbounds $(substate[p]))
        end
        if (@inbounds $(substate[p])) === nothing
            ## if sss[$p] === nothing
            $(pposi[p+1]) = $(pposi[p])
        end
        ## TODO: gc happening in next line?
        $(subresult[p]) = iterate_state($(part[p]), sequence, till, $(pposi[p]), $(pposi[p+1]), @inbounds $(substate[p]))
        if $(subresult[p]) === nothing
        prune_captures(sequence,$(pposi[p]))
        @inbounds $(substate[p]) = nothing
        $(pposi[p+1]) = $(pposi[p])
           @goto $(p == 1 ? :theend : subsearch[p-1])
        else
            $(pposi[p+1]) = tuple_pos($(subresult[p]))
            @inbounds $(substate[p]) = tuple_state($(subresult[p]))
        ##$(pposi[p+1]), $(substate[p]) = $(subresult[p])
            $(if p < length(fpts); (:(@inbounds $((substate[p+1]))=nothing)); end )
        end
        end
        for (p,t) in enumerate(fpts)
    ]
    R = quote
        $(init...)
        $(pposi[1]) = posi
        $(pposi[end]) = next_i
        states !== nothing && @goto $(subsearch[end])
        $(parseparts...)
        return $(pposi[end]), $ret_state
        @label theend
        return nothing
    end
    R
end

export Lazy
"""
    Lazy(x::Repeat)
    Lazy(x::Optional)

Lazy `x` repetition matching (instead of default greedy).

```jldoctest
julia> german_street_address = !Lazy(Repeat(AnyChar())) * Repeat1(' ') * TextParse.Numeric(Int)
🗄 Sequence
├─ .*? AnyValue |> Repeat |> Lazy |> !
├─ \\ +  |> Repeat
└─ <Int64>
::Tuple{SubString{String}, Vector{Char}, Int64}

julia> german_street_address("Konrad Adenauer Allee    42")
("Konrad Adenauer Allee", [' ', ' ', ' ', ' '], 42)
```

!!! note
    PCRE `@re_str`
    ```jldoctest
    julia> re"a+?"
    a+?  |> Repeat |> Lazy
    ::Vector{Char}

    julia> re"a??"
    a?? |missing |> Lazy
    ::Union{Missing, Char}
    ```
"""
@auto_hash_equals struct Lazy{P,S,T} <: WrappedParser{P,S,T}
    parser::P
    Lazy(p_) =
        let p = parser(p_)
            new{typeof(p),state_type(p),result_type(p)}(p)
        end
end

regex_inner(x::Lazy) = regex_inner(x.parser)
regex_suffix(x::Lazy) = regex_suffix(x.parser)*"?"

function print_constructor(io::IO, x::Lazy)
    print_constructor(io,x.parser)
    print(io, " |> Lazy" )
end

const Repeat_max = 10^6
export Repeat1, Repeat
"""
    Repeat(minmax::UnitRange, x...)
    Repeat(x...; min=0,max=Repeat_max)
    Repeat(min::Integer, x...)
    Repeat(min::Integer,max::Integer, x...)

Parser repeating pattern `x` `min:max` times.

```jldoctest
julia> Repeat(2,2,'a')
a{2}  |> Repeat
::Vector{Char}

julia> Repeat(3,'a')
a{3,}  |> Repeat
::Vector{Char}

```
"""
@auto_hash_equals struct Repeat{P,S,T} <: WrappedParser{P,S,T}
    range::UnitRange{Int}
    parser::P
    Repeat(range::UnitRange{Int},p::P) where {P<:CombinedParser} =
        new{P,repeat_state_type(state_type(p)),Vector{result_type(P)}}(range,p)
    # Repeat(p::P) where {P<:CombinedParser} =
    #     new{P,repeat_state_type(state_type(p)),Vector{result_type(P)}}(0:Repeat_max,p)
end
Repeat(range::UnitRange{Int},p...)                  = Repeat(range,sSequence(p...))
Repeat(min::Integer,max::Integer,p...)              = Repeat((min:max),p...)
Repeat(p...;min::Integer=0,max::Integer=Repeat_max) = Repeat((min:max),p...)
Repeat(min::Integer,p...)                           = Repeat((min:Repeat_max),p...)

@inline repeat_state_type(::Type{MatchState}) = Int
@inline repeat_state_type(T::Type) = Vector{T}

"""
    Repeat(f::Function,a...)

Abbreviation for [`Base.map`](@ref)`(f,Repeat(a...))`.
"""
Repeat(f::Union{Function,Type},a...;kw...)           = map(f,Repeat(a...;kw...))

"""
    Repeat1(x)

Parser repeating pattern `x` one time or more.
"""
Repeat1(x...; max=Repeat_max)                        = Repeat(1:Repeat_max,x...)

"""
    Repeat1(f::Function,a...)

Abbreviation for [`Base.map`](@ref)`(f,Repeat1(a...))`.
"""
Repeat1(f::Function,a...; kw...)                     = map(f,Repeat1(a...; kw...))

@deprecate Repeat(minmax::Tuple{<:Integer,<:Integer},x,y::Vararg) Repeat(minmax...,x,y...)

@deprecate Repeat(transform::Function, T::Type, a...) map(transform, T, Repeat(a...))

@deprecate Repeat(transform::Function, minmax::Tuple{<:Integer,<:Integer}, a...) map(transform, Repeat(minmax..., a...))

@deprecate rep(a...;kw...) Repeat(a...;kw...)

import Base.join

"""
    Base.join(x::Repeat,delim, infix=:skip)

Parser matching repeated `x.parser` separated by `delim`.
```jldoctest
julia> parse(join(Repeat(AnyChar()),','),"a,b,c")
3-element Vector{Char}:
 'a': ASCII/Unicode U+0061 (category Ll: Letter, lowercase)
 'b': ASCII/Unicode U+0062 (category Ll: Letter, lowercase)
 'c': ASCII/Unicode U+0063 (category Ll: Letter, lowercase)
```
```jldoctest
julia> parse(join(Repeat(AnyChar()),',';infix=:prefix),"a,b,c")
('a', [(',', 'b'), (',', 'c')])

julia> parse(join(Repeat(AnyChar()),',';infix=:suffix),"a,b,c")
([('a', ','), ('b', ',')], 'c')
```
"""
function Base.join(x::Repeat, delim_; infix=:skip)
    delim = parser(delim_)
    if infix==:prefix
        Sequence(x.parser, Repeat( Sequence( delim, x.parser ) ))
    elseif infix==:suffix
        Sequence(Repeat( Sequence( x.parser, delim ) ), x.parser)
    elseif infix==:skip
        ## todo: the get function could be optimized
        ##@show x.range
        map(x.parser * Repeat(
            max(0,x.range.start-1),
            x.range.stop == Repeat_max ? Repeat_max : x.range.stop-1,
            Sequence(2, delim,x.parser ))) do (f,r)
                pushfirst!(r,f)
                r::result_type(x)
            end
    else
        error("unknown delim=$delim, infix=$infix")
    end
end

"""
    Base.join(x::CombinedParser,delim; kw...)

Shorthand for `join(Repeat(x),delim; kw...)`.
"""
Base.join(x::Union{TextParse.AbstractToken,CombinedParser},delim; kw...) =
    join(Repeat(parser(x)),delim;kw...)

"""
    Base.join(f::Function, x::CombinedParser, delim; kw...)

Shorthand for [`Base.map`](@ref)`(f,join(x,delim; kw...))`.
"""
Base.join(f::Function,p::CombinedParser,delim_; kw...) =
    map(f,join(p,delim_; kw...))

function print_constructor(io::IO,x::Repeat)
    print_constructor(io,x.parser)
    print(io, " |> Repeat" )
end

regex_inner(x::Repeat) = regex_inner(x.parser)
regex_suffix(x::Repeat) =
    regex_suffix(x.parser)*if x.range.start == 0
        if x.range.stop >= Repeat_max
            "*"
        else
            "{,$(x.range.stop)}"
        end
    else
        if x.range.stop >= Repeat_max
            if x.range.start == 1
                "+"
            else
                "{$(x.range.start),}"
            end
        elseif x.range.start==x.range.stop
            "{$(x.range.start)}"
        else
            "{$(x.range.start),$(x.range.stop)}"
        end
    end

@inline function _leftof(str,i,parser::Repeat,x::Int)
    for e in 1:x
        i=leftof(str,i,parser.parser,MatchState())
    end
    i
end

@inline function _rightof(str,i,parser::Repeat,x::Int)
    for e in 1:x
        i=rightof(str,i,parser.parser,MatchState())
    end
    i
end

@inline function _rightof(str,i,parser::Repeat,x::Vector)
    for e in x
        i=rightof(str,i,parser.parser,e)
    end
    i
end

@inline function _leftof(str,i,parser::Repeat,x::Vector)
    for j in lastindex(x):-1:1
        @inbounds i=leftof(str,i,parser.parser,x[j])
    end
    i
end

@inline emptystate(::Type{Int}) = 0
@inline state_length(parser,state::Int) = state
@inline pushstate!(state::Int,parser,substate::MatchState) =
    state + 1

@inline poplast!(outer_state::Int) =
    if iszero(outer_state)
        nothing, 0
    else
        MatchState(), outer_state - 1
    end

@inline poplast!(outer_state,inner_parser) =
    poplast!(outer_state)

@inline state_length(parser::Repeat,x::Vector) =
    length(x)
@inline emptystate(::Type{Vector{T}}) where T =
    T[]

@inline function pushstate!(state::Vector,parser,substate)
    push!(state,substate)
end

@inline function poplast!(outer_state::Vector)
    l=pop!(outer_state)
    l,outer_state
end

## kernel function (function barrier)
@inline function fill_rep_j_state(x::Tuple{Int,S},state_,tparser) where S
    pos, state = x
    pos, pushstate!(state_,tparser, state)
end

@inline function fill_rep(t::Repeat, sequence, till::Int, i::Int,state)
    j_::Int = -1
    j::Int = i
    state_ = state
    tp = t.parser
    while state_length(t,state_) < t.range.stop && ( x = iterate_state(t.parser,sequence, till, j, j,nothing) )!==nothing
        ## @info "rep fill..." x state_
        ## e.g. match(re"(?:a|(?=b)|.)*\z","abc")
        j_=j
        ##j, state_ = fill_rep_j_state(x,state_,tp)
        j, state_ = fill_rep_j_state(x,state_,tp)
        state_length(t,state_)>t.range.start && j_==j && break
    end
    j,state_,state_length(t,state_) < t.range.start
end

## used by Repeat
function push_rep(t,sequence, till, posi, x::Nothing, state_)
    posi, state_, !iszero(state_length(t,state_))
end

## used by Repeat
function push_rep(t,sequence, till, posi, x::Tuple{Int,S}, state_) where S
    p,s = x
    if posi==p
        posi, state_, true
    else
        fill_rep(t,sequence,till,p,pushstate!(state_,t.parser,s))
    end
end

## used by Lazy{Repeat}
@inline function pushstate!_fill_rep(t_, sequence, till, state_, x)
    t = t_.parser
    state_=pushstate!(state_,t.parser,tuple_state(x))
    fill_rep(t_,sequence,till,tuple_pos(x),state_)
end

function iterate_state(t::Repeat, sequence, till, posi, next_i, state)
    next_i_::Int,outer_state::state_type(typeof(t)),goback::Bool = if state === nothing
        es = emptystate(state_type(typeof(t)))
        fill_rep(t,sequence,till,next_i, es)
    else
        if state_length(t,state)==0
            return nothing
            # https://www.pcre.org/original/doc/html/pcrepattern.html:
            # It is possible to construct infinite loops by following
            # a subpattern that can match no characters with a
            # quantifier that has no upper limit, for example:

            #   (a?)*

            # Earlier versions of Perl and PCRE used to give an error
            # at compile time for such patterns. However, because
            # there are cases where this can be useful, such patterns
            # are now accepted, but if any repetition of the
            # subpattern does in fact match no characters, the loop is
            # forcibly broken.
        #     return nothing
        end
        next_i, state, true
    end
    while goback
        if state_length(t,outer_state)==0
            return nothing
        end
        inner_state, outer_state=poplast!(outer_state,t.parser)
        posi = leftof(sequence,next_i_,t.parser,inner_state) ##state[end][1]
        prune_captures(sequence,posi)
        x = iterate_state(t.parser,sequence, till, posi, next_i_, inner_state)
        x === nothing && state_length(t,outer_state) in t.range && return posi, outer_state
        next_i_,outer_state,goback = push_rep(t,sequence, till, posi, x, outer_state)
    end
    if state_length(t,outer_state) in t.range
        next_i_, outer_state
    else
        nothing
    end
end

@inline function fill_rep(t_::Lazy{<:Repeat}, sequence, till::Int, j::Int, state_)
    t = t_.parser
    tp = t.parser
    while state_length(t,state_) < t.range.start && (x = iterate_state(t.parser,sequence, till,j, j,nothing))!==nothing
        j_=j
        j, state_ = fill_rep_j_state(x,state_,tp)
        j_==j && break
    end
    j,state_,false
end
function iterate_state(t_::Lazy{<:Repeat}, sequence, till, posi, next_i, state)
    t = t_.parser
    next_i_::Int,state_::state_type(typeof(t)),goback::Bool = if state === nothing
        es = emptystate(state_type(typeof(t)))
        fill_rep(t_,sequence,till,next_i, es)
    else
        if state_length(t,state)<t.range.stop
            x = iterate_state(t.parser,sequence, till, next_i, next_i, nothing)
            if x!==nothing && ( tuple_pos(x)>next_i || state_length(t,state)==0)
                return fill_rep_j_state(x,state,t.parser) #tuple_pos(x),pushstate!(state,t.parser,tuple_state(x))
            end
        end
        next_i, state, true
    end

    while goback
        if state_length(t,state)==0
            return nothing
        end
        lstate, state_=poplast!(state,t.parser)
        posi = leftof(sequence,next_i_,t.parser,lstate) ##state[end][1]
        x = iterate_state(t.parser,sequence, till, posi, next_i_, lstate)
        if x === nothing
            next_i_ = posi
            prune_captures(sequence,next_i_)
            if state_length(t,state_)==0
                return nothing
            end
            state = state_
        else
            next_i_,state_ = pushstate!_fill_rep(t_, sequence, till, state_, x)
            if state_length(t,state_) in t.range
                goback = false
            end
        end
    end
    if state_length(t,state_) in t.range ## && state_length(t,state_)>0
        return next_i_, state_
    else
        nothing
    end
end

"""
    defaultvalue(T::Type)

Default value if [`Optional`](@ref)<:`CombinedParser` is skipped.
- `T<:AbstractString`: `""`
- `T<:Vector{E}`: `E[]`
- `T<:CombinedParser`: `Always()`
- otherwise `missing`

!!! note
    [`get`](@ref) will return a [`CombinedParsers._copy`](@ref) of `defaultvalue`.
"""
defaultvalue(::Type{<:AbstractString}) = ""
defaultvalue(V::Type{<:Vector}) = eltype(V)[]
defaultvalue(V::Type) = missing
defaultvalue(V::Type{<:CombinedParser}) = Always()

export Optional
"""
State type for skipped optional. (Missing was breaking julia).
"""
struct NoMatch end
Base.show(io::IO, ::NoMatch) = print(io,"n/a")
"""
    Optional(parser;default=defaultvalue(result_type(parser)))

Parser that always succeeds.
If parser succeeds, return result of `parser` with curser behind match.
If parser does not succeed, return `default` with curser unchanged.

```jldoctest
julia> match(r"a?","b")
RegexMatch("")

julia> parse(Optional("a", default=42),"b")
42
```
"""
@auto_hash_equals struct Optional{P,S,T} <: WrappedParser{P,S,T}
    parser::P
    default::T
    function Optional(p::CombinedParser;default=defaultvalue(result_type(p)))
        T = result_type(p)
        D = typeof(default)
        T_ = promote_type(T,D)
        T_ === Any && ( T_ = Union{T,D} )
        new{typeof(p),Union{NoMatch,state_type(p)},T_}(p, default)
    end
end

Optional(x...;kw...) =
    Optional(sSequence(x...); kw...)

Optional(T::Type, x_; transform, kw...) =
    Optional(transform, T, x; kw...)

function Optional(transform::Function, T::Type, x;
                  default=defaultvalue(T))
    map(transform,T,Optional(x; default=default))
end

children(x::Optional) = children(x.parser)
regex_inner(x::Optional) = regex_inner(x.parser)
regex_suffix(x::Optional) = regex_suffix(x.parser)*"?"

function print_constructor(io::IO, x::Optional)
    print_constructor(io,x.parser)
    printstyled(io, "|$(x.default)",color=:blue)
    #print(io, " |> Optional(default=$(x.default))")
end

@inline _leftof(str,i,parser::Optional,x::NoMatch) = i
@inline _rightof(str,i,parser::Optional,x::NoMatch) = i

function iterate_state(t::Optional, str, till, posi, next_i, state::MatchState)
    prune_captures(str,posi)
    posi, NoMatch()
end

iterate_state(t::Optional, str, till, posi, next_i, state::NoMatch) =
    nothing

function iterate_state(t::Optional, str, till, posi, next_i, state)
    posi = state === nothing ? next_i : leftof(str,next_i,t.parser,state) ##state[end][1]
    r = iterate_state(t.parser, str, till, posi, next_i, state)
    if r === nothing
        prune_captures(str,posi)
        return tuple(posi, NoMatch())
    else
        r
    end
end

iterate_state(t::Lazy{<:Optional}, str, till, posi, next_i, state::Nothing) =
    next_i, NoMatch()
iterate_state(t::Lazy{<:Optional}, str, till, posi, next_i, state::NoMatch) =
    iterate_state(t.parser.parser, str, till, posi, next_i, nothing)
iterate_state(t::Lazy{<:Optional}, str, till, posi, next_i, state) =
    iterate_state(t.parser.parser, str, till, posi, next_i, state)

export Either
export Delayed

"""
    Either{S,T}(p) where {S,T} = new{typeof(p),S,T}(p)

Parser that tries matching the provided parsers in order, accepting the first match, and fails if all parsers fail.

This parser has no `==` and `hash` methods because it can recurse.

```jldoctest
julia> match(r"a|bc","bc")
RegexMatch("bc")

julia> parse(Either("a","bc"),"bc")
"bc"

julia> parse("a" | "bc","bc")
"bc"

```
"""
struct Either{Ps,S,T} <: CombinedParser{S,T}
    options::Ps
    Either{S,T}(p) where {S,T} = new{typeof(p),S,T}(p)
end

"""
    Base.getindex(x::Either, property::Symbol)

Return parser option with name `property` if found nested in `WrappedParser`s.
Errors otherwise.

Useful with [`substitute`](@ref) and [`CombinedParsers.BNF.bnf`](@ref).
"""
function Base.getindex(x::Either, property::Symbol)
    for p in x.options
        while p isa WrappedParser
            p isa NamedParser && p.name==property && return p
            p = p.parser
        end
    end
    error("no NamedParser $property found")
end

"""
    Either(p...; simplify=false)

Create a immutable `Either{either_state_type(p),either_result_type(p)}(::Tuple)` improved for performance.
Arguments `p...` are wrapped in [`parser`](@ref),
type parameters are computed with [`either_state_type`](@ref) and [`either_result_type`](@ref).

If `simplify`, flattens nested `Either`s and remove `Never` parsers, if only a single option remains return that option.
If you want to simplify a constructed parser, [`CombinedParsers.strip_either1`](@ref) provides more options.

```jldoctest
julia> Either('a', simplify=true)
re"a"

julia> Either('a',CharIn("AB")|"bc")
|🗄 Either
├─ a
└─ |🗄 Either
   ├─ [AB] ValueIn
   └─ bc
::Union{Char, SubString{String}}

julia> Either('a',CharIn("AB")|"bc", simplify=true)
|🗄 Either
├─ a
├─ [AB] ValueIn
└─ bc
::Union{Char, SubString{String}}
```
"""
function Either(p_...; simplify=false)
    os = either_options(p_...; simplify=simplify)
    simplify && length(os)==1 && return first(os)
    p = tuple(os...)
    Either{either_state_type(p),either_result_type(p)}(p)
end

"""
    Either(p::Vector; simplify=false)

Create a mutable `Either{Any,Any}(::Vector{Any})` for creating recursive parsers.
Arguments `p...` are wrapped in [`parser`](@ref),
type parameters are computed with [`either_state_type`](@ref) and [`either_result_type`](@ref).

See also [`@syntax`](@ref).
!!! note
    state type and result type are `Any` which might cost performance.
"""
function Either(p_::Vector; simplify=false)
    p = either_options(p_...; simplify=simplify)
    Either{Any,Any}(p)
end

"""
    Either{T}(p...; simplify=false, convert=false)

Create a mutable `Either{Any,T}(::Vector{Any})` for creating recursive parsers.
Options can be added with [`push!`](@ref) and [`pushfirst!`](@ref).

If `convert` for any option `x` in `p` that has `!(result_type(x) <: T)`, adds [`Base.map`](@ref)`(T,x)` instead.
(Provide a `convert` method!)

See also [`@syntax`](@ref).
!!! note
    state type is `Any` which might cost performance.
"""
function Either{T}(p_...; convert=false, simplify=false) where T
    p = either_options(p_...; simplify=simplify)
    for (i,x) in enumerate(p)
        if !(result_type(x) <: T)
            convert || error("transforming results with convert($T,::$(result_type(x)))\n$x")
            p[i] = map(T,x)
        end
    end
    Either{Any,T}(p)
end

@deprecate Either{T}(x::Vector; kw...) where T Either{T}(x...; kw...)
@deprecate Either{T}(x::Tuple; kw...) where T Either(x...; kw...)
@deprecate Either(x::Tuple; kw...) Either(x...; kw...)

"""
    Delayed(T::Type) =

[`Either`](@ref)`{T}()`.
"""
Delayed(T::Type) = Either{T}()

"""
    Either(transform::Function, x::Vararg)

abbreviation for [`Base.map`]`(transform, Either(x...))`.
"""
function Either(transform::Function, x...; kw...)
    map(transform, Either(x...;kw...))
end

_sEither(x::Either) = _sEither(x.options...)
_sEither(x::Never) = tuple()
_sEither() = tuple()
_sEither(x1) = tuple(parser(x1))
## todo: better aggregate in argument?
_sEither(x1,x...) = Iterators.flatten( Any[ _sEither(x1), ( _sEither(e) for e in x )... ] )

function either_options(x...; simplify = false)
    Any[if simplify
            _sEither(x...)
        else
            parser.(x)
        end...]
end
@deprecate sEither(x...) Either(x...; simplify=true)

either_state_type(ts::Type{Vector{Any}}) = Tuple{Int,Any}
either_state_type(ts::Type{<:CombinedParser}) = Tuple{Int,Any}
either_state_type(ts::Type{<:Vector}) = Tuple{Int,state_type(eltype(ts))}
either_state_type(ts::Type{<:Tuple}) = Tuple{Int,promote_type(state_type.(fieldtypes(ts))...)}
either_state_type(ts::Type...) = Tuple{Int,promote_type(state_type.(ts))}
either_state_type(x) = either_state_type(typeof(x))
@inline with_state!(x::Nothing,k::Int,s) = (k,s)
function promote_type_union(Ts...)
    T = promote_type(Ts...)
    Any <: T ? Union{Ts...} : T
end

"return tuple(state_type,result_type)"
function either_result_type(ts)
    promote_type_union(result_type.(ts)...)
end

children(x::Either) = x.options
regex_string(x::Either) = join(regex_string.(x.options),"|")
regex_prefix(x::Either) = "|"
regex_inner(x::Either) = join([ regex_string(p) for p in x.options],"|")
regex_suffix(x::Either) = ""
print_constructor(io::IO,x::Either) = print(io,"Either")

"""
    Base.push!(x::Either, option)

Push `option` to `x.options` as parser tried next if `x` fails.

Recursive parsers can be built with `push!` to `Either`.

See also [`pushfirst!`](@ref) and [`@syntax`](@ref).
"""
function Base.push!(x::Either{<:Vector,<:Any}, y_)
    y = parser(y_)
    promote_type(result_type(y),result_type(x)) <: result_type(x) || error("$(result_type(y)) <: $(result_type(x)). Fix with `push!(x|$(typeof(y)),y)`.\n$y")
    promote_type(state_type(y),state_type(x)) <: state_type(x) || error("$(state_type(y)) <: $(state_type(x)). Fix with `push!(x|$(typeof(y)),y)`.\n$y")
    push!(x.options,y)
    y
end

"""
    Base.pushfirst!(x::Either, option)

Push `option` to `x.options` as parser tried first, and trying `x` if `option` fails.

Recursive parsers can be built with `pushfirst!` to `Either`.

See also [`push!`](@ref) and [`@syntax`](@ref).
"""
function Base.pushfirst!(x::Either{<:Vector,<:Any}, y_)
    y = parser(y_)
    promote_type(result_type(y),result_type(x)) <: result_type(x) || error("$(result_type(y)) <: $(result_type(x)). Fix with `push!(x|$(typeof(y)),y)`.\n$y")
    promote_type(state_type(y),state_type(x)) <: state_type(x) || error("$(state_type(y)) <: $(state_type(x)). Fix with `push!(x|$(typeof(y)),y)`.\n$y")
    pushfirst!(x.options,y)
    x
end

"""
    Base.push!(x::WrappedParser{<:Either}, option)

Push `option` to `x.options` of repeated inner parser.
"""
function Base.push!(x::WrappedParser, y)
    push!(x.parser,y)
    x
end
"""
    Base.pushfirst!(x::WrappedParser{<:Either}, option)

Push `option` as first `x.options` of repeated inner parser.
"""
function Base.pushfirst!(x::WrappedParser, y)
    pushfirst!(x.parser,y)
    x
end

mutable struct MutablePair{K,V}
    first::K
    second::V
    MutablePair{K,V}(f,s) where {K,V} =
        new{K,V}(f,s)
    MutablePair(f,s) =
        new{typeof(f),typeof(s)}(f,s)
end
Base.show(io::IO, x::MutablePair) =
    print(io, x.first, "=>", x.second)
@inline function with_state!(x::MutablePair,s)
    ##s isa Tuple{Int,Nothing} && error()
    x.second=s
    x
end

@inline function with_state!(x::MutablePair,k,s)
    ##s isa Tuple{Int,Nothing} && error()
    x.first=k
    x.second=s
    x
end
@inline function with_state!(x::Pair,s)
    Pair(x.first,s)
end
@inline function with_state!(x::Pair,k,s)
    Pair(k, s)
end

@inline function with_state!(x::Tuple,k,s)
    (k, s)
end

either_state_option(::Nothing) = 1
either_state_state(x::Nothing) = nothing
either_state_option(x::Tuple) = x[1]
either_state_state(x::Tuple) = x[2]
either_state_option(x::Union{Pair,MutablePair}) = x.first
either_state_state(x::Union{Pair,MutablePair}) = x.second

@inline function _leftof(str,i,parser::Either,x)
    ## @show i
    leftof(str,i,(@inbounds parser.options[either_state_option(x)]),either_state_state(x))
end

@inline function _rightof(str,i,parser::Either,x)
    ## @show i
    rightof(str,i,(@inbounds parser.options[either_state_option(x)]),either_state_state(x))
end
@inline function _rightof(str,i,parser::Either{P,T},x::Tuple{Int,T}) where {P,T}
    rightof(str,i,(@inbounds parser.options[either_state_option(x)]),either_state_state(x))
end

@generated function _leftof(str,i,parser::Either{pts},x::Union{Pair,MutablePair}) where {pts<:Tuple}
    fpts = fieldtypes(pts)
    parseoptions = [
        quote
        if j === $p
        return _leftof(str,i,parser.options[$p],s) # $(part[p]),s)
        end
        end
        for (p,t) in enumerate(fpts)
    ]
    R = quote
        j = x.first
        s = x.second
        $(parseoptions...)
        error("?")
    end
    R
end

@inline function iterate_state_paired(first,state,sstate::Nothing)
    nothing
end

@inline function iterate_state_paired(first, state, sstate::Tuple)
    iterate_state_paired(first, state, sstate...)
end

@inline function iterate_state_paired(first, state, next_i_::Int, nstate_)
    next_i_, with_state!(state,first,nstate_)
end

function iterate_state_paired(first, t, str, till, posi, next_i, state)
    iterate_state_paired(first, state, iterate_state(t, str, till, posi, next_i, either_state_state(state)))
end

function iterate_state(t::Either{<:Vector}, str, till, posi, next_i, state::Nothing)
    r = nothing
    for (j,o) in enumerate(t.options)
        r = iterate_state_paired(j,o,str,till,posi, next_i,nothing)
        r!== nothing && return r
    end
    nothing
end

function iterate_state(t::Either{<:Vector}, str, till, posi, next_i, state)
    @inbounds opt = t.options[either_state_option(state)]
    fromindex = either_state_option(state)+1
    posi = leftof(str,next_i,opt,either_state_state(state)) ##state[end][1]
    r = iterate_state_paired(either_state_option(state),opt,str,till,posi, next_i,state)
    r !== nothing && return r
    prune_captures(str,posi)
    ##sstate = nothing
    for j in fromindex:length(t.options)
        @inbounds r2 = iterate_state_paired(j,t.options[j],str,till,posi,posi,nothing)
        r2 !== nothing && return r2
    end
    nothing
end

function iterate_state(parser::Either{<:Tuple}, sequence, till, posi, next_i, state)
    either_first(parser,posi,next_i,state) do index, option, ni, sstate
        iterate_state_paired(index, option, sequence, till, posi, ni, sstate)
    end
end

@generated function either_first(f::Function, parser::Either{pts}, posi, next_i, state) where {pts<:Tuple}
    fpts = fieldtypes(pts)
    subsearch = Symbol[ gensym(:subsearch) for p in fpts ]
    push!(subsearch, gensym(:subsearch))
    subresult = Symbol[ gensym(:r) for p in fpts ]
    part = Symbol[ gensym(:part) for p in fpts ]
    init = Expr(:(=), Expr(:tuple, part...),:(parser.options))
    parseoptions = [
        quote
        @label $(subsearch[p])
        j > $p && @goto $(subsearch[p+1])
        $(subresult[p]) = f($p,$(part[p]), next_i_, sstate)
        $(subresult[p]) !== nothing && return $(subresult[p])# iterate_state_paired($p,state, $(subresult[p]))
        next_i_ = posi
        sstate = nothing
        end
        for (p,t) in enumerate(fpts)
    ]
    init_before =
        quote
            j = either_state_option(state)
            sstate = state
        end
    R = quote
        next_i_::Int = next_i
        $(init)
        $(init_before)
        $(parseoptions...)
        @label $(subsearch[end])
        return nothing
    end
    R
end

include("trie.jl")

AtomicState = NCodeunitsState{MatchState}

export Atomic
"""
    Atomic(x)

A parser matching `p`, and failing when required to backtrack
(behaving like an atomic group in regular expressions).
"""
@auto_hash_equals struct Atomic{P,S,T} <: WrappedParser{P,S,T}
    parser::P
    Atomic(p::CombinedParser) =
        new{typeof(p),state_type(p),result_type(p)}(p)
    Atomic{MatchState}(p::CombinedParser) =
        new{typeof(p),AtomicState,result_type(p)}(p)
end
Atomic(p) = Atomic(parser(x))

regex_prefix(x::Atomic) = "(?>"*regex_prefix(x.parser)
regex_suffix(x::Atomic) = regex_suffix(x.parser)*")"
function Base.get(parser::Atomic, sequence, till, after, i, state::AtomicState)
    a, s = iterate_state(parser.parser, sequence, till, i, i, nothing)
    get(parser.parser, sequence, till, after, i, s)
end

@inline iterate_state(parser::Atomic, sequence, till, posi, next_i, state::Nothing) =
    iterate_state(parser.parser, sequence, till, posi, next_i, state)
@inline iterate_state(parser::Atomic{<:Any,AtomicState}, sequence, till, posi, next_i, state::Nothing) =
    AtomicState(iterate_state(parser.parser, sequence, till, posi, next_i, state))
@inline iterate_state(parser::Atomic, sequence, till, posi, next_i, state) =
    nothing

function print_constructor(io::IO,x::Atomic)
    print_constructor(io,x.parser)
    print(io, " |> Atomic" )
end

include("match.jl")

include("caseless.jl")

include("reverse.jl")

include("get.jl")
include("transformation.jl")

include("operators.jl")

include("deepmap.jl")

function _log_names(x::CombinedParser,message::Function,a...;kw...)
    log = message(x,a...; kw...)
    if log!==nothing
        with_log("$(log)",x)
    else
        x
    end
end

export log_parser, log_names

"""
    log_names(x,names=true; exclude=nothing)

Rebuild parser replacing `NamedParser` instances with `with_log` parsers.
Log all `NamedParser` instanses if `names==true` or `name in names` and not `name in exclude`.

See also: [`with_log`](@ref), [`log_parser`](@ref), [`deepmap_parser`](@ref)
"""
function log_names(x, names=true; exclude=nothing)
    message = if names === true
        if exclude === nothing
            x -> x isa NamedParser ? x.name : nothing
        else
            x -> ( x isa NamedParser && !in(x.name,exclude) ) ? x.name : nothing
        end
    elseif names isa Type
        return log_parser(names, x)
    else
        x -> ( x isa NamedParser && in(x.name,names) ) ? x.name : nothing
    end
    log_parser(message, x)
end

iostring(f::Function, a...; kw...) =
    let sio = IOBuffer()
        f(sio, a...; kw...)
        String(take!(sio))
    end

function lognode(message)
    p ->
        if p isa message
            iostring(printnode, p)
        else
            nothing
        end
end

"""
    log_parser(message::Type, x::CombinedParser, a...; kw...)
    log_parser(message::Function, x::CombinedParser, a...; kw...)

Transform parser including logging statements for sub-parsers
of type `message` or
for which calling `message` does not return `nothing`.
"""
function log_parser(message::Type, x::CombinedParser, a...; kw...)
    log_parser(lognode(message), x, a...; kw...)
end

function log_parser(message::Function, x::CombinedParser, a...; kw...)
    deepmap_parser(_log_names,Dict(),x,message, a...;kw...)
end

export optimize
optimize(x) = deepmap_parser(_optimize,x)
_optimize(x,a...) = x
_deepmap_parser(::typeof(_optimize),dict::AbstractDict,x::SideeffectParser) = x.parser

include("defaults.jl")
include("re.jl")

include("show.jl")

include("memoize.jl")

include("lazy.jl")

include("bnf.jl")
end # module


text:
@testset "Shift register" begin
    registers = 8191
    for i = 1:8191
        output_xb, registers = @inferred GNSSSignals.shift_register(
            registers, [1, 3, 4, 6, 7, 8, 12, 13]
        )
        results = [2788, 2056 , 3322, 2087, 6431]
        if (i in [266, 804, 1559, 3471, 5343])
            @test registers in results
        end
    end
    @test registers == 8191
end

@testset "GPS L1" begin

    @test @inferred(get_center_frequency(GPSL5)) == 1.17645e9Hz
    @test @inferred(get_code_length(GPSL5)) == 10230
    @test @inferred(get_secondary_code_length(GPSL5)) == 10
    @test @inferred(get_code(GPSL5, 0, 1)) == 1
    @test @inferred(get_code(GPSL5, 0.0, 1)) == 1
    @test @inferred(get_code_unsafe(GPSL5, 0.0, 1)) == 1
    @test @inferred(get_data_frequency(GPSL5)) == 100Hz
    @test @inferred(get_code_frequency(GPSL5)) == 10230e3Hz
    @test get_code.(GPSL5, 0:10229, 1) == L5_SAT1_CODE

end

@testset "Neuman sequence" begin
    code = get_code.(GPSL5, 0:103199, 1)
    satellite_code = code[1:10230]
    neuman_hofman_code = [0,0,0,0,1,1,0,1,0,1]
    for i = 1:10
        @test code[1+10230*(i-1):10230*i] == (
            satellite_code .* (Int8(-1)^neuman_hofman_code[i])
        )
    end
    @test code[1:10230] == code[10231:20460]
end

ext: jl


text:
using Lingua
using Base.Test

@test stem("благодаря",    "bg") == "благодар"  # remove -я
@test stem("това",         "bg") == "тов"       # remove -а
@test stem("добре",        "bg") == "добр"      # remove -е
@test stem("какво",        "bg") == "какв"      # remove -о
@test stem("сигурен",      "bg") == "сигурн"    # remove -е- from -ен
@test stem("веднъж",       "bg") == "веднж"     # remove -ъ- from -ъ�
@test stem("единственият", "bg") == "единствн"  # remove article: -ият
@test stem("история",      "bg") == "истор"     # remove article: -ия
@test stem("животът",      "bg") == "живот"     # remove article: -ът
@test stem("работата",     "bg") == "раб"       # remove article: -та
@test stem("когато",       "bg") == "ког"       # remove article: -то
@test stem("дяволите",     "bg") == "дявол"     # remove article: -те
@test stem("правят",       "bg") == "прав"      # remove article: -ят
@test stem("ключовете",    "bg") == "ключ"      # remove plural: -ове
@test stem("търговци",     "bg") == "търг"      # remove plural: remove -вци from -овци
@test stem("запази",       "bg") == "запаг"     # remove plural: replace -зи with -г
@test stem("приятели",     "bg") == "приятял"   # remove plural: replace -е�и with -я�
@test stem("седмици",      "bg") == "седмик"    # remove plural: replace -ци with -к
@test stem("момчетата",    "bg") == "момч"      # remove plural: -та
@test stem("сънищата",     "bg") == "сън"       # remove plural: -ища
@test stem("спаси",        "bg") == "спах"      # remove plural: replace -си with -х
@test stem("всички",       "bg") == "всичк"     # remove plural: -и

max_stars_repo_name: patch-orphan/lingua-jl

max_issues_repo_name: patch-orphan/lingua-jl

max_forks_repo_name: patch-orphan/lingua-jl


text:
# v0.6.0

rad = π / 4
deg = 45.0

@show rad deg
@show sin(rad) sin(deg2rad(deg))
@show cos(rad) cos(deg2rad(deg))
@show tan(rad) tan(deg2rad(deg))
@show asin(sin(rad)) asin(sin(rad)) |> rad2deg
@show acos(cos(rad)) acos(cos(rad)) |> rad2deg
@show atan(tan(rad)) atan(tan(rad)) |> rad2deg

max_stars_repo_name: ethansaxenian/RosettaDecode

max_issues_repo_name: ethansaxenian/RosettaDecode

max_forks_repo_name: ethansaxenian/RosettaDecode


text:
# ------------------------------------------------------------------
# Licensed under the ISC License. See LICENSE in the project root.
# ------------------------------------------------------------------

"""
    readgeotable(args; coordnames=[:x,:y,:z], kwargs)

Read data from disk using `CSV.read`, optionally specifying
the columns `coordnames` with spatial coordinates.

The arguments `args` and keyword arguments `kwargs` are
forwarded to the `CSV.read` function, please check their
documentation for more details.

This function returns a [`GeoDataFrame`](@ref) object.
"""
readgeotable(args...; coordnames=[:x,:y,:z], kwargs...) =
  GeoDataFrame(read(args...; kwargs...), coordnames)

"""
      split(object, fraction, [direction])

Split spatial `object` into two parts where the first
part has a `fraction` of the total volume. The split
is performed along a `direction`. The default direction
is aligned with the first spatial dimension of the object.
"""
Base.split(object::AbstractSpatialObject{T,N}, fraction::Real,
           normal=ntuple(i -> i == 1 ? one(T) : zero(T), N)) where {N,T} =
  partition(object, BisectFractionPartitioner(normal, fraction))


text:
module timeevolution_mcwf

export mcwf, mcwf_h, mcwf_nh, mcwf_dynamic, mcwf_nh_dynamic, diagonaljumps

using ...bases, ...states, ...operators
using ...operators_dense, ...operators_sparse
using ..timeevolution
using ...operators_lazysum, ...operators_lazytensor, ...operators_lazyproduct
import OrdinaryDiffEq

const DecayRates = Union{Vector{Float64}, Matrix{Float64}, Void}

"""
    mcwf_h(tspan, rho0, Hnh, J; <keyword arguments>)

Calculate MCWF trajectory where the Hamiltonian is given in hermitian form.

For more information see: [`mcwf`](@ref)
"""
function mcwf_h(tspan, psi0::Ket, H::Operator, J::Vector;
    seed=rand(UInt), rates::DecayRates=nothing,
    fout=nothing, Jdagger::Vector=dagger.(J),
    tmp::Ket=copy(psi0),
    display_beforeevent=false, display_afterevent=false,
    kwargs...)
    check_mcwf(psi0, H, J, Jdagger, rates)
    f(t, psi, dpsi) = dmcwf_h(psi, H, J, Jdagger, dpsi, tmp, rates)
    j(rng, t, psi, psi_new) = jump(rng, t, psi, J, psi_new, rates)
    return integrate_mcwf(f, j, tspan, psi0, seed; fout=fout,
    display_beforeevent=display_beforeevent,
    display_afterevent=display_afterevent,
    kwargs...)
end

"""
    mcwf_nh(tspan, rho0, Hnh, J; <keyword arguments>)

Calculate MCWF trajectory where the Hamiltonian is given in non-hermitian form.

```math
H_{nh} = H - \\frac{i}{2} \\sum_k J^†_k J_k
```

For more information see: [`mcwf`](@ref)
"""
function mcwf_nh(tspan, psi0::Ket, Hnh::Operator, J::Vector;
    seed=rand(UInt), fout=nothing,
    display_beforeevent=false, display_afterevent=false,
    kwargs...)
    check_mcwf(psi0, Hnh, J, J, nothing)
    f(t, psi, dpsi) = dmcwf_nh(psi, Hnh, dpsi)
    j(rng, t, psi, psi_new) = jump(rng, t, psi, J, psi_new, nothing)
    return integrate_mcwf(f, j, tspan, psi0, seed; fout=fout,
    display_beforeevent=display_beforeevent,
    display_afterevent=display_afterevent,
    kwargs...)
end

"""
    mcwf(tspan, psi0, H, J; <keyword arguments>)

Integrate the master equation using the MCWF method.

There are two implementations for integrating the non-hermitian
schroedinger equation:

* [`mcwf_h`](@ref): Usual formulation with Hamiltonian + jump operators
separately.
* [`mcwf_nh`](@ref): Variant with non-hermitian Hamiltonian.

The `mcwf` function takes a normal Hamiltonian, calculates the
non-hermitian Hamiltonian and then calls [`mcwf_nh`](@ref) which is
slightly faster.

# Arguments
* `tspan`: Vector specifying the points of time for which output should
be displayed.
* `psi0`: Initial state vector.
* `H`: Arbitrary Operator specifying the Hamiltonian.
* `J`: Vector containing all jump operators which can be of any arbitrary
operator type.
* `seed=rand()`: Seed used for the random number generator.
* `rates=ones()`: Vector of decay rates.
* `fout`: If given, this function `fout(t, psi)` is called every time an
output should be displayed. ATTENTION: The state `psi` is neither
normalized nor permanent! It is still in use by the ode solve
and therefore must not be changed.
* `Jdagger=dagger.(J)`: Vector containing the hermitian conjugates of the jump
operators. If they are not given they are calculated automatically.
* `display_beforeevent=false`: `fout` is called before every jump.
* `display_afterevent=false`: `fout` is called after every jump.
* `kwargs...`: Further arguments are passed on to the ode solver.
"""
function mcwf(tspan, psi0::Ket, H::Operator, J::Vector;
    seed=rand(UInt), rates::DecayRates=nothing,
    fout=nothing, Jdagger::Vector=dagger.(J),
    display_beforeevent=false, display_afterevent=false,
    kwargs...)
    isreducible = check_mcwf(psi0, H, J, Jdagger, rates)
    if !isreducible
        tmp = copy(psi0)
        dmcwf_h_(t, psi, dpsi) = dmcwf_h(psi, H, J, Jdagger, dpsi, tmp, rates)
        j_h(rng, t, psi, psi_new) = jump(rng, t, psi, J, psi_new, rates)
        return integrate_mcwf(dmcwf_h_, j_h, tspan, psi0, seed;
        fout=fout,
        display_beforeevent=display_beforeevent,
        display_afterevent=display_afterevent,
        kwargs...)
    else
        Hnh = copy(H)
        if typeof(rates) == Void
            for i=1:length(J)
                Hnh -= 0.5im*Jdagger[i]*J[i]
            end
        else
            for i=1:length(J)
                Hnh -= 0.5im*rates[i]*Jdagger[i]*J[i]
            end
        end
        dmcwf_nh_(t, psi, dpsi) = dmcwf_nh(psi, Hnh, dpsi)
        j_nh(rng, t, psi, psi_new) = jump(rng, t, psi, J, psi_new, rates)
        return integrate_mcwf(dmcwf_nh_, j_nh, tspan, psi0, seed;
        fout=fout,
        display_beforeevent=display_beforeevent,
        display_afterevent=display_afterevent,
        kwargs...)
    end
end

"""
    mcwf_dynamic(tspan, psi0, f; <keyword arguments>)

Integrate the master equation using the MCWF method with dynamic
Hamiltonian and Jump operators.

The `mcwf` function takes a normal Hamiltonian, calculates the
non-hermitian Hamiltonian and then calls [`mcwf_nh`](@ref) which is
slightly faster.

# Arguments
* `tspan`: Vector specifying the points of time for which output should
be displayed.
* `psi0`: Initial state vector.
* `f`: Function `f(t, psi) -> (H, J, Jdagger)` or `f(t, psi) -> (H, J, Jdagger, rates)`
    that returns the time-dependent Hamiltonian and Jump operators.
* `seed=rand()`: Seed used for the random number generator.
* `rates=ones()`: Vector of decay rates.
* `fout`: If given, this function `fout(t, psi)` is called every time an
output should be displayed. ATTENTION: The state `psi` is neither
normalized nor permanent! It is still in use by the ode solve
and therefore must not be changed.
* `display_beforeevent=false`: `fout` is called before every jump.
* `display_afterevent=false`: `fout` is called after every jump.
* `kwargs...`: Further arguments are passed on to the ode solver.
"""
function mcwf_dynamic(tspan, psi0::Ket, f::Function;
    seed=rand(UInt), rates::DecayRates=nothing,
    fout=nothing, display_beforeevent=false, display_afterevent=false,
    kwargs...)
    tmp = copy(psi0)
    dmcwf_(t, psi, dpsi) = dmcwf_h_dynamic(t, psi, f, rates, dpsi, tmp)
    j_(rng, t, psi, psi_new) = jump_dynamic(rng, t, psi, f, psi_new, rates)
    integrate_mcwf(dmcwf_, j_, tspan, psi0, seed;
        fout=fout,
        display_beforeevent=display_beforeevent,
        display_afterevent=display_afterevent,
        kwargs...)
end

"""
    mcwf_nh_dynamic(tspan, rho0, f; <keyword arguments>)

Calculate MCWF trajectory where the dynamic Hamiltonian is given in non-hermitian form.

For more information see: [`mcwf_dynamic`](@ref)
"""
function mcwf_nh_dynamic(tspan, psi0::Ket, f::Function;
    seed=rand(UInt), rates::DecayRates=nothing,
    fout=nothing, display_beforeevent=false, display_afterevent=false,
    kwargs...)
    dmcwf_(t, psi, dpsi) = dmcwf_nh_dynamic(t, psi, f, dpsi)
    j_(rng, t, psi, psi_new) = jump_dynamic(rng, t, psi, f, psi_new, rates)
    integrate_mcwf(dmcwf_, j_, tspan, psi0, seed;
        fout=fout,
        display_beforeevent=display_beforeevent,
        display_afterevent=display_afterevent,
        kwargs...)
end

function dmcwf_h_dynamic(t::Float64, psi::Ket, f::Function, rates::DecayRates,
                    dpsi::Ket, tmp::Ket)
    result = f(t, psi)
    @assert 3 <= length(result) <= 4
    if length(result) == 3
        H, J, Jdagger = result
        rates_ = rates
    else
        H, J, Jdagger, rates_ = result
    end
    check_mcwf(psi, H, J, Jdagger, rates_)
    dmcwf_h(psi, H, J, Jdagger, dpsi, tmp, rates)
end

function dmcwf_nh_dynamic(t::Float64, psi::Ket, f::Function, dpsi::Ket)
    result = f(t, psi)
    @assert 3 <= length(result) <= 4
    H, J, Jdagger = result[1:3]
    check_mcwf(psi, H, J, Jdagger, nothing)
    dmcwf_nh(psi, H, dpsi)
end

function jump_dynamic(rng, t::Float64, psi::Ket, f::Function, psi_new::Ket, rates::DecayRates)
    result = f(t, psi)
    @assert 3 <= length(result) <= 4
    J = result[2]
    if length(result) == 3
        rates_ = rates
    else
        rates_ = result[4]
    end
    jump(rng, t::Float64, psi::Ket, J::Vector, psi_new::Ket, rates::DecayRates)
end

"""
    integrate_mcwf(dmcwf, jumpfun, tspan, psi0, seed; fout, kwargs...)

Integrate a single Monte Carlo wave function trajectory.

# Arguments
* `dmcwf`: A function `f(t, psi, dpsi)` that calculates the time-derivative of
        `psi` at time `t` and stores the result in `dpsi`.
* `jumpfun`: A function `f(rng, t, psi, dpsi)` that uses the random number
        generator `rng` to determine if a jump is performed and stores the
        result in `dpsi`.
* `tspan`: Vector specifying the points of time for which output should
        be displayed.
* `psi0`: Initial state vector.
* `seed`: Seed used for the random number generator.
* `fout`: If given, this function `fout(t, psi)` is called every time an
        output should be displayed. ATTENTION: The state `psi` is neither
        normalized nor permanent! It is still in use by the ode solver
        and therefore must not be changed.
* `kwargs`: Further arguments are passed on to the ode solver.
"""
function integrate_mcwf(dmcwf::Function, jumpfun::Function, tspan,
                        psi0::Ket, seed; fout=nothing,
                        display_beforeevent=false, display_afterevent=false,
                        kwargs...)
    tmp = copy(psi0)
    as_ket(x::Vector{Complex128}) = Ket(psi0.basis, x)
    as_vector(psi::Ket) = psi.data
    rng = MersenneTwister(convert(UInt, seed))
    jumpnorm = Ref(rand(rng))
    djumpnorm(x::Vector{Complex128}, t, integrator) = norm(as_ket(x))^2 - (1-jumpnorm[])
    function dojump(integrator)
        x = integrator.u
        t = integrator.t
        jumpfun(rng, t, as_ket(x), tmp)
        x .= tmp.data
        jumpnorm[] = rand(rng)
    end
    cb = OrdinaryDiffEq.ContinuousCallback(djumpnorm,dojump,
                     save_positions = (display_beforeevent,display_afterevent))

    function fout_(t, x::Ket)
        if fout==nothing
            psi = copy(x)
            psi /= norm(psi)
            return psi
        else
            return fout(t, x)
        end
    end

    timeevolution.integrate(float(tspan), dmcwf, as_vector(psi0),
                copy(psi0), copy(psi0), fout_;
                callback = cb,
                kwargs...)
end

"""
    jump(rng, t, psi, J, psi_new)

Default jump function.

# Arguments
* `rng:` Random number generator
* `t`: Point of time where the jump is performed.
* `psi`: State vector before the jump.
* `J`: List of jump operators.
* `psi_new`: Result of jump.
"""
function jump(rng, t::Float64, psi::Ket, J::Vector, psi_new::Ket, rates::Void)
    if length(J)==1
        operators.gemv!(complex(1.), J[1], psi, complex(0.), psi_new)
        psi_new.data ./= norm(psi_new)
    else
        probs = zeros(Float64, length(J))
        for i=1:length(J)
            operators.gemv!(complex(1.), J[i], psi, complex(0.), psi_new)
            probs[i] = dot(psi_new.data, psi_new.data)
        end
        cumprobs = cumsum(probs./sum(probs))
        r = rand(rng)
        i = findfirst(cumprobs.>r)
        operators.gemv!(complex(1.)/sqrt(probs[i]), J[i], psi, complex(0.), psi_new)
    end
    return nothing
end

function jump(rng, t::Float64, psi::Ket, J::Vector, psi_new::Ket, rates::Vector{Float64})
    if length(J)==1
        operators.gemv!(complex(sqrt(rates[1])), J[1], psi, complex(0.), psi_new)
        psi_new.data ./= norm(psi_new)
    else
        probs = zeros(Float64, length(J))
        for i=1:length(J)
            operators.gemv!(complex(sqrt(rates[i])), J[i], psi, complex(0.), psi_new)
            probs[i] = dot(psi_new.data, psi_new.data)
        end
        cumprobs = cumsum(probs./sum(probs))
        r = rand(rng)
        i = findfirst(cumprobs.>r)
        operators.gemv!(complex(sqrt(rates[i]/probs[i])), J[i], psi, complex(0.), psi_new)
    end
    return nothing
end

"""
Evaluate non-hermitian Schroedinger equation.

The non-hermitian Hamiltonian is given in two parts - the hermitian part H and
the jump operators J.
"""
function dmcwf_h(psi::Ket, H::Operator,
                 J::Vector, Jdagger::Vector, dpsi::Ket, tmp::Ket, rates::Void)
    operators.gemv!(complex(0,-1.), H, psi, complex(0.), dpsi)
    for i=1:length(J)
        operators.gemv!(complex(1.), J[i], psi, complex(0.), tmp)
        operators.gemv!(-complex(0.5,0.), Jdagger[i], tmp, complex(1.), dpsi)
    end
    return dpsi
end

function dmcwf_h(psi::Ket, H::Operator,
                 J::Vector, Jdagger::Vector, dpsi::Ket, tmp::Ket, rates::Vector{Float64})
    operators.gemv!(complex(0,-1.), H, psi, complex(0.), dpsi)
    for i=1:length(J)
        operators.gemv!(complex(rates[i]), J[i], psi, complex(0.), tmp)
        operators.gemv!(-complex(0.5,0.), Jdagger[i], tmp, complex(1.), dpsi)
    end
    return dpsi
end

"""
Evaluate non-hermitian Schroedinger equation.

The given Hamiltonian is already the non-hermitian version.
"""
function dmcwf_nh(psi::Ket, Hnh::Operator, dpsi::Ket)
    operators.gemv!(complex(0,-1.), Hnh, psi, complex(0.), dpsi)
    return dpsi
end

"""
    check_mcwf(psi0, H, J, Jdagger, rates)

Check input of mcwf.
"""
function check_mcwf(psi0::Ket, H::Operator, J::Vector, Jdagger::Vector, rates::DecayRates)
    isreducible = true
    check_samebases(basis(psi0), basis(H))
    if !(isa(H, DenseOperator) || isa(H, SparseOperator))
        isreducible = false
    end
    for j=J
        @assert isa(j, Operator)
        if !(isa(j, DenseOperator) || isa(j, SparseOperator))
            isreducible = false
        end
        check_samebases(H, j)
    end
    for j=Jdagger
        @assert isa(j, Operator)
        if !(isa(j, DenseOperator) || isa(j, SparseOperator))
            isreducible = false
        end
        check_samebases(H, j)
    end
    @assert length(J) == length(Jdagger)
    if typeof(rates) == Matrix{Float64}
        throw(ArgumentError("Matrix of decay rates not supported for MCWF!
            Use diagonaljumps(rates, J) to calculate new rates and jump operators."))
    elseif typeof(rates) == Vector{Float64}
        @assert length(rates) == length(J)
    end
    isreducible
end

"""
    diagonaljumps(rates, J)

Diagonalize jump operators.

The given matrix `rates` of decay rates is diagonalized and the
corresponding set of jump operators is calculated.

# Arguments
* `rates`: Matrix of decay rates.
* `J`: Vector of jump operators.
"""
function diagonaljumps(rates::Matrix{Float64}, J::Vector{T}) where T <: Operator
    @assert length(J) == size(rates)[1] == size(rates)[2]
    d, v = eig(rates)
    d, [sum([v[j, i]*J[j] for j=1:length(d)]) for i=1:length(d)]
end

function diagonaljumps(rates::Matrix{Float64}, J::Vector{T}) where T <: Union{LazySum, LazyTensor, LazyProduct}
    @assert length(J) == size(rates)[1] == size(rates)[2]
    d, v = eig(rates)
    d, [LazySum([v[j, i]*J[j] for j=1:length(d)]...) for i=1:length(d)]
end

end #module


text:
using Distances

@doc raw"""
    AbstractCorrelation

An abstract type for all correlation functions.
"""
abstract type AbstractCorrelation end

(k::AbstractCorrelation)(x, y, θ...) = k(distance(k, θ...)(x, y))

function correlation(k::AbstractCorrelation, x, θ...; jitter = 0)
    ret = Array{Float64}(undef, size(x, 2), size(x, 2))
    correlation!(ret, k, x, θ...; jitter = jitter)
    return ret
end
function cross_correlation(k::AbstractCorrelation, x, y, θ...)
    ret = Array{Float64}(undef, size(x, 2), size(y, 2))
    cross_correlation!(ret, k, x, y, θ...)
    return ret
end
function cross_correlation!(out, k::AbstractCorrelation, x, y, θ...)
    dist = distance(k, θ...)
    pairwise!(out, dist, x, y, dims=2)
    out .= (τ -> k(τ, θ...)).(out)
    return nothing
end
function correlation!(out, k::AbstractCorrelation, x, θ...; jitter = 0)
    dist = distance(k, θ...)
    pairwise!(out, dist, x, dims=2)
    out .= (τ -> k(τ, θ...)).(out)
    if jitter != 0
        out[diagind(out)] .+= jitter
        out ./= out[1, 1]
    end
    return nothing
end

@doc raw"""
"""
struct FixedParam{K<:AbstractCorrelation,T} <: AbstractCorrelation
    k::K
    θ::T
end
FixedParam(k, θ...) = FixedParam(k, θ)

(k::FixedParam)(τ) = k.k(τ, k.θ...)
distance(k::FixedParam) = distance(k.k, k.θ...)

@doc raw"""
    Gaussian
"""
struct Gaussian <: AbstractCorrelation end
const RBF = Gaussian
const SqExponential = RBF

(::Gaussian)(τ, ℓ::Real) = exp(- τ / 2 / ℓ)
(::Gaussian)(τ, ::AbstractVector) = exp(- τ / 2)
distance(::Gaussian, ::Real) = SqEuclidean()
distance(::Gaussian, ℓ::AbstractVector) = WeightedSqEuclidean(ℓ)

partial_θ(k::Gaussian, τ, ℓ) = τ * k(τ, ℓ) / 2 / ℓ ^ 2
partial_τ(k::Gaussian, τ, ℓ) = - k(τ, ℓ) / 2 / ℓ
partial_θθ(k::RBF, τ, ℓ) = τ * k(τ, ℓ) * (τ - 4 * ℓ) / 4 / ℓ ^ 4

struct Spherical <: AbstractCorrelation end
# TODO

struct Matern <: AbstractCorrelation end
# TODO

struct RationalQuadratic <: AbstractCorrelation end
# TODO

max_stars_repo_name: dbindel/btg

max_issues_repo_name: dbindel/btg

max_forks_repo_name: dbindel/btg


text:
abstract type AbstractProbabilityVector{T <: Real} <: AbstractVector{T} end
Base.@propagate_inbounds getindex(pvec::AbstractProbabilityVector, i) = getweight(pvec, i)
Base.@propagate_inbounds setindex!(pvec::AbstractProbabilityVector, w, i) = setweight!(pvec, w, i)
Base.@propagate_inbounds setprobability!(pvec::AbstractProbabilityVector{T}, p::T, i::Int) where T = setweight!(pvec, p*normalization(pvec), i)
Base.@propagate_inbounds getprobability(pvec::AbstractProbabilityVector, i) = getweight(pvec, i) / normalization(pvec)

firstindex(::AbstractProbabilityVector) = 1
lastindex(pvec::AbstractProbabilityVector) = length(pvec)
size(pvec::AbstractProbabilityVector) = (length(pvec),)

###############################################################################

# more efficient for small probability vectors
struct ProbabilityVector{T} <: AbstractProbabilityVector{T}
    p::Vector{T}
    cdf::Vector{T}

    function ProbabilityVector{T}(p::Vector{T}) where {T <: Real}
        if length(p) == 0
            throw(ArgumentError("probability vector must have non-zero length!"))
        end
        if any(x -> x < zero(T), p)
            throw(ArgumentError("weights must be non-negative!"))
        end
        cdf = cumsum(p)
        new{T}(p, cdf)
    end
end
ProbabilityVector(p::Vector{T}) where T = ProbabilityVector{T}(p)
@inline length(pvec::ProbabilityVector) = length(pvec.p)
normalization(pvec::ProbabilityVector) = @inbounds pvec.cdf[end]

function show(io::IO, pvec::ProbabilityVector{T}) where T
    r = repr(pvec.p; context=IOContext(io, :limit=>true))
    println(io, "ProbabilityVector{$T}($r)")
end

function rand(pvec::ProbabilityVector{T})::Int where T
    cdf = pvec.cdf
    r = rand() * cdf[end]

    for i in eachindex(cdf)
        @inbounds if r < cdf[i]
            return i
        end
    end
    return lastindex(cdf)
end

# TODO: fix bisection method
# function rand_bisect(pvec::ProbabilityVector{T})::Int where T
#     if length(pvec) < 5
#         return rand_linear(pvec)
#     else
#         cdf = pvec.cdf
#         # @show length(cdf)
#         r = rand()*cdf[end]
#         l, u = firstindex(pvec)-1, lastindex(pvec)-1

#         while l <= u
#             m = fld((l + u), 2)
#             cdfm = cdf[m+1]
#             if cdfm < r
#                 l = m + 1
#             elseif cdfm > r
#                 u = m - 1
#             else
#                 return m + 1
#             end
#         end
#         return l
#     end
# end

@inline function setweight!(pvec::ProbabilityVector{T}, w::T, i::Int) where T
    @boundscheck checkbounds(pvec, i)

    p, cdf = pvec.p, pvec.cdf
    @inbounds diff = w - p[i]
    @inbounds p[i] = w

    @simd for j in i:length(p)
        cdf[j] += diff
    end
end

@inline function getweight(pvec::ProbabilityVector, i::Int)
    @boundscheck checkbounds(pvec, i)
    return @inbounds pvec.p[i]
end

@inline function getweight(pvec::ProbabilityVector, r::AbstractArray{Int})
    @boundscheck checkbounds(pvec, r)
    return @inbounds pvec.p[r]
end

###############################################################################

# more efficient for larger probability vectors
struct ProbabilityHeap{T} <: AbstractProbabilityVector{T}
    prob_heap::Vector{T}
    length::Int

    function ProbabilityHeap{T}(p::Vector{T}) where {T <: Real}
        if length(p) == 0
            throw(ArgumentError("probability vector must have non-zero length!"))
        end
        if any(x -> x < zero(T), p)
            throw(ArgumentError("weights must be non-negative!"))
        end

        L = length(p)
        d = 2 ^ ceil(Int, log2(L))

        heap = zeros(T, 2*d)
        @inbounds @views heap[d : d + L - 1] = p

        @inbounds for i in (d-1):-1:1
            heap[i] = heap[2*i] + heap[2*i + 1]
        end

        new{T}(heap, L)
    end
end
ProbabilityHeap(p::Vector{T}) where T = ProbabilityHeap{T}(p)
@inline length(pvec::ProbabilityHeap) = pvec.length
normalization(pvec::ProbabilityHeap) = @inbounds pvec.prob_heap[1]

function show(io::IO, p::ProbabilityHeap{T}) where T
    heap, L = p.prob_heap, p.length

    d = 2 ^ ceil(Int, log2(L))

    pvec = heap[d : d + L - 1]
    r = repr(pvec; context=IOContext(io, :limit=>true))

    println(io, "ProbabilityHeap{$T}($r)")
end

function rand(pvec::ProbabilityHeap{T})::Int where T
    heap = pvec.prob_heap
    l = length(heap) ÷ 2
    @inbounds r = rand() * heap[1]

    i = 1
    while i < l
        i *= 2
        @inbounds left = heap[i]
        if r > left
            r -= left
            i += 1
        end
    end
    return (i - l + 1)
end

@inline function setweight!(pvec::ProbabilityHeap{T}, w::T, i::Int) where T
    @boundscheck checkbounds(pvec, i)

    heap = pvec.prob_heap
    j = (length(heap) ÷ 2) - 1 + i
    @inbounds heap[j] = w
    @inbounds while j > 1
        j ÷= 2
        heap[j] = heap[2*j] + heap[2*j + 1]
    end
end

@inline function getweight(pvec::ProbabilityHeap, i::Int)
    @boundscheck checkbounds(pvec, i)

    heap = pvec.prob_heap
    d = (length(heap) ÷ 2) - 1
    @inbounds x = heap[d + i]
    return x
end

@inline function getweight(pvec::ProbabilityHeap, r::AbstractArray{Int})
    @boundscheck checkbounds(pvec, r)

    heap = pvec.prob_heap
    d = (length(heap) ÷ 2) - 1
    @inbounds x = heap[d .+ r]
    return x
end

###############################################################################

const CUTOFF = 50

function probability_vector(p::Vector{T})::AbstractProbabilityVector{T} where T
    if length(p) < CUTOFF
        return ProbabilityVector(p)
    else
        return ProbabilityHeap(p)
    end
end


text:
function output_ui()

    # Title of section
    title = node(:div, tachyons_css, "Output Options") |> class"f4 lh-title"

    o1 = Observable("")
    base_name = vbox(node(:div, "Base output file name: ",
                      attributes = Dict(:style => "margin-top: 12px")) |> class"b",
                     textbox(value = o1))

    o2 = Observable(false)
    o3 = Observable(false)
    options = vbox(checkbox("Current maps", value = o2),
                    checkbox("Voltage maps", value = o3))

    output_ui = vbox(title,
                     base_name,
                     options)

    s = Scope()

	s.dom = output_ui
    @private s["out"] = o1
    @private s["cur"] = o2
    @private s["volt"] = o3

    s
end


text:
export iauLdsun
"""
Deflection of starlight by the Sun.

This function is part of the International Astronomical Union's
SOFA (Standards of Fundamental Astronomy) software collection.

Status:  support function.

Given:
   p      double[3]  direction from observer to star (unit vector)
   e      double[3]  direction from Sun to observer (unit vector)
   em     double     distance from Sun to observer (au)

Returned:
   p1     double[3]  observer to deflected star (unit vector)

Notes:

   1. The source is presumed to be sufficiently distant that its
   directions seen from the Sun and the observer are essentially
   the same.

   2. The deflection is restrained when the angle between the star and
   the center of the Sun is less than a threshold value, falling to
   zero deflection for zero separation.  The chosen threshold value
   is within the solar limb for all solar-system applications, and
   is about 5 arcminutes for the case of a terrestrial observer.

   3. The arguments p and p1 can be the same array.

Called:
   iauLd        light deflection by a solar-system body

This revision:   2016 June 16

SOFA release 2018-01-30

Copyright (C) 2018 IAU SOFA Board.  See notes at end.
"""

# void iauLdsun(double p[3], double e[3], double em, double p1[3])
function iauLdsun(p::AbstractVector{<:Real}, e::AbstractVector{<:Real}, em::Real)
   # Allocate return values
   p1 = zeros(Float64, 3)

   ccall((:iauLdsun, libsofa_c), Cvoid,
        (Ptr{Cdouble}, Ptr{Cdouble}, Cdouble, Ptr{Cdouble}),
        convert(Array{Float64, 1}, p), convert(Array{Float64, 1}, e), convert(Float64, em), p1)

   return SVector{3}(p1)
end