diff3.hpp

Go to the documentation of this file.

/*
 *      Interactive disassembler (IDA).
 *      Copyright (c) 2005-2025 Hex-Rays SA <support@hex-rays.com>
 *      ALL RIGHTS RESERVED.
 */
 
#ifndef _DIFF3_HPP
#define _DIFF3_HPP

 
// The diffing algorithms in this file match information tied to addresses.
// So, if addresses do not match, the information will be considered to be different.
 
//-------------------------------------------------------------------------
struct diff_range_t
{
  diffpos_t start;
  diffpos_t end;
  diff_range_t(diffpos_t s=0, diffpos_t e=0) : start(s), end(e) {}
  bool empty() const { return start >= end; }
  void clear() { start = end = 0; }
  bool contains(diffpos_t p) const { return start <= p && p < end; }
  void set_start(diffpos_t p)
  {
    start = p;
    if ( end < start )
      end = start;
  }
  void set_end(diffpos_t p)
  {
    end = p;
    if ( end < start )
      start = end;
  }
  void intersect(const diff_range_t &r)
  {
    if ( start < r.start )
      start = r.start;
    if ( end > r.end )
      end = r.end;
    if ( end < start )
      end = start;
  }
 
  int compare(const diff_range_t &r) const { return start > r.start ? 1 : start < r.start ? -1 : 0; }
 
  bool operator ==(const diff_range_t &r) const { return compare(r) == 0; }
  bool operator !=(const diff_range_t &r) const { return compare(r) != 0; }
};
DECLARE_TYPE_AS_MOVABLE(diff_range_t);
 
//------------------------------------------------------------------------
typedef ssize_t diff_degree_t;
 
//------------------------------------------------------------------------
enum diff_action_t
{
  DIFF_NONE, 
  DIFF_USE1, 
  DIFF_USE2, 
  DIFF_BOTH, 
};
 
//------------------------------------------------------------------------
struct diff_region_t : public diff_range_t
{
  diff_degree_t diff_degree = 0;
  diff_action_t action = DIFF_BOTH;
  void clear() { diff_range_t::clear(); action = DIFF_NONE; }
  bool is_useless() const { return empty() || diff_degree == 0; }
  qstring dstr() const;
};
DECLARE_TYPE_AS_MOVABLE(diff_region_t);
typedef qvector<diff_region_t> diff_regions_t;
 
//------------------------------------------------------------------------
enum diffpos_check_t
{
  DIFFPOS_CHECK,        
  DIFFPOS_FORWARD,      
  DIFFPOS_BACKWARD,     
};
 
//------------------------------------------------------------------------
struct diff_text_t : public qstrvec_t
{
  diffpos_t pos;
};
DECLARE_TYPE_AS_MOVABLE(diff_text_t);
typedef qvector<diff_text_t> diff_texts_t;
 
//--------------------------------------------------------------------------
enum diff_source_idx_t
{
  NONE_IDX = -1,
  LOCAL_IDX = 0,
  REMOTE_IDX = 1,
  BASE_IDX = 2
};
 
//------------------------------------------------------------------------
#ifndef SWIG
#define DECLARE_DIFF_SOURCE_HELPERS(decl)\
decl void ida_export diff_source_merge_region(class diff_source_t *destination, class diff_source_t *source, const diff_range_t &dr);
#else
#define DECLARE_DIFF_SOURCE_HELPERS(decl)
#endif // SWIG
 
DECLARE_DIFF_SOURCE_HELPERS(idaman)
 
//------------------------------------------------------------------------
class diff_source_t
{
  friend class diff3_engine_t;
  diffpos_t get_lastpos(const diff_range_t &r)
  {
    diffpos_t last = check_position(r.end, DIFFPOS_BACKWARD);
    if ( last < r.start )
      last = r.end;
    if ( last == BADDIFF )
      last = r.start;
    return last;
  }
 
  void _merge_region(diff_source_t *source, const diff_range_t &dr);
 
  DECLARE_DIFF_SOURCE_HELPERS(friend)
 
public:
  int dbctx_id;
  diff_source_idx_t diffidx = NONE_IDX;
  diff_range_t range = diff_range_t(0, BADDIFF);
  diff_source_t(int id) : dbctx_id(id) {}
 
  virtual ~diff_source_t() {}

  virtual void init_diff_source() {}

  virtual void set_range(const diff_range_t &r) { range = r; }

  virtual const diff_range_t &get_range() const { return range; }

  virtual diffpos_t check_position(diffpos_t dpos, diffpos_check_t adj=DIFFPOS_CHECK) const = 0;

  virtual diff_degree_t compare_chunks(diff_source_t *src2, diffpos_t dpos) const = 0;

  virtual diff_degree_t find_next_diffpos(
        diffpos_t * /*dpos1*/,
        diffpos_t * /*dpos2*/,
        diff_source_t * /*src2*/) const
  {
    return -1; // not implemented
  }

  virtual qstring print_diffpos_name(diffpos_t dpos) const = 0;

  virtual void print_diffpos_details(qstrvec_t * /*out*/, diffpos_t /*dpos*/) const {}

  virtual void merge_add(diff_source_t * /*src*/, diffpos_t /*dpos*/) {}

  virtual void merge_del(diffpos_t /*dpos*/) {}

  virtual void merge_replace(diff_source_t *src, diffpos_t dpos)
  {
    merge_del(dpos);
    merge_add(src, dpos);
  }

  virtual void merge_region(diff_source_t *src, const diff_range_t &region)
  {
    diff_source_merge_region(this, src, region);
  }
 
#ifdef TESTABLE_BUILD
  // dump the test results into the provided log file.
  // nb: there is no need to switch dbctx, it is already done.
  virtual void dump_merge_results(FILE * /*fp*/) const {}
#endif
 
  diff_texts_t print_range(const diff_range_t *r, bool with_details) const;
  void test_diffpos_behavior() const;
  bool is_valid_position(diffpos_t dpos) const
  {
    return get_range().contains(dpos) && check_position(dpos) == dpos;
  }
  diff_texts_t print_diff_source(bool with_details=true) const
  {
    return print_range(nullptr, with_details);
  }
};
 
//------------------------------------------------------------------------
enum merge_policy_t ENUM_SIZE(uint8)
{
  MERGE_POLICY_SKIP,       
  MERGE_POLICY_USE_LOCAL,  
  MERGE_POLICY_USE_REMOTE, 
  MERGE_POLICY_POSTPONE,   
  MERGE_POLICY_MDIFF,      
  MERGE_POLICY_VDIFF,      
  MERGE_POLICY_LAST,
};
 
//------------------------------------------------------------------------
struct diff_result_t
{
  diff_source_t *src1;
  diff_source_t *src2;
  diff_regions_t regions;
  diff_result_t(diff_source_t *s1=nullptr, diff_source_t *s2=nullptr) : src1(s1), src2(s2) {}
  qstrvec_t print_region(const diff_region_t &b, bool with_details=true) const;
  qstrvec_t print_diff_result(bool with_details=true) const;
  size_t size() const { return regions.size(); }
  bool empty() const { return regions.empty(); }

  size_t merge_diff_sources(merge_policy_t merge_policy, size_t i1=0, size_t i2=SIZE_MAX);
private:
  bool merge_one_region(size_t n, merge_policy_t merge_policy) const;
};
 
//------------------------------------------------------------------------
class diff_engine_t
{
  friend class diff3_engine_t;
protected:
  diff_source_t *src1;
  diff_source_t *src2;
 
public:
  diff_engine_t(diff_source_t *_src1, diff_source_t *_src2)
    : src1(_src1), src2(_src2)
  {
  }
  virtual bool get_diff_regions(diff_regions_t *out) = 0;
  diff_result_t perform_diff();
};
 
//------------------------------------------------------------------------
class diff2_engine_t : public diff_engine_t
{
  // we maintain two positions to optimize calls to adjust_position
  // if you decide to remove one of them, please ensure that
  // std::lower_bound in testdiff3.cpp is not called too often
  diffpos_t pos1;
  diffpos_t pos2;
  diff_degree_t calc_diff_degree(diff_degree_t cur_degree);
public:
  diff2_engine_t(diff_source_t *_src1, diff_source_t *_src2)
    : diff_engine_t(_src1, _src2)
  {
    reset();
  }
  void reset();
  virtual bool get_diff_regions(diff_regions_t *out) override;
  bool get_diff_region(diff_region_t *out);
};
 
//------------------------------------------------------------------------
class diff3_engine_t : public diff2_engine_t
{
  diff2_engine_t de1; 
  diff2_engine_t de2; 
  diff2_engine_t de3; 
 
public:
  diff3_engine_t(
        diff_source_t *base,
        diff_source_t *src1,
        diff_source_t *src2);
  virtual ~diff3_engine_t() {}
  virtual bool get_diff_regions(diff_regions_t *out) override;
};

diff_result_t perform_diff3(
        diff_source_t *base,
        diff_source_t *src1,
        diff_source_t *src2);
 
qstrvec_t put_side_by_side(
        const char *const *headers,
        const diff_texts_t *const *linevecs,
        size_t n,
        int psbs_flags=0);
#define PSBS_DIFF_STARS 0x01    
#define PSBS_ONLY_DIFFS 0x02    
 
//-------------------------------------------------------------------------
enum lcsdiff_result_action_t
{
  TDLA_EQ = 0,  
  TDLA_ADD,     
  TDLA_SUB,     
  TDLA_MOD,     
};
 
//-------------------------------------------------------------------------

template<class T>
struct lcsdiff_res_part_t
{
  T part;                         
  T x_part;                       
  lcsdiff_result_action_t action; 
 
  lcsdiff_res_part_t(lcsdiff_result_action_t _a) : action(_a) {}
 
  void append(const T &v, size_t idx) { part.push_back(v[idx]); }
  void reverse() { std::reverse(part.begin(), part.end()); }
};
// template specialisation for qstring vector
template<>
struct lcsdiff_res_part_t<qstring>
{
  qstring part;                   
  qstring x_part;                 
  lcsdiff_result_action_t action; 
 
  lcsdiff_res_part_t(lcsdiff_result_action_t _a) : action(_a) {}
 
  void append(const qstring &v, size_t idx) { part.append(v[idx]); }
  void reverse() { if ( !part.empty() ) std::reverse(part.begin(), std::prev(part.end())); }
};
DECLARE_TYPE_AS_MOVABLE(lcsdiff_res_part_t<qstrvec_t>);
DECLARE_TYPE_AS_MOVABLE(lcsdiff_res_part_t<qstring>);

template<class T>
class lcsdiff_res_t : public qvector<lcsdiff_res_part_t<T>>
{
public:
  void eq(const T &v, size_t idx)
  {
    lcsdiff_res_part_t<T> &part = set_action(TDLA_EQ);
    part.append(v, idx);
  }

  void add(const T &v, size_t idx)
  {
    lcsdiff_res_part_t<T> &part = set_action(TDLA_ADD);
    part.append(v, idx);
  }

  void sub(const T &v, size_t idx)
  {
    lcsdiff_res_part_t<T> &part = set_action(TDLA_SUB);
    part.append(v, idx);
  }
 
private:
  lcsdiff_res_part_t<T> &set_action(lcsdiff_result_action_t wanted_action)
  {
    if ( this->empty() || this->back().action != wanted_action )
      this->push_back(lcsdiff_res_part_t<T>(wanted_action));
    return this->back();
  }
};
 
//-------------------------------------------------------------------------
template<class T>
class lcsdiff_t
{
protected:
  const T &x;                     
  const T &y;                     
  const size_t n = 0;             
  const size_t m = 0;             
  sizevec_t lcs_table;            
 
public:
  using result_t = lcsdiff_res_t<T>;
  result_t result;
 
  //------------------------------------------------------------------
  lcsdiff_t(const T &_x, const T &_y, size_t _n, size_t _m)
    : x(_x),
      y(_y),
      n(_n),
      m(_m)
  {
    // allocate storage for TABLE
    // need an additional row/column at index 0
    const size_t rows = n + 1;
    const size_t cols = m + 1;
    lcs_table.resize(rows * cols);
 
    // compute the LCS for substring started from (i,j) indices
    for ( size_t i=0; i < rows; ++i )
    {
      for ( size_t j=0; j < cols; ++j )
      {
        if ( i == 0 || j == 0 )
        {
          table(i, j) = 0;
        }
        else if ( x[i - 1] == y[j - 1] )
        {
          table(i, j) = 1 + table(i - 1, j - 1);
        }
        else
        {
          size_t l = table(i - 1, j);
          size_t u = table(i, j - 1);
          table(i, j) = qmax(l, u);
        }
      }
    }
  }
 
  //------------------------------------------------------------------
  void diff()
  {
    result.clear();
    size_t i = n;
    size_t j = m;
    while ( i != 0 || j != 0 )
    {
      // end of seq reached
      if ( i == 0 )
      {
        result.add(y, --j);
      }
      else if ( j == 0 )
      {
        result.sub(x, --i);
      }
      // Otherwise there's still parts of X and Y left. If the
      // currently considered parts are equal, then we found an unchanged
      // part which belongs to the longest common subsequence.
      else if ( x[i - 1] == y[j - 1] )
      {
        result.eq(x, --i);
        j--;
      }
      // In any other case, we go in the direction of the longest common subsequence.
      else if ( table(i - 1, j) <= table(i, j - 1) )
      {
        result.add(y, --j);
      }
      else
      {
        result.sub(x, --i);
      }
    }
    std::reverse(result.begin(), result.end());
    for ( auto &part : result )
      part.reverse();
  }
 
private:
  size_t &table(size_t i, size_t j)
  {
    const size_t idx = i * (m + 1) + j;
    QASSERT(2351, idx < lcs_table.size());
    return lcs_table[idx];
  }
};
 
//-------------------------------------------------------------------------
struct txtdiff_printer_t
{
  enum event_t
  {
    init,          
    term,          
 
    // print lines
    next_line,     
 
    same_line,     
    add_line,      
    del_line,      
    mod_line,      
  };
 
  txtdiff_printer_t() {}
  virtual ~txtdiff_printer_t() {}
 
  virtual void on_event(event_t ev, ...) = 0;
};
 
//-------------------------------------------------------------------------
class txtdiff_t;
 
#ifndef SWIG
#define DECLARE_TXTDIFF_HELPERS(decl)\
decl void ida_export txtdiff_t_diff_mod(txtdiff_t *_this);\
decl void ida_export txtdiff_t_serialize(txtdiff_t *_this, txtdiff_printer_t &printer);
#else
#define DECLARE_TXTDIFF_HELPERS(decl)
#endif // SWIG
 
DECLARE_TXTDIFF_HELPERS(idaman)
 
//------------------------------------------------------------------------
class txtdiff_t : public lcsdiff_t<qstrvec_t>
{
public:
  txtdiff_t(const qstrvec_t &_x, const qstrvec_t &_y)
    : lcsdiff_t<qstrvec_t>(_x, _y, _x.size(), _y.size()) {}
 
  //--------------------------------------------------------
  void diff_mod() { txtdiff_t_diff_mod(this); }
 
  //------------------------------------------------------------------------
  void serialize(txtdiff_printer_t &printer) { txtdiff_t_serialize(this, printer); }
 
  //--------------------------------------------------------
  // Convenience methods

  static void visual_diff(qstrvec_t *res, const qstrvec_t &x, const qstrvec_t &y, bool use_mod=true)
  {
    txtdiff_t d(x, y);
    use_mod ? d.diff_mod() : d.diff();
    for ( const auto &dl : d.result )
    {
      char c = dl.action == TDLA_EQ  ? ' '
             : dl.action == TDLA_ADD ? '+'
             : dl.action == TDLA_SUB ? '-'
             :                         '*';   // TDLA_MOD
      for ( auto &p : dl.part )
        res->push_back().sprnt("%c %s", c, p.c_str());
    }
  }
 
private:
  DECLARE_TXTDIFF_HELPERS(friend)
  // do not call these functions directly, they are here only for exporting
  void _diff_mod();
  void _serialize(txtdiff_printer_t &printer);
};
#undef DECLARE_TXTDIFF_HELPERS
 
//-------------------------------------------------------------------------
struct strdiff_printer_t
{
  enum event_t
  {
    init_chars,       
    term_chars,       
 
    same_chars,       
    add_chars,        
    del_chars,        
  };
 
  strdiff_printer_t() {}
  virtual ~strdiff_printer_t() {}
 
  virtual void on_event(event_t ev, ...) = 0;
};
 
//-------------------------------------------------------------------------
class strdiff_t;
 
#ifndef SWIG
#define DECLARE_STRDIFF_HELPERS(decl)\
decl void ida_export strdiff_t_serialize(strdiff_t *_this, strdiff_printer_t &printer);
#else
#define DECLARE_STRDIFF_HELPERS(decl)
#endif // SWIG
 
DECLARE_STRDIFF_HELPERS(idaman)
 
//-------------------------------------------------------------------------
class strdiff_t : public lcsdiff_t<qstring>
{
public:
  strdiff_t(const qstring &_x, const qstring &_y)
    : lcsdiff_t<qstring>(_x, _y, _x.length(), _y.length()) {}
 
  //------------------------------------------------------------------------
  void serialize(strdiff_printer_t &printer) { strdiff_t_serialize(this, printer); }
 
private:
  DECLARE_STRDIFF_HELPERS(friend)
  // do not call these functions directly, they are here only for exporting
  void _serialize(strdiff_printer_t &printer);
};
#undef DECLARE_STRDIFF_HELPERS
#endif // _DIFF3_HPP