Doublecheck the `EXCEPT`/`REFINE` madness

[SichangHe]

Leftover of #41.

[SichangHe]

RFC 2622:

The semantics for the except operator is as follows: The result of an
except operation is another <import-term>. The resulting policy set
contains the policies of the right hand side but their filters are
modified to only include the routes also matched by the left hand
side. The policies of the left hand side are included afterwards and
their filters are modified to exclude the routes matched by the right
hand side. Please note that the filters are modified during this
process but the actions are copied verbatim. When there are multiple
levels of nesting, the operations (both except and refine) are
performed right to left.

Examples:

Consider the following example:

import: from AS1 action pref = 1; accept as-foo;
        except {
           from AS2 action pref = 2; accept AS226;
           except {
              from AS3 action pref = 3; accept {128.9.0.0/16};
           }
        }

where the route 128.9.0.0/16 is originated by AS226, and AS226 is a
member of the as set as-foo. In this example, the route 128.9.0.0/16
is accepted from AS3, any other route (not 128.9.0.0/16) originated
by AS226 is accepted from AS2, and any other ASes' routes in as-foo
is accepted from AS1.

We can come to the same conclusion using the algebra defined above.
Consider the inner exception specification:

  from AS2 action pref = 2; accept AS226;
  except {
     from AS3 action pref = 3; accept {128.9.0.0/16};
  }

is equivalent to

 {
  from AS3 action pref = 3; accept AS226 AND {128.9.0.0/16};
  from AS2 action pref = 2; accept AS226 AND NOT {128.9.0.0/16};
 }

Hence, the original expression is equivalent to:

import: from AS1 action pref = 1; accept as-foo;
        except {
           from AS3 action pref = 3; accept AS226 AND {128.9.0.0/16};
           from AS2 action pref = 2; accept AS226 AND NOT {128.9.0.0/16};
        }

which is equivalent to

import: {
  from AS3 action pref = 3;
           accept as-foo AND AS226 AND {128.9.0.0/16};
  from AS2 action pref = 2;
           accept as-foo AND AS226 AND NOT {128.9.0.0/16};
  from AS1 action pref = 1;
           accept as-foo AND NOT
             (AS226 AND NOT {128.9.0.0/16} OR AS226 AND {128.9.0.0/16});
  }

Since AS226 is in as-foo and 128.9.0.0/16 is in AS226, it simplifies
to:

import: {
         from AS3 action pref = 3; accept {128.9.0.0/16};
         from AS2 action pref = 2; accept AS226 AND NOT {128.9.0.0/16};
         from AS1 action pref = 1; accept as-foo AND NOT AS226;
       }

In the case of the refine operator, the resulting set is constructed
by taking the cartasian product of the two sides as follows: for
each policy l in the left hand side and for each policy r in the
right hand side, the peerings of the resulting policy are the
peerings common to both r and l; the filter of the resulting policy
is the intersection of l's filter and r's filter; and action of the
resulting policy is l's action followed by r's action. If there are
no common peerings, or if the intersection of filters is empty, a
resulting policy is not generated.

Consider the following example:

import: { from AS-ANY action pref = 1; accept community(3560:10);
          from AS-ANY action pref = 2; accept community(3560:20);
        } refine {
           from AS1 accept AS1;
           from AS2 accept AS2;
           from AS3 accept AS3;
        }

Here, any route with community 3560:10 is assigned a preference of 1
and any route with community 3560:20 is assigned a preference of 2
regardless of whom they are imported from. However, only AS1's
routes are imported from AS1, and only AS2's routes are imported from
AS2, and only AS3's routes are imported form AS3, and no routes are
imported from any other AS. We can reach the same conclusion using
the above algebra. That is, our example is equivalent to:

Note that the above nested example is disallowed according to RFC 4012.

Note that the definition allows subsequent or "cascading" refinements
and exceptions. RFC 2622 [1] incorrectly refers to these as "nested"
expressions. The syntax does not allow true nested expressions.

RFC 4012 added afi support:

The address family may be specified in subsequent refine or except
policy expressions and is valid only within the policy expression
that contains it.

Therefore, in the example

aut-num:    AS65534
mp-import: afi any.unicast from AS65001 accept as-foo;
             except afi any.unicast {
               from AS65002 accept AS65226;
             } except afi ipv6.unicast {
                 from AS65003 accept {2001:0DB8::/32};
               }

the last "except" is evaluated only for the IPv6 unicast address
family, while other import-expressions are evaluated for both the
IPv6 and IPv4 unicast address families.

[cunha]

This seems like a rabbit hole that only the craziest operators will use, and even then we'll likely find a lot of errors and noise.

[cunha]

+1 to the deferred label.