memo-viz.html

<!doctype html>
<head>
<meta charset="utf-8">
<title>Incremental Packrat Parsing</title>
<link rel="stylesheet" href="third_party/codemirror-5.23.0/lib/codemirror.css">
</head>
<style>
  body {
    color: #333;
    margin: 20px 60px;
    font-family: -apple-system, BlinkMacSystemFont, "Helvetica Neue", sans-serif;
  }
  #editorContainer {
    border: 3px solid transparent;
    font-family: Menlo, Monaco, monospace;
    margin-bottom: 8px;
    transition: border-color .25s ease-in-out;
  }
  #editorContainer.in-progress {
    border: 3px solid #f0f0f0;
  }
  #editorContainer.failed {
    border: 3px solid #D9544F;
  }

  .CodeMirror {
    border: 1px solid #ddd;
    font-family: inherit;
    font-size: 33px;
    height: auto;
  }
  pre.CodeMirror-line {
    padding: 0 1px;
  }
  #memoIndices {
    display: flex;
    font-size: 12px;
    margin: 4px 2px;
  }
  #memoIndices .char {
    background-color: #f0f0f0;
    border: 1px solid #bbb;
    box-sizing: border-box;
    color: #999;
    cursor: default;
    display: inline-block;
    font-size: 9px;
    height: 14px;
    line-height: 14px;
    margin-right: 1px;
    text-align: center;
    width: 19px;
    vertical-align: middle;
  }
  #memoIndices .char:hover {
    background-color: #999;
    border-color: #999;
    color: white;
  }
  #memoEntries {
    padding: 0 3px 6px 3px;
    position: relative;  /* For positioning #stabbedRegion */
  }
  
  .memoContents {
    margin-bottom: 10px;
  }

  .extents {
    display: flex;
    flex-direction: row;
    margin: 1px 0;
    padding: 0 2px;
  }

  .ruleName {
    color: #666;
    /* This must match the font used on `_canvasCtxForMeasuring` below. */
    font: 12px system, -apple-system, BlinkMacSystemFont, "Helvetica Neue", sans-serif;
    white-space: nowrap;
  }

  .matched,
  .examined {
    box-sizing: border-box;
    transition: background-color .25s ease-in-out;
  }
  .matched.velocity-animating,
  .examined.velocity-animating {
    transition: none;
  }

  .matched {
    background-color: #aaa;
  }
  .new .matched {
    background-color: hsl(207, 66%, 59%);
  }
  .examined {
    background-color: #ddd;
  }
  .new .examined {
    background-color: hsla(205, 69%, 49%, 0.3);
  }

  .failed {
    color: #DB524B;
  }
  #stabbedRegion {
    bottom: 0;
    background-color: hsla(245, 72%, 75%, 0.35);
    border: 0 solid hsla(245, 72%, 75%, 0.8);
    box-shadow: 0 1px 3px rgba(255, 255, 255, 0.8);
    box-sizing: border-box;
    position: absolute;
    top: 0;
  }
  #grammar {
    padding-bottom: 20px;
  }
  #grammar > pre {
    font-family: Menlo, Monaco, monospace;
    font-size: 12px;
    margin-left: 20px;
  }
  .breadcrumb {
    background-color: #eceeef;
    border-radius: 4px;
    display: inline-block;
    padding: 12px 16px;
  }
  p {
    line-height: 1.4;
  }
  #content {
    max-width: 960px;
  }
</style>

<div id="content">
  <div class="breadcrumb">&#8249; <a href="https://ohmlang.github.io/sle17/">Incremental Packrat Parsing</a></div>

  <p>The visualization below demonstrates the algorithm presented in <a href="https://ohmlang.github.io/pubs/sle2017/incremental-packrat-parsing.pdf">our SLE'17 paper</a>. It accepts the same rudimentary arithmetic language presented in
    Section 2:
  <div id="grammar">
    <pre>expr = num "+" num
     | num "-" num

num = digit+

digit = "0".."9"</pre>
  </div>

  <div id="main"></div>
</div>

<script src="third_party/codemirror-5.23.0/lib/codemirror.js"></script>
<script src="third_party/velocity-animate-1.4.2.js"></script>
<script src="third_party/vue-2.1.10.js"></script>
<script src="src/standard.js"></script>
<script src="src/incremental.js"></script>

<script>

  // Helpers
  // -------

  const canvasCtxForMeasuring = document.createElement('canvas').getContext('2d');
  canvasCtxForMeasuring.font =
      '12px system, -apple-system, BlinkMacSystemFont, "Helvetica Neue", sans-serif';

  function measureRuleNameText(text) {
    var metrics = canvasCtxForMeasuring.measureText(text);
    return metrics.width + 2;
  }

  function charWidth(count) {
    return (count * 20);
  }

  function assert(cond, optMessage) {
    if (!cond) {
      throw new Error(optMessage || 'assertion failed');
    }
  }

  function filter(list, fn) {
    return Array.prototype.filter.call(list, fn);
  }

  function forEach(list, fn) {
    Array.prototype.forEach.call(list, fn);
  }

  function mapToObj(map, i, h) {
    const ans = Object.create(null);
    if (map) {
      map.forEach((v, k) => ans[k] = v);
    }
    return ans;
  }

  let nextId = 0;
  const extMemoRecs = new WeakMap();

  const posInfoIds = new WeakMap();

  // memo-value
  // ----------

  Vue.component('memo-value', {
    props: {
      val: Object,
      pos: Number,
      selection: Object
    },
    data() {
      return {isNew: true};
    },
    computed: {
      classObj() {
        return {
          invalid: this.isAffected,
          new: this.isNew
        };
      },
      successClass() {
        return this.val.cst == null ? 'failed' : 'succeeded';
      },
      examinedStyle() {
        const matchLen = this.val.cst == null ? 0 : this.val.matchLength;
        return {
          width: charWidth(this.val.examinedLength - matchLen) + 'px'
        };
      },
      matchedStyle() {
        return {
          width: charWidth(this.val.matchLength) + 'px'
        };
      },
      ruleNameStyle() {
        // Use relative positioning to place the label to the left of the bars.
        return {
          position: 'relative',
          left: -measureRuleNameText(this.val.ruleName) - 3 + 'px',
          width: 0
        }
      },
      // Return true if this memo value is (or will be) affected by an edit.
      isAffected() {
        const endPos = this.pos + this.val.examinedLength;
        const selStart = this.selection.start;
        const selEnd = this.selection.end;

        return this.pos < selStart && selStart < endPos ||
               this.pos < selEnd && selEnd < endPos ||
               selStart <= this.pos && endPos <= selEnd;
      }
    },
    template: `
      <div class="extents" :class="classObj">
        <div class="ruleName" :class="successClass" :style="ruleNameStyle">{{ val.ruleName }}</div>
        <div class="matched" :style="matchedStyle"></div>
        <div class="examined" :style="examinedStyle"></div>
      </div>`,
    mounted() {
      this.$el.style.display = 'none';
    },
    beforeUpdate() {
      this.isNew = false;
    }
  });

  // memo-contents
  // -------------

  Vue.component('memo-contents', {
    props: {
      entries: Object,
      pos: Number,
      selection: Object,
    },
    computed: {
      memoValues() {
        const ans = [];
        if (!this.entries) {
          return ans;
        }
        for (let ruleName in this.entries) {
          const memoRec = this.entries[ruleName];

          // Skip 'start', as it's sort of an implementation detail.
          if (ruleName === 'start') {
            continue;
          }

          if (!extMemoRecs.has(memoRec)) {
            const failed = memoRec.cst == null;
            extMemoRecs.set(memoRec, Object.assign({
              id: nextId++,
              ruleName: (failed ? '✗ ' : '') + ruleName,
              matchLength: 0
            }, memoRec));
          }
          ans.push(extMemoRecs.get(memoRec));
        }
        return ans;
      },
      styleObj() {
        return {position: 'relative', left: this.posLeft + 'px'};
      },
      posLeft() {
        return charWidth(this.pos);
      }
    },
    watch: {
      posLeft(newVal, oldVal) {
        this.$emit('beforeTransition', this);
        const tx = oldVal - newVal;
        Velocity(this.$el, {translateX: [0, tx]}, {
          duration: 2000,
          begin: () => this.$el.style.transform = `translateX(${tx}px)`,
          complete: () => this.$emit('completeTransition'),
        });
      }
    },
    template: `
      <div class="memoContents" :style="styleObj">
        <memo-value v-for="val in memoValues" :key="val.id"
                    :val="val" :pos="pos" :selection="selection" />
      </div>`,
  });

  // Root component
  // --------------

  const vm = new Vue({
    el: '#main',
    data: {
      hoveredIdx: -1,
      memoTable: [],
      selection: {start: 0, end: 0},
      activeTransitionCount: 0,
      changeInProgress: false,
      matchSucceeded: false
    },
    computed: {
      classObj() {
        if (this.changeInProgress) {
          return 'in-progress';
        } else if (!this.matchSucceeded) {
          return 'failed';
        }
      },
      stabbedRegionStyle() {
        const selectionSize = this.selection.end - this.selection.start;
        return {
          borderLeftWidth: '2px',
          borderRightWidth: selectionSize === 0 ? '0' : '2px',
          left: charWidth(this.selection.start) + 4 + 'px',
          width: charWidth(selectionSize) + 'px'
        };
      },
    },
    watch: {
      changeInProgress(newVal) {
        // Make the editor read-only whenever a change is in progress.
        this._editor.setOption('readOnly', newVal);
      }
    },
    template: `
      <div id="main">
        <div id="editorContainer" :class="classObj"></div>
        <div id="memoEntries">
          <memo-contents v-for="(data, i) in memoTable" :key="data.key"
              :entries="data.entries"
              :pos="i"
              :selection="selection"
              @beforeTransition="beforeTransition"
              @completeTransition="completeTransition" />
          <div id="stabbedRegion" :style="stabbedRegionStyle"></div>
        </div>
      </div>`,
    methods: {
      beforeTransition() {
        this.activeTransitionCount += 1;
      },
      completeTransition() {
        this.activeTransitionCount -= 1;
      },
      getKey(posInfo) {
        if (posInfo == null) {
          return -1;
        }
        if (posInfoIds.has(posInfo)) {
          return posInfoIds.get(posInfo);
        }
        const id = nextId++;
        posInfoIds.set(posInfo, id);
        return id;
      },
      waitForActiveTransitions(cb) {
        if (this.activeTransitionCount === 0) {
          cb();
        } else {
          const unwatch = this.$watch('activeTransitionCount', (count) => {
            if (count === 0) {
              unwatch();
              cb();
            }
          });
        }
      },
      updateMemoTable() {
        this.memoTable = this._matcher.memoTable.map(v => {
          return {
            entries: mapToObj(v && v.memo),
            key: this.getKey(v && v.memo)
          };
        });
      },

      removeInvalidEntries() {
        const invalidEls = this.$el.querySelectorAll('.invalid');
        if (invalidEls.length === 0) {
          return Promise.resolve();
        }
        Velocity(invalidEls, 'fadeOut', {
          duration: 1500,
          display: 'flex'
        });
        return Velocity(invalidEls, 'slideUp', {
          duration: 1000
        });
      },
      replaceInputRange(from, to, text) {
        return new Promise(cb => {
          this._matcher.applyEdit(from, to, text);
          this.updateMemoTable();
          this._editor.replaceSelection(text);
          Vue.nextTick(cb);
        });
      },
      transitionMovedEntries() {
        return new Promise(this.waitForActiveTransitions);
      },
      matchInput(cb) {
        return new Promise(cb => {
          this.matchSucceeded = this._matcher.match();
          this.updateMemoTable();
          setTimeout(cb, 0);
        });
      },
      transitionNewEntries(optDuration) {
        const duration = typeof optDuration === 'number' ? optDuration : 1000;
        const newEls = this.$el.querySelectorAll('.extents.new');

        Velocity.hook(newEls, 'display', 'flex');
        if (duration === 0 || newEls.length === 0) {
          return Promise.resolve();  // No more work to do.
        }

        Velocity(newEls, 'slideDown', {
          begin: els => Velocity.hook(els, 'opacity', 0),
          duration: duration * 5/6
        });
        return Velocity(newEls, 'fadeIn', {
          duration: duration * 1/6,
          display: 'flex',
          complete: (els) => Velocity.hook(els, 'opacity', '')
        });
      }
    },
    created() {
      var _ = value => new Terminal(value);
      var app = ruleName => new RuleApplication(ruleName);
      var seq = (...exps) => new Sequence(exps);
      var choice = (...exps) => new Choice(exps);
      var rep = exp => new Repetition(exp);
      var not = exp => new Not(exp);

      this._matcher = new Matcher({
        start: app('expr'),
        expr: choice(seq(app('num'), _('+'), app('num')),
                     seq(app('num'), _('-'), app('num'))),
        num: seq(app('digit'), rep(app('digit'))),
        digit: choice(_('0'), _('1'), _('2'), _('3'), _('4'), _('5'), _('6'), _('7'), _('8'), _('9'))
      });
    },
    mounted() {
      const editor = this._editor = CodeMirror(this.$el.querySelector('#editorContainer'));

      // Set an initial value.
      this._matcher.applyEdit(0, 0, '896-7')
      editor.setValue(this._matcher.input);  

      editor.on('beforeChange', (cm, change) => {
        if (!this.changeInProgress) {
          const from = cm.indexFromPos(change.from);
          const to = cm.indexFromPos(change.to);
          const changeText = change.text.join('\n');

          this.changeInProgress = true;
          change.cancel();

          // When the user hits backspace, ensure the selection includes the deleted char.
          if (changeText === '') {
            this._editor.setSelection(change.from, change.to);
          }

          Vue.nextTick()
              .then(() => this.removeInvalidEntries())
              .then(() => this.replaceInputRange(from, to, changeText))
              .then(() => this.transitionMovedEntries())
              .then(() => this.matchInput())
              .then(() => this.transitionNewEntries())
              .then(() => this.changeInProgress = false);
        }
      });
      editor.on('cursorActivity', cm => {
        const sel = cm.listSelections()[0];
        const [start, end] =
            [sel.anchor, sel.head].map(s => cm.indexFromPos(s)).sort();
        this.selection = {start, end};
      });
      editor.focus();

      this.matchInput();
      this.$nextTick(() => this.transitionNewEntries(0));
    },
  });
</script>