etcdserver/api/v3rpc/key.go
func checkIntervals(reqs []*pb.RequestOp) (map[string]struct{}, adt.IntervalTree, error) {
	var dels adt.IntervalTree

	// collect deletes from this level; build first to check lower level overlapped puts
	for _, req := range reqs {
		tv, ok := req.Request.(*pb.RequestOp_RequestDeleteRange)
		if !ok {
			continue
		}
		dreq := tv.RequestDeleteRange
		if dreq == nil {
			continue
		}
		var iv adt.Interval
		if len(dreq.RangeEnd) != 0 {
			iv = adt.NewStringAffineInterval(string(dreq.Key), string(dreq.RangeEnd))
		} else {
			iv = adt.NewStringAffinePoint(string(dreq.Key))
		}
		dels.Insert(iv, struct{}{})
	}

	// collect children puts/deletes
	puts := make(map[string]struct{})
	for _, req := range reqs {
		tv, ok := req.Request.(*pb.RequestOp_RequestTxn)
		if !ok {
			continue
		}
		putsThen, delsThen, err := checkIntervals(tv.RequestTxn.Success)
		if err != nil {
			return nil, dels, err
		}
		putsElse, delsElse, err := checkIntervals(tv.RequestTxn.Failure)
		if err != nil {
			return nil, dels, err
		}
		for k := range putsThen {
			if _, ok := puts[k]; ok {
				return nil, dels, rpctypes.ErrGRPCDuplicateKey
			}
			if dels.Intersects(adt.NewStringAffinePoint(k)) {
				return nil, dels, rpctypes.ErrGRPCDuplicateKey
			}
			puts[k] = struct{}{}
		}
		for k := range putsElse {
			if _, ok := puts[k]; ok {
				// if key is from putsThen, overlap is OK since
				// either then/else are mutually exclusive
				if _, isSafe := putsThen[k]; !isSafe {
					return nil, dels, rpctypes.ErrGRPCDuplicateKey
				}
			}
			if dels.Intersects(adt.NewStringAffinePoint(k)) {
				return nil, dels, rpctypes.ErrGRPCDuplicateKey
			}
			puts[k] = struct{}{}
		}
		dels.Union(delsThen, adt.NewStringAffineInterval("\x00", ""))
		dels.Union(delsElse, adt.NewStringAffineInterval("\x00", ""))
	}

	// collect and check this level's puts
	for _, req := range reqs {
		tv, ok := req.Request.(*pb.RequestOp_RequestPut)
		if !ok || tv.RequestPut == nil {
			continue
		}
		k := string(tv.RequestPut.Key)
		if _, ok := puts[k]; ok {
			return nil, dels, rpctypes.ErrGRPCDuplicateKey
		}
		if dels.Intersects(adt.NewStringAffinePoint(k)) {
			return nil, dels, rpctypes.ErrGRPCDuplicateKey
		}
		puts[k] = struct{}{}
	}
	return puts, dels, nil
}
func checkIntervals(reqs []*pb.RequestOp) (map[string]struct{}, adt.IntervalTree, error) {
	var dels adt.IntervalTree

	// collect deletes from this level; build first to check lower level overlapped puts
	for _, req := range reqs {
		tv, ok := req.Request.(*pb.RequestOp_RequestDeleteRange)
		if !ok {
			continue
		}
		dreq := tv.RequestDeleteRange
		if dreq == nil {
			continue
		}
		var iv adt.Interval
		if len(dreq.RangeEnd) != 0 {
			iv = adt.NewStringAffineInterval(string(dreq.Key), string(dreq.RangeEnd))
		} else {
			iv = adt.NewStringAffinePoint(string(dreq.Key))
		}
		dels.Insert(iv, struct{}{})
	}

	// collect children puts/deletes
	puts := make(map[string]struct{})
	for _, req := range reqs {
		tv, ok := req.Request.(*pb.RequestOp_RequestTxn)
		if !ok {
			continue
		}
		putsThen, delsThen, err := checkIntervals(tv.RequestTxn.Success)
		if err != nil {
			return nil, dels, err
		}
		putsElse, delsElse, err := checkIntervals(tv.RequestTxn.Failure)
		if err != nil {
			return nil, dels, err
		}
		for k := range putsThen {
			if _, ok := puts[k]; ok {
				return nil, dels, rpctypes.ErrGRPCDuplicateKey
			}
			if dels.Intersects(adt.NewStringAffinePoint(k)) {
				return nil, dels, rpctypes.ErrGRPCDuplicateKey
			}
			puts[k] = struct{}{}
		}
		for k := range putsElse {
			if _, ok := puts[k]; ok {
				// if key is from putsThen, overlap is OK since
				// either then/else are mutually exclusive
				if _, isSafe := putsThen[k]; !isSafe {
					return nil, dels, rpctypes.ErrGRPCDuplicateKey
				}
			}
			if dels.Intersects(adt.NewStringAffinePoint(k)) {
				return nil, dels, rpctypes.ErrGRPCDuplicateKey
			}
			puts[k] = struct{}{}
		}
		dels.Union(delsThen, adt.NewStringAffineInterval("\x00", ""))
		dels.Union(delsElse, adt.NewStringAffineInterval("\x00", ""))
	}

	// collect and check this level's puts
	for _, req := range reqs {
		tv, ok := req.Request.(*pb.RequestOp_RequestPut)
		if !ok || tv.RequestPut == nil {
			continue
		}
		k := string(tv.RequestPut.Key)
		if _, ok := puts[k]; ok {
			return nil, dels, rpctypes.ErrGRPCDuplicateKey
		}
		if dels.Intersects(adt.NewStringAffinePoint(k)) {
			return nil, dels, rpctypes.ErrGRPCDuplicateKey
		}
		puts[k] = struct{}{}
	}
	return puts, dels, nil
}
func checkIntervals ( reqs [ ] * pb . RequestOp ) ( map [ string ] struct { } , adt . IntervalTree , error ) { var dels adt . IntervalTree // collect deletes from this level; build first to check lower level overlapped puts for _ , req := range reqs { tv , ok := req . Request . ( * pb . RequestOp_RequestDeleteRange ) if ! ok { continue } dreq := tv . RequestDeleteRange if dreq == nil { continue } var iv adt . Interval if len ( dreq . RangeEnd ) != 0 { iv = adt . NewStringAffineInterval ( string ( dreq . Key ) , string ( dreq . RangeEnd ) ) } else { iv = adt . NewStringAffinePoint ( string ( dreq . Key ) ) } dels . Insert ( iv , struct { } { } ) } // collect children puts/deletes puts := make ( map [ string ] struct { } ) for _ , req := range reqs { tv , ok := req . Request . ( * pb . RequestOp_RequestTxn ) if ! ok { continue } putsThen , delsThen , err := checkIntervals ( tv . RequestTxn . Success ) if err != nil { return nil , dels , err } putsElse , delsElse , err := checkIntervals ( tv . RequestTxn . Failure ) if err != nil { return nil , dels , err } for k := range putsThen { if _ , ok := puts [ k ] ; ok { return nil , dels , rpctypes . ErrGRPCDuplicateKey } if dels . Intersects ( adt . NewStringAffinePoint ( k ) ) { return nil , dels , rpctypes . ErrGRPCDuplicateKey } puts [ k ] = struct { } { } } for k := range putsElse { if _ , ok := puts [ k ] ; ok { // if key is from putsThen, overlap is OK since // either then/else are mutually exclusive if _ , isSafe := putsThen [ k ] ; ! isSafe { return nil , dels , rpctypes . ErrGRPCDuplicateKey } } if dels . Intersects ( adt . NewStringAffinePoint ( k ) ) { return nil , dels , rpctypes . ErrGRPCDuplicateKey } puts [ k ] = struct { } { } } dels . Union ( delsThen , adt . NewStringAffineInterval ( " \x00 " , " " ) ) dels . Union ( delsElse , adt . NewStringAffineInterval ( " \x00 " , " " ) ) } // collect and check this level's puts for _ , req := range reqs { tv , ok := req . Request . ( * pb . RequestOp_RequestPut ) if ! ok || tv . RequestPut == nil { continue } k := string ( tv . RequestPut . Key ) if _ , ok := puts [ k ] ; ok { return nil , dels , rpctypes . ErrGRPCDuplicateKey } if dels . Intersects ( adt . NewStringAffinePoint ( k ) ) { return nil , dels , rpctypes . ErrGRPCDuplicateKey } puts [ k ] = struct { } { } } return puts , dels , nil }
// checkIntervals tests whether puts and deletes overlap for a list of ops. If
// there is an overlap, returns an error. If no overlap, return put and delete
// sets for recursive evaluation.
checkIntervals tests whether puts and deletes overlap for a list of ops . If there is an overlap returns an error . If no overlap return put and delete sets for recursive evaluation .