/*
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 */

/** \file
 * \ingroup bke
 *
 * Mirror/Symmetry functions applying to actions.
 */

#include <math.h>
#include <string.h>

#include "MEM_guardedalloc.h"

#include "DNA_anim_types.h"
#include "DNA_armature_types.h"
#include "DNA_object_types.h"

#include "BLI_blenlib.h"
#include "BLI_math.h"
#include "BLI_string_utils.h"
#include "BLI_utildefines.h"

#include "BKE_action.h"
#include "BKE_armature.h"
#include "BKE_fcurve.h"

#include "DEG_depsgraph.h"

/* -------------------------------------------------------------------- */
/** \name Flip the Action (Armature/Pose Objects)
 *
 * This flips the action using the rest pose (not the evaluated pose).
 *
 * Details:
 *
 * - Key-frames are modified in-place, creating new key-frames is not yet supported.
 *   That could be useful if a user for example only has 2x rotation channels set.
 *   In practice users typically keyframe all rotation channels or none.
 *
 * - F-curve modifiers are disabled for evaluation,
 *   so the values written back to the keyframes don't include modifier offsets.
 *
 * - Sub-frame key-frames aren't supported,
 *   this could be added if needed without much trouble.
 *
 * - F-curves must have a #FCurve.bezt array (sampled curves aren't supported).
 * \{ */

/**
 * This structure is created for each pose channels F-curve,
 * an action be evaluated and stored in `fcurve_eval`,
 * with the mirrored values written into `bezt_array`.
 *
 * Store F-curve evaluated values, constructed with a sorted array of rounded keyed-frames,
 * passed to #action_flip_pchan_cache_init.
 */
struct FCurve_KeyCache {
  /**
   * When NULL, ignore this channel.
   */
  FCurve *fcurve;
  /**
   * Cached evaluated F-curve values (without modifiers).
   */
  float *fcurve_eval;
  /**
   * Cached #FCurve.bezt values, NULL when no key-frame exists on this frame.
   *
   * \note The case where two keyframes round to the same frame isn't supported.
   * In this case only the first will be used.
   */
  BezTriple **bezt_array;
};

/**
 * Assign `fkc` path, using a `path` lookup for a single value.
 */
static void action_flip_pchan_cache_fcurve_assign_value(struct FCurve_KeyCache *fkc,
                                                        int index,
                                                        const char *path,
                                                        struct FCurvePathCache *fcache)
{
  FCurve *fcu = BKE_fcurve_pathcache_find(fcache, path, index);
  if (fcu && fcu->bezt) {
    fkc->fcurve = fcu;
  }
}

/**
 * Assign #FCurve_KeyCache.fcurve path, using a `path` lookup for an array.
 */
static void action_flip_pchan_cache_fcurve_assign_array(struct FCurve_KeyCache *fkc,
                                                        int fkc_len,
                                                        const char *path,
                                                        struct FCurvePathCache *fcache)
{
  FCurve **fcurves = alloca(sizeof(*fcurves) * fkc_len);
  if (BKE_fcurve_pathcache_find_array(fcache, path, fcurves, fkc_len)) {
    for (int i = 0; i < fkc_len; i++) {
      if (fcurves[i] && fcurves[i]->bezt) {
        fkc[i].fcurve = fcurves[i];
      }
    }
  }
}

/**
 * Fill in pose channel cache for each frame in `keyed_frames`.
 *
 * \param keyed_frames: An array of keyed_frames to evaluate,
 * note that each frame is rounded to the nearest int.
 * \param keyed_frames_len: The length of the `keyed_frames` array.
 */
static void action_flip_pchan_cache_init(struct FCurve_KeyCache *fkc,
                                         const float *keyed_frames,
                                         int keyed_frames_len)
{
  BLI_assert(fkc->fcurve != NULL);

  /* Cache the F-curve values for `keyed_frames`. */
  const int fcurve_flag = fkc->fcurve->flag;
  fkc->fcurve->flag |= FCURVE_MOD_OFF;
  fkc->fcurve_eval = MEM_mallocN(sizeof(float) * keyed_frames_len, __func__);
  for (int frame_index = 0; frame_index < keyed_frames_len; frame_index++) {
    const float evaltime = keyed_frames[frame_index];
    fkc->fcurve_eval[frame_index] = evaluate_fcurve_only_curve(fkc->fcurve, evaltime);
  }
  fkc->fcurve->flag = fcurve_flag;

  /* Cache the #BezTriple for `keyed_frames`, or leave as NULL. */
  fkc->bezt_array = MEM_mallocN(sizeof(*fkc->bezt_array) * keyed_frames_len, __func__);
  BezTriple *bezt = fkc->fcurve->bezt;
  BezTriple *bezt_end = fkc->fcurve->bezt + fkc->fcurve->totvert;

  int frame_index = 0;
  while (frame_index < keyed_frames_len) {
    const float evaltime = keyed_frames[frame_index];
    const float bezt_time = roundf(bezt->vec[1][0]);
    if (bezt_time > evaltime) {
      fkc->bezt_array[frame_index++] = NULL;
    }
    else {
      if (bezt_time == evaltime) {
        fkc->bezt_array[frame_index++] = bezt;
      }
      bezt++;
      if (bezt == bezt_end) {
        break;
      }
    }
  }
  /* Clear remaining unset keyed_frames (if-any). */
  while (frame_index < keyed_frames_len) {
    fkc->bezt_array[frame_index++] = NULL;
  }
}

/**
 */
static void action_flip_pchan(Object *ob_arm,
                              const bPoseChannel *pchan,
                              struct FCurvePathCache *fcache)
{
  /* Begin F-Curve pose channel value extraction. */
  /* Use a fixed buffer size as it's known this can only be at most:
   * `pose.bones["{MAXBONENAME}"].rotation_quaternion`. */
  char path_xform[256];
  char pchan_name_esc[sizeof(((bActionChannel *)NULL)->name) * 2];
  BLI_str_escape(pchan_name_esc, pchan->name, sizeof(pchan_name_esc));
  const int path_xform_prefix_len = SNPRINTF(path_xform, "pose.bones[\"%s\"]", pchan_name_esc);
  char *path_xform_suffix = path_xform + path_xform_prefix_len;
  const int path_xform_suffix_len = sizeof(path_xform) - path_xform_prefix_len;

  /* Lookup and assign all available #FCurve channels,
   * unavailable channels are left NULL. */

  /**
   * Structure to store transformation F-curves corresponding to a pose bones transformation.
   * Match struct member names from #bPoseChannel so macros avoid repetition.
   *
   * \note There is no need to read values unless they influence the 4x4 transform matrix,
   * and no need to write values back unless they would be changed by a modified matrix.
   * So `rotmode` needs to be read, but doesn't need to be written back to.
   *
   * Most bendy-bone settings don't need to be included either, flipping their RNA paths is enough.
   * Although the X/Y settings could make sense to transform, in practice it would only
   * work well if the rotation happened to swap X/Y alignment, leave this for now.
   */
  struct {
    struct FCurve_KeyCache loc[3], eul[3], quat[4], rotAxis[3], rotAngle, size[3], rotmode;
  } fkc_pchan = {{{NULL}}};

#define FCURVE_ASSIGN_VALUE(id, path_test_suffix, index) \
  BLI_strncpy(path_xform_suffix, path_test_suffix, path_xform_suffix_len); \
  action_flip_pchan_cache_fcurve_assign_value(&fkc_pchan.id, index, path_xform, fcache)

#define FCURVE_ASSIGN_ARRAY(id, path_test_suffix) \
  BLI_strncpy(path_xform_suffix, path_test_suffix, path_xform_suffix_len); \
  action_flip_pchan_cache_fcurve_assign_array( \
      fkc_pchan.id, ARRAY_SIZE(fkc_pchan.id), path_xform, fcache)

  FCURVE_ASSIGN_ARRAY(loc, ".location");
  FCURVE_ASSIGN_ARRAY(eul, ".rotation_euler");
  FCURVE_ASSIGN_ARRAY(quat, ".rotation_quaternion");
  FCURVE_ASSIGN_ARRAY(rotAxis, ".rotation_axis_angle");
  FCURVE_ASSIGN_VALUE(rotAngle, ".rotation_axis_angle", 3);
  FCURVE_ASSIGN_ARRAY(size, ".scale");
  FCURVE_ASSIGN_VALUE(rotmode, ".rotation_mode", 0);

#undef FCURVE_ASSIGN_VALUE
#undef FCURVE_ASSIGN_ARRAY

  /* Array of F-curves, for convenient access. */
#define FCURVE_CHANNEL_LEN (sizeof(fkc_pchan) / sizeof(struct FCurve_KeyCache))
  FCurve *fcurve_array[FCURVE_CHANNEL_LEN];
  int fcurve_array_len = 0;

  for (int chan = 0; chan < FCURVE_CHANNEL_LEN; chan++) {
    struct FCurve_KeyCache *fkc = (struct FCurve_KeyCache *)(&fkc_pchan) + chan;
    if (fkc->fcurve != NULL) {
      fcurve_array[fcurve_array_len++] = fkc->fcurve;
    }
  }

  /* If this pose has no transform channels, there is nothing to do. */
  if (fcurve_array_len == 0) {
    return;
  }

  /* Calculate an array of frames used by any of the key-frames in `fcurve_array`. */
  int keyed_frames_len;
  const float *keyed_frames = BKE_fcurves_calc_keyed_frames(
      fcurve_array, fcurve_array_len, &keyed_frames_len);

  /* Initialize the pose channel curve cache from the F-curve. */
  for (int chan = 0; chan < FCURVE_CHANNEL_LEN; chan++) {
    struct FCurve_KeyCache *fkc = (struct FCurve_KeyCache *)(&fkc_pchan) + chan;
    if (fkc->fcurve == NULL) {
      continue;
    }
    action_flip_pchan_cache_init(fkc, keyed_frames, keyed_frames_len);
  }

  /* X-axis flipping matrix. */
  float flip_mtx[4][4];
  unit_m4(flip_mtx);
  flip_mtx[0][0] = -1;

  bPoseChannel *pchan_flip = NULL;
  char pchan_name_flip[MAXBONENAME];
  BLI_string_flip_side_name(pchan_name_flip, pchan->name, false, sizeof(pchan_name_flip));
  if (!STREQ(pchan_name_flip, pchan->name)) {
    pchan_flip = BKE_pose_channel_find_name(ob_arm->pose, pchan_name_flip);
  }

  float arm_mat_inv[4][4];
  invert_m4_m4(arm_mat_inv, pchan_flip ? pchan_flip->bone->arm_mat : pchan->bone->arm_mat);

  /* Now flip the transformation & write it back to the F-curves in `fkc_pchan`. */

  for (int frame_index = 0; frame_index < keyed_frames_len; frame_index++) {

    /* Temporary pose channel to write values into,
     * using the `fkc_pchan` values, falling back to the values in the pose channel. */
    bPoseChannel pchan_temp = *pchan;

    /* Load the values into the channel. */
#define READ_VALUE_FLT(id) \
  if (fkc_pchan.id.fcurve_eval != NULL) { \
    pchan_temp.id = fkc_pchan.id.fcurve_eval[frame_index]; \
  } \
  ((void)0)

#define READ_VALUE_INT(id) \
  if (fkc_pchan.id.fcurve_eval != NULL) { \
    pchan_temp.id = floorf(fkc_pchan.id.fcurve_eval[frame_index] + 0.5f); \
  } \
  ((void)0)

#define READ_ARRAY_FLT(id) \
  for (int i = 0; i < ARRAY_SIZE(pchan_temp.id); i++) { \
    READ_VALUE_FLT(id[i]); \
  } \
  ((void)0)

    READ_ARRAY_FLT(loc);
    READ_ARRAY_FLT(eul);
    READ_ARRAY_FLT(quat);
    READ_ARRAY_FLT(rotAxis);
    READ_VALUE_FLT(rotAngle);
    READ_ARRAY_FLT(size);
    READ_VALUE_INT(rotmode);

#undef READ_ARRAY_FLT
#undef READ_VALUE_FLT
#undef READ_VALUE_INT

    float chan_mat[4][4];
    BKE_pchan_to_mat4(&pchan_temp, chan_mat);

    /* Move to the pose-space. */
    mul_m4_m4m4(chan_mat, pchan->bone->arm_mat, chan_mat);

    /* Flip the matrix. */
    mul_m4_m4m4(chan_mat, chan_mat, flip_mtx);
    mul_m4_m4m4(chan_mat, flip_mtx, chan_mat);

    /* Move back to bone-space space, using the flipped bone if it exists. */
    mul_m4_m4m4(chan_mat, arm_mat_inv, chan_mat);

    /* The rest pose having an X-axis that is not mapping to a left/right direction (so aligned
     * with the Y or Z axis) creates issues when flipping the pose. Instead of a negative scale on
     * the X-axis, it turns into a 180 degree rotation over the Y-axis.
     * This has only been observed with bones that can't be flipped,
     * hence the check for `pchan_flip`. */
    const float unit_x[4] = {1.0f, 0.0f, 0.0f, 0.0f};
    const bool is_problematic = pchan_flip == NULL &&
                                fabsf(dot_v4v4(pchan->bone->arm_mat[0], unit_x)) <= 1e-6;
    if (is_problematic) {
      /* Matrix needs to flip both the X and Z axes to come out right. */
      float extra_mat[4][4] = {
          {-1.0f, 0.0f, 0.0f, 0.0f},
          {0.0f, 1.0f, 0.0f, 0.0f},
          {0.0f, 0.0f, -1.0f, 0.0f},
          {0.0f, 0.0f, 0.0f, 1.0f},
      };
      mul_m4_m4m4(chan_mat, extra_mat, chan_mat);
    }

    BKE_pchan_apply_mat4(&pchan_temp, chan_mat, false);

    /* Write the values back to the F-curves. */
#define WRITE_VALUE_FLT(id) \
  if (fkc_pchan.id.fcurve_eval != NULL) { \
    BezTriple *bezt = fkc_pchan.id.bezt_array[frame_index]; \
    if (bezt != NULL) { \
      const float delta = pchan_temp.id - bezt->vec[1][1]; \
      bezt->vec[0][1] += delta; \
      bezt->vec[1][1] += delta; \
      bezt->vec[2][1] += delta; \
    } \
  } \
  ((void)0)

#define WRITE_ARRAY_FLT(id) \
  for (int i = 0; i < ARRAY_SIZE(pchan_temp.id); i++) { \
    WRITE_VALUE_FLT(id[i]); \
  } \
  ((void)0)

    /* Write the values back the F-curves. */
    WRITE_ARRAY_FLT(loc);
    WRITE_ARRAY_FLT(eul);
    WRITE_ARRAY_FLT(quat);
    WRITE_ARRAY_FLT(rotAxis);
    WRITE_VALUE_FLT(rotAngle);
    WRITE_ARRAY_FLT(size);
    /* No need to write back 'rotmode' as it can't be transformed. */

#undef WRITE_ARRAY_FLT
#undef WRITE_VALUE_FLT
  }

  /* Recalculate handles. */
  for (int i = 0; i < fcurve_array_len; i++) {
    calchandles_fcurve_ex(fcurve_array[i], 0);
  }

  MEM_freeN((void *)keyed_frames);

  for (int chan = 0; chan < FCURVE_CHANNEL_LEN; chan++) {
    struct FCurve_KeyCache *fkc = (struct FCurve_KeyCache *)(&fkc_pchan) + chan;
    if (fkc->fcurve_eval) {
      MEM_freeN(fkc->fcurve_eval);
    }
    if (fkc->bezt_array) {
      MEM_freeN(fkc->bezt_array);
    }
  }
}

/**
 * Swap all RNA paths left/right.
 */
static void action_flip_pchan_rna_paths(struct bAction *act)
{
  const char *path_pose_prefix = "pose.bones[\"";
  const int path_pose_prefix_len = strlen(path_pose_prefix);

  /* Tag curves that have renamed f-curves. */
  LISTBASE_FOREACH (bActionGroup *, agrp, &act->groups) {
    agrp->flag &= ~AGRP_TEMP;
  }

  LISTBASE_FOREACH (FCurve *, fcu, &act->curves) {
    if (!STRPREFIX(fcu->rna_path, path_pose_prefix)) {
      continue;
    }

    const char *name_esc = fcu->rna_path + path_pose_prefix_len;
    const char *name_esc_end = BLI_str_escape_find_quote(name_esc);

    /* While unlikely, an RNA path could be malformed. */
    if (UNLIKELY(name_esc_end == NULL)) {
      continue;
    }

    char name[MAXBONENAME];
    const size_t name_esc_len = (size_t)(name_esc_end - name_esc);
    const size_t name_len = BLI_str_unescape(name, name_esc, name_esc_len);

    /* While unlikely, data paths could be constructed that have longer names than
     * are currently supported. */
    if (UNLIKELY(name_len >= sizeof(name))) {
      continue;
    }

    /* When the flipped name differs, perform the rename. */
    char name_flip[MAXBONENAME];
    BLI_string_flip_side_name(name_flip, name, false, sizeof(name_flip));
    if (!STREQ(name_flip, name)) {
      char name_flip_esc[MAXBONENAME * 2];
      BLI_str_escape(name_flip_esc, name_flip, sizeof(name_flip_esc));
      char *path_flip = BLI_sprintfN("pose.bones[\"%s%s", name_flip_esc, name_esc_end);
      MEM_freeN(fcu->rna_path);
      fcu->rna_path = path_flip;

      if (fcu->grp != NULL) {
        fcu->grp->flag |= AGRP_TEMP;
      }
    }
  }

  /* Rename tagged groups. */
  LISTBASE_FOREACH (bActionGroup *, agrp, &act->groups) {
    if ((agrp->flag & AGRP_TEMP) == 0) {
      continue;
    }
    agrp->flag &= ~AGRP_TEMP;
    char name_flip[MAXBONENAME];
    BLI_string_flip_side_name(name_flip, agrp->name, false, sizeof(name_flip));
    if (!STREQ(name_flip, agrp->name)) {
      STRNCPY(agrp->name, name_flip);
    }
  }
}

void BKE_action_flip_with_pose(struct bAction *act, struct Object *ob_arm)
{
  struct FCurvePathCache *fcache = BKE_fcurve_pathcache_create(&act->curves);
  int i;
  LISTBASE_FOREACH_INDEX (bPoseChannel *, pchan, &ob_arm->pose->chanbase, i) {
    action_flip_pchan(ob_arm, pchan, fcache);
  }
  BKE_fcurve_pathcache_destroy(fcache);

  action_flip_pchan_rna_paths(act);

  DEG_id_tag_update(&act->id, ID_RECALC_COPY_ON_WRITE);
}

/** \} */