text:
abstract DataBase

@auto_hash_equals immutable dbPDBe <: DataBase
  number::Int # Cross referenced residue number
  name::ASCIIString # Cross referenced residue name
end

@inline _number_type(::Type{dbPDBe}) = Int

@auto_hash_equals immutable dbInterPro <: DataBase
  id::ASCIIString
  number::ASCIIString # Cross referenced residue number
  name::ASCIIString # Cross referenced residue name
  evidence::ASCIIString
end

@inline _number_type(::Type{dbInterPro}) = ASCIIString

for ref_type in [:dbUniProt, :dbPfam, :dbNCBI]
  @eval begin

    @auto_hash_equals immutable $(ref_type) <: DataBase
      id::ASCIIString # The cross reference database identifier
      number::Int # Cross referenced residue number
      name::ASCIIString # Cross referenced residue name
      end

    @inline _number_type(::Type{$(ref_type)}) = Int

  end
end

for ref_type in [:dbPDB, :dbCATH, :dbSCOP]
  @eval begin

    @auto_hash_equals immutable $(ref_type) <: DataBase
      id::ASCIIString
      number::ASCIIString
      name::ASCIIString
      chain::ASCIIString
    end

    @inline _number_type(::Type{$(ref_type)}) = ASCIIString

  end
end

@inline name(::Type{dbPDBe})    = "PDBe"
@inline name(::Type{dbUniProt}) = "UniProt"
@inline name(::Type{dbPfam})    = "Pfam"
@inline name(::Type{dbNCBI})    = "NCBI"
@inline name(::Type{dbInterPro})= "InterPro"
@inline name(::Type{dbPDB})     = "PDB"
@inline name(::Type{dbSCOP})    = "SCOP"
@inline name(::Type{dbCATH})    = "CATH"

"""Returns "" if the attributte is missing"""
function _get_attribute(elem::LightXML.XMLElement, attr::ASCIIString)
  text = attribute(elem, attr)
  if text === nothing
    return("")
  else
    return(text)
  end
end

for ref_type in [:dbPDB, :dbCATH, :dbSCOP]
  @eval begin

    function call(::Type{$(ref_type)}, map::LightXML.XMLElement)
      $(ref_type)(
      _get_attribute(map, "dbAccessionId"),
      _get_attribute(map, "dbResNum"),
      _get_attribute(map, "dbResName"),
      _get_attribute(map, "dbChainId")
      )
    end

  end
end

for ref_type in [:dbUniProt, :dbPfam, :dbNCBI]
  @eval begin

    function call(::Type{$(ref_type)}, map::LightXML.XMLElement)
      $(ref_type)(
      _get_attribute(map, "dbAccessionId"),
      parse(Int, _get_attribute(map, "dbResNum")),
      _get_attribute(map, "dbResName")
      )
    end

  end
end

function call(::Type{dbInterPro}, map::LightXML.XMLElement)
  dbInterPro(
    _get_attribute(map, "dbAccessionId"),
    _get_attribute(map, "dbResNum"),
    _get_attribute(map, "dbResName"),
    _get_attribute(map, "dbEvidence")
    )
end

function call(::Type{dbPDBe}, map::LightXML.XMLElement)
      dbPDBe(
      parse(Int, _get_attribute(map, "dbResNum")),
      _get_attribute(map, "dbResName")
      )
end

@auto_hash_equals immutable SIFTSResidue
  PDBe::dbPDBe
  UniProt::Nullable{dbUniProt}
  Pfam::Nullable{dbPfam}
  NCBI::Nullable{dbNCBI}
  InterPro::Array{dbInterPro, 1}
  PDB::Nullable{dbPDB}
  SCOP::Nullable{dbSCOP}
  CATH::Nullable{dbCATH}
  missing::Bool # XML: <residueDetail dbSource="PDBe" property="Annotation" ...
end

function show(io::IO, res::SIFTSResidue)
  println(io, "SIFTSResidue", res.missing ?  " (missing) " : "")
  println(io, "  PDBe:")
  println(io, "    number: ", res.PDBe.number)
  println(io, "    name: ", res.PDBe.name)
  for dbname in [:UniProt, :Pfam, :NCBI, :PDB, :SCOP, :CATH]
    dbfield = getfield(res, dbname)
    if !isnull(dbfield)
      println(io, "  ", dbname, " (Nullable) :")
      for f in fieldnames(get(dbfield))
        println(io, "    ", f, ": ",  getfield(get(dbfield), f))
      end
    end
  end
  println(io, "    InterPro: ",  res.InterPro)
end

function call(::Type{SIFTSResidue}, residue::LightXML.XMLElement, missing::Bool)
  PDBe = dbPDBe(residue)
  UniProt = Nullable{dbUniProt}()
  Pfam = Nullable{dbPfam}()
  NCBI = Nullable{dbNCBI}()
  InterPro = dbInterPro[]
  PDB = Nullable{dbPDB}()
  SCOP = Nullable{dbSCOP}()
  CATH = Nullable{dbCATH}()
  for crossref in get_elements_by_tagname(residue, "crossRefDb")
    db = attribute(crossref, "dbSource")
    if db == "UniProt"
      UniProt = Nullable(dbUniProt(crossref))
    elseif db == "Pfam"
      Pfam = Nullable(dbPfam(crossref))
    elseif db == "NCBI"
      NCBI = Nullable(dbNCBI(crossref))
    elseif db == "InterPro"
      push!(InterPro, dbInterPro(crossref))
    elseif db == "PDB"
      PDB = Nullable(dbPDB(crossref))
    elseif db == "SCOP"
      SCOP = Nullable(dbSCOP(crossref))
    elseif db == "CATH"
      CATH = Nullable(dbCATH(crossref))
    else
      warn(string(db, " is not in the MIToS' DataBases."))
    end
  end
  SIFTSResidue(PDBe,
               UniProt,
               Pfam,
               NCBI,
               InterPro,
               PDB,
               SCOP,
               CATH,
               missing)
end

call(::Type{SIFTSResidue}, residue::LightXML.XMLElement) =  SIFTSResidue(residue, _is_missing(residue))

# Mapping Functions
# =================

_parse(::Type{Int}, str) = parse(Int, str)
_parse(::Type{ASCIIString}, str) = ascii(str)
@inline _parse(::Type{ASCIIString}, str::ASCIIString) = str

"""Parses a SIFTS XML file and returns a `Dict` between residue numbers of two `DataBase`s  with the given identifiers.
A `chain` could be specified ("all" by default).
If `missings` is `true` (default) all the residues are used, even if they haven’t coordinates in the PDB file."""
function siftsmapping{F, T}(filename::AbstractString,
                            db_from::Type{F}, id_from::ASCIIString,
                            db_to::Type{T}, id_to::ASCIIString; chain::ASCIIString="all", missings::Bool = true)
  mapping = Dict{_number_type(F), _number_type(T)}()
  xdoc = parse_file(filename)
  try
    for entity in _get_entities(xdoc)
      segments = _get_segments(entity)
      for segment in segments
        residues = _get_residues(segment)
  		  for residue in residues
          in_chain = chain == "all"
          key_data = name(db_from) == "PDBe" ? Nullable(parse(Int, attribute(residue, "dbResNum"))) : Nullable{_number_type(F)}()
          value_data = name(db_to) == "PDBe" ? Nullable(parse(Int, attribute(residue, "dbResNum"))) : Nullable{_number_type(T)}()
	  	    if missings || !_is_missing(residue)
  			    crossref = get_elements_by_tagname(residue, "crossRefDb")
	  			  for ref in crossref
              source = attribute(ref, "dbSource")
		  		    if source == name(db_from) && attribute(ref, "dbAccessionId") == id_from
			  		    key_data = Nullable(_parse(_number_type(F), attribute(ref, "dbResNum")))
				  	  end
              if source == name(db_to) && attribute(ref, "dbAccessionId") == id_to
		  			    value_data = Nullable(_parse(_number_type(T), attribute(ref, "dbResNum")))
			  		  end
              if !in_chain && source == "PDB" # XML: <crossRefDb dbSource="PDB" ... dbChainId="E"/>
                in_chain = attribute(ref, "dbChainId") == chain
              end
		  		  end
            if !isnull(key_data) && !isnull(value_data) && in_chain
              key = get(key_data)
              haskey(mapping, key) && warn(string(key, " is already in the mapping with the value ", mapping[key], ". The value is replaced by ", get(value_data)))
			  		  mapping[key] = get(value_data)
            end
			    end
		    end
      end
    end
  finally
    free(xdoc)
  end
  sizehint!(mapping, length(mapping))
end

"""
`parse(document::LightXML.XMLDocument, ::Type{SIFTSXML}; chain::ASCIIString="all", missings::Bool = true)`

Returns a `Vector{SIFTSResidue}` parsed from a `SIFTSXML` file.
By default, parses all the `chain`s and includes `missings` residues.
"""
function parse(document::LightXML.XMLDocument, ::Type{SIFTSXML}; chain::ASCIIString="all", missings::Bool = true)
  vector = SIFTSResidue[]
  for entity in _get_entities(document)
    for segment in _get_segments(entity)
      residues = _get_residues(segment)
		  for residue in residues
        missing = _is_missing(residue)
		    if missings || !missing
          sifts_res = SIFTSResidue(residue, missing)
          if chain == "all" || (!isnull(sifts_res.PDB) && get(sifts_res.PDB).chain == chain)
            push!(vector, sifts_res)
          end
			  end
		  end
    end
  end
  vector
end

# Find SIFTSResidue
# -----------------

"""
`isobject{T <: DataBase}(res::SIFTSResidue, ::Type{T}, tests...)`

Returns `true` if the tests are successfully passed for that `DataBase` sub-type on that `SIFTSResidue`.
"""
function isobject{T <: DataBase}(res::SIFTSResidue, ::Type{T}, tests::AbstractTest...)
  dbfield = getfield(res, symbol(name(T)))
  if !isnull(dbfield)
    return(isobject(get(dbfield), tests...))
  end
  false
end

function findobjects{T <: DataBase}(vector::AbstractVector{SIFTSResidue}, ::Type{T}, tests::AbstractTest...)
  dbname = symbol(name(T))
  len = length(vector)
  indexes = Array(Int, len)
  n = 0
  for i in 1:len
    dbfield = getfield(vector[i], dbname)
    if !isnull(dbfield) && isobject(get(dbfield), tests...)
      n += 1
      indexes[n] = i
    end
  end
  resize!(indexes, n)
end

function collectobjects{T <: DataBase}(vector::AbstractVector{SIFTSResidue}, ::Type{T}, tests::AbstractTest...)
  dbname = symbol(name(T))
  len = length(vector)
  elements = Array(SIFTSResidue, len)
  n = 0
  for i in 1:len
    dbfield = getfield(vector[i], dbname)
    if !isnull(dbfield) && isobject(get(dbfield), tests...)
      n += 1
      elements[n] = vector[i]
    end
  end
  resize!(elements, n)
end

"""
`capture(res::SIFTSResidue, db_capture, field, db_test, tests...)`

Takes a `SIFTSResidue`, a `db...` type and a `Symbol` with the name of the `field` to capture from that database.
Returns a `Nullable` with the field content if the `tests` are passed over a determined database (`db_test`).
The function Returns `nothing` if the DataBase to test or capture is null in the `SIFTSResidue`.
"""
function capture{C <: DataBase, T <: DataBase}(res::SIFTSResidue, db_capture::Type{C}, field::Symbol, db_test::Type{T}, tests::AbstractTest...)
  dbfield_capture = getfield(res, symbol(name(C)))
  dbfield_test = getfield(res, symbol(name(T)))
  if !isnull(dbfield_capture) && !isnull(dbfield_test)
    captured = getfield(get(dbfield_capture), field)
    for test in tests
      if !Utils._test(get(dbfield_test), test)
        return(Nullable{typeof(captured)}())
      end
    end
    return(Nullable(captured))
  end
  nothing
end

"Returns the **type** of the `field` in the first object of the collection"
function guess_type{T <: DataBase}(collection::AbstractVector{SIFTSResidue}, ::Type{T}, field::Symbol)
  for res in collection
    dbfield = getfield(res, symbol(name(T)))
    if !isnull(dbfield)
      data = get(dbfield)
      if field in fieldnames(data)
        return(fieldtype(typeof(data), field))
      end
    end
  end
  Any
end

"""
`collectcaptures(vector::AbstractVector{SIFTSResidue}, db_capture, field, db_test, tests)`

Calls the `capture` function and returns a vector of `Nullable`s with the captured `field`s.
The element is null if any test fails or the object hasn't the `field`.
"""
function collectcaptures{C <: DataBase, T <: DataBase}(vector::AbstractVector{SIFTSResidue}, db_capture::Type{C}, field::Symbol, db_test::Type{T}, tests::AbstractTest...)
  Nullable{guess_type(vector, C, field)}[ capture(object, C, field, T, tests...) for object in vector ]
end


text:
#=
Copyright (c) 2015, Intel Corporation

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

    * Redistributions of source code must retain the above copyright notice,
      this list of conditions and the following disclaimer.
    * Redistributions in binary form must reproduce the above copyright
      notice, this list of conditions and the following disclaimer in the
      documentation and/or other materials provided with the distribution.
    * Neither the name of Intel Corporation nor the names of its contributors
      may be used to endorse or promote products derived from this software
      without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
=#

@doc """
Symbolic data-flow analysis framework

The framwork is based on 3-level lattice:

    Top
 /  / \  \
S1 S2 S3 S4
 \  \ /  /
  Bottom

Each entry in the lattice is a symbol(AbstactSymbol).
"""
module SymbolicAnalysis

using CompilerTools
using Sparso
using Sparso: ExprPattern, RegionInfo, AbstractPatternAction, CallSites, expr_skeleton
using Sparso: dprintln, dprint
import Base.Callable

export TransferRule
export SymbolicAnalyzer
export AbstractSymbol, MiddleSymbol, TOP_SYMBOL, BOTTOM_SYMBOL
export union_symbols

export check_and_gen_transfer_rules
export run_analyzer

export SA_SUCC

typealias BasicBlock      CompilerTools.CFGs.BasicBlock
typealias Statement       CompilerTools.CFGs.TopLevelStatement
typealias Liveness        CompilerTools.LivenessAnalysis.BlockLiveness
typealias CFG             CompilerTools.CFGs.CFG
#typealias DomLoops        CompilerTools.Loops.DomLoops
#typealias Loop            CompilerTools.Loops.Loop
#typealias GenSymId        Int
#typealias BasicBlockIndex Int
#typealias StatementIndex  Int
typealias Sym             Union{Symbol, GenSym} # A Symbol or GenSym.
#typealias Sym2TypeMap     Dict{Sym, Type}
typealias Symexpr         Union{Symbol, GenSym, Expr} # A Symbol, GenSym or Expr

const SA_SUCC = true

abstract AbstractSymbol

type TopSymbol <: AbstractSymbol
end

type BottomSymbol <: AbstractSymbol
end

immutable MiddleSymbol <: AbstractSymbol
    value :: Any
#    class :: SymbolClass

    MiddleSymbol(v) = new(v) #, SymbolClass(v))
end

const TOP_SYMBOL = TopSymbol()
const BOTTOM_SYMBOL = BottomSymbol()

@doc """
any ^ Bottom = Bottom
any ^ Top = any
Mi ^ Mi = Mi
Mi ^ Mj = Bottom (if i != j)
"""
function DefaultMeetRule(s1::AbstractSymbol, s2::AbstractSymbol)
    if s1 == BOTTOM_SYMBOL || s2 == BOTTOM_SYMBOL
        return BOTTOM_SYMBOL
    end

    if s1 == TOP_SYMBOL && s2 != TOP_SYMBOL
        return s2
    elseif s2 == TOP_SYMBOL && s1 != TOP_SYMBOL
        return s1
    elseif s1 == TOP_SYMBOL && s2 == TOP_SYMBOL
        return TOP_SYMBOL
    end

    if s1.value == s2.value #|| s1.class == s2.class
        #assert(isa(s1.class.first, MiddleClass))
        #return s1.class.first
        return s1
    else
        return BOTTOM_SYMBOL
    end
end

function DefaultInitializer()
end

function DefaultSymbolizer(e::Symexpr)
    if isa(e, Sym)
        return MiddleSymbol(Sym)
    else
        #TODO
    end
end

#function DefaultBooleanSymbolizer(e::Symexpr)
#    return MiddleSymbol(:true)
#end

@doc """
"""
#type SymbolicValue
#    value   :: AbstractSymbol
#    SymbolicValue() = new(TOP_SYMBOL)

#    values  :: Set{AbstractSymbol}  #
#    final   :: AbstractSymbol       # final symbolic value

#    SymbolicValue() = new(Set{AbstractSymbol}(), TOP_SYMBOL)
#end
typealias SymbolicValue AbstractSymbol

@doc """ a default pattern matcher """
function EmptyMatcher(ctx)
    return true
end

@doc """
"""
type TransferRule
    match_pattern   :: Tuple
    match_func      :: Function
    action          :: Function

    TransferRule(p :: Tuple, action :: Function) =  new(p, EmptyMatcher, action)
end

type SymbolicAnalyzer
    name            :: AbstractString
    transfer_rules  :: Vector{TransferRule}
    symbolizer      :: Function
    meet_rule       :: Function

    SymbolicAnalyzer(name::AbstractString,
        transfer_rules::Vector{TransferRule},
        symbolizer::Function,
        meet_rule::Function = DefaultMeetRule,
    ) = new(name, transfer_rules, symbolizer, meet_rule)
end

#@doc """
#Context used for analyzing one ast node (Sym or Expr)
#"""
type SymExprContext
    raw_expr    :: Any
    args        :: Vector{SymExprContext}
    types       :: Vector{Type}
    svalue      :: Union{SymbolicValue, Void} #

    SymExprContext(ast) = new(
        ast,
        Vector{SymExprContext}(),
        Vector{Type}(),
        nothing
    )
end

@doc """
Context used for analyzing one Julia statement
"""
type StmtContext
    stmt                 :: Statement                       # statement itself
    in                   :: Set{StmtContext}                # flow-in
    out                  :: Set{StmtContext}                # flow-out

    context_map          :: Dict{Any, SymExprContext}

    changed              :: Set{Sym}                        # variables whose property has been changed?
    # property map after analyzing this statement
    syms                 :: Set{Sym}
    in_symbolic_vals     :: Union{Dict{Sym, SymbolicValue}, Void}        # symbol -> property
    out_symbolic_vals    :: Dict{Sym, SymbolicValue}        # symbol -> property
#    local_symbolic_vals  :: Dict{Symexpr, SymbolicValue}    # symbol|expr -> property

    StmtContext(stmt) = new(
        stmt, # stmt
        Set{StmtContext}(), # in
        Set{StmtContext}(), # out
        #ypeof(stmt.expr) == Expr ? SymExprContext(stmt.expr) : nothing,
        Dict{Symexpr, SymExprContext}(), # context_map
        Set{Sym}(),                      # changed
        Set{Sym}(),                      # syms
        nothing,      # in_symbolic_vals
        Dict{Sym, SymbolicValue}(),      # out_symbolic_vals
#        Dict{Symexpr, SymbolicValue}()   # local_symbolic_vals
    )
end

@doc """
Context used for the whole analysis
"""
type AnalysisContext
    analyzer                :: SymbolicAnalyzer
    stmt_contexts           :: Dict{Statement, StmtContext}
    curr_context            :: Union{StmtContext, Void}

    live_in_before_expr     :: Set{Sym}
    equivalent_sets         :: Dict{SymbolicValue, Vector{SymbolicValue}}
    # Such patterns should be matched at the last, because otherwise, other
    # patterns may not be able to match what they should: they cannot find the
    # subtrees to match, which are no longer in the same statement.
    # We call such patterns splitting patterns, and the other non-splitting.
    # We can top-down match non-splitting patterns once, and bottom-up match
    # all patterns (including splitting and non-splitting) once.
    non_splitting_patterns  :: Vector{ExprPattern}

    AnalysisContext(analyzer) = new(
        analyzer,

        Dict{Statement, StmtContext}(),
        nothing,                         # curr_context

        Set{Sym}(),                      # live_in_before_expr
        Dict{Sym, Vector{Sym}}(),        # equivalent_sets

        Vector{ExprPattern}()            # non_splitting_patterns
    )
end

function check_and_gen_transfer_rules(rules)
    ret = Vector{TransferRule}()
    for r in rules
        assert(isa(r, Tuple))
        rule = TransferRule(r[1], r[2])
        push!(ret, rule)
    end
    ret
end

type PreActionFunctor <: AbstractPatternAction
    caller :: Function
    action :: Callable
end

function call_pre_action(
    functor           :: PreActionFunctor,
    ast               :: Expr,
    call_sites        :: CallSites,
    fknob_creator :: AbstractString,
    fknob_deletor :: AbstractString,
    matrices_to_track :: Tuple,
    reordering_power  :: Int,
    reordering_FAR    :: Tuple
)
    if typeof(ast) <: Sym || typeof(ast) == SymbolNode
        ast = Sparso.get_symexpr(ast)
    end

    stmt_ctx = call_sites.extra.curr_context
    assert(in(ast, stmt_ctx.context_map))
    return functor.action(stmt_ctx.context_map[ast]) #
end

function generate_pre_action(func::Callable)
    functor = PreActionFunctor(call_pre_action, func)
    functor
end

type PostActionFunctor <: AbstractPatternAction
    caller :: Function
    action :: Callable
end

type PatternActionEnv
    args :: Vector{}
end

function prepare_pattern_action_env(
    stmt_ctx    :: StmtContext,
    expr        :: Expr,
    symbol_info,
)
    if !in(expr, keys(stmt_ctx.context_map))
        dump(expr)
        dump(keys(stmt_ctx.context_map))
    end
    assert(in(expr, keys(stmt_ctx.context_map)))
    env = stmt_ctx.context_map[expr]
    assert(env.raw_expr == expr)

    # fill args if it's empty
    if isempty(env.args)
        idx = env.raw_expr.head == :call ? 2 : 1
        #skeleton = expr_skeleton(expr, symbol_info)
        #dump(skeleton)
        #assert(length(env.raw_expr.args) == length(skeleton))
        while idx <= length(env.raw_expr.args)
            arg = env.raw_expr.args[idx]
            if typeof(arg) == SymbolNode
                arg = Sparso.get_symexpr(arg)
            end

            if !in(arg, keys(stmt_ctx.context_map))
                dump(arg)
            end
            assert(in(arg, keys(stmt_ctx.context_map)))
            push!(env.args, stmt_ctx.context_map[arg])
            #push!(env.types, skeleton[idx])
            idx = idx + 1
        end
    #else
    #    assert(length(env.args) == length(env.raw_expr.args)-1)
    end

    return env
end

function done_pattern_action_env(
    stmt_ctx    :: StmtContext,
    env         :: SymExprContext
)
    #stmt_ctx.syms
    #stmt_ctx.out_symbolic_vals
end

function call_post_action(
    functor           :: PostActionFunctor,
    ast               :: Expr,
    call_sites        :: CallSites,
    fknob_creator :: AbstractString,
    fknob_deletor :: AbstractString,
    matrices_to_track :: Tuple,
    reordering_power  :: Int,
    reordering_FAR    :: Tuple
)
    if typeof(ast) <: Sym || typeof(ast) == SymbolNode
        ast = Sparso.get_symexpr(ast)
    end

    # wrap env
    stmt_ctx = call_sites.extra.curr_context
    env = prepare_pattern_action_env(stmt_ctx, ast, call_sites.symbol_info)
    ret = functor.action(env) #
    # assign a unique symbolic value if expr matched but not processed
    # by the user defined pattern rules
    #if ret != SA_SUCC && env.svalue == nothing && isa(env.raw_expr, Symexpr) && env.raw_expr.head != :(=)
    #    env.svalue = call_sites.extra.analyzer.symbolizer(env.raw_expr, Any, true)
    #end
    done_pattern_action_env(stmt_ctx, env)
    return true
end

function generate_post_action(func::Callable)
    functor = PostActionFunctor(call_post_action, func)
    functor
end

function generate_analysis_patterns(
    analyzer :: SymbolicAnalyzer
)
    # generate propagation patterns from user defined rules (analyzer)
    analysis_patterns = Vector{ExprPattern}()
    for r in analyzer.transfer_rules
        assert(isa(r.match_pattern, Tuple))
        pre_action = r.match_func == EmptyMatcher ? Sparso.do_nothing : generate_pre_action(r.match_func)
        post_action = generate_post_action(r.action)
        #post_action =  Sparso.do_nothing
        push!(analysis_patterns,
            ExprPattern(string(r), # name
                r.match_pattern,
                (:NO_SUB_PATTERNS,),
                pre_action,
                (:NO_CHANGE,),
                post_action,
                "",
                "",
                (),
                0,
                ()
            )
        )
    end
    return analysis_patterns
end

@doc """
build context for every top-level statement in a code region
"""
function build_stmt_contexts(
    region :: RegionInfo
)
    stmt_to_ctx = Dict{Statement, StmtContext}()
    for s in region.stmts
        #dprintln(1, 0, s)
        stmt_to_ctx[s] = StmtContext(s)
    end

    bb_idxs = keys(region.bblocks)
    bbs = values(region.bblocks)
    for bb in bbs
        if isempty(bb.statements)
            continue
        end

        first_stmt = first(bb.statements)
        last_stmt = last(bb.statements)

        # intrablock in and out
        for (idx, s) in enumerate(bb.statements)
            if s == last_stmt # last one?
                break
            end
            next = bb.statements[idx+1]
            assert(in(s, keys(stmt_to_ctx)))
            assert(in(next, keys(stmt_to_ctx)))
            push!(stmt_to_ctx[s].out, stmt_to_ctx[next])
            push!(stmt_to_ctx[next].in, stmt_to_ctx[s])
        end

        # interblock in and out
        # backward
        bb_list = collect(copy(bb.preds))
        i = 1
        while i <= length(bb_list)
            pred = bb_list[i]
            i+=1
            if !in(pred, bbs)
                continue
            end
            if isempty(pred.statements)
                for p in pred.preds
                    if !in(p, bb_list)
                        push!(bb_list, p)
                    end
                end
            else
                pred_last = last(pred.statements)
                push!(stmt_to_ctx[first_stmt].in, stmt_to_ctx[pred_last])
            end
        end
        # forward
        bb_list = collect(copy(bb.succs))
        i = 1
        while i <= length(bb_list)
            succ = bb_list[i]
            i+=1
            if !in(succ, bbs)
                continue
            end
            if isempty(succ.statements)
                for p in succ.succs
                    if !in(p, bb_list)
                        push!(bb_list, p)
                    end
                end
            else
                succ_first = first(succ.statements)
                push!(stmt_to_ctx[last_stmt].out, stmt_to_ctx[succ_first])
            end
        end
    end

    return stmt_to_ctx
end

# Symbol types unimportant to analysis
const SKIP_TYPES = [GlobalRef, TopNode, Int32, Int64, Float64, Bool, QuoteNode, ASCIIString, Complex]

function build_expr_contexts(ast, stmt_ctx)
    expr = ast
    ast_type = typeof(ast)
    if ast_type <: Sym || ast_type <: SymbolNode
        expr = Sparso.get_symexpr(ast)
        ctx = SymExprContext(expr)
        ctx.svalue = TOP_SYMBOL
        stmt_ctx.context_map[expr] = ctx
        push!(stmt_ctx.syms, expr)
    elseif ast_type <: Expr
        ctx = SymExprContext(expr)
        #ctx.svalue = TOP_SYMBOL
        stmt_ctx.context_map[expr] = ctx
    #elseif isa(expr, TopNode)
        #dump(expr)
        #assert(0)
    #elseif isa(expr, GlobalRef)
    elseif in(ast_type, SKIP_TYPES)
        #expr = Sparso.get_symexpr(ast)
        #dump(ast)
        ctx = SymExprContext(expr)
        #ctx.svalue = TOP_SYMBOL
        stmt_ctx.context_map[expr] = ctx
    else
        assert(0)
        #return nothing
    end

    #if !in(expr, keys(stmt_ctx.context_map))
    #    ctx = SymExprContext(expr)
    #    stmt_ctx.context_map[expr] = ctx
    #    if isa(ast, Expr)
    #        for i in 2 : length(expr.args)
    #            push!(ctx.args, (build_expr_contexts(ast.args[i], stmt_ctx)))
    #       end
    #    end
    #    return ctx
    #end
    return nothing
end

function build_expr_contexts(ast, stmt_ctx, top_level_number, is_top_level, read)
    build_expr_contexts(ast, stmt_ctx)
end

function merge_symbolic_vals(des::Dict{Sym, SymbolicValue}, src::Dict{Sym, SymbolicValue}, meet_rule::Function)
    des_keys = collect(keys(des))
    for (k, v) in src
        if in(k, des_keys)
            des[k] = meet_rule(src[k], des[k])
        else
            des[k] = v
        end
    end
end

#function show_
#end

function show_contexts(stmt_contexts::Dict{Statement, StmtContext})
    for (s, ctx) in stmt_contexts
        dprintln(1, 0, s.index, " ", s.expr)
        dprint(1, 1, "IN:")
        for c in ctx.in
            dprint(1, 0, " ", c.stmt.index)
        end
        dprintln(1, 0, "")
        dprint(1, 1, "OUT:")
        for c in ctx.out
            dprint(1, 0, " ", c.stmt.index)
            #dprintln(1, 2, c.stmt.index, " ", c.stmt.expr)
        end
        dprintln(1, 0, "")
    end
end

function union_symbols(s1::MiddleSymbol, s2::MiddleSymbol)
    if s1.value != s2.value && s1.class != s2.class
        assert(isempty(intersect(s1.class, s2.class)))
        union!(s1.class, s2.class)
        s2.class = s1
    end
end

function show_symbolic_vals(vals::Dict{Sym, SymbolicValue}, indent_level=1)
    for (s, v) in vals
        if v == BOTTOM_SYMBOL
            val = "BOTTOM"
        elseif v == TOP_SYMBOL
            val = "TOP"
        else
            val = v.value
        end

        dprintln(1, indent_level, s, " -> ", val)
        # meeting func
    end
end

function run_analyzer(
    analyzer    :: SymbolicAnalyzer,
    region      :: RegionInfo,
    predefined  ::Dict{Sym, AbstractSymbol},
    verbose
)

    # initialize property values for all Syms according to

    analysis_context = AnalysisContext(analyzer)

    analysis_context.stmt_contexts = build_stmt_contexts(region)

    # show_contexts(analysis_context.stmt_contexts)

    # build contexts for expressions of every statement
    for (stmt, ctx) in analysis_context.stmt_contexts
        expr = stmt.expr
        if typeof(expr) != Expr || expr.head == :return
            continue
        end
        CompilerTools.AstWalker.AstWalk(expr, build_expr_contexts, ctx)
    end

    analysis_patterns = generate_analysis_patterns(analyzer)

    call_sites  = Sparso.CallSites(Set{Sparso.CallSite}(),
                            region.region,
                            region.lambda,
                            region.symbol_info,
                            region.liveness, analysis_patterns,
                            Vector{Sparso.Action}(), analysis_context)

    # All patterns are non-splittable.
    analysis_context.non_splitting_patterns = analysis_patterns

    # Build flow graph

    converged = false
    cnt = 0
    while !converged
        cnt = cnt + 1
        converged = true
        for (stmt, stmt_ctx) in analysis_context.stmt_contexts

            if verbose > 1
                dprintln(1, 0, stmt.index, " ", stmt.expr)
            end

            new_symbolic_vals = Dict{Sym, SymbolicValue}()
            for in_ctx in stmt_ctx.in
                merge_symbolic_vals(new_symbolic_vals, in_ctx.out_symbolic_vals, analyzer.meet_rule)
            end

            # preserve predefined values
            for s in keys(predefined)
                #if in(s, keys(stmt_ctx.in_symbolic_vals))
                new_symbolic_vals[s] = predefined[s] #analyzer.symbolizer(s)
                #end
            end

            if verbose > 1
                dprintln(1, 1, "IN ")
                show_symbolic_vals(new_symbolic_vals, 2)
            end

            expr = stmt.expr
            if stmt_ctx.in_symbolic_vals == new_symbolic_vals
                if verbose > 1
                    dprintln(1, 1, "IN_SET_NOT_CHANGED")
                end
                continue
            else
                stmt_ctx.in_symbolic_vals = new_symbolic_vals
            end

            if typeof(expr) != Expr || expr.head == :return
                stmt_ctx.out_symbolic_vals = new_symbolic_vals
                if verbose > 1
                    dprintln(1, 1, "SKIP")
                    show_symbolic_vals(new_symbolic_vals, 2)
                end
                continue
            end

            #ctx = analysis_context.stmt_contexts[stmt]
            #ctx.local_map.clear()
            analysis_context.curr_context = stmt_ctx
            call_sites.extra.live_in_before_expr = CompilerTools.LivenessAnalysis.live_in(stmt, region.liveness)

            # update all Symexpr contexts from new_symbolic_vals
            for (se, se_ctx) in stmt_ctx.context_map
                if in(se, keys(new_symbolic_vals)) #(isa(se, Symbol) || isa(se, SymbolNode))
                    se_ctx.svalue = new_symbolic_vals[se]
                end
            end

            CompilerTools.AstWalker.AstWalk(expr, Sparso.match_replace_an_expr_pattern, call_sites)

            # update out_symbolic_vals
            for (se, se_ctx) in stmt_ctx.context_map
                if isa(se, Sym) #&& se_ctx.svalue != nothing
                    if se_ctx.svalue == nothing
                        #dump(se_ctx)
                        #assert(0)
                        se_ctx.svalue = TOP_SYMBOL
                    end
                    assert(in(se, stmt_ctx.syms))
                    if !in(se, keys(new_symbolic_vals))
                        new_symbolic_vals[se] = se_ctx.svalue
                    elseif se_ctx.svalue != new_symbolic_vals[se]
                        #if se_ctx.svalue == nothing
                        #end
                        new_symbolic_vals[se] = se_ctx.svalue
                    end
                end
            end

            # preserve predefined values
            for s in keys(predefined)
                #if in(s, keys(stmt_ctx.out_symbolic_vals))
                new_symbolic_vals[s] = predefined[s] #analyzer.symbolizer(s)
                #end
            end

            if stmt_ctx.out_symbolic_vals != new_symbolic_vals
                stmt_ctx.out_symbolic_vals = new_symbolic_vals
                converged = false

                if verbose > 1
                    dprintln(1, 1, "OUT")
                    show_symbolic_vals(new_symbolic_vals, 2)
                end
            else
                if verbose > 1
                    dprintln(1, 1, "OUT_SET_NOT_CHANGED")
                    show_symbolic_vals(new_symbolic_vals, 2)
                end
            end
        end
    end

    # global symbolic values
    global_symbolic_vals = Dict{Sym, SymbolicValue}()
    for (stmt, stmt_ctx) in analysis_context.stmt_contexts
        #merge_symbolic_vals(global_symbolic_vals, stmt_ctx.in_symbolic_vals, analyzer.meet_rule)
        merge_symbolic_vals(global_symbolic_vals, stmt_ctx.out_symbolic_vals, analyzer.meet_rule)
    end

    if verbose > 0
        dprintln(1, 0, "\n", region.name, " ", analyzer.name)
        show_symbolic_vals(global_symbolic_vals)
    end

    return global_symbolic_vals
end

end # module

ext: jl

max_stars_repo_name: IntelLabs/Sparso

max_issues_repo_name: IntelLabs/Sparso

max_forks_repo_name: IntelLabs/Sparso


text:
################################################################################

"""

    sensitivitySpecificity(ar::Array{T, 2}) where T <: Number

# Description
Calculate sensitivity and specificity from 2 x 2 array.

# Examples
```jldoctest
julia> χ = [10 40; 5 45]
julia> sensitivitySpecificity(χ)
(sensitivity = 0.6666666666666666, specificity = 0.5294117647058824)

julia> χ = [20 33; 10 37]
julia> sensitivitySpecificity(χ)
(sensitivity = 0.6666666666666666, specificity = 0.5285714285714286)
```

See also: [`predictiveValue`](@ref)
"""
function sensitivitySpecificity(ar::Array{T, 2}) where T <: Number
  if size(ar) == (2, 2)
    return (sensitivity = ar[1, 1] / ( ar[1, 1] + ar[2, 1] ), specificity = ar[2, 2] / ( ar[2, 2] + ar[1, 2] ))
  else
    @error "Matrix does not have the proper size"
  end
end

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

"""

    predictiveValue(ar::Array{T, 2}) where T <: Number

# Description
Calculate positive and negative predictive values from 2 x 2 array.

# Examples
```jldoctest
julia> χ = [10 40; 5 45]
julia> predictiveValue(χ)
(positive = 0.2, negative = 0.9)

julia> χ = [20 33; 10 37]
julia> predictiveValue(χ)
(positive = 0.37735849056603776, negative = 0.7872340425531915)
```

See also: [`sensitivitySpecificity`](@ref)
"""
function predictiveValue(ar::Array{T, 2}) where T <: Number
  if size(ar) == (2, 2)
    return (positive = ar[1, 1] / ( ar[1, 1] + ar[1, 2] ), negative = ar[2, 2] / ( ar[2, 2] + ar[2, 1] ))
  else
    @error "Matrix does not have the proper size"
  end
end

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

"""

    sensitivitySpecificity(tbVc::Array{T, 1}, labelVec::Array{T, 1}) where T <: Number

# Description
Calculate sensitivity and specificity from a `Hidden Markov model` struct.

See also: [`predictiveValue`](@ref)
"""
function sensitivitySpecificity(tbVc::Array{T, 1}, labelVec::Array{T, 1}) where T <: Number
  tbVec = copy(tbVc)

  # reassign frecuency labels
  labels = [1, 2]
  tbVec[findall(tbVec .> 1)] .= 2

  # adjust & concatenate frecuency tables
  positives = tbVec[labelVec[:, 1] .== 1] |> freqtable |> p -> convertFqDfTempl(p, templ = labels) |> p -> sort(p, rev = true)
  negatives = tbVec[labelVec[:, 1] .== 0] |> freqtable |> p -> convertFqDfTempl(p, templ = labels) |> p -> sort(p, rev = true)
  outNamedArray = [positives[:, 2] negatives[:, 2]]
  return sensitivitySpecificity(outNamedArray)
end

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

"""

    sensitivitySpecificity(tbVc::Array{T, 1}, labelMat::Matrix{T}) where T <: Number

# Description
Calculate sensitivity and specificity from a `Hidden Markov model` struct.

See also: [`predictiveValue`](@ref)
"""
function sensitivitySpecificity(tbVc::Array{T, 1}, labelMat::Matrix{T}) where T <: Number
  tbVec = copy(tbVc)

  # reassign frecuency labels
  labels = [1, 2]
  tbVec[findall(tbVec .> 1)] .= 2

  # add label columns
  labelVec = sum(labelMat, dims = 2)

  # adjust & concatenate frecuency tables
  positives = tbVec[labelVec[:, 1] .== 1] |> freqtable |> p -> convertFqDfTempl(p, templ = labels) |> p -> sort(p, rev = true)
  negatives = tbVec[labelVec[:, 1] .== 0] |> freqtable |> p -> convertFqDfTempl(p, templ = labels) |> p -> sort(p, rev = true)
  outNamedArray = [positives[:, 2] negatives[:, 2]]
  return sensitivitySpecificity(outNamedArray)
end

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

"""

    sensitivitySpecificity(ssDc::Dict{S, Tuple{Array{T, 1}, Array{Array{Float64, 1}, 1}}}, labelVec) where T <: Number where S <: String

# Description
Iterate on Dictionary and calculate sensitivity and specificity from a `Hidden Markov model` struct.

See also: [`predictiveValue`](@ref)
"""
function sensitivitySpecificity(ssDc::Dict{S, Tuple{Array{T, 1}, Array{Array{Float64, 1}, 1}}}, labelVec) where T <: Number where S <: String

  outDc = Dict{S, Array{Float64, 2}}() where S <: String
  for (k, v) in ssDc
    outSensSpec = zeros(1, 2)
    (outSensSpec[1, 1], outSensSpec[1, 2]) = sensitivitySpecificity(ssDc[k][1], labelVec)
    outDc[k] = outSensSpec
  end

  return outDc
end

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

"transform freqtable => dataframe"
function convertFqDf(fq::NamedVector{T, Array{T, 1}, Tuple{OrderedDict{T, T}}}; colnames::Array{S, 1} = ["Value", "Frecuency"]) where T <: Number where S <: String
  return DataFrames.DataFrame([names(fq)[1] fq.array], colnames)
end

"transform freqtable => dataframe template"
function convertFqDfTempl(fq::NamedVector{T, Array{T, 1}, Tuple{OrderedDict{T, T}}}; colnames::Array{S, 1} = ["Value", "Frecuency"], templ::Array{T, 1}) where T <: Number where S <: String

  fq = convertFqDf(fq)

  outDf = DataFrames.DataFrame([templ zeros(Int64, length(templ))], colnames)

  for ix in 1:size(fq, 1)
    outDf[findall(fq[ix, 1] .== outDf[:, 1]), 2] .= fq[ix, 2]
  end

  return outDf
end

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

"adjust frecuency tables for concatenation"
function stFreqTb(fTb::NamedArray{Int64, 1})
  sTb = size(fTb, 1)
  # de novo
  if sTb == 0
    fTb = [1, 2] |> freqtable |> reverse
    fTb .= 0
  # concatenate missing
  elseif sTb == 1
    added = copy(fTb)
    nPos = names(fTb)
    if sum.(nPos)[1] == 0
      NamedArrays.setnames!(added, [2], 1)
      added[1, :] .= 0
      fTb = [fTb; added]
    elseif sum.(nPos)[1] == 1
      NamedArrays.setnames!(added, [1], 1)
      added[1, :] .= 0
      fTb = [added; fTb]
    end
  # through warning
  elseif sTb > 2
    @warn "frecuency table contains more than 2 values"
  end
  return fTb
end

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

max_stars_repo_name: DanielRivasMD/MindReader

max_issues_repo_name: DanielRivasMD/MindReader

max_forks_repo_name: DanielRivasMD/MindReader


text:
using CompileBot

bcs = Vector{BotConfig}(undef, 3)

bcs[1] = BotConfig("TestPackage5", yml_path = "SnoopCompile.yml", tmin =0.0)

bcs[2] = BotConfig("TestPackage5", yml_path = "../../.github/workflows/SnoopCompile.yml", tmin =0.0)

bcs[3] = BotConfig("TestPackage5", yml_path = ".github/workflows/SnoopCompile.yml", tmin =0.0)

if !( VERSION <= v"1.2" && Base.Sys.iswindows() )
    push!(bcs, BotConfig("TestPackage5", yml_path = "../../$(@__DIR__)/.github/workflows/SnoopCompile.yml", tmin =0.0))
end


text:
import Base.rand

export Hyperrectangle

"""
    Hyperrectangle{N<:Real, VNC<:AbstractVector{N}, VNR<:AbstractVector{N}
                  } <: AbstractHyperrectangle{N}

Type that represents a hyperrectangle.

A [hyperrectangle](https://en.wikipedia.org/wiki/Hyperrectangle) is the
Cartesian product of one-dimensional intervals.

### Fields

- `center` -- center of the hyperrectangle as a real vector
- `radius` -- radius of the ball as a real vector, i.e., half of its width along
              each coordinate direction

### Examples

The `Hyperrectangle` type stores a vector representing the center and another
vector representing the radius. The default constructor `Hyperrectangle(c, r)`
receives the center and radius, in that order. For instance,

```jldoctest hyperrectangle_constructor
julia> c = [-1.0, 1.0];

julia> r = [2.0, 1.0];

julia> H = Hyperrectangle(c, r)
Hyperrectangle{Float64,Array{Float64,1},Array{Float64,1}}([-1.0, 1.0], [2.0, 1.0])
```

Which creates the hyperrectangle with vertices:

```jldoctest hyperrectangle_constructor
julia> vertices_list(H)
4-element Array{Array{Float64,1},1}:
 [1.0, 2.0]
 [-3.0, 2.0]
 [1.0, 0.0]
 [-3.0, 0.0]
```

The getter functions for the center and the radius are `center` and
`radius_hyperrectangle` (since `radius` corresponds to the radius of the
enclosing ball of minimal volume):

```jldoctest hyperrectangle_constructor
julia> center(H)
2-element Array{Float64,1}:
 -1.0
  1.0

julia> radius_hyperrectangle(H)
2-element Array{Float64,1}:
 2.0
 1.0
```

There is also a constructor from lower and upper bounds with keyword arguments
`high` and `low`. The following construction results in the same hyperrectangle
as in the previous paragraph:

```jldoctest hyperrectangle_constructor
julia> l = [-3.0, 0.0];

julia> h = [1.0, 2.0];

julia> Hyperrectangle(low=l, high=h)
Hyperrectangle{Float64,Array{Float64,1},Array{Float64,1}}([-1.0, 1.0], [2.0, 1.0])
```

By default, the constructor checks that that radius of the hyperrecatangle
is nonnegative. To supress this check, use the `check_bounds` optional flag
in the constructor. Note that if `check_bounds` is set to `false`, the behavior
of a set with contradictory bounds is undefined.
"""
struct Hyperrectangle{N<:Real, VNC<:AbstractVector{N}, VNR<:AbstractVector{N}
                     } <: AbstractHyperrectangle{N}
    center::VNC
    radius::VNR

    # default constructor with length comparison & domain constraint for radius
    function Hyperrectangle(center::VNC, radius::VNR; check_bounds::Bool=true) where
            {N<:Real, VNC<:AbstractVector{N}, VNR<:AbstractVector{N}}
        @assert length(center) == length(radius) "length of center and " *
            "radius must be equal"
        if check_bounds
            @assert all(v -> v >= zero(N), radius) "radius must not be negative"
        end
        return new{N, VNC, VNR}(center, radius)
    end
end

isoperationtype(::Type{<:Hyperrectangle}) = false
isconvextype(::Type{<:Hyperrectangle}) = true

# constructor from keyword arguments (lower and upper bounds)
function Hyperrectangle(; high::AbstractVector{N},
                          low::AbstractVector{N},
                          check_bounds::Bool=true) where {N<:Real}
    # compute center and radius from high and low vectors
    center = (high .+ low) ./ 2
    radius = high .- center
    return Hyperrectangle(center, radius, check_bounds=check_bounds)
end

# --- AbstractHyperrectangle interface functions ---

"""
    radius_hyperrectangle(H::Hyperrectangle{N}, i::Int) where {N<:Real}

Return the box radius of a hyperrectangle in a given dimension.

### Input

- `H` -- hyperrectangle
- `i` -- dimension of interest

### Output

The radius in the given dimension.
"""
function radius_hyperrectangle(H::Hyperrectangle{N}, i::Int) where {N<:Real}
    return H.radius[i]
end

"""
    radius_hyperrectangle(H::Hyperrectangle{N}) where {N<:Real}

Return the box radius of a hyperrectangle in every dimension.

### Input

- `H` -- hyperrectangle

### Output

The box radius of the hyperrectangle.
"""
function radius_hyperrectangle(H::Hyperrectangle{N}) where {N<:Real}
    return H.radius
end

function load_genmat_hyperrectangle_static()
return quote
    function genmat(H::Hyperrectangle{N, SVector{L, N}, SVector{L, N}}) where {L, N}
        gens = zeros(MMatrix{L, L, N})
        nzcol = Vector{Int}()
        @inbounds for i in 1:L
            r = H.radius[i]
            if !isapproxzero(r)
                gens[i, i] = r
                push!(nzcol, i)
            end
        end
        m = length(nzcol)
        return SMatrix{L, m}(view(gens, :, nzcol))
    end

    # this function is type-stable, though it doesn't prune the generators according
    # to flat dimensions of H
    function _genmat_static(H::Hyperrectangle{N, SVector{L, N}, SVector{L, N}}) where {L, N}
        gens = zeros(MMatrix{L, L, N})
        @inbounds for i in 1:L
            r = H.radius[i]
            gens[i, i] = r
        end
        return SMatrix{L, L}(gens)
    end
end
end

# --- AbstractCentrallySymmetric interface functions ---

"""
    center(H::Hyperrectangle{N}) where {N<:Real}

Return the center of a hyperrectangle.

### Input

- `H` -- hyperrectangle

### Output

The center of the hyperrectangle.
"""
function center(H::Hyperrectangle{N}) where {N<:Real}
    return H.center
end

# --- LazySet interface functions ---

"""
    rand(::Type{Hyperrectangle}; [N]::Type{<:Real}=Float64, [dim]::Int=2,
         [rng]::AbstractRNG=GLOBAL_RNG, [seed]::Union{Int, Nothing}=nothing)

Create a random hyperrectangle.

### Input

- `Hyperrectangle` -- type for dispatch
- `N`              -- (optional, default: `Float64`) numeric type
- `dim`            -- (optional, default: 2) dimension
- `rng`            -- (optional, default: `GLOBAL_RNG`) random number generator
- `seed`           -- (optional, default: `nothing`) seed for reseeding

### Output

A random hyperrectangle.

### Algorithm

All numbers are normally distributed with mean 0 and standard deviation 1.
Additionally, the radius is nonnegative.
"""
function rand(::Type{Hyperrectangle};
              N::Type{<:Real}=Float64,
              dim::Int=2,
              rng::AbstractRNG=GLOBAL_RNG,
              seed::Union{Int, Nothing}=nothing)
    rng = reseed(rng, seed)
    center = randn(rng, N, dim)
    radius = abs.(randn(rng, N, dim))
    return Hyperrectangle(center, radius)
end

"""
    translate(H::Hyperrectangle{N}, v::AbstractVector{N}; share::Bool=false
             ) where {N<:Real}

Translate (i.e., shift) a hyperrectangle by a given vector.

### Input

- `H`     -- hyperrectangle
- `v`     -- translation vector
- `share` -- (optional, default: `false`) flag for sharing unmodified parts of
             the original set representation

### Output

A translated hyperrectangle.

### Notes

The radius vector is shared with the original hyperrectangle if `share == true`.

### Algorithm

We add the vector to the center of the hyperrectangle.
"""
function translate(H::Hyperrectangle{N}, v::AbstractVector{N}; share::Bool=false
                  ) where {N<:Real}
    @assert length(v) == dim(H) "cannot translate a $(dim(H))-dimensional " *
                                "set by a $(length(v))-dimensional vector"
    c = center(H) + v
    radius = share ? H.radius : copy(H.radius)
    return Hyperrectangle(c, radius)
end

# Particular dispatch for SingleEntryVector
function ρ(d::SingleEntryVector{N}, H::Hyperrectangle{N}) where {N<:Real}
    return _ρ_sev_hyperrectangle(d, H)
end

# Particular dispatch for SingleEntryVector
function σ(d::SingleEntryVector{N}, H::Hyperrectangle{N}) where {N<:Real}
    return _σ_sev_hyperrectangle(d, H)
end


text:
"""
Method type, that you can lazily ask for all kind of information,
e.g. AST, lambdainfo, arguments, dependencies etc.
"""
type LazyMethod{T}
    signature
    cache
    decls::OrderedSet
    dependencies::OrderedSet{LazyMethod}
    parent
    codeinfo
    method
    ast::Expr
    source::String
    funcheader::String
    slots::Vector{Tuple{DataType, Symbol}}
    function (::Type{LazyMethod{T}}){T}(
            signature, parent = nothing,
            cache = Dict()
        )
        if parent == nothing
            new{T}(signature, cache, OrderedSet(), OrderedSet{LazyMethod}())
        else
            obj = new{T}(signature, cache, OrderedSet(), OrderedSet{LazyMethod}(), parent)
            #push!(parent.dependencies, obj)
            obj
        end
    end
end

LazyMethod{T}(lm::LazyMethod{T}, f, types) = LazyMethod{T}((f, Base.to_tuple_type(types)), lm, lm.cache)
LazyMethod{T}(lm::LazyMethod{T}, t) = LazyMethod{T}(t, lm, lm.cache)

LazyMethod(signature::DataType) = LazyMethod{:JL}(signature)
LazyMethod(f, types) = LazyMethod{:JL}((f, Base.to_tuple_type(types)))

"""
Like @code_typed, but will create a lazymethod!
"""
macro lazymethod(ex0)
    :($(Base.gen_call_with_extracted_types(:LazyMethod, ex0)))
end

function isfunction(x::LazyMethod)
    isa(x.signature, Tuple) &&
    length(x.signature) == 2 &&
    (isa(x.signature[1], AllFuncs) || isa(x.signature[1], Type))
end

istype(x::LazyMethod) = isa(x.signature, DataType)

function getfunction(x::LazyMethod)
    isfunction(x) || error("$(x.signature) is not a function")
    x.signature[1]
end

isintrinsic(f::IntrinsicFuncs) = true
isintrinsic(f) = false
is_native_type(x::LazyMethod, T) = false
isintrinsic(x::LazyMethod, f, signature) = isintrinsic(f)
function isintrinsic(x::LazyMethod)
    if isfunction(x)
        isintrinsic(x, x.signature...)
    else
        is_native_type(x, x.signature)
    end
end

function Base.push!(decl::LazyMethod, x::LazyMethod)
    push!(decl.dependencies, x)
end
function Base.push!{T, T2}(decl::LazyMethod{T}, signature::T2)
    push!(decl.dependencies, LazyMethod(decl, signature))
end

# Make Dicts/Set work correctly
import Base: ==
Base.hash(x::LazyMethod, h::UInt64) = hash(x.signature, h)
==(x::LazyMethod, y::LazyMethod) = x.signature == y.signature

Base.show(io::IO, x::LazyMethod) = show(io, MIME"text/plain"(), x)
function Base.show(io::IO, mt::MIME"text/plain", x::LazyMethod)
    if isfunction(x)
        print(io, x.signature[1], '(', join(to_tuple(x.signature[2]), ", "), ')')
    else
        show(io, mt, x.signature)
    end
end

function Base.show_unquoted(io::IO, x::LazyMethod, ::Int, ::Int)
    if isfunction(x)
        print(io, functionname(io, x))
    else
        print(io, typename(io, x.signature))
    end
end

function getmethod!(x::LazyMethod)
    if !isdefined(x, :method)
        x.method = Sugar.get_method(x.signature...)
    end
    x.method
end

function getcodeinfo!(x::LazyMethod)
    if !isdefined(x, :codeinfo)
        x.codeinfo = Sugar.get_lambda(code_typed, x.signature...)
    end
    x.codeinfo
end

function newslot!(m, T, name = gensym())
    slot = (T, name)
    idx = findfirst(m.slots, slot)
    if idx > 0
        # means we already have a slot with this name + type, which we can use.
        # This needs to be treated with care, since it might also be a clash.
        return TypedSlot(idx, T)
    else
        push!(m.slots, (T, name))
        return TypedSlot(length(m.slots), T)
    end
end

ssatypes(m::LazyMethod) = getcodeinfo!(m).ssavaluetypes

function getslots!(m::LazyMethod)
    if !isdefined(m, :slots)
        slotnames = Dict{Symbol, Int}()
        ci = getcodeinfo!(m)
        slots = Tuple{DataType, Symbol}[]
        for (i, (T, name)) in enumerate(zip(ci.slottypes, ci.slotnames))
            unique_name = if haskey(slotnames, name)
                id = slotnames[name] += 1
                Symbol("$(name)$(id)")
            else
                slotnames[name] = 0
                name
            end
            push!(slots, (T, unique_name))
        end
        m.slots = slots
    end
    m.slots
end

slottypes(m::LazyMethod) = map(first, getslots!(m))
slotnames(m::LazyMethod) = map(last, getslots!(m))

slottype(m::LazyMethod, s::TypedSlot) = s.typ
slottype(m::LazyMethod, s::Slot) = first(getslots!(m)[s.id])
slottype(m::LazyMethod, s::SSAValue) = ssatypes(m)[s.id + 1]
function slotname(tp::LazyMethod, ssa::SSAValue)
    Symbol(string("_ssavalue_", ssa.id))
end

function slotname(m::LazyMethod, s::Slot)
    slots = getslots!(m)
    id = s.id
    if id <= length(slots)
        last(slots[id])
    else
        # TODO check in what situation this turns up, and if it should be fixed earlier in the pipeline
        Symbol("slot_$(s.id)")
    end
end

function returntype(x::LazyMethod)
    if isclosure(x.signature[1])
        # TODO isn't there an easier way?!
        ftype = x.signature[1]
        world = typemax(UInt)
        tt = Tuple{ftype, to_tuple(x.signature[2])...}
        (ti, env, meth) = Base._methods_by_ftype(tt, 1, world)[1]
        meth = Base.func_for_method_checked(meth, tt)
        params = Core.Inference.InferenceParams(world)
        (_, code, ty) = Core.Inference.typeinf_code(meth, ti, env, false, false, params)
        ty
    else
        Base.Core.Inference.return_type(x.signature...)
    end
end

function method_nargs(f::LazyMethod)
    method = getmethod!(f)
    method.nargs
end

function type_ast(T)
    fields = Expr(:block)
    mutable = T <: Tuple ? false : T.mutable
    expr = Expr(:struct, mutable, T, fields)
    for name in fieldnames(T)
        FT = fieldtype(T, name)
        push!(fields.args, :($name::$FT))
    end
    expr
end

function has_varargs(x::LazyMethod)
    # we can't introspect intrinsics, for all I know
    isintrinsic(x) && return false, 0

    n = method_nargs(x)
    calltypes, real_signature = to_tuple(x.signature[2]), to_tuple(slottypes(x)[2:(n)])
    if calltypes == real_signature
        return false, n
    else
        # vararg must be at the end of argument list an will not match call type
        # will be a tuple in the type of the actual method.
        # Note, that all typeinf methods (code_typed etc), will still want the actual
        # call types though
        l1, l2 = last(calltypes), last(real_signature)
        return l1 != l2 && l2 <: Tuple, n
    end
end

function getfuncargs(x::LazyMethod)
    functype = x.signature[1]
    calltypes, slots = to_tuple(x.signature[2]), getslots!(x)
    n = method_nargs(x)
    args = map(2:n) do i
        argtype, name = slots[i]
        # Slot types might be less specific, e.g. when the variable is unused it might end up as Any.
        # but generally the slot type is the correct one, especially in the context of varargs.
        calltype = if !isleaftype(argtype) && length(calltypes) <= i
            argtype = calltypes[i - 1]
        end
        expr = :($(name)::$(argtype))
        expr.typ = argtype
        expr
    end
    args
end

"""
OpenCL needs to decompose structs containing device pointers, since they can't be inlined into structs.
"""
needs_decompose(x, T) = false

function getast!(x::LazyMethod)
    if !isdefined(x, :ast)
        ast = if isfunction(x)
            if isintrinsic(x)
                Expr(:block)
            else
                getcodeinfo!(x) # make sure codeinfo is present
                nargs = method_nargs(x)
                expr = sugared(x.signature..., code_typed)
                st = getslots!(x)
                for (i, (T, name)) in enumerate(st)
                    slot = TypedSlot(i, T)
                    push!(x.decls, slot)
                    push!(x, T)
                    if i > nargs # if not defined in arguments, define in body
                        tmp = :($name::$T)
                        tmp.typ = T
                        unshift!(expr.args, tmp)
                    end
                end
                expr.typ = returntype(x)
                args = Any[Expr(:inbounds, true), expr.args..., Expr(:inbounds, :pop)]
                args = Core.Inference.meta_elim_pass!(args, true, false)
                expr.args = args # remove our inbounds
                expr
            end
        else
            type_ast(x.signature)
        end
        x.ast = rewrite_ast(x, ast)
    end
    x.ast
end

function rewrite_function(m, expr)
    expr.args[1] = m
    expr
end

"""
A node to inline expressions into the AST
"""
immutable InlineNode
    deps::Vector
    expression::Expr
end

"""
Unrole `Core._apply`
"""
function rewrite_apply(m, types, expr)
    orig_expr = expr
    apply_args = expr.args[2:end]
    to_apply = resolve_func(m, expr.args[2])
    if all(x-> x <: Tuple, types[2:end])
        argtuple = apply_args[2:end]
        tuple_len = length(argtuple)
        # assign to tmp, in case it's  not a variable and instead a constructor expression
        tmp_exprs = []; args = []
        apply_types = []
        for i = 1:tuple_len
            arg_expr = argtuple[i]
            T = types[i + 1]
            push!(apply_types, to_tuple(T)...)
            # Unrole tuple expressions directly without first creating it!
            if isa(arg_expr, Expr) && arg_expr.head == :call && arg_expr.args[1] == GlobalRef(Core, :tuple)
                tupelems = map(x-> rewrite_ast(m, x), arg_expr.args[2:end])
                append!(args, tupelems)
                continue
            end
            arg = rewrite_ast(m, arg_expr)
            sym = newslot!(m, T, gensym("_apply_tmp"))
            push!(tmp_exprs, Expr(:(::), sym, T))
            push!(tmp_exprs, :($sym = $arg))
            ttup = to_tuple(T)
            tuplen = length(ttup)
            for j = 1:tuplen
                expr = Expr(:call, getindex, sym, j)
                expr.typ = ttup[j]
                childmethod = LazyMethod(m, getindex, (T, Int))
                expr = rewrite_function(childmethod, copy(expr))
                push!(args, expr)
            end
        end
        expr = typed_expr(orig_expr.typ, :call, to_apply, args...)
        childmethod = LazyMethod(m, to_apply, (apply_types...,))
        push!(m, childmethod)
        expr = rewrite_function(childmethod, expr)
        hasvarargs, n = has_varargs(childmethod)
        if hasvarargs
            # make a tuple out of varargs
            tupt = Tuple{apply_types[n - 1 : end]...}
            tup_expr = typed_expr(tupt, :call, tuple, expr.args[n:length(expr.args)]...)
            tup_expr = rewrite_ast(m, tup_expr)
            expr.args = [expr.args[1:n - 1]..., tup_expr]
        end
        return InlineNode(tmp_exprs, expr)
    end
    error("Unknown _apply construct. Found: $expr")
end

if isdefined(Base, :LambdaInfo)
    function get_static_parameters(lm::LazyMethod)
        to_tuple(getcodeinfo!(lm).sparam_vals)
    end
else
    function get_static_parameters(lm::LazyMethod)
        # TODO is this the correct way to get static parameters?! It seems to work at least
        world = typemax(UInt)
        y = Base._methods(lm.signature..., -1, world)
        isempty(y) && return ()
        x = first(y)
        to_tuple(x[2])
    end
end

function rewrite_quotenode(m::LazyMethod, node)
    node.value
end

specialized_typeof{T}(::T) = T
specialized_typeof{T}(::Type{T}) = Type{T}
unspecialized_type{T}(::Type{Type{T}}) = T
unspecialized_type{T}(::Type{T}) = T

make_typed_slot(m, slot::SlotNumber) = TypedSlot(slot.id, slottype(m, slot))
make_typed_slot(m, slot::TypedSlot) = slot
function make_typed_slot(m, slot::SSAValue)
    newslot!(m, slottype(m, slot), slotname(m, slot))
end

make_typed_slot(m, slot) = error("Lhs not a slot. Found: $(typeof(slot))")

# applicable is not overloadable
function exists(x::LazyMethod)
    istype(x) && return true # you can't construct a non existing type
    isintrinsic(x.signature[1]) && return true # must exist when julia intrinsic
    isintrinsic(x) && return true # must exist when backend intrinsic
    try
        getmethod!(x)
        return true
    catch e
        println(e)
        return false
    end
end
function isconcrete(x::LazyMethod)
    istype(x) && return isleaftype(x.signature)
    all(x-> isleaftype(x), Sugar.to_tuple(x.signature[2]))
end

Base.isvalid(x::LazyMethod) = exists(x) && isconcrete(x)

function assert_validity(x::LazyMethod)
    isvalid(x) && return
    if !isconcrete(x)
        throw(error("Method $x doesn't have concrete call types!"))
    end
    if !exists(x)
        throw(error("Method $x doesn't exist!"))
    end
end

function rewrite_vararg(lm, args, types)
    has_a_serious_case_of_the_varargs, n = has_varargs(lm)
    n = n - 1
    if has_a_serious_case_of_the_varargs
        # make a tuple out of varargs
        tup_expr = Expr(:call, tuple)
        for i in (n + 1):length(args)
            push!(tup_expr.args, args[i])
        end
        tupt = Tuple{types[(n):end]...}
        tup_expr.typ = tupt
        types = (types[1:n - 1]..., tupt)
        args = [args[1:n]..., tup_expr]
    end
    args, types
end

isclosure(FT) = false
function isclosure(FT::Type)
    FT <: Function && nfields(FT) > 0
end
resolve_module(x::Module) = x
resolve_module(x::GlobalRef) = getfield(x.mod, x.name)

is_typedomain(::Type{Type{T}}) where T = true
is_typedomain(x) = false
to_valuedomain(::Type{Type{T}}) where T = T

"""
Rewrite the ast to resolve everything statically
and infers the dependencies of an expression
"""
function rewrite_ast(m, expr)
    istype(m) && return expr
    sparams = get_static_parameters(m)
    # needs to be done in a first pass for now, since the next step relies on
    # all static params being resolved!s
    expr = first(replace_expr(expr) do expr
        if isa(expr, Expr)
            if expr.head == :static_parameter
                param = sparams[expr.args[1]]
                push!(m, specialized_typeof(param))
                return true, param
            else
                T = expr.typ
                # Tuples containing types (.., Float32, ...) don't get specialized, but we can fix this
                # because inference basically has this information.
                if T <: Tuple && T != Union{}
                    types = to_tuple(T)
                    # if is call to tuple + has datatype in there, we can use the
                    # type of it's arguments
                    if any(x-> x == DataType, types) && expr.head == :call && expr.args[1] == GlobalRef(Core, :tuple)
                        expr.typ = Tuple{map(x-> Sugar.expr_type(m, x), expr.args[2:end])...}
                    end
                end
            end
        end
        false, expr
    end)
    list = replace_expr(expr) do expr
        try
            if isa(expr, SlotNumber)
                # lets make things simple and always use typed slots
                typ = expr_type(m, expr)
                push!(m, typ)
                return true, TypedSlot(expr.id, typ)
            elseif isa(expr, SSAValue)
                # lets make things simple and always use typed slots
                typ = expr_type(m, expr)
                push!(m, typ)
                return true, make_typed_slot(m, expr)
            elseif isa(expr, NewvarNode)
                # seems like newvarnodes are redundant with the way we pre define
                # slots, so we can drop them here! # TODO is this true?
                return true, ()
            elseif isa(expr, GlobalRef)
                value = getfield(expr.mod, expr.name)
                push!(m, specialized_typeof(value))
                return true, value
            elseif isa(expr, QuoteNode)
                value = rewrite_quotenode(m, expr)
                push!(m, specialized_typeof(value))
                return true, value
            elseif isa(expr, Expr)
                args, head = expr.args, expr.head
                if head == :(=)
                    lhs = make_typed_slot(m, args[1])
                    rhs = map(x-> rewrite_ast(m, x), args[2:end])
                    res = similar_expr(expr, [lhs, rhs...])
                    if !(lhs in m.decls) # if not already declared
                        # DECLARE IT!
                        push!(m.decls, lhs)
                        typ = expr_type(m, lhs)
                        decl = Expr(:(::), lhs, typ)
                        decl.typ = typ
                        push!(m, typ)
                        return true, (decl, res) # splice in declaration
                    end
                    return true, res
                elseif head == :call
                    func = args[1]
                    types = (map(x-> expr_type(m, x), args[2:end])...)
                    FT = Sugar.expr_type(m, func)
                    return_type = expr_type(m, expr)

                    f = if isclosure(FT)
                        insert!(args, 2, func) # add self reference to call
                        FT
                    else
                        resolve_func(m, func)
                    end
                    if f == typeof
                        return true, unspecialized_type(return_type)
                    end
                    if is_typedomain(return_type) # in type domain
                        return true, to_valuedomain(return_type)
                    end
                    if f in (issubtype, ==, ===) && length(types) == 2 && all(is_typedomain, types) # in type domain
                        return true, f(to_valuedomain.(types)...)
                    end
                    if f == isa
                        T1 = expr_type(m, expr.args[2])
                        T2 = unspecialized_type(expr_type(m, expr.args[3]))
                        return true, (T1 <: T2)
                    end
                    if f == Core._apply
                        return true, rewrite_apply(m, types, expr)
                    end
                    if f == Core.getfield && types == (Module, Symbol) && isa(expr.args[3], Symbol)
                        return true, getfield(resolve_module(expr.args[2]), expr.args[3])
                    end
                    # TODO do this via deadcode elimination, dont eliminate if not dead
                    if f in (Base.throw, Base.throw_boundserror, Base.error)
                        return true, ()
                    end
                    if f == typeassert
                        @assert length(expr.args) == 3
                        args = expr.args[2:end]
                        # typeassert(::T, Type{T}) where T
                        aT, bT = Sugar.expr_type.(m, args)
                        if !(aT <: unspecialized_type(bT))
                            error("Typeassert failed: found type $aT, needs to be $(unspecialized_type(bT))")
                        end
                        res = rewrite_ast(m, expr.args[2])
                        return true, res
                    end
                    @assert isleaftype(return_type) "Found non concrete return type: $return_type"
                    lm = LazyMethod(m, f, types)
                    assert_validity(lm) # lets try to catch errors as soon as possible!

                    result = rewrite_function(lm, similar_expr(expr, args))
                    # rewrite_function is allowed to fully eliminate function calls and return single values
                    if isa(result, Expr)
                        if result.head == :call # if still is a call
                            lm = first(result.args)
                            args, types = rewrite_vararg(lm, result.args, (map(x-> expr_type(m, x), result.args[2:end])...))
                            args[1] = lm
                            result = similar_expr(expr, args)
                        end
                        # recursively rewrite arguments
                        result.args = map(x-> rewrite_ast(m, x), result.args)
                    end
                    if needs_decompose(m, return_type)
                        m.cache[expr] = rhs
                    end
                    return true, result
                end
            end
            # at this point, only values and expressions are left
            # and we're only interested in catching the dependencies of values.
            # Expr types to be expected: return, if/else, while/for,curly and so forth
            if isa(expr, LazyMethod)
                assert_validity(expr)
                push!(m, expr)
            elseif isa(expr, Union{TypedSlot, SSAValue})
                push!(m, expr_type(m, expr))
            end
        catch e
            println(STDERR, "___________________________________________________________________")
            println(STDERR, "Error in Expr rewrite! $e")
             # TODO filter errors, there are definitely errors that we can pick out that needs to be rethrown
            println(STDERR)
            println(STDERR, "Expression resulting in the error: ")
            show_source(STDERR, m, expr)
            println(STDERR)
            println(STDERR, "happening in function tree:")
            Sugar.print_stack_trace(STDERR, m)
            println(STDERR)
            println(STDERR, "Code of the context this error occured in: ")
            # we need to use `sugared` directly, since otherwise it will
            # try to rewrite the expression and exactly run into this error while printing the error
            show_source(STDERR, m, Sugar.sugared(m.signature..., code_typed))
            println(STDERR)
            rethrow(e)
        end
        false, expr
    end
    expr = first(list)
    if isa(expr, Expr)
        remove_inlinenodes(expr, (expr.args, 1))
    else
        return expr
    end
end

function show_source(io::IO, m::LazyMethod, body = getast!(m))
    src = getcodeinfo!(m)
    emph_io = Base.IOContext(io, :TYPEEMPHASIZE => true)
    sn = [String.(Sugar.slotnames(m))...]
    Base.show_unquoted(
        Base.IOContext(
            Base.IOContext(emph_io, :SOURCEINFO => src),
            :SOURCE_SLOTNAMES => sn
        ),
        body, 2
    )
end

function type_dependencies!(lm::LazyMethod)
    typ = lm.signature
    if isleaftype(typ) || isa(typ, Type)
        for name in fieldnames(typ)
            typ == Module && continue
            ft = fieldtype(typ, name)
            # Tuples can be types that are not possible to instantiate, e.g. Tuple{1, 1}
            if !(typ <: Tuple && !isa(ft, DataType))
                push!(lm, ft)
            end
        end
        for T in typ.parameters
            isa(T, DataType) && push!(lm, T)
        end
    else
        print_stack_trace(STDERR, lm)
        error("Found non concrete type: $(lm.signature)")
    end
end

function dependencies!(lm::LazyMethod, recursive = false)
    deps = OrderedSet{typeof(lm)}()
    if isfunction(lm)
        for elem in to_tuple(lm.signature[2])
            push!(lm, elem)
        end
        RT = returntype(lm)
        if isa(RT, DataType) && RT != Void && RT != Union{}
            push!(lm, RT)
        end
        getast!(lm) # walks ast && insertes dependencies
    else
        type_dependencies!(lm)
    end
    for elem in lm.dependencies
        if recursive
            deps2 = dependencies!(elem, true)
            for elem2 in deps2 # lol there is no append! ?!
                push!(deps, elem2)
            end
        end
        push!(deps, elem)
    end
    deps
end

remove_inlinenodes(node, insertion) = node

function remove_inlinenodes(node::InlineNode, insertion)
    list = Any[nothing] # cant be empty for splice! to work
    results = remove_inlinenodes.(node.deps, ((list, 1:1),))
    filter!(x-> x != nothing, list)
    splice!(insertion[1], insertion[2], vcat(list, results))
    remove_inlinenodes(node.expression, insertion)
end

function remove_inlinenodes(expr::Expr, insertion)
    new_expr = similar_expr(expr)
    if expr.head == :block
        insert_list = new_expr.args # save last point where we can savely insert expressions
        for (i, elem) in enumerate(expr.args)
            res = remove_inlinenodes(elem, (insert_list, (i:(i - 1))))
            push!(insert_list, res)
        end
    else
        new_expr.args = map(expr.args) do elem
            remove_inlinenodes(elem, insertion)
        end
    end
    new_expr
end

function getfuncheader!(x::LazyMethod)
    if !isdefined(x, :funcheader)
        x.funcheader = if isfunction(x)
            sprint() do io
                args = getfuncargs(x)
                show_function(io, x.signature...)
                Base.show_enclosed_list(io, '(', args, ", ", ')', 0, 0)
                print(io, "::", returntype(x))
            end
        else
            ""
        end
    end
    x.funcheader
end

function getfuncsource(x::LazyMethod)
    sprint() do io
        Base.show_unquoted(io, getast!(x), 0, 0)
    end
end

function gettypesource(x::LazyMethod)
    sprint() do io
        dump(io, x.signature)
    end
end

function print_stack_trace(io, x::LazyMethod)
    println(io, "Sugar stack trace:")
    i = 1
    while true
        println(io, "  [$i] ", x)
        println(io)
        i += 1
        isdefined(x, :parent) || break
        x = x.parent
    end
    return
end

function getbodysource!(x::LazyMethod)
    if istype(x)
        gettypesource(x)
    else
        getfuncsource(x)
    end
end

function getsource!(x::LazyMethod)
    if !isdefined(x, :source)
        str = getbodysource!(x)
        if isfunction(x)
            str = getfuncheader!(x) * "\n" * str
        end
        x.source = str
    end
    x.source
end

"""
Type of an expression in the context of a LazyMethod
"""
expr_type(x) = expr_type(nothing, x)

expr_type(lm, x::Expr) = x.typ
expr_type(lm, x::GlobalRef) = specialized_typeof(getfield(x.mod, x.name))
expr_type{T}(lm, x::Type{T}) = Type{T}
expr_type{T}(lm, x::T) = T
expr_type(lm, x::InlineNode) = expr_type(lm, x.expression)

expr_type(lm::Void, x::TypedSlot) = x.typ
expr_type(lm::LazyMethod, x::TypedSlot) = x.typ

function expr_type(lm::Void, slot::Union{Slot, SSAValue})
    error("Can't get expression type of an untyped SSAValue/Slot without a propper method context")
end
expr_type(lm::LazyMethod, slot::Union{Slot, SSAValue}) = slottype(lm, slot)
function expr_type(lm, m::LazyMethod)
    isfunction(m) ? typeof(getfunction(m)) : m.signature
end

function instance{F <: Function}(x::Type{F})
    F.instance
end
instance{T}(x::Type{T}) = x

extract_type{T}(x::Type{T}) = T

"""
Takes any value found in the context of a LazyMethod and returns
A concrete function!
"""
function resolve_func(m, f::LazyMethod)
    if isfunction(f)
        getfunction(f)
    else
        f.signature
    end
end
resolve_func(m, f::AllFuncs) = f
resolve_func{T}(m, X::Type{Type{T}}) = T
resolve_func{T}(m, X::Type{T}) = X
resolve_func(m, f::Union{GlobalRef, Symbol}) = eval(f)
function resolve_func(m, val::Union{Slot, SSAValue, Expr})
    f = expr_type(m, val)
    if isclosure(f)
        return resolve_func(m, f)
    else
        if f <: AllFuncs
            instance(f)
        else
            resolve_func(m, f)
        end
    end
end

function replace_slots(m::LazyMethod, ast)
    first(Sugar.replace_expr(ast) do expr
        if isa(expr, Slot) || isa(expr, SSAValue)
            return true, slotname(m, expr)
        elseif isa(expr, NewvarNode)
            return true, :(local $(slotname(m, expr.slot)))
        else
            return false, expr
        end
    end)
end

function get_func_expr(m::LazyMethod, name = Symbol(getfunction(m)))
    expr = sugared(m.signature..., code_lowered)
    get_func_expr(m, expr, name)
end

function get_func_expr(m::LazyMethod, expr::Expr, name = Symbol(getfunction(m)))
    body = replace_slots(m, expr)
    functype = m.signature[1]
    calltypes, slots = to_tuple(m.signature[2]), getslots!(m)
    n = method_nargs(m)
    args = map(2:n) do i
        argtype, name = slots[i]
        # Slot types might be less specific, e.g. when the variable is unused it might end up as Any.
        # but generally the slot type is the correct one, especially in the context of varargs.
        calltype = if !isleaftype(argtype) && length(calltypes) <= i
            argtype = calltypes[i - 1]
        end
        expr = :($(name)::$(argtype))
        expr.typ = argtype
        expr
    end
    Expr(:function,
        Expr(:call, name, args...),
        body
    )
end

function show_comment(io, comment)
    println(io, "# ", comment)
end

function print_dependencies(io, method, visited = Set())
    (method in visited) && return
    push!(visited, method)
    for elem in dependencies!(method)
        print_dependencies(io, elem, visited)
    end
    isintrinsic(method) && return
    try
        show_comment(io, method.signature)
        println(io, getsource!(method))
    catch e
        println(STDERR, "___________________________________________________________________")
        println(STDERR, "Can't compile dependency: $(method.signature)")
         # TODO filter errors, there are definitely errors that we can pick out that needs to be rethrown
        println(STDERR, e)
        display(catch_stacktrace())
        println(STDERR, "happening in function tree:")
        Sugar.print_stack_trace(STDERR, method)
        println(STDERR)
        println(STDERR, "___________________________________________________________________")
    end
end

# interface for transpilers
typename(io::IO, T) = string(T)
function _typename end
function functionname(io::IO, lm::LazyMethod)
    if isfunction(lm)
        string(Symbol(getfunction(lm)))
    else
        error("Not a function: $lm")
    end
end
function show_name end
function show_type end
function show_function end

function supports_overloading end
function vecname(io::IO, T)
    println(io, T)
end


text:
function scatter(data::CuMatrix, targets::CuVector, bins, ⊕)
    function kernel!(output, data, targets)
        thread = threadIdx().x + (blockIdx().x - 1) * blockDim().x - 1
        i = thread % size(output, 1) + 1
        j = thread ÷ size(output, 1) + 1

        @inbounds if i <= size(output, 1) && j <= length(targets)
            @atomic output[i, targets[j]] = ⊕(output[i, targets[j]], data[i, j])
        end
        return
    end

    # TODO: FIX TYPES
    output = CUDA.zeros(eltype(data), size(data, 1), bins)

    threads = 256
    blocks = ceil(Int, size(output, 1) * length(targets) / threads)
    @cuda blocks=blocks threads=threads kernel!(output, data, targets)

    return output
end

# Defining the fused message-aggregate operation
# function gather(X::CuMatrix, A::CuSparseMatrixHCOO, ⊕)
#     function kernel!(O, X, I, J, V)
#         thread = threadIdx().x + (blockIdx().x - 1) * blockDim().x - 1
#         i = thread % size(O, 1) + 1
#         j = thread ÷ size(O, 1) + 1

#         @inbounds if i <= size(O, 1) && j <= length(J)
#             @atomic O[i, J[j]] = ⊕(O[i, J[j]], X[i, I[j]] * V[j])
#         end
#         return
#     end

#     # TODO: FIX TYPES
#     O = CUDA.zeros(size(X, 1), size(A, 2))

#     threads = 256
#     blocks = ceil(Int, size(O, 1) * length(A.nzVal) / threads)
#     @cuda blocks=blocks threads=threads kernel!(O, X, A.rowInd, A.colInd, A.nzVal)

#     return O
# end


text:
"""
    step!(updater)

Perform a single step to update the system fields
using the methods defined by a provided `AbstractFieldUpdater`.
"""
step!(updater::AbstractFieldUpdater) = nothing

setup!(species::AbstractFieldUpdater, sys::FieldSystem) = nothing

"""
	updater_with_system(type, sys; kwargs...)

Return a field updater allocated for the provided system.
"""
function updater_with_system(TU::Type{<:AbstractFieldUpdater}, sys::FieldSystem; kwargs...)
	updater = TU(; kwargs...)
	setup!(updater, sys)
	return updater
end


text:
module CApi
    using Libdl

    const fdb_c = "libfdb_c"
    const libfdb = Ref{Ptr{Nothing}}(C_NULL)

    function __init__()
        global libfdb
        libfdb[] = Libdl.dlopen_e(fdb_c)

        (libfdb[] == C_NULL) && error("Can not open libfdb_c shared library. Please make sure you have Foundation DB client libraries installed.")
    end

    include("common.jl")
    include("ccalls.jl")

    export FDB_API_VERSION
    export FDBNetworkOption, FDBClusterOption, FDBDatabaseOption, FDBTransactionOption, FDBStreamingMode, FDBMutationType, FDBConflictRangeType, FDBErrorPredicate
    export fdb_select_api_version_impl, fdb_select_api_version, fdb_get_max_api_version, fdb_get_client_version, fdb_network_set_option, fdb_setup_network,
            fdb_run_network, fdb_stop_network, fdb_add_network_thread_completion_hook, fdb_future_cancel, fdb_future_destroy, fdb_future_block_until_ready,
            fdb_future_is_ready, fdb_future_set_callback, fdb_future_release_memory, fdb_future_get_error, fdb_future_get_keyvalue_array,
            fdb_future_get_version, fdb_future_get_key, fdb_future_get_cluster, fdb_future_get_database, fdb_future_get_value, fdb_future_get_string_array,
            fdb_create_cluster, fdb_cluster_destroy, fdb_cluster_set_option, fdb_cluster_create_database, fdb_database_destroy, fdb_database_set_option,
            fdb_database_create_transaction, fdb_transaction_destroy, fdb_transaction_set_option, fdb_transaction_cancel, fdb_transaction_set_read_version,
            fdb_transaction_get_read_version, fdb_transaction_get_addresses_for_key, fdb_transaction_set, fdb_transaction_atomic_op, fdb_transaction_clear,
            fdb_transaction_clear_range, fdb_transaction_watch, fdb_transaction_commit, fdb_transaction_get_committed_version, fdb_transaction_get_versionstamp,
            fdb_transaction_on_error, fdb_transaction_reset, fdb_transaction_add_conflict_range, fdb_transaction_get, fdb_transaction_get_key,
            fdb_transaction_get_range, fdb_get_error, fdb_error_predicate
    export fdb_run_network_in_thread, fdb_future_block_until_ready_in_thread
    export fdb_error_t, fdb_bool_t, fdb_transaction_ptr_t, fdb_future_ptr_t, fdb_cluster_ptr_t, fdb_database_ptr_t, fdb_network_option_t, fdb_cluster_option_t,
            fdb_database_option_t, fdb_transaction_option_t, fdb_streaming_mode_t, fdb_mutation_type_t, fdb_conflict_range_type_t, fdb_error_predicate_t,
            fdb_kv_t

    # APIs removed
    #export fdb_transaction_get_range_selector, fdb_future_is_error
end


text:
using Omega
using Spec
using Test
using Pkg

# FIXME: Make this a package
include("TestLib.jl")

# Add TestModels as submodule
Pkg.develop(PackageSpec(url=joinpath(dirname(pathof(Omega)), "..", "test", "OmegaTestModels")))

walktests(Omega, exclude = ["typestable.jl", "simple.jl"])


text:
using Test

include("CIFAR10.jl")
include("tests/DARTSModelTest.jl")
include("tests/MaskedTrainingTest.jl")
include("tests/UtilsTest.jl")

max_stars_repo_name: huangyxi/DifferentiableNAS

max_issues_repo_name: huangyxi/DifferentiableNAS

max_forks_repo_name: huangyxi/DifferentiableNAS


text:
module Runtests

using Test, MatrixPencils

@testset "Test MatrixPencils.jl" begin
    include("test_klf.jl")
    include("test_klfapps.jl")
    include("test_regular.jl")
    include("test_sklf.jl")
    include("test_sklfapps.jl")
    include("test_lstools.jl")
    include("test_pmtools.jl")
    include("test_pmapps.jl")
    include("test_rmtools.jl")
    include("test_rmapps.jl")
    include("test_gsfstab.jl")
    include("test_gsep.jl")
    include("test_gsklf.jl")
end

end


text:
using FactCheck
include(Pkg.dir("PseudoGenomes", "src","pseudogenome-misc.jl"))

fastafile1 = Pkg.dir("PseudoGenomes","testdata","test.fasta")
fastafile2 = Pkg.dir("PseudoGenomes","testdata","expected.fasta")
outputfasta = Pkg.dir("PseudoGenomes","testdata","diploid.fasta")
id1="abc"
id2="def"

make_diploid(fastafile1, id1, fastafile2, id2, outputfasta)


text:
@assert isequal(deparse(:(cos(x) + sin(x))), "cos(x) + sin(x)")
@assert isequal(deparse(:(cos(x) + sin(x) + exp(-x))), "cos(x) + sin(x) + exp(-x)")


text:
using Test
using IncrementalInference
using Manifolds
using DistributedFactorGraphs
##

import IncrementalInference: getSample

mutable struct PartialDim2{T} <: AbstractPrior
  Z::T
  partial::Tuple{Int}
end

PartialDim2(Z::D) where {D <: IIF.SamplableBelief} = PartialDim2(Z, (2,))

DFG.getManifold(::PartialDim2) = TranslationGroup(2)

getSample(cfo::CalcFactor{<:PartialDim2}) = [0; rand(cfo.factor.Z)]

##

@testset "Test partial dimensions on prior are correct" begin
##

fg = initfg()

v0 = addVariable!(fg, :x0, ContinuousEuclid{2})

f0 = addFactor!(fg, [:x0], PartialDim2(Normal()))

@test IIF._getDimensionsPartial(f0) == [2]

bel, infd = propagateBelief(fg, v0, [f0;])

@test isPartial(bel)

##

dens = Vector{ManifoldKernelDensity}()
IIF.proposalbeliefs!(fg, :x0, [f0], dens)

pts = getPoints(dens[1], false)

##

predictbelief(fg, :x0, [:x0f1;])
@test true

##
end

@testset "test propagateBelief returning a partial" begin
##

fg = initfg()

v0 = addVariable!(fg, :x0, ContinuousEuclid{2})

pts = [randn(1) for _ in 1:1000];
mkd = manikde!(TranslationGroup(1), pts, bw=[0.1;])
pp = PartialPrior(mkd, (2,))
f0 = addFactor!(fg, [:x0;], pp, graphinit=false)

##

bel, infd = propagateBelief(fg, v0, [f0;])
@test isPartial(bel)

##

doautoinit!(fg, :x0)

# check the number of points in the graph value store
@show getSolverParams(fg).N
@test length(getPoints(getBelief(fg, :x0))) == getSolverParams(fg).N
@info "PassThrough factors currently work different and will pass the full N=1000 count through to the graph."

##
end


text:
module DynamicMixtures

using Distributions: Beta, Dirichlet, Multinomial, MultivariateNormal, pdf
using DynamicLinearModels
using LinearAlgebra
using StatsBase

include("dirichlet.jl")
include("dynamic.jl")

end # module


text:
using RegularizedRegression: ScadRegression, McpRegression

@testset "SCAD regression" begin
    for _ in 1:NumTestRepetitions
        test_learner_with_includeIntercept(ScadRegression, 5.0)
    end
end

@testset "MCP regression" begin
    for _ in 1:NumTestRepetitions
        test_learner_with_includeIntercept(McpRegression, 5.0)
    end
end


text:
module KissConv

using OffsetArrays
export conv

struct Inner end
struct Outer end

function conv_axes(arr1, arr2, ::Inner)
    if ndims(arr1) != ndims(arr2)
        throw(DimensionMismatch("Cannot convolve arrays of different dimensions."))
    end
    axs = map(axes(arr1), axes(arr2)) do r1, r2
        i_start = first(r1) +  last(r2)
        i_stop  = last(r1)  + first(r2)
        i_start:i_stop
    end
    return axs
end

function conv_axes(arr1, arr2, ::Outer)
    if ndims(arr1) != ndims(arr2)
        throw(DimensionMismatch("Cannot convolve arrays of different dimensions."))
    end
    axs = map(axes(arr1), axes(arr2)) do r1, r2
        i_start = first(r1) + first(r2)
        i_stop  = last(r1)  + last(r2)
        i_start:i_stop
    end
    return axs
end

function conv_out(arr1, arr2, mode)
    T = promote_type(eltype(arr1), eltype(arr2))
    axs = conv_axes(arr1, arr2, mode)
    return similar(arr1, T, axs)
end

function conv!(out, arr1, arr2, ::Inner)
    z = zero(eltype(out))
    @inbounds for I in CartesianIndices(out)
        out[I] = z
        @simd for J in CartesianIndices(arr2)
            IJ = CartesianIndex(map(-, Tuple(I), Tuple(J)))
            out[I] += arr1[IJ] * arr2[J]
        end
    end
    return out
end

function conv(arr1, arr2, mode=Inner())
    out = conv_out(arr1, arr2, mode)
    return conv!(out, arr1, arr2, mode)
end

end#module


text:
# module Bukdu

function Base.getproperty(c::C, prop::Symbol) where {C <: ApplicationController}
    if prop in (:params, :query_params, :path_params, :body_params)
        getfield(c.conn, prop)
    else
        getfield(c, prop)
    end
end

# module Bukdu

max_stars_repo_name: wookay/TestBukdu

max_issues_repo_name: wookay/TestBukdu

max_forks_repo_name: wookay/TestBukdu


text:
using Indicators
using Temporal
using Test
using Random
using Statistics

const global N = 252
const global X0 = 50.0
const global SEED = 1

TEST_FILES = [
    "util.jl",
    "run.jl",
    "ma.jl",
    "mom.jl",
    "vol.jl",
    "reg.jl",
    "patterns.jl",
    "chaos.jl",
    "trendy.jl",
]

@inbounds for testfile in TEST_FILES
    include(testfile)
end