prog: limit prog size when splicing

1 files changed, 194 insertions, 190 deletions

diff --git a/prog/mutation.go b/prog/mutation.go
index 358a2b104..cbf1f53d5 100644
--- a/prog/mutation.go
+++ b/prog/mutation.go
@@ -15,220 +15,224 @@ import (
 func (p *Prog) Mutate(rs rand.Source, ncalls int, ct *ChoiceTable, corpus []*Prog) {
 	r := newRand(rs)
 
-	if r.oneOf(100) && corpus != nil {
-		// Splice with another prog from corpus.
-		p0 := corpus[r.Intn(len(corpus))]
-		p0c := p0.Clone()
-		idx := r.Intn(len(p.Calls))
-		p.Calls = append(p.Calls[:idx], append(p0c.Calls, p.Calls[idx:]...)...)
-	} else {
-		// Mutate current prog without splicing.
-		retry := false
-		for stop := false; !stop || retry; stop = r.oneOf(3) {
-			retry = false
-			switch {
-			case r.nOutOf(20, 31):
-				// Insert a new call.
-				if len(p.Calls) >= ncalls {
-					retry = true
-					continue
-				}
-				idx := r.biasedRand(len(p.Calls)+1, 5)
-				var c *Call
-				if idx < len(p.Calls) {
-					c = p.Calls[idx]
-				}
-				s := analyze(ct, p, c)
-				calls := r.generateCall(s, p)
-				p.insertBefore(c, calls)
-			case r.nOutOf(10, 11):
-				// Change args of a call.
-				if len(p.Calls) == 0 {
-					retry = true
-					continue
-				}
-				c := p.Calls[r.Intn(len(p.Calls))]
-				if len(c.Args) == 0 {
+	retry := false
+	for stop := false; !stop || retry; stop = r.oneOf(3) {
+		retry = false
+		switch {
+		case r.nOutOf(1, 100):
+			// Splice with another prog from corpus.
+			if len(corpus) == 0 || len(p.Calls) == 0 {
+				retry = true
+				continue
+			}
+			p0 := corpus[r.Intn(len(corpus))]
+			p0c := p0.Clone()
+			idx := r.Intn(len(p.Calls))
+			p.Calls = append(p.Calls[:idx], append(p0c.Calls, p.Calls[idx:]...)...)
+			if len(p.Calls) > ncalls {
+				p.Calls = p.Calls[:ncalls]
+			}
+		case r.nOutOf(20, 31):
+			// Insert a new call.
+			if len(p.Calls) >= ncalls {
+				retry = true
+				continue
+			}
+			idx := r.biasedRand(len(p.Calls)+1, 5)
+			var c *Call
+			if idx < len(p.Calls) {
+				c = p.Calls[idx]
+			}
+			s := analyze(ct, p, c)
+			calls := r.generateCall(s, p)
+			p.insertBefore(c, calls)
+		case r.nOutOf(10, 11):
+			// Change args of a call.
+			if len(p.Calls) == 0 {
+				retry = true
+				continue
+			}
+			c := p.Calls[r.Intn(len(p.Calls))]
+			if len(c.Args) == 0 {
+				retry = true
+				continue
+			}
+			s := analyze(ct, p, c)
+			for stop := false; !stop; stop = r.oneOf(3) {
+				args, bases := mutationArgs(c)
+				if len(args) == 0 {
 					retry = true
 					continue
 				}
-				s := analyze(ct, p, c)
-				for stop := false; !stop; stop = r.oneOf(3) {
-					args, bases := mutationArgs(c)
-					if len(args) == 0 {
-						retry = true
-						continue
+				idx := r.Intn(len(args))
+				arg, base := args[idx], bases[idx]
+				var baseSize uintptr
+				if base != nil {
+					if base.Kind != ArgPointer || base.Res == nil {
+						panic("bad base arg")
 					}
-					idx := r.Intn(len(args))
-					arg, base := args[idx], bases[idx]
-					var baseSize uintptr
-					if base != nil {
-						if base.Kind != ArgPointer || base.Res == nil {
-							panic("bad base arg")
+					baseSize = base.Res.Size()
+				}
+				switch a := arg.Type.(type) {
+				case *sys.IntType, *sys.FlagsType:
+					if r.bin() {
+						arg1, calls1 := r.generateArg(s, arg.Type)
+						p.replaceArg(c, arg, arg1, calls1)
+					} else {
+						switch {
+						case r.nOutOf(1, 3):
+							arg.Val += uintptr(r.Intn(4)) + 1
+						case r.nOutOf(1, 2):
+							arg.Val -= uintptr(r.Intn(4)) + 1
+						default:
+							arg.Val ^= 1 << uintptr(r.Intn(64))
 						}
-						baseSize = base.Res.Size()
 					}
-					switch a := arg.Type.(type) {
-					case *sys.IntType, *sys.FlagsType:
-						if r.bin() {
-							arg1, calls1 := r.generateArg(s, arg.Type)
-							p.replaceArg(c, arg, arg1, calls1)
-						} else {
-							switch {
-							case r.nOutOf(1, 3):
-								arg.Val += uintptr(r.Intn(4)) + 1
-							case r.nOutOf(1, 2):
-								arg.Val -= uintptr(r.Intn(4)) + 1
-							default:
-								arg.Val ^= 1 << uintptr(r.Intn(64))
+				case *sys.ResourceType, *sys.VmaType, *sys.ProcType:
+					arg1, calls1 := r.generateArg(s, arg.Type)
+					p.replaceArg(c, arg, arg1, calls1)
+				case *sys.BufferType:
+					switch a.Kind {
+					case sys.BufferBlobRand, sys.BufferBlobRange:
+						var data []byte
+						switch arg.Kind {
+						case ArgData:
+							data = append([]byte{}, arg.Data...)
+						case ArgConst:
+							// 0 is OK for optional args.
+							if arg.Val != 0 {
+								panic(fmt.Sprintf("BufferType has non-zero const value: %v", arg.Val))
 							}
+						default:
+							panic(fmt.Sprintf("bad arg kind for BufferType: %v", arg.Kind))
 						}
-					case *sys.ResourceType, *sys.VmaType, *sys.ProcType:
-						arg1, calls1 := r.generateArg(s, arg.Type)
-						p.replaceArg(c, arg, arg1, calls1)
-					case *sys.BufferType:
-						switch a.Kind {
-						case sys.BufferBlobRand, sys.BufferBlobRange:
-							var data []byte
-							switch arg.Kind {
-							case ArgData:
-								data = append([]byte{}, arg.Data...)
-							case ArgConst:
-								// 0 is OK for optional args.
-								if arg.Val != 0 {
-									panic(fmt.Sprintf("BufferType has non-zero const value: %v", arg.Val))
-								}
-							default:
-								panic(fmt.Sprintf("bad arg kind for BufferType: %v", arg.Kind))
-							}
+						minLen := int(0)
+						maxLen := math.MaxInt32
+						if a.Kind == sys.BufferBlobRange {
+							minLen = int(a.RangeBegin)
+							maxLen = int(a.RangeEnd)
+						}
+						arg.Data = mutateData(r, data, minLen, maxLen)
+					case sys.BufferString:
+						if r.bin() {
 							minLen := int(0)
 							maxLen := math.MaxInt32
-							if a.Kind == sys.BufferBlobRange {
-								minLen = int(a.RangeBegin)
-								maxLen = int(a.RangeEnd)
-							}
-							arg.Data = mutateData(r, data, minLen, maxLen)
-						case sys.BufferString:
-							if r.bin() {
-								minLen := int(0)
-								maxLen := math.MaxInt32
-								if a.Length != 0 {
-									minLen = int(a.Length)
-									maxLen = int(a.Length)
-								}
-								arg.Data = mutateData(r, append([]byte{}, arg.Data...), minLen, maxLen)
-							} else {
-								arg.Data = r.randString(s, a.Values, a.Dir())
+							if a.Length != 0 {
+								minLen = int(a.Length)
+								maxLen = int(a.Length)
 							}
-						case sys.BufferFilename:
-							arg.Data = []byte(r.filename(s))
-						case sys.BufferText:
-							arg.Data = r.mutateText(a.Text, arg.Data)
-						default:
-							panic("unknown buffer kind")
+							arg.Data = mutateData(r, append([]byte{}, arg.Data...), minLen, maxLen)
+						} else {
+							arg.Data = r.randString(s, a.Values, a.Dir())
 						}
-					case *sys.ArrayType:
-						count := uintptr(0)
-						switch a.Kind {
-						case sys.ArrayRandLen:
-							for count == uintptr(len(arg.Inner)) {
-								count = r.randArrayLen()
-							}
-						case sys.ArrayRangeLen:
-							if a.RangeBegin == a.RangeEnd {
-								panic("trying to mutate fixed length array")
-							}
-							for count == uintptr(len(arg.Inner)) {
-								count = r.randRange(int(a.RangeBegin), int(a.RangeEnd))
-							}
+					case sys.BufferFilename:
+						arg.Data = []byte(r.filename(s))
+					case sys.BufferText:
+						arg.Data = r.mutateText(a.Text, arg.Data)
+					default:
+						panic("unknown buffer kind")
+					}
+				case *sys.ArrayType:
+					count := uintptr(0)
+					switch a.Kind {
+					case sys.ArrayRandLen:
+						for count == uintptr(len(arg.Inner)) {
+							count = r.randArrayLen()
 						}
-						if count > uintptr(len(arg.Inner)) {
-							var calls []*Call
-							for count > uintptr(len(arg.Inner)) {
-								arg1, calls1 := r.generateArg(s, a.Type)
-								arg.Inner = append(arg.Inner, arg1)
-								for _, c1 := range calls1 {
-									calls = append(calls, c1)
-									s.analyze(c1)
-								}
-							}
-							for _, c1 := range calls {
-								sanitizeCall(c1)
-							}
-							sanitizeCall(c)
-							p.insertBefore(c, calls)
-						} else if count < uintptr(len(arg.Inner)) {
-							for _, arg := range arg.Inner[count:] {
-								p.removeArg(c, arg)
-							}
-							arg.Inner = arg.Inner[:count]
+					case sys.ArrayRangeLen:
+						if a.RangeBegin == a.RangeEnd {
+							panic("trying to mutate fixed length array")
 						}
-						// TODO: swap elements of the array
-					case *sys.PtrType:
-						// TODO: we don't know size for out args
-						size := uintptr(1)
-						if arg.Res != nil {
-							size = arg.Res.Size()
+						for count == uintptr(len(arg.Inner)) {
+							count = r.randRange(int(a.RangeBegin), int(a.RangeEnd))
 						}
-						arg1, calls1 := r.addr(s, a, size, arg.Res)
-						p.replaceArg(c, arg, arg1, calls1)
-					case *sys.StructType:
-						ctor := isSpecialStruct(a)
-						if ctor == nil {
-							panic("bad arg returned by mutationArgs: StructType")
+					}
+					if count > uintptr(len(arg.Inner)) {
+						var calls []*Call
+						for count > uintptr(len(arg.Inner)) {
+							arg1, calls1 := r.generateArg(s, a.Type)
+							arg.Inner = append(arg.Inner, arg1)
+							for _, c1 := range calls1 {
+								calls = append(calls, c1)
+								s.analyze(c1)
+							}
 						}
-						arg1, calls1 := ctor(r, s)
-						for i, f := range arg1.Inner {
-							p.replaceArg(c, arg.Inner[i], f, calls1)
-							calls1 = nil
+						for _, c1 := range calls {
+							sanitizeCall(c1)
 						}
-					case *sys.UnionType:
-						optType := a.Options[r.Intn(len(a.Options))]
-						maxIters := 1000
-						for i := 0; optType.FieldName() == arg.OptionType.FieldName(); i++ {
-							optType = a.Options[r.Intn(len(a.Options))]
-							if i >= maxIters {
-								panic(fmt.Sprintf("couldn't generate a different union option after %v iterations, type: %+v", maxIters, a))
-							}
+						sanitizeCall(c)
+						p.insertBefore(c, calls)
+					} else if count < uintptr(len(arg.Inner)) {
+						for _, arg := range arg.Inner[count:] {
+							p.removeArg(c, arg)
 						}
-						p.removeArg(c, arg.Option)
-						opt, calls := r.generateArg(s, optType)
-						arg1 := unionArg(a, opt, optType)
-						p.replaceArg(c, arg, arg1, calls)
-					case *sys.LenType:
-						panic("bad arg returned by mutationArgs: LenType")
-					case *sys.CsumType:
-						panic("bad arg returned by mutationArgs: CsumType")
-					case *sys.ConstType:
-						panic("bad arg returned by mutationArgs: ConstType")
-					default:
-						panic(fmt.Sprintf("bad arg returned by mutationArgs: %#v, type=%#v", *arg, arg.Type))
+						arg.Inner = arg.Inner[:count]
 					}
-
-					// Update base pointer if size has increased.
-					if base != nil && baseSize < base.Res.Size() {
-						arg1, calls1 := r.addr(s, base.Type, base.Res.Size(), base.Res)
-						for _, c1 := range calls1 {
-							sanitizeCall(c1)
+					// TODO: swap elements of the array
+				case *sys.PtrType:
+					// TODO: we don't know size for out args
+					size := uintptr(1)
+					if arg.Res != nil {
+						size = arg.Res.Size()
+					}
+					arg1, calls1 := r.addr(s, a, size, arg.Res)
+					p.replaceArg(c, arg, arg1, calls1)
+				case *sys.StructType:
+					ctor := isSpecialStruct(a)
+					if ctor == nil {
+						panic("bad arg returned by mutationArgs: StructType")
+					}
+					arg1, calls1 := ctor(r, s)
+					for i, f := range arg1.Inner {
+						p.replaceArg(c, arg.Inner[i], f, calls1)
+						calls1 = nil
+					}
+				case *sys.UnionType:
+					optType := a.Options[r.Intn(len(a.Options))]
+					maxIters := 1000
+					for i := 0; optType.FieldName() == arg.OptionType.FieldName(); i++ {
+						optType = a.Options[r.Intn(len(a.Options))]
+						if i >= maxIters {
+							panic(fmt.Sprintf("couldn't generate a different union option after %v iterations, type: %+v", maxIters, a))
 						}
-						p.insertBefore(c, calls1)
-						arg.AddrPage = arg1.AddrPage
-						arg.AddrOffset = arg1.AddrOffset
-						arg.AddrPagesNum = arg1.AddrPagesNum
 					}
-
-					// Update all len fields.
-					assignSizesCall(c)
+					p.removeArg(c, arg.Option)
+					opt, calls := r.generateArg(s, optType)
+					arg1 := unionArg(a, opt, optType)
+					p.replaceArg(c, arg, arg1, calls)
+				case *sys.LenType:
+					panic("bad arg returned by mutationArgs: LenType")
+				case *sys.CsumType:
+					panic("bad arg returned by mutationArgs: CsumType")
+				case *sys.ConstType:
+					panic("bad arg returned by mutationArgs: ConstType")
+				default:
+					panic(fmt.Sprintf("bad arg returned by mutationArgs: %#v, type=%#v", *arg, arg.Type))
 				}
-			default:
-				// Remove a random call.
-				if len(p.Calls) == 0 {
-					retry = true
-					continue
+
+				// Update base pointer if size has increased.
+				if base != nil && baseSize < base.Res.Size() {
+					arg1, calls1 := r.addr(s, base.Type, base.Res.Size(), base.Res)
+					for _, c1 := range calls1 {
+						sanitizeCall(c1)
+					}
+					p.insertBefore(c, calls1)
+					arg.AddrPage = arg1.AddrPage
+					arg.AddrOffset = arg1.AddrOffset
+					arg.AddrPagesNum = arg1.AddrPagesNum
 				}
-				idx := r.Intn(len(p.Calls))
-				p.removeCall(idx)
+
+				// Update all len fields.
+				assignSizesCall(c)
+			}
+		default:
+			// Remove a random call.
+			if len(p.Calls) == 0 {
+				retry = true
+				continue
 			}
+			idx := r.Intn(len(p.Calls))
+			p.removeCall(idx)
 		}
 	}