---
# System prepended metadata

title: Carl Niko 2024-09-20 discussion

---

# Carl Niko 2024-09-20 discussion

Easy case

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

Harder

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

Nested cycle 1

```mermaid
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

```mermaid
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?

```rust
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>
```