Reussir Language Reference

Synchronization

Synchronization

Reference counting is ordinary mutable state: copying a handle increments a count and dropping it decrements that count. Reussir’s normal shared records use inexpensive non-atomic counts. That is safe while every handle remains on one thread, but two threads updating the same count would race.

Reussir keeps the fast representation for thread-local functional code and introduces atomicity only where a value can cross a thread boundary:

  • Arc<X>Arc<X> gives an immutable shared box an atomic reference count;
  • synchronized cell kinds provide atomically counted mutable boxes; and
  • the compiler-derived SyncSync trait verifies that every value reachable from either box is safe to use from multiple threads.

The invariant is simple: no normal-count box, unsynchronized cell, or regional object may be reachable from more than one thread.

The SyncSync auto trait

Sync(T)Sync(T) means that a value of type TT may be reached, aliased, read, cloned, stored, and dropped concurrently from different threads. SyncSync is an auto trait: the compiler derives it from the complete structure of a type. There are no user-written SyncSync implementations.

The name resembles Rust’s SyncSync, but the Reussir predicate is stronger. An RC handle is freely duplicable, so the type system cannot prove that moving one handle to another thread left no aliases behind. A value that crosses a thread boundary must therefore be both transferable and concurrently shareable. Reussir’s single SyncSync predicate covers the roles served by both SendSend and SyncSync in Rust.

You can require the predicate on a generic parameter:

fn echo_sync<T : Sync>(value: T) -> T {
    value
}
fn echo_sync<T : Sync>(value: T) -> T {
    value
}

The compiler answers that bound structurally when a concrete TT is selected:

Type SyncSync? Reason
numeric scalars, boolbool, charchar, and unitunit yes copied values contain no independently managed box
[value][value] record derived yes exactly when every member is SyncSync
Nullable<T>Nullable<T> derived follows TT
Arc<X>Arc<X> yes its atomic box is well formed only when its interior is safe
Atomic<T>Atomic<T>, Mutex<T>Mutex<T>, FlatLock<T>FlatLock<T>, RwLock<T>RwLock<T> yes the cell kind supplies synchronization and enforces its element bound
bare [shared][shared] record, array, or closure no its RC box has a normal, non-atomic count
Cell<T>Cell<T> or RefCell<T>RefCell<T> no their mutation discipline is local to one thread
regional values and region handles no their lifetime belongs to one construction region

For example, a bare shared record does not satisfy the bound:

struct Plain {
    value: i64
}
fn require_sync<T : Sync>(value: T) -> T {
    value
}
fn rejected() -> Plain {
    require_sync(Plain { value: 1 })
}
struct Plain {
    value: i64
}
fn require_sync<T : Sync>(value: T) -> T {
    value
}
fn rejected() -> Plain {
    require_sync(Plain { value: 1 })
}

The diagnostic names both the concrete type and the reason it is unsafe:

Error: `Plain` is not `Sync`: it is a plain `[shared]` rc box whose refcount is not atomic
    ╭─[ sync-bound.rr:10:5 ]
    │
 10 │     require_sync(Plain { value: 1 })
    │     ────────────────┬───────────────
    │                     ╰───────────────── `Plain` is not `Sync`: it is a plain `[shared]` rc box whose refcount is not atomic
────╯
Error: `Plain` is not `Sync`: it is a plain `[shared]` rc box whose refcount is not atomic
    ╭─[ sync-bound.rr:10:5 ]
    │
 10 │     require_sync(Plain { value: 1 })
    │     ────────────────┬───────────────
    │                     ╰───────────────── `Plain` is not `Sync`: it is a plain `[shared]` rc box whose refcount is not atomic
────╯

This check is also applied when a generic is monomorphized. A generic definition may defer an answer while TT is unknown, but every ground instance must satisfy the same structural rules before code generation.

ArcArc: atomic reference counting from birth

Arc<X>Arc<X> is the same nominal XX stored in an atomically reference-counted box. Projection and pattern matching still expose XX’s fields and variants; only the ownership discipline changes.

Construct an arc-colored record by naming Arc<X>Arc<X> at the constructor:

struct Reading {
    value: i64
}
fn new_reading(value: i64) -> Arc<Reading> {
    Arc<Reading> { value }
}
fn read(reading: Arc<Reading>) -> i64 {
    reading.value
}
struct Reading {
    value: i64
}
fn new_reading(value: i64) -> Arc<Reading> {
    Arc<Reading> { value }
}
fn read(reading: Arc<Reading>) -> i64 {
    reading.value
}

The box is atomic from the moment it is created. Reussir never takes an existing ReadingReading and changes its count discipline at runtime. Converting a normal recursive structure to its arc-colored form therefore requires an explicit rebuild.

An arc colors exactly one box

The outer ArcArc is not a deep runtime conversion. Every member strictly inside XX must already be SyncSync. Scalars and [value][value] records made entirely from SyncSync members are fine; an independently boxed member must carry its own atomic discipline.

This record is rejected because leafleaf is a separate normal-count box:

struct Leaf {
    value: i64
}
struct Envelope {
    leaf: Leaf
}
fn rejected(value: Arc<Envelope>) -> i64 {
    value.leaf.value
}
struct Leaf {
    value: i64
}
struct Envelope {
    leaf: Leaf
}
fn rejected(value: Arc<Envelope>) -> i64 {
    value.leaf.value
}
Error: `Arc<Envelope>` is ill-formed: member `leaf` is a plain `[shared]` rc box whose refcount is not atomic; every member of an `Arc` inner must be `Sync`
   ╭─[ outer-arc.rr:9:1 ]
   │
 9 │ ╭─▶ fn rejected(value: Arc<Envelope>) -> i64 {
   ┆ ┆
11 │ ├─▶ }
   │ ╰─────── `Arc<Envelope>` is ill-formed: member `leaf` is a plain `[shared]` rc box whose refcount is not atomic; every member of an `Arc` inner must be `Sync`
───╯
Error: `Arc<Envelope>` is ill-formed: member `leaf` is a plain `[shared]` rc box whose refcount is not atomic; every member of an `Arc` inner must be `Sync`
   ╭─[ outer-arc.rr:9:1 ]
   │
 9 │ ╭─▶ fn rejected(value: Arc<Envelope>) -> i64 {
   ┆ ┆
11 │ ├─▶ }
   │ ╰─────── `Arc<Envelope>` is ill-formed: member `leaf` is a plain `[shared]` rc box whose refcount is not atomic; every member of an `Arc` inner must be `Sync`
───╯

Make that relationship atomic explicitly when it is not part of a recursive group:

struct Envelope {
    leaf: Arc<Leaf>
}
fn accepted(value: Arc<Envelope>) -> i64 {
    value.leaf.value
}
struct Envelope {
    leaf: Arc<Leaf>
}
fn accepted(value: Arc<Envelope>) -> i64 {
    value.leaf.value
}

The same distinction applies to synchronized cells. A lock protects its stored slot, but a clone returned from cell::getcell::get lives beyond the critical section. Consequently, Mutex<Plain>Mutex<Plain> is rejected while Mutex<Arc<Plain>>Mutex<Arc<Plain>> is valid:

Error: `Mutex<Plain>` is ill-formed: it is a plain `[shared]` rc box whose refcount is not atomic; the element of a lock-guarded cell must be `Sync` — the lock protects the stored slot, while clones of the element leave the critical section
Error: `Mutex<Plain>` is ill-formed: it is a plain `[shared]` rc box whose refcount is not atomic; the element of a lock-guarded cell must be `Sync` — the lock protects the stored slot, while clones of the element leave the critical section

ArcArc applies to immutable shared boxes, not to every type. Scalars, [value][value] and [regional][regional] records, cells, Nullable<T>Nullable<T>, and an already arc’d type cannot be an ArcArc inner. Synchronized cells do not need another wrapper: their cell kind creates an atomic box directly. Arc-colored arrays and closures can currently be written in type annotations, but their construction and lowering are not yet complete.

Recursive records and automatic SCC promotion

A direct application of the one-box rule would make every recursive structure impossible to share. In this list, for example, the ConsCons tail is written as a bare ListList:

enum List {
    Nil,
    Cons(i64, List)
}
enum List {
    Nil,
    Cons(i64, List)
}

Reussir solves this at compile time. It builds the graph of record declarations and finds each strongly connected component (SCC): the maximal set of record types that can recursively reach one another. Selecting Arc<List>Arc<List> selects the atomic form of the entire recursive group. Every same-group link is promoted automatically, and the SyncSync proof closes the recursion coinductively.

This SCC is a property of the recursive type declarations. It is different from the runtime object-graph scan performed when a regional value freezes. No list nodes are scanned when an Arc<List>Arc<List> is created.

Build the arc-colored list from the end outward:

enum List {
    Nil,
    Cons(i64, List)
}
fn sum(values: Arc<List>) -> i64 {
    match values {
        List::Nil => 0,
        List::Cons(head, tail) => head + sum(tail)
    }
}
fn answer() -> i64 {
    let values = Arc<List>::Cons {
        7,
        Arc<List>::Cons { 35, Arc<List>::Nil }
    };
    sum(values)
}
enum List {
    Nil,
    Cons(i64, List)
}
fn sum(values: Arc<List>) -> i64 {
    match values {
        List::Nil => 0,
        List::Cons(head, tail) => head + sum(tail)
    }
}
fn answer() -> i64 {
    let values = Arc<List>::Cons {
        7,
        Arc<List>::Cons { 35, Arc<List>::Nil }
    };
    sum(values)
}

Although the declaration says Cons(i64, List)Cons(i64, List), the tail constructor above expects Arc<List>Arc<List>, and matching an Arc<List>Arc<List> binds tailtail as Arc<List>Arc<List>. The same rule covers mutually recursive types: every record in their shared declaration SCC receives the atomic coloring.

Promotion does not recolor an already constructed plain value. Mixing the two worlds produces a purpose-built diagnostic:

fn rejected() -> Arc<List> {
    Arc<List>::Cons { 1, List::Nil }
}
fn rejected() -> Arc<List> {
    Arc<List>::Cons { 1, List::Nil }
}
Error: cannot reconcile thread-safety: expected `Arc<List>`, found `List`
   ╭─[ list-color.rr:7:26 ]
   │
 7 │     Arc<List>::Cons { 1, List::Nil }
   │                          ────┬────
   │                              ╰────── cannot reconcile thread-safety: expected `Arc<List>`, found `List`
   │
   │ Note 1: fields of the recursive group `List` are promoted to `Arc` inside an arc'd box
   │
   │ Note 2: a plain value is never re-colored; construct it as `Arc<List>::…` from the start
───╯
Error: cannot reconcile thread-safety: expected `Arc<List>`, found `List`
   ╭─[ list-color.rr:7:26 ]
   │
 7 │     Arc<List>::Cons { 1, List::Nil }
   │                          ────┬────
   │                              ╰────── cannot reconcile thread-safety: expected `Arc<List>`, found `List`
   │
   │ Note 1: fields of the recursive group `List` are promoted to `Arc` inside an arc'd box
   │
   │ Note 2: a plain value is never re-colored; construct it as `Arc<List>::…` from the start
───╯

Only links within the recursive group promote. If a list node also contains an unrelated shared record, that member must be declared Arc<Other>Arc<Other> explicitly; the compiler reports its member path just as it reported Envelope.leafEnvelope.leaf.

A parallel persistent map with a PolyFFI driver

The following program lets four Rust threads update one Reussir value. The shared state is a Mutex<Arc<Map>>Mutex<Arc<Map>>:

  • MapMap is a persistent binary-search tree. Inserting a key constructs a new path and shares untouched subtrees.
  • Arc<Map>Arc<Map> gives every node in the recursive map SCC atomic RC.
  • Mutex<Arc<Map>>Mutex<Arc<Map>> serializes replacement of the root while allowing each completed snapshot to remain immutable.
  • the Rust code embedded through PolyFFI is only the thread driver. The map, update, locking, and final fold remain Reussir code.

Create a Rene project for the example:

rene new parallel_map --vcs none
cd parallel_map
rene new parallel_map --vcs none
cd parallel_map

Replace src/lib.rrsrc/lib.rr with the following sections, in order.

The Reussir data structure and worker API

import core::intrinsic::cell;
pub enum Map {
    Tip,
    Node(i64, i64, Map, Map)
}
fn insert(m: Arc<Map>, key: i64, value: i64) -> Arc<Map> {
    match m {
        Map::Tip => {
            Arc<Map>::Node {
                key,
                value,
                Arc<Map>::Tip,
                Arc<Map>::Tip
            }
        },
        Map::Node(node_key, node_value, left, right) => {
            if key < node_key {
                Arc<Map>::Node {
                    node_key,
                    node_value,
                    insert(left, key, value),
                    right
                }
            } else {
                if key > node_key {
                    Arc<Map>::Node {
                        node_key,
                        node_value,
                        left,
                        insert(right, key, value)
                    }
                } else {
                    Arc<Map>::Node {
                        node_key,
                        value,
                        left,
                        right
                    }
                }
            }
        }
    }
}
import core::intrinsic::cell;
pub enum Map {
    Tip,
    Node(i64, i64, Map, Map)
}
fn insert(m: Arc<Map>, key: i64, value: i64) -> Arc<Map> {
    match m {
        Map::Tip => {
            Arc<Map>::Node {
                key,
                value,
                Arc<Map>::Tip,
                Arc<Map>::Tip
            }
        },
        Map::Node(node_key, node_value, left, right) => {
            if key < node_key {
                Arc<Map>::Node {
                    node_key,
                    node_value,
                    insert(left, key, value),
                    right
                }
            } else {
                if key > node_key {
                    Arc<Map>::Node {
                        node_key,
                        node_value,
                        left,
                        insert(right, key, value)
                    }
                } else {
                    Arc<Map>::Node {
                        node_key,
                        value,
                        left,
                        right
                    }
                }
            }
        }
    }
}

The fold and the constructors for the synchronized root come next:

fn total(m: Arc<Map>) -> i64 {
    match m {
        Map::Tip => 0,
        Map::Node(_, value, left, right) => {
            value + total(left) + total(right)
        }
    }
}
pub fn make_stats() -> Mutex<Arc<Map>> {
    cell::alloc<Mutex<Arc<Map>>>(Arc<Map>::Tip)
}
extern "C" trampoline "make_stats_ffi" = make_stats;
pub struct [value] Pair {
    keep: Mutex<Arc<Map>>,
    extra: Mutex<Arc<Map>>
}
pub fn dup(stats: Mutex<Arc<Map>>) -> Pair {
    Pair { keep: stats, extra: stats }
}
extern "C" trampoline "dup_ffi" = dup;
fn total(m: Arc<Map>) -> i64 {
    match m {
        Map::Tip => 0,
        Map::Node(_, value, left, right) => {
            value + total(left) + total(right)
        }
    }
}
pub fn make_stats() -> Mutex<Arc<Map>> {
    cell::alloc<Mutex<Arc<Map>>>(Arc<Map>::Tip)
}
extern "C" trampoline "make_stats_ffi" = make_stats;
pub struct [value] Pair {
    keep: Mutex<Arc<Map>>,
    extra: Mutex<Arc<Map>>
}
pub fn dup(stats: Mutex<Arc<Map>>) -> Pair {
    Pair { keep: stats, extra: stats }
}
extern "C" trampoline "dup_ffi" = dup;

Finally, export the worker operations that the Rust driver will call:

fn loop_insert(
    stats: Mutex<Arc<Map>>,
    key: i64,
    stride: i64,
    upto: i64,
) -> i64 {
    if key < upto {
        cell::rmw(stats, |map| insert(map, key, key));
        loop_insert(stats, key + stride, stride, upto)
    } else {
        0
    }
}
pub fn worker(
    stats: Mutex<Arc<Map>>,
    thread_id: i64,
    stride: i64,
    upto: i64,
) -> i64 {
    loop_insert(stats, thread_id, stride, upto)
}
extern "C" trampoline "worker_ffi" = worker;
pub fn grand_total(stats: Mutex<Arc<Map>>) -> i64 {
    total(cell::get(stats))
}
extern "C" trampoline "grand_total_ffi" = grand_total;
fn loop_insert(
    stats: Mutex<Arc<Map>>,
    key: i64,
    stride: i64,
    upto: i64,
) -> i64 {
    if key < upto {
        cell::rmw(stats, |map| insert(map, key, key));
        loop_insert(stats, key + stride, stride, upto)
    } else {
        0
    }
}
pub fn worker(
    stats: Mutex<Arc<Map>>,
    thread_id: i64,
    stride: i64,
    upto: i64,
) -> i64 {
    loop_insert(stats, thread_id, stride, upto)
}
extern "C" trampoline "worker_ffi" = worker;
pub fn grand_total(stats: Mutex<Arc<Map>>) -> i64 {
    total(cell::get(stats))
}
extern "C" trampoline "grand_total_ffi" = grand_total;

Each worker owns a handle to the same mutex cell. Its keys are thread_idthread_id, thread_id + stridethread_id + stride, and so on. cell::rmwcell::rmw runs one pure path-copying insertion while the mutex is held, then stores the returned Arc<Map>Arc<Map> as the new root.

The exported trampolines consume their Reussir arguments. dupdup therefore turns one owned cell handle into two managed handles. The Rust driver threads the keepkeep result forward and hands each extraextra result to exactly one worker; after four splits it owns four worker handles plus one handle for the final fold.

The embedded Rust thread driver

Append the Rust support texture and the imported driver function:

extern "rust" [{
    #[repr(C)]
    struct WorkerArgs {
        stats: *mut std::ffi::c_void,
        thread_id: i64,
        stride: i64,
        upto: i64,
    }
    #[repr(C)]
    struct DupArg {
        stats: *mut std::ffi::c_void,
    }
    #[repr(C)]
    struct DupPair {
        keep: *mut std::ffi::c_void,
        extra: *mut std::ffi::c_void,
    }
    unsafe extern "C" {
        fn make_stats_ffi() -> *mut std::ffi::c_void;
        fn dup_ffi(out: *mut DupPair, args: *mut DupArg);
        fn worker_ffi(args: *mut WorkerArgs) -> i64;
        fn grand_total_ffi(stats: *mut std::ffi::c_void) -> i64;
    }
    struct Handle(*mut std::ffi::c_void);
    unsafe impl Send for Handle {}
}];
extern "rust" [{
    #[repr(C)]
    struct WorkerArgs {
        stats: *mut std::ffi::c_void,
        thread_id: i64,
        stride: i64,
        upto: i64,
    }
    #[repr(C)]
    struct DupArg {
        stats: *mut std::ffi::c_void,
    }
    #[repr(C)]
    struct DupPair {
        keep: *mut std::ffi::c_void,
        extra: *mut std::ffi::c_void,
    }
    unsafe extern "C" {
        fn make_stats_ffi() -> *mut std::ffi::c_void;
        fn dup_ffi(out: *mut DupPair, args: *mut DupArg);
        fn worker_ffi(args: *mut WorkerArgs) -> i64;
        fn grand_total_ffi(stats: *mut std::ffi::c_void) -> i64;
    }
    struct Handle(*mut std::ffi::c_void);
    unsafe impl Send for Handle {}
}];

The imported function splits the handles, starts one Rust thread for each handle, waits for them, and consumes the final handle to read the result:

#[ffi(import)]
fn run_workers(threads: i64, keys: i64) -> i64 [{
    {
        let mut keep = unsafe { make_stats_ffi() };
        let mut handles = Vec::new();
        for _ in 0..threads {
            let mut args = DupArg { stats: keep };
            let mut pair = DupPair {
                keep: std::ptr::null_mut(),
                extra: std::ptr::null_mut(),
            };
            unsafe { dup_ffi(&mut pair, &mut args) };
            handles.push(Handle(pair.extra));
            keep = pair.keep;
        }
        let workers: Vec<_> = handles
            .into_iter()
            .enumerate()
            .map(|(thread_id, handle)| {
                std::thread::spawn(move || {
                    let mut args = WorkerArgs {
                        stats: handle.0,
                        thread_id: thread_id as i64,
                        stride: threads,
                        upto: keys,
                    };
                    unsafe { worker_ffi(&mut args) }
                })
            })
            .collect();
        for worker in workers {
            worker.join().expect("a worker thread panicked");
        }
        unsafe { grand_total_ffi(keep) }
    }
}];
#[ffi(import)]
fn run_workers(threads: i64, keys: i64) -> i64 [{
    {
        let mut keep = unsafe { make_stats_ffi() };
        let mut handles = Vec::new();
        for _ in 0..threads {
            let mut args = DupArg { stats: keep };
            let mut pair = DupPair {
                keep: std::ptr::null_mut(),
                extra: std::ptr::null_mut(),
            };
            unsafe { dup_ffi(&mut pair, &mut args) };
            handles.push(Handle(pair.extra));
            keep = pair.keep;
        }
        let workers: Vec<_> = handles
            .into_iter()
            .enumerate()
            .map(|(thread_id, handle)| {
                std::thread::spawn(move || {
                    let mut args = WorkerArgs {
                        stats: handle.0,
                        thread_id: thread_id as i64,
                        stride: threads,
                        upto: keys,
                    };
                    unsafe { worker_ffi(&mut args) }
                })
            })
            .collect();
        for worker in workers {
            worker.join().expect("a worker thread panicked");
        }
        unsafe { grand_total_ffi(keep) }
    }
}];

Add one small imported helper for checking and printing the result:

#[ffi(import)]
fn report(got: i64, want: i64) [{
    {
        assert_eq!(got, want, "an update was lost");
        println!("parallel shared map: {got}");
    }
}];
#[ffi(import)]
fn report(got: i64, want: i64) [{
    {
        assert_eq!(got, want, "an update was lost");
        println!("parallel shared map: {got}");
    }
}];

The contents of extern "rust" [{ ... }]extern "rust" [{ ... }] and each [{ ... }][{ ... }] implementation are Rust; the surrounding declarations are Reussir. PolyFFI compiles those Rust fragments and links them into the same program.

Rust sees a Reussir handle as an opaque pointer, so the small HandleHandle wrapper needs an unsafe impl Sendunsafe impl Send before std::thread::spawnstd::thread::spawn will accept it. That assertion is justified here specifically because the pointer owns a Mutex<Arc<Map>>Mutex<Arc<Map>>, a type the Reussir compiler has already proven SyncSync. It would be incorrect to reuse this wrapper for a bare shared record, CellCell, RefCellRefCell, or regional value.

Run the workload

Finish the file with a main entry point:

#[main]
pub fn entry() {
    let keys: i64 = 256;
    let got = run_workers(4, keys);
    report(got, keys * (keys - 1) / 2);
}
#[main]
pub fn entry() {
    let keys: i64 = 256;
    let got = run_workers(4, keys);
    report(got, keys * (keys - 1) / 2);
}

Build and run it from the project directory:

rene build --profile release
./reussir-build/release/parallel_map
rene build --profile release
./reussir-build/release/parallel_map

On Windows, run the corresponding .exe.exe. The four workers collectively insert every key in 0..2560..256 with its own value, so the final fold must equal 0 + 1 + ... + 2550 + 1 + ... + 255:

parallel shared map: 32640
parallel shared map: 32640

This example intentionally keeps synchronization at one small boundary. The mutex protects publication of a new persistent root; readers and the insert algorithm otherwise operate on immutable Arc<Map>Arc<Map> snapshots. More elaborate thread APIs and scheduling abstractions remain outside the synchronization model documented here.