Skip to main content


Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
Home » Archived » EMF-IncQuery » IncQuery Explorer and Xtext resources
IncQuery Explorer and Xtext resources [message #1414880] Mon, 01 September 2014 13:59 Go to next message
Knut Wannheden is currently offline Knut WannhedenFriend
Messages: 298
Registered: July 2009
Senior Member
Hi all,

I just started using IncQuery and think it looks very interesting! I have some comments and questions I would like to discuss:

0. I think it was a bit hard to get started because some of the examples seem a bit outdated and the getting started doesn't really have much to say about using the Query Explorer. Also some of the annotations and annotation values (e.g. QueryExplorer.show or sImilar) seem to have been deprecated but I don't find any documentation on what to use instead.

1. I wanted to write some queries against some models in Xtext resources. I couldn't seem to load the resources in the explorer and was thinking I missed something. Then I found that I can load them if I open the resource in the sample reflective ecore model editor instead. I think it would be great if IncQuery could also support the Xtext editors to do this (also drag&drop wouldn't work).

2. Next I wanted to write a generic recursive "contains" pattern to match an object contained by another (directly or indirectly). I quickly found that this is 't possible without declaring an alternative for every single containment reference in the meta model(s). I think it would be great if this could be "fixed". Alternatively, would it be possible to allow check() and eval() expressions to operate on EObjects (maybe with an appropriate @SuppressWarnings somewhere) so that things like this could be done in Java?

Kind regards,

Knut Wannheden
Re: IncQuery Explorer and Xtext resources [message #1415177 is a reply to message #1414880] Tue, 02 September 2014 08:58 Go to previous messageGo to next message
Zoltan Ujhelyi is currently offline Zoltan UjhelyiFriend
Messages: 343
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 Go to previous messageGo to next message
Knut Wannheden is currently offline Knut WannhedenFriend
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 Go to previous messageGo to next message
Gabor Bergmann is currently offline Gabor BergmannFriend
Messages: 28
Registered: July 2009
Junior 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 Smile

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 Smile
Re: IncQuery Explorer and Xtext resources [message #1415939 is a reply to message #1415768] Thu, 04 September 2014 02:22 Go to previous messageGo to next message
Knut Wannheden is currently offline Knut WannhedenFriend
Messages: 298
Registered: July 2009
Senior Member
Hi Gabor and Zoltan,

Thank you for the answers, explanations, and the sample implementation for my query problem. Regarding the latter I was afraid that I would have to use double negation. I was asking about this particular problem, because that is also something that is cumbersome to implement with ANSI SQL (and also performs horribly on some RDBMS's). Instead I was hoping that there would be some for-each primitive which would allow me to formulate the pattern in a "positive way": For each attribute of type1 there is an equivalent in type2. I suppose I can't simply use the Java API to formulate it this way, can I?

Since you have a lot of experience with using IncQuery for source code models, can you point me to some examples of more complex queries of that kind (other than what is already listed in the documentation)? I think that would help me get ideas for other ways to express my queries.

Regards,

Knut
Re: IncQuery Explorer and Xtext resources [message #1416447 is a reply to message #1415939] Thu, 04 September 2014 19:20 Go to previous messageGo to next message
Zoltan Ujhelyi is currently offline Zoltan UjhelyiFriend
Messages: 343
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 Go to previous messageGo to next message
Knut Wannheden is currently offline Knut WannhedenFriend
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 Go to previous messageGo to next message
Zoltan Ujhelyi is currently offline Zoltan UjhelyiFriend
Messages: 343
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 Go to previous messageGo to next message
Knut Wannheden is currently offline Knut WannhedenFriend
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 #1421320 is a reply to message #1421172] Thu, 11 September 2014 07:59 Go to previous messageGo to next message
Zoltan Ujhelyi is currently offline Zoltan UjhelyiFriend
Messages: 343
Registered: July 2015
Senior Member
Hi Knut,

you are right; our design philosophy with regards to the language was to have only constructs that we can efficiently evaluate using the Rete networks (as used by our runtime). As we are now working on alternative query execution strategies, we plan to soften some of these constraints. However, until we have those strategies in place, the memory limits and incremental soundness are our main issues.

About your suggestion: you understand well the issue with the notifications; and we took a very strict approach to ensure safety by disallowing referencing EObjects in check/eval expressions. There are some exceptions where they are safe to use; but it is very hard to verify it.

We have a different strategy called "run-once" query engine implemented (see https://wiki.eclipse.org/EMFIncQuery/UserDocumentation/API/RunOnce) that alleviates all issues related to incremental soundness by building a Rete network, evaluating the queries and throwing the network away.

For "run-once" queries these incremental soundness issues could be ignored, so I guess, by implementing some runtime validations we might loose this validation rule.

Gábor, what do you think about this?

Zoltán
Re: IncQuery Explorer and Xtext resources [message #1421407 is a reply to message #1421172] Thu, 11 September 2014 10:20 Go to previous message
Gabor Bergmann is currently offline Gabor BergmannFriend
Messages: 28
Registered: July 2009
Junior Member
Knut Wannheden wrote on Thu, 11 September 2014 04:35
Hi 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 Smile

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.
Previous Topic:Check URI of Resource
Next Topic:call queries IncQuery API
Goto Forum:
  


Current Time: Tue Nov 13 19:51:40 GMT 2018

Powered by FUDForum. Page generated in 0.02504 seconds
.:: Contact :: Home ::.

Powered by: FUDforum 3.0.2.
Copyright ©2001-2010 FUDforum Bulletin Board Software

Back to the top