// diff phase: will log messages regarding the diff.
// - get the schema on all tablets
// - if some table schema mismatches, record them (use existing schema diff tools).
// - for each table in destination, run a diff pipeline.
336361
func (sdw *SplitDiffWorker) diff(ctx context.Context) error {
	sdw.SetState(WorkerStateDiff)

	sdw.wr.Logger().Infof("Gathering schema information...")
	wg := sync.WaitGroup{}
	rec := &concurrency.AllErrorRecorder{}
	wg.Add(1)
	go func() {
		var err error
		shortCtx, cancel := context.WithTimeout(ctx, *remoteActionsTimeout)
		sdw.destinationSchemaDefinition, err = sdw.wr.GetSchema(
			shortCtx, sdw.destinationAlias, nil /* tables */, sdw.excludeTables, false /* includeViews */)
		cancel()
		if err != nil {
			sdw.markAsWillFail(rec, err)
		}
		sdw.wr.Logger().Infof("Got schema from destination %v", sdw.destinationAlias)
		wg.Done()
	}()
	wg.Add(1)
	go func() {
		var err error
		shortCtx, cancel := context.WithTimeout(ctx, *remoteActionsTimeout)
		sdw.sourceSchemaDefinition, err = sdw.wr.GetSchema(
			shortCtx, sdw.sourceAlias, nil /* tables */, sdw.excludeTables, false /* includeViews */)
		cancel()
		if err != nil {
			sdw.markAsWillFail(rec, err)
		}
		sdw.wr.Logger().Infof("Got schema from source %v", sdw.sourceAlias)
		wg.Done()
	}()

	wg.Wait()
	if rec.HasErrors() {
		return rec.Error()
	}

	sdw.wr.Logger().Infof("Diffing the schema...")
	rec = &concurrency.AllErrorRecorder{}
	tmutils.DiffSchema("destination", sdw.destinationSchemaDefinition, "source", sdw.sourceSchemaDefinition, rec)
	if rec.HasErrors() {
		sdw.wr.Logger().Warningf("Different schemas: %v", rec.Error().Error())
	} else {
		sdw.wr.Logger().Infof("Schema match, good.")
	}

	// read the vschema if needed
	var keyspaceSchema *vindexes.KeyspaceSchema
	if *useV3ReshardingMode {
		kschema, err := sdw.wr.TopoServer().GetVSchema(ctx, sdw.keyspace)
		if err != nil {
			return vterrors.Wrapf(err, "cannot load VSchema for keyspace %v", sdw.keyspace)
		}
		if kschema == nil {
			return vterrors.Errorf(vtrpc.Code_FAILED_PRECONDITION, "no VSchema for keyspace %v", sdw.keyspace)
		}

		keyspaceSchema, err = vindexes.BuildKeyspaceSchema(kschema, sdw.keyspace)
		if err != nil {
			return vterrors.Wrapf(err, "cannot build vschema for keyspace %v", sdw.keyspace)
		}
	}

	// Compute the overlap keyrange. Later, we'll compare it with
	// source or destination keyrange. If it matches either,
	// we'll just ask for all the data. If the overlap is a subset,
	// we'll filter.
	overlap, err := key.KeyRangesOverlap(sdw.shardInfo.KeyRange, sdw.sourceShard.KeyRange)
	if err != nil {
		return vterrors.Wrap(err, "Source shard doesn't overlap with destination")
	}

	// run the diffs, 8 at a time
	sdw.wr.Logger().Infof("Running the diffs...")
	sem := sync2.NewSemaphore(sdw.parallelDiffsCount, 0)
	tableDefinitions := sdw.destinationSchemaDefinition.TableDefinitions

	// sort tables by size
	// if there are large deltas between table sizes then it's more efficient to start working on the large tables first
	sort.Slice(tableDefinitions, func(i, j int) bool { return tableDefinitions[i].DataLength > tableDefinitions[j].DataLength })

	// use a channel to make sure tables are diffed in order
	tableChan := make(chan *tabletmanagerdatapb.TableDefinition, len(tableDefinitions))
	for _, tableDefinition := range tableDefinitions {
		tableChan <- tableDefinition
	}

	// start as many goroutines as there are tables to diff
	for range tableDefinitions {
		wg.Add(1)
		go func() {
			defer wg.Done()
			// use the semaphore to limit the number of tables that are diffed in parallel
			sem.Acquire()
			defer sem.Release()

			// grab the table to process out of the channel
			tableDefinition := <-tableChan

			sdw.wr.Logger().Infof("Starting the diff on table %v", tableDefinition.Name)

			// On the source, see if we need a full scan
			// or a filtered scan.
			var sourceQueryResultReader *QueryResultReader
			if key.KeyRangeEqual(overlap, sdw.sourceShard.KeyRange) {
				sourceQueryResultReader, err = TableScan(ctx, sdw.wr.Logger(), sdw.wr.TopoServer(), sdw.sourceAlias, tableDefinition)
			} else {
				sourceQueryResultReader, err = TableScanByKeyRange(ctx, sdw.wr.Logger(), sdw.wr.TopoServer(), sdw.sourceAlias, tableDefinition, overlap, keyspaceSchema, sdw.keyspaceInfo.ShardingColumnName, sdw.keyspaceInfo.ShardingColumnType)
			}
			if err != nil {
				newErr := vterrors.Wrap(err, "TableScan(ByKeyRange?)(source) failed")
				sdw.markAsWillFail(rec, newErr)
				sdw.wr.Logger().Error(newErr)
				return
			}
			defer sourceQueryResultReader.Close(ctx)

			// On the destination, see if we need a full scan
			// or a filtered scan.
			var destinationQueryResultReader *QueryResultReader
			if key.KeyRangeEqual(overlap, sdw.shardInfo.KeyRange) {
				destinationQueryResultReader, err = TableScan(ctx, sdw.wr.Logger(), sdw.wr.TopoServer(), sdw.destinationAlias, tableDefinition)
			} else {
				destinationQueryResultReader, err = TableScanByKeyRange(ctx, sdw.wr.Logger(), sdw.wr.TopoServer(), sdw.destinationAlias, tableDefinition, overlap, keyspaceSchema, sdw.keyspaceInfo.ShardingColumnName, sdw.keyspaceInfo.ShardingColumnType)
			}
			if err != nil {
				newErr := vterrors.Wrap(err, "TableScan(ByKeyRange?)(destination) failed")
				sdw.markAsWillFail(rec, newErr)
				sdw.wr.Logger().Error(newErr)
				return
			}
			defer destinationQueryResultReader.Close(ctx)

			// Create the row differ.
			differ, err := NewRowDiffer(sourceQueryResultReader, destinationQueryResultReader, tableDefinition)
			if err != nil {
				newErr := vterrors.Wrap(err, "NewRowDiffer() failed")
				sdw.markAsWillFail(rec, newErr)
				sdw.wr.Logger().Error(newErr)
				return
			}

			// And run the diff.
			report, err := differ.Go(sdw.wr.Logger())
			if err != nil {
				newErr := vterrors.Wrapf(err, "Differ.Go failed")
				sdw.markAsWillFail(rec, newErr)
				sdw.wr.Logger().Error(newErr)
			} else {
				if report.HasDifferences() {
					err := vterrors.Errorf(vtrpc.Code_FAILED_PRECONDITION, "table %v has differences: %v", tableDefinition.Name, report.String())
					sdw.markAsWillFail(rec, err)
					sdw.wr.Logger().Warningf(err.Error())
				} else {
					sdw.wr.Logger().Infof("Table %v checks out (%v rows processed, %v qps)", tableDefinition.Name, report.processedRows, report.processingQPS)
				}
			}
		}()
	}

	// grab the table to process out of the channel
	wg.Wait()

	return rec.Error()
}
938055
func (v Values) Diff(other Values) Values {
	diff := Values{}
	for key, value := range v {
		if !assert.ObjectsAreEqual(value, other[key]) {
			diff[key] = value
		}
	}
	return diff
}
1139040
func (s *ChangesService) GetDiff(changeID, revisionID, fileID string, opt *DiffOptions) (*DiffInfo, *Response, error) {
	u := fmt.Sprintf("changes/%s/revisions/%s/files/%s/diff", changeID, revisionID, url.PathEscape(fileID))

	u, err := addOptions(u, opt)
	if err != nil {
		return nil, nil, err
	}

	req, err := s.client.NewRequest("GET", u, nil)
	if err != nil {
		return nil, nil, err
	}

	v := new(DiffInfo)
	resp, err := s.client.Do(req, v)
	if err != nil {
		return nil, resp, err
	}

	return v, resp, err
}
275470
func (d *Driver) Diff(id string, idMappings *idtools.IDMappings, parent string, parentMappings *idtools.IDMappings, mountLabel string) (io.ReadCloser, error) {
	if d.useNaiveDiff() || !d.isParent(id, parent) {
		return d.naiveDiff.Diff(id, idMappings, parent, parentMappings, mountLabel)
	}

	if idMappings == nil {
		idMappings = &idtools.IDMappings{}
	}

	lowerDirs, err := d.getLowerDirs(id)
	if err != nil {
		return nil, err
	}

	diffPath := d.getDiffPath(id)
	logrus.Debugf("Tar with options on %s", diffPath)
	return archive.TarWithOptions(diffPath, &archive.TarOptions{
		Compression:    archive.Uncompressed,
		UIDMaps:        idMappings.UIDs(),
		GIDMaps:        idMappings.GIDs(),
		WhiteoutFormat: d.getWhiteoutFormat(),
		WhiteoutData:   lowerDirs,
	})
}
432895
func (from *Tree) Diff(to *Tree) (Changes, error) {
	return DiffTree(from, to)
}
1218056
func (m *Meta) GetSchemaDiff(schemaVersion int64) (*model.SchemaDiff, error) {
	diffKey := m.schemaDiffKey(schemaVersion)
	startTime := time.Now()
	data, err := m.txn.Get(diffKey)
	metrics.MetaHistogram.WithLabelValues(metrics.GetSchemaDiff, metrics.RetLabel(err)).Observe(time.Since(startTime).Seconds())
	if err != nil || len(data) == 0 {
		return nil, errors.Trace(err)
	}
	diff := &model.SchemaDiff{}
	err = json.Unmarshal(data, diff)
	return diff, errors.Trace(err)
}
510587
func (d config) Diff(c Config) ([]structs.Field, error) {
	var fields []structs.Field

	currFields := structs.Fields(d.Data())
	newFields := structs.Fields(c.Data())

	var found bool
	for _, currField := range currFields {
		found = false
		for _, newField := range newFields {
			if reflect.DeepEqual(currField.Name(), newField.Name()) {
				found = true
			}
		}
		if !found {
			fields = append(fields, *currField)
		}
	}
	return fields, nil
}
75786
func ctySequenceDiff(old, new []cty.Value) []*plans.Change {
	var ret []*plans.Change
	lcs := objchange.LongestCommonSubsequence(old, new)
	var oldI, newI, lcsI int
	for oldI < len(old) || newI < len(new) || lcsI < len(lcs) {
		for oldI < len(old) && (lcsI >= len(lcs) || !old[oldI].RawEquals(lcs[lcsI])) {
			isObjectDiff := old[oldI].Type().IsObjectType() && (newI >= len(new) || new[newI].Type().IsObjectType())
			if isObjectDiff && newI < len(new) {
				ret = append(ret, &plans.Change{
					Action: plans.Update,
					Before: old[oldI],
					After:  new[newI],
				})
				oldI++
				newI++ // we also consume the next "new" in this case
				continue
			}

			ret = append(ret, &plans.Change{
				Action: plans.Delete,
				Before: old[oldI],
				After:  cty.NullVal(old[oldI].Type()),
			})
			oldI++
		}
		for newI < len(new) && (lcsI >= len(lcs) || !new[newI].RawEquals(lcs[lcsI])) {
			ret = append(ret, &plans.Change{
				Action: plans.Create,
				Before: cty.NullVal(new[newI].Type()),
				After:  new[newI],
			})
			newI++
		}
		if lcsI < len(lcs) {
			ret = append(ret, &plans.Change{
				Action: plans.NoOp,
				Before: lcs[lcsI],
				After:  lcs[lcsI],
			})

			// All of our indexes advance together now, since the line
			// is common to all three sequences.
			lcsI++
			oldI++
			newI++
		}
	}
	return ret
}
1057589
func (p *Provider) Diff(
	info *terraform.InstanceInfo,
	s *terraform.InstanceState,
	c *terraform.ResourceConfig) (*terraform.InstanceDiff, error) {
	r, ok := p.ResourcesMap[info.Type]
	if !ok {
		return nil, fmt.Errorf("unknown resource type: %s", info.Type)
	}

	return r.Diff(s, c, p.meta)
}
414486
func (old *Manifest_Directory) Diff(new *Manifest_Directory) *ManifestDiff_Directory {
	ret := &ManifestDiff_Directory{}

	ret.Overall = zeroCmpTwo(old, new, func() ManifestDiff_Stat {
		var dirChanged modifiedTracker

		if ret.GitCheckout = old.GitCheckout.Diff(new.GitCheckout); ret.GitCheckout != nil {
			dirChanged.add(ret.GitCheckout.Overall)
		}

		ret.CipdServerHost = dirChanged.add(zeroCmpTwo(old.CipdServerHost, new.CipdServerHost, nil))
		if ret.CipdServerHost == ManifestDiff_EQUAL && new.CipdServerHost != "" {
			cipdPackages := map[string]ManifestDiff_Stat{}

			for name, pkg := range old.CipdPackage {
				cipdPackages[name] = dirChanged.add(pkg.Diff(new.CipdPackage[name]))
			}
			for name, pkg := range new.CipdPackage {
				if _, ok := cipdPackages[name]; !ok {
					cipdPackages[name] = dirChanged.add(old.CipdPackage[name].Diff(pkg))
				}
			}

			if len(cipdPackages) > 0 {
				ret.CipdPackage = cipdPackages
			}
		}

		ret.IsolatedServerHost = dirChanged.add(zeroCmpTwo(old.IsolatedServerHost, new.IsolatedServerHost, nil))
		ret.Isolated = dirChanged.add(IsolatedDiff(old.Isolated, new.Isolated))

		return dirChanged.status()
	})

	return ret
}
880461
func DiffDelta(src, tgt []byte) []byte {
	return diffDelta(new(deltaIndex), src, tgt)
}
1295974
func (r *RequestedDevice) Diff(other *RequestedDevice, contextual bool) *ObjectDiff {
	diff := &ObjectDiff{Type: DiffTypeNone, Name: "Device"}
	var oldPrimitiveFlat, newPrimitiveFlat map[string]string

	if reflect.DeepEqual(r, other) {
		return nil
	} else if r == nil {
		diff.Type = DiffTypeAdded
		newPrimitiveFlat = flatmap.Flatten(other, nil, true)
	} else if other == nil {
		diff.Type = DiffTypeDeleted
		oldPrimitiveFlat = flatmap.Flatten(r, nil, true)
	} else {
		diff.Type = DiffTypeEdited
		oldPrimitiveFlat = flatmap.Flatten(r, nil, true)
		newPrimitiveFlat = flatmap.Flatten(other, nil, true)
	}

	// Diff the primitive fields.
	diff.Fields = fieldDiffs(oldPrimitiveFlat, newPrimitiveFlat, contextual)

	return diff
}
212335
func (j *Job) Diff(other *Job, contextual bool) (*JobDiff, error) {
	// COMPAT: Remove "Update" in 0.7.0. Update pushed down to task groups
	// in 0.6.0
	diff := &JobDiff{Type: DiffTypeNone}
	var oldPrimitiveFlat, newPrimitiveFlat map[string]string
	filter := []string{"ID", "Status", "StatusDescription", "Version", "Stable", "CreateIndex",
		"ModifyIndex", "JobModifyIndex", "Update", "SubmitTime"}

	if j == nil && other == nil {
		return diff, nil
	} else if j == nil {
		j = &Job{}
		diff.Type = DiffTypeAdded
		newPrimitiveFlat = flatmap.Flatten(other, filter, true)
		diff.ID = other.ID
	} else if other == nil {
		other = &Job{}
		diff.Type = DiffTypeDeleted
		oldPrimitiveFlat = flatmap.Flatten(j, filter, true)
		diff.ID = j.ID
	} else {
		if j.ID != other.ID {
			return nil, fmt.Errorf("can not diff jobs with different IDs: %q and %q", j.ID, other.ID)
		}

		oldPrimitiveFlat = flatmap.Flatten(j, filter, true)
		newPrimitiveFlat = flatmap.Flatten(other, filter, true)
		diff.ID = other.ID
	}

	// Diff the primitive fields.
	diff.Fields = fieldDiffs(oldPrimitiveFlat, newPrimitiveFlat, false)

	// Datacenters diff
	if setDiff := stringSetDiff(j.Datacenters, other.Datacenters, "Datacenters", contextual); setDiff != nil && setDiff.Type != DiffTypeNone {
		diff.Objects = append(diff.Objects, setDiff)
	}

	// Constraints diff
	conDiff := primitiveObjectSetDiff(
		interfaceSlice(j.Constraints),
		interfaceSlice(other.Constraints),
		[]string{"str"},
		"Constraint",
		contextual)
	if conDiff != nil {
		diff.Objects = append(diff.Objects, conDiff...)
	}

	// Affinities diff
	affinitiesDiff := primitiveObjectSetDiff(
		interfaceSlice(j.Affinities),
		interfaceSlice(other.Affinities),
		[]string{"str"},
		"Affinity",
		contextual)
	if affinitiesDiff != nil {
		diff.Objects = append(diff.Objects, affinitiesDiff...)
	}

	// Task groups diff
	tgs, err := taskGroupDiffs(j.TaskGroups, other.TaskGroups, contextual)
	if err != nil {
		return nil, err
	}
	diff.TaskGroups = tgs

	// Periodic diff
	if pDiff := primitiveObjectDiff(j.Periodic, other.Periodic, nil, "Periodic", contextual); pDiff != nil {
		diff.Objects = append(diff.Objects, pDiff)
	}

	// ParameterizedJob diff
	if cDiff := parameterizedJobDiff(j.ParameterizedJob, other.ParameterizedJob, contextual); cDiff != nil {
		diff.Objects = append(diff.Objects, cDiff)
	}

	// Check to see if there is a diff. We don't use reflect because we are
	// filtering quite a few fields that will change on each diff.
	if diff.Type == DiffTypeNone {
		for _, fd := range diff.Fields {
			if fd.Type != DiffTypeNone {
				diff.Type = DiffTypeEdited
				break
			}
		}
	}

	if diff.Type == DiffTypeNone {
		for _, od := range diff.Objects {
			if od.Type != DiffTypeNone {
				diff.Type = DiffTypeEdited
				break
			}
		}
	}

	if diff.Type == DiffTypeNone {
		for _, tg := range diff.TaskGroups {
			if tg.Type != DiffTypeNone {
				diff.Type = DiffTypeEdited
				break
			}
		}
	}

	return diff, nil
}
1163009
func (args Arguments) Diff(objects []interface{}) (string, int) {
	//TODO: could return string as error and nil for No difference

	var output = "\n"
	var differences int

	var maxArgCount = len(args)
	if len(objects) > maxArgCount {
		maxArgCount = len(objects)
	}

	for i := 0; i < maxArgCount; i++ {
		var actual, expected interface{}
		var actualFmt, expectedFmt string

		if len(objects) <= i {
			actual = "(Missing)"
			actualFmt = "(Missing)"
		} else {
			actual = objects[i]
			actualFmt = fmt.Sprintf("(%[1]T=%[1]v)", actual)
		}

		if len(args) <= i {
			expected = "(Missing)"
			expectedFmt = "(Missing)"
		} else {
			expected = args[i]
			expectedFmt = fmt.Sprintf("(%[1]T=%[1]v)", expected)
		}

		if matcher, ok := expected.(argumentMatcher); ok {
			if matcher.Matches(actual) {
				output = fmt.Sprintf("%s\t%d: PASS:  %s matched by %s\n", output, i, actualFmt, matcher)
			} else {
				differences++
				output = fmt.Sprintf("%s\t%d: FAIL:  %s not matched by %s\n", output, i, actualFmt, matcher)
			}
		} else if reflect.TypeOf(expected) == reflect.TypeOf((*AnythingOfTypeArgument)(nil)).Elem() {

			// type checking
			if reflect.TypeOf(actual).Name() != string(expected.(AnythingOfTypeArgument)) && reflect.TypeOf(actual).String() != string(expected.(AnythingOfTypeArgument)) {
				// not match
				differences++
				output = fmt.Sprintf("%s\t%d: FAIL:  type %s != type %s - %s\n", output, i, expected, reflect.TypeOf(actual).Name(), actualFmt)
			}

		} else {

			// normal checking

			if assert.ObjectsAreEqual(expected, Anything) || assert.ObjectsAreEqual(actual, Anything) || assert.ObjectsAreEqual(actual, expected) {
				// match
				output = fmt.Sprintf("%s\t%d: PASS:  %s == %s\n", output, i, actualFmt, expectedFmt)
			} else {
				// not match
				differences++
				output = fmt.Sprintf("%s\t%d: FAIL:  %s != %s\n", output, i, actualFmt, expectedFmt)
			}
		}

	}

	if differences == 0 {
		return "No differences.", differences
	}

	return output, differences

}
866227
func (gdw *NaiveDiffDriver) Diff(id, parent string) (arch io.ReadCloser, err error) {
	startTime := time.Now()
	driver := gdw.ProtoDriver

	layerRootFs, err := driver.Get(id, "")
	if err != nil {
		return nil, err
	}
	layerFs := layerRootFs.Path()

	defer func() {
		if err != nil {
			driver.Put(id)
		}
	}()

	if parent == "" {
		archive, err := archive.Tar(layerFs, archive.Uncompressed)
		if err != nil {
			return nil, err
		}
		return ioutils.NewReadCloserWrapper(archive, func() error {
			err := archive.Close()
			driver.Put(id)
			return err
		}), nil
	}

	parentRootFs, err := driver.Get(parent, "")
	if err != nil {
		return nil, err
	}
	defer driver.Put(parent)

	parentFs := parentRootFs.Path()

	changes, err := archive.ChangesDirs(layerFs, parentFs)
	if err != nil {
		return nil, err
	}

	archive, err := archive.ExportChanges(layerFs, changes, gdw.uidMaps, gdw.gidMaps)
	if err != nil {
		return nil, err
	}

	return ioutils.NewReadCloserWrapper(archive, func() error {
		err := archive.Close()
		driver.Put(id)

		// NaiveDiffDriver compares file metadata with parent layers. Parent layers
		// are extracted from tar's with full second precision on modified time.
		// We need this hack here to make sure calls within same second receive
		// correct result.
		time.Sleep(time.Until(startTime.Truncate(time.Second).Add(time.Second)))
		return err
	}), nil
}
867993
func Diff(config, live *unstructured.Unstructured, normalizer Normalizer) *DiffResult {
	if config != nil {
		config = stripTypeInformation(config)
		Normalize(config, normalizer)
	}
	if live != nil {
		live = stripTypeInformation(live)
		Normalize(live, normalizer)
	}
	orig := GetLastAppliedConfigAnnotation(live)
	if orig != nil && config != nil {
		Normalize(orig, normalizer)
		dr, err := ThreeWayDiff(orig, config, live)
		if err == nil {
			return dr
		}
		log.Debugf("three-way diff calculation failed: %v. Falling back to two-way diff", err)
	}
	return TwoWayDiff(config, live)
}
845288
func DiffFormatWrite(ctx formatter.Context, changes []container.ContainerChangeResponseItem) error {

	render := func(format func(subContext formatter.SubContext) error) error {
		for _, change := range changes {
			if err := format(&diffContext{c: change}); err != nil {
				return err
			}
		}
		return nil
	}
	return ctx.Write(newDiffContext(), render)
}