// Copyright 2020 CUE Authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package eval

import (
	"fmt"
	"strings"
	"testing"

	"cuelang.org/go/internal/core/adt"
)

func TestInsert(t *testing.T) {
	testCases := []struct {
		tree   []CloseDef
		typ    func(c *acceptor, at adt.ID, p adt.Node) adt.ID
		at     adt.ID
		wantID adt.ID
		out    string
	}{{
		tree:   nil,
		at:     0,
		typ:    (*acceptor).InsertDefinition,
		wantID: 1,
		out:    "&( 0[] *1[])",
	}, {
		tree:   []CloseDef{{}},
		at:     0,
		typ:    (*acceptor).InsertDefinition,
		wantID: 1,
		out:    "&( 0[] *1[])",
	}, {
		tree:   []CloseDef{0: {And: 1}, {And: 0, IsDef: true}},
		at:     0,
		typ:    (*acceptor).InsertDefinition,
		wantID: 2,
		out:    "&( 0[] *2[] *1[])",
	}, {
		tree:   []CloseDef{0: {And: 1}, 1: {And: 0, IsDef: true}},
		at:     1,
		typ:    (*acceptor).InsertDefinition,
		wantID: 2,
		out:    "&( 0[] 1[] *2[])",
	}, {
		tree: []CloseDef{
			0: {And: 1},
			1: {And: 2, IsDef: true},
			2: {And: 0, IsDef: true},
		},
		at:     1,
		typ:    (*acceptor).InsertDefinition,
		wantID: 3,
		out:    "&( 0[] 1[] *3[] *2[])",
	}, {
		tree: []CloseDef{
			0: {And: 1},
			1: {And: 0, NextEmbed: 2, IsDef: true},
			2: {And: embedRoot},
			3: {And: 3},
		},
		at:     1,
		typ:    (*acceptor).InsertDefinition,
		wantID: 4,
		out:    "&( 0[] 1[&( 3[])] *4[])",
	}, {
		tree: []CloseDef{
			0: {And: 1},
			1: {And: 0, NextEmbed: 2, IsDef: true},
			2: {And: embedRoot},
			3: {And: 3},
		},
		at:     3,
		typ:    (*acceptor).InsertDefinition,
		wantID: 4,
		out:    "&( 0[] *1[&( 3[] *4[])])",
	}, {
		tree:   nil,
		at:     0,
		typ:    (*acceptor).InsertEmbed,
		wantID: 2,
		out:    "&( 0[&( 2[])])",
	}, {
		tree:   []CloseDef{{}},
		at:     0,
		typ:    (*acceptor).InsertEmbed,
		wantID: 2,
		out:    "&( 0[&( 2[])])",
	}, {
		tree:   []CloseDef{0: {And: 1}, 1: {And: 0, IsDef: true}},
		at:     1,
		typ:    (*acceptor).InsertEmbed,
		wantID: 3,
		out:    "&( 0[] *1[&( 3[])])",
	}, {
		tree:   []CloseDef{0: {NextEmbed: 1}, 1: {And: embedRoot}, 2: {And: 2}},
		at:     0,
		typ:    (*acceptor).InsertEmbed,
		wantID: 4,
		out:    "&( 0[&( 4[])&( 2[])])",
	}, {
		tree:   []CloseDef{0: {NextEmbed: 1}, 1: {And: embedRoot}, 2: {And: 2}},
		at:     1,
		typ:    (*acceptor).InsertEmbed,
		wantID: 4,
		out:    "&( 0[&( 2[])&( 4[])])",
	}, {
		tree: []CloseDef{
			0: {And: 1},
			1: {And: 2},
			2: {And: 0},
		},
		at:     2,
		typ:    (*acceptor).InsertEmbed,
		wantID: 4,
		out:    "&( 0[] 1[] 2[&( 4[])])",
	}}
	for i, tc := range testCases {
		t.Run(fmt.Sprint(i), func(t *testing.T) {
			c := &acceptor{Canopy: tc.tree}
			got := tc.typ(c, tc.at, nil)

			if got != tc.wantID {
				t.Errorf("id: got %d; want %d", got, tc.wantID)
			}

			w := &strings.Builder{}
			// fmt.Fprintf(w, "%#v", c.Canopy)
			writeConjuncts(w, c)
			if got := w.String(); got != tc.out {
				t.Errorf("id: got %s; want %s", got, tc.out)
			}
		})
	}
}

func TestInsertSubtree(t *testing.T) {
	testCases := []struct {
		tree []CloseDef
		at   adt.ID
		sub  []CloseDef
		out  string
	}{{
		tree: nil,
		at:   0,
		sub:  nil,
		out:  "&( 0[&( 2[])])",
	}, {
		tree: []CloseDef{{}},
		at:   0,
		sub:  nil,
		out:  "&( 0[&( 2[])])",
	}, {
		tree: []CloseDef{0: {And: 1}, {And: 0, IsDef: true}},
		at:   0,
		sub:  []CloseDef{{}},
		out:  "&( 0[&( 3[])] *1[])",
	}, {
		tree: []CloseDef{0: {And: 1}, {And: 0, IsDef: true}},
		at:   0,
		sub:  []CloseDef{{And: 1}, {And: 0, IsDef: true}},
		out:  "&( 0[&( 3[] *4[])] *1[])",
	}, {
		tree: []CloseDef{0: {NextEmbed: 1}, 1: {And: embedRoot}, 2: {And: 2}},
		at:   0,
		sub:  []CloseDef{0: {NextEmbed: 1}, 1: {And: embedRoot}, 2: {And: 2}},
		out:  "&( 0[&( 4[&( 6[])])&( 2[])])",
	}, {
		tree: []CloseDef{0: {NextEmbed: 1}, 1: {And: embedRoot}, 2: {And: 2}},
		at:   2,
		sub:  []CloseDef{0: {NextEmbed: 1}, 1: {And: embedRoot}, 2: {And: 2}},
		out:  "&( 0[&( 2[&( 4[&( 6[])])])])",
	}}
	for i, tc := range testCases {
		t.Run(fmt.Sprint(i), func(t *testing.T) {
			c := &acceptor{Canopy: tc.tree}
			d := &acceptor{Canopy: tc.sub}
			n := &nodeContext{nodeShared: &nodeShared{node: &adt.Vertex{}}}
			c.InsertSubtree(tc.at, n, &adt.Vertex{Closed: d}, false)

			w := &strings.Builder{}
			// fmt.Fprintf(w, "%#v", c.Canopy)
			writeConjuncts(w, c)
			if got := w.String(); got != tc.out {
				t.Errorf("id: got %s; want %s", got, tc.out)
			}
		})
	}
}
func TestVerifyArcAllowed(t *testing.T) {
	fields := func(a ...adt.Feature) []adt.Feature { return a }
	results := func(a ...bool) []bool { return a }
	fieldSets := func(a ...[]adt.Feature) [][]adt.Feature { return a }

	testCases := []struct {
		desc     string
		isClosed bool
		tree     []CloseDef
		fields   [][]adt.Feature
		check    []adt.Feature
		want     []bool
	}{{
		desc:     "required and remains closed with embedding",
		isClosed: true,
		tree: []CloseDef{
			{And: 0},
		},
		fields: fieldSets(
			fields(1),
		),
		check: fields(2),
		want:  results(false),
	}, {

		// 	desc:  "empty tree accepts everything",
		// 	tree:  nil,
		// 	check: feats(1),
		// 	want:  results(true),
		// }, {
		desc: "feature required in one",
		tree: []CloseDef{
			0: {And: 1},
			1: {And: 0, IsDef: true},
		},
		fields: fieldSets(
			fields(1),
			fields(2),
		),
		check: fields(1, 2, 3, 4),
		want:  results(false, true, false, false),
	}, {
		desc: "feature required in both",
		tree: []CloseDef{
			0: {And: 1, IsDef: true},
			1: {And: 0, IsDef: true},
		},
		fields: fieldSets(
			fields(1, 3),
			fields(2, 3),
		),
		check: fields(1, 2, 3, 4),
		want:  results(false, false, true, false),
	}, {
		desc: "feature required in neither",
		tree: []CloseDef{
			0: {And: 1},
			1: {And: 0},
		},
		fields: fieldSets(
			fields(1, 3),
			fields(2, 3),
		),
		check: fields(1, 2, 3, 4),
		want:  results(true, true, true, true),
	}, {
		desc: "closedness of embed",
		tree: []CloseDef{
			0: {And: 1},
			1: {And: 0, IsDef: true, NextEmbed: 2},
			2: {And: -1},
			3: {And: 4},
			4: {And: 3, IsDef: true},
		},
		fields: fieldSets(
			fields(3, 4),
			fields(),
			fields(),
			fields(),
			fields(3),
		),
		check: fields(1, 3, 4),
		want:  results(false, true, false),
	}, {
		desc: "implied required through embedding",
		tree: []CloseDef{
			0: {And: 0, NextEmbed: 1},
			1: {And: -1},
			2: {And: 3},
			3: {And: 2, IsDef: true},
		},
		fields: fieldSets(
			fields(3, 4),
			fields(),
			fields(),
			fields(3, 2),
		),
		check: fields(1, 2, 3, 4),
		want:  results(false, true, true, true),
	}, {
		desc: "implied required through recursive embedding",
		tree: []CloseDef{
			0: {And: 0, NextEmbed: 1},
			1: {And: -1},
			2: {And: 2, NextEmbed: 3},
			3: {And: -1},
			4: {And: 5},
			5: {And: 4, IsDef: true},
		},
		fields: fieldSets(
			fields(3, 4),
			fields(),
			fields(),
			fields(),
			fields(),
			fields(3, 2),
		),
		check: fields(1, 2, 3, 4),
		want:  results(false, true, true, true),
	}, {
		desc: "nil fieldSets",
		tree: []CloseDef{
			0: {And: 0, NextEmbed: 1},
			1: {And: -1},
			2: {And: 3},
			3: {And: 2, IsDef: true},
		},
		fields: fieldSets(
			nil,
			nil,
			fields(1),
			fields(2),
		),
		check: fields(1, 2, 3),
		want:  results(false, true, false),
	}, {
		desc: "required and remains closed with embedding",
		tree: []CloseDef{
			{And: 1},
			{And: 0, NextEmbed: 2, IsDef: true},
			{And: -1},
			{And: 3},
		},
		fields: fieldSets(
			fields(1),
			fields(),
			nil,
			fields(2),
		),
		check: fields(0, 1, 2, 3),
		want:  results(false, false, true, false),
	}}
	for i, tc := range testCases {
		t.Run(fmt.Sprint(i, "/", tc.desc), func(t *testing.T) {
			c := &acceptor{Canopy: tc.tree, isClosed: tc.isClosed}
			for _, f := range tc.fields {
				if f == nil {
					c.Fields = append(c.Fields, nil)
					continue
				}
				fs := &fieldSet{}
				c.Fields = append(c.Fields, fs)
				for _, id := range f {
					fs.fields = append(fs.fields, field{label: id})
				}
			}

			ctx := &adt.OpContext{}

			for i, f := range tc.check {
				got := c.verify(ctx, f)
				if got != tc.want[i] {
					t.Errorf("%d/%d: got %v; want %v", i, f, got, tc.want[i])
				}
			}
		})
	}
}

func TestCompact(t *testing.T) {
	testCases := []struct {
		desc      string
		tree      []CloseDef
		conjuncts []adt.ID
		out       string
	}{{
		desc:      "leave nil as is",
		tree:      nil,
		conjuncts: []adt.ID{0, 0},
		out:       "nil",
	}, {
		desc:      "simplest case",
		tree:      []CloseDef{{}},
		conjuncts: []adt.ID{0, 0},
		out:       "&( 0[])",
	}, {
		desc:      "required ands should not be removed",
		tree:      []CloseDef{{And: 1}, {And: 0, IsDef: true}},
		conjuncts: []adt.ID{0, 0},
		out:       "&( 0[] *1[])",
		// }, {
		// 	// TODO:
		// 	desc:      "required ands should not be removed",
		// 	tree:      []Node{{And: 1}, {And: 0, Required: false}},
		// 	conjuncts: []adt.ID{1},
		// 	out:       "&( 0[] 1[])",
	}, {
		desc:      "remove embedding",
		tree:      []CloseDef{{NextEmbed: 1}, {And: embedRoot}, {And: 2}},
		conjuncts: []adt.ID{0},
		out:       "&( 0[])",
	}, {
		desc:      "keep embedding if used",
		tree:      []CloseDef{{NextEmbed: 1}, {And: embedRoot}, {And: 2}},
		conjuncts: []adt.ID{0, 2},
		out:       "&( 0[&( 2[])])",
	}}
	for _, tc := range testCases {
		t.Run(tc.desc, func(t *testing.T) {
			c := &acceptor{Canopy: tc.tree}
			all := []adt.Conjunct{}
			for _, id := range tc.conjuncts {
				all = append(all, adt.Conjunct{CloseID: id})
			}

			c.Canopy = c.Compact(all)

			w := &strings.Builder{}
			// fmt.Fprintf(w, "%#v", c.Canopy)
			writeConjuncts(w, c)
			if got := w.String(); got != tc.out {
				t.Errorf("id: got %s; want %s", got, tc.out)
			}
		})
	}
}

func writeConjuncts(w *strings.Builder, c *acceptor) {
	if len(c.Canopy) == 0 {
		w.WriteString("nil")
		return
	}
	writeAnd(w, c, 0)
}

func writeAnd(w *strings.Builder, c *acceptor, id adt.ID) {
	w.WriteString("&(")
	c.visitAnd(id, func(id adt.ID, n CloseDef) bool {
		w.WriteString(" ")
		if n.IsDef || n.IsClosed {
			w.WriteString("*")
		}
		fmt.Fprintf(w, "%d[", id)
		c.visitEmbed(id, func(id adt.ID, n CloseDef) bool {
			writeAnd(w, c, id)
			return true
		})
		w.WriteString("]")
		return true
	})
	w.WriteString(")")
}