optimise brokenlinks by gathering the data when calculating backlinks

During backlink calulation, all links are examined and broken links can
be detected for free, so store a list of broken links and have brokenlinks
use it.

Exposing the %brokenlinks structure is a bit ugly, but the speedup seems
worth it: Around 1 second for wikis the size of the doc wiki that use
brokenlinks.

3 files changed, 29 insertions, 27 deletions

diff --git a/IkiWiki/Plugin/brokenlinks.pm b/IkiWiki/Plugin/brokenlinks.pm
index 5ad4c917c..eb698b0be 100644
--- a/IkiWiki/Plugin/brokenlinks.pm
+++ b/IkiWiki/Plugin/brokenlinks.pm
@@ -27,31 +27,27 @@ sub preprocess (@) {
 	# register a dependency.
 	add_depends($params{page}, $params{pages});
 	
-	my %broken;
-	foreach my $page (pagespec_match_list([keys %links],
-			$params{pages}, location => $params{page})) {
-		my %seen;
-		foreach my $link (@{$links{$page}}) {
-			next if $seen{$link};
-			$seen{$link}=1;
-			next if $link =~ /.*\/\Q$config{discussionpage}\E/i && $config{discussion};
-			my $bestlink=bestlink($page, $link);
-			next if length $bestlink;
-			push @{$broken{$link}}, $page;
+	my @broken;
+	foreach my $link (keys %IkiWiki::brokenlinks) {
+		next if $link =~ /.*\/\Q$config{discussionpage}\E/i && $config{discussion};
+
+		my @pages;
+		foreach my $page (@{$IkiWiki::brokenlinks{$link}}) {
+			push @pages, $page
+				if pagespec_match($page, $params{pages}, location => $params{page});
 		}
-	}
+		next unless @pages;
 
-	my @broken;
-	foreach my $link (keys %broken) {
-		my $page=$broken{$link}->[0];
+		my $page=$IkiWiki::brokenlinks{$link}->[0];
 		push @broken, sprintf(gettext("%s from %s"),
 			htmllink($page, $params{destpage}, $link, noimageinline => 1),
 			join(", ", map {
 				htmllink($params{page}, $params{destpage}, $_, 	noimageinline => 1)
-			} @{$broken{$link}}));
+			} @pages)
+		);
 	}
 	
-	return gettext("There are no broken links!") unless %broken;
+	return gettext("There are no broken links!") unless @broken;
 	return "<ul>\n"
 		.join("\n",
 			map {
diff --git a/IkiWiki/Render.pm b/IkiWiki/Render.pm
index d5e81f1b9..578142d2e 100644
--- a/IkiWiki/Render.pm
+++ b/IkiWiki/Render.pm
@@ -8,26 +8,31 @@ use IkiWiki;
 use Encode;
 
 my %backlinks;
-my $backlinks_calculated=0;
+our %brokenlinks;
+my $links_calculated=0;
 
-sub calculate_backlinks () {
-	return if $backlinks_calculated;
-	%backlinks=();
+sub calculate_links () {
+	return if $links_calculated;
+	%backlinks=%brokenlinks=();
 	foreach my $page (keys %links) {
 		foreach my $link (@{$links{$page}}) {
 			my $bestlink=bestlink($page, $link);
-			if (length $bestlink && $bestlink ne $page) {
-				$backlinks{$bestlink}{$page}=1;
+			if (length $bestlink) {
+				$backlinks{$bestlink}{$page}=1
+					if $bestlink ne $page;
+			}
+			else {
+				push @{$brokenlinks{$link}}, $page;
 			}
 		}
 	}
-	$backlinks_calculated=1;
+	$links_calculated=1;
 }
 
 sub backlink_pages ($) {
 	my $page=shift;
 
-	calculate_backlinks();
+	calculate_links();
 
 	return keys %{$backlinks{$page}};
 }
@@ -416,7 +421,7 @@ sub refresh () {
 		debug(sprintf(gettext("scanning %s"), $file));
 		scan($file);
 	}
-	calculate_backlinks();
+	calculate_links();
 	foreach my $file (@needsbuild) {
 		debug(sprintf(gettext("building %s"), $file));
 		render($file);
diff --git a/debian/changelog b/debian/changelog
index 5e5149927..147d279bb 100644
--- a/debian/changelog
+++ b/debian/changelog
@@ -5,7 +5,8 @@ ikiwiki (3.141593) UNRELEASED; urgency=low
   * inline: Avoid use of my $_ as it fails with older perls.
     Closes: #541215
   * Add discussionpage configuration setting.
-  * Small optimisations.
+  * Several optimisations, including speedups to orphans and brokenlinks
+    calculation.
 
  -- Joey Hess <joeyh@debian.org>  Wed, 12 Aug 2009 12:25:30 -0400