response
[ikiwiki.git] / doc / todo / dependency_types.mdwn
1 Ikiwiki currently only has one type of dependency between pages
2 (plus wikilinks special cased in on the side). This has resulted in various
3 problems, and it's seemed for a long time to me that ikiwiki needs to get
4 smarter about what types of dependencies are supported.
5
6 ### unnecessary work
7
8 The current single dependency type causes the depending page to be rebuilt
9 whenever a matching dependency is added, removed, or *modified*. But a
10 great many things don't care about the modification case, and often cause
11 unnecessary page rebuilds:
12
13 * map only cares if the pages are added or removed. Content change does
14   not matter (unless show=title is used).
15 * brokenlinks, orphans, pagecount, ditto (generally)
16 * inline in archive mode cares about page title, author changing, but
17   not content. (Ditto for meta with show=title.)
18 * Causes extra work when solving the [[bugs/transitive_dependencies]]
19   problem.
20
21 ### two types of dependencies needed for [[tracking_bugs_with_dependencies]]
22
23 >>  it seems that there are two types of dependency, and ikiwiki
24 >>  currently only handles one of them.  The first type is "Rebuild this
25 >>  page when any of these other pages changes" - ikiwiki handles this.
26 >>  The second type is "rebuild this page when set of pages referred to by
27 >>  this pagespec changes" - ikiwiki doesn't seem to handle this.  I
28 >>  suspect that named pagespecs would make that second type of dependency
29 >>  more important.  I'll try to come up with a good example. -- [[Will]]
30
31 >>> Hrm, I was going to build an example of this with backlinks, but it
32 >>> looks like that is handled as a special case at the moment (line 458 of
33 >>> render.pm).  I'll see if I can breapk
34 >>> things another way.  Fixing this properly would allow removal of that special case. -- [[Will]]
35
36 >>>> I can't quite understand the distinction you're trying to draw
37 >>>> between the two types of dependencies. Backlinks are a very special
38 >>>> case though and I'll be suprised if they fit well into pagespecs.
39 >>>> --[[Joey]] 
40
41 >>>>> The issue is that the existential pagespec matching allows you to build things that have similar
42 >>>>> problems to backlinks.
43 >>>>> e.g. the following inline:
44
45     \[[!inline pages="define(~done, link(done)) and link(~done)" archive=yes]]
46
47 >>>>> includes any page that links to a page that links to done.  Now imagine I add a new link to 'done' on
48 >>>>> some random page somewhere - a page which some other page links to which didn't previously get included - the set of pages accepted by the pagespec, and hence the set of
49 >>>>> pages inlined, will change.  But, there is no dependency anywhere on the page that I altered, so
50 >>>>> ikiwiki will not rebuild the page with the inline in it.  What is happening is that the page that I altered affects
51 >>>>> the set of pages matched by the pagespec without itself being matched by the pagespec, and hence included in the dependency list.
52
53 >>>>> To make this work well, I think you need to recognise two types of dependencies for each page (and no
54 >>>>> special cases for particular types of links, eg backlinks).  The first type of dependency says, "The content of
55 >>>>> this page depends upon the content of these other pages".  The `add_depends()` in the shortcuts
56 >>>>> plugin is of this form: any time the shortcuts page is edited, any page with a shortcut on it
57 >>>>> is rebuilt.  The inline plugin also needs to add dependencies of this form to detect when the inlined
58 >>>>> content changes.  By contrast, the map plugin does not need a dependency of this form, because it
59 >>>>> doesn't actually care about the content of any pages, just which pages it needs to include (which we'll handle next).
60
61 >>>>> The second type of dependency says, "The content of this page depends upon the exact set of pages matched
62 >>>>> by this pagespec".  The first type of dependency was about the content of some pages, the second type is about
63 >>>>> which pages get matched by a pagespec.  This is the type of dependency tracking that the map plugin needs.
64 >>>>> If the set of pages matched by map pagespec changes, then the page with the map on it needs to be rebuilt to show a different list of pages.
65 >>>>> Inline needs this type of dependency as well as the previous type - This type handles a change in which pages
66 >>>>> are inlined, the previous type handles a change in the content of any of those pages.  Shortcut does not need this type of
67 >>>>> dependency.  Most of the places that use `add_depends()` seem to need this type of dependency rather than the first type.
68
69 >>>>>> Note that inline and map currently achieve the second type of dependency by
70 >>>>>> explicitly calling `add_depends` for each page the displayed.
71 >>>>>> If any of those pages are removed, the regular pagespec would not
72 >>>>>> match them -- since they're gone. However, the explicit dependency
73 >>>>>> on them does cause them to match. It's an ugly corner I'd like to
74 >>>>>> get rid of. --[[Joey]]
75
76 >>>>> Implementation Details:  The first type of dependency can be handled very similarly to the current
77 >>>>> dependency system.  You just need to keep a list of pages that the content depends upon.  You could
78 >>>>> keep that list as a pagespec, but if you do this you might want to check that the pagespec doesn't change,
79 >>>>> possibly by adding a dependency of the second type along with the dependency of the first type.
80
81 >>>>>> An example of the current system not tracking enough data is 
82 >>>>>> described in [[bugs/transitive_dependencies]].
83 >>>>>> --[[Joey]] 
84
85 >>>>> The second type of dependency is a little more tricky.  For each page, we'd need a list of pagespecs that
86 >>>>> the page depended on, and for each pagespec you'd want to store the list of pages that currently match it.
87 >>>>> On refresh, you'd need to check each pagespec to see if the set of pages that match it has changed, and if
88 >>>>> that set has changed, then rebuild the dependent page(s).  Oh, and for this second type of dependency, I
89 >>>>> don't think you can merge pagespecs.  If I wanted to know if either "\*" or "link(done)" changes, then just checking
90 >>>>> to see if the set of pages matched by "\* or link(done)" changes doesn't work.
91
92 >>>>> The current system works because even though you usually want dependencies of the second type, the set of pages
93 >>>>> referred to by a pagespec can only change if one of those pages itself changes.  i.e. A dependency check of the
94 >>>>> first type will catch a dependency change of the second type with current pagespecs.
95 >>>>> This doesn't work with backlinks, and it doesn't work with existential matching.  Backlinks are currently special-cased.  I don't know
96 >>>>> how to special-case existential matching - I suspect you're better off just getting the dependency tracking right.
97
98 >>>>> I also tried to come up with other possible solutions: e.g. can we find the dependencies for a pagespec?  That
99 >>>>> would be the set of pages where a change on one of those pages could lead to a change in the set of pages matched by the pagespec.
100 >>>>> For old-style pagespecs without backlinks, the dependency set for a pagespec is the same as the set of pages the pagespec matches.
101 >>>>> Unfortunately, with existential matching, the set of pages that each
102 >>>>> pagespec depends upon can quickly become "*", which is not very useful.  -- [[Will]]
103
104 ### proposal
105
106 I propose the following. --[[Joey]] 
107
108 * Add a second type of dependency, call it an "presence dependency".
109 * `add_depends` defaults to adding a regular ("full") dependency, as
110   before. (So nothing breaks.)
111 * `add_depends($page, $spec, presence => 0)` adds an presence dependency.
112 * `refresh` only looks at added/removed pages when resolving presence
113   dependencies.
114
115 This seems straightforwardly doable. I'd like [[Will]]'s feedback on it, if
116 possible. The type types of dependencies I am proposing are not identical
117 to the two types he talks about above, but I hope are close enough that
118 they can be used.
119
120 This doesn't deal with the stuff that only depend on the metadata of a
121 page, as collected in the scan pass, changing.  But it does leave a window
122 open for adding such a dependency type later.
123
124 ----
125
126 I implemented the above in a branch.
127 [[!template id=gitbranch branch=origin/dependency-types author="[[joey]]"]]
128
129 Then I found some problems:
130
131 * Something simple like pagecount, that seems like it could use a
132   presence dependency, can have a pagespec that uses metadata, like
133   `author()` or `copyright()`.
134 * pagestats, orphans and brokenlinks cannot use presence dependencies
135   because they need to update when links change.
136
137 Now I'm thinking about having a special dependency look at page
138 metadata, and fire if the metadata changes. And it seems links should
139 either be included in that, or there should be a way to make a dependency
140 that fires when a page's links change. (And what about backlinks?)
141
142 It's easy to see when a page's links change, since there is `%oldlinks`.
143 To see when metadata is changed is harder, since it's stored in the
144 pagestate by the meta plugin. Also, there are many different types of
145 metadata, that would need to be matched with the pagespecs somehow.
146
147 Quick alternative: Make add_depends look at the pagespec. Ie, if it
148 is a simple page name, or a glob, we know a presence dependency
149 can be valid. If's more complex, convert the dependency from
150 presence to full.
151
152 There is a lot to dislike about this method. Its parsing of the pagespec,
153 as currently implemented, does not let plugins add new types of pagespecs
154 that only care about presence. Its pagespec parsing is also subject to
155 false negatives (though these should be somewhat rare, and no false
156 positives). Still, it does work, and it makes things like simple maps and
157 pagecounts much more efficient.
158
159 ----
160
161 #### Will's first pass feedback.
162
163 If the API is going to be updated, then it would be good to make it forward compatible.
164 I'd like for the API to be extendible to what is useful for complex pagespecs, even if we
165 that is a little redundant at the moment.
166
167 My attempt to play with this is in my git repo.  [[!template id=gitbranch branch=origin/depends-spec author="[[will]]"]]
168 That branch is a little out of date, but if you just look at the changes in IkiWiki.pm you'll see the concept I was looking at.
169 I added an "add_depends_spec()" function that adds a dependency on the pagespec passed to it.  If the set of matched pages
170 changes, then the dependent page is rebuilt.  At the moment the implementation uses the same hack used by map and inline -
171 just add all the pages that currently exist as traditional content dependencies.
172
173 > As I note below, a problem with this approach is that it has to try
174 > matching the pagespec against every page, redundantly with the work done
175 > by the plugin. (But there are ways to avoid that redundant matching.)
176 > --[[Joey]] 
177
178 Getting back to commenting on your proposal:
179
180 Just talking about the definition of a "presence dependency" for the moment, and ignoring implementation.  Is a
181 "presence dependency" supposed to cause an update when a page disappears?  I assume so.  Is a presence dependency
182 supposed to cause an update when a pages existence hasn't changed, but it no longer matches the pagespec.
183 (e.g. you use `created_before(test_page)` in a pagespec, and there was a page, `new_page`, that was created
184 after `test_page`.  `new_page` will not match the spec.  Now we'll delete and then re-create `test_page`.  Now
185 `new_page` will match the spec, and yet `new_page` itself hasn't changed.  Nor has its 'presence' - it was present
186 before and it is present now.  Should this cause a re-build of any page that has a 'presence' dependency on the spec?
187
188 > Yes, a presence dep will trigger when a page is added, or removed. 
189
190 > Your example is valid.. but it's also not handled right by normal,
191 > (content) dependencies, for the same reasons. Still, I think I've
192 > addressed it with the pagespec influence stuff below. --[[Joey]]
193
194 I think that is another version of the problem you encountered with meta-data.
195
196 In the longer term I was thinking we'd have to introduce a concept of 'internal pagespec dependencies'.  Note that I'm
197 defining 'internal' pagespec dependencies differently to the pagespec dependencies I defined above.  Perhaps an example:
198 If you had a pagespec that was `created_before(test_page)`, then you could list all pages created before `test_page`
199 with a `map` directive.  The map directive would add a pagespec dependency on `created_before(test_page)`.
200 Internally, there would be a second page-spec parsing function that discovers which pages a given pagespec
201 depends on.  As well as the function `match_created_before()`, we'd have to add a new function `depend_created_before()`.
202 This new function would return a list of pages, which when any of them change, the output of `match_created_before()`
203 would change.  In this example, it would just return `test_page`.
204
205 These lists of dependent pages could just be concatenated for every `match_...()` function in a pagespec - you can ignore
206 the boolean formula aspects of the pagespec for this.  If a content dependency were added on these pages, then I think 
207 the correct rebuilds would occur.  
208
209 In all, this is a surprisingly difficult problem to solve perfectly.  Consider the following case:
210
211 PageA.mdwn:
212
213 > [ShavesSelf]
214
215 PageB.mdwn
216
217 > Doesn't shave self.
218
219 ShavedByBob.mdwn:
220
221 > [!include pages="!link(ShavesSelf)"]
222
223 Does ShavedByBob.mdwn include itself?
224
225 (Yeah - in IkiWiki currently links are *not* included by include, but the idea holds.  I had a good example a while back, but I can't think of it right now.)
226
227 sigh.
228
229 -- [[Will]]
230
231 > I have also been thinking about some sort of analysis pass over pagespecs
232 > to determine what metadata, pages, etc they depend on. It is indeed
233 > tricky to do. More thoughts on influence lists a bit below. --[[Joey]] 
234
235 >> The big part of what makes this tricky is that there may be cycles in the
236 >> dependency graph.  This can lead to situations where the result is just not
237 >> well defined.  This is what I was trying to get at above. -- [[Will]]
238
239 >>> Hmm, I'm not seeing cycles be a problem, at least with the current
240 >>> pagespec terms. --[[Joey]] 
241
242 >>>> Oh, they're not with current pagespec terms.  But this is really close to extending to handle
243 >>>> functional pagespecs, etc.  And I think I'd like to think about that now.
244 >>>>
245 >>>> Having said that, I don't want to hold you up - you seem to be making progress.  The best is
246 >>>> the enemy of the good, etc. etc.
247 >>>>
248 >>>> For my part, I'm imagining we have two more constructs in IkiWiki:
249 >>>>
250 >>>>  * A map directive that actually wikilinks to the pages it links to, and
251 >>>>  * A `match_sharedLink(pageX)` matching function that matches pageY if both pageX and pageY each have links to any same third page, pageZ.
252 >>>>
253 >>>> With those two constructs, one page changing might change the set of pages included in a map somewhere, which might then change the set of pages matched by some other pagespec, which might then...
254 >>>>
255 >>>> --[[Will]]
256
257 >>>>> I think that should be supported by [[bugs/transitive_dependencies]].
258 >>>>> At least in the current implementation, which considers each page
259 >>>>> that is rendered to be changed, and rebuilds pages that are dependent
260 >>>>> on it, in a loop. An alternate implementation, which could be faster,
261 >>>>> is to construct a directed graph and traverse it just once. Sounds
262 >>>>> like that would probably not support what you want to do.
263 >>>>> --[[Joey]]
264
265 >>>>>> Yes - that's what I'm talking about - I'll add some comments there.  -- [[Will]]
266
267 ---- 
268
269 ### Link dependencies
270
271 * `add_depends($page, $spec, links => 1, presence => 1)`
272   adds a links + presence dependency.
273 * Use backlinks change code to detect changes to link dependencies too.
274 * So, brokenlinks can fire whenever any links in any of the
275   pages it's tracking change, or when pages are added or
276   removed.
277 * To determine if a pagespec is valid to be used with a links dependency,
278   use the same set that are valid for presence dependencies. But also
279   allow `backlinks()` to be used in it, since that matches pages
280   that the page links to, which is just what link dependencies are
281   triggered on.
282
283 ----
284
285 ### the removal problem
286
287 So far I have not addressed fixing the removal problem (which Will
288 discusses above).
289
290 Summary of problem: A has a dependency on a pagespec such as
291 "bugs/* and !link(done)". B currently matches. Then B is updated,
292 in a way that makes A's dependency not match it (ie, it links to done).
293 Now A is not updated, because ikiwiki does not realize that it
294 depended on B before.
295
296 This was worked around to fix [[bugs/inline_page_not_updated_on_removal]]
297 by inline and map adding explicit dependencies on each page that appears
298 on them. Then a change to B triggers the explicit dep. While this works,
299 it's 1) ugly 2) probably not implemented by all plugins that could
300 be affected by this problem (ie, linkmap) and 3) is most of the reason why
301 we grew the complication of `depends_simple`.
302
303 One way to fix this is to include with each dependency, a list of pages
304 that currently match it. If the list changes, the dependency is triggered.
305
306 Should be doable, but may involve more work than
307 currently. Consider that a dependency on `bugs/*` currently
308 is triggered by just checking until *one* page is found to match it.
309 But to store the list, *every* page would have to be tried against it.
310 Unless the list can somehow be intelligently updated, looking at only the
311 changed pages.
312
313 ----
314
315 Found a further complication in presence dependencies. Map now uses
316 presence dependencies when adding its explicit dependencies on pages. But
317 this defeats the purpose of the explicit dependencies! Because, now,
318 when B is changed to not match a pagespec, the A's presence dep does
319 not fire.
320
321 I didn't think things through when switching it to use presence
322 dependencies there. But, if I change it to use full dependencies, then all
323 the work that was done to allow map to use presence dependencies for its
324 main pagespec is for naught. The map will once again have to update
325 whenever *any* content of the page changes.
326
327 This points toward the conclusion that explicit dependencies, however they
328 are added, are not the right solution at all. Some other approach, such as
329 maintaining the list of pages that match a dependency, and noticing when it
330 changes, is needed.
331
332 ----
333
334 ### pagespec influence lists
335
336 I'm using this term for the concept of a list of pages whose modification
337 can indirectly influence what pages a pagespec matches.
338
339 > Trying to make a formal definition of this: (Note, I'm using the term sets rather than lists, but they're roughly equivalent)
340 >
341 >  * Let the *matching set* for a pagespec be the set of existing pages that the pagespec matches.
342 >  * Let the *missing document matching set* be the set of pages that would match the spec if they didn't exist. These pages may or may not currently exist.  Note that membership of this set depends upon how the `match_()` functions react to non-existant pages.
343 >  * Let the *indirect influence set* for a pagespec be the set of all pages, *p*, whose alteration might:
344 >    * cause the pagespec to include or exclude a page other than *p*, or
345 >    * cause the pagespec to exclude *p*, unless the alteration is the removal of *p* and *p* is in the missing document matching set.
346 >
347 > Justification: The 'base dependency mechanism' is to compare changed pages against each pagespec.  If the page matches, then rebuild the spec.  For this comparison, creation and removal
348 > of pages are both considered changes.  This base mechanism will catch:
349 >
350 >  * The addition of any page to the matching set through its own modification/creation
351 >  * The removal of any page *that would still match while non-existant* from the matching set through its own removal.  (Note: The base mechanism cannot remove a page from the matching set because of that page's own modification (not deletion).  If the page should be removed matching set, then it obviously cannot match the spec after the change.) 
352 >  * The modification (not deletion) of any page that still matches after the modification.
353 >
354 > The base mechanism may therefore not catch:
355 >
356 >  * The addition or removal of any page from the matching set through the modification/addition/removal of any other page.
357 >  * The removal of any page from the matching set through its own modification/removal if it does not still match after the change.
358 >
359 > The indirect influence set then should handle anything that the base mechanism will not catch.
360 >
361 > --[[Will]]
362
363 >> I appreciate the formalism! 
364 >>
365 >> Only existing pages need to be in these sets, because if a page is added
366 >> in the future, the existing dependency code will always test to see
367 >> if it matches. So it will be in the maching set (or not) at that point.
368 >>
369 >>> Hrm, I agree with you in general, but I think I can come up with nasty counter-examples.  What about a pagespec
370 >>> of "!backlink(bogus)" where the page bogus doesn't exist?  In this case, the page 'bogus' needs to be in the influence
371 >>> set even though it doesn't exist.
372 >>>
373 >>>> I think you're right, this is a case that the current code is not
374 >>>> handling. Actually, I made all the pagespecs return influences
375 >>>> even if the influence was not present or did not match. But, it
376 >>>> currently only records influences as dependencies when a pagespec
377 >>>> successfully matches. Now I'm sure that is wrong, and I've removed
378 >>>> that false optimisation. I've updated some of the below. --[[Joey]]
379 >>>
380 >>> Also, I would really like the formalism to include the whole dependency system, not just any additions to it.  That will make
381 >>> the whole thing much easier to reason about.
382 >>
383 >> The problem with your definition of direct influence set seems to be
384 >> that it doesn't allow `link()` and `title()` to have as an indirect
385 >> influence, the page that matches. But I'm quite sure we need those.
386 >>  --[[Joey]] 
387
388 >>> I see what you mean.  Does the revised definition capture this effectively?
389 >>> The problem with this revised definition is that it still doesn't match your examples below.
390 >>> My revised definition will include pretty much all currently matching pages to be in the influence list
391 >>> because deletion of any of them would cause a change in which pages are matched - the removal problem.
392 >>> -- [[Will]]
393
394 #### Examples
395
396 * The pagespec "created_before(foo)" has an indirect influence list that contains foo.
397   The removal or (re)creation of foo changes what pages match it. Note that
398   this is true even if the pagespec currently fails to match.
399
400 >>> This is an annoying example (hence well worth having :) ).  I think the
401 >>> indirect influence list must contain 'foo' and all currently matching
402 >>> pages.  `created_before(foo)` will not match
403 >>> a deleted page, and so the base mechanism would not cause a rebuild.  The
404 >>> removal problem strikes. -- [[Will]]
405
406 >>>> But `created_before` can in fact match a deleted page. Because the mtime
407 >>>> of a deleted page is temporarily set to 0 while the base mechanism runs to
408 >>>> find changes in deleted pages. (I verified this works by experiment,
409 >>>> also that `created_after` is triggered by a deleted page.) --[[Joey]]
410
411 * The pagespec "foo" has an empty influence list. This is because a
412   modification/creation/removal of foo directly changes what the pagespec
413   matches.
414
415 * The pagespec "*" has an empty influence list, for the same reason.
416   Avoiding including every page in the wiki into its influence list is
417   very important!
418
419 >>> So, why don't the above influence lists contain the currently matched pages?
420 >>> Don't you need this to handle the removal problem? -- [[Will]]
421
422 >>>> The removal problem is slightly confusingly named, since it does not
423 >>>> affect pages that were matched by a glob and have been removed. Such
424 >>>> pages can be handled without being influences, because ikiwiki knows
425 >>>> they have been removed, and so can still match them against the
426 >>>> pagespec, and see they used to match; and thus knows that the
427 >>>> dependency has triggered.
428 >>>>
429 >>>>> IkiWiki can only see that they used to match if they're in the glob matching set.  -- [[Will]]
430 >>>>
431 >>>> Maybe the thing to do is consider this an optimisation, where such
432 >>>> pages are influences, but ikiwiki is able to implicitly find them,
433 >>>> so they do not need to be explicitly stored. --[[Joey]]
434
435 * The pagespec "title(foo)" has an influence list that contains every page
436   that currently matches it. A change to any matching page can change its
437   title, making it not match any more, and so the list is needed due to the
438   removal problem. A page that does not have a matching title is not an
439   influence, because modifying the page to change its title directly
440   changes what the pagespec matches.
441
442 * The pagespec "backlink(index)" has an influence list
443   that contains index (because a change to index changes the backlinks).
444   Note that this is true even if the backlink currently fails.
445
446 >>> This is another interesting example.  The missing document matching set contains all links on the page index, and so
447 >>> the influence list only needs to contain 'index' itself.  -- [[Will]]
448
449 * The pagespec "link(done)" has an influence list that
450   contains every page that it matches. A change to any matching page can
451   remove a link and make it not match any more, and so the list is needed
452   due to the removal problem.
453
454 >> Why doesn't this include every page?  If I change a page that doesn't have a link to
455 >> 'done' to include a link to 'done', then it will now match...  or is that considered a
456 >> 'direct match'? -- [[Will]]
457
458 >>> The regular dependency calculation code will check if every changed
459 >>> page matches every dependency. So it will notice the link was added.
460 >>> --[[Joey]] 
461
462 #### Low-level Calculation
463
464 One way to calculate a pagespec's influence would be to
465 expand the SuccessReason and FailReason objects used and returned
466 by `pagespec_match`. Make the objects be created with an
467 influence list included, and when the objects are ANDed or ORed
468 together, combine the influence lists.
469
470 That would have the benefit of allowing just using the existing `match_*`
471 functions, with minor changes to a few of them to gather influence info.
472
473 But does it work? Let's try some examples:
474
475 Consider "bugs/* and link(done) and backlink(index)".
476
477 Its influence list contains index, and it contains all pages that the whole
478 pagespec matches. It should, ideally, not contain all pages that link
479 to done. There are a lot of such pages, and only a subset influence this
480 pagespec.
481
482 When matching this pagespec against a page, the `link` will put the page
483 on the list. The `backlink` will put index on the list, and they will be
484 anded together and combined. If we combine the influences from each
485 successful match, we get the right result.
486
487 Now consider "bugs/* and link(done) and !backlink(index)".
488
489 It influence list is the same as the previous one, even though a term has
490 been negated. Because a change to index still influences it, though in a
491 different way.
492
493 If negation of a SuccessReason preserves the influence list, the right
494 influence list will be calculated.
495
496 Consider "bugs/* and (link(done) or backlink(index))"
497 and      "bugs/* and (backlink(index) or link(done))'
498
499 Its clear that the influence lists for these are identical. And they
500 contain index, plus all matching pages.
501
502 When matching the first against page P, the `link` will put P on the list.
503 The OR needs to be a non-short-circuiting type. (In perl, `or`, not `||` --
504 so, `pagespec_translate` will need to be changed to not use `||`.)
505 Given that, the `backlink` will always be evalulated, and will put index
506 onto the influence list. If we combine the influences from each
507 successful match, we get the right result.
508
509 > This is implemented, seems to work ok. --[[Joey]]
510
511 > `or` short-circuits too, but the implementation correctly uses `|`,
512 > which I assume is what you meant. --[[smcv]]
513
514 >> Er, yeah. --[[Joey]] 
515
516 ----
517
518 What about: "!link(done)"
519
520 Specifically, I want to make sure it works now that I've changed
521 `match_link` to only return a page as an influence if it *does*
522 link to done.
523
524 So, when matching against page P, that does not link to done,
525 there are no influences, and the pagespec matches. If P is later
526 changed to add a link to done, then the dependency resolver will directly
527 notice that.
528
529 When matching against page P, that does link to done, P
530 is an influence, and the pagespec does not match. If P is later changed
531 to not link to done, the influence will do its job.
532
533 Looks good!
534
535 ----
536
537 Here is a case where this approach has some false positives.
538
539 "bugs/* and link(patch)"
540
541 This finds as influences all pages that link to patch, even
542 if they are not under bugs/, and so can never match.
543
544 To fix this, the influence calculation would need to consider boolean
545 operators. Currently, this turns into roughly:
546
547 `FailReason() & SuccessReason(patch)`
548
549 Let's say that the glob instead returns a HardFailReason, which when
550 ANDed with another object, drops their influences. (But when ORed, combines
551 them.) Fixes the above, but does it always work?
552
553 "(bugs/* or link(patch)) and backlink(index)" =>
554 `( HardFailReason() | SuccessReason(page) ) & SuccessReason(index)`` =>
555 `SuccessReason(page & SuccessReason(index)` =>
556 SuccessReason(page, index) => right
557
558 "(bugs/* and link(patch)) or backlink(index)" =>
559 `( HardFailReason() & SuccessReason(page) ) | SuccessReason(index)`` =>
560 `HardFailReason() | SuccessReason(index)` =>
561 `SuccessReason(index)` => right
562
563 "!bugs/* and link(patch)" =>
564 `HardFailReason() | SuccessReason(bugs/foo)` =>  
565 `HardFailReason()` => right
566
567 #### High-level Calculation and Storage
568
569 Naively calculating the full influence list for a pagespec requires trying
570 to match it against every page in the wiki. I'd like to avoid doing such
571 expensive matching redundantly.
572
573 It may be possible, for some types of pagespecs, to just try matching a
574 single, arbitrary page against it, and know the full influence list has
575 been obtained. It seems to be that case that if a pagespec has any
576 influences, matching any page will return at least one. So if none are
577 returned, we can skip trying other pages.
578
579 If the influence list does not include the page that was tried, we know
580 that the pagespec does not things like `link()` and `title()`, that are
581 influenced by the page's own content. So it *might* be safe to not try
582 matching any more pages in this case too. I think it would work for all
583 current pagespec terms. There might be a hypothetical term where this
584 optimisation doesn't work. We could add a special case to ensure it can
585 work: If a term declares it is unfluenced by "", then it means it is
586 always influenced by the matching page.
587
588 Anyway, this seems worth doing: Add a `pagespec_match_all`, which returns a
589 list of all pages in the whole wiki that match the pagespec, and also adds
590 the pagespec as a dependency, and while it's at it, calculates and stores
591 the influence list.
592
593 It could have an optional sort parameter, and limit parameter, to control
594 how many items to return and the sort order. So when inline wants to
595 display the 10 newest, only the influence lists for those ten are added.
596
597 If `pagespec_match_depends` can be used by all plugins, then great,
598 influences are automatically calculated, no extra work needs to be done.
599
600 If not, and some plugins still need to use `pagespec_match_list` or
601 `pagespec_match`, and `add_depends`, then I guess that `add_depends` can do
602 a slightly more expensive influence calculation.
603
604 Bonus: If `add_depends` is doing an influence calculation, then I can remove
605 the nasty hack it currently uses to decide if a given pagespec is safe to use
606 with an existence or links dependency.
607
608 Where to store the influence list? Well, it appears that we can just add
609 (content) dependencies for each item on the list, to the page's
610 regular list of simple dependencies. So, the data stored ends up looking
611 just like what is stored today by the explicit dependency hacks. Except,
612 it's calculated more smartly, and is added automatically.
613
614 > I've implemented influence calculation in `add_depends`. As expected,
615 > it means rather a lot more work, and makes some things much slower.
616 > Optimisations next.. --[[Joey]] 
617
618 #### Influence types
619
620 Note that influences can also have types, same as dependency types.
621 For example, "backlink(foo)" has an influence of foo, of type links.
622 "created_before(foo)" also is influenced by foo, but it's a presence
623 type. Etc.
624
625 > This is an interesting concept that I hadn't considered.  It might
626 > allow significant computational savings, but I suspect will be tricky
627 > to implement. -- [[Will]]
628
629 >> It was actually really easy to implement it, assuming I picked the right
630 >> dependency types of course. --[[Joey]]