summaryrefslogtreecommitdiff
path: root/doc/todo/tracking_bugs_with_dependencies.mdwn
blob: 7186166ce5396779388e5791e1518170cd42cc3f (plain)

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.

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?

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


diff --git a/IkiWiki.pm b/IkiWiki.pm index e476521..07b71d7 100644 --- a/IkiWiki.pm +++ b/IkiWiki.pm @@ -1524,7 +1524,7 @@ sub globlist_to_pagespec ($) { #{{{

sub is_globlist ($) { #{{{ my $s=shift;

  • return ( $s =~ /[^\s]+\s+([^\s]+)/ && $1 ne "and" && $1 ne "or" );
  • return 0; #( $s =~ /[^\s]+\s+([^\s]+)/ && $1 ne "and" && $1 ne "or" ); } #}}}

sub safequote ($) { #{{{ @@ -1605,7 +1605,7 @@ sub pagespec_merge ($$) { #{{{ return "($a) or ($b)"; } #}}}

-sub pagespec_translate ($) { #{{{ +sub pagespec_makeperl ($) { #{{{ my $spec=shift;

# Support for old-style GlobLists.

@@ -1624,9 +1624,11 @@ 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\(\)]+	# any other text
      )
      \s*		# ignore whitespace
    
    }igx) { @@ -1640,16 +1642,23 @@ sub pagespec_translate ($) { #{{{ elsif ($word eq "(" || $word eq ")" || $word eq "!") { $code.=' '.$word; }
  •   elsif ($word =~ /^define\(\s*~(\w+)\s*,(.*)\)$/) {
    
  •   	$code .= " (\$specFuncsRef->{$1}=";
    
  •   	#$code .= "memoize(";
    
  •   	$code .= pagespec_makeperl($2);
    
  •   	#$code .= ")";
    
  •   	$code .= ") ";
    
  •   }
      elsif ($word =~ /^(\w+)\((.*)\)$/) {
      	if (exists $IkiWiki::PageSpec::{"match_$1"}) {
    
  •   		$code.="IkiWiki::PageSpec::match_$1(\$page, ".safequote($2).", \@_)";
    
  •   		$code.="IkiWiki::PageSpec::match_$1(\$page, \$specFuncsRef, ".safequote($2).", \@_)";
      	}
      	else {
      		$code.=' 0';
      	}
      }
      else {
    
  •   	$code.=" IkiWiki::PageSpec::match_glob(\$page, ".safequote($word).", \@_)";
    
  •   	$code.=" IkiWiki::PageSpec::match_glob(\$page, \$specFuncsRef, ".safequote($word).", \@_)";
      }
    
    }

@@ -1657,8 +1666,18 @@ sub pagespec_translate ($) { #{{{ $code=0; }

  • return 'sub { my $page=shift; my $specFuncsRef=shift; '.$code.' }'; +} #}}}

+sub pagespec_translate ($) { #{{{

  • my $spec=shift;
  • my $code = pagespec_makeperl($spec);
  • print "Spec '$spec' led to perl '$code'\n";
  • no warnings;
  • return eval 'sub { my $page=shift; '.$code.' }';
  • return eval $code; } #}}}

sub pagespec_match ($$;@) { #{{{ @@ -1673,7 +1692,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); } #}}}

sub pagespec_valid ($) { #{{{ @@ -1722,13 +1741,77 @@ sub new { #{{{

package IkiWiki::PageSpec;

-sub match_glob ($$;@) { #{{{ +sub check_named_spec($$$;@) {

  • my $page=shift;
  • my $specFuncsRef=shift;
  • my $specName=shift;
  • my %params=@_;
  • return IkiWiki::FailReason->new("Named page spec '$specName' is not valid")
  •   unless (substr($specName, 0, 1) eq '~');
    
  • $specName = substr($specName, 1);
  • print "Checking pagespec named $specName against page $page\n";
  • if (exists $specFuncsRef->{$specName}) {
  •   # remove the named spec from the spec refs
    
  •   # when we recurse to avoid infinite recursion
    
  •   my $sub = $specFuncsRef->{$specName};
    
  •   $specFuncsRef->{$specName} = undef;
    
  •   my $result = $sub->($page, $specFuncsRef, %params);
    
  •   $specFuncsRef->{$specName} = $sub;
    
  •   return $result;
    
  • } else {
  •   print "Couldn't find pagespec\n";
    
  •   return IkiWiki::FailReason->new("Page spec $specName does not exist");
    
  • } +}

+sub check_named_spec_existential($$$$;@) {

  • my $page=shift;
  • my $specFuncsRef=shift;
  • my $specName=shift;
  • my $funcref=shift;
  • my %params=@_;
  • return IkiWiki::FailReason->new("Named page spec '$specName' is not valid")
  •   unless (substr($specName, 0, 1) eq '~');
    
  • $specName = substr($specName, 1);
  • print "Checking (existential) pagespec named $specName against page $page\n";
  • if (exists $specFuncsRef->{$specName}) {
  •   # remove the named spec from the spec refs
    
  •   # when we recurse to avoid infinite recursion
    
  •   my $sub = $specFuncsRef->{$specName};
    
  •   $specFuncsRef->{$specName} = undef;
    
  •   foreach my $nextpage (keys %IkiWiki::pagesources) {
    
  •   	print "Checking $nextpage against $specName\n";
    
  •   	if ($sub->($nextpage, $specFuncsRef, %params)) {
    
  •   		print "Match!  Checking spec $nextpage against function from original page $page\n";
    
  •   		my $tempResult = $funcref->($page, $specFuncsRef, $nextpage, %params);
    
  •   		return $tempResult if ($tempResult);
    
  •   	}
    
  •   }
    
  •   $specFuncsRef->{$specName} = $sub;
    
  •   return IkiWiki::FailReason->new("No page in spec $specName was successfully matched");
    
  • } else {
  •   print "Couldn't find pagespec\n";
    
  •   return IkiWiki::FailReason->new("Page spec $specName does not exist");
    
  • } +}

+sub match_glob ($$$;@) { #{{{ my $page=shift;

  • my $specFuncsRef=shift; my $glob=shift; my %params=@_;

    my $from=exists $params{location} ? $params{location} : '';

  • print "Matching glob $glob \n";

  • relative matching

    if ($glob =~ m!^./!) { $from=~s#/?[^/]+$##; @@ -1736,6 +1819,10 @@ sub match_glob ($$;@) { #{{{ $glob="$from/$glob" if length $from; }

  • if (substr($glob, 0, 1) eq '~') {

  •   return check_named_spec($page, $specFuncsRef, $glob);
    
  • }

  • my $regexp=IkiWiki::glob2re($glob); if ($page=~/^$regexp$/i) { if (! IkiWiki::isinternal($page) || $params{internal}) { @@ -1750,17 +1837,29 @@ sub match_glob ($$;@) { #{{{ } } #}}}

-sub match_internal ($$;@) { #{{{

  • return match_glob($[0], $[1], @_, internal => 1) +sub match_internal ($$$;@) { #{{{
  • my $page=shift;
  • my $specFuncsRef=shift;
  • my $glob=shift;
  • return match_glob($page, $specFuncsRef, $glob, @_, internal => 1) } #}}}

-sub match_link ($$;@) { #{{{ +sub match_link ($$$;@) { #{{{ my $page=shift;

  • my $link=lc(shift);
  • my $specFuncsRef=shift;

  • my $fulllink=shift;

  • my $link=lc($fulllink); my %params=@_;

  • print "Matching link $fulllink \n";

  • my $from=exists $params{location} ? $params{location} : '';

  • if (substr($fulllink, 0, 1) eq '~') {

  •   return check_named_spec_existential($page, $specFuncsRef, $fulllink, \&match_link);
    
  • }

  • relative matching

    if ($link =~ m!^.! && defined $from) { $from=~s#/?[^/]+$##; @@ -1784,12 +1883,16 @@ sub match_link ($$;@) { #{{{ return IkiWiki::FailReason->new("$page does not link to $link"); } #}}}

-sub match_backlink ($$;@) { #{{{

  • return match_link($[1], $[0], @_); +sub match_backlink ($$$;@) { #{{{
  • my $page=shift;
  • my $specFuncsRef=shift;
  • my $backlink=shift;
  • return match_link($backlink, $specFuncsRef, $page, @_); } #}}}

-sub match_created_before ($$;@) { #{{{ +sub match_created_before ($$$;@) { #{{{ my $page=shift;

  • my $specFuncsRef=shift; my $testpage=shift;

    if (exists $IkiWiki::pagectime{$testpage}) { @@ -1805,8 +1908,9 @@ sub match_created_before ($$;@) { #{{{ } } #}}}

-sub match_created_after ($$;@) { #{{{ +sub match_created_after ($$$;@) { #{{{ my $page=shift;

  • my $specFuncsRef=shift; my $testpage=shift;

    if (exists $IkiWiki::pagectime{$testpage}) { @@ -1822,8 +1926,12 @@ sub match_created_after ($$;@) { #{{{ } } #}}}

-sub match_creation_day ($$;@) { #{{{

  • if ((gmtime($IkiWiki::pagectime{shift()}))[3] == shift) { +sub match_creation_day ($$$;@) { #{{{
  • my $page=shift;
  • shift;
  • my $time=shift;
  • if ((gmtime($IkiWiki::pagectime{$page}))[3] == $time) { return IkiWiki::SuccessReason->new('creation_day matched'); } else { @@ -1831,8 +1939,12 @@ sub match_creation_day ($$;@) { #{{{ } } #}}}

-sub match_creation_month ($$;@) { #{{{

  • if ((gmtime($IkiWiki::pagectime{shift()}))[4] + 1 == shift) { +sub match_creation_month ($$$;@) { #{{{
  • my $page=shift;
  • shift;
  • my $time=shift;
  • if ((gmtime($IkiWiki::pagectime{$page}))[4] + 1 == $time) { return IkiWiki::SuccessReason->new('creation_month matched'); } else { @@ -1840,8 +1952,12 @@ sub match_creation_month ($$;@) { #{{{ } } #}}}

-sub match_creation_year ($$;@) { #{{{

  • if ((gmtime($IkiWiki::pagectime{shift()}))[5] + 1900 == shift) { +sub match_creation_year ($$$;@) { #{{{
  • my $page=shift;
  • shift;
  • my $time=shift;
  • if ((gmtime($IkiWiki::pagectime{$page}))[5] + 1900 == $time) { return IkiWiki::SuccessReason->new('creation_year matched'); } else { diff --git a/IkiWiki/Plugin/attachment.pm b/IkiWiki/Plugin/attachment.pm index f1f792a..a410e48 100644 --- a/IkiWiki/Plugin/attachment.pm +++ b/IkiWiki/Plugin/attachment.pm @@ -291,7 +291,8 @@ sub attachment_list ($) { #{{{

package IkiWiki::PageSpec;

-sub match_user ($$;@) { #{{{ +sub match_user ($$$;@) { #{{{

  • shift; shift; my $user=shift; my %params=@_; @@ -311,7 +312,8 @@ sub match_user ($$;@) { #{{{ } } #}}}

-sub match_ip ($$;@) { #{{{ +sub match_ip ($$$;@) { #{{{

  • shift; shift; my $ip=shift; my %params=@_; diff --git a/IkiWiki/Plugin/conditional.pm b/IkiWiki/Plugin/conditional.pm index 7716fce..2110ca0 100644 --- a/IkiWiki/Plugin/conditional.pm +++ b/IkiWiki/Plugin/conditional.pm @@ -70,7 +70,8 @@ sub preprocess_if (@) { #{{{

package IkiWiki::PageSpec;

-sub match_enabled ($$;@) { #{{{ +sub match_enabled ($$$;@) { #{{{

  • shift; shift; my $plugin=shift;

@@ -83,13 +84,14 @@ sub match_enabled ($$;@) { #{{{ } } #}}}

-sub match_sourcepage ($$;@) { #{{{ +sub match_sourcepage ($$$;@) { #{{{ shift;

  • my $specFuncsRef=shift; my $glob=shift; my %params=@_;

    return IkiWiki::FailReason->new("cannot match sourcepage") unless exists $params{sourcepage};

  • if (match_glob($params{sourcepage}, $glob, @_)) {
  • if (match_glob($params{sourcepage}, $specFuncsRef, $glob, @_)) { return IkiWiki::SuccessReason->new("sourcepage matches $glob"); } else { @@ -97,13 +99,14 @@ sub match_sourcepage ($$;@) { #{{{ } } #}}}

-sub match_destpage ($$;@) { #{{{ +sub match_destpage ($$$;@) { #{{{ shift;

  • my $specFuncsRef=shift; my $glob=shift; my %params=@_;

    return IkiWiki::FailReason->new("cannot match destpage") unless exists $params{destpage};

  • if (match_glob($params{destpage}, $glob, @_)) {
  • if (match_glob($params{destpage}, $specFuncsRef, $glob, @_)) { return IkiWiki::SuccessReason->new("destpage matches $glob"); } else { @@ -111,7 +114,8 @@ sub match_destpage ($$;@) { #{{{ } } #}}}

-sub match_included ($$;@) { #{{{ +sub match_included ($$$;@) { #{{{

  • shift; shift; shift; my %params=@_; diff --git a/IkiWiki/Plugin/filecheck.pm b/IkiWiki/Plugin/filecheck.pm index 6f71be3..bf472c5 100644 --- a/IkiWiki/Plugin/filecheck.pm +++ b/IkiWiki/Plugin/filecheck.pm @@ -66,8 +66,9 @@ sub humansize ($) { #{{{

package IkiWiki::PageSpec;

-sub match_maxsize ($$;@) { #{{{ +sub match_maxsize ($$$;@) { #{{{ my $page=shift;

  • shift; my $maxsize=eval{IkiWiki::Plugin::attachment::parsesize(shift)}; if ($@) { return IkiWiki::FailReason->new("unable to parse maxsize (or number too large)"); @@ -87,8 +88,9 @@ sub match_maxsize ($$;@) { #{{{ } } #}}}

-sub match_minsize ($$;@) { #{{{ +sub match_minsize ($$$;@) { #{{{ my $page=shift;

  • shift; my $minsize=eval{IkiWiki::Plugin::attachment::parsesize(shift)}; if ($@) { return IkiWiki::FailReason->new("unable to parse minsize (or number too large)"); @@ -108,8 +110,9 @@ sub match_minsize ($$;@) { #{{{ } } #}}}

-sub match_mimetype ($$;@) { #{{{ +sub match_mimetype ($$$;@) { #{{{ my $page=shift;

  • shift; my $wanted=shift;

    my %params=@_; @@ -138,8 +141,9 @@ sub match_mimetype ($$;@) { #{{{ } } #}}}

-sub match_virusfree ($$;@) { #{{{ +sub match_virusfree ($$$;@) { #{{{ my $page=shift;

  • shift; my $wanted=shift;

    my %params=@_; @@ -180,7 +184,7 @@ sub match_virusfree ($$;@) { #{{{ } } #}}}

-sub match_ispage ($$;@) { #{{{ +sub match_ispage ($$$;@) { #{{{ my $filename=shift;

if (defined IkiWiki::pagetype($filename)) {

diff --git a/IkiWiki/Plugin/meta.pm b/IkiWiki/Plugin/meta.pm index b2c85c8..1ee6a69 100644 --- a/IkiWiki/Plugin/meta.pm +++ b/IkiWiki/Plugin/meta.pm @@ -264,6 +264,7 @@ sub pagetemplate (@) { #{{{ sub match { #{{{ my $field=shift; my $page=shift;

  • shift;

    turn glob into a safe regexp

    my $re=IkiWiki::glob2re(shift); @@ -291,23 +292,23 @@ sub match { #{{{

package IkiWiki::PageSpec;

-sub match_title ($$;@) { #{{{ +sub match_title ($$$;@) { #{{{ IkiWiki::Plugin::meta::match("title", @_); } #}}}

-sub match_author ($$;@) { #{{{ +sub match_author ($$$;@) { #{{{ IkiWiki::Plugin::meta::match("author", @_); } #}}}

-sub match_authorurl ($$;@) { #{{{ +sub match_authorurl ($$$;@) { #{{{ IkiWiki::Plugin::meta::match("authorurl", @_); } #}}}

-sub match_license ($$;@) { #{{{ +sub match_license ($$$;@) { #{{{ IkiWiki::Plugin::meta::match("license", @_); } #}}}

-sub match_copyright ($$;@) { #{{{ +sub match_copyright ($$$;@) { #{{{ IkiWiki::Plugin::meta::match("copyright", @_); } #}}}