mcs/tools/monkeydoc/Monkeydoc/Tree.cs

   1 using System;
   2 using System.IO;
   3 using System.Text;
   4 using System.Linq;
   5 using System.Xml;
   6 using System.Collections.Generic;
   7
   8 namespace MonkeyDoc
   9 {
  10         /// <summary>
  11         ///    This tree is populated by the documentation providers, or populated
  12         ///    from a binary encoding of the tree.  The format of the tree is designed
  13         ///    to minimize the need to load it in full.
  14         /// </summary>
  15
  16         /* Ideally this class should also be abstracted to let user have something
  17          * else than a file as a backing store, a database for instance
  18          */
  19         public class Tree
  20         {
  21                 public readonly HelpSource HelpSource;
  22
  23                 FileStream InputStream;
  24                 BinaryReader InputReader;
  25
  26                 // This is the node which contains all the other node of the tree
  27                 Node rootNode;
  28
  29                 /// <summary>
  30                 ///   Load from file constructor
  31                 /// </summary>
  32                 public Tree (HelpSource hs, string filename)
  33                 {
  34                         Encoding utf8 = new UTF8Encoding (false, true);
  35
  36                         if (!File.Exists (filename)){
  37                                 throw new FileNotFoundException ();
  38                         }
  39
  40                         InputStream = File.OpenRead (filename);
  41                         InputReader = new BinaryReader (InputStream, utf8);
  42                         byte [] sig = InputReader.ReadBytes (4);
  43
  44                         if (!GoodSig (sig))
  45                                 throw new Exception ("Invalid file format");
  46
  47                         InputStream.Position = 4;
  48                         var position = InputReader.ReadInt32 ();
  49                         rootNode = new Node (this, position);
  50                         InflateNode (rootNode);
  51
  52                         HelpSource = hs;
  53                 }
  54
  55                 /// <summary>
  56                 ///    Tree creation and merged tree constructor
  57                 /// </summary>
  58                 public Tree (HelpSource hs, string caption, string url) : this (hs, null, caption, url)
  59                 {
  60                 }
  61
  62                 public Tree (HelpSource hs, Node parent, string caption, string element)
  63                 {
  64                         HelpSource = hs;
  65                         rootNode = parent == null ? new Node (this, caption, element) : new Node (parent, caption, element);
  66                 }
  67
  68                 /// <summary>
  69                 ///    Saves the tree into the specified file using the help file format.
  70                 /// </summary>
  71                 public void Save (string file)
  72                 {
  73                         Encoding utf8 = new UTF8Encoding (false, true);
  74                         using (FileStream output = File.OpenWrite (file)){
  75                                 // Skip over the pointer to the first node.
  76                                 output.Position = 8;
  77
  78                                 using (BinaryWriter writer = new BinaryWriter (output, utf8)) {
  79                                         // Recursively dump
  80                                         rootNode.Serialize (output, writer);
  81
  82                                         output.Position = 0;
  83                                         writer.Write (new byte [] { (byte) 'M', (byte) 'o', (byte) 'H', (byte) 'P' });
  84                                         writer.Write (rootNode.Address);
  85                                 }
  86                         }
  87                 }
  88
  89                 public Node RootNode {
  90                         get {
  91                                 return rootNode;
  92                         }
  93                 }
  94
  95                 static bool GoodSig (byte [] sig)
  96                 {
  97                         if (sig.Length != 4)
  98                                 return false;
  99                         return sig [0] == (byte) 'M'
 100                                 && sig [1] == (byte) 'o'
 101                             && sig [2] == (byte) 'H'
 102                                 && sig [3] == (byte) 'P';
 103                 }
 104
 105                 public void InflateNode (Node baseNode)
 106                 {
 107                         var address = baseNode.Address;
 108                         if (address < 0)
 109                                 address = -address;
 110
 111                         InputStream.Position = address;
 112                         baseNode.Deserialize (InputReader);
 113                 }
 114         }
 115
 116         public class Node : IComparable<Node>, IComparable
 117         {
 118                 readonly Tree tree;
 119                 string caption, element;
 120                 public bool Documented;
 121                 bool loaded;
 122                 Node parent;
 123                 List<Node> nodes;
 124                 Dictionary<string, Node> childrenLookup;
 125                 /* Address has three types of value,
 126                  *   _ 0 is for no on-disk representation
 127                  *   _ >0 is a valid address that is loaded immediately
 128                  *   _ <0 is a valid negated address to indicate lazy loading
 129                  */
 130                 int address;
 131
 132                 public Node (Node parent, string caption, string element) : this (parent.Tree, caption, element)
 133                 {
 134                         this.parent = parent;
 135                 }
 136
 137                 internal Node (Tree tree, string caption, string element)
 138                 {
 139                         this.tree = tree;
 140                         this.caption = caption;
 141                         this.element = element;
 142                 }
 143
 144                 /// <summary>
 145                 ///    Creates a node from an on-disk representation
 146                 /// </summary>
 147                 internal Node (Node parent, int address) : this (parent.tree, address)
 148                 {
 149                         this.parent = parent;
 150                 }
 151
 152                 internal Node (Tree tree, int address)
 153                 {
 154                         this.address = address;
 155                         this.tree = tree;
 156                         if (address > 0)
 157                                 LoadNode ();
 158                 }
 159
 160                 /* This is solely used for MatchNode to check for equality */
 161                 internal Node ()
 162                 {
 163                 }
 164
 165                 void LoadNode ()
 166                 {
 167                         tree.InflateNode (this);
 168                         if (parent != null)
 169                                 parent.RegisterFullNode (this);
 170                 }
 171
 172                 public void AddNode (Node n)
 173                 {
 174                         nodes.Add (n);
 175                         n.parent = this;
 176                         n.Documented = true;
 177                         RegisterFullNode (n);
 178                 }
 179
 180                 public void DeleteNode (Node n)
 181                 {
 182                         nodes.Remove (n);
 183                         if (!string.IsNullOrEmpty (n.element))
 184                                 childrenLookup.Remove (n.element);
 185                 }
 186
 187                 // When a child node is inflated, it calls this method
 188                 // so that we can add it to our lookup for quick search
 189                 void RegisterFullNode (Node child)
 190                 {
 191                         if (childrenLookup == null)
 192                                 childrenLookup = new Dictionary<string, Node> ();
 193                         if (!string.IsNullOrEmpty (child.element))
 194                                 childrenLookup[child.element] = child;
 195                 }
 196
 197                 public List<Node> Nodes {
 198                         get {
 199                                 EnsureLoaded ();
 200                                 return nodes != null ? nodes : new List<Node> ();
 201                         }
 202                 }
 203
 204                 public string Element {
 205                         get {
 206                                 EnsureLoaded ();
 207                                 return element;
 208                         }
 209                         set {
 210                                 element = value;
 211                         }
 212                 }
 213
 214                 public string Caption {
 215                         get {
 216                                 EnsureLoaded ();
 217                                 return caption;
 218                         }
 219                         internal set {
 220                                 caption = value;
 221                         }
 222                 }
 223
 224                 public Node Parent {
 225                         get {
 226                                 return parent;
 227                         }
 228                 }
 229
 230                 public Tree Tree {
 231                         get {
 232                                 return tree;
 233                         }
 234                 }
 235
 236                 internal int Address {
 237                         get {
 238                                 return address;
 239                         }
 240                 }
 241
 242                 /// <summary>
 243                 ///   Creates a new node, in the locator entry point, and with
 244                 ///   a user visible caption of @caption
 245                 /// </summary>
 246                 public Node CreateNode (string c_caption, string c_element)
 247                 {
 248                         EnsureNodes ();
 249
 250                         Node t = new Node (this, c_caption, c_element);
 251                         nodes.Add (t);
 252                         childrenLookup[c_element] = t;
 253
 254                         return t;
 255                 }
 256
 257                 public Node GetOrCreateNode (string c_caption, string c_element)
 258                 {
 259                         if (nodes == null)
 260                                 return CreateNode (c_caption, c_element);
 261                         if (childrenLookup.Count != nodes.Count || (nodes.Count == 0 && childrenLookup.Count != nodes.Capacity))
 262                                 UpdateLookup ();
 263
 264                         Node result;
 265                         if (!childrenLookup.TryGetValue (c_element, out result))
 266                                 result = CreateNode (c_caption, c_element);
 267                         return result;
 268                 }
 269
 270                 public void EnsureNodes ()
 271                 {
 272                         if (nodes == null) {
 273                                 nodes = new List<Node> ();
 274                                 childrenLookup = new Dictionary<string, Node> ();
 275                         }
 276                 }
 277
 278                 public void EnsureLoaded ()
 279                 {
 280                         if (address < 0 && !loaded) {
 281                                 LoadNode ();
 282                                 loaded = true;
 283                         }
 284                 }
 285
 286                 void UpdateLookup ()
 287                 {
 288                         foreach (var node in nodes)
 289                                 childrenLookup[node.Element] = node;
 290                 }
 291
 292                 public bool IsLeaf {
 293                         get {
 294                                 return nodes == null || nodes.Count == 0;
 295                         }
 296                 }
 297
 298                 void EncodeInt (BinaryWriter writer, int value)
 299                 {
 300                         do {
 301                                 int high = (value >> 7) & 0x01ffffff;
 302                                 byte b = (byte)(value & 0x7f);
 303
 304                                 if (high != 0) {
 305                                         b = (byte)(b | 0x80);
 306                                 }
 307
 308                                 writer.Write(b);
 309                                 value = high;
 310                         } while(value != 0);
 311                 }
 312
 313                 int DecodeInt (BinaryReader reader)
 314                 {
 315                         int ret = 0;
 316                         int shift = 0;
 317                         byte b;
 318
 319                         do {
 320                                 b = reader.ReadByte();
 321
 322                                 ret = ret | ((b & 0x7f) << shift);
 323                                 shift += 7;
 324                         } while ((b & 0x80) == 0x80);
 325
 326                         return ret;
 327                 }
 328
 329                 internal void Deserialize (BinaryReader reader)
 330                 {
 331                         int count = DecodeInt (reader);
 332                         element = reader.ReadString ();
 333                         caption = reader.ReadString ();
 334
 335                         if (count == 0)
 336                                 return;
 337
 338                         nodes = new List<Node> (count);
 339                         for (int i = 0; i < count; i++) {
 340                                 int child_address = DecodeInt (reader);
 341
 342                                 Node t = new Node (this, -child_address);
 343                                 nodes.Add (t);
 344                         }
 345                 }
 346
 347                 internal void Serialize (FileStream output, BinaryWriter writer)
 348                 {
 349                         if (nodes != null)
 350                                 foreach (Node child in nodes)
 351                                         child.Serialize (output, writer);
 352
 353                         address = (int) output.Position;
 354                         EncodeInt (writer, nodes == null ? 0 : (int) nodes.Count);
 355                         writer.Write (element);
 356                         writer.Write (caption);
 357
 358                         if (nodes != null)
 359                                 foreach (Node child in nodes)
 360                                         EncodeInt (writer, child.address);
 361                 }
 362
 363                 public void Sort ()
 364                 {
 365                         if (nodes != null)
 366                                 nodes.Sort ();
 367                 }
 368
 369                 internal string GetInternalUrl ()
 370                 {
 371                         EnsureLoaded ();
 372                         if (element.IndexOf (":") != -1 || parent == null)
 373                                 return element;
 374
 375                         var parentUrl = parent.GetInternalUrl ();
 376                         return parentUrl.EndsWith ("/") ? parentUrl + element : parentUrl + "/" + element;
 377                 }
 378
 379                 public string PublicUrl {
 380                         get {
 381                                 var url = GetInternalUrl ();
 382                                 return tree.HelpSource != null ? tree.HelpSource.GetPublicUrl (this) : url;
 383                         }
 384                 }
 385
 386                 int IComparable.CompareTo (object obj)
 387                 {
 388                         Node other = obj as Node;
 389                         if (other == null)
 390                                 return -1;
 391                         return CompareToInternal (other);
 392                 }
 393
 394                 int IComparable<Node>.CompareTo (Node obj)
 395                 {
 396                         return CompareToInternal (obj);
 397                 }
 398
 399                 int CompareToInternal (Node other)
 400                 {
 401                         EnsureLoaded ();
 402                         other.EnsureLoaded ();
 403
 404                         var cap1 = caption;
 405                         var cap2 = other.caption;
 406
 407                         /* Some node (notably from ecmaspec) have number prepended to them
 408                          * which we need to sort better by padding them to the same number
 409                          * of digits
 410                          */
 411                         if (char.IsDigit (cap1[0]) && char.IsDigit (cap2[0])) {
 412                                 int c1 = cap1.TakeWhile (char.IsDigit).Count ();
 413                                 int c2 = cap2.TakeWhile (char.IsDigit).Count ();
 414
 415                                 if (c1 != c2) {
 416                                         cap1 = cap1.PadLeft (cap1.Length + Math.Max (0, c2 - c1), '0');
 417                                         cap2 = cap2.PadLeft (cap2.Length + Math.Max (0, c1 - c2), '0');
 418                                 }
 419                         }
 420
 421                         return string.Compare (cap1, cap2, StringComparison.OrdinalIgnoreCase);
 422                 }
 423         }
 424
 425         public static class TreeDumper
 426         {
 427                 static int indent;
 428
 429                 static void Indent ()
 430                 {
 431                         for (int i = 0; i < indent; i++)
 432                                 Console.Write ("   ");
 433                 }
 434
 435                 public static void PrintTree (Node node)
 436                 {
 437                         Indent ();
 438                         Console.WriteLine ("{0},{1}\t[PublicUrl: {2}]", node.Element, node.Caption, node.PublicUrl);
 439                         if (node.Nodes.Count == 0)
 440                                 return;
 441
 442                         indent++;
 443                         foreach (Node n in node.Nodes)
 444                                 PrintTree (n);
 445                         indent--;
 446                 }
 447
 448                 public static string ExportToTocXml (Node root, string title, string desc)
 449                 {
 450                         if (root == null)
 451                                 throw new ArgumentNullException ("root");
 452                         // Return a toc index of sub-nodes
 453                         StringBuilder buf = new StringBuilder ();
 454                         var writer = XmlWriter.Create (buf);
 455                         writer.WriteStartElement ("toc");
 456                         writer.WriteAttributeString ("title", title ?? string.Empty);
 457                         writer.WriteElementString ("description", desc ?? string.Empty);
 458                         writer.WriteStartElement ("list");
 459                         foreach (Node n in root.Nodes) {
 460                                 writer.WriteStartElement ("item");
 461                                 writer.WriteAttributeString ("url", n.Element);
 462                                 writer.WriteValue (n.Caption);
 463                                 writer.WriteEndElement ();
 464                         }
 465                         writer.WriteEndElement ();
 466                         writer.WriteEndElement ();
 467                         writer.Flush ();
 468                         writer.Close ();
 469
 470                         return buf.ToString ();
 471                 }
 472         }
 473 }