Optional break (.) does not work properly, in contexts other than sequential ones

[AndreVanDelft]

Tolya mailed:

'.' operator functions not exactly the way it is supposed to. Basically, if you write: a & . & b & c, then 'c' will never be activated. That is, the process will go the following way:

1. Activate '&'
2. Activate 'a'
3. Activate '.'
4. Stop activation
5. Start 'a'
6. Activate 'b'
7. Start 'b'

The way it should go: ...

6. Activate 'b'
7. Activate 'c'
8. Start 'b' ...

[anatoliykmetyuk]

The nature of the issue is composite: it is composed of 2 parts:

1. Activation doesn't resume after (valid) AA have started. That means, only Activation message for the next node is inserted. The valid way of doing things is to insert both Activation message for the next node and Continuation message for the current n-ary operator.
2. Optional break "reacts" to every AAStarted message that comes through the n-ary operator, but it should react only to the message that passed also through the child node activated right before the correspondent break node was activated

What I propose in my commit:

1. In handleContinuation() method, insert continuation message unconditionally if there's a permission to activate next node:

if (activateNext) {
  val t = message.node.template.children(nextActivationTemplateIndex)
  activateFrom(message.node, t, Some(nextActivationPass))
  val activation = if (message.activation != null) message.activation else
                           Activation(message.node)

  val nary_op_isLeftMerge = n match {
    case nary@N_n_ary_op (t: T_n_ary, isLeftMerge) => isLeftMerge case _ => false
  }
  if (!nary_op_isLeftMerge) insertContinuation(activation, n)
}

2. 2.1. CallGraphTreeNode_n_ary node will now be aware of a node who's start must wake it from a break in case if it is in a state of break:

var breakWaker: CallGraphNodeTrait = null 

2.2. breakWaker will be filled on node connection to the graph like this:

def connect(parentNode: CallGraphParentNodeTrait, childNode: CallGraphTreeNode) {
    childNode.parent = parentNode
    childNode.scriptExecutor = parentNode.scriptExecutor
    parentNode.children.append(childNode)

    parentNode match {
      case p: CallGraphTreeNode_n_ary =>
        childNode match {case N_break(_) | N_optional_break(_) | N_optional_break_loop(_) => p.breakWaker = p.lastActivatedChild case _ =>}
        p.lastActivatedChild = childNode

      case _ =>
    }
  }

2.3. When a node receives AAStarted, it will check if it is a breakWaker for it's parent n-ary operator; if so - set correspondent flag in it. In handleAAStarted():

 val operator = message.node.n_ary_op_ancestor
 if (operator != null && (operator.breakWaker eq message.node)) operator.aaStartedSinceLastOptionalBreak = true

[AndreVanDelft]

I have merged the pull request, but I think the issue has not yet been solved well. But first I should write down carefully what the optional break really must do.

2.1. CallGraphTreeNode_n_ary node will now be aware of a node who's start must wake it from a break in case if it is in a state of break:

var breakWaker: CallGraphNodeTrait = null

I think something like this could indeed be needed, but possibly a bit different.

2.2. breakWaker will be filled on node connection to the graph like this:

def connect(parentNode: CallGraphParentNodeTrait, childNode: CallGraphTreeNode) { ... } This goes wrong... As a principle, the basic graph operations "connect" and "disconnect" should do just that, and (Ok) set the scriptExecutor. Don't inspect the child node, because you will not cover all cases. E.g.,

x / (if (i==0) . else .) / y

should behave equivalently to

x / . / y

Such cases will not be covered by the child inspection in connect().

So some rules and ideas:

1. .. behaves like . , apart from the fact that it turns the ancestor nary-operator into an iteration. So we do not need to define other aspects of the behaviour of ..; just . would be enough.
2. / behaves like both || and +: logically it is or-like (as both || and + do) when the left LHS successfully the RHS is terminated (like with ||) when an atomic action starts in the RHS then the LHS is terminated (like with +).
3. . & x should mean: 0 or more x's. Initially . should be activated and then x (in the continuation). x & . should mean: 1 or more x's. Initially x should be activated and then . (in the continuation). Note: . & x must initially have a success.
4. We want to describe behaviour of the kind x & . & y (More general also forms such as: x1 & x2 & x3 & . y1 & y2 &y3. The point is that the dot is somewhere in the middle). Filling in for x or y the neutral operand (here (+) which is the "1") yields (+) & . & y and x & . & (+), which should be equivalent to the forms of point 3.

So x & . & y does: activate x and . (partially in the continuation); if any atomic action had been activated in x then further activation of y will only continue when for the first time an atomic action in x starts; else further activation of y happens anyway. such a group of x operands in which an atomic action has been activated but not yet started is FTTB called an optional operand group. according the logical and-behavior the &-node has success when all its operands have success. However, for this requirement the operands in any optional operand group are not considered &&, |, || and / are much likewise. Note that the optional operand group issue is not relevant in the context of |, ||, /.

I think this sums it all up quite well. Only: this is just functional requirements. The implementation requires some administration. I would think that the optional operand group should be marked by keeping track of a child node index. Also I think that it requires a count of child nodes in the optional operand group that have a recent success, and a count for the unsuccessfully terminated children therein.

What do you think?

[anatoliykmetyuk]

I agree on the point that this implementation won't cover the case when optional break node is indirect child of n-ary operator, like in case with if-else. Indeed, this should be improved.

I think, we need to compose a formal definition of what"." should do. Use cases are good for understanding of the matter, but before implementation a concise formal definition should be composed. For example, it's not very clear why ". & x" and "x & ." should behave in a special way. ". & x" will normally cause a deadlock, because the activation will stop after "." and never resume. That's why, I think, a proper definition should be generated from all the use cases you've provided.

[AndreVanDelft]

". & x" will normally cause a deadlock, because the activation will stop after "." and never resume. That is what the current implementation does, but we need to fix that.

I think the informal description that I gave 2 days ago should be more or less clear. A formal definition would resemble the VM internals very much, IMO; FTTB I would not know a concise suitable formalism.

Another way of defining the behaviour would be the kind of transition rules that are present in the unit test OperatorsSuite.scala. Currently these test scripts defined by strings; a limitation is that the tested operators have only 3 operands at most. This is not enough to test the behaviour of the optional break in a parallel context. As soon as we have script lambdas we will be able to specifiy the test scripts more conveniently.

[anatoliykmetyuk]

So the constraints are:

1. Break may be an indirect child of an n-ary node
2. Break may be the first node activated; in this case it makes no effect

If the nodes' children collection is ordered in order of their activation, then we can do the following: once a break node is activated, it seeks its n-ary node parent (maybe, indirect), then it sets this node's "breakWaker" node to the second child from the tail: this way, the node, activated before the lastActivatedNode will be set to the "breakWaker". If there's no such node, this means that break node is a very first node activated and, hence, we shouldn't actually send the "break" message. This will work in case of ". & x" and "x & if (true) . else .". What do you think about this implementation?

[AndreVanDelft]

I am not sure. Some more constraints:

• the solution should work for each parallel operator and for /
• for and-parallel operators the logic behavior will need special attention
• references to nodes such as a "breakWaker" should be done in terms of the node index; this way you can easily see whether a child node older or newer
• the behavior should (probably) match the following tests:

< a / . / b >        -> "a"
< a b / . / c d >    -> "->a a->bc  ab     ac->d  acd"
< a b & . & c d >    -> "->a a->bc  ab->1c ac->bd abc->d  abcd acb->d  acd->b  acbd acdb"
< a b | . | c d >    -> "->a a->bc  ab->1c ac->bd abc->1d abcd acb->1d acd->1b acbd acdb"
< . / a b >          -> "->1a a->b  ab"
< . & a b >          -> "->1a a->b  ab"
< . | a b >          -> "->1a a->b  ab"
< . / a b . / c d >  -> "->1a a->bc ab ac->d acd"

These tests still need to be included in OperatorsSuite.scala.

[anatoliykmetyuk]

We can't do the references to breakWaker in terms of node index, because graph constantly changes dynamically. In different times one node can have different indexes. For example

1. A activated (index 0)
2. B activated (index 1)
3. A deactivated Now B have index 0.

Have you managed to run the OperatorsSuite? Or maybe it's better to wait until script lambdas are implemented before relying on it? Anyway, I'll try to implement and try out the enhanced version of "." in nearest time.

[AndreVanDelft]

Yes/no, we can use the node index! I mean the field CallGraphNodeTrait.index. I have not proceeded with OperatorsSuite yet. The reason why the lambda's would be needed is that the current suite only supports expressions of up to 3 operands.

[AndreVanDelft]

A few more test cases:

< a b  | .  | 1 >    -> "->a a->1b ab"
< a b || . || 1 >    -> "a"
< a b  & .  & 0 >    -> "ab0"
< a b && . && 0 >    -> "a0"

[AndreVanDelft]

CallGraphTreeNode_n_ary has -among others- the following fields:

• activationMode
• lastActivatedChild
• aaStartedSinceLastOptionalBreak
• aChildEndedInFailure
• rightmostChildThatEndedInSuccess_index (and def aChildEndedInSuccess = rightmostChildThatEndedInSuccess_index>=0)

Some of these are needed to determine when an n-ary node has success. Now that we are implementing optional break it seems time to reconsider such fields. Take

x & . & y . & z

Suppose x and y have been activated; inside y at least one Atomic Action has been activated but none have happened yet (see this issue: https://github.com/AndreVanDelft/scala/issues/5), so activation has essentially been paused at the seconde ".". To see whether the expression so far has success, we need to consider x.

y is optional here. Now one child in y may have ended already without success, like 0. Should this prevent the &-node to have success? The easiest thing is to say: yes; then we can just keep the algorithm with aChildEndedInFailure. ScriptExecutor has the following code:

T_n_ary_op.getLogicalKind(n.template.kind) match {
  case LogicalKind.None =>
  case LogicalKind.And  => shouldSucceed = (isSequential || !n.aChildEndedInFailure && !activateNext) &&
                                           n.children.forall((e:CallGraphNodeTrait)=>e.hasSuccess)
  case LogicalKind.Or   => shouldSucceed = n.aChildEndedInSuccess || 
                                           n.children.exists((e:CallGraphNodeTrait)=>e.hasSuccess)

Here the forall and exists loops should be limited to the "x" part of the example, so stop when the index of the first optional break has been reached.

The "y" part is not optional (any more) if either:

• no atomic actions in y had been activated
• any atomic action in y has happened

Then the "z" part should be activated.

Let's call the elements of y the "optional children" of the n-ary operator. Then keep the following indexes:

• firstOptionalChild_index
• lastOptionalBreak_index

(two indexes are needed, and indexes work much better than a pointer such as breakWaker: you can immediately compare ages and there is no memory leak).

So when an atomic action happens somewhere down a child with index >= firstOptionalChild_index, then y should stop being optional; activation should be taken up from lastOptionalBreak_index (in case there was another optional break, i.e. index >= 0) etc. This is not trivial, since we should also be able to deal with x & . & y etc.

[anatoliykmetyuk]

First of all, we should make the nature of x, y and z more clear in your example. In its current implementation, SubScript allows almost every valid graph node to be substituted in place of x, y, or z. And, if some of y's children have ended without success, this doesn't mean that '&' shouldn't also have success: consider y = a || (-), for example. Here, (-) won't end with success, yet I can't see any reasons to make '&' in x & . & y & . & z also end without success, because 'y' will end with success. We should infer success of n-ary nodes only based on their direct children success, we shouldn't look deeper into the graph, because this is the job of the children by themselves.

So basically, what needs to be done is make "." break only if there was something activated before "." or its indirect parent was activated? For instance, if "." or its parent is the first node activated under the n-ary operator, this n-ary operator should just ignore the break; otherwise it should act as usual?

[AndreVanDelft]

With x, y and z I mean any group of operands of the n-ary operator, that do not contain "." etc.

So in a & b & . & (c+d) & {} & "." & e f the roles are:

x = a & b
y = (c+d) & {} 
z = e f

However, you should bear in mind that the ampersands symbols all belong to 1 n-ary operator. So you should regard these x, y, z in this context as a kind of C-style macro's.

"." only breaks the activations if "recently" children to the left hand side had been activated, and during these activations at least 1 atomic actions had been activated. Activation from such a break only continues if for the first time one of such atomic actions has happened.

When "." does not break activations, it still has impact: the part to the right of it becomes optional.

I think the following fields in N_n_ary_op would be sufficient to determine succes:

var nActivatedChildren (i.e. including the number of already deactivated children)
var nActivatedChildrenWithRecentSuccess
def nActivatedChildrenWithoutRecentSuccess = nActivatedChildren - nActivatedChildrenWithRecentSuccess
var nActivatedOptionalChildren
var nActivatedOptionalChildrenWithRecentSuccess
def nActivatedOptionalChildrenWithoutRecentSuccess = ... - ...
def nActivatedMandatoryChildren = nActivatedChildren - nActivatedOptionalChildren
def nActivatedMandatoryChildrenWithRecentSuccess = ... - ...
def nActivatedMandatoryChildrenWithoutRecentSuccess = ... - ...

The 4 variables will be easy to maintain.

Then And-like operators have success when nActivatedMandatoryChildrenWithoutRecentSuccess = 0, or, maybe better, when nActivatedMandatoryChildrenWithoutRecentSuccess = 0 & nDeactivatedChildrenWithoutRecentSuccess = 0

Or-like operators have success when nActivatedMandatoryChildrenWithRecentSuccess > 0 or, maybe better, when nActivatedChildrenWithRecentSuccess > 0

[AndreVanDelft]

I improved the working of the ScriptExecutor. [ a b / . / c d ] now works well; this implies that x/.. also probably works well. This is important for the Actor demonstration.

However, it was quite hard for me to get this far. ScriptExecutor.handleContinuation has become very messy again. I had to comment out the following tests in OperatorsSuite:

[ . / a b ]               -> "->1a a->b  ab"
[ . | a b ]               -> "->1a a->b  ab"
[ . / a b / . / c d ]     -> "->1a a->bc ab ac->d acd"
[ a b  | .  | (+) ]       -> "->a a->1b ab"
[ a b || . || (+) ]       -> "->a a"
[ a b  & .  & (-) ]       -> "->a a->b ab->0"   does ab
[ a b && . && (-) ]       -> "->a a->0"
[ (a b+(+))  & .  & (-) ] -> "->1a a->b ab->0"
[ (a b+(+)) && . && (-) ] -> "->1a a->0"

This all needs to be resolved once, but we can leave it like this FTTB.

[anatoliykmetyuk]

Ok, I'll try that on actors as soon as I have time. we shouldn't comment tests, we just should fail them (if they compile of course).

[AndreVanDelft]

I have mixed opinions about the not-commenting. Indeed these test cases should in principle stay in the suite. However, I have now 1 single list of test cases which are processed in 1 test method. This means JUnit stops processing after the first test case fails. That is not what I want: I want at least the well performing tests to run, to see whether there is regression.

A solution would be to make a separate test method for each test case, but that would make things unpractical. IMO the specifications should be as easy as one can think of; not only for test cases BTW. So if we want to resolve the sitiuation we should find a real solution.

• maybe JUnit has already a solution for this. If we find that we could take it
• we could write our own extension to JUnit, but that would be overkill
• we could annotate the failing tests, e.g.,

[ . / a b ]               -> "FAIL: ->1a a->b  ab"
[ . | a b ]               -> "FAIL: ->1a a->b  ab"
[ . / a b / . / c d ]     -> "FAIL: ->1a a->bc ab FAIL: ac->d acd"

Then running such annotated tests would make an inverse assumption. Normally such tests don't run well, and JUnit will not complain. That is fine, because we already know that there are problems. As soon as such an annotated test case runs well, JUnit will report failure; that would be a notification that an error has been resolved. We then simply deal with it by removing the "FAIL:" annotation, and (possibly) by shortening the issue list. I am happy with this solution; I will implement this soon.