/*
Copyright 2021 The Kruise Authors.
Copyright 2016 The Kubernetes Authors.

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/

package polymorphichelpers

import (
	"bytes"
	"context"
	"fmt"
	"sort"

	kruiseappsv1alpha1 "github.com/openkruise/kruise-api/apps/v1alpha1"
	kruiseappsv1beta1 "github.com/openkruise/kruise-api/apps/v1beta1"
	kruiseclientsets "github.com/openkruise/kruise-api/client/clientset/versioned"
	internalapps "github.com/openkruise/kruise-tools/pkg/internal/apps"

	utils "github.com/openkruise/kruise-tools/pkg/utils"
	appsv1 "k8s.io/api/apps/v1"
	corev1 "k8s.io/api/core/v1"
	apiequality "k8s.io/apimachinery/pkg/api/equality"
	"k8s.io/apimachinery/pkg/api/meta"
	metav1 "k8s.io/apimachinery/pkg/apis/meta/v1"
	"k8s.io/apimachinery/pkg/runtime"
	"k8s.io/apimachinery/pkg/runtime/schema"
	"k8s.io/apimachinery/pkg/types"
	"k8s.io/apimachinery/pkg/util/json"
	"k8s.io/apimachinery/pkg/util/strategicpatch"
	"k8s.io/client-go/kubernetes"
	cmdutil "k8s.io/kubectl/pkg/cmd/util"
	"k8s.io/kubectl/pkg/scheme"
	deploymentutil "k8s.io/kubectl/pkg/util/deployment"
)

const (
	rollbackSuccess = "rolled back"
	rollbackSkipped = "skipped rollback"
)

// Rollbacker provides an interface for resources that can be rolled back.
type Rollbacker interface {
	Rollback(obj runtime.Object, updatedAnnotations map[string]string, toRevision int64, dryRunStrategy cmdutil.DryRunStrategy) (string, error)
}

type RollbackVisitor struct {
	clientset       kubernetes.Interface
	kruiseclientset kruiseclientsets.Interface
	result          Rollbacker
}

func (v *RollbackVisitor) VisitDeployment(elem internalapps.GroupKindElement) {
	v.result = &DeploymentRollbacker{v.clientset}
}

func (v *RollbackVisitor) VisitStatefulSet(kind internalapps.GroupKindElement) {
	v.result = &StatefulSetRollbacker{v.clientset}
}

func (v *RollbackVisitor) VisitDaemonSet(kind internalapps.GroupKindElement) {
	v.result = &DaemonSetRollbacker{v.clientset}
}

func (v *RollbackVisitor) VisitCloneSet(kind internalapps.GroupKindElement) {
	v.result = &CloneSetRollbacker{k: v.clientset, kc: v.kruiseclientset}
}

func (v *RollbackVisitor) VisitJob(kind internalapps.GroupKindElement)                   {}
func (v *RollbackVisitor) VisitPod(kind internalapps.GroupKindElement)                   {}
func (v *RollbackVisitor) VisitReplicaSet(kind internalapps.GroupKindElement)            {}
func (v *RollbackVisitor) VisitReplicationController(kind internalapps.GroupKindElement) {}
func (v *RollbackVisitor) VisitCronJob(kind internalapps.GroupKindElement)               {}
func (v *RollbackVisitor) VisitAdvancedStatefulSet(kind internalapps.GroupKindElement) {
	v.result = &AdvancedStatefulSetRollbacker{k: v.clientset, kc: v.kruiseclientset}
}
func (v *RollbackVisitor) VisitAdvancedDaemonSet(kind internalapps.GroupKindElement) {
	v.result = &AdvancedDaemonSetRollbacker{k: v.clientset, kc: v.kruiseclientset}
}
func (v *RollbackVisitor) VisitRollout(kind internalapps.GroupKindElement) {
	v.result = &RolloutRollbacker{k: v.clientset, kc: v.kruiseclientset}
}

// RollbackerFor returns an implementation of Rollbacker interface for the given schema kind
func RollbackerFor(kind schema.GroupKind, c kubernetes.Interface, kc kruiseclientsets.Interface) (Rollbacker, error) {
	elem := internalapps.GroupKindElement(kind)
	visitor := &RollbackVisitor{
		clientset:       c,
		kruiseclientset: kc,
	}

	err := elem.Accept(visitor)

	if err != nil {
		return nil, fmt.Errorf("error retrieving rollbacker for %q, %v", kind.String(), err)
	}

	if visitor.result == nil {
		return nil, fmt.Errorf("no rollbacker has been implemented for %q", kind)
	}

	return visitor.result, nil
}

type DeploymentRollbacker struct {
	c kubernetes.Interface
}

func (r *DeploymentRollbacker) Rollback(obj runtime.Object, updatedAnnotations map[string]string, toRevision int64, dryRunStrategy cmdutil.DryRunStrategy) (string, error) {
	if toRevision < 0 {
		return "", revisionNotFoundErr(toRevision)
	}
	accessor, err := meta.Accessor(obj)
	if err != nil {
		return "", fmt.Errorf("failed to create accessor for kind %v: %s", obj.GetObjectKind(), err.Error())
	}
	name := accessor.GetName()
	namespace := accessor.GetNamespace()

	// TODO: Fix this after kubectl has been removed from core. It is not possible to convert the runtime.Object
	// to the external appsv1 Deployment without round-tripping through an internal version of Deployment. We're
	// currently getting rid of all internal versions of resources. So we specifically request the appsv1 version
	// here. This follows the same pattern as for DaemonSet and StatefulSet.
	deployment, err := r.c.AppsV1().Deployments(namespace).Get(context.TODO(), name, metav1.GetOptions{})
	if err != nil {
		return "", fmt.Errorf("failed to retrieve Deployment %s: %v", name, err)
	}

	rsForRevision, err := deploymentRevision(deployment, r.c, toRevision)
	if err != nil {
		return "", err
	}
	if dryRunStrategy == cmdutil.DryRunClient {
		return printTemplate(&rsForRevision.Spec.Template)
	}

	// Skip if the revision already matches current Deployment
	if equalIgnoreHash(&rsForRevision.Spec.Template, &deployment.Spec.Template) {
		return fmt.Sprintf("%s (current template already matches revision %d)", rollbackSkipped, toRevision), nil
	}

	// remove hash label before patching back into the deployment
	delete(rsForRevision.Spec.Template.Labels, appsv1.DefaultDeploymentUniqueLabelKey)

	// compute deployment annotations
	annotations := map[string]string{}

	// In the same vein as annotationsToSkip, which records annotations to exclude,
	// IsKruiseRolloutsAnnotation checks whether an annotation is generated by kruise-rollout.
	// Annotations identified as generated by kruise-rollout
	// will be skipped when copying from ReplicaSet annotations to Deployment annotations.
	for k, v := range deployment.Annotations {
		if annotationsToSkip[k] || utils.IsKruiseRolloutsAnnotation(&k) {
			annotations[k] = v
		}
	}
	for k, v := range rsForRevision.Annotations {
		if !annotationsToSkip[k] && !utils.IsKruiseRolloutsAnnotation(&k) {
			annotations[k] = v
		}
	}

	// make patch to restore
	patchType, patch, err := getDeploymentPatch(&rsForRevision.Spec.Template, annotations)
	if err != nil {
		return "", fmt.Errorf("failed restoring revision %d: %v", toRevision, err)
	}

	patchOptions := metav1.PatchOptions{}
	if dryRunStrategy == cmdutil.DryRunServer {
		patchOptions.DryRun = []string{metav1.DryRunAll}
	}
	// Restore revision
	if _, err = r.c.AppsV1().Deployments(namespace).Patch(context.TODO(), name, patchType, patch, patchOptions); err != nil {
		return "", fmt.Errorf("failed restoring revision %d: %v", toRevision, err)
	}
	return rollbackSuccess, nil
}

// equalIgnoreHash returns true if two given podTemplateSpec are equal, ignoring the diff in value of Labels[pod-template-hash]
// We ignore pod-template-hash because:
//  1. The hash result would be different upon podTemplateSpec API changes
//     (e.g. the addition of a new field will cause the hash code to change)
//  2. The deployment template won't have hash labels
func equalIgnoreHash(template1, template2 *corev1.PodTemplateSpec) bool {
	t1Copy := template1.DeepCopy()
	t2Copy := template2.DeepCopy()
	// Remove hash labels from template.Labels before comparing
	delete(t1Copy.Labels, appsv1.DefaultDeploymentUniqueLabelKey)
	delete(t2Copy.Labels, appsv1.DefaultDeploymentUniqueLabelKey)
	return apiequality.Semantic.DeepEqual(t1Copy, t2Copy)
}

// annotationsToSkip lists the annotations that should be preserved from the deployment and not
// copied from the replicaset when rolling a deployment back
var annotationsToSkip = map[string]bool{
	corev1.LastAppliedConfigAnnotation:       true,
	deploymentutil.RevisionAnnotation:        true,
	deploymentutil.RevisionHistoryAnnotation: true,
	deploymentutil.DesiredReplicasAnnotation: true,
	deploymentutil.MaxReplicasAnnotation:     true,
	appsv1.DeprecatedRollbackTo:              true,
}

// getPatch returns a patch that can be applied to restore a Deployment to a
// previous version. If the returned error is nil the patch is valid.
func getDeploymentPatch(podTemplate *corev1.PodTemplateSpec, annotations map[string]string) (types.PatchType, []byte, error) {
	// Create a patch of the Deployment that replaces spec.template
	patch, err := json.Marshal([]interface{}{
		map[string]interface{}{
			"op":    "replace",
			"path":  "/spec/template",
			"value": podTemplate,
		},
		map[string]interface{}{
			"op":    "replace",
			"path":  "/metadata/annotations",
			"value": annotations,
		},
	})
	return types.JSONPatchType, patch, err
}

func deploymentRevision(deployment *appsv1.Deployment, c kubernetes.Interface, toRevision int64) (revision *appsv1.ReplicaSet, err error) {

	_, allOldRSs, newRS, err := deploymentutil.GetAllReplicaSets(deployment, c.AppsV1())
	if err != nil {
		return nil, fmt.Errorf("failed to retrieve replica sets from deployment %s: %v", deployment.Name, err)
	}
	allRSs := allOldRSs
	if newRS != nil {
		allRSs = append(allRSs, newRS)
	}

	var (
		latestReplicaSet   *appsv1.ReplicaSet
		latestRevision     = int64(-1)
		previousReplicaSet *appsv1.ReplicaSet
		previousRevision   = int64(-1)
	)
	for _, rs := range allRSs {
		if v, err := deploymentutil.Revision(rs); err == nil {
			if toRevision == 0 {
				if latestRevision < v {
					// newest one we've seen so far
					previousRevision = latestRevision
					previousReplicaSet = latestReplicaSet
					latestRevision = v
					latestReplicaSet = rs
				} else if previousRevision < v {
					// second newest one we've seen so far
					previousRevision = v
					previousReplicaSet = rs
				}
			} else if toRevision == v {
				return rs, nil
			}
		}
	}

	if toRevision > 0 {
		return nil, revisionNotFoundErr(toRevision)
	}

	// even a deployment is paused, rollout history can update if the current rollout progress is
	// actually a rollback, for example:

	// Step1. Initially, there's only one revision for the deployment:
	// REVISION  CHANGE-CAUSE
	// 1         <none>
	// before the first canary release is completed, the rollout history won't update since the original deployment
	// is paused. If someone decides to rollback during this release (before it is completed),
	// we should return the latestReplicaSet instead of the previousReplicaSet.

	// Step2. After a canary release completed, the rollout history will be like:
	// REVISION  CHANGE-CAUSE
	// 1       	 <none>
	// 2         <none>

	// Step3. Someone decides to rollback after this release using rollout undo.
	// It is ok, and it will be seen as a new canary release.
	// However, the rollout history will update though the original deployment is paused, because
	// the "new" canary revision can be found from the rollout history, which will be like:
	// REVISION  CHANGE-CAUSE
	// 2         <none>
	// 3         <none>

	// Step4. Someone decides to rollback during this rollback progress (before it is completed),
	// that means rolling back to the revision referred in the Step2.
	// We should return the previousReplicaSet instead of the latestReplicaSet.
	if utils.InCanaryProgress(deployment) {
		if latestReplicaSet == nil {
			return nil, fmt.Errorf("no rollout history found for deployment %q", deployment.Name)
		}
		// only one revison found, then return it, equalIgnoreHash will be called later in Rollback function
		if previousReplicaSet == nil {
			return latestReplicaSet, nil
		}
		// possibly attempting to rollback during a rollback progress, so we return previousReplicaSet,
		// since the rollout history is updated
		if equalIgnoreHash(&latestReplicaSet.Spec.Template, &deployment.Spec.Template) {
			return previousReplicaSet, nil
		}
		// attempting to rollback during a normal publication,
		// so we return latestReplicaSet since the rollout history hasn't updated
		return latestReplicaSet, nil
	}

	if previousReplicaSet == nil {
		return nil, fmt.Errorf("no rollout history found for deployment %q", deployment.Name)
	}
	return previousReplicaSet, nil
}

type DaemonSetRollbacker struct {
	c kubernetes.Interface
}

func (r *DaemonSetRollbacker) Rollback(obj runtime.Object, updatedAnnotations map[string]string, toRevision int64, dryRunStrategy cmdutil.DryRunStrategy) (string, error) {
	if toRevision < 0 {
		return "", revisionNotFoundErr(toRevision)
	}
	accessor, err := meta.Accessor(obj)
	if err != nil {
		return "", fmt.Errorf("failed to create accessor for kind %v: %s", obj.GetObjectKind(), err.Error())
	}
	ds, history, err := daemonSetHistory(r.c.AppsV1(), accessor.GetNamespace(), accessor.GetName())
	if err != nil {
		return "", err
	}
	if toRevision == 0 && len(history) <= 1 {
		return "", fmt.Errorf("no last revision to roll back to")
	}

	toHistory := findHistory(toRevision, history)
	if toHistory == nil {
		return "", revisionNotFoundErr(toRevision)
	}

	if dryRunStrategy == cmdutil.DryRunClient {
		appliedDS, err := applyDaemonSetHistory(ds, toHistory)
		if err != nil {
			return "", err
		}
		return printPodTemplate(&appliedDS.Spec.Template)
	}

	// Skip if the revision already matches current DaemonSet
	done, err := daemonSetMatch(ds, toHistory)
	if err != nil {
		return "", err
	}
	if done {
		return fmt.Sprintf("%s (current template already matches revision %d)", rollbackSkipped, toRevision), nil
	}

	patchOptions := metav1.PatchOptions{}
	if dryRunStrategy == cmdutil.DryRunServer {
		patchOptions.DryRun = []string{metav1.DryRunAll}
	}
	// Restore revision
	if _, err = r.c.AppsV1().DaemonSets(accessor.GetNamespace()).Patch(context.TODO(), accessor.GetName(), types.StrategicMergePatchType, toHistory.Data.Raw, patchOptions); err != nil {
		return "", fmt.Errorf("failed restoring revision %d: %v", toRevision, err)
	}

	return rollbackSuccess, nil
}

// daemonMatch check if the given DaemonSet's template matches the template stored in the given history.
func daemonSetMatch(ds *appsv1.DaemonSet, history *appsv1.ControllerRevision) (bool, error) {
	patch, err := getDaemonSetPatch(ds)
	if err != nil {
		return false, err
	}
	return bytes.Equal(patch, history.Data.Raw), nil
}

// getPatch returns a strategic merge patch that can be applied to restore a Daemonset to a
// previous version. If the returned error is nil the patch is valid. The current state that we save is just the
// PodSpecTemplate. We can modify this later to encompass more state (or less) and remain compatible with previously
// recorded patches.
func getDaemonSetPatch(ds *appsv1.DaemonSet) ([]byte, error) {
	dsBytes, err := json.Marshal(ds)
	if err != nil {
		return nil, err
	}
	var raw map[string]interface{}
	err = json.Unmarshal(dsBytes, &raw)
	if err != nil {
		return nil, err
	}
	objCopy := make(map[string]interface{})
	specCopy := make(map[string]interface{})

	// Create a patch of the DaemonSet that replaces spec.template
	spec := raw["spec"].(map[string]interface{})
	template := spec["template"].(map[string]interface{})
	specCopy["template"] = template
	template["$patch"] = "replace"
	objCopy["spec"] = specCopy
	patch, err := json.Marshal(objCopy)
	return patch, err
}

type StatefulSetRollbacker struct {
	c kubernetes.Interface
}

// toRevision is a non-negative integer, with 0 being reserved to indicate rolling back to previous configuration
func (r *StatefulSetRollbacker) Rollback(obj runtime.Object, updatedAnnotations map[string]string, toRevision int64, dryRunStrategy cmdutil.DryRunStrategy) (string, error) {
	if toRevision < 0 {
		return "", revisionNotFoundErr(toRevision)
	}
	accessor, err := meta.Accessor(obj)
	if err != nil {
		return "", fmt.Errorf("failed to create accessor for kind %v: %s", obj.GetObjectKind(), err.Error())
	}
	sts, history, err := statefulSetHistory(r.c.AppsV1(), accessor.GetNamespace(), accessor.GetName())
	if err != nil {
		return "", err
	}
	if toRevision == 0 && len(history) <= 1 {
		return "", fmt.Errorf("no last revision to roll back to")
	}

	toHistory := findHistory(toRevision, history)
	if toHistory == nil {
		return "", revisionNotFoundErr(toRevision)
	}

	if dryRunStrategy == cmdutil.DryRunClient {
		appliedSS, err := applyRevision(sts, toHistory)
		if err != nil {
			return "", err
		}
		return printPodTemplate(&appliedSS.Spec.Template)
	}

	// Skip if the revision already matches current StatefulSet
	done, err := statefulsetMatch(sts, toHistory)
	if err != nil {
		return "", err
	}
	if done {
		return fmt.Sprintf("%s (current template already matches revision %d)", rollbackSkipped, toRevision), nil
	}

	patchOptions := metav1.PatchOptions{}
	if dryRunStrategy == cmdutil.DryRunServer {
		patchOptions.DryRun = []string{metav1.DryRunAll}
	}
	// Restore revision
	if _, err = r.c.AppsV1().StatefulSets(sts.Namespace).Patch(context.TODO(), sts.Name, types.StrategicMergePatchType, toHistory.Data.Raw, patchOptions); err != nil {
		return "", fmt.Errorf("failed restoring revision %d: %v", toRevision, err)
	}

	return rollbackSuccess, nil
}

type CloneSetRollbacker struct {
	k  kubernetes.Interface
	kc kruiseclientsets.Interface
}

func (r *CloneSetRollbacker) Rollback(obj runtime.Object,
	updatedAnnotations map[string]string,
	toRevision int64,
	dryRunStrategy cmdutil.DryRunStrategy) (string, error) {

	if toRevision < 0 {
		return "", revisionNotFoundErr(toRevision)
	}
	accessor, err := meta.Accessor(obj)
	if err != nil {
		return "", fmt.Errorf("failed to create accessor for kind %v: %s", obj.GetObjectKind(), err.Error())
	}
	cs, history, err := clonesetHistory(r.k.AppsV1(), r.kc.AppsV1alpha1(), accessor.GetNamespace(), accessor.GetName())
	if err != nil {
		return "", err
	}
	if toRevision == 0 && len(history) <= 1 {
		return "", fmt.Errorf("no last revision to roll back to")
	}
	toHistory := findHistory(toRevision, history)
	if toHistory == nil {
		return "", revisionNotFoundErr(toRevision)
	}

	if dryRunStrategy == cmdutil.DryRunClient {
		appliedSS, err := applyCloneSetRevision(cs, toHistory)
		if err != nil {
			return "", err
		}
		return printPodTemplate(&appliedSS.Spec.Template)
	}

	// Skip if the revision already matches current CloneSet
	done, err := cloneSetMatch(cs, toHistory)
	if err != nil {
		return "", err
	}
	if done {
		return fmt.Sprintf("%s (current template already matches revision %d)", rollbackSkipped, toRevision), nil
	}

	patchOptions := metav1.PatchOptions{}
	if dryRunStrategy == cmdutil.DryRunServer {
		patchOptions.DryRun = []string{metav1.DryRunAll}
	}

	// Restore revision
	_, err = r.kc.AppsV1alpha1().CloneSets(cs.Namespace).Patch(context.TODO(), cs.Name, types.MergePatchType, toHistory.Data.Raw, patchOptions)
	if err != nil {
		return "", fmt.Errorf("failed restoring revision %d: %v", toRevision, err)
	}

	return rollbackSuccess, nil
}

type AdvancedStatefulSetRollbacker struct {
	k  kubernetes.Interface
	kc kruiseclientsets.Interface
}

func (r *AdvancedStatefulSetRollbacker) Rollback(obj runtime.Object,
	updatedAnnotations map[string]string,
	toRevision int64,
	dryRunStrategy cmdutil.DryRunStrategy) (string, error) {
	if toRevision < 0 {
		return "", revisionNotFoundErr(toRevision)
	}
	accessor, err := meta.Accessor(obj)
	if err != nil {
		return "", fmt.Errorf("failed to create accessor for kind %v: %s", obj.GetObjectKind(), err.Error())
	}
	asts, history, err := advancedstsHistory(r.k.AppsV1(), r.kc.AppsV1beta1(), accessor.GetNamespace(), accessor.GetName())
	if err != nil {
		return "", err
	}
	if toRevision == 0 && len(history) <= 1 {
		return "", fmt.Errorf("no latest revision to roll back to")
	}
	toHistory := findHistory(toRevision, history)
	if toHistory == nil {
		return "", revisionNotFoundErr(toRevision)
	}
	if dryRunStrategy == cmdutil.DryRunClient {
		appliedSS, err := applyAdvancedStatefulSetRevision(asts, toHistory)
		if err != nil {
			return "", err
		}
		return printPodTemplate(&appliedSS.Spec.Template)
	}
	// Skip if the revision already matches current CloneSet
	done, err := astsMatch(asts, toHistory)
	if err != nil {
		return "", err
	}
	if done {
		return fmt.Sprintf("%s (current template already matches revision %d)", rollbackSkipped, toRevision), nil
	}

	patchOptions := metav1.PatchOptions{}
	if dryRunStrategy == cmdutil.DryRunServer {
		patchOptions.DryRun = []string{metav1.DryRunAll}
	}

	// Restore revision
	_, err = r.kc.AppsV1beta1().StatefulSets(asts.Namespace).Patch(context.TODO(), asts.Name, types.MergePatchType, toHistory.Data.Raw, patchOptions)
	if err != nil {
		return "", fmt.Errorf("failed restoring revision %d: %v", toRevision, err)
	}

	return rollbackSuccess, nil
}

type AdvancedDaemonSetRollbacker struct {
	k  kubernetes.Interface
	kc kruiseclientsets.Interface
}

type RolloutRollbacker struct {
	k  kubernetes.Interface
	kc kruiseclientsets.Interface
}

// RolloutRollbacker.Rollback never be called
func (r *RolloutRollbacker) Rollback(obj runtime.Object,
	updatedAnnotations map[string]string,
	toRevision int64,
	dryRunStrategy cmdutil.DryRunStrategy) (string, error) {

	return rollbackSuccess, nil
}

func (r *AdvancedDaemonSetRollbacker) Rollback(obj runtime.Object,
	updatedAnnotations map[string]string,
	toRevision int64,
	dryRunStrategy cmdutil.DryRunStrategy) (string, error) {
	if toRevision < 0 {
		return "", revisionNotFoundErr(toRevision)
	}
	accessor, err := meta.Accessor(obj)
	if err != nil {
		return "", fmt.Errorf("failed to create accessor for kind %v: %s", obj.GetObjectKind(), err.Error())
	}
	ads, history, err := advancedDaemonSetHistory(r.k.AppsV1(), r.kc.AppsV1alpha1(), accessor.GetNamespace(), accessor.GetName())
	if err != nil {
		return "", err
	}
	if toRevision == 0 && len(history) <= 1 {
		return "", fmt.Errorf("no last revision to roll back to")
	}

	toHistory := findHistory(toRevision, history)
	if toHistory == nil {
		return "", revisionNotFoundErr(toRevision)
	}

	if dryRunStrategy == cmdutil.DryRunClient {
		appliedDS, err := applyAdvancedDaemonSetHistory(ads, toHistory)
		if err != nil {
			return "", err
		}
		return printPodTemplate(&appliedDS.Spec.Template)
	}

	// Skip if the revision already matches current DaemonSet
	done, err := advancedDaemonSetMatch(ads, toHistory)
	if err != nil {
		return "", err
	}
	if done {
		return fmt.Sprintf("%s (current template already matches revision %d)", rollbackSkipped, toRevision), nil
	}

	patchOptions := metav1.PatchOptions{}
	if dryRunStrategy == cmdutil.DryRunServer {
		patchOptions.DryRun = []string{metav1.DryRunAll}
	}
	// Restore revision
	if _, err = r.kc.AppsV1alpha1().DaemonSets(ads.Namespace).Patch(context.TODO(), ads.Name, types.MergePatchType, toHistory.Data.Raw, patchOptions); err != nil {
		return "", fmt.Errorf("failed restoring revision %d: %v", toRevision, err)
	}

	return rollbackSuccess, nil
}

var appsCodec = scheme.Codecs.LegacyCodec(appsv1.SchemeGroupVersion)

// applyRevision returns a new StatefulSet constructed by restoring the state in revision to set. If the returned error
// is nil, the returned StatefulSet is valid.
func applyRevision(set *appsv1.StatefulSet, revision *appsv1.ControllerRevision) (*appsv1.StatefulSet, error) {
	patched, err := strategicpatch.StrategicMergePatch([]byte(runtime.EncodeOrDie(appsCodec, set)), revision.Data.Raw, set)
	if err != nil {
		return nil, err
	}
	result := &appsv1.StatefulSet{}
	err = json.Unmarshal(patched, result)
	if err != nil {
		return nil, err
	}
	return result, nil
}

var kruiseAppsv1alpha1Codec = scheme.Codecs.LegacyCodec(kruiseappsv1alpha1.SchemeGroupVersion)

// applyCloneSetRevision returns a new CloneSet constructed by restoring the state in revision to set. If the returned error
// is nil, the returned CloneSet is valid.
func applyCloneSetRevision(cs *kruiseappsv1alpha1.CloneSet,
	revision *appsv1.ControllerRevision) (*kruiseappsv1alpha1.CloneSet, error) {
	patched, err := strategicpatch.StrategicMergePatch([]byte(runtime.EncodeOrDie(kruiseAppsv1alpha1Codec, cs)), revision.Data.Raw, cs)
	if err != nil {
		return nil, err
	}
	result := &kruiseappsv1alpha1.CloneSet{}
	err = json.Unmarshal(patched, result)
	if err != nil {
		return nil, err
	}
	return result, nil
}

var kruiseAppsv1beta1Codec = scheme.Codecs.LegacyCodec(kruiseappsv1beta1.SchemeGroupVersion)

// apply  applyAdvancedStatefulSetRevision returns a new Advanced StatefulSet constructed by restoring the state in revision to set.
// If the returned error is nil, the returned Advanced StatefulSet is valid.
func applyAdvancedStatefulSetRevision(asts *kruiseappsv1beta1.StatefulSet,
	revision *appsv1.ControllerRevision) (*kruiseappsv1beta1.StatefulSet, error) {
	patched, err := strategicpatch.StrategicMergePatch([]byte(runtime.EncodeOrDie(kruiseAppsv1beta1Codec, asts)), revision.Data.Raw, asts)
	if err != nil {
		return nil, err
	}
	result := &kruiseappsv1beta1.StatefulSet{}
	err = json.Unmarshal(patched, result)
	if err != nil {
		return nil, err
	}
	return nil, err
}

// statefulsetMatch check if the given StatefulSet's template matches the template stored in the given history.
func statefulsetMatch(ss *appsv1.StatefulSet, history *appsv1.ControllerRevision) (bool, error) {
	patch, err := getStatefulSetPatch(ss)
	if err != nil {
		return false, err
	}
	return bytes.Equal(patch, history.Data.Raw), nil
}

// astsMatch check if the given Advanced StatefulSet's template matched the template stored in the given history
func astsMatch(asts *kruiseappsv1beta1.StatefulSet, history *appsv1.ControllerRevision) (bool, error) {
	patch, err := getAdvancedStatefulSetPatch(asts)
	if err != nil {
		return false, err
	}
	return bytes.Equal(patch, history.Data.Raw), nil
}

// cloneSetMatch check if the given CloneSet's template matches the template stored in the given history.
func cloneSetMatch(cs *kruiseappsv1alpha1.CloneSet, history *appsv1.ControllerRevision) (bool, error) {
	patch, err := getCloneSetPatch(cs)
	if err != nil {
		return false, err
	}
	return bytes.Equal(patch, history.Data.Raw), nil
}

// advancedDaemonSetMatch check if the given Advanced DaemonSet's template matches the template stored in the given history.
func advancedDaemonSetMatch(ads *kruiseappsv1alpha1.DaemonSet, history *appsv1.ControllerRevision) (bool, error) {
	patch, err := getAdvancedDaemonSetPatch(ads)
	if err != nil {
		return false, err
	}
	return bytes.Equal(patch, history.Data.Raw), nil
}

// getStatefulSetPatch returns a strategic merge patch that can be applied to restore a StatefulSet to a
// previous version. If the returned error is nil the patch is valid. The current state that we save is just the
// PodSpecTemplate. We can modify this later to encompass more state (or less) and remain compatible with previously
// recorded patches.
func getStatefulSetPatch(set *appsv1.StatefulSet) ([]byte, error) {
	str, err := runtime.Encode(appsCodec, set)
	if err != nil {
		return nil, err
	}
	var raw map[string]interface{}
	if err := json.Unmarshal(str, &raw); err != nil {
		return nil, err
	}
	objCopy := make(map[string]interface{})
	specCopy := make(map[string]interface{})
	spec := raw["spec"].(map[string]interface{})
	template := spec["template"].(map[string]interface{})
	specCopy["template"] = template
	template["$patch"] = "replace"
	objCopy["spec"] = specCopy
	patch, err := json.Marshal(objCopy)
	return patch, err
}

// getCloneSetPatch returns a strategic merge patch that can be applied to restore a CloneSet to a
// previous version.
func getCloneSetPatch(cs *kruiseappsv1alpha1.CloneSet) ([]byte, error) {
	str, err := runtime.Encode(kruiseAppsv1alpha1Codec, cs)
	if err != nil {
		return nil, err
	}
	var raw map[string]interface{}
	if err := json.Unmarshal(str, &raw); err != nil {
		return nil, err
	}

	objCopy := make(map[string]interface{})
	specCopy := make(map[string]interface{})
	spec := raw["spec"].(map[string]interface{})
	template := spec["template"].(map[string]interface{})
	specCopy["template"] = template
	template["$patch"] = "replace"
	objCopy["spec"] = specCopy
	patch, err := json.Marshal(objCopy)
	return patch, err
}

// getAdvancedStatefulSetPatch returns a strategic merge patch that can be applied to restore a Advanced StatefulSet to
// a previous version
func getAdvancedStatefulSetPatch(asts *kruiseappsv1beta1.StatefulSet) ([]byte, error) {
	str, err := runtime.Encode(kruiseAppsv1beta1Codec, asts)
	if err != nil {
		return nil, err
	}
	var raw map[string]interface{}
	if err := json.Unmarshal(str, &raw); err != nil {
		return nil, err
	}
	objCopy := make(map[string]interface{})
	specCopy := make(map[string]interface{})
	spec := raw["spec"].(map[string]interface{})
	template := spec["template"].(map[string]interface{})
	specCopy["template"] = template
	template["$patch"] = "replace"
	objCopy["spec"] = specCopy
	patch, err := json.Marshal(objCopy)
	return patch, err
}

func getAdvancedDaemonSetPatch(ads *kruiseappsv1alpha1.DaemonSet) ([]byte, error) {
	str, err := runtime.Encode(kruiseAppsv1alpha1Codec, ads)
	if err != nil {
		return nil, err
	}
	var raw map[string]interface{}
	if err := json.Unmarshal(str, &raw); err != nil {
		return nil, err
	}
	objCopy := make(map[string]interface{})
	specCopy := make(map[string]interface{})
	// Create a patch of the DaemonSet that replaces spec.template
	spec := raw["spec"].(map[string]interface{})
	template := spec["template"].(map[string]interface{})
	specCopy["template"] = template
	template["$patch"] = "replace"
	objCopy["spec"] = specCopy
	patch, err := json.Marshal(objCopy)
	return patch, err
}

// findHistory returns a controllerrevision of a specific revision from the given controllerrevisions.
// It returns nil if no such controllerrevision exists.
// If toRevision is 0, the last previously used history is returned.
func findHistory(toRevision int64, allHistory []*appsv1.ControllerRevision) *appsv1.ControllerRevision {
	if toRevision == 0 && len(allHistory) <= 1 {
		return nil
	}

	// Find the history to rollback to
	var toHistory *appsv1.ControllerRevision
	if toRevision == 0 {
		// If toRevision == 0, find the latest revision (2nd max)
		sort.Sort(historiesByRevision(allHistory))
		toHistory = allHistory[len(allHistory)-2]
	} else {
		for _, h := range allHistory {
			if h.Revision == toRevision {
				// If toRevision != 0, find the history with matching revision
				return h
			}
		}
	}

	return toHistory
}

// printPodTemplate converts a given pod template into a human-readable string.
func printPodTemplate(specTemplate *corev1.PodTemplateSpec) (string, error) {
	podSpec, err := printTemplate(specTemplate)
	if err != nil {
		return "", err
	}
	return fmt.Sprintf("will roll back to %s", podSpec), nil
}

func revisionNotFoundErr(r int64) error {
	return fmt.Errorf("unable to find specified revision %v in history", r)
}

// TODO: copied from daemon controller, should extract to a library
type historiesByRevision []*appsv1.ControllerRevision

func (h historiesByRevision) Len() int      { return len(h) }
func (h historiesByRevision) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h historiesByRevision) Less(i, j int) bool {
	return h[i].Revision < h[j].Revision
}
