Repository: kythe/kythe
Pull request #5431 (2022-11-08 18:34:57)

chore: add support for patching full Spans


Patch:
diff --git a/kythe/go/serving/xrefs/columnar.go b/kythe/go/serving/xrefs/columnar.go
index d66c9b613..f7c42389a 100644
--- a/kythe/go/serving/xrefs/columnar.go
+++ b/kythe/go/serving/xrefs/columnar.go
@@ -285,7 +285,7 @@ func (c *ColumnarTable) Decorations(ctx context.Context, req *xpb.DecorationsReq
 			if diag.Span == nil {
 				reply.Diagnostic = append(reply.Diagnostic, diag)
 			} else {
-				start, end, exists := patcher.PatchSpan(diag.Span)
+				start, end, exists := patcher.Patch(span.ByteOffsets(diag.Span))
 				// Filter non-existent (or out-of-bounds) diagnostic.  Diagnostics can
 				// no longer exist if we were given a dirty buffer and the diagnostic
 				// was inside a changed region.
diff --git a/kythe/go/serving/xrefs/xrefs.go b/kythe/go/serving/xrefs/xrefs.go
index cae9ade03..9722ac7c2 100644
--- a/kythe/go/serving/xrefs/xrefs.go
+++ b/kythe/go/serving/xrefs/xrefs.go
@@ -548,7 +548,7 @@ func (t *Table) Decorations(ctx context.Context, req *xpb.DecorationsRequest) (*
 			if diag.Span == nil {
 				reply.Diagnostic = append(reply.Diagnostic, diag)
 			} else {
-				start, end, exists := patcher.PatchSpan(diag.Span)
+				start, end, exists := patcher.Patch(span.ByteOffsets(diag.Span))
 				// Filter non-existent (or out-of-bounds) diagnostic.  Diagnostics can
 				// no longer exist if we were given a dirty buffer and the diagnostic
 				// was inside a changed region.
diff --git a/kythe/go/util/span/span.go b/kythe/go/util/span/span.go
index 1c9d24503..799b2ee48 100644
--- a/kythe/go/util/span/span.go
+++ b/kythe/go/util/span/span.go
@@ -68,11 +68,17 @@ func NewPatcher(oldText, newText []byte) (p *Patcher, err error) {
 // Marshal encodes the Patcher into a packed binary format.
 func (p *Patcher) Marshal() ([]byte, error) {
 	db := &srvpb.Diff{
-		SpanLength: make([]int32, len(p.spans)),
-		SpanType:   make([]srvpb.Diff_Type, len(p.spans)),
+		SpanLength:       make([]int32, len(p.spans)),
+		SpanType:         make([]srvpb.Diff_Type, len(p.spans)),
+		SpanNewlines:     make([]int32, len(p.spans)),
+		SpanFirstNewline: make([]int32, len(p.spans)),
+		SpanLastNewline:  make([]int32, len(p.spans)),
 	}
 	for i, d := range p.spans {
 		db.SpanLength[i] = d.Length
+		db.SpanNewlines[i] = d.Newlines
+		db.SpanFirstNewline[i] = d.FirstNewline
+		db.SpanLastNewline[i] = d.LastNewline
 		switch d.Type {
 		case eq:
 			db.SpanType[i] = srvpb.Diff_EQUAL
@@ -95,10 +101,21 @@ func Unmarshal(rec []byte) (*Patcher, error) {
 	}
 	if len(db.SpanLength) != len(db.SpanType) {
 		return nil, fmt.Errorf("length of span_length does not match length of span_type: %d vs %d", len(db.SpanLength), len(db.SpanType))
+	} else if len(db.SpanLength) != len(db.SpanNewlines) {
+		return nil, fmt.Errorf("length of span_length does not match length of span_newlines: %d vs %d", len(db.SpanLength), len(db.SpanNewlines))
+	} else if len(db.SpanLength) != len(db.SpanFirstNewline) {
+		return nil, fmt.Errorf("length of span_length does not match length of span_first_newline: %d vs %d", len(db.SpanLength), len(db.SpanFirstNewline))
+	} else if len(db.SpanLength) != len(db.SpanLastNewline) {
+		return nil, fmt.Errorf("length of span_length does not match length of span_last_newline: %d vs %d", len(db.SpanLength), len(db.SpanLastNewline))
 	}
 	spans := make([]diff, len(db.SpanLength))
 	for i, l := range db.SpanLength {
-		spans[i].Length = l
+		spans[i] = diff{
+			Length:       l,
+			Newlines:     db.SpanNewlines[i],
+			FirstNewline: db.SpanFirstNewline[i],
+			LastNewline:  db.SpanLastNewline[i],
+		}
 		switch db.SpanType[i] {
 		case srvpb.Diff_EQUAL:
 			spans[i].Type = eq
@@ -116,6 +133,10 @@ func Unmarshal(rec []byte) (*Patcher, error) {
 type diff struct {
 	Length int32
 	Type   diffmatchpatch.Operation
+
+	Newlines     int32
+	FirstNewline int32
+	LastNewline  int32
 }
 
 const (
@@ -127,11 +148,106 @@ const (
 func mapToOffsets(ds []diffmatchpatch.Diff) []diff {
 	res := make([]diff, len(ds))
 	for i, d := range ds {
-		res[i] = diff{Length: int32(len(d.Text)), Type: d.Type}
+		l := len(d.Text)
+		var newlines int
+		var first, last int = -1, -1
+		for j := 0; j < l; j++ {
+			if d.Text[j] != '\n' {
+				continue
+			}
+			newlines++
+			if first == -1 {
+				first = j
+			}
+			last = j
+		}
+		res[i] = diff{
+			Length:       int32(l),
+			Type:         d.Type,
+			Newlines:     int32(newlines),
+			FirstNewline: int32(first),
+			LastNewline:  int32(last),
+		}
 	}
 	return res
 }
 
+type offsetTracker struct {
+	Type diffmatchpatch.Operation
+
+	Offset       int32
+	Lines        int32
+	ColumnOffset int32
+}
+
+func (t *offsetTracker) Update(d diff) {
+	if d.Type != eq && d.Type != t.Type {
+		return
+	}
+	t.Offset += d.Length
+	t.Lines += d.Newlines
+	if d.LastNewline == -1 {
+		t.ColumnOffset += d.Length
+	} else {
+		t.ColumnOffset = d.Length - d.LastNewline - 1
+	}
+}
+
+// PatchSpan returns the resulting Span of mapping the given Span from the
+// Patcher's constructed oldText to its newText.  If the span no longer exists
+// in newText or is invalid, the returned bool will be false.  As a convenience,
+// if p==nil, the original span will be returned.
+func (p *Patcher) PatchSpan(s *cpb.Span) (span *cpb.Span, exists bool) {
+	spanStart := s.GetStart().GetByteOffset()
+	spanEnd := s.GetEnd().GetByteOffset()
+	if spanStart > spanEnd {
+		return nil, false
+	} else if p == nil {
+		return s, true
+	}
+
+	oldT := offsetTracker{Type: del}
+	newT := offsetTracker{Type: ins}
+
+	for _, d := range p.spans {
+		if oldT.Offset > spanStart {
+			return nil, false
+		}
+
+		if d.Type == eq && oldT.Offset <= spanStart && spanEnd <= oldT.Offset+d.Length {
+			// The span is located within the equal region.  It exists.
+			lineDiff := newT.Lines - oldT.Lines
+			colDiff := newT.ColumnOffset - oldT.ColumnOffset
+			if d.FirstNewline != -1 && spanStart-oldT.Offset >= d.FirstNewline {
+				// The given span is past the first newline so it has no column diff.
+				colDiff = 0
+			}
+			return &cpb.Span{
+				Start: &cpb.Point{
+					ByteOffset:   newT.Offset + (spanStart - oldT.Offset),
+					ColumnOffset: s.GetStart().GetColumnOffset() + colDiff,
+					LineNumber:   s.GetStart().GetLineNumber() + lineDiff,
+				},
+				End: &cpb.Point{
+					ByteOffset:   newT.Offset + (spanEnd - oldT.Offset),
+					ColumnOffset: s.GetEnd().GetColumnOffset() + colDiff,
+					LineNumber:   s.GetEnd().GetLineNumber() + lineDiff,
+				},
+			}, true
+		}
+
+		oldT.Update(d)
+		newT.Update(d)
+	}
+
+	return nil, false
+}
+
+// ByteOffsets returns the starting and ending byte offsets of the Span.
+func ByteOffsets(s *cpb.Span) (int32, int32) {
+	return s.GetStart().GetByteOffset(), s.GetEnd().GetByteOffset()
+}
+
 // Patch returns the resulting span of mapping the given span from the Patcher's
 // constructed oldText to its newText.  If the span no longer exists in newText
 // or is invalid, the returned bool will be false.  As a convenience, if p==nil,
@@ -169,12 +285,6 @@ func (p *Patcher) Patch(spanStart, spanEnd int32) (newStart, newEnd int32, exist
 	return 0, 0, false
 }
 
-// PatchSpan returns the given Span's byte offsets mapped from the Patcher's
-// oldText to its newText using Patcher.Patch.
-func (p *Patcher) PatchSpan(span *cpb.Span) (newStart, newEnd int32, exists bool) {
-	return p.Patch(span.GetStart().GetByteOffset(), span.GetEnd().GetByteOffset())
-}
-
 // Normalizer fixes xref.Locations within a given source text so that each point
 // has consistent byte_offset, line_number, and column_offset fields within the
 // range of text's length and its line lengths.
diff --git a/kythe/proto/serving.proto b/kythe/proto/serving.proto
index dbdace18f..f8c04656b 100644
--- a/kythe/proto/serving.proto
+++ b/kythe/proto/serving.proto
@@ -425,4 +425,7 @@ message Diff {
   // Parallel array of diff spans so the values are packed.
   repeated int32 span_length = 1 [packed = true];
   repeated Type span_type = 2 [packed = true];
+  repeated int32 span_newlines = 3 [packed = true];
+  repeated int32 span_first_newline = 4 [packed = true];
+  repeated int32 span_last_newline = 5 [packed = true];
 }
diff --git a/kythe/proto/serving_go_proto/serving.pb.go b/kythe/proto/serving_go_proto/serving.pb.go
index f79bd129d..da8b73875 100644
--- a/kythe/proto/serving_go_proto/serving.pb.go
+++ b/kythe/proto/serving_go_proto/serving.pb.go
@@ -1602,8 +1602,11 @@ type Diff struct {
 	sizeCache     protoimpl.SizeCache
 	unknownFields protoimpl.UnknownFields
 
-	SpanLength []int32     `protobuf:"varint,1,rep,packed,name=span_length,json=spanLength,proto3" json:"span_length,omitempty"`
-	SpanType   []Diff_Type `protobuf:"varint,2,rep,packed,name=span_type,json=spanType,proto3,enum=kythe.proto.serving.Diff_Type" json:"span_type,omitempty"`
+	SpanLength       []int32     `protobuf:"varint,1,rep,packed,name=span_length,json=spanLength,proto3" json:"span_length,omitempty"`
+	SpanType         []Diff_Type `protobuf:"varint,2,rep,packed,name=span_type,json=spanType,proto3,enum=kythe.proto.serving.Diff_Type" json:"span_type,omitempty"`
+	SpanNewlines     []int32     `protobuf:"varint,3,rep,packed,name=span_newlines,json=spanNewlines,proto3" json:"span_newlines,omitempty"`
+	SpanFirstNewline []int32     `protobuf:"varint,4,rep,packed,name=span_first_newline,json=spanFirstNewline,proto3" json:"span_first_newline,omitempty"`
+	SpanLastNewline  []int32     `protobuf:"varint,5,rep,packed,name=span_last_newline,json=spanLastNewline,proto3" json:"span_last_newline,omitempty"`
 }
 
 func (x *Diff) Reset() {
@@ -1652,6 +1655,27 @@ func (x *Diff) GetSpanType() []Diff_Type {
 	return nil
 }
 
+func (x *Diff) GetSpanNewlines() []int32 {
+	if x != nil {
+		return x.SpanNewlines
+	}
+	return nil
+}
+
+func (x *Diff) GetSpanFirstNewline() []int32 {
+	if x != nil {
+		return x.SpanFirstNewline
+	}
+	return nil
+}
+
+func (x *Diff) GetSpanLastNewline() []int32 {
+	if x != nil {
+		return x.SpanLastNewline
+	}
+	return nil
+}
+
 type EdgeGroup_Edge struct {
 	state         protoimpl.MessageState
 	sizeCache     protoimpl.SizeCache
@@ -2765,20 +2789,29 @@ var file_kythe_proto_serving_proto_rawDesc = []byte{
 	0x68, 0x2e, 0x54, 0x79, 0x70, 0x65, 0x52, 0x04, 0x74, 0x79, 0x70, 0x65, 0x22, 0x2b, 0x0a, 0x04,
 	0x54, 0x79, 0x70, 0x65, 0x12, 0x0b, 0x0a, 0x07, 0x55, 0x4e, 0x4b, 0x4e, 0x4f, 0x57, 0x4e, 0x10,
 	0x00, 0x12, 0x0a, 0x0a, 0x06, 0x43, 0x41, 0x4c, 0x4c, 0x45, 0x52, 0x10, 0x01, 0x12, 0x0a, 0x0a,
-	0x06, 0x43, 0x41, 0x4c, 0x4c, 0x45, 0x45, 0x10, 0x02, 0x22, 0x97, 0x01, 0x0a, 0x04, 0x44, 0x69,
+	0x06, 0x43, 0x41, 0x4c, 0x4c, 0x45, 0x45, 0x10, 0x02, 0x22, 0xa2, 0x02, 0x0a, 0x04, 0x44, 0x69,
 	0x66, 0x66, 0x12, 0x23, 0x0a, 0x0b, 0x73, 0x70, 0x61, 0x6e, 0x5f, 0x6c, 0x65, 0x6e, 0x67, 0x74,
 	0x68, 0x18, 0x01, 0x20, 0x03, 0x28, 0x05, 0x42, 0x02, 0x10, 0x01, 0x52, 0x0a, 0x73, 0x70, 0x61,
 	0x6e, 0x4c, 0x65, 0x6e, 0x67, 0x74, 0x68, 0x12, 0x3f, 0x0a, 0x09, 0x73, 0x70, 0x61, 0x6e, 0x5f,
 	0x74, 0x79, 0x70, 0x65, 0x18, 0x02, 0x20, 0x03, 0x28, 0x0e, 0x32, 0x1e, 0x2e, 0x6b, 0x79, 0x74,
 	0x68, 0x65, 0x2e, 0x70, 0x72, 0x6f, 0x74, 0x6f, 0x2e, 0x73, 0x65, 0x72, 0x76, 0x69, 0x6e, 0x67,
 	0x2e, 0x44, 0x69, 0x66, 0x66, 0x2e, 0x54, 0x79, 0x70, 0x65, 0x42, 0x02, 0x10, 0x01, 0x52, 0x08,
-	0x73, 0x70, 0x61, 0x6e, 0x54, 0x79, 0x70, 0x65, 0x22, 0x29, 0x0a, 0x04, 0x54, 0x79, 0x70, 0x65,
-	0x12, 0x09, 0x0a, 0x05, 0x45, 0x51, 0x55, 0x41, 0x4c, 0x10, 0x00, 0x12, 0x0a, 0x0a, 0x06, 0x49,
-	0x4e, 0x53, 0x45, 0x52, 0x54, 0x10, 0x01, 0x12, 0x0a, 0x0a, 0x06, 0x44, 0x45, 0x4c, 0x45, 0x54,
-	0x45, 0x10, 0x02, 0x42, 0x33, 0x0a, 0x1f, 0x63, 0x6f, 0x6d, 0x2e, 0x67, 0x6f, 0x6f, 0x67, 0x6c,
-	0x65, 0x2e, 0x64, 0x65, 0x76, 0x74, 0x6f, 0x6f, 0x6c, 0x73, 0x2e, 0x6b, 0x79, 0x74, 0x68, 0x65,
-	0x2e, 0x70, 0x72, 0x6f, 0x74, 0x6f, 0x5a, 0x10, 0x73, 0x65, 0x72, 0x76, 0x69, 0x6e, 0x67, 0x5f,
-	0x67, 0x6f, 0x5f, 0x70, 0x72, 0x6f, 0x74, 0x6f, 0x62, 0x06, 0x70, 0x72, 0x6f, 0x74, 0x6f, 0x33,
+	0x73, 0x70, 0x61, 0x6e, 0x54, 0x79, 0x70, 0x65, 0x12, 0x27, 0x0a, 0x0d, 0x73, 0x70, 0x61, 0x6e,
+	0x5f, 0x6e, 0x65, 0x77, 0x6c, 0x69, 0x6e, 0x65, 0x73, 0x18, 0x03, 0x20, 0x03, 0x28, 0x05, 0x42,
+	0x02, 0x10, 0x01, 0x52, 0x0c, 0x73, 0x70, 0x61, 0x6e, 0x4e, 0x65, 0x77, 0x6c, 0x69, 0x6e, 0x65,
+	0x73, 0x12, 0x30, 0x0a, 0x12, 0x73, 0x70, 0x61, 0x6e, 0x5f, 0x66, 0x69, 0x72, 0x73, 0x74, 0x5f,
+	0x6e, 0x65, 0x77, 0x6c, 0x69, 0x6e, 0x65, 0x18, 0x04, 0x20, 0x03, 0x28, 0x05, 0x42, 0x02, 0x10,
+	0x01, 0x52, 0x10, 0x73, 0x70, 0x61, 0x6e, 0x46, 0x69, 0x72, 0x73, 0x74, 0x4e, 0x65, 0x77, 0x6c,
+	0x69, 0x6e, 0x65, 0x12, 0x2e, 0x0a, 0x11, 0x73, 0x70, 0x61, 0x6e, 0x5f, 0x6c, 0x61, 0x73, 0x74,
+	0x5f, 0x6e, 0x65, 0x77, 0x6c, 0x69, 0x6e, 0x65, 0x18, 0x05, 0x20, 0x03, 0x28, 0x05, 0x42, 0x02,
+	0x10, 0x01, 0x52, 0x0f, 0x73, 0x70, 0x61, 0x6e, 0x4c, 0x61, 0x73, 0x74, 0x4e, 0x65, 0x77, 0x6c,
+	0x69, 0x6e, 0x65, 0x22, 0x29, 0x0a, 0x04, 0x54, 0x79, 0x70, 0x65, 0x12, 0x09, 0x0a, 0x05, 0x45,
+	0x51, 0x55, 0x41, 0x4c, 0x10, 0x00, 0x12, 0x0a, 0x0a, 0x06, 0x49, 0x4e, 0x53, 0x45, 0x52, 0x54,
+	0x10, 0x01, 0x12, 0x0a, 0x0a, 0x06, 0x44, 0x45, 0x4c, 0x45, 0x54, 0x45, 0x10, 0x02, 0x42, 0x33,
+	0x0a, 0x1f, 0x63, 0x6f, 0x6d, 0x2e, 0x67, 0x6f, 0x6f, 0x67, 0x6c, 0x65, 0x2e, 0x64, 0x65, 0x76,
+	0x74, 0x6f, 0x6f, 0x6c, 0x73, 0x2e, 0x6b, 0x79, 0x74, 0x68, 0x65, 0x2e, 0x70, 0x72, 0x6f, 0x74,
+	0x6f, 0x5a, 0x10, 0x73, 0x65, 0x72, 0x76, 0x69, 0x6e, 0x67, 0x5f, 0x67, 0x6f, 0x5f, 0x70, 0x72,
+	0x6f, 0x74, 0x6f, 0x62, 0x06, 0x70, 0x72, 0x6f, 0x74, 0x6f, 0x33,
 }
 
 var (


Test patch:
diff --git a/kythe/go/util/span/span_test.go b/kythe/go/util/span/span_test.go
index 2c88873da..6b9dd5718 100644
--- a/kythe/go/util/span/span_test.go
+++ b/kythe/go/util/span/span_test.go
@@ -18,6 +18,7 @@ package span
 
 import (
 	"fmt"
+	"strconv"
 	"testing"
 
 	"kythe.io/kythe/go/test/testutil"
@@ -157,9 +158,150 @@ func TestPatcher(t *testing.T) {
 	}
 }
 
+func p(bo, ln, co int32) *cpb.Point {
+	return &cpb.Point{ByteOffset: bo, LineNumber: ln, ColumnOffset: co}
+}
+
+func sp(start, end *cpb.Point) *cpb.Span { return &cpb.Span{Start: start, End: end} }
+
+func TestPatchSpan(t *testing.T) {
+	tests := []struct {
+		oldText, newText string
+
+		oldSpans []*cpb.Span
+		newSpans []*cpb.Span
+	}{{
+		oldText: "this is some text",
+		newText: "this is some changed text",
+
+		oldSpans: []*cpb.Span{
+			sp(p(0, 1, 0), p(4, 1, 4)),
+			sp(p(13, 1, 13), p(17, 1, 17)),
+		},
+		newSpans: []*cpb.Span{
+			sp(p(0, 1, 0), p(4, 1, 4)),
+			sp(p(21, 1, 21), p(25, 1, 25)),
+		},
+	}, {
+		oldText: "line one\nline two\nline three\nline four\n",
+		newText: "line one\nline three\nline two\npre line four\n",
+
+		oldSpans: []*cpb.Span{
+			sp(p(0, 1, 0), p(5, 1, 5)),
+			sp(p(10, 2, 0), p(14, 2, 4)),
+			sp(p(15, 2, 6), p(18, 2, 11)),
+			sp(p(30, 4, 0), p(34, 4, 4)),
+		},
+		newSpans: []*cpb.Span{
+			sp(p(0, 1, 0), p(5, 1, 5)),
+			sp(p(10, 2, 0), p(14, 2, 4)),
+			nil,
+			sp(p(34, 4, 4), p(38, 4, 8)),
+		},
+	}, {
+		oldText: "line one\nmoved\n",
+		newText: "line one\ninsert\nmoved\n",
+
+		oldSpans: []*cpb.Span{
+			sp(p(5, 1, 5), p(8, 1, 8)),
+			sp(p(10, 2, 0), p(15, 2, 5)),
+		},
+		newSpans: []*cpb.Span{
+			sp(p(5, 1, 5), p(8, 1, 8)),
+			sp(p(17, 3, 0), p(22, 3, 5)),
+		},
+	}, {
+		oldText: "line\ntwo\nthree\n",
+		newText: "line one\nline two\nthee\n",
+
+		oldSpans: []*cpb.Span{
+			sp(p(0, 1, 0), p(4, 1, 4)),
+			sp(p(5, 2, 0), p(8, 2, 3)),
+			sp(p(9, 3, 0), p(14, 3, 5)),
+		},
+		newSpans: []*cpb.Span{
+			sp(p(0, 1, 0), p(4, 1, 4)),
+			sp(p(14, 2, 5), p(17, 2, 8)),
+			nil,
+		},
+	}, {
+		oldText: "line three\n",
+		newText: "line one\ntwo\nthree\n",
+
+		oldSpans: []*cpb.Span{
+			sp(p(0, 1, 0), p(4, 1, 4)),
+			sp(p(5, 1, 5), p(10, 1, 10)),
+		},
+		newSpans: []*cpb.Span{
+			sp(p(0, 1, 0), p(4, 1, 4)),
+			sp(p(13, 3, 0), p(18, 3, 5)),
+		},
+	}, {
+		oldText: "line three\nfour\n",
+		newText: "line one\ntwo\nthree\nfour\n",
+
+		oldSpans: []*cpb.Span{
+			sp(p(0, 1, 0), p(4, 1, 4)),
+			sp(p(5, 1, 5), p(10, 1, 10)),
+			sp(p(11, 2, 0), p(15, 2, 4)),
+		},
+		newSpans: []*cpb.Span{
+			sp(p(0, 1, 0), p(4, 1, 4)),
+			sp(p(13, 3, 0), p(18, 3, 5)),
+			sp(p(19, 4, 0), p(23, 4, 4)),
+		},
+	}, {
+		oldText: "線\n動\n",
+		newText: "線\n入\n動\n",
+
+		oldSpans: []*cpb.Span{
+			sp(p(0, 1, 0), p(3, 1, 3)),
+			sp(p(0, 1, 0), p(7, 2, 3)),
+			sp(p(4, 2, 0), p(7, 2, 3)),
+		},
+		newSpans: []*cpb.Span{
+			sp(p(0, 1, 0), p(3, 1, 3)),
+			nil,
+			sp(p(8, 3, 0), p(11, 3, 3)),
+		},
+	}}
+
+	for i, test := range tests {
+		t.Run(strconv.Itoa(i), func(t *testing.T) {
+			if len(test.oldSpans) == 0 || len(test.oldSpans) != len(test.newSpans) {
+				t.Fatalf("Invalid test: {%v}", test)
+			}
+
+			p, err := NewPatcher([]byte(test.oldText), []byte(test.newText))
+			if err != nil {
+				t.Fatal(err)
+			}
+
+			for i, s := range test.oldSpans {
+				t.Run(strconv.Itoa(i), func(t *testing.T) {
+					found, exists := p.PatchSpan(s)
+
+					if ns := test.newSpans[i]; ns == nil && exists {
+						t.Errorf("Expected span not to exist in new text; received %s", found)
+					} else if ns != nil && !exists {
+						t.Errorf("Expected span %s to exist in new text as %s; did not exist", s, ns)
+					} else if ns != nil && exists && !proto.Equal(found, ns) {
+						t.Errorf("(-expected; +found)\n%s", compare.ProtoDiff(ns, found))
+					}
+				})
+			}
+		})
+	}
+}
+
 func TestMarshal(t *testing.T) {
 	expected := &Patcher{
-		[]diff{{2, ins}, {10, del}, {3, eq}, {5, ins}},
+		[]diff{
+			{2, ins, 1, 2, 5},
+			{10, del, 5, 0, 9},
+			{3, eq, 0, -1, -1},
+			{5, ins, 1, 2, 2},
+		},
 	}
 
 	rec, err := expected.Marshal()