unicode/norm: let any starter block composition in compose

reorderBuffer.compose only refreshed s, the index of the last starter,
inside the ii.combinesBackward() branch. A rune that does not combine
backward therefore left s pointing at whatever starter preceded it, and
the next backward-combining mark composed with that stale starter even
though an intervening starter should have blocked it.

For example, NFKC of U+16D68 U+FB01 U+113C2 U+0300 U+0316 decomposes to
U+16D68 f i U+113C2 U+0316 U+0300. U+0316 does not combine backward, so
s was left pointing at the "i" rather than at the starter U+113C2, and
U+0300 composed with the "i" to give U+00EC, dropping a code point and
producing a string that is not canonically equivalent to the input.

Update s on every iteration, as combineHangul already does.

Fixes golang/go#81001.

Change-Id: I4d2332b4a0c44d60bd0961036391617a728c12df
Reviewed-on: https://go-review.googlesource.com/c/text/+/822081
Reviewed-by: David Chase <drchase@google.com>
LUCI-TryBot-Result: golang-scoped@luci-project-accounts.iam.gserviceaccount.com <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Damien Neil <dneil@google.com>

unicode/norm/composition.go

diff --git a/unicode/norm/composition.go b/unicode/norm/composition.go
index 1ad6b5b..e024e74 100644
--- a/unicode/norm/composition.go
+++ b/unicode/norm/composition.go
@@ -494,25 +494,27 @@
 			return
 		}
 		ii := b[i]
+		// Track the last starter unconditionally: b[i] must be blocked by
+		// any starter between it and s, even one that b[i] itself cannot
+		// combine with, and even if the runes in between never enter the
+		// combinesBackward branch below.
+		cccB := b[k-1].ccc
+		cccC := ii.ccc
+		blocked := false // b[i] blocked by starter or greater or equal CCC?
+		if cccB == 0 {
+			s = k - 1
+		} else {
+			blocked = s != k-1 && cccB >= cccC
+		}
 		// We can only use combineForward as a filter if we later
 		// get the info for the combined character. This is more
 		// expensive than using the filter. Using combinesBackward()
 		// is safe.
-		if ii.combinesBackward() {
-			cccB := b[k-1].ccc
-			cccC := ii.ccc
-			blocked := false // b[i] blocked by starter or greater or equal CCC?
-			if cccB == 0 {
-				s = k - 1
-			} else {
-				blocked = s != k-1 && cccB >= cccC
-			}
-			if !blocked {
-				combined := combine(rb.runeAt(s), rb.runeAt(i))
-				if combined != 0 {
-					rb.assignRune(s, combined)
-					continue
-				}
+		if ii.combinesBackward() && !blocked {
+			combined := combine(rb.runeAt(s), rb.runeAt(i))
+			if combined != 0 {
+				rb.assignRune(s, combined)
+				continue
 			}
 		}
 		b[k] = b[i]

unicode/norm/composition_test.go

diff --git a/unicode/norm/composition_test.go b/unicode/norm/composition_test.go
index 3bc034c..5aab245 100644
--- a/unicode/norm/composition_test.go
+++ b/unicode/norm/composition_test.go
@@ -178,3 +178,27 @@
 		}
 	}
 }
+
+// TestCompositionBlockedByStarter tests that a starter blocks composition
+// across it even when the starter itself takes no part in any composition and
+// the runes between it and the following mark never combine backward.
+// See go.dev/issue/81001.
+func TestCompositionBlockedByStarter(t *testing.T) {
+	tests := []struct {
+		name    string
+		f       Form
+		in, out string
+	}{
+		// U+113C2 is a starter (ccc 0), so it blocks U+0300 from
+		// composing with the "i" of the U+FB01 expansion.
+		{"NFKC", NFKC, "\U00016d68\ufb01\U000113c2\u0300\u0316", "\U00016d68fi\U000113c2\u0316\u0300"},
+		{"NFC", NFC, "i\U000113c2\u0300\u0316", "i\U000113c2\u0316\u0300"},
+		// Without the intervening starter the composition must still happen.
+		{"NFC", NFC, "i\u0300\u0316", "\u00ec\u0316"},
+	}
+	for _, test := range tests {
+		if got := test.f.String(test.in); got != test.out {
+			t.Errorf("%s.String(%+q) = %+q; want %+q", test.name, test.in, got, test.out)
+		}
+	}
+}