playground: interleave standard output and error correctly

The change reconstructs the correct interleaving of the standard
output and error. Playground buffers those streams separetely
and performs a sorted merge.

The change depends on the change https://golang.org/cl/105235,
which makes Playground timestamps change when the stream fd changes.
It's recommended to merge this change after the CL 105235 went into
go release, but it can be picked with CL 106216 until that happens.

Fixes golang/go#24615
Fixes golang/go#24659

Change-Id: I76f8815c47e8961d5c435e55c761c7a7bf3920ce
Reviewed-on: https://go-review.googlesource.com/105496
Reviewed-by: Andrew Bonventre <andybons@golang.org>
Reviewed-by: Bryan C. Mills <bcmills@google.com>
diff --git a/play.go b/play.go
index fd56676..e160220 100644
--- a/play.go
+++ b/play.go
@@ -35,41 +35,27 @@
 // 	4 bytes: big-endian int32, length of the next write
 //
 type Recorder struct {
-	mu     sync.Mutex
-	writes []recorderWrite
+	stdout, stderr recorderWriter
 }
 
-type recorderWrite struct {
-	b    []byte
-	kind string
-}
-
-func (r *Recorder) Stdout() io.Writer { return recorderWriter{r, "stdout"} }
-func (r *Recorder) Stderr() io.Writer { return recorderWriter{r, "stderr"} }
+func (r *Recorder) Stdout() io.Writer { return &r.stdout }
+func (r *Recorder) Stderr() io.Writer { return &r.stderr }
 
 type recorderWriter struct {
-	r    *Recorder
-	kind string
+	mu     sync.Mutex
+	writes []byte
 }
 
-func (w recorderWriter) Write(b []byte) (n int, err error) {
-	w.r.mu.Lock()
-	defer w.r.mu.Unlock()
+func (w *recorderWriter) bytes() []byte {
+	w.mu.Lock()
+	defer w.mu.Unlock()
+	return w.writes[0:len(w.writes):len(w.writes)]
+}
 
-	// Append this write to the previous one if it has the same kind.
-	if len(w.r.writes) > 0 {
-		prev := &w.r.writes[len(w.r.writes)-1]
-		if prev.kind == w.kind {
-			prev.b = append(prev.b, b...)
-			return len(b), nil
-		}
-	}
-
-	// Otherwise, append a new write.
-	w.r.writes = append(w.r.writes, recorderWrite{
-		append([]byte(nil), b...), w.kind,
-	})
-
+func (w *recorderWriter) Write(b []byte) (n int, err error) {
+	w.mu.Lock()
+	defer w.mu.Unlock()
+	w.writes = append(w.writes, b...)
 	return len(b), nil
 }
 
@@ -80,31 +66,36 @@
 }
 
 func (r *Recorder) Events() ([]Event, error) {
-	r.mu.Lock()
-	defer r.mu.Unlock()
+	stdout, stderr := r.stdout.bytes(), r.stderr.bytes()
+
+	evOut, err := decode("stdout", stdout)
+	if err != nil {
+		return nil, err
+	}
+	evErr, err := decode("stderr", stderr)
+	if err != nil {
+		return nil, err
+	}
+
+	events := sortedMerge(evOut, evErr)
 
 	var (
 		out []Event
 		now = epoch
 	)
-	for _, w := range r.writes {
-		events, err := decode(w.kind, w.b)
-		if err != nil {
-			return nil, err
+
+	for _, e := range events {
+		delay := e.time.Sub(now)
+		if delay < 0 {
+			delay = 0
 		}
-		for _, e := range events {
-			delay := e.time.Sub(now)
-			if delay < 0 {
-				delay = 0
-			}
-			out = append(out, Event{
-				Message: string(sanitize(e.msg)),
-				Kind:    e.kind,
-				Delay:   delay,
-			})
-			if delay > 0 {
-				now = e.time
-			}
+		out = append(out, Event{
+			Message: string(sanitize(e.msg)),
+			Kind:    e.kind,
+			Delay:   delay,
+		})
+		if delay > 0 {
+			now = e.time
 		}
 	}
 	return out, nil
@@ -184,6 +175,31 @@
 	return events, nil
 }
 
+// Sorted merge of two slices of events into one slice.
+func sortedMerge(a, b []event) []event {
+	if len(a) == 0 {
+		return b
+	}
+	if len(b) == 0 {
+		return a
+	}
+
+	sorted := make([]event, 0, len(a)+len(b))
+	i, j := 0, 0
+	for i < len(a) && j < len(b) {
+		if a[i].time.Before(b[j].time) {
+			sorted = append(sorted, a[i])
+			i++
+		} else {
+			sorted = append(sorted, b[j])
+			j++
+		}
+	}
+	sorted = append(sorted, a[i:]...)
+	sorted = append(sorted, b[j:]...)
+	return sorted
+}
+
 // sanitize scans b for invalid utf8 code points. If found, it reconstructs
 // the slice replacing the invalid codes with \uFFFD, properly encoded.
 func sanitize(b []byte) []byte {
diff --git a/play_test.go b/play_test.go
index 69f9dd4..bf02993 100644
--- a/play_test.go
+++ b/play_test.go
@@ -19,22 +19,22 @@
 	stdout.Write([]byte("head"))
 	stdout.Write(pbWrite(0, "one"))
 	stdout.Write(pbWrite(0, "two"))
+
 	stderr.Write(pbWrite(1*time.Second, "three"))
-	stdout.Write(pbWrite(2*time.Second, "four"))
-	stderr.Write(pbWrite(3*time.Second, "five"))
+	stderr.Write(pbWrite(2*time.Second, "five"))
+	stdout.Write(pbWrite(2*time.Second-time.Nanosecond, "four"))
+	stderr.Write(pbWrite(2*time.Second, "six"))
+
 	stdout.Write([]byte("middle"))
-	stderr.Write(pbWrite(4*time.Second, "six"))
-	stdout.Write(pbWrite(4*time.Second, "seven"))
+	stdout.Write(pbWrite(3*time.Second, "seven"))
 	stdout.Write([]byte("tail"))
 
 	want := []Event{
 		{"headonetwo", "stdout", 0},
 		{"three", "stderr", time.Second},
-		{"four", "stdout", time.Second},
-		{"five", "stderr", time.Second},
-		{"middle", "stdout", 0},
-		{"six", "stderr", time.Second},
-		{"seventail", "stdout", 0},
+		{"fourmiddle", "stdout", time.Second - time.Nanosecond},
+		{"fivesix", "stderr", time.Nanosecond},
+		{"seventail", "stdout", time.Second},
 	}
 
 	got, err := r.Events()
@@ -42,7 +42,7 @@
 		t.Fatalf("Decode: %v", err)
 	}
 	if !reflect.DeepEqual(got, want) {
-		t.Errorf("got %v, want %v", got, want)
+		t.Errorf("got: \n%v,\nwant \n%v", got, want)
 	}
 }