Vela Regions.

1. The idea

A region is a named place to put memory. You declare one with region r, and new T(value) at r copies a value into it and gives you a pointer to the copy. Nothing in a region is freed on its own. Instead, the whole region is freed at once, when the block that declared it ends.

Think of a whiteboard in a meeting room: during the meeting anyone can write on it, and when the meeting ends it is wiped clean in one go. Nobody erases single words, and nobody can read the board after it was wiped, because the meeting (the block) is over.

What makes Vela's regions safe is that the region's name is part of every pointer's type. A ^Node@nodes is "a pointer to a Node in region nodes". A type can only name a region that exists where the type is written, so a pointer can never be kept anywhere that lives longer than its region. The compiler checks this with a few simple rules, and nothing is checked at run time.

task main()
    region scratch                     ; a new, empty region
    fixed n = new int(42) at scratch    ; n has type ^int@scratch
    show(n^)                           ; 42
fi                                     ; scratch, and everything in it, is freed here

2. Why Vela has regions

Most Vela values don't need any of this. Numbers, bools, shapes, and kinds are copied when they are assigned or passed, and live in the block that declares them (When a type needs a region is the full answer to which values do). But some data can't work that way:

• Linked data, such as lists, trees, and graphs, where one value points to another.
• Shared data, where several places must see and change the same value.
• Data that outlives a call, built by one task and used by its caller.

These need pointers to memory allocated somewhere else. Before regions, Vela did this the way C does: new allocated a value, and free(p) gave it back. That is simple, and it is where the classic memory bugs come from:

; Vela before regions: this no longer compiles.
task main()
    fixed p = new int(1)
    free(p)
    show(p^)          ; use after free: reads memory that may belong to something else
    free(p)           ; double free: corrupts the allocator
    fixed q = new int(2)
fi                    ; q is never freed: a leak

Nothing in the language stopped any of these. Languages solve this in a few ways, and each has a price:

Vela chose regions (the full comparison is in Future Directions), because they fit what Vela wants to be:

• Minimal. One statement (region), one type annotation (@r), one parameter type (region). There are no lifetimes to infer and no borrowing rules.
• Explicit. You can see where memory lives (the region's name) and when it goes away (the end of the region's block).
• Fast. Allocating is a pointer bump, and freeing a region frees all its values at once.
• Checkable. Safety follows from a handful of local type rules, all checked at compile time.
• Plain C. The generated C is an ordinary local variable and a function call at each block exit.

3. What regions guarantee

If a Vela program compiles:

• No use after free. No variable, field, or result can hold a pointer after its region is freed, because its type would have to name a region that no longer exists.
• No double free. Only the compiler frees memory, once per region, and there is no free.
• No leaks past a block. Every way out of a block frees its regions: its fi, the end of a plan B block, and a <- from anywhere inside it.
• No null pointers. A ^T@r always points to something; one that may be missing is a maybe ^T@r, which must be checked before use (see Maybe and Errors).
• No hidden costs. No garbage collector, no reference counts, and no run-time checks when a pointer is used.

What they don't promise:

• Bounded memory. A long-lived region keeps growing while you allocate in it, even if old values are no longer used. Choosing regions well (see Choosing regions) is how you keep memory flat.
• Surviving out of memory. If the system has no memory left, the program prints vela: out of memory and stops.

4. Pros and cons

5. When a type needs a region

The question that comes up first, and keeps coming up, is: does this type name a region or not? The short answer is the one you would guess — memory that would be on the heap in C goes in a region — but it is worth seeing why, because the rule then answers every case, including the one type that goes both ways.

Where a value's bytes are

Every byte in a running Vela program is in one of three places, and each has its own answer to "when is it freed?":

1. In the value itself. A number, a bool, an array of a known size, a shape of such fields: the bytes sit in the variable, the field, or the parameter that holds them, and are copied when the value is. Their size is known as the program is compiled. Freed when the variable's block ends, automatically, with nothing to say about it. In C: a local variable or a field.
2. In the program. The bytes of a text literal are in the compiled program, put there before main starts. Never freed. In C: a string literal in static storage.
3. In a region. Bytes the program asked for while it was running, because their size or their number wasn't known before: what a pointer points at, a slice's items, text built out of other text. Freed when the region's block ends. In C: the heap, taken from a region's chunks.

Only the third kind needs a name, and that is the whole reason regions are in types. For the first two, the compiler already knows the answer to "when do these bytes go away?" — with the block, or never. For the third, the answer is "when that region ends", and a pointer can be stored anywhere; without the region's name in the type, there would be nothing to compare when the pointer is stored somewhere longer-lived. So:

Note what this is not about. It isn't about how big the value is: a [int#1000] is eight thousand bytes and needs no region, because they are part of the value. It isn't about being changed: a flex variable of any plain type changes in place. And it isn't about being passed around: plain values are copied into a task and copied back out, which needs no shared memory at all.

Which types name a region

Nothing in this program is in a region, so no region is declared and no type names one:

; Every value here lives where it is written, and its text is part of the program.
shape Point
    x: int
    y: int
fi

task moved(p: Point, by: int) -> Point
    <- Point { x: p.x + by, y: p.y + by }
fi

task main()
    fixed count = 41                    ; int: in the variable
    fixed ratio = 0.5                   ; float: in the variable
    fixed grid: [int#3] = [count#3]   ; an array: three ints, in the variable
    fixed here = Point { x: 1, y: 2 }    ; a shape of plain fields: in the variable
    fixed label = "point"               ; text: in the program, and never freed
    fixed pair = (count, label)         ; a tuple: each item where it belongs
    show(label, " ", moved(here, 1).x, " ", grid[0] + count, " ", ratio, " ", pair.0)
fi

point 2 82 0.5 41

Everything in this one is made while the program runs, so every type says where: a pointer, text built from other text, a slice, and a shape that holds them.

shape Note
    title: text                ; in the region of the Note that holds it
    next: maybe ^Note            ; a field never names a region
fi

task main()
    region notes
    fixed count = new int(7) at notes          ; ^int@notes: the int is in notes
    fixed number = count^.str() at notes       ; text@notes: new bytes, made here
    fixed title = "note " + number at notes     ; text@notes: a join makes new text
    fixed first = new Note(Note { title: title, next: none }) at notes
    fixed second = new Note(Note { title: "second", next: first }) at notes
    flex titles = new [text]() at notes        ; [text]@notes: the items are in notes
    titles.add(second^.title)
    titles.add(first^.title)
    show(titles.len, " ", titles[0], " ", titles[1], " ", count^)
fi

2 second note 7 7

Text, the one that goes both ways

Text is the one type the answer isn't settled for: the same text is sometimes in a region and sometimes not, and a shape or kind holding text follows its text. That is why it causes most of the questions, and the reason is simple: a text is a pointer and a length, and the bytes it points at are either in the program (a literal, written in the source, there before the program starts) or in a region (made while running, out of other text or out of a number). So the test is not what the text says but where its bytes came from: text you wrote needs no region; text the program made needs one.

task main()
    region r
    fixed greeting = "Hello, world"              ; text: written, so it lasts
    fixed hello = greeting[0..5]                 ; text: the same bytes, so still no region
    fixed name = "Ada"
    fixed line = greeting + " and " + name at r   ; text@r: new bytes
    fixed age = 42.str() at r                    ; text@r: a number written out
    fixed both = "{hello}, {name}" at r           ; text@r: values written into text
    show(line)
    show(both, " ", age, " ", greeting.len, " ", hello == "Hello")
fi

Hello, world and Ada
Hello, Ada 42 12 true

The two never mix in the wrong direction. Text that lasts fits anywhere text of a region is expected, since it outlives every region; text of a region can't be kept in a text, which would outlive it (that limitation, and .copy() is the way across). And a task that reads text of a region names the region in its header, title: text@r, exactly as it would for a pointer.

What a value holds decides for it

A shape or a kind is in a region when anything it holds is — a pointer, a slice, text made while running, or another shape or kind that is. Its fields never name a region: they are all in the one region of the value that holds them, which is what Node@r says. That is also why one value can't hold pointers into two regions (this limitation): @r is one name for all of it.

A shape holding only text is the case where both exist, and the same declaration serves both: Person is a person whose name is a literal, Person@r one whose name was read or built in r. A kind is the same, variant by variant: Status.Todo holds nothing and fits any region, Status.Blocked(reason) holds text, so it is in the region that text is in.

Tuples work the other way around, because their items never change: a tuple holds no pointer and no slice at all, and each item keeps its own type, so (text@a, text@b) — text of two different regions in one value — is fine, where a shape with two such fields is not. maybe and ~ only wrap: whether maybe ^Node@r is in a region is decided by the ^Node@r inside it.

One case looks like a region and isn't: a value built with no pointers in it yet, such as Leaf(1) or Node { value: 1, next: none }. It fits into any region, so nothing in it fixes one; that is why such a value needs its region written where it is bound (flex head: Node@nodes = …), and why the compiler writes @_ for "no region" when it talks about one (this limitation).

When a region is an argument, and when a name is enough

The second half of the question is about headers. A task can always read data in a region it merely names in a type; it can only allocate in a region it was given as a parameter or declared itself. So the test is not whether a task touches memory in a region, but whether it makes any:

shape Node
    value: int
    next: maybe ^Node
fi

; Makes data for its caller, so the caller's region is an argument.
task push(r: region, list: maybe ^Node@r, value: int) -> ^Node@r
    <- new Node(Node { value: value, next: list }) at r
fi

; Only reads what the caller made: it names the region and is given nothing.
task total(list: maybe ^Node@r) -> int
    when list is {node}
        <- node^.value + total(node^.next)
    fi
    <- 0
fi

; Adds what the list holds to a slice of the caller, in the region it takes.
task gather(list: maybe ^Node@r, flex& seen: [int]@w, w: region)
    when list is {node}
        seen.add(node^.value)
        gather(node^.next, &seen, w)
    fi
fi

; Allocates only for itself: a region of its own, and a result holding nothing.
task largest(list: maybe ^Node@r) -> int
    region work
    flex seen = new [int]() at work
    gather(list, &seen, work)
    flex most = 0
    each v in seen
        when v > most
            most = v
        fi
    fi
    <- most
fi

; Plain values only: no region anywhere in the header.
task twice(n: int) -> int
    <- n * 2
fi

task main()
    region nodes
    flex list: maybe ^Node@nodes = none
    each i in 1..4
        list = push(nodes, list, i)
    fi
    show(total(list), " ", largest(list), " ", twice(total(list)))
fi

6 3 12

largest is the one to notice: it allocates a slice on every call, and its header says nothing about regions, because that memory is nobody else's business — it is freed at the task's fi. Taking r: region there would be wrong twice over: the caller would pay for it, and the scratch items would stay in the caller's region until its block ended.

Three rules follow from the same place, and each has its own message when it is broken:

• A named region can't be allocated in. @r in a type is a name for whatever region the caller's value was in; there is no region to allocate with, which is exactly what makes the task free to call. Writing new … at r there says this task can't allocate in 'r', which it only names in its types; take it as a parameter, 'r: region'. The same goes for making text and for add on a slice, which may need more room.
• A result's region must be a parameter's. A region the task declares is freed when it returns, so nothing it sends can point into it; a region only the result names isn't accepted either (why, and the workaround).
• The same name means the same region. Two parameters written @r must be in one region, and two written @x and @y may differ, which is what lets a task link two lists safely or refuse to (Lesson 5).

Where a region is an argument, it is passed by name at the call, push(nodes, list, i), even inside a block with a default region: a default settles where an allocation goes, not which region a task is handed. And .copy() takes its region from the place the copy goes, so a copy needs one written only where nothing else names it.

Deciding, in order

1. Does the value hold a pointer, a slice, or text the program made? If not, there is no region to write, and nothing to pass: use it as a plain value.
2. If it does, when should its memory go away? Declare the region in the block that ends then: the top of main for data the whole program uses, inside the loop for data of one pass.
3. Who makes it? The task that allocates needs the region — as a parameter when the caller keeps the result, as its own region when the memory is scratch.
4. Who else touches it? Everything that only reads, walks, or links it names the region in its types and takes nothing.
5. Does one region do nearly all the work in the block? Then name it the block's default and let the lines that go elsewhere be the ones that say so.

Questions that come up

• Does a big array need a region? No. [int#1000] is part of its value however large it is; it makes the value large. A number of items known only while running is a slice, which does need one.
• My task allocates, but gives back an int. Then it needs no region in its header: declare one in its body (the first limitation shows the shape of it).
• Does printing a shape of mine need a region? No. show writes the text of each value into a region it makes for the line and frees straight after, so printing needs no region of yours; one you declare is for text you keep, pass on, or send back.
• Two regions in one value? Not in a shape or a kind — all of one value is in one region. A tuple of text can hold two, a task can send several results in different regions (-> ^int@a, ^int@b), and .copy() moves data across.
• Can the program pick a region while it runs? No: a region is not a value (why). Call the task in both branches of a when instead.
• What should a task that takes text write? name: text@r, nearly always: it takes text of any region and literals, since text that lasts fits everywhere. name: text takes only text that lasts, which is right for a task that keeps what it is given beyond any region.
• How do I check where a value really went? Hover it in Vela Studio: it shows the type Vela worked out, fixed p: ^int@kept. That is the quickest way to confirm an allocation landed where you meant — including one that named no region because the block has a default.

6. Tutorial

The lessons build on each other. Each program is complete: save it as a .vela file and run it with vela file.vela -o file && ./file, or open it in Vela Studio and press F5.

Lesson 1: A first region

task main()
    region scratch
    flex count = new int(41) at scratch
    count^ = count^ + 1
    show(count^)
fi

42

region scratch is a statement: from here to the end of the block (the task), scratch is a region you can allocate in. new int(41) at scratch copies 41 into it and gives back a pointer, so count has type ^int@scratch. count^ is the value it points to, which you can read and write, since count is a flex: through a fixed, nothing changes, not even the value it points to. At the task's fi, the region is freed.

Lesson 2: Pointer types name their region

shape Point
    x: int
    y: int
fi

task main()
    region points
    flex p: ^Point@points = new Point(Point { x: 1, y: 2 }) at points
    flex q = new@points Point(Point { x: 3, y: 4 })
    p^.x = p^.x + q^.x
    show(p^.x)

    flex spare: maybe ^Point@points = none
    when spare is {s}
        show(s^.y)
    else
        show("no spare yet")
    fi
    spare = q
    show(spare { p }^.y)
fi

4
no spare yet
4

• new Point(v) at points and new@points Point(v) mean the same thing; use whichever reads better.
• A pointer's type is ^T@r. You can write it out (p: ^Point@points) or let Vela infer it (q).
• The type after new names no region (new Point(…), not new Point@points(…)): what it makes lives in the region it allocates in.
• A pointer to a shape has no fields; go through ^: p^.x.
• A pointer is never none. A pointer that may be missing is a maybe ^Point@points, read with is, match, or a plan B (spare { p } is spare's pointer, or p when there is none).

Lesson 3: When memory is freed

task first_square_over(limit: int) -> int
    region work
    each i in 0..100
        fixed square = new int(i * i) at work
        when square^ > limit
            <- square^
        fi
    fi
    <- -1
fi

task main()
    region outer
    flex total = new int(0) at outer
    each round in 0..3
        region pass
        fixed step = new int(round * 10) at pass
        total^ = total^ + step^
    fi
    show(total^)
    show(first_square_over(50))

    fixed missing: maybe int = none
    fixed rescued = missing {
        region rescue
        fixed spare = new int(7) at rescue
        spare^ * 6
    }
    show(rescued)
fi

30
64
42

A region is freed when the block that declares it ends, whichever way it ends:

• At its fi. A region declared in a loop's body is a new region on every pass and is freed at the end of each pass, so pass never holds more than one value. This is how a loop allocates without growing.
• At a <-. In first_square_over, the send frees work (after computing square^, the value it sends), even though it happens deep inside a loop.
• At the end of a plan B's block, after its last line has given its value.
• At the fi of a block, a block of its own, written anywhere a statement is, for a region (and the files opened in it) that should end before the task does, with no loop or condition around it.

Notice that total lives in outer, declared before the loop: values that must survive every pass go in a region outside the loop, and values for one pass go in a region inside it.

Lesson 4: Linked data

shape Node
    value: int
    next: maybe ^Node
fi

task push(r: region, list: maybe ^Node@r, value: int) -> ^Node@r
    <- new Node(Node { value: value, next: list }) at r
fi

task sum(list: maybe ^Node@r) -> int
    when list is {node}
        <- node^.value + sum(node^.next)
    fi
    <- 0
fi

task main()
    region nodes
    flex list: maybe ^Node@nodes = none
    each i in 1..6
        list = push(nodes, list, i)
    fi
    show(sum(list))
    show(sum(none))
fi

15
0

• In the shape, the field next: maybe ^Node names no region. A field's pointers are in the region of the value that holds them.
• push allocates, so it takes the region to allocate in as a parameter, r: region, and its result is a pointer into it, ^Node@r. The caller decides where the list lives: push(nodes, list, i).
• sum only reads, so it just names a region in its parameter's type, @r, without taking it. It works on a list in any region, and costs nothing extra at run time. sum(none) works too. It calls itself for the rest of the list rather than moving a flex cursor along it, since its parameter is a fixed name and no flex name may be given what one owns (see What a fixed name owns).

Lesson 5: Tasks and regions

How a task mentions a region decides what it can do with it:

shape Node
    value: int
    next: maybe ^Node
fi

task push(r: region, list: maybe ^Node@r, value: int) -> ^Node@r
    <- new Node(Node { value: value, next: list }) at r
fi

task length(list: maybe ^Node@r) -> int
    when list is {node}
        <- 1 + length(node^.next)
    fi
    <- 0
fi

; Two regions, which may be different.
task longer(a: maybe ^Node@x, b: maybe ^Node@y) -> int
    when length(a) > length(b)
        <- length(a)
    fi
    <- length(b)
fi

; One name twice: both lists must be in the same region.
task join(flex last: ^Node@r, flex rest: maybe ^Node@r)
    last^.next = rest
fi

; A region passed on under another name.
task pair(into: region, value: int) -> ^Node@into
    <- push(into, push(into, none, value), value * 2)
fi

task main()
    region small
    region big
    flex a = push(small, none, 1)
    fixed b = push(big, push(big, none, 2), 3)
    show(longer(a, b))
    join(a, pair(small, 10))
    show(length(a))
fi

2
3

• Different names can be different regions. longer takes lists in x and y; the caller passes one in small and one in big. (Inside the task, x and y are treated as different, so it can't link one list to the other.)
• The same name is the same region. join links rest after last, which is only safe when both are in one region, so both are @r, and the call is rejected if they aren't.
• A region can be passed on under another name: pair takes into and passes it to push.
• A task can have scratch regions of its own: a region declared in a task is freed before the task returns, so the result can't point into it. A result can only be in a region the header's parameters name.

A parameter that changes the caller's value is written flex&, and the call gives the place with & (see Parameters that change). Its type names a region like any other, so what the task puts there stays in that region: prepend links a new node into the caller's list, and grow adds to the caller's slice, both in r. A place of another region is refused, since the task would leave a pointer to r in it: given a list of a region s, prepend(&other, r, 3) is expected region 's', got 'r'.

shape Node
    value: int
    next: maybe ^Node
fi

task prepend(flex& list: maybe ^Node@r, r: region, value: int)
    list = new Node(Node { value: value, next: list }) at r
fi

task grow(flex& xs: [int]@r, r: region)
    xs.add(xs.len)
fi

task main()
    region r
    flex list: maybe ^Node@r = none
    prepend(&list, r, 1)
    prepend(&list, r, 2)
    when list is {first}
        show(first^.value)
    fi
    flex xs = new [int]() at r
    grow(&xs, r)
    grow(&xs, r)
    show(xs)
fi

2
[0, 1]

A task that takes its region last can be given it after the call instead, as new is: copy(tree) at kept or copy(tree)@kept is copy(tree, kept). After a + chain of text, at r is the whole chain's, and a part names its own with @ (see The region after a call); with a block's default region, a call that names none uses it.

Lesson 6: Shapes and kinds that hold pointers

shape Node
    value: int
    next: maybe ^Node
fi

kind Tree
    Leaf(value: int)
    Branch(left: ^Tree, right: ^Tree)
fi

task build(r: region, depth: int) -> Tree@r
    when depth == 0
        <- Leaf(1)
    fi
    <- Branch(new Tree(build(r, depth - 1)) at r, new Tree(build(r, depth - 1)) at r)
fi

task leaves(t: Tree@r) -> int
    match t
    case Leaf value
        <- value
    case Branch left right
        <- leaves(left^) + leaves(right^)
    fi
fi

task main()
    region trees
    show(leaves(build(trees, 4)))
    show(leaves(Leaf(5)))

    flex head: Node@trees = Node { value: 1, next: none }
    head.next = new Node(Node { value: 2, next: none }) at trees
    when head.next is {second}
        show(head.value + second^.value)
    fi
fi

16
5
3

A shape or kind that holds pointers (in its fields, or in shapes and kinds it holds by value) lives in a region, written after its name: Tree@r, Node@trees. Everything one value holds is in that one region, so reading head.next of a Node@trees gives a maybe ^Node@trees. A shape without pointers, like Point, lives in no region, and Point@r is an error.

A value built without any pointers, like Leaf(5) or Node { value: 1, next: none }, can go in any region: it takes the region of the place it goes. build can send Leaf(1) as a Tree@r, and leaves(Leaf(5)) works. A binding without a written type can't tell which region such a value is meant for, so head is written head: Node@trees.

Text in a region. Text has a lifetime as well: text lasts as long as the program, as a literal does, and text@r is in region r. Text a value in a region holds is in that region, whatever it was made from, so the title of an Item@items is a text@items:

; A to-do item in a region holds its text there, whatever the text was made from.
kind Status
    Todo
    Blocked(reason: text)
fi

shape Item
    title: text
    status: Status
    next: maybe ^Item
fi

; Names the region, so it takes a status of any region, and sends text of it.
task describe(s: Status@r) -> text@r
    match s
    case Todo
        <- "todo"
    case Blocked reason
        <- reason
    fi
fi

task main()
    region items
    fixed first = new Item(Item { title: "write", status: Status.Todo, next: none }) at items
    fixed second = new Item(Item { title: "test", status: Status.Blocked("no compiler"), next: first }) at items
    show(describe(second^.status))
    fixed title = first^.title
    show(title)
    flex chosen = "nothing"
    show(chosen == title)
fi

no compiler
write
false

Text that lasts fits wherever text of a region is expected (the literals above go into items), and text of a region never goes where it could outlive the region: chosen = title would be an error, since chosen is a text. A task that reads text of a region names one, as it would for a pointer: describe takes a Status@r and sends a text@r, and still takes Status.Todo, whose text lasts. Text read with scan("…") at r is new text, so it is in the region scan names, and so is text joined with a + b at r, made from a value with n.str() at r or text(n) at r, or holding values, "{name} is {age}" at r; a part of text, t[a..b], is the same bytes, so it stays in the region the text is in. A number read from input, scan("Age: ", int), is no memory at all, so that form of scan names no region. A shape or kind holding text but no pointers may name a region or not: Person holds text that lasts, Person@r text in r. Text, the one that goes both ways lists every form that makes new text and every one that doesn't.

One region is made without being written: show(card) writes a shape or kind with its own str, and that text goes in a region the line gets for itself, freed as soon as the line ends. It is the region a program would have declared around the show and thrown away after it, so printing a value of your own needs no region of yours; a region you declare is still the place for text you keep, pass on, or send back.

A method of such a shape or kind is called on a value in some region, which its header and body name @this. It can send what the value holds there, and take pointers into it, and each call works out which region that is from the value. It isn't given the region itself, so it can't allocate there; to make something, it takes a region, as a task does:

shape Node
    value: int
fi

shape Named
    name: text
    node: ^Node

    nameOf() -> text@this
        <- .name
    fi

    alters point(flex to: ^Node@this)
        .node = to
    fi

    made(r: region, value: int) -> ^Node@r
        <- new Node(Node { value: value + .node^.value }) at r
    fi
fi

task main()
    region people
    flex ada: Named@people = Named { name: "Ada".copy() at people, node: new Node(Node { value: 1 }) at people }
    show(ada.nameOf())
    ada.point(new Node(Node { value: 5 }) at people)
    region scratch
    fixed sum = ada.made(scratch, 10)
    show(sum^.value)
fi

Ada
15

ada.point(…) with a node of scratch is an error: point takes its node in @this, which for ada is people. A method that should grow its value, such as adding to a slice the value holds, can't yet (see below).

Lesson 7: Regions with errors and maybe values

shape Node
    value: int
    next: maybe ^Node
fi

task parse_node(r: region, digit: int) -> ^Node@r ~ text
    when digit < 0 or digit > 9
        <- fail "not a digit"
    fi
    <- new Node(Node { value: digit, next: none }) at r
fi

task main()
    region nodes
    fixed good = parse_node(nodes, 7) { <- }
    show(good^.value)
    fixed fallback = parse_node(nodes, 42) {
        failure reason
        show(reason)
        good
    }
    show(fallback^.value)
fi

7
not a digit
7

Regions combine with maybe and T ~ E as you'd expect: ^Node@r ~ text is a pointer into r or a text error. The @r belongs to the pointer, so it comes before ~. A plan B's fallback must be in the same region as the value it replaces: good is also in nodes.

Lesson 8: Scratch work, and keeping what survives

A common shape for a program is: do some work that creates a lot of temporary data, keep a small result, and throw the rest away. With regions, the temporary data goes in a region inside the work's block, and the result is copied into a region outside it:

shape Node
    value: int
    next: maybe ^Node
fi

task push(r: region, list: maybe ^Node@r, value: int) -> ^Node@r
    <- new Node(Node { value: value, next: list }) at r
fi

task sum(list: maybe ^Node@r) -> int
    when list is {node}
        <- node^.value + sum(node^.next)
    fi
    <- 0
fi

task main()
    region kept
    flex best: maybe ^Node@kept = none
    each round in 0..3
        region work
        flex draft: maybe ^Node@work = none
        each i in 0..round + 2
            draft = push(work, draft, i)
        fi
        when sum(draft) > sum(best)
            best = draft.copy()                    ; every node, into kept
        fi
    fi
    show(sum(best))
fi

6

A pointer into work can't be stored in best, which lives in kept (that would leave best pointing at freed memory after the pass). So draft.copy() copies the list into kept, the region best names: every node, following the pointers. Each pass's draft is freed at the end of the pass, so only the lists that were copied stay allocated. A copy keeps a node two pointers share as one node, and copies a cycle as a cycle; where nothing names the region to copy into, write it: draft.copy() at kept (or draft.copy()@kept). See Copying into another region for what a copy covers.

Lesson 9: Slices in a region

An array in a variable, [int#4], is a value like any other and needs no region. When the number of items is known only as the program runs, they go in a region, as a slice: [int]@r is a pointer to the first and a count, and follows every rule a pointer does. new [int](…) at r makes one, copying the items in; xs[a..b] views part of it without copying:

; The first n Fibonacci numbers, in the caller's region.
task fibs(r: region, n: int) -> [int]@r
    flex out = new [int]([1#n]) at r
    each i in 2..n
        out[i] = out[i - 1] + out[i - 2]
    fi
    <- out
fi

; Only reads, so it names the region without taking it.
task sum(xs: [int]@r) -> int
    flex total = 0
    each x in xs
        total = total + x
    fi
    <- total
fi

task main()
    region kept
    fixed numbers = fibs(kept, 10)
    show(numbers[9])
    fixed tail = numbers[5..numbers.len]
    show(sum(tail))
    each round in 0..2
        region work
        flex scratch = new [int](tail) at work
        scratch[0] = 0
        show(sum(scratch))
    fi
    show(tail[0])
fi

55
131
123
123
8

tail is a view of numbers' last five items, in kept. Each pass copies it into work, changes the copy, and frees it at the end of the pass, so tail is unchanged. Storing scratch in a variable of type [int]@kept would be the same error as for a pointer into work. An array in a variable can't be sliced, since it isn't in a region: copy it with new [int](xs) at r, or allocate it there, new [int#4](xs) at r, and slice what the pointer points to (p^[0..2]).

A slice can also grow and shrink: xs.add(v) puts a value last, xs.add(i, v) before item i, and xs.del(i) and xs.del() take an item out and give it. new [int]() at r starts with no items. Adding may need more memory, which comes from the slice's own region, so a task that adds needs that region, as one that calls new does:

; The primes below n, added as they are found, in the caller's region.
task primes(r: region, n: int) -> [int]@r
    flex found = new [int]() at r
    each candidate in 2..n
        flex prime = true
        each p in found
            when candidate % p == 0
                prime = false
            fi
        fi
        when prime
            found.add(candidate)
        fi
    fi
    <- found
fi

task main()
    region kept
    flex numbers = primes(kept, 30)
    show(numbers.len)
    show(numbers.del())
    numbers.add(0, 1)
    show(numbers[0] + numbers[1])
    each round in 0..2
        region work
        flex stack = new [int](numbers) at work
        loop stack.len > 1
            stack.add(stack.del() + stack.del())
        fi
        show(stack[0])
    fi
    show(numbers.len)
fi

10
29
3
101
101
10

found gets its items in kept, the region primes is given. Its first add makes a block with room for more, and later ones fill that room; a full block is replaced by one twice as large, whose items are copied in, and the old one stays in the region until the region is freed (or grows in place, when nothing was allocated after it). Each pass builds stack in work, so its blocks are freed with the pass, and numbers is unchanged: a copy into another region never shares items. A fixed slice, a plain or fixed parameter, or a part xs[a..b] can't change its length. A flex parameter changes the task's own copy; a task changes its caller's slice through a flex& parameter, as grow does in Lesson 5, or through a pointer to what holds it, as in bag^.items.add(v).

Lesson 10: A default region

Writing at r on every line that allocates says where memory goes, and in a block where nearly everything goes to one region it says it over and over. A block may name one of its regions its default: what allocates there needs no at r, and only the lines that go somewhere else name a region.

task collect(r: region default, upto: int) -> [text]@r
    flex lines = new [text]()             ; in r, the region this task was given
    each n in 1..upto
        lines.add("line " + n.str())      ; the join and the number, both in r
    fi
    <- lines
fi

task main()
    region kept default
    fixed lines = collect(kept, 4)
    each line in lines
        show(line)
    fi
    each round in 0..2
        region pass default              ; the inner block's own default
        fixed note = "pass " + round.str()  ; text@pass: freed at the end of the pass
        show(note)
    fi
    fixed after = new int(1)             ; ^int@kept: the outer default again
    show(after^)
fi

line 1
line 2
line 3
pass 0
pass 1
1

The rules are few, and the types don't change: a value allocated in the default still has the region in its type (^int@kept), which is what keeps it from outliving its memory, and what hover in Vela Studio shows.

• One per block. A second default in one block is an error: two lines that look alike would allocate in regions with different lifetimes. An inner block may name its own, and after it the enclosing default is in force again.
• A region a task is given can be one (r: region default), which is where at r repeats most. A region the header only names can't: nothing can allocate there.
• Everything that makes memory takes it: new, new [T](…), joining text, text holding values, x.str() and text(x), scan(prompt), and a call of a task or method that takes its region last and leaves it out (label(n)). A region a task takes anywhere else is still passed by name: collect(kept, 4).
• A copy is the exception. x.copy() goes where the value it becomes goes, which says more than a default could, so a copy that nothing gives a region still asks for one.
• It is opt-in. A block that names no default is exactly as it was: every allocation there names its region.

When to reach for it: a task or a block where one region does nearly all the work. When not to: a block that allocates into two regions in turn, where the names are the point — as in Lesson 8, where scratch work and what survives sit side by side.

Lesson 11: Choosing regions

Rules of thumb, once which types need a region is settled:

• Match regions to lifetimes. Declare a region in the block whose end is when the data stops being needed. Data for the whole program: a region at the top of main. Data for one request, frame, or loop pass: a region inside that block.
• Let callers choose. A task that builds data for its caller takes r: region. A task that only reads names the region in its types. A task's own temporary data goes in a region it declares.
• Don't replace values in a long-lived region inside a long loop. Each new adds memory that stays until the region is freed. To change a value, write through the pointer (p^ = v); for temporary values, use a region inside the loop.
• Prefer plain values when you can. A Point or a small shape passed by value needs no region at all. Reach for pointers when data is linked, shared, or must be changed by another task.
• Copy out to keep a little of a lot. Build in a scratch region, copy the result into a longer-lived one with .copy() (Lesson 8).
• Name a default where one region does the work. In a block or a task where nearly everything goes to one region, region r default (Lesson 10) leaves the region written on the lines that go somewhere else, which are the ones worth noticing. Where two regions share a block, as in Lesson 8, write both.

Lesson 12: Reading the compiler's messages

A run reports every mistake it finds in a file, in the order the lines come, each with the line quoted and the place marked; past twenty it prints the first twenty and 3 more mistakes, not shown; fix these first and check again. Region mistakes come in groups — one wrong region name can make several lines complain — so it is worth reading the first of a group before changing anything. These are the ones that come up most:

7. How it runs

A region is a list of chunks of memory. new takes the next free bytes of the newest chunk, aligned for the type, and copies the value in: a few instructions. When the chunk is full, a new one is added, twice as large as the last, starting at 4 KB and growing up to 1 MB. An allocation too large for that gets a chunk of exactly its size, placed behind the newest chunk, which keeps serving small allocations. Freeing a region frees its chunks, however many values they hold. A region that never allocates costs nothing.

The generated C for Lesson 1's main (vela 01_first.vela --emit-c):

void vela_main(void) {
    vela__rt__region scratch[1] = { VELA__RT__REGION_EMPTY };
    int64_t* count = ((int64_t*)vela__rt__new(scratch, (int64_t[1]){ 41 }, sizeof(int64_t), _Alignof(int64_t)));
    (*(count)) = (vela__rt__add((*(count)), 1, "4:21 in task 'main'"));
    vela__rt__show_int((*(count)));
    vela__rt__region_free(scratch);
    return;
}

A region parameter is a plain vela__rt__region*; region names in types disappear, since C doesn't need them. A copy (value.copy()) is a generated function per type that copies the value's bytes, then its text, its slices' items, and what its pointers point to; each pointed-to value is copied once, remembered in a table, and waits in a list rather than in a C call, so a long list copies without deep recursion. The allocator is about a hundred lines in runtime/vela_rt.h, and the test suite runs the region programs in tests/run and examples under AddressSanitizer and UndefinedBehaviorSanitizer, with leak detection.

8. Limitations and workarounds

Regions trade some flexibility for simplicity. Some of these limits are part of the model; others reject programs that would be safe, because the rules that would accept them would be more complicated. Ideas for regions discusses how each could be lifted.

shape Report
    lines: int
    total: int
fi

task summarize(count: int) -> Report
    region work                          ; only this call's scratch data
    flex sum = new int(0) at work
    each i in 0..count
        sum^ = sum^ + i
    fi
    <- Report { lines: count, total: sum^ }
fi

task main()
    fixed report = summarize(5)
    show(report.total)
fi

10

region long
flex latest = new int(0) at long
each i in 0..1000000
    latest = new int(i) at long        ; a million ints stay allocated until long is freed
fi

task main()
    region long
    flex latest = new int(0) at long
    each i in 0..1000
        latest^ = i                      ; reuse the memory: no new allocation
    fi
    show(latest^)
fi

999

shape Pair
    first: ^int
    second: ^int
fi

region a
region b
fixed p = Pair { first: new int(1) at a, second: new int(2) at b }
; error: expected type ^int@a, got ^int@b; a value can't move to another region

shape Pair
    first: ^int
    second: ^int
fi

task main()
    region a
    region b
    fixed short = new int(2) at b
    ; Copy the value into a, the region the pair lives in.
    fixed p = Pair { first: new int(1) at a, second: new int(short^) at a }
    show(p.first^ + p.second^)
fi

3

flex chosen = "nothing"
chosen = item^.title
; error: expected type text, got text@items; this text is in region 'items', and text here must last as long as the program

region outer
fixed root = new Node(Node { value: 1, next: none }) at outer
when root^.value > 0
    region inner
    fixed leaf = new Node(Node { value: 2, next: root }) at inner
    ; error: expected type Node@inner, got Node@outer; a value can't move to another region
fi

shape Node
    value: int
    next: maybe ^Node
fi

task main()
    region outer
    fixed root = new Node(Node { value: 1, next: none }) at outer
    when root^.value > 0
        region inner
        ; Copy the older value into the younger region.
        fixed older = root.copy() at inner
        fixed leaf = new Node(Node { value: 2, next: older }) at inner
        show(leaf^.value + older^.value)
    fi
fi

3

task grow(list: maybe ^Node@r) -> ^Node@r
    <- new Node(Node { value: 1, next: list }) at r
    ; error: this task can't allocate in 'r', which it only names in its types; take it as a parameter, 'r: region'
fi

shape Bag
    items: [int]

    alters put(value: int)
        .items.add(value)
        ; error: adding to a slice may need more room in its region, and '@this' is the region the value
        ;   this method is called on lives in, which a method isn't given, so it can't allocate there, and a
        ;   region it takes is another one, which the value can't point into; add to it where the value is
        ;   kept, outside the method
    fi
fi

task leaf() -> Tree@r
    <- Leaf(1)
    ; error: the result lives in region 'r', which the task isn't given; take it as a parameter, as in 'r: region'
fi

kind Tree
    Leaf(value: int)
    Branch(left: ^Tree, right: ^Tree)
fi

task leaf(r: region, value: int) -> Tree@r
    <- Leaf(value)
fi

task main()
    region trees
    fixed t: Tree@trees = leaf(trees, 3)
    match t
    case Leaf value
        show(value)
    case Branch _ _
        show("branch")
    fi
fi

3

region a
fixed q = new Node(Node { value: 2, next: none }) at a
when first(none) is {flex n}
    n^.next = q
    ; error: expected type maybe ^Node@_, got ^Node@a; this place holds a value without pointers (of no region), ...
fi

shape Node
    value: int
    next: maybe ^Node
fi

task first(list: maybe ^Node@r) -> maybe ^Node@r
    <- list
fi

task main()
    region a
    flex q = new Node(Node { value: 2, next: none }) at a
    flex start: maybe ^Node@a = new Node(Node { value: 1, next: none }) at a
    when first(start) is {flex n}
        n^.next = q
        show(n^.value + q^.value)
    fi
fi

3

9. Ideas for regions

Easier region passing

Every call to a task that allocates passes a region: push(nodes, list, 1). In a program that allocates a lot, that region argument repeats everywhere, and it is easy to confuse with the real arguments. Several spellings could make it lighter:

Done in part A task that takes its region last is now given it after the call, as new is: push(list, 1) at nodes or push(list, 1)@nodes, and a call that leaves it out takes the block's default region (see The region after a call). What follows is still open for a region taken anywhere but last, and for working the region out from the arguments.

task push(r: region, list: maybe ^Node@r, value: int) -> ^Node@r
    <- new Node(Node { value: value, next: list }) at r
fi

list = nodes.push(list, 1)       ; the same call as push(nodes, list, 1)

task push[r: region](list: maybe ^Node@r, value: int) -> ^Node@r
    <- new Node(Node { value: value, next: list }) at r
fi

task sum[r](list: maybe ^Node@r) -> int      ; a region the task only names
    ...
fi

list = push[nodes](list, 1)

region nodes
flex list: maybe ^Node@nodes = none
list = push(list, 1)             ; r is nodes: list's type says so
fixed other = push[nodes](none, 2) ; nothing names a region, so it is written

Freeing one value early

region cache
fixed big = new own Buffer(Buffer { size: 1024 }) at cache
read(big^)
drop big                         ; its memory goes back to the region now
show(big^.size)                  ; error: 'big' was dropped

pool entities of Entity at world
fixed player = entities.add(Entity { health: 100 })  ; a handle, not a pointer
entities.remove(player)
when entities.get(player) is {e}                     ; none: removed
    show(e^.health)
fi

Lifting today's limitations

when first(none) is {flex n: ^Node@a} ; the case form names the region
    n^.next = q
fi

flex head = Node { value: 1, next: none }
head.next = push(nodes, none, 2)      ; head's region is inferred from this line

shape Edge[from, to]
    source: ^Node@from
    target: ^Node@to
fi

task connect(a: ^Node@x, b: ^Node@y) -> Edge[x, y]
    <- Edge { source: a, target: b }
fi

region kept
each line in lines
    region work
    fixed parsed = parse(work, line)
    when parsed.ok
        move work into kept          ; everything in work is in kept now; work can't be used again
    fi
fi

Safety and diagnostics

Performance

Growing with the other memory models

Regions were chosen over the other options in Future Directions, but those options aren't discarded. Several combine well with regions:

• Borrowed, read-only references (from Rust's model): a task could take a view into any region that lives at least as long as the call, and younger data could point at older data (above).
• Move-only ownership: own pointers that can be dropped early (above), and that can move between threads.
• Capabilities (own, read, write, from the second notebook): a read ^Node@r parameter would document and enforce that a task doesn't change the list.
• Reference counting for the few values shared across a whole program, in a region kind of their own, without making every pointer pay for it.