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