Subject: [netmod] when issues

From: Ladislav Lhotka <[email-masked]>
Date: Wed, 02 Dec 2009 08:05:11 +0100

Hi,

the issues raised in the other thread about 'when' IMO need to be
addressed. They are illustrated in this YANG fragment:

leaf foo {
    type uint8;
    default 42;
    when "not(../bar=1)";
}
leaf bar {
    type uint8;
    default 1;
    when "not(../foo=42)";
}

Dealing with the schema constraints at the same time as with the 'when'
and 'default' statements leads to a deadlock.

I think it is necessary to make the schema immune to "run-time"
modifications, so that 'when' should not be allowed under 'augment' and
'uses'. Only features might modify the schema.

In addition, it is necessary to prioritize the validation procedure by
dividing it into three steps similar to those outlined in DSDL mapping
draft, sec. 7:

1. The schema-based constraints are checked first, independently of the 
   remaining two steps.

2. Default values and ancestor containers are (conceptually) added 
   where necessary - this forms the "conceptual data tree".

3. Rule-based constraint ('must' and 'when') are checked.

In the above example, if the configuration contains neither "foo" nor
"bar", then
- step 1 succeeds because both leafs are optional,
- step 2 adds the leafs <foo>42</foo><bar>1</bar> (and ancestor 
  container(s), if necessary),
- in step 3, both 'when' rules are found to be violated, which leads to 
  a validation error.

Lada

-- 
Ladislav Lhotka, CESNET
PGP Key ID: E74E8C0C

---

From: Martin Bjorklund <[email-masked]>
Date: Wed, 02 Dec 2009 08:31:03 +0100 (CET)

Hi,

> and 'default' statements leads to a deadlock.

I think the problem comes from the recursive definition here.  I'd
rather make recurisive when expressions illegal.

> 'uses'.

I don't understand this.  Can you provide an example?  Originally, we
had "when" only for augment, allowing you to formally specify the
conditions for a sparse augmentation.

> In addition, it is necessary to prioritize the validation procedure

Why is this necessary?  It seems to be an implementation detail in
which order things are checked.  An implementation needs to detect
invalid configs, but how it does this does not matter.

> by

  leaf-list x {
    type int32;
    min-entries 1;
    when "../y > 1";
  }
  leaf y {
    type int32;
  }

Does your rule 1 mean that first I should check min-entries,
regardless of the 'when' statement?  So this instance doc will fail:

  <y>2</y>

/martin

---

From: Juergen Schoenwaelder <[email-masked]>
Date: Wed, 2 Dec 2009 09:08:44 +0100

> 'uses'. Only features might modify the schema.

There is no 'run-time' modification. You can always screw up data
models; even in SMIv2 land you can easily write new object definitions
where the description clause contradicts some other object
definitions. The only difference here is that YANG provides some very
sharp tools likely encouraging people to write down more contraints
than they would do in natural language and thus the likelihood to
regret certain constraints later on increases as well.

> - in step 3, both 'when' rules are found to be violated, which leads to 

So why are these steps useful for interoperability? The situation you
have above should ideally be caught before implementation begins, e.g.
by having a tool that understands YANG and is able to generate valid
pseudo configurations, much like abnfgen. If it is impossible to
generate valid instances, then this ideally should be caught before
'runtime'.

/js

-- 
Juergen Schoenwaelder           Jacobs University Bremen gGmbH
Phone: +49 421 200 3587         Campus Ring 1, 28759 Bremen, Germany
Fax:   +49 421 200 3103         <http://www.jacobs-university.de/>

---

From: Ladislav Lhotka <[email-masked]>
Date: Wed, 02 Dec 2009 09:21:34 +0100

> rather make recurisive when expressions illegal.

Such interferences can happen across any number of steps and can be
hidden in the complexity of XPath expressions, so there is no practical
way for detecting this in a general case.
 
> conditions for a sparse augmentation.

I think it is fundamentally wrong if an instance document is allowed to
modify the schema which is supposed to define the document's grammar. No
schema language I am aware of permits this.

The schema derived from all advertised modules and features should be
fixed.
 
> invalid configs, but how it does this does not matter.

It does resolve the above deadlock.

> regardless of the 'when' statement?  So this instance doc will fail:

Yes. The 'when' statement is then essentially equivalent to the
following 'must' constraint specified in the parent container:

must "y>1 or not(x)";

But you could achieve the right thing by using

  must "not(y>1) or count(x)>=1";
  leaf-list x {
    type int32;
    min-entries 0;
  }
  leaf y {
    type int32;
  }

Lada

-- 
Ladislav Lhotka, CESNET
PGP Key ID: E74E8C0C

---

From: Juergen Schoenwaelder <[email-masked]>
Date: Wed, 2 Dec 2009 09:31:46 +0100

> The schema derived from all advertised modules and features should be

I do not get why you believe an instance document modifies the schema.

/js

---

From: Ladislav Lhotka <[email-masked]>
Date: Wed, 02 Dec 2009 09:38:00 +0100

> I do not get why you believe an instance document modifies the schema.

Look at the example at the end of Martin's last message. Can you tell
what the schema is without looking into any instance document? Probably
I should rather have said that the schema depends on the instance
document.

Lada

-- 
Ladislav Lhotka, CESNET
PGP Key ID: E74E8C0C

---

From: Martin Bjorklund <[email-masked]>
Date: Wed, 02 Dec 2009 09:52:46 +0100 (CET)

> schema language I am aware of permits this.

The instance document does not modify the schema tree.

> The schema derived from all advertised modules and features should be

Yes.

> Yes.

But it is valid!  When y > 1, no x should exist.  When y <= 1, at
least 1 x must exist.

/martin

---

From: Ladislav Lhotka <[email-masked]>
Date: Wed, 02 Dec 2009 10:18:40 +0100

> The instance document does not modify the schema tree.

OK, the schema *depends on* the instance document, and such dependencies
are not localized and may even come from other modules via groupings and
augments.
 
> > The schema derived from all advertised modules and features should be

In your example, what is then the ordinality constraint on leaf-list x?

> But it is valid!  When y > 1, no x should exist.  When y <= 1, at

I showed you how this condition can be expressed using just 'must' and
'must' is absolutely safe because it operates by design only on the
instance document - or rather the conceptual data tree created from the
document. Are there any cases where 'when' cannot be emulated this way?

Lada

-- 
Ladislav Lhotka, CESNET
PGP Key ID: E74E8C0C

---

From: Martin Bjorklund <[email-masked]>
Date: Wed, 02 Dec 2009 10:30:53 +0100 (CET)

"Bert (IETF) Wijnen" <[email-masked]> wrote:
> Martin, I am not up to speed in YANG as you guys are,
> 
> but did you not mean
> 
>    When y <= 1, no x should exist.  When y > 1, at
>    least 1 x must exist.

Yes!  Thanks for catching this.  Negation is tricky...  

So my original example and question should be:

With this data model:

  leaf-list x {
    type int32;
    min-entries 1;
    when "../y <= 1";
  }
  leaf y {
    type int32;
  }

  <y>2</y>

It should not fail, since when y > 1, no x should exist.  When y <= 1,
at least 1 x must exist.

/martin

---

From: Ladislav Lhotka <[email-masked]>
Date: Wed, 02 Dec 2009 11:09:31 +0100

> Yes!  Thanks for catching this.  Negation is tricky... 

Right, I missed this too, but we know what the problem is. BTW,
min-entries should be min-elements. :-)

> It should not fail, since when y > 1, no x should exist.  When y <= 1,

It comes as no surprise if you know the rules of the game, namely that
"min-elements 1" is a constraint on the schema and 'when' is checked on
the conceptual data tree. You can safely implement the desired logic
this way:

  must "not(y<=1) or count(x)>=1";
  leaf-list x {
    type int32;
    min-elements 0;
  }
  leaf y {
    type int32;
  }

Then <y>2</y> will be valid but <y>1</y> won't, although both documents
are valid according to the schema (step 1).

It's the same as with other languages: lexical, syntactic and semantic
analyses are independent steps, because otherwise you can't reliably
cope with the complexity.

Lada 

> 
> 
> 
> /martin
> _______________________________________________
> netmod mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/netmod

-- 
Ladislav Lhotka, CESNET
PGP Key ID: E74E8C0C

---

From: Andy Bierman <[email-masked]>
Date: Wed, 02 Dec 2009 02:38:02 -0800

> rather make recurisive when expressions illegal.

You can't do this.
It is too difficult to check for these
perfectly legal XPath expressions
that happen to do 'the wrong thing'
from a data modeling perspective.

> conditions for a sparse augmentation.

The 'when' and 'if-feature' statements combine
to form an intensely complex implementation
requirement.  So what?  Nobody said implementing
YANG would be easy.

There is no way (or need) to limit the combination of 'upstream'
constraints (via uses, augment) with the 'downstream'
constraints (leaf, container, etc.).

> regardless of the 'when' statement?  So this instance doc will fail:

If 'when' and/or 'if-feature' is false,
then the node doesn't exist -- it doesn't count
towards the existence tests of its siblings or ancestors.

> /martin

Andy

---

From: Ladislav Lhotka <[email-masked]>
Date: Wed, 02 Dec 2009 13:19:32 +0100

> requirement.  So what?  Nobody said implementing

But it should at least be based on sound principles, or we will find
ourselves writing a new "Lessons learned ..." draft after few more
years. YANG is said to be simple but the fact is that it is now so
complex that its "grammars" cannot be even classified within the Chomsky
hierarchy - and we don't care?

XSD was carefully designed to produce context-free grammars. It turned
out it couldn't handle arbitrary order of children. RELAX NG can handle
this very well because it is based on the theory of hedge automata.

In both cases, it has been mathematically proven that there is an
algorithm for checking instance membership (validity). We can't hope to
do this for YANG, so I am extremely cautious about all "powerful" and
"flexible" features that move too far away from the established models.

Lada

-- 
Ladislav Lhotka, CESNET
PGP Key ID: E74E8C0C

---

From: Juergen Schoenwaelder <[email-masked]>
Date: Wed, 2 Dec 2009 13:24:38 +0100

On Wed, Dec 02, 2009 at 01:19:32PM +0100, Ladislav Lhotka wrote:
> Andy Bierman p????e v St 02. 12. 2009 v 02:38 -0800:

Please provide evidence.

> "flexible" features that move too far away from the established models.

It will help me a lot if you can write up a clear email providing
evidence (e.g. by presenting a valid example) that it is not decidable
whether an instance document is valid or not.

/js

---

From: Ladislav Lhotka <[email-masked]>
Date: Wed, 02 Dec 2009 13:46:10 +0100

> > hierarchy - and we don't care?

Even the most general - type 0 - grammar only knows about terminals,
non-terminals and production rules, there are no conditionals. You can
implement very limited context sensitivity like this:

<foo> ::= 1<x> | 2

and the same can be done in XSD and RELAX NG. What 'when' in YANG
attempts to do is

<foo> ::= if "y<=1" then <y><x> else <y> 

> whether an instance document is valid or not.

I started this thread by providing such an example. Is the document
containing neither <foo> nor <bar> valid or not?

Lada

-- 
Ladislav Lhotka, CESNET
PGP Key ID: E74E8C0C

---

From: "Bert (IETF) Wijnen" <[email-masked]>
Date: Wed, 02 Dec 2009 13:49:56 +0100

> requirement.  So what?  Nobody said implementing
Statements like the above make me worried!!!!
That was not what we set out to do was it?

Bert

---

From: Martin Bjorklund <[email-masked]>
Date: Wed, 02 Dec 2009 14:10:29 +0100 (CET)

> <foo> ::= if "y<=1" then <y><x> else <y> 

But you provided an equivalent must expression which you were happy
with.

In my view, the schema is fixed, and the when (and must) expressions
specify constraints on content (instance documents).

The difference between when and must is when/how they are enforced.

> containing neither <foo> nor <bar> valid or not?

Yes it is valid.  when expressions are not evaluated for nodes that do
not exist.

The problem with your example is that is had both 'when' and
'default', and in your step 2 you added the default values to the tree
and then evaluated the when expression for these leafs - but they were
not there from the start, so you should not evaluate their when
expressions.

Maybe we should not allow default and when at the same time.
Otherwise we'd have to interpret this as a conditional default, and I
think that would be too complicated.  (i.e. if the node is not there
and its when expression is true, then the default value applies; but
if it is not there and its when expression is false, then the default
doesn't apply either).

/martin

---

From: Ladislav Lhotka <[email-masked]>
Date: Wed, 02 Dec 2009 15:00:33 +0100

> But you provided an equivalent must expression which you were happy

No, the 'must' expression has nothing to do with the grammar, it is only
a semantic rule that the conceptual data tree is checked against.

> specify constraints on content (instance documents).

But there are grammatic (syntactic) constraints and semantic
constraints. 'when' mixes them together.

> Yes it is valid.  when expressions are not evaluated for nodes that do

So what is in the reply to <get-config> if with-defaults is set to
"report-all"? If nothing, both 'when' expressions in the data model
evaluate as true, so both nodes are valid and their defaults should
apply, which however makes the 'when' expressions false.

> if it is not there and its when expression is false, then the default

The same problem is with 'mandatory':

leaf foo {
    mandatory true;
    when "not(bar)";
    ...
}
leaf bar {
    mandatory true;
    when "not(foo)";
    ...
}

Again, this looks trivial, but the same logic can be buried deeply in
XPath expressions and more nodes may be involved.

And forbidding 'when' as a sibling of 'default' also doesn't help:

container superfoo {
    when "not(../superbar/bar = 1)";
    leaf foo {
        type uint8;
        default 42;
    }
}
container superbar {
    when "not(../superfoo/foo = 42)";
    leaf bar {
        type uint8;
        default 1;
    }
}

If there is neither <superfoo> nor <superbar>, we have the same problem
as before.

Lada

-- 
Ladislav Lhotka, CESNET
PGP Key ID: E74E8C0C

---

From: Martin Bjorklund <[email-masked]>
Date: Wed, 02 Dec 2009 15:08:45 +0100 (CET)

> constraints. 'when' mixes them together.

Why do you think it does?  Why can't you view when as providing
semantic constraints like must?

> The same problem is with 'mandatory':

And you get the same problem with s/when/must/g above.

/martin

---

From: Juergen Schoenwaelder <[email-masked]>
Date: Wed, 2 Dec 2009 15:16:49 +0100

> That was not what we set out to do was it?

I suggest to ignore the statement. Every data modeling language allows
to write down data models that can't be implemented. This is not a new
feature invented by YANG.

/js

---

From: Juergen Schoenwaelder <[email-masked]>
Date: Wed, 2 Dec 2009 15:30:51 +0100

> <foo> ::= if "y<=1" then <y><x> else <y> 

I know what a type 0 grammar is, still I can't follow.
 
> containing neither <foo> nor <bar> valid or not?

So I guess you mean this one:

leaf foo {
    type uint8;
    default 42;
    when "not(../bar=1)";
}
leaf bar {
    type uint8;
    default 1;
    when "not(../foo=42)";
}

The _grammar_ for the XML instance document is pretty clear I would
say. Neither the semantics in the when clauses nor the instance
document change the _grammar_.

Your other question is whether both <foo/> and <bar/> can exist.  Yes,
I think this is possible and this would be a valid instance:

<foo>0</foo>
<bar>0</bar>

Your question was about what happens if there are no explicit values
and the default statements kick in. In that case, you run into a
_semantic_ contradiction but _not_ into a grammar contradiction.
Hence, I fail to see the link to Chomsky language hierarchies. And for
what its worth, this example can be written without a when statement:

leaf foo {
    type uint8;
    default 42;
    description "this leaf exists only when bar != 1";
}
leaf bar {
    type uint8;
    default 1;
    description "this leaf exists only when foo != 42";
}

I see no change in the Chomsky hierarchy between these two versions of
the example. Both examples simply show the same modeling error.

/js

---

From: Ladislav Lhotka <[email-masked]>
Date: Wed, 02 Dec 2009 15:34:18 +0100

> semantic constraints like must?

This is what I tried to suggest by checking them after doing
(independently) the grammar validation and applying the defaults.
Your example with list ordinality indicates that the purpose of 'when'
is to take effect at the same time as the grammar.
  
> And you get the same problem with s/when/must/g above.

No, I don't, because I can never end up in a deadlock. A document
without <foo> and/or <bar> is gramatically invalid and document with
both of them is semantically invalid. So the module is broken but it
will not make my device cycle forever.

Lada

-- 
Ladislav Lhotka, CESNET
PGP Key ID: E74E8C0C

---

From: Ladislav Lhotka <[email-masked]>
Date: Wed, 02 Dec 2009 16:29:41 +0100

> I know what a type 0 grammar is, still I can't follow.

The rule like the last one is not type 0 production rule.
Consider this:

leaf y {
    type unit32;
}
leaf x {
    mandatory true;
    type int32;
    when "../y<=1";
}

A true grammar rule can only say that x is mandatory. So <y>2</y> will
be grammatically invalid, no matter what the semantic rule says.

> document change the _grammar_.

If I understand what 'when' is supposed to do in YANG, the grammar -
ordinality of nodes - is not fully determined without knowing the uint8
values in a particular instance. In particular, if 'when' is a
substatement of 'uses', then clearly the grouping may or may not
contribute new nodes, depending on the result of an XPath expression.

But if we agree that it is not the case - that the grammar simply says
that both nodes are optional in this example - then it is exactly what I
suggested: the grammar is determined first, the instance document
validated against it, defaults are applied and only then the semantic
'when' rules are checked.

Lada

-- 
Ladislav Lhotka, CESNET
PGP Key ID: E74E8C0C

---

From: Juergen Schoenwaelder <[email-masked]>
Date: Wed, 2 Dec 2009 17:20:01 +0100

On Wed, Dec 02, 2009 at 04:29:41PM +0100, Ladislav Lhotka wrote:
> Juergen Schoenwaelder p????e v St 02. 12. 2009 v 15:30 +0100:

You seem to be trying to translate semantic contraints down into
grammar, which generally does not work. Even in languages like C, I
can write

  int i = 1 / 0;

and this does not violate the grammar. Semantically, this is broken
and some compilers catch this (gcc by default emits a warning, not a
parse error).

> 'when' rules are checked.

Can we agree on this: The 'when' and 'must' statements do not affect
the grammar - they are semantic constraints. A valid document needs to
satisfy the grammar constraints and the semantic constraints.

For me, having agreement on this would also be sufficient - I do not
think we need to spell out how and which conflicts or inconsistencies
have to be detected at compile time and which ones at run time.

/js

---

From: Andy Bierman <[email-masked]>
Date: Wed, 02 Dec 2009 08:23:08 -0800

> That was not what we set out to do was it?

There are lots of loops to detect, but they are
the responsibility of the compiler.  Since 'when'
expression evaluation depends on the database values
at run-time, the server has to detect these loops.

Of course, none of YANG has to be implemented
in an automated fashion in the central stack.
The draft has some text explaining
how a server doesn't really need XPath.
(It just needs to implement the behavior of
specific data nodes in YANG modules.)

In this case the complexity is obvious isn't it?
In order to find out if /x is allowed, the
values in the XPath expression need to be retrieved.
In order to retrieve the value, the server first
has to make sure the 'when' condition is met,
so those values have to retrieved first.

It could be challenging for an implementation
to ever decide either /x or /y is allowed to exist.
Using must-stmt like loop detection, the expression
will always be false (because breaking the loop
looks the same as if the node does not exist).

Andy

---

From: Ladislav Lhotka <[email-masked]>
Date: Wed, 02 Dec 2009 17:56:29 +0100

> You seem to be trying to translate semantic contraints down into

How did you come to this conclusion? I think exactly the opposite is
true. As you say below: 'when' statement does not affect the grammar, so
node "x" is mandatory and the document <y>2</y> is not grammatically
correct because <x> is missing. But this is what Martin protested
against. It would be useful to clarify our positions on this example.
Martin?
 
> satisfy the grammar constraints and the semantic constraints.

Yes, we are in a perfect agreement here. :-) In any case, this is how
the DSDL mapping works - grammar translates to RELAX NG, 'must' and
'when' to Schematron.

Lada

-- 
Ladislav Lhotka, CESNET
PGP Key ID: E74E8C0C

---

From: Martin Bjorklund <[email-masked]>
Date: Wed, 02 Dec 2009 18:42:06 +0100 (CET)

Ladislav Lhotka <[email-masked]> wrote:
> How did you come to this conclusion?

That's also how I read your arguments, and what I (thought I) protested
against. 

> I think exactly the opposite is

I also agree.  I do not want the when statement to affect the grammar.

/martin

---

From: Andy Bierman <[email-masked]>
Date: Wed, 02 Dec 2009 11:14:52 -0800

> It should not fail, since when y > 1, no x should exist.  When y <= 1,

This is part of the validation sequence done for
edit-config on running, or commit of the candidate.
As such, these outcome should be predictable.

One implementation strategy (YMMV):

 1 - server deletes all the nodes that have false 'when' results
     (e.g., go through all the nodes with 'when-stmts' and keep
     doing it until no nodes at all are deleted in the loop.
     Avoids deadlock due to XPath cross-references completely.)
 2 - server verifies mandatory and other constraints on the
     nodes that are left

Another way of looking at it -- go ahead and create /x entries,
but if you don't get /y right before the commit, the server
will delete all the /x entries and not commit them.

The same logic applies to when+default.
Even if the server creates the default in the candidate,
it will get deleted in the commit if the when expression
is false.

Andy