combo: simple parser combinator library for JavaScript

README

This is `combo.js` as of SourceCred commit fb669962a030, modified to convert
Flow type annotations to comment syntax and to group ES6 exports to the end of
the file (for easier conversion to Node-style `module.exports`). The code of
`combo.js` up to this point in history was written entirely by me. Its tests
still pass.

combo.js

// @flow

// Simple parser combinator library for structured types rather than
// bytestring parsing.

/*::
export type JsonObject =
  | string
  | number
  | boolean
  | null
  | $ReadOnlyArray<JsonObject>
  | {+[string]: JsonObject};

export type ParseResult<+T> =
  | {|+ok: true, +value: T|}
  | {|+ok: false, +err: string|};
*/

class Parser /*:: <+T> */ {
  /*::
  +_f: (JsonObject) => ParseResult<T>;
  // Phantom data for the output type of this parser. Used to more
  // reliably match on parsers at the type level, via `$PropertyType`
  // rather than `$Call`. Not populated at runtime; do not dereference.
  +_phantomT: T;
  */

  constructor(f /*: (JsonObject) => ParseResult<T> */) {
    this._f = f;
  }
  parse(raw /*: JsonObject */) /*: ParseResult<T> */ {
    return this._f(raw);
  }
  parseOrThrow(raw /*: JsonObject */) /*: T */ {
    const result = this.parse(raw);
    if (result.ok) {
      return result.value;
    } else {
      throw new Error(result.err);
    }
  }
}

/*::
// Helper type to extract the underlying type of a parser: for instance,
// `ParserOutput<Parser<string>>` is just `string`.
export type ParserOutput<P: Parser<mixed>> = $PropertyType<P, "_phantomT">;
type ExtractParserOutput = <P: Parser<mixed>>(P) => ParserOutput<P>;
*/

// Helper to make a successful parse result. For readability.
function success /*:: <T> */(t /*: T */) /*: ParseResult<T> */ {
  return {ok: true, value: t};
}

// Helper to make a failed parse result. For readability.
function failure(err /*: string */) /*: ParseResult<empty> */ {
  return {ok: false, err};
}

// Helper to nicely render a JSON object's typename, accounting for
// nulls and arrays.
function typename(x /*: JsonObject*/) /*: string */ {
  if (x === null) {
    return "null";
  }
  if (Array.isArray(x)) {
    return "array";
  }
  return typeof x;
}

const string /*: Parser<string> */ = new Parser((x) => {
  if (typeof x !== "string") {
    return failure("expected string, got " + typename(x));
  }
  return success(x);
});

const number /*: Parser<number> */ = new Parser((x) => {
  if (typeof x !== "number") {
    return failure("expected number, got " + typename(x));
  }
  return success(x);
});

const boolean /*: Parser<boolean> */ = new Parser((x) => {
  if (typeof x !== "boolean") {
    return failure("expected boolean, got " + typename(x));
  }
  return success(x);
});

// Parser that only accepts a literal `null`. (Called `null_` rather
// than `null` to avoid conflicting with keyword.)
const null_ /*: Parser<null> */ = new Parser((x) => {
  if (x !== null) {
    return failure("expected null, got " + typename(x));
  }
  return success(x);
});

// The identity operation: a parser that always succeeds, emitting a
// `JsonObject` (not `any`) with the input. Used when you need a parser
// that matches anything:
//
//    // Accepts an arbitrary heterogeneous array and returns its length
//    C.fmap(C.array(C.raw), (a) => a.length)
//
//    // Accepts a config file with dynamic plugin-specific data
//    C.object({version: string, pluginConfig: C.dict(C.raw)})
//
// To destructure the parsed value dynamically, pair with `fmap`.
const raw /*: Parser<JsonObject> */ = new Parser(success);

// Lift a plain value into a parser that always returns that value,
// ignoring its input.
function pure /*:: <T> */(t /*: T */) /*: Parser<T> */ {
  return new Parser((_) => success(t));
}

// Create a parser that accepts any value from a fixed set. This can be
// used for enumerated values in configs:
//
//    type Environment = "dev" | "prod";
//    const p: C.Parser<Environment> = C.exactly(["dev", "prod"]);
//
// This function only supports value types. Performing an `any`-cast
// guarded by a deep equality check would be unsound, breaking opaque
// type boundaries: e.g., a module could `export opaque type T = {}` and
// provide two constants `ONE = {}` and `TWO = {}` (different objects),
// and then expect that any value of type `T` would be identical to
// either `ONE` or `TWO`. Using strict reference equality for array and
// object types would be sound, but would not usually be what was
// wanted, as it wouldn't match ~any actual output of `JSON.parse`.
function exactly /*:: <T: string | number | boolean | null> */(
  ts /*: $ReadOnlyArray<T> */
) /*: Parser<T> */ {
  return new Parser((x) => {
    for (const t of ts) {
      if (x === t) {
        return success(t);
      }
    }
    const expected /*: string */ =
      ts.length === 1 ? String(ts[0]) : `one of ${JSON.stringify(ts)}`;
    return failure(`expected ${expected}, got ${typename(x)}`);
  });
}

// Transform the output of a parser with a pure function. For instance,
// if `p: Parser<number>` and `f = (n: number) => n % 2 === 0`, then
// `fmap(p, f)` is a `Parser<boolean>` that first uses `p` to parse its
// input to a number and then checks whether the number is even.
//
// If the function `f` throws, the thrown value will be converted to
// string and returned as a parse error. (The string conversion takes
// `e.message` if the thrown value `e` is an `Error`, else just converts
// with the `String` builtin.)
//
// This can be used for "strong validation". If `U` is a (possibly
// opaque) subtype of `T`, and `f: (T) => U` is a checked downcast that
// either returns a `U` or throws an error, then `fmap` can transform a
// `Parser<T>` into a validating `Parser<U>`, where the fact that the
// validation has been performed is encoded at the type level. Thus:
//
//    import * as C from ".../combo";
//    import {NodeAddress, type NodeAddressT} from ".../core/graph";
//
//    const addressParser: Parser<NodeAddressT> =
//      C.fmap(C.array(C.string), NodeAddress.fromParts);
//
// As a degenerate case, it can also be used for "weak validation",
// where the types `T` and `U` are the same and the function `f` simply
// returns its argument or throws, but in this case there is nothing
// preventing a user of a `Parser<T>` from simply forgetting to
// validate. Prefer strong validation when possible.
function fmap /*:: <T, U> */(
  p /*: Parser<T> */,
  f /*: (T) => U */
) /*: Parser<U> */ {
  return new Parser((x) => {
    const maybeT = p.parse(x);
    if (!maybeT.ok) {
      return failure(maybeT.err);
    }
    const t = maybeT.value;
    let u /*: U */;
    try {
      u = f(t);
    } catch (e) {
      if (e instanceof Error) {
        return failure(e.message);
      } else {
        return failure(String(e));
      }
    }
    return success(u);
  });
}

// Create a parser that tries each of the given parsers on the same
// input, taking the first successful parse or failing if all parsers
// fail. In the failure case, the provided `errorFn` will be called with
// the error messages from all the subparsers to form the resulting
// error; the default error function includes the full text of all the
// error messages, but a user-supplied error function may act with
// domain-specific precision.
//
// One use case is for parsing unions, including discriminated unions:
//
//    type Expr =
//      | {|+type: "CONSTANT", +value: number|}
//      | {|+type: "VARIABLE", +name: string|};
//    const exprParser: C.Parser<Expr> = C.orElse([
//      C.fmap(C.number, (value) => ({type: "CONSTANT", value})),
//      C.fmap(C.string, (name) => ({type: "VARIABLE", name})),
//    ]);
//
// Another is to use `pure` to provide a default value:
//
//    const lenientNumber: C.Parser<number | "(unknown)"> = C.orElse([
//      C.number,
//      C.pure("(unknown)"),
//    ]);
//
// This last parser will always succeed, because `C.pure(v)` always
// succeeds and always returns `v`.
function orElse /*:: <T: $ReadOnlyArray<Parser<mixed>>> */(
  parsers /*: T */,
  errorFn /*:: ?: (string[]) => string */ = (errors) =>
    `no parse matched: ${JSON.stringify(errors)}`
) /*: Parser<$ElementType<$TupleMap<T, ExtractParserOutput>, number>> */ {
  return new Parser((x) => {
    const errors = [];
    for (const parser of parsers) {
      const result = parser.parse(x);
      if (result.ok) {
        return success((result.value /*: any */));
      } else {
        errors.push(result.err);
      }
    }
    return failure(errorFn(errors));
  });
}

function array /*:: <T> */(p /*: Parser<T> */) /*: Parser<T[]> */ {
  return new Parser((x) => {
    if (!Array.isArray(x)) {
      return failure("expected array, got " + typename(x));
    }
    const result = Array(x.length);
    for (let i = 0; i < result.length; i++) {
      const raw = x[i];
      const parsed = p.parse(raw);
      if (!parsed.ok) {
        return failure(`index ${i}: ${parsed.err}`);
      }
      result[i] = parsed.value;
    }
    return success(result);
  });
}

/*::
// Fields for an object type. Each is either a bare parser or the result
// of `rename("oldFieldName", p)` for a parser `p`, to be used when the
// field name in the output type is to be different from the field name
// in the input type.
export type Field<+T> = Parser<T> | RenameField<T>;
export opaque type RenameField<+T>: {+_phantomT: T} = RenameFieldImpl<T>;
export type Fields = {+[string]: Field<mixed>};

// Like `ExtractParserOutput`, but works on `Field`s even when the
// bound ascription is checked outside of this module.
type FieldOutput<F: Field<mixed>> = $PropertyType<F, "_phantomT">;
type ExtractFieldOutput = <F: Field<mixed>>(F) => FieldOutput<F>;
*/

function rename /*:: <T> */(
  oldKey /*: string */,
  parser /*: Parser<T> */
) /*: RenameField<T> */ {
  return new RenameFieldImpl(oldKey, parser);
}

class RenameFieldImpl /*:: <+T> */ extends Parser /*:: <T> */ {
  /*:: +oldKey: string; */
  constructor(oldKey /*: string */, parser /*: Parser<T> */) {
    super(parser._f);
    this.oldKey = oldKey;
  }
}

/*::
// Parser combinator for an object type all of whose fields are
// required.
type PObjectAllRequired = <FReq: Fields>(
  required: FReq
) => Parser<$ObjMap<FReq, ExtractFieldOutput>>;

// Parser combinator for an object type with some required fields (maybe
// none) and some optional ones.
type PObjectWithOptionals = <FReq: Fields, FOpt: Fields>(
  required: FReq,
  optional: FOpt
) => Parser<
  $Exact<{
    ...$Exact<$ObjMap<FReq, ExtractFieldOutput>>,
    ...$Rest<$Exact<$ObjMap<FOpt, ExtractFieldOutput>>, {}>,
  }>
>;

// Parser combinator for an object type where all fields are optional.
// Special case of `PObjectWithOptionals`.
type PObjectShape = <FOpt: Fields>(
  optional: FOpt
) => Parser<$Rest<$Exact<$ObjMap<FOpt, ExtractFieldOutput>>, {}>>;

// Parser combinator for an object type with some required fields (maybe
// none) and maybe some optional ones. (This is an intersection type
// rather than a normal function with optional second argument to force
// inference to pick a branch based on arity rather than inferring an
// `empty` type.)
type PObject = PObjectAllRequired & PObjectWithOptionals;
*/

// Create a parser for an object type, with required fields and
// (optionally) optional fields. The returned parser will silently drop
// extraneous fields on values that it parses, to facilitate forward and
// backward compatibility.
const object /*: PObject */ = (function object(
  requiredFields,
  optionalFields /*:: ? */
) {
  const newKeysSeen = new Set();
  const fields /*: Array<{|
    +oldKey: string,
    +newKey: string,
    +required: boolean,
    +parser: Parser<mixed>,
  |}> */ = [];
  const fieldsets = [
    {inputFields: requiredFields, required: true},
    {inputFields: optionalFields || {}, required: false},
  ];
  for (const {inputFields, required} of fieldsets) {
    for (const newKey of Object.keys(inputFields)) {
      const parser = inputFields[newKey];
      if (newKeysSeen.has(newKey)) {
        throw new Error("duplicate key: " + JSON.stringify(newKey));
      }
      newKeysSeen.add(newKey);
      const oldKey = parser instanceof RenameFieldImpl ? parser.oldKey : newKey;
      fields.push({oldKey, newKey, parser, required});
    }
  }
  return new Parser((x) => {
    if (typeof x !== "object" || Array.isArray(x) || x == null) {
      return failure("expected object, got " + typename(x));
    }
    const result = {};
    for (const {oldKey, newKey, parser, required} of fields) {
      const raw = x[oldKey];
      if (raw === undefined) {
        if (required) {
          return failure("missing key: " + JSON.stringify(oldKey));
        } else {
          continue;
        }
      }
      const parsed = parser.parse(raw);
      if (!parsed.ok) {
        return failure(`key ${JSON.stringify(oldKey)}: ${parsed.err}`);
      }
      result[newKey] = parsed.value;
    }
    return success(result);
  });
} /*:: : any */);

// Create a parser for an object type all of whose fields are optional.
// Shorthand for `object` with an empty first argument.
const shape /*: PObjectShape */ = function shape(fields) {
  return object({}, fields);
};

// Create a parser for a tuple: a fixed-length array with possibly
// heterogeneous element types. For instance,
//
//    C.tuple([C.string, C.number, C.boolean])
//
// is a parser that accepts length-3 arrays whose first element is a
// string, second element is a number, and third element is a boolean.
function tuple /*:: <T: Iterable<Parser<mixed>>> */(
  parsers /*: T */
) /*: Parser<$TupleMap<T, ExtractParserOutput>> */ {
  const ps = Array.from(parsers);
  return new Parser((x) => {
    if (!Array.isArray(x)) {
      return failure("expected array, got " + typename(x));
    }
    if (x.length !== ps.length) {
      return failure(`expected array of length ${ps.length}, got ${x.length}`);
    }
    const result = Array(ps.length);
    for (let i = 0; i < result.length; i++) {
      const raw = x[i];
      const parser = ps[i];
      const parsed = parser.parse(raw);
      if (!parsed.ok) {
        return failure(`index ${i}: ${parsed.err}`);
      }
      result[i] = parsed.value;
    }
    return success(result);
  });
}

/*::
// Parser combinator for a dictionary whose keys are arbitrary strings.
type PDictStringKey = <V>(Parser<V>) => Parser<{|[string]: V|}>;
// Parser combinator for a dictionary whose keys are a specified subtype
// of string.
type PDictCustomKey = <V, K: string>(
  Parser<V>,
  Parser<K>
) => Parser<{|[K]: V|}>;
type PDict = PDictStringKey & PDictCustomKey;
*/

// Create a parser for objects with arbitrary string keys and
// homogeneous values. For instance, a set of package versions:
//
//    {"better-sqlite3": "^7.0.0", "react": "^16.13.0"}
//
// might be parsed by the following parser:
//
//    C.dict(C.fmap(C.string, (s) => SemVer.parse(s)))
//
// Objects may have any number of entries, including zero.
//
// An optional second argument may be passed to refine the keys to a
// subtype of `string`, such as an opaque subtype (`NodeAddressT`) or a
// string enum (`"ONE" | "TWO"`). Fails if the key parser gives the same
// output for two distinct keys.
const dict /*: PDict */ = (function dict /*:: <V, K: string> */(
  valueParser,
  keyParser /*: Parser<K> */ = (string /*: any */) // safe when called as `PDict`
) /*: Parser<{[K]: V}> */ {
  return new Parser((x) => {
    if (typeof x !== "object" || Array.isArray(x) || x == null) {
      return failure("expected object, got " + typename(x));
    }
    const rawKeys /*: Map<K, string> */ = new Map();
    const result /*: {|[K]: V|} */ = ({} /*: any */);
    for (const rawKey of Object.keys(x)) {
      const parsedKey = keyParser.parse(rawKey);
      if (!parsedKey.ok) {
        return failure(`key ${JSON.stringify(rawKey)}: ${parsedKey.err}`);
      }
      const oldRawKey = rawKeys.get(parsedKey.value);
      if (oldRawKey != null) {
        const s = JSON.stringify;
        return failure(
          `conflicting keys ${s(oldRawKey)} and ${s(rawKey)} ` +
            `both have logical key ${s(parsedKey.value)}`
        );
      }
      rawKeys.set(parsedKey.value, rawKey);
      const rawValue = x[rawKey];
      const parsedValue = valueParser.parse(rawValue);
      if (!parsedValue.ok) {
        return failure(`value ${JSON.stringify(rawKey)}: ${parsedValue.err}`);
      }
      result[parsedKey.value] = parsedValue.value;
    }
    return success(result);
  });
} /*: any */);

export {
  Parser,
  string,
  number,
  boolean,
  null_,
  raw,
  pure,
  exactly,
  fmap,
  orElse,
  array,
  rename,
  object,
  shape,
  tuple,
  dict,
};

combo.test.js

// @flow

import * as C from "./combo";

describe("src/util/combo", () => {
  describe("type JsonObject", () => {
    it("includes compound structures of strict subtypes", () => {
      // (requires covariance in the array/object clauses)
      (x /*: string[] */) /*: C.JsonObject */ => x;
      (x /*: {[string]: number} */) /*: C.JsonObject */ => x;
    });
  });

  describe("primitives", () => {
    describe("string", () => {
      it("accepts strings", () => {
        expect(C.string.parseOrThrow("hey")).toEqual("hey");
      });
      it("rejects numbers", () => {
        const thunk = () => C.string.parseOrThrow(77);
        expect(thunk).toThrow("expected string, got number");
      });
      it("rejects nulls", () => {
        const thunk = () => C.string.parseOrThrow(null);
        expect(thunk).toThrow("expected string, got null");
      });
    });

    describe("number", () => {
      it("accepts numbers", () => {
        expect(C.number.parseOrThrow(77)).toEqual(77);
      });
      it("rejects strings", () => {
        const thunk = () => C.number.parseOrThrow("hey");
        expect(thunk).toThrow("expected number, got string");
      });
      it("rejects arrays", () => {
        const thunk = () => C.number.parseOrThrow([2, 3, 4]);
        expect(thunk).toThrow("expected number, got array");
      });
      it("rejects strings that look like numbers", () => {
        const thunk = () => C.number.parseOrThrow("77");
        expect(thunk).toThrow("expected number, got string");
      });
    });

    describe("boolean", () => {
      it("accepts true", () => {
        expect(C.boolean.parseOrThrow(true)).toEqual(true);
      });
      it("accepts false", () => {
        expect(C.boolean.parseOrThrow(true)).toEqual(true);
      });
      it("rejects null", () => {
        const thunk = () => C.boolean.parseOrThrow(null);
        expect(thunk).toThrow("expected boolean, got null");
      });
      it("rejects objects", () => {
        const thunk = () => C.boolean.parseOrThrow({});
        expect(thunk).toThrow("expected boolean, got object");
      });
    });

    describe("null_", () => {
      it("accepts null", () => {
        expect(C.null_.parseOrThrow(null)).toEqual(null);
      });
      it("rejects undefined", () => {
        // This is a defense-in-depth test---undefined isn't actually a
        // valid JSON value---so silence Flow's justified complaint.
        const undef /*: C.JsonObject */ = (undefined /*: any */);
        const thunk = () => C.null_.parseOrThrow(undef);
        expect(thunk).toThrow("expected null, got undefined");
      });
      it("rejects falsy strings", () => {
        const thunk = () => C.null_.parseOrThrow("");
        expect(thunk).toThrow("expected null, got string");
      });
      it("rejects falsy numbers", () => {
        const thunk = () => C.null_.parseOrThrow(0);
        expect(thunk).toThrow("expected null, got number");
      });
    });
  });

  describe("raw", () => {
    it("parses strings", () => {
      expect(C.raw.parseOrThrow("hey")).toEqual("hey");
    });
    it("parses numbers", () => {
      expect(C.raw.parseOrThrow(123)).toEqual(123);
    });
    it("parses booleans", () => {
      expect(C.raw.parseOrThrow(true)).toEqual(true);
      expect(C.raw.parseOrThrow(false)).toEqual(false);
    });
    it("parses null", () => {
      expect(C.raw.parseOrThrow(null)).toEqual(null);
    });
    it("parses heterogeneous arrays", () => {
      expect(C.raw.parseOrThrow([1, "two"])).toEqual([1, "two"]);
    });
    it("parses heterogeneous objects", () => {
      const input = {one: 2, three: "five"};
      expect(C.raw.parseOrThrow(input)).toEqual({one: 2, three: "five"});
    });
  });

  describe("pure", () => {
    it("does what it says on the tin", () => {
      /*:: type Color = "RED" | "GREEN" | "BLUE"; */
      const p /*: C.Parser<Color> */ = C.pure("GREEN");
      expect(p.parseOrThrow(p)).toEqual("GREEN");
    });
  });

  describe("exactly", () => {
    it("is type-safe", () => {
      (C.exactly([1, 2, 3]) /*: C.Parser<1 | 2 | 3> */);
      (C.exactly(["one", 2]) /*: C.Parser<"one" | 2> */);
      (C.exactly([]) /*: C.Parser<empty> */);
      // $FlowExpectedError
      (C.exactly([1, 2, 3]) /*: C.Parser<1 | 2> */);
      // $FlowExpectedError
      (C.exactly(["one", 2]) /*: C.Parser<1 | "two"> */);
      // $FlowExpectedError
      (C.exactly([false]) /*: C.Parser<empty> */);
    });
    it("accepts any matching value", () => {
      /*:: type Color = "RED" | "GREEN" | "BLUE"; */
      const p /*: C.Parser<Color> */ = C.exactly(["RED", "GREEN", "BLUE"]);
      expect([p.parse("RED"), p.parse("GREEN"), p.parse("BLUE")]).toEqual([
        {ok: true, value: "RED"},
        {ok: true, value: "GREEN"},
        {ok: true, value: "BLUE"},
      ]);
    });
    it("rejects a non-matching value among multiple alternatives", () => {
      /*:: type Color = "RED" | "GREEN" | "BLUE"; */
      const p /*: C.Parser<Color> */ = C.exactly(["RED", "GREEN", "BLUE"]);
      const thunk = () => p.parseOrThrow("YELLOW");
      expect(thunk).toThrow(
        'expected one of ["RED","GREEN","BLUE"], got string'
      );
    });
    it("rejects a non-matching value from just one option", () => {
      /*:: type Consent = {|+acceptedEula: true|}; */
      const p /*: C.Parser<Consent> */ = C.object({
        acceptedEula: C.exactly([true]),
      });
      const thunk = () => p.parseOrThrow({acceptedEula: false});
      expect(thunk).toThrow("expected true, got boolean");
    });
    it("rejects a non-matching value from no options", () => {
      const p /*: C.Parser<empty> */ = C.exactly([]);
      const thunk = () => p.parseOrThrow("wat");
      expect(thunk).toThrow("expected one of [], got string");
    });
  });

  describe("fmap", () => {
    /*:: type Color = "RED" | "GREEN" | "BLUE"; */
    function stringToColor(s /*: string */) /*: Color */ {
      const c = s.toLowerCase().charAt(0);
      switch (c) {
        case "r":
          return "RED";
        case "g":
          return "GREEN";
        case "b":
          return "BLUE";
        default:
          throw new Error("unknown color: " + JSON.stringify(s));
      }
    }
    it("handles the success case", () => {
      const p /*: C.Parser<Color> */ = C.fmap(C.string, stringToColor);
      expect(p.parseOrThrow("blu")).toEqual("BLUE");
    });
    it("handles failure of the base parser", () => {
      const p /*: C.Parser<Color> */ = C.fmap(C.string, stringToColor);
      const thunk = () => p.parseOrThrow(77);
      expect(thunk).toThrow("expected string, got number");
    });
    it("handles `Error`s thrown by the mapping function", () => {
      const p /*: C.Parser<Color> */ = C.fmap(C.string, stringToColor);
      // Avoid `.toThrow` because that checks for a substring, and we
      // want to ensure no "Error: " prefix is included.
      expect(p.parse("wat")).toEqual({ok: false, err: 'unknown color: "wat"'});
    });
    it("handles failure of the mapping function", () => {
      const p /*: C.Parser<Color> */ = C.fmap(C.string, () => {
        throw 123;
      });
      expect(p.parse("wat")).toEqual({ok: false, err: "123"});
    });
    it("composes", () => {
      const raw /*: C.Parser<string> */ = C.string;
      const trimmed /*: C.Parser<string> */ = C.fmap(raw, (s) => s.trim());
      const color /*: C.Parser<Color> */ = C.fmap(trimmed, stringToColor);
      expect(color.parseOrThrow("  blu\n\n")).toEqual("BLUE");
    });
    it("is type-safe", () => {
      // input safety
      // $FlowExpectedError
      C.fmap(C.string, (n /*: number */) => n.toFixed());
      // output safety
      (C.fmap(C.number, (n /*: number */) =>
        // $FlowExpectedError
        n.toFixed()
      ) /*: C.Parser<number> */);
    });
  });

  describe("orElse", () => {
    it("is type-safe", () => {
      (C.orElse([C.number, C.string]) /*: C.Parser<number | string> */);
      (C.orElse([C.number, C.null_]) /*: C.Parser<number | null> */);
      (C.orElse([C.number, C.null_]) /*: C.Parser<?number> */);
      (C.orElse([C.number, C.null_]) /*: C.Parser<number | null | boolean> */);
      (C.orElse([]) /*: C.Parser<empty> */);
      // $FlowExpectedError
      (C.orElse([C.number, C.string]) /*: C.Parser<number | boolean> */);
      // $FlowExpectedError
      (C.orElse([C.number, C.string]) /*: C.Parser<empty> */);
    });

    it("takes the first alternative if it works", () => {
      const p /*: C.Parser<number | string> */ = C.orElse([C.number, C.string]);
      expect(p.parseOrThrow(123)).toEqual(123);
    });
    it("takes the second alternative if necessary", () => {
      const p /*: C.Parser<number | string> */ = C.orElse([C.number, C.string]);
      expect(p.parseOrThrow("four")).toEqual("four");
    });
    it("takes the first alternative even if both work", () => {
      const p /*: C.Parser<1 | 2> */ = C.orElse([C.pure(1), C.pure(2)]);
      expect(p.parseOrThrow("hmm")).toEqual(1);
    });
    it("permits an empty set of parsers, always rejecting", () => {
      const p /*: C.Parser<empty> */ = C.orElse([]);
      expect(() => p.parseOrThrow("anything")).toThrow("no parse matched: []");
    });

    function extractError(result /*: C.ParseResult<mixed> */) /*: string */ {
      expect(result).toEqual(expect.objectContaining({ok: false}));
      if (result.ok) {
        throw new Error("(unreachable)");
      }
      return result.err;
    }
    function checkPositive(x /*: number */) /*: number */ {
      if (!(x > 0)) throw new Error("not positive");
      return x;
    }
    function checkNegative(x /*: number */) /*: number */ {
      if (!(x < 0)) throw new Error("not negative");
      return x;
    }
    function checkZero(x /*: number */) /*: number */ {
      if (!(x === 0)) throw new Error("not zero");
      return x;
    }

    it("combines error messages with a default combination function", () => {
      const p /*: C.Parser<number> */ = C.orElse([
        C.fmap(C.number, checkPositive),
        C.fmap(C.number, checkNegative),
        C.fmap(C.number, checkZero),
      ]);
      expect(() => p.parseOrThrow(NaN)).toThrow(
        'no parse matched: ["not positive","not negative","not zero"]'
      );
    });
    it("applies a user-specified error combination function", () => {
      const p /*: C.Parser<number> */ = C.orElse(
        [
          C.fmap(C.number, checkPositive),
          C.fmap(C.number, checkNegative),
          C.fmap(C.number, checkZero),
        ],
        (errors) => errors.map((e) => `${e}!`).join(" and ")
      );
      const result = p.parse(NaN);
      const err = extractError(result);
      expect(err).toEqual("not positive! and not negative! and not zero!");
    });
  });

  describe("array", () => {
    it("accepts an empty array", () => {
      const p /*: C.Parser<string[]> */ = C.array(C.string);
      expect(p.parseOrThrow([])).toEqual([]);
    });
    it("accepts a singleton array", () => {
      const p /*: C.Parser<string[]> */ = C.array(C.string);
      expect(p.parseOrThrow(["one"])).toEqual(["one"]);
    });
    it("accepts a long array", () => {
      const p /*: C.Parser<string[]> */ = C.array(C.string);
      expect(p.parseOrThrow(["a", "b", "c"])).toEqual(["a", "b", "c"]);
    });
    it("works for nested array types", () => {
      const p /*: C.Parser<string[][]> */ = C.array(C.array(C.string));
      expect(p.parseOrThrow([["a", "b"], ["c"]])).toEqual([["a", "b"], ["c"]]);
    });
    it("rejects on an object with numeric-string keys", () => {
      const p /*: C.Parser<string[][]> */ = C.array(C.array(C.string));
      const input = {"0": "hmm", "1": "hum"};
      const thunk = () => p.parseOrThrow(input);
      expect(thunk).toThrow("expected array, got object");
    });
    it("rejects arrays with elements of the wrong type", () => {
      const p /*: C.Parser<string[]> */ = C.array(C.string);
      const input = ["one", "two", 5];
      const thunk = () => p.parseOrThrow(input);
      expect(thunk).toThrow("index 2: expected string, got number");
    });
    it("has nice error messages on nested arrays", () => {
      const p /*: C.Parser<string[][]> */ = C.array(C.array(C.string));
      const input = [["one"], ["two"], [5, "---three, sir"]];
      const thunk = () => p.parseOrThrow(input);
      expect(thunk).toThrow("index 2: index 0: expected string, got number");
    });
    it("is type-safe", () => {
      // $FlowExpectedError
      (C.array(C.string) /*: C.Parser<string> */);
      // $FlowExpectedError
      (C.array(C.string) /*: C.Parser<number[]> */);
      // $FlowExpectedError
      (C.array(C.string) /*: C.Parser<string[][]> */);
    });
  });

  describe("object", () => {
    it("type-errors if the unique field doesn't match", () => {
      // $FlowExpectedError
      (C.object({name: C.string}) /*: C.Parser<{|+name: number|}> */);
    });
    it("type-errors if two fields on an object are swapped", () => {
      // $FlowExpectedError
      (C.object({
        name: C.string,
        age: C.number,
      }) /*: C.Parser<{|
        +name: number,
        +age: string,
      |}> */);
    });
    it("type-errors if two optional fields on an object are swapped", () => {
      // $FlowExpectedError
      (C.object(
        {id: C.string},
        {maybeName: C.string, maybeAge: C.number}
      ) /*: C.Parser<{|
        +id: string,
        +maybeName?: number,
        +maybeAge?: string,
      |}> */);
    });
    it("type-errors on bad required fields when optionals present", () => {
      // $FlowExpectedError
      (C.object(
        {name: C.string, age: C.number},
        {hmm: C.boolean}
      ) /*: C.Parser<{|
        +name: number,
        +age: string,
        +hmm?: boolean,
      |}> */);
    });
    it("type-errors on bad required fields when empty optionals present", () => {
      // $FlowExpectedError
      (C.object(
        {name: C.string, age: C.number},
        {}
      ) /*: C.Parser<{|
        +name: number,
        +age: string,
        +hmm?: boolean,
      |}> */);
    });
    it("accepts an object with one field", () => {
      const p /*: C.Parser<{|+name: string|}> */ = C.object({name: C.string});
      expect(p.parseOrThrow({name: "alice"})).toEqual({name: "alice"});
    });
    it("accepts an object with two fields at distinct types", () => {
      const p /*: C.Parser<{|+name: string, +age: number|}> */ = C.object({
        name: C.string,
        age: C.number,
      });
      expect(p.parseOrThrow({name: "alice", age: 42})).toEqual({
        name: "alice",
        age: 42,
      });
    });
    it("ignores extraneous fields on input values", () => {
      const p /*: C.Parser<{|+name: string, +age: number|}> */ = C.object({
        name: C.string,
        age: C.number,
      });
      expect(p.parseOrThrow({name: "alice", age: 42, hoopy: true})).toEqual({
        name: "alice",
        age: 42,
      });
    });
    it("rejects an object with missing fields", () => {
      const p /*: C.Parser<{|+name: string, +age: number|}> */ = C.object({
        name: C.string,
        age: C.number,
      });
      const thunk = () => p.parseOrThrow({name: "alice"});
      expect(thunk).toThrow('missing key: "age"');
    });
    it("rejects an object with fields at the wrong type", () => {
      const p /*: C.Parser<{|+name: string, +age: number|}> */ = C.object({
        name: C.string,
        age: C.number,
      });
      const thunk = () => p.parseOrThrow({name: "alice", age: "secret"});
      expect(thunk).toThrow('key "age": expected number, got string');
    });
    it("rejects arrays", () => {
      const p = C.object({name: C.string});
      const thunk = () => p.parseOrThrow(["alice", "bob"]);
      expect(thunk).toThrow("expected object, got array");
    });
    it("rejects null", () => {
      const p = C.object({name: C.string});
      const thunk = () => p.parseOrThrow(null);
      expect(thunk).toThrow("expected object, got null");
    });
    it("rejects strings", () => {
      const p = C.object({name: C.string});
      const thunk = () => p.parseOrThrow("hmm");
      expect(thunk).toThrow("expected object, got string");
    });
    describe("for objects with some required and some optional fields", () => {
      const p /*: C.Parser<{|
        +rs: string,
        +rn: number,
        +os?: string,
        +on?: number,
      |}> */ = C.object(
        {rs: C.string, rn: C.number},
        {os: C.string, on: C.number}
      );
      it("accepts values with none of the optional fields", () => {
        const v = {rs: "a", rn: 1};
        expect(p.parseOrThrow(v)).toEqual(v);
      });
      it("accepts values with a strict subset of the optional fields", () => {
        const v = {rs: "a", rn: 1, on: 9};
        expect(p.parseOrThrow(v)).toEqual(v);
      });
      it("accepts values with all the optional fields", () => {
        const v = {rs: "a", rn: 1, os: "z", on: 9};
        expect(p.parseOrThrow(v)).toEqual(v);
      });
    });
    describe("with field renaming", () => {
      const p /*: C.Parser<{|
        +one: number,
        +two: number,
        +three?: number,
        +four?: number,
      |}> */ = C.object(
        {one: C.number, two: C.rename("dos", C.number)},
        {three: C.number, four: C.rename("cuatro", C.number)}
      );
      it("renames both required and optional fields", () => {
        expect(p.parseOrThrow({one: 1, dos: 2, three: 3, cuatro: 4})).toEqual({
          one: 1,
          two: 2,
          three: 3,
          four: 4,
        });
      });
      it("provides missing key errors using the user-facing name", () => {
        const thunk = () => p.parseOrThrow({one: 1, cuatro: 4});
        expect(thunk).toThrow('missing key: "dos"');
      });
      it("only accepts the user-facing keys", () => {
        const thunk = () => p.parseOrThrow({one: 1, two: 2});
        expect(thunk).toThrow('missing key: "dos"');
      });
      it("only accepts the user-facing keys for optionals", () => {
        expect(p.parseOrThrow({one: 1, dos: 2, three: 3, four: 4})).toEqual({
          one: 1,
          two: 2,
          three: 3,
        });
      });
      it("allows mapping one old key to multiple new keys", () => {
        // This makes it a bit harder to see how to turn `object` into
        // an iso, but it's the intended behavior for now, so let's test
        // it.
        const p /*: C.Parser<{|
          +value: number,
          +valueAsString: string,
        |}> */ = C.object(
          {
            value: C.number,
            valueAsString: C.rename(
              "value",
              C.fmap(C.number, (n) => n.toFixed())
            ),
          }
        );
        expect(p.parseOrThrow({value: 7})).toEqual({
          value: 7,
          valueAsString: "7",
        });
      });
    });
    it("fails when `required` and `optional` have overlapping new keys", () => {
      expect(() => {
        // ...even if the parser types are compatible and the old keys
        // are different
        C.object({hmm: C.string}, {hmm: C.rename("hum", C.string)});
      }).toThrow('duplicate key: "hmm"');
    });
    it("doesn't type a rename as a parser", () => {
      // In the (current) implementation, a `C.rename(...)` actually is
      // a parser, for weird typing reasons. This test ensures that that
      // implementation detail doesn't leak past the opaque type
      // boundary.
      const rename = C.rename("old", C.string);
      // $FlowExpectedError
      (rename /*: C.Parser<string> */);
    });
    it("forbids renaming a rename at the type level", () => {
      // $FlowExpectedError
      C.rename("hmm", C.rename("old", C.string));
    });
  });

  describe("shape", () => {
    // Light test; this is a special case of `object`.
    it("works for normal and renamed fields", () => {
      const p /*: C.Parser<{|
        +one?: number,
        +two?: number,
        +three?: number,
        +four?: number,
      |}> */ = C.shape(
        {
          one: C.number,
          two: C.rename("dos", C.number),
          three: C.number,
          four: C.rename("cuatro", C.number),
        }
      );
      expect(p.parseOrThrow({one: 1, dos: 2})).toEqual({one: 1, two: 2});
    });
    it("type-errors if the output has any required fields", () => {
      const _ /*: C.Parser<{|
        +a?: null,
        +b: null, // bad
        // $FlowExpectedError
      |}> */ = C.shape(
        {
          a: C.null_,
          b: C.null_,
        }
      );
    });
  });

  describe("tuple", () => {
    describe("for an empty tuple type", () => {
      const makeParser = () /*: C.Parser<[]> */ => C.tuple([]);
      it("accepts an empty array", () => {
        const p /*: C.Parser<[]> */ = makeParser();
        expect(p.parseOrThrow([])).toEqual([]);
      });
      it("rejects a non-empty array", () => {
        const p /*: C.Parser<[]> */ = makeParser();
        const thunk = () => p.parseOrThrow([1, 2, 3]);
        expect(thunk).toThrow("expected array of length 0, got 3");
      });
    });
    describe("for a heterogeneous tuple type", () => {
      it("is typesafe", () => {
        (C.tuple([C.string, C.number]) /*: C.Parser<[string, number]> */);
        // $FlowExpectedError
        (C.tuple([C.string, C.number]) /*: C.Parser<[string, string]> */);
      });
      const makeParser = () /*: C.Parser<[string, number]> */ =>
        C.tuple([C.fmap(C.string, (s) => s + "!"), C.number]);
      it("rejects a non-array", () => {
        const p /*: C.Parser<[string, number]> */ = makeParser();
        const thunk = () => p.parseOrThrow({hmm: "hum"});
        expect(thunk).toThrow("expected array, got object");
      });
      it("rejects an empty array", () => {
        const p /*: C.Parser<[string, number]> */ = makeParser();
        const thunk = () => p.parseOrThrow([]);
        expect(thunk).toThrow("expected array of length 2, got 0");
      });
      it("rejects an array of proper length but bad values", () => {
        const p /*: C.Parser<[string, number]> */ = makeParser();
        const thunk = () => p.parseOrThrow(["one", "two"]);
        expect(thunk).toThrow("index 1: expected number, got string");
      });
      it("accepts a properly typed input", () => {
        const p /*: C.Parser<[string, number]> */ = makeParser();
        expect(p.parseOrThrow(["one", 23])).toEqual(["one!", 23]);
      });
    });
  });

  describe("dict", () => {
    const makeParser = () /*: C.Parser<{|[string]: number|}> */ =>
      C.dict(C.number);
    it("is type-safe", () => {
      // when no key parser is given, key type must be string
      // $FlowExpectedError
      (C.dict(C.string) /*: C.Parser<{["hmm"]: string}> */);
    });
    it("rejects null", () => {
      const p = makeParser();
      const thunk = () => p.parseOrThrow(null);
      expect(thunk).toThrow("expected object, got null");
    });
    it("rejects arrays", () => {
      const p = makeParser();
      const thunk = () => p.parseOrThrow([1, 2, 3]);
      expect(thunk).toThrow("expected object, got array");
    });
    it("accepts an empty object", () => {
      const p = makeParser();
      expect(p.parseOrThrow({})).toEqual({});
    });
    it("accepts an object with one entries", () => {
      const p = makeParser();
      expect(p.parseOrThrow({one: 1})).toEqual({one: 1});
    });
    it("accepts an object with multiple entries", () => {
      const p = makeParser();
      const input = {one: 1, two: 2, three: 3};
      expect(p.parseOrThrow(input)).toEqual({one: 1, two: 2, three: 3});
    });
    it("rejects an object with bad values", () => {
      const p = makeParser();
      const thunk = () => p.parseOrThrow({one: "two?"});
      expect(thunk).toThrow('value "one": expected number, got string');
    });
    describe("with custom key parser", () => {
      /*:: type Color = "RED" | "GREEN" | "BLUE"; */
      const color /*: C.Parser<Color> */ = C.fmap(C.string, (x) => {
        x = x.toUpperCase();
        if (x === "RED" || x === "GREEN" || x === "BLUE") {
          return x;
        }
        throw new Error(`bad color: ${x}`);
      });
      it("accepts an object", () => {
        const p /*: C.Parser<{[Color]: number}> */ = C.dict(C.number, color);
        const input = {red: 1, green: 2};
        expect(p.parseOrThrow(input)).toEqual({RED: 1, GREEN: 2});
      });
      it("rejects unparseable keys", () => {
        const p /*: C.Parser<{[Color]: number}> */ = C.dict(C.number, color);
        const input = {yellow: 777};
        const thunk = () => p.parseOrThrow(input);
        expect(thunk).toThrow('key "yellow": bad color: YELLOW');
      });
      it("rejects conflicting keys", () => {
        const p /*: C.Parser<{[Color]: number}> */ = C.dict(C.number, color);
        const input = {rEd: 1, ReD: 2};
        const thunk = () => p.parseOrThrow(input);
        expect(thunk).toThrow(
          'conflicting keys "rEd" and "ReD" both have logical key "RED"'
        );
      });
      it("is type-safe", () => {
        // key type must be string subtype
        const asciiNumber /*: C.Parser<number> */ = C.fmap(C.string, (x) =>
          parseInt(x, 10)
        );
        // $FlowExpectedError
        C.dict(C.boolean, asciiNumber);
      });
    });
  });
});