go/token: FileSet: hold Files in a balanced tree

This CL changes the representation of FileSet from a slice
to a tree, specifically an AVL tree keyed by the File's
base-end range. This makes a sequence of insertions using
AddExistingFiles much more efficient: creating a FileSet
of size n by a sequence of calls costs O(n log n), whereas
before it was O(n^2 log n) because of the repeated sorting.

The AVL tree is based on Russ' github.com/rsc/omap,
simplified for clarity and to reduce unnecessary dynamism.
We use an AVL tree as it is more strongly balanced than an
RB tree, optimising lookups at the expense of insertions.

The CL includes a basic unit test of the tree using
operations on pseudorandom values.

Benchmarks of Position lookups actually improve because
the tree avoids BinarySearchFunc's dynamic dispatch to cmp,
and the benchmark of AddExistingFiles is about 1000x (!) faster:

goos: darwin
goarch: arm64
pkg: go/token
cpu: Apple M1 Pro
                                    │     old.txt     │               new.txt               │
                                    │     sec/op      │    sec/op     vs base               │
FileSet_Position/random-8                51.60n ±  1%   39.99n ±  1%  -22.50% (p=0.000 n=9)
FileSet_Position/file-8                  27.10n ±  3%   26.64n ±  1%        ~ (p=0.168 n=9)
FileSet_Position/manyfiles-8             209.9n ± 17%   154.1n ±  9%  -26.58% (p=0.000 n=9)
FileSet_AddExistingFiles/sequence-8   395930.3µ ±  4%   280.8µ ± 10%  -99.93% (p=0.000 n=9)

Updates #73205

Change-Id: Iea59c624a6cedadc2673987a5eb0ebece67af9e9
Reviewed-on: https://go-review.googlesource.com/c/go/+/675736
Reviewed-by: Robert Findley <rfindley@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>

0 files changed, 0 insertions, 0 deletions