Dest.pm #37

package VCP::Dest ;

=head1 NAME

VCP::Dest - A base class for VCP destinations

=head1 SYNOPSIS

=head1 DESCRIPTION

=head1 EXTERNAL METHODS

=over

=for test_scripts t/01sort.t

=cut

use strict ;

use Carp ;
use File::Spec ;
use File::Spec::Unix ;
use UNIVERSAL qw( isa ) ;
use VCP::Revs ;
use VCP::Debug qw(:debug) ;
use VCP::Utils qw( start_dir escape_filename empty );

use vars qw( $VERSION $debug ) ;

$VERSION = 0.1 ;

$debug = 0 ;

use base 'VCP::Plugin' ;

use fields (
   'DEST_HEADER',          ## Holds header info until first rev is seen.
   'DEST_SORT_SPEC',       ## ARRAY of field names to sort by
   'DEST_SORT_KEYS',       ## HASH of sort keys, indexed by name and rev.
   'DEST_COMMENT_TIMES',   ## The average time of all instances of a comment
   'DEST_DEFAULT_COMMENT', ## The comment to use when a comment is undefined
                           ## This is used when presorting/merging so
                           ## that comment will still be used to
                           ## compare when selecting the next rev to
                           ## merge, otherwise it would be removed as
                           ## a sporadic field.

   'DEST_HEAD_REVS',       ## Map of head revision on each branch of each file
   'DEST_REV_MAP',         ## Map of source rev id to destination file & rev
   'DEST_MAIN_BRANCH_ID',  ## Container of main branch_id for each file
   'DEST_FILES',           ## Map of files->state, for CVS' sake
   'DEST_DB_DIR',          ## Directory name in which to store the transfer
                           ## state databases
) ;

use VCP::Revs ;


=item new

Creates an instance, see subclasses for options.  The options passed are
usually native command-line options for the underlying repository's
client.  These are usually parsed and, perhaps, checked for validity
by calling the underlying command line.

=cut

sub new {
   my $class = shift ;
   $class = ref $class || $class ;

   my VCP::Dest $self = $class->SUPER::new( @_ ) ;

   ## rev_id is here in case the change id isn't,
   ## name is here for VSS deletes, which have no other data.
#   $self->set_sort_spec( "presort,change_id,time,avg_comment_time,comment,branch_id,name,rev_id" ) ;
   $self->set_sort_spec( "change_id,time,user_id,comment,branch_id,name" ) ;

   return $self ;
}

=back


###############################################################################

=head1 SUBCLASSING

This class uses the fields pragma, so you'll need to use base and 
possibly fields in any subclasses.

=head2 SUBCLASS API

These methods are intended to support subclasses.

=over


=item parse_options

    $self->parse_options( \@options, @specs );

Parses common options.

=cut

sub parse_options {
   my VCP::Dest $self = shift;

   $self->SUPER::parse_options( 
      @_,
      "db-dir=s"  => sub { $self->db_dir( $_[1] ) },
   );

   if( ! empty $self->db_dir && empty $self->repo_id ) {
      warn "--repo-id required if --db-dir present\n";
      $self->usage_and_exit ;
   }
}


=item digest

    $self->digest( "/tmp/readers" ) ;

Returns the Base64 MD5 digest of the named file.  Used to compare a base
rev (which is the revision *before* the first one we want to transfer) of
a file from the source repo to the existing head rev of a dest repo.

The Base64 version is returned because that's what RevML uses and we might
want to cross-check with a .revml file when debugging.

=cut

sub digest {
   shift ;  ## selfless little bugger, isn't it?
   my ( $path ) = @_ ;

   require Digest::MD5 ;
   my $d= Digest::MD5->new ;
   open DEST_P4_F, "<$path" or die "$!: $path" ;
   $d->addfile( \*DEST_P4_F ) ;

   my $digest = $d->b64digest ;
   close DEST_P4_F ;
   return $digest ;
}


=item compare_base_revs

   $self->compare_base_revs( $rev ) ;

Checks out the indicated revision fromt the destination repository and
compares it (using digest()) to the file from the source repository
(as indicated by $rev->work_path). Dies with an error message if the
base revisions do not match.

Calls $self->checkout_file( $rev ), which the subclass must implement.

=cut

sub compare_base_revs {
   my VCP::Dest $self = shift ;
   my ( $rev ) = @_ ;

   ## This block should only be run when transferring an incremental rev.
   ## from a "real" repo.  If it's from a .revml file, the backfill will
   ## already be done for us.
   ## Grab it and see if it's the same...
   my $source_digest = $self->digest( $rev->work_path ) ;

   my $backfilled_path = $self->checkout_file( $rev );
   my $dest_digest     = $self->digest( $backfilled_path );

   die( "vcp: base revision\n",
       $rev->as_string, "\n",
       "differs from the last version in the destination p4 repository.\n",
       "    source digest: $source_digest (in ", $rev->work_path, ")\n",
       "    dest. digest:  $dest_digest (in ", $backfilled_path, ")\n"
   ) unless $source_digest eq $dest_digest ;
}


=item header

Gets/sets the $header passed to handle_header().

Generally not overridden: all error checking is done in new(), and
no output should be generated until output() is called.

=cut

sub header {
   my VCP::Dest $self = shift ;
   $self->{DEST_HEADER} = shift if @_ ;
   return $self->{DEST_HEADER} ;
}


=item db_dir

Set or return the directory name where the transfer state databases
are stored.

This is the directory to store the state information for this transfer
in.  This includes the mapping of source repository versions
(name+rev_id, usually) to destination repository versions and the
status of the last transfer, so that incremental transfers may restart
where they left off.

=cut

sub db_dir {
   my VCP::Dest $self = shift ;
   
   $self->{DEST_DB_DIR} = shift if @_;
   return $self->{DEST_DB_DIR};
}

=item _db_store_location

Determine the location to store the transfer state databases.

Uses the absolute path provided by the --db-dir option if present,
else use directory 'vcp_state' in the directory the program was
started in.  The file name is an escaped repo_id.

=cut

sub _db_store_location {
   my VCP::Dest $self = shift ;

   my $loc = $self->db_dir;
   $loc = ( empty $loc )
      ? File::Spec->catdir( start_dir, "vcp_state" )
      : File::Spec::Unix->rel2abs( $loc ) ;

   return File::Spec->catfile( $loc, escape_filename $self->repo_id );
}

=item rev_map

Set or return a reference to the RevMapDB in use.

=cut

sub rev_map {
   my VCP::Dest $self = shift ;
   
   $self->{DEST_REV_MAP} ||= do {
      require VCP::RevMapDB;
      VCP::RevMapDB->new( 
         StoreLoc => $self->_db_store_location,
      );
   };
}

=item head_revs

Set or return a reference to the HeadRevsDB in use.

=cut

sub head_revs {
   my VCP::Dest $self = shift ;
   
   $self->{DEST_HEAD_REVS} ||= do {
      require VCP::HeadRevsDB;

      $self->{DEST_HEAD_REVS} = VCP::HeadRevsDB->new( 
         StoreLoc => $self->_db_store_location,
      );
   };
}

=item main_branch_id

Set or return a reference to the MainBranchIdDB in use.

=cut

sub main_branch_id {
   my VCP::Dest $self = shift;
   
   $self->{DEST_MAIN_BRANCH_ID} ||= do {
      require VCP::MainBranchIdDB;
      $self->{DEST_MAIN_BRANCH_ID} = VCP::MainBranchIdDB->new(
         StoreLoc => $self->_db_store_location,
      );
   };
}

=item files

Set or return a reference to the HeadRevsDB in use.

=cut

sub files {
   my VCP::Dest $self = shift ;
   
   $self->{DEST_FILES} ||= do {
      require VCP::FilesDB;
      $self->{DEST_FILES} = VCP::FilesDB->new(
         StoreLoc => $self->_db_store_location,
      );
   }
}

=back

=head2 SUBCLASS OVERLOADS

These methods are overloaded by subclasses.

=over

=item backfill

   $dest->backfill( $rev ) ;

Checks the file indicated by VCP::Rev $rev out of the target repository if
this destination supports backfilling.  Currently, only the revml destination
does not support backfilling.

The $rev->workpath must be set to the filename the backfill was put
in.

This is used when doing an incremental update, where the first revision of
a file in the update is encoded as a delta from the prior version.  A digest
of the prior version is sent along before the first version delta to
verify it's presence in the database.

So, the source calls backfill(), which returns TRUE on success, FALSE if the
destination doesn't support backfilling, and dies if there's an error in
procuring the right revision.

If FALSE is returned, then the revisions will be sent through with no
working path, but will have a delta record.

MUST BE OVERRIDDEN.

=cut

sub backfill {
   my VCP::Dest $self = shift ;
   my ( $r ) = @_;

   die ref( $self ) . "::checkout_file() not found for ", $r->as_string, "\n"
      unless $self->can( "checkout_file" );

   my $work_path = $self->checkout_file( $r );

   link $work_path, $r->work_path
      or die "$! linking $work_path to ", $r->work_path;
   unlink $work_path or die "$! unlinking $work_path";
}


=item handle_footer

   $dest->handle_footer( $footer ) ;

Does any cleanup necessary.  Not required.  Don't call this from the override.

=cut

sub handle_footer {
   my VCP::Dest $self = shift ;
   return ;
}

=item handle_header

   $dest->handle_header( $header ) ;

Stows $header in $self->header.  This should only rarely be overridden,
since the first call to handle_rev() should output any header info.

=cut

sub handle_header {
   my VCP::Dest $self = shift ;

   my ( $header ) = @_ ;

   $self->header( $header ) ;

   return ;
}

=item handle_rev

   $dest->handle_rev( $rev ) ;

Outputs the item referred to by VCP::Rev $rev.  If this is the first call,
then $self->none_seen will be TRUE and any preamble should be emitted.

MUST BE OVERRIDDEN.  Don't call this from the override.

=cut

sub handle_rev {
   my VCP::Dest $self = shift ;
   die ref( $self ) . "::handle_rev() not found, Oops.\n" ;
}

=back

=head2 Sorting

=over

=item set_sort_spec

   $dest->set_sort_spec( @key_names ) ;

@key_names specifies the list of fields to sort by.  Each element in the array
may be a comma separated list.  Such elements are treated as though each name
was passed in it's own element; so C<( "a", "b,c" )> is equivalent to C<("a",
"b", "c")>.  This eases command line parameter parsing.

Sets the sort specification, checking to make sure that the field_names
have corresponding parse_sort_field_... handlers in this object.

Legal field names include: name, change, change_id, rev, rev_id, comment,
time.

If a field is missing from all revs, it is ignored, however at
least one of rev_id, change, or time *must* be used.

Default ordering is by

  - change_id    (compared numerically using <=>, for now)
  - time         (commit time: simple numeric, since this is a simple number)
  - comment      (alphabetically, case sensitive)

This ordering benefits change number oriented systems while preserving
commit order for non-change number oriented systems.

If change_id is undefined in either rev, it is not used.

If time is undefined in a rev, the value "-1" is used.  This causes
base revisions (ie digest-only) to precede real revisions.

That's not always good, though: one of commit time or change number should
be defined!  

Change ids are compared numerically, times by date order (ie numerically, since
time-since-the-epoch is used internally). Comments are compared alphabetically.

Each sort field is split in to one or more segments, see the appropriate
parse_sort_field_... documentation.

Here's the sorting rules:
  - Revisions are compared field by field.
  - The first non-equal field determines sort order.
  - Fields are compared segment by segment.
  - The first non-equal segment determines sort order.
  - A not-present segment compares as less-than any other segment, so
    fields that are leading substrings of longer fields come first, and
    not-present fields come before all present fields, including empty
    fields.

=cut

sub set_sort_spec {
   my VCP::Dest $self = shift ;

   my @spec = split ',', join ',', @_ ;

#   for ( @spec ) {
#      next if /^presort\b/;
#      next if $self->can( "parse_sort_field_$_" ) ;
#      croak "Sort specification $_ is not available in ",
#         ref( $self ) =~ /.*:(.*)/ ;
#   }

   debug "vcp: sort spec: ", join ",", @spec
      if explicitly_debugging "sort" || debugging $self ;
   $self->{DEST_SORT_SPEC} = \@spec ;
   return undef ;
}


=item How rev_id and change_id are sorted

C<change_id> or C<rev_id> are split in to segments
suitable for sorting.

The splits occur at the following points:

   1. Before and after each substring of consecutive digits
   2. Before and after each substring of consecutive letters
   3. Before and after each non-alpha-numeric character

The substrings are greedy: each is as long as possible and non-alphanumeric
characters are discarded.  So "11..22aa33" is split in to 5 segments:
( 11, "", 22, "aa", 33 ).

If a segment is numeric, it is left padded with 10 NUL characters.

This algorithm makes 1.52 be treated like revision 1, minor revision 52, not
like a floating point C<1.52>.  So the following sort order is maintained:

   1.0
   1.0b1
   1.0b2
   1.0b10
   1.0c
   1.1
   1.2
   1.10
   1.11
   1.12

The substring "pre" might be treated specially at some point.

(At least) the following cases are not handled by this algorithm:

   1. floating point rev_ids: 1.0, 1.1, 1.11, 1.12, 1.2
   2. letters as "prereleases": 1.0a, 1.0b, 1.0, 1.1a, 1.1

Never returns (), since C<rev_id> is a required field.

=cut

sub _compile_sort_rec_indexer {
   my ( $rev, $spec ) = @_ ;

   my $code = join "",
      q[sub { my $r = shift; pack '],
      map( $rev->pack_format( $_ ), @$spec ),
      q[', ],
      join( ", ", map $rev->index_value_expression( $_ ), @$spec ),
      q[}];

   debug caller, $code if debugging __PACKAGE__;

   return ( eval $code or die $@ );
}


sub _compile_sort_rec_bulk_indexer {
   my ( $rev, $spec ) = @_ ;

   my $code = join "",
      q[sub { my $revs = shift; my $r; for my $sr ( @$revs ) { $r = $sr->[0]; $sr->[1] = pack '],
      map( $rev->pack_format( $_ ), @$spec ),
      q[', ],
      join( ", ", map $rev->index_value_expression( $_ ), @$spec ),
      q[}}];

   debug caller, $code if debugging __PACKAGE__;

   return ( eval $code or die $@ );
}


=item sort_revs

   $source->dest->sort_revs( $source->revs ) ;

This sorts the revisions that the source has identified in to whatever order
is needed by the destination.

Sorting is normally done in two passes.  Each file's revisions are sorted
by change, rev_id, or time, then the resulting lists of revisions are
sorted in to one long list by pulling the "least" revision off the head
of each list based on change, time, comment, and name.

This two-phased approach ensures that revisions of a file are always in
proper order no matter what order they are provided, and furthermore in an
order that enables change number aggregation (which is useful even if the
destination does not provide change numbers if only to do batch submits
or get commit timestamps in a sensible order).

This is all because, when doing change aggregation, it's necessary to put
revision number last in the sort key fields.  If revisions of a file have bogus
timestamps, say, this can cause revisions of a file to be sorted out of order.
So we sort on rev_id first to guarantee that each file's versions are in a
correct order, then we do change aggregation.

The sort specification "presort" is used to engage the presort-and-merge
algorithm, and is in the default sort spec.  There is currently no way to
affect the sort order in the presort phase.

=cut

## TODO: see if a loop that works on all the records when the default ## sort
## key is used is much faster, I suspect it will be.

sub _calc_sort_recs {
   my VCP::Dest $self = shift ;
   my ( $sort_recs, $spec ) = @_;

   return unless @$sort_recs;

   debug "vcp sort key: ", join ", ", @$spec
      if debugging "sort" ;

   if ( grep /avg_comment_time/, @$spec ) {
      $self->{DEST_COMMENT_TIMES} = {};
      for ( @$sort_recs ) {
         my $r = $_->[0];
         my $comment = defined $r->comment
             ? $r->comment
             : $r->is_base_rev ? "" : undef;
         my $time = defined $r->sort_time
             ? $r->sort_time
             : $r->is_base_rev ? 0 : undef;
         next unless defined $comment && defined $time;
         push @{$self->{DEST_COMMENT_TIMES}->{$comment}}, $time;
      }

      for ( values %{$self->{DEST_COMMENT_TIMES}} ) {
         next unless @$_;
         my $sum;
         $sum += $_ for @$_;
         $_ = $sum / @$_;
      }
   }

   my $indexer = _compile_sort_rec_bulk_indexer( $sort_recs->[0]->[0], $spec );
   $indexer->( $sort_recs );
}

sub _remove_sporadics {
   my VCP::Dest $self = shift;
   my ( $sort_recs, $spec ) = @_;
return; ## TODO!!!

   my @not_seen = my @seen = ( 0 ) x @$spec;
   my @sporadics;
   my @keepers = ( 0 );  ## Always keep the rev ($sort_rec[0])
   my $its_ok;

   my $max_i = 0;
   for ( @$sort_recs) {
      $max_i = $#$_ if $#$_ > $max_i;
      for my $i ( 1..$#$_ ) {
         if ( @{$_->[$i]} && defined $_->[$i]->[0] ) {
            ++$seen[$i];
         }
         else {
            ++$not_seen[$i];
         }
      }
   }
   for my $i ( 1..$max_i ) {
      if ( $seen[$i] && $not_seen[$i] ) {
         push @sporadics, $i;
         next;
      }
      push @keepers, $i;

      if (
         $seen[$i]
         && $spec->[$i-1] =~ /^(change|rev|time)/
      ) {
         ## One of the numeric ordering fields is present.
         $its_ok = 1;
      }
   }

   if ( @sporadics ) {
      my @sp_desc = map 
         "$spec->[$_] (seen $seen[$_] times, missing $not_seen[$_])\n",
         @sporadics;
      unless ( $its_ok ) {
         die "missing sort key",
            @sp_desc == 1 ? () : "s",
            " while sorting revisions:",
            @sp_desc == 1
               ? ( " ", @sp_desc )
               : ( "\n", map "    $_", @sp_desc ),
            "sort keys are ",
            join( ", ", @$spec ),
            "\n";
      }

      debug "removing sporadic sort key",
         @sp_desc == 1
            ? ( ": ", @sp_desc )
            : ( "s:\n", map "    $_", @sp_desc )
         if debugging;

confess "not keeping revs" unless $keepers[0] == 0;

      @$_ = @{$_}[@keepers] for @$sort_recs;
   }
}


sub _presort_revs {
   my VCP::Dest $self = shift ;
   my ( $revs, $sort_spec ) = @_;

   debug "presorting revisions by ", join ", ", @$sort_spec
      if debugging ;

   debug "...categorizing and generating index" if debugging ;
   my %p;
   my $indexer;
   for my $r ( $revs->get ) {
      $indexer ||= _compile_sort_rec_indexer( $r, $sort_spec );
      ## TODO: use $r->source_filebranch_id here as the key
      push @{$p{$r->name . "\000" . ( $r->branch_id || "" )}}, [ $r, $indexer->( $r ) ];
   }

   debug "...presorting revisions" if debugging ;

   my @p = map [ sort { $a->[1] cmp $b->[1] } @$_ ], values %p;
   debug "...done presort" if debugging ;
   return \@p;
}


sub _merge_presorted_revs {
   my VCP::Dest $self = shift ;
   my ( $presorted, $spec ) = @_;

   debug "merging presorted revisions by ", join ", ", @$spec
      if debugging ;

   my @p = splice @$presorted;

   my @sort_recs = map @$_, @p;

   $self->{DEST_DEFAULT_COMMENT} = "";
   debug "...generating index" if debugging ;
   $self->_calc_sort_recs( \@sort_recs, $spec );
   $self->{DEST_DEFAULT_COMMENT} = undef;

   ## Fill in missing time values as best as we can for things like
   ## VSS.
   if ( grep $_ eq "time", @$spec ) {
      debug "...filling in missing time values" if debugging ;
      my $found = 0;
      for ( @p ) {
         my $prev_t = "9" x 10;
         for ( reverse @$_ ) {
            my $t = $_->[0]->time;
            if ( defined $t ) {
               $prev_t = $t;
            }
            else {
               $_->[0]->sort_time( $prev_t );
            }
         }
      }
      debug "...estimated $found time values" if debugging ;
   }

   $self->_remove_sporadics( \@sort_recs, $spec );

   debug "...merging presorted lists" if debugging;
   my @result;

   my %rank;

   debug "...ranking" if debugging;
   $rank{ int $_ } = keys %rank for
        sort { $a->[1] cmp $b->[1] } map @$_, @p;

   debug "......sorting first files by rank" if debugging;
   @p = sort { $rank{ int $a->[0] } <=> $rank{ int $b->[0] } } @p;
#for my $i ( 1..$#p ) {
#    die "sort already broken" if $rank{ int $p[$i-1]->[0]} > $rank{ int $p[$i]->[0] };
#}
   debug "......merging" if debugging;
   while ( @p ) {
      push @result, (shift @{$p[0]})->[0];

      if ( ! @{$p[0]} ) {
         ## No more revs for that file.
         shift @p;
         next if @p >= 2;
         last unless @p;  ## Could have been the last rev.
      }

      if ( @p == 1 ) {
         ## ...and it was the only or next to last file.
         push @result, map $_->[0], @{shift @p} if @p == 1;
         last;
      }

      ## $p[0] may need to be moved.

      my $r = $rank{int $p[0]->[0]};

      ## Do an insertion sort using a binary search.
      ## After seeing it should
      next if $r < $rank{ int $p[1]->[0] }; # Nope.  it stays where it is.

      my $p = shift @p;

      if ( $r > $rank{ int $p[-1]->[0] } ) {
          # hmmm, it goes on the end.  Even if this is not a common
          # case, the binary search below does not deal well if we
          # don't do this.
          push @p, $p;
          next;
      }

      my ( $l, $u ) = ( 0, $#p );
      # Invariants
      #    $l is at or below the insertion point.
      #    $u + 1 is at or above the insertion point.

      my $m;
      while ( $l < $u ) {
         $m = ( $l + $u ) >> 1;  ## TODO: interpolate $m?
         if ( $r > $rank{ int $p[$m]->[0] } ) {
            # must insert after $m.
            $l = $m + 1;
         }
         else {
            # must insert before $m+1
            $u = $m;
         }
      }

#print STDERR "=$l\n";

      splice @p, $l, 0, $p;

#for my $i ( 1..$#p ) {
#   die "sort broken" if $rank{ int $p[$i]->[0]} < $rank{ int $p[$i-1]->[0] };
#}
   }
   debug "done merging" if debugging $self;
   @result;
}

sub _eq($$) {
    defined $_[0] && defined $_[1]
       ? $_[0] eq $_[1]
       : ! defined( $_[0] ) && ! defined( $_[1] );

}

sub _in_same_change {
   my ( $ra, $rb ) = @_;

   return $ra->change_id eq $rb->change_id
      unless empty $ra->change_id || empty $rb->change_id;

   return _eq( $ra->user_id, $rb->user_id )
      && _eq( $ra->comment, $rb->comment )
      && (
         ( ! $ra->is_placeholder_rev && ! $rb->is_placeholder_rev )
         || ( $ra->is_placeholder_rev
            && $rb->is_placeholder_rev
            &&  _eq $ra->branch_id, $rb->branch_id
         )
      );

      ## placeholders must be on same branch; regular revs don't
      ## (we assume comments will break those more readily);
      ## placeholders and non-placeholders should not be in same
      ## change.
}


## The "normal" way of VCP conversions is to create branches in
## one change and then make the first edits on another change.
## In this situation, the change number aggregation here should
## be the proper way to group revs in to changes, otherwise it's
## up to the subclass.
## For testing purposes, and possibly for real world use, we also
## allow the branch and the edit to occur in the same change.
sub add_in_change_numbers {
   return 1;
}


sub sort_revs {
   goto &full_sort_revs if $_[0]->isa( "VCP::Dest::revml" );

   my VCP::Dest $self = shift ;

   my ( $revs ) = @_ ;
   
   ## Use the ->previous references to find the roots and then
   ## reorder the revs by growing up from the roots.

   my %rev_kids;
   my @roots;
   my @sort_recs;

   debug "creating revision trees and indexing them"
      if debugging $self;

   my $has_change_ids;

   for my $r ( $revs->get ) {
      $has_change_ids ||= ! empty $r->change_id;

      ## the undef is so the sort keys can be filled in later
      ## without needing to increase the memory size.
      my $sort_rec = [ $r, undef ];
      push @sort_recs, $sort_rec;

      if ( $r->previous ) {
         push @{$rev_kids{int $r->previous}}, $sort_rec;
      }
      else {
         push @roots, $sort_rec;
      }
   }

   $self->{DEST_DEFAULT_COMMENT} = "";
   debug "generating index" if debugging $self;
   my @spec = @{$self->{DEST_SORT_SPEC}};
   shift @spec if @spec && $spec[0] eq "presort";

   VCP::Rev::preindex();

   $self->_calc_sort_recs( \@sort_recs, \@spec );

   $self->{DEST_DEFAULT_COMMENT} = undef;

   warn "vcp: aggregating changes.\n";
   my @result;
   @roots = sort { $a->[1] cmp $b->[1] } @roots;

   my $change_number = 0;

   while ( @roots ) {
      ++$change_number;
      my @change;
      my @kids;

      ## Extract one change and then add in all children of the
      ## extracted revisions.
      do {
         my ( $r, undef ) = @{shift @roots};  ## discard sort key
         push @change, $r;
         my $kids = delete $rev_kids{int $r};
         push @kids, @$kids if $kids;
      } while ( @roots
         && ( $has_change_ids
            ? $change[0]->change_id eq $roots[0]->[0]->change_id
            : _in_same_change $change[0], $roots[0]->[0]
         )
      );

      debug "...change $change_number: " . @change . " revs"
         if debugging $self;

      if ( $self->add_in_change_numbers && ! $has_change_ids ) {
         $_->change_id( $change_number ) for @change;
      }

      push @result, @change;

      if ( @kids ) {
         ## This is the slow but guaranteed perfect way to sort:
         #@roots = sort { $a->[1] cmp $b->[1] } @roots, @kids;
         #next;

         ## This is the faster but more comples production sorting.
         ## It's a merge sort with some common cases short circuited
         ## out.
         @kids = sort { $a->[1] cmp $b->[1] } @kids
            if @kids > 1;

         if ( @roots ) {
            if ( $kids[0]->[1] ge $roots[-1]->[1] ) {
               push @roots, @kids;
            }
            elsif ( $kids[-1]->[1] le $roots[0]->[1] ) {
               unshift @roots, @kids;
            }
            else {
               my @result;

               ## 5 is just a guess.
               if ( @roots > 5 ) {
                  ## Find the first root that is greater than the first
                  ## kid and splice all preceding roots out.
                  my $i = 0;
                  my $k = $kids[0]->[1];
                  ++$i while $i <= $#roots && $k ge $roots[$i]->[1];
                  @result = splice @roots, 0, $i;
               }

               ## This is the slowest bit.
               while ( @roots && @kids ) {
                  my $w = $roots[0]->[1] cmp $kids[0]->[1];
                  if    ( $w < 0 ) { push @result, shift @roots }
                  elsif ( $w > 0 ) { push @result, shift @kids  }
                  else             { push @result, shift @roots, shift @kids  }
               }

               @roots = ( @result, @roots, @kids );
            }
         }
         else {
            @roots = @kids;
         }
      }
   }

   warn "vcp: ", $change_number, " changes found",
      $change_number
         ? sprintf " (%.2f mean revs/change)", $revs->get / $change_number
         : (),
      "\n";

   $revs->set( @result );
}


sub full_sort_revs {

   my VCP::Dest $self = shift ;

   my ( $revs ) = @_ ;

   VCP::Rev::preindex();

   my @spec = @{$self->{DEST_SORT_SPEC}};

   if ( substr( $spec[0], 0, 7 ) eq "presort" ) {
      my @prespec = ( shift @spec ) =~ m/presort\((?:\s*(\w+)[,)])*\)/;
      @prespec = qw( change_id rev_id time ) unless @prespec;

      my $presorted = $self->_presort_revs( $revs, \@prespec );

      $revs->set( $self->_merge_presorted_revs( $presorted, \@spec ) );
      debug "done merge" if debugging ;

      return;
   }

   debug "generating index" if debugging ;
   my $sort_recs = [ map [ $_ ], $revs->get ];
   $self->_calc_sort_recs( $sort_recs, \@spec );

   $self->_remove_sporadics( $sort_recs, \@spec );

   debug "sorting revisions" if debugging ;
   $revs->set( map $_->[0], sort { $a->[1] cmp $b->[1] } @$sort_recs ) ;
}

#=item is_in_dest
#
#    $dest->is_in_dest( $filebranch_id, $rev_id );
#
#Checks to see if the indicated revision is in the destination already
#by checking the head_revs database.  Returns 0 if no state_location
#is defined.
#
#=cut
#
#my $warned_is_in_dest;
#
#sub is_in_dest {
#   my VCP::Dest $self = shift;
#   my ( $rev ) = @_;
#
#   return 0 unless defined $self->{DEST_HEAD_REVS};
#
#   my ( $hr ) = $self->head_revs->get( $rev->source_filebranch_id );
#   return $hr && VCP::Rev->cmp_id( $rev->rev_id, $hr ) <= 0;
#}
#

=item last_rev_in_filebranch

   my $rev_id = $dest->last_rev_in_filebranch(
      $source_repo_id,
      $source_filebranch_id
   );

Returns the last revision for the file and branch indicated by
$source_filebranch_id.  This is used to support --continue.

Returns undef if not found.

=cut

sub last_rev_in_filebranch {
   my VCP::Dest $self = shift;
   return 0 unless defined $self->{DEST_HEAD_REVS};
   return ($self->head_revs->get( \@_ ))[0];
}

=item metadata_only

This returns false by default, but the experimental branch_diagram
destination requires only metadata.  A source should look at this
before going to the effort of checking out each file.

=cut

sub metadata_only { 0 }

=back


=head1 NOTES

Several fields are jury rigged for "base revisions": these are fake
revisions used to start off incremental, non-bootstrap transfers with
the MD5 digest of the version that must be the last version in the
target repository.  Since these are "faked", they don't contain
comments or timestamps, so the comment and timestamp fields are treated as
"" and 0 by the sort routines.

There is a special sortkey C<avg_comment_time> that allows revisions within
the same time period (second, minute, day) to be sorted according to the
average time of the comment for the revision (across all revisions with
that comment).  This causes changes that span more than one time period
to still be grouped properly.

=cut

=head1 COPYRIGHT

Copyright 2000, Perforce Software, Inc.  All Rights Reserved.

This module and the VCP package are licensed according to the terms given in
the file LICENSE accompanying this distribution, a copy of which is included in
L<vcp>.

=head1 AUTHOR

Barrie Slaymaker <barries@slaysys.com>

=cut

1