4 files changed, 133 insertions, 1 deletions

diff --git a/internal/norm/fuzz_test.go b/internal/norm/fuzz_test.go
index fde62a0..27deadc 100644
--- a/internal/norm/fuzz_test.go
+++ b/internal/norm/fuzz_test.go
@@ -2,7 +2,11 @@
 
 package norm
 
-import "testing"
+import (
+	"strings"
+	"testing"
+	"unicode/utf8"
+)
 
 // FuzzTextIdempotent: normalising text twice changes nothing more than
 // normalising it once, under every case and fold setting, and so for names.
@@ -28,3 +32,33 @@ func FuzzTextIdempotent(f *testing.F) {
 		}
 	})
 }
+
+// FuzzFoldMapped: FoldMapped's text is always Fold's, and any part of it
+// leads back to original text that folds to something holding that part.
+func FuzzFoldMapped(f *testing.F) {
+	for _, s := range []string{"Łódź-faktura.pdf", "straße", "áb", "\xff\xfeé", "́a", "Æsir"} {
+		f.Add(s, 0, 2)
+	}
+	f.Fuzz(func(t *testing.T, s string, a, b int) {
+		m := FoldMapped(s)
+		if m.Text != Fold(s) {
+			t.Fatalf("FoldMapped(%q).Text = %q, Fold = %q", s, m.Text, Fold(s))
+		}
+		n := len(m.Text) + 1
+		a, b = (a%n+n)%n, (b%n+n)%n
+		if a > b {
+			a, b = b, a
+		}
+		// A regex match starts and ends on whole characters.
+		for a < len(m.Text) && !utf8.RuneStart(m.Text[a]) {
+			a--
+		}
+		for b < len(m.Text) && !utf8.RuneStart(m.Text[b]) {
+			b--
+		}
+		src := m.Source(a, b)
+		if !strings.Contains(Fold(src), m.Text[a:b]) {
+			t.Fatalf("FoldMapped(%q).Source(%d, %d) = %q, which folds to %q, not holding %q", s, a, b, src, Fold(src), m.Text[a:b])
+		}
+	})
+}
diff --git a/internal/norm/norm.go b/internal/norm/norm.go
index 701f765..bff2127 100644
--- a/internal/norm/norm.go
+++ b/internal/norm/norm.go
@@ -8,6 +8,7 @@ import (
 	"fmt"
 	"strings"
 	"unicode"
+	"unicode/utf8"
 
 	unorm "golang.org/x/text/unicode/norm"
 )
@@ -70,6 +71,69 @@ func Fold(s string) string {
 	return b.String()
 }
 
+// Folded is Fold's result with a way back to the text it was folded from.
+type Folded struct {
+	Text string // Fold(src)
+
+	src        string
+	same       bool  // Text is src (ASCII)
+	start, end []int // per byte of Text, the bounds in src of the character it came from; nil when no map exists
+}
+
+// FoldMapped folds s like Fold and keeps, for every byte of the result, the
+// original character it came from, so a regex match on the folded text can
+// be read back from s with its diacritics. The map is built by folding one
+// character at a time (a run of invalid bytes counts as one, as Fold's
+// U+FFFD does); in the rare case that differs from Fold's decomposition of
+// the whole string (combining marks NFD reorders), there is no map and
+// Source returns the folded text.
+func FoldMapped(s string) Folded {
+	text := Fold(s)
+	if text == s {
+		return Folded{Text: text, src: s, same: true}
+	}
+	var b strings.Builder
+	start := make([]int, 0, len(text))
+	end := make([]int, 0, len(text))
+	for i := 0; i < len(s); {
+		j, piece := i, ""
+		if r, w := utf8.DecodeRuneInString(s[i:]); r == utf8.RuneError && w == 1 {
+			for j < len(s) {
+				if r, w := utf8.DecodeRuneInString(s[j:]); r != utf8.RuneError || w != 1 {
+					break
+				}
+				j++
+			}
+			piece = "\ufffd"
+		} else {
+			j = i + w
+			piece = Fold(s[i:j])
+		}
+		b.WriteString(piece)
+		for range len(piece) {
+			start = append(start, i)
+			end = append(end, j)
+		}
+		i = j
+	}
+	if b.String() != text {
+		return Folded{Text: text, src: s}
+	}
+	return Folded{Text: text, src: s, start: start, end: end}
+}
+
+// Source returns the original text that Text[a:b] was folded from, widened
+// to whole characters; without a map, Text[a:b] itself.
+func (f Folded) Source(a, b int) string {
+	switch {
+	case f.same || f.start == nil:
+		return f.Text[a:b]
+	case a >= b:
+		return ""
+	}
+	return f.src[f.start[a]:f.end[b-1]]
+}
+
 // Text puts s into the form content and keywords are compared in: Fold if
 // fold, strings.ToLower if ignoreCase, then every run of Unicode white
 // space becomes one ASCII space and both ends are trimmed.
diff --git a/internal/norm/norm_test.go b/internal/norm/norm_test.go
index 885c6f7..a165b32 100644
--- a/internal/norm/norm_test.go
+++ b/internal/norm/norm_test.go
@@ -73,3 +73,33 @@ func TestFoldASCIINoAlloc(t *testing.T) {
 		t.Errorf("Fold allocates %v times on ASCII input", n)
 	}
 }
+
+// TestFoldMappedSource: a part of the folded text leads back to the original
+// characters it came from, widened to whole characters - so a capture can be
+// written with its diacritics.
+func TestFoldMappedSource(t *testing.T) {
+	cases := []struct {
+		in, folded string
+		a, b       int
+		want       string
+	}{
+		{"Łódź-faktura.pdf", "Lodz-faktura.pdf", 0, 4, "Łódź"},
+		{"Łódź-faktura.pdf", "Lodz-faktura.pdf", 5, 12, "faktura"},
+		{"straße", "strasse", 4, 5, "ß"},
+		{"áb", "ab", 0, 1, "a"},
+		{"áb", "ab", 1, 2, "b"},
+		{"\xff\xfeé", "�e", 0, 3, "\xff\xfe"},
+		{"plain.txt", "plain.txt", 0, 5, "plain"},
+		{"Łódź", "Lodz", 2, 2, ""},
+	}
+	for _, c := range cases {
+		f := FoldMapped(c.in)
+		if f.Text != c.folded || f.Text != Fold(c.in) {
+			t.Errorf("FoldMapped(%q).Text = %q, want %q (Fold)", c.in, f.Text, c.folded)
+			continue
+		}
+		if got := f.Source(c.a, c.b); got != c.want {
+			t.Errorf("FoldMapped(%q).Source(%d, %d) = %q, want %q", c.in, c.a, c.b, got, c.want)
+		}
+	}
+}
diff --git a/internal/norm/testdata/fuzz/FuzzFoldMapped/ef66462f0d689aef b/internal/norm/testdata/fuzz/FuzzFoldMapped/ef66462f0d689aef
new file mode 100644
index 0000000..f77399e
--- /dev/null
+++ b/internal/norm/testdata/fuzz/FuzzFoldMapped/ef66462f0d689aef
@@ -0,0 +1,4 @@
+go test fuzz v1
+string("0\u0381")
+int(0)
+int(2)