text: 'use strict';
  
  // --------------------------------------------------------------------
  // Imports
  // --------------------------------------------------------------------
  
  var Interval = require('./Interval');
  var common = require('./common');
  
  // --------------------------------------------------------------------
  // Private stuff
  // --------------------------------------------------------------------
  
  // Unicode characters that are used in the `toString` output.
  var BALLOT_X = '\u2717';
  var CHECK_MARK = '\u2713';
  var DOT_OPERATOR = '\u22C5';
  var RIGHTWARDS_DOUBLE_ARROW = '\u21D2';
  var SYMBOL_FOR_HORIZONTAL_TABULATION = '\u2409';
  var SYMBOL_FOR_LINE_FEED = '\u240A';
  var SYMBOL_FOR_CARRIAGE_RETURN = '\u240D';
  
  var Flags = {
    succeeded: 1 << 0,
    isRootNode: 1 << 1,
    isImplicitSpaces: 1 << 2,
    isMemoized: 1 << 3,
    isHeadOfLeftRecursion: 1 << 4,
    terminatesLR: 1 << 5
  };
  
  function spaces(n) {
    return common.repeat(' ', n).join('');
  }
  
  // Return a string representation of a portion of `input` at offset `pos`.
  // The result will contain exactly `len` characters.
  function getInputExcerpt(input, pos, len) {
    var excerpt = asEscapedString(input.slice(pos, pos + len));
  
    // Pad the output if necessary.
    if (excerpt.length < len) {
      return excerpt + common.repeat(' ', len - excerpt.length).join('');
    }
    return excerpt;
  }
  
  function asEscapedString(obj) {
    if (typeof obj === 'string') {
      // Replace non-printable characters with visible symbols.
      return obj
          .replace(/ /g, DOT_OPERATOR)
          .replace(/\t/g, SYMBOL_FOR_HORIZONTAL_TABULATION)
          .replace(/\n/g, SYMBOL_FOR_LINE_FEED)
          .replace(/\r/g, SYMBOL_FOR_CARRIAGE_RETURN);
    }
    return String(obj);
  }
  
  // ----------------- Trace -----------------
  
  function Trace(input, pos1, pos2, expr, succeeded, bindings, optChildren) {
    this.input = input;
    this.pos = this.pos1 = pos1;
    this.pos2 = pos2;
    this.source = new Interval(input, pos1, pos2);
    this.expr = expr;
    this.bindings = bindings;
    this.children = optChildren || [];
    this.terminatingLREntry = null;
  
    this._flags = succeeded ? Flags.succeeded : 0;
  }
  
  // A value that can be returned from visitor functions to indicate that a
  // node should not be recursed into.
  Trace.prototype.SKIP = {};
  
  Object.defineProperty(Trace.prototype, 'displayString', {
    get: function() { return this.expr.toDisplayString(); }
  });
  
  // For convenience, create a getter and setter for the boolean flags in `Flags`.
  Object.keys(Flags).forEach(function(name) {
    var mask = Flags[name];
    Object.defineProperty(Trace.prototype, name, {
      get: function() {
        return (this._flags & mask) !== 0;
      },
      set: function(val) {
        if (val) {
          this._flags |= mask;
        } else {
          this._flags &= ~mask;
        }
      }
    });
  });
  
  Trace.prototype.clone = function() {
    return this.cloneWithExpr(this.expr);
  };
  
  Trace.prototype.cloneWithExpr = function(expr) {
    var ans = new Trace(
        this.input, this.pos, this.pos2, expr, this.succeeded, this.bindings, this.children);
  
    ans.isHeadOfLeftRecursion = this.isHeadOfLeftRecursion;
    ans.isImplicitSpaces = this.isImplicitSpaces;
    ans.isMemoized = this.isMemoized;
    ans.isRootNode = this.isRootNode;
    ans.terminatesLR = this.terminatesLR;
    ans.terminatingLREntry = this.terminatingLREntry;
    return ans;
  };
  
  // Record the trace information for the terminating condition of the LR loop.
  Trace.prototype.recordLRTermination = function(ruleBodyTrace, value) {
    this.terminatingLREntry =
        new Trace(this.input, this.pos, this.pos2, this.expr, false, [value], [ruleBodyTrace]);
    this.terminatingLREntry.terminatesLR = true;
  };
  
  // Recursively traverse this trace node and all its descendents, calling a visitor function
  // for each node that is visited. If `vistorObjOrFn` is an object, then its 'enter' property
  // is a function to call before visiting the children of a node, and its 'exit' property is
  // a function to call afterwards. If `visitorObjOrFn` is a function, it represents the 'enter'
  // function.
  //
  // The functions are called with three arguments: the Trace node, its parent Trace, and a number
  // representing the depth of the node in the tree. (The root node has depth 0.) `optThisArg`, if
  // specified, is the value to use for `this` when executing the visitor functions.
  Trace.prototype.walk = function(visitorObjOrFn, optThisArg) {
    var visitor = visitorObjOrFn;
    if (typeof visitor === 'function') {
      visitor = {enter: visitor};
    }
  
    function _walk(node, parent, depth) {
      var recurse = true;
      if (visitor.enter) {
        if (visitor.enter.call(optThisArg, node, parent, depth) === Trace.prototype.SKIP) {
          recurse = false;
        }
      }
      if (recurse) {
        node.children.forEach(function(child) {
          _walk(child, node, depth + 1);
        });
        if (visitor.exit) {
          visitor.exit.call(optThisArg, node, parent, depth);
        }
      }
    }
    if (this.isRootNode) {
      // Don't visit the root node itself, only its children.
      this.children.forEach(function(c) { _walk(c, null, 0); });
    } else {
      _walk(this, null, 0);
    }
  };
  
  // Return a string representation of the trace.
  // Sample:
  //     12⋅+⋅2⋅*⋅3 ✓ exp ⇒  "12"
  //     12⋅+⋅2⋅*⋅3   ✓ addExp (LR) ⇒  "12"
  //     12⋅+⋅2⋅*⋅3       ✗ addExp_plus
  Trace.prototype.toString = function() {
    var sb = new common.StringBuffer();
    this.walk(function(node, parent, depth) {
      if (!node) {
        return this.SKIP;
      }
      var ctorName = node.expr.constructor.name;
      // Don't print anything for Alt nodes.
      if (ctorName === 'Alt') {
        return;  // eslint-disable-line consistent-return
      }
      sb.append(getInputExcerpt(node.input, node.pos, 10) + spaces(depth * 2 + 1));
      sb.append((node.succeeded ? CHECK_MARK : BALLOT_X) + ' ' + node.displayString);
      if (node.isHeadOfLeftRecursion) {
        sb.append(' (LR)');
      }
      if (node.succeeded) {
        var contents = asEscapedString(node.source.contents);
        sb.append(' ' + RIGHTWARDS_DOUBLE_ARROW + '  ');
        sb.append(typeof contents === 'string' ? '"' + contents + '"' : contents);
      }
      sb.append('\n');
    }.bind(this));
    return sb.contents();
  };
  
  // --------------------------------------------------------------------
  // Exports
  // --------------------------------------------------------------------
  
  module.exports = Trace;
  