Core/StringBuffer.cs

   1 /*
   2  * Copyright (C) 2013 FooProject
   3  * * 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
   4  * the Free Software Foundation; either version 3 of the License, or (at your option) any later version.
   5
   6  * This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
   7  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
   8
   9 You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>.
  10  */
  11 //#define TEST_ASYNC
  12 using System;
  13 using System.IO;
  14 using System.Collections.Generic;
  15 using System.Globalization;
  16 using System.Linq;
  17 using System.Text;
  18 using System.Text.RegularExpressions;
  19 using System.Threading;
  20 using System.Threading.Tasks;
  21 using Slusser.Collections.Generic;
  22
  23 namespace FooEditEngine
  24 {
  25     /// <summary>
  26     /// ランダムアクセス可能な列挙子を提供するインターフェイス
  27     /// </summary>
  28     /// <typeparam name="T"></typeparam>
  29     public interface IRandomEnumrator<T>
  30     {
  31         /// <summary>
  32         /// インデクサーを表す
  33         /// </summary>
  34         /// <param name="index">インデックス</param>
  35         /// <returns>Tを返す</returns>
  36         T this[int index]{get;}
  37     }
  38
  39     sealed class StringBuffer : IEnumerable<char>, IRandomEnumrator<char>
  40     {
  41         GapBuffer<char> buf = new GapBuffer<char>();
  42         const int MaxSemaphoreCount = 1;
  43         SemaphoreSlim Semaphore = new SemaphoreSlim(MaxSemaphoreCount);
  44
  45         public StringBuffer()
  46         {
  47             this.Update = (s, e) => { };
  48         }
  49
  50         /// <summary>
  51         /// ロック中なら真を返し、そうでないなら偽を返す
  52         /// </summary>
  53         public bool IsLocked
  54         {
  55             get
  56             {
  57                 return this.Semaphore.CurrentCount == 0;
  58             }
  59         }
  60
  61         /// <summary>
  62         /// ロックを解除します
  63         /// </summary>
  64         public void UnLock()
  65         {
  66             this.Semaphore.Release();
  67         }
  68
  69         /// <summary>
  70         /// ロックします
  71         /// </summary>
  72         public void Lock()
  73         {
  74             this.Semaphore.Wait();
  75         }
  76
  77         /// <summary>
  78         /// ロックします
  79         /// </summary>
  80         /// <returns>Taskオブジェクト</returns>
  81         public Task LockAsync()
  82         {
  83             return this.Semaphore.WaitAsync();
  84         }
  85
  86         public StringBuffer(StringBuffer buffer)
  87             : this()
  88         {
  89             buf.AddRange(buffer.buf, buffer.Length);
  90         }
  91
  92
  93         public char this[int index]
  94         {
  95             get
  96             {
  97                 char c = buf[index];
  98                 return c;
  99             }
 100         }
 101
 102         public string ToString(int index, int length)
 103         {
 104             this.Lock();
 105
 106             StringBuilder temp = new StringBuilder();
 107             temp.Clear();
 108             for (int i = index; i < index + length; i++)
 109                 temp.Append(buf[i]);
 110
 111             this.UnLock();
 112
 113             return temp.ToString();
 114         }
 115
 116         public IEnumerable<string> GetLines(int startIndex, int endIndex, int maxCharCount = -1)
 117         {
 118             foreach (Tuple<int, int> range in this.ForEachLines(startIndex, endIndex, maxCharCount))
 119             {
 120                 StringBuilder temp = new StringBuilder();
 121                 temp.Clear();
 122                 int lineEndIndex = range.Item1;
 123                 if (range.Item2 > 0)
 124                     lineEndIndex += range.Item2 - 1;
 125                 for (int i = range.Item1; i <= lineEndIndex; i++)
 126                     temp.Append(buf[i]);
 127                 yield return temp.ToString();
 128             }
 129         }
 130
 131         public IEnumerable<Tuple<int,int>> ForEachLines(int startIndex, int endIndex, int maxCharCount = -1)
 132         {
 133             int currentLineHeadIndex = startIndex;
 134             int currentLineLength = 0;
 135
 136             for (int i = startIndex; i <= endIndex; i++)
 137             {
 138                 currentLineLength++;
 139                 char c = this.buf[i];
 140                 if (c == Document.NewLine ||
 141                     (maxCharCount != -1 && currentLineLength >= maxCharCount))
 142                 {
 143                     UnicodeCategory uc = CharUnicodeInfo.GetUnicodeCategory(c);
 144                     if (uc != UnicodeCategory.NonSpacingMark &&
 145                     uc != UnicodeCategory.SpacingCombiningMark &&
 146                     uc != UnicodeCategory.EnclosingMark &&
 147                     uc != UnicodeCategory.Surrogate)
 148                     {
 149                         yield return new Tuple<int,int>(currentLineHeadIndex, currentLineLength);
 150                         currentLineHeadIndex += currentLineLength;
 151                         currentLineLength = 0;
 152                     }
 153                 }
 154             }
 155             if (currentLineLength > 0)
 156                 yield return new Tuple<int, int>(currentLineHeadIndex, currentLineLength);
 157         }
 158
 159         public int Length
 160         {
 161             get { return this.buf.Count; }
 162         }
 163
 164         internal DocumentUpdateEventHandler Update;
 165
 166         internal void Replace(StringBuffer buf)
 167         {
 168             this.Replace(buf.buf);
 169         }
 170
 171         internal void Replace(GapBuffer<char> buf)
 172         {
 173             this.Lock();
 174
 175             this.Clear();
 176             this.buf = buf;
 177
 178             this.UnLock();
 179
 180             this.Update(this, new DocumentUpdateEventArgs(UpdateType.Replace, 0, 0, buf.Count));
 181         }
 182
 183         internal void Replace(int index, int length, IEnumerable<char> chars,int count)
 184         {
 185             this.Lock();
 186
 187             try{
 188                 if (length > 0)
 189                     this.buf.RemoveRange(index, length);
 190                 this.buf.InsertRange(index, chars, count);
 191             }
 192             finally
 193             {
 194                 this.UnLock();
 195             }
 196
 197             this.Update(this, new DocumentUpdateEventArgs(UpdateType.Replace, index, length, count));
 198         }
 199
 200         internal async Task LoadAsync(TextReader fs, CancellationTokenSource tokenSource = null)
 201         {
 202             char[] str = new char[1024 * 256];
 203             int readCount;
 204             do
 205             {
 206                 int index = this.Length;
 207                 if (index < 0)
 208                     index = 0;
 209
 210                 readCount = await fs.ReadAsync(str, 0, str.Length).ConfigureAwait(false);
 211
 212                 //内部形式に変換する
 213                 var internal_str = from s in str where s != '\r' && s != '\0' select s;
 214
 215                 await this.LockAsync().ConfigureAwait(false);
 216                 //str.lengthは事前に確保しておくために使用するので影響はない
 217                 this.buf.InsertRange(index, internal_str, str.Length);
 218
 219                 this.UnLock();
 220
 221                 if (tokenSource != null)
 222                     tokenSource.Token.ThrowIfCancellationRequested();
 223 #if TEST_ASYNC
 224                 System.Diagnostics.Debug.WriteLine("waiting now");
 225                 await Task.Delay(100).ConfigureAwait(false);
 226 #endif
 227                 Array.Clear(str, 0, str.Length);
 228             } while (readCount > 0);
 229         }
 230
 231         internal async Task SaveAsync(TextWriter fs, CancellationTokenSource tokenSource = null)
 232         {
 233             try
 234             {
 235                 await this.LockAsync().ConfigureAwait(false);
 236                 StringBuilder line = new StringBuilder();
 237                 for (int i = 0; i < this.Length; i++)
 238                 {
 239                     char c = this[i];
 240                     line.Append(c);
 241                     if (c == Document.NewLine || i == this.Length - 1)
 242                     {
 243                         string str = line.ToString();
 244                         str = str.Replace(Document.NewLine.ToString(), fs.NewLine);
 245                         await fs.WriteAsync(str).ConfigureAwait(false);
 246                         line.Clear();
 247                         if (tokenSource != null)
 248                             tokenSource.Token.ThrowIfCancellationRequested();
 249 #if TEST_ASYNC
 250                     System.Threading.Thread.Sleep(10);
 251 #endif
 252                     }
 253                 }
 254             }
 255             finally
 256             {
 257                 this.UnLock();
 258             }
 259         }
 260
 261         internal void ReplaceRegexAll(LineToIndexTable layoutlines, Regex regex, string pattern, bool groupReplace)
 262         {
 263             for (int i = 0; i < layoutlines.Count; i++)
 264             {
 265                 int lineHeadIndex = layoutlines.GetIndexFromLineNumber(i), lineLength = layoutlines.GetLengthFromLineNumber(i);
 266                 int left = lineHeadIndex, right = lineHeadIndex;
 267                 string output = regex.Replace(layoutlines[i], (m) => {
 268                     if (groupReplace)
 269                         return m.Result(pattern);
 270                     else
 271                         return pattern;
 272                 });
 273
 274                 this.Lock();
 275                 try
 276                 {
 277                     //空行は削除する必要はない
 278                     if (lineHeadIndex < this.buf.Count)
 279                         this.buf.RemoveRange(lineHeadIndex, lineLength);
 280                     this.buf.InsertRange(lineHeadIndex, output, output.Length);
 281                 }
 282                 finally
 283                 {
 284                     this.UnLock();
 285                 }
 286
 287                 this.Update(this, new DocumentUpdateEventArgs(UpdateType.Replace, lineHeadIndex, lineLength, output.Length, i));
 288             }
 289         }
 290
 291         internal void ReplaceAll(LineToIndexTable layoutlines,string target, string pattern, bool ci = false)
 292         {
 293             TextSearch ts = new TextSearch(target, ci);
 294             char[] pattern_chars = pattern.ToCharArray();
 295             for(int i = 0; i < layoutlines.Count; i++)
 296             {
 297                 int lineHeadIndex = layoutlines.GetIndexFromLineNumber(i), lineLength = layoutlines.GetLengthFromLineNumber(i);
 298                 int left = lineHeadIndex, right = lineHeadIndex;
 299                 int newLineLength = lineLength;
 300                 while ((right = ts.IndexOf(this.buf, left, lineHeadIndex + newLineLength)) != -1)
 301                 {
 302                     this.Lock();
 303                     try
 304                     {
 305                         this.buf.RemoveRange(right, target.Length);
 306                         this.buf.InsertRange(right, pattern_chars, pattern.Length);
 307                     }
 308                     finally
 309                     {
 310                         this.UnLock();
 311
 312                     }
 313                     left = right + pattern.Length;
 314                     newLineLength += pattern.Length - target.Length;
 315                 }
 316
 317
 318                 this.Update(this, new DocumentUpdateEventArgs(UpdateType.Replace, lineHeadIndex, lineLength, newLineLength, i));
 319             }
 320         }
 321
 322         internal int IndexOf(string target, int start,bool ci = false)
 323         {
 324             this.Lock();
 325
 326             TextSearch ts = new TextSearch(target,ci);
 327             int patternIndex = ts.IndexOf(this.buf, start,this.buf.Count);
 328
 329             this.UnLock();
 330
 331             return patternIndex;
 332         }
 333
 334         /// <summary>
 335         /// 文字列を削除する
 336         /// </summary>
 337         internal void Clear()
 338         {
 339             this.buf.Clear();
 340             this.Update(this, new DocumentUpdateEventArgs(UpdateType.Clear, 0, this.buf.Count,0));
 341         }
 342
 343         internal IEnumerable<char> GetEnumerator(int start, int length)
 344         {
 345             for (int i = start; i < start + length; i++)
 346                 yield return this.buf[i];
 347         }
 348
 349         #region IEnumerable<char> メンバー
 350
 351         public IEnumerator<char> GetEnumerator()
 352         {
 353             for (int i = 0; i < this.Length; i++)
 354                 yield return this.buf[i];
 355         }
 356
 357         #endregion
 358
 359         #region IEnumerable メンバー
 360
 361         System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
 362         {
 363             for (int i = 0; i < this.Length; i++)
 364                 yield return this[i];
 365         }
 366
 367         #endregion
 368     }
 369
 370     sealed class TextSearch
 371     {
 372         char[] pattern;
 373         int patternLength;
 374         Dictionary<char, int> qsTable = new Dictionary<char, int>();
 375         bool caseInsenstive;
 376         public TextSearch(string pattern,bool ci = false)
 377         {
 378             this.patternLength = pattern.Length;
 379             this.caseInsenstive = ci;
 380             if (ci)
 381             {
 382                 this.CreateQSTable(pattern.ToLower());
 383                 this.CreateQSTable(pattern.ToUpper());
 384                 this.pattern = new char[pattern.Length];
 385                 for (int i = 0; i < pattern.Length; i++)
 386                     this.pattern[i] = CharTool.ToUpperFastIf(pattern[i]);
 387             }
 388             else
 389             {
 390                 this.CreateQSTable(pattern);
 391                 this.pattern = pattern.ToCharArray();
 392             }
 393         }
 394         void CreateQSTable(string pattern)
 395         {
 396             int len = pattern.Length;
 397             for (int i = 0; i < len; i++)
 398             {
 399                 if (!this.qsTable.ContainsKey(pattern[i]))
 400                     this.qsTable.Add(pattern[i], len - i);
 401                 else
 402                     this.qsTable[pattern[i]] = len - i;
 403             }
 404         }
 405         public int IndexOf(GapBuffer<char> buf, int start,int end)
 406         {
 407             //QuickSearch法
 408             int buflen = buf.Count - 1;
 409             int plen = this.patternLength;
 410             int i = start;
 411             int search_end = end - plen;
 412             //最適化のためわざとコピペした
 413             if (this.caseInsenstive)
 414             {
 415                 while (i <= search_end)
 416                 {
 417                     int j = 0;
 418                     while (j < plen)
 419                     {
 420                         if (CharTool.ToUpperFastIf(buf[i + j]) != this.pattern[j])
 421                             break;
 422                         j++;
 423                     }
 424                     if (j == plen)
 425                     {
 426                         return i;
 427                     }
 428                     else
 429                     {
 430                         int k = i + plen;
 431                         if (k <= buflen)        //buffer以降にアクセスする可能性がある
 432                         {
 433                             int moveDelta;
 434                             if (this.qsTable.TryGetValue(buf[k], out moveDelta))
 435                                 i += moveDelta;
 436                             else
 437                                 i += plen;
 438                         }
 439                         else
 440                         {
 441                             break;
 442                         }
 443                     }
 444                 }
 445
 446             }
 447             else
 448             {
 449                 while (i <= search_end)
 450                 {
 451                     int j = 0;
 452                     while (j < plen)
 453                     {
 454                         if (buf[i + j] != this.pattern[j])
 455                             break;
 456                         j++;
 457                     }
 458                     if (j == plen)
 459                     {
 460                         return i;
 461                     }
 462                     else
 463                     {
 464                         int k = i + plen;
 465                         if (k <= buflen)        //buffer以降にアクセスする可能性がある
 466                         {
 467                             int moveDelta;
 468                             if (this.qsTable.TryGetValue(buf[k], out moveDelta))
 469                                 i += moveDelta;
 470                             else
 471                                 i += plen;
 472                         }
 473                         else
 474                         {
 475                             break;
 476                         }
 477                     }
 478                 }
 479             }
 480             return -1;
 481         }
 482     }
 483     static class CharTool
 484     {
 485         /// <summary>
 486         /// Converts characters to lowercase.
 487         /// </summary>
 488         const string _lookupStringL =
 489         "---------------------------------!-#$%&-()*+,-./0123456789:;<=>?@abcdefghijklmnopqrstuvwxyz[-]^_`abcdefghijklmnopqrstuvwxyz{|}~-";
 490
 491         /// <summary>
 492         /// Converts characters to uppercase.
 493         /// </summary>
 494         const string _lookupStringU =
 495         "---------------------------------!-#$%&-()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[-]^_`ABCDEFGHIJKLMNOPQRSTUVWXYZ{|}~-";
 496
 497         /// <summary>
 498         /// Get lowercase version of this ASCII character.
 499         /// </summary>
 500         public static char ToLower(char c)
 501         {
 502             return _lookupStringL[c];
 503         }
 504
 505         /// <summary>
 506         /// Get uppercase version of this ASCII character.
 507         /// </summary>
 508         public static char ToUpper(char c)
 509         {
 510             return _lookupStringU[c];
 511         }
 512
 513         /// <summary>
 514         /// Translate uppercase ASCII characters to lowercase.
 515         /// </summary>
 516         public static char ToLowerFastIf(char c)
 517         {
 518             if (c >= 'A' && c <= 'Z')
 519             {
 520                 return (char)(c + 32);
 521             }
 522             else
 523             {
 524                 return c;
 525             }
 526         }
 527
 528         /// <summary>
 529         /// Translate lowercase ASCII characters to uppercase.
 530         /// </summary>
 531         public static char ToUpperFastIf(char c)
 532         {
 533             if (c >= 'a' && c <= 'z')
 534             {
 535                 return (char)(c - 32);
 536             }
 537             else
 538             {
 539                 return c;
 540             }
 541         }
 542     }
 543 }