common.go

Documentation: golang.org/x/tools/internal/diff/lcs

     1  // Copyright 2022 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package lcs
     6  
     7  import (
     8  	"log"
     9  	"sort"
    10  )
    11  
    12  // lcs is a longest common sequence
    13  type lcs []diag
    14  
    15  // A diag is a piece of the edit graph where A[X+i] == B[Y+i], for 0<=i<Len.
    16  // All computed diagonals are parts of a longest common subsequence.
    17  type diag struct {
    18  	X, Y int
    19  	Len  int
    20  }
    21  
    22  // sort sorts in place, by lowest X, and if tied, inversely by Len
    23  func (l lcs) sort() lcs {
    24  	sort.Slice(l, func(i, j int) bool {
    25  		if l[i].X != l[j].X {
    26  			return l[i].X < l[j].X
    27  		}
    28  		return l[i].Len > l[j].Len
    29  	})
    30  	return l
    31  }
    32  
    33  // validate that the elements of the lcs do not overlap
    34  // (can only happen when the two-sided algorithm ends early)
    35  // expects the lcs to be sorted
    36  func (l lcs) valid() bool {
    37  	for i := 1; i < len(l); i++ {
    38  		if l[i-1].X+l[i-1].Len > l[i].X {
    39  			return false
    40  		}
    41  		if l[i-1].Y+l[i-1].Len > l[i].Y {
    42  			return false
    43  		}
    44  	}
    45  	return true
    46  }
    47  
    48  // repair overlapping lcs
    49  // only called if two-sided stops early
    50  func (l lcs) fix() lcs {
    51  	// from the set of diagonals in l, find a maximal non-conflicting set
    52  	// this problem may be NP-complete, but we use a greedy heuristic,
    53  	// which is quadratic, but with a better data structure, could be D log D.
    54  	// indepedent is not enough: {0,3,1} and {3,0,2} can't both occur in an lcs
    55  	// which has to have monotone x and y
    56  	if len(l) == 0 {
    57  		return nil
    58  	}
    59  	sort.Slice(l, func(i, j int) bool { return l[i].Len > l[j].Len })
    60  	tmp := make(lcs, 0, len(l))
    61  	tmp = append(tmp, l[0])
    62  	for i := 1; i < len(l); i++ {
    63  		var dir direction
    64  		nxt := l[i]
    65  		for _, in := range tmp {
    66  			if dir, nxt = overlap(in, nxt); dir == empty || dir == bad {
    67  				break
    68  			}
    69  		}
    70  		if nxt.Len > 0 && dir != bad {
    71  			tmp = append(tmp, nxt)
    72  		}
    73  	}
    74  	tmp.sort()
    75  	if false && !tmp.valid() { // debug checking
    76  		log.Fatalf("here %d", len(tmp))
    77  	}
    78  	return tmp
    79  }
    80  
    81  type direction int
    82  
    83  const (
    84  	empty    direction = iota // diag is empty (so not in lcs)
    85  	leftdown                  // proposed acceptably to the left and below
    86  	rightup                   // proposed diag is acceptably to the right and above
    87  	bad                       // proposed diag is inconsistent with the lcs so far
    88  )
    89  
    90  // overlap trims the proposed diag prop  so it doesn't overlap with
    91  // the existing diag that has already been added to the lcs.
    92  func overlap(exist, prop diag) (direction, diag) {
    93  	if prop.X <= exist.X && exist.X < prop.X+prop.Len {
    94  		// remove the end of prop where it overlaps with the X end of exist
    95  		delta := prop.X + prop.Len - exist.X
    96  		prop.Len -= delta
    97  		if prop.Len <= 0 {
    98  			return empty, prop
    99  		}
   100  	}
   101  	if exist.X <= prop.X && prop.X < exist.X+exist.Len {
   102  		// remove the beginning of prop where overlaps with exist
   103  		delta := exist.X + exist.Len - prop.X
   104  		prop.Len -= delta
   105  		if prop.Len <= 0 {
   106  			return empty, prop
   107  		}
   108  		prop.X += delta
   109  		prop.Y += delta
   110  	}
   111  	if prop.Y <= exist.Y && exist.Y < prop.Y+prop.Len {
   112  		// remove the end of prop that overlaps (in Y) with exist
   113  		delta := prop.Y + prop.Len - exist.Y
   114  		prop.Len -= delta
   115  		if prop.Len <= 0 {
   116  			return empty, prop
   117  		}
   118  	}
   119  	if exist.Y <= prop.Y && prop.Y < exist.Y+exist.Len {
   120  		// remove the beginning of peop that overlaps with exist
   121  		delta := exist.Y + exist.Len - prop.Y
   122  		prop.Len -= delta
   123  		if prop.Len <= 0 {
   124  			return empty, prop
   125  		}
   126  		prop.X += delta // no test reaches this code
   127  		prop.Y += delta
   128  	}
   129  	if prop.X+prop.Len <= exist.X && prop.Y+prop.Len <= exist.Y {
   130  		return leftdown, prop
   131  	}
   132  	if exist.X+exist.Len <= prop.X && exist.Y+exist.Len <= prop.Y {
   133  		return rightup, prop
   134  	}
   135  	// prop can't be in an lcs that contains exist
   136  	return bad, prop
   137  }
   138  
   139  // manipulating Diag and lcs
   140  
   141  // prepend a diagonal (x,y)-(x+1,y+1) segment either to an empty lcs
   142  // or to its first Diag. prepend is only called to extend diagonals
   143  // the backward direction.
   144  func (lcs lcs) prepend(x, y int) lcs {
   145  	if len(lcs) > 0 {
   146  		d := &lcs[0]
   147  		if int(d.X) == x+1 && int(d.Y) == y+1 {
   148  			// extend the diagonal down and to the left
   149  			d.X, d.Y = int(x), int(y)
   150  			d.Len++
   151  			return lcs
   152  		}
   153  	}
   154  
   155  	r := diag{X: int(x), Y: int(y), Len: 1}
   156  	lcs = append([]diag{r}, lcs...)
   157  	return lcs
   158  }
   159  
   160  // append appends a diagonal, or extends the existing one.
   161  // by adding the edge (x,y)-(x+1.y+1). append is only called
   162  // to extend diagonals in the forward direction.
   163  func (lcs lcs) append(x, y int) lcs {
   164  	if len(lcs) > 0 {
   165  		last := &lcs[len(lcs)-1]
   166  		// Expand last element if adjoining.
   167  		if last.X+last.Len == x && last.Y+last.Len == y {
   168  			last.Len++
   169  			return lcs
   170  		}
   171  	}
   172  
   173  	return append(lcs, diag{X: x, Y: y, Len: 1})
   174  }
   175  
   176  // enforce constraint on d, k
   177  func ok(d, k int) bool {
   178  	return d >= 0 && -d <= k && k <= d
   179  }
   180
View as plain text