package queue import ( "context" "errors" "math" "sort" "sync" "testing" "time" ) // fakeTime is a clock and a sleep that never really sleeps. With advance set, a sleep moves the clock // (a single caller); otherwise the clock stands still and the durations asked for are recorded // (many callers reserving slots at the same instant). type fakeTime struct { mu sync.Mutex t time.Time advance bool slept []time.Duration err error // returned by sleep when set } func (f *fakeTime) now() time.Time { f.mu.Lock() defer f.mu.Unlock() return f.t } func (f *fakeTime) move(d time.Duration) { f.mu.Lock() f.t = f.t.Add(d) f.mu.Unlock() } func (f *fakeTime) sleep(ctx context.Context, d time.Duration) error { f.mu.Lock() defer f.mu.Unlock() f.slept = append(f.slept, d) if f.err != nil { return f.err } if f.advance { f.t = f.t.Add(d) } return nil } func (f *fakeTime) durations() []time.Duration { f.mu.Lock() defer f.mu.Unlock() d := append([]time.Duration(nil), f.slept...) sort.Slice(d, func(i, j int) bool { return d[i] < d[j] }) return d } func TestPacerSpacesSendsByTheInterval(t *testing.T) { f := &fakeTime{t: t0, advance: true} p := newPacer(10, f.now, f.sleep) // one slot every 100 ms for i := 0; i < 4; i++ { if err := p.Wait(context.Background()); err != nil { t.Fatal(err) } if want := t0.Add(time.Duration(i) * 100 * time.Millisecond); !f.now().Equal(want) { t.Fatalf("send %d starts at +%v, want +%v", i, f.now().Sub(t0), want.Sub(t0)) } } } func TestPacerFirstSendDoesNotWait(t *testing.T) { f := &fakeTime{t: t0, advance: true} p := newPacer(1, f.now, f.sleep) p.Wait(context.Background()) if len(f.slept) != 0 { t.Fatalf("the first send waited: %v", f.slept) } } func TestPacerAllowsNoBurstAfterAnIdlePeriod(t *testing.T) { f := &fakeTime{t: t0, advance: true} p := newPacer(10, f.now, f.sleep) p.Wait(context.Background()) f.move(10 * time.Second) // idle: slots do not pile up start := f.now() p.Wait(context.Background()) p.Wait(context.Background()) if got := f.now().Sub(start); got != 100*time.Millisecond { t.Fatalf("two sends after an idle period took %v, want exactly one interval", got) } } func TestPacerSleepsOnlyWhatIsLeftOfTheInterval(t *testing.T) { f := &fakeTime{t: t0, advance: true} p := newPacer(10, f.now, f.sleep) p.Wait(context.Background()) f.move(30 * time.Millisecond) // the send itself took 30 ms p.Wait(context.Background()) if len(f.slept) != 1 || f.slept[0] != 70*time.Millisecond { t.Fatalf("slept %v, want [70ms]", f.slept) } } func TestPacerGivesConcurrentCallersDistinctSlots(t *testing.T) { const n = 16 f := &fakeTime{t: t0} // the clock stands still: every caller reserves at the same instant p := newPacer(4, f.now, f.sleep) var wg sync.WaitGroup for i := 0; i < n; i++ { wg.Add(1) go func() { defer wg.Done() if err := p.Wait(context.Background()); err != nil { t.Error(err) } }() } wg.Wait() got := f.durations() // the first caller does not sleep, so n-1 sleeps: 250ms, 500ms... if len(got) != n-1 { t.Fatalf("%d sleeps, want %d: %v", len(got), n-1, got) } for i, d := range got { if want := time.Duration(i+1) * 250 * time.Millisecond; d != want { t.Fatalf("sleeps %v: slot %d is %v, want %v", got, i+1, d, want) } } } func TestPacerCancelledBeforeWaitingReturnsAtOnceAndTakesNoSlot(t *testing.T) { f := &fakeTime{t: t0} p := newPacer(1, f.now, f.sleep) ctx, cancel := context.WithCancel(context.Background()) cancel() if err := p.Wait(ctx); !errors.Is(err, context.Canceled) { t.Fatalf("err = %v", err) } if len(f.slept) != 0 { t.Fatalf("slept %v", f.slept) } // No slot was used: the next caller goes first, without waiting. if err := p.Wait(context.Background()); err != nil || len(f.slept) != 0 { t.Fatalf("err=%v slept=%v", err, f.slept) } } func TestPacerCancelledWhileWaitingGivesTheSlotBack(t *testing.T) { f := &fakeTime{t: t0} p := newPacer(10, f.now, f.sleep) p.Wait(context.Background()) // takes slot 0; the next free slot is +100ms f.err = context.Canceled if err := p.Wait(context.Background()); !errors.Is(err, context.Canceled) { t.Fatalf("err = %v", err) } f.err = nil f.slept = nil p.Wait(context.Background()) if len(f.slept) != 1 || f.slept[0] != 100*time.Millisecond { t.Fatalf("after a cancelled wait the next caller sleeps %v, want [100ms]: the slot was not given back", f.slept) } } func TestPacerCancelledCallerInTheMiddleNeverBlocksTheOthers(t *testing.T) { f := &fakeTime{t: t0} p := newPacer(10, f.now, f.sleep) p.Wait(context.Background()) // B and C reserve +100ms and +200ms; B is cancelled and C still gets out at +200ms at most. var mu sync.Mutex first := true f2 := func(ctx context.Context, d time.Duration) error { if first { first = false return context.Canceled } mu.Lock() defer mu.Unlock() f.slept = append(f.slept, d) return nil } p.sleep = f2 if err := p.Wait(context.Background()); err == nil { t.Fatal("B should fail") } if err := p.Wait(context.Background()); err != nil { t.Fatal(err) } for _, d := range f.slept { if d > 200*time.Millisecond { t.Fatalf("slept %v: later than the slot it reserved", d) } } } func TestNoPacerForARateOfZeroOrLess(t *testing.T) { for _, r := range []float64{0, -1, math.NaN(), math.Inf(-1), math.Inf(1)} { f := &fakeTime{t: t0} p := newPacer(r, f.now, f.sleep) for i := 0; i < 5; i++ { if err := p.Wait(context.Background()); err != nil { t.Fatalf("rate %v: %v", r, err) } } if len(f.slept) != 0 { t.Fatalf("rate %v: slept %v", r, f.slept) } } } func TestNoPacerStillStopsForACancelledContext(t *testing.T) { var p *pacer ctx, cancel := context.WithCancel(context.Background()) cancel() if err := p.Wait(ctx); err == nil { t.Fatal("a cancelled context must not pass") } } func TestPacerAtAVeryLowRateDoesNotOverflow(t *testing.T) { f := &fakeTime{t: t0, advance: true} p := newPacer(1e-300, f.now, f.sleep) for i := 0; i < 3; i++ { p.Wait(context.Background()) } if len(f.slept) != 2 { t.Fatalf("slept %v", f.slept) } for _, d := range f.slept { if d <= 0 || d > maxInterval { t.Fatalf("sleep %v out of range (0, %v]", d, maxInterval) } } } func TestPacerAtAVeryHighRateNeverWaits(t *testing.T) { for _, r := range []float64{1e10, 1e12, 1e300, math.MaxFloat64} { f := &fakeTime{t: t0} p := newPacer(r, f.now, f.sleep) for i := 0; i < 100; i++ { if err := p.Wait(context.Background()); err != nil { t.Fatal(err) } } if len(f.slept) != 0 { t.Fatalf("rate %v: slept %v", r, f.slept) } } } func TestSleepCtxStopsWhenTheContextIsCancelled(t *testing.T) { ctx, cancel := context.WithCancel(context.Background()) cancel() start := time.Now() if err := sleepCtx(ctx, time.Hour); !errors.Is(err, context.Canceled) { t.Fatalf("err = %v", err) } if time.Since(start) > time.Second { t.Fatal("did not return at once") } if err := sleepCtx(context.Background(), time.Millisecond); err != nil { t.Fatal(err) } } func TestPacerKeepsTheSlotsOfLaterCallersWhenAnEarlierOneGivesUp(t *testing.T) { f := &fakeTime{t: t0} release := make(chan struct{}) p := newPacer(10, f.now, nil) p.sleep = func(ctx context.Context, d time.Duration) error { f.sleep(ctx, d) if d == 100*time.Millisecond { <-release // B waits until C has reserved its slot, then gives up return context.Canceled } return nil } p.Wait(context.Background()) // A: slot 0 done := make(chan error) go func() { done <- p.Wait(context.Background()) }() // B: slot +100ms for len(f.durations()) < 1 { time.Sleep(time.Millisecond) } p.Wait(context.Background()) // C: slot +200ms close(release) if err := <-done; err == nil { t.Fatal("B should have given up") } f.mu.Lock() f.slept = nil f.mu.Unlock() p.Wait(context.Background()) // D must come after C, not collide with it if got := f.durations(); len(got) != 1 || got[0] != 300*time.Millisecond { t.Fatalf("D sleeps %v, want [300ms]: it took a slot another caller holds", got) } }