func TestAbortCacheEncodeDecode(t *testing.T) {
	defer leaktest.AfterTest(t)()
	const rangeID = 123
	testTxnID, err := uuid.FromString("0ce61c17-5eb4-4587-8c36-dcf4062ada4c")
	if err != nil {
		panic(err)
	}
	key := AbortCacheKey(rangeID, testTxnID)
	txnID, err := DecodeAbortCacheKey(key, nil)
	if err != nil {
		t.Fatal(err)
	}
	if !roachpb.TxnIDEqual(txnID, testTxnID) {
		t.Fatalf("expected txnID %q, got %q", testTxnID, txnID)
	}
}

// GetMax returns the maximum read and write timestamps which overlap
// the interval spanning from start to end. Cached timestamps matching
// the specified txnID are not considered. If no part of the specified
// range is overlapped by timestamps in the cache, the low water
// timestamp is returned for both read and write timestamps.
//
// The txn ID prevents restarts with a pattern like: read("a"),
// write("a"). The read adds a timestamp for "a". Then the write (for
// the same transaction) would get that as the max timestamp and be
// forced to increment it. This allows timestamps from the same txn
// to be ignored.
func (tc *TimestampCache) GetMax(start, end roachpb.Key, txnID []byte) (roachpb.Timestamp, roachpb.Timestamp) {
	if len(end) == 0 {
		end = start.Next()
	}
	maxR := tc.lowWater
	maxW := tc.lowWater
	for _, o := range tc.cache.GetOverlaps(start, end) {
		ce := o.Value.(*cacheValue)
		if ce.txnID == nil || txnID == nil || !roachpb.TxnIDEqual(txnID, ce.txnID) {
			if ce.readOnly && maxR.Less(ce.timestamp) {
				maxR = ce.timestamp
			} else if !ce.readOnly && maxW.Less(ce.timestamp) {
				maxW = ce.timestamp
			}
		}
	}
	return maxR, maxW
}

func (tc *TimestampCache) getMax(start, end roachpb.Key, txnID *uuid.UUID, readTSCache bool) roachpb.Timestamp {
	if len(end) == 0 {
		end = start.ShallowNext()
	}
	max := tc.lowWater
	cache := tc.wCache
	if readTSCache {
		cache = tc.rCache
	}
	for _, o := range cache.GetOverlaps(start, end) {
		ce := o.Value.(*cacheValue)
		if ce.txnID == nil || txnID == nil || !roachpb.TxnIDEqual(txnID, ce.txnID) {
			if max.Less(ce.timestamp) {
				max = ce.timestamp
			}
		}
	}
	return max
}

func TestSequenceCacheEncodeDecode(t *testing.T) {
	defer leaktest.AfterTest(t)
	const rangeID = 123
	const expSeq = 987
	key := keys.SequenceCacheKey(rangeID, testTxnID, testTxnEpoch, expSeq)
	txnID, epoch, seq, err := decodeSequenceCacheKey(key, nil)
	if err != nil {
		t.Fatal(err)
	}
	if !roachpb.TxnIDEqual(txnID, testTxnID) {
		t.Fatalf("expected txnID %q, got %q", testTxnID, txnID)
	}
	if epoch != testTxnEpoch {
		t.Fatalf("expected epoch %d, got %d", testTxnEpoch, epoch)
	}
	if seq != expSeq {
		t.Fatalf("expected sequence %d, got %d", expSeq, seq)
	}
}

func TestSequenceCacheEncodeDecode(t *testing.T) {
	defer leaktest.AfterTest(t)()
	const rangeID = 123
	const testTxnEpoch = 5
	const expSeq = 987
	testTxnID, err := uuid.FromString("0ce61c17-5eb4-4587-8c36-dcf4062ada4c")
	if err != nil {
		panic(err)
	}
	key := SequenceCacheKey(rangeID, testTxnID, testTxnEpoch, expSeq)
	txnID, epoch, seq, err := DecodeSequenceCacheKey(key, nil)
	if err != nil {
		t.Fatal(err)
	}
	if !roachpb.TxnIDEqual(txnID, testTxnID) {
		t.Fatalf("expected txnID %q, got %q", testTxnID, txnID)
	}
	if epoch != testTxnEpoch {
		t.Fatalf("expected epoch %d, got %d", testTxnEpoch, epoch)
	}
	if seq != expSeq {
		t.Fatalf("expected sequence %d, got %d", expSeq, seq)
	}
}

// TestPropagateTxnOnPushError is similar to TestPropagateTxnOnError,
// but verifies that txn data are propagated to the next iteration on
// TransactionPushError.
func TestPropagateTxnOnPushError(t *testing.T) {
	defer leaktest.AfterTest(t)
	s := server.StartTestServer(t)
	defer s.Stop()
	db := setupMultipleRanges(t, s, "b")

	waitForWriteIntent := make(chan struct{})
	waitForTxnRestart := make(chan struct{})
	waitForTxnCommit := make(chan struct{})
	// Create a goroutine that creates a write intent and waits until
	// another txn created in this test is restarted.
	go func() {
		if pErr := db.Txn(func(txn *client.Txn) *roachpb.Error {
			if pErr := txn.Put("b", "val"); pErr != nil {
				return pErr
			}
			close(waitForWriteIntent)
			// Wait until another txn in this test is
			// restarted by a push txn error.
			<-waitForTxnRestart
			return txn.CommitInBatch(txn.NewBatch())
		}); pErr != nil {
			t.Errorf("unexpected error on transactional Puts: %s", pErr)
		}
		close(waitForTxnCommit)
	}()

	// Wait until a write intent is created by the above goroutine.
	<-waitForWriteIntent

	// The transaction below is restarted multiple times.
	// - The first retry is caused by the write intent created on key "b" by the above goroutine.
	// - The subsequent retries are caused by the write conflict on key "a". Since the txn
	//   ID is not propagated, a txn of a new epoch always has a new txn ID different
	//   from the previous txn's. So, the write intent made by the txn of the previous epoch
	//   is treated as a write made by some different txn.
	epoch := 0
	var txnID *uuid.UUID
	if pErr := db.Txn(func(txn *client.Txn) *roachpb.Error {
		// Set low priority so that the intent will not be pushed.
		txn.InternalSetPriority(1)

		epoch++

		if epoch == 2 {
			close(waitForTxnRestart)
			// Wait until the txn created by the goroutine is committed.
			<-waitForTxnCommit
			if !roachpb.TxnIDEqual(txn.Proto.ID, txnID) {
				t.Errorf("txn ID is not propagated; got %s", txn.Proto.ID)
			}
		}

		b := txn.NewBatch()
		b.Put("a", "val")
		b.Put("b", "val")
		// The commit returns an error, but it will not be
		// passed to the next iteration. txnSender.Send() does
		// not update the txn data since
		// TransactionPushError.Transaction() returns nil.
		pErr := txn.CommitInBatch(b)
		if epoch == 1 {
			if tErr, ok := pErr.GetDetail().(*roachpb.TransactionPushError); ok {
				if tErr.Txn.ID == nil {
					t.Errorf("txn ID is not set unexpectedly: %s", tErr)
				}
				txnID = tErr.Txn.ID
			} else {
				t.Errorf("expected TransactionRetryError, but got: %s", pErr)
			}
		}
		return pErr
	}); pErr != nil {
		t.Errorf("unexpected error on transactional Puts: %s", pErr)
	}

	if e := 2; epoch != e {
		t.Errorf("unexpected epoch; the txn must be attempted %d times, but got %d attempts", e, epoch)
	}
}

// TestPropagateTxnOnPushError is similar to TestPropagateTxnOnError,
// but verifies that txn data are propagated to the next iteration on
// TransactionPushError.
func TestPropagateTxnOnPushError(t *testing.T) {
	defer leaktest.AfterTest(t)()
	s := server.StartTestServer(t)
	defer s.Stop()
	db := setupMultipleRanges(t, s, "b")

	waitForWriteIntent := make(chan struct{})
	waitForTxnRestart := make(chan struct{})
	waitForTxnCommit := make(chan struct{})
	lowPriority := int32(1)
	highPriority := int32(10)
	key := "a"
	// Create a goroutine that creates a write intent and waits until
	// another txn created in this test is restarted.
	go func() {
		if pErr := db.Txn(func(txn *client.Txn) *roachpb.Error {
			// Set high priority so that the intent will not be pushed.
			txn.InternalSetPriority(highPriority)
			log.Infof("Creating a write intent with high priority")
			if pErr := txn.Put(key, "val"); pErr != nil {
				return pErr
			}
			close(waitForWriteIntent)
			// Wait until another txn in this test is
			// restarted by a push txn error.
			log.Infof("Waiting for the txn restart")
			<-waitForTxnRestart
			return txn.CommitInBatch(txn.NewBatch())
		}); pErr != nil {
			t.Errorf("unexpected error on transactional Puts: %s", pErr)
		}
		close(waitForTxnCommit)
	}()

	// Wait until a write intent is created by the above goroutine.
	log.Infof("Waiting for the write intent creation")
	<-waitForWriteIntent

	// The transaction below is restarted exactly once. The restart is
	// caused by the write intent created on key "a" by the above goroutine.
	// When the txn is retried, the error propagates the txn ID to the next
	// iteration.
	epoch := 0
	var txnID *uuid.UUID
	if pErr := db.Txn(func(txn *client.Txn) *roachpb.Error {
		// Set low priority so that a write from this txn will not push others.
		txn.InternalSetPriority(lowPriority)

		epoch++

		if epoch == 2 {
			close(waitForTxnRestart)
			// Wait until the txn created by the goroutine is committed.
			log.Infof("Waiting for the txn commit")
			<-waitForTxnCommit
			if !roachpb.TxnIDEqual(txn.Proto.ID, txnID) {
				t.Errorf("txn ID is not propagated; got %s", txn.Proto.ID)
			}
		}

		// The commit returns an error, and it will pass
		// the txn data to the next iteration.
		pErr := txn.Put(key, "val")
		if epoch == 1 {
			if tErr, ok := pErr.GetDetail().(*roachpb.TransactionPushError); ok {
				if pErr.GetTxn().ID == nil {
					t.Errorf("txn ID is not set unexpectedly: %s", tErr)
				}
				txnID = pErr.GetTxn().ID
			} else {
				t.Errorf("expected TransactionRetryError, but got: %s", pErr)
			}
		}
		return pErr
	}); pErr != nil {
		t.Errorf("unexpected error on transactional Puts: %s", pErr)
	}

	if e := 2; epoch != e {
		t.Errorf("unexpected epoch; the txn must be attempted %d times, but got %d attempts", e, epoch)
		if epoch == 1 {
			// Wait for the completion of the goroutine to see if it successfully commits the txn.
			close(waitForTxnRestart)
			log.Infof("Waiting for the txn commit")
			<-waitForTxnCommit
		}
	}
}

// TestDoNotPropagateTxnOnError reproduces a bug where txn data (e.g., txn ID)
// are not propagated to a next epoch on error.
//
// TODO(kkaneda): Fix #743. The bug happens since not all errors carry
// a transaction, but range-spanning writes are not atomic (and data
// may actually have been written).
func TestDoNotPropagateTxnOnError(t *testing.T) {
	defer leaktest.AfterTest(t)
	s, db := setupMultipleRanges(t, "b")
	defer s.Stop()

	waitForWriteIntent := make(chan struct{})
	waitForTxnRestart := make(chan struct{})
	waitForTxnCommit := make(chan struct{})
	// Create a goroutine that creates a write intent and waits until
	// another txn created in this test is restarted.
	go func() {
		if err := db.Txn(func(txn *client.Txn) error {
			if err := txn.Put("b", "val"); err != nil {
				return err
			}
			close(waitForWriteIntent)
			// Wait until another txn in this test is
			// restarted by a push txn error.
			<-waitForTxnRestart
			return txn.CommitInBatch(&client.Batch{})
		}); err != nil {
			t.Errorf("unexpected error on transactional Puts: %s", err)
		}
		close(waitForTxnCommit)
	}()

	// Wait until a write intent is created by the above goroutine.
	<-waitForWriteIntent

	// The transaction below is restarted multiple times.
	// - The first retry is caused by the write intent created on key "b" by the above goroutine.
	// - The subsequent retries are caused by the write conflict on key "a". Since the txn
	//   ID is not propagated, a txn of a new epoch always has a new txn ID different
	//   from the previous txn's. So, the write intent made by the txn of the previous epoch
	//   is treated as a write made by some different txn.
	epoch := 0
	if err := db.Txn(func(txn *client.Txn) error {
		// Set low priority so that the intent will not be pushed.
		txn.InternalSetPriority(1)

		epoch++

		if epoch == 2 {
			close(waitForTxnRestart)
			// Wait until the txn created by the goroutine is committed.
			<-waitForTxnCommit
		} else if epoch > 2 {
			// Enough number of retries.
			return nil
		}

		if !roachpb.TxnIDEqual(txn.Proto.ID, []byte("")) {
			t.Errorf("txn ID is set unexpectedly")
		}

		b := &client.Batch{}
		b.Put("a", "val")
		b.Put("b", "val")
		// The commit returns an error, but it will not be
		// passed to the next iteration. txnSender.Send() does
		// not update the txn data since
		// TransactionPushError.Transaction() returns nil.
		err := txn.CommitInBatch(b)
		if tErr, ok := err.(*roachpb.TransactionPushError); ok {
			if roachpb.TxnIDEqual(tErr.Txn.ID, []byte("")) {
				t.Errorf("txn ID is not set unexpectedly: %s", tErr.Txn.ID)
			}
		} else {
			t.Errorf("expected TransactionRetryError, but got: %s", err)
		}
		return err
	}); err != nil {
		t.Errorf("unexpected error on transactional Puts: %s", err)
	}

	if epoch <= 2 {
		t.Errorf("unexpected epoch; the txn must be retried at least twice, but got %d", epoch)
	}
}