Repository: kythe/kythe
Pull request #5600 (2023-04-25 21:17:47)

fix(serving): cleanup/fix crossrefs paging


Patch:
diff --git a/kythe/go/serving/xrefs/xrefs.go b/kythe/go/serving/xrefs/xrefs.go
index 9c1057e96..eabd1321b 100644
--- a/kythe/go/serving/xrefs/xrefs.go
+++ b/kythe/go/serving/xrefs/xrefs.go
@@ -1381,7 +1381,7 @@ func (s *refStats) addRelatedNodes(crs *xpb.CrossReferencesReply_CrossReferenceS
 }
 
 func (s *refStats) addAnchors(to *[]*xpb.CrossReferencesReply_RelatedAnchor, grp *srvpb.PagedCrossReferences_Group) bool {
-	if s.total == s.max {
+	if s.total >= s.max {
 		return true
 	}
 
@@ -1394,22 +1394,22 @@ func (s *refStats) addAnchors(to *[]*xpb.CrossReferencesReply_RelatedAnchor, grp
 	}
 	totalRefs := countRefs(scopedRefs)
 
-	if s.skip > totalRefs {
+	if s.skip >= totalRefs {
 		s.skip -= totalRefs
 		return false
 	}
 
 	if s.skip > 0 {
-		firstNonEmpty := len(scopedRefs)
+		var firstNonEmpty int
 		for i := 0; i < len(scopedRefs) && s.skip > 0; i++ {
 			sr := scopedRefs[i]
-			if len(sr.GetReference()) < s.skip {
+			if len(sr.GetReference()) <= s.skip {
 				s.skip -= len(sr.GetReference())
+				firstNonEmpty++
 				continue
 			}
-			sr.Reference = sr.GetReference()[:s.skip]
+			sr.Reference = sr.GetReference()[s.skip:]
 			s.skip = 0
-			firstNonEmpty = i
 		}
 		scopedRefs = scopedRefs[firstNonEmpty:]
 	}


Test patch:
diff --git a/kythe/go/serving/identifiers/identifiers_test.go b/kythe/go/serving/identifiers/identifiers_test.go
index 7ee8d9f04..dc7be379b 100644
--- a/kythe/go/serving/identifiers/identifiers_test.go
+++ b/kythe/go/serving/identifiers/identifiers_test.go
@@ -70,7 +70,7 @@ var tests = []testCase{
 	},
 	{
 		findRequest("com.java.package.Interface", []string{"corpus"}, nil),
-		[]*ipb.FindReply_Match{},
+		nil,
 	},
 }
 
diff --git a/kythe/go/serving/xrefs/xrefs_test.go b/kythe/go/serving/xrefs/xrefs_test.go
index e238d9015..35975fe50 100644
--- a/kythe/go/serving/xrefs/xrefs_test.go
+++ b/kythe/go/serving/xrefs/xrefs_test.go
@@ -1508,6 +1508,172 @@ func TestCrossReferencesScoped(t *testing.T) {
 	}
 }
 
+func TestCrossReferencesPaging(t *testing.T) {
+	ticket := "kythe://someCorpus?lang=otpl#signature"
+
+	st := tbl.Construct(t)
+	req := &xpb.CrossReferencesRequest{
+		Ticket:         []string{ticket},
+		DefinitionKind: xpb.CrossReferencesRequest_BINDING_DEFINITIONS,
+		ReferenceKind:  xpb.CrossReferencesRequest_ALL_REFERENCES,
+		Snippets:       xpb.SnippetsKind_DEFAULT,
+		SemanticScopes: true,
+		PageSize:       1,
+	}
+
+	var anchors []*xpb.CrossReferencesReply_RelatedAnchor
+	for {
+		reply, err := st.CrossReferences(ctx, req)
+		testutil.Fatalf(t, "CrossReferencesRequest error: %v", err)
+		xr := reply.GetCrossReferences()[ticket]
+		anchors = append(anchors, xr.GetReference()...)
+		anchors = append(anchors, xr.GetDefinition()...)
+		anchors = append(anchors, xr.GetDeclaration()...)
+		anchors = append(anchors, xr.GetCaller()...)
+
+		req.PageToken = reply.GetNextPageToken()
+		if req.PageToken == "" {
+			break
+		}
+		t.Logf("NextPageToken: %s", req.PageToken)
+	}
+
+	expected := []*xpb.CrossReferencesReply_RelatedAnchor{
+		{
+			Ticket: "kythe://someCorpus?lang=otpl#scope",
+			MarkedSource: &cpb.MarkedSource{
+				Kind:    cpb.MarkedSource_IDENTIFIER,
+				PreText: "Scope",
+			},
+			Anchor: &xpb.Anchor{
+				Ticket:      "kythe://c?lang=otpl?path=/a/path#scope",
+				Kind:        "/kythe/edge/defines/binding",
+				Parent:      "kythe://c?path=/a/path",
+				BuildConfig: "testConfig",
+
+				Span: &cpb.Span{
+					Start: &cpb.Point{
+						ByteOffset:   27,
+						LineNumber:   2,
+						ColumnOffset: 10,
+					},
+					End: &cpb.Point{
+						ByteOffset:   33,
+						LineNumber:   3,
+						ColumnOffset: 5,
+					},
+				},
+
+				SnippetSpan: &cpb.Span{
+					Start: &cpb.Point{
+						ByteOffset: 17,
+						LineNumber: 2,
+					},
+					End: &cpb.Point{
+						ByteOffset:   27,
+						LineNumber:   2,
+						ColumnOffset: 10,
+					},
+				},
+				Snippet: "here and  ",
+			},
+			Site: []*xpb.Anchor{{
+				Ticket:      "kythe://c?lang=otpl?path=/a/path#27-33",
+				Kind:        "/kythe/edge/defines/binding",
+				Parent:      "kythe://c?path=/a/path",
+				BuildConfig: "testConfig",
+
+				Span: &cpb.Span{
+					Start: &cpb.Point{
+						ByteOffset:   27,
+						LineNumber:   2,
+						ColumnOffset: 10,
+					},
+					End: &cpb.Point{
+						ByteOffset:   33,
+						LineNumber:   3,
+						ColumnOffset: 5,
+					},
+				},
+
+				SnippetSpan: &cpb.Span{
+					Start: &cpb.Point{
+						ByteOffset: 17,
+						LineNumber: 2,
+					},
+					End: &cpb.Point{
+						ByteOffset:   27,
+						LineNumber:   2,
+						ColumnOffset: 10,
+					},
+				},
+				Snippet: "here and  ",
+			}},
+		},
+		{
+			Anchor: &xpb.Anchor{
+				Ticket: "kythe:?path=some/utf16/file#0-4",
+				Kind:   "/kythe/edge/ref",
+				Parent: "kythe:?path=some/utf16/file",
+
+				Span: &cpb.Span{
+					Start: &cpb.Point{LineNumber: 1},
+					End:   &cpb.Point{ByteOffset: 4, LineNumber: 1, ColumnOffset: 4},
+				},
+
+				SnippetSpan: &cpb.Span{
+					Start: &cpb.Point{
+						LineNumber: 1,
+					},
+					End: &cpb.Point{
+						ByteOffset:   28,
+						LineNumber:   1,
+						ColumnOffset: 28,
+					},
+				},
+				Snippet: "これはいくつかのテキストです",
+			},
+		},
+		{
+			Anchor: &xpb.Anchor{
+				Ticket: "kythe://c?lang=otpl?path=/a/path#51-55",
+				Kind:   "/kythe/edge/ref",
+				Parent: "kythe://c?path=/a/path",
+
+				Span: &cpb.Span{
+					Start: &cpb.Point{
+						ByteOffset:   51,
+						LineNumber:   4,
+						ColumnOffset: 15,
+					},
+					End: &cpb.Point{
+						ByteOffset:   55,
+						LineNumber:   5,
+						ColumnOffset: 2,
+					},
+				},
+
+				SnippetSpan: &cpb.Span{
+					Start: &cpb.Point{
+						ByteOffset: 36,
+						LineNumber: 4,
+					},
+					End: &cpb.Point{
+						ByteOffset:   52,
+						LineNumber:   4,
+						ColumnOffset: 16,
+					},
+				},
+				Snippet: "some random text",
+			},
+		},
+	}
+
+	if err := testutil.DeepEqual(expected, anchors); err != nil {
+		t.Fatal(err)
+	}
+}
+
 func TestCrossReferencesReadAhead(t *testing.T) {
 	const flagName = "page_read_ahead"
 	val := flag.Lookup(flagName).Value.String()
@@ -1911,7 +2077,7 @@ func TestCrossReferencesPatching(t *testing.T) {
 			Snippet: "here and  ",
 		}}},
 	}
-	expectedInfos := []*srvpb.FileInfo{}
+	var expectedInfos []*srvpb.FileInfo
 
 	xr := reply.CrossReferences[ticket]
 	if xr == nil {
@@ -3194,7 +3360,12 @@ type byOffset []*xpb.CrossReferencesReply_RelatedAnchor
 func (s byOffset) Len() int      { return len(s) }
 func (s byOffset) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
 func (s byOffset) Less(i, j int) bool {
-	return s[i].Anchor.Span.Start.ByteOffset < s[j].Anchor.Span.Start.ByteOffset
+	if s[i].Anchor.Span.Start.ByteOffset != s[j].Anchor.Span.Start.ByteOffset {
+		return s[i].Anchor.Span.Start.ByteOffset < s[j].Anchor.Span.Start.ByteOffset
+	} else if len(s[i].Site) == 0 || len(s[i].Site) != len(s[j].Site) {
+		return len(s[i].Site) < len(s[j].Site)
+	}
+	return s[i].Site[0].Span.Start.ByteOffset < s[j].Site[0].Span.Start.ByteOffset
 }
 
 func nodeInfo(n *srvpb.Node) *cpb.NodeInfo {
diff --git a/kythe/go/test/testutil/BUILD b/kythe/go/test/testutil/BUILD
index fceb6d853..6b41de268 100644
--- a/kythe/go/test/testutil/BUILD
+++ b/kythe/go/test/testutil/BUILD
@@ -9,6 +9,5 @@ go_library(
         "//kythe/go/util/compare",
         "@com_github_google_go_cmp//cmp:go_default_library",
         "@io_k8s_sigs_yaml//:go_default_library",
-        "@org_golang_google_protobuf//proto:go_default_library",
     ],
 )
diff --git a/kythe/go/test/testutil/testutil.go b/kythe/go/test/testutil/testutil.go
index 95305061c..89b29f146 100644
--- a/kythe/go/test/testutil/testutil.go
+++ b/kythe/go/test/testutil/testutil.go
@@ -23,7 +23,6 @@ import (
 	"math/rand"
 	"os"
 	"path/filepath"
-	"reflect"
 	"regexp"
 	"runtime"
 	"strings"
@@ -32,123 +31,16 @@ import (
 	"kythe.io/kythe/go/util/compare"
 
 	"github.com/google/go-cmp/cmp"
-	"google.golang.org/protobuf/proto"
 	"sigs.k8s.io/yaml"
 )
 
 // DeepEqual determines if expected is deeply equal to got, returning a
 // detailed error if not. It is okay for expected and got to be protobuf
 // message values.
-func DeepEqual(expected, got interface{}) error {
-	// Check for proto.Message types specifically; because protobuf generated
-	// types have complex conditions for equality, only do the reflective step
-	// if they are known not to be equivalent. This avoids spurious errors that
-	// may arise from messages that are equivalent but have different internal
-	// states (e.g., due to unrecognized fields, caching, etc.).
-	if epb, ok := expected.(proto.Message); ok {
-		if gpb, ok := got.(proto.Message); ok {
-			if proto.Equal(epb, gpb) {
-				return nil
-			}
-			return fmt.Errorf("(-expected; +found)\n%s", compare.ProtoDiff(expected, got))
-		}
-	}
-
-	// At this point, we either have non-protobuf values, or we know that the
-	// two are unequal.
-	et, gt := reflect.TypeOf(expected), reflect.TypeOf(got)
-	ev, gv := reflect.ValueOf(expected), reflect.ValueOf(got)
-
-	for {
-		if (et == nil) != (gt == nil) {
-			// Only one was a nil interface value
-			return fmt.Errorf("expected: %v; found %v", expected, got)
-		} else if et == nil {
-			return nil // both were nil interface values
-		} else if et.Kind() != reflect.Ptr || gt.Kind() != reflect.Ptr {
-			break
-		}
-
-		if ev.Elem().IsValid() != gv.Elem().IsValid() {
-			return fmt.Errorf("expected: %v; found %v", expected, got)
-		}
-		if !ev.Elem().IsValid() {
-			return nil
-		}
-		ev, gv = ev.Elem(), gv.Elem()
-		et, gt = ev.Type(), gv.Type()
-	}
-
-	if et != gt {
-		return expectError(expected, got, "types differ: expected %T; found %T", expected, got)
-	}
-
-	if et.Kind() == reflect.Slice && gt.Kind() == reflect.Slice {
-		return expectSliceEqual(ev, gv)
-	} else if et.Kind() == reflect.Struct && gt.Kind() == reflect.Struct {
-		return expectStructEqual(ev, gv)
-	} else if et.Kind() == reflect.Map && gt.Kind() == reflect.Map {
-		return expectMapEqual(ev, gv)
-	}
-
-	if !reflect.DeepEqual(expected, got) {
-		return expectError(expected, got, "")
-	}
-	return nil
-}
-
-func expectError(expected, got interface{}, msg string, args ...interface{}) error {
-	if msg != "" {
-		msg = fmt.Sprintf(": "+msg, args...)
-	}
-
-	return fmt.Errorf("expected %v; found %v%s", expected, got, msg)
-}
-
-func expectSliceEqual(expected reflect.Value, got reflect.Value) error {
-	el, gl := expected.Len(), got.Len()
-	if el != gl {
-		return expectError(expected.Interface(), got.Interface(), "expected length: %d; found length: %d", el, gl)
-	}
-
-	for i := 0; i < el; i++ {
-		ev := expected.Index(i).Interface()
-		gv := got.Index(i).Interface()
-		if err := DeepEqual(ev, gv); err != nil {
-			return expectError(expected.Interface(), got.Interface(), "values at index %d differ: %s", i, err)
-		}
-	}
-	return nil
-}
-
-func expectStructEqual(expected, got reflect.Value) error {
-	for i := 0; i < expected.NumField(); i++ {
-		ef, gf := expected.Field(i), got.Field(i)
-		if err := DeepEqual(ef.Interface(), gf.Interface()); err != nil {
-			field := expected.Type().Field(i)
-			return expectError(expected.Interface(), got.Interface(), "%s fields differ: %s", field.Name, err)
-		}
+func DeepEqual(expected, got interface{}, opts ...cmp.Option) error {
+	if diff := compare.ProtoDiff(expected, got, opts...); diff != "" {
+		return fmt.Errorf("(-expected; +found)\n%s", diff)
 	}
-
-	return nil
-}
-
-func expectMapEqual(expected, got reflect.Value) error {
-	el, gl := expected.Len(), got.Len()
-	if el != gl {
-		return expectError(expected.Interface(), got.Interface(), "expected length: %d; found length: %d", el, gl)
-	}
-
-	for _, key := range expected.MapKeys() {
-		ev, gv := expected.MapIndex(key), got.MapIndex(key)
-
-		if ev.IsValid() != gv.IsValid() {
-			return expectError(expected.Interface(), got.Interface(), "%#v key values not both valid", key.Interface())
-		} else if err := DeepEqual(ev.Interface(), gv.Interface()); err != nil {
-			return expectError(expected.Interface(), got.Interface(), "%#v key values differ: %s", key.Interface(), err)
-		}
-	}
-
 	return nil
 }