includes/api/ApiFormatYaml_spyc.php

   1 <?php
   2   /**
   3    * Spyc -- A Simple PHP YAML Class
   4    * @version 0.2.3 -- 2006-02-04
   5    * @author Chris Wanstrath <chris@ozmm.org>
   6    * @link http://spyc.sourceforge.net/
   7    * @copyright Copyright 2005-2006 Chris Wanstrath
   8    * @license http://www.opensource.org/licenses/mit-license.php MIT License
   9    * @addtogroup Spyc
  10    */
  11
  12   /**
  13    * A node, used by Spyc for parsing YAML.
  14    * @addtogroup Spyc
  15    */
  16   class YAMLNode {
  17     /**#@+
  18      * @access public
  19      * @var string
  20      */
  21     var $parent;
  22     var $id;
  23     /**#@+*/
  24     /**
  25      * @access public
  26      * @var mixed
  27      */
  28     var $data;
  29     /**
  30      * @access public
  31      * @var int
  32      */
  33     var $indent;
  34     /**
  35      * @access public
  36      * @var bool
  37      */
  38     var $children = false;
  39
  40     /**
  41      * The constructor assigns the node a unique ID.
  42      * @access public
  43      * @return void
  44      */
  45     function YAMLNode() {
  46       $this->id = uniqid('');
  47     }
  48   }
  49
  50   /**
  51    * The Simple PHP YAML Class.
  52    *
  53    * This class can be used to read a YAML file and convert its contents
  54    * into a PHP array.  It currently supports a very limited subsection of
  55    * the YAML spec.
  56    *
  57    * Usage:
  58    * <code>
  59    *   $parser = new Spyc;
  60    *   $array  = $parser->load($file);
  61    * </code>
  62    * @addtogroup Spyc
  63    */
  64   class Spyc {
  65
  66     /**
  67      * Load YAML into a PHP array statically
  68      *
  69      * The load method, when supplied with a YAML stream (string or file),
  70      * will do its best to convert YAML in a file into a PHP array.  Pretty
  71      * simple.
  72      *  Usage:
  73      *  <code>
  74      *   $array = Spyc::YAMLLoad('lucky.yml');
  75      *   print_r($array);
  76      *  </code>
  77      * @access public
  78      * @return array
  79      * @param string $input Path of YAML file or string containing YAML
  80      */
  81     function YAMLLoad($input) {
  82       $spyc = new Spyc;
  83       return $spyc->load($input);
  84     }
  85
  86     /**
  87      * Dump YAML from PHP array statically
  88      *
  89      * The dump method, when supplied with an array, will do its best
  90      * to convert the array into friendly YAML.  Pretty simple.  Feel free to
  91      * save the returned string as nothing.yml and pass it around.
  92      *
  93      * Oh, and you can decide how big the indent is and what the wordwrap
  94      * for folding is.  Pretty cool -- just pass in 'false' for either if
  95      * you want to use the default.
  96      *
  97      * Indent's default is 2 spaces, wordwrap's default is 40 characters.  And
  98      * you can turn off wordwrap by passing in 0.
  99      *
 100      * @access public
 101      * @static
 102      * @return string
 103      * @param array $array PHP array
 104      * @param int $indent Pass in false to use the default, which is 2
 105      * @param int $wordwrap Pass in 0 for no wordwrap, false for default (40)
 106      */
 107     public static function YAMLDump($array,$indent = false,$wordwrap = false) {
 108       $spyc = new Spyc;
 109       return $spyc->dump($array,$indent,$wordwrap);
 110     }
 111
 112     /**
 113      * Load YAML into a PHP array from an instantiated object
 114      *
 115      * The load method, when supplied with a YAML stream (string or file path),
 116      * will do its best to convert the YAML into a PHP array.  Pretty simple.
 117      *  Usage:
 118      *  <code>
 119      *   $parser = new Spyc;
 120      *   $array  = $parser->load('lucky.yml');
 121      *   print_r($array);
 122      *  </code>
 123      * @access public
 124      * @return array
 125      * @param string $input Path of YAML file or string containing YAML
 126      */
 127     function load($input) {
 128       // See what type of input we're talking about
 129       // If it's not a file, assume it's a string
 130       if (!empty($input) && (strpos($input, "\n") === false)
 131           && file_exists($input)) {
 132         $yaml = file($input);
 133       } else {
 134         $yaml = explode("\n",$input);
 135       }
 136       // Initiate some objects and values
 137       $base              = new YAMLNode;
 138       $base->indent      = 0;
 139       $this->_lastIndent = 0;
 140       $this->_lastNode   = $base->id;
 141       $this->_inBlock    = false;
 142       $this->_isInline   = false;
 143
 144       foreach ($yaml as $linenum => $line) {
 145         $ifchk = trim($line);
 146
 147         // If the line starts with a tab (instead of a space), throw a fit.
 148         if (preg_match('/^(\t)+(\w+)/', $line)) {
 149           $err = 'ERROR: Line '. ($linenum + 1) .' in your input YAML begins'.
 150                  ' with a tab.  YAML only recognizes spaces.  Please reformat.';
 151           die($err);
 152         }
 153
 154         if ($this->_inBlock === false && empty($ifchk)) {
 155           continue;
 156         } elseif ($this->_inBlock == true && empty($ifchk)) {
 157           $last =& $this->_allNodes[$this->_lastNode];
 158           $last->data[key($last->data)] .= "\n";
 159         } elseif ($ifchk{0} != '#' && substr($ifchk,0,3) != '---') {
 160           // Create a new node and get its indent
 161           $node         = new YAMLNode;
 162           $node->indent = $this->_getIndent($line);
 163
 164           // Check where the node lies in the hierarchy
 165           if ($this->_lastIndent == $node->indent) {
 166             // If we're in a block, add the text to the parent's data
 167             if ($this->_inBlock === true) {
 168               $parent =& $this->_allNodes[$this->_lastNode];
 169               $parent->data[key($parent->data)] .= trim($line).$this->_blockEnd;
 170             } else {
 171               // The current node's parent is the same as the previous node's
 172               if (isset($this->_allNodes[$this->_lastNode])) {
 173                 $node->parent = $this->_allNodes[$this->_lastNode]->parent;
 174               }
 175             }
 176           } elseif ($this->_lastIndent < $node->indent) {
 177             if ($this->_inBlock === true) {
 178               $parent =& $this->_allNodes[$this->_lastNode];
 179               $parent->data[key($parent->data)] .= trim($line).$this->_blockEnd;
 180             } elseif ($this->_inBlock === false) {
 181               // The current node's parent is the previous node
 182               $node->parent = $this->_lastNode;
 183
 184               // If the value of the last node's data was > or | we need to
 185               // start blocking i.e. taking in all lines as a text value until
 186               // we drop our indent.
 187               $parent =& $this->_allNodes[$node->parent];
 188               $this->_allNodes[$node->parent]->children = true;
 189               if (is_array($parent->data)) {
 190                 $chk = $parent->data[key($parent->data)];
 191                 if ($chk === '>') {
 192                   $this->_inBlock  = true;
 193                   $this->_blockEnd = ' ';
 194                   $parent->data[key($parent->data)] =
 195                         str_replace('>','',$parent->data[key($parent->data)]);
 196                   $parent->data[key($parent->data)] .= trim($line).' ';
 197                   $this->_allNodes[$node->parent]->children = false;
 198                   $this->_lastIndent = $node->indent;
 199                 } elseif ($chk === '|') {
 200                   $this->_inBlock  = true;
 201                   $this->_blockEnd = "\n";
 202                   $parent->data[key($parent->data)] =
 203                         str_replace('|','',$parent->data[key($parent->data)]);
 204                   $parent->data[key($parent->data)] .= trim($line)."\n";
 205                   $this->_allNodes[$node->parent]->children = false;
 206                   $this->_lastIndent = $node->indent;
 207                 }
 208               }
 209             }
 210           } elseif ($this->_lastIndent > $node->indent) {
 211             // Any block we had going is dead now
 212             if ($this->_inBlock === true) {
 213               $this->_inBlock = false;
 214               if ($this->_blockEnd = "\n") {
 215                 $last =& $this->_allNodes[$this->_lastNode];
 216                 $last->data[key($last->data)] =
 217                       trim($last->data[key($last->data)]);
 218               }
 219             }
 220
 221             // We don't know the parent of the node so we have to find it
 222             // foreach ($this->_allNodes as $n) {
 223             foreach ($this->_indentSort[$node->indent] as $n) {
 224               if ($n->indent == $node->indent) {
 225                 $node->parent = $n->parent;
 226               }
 227             }
 228           }
 229
 230           if ($this->_inBlock === false) {
 231             // Set these properties with information from our current node
 232             $this->_lastIndent = $node->indent;
 233             // Set the last node
 234             $this->_lastNode = $node->id;
 235             // Parse the YAML line and return its data
 236             $node->data = $this->_parseLine($line);
 237             // Add the node to the master list
 238             $this->_allNodes[$node->id] = $node;
 239             // Add a reference to the node in an indent array
 240             $this->_indentSort[$node->indent][] =& $this->_allNodes[$node->id];
 241             // Add a reference to the node in a References array if this node
 242             // has a YAML reference in it.
 243             if (
 244               ( (is_array($node->data)) &&
 245                 isset($node->data[key($node->data)]) &&
 246                 (!is_array($node->data[key($node->data)])) )
 247               &&
 248               ( (preg_match('/^&([^ ]+)/',$node->data[key($node->data)]))
 249                 ||
 250                 (preg_match('/^\*([^ ]+)/',$node->data[key($node->data)])) )
 251             ) {
 252                 $this->_haveRefs[] =& $this->_allNodes[$node->id];
 253             } elseif (
 254               ( (is_array($node->data)) &&
 255                 isset($node->data[key($node->data)]) &&
 256                  (is_array($node->data[key($node->data)])) )
 257             ) {
 258               // Incomplete reference making code.  Ugly, needs cleaned up.
 259               foreach ($node->data[key($node->data)] as $d) {
 260                 if ( !is_array($d) &&
 261                   ( (preg_match('/^&([^ ]+)/',$d))
 262                     ||
 263                     (preg_match('/^\*([^ ]+)/',$d)) )
 264                   ) {
 265                     $this->_haveRefs[] =& $this->_allNodes[$node->id];
 266                 }
 267               }
 268             }
 269           }
 270         }
 271       }
 272       unset($node);
 273
 274       // Here we travel through node-space and pick out references (& and *)
 275       $this->_linkReferences();
 276
 277       // Build the PHP array out of node-space
 278       $trunk = $this->_buildArray();
 279       return $trunk;
 280     }
 281
 282     /**
 283      * Dump PHP array to YAML
 284      *
 285      * The dump method, when supplied with an array, will do its best
 286      * to convert the array into friendly YAML.  Pretty simple.  Feel free to
 287      * save the returned string as tasteful.yml and pass it around.
 288      *
 289      * Oh, and you can decide how big the indent is and what the wordwrap
 290      * for folding is.  Pretty cool -- just pass in 'false' for either if
 291      * you want to use the default.
 292      *
 293      * Indent's default is 2 spaces, wordwrap's default is 40 characters.  And
 294      * you can turn off wordwrap by passing in 0.
 295      *
 296      * @access public
 297      * @return string
 298      * @param array $array PHP array
 299      * @param int $indent Pass in false to use the default, which is 2
 300      * @param int $wordwrap Pass in 0 for no wordwrap, false for default (40)
 301      */
 302     function dump($array,$indent = false,$wordwrap = false) {
 303       // Dumps to some very clean YAML.  We'll have to add some more features
 304       // and options soon.  And better support for folding.
 305
 306       // New features and options.
 307       if ($indent === false or !is_numeric($indent)) {
 308         $this->_dumpIndent = 2;
 309       } else {
 310         $this->_dumpIndent = $indent;
 311       }
 312
 313       if ($wordwrap === false or !is_numeric($wordwrap)) {
 314         $this->_dumpWordWrap = 40;
 315       } else {
 316         $this->_dumpWordWrap = $wordwrap;
 317       }
 318
 319       // New YAML document
 320       $string = "---\n";
 321
 322       // Start at the base of the array and move through it.
 323       foreach ($array as $key => $value) {
 324         $string .= $this->_yamlize($key,$value,0);
 325       }
 326       return $string;
 327     }
 328
 329     /**** Private Properties ****/
 330
 331     /**#@+
 332      * @access private
 333      * @var mixed
 334      */
 335     var $_haveRefs;
 336     var $_allNodes;
 337     var $_lastIndent;
 338     var $_lastNode;
 339     var $_inBlock;
 340     var $_isInline;
 341     var $_dumpIndent;
 342     var $_dumpWordWrap;
 343     /**#@+*/
 344
 345     /**** Private Methods ****/
 346
 347     /**
 348      * Attempts to convert a key / value array item to YAML
 349      * @access private
 350      * @return string
 351      * @param $key The name of the key
 352      * @param $value The value of the item
 353      * @param $indent The indent of the current node
 354      */
 355     function _yamlize($key,$value,$indent) {
 356       if (is_array($value)) {
 357         // It has children.  What to do?
 358         // Make it the right kind of item
 359         $string = $this->_dumpNode($key,NULL,$indent);
 360         // Add the indent
 361         $indent += $this->_dumpIndent;
 362         // Yamlize the array
 363         $string .= $this->_yamlizeArray($value,$indent);
 364       } elseif (!is_array($value)) {
 365         // It doesn't have children.  Yip.
 366         $string = $this->_dumpNode($key,$value,$indent);
 367       }
 368       return $string;
 369     }
 370
 371     /**
 372      * Attempts to convert an array to YAML
 373      * @access private
 374      * @return string
 375      * @param $array The array you want to convert
 376      * @param $indent The indent of the current level
 377      */
 378     function _yamlizeArray($array,$indent) {
 379       if (is_array($array)) {
 380         $string = '';
 381         foreach ($array as $key => $value) {
 382           $string .= $this->_yamlize($key,$value,$indent);
 383         }
 384         return $string;
 385       } else {
 386         return false;
 387       }
 388     }
 389
 390     /**
 391      * Returns YAML from a key and a value
 392      * @access private
 393      * @return string
 394      * @param $key The name of the key
 395      * @param $value The value of the item
 396      * @param $indent The indent of the current node
 397      */
 398     function _dumpNode($key,$value,$indent) {
 399       // do some folding here, for blocks
 400       if (strpos($value,"\n")) {
 401         $value = $this->_doLiteralBlock($value,$indent);
 402       } else {
 403         $value  = $this->_doFolding($value,$indent);
 404       }
 405
 406       $spaces = str_repeat(' ',$indent);
 407
 408       if (is_int($key)) {
 409         // It's a sequence
 410         $string = $spaces.'- '.$value."\n";
 411       } else {
 412         // It's mapped
 413         $string = $spaces.$key.': '.$value."\n";
 414       }
 415       return $string;
 416     }
 417
 418     /**
 419      * Creates a literal block for dumping
 420      * @access private
 421      * @return string
 422      * @param $value
 423      * @param $indent int The value of the indent
 424      */
 425     function _doLiteralBlock($value,$indent) {
 426       $exploded = explode("\n",$value);
 427       $newValue = '|';
 428       $indent  += $this->_dumpIndent;
 429       $spaces   = str_repeat(' ',$indent);
 430       foreach ($exploded as $line) {
 431         $newValue .= "\n" . $spaces . trim($line);
 432       }
 433       return $newValue;
 434     }
 435
 436     /**
 437      * Folds a string of text, if necessary
 438      * @access private
 439      * @return string
 440      * @param $value The string you wish to fold
 441      */
 442     function _doFolding($value,$indent) {
 443       // Don't do anything if wordwrap is set to 0
 444       if ($this->_dumpWordWrap === 0) {
 445         return $value;
 446       }
 447
 448       if (strlen($value) > $this->_dumpWordWrap) {
 449         $indent += $this->_dumpIndent;
 450         $indent = str_repeat(' ',$indent);
 451         $wrapped = wordwrap($value,$this->_dumpWordWrap,"\n$indent");
 452         $value   = ">\n".$indent.$wrapped;
 453       }
 454       return $value;
 455     }
 456
 457     /* Methods used in loading */
 458
 459     /**
 460      * Finds and returns the indentation of a YAML line
 461      * @access private
 462      * @return int
 463      * @param string $line A line from the YAML file
 464      */
 465     function _getIndent($line) {
 466       $match = array();
 467       preg_match('/^\s{1,}/',$line,$match);
 468       if (!empty($match[0])) {
 469         $indent = substr_count($match[0],' ');
 470       } else {
 471         $indent = 0;
 472       }
 473       return $indent;
 474     }
 475
 476     /**
 477      * Parses YAML code and returns an array for a node
 478      * @access private
 479      * @return array
 480      * @param string $line A line from the YAML file
 481      */
 482     function _parseLine($line) {
 483       $line = trim($line);
 484
 485       $array = array();
 486
 487       if (preg_match('/^-(.*):$/',$line)) {
 488         // It's a mapped sequence
 489         $key         = trim(substr(substr($line,1),0,-1));
 490         $array[$key] = '';
 491       } elseif ($line[0] == '-' && substr($line,0,3) != '---') {
 492         // It's a list item but not a new stream
 493         if (strlen($line) > 1) {
 494           $value   = trim(substr($line,1));
 495           // Set the type of the value.  Int, string, etc
 496           $value   = $this->_toType($value);
 497           $array[] = $value;
 498         } else {
 499           $array[] = array();
 500         }
 501       } elseif (preg_match('/^(.+):/',$line,$key)) {
 502         // It's a key/value pair most likely
 503         // If the key is in double quotes pull it out
 504         $matches = array();
 505         if (preg_match('/^(["\'](.*)["\'](\s)*:)/',$line,$matches)) {
 506           $value = trim(str_replace($matches[1],'',$line));
 507           $key   = $matches[2];
 508         } else {
 509           // Do some guesswork as to the key and the value
 510           $explode = explode(':',$line);
 511           $key     = trim($explode[0]);
 512           array_shift($explode);
 513           $value   = trim(implode(':',$explode));
 514         }
 515
 516         // Set the type of the value.  Int, string, etc
 517         $value = $this->_toType($value);
 518         if (empty($key)) {
 519           $array[]     = $value;
 520         } else {
 521           $array[$key] = $value;
 522         }
 523       }
 524       return $array;
 525     }
 526
 527     /**
 528      * Finds the type of the passed value, returns the value as the new type.
 529      * @access private
 530      * @param string $value
 531      * @return mixed
 532      */
 533     function _toType($value) {
 534       $matches = array();
 535       if (preg_match('/^("(.*)"|\'(.*)\')/',$value,$matches)) {
 536        $value = (string)preg_replace('/(\'\'|\\\\\')/',"'",end($matches));
 537        $value = preg_replace('/\\\\"/','"',$value);
 538       } elseif (preg_match('/^\\[(.+)\\]$/',$value,$matches)) {
 539         // Inline Sequence
 540
 541         // Take out strings sequences and mappings
 542         $explode = $this->_inlineEscape($matches[1]);
 543
 544         // Propogate value array
 545         $value  = array();
 546         foreach ($explode as $v) {
 547           $value[] = $this->_toType($v);
 548         }
 549       } elseif (strpos($value,': ')!==false && !preg_match('/^{(.+)/',$value)) {
 550           // It's a map
 551           $array = explode(': ',$value);
 552           $key   = trim($array[0]);
 553           array_shift($array);
 554           $value = trim(implode(': ',$array));
 555           $value = $this->_toType($value);
 556           $value = array($key => $value);
 557       } elseif (preg_match("/{(.+)}$/",$value,$matches)) {
 558         // Inline Mapping
 559
 560         // Take out strings sequences and mappings
 561         $explode = $this->_inlineEscape($matches[1]);
 562
 563         // Propogate value array
 564         $array = array();
 565         foreach ($explode as $v) {
 566           $array = $array + $this->_toType($v);
 567         }
 568         $value = $array;
 569       } elseif (strtolower($value) == 'null' or $value == '' or $value == '~') {
 570         $value = NULL;
 571       } elseif (ctype_digit($value)) {
 572         $value = (int)$value;
 573       } elseif (in_array(strtolower($value),
 574                   array('true', 'on', '+', 'yes', 'y'))) {
 575         $value = TRUE;
 576       } elseif (in_array(strtolower($value),
 577                   array('false', 'off', '-', 'no', 'n'))) {
 578         $value = FALSE;
 579       } elseif (is_numeric($value)) {
 580         $value = (float)$value;
 581       } else {
 582         // Just a normal string, right?
 583         $value = trim(preg_replace('/#(.+)$/','',$value));
 584       }
 585
 586       return $value;
 587     }
 588
 589     /**
 590      * Used in inlines to check for more inlines or quoted strings
 591      * @access private
 592      * @return array
 593      */
 594     function _inlineEscape($inline) {
 595       // There's gotta be a cleaner way to do this...
 596       // While pure sequences seem to be nesting just fine,
 597       // pure mappings and mappings with sequences inside can't go very
 598       // deep.  This needs to be fixed.
 599
 600       // Check for strings
 601       $regex = '/(?:(")|(?:\'))((?(1)[^"]+|[^\']+))(?(1)"|\')/';
 602       $strings = array();
 603       if (preg_match_all($regex,$inline,$strings)) {
 604         $saved_strings[] = $strings[0][0];
 605         $inline  = preg_replace($regex,'YAMLString',$inline);
 606       }
 607       unset($regex);
 608
 609       // Check for sequences
 610       $seqs = array();
 611       if (preg_match_all('/\[(.+)\]/U',$inline,$seqs)) {
 612         $inline = preg_replace('/\[(.+)\]/U','YAMLSeq',$inline);
 613         $seqs   = $seqs[0];
 614       }
 615
 616       // Check for mappings
 617       $maps = array();
 618       if (preg_match_all('/{(.+)}/U',$inline,$maps)) {
 619         $inline = preg_replace('/{(.+)}/U','YAMLMap',$inline);
 620         $maps   = $maps[0];
 621       }
 622
 623       $explode = explode(', ',$inline);
 624
 625       // Re-add the strings
 626       if (!empty($saved_strings)) {
 627         $i = 0;
 628         foreach ($explode as $key => $value) {
 629           if (strpos($value,'YAMLString')) {
 630             $explode[$key] = str_replace('YAMLString',$saved_strings[$i],$value);
 631             ++$i;
 632           }
 633         }
 634       }
 635
 636       // Re-add the sequences
 637       if (!empty($seqs)) {
 638         $i = 0;
 639         foreach ($explode as $key => $value) {
 640           if (strpos($value,'YAMLSeq') !== false) {
 641             $explode[$key] = str_replace('YAMLSeq',$seqs[$i],$value);
 642             ++$i;
 643           }
 644         }
 645       }
 646
 647       // Re-add the mappings
 648       if (!empty($maps)) {
 649         $i = 0;
 650         foreach ($explode as $key => $value) {
 651           if (strpos($value,'YAMLMap') !== false) {
 652             $explode[$key] = str_replace('YAMLMap',$maps[$i],$value);
 653             ++$i;
 654           }
 655         }
 656       }
 657
 658       return $explode;
 659     }
 660
 661     /**
 662      * Builds the PHP array from all the YAML nodes we've gathered
 663      * @access private
 664      * @return array
 665      */
 666     function _buildArray() {
 667       $trunk = array();
 668
 669       if (!isset($this->_indentSort[0])) {
 670         return $trunk;
 671       }
 672
 673       foreach ($this->_indentSort[0] as $n) {
 674         if (empty($n->parent)) {
 675           $this->_nodeArrayizeData($n);
 676           // Check for references and copy the needed data to complete them.
 677           $this->_makeReferences($n);
 678           // Merge our data with the big array we're building
 679           $trunk = $this->_array_kmerge($trunk,$n->data);
 680         }
 681       }
 682
 683       return $trunk;
 684     }
 685
 686     /**
 687      * Traverses node-space and sets references (& and *) accordingly
 688      * @access private
 689      * @return bool
 690      */
 691     function _linkReferences() {
 692       if (is_array($this->_haveRefs)) {
 693         foreach ($this->_haveRefs as $node) {
 694           if (!empty($node->data)) {
 695             $key = key($node->data);
 696             // If it's an array, don't check.
 697             if (is_array($node->data[$key])) {
 698               foreach ($node->data[$key] as $k => $v) {
 699                 $this->_linkRef($node,$key,$k,$v);
 700               }
 701             } else {
 702               $this->_linkRef($node,$key);
 703             }
 704           }
 705         }
 706       }
 707       return true;
 708     }
 709
 710     function _linkRef(&$n,$key,$k = NULL,$v = NULL) {
 711       if (empty($k) && empty($v)) {
 712         // Look for &refs
 713         $matches = array();
 714         if (preg_match('/^&([^ ]+)/',$n->data[$key],$matches)) {
 715           // Flag the node so we know it's a reference
 716           $this->_allNodes[$n->id]->ref = substr($matches[0],1);
 717           $this->_allNodes[$n->id]->data[$key] =
 718                    substr($n->data[$key],strlen($matches[0])+1);
 719         // Look for *refs
 720         } elseif (preg_match('/^\*([^ ]+)/',$n->data[$key],$matches)) {
 721           $ref = substr($matches[0],1);
 722           // Flag the node as having a reference
 723           $this->_allNodes[$n->id]->refKey =  $ref;
 724         }
 725       } elseif (!empty($k) && !empty($v)) {
 726         if (preg_match('/^&([^ ]+)/',$v,$matches)) {
 727           // Flag the node so we know it's a reference
 728           $this->_allNodes[$n->id]->ref = substr($matches[0],1);
 729           $this->_allNodes[$n->id]->data[$key][$k] =
 730                               substr($v,strlen($matches[0])+1);
 731         // Look for *refs
 732         } elseif (preg_match('/^\*([^ ]+)/',$v,$matches)) {
 733           $ref = substr($matches[0],1);
 734           // Flag the node as having a reference
 735           $this->_allNodes[$n->id]->refKey =  $ref;
 736         }
 737       }
 738     }
 739
 740     /**
 741      * Finds the children of a node and aids in the building of the PHP array
 742      * @access private
 743      * @param int $nid The id of the node whose children we're gathering
 744      * @return array
 745      */
 746     function _gatherChildren($nid) {
 747       $return = array();
 748       $node   =& $this->_allNodes[$nid];
 749       foreach ($this->_allNodes as $z) {
 750         if ($z->parent == $node->id) {
 751           // We found a child
 752           $this->_nodeArrayizeData($z);
 753           // Check for references
 754           $this->_makeReferences($z);
 755           // Merge with the big array we're returning
 756           // The big array being all the data of the children of our parent node
 757           $return = $this->_array_kmerge($return,$z->data);
 758         }
 759       }
 760       return $return;
 761     }
 762
 763     /**
 764      * Turns a node's data and its children's data into a PHP array
 765      *
 766      * @access private
 767      * @param array $node The node which you want to arrayize
 768      * @return boolean
 769      */
 770     function _nodeArrayizeData(&$node) {
 771       if (is_array($node->data) && $node->children == true) {
 772         // This node has children, so we need to find them
 773         $childs = $this->_gatherChildren($node->id);
 774         // We've gathered all our children's data and are ready to use it
 775         $key = key($node->data);
 776         $key = empty($key) ? 0 : $key;
 777         // If it's an array, add to it of course
 778         if (is_array($node->data[$key])) {
 779           $node->data[$key] = $this->_array_kmerge($node->data[$key],$childs);
 780         } else {
 781           $node->data[$key] = $childs;
 782         }
 783       } elseif (!is_array($node->data) && $node->children == true) {
 784         // Same as above, find the children of this node
 785         $childs       = $this->_gatherChildren($node->id);
 786         $node->data   = array();
 787         $node->data[] = $childs;
 788       }
 789
 790       // We edited $node by reference, so just return true
 791       return true;
 792     }
 793
 794     /**
 795      * Traverses node-space and copies references to / from this object.
 796      * @access private
 797      * @param object $z A node whose references we wish to make real
 798      * @return bool
 799      */
 800     function _makeReferences(&$z) {
 801       // It is a reference
 802       if (isset($z->ref)) {
 803         $key                = key($z->data);
 804         // Copy the data to this object for easy retrieval later
 805         $this->ref[$z->ref] =& $z->data[$key];
 806       // It has a reference
 807       } elseif (isset($z->refKey)) {
 808         if (isset($this->ref[$z->refKey])) {
 809           $key           = key($z->data);
 810           // Copy the data from this object to make the node a real reference
 811           $z->data[$key] =& $this->ref[$z->refKey];
 812         }
 813       }
 814       return true;
 815     }
 816
 817
 818     /**
 819      * Merges arrays and maintains numeric keys.
 820      *
 821      * An ever-so-slightly modified version of the array_kmerge() function posted
 822      * to php.net by mail at nospam dot iaindooley dot com on 2004-04-08.
 823      *
 824      * http://us3.php.net/manual/en/function.array-merge.php#41394
 825      *
 826      * @access private
 827      * @param array $arr1
 828      * @param array $arr2
 829      * @return array
 830      */
 831     function _array_kmerge($arr1,$arr2) {
 832       if(!is_array($arr1))
 833         $arr1 = array();
 834
 835       if(!is_array($arr2))
 836         $arr2 = array();
 837
 838       $keys1 = array_keys($arr1);
 839       $keys2 = array_keys($arr2);
 840       $keys  = array_merge($keys1,$keys2);
 841       $vals1 = array_values($arr1);
 842       $vals2 = array_values($arr2);
 843       $vals  = array_merge($vals1,$vals2);
 844       $ret   = array();
 845
 846       foreach($keys as $key) {
 847         list( /* unused */ ,$val) = each($vals);
 848         // This is the good part!  If a key already exists, but it's part of a
 849         // sequence (an int), just keep addin numbers until we find a fresh one.
 850         if (isset($ret[$key]) and is_int($key)) {
 851           while (array_key_exists($key, $ret)) {
 852             $key++;
 853           }
 854         }
 855         $ret[$key] = $val;
 856       }
 857
 858       return $ret;
 859     }
 860   }
 861 ?>