#!/usr/bin/perl -w

$intentionmode = 1;
$backoutmode = 2;

$mode = 1;
%accounts = ();
%tentative_accounts = ();
%last_db = ();
$last_entry = "";

%winners = ();
%active  = ();
%active_accts = ();

sub find {
    my ($item, @array) = @_;
    my $i;
    for($i=0; $i<scalar(@array); $i++) {
	if ($item eq $array[$i]) {
	    return $i;
	}
    }
    return -1;
}
sub commit_transaction {
    my ($tid) = @_;
    %last_db = %accounts;

    @commands = @{ $active{$tid} };
    foreach $command (@commands) {
	my @one_cmd = @{ $command };
	&do_command(0, @one_cmd);
    }
}
sub add_command {
    # adds a command to a command list
    my ($tid, $type, $anum, $value, $oldvalue, $list_ref) = @_;
    
    if (!  ${ %{$list_ref}} {$tid} )  {
           ${ %{$list_ref}} {$tid} = [];
    }
    push @{ ${%{$list_ref}} {$tid}}, [$tid, $type, $anum, $value, $oldvalue];
}
sub do_tentative_command {
# place command into tentative state, but dont make it visible yet
# if the command is a commit, then commit the entire transaction and make it visible.
    my ($tid, $type, $anum, $value) = @_;
    my $oldval;
    if ($accounts{$anum}) {
	$oldval = $accounts{$anum};
    } else {
	$oldval = 0;
    }

    &add_command($tid, $type, $anum, $value, $oldval, \%active);
    
    if ($type eq "init") {
        print "  Tentatively initializing account $anum to $value\n";
	$active_accts{$anum} = $tid;
	$tentative_accounts{$anum} = $value;
    } elsif ($type eq "write") {
	print "  Tentatively writing $value to account number $anum\n";
	$active_accts{$anum} = $tid;
	$tentative_accounts{$anum} = $value;
    } elsif ($type eq "begin") {

    } 
    
    if ($type eq "commit") {
	my %t = reverse %active_accts;
	if ($t{$tid} && $active_accts{$t{$tid}}) {delete $active_accts{$t{$tid}};}
        &commit_transaction($tid);
    }
}

sub print_db { foreach $k (sort keys(%accounts)) {print "  Account $k = $accounts{$k}\n"; }}
sub print_tid {
    my($label, $items_ref) = @_;
    my $s;
    foreach $s (sort keys %{$items_ref}) { print "$label: $s\n";}
}

sub write_cp {
    my ($dbnum) = @_;
    if ($dbnum == -1) {

	open(DB, ">DB") or die "could not write DB\n";
	if ($mode eq $intentionmode) {
	    foreach $k (sort keys (%last_db)) { 
		print DB "$k $last_db{$k}\n";
	    }
	} else {
	    foreach $k (sort keys (%last_db)) { 
		print DB "$k $tentative_accounts{$k}\n";
	    }
	}
	close(DB);
	return;

    } else {
	my $k;
	print LOG "CHECKPOINT";
	foreach $k (keys %active) {
	    print LOG " $k";
	}
	print LOG "\n";
    }
}
sub read_cp {
    my ($dbnum) = @_;
    if ($dbnum == -1) {
	open(DB, "DB") or return;
	print "  Reading DB\n";
    } else {
	open(DB, "CP$dbnum") or die "could not open CP$dbnum\n";
	print "  Reading CP$dbnum\n";
    }

    while (<DB>) {
	/(\S+) (\d+)/;
	$accounts{$1} = $2;
    }
    %tentative_accounts = %accounts;
    close(DB);
}
sub find_uncommitted_tid {
    my (@command_refs) = @_;
    my (@command, @begun, @committed);
    my ($i, $completed, $command_ref);
    my %returnlist = ();

    foreach $command_ref (@command_refs) {
	@command = @{$command_ref};
	if ($command[1] eq "begin") {
	    push @begun, $command[0];
	} elsif ($command[1] eq "commit") {
	    push @committed, $command[0];
	}
    }
    
    foreach $started (@begun) {
	$completed = 0;
	foreach $x (@committed) {
	    if ($x eq $started) {$completed = 1;}
	}
	if (!$completed) {$returnlist{$started} = 1;}
    }
    return \%returnlist;
}
sub find_intention_losers {
    my ($uncommitted_ref, $after_ref) = @_;
    my %h = %{$uncommitted_ref};

    foreach $command_ref (@{$after_ref}) {
	@command = @{$command_ref};
	if ($command[1] eq "commit" && $h{$command[0]} ) { 
	    delete $h{$command[0]};
	}
    }
    return %h;
}
sub find_intention_winners {
    my ($uncommitted_ref, @after) = @_;
    my %h = ();
    foreach $command_ref (@after) {

	@command = @{$command_ref};
	if ($command[1] eq "commit" && ${%{$uncommitted_ref}}{$command[0]} ) { 
	     $h{$command[0]} = 1;
	}
    }
    return \%h;
}

sub find_uncommitted_after_tid {
    my ($before_refs, $after_refs) = @_;
    my (@committed, %h);

    foreach $command_ref (@{$after_refs}, @{$before_refs}) {
	@command = @{$command_ref};
	if ($command[1] eq "commit") { $committed{$command[0]} = 1; }
    }
    foreach $command_ref (@{$before_refs}) {
	@command = @{$command_ref};
	if ($command[1] eq "begin" && !$committed{$command[0]}) {
	    $h{$command[0]} = 1;
	}
    }
    return \%h;
}
sub find_committed_tid {
    my (@command_refs) = @_;
    my (@begun, @committed, @command);
    my ($i, $completed, $command_ref);
    my %returnlist = ();

    foreach $command_ref (@command_refs) {
	@command = @{$command_ref};
	if ($command[1] eq "begin") {
	    push @begun, $command[0];
	} elsif ($command[1] eq "commit") {
	    push @committed, $command[0];
	}
    }
    
    foreach $started (@begun) {
	$completed = 0;
	foreach $x (@committed) {
	    if ($x eq $started) {$completed = 1;}
	}
	if ($completed) {$returnlist{$started} = 1;}
    }
    return \%returnlist;
}

sub find_committed_after_tid {
    my ($before_refs, $after_refs) = @_;
    my (@begun, @committed, @command);
    my ($i, $completed, $command_ref);
    my %returnlist = ();

    foreach $command_ref (@{$before_refs}) {
	@command = @{$command_ref};
	if ($command[1] eq "begin") {
	    push @begun, $command[0];
	} 
    }
    foreach $command_ref (@{$after_refs}) {
	@command = @{$command_ref};
	if ($command[1] eq "commit") {
	    push @committed, $command[0];
	}
    }

    foreach $started (@begun) {
	$completed = 0;
	foreach $x (@committed) {
	    if ($x eq $started) {$completed = 1;}
	}
	if ($completed) {$returnlist{$started} = 1;}
    }
    return \%returnlist;
}

sub check_command {
    my ($tid, $type, $anum, $value, $oldvalue) = @_;    
    #begin : ensure that tid does not already exist
    #init  : ensure that account does not already exist
    #        ensure that tid exists
    #write : ensure that account exists
    #        ensure that tid exists
    #commit: ensure that tid exists
    my %temp;
    if ($mode eq $intentionmode) {
	%temp = %tentative_accounts;
    } else {
	%temp = %accounts;
    }

    if ($tid < 1) {
	print "invalid: TID must be greater than 0 "; return 0; 
    }
    if ($type eq "begin") {
	if ($active{$tid}) { print "invalid: TID $tid already started "; return 0; }
	if ($winners{$tid}) { print "invalid: TID $tid already used "; return 0; }

    } 
    if ($type eq "write") {
	if (!$temp{$anum}) {print "invalid: Account $anum not initialized "; return 0; }
    }
    if ($type eq "init") {
	if ($temp{$anum}) {print "invalid: Account $anum already initialized "; return 0; }
    }
    if ($type eq "init" or $type eq "write") {
	if (!$active{$tid}) { print "invalid: TID $tid not started "; return 0;}
	if ($active_accts{$anum} && $active_accts{$anum} ne $tid) {
	    print "invalid: Account $anum is already in use by TID $active_accts{$anum} "; 
	    return 0;
	}
    }
    if ($type eq "commit") {
	if ($winners{$tid}) { print "invalid: TID $tid already committed "; return 0; }
	if (!$active{$tid}) { print "invalid: TID $tid not been started yet "; return 0; }
	
    } 

    return 1;
}
sub do_command {
# Take a command and apply it to the database

    my ($recovery, $tid, $type, $anum, $value, $oldvalue) = @_;

    if ($mode eq $backoutmode) {
	&add_command($tid, $type, $anum, $value, $oldvalue, \%active);
    }	

    if ($type eq "init") {
	if ($recovery) {
	    if (!$accounts{$anum} || $value ne $accounts{$anum}) {
		print "  Initializing account $anum to $value\n";
		$accounts{$anum} = $value;
	    }
	} else {
	    $accounts{$anum} = $value;
	}
    } elsif ($type eq "write") {
	if ($recovery) {
	    if (!$accounts{$anum} || $value ne $accounts{$anum}) {
		print "  Writing $value to account number $anum\n";
		$accounts{$anum} = $value;
	    } 
	} else {
	    $accounts{$anum} = $value;
	}

    } elsif ($type eq "begin") {
	#$active{$tid} = 1;
    } elsif ($type eq "commit") {
	$winners{$tid} = 1;
	delete $active{$tid};
    }
}


sub undo_command {
# Take a command and undo it from the database

    my ($tid, $type, $anum, $value, $oldvalue) = @_;

    if ($type eq "init" && $accounts{$anum}) {
	print "   Undoing: init $tid $anum $value\n";
	delete $accounts{$anum};
    } elsif ($type eq "write" && $accounts{$anum} && $accounts{$anum} eq $value) {
	print "   Undoing: write $tid $anum $value, reseting value to $oldvalue\n";
	$accounts{$anum} = $oldvalue;
    }
}

sub log_command {
# Write the passed command to the log file
    my ($tid, $type, $anum, $value, $oldvalue) = @_;
    my $s;

    if ($type eq "begin") {
	$s = "TID $tid: BEGIN\n";
    } elsif ($type eq "init") {
	$s = "TID $tid: INIT account $anum to $value\n";
    } elsif ($type eq "write") {
	$s = "TID $tid: WRITE the value $value to account $anum (value was $oldvalue)\n";
    } elsif ($type eq "commit") {
	$s = "TID $tid: COMMIT\n";
    }

    if ($mode eq $intentionmode) {
	print LOG $s;
    } else {
	if ($last_entry ne "") { print LOG $last_entry; }
	$last_entry = $s;
    }
}

sub do_checkpoint {
# write out the current DB to a checkpoint, and insert a pointer into the log
    print "  Writing checkpoint\n";
    write_cp(0);
}
sub do_crash {
    close(LOG);
    write_cp(-1);
    exit(0);
}

sub process_command_input {
# Read commands from STDIN and process them.

    my ($line) = ();
    my @command = ();
    open(LOG, ">>LOG") or die "Coult not open LOG for writing";

    while ($line = <STDIN>) {
	@command = ();
	if ($line =~ /begin\s+(\d+)\s*$/) {
	    @command = ($1, "begin", 0,0,0);
	} elsif ($line =~ /init\s+(\d+)\s+(\S+)\s+(\d+)\s*$/) {
	    @command = ($1, "init", $2,$3,0);
	} elsif ($line =~ /write\s+(\d+)\s+(\S+)\s+(\d+)\s*$/) {
	    if ($tentative_accounts{$2}) { 
		@command = ($1, "write", $2,$3,$tentative_accounts{$2});
	    } else {
		@command = ($1, "write", $2,$3,0);
	    }
	} elsif ($line =~ /commit\s+(\d+)\s*$/) {
	    @command = ($1, "commit", 0,0,0);


	} elsif ($line =~ /print/) {
	    &print_db();
	    next;
	} elsif ($line =~ /crash/) {
	    &do_crash();
	} elsif ($line =~ /checkpoint/) {
	    &do_checkpoint();
	    next;
	} elsif ($line =~/^\s*$/) {
	} else {
	    print "invalid command: $line";
	    next;
	}

	if (scalar(@command)) {
	    if (&check_command(@command)) {
		if ($mode eq $intentionmode) {
		    &log_command(@command);
		    &do_tentative_command(@command);
		} else {
		    &do_command(1, @command);
		    &log_command(@command);

		    if ($command[1] eq "commit") {
			my %t = reverse %active_accts;
			if ($t{$1} && $active_accts{$t{$1}}) {delete $active_accts{$t{$1}};}
			&commit_transaction($1);
		    }


		}
	    } else {
		print " invalid command: $line";
	    }
	}
	    
    }
}
sub process_log_input {
# Take a line from the log and apply it to the DB
    my ($line) = @_;
    my @command = ();

    if ($line =~ /TID (\d+): BEGIN/) {
	@command = ($1, "begin", 0,0,0);	
    } elsif ($line =~ /TID (\d+): INIT account (\S+) to (\d+)/) {
	@command = ($1, "init", $2,$3,0);
    } elsif ($line =~ /TID (\d+): WRITE the value (\d+) to account (\S+) \(value was (\d+)\)/) {
	@command = ($1, "write", $2,$3,$4);
    } elsif ($line =~ /TID (\d+): COMMIT/) {
	@command = ($1, "commit", 0,0,0);
    } else {
	print "  invalid log entry: $line";
    }
    
    if (scalar(@command)) {
	if (&check_command(@command)) {
	    &do_command(0, @command);
	} else {
	    print " invalid log entry: $line";
	}
    }
}

sub read_log {
    my ($before_ref, $after_ref, $uncommitted_ref) = @_;
    my $relevant_cp = -1;

    if (!open(LOG, "LOG")) { 
	#print "  No log exists.\n";
	return -1;
    }

    # find all transactions before and after last CP, starting at the last recovered point
    while(<LOG>) {
	if (/TID (\d+): BEGIN/) {
	    push @{$after_ref}, [$1, "begin", 0, 0, 0];
	} elsif (/TID (\d+): INIT account (\S+) to (\d+)/) {
	    push @{$after_ref}, [$1, "init", $2, $3, 0];
 	} elsif (/TID (\d+): WRITE the value (\d+) to account (\S+) \(value was (\d+)\)/) {
	    push @{$after_ref}, [$1, "write", $3, $2, $4];
	} elsif (/TID (\d+): COMMIT/) {
	    push @{$after_ref}, [$1, "commit", 0, 0, 0];
	} elsif (/CHECKPOINT\s*(.*)$/) {
	    %{$uncommitted_ref} = ();
	    my $numbers = $1;
	    while($numbers =~ /^\s*(\d+)(.*)$/) {
		${%{$uncommitted_ref}}{$1} = 1;
		$numbers = $2;
	    }
	    push @{$before_ref}, @{$after_ref};
	    @{$after_ref}  = ();
	} elsif (/RECOVERED/) {
	    %{$uncommitted_ref} = ();
            @{$before_ref} = ();
	    @{$after_ref}  = ();
	} else {
	    print "  invalid log entry: $_";
	}
    }
    close(LOG);
    return;
}

sub recover_backout {
    my (%losers, @before, @after, $command_ref, @command);
    my %uncommitted;

    &read_cp(-1);

    &read_log(\@before, \@after, \%uncommitted);
    push @before, @after;

    %losers = %{&find_uncommitted_tid(@before)};
    &print_tid("  Loser ", \%losers);

    foreach $command_ref (reverse @before) {
	@command = @{$command_ref};
	if ($losers{$command[0]}) {
	    &undo_command(@command);
	}
    }
}
sub recover_intentions {
# only recover transactions which were committed
    
    my (@before, @after, @command);
    my ($tid, $A, $B, $C, $T);
    my (%losers, %winners, %uncommitted);

    &read_cp(-1);
    &read_log(\@before, \@after, \%uncommitted);

    %winners = (%{&find_intention_winners(\%uncommitted, @after)},
		%{&find_committed_tid(@after)});
    %losers  = (&find_intention_losers(\%uncommitted, \@after),
    		%{&find_uncommitted_tid(@after)});

    &print_tid("  Winner", \%winners);
    &print_tid("  Loser ", \%losers);
    
    # play winners starting from CP and working forwards
    foreach $command_ref (@before, @after) {
	@command = @{$command_ref};
	if ($winners{$command[0]}) {
	    &do_command(1, @command);
        }
    }
}


sub recover {
    print "Recovering...\n";
    if ($mode == $intentionmode) {
	&recover_intentions();
    } else {
	&recover_backout();
    }
    open(LOG, ">>LOG") or die "Coult not open LOG for writing";
    print LOG "RECOVERED\n";
    close(LOG);
    %tentative_accounts = %accounts;
    %last_db = %accounts;
}

#sub usage { print "usage : trans [-reset] [-intentions|-backout]\n"; }
sub usage { print "usage : trans [-reset]\n"; }

sub main {
    my @args  = @_;
    my $arg;

    while ($arg = shift (@args)) {
	if ($arg =~ /-reset/) {
	    system("rm", "-f", "LOG", "DB", "CP*");
	#} elsif ($arg =~ /-intentions/) {
	#    $mode = $intentionmode;
	#} elsif ($arg =~ /-backout/) {
	#    $mode = $backoutmode;
	} else {
	    &usage();
	    exit(0);
	}
    }

    if (open(Q, "LOG")) {
	close(Q);
	&recover();
    } else {
	close(Q);
	print "Starting new log\n";
    }


    &process_command_input();
}

&main(@ARGV);