src/TortoiseMerge/libsvn_diff/SVNLineDiff.cpp

   1 // TortoiseGitMerge - a Diff/Patch program
   2
   3 // Copyright (C) 2006-2009, 2011 - TortoiseSVN
   4
   5 // This program is free software; you can redistribute it and/or
   6 // modify it under the terms of the GNU General Public License
   7 // as published by the Free Software Foundation; either version 2
   8 // of the License, or (at your option) any later version.
   9
  10 // This program is distributed in the hope that it will be useful,
  11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 // GNU General Public License for more details.
  14
  15 // You should have received a copy of the GNU General Public License
  16 // along with this program; if not, write to the Free Software Foundation,
  17 // 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18 //
  19 #include "stdafx.h"
  20 #include "SVNLineDiff.h"
  21
  22 const svn_diff_fns2_t SVNLineDiff::SVNLineDiff_vtable =
  23 {
  24         SVNLineDiff::datasources_open,
  25         SVNLineDiff::datasource_close,
  26         SVNLineDiff::next_token,
  27         SVNLineDiff::compare_token,
  28         SVNLineDiff::discard_token,
  29         SVNLineDiff::discard_all_token
  30 };
  31
  32 #define SVNLINEDIFF_CHARTYPE_NONE                       0
  33 #define SVNLINEDIFF_CHARTYPE_ALPHANUMERIC       1
  34 #define SVNLINEDIFF_CHARTYPE_SPACE                      2
  35 #define SVNLINEDIFF_CHARTYPE_OTHER                      3
  36
  37 typedef void (*LineParser)(LPCTSTR line, apr_size_t lineLength, std::vector<std::wstring> &tokens);
  38
  39 void SVNLineDiff::ParseLineWords(
  40         LPCTSTR line, apr_size_t lineLength, std::vector<std::wstring> &tokens)
  41 {
  42         std::wstring token;
  43         int prevCharType = SVNLINEDIFF_CHARTYPE_NONE;
  44         tokens.reserve(lineLength/2);
  45         for (apr_size_t i = 0; i < lineLength; ++i)
  46         {
  47                 int charType =
  48                         IsCharAlphaNumeric(line[i]) ? SVNLINEDIFF_CHARTYPE_ALPHANUMERIC :
  49                         IsCharWhiteSpace(line[i]) ? SVNLINEDIFF_CHARTYPE_SPACE :
  50                         SVNLINEDIFF_CHARTYPE_OTHER;
  51
  52                 // Token is a sequence of either alphanumeric or whitespace characters.
  53                 // Treat all other characters as a separate tokens.
  54                 if (charType == prevCharType && charType != SVNLINEDIFF_CHARTYPE_OTHER)
  55                         token += line[i];
  56                 else
  57                 {
  58                         if (!token.empty())
  59                                 tokens.push_back(token);
  60                         token = line[i];
  61                 }
  62                 prevCharType = charType;
  63         }
  64         if (!token.empty())
  65                 tokens.push_back(token);
  66 }
  67
  68 void SVNLineDiff::ParseLineChars(
  69         LPCTSTR line, apr_size_t lineLength, std::vector<std::wstring> &tokens)
  70 {
  71         std::wstring token;
  72         for (apr_size_t i = 0; i < lineLength; ++i)
  73         {
  74                 token = line[i];
  75                 tokens.push_back(token);
  76         }
  77 }
  78
  79 svn_error_t * SVNLineDiff::datasources_open(void *baton, apr_off_t *prefix_lines, apr_off_t * /*suffix_lines*/, const svn_diff_datasource_e *datasources, apr_size_t datasource_len)
  80 {
  81         SVNLineDiff * linediff = (SVNLineDiff *)baton;
  82         LineParser parser = linediff->m_bWordDiff ? ParseLineWords : ParseLineChars;
  83         for (apr_size_t i = 0; i < datasource_len; i++)
  84         {
  85                 switch (datasources[i])
  86                 {
  87                 case svn_diff_datasource_original:
  88                         parser(linediff->m_line1, linediff->m_line1length, linediff->m_line1tokens);
  89                         break;
  90                 case svn_diff_datasource_modified:
  91                         parser(linediff->m_line2, linediff->m_line2length, linediff->m_line2tokens);
  92                         break;
  93                 }
  94         }
  95         // Don't claim any prefix matches.
  96         *prefix_lines = 0;
  97
  98         return SVN_NO_ERROR;
  99 }
 100
 101 svn_error_t * SVNLineDiff::datasource_close(void * /*baton*/, svn_diff_datasource_e /*datasource*/)
 102 {
 103         return SVN_NO_ERROR;
 104 }
 105
 106 void SVNLineDiff::NextTokenWords(
 107         apr_uint32_t* hash, void** token, apr_size_t& linePos, const std::vector<std::wstring>& tokens)
 108 {
 109         if (linePos < tokens.size())
 110         {
 111                 *token = (void*)tokens[linePos].c_str();
 112                 *hash = SVNLineDiff::Adler32(0, tokens[linePos].c_str(), tokens[linePos].size());
 113                 linePos++;
 114         }
 115 }
 116
 117 void SVNLineDiff::NextTokenChars(
 118         apr_uint32_t* hash, void** token, apr_size_t& linePos, LPCTSTR line, apr_size_t lineLength)
 119 {
 120         if (linePos < lineLength)
 121         {
 122                 *token = (void*)&line[linePos];
 123                 *hash = line[linePos];
 124                 linePos++;
 125         }
 126 }
 127
 128 svn_error_t * SVNLineDiff::next_token(
 129         apr_uint32_t * hash, void ** token, void * baton, svn_diff_datasource_e datasource)
 130 {
 131         SVNLineDiff * linediff = (SVNLineDiff *)baton;
 132         *token = NULL;
 133         switch (datasource)
 134         {
 135         case svn_diff_datasource_original:
 136                 if (linediff->m_bWordDiff)
 137                         NextTokenWords(hash, token, linediff->m_line1pos, linediff->m_line1tokens);
 138                 else
 139                         NextTokenChars(hash, token, linediff->m_line1pos, linediff->m_line1, linediff->m_line1length);
 140                 break;
 141         case svn_diff_datasource_modified:
 142                 if (linediff->m_bWordDiff)
 143                         NextTokenWords(hash, token, linediff->m_line2pos, linediff->m_line2tokens);
 144                 else
 145                         NextTokenChars(hash, token, linediff->m_line2pos, linediff->m_line2, linediff->m_line2length);
 146                 break;
 147         }
 148         return SVN_NO_ERROR;
 149 }
 150
 151 svn_error_t * SVNLineDiff::compare_token(void * baton, void * token1, void * token2, int * compare)
 152 {
 153         SVNLineDiff * linediff = (SVNLineDiff *)baton;
 154         if (linediff->m_bWordDiff)
 155         {
 156                 LPCTSTR s1 = (LPCTSTR)token1;
 157                 LPCTSTR s2 = (LPCTSTR)token2;
 158                 if (s1 && s2)
 159                 {
 160                         *compare = _tcscmp(s1, s2);
 161                 }
 162         }
 163         else
 164         {
 165                 TCHAR * c1 = (TCHAR *)token1;
 166                 TCHAR * c2 = (TCHAR *)token2;
 167                 if (c1 && c2)
 168                 {
 169                         if (*c1 == *c2)
 170                                 *compare = 0;
 171                         else if (*c1 < *c2)
 172                                 *compare = -1;
 173                         else
 174                                 *compare = 1;
 175                 }
 176         }
 177         return SVN_NO_ERROR;
 178 }
 179
 180 void SVNLineDiff::discard_token(void * /*baton*/, void * /*token*/)
 181 {
 182 }
 183
 184 void SVNLineDiff::discard_all_token(void * /*baton*/)
 185 {
 186 }
 187
 188 SVNLineDiff::SVNLineDiff()
 189         : m_pool(NULL)
 190         , m_subpool(NULL)
 191         , m_line1(NULL)
 192         , m_line1length(0)
 193         , m_line2(NULL)
 194         , m_line2length(0)
 195         , m_line1pos(0)
 196         , m_line2pos(0)
 197         , m_bWordDiff(false)
 198 {
 199         m_pool = svn_pool_create(NULL);
 200 }
 201
 202 SVNLineDiff::~SVNLineDiff()
 203 {
 204         svn_pool_destroy(m_pool);
 205 };
 206
 207 bool SVNLineDiff::Diff(svn_diff_t **diff, LPCTSTR line1, apr_size_t len1, LPCTSTR line2, apr_size_t len2, bool bWordDiff)
 208 {
 209         if (m_subpool)
 210                 svn_pool_clear(m_subpool);
 211         else
 212                 m_subpool = svn_pool_create(m_pool);
 213
 214         if (m_subpool == NULL)
 215                 return false;
 216
 217         m_bWordDiff = bWordDiff;
 218         m_line1 = line1;
 219         m_line2 = line2;
 220         m_line1length = len1 ? len1 : _tcslen(m_line1);
 221         m_line2length = len2 ? len2 : _tcslen(m_line2);
 222
 223         m_line1pos = 0;
 224         m_line2pos = 0;
 225         m_line1tokens.clear();
 226         m_line2tokens.clear();
 227         svn_error_t * err = svn_diff_diff_2(diff, this, &SVNLineDiff_vtable, m_subpool);
 228         if (err)
 229         {
 230                 svn_error_clear(err);
 231                 svn_pool_clear(m_subpool);
 232                 return false;
 233         }
 234         return true;
 235 }
 236
 237 #define ADLER_MOD_BASE 65521
 238 #define ADLER_MOD_BLOCK_SIZE 5552
 239
 240 apr_uint32_t SVNLineDiff::Adler32(apr_uint32_t checksum, const WCHAR *data, apr_size_t len)
 241 {
 242         const unsigned char * input = (const unsigned char *)data;
 243         apr_uint32_t s1 = checksum & 0xFFFF;
 244         apr_uint32_t s2 = checksum >> 16;
 245         apr_uint32_t b;
 246         len *= 2;
 247         apr_size_t blocks = len / ADLER_MOD_BLOCK_SIZE;
 248
 249         len %= ADLER_MOD_BLOCK_SIZE;
 250
 251         while (blocks--)
 252         {
 253                 int count = ADLER_MOD_BLOCK_SIZE;
 254                 while (count--)
 255                 {
 256                         b = *input++;
 257                         s1 += b;
 258                         s2 += s1;
 259                 }
 260
 261                 s1 %= ADLER_MOD_BASE;
 262                 s2 %= ADLER_MOD_BASE;
 263         }
 264
 265         while (len--)
 266         {
 267                 b = *input++;
 268                 s1 += b;
 269                 s2 += s1;
 270         }
 271
 272         return ((s2 % ADLER_MOD_BASE) << 16) | (s1 % ADLER_MOD_BASE);
 273 }
 274
 275 bool SVNLineDiff::IsCharWhiteSpace(TCHAR c)
 276 {
 277         return (c == ' ') || (c == '\t');
 278 }
 279
 280 bool SVNLineDiff::ShowInlineDiff(svn_diff_t* diff)
 281 {
 282         svn_diff_t* tempdiff = diff;
 283         apr_size_t diffcounts = 0;
 284         apr_off_t origsize = 0;
 285         apr_off_t diffsize = 0;
 286         while (tempdiff)
 287         {
 288                 if (tempdiff->type == svn_diff__type_common)
 289                 {
 290                         origsize += tempdiff->original_length;
 291                 }
 292                 else
 293                 {
 294                         diffcounts++;
 295                         diffsize += tempdiff->original_length;
 296                         diffsize += tempdiff->modified_length;
 297                 }
 298                 tempdiff = tempdiff->next;
 299         }
 300         return (origsize > 0.5 * diffsize + 1.0 * diffcounts); // Multiplier values may be subject to individual preferences
 301 }