# Carl Niko 2024-09-20 discussion

Easy case

flowchart LR
    subgraph thread0
        A --> B --> C --> A
    end
    
    subgraph thread1
        X --> B
    end

Harder

flowchart LR
    subgraph thread0
        A --> B --> C --> A
    end
    
    subgraph thread1
        X --> B
    end
    
    C --> X

Nested cycle 1

flowchart LR
    A --> C
    C --> E
    E --> C
    C --> A
    
    A[A 3]
    C[C 5]
    E[E 10]

* A starts with provisional value inf
* C starts with provisional value inf
* E starts with provisional value inf
* E visits C, which has provisional value inf
* C is tagged as head of cycle
* E computes min(10, inf), which is 10
* C visits A, which has provisional value inf
* A is tagged as head of cycle
* C computes min(5, 10, inf), which is 5
* A computes min(3, 5), which is 3
* A starts next iteration with provisional value 3
* C starts with provisional value inf
* E starts with provisional value inf
* E visits C, which has provisional value inf
* C is tagged as head of cycle
* E computes min(10, inf), which is 10
* C visits A, which has provisional value 3
* C computes min(5, 10, 3), which is 3

Nested cycle 3

flowchart LR
    A --> C
    C --> E
    E --> C
    C --> A
    C --> D
    D --> C
    
    A[A 3]
    C[C 5]
    E[E 10]

* A starts with provisional value inf
* C starts with provisional value inf
* E starts with provisional value inf
* E visits C, which has provisional value inf
* C is tagged as head of cycle
* E computes min(10, inf), which is 10
* C visits A, which has provisional value inf
* A is tagged as head of cycle
* C computes min(5, 10, inf), which is 5
* A computes min(3, 5), which is 3
* A starts next iteration with provisional value 3
* C starts with provisional value inf
* E starts with provisional value inf
* E visits C, which has provisional value inf
* C is tagged as head of cycle
* E computes min(10, inf), which is 10
* C visits A, which has provisional value 3
* C computes min(5, 10, 3), which is 3

# Node states

* Uncomputed
* InProcess
* interim value
* Completed
* cycle head
* final value

A --> B --> C --> A

* A becomes InProcess(inf)
* B becomes InProcess(inf)
* C becomes InProcess(0, inf)
* cycle head = A
* final value = C0
* C becomes Completed(A, C0)
* B sees cycle head of A
* final value = B0 // actual function
* B becomes Completed(A, B0)
* A reads Completed(A, B0)
* A computes A0
* A compares A0 to inf, not equal, (call user-provided check-if-done function, with value and maybe with counter?), need to iterate
* A becomes InProcess(A0)
* A calls B, B is Completed, but cycle head (A) is InProcess
* B becomes InProcess(B0) // or maybe it starts with inf again?
* C is Completed(A, C0), but A is InProcess
* C becomes InProcess(C0)
* C calls B, which is InProcess(B0), and uses B0 as interim value

reason to keep counter in InProcess state:

* A calls B
* B calls C
* C calls A (cycle!)
* B calls C again
* can we reuse previous C?

enum NodeState {
    InProgress {
        iteration_count: u32,
        provisional_value: X
    },
    
    Completed {
        cycle_head: (AtomicCell?) Option<CycleHead>,
        final_value: X
    }
}

struct CycleHead {
    id: Id,
    iteration_count: u32,
}

type State = Option<NodeState>