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