git/animus

history.js (9.9 KB)

// each frame is a base image plus a log of ops painted on top of it. undo
// and redo switch an action's ops off or on and redraw the tiles they cover
// from base. once an action leaves every undo stack it is sealed: folded
// into base and forgotten
const UNDO_MAX = 10;
const actions = new Map();
// frames removed by a delete or merge, kept so the action can be undone
const limbo = new Map();
const local = { undo: [], redo: [] };
let actSeq = 0;
let verSeq = 0;
let stroke = null;

function copyCanvas(src) {
	const cnv = document.createElement('canvas');
	cnv.width = CHUNK;
	cnv.height = CHUNK;
	cnv.getContext('2d').drawImage(src, 0, 0);
	return cnv;
}

function getFrame(id) {
	return frames.find((f) => f.id === id) || limbo.get(id) || null;
}

function resetTimeline() {
	actions.clear();
	limbo.clear();
	local.undo.length = 0;
	local.redo.length = 0;
	stroke = null;
}

function strokeFor(fid) {
	if (stroke && stroke.f === fid) return false;
	closeStroke();
	stroke = { f: fid, a: ++actSeq };
	return true;
}

function closeStroke() {
	net.flush();
	stroke = null;
}

function opKeys(op) {
	const keys = new Set();
	const off = Math.floor(op.b / 2);
	for (let i = 0; i + 3 < op.o.length; i += 4) {
		const cx0 = Math.floor((Math.min(op.o[i], op.o[i + 2]) - off) / CHUNK);
		const cx1 = Math.floor((Math.max(op.o[i], op.o[i + 2]) - off + op.b - 1) / CHUNK);
		const cy0 = Math.floor((Math.min(op.o[i + 1], op.o[i + 3]) - off) / CHUNK);
		const cy1 = Math.floor((Math.max(op.o[i + 1], op.o[i + 3]) - off + op.b - 1) / CHUNK);
		for (let cy = cy0; cy <= cy1; cy++) {
			for (let cx = cx0; cx <= cx1; cx++) keys.add(chunkKey(cx, cy));
		}
	}
	return keys;
}

function srcKeys(src) {
	return src ? new Set([...src.keys(), ...src.base.keys()]) : new Set();
}

// every tile write takes a fresh version, so a saved copy of a tile can
// tell whether it is still current
function bump(f, keys) {
	for (const k of keys) f.vers.set(k, ++verSeq);
}

function versions(f, keys) {
	const v = new Map();
	for (const k of keys) v.set(k, f.vers.get(k));
	return v;
}

function unchanged(f, v, keys) {
	for (const k of keys) {
		if (!v.has(k) || f.vers.get(k) !== v.get(k)) return false;
	}
	return true;
}

// taken before an undo redraws, so the redo can put the tiles back instead
// of replaying, as long as they still carry the versions the undo left
function snapshot(f, keys) {
	const tiles = new Map();
	for (const k of keys) {
		const c = f.get(k);
		tiles.set(k, c ? copyCanvas(c.canvas) : null);
	}
	return { f, tiles, before: versions(f, keys), after: null };
}

function restore(snap) {
	const f = snap.f;
	for (const [k, cnv] of snap.tiles) {
		if (!cnv) {
			f.delete(k);
			continue;
		}
		const [cx, cy] = k.split(',').map(Number);
		getOrCreateChunk(cx, cy, f).ctx.drawImage(cnv, 0, 0);
	}
	for (const [k, n] of snap.before) f.vers.set(k, n);
	requestDraw();
}

// base holds only tiles some logged op touches, copied just before the
// first one does
function registerKeys(f, keys) {
	for (const k of keys) {
		if (f.base.has(k)) continue;
		const c = f.get(k);
		f.base.set(k, c ? copyCanvas(c.canvas) : null);
	}
}

function applyPaint(f, op, isNew) {
	if (isNew) actions.set(op.a, { kind: 'stroke', f: f.id });
	const keys = opKeys(op);
	registerKeys(f, keys);
	const raster = rasterize(op.o, op.b, op.s);
	const last = f.log[f.log.length - 1];
	if (last && last.a === op.a && !last.src && last.on && last.b === op.b && last.s === op.s
		&& last.c[0] === op.c[0] && last.c[1] === op.c[1] && last.c[2] === op.c[2]) {
		last.o.push(...op.o);
		for (const k of keys) last.keys.add(k);
		last.raster = null;
	} else {
		f.log.push({ a: op.a, o: op.o.slice(), c: op.c, b: op.b, s: op.s, on: true, keys, raster });
	}
	fillRaster(f, raster, op.c);
	bump(f, keys);
	if (f === chunks) requestDraw();
}

function banish(rec, a) {
	const f = frames.find((fr) => fr.id === rec.f);
	if (!f) return false;
	const i = removeFrame(f);
	if (i < 0) return false;
	rec.at = i;
	f.limboBy = a;
	limbo.set(f.id, f);
	net.pending = net.pending.filter((p) => p.f !== f.id);
	net.overlays.delete(f.id);
	return true;
}

function unbanish(rec, a, land) {
	const f = limbo.get(rec.f);
	if (!f || f.limboBy !== a) return false;
	limbo.delete(f.id);
	f.limboBy = null;
	insertFrame(f, rec.at, land);
	return true;
}

function applyAdd(id, at, a, mine) {
	const f = newFrameMap(id);
	insertFrame(f, at, mine);
	actions.set(a, { kind: 'add', f: f.id, at: frames.indexOf(f) });
}

function applyDelete(id, a) {
	const rec = { kind: 'del', f: id, at: 0 };
	if (!banish(rec, a)) return false;
	actions.set(a, rec);
	return true;
}

function applyMerge(id, intoId, a, mine) {
	const top = frames.find((f) => f.id === id);
	const bottom = frames.find((f) => f.id === intoId);
	if (!top || !bottom || top === bottom) return false;
	const wasCur = top === chunks;
	const keys = srcKeys(top);
	registerKeys(bottom, keys);
	const rec = { kind: 'merge', f: id, into: intoId, at: 0 };
	if (!banish(rec, a)) return false;
	movePeers(id, intoId);
	bottom.log.push({ a, src: id, on: true });
	mergeInto(top, bottom);
	bump(bottom, keys);
	top.into = intoId;
	actions.set(a, rec);
	if (mine || wasCur) setFrame(frames.indexOf(bottom));
	requestDraw();
	return true;
}

function overlaps(keys, only) {
	for (const k of keys) {
		if (only.has(k)) return true;
	}
	return false;
}

function actionKeys(f, a) {
	const keys = new Set();
	for (const op of f.log) {
		if (op.a !== a) continue;
		for (const k of op.keys) keys.add(k);
	}
	return keys;
}

function rebuild(f, only) {
	if (only) {
		registerKeys(f, only);
	} else {
		for (const op of f.log) registerKeys(f, op.src ? srcKeys(getFrame(op.src)) : op.keys);
		only = new Set(f.base.keys());
	}
	bump(f, only);
	for (const k of only) {
		const cnv = f.base.get(k);
		if (!cnv) {
			f.delete(k);
			continue;
		}
		const [cx, cy] = k.split(',').map(Number);
		getOrCreateChunk(cx, cy, f).ctx.drawImage(cnv, 0, 0);
	}
	// ops reach past the tiles being redrawn; the rest must stay as they are
	paintClip = only;
	try {
		for (const op of f.log) {
			if (!op.on) continue;
			if (op.src) mergeInto(getFrame(op.src), f, only);
			else if (overlaps(op.keys, only)) paintOpInto(f, op);
		}
	} finally {
		paintClip = null;
	}
	requestDraw();
	// a merged frame's pixels live on in the frame it went into
	if (f.into) {
		const g = getFrame(f.into);
		if (g) rebuild(g, only);
	}
}

// only the sealed ops at the front of the log can join base; anything
// after a live op has to stay so the order is kept
function fold(f) {
	let n = 0;
	while (n < f.log.length && !actions.has(f.log[n].a)) n++;
	if (!n) return;
	const done = f.log.splice(0, n);
	const tmp = new Map();
	for (const [k, cnv] of f.base) {
		if (cnv) tmp.set(k, { canvas: cnv, ctx: cnv.getContext('2d') });
	}
	for (const op of done) {
		if (!op.on) continue;
		if (op.src) {
			const src = limbo.get(op.src);
			if (!src) continue;
			mergeInto(src, tmp);
			destroyFrame(src);
		} else {
			paintOpInto(tmp, op);
		}
	}
	const live = new Set();
	for (const op of f.log) {
		for (const k of op.src ? srcKeys(getFrame(op.src)) : op.keys) live.add(k);
	}
	for (const k of [...f.base.keys()]) {
		if (!live.has(k)) {
			f.base.delete(k);
			continue;
		}
		const t = tmp.get(k);
		f.base.set(k, t ? t.canvas : null);
	}
}

function destroyFrame(f) {
	limbo.delete(f.id);
	for (const op of f.log) {
		if (!op.on || !op.src) continue;
		const s = limbo.get(op.src);
		if (s && s.limboBy === op.a) destroyFrame(s);
	}
}

function seal(list) {
	const touched = new Set();
	for (const a of list) {
		const rec = actions.get(a);
		if (!rec) continue;
		actions.delete(a);
		const f = getFrame(rec.f);
		if (rec.kind === 'stroke') {
			if (f) touched.add(f);
		} else if (rec.kind === 'merge') {
			const into = getFrame(rec.into);
			if (into) touched.add(into);
		} else if (f && f.limboBy === a) {
			destroyFrame(f);
		}
	}
	for (const f of touched) fold(f);
}

function redrawAction(rec, f, keys, on, top) {
	const snap = rec.redo;
	rec.redo = null;
	if (on) {
		if (snap && !f.into && snap.f === f && unchanged(f, snap.after, keys)
			&& (!top || unchanged(top, snap.top, keys))) restore(snap);
		else rebuild(f, keys);
		return;
	}
	const next = f.into ? null : snapshot(f, keys);
	rebuild(f, keys);
	if (next) {
		next.after = versions(f, keys);
		if (top) next.top = versions(top, keys);
		rec.redo = next;
	}
}

function toggle(a, on, mine) {
	const rec = actions.get(a);
	if (!rec) return;
	if (rec.kind === 'stroke') {
		const f = getFrame(rec.f);
		if (!f) return;
		for (const op of f.log) {
			if (op.a === a) op.on = on;
		}
		redrawAction(rec, f, actionKeys(f, a), on, null);
		if (mine && frames.includes(f)) setFrame(frames.indexOf(f));
	} else if (rec.kind === 'add' || rec.kind === 'del') {
		if (on === (rec.kind === 'add')) unbanish(rec, a, mine);
		else banish(rec, a);
	} else if (rec.kind === 'merge') {
		const bottom = getFrame(rec.into);
		const op = bottom && bottom.log.find((o) => o.a === a);
		if (!op) return;
		if (on) {
			const top = frames.find((f) => f.id === rec.f);
			if (!top || !banish(rec, a)) return;
			op.on = true;
			top.into = bottom.id;
			redrawAction(rec, bottom, srcKeys(top), true, top);
			if (mine && frames.includes(bottom)) setFrame(frames.indexOf(bottom));
		} else {
			const top = limbo.get(rec.f);
			if (!top || !unbanish(rec, a, mine)) return;
			op.on = false;
			top.into = null;
			redrawAction(rec, bottom, srcKeys(top), false, top);
		}
	}
}

function localActionId() {
	return 'a' + (++actSeq);
}

function localAction(a) {
	local.undo.push(a);
	const done = local.redo.splice(0);
	if (local.undo.length > UNDO_MAX) done.push(local.undo.shift());
	seal(done);
}

function stepHistory(from, to, on, t) {
	closeStroke();
	// in a room the server keeps each painter's stacks
	if (net.on) {
		net.send({ t });
		return;
	}
	const a = from.pop();
	if (a === undefined) return;
	to.push(a);
	toggle(a, on, true);
	dirty = true;
}

function undo() { stepHistory(local.undo, local.redo, false, 'undo'); }
function redo() { stepHistory(local.redo, local.undo, true, 'redo'); }