src/TortoiseMerge/libsvn_diff/SVNLineDiff.cpp

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