Challenge: Recursive and Accumulating Filter - wikitext kin:list:from[]

[Yaisog]

@saqimtiaz

While I often think a fair bit about performance as well, make sure you aren’t overoptimizing where it isn’t needed.

That’s true, I am falling into that trap at times.
However, in my production wiki it did make a significant difference when I switched from kin to the taggingtree filter, and according to @stobot’s speed tests, kin would be comparable to the recursive filter thing.
In particular I have a search that creates a list of all tags for all search results (up through multiple levels, tags-of-tags, etc.). This list can then be used via a select element to narrow down all search results to a particular topic anywhere in the upwards hierarchy. To maintain responsiveness of the search to keyboard input this must be really fast.

Maybe I get around to created a more general version of taggingtree and tagstree which use any field containing a title list. There have been a few requests. The thing is that there are internal JavaScript functions for working with tags which would have to be polyfilled to work with any list, I think.

Yaisog

[saqimtiaz]

@Yaisog

To maintain responsiveness of the search to keyboard input this must be really fast.

Makes sense. I often find that keyboard driven workflows really push the boundaries of performance in wikitext. I have had to write custom search operators for precisely these kinds of situations in some of my work.

[TW_Tones]

That would be good @Yaisog but when those lists came about due to tags, the list field will only be present and up to date if triggered. Typicaly an order change since the last tag was added. Ultimatly this is manual.

• I have in the past called for a way trigger a list field update on a given tag, filter or all tags.
• Idealy automaticaly but at least programaticaly.

[Yaisog]

Hi @stobot, I took a stab at making the taggingtree and tagstree filters flexible regarding the field they use. In the end it was just a matter of finding the right core functions.
Have a look at this:
ancestors and descendants filters [TW sharing edition]

These are not fully fleshed out plugins, yet, but just these two filter operators. Drag the system tiddlers to your wiki, save and reload, and you should be good to go.

[[title]ancestors[field]]
will give you all ancestors of title as determined via field. The “ancestor” definition is in the sense of the tags field – the tiddlers listed there are considered the parents of the current tiddler. If you use tags as name of the field, ancestors[] should yield the same results as tagstree[].
If you list the children instead in the field, the meaning of ancestors and descendants is switched, but everything else works just the same.
The input to the filter can be more than a single title. Ancestors for all tiddlers in the input list will be given.

[[title]descendants[field]]
will similarly give you all descendants of title as determined via field.

I am planning on doing some speed testing to see if the internal JS functions for tags are faster than those for general fields (in which case I would keep the taggingtree and tagstree filters). Let me know if everything works OK and I might make these into proper plugins.

Yaisog

[Scott_Sauyet]

I’m curious as to whether this is just a typo or some humor that went over my head:

getTdidlersRecursively
   ^ ^

[Yaisog]

This is a typo. Which I seemingly made 3 times out of 3. Very weird. Shall be fixed in the final version.

Yaisog

[Yaisog]

In some very quick and non-representative tests it seemed that taggingtree[] is about 3 times faster than descendants[], and tagstree[] is about twice as fast as ancestors[]. Seems like the optimizations in the core for working with tags are pretty effective.
So, when UI responsivity is of the utmost importance, the general versions cannot fully replace the specialized ones.

Yaisog

[pmario]

Non of the functions you mention here are part of the core.

[stobot]

@Yaisog - Thanks! I just ran the full speed trials, and ancestors[] is the new speed champ! It doesn’t come out in the needed order, but maybe that’s easily fixed.

Speed trials:

9 tests, min, max, average, median shown, median used for results

Needed order:

Ancestors order:

Ancestors also doesn’t include the “root” but I can probably add that in the filter string.

@pmario: I was under the assumption that the “tag-based” functions might be getting benefit from the core tag indexing / optimizations even though the functions aren’t core. Is that possible? I’m assuming that’s what Yaisog was thinking too?

[pmario]

@stobot

@pmario: I was under the assumption that the “tag-based” functions might be getting benefit from the core tag indexing / optimizations even though the functions aren’t core. Is that possible? I’m assuming that’s what Yaisog was thinking too?

It depends on the internal functions the js-code uses. Those core functions usually use the tag-based optimizations.

I do not use any of those functions. Are there any links to the code repositories?

[TW_Tones]

Love your wokd @Yaisog.

Please make sure the order is depth first by default as it is much more useful than the alternative and most likely reflects the ways you aquire titles. I argued this earlier with taggingtree but remember the breadth first is easy to get from standard filters the depth first is what designers most need in tree walking.

I am yet to experiment with your new operators and will soon but can we use them to handle the two different cases as follows?

• a tiddler lists it parent(s) as tags do now
• a parent lists its children

I raise this because the operators are using the general names of ansestors and descendants and if they will only handle one form we will need to find a way to represent the other form.

We also need to address the posibility of two or more parents. Which interestingly although are ancestors looks more like a descendants tree going from few to many.

[Yaisog]

@pmario

Non of the functions you mention here are part of the core.

I was talking about the JavaScript core functions that are used within the JS filter code, not the new “filter functions.” It does get confusing a bit with the new nomenclature and all…

@TW_Tones

Please make sure the order is depth first by default as it is much more useful than the alternative and most likely reflects the ways you aquire titles.

Yes, the final versions will do that, since it doesn’t add any complexity. I simply based the new filters off the “wrong” base versions.

@stobot

I was under the assumption that the “tag-based” functions might be getting benefit from the core tag indexing / optimizations even though the functions aren’t core.

I think tag handling is heavily optimized in the core, but regular fields are also cached und thus much faster than they were in early versions. But, like I said, in my test wiki which has 8,500 tiddlers overall, using the internal function getTiddlersWithTag(title) is about 3 times faster than the generic findListingsOfTiddler(title,field) even when the latter uses the tags field.
In smaller wikis the differences seem to vanish a bit, since the “two-function-method” took about 25 times as long as taggingtree[] in that wiki, while in your table the difference is much smaller.

[TW_Tones]

Perhaps in time the results of these operators could also be cached as well?

However the value of such an operator is to set a variable to the resulting list of tiddlers, then use that variable to count them all, find a position in the list, find next and last in the list, etc… so you need only walk the tree once.

• In effect the variable containing the list becomes the cache
• perhaps if there is any caching to do, we do it on large list variables.
  • I wonder if tiddlywiki could cache all large list variables or we could create a special case to set a cached list variable.
• One discovery of my own is once you have access to your list of tiddlers, in your code you can always go to an interrogate that tiddler again if you want.
  • lets say you are stepping through the tiddlywiki TOC and you are at [[OfficialPlugins]] you need not get tricky just go to [[OfficialPlugins]] tiddler to retrieve its children, rather than trying to manage that in the aforementioned list variable.
  • Such operators walk the tree and generate a complete list, we can then use it as the reference and make use of each tiddler title as we wish.
• Since tiddlywiki runs in browser memory I think it possibly is efficient already.

[TW_Tones]

@Yaisog just a quick reminder of what the kin operator does to keep in mind if your code has the opportunity to address.

• you can set the position or depth to itterate

One other thing we can all remember is the value of comparing two or more lists and especialy when using heirachical lists these operators can generate. Intersections subtractions etc…

For example

Give the current tiddler we can find its grandparent(s) then itterate their descendants. Then find its parent(s) and their descendants, we can subtract the second list from the first and find the cousins.

• the kin operator continues to be a powerful tool to do this kind of analysis.

[Yaisog]

Hi @TW_Tones, are you suggesting that I add this functionality, too, or are you merely pointing out the merits of kin as compared to tagstree[] and company?

It should not be too hard to integrate a recursion counter and to stop at some given depth. I’m wondering what the best filter syntax for this case would be. I’m leaning towards

descendants[‹field›],[‹depth›]

since this would allow both parameters to be set via variables or transclusions.

I have already integrated the taggingtree[] functionality into the descendants[] filter by using the quicker JS functions when the field is tags (or equivalently is not set). For tags, there is no measurable difference in computation time between the two as far as I can tell. Other fields will be a bit slower. I want to get the syntax final before I post a any further code, though.

Yaisog

PS: Whenever I write taggingtree / descendants I also mean the tagstree / ancestors pair.

[TW_Tones]

The design is in your hands @Yaisog. My outline previous is primarily for clarity and for future readers. Hopefully it provides clarity to you as well.

The depth feature would be great, for a range of applications, both for its efficiency and even it overall simplicity compared to @saqimtiaz brilliant use of two functions.

I support your approach to the parameters in the example you give, however I still see it it could be even more general. I am not necessarily saying you should change your approach, but I want it to be clear even if I overstate it.

As I understand in your current proposed filters they will receive a title and look for that title in the (list) field or tags named? It will do this recursively and depth first, by default all tiddlers in that “tree”.

• This is of great advantage to designers within TiddlyWiki script because it roles the recursion into a filter operator.
• We can see how given the parameters your operators are given they will produce the equivalent to a filter to walk the tree.
• This is most likely much more performant.

Questions

Effective field

There are cases where the related tiddlers (Children or Parents) can be found listed in the current tiddler, or cases where the current tiddler is listed in other tiddlers fields.

• Will your operators allow both these these cases?

Using any filter

If we write a procedure that calls a second “each item” procedure we can write a recursive procedure. In this case however we can give any filter that is used both for the root and walking the tree. This filter can be any valid filter, for example we may be able to iterate a tree based on backlinks for example. But we do need to add loop protection.

• Can you see us writing a similar operator to walk the tree based on an arbitrary filter as above?.
• This would allow a comprehensive and general solution.

When loops are found

When a loop is encountered clearly the process needs to stop iterating otherwise it gets into a loop. Perhaps there are two ways I can see to handle this;

• The operators could exclude the “offending title” altogether,
• or add it to the output, as a duplicate entry but not iterate it further.

There are pros and cons about both approaches, but the second may be the only way to find and identify such cases, and possibly handle them differently, what are your/anyones thoughts?

[Yaisog]

@TW_Tones

Will your operators allow both these these cases?

The field to use is the first parameter and defaults to tags.

@TW_Tones

Can you see us writing a similar operator to walk the tree based on an arbitrary filter as above?.

I think this is best left to a WikiText implementation which offers great flexibility for such special cases. This could be the filter function approach from above which uses the new ability to write recursive filters.
I can also see the kin filter being extended, since it was conceived as a very general and flexible solution from the beginning.

@TW_Tones

The operators could exclude the “offending title” altogether,

When a title is found that is already in the results list - as would be the case with a loop - it is not added again and/or followed further. I think loop protection already works pretty good.

Yaisog

[TW_Tones]

I think this topic is very valuable, and @saqimtiaz and @Yaisog’s contributions substantial. However I am trying to retain an open and innovative mind.

• If we have a reliable depth first list of tiddlers found, which we do now, I belive there is a lot we can do with such lists, not fully explored yet.
  • For example looking at such lists as sets or arrays and using all the common set operations against one or more sets.

The following may Only be for the code and concept geeks

However I also saw @Yaisog mention of;

@Yaisog

unique[] filter at the end since :map:flat doesn’t remove duplicates by itself.

May give me room to explore this following idea, outside of the ancestor and dependants operators and in @saqimtiaz’s function equivalents.

@TW_Tones

When loops are found

When a loop is encountered clearly the process needs to stop iterating otherwise it gets into a loop. Perhaps there are two ways I can see to handle this;

• The operators could exclude the “offending title” altogether,
• or add it to the output, as a duplicate entry but not iterate it further.

• Because this is useful information. Especialy if iterating networks, rather than heirachies. Just because it would result in a loop, it does not stop it from being information found in the data, and thus useful.

My mind then wandered to, where else I had seen something similar to recursion in existing filter operators?, then I remembered each and eachday operators.

Each input title is processed in turn. The value of field F in the corresponding tiddler is examined.

As long as the value of the field is unique (i.e. has not been encountered before), the title is appended to the output.

• I think this may offer a quick way to collect all titles that belong in a large list such as a set or heirachy, even if not in a usabable order. Thus allowing us to quickly test for membership or non membership.
  • We may thus be able to avoid a logicaly recursive process to build membership lists.
  • This is only a hunch at present.

[Edited] @Yaisog the depth function is not yet implemented?