GNOME Bugzilla – Bug 496232
Add traverse flag to Collection.getMatches[From|To]
Last modified: 2008-02-27 06:08:18 UTC
The getMatches functions do not traverse out of a subtree. This makes finding the next and previous object that matches a given matchRule impossible unless the two objects are within the same subtree. Please give tree traversal the ability to traverse out of subtree and to continue looking in an in-order manner.
This bug comes from some discussion you can find on http://live.gnome.org/GAP/Collection. I think it would be best to change getMatchesFrom into something like getMatchesFrom (object, matches, traverse_collection, type_of_traversal); where type_of_traversal is an enum that includes the two current type of traversals but also what Scott is asking for. Traverse_collection means if collection should traverse into another collection. Li you can assign this to me. ariel
Just curious how progress is coming along on this bug. Is it something we might have for GNOME 2.21.5 on January 14?
Created attachment 104391 [details] [review] Ariel's original 'work in progress' patch This is the original patch Ariel sent me.
Created attachment 104394 [details] [review] first version of Add traverse flag to Collection.getMatches[From|To] This patch adds two new Collection methods: getMatchesInOrder(current_object, MatchRule, sortby, recurse, count, traverse) and getMatchesInBackOrder (current_object, MatchRule, sortby, count). getMatchesInOrder() was adapted from Ariel's original patch and getMatchesInBackOrder() is original work. Functionality: getMatchesInOrder() - given an object within the collection and a matchrule, this method will return a list of matches from the given object (not inclusive) in an inorder traversal. It has flags to recurse the collection and to traverse outside the collect and into the remaining hierarchy. getMatchesInBackOrder() - given an object within the collection and a matchrule, this method will return a list of matches from the given object (not inclusive) to the collection node in a reverse inorder traversal. There are no flags for traversal or recursion. questions: what is the last call to sort_order_canonical() in inorder() used for? what is the functionality of getMatchesTo() and getMatchesFrom()? Are they now obsolete?
getMatchesFrom/to return the next / previous element from the current object but only from this object children but doesn't get all of the next elements as in the InOrder functions. I think we only need one method that provides a flag of what type of query we need.
(In reply to comment #5) > getMatchesFrom/to return the next / previous element from the current object > but only from this object children but doesn't get all of the next elements as > in the InOrder functions. I think we only need one method that provides a flag > of what type of query we need. I'm confused by the current API in trunk -- there's no documentation in the IDL, so I'm try to cross reference things to http://www.gnome.org/~billh/at-spi-new-idl/html/html/classAccessibility_1_1Collection.html. I assume get[Previous,Next]Children is now get[Previous,Next]Matches methods in the current API in trunk. Is that true? In addition, the current API has a 'traverse' flag in the get{Previous,Next}Matches methods. Is the 'traverse' flag the one we're looking to use for this bug? I just might not be understanding the API very well, though. My mental model is this: getMatches - works on a Collection pulled from the current accessible. All results are relative to the accessible it was pulled from. getMatchesTo - given an accessible, do a reverse search for a match getMatchesFrom - given an accessible, do a forward search for a match If this is the case, then the current API in trunk seems weird: 1) Should 'traverse' be 'recurse' in getMatches? AccessibleSet getMatches (in MatchRule rule, in SortOrder sortby, in long count, in boolean traverse); 2) This seems to make sense. 'recurse' means go into children and grandchildren and so on, and traverse means to pop upwards and previous in the hierarchy: AccessibleSet getMatchesTo (in Accessible current_object, in MatchRule rule, in SortOrder sortby, in boolean recurse, in long count, in boolean traverse); 3) I'm guessing 'isrestrict' should be 'recurse'? AccessibleSet getMatchesFrom (in Accessible current_object, in MatchRule rule, in SortOrder sortby, in boolean isrestrict, in long count, in boolean traverse); If I put all this together, it seems like getMatchesInOrder and getMatchesInBackOrder might be manageable in the existing API by using SortOrder = SORT_ORDER_CANONICAL and traverse = True. But, my mental model might be wrong. I see these strange sort orders in the API: SORT_ORDER_REVERSE_CANONICAL, SORT_ORDER_REVERSE_FLOW, SORT_ORDER_REVERSE_TAB, If getMatchesTo is indeed a reverse search, then what are these sort orders for? For example, what does a SORT_ORDER_REVERSE_CANONICAL mean in a call to getMatchesTo?
Li and/or Ariel: Can you provide more description (or documentation) on what the existing IDL is supposed to do? It will definitely help us understand if there is a need for new methods in the API and/or if the existing functionality has bugs or not. Thanks! Will
I'll post one by tomorrow.
Info from IM: (13:56:10) WillieWalker: ariel: what do the SORT_ORDER_REVERSE_* values mean when using getMatches{To,From}? (13:56:12) ariel: basically i added getmatchesinorder so scott could test what he wanted (13:57:08) ariel: in getMatchesTo/From is confusing (13:57:21) ariel: but they are not the same (13:57:33) WillieWalker: ariel: ha, yeah. (13:58:04) WillieWalker: ariel: my understanding is that getMatchesTo is a reverse search from the accessible and getMatchesFrom is a forward search. (13:58:21) ariel: starting from the given current_object (13:58:29) ariel: yes (13:58:40) ariel: and if you add the SORT_FLAG_REVRESE (13:58:40) WillieWalker: ariel: and SORT_ORDER_* were mostly to say the kind of patch to be taken (hierarchical, flows relations, etc.). (13:58:53) ariel: from the result you will get the revrese of the normal order (13:59:11) ariel: in canonical (13:59:30) WillieWalker: s/patch/path/ (14:00:22) WillieWalker: ariel: so assume we have some sort of ordering like this: a b c d e f (14:00:30) ariel: aja (14:00:31) WillieWalker: ariel: and I'm on "c" (14:00:47) ariel: on To you will get a b (14:00:59) ariel: on From you will get d e f (14:01:07) ariel: reverse on to will give you b a (14:01:12) ariel: and from f e d (14:01:26) WillieWalker: ariel: aha. Thanks! That explains it. (14:01:47) ariel: so what you said on the bug is not what it's happening (14:01:49) ariel: it's confusing (14:01:58) ariel: and the current API is confusing with all the flags and things (14:02:03) ariel: the traverse, restrict (14:02:06) ariel: etc (14:02:15) hittsjunk left the room (quit: Leaving.). (14:02:42) WillieWalker: ariel: so, we really should just need two flags: recurse and traverse? (14:02:56) ariel: I think three (14:03:11) ariel: recurse, traverse, and type_of_tree_search (14:03:23) WillieWalker: is type_of_tree the sort_order? (14:03:27) ariel: no (14:03:32) ariel: that's different (14:03:38) WillieWalker: you mean depth first vs. breadth first? (14:03:43) ariel: nope (14:03:53) ariel: let me quickly epxalin (14:03:55) ariel: explain (14:04:07) ***WillieWalker listens and shuts up. :-) (14:04:30) ariel: we might want to ask to search only for the nex matches of current_object (14:04:40) ariel: that's one type (14:05:20) ariel: this means to look on the chidlren of current_object only (14:06:10) ariel: we might also want to the previous things but also to look on the nexct matches of the next children of the parent of current_object (14:06:40) ariel: and finally we might like to look for the nexct matches in depth first (14:06:50) ariel: all of this already coded (14:07:40) ariel: WillieWalker: only a matter of deciding what we want, if all of these are usable or not (14:08:42) WillieWalker: ariel: I took 'recurse' to mean go into children and I took 'traverse' to mean look above the current object and I took CANONICAL to mean depth first, even though it really didn't say so. (14:08:50) ariel: nope (14:09:16) ariel: recurse means if we want to look on the children of the chidlren of the starting object (14:09:31) ariel: traverse means whether we should traverse into another collection (14:09:52) ariel: originally it was decided that a collection query cpuldnot traverse into another collection (14:10:01) ariel: s/cpuldnot/couldnt (14:10:07) WillieWalker: OK - I think we're on the same page about recurse. (14:10:25) ariel: traverse means traverse into other collections (14:10:31) WillieWalker: I'm not sure I understand traverse. What is 'another collection'? (14:10:56) ariel: on your hierarchy you might found another accesible that implements collection (14:11:27) ariel: the original idea was that you didn't want to go inside another collection (14:11:38) ariel: but Scott told me it was necesary in some cases (14:11:51) ariel: so that's why I added that flag (14:12:22) ariel: WillieWalker: I have to go, but maybe later we can continue (14:12:25) WillieWalker: Oh...I see now. Sounds odd. shaeger - is it that you want to go into another Collection or that you want to be able to pop up above the current object and look in order through the rest of te tree? (14:12:36) WillieWalker: ariel: OK. Thanks for the explanation! (14:12:44) ariel: It's confusing I know (14:13:07) ariel: when is the target for gnome 2.22? (14:13:15) WillieWalker: ariel: soon! (14:13:27) WillieWalker: http://live.gnome.org/TwoPointTwentyone (14:13:30) ariel: soon is tomorrow? soon is 1/2 weeks? (14:13:39) WillieWalker: ariel: Beta 2 is Monday. (14:13:59) WillieWalker: ariel: API freeze was Jan 21. (14:14:06) shaeger: WillieWalker: ariel: given a collection node, say the document frame, I want to give a second object and begin the search from the second object to the last object or collection object (14:14:57) ariel: WillieWalker: do we agree that we onlny need one From method and one To method (14:14:58) ariel: right? (14:15:27) WillieWalker: ariel: I think. I need to better understand the API and also what Scott is trying to accomplish. (14:15:49) ariel: we can continue this conversation later today (14:16:02) WillieWalker: ariel: OK. I'll be around. Mind if I cut/paste this IM chat into the bug? (14:16:13) ariel: no problem (14:16:17) WillieWalker: ariel: TX!
The patch that I will add after this comment now defines getMatches, getMatchesTo and getMatchesFrom as: AccessibleSet getMatches (in MatchRule rule, in SortOrder sortby, in long count, in boolean traverse); AccessibleSet getMatchesTo (in Accessible current_object, in MatchRule rule, in SortOrder sortby, in TreeTraversalType tree, in boolean recurse, in long count, in boolean traverse); AccessibleSet getMatchesFrom (in Accessible current_object, in MatchRule rule, in SortOrder sortby, in TreeTraversalType tree, in long count, in boolean traverse); For Scott needs you have to do: matches = col.getMatchesFrom (matches[0], rule, col.SORT_ORDER_CANONICAL, col.TREE_INORDER, 0, True) I am still not sure on the name I used for the TreeTraversalType enumeration.
Created attachment 104901 [details] [review] Clean API with better implementation of getMatches(To/From) See previous comment. Scott, please check to ensure everything is in place.
Here are my observations: 1) getMatchesTo(... TREE_RESTRICT_CHILDREN ...) and getMatchesTo(... TREE_RESTRICT_SIBLING ...) are the same. Did you forget to pass the correct value in the switch statement? 2) The sort order is different for getMatchesTo( ... TREE_INORDER ...) compared to getMatchesTo( ... TREE_RESTRICT_CHILDREN ...) and getMatchesTo( ... TREE_RESTRICT_SIBLING ...) test script and test HTML file to follow.
Created attachment 104951 [details] test script and HTML file. the HTML file has a hierarchy as follows where df=doc frame, S=Section, and H=heading: df / / | \ \ H H S S H / / \ H H S / H Also included is a new Python test script. Look for 'startobj' to change the starting object. Right now, we match on all objects.
Scott, Not sure what do you mean by this: 2) The sort order is different for getMatchesTo( ... TREE_INORDER ...) compared to getMatchesTo( ... TREE_RESTRICT_CHILDREN ...) and getMatchesTo( ... TREE_RESTRICT_SIBLING ...) ariel
The returned list of objects is reversed when TREE_RESTRICT_CHILDREN and TREE_RESTRICT_SIBLING are used in a call to getMatchesTo().
Created attachment 105516 [details] [review] Fixes getMatchesTo sort order. Fixes getMatchesTo sort order.
Comment on attachment 105516 [details] [review] Fixes getMatchesTo sort order. >Index: libspi/collection.c >=================================================================== >--- libspi/collection.c (revision 982) >+++ libspi/collection.c (working copy) >@@ -157,8 +157,7 @@ > mrp = spimatchrule->_mrp; > > CORBA_free (mrp->attributes); >- CORBA_free (mrp->roles); >- CORBA_free (mrp->interfaces); >+ CORBA_free (mrp->roles); CORBA_free (mrp->interfaces); > Why? > g_free (mrp); > >@@ -560,12 +559,11 @@ > Accessibility_Accessible obj, glong index, gboolean flag, > Accessibility_Accessible pobj, CORBA_boolean recurse, > CORBA_boolean traverse, CORBA_Environment *ev){ >- > gint i = index; > glong acount = Accessibility_Accessible__get_childCount (obj, ev); > gboolean prev = pobj? TRUE : FALSE; >- >- for (; i < acount && (max == 0 || kount < max); i++){ >+ >+ for (; i < acount && (max == 0 || kount < max); i++){ Do we only added a space here? > Accessibility_Accessible child = Accessibility_Accessible_getChildAtIndex (obj, i, ev); > > >@@ -575,7 +573,8 @@ > > } > >- if (flag && match_interfaces_lookup (child, mrp, ev) && match_states_lookup (child, mrp, ev) >+ if (flag && match_interfaces_lookup (child, mrp, ev) >+ && match_states_lookup (child, mrp, ev) > && match_roles_lookup (child, mrp, ev) > && match_attributes_lookup (child, mrp, ev) > ){ >@@ -595,6 +594,69 @@ > return kount; > } > >+static int >+sort_order_rev_canonical (MatchRulePrivate *mrp, GList *ls, >+ gint kount, gint max, >+ Accessibility_Accessible obj, gboolean flag, >+ Accessibility_Accessible pobj, CORBA_Environment *ev){ >+ Accessibility_Accessible nextobj; >+ Accessibility_Accessible parent; >+ glong indexinparent; >+ >+ // This breaks us out of the recursion. >+ // todo: might need to restrict the bounds of the "Collection" Can we put the comments in /* */ ? >+ if (obj == CORBA_OBJECT_NIL >+ || CORBA_Object_is_equivalent (obj, pobj, ev)) >+ { >+ return kount; >+ } >+ >+ // Add to the list if it matches >+ if (flag && match_interfaces_lookup (obj, mrp, ev) >+ && match_states_lookup (obj, mrp, ev) >+ && match_roles_lookup (obj, mrp, ev) >+ && match_attributes_lookup (obj, mrp, ev)) >+ { >+ ls = g_list_append (ls, obj); >+ kount++; >+ } >+ >+ if(!flag) flag = TRUE; >+ >+ // Get the current nodes index in it's parent and the parent object. >+ indexinparent = Accessibility_Accessible_getIndexInParent (obj, ev); >+ parent = Accessibility_Accessible__get_parent (obj, ev); >+ >+ if(indexinparent > 0) >+ { >+ // there are still some siblings to visit so get the previous sibling >+ // and get it's last descendant. >+ // First, get the previous sibling >+ nextobj = Accessibility_Accessible_getChildAtIndex (parent, >+ indexinparent-1, >+ ev); >+ >+ // Now, drill down the right side to the last descendant >+ while(Accessibility_Accessible__get_childCount (nextobj, ev) > 0) >+ { >+ nextobj = Accessibility_Accessible_getChildAtIndex (nextobj, >+ Accessibility_Accessible__get_childCount (nextobj, ev)-1, ev); >+ >+ } >+ // recurse with the last descendant >+ kount = sort_order_rev_canonical (mrp, ls, kount, max, >+ nextobj, TRUE, pobj, ev); >+ } >+ else >+ { >+ // no more siblings so next node must be the parent >+ kount = sort_order_rev_canonical (mrp, ls, kount, max, >+ parent, TRUE, pobj, ev); >+ >+ } >+ return kount; >+} >+ > static int > query_exec (MatchRulePrivate *mrp, Accessibility_Collection_SortOrder sortby, > GList *ls, gint kount, gint max, >@@ -638,15 +700,21 @@ > return retval; > } > >+/* >+ GetMatchesTo es normal segun API. Podria usarse tambien para anterior cuando ya recorremos el arbol normalmente. >+ Este solamente sirve para encontrar los siguientes nodos a partir de current_object teniendo este como tope, >+ o siguientes matches tomando como marco el parent del current_object >+*/ >+ > static Accessibility_AccessibleSet * >-impl_getMatchesFrom (PortableServer_Servant servant, >- const Accessibility_Accessible current_object, >- const Accessibility_MatchRule rule, >- const Accessibility_Collection_SortOrder sortby, >- const CORBA_boolean isrestrict, >- CORBA_long count, >- const CORBA_boolean traverse, >- CORBA_Environment *ev){ >+getMatchesFrom (PortableServer_Servant servant, >+ const Accessibility_Accessible current_object, >+ const Accessibility_MatchRule rule, >+ const Accessibility_Collection_SortOrder sortby, >+ const CORBA_boolean isrestrict, >+ CORBA_long count, >+ const CORBA_boolean traverse, >+ CORBA_Environment *ev){ > > GList *ls = NULL; > Accessibility_Accessible parent; >@@ -654,6 +722,7 @@ > glong index = Accessibility_Accessible_getIndexInParent (current_object, ev); > gint kount = 0; > >+ Please remove the empty line. > ls = g_list_append (ls, current_object); > mrp = get_collection_from_servant (servant)->_mrp;; > >@@ -675,33 +744,148 @@ > } > > >+/* >+ inorder traversal from a given object in the hierarchy >+*/ >+ >+static int >+inorder (Accessibility_Accessible collection, MatchRulePrivate *mrp, >+ GList *ls, gint kount, gint max, >+ Accessibility_Accessible obj, >+ gboolean flag, >+ Accessibility_Accessible pobj, >+ CORBA_boolean traverse, >+ CORBA_Environment *ev){ >+ >+ int i = 0; >+ >+ // First, look through the children recursively. >+ kount = sort_order_canonical (mrp, ls, kount, max, obj, 0, TRUE, >+ CORBA_OBJECT_NIL, TRUE, TRUE, ev); >+ >+ // Next, we look through the right subtree >+ while ((max == 0 || kount < max) >+ && ! CORBA_Object_is_equivalent (obj, collection, ev)) >+ { >+ >+ i = Accessibility_Accessible_getIndexInParent (obj, ev); >+ Accessibility_Accessible parent = >+ Accessibility_Accessible__get_parent (obj, ev); >+ kount = sort_order_canonical (mrp, ls, kount, max, parent, >+ i+1, TRUE, FALSE, TRUE, TRUE, ev); >+ obj = parent; >+ } >+ >+ // unknown function ??? >+ if (kount < max) >+ { >+ kount = sort_order_canonical (mrp, ls, kount, max, >+ obj, i + 1, TRUE, FALSE, >+ TRUE, TRUE, ev); >+ } >+ >+ return kount; >+} >+ >+/* >+ GetMatchesInOrder: get matches from a given object in an inorder traversal. >+*/ >+ > static Accessibility_AccessibleSet * >-impl_getMatchesTo (PortableServer_Servant servant, >- const Accessibility_Accessible current_object, >- const Accessibility_MatchRule rule, >- const Accessibility_Collection_SortOrder sortby, >- const CORBA_boolean recurse, >- CORBA_long count, >- const CORBA_boolean traverse, >- CORBA_Environment *ev){ >+getMatchesInOrder (PortableServer_Servant servant, >+ const Accessibility_Accessible current_object, >+ const Accessibility_MatchRule rule, >+ const Accessibility_Collection_SortOrder sortby, >+ const CORBA_boolean recurse, >+ CORBA_long count, >+ const CORBA_boolean traverse, >+ CORBA_Environment *ev){ >+ GList *ls = NULL; >+ AtkObject *aobj; >+ Accessibility_Accessible obj, collection; >+ MatchRulePrivate *mrp; >+ gint kount = 0; > >+ ls = g_list_append (ls, current_object); >+ mrp = get_collection_from_servant (servant)->_mrp; > >+ aobj = get_atkobject_from_servant (servant); >+ obj = spi_accessible_new_return (aobj, FALSE, ev); >+ collection = obj; Why do we need obj here?
Created attachment 105774 [details] [review] second version of Add traverse flag to Collection.getMatches[From|To] This patch is a major cleanup from the previous patch. The work includes removing blank lines and other whitespace, restricting lines to 80 characters, commit style changes and general readability changes. None of the logic from the previous patch has been changed except for the last item mentioned in Li's previous comment, namely removing collection = obj and using obj directly.
Thanks for the patch. Can someone provide a changelog for the patch?
Since the patch changes the API, I'd like to commit it after the API freeze
(In reply to comment #20) > Since the patch changes the API, I'd like to commit it after the API freeze Hi Li: I'd like to request an API freeze break if we can. The reason is that we're pretty sure Orca is currently the only consumer of the Collections API right now. If we were to not change the API now, we risk the chance that someone else will start using the API and we will end up with a situation where the changes may have an adverse effect on them. By making the changes now, we can be sure that new users of the API will not run into this. What do you think? Will
Li, Will is right I think is better to change the API now and stop any future now that orca is the only one using it. ariel
2008-02-25 Ariel Rios <ariel@gnu.org> * libspi/collection.c: (getMatchesInOrder): New method to get next matches from a given object in order. (inorder): Helper method for above method. (getMatchesInBackOrder): New method to get previous matches from a given object in order. (getMatches[From/To]): Old impl_getMatches[From/To] to be able to accomodate in order querys. (impl_getMatches[From\To]): New implementation that accomodate in order querys. (sort_order_rev_canonical): Method to do querys and get results in canonical reverse. New. * idl/Accessibility_Collection.idl: (getMatchesTo, getMatchesFrom) API Change that adds in order querys Bug #496232. Work by Ariel Rios <ariel@gnu.org> and Scott Haeger <scott@bashautomation.com>.
OK for me. Please request an API freeze break.
Can we close this bug?
I say yes we can.
I think so. ariel