shrink.go

// Copyright 2019 Gregory Petrosyan <gregory.petrosyan@gmail.com>
//
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at https://mozilla.org/MPL/2.0/.

package rapid

import (
	"encoding/binary"
	"fmt"
	"math"
	"math/bits"
	"os"
	"strings"
	"time"
)

const (
	labelLowerFloatExp       = "lower_float_exp"
	labelLowerFloatSignif    = "lower_float_signif"
	labelLowerFloatFrac      = "lower_float_frac"
	labelMinBlockBinSearch   = "minblock_binsearch"
	labelMinBlockShift       = "minblock_shift"
	labelMinBlockSort        = "minblock_sort"
	labelMinBlockTrySmall    = "minblock_trysmall"
	labelMinBlockUnset       = "minblock_unset"
	labelRemoveGroup         = "remove_group"
	labelRemoveGroupAndLower = "remove_group_lower"
	labelRemoveGroupSpan     = "remove_groupspan"
	labelSortGroups          = "sort_groups"
)

func shrink(tb tb, deadline time.Time, rec recordedBits, err *testError, prop func(*T)) ([]uint64, *testError) {
	rec.prune()

	s := &shrinker{
		tb:      tb,
		rec:     rec,
		err:     err,
		prop:    prop,
		visBits: []recordedBits{rec},
		tries:   map[string]int{},
		cache:   map[string]struct{}{},
	}

	buf, err := s.shrink(deadline)

	if flags.debugvis {
		name := fmt.Sprintf("vis-%v.html", strings.Replace(tb.Name(), "/", "_", -1))
		f, err := os.Create(name)
		if err != nil {
			tb.Logf("failed to create debugvis file %v: %v", name, err)
		} else {
			defer func() { _ = f.Close() }()

			if err = visWriteHTML(f, tb.Name(), s.visBits); err != nil {
				tb.Logf("failed to write debugvis file %v: %v", name, err)
			}
		}
	}

	return buf, err
}

type shrinker struct {
	tb      tb
	rec     recordedBits
	err     *testError
	prop    func(*T)
	visBits []recordedBits
	tries   map[string]int
	shrinks int
	cache   map[string]struct{}
	hits    int
}

func (s *shrinker) debugf(verbose_ bool, format string, args ...any) {
	if flags.debug && (!verbose_ || flags.verbose) {
		s.tb.Helper()
		s.tb.Logf("[shrink] "+format, args...)
	}
}

func (s *shrinker) shrink(deadline time.Time) (buf []uint64, err *testError) {
	defer func() {
		if r := recover(); r != nil {
			buf, err = s.rec.data, r.(*testError)
		}
	}()

	i := 0
	for shrinks := -1; s.shrinks > shrinks && time.Now().Before(deadline); i++ {
		shrinks = s.shrinks

		s.debugf(false, "round %v start", i)
		s.removeGroups(deadline)
		s.minimizeBlocks(deadline)

		if s.shrinks == shrinks {
			s.debugf(false, "trying expensive algorithms for round %v", i)
			s.lowerFloatHack(deadline)
			s.removeGroupsAndLower(deadline)
			s.sortGroups(deadline)
			s.removeGroupSpans(deadline)
		}
	}

	tries := 0
	for _, n := range s.tries {
		tries += n
	}
	s.debugf(false, "done, %v rounds total (%v tries, %v shrinks, %v cache hits):\n%v", i, tries, s.shrinks, s.hits, s.tries)

	return s.rec.data, s.err
}

func (s *shrinker) removeGroups(deadline time.Time) {
	for i := 0; i < len(s.rec.groups) && time.Now().Before(deadline); i++ {
		g := s.rec.groups[i]
		if !g.standalone || g.end < 0 {
			continue
		}

		if s.accept(without(s.rec.data, g), labelRemoveGroup, "remove group %q at %v: [%v, %v)", g.label, i, g.begin, g.end) {
			i--
		}
	}
}

func (s *shrinker) minimizeBlocks(deadline time.Time) {
	for i := 0; i < len(s.rec.data) && time.Now().Before(deadline); i++ {
		minimize(s.rec.data[i], func(u uint64, label string) bool {
			buf := append([]uint64(nil), s.rec.data...)
			buf[i] = u
			return s.accept(buf, label, "minimize block %v: %v to %v", i, s.rec.data[i], u)
		})
	}
}

func (s *shrinker) lowerFloatHack(deadline time.Time) {
	for i := 0; i < len(s.rec.groups) && time.Now().Before(deadline); i++ {
		g := s.rec.groups[i]
		if !g.standalone || g.end != g.begin+7 {
			continue
		}

		buf := append([]uint64(nil), s.rec.data...)
		buf[g.begin+3] -= 1
		buf[g.begin+4] = math.MaxUint64
		buf[g.begin+5] = math.MaxUint64
		buf[g.begin+6] = math.MaxUint64

		if !s.accept(buf, labelLowerFloatExp, "lower float exponent of group %q at %v to %v", g.label, i, buf[g.begin+3]) {
			buf := append([]uint64(nil), s.rec.data...)
			buf[g.begin+4] -= 1
			buf[g.begin+5] = math.MaxUint64
			buf[g.begin+6] = math.MaxUint64

			if !s.accept(buf, labelLowerFloatSignif, "lower float significant of group %q at %v to %v", g.label, i, buf[g.begin+4]) {
				buf := append([]uint64(nil), s.rec.data...)
				buf[g.begin+5] -= 1
				buf[g.begin+6] = math.MaxUint64

				s.accept(buf, labelLowerFloatFrac, "lower float frac of group %q at %v to %v", g.label, i, buf[g.begin+5])
			}
		}
	}
}

func (s *shrinker) removeGroupsAndLower(deadline time.Time) {
	for i := 0; i < len(s.rec.data) && time.Now().Before(deadline); i++ {
		if s.rec.data[i] == 0 {
			continue
		}

		buf := append([]uint64(nil), s.rec.data...)
		buf[i] -= 1

		for j := 0; j < len(s.rec.groups); j++ {
			g := s.rec.groups[j]
			if !g.standalone || g.end < 0 || (i >= g.begin && i < g.end) {
				continue
			}

			if s.accept(without(buf, g), labelRemoveGroupAndLower, "lower block %v to %v and remove group %q at %v: [%v, %v)", i, buf[i], g.label, j, g.begin, g.end) {
				i--
				break
			}
		}
	}
}

func (s *shrinker) sortGroups(deadline time.Time) {
	for i := 1; i < len(s.rec.groups) && time.Now().Before(deadline); i++ {
		for j := i; j > 0; {
			g := s.rec.groups[j]
			if !g.standalone || g.end < 0 {
				break
			}

			j_ := j
			for j--; j >= 0; j-- {
				h := s.rec.groups[j]
				if !h.standalone || h.end < 0 || h.end > g.begin || h.label != g.label {
					continue
				}

				buf := append([]uint64(nil), s.rec.data[:h.begin]...)
				buf = append(buf, s.rec.data[g.begin:g.end]...)
				buf = append(buf, s.rec.data[h.end:g.begin]...)
				buf = append(buf, s.rec.data[h.begin:h.end]...)
				buf = append(buf, s.rec.data[g.end:]...)

				if s.accept(buf, labelSortGroups, "swap groups %q at %v: [%v, %v) and %q at %v: [%v, %v)", g.label, j_, g.begin, g.end, h.label, j, h.begin, h.end) {
					break
				}
			}
		}
	}
}

func (s *shrinker) removeGroupSpans(deadline time.Time) {
	for i := 0; i < len(s.rec.groups) && time.Now().Before(deadline); i++ {
		g := s.rec.groups[i]
		if !g.standalone || g.end < 0 {
			continue
		}

		groups := []groupInfo{g}
		for j := i + 1; j < len(s.rec.groups); j++ {
			h := s.rec.groups[j]
			if !h.standalone || h.end < 0 || h.begin < groups[len(groups)-1].end {
				continue
			}

			groups = append(groups, h)
			buf := without(s.rec.data, groups...)

			if s.accept(buf, labelRemoveGroupSpan, "remove %v groups %v", len(groups), groups) {
				i--
				break
			}
		}
	}
}

func (s *shrinker) accept(buf []uint64, label string, format string, args ...any) bool {
	if compareData(buf, s.rec.data) >= 0 {
		return false
	}
	bufStr := dataStr(buf)
	if _, ok := s.cache[bufStr]; ok {
		s.hits++
		return false
	}

	s.debugf(true, label+": trying to reproduce the failure with a smaller test case: "+format, args...)
	s.tries[label]++
	s1 := newBufBitStream(buf, false)
	err1 := checkOnce(newT(s.tb, s1, flags.debug && flags.verbose, nil), s.prop)
	if traceback(err1) != traceback(s.err) {
		s.cache[bufStr] = struct{}{}
		return false
	}

	s.debugf(true, label+": trying to reproduce the failure")
	s.tries[label]++
	s.err = err1
	s2 := newBufBitStream(buf, true)
	err2 := checkOnce(newT(s.tb, s2, flags.debug && flags.verbose, nil), s.prop)
	s.rec = s2.recordedBits
	s.rec.prune()
	assert(compareData(s.rec.data, buf) <= 0)
	if flags.debugvis {
		s.visBits = append(s.visBits, s.rec)
	}
	if !sameError(err1, err2) {
		panic(err2)
	}

	s.debugf(false, label+" success: "+format, args...)
	s.shrinks++

	return true
}

func minimize(u uint64, cond func(uint64, string) bool) uint64 {
	if u == 0 {
		return 0
	}
	for i := uint64(0); i < u && i < small; i++ {
		if cond(i, labelMinBlockTrySmall) {
			return i
		}
	}
	if u <= small {
		return u
	}

	m := &minimizer{best: u, cond: cond}

	m.rShift()
	m.unsetBits()
	m.sortBits()
	m.binSearch()

	return m.best
}

type minimizer struct {
	best uint64
	cond func(uint64, string) bool
}

func (m *minimizer) accept(u uint64, label string) bool {
	if u >= m.best || u < small || !m.cond(u, label) {
		return false
	}
	m.best = u
	return true
}

func (m *minimizer) rShift() {
	for m.accept(m.best>>1, labelMinBlockShift) {
	}
}

func (m *minimizer) unsetBits() {
	size := bits.Len64(m.best)

	for i := size - 1; i >= 0; i-- {
		m.accept(m.best^1<<uint(i), labelMinBlockUnset)
	}
}

func (m *minimizer) sortBits() {
	size := bits.Len64(m.best)

	for i := size - 1; i >= 0; i-- {
		h := uint64(1 << uint(i))
		if m.best&h != 0 {
			for j := 0; j < i; j++ {
				l := uint64(1 << uint(j))
				if m.best&l == 0 {
					if m.accept(m.best^(l|h), labelMinBlockSort) {
						break
					}
				}
			}
		}
	}
}

func (m *minimizer) binSearch() {
	if !m.accept(m.best-1, labelMinBlockBinSearch) {
		return
	}

	i := uint64(0)
	j := m.best
	for i < j {
		h := i + (j-i)/2
		if m.accept(h, labelMinBlockBinSearch) {
			j = h
		} else {
			i = h + 1
		}
	}
}

func without(data []uint64, groups ...groupInfo) []uint64 {
	buf := append([]uint64(nil), data...)

	for i := len(groups) - 1; i >= 0; i-- {
		g := groups[i]
		buf = append(buf[:g.begin], buf[g.end:]...)
	}

	return buf
}

func dataStr(data []uint64) string {
	b := &strings.Builder{}
	err := binary.Write(b, binary.LittleEndian, data)
	assert(err == nil)
	return b.String()
}

func compareData(a []uint64, b []uint64) int {
	if len(a) < len(b) {
		return -1
	}
	if len(a) > len(b) {
		return 1
	}

	for i := range a {
		if a[i] < b[i] {
			return -1
		}
		if a[i] > b[i] {
			return 1
		}
	}

	return 0
}