std::core

The vocabulary every Khora program starts with.

Option and Result, the comparison and display traits, lists, arrays, strings, vectors, maps and dictionaries, and the pieces structured concurrency is built out of – regions, fibers, nurseries and Shared. Nothing here is optional in the way the rest of std is: two libraries that disagree about what an Option is cannot exchange one.

Where the effects went

Khora tracks effects as rows on the signature rather than as a wrapper type, so there is no Effect<A, R, E> here. A computation’s requirements live in its with clause and its failures in its raises clause; both are inferred on private functions and written out on exported ones.

The module is std::core rather than std::effect because effect is a reserved word, so std::effect will not lex as a path.

API at a glance

Types: Ordering · Option · Result · Redacted · Validated · List · Halves · Parts · Step · Range · Mapped · Filtered · Taken · Never · Region · Fiber · Outcome · Array · Split · Ptr · Chain · Pair · Least · Dict · Map · Vector · SharedFn · Changed · Channel · Handoff · Shared · Fibers · ChildFailed

Traits: Eq · Ord · Hash · Show · Share · Iterator · Functor · Applicative · Traversable

Effects: Scope · Nursery

Methods: Bool · Char · Ordering · Option\<A> · Result\<A, E> · Redacted\<A> · Validated\<A, E> · List\<A> · List\<A> · List\<A> · List\<A> · List\<Int> · Region · Scope · Fiber\<A, 'er> · Array\<A> · Array\<U8> · Int · String · Float · Int · Ptr · String · U8 · U16 · U32 · U64 · I8 · I16 · I32 · Dict\<K, V> · Dict\<K, V> · Map\<K, V> · Vector\<A> · SharedFn\<A, B, 'er> · Channel\<A> · Handoff\<A> · Shared\<A> · Fibers

Trait implementations: Show for Int · Show for Float · Show for Bool · Show for Char · Eq for Char · Ord for Char · Hash for Char · Show for String · Eq for Int · Ord for Int · Hash for Int · Eq for Bool · Eq for String · Hash for Bool · Hash for String · Ord for String · Eq for Ordering · Show for Ordering · Show for Option\<A> · Eq for Option\<A> · Ord for Option\<A> · Show for Result\<A, E> · Eq for Result\<A, E> · Show for Redacted\<A> · Iterator for Range · Show for List\<A> · Eq for List\<A> · Ord for List\<A> · Iterator for List\<A> · Iterator for Mapped\<I, B> · Iterator for Filtered\<I> · Iterator for Taken\<I> · Functor for Option · Applicative for Option · Traversable for Option · Functor for List · Traversable for List · Eq for U8 · Ord for U8 · Show for U8 · Hash for U8 · Eq for U16 · Ord for U16 · Show for U16 · Hash for U16 · Eq for U32 · Ord for U32 · Show for U32 · Hash for U32 · Eq for U64 · Ord for U64 · Show for U64 · Hash for U64 · Eq for I8 · Ord for I8 · Show for I8 · Hash for I8 · Eq for I16 · Ord for I16 · Show for I16 · Hash for I16 · Eq for I32 · Ord for I32 · Show for I32 · Hash for I32 · Show for Pair\<K, V> · Show for Dict\<K, V> · Show for Map\<K, V> · Show for Vector\<A>

Functions: assert · assert_that · print · todo · join_all · nursery · bounded_nursery · scoped · acquire · attempt

Types

Ordering

pub type Ordering =
  | Less
  | Equal
  | Greater;

The result of comparing two values.

A three-way answer rather than two booleans: one comparison decides all six operators, and a type cannot accidentally disagree with itself about < and >=.

Option

pub type Option<A> =
  | Some(value: A)
  | None;

A value, or nothing.

For absence that is ordinary and expected: a key that is not in a map, the head of an empty list. When the absence is a failure — something went wrong and the caller should know what — the type is Result, and ok_or below is the bridge between them.

Result

pub type Result<A, E> =
  | Ok(value: A)
  | Err(error: E);

A value, or the reason there is not one.

The same thing a raises row says, said as a value. A tagged return already is “an error or a value”; which of the two readings a function offers is a choice about its caller, and attempt is where one becomes the other.

Redacted

pub type Redacted<A> = | Secret(value: A);

A value that a log line cannot get at.

A password, a token, an API key. The leak everybody actually has is not a clever one: it is a Config record in a structured log, or a ${} in a message written while debugging something else, and no review catches it because nothing about the line looks wrong.

Show prints <redacted>, and there is no Encode. Those two sentences are the whole design, and each is deliberate in a different direction:

• With Show, a record holding one still derives Show, so the config a service prints at start-up stays printable and the secret in it does not appear. A Redacted with no Show at all would look stricter and be worse: it makes the containing record unprintable, and the way people answer that is by not wrapping the secret.
• Without Encode, a record holding one does not derive Encode, and the build stops. That is the right place to stop: a type that serializes a secret is a bug, and one that serializes "<redacted>" is a payload that fails to round-trip somewhere further away. It still derives Decode, because a secret arrives from somewhere: it reads, and does not write.

This is where a nominal type earns its keep. Elsewhere the same idea is a toString override, which any structured logger walks straight past because it reads fields rather than calling it. Here it is a missing impl, which is a compile error.

derive(Show)
type Config = { host: String, password: Redacted<String> };

let settings: Config = { host: "db.internal", password: Redacted::of(secret) };
print(Show::show(settings));   // Config { host: db.internal, password: <redacted> }
connect(Redacted::expose(settings.password));

Interpolation is covered by the same Show. "${key}" calls it like any other hole, so the line compiles and prints <redacted>.

Nothing needs expose to print one. expose hands over the secret itself, which is the shortest route into a log for somebody who only wanted their message printed; a hole that already redacts removes the reason to reach for it.

So every way a value reaches a log – show, a derived Show on something holding it, and a hole – goes through the one implementation, and there is no second thing to keep in step with it.

Deliberately no Eq. Comparing two secrets is a real thing to want and a derived Eq would compare them byte by byte and stop at the first difference, which is how a timing side channel gets written by somebody who was not writing one. Anybody who needs the comparison writes expose and says so.

Validated

derive(Eq, Show)
pub type Validated<A, E> =
  | Valid(value: A)
  | Invalid(errors: List<E>);

Every reason the input was wrong, rather than the first one.

Result is the right shape when the next step depends on the last: it stops, because there is nothing sensible to do with a value that is not there. Validation is the other shape. The fields of a form, the keys of a config, the columns of a row – these do not depend on each other, and reporting them one restart at a time is a person running the program five times to be told five things it knew the first time.

Applicative::map2 is the operation that distinguishes the two, and std::core’s own docstring on it has been pointing here since it was written: “Option gives up if either is None, and a validation type would collect both failures.”

let settings = Validated::map2(
  integer("PORT"),
  string("HOST"),
  fn (port, host) => Settings { port: port, host: host },
);

Not an Applicative instance, though it is one in shape. The instance would need Validated<_, E> – the error parameter fixed and the value parameter free – and Khora has no partial application of a type constructor. The methods are the same functions under their own names, and the instance can arrive later without changing a call site.

List

pub type List<A> =
  | Nil
  | Cons(head: A, tail: List<A>);

A singly-linked list: the sequence with no capacity, no reallocation and no index.

Cheap at the front and linear everywhere else. Vector is the one to reach for when the work is indexing or appending; this is the one to reach for when the work is “each of these, in order”, which is most of it.

[a, b, c] builds one — the literal is Cons(a, Cons(b, Cons(c, Nil))) and needs List in scope, exactly as 0.01d needs Decimal.

Halves

pub type Halves<A> = {
  pub left: List<A>,
  pub right: List<A>,
};

A list split down the middle, for sort.

Parts

pub type Parts<A> = {
  pub kept: List<A>,
  pub rest: List<A>,
};

A list split by a question, for partition.

Named rather than reusing Halves, whose left and right say where a piece came from and not what is true of it. A caller of partition reads .kept and knows which side answered yes; reading .left they would have to go and look.

Step

pub type Step<S, A> =
  | Yield(state: S, item: A)
  | Done;

One step of an iteration: the next item and the rest, or the end.

Khora has no mutable references, so Rust’s fn next(&mut self) -> Option<Item> is not expressible: there is no way to hand next something it may write through. An iterator hands back its successor instead. for desugars to this and reads the same.

This said “no mutable references and no mutable fields” until mut fields arrived – Map is built out of one, Vector out of two – and the second half stopped being true without the first half needing to change. It is the reference that is missing, not the mutation.

This is the allocation for pays per element. A Step is an ordinary heap object, so a for loop is about 3.6 times slower than the same loop written out – measured in bench/iteration. Unboxing is what would close that; desugaring for to a closure would not.

Range

pub type Range = | Of(from: Int, to: Int);

Range::Of(from, to) yields from up to but not including to.

Mapped

pub type Mapped<I, B> = { inner: I, f: (I::Item) -> B };

Iterator::map(it, f): the same walk, with each item put through f.

Filtered

pub type Filtered<I> = { inner: I, keep: (I::Item) -> Bool };

Iterator::filter(it, keep): the items keep answers true for.

Taken

pub type Taken<I> = { inner: I, left: Int };

Iterator::take(it, n): at most the first n items.

Never

pub type Never;

The empty type. A function whose return type is Never does not return normally — it raises, diverges, or transfers control to a handler.

The bottom type, which means a Never branch takes the other branch’s type. if index < 0 { stop(index) } else { xs } is an A when xs is, including when A is a type the caller chose — the branch that cannot return has nothing to disagree with.

The name is the compiler’s, the way Int and String are, so it needs no import. This declaration is where it is documented and what an import naming it resolves against; nothing resolves to it. It is the solver’s bottom — the type a raise already has.

Region

pub type Region;

A region, and the finalizers deferred to it.

The type is here rather than hidden because scoped is written in Khora and has to name it. Reference counted like everything else — which is the whole mechanism: releasing the last reference runs the finalizers, and the paths that release a binding are already the paths a region has to end on.

Fiber

pub type Fiber<A, 'er>;

A running fiber, and the only way to wait for one or stop it.

Releasing a handle joins, so a fiber cannot outlive the binding that holds it — on every path out, including a raise passing through. Put one in a region and the region waits; put it in a block and the block does. That is where structured concurrency comes from, and it needed nothing of its own.

Outcome

pub type Outcome<A> =
  | Answered(value: A)
  | Stopped;

What a fiber ended as, when the asking must not unwind the asker.

Fiber::outcome produces one. Answered carries what the fiber computed; Stopped says a cancellation reached it and carries nothing, because a fiber that was stopped has no answer to carry.

Stopped is not a failure. A child that failed raises on the fiber’s own row and never appears here — which is what keeps a failure the caller’s to interpret rather than one arm among two.

Array

pub type Array<A>;

A fixed number of elements, side by side.

Fixed because growing is a library question and this is the primitive one is built out of: { mut items: Array<A>, mut len: Int } is a vector, and it can be written in Khora now that a field can be written.

Reading an element is a bounds check and a load — no call — because the layout is a contract with the code generator rather than something the runtime hides. What the runtime does own is allocation and release, both of which need the length at run time.

Split

pub type Split = {
  pub head: String,
  pub rest: String,
};

What split_once found: the text before the separator, and everything after it.

Ptr

pub type Ptr;

An opaque machine address: a C void *.

Not counted, not dereferenceable, and never a pointer into Khora’s own heap. It exists so a foreign library can hand back a handle — a FILE *, an SSL_CTX * — and be given it again later. Nothing in the language turns a Khora value into one, which is what makes a dangling Ptr impossible: every pointer that exists came from the other side, and its lifetime is that side’s business.

Lending a buffer across is the harder question and this type deliberately does not answer it.

Chain

pub type Chain<K, V> =
  | Empty
  | Node(key: K, value: V, rest: Chain<K, V>);

One bucket’s worth of entries: the keys that hashed to the same slot.

Separate chaining rather than open addressing, because a chain is an ordinary recursive ADT and needs no tombstones, no sentinel value and no second array saying which slots are live. It allocates per entry, which is the price, and it is the shape the language is actually good at.

Pair

pub type Pair<K, V> = {
  pub key: K,
  pub value: V,
};

One key and the value under it.

Least

pub type Least<K, V> = {
  key: K,
  value: V,
  rest: Dict<K, V>,
};

The smallest entry of a tree, and what is left without it.

Dict

pub type Dict<K, V> =
  | Empty
  | Node(size: Int, key: K, value: V, left: Dict<K, V>, right: Dict<K, V>);

An ordered map that is never written in place.

Map is the other one: a hash table that mutates its buckets, which is fast and is exactly why it cannot cross a fiber or go in a Shared. This is built out of ordinary variants, so it holds nothing writable and is shareable in the ordinary structural way — a Shared<Dict<K, V>> is how a cache several fibers use is spelled.

Persistent, so an insert gives back a new map and the old one is still there. The two share everything the insert did not touch, which is what makes that affordable: one path from the root is rebuilt, and the rest of the tree is the same objects with one more reference each.

Weight-balanced (Adams), so every operation is logarithmic in the size and the recursion here is bounded by the depth rather than by the length — the distinction that String::slice got wrong and paid for.

Map

pub type Map<K, V> = {
  mut buckets: Array<Chain<K, V>>,
  mut count: Int,
};

A hash table: unordered, mutated in place, and the fast one.

Map mutates and Dict does not, which is the whole choice between them. Insert into a Map and the map you were holding has changed; insert into a Dict and you get a new one and the old is untouched. So a Map cannot go into a Shared and cannot cross into a fiber, and a Dict can.

Keys need Hash, and Hash requires Eq because the two have to agree — see the trait. Entries come back in no particular order, and not even a stable one: growing rehashes everything.

Vector

pub type Vector<A> = {
  mut items: Array<A>,
  mut len: Int,
  mut wanted: Int,
};

A sequence that grows: an array, the part of it that is in use, and a reallocation when those two meet.

The container to accumulate into. Array<A> is fixed at the length it was allocated with, so a caller that does not know the count in advance cannot use one; List<A> grows, but at the front, one allocation and one pointer chase per element, and indexing it is a walk. This is contiguous, indexed in constant time, appended to in amortized constant time, and — the point of the whole exercise — a constant number of allocations for any number of elements.

Fiber-local, like Map and for the same reason: the mut fields are what make push cheap, and they are exactly what the sharing rules refuse to a second fiber. A sequence several fibers write is a Shared<List<A>>, which is slower and says so.

Why new takes no seed element. Array::new needs a value to fill with, and there is no value of an arbitrary A to be had: Vector::new() has nothing in its hands, and neither has with_capacity, whose whole purpose is to allocate before there is anything to put in it.

A vector of a hundred integers is two live objects — the vector and its array — at that length and at every other. Allocating per element is precisely the property a vector exists to not have, and it is the reason to reach for one over a List. Holding Array<Option<A>> would cost a Some per element and give that property away. The other way out is a new that takes a seed element, which is C++’s value-initialization: it turns “give me somewhere to collect results” into “produce a result first”, and a type with no cheap value has to fabricate one.

The answer is Array::empty, which is a zero-length array and needs no fill because it has no cells. The storage starts there and costs nothing; the first push allocates for real, and it can, because the element being pushed is the value to fill with. Every cell of a fresh array holds that element until a later push overwrites it, which for a boxed A is one reference count per cell rather than one allocation per cell, and for an Int is nothing at all.

with_capacity is the field that falls out of this: it cannot allocate when it is called, so it records what was asked for in wanted and the first push honors it. A capacity is a promise here, not storage — capacity answers with what is really allocated, so a vector that has been asked for a thousand cells and pushed to zero times still reports nought. The alternative, reporting the promise, would be a number no memory corresponds to.

What this costs against the Option cells is eager release. There is no “empty” to write into a cell a pop vacated, so pop writes the vector’s first element there instead — a value of A it is guaranteed to have — which releases the popped one just as promptly and costs a reference count. Popping the last element and clear both drop the array outright, which releases everything at once and is why neither keeps the storage; wanted remembers the size, so refilling reallocates exactly once.

wanted

mut wanted: Int

How big the first allocation should be. Meaningless once there is one.

SharedFn

pub type SharedFn<A, B, 'er>;

A function two fibers may hold.

A closure is never shareable on its own: what it captured is not in its type, so no amount of looking at (Request) -> Response says whether the thing behind it can be written. That is fine until a container of closures has to cross — a router holding its handlers, a table of callbacks — at which point the whole container is stuck on this side.

This is the proof, reified. SharedFn::of accepts only a closure written at the call, where the captures are on the screen and can be checked; what it returns has forgotten how it was made, and is shareable because the check already happened. A Route holding one is shareable in the ordinary structural way, with nothing special said about routers.

The cost is the wrapper at the mount site, and that is the honest price: the alternative is a bit in every function type, which colors every container of a function all the way up.

Changed

pub type Changed<A, B> = {
  pub state: A,
  pub result: B,
};

A new state, and something to hand back that is not the state.

What Shared::modify asks its change function for. A record rather than a tuple – Validated::zip shows a tuple literal is perfectly writable – because named halves read better than positional ones at the call, and the two halves here are the two things a caller is most likely to swap.

Channel

pub type Channel<A>;

A bounded queue one fiber puts values into and another takes them out of.

Shared<A> is a cell; this is a hand-off. The two answer different questions and the difference is what a value is while it is in flight. A cell holds one value that anybody may read or replace. A channel holds a queue of values that each go to exactly one taker, and — the part that matters — a fiber waiting at either end gives its worker back rather than spinning or blocking a thread.

What it is for

Three things, and they are the same thing seen from different sides.

Owning a resource that cannot be shared. A handler may not capture anything writable, and a database connection is writable and strictly serial — two fibers writing one socket interleave their frames. So one fiber owns the connection and the others send it requests. The handler captures the channel, which is Share, and never the connection, which is not. A database driver is the shape this is for.

Backpressure. A full channel stops the sender until a taker catches up. That is not a limitation to be worked around; it is how a service under more load than it can serve declines work at the edge instead of queueing it until memory runs out.

A pool. A channel holding the four idle workers is the pool: taking one is a receive, giving it back is a send, and waiting for one is what the channel already does.

Closing

close says nothing more will be sent and releases everybody waiting. A receive then drains what is already queued before answering None, because values already sent are still worth having. Closing twice is allowed: the fiber that owns a channel and the fiber that finishes with it are often different code, and neither should have to know which went first.

What it does not do

No rendezvous. bounded(0) gets a capacity of one rather than a channel where a send waits for a receive. Zero is a useful thing and it is not this thing; building it here would mean a sender waiting on a receiver that is waiting on a sender, and getting that wrong is a hang rather than an error.

No select. Waiting on the first of several channels wants a primitive of its own, and nothing has needed one yet.

Handoff

pub type Handoff<A>;

A queue that gives values away.

What it is for: handing a value that can be written to another fiber. A Channel shares what it carries, so it carries only Share values. A hand-off carries anything, because a send gives the value away: the sending fiber keeps nothing, so the receiver is the only fiber that can reach it. A database connection a pool lends out is the case it exists for.

What the send requires. The value sent must be the last use of it, and nothing writable it reaches – a record with a mut field, an Array, a Map – may be held by anything else. The compiler checks the first. The second is checked when the send runs, by reference count: a send that finds a writable part still held elsewhere stops the program, naming the type, rather than let two fibers hold one writable object.

A part of the value that is Share may be held elsewhere. It cannot be written, so it is marked for the receiving fiber the way a channel send marks what it carries.

What trips the check. Anything the sending fiber still uses after the send that holds a writable part: a binding read again later, or a value the sent one was taken out of that is read again later.

let got = connect(settings);
match got {
  Result::Ok(c) => Handoff::send(pool, c),
  Result::Err(_) => false,
};
log(got)

stops the program at the send, because got still holds c for the log after it. Sending a match arm’s binding is fine when the value matched on is not used again. The stop happens on every send of a shape that trips it, not by chance, so a test that runs the path finds it.

What it costs. A walk over every object in the value that is not already shared, at every send: about 2,400 instructions for a record of a dozen objects. Receiving costs what a channel receive does.

Like a channel’s, a send and a receive are cancellation points, a full hand-off makes the sender wait, and close releases everybody waiting.

Shared

pub type Shared<A>;

A value two fibers may both change.

The sharing rules refuse a mutable record to a second fiber on purpose, and refuse a handler that captures one, because two fibers writing one value is a race. This is what they refuse them until: a cell holding a value, with the reads and writes serialized.

Mutation becomes replacement. There is no borrow of the inside — a counter is Shared::update(count, fn n => n + 1), not count.n = count.n + 1 — and that is the whole of why this is safe rather than careful. Handing out the inner value would mean stopping it escaping the critical section, and without lifetimes there is no way to say that. Nothing unshareable goes in or comes out, so there is nothing to leak.

The contents must be Share for the same reason, which also means a Map cannot go in one: it mutates its buckets in place. Dict is the ordered persistent map, and is what a shared table is made of.

Fibers

pub type Fibers;

A nursery: the fibers started under it, and the guarantee that none of them outlives it.

Releasing one cancels its children and waits for them, which is where structured concurrency comes from — a fiber cannot escape the block that started it, because the binding holding the nursery ends on every path out. nursery is the ordinary way to get one.

One value means both “wait for the children” and “the answers are no longer wanted”, without ever being told which of the two it is: on the ordinary path nursery has already waited, so the release finds nothing left to stop.

ChildFailed

pub type ChildFailed = { pub children: Int };

Raised by a nursery when one or more of its children ended with an error.

Not the child’s own error, because there is no such single thing. A nursery holds Fiber<(), 'er> with the row quantified per adoption, so two children may fail with two unrelated types and the nursery has nowhere to put either — Nursery says why. What survives the handles is the count, so that is what this carries.

A child that a nursery canceled is not a failure and is not counted: cancellation is what a nursery does to its children on the way out, and counting it would make every early exit look like a fault.

match attempt(fn () => nursery(gather)!) {
  Result::Ok(answer) => answer,
  Result::Err(failure) => retry_smaller(failure.children)!,
}

Traits

Eq

pub trait Eq

Whether two values of a type are the same value.

Structural, and written rather than derived for a type whose identity is not its contents. Nothing here defines !=: one operator is one thing to get right, and the negation is the negation.

Float is not an instance, because NaN == NaN is false and a type whose values are not equal to themselves breaks every container built on this one. The numbers design note has the argument.

eq

fn eq(self, other: Self) -> Bool

Whether these are the same value.

Ord

pub trait Ord: Eq

Ordering refines equality: anything orderable can be compared for equality, so Ord requires Eq rather than repeating it.

cmp

fn cmp(self, other: Self) -> Ordering

Where self falls relative to other.

Must agree with eq: cmp answering Equal and eq answering false is a sort that loses elements and a search that cannot find them.

Hash

pub trait Hash: Eq

A value that can be a key.

Requires Eq rather than repeating it, because the two have to agree: a map finds a key by hashing it to a bucket and then comparing, so equal values must hash equal. Unequal values may collide — that is what the bucket’s chain is for — but two values that eq says are the same and hash sends to different buckets are an entry that can be inserted and never found.

Float is deliberately not an instance, because it is not an instance of Eq: NaN == NaN is false, and a key that is not equal to itself is a lost entry in every language that allows one.

hash

fn hash(self) -> Int

A number to bucket by. Any number: spreading it out is the map’s job, not this one’s, so an implementation only has to be consistent.

Show

pub trait Show

A value rendered for a person to read.

Not a serialization format. show is for a log line, an error message and a test’s failure output; std::json is for something that has to be read back. Nothing promises that show round-trips, and Float is the one place it happens to — see the compatibility design note, which makes that a promise about Float rather than about Show.

show

fn show(self) -> String

This value, as text.

Share

pub trait Share

Two fibers may hold this at once.

A marker: no methods, and implementing it asserts rather than provides. Nothing has to write it for an ordinary type — a record, a variant, a tuple is shareable exactly when everything inside it is, and the compiler can see that. This is for the types it cannot see inside: one declared with no body, whose behavior lives in the runtime or across the C ABI.

Those default to unshareable, which is the only safe way round. Array can be written through Array::set and Ptr points at memory this language did not allocate; both look like empty structures and neither is safe for two fibers to share. So the author says which is which, and the reader can see where the assertion was made.

Fibers are operating-system threads today, so this is Sync rather than Send: both fibers keep their reference, and neither hands it over.

Iterator

pub trait Iterator

Something a for loop can walk.

One method, and it hands back a successor rather than mutating: see Step above for why that shape rather than Rust’s. Implementing it is what makes a type usable in for.

Associated types

Item

type Item;

What the iteration yields.

Effects

type Effects;

What pulling from it requires, which is what makes this one trait rather than two.

Effects = {} is an ordinary iterator over something already in memory: Range and List below, and a for loop over either asks its enclosing function for nothing. Effects = { fs: FsRead } is a stream of the lines of a file, and a for loop over that requires fs of whoever wrote it, because pulling the next line reads the disk.

Rust needs Iterator, Stream and AsyncIterator for this, and Effect needs Iterable and Stream, because in both of them an effect changes a function’s type. Here it is a row, and a row can be empty – so one trait, one set of combinators, written once.

Functions

next

fn next(self) -> Step<Self, Self::Item> with Self::Effects

The next item and the iterator that follows it, or Done.

map

fn map<B>(self, f: (Self::Item) -> B) -> Mapped<Self, B>

Each item put through f. Nothing is pulled until something asks.

filter

fn filter(self, keep: (Self::Item) -> Bool) -> Filtered<Self>

The items keep answers true for.

take

fn take(self, n: Int) -> Taken<Self>

At most the first n.

fold

fn fold<B>(self, init: B, f: (B, Self::Item) -> B) -> B with Self::Effects

Walks to the end, carrying init through f.

The consumer is where the effects happen. map and filter build a description and require nothing; this is what pulls, so this is what carries Self::Effects – which is why a pipeline over a file asks for fs at the fold and not at the map.

each

fn each(self, f: (Self::Item) ->()) ->() with Self::Effects

f on each item, for the effect rather than the answer.

count

fn count(self) -> Int with Self::Effects

How many items it yields. Walks the whole thing, so it is not free on a stream that reads a socket.

Functor

pub trait Functor

A container whose contents can be replaced one for one.

Higher-kinded: Self is applied to a type here rather than being one, which is what lets a single map serve Option, List and everything else with a shape. docs/vision.md names this as a non-negotiable, and it is the thing Rust’s trait system cannot say.

map

fn map<A, B, 'ef, 'er>(self: Self<A>, f: (A) -> B with 'ef raises 'er) -> Self<B> with 'ef raises 'er

Every element replaced by f of it, in the same shape.

f may fail and may need capabilities, and the rows say so rather than the signature quietly forbidding it. Without them the only way to map a fallible function over a container was to write the walk out by hand, which for a language whose headline is typed failure is the collection library and the failure system declining to compose.

Variables, so nothing that maps a pure function has to change: they instantiate empty and the call site keeps its shape.

Applicative

pub trait Applicative: Functor

pure lifts a value; map2 combines two containers. map2 rather than ap because ap would need a container of functions, and reading a signature is easier than reading Self<(A) -> B>.

pure

fn pure<A>(value: A) -> Self<A>

One value, in the smallest container that can hold it.

map2

fn map2<A, B, C>(self: Self<A>, other: Self<B>, f: (A, B) -> C) -> Self<C>

Two containers combined element-wise by f.

What “combined” means is the instance’s to decide: Option gives up if either is None, and a validation type would collect both failures.

Traversable

pub trait Traversable: Functor

Walks a structure left to right, collecting the effects of each step.

This is the abstraction Rust cannot express and the reason higher-kinded types are a non-negotiable in docs/vision.md: one traverse per container serves every Applicative.

traverse

fn traverse<A, B, F: Applicative>(self: Self<A>, f: (A) -> F<B>) -> F<Self<B>>

f over every element, with the containers turned inside out.

A List<A> and an (A) -> Option<B> give an Option<List<B>>: one answer for the whole walk rather than a list of answers. That inversion is the whole point — it is how “all of these, or the first reason not” is written once instead of per container.

Effects

Scope

pub effect Scope {
  defer: (() -> ()) -> (),
}

Resource lifetimes.

A finalizer registered with a scope runs when the enclosing region ends, however it ends: falling off the end, an early return, or a raise passing through.

A scope stays on the fiber that opened it, so a finalizer runs on the fiber that deferred it and may capture a record with mut fields that fiber goes on writing. A fiber’s body cannot capture one, nor can a handler for another effect; a child is given its own with scoped(work).

The operation takes only a thunk. A handler’s fields are ordinary closures and a closure is monomorphic, so an operation cannot be generic — and it need not be: acquire below is an ordinary generic function that closes over the value and the release, which is where the polymorphism belongs.

defer

defer: (() ->()) ->()

Nursery

pub effect Nursery {
  adopt: (Fiber<(), 'er>) -> (),
}

Where a spawned fiber goes.

The operation takes a fiber rather than a thunk, because a thunk cannot be forwarded to Fiber::spawn at all. A fiber’s body has to be written where it starts, so that what it closes over can be checked against the rule that a mutable value may not cross — a thunk that arrived from somewhere else took its captures with it, and that is the one thing the check cannot see.

The answer is fixed at () because an operation cannot be generic in a type, and because a nursery has nothing to do with an answer it cannot hand back. A fiber whose result matters is one you keep the handle to and join.

The row is not fixed, and that is worth a sentence because it is the one place an operation is polymorphic. 'er here is quantified per call rather than per handler: two children raising two different things are both adopted by one nursery. It costs nothing at run time — a capability crosses as evidence and an error as a tag, so the handler’s closure is the same code for every row, which is exactly why a row can be generic where a type cannot.

So the idiom is one call inside another, and the body is on the screen:

nursery.adopt(Fiber::spawn(fn () => analyze(id)!));

adopt

adopt: (Fiber<(), ’er>) ->()

Methods

Bool

impl Bool

to_string

pub fn to_string(self) -> String

"true" or "false".

The same text show gives, under the name the other scalars use – Int::to_string and Float::to_string are both here, and a reader who has met those goes looking for this one. Show for Bool is written in terms of it rather than the other way round, so there is one place the two words are spelled.

Char

impl Char

One Unicode scalar value.

Not a String of length one. A String can be empty or a thousand characters, so a function taking one has to decide what those mean; a Char cannot be either. It is thirty-two bits and lives in a register, which is the other half: scanning a string a character at a time through one-character Strings allocates once per character.

A scalar value, which is not every number. The range stops at 0x10FFFF and the surrogates 0xD800 to 0xDFFF are a hole in the middle of it – they exist only to encode a pair in UTF-16 and are not characters. Char::from_code is checked for both.

Written 'a', '\n', '\u{1F600}'. The escapes are the string ones.

code

pub fn code(self) -> Int

The code point, as an Int. Every Char has one, so this cannot fail.

from_code

pub fn from_code(value: Int) -> Char

The character with this code point, or a stopped program.

Stops rather than raises, for the reason every other narrowing conversion in this library does: a number that is not a character is a mistake in the program rather than a condition to handle, and U8::of sets the precedent. Check the range first if the number came from outside.

to_string

pub fn to_string(self) -> String

This character as a one-character string.

The UTF-8 encoding, written out here rather than asked of the runtime: four branches on the code point and String::from_bytes at the end, so the standard library’s own text handling has no intrinsic under it that a reader cannot follow.

utf8_length

pub fn utf8_length(self) -> Int

How many bytes this character takes in UTF-8: 1, 2, 3 or 4.

is_digit

pub fn is_digit(self) -> Bool

'0' to '9'. ASCII only, and the name says so nowhere else, so: this is not Nd. Arabic-Indic and Devanagari digits are digits to Unicode and not to this, because a parser that accepted them would then have to decide what Int::of_string does with them.

is_alpha

pub fn is_alpha(self) -> Bool

'a' to 'z' and 'A' to 'Z'. ASCII only, for the reason on is_digit.

is_alphanumeric

pub fn is_alphanumeric(self) -> Bool

A letter or a digit, both in the ASCII sense above.

is_whitespace

pub fn is_whitespace(self) -> Bool

Space, tab, newline, carriage return.

to_upper

pub fn to_upper(self) -> Char

'A' for 'a', and everything else unchanged. ASCII only.

to_lower

pub fn to_lower(self) -> Char

'a' for 'A', and everything else unchanged. ASCII only.

Ordering

impl Ordering

is_less

pub fn is_less(self) -> Bool

Whether the comparison came out Less.

is_equal

pub fn is_equal(self) -> Bool

Whether it came out Equal.

is_greater

pub fn is_greater(self) -> Bool

Whether it came out Greater.

reverse

pub fn reverse(self) -> Ordering

Ordering::reverse(Ord::cmp(a, b)) sorts descending without a second comparison.

Option<A>

impl<A> Option<A>

is_some

pub fn is_some(self) -> Bool

Whether there is a value.

For a condition. Reaching for the value afterwards means matching twice; match once instead.

is_none

pub fn is_none(self) -> Bool

Whether there is not.

unwrap_or

pub fn unwrap_or(self, fallback: A) -> A

The value, or fallback if there is none.

fallback is evaluated either way. unwrap_or_else takes a closure for when producing it is expensive.

unwrap_or_else

pub fn unwrap_or_else<'ef, 'er>(self, fallback: () -> A with 'ef raises 'er) -> A with 'ef raises 'er

The value, or the result of calling fallback.

The closure is called only when there is nothing, which is the whole difference from unwrap_or — reach for this when producing the fallback costs something.

ok_or

pub fn ok_or<E>(self, error: E) -> Result<A, E>

Turns absence into a failure, which is how an Option joins a raises chain.

and_then

pub fn and_then<B, 'ef, 'er>(self, f: (A) -> Option<B> with 'ef raises 'er) -> Option<B> with 'ef raises 'er

The next step, when it can also come to nothing.

map with a function that returns an Option gives an Option<Option<B>>, which nobody wants and everybody writes once. This flattens as it goes.

What its absence costs is a shape, not a keystroke. Reading a record out of positional fields is one lookup that may fail per field, and without this each is a match inside the previous one.

filter

pub fn filter<'ef, 'er>(self, wanted: (A) -> Bool with 'ef raises 'er) -> Option<A> with 'ef raises 'er

The value if it is there and wanted says so, and nothing otherwise.

The bridge from a predicate back into the chain: find gives an Option, and asking a second question about what it found should not mean leaving the chain to ask it.

Result<A, E>

impl<A, E> Result<A, E>

is_ok

pub fn is_ok(self) -> Bool

Whether this succeeded.

is_err

pub fn is_err(self) -> Bool

Whether it did not.

unwrap_or

pub fn unwrap_or(self, fallback: A) -> A

The value, or fallback if there was an error.

The error is discarded. That is the right thing exactly when the caller has already decided the reason does not change what they do; when it might, match.

ok

pub fn ok(self) -> Option<A>

Discards the error, which is the one direction that cannot fail.

map_err

pub fn map_err<F, 'ef, 'er>(self, f: (E) -> F with 'ef raises 'er) -> Result<A, F> with 'ef raises 'er

Rewrites the error and leaves the value alone.

What a function does at the edge of its own vocabulary: a caller should see the failure in terms of what they asked for, not in terms of whatever was reached to answer it.

map

pub fn map<B, 'ef, 'er>(self, f: (A) -> B with 'ef raises 'er) -> Result<B, E> with 'ef raises 'er

Rewrites the value and leaves the error alone.

The other half of map_err: a reader who has met one goes looking for this and finds a match.

Not Functor, which takes one type parameter and Result has two. An impl Functor for Result<_, E> needs partial application of a type constructor, which this language does not have and does not need for one method.

and_then

pub fn and_then<B, 'ef, 'er>(self, f: (A) -> Result<B, E> with 'ef raises 'er) -> Result<B, E> with 'ef raises 'er

The next step, when it can fail the same way.

The error type is shared, which is what makes this a chain rather than a pair of unrelated failures: a step that fails differently says so with map_err first, and the conversion is visible at the place it happens.

Redacted<A>

impl<A> Redacted<A>

of

pub fn of(value: A) -> Redacted<A>

Wraps a value so that showing it shows nothing.

expose

pub fn expose(self) -> A

The value back.

The only way out, and it is meant to be visible. expose at a call site is a word a reviewer can search for; the leak this type exists to stop is the one nobody wrote on purpose.

Validated<A, E>

impl<A, E> Validated<A, E>

of

pub fn of(value: A) -> Validated<A, E>

A value that was fine.

error

pub fn error(e: E) -> Validated<A, E>

One thing wrong.

is_valid

pub fn is_valid(self) -> Bool

Whether nothing was wrong.

map

pub fn map<B>(self, f: (A) -> B) -> Validated<B, E>

The same value, transformed. Failures pass through untouched.

map2

pub fn map2<B, C>(self, other: Validated<B, E>, f: (A, B) -> C) -> Validated<C, E>

Two together, keeping both sides’ failures.

This is the whole type. f runs only when both succeeded; when either did not, the answer carries every error from both, left to right, and f is not called. Chained through a record’s fields it reports the whole form in one pass.

zip

pub fn zip<B>(self, other: Validated<B, E>) -> Validated<(A, B), E>

Both values together, keeping both sides’ failures.

map2 with the pair as its answer, and the one combinator that composes without an arity: zip(a, zip(b, c)) is three values in a nested tuple, and let (x, (y, z)) = t; takes it apart, however many there are. It is what a generated record decoder chains through, which is why there is no map6 and never will be.

map3

pub fn map3<B, C, D>(self, b: Validated<B, E>, c: Validated<C, E>, f: (A, B, C) -> D) -> Validated<D, E>

Three together, keeping every side’s failures.

map2 stopped at two and a CSV row has five columns. Building a record out of four validated fields meant nesting map2 and carrying a tuple through it, or hand-rolling the accumulation – which two of the four review programs did, separately.

Errors come back left to right, whichever sides failed, and f runs only when every side succeeded. Written out rather than built from map2 through a chain of pairs: that version works and reads p.key.key.value by the time it reaches five.

map4

pub fn map4<B, C, D, F>(self, b: Validated<B, E>, c: Validated<C, E>, d: Validated<D, E>, f: (A, B, C, D) -> F) -> Validated<F, E>

Four together, keeping every side’s failures.

map5

pub fn map5<B, C, D, F, G>(self, b: Validated<B, E>, c: Validated<C, E>, d: Validated<D, E>, e: Validated<F, E>, f: (A, B, C, D, F) -> G) -> Validated<G, E>

Five together, keeping every side’s failures.

Five is where this stops, because a CSV row is what asked for it and a sixth field is a record built out of two of these. List::traverse does the unbounded version and would have done the whole job – except that Validated is deliberately not an Applicative, for the reason the type gives above, so the one type in std built for accumulating errors cannot use it.

and_then

pub fn and_then<B>(self, f: (A) -> Validated<B, E>) -> Validated<B, E>

A second step that can fail, run only if the first did not.

Fails fast, and that is not a contradiction. map2 collects because its two sides are independent; this one’s second step is written in terms of the first’s value, so there is no second answer to collect when there is no first value to write it against. Parsing is the shape: integer reads the text and then parses it, and “not set” and “not a number” are never both true of one variable.

to_result

pub fn to_result(self) -> Result<A, List<E>>

The failures collapsed into one Result, for joining a raises chain.

List<E> rather than E, because the point of getting here was that there may be more than one and throwing the rest away at the boundary would undo the collecting.

unwrap_or

pub fn unwrap_or(self, fallback: A) -> A

The value, or fallback if anything was wrong.

List<A>

impl<A: Ord> List<A>

sort

pub fn sort(self) -> List<A>

The same elements, in order.

A merge sort, because a linked list is what it was invented for: it needs no indexing, no copying into an array and back, and it is stable — equal elements keep the order they were given, which is the property a caller notices the absence of when sorting by one field and expecting the previous sort to survive.

A: Ord rather than a comparison function, so that < on the elements and sort on the list cannot disagree. Sorting by something else is sort_by, which takes the comparison.

Its own recursion is the divide, so it goes about log2(n) deep — twenty frames for a million elements. The merge underneath it is iterative and so is the release of the intermediate lists, so neither adds a frame per element and the depth is the only depth there is.

split

pub fn split(self) -> Halves<A>

The first half and the second, each in the order it was given.

By counting to the middle, not by dealing alternately. Dealing is one pass and needs no length, and it is what this did first — but it is not stable, and the test said so. Two equal elements at positions 1 and 2 land in different halves with the later one on the left, and a merge that breaks its tie towards the left then puts them back the wrong way round.

The cost is a length and a reversal, both linear, against a sort that is already linearithmic.

min

pub fn min(self) -> Option<A>

The smallest element, or nothing if there are none.

Option rather than a fallback, because the smallest of nothing is not a number a caller can be handed – and a library that picked one would be picking for whoever forgot the list could be empty.

Ties go to the first, which matches sort being stable: min and head(sort(xs)) name the same element.

max

pub fn max(self) -> Option<A>

The largest element, or nothing if there are none.

Ties go to the first as well, for the same reason.

List<A>

impl<A> List<A>

is_empty

pub fn is_empty(self) -> Bool

Whether there is nothing in it.

Constant time, which length() == 0 is not.

length

pub fn length(self) -> Int

How many elements there are.

Walks the list. Nothing here caches it, so a loop that asks each time round is quadratic — take it once.

head

pub fn head(self) -> Option<A>

The first element, or None for an empty list.

push

pub fn push(self, item: A) -> List<A>

Prepends, which is the cheap end. Appending walks the whole list, so it is spelled concat and its cost is visible at the call site.

concat

pub fn concat(self, other: List<A>) -> List<A>

self followed by other.

Copies self and shares other, so the cost is the length of the left argument. Building a list by repeatedly concatenating onto the end is the quadratic way to do it; push and reverse once.

reverse

pub fn reverse(self) -> List<A>

The same elements, back to front.

reverse_onto

pub fn reverse_onto(self, acc: List<A>) -> List<A>

self reversed, in front of acc.

The accumulating half of reverse, and useful on its own: building a list front-to-back and reversing it at the end is the linear way to do what concat in a loop does quadratically. This is the “at the end”.

fold

pub fn fold<B, 'ef, 'er>(self, start: B, step: (B, A) -> B with 'ef raises 'er) -> B with 'ef raises 'er

Combines every element into one value, left to right.

step is called with what has been accumulated so far and the next element. Summing is fold(0, fn (a, b) => a + b).

any

pub fn any<'ef, 'er>(self, wanted: (A) -> Bool with 'ef raises 'er) -> Bool with 'ef raises 'er

Whether any element satisfies wanted.

Stops at the first one, which is what makes it worth having over a fold: a fold visits everything, and the whole point of asking whether any element matches is that the answer often arrives early.

all

pub fn all<'ef, 'er>(self, wanted: (A) -> Bool with 'ef raises 'er) -> Bool with 'ef raises 'er

Whether every element satisfies wanted. Stops at the first that does not.

True of the empty list, which is the convention that makes all compose: splitting a list in two and asking each half gives the same answer as asking the whole, and that fails at the empty case under any other rule.

find

pub fn find<'ef, 'er>(self, wanted: (A) -> Bool with 'ef raises 'er) -> Option<A> with 'ef raises 'er

The first element satisfying wanted, or nothing.

take

pub fn take(self, count: Int) -> List<A>

The first count elements, or all of them if there are fewer.

Below one is empty rather than an error: take is what a caller reaches for when the count came from somewhere else, and refusing zero would make every such caller check it first.

drop

pub fn drop(self, count: Int) -> List<A>

Everything after the first count elements.

nth

pub fn nth(self, index: Int) -> Option<A>

The element at index, counting from zero, or nothing.

last

pub fn last(self) -> Option<A>

The last element, or nothing.

filter

pub fn filter<'ef, 'er>(self, keep: (A) -> Bool with 'ef raises 'er) -> List<A> with 'ef raises 'er

The elements keep accepts, in the order they were in.

Inherent rather than a trait method, unlike map: Functor says how to change what is in a container, and dropping elements changes the container itself, which is why no lawful Functor has a filter. There is a class that does – Filterable – and one method is not a reason to introduce one.

filter then map is two walks; fold is one, and is what to reach for when that matters.

sort_by

pub fn sort_by(self, order: (A, A) -> Ordering) -> List<A>

The same elements, in the order order asks for.

What sort cannot do, and its doc comment already said so: sort takes A: Ord on purpose, so that < on the elements and sort on the list cannot disagree. Sorting a record by one of its fields is a different question, and this is where it is asked.

Stable, so equal elements keep the order they were given – which is what makes sorting twice, by one key and then another, do what everybody expects.

Sorted in an array, and the list rebuilt from it. The elements are copied into one array, sorted there by Array::sort_by’s bottom-up merge, and read back into a new list: two arrays and one new cell per element, however many rounds the merge takes. It recurses nowhere, so a long list costs no stack.

order must be consistent: if it says a is less than b it must not also say b is less than a. One that is not produces some order and no crash, which is the most any sort can promise about a broken comparison.

partition

pub fn partition<'ef, 'er>(self, wanted: (A) -> Bool with 'ef raises 'er) -> Parts<A> with 'ef raises 'er

The elements wanted accepts and the ones it does not, in one walk.

Two filters with opposite predicates is the alternative, and it walks twice and calls the question twice per element – which is wrong when the question is expensive and wrong in a different way when it is not pure. Both sides keep the order they were given.

List<A>

impl<A: Eq> List<A>

contains

pub fn contains(self, wanted: A) -> Bool

Whether wanted is in the list.

A: Eq rather than a predicate, because contains is the question somebody asks about a value they are holding – List::any is already there for the predicate.

List<A>

impl<A> List<A>

map

pub fn map<B, 'ef, 'er>(self, f: (A) -> B with 'ef raises 'er) -> List<B> with 'ef raises 'er

Each element through f, in order, answering a List.

List is the one type in std that implements both Functor and Iterator, and both of them declare a map. They are not the same operation: Functor::map answers a List<B>, and Iterator::map answers a lazy Mapped that computes nothing until something walks it. With only those two, xs.map(f) was a hard error naming both traits, and no answer a reader could guess – the most ordinary line in the language, made ambiguous by an abstraction most programs never mention.

So List has its own. A type’s own method outranks a trait’s, so this is what xs.map(f) means, and it means the eager one: a list in, a list out, which is what a reader arriving from Go, TypeScript or Rust’s Vec expects. The lazy pipeline is still there and is now asked for by name – Iterator::map(xs, f), or .iter() on something that has one – which is the right way round: the abstraction pays for itself, not the boring call.

The body is Functor’s, because two implementations of one operation is the shape half of this repository’s errata is about. f’s effect and failure rows pass straight through, so a map over a list of requests that can fail is still one call and still fails where it is written.

flat_map

pub fn flat_map<B, 'ef, 'er>(self, step: (A) -> List<B> with 'ef raises 'er) -> List<B> with 'ef raises 'er

Each element’s list, laid end to end.

map and then a flatten, written as one pass because the intermediate list of lists is the only thing the two-step version allocates that nobody wants.

zip

pub fn zip<B>(self, other: List<B>) -> List<Pair<A, B>>

Pairs, one from each, stopping at the shorter.

Stopping rather than padding, because there is nothing to pad a List<A> with: A is any type and this library has no notion of a default. A caller who wants the tail of the longer one still has it.

List<Int>

impl List<Int>

sum

pub fn sum(self) -> Int

Every element added together. Empty is zero.

Int only, and deliberately: a sum over anything addable wants a Monoid, and std::core has Functor and Applicative and not that one yet. Naming the concrete case is honest; a half-general one would have to be taken back.

Region

impl Region

open

pub fn open() -> Region

A new region with nothing deferred into it.

scoped is the way to reach one from ordinary code; this is what scoped calls. Opening one by hand means being responsible for the binding that ends it.

The region ends with the block the binding is in, not with the function and not at the next statement. So

{
  let region = Region::open();
  Region::defer(region, fn () => print("released"));
  work();
};

releases before the statement after the block, on every way out of it including a cancellation. Putting the let at the top of a function therefore holds everything until the function returns, which is the difference between a lease that ends with the call and one that ends with the caller – packages/postgres had exactly that bug, and a pool of n behaved like a pool of n uses.

defer

pub fn defer(self, finalizer: () ->()) ->()

Registers finalizer to run when this region ends.

Reverse order: the last deferred is the first run, so a finalizer may depend on one registered before it — a transaction rolled back before the connection it ran on is closed. Cleanup runs with cancellation held off, so a finalizer caused by a cancellation is not cut short by it.

root

pub fn root() -> Region

The region that ends when the program does, released by the entry point after main returns — on the failing path as well as the ordinary one.

It belongs to the program’s own fiber. A spawned fiber that calls this traps: a finalizer it deferred here would run at exit, on the main fiber, while the child might still be writing what it captured. A test block has a root region of its own, released when the test ends.

Scope

impl Scope

root

pub fn root() -> Scope

The outermost scope: the one that ends when the program does.

An entry point has to get a Scope from somewhere, and there is nothing above it to ask. Everything else should take one rather than reach for this — a library that roots its own scope has decided its caller’s lifetimes for it.

Like Region::root, it belongs to the program’s own fiber, and a spawned fiber that calls it traps. A child is handed scoped(work).

Fiber<A, ’er>

impl<A: Share, 'er> Fiber<A, 'er>

spawn

pub fn spawn(body: () -> A raises 'er) -> Fiber<A, 'er>

Runs body on a fiber of its own.

The fiber can be stopped whatever the thunk’s row says: Fiber::cancel stops it at its next loop, call or blocking operation, and its cleanup runs on the way out.

A must be Share for the reason every value crossing a fiber must be: it is computed on one and read on another, so a thing that cannot be held twice cannot be an answer.

join

pub fn join(self) -> A raises 'er

Waits for the fiber to finish, and answers what it answered.

A failure comes back out here, with its type. If the fiber raised, so does this — the whole point of a fiber that returns a value is that the caller decides what a failure means, rather than the runtime printing a line nobody reads. Joining twice is joining once, and gets the answer twice.

'r is the row the body raised, carried on the handle. That is what makes this pleasant rather than merely possible:

let count = Fiber::join(Fiber::spawn(fn () => tally(rows)));
//                                                  no `!`, it cannot fail

let row = Fiber::join(worker)! catch {
  // by name, because the row is here
  DbError::Disconnected(_why) => { columns: List::Nil, cells: List::Nil },
};

An erased handle would have needed a ! on every join — including on a fiber that provably cannot fail — and catch { _ => .. } as the only arm. The effect-survey design note §3.1 records what that cost and why the row is on the type instead.

wait

pub fn wait(self) ->() raises 'er

Waits for the fiber, and does not take its answer.

join is for the answer; this is for the ordering. They are not the same wait, and the difference shows up on a fiber that was canceled: a canceled fiber has no answer, so a join has nothing to hand back and unwinds the joiner along with it. This one just waits. Reach for it when what you needed was “not before that finishes”, which is most of the time a fiber is spawned for what it does rather than for what it computes.

Letting the binding go waits too — that is where structured concurrency comes from — so this is for the case where the waiting has to happen at a particular line rather than at the end of a scope.

A cancellation point. A fiber parked here is asked to stop like any other, and stops here, whatever either fiber’s row says. The row is the child’s: a waiter over a fallible child writes !, and one over a child that cannot fail writes nothing.

The child is not canceled by the waiter giving up. Letting the handle go still waits, which is what keeps it from outliving the binding.

finished

pub fn finished(self) -> Bool

Whether the fiber has finished, without waiting for it to.

For the loop that supervises rather than waits. join and wait both block, and letting the handle go blocks, so a program that spawns a server and then watches a stop flag has no way to ask the one question it needs: is the thing I spawned still running?

Without it, a listener whose port would not bind leaves its supervisor turning over a fiber that died before the first pass — no error, no exit, and a process that looks healthy to anything watching it.

let server = Fiber::spawn(fn () => Router::listen_quietly(router, port)!);
loop {
  clock.sleep(50);
  if Fiber::finished(server) {
    // It stopped on its own, which for a listener is never good news.
    Fiber::join(server)!;
    break
  };
  if Shared::get(stop) { break }
}

A true here means join has an answer ready and will not block. False is a fact about the instant it was asked, so this belongs in a loop that sleeps between looks rather than one that spins.

canceled

pub fn canceled(self) -> Bool

Whether the fiber was stopped, rather than allowed to finish.

finished says a supervised fiber is gone and cannot say why. The call that would say why is join, and on a canceled fiber a join unwinds its caller — at the entry point that ends the program with status 130, which is not something a supervisor can catch. So the loop that notices its listener has stopped has no way to tell a listener that returned from one somebody canceled, and those are the two cases it would act on differently.

let server = Fiber::spawn(fn () => Router::listen_quietly(router, port)!);
loop {
  clock.sleep(50);
  if Fiber::finished(server) {
    if Fiber::canceled(server) {
      // Somebody asked it to stop, so this is a shutdown and not a fault.
      break
    };
    // It ended on its own, which for a listener is never good news.
    Fiber::join(server)!;
    break
  };
  if Shared::get(stop) { break }
}

It reports that the fiber was stopped, not what it had computed. A true says a cancellation reached the fiber and the fiber gave up on it; it says nothing about how far the work got, and there is no way here to take a partial answer. For that, have the fiber publish to a Shared cell and read the cell.

join still ends the program on a canceled fiber. This does not change that, and asking first does not make the join safe — between the question and the join is another instant in which a cancellation can arrive. Reach for Fiber::wait, which waits without taking the answer.

A false is a fact about the instant it was asked, exactly as it is for finished, so this belongs in a loop that sleeps between looks. Asking does not consume the handle: a supervisor asks and keeps supervising.

A detached fiber answers false, whatever happened to it. Fiber::detach releases the shared state this reads, so after a detach there is nothing left to ask and the honest answer is the one a released handle always gives. Fiber::finished has the same shape for the same reason. Ask before detaching, or keep the handle.

outcome

pub fn outcome(self) -> Outcome<A> raises 'er

What the fiber ended as, waiting for it without unwinding this frame.

canceled says a fiber was stopped and cannot hand back what it computed; join hands back the answer and, on a stopped fiber, unwinds the joiner. At the entry point that ends the program with status 130, which no catch can name. So a caller that wants the answer and tolerates a stop had neither call, and this is that one: the stop comes back as a value.

let f = Fiber::spawn(fn () => tally(rows));
Fiber::cancel(f);
match Fiber::outcome(f) {
  Outcome::Answered(n) => n,
  Outcome::Stopped => 0,
}

The ceremony scales with the fiber’s own row, which is the rule join follows. On a Fiber<Int, {}> this is infallible and needs no !. On a fallible fiber it raises 'er, and a child that failed still comes out by name — only a child cancellation comes back as a value, so the caller who decides what a failure means keeps deciding it.

match Fiber::outcome(worker)! catch {
  DbError::Disconnected(_why) => Outcome::Stopped,
} {
  Outcome::Answered(rows) => rows,
  Outcome::Stopped => List::Nil,
}

It does not make join safe. join on a canceled fiber ends the program as it always has; this is an alternative to that call and not a repair of it. Nor does asking first make a later join safe: between the question and the join is another instant in which a cancellation can arrive.

A cancellation reaching this frame while it waits still stops it. The fiber asking is cancelable like any other, and that cancellation travels the ! rather than becoming an Outcome::Stopped — the value reports what the child ended as, and a frame cannot swallow a cancellation aimed at itself.

A fiber that was stopped after computing something answers Stopped, and the value is not handed back. A fiber that was canceled did not finish the work its answer stands for, so handing back whatever it had computed would be an answer wearing the type of one that was complete. For partial progress, have the fiber publish to a Shared cell and read the cell.

Asking consumes nothing a second question would need: like join, asking twice is asking once and gets the answer twice.

cancel

pub fn cancel(self) ->()

Asks the fiber to stop at its next cancellation point. Returns at once.

A cancellation point is every loop iteration, every call to a function that can reach one, every blocking std operation and every fiber or channel operation. The fiber’s scoped cleanup and Region::defer finalizers run on the way out, to completion; catch does not see the cancellation. A single foreign (C) call or file-system call already in progress finishes first.

Asking twice is asking once. Cleanup is not cut short by a second cancel. Fiber::abort is the request that does, and Fiber::cancel_within escalates to it after a deadline the caller chooses.

A fiber whose body is a nursery cancels its children with it, so a canceled fan-out stops rather than waiting on workers nobody told.

Fiber::detach is the way out that does not wait.

abort

pub fn abort(self) ->()

Stops the fiber at its next cancellation point even inside its cleanup, and its nurseries’ children with it.

cancel lets cleanup run to completion, and asking again changes nothing. So a finalizer that blocks for ever – a receive nobody will answer – holds its fiber, and every fiber waiting on it, for ever. This is the way to end that. It cancels the fiber too if nobody had. Asking twice is asking once.

What it costs is what it says: cleanup cut off part-way. A ROLLBACK may not be sent; a connection may be dropped rather than returned. Reach for it when waiting any longer is worse than that. A change function running under Shared::update still finishes, because it holds the cell’s lock; a blocking call inside one gives up at once instead. A single foreign (C) call or file-system call already in progress finishes first.

Fiber::cancel_within asks for this after a deadline you choose, which is usually what a shutdown wants.

cancel_within

pub fn cancel_within(self, millis: Int) ->()

Cancels the fiber now, and aborts it if it is still running millis milliseconds later.

A bound on how long cleanup may take, chosen by the caller. Khora has no default grace period: cleanup runs to completion unless something in the program says otherwise, and this is that something.

Fiber::cancel_within(server, 5000);
Fiber::wait(server);   // at most five seconds of cleanup, then abort

Returns at once. A fiber that finishes before the deadline is not aborted. The deadline is kept by a thread of its own until it expires.

detach

pub fn detach(self) ->()

Stops waiting for the fiber, and asks it to stop.

The valve, and there has to be one. Every other way out of a handle waits: join waits, and so does letting the binding go, which is where structured concurrency comes from. That is right, and it is also how a program hangs — one finalizer that never returns holds its nursery, which holds its parent, up to main. The scheduler design note promises both bounded cancellation latency and that a nursery exit leaves every child stopped or joined, and those two are in tension exactly here.

So: signal, and go. The fiber keeps running, its answer is dropped when it arrives, and a failure it reports afterwards is silent — the program said it was no longer listening. Without this, a timeout over a body with an uninterruptible tail is a lie: it would promise to return in half a second and then block on the tail.

It cancels as well as detaching, because a detached fiber nobody asked to stop is a leak with a nicer name.

Array<A>

impl<A> Array<A>

empty

pub fn empty() -> Array<A>

No elements at all.

new needs a value to fill with and a generic container has none to give until something has been put in it, so without this there is no way to write down an empty Array<A> — Array::new(0, fill) still demands the fill it will never write. That gap is what Vector<A> is built on: its storage starts here and is allocated for real by the first push, which is also the first moment there is a value of A to fill with.

new

pub fn new(length: Int, fill: A) -> Array<A>

length elements, every one of them fill.

Every one of them the same fill, which matters when it can be written. A record is a value and two cells holding one that nobody can change are indistinguishable from two copies – but give it a mut field and they are one object with two names:

type Agg = { mut count: Int };
let slots: Array<Agg> = Array::new(3, { count: 0 });
Array::get(slots, 0).count = Array::get(slots, 0).count + 1;
Array::get(slots, 1).count = Array::get(slots, 1).count + 1;
// every slot now reads 2, including the one nothing touched

An array of mutable accumulators is the natural way to group by a small key and it is the fast way – thirteen nanoseconds an event – so this is a shape people reach for. It reports counts multiplied by the number of buckets, silently, with nothing to say so. Use Array::from_fn below, which builds each cell separately.

The one place std disagrees with its own naming rule. new means “an empty one of something that grows”, and an array does neither – Array::empty sits above this for the empty case. Array::filled(length, fill) is what the rule asks for, and renaming a published std signature is a compatibility decision rather than a style one. The naming design note records it.

length

pub fn length(self) -> Int

How many elements it has. Fixed at construction; nothing grows an array.

get

pub fn get(self, index: Int) -> A

The element at index.

An index outside the array stops the program and says which index and what length. Same reasoning as trapping on integer overflow: a program that runs off its own array is wrong, and reading whatever is next in memory is the least useful possible response.

set

pub fn set(self, index: Int, value: A) ->()

Writes value at index, in place.

The one mutation in core, and the reason Array is not Share: two fibers writing one array is a data race, so an array crosses into a fiber only inside a type that says it is safe.

An index outside the array stops the program, as get does.

from_fn

pub fn from_fn(count: Int, make: (Int) -> A) -> Array<A>

count elements, each one built by calling make with its index.

The answer when the cells must not be the same object. Array::new fills every cell with one value, which is right for a number and wrong for anything with a mut field – an array of accumulators built that way is one accumulator with count names, and it reports every total multiplied by the number of buckets with nothing to say so.

make is called exactly count times, in order, so it may be the source of the difference rather than only of the shape:

let slots: Array<Agg> = Array::from_fn(16, fn _i => { count: 0 });
let squares: Array<Int> = Array::from_fn(10, fn i => i * i);

A count below one is Array::empty, and make is not called at all – which is the reason this is not Array::new(count, make(0)) with a loop after it.

sort_by

pub fn sort_by(self, order: (A, A) -> Ordering) ->()

Sorts the whole array in place, stably, by order.

is_utf8

pub fn is_utf8(self) -> Bool

Whether these bytes are well-formed UTF-8, and so whether String::from_bytes will accept them. Only an Array<U8> has an answer.

prefix

pub fn prefix(self, count: Int) -> Array<A>

The first count elements, copied.

What a caller does with a buffer it only partly filled: a socket read says how many bytes arrived, and the rest of the buffer is not part of the message.

with_data

pub fn with_data<B, 'ef, 'er>(self, body: (Ptr, Int) -> B with 'ef raises 'er) -> B with 'ef raises 'er

Lends the elements to body as a pointer and a count, for the duration of the call and no longer.

This is how a buffer reaches a foreign function. The count is the number of elements — the same number length gives — so a body that wants bytes multiplies by the element’s width itself.

The lifetime is the call, and that is the design rather than a limitation. A plain data(self) -> Ptr would be a dangling pointer waiting to happen: the array is released at its last use, and that use would be the data call. No wider scope is right either — the innermost one is wrong for a pointer taken in one branch of an if, and the function’s own is wrong for a loop, which would hold one buffer alive per iteration.

Only an array of numbers can be lent. An Array<A> of Khora objects holds reference-counted pointers, and handing those across is the mistake the whole boundary exists to prevent.

Array<U8>

impl Array<U8>

copy_into

pub fn copy_into(source: Array<U8>, from: Int, target: Array<U8>, at: Int, count: Int) ->()

Copies count bytes of source, starting at from, into target starting at at, in one move.

What it is for: a byte buffer copied a byte at a time. A loop of get and set checks two bounds and passes a cancellation point per byte, and a network protocol copies every byte it reads or writes at least once. This checks the two ranges once and moves the bytes with the C library’s memmove.

source and target may be the same array and the ranges may overlap: the bytes arrive as they were before the copy began, which is what moving the unread tail of a buffer to its front needs.

A range that does not fit, on either side, or a negative count, stops the program and names the index, as Array::get does. A count of zero copies nothing, anywhere a zero-length range fits – including at either array’s end.

let buffer: Array<U8> = Array::new(8, 0);
Array::copy_into(String::bytes("hello"), 0, buffer, 3, 5);
// buffer is 0 0 0 h e l l o

Int

impl Int

Arithmetic that does not trap, and the bits underneath it.

Ordinary +, - and * stop the program when they do not fit: a program that passes its tests and then wraps in production is the failure worth a branch to prevent. These are how you ask for the other behavior in the places that genuinely want it — a hash, a checksum, a pseudo-random number — by name, so that the trap stays the default without being in the way.

Methods rather than operators for now. ^, &, |, << and >> are five new tokens and >> has to be told apart from the end of two nested type arguments; none of that is hard and none of it is what a hash was waiting for.

wrapping_add

pub fn wrapping_add(self, other: Int) -> Int

The sum, wrapping at the type’s own range instead of trapping.

wrapping_sub

pub fn wrapping_sub(self, other: Int) -> Int

The difference, wrapping.

wrapping_mul

pub fn wrapping_mul(self, other: Int) -> Int

The product, wrapping.

xor

pub fn xor(self, other: Int) -> Int

Bit by bit: one wherever the two differ.

and

pub fn and(self, other: Int) -> Int

Bit by bit: one wherever both are one.

or

pub fn or(self, other: Int) -> Int

Bit by bit: one wherever either is one.

shl

pub fn shl(self, other: Int) -> Int

Towards the high bits, with zeros coming in at the bottom and whatever leaves the top gone.

shr

pub fn shr(self, other: Int) -> Int

Arithmetic, so a negative number stays negative. A logical shift is what Int cannot express and what an unsigned fixed-width type will.

String

impl String

slice

pub fn slice(self, from: Int, to: Int) -> String

The bytes from from up to to, clamped to what is there.

One allocation and one copy, which is why it is a compiler intrinsic rather than the six lines it reads like. Written in Khora it went through an Array<U8> and String::from_bytes, so every slice was two allocations, two copies and a walk of the bytes to re-check that they were UTF-8 — 2,915 nanoseconds for eighty bytes. String::split_once is two slices and the request parser is a dozen splits, so this one function was most of what a server spent its time on.

Stops the program if the ends fall inside a character, the same bargain String::byte makes about an index. The check is two byte reads rather than a walk: the input is already UTF-8, so the only way out of it is a cut through a multi-byte character, and that shows up as a continuation byte at one end or the other.

Indices outside the string are clamped rather than refused, because “the rest of it” is what every caller of slice(i, byte_length(s)) means.

is_char_boundary

pub fn is_char_boundary(self, at: Int) -> Bool

Whether at is where a character starts.

The question slice gives no way to ask, and it is the one that matters. slice counts bytes and stops the program when the cut lands inside a character:

khora: this slice cuts a character in half, so it is not a String

Which is right – the alternative is a String that is not UTF-8 – but until there was a way to ask, a program truncating text it did not write was one non-ASCII input from dying. std::json copes by reasoning that every byte it escapes is below 128; an application should not have to.

The end of the string is a boundary, and so is 0. Anything outside is not.

next_boundary

pub fn next_boundary(self, at: Int) -> Int

The first character boundary at or after at, or the string’s length.

For walking to a safe place to cut: String::slice(s, 0, s |> next_boundary(20)) takes about twenty bytes and never lands in the middle of anything.

At or after, so it does not advance. Given an offset that is already a boundary this answers that offset, which means

while at < stop {
  at = String::next_boundary(s, at);   // never ends
}

is an infinite loop on every string. To step a character at a time, pass at + 1 — or better, ask char_at and add Char::utf8_length, which says what it is doing.

The name is the trap: next reads as after. It is kept because the behavior is the one a cut wants — rounding an arbitrary offset outward to something safe — and because String::chars_between and String::chars are the two loops most callers actually want, and both are here already.

previous_boundary

pub fn previous_boundary(self, at: Int) -> Int

The last character boundary at or before at, or 0.

At or before, like its sibling: on a boundary it answers where it already is. See next_boundary for what that costs a caller who steps with it.

char_at

pub fn char_at(self, at: Int) -> Option<Char>

The character beginning at byte at, or None.

None when at is outside the string or is not a boundary – asking for the character in the middle of one has no answer, and inventing the replacement character would hide a caller that is stepping by the wrong amount.

Byte offsets, not character indices. char_at(s, 3) is the character three bytes in, and utf8_length is how far to step for the next one. A character index would mean walking the string from the start for every access, which is the quadratic loop this signature refuses to hide.

chars

pub fn chars(self) -> List<Char>

Every character, in order.

Allocates a list as long as the string has characters, which is what makes it the convenient answer rather than the fast one. A scan that cares walks with char_at and Char::utf8_length and allocates nothing.

char_length

pub fn char_length(self) -> Int

How many characters, which is not how many bytes.

Walks the string, so it is O(n). byte_length is the constant-time one and is what a buffer size wants.

chars_between

pub fn chars_between(self, start: Int, end: Int) -> Int

How many characters lie between two byte offsets.

What a caret needs. A tool reporting on text somebody else wrote places the caret by counting the characters before the span and draws it by counting the characters inside it, and char_length counts a whole string while byte_length counts the wrong unit. examples/khq wrote this for itself before it was here.

start is rounded down to a boundary and end up, so a range that splits a character counts it once rather than trapping. A caller who wants to know whether it split one has is_char_boundary.

find

pub fn find(self, needle: String, from: Int) -> Int

Where needle first occurs at or after from, counting in bytes, or -1 if it is nowhere.

The one place in this library that answers with a sentinel, and it earns it the way String::byte earns being able to stop the program: this is the bottom of the string library, index_of is one line above it and is what everything else calls. A search is the C library’s memmem, which says -1, and turning that into an Option is work the compiler cannot do inside an intrinsic — so it is done here, once, in the open.

from exists so that scanning a string does not mean copying it. Walking a header block by slicing off the front costs a copy of everything left over, once per header; searching from a cursor copies only the pieces that are kept.

An empty needle is found at from, which is what every other language says and what stops split_once on an empty separator from running forever.

index_of

pub fn index_of(self, needle: String) -> Option<Int>

Where needle first occurs, or nothing.

A compiler intrinsic underneath, and the reason is a measurement. Written as a loop over String::byte this took 3,180 nanoseconds to find a six-byte word in eighty bytes — a call and a bounds check per byte, at every candidate position. Bound to memmem and reached through two nested String::with_data calls it took 500, measured with each of their closures built on the heap. A body written in place is built in the caller’s frame, which removes those two allocations but not the two calls through a closure. Going straight to the runtime call is 40.

That matters because this is the hottest thing in the request parser: split_once is built on it, and parsing one request is about eight searches.

matches_at

pub fn matches_at(self, needle: String, at: Int) -> Bool

Whether needle sits at exactly at, without cutting a string out to ask.

The primitive find, starts_with and ends_with are all written over: comparing in place costs nothing, and slice would allocate once per position tried.

starts_with

pub fn starts_with(self, prefix: String) -> Bool

Whether the text begins with prefix. A prefix longer than the text is simply false rather than an index that would go past the end.

ends_with

pub fn ends_with(self, suffix: String) -> Bool

Whether the text ends with suffix.

contains

pub fn contains(self, needle: String) -> Bool

Whether needle occurs anywhere.

The empty string is in everything, which is what find already answers and is the convention every library that has thought about it settled on: it is the identity of concatenation, and it is at position 0 of anything.

is_empty

pub fn is_empty(self) -> Bool

Whether there are no bytes at all.

trim

pub fn trim(self) -> String

The string without leading or trailing whitespace.

Space, tab, carriage return and newline – the four a line of text picks up on its way through a file or a socket. Not Unicode’s full set of space characters: that list changes with the standard, and a std that silently trimmed a non-breaking space would be surprising in the other direction.

The ends move inwards over the original bytes and only what survives is copied: one allocation, and no second walk of the bytes. The copy is String::slice, which always makes one — trimming nothing still hands back a new string of the same length rather than the one it was given.

lower

pub fn lower(self) -> String

The string with A-Z written in lower case.

ASCII only, and deliberately. Unicode case folding is locale dependent – Turkish I lowercases to a dotless ı, and German ß upper-cases to two characters – so a correct lower needs a locale and a table, and neither belongs in core. What this is for is comparing a header name or a file extension, where the input is ASCII by specification.

Bytes outside A-Z are untouched, so text in any encoding passes through rather than being mangled.

upper

pub fn upper(self) -> String

The same text with a-z shifted to A-Z.

ASCII only, for the reason lower gives: a case mapping that is right for every script is a table that changes with the Unicode standard, and one that is right for some scripts silently is worse than one that is honest about being ASCII. Turkish dotless i is the example everybody learns this from.

escape_html

pub fn escape_html(self) -> String

The text made safe to put in an HTML page: &, <, >, " and ' replaced by &, <, >, " and '.

For text going into an element or a quoted attribute value, which is where a user’s input goes in a page. All five are escaped, not only < and &, so the same call is safe in title="..." and in title='...'. It is not enough for an unquoted attribute, a URL, a <script> or a <style>: each of those has rules of its own, and no single escaper satisfies them all.

Every other byte is kept as it is, so text in any language passes through unchanged. ' is HTML5’s (and XML’s); a reader of HTML 4 would show it literally.

Text with nothing to escape comes back as it is, with no copy. Otherwise the answer is built in one buffer, with the plain runs between the five characters copied whole.

let row = "<td>${String::escape_html(message)}</td>";

trim_start

pub fn trim_start(self) -> String

The text with leading whitespace removed.

trim_end

pub fn trim_end(self) -> String

The text with trailing whitespace removed.

split

pub fn split(self, separator: String) -> List<String>

Every piece between occurrences of separator, in order.

n separators give n + 1 pieces, always, which is the rule that makes splitting and joining inverses: "" splits to one empty piece, "a," splits to two of which the second is empty, and join(split(s, x), x) is s for every s. Dropping empty pieces is a filter the caller can write and cannot undo.

An empty separator would match everywhere and split nothing, so it gives back the whole string as one piece rather than looping.

join

pub fn join(pieces: List<String>, separator: String) -> String

The pieces laid end to end with separator between them.

The inverse of split for the same separator, which is the property that decides both. Written here rather than on List because it is about text and not about lists: a List<Int> has no join.

Linear in the output, and no intermediate strings. The pieces are measured first and copied into one buffer, which becomes the answer: two allocations and two copies of each byte (the buffer, then the string made from it) whatever the number of pieces. The walk is a loop rather than a stack, so tens of thousands of pieces are fine. A single piece is returned without copying.

replace

pub fn replace(self, from: String, to: String) -> String

Every occurrence of from replaced by to.

Left to right over the original, so what to puts in is never searched again: replacing "a" with "aa" doubles each a once rather than looping. An empty from matches everywhere and changes nothing, which is the only answer that terminates.

repeat

pub fn repeat(self, count: Int) -> String

The text count times over. Below one is empty.

By doubling, for the reason join above pairs. self + repeat(self, count - 1) was a stack frame per repetition and copied the whole of what it had built at every one of them, so asking for a line of ten thousand dashes did fifty million bytes of work and asking for a hundred thousand stopped the program. Squaring the chunk and taking the bits of count makes it a handful of copies of the answer’s own length.

is_space

pub fn is_space(byte: U8) -> Bool

Whether a byte is one of the four whitespace characters trim removes.

split_once

pub fn split_once(self, separator: String) -> Option<Split>

The text either side of the first separator, or nothing if it does not appear.

For a header line, a key=value pair, a URL and its query — anywhere the separator may legitimately appear again in the second half and splitting on every one of them would be wrong.

One split rather than a list of them, because a list wants an allocation per piece and every caller here wants the head and the rest. A record rather than a pair, because .head says which one it is and .0 does not.

pad_left

pub fn pad_left(self, width: Int, fill: String) -> String

self with fill in front of it until it is width bytes long.

For a column, which is the only reason anybody wants it. Every one of the three programs written against this library grew its own, and std::time has a third copy under the name padded – a function four people write is a function the library should have.

Bytes rather than characters, which matters the moment the text is not ASCII: a column of names in Greek will not line up, and lining up text by display width is a font question this type cannot answer. byte_length is the length everything else here counts in, so this counts in it too.

Already at or past width is returned unchanged: a truncating pad is a different function, and one that silently loses a digit from a total is not one this library is going to offer by accident. A fill that is not one byte long is refused the same way, since the loop could not land on width exactly.

pad_right

pub fn pad_right(self, width: Int, fill: String) -> String

self with fill after it until it is width bytes long.

The other side of pad_left, and the one a left-aligned label wants.

split_whitespace

pub fn split_whitespace(self) -> List<String>

The pieces between runs of whitespace, with no empty ones.

Not split(" "), and the difference is the whole point: split keeps every empty piece, which is right for a CSV – where two commas in a row mean a field that is there and blank – and wrong for anything column-aligned, where two spaces in a row mean the writer was lining something up. A log line split the first way has empty strings in it that no reader of the log put there.

Whitespace is what is_space says: space, tab, carriage return and newline.

Float

impl Float

to_string

pub fn to_string(self) -> String

The number, written out — 1.5, 0.1, inf.

The shortest form that reads back as the same number, which is what a reader means by “the number” and what print on a Float already gives. Thirty-two bytes is always enough for a double; the call says how many it needed, so a longer answer would be caught rather than truncated.

to_fixed

pub fn to_fixed(self, places: Int) -> String

The number to exactly places decimal places.

For a column and for a percentage, which is what everybody wanted it for: to_string gives the shortest form that reads back, so 0.5 and 0.125 are three characters apart and a table of them does not line up. Two of the review programs wrote the same percent(part, whole) helper and examples/risk_analyzer had a third copy, and the rounding was the half none of them wanted to write.

Not written in Khora, and the reason is the point of the whole numeric design. Multiplying by 10^places, rounding and dividing back does the rounding in binary floating point — so a percentage renders as 33.33 on one machine and 33.34 on another, which is the bug std::decimal exists to prevent, reintroduced by the formatter. The runtime rounds the decimal expansion of the double instead, the way C’s printf and Go’s strconv do, so this and its neighbors agree.

Still a Float, so it is still a rounding of an approximation. 0.1 + 0.2 to two places is 0.30, and it is 0.30 because the sum was near enough, not because it was right. Money is Decimal and Decimal::rounded is the exact version of this; the type that cannot have an Eq cannot have an exact one of these either.

places is clamped to nought through thirty: a double carries about seventeen significant digits, so past that the characters are an artifact of the binary value rather than information.

to_int

pub fn to_int(self) -> Int

The whole part, with nothing rounded.

Truncates toward zero — 2.9 is 2 and -2.9 is -2 — which is what every machine’s “convert to integer” does, and what C, Rust and Go all mean by it. Rounding is a different question with four defensible answers, so it gets a different function when somebody needs one.

A number too large for an Int clamps to the nearest end, and a NaN is zero. Undefined behavior is the alternative and is not one.

of_string

pub fn of_string(text: String) -> Option<Float>

The number text names, or None if it does not name one.

The shape is JSON’s, which is also what a person writes: an optional -, digits, an optional . and digits, an optional e or E with an optional sign and digits. No + in front, no underscores, no spaces, no hexadecimal, no inf and no nan — a parser that accepts more than the caller expected is how a configuration value ends up meaning something nobody wrote, and the two names are worse than that because they are values arithmetic cannot get back out of.

An Option for Int::of_string’s reason: the text came from outside, and somebody typing it wrong is a thing to answer rather than to stop the program over.

This existed already, privately, in std::json. Its comment said so: “This is Float::of_string in all but name and would be better as one in std::core. It is here because std::json is where the need is and a number parser in core is a decision worth making on its own evidence.” The evidence arrived as examples/khq, which has to read the numbers in a query and could not, and which found in the same hour that Float is the only primitive with no way in from text — Int and Decimal both have one.

Inexact by construction, and that is the type rather than this function: 0.1 is not a binary fraction and never will be. Decimal::of_string is the one to reach for when the digits have to survive.

Int

impl Int

of_string

pub fn of_string(text: String) -> Option<Int>

The number a string spells, or nothing.

An Option rather than a trap, because the text almost always came from outside — an environment variable, a header, a path segment, a form field — and “somebody typed it wrong” is a thing to answer with a 400 rather than to stop the program over.

Leading - and nothing else: no +, no underscores, no spaces, no hexadecimal. A parser that accepts more than the caller expected is how a configuration value ends up meaning something nobody wrote.

Refuses rather than overflows. * and + trap in this language, so a long enough run of digits would have stopped the program — which for text off a socket is a denial of service with extra steps. The running total is checked before it is grown instead.

The guard is exact rather than approximate: it asks for the room one more digit needs, so "9223372036854775808" — one past the largest Int, and the shape of a number somebody fat-fingered into a form — is refused rather than wrapped or fatal.

The total is counted downward, which is why the guard is written against smallest_int rather than a largest one. Every Int has a negative twin and not every one has a positive twin, so building 9223372036854775808 on the way to -9223372036854775808 would make the most negative number the one value this could not read.

to_float

pub fn to_float(self) -> Float

The same number as a Float.

Exact up to 2^53 and rounded beyond it, which is IEEE’s business rather than Khora’s.

to_string

pub fn to_string(self) -> String

The number, written out.

Needed by anything that puts a number in a message — a Content-Length, a status line, a log — so it is on every request path there is.

One buffer, counted first and filled from the end: two allocations, the buffer and the string, whatever the number of digits.

The most negative Int prints. Taking its magnitude with 0 - self overflows — that is the whole peculiarity of the number — so the digits are walked on whichever side of zero the number is already on, and only a remainder, which is in -9..=9, is ever negated.

Ptr

impl Ptr

null

pub fn null() -> Ptr

The null pointer, for the libraries that take one.

is_null

pub fn is_null(self) -> Bool

Whether this is null — which is how a great many C functions say they failed.

String

impl String

A string’s bytes.

Length and index are both in bytes, and say so in their names. A String is UTF-8, so a character is one to four of these, and a length that quietly meant one of the two would be wrong for half its callers and silent about which half. Anything that wants characters wants a decoder, which is a library on top of this rather than a different meaning for the same word.

byte_length

pub fn byte_length(self) -> Int

How many bytes the string occupies. Not how many characters it has.

byte

pub fn byte(self, index: Int) -> U8

The byte at index, counting from zero. Out of range stops the program, the same as an array.

from_bytes

pub fn from_bytes(bytes: Array<U8>) -> String

The same bytes, as a String.

Stops the program if they are not UTF-8. The same bargain get makes about an index: the check exists — Array::is_utf8 — and calling this without it is the mistake. An Option was the alternative and would put the decision in the wrong place, because what to do about bytes that are not text depends entirely on where they came from.

bytes

pub fn bytes(self) -> Array<U8>

A copy of the bytes.

A copy rather than a view, because a string is immutable and an array is not — a view would let one be edited through the other.

with_c_string

pub fn with_c_string<B, 'ef, 'er>(self, body: (Ptr) -> B with 'ef raises 'er) -> B with 'ef raises 'er

Lends the bytes to body as a const char *: the same bytes with a zero after them, which is how every function in the C library finds the end of a string.

A copy, necessarily — a Khora string knows its length instead of carrying a terminator, and there is nowhere to append one to a borrowed view. The copy lives exactly as long as the call.

A string with a zero inside it is not refused: C will see a shorter string than Khora has, which is what C strings are.

with_data

pub fn with_data<B, 'ef, 'er>(self, body: (Ptr, Int) -> B with 'ef raises 'er) -> B with 'ef raises 'er

See Array::with_data, which is the same thing and carries the argument for why the lifetime is a call rather than anything wider.

copy_into

pub fn copy_into(self, from: Int, target: Array<U8>, at: Int, count: Int) ->()

Copies count of the string’s bytes, starting at byte from, into target starting at at, in one move.

Array::copy_into for a string’s bytes, and the same rules: a range that does not fit, or a negative count, stops the program. What it saves over String::bytes and then a copy is the array in between, which is a whole copy of the string made to be thrown away.

from counts bytes, not characters, so a range can end inside a character. The bytes are copied as they are; whether target holds text afterwards is Array::is_utf8’s question.

U8

impl U8

An unsigned byte: 0 to 255.

The one every other type here is in service of — a wire format, a file and a string are all made of these.

The seven bitwise and wrapping operations mean the same thing in every one of these blocks, so they are argued for here and only named in the other six. +, - and * trap on overflow — The numbers design note §“Overflow traps, in every build” argues that at length — and wrapping_add, wrapping_sub and wrapping_mul are how a program asks for the other behavior by name. That is what a hash, a checksum and a wire format want, and naming it is what keeps a wrap that was intended apart from one that was a bug.

xor, and, or and shl are the bit operations under names rather than symbols, because Khora spends its operator budget on arithmetic and comparison. shr is the one that differs by type, so it keeps a line of its own in each block: logical where the type is unsigned, arithmetic where it is signed.

Every conversion goes through Int — U8::of and U8::to_int rather than a method for each of the forty-two ordered pairs. U8 to U32 is two steps, which is more to type and never wrong. And every narrowing is explicit, because a number that silently becomes a different number is found in production rather than in a test.

of

pub fn of(value: Int) -> U8

The same number as a U8, or a stopped program if it does not fit.

wrapping

pub fn wrapping(value: Int) -> U8

The low bits of value, whatever they are. The way to ask for truncation by name, for the wire formats that mean it.

to_int

pub fn to_int(self) -> Int

Every U8 is an Int, so this cannot fail and costs one instruction.

wrapping_add

pub fn wrapping_add(self, other: U8) -> U8

The sum, wrapping at the type’s own range instead of trapping.

wrapping_sub

pub fn wrapping_sub(self, other: U8) -> U8

The difference, wrapping.

wrapping_mul

pub fn wrapping_mul(self, other: U8) -> U8

The product, wrapping.

xor

pub fn xor(self, other: U8) -> U8

Bit by bit: one wherever the two differ.

and

pub fn and(self, other: U8) -> U8

Bit by bit: one wherever both are one.

or

pub fn or(self, other: U8) -> U8

Bit by bit: one wherever either is one.

shl

pub fn shl(self, other: U8) -> U8

Towards the high bits, with zeros coming in at the bottom and whatever leaves the top gone.

shr

pub fn shr(self, other: U8) -> U8

Logical, because the type is unsigned: the vacated bits are zeros and a large value stays large.

U16

impl U16

An unsigned 16-bit integer: 0 to 65,535.

of

pub fn of(value: Int) -> U16

The same number as a U16, or a stopped program if it does not fit.

wrapping

pub fn wrapping(value: Int) -> U16

The low bits of value, whatever they are.

to_int

pub fn to_int(self) -> Int

Every U16 is an Int, so this cannot fail.

wrapping_add

pub fn wrapping_add(self, other: U16) -> U16

The sum, wrapping.

wrapping_sub

pub fn wrapping_sub(self, other: U16) -> U16

The difference, wrapping.

wrapping_mul

pub fn wrapping_mul(self, other: U16) -> U16

The product, wrapping.

xor

pub fn xor(self, other: U16) -> U16

Bit by bit: one wherever the two differ.

and

pub fn and(self, other: U16) -> U16

Bit by bit: one wherever both are one.

or

pub fn or(self, other: U16) -> U16

Bit by bit: one wherever either is one.

shl

pub fn shl(self, other: U16) -> U16

Towards the high bits, with zeros coming in at the bottom.

shr

pub fn shr(self, other: U16) -> U16

Logical, because the type is unsigned.

U32

impl U32

An unsigned 32-bit integer: 0 to 4,294,967,295.

of

pub fn of(value: Int) -> U32

The same number as a U32, or a stopped program if it does not fit.

wrapping

pub fn wrapping(value: Int) -> U32

The low bits of value, whatever they are.

to_int

pub fn to_int(self) -> Int

Every U32 is an Int, so this cannot fail.

wrapping_add

pub fn wrapping_add(self, other: U32) -> U32

The sum, wrapping.

wrapping_sub

pub fn wrapping_sub(self, other: U32) -> U32

The difference, wrapping.

wrapping_mul

pub fn wrapping_mul(self, other: U32) -> U32

The product, wrapping.

xor

pub fn xor(self, other: U32) -> U32

Bit by bit: one wherever the two differ.

and

pub fn and(self, other: U32) -> U32

Bit by bit: one wherever both are one.

or

pub fn or(self, other: U32) -> U32

Bit by bit: one wherever either is one.

shl

pub fn shl(self, other: U32) -> U32

Towards the high bits, with zeros coming in at the bottom.

shr

pub fn shr(self, other: U32) -> U32

Logical, because the type is unsigned.

U64

impl U64

An unsigned 64-bit integer: 0 to 18,446,744,073,709,551,615.

The only type here that holds numbers Int cannot, which is why it is the only one whose to_int can stop the program.

of

pub fn of(value: Int) -> U64

The same number as a U64, or a stopped program if it does not fit.

wrapping

pub fn wrapping(value: Int) -> U64

The low bits of value, whatever they are.

to_int

pub fn to_int(self) -> Int

Int cannot hold every U64, so this stops the program above Int’s maximum. U64::wrapping_to_int is how to reinterpret the bits instead.

wrapping_to_int

pub fn wrapping_to_int(self) -> Int

The same bits read as a signed Int, so a U64 above Int’s maximum comes back negative rather than stopping.

wrapping_add

pub fn wrapping_add(self, other: U64) -> U64

The sum, wrapping.

wrapping_sub

pub fn wrapping_sub(self, other: U64) -> U64

The difference, wrapping.

wrapping_mul

pub fn wrapping_mul(self, other: U64) -> U64

The product, wrapping.

xor

pub fn xor(self, other: U64) -> U64

Bit by bit: one wherever the two differ.

and

pub fn and(self, other: U64) -> U64

Bit by bit: one wherever both are one.

or

pub fn or(self, other: U64) -> U64

Bit by bit: one wherever either is one.

shl

pub fn shl(self, other: U64) -> U64

Towards the high bits, with zeros coming in at the bottom.

shr

pub fn shr(self, other: U64) -> U64

Logical, because the type is unsigned.

I8

impl I8

A signed 8-bit integer: -128 to 127.

of

pub fn of(value: Int) -> I8

The same number as a I8, or a stopped program if it does not fit.

wrapping

pub fn wrapping(value: Int) -> I8

The low bits of value, whatever they are.

to_int

pub fn to_int(self) -> Int

Every I8 is an Int, so this cannot fail.

wrapping_add

pub fn wrapping_add(self, other: I8) -> I8

The sum, wrapping.

wrapping_sub

pub fn wrapping_sub(self, other: I8) -> I8

The difference, wrapping.

wrapping_mul

pub fn wrapping_mul(self, other: I8) -> I8

The product, wrapping.

xor

pub fn xor(self, other: I8) -> I8

Bit by bit: one wherever the two differ.

and

pub fn and(self, other: I8) -> I8

Bit by bit: one wherever both are one.

or

pub fn or(self, other: I8) -> I8

Bit by bit: one wherever either is one.

shl

pub fn shl(self, other: I8) -> I8

Towards the high bits, with zeros coming in at the bottom.

shr

pub fn shr(self, other: I8) -> I8

Arithmetic, because the type is signed.

I16

impl I16

A signed 16-bit integer: -32,768 to 32,767.

of

pub fn of(value: Int) -> I16

The same number as a I16, or a stopped program if it does not fit.

wrapping

pub fn wrapping(value: Int) -> I16

The low bits of value, whatever they are.

to_int

pub fn to_int(self) -> Int

Every I16 is an Int, so this cannot fail.

wrapping_add

pub fn wrapping_add(self, other: I16) -> I16

The sum, wrapping.

wrapping_sub

pub fn wrapping_sub(self, other: I16) -> I16

The difference, wrapping.

wrapping_mul

pub fn wrapping_mul(self, other: I16) -> I16

The product, wrapping.

xor

pub fn xor(self, other: I16) -> I16

Bit by bit: one wherever the two differ.

and

pub fn and(self, other: I16) -> I16

Bit by bit: one wherever both are one.

or

pub fn or(self, other: I16) -> I16

Bit by bit: one wherever either is one.

shl

pub fn shl(self, other: I16) -> I16

Towards the high bits, with zeros coming in at the bottom.

shr

pub fn shr(self, other: I16) -> I16

Arithmetic, because the type is signed.

I32

impl I32

A signed 32-bit integer: -2,147,483,648 to 2,147,483,647.

A C int, which is why it is the one a foreign function usually wants.

of

pub fn of(value: Int) -> I32

The same number as a I32, or a stopped program if it does not fit.

wrapping

pub fn wrapping(value: Int) -> I32

The low bits of value, whatever they are.

to_int

pub fn to_int(self) -> Int

Every I32 is an Int, so this cannot fail.

wrapping_add

pub fn wrapping_add(self, other: I32) -> I32

The sum, wrapping.

wrapping_sub

pub fn wrapping_sub(self, other: I32) -> I32

The difference, wrapping.

wrapping_mul

pub fn wrapping_mul(self, other: I32) -> I32

The product, wrapping.

xor

pub fn xor(self, other: I32) -> I32

Bit by bit: one wherever the two differ.

and

pub fn and(self, other: I32) -> I32

Bit by bit: one wherever both are one.

or

pub fn or(self, other: I32) -> I32

Bit by bit: one wherever either is one.

shl

pub fn shl(self, other: I32) -> I32

Towards the high bits, with zeros coming in at the bottom.

shr

pub fn shr(self, other: I32) -> I32

Arithmetic, because the type is signed.

Dict<K, V>

impl<K, V> Dict<K, V>

new

pub fn new() -> Dict<K, V>

An empty dictionary.

size

pub fn size(self) -> Int

How many entries. Kept in the node rather than counted, because balancing asks for it at every step.

is_empty

pub fn is_empty(self) -> Bool

Whether there are no entries.

rotate_left

pub fn rotate_left(key: K, value: V, left: Dict<K, V>, right: Dict<K, V>) -> Dict<K, V>

The right side is heavy. Which rotation depends on its own shape: a single one moves its left subtree across, which only helps if that subtree is the lighter half.

rotate_right

pub fn rotate_right(key: K, value: V, left: Dict<K, V>, right: Dict<K, V>) -> Dict<K, V>

The mirror of it.

entries

pub fn entries(self) -> List<Pair<K, V>>

Every entry, smallest key first.

keys

pub fn keys(self) -> List<K>

Every key, in order.

Here because Map has keys and values and this had only entries, which left a reader who found one and not the other to work out whether the difference meant something. It did not.

values

pub fn values(self) -> List<V>

Every value, in key order.

Dict<K, V>

impl<K: Ord, V> Dict<K, V>

get

pub fn get(self, key: K) -> Option<V>

The value under key, if there is one.

contains

pub fn contains(self, key: K) -> Bool

Whether key has an entry.

insert

pub fn insert(self, key: K, value: V) -> Dict<K, V>

The map with key set to value, leaving this one as it was.

update

pub fn update(self, key: K, step: (Option<V>) -> V) -> Dict<K, V>

The map with key set to whatever step makes of what was there.

Counting things into a map is the most common thing a log analyzer does, and without this it is insert(t, k, unwrap_or(get(t, k), 0) + 1) every time – which names the map three times, the key twice, and walks the tree twice to answer one question.

step is given None when the key is new, so the initial value and the update are the same expression:

counts = Dict::update(counts, word, fn seen => Option::unwrap_or(seen, 0) + 1);

One walk, and step is called exactly once. There is no version that removes the entry: step returns a V rather than an Option<V> because “update or delete” is two operations wearing one name, and remove is right there.

remove

pub fn remove(self, key: K) -> Dict<K, V>

The map without key. Removing what is not there is the map unchanged.

glue

pub fn glue(left: Dict<K, V>, right: Dict<K, V>) -> Dict<K, V>

Joins two sides whose node has gone.

The successor moves up: every key on the left is smaller than every key on the right, so the smallest of the right is the one that can sit between them.

from_list

pub fn from_list(entries: List<Pair<K, V>>) -> Dict<K, V>

Builds a map from entries, later ones winning.

A loop rather than a fold, because the recursion would be as deep as the list is long — the cliff String::slice fell off.

Map<K, V>

impl<K: Hash, V> Map<K, V>

new

pub fn new() -> Map<K, V>

An empty map, which allocates nothing but itself.

The buckets wait for the first insert, so a map that is never written to costs nothing beyond the map itself. A great many are never written to: a request with no query string still builds a query map, and a route with no :name still builds one for its parameters.

len

pub fn len(self) -> Int

How many entries there are. Counted as it goes, not walked.

get

pub fn get(self, key: K) -> Option<V>

The value under key, if there is one.

holds

pub fn holds(self, key: K) -> Bool

Whether key has an entry.

For when the value is not wanted; get is one lookup either way, so holds followed by get is two and a match on get is one.

insert

pub fn insert(self, key: K, value: V) ->()

Adds key, replacing whatever was there. The count only moves when the key is new, which is what makes it the number of entries rather than the number of insertions.

update

pub fn update(self, key: K, step: (Option<V>) -> V) ->()

Puts step of whatever is under key back under it.

One hash instead of two, which is the whole point. Counting things is the commonest thing a mutable map is for, and written with what was here it is

let seen = match Map::get(counts, word) {
  Option::Some(n) => n + 1,
  Option::None => 1,
};
Map::insert(counts, word, seen);

— two hashes of the same key, two walks of the same bucket and an Option built in between, on the hot line of every histogram, word count and group-by anybody writes. This is

Map::update(counts, word, fn seen => match seen {
  Option::Some(n) => n + 1,
  Option::None => 1,
});

step is handed None when the key is new, so it is also how a default is written without saying the key twice. The mirror of Dict::update, which answers a new dictionary where this changes the one it is given.

remove

pub fn remove(self, key: K) ->()

Takes key out, in place. Removing what is not there does nothing.

The table never shrinks. A map emptied of a million entries keeps its million buckets, which nothing here has needed to be otherwise.

entries

pub fn entries(self) -> List<Pair<K, V>>

Every entry, as a list.

In no particular order. A hash table forgets the order its keys arrived in, and the order this does report is not even stable across inserts: growing rehashes everything into twice as many buckets and moves roughly half of it. A caller that wants an order sorts what comes back, or uses Dict, whose entries is in key order because the tree already is.

Without this, iterating a map means reaching into buckets and matching on Chain, which is what std::json had to do to write an object back out — a module coupled to the table’s representation for want of six lines here.

Two loops rather than two recursions. A table with a million entries has a million buckets to visit, and a stack frame each is the mistake String::slice made per byte. The inner walk is a loop too, for a less obvious reason: a chain is only short while the Hash is good, and a bad one puts every entry in a single bucket. The price of that should be a slow walk, not a smashed stack.

keys

pub fn keys(self) -> List<K>

The keys, in the reverse of the order entries reports them — which is to say in no particular order either.

Built by walking entries rather than the buckets a second time. The pairs it allocates and throws away are the price of having one place where the traversal is written; a map big enough for that to matter wants entries itself, which allocates the pairs the caller was going to keep.

Not List::map, which is a loop too but reverses at the end to hand back the input’s order. Nothing here promises an order, so that reversal would be a second walk of the list for nothing — and skipping it is exactly why this reports the reverse of what entries did.

keys and values walk the same list the same way, so the two line up position for position. That is the only thing worth promising about the order of either.

values

pub fn values(self) -> List<V>

The values, one per entry — duplicates included, because two keys may well hold the same value and dropping one would make values disagree with len.

Vector<A>

impl<A> Vector<A>

new

pub fn new() -> Vector<A>

Empty, holding no storage at all.

Eight is what the first push will ask for, matching Map::new’s eight buckets — enough that a small vector never reallocates, small enough that a vector which is made and never pushed to, as a field on a record or an accumulator on the branch that turned out to have nothing to accumulate, has cost two objects and no cells: itself, and the empty array’s header.

with_capacity

pub fn with_capacity(capacity: Int) -> Vector<A>

Room for capacity elements, from the first push onwards.

Nothing is allocated here — there is no value of A to fill an array with yet — so this records the size and the first push allocates it. The saving is real either way: what with_capacity buys is that filling it reallocates once instead of a dozen times, and that is a property of the first allocation’s size, not of when it happens.

A capacity that is not positive is no opinion at all, and gets the same eight new would have. Array::new would trap on a negative length, and rightly, but a capacity is a hint about a size that is often computed — expected - already_have — and being wrong about a hint is not the same kind of mistake as indexing off the end of an array.

length

pub fn length(self) -> Int

How many elements are in it.

is_empty

pub fn is_empty(self) -> Bool

Whether there is nothing in it.

capacity

pub fn capacity(self) -> Int

How many elements fit before the next reallocation — allocated cells, not promised ones, so this is nought until the first push.

Worth exposing because growth is the only thing about a vector that is not visible from the outside, and a test that means to exercise it has to be able to see it.

push

pub fn push(self, item: A) ->()

Adds an element at the end.

The element goes to grow as well when the array is full, because it is the fill: the only value of A anyone here has.

grow

pub fn grow(self, seed: A) ->()

Twice the room, or wanted if there was none, with seed in every cell.

Doubling, not a fixed increment, which is the whole reason push is amortized constant: growing by a constant makes filling a vector quadratic in its length, and that is the bug that turns a working program into a slow one only once the input gets big. Two rather than the 1.5 some allocators are tuned for, because reusing the freed blocks needs an allocator that coalesces them and this runtime hands them straight to malloc; the smaller factor would buy nothing and copy more often.

The cells past len hold seed — a copy of the element being pushed, because there is nothing else of type A to put there. They are overwritten by the pushes that follow, and until then a boxed A is held by that many references rather than that many objects.

The one visible consequence: a vector that grew and was then popped back down keeps that element alive, because the cells above the length were never written over. It is a single object however long the vector is — all of those cells hold the same one — and it goes at the next growth or with the array. Blanking them would need a value of A to blank them with, which is the same wall this whole type is built around.

pop

pub fn pop(self) -> Option<A>

Removes the last element and hands it back.

Option::None from an empty vector rather than a trap: draining one is match Vector::pop(v) until it answers None, which makes empty a loop condition rather than a mistake. That is the opposite call from Array::get, and deliberately — an index is a claim about a length the caller believes it knows, while popping is a question.

The cell that is left over has to hold something of type A, so it is given the first element. That is not tidiness: without it the array would go on holding the element that was just removed, and a vector popped down and then kept would be indistinguishable from a leak. Popping the last element has no first element to use and needs none — the array goes, all at once, and wanted keeps its size for the next fill.

get

pub fn get(self, index: Int) -> Option<A>

The element at index, or Option::None if there is none there.

Soft where Array::get traps, and not only for symmetry with pop: an array’s length is fixed and known where it was allocated, while a vector’s is whatever the pushes left it at, so a caller reading one is far more often asking than asserting.

Bounded by len and never by Array::length. The cells in between are not empty — they hold the fill, or an element a pop left behind — and handing one of those back would be a phantom element rather than an error.

at

pub fn at(self, index: Int) -> A

The element at index, or the program stops.

The one that does not allocate. Vector::get answers an Option<A>, which is right when the index is a question — and it is wrong when it is not. Walking a vector by index is the ordinary way to read one, and every read of that walk allocated a Some for the caller to match away one line later. The bound is checked either way; what this removes is the object built to carry an answer that was never in doubt.

So the two are a pair, and which one to reach for is a question about the index rather than about speed: get when the index came from outside and might not be there, at when the loop that produced it is right above. Array::get has been the second of those all along, and a vector had only the first.

Out of range stops the program and says which index and how long the vector was — bounded by len and not by the array underneath it, so the cells a pop left behind are past the end here as they are everywhere else.

sort_by

pub fn sort_by(self, order: (A, A) -> Ordering) ->()

Sorts the vector in place, stably, by order.

The elements, and not the array underneath them: a vector’s array is as long as the last push made it and the cells past len hold whatever a pop left behind, so sorting the array would sort those into the middle of the answer.

set

pub fn set(self, index: Int, value: A) -> Bool

Replaces the element at index. Answers whether there was one to replace.

A write past the end is not a question with an answer — there is no element there — so this reports rather than inventing one or growing to fit. Growing would have to fill the gap between, and the gap is exactly what there is no value of A for; push is how a vector gets longer.

clear

pub fn clear(self) ->()

Empties it.

The array goes rather than being kept and blanked, because there is nothing to blank a cell with: keeping it would keep every element in it alive until something was pushed over that cell, and a cleared vector holding its contents is the bug this method is usually called to avoid. wanted remembers how big it was, so the next fill reallocates once and arrives back where it started.

to_list

pub fn to_list(self) -> List<A>

The elements, first to last.

Backwards through the array, prepending, so the list comes out in order without a reversing pass — the same trick Map::entries uses, and a loop for the same reason: one frame per element is what String::slice overflowed the stack with.

from_list

pub fn from_list(items: List<A>) -> Vector<A>

A vector of the list’s elements, in the same order.

Pushed one at a time into an empty vector rather than sized up front with List::length, on the argument that pre-sizing costs a second full walk of the list to save a handful of reallocations that double — and a walk of the whole input is the more expensive half of that trade.

SharedFn<A, B, ’er>

impl<A, B, 'er> SharedFn<A, B, 'er>

of

pub fn of(f: (A) -> B raises 'er) -> SharedFn<A, B, 'er>

Certifies a closure written here.

The argument has to be a closure literal or a named function — anything else was written elsewhere and took its captures with it, which is the one thing this cannot check and so the one thing it refuses.

call

pub fn call(self, argument: A) -> B raises 'er

Calls it. A plain closure call; the wrapper costs nothing at runtime.

Channel<A>

impl<A: Share> Channel<A>

bounded

pub fn bounded(capacity: Int) -> Channel<A>

A channel that will hold at most capacity values.

Below one is one — see the type’s note on rendezvous.

A full one makes the sender wait, which is backpressure and is the right default: a queue nobody is draining is a producer that should slow down. dropping and sliding are the two ways to say the opposite.

dropping

pub fn dropping(capacity: Int) -> Channel<A>

Like bounded, but a send into a full one fails instead of waiting.

For a queue whose producer must not stall: the request path writing an audit event, a handler emitting a metric. send answers false, so the loss is a value the caller can count and report — which is the whole difference from sliding, where it is not.

The choice is the channel’s rather than the send’s, because a queue is lossy or it is not, and two senders disagreeing about which is not a state a queue can be in.

sliding

pub fn sliding(capacity: Int) -> Channel<A>

Like bounded, but a send into a full one evicts the oldest value.

For a feed where the newest value is the only one worth having: a gauge, a progress indicator, the last-known position of something. send answers true — nothing was refused — so the loss is invisible at the call site, and that is deliberate: nobody was going to act on it. Reach for dropping where somebody would.

send

pub fn send(self, value: A) -> Bool

Puts a value in, waiting while the channel is full.

False when the channel is closed, in which case the value is released rather than kept: a send with nowhere to put its value must not be the quietest possible leak.

A cancellation point. Waiting for room is one of the places a fiber can sit indefinitely, so a cancellation reaches it here: the fiber stops and the value is released, the same as on a closed channel. It needs no !, because it cannot fail.

receive

pub fn receive(self) -> Option<A>

Takes a value out, waiting while the channel is empty.

None only when the channel is closed and drained.

Waiting receivers are served in the order they started waiting, on the scheduler backend: a value sent while some are waiting goes to the one that has waited longest, and a receive or poll from a fiber that has not waited cannot take it first. So fibers queued for a connection pool’s connections get them in turn.

A cancellation point, for the reason send gives. A receive that is canceled is always canceled empty-handed: the runtime looks at the flag only once it has established the queue is empty, so a send arriving at the same moment still wins and the value is never dropped on the floor.

poll

pub fn poll(self) -> Option<A>

Takes a value if one is already there, and never waits.

None means “not right now”, not “not ever”. A closed and drained channel and a live empty one both answer None, and telling them apart is what receive is for. This exists for a loop with something else to do between looks; a loop that only polls is a loop that spins, and the answer to that is receive.

close

pub fn close(self) ->()

Says nothing more will be sent, and releases everybody waiting.

depth

pub fn depth(self) -> Int

How many values are waiting to be taken.

Stale the moment it is given, which is true of every such count. For a pool reporting its depth and for tests; nothing should branch on it.

Handoff<A>

impl<A> Handoff<A>

bounded

pub fn bounded(capacity: Int) -> Handoff<A>

A hand-off that holds at most capacity values. Below one is one.

send

pub fn send(self, value: A) -> Bool

Gives value away, waiting while the hand-off is full.

False when it is closed, or this fiber is canceled while it waits; the value is then released. Stops the program when something else holds a writable part of value – see the type.

receive

pub fn receive(self) -> Option<A>

Takes a value, waiting while it is empty. None once it is closed and drained, or this fiber is canceled while it waits.

close

pub fn close(self) ->()

Says nothing more will be sent, and releases everybody waiting.

Shared<A>

impl<A: Share> Shared<A>

of

pub fn of(value: A) -> Shared<A>

A cell holding value.

get

pub fn get(self) -> A

What is in it now, as a value of the caller’s own.

Takes the lock for the read, so it never observes a half-written value. The answer is a retain rather than a deep copy, and it is a snapshot: a concurrent set or update may land the moment after it returns.

set

pub fn set(self, value: A) ->()

Replaces what is in it.

Takes the lock, so it does not interleave with an update in progress. It does not read first, so set(get(cell) + 1) is two steps and two fibers running it can lose one of the increments — that is what update is for.

update

pub fn update(self, change: (A) -> A) -> A

Reads, transforms and writes as one step, and gives back the new value.

change runs once, under the lock. It cannot fail, so nothing leaves the critical section with the lock still held; work that can fail belongs outside — compute it, then set the answer.

A cancellation does not stop change part-way. A blocking call inside it — a receive, a sleep, a socket call — gives up on a cancel and hands back its “gave up” answer (None, false), change finishes with that answer and the cell takes the result, and the fiber stops right after the update. A Fiber::join, wait or outcome inside change has no such answer: on a cancel it leaves the cell as it was, and the fiber stops there. In cleanup — a Region::defer finalizer or scoped cleanup — those three wait for the child instead, holding the lock, because only abort stops cleanup.

Updating the same cell from inside change is a deadlock, and stops the program with a message rather than waiting for itself.

modify

pub fn modify<B>(self, change: (A) -> Changed<A, B>) -> B

The same, for a change that has something to say beyond the new state.

update can only answer with what it left in the cell, which is not always what the caller needs to know. A handler inserting a record under a generated key has to get that key back, and searching the new state for it afterwards is a guess — a wrong one the moment two fibers insert records that look alike:

let code = Shared::modify(links, fn table => {
  let drawn = fresh_code(table);
  { state: Dict::insert(table, drawn, made), result: drawn }
});

Both halves are installed and handed back under the one lock, so the answer belongs to the state it was produced with.

Fibers

impl Fibers

open

pub fn open() -> Fibers

A nursery with no limit on how many children it holds at once.

bounded is usually the one to want: a server adopting a fiber per connection meets an unbounded nursery’s ceiling by exhausting memory.

bounded

pub fn bounded(limit: Int) -> Fibers

A nursery that will hold at most limit running children.

Adopting past the limit waits for the oldest to finish. That is the whole of it, and it is what turns a capacity ceiling into a queue: a server adopting a fiber per connection meets an unbounded nursery’s ceiling by exhausting memory, and meets a bounded one’s by accepting more slowly, which the listening socket’s backlog is already built to absorb.

Unbounded is right for a nursery over a known handful of tasks — the shape nursery(..) is usually used for — and wrong for one fed by the outside world.

adopt

pub fn adopt<'er>(self, fiber: Fiber<(), 'er>) ->()

Puts a running fiber under this nursery.

The nursery takes the handle, so nothing else can outlive it with one. Adopting past a bounded limit waits for the oldest child to finish, which is what turns a ceiling into a queue. A cancel that arrives during that wait is passed to the child being waited on, and the adopting fiber stops once it has finished.

Fiber<(), 'er>: adopting gives up the answer and keeps the failure. A nursery holds its children as bare handles and waits for them; it could not hand back what they computed even if it kept it, so the answer is fixed at (). The row stays so a child’s failure can still be counted and reported as ChildFailed. Canceling the nursery’s fiber cancels every child, whatever its row.

wait

pub fn wait(self) -> Int

Waits for every child, oldest first, and empties the nursery, and answers how many of them ended with an error.

A count, because a count is what a nursery can honestly say. Every child’s error has a type of its own and a nursery holds them as bare handles — that is written down at adopt and is not going to change — so there is no one value to hand back. bounded_nursery turns a non-zero answer into a ChildFailed, which is what a program should be reading rather than this.

A failure cancels the siblings, and when is not yet a promise. A nursery is a unit: the block asked for these fibers together, so one of them failing means the answer the group was computing is not coming and the rest are working on a question nobody will ask. They are canceled rather than killed, so each stops at its next ! and runs its finalizers on the way out, and every one of them is still waited for.

What is measured today is weaker than that reads. A nursery reaps handles oldest-first, so a failure is noticed in adoption order: with twelve children and a failure at 10 ms, the siblings were canceled in 2-8 ms when the doomed child was adopted first, in about half of runs at all when it was adopted in the middle, and in none of twenty-five runs when it was adopted last – everyone finished and the count came back 421 ms later. The group does collapse and every child is waited for. Promptness is not something to build on yet. Roadmap 16.7.

Trait implementations

Show for Int

impl Show for Int

The scalars, so that derive(Show) on a record of them has something to call.

One line each, and each deferring to a to_string that already existed. The two have to agree — Show is what a generic function asks for and to_string is what a caller reaches for directly — and they agree here by one being written in terms of the other rather than by anyone remembering.

A String shows as itself, unquoted. A derived Show is for reading, not for parsing back: User { name: alice } is what a person wants in a log line, and a caller who needs the quotes is writing a serializer, which is std::json’s job and not this trait’s.

show

fn show(self) -> String

Show for Float

impl Show for Float

show

fn show(self) -> String

Show for Bool

impl Show for Bool

show

fn show(self) -> String

Show for Char

impl Show for Char

show

fn show(self) -> String

The character itself, with no quotes.

Show is what a value looks like to a reader, and 'a' printed inside a sentence should read a. The quoted form is how it is written in source, which is a different question and one nothing asks yet.

Eq for Char

impl Eq for Char

eq

fn eq(self, other: Char) -> Bool

Ord for Char

impl Ord for Char

cmp

fn cmp(self, other: Char) -> Ordering

By code point, which is what < on characters means everywhere.

Not a collation order. 'Z' sorts before 'a' because 90 is less than 97, and 'é' sorts after both; a human-facing sort of names wants a locale and a library, and pretending this is one would be worse than not having it.

Hash for Char

impl Hash for Char

hash

fn hash(self) -> Int

Show for String

impl Show for String

show

fn show(self) -> String

Eq for Int

impl Eq for Int

eq

fn eq(self, other: Int) -> Bool

Ord for Int

impl Ord for Int

cmp

fn cmp(self, other: Int) -> Ordering

Hash for Int

impl Hash for Int

An Int is its own hash. Map::slot does the mixing, so there is nothing for this to add.

hash

fn hash(self) -> Int

Eq for Bool

impl Eq for Bool

eq

fn eq(self, other: Bool) -> Bool

Eq for String

impl Eq for String

eq

fn eq(self, other: String) -> Bool

Hash for Bool

impl Hash for Bool

hash

fn hash(self) -> Int

Hash for String

impl Hash for String

FNV-1a over the bytes, which is one multiply and one xor each and is what a string hash is supposed to look like. Wrapping on purpose: the overflow is where the mixing comes from.

hash

fn hash(self) -> Int

Ord for String

impl Ord for String

Byte order, which is what < on a String means here.

Not a locale’s order and not code-point order — the first needs a table nobody has bound and the second differs from this one only above the basic plane. What it is is stable, cheap, and the same on every machine, which is what sorting for a program’s own use wants. A human-facing sort wants a collation library and should say so.

Compared by the runtime’s memcmp, with no cancellation point inside: a comparison of two strings is one call however long they are.

cmp

fn cmp(self, other: String) -> Ordering

Eq for Ordering

impl Eq for Ordering

eq

fn eq(self, other: Ordering) -> Bool

Show for Ordering

impl Show for Ordering

show

fn show(self) -> String

The variant’s own name, which is what a comparison in a log wants to say.

Show for Option<A>

impl<A: Show> Show for Option<A>

Some(3) and None, which is how they are written minus the prefix.

The two most-reached-for types in the language could not be printed. print("saw ${found}") on an Option was refused, and the message advised derive(Show) – on a type in std that the reader does not own and cannot annotate. So the shortest debugging line anybody writes was unavailable, and the advice for fixing it could not be taken.

The variant’s own name, the way Ordering does it, rather than the value alone. Some("") and None print differently, which is most of the reason somebody is looking.

show

fn show(self) -> String

Eq for Option<A>

impl<A: Eq> Eq for Option<A>

Both nothing, or both something and the somethings equal.

assert(found == Option::None) could not be written, which is the assertion a test makes about a lookup that should miss. The workaround was assert(Option::is_none(found)), which says the same thing about None and nothing at all about Some.

eq

fn eq(self, other: Option<A>) -> Bool

Ord for Option<A>

impl<A: Ord> Ord for Option<A>

Nothing sorts before something, and two somethings by their contents.

The order every language that has this type picks, and the one a sort by an optional field wants: the rows that have the field, in order, after the rows that do not.

cmp

fn cmp(self, other: Option<A>) -> Ordering

Show for Result<A, E>

impl<A: Show, E: Show> Show for Result<A, E>

Ok(3) and Err("no"), for the same reason Option has one.

Both halves need Show, because either may be the one printed and a type that could print only its successes would be the wrong way round for the line somebody is actually writing.

show

fn show(self) -> String

Eq for Result<A, E>

impl<A: Eq, E: Eq> Eq for Result<A, E>

Same side, and equal contents.

eq

fn eq(self, other: Result<A, E>) -> Bool

Show for Redacted<A>

impl<A> Show for Redacted<A>

show

fn show(self) -> String

<redacted>, whatever is inside.

No bound on A: this never looks at the value, which is the point, and requiring A: Show would mean a secret you cannot show is a secret you cannot wrap.

Iterator for Range

impl Iterator for Range

Associated types

Item

type Item = Int;

Effects

type Effects = {};

Functions

next

fn next(self) -> Step<Range, Int>

Show for List<A>

impl<A: Show> Show for List<A>

[a, b, c], which is how the literal is written.

Added because derive(Show) walks fields, and a record holding a List could not derive one – so the type people reach for by default was the type that made a struct unprintable. The bound is on the element, so a list of something unshowable is still unshowable, which is the honest answer.

show

fn show(self) -> String

Eq for List<A>

impl<A: Eq> Eq for List<A>

Element by element, and length first where they differ in length.

eq

fn eq(self, other: List<A>) -> Bool

Ord for List<A>

impl<A: Ord> Ord for List<A>

cmp

fn cmp(self, other: List<A>) -> Ordering

Element by element, and a list that runs out first is smaller.

Lexicographic, which is what every other language means by comparing two sequences and what a sorted list of paths, version segments or keys needs. Length is the tie-break rather than the first question: [1, 2] is less than [1, 2, 0], and [2] is greater than [1, 9, 9].

Consistent with the derived Eq above – two lists compare Equal exactly when eq says they are equal – which is the property that lets sort on a List<List<A>> mean anything.

Iterator for List<A>

impl<A> Iterator for List<A>

Associated types

Item

type Item = A;

Effects

type Effects = {};

Functions

next

fn next(self) -> Step<List<A>, A>

Iterator for Mapped<I, B>

impl<I: Iterator, B> Iterator for Mapped<I, B>

Associated types

Item

type Item = B;

Effects

type Effects = I::Effects;

Functions

next

fn next(self) -> Step<Mapped<I, B>, B> with Self::Effects

Taken apart rather than read from. self.inner copies the source out of the adapter, so it reaches the inner next shared and the cell it matched cannot be built in. Destructuring hands it over instead, which is what a record pattern is for here.

Iterator for Filtered<I>

impl<I: Iterator> Iterator for Filtered<I>

Associated types

Item

type Item = I::Item;

Effects

type Effects = I::Effects;

Functions

next

fn next(self) -> Step<Filtered<I>, I::Item> with Self::Effects

One next may pull many times, which is the whole of what a filter is: it walks until something is kept or the source runs out, so a caller never sees a step that yielded nothing.

Iterator for Taken<I>

impl<I: Iterator> Iterator for Taken<I>

Associated types

Item

type Item = I::Item;

Effects

type Effects = I::Effects;

Functions

next

fn next(self) -> Step<Taken<I>, I::Item> with Self::Effects

The count is checked before the pull, so take(0) on a stream that reads a socket reads nothing at all. A take that pulled first and then discarded would be a different program.

Functor for Option

impl Functor for Option

map

fn map<A, B, 'ef, 'er>(self: Option<A>, f: (A) -> B with 'ef raises 'er) -> Option<B> with 'ef raises 'er

Applicative for Option

impl Applicative for Option

pure

fn pure<A>(value: A) -> Option<A>

map2

fn map2<A, B, C>(self: Option<A>, other: Option<B>, f: (A, B) -> C) -> Option<C>

Traversable for Option

impl Traversable for Option

traverse

fn traverse<A, B, F: Applicative>(self: Option<A>, f: (A) -> F<B>) -> F<Option<B>>

Functor for List

impl Functor for List

map

fn map<A, B, 'ef, 'er>(self: List<A>, f: (A) -> B with 'ef raises 'er) -> List<B> with 'ef raises 'er

Each element through f, in order.

A loop and not a recursion, which is the rule every other walk in this file already followed: fold, filter, any, contains, zip and partition are all while with an accumulator, because Khora does not promise tail calls and a frame per element dies on a long list.

Built back to front and reversed, so the answer is in the order the input was and f is called in that order too. That matters when f has effects: map over a list of requests should make them in the order the list is in.

Traversable for List

impl Traversable for List

traverse

fn traverse<A, B, F: Applicative>(self: List<A>, f: (A) -> F<B>) -> F<List<B>>

Each element through f, with the effects combined and the answers collected.

Two loops rather than a recursion, for the reason map above has one, and two rather than one because the order has to survive being made iterative. There are two orders and they are not the same:

• f is called front to back, because it may have effects and a traversal over a list of requests should make them in the order the list is in. That is the first loop.
• The effects combine back to front, because map2 puts its left side’s failures first and the recursion this replaces nested to the right: map2(f(a), map2(f(b), map2(f(c), pure(Nil)))). Combining the other way round reverses the error list, which for Validated – the one type in std built for accumulating errors – is the whole thing it is for. That is the second loop, over what the first collected in reverse.

Doing it in one loop gets one of the two wrong, which is why there are two.

Eq for U8

impl Eq for U8

eq

fn eq(self, other: U8) -> Bool

Ord for U8

impl Ord for U8

cmp

fn cmp(self, other: U8) -> Ordering

Show for U8

impl Show for U8

show

fn show(self) -> String

Hash for U8

impl Hash for U8

hash

fn hash(self) -> Int

Eq for U16

impl Eq for U16

eq

fn eq(self, other: U16) -> Bool

Ord for U16

impl Ord for U16

cmp

fn cmp(self, other: U16) -> Ordering

Show for U16

impl Show for U16

show

fn show(self) -> String

Hash for U16

impl Hash for U16

hash

fn hash(self) -> Int

Eq for U32

impl Eq for U32

eq

fn eq(self, other: U32) -> Bool

Ord for U32

impl Ord for U32

cmp

fn cmp(self, other: U32) -> Ordering

Show for U32

impl Show for U32

show

fn show(self) -> String

Hash for U32

impl Hash for U32

hash

fn hash(self) -> Int

Eq for U64

impl Eq for U64

eq

fn eq(self, other: U64) -> Bool

Ord for U64

impl Ord for U64

cmp

fn cmp(self, other: U64) -> Ordering

Show for U64

impl Show for U64

show

fn show(self) -> String

Hash for U64

impl Hash for U64

hash

fn hash(self) -> Int

Eq for I8

impl Eq for I8

eq

fn eq(self, other: I8) -> Bool

Ord for I8

impl Ord for I8

cmp

fn cmp(self, other: I8) -> Ordering

Show for I8

impl Show for I8

show

fn show(self) -> String

Hash for I8

impl Hash for I8

hash

fn hash(self) -> Int

Eq for I16

impl Eq for I16

eq

fn eq(self, other: I16) -> Bool

Ord for I16

impl Ord for I16

cmp

fn cmp(self, other: I16) -> Ordering

Show for I16

impl Show for I16

show

fn show(self) -> String

Hash for I16

impl Hash for I16

hash

fn hash(self) -> Int

Eq for I32

impl Eq for I32

eq

fn eq(self, other: I32) -> Bool

Ord for I32

impl Ord for I32

cmp

fn cmp(self, other: I32) -> Ordering

Show for I32

impl Show for I32

show

fn show(self) -> String

Hash for I32

impl Hash for I32

hash

fn hash(self) -> Int

Show for Pair<K, V>

impl<K: Show, V: Show> Show for Pair<K, V>

show

fn show(self) -> String

key: value, which is what it reads as everywhere it is written down.

No brackets around it. A Pair is nearly always inside something that has its own – Dict and Map both print a list of these – and a pair that brought its own would double them.

Show for Dict<K, V>

impl<K: Ord + Show, V: Show> Show for Dict<K, V>

show

fn show(self) -> String

{a: 1, b: 2}, in key order.

Braces rather than brackets, so a map does not read as a list at a glance. In key order because a Dict is a search tree and entries walks it in order – which means two dictionaries holding the same entries print the same way, and a golden test over one is worth writing. Map cannot promise that and says so.

The key needs both bounds and for different reasons: Ord is what a Dict asks of its keys at all, and Show is what printing one asks. A map whose keys order but cannot print does not print, which is the right answer – there is nothing to write in place of the key.

Show for Map<K, V>

impl<K: Hash + Show, V: Show> Show for Map<K, V>

show

fn show(self) -> String

{a: 1, b: 2}, in whatever order the buckets are in.

And that order is arbitrary, so do not write a golden test over one. The type’s own note says entries come back in no particular order and not even a stable one, because growing rehashes everything; printing cannot promise more than the walk it is built on. A Dict prints in key order and is what to reach for when the text has to be comparable.

Sorting here instead would need K: Ord, which would mean a map whose keys hash but do not order could not print at all – and the reason this exists is that a record holding a Map could not derive Show. Trading that back for a tidier order is the wrong way round.

Show for Vector<A>

impl<A: Show> Show for Vector<A>

[a, b, c], the same as a List of the same elements.

The two print alike on purpose: which container a value is in is a decision about cost, and a log line that changed shape when somebody swapped one for the other would make that decision visible in the wrong place.

Its elements, not its array. The cells past len hold whatever a pop left behind, and printing those would be printing the vector’s history.

show

fn show(self) -> String

Functions

assert

pub fn assert(condition: Bool)

Fails the test this is written in, if condition is false.

Only allowed inside a test block, and inside one it needs no !. Both halves of that are deliberate: an assertion is the one place a reader of a test already expects control to leave, it is written at every one of them, and a test is not ordinary code.

assert_that

pub fn assert_that(condition: Bool, message: String)

The same, with something to say when it does not hold.

assert reports which assertion failed and on what line. What it cannot report is why, because a Bool arrives having forgotten both operands — so the next step was always to add a print and build again, which on a program linking std costs the better part of a minute to recover a value the test had already computed.

test "a record decodes" {
  let parsed = decode(input);
  assert_that(parsed.port == 8080, "port was ${parsed.port}");
}

The message is built only when the assertion fails, so a passing test — which is nearly all of them, nearly all the time — does not allocate it.

Only allowed inside a test block, like assert, and for the same reason.

print

pub fn print(value: String)

Writes a line to standard output.

A String and nothing else. A number needs converting first — Int::to_string(n), Float::to_string(x) — or interpolating, which calls Show for you: print("saw ${n}").

Not an effect, unlike std::log — so it needs no with clause and can be called before any capability is installed.

todo

pub fn todo<A>() -> A

A hole where the code is not written yet.

It answers whatever is wanted, so it fits anywhere. An unwritten match arm has to agree with whatever its neighbors produce, so this is generic in its result and todo() type-checks in a String arm and an Int arm alike, leaving the program compiling while a case is unfinished.

Generic rather than -> Never because a body that is a Never call has no value for the backend to return; the runtime symbol under it has that type, and a caller substitutes its own.

Running one stops the program the way every other trap does, with a message and status 134. That is the point rather than a limitation: a placeholder that returned a plausible value would let a half-written program answer, and a wrong answer is the one outcome worse than a refusal.

match color {
  Color::Red => "red",
  Color::Green => todo(),
}

join_all

pub fn join_all<A: Share, 'er>(fibers: List<Fiber<A, 'er>>) -> List<A> raises 'er

Every fiber’s answer, in the order the handles were given.

The gap a nursery cannot close. Fibers::wait waits for its children and discards what they computed, and it has to: a nursery holds Fiber<(), 'er>, because an operation cannot be generic in a type – only in a row – so the answer is fixed at () where the handles are held. That is written down at Nursery and it is not going to change.

This is a plain function rather than an operation, so it can be generic in A, which is the whole reason it can exist. Fan out with Fiber::spawn, keep the handles, and ask for the answers:

let prices = join_all(List::map(symbols, fn s => Fiber::spawn(fn () => quote(s)!)))!;

The first failure comes out, and the rest are still waited for. The raise unwinds past the handles that have not been joined yet, and letting a handle go waits for its fiber – which is where structured concurrency comes from and is why this needs no cleanup of its own. So a fan-out where one branch fails is a raise, not a leak, and not a fiber still running after the caller has moved on.

A cancellation does not come out here the way a failure does. This joins, and Fiber::wait records what a join does to a fiber that was canceled: a canceled fiber has no answer, so the join has nothing to hand back and unwinds the joiner along with it. Where the joiner is main there is nowhere left to unwind to, and the program ends at status 130 naming the call that got there. Being ordered is what leaves no other answer: a list in handle order has no entry to put where an answer was never computed.

So a deadline over a fan-out is not spelled as a cancel and then a join_all. A caller who only needed the ordering wants Fiber::wait, which does not ask for an answer and so has nothing to lose when there is none; one who wants to stop waiting at all wants Fiber::detach.

In handle order rather than completion order. A caller who wanted the fastest first wanted a channel, and one who wanted the answers lined up against the requests – which is nearly everybody – wanted this.

A: Share is Fiber::join’s own bound and not a new one: the answer was computed on another fiber and has to be safe to hold from this one.

nursery

pub fn nursery<A, 'ef, 'er>(body: () -> A with { 'ef | nursery: Nursery } raises 'er) -> A with 'ef raises 'er + ChildFailed

Runs body with a nursery, and does not return until its children are done.

Structured concurrency, and the structure is the region’s: a fiber cannot outlive this block, because leaving it — at the end, on a return, or with a raise passing through — releases the nursery, and releasing a nursery stops what is still running.

A named function or a lambda; both work. A named function receives what its with clause names as evidence parameters, so it can be handed here directly and called with the nursery this function installs:

fn serve<'ef>() -> () with { 'ef | nursery: Nursery } { .. }
nursery(serve)!

nursery(fn () => serve()!) is the same thing. A lambda resolves a capability lexically where it can and requires it where it cannot, so this one’s type becomes () -> () with { nursery: Nursery } and the body()! below supplies it from the handler just installed. That is the rule in the capability-passing design note, and the reason for it is that eta-expansion must not alter what a program means.

And the body may name the nursery:

nursery(fn () => {
  nursery.adopt(Fiber::spawn(work));
  nursery.adopt(Fiber::spawn(more));
})!

Inside the body, nursery is the capability rather than this function: the label is the lambda’s parameter in all but spelling, and shadows this function the way a parameter shadows anything else.

bounded_nursery

pub fn bounded_nursery<A, 'ef, 'er>(limit: Int, body: () -> A with { 'ef | nursery: Nursery } raises 'er) -> A with 'ef raises 'er + ChildFailed

The same, holding at most limit children at once.

Which one to reach for is a question about where the work comes from. A nursery over a known handful of tasks — three lookups in parallel, a fan-out over a list you are holding — should be unbounded, because the count is already bounded by the thing you are iterating. A nursery fed by the outside world should not be, because then the count is somebody else’s decision.

A fiber is an operating-system thread today, so unbounded there means a ceiling met by exhausting memory. Bounded means one met by adopting more slowly, which for a server means accepting more slowly, which the listening socket’s backlog is already built to absorb: overload becomes latency instead of collapse.

import std::core::{ChildFailed, Fiber, Nursery, bounded_nursery, print};

fn handle(job: Int) -> () { print("job ${job}") }

fn launch() -> () with { nursery: Nursery } {
  let mut next = 0;
  while next < 1000 {
    let job = next;
    nursery.adopt(Fiber::spawn(fn () => handle(job)));
    next = next + 1;
  }
}

pub fn main() raises ChildFailed { bounded_nursery(64, launch)! }

The producer slows down at the boundary where it creates work rather than filling an unbounded queue somewhere else. The limit admits limit + 1 live children, because Fiber::spawn starts the child before adopt blocks; subtract one where it stands for a real resource.

scoped

pub fn scoped<A, 'ef, 'er>(body: () -> A with { 'ef | scope: Scope } raises 'er) -> A with 'ef raises 'er

Runs body in a fresh region, discharging its scope requirement.

Row subtraction made concrete: scope is present in the body’s requirement row and absent from the result’s. The region is an ordinary binding of this function, so it ends when this function does — including when body raises and the error passes straight through.

A named function or a lambda, for the reason on nursery.

import std::core::{Scope, acquire, scoped};
import std::net::socket::{listen_on, shut};

fn serve() -> () with { scope: Scope } {
  let server = acquire(listen_on(8080), fn s => shut(s));
  answer(server)
}

pub fn main() -> Int { scoped(fn () => serve()); 0 }

scoped is where the releases run, and they run on every way out – a return, a raise, or a cancellation. That last one is why this exists rather than a close written after the loop: a canceled fiber never reaches the line after the loop.

It is also how a child fiber releases what it acquires. The scope stays on the fiber that opened it, so a child cannot be handed its parent’s; it opens its own, and its releases run on the child: Fiber::spawn(fn () => scoped(work)), or with a lambda, scoped(fn () => work(connection)). The scope scoped hands its body is the one the body uses, inside a function with a scope of its own as anywhere else.

acquire

pub fn acquire<A, 'ef>(value: A, release: (A) ->()) -> A with { 'ef | scope: Scope }

Acquires a value and registers its release in one step.

The generic half of Scope, kept out of the effect so the operation can stay a plain closure. release is called with value when the region ends.

import std::core::{Scope, acquire};
import std::net::socket::{connect_to, shut, transmit};

fn ask(host: String) -> Int with { scope: Scope } {
  let connection = acquire(connect_to(host, 80), fn c => shut(c));
  transmit(connection, "GET / HTTP/1.0\r\n\r\n")
}

Registered with the enclosing scoped, and it returns the value so the acquisition and the release are one expression. Written as two statements – take it, then remember to close it – the second is the one a cancellation skips.

attempt

pub fn attempt<A, E, 'ef>(body: () -> A with 'ef raises E) -> Result<A, E> with 'ef

Runs body and makes its failure a value.

The error channel and Result are the same thing said two ways — a tagged return already is “an error or a value” — and this is where a caller chooses which way to read it. The row of body is discharged, so what comes back cannot fail again.

This is also what makes retrying possible: a policy that runs a computation a second time has to be able to see that the first time did not work, without knowing what it was doing.

One error type, and that is a real limit. E is a type rather than a row, so a body raising IoError + Denied has nowhere to go through here:

error: this argument: `Denied` is not accounted for here. This takes one
       error type and the body raises `IoError` and `Denied`; there is no
       type that means "either of these", so handle them with `catch`
       instead

The limit is not an oversight. Result<A, E> needs one E, and Khora has no anonymous sum to name “either of these two” — so there is nothing for a two-type row to collapse into. Naming a union would mean declaring a type for every pair of failures a program happens to combine, which is worse than the thing it fixes.

catch is the answer, because it matches per type and never has to name the union:

let answer = fetch(url)! catch {
  IoError::NotFound(_p) => fallback(),
  Denied(_p) => refuse(),
};

A row of one is what attempt is for, and it stays the shorter way to write it.