func diffStructs(w io.Writer, p types.Path, v1, v2 types.Struct) {
	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 {
		fn := string(change.V.(types.String))
		switch change.ChangeType {
		case types.DiffChangeAdded:
			wroteHeader = writeHeader(w, wroteHeader, p)
			field(w, ADD, change.V, v2.Get(fn))
		case types.DiffChangeRemoved:
			wroteHeader = writeHeader(w, wroteHeader, p)
			field(w, DEL, change.V, v1.Get(fn))
		case types.DiffChangeModified:
			f1 := v1.Get(fn)
			f2 := v2.Get(fn)
			if shouldDescend(f1, f2) {
				diff(w, p.AddField(fn), types.String(fn), f1, f2)
			} else {
				wroteHeader = writeHeader(w, wroteHeader, p)
				field(w, DEL, change.V, f1)
				field(w, ADD, change.V, f2)
			}
		}
	}
	writeFooter(w, wroteHeader)
}

func descendsFrom(commit types.Struct, currentHeadRef types.Ref, vr types.ValueReader) bool {
	// BFS because the common case is that the ancestor is only a step or two away
	ancestors := commit.Get(ParentsField).(types.Set)
	for !ancestors.Has(currentHeadRef) {
		if ancestors.Empty() {
			return false
		}
		ancestors = getAncestors(ancestors, vr)
	}
	return true
}

func diffStructs(dq *diffQueue, w io.Writer, p types.Path, v1, v2 types.Struct) {
	changed := types.StructDiff(v1, v2)
	wroteHeader := false
	for _, field := range changed {
		f1 := v1.Get(field)
		f2 := v2.Get(field)
		if canCompare(f1, f2) {
			p1 := p.AddField(field)
			dq.PushBack(diffInfo{path: p1, key: types.String(field), v1: f1, v2: f2})
		} else {
			wroteHeader = writeHeader(w, wroteHeader, p)
			line(w, subPrefix, types.String(field), f1)
			line(w, addPrefix, types.String(field), f2)
		}
	}
}

func diffSummaryStructs(ch chan<- diffSummaryProgress, v1, v2 types.Struct) {
	size1 := uint64(v1.Type().Desc.(types.StructDesc).Len())
	size2 := uint64(v2.Type().Desc.(types.StructDesc).Len())
	diffSummaryValueChanged(ch, size1, size2, func(changeChan chan<- types.ValueChanged, stopChan <-chan struct{}) {
		v2.Diff(v1, changeChan, stopChan)
	})
}

func (fs *nomsFS) getNode(inode types.Struct, name string, parent *nNode) *nNode {
	// The parent has to be a directory.
	if parent != nil {
		d.Chk.Equal("Directory", nodeType(parent.inode))
	}

	np, ok := fs.nodes[inode.Hash()]
	if ok {
		d.Chk.Equal(np.parent, parent)
		d.Chk.Equal(np.name, name)
	} else {
		np = &nNode{
			nLock:  &sync.Mutex{},
			parent: parent,
			name:   name,
			key:    inode.Hash(),
			inode:  inode,
		}
		fs.nodes[np.key] = np
	}
	return np
}

func diffStructs(w io.Writer, p types.Path, v1, v2 types.Struct) error {
	return diffOrdered(w, p, field, func(cc chan<- types.ValueChanged, sc <-chan struct{}) {
		v2.Diff(v1, cc, sc)
	},
		func(k types.Value) types.Value { return k },
		func(k types.Value) types.Value { return v1.Get(string(k.(types.String))) },
		func(k types.Value) types.Value { return v2.Get(string(k.(types.String))) },
	)
}

func (fs *nomsFS) updateNode(np *nNode, inode types.Struct) {
	delete(fs.nodes, np.key)
	np.inode = inode
	np.key = inode.Hash()
	fs.nodes[np.key] = np
}

func updateMtime(attr types.Struct) types.Struct {
	now := time.Now()
	mtime := types.Number(float64(now.Unix()) + float64(now.Nanosecond())/1000000000)

	return attr.Set("mtime", mtime)
}

func (ds *databaseCommon) commit(datasetID string, commit types.Struct) error {
	d.PanicIfTrue(!IsCommitType(commit.Type()), "Can't commit a non-Commit struct to dataset %s", datasetID)
	return ds.doCommit(datasetID, commit)
}

// 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})
}