aboutsummaryrefslogtreecommitdiff
path: root/doc/todo/tracking_bugs_with_dependencies.mdwn
blob: 2832e37aad36c85e0c696bce62cb124791ad8aab (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
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]]

> I started having a think about this.  I'm going to start with the idea that expanding
> the pagespec syntax is the way to attack this.  It seems that any pagespec that is going
> to represent "all bugs with no dependencies on bugs not marked as done" is going to
> need some way to represent "bugs not marked as done" as a collection of pages, and
> then represent "bugs which do not link to pages in the previous collection".
>
> One way to do this would be to introduce variables into the pagespec, along with
> universal and/or existential [[!wikipedia Quantification]].  That looks quite complex.
>
>> I thought about this briefly, and got about that far.. glad you got
>> further. :-) --[[Joey]]
> 
> Another option would be go with a more functional syntax.  The concept here would
> be to allow a pagespec to appear in a 'pagespec function' anywhere a page can.  e.g.
> I could pass a pagespec to `link()` and that would return true if there is a link to any
> page matching the pagespec.  This makes the variables and existential quantification
> implicit.  It would allow the example requested above:
>
>> `bugs/* and !*/Discussion and !link(bugs/* and !*/Discussion and !link(done))`
>
> Unfortunately, this is also going to make the pagespec parsing more complex because
> we now need to parse nested sets of parentheses to know when the nested pagespec
> ends, and that isn't a regular language (we can't use regular expression matching for
> easy parsing).
>
>> Also, it may cause ambiguities with page names that contain parens
>> (though some such ambigutities already exist with the pagespec syntax).
>
> One simplification of that would be to introduce some pagespec [[shortcuts]].  We could
> then allow pagespec functions to take either pages, or named pagespec shortcuts.  The
> pagespec shortcuts would just be listed on a special page, like current [[shortcuts]].
> (It would probably be a good idea to require that shortcuts on that page can only refer
> to named pagespecs higher up that page than themselves.  That would stop some
> looping issues...)  These shortcuts would be used as follows: when trying to match
> a page (without globs) you look to see if the page exists.  If it does then you have a
> match.  If it doesn't, then you look to see if a similarly named pagespec shortcut
> exists.  If it does, then you check that pagespec recursively to see if you have a match.
> The ordering requirement on named pagespecs stops infinite recursion.
>
> Does that seem like a reasonable first approach?
>
> -- [[Will]]

>> Having a separate page for the shortcuts feels unwieldly.. perhaps
>> instead the shortcut could be defined earlier in the scope of the same
>> pagespec that uses it?
>> 
>> Example: `define(~bugs, bugs/* and !*/Discussion) and define(~openbugs, ~bugs and !link(done)) and ~openbugs and !link(~openbugs)`

>>> That could work.  parens are only ever nested 1 deep in that grammar so it is regular and the current parsing would be ok.

>> Note that I made the "~" explicit, not implicit, so it could be left out. In the case of ambiguity between
>> a definition and a page name, the definition would win.

>>> 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.

>> So, equivilant example: `define(bugs, bugs/* and !*/Discussion) and define(openbugs, bugs and !link(done)) and openbugs and !link(openbugs)`
>> 
>> Re recursion, it is avoided.. but building a pagespec that is O(N^X) where N is the
>> number of pages in the wiki is not avoided. Probably need to add DOS prevention.
>>  --[[Joey]]

>>> If you memoize the outcomes of the named pagespecs you can make in O(N.X), no?
>>> -- [[Will]]

>>>> Yeah, guess that'd work. :-)

> One quick further thought.  All the above discussion assumes that 'dependency' is the
> same as 'links to', which is not really true.  For example, you'd like to be able to say
> "This bug does not depend upon [ [ link to other bug ] ]" and not have a dependency.
> Without having different types of links, I don't see how this would be possible.
>
> -- [[Will]]

Okie - I've had a quick attempt at this.  Initial patch attached.  This one doesn't quite work.
And there is still a lot of debugging stuff in there.

At the moment I've added a new preprocessor plugin, `definepagespec`, which is like
shortcut for pagespecs.  To reference a named pagespec, use `~` like this:

    [ [!definepagespec name="bugs" spec="bugs/* and !*/Discussion"]]
    [ [!definepagespec name="openbugs" spec="~bugs and !link(done)"]]
    [ [!definepagespec name="readybugs" spec="~openbugs and !link(~openbugs)"]]

At the moment the problem is in `match_link()` when we're trying to find a sub-page that
matches the appropriate page spec.  There is no good list of pages available to iterate over.

    foreach my $nextpage (keys %IkiWiki::pagesources)

does not give me a good list of pages.  I found the same thing when I was working on
this todo [[todo/Add_a_plugin_to_list_available_pre-processor_commands]].

> I'm not sure why iterating over `%pagesources` wouldn't work here, it's the same method
> used by anything that needs to match a pagespec against all pages..? --[[Joey]]

>> My uchecked hypothesis is that %pagesources is created after the refresh hook.
>> I've also been concerned about how globally defined pagespec shortcuts would interact with
>> the page dependancy system.  Your idea of internally defined shortcuts should fix that. -- [[Will]]

>>> You're correct, the refresh hook is run very early, before pagesources
>>> is populated. (It will be partially populated on a refresh, but will
>>> not be updated to reflect new pages.) Agree that internally defined
>>> seems the way to go. --[[Joey]]

Immediately below is a patch which seems to basically work.  Lots of debugging code is still there
and it needs a cleanup, but I thought it worth posting at this point.  (I was having problems
with old style glob lists, so i just switched them off for the moment.)

The following three inlines work for me with this patch:

    Bugs:
    
    [ [!inline pages="define(~bugs, bugs/* and ! */Discussion) and ~bugs" archive="yes"]]
    
    OpenBugs:
    
    [ [!inline pages="define(~bugs, bugs/* and ! */Discussion) and define(~openbugs,~bugs and !link(done)) and ~openbugs" archive="yes"]]
    
    ReadyBugs:
    
    [ [!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"]]

> Nice! Could the specfuncsref be passed in %params? I'd like to avoid
> needing to change the prototype of every pagespec function, since several
> plugins define them too. --[[Joey]]

>> Maybe - it needs more thought.  I also considered it when I was going though changing all those plugins :).
>> My concern was that `%params` can contain other user-defined parameters,
>> e.g. `link(target, otherparameter)`, and that means that the specFuncs could be clobbered by a user (or other
>> weird security hole).  I thought it better to separate it, but I didn't think about it too hard.  I might move it to
>> the first parameter rather than the second.  Ikiwiki is my first real perl hacking and I'm still discovering
>> good ways to write things in perl.
>>
>>>> `%params` contains the parameters passed to `pagespec_match`, not
>>>> user-supplied parameters. The user-supplied parameter to a function
>>>> like `match_glob()` or `match_link()` is passed in the second positional parameter. --[[Joey]]

>>>>> OK.  That seems reasonable then.  The only problem is that my PERLfu is not strong enough to make it
>>>>> work.  I really have to wonder what substance was influencing the designers of PERL...
>>>>> I can't figure out how to use the %params.  And I'm pissed off enough with PERL that I'm not going
>>>>> to try and figure it out any more.  There are two patches below now.  The first one uses an extra
>>>>> argument and works.  The second one tries to use %params and doesn't - take your pick :-). -- [[Will]]

>> What do you think is best to do about `is_globlist()`?  At the moment it requires that the 'second word', as
>> 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).
>> My thought was just to search for 'and' or 'or' as words anywhere in the pagespec.  Thoughts?

>>> Dunno, we could just finish deprecating it. Or change the regexp to
>>> skip over spaces in parens. (`/[^\s]+\s+([^)]+)/`) --[[Joey]]

>>>> I think I have a working regexp now.

>> Oh, one more thing.  In pagespec_translate (now pagespec_makeperl), there is a part of the regular expression for `# any other text`.
>> This contained `()`, which has no effect.  I replaced that with `\(\)`, but that is a change in the definition of pagespecs unrelated to the
>> rest of this patch. In a related change, commands were not able to contain `)` in their parameters.  I've extended that so the cannot
>> contain `(` or `)`.  -- [[Will]]

>>> `[^\s()]+` is a character class matching all characters not spaces or
>>> parens. Since the pervious terminals in the regexp consume most
>>> occurances of an open paren or close paren, it's unlikely for one to
>>> get through to that part of the regexp. For example, "foo()" will be
>>> matched by the command matcher; "(foo)" will be matched by the open
>>> paren literal terminal. "foo(" and "foo)" can get through to the
>>> end, and would be matched as a page name, if it didn't exclude parens.
>>>
>>> So why exclude them? Well, consider "foo and(bar and baz)". We don't
>>> want it to match "and(" as a page name!
>>> 
>>> Escaping the parens in the character class actually changes nothing; the
>>> changed character class still matches all characters not spaces or
>>> parens. (Try it!).
>>> 
>>> Re commands containing '(', I don't really see any reason not to
>>> allow that, unless it breaks something. --[[Joey]]

>>>> Oh, I didn't realise you didn't need to escape parens inside [].  All else I
>>>> I understood.  I have stopped commands from containing parens because
>>>> once you allow that then you might have a extra level of depth in the parsing
>>>> of define() statements. -- [[Will]]

>>> Updated patch.  Moved the specFuncsRef to the front of the arg list.  Still haven't thought through the security implications of
>>> having it in `%params`.  I've also removed all the debugging `print` statements.  And I've updated the `is_globlist()` function.
>>> I think this is ready for people other than me to have a play.  It is not well enough tested to commit just yet.
>>> -- [[Will]]

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
account all comments above (which doesn't mean it is above reproach :) ).  --[[Will]]

----

    diff --git a/IkiWiki.pm b/IkiWiki.pm
    index 4e4da11..8b3cdfe 100644
    --- a/IkiWiki.pm
    +++ b/IkiWiki.pm
    @@ -1550,7 +1550,16 @@ sub globlist_to_pagespec ($) {
     
     sub is_globlist ($) {
     	my $s=shift;
    -	return ( $s =~ /[^\s]+\s+([^\s]+)/ && $1 ne "and" && $1 ne "or" );
    +	return ! ($s =~ /
    +			(^\s*
    +				[^\s(]+		# single item
    +					(\(			# possibly with parens after it
    +						([^)]*	# with stuff inside those parens
    +						(\([^)]*\))*)*	# maybe even nested parens
    +					\))?\s*$
    +			) |
    +				(\s and \s) | (\s or \s)	# or we find 'and' or 'or' somewhere
    +			/xs);
     }
     
     sub safequote ($) {
    @@ -1631,7 +1640,7 @@ sub pagespec_merge ($$) {
     	return "($a) or ($b)";
     }
     
    -sub pagespec_translate ($) {
    +sub pagespec_makeperl ($) {
     	my $spec=shift;
     
     	# Support for old-style GlobLists.
    @@ -1650,12 +1659,14 @@ sub pagespec_translate ($) {
     		|
     			\)		# )
     		|
    -			\w+\([^\)]*\)	# command(params)
    +			define\(\s*~\w+\s*,((\([^()]*\)) | ([^()]+))+\)	# define(~specName, spec) - spec can contain parens 1 deep
    +		|
    +			\w+\([^()]*\)	# command(params) - params cannot contain parens
     		|
     			[^\s()]+	# any other text
     		)
     		\s*		# ignore whitespace
    -	}igx) {
    +	}igxs) {
     		my $word=$1;
     		if (lc $word eq 'and') {
     			$code.=' &&';
    @@ -1666,16 +1677,23 @@ sub pagespec_translate ($) {
     		elsif ($word eq "(" || $word eq ")" || $word eq "!") {
     			$code.=' '.$word;
     		}
    -		elsif ($word =~ /^(\w+)\((.*)\)$/) {
    +		elsif ($word =~ /^define\(\s*~(\w+)\s*,(.*)\)$/s) {
    +			$code .= " (\$params{specFuncs}->{$1}=";	# (exists \$params{specFuncs}) && 
    +			$code .= "memoize(";
    +			$code .= &pagespec_makeperl($2);
    +			$code .= ")";
    +			$code .= ") ";
    +		}
    +		elsif ($word =~ /^(\w+)\((.*)\)$/s) {
     			if (exists $IkiWiki::PageSpec::{"match_$1"}) {
    -				$code.="IkiWiki::PageSpec::match_$1(\$page, ".safequote($2).", \@_)";
    +				$code.="IkiWiki::PageSpec::match_$1(\$page, ".safequote($2).", \%params)";
     			}
     			else {
     				$code.=' 0';
     			}
     		}
     		else {
    -			$code.=" IkiWiki::PageSpec::match_glob(\$page, ".safequote($word).", \@_)";
    +			$code.=" IkiWiki::PageSpec::match_glob(\$page, ".safequote($word).", \%params)";
     		}
     	}
     
    @@ -1683,8 +1701,18 @@ sub pagespec_translate ($) {
     		$code=0;
     	}
     
    +	return 'sub { my $page=shift; my %params = @_; '.$code.' }';
    +}
    +
    +sub pagespec_translate ($) {
    +	my $spec=shift;
    +
    +	my $code = pagespec_makeperl($spec);
    +
    +	# print STDERR "Spec '$spec' generated code '$code'\n";
    +
     	no warnings;
    -	return eval 'sub { my $page=shift; '.$code.' }';
    +	return eval $code;
     }
     
     sub pagespec_match ($$;@) {
    @@ -1699,7 +1727,7 @@ sub pagespec_match ($$;@) {
     
     	my $sub=pagespec_translate($spec);
     	return IkiWiki::FailReason->new("syntax error in pagespec \"$spec\"") if $@;
    -	return $sub->($page, @params);
    +	return $sub->($page, @params, specFuncs => {});
     }
     
     sub pagespec_valid ($) {
    @@ -1748,11 +1776,78 @@ sub new {
     
     package IkiWiki::PageSpec;
     
    +sub check_named_spec($$;@) {
    +	my $page=shift;
    +	my $specName=shift;
    +	my %params=@_;
    +	
    +	error("Unable to find specFuncs in params to check_named_spec()!") unless exists $params{specFuncs};
    +
    +	my $specFuncsRef=$params{specFuncs};
    +	
    +	return IkiWiki::FailReason->new("Named page spec '$specName' is not valid")
    +		unless (substr($specName, 0, 1) eq '~');
    +	
    +	$specName = substr($specName, 1);
    +
    +	if (exists $specFuncsRef->{$specName}) {
    +		# remove the named spec from the spec refs
    +		# when we recurse to avoid infinite recursion
    +		my $sub = $specFuncsRef->{$specName};
    +		delete $specFuncsRef->{$specName};
    +		my $result = $sub->($page, %params);
    +		$specFuncsRef->{$specName} = $sub;
    +		return $result;
    +	} else {
    +		return IkiWiki::FailReason->new("Page spec '$specName' does not exist");
    +	}
    +}
    +
    +sub check_named_spec_existential($$$;@) {
    +	my $page=shift;
    +	my $specName=shift;
    +	my $funcref=shift;
    +	my %params=@_;
    +	
    +	error("Unable to find specFuncs in params to check_named_spec_existential()!") unless exists $params{specFuncs};
    +	my $specFuncsRef=$params{specFuncs};
    +	
    +	return IkiWiki::FailReason->new("Named page spec '$specName' is not valid")
    +		unless (substr($specName, 0, 1) eq '~');
    +	$specName = substr($specName, 1);
    +	
    +	if (exists $specFuncsRef->{$specName}) {
    +		# remove the named spec from the spec refs
    +		# when we recurse to avoid infinite recursion
    +		my $sub = $specFuncsRef->{$specName};
    +		delete $specFuncsRef->{$specName};
    +		
    +		foreach my $nextpage (keys %IkiWiki::pagesources) {
    +			if ($sub->($nextpage, %params)) {
    +				my $tempResult = $funcref->($page, $nextpage, %params);
    +				if ($tempResult) {
    +					$specFuncsRef->{$specName} = $sub;
    +					return $tempResult;
    +				}
    +			}
    +		}
    +		
    +		$specFuncsRef->{$specName} = $sub;
    +		return IkiWiki::FailReason->new("No page in spec '$specName' was successfully matched");
    +	} else {
    +		return IkiWiki::FailReason->new("Named page spec '$specName' does not exist");
    +	}
    +}
    +
     sub match_glob ($$;@) {
     	my $page=shift;
     	my $glob=shift;
     	my %params=@_;
     	
    +	if (substr($glob, 0, 1) eq '~') {
    +		return check_named_spec($page, $glob, %params);
    +	}
    +
     	my $from=exists $params{location} ? $params{location} : '';
     	
     	# relative matching
    @@ -1782,11 +1877,12 @@ sub match_internal ($$;@) {
     
     sub match_link ($$;@) {
     	my $page=shift;
    -	my $link=lc(shift);
    +	my $fulllink=shift;
     	my %params=@_;
    +	my $link=lc($fulllink);
     
     	my $from=exists $params{location} ? $params{location} : '';
    -
    +	
     	# relative matching
     	if ($link =~ m!^\.! && defined $from) {
     		$from=~s#/?[^/]+$##;
    @@ -1804,19 +1900,32 @@ sub match_link ($$;@) {
     		}
     		else {
     			return IkiWiki::SuccessReason->new("$page links to page $p matching $link")
    -				if match_glob($p, $link, %params);
    +				if match_glob($p, $fulllink, %params);
     		}
     	}
     	return IkiWiki::FailReason->new("$page does not link to $link");
     }
     
     sub match_backlink ($$;@) {
    -	return match_link($_[1], $_[0], @_);
    +	my $page=shift;
    +	my $backlink=shift;
    +	my @params=@_;
    +
    +	if (substr($backlink, 0, 1) eq '~') {
    +		return check_named_spec_existential($page, $backlink, \&match_backlink, @params);
    +	}
    +
    +	return match_link($backlink, $page, @params);
     }
     
     sub match_created_before ($$;@) {
     	my $page=shift;
     	my $testpage=shift;
    +	my @params=@_;
    +
    +	if (substr($testpage, 0, 1) eq '~') {
    +		return check_named_spec_existential($page, $testpage, \&match_created_before, @params);
    +	}
     
     	if (exists $IkiWiki::pagectime{$testpage}) {
     		if ($IkiWiki::pagectime{$page} < $IkiWiki::pagectime{$testpage}) {
    @@ -1834,6 +1943,11 @@ sub match_created_before ($$;@) {
     sub match_created_after ($$;@) {
     	my $page=shift;
     	my $testpage=shift;
    +	my @params=@_;
    +
    +	if (substr($testpage, 0, 1) eq '~') {
    +		return check_named_spec_existential($page, $testpage, \&match_created_after, @params);
    +	}
     
     	if (exists $IkiWiki::pagectime{$testpage}) {
     		if ($IkiWiki::pagectime{$page} > $IkiWiki::pagectime{$testpage}) {