From fd7b5767d3d377185838895d04f51288f0889a59 Mon Sep 17 00:00:00 2001 From: Joey Hess Date: Mon, 5 Oct 2009 21:24:55 -0400 Subject: [PATCH] new link change detection method and general code rework This new method for determining when links on pages have changed should be more efficient, since it avoids double calculation of the bestlinks. It also allows collecting data about the old links, before the scan pass, so the data is accurate when pages move around and bestlinks change. Also got some code back to a saner indent level. --- IkiWiki/Render.pm | 242 ++++++++++++++++++++++------------------------ 1 file changed, 116 insertions(+), 126 deletions(-) diff --git a/IkiWiki/Render.pm b/IkiWiki/Render.pm index 599bb26e2..fe0b3138a 100644 --- a/IkiWiki/Render.pm +++ b/IkiWiki/Render.pm @@ -58,52 +58,6 @@ sub backlinks ($) { return @links; } -sub find_changed_links (@_) { - my %linkchanged; - my %linkchangers; - foreach my $file (@_) { - my $page=pagename($file); - - if (exists $links{$page}) { - foreach my $l (@{$links{$page}}) { - my $link=bestlink($page, $l); - if (length $link) { - if (! exists $oldlinks{$page} || - ! grep { bestlink($page, $_) eq $link } @{$oldlinks{$page}}) { - $linkchanged{$link}=1; - $linkchangers{lc($page)}=1; - } - } - else { - if (! grep { lc $_ eq lc $l } @{$oldlinks{$page}}) { - $linkchangers{lc($page)}=1 - } - } - - } - } - if (exists $oldlinks{$page}) { - foreach my $l (@{$oldlinks{$page}}) { - my $link=bestlink($page, $l); - if (length $link) { - if (! exists $links{$page} || - ! grep { bestlink($page, $_) eq $link } @{$links{$page}}) { - $linkchanged{$link}=1; - $linkchangers{lc($page)}=1; - } - } - else { - if (! grep { lc $_ eq lc $l } @{$links{$page}}) { - $linkchangers{lc($page)}=1 - } - } - } - } - } - - return \%linkchanged, \%linkchangers; -} - sub genpage ($$) { my $page=shift; my $content=shift; @@ -389,6 +343,7 @@ sub refresh () { my ($files, $exists)=find_src_files(); my (%rendered, @add, @del, @internal, @internal_change); + # check for added or removed pages foreach my $file (@$files) { my $page=pagename($file); @@ -452,10 +407,11 @@ sub refresh () { $stat[9] > $pagemtime{$page} || $forcerebuild{$page}) { $pagemtime{$page}=$stat[9]; + if (isinternal($page)) { - push @internal_change, $file; # Preprocess internal page in scan-only mode. preprocess($page, $page, readfile($srcfile), 1); + push @internal_change, $file; } else { push @needsbuild, $file; @@ -464,7 +420,19 @@ sub refresh () { } run_hooks(needsbuild => sub { shift->(\@needsbuild) }); - # scan and render files + # before scanning, make a note of where pages' + # old links pointed + my %oldlink_targets; + foreach my $file (@needsbuild, @del) { + my $page=pagename($file); + if (exists $oldlinks{$page}) { + foreach my $l (@{$oldlinks{$page}}) { + $oldlink_targets{$page}{$l}=bestlink($page, $l); + } + } + } + + # scan and render changed files foreach my $file (@needsbuild) { debug(sprintf(gettext("scanning %s"), $file)); scan($file); @@ -499,99 +467,121 @@ sub refresh () { } } } - - if (%rendered || @del || @internal || @internal_change) { + + # determine which links, on what pages, have changed + my %backlinkchanged; + my %linkchangers; + foreach my $file (@needsbuild, @del) { + my $page=pagename($file); + my %link_targets; + if (exists $links{$page}) { + foreach my $l (@{$links{$page}}) { + my $target=bestlink($page, $l); + if (! exists $oldlink_targets{$page}{$l} || + $target ne $oldlink_targets{$page}{$l}) { + $backlinkchanged{$l}=1; + $linkchangers{lc($page)}=1; + } + delete $oldlink_targets{$page}{$l}; + } + } + if (exists $oldlink_targets{$page} && + %{$oldlink_targets{$page}}) { + foreach my $target (keys %{$oldlink_targets{$page}}) { + $backlinkchanged{$target}=1; + } + $linkchangers{lc($page)}=1; + } + } + %oldlink_targets=(); + + # rebuild dependant pages, recursively + my $deps=(@needsbuild || @del || @internal || @internal_change); + do { + $deps=0; my @changed=(keys %rendered, @del); - my ($linkchanged, $linkchangers)=find_changed_links(@changed); - - my $unsettled; - do { - $unsettled=0; - @changed=(keys %rendered, @del); - my @exists_changed=(@add, @del); + my @exists_changed=(@add, @del); - my %lc_changed = map { lc(pagename($_)) => 1 } @changed; - my %lc_exists_changed = map { lc(pagename($_)) => 1 } @exists_changed; + my %lc_changed = map { lc(pagename($_)) => 1 } @changed; + my %lc_exists_changed = map { lc(pagename($_)) => 1 } @exists_changed; - # rebuild dependant pages - foreach my $f (@$files) { - next if $rendered{$f}; - my $p=pagename($f); - my $reason = undef; + foreach my $f (@$files) { + next if $rendered{$f}; + my $p=pagename($f); + my $reason = undef; - if (exists $depends_simple{$p}) { - foreach my $d (keys %{$depends_simple{$p}}) { - if (($depends_simple{$p}{$d} & $IkiWiki::DEPEND_CONTENT && - $lc_changed{$d}) - || - ($depends_simple{$p}{$d} & $IkiWiki::DEPEND_PRESENCE && - $lc_exists_changed{$d}) - || - ($depends_simple{$p}{$d} & $IkiWiki::DEPEND_LINKS && - $linkchangers->{$d}) - ) { - $reason = $d; - last; - } + if (exists $depends_simple{$p}) { + foreach my $d (keys %{$depends_simple{$p}}) { + if (($depends_simple{$p}{$d} & $IkiWiki::DEPEND_CONTENT && + $lc_changed{$d}) + || + ($depends_simple{$p}{$d} & $IkiWiki::DEPEND_PRESENCE && + $lc_exists_changed{$d}) + || + ($depends_simple{$p}{$d} & $IkiWiki::DEPEND_LINKS && + $linkchangers{$d}) + ) { + $reason = $d; + last; } } + } - if (exists $depends{$p} && ! defined $reason) { - D: foreach my $d (keys %{$depends{$p}}) { - my $sub=pagespec_translate($d); - next if $@ || ! defined $sub; - - # only consider internal files - # if the page explicitly depends - # on such files - my $internal_dep=$d =~ /internal\(/; - - my @candidates; - if ($depends{$p}{$d} & $IkiWiki::DEPEND_PRESENCE) { - @candidates=@exists_changed; - push @candidates, @internal - if $internal_dep; - } - if (($depends{$p}{$d} & ($IkiWiki::DEPEND_CONTENT | $IkiWiki::DEPEND_LINKS))) { - @candidates=@changed; - push @candidates, @internal, @internal_change - if $internal_dep; - } + if (exists $depends{$p} && ! defined $reason) { + D: foreach my $d (keys %{$depends{$p}}) { + my $sub=pagespec_translate($d); + next if $@ || ! defined $sub; + + # only consider internal files + # if the page explicitly depends + # on such files + my $internal_dep=$d =~ /internal\(/; + + my @candidates; + if ($depends{$p}{$d} & $IkiWiki::DEPEND_PRESENCE) { + @candidates=@exists_changed; + push @candidates, @internal + if $internal_dep; + } + if (($depends{$p}{$d} & ($IkiWiki::DEPEND_CONTENT | $IkiWiki::DEPEND_LINKS))) { + @candidates=@changed; + push @candidates, @internal, @internal_change + if $internal_dep; + } - foreach my $file (@candidates) { - next if $file eq $f; - my $page=pagename($file); - if ($sub->($page, location => $p)) { - if ($depends{$p}{$d} & $IkiWiki::DEPEND_LINKS) { - next unless $linkchangers->{lc($page)}; - } - $reason = $page; - last D; + foreach my $file (@candidates) { + next if $file eq $f; + my $page=pagename($file); + if ($sub->($page, location => $p)) { + if ($depends{$p}{$d} & $IkiWiki::DEPEND_LINKS) { + next unless $linkchangers{lc($page)}; } + $reason = $page; + last D; } } } - - if (defined $reason) { - debug(sprintf(gettext("building %s, which depends on %s"), $f, $reason)); - render($f); - $rendered{$f}=1; - $unsettled=1; - last; - } } - } while $unsettled; - - # update backlinks at end - foreach my $link (keys %{$linkchanged}) { - my $linkfile=$pagesources{$link}; - if (defined $linkfile) { - next if $rendered{$linkfile}; - debug(sprintf(gettext("building %s, to update its backlinks"), $linkfile)); - render($linkfile); - $rendered{$linkfile}=1; + + if (defined $reason) { + debug(sprintf(gettext("building %s, which depends on %s"), $f, $reason)); + render($f); + $rendered{$f}=1; + $deps=1; + last; } } + } while $deps; + + # update backlinks + foreach my $link (keys %backlinkchanged) { + my $linkfile=$pagesources{$link}; + if (defined $linkfile) { + next if $rendered{$linkfile}; + debug(sprintf(gettext("building %s, to update its backlinks"), $linkfile)); + render($linkfile); + $rendered{$linkfile}=1; + } } # remove no longer rendered files -- 2.26.2