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

#####################
# OptimizationState #
#####################

mutable struct OptimizationState
    linfo::MethodInstance
    result_vargs::Vector{Any}
    backedges::Vector{Any}
    src::CodeInfo
    mod::Module
    nargs::Int
    next_label::Int # index of the current highest label for this function
    min_valid::UInt
    max_valid::UInt
    params::Params
    function OptimizationState(frame::InferenceState)
        s_edges = frame.stmt_edges[1]
        if s_edges === ()
            s_edges = []
            frame.stmt_edges[1] = s_edges
        end
        src = frame.src
        next_label = max(label_counter(src.code), length(src.code)) + 10
        return new(frame.linfo, frame.result.vargs,
                   s_edges::Vector{Any},
                   src, frame.mod, frame.nargs,
                   next_label, frame.min_valid, frame.max_valid,
                   frame.params)
    end
    function OptimizationState(linfo::MethodInstance, src::CodeInfo,
                               params::Params)
        # prepare src for running optimization passes
        # if it isn't already
        nssavalues = src.ssavaluetypes
        if nssavalues isa Int
            src.ssavaluetypes = Any[ Any for i = 1:nssavalues ]
        end
        if src.slottypes === nothing
            nslots = length(src.slotnames)
            src.slottypes = Any[ Any for i = 1:nslots ]
        end
        s_edges = []
        # cache some useful state computations
        toplevel = !isa(linfo.def, Method)
        if !toplevel
            meth = linfo.def
            inmodule = meth.module
            nargs = meth.nargs
        else
            inmodule = linfo.def::Module
            nargs = 0
        end
        next_label = max(label_counter(src.code), length(src.code)) + 10
        result_vargs = Any[] # if you want something more accurate, set it yourself :P
        return new(linfo, result_vargs,
                   s_edges::Vector{Any},
                   src, inmodule, nargs,
                   next_label,
                   min_world(linfo), max_world(linfo),
                   params)
    end
end

function OptimizationState(linfo::MethodInstance, params::Params)
    src = retrieve_code_info(linfo)
    src === nothing && return nothing
    return OptimizationState(linfo, src, params)
end

include("compiler/ssair/driver.jl")

_topmod(sv::OptimizationState) = _topmod(sv.mod)

function update_valid_age!(min_valid::UInt, max_valid::UInt, sv::OptimizationState)
    sv.min_valid = max(sv.min_valid, min_valid)
    sv.max_valid = min(sv.max_valid, max_valid)
    @assert(!isa(sv.linfo.def, Method) ||
            (sv.min_valid == typemax(UInt) && sv.max_valid == typemin(UInt)) ||
            sv.min_valid <= sv.params.world <= sv.max_valid,
            "invalid age range update")
    nothing
end

update_valid_age!(li::MethodInstance, sv::OptimizationState) = update_valid_age!(min_world(li), max_world(li), sv)

function add_backedge!(li::MethodInstance, caller::OptimizationState)
    isa(caller.linfo.def, Method) || return # don't add backedges to toplevel exprs
    push!(caller.backedges, li)
    update_valid_age!(li, caller)
    nothing
end

###########
# structs #
###########

struct InvokeData
    mt::Core.MethodTable
    entry::Core.TypeMapEntry
    types0
    fexpr
    texpr
end

#############
# constants #
#############

# The slot has uses that are not statically dominated by any assignment
# This is implied by `SLOT_USEDUNDEF`.
# If this is not set, all the uses are (statically) dominated by the defs.
# In particular, if a slot has `AssignedOnce && !StaticUndef`, it is an SSA.
const SLOT_STATICUNDEF  = 1

const SLOT_ASSIGNEDONCE = 16 # slot is assigned to only once

const SLOT_USEDUNDEF    = 32 # slot has uses that might raise UndefVarError

# const SLOT_CALLED      = 64

const IR_FLAG_INBOUNDS = 0x01

# known affect-free calls (also effect-free)
const _PURE_BUILTINS = Any[tuple, svec, fieldtype, apply_type, ===, isa, typeof, UnionAll, nfields]

# known effect-free calls (might not be affect-free)
const _PURE_BUILTINS_VOLATILE = Any[getfield, arrayref, isdefined, Core.sizeof]

const TOP_TUPLE = GlobalRef(Core, :tuple)

#########
# logic #
#########

function isinlineable(m::Method, src::CodeInfo, mod::Module, params::Params, bonus::Int=0)
    # compute the cost (size) of inlining this code
    inlineable = false
    cost_threshold = params.inline_cost_threshold
    if m.module === _topmod(m.module)
        # a few functions get special treatment
        name = m.name
        sig = m.sig
        if ((name === :+ || name === :* || name === :min || name === :max) &&
            isa(sig,DataType) &&
            sig == Tuple{sig.parameters[1],Any,Any,Any,Vararg{Any}})
            inlineable = true
        elseif (name === :iterate || name === :unsafe_convert ||
                name === :cconvert)
            cost_threshold *= 4
        end
    end
    if !inlineable
        inlineable = inline_worthy(src.code, src, mod, params, cost_threshold + bonus)
    end
    return inlineable
end

# converge the optimization work
function optimize(me::InferenceState)
    # annotate fulltree with type information
    type_annotate!(me)

    # run optimization passes on fulltree
    force_noinline = true
    def = me.linfo.def
    if me.limited && me.cached && me.parent !== nothing
        # a top parent will be cached still, but not this intermediate work
        me.cached = false
        me.linfo.inInference = false
    elseif me.optimize
        opt = OptimizationState(me)
        reindex_labels!(opt)
        nargs = Int(opt.nargs) - 1
        if def isa Method
            topline = LineInfoNode(opt.mod, def.name, def.file, Int(def.line), 0)
        else
            topline = LineInfoNode(opt.mod, NullLineInfo.method, NullLineInfo.file, 0, 0)
        end
        linetable = [topline]
        @timeit "optimizer" ir = run_passes(opt.src, nargs, linetable, opt)
        force_noinline = any(x->isexpr(x, :meta) && x.args[1] == :noinline, ir.meta)
        replace_code_newstyle!(opt.src, ir, nargs, linetable)
        me.min_valid = opt.min_valid
        me.max_valid = opt.max_valid
    end

    # convert all type information into the form consumed by the code-generator
    widen_all_consts!(me.src)

    # compute inlining and other related properties
    me.const_ret = (isa(me.bestguess, Const) || isconstType(me.bestguess))
    if me.const_ret
        proven_pure = false
        # must be proven pure to use const_api; otherwise we might skip throwing errors
        # (issue #20704)
        # TODO: Improve this analysis; if a function is marked @pure we should really
        # only care about certain errors (e.g. method errors and type errors).
        if length(me.src.code) < 10
            proven_pure = true
            for stmt in me.src.code
                if !statement_effect_free(stmt, me.src, me.mod)
                    proven_pure = false
                    break
                end
            end
            if proven_pure
                for fl in me.src.slotflags
                    if (fl & SLOT_USEDUNDEF) != 0
                        proven_pure = false
                        break
                    end
                end
            end
        end
        if proven_pure
            me.src.pure = true
        end

        if proven_pure && !coverage_enabled()
            # use constant calling convention
            # Do not emit `jl_fptr_const_return` if coverage is enabled
            # so that we don't need to add coverage support
            # to the `jl_call_method_internal` fast path
            # Still set pure flag to make sure `inference` tests pass
            # and to possibly enable more optimization in the future
            if !(isa(me.bestguess, Const) && !is_inlineable_constant(me.bestguess.val))
                me.const_api = true
            end
            force_noinline || (me.src.inlineable = true)
        end
    end

    # determine and cache inlineability
    if !force_noinline
        # don't keep ASTs for functions specialized on a Union argument
        # TODO: this helps avoid a type-system bug mis-computing sparams during intersection
        sig = unwrap_unionall(me.linfo.specTypes)
        if isa(sig, DataType) && sig.name === Tuple.name
            for P in sig.parameters
                P = unwrap_unionall(P)
                if isa(P, Union)
                    force_noinline = true
                    break
                end
            end
        else
            force_noinline = true
        end
    end
    if force_noinline
        me.src.inlineable = false
    elseif !me.src.inlineable && isa(def, Method)
        bonus = 0
        if me.bestguess ⊑ Tuple && !isbitstype(widenconst(me.bestguess))
            bonus = me.params.inline_tupleret_bonus
        end
        me.src.inlineable = isinlineable(def, me.src, me.mod, me.params, bonus)
    end
    me.src.inferred = true
    if me.optimize && !(me.limited && me.parent !== nothing)
        validate_code_in_debug_mode(me.linfo, me.src, "optimized")
    end
    nothing
end

# inference completed on `me`
# update the MethodInstance and notify the edges
function finish(me::InferenceState)
    if me.cached
        toplevel = !isa(me.linfo.def, Method)
        if !toplevel
            min_valid = me.min_valid
            max_valid = me.max_valid
        else
            min_valid = UInt(0)
            max_valid = UInt(0)
        end

        # check if the existing me.linfo metadata is also sufficient to describe the current inference result
        # to decide if it is worth caching it again (which would also clear any generated code)
        already_inferred = !me.linfo.inInference
        if isdefined(me.linfo, :inferred)
            inf = me.linfo.inferred
            if !isa(inf, CodeInfo) || (inf::CodeInfo).inferred
                if min_world(me.linfo) == min_valid && max_world(me.linfo) == max_valid
                    already_inferred = true
                end
            end
        end

        # don't store inferred code if we've decided to interpret this function
        if !already_inferred && invoke_api(me.linfo) != 4
            const_flags = (me.const_ret) << 1 | me.const_api
            if me.const_ret
                if isa(me.bestguess, Const)
                    inferred_const = (me.bestguess::Const).val
                else
                    @assert isconstType(me.bestguess)
                    inferred_const = me.bestguess.parameters[1]
                end
            else
                inferred_const = nothing
            end
            if me.const_api
                # use constant calling convention
                inferred_result = nothing
            else
                inferred_result = me.src
            end

            if !toplevel
                if !me.const_api
                    def = me.linfo.def::Method
                    keeptree = me.optimize &&
                        (me.src.inlineable ||
                         ccall(:jl_isa_compileable_sig, Int32, (Any, Any), me.linfo.specTypes, def) != 0)
                    if keeptree
                        # compress code for non-toplevel thunks
                        inferred_result = ccall(:jl_compress_ast, Any, (Any, Any), def, inferred_result)
                    else
                        inferred_result = nothing
                    end
                end
            end
            cache = ccall(:jl_set_method_inferred, Ref{MethodInstance}, (Any, Any, Any, Any, Int32, UInt, UInt),
                me.linfo, widenconst(me.bestguess), inferred_const, inferred_result,
                const_flags, min_valid, max_valid)
            if cache !== me.linfo
                me.linfo.inInference = false
                me.linfo = cache
                me.result.linfo = cache
            end
        end
        me.linfo.inInference = false
    end

    # finish updating the result struct
    if me.src.inlineable
        me.result.src = me.src # stash a copy of the code (for inlining)
    end
    me.result.result = me.bestguess # record type, and that wip is done and me.linfo can be used as a backedge

    # update all of the callers with real backedges by traversing the temporary list of backedges
    for (i, _) in me.backedges
        add_backedge!(me.linfo, i)
    end

    # finalize and record the linfo result
    me.inferred = true
    nothing
end

function maybe_widen_conditional(vt)
    if isa(vt, Conditional)
        if vt.vtype === Bottom
            vt = Const(false)
        elseif vt.elsetype === Bottom
            vt = Const(true)
        end
    end
    vt
end

function annotate_slot_load!(e::Expr, vtypes::VarTable, sv::InferenceState, undefs::Array{Bool,1})
    head = e.head
    i0 = 1
    e.typ = maybe_widen_conditional(e.typ)
    if is_meta_expr_head(head) || head === :const
        return
    end
    if head === :(=) || head === :method
        i0 = 2
    end
    for i = i0:length(e.args)
        subex = e.args[i]
        if isa(subex, Expr)
            annotate_slot_load!(subex, vtypes, sv, undefs)
        elseif isa(subex, Slot)
            id = slot_id(subex)
            s = vtypes[id]
            vt = maybe_widen_conditional(s.typ)
            if s.undef
                # find used-undef variables
                undefs[id] = true
            end
            #  add type annotations where needed
            if !(sv.src.slottypes[id] ⊑ vt)
                e.args[i] = TypedSlot(id, vt)
            end
        end
    end
end

function record_slot_assign!(sv::InferenceState)
    # look at all assignments to slots
    # and union the set of types stored there
    # to compute a lower bound on the storage required
    states = sv.stmt_types
    body = sv.src.code::Vector{Any}
    slottypes = sv.src.slottypes::Vector{Any}
    for i = 1:length(body)
        expr = body[i]
        st_i = states[i]
        # find all reachable assignments to locals
        if isa(st_i, VarTable) && isa(expr, Expr) && expr.head === :(=)
            lhs = expr.args[1]
            rhs = expr.args[2]
            if isa(lhs, Slot)
                id = slot_id(lhs)
                if isa(rhs, Slot)
                    # exprtype isn't yet computed for slots
                    vt = st_i[slot_id(rhs)].typ
                else
                    vt = exprtype(rhs, sv.src, sv.mod)
                end
                vt = widenconst(vt)
                if vt !== Bottom
                    otherTy = slottypes[id]
                    if otherTy === Bottom
                        slottypes[id] = vt
                    elseif otherTy === Any
                        slottypes[id] = Any
                    else
                        slottypes[id] = tmerge(otherTy, vt)
                    end
                end
            end
        end
    end
end

# annotate types of all symbols in AST
function type_annotate!(sv::InferenceState)
    # remove all unused ssa values
    gt = sv.src.ssavaluetypes
    for j = 1:length(gt)
        if gt[j] === NOT_FOUND
            gt[j] = Union{}
        end
    end

    # compute the required type for each slot
    # to hold all of the items assigned into it
    record_slot_assign!(sv)

    # annotate variables load types
    # remove dead code
    # and compute which variables may be used undef
    src = sv.src
    states = sv.stmt_types
    nargs = sv.nargs
    nslots = length(states[1])
    undefs = fill(false, nslots)
    body = src.code::Array{Any,1}
    nexpr = length(body)
    push!(body, LabelNode(nexpr + 1)) # add a terminal label for tracking phi
    i = 1
    while i <= nexpr
        st_i = states[i]
        expr = body[i]
        if isa(st_i, VarTable)
            # st_i === ()  =>  unreached statement  (see issue #7836)
            if isa(expr, Expr)
                annotate_slot_load!(expr, st_i, sv, undefs)
            elseif isa(expr, Slot)
                id = slot_id(expr)
                if st_i[id].undef
                    # find used-undef variables in statement position
                    undefs[id] = true
                end
            end
        elseif sv.optimize
            if ((isa(expr, Expr) && is_meta_expr(expr)) ||
                 isa(expr, LineNumberNode))
                # keep any lexically scoped expressions
                i += 1
                continue
            end
            # This can create `Expr(:gotoifnot)` with dangling label, which we
            # will clean up by replacing them with the conditions later.
            deleteat!(body, i)
            deleteat!(states, i)
            nexpr -= 1
            continue
        end
        i += 1
    end

    # finish marking used-undef variables
    for j = 1:nslots
        if undefs[j]
            src.slotflags[j] |= SLOT_USEDUNDEF | SLOT_STATICUNDEF
        end
    end

    # The dead code elimination can delete the target of a reachable node. This
    # must mean that the target is unreachable. Later optimization passes will
    # assume that all branches lead to labels that exist, so we must replace
    # the node with the branch condition (which may have side effects).
    labelmap = get_label_map(body)
    for i in 1:length(body)
        expr = body[i]
        if isa(expr, Expr) && expr.head === :gotoifnot
            labelnum = labelmap[expr.args[2]::Int]
            if labelnum === 0
                body[i] = expr.args[1]
            end
        end
    end
    nothing
end

# widen all Const elements in type annotations
function _widen_all_consts!(e::Expr, untypedload::Vector{Bool}, slottypes::Vector{Any})
    e.typ = widenconst(e.typ)
    for i = 1:length(e.args)
        x = e.args[i]
        if isa(x, Expr)
            _widen_all_consts!(x, untypedload, slottypes)
        elseif isa(x, TypedSlot)
            vt = widenconst(x.typ)
            if !(vt === x.typ)
                if slottypes[x.id] ⊑ vt
                    x = SlotNumber(x.id)
                    untypedload[x.id] = true
                else
                    x = TypedSlot(x.id, vt)
                end
                e.args[i] = x
            end
        elseif isa(x, PiNode)
            e.args[i] = PiNode(x.val, widenconst(x.typ))
        elseif isa(x, SlotNumber) && (i != 1 || e.head !== :(=))
            untypedload[x.id] = true
        end
    end
    nothing
end

function widen_all_consts!(src::CodeInfo)
    for i = 1:length(src.ssavaluetypes)
        src.ssavaluetypes[i] = widenconst(src.ssavaluetypes[i])
    end
    for i = 1:length(src.slottypes)
        src.slottypes[i] = widenconst(src.slottypes[i])
    end

    nslots = length(src.slottypes)
    untypedload = fill(false, nslots)
    e = Expr(:body)
    e.args = src.code
    _widen_all_consts!(e, untypedload, src.slottypes)
    for i = 1:nslots
        src.slottypes[i] = widen_slot_type(src.slottypes[i], untypedload[i])
    end
    return src
end

# widen all slots to their optimal storage layout
# we also need to preserve the type for any untyped load of a DataType
# since codegen optimizations of functions like `is` will depend on knowing it
function widen_slot_type(@nospecialize(ty), untypedload::Bool)
    if isa(ty, DataType)
        if untypedload || isbitstype(ty) || isdefined(ty, :instance)
            return ty
        end
    elseif isa(ty, Union)
        ty_a = widen_slot_type(ty.a, false)
        ty_b = widen_slot_type(ty.b, false)
        if ty_a !== Any || ty_b !== Any
            # TODO: better optimized codegen for unions?
            return ty
        end
    elseif isa(ty, UnionAll)
        if untypedload
            return ty
        end
    end
    return Any
end

# replace slots 1:na with argexprs, static params with spvals, and increment
# other slots by offset.
function substitute!(
        @nospecialize(e), na::Int, argexprs::Vector{Any},
        @nospecialize(spsig), spvals::Vector{Any},
        offset::Int, boundscheck::Symbol)
    if isa(e, Slot)
        id = slot_id(e)
        if 1 <= id <= na
            ae = argexprs[id]
            if isa(e, TypedSlot) && isa(ae, Slot)
                return TypedSlot(ae.id, e.typ)
            end
            return ae
        end
        if isa(e, SlotNumber)
            return SlotNumber(id + offset)
        else
            return TypedSlot(id + offset, e.typ)
        end
    end
    if isa(e, NewvarNode)
        return NewvarNode(substitute!(e.slot, na, argexprs, spsig, spvals, offset, boundscheck))
    end
    if isa(e, PhiNode)
        values = Vector{Any}(undef, length(e.values))
        for i = 1:length(values)
            isassigned(e.values, i) || continue
            values[i] = substitute!(e.values[i], na, argexprs, spsig,
                spvals, offset, boundscheck)
        end
        return PhiNode(e.edges, values)
    end
    if isa(e, PiNode)
        return PiNode(substitute!(e.val, na, argexprs, spsig, spvals, offset, boundscheck), e.typ)
    end
    if isa(e, Expr)
        e = e::Expr
        head = e.head
        if head === :static_parameter
            return quoted(spvals[e.args[1]])
        elseif head === :cfunction
            @assert !isa(spsig, UnionAll) || !isempty(spvals)
            if !(e.args[2] isa QuoteNode) # very common no-op
                e.args[2] = substitute!(e.args[2], na, argexprs, spsig, spvals, offset, boundscheck)
            end
            e.args[3] = ccall(:jl_instantiate_type_in_env, Any, (Any, Any, Ptr{Any}), e.args[3], spsig, spvals)
            e.args[4] = svec(Any[
                ccall(:jl_instantiate_type_in_env, Any, (Any, Any, Ptr{Any}), argt, spsig, spvals)
                for argt
                in e.args[4] ]...)
        elseif head === :foreigncall
            @assert !isa(spsig, UnionAll) || !isempty(spvals)
            for i = 1:length(e.args)
                if i == 2
                    e.args[2] = ccall(:jl_instantiate_type_in_env, Any, (Any, Any, Ptr{Any}), e.args[2], spsig, spvals)
                elseif i == 3
                    e.args[3] = svec(Any[
                        ccall(:jl_instantiate_type_in_env, Any, (Any, Any, Ptr{Any}), argt, spsig, spvals)
                        for argt
                        in e.args[3] ]...)
                elseif i == 4
                    @assert isa((e.args[4]::QuoteNode).value, Symbol)
                elseif i == 5
                    @assert isa(e.args[5], Int)
                else
                    e.args[i] = substitute!(e.args[i], na, argexprs, spsig, spvals, offset, boundscheck)
                end
            end
        elseif head === :boundscheck
            if boundscheck === :propagate
                return e
            elseif boundscheck === :off
                return false
            else
                return true
            end
        elseif !is_meta_expr_head(head)
            for i = 1:length(e.args)
                e.args[i] = substitute!(e.args[i], na, argexprs, spsig, spvals, offset, boundscheck)
            end
        end
    end
    return e
end

# whether `f` is pure for inference
function is_pure_intrinsic_infer(f::IntrinsicFunction)
    return !(f === Intrinsics.pointerref || # this one is volatile
             f === Intrinsics.pointerset || # this one is never effect-free
             f === Intrinsics.llvmcall ||   # this one is never effect-free
             f === Intrinsics.arraylen ||   # this one is volatile
             f === Intrinsics.sqrt_llvm ||  # this one may differ at runtime (by a few ulps)
             f === Intrinsics.cglobal)  # cglobal lookup answer changes at runtime
end

# whether `f` is pure for optimizations
function is_pure_intrinsic_optim(f::IntrinsicFunction)
    return !(f === Intrinsics.pointerref || # this one is volatile
             f === Intrinsics.pointerset || # this one is never effect-free
             f === Intrinsics.llvmcall ||   # this one is never effect-free
             f === Intrinsics.arraylen ||   # this one is volatile
             f === Intrinsics.checked_sdiv_int ||  # these may throw errors
             f === Intrinsics.checked_udiv_int ||
             f === Intrinsics.checked_srem_int ||
             f === Intrinsics.checked_urem_int ||
             f === Intrinsics.cglobal)  # cglobal throws an error for symbol-not-found
end

function is_pure_builtin(@nospecialize(f))
    if isa(f, IntrinsicFunction)
        return is_pure_intrinsic_optim(f)
    elseif isa(f, Builtin)
        return (contains_is(_PURE_BUILTINS, f) ||
                contains_is(_PURE_BUILTINS_VOLATILE, f))
    else
        return f === return_type
    end
end

function statement_effect_free(@nospecialize(e), src, mod::Module)
    if isa(e, Expr)
        if e.head === :(=)
            return !isa(e.args[1], GlobalRef) && effect_free(e.args[2], src, mod, false)
        elseif e.head === :gotoifnot
            return effect_free(e.args[1], src, mod, false)
        end
    elseif isa(e, LabelNode) || isa(e, GotoNode)
        return true
    end
    return effect_free(e, src, mod, false)
end

# detect some important side-effect-free calls (allow_volatile=true)
# and some affect-free calls (allow_volatile=false) -- affect_free means the call
# cannot be affected by previous calls, except assignment nodes
function effect_free(@nospecialize(e), src, mod::Module, allow_volatile::Bool)
    if isa(e, GlobalRef)
        return (isdefined(e.mod, e.name) && (allow_volatile || isconst(e.mod, e.name)))
    elseif isa(e, Symbol)
        return allow_volatile
    elseif isa(e, Slot)
        return src.slotflags[slot_id(e)] & SLOT_USEDUNDEF == 0
    elseif isa(e, Expr)
        e = e::Expr
        head = e.head
        if is_meta_expr_head(head)
            return true
        end
        if head === :static_parameter
            # if we aren't certain enough about the type, it might be an UndefVarError at runtime
            return isa(e.typ, Const) || issingletontype(widenconst(e.typ))
        end
        if e.typ === Bottom
            return false
        end
        ea = e.args
        if head === :call
            if is_known_call_p(e, is_pure_builtin, src, mod)
                if !allow_volatile
                    if is_known_call(e, arrayref, src, mod) || is_known_call(e, arraylen, src, mod)
                        return false
                    elseif is_known_call(e, getfield, src, mod)
                        nargs = length(ea)
                        (3 <= nargs <= 4) || return false
                        et = exprtype(e, src, mod)
                        # TODO: check ninitialized
                        if !isa(et, Const) && !isconstType(et)
                            # first argument must be immutable to ensure e is affect_free
                            a = ea[2]
                            typ = unwrap_unionall(widenconst(exprtype(a, src, mod)))
                            if isType(typ)
                                # all fields of subtypes of Type are effect-free
                                # (including the non-inferrable uid field)
                            elseif !isa(typ, DataType) || typ.abstract || (typ.mutable && length(typ.types) > 0)
                                return false
                            end
                        end
                    end
                end
                # fall-through
            elseif is_known_call(e, _apply, src, mod) && length(ea) > 1
                ft = exprtype(ea[2], src, mod)
                if !isa(ft, Const) || (!contains_is(_PURE_BUILTINS, ft.val) &&
                                       ft.val !== Core.sizeof)
                    return false
                end
                # fall-through
            else
                return false
            end
        elseif head === :new
            a = ea[1]
            typ = exprtype(a, src, mod)
            # `Expr(:new)` of unknown type could raise arbitrary TypeError.
            typ, isexact = instanceof_tfunc(typ)
            isexact || return false
            isconcretedispatch(typ) || return false
            typ = typ::DataType
            if !allow_volatile && typ.mutable
                return false
            end
            fieldcount(typ) >= length(ea) - 1 || return false
            for fld_idx in 1:(length(ea) - 1)
                eT = exprtype(ea[fld_idx + 1], src, mod)
                fT = fieldtype(typ, fld_idx)
                eT ⊑ fT || return false
            end
            # fall-through
        elseif head === :return
            # fall-through
        elseif head === :isdefined
            return allow_volatile
        elseif head === :the_exception
            return allow_volatile
        elseif head === :copyast
            return true
        else
            return false
        end
        for a in ea
            if !effect_free(a, src, mod, allow_volatile)
                return false
            end
        end
    elseif isa(e, LabelNode) || isa(e, GotoNode)
        return false
    end
    return true
end

function countunionsplit(atypes)
    nu = 1
    for ti in atypes
        if isa(ti, Union)
            nu *= unionlen(ti::Union)
        end
    end
    return nu
end

## Computing the cost of a function body

# saturating sum (inputs are nonnegative), prevents overflow with typemax(Int) below
plus_saturate(x, y) = max(x, y, x+y)

# known return type
isknowntype(@nospecialize T) = (T == Union{}) || isconcretetype(T)

function statement_cost(ex::Expr, line::Int, src::CodeInfo, mod::Module, params::Params)
    head = ex.head
    if is_meta_expr(ex) || head == :copyast # not sure if copyast is right
        return 0
    end
    argcost = 0
    for a in ex.args
        if a isa Expr
            argcost = plus_saturate(argcost, statement_cost(a, line, src, mod, params))
        end
    end
    if head == :return || head == :(=)
        return argcost
    end
    if head == :call
        extyp = exprtype(ex.args[1], src, mod)
        if isa(extyp, Type)
            return argcost
        end
        if isa(extyp, Const)
            f = (extyp::Const).val
            if isa(f, IntrinsicFunction)
                iidx = Int(reinterpret(Int32, f::IntrinsicFunction)) + 1
                if !isassigned(T_IFUNC_COST, iidx)
                    # unknown/unhandled intrinsic
                    return plus_saturate(argcost, params.inline_nonleaf_penalty)
                end
                return plus_saturate(argcost, T_IFUNC_COST[iidx])
            end
            if isa(f, Builtin)
                # The efficiency of operations like a[i] and s.b
                # depend strongly on whether the result can be
                # inferred, so check ex.typ
                if f == Main.Core.getfield || f == Main.Core.tuple
                    # we might like to penalize non-inferrability, but
                    # tuple iteration/destructuring makes that
                    # impossible
                    # return plus_saturate(argcost, isknowntype(ex.typ) ? 1 : params.inline_nonleaf_penalty)
                    return argcost
                elseif f == Main.Core.arrayref
                    return plus_saturate(argcost, isknowntype(ex.typ) ? 4 : params.inline_nonleaf_penalty)
                end
                fidx = findfirst(x->x===f, T_FFUNC_KEY)
                if fidx === nothing
                    # unknown/unhandled builtin or anonymous function
                    # Use the generic cost of a direct function call
                    return plus_saturate(argcost, 20)
                end
                return plus_saturate(argcost, T_FFUNC_COST[fidx])
            end
        end
        return plus_saturate(argcost, params.inline_nonleaf_penalty)
    elseif head == :foreigncall || head == :invoke
        # Calls whose "return type" is Union{} do not actually return:
        # they are errors. Since these are not part of the typical
        # run-time of the function, we omit them from
        # consideration. This way, non-inlined error branches do not
        # prevent inlining.
        return ex.typ == Union{} ? 0 : plus_saturate(20, argcost)
    elseif head == :llvmcall
        return plus_saturate(10, argcost) # a wild guess at typical cost
    elseif head == :enter
        # try/catch is a couple function calls,
        # but don't inline functions with try/catch
        # since these aren't usually performance-sensitive functions,
        # and llvm is more likely to miscompile them when these functions get large
        return typemax(Int)
    elseif head == :gotoifnot
        target = ex.args[2]::Int
        # loops are generally always expensive
        # but assume that forward jumps are already counted for from
        # summing the cost of the not-taken branch
        return target < line ? plus_saturate(40, argcost) : argcost
    end
    return argcost
end

function inline_worthy(body::Array{Any,1}, src::CodeInfo, mod::Module,
                       params::Params,
                       cost_threshold::Integer=params.inline_cost_threshold)
    bodycost = 0
    for line = 1:length(body)
        stmt = body[line]
        if stmt isa Expr
            thiscost = statement_cost(stmt, line, src, mod, params)::Int
        elseif stmt isa GotoNode
            # loops are generally always expensive
            # but assume that forward jumps are already counted for from
            # summing the cost of the not-taken branch
            thiscost = stmt.label < line ? 40 : 0
        else
            continue
        end
        bodycost = plus_saturate(bodycost, thiscost)
        bodycost == typemax(Int) && return false
    end
    return bodycost <= cost_threshold
end

function inline_worthy(body::Expr, src::CodeInfo, mod::Module, params::Params,
                       cost_threshold::Integer=params.inline_cost_threshold)
    bodycost = statement_cost(body, typemax(Int), src, mod, params)
    return bodycost <= cost_threshold
end

function inline_worthy(@nospecialize(body), src::CodeInfo, mod::Module, params::Params,
                       cost_threshold::Integer=params.inline_cost_threshold)
    newbody = exprtype(body, src, mod)
    !isa(newbody, Expr) && return true
    return inline_worthy(newbody, src, mod, params, cost_threshold)
end

ssavalue_increment(@nospecialize(body), incr) = body
ssavalue_increment(body::SSAValue, incr) = SSAValue(body.id + incr)
function ssavalue_increment(body::Expr, incr)
    if is_meta_expr(body)
        return body
    end
    for i in 1:length(body.args)
        body.args[i] = ssavalue_increment(body.args[i], incr)
    end
    return body
end
ssavalue_increment(body::PiNode, incr) = PiNode(ssavalue_increment(body.val, incr), body.typ)
function ssavalue_increment(body::PhiNode, incr)
    values = Vector{Any}(undef, length(body.values))
    for i = 1:length(values)
        isassigned(body.values, i) || continue
        values[i] = ssavalue_increment(body.values[i], incr)
    end
    return PhiNode(body.edges, values)
end

function mk_tuplecall(args, sv::OptimizationState)
    e = Expr(:call, TOP_TUPLE, args...)
    e.typ = tuple_tfunc(Tuple{Any[widenconst(exprtype(x, sv.src, sv.mod)) for x in args]...})
    return e
end

function add_slot!(src::CodeInfo, @nospecialize(typ), is_sa::Bool, name::Symbol=COMPILER_TEMP_SYM)
    @assert !isa(typ, Const) && !isa(typ, Conditional)
    id = length(src.slotnames) + 1
    push!(src.slotnames, name)
    push!(src.slottypes, typ)
    push!(src.slotflags, is_sa * SLOT_ASSIGNEDONCE)
    return SlotNumber(id)
end

function is_known_call(e::Expr, @nospecialize(func), src, mod::Module)
    if e.head !== :call
        return false
    end
    f = exprtype(e.args[1], src, mod)
    return isa(f, Const) && f.val === func
end

function is_known_call_p(e::Expr, @nospecialize(pred), src, mod::Module)
    if e.head !== :call
        return false
    end
    f = exprtype(e.args[1], src, mod)
    return (isa(f, Const) && pred(f.val)) || (isType(f) && pred(f.parameters[1]))
end

# fix label numbers to always equal the statement index of the label
function reindex_labels!(body::Vector{Any})
    mapping = get_label_map(body)
    for i = 1:length(body)
        el = body[i]
        # For goto and enter, the statement and the target has to be
        # both reachable or both not.
        if isa(el, LabelNode)
            labelnum = mapping[el.label]
            @assert labelnum !== 0
            body[i] = LabelNode(labelnum)
        elseif isa(el, GotoNode)
            labelnum = mapping[el.label]
            @assert labelnum !== 0
            body[i] = GotoNode(labelnum)
        elseif isa(el, Expr)
            if el.head === :gotoifnot
                labelnum = mapping[el.args[2]::Int]
                @assert labelnum !== 0
                el.args[2] = labelnum
            elseif el.head === :enter
                labelnum = mapping[el.args[1]::Int]
                @assert labelnum !== 0
                el.args[1] = labelnum
            elseif el.head === :(=)
                if isa(el.args[2], PhiNode)
                    edges = Any[mapping[edge::Int + 1] - 1 for edge in el.args[2].edges]
                    @assert all(x->x >= 0, edges)
                    el.args[2] = PhiNode(convert(Vector{Any}, edges), el.args[2].values)
                end
            end
        end
    end
    if body[end] isa LabelNode
        # we usually have a trailing label for the purposes of phi numbering
        # this can now be deleted also if unused
        if label_counter(body, false) < length(body)
            pop!(body)
        end
    end
end

function reindex_labels!(sv::OptimizationState)
    reindex_labels!(sv.src.code)
end

function return_type(@nospecialize(f), @nospecialize(t))
    params = Params(ccall(:jl_get_tls_world_age, UInt, ()))
    rt = Union{}
    if isa(f, Builtin)
        rt = builtin_tfunction(f, Any[t.parameters...], nothing, params)
        if isa(rt, TypeVar)
            rt = rt.ub
        else
            rt = widenconst(rt)
        end
    else
        for m in _methods(f, t, -1, params.world)
            ty = typeinf_type(m[3], m[1], m[2], true, params)
            ty === nothing && return Any
            rt = tmerge(rt, ty)
            rt === Any && break
        end
    end
    return rt
end

max_stars_repo_name: ninjin/julia

max_issues_repo_name: ninjin/julia

max_forks_repo_name: ninjin/julia


text:
using Flux.Data.MNIST, LIBSVM, Plots

logFilePath = "../data/svmlog.txt"
nTrain = 10^4

trainImgs   = MNIST.images()[1:nTrain]
trainLabels = MNIST.labels()[1:nTrain]
trainData = hcat([vcat(float.(trainImgs[i])...) for i in 1:nTrain]...)

testImgs = MNIST.images(:test)
testLabels = MNIST.labels(:test)
nTest = length(testImgs)
testData = hcat([vcat(float.(testImgs[i])...) for i in 1:nTest]...)

@info "Training model with verbose output to $logFilePath."
@time begin
    sOut = stdout
    logF = open(logFilePath, "w")
    redirect_stdout(logF)
    model = svmtrain(trainData, trainLabels,
                    kernel = Kernel.Linear, verbose=true)
    close(logF)
    redirect_stdout(sOut)
    @info "Training complete."
end

predicted_labels, _ = svmpredict(model, testData)

accuracy = sum(predicted_labels .== testLabels)/nTest
println("Prediction accuracy (measured on test set of size $nTest): ", accuracy)

ext: jl

max_stars_repo_name: Yoshinobu-Ishizaki/StatsWithJuliaBook

max_issues_repo_name: Yoshinobu-Ishizaki/StatsWithJuliaBook

max_forks_repo_name: Yoshinobu-Ishizaki/StatsWithJuliaBook


text:
import Base: show, showcompact, similar, convert, _reshape, map!, copy!, map, copy, showarray

# Dense GPU Array
abstract type GPUArray{T, N} <: DenseArray{T, N} end

# Sampler type that acts like a texture/image and allows interpolated access
abstract type Sampler{T, N} <: DenseArray{T, N} end

const GPUVector{T} = GPUArray{T, 1}
const GPUMatrix{T} = GPUArray{T, 2}
const GPUVecOrMat{T} = Union{GPUArray{T, 1}, GPUArray{T, 2}}

# GPU Local Memory
struct LocalMemory{T} <: GPUArray{T, 1}
    size::Int
    LocalMemory{T}(x::Integer) where T = new{T}(x)
end

#=
AbstractArray interface
=#

function showarray(io::IO, A::GPUArray, repr::Bool)
    print(io, "GPU: ")
    showarray(io, Array(A), repr)
end
function showcompact(io::IO, mt::MIME"text/plain", A::GPUArray)
    showcompact(io, mt, Array(A))
end

############################################
# serialization

const BaseSerializer = if isdefined(Base, :AbstractSerializer)
    Base.AbstractSerializer
elseif isdefined(Base, :SerializationState)
    Base.SerializationState
else
    error("No Serialization type found. Probably unsupported Julia version")
end

function Base.serialize(s::BaseSerializer, t::T) where T <: GPUArray
    Base.serialize_type(s, T)
    serialize(s, Array(t))
end
function Base.deserialize(s::BaseSerializer, ::Type{T}) where T <: GPUArray
    A = deserialize(s)
    T(A)
end

@inline unpack_buffer(x) = x
@inline unpack_buffer(x::GPUArray) = pointer(x)
@inline unpack_buffer(x::Ref{<: GPUArray}) = unpack_buffer(x[])

function to_cartesian(A, indices::Tuple)
    start = CartesianIndex(ntuple(length(indices)) do i
        val = indices[i]
        isa(val, Integer) && return val
        isa(val, UnitRange) && return first(val)
        isa(val, Colon) && return 1
        isa(val, Base.Slice{Base.OneTo{Int}}) && return 1
        error("GPU indexing only defined for integers or unit ranges. Found: $val")
    end)
    stop = CartesianIndex(ntuple(length(indices)) do i
        val = indices[i]
        isa(val, Integer) && return val
        isa(val, UnitRange) && return last(val)
        isa(val, Colon) && return size(A, i)
        isa(val, Base.Slice{Base.OneTo{Int}}) && return size(A, i)
        error("GPU indexing only defined for integers or unit ranges. Found: $val")
    end)
    CartesianRange(start, stop)
end

crange(start, stop) = CartesianRange(CartesianIndex(start), CartesianIndex(stop))

for (D, S) in ((GPUArray, AbstractArray), (AbstractArray, GPUArray), (GPUArray, GPUArray))
    @eval begin
        function copy!(
                dest::$D, doffset::Integer,
                src::$S, soffset::Integer, amount::Integer
            )
            copy!(
                unpack_buffer(dest), doffset,
                unpack_buffer(src), soffset, amount
            )
        end
        function copy!(
                dest::$D{T, N}, rdest::NTuple{N, UnitRange},
                src::$S{T, N}, ssrc::NTuple{N, UnitRange},
            ) where {T, N}
            drange = crange(start.(rdest), last.(rdest))
            srange = crange(start.(ssrc), last.(ssrc))
            copy!(dest, drange, src, srange)
        end
        function copy!(
                dest::$D{T}, d_range::CartesianRange{CartesianIndex{1}},
                src::$S{T}, s_range::CartesianRange{CartesianIndex{1}},
            ) where T
            amount = length(d_range)
            if length(s_range) != amount
                throw(ArgumentError("Copy range needs same length. Found: dest: $amount, src: $(length(s_range))"))
            end
            amount == 0 && return dest
            d_offset = first(d_range)[1]
            s_offset = first(s_range)[1]
            copy!(dest, d_offset, src, s_offset, amount)
        end
        function copy!(
                dest::$D{T, N}, src::$S{T, N}
            ) where {T, N}
            len = length(src)
            len == 0 && return dest
            if length(dest) > len
                throw(BoundsError(dest, length(src)))
            end
            copy!(dest, 1, src, 1, len)
        end
    end
end

function copy_kernel!(state, dest, dest_offsets, src, src_offsets, shape, shape_dest, shape_source, length)
    i = linear_index(state)
    if i <= length
        # TODO can this be done faster and smarter?
        idx = gpu_ind2sub(shape, i)
        dest_idx = gpu_sub2ind(shape_dest, idx .+ dest_offsets)
        src_idx = gpu_sub2ind(shape_source, idx .+ src_offsets)
        @inbounds dest[dest_idx] = src[src_idx]
    end
    return
end

function copy!(
        dest::GPUArray{T, N}, destcrange::CartesianRange{CartesianIndex{N}},
        src::GPUArray{T, N}, srccrange::CartesianRange{CartesianIndex{N}}
    ) where {T, N}
    shape = size(destcrange)
    if shape != size(srccrange)
        throw(DimensionMismatch("Ranges don't match their size. Found: $shape, $(size(srccrange))"))
    end
    len = length(destcrange)
    dest_offsets = UInt32.(destcrange.start.I .- 1)
    src_offsets = UInt32.(srccrange.start.I .- 1)
    ui_shape = UInt32.(shape)
    gpu_call(
        copy_kernel!, dest,
        (dest, dest_offsets, src, src_offsets, ui_shape, UInt32.(size(dest)), UInt32.(size(src)), UInt32(len)),
        len
    )
    dest
end

function copy!(
        dest::GPUArray{T, N}, destcrange::CartesianRange{CartesianIndex{N}},
        src::AbstractArray{T, N}, srccrange::CartesianRange{CartesianIndex{N}}
    ) where {T, N}
    # Is this efficient? Maybe!
    # TODO: compare to a pure intrinsic copy implementation!
    # this would mean looping over linear sections of memory and
    # use copy!(dest, offset::Integer, buffer(src), offset::Integer, amout::Integer)
    src_gpu = typeof(dest)(map(idx-> src[idx], srccrange))
    nrange = CartesianRange(one(CartesianIndex{N}), CartesianIndex(size(src_gpu)))
    copy!(dest, destcrange, src_gpu, nrange)
    dest
end

function copy!(
        dest::AbstractArray{T, N}, destcrange::CartesianRange{CartesianIndex{N}},
        src::GPUArray{T, N}, srccrange::CartesianRange{CartesianIndex{N}}
    ) where {T, N}
    # Is this efficient? Maybe!
    dest_gpu = similar(src, size(destcrange))
    nrange = CartesianRange(one(CartesianIndex{N}), CartesianIndex(size(dest_gpu)))
    copy!(dest_gpu, nrange, src, srccrange)
    copy!(dest, destcrange, Array(dest_gpu), nrange)
    dest
end

copy(x::GPUArray) = identity.(x)

#=
reinterpret taken from julia base/array.jl
Copyright (c) 2009-2016: Jeff Bezanson, Stefan Karpinski, Viral B. Shah, and other contributors:

https://github.com/JuliaLang/julia/contributors

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
=#
import Base.reinterpret

"""
Unsafe reinterpret for backends to overload.
This makes it easier to do checks just on the high level.
"""
function unsafe_reinterpret end

function reinterpret(::Type{T}, a::GPUArray{S,1}) where T where S
    nel = Int(div(length(a)*sizeof(S),sizeof(T)))
    # TODO: maybe check that remainder is zero?
    return reinterpret(T, a, (nel,))
end

function reinterpret(::Type{T}, a::GPUArray{S}) where T where S
    if sizeof(S) != sizeof(T)
        throw(ArgumentError("result shape not specified"))
    end
    reinterpret(T, a, size(a))
end

function reinterpret(::Type{T}, a::GPUArray{S}, dims::NTuple{N,Int}) where T where S where N
    if !isbits(T)
        throw(ArgumentError("cannot reinterpret Array{$(S)} to ::Type{Array{$(T)}}, type $(T) is not a bits type"))
    end
    if !isbits(S)
        throw(ArgumentError("cannot reinterpret Array{$(S)} to ::Type{Array{$(T)}}, type $(S) is not a bits type"))
    end
    nel = div(length(a)*sizeof(S),sizeof(T))
    if prod(dims) != nel
        throw(DimensionMismatch("new dimensions $(dims) must be consistent with array size $(nel)"))
    end
    unsafe_reinterpret(T, a, dims)
end

function _reshape(A::GPUArray{T}, dims::Dims) where T
    n = Base._length(A)
    prod(dims) == n || throw(DimensionMismatch("parent has $n elements, which is incompatible with size $dims"))
    return unsafe_reinterpret(T, A, dims)
end
#ambig
function _reshape(A::GPUArray{T, 1}, dims::Tuple{Int}) where T
    n = Base._length(A)
    prod(dims) == n || throw(DimensionMismatch("parent has $n elements, which is incompatible with size $dims"))
    return unsafe_reinterpret(T, A, dims)
end


text:
module GeneralizedChartparsing

const LOGSPACE_THRESHOLD = 0.0001

# MAX_POP_NUMBER is length of unary chain plus two for
# (1) creating the item and (2) inserting it into the chart

# const MAX_POP_NUMBER = 4
const MAX_POP_NUMBER = 4

####################
### Dependencies ###
####################
using ForceImport

@force using Base # must be concretized
# importall Base.Collections

@force using DataStructures

using Missings
using LogProbs
# using Base.Collections
using AutoHashEquals
# using DataFrames
# using Gadfly
using LightGraphs
using Setfield

##################################
### Exported methods and types ###
##################################

# semi-rings
export LogProb,
       Product

# parser methods
export run_chartparser,
       score,
       prob,
       inside,
       outside,
       best_tree,
       sample_tree,
       is_complete,
       heads,
       get_edge,
       get_cons,
       calculate_outside_probs_and_expected_rule_usages!

# evaluation methods
export single_fold_cross_validation,
       single_fold_cross_validation_baseline,
       parsable_trees,
       model_evaluation

# WSJ methods
# export read_treebank_grammar,
#        compute_treebank_scores,
#        treebank_goldstandard_scores

# grammar mathods
export Grammar,
       State,
       train!,
       dependent_components,
       set_params!,
       one_update_step_hyperparameters!,
       learn_hyperparameters!,
       MinimalistGrammar,
       LexicalItem

# jazz grammar methods
# export make_jazz_grammar,
#        make_plain_PCFG_jazz_grammar,
#        make_terminals,
#        pitch_class,
#        Terminal,
#        make_parsable_trees

# Tree Class types and methods
export TreeNode,
       leaf_data,
       dependency_matrix,
       boolean_dependency_matrix,
       leafs

export category_type,
       terminal_type,
       category_rule_type,
       terminal_rule_type,
       score_type,
       state_type,
       startstate,
       startsymbols,
       completions,
       score,
       prob,
       is_possible_transition,
       transition,
       isfinal

# vb_update
# export expected_lexitem_counts,
#        expected_lexitem_counts_by_category,
#        expected_lexitem_counts_by_sentence,
#        makeLexicon_andCorpus,
#        makeLexicon_test,
#        variational_inference,
#        variational_inference_full_corpus_parallel,
#        variational_inference_full_corpus,
#        load_lexicon,
#        sample_counts

# # UD corpus
# export read_corpus,
#        read_sentences,
#        get_sentences,
#        CoNLLUCorpus,
#        CoNLLUSentence,
#        CoNLLUWord,
#        evaluate_dependencies,
#        make_lexicon_from_corpus_all_combinations,
#        unkify!,
#        parse_given_dependencies,
#        kullback_leibler,
#        uptorank,
#        compare_compactness

# lexicon.jl
# export make_feature_list,
#        remove_duplicates!,
#        remove_vacuous_nullheads!

# evaluation
# export precision,
#        recall,
#        parse_and_evaluate_corpus,
#        parse_and_show_results,
#        vblearn_parse_and_show_results

# dependencies
export head,
       dependents,
       dependencies,
       graph_to_dependency_matrix,
       binarize_dependency_matrix,
       haspath,
       has_crossing_dependencies,
       has_noncontiguous_dependencies,
       tikzdependency

# Forward sampler for MG
# export SampleGrammar,
#        SampleDerivation,
#        find_selectors,
#        treeRootC,
#        probDerivation,
#        samplerMGderivation,
#        getsent_fromderiv,
#        sample_corpus,
#        corpus_without_duplicates,
#        write_probs,
#        write_sentence_probs,
#        write_sentence_probs_ranked

##################
### Load files ###
##################

include(joinpath("tools", "code_tools.jl"))

include(joinpath("semi_rings", "ProductSemiRings.jl"))

include(joinpath("tools", "Trees.jl"))
using .Trees
include(joinpath("tools", "tree_to_dependency_matrix.jl"))
include(joinpath("tools", "tree_evaluation.jl"))

# include(joinpath("grammars", "UrnModels.jl"))
include(joinpath("grammars", "CompoundDistributions.jl"))
#using GeneralizedChartparsing.CompoundDistributions
@force using .CompoundDistributions # Grammars.jl uses logscore
include(joinpath("grammars", "Grammars.jl"))
# include(joinpath("grammars", "parameter_learning.jl"))

# include(joinpath("minimalist", "MinimalistGrammar.jl"))
# include(joinpath("minimalist", "counts.jl"))
# include(joinpath("minimalist", "lexicon.jl"))
# include(joinpath("minimalist", "dependencies.jl"))
# include(joinpath("minimalist", "forwardsampler_MG.jl"))
using Nullables
include(joinpath("parser", "parser_types.jl"))
include(joinpath("parser", "parser_methods.jl"))
#
# include(joinpath("jazz_applications", "music_data_types.jl"))
# include(joinpath("jazz_applications", "JazzGrammars.jl"))
# include(joinpath("jazz_applications", "single_fold_cross_validation.jl"))
# include(joinpath("jazz_applications", "boxplot.jl"))
# include(joinpath("jazz_applications", "model_evaluation.jl"))
#
# include(joinpath("WSJ", "WSJ_methods.jl"))
#
# include(joinpath("tools", "corpus.jl"))
# include(joinpath("minimalist", "interface_parser_vb_update.jl"))

end # module


text:
module LaxZonedDateTimes

# Prototype of a new type that is a more context aware Nullable{ZonedDateTime}

using Dates: AbstractDateTime, DatePeriod, DateTime, Dates, Millisecond, Period, TimePeriod
using Intervals
using TimeZones
using TimeZones: Local, UTC, interpret, timezone

export
    LaxZonedDateTime, ZDT,
    # accessors.jl
    isvalid, isinvalid, isambiguous, isnonexistent,
    hour, minute, second, millisecond

abstract type InvalidTimeZone <: TimeZone end

struct NonExistent <: InvalidTimeZone end

struct Ambiguous <: InvalidTimeZone end

# Seems like we want to keep the UTC datetime even if it doesn't align with our local
# datetime so that we can still do UTC based calculations.

struct LaxZonedDateTime <: AbstractDateTime
    local_datetime::DateTime
    timezone::TimeZone
    zone::Union{FixedTimeZone,InvalidTimeZone}
    representable::Bool

    function LaxZonedDateTime(dt, tz, zone, rep)
        utc = TimeZone("UTC")
        return rep ? new(dt, tz, zone, rep) : new(DateTime(0), utc, utc, false)
    end
end

function LaxZonedDateTime()
    utc = TimeZone("UTC")
    LaxZonedDateTime(DateTime(0), utc, utc, false)
end

function LaxZonedDateTime(zdt::ZonedDateTime)
    LaxZonedDateTime(DateTime(zdt), timezone(zdt), zdt.zone, true)
end

function LaxZonedDateTime(dt::DateTime, tz::TimeZone, zone)
    LaxZonedDateTime(dt, tz, zone, true)
end

function LaxZonedDateTime(local_dt::DateTime, tz::FixedTimeZone)
    return LaxZonedDateTime(ZonedDateTime(local_dt, tz))
end

function LaxZonedDateTime(local_dt::DateTime, tz::VariableTimeZone)
    possible = interpret(local_dt, tz, Local)

    num = length(possible)
    if num == 1
        lzdt = LaxZonedDateTime(first(possible))
    elseif num == 0
        lzdt = LaxZonedDateTime(local_dt, tz, NonExistent())
    else
        lzdt = LaxZonedDateTime(local_dt, tz, Ambiguous())
    end

    return lzdt
end

# We need to define the behaviour for constructing an empty Interval of LaxZonedDateTimes
function Intervals.Interval{T}() where T <: LaxZonedDateTime
    return Interval{T,Open,Open}(
        T(DateTime(0), tz"UTC"),
        T(DateTime(0), tz"UTC"),
    )
end

# Allows for the creation of valid `AnchoredInterval`s without having to compute the
# non-anchor endpoint.
# Note: `Intervals._isfinite` was introduced in Intervals 1.3
if isdefined(Intervals, :_isfinite)
    Intervals._isfinite(x::LaxZonedDateTime) = isvalid(x)
end

function Base.:(==)(x::LaxZonedDateTime, y::LaxZonedDateTime)
    if isvalid(x) && isvalid(y)
        return DateTime(x, UTC) == DateTime(y, UTC)
    else
        return (
            x.representable == y.representable == true &&
            x.local_datetime == y.local_datetime &&
            x.timezone == y.timezone &&
            x.zone == y.zone
        )
    end
end

function Base.:(==)(x::LaxZonedDateTime, y::ZonedDateTime)
    if isvalid(x)
        return DateTime(x, UTC) == DateTime(y, UTC)
    else
        return false
    end
end

Base.:(==)(x::ZonedDateTime, y::LaxZonedDateTime) = y == x

# Note: `hash` and `isequal` assume that the "zone" of a ZonedDateTime is not being set
# incorrectly.

function Base.isequal(x::LaxZonedDateTime, y::LaxZonedDateTime)
    if isvalid(x) && isvalid(y)
        return isequal(DateTime(x, UTC), DateTime(y, UTC))
    else
        return (
            isequal(x.local_datetime, y.local_datetime) &&
            isequal(x.timezone, y.timezone) &&
            isequal(x.zone, y.zone) &&
            isequal(x.representable, y.representable)
        )
    end
end

function Base.isequal(x::LaxZonedDateTime, y::ZonedDateTime)
    isvalid(x) ? isequal(DateTime(x, UTC), DateTime(y, UTC)) : false
end

Base.isequal(x::ZonedDateTime, y::LaxZonedDateTime) = isequal(y, x)

# Valid LaxZonedDateTimes should hash to the same value as the equivalent ZonedDateTime
# All invalid or unrepresentable LaxZonedDateTimes should always hash to a different value.
function Base.hash(lzdt::LaxZonedDateTime, h::UInt)
    if isvalid(lzdt)
        h = hash(:utc_instant, h)
        h = hash(DateTime(lzdt, UTC), h)
    else
        h = hash(:invalid_utc_instant, h)
        h = hash(lzdt.local_datetime, h)
    end

    return h
end

function Base.:(-)(x::LaxZonedDateTime, y::LaxZonedDateTime)
    if isvalid(x) && isvalid(y)
        DateTime(x, UTC) - DateTime(y, UTC)
    else
        nothing
    end
end

function Base.:(-)(x::LaxZonedDateTime, y::ZonedDateTime)
    if isvalid(x)
        DateTime(x, UTC) - DateTime(y, UTC)
    else
        nothing
    end
end

Base.:(-)(x::ZonedDateTime, y::LaxZonedDateTime) = y - x

function Base.:(+)(lzdt::LaxZonedDateTime, p::DatePeriod)
    !isrepresentable(lzdt) && (return lzdt)
    isa(lzdt.timezone, FixedTimeZone) && (return LaxZonedDateTime(ZonedDateTime(lzdt) + p))

    local_dt, tz = DateTime(lzdt), timezone(lzdt)
    local_dt = local_dt + p
    possible = interpret(local_dt, tz, Local)

    num = length(possible)
    if num == 1
        return LaxZonedDateTime(first(possible))
    elseif num == 0
        return LaxZonedDateTime(local_dt, tz, NonExistent())
    else
        return LaxZonedDateTime(local_dt, tz, Ambiguous())
    end
end

function Base.:(+)(lzdt::LaxZonedDateTime, p::TimePeriod)
    !isrepresentable(lzdt) && (return lzdt)
    isa(lzdt.timezone, FixedTimeZone) && (return LaxZonedDateTime(ZonedDateTime(lzdt) + p))
    isa(lzdt.zone, InvalidTimeZone) && (return LaxZonedDateTime())

    utc_dt, tz = DateTime(lzdt, UTC), timezone(lzdt)
    possible = interpret(utc_dt + p, tz, UTC)
    return LaxZonedDateTime(first(possible))
end

function Base.:(-)(lzdt::LaxZonedDateTime, p::Period)
    return lzdt + (-p)
end

function Base.show(io::IO, lzdt::LaxZonedDateTime)
    if isrepresentable(lzdt)
        print(io, DateTime(lzdt))

        if isa(lzdt.zone, NonExistent)
            print(io, "-DNE")
        elseif isa(lzdt.zone, Ambiguous)
            print(io, "-AMB")
        else
            print(io, lzdt.zone.offset)
        end
    else
        print(io, "unrepresentable")
    end
end

Base.promote_rule(::Type{LaxZonedDateTime},::Type{ZonedDateTime}) = LaxZonedDateTime
Base.convert(::Type{LaxZonedDateTime}, x::ZonedDateTime) = LaxZonedDateTime(x)
Base.convert(::Type{ZonedDateTime}, x::LaxZonedDateTime) = ZonedDateTime(x)

function Base.isless(a::LaxZonedDateTime, b::LaxZonedDateTime)
    if !isrepresentable(a) || !isrepresentable(b)
        return false
    end

    # Need to compare using UTC when the zones are fixed and don't have the same offset.
    if a.zone != b.zone && isa(a.zone, FixedTimeZone) && isa(b.zone, FixedTimeZone)
        return isless(DateTime(a, UTC), DateTime(b, UTC))
    else
        return isless(DateTime(a), DateTime(b))
    end
end

Base.:(<=)(a::LaxZonedDateTime, b::LaxZonedDateTime) = !(a > b)

"""
    ZonedDateTime(lzdt::LaxZonedDateTime, resolve_by::Symbol=:throw) -> ZonedDateTime

Convert a `LaxZonedDateTime` to a [`ZonedDateTime`](@ref). If an [`Ambiguous`](@ref) or
[`NonExistent`](@ref) time is given the conversion will throw the appropriate error.

To force conversion, the `resolve_by` positional argument should be either `:first` or `:last`.
For [`Ambiguous`](@ref) times, this will return the same `DateTime` but resolved in the timezone
just before (first) or just after (last) the transition. For [`NonExistent`](@ref) times, this
will return the closest `DateTime` instant in the timezone which is just before (first) or just
after (last) the transition gap.
"""
function TimeZones.ZonedDateTime(lzdt::LaxZonedDateTime, resolve_by::Symbol=:throw)
    if !isrepresentable(lzdt)
        throw(ArgumentError("Unable to determine UTC datetime from an unrepresentable LaxZonedDateTime"))
    end

    if isa(lzdt.zone, FixedTimeZone)
        utc_dt = lzdt.local_datetime - lzdt.zone.offset
        return ZonedDateTime(utc_dt, timezone(lzdt); from_utc=true)
    end

    local_dt, tz = DateTime(lzdt), timezone(lzdt)

    if isambiguous(lzdt)
        possible = interpret(local_dt, tz, Local)

        if resolve_by == :first
            return first(possible)
        elseif resolve_by == :last
            return last(possible)
        else
            throw(AmbiguousTimeError(local_dt, tz))
        end
    elseif isnonexistent(lzdt)
        zdts = TimeZones.shift_gap(local_dt, tz)

        if resolve_by == :first
            return first(zdts)
        elseif resolve_by == :last
            return last(zdts)
        else
            throw(NonExistentTimeError(local_dt, tz))
        end
    else
        return ZonedDateTime(local_dt, tz)
    end
end

const ZDT = Union{ZonedDateTime, LaxZonedDateTime}

include("accessors.jl")
include("conversions.jl")
include("rounding.jl")
include("ranges.jl")
include("deprecated.jl")

end


text:
using HaloMF

# We use some functions in https://github.com/komatsu5147/MatterPower.jl
import MatterPower

# %% Specify a redshift
redshift = 0

# %% Define a function to return a linear matter power spectrum (in units of Mpc^3/h^3)
# as a function of the comoving wavenumber, kovh, in units of h/Mpc.
# Here is an example using Einstein & Hu's analytical transfer function in MatterPower.jl

# Cosmological parameters
As, ns, kpivot = 2.097e-9, 0.9652, 0.05
Ωm, ΩΛ, Ωb = 0.315, 0.685, 0.049
Ωk = 1 - Ωm - ΩΛ
h0 = 0.674
ωm, fb = Ωm * h0^2, Ωb / Ωm

# Tabulate linear growth factor as a function of scale factor, a
sol = MatterPower.setup_growth(Ωm, ΩΛ)
a = 1 / (1 + redshift)
D1 = sol(a)[1]

pk(kovh) =
   D1^2 *
   As * (kovh * h0 / kpivot)^(ns - 1) *
   (2 * kovh^2 * 2998^2 / 5 / Ωm)^2 *
   MatterPower.t_nowiggle(kovh * h0, ωm, fb)^2 *
   2 * π^2 / kovh^3

# %% Alternatively you may read in pre-computed data and define a spline function
# using Dierckx
# pk = Spline1D(tabulated_kovh, tabulated_power_spectrum)

# %% Spefify a halo mass, Mh, in units of M⊙/h (M⊙ is the mass of Sun)
Mh = 1e14

# Compute the corresponding radius, Rh, in units of Mpc/h
# ρc is the present-day critical density of the Universe in units of h^2 M⊙/Mpc^3
ρc = 2.775e11
Rh = cbrt(Mh * 3 / 4π / ρc / Ωm)

# %% Compute variance of the mass density fluctuation and its derivative
# Here is an example using functions in MatterPower.jl
σ2 = MatterPower.sigma2(pk, Rh)
dlnσ2dlnRh = Rh * MatterPower.dsigma2dR(pk, Rh) / σ2

# %% Finally, the mass function per logarithmic mass interval, dn/dlnMh, in units of h^3 Mpc^-3
# Specify the desired value of the overdensity
Δm = 200
z = redshift
lnν = 2 * log(1.6865) - log(σ2)
MF = tinker08MF(lnν, z, Δm)
dndlnMh = -dlnσ2dlnRh * MF / 4π / Rh^3


text:
module WECOrules

using DataFrames
using Statistics
using DataStructures
using Requires

export weco, wecorules, shewhart

function __init__()
    # defines the shewhart method to plot the data
    @require Gadfly = "c91e804a-d5a3-530f-b6f0-dfbca275c004" include("gadfly.jl")
end

"""
    function weco(
        df::AbstractDataFrame, # DataFrame containing columns :Date & :Value (or below)
        nominal::Real, # Nominal value for :Value column
        onesigma::Real; # Nominal 1σ variation in :Value column
        timestamp::Union{Symbol,AbstractString}=:Date, # Alternative to :Date
        value::Union{Symbol,AbstractString}=:Value, # Alternative to :Value
        result::Union{Missing,Function}=missing,
        summary::Bool = false # Add a summary column
    )::DataFrame

Evaluates the Western Electric Company rules against each row in a `DataFrame`.  The 8 rules are:

1) A single data point more than three standard deviations from the nominal value.
2) Nine sequential data points above (or below) the nominal value.
3) Six sequential data points monotonically increasing (decreasing).
4) Sixteen sequential data points alternating up and down.
5) Two of three data points above (or below) that are over two standard deviations from the nominal value.
6) Four of five data points above (or below) that are more than one standard deviation from the nominal value.
7) Fifteen data points within one standard deviation of the nominal value.
8) Eight sequential data points that are more than one standard deviation from the nominal value.
"""
function weco(
    df::AbstractDataFrame, # DataFrame containing columns :Date & :Value (or below)
    nominal::Real, # Nominal value for :Value column
    onesigma::Real; # Nominal 1σ variation in :Value column
    timestamp::Union{Symbol,AbstractString}=:Date, # Alternative to :Date
    value::Union{Symbol,AbstractString}=:Value, # Alternative to :Value
    result::Union{Missing,Function}=missing,
    summary::Bool=false # Add a final summary column
)::DataFrame
    same(cb) = all(cb) || (!any(cb))
    res = sort(df, timestamp)
    # Some of the rules can be computed using stateless methods (only the current value), others require state based on previous values
    # 1) A single data point more than three standard deviations from the nominal value.
    begin
        rule1 = map(r-> abs(r[value]-nominal)<3*onesigma, eachrow(res))
        insertcols!(res, :Rule1 => rule1)
    end
    # 2) Nine sequential data points above (or below) the nominal value.
    begin
        cb2 = CircularBuffer{Bool}(9) # true=above, false=below
        rule2 = map(eachrow(res)) do r
            push!(cb2, r[value] > nominal)
            isfull(cb2) ? !same(cb2) : missing
        end
        insertcols!(res, :Rule2 => rule2)
    end
    # 3) Six sequential data points monotonically increasing (decreasing).
    begin
        cb3, prev = CircularBuffer{Int}(6), missing
        rule3 = map(eachrow(res)) do r
            (!ismissing(prev)) && push!(cb3, r[value] < prev ? -1 : (r[value] > prev ? +1 : 0))
            prev = r[value]
            isfull(cb3) ? !(sum(cb3)==6 || sum(cb3)==-6) : missing
        end
        insertcols!(res, :Rule3 => rule3)
    end
    # 4) Sixteen sequential data points alternating up and down.
    begin
        cb4, prev = CircularBuffer{Bool}(15), missing
        alternating(cb) = all(i->cb[i] ≠ cb[i-1], 2:length(cb))
        rule4 = map(eachrow(res)) do r
            (!ismissing(prev)) && push!(cb4, r[value] - prev > 0)
            prev = r[value]
            isfull(cb4) ? !alternating(cb4) : missing
        end
        insertcols!(res, :Rule4 => rule4)
    end
    # 5) Two of three data points above (or below) that are over two standard deviations from the nominal value.
    begin
        cb5p, cb5n = CircularBuffer{Bool}(3), CircularBuffer{Bool}(3)
        rule5 = map(eachrow(res)) do r
            push!(cb5p, r[value]-nominal > 2*onesigma)
            push!(cb5n, r[value]-nominal < -2*onesigma)
            # Don't call point if it is in tolerance but follows two out-of-tolerance
            outside = abs(r[value]-nominal) > 2*onesigma
            isfull(cb5p) ? !(outside && (count(cb5p) >= 2 || count(cb5n) >= 2)) : missing
        end
        insertcols!(res, :Rule5 => rule5)
    end
    # 6) Four of five data points above (or below) that are more than one standard deviation from the nominal value.
    begin
        cb6p, cb6n = CircularBuffer{Bool}(5), CircularBuffer{Bool}(5)
        rule6 = map(eachrow(res)) do r
            push!(cb6p, r[value]-nominal > onesigma)
            push!(cb6n, r[value]-nominal < -onesigma)
            # Don't call point if it is intolerance but follows four out-of-tolerance
            outside = abs(r[value]-nominal) > onesigma
            isfull(cb6p) ? !(outside && (count(cb6p) >= 4 || count(cb6n) >= 4)) : missing
        end
        insertcols!(res, :Rule6 => rule6)
    end
    # 7) Fifteen data points within one standard deviation of the nominal value.
    begin
        cb7 = CircularBuffer{Bool}(15)
        rule7 = map(eachrow(res)) do r
            push!(cb7, abs(r[value]-nominal) <= onesigma)
            isfull(cb7) ? !all(cb7) : missing
        end
        insertcols!(res, :Rule7 => rule7)
    end
    # 8) Eight sequential data points that are more than one standard deviation from the nominal value.
    begin
        cb8 = CircularBuffer{Bool}(8)
        rule8 = map(eachrow(res)) do r
            push!(cb8, abs(r[value]-nominal)>onesigma)
            isfull(cb8) ? !all(cb8) : missing
        end
        insertcols!(res, :Rule8 => rule8)
    end
    mot(v) = ismissing(v) || v
    allrules(r) = all(mot.((r[:Rule1], r[:Rule2], r[:Rule3], r[:Rule4], r[:Rule5], r[:Rule6], r[:Rule7], r[:Rule8])))
    result = ismissing(result) ? allrules : result
    insertcols!(res, :Passes=>map(result, eachrow(res)))
    if summary
        function details(row)
            fails=filter(r->!mot(row[Symbol("Rule",r)]), 1:8)
            if length(fails)==0
                return "Passes all tests."
            elseif length(fails)==1
                return "Fails test $(fails[1])."
            else
                return "Fails tests $(join(string.(fails), ", ", " and "))."
            end
        end
        insertcols!(res, :Details=>details.(eachrow(res)))
    end
    return res
end

"""
    wecorules(idx)

Returns a description of the idx-th Western Electric Company rule as implemented by this library.
"""
function wecorules(idx)
    return (
        "A single data point more than three standard deviations from the nominal value.",
        "Nine sequential data points above (or below) the nominal value.",
        "Six sequential data points monotonically increasing (decreasing).",
        "Sixteen sequential data points alternating up and down.",
        "Two of three data points above (or below) that are over two standard deviations from the nominal value.",
        "Four of five data points above (or below) that are more than one standard deviation from the nominal value.",
        "Fifteen data points within one standard deviation of the nominal value.",
        "Eight sequential data points that are more than one standard deviation from the nominal value."
    )[idx]
end

end