Crawler, second version

lib/encoding.js

+let {Logger} = require( "logger" );
+
+function tab( indent )
+{
+  var s = "";
+  for ( let i = indent ; i > 0 ; --i )
+    s += "    ";
+  return s;
+}
+
+//-------------------------------------------------------
+// Multiple Format
+//-------------------------------------------------------
+/**
+ * Combine a number of formats as a single output.
+ * <p>
+ * Written to support an ordinary use case: YAML to the log window, JSON to file.
+ * @constructor
+ */
+var Multiple_Format = function()
+{
+  this.formatters = [];
+};
+
+Multiple_Format.prototype.add = function( formatter )
+{
+  this.formatters.push( formatter );
+};
+
+Multiple_Format.prototype.primitive = function( value )
+{
+  for ( let f of this.formatters )
+  {
+    f.primitive( value );
+  }
+};
+
+Multiple_Format.prototype.special_null = function()
+{
+  for ( let f of this.formatters )
+  {
+    f.special_null();
+  }
+};
+
+Multiple_Format.prototype.object_begin = function()
+{
+  for ( let f of this.formatters )
+  {
+    f.object_begin();
+  }
+};
+
+Multiple_Format.prototype.object_before_element = function( key )
+{
+  for ( let f of this.formatters )
+  {
+    f.object_before_element( key );
+  }
+};
+
+Multiple_Format.prototype.object_end = function()
+{
+  for ( let f of this.formatters )
+  {
+    f.object_end();
+  }
+};
+
+Multiple_Format.prototype.array_begin = function()
+{
+  for ( let f of this.formatters )
+  {
+    f.array_begin();
+  }
+};
+
+Multiple_Format.prototype.array_before_element = function()
+{
+  for ( let f of this.formatters )
+  {
+    f.array_before_element();
+  }
+};
+
+Multiple_Format.prototype.array_end = function()
+{
+  for ( let f of this.formatters )
+  {
+    f.array_end();
+  }
+};
+
+//-------------------------------------------------------
+// Stack-based Formatter
+//-------------------------------------------------------
+/**
+ * Base class for formatters that provides an internal stack.
+ * <p>
+ * Stack provides a default 'counter' member for detection first/subsequent sequence members to support delimiters.
+ * @constructor
+ */
+var Stack_Format_class = function()
+{
+};
+
+Stack_Format_class.init = function()
+{
+  this._format_stack = [];
+};
+
+/**
+ * @param {Object} x
+ *      Stack object. A 'counter' member is added whose initial value is zero.
+ */
+Stack_Format_class.prototype.push_format = function( x )
+{
+  this._format_stack.push( x );
+  this._format_stack[ this._format_stack.length - 1 ].counter = 0;
+};
+
+/**
+ * Pop an item off the top of the format stack.
+ */
+Stack_Format_class.prototype.pop_format = function()
+{
+  this._format_stack.pop();
+};
+
+/**
+ * Retrieve the format on the top of the format stack.
+ * @param {number} [n]
+ * @return {*}
+ */
+Stack_Format_class.prototype.top_format = function( n )
+{
+  if ( arguments.length == 0 )
+  {
+    n = 0;
+  }
+  return this._format_stack[ this._format_stack.length - n - 1];
+};
+
+Stack_Format_class.prototype.counter = function()
+{
+  return this.top_format( 0 ).counter;
+};
+
+Stack_Format_class.prototype.advance = function()
+{
+  ++this.top_format( 0 ).counter;
+};
+
+//-------------------------------------------------------
+// JSON Formatter
+//-------------------------------------------------------
+var JSON_Format = function( sink )
+{
+  Stack_Format_class.init.call( this );
+
+  this.sink = sink;
+};
+JSON_Format.prototype = new Stack_Format_class();
+
+JSON_Format.prototype.primitive = function( value )
+{
+  this.sink( JSON.stringify( value ) );
+};
+
+JSON_Format.prototype.special_null = function()
+{
+  this.sink( "null" );
+};
+
+JSON_Format.prototype.object_begin = function()
+{
+  this.sink( "{" );
+  this.push_format( {} );
+};
+
+JSON_Format.prototype.object_before_element = function( key )
+{
+  if ( this.counter() != 0 )
+    this.sink( "," );
+  this.advance();
+  this.sink( JSON.stringify( key ) + ":" );
+};
+
+JSON_Format.prototype.object_end = function()
+{
+  this.sink( "}" );
+  this.pop_format();
+};
+
+JSON_Format.prototype.array_begin = function()
+{
+  this.sink( "[" );
+  this.push_format( {} );
+};
+
+JSON_Format.prototype.array_before_element = function()
+{
+  if ( this.counter() != 0 )
+    this.sink( "," );
+  this.advance();
+};
+
+JSON_Format.prototype.array_end = function()
+{
+  this.sink( "]" );
+  this.pop_format();
+};
+
+//-------------------------------------------------------
+// YAML Formatter
+//-------------------------------------------------------
+
+var YAML_Format = function( sink )
+{
+  Stack_Format_class.init.call( this );
+
+  this.sink = sink;
+
+  this.push_format( {
+    indent: 0,
+    primitive_extra: "",
+    aggregate_first: ""
+  } );
+
+  this.logger = new Logger( "YAML_format" );
+  //this.logger.suppress( true );
+
+  this.trace_token = false;
+};
+YAML_Format.prototype = new Stack_Format_class();
+
+YAML_Format.array_mark = "- ";
+YAML_Format.array_extra = "  ";
+
+YAML_Format.prototype.primitive = function( value )
+{
+  this._atom( value.toString() );
+};
+
+YAML_Format.prototype.special_null = function()
+{
+  this._atom( "null" );
+};
+
+YAML_Format.prototype._atom = function( s )
+{
+  this.sink( this.top_format().primitive_extra + s + "\n" );
+};
+
+//----------------------------------
+// YAML_format, object
+//----------------------------------
+
+YAML_Format.prototype.object_begin = function()
+{
+  var format = this.top_format();
+  this.push_format( {
+    indent: format.indent + 1,
+    primitive_extra: " ",
+    aggregate_first: "\n" + tab( format.indent + 1 )
+  } );
+};
+
+YAML_Format.prototype.object_before_element = function( key )
+{
+  let parent = this.top_format( 1 );
+
+  if ( this.counter() == 0 )
+  {
+    this.sink( parent.aggregate_first );
+  }
+  else
+  {
+    this.sink( tab( parent.indent ) );
+  }
+  this.sink( key + ":" );
+  this.advance();
+};
+
+YAML_Format.prototype.object_end = function()
+{
+  this.pop_format();
+};
+
+//----------------------------------
+// YAML_format, array
+//----------------------------------
+
+YAML_Format.prototype.array_begin = function()
+{
+  let parent = this.top_format();
+  let prefix = parent.aggregate_first + YAML_Format.array_mark;
+
+  this.push_format( {
+    indent: parent.indent + 1,
+    primitive_extra: prefix,
+    aggregate_first: prefix + YAML_Format.array_extra
+  } );
+  this.logger.make_log( "array_begin" )(
+    "\n\tprefix = " + JSON.stringify( prefix )
+      + "\n\tparent = " + JSON.stringify( parent )
+      + "\n\tformat = " + JSON.stringify( this.top_format() ),
+    false
+  )
+};
+
+YAML_Format.prototype.array_before_element = function()
+{
+  let format = this.top_format( 0 );
+  let parent = this.top_format( 1 );
+
+  this.logger.make_log( "array_before_element" )(
+    "\n\tparent = " + JSON.stringify( parent )
+      + "\n\tformat = " + JSON.stringify( format )
+      + "\n\tcounter = " + this.counter(),
+    false
+  );
+
+  if ( this.counter() > 0 )
+  {
+    let prefix = tab( parent.indent ) + YAML_Format.array_mark;
+    this.swap_format( format.indent, prefix, prefix + YAML_Format.array_extra );
+  }
+  this.advance();
+};
+
+YAML_Format.prototype.array_end = function()
+{
+  let format = this.top_format( 0 );
+  let parent = this.top_format( 1 );
+
+  this.logger.make_log( "array_end" )(
+    "\n\tparent = " + JSON.stringify( parent )
+      + "\n\tformat = " + JSON.stringify( format )
+      + "\n\tcounter = " + this.counter(),
+    false
+  );
+
+  if ( this.counter() == 0 )
+    this.sink( parent.primitive_extra + "\n" );
+
+  this.pop_format();
+};
+
+/**
+ * Replace the top element of the format stack for the arguments. The top element is discarded.
+ *
+ * @param {number} indent
+ * @param {string} primitive_extra
+ * @param {string} aggregate_first
+ */
+YAML_Format.prototype.swap_format = function( indent, primitive_extra, aggregate_first )
+{
+  var format = this.top_format( 0 );
+  format.indent = indent;
+  format.primitive_extra = primitive_extra;
+  format.aggregate_first = aggregate_first;
+};
+
+//-------------------------------------------------------
+// Format_stream
+//-------------------------------------------------------
+/**
+ * Stream output in YAML format.
+ * @param formatter
+ *      An instance of one of the *_Format classes.
+ * @constructor
+ */
+var Format_stream = function( formatter )
+{
+  this.logger = new Logger( "Format_stream" );
+
+  /**
+   * Traversal stack. Tracks the depth-first traversal tokens.
+   * @type {Array}
+   */
+  this.stack = [];
+
+  this._writing = false;
+
+  /**
+   * Input queue. We only need one token of lookahead, but that means that we need to manage an input token that
+   * may be present or not.
+   * @type {Array}
+   */
+  this._input_queue = [];
+
+  this.formatter = formatter;
+
+  this.logger.suppress( true );
+  this.trace_input = false;
+  this.trace_token = false;
+};
+
+Format_stream.prototype.sequence_start = function()
+{
+  this.logger.make_log( "sequence_start" )( "" );
+  this._send( { view: { type: Encoding.type.start }, content: { mark: Encoding.type.start } } );
+};
+
+Format_stream.prototype.sequence_stop = function()
+{
+  this.logger.make_log( "sequence_stop" )( "" );
+  this._send( { view: { type: Encoding.type.stop }, content: { mark: Encoding.type.stop } } );
+};
+
+Format_stream.prototype.sequence_send = function( value )
+{
+  this._send( { content: { value: value } } );
+};
+
+function is_mark( token )
+{
+  return ("content" in token) && ("mark" in token.content);
+}
+
+function is_value( token )
+{
+  return ("content" in token) && ("value" in token.content);
+}
+
+function get_value( token )
+{
+  return token.content.value;
+}
+
+/**
+ * Send a token to the state machine.
+ * @param token
+ * @private
+ */
+Format_stream.prototype._send = function( token )
+{
+  if ( !this._writing )
+  {
+    throw new Error( "May not send tokens when we aren't writing." )
+  }
+  this.logger.make_log( "_send" )( "SEND: " + "\n\ttoken = " + JSON.stringify( token ), false );
+  try
+  {
+    this._insert_input( token );
+    this.generator.next();
+  }
+  catch ( e )
+  {
+    if ( e === StopIteration )
+    // This is expected if it stops the last deferred sequence in the object.
+      return;
+    throw e;
+  }
+};
+
+Format_stream.prototype.write = function( value, view )
+{
+  /*
+   * Consistency check to ensure that the caller has been feeding us correctly. If this throws, it means the
+   * caller has made a mistake.
+   */
+  if ( this._writing )
+    throw new Error( "Already writing" );
+  this._writing = true;
+
+  /*
+   * Initialize the input queue with a single token, the one that will be expanded.
+   *
+   * Start the generator and bring it
+   * to its first yield statement. It will stop if there are no stream inputs within the token, so we check for that.
+   */
+  this._insert_input( { view: view, content: { value: value } } );
+  var g = this._machine();
+  this.generator = g;
+  try
+  {
+    g.next();
+  }
+  catch ( e )
+  {
+    if ( e !== StopIteration ) throw e;
+  }
+};
+
+/**
+ * Predicate: "Is write() available to be called?"
+ * @return {boolean}
+ */
+Format_stream.prototype.may_write = function()
+{
+  return !this._writing;
+};
+
+/**
+ * Stack processing machine for a depth-first traversal of an object tree structure where some of the nodes may
+ * be deferred streams.
+ * @private
+ */
+Format_stream.prototype._machine = function()
+{
+  /*
+   * The head token of our input stream, if initialized; otherwise undefined
+   */
+  var token = null;
+  /*
+   * Predicate: "the variable 'token' and related variables represent the head token of our input stream"
+   */
+  var have_token = false;
+  /*
+   *  Predicate: "we need to have a current token"
+   */
+  var need_token = false;
+  /*
+   * Predicate: "we need to have a lookahead token in the input queue that hasn't been consumed yet"
+   */
+  var need_lookahead = false;
+
+  while ( this._has_token() || this._has_input() )
+  {
+    // Log function indicates stack depth.
+    var log = this.logger.make_log( "machine(" + this.stack.length + ")" );
+
+    /*---------------------
+     * STAGE ONE: Manage input queue.
+     *
+     * We need a token if one of the handlers below has asked for it. If we need a token and we don't already have
+     * one, we ensure we have one with a yield statement. Since _send() is the only thing that calls us as a
+     * generator, we will have an input token after a yield.
+     *
+     * This section is here as a result of unrolling a recursive-descent algorithm. In that pattern, there would be
+     * calls such as queue.get() and queue.lookahead(1). Since we have unrolled everything, such calls occur here at
+     * the top of the loop. Code below makes the analogue of queue calls by setting the variables 'need_token' and
+     * 'need_lookahead'.
+     */
+    // Defense
+    if ( need_lookahead && need_token )
+    {
+      /*
+       * The head token of the stream cannot exist in two places at once. Either it's on the input queue
+       * or it has been consumed and is in the local 'token' variable.
+       */
+      throw new Error( "Requesting both lookahead and a current token is inconsistent." );
+    }
+
+    if ( need_lookahead )
+    {
+      if ( !have_token )
+      {
+        if ( !this._has_input() )
+        {
+          yield null;
+          // Defense
+          if ( !this._has_input() )
+            throw new Error( "Yielded for lookahead token but did not receive it." );
+        }
+
+        log( "Input LOOKAHEAD" +
+          "\n\ttoken = " + JSON.stringify( token ), this.trace_input );
+      }
+      else
+      {
+        // Untested
+        this._unconsume_input( token );
+        have_token = false;
+      }
+      need_lookahead = false;
+    }
+    else if ( need_token )
+    {
+      /*
+       * If we already have a token, we don't need to do anything more but clear the need_token flag.
+       */
+      if ( !have_token )
+      {
+        if ( !this._has_input() )
+        {
+          yield null;
+          // Defense
+          if ( !this._has_input() )
+            throw new Error( "Yielded for current token but did not receive it." );
+        }
+        // Assert this._has_input()
+        token = this._consume_input();
+        have_token = true;
+      }
+      need_token = false;
+
+      log( "Input CURRENT" +
+        "\n\ttoken = " + JSON.stringify( token ), this.trace_input );
+    }
+    else
+    {
+      // Defense
+      if ( !have_token && !this._has_token() && !this._has_input() )
+        throw new Error( "No current token, no token on traversal stack, and no token in queue" );
+      // Defense
+      token = undefined;
+    }
+
+    /*---------------------
+     * STAGE TWO: Automatic actions, those invoked without input.
+     *
+     * If we don't have a token, there's one either on the input queue or on the top of the traversal stack. If the
+     * traversal stack is empty, we use the input queue. If not, we act according to the state of the token at the
+     * top of the traversal stack.
+     */
+    if ( !have_token )
+    {
+      if ( !this._has_token() )
+      {
+        /*
+         * The token stack is empty. There must be something on the input queue for use to still be here.
+         */
+        need_token = true;
+        continue;
+      }
+
+      // Current Token
+      let c_token = this._top_token();
+      // Look-Ahead Token
+      var la_token = this._look_input();
+
+      log( "TRAVERSAL STACK TOKEN"
+        + "\n\ttop of stack = " + JSON.stringify( c_token )
+        + "\n\t" + ((this._has_input()) ? "lookahead = " + JSON.stringify( la_token ) : "no lookahead"),
+        this.trace_token
+      );
+
+      switch ( c_token.view.type.id )
+      {
+        case Encoding.type.object.id:
+          if ( c_token.state.i == 0 )
+          {
+            this.formatter.object_begin();
+          }
+          if ( c_token.state.i < c_token.view.seq.length )
+          {
+            let field = c_token.view.seq[ c_token.state.i ];
+            this.formatter.object_before_element( field.key );
+            let new_token = {
+              content: { value: c_token.content.value[ field.key ] }
+            };
+            if ( 'element_view' in field )
+            {
+              new_token.view = field.element_view;
+            }
+            this._insert_input( new_token );
+            need_token = true;
+            ++c_token.state.i;
+          }
+          else
+          {
+            this.formatter.object_end();
+            this._pop_token();
+          }
+          break;
+
+        case Encoding.type.array.id:
+          if ( c_token.state.i == 0 )
+          {
+            this.formatter.array_begin();
+          }
+          if ( c_token.state.i < c_token.content.value.length )
+          {
+            this.formatter.array_before_element();
+            this._insert_input( {
+              view: c_token.view.element_view,
+              content: { value: c_token.content.value[ c_token.state.i ] }
+            } );
+            need_token = true;
+            ++c_token.state.i;
+          }
+          else
+          {
+            this.formatter.array_end();
+            this._pop_token();
+          }
+          break;
+
+        case Encoding.type.array_stream.id:
+          if ( !this._has_input() )
+          {
+            // If we can't see the next token, we can't proceed.
+            need_lookahead = true;
+            break;
+          }
+          if ( is_mark( la_token ) )
+          {
+            switch ( la_token.view.type.id )
+            {
+              case Encoding.type.start.id:
+                let first_pass = ( c_token.state.i == 0 );
+                if ( first_pass )
+                {
+                  /*
+                   * Always consume a start token the first time we see one. So this one's ours.
+                   */
+                  this._consume_input();
+                  have_token = false;
+                  this.formatter.array_begin();
+                }
+
+                /*
+                 * Here we have the analogue of a shift-reduce decision. If the 'element_view' field
+                 * in the array specification is an ordinary type, we reduce to the rule that the next
+                 * elements are part of our list. If that field is a stream type, we need to shift to a
+                 * new list. In the second case, it means we need a new node on the top of the stack.
+                 */
+                let x = c_token.view.element_view;
+                if ( x && x.type.stream )
+                {
+                  /*
+                   * We need to associate the present start mark with a stream token we create. In
+                   * order to do that, we need the stream token to appear before the start mark. Thus
+                   * we stuff a token onto the _back_ end of the queue so that it's the next token
+                   * consumed. The start mark will then be consumed at the iteration following.
+                   */
+                  this._unconsume_input( { view: x, content: { value: null } } );
+                }
+                else
+                {
+                  /*
+                   * We have a start mark at some point after the first pass. That's only valid
+                   * when our element type is a stream type, which it's not at this point.
+                   */
+                  if ( !first_pass )
+                  {
+                    /*
+                     * This is not an internal defense, but an external one. If the user
+                     * makes a call to sequence_start() at the wrong time, we'll end up here.
+                     */
+                    throw new Error( "unexpected call to sequence_start()" );
+                  }
+                  /*
+                   * Note that if 'element_view' is defined but not a stream, that we have a type
+                   * specified for unseen elements. There might be a type conflict here. We are
+                   * resolving that conflict by ignoring 'element_view' unless it's a stream type.
+                   */
+                }
+                /*
+                 * Because the next token could be a stop mark, we don't load it as a current token.
+                 * Marks are always consumed as lookahead.
+                 */
+                need_lookahead = true;
+
+                log( "processed start mark"
+                  + "\n\ttop of stack = " + JSON.stringify( this._top_token() ),
+                  false );
+                break;
+              case Encoding.type.stop.id:
+                this._consume_input();
+                have_token = false;
+                this._pop_token();
+                this.formatter.array_end();
+                break;
+              default:
+                throw new Error( "Unexpected mark seen for array_stream" );
+            }
+          }
+          else
+          {
+            // Assert the lookahead token is a regular token, since it's not a mark
+            this.formatter.array_before_element();
+            ++c_token.state.i;
+            // Don't use more than 10 million elements in an array.
+            if ( c_token.state.i > 10000000 )
+              throw new Error( "Runaway loop" );
+            need_token = true;
+          }
+          break;
+        default:
+          throw new Error( "Found token type that should not appear as a non-input token" );
+      }
+      /*
+       * We're skipping all the code below and going back to the top of the loop, where any 'need_token' or
+       * 'need_lookahead' requests can be fulfilled.
+       */
+      continue;
+    }
+
+    /*---------------------
+     * Initialize the local variable 'value'. We may have received a mark, which requires different initialization.
+     */
+    // Defense
+    if ( is_mark( token ) )
+      throw new Error( "Value token expected; mark token found." );
+    // Defense
+    if ( !is_value( token ) )
+      throw new Error( "Value token expected; neither value nor mark token found." );
+    var value = get_value( token );
+
+    /*---------------------
+     * Obtain a view object.
+     *
+     * A view can arise in three different ways:
+     *      1) From a view specification. This is the only way that deferred items can arise.
+     *      2) By inference from a value. This is the ordinary way for most values.
+     *      3) By explicit specification on the object. [Not yet supported.] Moral equivalent of toJSON().
+     */
+    if ( !( "view" in token ) || !token.view )
+    {
+      try
+      {
+        if ( "__encoding__" in value )
+        {
+          token.view = value["__encoding__"];
+        }
+        else
+        {
+          token.view = {};
+        }
+      }
+      catch ( e )
+      {
+        token.view = {};
+      }
+    }
+    var view = token.view;
+
+    /*---------------------
+     * Honor a toJSON replacement object, if any. Note that we do this _after_ getting an encoding from the value,
+     * should we need to.
+     */
+    try
+    {
+      if ( "toJSON" in value )
+      {
+        value = value.toJSON();
+      }
+    }
+    catch ( e )
+    {
+      // Disregard errors. The most likely one happens when 'value' is not an object at all.
+    }
+
+    /*---------------------
+     * If we still need a type within our view, we need to infer one from the value we have.
+     */
+    if ( !( "type" in view ) )
+    {
+      // Determine the encoding.
+      if ( value == null )
+      {
+        view.type = Encoding.type.null;
+      }
+      else if ( ( typeof value ) == "object" )
+      {
+        let t = Object.prototype.toString.call( value );
+        switch ( t )
+        {
+          case "[object Array]":
+            view.type = Encoding.type.array;
+            break;
+          case "[object Object]":
+            view.type = Encoding.type.object;
+            try
+            {
+              var keys = Object.keys( value );
+            }
+            catch ( e )
+            {
+              // Sometimes an object is not an object. Really.
+              view.type = Encoding.type.primitive;
+              if ( value == null )
+              {
+                value = "null";
+              }
+              break;
+            }
+            view.seq = Encoding.immediate_fields( keys );
+            break;
+          default:
+            /*
+             * For example, [object Date]. They all have meaningful toString() implementations.
+             */
+            view.type = Encoding.type.primitive;
+            break;
+        }
+      }
+      else
+      {
+        view.type = Encoding.type.primitive;
+      }
+    }
+
+    log( "INPUT TOKEN.\n\tvalue = " + JSON.stringify( value )
+      + "\n\tview = " + JSON.stringify( view )
+      + "\n\t" + ( ('state' in token) ? "state = " + JSON.stringify( token.state ) : "no state" ),
+      this.trace_token
+    );
+
+    /*---------------------
+     * Process a single iteration step of the state machine.
+     *
+     * - If there's a deferred value, push the next state on to the stack.
+     * - If there's an immediate value, write it to the sink.
+     */
+    /*
+     * If we get this far, we'll consume the token in each case.
+     */
+    have_token = false;
+    if ( view.type.aggregate )
+    {
+      this._push_token( token );
+      // We'll loop back to the top and process the top of the stack next.
+      // Assert need_lookahead == false && need_token == false && have_token == false
+    }
+    else
+    {
+      switch ( view.type.id )
+      {
+        case Encoding.type.null.id:
+          this.formatter.special_null();
+          break;
+        case Encoding.type.primitive.id:
+          this.formatter.primitive( value );
+          break;
+        default:
+          throw new Error( "unexpected encoding type" );
+          break;
+        /*
+         * If we need to output "undefined", we'd do it here.
+         */
+      }
+    }
+  }
+  log = this.logger.make_log( "machine(" + this.stack.length + ")" );
+  log( "machine end" );
+  this._writing = false;
+};
+
+//----------------------------------
+// YAML_stream, traversal stack
+//----------------------------------
+/**
+ * Push a token onto the top of the traversal stack. Only aggregates go onto this stack. From the point of view of
+ * a graph traversal, atomic elements are leaf nodes and do not appear on the stack, and aggregates are non-leaf nodes
+ * and do appear. Since an aggregate may only be pushed once onto the traversal stack, we do initialization and a
+ * validation check here.
+ * @param token
+ * @private
+ */
+Format_stream.prototype._push_token = function( token )
+{
+  if ( "state" in token )
+  {
+    throw new Error( "An aggregate type may not be pushed more than once onto the traversal stack" );
+  }
+  else
+  {
+    token.state = { i: 0 };
+  }
+
+  if ( this.stack.length > 100 )
+    throw new Error( "stack overflow" );
+
+  this.stack.push( token );
+};
+
+/**
+ * The token on top of the traversal stack.
+ * @return {*}
+ * @private
+ */
+Format_stream.prototype._top_token = function()
+{
+  return this.stack[ this.stack.length - 1 ];
+};
+
+/**
+ * Pop a token off the top of the traversal stack.
+ * @return {*}
+ * @private
+ */
+Format_stream.prototype._pop_token = function()
+{
+  if ( this.stack.length == 0 )
+    throw new Error( "Stack empty" );
+  return this.stack.pop();
+};
+
+/**
+ * Predicate "Is the traversal stack non-empty?"
+ * @return {boolean}
+ * @private
+ */
+Format_stream.prototype._has_token = function()
+{
+  return this.stack.length != 0;
+};
+
+//----------------------------------
+// YAML_stream, input queue
+//----------------------------------
+/**
+ * Predicate "does the input queue have a token ready for us?"
+ * @private
+ */
+Format_stream.prototype._has_input = function()
+{
+  return this._input_queue.length > 0;
+};
+
+/**
+ * Look-ahead function. We shouldn't need more than to call this with n=0.
+ * @param {number} [n=0]
+ * @private
+ */
+Format_stream.prototype._look_input = function( n )
+{
+  if ( arguments.length == 0 )
+    n = 0;
+  return this._input_queue[ n ];
+};
+
+/**
+ * Put a token into the input queue.
+ * @param input
+ * @private
+ */
+Format_stream.prototype._insert_input = function( input )
+{
+  return this._input_queue.push( input );
+};
+
+/**
+ * Retrieve a token from the input queue and remove it so that it won't be examined again.
+ * @return {*}
+ * @private
+ */
+Format_stream.prototype._consume_input = function()
+{
+  return this._input_queue.shift();
+};
+
+/**
+ * Stuff a token back into the back end of the queue so that it will be seen again.
+ * @param token
+ * @return {*}
+ * @private
+ */
+Format_stream.prototype._unconsume_input = function( token )
+{
+  this._input_queue.unshift( token );
+};
+
+//-------------------------------------------------------
+// Encoding
+//-------------------------------------------------------
+
+/**
+ * The export object for this module.
+ */
+var Encoding = {
+  Format_stream: Format_stream,
+  YAML: YAML_Format,
+  JSON: JSON_Format,
+  Multiple_Format: Multiple_Format
+};
+Encoding.type = {
+  /**
+   * A primitive value or opaque object whose members are not separately output. Uses toString() to provide a value.
+   */
+  null: { id: 0, name: "null" },
+  /**
+   * A primitive value or opaque object whose members are not separately output. Uses toString() to provide a value.
+   */
+  primitive: { id: 1, name: "primitive" },
+  /**
+   * A transparent object whose members are each listed.
+   */
+  object: { id: 2, name: "object", aggregate: true },
+  /**
+   * An array object
+   */
+  array: { id: 3, name: "array", aggregate: true },
+  /**
+   * An array object
+   */
+  array_stream: { id: 4, name: "array_stream", aggregate: true, stream: true },
+  /**
+   * A start marker for the beginning of a deferred sequence
+   */
+  start: { id: 5, name: "start" },
+  /**
+   * A stop marker for the end of a deferred sequence
+   */
+  stop: { id: 6, name: "stop" }
+};
+
+Encoding.immediate_fields = function( keys )
+{
+  return keys.reduce( function( result, key )
+  {
+    result.push( { key: key } );
+    return result;
+  }, [] );
+};
+
+
+Encoding.as_object = function( encodings )
+{
+  return {
+    type: Encoding.type.object,           // Since we're listing fields explicitly, it's a transparent object
+    seq: encodings.reduce(
+      function( result, item )
+      {
+        return result.concat( item );
+      }
+    )
+  };
+};
+
+Encoding.field = function( key, view )
+{
+  return [
+    { key: key, element_view: view }
+  ];
+};
+
+/**
+ * @param {*} [element_view=null]
+ */
+Encoding.array = function( element_view )
+{
+  return {
+    type: Encoding.type.array,
+    element_view: ( arguments.length >= 1 ) ? element_view : null
+  };
+};
+
+/**
+ * @param {*} element_view=null
+ */
+Encoding.array_stream = function( element_view )
+{
+  return {
+    type: Encoding.type.array_stream,
+    element_view: element_view
+  };
+};
+
+exports.Encoding = Encoding;