Repository: jneen/parsimmon
Pull request #228 (2018-03-07 19:40:56)

Non-byte aligned primitives.
Opening this PR before I begin work so that discussion can reflect over the life of the PR. #224 


Patch:
diff --git a/API.md b/API.md
index afc491d..2cf2af8 100644
--- a/API.md
+++ b/API.md
@@ -424,6 +424,49 @@ parser.parse('accccc');
 //=> {status: true, value: ['a', ['c', 'c', 'c', 'c', 'c']]}
 ```
 
+# Binary constructors.
+
+The purpose of the following constructors is to allow the consumption of Buffer types in node to allow for attoparsec style consumption of binary input.
+As these constructors yield regular values within parsers, they can then be combined in the same fashion as the above string-based constructors to produce
+robust binary parsers.  These constructors live in the Parsimmon.Binary namespace.
+
+## Parsimmon.byte(int)
+
+Returns a parser that yields a byte that matches the given input.  Similar to digit/letter.
+
+```javascript
+var parser = Parsimmon.Binary.byte(0xFF);
+parser.parse(Buffer.from([0xFF]));
+//=> { status: true, value: 255 }
+```
+
+## Parsimmon.bitSeq(alignments)
+
+Specify a series of bit alignments that do not have to be byte aligned and consume them from a buffer.  The bits must
+sum to a byte boundary.
+
+```javascript
+var parser = Parsimmon.Binary.bitSeq([3, 5, 5, 3]);
+parser.parse(Buffer.from([0x04, 0xFF]));
+//=> {status: true, value: [ 0, 4, 31, 7 ]}
+```
+
+## Parsimmon.bitSeqObj(namedAlignments)
+
+Specify a series of bit alignments with names that will output an object with those alignments.  Very similar to seqObj,
+however, but only accepts numeric values.  Will discard unnamed alignments.
+
+```javascript
+var parser = Parsimmon.Binary.bitSeqObj([
+    ["a", 3],
+    5,
+    ["b", 5],
+    ["c", 3]
+]);
+parser.parse(Buffer.from([0x04, 0xFF]));
+//=> { status: true, value: { a: 0, b: 31, c: 7 } }
+```
+
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 
 # Parser methods
diff --git a/package-lock.json b/package-lock.json
index 3739411..19672c3 100644
--- a/package-lock.json
+++ b/package-lock.json
@@ -1,6 +1,6 @@
 {
   "name": "parsimmon",
-  "version": "1.6.2",
+  "version": "1.6.4",
   "lockfileVersion": 1,
   "requires": true,
   "dependencies": {
@@ -1686,15 +1686,6 @@
           "integrity": "sha1-BOaSb2YolTVPPdAVIDYzuFcpfiw=",
           "dev": true
         },
-        "string_decoder": {
-          "version": "1.0.3",
-          "resolved": "https://registry.npmjs.org/string_decoder/-/string_decoder-1.0.3.tgz",
-          "integrity": "sha512-4AH6Z5fzNNBcH+6XDMfA/BTt87skxqJlO0lAh3Dker5zThcAxG6mKz+iGu308UKoPPQ8Dcqx/4JhujzltRa+hQ==",
-          "dev": true,
-          "requires": {
-            "safe-buffer": "5.1.1"
-          }
-        },
         "string-width": {
           "version": "1.0.2",
           "resolved": "https://registry.npmjs.org/string-width/-/string-width-1.0.2.tgz",
@@ -1706,6 +1697,15 @@
             "strip-ansi": "3.0.1"
           }
         },
+        "string_decoder": {
+          "version": "1.0.3",
+          "resolved": "https://registry.npmjs.org/string_decoder/-/string_decoder-1.0.3.tgz",
+          "integrity": "sha512-4AH6Z5fzNNBcH+6XDMfA/BTt87skxqJlO0lAh3Dker5zThcAxG6mKz+iGu308UKoPPQ8Dcqx/4JhujzltRa+hQ==",
+          "dev": true,
+          "requires": {
+            "safe-buffer": "5.1.1"
+          }
+        },
         "strip-ansi": {
           "version": "3.0.1",
           "resolved": "https://registry.npmjs.org/strip-ansi/-/strip-ansi-3.0.1.tgz",
@@ -5013,14 +5013,6 @@
         "xtend": "https://registry.npmjs.org/xtend/-/xtend-4.0.1.tgz"
       }
     },
-    "string_decoder": {
-      "version": "https://registry.npmjs.org/string_decoder/-/string_decoder-1.0.0.tgz",
-      "integrity": "sha1-8G9BFXtmTYYGn4S9vcmw2KsoFmc=",
-      "dev": true,
-      "requires": {
-        "buffer-shims": "https://registry.npmjs.org/buffer-shims/-/buffer-shims-1.0.0.tgz"
-      }
-    },
     "string-width": {
       "version": "https://registry.npmjs.org/string-width/-/string-width-1.0.2.tgz",
       "integrity": "sha1-EYvfW4zcUaKn5w0hHgfisLmxB9M=",
@@ -5031,6 +5023,14 @@
         "strip-ansi": "https://registry.npmjs.org/strip-ansi/-/strip-ansi-3.0.1.tgz"
       }
     },
+    "string_decoder": {
+      "version": "https://registry.npmjs.org/string_decoder/-/string_decoder-1.0.0.tgz",
+      "integrity": "sha1-8G9BFXtmTYYGn4S9vcmw2KsoFmc=",
+      "dev": true,
+      "requires": {
+        "buffer-shims": "https://registry.npmjs.org/buffer-shims/-/buffer-shims-1.0.0.tgz"
+      }
+    },
     "stringstream": {
       "version": "0.0.5",
       "resolved": "https://registry.npmjs.org/stringstream/-/stringstream-0.0.5.tgz",
diff --git a/src/parsimmon.js b/src/parsimmon.js
index 1d9895e..017b19f 100644
--- a/src/parsimmon.js
+++ b/src/parsimmon.js
@@ -9,6 +9,180 @@ function Parsimmon(action) {
 
 var _ = Parsimmon.prototype;
 
+function times(n, f) {
+  var i = 0;
+  for (i; i < n; i++) {
+    f(i);
+  }
+}
+
+function forEach(f, arr) {
+  times(arr.length, function(i) {
+    f(arr[i], i, arr);
+  });
+}
+
+function reduce(f, seed, arr) {
+  forEach(function(elem, i, arr) {
+    seed = f(seed, elem, i, arr);
+  }, arr);
+  return seed;
+}
+
+function map(f, arr) {
+  return reduce(
+    function(acc, elem, i, a) {
+      return acc.concat([f(elem, i, a)]);
+    },
+    [],
+    arr
+  );
+}
+
+function lshiftBuffer(input) {
+  var asTwoBytes = reduce(
+    function(a, v, i, b) {
+      return a.concat(
+        i === b.length - 1
+          ? Buffer.from([v, 0]).readUInt16BE(0)
+          : b.readUInt16BE(i)
+      );
+    },
+    [],
+    input
+  );
+  return Buffer.from(
+    map(function(x) {
+      return ((x << 1) & 0xffff) >> 8;
+    }, asTwoBytes)
+  );
+}
+
+function consumeBitsFromBuffer(n, input) {
+  var state = { v: 0, buf: input };
+  times(n, function() {
+    state = {
+      v: (state.v << 1) | bitPeekBuffer(state.buf),
+      buf: lshiftBuffer(state.buf)
+    };
+  });
+  return state;
+}
+
+function bitPeekBuffer(input) {
+  return input[0] >> 7;
+}
+
+function sum(numArr) {
+  return reduce(
+    function(x, y) {
+      return x + y;
+    },
+    0,
+    numArr
+  );
+}
+
+function find(pred, arr) {
+  return reduce(
+    function(found, elem) {
+      return found || (pred(elem) ? elem : found);
+    },
+    null,
+    arr
+  );
+}
+
+function bufferExists() {
+  return typeof Buffer !== "undefined";
+}
+
+function ensureBuffer() {
+  if (!bufferExists()) {
+    throw new Error(
+      "Buffer global does not exist; please consider using https://github.com/feross/buffer if you are running Parsimmon in a browser."
+    );
+  }
+}
+
+function bitSeq(alignments) {
+  ensureBuffer();
+  var totalBits = sum(alignments);
+  if (totalBits % 8 !== 0) {
+    throw new Error(
+      "The bits [" +
+        alignments.join(", ") +
+        "] add up to " +
+        totalBits +
+        " which is not an even number of bytes; the total should be divisible by 8"
+    );
+  }
+  var bytes = totalBits / 8;
+
+  var tooBigRange = find(function(x) {
+    return x > 48;
+  }, alignments);
+  if (tooBigRange) {
+    throw new Error(
+      tooBigRange + " bit range requested exceeds 48 bit (6 byte) Number max."
+    );
+  }
+
+  return new Parsimmon(function(input, i) {
+    if (bytes + i > input.length) {
+      return makeFailure(i, bytes.toString() + " bytes");
+    }
+    return makeSuccess(
+      i + bytes,
+      reduce(
+        function(acc, bits) {
+          var state = consumeBitsFromBuffer(bits, acc.buf);
+          return {
+            coll: acc.coll.concat(state.v),
+            buf: state.buf
+          };
+        },
+        { coll: [], buf: input },
+        alignments
+      ).coll
+    );
+  });
+}
+
+function bitSeqObj(namedAlignments) {
+  ensureBuffer();
+  var fullAlignments = map(function(pair) {
+    return isArray(pair) ? pair : [null, pair];
+  }, namedAlignments);
+
+  var namesOnly = map(function(pair) {
+    return pair[0];
+  }, fullAlignments);
+  var alignmentsOnly = map(function(pair) {
+    return pair[1];
+  }, fullAlignments);
+
+  return bitSeq(alignmentsOnly).map(function(parsed) {
+    var namedParsed = map(function(name, i) {
+      return [name, parsed[i]];
+    }, namesOnly);
+
+    return reduce(
+      function(obj, kv) {
+        if (kv[0] !== null) {
+          obj[kv[0]] = kv[1];
+        }
+        return obj;
+      },
+      {},
+      namedParsed
+    );
+  });
+}
+
+function toArray(arrLike) {
+  return Array.prototype.slice.call(arrLike);
+}
 // -*- Helpers -*-
 
 function isParser(obj) {
@@ -19,10 +193,9 @@ function isArray(x) {
   return {}.toString.call(x) === "[object Array]";
 }
 
-var hasBuffer = typeof Buffer !== "undefined";
 function isBuffer(x) {
   /* global Buffer */
-  return hasBuffer && Buffer.isBuffer(x);
+  return bufferExists() && Buffer.isBuffer(x);
 }
 
 function makeSuccess(index, value) {
@@ -240,7 +413,7 @@ function seq() {
 function seqObj() {
   var seenKeys = {};
   var totalKeys = 0;
-  var parsers = [].slice.call(arguments);
+  var parsers = toArray(arguments);
   var numParsers = parsers.length;
   for (var j = 0; j < numParsers; j += 1) {
     var p = parsers[j];
@@ -611,7 +784,17 @@ function string(str) {
 }
 
 function byte(b) {
+  ensureBuffer();
   assertNumber(b);
+  if (b > 0xff) {
+    throw new Error(
+      "Value specified to byte constructor (" +
+        b +
+        "=0x" +
+        b.toString(16) +
+        ") is larger in value than a single byte."
+    );
+  }
   var expected = (b > 0xf ? "0x" : "0x0") + b.toString(16);
   return Parsimmon(function(input, i) {
     var head = get(input, i);
@@ -802,7 +985,6 @@ var whitespace = regexp(/\s+/).desc("whitespace");
 Parsimmon.all = all;
 Parsimmon.alt = alt;
 Parsimmon.any = any;
-Parsimmon.byte = byte;
 Parsimmon.createLanguage = createLanguage;
 Parsimmon.custom = custom;
 Parsimmon.digit = digit;
@@ -841,4 +1023,10 @@ Parsimmon.whitespace = whitespace;
 Parsimmon["fantasy-land/empty"] = empty;
 Parsimmon["fantasy-land/of"] = succeed;
 
+Parsimmon.Binary = {
+  bitSeq: bitSeq,
+  bitSeqObj: bitSeqObj,
+  byte: byte
+};
+
 module.exports = Parsimmon;


Test patch:
diff --git a/test/.eslintrc b/test/.eslintrc
index 6b1adcc..7b7df31 100644
--- a/test/.eslintrc
+++ b/test/.eslintrc
@@ -1,13 +1,10 @@
 {
   "env": {
-    "node": true
+    "node": true,
+    "mocha": true
   },
   "globals":{
     "Parsimmon": true,
-    "assert": true,
-    "suite": true,
-    "setup": true,
-    "teardown": true,
-    "test": true
+    "assert": true
   }
 }
diff --git a/test/core/bitSeq.test.js b/test/core/bitSeq.test.js
new file mode 100644
index 0000000..9949d6a
--- /dev/null
+++ b/test/core/bitSeq.test.js
@@ -0,0 +1,45 @@
+"use strict";
+
+describe("bitSeq", function() {
+  it("consumes bits into a sequence from a buffer", function() {
+    var b = Buffer.from([0xff, 0xff]);
+    var p = Parsimmon.Binary.bitSeq([3, 5, 5, 3]);
+    assert.deepEqual(p.parse(b).value, [7, 31, 31, 7]);
+  });
+
+  it("disallows construction of parsers that don't align to byte boundaries", function() {
+    assert.throws(function() {
+      Parsimmon.Binary.bitSeq([1, 2]);
+    }, /add up to 3/);
+  });
+
+  it("fails if requesting too much", function() {
+    var b = Buffer.from([]);
+    var p = Parsimmon.Binary.bitSeq([3, 5, 5, 3]);
+    assert.deepEqual(p.parse(b).expected, ["2 bytes"]);
+  });
+
+  it("throws an exception for too large of a range request", function() {
+    assert.throws(function() {
+      Parsimmon.Binary.bitSeq([1, 2, 4, 49]);
+    }, /49 bit range/);
+  });
+
+  context("Buffer is not present.", function() {
+    var buff;
+    before(function() {
+      buff = global.Buffer;
+      global.Buffer = undefined;
+    });
+
+    after(function() {
+      global.Buffer = buff;
+    });
+
+    it("Disallows construction.", function() {
+      assert.throws(function() {
+        Parsimmon.Binary.bitSeq(0xf);
+      }, /buffer global/i);
+    });
+  });
+});
diff --git a/test/core/bitSeqObj.test.js b/test/core/bitSeqObj.test.js
new file mode 100644
index 0000000..aba0b8d
--- /dev/null
+++ b/test/core/bitSeqObj.test.js
@@ -0,0 +1,55 @@
+"use strict";
+
+describe("bitSeqObj", function() {
+  it("consumes bits into an object from a buffer", function() {
+    var b = Buffer.from([0xff, 0xff]);
+    var p = Parsimmon.Binary.bitSeqObj([
+      ["a", 3],
+      ["b", 5],
+      ["c", 5],
+      ["d", 3]
+    ]);
+    assert.deepEqual(p.parse(b).value, { a: 7, b: 31, c: 31, d: 7 });
+  });
+
+  it("disallows construction of parsers that don't align to byte boundaries", function() {
+    assert.throws(function() {
+      Parsimmon.Binary.bitSeqObj([["a", 1], ["b", 2]]);
+    });
+  });
+
+  it("fails if requesting too much", function() {
+    var b = Buffer.from([]);
+    var p = Parsimmon.Binary.bitSeqObj([
+      ["a", 3],
+      ["b", 5],
+      ["c", 5],
+      ["d", 3]
+    ]);
+    assert.deepEqual(p.parse(b).expected, ["2 bytes"]);
+  });
+
+  it("ignores unnamed ranges", function() {
+    var b = Buffer.from([0xff, 0xff]);
+    var p = Parsimmon.Binary.bitSeqObj([["a", 3], 5, ["c", 5], ["d", 3]]);
+    assert.deepEqual(p.parse(b).value, { a: 7, c: 31, d: 7 });
+  });
+
+  context("Buffer is not present.", function() {
+    var buff;
+    before(function() {
+      buff = global.Buffer;
+      global.Buffer = undefined;
+    });
+
+    after(function() {
+      global.Buffer = buff;
+    });
+
+    it("Disallows construction.", function() {
+      assert.throws(function() {
+        Parsimmon.Binary.bitSeqObj(0xf);
+      }, /buffer global/i);
+    });
+  });
+});
diff --git a/test/core/byte.test.js b/test/core/byte.test.js
index 7516fef..f602abc 100644
--- a/test/core/byte.test.js
+++ b/test/core/byte.test.js
@@ -1,21 +1,45 @@
 "use strict";
 
-suite("byte", function() {
-  test("it matches a buffer byte", function() {
+describe("byte", function() {
+  it("matches a buffer byte", function() {
     var b = Buffer.from([0xf]);
-    var p = Parsimmon.byte(0xf);
+    var p = Parsimmon.Binary.byte(0xf);
     assert.ok(p.parse(b).value);
   });
 
-  test("it formats single digit bytes like 0x0f", function() {
+  it("formats single digit bytes like 0x0f", function() {
     var b = Buffer.from([0xa]);
-    var p = Parsimmon.byte(0xf);
+    var p = Parsimmon.Binary.byte(0xf);
     assert.deepEqual(p.parse(b).expected, ["0x0f"]);
   });
 
-  test("it formats double digit bytes like 0xff", function() {
+  it("formats double digit bytes like 0xff", function() {
     var b = Buffer.from([0x12]);
-    var p = Parsimmon.byte(0xff);
+    var p = Parsimmon.Binary.byte(0xff);
     assert.deepEqual(p.parse(b).expected, ["0xff"]);
   });
+
+  it("disallows larger values than a byte.", function() {
+    assert.throws(function() {
+      Parsimmon.Binary.byte(0xfff);
+    }, /4095=0xfff/);
+  });
+
+  context("Buffer is not present.", function() {
+    var buff;
+    before(function() {
+      buff = global.Buffer;
+      global.Buffer = undefined;
+    });
+
+    after(function() {
+      global.Buffer = buff;
+    });
+
+    it("Disallows construction.", function() {
+      assert.throws(function() {
+        Parsimmon.Binary.byte(0xf);
+      }, /buffer global/i);
+    });
+  });
 });
diff --git a/test/core/parse.test.js b/test/core/parse.test.js
index d4b72a0..2d95cac 100644
--- a/test/core/parse.test.js
+++ b/test/core/parse.test.js
@@ -23,4 +23,13 @@ suite(".parse", function() {
       Parsimmon.of("kaboom").parse();
     });
   });
+
+  context("The input is a buffer.", function() {
+    it("Formats errors correctly.", function() {
+      var parser = Parsimmon.Binary.byte(0);
+      assert.throws(function() {
+        parser.tryParse(Buffer.from([0xf]));
+      }, /at byte/);
+    });
+  });
 });