Simplistic reconciliation of mostly-append text files like Offpunk lists: draft involving Kahn’s algorithm

I have been thinking about managing my Offpunk list files that I might be modifying on either, or both, my netbook and some main laptop. Since this is mostly about new parts that might have gotten added, I didn’t want to introduce some full-blown version control to this. Instead, I figured that I could start ensuring the files end with a time-specific marker when was the file last appended before sync that would also be useful to the human…

#!/bin/sh

set -eu

string='> --- Last appended: '
for f; do
  last_line="`tail -n1 "$f"`"
  case "$last_line" in
    "$string"*) ;;
    *)
      mtime=`stat -c %Y "$f" || stat -f %m "$f"`
      printf "\n%s\n" "$string`date -d@$mtime`" >> "$f"
      ;;
  esac
done

…and then write a program that would ensure all such blocks (indicated by being followed by such a marker) are present in both versions of reconciled file (in both directions) — which would then allow me to diff the files equivalently to diffing the blocks, and maybe add merge conflict indicators in case of any changes in the particular same block.

So far I have drafted the code below for a reconciliation script, but I have not executed that script even once so far. That’s it, that’s the post. The code is a bit of an overkill, uses Kahn’s algorithm to ensure sorting of the result most adherent to original orders.

#!/usr/bin/perl
use Tie::File;
use warnings;
use strict;
use Fcntl qw(O_WRONLY O_CREAT O_APPEND);
use Tie::IxHash;
use List::MoreUtils qw(uniq);

my $marker = qr/^> --- Last appended: /;

# $rec is filename with .reconcile, $base is without
my $rec = shift @ARGV;
my $base = $rec; $base =~ s/\.reconcile$//;

# instances of Tie::File for both files
tie my @base, 'Tie::File', $base or die $!;
tie my @rec,  'Tie::File', $rec  or die $!;

# Get marker line indices; for position → marker line lookup
my @base_markers = grep { $base[$_] =~ $marker } 0..$#base;
my @rec_markers  = grep { $rec[$_] =~ $marker }  0..$#rec;

# Map: full marker line → its line index in file
tie my %base_has, 'Tie::IxHash';
@base_has{ map { $base[$_] } @base_markers } = @base_markers;
tie my %rec_has, 'Tie::IxHash';
@rec_has{ map { $rec[$_] } @rec_markers } = @rec_markers;

# Kahn's algorithm - topological merge preserving both orders

my %predecessors;
my %base_previous;
my %successors;
my $previous;
for my $i (keys %base_has) {
    $predecessors{$i} //= [];
    push @{$predecessors{$i}}, $previous if (defined $previous);
    $successors{$i} //= [];
    push @{$successors{$previous}}, $i if (defined $previous);
    $base_previous{$i} = defined $previous ? $previous : 0;
    $previous = $i;    
}
undef $previous;
my %rec_previous;
for my $i (keys %rec_has) {
    $predecessors{$i} //= [];
    push @{$predecessors{$i}}, $previous if (defined $previous);
    $successors{$i} //= [];
    push @{$successors{$previous}}, $i if (defined $previous);
    $rec_previous{$i} = defined $previous ? $previous : 0;
    $previous = $i;
}


my @result;
# from uniq list of keys, filter those with no incoming edges for queue
my @queue = grep { $#{$predecessors{$_}} == 0 } 
            uniq((keys %base_has), (keys %rec_has));

while(@queue) {
    my $curr = shift @queue;
    push @result, $curr;

    for my $i (@{$successors{$curr}}) {
        $predecessors{$i} =
            [grep {$_ ne $curr} @{$predecessors{$i}}];
        push @queue, $i if $#{$predecessors{$i}} == 0;
    }
}

tie my @result_base, 'Tie::File', "$base~",
    mode => O_WRONLY | O_CREAT
or die $!;
tie my @result_rec, 'Tie::File', "$rec~",
    mode => O_WRONLY | O_CREAT
or die $!;

sub get_block_indices_for_insert_from_this {
    my ($item, $previous, $has) = $_;
    my $block_start = $previous->{$item} == 0 ? 0
        : $has->{$previous->{$item}} + 1;
    my $block_end = $has->{$previous->{$item}};
    return [$block_start .. $block_end];
}

sub get_block_for_insert {
    my (
        $item,
        $target_previous,
        $target_has,
        $target_source,
        $other_previous,
        $other_has,
        $other_source
    ) = @_;
    my $which = exists $target_has->{$item};
    return [map {
        my $source = $which ? $target_source : $other_source;
        $source->[$_];
    } (get_block_indices_for_insert_from_this $item,
        $which ? $target_previous : $other_previous,
        $which ? $target_has : $other_has)]
}

for my $item (@result) {
    push @result_base, [get_block_for_insert $item,
        \%base_previous, \%base_has, \@base,
        \%rec_previous, \%rec_has, \@rec];
    push @result_rec, [get_block_for_insert $item,
        \%rec_previous, \%rec_has, \@rec,
        \%base_previous, \%base_has, \@base];
}

untie @result_base;
untie @result_rec;

Note to mostly self: code pasting courtesy of sed 's/&/\&amp;/g; s/</\&lt;/g; s/>/\&gt;/g; s/"/\&quot;/g; s/'"'"'/\&#39;/g'