Home » Archived » EMF-IncQuery » IncQuery Explorer and Xtext resources
|
Re: IncQuery Explorer and Xtext resources [message #1415177 is a reply to message #1414880] |
Tue, 02 September 2014 08:58 |
Zoltan Ujhelyi Messages: 392 Registered: July 2015 |
Senior Member |
|
|
Hi Knut,
thanks for the comments, they are highlighting important issues in the documentation. In the following I try to answer step-by-step (first shortly, then adding some context into it):
0. We have removed the display parameter of the annotation as it was confusing, and we suggest to use the checked attribute instead.
----
I have updated the hover documentation to suggest the alternative usage. For some reason, we have forgotten to migrate (and update) the documentation page from http://incquery.net/node/129 to the Eclipse wiki (I guess this is where you found the description). I have opened bug https://bugs.eclipse.org/bugs/show_bug.cgi?id=443062 to track this.
----
1. Unfortunately, Xtext has this bug: https://bugs.eclipse.org/bugs/show_bug.cgi?id=387119 And as long as it has this bug, using Xtext resources in EMF-IncQuery is not a good idea (using the Reflective editor seems a feasible alternative to us).
----
In details: EMF-IncQuery promises that it works incrementally; in other words, the promise is when the queried model changes, the results are also automatically updated. Generally, this works for Xtext resources as well, however we have found a case when Xtext turns off change notifications as a performance optimization (https://bugs.eclipse.org/bugs/show_bug.cgi?id=387119) that can invalidate the query results. In this case, we have opted not to support direct queries over Xtext editors until this issue is handled, because it would not work as expected. On the other hand, this problem is probably worth a FAQ entry in the web.
----
2. Right now, general containment is not supported directly because of efficiency reasons. We plan to add it, but first, we have to provide support for it in the engine. Additionally, doing model traversal (e.g. containment traversal) makes it impossible to do incremental updates (as the engine does not know what model elements are relevant to the query).
As a workaround, we are designing an alternative search strategy (https://bugs.eclipse.org/bugs/show_bug.cgi?id=406073) that does not feature this limitation, but that is not yet really usable. After that feature works, we are planning to add support for containment hierarchies into the language as well.
----
In details:
Recursive containment is problematic because of incrementality - again... The problem here is, that EMF-IncQuery caches the partial results as well, so for the transitive containment hierarchy it has to maintain a cache that stores all direct and indirect containment edges (that is generally around O(n^2), where n is the number of nodes in the EMF model). Building and maintaining this cache requires big work. Finally, in our experience (e.g. with queries on source code models) we have found that the containment constraints one tends to formulate intuitively are often not necessary to put in the query - though this may not apply in your queries.
EObjects were banned from check expressions for safe incrementality as well. If we allow you to traverse the model in Java code within an eval(), we have no way for automatically updating your results when the model is changed. If you do not need your results to be updated, you can just write your query in Java; and you can still use IncQuery for those parts of the query that are easier to formulate in the pattern language, since it is easy to call and evaluate IncQuery from Java code.
----
Finally, I would like to thank again for your time to write this feedback, it is really appreciated. It helps to detect what is hard to find for new users.
Cheers,
Zoltán
PS.: Credits where credits due: some of these ideas linked above were by my collegue Gábor Bergmann (we merged our comments here).
|
|
|
Re: IncQuery Explorer and Xtext resources [message #1415671 is a reply to message #1415177] |
Wed, 03 September 2014 10:20 |
Knut Wannheden Messages: 298 Registered: July 2009 |
Senior Member |
|
|
Thank you very much for your detailed reply. I am also glad that you understood my comments as constructive feedback rather than any form of criticism. I really think EMF IncQuery seems like a great tool!
0. Thanks for the reference to http://incquery.net/node/129. Somehow I had until now mostly landed on the Eclipse wiki pages (https://wiki.eclipse.org/EMFIncQuery). How come there is two sources of the documentation and which one should be considered the "official"?
I had actually also noticed the "checked" parameter. But I only tried it with an eiq file in my workspace which I registered using the context action. There the "checked" parameter didn't have any effect, so I concluded that it probably meant something different.
1. OK. I understand the problem. But I wonder if the problem doesn't go even deeper than in the mentioned bug. Or would IncQuery behave as expected when the Xtext resource is edited and as a consequence its EMF model gets largely "thrown away" and rebuilt (rather than modifying the individual EObjects)?
Yes, I think an FAQ would probably make sense here, with a pointer to the sample reflective editor.
2. General containment support sounds like it would be nice to have. If the incrementality nature is part of the problem again, have you considered allowing to opt that out? At least in my case I am not really interested in that feature at the moment. I just want to match some patterns against a "static" model.
Since EMF models are trees I would rather have expected O(n*log(n)) direct and indirect containment edges. But I guess that can still be a lot.
Thanks for the hint that I can write these "predicates" in Java. I will certainly have a look at that.
Since you mention that you have experience with queries over source code models, I can outline a query problem that I am trying to solve with IncQuery. I would like to write a pattern which matches all types which can be seen as a subset of another (i.e. one type declares attributes (with name and type) which are a subset of those of the other type). I thought I would start with a pattern that takes two type input parameters:
pattern same_structure_intl(obj1, obj2) {
obj1 != obj2;
Type(obj1);
Type(obj2);
Type.attributes(obj1, attrs1);
Type.attributes(obj2, attrs2);
find same_structure_intl(attrs1, attrs2);
} or {
obj1 != obj2;
Attribute(obj1);
Attribute(obj2);
Attribute.name(obj1, name1);
Attribute.name(obj2, name2);
name1 == name2;
Attribute.domain(obj1, domain1);
Attribute.domain(obj2, domain2);
domain1 == domain2;
}
With this pattern I seem to have the problem that the types will be considered a match as soon as they have at least one attribute in common. Would I have to add a negated constraint to check that the subset type doesn't declare an attribute which the other type doesn't have? I get the impression that I am doing something too complicated here...
While this query doesn't demand the general containment discussed above, I do have other queries where that would be useful.
|
|
|
Re: IncQuery Explorer and Xtext resources [message #1415768 is a reply to message #1414880] |
Wed, 03 September 2014 15:05 |
Gabor Bergmann Messages: 36 Registered: July 2009 |
Member |
|
|
Hi Knut,
0. incquery.net was created before we were accepted as an Eclipse project. It is mostly obsolete now, but unfortunately not everything has been updated && migrated to the Eclipse wiki yet. Yes, we know it is an embarrassment, and we would really like to improve the situation soon
I think the rationale behind this behaviour of 'checked' was that you probably would want to see the results while you were actively developing the query, but not necessarily if it is just loaded from some plugin.
1. EMF-IncQuery would behave functionally correctly in case of partial or full Xtext tree rebuilds, as long as notifications are delivered properly. The performance may of course suffer - incremental evaluation is most efficient when there are small changes in large models.
2. Well, we do have a way to opt-out of incremental updates, but it was developed for a different use case, so it still doeas not support containments.
Yes, EMF models are trees, so there are O(n) direct containment edges. But if the tree is k levels deep, there are O(k^2) transitive containment edges along each path from leaf to root. We have thought of ways of avoiding this explosion, just did not get around to implementing them.
----
As for the complex example: you want to express that type x doesn't have any attribute which is missing from type y. This is double negation, which can be expressed by two nested 'neg' calls. A solution might go like this:
pattern equivalentAttribute (attr1: Attribute, attr2: Attribute) = {
attr1 != attr2;
Attribute.name(attr1, sameName);
Attribute.name(attr2, sameName);
Attribute.domain(attr1, sameDomain);
Attribute.domain(attr2, sameDomain);
}
// classes having one pair of equivalent attributes
pattern classesWithEquivalentPair(class1: Type, attr1: Attribute, class2: Type, attr2: Attribute) = {
class1 != class2;
Type.attributes(class1, attr1);
Type.attributes(class2, attr2);
find equivalentAttribute (attr1, attr2);
}
// one of the types has an attribute for which the other has no equivalent
pattern classWithExtraAttribute(class1: Type, attr1: Attribute, class2: Type) = {
Type.attributes(class1, attr1);
neg find classesWithEquivalentPair(class1, attr1, class2, _anyAttr2);
}
// class2 has an equivalent for all attributes of class1
pattern subtypeOf(class1: Type, class2: Type) = {
neg find classWithExtraAttribute(class1, _anyAttr, class2);
}
The first two patterns can be merged, I separated them for clarity only.
Performance warning for this solution: cost of evaluating pattern classWithExtraAttribute would be around O( |Attribute| x |Type| ), because a type has to be paired with each attribute of each other type (except for the case when it does have an equivalent) . This might be a problem if you have thousands of Types. In fact the IncQuery tooling will warn you about this, I think
|
|
| |
Re: IncQuery Explorer and Xtext resources [message #1416447 is a reply to message #1415939] |
Thu, 04 September 2014 19:20 |
Zoltan Ujhelyi Messages: 392 Registered: July 2015 |
Senior Member |
|
|
Hi Knut,
I am thinking a lot and I see no easy way to _both_ avoid the double negation _and_ use IncQuery patterns in a way that is clearly beneficial. Of course, it is easy to write patterns that joins the corresponding types and attributes - but having the types makes this collection trivial, so using a graph pattern for it seems a bit of overkill.
On the other hand, the double negation itself should work quite efficiently in case of IncQuery (the performance warning Gábor has shared has nothing to do with that option). Yes, I know it makes the pattern definition somewhat hard to read, but this should still be understandable.
About source code analysis, we have a set of public and a non-public queries. The public are queries for a Transformation Tool Contest case from 2011 (see https://github.com/ujhelyiz/viatra2-programunderstanding for details - do not be confused by the viatra name, the queries are created with IncQuery). The implemented queries are simple, but for more complex optional tasks we need to implement additional ones.
We also have implemented a set of queries for source code analysis (http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=6747181&url=http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6747181). The paper itself contains the query specifications, but I cannot share the implementations as they were implemented over a proprietary Java AST metamodel.
Cheers,
Zoltán
|
|
|
Re: IncQuery Explorer and Xtext resources [message #1420632 is a reply to message #1416447] |
Wed, 10 September 2014 08:49 |
Knut Wannheden Messages: 298 Registered: July 2009 |
Senior Member |
|
|
Hi Zoltán,
Thank you again for your reply.
Yes, maybe graph patterns are not the correct tool for this particular
query. But it is also these limits I am interested in finding out about
so that I know when to use IncQuery and when not.
I am actually also writing queries against source code models (EMF
models), so I was interested to read your paper. After going through the
6 anti-patterns in the paper I realized that none of them are concerned
with ordering of elements in multi-valued features. That is something I
often find a need to express in my queries. E.g. is statement X the
first in the block B? Or is statement Y immediately followed by
statement Z? I found no way to express such things using the IncQuery
pattern language. Would I be able to do such things at a lower level or
is this an area where you would recommend against using IncQuery?
Kind regards,
Knut
On 9/5/14 3:20, Zoltan Ujhelyi wrote:
> Hi Knut,
>
> I am thinking a lot and I see no easy way to _both_ avoid the double
> negation _and_ use IncQuery patterns in a way that is clearly
> beneficial. Of course, it is easy to write patterns that joins the
> corresponding types and attributes - but having the types makes this
> collection trivial, so using a graph pattern for it seems a bit of
> overkill.
>
> On the other hand, the double negation itself should work quite
> efficiently in case of IncQuery (the performance warning Gábor has
> shared has nothing to do with that option). Yes, I know it makes the
> pattern definition somewhat hard to read, but this should still be
> understandable.
>
>
>
>
> About source code analysis, we have a set of public and a non-public
> queries. The public are queries for a Transformation Tool Contest case
> from 2011 (see https://github.com/ujhelyiz/viatra2-programunderstanding
> for details - do not be confused by the viatra name, the queries are
> created with IncQuery). The implemented queries are simple, but for more
> complex optional tasks we need to implement additional ones.
>
> We also have implemented a set of queries for source code analysis
> (http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=6747181&url=http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6747181).
> The paper itself contains the query specifications, but I cannot share
> the implementations as they were implemented over a proprietary Java AST
> metamodel.
>
> Cheers,
> Zoltán
|
|
|
Re: IncQuery Explorer and Xtext resources [message #1420642 is a reply to message #1420632] |
Wed, 10 September 2014 09:03 |
Zoltan Ujhelyi Messages: 392 Registered: July 2015 |
Senior Member |
|
|
Hi Knut,
you are correct, neither of the queries in the paper rely on the correct ordering, as in we looked for the cases that are easily expressible with all used techniques. We have written a follow-up paper (under review) that tries to extend (among other things) the set of patterns that can be evaluated, but it still does not include ordering constraints.
IncQuery itself does not support quering the order of multi-valued features (this is tracked in bug https://bugs.eclipse.org/bugs/show_bug.cgi?id=398737). The reasons are largely the same as in the previous cases: it is hard to do efficiently in an incremental fashion. We are thinking about supporting such cases, but it is not yet ready.
Possible workarounds:
* If you have a relation that expresses the 'next' element of the list, it can be used instead of the ordering. The blog post in http://cubussapiens.hu/2014/01/parsing-textual-input-with-incquery shows a metamodel that was constructed this way to support this use case.
* You could collect all possible results not caring about the possible ordering, and when processing the results, filter out the invalid ones using Java code.
I hope these ideas are helpful.
Cheers,
Zoltán
|
|
|
Re: IncQuery Explorer and Xtext resources [message #1421172 is a reply to message #1420642] |
Thu, 11 September 2014 02:35 |
Knut Wannheden Messages: 298 Registered: July 2009 |
Senior Member |
|
|
Hi Zoltán,
It seems like rather many of the design decisions boil down to a
trade-off in favor of incremental updates. This is of course a very
powerful feature and I take it that this must be very important to some
users.
Regarding the indexing of elements in a multi-valued feature I was again
wondering if I couldn't externalize this to a Java method using eval()
or check(). Of course there is still the limitation that no EObjects are
allowed as parameters here. I would like to discuss if it wouldn't make
sense to introduce a mechanism to disable that constraint for individual
patterns (e.g. using some annotation or so).
In the user documentation
(https://wiki.eclipse.org/EMFIncQuery/UserDocumentation/QueryLanguage) I
found this in the limitations section:
* For example, you CAN use check(name.contains(someString)).
* But You MUSTN'T use check(someObject.name.contains(someString) as the
name of someObject can change without the Java reference someObject
changing!
Since Java Strings are immutable (I guess this problem is even worse for
mutable data objects like Date) one would actually have to change the
value of the "name" attribute of the "someObject" object. This means
that IncQuery would ignore the resulting change notification if the
pattern doesn't explicitly refer to "name" using a variable. Have I
understood this correctly?
In the case of ordering of values within a multi-valued feature I could
however use a Java method to implement some constraints. E.g. something
like "check(before(block, stmt1, stmt2))" could verify that "stmt1"
occurs before "stmt2" within "block". Provided that EMF IncQuery would
allow me to do this, would the pattern be re-evaluated if some Java
client were to call "block.getStatements().move(0, stmt2);"?
Thanks for the Bugzilla pointer. I will also have a look at Henshin to
see if that can be used to implement some specific queries.
Kind regards,
Knut
On 9/10/14 17:03, Zoltan Ujhelyi wrote:
> Hi Knut,
>
> you are correct, neither of the queries in the paper rely on the correct
> ordering, as in we looked for the cases that are easily expressible with
> all used techniques. We have written a follow-up paper (under review)
> that tries to extend (among other things) the set of patterns that can
> be evaluated, but it still does not include ordering constraints.
>
> IncQuery itself does not support quering the order of multi-valued
> features (this is tracked in bug
> https://bugs.eclipse.org/bugs/show_bug.cgi?id=398737). The reasons are
> largely the same as in the previous cases: it is hard to do efficiently
> in an incremental fashion. We are thinking about supporting such cases,
> but it is not yet ready.
>
> Possible workarounds:
> * If you have a relation that expresses the 'next' element of the list,
> it can be used instead of the ordering. The blog post in
> http://cubussapiens.hu/2014/01/parsing-textual-input-with-incquery shows
> a metamodel that was constructed this way to support this use case.
> * You could collect all possible results not caring about the possible
> ordering, and when processing the results, filter out the invalid ones
> using Java code.
>
> I hope these ideas are helpful.
>
> Cheers,
> Zoltán
|
|
| |
Re: IncQuery Explorer and Xtext resources [message #1421407 is a reply to message #1421172] |
Thu, 11 September 2014 10:20 |
Gabor Bergmann Messages: 36 Registered: July 2009 |
Member |
|
|
Knut Wannheden wrote on Thu, 11 September 2014 04:35Hi Zoltán,
* But You MUSTN'T use check(someObject.name.contains(someString) as the
name of someObject can change without the Java reference someObject
changing!
Since Java Strings are immutable (I guess this problem is even worse for
mutable data objects like Date) one would actually have to change the
value of the "name" attribute of the "someObject" object. This means
that IncQuery would ignore the resulting change notification if the
pattern doesn't explicitly refer to "name" using a variable. Have I
understood this correctly?
Yes. IncQuery has no way of knowing that you use the "name" field, since you can put arbitrary Java code in the check()/eval() constructs (ant the field access may be hidden within a method call, etc.). So it has no way of knowing when to re-evaluate.
I think disabling this validation (e.g. to support your before() construct) would be possible in case of RunOnce execution - but not otherwise. We still have to figure out how to make such a language rule optional
Knut Wannheden wrote on Thu, 11 September 2014 04:35
In the case of ordering of values within a multi-valued feature I could
however use a Java method to implement some constraints. E.g. something
like "check(before(block, stmt1, stmt2))" could verify that "stmt1"
occurs before "stmt2" within "block". Provided that EMF IncQuery would
allow me to do this, would the pattern be re-evaluated if some Java
client were to call "block.getStatements().move(0, stmt2);"?
Not at the moment.
One of our ideas for ordering support was a new language concept similar to you before expression. But we do not have that right now.
|
|
|
Goto Forum:
Current Time: Thu Mar 28 16:09:31 GMT 2024
Powered by FUDForum. Page generated in 0.02412 seconds
|