
use coro
use core
use mem
use time

value mem_minimum_trigger (8 * 1024)

// Core
global gc : Gc (@undefined)

struct Gc {
    mutex: core:MutexStruct[void] (core:MutexStruct[void].new())
    // Lists
    globals: Bump (Bump.new())
    stack_items: Bump (Bump.new())
    prev_stack_items: Bump (Bump.new())
    updated_list: Bump (Bump.new())
    blanks: Bump (Bump.new())
    dis_owned_list: Bump (Bump.new())
    re_own_list: Bump (Bump.new())
    shared_items: Bump (Bump.new())
    mark_list: Lifo (Lifo.new())
    // Refs
    stack_root: ptr (stack_root)
    stack_top_ptr: ptr[ptr] (@ref(stack_top))
    stack_backup: ptr (stack_backup)
    stack_backup_size_ptr: ptr[uint] (@ref(stack_backup_size))
    coros_ptr: ptr[Array[?coro:Coro]] (@ref(coro:g_coros))
    pools: ptr (pools)
    poolc_ptr: ptr[uint] (@ref(poolc))
    //
    mark_shared: bool (false)
    dont_stop: bool (false)
    disable: bool (true)
    did_shutdown: bool (false)
    // Counts
    mem_marked: uint (0)
    mem_trigger: uint (mem_minimum_trigger)
    mem_new: uint (0)
    dis_own_count: uint (0)
    collect_count: uint (0)
    trigger_list: [uint x 5] ({0...})
    dis_own_list: [uint x 5] ({0...})
    marked_max_reset_at : uint (0)
    marked_max : uint (0)
    marked_max_next : uint (0)
    mem_usage_thread : uint (0)

    + static fn init() Gc {
        return Gc {}
    }

    fn lock() { this.mutex.lock() }
    fn unlock() { this.mutex.unlock() }

    fn collect() {
        if this.dont_stop : panic("Started GC while adding shared memory (bug)")
        if stack_top > ((&stack_root).@cast(ptr) + ((STACK_ITEMS_MAX / 4) * 3) * size_of(ptr)) : panic("Stack overflow: too much recursion")

        if this.disable : return
        this.disable = true

        // 
        if !this.did_shutdown : this.collect_stack_items()

        // Check if items have dissapeared from the stack
        this.loop_previous_stack_items()

        // Mark stack items
        if !this.did_shutdown : this.loop_stack_items(Gc.mark_stack_item)

        //
        this.dis_own_count = 0
        this.loop_dis_own()
        if !this.did_shutdown : this.loop_updates()
        if !this.did_shutdown : this.loop_re_own()

        this.check_blanks()

        // Reset pools
        if this.mark_shared : this.mark_shared_items()
        else : reset_pools(this.pools, this.poolc_ptr[0])

        // Clear stack items list
        if !this.did_shutdown : this.clear_stack_items()

        if verify && !running_shared && !this.did_shutdown : this.leak_check()

        // Reset mem_new
        this.mem_new = this.mem_marked
        if this.mem_marked > this.marked_max_next : this.marked_max_next = this.mem_marked
        if this.mem_marked > this.marked_max : this.marked_max = this.mem_marked
        let time = time:microtime()
        if time > this.marked_max_reset_at {
            this.marked_max_reset_at = time + 200 * 1000 // 200ms
            this.marked_max_next = 0
            this.marked_max = this.marked_max_next
        }

        // Learn from the past
        this.trigger_list[this.collect_count % 5] = this.mem_trigger
        this.dis_own_list[this.collect_count % 5] = this.dis_own_count
        this.collect_count++

        // Update trigger point
        let high = this.mem_marked / 100 * 120 + 1024
        let high2 = high / 100 * 150
        let low = this.mem_trigger / 100 * 95
        if low > high : high = low
        if low > high2 : high2 = low
        this.mem_trigger = high

        // Check for best match in the past
        let bar : uint = 2_999_999
        let i = 5
        while i-- > 0 {
            let t = this.trigger_list[i]
            if t == 0 : continue
            let d = this.dis_own_list[i]
            if d < bar && t >= high && t <= high2 {
                this.mem_trigger = t
                bar = d
            }
        }

        //
        if this.mem_trigger < this.marked_max : this.mem_trigger = this.marked_max

        //
        this.disable = false
    }

    fn leak_check() {
        this.loop_stack_items(fn(item: ptr){ mark_leak_rec(item, true) })
        this.loop_stack_items(fn(item: ptr){ mark_leak_rec(item, false) })
    }

    static fn mark_stack_item(item: ptr) {
        let data = (@offset(item, u8, -8)).@cast(GcData)
        if data.is_shared() : return // Prevent race conditions
        if data.is_not_owned() {
            mark_used(item)
            gc.prev_stack_items.add_ptr(item)
        }
    }

    fn loop_previous_stack_items() {

        let discs = this.dis_owned_list
        let list = this.prev_stack_items
        let data = list.data
        let adr = data
        let end = adr + list.index
        list.reset()

        while adr < end {
            let item = @ptrv(adr, ptr)
            let data = (@offset(item, u8, -8)).@cast(GcData)
            adr += size_of(ptr)

            #if TEST
            if item == null : panic("Invalid previous stack item (value is null)")
            #end

            // A stack item can become shared
            if data.is_shared() {
                data.set_no_owner()
                continue
            }

            if data.is_on_stack() {
                let adr = list.get(size_of(ptr))
                @ptrv(adr, ptr) = item
            } else {
                let adr = discs.get(size_of(ptr))
                @ptrv(adr, ptr) = item
                data.set_no_owner()
            }
        }
    }

    fn loop_dis_own() {

        let list = this.dis_owned_list
        let i : uint = 0 

        // The dis-own list can grow while running this code
        while i < list.index {
            let item = @ptrv(list.data, ptr, i / size_of(ptr))
            i += size_of(ptr)

            #if TEST
            if item == null : panic("Dis own list contains a null value")
            #end

            let data = (@offset(item, u8, -8)).@cast(GcData)

            // A dis-owned item can become shared, so we need to make sure it's ignored
            if data.is_no_owner_not_shared() {
                dis_own_rec(item)
            }
        }

        list.reset()
    }

    fn loop_re_own() {

        let dis_own_list = this.dis_owned_list
        let list = this.re_own_list
        let data = list.data
        let adr = data
        let end = adr + list.index
        list.reset()

        while adr < end {
            let item = @ptrv(adr, ptr)
            let data = (@offset(item, u8, -8)).@cast(GcData)
            adr += size_of(ptr)

            // if data.is_shared() : panic("Shared re-own item")

            if data.is_new() && data.co_count > 0 {
                mark_used(item)
                data.set_no_owner()
                dis_own_list.add_ptr(item)
            }
        }
    }

    fn loop_updates() {

        let list = this.updated_list
        let data = list.data
        let adr = data
        let end = adr + list.index
        list.reset()

        let ml = this.mark_list

        while adr < end {
            let item = @ptrv(adr, GcItem)
            adr += size_of(ptr)

            let data = gcdata(item)
            data.remove_in_updates()

            if data.is_owned_not_shared() {
                ml.add(item)
            }
        }

        mark_used(null)
    }

    fn check_blanks() {

        let list = this.blanks
        let data = list.data
        let adr = data
        let end = adr + list.index
        list.reset()

        while adr < end {
            let item = @ptrv(adr, GcItem)
            adr += size_of(ptr)

            let data = gcdata(item)
            data.remove_in_blanks()
            if data.is_not_new() : continue

            free_blank(item)
        }
    }

    //////////////////////////
    // Loop stack
    //////////////////////////

    fn loop_stack_items(func: fnRef(ptr)()) {
        let list = this.stack_items
        let adr = list.data
        let end = adr + list.index

        while adr < end {
            let item = @ptrv(adr, GcItem)
            adr += size_of(ptr)
            func(item)
        }
    }

    fn clear_stack_items() {
        let list = this.stack_items
        let adr = list.data
        let end = adr + list.index
        list.reset()

        while adr < end {
            let item = @ptrv(adr, GcItem)
            adr += size_of(ptr)
            let data = gcdata(item)
            data.co_count--
            data.remove_on_stack()
        }
    }
    fn collect_stack_item(item: ptr) {
        let data = gcdata(item)
        if data.is_on_stack() : return
        data.set_on_stack()
        data.co_count++
        this.stack_items.add_ptr(item)
    }
    fn collect_stack_items() {

        // Globals
        let g_adr = this.globals.data
        let g_end_adr : ptr = g_adr + this.globals.index
        while g_adr < g_end_adr {
            let ref = @ptrv(g_adr, ptr)
            let item = @ptrv(ref, ?ptr)
            if isset(item) : this.collect_stack_item(item)
            g_adr += size_of(ptr)
        }

        // Stack
        let adr = this.stack_root
        let top : ptr = this.stack_top_ptr[0]
        while adr < top {
            let item = @ptrv(adr, ?ptr)
            if isset(item) : this.collect_stack_item(item)
            adr += size_of(ptr)
        }

        // Backup
        adr = this.stack_backup
        let size = this.stack_backup_size_ptr[0]
        top = adr + size
        while adr < top {
            let item = @ptrv(adr, ?ptr)
            if isset(item) : this.collect_stack_item(item)
            adr += size_of(ptr)
        }

        let coros = this.coros_ptr[0]
        each coros as coro {
            if isset(coro) {
                let adr = coro.stack
                if isset(adr) {
                    let top = adr + coro.stack_size
                    while adr < top {
                        let item = @ptrv(adr, ?ptr)
                        if isset(item) : this.collect_stack_item(item)
                        adr += size_of(ptr)
                    }
                }
            }
        }
    }

    //////////////////////////
    // Shared
    //////////////////////////

    fn mark_shared_items() {
        this.mark_shared = false
        // Loop over stack items
        this.loop_stack_items(fn(item: GcItem) {
            let data = gcdata(item)
            // if data.is_shared() : update_mark(item)
            if data.is_shared() : share(item)
        })
    }

    fn update_marks() {
        let list = this.shared_items
        let data = list.data
        let adr = data
        let end = adr + list.index

        while adr < end {
            let item = @ptrv(adr, GcItem)
            adr += size_of(ptr)
            let data = gcdata(item)
            if data.is_owned() || data.co_count > 0 {
                share(item)
            }
        }
    }

    // fn validate_shared() {
    //     let list = this.shared_items
    //     let data = list.data
    //     let adr = data
    //     let end = adr + list.index

    //     while adr < end {
    //         let item = @ptrv(adr, GcItem)
    //         adr += size_of(ptr)
    //         let data = gcdata(item)

    //         if !data.is_shared() : panic("Shared items contains non-shared")
    //         if data.state == state_new : panic("Shared items contains new_state")
    //     }
    // }

    fn clear_shared() {
        let list = this.shared_items
        let data = list.data
        let adr = data
        let end = adr + list.index
        list.reset()

        while adr < end {
            let item = @ptrv(adr, GcItem)
            adr += size_of(ptr)
            let data = gcdata(item)

            if data.is_marked() {
                list.add_ptr(item)
                continue
            }

            free_shared_item(item)
        }
    }

    //////////////////////////
    // Shutdown
    //////////////////////////

    + fn shutdown() {
        this.did_shutdown = true
        this.collect()

        // Free blocks or store them in unused-block-list if they still contain items
        pool_lock.lock()
        loop_all_blocks(fn(block: Block)() {
            if block.used == 0 {
                mem:free(block)
            } else {
                add_unused_block(block)
            }
        })
        pool_lock.unlock()

        shared_lock.lock()
        dump_shared(this.shared_items)
        shared_lock.unlock()

        //
        this.mutex.free()
        //
        this.globals.free()
        this.stack_items.free()
        this.updated_list.free()
        this.blanks.free()
        this.dis_owned_list.free()
        this.re_own_list.free()
        this.shared_items.free()
        this.mark_list.free()
        //
        mem:free(this)
    }
}
