code review 3079041: position.go: test cases for token.Pos

position.go: test cases for token.Pos

- adjustments to position.go due to changed sort.Search semantics
- various minor fixes

[gri, 2010-11-13 05:01:47]

Hello rsc (cc: golang-dev@googlegroups.com, r),

I'd like you to review this change.

[rsc1, 2010-11-17 18:40:00]

LGTM

I believe the suggested implementation
for searchFiles applies to the other searches too.

http://codereview.appspot.com/3079041/diff/6001/src/pkg/go/token/position.go
File src/pkg/go/token/position.go (right):

http://codereview.appspot.com/3079041/diff/6001/src/pkg/go/token/position.go#...
src/pkg/go/token/position.go:98: // TODO(gri) The code below is really
unfortunate. With the old
This boils down to the fact that the old search returned the
rightmost of a string of "equal" elements, while the new search
returns the leftmost.  I think there are better arguments for
leftmost than rightmost in general, but you need rightmost
here because of the definition of base.

To find the rightmost element that is ==, I think you can find
the leftmost element that is too big and then subtract one:

return sort.Search(len(a), func(i int) bool { x >= a[i].base }) - 1

Regarding the Search API, though, I wonder if the function f's
sense is inverted.  Right now Search(n, f) means "find me the first
index where f is false" - tell me what you're *not* looking for -
but I think I would find it easier to reason about  non-idiomatic 
alls such as this one if it meant "find me the first index where
f is *true" - tell me what you *are* looking for.  With that sense,
searchFiles would be

return sort.TrueSearch(len(a), func(i int) bool { x < a[i].base }) - 1

And then inverting f to match the current Search API produces
the implementation I suggested above.  In fact, that's how I got
there.

What do you think about inverting the sense of f in Search to
make this kind of reasoning about non-idiomatic searches
easier?

[gri, 2010-11-17 20:16:29]

On Wed, Nov 17, 2010 at 10:40 AM, <rsc@google.com> wrote:

> LGTM
>
> I believe the suggested implementation
> for searchFiles applies to the other searches too.
>

It works for searchFiles because each valid Pos p for a given FileSet will
lead to an index i > 0 because p >= a[0].base for any legal p and thus the
smallest i returned will be 1. This is not true for the search in
searchLineInfos where the search may return 0 and then i-1 is illegal.

I like the proposal of changing the sense of f (and I have looked at your
other search related CL), but I am hesitant to make the change at the
moment: In retrospect I am wondering if if was a mistake to change the
original semantics of search. The new semantics is superficially simpler to
understand, but all uses of binary search I have (and there are many, not
just in this code) turn out to use the original (Dijkstra) semantics. It may
be slightly easier to implement insert using the new semantics but that is
not the most frequent operation - it is finding indices to lookup stuff. And
it's that operation where we don't additional compares afterwards, if it can
be avoided.

- gri


>
>
>
> http://codereview.appspot.com/3079041/diff/6001/src/pkg/go/token/position.go
> File src/pkg/go/token/position.go (right):
>
>
>
http://codereview.appspot.com/3079041/diff/6001/src/pkg/go/token/position.go#...
> src/pkg/go/token/position.go:98: // TODO(gri) The code below is really
> unfortunate. With the old
> This boils down to the fact that the old search returned the
> rightmost of a string of "equal" elements, while the new search
> returns the leftmost.  I think there are better arguments for
> leftmost than rightmost in general, but you need rightmost
> here because of the definition of base.
>
> To find the rightmost element that is ==, I think you can find
> the leftmost element that is too big and then subtract one:
>
> return sort.Search(len(a), func(i int) bool { x >= a[i].base }) - 1
>
> Regarding the Search API, though, I wonder if the function f's
> sense is inverted.  Right now Search(n, f) means "find me the first
> index where f is false" - tell me what you're *not* looking for -
> but I think I would find it easier to reason about  non-idiomatic
> alls such as this one if it meant "find me the first index where
> f is *true" - tell me what you *are* looking for.  With that sense,
> searchFiles would be
>
> return sort.TrueSearch(len(a), func(i int) bool { x < a[i].base }) - 1
>
> And then inverting f to match the current Search API produces
> the implementation I suggested above.  In fact, that's how I got
> there.
>
> What do you think about inverting the sense of f in Search to
> make this kind of reasoning about non-idiomatic searches
> easier?
>
>
> http://codereview.appspot.com/3079041/
>

[gri, 2010-11-17 20:17:48]

*** Submitted as http://code.google.com/p/go/source/detail?r=f6ff36054db8 ***

position.go: test cases for token.Pos

- adjustments to position.go due to changed sort.Search semantics
- various minor fixes

R=rsc
CC=golang-dev, r
http://codereview.appspot.com/3079041