From b575e3ca99501448cf6bed6e82a83f9a99d938d8 Mon Sep 17 00:00:00 2001
From: Marcel van Lohuizen <mpvl@golang.org>
Date: Thu, 25 Oct 2012 13:02:31 +0200
Subject: [PATCH] exp/locale/collate: slightly changed collation elements: -
 Allow secondary values below the default value in second form. This is   to
 support before tags for secondary values, as used by Chinese. - Eliminate
 collation elements that are guaranteed to be immaterial   after a weight
 increment.

R=r
CC=golang-dev
https://golang.org/cl/6739051
---
 src/pkg/exp/locale/collate/build/colelem.go   | 36 ++++++++++++-------
 .../exp/locale/collate/build/colelem_test.go  | 24 ++++++++-----
 src/pkg/exp/locale/collate/colelem.go         |  2 +-
 src/pkg/exp/locale/collate/colelem_test.go    |  2 +-
 4 files changed, 40 insertions(+), 24 deletions(-)

diff --git a/src/pkg/exp/locale/collate/build/colelem.go b/src/pkg/exp/locale/collate/build/colelem.go
index 343aa740a7..ff63eb594c 100644
--- a/src/pkg/exp/locale/collate/build/colelem.go
+++ b/src/pkg/exp/locale/collate/build/colelem.go
@@ -70,7 +70,7 @@ func makeCE(weights []int) (uint32, error) {
 			ce = uint32(weights[0]<<maxSecondaryCompactBits + weights[1])
 			ce |= isPrimary
 		} else {
-			d := weights[1] - defaultSecondary
+			d := weights[1] - defaultSecondary + 4
 			if d >= 1<<maxSecondaryDiffBits || d < 0 {
 				return 0, fmt.Errorf("makeCE: secondary weight diff out of bounds: %x < 0 || %x > %x", d, d, 1<<maxSecondaryDiffBits)
 			}
@@ -258,21 +258,31 @@ func convertLargeWeights(elems [][]int) (res [][]int, err error) {
 // nextWeight computes the first possible collation weights following elems
 // for the given level.
 func nextWeight(level collate.Level, elems [][]int) [][]int {
-	nce := make([][]int, len(elems))
-	copy(nce, elems)
-
-	if level != collate.Identity {
-		nce[0] = make([]int, len(elems[0]))
-		copy(nce[0], elems[0])
-		nce[0][level]++
-		if level < collate.Secondary {
-			nce[0][collate.Secondary] = defaultSecondary
+	if level == collate.Identity {
+		next := make([][]int, len(elems))
+		copy(next, elems)
+		return next
+	}
+	next := [][]int{make([]int, len(elems[0]))}
+	copy(next[0], elems[0])
+	next[0][level]++
+	if level < collate.Secondary {
+		next[0][collate.Secondary] = defaultSecondary
+	}
+	if level < collate.Tertiary {
+		next[0][collate.Tertiary] = defaultTertiary
+	}
+	// Filter entries that cannot influence ordering.
+	for _, ce := range elems[1:] {
+		skip := true
+		for i := collate.Primary; i < level; i++ {
+			skip = skip && ce[i] == 0
 		}
-		if level < collate.Tertiary {
-			nce[0][collate.Tertiary] = defaultTertiary
+		if !skip {
+			next = append(next, ce)
 		}
 	}
-	return nce
+	return next
 }
 
 func nextVal(elems [][]int, i int, level collate.Level) (index, value int) {
diff --git a/src/pkg/exp/locale/collate/build/colelem_test.go b/src/pkg/exp/locale/collate/build/colelem_test.go
index 28d7c894dc..8a794d3508 100644
--- a/src/pkg/exp/locale/collate/build/colelem_test.go
+++ b/src/pkg/exp/locale/collate/build/colelem_test.go
@@ -34,10 +34,10 @@ func decompCE(in []int) (ce uint32, err error) {
 var ceTests = []ceTest{
 	{normalCE, []int{0, 0, 0}, 0x80000000},
 	{normalCE, []int{0, 0x28, 3}, 0x80002803},
-	{normalCE, []int{100, defaultSecondary, 3}, 0x0000C803},
+	{normalCE, []int{100, defaultSecondary, 3}, 0x0000C883},
 	// non-ignorable primary with non-default secondary
 	{normalCE, []int{100, 0x28, defaultTertiary}, 0x40006428},
-	{normalCE, []int{100, defaultSecondary + 8, 3}, 0x0000C903},
+	{normalCE, []int{100, defaultSecondary + 8, 3}, 0x0000C983},
 	{normalCE, []int{100, 0, 3}, 0xFFFF}, // non-ignorable primary with non-supported secondary
 	{normalCE, []int{100, 1, 3}, 0xFFFF},
 	{normalCE, []int{1 << maxPrimaryBits, defaultSecondary, 0}, 0xFFFF},
@@ -114,18 +114,24 @@ var nextWeightTests = []weightsTest{
 	},
 }
 
-var extra = []int{200, 32, 8, 0}
+var extra = [][]int{{200, 32, 8, 0}, {0, 32, 8, 0}, {0, 0, 8, 0}, {0, 0, 0, 0}}
 
 func TestNextWeight(t *testing.T) {
 	for i, tt := range nextWeightTests {
-		test := func(tt weightsTest, a, gold [][]int) {
+		test := func(l collate.Level, tt weightsTest, a, gold [][]int) {
 			res := nextWeight(tt.level, a)
 			if !equalCEArrays(gold, res) {
-				t.Errorf("%d: expected weights %d; found %d", i, tt.b, res)
+				t.Errorf("%d:%d: expected weights %d; found %d", i, l, gold, res)
+			}
+		}
+		test(-1, tt, tt.a, tt.b)
+		for l := collate.Primary; l <= collate.Tertiary; l++ {
+			if tt.level <= l {
+				test(l, tt, append(tt.a, extra[l]), tt.b)
+			} else {
+				test(l, tt, append(tt.a, extra[l]), append(tt.b, extra[l]))
 			}
 		}
-		test(tt, tt.a, tt.b)
-		test(tt, append(tt.a, extra), append(tt.b, extra))
 	}
 }
 
@@ -137,7 +143,7 @@ var compareTests = []weightsTest{
 		0,
 	},
 	{
-		[][]int{{100, 20, 5, 0}, extra},
+		[][]int{{100, 20, 5, 0}, extra[0]},
 		[][]int{{100, 20, 5, 1}},
 		collate.Primary,
 		1,
@@ -192,6 +198,6 @@ func TestCompareWeights(t *testing.T) {
 			}
 		}
 		test(tt, tt.a, tt.b)
-		test(tt, append(tt.a, extra), append(tt.b, extra))
+		test(tt, append(tt.a, extra[0]), append(tt.b, extra[0]))
 	}
 }
diff --git a/src/pkg/exp/locale/collate/colelem.go b/src/pkg/exp/locale/collate/colelem.go
index 4af71f02de..157b863011 100644
--- a/src/pkg/exp/locale/collate/colelem.go
+++ b/src/pkg/exp/locale/collate/colelem.go
@@ -93,7 +93,7 @@ func splitCE(ce colElem) weights {
 	} else if ce&secondaryMask == 0 {
 		w.tertiary = uint8(ce & 0x1F)
 		ce >>= 5
-		w.secondary = defaultSecondary + uint16(ce&0xF)
+		w.secondary = defaultSecondary + uint16(ce&0xF) - 4
 		ce >>= 4
 		w.primary = uint32(ce)
 	} else {
diff --git a/src/pkg/exp/locale/collate/colelem_test.go b/src/pkg/exp/locale/collate/colelem_test.go
index bcb4ddb68c..b8701f66b5 100644
--- a/src/pkg/exp/locale/collate/colelem_test.go
+++ b/src/pkg/exp/locale/collate/colelem_test.go
@@ -32,7 +32,7 @@ func makeCE(weights []int) colElem {
 			ce = colElem(weights[0]<<maxSecondaryCompactBits + weights[1])
 			ce |= isPrimary
 		} else {
-			d := weights[1] - defaultSecondary
+			d := weights[1] - defaultSecondary + 4
 			ce = colElem(weights[0]<<maxSecondaryDiffBits + d)
 			ce = ce<<maxTertiaryCompactBits + colElem(weights[2])
 		}
-- 
2.48.1