func commitRefsFromSet(set types.Set) []types.Ref {
	res := []types.Ref{}
	set.IterAll(func(v types.Value) {
		res = append(res, v.(types.Ref))
	})
	return res
}

func diffSets(w io.Writer, p types.Path, v1, v2 types.Set) {
	changeChan := make(chan types.ValueChanged)
	stopChan := make(chan struct{}, 1) // buffer size of 1, so this won't block if diff already finished

	defer stop(stopChan)
	go func() {
		v2.Diff(v1, changeChan, stopChan)
		close(changeChan)
	}()

	wroteHeader := false

	for change := range changeChan {
		wroteHeader = writeHeader(w, wroteHeader, p)
		switch change.ChangeType {
		case types.DiffChangeAdded:
			line(w, ADD, nil, change.V)
		case types.DiffChangeRemoved:
			line(w, DEL, nil, change.V)
		default:
			panic("unknown change type")
		}
	}

	writeFooter(w, wroteHeader)
}

func diffSets(w io.Writer, p types.Path, v1, v2 types.Set) error {
	return diffOrdered(w, p, line, func(cc chan<- types.ValueChanged, sc <-chan struct{}) {
		v2.DiffLeftRight(v1, cc, sc)
	},
		func(k types.Value) types.Value { return nil },
		func(k types.Value) types.Value { return k },
		func(k types.Value) types.Value { return k },
	)
}

func getAncestors(commits types.Set, vr types.ValueReader) types.Set {
	ancestors := types.NewSet()
	commits.IterAll(func(v types.Value) {
		r := v.(types.Ref)
		c := r.TargetValue(vr).(types.Struct)
		next := []types.Value{}
		c.Get(ParentsField).(types.Set).IterAll(func(v types.Value) {
			next = append(next, v)
		})
		ancestors = ancestors.Insert(next...)
	})
	return ancestors
}

func valueTypesFromParents(parents types.Set, fieldName string) []*types.Type {
	elemType := getSetElementType(parents.Type())
	switch elemType.Kind() {
	case types.UnionKind:
		ts := []*types.Type{}
		for _, rt := range elemType.Desc.(types.CompoundDesc).ElemTypes {
			ts = append(ts, fieldTypeFromRefOfCommit(rt, fieldName))
		}
		return ts
	default:
		return []*types.Type{fieldTypeFromRefOfCommit(elemType, fieldName)}
	}
}

func diffSets(dq *diffQueue, w io.Writer, p types.Path, v1, v2 types.Set) {
	wroteHeader := false
	added, removed := v2.Diff(v1)
	if len(added) == 1 && len(removed) == 1 && canCompare(added[0], removed[0]) {
		p1 := p.AddField(added[0].Hash().String())
		dq.PushBack(diffInfo{path: p1, key: types.String(""), v1: removed[0], v2: added[0]})
	} else {
		for _, value := range removed {
			wroteHeader = writeHeader(w, wroteHeader, p)
			line(w, subPrefix, nil, value)
		}
		for _, value := range added {
			wroteHeader = writeHeader(w, wroteHeader, p)
			line(w, addPrefix, nil, value)
		}
	}
	writeFooter(w, wroteHeader)
	return
}

func diffSummarySet(ch chan<- diffSummaryProgress, v1, v2 types.Set) {
	diffSummaryValueChanged(ch, v1.Len(), v2.Len(), func(changeChan chan<- types.ValueChanged, stopChan <-chan struct{}) {
		v2.Diff(v1, changeChan, stopChan)
	})
}