internal/impl: support legacy unknown fields

Add wrapper data structures to get legacy XXX_unrecognized fields to support
the new protoreflect.UnknownFields interface. This is a challenge since the
field is a []byte, which does not give us much flexibility to work with
in terms of choice of data structures.

This implementation is relatively naive where every operation is O(n) since
it needs to strip through the entire []byte each time. The Range operation
operates slightly differently from ranging over Go maps since it presents a
stale version of RawFields should a mutation occur while ranging.
This distinction is unlikely to affect anyone in practice.

Change-Id: Ib3247cb827f9a0dd6c2192cd59830dca5eef8257
Reviewed-on: https://go-review.googlesource.com/c/144697
Reviewed-by: Damien Neil <dneil@google.com>
diff --git a/internal/impl/legacy_test.go b/internal/impl/legacy_test.go
index fc3a2ee..32253f3 100644
--- a/internal/impl/legacy_test.go
+++ b/internal/impl/legacy_test.go
@@ -5,9 +5,12 @@
 package impl
 
 import (
+	"bytes"
+	"math"
 	"reflect"
 	"testing"
 
+	"github.com/golang/protobuf/v2/internal/encoding/pack"
 	"github.com/golang/protobuf/v2/internal/pragma"
 	pref "github.com/golang/protobuf/v2/reflect/protoreflect"
 	ptype "github.com/golang/protobuf/v2/reflect/prototype"
@@ -25,7 +28,7 @@
 var fileDescLP2 = mustLoadFileDesc(LP2FileDescriptor)
 var fileDescLP3 = mustLoadFileDesc(LP3FileDescriptor)
 
-func TestLegacy(t *testing.T) {
+func TestLegacyDescriptor(t *testing.T) {
 	tests := []struct {
 		got  pref.Descriptor
 		want pref.Descriptor
@@ -133,3 +136,122 @@
 		})
 	}
 }
+
+func TestLegacyUnknown(t *testing.T) {
+	rawOf := func(toks ...pack.Token) pref.RawFields {
+		return pref.RawFields(pack.Message(toks).Marshal())
+	}
+	raw1a := rawOf(pack.Tag{1, pack.VarintType}, pack.Svarint(-4321))                // 08c143
+	raw1b := rawOf(pack.Tag{1, pack.Fixed32Type}, pack.Uint32(0xdeadbeef))           // 0defbeadde
+	raw1c := rawOf(pack.Tag{1, pack.Fixed64Type}, pack.Float64(math.Pi))             // 09182d4454fb210940
+	raw2a := rawOf(pack.Tag{2, pack.BytesType}, pack.String("hello, world!"))        // 120d68656c6c6f2c20776f726c6421
+	raw2b := rawOf(pack.Tag{2, pack.VarintType}, pack.Uvarint(1234))                 // 10d209
+	raw3a := rawOf(pack.Tag{3, pack.StartGroupType}, pack.Tag{3, pack.EndGroupType}) // 1b1c
+	raw3b := rawOf(pack.Tag{3, pack.BytesType}, pack.Bytes("\xde\xad\xbe\xef"))      // 1a04deadbeef
+
+	joinRaw := func(bs ...pref.RawFields) (out []byte) {
+		for _, b := range bs {
+			out = append(out, b...)
+		}
+		return out
+	}
+
+	var fs legacyUnknownBytes
+	if got, want := fs.Len(), 0; got != want {
+		t.Errorf("Len() = %d, want %d", got, want)
+	}
+	if got, want := []byte(fs), joinRaw(); !bytes.Equal(got, want) {
+		t.Errorf("data mismatch:\ngot:  %x\nwant: %x", got, want)
+	}
+
+	fs.Set(1, raw1a)
+	fs.Set(1, append(fs.Get(1), raw1b...))
+	fs.Set(1, append(fs.Get(1), raw1c...))
+	if got, want := fs.Len(), 1; got != want {
+		t.Errorf("Len() = %d, want %d", got, want)
+	}
+	if got, want := []byte(fs), joinRaw(raw1a, raw1b, raw1c); !bytes.Equal(got, want) {
+		t.Errorf("data mismatch:\ngot:  %x\nwant: %x", got, want)
+	}
+
+	fs.Set(2, raw2a)
+	if got, want := fs.Len(), 2; got != want {
+		t.Errorf("Len() = %d, want %d", got, want)
+	}
+	if got, want := []byte(fs), joinRaw(raw1a, raw1b, raw1c, raw2a); !bytes.Equal(got, want) {
+		t.Errorf("data mismatch:\ngot:  %x\nwant: %x", got, want)
+	}
+
+	if got, want := fs.Get(1), joinRaw(raw1a, raw1b, raw1c); !bytes.Equal(got, want) {
+		t.Errorf("Get(%d) = %x, want %x", 1, got, want)
+	}
+	if got, want := fs.Get(2), joinRaw(raw2a); !bytes.Equal(got, want) {
+		t.Errorf("Get(%d) = %x, want %x", 2, got, want)
+	}
+	if got, want := fs.Get(3), joinRaw(); !bytes.Equal(got, want) {
+		t.Errorf("Get(%d) = %x, want %x", 3, got, want)
+	}
+
+	fs.Set(1, nil) // remove field 1
+	if got, want := fs.Len(), 1; got != want {
+		t.Errorf("Len() = %d, want %d", got, want)
+	}
+	if got, want := []byte(fs), joinRaw(raw2a); !bytes.Equal(got, want) {
+		t.Errorf("data mismatch:\ngot:  %x\nwant: %x", got, want)
+	}
+
+	// Simulate manual appending of raw field data.
+	fs = append(fs, joinRaw(raw3a, raw1a, raw1b, raw3b, raw2b, raw1c)...)
+	if got, want := fs.Len(), 3; got != want {
+		t.Errorf("Len() = %d, want %d", got, want)
+	}
+
+	// Verify range iteration order.
+	var i int
+	want := []struct {
+		num pref.FieldNumber
+		raw pref.RawFields
+	}{
+		{3, joinRaw(raw3a, raw3b)},
+		{2, joinRaw(raw2a, raw2b)},
+		{1, joinRaw(raw1a, raw1b, raw1c)},
+	}
+	fs.Range(func(num pref.FieldNumber, raw pref.RawFields) bool {
+		if i < len(want) {
+			if num != want[i].num || !bytes.Equal(raw, want[i].raw) {
+				t.Errorf("Range(%d) = (%d, %x), want (%d, %x)", i, num, raw, want[i].num, want[i].raw)
+			}
+		} else {
+			t.Errorf("unexpected Range iteration: %d", i)
+		}
+		i++
+		return true
+	})
+
+	fs.Set(2, fs.Get(2)) // moves field 2 to the end
+	if got, want := fs.Len(), 3; got != want {
+		t.Errorf("Len() = %d, want %d", got, want)
+	}
+	if got, want := []byte(fs), joinRaw(raw3a, raw1a, raw1b, raw3b, raw1c, raw2a, raw2b); !bytes.Equal(got, want) {
+		t.Errorf("data mismatch:\ngot:  %x\nwant: %x", got, want)
+	}
+	fs.Set(1, nil) // remove field 1
+	if got, want := fs.Len(), 2; got != want {
+		t.Errorf("Len() = %d, want %d", got, want)
+	}
+	if got, want := []byte(fs), joinRaw(raw3a, raw3b, raw2a, raw2b); !bytes.Equal(got, want) {
+		t.Errorf("data mismatch:\ngot:  %x\nwant: %x", got, want)
+	}
+
+	// Remove all fields.
+	fs.Range(func(n pref.FieldNumber, b pref.RawFields) bool {
+		fs.Set(n, nil)
+		return true
+	})
+	if got, want := fs.Len(), 0; got != want {
+		t.Errorf("Len() = %d, want %d", got, want)
+	}
+	if got, want := []byte(fs), joinRaw(); !bytes.Equal(got, want) {
+		t.Errorf("data mismatch:\ngot:  %x\nwant: %x", got, want)
+	}
+}