]> git.vanrenterghem.biz Git - git.ikiwiki.info.git/blob - doc/todo/tracking_bugs_with_dependencies.mdwn
Fix example blog's tags/life to not have a broken PageSpec. Closes: #543510
[git.ikiwiki.info.git] / doc / todo / tracking_bugs_with_dependencies.mdwn
1 [[!tag patch patch/core]]
3 I like the idea of [[tips/integrated_issue_tracking_with_ikiwiki]], and I do so on several wikis.  However, as far as I can tell, ikiwiki has no functionality which can represent dependencies between bugs and allow pagespecs to select based on dependencies.  For instance, I can't write a pagespec which selects all bugs with no dependencies on bugs not marked as done.  --[[JoshTriplett]]
5 > I started having a think about this.  I'm going to start with the idea that expanding
6 > the pagespec syntax is the way to attack this.  It seems that any pagespec that is going
7 > to represent "all bugs with no dependencies on bugs not marked as done" is going to
8 > need some way to represent "bugs not marked as done" as a collection of pages, and
9 > then represent "bugs which do not link to pages in the previous collection".
10 >
11 > One way to do this would be to introduce variables into the pagespec, along with
12 > universal and/or existential [[!wikipedia Quantification]].  That looks quite complex.
13 >
14 >> I thought about this briefly, and got about that far.. glad you got
15 >> further. :-) --[[Joey]]
17 >> Or, one [[!taglink could_also_refer|pagespec_in_DL_style]] to the language of [[!wikipedia description logics]]: their formulas actually define classes of objects through quantified relations to other classes. --Ivan Z.
18
19 > Another option would be go with a more functional syntax.  The concept here would
20 > be to allow a pagespec to appear in a 'pagespec function' anywhere a page can.  e.g.
21 > I could pass a pagespec to `link()` and that would return true if there is a link to any
22 > page matching the pagespec.  This makes the variables and existential quantification
23 > implicit.  It would allow the example requested above:
24 >
25 >> `bugs/* and !*/Discussion and !link(bugs/* and !*/Discussion and !link(done))`
26 >
27 > Unfortunately, this is also going to make the pagespec parsing more complex because
28 > we now need to parse nested sets of parentheses to know when the nested pagespec
29 > ends, and that isn't a regular language (we can't use regular expression matching for
30 > easy parsing).
31 >
32 >> Also, it may cause ambiguities with page names that contain parens
33 >> (though some such ambigutities already exist with the pagespec syntax).
34 >
35 > One simplification of that would be to introduce some pagespec [[shortcuts]].  We could
36 > then allow pagespec functions to take either pages, or named pagespec shortcuts.  The
37 > pagespec shortcuts would just be listed on a special page, like current [[shortcuts]].
38 > (It would probably be a good idea to require that shortcuts on that page can only refer
39 > to named pagespecs higher up that page than themselves.  That would stop some
40 > looping issues...)  These shortcuts would be used as follows: when trying to match
41 > a page (without globs) you look to see if the page exists.  If it does then you have a
42 > match.  If it doesn't, then you look to see if a similarly named pagespec shortcut
43 > exists.  If it does, then you check that pagespec recursively to see if you have a match.
44 > The ordering requirement on named pagespecs stops infinite recursion.
45 >
46 > Does that seem like a reasonable first approach?
47 >
48 > -- [[Will]]
50 >> Having a separate page for the shortcuts feels unwieldly.. perhaps
51 >> instead the shortcut could be defined earlier in the scope of the same
52 >> pagespec that uses it?
53 >> 
54 >> Example: `define(~bugs, bugs/* and !*/Discussion) and define(~openbugs, ~bugs and !link(done)) and ~openbugs and !link(~openbugs)`
56 >>> That could work.  parens are only ever nested 1 deep in that grammar so it is regular and the current parsing would be ok.
58 >> Note that I made the "~" explicit, not implicit, so it could be left out. In the case of ambiguity between
59 >> a definition and a page name, the definition would win.
61 >>> That was my initial thought too :), but when implementing it I decided that requiring the ~ made things easier.  I'll probably require the ~ for the first pass at least.
63 >> So, equivilant example: `define(bugs, bugs/* and !*/Discussion) and define(openbugs, bugs and !link(done)) and openbugs and !link(openbugs)`
64 >> 
66 >> Re recursion, it is avoided.. but building a pagespec that is O(N^X) where N is the
67 >> number of pages in the wiki is not avoided. Probably need to add DOS prevention.
68 >>  --[[Joey]]
70 >>> If you memoize the outcomes of the named pagespecs you can make in O(N.X), no?
71 >>> -- [[Will]]
73 >>>> Yeah, guess that'd work. :-)
75 > <a id="another_kind_of_links" />One quick further thought.  All the above discussion assumes that 'dependency' is the
76 > same as 'links to', which is not really true.  For example, you'd like to be able to say
77 > "This bug does not depend upon [ [ link to other bug ] ]" and not have a dependency.
78 > Without having different types of links, I don't see how this would be possible.
79 >
80 > -- [[Will]]
82 >> I saw that this issue is targeted at by the work on [[structured page data#another_kind_of_links]]. --Ivan Z.
84 Okie - I've had a quick attempt at this.  Initial patch attached.  This one doesn't quite work.
85 And there is still a lot of debugging stuff in there.
87 At the moment I've added a new preprocessor plugin, `definepagespec`, which is like
88 shortcut for pagespecs.  To reference a named pagespec, use `~` like this:
90     [ [!definepagespec name="bugs" spec="bugs/* and !*/Discussion"]]
91     [ [!definepagespec name="openbugs" spec="~bugs and !link(done)"]]
92     [ [!definepagespec name="readybugs" spec="~openbugs and !link(~openbugs)"]]
94 At the moment the problem is in `match_link()` when we're trying to find a sub-page that
95 matches the appropriate page spec.  There is no good list of pages available to iterate over.
97     foreach my $nextpage (keys %IkiWiki::pagesources)
99 does not give me a good list of pages.  I found the same thing when I was working on
100 this todo [[todo/Add_a_plugin_to_list_available_pre-processor_commands]].
102 > I'm not sure why iterating over `%pagesources` wouldn't work here, it's the same method
103 > used by anything that needs to match a pagespec against all pages..? --[[Joey]]
105 >> My uchecked hypothesis is that %pagesources is created after the refresh hook.
106 >> I've also been concerned about how globally defined pagespec shortcuts would interact with
107 >> the page dependancy system.  Your idea of internally defined shortcuts should fix that. -- [[Will]]
109 >>> You're correct, the refresh hook is run very early, before pagesources
110 >>> is populated. (It will be partially populated on a refresh, but will
111 >>> not be updated to reflect new pages.) Agree that internally defined
112 >>> seems the way to go. --[[Joey]]
114 Immediately below is a patch which seems to basically work.  Lots of debugging code is still there
115 and it needs a cleanup, but I thought it worth posting at this point.  (I was having problems
116 with old style glob lists, so i just switched them off for the moment.)
118 The following three inlines work for me with this patch:
120     Bugs:
121     
122     [ [!inline pages="define(~bugs, bugs/* and ! */Discussion) and ~bugs" archive="yes"]]
123     
124     OpenBugs:
125     
126     [ [!inline pages="define(~bugs, bugs/* and ! */Discussion) and define(~openbugs,~bugs and !link(done)) and ~openbugs" archive="yes"]]
127     
128     ReadyBugs:
129     
130     [ [!inline pages="define(~bugs, bugs/* and ! */Discussion) and define(~openbugs,~bugs and !link(done)) and define(~readybugs,~openbugs and !link(~openbugs)) and ~readybugs" archive="yes"]]
132 > Nice! Could the specfuncsref be passed in %params? I'd like to avoid
133 > needing to change the prototype of every pagespec function, since several
134 > plugins define them too. --[[Joey]]
136 >> Maybe - it needs more thought.  I also considered it when I was going though changing all those plugins :).
137 >> My concern was that `%params` can contain other user-defined parameters,
138 >> e.g. `link(target, otherparameter)`, and that means that the specFuncs could be clobbered by a user (or other
139 >> weird security hole).  I thought it better to separate it, but I didn't think about it too hard.  I might move it to
140 >> the first parameter rather than the second.  Ikiwiki is my first real perl hacking and I'm still discovering
141 >> good ways to write things in perl.
142 >>
143 >>>> `%params` contains the parameters passed to `pagespec_match`, not
144 >>>> user-supplied parameters. The user-supplied parameter to a function
145 >>>> like `match_glob()` or `match_link()` is passed in the second positional parameter. --[[Joey]]
147 >>>>> OK.  That seems reasonable then.  The only problem is that my PERLfu is not strong enough to make it
148 >>>>> work.  I really have to wonder what substance was influencing the designers of PERL...
149 >>>>> I can't figure out how to use the %params.  And I'm pissed off enough with PERL that I'm not going
150 >>>>> to try and figure it out any more.  There are two patches below now.  The first one uses an extra
151 >>>>> argument and works.  The second one tries to use %params and doesn't - take your pick :-). -- [[Will]]
153 >> What do you think is best to do about `is_globlist()`?  At the moment it requires that the 'second word', as
154 >> delimited by a space and ignoring parens, is 'and' or 'or'.  This doesn't hold in the above example pagespecs (so I just hard wired it to 0 to test my patch).
155 >> My thought was just to search for 'and' or 'or' as words anywhere in the pagespec.  Thoughts?
157 >>> Dunno, we could just finish deprecating it. Or change the regexp to
158 >>> skip over spaces in parens. (`/[^\s]+\s+([^)]+)/`) --[[Joey]]
160 >>>> I think I have a working regexp now.
162 >> Oh, one more thing.  In pagespec_translate (now pagespec_makeperl), there is a part of the regular expression for `# any other text`.
163 >> This contained `()`, which has no effect.  I replaced that with `\(\)`, but that is a change in the definition of pagespecs unrelated to the
164 >> rest of this patch. In a related change, commands were not able to contain `)` in their parameters.  I've extended that so the cannot
165 >> contain `(` or `)`.  -- [[Will]]
167 >>> `[^\s()]+` is a character class matching all characters not spaces or
168 >>> parens. Since the pervious terminals in the regexp consume most
169 >>> occurances of an open paren or close paren, it's unlikely for one to
170 >>> get through to that part of the regexp. For example, "foo()" will be
171 >>> matched by the command matcher; "(foo)" will be matched by the open
172 >>> paren literal terminal. "foo(" and "foo)" can get through to the
173 >>> end, and would be matched as a page name, if it didn't exclude parens.
174 >>>
175 >>> So why exclude them? Well, consider "foo and(bar and baz)". We don't
176 >>> want it to match "and(" as a page name!
177 >>> 
178 >>> Escaping the parens in the character class actually changes nothing; the
179 >>> changed character class still matches all characters not spaces or
180 >>> parens. (Try it!).
181 >>> 
182 >>> Re commands containing '(', I don't really see any reason not to
183 >>> allow that, unless it breaks something. --[[Joey]]
185 >>>> Oh, I didn't realise you didn't need to escape parens inside [].  All else I
186 >>>> I understood.  I have stopped commands from containing parens because
187 >>>> once you allow that then you might have a extra level of depth in the parsing
188 >>>> of define() statements. -- [[Will]]
190 >>> Updated patch.  Moved the specFuncsRef to the front of the arg list.  Still haven't thought through the security implications of
191 >>> having it in `%params`.  I've also removed all the debugging `print` statements.  And I've updated the `is_globlist()` function.
192 >>> I think this is ready for people other than me to have a play.  It is not well enough tested to commit just yet.
193 >>> -- [[Will]]
195 I've lost track of the indent level, so I'm going back to not indented - I think this is a working [[patch]] taking into
196 account all comments above (which doesn't mean it is above reproach :) ).  --[[Will]]
198 > Very belated code review of last version of the patch:
199
200 > * `is_globlist` is no longer needed
202 >> Good :)
204 > * I don't understand why the pagespec match regexp is changed
205 >   from having flags `igx` to `ixgs`. Don't see why you
206 >   want `.` to match '\n` in it, and don't see any `.` in the regexp 
207 >   anyway?
209 >> Because you have to define all the named pagespecs in the pagespec, you sometimes end up with very long pagespecs.  I found it useful to split them over multiple lines.  That didn't work at one point and I added the 's' to make it work.  I may have further altered the regex since then to make the 's' redundant.  Remove it and see if multi-line pagespecs still work. :)
211 >>> Well, I can tell you that multi-line pagespecs are supported w/o
212 >>> your patch .. I use them all the time. The reason I find your
213 >>> use of `/s` unlikely is because without it `\s` already matches
214 >>> a newline. Only if you want to treat a newline as non-whitespace
215 >>> is `/s` typically necessary. --[[Joey]] 
217 > * Some changes of `@_` to `%params` in `pagespec_makeperl` do not
218 >   make sense to me. I don't see where \%params is defined and populated,
219 >   except with `\$params{specFunc}`.
221 >> I'm not a perl hacker.  This was a mighty battle for me to get going.
222 >> There is probably some battlefield carnage from my early struggles
223 >> learning perl left here. Part of this is that @_ / @params already
224 >> existed as a way of passing in extra parameters.  I didn't want to
225 >> pollute that top level namespace - just at my own parameter (a hash)
226 >> which contained the data I needed.
228 >>> I think I understand how the various `%params`
229 >>> (there's not just one) work in your code now, but it's really a mess.
230 >>> Explaining it in words would take pages.. It could be fixed by,
231 >>> in `pagespec_makeperl` something like:
232 >>> 
233 >>>     my %specFuncs;
234 >>>     push @_, specFuncs => \%specFuncs;
235 >>> 
236 >>> With that you have the hash locally available for populating
237 >>> inside `pagespec_makeperl`, and when the `match_*` functions
238 >>> are called the same hash data will be available inside their
239 >>> `@_` or `%params`. No need to change how the functions are called
240 >>> or do any of the other hacks.
241 >>>
242 >>> Currently, specFuncs is populated by building up code
243 >>> that recursively calls `pagespec_makeperl`, and is then
244 >>> evaluated when the pagespec gets evaluated. My suggested
245 >>> change to `%params` will break that, but that had to change 
246 >>> anyway.
247 >>>
248 >>> It probably has a security hole, and is certianly inviting
249 >>> one, since the pagespec definition is matched by a loose regexp (`.*`)
250 >>> and then subject to string interpolation before being evaluated
251 >>> inside perl code. I recently changed ikiwiki to never interpolate
252 >>> user-supplied strings when translating pagespecs, and that
253 >>> needs to happen here too. The obvious way, it seems to me,
254 >>> is to not generate perl code, but just directly run perl code that
255 >>> populates specFuncs.
257 >>>> I don't think this is as bad as you make out, but your addition of the
258 >>>> data array will break with the recursion my patch adds in pagespec_makeperl.
259 >>>> To fix that I'll need to pass a reference to that array into pagespec_makeperl.
260 >>>> I think I can then do the same thing to $params{specFuncs}.  -- [[Will]]
262 >>>>> You're right -- I did not think the recursive case through.
263 >>>>> --[[Joey]] 
265 > * Seems that the only reason `match_glob` has to check for `~` is
266 >   because when a named spec appears in a pagespec, it is translated
267 >   to `match_glob("~foo")`. If, instead, `pagespec_makeperl` checked
268 >   for named specs, it could convert them into `check_named_spec("foo")`
269 >   and avoid that ugliness.
271 >> Yeah - I wanted to make named specs syntactically different on my first pass.  You are right in that this could be made a fallback - named specs always override pagenames.
273 > * The changes to `match_link` seem either unecessary, or incomplete.
274 >   Shouldn't it check for named specs and call
275 >   `check_named_spec_existential`?
277 >>  An earlier version did.  Then I realised it wasn't actually needed in that case - match_link() already included a loop that was like a type of existential matching.  Each time through the loop it would
278 >> call match_glob().  match_glob() in turn will handle the named spec.  I tested this version briefly and it seemed to work.  I remember looking at this again later and wondering if I had mis-understood
279 >> some of the logic in match_link(), which might mean there are cases where you would need an explicit call to check_named_spec_existential() - I never checked it properly after having that thought.
281 >>> In the common case, `match_link` does not call `match_glob`,
282 >>> because the link target it is being asked to check for is a single
283 >>> page name, not a glob.
285 >>>> A named pagespec should fall into the glob case.  These two pagespecs should be the same:
287     link(a*)
289 >>>> and
291     define(aStar, a*) and link(~aStar)
293 >>>> In the first case, we want the pagespec to match any page that links to a page matching the glob.
294 >>>> In the second case, we want the pagespec to match any page that links to a page matching the named spec.
295 >>>> match_link() was already doing existential part.  The patches to this code were simply to remove the `lc()`
296 >>>> call from the named pagespec name.  Can that `lc` be removed entirely? -- [[Will]]
298 >>>>> I think we could get rid of it. `bestlink` will lc it itself
299 >>>>> if the uppercase version does not exist; `match_glob` matches
300 >>>>> insensitively.
301 >>>>> --[[Joey]] 
303 > * Generally, the need to modify `match_*` functions so that they
304 >   check for and handle named pagespecs seems suboptimal, if
305 >   only because there might be others people may want to use named
306 >   pagespecs with. It would be possible to move this check
307 >   to `pagespec_makeperl`, by having it check if the parameter
308 >   passed to a pagespec function looked like a named pagespec.
309 >   The only issue is that some pagespec functions take a parameter
310 >   that is not a page name at all, and it could be weird
311 >   if such a parameter were accidentially interpreted as a named
312 >   pagespec. (But, that seems unlikely to happen.)
314 >> Possibly.  I'm not sure which I prefer between the current solution and that one.  Each have advantages and disadvantages.
315 >> It really isn't much code for the match functions to add a call to check_named_spec_existential().
317 >>> But if a plugin adds its own match function, it has
318 >>> to explicitly call that code to support named pagespecs.
320 >>>> Yes, and it can do that in just three lines of code.  But if we automatically check for named pagespecs all the time we
321 >>>> potentially break any matching function that doesn't accept pages, or wants to use multiple arguments.
323 >>>>> 3 lines of code, plus the functions called become part of the API,
324 >>>>> don't forget about that..
325 >>>>>
326 >>>>> Yes, I think that is the tradeoff, the question is whether to export
327 >>>>> the additional complexity needed for that flexability.
328 >>>>>
329 >>>>> I'd be suprised if multiple argument pagespecs become necessary..
330 >>>>> with the exception of this patch there has been no need for them yet.
331 >>>>>
332 >>>>> There are lots of pagespecs that take data other than pages,
333 >>>>> indeed, that's really the common case. So far, none of them 
334 >>>>> seem likely to take data that starts with a `~`. Perhaps
335 >>>>> the thing to do would be to check if `~foo` is a known,
336 >>>>> named pagespec, and if not, just pass it through unchanged.
337 >>>>> Then there's little room for ambiguity, and this also allows
338 >>>>> pagespecs like `glob(~foo*)` to match the literal page `~foo`.
339 >>>>> (It will make pagespec_merge even harder tho.. see below.)
340 >>>>> --[[Joey]] 
342 >>>>>> I've already used multi-argument pagespec match functions in
343 >>>>>> my data plugin.  It is used for having different types of links.  If
344 >>>>>> you want to have multiple types of links, then the match function
345 >>>>>> for them needs to take both the link name and the link type.
346 >>>>>> I'm trying to think of a way we could have both - automatically
347 >>>>>> handle the existential case unless the function indicates somehow
348 >>>>>> that it'll do it itself.  Any ideas?  -- [[Will]]
350 > * I need to check if your trick to avoid infinite recursion
351 >   works if there are two named specs that recursively
352 >   call one-another. I suspect it does, but will test this
353 >   myself..
355 >> It worked for me. :)
357 > * I also need to verify if memoizing the named pagespecs has
358 >   really guarded against very expensive pagespecs DOSing the wiki..
360 > --[[Joey]] 
362 >>  There is one issue that I've been thinking about that I haven't raised anywhere (or checked myself), and that is how this all interacts with page dependencies.
363 >>  Firstly, I'm not sure anymore that the `pagespec_merge` function will continue to work in all cases.
365 >>> The problem I can see there is that if two pagespecs
366 >>> get merged and both use `~foo` but define it differently,
367 >>> then the second definition might be used at a point when
368 >>> it shouldn't (but I haven't verified that really happens).
369 >>> That could certianly be a show-stopper. --[[Joey]] 
371 >>>> I think this can happen in the new closure based code.  I don't think this could happen in the old code.  -- [[Will]]
373 >>>> Even if that works, this is a good argument for having a syntactic difference between named pagespecs and normal pages.
374 >>>> If you're joining two pagespecs with 'or', you don't want a named pagespec in the first part overriding a page name in the
375 >>>> second part.  Oh, and I assume 'or' has the right operator precedence that "a and b or c" is "(a and b) or c", and not "a and (b or c)" -- [[Will]]
377 >>>>> Looks like its bracketed in the code anyway... -- [[Will]]
379 >>>> Perhaps the thing to do is to have a `clear_defines()`
380 >>>> function, then merging `A` and `B` yields `(A) or (clear_defines() and (B))`
381 >>>> That would deal with both the cases where `A` and `B` differently
382 >>>> define `~foo` as well as with the case where `A` defines `~foo` while
383 >>>> `B` uses it to refer to a literal page.
384 >>>> --[[Joey]]
386 >>>>> I don't think this will work with the new patch, and I don't think it was needed with the old one.
387 >>>>> Under the old patch, pagespec_makeperl() generated a string of unevaluated, self-contained, perl
388 >>>>> code.  When a new named pagespec was defined, a recursive call was made to get the perl code
389 >>>>> for the pagespec, and then that code was used to add something like `$params{specFuncs}->{name} = sub {recursive code} and `
390 >>>>> to the result of the calling function.  This means that at pagespec testing time, when this code is executed, the
391 >>>>> specFuncs hash is built up as the pagespec is checked.  In the case of the 'or' used above, later redefinitions of
392 >>>>> a named pagespec would have redefined the specFunc at the right time.  It should have just worked.  However...
394 >>>>> Since my original patch, you started using closures for security reasons (and I can see the case for that).  Unfortunately this
395 >>>>> means that the generated perl code is no longer self-contained - it needs to be evaluated in the same closure it was generated
396 >>>>> so that it has access to the data array.  To make this work with the recursive call I had two options: a) make the data array a
397 >>>>> reference that I pass around through the pagespec_makeperl() functions and have available when the code is finally evaluated
398 >>>>> in pagespec_translate(), or b) make sure that each pagespec is evaluated in its correct closure and a perl function is returned, not a
399 >>>>> string containing unevaluated perl code.
401 >>>>> I went with option b).  I did it in such a way that the hash of specfuncs is built up at translation time, not at execution time.  This
402 >>>>> means that with the new code you can call specfuncs that get defined out of order:
404     ~test and define(~test, blah)
406 >>>>> but it also means that using a simple 'or' to join two pagespecs wont work.  If you do something like this:
408     ~test and define(~test, foo) and define(~test, baz)
410 >>>>> then the last definition (baz) takes precedence.
411 >>>>> In the process of writing this I think I've come up with a way to change this back the way it was, still using closures. -- [[Will]]
413 >>> Alternatively, my [[remove-pagespec-merge|should_optimise_pagespecs]]
414 >>> branch solves this, in a Gordian knot sort of way :-) --[[smcv]]
416 >>  Secondly, it seems that there are two types of dependency, and ikiwiki
417 >>  currently only handles one of them.  The first type is "Rebuild this
418 >>  page when any of these other pages changes" - ikiwiki handles this.
419 >>  The second type is "rebuild this page when set of pages referred to by
420 >>  this pagespec changes" - ikiwiki doesn't seem to handle this.  I
421 >>  suspect that named pagespecs would make that second type of dependency
422 >>  more important.  I'll try to come up with a good example. -- [[Will]]
424 >>> Hrm, I was going to build an example of this with backlinks, but it
425 >>> looks like that is handled as a special case at the moment (line 458 of
426 >>> render.pm).  I'll see if I can breapk
427 >>> things another way.  Fixing this properly would allow removal of that special case. -- [[Will]]
429 >>>> I can't quite understand the distinction you're trying to draw
430 >>>> between the two types of dependencies. Backlinks are a very special
431 >>>> case though and I'll be suprised if they fit well into pagespecs.
432 >>>> --[[Joey]] 
434 >>>>> The issue is that the existential pagespec matching allows you to build things that have similar
435 >>>>> problems to backlinks.
436 >>>>> e.g. the following inline:
438     \[[!inline pages="define(~done, link(done)) and link(~done)" archive=yes]]
440 >>>>> includes any page that links to a page that links to done.  Now imagine I add a new link to 'done' on
441 >>>>> 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
442 >>>>> pages inlined, will change.  But, there is no dependency anywhere on the page that I altered, so
443 >>>>> ikiwiki will not rebuild the page with the inline in it.  What is happening is that the page that I altered affects
444 >>>>> the set of pages matched by the pagespec without itself being matched by the pagespec, and hence included in the dependency list.
446 >>>>> To make this work well, I think you need to recognise two types of dependencies for each page (and no
447 >>>>> special cases for particular types of links, eg backlinks).  The first type of dependency says, "The content of
448 >>>>> this page depends upon the content of these other pages".  The `add_depends()` in the shortcuts
449 >>>>> plugin is of this form: any time the shortcuts page is edited, any page with a shortcut on it
450 >>>>> is rebuilt.  The inline plugin also needs to add dependencies of this form to detect when the inlined
451 >>>>> content changes.  By contrast, the map plugin does not need a dependency of this form, because it
452 >>>>> doesn't actually care about the content of any pages, just which pages it needs to include (which we'll handle next).
454 >>>>> The second type of dependency says, "The content of this page depends upon the exact set of pages matched
455 >>>>> by this pagespec".  The first type of dependency was about the content of some pages, the second type is about
456 >>>>> which pages get matched by a pagespec.  This is the type of dependency tracking that the map plugin needs.
457 >>>>> 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.
458 >>>>> Inline needs this type of dependency as well as the previous type - This type handles a change in which pages
459 >>>>> are inlined, the previous type handles a change in the content of any of those pages.  Shortcut does not need this type of
460 >>>>> dependency.  Most of the places that use `add_depends()` seem to need this type of dependency rather than the first type.
462 >>>>>> Note that inline and map currently achieve the second type of dependency by
463 >>>>>> explicitly calling `add_depends` for each page the displayed.
464 >>>>>> If any of those pages are removed, the regular pagespec would not
465 >>>>>> match them -- since they're gone. However, the explicit dependency
466 >>>>>> on them does cause them to match. It's an ugly corner I'd like to
467 >>>>>> get rid of. --[[Joey]]
469 >>>>> Implementation Details:  The first type of dependency can be handled very similarly to the current
470 >>>>> dependency system.  You just need to keep a list of pages that the content depends upon.  You could
471 >>>>> keep that list as a pagespec, but if you do this you might want to check that the pagespec doesn't change,
472 >>>>> possibly by adding a dependency of the second type along with the dependency of the first type.
474 >>>>>> An example of the current system not tracking enough data is 
475 >>>>>> where A inlines B which inlines C. A change to C will cause B to
476 >>>>>> rebuild, but A will not "notice" that B has implicitly changed.
477 >>>>>> That example suggests it might be fixable without explicitly storing
478 >>>>>> data, by causing a rebuild of B to be treated as a change to B.
479 >>>>>> --[[Joey]] 
481 >>>>> The second type of dependency is a little more tricky.  For each page, we'd need a list of pagespecs that
482 >>>>> the page depended on, and for each pagespec you'd want to store the list of pages that currently match it.
483 >>>>> On refresh, you'd need to check each pagespec to see if the set of pages that match it has changed, and if
484 >>>>> that set has changed, then rebuild the dependent page(s).  Oh, and for this second type of dependency, I
485 >>>>> don't think you can merge pagespecs.  If I wanted to know if either "\*" or "link(done)" changes, then just checking
486 >>>>> to see if the set of pages matched by "\* or link(done)" changes doesn't work.
488 >>>>> The current system works because even though you usually want dependencies of the second type, the set of pages
489 >>>>> referred to by a pagespec can only change if one of those pages itself changes.  i.e. A dependency check of the
490 >>>>> first type will catch a dependency change of the second type with current pagespecs.
491 >>>>> This doesn't work with backlinks, and it doesn't work with existential matching.  Backlinks are currently special-cased.  I don't know
492 >>>>> how to special-case existential matching - I suspect you're better off just getting the dependency tracking right.
494 >>>>> I also tried to come up with other possible solutions: e.g. can we find the dependencies for a pagespec?  That
495 >>>>> 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.
496 >>>>> For old-style pagespecs without backlinks, the dependency set for a pagespec is the same as the set of pages the pagespec matches.
497 >>>>> Unfortunately, with existential matching, the set of pages that each
498 >>>>> pagespec depends upon can quickly become "*", which is not very useful.  -- [[Will]]
500 Patch updated to use closures rather than inline generated code for named pagespecs.  Also includes some new use of ErrorReason where appropriate. -- [[Will]]
502 > * Perl really doesn't need forward declarations, honest!
504 >> It complained (warning, not error) when I didn't use the forward declaration. :(
506 > * I have doubts about memoizing the anonymous sub created by
507 >   `pagespec_translate`.
509 >> This is there explicitly to make sure that runtime is polynomial and not exponential.
511 > * Think where you wrote `+{}` you can just write `{}`
513 >> Possibly :) -- [[Will]]
515 ----
517     diff --git a/IkiWiki.pm b/IkiWiki.pm
518     index 061a1c6..1e78a63 100644
519     --- a/IkiWiki.pm
520     +++ b/IkiWiki.pm
521     @@ -1774,8 +1774,12 @@ sub pagespec_merge ($$) {
522         return "($a) or ($b)";
523      }
524      
525     -sub pagespec_translate ($) {
526     +# is perl really so dumb it requires a forward declaration for recursive calls?
527     +sub pagespec_translate ($$);
528     +
529     +sub pagespec_translate ($$) {
530         my $spec=shift;
531     +   my $specFuncsRef=shift;
532      
533         # Convert spec to perl code.
534         my $code="";
535     @@ -1789,7 +1793,9 @@ sub pagespec_translate ($) {
536                 |
537                         \)              # )
538                 |
539     -                   \w+\([^\)]*\)   # command(params)
540     +                   define\(\s*~\w+\s*,((\([^()]*\)) | ([^()]+))+\) # define(~specName, spec) - spec can contain parens 1 deep
541     +           |
542     +                   \w+\([^()]*\)   # command(params) - params cannot contain parens
543                 |
544                         [^\s()]+        # any other text
545                 )
546     @@ -1805,10 +1811,19 @@ sub pagespec_translate ($) {
547                 elsif ($word eq "(" || $word eq ")" || $word eq "!") {
548                         $code.=' '.$word;
549                 }
550     -           elsif ($word =~ /^(\w+)\((.*)\)$/) {
551     +           elsif ($word =~ /^define\(\s*(~\w+)\s*,(.*)\)$/s) {
552     +                   my $name = $1;
553     +                   my $subSpec = $2;
554     +                   my $newSpecFunc = pagespec_translate($subSpec, $specFuncsRef);
555     +                   return if $@ || ! defined $newSpecFunc;
556     +                   $specFuncsRef->{$name} = $newSpecFunc;
557     +                   push @data, qq{Created named pagespec "$name"};
558     +                   $code.="IkiWiki::SuccessReason->new(\$data[$#data])";
559     +           }
560     +           elsif ($word =~ /^(\w+)\((.*)\)$/s) {
561                         if (exists $IkiWiki::PageSpec::{"match_$1"}) {
562                                 push @data, $2;
563     -                           $code.="IkiWiki::PageSpec::match_$1(\$page, \$data[$#data], \@_)";
564     +                           $code.="IkiWiki::PageSpec::match_$1(\$page, \$data[$#data], \@_, specFuncs => \$specFuncsRef)";
565                         }
566                         else {
567                                 push @data, qq{unknown function in pagespec "$word"};
568     @@ -1817,7 +1832,7 @@ sub pagespec_translate ($) {
569                 }
570                 else {
571                         push @data, $word;
572     -                   $code.=" IkiWiki::PageSpec::match_glob(\$page, \$data[$#data], \@_)";
573     +                   $code.=" IkiWiki::PageSpec::match_glob(\$page, \$data[$#data], \@_, specFuncs => \$specFuncsRef)";
574                 }
575         }
576      
577     @@ -1826,7 +1841,7 @@ sub pagespec_translate ($) {
578         }
579      
580         no warnings;
581     -   return eval 'sub { my $page=shift; '.$code.' }';
582     +   return eval 'memoize (sub { my $page=shift; '.$code.' })';
583      }
584      
585      sub pagespec_match ($$;@) {
586     @@ -1839,7 +1854,7 @@ sub pagespec_match ($$;@) {
587                 unshift @params, 'location';
588         }
589      
590     -   my $sub=pagespec_translate($spec);
591     +   my $sub=pagespec_translate($spec, +{});
592         return IkiWiki::ErrorReason->new("syntax error in pagespec \"$spec\"")
593                 if $@ || ! defined $sub;
594         return $sub->($page, @params);
595     @@ -1850,7 +1865,7 @@ sub pagespec_match_list ($$;@) {
596         my $spec=shift;
597         my @params=@_;
598      
599     -   my $sub=pagespec_translate($spec);
600     +   my $sub=pagespec_translate($spec, +{});
601         error "syntax error in pagespec \"$spec\""
602                 if $@ || ! defined $sub;
603         
604     @@ -1872,7 +1887,7 @@ sub pagespec_match_list ($$;@) {
605      sub pagespec_valid ($) {
606         my $spec=shift;
607      
608     -   my $sub=pagespec_translate($spec);
609     +   my $sub=pagespec_translate($spec, +{});
610         return ! $@;
611      }
612      
613     @@ -1919,6 +1934,68 @@ sub new {
614      
615      package IkiWiki::PageSpec;
616      
617     +sub check_named_spec($$;@) {
618     +   my $page=shift;
619     +   my $specName=shift;
620     +   my %params=@_;
621     +
622     +   return IkiWiki::ErrorReason->new("Unable to find specFuncs in params to check_named_spec()!")
623     +           unless exists $params{specFuncs};
624     +
625     +   my $specFuncsRef=$params{specFuncs};
626     +
627     +   return IkiWiki::ErrorReason->new("Named page spec '$specName' is not valid")
628     +           unless (substr($specName, 0, 1) eq '~');
629     +
630     +   if (exists $specFuncsRef->{$specName}) {
631     +           # remove the named spec from the spec refs
632     +           # when we recurse to avoid infinite recursion
633     +           my $sub = $specFuncsRef->{$specName};
634     +           delete $specFuncsRef->{$specName};
635     +           my $result = $sub->($page, %params);
636     +           $specFuncsRef->{$specName} = $sub;
637     +           return $result;
638     +   } else {
639     +           return IkiWiki::ErrorReason->new("Page spec '$specName' does not exist");
640     +   }
641     +}
642     +
643     +sub check_named_spec_existential($$$;@) {
644     +   my $page=shift;
645     +   my $specName=shift;
646     +   my $funcref=shift;
647     +   my %params=@_;
648     +
649     +   return IkiWiki::ErrorReason->new("Unable to find specFuncs in params to check_named_spec_existential()!")
650     +                   unless exists $params{specFuncs};
651     +   my $specFuncsRef=$params{specFuncs};
652     +   
653     +   return IkiWiki::ErrorReason->new("Named page spec '$specName' is not valid")
654     +           unless (substr($specName, 0, 1) eq '~');
655     +
656     +   if (exists $specFuncsRef->{$specName}) {
657     +           # remove the named spec from the spec refs
658     +           # when we recurse to avoid infinite recursion
659     +           my $sub = $specFuncsRef->{$specName};
660     +           delete $specFuncsRef->{$specName};
661     +           
662     +           foreach my $nextpage (keys %IkiWiki::pagesources) {
663     +                   if ($sub->($nextpage, %params)) {
664     +                           my $tempResult = $funcref->($page, $nextpage, %params);
665     +                           if ($tempResult) {
666     +                                   $specFuncsRef->{$specName} = $sub;
667     +                                   return IkiWiki::SuccessReason->new("Existential check of '$specName' matches because $tempResult");
668     +                           }
669     +                   }
670     +           }
671     +           
672     +           $specFuncsRef->{$specName} = $sub;
673     +           return IkiWiki::FailReason->new("No page in spec '$specName' was successfully matched");
674     +   } else {
675     +           return IkiWiki::ErrorReason->new("Named page spec '$specName' does not exist");
676     +   }
677     +}
678     +
679      sub derel ($$) {
680         my $path=shift;
681         my $from=shift;
682     @@ -1937,6 +2014,10 @@ sub match_glob ($$;@) {
683         my $glob=shift;
684         my %params=@_;
685         
686     +   if (substr($glob, 0, 1) eq '~') {
687     +           return check_named_spec($page, $glob, %params);
688     +   }
689     +
690         $glob=derel($glob, $params{location});
691      
692         my $regexp=IkiWiki::glob2re($glob);
693     @@ -1959,8 +2040,9 @@ sub match_internal ($$;@) {
694      
695      sub match_link ($$;@) {
696         my $page=shift;
697     -   my $link=lc(shift);
698     +   my $fullLink=shift;
699         my %params=@_;
700     +   my $link=lc($fullLink);
701      
702         $link=derel($link, $params{location});
703         my $from=exists $params{location} ? $params{location} : '';
704     @@ -1975,25 +2057,37 @@ sub match_link ($$;@) {
705                 }
706                 else {
707                         return IkiWiki::SuccessReason->new("$page links to page $p matching $link")
708     -                           if match_glob($p, $link, %params);
709     +                           if match_glob($p, $fullLink, %params);
710                         $p=~s/^\///;
711                         $link=~s/^\///;
712                         return IkiWiki::SuccessReason->new("$page links to page $p matching $link")
713     -                           if match_glob($p, $link, %params);
714     +                           if match_glob($p, $fullLink, %params);
715                 }
716         }
717         return IkiWiki::FailReason->new("$page does not link to $link");
718      }
719      
720      sub match_backlink ($$;@) {
721     -   return match_link($_[1], $_[0], @_);
722     +   my $page=shift;
723     +   my $backlink=shift;
724     +   my @params=@_;
725     +
726     +   if (substr($backlink, 0, 1) eq '~') {
727     +           return check_named_spec_existential($page, $backlink, \&match_backlink, @params);
728     +   }
729     +
730     +   return match_link($backlink, $page, @params);
731      }
732      
733      sub match_created_before ($$;@) {
734         my $page=shift;
735         my $testpage=shift;
736         my %params=@_;
737     -   
738     +
739     +   if (substr($testpage, 0, 1) eq '~') {
740     +           return check_named_spec_existential($page, $testpage, \&match_created_before, %params);
741     +   }
742     +
743         $testpage=derel($testpage, $params{location});
744      
745         if (exists $IkiWiki::pagectime{$testpage}) {
746     @@ -2014,6 +2108,10 @@ sub match_created_after ($$;@) {
747         my $testpage=shift;
748         my %params=@_;
749         
750     +   if (substr($testpage, 0, 1) eq '~') {
751     +           return check_named_spec_existential($page, $testpage, \&match_created_after, %params);
752     +   }
753     +
754         $testpage=derel($testpage, $params{location});
755      
756         if (exists $IkiWiki::pagectime{$testpage}) {