@jafingerhut @jnfoster This is an implementation of safe tagged unions. It diverges somewhat from Andy's proposal from the LDWG, but it sticks very close to the existing syntax. Please take a look particularly at the new test cases. A midend pass eliminates unions into structs plus tags.

There's a hole in this design. Consider the following:

union U { ... }
struct S { U u; }

extern void f(out S s);

S s;
switch (s.u) {
   U.field: { f(s); } // can change s.u, including the tag of u.
}

This can potentially mutate u through s. So it's not enough to make s.u read-only in each switch label, all structures that enclose s.u also have to be treated as read-only, i.e., s.

I think this can be fixed. I hope there are no other holes.

The language design working group has asked for some examples using unions. Here are some use cases that I find very compelling: exposing data structures to the dataplane, including mutable tables. Here is the design of an API for action-less tables, that could be compiled into traditional tables.

union Option<T> {
    T some;
    tuple<> none;
}

/**
 * Table with a match kind M, a key type K, and a value type V.
 */
extern SimpleTable<M, K, V> {
    /**
     * Create a table with match kinds T and the specified size (number of entries).
     * M must be a tuple with a structure similar to K; each field of the tuple
     * must be of type match_kind.
     */
    SimpleTable(M match_kinds_tuple, int size);
    /**
     * Lookup the key in the table.  Returns an option that contains the value on
     * hit or none on miss.
     */
    Option<V> lookup(in K key);
    /**
     * Update the entry corresponding to key K (or insert it if it does not exist).
     */
    void update(in K key, in V value);
    /**
     * Delete the entry corresponding to key K.
     */
    void delete(in K key);
}

union Either<HV, MV> {
    HV hit;
    MV miss;
}

/**
 * Table with match kind M, key type K and two kinds of values:
 * HV: value returned on a hit
 * MV: value returned on a miss
 */
extern Table<M, K, HV, MV> {
    /**
     * Create a table with match kinds M and the specified size (number of entries)
     * M must be a tuple with a structure similar to K; each field of the tuple
     * must be of type match_kind.
     */
    Table(M match_kinds_tuple, int size);
    /**
     * Lookup the key in the table.  Returns an Either structure, with
     * the hit field present on a hit, or the field miss present on a miss.
     */
    Either<HV, MV> lookup(in K key);
    /**
     * Update the entry corresponding to hit on key K (or insert it if it does not exist).
     */
    void update(in K key, in HV value);
    /**
     * Update the entry corresponding to a miss.
     */
    void updateMiss(in MV value);
    /**
     * Delete the entry corresponding to key K.
     */
    void delete(in K key);
}

Here is a sample program using the SimpleTable:

struct S {
    bit<32> a;
    bit<32> b;
}

struct V {
    bit<16> c;
    bit<16> d;
}

struct M {
    match_kind m0;
    match_kind m1;
}

control c(out bit<16> data) {
    SimpleTable<M, S, V>({ exact, exact }, 24) s;

    apply {
        S key = { 10, 20 };
        Option<V> o = s.lookup(key);
        switch (o) {
            o.some as some: {
                data = some.c   some.d;
            }
            default: {
                data = 0;
            }
        }

        s.update(key, { 0, 1 });
        s.delete(key);
    }
}

Compounding this example, one can even create tables where the values are unions themselves.

For each entry in a table, a counter already tracks hit or miss. Why do we need to update hit/miss count using an API in a new extern?

Does it make sense, to add a "show table" API so that a user gets a list of all entries in the table? I think P4Runtime should already support getting such data.

If the design adds mutable table entries, since p4c already supports "const entries = { }", is the plan to support "entries = { }" to configure a mutable entry? Or would you add an explicit table property for a table being mutable in data plane or both?

I suppose such new externs go into psa.p4 and pna.p4 architecture files?

For each entry in a table, a counter already tracks hit or miss. Why do we need to update hit/miss count using an API in a new extern?

There is nothing in this API about counting.

Does it make sense, to add a "show table" API so that a user gets a list of all entries in the table? I think P4Runtime should already support getting such data.

That is a control-plane API, these are all data-plane APIs.

If the design adds mutable table entries, since p4c already supports "const entries = { }", is the plan to support "entries = { }" to configure a mutable entry? Or would you add an explicit table property for a table being mutable in data plane or both?

That is completely independent of this proposal. The reason we haven't done it is that we don't have syntax to represent table contents for arbitrary table representations; e.g., priorities. But since match_kind can be user-defined, the shape of tables is not fixed.

I suppose such new externs go into psa.p4 and pna.p4 architecture files?

They could be included in architectures that support such tables, but they could also be in independent libraries. I plan to implement a pass which converts such tables into traditional tables, so the API could be supported potentially on any architecture.

@mbudiu-vmw OK, understood - thanks for your reply. It's a very good API design for data plane.

Updating an entry to the data plane from the data plane is expected to be an asynchronous call. When the writing is done, the data plane should notify the caller if update of an entry was successful or failed? Currently, in P4, the data plane does not read counters. But, the counters on the entry are available in the data plane to see if a counter in increasing for hit after an Update. If an entry can be updated by data plane, maybe it’s not a stretch to change behavior that the data plane also reads counters?

You can extend this API in many ways, including adding a new method to access counters associated with a key.
You can also model the counters associated with a table like a separate table that maps keys to numbers.

You can extend this API in many ways, including adding a new method to access counters associated with a key.
You can also model the counters associated with a table like a separate table that maps keys to numbers.

Sounds good. We can now take this discussion to a PNA meeting to tweak the API since the NIC is expected to use writing to data plane by the data plane .

I plan to provide a working implementation of this API in the ebpf backend. Once it's working end to end we can be more confident.

Unfortunately this proposal is flawed. The problem is that one can surreptitiously modify the union that is being accessed, e.g.,
switch (u) { Option.some: action(); }, where the action will modify u. So a slightly different scheme will be necessary. I think I have an alternative proposal that we'll have to discuss.

This is a reworked implementation of safe unions.

Some bikeshedding thoughts:

• Being able to "clear" a union to "no longer initialized" or, alternatively, avoiding the "not initialized" case somehow.
• It seems that I would forget sometimes the final s.f = f; in a case like the one below. I hope that the compiler can be smart enough to warn me if I forget:

 s.f as f: {
                o = f.f == 1;
                f.f = 2;
                s.f = f;
            }

• Sometimes in switch (s), the s will be a long expression. It's not great to have to repeat that in each case. It would be nice if the switch cases could be written as .f instead of s.f.
• It seems like flattening nested switches could in some cases be convenient, e.g. switch (s.a.b) where both s and a are unions.

* Sometimes in `switch (s)`, the `s` will be a long expression. It's not great to have to repeat that in each case. It would be nice if the switch cases could be written as `.f` instead of `s.f`.

Mihai suggested that syntax like switch (longexpression as s) could work too.