From 0053ec452db5bd973c7ac9f4faa5041884e460e8 Mon Sep 17 00:00:00 2001 From: cuiweixie Date: Thu, 25 Aug 2022 22:08:10 +0800 Subject: [PATCH] reflect: rtype.MethodByName using binary search Change-Id: If36e9fd7d6b1993ca2d0d382e7fa52212170c798 Reviewed-on: https://go-review.googlesource.com/c/go/+/425481 Auto-Submit: Ian Lance Taylor Run-TryBot: Ian Lance Taylor Reviewed-by: Cherry Mui Reviewed-by: Ian Lance Taylor TryBot-Result: Gopher Robot --- src/reflect/all_test.go | 10 ++++++++++ src/reflect/type.go | 22 ++++++++++++++++++---- 2 files changed, 28 insertions(+), 4 deletions(-) diff --git a/src/reflect/all_test.go b/src/reflect/all_test.go index e97f69904d..d80e6e5d86 100644 --- a/src/reflect/all_test.go +++ b/src/reflect/all_test.go @@ -2384,6 +2384,16 @@ func TestMethod(t *testing.T) { 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 443a4b258d..984091ffc4 100644 --- a/src/reflect/type.go +++ b/src/reflect/type.go @@ -892,12 +892,26 @@ func (t *rtype) MethodByName(name string) (m Method, ok bool) { 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 } -- 2.50.0