// Copyright 2018 The dexon-consensus-core Authors
// This file is part of the dexon-consensus-core library.
//
// The dexon-consensus-core library is free software: you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public License as
// published by the Free Software Foundation, either version 3 of the License,
// or (at your option) any later version.
//
// The dexon-consensus-core library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with the dexon-consensus-core library. If not, see
// <http://www.gnu.org/licenses/>.

package core

import (
	"math/rand"
	"sort"
	"testing"

	"github.com/stretchr/testify/suite"

	"github.com/dexon-foundation/dexon-consensus-core/blockdb"
	"github.com/dexon-foundation/dexon-consensus-core/common"
	"github.com/dexon-foundation/dexon-consensus-core/core/test"
	"github.com/dexon-foundation/dexon-consensus-core/core/types"
)

type AckingTest struct {
	suite.Suite
}

func (s *AckingTest) SetupSuite() {

}

func (s *AckingTest) SetupTest() {

}

// genTestCase1 generates test case 1,
//  3
//  |
//  2
//  | \
//  1  |     1
//  |  |     |
//  0  0  0  0 (block height)
//  0  1  2  3 (validator)
func genTestCase1(s *AckingTest, a *acking) []types.ValidatorID {
	// Create new acking instance with 4 validators
	var b *types.Block
	var h common.Hash
	vids := []types.ValidatorID{}
	for i := 0; i < 4; i++ {
		vid := types.ValidatorID{Hash: common.NewRandomHash()}
		a.addValidator(vid)
		vids = append(vids, vid)
	}
	// Add genesis blocks.
	for i := 0; i < 4; i++ {
		h = common.NewRandomHash()
		b = &types.Block{
			ProposerID: vids[i],
			ParentHash: h,
			Hash:       h,
			Height:     0,
			Acks:       map[common.Hash]struct{}{},
		}
		a.processBlock(b)
	}

	// Add block 0-1 which acks 0-0.
	h = a.lattice[vids[0]].blocks[0].Hash
	b = &types.Block{
		ProposerID: vids[0],
		ParentHash: h,
		Hash:       common.NewRandomHash(),
		Height:     1,
		Acks: map[common.Hash]struct{}{
			h: struct{}{},
		},
	}
	a.processBlock(b)
	s.NotNil(a.lattice[vids[0]].blocks[1])

	// Add block 0-2 which acks 0-1 and 1-0.
	h = a.lattice[vids[0]].blocks[1].Hash
	b = &types.Block{
		ProposerID: vids[0],
		ParentHash: h,
		Hash:       common.NewRandomHash(),
		Height:     2,
		Acks: map[common.Hash]struct{}{
			h: struct{}{},
			a.lattice[vids[1]].blocks[0].Hash: struct{}{},
		},
	}
	a.processBlock(b)
	s.NotNil(a.lattice[vids[0]].blocks[2])

	// Add block 0-3 which acks 0-2.
	h = a.lattice[vids[0]].blocks[2].Hash
	b = &types.Block{
		ProposerID: vids[0],
		ParentHash: h,
		Hash:       common.NewRandomHash(),
		Height:     3,
		Acks: map[common.Hash]struct{}{
			h: struct{}{},
		},
	}
	a.processBlock(b)
	s.NotNil(a.lattice[vids[0]].blocks[3])

	// Add block 3-1 which acks 3-0.
	h = a.lattice[vids[3]].blocks[0].Hash
	b = &types.Block{
		ProposerID: vids[3],
		ParentHash: h,
		Hash:       common.NewRandomHash(),
		Height:     1,
		Acks: map[common.Hash]struct{}{
			h: struct{}{},
		},
	}
	a.processBlock(b)
	s.NotNil(a.lattice[vids[3]].blocks[0])

	return vids
}

func (s *AckingTest) TestAddValidator() {
	a := newAcking()
	s.Equal(len(a.lattice), 0)
	genTestCase1(s, a)
	s.Equal(len(a.lattice), 4)
}

func (s *AckingTest) TestSanityCheck() {
	var b *types.Block
	var h common.Hash
	var vids []types.ValidatorID
	var err error
	a := newAcking()
	vids = genTestCase1(s, a)

	// Non-genesis block with no ack, should get error.
	b = &types.Block{
		ProposerID: vids[0],
		ParentHash: common.NewRandomHash(),
		Height:     10,
		Acks:       make(map[common.Hash]struct{}),
	}
	err = a.sanityCheck(b)
	s.NotNil(err)
	s.Equal(ErrNotAckParent.Error(), err.Error())

	// Non-genesis block which does not ack its parent.
	b = &types.Block{
		ProposerID: vids[1],
		ParentHash: common.NewRandomHash(),
		Height:     1,
		Acks: map[common.Hash]struct{}{
			a.lattice[vids[2]].blocks[0].Hash: struct{}{},
		},
	}
	err = a.sanityCheck(b)
	s.NotNil(err)
	s.Equal(ErrNotAckParent.Error(), err.Error())

	// Non-genesis block which acks its parent but the height is invalid.
	h = a.lattice[vids[1]].blocks[0].Hash
	b = &types.Block{
		ProposerID: vids[1],
		ParentHash: h,
		Height:     2,
		Acks: map[common.Hash]struct{}{
			h: struct{}{},
		},
	}
	err = a.sanityCheck(b)
	s.NotNil(err)
	s.Equal(ErrInvalidBlockHeight.Error(), err.Error())

	// Invalid proposer ID.
	h = a.lattice[vids[1]].blocks[0].Hash
	b = &types.Block{
		ProposerID: types.ValidatorID{Hash: common.NewRandomHash()},
		ParentHash: h,
		Height:     1,
		Acks: map[common.Hash]struct{}{
			h: struct{}{},
		},
	}
	err = a.sanityCheck(b)
	s.NotNil(err)
	s.Equal(ErrInvalidProposerID.Error(), err.Error())

	// Fork block.
	h = a.lattice[vids[0]].blocks[0].Hash
	b = &types.Block{
		ProposerID: vids[0],
		ParentHash: h,
		Height:     1,
		Acks: map[common.Hash]struct{}{
			h: struct{}{},
		},
	}
	err = a.sanityCheck(b)
	s.NotNil(err)
	s.Equal(ErrForkBlock.Error(), err.Error())

	// Replicated ack.
	h = a.lattice[vids[0]].blocks[3].Hash
	b = &types.Block{
		ProposerID: vids[0],
		ParentHash: h,
		Height:     4,
		Acks: map[common.Hash]struct{}{
			h: struct{}{},
			a.lattice[vids[1]].blocks[0].Hash: struct{}{},
		},
	}
	err = a.sanityCheck(b)
	s.NotNil(err)
	s.Equal(ErrDoubleAck.Error(), err.Error())

	// Normal block.
	h = a.lattice[vids[1]].blocks[0].Hash
	b = &types.Block{
		ProposerID: vids[1],
		ParentHash: h,
		Height:     1,
		Acks: map[common.Hash]struct{}{
			h: struct{}{},
			common.NewRandomHash(): struct{}{},
		},
	}
	err = a.sanityCheck(b)
	s.Nil(err)
}

func (s *AckingTest) TestAreAllAcksInLattice() {
	var b *types.Block
	var vids []types.ValidatorID
	a := newAcking()
	vids = genTestCase1(s, a)

	// Empty ack should get true, although won't pass sanity check.
	b = &types.Block{
		Acks: map[common.Hash]struct{}{},
	}
	s.True(a.areAllAcksInLattice(b))

	// Acks blocks in lattice
	b = &types.Block{
		Acks: map[common.Hash]struct{}{
			a.lattice[vids[0]].blocks[0].Hash: struct{}{},
			a.lattice[vids[0]].blocks[1].Hash: struct{}{},
		},
	}
	s.True(a.areAllAcksInLattice(b))

	// Acks random block hash.
	b = &types.Block{
		Acks: map[common.Hash]struct{}{
			common.NewRandomHash(): struct{}{},
		},
	}
	s.False(a.areAllAcksInLattice(b))
}

func (s *AckingTest) TestStrongAck() {
	var b *types.Block
	var vids []types.ValidatorID
	a := newAcking()
	vids = genTestCase1(s, a)

	// Check block 0-0 to 0-3 before adding 1-1 and 2-1.
	for i := uint64(0); i < 4; i++ {
		s.Equal(types.BlockStatusInit, a.lattice[vids[0]].blocks[i].Status)
	}

	// Add block 1-1 which acks 1-0 and 0-2, and block 0-0 to 0-3 are still
	// in BlockStatusInit, because they are not strongly acked.
	b = &types.Block{
		ProposerID: vids[1],
		ParentHash: a.lattice[vids[1]].blocks[0].Hash,
		Hash:       common.NewRandomHash(),
		Height:     1,
		Acks: map[common.Hash]struct{}{
			a.lattice[vids[0]].blocks[2].Hash: struct{}{},
			a.lattice[vids[1]].blocks[0].Hash: struct{}{},
		},
	}
	a.processBlock(b)
	s.NotNil(a.lattice[vids[1]].blocks[1])
	for i := uint64(0); i < 4; i++ {
		s.Equal(types.BlockStatusInit, a.lattice[vids[0]].blocks[i].Status)
	}

	// Add block 2-1 which acks 0-2 and 2-0, block 0-0 to 0-2 are strongly acked but
	// 0-3 is still not.
	b = &types.Block{
		ProposerID: vids[2],
		ParentHash: a.lattice[vids[2]].blocks[0].Hash,
		Hash:       common.NewRandomHash(),
		Height:     1,
		Acks: map[common.Hash]struct{}{
			a.lattice[vids[0]].blocks[2].Hash: struct{}{},
			a.lattice[vids[2]].blocks[0].Hash: struct{}{},
		},
	}
	a.processBlock(b)
	s.Equal(types.BlockStatusAcked, a.lattice[vids[0]].blocks[0].Status)
	s.Equal(types.BlockStatusAcked, a.lattice[vids[0]].blocks[1].Status)
	s.Equal(types.BlockStatusAcked, a.lattice[vids[0]].blocks[2].Status)
	s.Equal(types.BlockStatusInit, a.lattice[vids[0]].blocks[3].Status)
}

func (s *AckingTest) TestExtractBlocks() {
	var b *types.Block
	a := newAcking()
	vids := genTestCase1(s, a)

	// Add block 1-1 which acks 1-0, 0-2, 3-0.
	b = &types.Block{
		ProposerID: vids[1],
		ParentHash: a.lattice[vids[1]].blocks[0].Hash,
		Hash:       common.NewRandomHash(),
		Height:     1,
		Acks: map[common.Hash]struct{}{
			a.lattice[vids[0]].blocks[2].Hash: struct{}{},
			a.lattice[vids[1]].blocks[0].Hash: struct{}{},
			a.lattice[vids[3]].blocks[0].Hash: struct{}{},
		},
	}
	a.processBlock(b)

	// Add block 2-1 which acks 0-2, 2-0, 3-0.
	b = &types.Block{
		ProposerID: vids[2],
		ParentHash: a.lattice[vids[2]].blocks[0].Hash,
		Hash:       common.NewRandomHash(),
		Height:     1,
		Acks: map[common.Hash]struct{}{
			a.lattice[vids[0]].blocks[2].Hash: struct{}{},
			a.lattice[vids[2]].blocks[0].Hash: struct{}{},
			a.lattice[vids[3]].blocks[0].Hash: struct{}{},
		},
	}
	a.processBlock(b)

	hashs := []common.Hash{
		a.lattice[vids[0]].blocks[0].Hash,
		a.lattice[vids[0]].blocks[1].Hash,
		a.lattice[vids[3]].blocks[0].Hash,
	}
	hashExtracted := map[common.Hash]*types.Block{}
	for _, b := range a.extractBlocks() {
		hashExtracted[b.Hash] = b
		s.Equal(types.BlockStatusOrdering, b.Status)
	}
	for _, h := range hashs {
		_, exist := hashExtracted[h]
		s.True(exist)
	}
}

func (s *AckingTest) TestRandomIntensiveAcking() {
	a := newAcking()
	vids := []types.ValidatorID{}
	heights := map[types.ValidatorID]uint64{}
	extractedBlocks := []*types.Block{}

	// Generate validators and genesis blocks.
	for i := 0; i < 4; i++ {
		vid := types.ValidatorID{Hash: common.NewRandomHash()}
		a.addValidator(vid)
		vids = append(vids, vid)
		h := common.NewRandomHash()
		b := &types.Block{
			Hash:       h,
			ParentHash: h,
			Acks:       map[common.Hash]struct{}{},
			Height:     0,
			ProposerID: vid,
		}
		a.processBlock(b)
		heights[vid] = 1
	}

	for i := 0; i < 5000; i++ {
		vid := vids[rand.Int()%len(vids)]
		height := heights[vid]
		heights[vid]++
		parentHash := a.lattice[vid].blocks[height-1].Hash
		acks := map[common.Hash]struct{}{}
		for _, vid2 := range vids {
			if b, exist := a.lattice[vid2].blocks[a.lattice[vid].nextAck[vid2]]; exist {
				acks[b.Hash] = struct{}{}
			}
		}
		b := &types.Block{
			ProposerID: vid,
			Hash:       common.NewRandomHash(),
			ParentHash: parentHash,
			Height:     height,
			Acks:       acks,
		}
		a.processBlock(b)
		extractedBlocks = append(extractedBlocks, a.extractBlocks()...)
	}

	extractedBlocks = append(extractedBlocks, a.extractBlocks()...)
	// The len of array extractedBlocks should be about 5000.
	s.True(len(extractedBlocks) > 4500)
	// The len of a.blocks should be small if deleting mechanism works.
	s.True(len(a.blocks) < 500)
}

func (s *AckingTest) TestRandomlyGeneratedBlocks() {
	var (
		validatorCount = 19
		blockCount     = 50
		repeat         = 20
	)

	// Prepare a randomly generated blocks.
	db, err := blockdb.NewMemBackedBlockDB("test-acking-random.blockdb")
	s.Require().Nil(err)
	defer func() {
		// If the test fails, keep the block database for troubleshooting.
		if s.T().Failed() {
			s.Nil(db.Close())
		}
	}()
	gen := test.NewBlocksGenerator(nil)
	s.Require().Nil(gen.Generate(validatorCount, blockCount, nil, db))
	iter, err := db.GetAll()
	s.Require().Nil(err)
	// Setup a revealer that would reveal blocks randomly.
	revealer, err := test.NewRandomRevealer(iter)
	s.Require().Nil(err)

	stronglyAckedHashesAsString := map[string]struct{}{}
	for i := 0; i < repeat; i++ {
		validators := map[types.ValidatorID]struct{}{}
		acking := newAcking()
		stronglyAckedHashes := common.Hashes{}
		revealer.Reset()

		for {
			// Reveal next block.
			b, err := revealer.Next()
			if err != nil {
				if err == blockdb.ErrIterationFinished {
					err = nil
					break
				}
			}
			s.Require().Nil(err)

			// It's a hack to add validator to Acking module.
			if _, added := validators[b.ProposerID]; !added {
				acking.addValidator(b.ProposerID)
				validators[b.ProposerID] = struct{}{}
			}
			// Perform reliable broadcast process.
			acking.processBlock(&b)
			for _, b := range acking.extractBlocks() {
				stronglyAckedHashes = append(stronglyAckedHashes, b.Hash)
			}
		}
		// To make it easier to check, sort hashes of
		// strongly acked blocks, and concatenate them into
		// a string.
		sort.Sort(stronglyAckedHashes)
		asString := ""
		for _, h := range stronglyAckedHashes {
			asString += h.String() + ","
		}
		stronglyAckedHashesAsString[asString] = struct{}{}
	}
	// Make sure concatenated hashes of strongly acked blocks are identical.
	s.Require().Len(stronglyAckedHashesAsString, 1)
	for h := range stronglyAckedHashesAsString {
		// Make sure at least some blocks are strongly acked.
		s.True(len(h) > 0)
	}
}

func TestAcking(t *testing.T) {
	suite.Run(t, new(AckingTest))
}