reflect: rtype.MethodByName using binary search
Change-Id: If36e9fd7d6b1993ca2d0d382e7fa52212170c798
Reviewed-on: https://go-review.googlesource.com/c/go/+/425481
Auto-Submit: Ian Lance Taylor <iant@google.com>
Run-TryBot: Ian Lance Taylor <iant@google.com>
Reviewed-by: Cherry Mui <cherryyz@google.com>
Reviewed-by: Ian Lance Taylor <iant@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
diff --git a/src/reflect/all_test.go b/src/reflect/all_test.go
index e97f699..d80e6e5 100644
--- a/src/reflect/all_test.go
+++ b/src/reflect/all_test.go
@@ -2384,6 +2384,16 @@
t.Errorf("NoArgs returned %d values; want 0", n)
}
+ _, ok = TypeOf(&p).MethodByName("AA")
+ if ok {
+ t.Errorf(`MethodByName("AA") should have failed`)
+ }
+
+ _, ok = TypeOf(&p).MethodByName("ZZ")
+ if ok {
+ t.Errorf(`MethodByName("ZZ") should have failed`)
+ }
+
// Curried method of value.
tfunc := TypeOf((func(int) int)(nil))
v := ValueOf(p).Method(1)
diff --git a/src/reflect/type.go b/src/reflect/type.go
index 443a4b2..984091f 100644
--- a/src/reflect/type.go
+++ b/src/reflect/type.go
@@ -892,12 +892,26 @@
if ut == nil {
return Method{}, false
}
- // TODO(mdempsky): Binary search.
- for i, p := range ut.exportedMethods() {
- if t.nameOff(p.name).name() == name {
- return t.Method(i), true
+
+ methods := ut.exportedMethods()
+
+ // We are looking for the first index i where the string becomes >= s.
+ // This is a copy of sort.Search, with f(h) replaced by (t.nameOff(methods[h].name).name() >= name).
+ i, j := 0, len(methods)
+ for i < j {
+ h := int(uint(i+j) >> 1) // avoid overflow when computing h
+ // i ≤ h < j
+ if !(t.nameOff(methods[h].name).name() >= name) {
+ i = h + 1 // preserves f(i-1) == false
+ } else {
+ j = h // preserves f(j) == true
}
}
+ // i == j, f(i-1) == false, and f(j) (= f(i)) == true => answer is i.
+ if i < len(methods) && name == t.nameOff(methods[i].name).name() {
+ return t.Method(i), true
+ }
+
return Method{}, false
}
