context: // ***************************************************************
  // <copyright file="FormatStore.cs" company="Microsoft">
  //      Copyright (C) Microsoft Corporation.  All rights reserved.
  // </copyright>
  // <summary>
  //      ...
  // </summary>
  // ***************************************************************
  
  namespace Microsoft.Exchange.Data.TextConverters.Internal.Format
  {
      using System;
      using System.IO;
      using System.Text;
      using System.Runtime.InteropServices;
      using System.Collections;
      using System.Collections.Generic;
      using Data.Internal;
      using Globalization;
      using Strings = CtsResources.TextConvertersStrings;
  
      
  
      internal enum FormatContainerType : byte
      {
          Null                    = 0x00,                 
  
          Root                    = 0x01 | BlockFlag,     
  
          Document                = 0x02 | BlockFlag,     
          Fragment                = 0x03 | BlockFlag,     
  
          Block                   = 0x04 | BlockFlag,     
          BlockQuote              = 0x05 | BlockFlag,     
  
          HorizontalLine          = 0x06 | BlockFlag,     
  
          TableContainer          = 0x07,                 
          TableDefinition         = 0x08,                 
          TableColumnGroup        = 0x09,                 
          TableColumn             = 0x0A,                 
          TableCaption            = 0x0B | BlockFlag,     
          TableExtraContent       = 0x0C | BlockFlag,     
          Table                   = 0x0D | BlockFlag,     
          TableRow                = 0x0E | BlockFlag,     
          TableCell               = 0x0F | BlockFlag,     
  
          List                    = 0x10 | BlockFlag,     
          ListItem                = 0x11 | BlockFlag,     
          
                                                          
                                                          
  
          Inline                  = 0x12,                 
  
          HyperLink               = 0x13,                 
                                                          
  
          Bookmark                = 0x14,                 
  
          Image                   = 0x15 | InlineObjectFlag,  
  
          Area                    = 0x16,
          Map                     = 0x17 | BlockFlag,
  
          BaseFont                = 0x18,
  
          Form                    = 0x19,
          FieldSet                = 0x1A,
          Label                   = 0x1B,
          Input                   = 0x1C,
          Button                  = 0x1D,
          Legend                  = 0x1E,
          TextArea                = 0x1F,
          Select                  = 0x20,
          OptionGroup             = 0x21,
          Option                  = 0x22,
  
          Text                    = 0x24,                 
                                                          
  
          PropertyContainer       = 0x25,                 
                                                          
                                                          
  
          InlineObjectFlag        = 0x40,                 
          BlockFlag               = 0x80,                 
      }
  
      
  
      internal class FormatStore
      {
          
          internal NodeStore nodes;   
  
          
          internal StyleStore styles;
  
          
          internal StringValueStore strings;   
  
          
          internal MultiValueStore multiValues;
  
          internal TextStore text;
  
          public FormatStore()
          {
              nodes = new NodeStore(this);
  
              styles = new StyleStore(this, FormatStoreData.GlobalStyles);
  
              strings = new StringValueStore(FormatStoreData.GlobalStringValues);
  
              multiValues = new MultiValueStore(this, FormatStoreData.GlobalMultiValues);
  
              text = new TextStore();
  
              Initialize();
          }
  
          public void Initialize()
          {
              nodes.Initialize();
  
              styles.Initialize(FormatStoreData.GlobalStyles);
  
              strings.Initialize(FormatStoreData.GlobalStringValues);
  
              multiValues.Initialize(FormatStoreData.GlobalMultiValues);
  
              text.Initialize();
          }
  
          public FormatNode RootNode => new FormatNode(this, 1);
  
          public uint CurrentTextPosition => text.CurrentPosition;
  
          public void ReleaseValue(PropertyValue value)
          {
              InternalDebug.Assert(value.IsRefCountedHandle);
              if (value.IsString)
              {
                  GetStringValue(value).Release();
              }
              else if (value.IsMultiValue)
              {
                  GetMultiValue(value).Release();
              }
          }
  
          public void AddRefValue(PropertyValue value)
          {
              InternalDebug.Assert(value.IsRefCountedHandle);
              if (value.IsString)
              {
                  GetStringValue(value).AddRef();
              }
              else if (value.IsMultiValue)
              {
                  GetMultiValue(value).AddRef();
              }
          }
  
          public FormatNode GetNode(int nodeHandle)
          {
              return new FormatNode(this, nodeHandle);
          }
  
          public FormatNode AllocateNode(FormatContainerType type)
          {
              return new FormatNode(nodes, nodes.Allocate(type, CurrentTextPosition));
          }
  
          public FormatNode AllocateNode(FormatContainerType type, uint beginTextPosition)
          {
              return new FormatNode(nodes, nodes.Allocate(type, beginTextPosition));
          }
  
          public void FreeNode(FormatNode node)
          {
              nodes.Free(node.Handle);
          }
  
          public FormatStyle AllocateStyle(bool isStatic)
          {
              return new FormatStyle(this, styles.Allocate(isStatic));
          }
  
          public FormatStyle GetStyle(int styleHandle)
          {
              return new FormatStyle(this, styleHandle);
          }
  
          public void FreeStyle(FormatStyle style)
          {
              InternalDebug.Assert(style.RefCount == 0);
              styles.Free(style.Handle);
          }
  
          public StringValue AllocateStringValue(bool isStatic)
          {
              return new StringValue(this, strings.Allocate(isStatic));
          }
  
          public StringValue AllocateStringValue(bool isStatic, string value)
          {
              var sv = AllocateStringValue(isStatic);
              sv.SetString(value);
              return sv;
          }
  
          public StringValue GetStringValue(PropertyValue propertyValue)
          {
              return new StringValue(this, propertyValue.StringHandle);
          }
  
          public void FreeStringValue(StringValue str)
          {
              InternalDebug.Assert(str.RefCount == 0);
              strings.Free(str.Handle);
          }
  
          public MultiValue AllocateMultiValue(bool isStatic)
          {
              return new MultiValue(this, multiValues.Allocate(isStatic));
          }
  
          public MultiValue GetMultiValue(PropertyValue propertyValue)
          {
              return new MultiValue(this, propertyValue.MultiValueHandle);
          }
  
          public void FreeMultiValue(MultiValue multi)
          {
              InternalDebug.Assert(multi.RefCount == 0);
              multiValues.Free(multi.Handle);
          }
  
          
  
          public void InitializeCodepageDetector()
          {
              text.InitializeCodepageDetector();
          }
  
          public int GetBestWindowsCodePage()
          {
              return text.GetBestWindowsCodePage();
          }
  
          public int GetBestWindowsCodePage(int preferredCodePage)
          {
              return text.GetBestWindowsCodePage(preferredCodePage);
          }
  
          
  
          public void SetTextBoundary()
          {
              
              text.DoNotMergeNextRun();
          }
  
          
  
          public void AddBlockBoundary()
          {
              if (text.LastRunType != TextRunType.BlockBoundary)
              {
                  text.AddSimpleRun(TextRunType.BlockBoundary, 1);
              }
          }
  
          
  
          public void AddText(char[] textBuffer, int offset, int count)
          {
              text.AddText(TextRunType.NonSpace, textBuffer, offset, count);
          }
  
          public void AddInlineObject()
          {
              text.AddSimpleRun(TextRunType.InlineObject, 1);
              text.DoNotMergeNextRun(); 
          }
  
          public void AddSpace(int count)
          {
              text.AddSimpleRun(TextRunType.Space, count);
          }
  
          public void AddLineBreak(int count)
          {
              text.AddSimpleRun(TextRunType.NewLine, count);
          }
  
          public void AddNbsp(int count)
          {
              text.AddSimpleRun(TextRunType.NbSp, count);
          }
  
          public void AddTabulation(int count)
          {
              text.AddSimpleRun(TextRunType.Tabulation, count);
          }
  
          internal TextRun GetTextRun(uint position)
          {
              InternalDebug.Assert(position <= CurrentTextPosition);
  
              if (position < CurrentTextPosition)
              {
                  return GetTextRunReally(position);
              }
  
              return TextRun.Invalid;
          }
  
          internal TextRun GetTextRunReally(uint position)
          {
              return new TextRun(text, position);
          }
  
          
  #if DEBUG
          internal void Dump(Stream stream, bool close)
          {
              var dumpWriter = new StreamWriter(stream);
              uint runningPosition = 0;
  
              DumpNode(dumpWriter, RootNode, 0, false, ref runningPosition);
  
              CalculateAndDumpStatistics(dumpWriter);
  
              if (close)
              {
                  dumpWriter.Close();
              }
              else
              {
                  dumpWriter.Flush();
              }
          }
  
          private static void DumpIndent(TextWriter dumpWriter, int level)
          {
              if (level < 20)
              {
                  for (var i = 0; i < level; i++)
                  {
                      dumpWriter.Write("   ");
                  }
              }
              else
              {
                  for (var i = 0; i < level; i++)
                  {
                      dumpWriter.Write("   ");
                  }
                  dumpWriter.Write("{0}: ", level);
              }
          }
  
          private void DumpNode(TextWriter dumpWriter, FormatNode node, int level, bool outOfOrder, ref uint runningPosition)
          {
              DumpIndent(dumpWriter, level);
  
              dumpWriter.WriteLine("{0} /{1:X}/ tp:/{2:X}/{3:X}/{4}", node.NodeType.ToString(), node.Handle, node.BeginTextPosition, node.EndTextPosition, node.IsInOrder ? "" : "  out-of-order!");
  
              var enumerator = new NodePropertiesEnumerator(node);
              foreach (var prop in enumerator)
              {
                  DumpIndent(dumpWriter, level + 1);
  
                  dumpWriter.WriteLine("| PROP " + prop.ToString());
  
                  if (prop.Value.IsString)
                  {
                      DumpIndent(dumpWriter, level + 1);
  
                      var sv = GetStringValue(prop.Value);
                      dumpWriter.WriteLine("|   = \"" + sv.GetString() + "\"");
                  }
                  else if (prop.Value.IsMultiValue)
                  {
                      var mv = GetMultiValue(prop.Value);
  
                      for (var k = 0; k < mv.Length; k++)
                      {
                          DumpIndent(dumpWriter, level + 1);
  
                          dumpWriter.WriteLine("|   = " + mv[k].ToString());
  
                          if (mv[k].IsString)
                          {
                              DumpIndent(dumpWriter, level + 1);
  
                              var sv = GetStringValue(mv[k]);
                              dumpWriter.WriteLine("|      = \"" + sv.GetString() + "\"");
                          }
                      }
                  }
              }
  #if false
              if (!outOfOrder && !node.IsText && node.IsInOrder)
              {
                  this.DumpStartMarkup(dumpWriter, node, level, ref runningPosition);
              }
  #endif
              if (node.IsText)
              {
                  
                  DumpTextRuns(node.BeginTextPosition, node.EndTextPosition, dumpWriter, level);
                  if (!outOfOrder)
                  {
                      runningPosition = node.EndTextPosition;
                  }
              }
              else
              {
                  var child = node.FirstChild;
                  while (!child.IsNull)
                  {
                      DumpNode(dumpWriter, child, level + 1, outOfOrder || !node.IsInOrder, ref runningPosition);
                      child = child.NextSibling;
                  }
              }
  #if false
              if (!outOfOrder && node.IsInOrder && !node.Parent.IsNull)
              {
                  this.DumpEndMarkup(dumpWriter, node, level, ref runningPosition);
              }
  #endif
          }
  #if false
          private void DumpStartMarkup(TextWriter dumpWriter, FormatNode node, int level, ref uint runningPosition)
          {
              uint start = node.BeginTextPosition;
              uint end = start;
  
              FormatNode firstChild = node.FirstChild;
              while (!firstChild.IsNull && !firstChild.IsInOrder)
              {
                  firstChild = firstChild.NextSibling;
              }
  
              if (!firstChild.IsNull)
              {
                  end = firstChild.BeginTextPosition;
              }
              else
              {
                  end = node.EndTextPosition;
              }
  
              InternalDebug.Assert(start == runningPosition);
  
              if (start != end)
              {
                  InternalDebug.Assert(start < end);
                  this.DumpTextRuns(start, end, dumpWriter, level);
                  runningPosition = end;
              }
          }
  
          private void DumpEndMarkup(TextWriter dumpWriter, FormatNode node, int level, ref uint runningPosition)
          {
              uint start = node.EndTextPosition;
              uint end = start;
  
              FormatNode nextSibling = node.NextSibling;
              while (!nextSibling.IsNull && !nextSibling.IsInOrder)
              {
                  nextSibling = nextSibling.NextSibling;
              }
  
              if (!nextSibling.IsNull)
              {
                  end = nextSibling.BeginTextPosition;
              }
              else
              {
                  end = node.Parent.EndTextPosition;
              }
  
              InternalDebug.Assert(start <= runningPosition);
  
              if (start < end)
              {
                  if (end >= runningPosition)
                  {
                      if (start < runningPosition)
                      {
                          DumpIndent(dumpWriter, level + 1);
                          dumpWriter.WriteLine("| OVERLAPPED JUMP FORWARD FROM {0:X} TO {1:X}", start, runningPosition);
                          dumpWriter.Flush();
  
                          start = runningPosition;
                          InternalDebug.Assert(start <= end);
                      }
  
                      if (start != end)
                      {
                          this.DumpTextRuns(start, end, dumpWriter, level);
                          runningPosition = end;
                      }
                  }
              }
              else if (start != end)
              {
                  DumpIndent(dumpWriter, level + 1);
                  dumpWriter.WriteLine("| OVERLAPPED STEP BACK FROM {0:X} TO {1:X}", start, end);
              }
          }
  #endif
          private void DumpTextRuns(uint start, uint end, TextWriter dumpWriter, int level)
          {
              char[] buffer;
              int offset;
              int count;
  
              DumpIndent(dumpWriter, level + 1);
              dumpWriter.Write("| ");
  
              var saveStart = start;
              var newLine = false;
  
              if (start != end)
              {
                  var run = GetTextRun(start);
  
                  do
                  {
                      if (run.Position != saveStart && !newLine)
                      {
                          dumpWriter.Write(", ");
                      }
                      else if (newLine)
                      {
                          dumpWriter.WriteLine();
                          DumpIndent(dumpWriter, level + 1);
                          dumpWriter.Write("|           ");
                          newLine = false;
                      }
  
                      switch (run.Type)
                      {
                          case TextRunType.NewLine:
  
                              dumpWriter.Write("nl({0})", run.EffectiveLength);
                              newLine = true;
                              break;
  
                          case TextRunType.Tabulation:
  
                              dumpWriter.Write("tab({0})", run.EffectiveLength);
                              break;
  
                          case TextRunType.Space:
  
                              dumpWriter.Write("sp({0})", run.EffectiveLength);
                              break;
  
                          case TextRunType.NbSp:
  
                              dumpWriter.Write("nbsp({0})", run.EffectiveLength);
                              break;
                                  
                          case TextRunType.NonSpace:
  
                              var pos = 0;
  
                              dumpWriter.Write("\"");
  
                              while (pos != run.EffectiveLength)
                              {
                                  run.GetChunk(pos, out buffer, out offset, out count);
                                  dumpWriter.Write(buffer, offset, count);
                                  pos += count;
                              }
  
                              dumpWriter.Write("\"");
                              break;
                      }
  
                      run.MoveNext();
                  }
                  while (run.Position < end);
              }
  
              dumpWriter.WriteLine();
          }
  
  #if PRIVATEBUILD
          internal long bytesTotal;
  #endif
          public long CalculateAndDumpStatistics(TextWriter dumpWriter)
          {
  #if !PRIVATEBUILD
              long bytesTotal;
  #endif
              bytesTotal = 0;
  
              bytesTotal += text.DumpStat(dumpWriter);
  
              if (dumpWriter != null)
              {
                  dumpWriter.WriteLine();
              }
  
              bytesTotal += nodes.DumpStat(dumpWriter);
  
              if (dumpWriter != null)
              {
                  dumpWriter.WriteLine();
              }
  
              bytesTotal += styles.DumpStat(dumpWriter);
  
              if (dumpWriter != null)
              {
                  dumpWriter.WriteLine();
              }
  
              bytesTotal += strings.DumpStat(dumpWriter);
  
              if (dumpWriter != null)
              {
                  dumpWriter.WriteLine();
              }
  
              bytesTotal += multiValues.DumpStat(dumpWriter);
  
              if (dumpWriter != null)
              {
                  dumpWriter.WriteLine();
                  dumpWriter.WriteLine("Total bytes for store: {0}", bytesTotal);
              }
  
              return bytesTotal;
          }
  #endif
          
  
          [Flags]
          internal enum NodeFlags : byte
          {
              OnRightEdge = 0x01,         
              OnLeftEdge = 0x02,          
              CanFlush = 0x04,            
              OutOfOrder = 0x08,          
              Visited = 0x10,             
                                          
          }
  
          [StructLayout(LayoutKind.Sequential, Pack=4)]
          internal struct NodeEntry
          {
              
              
  
              internal FormatContainerType type;
              internal NodeFlags nodeFlags;
              internal TextMapping textMapping;
  
              internal int parent;
              internal int lastChild;              
              internal int nextSibling;            
  
              internal uint beginTextPosition;
              internal uint endTextPosition;
  
              internal int inheritanceMaskIndex;
              internal FlagProperties flagProperties;          
              internal PropertyBitMask propertyMask;           
              internal Property[] properties;                  
  
              
              internal int NextFree
              {
                  get { return nextSibling; }
                  set { nextSibling = value; }
              }
  
              public void Clean()
              {
                  this = new NodeEntry();
              }
  
              public override string ToString()
              {
                  return type.ToString() + " (" + parent.ToString("X") + ", " + lastChild.ToString("X") + ", " + nextSibling.ToString("X") + ") " + beginTextPosition.ToString("X") + " - " + endTextPosition.ToString("X");
              }
          }
  
          
  
          internal struct StyleEntry
          {
              internal int refCount;
              internal FlagProperties flagProperties;          
              internal PropertyBitMask propertyMask;           
              internal Property[] propertyList;                
  
              public StyleEntry(FlagProperties flagProperties, PropertyBitMask propertyMask, Property[] propertyList)
              {
                  refCount = Int32.MaxValue;     
                  this.flagProperties = flagProperties;
                  this.propertyMask = propertyMask;
                  this.propertyList = propertyList;
              }
  
              
              internal int NextFree
              {
                  get { return flagProperties.IntegerBag; }
                  set { flagProperties.IntegerBag = value; }
              }
  
              public void Clean()
              {
                  this = new StyleEntry();
              }
          }
  
          
  
          internal struct MultiValueEntry
          {
              internal int refCount;
              internal int nextFree;                           
              internal PropertyValue[] values;                
  
              public MultiValueEntry(PropertyValue[] values)
              {
                  refCount = Int32.MaxValue;     
                  this.values = values;
                  nextFree = 0;
              }
  
              
              
              internal int NextFree
              {
                  get { return nextFree; }
                  set { nextFree = value; }
              }
  
              public void Clean()
              {
                  this = new MultiValueEntry();
              }
          }
  
          
  
          internal struct StringValueEntry
          {
              internal int refCount;
              internal int nextFree;                           
              internal string str;                            
  
              public StringValueEntry(string str)
              {
                  refCount = Int32.MaxValue;     
                  this.str = str;
                  nextFree = 0;
              }
       
              
              
              internal int NextFree
              {
                  get { return nextFree; }
                  set { nextFree = value; }
              }
  
              public void Clean()
              {
                  this = new StringValueEntry();
              }
          }
  
          internal struct InheritaceMask
          {
              internal FlagProperties flagProperties;          
              internal PropertyBitMask propertyMask;           
  
              public InheritaceMask(FlagProperties flagProperties, PropertyBitMask propertyMask)
              {
                  this.flagProperties = flagProperties;
                  this.propertyMask = propertyMask;
              }
          }
  
          
  
          internal class NodeStore
          {
              
              
              
              internal const int MaxElementsPerPlane = 1024;
  
              
              
              
              internal const int MaxPlanes = (1024 * 1024) / MaxElementsPerPlane;
  
              
              internal const int InitialPlanes = 32;
  
              
              internal const int InitialElements = 16;
  
              private FormatStore store;
              private NodeEntry[][] planes;
              private int freeListHead;
              private int top;
  
  #if PRIVATEBUILD
              internal long countAllocated;
              internal long countUsed;
              internal long countPropLists;
              internal long totalPropListsLength;
              internal long averagePropListLength;
              internal long maxPropListLength;
              internal long bytesTotal;
  #endif
              public NodeStore(FormatStore store)
              {
                  InternalDebug.Assert(InitialElements < MaxElementsPerPlane);
                  InternalDebug.Assert(Marshal.SizeOf(typeof(NodeEntry)) * MaxElementsPerPlane < 85000, "exceeding LOH threshold!");
  
                  this.store = store;
                  planes = new NodeEntry[InitialPlanes][];       
                  planes[0] = new NodeEntry[InitialElements];
                  freeListHead = 0;
                  top = 0;
              }
  
              public NodeEntry[] Plane(int handle) { return planes[handle / MaxElementsPerPlane]; }
              public int Index(int handle) { return handle % MaxElementsPerPlane; }
  
              public void Initialize()
              {
                  
  
                  freeListHead = -1;
  
                  top = 1;          
  
                  
                  planes[0][1].type = FormatContainerType.Root;
                  planes[0][1].nodeFlags = NodeFlags.OnRightEdge | NodeFlags.CanFlush;
                  planes[0][1].textMapping = TextMapping.Unicode;
                  planes[0][1].parent = 0;
                  planes[0][1].nextSibling = 1;
                  planes[0][1].lastChild = 0;
                  planes[0][1].beginTextPosition = 0;
                  planes[0][1].endTextPosition = uint.MaxValue;
                  planes[0][1].flagProperties = new FlagProperties();
                  planes[0][1].propertyMask = new PropertyBitMask();
                  planes[0][1].properties = null;
  
                  top ++;
              }
  
              public int Allocate(FormatContainerType type, uint currentTextPosition)
              {
                  InternalDebug.Assert(planes != null);
  
                  NodeEntry[] plane;
                  int index;
  
                  var handle = freeListHead;
  
                  if (handle != -1)
                  {
                      
  
                      index = handle % MaxElementsPerPlane;
                      plane = planes[handle / MaxElementsPerPlane];
  
                      freeListHead = plane[index].NextFree;
                  }
                  else
                  {
                      InternalDebug.Assert(top <= planes.Length * MaxElementsPerPlane);
  
                      handle = top++;
  
                      index = handle % MaxElementsPerPlane;
                      var planeIndex = handle / MaxElementsPerPlane;
  
                      if (index == 0)
                      {
                          
  
                          
  
                          if (planeIndex == MaxPlanes)
                          {
                              
                              throw new TextConvertersException(Strings.InputDocumentTooComplex);
                          }
  
                          if (planeIndex == planes.Length)
                          {
                              
  
                              var newLength = Math.Min(planes.Length * 2, MaxPlanes);
                              var newPlanes = new NodeEntry[newLength][];
                              Array.Copy(planes, 0, newPlanes, 0, planes.Length);
                              planes = newPlanes;
                          }
  
                          if (planes[planeIndex] == null)
                          {
                              
  
                              planes[planeIndex] = new NodeEntry[MaxElementsPerPlane];
                          }
                      }
  
gt:                     else if (planeIndex == 0 && index == planes[planeIndex].Length)