Special linked list for micromark

README.md

micromark has slow postprocessing. This is caused by intensive splice operations over big array.

This linked list implements basic array api and wraps processing events.

Micromarc postprocess should be changed to

import { subtokenize } from 'micromark-util-subtokenize';
import {link, values} from '../../../linked-list.js'

export function postprocess(events) {
  events = link(events)
  while (!subtokenize(events)) {// Empty
  }
  return values(events)


  return events;
}

and micromark-util-chunked shold be changes to:

...
remove = remove > 0 ? remove : 0

if (list.proxy) {
    if (items.proxy) {
      list.splice(start, remove, items);
    } else {
      list.splice(start, remove, ...items);
    }
} else if (items.length < constants.v8MaxSafeChunkSize) {
...

linked-list.js

export function link(events, noproxy) {
  const state = State(events.length);

  if (events.length) {
    state.head = point(events[0]);

    let index = 1;
    let current = state.head;
    while (index < events.length) {
      current.next = point(events[index], current);
      current = current.next;
      index++;
    }

    state.tail = current;
  }

  if (noproxy) {
    return state;
  }

  return proxy(state);
}

function State(length) {
  const state = {
    length: length,
    head: null,
    tail: null,
    cursors: null,
    methods: {
      unshift(...args) {
        const items = args[0].proxy ? args[0].proxy : link(args).proxy;

        connectp(items.tail, state.head);
        state.head = items.head;
        state.length += items.length;
        if (state.cursor) {
          state.cursor.position += items.length;
        }

        return state.length;
      },

      push(...args) {
        const items = args[0].proxy ? args[0].proxy : link(args).proxy;

        connect(state, items);

        return state.length;
      },

      pop() {
        if (state.length === 0) {
          return undefined;
        } else if (state.length === 1) {
          const value = state.tail.value;

          state.tail = state.head = null;
          state.length = 0;
          state.cursor = null;

          return value;
        } else {
          const tail = state.tail;

          state.tail = state.tail.prev;
          state.tail.next = null;
          state.length -= 1;

          if (state.cursor) {
            if (state.cursor === state.tail) {
              state.cursor = null;
            }
          }

          return tail.value;
        }
      },

      shift() {
        if (state.length === 0) {
          return undefined;
        } else if (state.length === 1) {
          const value = state.head.value;

          state.head = state.tail = null;
          state.length = 0;
          state.cursor = null;

          return value;
        } else {
          const head = state.head;

          state.head = state.head.next;
          state.head.prev = null;
          state.length -= 1;

          if (state.cursor) {
            if (state.cursor === state.head) {
              state.cursor = null;
            } else {
              state.cursor.position -= 1;
            }
          }

          return head.value;
        }
      },

      concat(...args) {
        const list = copy(state);

        for (const part of args) {
          list.methods.push(link(part));
        }

        return proxy(list);
      },

      slice(...args) {
        const from = args.length > 0 ? args[0] : 0;
        const to = args.length > 1 ? args[1] : state.length;
        const start = Math.max(from < 0 ? state.length + from : from, 0);
        const end = Math.min(to < 0 ? state.length + to : to, state.length);

        return proxy(copy(state, start, end - start));
      },

      splice(from, remove, ...insert) {
        if (insert[0].proxy) {
          insert = insert[0];
        } else {
          insert = link(insert);
        }

        // console.log(from, remove, insert.length);
        if (from >= state.length) {
          if (insert.length) {
            state.methods.push(insert);
          }

          return proxy(copy(state, -1, 0));
        }

        const start = Math.max(from < 0 ? state.length + from : from, 0);
        const end = Math.min(start + remove, state.length);
        const rest = copy(state, start, end - start);

        const Head = Symbol('head');
        const Tail = Symbol('tail');

        state.methods.unshift(Head);
        state.methods.push(Tail);

        const startp = index(state, start, true);
        const endp = index(state, end + 1, true);

        // state.cursors.length = 0;

        if (end - start) {
          state.cursor = { position: start, point: startp };
          connectp(startp, endp);
          state.length -= end - start;
        }

        if (insert.length) {
          const part = insert.proxy;
          connectp(startp, part.head);
          connectp(part.tail, endp);

          state.length += part.length;
        }

        state.methods.pop();
        state.methods.shift();

        return proxy(rest);
      }
    }
  };

  return state;
}

function proxy(state) {
  return new Proxy(state, { get });
}

function get(target, prop) {
  if (typeof prop === 'symbol') {
    console.log(prop, new Error().stack);
    return;
  }

  if (!Number.isNaN(Number(prop))) {
    return index(target, prop);
  }

  if (prop === 'length') {
    return target.length;
  }

  if (prop === 'proxy') {
    return target;
  }

  if (prop in target.methods) {
    return target.methods[prop];
  }

  throw new TypeError('Unknown prop');
}

function copy(list, from = 0, count = list.length - from) {
  const state = State(count);
  const head = count && index(list, from, true);

  if (head) {
    state.head = point(head.value);

    let lpoint = head.next;
    let rpoint = state.head;
    while (lpoint && --count) {
      rpoint.next = point(lpoint.value, rpoint);
      lpoint = lpoint.next;
      rpoint = rpoint.next;
    }

    state.tail = rpoint;
  }

  return state;
}

function index(state, prop, noproxy) {
  prop = Number(prop);

  const head = state.head;
  const tail = state.tail;

  if (prop < 0 || prop >= state.length) {
    return undefined;
  }

  if (prop === 0) {
    return head ? noproxy ? head : head.value : undefined;
  }

  if (prop === state.length - 1) {
    return tail ? noproxy ? tail : tail.value : undefined;
  }

  let cursor = state.cursor || { position: -1 };
  if (Math.abs(prop) < Math.abs(cursor.position - prop)) {
    cursor = { position: 0, point: head };
  }
  if (Math.abs(state.length - 1 - prop) < Math.abs(cursor.position - prop)) {
    cursor = { position: state.length - 1, point: tail };
  }

  const delta = cursor.position - prop;

  let point = cursor.point;
  if (delta) {
    const direction = delta < 0 ? 'next' : 'prev';

    let steps = Math.abs(delta);
    while (steps-- && point) {
      point = point[direction];
    }

    if (point && point !== state.head && point !== state.tail) {
      state.cursor = {
        position: prop,
        point: point
      };
    }
  }

  if (noproxy) {
    return point;
  }

  return point ? point.value : undefined;
}

function connect(a, b) {
  if (b.head) {
    connectp(a.tail, b.head);
    a.tail = b.tail;
    a.length += b.length;
  }

  return a;
}

function connectp(a, b) {
  a.next = b;
  b.prev = a;
}

function point(value, prev, next) {
  return { value, prev, next };
}

export function values(proxy) {
  const values = [];
  const state = proxy.proxy;

  let next = state.head;
  while (next) {
    values.push(next.value);
    next = next === state.tail ? null : next.next;
  }

  return values;
}