Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.42.0

0.42.0 / src / std / ownership / cycles.lucb

#==============================================================================================
#
#   cycles - The cycle collector
#
#   DESCRIPTION:
#       A synchronous trial-deletion collector for reference cycles on the owning thread,
#       run when the candidate set fills or at the end of a run. An object whose type is
#       acyclic is never a candidate and never walked into: it cannot be part of a cycle,
#       and every visitor skipping it keeps the trial counts balanced.
#
#==============================================================================================

# mark: The cycle collector ====================================================================
pub let candidate_limit: usize = 1024
local var roots: Object*[]
local var root_count: usize = 0
local var whites: Object*[]
local var white_count: usize = 0
local var collector_running: bool = false
## `LUCE_CYCLE_STRESS` in the environment: 0 not read yet, 1 absent, 2 present.
var stress_state: @u8
extern func stress_getenv as "getenv"(name: c.str) -> c.str?

## Whether `LUCE_CYCLE_STRESS` is set: the collector then runs at every new candidate, so a
## collection happens at every release that could leave a cycle, in `clear`, `remove`, a
## `deinit` and a failed `init` too (the stress mode of luce's tools/cycles_fuzz.py). The
## environment is read once; every thread reads the same answer.
func stressed() -> bool:
    var state = stress_state.load(.relaxed)
    if state == 0:
        state = 2 if stress_getenv("LUCE_CYCLE_STRESS") != none else 1
        stress_state.store(state, .relaxed)
    return state == 2

func push_root(o: Object*):
    if root_count == roots.length:
        roots = grow(roots, root_count, candidate_limit)
    roots[root_count] = o
    root_count += 1

func push_white(o: Object*):
    if white_count == whites.length:
        whites = grow(whites, white_count, 256)
    whites[white_count] = o
    white_count += 1

func possible_root(o: Object*):
    if color_of(o) != purple:
        set_color(o, purple)
        if not has(o, buffered):
            o.flags |= buffered
            push_root(o)
            if (root_count >= candidate_limit or stressed()) and not collector_running:
                collect()

## An object no walk enters: a literal, an acyclic one, or one `abandon` is dropping.
func skipped(child: Object*) -> bool:
    return has(child, immortal) or child.info.acyclic or has(child, abandoning)

func visit_mark_gray(child: Object*, context: void*):
    if skipped(child):
        return
    check_thread(child)
    child.strong -= 1
    mark_gray(child)

func mark_gray(o: Object*):
    if color_of(o) != gray:
        set_color(o, gray)
        o.info.trace(o, visit_mark_gray, (void*)o)

func visit_scan(child: Object*, context: void*):
    if skipped(child):
        return
    check_thread(child)
    scan(child)

func visit_scan_black(child: Object*, context: void*):
    if skipped(child):
        return
    check_thread(child)
    child.strong += 1
    if color_of(child) != black:
        scan_black(child)

func scan(o: Object*):
    if color_of(o) == gray:
        if o.strong > 0:
            scan_black(o)
        else:
            set_color(o, white)
            o.info.trace(o, visit_scan, (void*)o)

func scan_black(o: Object*):
    set_color(o, black)
    o.info.trace(o, visit_scan_black, (void*)o)

func visit_gather(child: Object*, context: void*):
    if skipped(child):
        return
    check_thread(child)
    gather(child)

## The white objects, each once, flagged as being collected (`sort_whites` orders them).
func gather(o: Object*):
    if color_of(o) == white and not has(o, collecting):
        o.flags |= collecting
        push_white(o)
        o.info.trace(o, visit_gather, (void*)o)

## Undo the trial deletion of one edge out of a garbage object. `mark_gray` took one count
## for every edge it walked; `scan_black` gave back those out of objects found reachable, but
## an edge out of garbage is still missing, whether it points at more garbage or at a live
## object. Restoring every one lets each field release below be an ordinary release: a live
## object loses exactly the reference the garbage held, where it once lost two.
func visit_restore(child: Object*, context: void*):
    if skipped(child):
        return
    check_thread(child)
    child.strong += 1

## The garbage in the order its objects were made, oldest first (their generations): what a
## cycle's deinits and the releases of its fields follow, the same in a compiled program and
## Luce's interpreter whatever let go of what when (a heap sort, in place).
func sort_whites():
    var start = white_count // 2
    while start > 0:
        start -= 1
        sift_white(start, white_count)
    var end = white_count
    while end > 1:
        end -= 1
        let top = whites[0]
        whites[0] = whites[end]
        whites[end] = top
        sift_white(0, end)

func sift_white(first: usize, end: usize):
    var root = first
    while root * 2 + 1 < end:
        var child = root * 2 + 1
        if child + 1 < end and whites[child + 1].generation > whites[child].generation:
            child += 1
        if whites[root].generation >= whites[child].generation:
            return
        let held = whites[root]
        whites[root] = whites[child]
        whites[child] = held
        root = child

## Free the garbage: deinits first, then every object's fields, then the storage.
pub func collect():
    if collector_running:
        return
    collector_running = true
    # candidates still purple and alive stay; the rest leave the buffer
    var kept: usize = 0
    var i: usize = 0
    while i < root_count:
        let o = roots[i]
        if color_of(o) == purple and o.strong > 0 and not has(o, dead):
            roots[kept] = o
            kept += 1
        else:
            o.flags &= ~buffered
            release_shell(o)
        i += 1
    root_count = kept
    i = 0
    while i < root_count:
        mark_gray(roots[i])
        i += 1
    i = 0
    while i < root_count:
        scan(roots[i])
        i += 1
    white_count = 0
    i = 0
    while i < root_count:
        gather(roots[i])
        i += 1
    i = 0
    while i < root_count:
        roots[i].flags &= ~buffered
        i += 1
    root_count = 0
    sort_whites()
    # the counts the trial deletion took for the garbage's edges are restored, to garbage and
    # to live objects alike, so that every field release below is an ordinary one; a release
    # of a white object then only lowers its count
    i = 0
    while i < white_count:
        whites[i].info.trace(whites[i], visit_restore, (void*)whites[i])
        i += 1
    i = 0
    while i < white_count:
        let o = whites[i]
        if let f = o.info.finish:
            let before = o.strong
            o.strong += 1
            f(o)
            if o.strong > before + 1:
                trap("`deinit` published `self`")
            # Native disposal may release edges, including an edge to itself.
            # Remove only the temporary finalizer reference, preserving those drops.
            o.strong -= 1
        i += 1
    i = 0
    while i < white_count:
        whites[i].info.drop(whites[i])
        i += 1
    i = 0
    while i < white_count:
        let o = whites[i]
        live -= 1
        o.strong = 0
        o.flags = dead
        release_shell(o)
        i += 1
    white_count = 0
    collector_running = false