raqb/experiments/old-optimizer.js

"use strict";

const util = require("util");
const syncpipe = require("syncpipe");
const debug = require("debug");
const defaultValue = require("default-value");
const mapObj = require("map-obj");

const NoChange = require("../../optimizers/util/no-change");
const RemoveNode = require("../../optimizers/util/remove-node");
const typeOf = require("../../type-of");
const unreachable = require("../../unreachable");
const measureTime = require("../../measure-time");
const concat = require("../../concat");

// FIXME: Consider deepcopying the tree once, and then mutating that tree, instead of doing everything immutably; this might be significantly faster when a few iterations are needed to stabilize the tree, as that might otherwise result in many copies of the subtree(s) leeding up to the changed node(s), one for each iteration.
// FIXME: Consider whether inverting the evaluation order (deepest-first rather than shallowest-first) can remove the need for multiple optimization passes and stabilization detection.
// FIXME: Verify that changed nodes actually result in a change in where the walker goes!

function createDebuggers(optimizers) {
	let debuggers = {};

	for (let optimizer of optimizers) {
		debuggers[optimizer.name] = debug(`raqb:ast:optimize:${optimizer.name}`);
	}

	return debuggers;
}

function createTimings(optimizers) {
	let timings = {};

	for (let optimizer of optimizers) {
		// timings[optimizer.name] = 0n;
		timings[optimizer.name] = 0;
	}

	return timings;
}

function combineOptimizers(optimizers) {
	let allVisitors = {};

	for (let optimizer of optimizers) {
		for (let [ key, visitor ] of Object.entries(optimizer.visitors)) {
			if (allVisitors[key] == null) {
				allVisitors[key] = [];
			}

			allVisitors[key].push({
				name: optimizer.name,
				func: visitor
			});
		}
	}

	return allVisitors;
}

// FIXME: StopMatching marker to signal that eg. a generic visitor should no longer match after a specific one?
// FIXME: OriginalNode marker to explicitly indicate that any transformations applied by *other* visitors should be thrown out?

function defer(func) {
	return { __type: "defer", func: func };
}

module.exports = function optimizeTree(ast, optimizers) {
	// NOTE: Depth-first!
	let visitors = combineOptimizers(optimizers);
	let timings = createTimings(optimizers);
	let debuggers = createDebuggers(optimizers);
	// FIXME: Dirty tracking for stabilization detection

	let visitorsByType = mapObj(visitors, (key, value) => {
		return concat([
			defaultValue(visitors[key], []),
			defaultValue(visitors["*"], []),
		]);
	});

	function handle(node/*, parentStateHandlers*/) {
		let deferFuncs = [];
		// let stateHandlers = Object.create(parentStateHandlers);
		let stateLog = [];

		function registerStateHandler(name, func) {
			stateHandlers[name] = function (value) {
				// FIXME: test setParentState
				return func(value, { setState: setParentState });
			};
		}

		function setParentState(name, value) {
			if (parentStateHandlers[name] != null) {
				parentStateHandlers[name](value);
			}
		}

		function setState(name, value) {
			stateLog.push({ type: "set", name, value });
			// if (stateHandlers[name] != null) {
			// 	stateHandlers[name](value);
			// }
		}

		function resetAllListeners() {
			// Called whenever a node is invalidated (replaced, removed, ...) and therefore no longer has a reason to receive any kind of callbacks
			deferFuncs = [];
			// stateHandlers = Object.create(parentStateHandlers);
			stateLog.push({ type: "reset" });
		}

		function applyVisitors(node) {
			let nodeVisitors = visitorsByType[node.type];

			/*
			run each visitor on the node, until either 
				a) the node is invalidated (removed, substituted)
				b) the list of visitors is finished

			then process all children

			then 
			*/

			if (nodeVisitors == null) {
				return node;
			} else {
				let lastNode = node;
	
				for (let visitor of nodeVisitors) {
					// eslint-disable-next-line no-loop-func
					let { value: result, time } = measureTime(() => {
						return visitor.func(lastNode, { registerStateHandler, setState, defer });
					});
					// FIXME: Re-evaluate children after presence in a new subtree? Is this necessary for making sure the context tree is correct?
	
					timings[visitor.name] += time;
	
					if (result === NoChange) {
						// no-op
					} else if (result == null) {
						throw new Error(`A visitor is not allowed to return null or undefined; if you intended to leave the node untouched, return a NoChange marker instead`);
					} else if (result === RemoveNode) {
						debuggers[visitor.name](`Node of type '${typeOf(lastNode)}' removed`);
						lastNode = RemoveNode;
						resetAllListeners();
						break; // Node has gone stale, stop applying visitors to it
					} else if (result.__type === "defer") {
						deferFuncs.push(result.func);
						continue;
					} else if (result.__raqbASTNode === true) {
						// New subtree to replace the old one
						if (result === node) {
							// Visitor returned the original node again; but in this case, it should return NoChange instead. We enforce this because after future changes to the optimizer implementation (eg. using an internally-mutable deep copy of the tree), we may no longer be able to *reliably* detect when the original node is returned; so it's best to already get people into the habit of returning a NoChange marker in those cases, by disallowing this.
							throw new Error(`Visitor returned original node, but this may not work reliably; if you intended to leave the node untouched, return a NoChange marker instead`);
						} else {
							debuggers[visitor.name](`Node of type '${typeOf(lastNode)}' replaced by node of type '${typeOf(result)}'`);
							lastNode = result;
							resetAllListeners();
							break; // Node has gone stale, stop applying visitors to it
						}
					} else {
						throw new Error(`Visitor returned an unexpected type of return value: ${util.inspect(result)}`);
					}
				}
	
				if (lastNode !== node) {
					// We re-evalue the new node before leaving control to the children handler, as the old one has been substituted, and therefore new visitors might be applicable.
					// FIXME: Is RemoveNode getting handled correctly here?
					// FIXME: This needs to be moved outside of this function to also re-apply other visitors correctly
					return applyVisitors(lastNode);
				} else {
					return lastNode;
				}
			}
		}

		node = applyVisitors(node);
		

		// FIXME: Eventually hardcode the available properties for different node types (and them being single/multiple), for improved performance?
		let changedProperties = {};

		for (let [ property, value ] of Object.entries(node)) {
			if (value == null) {
				continue;
			} else if (value.__raqbASTNode === true) {
				let newValue = handle(value, stateHandlers);

				if (newValue !== value) {
					changedProperties[property] = newValue;
				}
			} else if (Array.isArray(value) && value.length > 0 && value[0].__raqbASTNode === true) {
				// NOTE: We assume that if an array in an AST node property contains one AST node, *all* of its items are AST nodes. This should be ensured by the input wrapping in the operations API.
				// eslint-disable-next-line no-loop-func
				let newValues = value.map((item) => handle(item, stateHandlers));

				if (newValues.some((newValue, i) => newValue !== value[i])) {
					changedProperties[property] = newValues.filter((item) => item !== RemoveNode);
				}
			} else {
				// Probably some kind of literal value; we don't touch these.
				continue;
			}
		}

		if (Object.keys(changedProperties).length === 0) {
			return node;
		} else {
			let newNode = Object.assign({}, node, changedProperties);

			// FIXME: Think carefully about whether there is *ever* a valid reason to remove a single node! As array items are already taken care of above, and leave an empty array at worst, which can make sense. Possibly we even need to encode this data into node type metadata.
			for (let [ key, value ] of Object.entries(newNode)) {
				if (value === RemoveNode) {
					delete newNode[key];
				}
			}

			return newNode;
		}






		// FIXME: Possibly optimize the "node gets returned unchanged" case, somehow? Perhaps by propagating the NoChange marker? But object creation is fast, so that may actually make things slower than just blindly creating new objects...
		// return syncpipe(node, [
		// 	(_) => applyVisitors(_),
		// 	(_) => handleChildren(_)
		// ]);
	}

	let { value: rootNode, time } = measureTime(() => {
		return handle(ast, {});
	});
	
	// let timeSpentInOptimizers = Object.values(timings).reduce((sum, n) => sum + n, 0n);
	let timeSpentInOptimizers = Object.values(timings).reduce((sum, n) => sum + n, 0);

	if (rootNode !== RemoveNode) {
		return {
			ast: rootNode,
			timings: {
				"# Total": time,
				"# Walker overhead": time - timeSpentInOptimizers,
				... timings,
			}
		};
	} else {
		unreachable("Root node was removed");
	}
};