// ValueToListAndElemDesc ensures that v is a types.List of structs, pulls the types.StructDesc that describes the elements of v out of vr, and returns the List and related StructDesc.
func ValueToListAndElemDesc(v types.Value, vr types.ValueReader) (types.List, types.StructDesc) {
	d.Exp.True(types.ListKind == v.Type().Kind())

	t := v.Type().Desc.(types.CompoundDesc).ElemTypes[0]
	d.Exp.True(types.StructKind == t.Kind())
	return v.(types.List), t.Desc.(types.StructDesc)
}

func writeEncodedValue(w io.Writer, v types.Value) error {
	if v.Type().Kind() != types.BlobKind {
		return types.WriteEncodedValue(w, v)
	}
	write(w, []byte("Blob ("))
	write(w, []byte(humanize.Bytes(v.(types.Blob).Len())))
	return write(w, []byte(")"))
}

func writeEncodedValue(w io.Writer, v types.Value) {
	if v.Type().Kind() == types.BlobKind {
		w.Write([]byte("Blob ("))
		w.Write([]byte(humanize.Bytes(v.(types.Blob).Len())))
		w.Write([]byte(")"))
	} else {
		d.PanicIfError(types.WriteEncodedValue(w, v))
	}
}

func (suite *DatabaseSuite) TestReadWriteCache() {
	var v types.Value = types.Bool(true)
	suite.NotEqual(hash.Hash{}, suite.ds.WriteValue(v))
	r := suite.ds.WriteValue(v).TargetHash()
	commit := NewCommit(v, types.NewSet(), types.EmptyStruct)
	newDs, err := suite.ds.Commit("foo", commit)
	suite.NoError(err)
	suite.Equal(1, suite.cs.Writes-writesOnCommit)

	v = newDs.ReadValue(r)
	suite.True(v.Equals(types.Bool(true)))
}

// Summary prints a summary of the diff between two values to stdout.
func Summary(value1, value2 types.Value) {
	if datas.IsCommitType(value1.Type()) && datas.IsCommitType(value2.Type()) {
		fmt.Println("Comparing commit values")
		value1 = value1.(types.Struct).Get(datas.ValueField)
		value2 = value2.(types.Struct).Get(datas.ValueField)
	}

	var singular, plural string
	if value1.Type().Kind() == value2.Type().Kind() {
		switch value1.Type().Kind() {
		case types.StructKind:
			singular = "field"
			plural = "fields"
		case types.MapKind:
			singular = "entry"
			plural = "entries"
		default:
			singular = "value"
			plural = "values"
		}
	}
	// waitChan := make(chan struct{})
	ch := make(chan diffSummaryProgress)
	go func() {
		diffSummary(ch, value1, value2)
		close(ch)
	}()

	acc := diffSummaryProgress{}
	for p := range ch {
		acc.Adds += p.Adds
		acc.Removes += p.Removes
		acc.Changes += p.Changes
		acc.NewSize += p.NewSize
		acc.OldSize += p.OldSize
		if status.WillPrint() {
			formatStatus(acc, singular, plural)
		}
	}
	formatStatus(acc, singular, plural)
	status.Done()
}

func diff(w io.Writer, p types.Path, key, v1, v2 types.Value) {
	if !v1.Equals(v2) {
		if shouldDescend(v1, v2) {
			switch v1.Type().Kind() {
			case types.ListKind:
				diffLists(w, p, v1.(types.List), v2.(types.List))
			case types.MapKind:
				diffMaps(w, p, v1.(types.Map), v2.(types.Map))
			case types.SetKind:
				diffSets(w, p, v1.(types.Set), v2.(types.Set))
			case types.StructKind:
				diffStructs(w, p, v1.(types.Struct), v2.(types.Struct))
			default:
				panic("Unrecognized type in diff function")
			}
		} else {
			line(w, DEL, key, v1)
			line(w, ADD, key, v2)
		}
	}
}

func diffSummary(ch chan diffSummaryProgress, v1, v2 types.Value) {
	if !v1.Equals(v2) {
		if shouldDescend(v1, v2) {
			switch v1.Type().Kind() {
			case types.ListKind:
				diffSummaryList(ch, v1.(types.List), v2.(types.List))
			case types.MapKind:
				diffSummaryMap(ch, v1.(types.Map), v2.(types.Map))
			case types.SetKind:
				diffSummarySet(ch, v1.(types.Set), v2.(types.Set))
			case types.StructKind:
				diffSummaryStructs(ch, v1.(types.Struct), v2.(types.Struct))
			default:
				panic("Unrecognized type in diff function: " + v1.Type().Describe() + " and " + v2.Type().Describe())
			}
		} else {
			ch <- diffSummaryProgress{Adds: 1, Removes: 1, NewSize: 1, OldSize: 1}
		}
	}
}

func Diff(w io.Writer, v1, v2 types.Value) (err error) {
	dq := NewDiffQueue()
	di := diffInfo{path: types.NewPath().AddField("/"), v1: v1, v2: v2}
	dq.PushBack(di)

	err = d.Try(func() {
		for di, ok := dq.PopFront(); ok; di, ok = dq.PopFront() {
			p, key, v1, v2 := di.path, di.key, di.v1, di.v2

			v1.Type().Kind()
			if v1 == nil && v2 != nil {
				line(w, addPrefix, key, v2)
			}
			if v1 != nil && v2 == nil {
				line(w, subPrefix, key, v1)
			}
			if !v1.Equals(v2) {
				if !canCompare(v1, v2) {
					line(w, subPrefix, key, v1)
					line(w, addPrefix, key, v2)
				} else {
					switch v1.Type().Kind() {
					case types.ListKind:
						diffLists(dq, w, p, v1.(types.List), v2.(types.List))
					case types.MapKind:
						diffMaps(dq, w, p, v1.(types.Map), v2.(types.Map))
					case types.SetKind:
						diffSets(dq, w, p, v1.(types.Set), v2.(types.Set))
					case types.StructKind:
						diffStructs(dq, w, p, v1.(types.Struct), v2.(types.Struct))
					default:
						panic("Unrecognized type in diff function")
					}
				}
			}
		}
	})
	return
}

func canCompare(v1, v2 types.Value) bool {
	return !isPrimitiveOrRef(v1) && v1.Type().Kind() == v2.Type().Kind()
}

func isPrimitiveOrRef(v1 types.Value) bool {
	kind := v1.Type().Kind()
	return types.IsPrimitiveKind(kind) || kind == types.RefKind
}

func shouldDescend(v1, v2 types.Value) bool {
	kind := v1.Type().Kind()
	return !types.IsPrimitiveKind(kind) && kind == v2.Type().Kind() && kind != types.RefKind
}

func doTreeWalkP(v types.Value, vr types.ValueReader, cb SomeCallback, concurrency int) {
	rq := newRefQueue()
	f := newFailure()

	visited := map[hash.Hash]bool{}
	mu := sync.Mutex{}
	wg := sync.WaitGroup{}

	var processVal func(v types.Value, r *types.Ref)
	processVal = func(v types.Value, r *types.Ref) {
		if cb(v, r) {
			return
		}

		if sr, ok := v.(types.Ref); ok {
			wg.Add(1)
			rq.tail() <- sr
		} else {
			switch coll := v.(type) {
			case types.List:
				coll.IterAll(func(c types.Value, index uint64) {
					processVal(c, nil)
				})
			case types.Set:
				coll.IterAll(func(c types.Value) {
					processVal(c, nil)
				})
			case types.Map:
				coll.IterAll(func(k, c types.Value) {
					processVal(k, nil)
					processVal(c, nil)
				})
			default:
				for _, c := range v.ChildValues() {
					processVal(c, nil)
				}
			}
		}
	}

	processRef := func(r types.Ref) {
		defer wg.Done()

		mu.Lock()
		skip := visited[r.TargetHash()]
		visited[r.TargetHash()] = true
		mu.Unlock()

		if skip || f.didFail() {
			return
		}

		target := r.TargetHash()
		v := vr.ReadValue(target)
		if v == nil {
			f.fail(fmt.Errorf("Attempt to copy absent ref:%s", target.String()))
			return
		}
		processVal(v, &r)
	}

	iter := func() {
		for r := range rq.head() {
			processRef(r)
		}
	}

	for i := 0; i < concurrency; i++ {
		go iter()
	}

	processVal(v, nil)
	wg.Wait()

	rq.close()

	f.checkNotFailed()
}

// NewCommit creates a new commit object. The type of Commit is computed based on the type of the value, the type of the meta info as well as the type of the parents.
//
// For the first commit we get:
//
// ```
// struct Commit {
//   meta: M,
//   parents: Set<Ref<Cycle<0>>>,
//   value: T,
// }
// ```
//
// As long as we continue to commit values with type T and meta of type M that type stays the same.
//
// When we later do a commit with value of type U and meta of type N we get:
//
// ```
// struct Commit {
//   meta: N,
//   parents: Set<Ref<struct Commit {
//     meta: M | N,
//     parents: Set<Ref<Cycle<0>>>,
//     value: T | U
//   }>>,
//   value: U,
// }
// ```
//
// Similarly if we do a commit with a different type for the meta info.
//
// The new type gets combined as a union type for the value/meta of the inner commit struct.
func NewCommit(value types.Value, parents types.Set, meta types.Struct) types.Struct {
	t := makeCommitType(value.Type(), valueTypesFromParents(parents, ValueField), meta.Type(), valueTypesFromParents(parents, MetaField))
	return types.NewStructWithType(t, types.ValueSlice{meta, parents, value})
}