Comparing nodes and the order of features

[ftomassetti]

Today I ran into an issue when comparison two Serialization Chunk. The problem was that the two chunks were equivalent, with the only difference being the order of features. In our serialization format we have JSON Objects. Even if we do not dictate a specific order for the keys, still we can perform a comparison using some JSON libraries. However when we have lists, like its the case for containments, properties, and references then the libraries would expect the order of such elements to be meaningful, while for us it is not. So this means that we need to create LionWeb specific comparison routines. Doable, but slightly inconvenient for users and a bit of extra work for us.

We could consider:

• Using a specific order for listing features
• Using objects instead of lists when ordering has no meaning (e.g., use the meta-pointer as a key)

Alternatively, we should consider providing facilities to compare serialization chunks in our libraries.

[ftomassetti]

Also the order of nodes could be specified or the nodes list could become an object, using IDs as keys

[joswarmer]

The spec states that the order in a list is important, because there are numerous cases where it is. As a result lists where the order is not significant are handled in the same way.

One way of solving this is to specify in the meta-model whether a list is ordered or not. This way a language may contain both ordered and unordered lists in different concepts.

This would mean to add a property (un)ordered to Link in the meta-model, which should probably default to "ordered". In a typical language the list of Features could them be unordered, while the list of Statements inside a function can be ordered.

[joswarmer]

Also see https://github.com/LionWeb-io/specification/issues/4

[joswarmer]

Problem with adding the ordered property is that it becomes hard (if not impossible) to compare two Serialization Chunks without knowing the language, because the ordered value is needed to perform the correct comparison.

Another possible solution is to sort the features in both chunk before comparing, this would need no change to the specification.

[ftomassetti]

I think supporting ordered may be a bit more complex, but an immediate problem we have that we can solve without introducing ordered is the serialization of the feature values, i.e., the order in which we put stuff into properties, containments, references.

Note that I am not referring to the values of the features, but the order of the features itself.

For example, now this snippet can be serialized in two equivalent ways:

            "references": [
                {
                    "reference": {
                        "language": "com_strumenta_starlasu",
                        "version": "1",
                        "key": "com_strumenta_starlasu-ASTNode-originalNode-key"
                    },
                    "targets": []
                },
                {
                    "reference": {
                        "language": "com_strumenta_starlasu",
                        "version": "1",
                        "key": "com_strumenta_starlasu-ASTNode-transpiledNode-key"
                    },
                    "targets": []
                }
            ],

or:

            "references": [
                {
                    "reference": {
                        "language": "com_strumenta_starlasu",
                        "version": "1",
                        "key": "com_strumenta_starlasu-ASTNode-transpiledNode-key"
                    },
                    "targets": []
                },
                {
                    "reference": {
                        "language": "com_strumenta_starlasu",
                        "version": "1",
                        "key": "com_strumenta_starlasu-ASTNode-originalNode-key"
                    },
                    "targets": []
                }
            ],

Perhaps we could specify this may depend on the order in which features are declared in the concept, and we should also define an order for inherited features. Or we could sort them alphabetically

[enikao]

See also #156, still open

[dslmeinte]

I strongly feel that the slight inconvenience of having —what's essentially— an equivalence relation on serialization chunks (which indeed requires a bit of extra code to check whether two serialized nodes are equal modulo order of serialized features, and by extension, whether two serialization are equal modulo order of serialized features per serialized node, and modulo order of serialized nodes) outweighs any “marking” mechanism that can only befined on a level above that of serialization.