// Diff returns the differences of data.
// data.Equal is called repeatedly with 0<=i<n and 0<=j<m
975699
func Diff(n, m int, data Data) []Change {
	c := &context{data: data}
	if n > m {
		c.flags = make([]byte, n)
	} else {
		c.flags = make([]byte, m)
	}
	c.max = n + m + 1
	c.compare(0, 0, n, m)
	return c.result(n, m)
}
496447
func (s VarSet) Equal(vs VarSet) bool {
	if len(s.Diff(vs)) > 0 {
		return false
	}
	return len(vs.Diff(s)) == 0
}
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
}
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
}
1368695
func difference(sourceClnt, targetClnt Client, sourceURL, targetURL string, isRecursive, returnSimilar bool, dirOpt DirOpt) (diffCh chan diffMessage) {
	var (
		srcEOF, tgtEOF       bool
		srcOk, tgtOk         bool
		srcCtnt, tgtCtnt     *clientContent
		srcSuffix, tgtSuffix string
	)

	// Set default values for listing.
	isIncomplete := false // we will not compare any incomplete objects.
	srcCh := sourceClnt.List(isRecursive, isIncomplete, dirOpt)
	tgtCh := targetClnt.List(isRecursive, isIncomplete, dirOpt)

	diffCh = make(chan diffMessage, 1000)

	go func() {

		srcCtnt, srcOk = <-srcCh
		tgtCtnt, tgtOk = <-tgtCh

		defer close(diffCh)

		for {
			srcEOF = !srcOk
			tgtEOF = !tgtOk

			// No objects from source AND target: Finish
			if srcEOF && tgtEOF {
				break
			}

			if !srcEOF && srcCtnt.Err != nil {
				diffCh <- diffMessage{Error: srcCtnt.Err.Trace(sourceURL, targetURL)}
				return
			}

			if !tgtEOF && tgtCtnt.Err != nil {
				diffCh <- diffMessage{Error: tgtCtnt.Err.Trace(sourceURL, targetURL)}
				return
			}

			// If source doesn't have objects anymore, comparison becomes obvious
			if srcEOF {
				diffCh <- diffMessage{
					SecondURL:     tgtCtnt.URL.String(),
					Diff:          differInSecond,
					secondContent: tgtCtnt,
				}
				tgtCtnt, tgtOk = <-tgtCh
				continue
			}

			// The same for target
			if tgtEOF {
				diffCh <- diffMessage{
					FirstURL:     srcCtnt.URL.String(),
					Diff:         differInFirst,
					firstContent: srcCtnt,
				}
				srcCtnt, srcOk = <-srcCh
				continue
			}

			srcSuffix = strings.TrimPrefix(srcCtnt.URL.String(), sourceURL)
			tgtSuffix = strings.TrimPrefix(tgtCtnt.URL.String(), targetURL)

			current := urlJoinPath(targetURL, srcSuffix)
			expected := urlJoinPath(targetURL, tgtSuffix)

			if !utf8.ValidString(srcSuffix) {
				// Error. Keys must be valid UTF-8.
				diffCh <- diffMessage{Error: errInvalidSource(current).Trace()}
				srcCtnt, srcOk = <-srcCh
				continue
			}
			if !utf8.ValidString(tgtSuffix) {
				// Error. Keys must be valid UTF-8.
				diffCh <- diffMessage{Error: errInvalidTarget(expected).Trace()}
				tgtCtnt, tgtOk = <-tgtCh
				continue
			}

			// Normalize to avoid situations where multiple byte representations are possible.
			// e.g. 'ä' can be represented as precomposed U+00E4 (UTF-8 0xc3a4) or decomposed
			// U+0061 U+0308 (UTF-8 0x61cc88).
			normalizedCurrent := norm.NFC.String(current)
			normalizedExpected := norm.NFC.String(expected)

			if normalizedExpected > normalizedCurrent {
				diffCh <- diffMessage{
					FirstURL:     srcCtnt.URL.String(),
					Diff:         differInFirst,
					firstContent: srcCtnt,
				}
				srcCtnt, srcOk = <-srcCh
				continue
			}
			if normalizedExpected == normalizedCurrent {
				srcType, tgtType := srcCtnt.Type, tgtCtnt.Type
				srcSize, tgtSize := srcCtnt.Size, tgtCtnt.Size
				srcTime, tgtTime := srcCtnt.Time, tgtCtnt.Time
				if srcType.IsRegular() && !tgtType.IsRegular() ||
					!srcType.IsRegular() && tgtType.IsRegular() {
					// Type differs. Source is never a directory.
					diffCh <- diffMessage{
						FirstURL:      srcCtnt.URL.String(),
						SecondURL:     tgtCtnt.URL.String(),
						Diff:          differInType,
						firstContent:  srcCtnt,
						secondContent: tgtCtnt,
					}
					continue
				}
				if (srcType.IsRegular() && tgtType.IsRegular()) && srcSize != tgtSize {
					// Regular files differing in size.
					diffCh <- diffMessage{
						FirstURL:      srcCtnt.URL.String(),
						SecondURL:     tgtCtnt.URL.String(),
						Diff:          differInSize,
						firstContent:  srcCtnt,
						secondContent: tgtCtnt,
					}
				} else if srcTime.After(tgtTime) {
					// Regular files differing in timestamp.
					diffCh <- diffMessage{
						FirstURL:      srcCtnt.URL.String(),
						SecondURL:     tgtCtnt.URL.String(),
						Diff:          differInTime,
						firstContent:  srcCtnt,
						secondContent: tgtCtnt,
					}
				}
				// No differ
				if returnSimilar {
					diffCh <- diffMessage{
						FirstURL:      srcCtnt.URL.String(),
						SecondURL:     tgtCtnt.URL.String(),
						Diff:          differInNone,
						firstContent:  srcCtnt,
						secondContent: tgtCtnt,
					}
				}
				srcCtnt, srcOk = <-srcCh
				tgtCtnt, tgtOk = <-tgtCh
				continue
			}
			// Differ in second
			diffCh <- diffMessage{
				SecondURL:     tgtCtnt.URL.String(),
				Diff:          differInSecond,
				secondContent: tgtCtnt,
			}
			tgtCtnt, tgtOk = <-tgtCh
			continue
		}
	}()

	return diffCh
}
489654
func (rs RuleSet) Diff(other RuleSet) RuleSet {
	result := NewRuleSet()
	for i := range rs {
		if !other.Contains(rs[i]) {
			result.Add(rs[i])
		}
	}
	return result
}
1205336
func Compare(a, b interface{}) Diff {
	mapA := map[string]interface{}{}
	mapB := map[string]interface{}{}

	jsonA, _ := json.Marshal(a)
	jsonB, _ := json.Marshal(b)

	json.Unmarshal(jsonA, &mapA)
	json.Unmarshal(jsonB, &mapB)

	return compareStringMaps(mapA, mapB)
}
812429
func (a FileAnalyzer) Diff(image1, image2 pkgutil.Image) (util.Result, error) {
	diff, err := diffImageFiles(image1.FSPath, image2.FSPath)
	return &util.DirDiffResult{
		Image1:   image1.Source,
		Image2:   image2.Source,
		DiffType: "File",
		Diff:     diff,
	}, err
}
736271
func (vsdw *VerticalSplitDiffWorker) diff(ctx context.Context) error {
	vsdw.SetState(WorkerStateDiff)

	vsdw.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)
		vsdw.destinationSchemaDefinition, err = vsdw.wr.GetSchema(
			shortCtx, vsdw.destinationAlias, vsdw.shardInfo.SourceShards[0].Tables, nil /* excludeTables */, false /* includeViews */)
		cancel()
		if err != nil {
			vsdw.markAsWillFail(rec, err)
		}
		vsdw.wr.Logger().Infof("Got schema from destination %v", topoproto.TabletAliasString(vsdw.destinationAlias))
		wg.Done()
	}()
	wg.Add(1)
	go func() {
		var err error
		shortCtx, cancel := context.WithTimeout(ctx, *remoteActionsTimeout)
		vsdw.sourceSchemaDefinition, err = vsdw.wr.GetSchema(
			shortCtx, vsdw.sourceAlias, vsdw.shardInfo.SourceShards[0].Tables, nil /* excludeTables */, false /* includeViews */)
		cancel()
		if err != nil {
			vsdw.markAsWillFail(rec, err)
		}
		vsdw.wr.Logger().Infof("Got schema from source %v", topoproto.TabletAliasString(vsdw.sourceAlias))
		wg.Done()
	}()
	wg.Wait()
	if rec.HasErrors() {
		return rec.Error()
	}

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

	// run the diffs, 8 at a time
	vsdw.wr.Logger().Infof("Running the diffs...")
	sem := sync2.NewSemaphore(vsdw.parallelDiffsCount, 0)
	for _, tableDefinition := range vsdw.destinationSchemaDefinition.TableDefinitions {
		wg.Add(1)
		go func(tableDefinition *tabletmanagerdatapb.TableDefinition) {
			defer wg.Done()
			sem.Acquire()
			defer sem.Release()

			vsdw.wr.Logger().Infof("Starting the diff on table %v", tableDefinition.Name)
			sourceQueryResultReader, err := TableScan(ctx, vsdw.wr.Logger(), vsdw.wr.TopoServer(), vsdw.sourceAlias, tableDefinition)
			if err != nil {
				newErr := vterrors.Wrap(err, "TableScan(source) failed")
				vsdw.markAsWillFail(rec, newErr)
				vsdw.wr.Logger().Error(newErr)
				return
			}
			defer sourceQueryResultReader.Close(ctx)

			destinationQueryResultReader, err := TableScan(ctx, vsdw.wr.Logger(), vsdw.wr.TopoServer(), vsdw.destinationAlias, tableDefinition)
			if err != nil {
				newErr := vterrors.Wrap(err, "TableScan(destination) failed")
				vsdw.markAsWillFail(rec, newErr)
				vsdw.wr.Logger().Error(newErr)
				return
			}
			defer destinationQueryResultReader.Close(ctx)

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

			report, err := differ.Go(vsdw.wr.Logger())
			if err != nil {
				vsdw.wr.Logger().Errorf2(err, "Differ.Go failed")
			} else {
				if report.HasDifferences() {
					err := fmt.Errorf("table %v has differences: %v", tableDefinition.Name, report.String())
					vsdw.markAsWillFail(rec, err)
					vsdw.wr.Logger().Error(err)
				} else {
					vsdw.wr.Logger().Infof("Table %v checks out (%v rows processed, %v qps)", tableDefinition.Name, report.processedRows, report.processingQPS)
				}
			}
		}(tableDefinition)
	}
	wg.Wait()

	return rec.Error()
}
345845
func (t Term) Difference(args ...interface{}) Term {
	return constructMethodTerm(t, "Difference", p.Term_DIFFERENCE, args, map[string]interface{}{})
}
621755
func (s Int64) Difference(s2 Int64) Int64 {
	result := NewInt64()
	for key := range s {
		if !s2.Has(key) {
			result.Insert(key)
		}
	}
	return result
}
346194
func Compare(first, second []byte, separator string) (Diff, error) {
	fd, err := Parse(first, separator)
	if err != nil {
		return nil, err
	}
	sd, err := Parse(second, separator)
	if err != nil {
		return nil, err
	}
	d := &diff{
		first:  fd,
		second: sd,
	}
	err = d.compare()
	if err != nil {
		return nil, err
	}
	return d, nil
}
339619
func Diff(e, a interface{}) string {
	if e == nil || a == nil {
		return ""
	}

	t := reflect.TypeOf(e)
	k := t.Kind()

	if reflect.TypeOf(a) != t {
		return ""
	}

	if k == reflect.Ptr {
		t = t.Elem()
		k = t.Kind()
	}

	if k != reflect.Array && k != reflect.Map && k != reflect.Slice && k != reflect.Struct {
		return ""
	}

	es := dumpConf.Sdump(e)
	as := dumpConf.Sdump(a)

	diff, err := difflib.GetUnifiedDiffString(difflib.UnifiedDiff{
		A:        difflib.SplitLines(es),
		B:        difflib.SplitLines(as),
		Context:  1,
		FromFile: "Expected params",
		ToFile:   "Actual params",
	})

	if err != nil {
		panic(err)
	}

	return "\n\nDiff:\n" + diff
}
1332106
func (a *Driver) Diff(id string, idMappings *idtools.IDMappings, parent string, parentMappings *idtools.IDMappings, mountLabel string) (io.ReadCloser, error) {
	if !a.isParent(id, parent) {
		return a.naiveDiff.Diff(id, idMappings, parent, parentMappings, mountLabel)
	}

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

	// AUFS doesn't need the parent layer to produce a diff.
	return archive.TarWithOptions(path.Join(a.rootPath(), "diff", id), &archive.TarOptions{
		Compression:     archive.Uncompressed,
		ExcludePatterns: []string{archive.WhiteoutMetaPrefix + "*", "!" + archive.WhiteoutOpaqueDir},
		UIDMaps:         idMappings.UIDs(),
		GIDMaps:         idMappings.GIDs(),
	})
}
1072395
func (e Entries) Diff(cmp Entries) (Entries, Entries) {
	added := Entries{}
	for _, entry := range cmp {
		if !e.Contains(entry) {
			added = append(added, entry)
		}
	}

	removed := Entries{}
	for _, entry := range e {
		if !cmp.Contains(entry) {
			removed = append(removed, entry)
		}
	}

	return added, removed
}
877449
func (x Vector) Diff() Vector {
	n := len(x)

	if n < 2 {
		return Vector{NA}
	} else {
		d := make(Vector, n-1)

		i := 1
		for i < n {
			d[i-1] = x[i] - x[i-1]
			i++
		}
		return d
	}
}
68011
func getDiff(baseData, newData *simplejson.Json) (interface{}, diff.Diff, error) {
	leftBytes, err := baseData.Encode()
	if err != nil {
		return nil, nil, err
	}

	rightBytes, err := newData.Encode()
	if err != nil {
		return nil, nil, err
	}

	jsonDiff, err := diff.New().Compare(leftBytes, rightBytes)
	if err != nil {
		return nil, nil, err
	}

	if !jsonDiff.Modified() {
		return nil, nil, ErrNilDiff
	}

	left := make(map[string]interface{})
	err = json.Unmarshal(leftBytes, &left)
	if err != nil {
		return nil, nil, err
	}

	return left, jsonDiff, nil
}