// compute is the unexported helper for Diff that returns the results of
// diffing left and right.
320101
func compute(seq1, seq2 []string) (diff []DiffRecord) {
	matrix := longestCommonSubsequenceMatrix(seq1, seq2)
	i, j := len(seq1), len(seq2)
	for i > 0 || j > 0 {
		if i > 0 && matrix[i][j] == matrix[i-1][j] {
			diff = append(diff, DiffRecord{seq1[len(seq1)-i], LeftOnly})
			i--
		} else if j > 0 && matrix[i][j] == matrix[i][j-1] {
			diff = append(diff, DiffRecord{seq2[len(seq2)-j], RightOnly})
			j--
		} else if i > 0 && j > 0 {
			diff = append(diff, DiffRecord{seq1[len(seq1)-i], Common})
			i--
			j--
		}
	}
	return
}
558233
func (msdw *MultiSplitDiffWorker) diff(ctx context.Context) error {
	msdw.SetState(WorkerStateDiff)

	destinationSchemaDefinitions, sourceSchemaDefinition, err := msdw.gatherSchemaInfo(ctx)
	if err != nil {
		return err
	}
	err = msdw.diffSchemaInformation(ctx, destinationSchemaDefinitions, sourceSchemaDefinition)
	if err != nil {
		return err
	}

	// read the vschema if needed
	var keyspaceSchema *vindexes.KeyspaceSchema
	if *useV3ReshardingMode {
		keyspaceSchema, err = msdw.loadVSchema(ctx)
		if err != nil {
			return err
		}
	}

	msdw.wr.Logger().Infof("running the diffs...")
	tableDefinitions := sourceSchemaDefinition.TableDefinitions
	rec := &concurrency.AllErrorRecorder{}

	// 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 })
	tableChan := make(chan *tabletmanagerdatapb.TableDefinition, len(tableDefinitions))
	for _, tableDefinition := range tableDefinitions {
		tableChan <- tableDefinition
	}
	close(tableChan)

	consumers := sync.WaitGroup{}
	// start as many goroutines we want parallel diffs running
	for i := 0; i < msdw.parallelDiffsCount; i++ {
		scanners := msdw.scanners[i]
		if scanners.sourceScanner == nil || scanners.destinationScanner == nil {
			return vterrors.Errorf(vtrpc.Code_INTERNAL, "should not be nil [%v] OR [%v]", scanners.sourceScanner, scanners.destinationScanner)
		}

		consumers.Add(1)
		go msdw.tableDiffingConsumer(ctx, &consumers, tableChan, rec, keyspaceSchema, scanners.sourceScanner, scanners.destinationScanner)
	}

	// wait for all consumers to wrap up their work
	consumers.Wait()

	return rec.Error()
}
916420
func (c *CuckooFilter) computeHash(data []byte) []byte {
	c.hash.Write(data)
	hash := c.hash.Sum(nil)
	c.hash.Reset()
	return hash
}
811624
func computeBackoff() time.Duration {
	globalBackoffMutex.Lock()
	defer globalBackoffMutex.Unlock()

	v := globalBackoff
	v = v + v
	if v > maxGlobalBackoff {
		v = maxGlobalBackoff
	}
	globalBackoff = v

	return v
}
1257065
func (d *MyDecimal) Compare(to *MyDecimal) int {
	if d.negative == to.negative {
		cmp, _ := doSub(d, to, nil)
		return cmp
	}
	if d.negative {
		return -1
	}
	return 1
}
281237
func (h *HistogramDiffer) Solve() *DiffSolution {
	s := &DiffSolution{}
	prevRegion := &matchRegion{aStart: 0, aEnd: 0, bStart: 0, bEnd: 0}
	regions := h.solveRange(0, len(h.a), 0, len(h.b))
	for _, region := range regions {
		// compute intra-region differences
		a := h.a[prevRegion.aEnd:region.aStart]
		b := h.b[prevRegion.bEnd:region.bStart]
		s.addSolution(NewSequenceDiffer(a, b).Solve())

		// copy match region
		for _, l := range h.a[region.aStart:region.aEnd] {
			s.addLine(l, l, LineFromBoth)
		}

		// update for loop
		prevRegion = region
	}

	// compute diff for final unmatched section
	a := h.a[prevRegion.aEnd:len(h.a)]
	b := h.b[prevRegion.bEnd:len(h.b)]
	s.addSolution(NewSequenceDiffer(a, b).Solve())
	s.PostProcess()
	return s
}
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
}
742044
func (as ArraySpec) Div(val Input) Input {
	return as.proc(func(i Input) Input {
		return i.Div(val)
	})
}
949696
func computeTotal(prof *profile.Profile, value, meanDiv func(v []int64) int64) int64 {
	var div, total, diffDiv, diffTotal int64
	for _, sample := range prof.Sample {
		var d, v int64
		v = value(sample.Value)
		if meanDiv != nil {
			d = meanDiv(sample.Value)
		}
		if v < 0 {
			v = -v
		}
		total += v
		div += d
		if sample.DiffBaseSample() {
			diffTotal += v
			diffDiv += d
		}
	}
	if diffTotal > 0 {
		total = diffTotal
		div = diffDiv
	}
	if div != 0 {
		return total / div
	}
	return total
}
241059
func (rd *RowDiffer2) Diff() (DiffReport, error) {
	var dr DiffReport
	var err error

	dr.startingTime = time.Now()
	defer dr.ComputeQPS()

	fields := rd.left.Fields()
	var left []sqltypes.Value
	var right []sqltypes.Value
	advanceLeft := true
	advanceRight := true
	for {
		if advanceLeft {
			if left, err = rd.left.Next(); err != nil {
				return dr, err
			}
			advanceLeft = false
		}
		if advanceRight {
			if right, err = rd.right.Next(); err != nil {
				return dr, err
			}
			advanceRight = false
		}
		dr.processedRows++
		if left == nil && right == nil {
			// No more rows from either side. We're done.
			break
		}
		if left == nil {
			// No more rows on the left side.
			// We know we have at least one row on the right side left.
			// Delete the row from the destination.
			if err := rd.reconcileRow(right, DiffExtraneous); err != nil {
				return dr, err
			}
			dr.extraRowsRight++
			advanceRight = true
			continue
		}
		if right == nil {
			// No more rows on the right side.
			// We know we have at least one row on the left side left.
			// Add the row on the destination.
			if err := rd.reconcileRow(left, DiffMissing); err != nil {
				return dr, err
			}
			dr.extraRowsLeft++
			advanceLeft = true
			continue
		}

		// we have both left and right, compare
		f := RowsEqual(left, right)
		if f == -1 {
			// rows are the same, next
			dr.matchingRows++
			advanceLeft = true
			advanceRight = true
			rd.skipRow()
			continue
		}

		if f >= rd.pkFieldCount {
			// rows have the same primary key, only content is different
			dr.mismatchedRows++
			advanceLeft = true
			advanceRight = true
			// Update the row on the destination.
			if err := rd.updateRow(left, right, DiffNotEqual); err != nil {
				return dr, err
			}
			continue
		}

		// have to find the 'smallest' row and advance it
		c, err := CompareRows(fields, rd.pkFieldCount, left, right)
		if err != nil {
			return dr, err
		}
		if c < 0 {
			dr.extraRowsLeft++
			advanceLeft = true
			// Add the row on the destination.
			if err := rd.reconcileRow(left, DiffMissing); err != nil {
				return dr, err
			}
			continue
		} else if c > 0 {
			dr.extraRowsRight++
			advanceRight = true
			// Delete the row from the destination.
			if err := rd.reconcileRow(right, DiffExtraneous); err != nil {
				return dr, err
			}
			continue
		}

		// Values of the primary key columns were not binary equal but their parsed
		// values are.
		// This happens when the raw values returned by MySQL were different but
		// they became equal after we parsed them into ints/floats
		// (due to leading/trailing zeros, for example). So this can happen if MySQL
		// is inconsistent in how it prints a given number.
		dr.mismatchedRows++
		advanceLeft = true
		advanceRight = true
		// Update the row on the destination.
		if err := rd.updateRow(left, right, DiffNotEqual); err != nil {
			return dr, err
		}
	}

	// Flush all aggregators in case they have buffered queries left.
	for i := range rd.aggregators {
		for _, aggregator := range rd.aggregators[i] {
			if err := aggregator.Flush(); err != nil {
				return dr, err
			}
		}
	}

	return dr, nil
}
913750
func ComputeBitXor(sc *variable.StatementContext, a, b Datum) (d Datum, err error) {
	aKind, bKind := a.Kind(), b.Kind()
	if (aKind == KindInt64 || aKind == KindUint64) && (bKind == KindInt64 || bKind == KindUint64) {
		d.SetUint64(a.GetUint64() ^ b.GetUint64())
		return
	}
	// If either is not integer, we round the operands and then use uint64 to calculate.
	x, err := convertNonInt2RoundUint64(sc, a)
	if err != nil {
		return d, errors.Trace(err)
	}

	y, err := convertNonInt2RoundUint64(sc, b)
	if err != nil {
		return d, errors.Trace(err)
	}

	d.SetUint64(x ^ y)
	return d, nil
}
671596
func (a *allocReconciler) Compute() *reconcileResults {
	// Create the allocation matrix
	m := newAllocMatrix(a.job, a.existingAllocs)

	// Handle stopping unneeded deployments
	a.cancelDeployments()

	// If we are just stopping a job we do not need to do anything more than
	// stopping all running allocs
	if a.job.Stopped() {
		a.handleStop(m)
		return a.result
	}

	// Detect if the deployment is paused
	if a.deployment != nil {
		a.deploymentPaused = a.deployment.Status == structs.DeploymentStatusPaused
		a.deploymentFailed = a.deployment.Status == structs.DeploymentStatusFailed
	}

	// Reconcile each group
	complete := true
	for group, as := range m {
		groupComplete := a.computeGroup(group, as)
		complete = complete && groupComplete
	}

	// Mark the deployment as complete if possible
	if a.deployment != nil && complete {
		a.result.deploymentUpdates = append(a.result.deploymentUpdates, &structs.DeploymentStatusUpdate{
			DeploymentID:      a.deployment.ID,
			Status:            structs.DeploymentStatusSuccessful,
			StatusDescription: structs.DeploymentStatusDescriptionSuccessful,
		})
	}

	// Set the description of a created deployment
	if d := a.result.deployment; d != nil {
		if d.RequiresPromotion() {
			d.StatusDescription = structs.DeploymentStatusDescriptionRunningNeedsPromotion
		}
	}

	return a.result
}
1346520
func (s *Bitset) Diff(b *Bitset) *Bitset {
	return s.bitsetOp(
		b,

		func(s, b *Bitset, length *uint) {
			if *length > s.Length(0) {
				*length = s.Length(0)
			} else {
				b.unsetTop()
			}
		},

		func(s, b *Bitset, index uint) {
			s.set[index] &= ^b.set[index]
		},
	)
}
1049741
func (diff *differ) Diff(out io.Writer, a io.ReadSeeker, b io.ReadSeeker) error {
	d, err := readData(a, b)
	if err != nil {
		return err
	}

	changes := d.Diff()
	for _, change := range changes {
		err := d.WriteHunk(out, change, 3)
		if err != nil {
			return err
		}
	}
	return nil
}
1138477
func Diff(A, B string) string {
	aLines := strings.Split(A, "\n")
	bLines := strings.Split(B, "\n")

	chunks := DiffChunks(aLines, bLines)

	buf := new(bytes.Buffer)
	for _, c := range chunks {
		for _, line := range c.Added {
			fmt.Fprintf(buf, "+%s\n", line)
		}
		for _, line := range c.Deleted {
			fmt.Fprintf(buf, "-%s\n", line)
		}
		for _, line := range c.Equal {
			fmt.Fprintf(buf, " %s\n", line)
		}
	}
	return strings.TrimRight(buf.String(), "\n")
}
814865
func (left *Resource) Subtract(right Resource) {
	switch right.checkType(left.GetType()) {
	case SCALAR:
		left.Scalar = left.GetScalar().Subtract(right.GetScalar())
	case RANGES:
		left.Ranges = left.GetRanges().Subtract(right.GetRanges())
	case SET:
		left.Set = left.GetSet().Subtract(right.GetSet())
	}
}
111169
func Diff(data sort.Interface, pivot int) (size int) {
	k, l := pivot, data.Len()
	p, i, j := 0, 0, k
	for i < k && j < l {
		switch {
		case data.Less(i, j):
			if p < i {
				data.Swap(p, i)
			}
			p, i = p+1, i+1
		case data.Less(j, i):
			j++
		default:
			i, j = i+1, j+1
		}
	}
	return xcopy(data, p, i, k, k)
}