File Coverage

=head1 NAME

App::FileSync::Delta - rsync-style block deltas in pure Perl

=head1 SYNOPSIS

        my $signature = App::FileSync::Delta::signature($old_path);
        App::FileSync::Delta::diff($new_path, $signature, $spool);
        seek $spool, 0, 0;
        App::FileSync::Delta::apply($old_path, $spool, $out);

=head1 FUNCTIONS

=head2 block_size

Purpose: the block length for a file of a given size.

Args: C<$size> in bytes.

Returns: C<$BLOCK> (16 KiB) for files up to C<$BLOCK * $MAX_BLOCKS>; above that,
a larger whole-KiB block so the signature stays at most about C<$MAX_BLOCKS>
records.

Side Effects: none.

Usage:

        my $block = App::FileSync::Delta::block_size(-s $path);

=head3 EXAMPLE

        print App::FileSync::Delta::block_size(1_000_000), "\n";      # 16384

=head3 API SPECIFICATION

=head4 INPUT

        [ { name => 'size', type => 'integer', min => 0, optional => 1 } ]

=head4 OUTPUT

        { type => 'integer', min => 1024 }

=head3 MESSAGES

None.

=head3 FORMAL SPECIFICATION

        block_size(s) = BLOCK                                   if s ≤ BLOCK × MAX_BLOCKS
                      = (⌈⌈s / MAX_BLOCKS⌉ / 1024⌉ + 1) × 1024    otherwise

=cut

=head2 signature

Purpose: describe a file the receiver already holds.

Args: C<$path>, optional C<$block> length (default L</block_size>).

Returns: C<{ size, blocklen, blocks =E<gt> [ [ weak, strong ], ... ] }>, one pair
per full block (a short final block is not included; its bytes are simply never
reused), or C<undef> for a missing file or one smaller than C<$MIN_SIZE>.

Side Effects: reads the file.

Usage:

        my $signature = App::FileSync::Delta::signature($abs) or return 0;

=head3 EXAMPLE

        my $sig = App::FileSync::Delta::signature('/tmp/big.iso');
        printf "%d blocks of %d bytes\n", scalar @{ $sig->{blocks} }, $sig->{blocklen} if $sig;

=head3 API SPECIFICATION

=head4 INPUT

        [
                { name => 'path',  type => 'string', optional => 1 },
                { name => 'block', type => 'integer', min => 1, optional => 1 },
        ]

=head4 OUTPUT

        { type => 'hashref', optional => 1 }

=head3 MESSAGES

        Key        Meaning                    Resolution
        io.read    the file cannot be read    check permissions

=head3 FORMAL SPECIFICATION

        signature(p, b) = ⊥                                    if p ∉ dom FS ∨ #FS(p) < MIN_SIZE
                        = ⟨size ↦ #F, blocklen ↦ b,
                           blocks ↦ ⟨(weak(F[i]), sha256(F[i])) | i ∈ 0 .. ⌊#F / b⌋ − 1⟩⟩
                          where F = FS(p), F[i] = bytes i×b .. (i+1)×b − 1

=cut

=head2 encode_signature

Documented with L</decode_signature> below.

=head2 decode_signature

Purpose: put a signature's blocks on the wire and take them off again.

Args: C<encode_signature($signature)>; C<decode_signature($bytes, $count)>.

Returns: the encoded bytes (36 per block: a big-endian weak sum then the
32-byte SHA-256); the decoded arrayref of C<[ weak, strong ]> pairs.

Side Effects: none.

Usage:

        my $bytes = App::FileSync::Delta::encode_signature($signature);
        my $blocks = App::FileSync::Delta::decode_signature($bytes, $count);

=head3 EXAMPLE

        my $blocks = App::FileSync::Delta::decode_signature(
                App::FileSync::Delta::encode_signature($sig), scalar @{ $sig->{blocks} });

=head3 API SPECIFICATION

=head4 INPUT

        [
                { name => 'bytes', type => 'string', optional => 1 },
                { name => 'count', type => 'integer', min => 0, optional => 1 },
        ]

=head4 OUTPUT

        { type => 'arrayref' }

=head3 MESSAGES

        Key               Meaning                              Resolution
        delta.bad_count   the block count is not a number      a peer bug; resync with --no-delta
        delta.bad_length  the bytes do not match the count     a peer bug; resync with --no-delta

=head3 FORMAL SPECIFICATION

        encode(⟨(w₁,s₁), …, (wâ‚™,sâ‚™)⟩) = be32(w₁) ⁀ s₁ ⁀ … ⁀ be32(wâ‚™) ⁀ sâ‚™
        decode(encode(bs), #bs) = bs
        pre decode: #bytes = 36 × count

=cut

=head2 diff

Purpose: write the delta that turns the receiver's file into C<$path>.

Args: C<$path> (the new content), C<$signature> (of what the receiver has;
C<blocklen> and C<blocks> are used), C<$out> (a writable handle).

Returns: C<{ literal, copy, ops }>: bytes sent literally, bytes copied, and
records written, so the caller can decide whether the delta beats the file.

Side Effects: reads C<$path>; writes copy and literal records to C<$out>.

Usage:

        my $stats = App::FileSync::Delta::diff($abs, $signature, $spool);

=head3 EXAMPLE

        open my $spool, '+>', undef;
        my $stats = App::FileSync::Delta::diff('/tmp/new.bin', $sig, $spool);
        printf "%d literal bytes in %d records\n", $stats->{literal}, $stats->{ops};

=head3 API SPECIFICATION

=head4 INPUT

        [
                { name => 'path',      type => 'string', min => 1 },
                { name => 'signature', type => 'hashref' },
                { name => 'out',       type => 'handle' },
        ]

=head4 OUTPUT

        {
                type => 'hashref',
                schema => {
                        literal => { type => 'integer', min => 0 },
                        copy    => { type => 'integer', min => 0 },
                        ops     => { type => 'integer', min => 0 },
                },
        }

=head3 MESSAGES

        Key                  Meaning                              Resolution
        delta.no_output      no output handle                     a caller bug
        delta.no_block       the signature has no block length    a peer bug
        delta.write          the delta cannot be written          check space for the spool
        io.read              the new file cannot be read          check permissions

=head3 FORMAL SPECIFICATION

        let R = records written to out
        apply(old, R) = FS(path)                (correctness)
        literal = Σ { #l | L(l) ∈ R } ; copy = Σ { n | C(o, n) ∈ R } ; ops = #R
        literal + copy = #FS(path)

=head3 PSEUDOCODE

        index the receiver's blocks by weak checksum
        while the next full block equals the receiver's block at the same index:
                emit a copy of it (no rolling needed for an unchanged prefix)
        read up to SCAN_LIMIT more bytes into a window buffer
        slide a one-block window through the buffer:
                if its weak sum is indexed and the strong hash matches a block:
                        emit a copy, jump a whole block
                else: add one byte to the literal run, roll the sums forward one byte
        flush the rest of the buffer and the unscanned tail as literals

=cut

=head2 write_copy

Documented with L</write_literal> below.

=head2 write_literal

Purpose: write one delta record.

Args: C<write_copy($out, $offset, $length)>; C<write_literal($out, $bytes)>
(an empty literal writes nothing).

Returns: 1.

Side Effects: writes to C<$out>.

Usage:

        App::FileSync::Delta::write_copy($spool, $offset, $length);
        App::FileSync::Delta::write_literal($spool, $bytes);

=head3 EXAMPLE

        App::FileSync::Delta::write_literal($out, "new text\n");

=head3 API SPECIFICATION

=head4 INPUT

        [
                { name => 'out',    type => 'handle' },
                { name => 'offset', type => 'integer', min => 0 },
                { name => 'length', type => 'integer', min => 0 },
        ]

=head4 OUTPUT

        { type => 'integer', min => 1, max => 1 }

=head3 MESSAGES

        Key           Meaning                      Resolution
        delta.write   the record cannot be written  check space for the spool

=head3 FORMAL SPECIFICATION

        write_copy(o, n): out' = out ⁀ "C" ⁀ be32(o) ⁀ be32(n)
        write_literal(b): out' = out ⁀ "L" ⁀ be32(#b) ⁀ b    if b ≠ ⟨⟩

=cut

=head2 read_op

Purpose: read the next delta record.

Args: C<$in>, a handle positioned at a record.

Returns: C<('copy', $offset, $length)>, C<('literal', $bytes)>, or the empty
list at the end.  A list because callers loop with
C<while (my ($type, @rest) = read_op($in))>.

Side Effects: advances C<$in>.

Usage:

        while (my ($type, @rest) = App::FileSync::Delta::read_op($spool)) { ... }

=head3 EXAMPLE

        my ($type, $offset, $length) = App::FileSync::Delta::read_op($spool);

=head3 API SPECIFICATION

=head4 INPUT

        [ { name => 'in', type => 'handle' } ]

=head4 OUTPUT

        { type => 'arrayref' }

=head3 MESSAGES

        Key                 Meaning                         Resolution
        delta.read          the delta cannot be read        check the spool
        delta.bad_record    an unknown record type          a peer bug; resync with --no-delta
        io.short            the delta ends mid-record       a peer bug; resync with --no-delta

=head3 FORMAL SPECIFICATION

        read_op("C" ⁀ be32(o) ⁀ be32(n) ⁀ rest) = (copy, o, n)
        read_op("L" ⁀ be32(k) ⁀ b ⁀ rest) = (literal, b)    where #b = k
        read_op(⟨⟩) = ⟨⟩

=cut

=head2 apply

Purpose: rebuild a file from the old copy and a spooled delta.

Args: C<$old_path>, C<$in> (the delta), C<$out> (where the new content goes).

Returns: C<{ size }>, the bytes written.

Side Effects: reads C<$old_path> and C<$in>; writes C<$out>.

Usage:

        my $result = App::FileSync::Delta::apply($old, $spool, $out);

=head3 EXAMPLE

        open my $out, '>', '/tmp/rebuilt.bin';
        App::FileSync::Delta::apply('/tmp/old.bin', $spool, $out);

=head3 API SPECIFICATION

=head4 INPUT

        [
                { name => 'old_path', type => 'string', min => 1 },
                { name => 'in',       type => 'handle' },
                { name => 'out',      type => 'handle' },
        ]

=head4 OUTPUT

        { type => 'hashref', schema => { size => { type => 'integer', min => 0 } } }

=head3 MESSAGES

        Key                   Meaning                            Resolution
        io.read               the old file cannot be read        check permissions
        io.seek               a copy points outside the file     the delta does not fit this file
        delta.write_restored  the output cannot be written       check space

=head3 FORMAL SPECIFICATION

        apply(old, R) = ⁀/ ⟨ bytes(r) | r ← R ⟩
          where bytes(C(o, n)) = FS(old)[o .. o + n − 1], bytes(L(b)) = b

=cut

=head2 read_exact

Purpose: read exactly C<$length> bytes.

Args: C<$fh>, C<$length>, C<$what> (named in errors).

Returns: the bytes.

Side Effects: advances C<$fh>.

Usage:

        my $data = App::FileSync::Delta::read_exact($fh, $block, $path);

=head3 EXAMPLE

        my $header = App::FileSync::Delta::read_exact($spool, 8, 'delta');

=head3 API SPECIFICATION

=head4 INPUT

        [
                { name => 'fh',     type => 'handle' },
                { name => 'length', type => 'integer', min => 0 },
                { name => 'what',   type => 'string' },
        ]

=head4 OUTPUT

        { type => 'string' }

=head3 MESSAGES

        Key        Meaning                         Resolution
        io.read    the read failed                 check the device
        io.short   fewer bytes than required       the file was truncated

=head3 FORMAL SPECIFICATION

        read_exact(fh, n, w) = take(n, rest(fh))   if #rest(fh) ≥ n
                             â†‘ io.short           otherwise

=cut