Tables with empty keys and without keys

[QinshiWang]

The manual says as follows:

If a table has no key property, then it contains no look-up table, just a default action—i.e., the associated lookup table is always the empty map.

I'm wondering if it also includes key = { }. I think literally it doesn't. It only means tables without the key property.

[mihaibudiu]

These should be equivalent

[QinshiWang]

@mbudiu-vmw Okay. Then let's say it in the spec.

[jnfoster]

Just to state the obvious, it could instead be that a table with key = {} can be in three configurations:

• A single entry whose key is the empty tuple,
• No entries and no default action defined in the program or set by the control plane (so implicitly NoAction),
• No entries and a default action defined in the program or set by the control plane.

[QinshiWang]

Currently, the syntax doesn't allow defining an entry with empty tuple.

[jnfoster]

Except for tables with const entries, this is a P4Runtime question, not a P4 Language question.

[QinshiWang]

If it's said there's no look-up table, then there are no entries, for both const and non-const. But if we don't say it, I agree that the control plane can have entries for key = { }

[jnfoster]

I think we can go either way:

• Decide that key = {} is the same as no key property.
• Decide that key = {} is a lookup table with only one possible entry.
  Either one is coherent. I have a slight preference for the latter, as it seems more coherent.

(I don't think this is a big deal in practical programs...)

[QinshiWang]

It matters for practical programs. Practical programs do use key = { } or keyless (I'm not sure which one should be preferred) to encode a "direct action" table, so the name of the table is given by the program instead of the compiler.

    table tbl_clear_index {
        actions = {
            act_clear_index();
        }
        default_action = act_clear_index();
        size = 1;
    }

[jnfoster]

Of course. What I meant is that I don't know if having both no-key and empty-key tables (with different semantics) is important in practical programs.

[jafingerhut]

It seems difficult to imagine that allowing key = {} tables to have a single entry that is an "empty key" provides any additional power in the language. Whether you can add such an entry or not, as long as the default action is not declared const, the runtime can change the behavior of a miss on the table any time it wants to, just as it could for a hit entry.

[vgurevich]

I guess, the question is: should the spec explicitly state that not specifying the key at all is totally equivalent to specifying an empty key or these constructs are not equivalent and the rest is left to the implementation.

There might be one subtle difference between them, but today's front end does not allow us to see it (and that might be a good thing, actually) :)

Imagine two tables:

table t1 {
    actions = { a; }
    const default_action = a();
}

table t2 = {
    key = { }
    actions = { a };
    const default_action = a();
    const entries = {
        _ : a();
    }
}

Obviously, the first question is whether the table t2 is legit (and specifically the question will be about its const entries). Today's frontend believes that it is not, therefore making the discussion a little easier:

$ ~/tools/p4_test.sh empty_key.p4 
empty_key.p4(86): [--Werror=type-error] error: Entry
            _ : a();
            ^^^^^^^
  ---- Actual error:
  Tuples with different sizes 0 vs 1
  ---- Originating from:
  empty_key.p4(86): Table entry has type 'tuple<>' which is not the expected type 'tuple<_>'
              _ : a();
              ^

In other words, if we state that a table with an empty key can have no entries ever, then I think that we will be in our full right to declare that no key and en empty key are the same thing. It will also mean that, indeed, the only result after applying the table with no key is a miss, confirming the correctness of what the spec states today.

If, however, we find that it is OK for _ to match on anything, including the the values of the type tuple<>, then applying table t1 will always result in execution of the action a() and a miss, whereas applying the table t2 should always result in execution of the action a() and a hit.

[QinshiWang]

It seems difficult to imagine that allowing key = {} tables to have a single entry that is an "empty key" provides any additional power in the language. Whether you can add such an entry or not, as long as the default action is not declared const, the runtime can change the behavior of a miss on the table any time it wants to, just as it could for a hit entry.

Yes. For this, I think the only behavior that is changed is hit or miss, right? But it matters for the formalization. We need to know when key = {}, if the control plane can add entries. That's not the same mechanism as the default action.

[jafingerhut]

Would collecting the current behavior of P4Runtime API, Barefoot API, and TDI in this area help provide guidance here? For example, if for all of them the behavior of a table with key = {} and a table with no key attribute at all was "no key can be added, not even an 'empty key'", that would seem to be consistent with a future spec revision explicitly saying that these two kinds of tables are equivalent, and will always experience a miss when they are applied.

[mihaibudiu]

@vgurevich the bug you mention has been just fixed.

[QinshiWang]

@mbudiu-vmw @vgurevich So what's the current behavior of the compiler? In

    const entries = {
        _ : a();
    }

does it allow _ to be any kind, including tuple<>, tuple<_>, tuple<_, _>, etc.?

[mihaibudiu]

The type of _ is Type_Dontcare, also written as _, and it unifies with anything.

[vgurevich]

The latest version of p4-test still complains:

$ ~/tools/p4_test.sh empty_key.p4 
empty_key.p4(86): [--Werror=type-error] error: Entry
            _ : a();
            ^^^^^^^
  ---- Actual error:
  Tuples with different sizes 0 vs 1
  ---- Originating from:
  empty_key.p4(86): Table entry has type 'tuple<>' which is not the expected type 'tuple<_>'
              _ : a();
              ^

empty_key_psa.p4.txt

[vgurevich]

One thing that I can say is that that Tofino implementation treats tables with no key and with an empty key identically both at the compiler and at the API lieve.. @jafingerhut plans to test BMv2 implementation and if we found that they are treated the same way too, I think it might be reasonable just to codify it in the spec that key = {} is the same as not specifying the key at all.

[mihaibudiu]

That is because no one wants to review the fix in p4lang/p4c#3444

[vgurevich]

@mbudiu-vmw -- as per my previous message, it might actually not be a bad thing that we reject the program above -- in fact is strengthens the case for treating the "empty" key as "no key"

[mihaibudiu]

Once the fix is merged you should file a new issue if you think that the error message is wrong.

[vgurevich]

@mbudiu-vmw My point is that the way the compiler is today, it allows us to answer the question posed in this issue very easily. Once you merge the fix, the answer will be different, because it will open a new possibility :)

[jnfoster]

It may well be a very good idea to rule out this program. My suggestion to consider treating no key / empty key as different was not me lobbying for that resolution. Rather, it came from a default approach that starts by trying to have simple and uniform constructs that compose cleanly in the language design (I.e. without myriad special cases). In particular, because (i) key declarations are treated as tuples and (ii) we have empty tuples / empty tuple types in the language, it would be consistent/uniform/logical to treat the empty key as having the empty tuple type. But it is also totally sensible for us to decide that — for domain specific reasons — we should depart from uniformity as an overarching design principle and treat empty/missing key declarations as equivalent. In that case, we should extend the typechecking rule for table declarations to explicitly rule out tables with empty/missing keys and also const entries. However, we should not rely on a bug/glitch in the current implementation to enforce that conditions. That’s just how good language design and compiler engineering works…

…

On Wed, Jul 20, 2022 at 5:42 PM Vladimir Gurevich ***@***.***> wrote: @mbudiu-vmw <https://github.com/mbudiu-vmw> My point is that the way the compiler is today, it allows us to answer the question posed in this issue very easily. Once you merge the fix, the answer will be different, because it will open a new possibility :) — Reply to this email directly, view it on GitHub <#1120 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAOCFUVAI3RLXEBVMQ2BTKDVVBXEBANCNFSM53TRVMFA> . You are receiving this because you commented.Message ID: ***@***.***>

[QinshiWang]

For the test given by @vgurevich

$ ~/tools/p4_test.sh empty_key.p4 
empty_key.p4(86): [--Werror=type-error] error: Entry
            _ : a();
            ^^^^^^^
  ---- Actual error:
  Tuples with different sizes 0 vs 1
  ---- Originating from:
  empty_key.p4(86): Table entry has type 'tuple<>' which is not the expected type 'tuple<_>'
              _ : a();
              ^

I think the error message here hints that _ also doesn't work for tuple<_, _>. Please let me know if that's true for p4_test.

[rst0git]

With Mihai's fix, p4test would accept the P4 program mentioned above and represent

  table t {
    key = {}
    actions = { a; }
    const entries = {
      _ : a();
    }
  }

as

table t {
    key = {}
    actions = {
        a();
        @defaultonly NoAction();
    }
    const entries = {
            default : a();
    }
    default_action = NoAction();
}

we should not rely on a bug/glitch in the current implementation to enforce that conditions.

I agree, it would be good to fix this bug. If we want to rule out this P4 program it would be good to use an explicit error message.

[jnfoster]

Qinshi, I’m not exactly sure if this is what you are asking, but I believe an underscore in an error message like this means any single type (and not multiple types).

…

-N

On Wed, Jul 20, 2022 at 7:24 PM Qinshi Wang ***@***.***> wrote: For the test given by @vgurevich <https://github.com/vgurevich> $ ~/tools/p4_test.sh empty_key.p4 empty_key.p4(86): [--Werror=type-error] error: Entry _ : a(); ^^^^^^^ ---- Actual error: Tuples with different sizes 0 vs 1 ---- Originating from: empty_key.p4(86): Table entry has type 'tuple<>' which is not the expected type 'tuple<_>' _ : a(); ^ I think the error message here hints that _ also doesn't work for tuple<_, _>. Please let me know if that's true for p4_test. — Reply to this email directly, view it on GitHub <#1120 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAOCFURJC2B4QT22TGP6MC3VVCDBTANCNFSM53TRVMFA> . You are receiving this because you commented.Message ID: ***@***.***>

[QinshiWang]

Yes. The error message indicates that if you want a wildcard for tuple<_, _>, you need to write _, _ instead of _. And if you want a wildcard for tuple<>, you need to write zero _'s which is not allowed in the syntax. So I'm asking whether this behavior is consistent with the spec and with what people think.

[mihaibudiu]

_ will unify with any type, including tuple<>.
tuple<_> will unify with a tuple of any type.
I guess that _,_ is in this context a literal with type tuple<_,_>.

[jafingerhut]

Sorry, I do not have the code handy to show right now, but with a fairly simple P4 program and using --p4runtime-files to generate P4Info files for a table with key = {} and with no key property at all, they generate the same P4Info file, and even the same BMv2 JSON file for simple_switch.

[mihaibudiu]

The discussion conclusion in the LDWG is that an empty key is the same as no key. @jafingerhut should submit a PR against the spec.