lazymanifest: use a binary search to do an insertion This makes insertions log(n) plus some memmove() overhead, rather than doing an append followed by an n*log(n) sort. There's probably a lot of performance to be gained by adding a batch-add method, which could be smarter about the memmove()s performed. Includes a couple of extra tests that should help prevent bugs. Thanks to Martin for some significant pre-mail cleanup of this change.

context: don't sort manifest entries The manifest iterator is now pre-sorted, so we can skip this check.

manifest: use custom C implementation of lazymanifest This version is actually lazy, unlike the pure-python version. The latter could stand to be optimized if anyone actually wants to use it seriously. I put no work into it. Before any of my related changes on mozilla-central: perfmanifest tip ! wall 0.268805 comb 0.260000 user 0.260000 sys 0.000000 (best of 37) perftags ! result: 162 ! wall 0.007099 comb 0.000000 user 0.000000 sys 0.000000 (best of 401) perfstatus ! wall 0.415680 comb 0.420000 user 0.260000 sys 0.160000 (best of 24) hgperf export tip ! wall 0.142118 comb 0.140000 user 0.140000 sys 0.000000 (best of 67) after all of my changes on mozilla-central: ./hg: perfmanifest tip ! wall 0.232640 comb 0.230000 user 0.220000 sys 0.010000 (best of 43) perftags ! result: 162 ! wall 0.007057 comb 0.010000 user 0.000000 sys 0.010000 (best of 395) perfstatus ! wall 0.415503 comb 0.420000 user 0.280000 sys 0.140000 (best of 24) hgperf export tip ! wall 0.025096 comb 0.030000 user 0.030000 sys 0.000000 (best of 102) so it's no real change in performance on perf{manifest,tags,status}, but is a huge win on 'hgperf export tip'. There's a little performance work that could still be done here: fastdelta() could be done significantly more intelligently by using the internal state of the lazymanifest type in C, but that seems like good future work.

manifest: split manifestdict into high-level and low-level logic The low-level logic type (_lazymanifest) matches the behavior of the C implementation introduced in a5f1bccd. A future patch will use that when available.

manifest: do parsing inside manifestdict contstructor This shape to the code will make using a C implementation of the manifest storage easier.

manifest: move parsing functions up in file These functions are about to change signature and be hidden inside the manifestdict constructor. Doing the code motion now as an isolated change to make things easier to review.

dispatch: offer suggestions of similar-named commands When suggestions are available, we show those suggestions instead of showing some help output.

dispatch: offer near-edit-distance suggestions for {file,rev}set functions Before this patch, when I have a brain fart and type `hg log -r 'add(foo)'`, hg exits and just says add isn't a function, leading me to the help page for revset to figure out how to spell the function. With this patch, it suggests 'adds' as a function I might have meant.