Franca IDL validation should disallow cyclic dependencies

[GoogleCodeExporter]

Currently, the built-in validation of Franca IDL does only some basic checks 
regarding cyclic dependencies. E.g., it is checked that no struct definition 
will contain itself as a struct element. It is also checked that an interface 
doesn't inherit directly or indirectly from itself.

However, these checks are not complete yet. There should be a more generic 
cycle check on a unified dependency graph. For example, the following code 
should be marked as error by the built-in validator.

struct S {
   T t
}
struct T extends S { }

I would assume that the dependency graph for interface inheritance can be 
checked separately from the dependency graph for data types, but this has to be 
confirmed yet.

Original issue reported on code.google.com by klaus.birken@gmail.com on 7 May 2013 at 1:21

[GoogleCodeExporter]

Implementation notes:
- The correct location for this is plugin org.franca.core.dsl, package 
org.franca.core.dsl.validation. The checks should be called from the 
FrancaIDLJavaValidator, but the actual algorithms should be placed in a 
separate file (DependencyCycleChecker). Both Java or xtend would be ok. See 
existing ContractValidator, which is a blueprint for this kind of separation.

- There is a utility in plugin org.franca.core, package 
org.franca.core.utils.digraph. This is a generic graph implementation which 
also provides a topological sort (which will detect a cycle in the graph). This 
might be a good helper class to be used.

- There is some work being done on issue #7 (on the add ons branch), which also 
affects FrancaIDLJavaValidator. In order to avoid heavy merging, the work 
should be synchronized.

Original comment by klaus.birken@gmail.com on 7 May 2013 at 1:32

[GoogleCodeExporter]

As far as I as a newbie can see, there are 4 possible dependy-cycles

- enum: extends

- struct: type of member, extends
- typedef: is

- interface: extends

- union: extends

Did I miss something ?

Original comment by bonge...@gmail.com on 13 May 2013 at 2:41

[GoogleCodeExporter]

Original comment by bonge...@gmail.com on 13 May 2013 at 2:42

[GoogleCodeExporter]

I found some cycle cases (length n=2) based on various containment relations. 
See enclosed file. Each of them can be extended to be cycles of length n>2. 
There might be more such cases along this line of thinking. 

Original comment by klaus.birken@gmail.com on 13 May 2013 at 3:01

Attachments:

• cycles.fidl

[GoogleCodeExporter]

Original comment by klaus.birken@gmail.com on 15 May 2013 at 12:35

[GoogleCodeExporter]

This issue was closed by revision 15380ebd414d.

Original comment by bonge...@gmail.com on 3 Jun 2013 at 11:39

• Changed state: Fixed

[GoogleCodeExporter]

Fixed. Dependencies covered are:

FModel.interfaces
FModel.typeCollections

FInterface.base
FInterface.types

FTypeCollection.types

FArrayType.elementType.derived

FStructType.base
FStructType.elements.type.derived

FEnumerationType.base

FUnionType.base
FUnionType.elements.type.derived

FMapType.keyType
FMapType.valueType

Unit-Test is org.franca.core.dsl.tests.CyclicDependenciesValidationTests

Original comment by bonge...@gmail.com on 3 Jun 2013 at 11:49

[GoogleCodeExporter]

The cycle detection works well (though I did not test very deeply, yet).

Currently, the error markers are all placed at the top of the file (where the 
package declaration is). Would it be possible to put the error markers to the 
specific locations in the file, where the cycle actually occurs? This would it 
make much easier for the user to fix the cycles...

Original comment by klaus.birken@gmail.com on 11 Jul 2013 at 4:14

• Changed state: New

[GoogleCodeExporter]

Please confirm:
That means a cycle covering 5 artifacts results in 5 errors ... possibly 
covering multiple files.
Correct? 

Original comment by bonge...@gmail.com on 12 Jul 2013 at 12:07

[GoogleCodeExporter]

Diving deeper into this issue revealed some more aspects:
(1) Digraphs topological sort (which will detect a cycle in the graph) signals 
whether no cycle exists or not. Consider a model with two cycles: A->C, C->A 
and B->B. In that case the error message is "Cycle Detected: A->C, B->B, C->A". 
The cycles have to be split.

(2) The strategy "place marker at top of file" addresses the file/package where 
the validation starts. Think of a situation with two Files: FileA with a Cycle 
"A->A" and FileB with a ref to that cycle "B->A". In that case the validation 
of FileB results in a marker "Cycle A->A" detected.  The markup strategy has to 
consider the file.

Original comment by bonge...@gmail.com on 12 Jul 2013 at 1:52

[GoogleCodeExporter]

Regarding #9: Yes, each hop in the cycle should be marked, disregarding if its 
in several files or not. Ideally, Jump-to-definition can be used to jump 
through the cycle and decide how to resolve it. 

Original comment by klaus.birken@gmail.com on 16 Jul 2013 at 3:43

[GoogleCodeExporter]

Regarding comment #10: 

ad (1): Yes, each part of a cycle should be marked at the proper location. The 
optimal solution in the example would be:
   - the reference to C in A should be error-marked with "Cycle A=>C=>A"
   - the reference to A in C should be error-marked with "Cycle C=>A=>C"
   - the reference to B in B should be error-marked with "Cycle B=>B"

ad (2): In this example, the reference to A in B doesn't have to be marked at 
all (as B is not part of the cycle). 

If Digraph toposort doesn't support this kind of analysis, we either have to 
extend it or choose a different algorithm. I didn't look into details of cycle 
detection algorithms yet...

Original comment by klaus.birken@gmail.com on 16 Jul 2013 at 3:50

[GoogleCodeExporter]

This issue was closed by revision fabf14409c86.

Original comment by bonge...@gmail.com on 22 Jul 2013 at 11:42

• Changed state: Fixed

[GoogleCodeExporter]

NOTE: The fix revision fabf14409c86 covers a manual merge of 
"releng/org.franca.targetplatform/franca-juno.target" from master into 
dev_validator. The commit of that manual merge is 726f585.

Please ignore changes to to franca-juno.target when merging the fix into 
master-branch.

Original comment by bonge...@gmail.com on 22 Jul 2013 at 11:48

[GoogleCodeExporter]

added a (plugin-) unit-test: revision b2c8a7681a1c  

Original comment by bonge...@gmail.com on 22 Jul 2013 at 2:16