attoparsec.ts

export type State<Source> = {
  source: Source;
  position: number;
  completed: boolean;
};

export function State<Source>(
  source: Source,
  position?: number
): State<Source> {
  if (position == null) {
    position = 0;
  }
  return { source, position, completed: false };
}

export type DState = State<DataView>;
export type SState = State<string>;

export type Result<Source, FinalValue> =
  | {
      tag: "fail";
      rest: { source: Source; position: number }[];
      traceback: string[];
      message: string;
    }
  | { tag: "partial"; cont: (s: Source) => Result<Source, FinalValue> }
  | {
      tag: "done";
      rest: { source: Source; position: number }[];
      value: FinalValue;
    };

export type Parser<Source, Value, FinalValue = Value> = (
  s: State<Source>,
  failure: FailureCont<Source, FinalValue>,
  success: SuccessCont<Source, Value, FinalValue>
) => Result<Source, FinalValue>;

export type DParser<Value, FinalValue = Value> = Parser<
  DataView,
  Value,
  FinalValue
>;
export type SParser<Value, FinalValue = Value> = Parser<
  string,
  Value,
  FinalValue
>;

export function failK<Source, FinalValue>(
  { source, position }: State<Source>,
  traceback: string[],
  message: string
): Result<Source, FinalValue> {
  return { tag: "fail", rest: [{ source, position }], traceback, message };
}

export function successK<Source, Value>(
  { source, position }: State<Source>,
  value: Value
): Result<Source, Value> {
  return { tag: "done", rest: [{ source, position }], value };
}

export function parse<Source, Value>(
  p: Parser<Source, Value, Value>,
  source: Source
): Result<Source, Value> {
  return p(State(source), failK, successK);
}

export function feed<Source, Value, FinalValue>(
  result: Result<Source, FinalValue>,
  source: Source
) {
  switch (result.tag) {
    case "fail": {
      const { rest } = result;
      return {
        ...result,
        rest: [...rest, { source, position: 0 }]
      };
    }
    case "partial": {
      const { cont } = result;
      return cont(source);
    }
    case "done": {
      const { rest } = result;
      return {
        ...result,
        rest: [...rest, { source, position: 0 }]
      };
    }
    default:
      throw Error(`invalid Result: ${result}`);
  }
}

export function pure<Source, Value, FinalValue>(
  a: Value
): Parser<Source, Value, FinalValue> {
  return (state, failure, success) => {
    return success(state, a);
  };
}

export function mempty<Source, Value, FinalValue>(
  err: string
): Parser<Source, Value, FinalValue> {
  return (state: State<Source>, failure, success) => {
    return failure(state, [], `Failed reading: ${err}`);
  };
}

export function mappend<Source, Value, FinalValue>(
  a: Parser<Source, Value, FinalValue>,
  b: Parser<Source, Value, FinalValue>
): Parser<Source, Value, FinalValue> {
  return (s: State<Source>, failure, success) => {
    const newFailure = (
      { source, position: _p, completed }: State<Source>,
      _c: string[],
      _m: string
    ) => b({ source, position: s.position, completed }, failure, success);
    return a(s, newFailure, success);
  };
}

export function fmap<Source, ValueA, ValueB, FinalValue>(
  fn: (a: ValueA) => ValueB,
  p: Parser<Source, ValueA, FinalValue>
): Parser<Source, ValueB, FinalValue> {
  return (state: State<Source>, failure, success) => {
    const newSuccess = (s: State<Source>, a: ValueA) => success(s, fn(a));
    return p(state, failure, newSuccess);
  };
}

export function ap<Source, ValueA, ValueB, FinalValue>(
  atob: Parser<Source, (a: ValueA) => ValueB, FinalValue>,
  a: Parser<Source, ValueA, FinalValue>
): Parser<Source, ValueB, FinalValue> {
  return mbind(atob, f => mbind(a, x => pure(f(x))));
}

export function mbind<Source, ValueA, ValueB, FinalValue>(
  m: Parser<Source, ValueA, FinalValue>,
  k: (a: ValueA) => Parser<Source, ValueB, FinalValue>
): Parser<Source, ValueB, FinalValue> {
  return (state: State<Source>, failure, success) => {
    const newSuccess = (s: State<Source>, a: ValueA) =>
      k(a)(s, failure, success);
    return m(state, failure, newSuccess);
  };
}

type SuccessCont<Source, Value, FinalValue> = (
  s: State<Source>,
  a: Value
) => Result<Source, FinalValue>;

type FailureCont<Source, FinalValue> = (
  s: State<Source>,
  traceback: string[],
  message: string
) => Result<Source, FinalValue>;

export function skip<Source, FinalValue>(
  count: number
): Parser<Source, undefined, FinalValue> {
  return (state, failure, success) => {
    const { position } = state;
    return success({ ...state, position: position + count }, undefined);
  };
}

export function string<FinalValue>(s: string): SParser<string, FinalValue> {
  return (state, failure, success) => {
    const { source, position } = state;
    const sub = source.slice(position, position + s.length);
    if (sub === s) {
      return success({ ...state, position: position + s.length }, s);
    } else {
      return failure(
        state,
        [],
        `Expected: ${s}, Actual: ${source.slice(position, position + s.length)}`
      );
    }
  };
}

export function cons<T>(x: T) {
  return (xs: T[]) => [x, ...xs];
}

export function many<Source, Value, FinalValue>(
  p: Parser<Source, Value, FinalValue>
): Parser<Source, Value[], FinalValue> {
  const manyP = (): Parser<Source, Value[], FinalValue> =>
    mappend(someP(), pure([]));
  const someP = (): Parser<Source, Value[], FinalValue> => {
    return mbind(p, v => fmap(cons(v), manyP()));
  };
  return manyP();
}

export function many1<Source, Value, FinalValue>(
  p: Parser<Source, Value, FinalValue>
): Parser<Source, Value[], FinalValue> {
  return ap(fmap((v: Value) => cons(v), p), many(p));
}

{
  const hello: SParser<string> = mbind(string("He"), he =>
    mbind(many1(string("l")), ll => mappend(string("!"), string("o")))
  );
  const comma: SParser<string> = fmap(
    ss => ss.join(""),
    mbind(string(","), c => many(string(" ")))
  );
  const world: SParser<string> = mappend(string("world!"), string("世界！"));
  const parseTest = (s: string) => {
    const result = parse(mbind(hello, () => mbind(comma, () => world)), s);
    console.log(s, result.tag);
  };

  parseTest("Hello, world!");
  parseTest("Hello, 世界！");
  parseTest("Hello,world!");
  parseTest("Hello,     world!");
  parseTest("Heo, world!");
  parseTest("Helllllo, world!");
}