src/TortoiseMerge/libsvn_diff/SVNLineDiff.cpp

   1 // TortoiseMerge - a Diff/Patch program
   2
   3 // Copyright (C) 2006-2008 - 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 <tchar.h>
  21 #include <vector>
  22 #include "SVNLineDiff.h"
  23
  24 const svn_diff_fns_t SVNLineDiff::SVNLineDiff_vtable =
  25 {
  26         SVNLineDiff::datasource_open,
  27         SVNLineDiff::datasource_close,
  28         SVNLineDiff::next_token,
  29         SVNLineDiff::compare_token,
  30         SVNLineDiff::discard_token,
  31         SVNLineDiff::discard_all_token
  32 };
  33
  34 #define SVNLINEDIFF_CHARTYPE_NONE                       0
  35 #define SVNLINEDIFF_CHARTYPE_ALPHANUMERIC       1
  36 #define SVNLINEDIFF_CHARTYPE_SPACE                      2
  37 #define SVNLINEDIFF_CHARTYPE_OTHER                      3
  38
  39 typedef void (*LineParser)(LPCTSTR line, unsigned long lineLength, std::vector<std::wstring> &tokens);
  40
  41 void SVNLineDiff::ParseLineWords(
  42         LPCTSTR line, unsigned long lineLength, std::vector<std::wstring> &tokens)
  43 {
  44         std::wstring token;
  45         int prevCharType = SVNLINEDIFF_CHARTYPE_NONE;
  46         for (unsigned long i = 0; i < lineLength; ++i)
  47         {
  48                 int charType =
  49                         IsCharAlphaNumeric(line[i]) ? SVNLINEDIFF_CHARTYPE_ALPHANUMERIC :
  50                         IsCharWhiteSpace(line[i]) ? SVNLINEDIFF_CHARTYPE_SPACE :
  51                         SVNLINEDIFF_CHARTYPE_OTHER;
  52
  53                 // Token is a sequence of either alphanumeric or whitespace characters.
  54                 // Treat all other characters as a separate tokens.
  55                 if (charType == prevCharType && charType != SVNLINEDIFF_CHARTYPE_OTHER)
  56                         token += line[i];
  57                 else
  58                 {
  59                         if (!token.empty())
  60                                 tokens.push_back(token);
  61                         token = line[i];
  62                 }
  63                 prevCharType = charType;
  64         }
  65         if (!token.empty())
  66                 tokens.push_back(token);
  67 }
  68
  69 void SVNLineDiff::ParseLineChars(
  70         LPCTSTR line, unsigned long lineLength, std::vector<std::wstring> &tokens)
  71 {
  72         std::wstring token;
  73         for (unsigned long i = 0; i < lineLength; ++i)
  74         {
  75                 token = line[i];
  76                 tokens.push_back(token);
  77         }
  78 }
  79
  80 svn_error_t * SVNLineDiff::datasource_open(void * baton, svn_diff_datasource_e datasource)
  81 {
  82         SVNLineDiff * linediff = (SVNLineDiff *)baton;
  83         LineParser parser = linediff->m_bWordDiff ? ParseLineWords : ParseLineChars;
  84         switch (datasource)
  85         {
  86                 case svn_diff_datasource_original:
  87                         parser(linediff->m_line1, linediff->m_line1length, linediff->m_line1tokens);
  88                         break;
  89                 case svn_diff_datasource_modified:
  90                         parser(linediff->m_line2, linediff->m_line2length, linediff->m_line2tokens);
  91                         break;
  92         }
  93         return SVN_NO_ERROR;
  94 }
  95
  96 svn_error_t * SVNLineDiff::datasource_close(void * /*baton*/, svn_diff_datasource_e /*datasource*/)
  97 {
  98         return SVN_NO_ERROR;
  99 }
 100
 101 void SVNLineDiff::NextTokenWords(
 102         apr_uint32_t* hash, void** token, unsigned long& linePos, const std::vector<std::wstring>& tokens)
 103 {
 104         if (linePos < tokens.size())
 105         {
 106                 *token = (void*)tokens[linePos].c_str();
 107                 *hash = SVNLineDiff::Adler32(0, tokens[linePos].c_str(), tokens[linePos].size());
 108                 linePos++;
 109         }
 110 }
 111
 112 void SVNLineDiff::NextTokenChars(
 113         apr_uint32_t* hash, void** token, unsigned long& linePos, LPCTSTR line, unsigned long lineLength)
 114 {
 115         if (linePos < lineLength)
 116         {
 117                 *token = (void*)&line[linePos];
 118                 *hash = line[linePos];
 119                 linePos++;
 120         }
 121 }
 122
 123 svn_error_t * SVNLineDiff::next_token(
 124         apr_uint32_t * hash, void ** token, void * baton, svn_diff_datasource_e datasource)
 125 {
 126         SVNLineDiff * linediff = (SVNLineDiff *)baton;
 127         *token = NULL;
 128         switch (datasource)
 129         {
 130         case svn_diff_datasource_original:
 131                 if (linediff->m_bWordDiff)
 132                         NextTokenWords(hash, token, linediff->m_line1pos, linediff->m_line1tokens);
 133                 else
 134                         NextTokenChars(hash, token, linediff->m_line1pos, linediff->m_line1, linediff->m_line1length);
 135                 break;
 136         case svn_diff_datasource_modified:
 137                 if (linediff->m_bWordDiff)
 138                         NextTokenWords(hash, token, linediff->m_line2pos, linediff->m_line2tokens);
 139                 else
 140                         NextTokenChars(hash, token, linediff->m_line2pos, linediff->m_line2, linediff->m_line2length);
 141                 break;
 142         }
 143         return SVN_NO_ERROR;
 144 }
 145
 146 svn_error_t * SVNLineDiff::compare_token(void * baton, void * token1, void * token2, int * compare)
 147 {
 148         SVNLineDiff * linediff = (SVNLineDiff *)baton;
 149         if (linediff->m_bWordDiff)
 150         {
 151                 LPCTSTR s1 = (LPCTSTR)token1;
 152                 LPCTSTR s2 = (LPCTSTR)token2;
 153                 if (s1 && s2)
 154                 {
 155                         *compare = _tcscmp(s1, s2);
 156                 }
 157         }
 158         else
 159         {
 160                 TCHAR * c1 = (TCHAR *)token1;
 161                 TCHAR * c2 = (TCHAR *)token2;
 162                 if (c1 && c2)
 163                 {
 164                         if (*c1 == *c2)
 165                                 *compare = 0;
 166                         else if (*c1 < *c2)
 167                                 *compare = -1;
 168                         else
 169                                 *compare = 1;
 170                 }
 171         }
 172         return SVN_NO_ERROR;
 173 }
 174
 175 void SVNLineDiff::discard_token(void * /*baton*/, void * /*token*/)
 176 {
 177 }
 178
 179 void SVNLineDiff::discard_all_token(void * /*baton*/)
 180 {
 181 }
 182
 183 SVNLineDiff::SVNLineDiff()
 184         : m_pool(NULL)
 185         , m_subpool(NULL)
 186         , m_line1(NULL)
 187         , m_line1length(0)
 188         , m_line2(NULL)
 189         , m_line2length(0)
 190         , m_line1pos(0)
 191         , m_line2pos(0)
 192         , m_bWordDiff(false)
 193 {
 194         m_pool = svn_pool_create(NULL);
 195 }
 196
 197 SVNLineDiff::~SVNLineDiff()
 198 {
 199         svn_pool_destroy(m_pool);
 200 };
 201
 202 bool SVNLineDiff::Diff(svn_diff_t **diff, LPCTSTR line1, int len1, LPCTSTR line2, int len2, bool bWordDiff)
 203 {
 204         if (m_subpool)
 205                 svn_pool_clear(m_subpool);
 206         else
 207                 m_subpool = svn_pool_create(m_pool);
 208
 209         if (m_subpool == NULL)
 210                 return false;
 211
 212         m_bWordDiff = bWordDiff;
 213         m_line1 = line1;
 214         m_line2 = line2;
 215         m_line1length = len1 ? len1 : _tcslen(m_line1);
 216         m_line2length = len2 ? len2 : _tcslen(m_line2);
 217
 218         m_line1pos = 0;
 219         m_line2pos = 0;
 220         m_line1tokens.clear();
 221         m_line2tokens.clear();
 222         svn_error_t * err = svn_diff_diff(diff, this, &SVNLineDiff_vtable, m_subpool);
 223         if (err)
 224         {
 225                 svn_error_clear(err);
 226                 svn_pool_clear(m_subpool);
 227                 return false;
 228         }
 229         return true;
 230 }
 231
 232 #define ADLER_MOD_BASE 65521
 233 #define ADLER_MOD_BLOCK_SIZE 5552
 234
 235 apr_uint32_t SVNLineDiff::Adler32(apr_uint32_t checksum, const WCHAR *data, apr_size_t len)
 236 {
 237         const unsigned char * input = (const unsigned char *)data;
 238         apr_uint32_t s1 = checksum & 0xFFFF;
 239         apr_uint32_t s2 = checksum >> 16;
 240         apr_uint32_t b;
 241         len *= 2;
 242         apr_size_t blocks = len / ADLER_MOD_BLOCK_SIZE;
 243
 244         len %= ADLER_MOD_BLOCK_SIZE;
 245
 246         while (blocks--)
 247         {
 248                 int count = ADLER_MOD_BLOCK_SIZE;
 249                 while (count--)
 250                 {
 251                         b = *input++;
 252                         s1 += b;
 253                         s2 += s1;
 254                 }
 255
 256                 s1 %= ADLER_MOD_BASE;
 257                 s2 %= ADLER_MOD_BASE;
 258         }
 259
 260         while (len--)
 261         {
 262                 b = *input++;
 263                 s1 += b;
 264                 s2 += s1;
 265         }
 266
 267         return ((s2 % ADLER_MOD_BASE) << 16) | (s1 % ADLER_MOD_BASE);
 268 }
 269
 270 bool SVNLineDiff::IsCharWhiteSpace(TCHAR c)
 271 {
 272         return (c == ' ') || (c == '\t');
 273 }
 274
 275 bool SVNLineDiff::ShowInlineDiff(svn_diff_t* diff)
 276 {
 277         svn_diff_t* tempdiff = diff;
 278         int diffcounts = 0;
 279         int origcounts = 0;
 280         apr_off_t origsize = 0;
 281         apr_off_t diffsize = 0;
 282         while (tempdiff)
 283         {
 284                 if (tempdiff->type == svn_diff__type_common)
 285                 {
 286                         origcounts++;
 287                         origsize += tempdiff->original_length;
 288                 }
 289                 else
 290                 {
 291                         diffcounts++;
 292                         diffsize += tempdiff->original_length;
 293                         diffsize += tempdiff->modified_length;
 294                 }
 295                 tempdiff = tempdiff->next;
 296         }
 297         return (origcounts >= diffcounts) && (origsize > diffsize);
 298 }