We started with the implementation and get stuck with the algorithm to walk the model. Let me recall your advice from Dec 20.
george wrote:One is to walk the model and determine the elements (you should take into account in this case also substitution groups) and the other is to try to validate the element content trying to insert each possible element as a subelement.
I will demonstrate the troubles on an example. Consider the element 'TheFeature' that can contain subelements F1, F2, F3, F4 while only only 2 or 3 of these subelements can be contained in the 'TheFeature'. The legal content thus can be e.g. <TheFeature><F1/><F2/></TheFeature> of <TheFeature><F1/><F3/><F4/></TheFeature> but not <TheFeature><F1/></TheFeature>, <TheFeature><F1/><F2/><F3/><F4/></TheFeature> or <TheFeature><F1/><F1/><F1/></TheFeature>.
The XML Schema that enforces this constraints is at http://control.ee.ethz.ch/~rohliko/xml/2-3of4.xsd
and below is the graphical representation of the 'TheFeature'):
The group 'problemativgroup' is fairly complex but it is the only way we can express the constraint described above. Note that this schema is automaticaly genereted from the feature model using XSL program. This is why there are some relics like those in light yellow color.
Now, the problem
: Say, the user is in the middle of editing. He already has <TheFeature><F2/><F3/>
</TheFeature>. When right-clicking the 'TheFeature' box in our tool we want to offer to the user all legal subfeatures -- in this case the F1
marked in blue and F4
marked in green.
We tried the both advices we have got. The second one 'try to validate the element content trying to insert each possible element as a subelement
' would work for this particular case but not generaly. If, for example, it is necessary to add at least to subelements (say F1 and F0) to have the TheFeature valid (this assumes aditional subelement F0 defined in the schema) then after trying to add possible subelement F1 the 'TheFeature' is still not valid (required F0 is still missing).
The first advice i.e. walk the model and determine the elements
is the one we expect to work fine, especially since we do not have any subtitution groups. However we failed to find out the algorithm to do so. More precisely out of the four ideas we have only the 'brute force' algoritm seems to work.
The brute force algorithm should work like this:
1) Generate ALL possible combinations of subelements bu recursively traversing the particles in schema model (in our simple XSD it is (F1, F2), (F1, F3), (F1, F4), (F2, F3), (F2, F4), (F3, F4), (F1, F2, F3), (F1, F2, F4), (F1, F3, F4), (F2, F3, F4)).
2) Look for those combination that contain all subelements already in the edited XML document (F2 and F3) and note subelements that can extend the current content of the element (of element 'TheFeature').
3) Make union of those noted subelements. This gives F1 and F4.
Clearly, the fact the we have to generate all the combinations is ill. Just consider the complexity of the same example extended to select three, four or five elements out of seven instead of out 2 - 3 elements out of 4 -- (to have an idea of how this can look like you mau have a look at http://control.ee.ethz.ch/~rohliko/xml/3-5of7.png
). The have to be more elegant solution. First prove of this: the code completion in Oxygen is very fast. Second prove: The authors of XML Schema are people that had in mind the issue of schema validation and (surely) designed the XML Schema in such a way that even the structures like the one we have can be analyzed easily.
Would you be so kind and point us to right direction to go?
Thank you very much,