User:TotoBaggins

#!/usr/bin/perl -w
 # FILE: wiki-blame.pl
 # AUTHOR: TotoBaggins on en.wikipedia.org
 # 
 # LICENSE: GPL
 #
 # DESCRIPTION: This program outputs a URL of the first revision of an article
 # to contain a particular bit of text.  We only download log_2 N articles,
 # so it's reasonably fast and kind to the servers.
 # 
 # USAGE:
 #
 #    ./wiki-blame.pl {article or history URL} {offending text}
 #
 # The URL must be url-encoded.
 # The offending text should be quoted as a single argument.
 # 
 # EXAMPLES:
 #
 # Find which revision inserted some text at or before an old revision
 # of the C++ article:
 # 
 #   ./wiki-blame.pl 'http://en.wikipedia.org/w/index.php?title=C%2B%2B&oldid=101608911' 'Evil Text'
 #
 #
 # Find which revision inserted some text at or before the current revision
 # of the C++ article:
 #
 #   ./wiki-blame.pl 'http://en.wikipedia.org/wiki/C%2B%2B' 'Evil Text'
 #
 # 
 # BUGS:
 #
 # -- We only look back 2000 edits worth.
 # -- We could be politer and faster if we stepped back through
 #    history exponentially.
 # -- We are too dependent on wikipedia.org's URL layout.
 # 
 
 use strict;
 use LWP::UserAgent;
 use HTML::Parser;
 use HTML::LinkExtor;
 use Carp;
 use Data::Dumper;
 
 my $WebAgent = LWP::UserAgent->new(keep_alive => 1);
 
 sub get_page
 {
     my $url = shift;
     my $response = $WebAgent->get($url);
     $response->is_success() or croak $response->status_line();
     return $response->content();
 }
 
 sub get_links
 {
     my $url = shift;
     my $url_front = $url;
     $url_front =~ s,^([^/]+//[^/]+)/.*,$1,;
     my $page = get_page($url);
     my $linky = HTML::LinkExtor->new();
     $linky->utf8_mode(1);
     $linky->parse($page) or croak "Can't parse: $page";
     my @urls;
     foreach my $link ($linky->links())
     {
         my ($tag, %links) = @$link;
         my $url = $links{href} or next;
         push @urls, "$url_front$url";
     }
     return @urls;
 }
 
 
 use constant YES_MARKER => 100;
 use constant NO_MARKER  => 0;
 
 {
     my %MarkerCache;
     sub url_has_text
     {
         my ($url, $text) = @_;
         unless (defined $MarkerCache{$url})
         {
             my $page = get_page($url);
             use File::Slurp;
             $url =~ /oldid=(\d+)/;
             write_file("oldid-$1.html", $page);
             $MarkerCache{$url} = index($page, $text) >= 0
                                     ? YES_MARKER : NO_MARKER;
         }
         return $MarkerCache{$url};
     }
 }
 
 # This is from List::Search, which had a bug.  It can be
 # removed when "List::Search::nlist_search(2, [2, 2, 2])" returns 0 and not 1
 sub custom_list_search
 {
     my ($cmp_code, $key, $array_ref) = @_;
 
     my $max_index = scalar(@$array_ref) - 1;
 
     my $low  = 0;
     my $mid  = undef;
     my $high = $max_index;
     my $lowest_match = undef;
 
     while ($low <= $high)
     {
         $mid = int($low + (($high - $low) / 2));
         my $mid_val = $array_ref->[$mid];
 
         my $cmp_result = $cmp_code->($key, $mid_val);
 
         if ($cmp_result > 0)
         {
             $low = $mid + 1;
         }
         else
         {
             if ($cmp_result == 0
                  && (!defined($lowest_match) || $lowest_match > $mid))
             {
                 $lowest_match = $mid;
             }
             $high = $mid - 1;
         }
     }
 
     # Look at the values here and work out what to return.
     # Perhaps there are no matches in the array
     return -1 if $cmp_code->($key, $array_ref->[-1]) == 1;
 
     # Perhaps $mid is just before the best match
     return $mid + 1 if $cmp_code->($key, $array_ref->[$mid]) == 1;
 
     # $mid is correct
     return $mid;
 }
 
 sub snarf_history_urls
 {
     my ($article_url, $limit) = @_;
 
     my $idx_url = $article_url;
     $idx_url =~ s/\&oldid=(\d+)$/\&action=history&limit=$limit/
         ||
     $idx_url =~ s,/wiki/(.+),/w/index.php?title=$1&limit=$limit&action=history,
         or die $idx_url;
 
     my @all_urls = get_links($idx_url);
 
     my @history_urls;
     foreach my $url (@all_urls)
     {
         # only old article urls
         next unless $url =~ m,/index.php\?title=[^&]+&oldid=\d+$,;
 
         push @history_urls, $url;
     }
     # make chronological
     @history_urls = reverse @history_urls;
 
     return @history_urls;
 }
 
 sub get_first_history_url
 {
     my $url = shift;
     return $url if $url =~ /&oldid=\d/;
     my @history_urls = snarf_history_urls($url, 1);
     return $history_urls[0];
 }
 
 sub find_rev_that_added
 {
     my ($offending_history_url, $offending_text) = @_;
     my $history_index_url = $offending_history_url;
 
     # FIXME: we limit it to 2000 urls to be kind to the wikiservers
     # We should really bite off pieces of history stepwise.
     my $max_urls = 2000;
     my @history_urls = snarf_history_urls($offending_history_url, $max_urls);
 
     $offending_history_url =~ /\&oldid=(\d+)/ or die $offending_history_url;
     my $offending_id = $1;
 
 #     my %url2index;
     my $saw_offender;
     my @before_offender_urls;
     foreach my $url (@history_urls)
     {
 #         $url2index{$url} = @before_offender_urls;
         push @before_offender_urls, $url;
         last if $url =~ /\&oldid=$offending_id\b/;
     }
 
     my $url2marker = sub {
         my ($key, $url) = @_;
         my $has_it = url_has_text($url, $offending_text);
         my $ret = $key <=> $has_it;
 #         warn "has($has_it), ret($ret), u2i($url2index{$url}), $url\n";
         return $key <=> $has_it;
     };
     my $first_with = custom_list_search($url2marker, YES_MARKER,
                                         \@before_offender_urls);
     return unless $first_with >= 0;
 
     if ($first_with == $max_urls)
     {
         warn "Warning: It looks like that edit occurred further in "
              . "the past than I feel comfortable looking (beyond "
              . "$max_urls edits).\n";
         return;
     }
 
     return $before_offender_urls[$first_with];
 }
 
 @ARGV == 2 or die "usage: $0 {article or history URL} {offending text}\n";
 my $url = shift;
 my $offending_text = shift;
 
 my $offending_history_url = get_first_history_url($url);
 
 if (my $found_url = find_rev_that_added($offending_history_url,
                                         $offending_text))
 {
     if ($found_url eq $offending_history_url)
     {
         print "No earlier revisions found.\n";
     }
     else
     {
         print "Earliest revision: $found_url\n";
     }
 }
 else
 {
     print "Not found\n";
 }