code review 6971044: exp/locale/collate: include composed characters into th...

exp/locale/collate: include composed characters into the table. This eliminates
the need to decompose characters for the majority of cases.  This considerably
speeds up collation while increasing the table size minimally.

To detect non-normalized strings, rather than relying on exp/norm, the table
now includes CCC information. The inclusion of this information does not
increase table size.

DETAILS
 - Raw collation elements are now a struct that includes the CCC, rather
   than a slice of ints.
 - Builder now ensures that NFD and NFC counterparts are included in the table.
   This also fixes a bug for Korean which is responsible for most of the growth
   of the table size.
 - As there is no more normalization step, code should now handle both strings
   and byte slices as input. Introduced source type to facilitate this.

NOTES
 - This change does not handle normalization correctly entirely for contractions.
   This causes a few failures with the regtest. table_test.go contains a few
   uncommented tests that can be enabled once this is fixed.  The easiest is to
   fix this once we have the new norm.Iter.
 - Removed a test cases in table_test that covers cases that are now guaranteed
   to not exist.

[mpvl, 2012-12-19 09:47:48]

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

I'd like you to review this change to
https://go.googlecode.com/hg

[rsc, 2012-12-21 20:12:52]

LGTM

Does the trie encoding make sure that you don't accept 4-byte sequences with
value > 0x10FFFF, and that you don't, say, accept a 2-byte sequence with value
0x00 ?

https://codereview.appspot.com/6971044/diff/2001/src/pkg/exp/locale/collate/b...
File src/pkg/exp/locale/collate/build/builder.go (right):

https://codereview.appspot.com/6971044/diff/2001/src/pkg/exp/locale/collate/b...
src/pkg/exp/locale/collate/build/builder.go:662:
log.Fatalf("%s:processContractions: unexpected length for '%X'; len=%d; want
%d", o.id, e.runes, sn, len(str))
space after %s

https://codereview.appspot.com/6971044/diff/2001/src/pkg/exp/locale/collate/b...
src/pkg/exp/locale/collate/build/builder.go:666: log.Fatalf("%s:multiple
contractions for position %d for rune %U", o.id, p, e.runes[0])
same

https://codereview.appspot.com/6971044/diff/2001/src/pkg/exp/locale/collate/c...
File src/pkg/exp/locale/collate/collate.go (right):

https://codereview.appspot.com/6971044/diff/2001/src/pkg/exp/locale/collate/c...
src/pkg/exp/locale/collate/collate.go:292: func (src source) done() bool {
probably all of these should be pointer receivers.

[mpvl_google.com, 2012-12-24 15:20:30]

Good point regarding trie.   4-byte values > 0x10FFFF are treated as
unknown code points and get assigned an implicit weight (will simply be
sorted at the end). Sequences with a too-small value will be treated in the
same way.  I will ensure the semantics is the same as with unicode/utf8.
 Interesting example, though: Modified UTF-8 actually *requires* the value
0x00 to be encoded with 2 bytes, allowing the 1-byte 0x00 to be used as a
terminator. Java uses this for object serialization. To disallow it is
consistent with the recent change of disallowing surrogate pairs encoded in
UTF-8, though.


On Fri, Dec 21, 2012 at 9:12 PM, <rsc@golang.org> wrote:

> LGTM
>
> Does the trie encoding make sure that you don't accept 4-byte sequences
> with value > 0x10FFFF, and that you don't, say, accept a 2-byte sequence
> with value 0x00 ?
>
>
>
> https://codereview.appspot.**com/6971044/diff/2001/src/pkg/**
>
exp/locale/collate/build/**builder.go<https://codereview.appspot.com/6971044/diff/2001/src/pkg/exp/locale/collate/build/builder.go>
> File src/pkg/exp/locale/collate/**build/builder.go (right):
>
> https://codereview.appspot.**com/6971044/diff/2001/src/pkg/**
>
exp/locale/collate/build/**builder.go#newcode662<https://codereview.appspot.com/6971044/diff/2001/src/pkg/exp/locale/collate/build/builder.go#newcode662>
> src/pkg/exp/locale/collate/**build/builder.go:662:
> log.Fatalf("%s:**processContractions: unexpected length for '%X'; len=%d;
> want %d", o.id, e.runes, sn, len(str))
> space after %s
>
> https://codereview.appspot.**com/6971044/diff/2001/src/pkg/**
>
exp/locale/collate/build/**builder.go#newcode666<https://codereview.appspot.com/6971044/diff/2001/src/pkg/exp/locale/collate/build/builder.go#newcode666>
> src/pkg/exp/locale/collate/**build/builder.go:666: log.Fatalf("%s:multiple
> contractions for position %d for rune %U", o.id, p, e.runes[0])
> same
>
> https://codereview.appspot.**com/6971044/diff/2001/src/pkg/**
>
exp/locale/collate/collate.go<https://codereview.appspot.com/6971044/diff/2001/src/pkg/exp/locale/collate/collate.go>
> File src/pkg/exp/locale/collate/**collate.go (right):
>
> https://codereview.appspot.**com/6971044/diff/2001/src/pkg/**
>
exp/locale/collate/collate.go#**newcode292<https://codereview.appspot.com/6971044/diff/2001/src/pkg/exp/locale/collate/collate.go#newcode292>
> src/pkg/exp/locale/collate/**collate.go:292: func (src source) done() bool
> {
> probably all of these should be pointer receivers.
>
>
https://codereview.appspot.**com/6971044/<https://codereview.appspot.com/6971...
>



-- 
Trying this for a while: http://go/OnlyCheckEmailTwiceADay.
Marcel van Lohuizen -- Google Switzerland GmbH -- Identifikationsnummer:
CH-020.4.028.116-1

[mpvl, 2012-12-24 15:41:12]

https://codereview.appspot.com/6971044/diff/2001/src/pkg/exp/locale/collate/b...
File src/pkg/exp/locale/collate/build/builder.go (right):

https://codereview.appspot.com/6971044/diff/2001/src/pkg/exp/locale/collate/b...
src/pkg/exp/locale/collate/build/builder.go:662:
log.Fatalf("%s:processContractions: unexpected length for '%X'; len=%d; want
%d", o.id, e.runes, sn, len(str))
On 2012/12/21 20:12:52, rsc wrote:
> space after %s

Done.

https://codereview.appspot.com/6971044/diff/2001/src/pkg/exp/locale/collate/b...
src/pkg/exp/locale/collate/build/builder.go:666: log.Fatalf("%s:multiple
contractions for position %d for rune %U", o.id, p, e.runes[0])
On 2012/12/21 20:12:52, rsc wrote:
> same

Done.

https://codereview.appspot.com/6971044/diff/2001/src/pkg/exp/locale/collate/c...
File src/pkg/exp/locale/collate/collate.go (right):

https://codereview.appspot.com/6971044/diff/2001/src/pkg/exp/locale/collate/c...
src/pkg/exp/locale/collate/collate.go:292: func (src source) done() bool {
On 2012/12/21 20:12:52, rsc wrote:
> probably all of these should be pointer receivers.

Done.

[mpvl, 2012-12-24 15:42:49]

*** Submitted as https://code.google.com/p/go/source/detail?r=4115d29db6bb ***

exp/locale/collate: include composed characters into the table. This eliminates
the need to decompose characters for the majority of cases.  This considerably
speeds up collation while increasing the table size minimally.

To detect non-normalized strings, rather than relying on exp/norm, the table
now includes CCC information. The inclusion of this information does not
increase table size.

DETAILS
 - Raw collation elements are now a struct that includes the CCC, rather
   than a slice of ints.
 - Builder now ensures that NFD and NFC counterparts are included in the table.
   This also fixes a bug for Korean which is responsible for most of the growth
   of the table size.
 - As there is no more normalization step, code should now handle both strings
   and byte slices as input. Introduced source type to facilitate this.

NOTES
 - This change does not handle normalization correctly entirely for
contractions.
   This causes a few failures with the regtest. table_test.go contains a few
   uncommented tests that can be enabled once this is fixed.  The easiest is to
   fix this once we have the new norm.Iter.
 - Removed a test cases in table_test that covers cases that are now guaranteed
   to not exist.

R=rsc, mpvl
CC=golang-dev
https://codereview.appspot.com/6971044