view release on metacpan or  search on metacpan

lib/Code/DRY.pm  view on Meta::CPAN

    }

    find_duplicates_in( $minlength, $ignoreContentFilter, @filepaths );
}

sub __get_text {
    my $file     = shift;
    my $contents = '';
    my @lineoffsets;
    open my $infile, '<', $file or die "cannot open file $file: $!\n";
    while (<$infile>) {
        $contents .= $_;
        push @lineoffsets, length($contents) - 1;
    }
    return ( $contents, @lineoffsets );
}

1;
__END__

=encoding Latin-1

=head1 NAME

Code::DRY - Cut-and-Paste-Detector for Perl code 

=head1 SYNOPSIS

  use Code::DRY;

  # high level usage: scan some directories for Perl code
  # and let the module report duplicates sorted
  # by length of duplicates. Minimum length are 4 lines, 
  # and all filters are set to undef.
  #
  Code::DRY::scan_directories(4, undef, undef, undef, @dirs);

  or

  # mid level usage: let the function report duplicates
  # from a list of files. The ignore filter is set to undef.
  # This time the minimum length is set to 40 bytes.
  Code::DRY::find_duplicates_in(-40, undef, @files);

  or

  # low level usage: analyse the raw data yourself
  # built the suffix and lcp array
  Code::DRY::build_suffixarray_and_lcp($longstringwithcode);
  # avoid matches crossing file boundaries
  Code::DRY::clip_lcp_to_fileboundaries(\@Code::DRY::fileoffsets);
  # avoid matches overlapping into each other
  Code::DRY::reduce_lcp_to_nonoverlapping_lengths();
  # avoid matches that are included in longer matches
  Code::DRY::set_lcp_to_zero_for_shadowed_substrings();
  # then iterate through the lcp array via get_len_at(index)
  # and through the suffix/offset array via get_offset_at(index)

=head1 DESCRIPTION

The module's main purpose is to report repeated text fragments (typically Perl code)
that could be considered for isolation and/or abstraction in order to
reduce multiple copies of the same code (aka cut and paste code).

Code duplicates may occur in the same line, file or directory.

The ad hoc approach to compare every item against every other item
leads to computing times growing exponentially with the amount of code,
which is not useful for anything but the smallest code bases.

So a efficient data structure is needed. 

This module can create the suffix array and the longest common prefix array
for a string of 8-bit characters. These data structures can be used to
search for repetitions of substrings in O(n) time.

The current strategy is to concatenate code from all files into one
string and then use the suffix array and its companion,
the longest-common-prefix (lcp) array on this string.


=head3 Example:

Instead of real Perl code I use the string 'mississippi' for simplicity.
A B<suffix> is a partial string of an input string, which ends at the end of the input string.
A B<prefix> is a partial string of an input string, which starts at the start of the input string.
The B<suffix array> of a string is a list of offsets (each one for a suffix),
which is sorted lexicographically by suffix:

    #  offset suffix
    ================
    0  10:    i
    1   7:    ippi
    2   4:    issippi
    3   1:    ississippi
    4   0:    mississippi
    5   9:    pi
    6   8:    ppi
    7   6:    sippi
    8   3:    sissippi
    9   5:    ssippi
    10  2:    ssissippi

The other structure needed is the B<longest common prefix array> (lcp).
It contains the maximal length of the prefixes for this entry shared with the previous 
entry from the suffix array. For this example it looks like this:


    #  offset lcp  (common prefixes shown in ())
    =====================
    0  10:    0    ()
    1   7:    1    (i)
    2   4:    1    (i)
    3   1:    4    (issi) overlap!
    3         3    (iss)  corrected non overlapping prefixes
    4   0:    0    ()
    5   9:    0    ()
    6   8:    1    (p)
    7   6:    0    ()
    8   3:    2    (si)
    9   5:    1    (s)

lib/Code/DRY.pm  view on Meta::CPAN

This is a core module now for a while.

=back

=head2 OPTIONAL MODULES

=over

=item * L<Test::More>

Required if you want to run Code::DRY's own tests.

=item * L<Test::Output>

Optional if you want to run Code::DRY's own tests.

=back


=head1 SUBROUTINES


=head2 C<scan_directories($minlength, $ignoreContent, $regexAccept, $regexIgnore, @array_of_pathnames_of_directories)>

Scans the given directories in C<@array_of_pathnames_of_directories> recursively for file names 
matching the regexp C<$regexAccept>, if it is defined.
If those file names also do B<not> match against the regexp C<$regexIgnore> 
(unless C<$regexIgnore> is undefined) they are included in the analysis.

If C<$regexAccept> and C<$regexIgnore> both are C<undef>, all file names will be considered for analysis.

If either of C<$regexAccept> and C<$regexIgnore> is not a ref of type 'Regexp', 
it is expected to be a pattern string that will be converted into a regexp with C<qr{}xms>.

The parameter C<$ignoreContent> can be used to avoid duplication reports for content matching this regex.
If C<$ignoreContent> is not a ref of type 'Regexp', it is expected to be a pattern string that 
will be converted into a regexp with C<qr{}xms>.

The parameter C<$minlength> is interpreted in units of lines when being positive.
Otherwise its absolute value is interpreted in units of bytes.

All repetitions with a minimum length of C<$minlength> will be reported by the C<report> callback function.


=head2 C<find_duplicates_in($minlength, $ignoreContent, @array_of_pathnames_of_files)>

Reads files for the given file names composing a long string, which is then analysed for repetitions.

The parameter C<$minlength> is interpreted in units of lines when being positive.
Otherwise its absolute value is interpreted in units of bytes.

The parameter C<$ignoreContent> can be used to avoid duplication reports for content matching this regex.
If C<$ignoreContent> is not a ref of type 'Regexp', it is expected to be a pattern string that 
will be converted into a regexp with C<qr{}xms>.

All repetitions with a minimum length of C<$minlength> will be reported by the C<report> callback function.


=head2 C<set_reporter(sub{ CODE BLOCK })>

Set custom code to report duplicates of a code fragment. The callback is invoked with 
position information for the copies found during analysis.

The supplied code has to accept two scalars and an array reference. 

The first parameter is the required minimum length of duplicates to be reported.

The second parameter contains a string describing the units for minimum length ('lines' or 'bytes').

The referenced array (third parameter) contains one entry with an anonymous array reference for each copy found.
Copies are reported in the order of the processing of the files and then in the order of positions.
Each copy is represented by this position information as an array entry:

=over

=item 1. filename

=item 2. line number at start of copy (starting with 1). This is the line number of the first line completely contained in the copy.

=item 3. line number at end of copy. This is the line number of the last line completely contained in the copy.

=item 4. offset from start of file at start of copy (starting with 0) clipped to the next completely contained line.

=item 5. offset from start of file at end of copy clipped to the last completely contained line.

=item 6. offset from start of file at start of copy (starting with 0) (used in 'bytes' mode)

=item 7. offset from start of file at end of copy (used in 'bytes' mode)

=back


The default reporter is like this:

    XXX insert code when stable


=head2 C<set_default_reporter>

Resets the reporter callback function to the default shown above.


=head2 C<report_dupes($minlength, $copies, $length, $index_in_suffix_and_lcp_array)>

This function builds a data structure with position information for the duplication copies 
described by the input parameters. The entries in the suffix array from 
C<$index_in_suffix_and_lcp_array> to C<$index_in_suffix_and_lcp_array + $copies -1>
will give the offsets in the string where the copies start. Each has a length of 
C<$length> characters. With these values file names and line numbers are retrieved and 
stored in the structure.
Then the reporter callback function is called with the minimum length of this scan C<$minlength> and this structure.
See also function L<set_reporter()>.


=head2 C<enter_files($ref_to_array_of_pathnames_of_files)>

Reads the files given by the pathnames. Any files with length zero are skipped (and removed from the filename array).
Offset arrays for file and line end positions are built.
The content of all files is concatenated. Currently the content must not be valid Perl (but this
might change when parsing gets involved in a future release).