constrain.js

"use strict"

// Constrain: A package for creating animated figures in JavaScript canvases,
// similar to the sort of animated figure you would put into a slide
// presentation, or for web-based course notes.
// 
// Author: Andrew Myers, 2019-2023
//   github.com/andrewcmyers/constrain

var Constrain = function() {

// There is a set of Figure objects recorded in the array Figures. Each one
// is attached to a separate canvas.
// 
const Figures = []

// Various switches and constants control the default appearance of figures.

const USE_BACKPROPAGATION = true,
      CACHE_ALL_EVALUATIONS = true,
      PROFILE_EVALUATIONS = false,
      REPORT_EVALUATED_EXPRESSIONS = false,
      COMPARE_GRADIENTS = false,
      TINY = 1e-17

const DEBUG = false, DEBUG_GROUPS = false, DEBUG_CONSTRAINTS = false, REPORT_UNSOLVED_CONSTRAINTS = false,
      CHECK_NAN = false, DEBUG_TWEENING = false
const REPORT_PERFORMANCE = false

const NUMBER = "number", FUNCTION = "function", OBJECT_STR = "object", STRING_STR = "string"

const Figure_defaults = {
    ARROW_SIZE : 12,
    FONT_SIZE : 12,
    LINEWIDTH : 1,
    TRIANGLE_SIZE : 10,
    FRAMERATE : 60,
    FONT_NAME : "sans-serif",
    FONT_STYLE : "",
    LINE_SPACING : 1.3,
    SUPERSCRIPT_OFFSET : 0.44,
    SUBSCRIPT_OFFSET : -0.16,
    LINELABEL_INSET : null,
    SCRIPTSIZE : 0.80,
    LARGE_SPAN : 10000.0,
    HYPHEN_COST : 100000,
    CONNECTION_STYLE : 'magnet'
}

const UNCMIN_GRADIENT = 0, UNCMIN_BFGS = 1, UNCMIN_DFP = 2, UNCMIN_ADAM = 3, UNCMIN_LBFGS = 4
let algorithm = UNCMIN_BFGS

const CALLBACK_RETURNED_TRUE = "Callback returned true",
      BAD_SEARCH_DIRECTION = "Search direction has Infinity or NaN",
      BAD_GRADIENT = "Gradient has Infinity or NaN"

const ADAM_BETA1 = 0.9, ADAM_BETA2 = 0.999, ADAM_EPSILON = 1e-8
const RANDOM_GRADIENT_SCALING = 0.001
const SOLVE_TIME_ALPHA = 0.3
const TARGET_TWEEN_FRAMES = 4

const defaultMinimizationOptions = {
    maxIterations : 1000,
    overshoot : 0.1,
    stepSize : 1,
    LBFGS_M : 10,
}

const {gradient, dot, sub, add, tensor, div, sqrt, mul, transpose, all, isFinite, neg} = numeric

function wrongSizedInvHessian(nvars, invHessian) {
  switch (algorithm) {
    case UNCMIN_BFGS:
    case UNCMIN_DFP: return nvars != invHessian.length
    case UNCMIN_LBFGS: return nvars != invHessian.y_hist[0].length
    default: return false
  }
}

function seconds(T) {
    return ((T / 1000) % 100).toLocaleString(undefined, {minimumFractionDigits:3, maximumFractionDigits:3})
}

// A Figure represents a possibly animated figure containing graphical objects
// whose position is solved for.  A Figure is attached to a canvas and knows
// how to render itself. It has a set of associated Frames which can be stepped
// through.
// 
// A Figure can have multiple frames that correspond to the state of the
// animation. Frames can have a positive duration, allowing smooth animation
// during the frame if constraints are phrased in terms of the time within the
// frame.
//
// A Figure has a set of Variables that can be adjusted to minimize an
// objective function generated by summing costs from various constraints.
//
// Expressions can be built out of Variables. Constraints are built using expressions.
// They have a cost that is supposed to be as small as possible (zero, if the constraint
// is fully satisfiable). The solver tries to minimize the total cost of all constraints.
//
// Associated with each figure is a set of Graphics that know how to
// render themselves based on associated Variables.  When new graphical objects
// are created, their style is set to their figure's style by default, but can
// be changed later.
// 
// Depending on which frame a figure is on, different variables are active and
// solved for. A figure can also have multiple stages, which are orthogonal to
// frames. Variables are solved for in stages, and the same stages are solved
// for each frame.
// 
class Figure {
    // Create a figure appearing in a canvas.  'canvas' should be either the
    // canvas HTML element or, for convenience, its id attribute as a string
    constructor(canvas) {
        this.figure = this
        if (typeof canvas == OBJECT_STR && canvas instanceof HTMLCanvasElement) {
            this.canvas = canvas
            this.name = canvas.id
        } else if (typeof canvas == STRING_STR) {
            const c = document.getElementById(canvas)
            if (c) {
                this.canvas = canvas = c
                this.name = c.id
            } else {
                console.error('Could not find any canvas with id "' + canvas + '"')
                return
            }
        } else if (typeof canvas == 'undefined' &&
                document.getElementsByTagName('canvas').length == 1) {
            this.canvas = canvas = document.getElementsByTagName('canvas')[0]
            this.name = 'canvas'
        } else {
            console.error("new Figure() expects a canvas or a canvas id")
            return
        }
        this.ctx = canvas.getContext("2d")
        this.is_ready = true   // whether figure content is marked as ready for rendering
        this.is_started = false // whether a request for rendering has occurred
        this.setupListeners()
        this.initObjects()
        this.time = 0
        this.zoom = 1 // figure units per HTML pixel
        this.zoomCheckInterval = 200 // how many ms between testing browser zoom
        this.currentFrame = undefined // current frame object
        this.frameRate = Figure_defaults.FRAMERATE
        this.Frames = []
        this.wrapFrames = false // does advancing from last frame go back to first
        this.currentStage = 0
        this.numStages = 1
        this.substitutionEnabled = true
    // default styles
        this.style = new Context()
        this.setFillStyle("white")
        this.setStrokeStyle("black")
        this.setTextStyle("black")
        this.setFontName(Figure_defaults.FONT_NAME)
        this.setFontStyle(Figure_defaults.FONT_STYLE)
        this.setFontSize(Figure_defaults.FONT_SIZE)
        this.setLineWidth(Figure_defaults.LINEWIDTH)
        this.setLineSpacing(Figure_defaults.LINE_SPACING)
        this.setLineLabelInset(Figure_defaults.LINELABEL_INSET)
        this.setArrowSize(Figure_defaults.ARROW_SIZE)
        this.setConnectionStyle(Figure_defaults.CONNECTION_STYLE)
        this.setLineDash(null)

        this.repeat = false
        this.animatedSolving = false
        this.solverCallbacks = []
        this.minimizationOptions = {...defaultMinimizationOptions}
        this.fadeColor = this.findFadeColor(canvas)
        this.timeVar = new Variable(this, "time") // variable representing the current frame time
        Figures.push(this)
        if (canvas.style.padding && canvas.style.padding != "0px")
            console.error("Canvas input will not work correctly with padding")
    }
    setupCanvas() {
        const canvas = this.canvas, br = canvas.getBoundingClientRect(),
              _width = br.width, _height = br.height
        let scale
        if (window.innerWidth && window.visualViewport) {
            this.browserZoom = (window.innerWidth/window.visualViewport.width)
        } else {
            scale = 1
        }
        scale = this.browserZoom * (window.devicePixelRatio || 1) // canvas pixels per HTML "pixel"
        this.scale = scale
        this.width = _width
        this.height = _height
        this.canvas.width = _width * scale
        this.canvas.height = _height * scale
        this.ctx.setTransform(scale * this.zoom, 0, 0, scale * this.zoom, 0, 0)

        if (this.browserZoom) {
            setInterval(() => {
                const newZoom = (window.innerWidth/window.visualViewport.width)
                if (newZoom != this.browserZoom) {
                    this.browserZoom = newZoom
                    this.renderNeeded = true
                    this.delayedRender()
                }
            }, this.zoomCheckInterval)
        }
    }
    findFadeColor(canvas) {
        let elt = canvas, c
        while (elt) {
            c = window.getComputedStyle(canvas).backgroundColor
            if (c != "rgba(0, 0, 0, 0)") break
            elt = elt.parentNode
        }
        if (c == "rgba(0, 0, 0, 0)") return "#fff"
        return c
    }
    toString() {
        return "Figure"
    }
    // Return this figure. Useful in combination with `with`.
    thisFigure() {
        return this
    }
    setZoom(z) {
        this.zoom = z || 1
    }
    setupListeners() {
        const canvas = this.canvas
        this.canvas.addEventListener('mousedown', e => {
            const x = e.offsetX, y = e.offsetY
            // alternatively: could use clientX/clientY with getBoundingClientRect
            this.interactives.forEach(i => {
                if (!i.mousedown(x, y, e)) return false
            })
            e.preventDefault()
            e.stopPropagation()
            return false
        })
        this.canvas.addEventListener('mouseup', e => {
            const x = e.offsetX, y = e.offsetY
            this.interactives.forEach(i => {
                if (!i.mouseup(e)) return false
            })
            e.preventDefault()
            e.stopPropagation()
            return false
        })
        this.canvas.addEventListener('mousemove', e => {
            if (!this.focused) return false
            const x = e.offsetX, y = e.offsetY
            return this.focused.mousemove(x, y, e)
        })
        this.canvas.addEventListener('dblclick', e => {
            e.preventDefault()
            e.stopPropagation()
            return false
        })
        this.canvas.addEventListener('click', e => {
            e.preventDefault()
            e.stopPropagation() 
            return false
        })
    }
    initObjects() {
        this.Graphics = []
        this.Constraints = []
        this.Graphs = []
        this.Variables = []
        this.numVariables = 0
        this.interactives = []
        this.events = []
        this.focused = null
        this.renderNeeded = false
    }
    // Return the valuation to be used for solving
    initialValuation(incremental) {
        if (this.Variables.length != this.numVariables) {
            console.error("oops " + this.numVariables + " " + this.Variables.length)
        }
        const result = new Array(this.activeVariables.length)
        for (let i = 0; i < this.activeVariables.length; i++) {
            const v = this.activeVariables[i]
            if (v.hasOwnProperty('solutionValue')) {
                if (!incremental && v.prevValue !== undefined) {
                    // predict next solution based on linear motion assumption
                    const motion = numeric.sub(v.solutionValue, v.prevValue)
                    if (isFinite(motion) && Math.abs(motion) < 10) {
                        result[i] =  numeric.add(v.solutionValue, motion)
                    } else {
                        result[i] = v.solutionValue
                    }
                } else {
                    result[i] = v.solutionValue
                }
                v.prevValue = v.solutionValue
            } else if (v.hint != null) {
                result[i] = v.hint
            } else {
                result[i] = 100
            }
            v.solutionValue = result[i]
        }
        return result
    }
    // Create a map from each variable to the set of constraints that mention it.
    constraintsByVar() {
        const constraintsByVar = new Map()
        this.Constraints.forEach(c => {
            if (c.active()) {
                for (const v of c.variables()) {
                    const cons = constraintsByVar.get(v) || new Set()
                    cons.add(c)
                    constraintsByVar.set(v, cons)
                }
            }
        })
        return constraintsByVar
    }

    // Control whether substitution is used to solve for variables. It usually
    // speeds up solving but by overconstraining related variables can make it
    // harder to escape local minima.
    enableSubstitution(b) {
        if (b === undefined) b = true
        this.substitutionEnabled = b
    }

    // Variables are solved either by minimization or by direct solution after
    // minimization is complete.  This function identifies which variables need
    // to be solved to support the currently visible graphical objects in this
    // stage (and component, if provided), and decides which way to solve them.
    // It also determines which constraints need to be evaluated during
    // minimization.
    //   Variables solved by minimization are assigned indices in the valuation
    // array to each of the variables that are active in this stage (and
    // component, if provided).
    //   Variables are solved directly when they are only used in a single
    // constraint whose form admits direct solution. Closures that directly
    // solve these variables are appended to this.postMinActions; these closures
    // are ordered so that variables have already been solved.
    //   If the component is not specified, only computes this.stageVariables
    // to be the variables that need to be solved across all components in the
    // stage.
    numberVariables(stage, component) {
        let i = 0
        const frame = this.currentFrame
        if (DEBUG && DEBUG_CONSTRAINTS) {
            console.log("-- Setting up solving for " + this.name +
                ", frame " + (frame ? frame.index : "none") + ", stage " + stage
                + (component ? (", component " + component) : " (all components)") + " --")
        }
        this.Variables.forEach(v => v.removeIndex())
        this.Constraints.forEach(c => { delete c.directSolved })
        const constraintsByVar = this.constraintsByVar()
        const solvedVariables = new Set()    // all variables to solve currently
        const enabledConstraints = new Set() // relevant to current solve
        const activeVariables = []           // to solve via minimization
        const postMinActions = []            // solving actions to run after minimization
        const directSolvedConstraints = new Set() // solved directly or by substitution
        let substitutable = 0, directlySolved = 0
        // Add this constraint, if not there already, to the
        // set of enabled constraints, and check if each of its variables need
        // to be solved, which may lead to enabling more constraints.
        function enableConstraint(c) {
            if (!enabledConstraints.has(c)) {
                enabledConstraints.add(c)
                c.variables().forEach(checkIfNeeded)
                delete c.directSolved
            }
        }

        // Check whether v needs to be solved for, and activate any
        // constraints that mention it.
        function checkIfNeeded(v) {
            if (v.stage != stage) return
            if (v.index !== undefined) return
            if (v === v.figure.timeVar) return
            if (component && v.component != component) return
            if (solvedVariables.has(v)) return
            solvedVariables.add(v)
            const cons = constraintsByVar.get(v)
            if (cons) cons.forEach(enableConstraint)
        }
        this.Graphics.forEach(g => {
            if (g.active() && g.visible()) {
                g.variables().forEach(v => {
                    checkIfNeeded(v)
                })
            }
        })
        if (!component) {
            this.stageVariables = solvedVariables
            if (DEBUG && DEBUG_CONSTRAINTS) {
                console.log("Stage variables = ", this.stageVariables)
            }
            return solvedVariables
        }

        // Return a function that solves the equation e = e2 for the variable v,
        // given two arguments: the value of e2, and a current valuation array.
        function solveFor(v, e) {
            if (e == v) {
                return (v2, valuation) => v2
            }
            if (e instanceof Plus) {
                const [e1, e2] = [e.e1, e.e2]
                const solve1 = solveFor(v, e1)
                if (solve1 && !exprVariables(e2).has(v)) { // e1 + e2 = sum <=> e1 = sum - e2
                    return (sum, valuation) => solve1(sum - evaluate(e2, valuation), valuation)
                }
                const solve2 = solveFor(v, e2)
                if (solve2 && !exprVariables(e1).has(v)) { // e1 + e2 = sum <=> e2 = sum - e1
                    return (sum, valuation) => solve2(sum - evaluate(e1, valuation), valuation)
                }
                return null
            } else if (e instanceof Minus) {
                const [e1, e2] = [e.e1, e.e2]
                const solve1 = solveFor(v, e1)
                if (solve1 && !exprVariables(e2).has(v)) { // e1 - e2 = diff <=> e1 = diff + e2
                    return (diff, valuation) => solve1(diff + evaluate(e2, valuation), valuation)
                }
                const solve2 = solveFor(v, e2)
                if (solve2 && !exprVariables(e1).has(v)) { // e1 - e2 = diff <=> e2 = e1 - diff
                    return (diff, valuation) => solve2(evaluate(e1, valuation) - diff, valuation)
                }
                return null
            } else {
                return null // can't solve
            }
        }

        // If variable v is only in one constraint and can
        // be solved from it, append solving code to postMinActions
        // for v and (before that) for any directly solvable variables
        // it depends on and return true. If we can't solve v directly,
        // return false.
        // 
        function tryDirectSolve(v) {
            if (v.hasOwnProperty('directSolved')) return v.directSolved
            if (v.solvePending) return false // prevent cycles in solution strategy
            const s = constraintsByVar.get(v)
            if (!s || s.size == 0) {
                postMinActions.push(valuation => {
                    v.solutionValue = v.hasOwnProperty('hint') ? v.hint : 100
                    if (DEBUG_CONSTRAINTS) console.log("Trivially solving " + v + " <- " + v.solutionValue)
                })
                directlySolved++
                v.directSolved = true // unconstrained: any value works!
                return
            }
            if (s.size > 1) return false
            v.solvePending = true
            for (const c of s.keys()) {
                if (c instanceof NearZero && c.expr instanceof Sq && c.expr.expr instanceof Minus && !c.directSolved) {
                    let e1 = c.expr.expr.e1, e2 = c.expr.expr.e2
                    let solve1 = solveFor(v, e1),
                        e2v = exprVariables(e2)
                    if (!solve1 || e2v.has(v)) { // try it the other way round
                        [e1, e2] = [e2, e1]
                        solve1 = solveFor(v, e1)
                        e2v = exprVariables(e2)
                    }
                    if (solve1 && !e2v.has(v)) {
                        for (const v2 of e2v) tryDirectSolve(v2)
                        if (c.directSolved) { // oops, used it up already
                            v.directSolved = false
                            v.solvePending = false
                            return false
                        }
                        postMinActions.push(valuation => {
                            v.solutionValue = 0
                            v.solutionValue = solve1(evaluate(e2, valuation), valuation)
                            if (DEBUG_CONSTRAINTS) console.log("Directly solving " + v + " <- " + v.solutionValue)
                        })
                        directlySolved++
                        v.directSolved = c
                        v.solvePending = false
                        directSolvedConstraints.add(c)
                        c.directSolved = v
                        return true
                    }
                }
                v.directSolved = false // can't solve directly
                v.solvePending = false
                return false
            }
            console.error("can't get here")
        }
        for (const v of solvedVariables) {
            tryDirectSolve(v)
        }

        function simpleExpr(e) {
            return (e instanceof Variable) || (typeof e == NUMBER) || (e instanceof Global)
        }

        function trySubstitution(v) {
            const s = constraintsByVar.get(v)
            for (const c of s.keys()) {
                if (c instanceof NearZero && c.expr instanceof Sq && c.expr.expr instanceof Minus && c.cost >= 1) {
                    let e1 = c.expr.expr.e1, e2 = c.expr.expr.e2
                    const e1_simple = simpleExpr(e1),
                          e2_simple = simpleExpr(e2)
                    if (e1 == v && e2_simple || e2 == v && e1_simple) {
                        const substitution = (v == e1) ? e2 : e1
                        if (substitution instanceof Variable) {
                            if (substitution.directSolved) continue
                            if (v.toString() >= substitution.toString()) continue
                        }
                        v.substitution = substitution
                        directSolvedConstraints.add(c)
                        postMinActions.push(valuation => {
                            v.solutionValue = evaluate(substitution, valuation)
                            if (DEBUG_CONSTRAINTS) console.log("Solving by substitution " + v + " <- " + v.solutionValue)
                        })
                        substitutable++
                        if (DEBUG_CONSTRAINTS) console.log("Substitution: " + v + " <- " + v.substitution)
                        return
                    }
                }
            }
        }

        if (this.substitutionEnabled) {
            for (const v of solvedVariables) {
                if (!v.directSolved) trySubstitution(v)
            }
        }

        // Assign a fresh index to variable v if it is not to be solved directly
        function assignIndex(v) {
            if (v.substitution && v.substitution.directSolved) {
                console.error("Oops, using a direct solved variable")
            }
            if (v.directSolved || v.substitution) return
            if (component && v.variableComponent() !== component) return
            v.setIndex(i)
            activeVariables.push(v)
            i++
        }


        // assign indices to all variables that need to be solved and cannot be
        // solved directly
        for (const v of solvedVariables) {
            assignIndex(v)
        }

        const activeConstraints = new Set()  // to use in minimization
        // create the set of constraints that minimization should try to minimize
        for (const c of enabledConstraints) {
            if (!directSolvedConstraints.has(c)) activeConstraints.add(c)
        }
        this.activeConstraints = activeConstraints

        if (DEBUG) {
            this.solvedVariables = solvedVariables
            this.enabledConstraints = enabledConstraints
        }
        this.activeVariables = activeVariables
        this.postMinActions = postMinActions
        if (DEBUG) {
            console.log("Stage " + stage + ", component " + component)
            console.log("  Constraints solved by minimization: ", activeConstraints.size)
            console.log("  Variables solved by minimization: ", activeVariables.length)
            console.log("  Directly solved variables: ", directlySolved)
            console.log("  Substituted variables: ", substitutable)
        }
    }
    unnumberVariables() {
        const vars = this.Variables, n = vars.length
        for (let i = 0; i < n; i++) {
            vars[i].removeIndex()
        }
    }
    // Add one or more constraints that should be satisfied
    // If an array is passed as an argument, each element is added
    // as a constraint.
    // A constraint should return a nonnegative cost
    // Normally, constraints call this method themselves
    addConstraints(...constraints) {
        constraints.flat().forEach(c => {
            if (!this.Constraints.includes(c)) this.Constraints.push(c)
        })
        delete this.components
    }
    removeConstraints(...constraints) {
        constraints = constraints.flat()
        this.Constraints = this.Constraints.filter(c => !constraints.includes(c))
        delete this.components
    }

    totalCost(valuation) {
        return this.costGrad(valuation, false)
    }

    // compute the gradient of the output cost at value 'valuation' with
    // respect to all active expressions, including variables, using
    // backpropagation. Two different backprop evaluations cannot happen
    // at the same time, because partial results are stored in the expression
    // objects themselves, in their bpDiff field.
    //
    // Requires that all variables have been numbered appropriately.
    bpGrad(valuation, task) {
        const n = valuation.length,
              val = this.totalCost(valuation) // initalize node values
        task.run(valuation)
        const grad = new Array(n)
        for (let i = 0; i < n; i++) {
            const v = this.activeVariables[i]
            if (v.bpTask !== task) {
                // console.log("Variable did not have its gradient computed: " + v)
                grad[i] = 0
            } else {
                grad[i] = v.bpDiff
                if (CHECK_NAN) checkNaNResult(v.bpDiff)
            }
        }
        if (COMPARE_GRADIENTS) {
            let [cgVal, cgGrad] = this.costGrad(valuation, true)
            for (let i = 0; i < valuation.length; i++) {
                if (exceedsError(cgVal, val)) {
                    console.error("Difference between computed values exceeds error")
                }
                if (exceedsError(cgGrad[i], grad[i])) {
                    console.error("Difference between computed gradients exceeds error")
                }
            }
        }
        return [val, grad]
    }

    isActiveConstraint(con) {
        if (!con.active()) return false
        if (con.parent !== undefined) return this.isActiveConstraint(con.parent)
        return true
    }

    setupBackPropagation(task) {
        let n = 0
        this.activeConstraints.forEach(con => {
            n++
            // console.log("  active constraint: " + con)
            con.addToTask(task)
        })
        // console.log(`Created backpropagation task with ${task.exprs.length} expressions from ${n} active constraints`)
    }

    // Compute the total cost of the constraints, and the gradient of
    // the cost wrt the currently active variables. This is done by
    // symbolic differentiation.
    costGrad(valuation, doGrad) {
        let n = valuation.length, cost = 0, dcost = new Array(n).fill(0)
        this.activeConstraints.forEach(con => {
            if (con.directSolved) {
                console.error("direct-solved constraint appearing in cost minimization", con)
            }
            const result = con.getCost(valuation, doGrad)
            if (CHECK_NAN && checkNaNResult(result)) return
            let c, dc
            if (doGrad) {
                [c, dc] = result
                dcost = numeric.add(dcost, dc)
            } else {
                c = result
            }
            cost += c
        })
        if (!doGrad) {
            return cost
        } else {
            return [cost, dcost]
        }
    }
    // Recompute the components for a given figure stage
    // Requires: this.stageVariables contains all the variables that need to be solved in
    // this stage.
    computeComponents(stage) {
        if (DEBUG) console.log("Computing components for stage " + stage)
        delete this.activeComponent
        for (const v of this.stageVariables) {
            if (v.stage != stage) {
                console.error("Variable is in wrong stage")
            }
            delete v.component
        }
        this.Constraints.forEach(c => {
            if (c.active())
                c.variables().forEach(v1 => {
                    if (v1.stage != stage) return
                    const v1c = v1.variableComponent()
                    c.variables().forEach(v2 => {
                        if (v2.stage != stage) return
                        const v2c = v2.variableComponent()
                        if (v1c !== v2c) {
                          v1c.component = v2c
                        }
                    })
                })
        })
        const components = []
        for (const v of this.stageVariables) {
            const c = v.variableComponent()
            c.component = c
            if (!components.includes(c)) components.push(c)
        }
        if (DEBUG_CONSTRAINTS) {
         console.log(this.name +
            (this.currentFrame ? " frame " + this.currentFrame.index : "") +
            ": stage " + stage + " contains " + this.stageVariables.size + " variables and " + components.length + " components: [" + components.join(", ") + "]")
            for (const c of components) {
                let s = "component " + c + ": "
                for (const v of this.stageVariables) {
                    if (v.variableComponent() == c) s += (v + ' ')
                }
                console.log(s)
            }
        }
        return components
    }
    // compute a valuation to solve constraints within tolerance tol
    updateValuation(tol, incremental) {
      let solution, figure = this
      if (PROFILE_EVALUATIONS) evaluations = 0
      if (!this.components) this.components = []
      figure.timeVar.currentValue = figure.currentTime
      this.invalidateCachedExprs([this.timeVar])
      for (let stage = 0; stage < this.numStages; stage++) {
        this.activeStage = stage
        this.numberVariables(stage)
        let components = this.components[stage]
        if (!components) {
            components = this.computeComponents(stage)
            this.components[stage] = components
        } // otherwise, reuse previously computed components

        solution = [[], "No minimization needed"]

        // console.log(`Stage ${stage}: ${components.length} components`)
        for (const component of components) {
            this.activeComponent = component
            this.numberVariables(stage, component)
            this.invalidateCachedExprs(this.stageVariables)
            this.currentValuation = this.initialValuation(incremental)
            if (DEBUG_CONSTRAINTS) {
               console.log(`Solving component in stage ${stage}: ${this.activeVariables.length} minimized variables, ${this.activeConstraints.size} constraints, ${this.postMinActions.length} post-min actions`)
            }
            if (component.invHessian && wrongSizedInvHessian(this.currentValuation.length, component.invHessian)) {
                delete component.invHessian
                if (DEBUG) console.log("Discarding wrong-sized inverse Hessian")
            }
            solution = this.minimizeConstraintLoss(this.currentValuation, tol, component.invHessian)
            if (solution[3]) this.totalIterations += solution[3]
            if (!solution[1]) return false
            component.invHessian = solution[2]
            this.postMinActions.forEach(solver => solver(solution[0]))

            if (PROFILE_EVALUATIONS) console.log("  evaluations = " + evaluations)
            if (DEBUG_CONSTRAINTS || REPORT_UNSOLVED_CONSTRAINTS) {
                for (const c of this.activeConstraints) {
                    if (c instanceof Loss) {
                        const loss = evaluate(c.expr, solution[0])
                        if (Math.abs(loss > 0.01)) {
                          if (c.cost >= 1) {
                            console.log("** Badly solved constraint " + c + ": loss = " + loss)
                          } else {
                            console.log("   Weak constraint " + c + ": loss = " + loss)
                          }
                        }
                    } else {
                        //      console.error("huh?" + c)
                    }
                }
            }
        }
      }
      if (PROFILE_EVALUATIONS) {
       console.log("Total evaluations: " + evaluations)
       if (REPORT_EVALUATED_EXPRESSIONS) {
        const entries = []
        for (const e of evaluationCounts.entries()) {
            entries.push(e)
        }
        const sorted = entries.sort((a, b) => b[1] - a[1])
        for (let i = 0; i < sorted.length; i++) {
            console.log("  expr: " + sorted[i][0] + ", evaluations: " + sorted[i][1])
        }
       }
      }
      return true
    }

    recordUpdatedValuation(accuracy) {
        this.totalIterations = 0
        const solved = this.updateValuation(accuracy)
        if (DEBUG_TWEENING) console.log("total iterations: " + this.totalIterations)
        if (!solved) {
            console.error("not solved??")
        }
        this.unnumberVariables()
        return this.recordValuation(true)
    }

    // Create a new array holding the current values of all variables. If
    // valuation is provided as an argument, it's the solver's current value;
    // otherwise, the renderer's.
    recordValuation(valuation) {
        const vars = this.Variables,
              n = vars.length,
              result = new Array(n)
        for (let i = 0; i < n; i++) {
            if (valuation) {
                result[i] = vars[i].solutionValue
            } else {
                result[i] = vars[i].renderValue
            }
        }
        // console.log("recorded " + count + " variable values")
        return result
    }

    // Set the render values of all variables using the valuation array
    applyValuation(valuation) {
        const vars = this.Variables
        const n = vars.length
        if (n != valuation.length) {
            console.error("length mismatch")
        }
        for (let i = 0; i < n; i++) {
            const v = valuation[i], variable = vars[i]
            variable.removeIndex()
            if (v !== undefined) {
                if (variable.renderValue !== v) {
                    variable.renderValue = v
                    // console.log("invalidating cached exprs from renderValue " + variable)
                    this.invalidateCachedExprs([variable])
                }
            } else {
                delete variable.renderValue
                // console.log("invalidating cached exprs from undefined " + variable)
                this.invalidateCachedExprs([variable])
            }
        }
    }

    invalidateCachedExprs(vars) {
        for (const v of vars) {
            for (const expr of v.dependents) {
                if (expr.cachedResult) {
                    // console.log("  forgetting cached value of " + expr + " because of " + v)
                    expr.clearCache()
                }
            }
        }
    }

    // Register a callback to be invoked at every solver step
    registerCallback(cb) {
        for (let i = 0; i < this.solverCallbacks.length; i++) {
            if (this.solverCallbacks[i] == cb) return
        }
        this.solverCallbacks.push(cb)
    }
    // Unregister a callback. Either the callback object itself or
    // its name may be supplied as an argument.
    unregisterCallback(name) {
        for (let i = 0; i < this.solverCallbacks.length; i++) {
            if (this.solverCallbacks[i].name == name ||
                this.solverCallbacks[i] === name) {
                this.solverCallbacks = this.solverCallbacks.slice(0, i)
                                           .concat(this.solverCallbacks.slice(i+1))
            }
        }
    }
    // Run the minimization-based solver. The parameter invHessian is optional, useful
    // for incrementally solving from a previous solution.
    minimizeConstraintLoss(valuation, tol, invHessian) {
        let doGrad = true, fig = this
        if (valuation === undefined) {
            console.error("Need initial valuation")
        }
        if (valuation.length == 0) {
            if (DEBUG) console.log("  No minimization needed")
            return [valuation, "No minimization needed"]
        }
        const task = USE_BACKPROPAGATION ? new BackPropagation(this.activeVariables) : undefined
        if (USE_BACKPROPAGATION) {
            this.setupBackPropagation(task)
        }
        let result, callback, maxit = 1000
        if (this.solverCallbacks.length > 0) {
            callback = (it, x0, f0, g0, H1) => {
                for (let i = 0; i < this.solverCallbacks.length; i++) {
                    if  (this.solverCallbacks[i].call(it, x0, f0, g0, H1)) return true
                }
                return false
            }
        }
        const minimizationOptions = this.minimizationOptions
        const uncmin_options = {tol, maxit}
        for (const key in minimizationOptions) uncmin_options[key] = minimizationOptions[key]
        uncmin_options.Hinv = invHessian
        if (doGrad) {
            if (USE_BACKPROPAGATION) {
                result = uncmin((v,d) => { return d ? fig.bpGrad(v, task) : fig.totalCost(v) },
                                valuation, callback, uncmin_options)
            } else {
                result = uncmin((v,d) => fig.costGrad(v,d), valuation, callback, uncmin_options)
            }
        } else {
            result = numeric.uncmin(this.totalCost, valuation, undefined, uncmin_options)
        }
        if (DEBUG && result.message != CALLBACK_RETURNED_TRUE) console.log(result.iterations + " iterations, ", result.message)
        return [result.solution, result.message != CALLBACK_RETURNED_TRUE, result.invHessian, result.iterations]
    }

// Rendering
    renderIfDirty(animating) {
        if (this.currentFrame === undefined) {
            console.log("current frame not defined yet, skipping render")
            return
        }
        if (this.renderNeeded) {
            this.renderFrame(animating)
            this.renderNeeded = false
        }
    }

    // Cause a render to happen (but not right away, so multiple render requests are
    // collapsed into one.)
    delayedRender() {
        this.figure.renderNeeded = true
        setTimeout(() => this.figure.renderIfDirty(false), 0)
    }

    // Render this figure for time this.renderTime (whic is a fraction in [0,1]
    // measuring completion of current frame) Parameter animating is whether
    // this is just an intermediate animation frame.
    //
    // Implementation notes:
    // The figure maintains up to 3 valuations for solvable variables,
    // in this.valuations.
    // this.prevValuation : the solved valuation for a time before the current time
    // this.nextValuation : the solved valuation for a time after the current time
    // this.pendingValuation : the solved valuation for a time after the time for valuations[1].
    //    Once the current time goes beyond the time for nextValuation, that valuation becomes
    //    the prevValuation and pendingValuation becomes nextValuation.
    // the properties this.prevTime, this.nextTime, and this.pendingTime are the values of time
    // for each of these valuations. In addition, the property this.renderTime is the time
    // at which rendering is supposed to happen, and what is rendering is an interpolation between
    // prevValuation and nextValuation, which is in v.renderValue for all variables v
    //
    // cases:
    //   1. no existing valuations: compute the valuation for current time and render it,
    //       and also start a solving job for the next time.
    //   2. have previous valuation but not next valuation.
    //       solve in foreground for the valuation for the next time and render an interpolated value, and
    //       also start a solving job for the pending valuation, aborting any existing solving job.
    //   3. have previous and next valuation but not pending valuation
    //       render an interpolated valuation and possibly start a solving job for the pending valuation
    //        3a. No useful pending background solve, so start one, aborting any existing background solve.
    //        3b. Pending background solve for a time in the future. Just interpolate and render.
    //   4. have previous, next, and (good) pending valuation.
    //        Simply render interpolated frame.
    renderFrame(animating, frameInterval, frameLength) {
        const figure = this,
              rT = figure.realTime,
              t = figure.renderTime,
              vars = this.Variables
        function updateSolveTime() {
            const dT = (new Date().getTime() - figure.startRealTime) - figure.realTime
            figure.avgSolveTime = figure.avgSolveTime * (1 - SOLVE_TIME_ALPHA) + dT * SOLVE_TIME_ALPHA
            if (DEBUG_TWEENING) {
                console.log("Actual solve time = " + dT/1000)
                console.log("New avg solve time = " + figure.avgSolveTime/1000)
            }
        }
        function nextSolveTime(t) {
            const result = Math.min(1, t + TARGET_TWEEN_FRAMES * figure.avgSolveTime/frameLength)
            const eof = figure.startRealTime + frameLength
            if (result > eof - frameInterval) result = 1
            // console.log("next solve time for " + t + " is " + result)
            return result
        }
        function interpolate(v0, v1, f) {
            const n = v0.length,
                  result = new Array(n)
            for (let i = 0; i < n; i++) {
                const a = v0[i], b = v1[i]
                result[i] = (a === undefined ? b :
                             b === undefined ? a :
                             a + (b - a) * f)
            }
            return result
        }
        function sameValuation(a, b) {
            const n = a.length
            for (let i = 0; i < n; i++) {
                if (a[i] != b[i]) return false
            }
            return true
        }
        if (!animating) {
            this.setupCanvas()
            this.Graphs.forEach(g => g.setupHints())
            const t0 = new Date().getTime()
            figure.realTime = 0
            const solved = this.updateValuation(this.solutionAccuracy(false))
            if (!figure.avgSolveTime) figure.avgSolveTime = new Date().getTime() - t0
            this.unnumberVariables()
            const valuation = this.recordValuation(true)
            this.applyValuation(valuation)
            this.currentValuation = true
            if (!solved) { // animating solution
                setTimeout(() => this.renderFrame(false), 16)
            }
            this.clearCanvas()
            this.renderFromValues()
            return
        }
        frameInterval = frameInterval || 1000/this.frameRate
        const accuracy = this.solutionAccuracy(true)

        let stateToString = () => "t = " + (t.toLocaleString(undefined, {maximumFractionDigits:3})) +
            " prevTime = " + (figure.prevTime !== undefined ? figure.prevTime.toLocaleString(undefined,
                {maximumFractionDigits: 3}) : 'undefined') +
            " nextTime = " + (figure.nextTime !== undefined ? figure.nextTime.toLocaleString(undefined,
                {maximumFractionDigits: 3}) : 'undefined') +
            " pendingTime = " + (figure.pendingTime !== undefined ? figure.pendingTime.toLocaleString(undefined,
                {maximumFractionDigits: 3}) : 'undefined') +
            (figure.pendingValuation !== undefined ? " (ready)" : " (unsolved)")

        if (DEBUG_TWEENING) console.log("Entering renderFrame: " + stateToString())

        let t1 = this.nextTime
        while (t1 !== undefined && t > t1) {
            if (DEBUG_TWEENING) console.log("advancing to next time segment since past " + t1)
            this.prevTime = this.nextTime
            this.prevValuation = this.nextValuation
            if (this.pendingValuation) {
                t1 = this.nextTime = this.pendingTime
                this.nextValuation = this.pendingValuation
            } else {
                if (DEBUG_TWEENING && this.pendingTime) console.log(" Ugh: losing next valuation")
                this.nextTime = this.pendingTime = undefined
                this.pendingValuation = undefined
                break
            }
            if (this.pendingTime) {
                this.endBackgroundSolve()
                this.pendingTime = undefined
                this.pendingValuation = undefined
            }
        }
        if (DEBUG_TWEENING) console.log("After stepping time: " + stateToString())

        if (this.prevTime === undefined) { // case 1
            this.prevTime = this.nextTime = this.currentTime = t
            this.setupCanvas()
            
            if (DEBUG_TWEENING) console.log("tweening case 1: no previous value to use, foreground solve (" +
                seconds(rT) + " = " + this.currentTime + ")")
            this.endBackgroundSolve()
            const valuation = this.recordUpdatedValuation(accuracy)
            this.nextValuation = valuation
            this.prevValuation = [...this.nextValuation]
            this.clearCanvas()
            this.renderFromValues()
            updateSolveTime()
            this.startBackgroundSolve(t, nextSolveTime(t), rT, frameInterval)
            if (this.backgroundSolver) (this.backgroundSolver)()
            return
        }
        if (this.nextTime === undefined) { // case 2
            this.currentTime = this.nextTime = nextSolveTime(t)
            if (DEBUG_TWEENING) console.log("tweening case 2: no next value to use, foreground solve (" +
                seconds(this.startRealTime) + "+" + seconds(rT) + ": " +
                this.currentTime + ")")

            this.endBackgroundSolve()
            this.totalIterations = 0
            this.setupCanvas() // must happen before solve because of globals
            const valuation = this.recordUpdatedValuation(accuracy)
            if (DEBUG_TWEENING) console.log("Finished foreground solve at " + seconds(new Date().getTime()))
            this.nextValuation = valuation
            this.currentTime = t
            const f = (t - this.prevTime)/(this.nextTime - this.prevTime)
            if (this.prevValuation == this.nextValuation) {
                console.error("aliased. no interpolation will happen... (case 2)")
            }
            if (sameValuation(this.prevValuation, this.nextValuation)) {
                console.error("same valuation. no interpolation will happen...")
            }
            this.currentValuation = interpolate(this.prevValuation, this.nextValuation, f)
            this.applyValuation(this.currentValuation)
            this.clearCanvas()
            this.renderFromValues()
            updateSolveTime()
        } else { // case 3 or 4
            this.currentTime = t
            const f = (t - this.prevTime)/(this.nextTime - this.prevTime)
            if (this.prevValuation == this.nextValuation) {
                console.error("aliased. no interpolation will happen...")
            }
            if (sameValuation(this.prevValuation, this.nextValuation)) {
                console.error("same valuation. no interpolation will happen...")
            }
            this.currentValuation = interpolate(this.prevValuation, this.nextValuation, f)
            if (DEBUG_TWEENING) {
              if (this.pendingTime !== undefined && this.pendingValuation !== undefined) {
                console.log("tweening case 4: tweening " + f) 
              } else {
                if (this.pendingTime) {
                    console.log("tweening case 3b: tweening " + f + "; background solve in progress")
                } else {
                    if (this.nextTime == 1) {
                        console.log("tweening case 3a: tweening " + f + " to end of frame")
                    } else {
                        console.log("tweening case 3a: tweening " + f + ", but need background solve")
                    }
                }
              }
            }
            this.applyValuation(this.currentValuation)
            this.clearCanvas()
            this.renderFromValues()
        }
        if (this.nextTime < 1 && this.pendingTime == undefined || this.pendingTime < t) {
            this.startBackgroundSolve(t, nextSolveTime(this.nextTime), rT, frameInterval)
        }
        if (this.backgroundSolver) (this.backgroundSolver)()
    }
    endBackgroundSolve() {
        if (this.backgroundSolver) {
            this.unregisterCallback("backgroundSolver")
            delete this.backgroundSolver
        }
    }
    abortBackgroundSolve() {
        this.endBackgroundSolve()
        delete this.pendingTime
    }
    startBackgroundSolve(now, target, T, frameInterval) {
        const cur = this.pendingTime, figure = this
        T = new Date().getTime()
        if (cur !== undefined) {
            if (cur < now) {
                if (DEBUG_TWEENING) console.log("aborting background solve for " + cur + " at time " + seconds(T))
                this.avgSolveTime *= 2
                this.abortBackgroundSolve()
            } else {
                console.log("already have background solve for " + cur)
                return
            }
        }
        if (DEBUG_TWEENING) console.log("Starting background solve for " + target + " at time " + seconds(T))

        this.pendingTime = target
        this.totalIterations = 0
        let counter = 0
        this.registerCallback(new SolverCallback("backgroundSolver",
            () => {
                const T1 = new Date().getTime()
                if (counter++ % 5 == 0 && T1 >= T + frameInterval) {
                    return true
                }
            }))
        let incremental = false
        figure.backgroundSolver = () => {
            if (DEBUG_TWEENING) console.log("background solve running again at " + seconds(new Date().getTime()))
            figure.currentTime = figure.pendingTime
            const accuracy = figure.solutionAccuracy(figure.pendingTime < 1),
                  solved = figure.updateValuation(accuracy, incremental)
            incremental = true

            if (!solved) {
                T = new Date().getTime()
                if (DEBUG_TWEENING) console.log("solver ran out of time at " + seconds(T) + ", next timeout at " + seconds(T + frameInterval) + ", total iterations " + figure.totalIterations)
            } else {
                if (DEBUG_TWEENING) console.log("solver finished! total iterations: " + figure.totalIterations)
                figure.unnumberVariables()
                figure.endBackgroundSolve()
                if (figure.pendingTime) figure.pendingValuation = figure.recordValuation(true)
            }
        }
    }
    // Required solution accuracy
    solutionAccuracy(animating) {
        return 1.0e-6
        // return animating ? 0.05 : 0.001
    }

    // Render the figure using the current renderValue property of variables
    renderFromValues() {
        for (const g of this.Graphics) {
            if (g.parent === undefined && g.renderIfVisible && g.active())
              g.renderIfVisible()
        }
        if (false && DEBUG_TWEENING) {
            this.ctx.strokeStyle = '#f0f';
            this.ctx.beginPath()
            this.ctx.moveTo(0,0)
            this.ctx.lineTo(this.width * this.currentTime, 0)
            this.ctx.stroke()
            this.ctx.strokeStyle = '#0f0';
            this.ctx.moveTo(0, 10)
            this.ctx.lineTo(this.width * this.renderTime, 10)
            this.ctx.stroke()
        }
    }

// Frame management. A figure can have multiple frames, each possibly with a
// duration.  Figures can be manually advanced to the next frame, or frames can
// be marked to automatically advance.

    // Create one or more new frames, returning either the single new frame or
    // an array of the new frames.
    addFrame(...names) {
        if (names.length > 1) {
            return names.flat().map(n => new Frame(this, n))
        } else {
            return new Frame(this, ...names)
        }
    }

    getFrame(i) {
        return this.Frames[i]
    }

    // Make sure there is at least one frame
    ensureFrame() {
        if (this.Frames.length == 0) {
            this.currentFrame = this.Frames[0] = new Frame(this, "default")
        }
    }

    // Mark this figure as being ready for rendering.
    // Create an initial frame if no frames have been created yet.
    ready() {
        this.ensureFrame()
        this.is_ready = true
        if (this.is_started) this.start()
    }

    // Request that this figure start rendering. If the figure
    // is not ready to render, it will just set the is_started
    // flag.
    start() {
        this.is_started = true
        if (!this.is_ready) {
            console.log("Figure is not ready to render yet.")
            return
        }
        this.ensureFrame()
        this.currentFrame = this.Frames[0]
        if (document.readyState == "complete") {
            // console.log("Document is ready, starting first frame")
            this.startCurrentFrame()
        } else {
            // console.log("Document is not ready, starting listener")
            window.addEventListener('load', () => {
                // console.log("Document loaded, starting frame")
                this.startCurrentFrame()
            })
        }
    }
    // Clear this figure and move it back to unready status
    stop() {
        if (this.is_started) {
            this.clearCanvas()
            this.is_started = false
            this.is_ready = false
        }
    }
    clearCanvas() {
        this.ctx.clearRect(0, 0, this.width, this.height)
    }
    // Stop this figure and remove it from the list of figures
    destroy() {
        if (this.is_started) this.stop()
        let f = Figures.pop()
        for (let i = 0; i < Figures.length; i++) {
            if (Figures[i] === this) Figures[i] = f
        }
    }

    // Reset this figure back to the first frame
    reset() {
        this.ensureFrame()
        this.currentFrame = this.Frames[0]
        this.renderFrame(false)
    }

    // return the next frame to f (or to the current frame if f is omitted),
    // or null if there is no next frame
    nextFrame(f) {
        f = f || this.currentFrame
        if (f === undefined) {
            return this.Frames[0]
        }
        for (let i = 0; i < this.Frames.length; i++) {
            if (this.Frames[i] == f && i + 1 < this.Frames.length) {
                return this.Frames[i+1]
            }
        }
        return null
    }

    // return the previous frame to f (or to the current frame if f is omitted)
    // or null if it's the first frame.
    prevFrame(f) {
        f = f || this.currentFrame
        if (f === undefined) return null
        for (let i = 0; i < this.Frames.length; i++) {
            if (this.Frames[i] == f && i > 0) return this.Frames[i-1]
        }
        return null
    }

    // Advance to the next frame, if any.
    // Return true if there is a next frame to go to.
    advance() {
        if (!this.is_ready) {
            console.log("Cannot advance unready figure")
            return
        }
        const f = this.nextFrame()
        if (DEBUG && f) console.log("Advancing to frame " + f.name)
        if (f) {
            this.currentFrame = f
            this.startCurrentFrame()
            return true
        } else {
            this.complete()
            if (this.repeat) {
                this.animate(1000, 80,
                  () => {
                    const col = this.fadeColor || 'white'
                    this.ctx.fillStyle = col
                    this.ctx.globalAlpha = 0.3
                    this.ctx.fillRect(0, 0, this.width, this.height)
                  },
                  () => {
                    this.ctx.globalAlpha = 1
                    this.reset()
                    this.renderFrame(false)
                  })
            }
            return false
        }
    }

    // Rewind to the previous frame, if any.
    // Return true if there is a previous frame to go to.
    rewind() {
        if (!this.is_ready) {
            console.log("Cannot rewind unready figure")
        }
        const f = this.prevFrame()
        if (f) {
            this.currentFrame = f
            this.startCurrentFrame()
            return true
        } else {
            return false
        }
    }

// Stage management. The constraint problem of a figure is broken into a
// sequence of one or more stages. By default there is only a single stage.
// Variables and constraints are associated with a stage. A constraint is only
// solved only in its stage and later stages. Variables are solved in their
// stage and are treated as fixed in later stages. Stages are not associated
// with frames; the same stages exist in every frame.

    // Add a new stage to the figure and change the current stage to that new
    // stage.  All constraints and variables created after this point will be
    // associated with the new stage (or a later one). Moving to a new stage
    // has the effect of freezing the position of everything created so far.
    freeze() {
        this.currentStage++
        this.numStages = this.currentStage + 1
    }

    setRepeat(f) {
        this.repeat = f
    }
    setFadeColor(c) {
        this.fadeColor = c
    }

    // Whether this figure is at the end of the last frame
    isComplete() {
        return (this.nextFrame() == null) && (this.currentTime >= 1 || this.currentFrame.length == 0)
    }

    // Whether this figure is at the first frame
    isReset() {
        return (!this.currentFrame || this.Frames[0] == this.currentFrame)
    }

    complete() {
        this.currentFrame = this.Frames[this.Frames.length - 1]
        this.endCurrentFrame()
    }

    /** Start an animation that takes frameLength seconds, with an interval of
     *  frameInterval ms between frames. For each frame, the function action()
     *  is called with the amount of elapsed time since the beginning of the
     *  animation. Elapsed time begins with the first return from the action().
     *  If the animation has completed, the completedAction function is called
     *  instead.
     */
    animate(frameLength, frameInterval, action, completedAction) {
        let figure = this,
            steps_rendered = 0,
            T0 = new Date().getTime()
        figure.startRealTime = T0
        const handleFrame = () => {
            steps_rendered++
            const T = new Date().getTime(), dT = T - T0
            const frac = dT/frameLength
            if (DEBUG_TWEENING) if (DEBUG_TWEENING) console.log("  step " + steps_rendered + ": " + seconds(T)
                + " (" + frac.toLocaleString(undefined, {maximumFractionDigits: 3}) + ")")
            if (frac >= 1) {
                figure.stopTimer()
                completedAction()
                if (DEBUG || REPORT_PERFORMANCE)  {
                    console.log("rendered " + steps_rendered + " steps in " + (T - T0) +
                                " ms (" + Math.round(1000*steps_rendered/(T - T0)) + "/sec)")
                }
                return
            } else {
                action(frac, dT, frameLength)
                const T1 = new Date().getTime()
                if (steps_rendered == 1) {
                    // reset the start time if necessary to give some headroom to the
                    // solver.
                    if (T1 - frameInterval > T0) {
                        figure.stopTimer()
                        if (DEBUG_TWEENING) {
                            console.log("First render was slow, resetting frame start time to " +
                                seconds(T1 - frameInterval))
                        }
                        T0 = Math.max(T0, T1 - frameInterval)
                        this.interval = setInterval(handleFrame, frameInterval)
                    }
                }
            }
        }
        this.interval = setInterval(handleFrame, frameInterval)
    }

    // Start rendering (and animating, if necessary) the current frame
    startCurrentFrame() {
        this.currentTime = 0
        delete this.components // cannot safely reuse components across frames
        this.stopTimer()
        if (!this.currentFrame) {
            console.error("no current frame")
        }
        if (this.currentFrame.length > 0) {
            if (DEBUG) {
               console.log("starting animated frame " + this.currentFrame.name + " in " + this.name)
            }
            this.startAnimatedFrame()
        } else {
            if (DEBUG) {
               console.log("starting static frame " + this.currentFrame.name + " in " + this.name)
            }
            delete this.interval
            this.renderFrame(false)
        }
    }

    startAnimatedFrame() {
        let solvePt
        this.renderTime = this.currentTime = 0
        this.prevTime = 0
        this.prevValuation = this.recordValuation()
        delete this.nextTime
        delete this.nextValuation
        delete this.pendingTime
        delete this.pendingValuation
        const frameInterval = 1000/this.frameRate // ms
        this.avgSolveTime = frameInterval * TARGET_TWEEN_FRAMES
        this.animate(this.currentFrame.length, frameInterval,
            (frac, t) => {
                this.renderTime = frac
                this.realTime = t
                this.renderFrame(true, frameInterval, this.currentFrame.length)
            },
            () => {
                this.endCurrentFrame()
            }
        )
    }

    endCurrentFrame() {
        if (this.currentFrame === undefined) return
        if (DEBUG) console.log("ending current frame")
        this.currentTime = this.renderTime = 1
        this.stopTimer()
        this.endBackgroundSolve()
        if (this.currentFrame.length > 0) this.renderFrame(false)
        if (this.nextFrame() && this.nextFrame().autoAdvance) {
            this.advance()
        }
    }

    stopTimer() {
        if (this.interval !== undefined) {
            clearInterval(this.interval)
            delete this.interval
        }
    }

    setAnimatedSolving(t) {
        this.animatedSolving = t
        if (t) {
            let counter = 0
            this.registerCallback(new SolverCallback("animateSolving",
                () => { counter++; return counter < 1000; }))
        } else {
            this.unregisterCallback("animateSolving")
        }
    }

// ---- default style control: some objects will use figure defaults if style parameters are not provided ----

    // map key->value in the current figure style
    setStyle(key, value) {
        this.currentStyle().set(key, value)
        return this
    }
    getStyle(key, required) {
        return this.currentStyle().get(key, required)
    }
    hasStyle(key) {
        return this.currentStyle().has(key)
    }

    // Set the default fill style
    setFillStyle(style) {
        return this.setStyle('fillStyle', style)
    }
    getFillStyle() {
        return this.getStyle('fillStyle')
    }

    // Set the default stroke style
    setStrokeStyle(style) {
        return this.setStyle('strokeStyle', style)
    }
    getStrokeStyle() {
        return this.getStyle('strokeStyle')
    }

    // Set the default text color/style
    setTextStyle(style) {
        return this.setStyle('textStyle', style)
    }
    // Get the default text color/style
    getTextStyle(style) {
        return this.getStyle('textStyle')
    }

    // Set the default line width
    setLineWidth(w) {
        return this.setStyle('lineWidth', w)
    }
    getLineWidth() {
        return this.getStyle('lineWidth')
    }

    // set line dash
    setLineDash(d) {
        return this.setStyle('lineDash', d)
    }
    getLineDash() {
        return this.getStyle('lineDash')
    }

    // Set the default arrow size
    setArrowSize(s) {
        return this.setStyle('arrowSize', s)
    }
    getArrowSize() {
        return this.getStyle('arrowSize')
    }

    // Set default font size
    setFontSize(s) {
        return this.setStyle('fontSize', s)
    }
    getFontSize() {
        return this.getStyle('fontSize')
    }
    // Given a style context, return the font size in
    // figure pixels.
    fontSizePixels(tc) {
        const fontSize = tc.get('fontSize')
        return this.fontSizeToPixels(fontSize)
    }
    // Convert a font size specification to figure pixels
    fontSizeToPixels(fontSize) {
        const ty = typeof fontSize
        if (ty === NUMBER) return fontSize
        if (fontSize instanceof Expression) return evaluate(fontSize)
        if (ty === STRING_STR) {
            const [str, valueStr, unit] = fontSize.match(/([0-9\.]*)(.*)/)
            const value = Number.parseFloat(valueStr)
            if (isNaN(value)) return Figure_defaults.FONT_SIZE
            switch (unit) {
                case "":
                case "px":
                    return value
                case "pt":
                    return value * (96/72)
                case "em":
                    return value * parentFontSize
                case "vh":
                    return value * visualViewport.height / 100
                case "vw":
                    return value * visualViewport.width / 100
                default: break
            }
        }
        console.error("Unrecognized font size specification: " + fontSize)
        return Figure_defaults.FONT_SIZE
    }

    // Set default font name
    setFontName(n) {
        return this.setStyle('fontName', n)
    }

    setFontStyle(sty) {
        return this.setStyle('fontStyle', sty)
    }

    getFont() {
        return new Font(this, this.currentStyle())
    }

    // Line spacing in text, as a multiplier to the font size
    setLineSpacing(s) {
        return this.setStyle('lineSpacing', s)
    }
    getLineSpacing() {
        return this.getStyle('lineSpacing')
    }

    // Inset of labels for lines
    setLineLabelInset(x) {
        return this.setStyle('lineLabelInset', x)
    }
    getLineLabelInset() {
        return this.getStyle('lineLabelInset')
    }

    // connection style ('magnet' or 'intersection')
    setConnectionStyle(s) {
        return this.setStyle('connectionStyle', s)
    }
    getConnectionStyle() {
        return this.getStyle('connectionStyle')
    }

// ---- utility functions for creating constraints ----

    costEqual(cost, ...e) {
        if (e.length == 2) return new NearZero(this, new Minus(e[0], e[1]), cost)
        const a = []
        for (let i = 1; i < e.length; i++) {
            a.push(new NearZero(this, new Minus(e[0], e[i])), cost)
        }
        return new ConstraintGroup(this, a)
    }
    equal(...e) {
        e.forEach(x => legalExpr(x))
        if (e.length == 2) {
            return new NearZero(this, this.minus(e[0], e[1]))
        }
        const a = []
        for (let i = 1; i < e.length; i++) {
            a.push(new NearZero(this, this.minus(e[0], e[i])))
        }
        return new ConstraintGroup(this, a)
    }
    geq(...args) {
        args.forEach(x => legalExpr(x))
        if (args.length == 2) return new NearZero(this, new Relu(this.minus(args[1], args[0])))
        const a = []
        for (let i = 1; i < args.length; i++) {
            a.push(new NearZero(this, new Relu(this.minus(args[i], args[i-1]))))
        }
        return new ConstraintGroup(this, a)
    }
    positive(e) {
        return this.geq(legalExpr(e), 0)
    }
    leq(...args) {
        args.forEach(x => legalExpr(x))
        if (args.length == 2) return new NearZero(this, new Relu(this.minus(args[0], args[1])))
        const a = []
        for (let i = 1; i < args.length; i++) {
            a.push(new NearZero(this, new Relu(this.minus(args[i-1], args[i]))))
        }
        return new ConstraintGroup(this, a)
    }

    // constraints to pin all the objects at the same location
    pin(...objects) {
        objects = flattenGraphics(objects)
        const r = []
        for (let i = 1; i < objects.length; i++) {
            r.push(this.equal(objects[0].x(), objects[i].x()))
            r.push(this.equal(objects[0].y(), objects[i].y()))
        }
        if (r.length == 1) return r[0]
        else return new ConstraintGroup(this, r)
    }

    // Add a hint that value v is a good initial guess for the solution to expression e.
    hint(e, v) {
        legalExpr(e)
        if (e instanceof Variable && typeof v == NUMBER) {
            e.setHint(v)
        } else {
            if (typeof v == NUMBER) {
                const variable = new Variable(this, "hint", v)
                this.equal(variable, e)
            } else if (Array.isArray(v)) {
                for (let i = 0; i < v.length; i++) {
                    const variable = new Variable(this, "hint_index_"+i, v[i])
                    this.equal(variable, new Projection(e, i, v.length))
                }
            }
        }
        return e
    }

    // Return a list of constraints that align a variable number of objects both
    // horizontal and vertically.
    // Allowed options for horizontal alignment:
    //    "none" : no alignment
    //    "left/right/center" : align left edges/center/right edges
    //    "abut" : make objects abut each other directly (see hspace() and vspace() for adding space)
    //    "distribute": objects have equal space separating them
    // Allowed options for vertical are the same except "top" and "bottom"
    //    replace "left" and "right".
    // Objects can either be passed as an array or as a variable number of arguments
    // starting from the third argument.
    align(horizontal, vertical, objlist) {
        const result = []
        if (objlist === undefined) return []
        if (!Array.isArray(objlist))
            objlist = flattenGraphics(argsToArray(arguments, 2))
        switch (horizontal) {
            case "":
            case "none": break
            case "center": 
                for (let i = 1; i < objlist.length; i++)
                    result.push(this.equal(objlist[i].x(), objlist[0].x()))
                break
            case "left":
            case "L":
                for (let i = 1; i < objlist.length; i++)
                    result.push(this.equal(objlist[i].x0(), objlist[0].x0()))
                break
            case "right":
            case "R":
                for (let i = 1; i < objlist.length; i++)
                    result.push(this.equal(objlist[i].x1(), objlist[0].x1()))
                break
            case "left right":
            case "right left":
            case "LR":
            case "RL":
                for (let i = 1; i < objlist.length; i++) {
                    result.push(this.equal(objlist[i].x0(), objlist[0].x0()))
                    result.push(this.equal(objlist[i].x1(), objlist[0].x1()))
                }
                break
            case "target":
                for (let i = 1; i < objlist.length; i++) {
                    result.push(this.equal(objlist[i].target().x(), objlist[0].target().x()))
                }
                break
            case "abut":
                for (let i = 1; i < objlist.length; i++)
                    result.push(this.equal(objlist[i-1].x1(), objlist[i].x0()))
                break
            case "distribute":
                if (objlist.length < 2) break
                const d = new Minus(objlist[1].x0(), objlist[0].x1())
                for (let i = 2; i < objlist.length; i++) {
                    result.push(this.equal(new Minus(objlist[i].x0(), objlist[i-1].x1()), d))
                    result.push(this.geq(objlist[i].x0(), objlist[i-1].x1()))
                }
                break
            default:
                console.error("Unrecognized horizontal alignment: " + horizontal)
                break
        }
        switch (vertical) {
            case "":
            case "none": break
            case "center": 
                for (let i = 1; i < objlist.length; i++)
                    result.push(this.equal(objlist[i].y(), objlist[0].y()))
                break
            case "top":
            case "T":
                for (let i = 1; i < objlist.length; i++)
                    result.push(this.equal(objlist[i].y0(), objlist[0].y0()))
                break
            case "bottom":
            case "B":
                for (let i = 1; i < objlist.length; i++)
                    result.push(this.equal(objlist[i].y1(), objlist[0].y1()))
                break
            case "top bottom":
            case "bottom top":
            case "TB":
            case "BT":
                for (let i = 1; i < objlist.length; i++) {
                    result.push(this.equal(objlist[i].y0(), objlist[0].y0()))
                    result.push(this.equal(objlist[i].y1(), objlist[0].y1()))
                }
                break
            case "target":
                for (let i = 1; i < objlist.length; i++) {
                    result.push(this.equal(objlist[i].target().y(), objlist[0].target().y()))
                }
                break
            case "abut":
                for (let i = 1; i < objlist.length; i++)
                    result.push(this.equal(objlist[i-1].y1(), objlist[i].y0()))
                break
            case "distribute":
                if (objlist.length < 2) break
                const d = new Minus(objlist[1].y0(), objlist[0].y1())
                for (let i = 2; i < objlist.length; i++) {
                    result.push(this.equal(new Minus(objlist[i].y0(), objlist[i-1].y1()), d))
                    result.push(this.geq(objlist[i].y0(), objlist[i-1].y1()))
                }
                break
            default:
                console.error("Unrecognized vertical alignment: " + vertical)
                break
        }
        return result
    }
    // keep g1 inside the bounds of g2
    keepInside(g1, g2) {
        return new ConstraintGroup(this,
            this.leq(g1.x1(), g2.x1()),
            this.leq(g1.y1(), g2.y1()),
            this.geq(g1.x0(), g2.x0()),
            this.geq(g1.y0(), g2.y0()))
    }
    // keep g1 and g2 the same size
    sameSize(...objs) {
        return new ConstraintGroup(this,
            this.equal(...objs.map(o => o.w())),
            this.equal(...objs.map(o => o.h())))
    }
    // Set the direction from g1 to g2, in degrees, where 0 degrees
    // is upward, 90 is to the right, and so forth. The direction can
    // also be given a compass point, like "N", "wsw", etc.
    direction(g1, g2, dir) {
        const dx = this.minus(g2.target().x(), g1.target().y()),
              dy = this.minus(g2.target().y(), g1.target().y())
        if (typeof dir == "string") {
            switch (dir.toLowerCase()) {
                case "n": dir = 0; break;
                case "e": dir = 90; break;
                case "s": dir = 180; break;
                case "w": dir = 270; break;
                case "ne": dir = 45; break;
                case "se": dir = 135; break;
                case "sw": dir = 225; break;
                case "nw": dir = 315; break;
                case "nne": dir = 22.5; break;
                case "ene": dir = 67.5; break;
                case "ese": dir = 112.5; break;
                case "sse": dir = 157.5; break;
                case "ssw": dir = 202.5; break;
                case "wsw": dir = 247.5; break;
                case "wnw": dir = 292.5; break;
                case "nnw": dir = 337.5; break;
                default:
                    console.error("Unknown compass point: " + dir)
                    return
            }
        }
        dir = this.times(dir, Math.PI/180)
        const dist = this.distance(g1, g2)

        return new ConstraintGroup(this,
            this.equal(dx, this.times(dist, new Sin(dir))),
            this.equal(dy, this.times(dist, new Neg(new Cos(dir)))))
    }

    after(frame, ...objs) {
        if (objs.length == 1) return new After(this, frame, objs[0])
        return objs.flat().map(o => new After(this, frame, o))
    }
    before(frame, ...objs) {
        if (objs.length == 1) return new Before(this, frame, objs[0])
        objs.flat().map(o => new Before(this, frame, o))
    }
    betweenFrames(frame1, frame2, ...objs) {
        if (objs.length == 1) return new Before(this, frame2, new After(this, frame1, objs[0]))
        objs.flat().map(o => new Before(this, frame2, new After(this, frame1, o)))
    }
    inFrame(frame, ...objs) {
        if (objs.length == 1) return new InFrame(this, frame, objs[0])
        return objs.flat().map(o => new InFrame(this, frame, o))
    }
    drawAfter(frame, ...objs) {
        if (objs.length == 1) return new DrawAfter(this, frame, objs[0])
        return objs.flat().map(o => new DrawAfter(this, frame, o))
    }
    drawBefore(frame, ...objs) {
        if (objs.length == 1) return new DrawBefore(this, frame, objs[0])
        objs.flat().map(o => new DrawBefore(this, frame, o))
    }
    drawBetween(frame1, frame2, ...objs) {
        if (objs.length == 1) return new DrawBefore(this, frame2, new DrawAfter(this, frame1, objs[0]))
        objs.flat().map(o => new DrawBefore(this, frame2, new DrawAfter(this, frame1, o)))
    }

// ---- Utility methods for creating figure objects ----

    canvasRect() {
        return new CanvasRect(this.figure)
    }
    margin(n) {
        return new CanvasRect(this.figure).inset(n === undefined ? this.getLineWidth() : n)
    }
    rectangle(fillStyle, strokeStyle, lineWidth, x_hint, y_hint, w_hint, h_hint) {
        return new Rectangle(this, fillStyle, strokeStyle, lineWidth, x_hint, y_hint, w_hint, h_hint)
    }
    square(fillStyle, strokeStyle, lineWidth, x_hint, y_hint, w_hint) {
        return new Square(this, fillStyle, strokeStyle, lineWidth, x_hint, y_hint, w_hint)
    }
    circle(fillStyle, strokeStyle, lineWidth, x_hint, y_hint, w_hint) {
        return new Circle(this, fillStyle, strokeStyle, lineWidth, x_hint, y_hint, w_hint)
    }
    ellipse(fillStyle, strokeStyle, lineWidth, x_hint, y_hint, r_hint) {
        return new Ellipse(this, fillStyle, strokeStyle, lineWidth, x_hint, y_hint, r_hint)
    }
    polygon(...points) {
        return new Polygon(this, points)
    }
    closedCurve(...points) {
        return new ClosedCurve(this, points)
    }
    line(start, end, strokeStyle, lineWidth) {
        return new Line(this, start, end, strokeStyle, lineWidth)
    }
    horzLine(start, end, strokeStyle, lineWidth) {
        if (!(start instanceof LayoutObject) && arguments.length == 2) {
            strokeStyle = start
            lineWidth = end
            start = this.point()
            end = this.point()
        }
        return new HorzLine(this, start, end, strokeStyle, lineWidth)
    }
    vertLine(start, end, strokeStyle, lineWidth) {
        if (!(start instanceof LayoutObject) && arguments.length == 2) {
            strokeStyle = start
            lineWidth = end
            start = this.point()
            end = this.point()
        }
        return new VertLine(this, start, end, strokeStyle, lineWidth)
    }
    hspace(w, unit) {
        if (unit === undefined || unit == "px") return new HSpace(this, w)
        let multiplier = 1
        if (typeof unit == STRING_STR) {
            switch (unit) {
                case "canvas": multiplier = this.canvasRect().w(); break;
                case "em": multiplier = this.getFontSize(); break;
                default:
                    console.error("Unrecognized unit: " + unit);
                    break;
            }
        } else if (unit instanceof LayoutObject) {
            multiplier = unit.w()
        } else {
            console.error("Unrecognized unit: " + unit);
        }
        return new HSpace(this, this.times(multiplier, w))
    }
    vspace(h, unit) {
        if (unit === undefined || unit == "px") return new VSpace(this, h)
        let multiplier = 1
        if (typeof unit == STRING_STR) {
            switch (unit) {
                case "canvas": multiplier = this.canvasRect().h(); break;
                case "em": multiplier = this.getFontSize(); break;
                default:
                    console.error("Unrecognized unit: " + unit);
                    break;
            }
        } else if (unit instanceof LayoutObject) {
            multiplier = unit.h()
        } else {
            console.error("Unrecognized unit: " + unit);
        }
        return new VSpace(this, this.times(multiplier, h))
    }
    box() { return new Box(this) }
    text(...t) { return createText(...t) }
    superscript(...t) {
        return new SuperscriptText(createText(...t))
    }
    subscript(...t) {
        return new SubscriptText(createText(...t))
    }
    italic(...t) {
        return new ItalicText(createText(...t))
    }
    bold(...t) {
        return new BoldText(createText(...t))
    }
    numericText(e, digits) {
        if (digits === undefined) digits = 2
        const fig = this
        return new ComputedText(() =>
                        fig.currentValuation
                            ?  createText(fig.evaluate(e).toFixed(digits))
                            :  createText("###"))
    }
    fontName(name, ...t) {
        return this.textContext(tc => {
            return tc.set('fontName', name)
        }, ...t)
    }
    fontSize(size, ...t) {
        return this.textContext(tc => {
            return tc.set('fontSize', size)
        }, ...t)
    }
    textColor(c, ...t) {
        return this.textContext(tc => tc.set('fillStyle', c), ...t)
    }
    hyphen() {
        return new Hyphen()
    }
    br() {
        return new LineBreak()
    }
    word(w) {
        return new WordText(w)
    }
    whitespace() {
        return new Whitespace()
    }
    negspace(offset) {
        return new NegSpace(offset)
    }
    currentStyle() {
        return this.style
    }
    saveStyle() {
        this.style = new Context(this.style)
    }
    restoreStyle() {
        if (this.style.parent) {
            this.style = this.style.parent
        } else {
            console.error("Cannot pop last context from the context stack")
        }
    }
    withStyle(styles, cmd) {
        this.saveStyle()
        for (let key in styles) {
            this.setStyle(key, styles[key])
        }
        cmd()
        this.restoreStyle()
    }

    textContext(f, ...t) {
        return new ContextTransformer(tc => f(new Context(tc)), createText(...t))
    }
    textFrame(txt, fillStyle) {
        if (txt && !(txt instanceof ContainedText)) txt = new ContainedText(this, txt)
        return new TextFrame(this, txt, fillStyle)
    }
    label(text, fontSize, fontName, fillStyle) {
        return new Label(this, text, fontSize, fontName, fillStyle)
    }
    // deprecated for client use
    lineLabel(string, position, offset) {
        if (string && typeof string != STRING_STR && !(string instanceof Graphic)
            && string.constructor != ContainedText) {
            string = new ContainedText(this, string)
        }
        return new LineLabel(this, string, position, offset)
    }
    handle(style) {
        return new Handle(this, style)
    }
    connector(...objects) {
        return new Connector(this, ...objects)
    }
    DOMElement(id) {
        return new DOMElementBox(this, id)
    }
    group(...objects) {
        objects = flattenGraphics(objects)
        return new Group(this, ...objects)
    }
    linear(frame, e1, e2) {
        return new LinearInterpolation(this, frame, e1, e2)
    }
    smooth(frame, e1, e2) {
        return new SmoothInterpolation(this, frame, e1, e2)
    }
    variable(name, hint) {
        return new Variable(this, name, hint)
    }
    /** Select a component of an array-valued expression like a point or
     *  or graphical object. n is the size of the array, which is 2 by default.
     */
    projection(expr, i, n) {
        if (expr instanceof LayoutObject) {
            if (i == 0) return expr.x()
            if (i == 1) return expr.y()
        }
        if (n == undefined) n = 2
        return new Projection(expr, i, n)
    }

    // Create a point with variables for its coordinates
    point() {
        if (arguments.length == 2) {
            return new Point(legalExpr(arguments[0]), legalExpr(arguments[1]))
        } else {
            if (arguments.length != 0) {
                console.error("point(...) expects 0 or 2 arguments")
            }
            const x = this.variable("px"), y = this.variable("py")
            return new Point(x, y)
        }
    }
    advanceButton() {
        return new AdvanceButton(this)
    }
    makeGraph() {
        if (!Constrain.Graph) {
            alert("Can't find Graph class. Did you forget to load constrain-graph.js?")
            return
        }
        const g = new Constrain.Graph(this)
        this.Graphs.push(g)
        return g
    }

    arrObjects(n, f) {
        const result = []
        for (let i = 0; i < n; i++) result.push(f(i))
        return result
    }

// ---- Utility methods for creating expressions ----

    plus(...args) {
        return plus(...args)
    }
    minus(x, y) {
        if (y === 0) return x
        if (typeof x == NUMBER && typeof y == NUMBER) return x - y
        return new Minus(legalExpr(x), legalExpr(y))
    }
    times(...args) {
        return times(...args)
    }
    divide(x, y) {
        if (typeof x == NUMBER && typeof y == NUMBER) return x / y
        return new Divide(legalExpr(x), legalExpr(y))
    }
    abs(e) { return new Abs(legalExpr(e)) }
    max(...args) {
        args = args.flat().map(a => legalExpr(a))
        return new Max(...args)
    }
    min(...args) {
        args = args.flat().map(a => legalExpr(a))
        return new Min(...args)
    }
    conditional(cond, epos, eneg) {
        return new Conditional(cond, epos, eneg)
    }
    sqrt(x) { return (typeof x == NUMBER) ? Math.sqrt(x) : new Sqrt(legalExpr(x)) }
    sq(x) { return new Sq(legalExpr(x)) }
    sin(x) { return (typeof x == NUMBER) ? Math.sin(x) : new Sin(legalExpr(x)) }
    cos(x) { return (typeof x == NUMBER) ? Math.cos(x) : new Cos(legalExpr(x)) }
    average(...args) {
        const n = args.length
        if (n == 0) return 0
        if (n == 1) return legalExpr(args[0])
        if (n == 2) {
            return new Average(legalExpr(args[0]), legalExpr(args[1]))
        }
        return plus(times(1/n, args[0]), times((n-1)/n, this.average(...args.slice(1))))
    }
    distance(p1, p2, dims) { return new Distance(legalExpr(p1), legalExpr(p2), dims) }
    nearZero(e, cost) { return new NearZero(this, legalExpr(e), cost) }
    constraintGroup(...c) { return new ConstraintGroup(this, ...c) }
    // constraint that (p1 -> p2) is perpendicular to (p3->p4)
    perpendicular(p1, p2, p3, p4) {
        let v1 = new Minus(legalExpr(p2), legalExpr(p1)), v2 = new Minus(legalExpr(p4), legalExpr(p3))
        return new NearZero(this,
            plus(times(new Projection(v1, 0, 2), new Projection(v2, 0, 2)),
                 times(new Projection(v1, 1, 2), new Projection(v2, 1, 2))))
    }

// dy1/dx1 = dy2/dx2 <==> dy1*dx2 = dy2 * dx1
    collinear() {
      switch (arguments.length) {
        case 0: case 1: case 2: console.error("collinear expects at least 3 points"); return;
        case 3:
            let p0 = arguments[0], p1 = arguments[1], p2 = arguments[2]
            return this.equal(
                times(this.minus(p1.y(), p0.y()), this.minus(p2.x(), p0.x())),
                times(this.minus(p2.y(), p0.y()), this.minus(p1.x(), p0.x())))
        default:
          let result = []
          for (let i = 2; i < arguments.length; i++) {
            result.push(this.collinear(arguments[0], arguments[1], arguments[i]))
          }
          return new ConstraintGroup(this, ...result)
      }
    }

    between(p0, p1, p2) {
        let a = this.variable("a", 0.5), b = this.minus(1, a)
        return new ConstraintGroup(this,
            this.geq(a, 0),
            this.leq(a, 1),
            this.equal(p0.x(), this.plus(this.times(a, p1.x()), this.times(b, p2.x()))),
            this.equal(p0.y(), this.plus(this.times(a, p1.y()), this.times(b, p2.y())))
        )
    }
// dy1/dx1 = dy2/dx2 <==> dy1*dx2 = dy2 * dx1
// make p0-p1 parallel to p2-p3
    parallel(p0, p1, p2, p3) {
        return this.equal(
          this.times(this.minus(p1.y(), p0.y()), this.minus(p3.x(), p2.x())),
          this.times(this.minus(p3.y(), p2.y()), this.minus(p1.x(), p0.x())))
    }

    // The position (x,y) in a coordinate system in which
    // a is the origin and b is (1,0)
    relative(x, y, a, b) {
        x = legalExpr(x); y = legalExpr(y); a = legalExpr(a); b = legalExpr(b)
        let dx = this.minus(b, a),
            dy = new Point(new Projection(dx, 1, 2), new Neg(new Projection(dx, 0, 2))),
            pos = this.plus(a, new Times(x, dx), new Times(y, dy))
        return this.point(new Projection(pos, 0, 2), new Projection(pos, 1, 2))
    }
    // Signed distance from point p0 to the line p1 -> p2.
    // Distance is negative if the point is on the left side of the line
    // and positive if on the right side.
    ptToLineDist(p0, p1, p2) {
        const f = this
        const tl = f.times(f.minus(f.projection(p1, 0), f.projection(p0, 0)),
                           f.minus(f.projection(p2, 1), f.projection(p1, 1)))
        const tr = f.times(f.minus(f.projection(p1, 1), f.projection(p0, 1)),
                            f.minus(f.projection(p2, 0), f.projection(p1, 0)))
        const rad = f.plus(f.sq(f.minus(f.projection(p2, 0), f.projection(p1, 0))),
                           f.sq(f.minus(f.projection(p2, 1), f.projection(p1, 1))))
        return f.divide(f.minus(tr, tl), f.sqrt(rad))
    }
}

function terms(expr) {
    if (expr instanceof Plus) {
        return terms(expr.e1).concat(terms(expr.e2))
    } else {
        return [expr]
    }
}

function plus(...args) {
    args = args.flat().map(a => legalExpr(a)).filter(x => x !== 0)
    args = args.flatMap(x => terms(x))
    const nums = args.filter(x => NUMBER == typeof x),
          nonnums = args.filter(x => NUMBER != typeof x),
          sum = nums.reduce((x,y) => x+y, 0)
    switch (nonnums.length) {
        case 0: return sum
        case 1: return sum == 0 ? nonnums[0] : new Plus(sum, nonnums[0])
        default: return sum == 0 ? new Plus(nonnums[0], plus(...nonnums.slice(1)))
                                : new Plus(sum, plus(...nonnums))
    }
}

function times(...args) {
    args = args.flat().map(a => legalExpr(a)).filter(x => x !== 1)
    const nums = args.filter(x => NUMBER == typeof x)
    const nonnums = args.filter(x => NUMBER != typeof x)
    const product = nums.reduce((x,y) => x*y, 1)
    switch (nonnums.length) {
        case 0: return product
        case 1: return product == 1 ? nonnums[0] : new Times(product, nonnums[0])
        default: return product == 1 ? new Times(nonnums[0], times(...nonnums.slice(1)))
                                     : new Times(product, times(...nonnums))
    }
}

function isFigure(figure) {
    return (figure.connector !== undefined)
}

// A callback that the solver will invoke if registered via Figure.registerCallback()
class SolverCallback {
    constructor(name, f) {
        this.name = name
        this.fun = f
    }
    call(it, x0, f0, g0, H1) {
        return (this.fun)(it, x0, f0, g0, H1)
    }
}

// Return which Figure is associated with element e, or null if
// none (for example, if e is not a canvas or (somehow) inside a canvas).
function canvasToFigure(e) {
    while (e != null) {
        if (e.nodeName == "CANVAS") break
        e = e.parentElement
    }
    if (e == null) return null
    for (let i = 0; i < Figures.length; i++) {
        if (Figures[i].canvas == e) return Figures[i]
    }
    return null
}

function getFigureByName(name) {
    for (const fig of Figures) {
        if (fig.name == name) return fig
    }
    return undefined
}

// add event listeners for touch events in canvases
function setupTouchListeners() {
    window.addEventListener('touchstart',
        e => {
            const figure = canvasToFigure(e.target)

            if (!figure || figure.interactives.length == 0) return true
            const t = e.targetTouches,
                  r = figure.canvas.getClientRects()[0],
                  touch = t.item(0),
                  x = touch.clientX - r.left,
                  y = touch.clientY - r.top
            for (let i = 0; i < figure.interactives.length; i++) {
                const h = figure.interactives[i]
                if (!h.mousedown(x, y, e)) {
                    e.preventDefault()
                    e.stopImmediatePropagation()
                    return false
                }
            }
            return true
        }, {passive: false})

    window.addEventListener('touchmove',
        e => {
            const figure = canvasToFigure(e.target)
            if (!figure || figure.interactives.length == 0) return true
            const t = e.targetTouches,
                  r = figure.canvas.getClientRects()[0],
                  touch = t.item(0),
                  x = touch.clientX - r.left,
                  y = touch.clientY - r.top
            if (!figure.focused) return true
            e.preventDefault()
            e.stopImmediatePropagation()
            return figure.focused.mousemove(x, y, e)
        }, {passive: false})

    window.addEventListener('touchend',
        e => {
            const figure = canvasToFigure(e.target)
            if (!figure || figure.interactives.length == 0) return true
            if (!figure.focused) return true
            e.preventDefault()
            e.stopImmediatePropagation()
            return figure.focused.mouseup(e)
        }, {passive: false})
}

function partition(a, l, r) {
    const p = a[l] // better: swap a[l] with random element first
    let i = l, j = r
    j--
    while (a[j] > p) j--
    while (i < j) {
        const t = a[i]; a[i] = a[j]; a[j] = t
        i++
        while (a[i] < p) i++
        j--
        while (a[j] > p) j--
    }
    return j+1
}

// Adapted from numeric-1.2.6.js to allow f to supply the gradient directly. Uses
// various functions from that package.
//
// Returns: a local minimum of a function f(x) whose gradient is g(x), using, by default,
//   the BFGS minimization algorithm. (Other algorithms can be selected using
//   setMinimizationAlgorithm.)
// Requires: fg(x) or fg(x, false) must return just f(x),
//   fg(x, true) must return [ f(x), (grad f)(x)] or [f(x0), undefined]. In the former case,
//   (grad f) must return an array whose length is the same as x. In the latter
//   case, a numeric gradient is computed using f, probably more expensively.
//   If the computed gradient is infinite or contains NaN, the search terminates.
// Effects: if callback is a function, it is invoked on each iteration of the algorithm.
//    If it returns true, the search for the local minimum halts.
function uncmin(fg, x0, callback, options) {
    if (options === undefined) options = {}
    const tol = Math.max(options.tol || 1e-8, numeric.epsilon),
          maxit = options.maxIterations || 1000

    const gradient = x => gradient(fg, x)
    x0 = numeric.clone(x0)
    const n = x0.length
    let [f0, g0] = fg(x0, true)
    let f1, g1, df0
    if (isNaN(f0))
        throw new Error('uncmin: f(x0) is a NaN!')
    const idn = numeric.identity(n)
    const max = Math.max,
        norm2 = numeric.norm2
    if (options.Hinv && wrongSizedInvHessian(n, options.Hinv)) {
        throw new Error("Inverse Hessian has wrong dimensions")
    }
    let step, H1 = options.Hinv || mul(numeric.identity(n), options.stepSize || 1)

    let it = 0,
        i, s, x1, y, ys, Hs, i0, t, nstep, t1, t2,
        m, v // ADAM
    let overshoot = options.overshoot || 0.1
    let msg = ""
    if (algorithm == UNCMIN_ADAM) {
        m = getZeros(n)
        v = getZeros(n)
    }
    let hist, y_hist, s_hist, rho // L-BFGS
    if (algorithm == UNCMIN_LBFGS) {
        if (options.Hinv) {
            // console.log("Hinv = ", options.Hinv)
            hist = options.Hinv.hist
            y_hist = options.Hinv.y_hist
            s_hist = options.Hinv.s_hist
            rho = options.Hinv.rho
        } else {
            console.log("fresh L-BFGS, initializing Hinv")
            hist = 0 // the m of L-BFGS
            y_hist = []; s_hist = []; rho = [] // length of each is hist
        }
    }
    while (it < maxit) {
        if (!all(isFinite(g0))) {
            msg = BAD_GRADIENT
            break
        }
        t = 1.0
        switch (algorithm) {
            case UNCMIN_BFGS:
            case UNCMIN_DFP:
                step = neg(dot(H1, g0))
                break
            case UNCMIN_LBFGS: {
                    let q = g0
                    const alpha = new Array(hist)
                    for (let i = hist-1; i >= 0; i--) {
                        alpha[i] = rho[i] * dot(s_hist[i], q)
                        q = sub(q, mul(alpha[i], y_hist[i]))
                    }
                    const gamma = // use rho for numerator?
                        hist > 0 ? dot(s_hist[hist-1], y_hist[hist-1])/dot(y_hist[hist-1], y_hist[hist-1])
                                 : 1
                    let z = mul(gamma, q)
                    for (let i = 0; i < hist; i++) {
                        const beta_i = rho[i] * dot(y_hist[i], z)
                        z = add(z, mul(s_hist[i], alpha[i] - beta_i))
                    }
                    step = neg(z)
                }

                break
            case UNCMIN_GRADIENT:
                step = neg(g0)
                break
            case UNCMIN_ADAM:
                m = add(mul(ADAM_BETA1, m), mul(1 - ADAM_BETA1, g0))
                v = add(mul(ADAM_BETA2, v), mul(1 - ADAM_BETA2, mul(g0, g0)))
                step = div(mul(-t, m), add(sqrt(v), ADAM_EPSILON))
                break
        }

        if (!all(isFinite(step))) {
            msg = BAD_SEARCH_DIRECTION
            break
        }
        nstep = norm2(step)
        // console.log("  iteration " + it + ": f0 = " + f0 + ", size of Newton step = " + nstep)
        if (nstep < tol) {
            msg = "Newton step smaller than tol"
            break
        }
        df0 = dot(g0, step)
        // line search
        x1 = x0
        while (it < maxit) {
            if (t * nstep < tol) {
                break
            }
            s = mul(step, t)
            x1 = add(x0, s)
            f1 = fg(x1)
            if (algorithm != UNCMIN_ADAM && f1 - f0 >= overshoot * t * df0 || isNaN(f1)) {
                t *= 0.5
                it++
                continue
            }
            break
        }
        if (t * nstep < tol/10) {
            msg = "Line search step size smaller than tol"
            break
        }
        if (it === maxit) {
            msg = "maxit reached during line search"
            break
        }
        [f1, g1] = fg(x1, true)
        if (g1 === undefined) g1 = gradient(x1)
        switch (algorithm) {
            case UNCMIN_BFGS: {
                y = sub(g1, g0)
                ys = dot(y, s)
                if (ys <= 0) {
                    H1 = numeric.identity(n) // inverse Hessian looks broken, restart
                    console.log("resetting inverse Hessian estimate")
                } else {
                    const Hy = dot(H1, y)
                    H1 = sub(add(H1,
                                mul((ys + dot(y, Hy)) / (ys * ys),
                                    tensor(s, s))),
                            div(add(tensor(Hy, s), tensor(s, Hy)), ys))
                }
            }
            break

            case UNCMIN_DFP: {
                y = sub(g1, g0)
                const ys = dot(y, s)
                const yHy = dot(y, Hy),
                    t1 = mul(tensor(Hy, Hy), -1/yHy),
                    t2 = mul(ys, tensor(s,s))
                H1 = add(add(H1, t1), t2)
            }
            break

            case UNCMIN_LBFGS: {
                y = sub(g1, g0)
                s_hist.push(s)
                y_hist.push(y)
                rho.push(1/dot(y, s))
                hist++
                if (hist > options.LBFGS_M) {
                    s_hist.shift()
                    y_hist.shift()
                    rho.shift()
                    hist--
                }
            }

            default: break
        }
        x0 = x1
        f0 = f1
        g0 = g1
        it++
        if (typeof callback === FUNCTION) {
            if (callback(it, x0, f0, g0, H1)) {
                msg = CALLBACK_RETURNED_TRUE
                break
            }
        }
    }
    if (algorithm == UNCMIN_LBFGS) {
        H1 = { hist: hist, s_hist: s_hist, y_hist: y_hist, rho: rho }
    }
    return {
        solution: x0,
        f: f0,
        gradient: g0,
        invHessian: H1,
        iterations: it,
        message: msg
    }
}

// A frame of the animation. Frames can auto-advance
// to the next frame or require manual advancing.
// frame.index gives the index of the frame in the
// current figure.
class Frame {
    constructor(figure, name) {
        if (name === undefined) name = figure.Frames.length
        if (!isFigure(figure)) {
            console.error("First argument to new Frame() must be a figure")
        }
        this.index = figure.Frames.length
        this.name = name
        figure.Frames.push(this)
        this.autoAdvance = false
        this.length = 0
    }
    // Set the length of this frame (ms)
    setLength(ms) {
        this.length = ms
        return this
    }
    setAutoAdvance(a) {
        this.autoAdvance = a
        return this
    }
    isAfter(f) {
        return this.index >= f.index
    }
    isBefore(f) {
        return this.index < f.index
    }
    isBeforeOrOn(f) {
        return this.index <= f.index
    }
    toString() {
        return "Frame " + this.name
    }
}

// An Expression is used to build constraints or and to express useful
// quantities in terms of the solved-for values of variables.
class Expression {
    constructor() {}
    // The value (along with, if doGrad, the gradient) of the expression
    // given the specified valuation.
    evaluate(valuation, doGrad) {
        console.error("Don't know how to evaluate this expression")
        return 0
    }
    // support for caching evaluations. Mostly not worthwhile but can pay off for
    // reused expressions.
    checkCache(valuation, doGrad) {
        doGrad = doGrad ? true : false
        if (!this.hasOwnProperty('cachedValuation')) return undefined
        if (this.cachedValuation !== valuation || doGrad > this.cachedDoGrad) {
            cacheMisses++
            return undefined
        }
        cacheHits++
        if (doGrad == this.cachedDoGrad) return this.cachedResult
        else return this.cachedResult[0]
    }
    // Record a computed value (and optionally gradient) in the cache
    recordCache(valuation, doGrad, result) {
        doGrad = doGrad ? true : false
        this.cachedValuation = valuation
        this.cachedDoGrad = doGrad
        this.cachedResult = result
        // console.log("caching " + this + " = " + result + " : valuation " + valuation)
        for (let v of exprVariables(this)) {
            // console.log("  depends on " + v)
            v.addDependent(this)
        }
        return result
    }
    clearCache() {
        delete this.cachedValuation
        delete this.cachedDoGrad
        delete this.cachedResult
    }
    // The set of variables that are needed to evaluate this expression.
    variables() { return new Set() }
    initDiff() { this.bpDiff = 0 }
    // Propagate differentials backward to dependencies
    backprop(task) {
        console.error("Don't know how to back-propagate this expression")
    }
    // Add the dependencies of this expression (but not this expression itself)
    // to a backpropagation task
    addDependencies(task) {
        console.error("Don't know how to compute dependencies for this expression")
    }
    // Returns this, but checks whether this expression can be used as a point.
    // Default: no
    isLegalPoint() {
        console.error("Not a legal point: " + this)
        return this
    }
    // Returns this, but checks whether this expression can be used as a scalar.
    // Default: yes
    isLegalScalar() {
        return this
    }
}

/** Return e if it is a legal expression; otherwise, return a
    *  legal expression and log an error message to the console.
    */
function legalExpr(e) {
    if (e instanceof Expression ||
        typeof e == NUMBER ||
        (typeof e == OBJECT_STR && Array.isArray(e))) {
            return e;
    }
    console.error("Illegal expression: " + e)
    return 0
}

// Return the current solved value of e, which is either a number or an expression
function solvedValue(e) {
    if (typeof e === NUMBER) {
        return e
    } else {
        return e.solutionValue
    }
}

// A Variable is solved for by the constraint solver.  A variable has an index 
// that determines its location in the valuation array. A variable is associated
// with a particular stage. Before that stage, its value should not be needed.
//
class Variable extends Expression {
    constructor(figure, basename, hint) {
        super()
        this.basename = basename + "_" + figure.numVariables
        this.index = figure.numVariables // overridden later by numberVariables()
        this.figure = figure             // a variable is associated with one figure
        this.stage = figure.currentStage
        this.dependents = new Set()
        figure.Variables.push(this)
        figure.numVariables++
        if (hint !== undefined) {
            this.hint = hint
        }
    }
    // Evaluate the value of a variable. If the evaluation is being done for
    // rendering, then no arguments will be provided and the value is
    // determined by its renderValue property. If the evaluation is being done
    // for solving, then 'valuation' provides the values of the variables being
    // solved by minimization (possibly via substitution) and 'doGrad'
    // specifies whether a gradient should be returned. If the variable is not
    // being solved by minimization then its value is specified by the
    // solutionValue property.
    evaluate(valuation, doGrad) {
        if (!valuation) {
            const renderValue = this.renderValue
            if (renderValue !== undefined) return renderValue
            return this.hint
                   || (console.error("undefined variable??"), 0.123)
        }
        if (this.index === undefined) {
            const substitution = this.substitution
            if (substitution) return evaluate(substitution, valuation, doGrad)
            const v = this.solutionValue
            if (v !== undefined) return v
            return this.hint
                   || (console.error("undefined solution variable??"), 0)
        }
        if (DEBUG && this.figure.activeVariables[this.index] !== this) {
            console.error("Variable index does not agree with active variables list")
        }
        if (doGrad) {
            let g = this.grad, n = valuation.length
            if (!g || g.length != n) {
                g = new Array(n).fill(0)
                g[this.index] = 1
                this.grad = g // save gradient for later
            }
            return [valuation[this.index], g]
        } else {
            const v = valuation[this.index]
            if (v === undefined) {
              console.error("undefined solution variable??")
              return 0
            } else {
                return v
            }
        }
    }
    backprop(task) {
        if (CHECK_NAN && checkNaNResult(this.bpDiff)) {
            console.error("NaN in variable bpDiff")
        }
        if (this.substitution) task.propagate(this.substitution, this.bpDiff)
    }
    addDependencies(task) {
        if (this.substitution) task.prepareBackProp(this.substitution)
    }
    setHint(v) {
        this.hint = v
    }
    setIndex(n) {
        this.index = n
    }
    // Remove this variable. Requires: no constraints mention it.
    remove() {
        const vars = this.figure.Variables
        for (let i = 0; i < vars.length; i++) {
            if (vars[i] == this) {
                vars.splice(i, 1)
                this.figure.numVariables--
                break
            }
        }
    }
    // Reset the information about how the value of this variable is determined
    removeIndex() {
        delete this.index
        delete this.directSolved
        delete this.substitution
        delete this.solvePending
    }
    toString() {
        return this.basename
    }
    variables() { return new Set().add(this) }
    variableComponent() {
        if (this.component !== undefined && this.component != this) {
            const v = this.component.variableComponent()
            this.component = v
            return v
        }
        return this
    }
    isLegalPoint() {
        return null
    }
    // record that this expressions value depends on this variable
    addDependent(expr) {
        this.dependents.add(expr)
    }
}

// This variable caches an array of zeros of the appropriate length
var zeros

// Return an array of zeros of length n. It may not be mutated. 
function getZeros(n) {
    if (zeros && zeros.length == n) return zeros
    zeros = new Array(n).fill(0)
    return zeros
}

var cacheHits = 0, cacheMisses = 0

function statistics() {
    const result = {
        cacheHits: cacheHits,
        cacheMisses: cacheMisses,
    }
    if (PROFILE_EVALUATIONS) {
        result.evaluations = evaluations
        result.evaluationCounts = evaluationCounts
    }
    return result
}

// The variables used by expression e.
function exprVariables(e) {
    if (e === undefined)
        console.error("undefined expr")
    if (e.cachedVariables) return e.cachedVariables
    if (typeof e === NUMBER || Array.isArray(e)) return new Set()
    if (!e.variables)
        console.error("no variables method")
    e.cachedVariables = e.variables()
    return e.cachedVariables
}

function similarResults(x, y) {
    if (typeof x === "number" && typeof y === "number")
        return Math.abs(x - y) < 1.0e-4
    if (typeof x != typeof y) return false
    for (let i = 0; i < x.length; i++) {
        if (!similarResults(x[i], y[i])) return false
    }
    return true
}

let evaluations = 0,
    evaluationCounts = new Map()

// The value of expression expr in the given valuation (an array of variable values).
// If doGrad is true, it returns an array [v, g] where is the value of the expression and
// g is its gradient with respect to all the variables.
// The valuation may be omitted, in which case the current value of the variable is used
// instead of what the valuation array says.
function evaluate(expr, valuation, doGrad) {
    if (PROFILE_EVALUATIONS) {
        evaluations++
        evaluationCounts.set(expr, 1 + (evaluationCounts.get(expr) || 0))
    }
    switch (typeof expr) {
        case NUMBER: return !doGrad ? expr : [ expr, getZeros(valuation.length) ]
        case FUNCTION:
            return (expr)(valuation)
        default:
            if (Array.isArray(expr)) {
                return expr.map(e => evaluate(e, valuation, doGrad))
            } else {
                if (CACHE_ALL_EVALUATIONS) {
                    if (valuation === undefined) valuation = false
                    const result1 = expr.checkCache(valuation, doGrad)
                    if (result1 !== undefined) {
                        const result2 = expr.evaluate(valuation, doGrad)
                        /*
                        if (!similarResults(result1, result2)) {
                            console.log(`Oops, results disagree: ${result1} != ${result2}`)
                            console.log(`dependencies are: ${Array.from(exprVariables(expr))}`)
                        }
                        console.log("reusing value of " + expr + " = " + result1)
                        */
                        return result1
                    }
                    const result2 = expr.evaluate(valuation, doGrad)
                    if (CHECK_NAN && checkNaNResult(result2)) {
                        console.error("result is NaN")
                    }
                    // console.log("standard caching for " + expr + " : valuation " + valuation)
                    expr.recordCache(valuation, doGrad, result2)
                    if (valuation) expr.solutionValue = result2
                    return result2
                } else {
                    const r = expr.evaluate(valuation, doGrad)
                    if (valuation) expr.solutionValue = r
                    return r
                }
            }
    }
}

function checkNaNResult(r) {
    if (Array.isArray(r)) {
        const [c, dc] = r
        if (isNaN(c)) {
            console.error("Saw NaN in computed value (with grad)")
            return true
        }
        for (let i = 0; i < dc.length; i++) {
            if (isNaN(dc[i])) {
                console.error("Saw NaN in computed gradient")
                return true
            }
        }
    } else if (isNaN(r)) {
        console.error("Saw NaN in computed value")
        return true
    }
    return false
}

function checkDiffValid(d) {
    if (typeof d === NUMBER && isNaN(d) ||
        typeof d === OBJECT_STR && (isNaN(d[0]) || isNaN(d[1])))
    {
        console.error("Asked to propagate NaN")
        return false
    }
    return true
}

// A back-propagation task. It computes the differential of a sum of functions
// wrt each subexpression at the given valuation.  Only one such task can be
// running at a given time because state is stored in expression nodes.
class BackPropagation {
    // create a task for computing differentials at the
    // specified valuation
    constructor(variables) {
        // this.exprs contains all the expressions that are in the expression
        // AST/DAG, in reverse postorder so that they can be propagated in a single
        // left-to-right pass
        this.exprs = []
        this.variables = variables
    }

    run(valuation) {
        this.valuation = valuation
        const es = this.exprs, n = valuation.length, vs = this.variables
        for (let i = 0; i < es.length; i++) {
            const e = es[i]
            if (!e.bpRoot) e.initDiff()
        }
        for (let i = es.length - 1; i >= 0; i--) {
            const e = es[i]
            if (e.solutionValue === undefined) {
                evaluate(e, valuation)
                if (CHECK_NAN) checkNaNResult(e.solutionValue)
            }
            if (e.bpDiff !== 0) {
                e.backprop(this)
            }
        }
    }

    // back-propagate the differential value d to expr
    propagate(expr, d) {
        // console.log("propagate: " + expr + " <- " + d)
        if (CHECK_NAN && typeof expr !== NUMBER && expr.bpDiff === undefined) {
            console.error("bpDiff not defined")
        }
        if (CHECK_NAN && !checkDiffValid(d)) {
            console.error("Asked to propagate invalid diff")
        }
        switch (typeof expr) {
            case NUMBER: return // nothing to do
            case FUNCTION: console.error("something is broken")
            default:
                if (expr.bpTask !== this)
                    console.error("expr does not belong to correct backprop")

                if (typeof d === NUMBER) {
                    if (Array.isArray(expr.bpDiff)) {
                        console.error("Can't update an array-valued expression with a scalar")
                    }
                    expr.bpDiff += d
                }
                else if (Array.isArray(d)) {
                    expr.bpDiff = numeric.add(expr.bpDiff, d)
                } else {
                    console.error("attempt to backpropagate something of the wrong type")
                }
                if (CHECK_NAN && isNaN(expr.bpDiff) && isNaN(expr.bpDiff[0])) {
                    console.error("oops")
                }
        }
    }
    // Add this expression as something to minimize
    addTask(expr, cost) {
        this.prepareBackProp(expr)
        if (isNaN(cost)) {
            console.error("cost is not a number!?")
        }
        expr.bpDiff = cost
        expr.bpRoot = true
    }
    // Add this expression to the backpropagation task, along
    // with its dependencies.
    prepareBackProp(expr) {
        if (typeof expr === NUMBER) return
        if (expr.bpTask === this) return // already visited
        expr.bpTask = this
        expr.addDependencies(this)
        this.exprs.push(expr)
    }
}

function union(...s) {
    const result = new Set()
    for (let i = 0; i < s.length; i++) {
        for (const e of s[i]) result.add(e)
    }
    return result
}

const precedence = { "avg": 0, "binop": 0, "+" : 1, "-": 1, "*": 2, "/": 2 }

// A binary expression like +, *, -, /
class BinaryExpression extends Expression {
    constructor(e1, e2) {
        super()
        if (e1 === undefined) console.error("undefined e1")
        if (e2 === undefined) console.error("undefined e2")
        this.e1 = legalExpr(e1)
        this.e2 = legalExpr(e2)
        this.precedence = precedence[this.opName()]
        return this
    }
    toString() {
        const s1 = (this.e1.precedence && this.e1.precedence < this.precedence) ? "(" + this.e1 + ")" : this.e1
        const s2 = (this.e2.precedence && this.e2.precedence < this.precedence) ? "(" + this.e2 + ")" : this.e2
        return s1 + " " + this.opName() + " " + s2
    }
    opName() { return "binop" }
    evaluate(valuation, doGrad) {
        if (!doGrad || !this.gradop)
            return this.operation(evaluate(this.e1, valuation), evaluate(this.e2, valuation))
        const [a, da] = evaluate(this.e1, valuation, true)
        const [b, db] = evaluate(this.e2, valuation, true)
        CHECK_NAN && checkNaNResult(a)
        CHECK_NAN && checkNaNResult(b)
        return this.gradop(a, b, da, db)
    }
    addDependencies(task) {
        task.prepareBackProp(this.e1)
        task.prepareBackProp(this.e2)
    }
    variables() {
       return union(exprVariables(this.e1), exprVariables(this.e2))
    }
}

// An expression x - y
class Minus extends BinaryExpression {
    constructor(e1, e2) { super(e1, e2) }
    operation(a, b) { return numeric.sub(a, b) }
    gradop(a, b, da, db) {
        return [numeric.sub(a, b), numeric.sub(da, db)]
    }
    backprop(task) {
        task.propagate(this.e1, this.bpDiff)
        task.propagate(this.e2, numeric.neg(this.bpDiff))
    }
    opName() { return "-" }
}

// An expression x + y
class Plus extends BinaryExpression {
    constructor(e1, e2) { super(e1, e2) }
    operation(a, b) { return numeric.add(a, b) }
    gradop(a, b, da, db) { return [numeric.add(a, b), numeric.add(da, db)] }
    isLegalPoint() {
        if (legalPoint(this.e1) && legalPoint(this.e2)) return this
        return null
    }
    backprop(task) {
        task.propagate(this.e1, this.bpDiff)
        task.propagate(this.e2, this.bpDiff)
    }
    opName() { return "+" }
}

// The average of two numbers or points
class Average extends BinaryExpression {
    constructor(e1, e2) { super(e1, e2) }
    operation(a, b) { return numeric.mul(0.5, numeric.add(a, b)) }
    gradop(a, b, da, db) {
        return [ numeric.mul(0.5, numeric.add(a, b)), numeric.mul(numeric.add(da, db), 0.5) ]
    }
    backprop(task) {
        task.propagate(this.e1, numeric.mul(0.5, this.bpDiff))
        task.propagate(this.e2, numeric.mul(0.5, this.bpDiff))
    }
    opName() { return "avg" }
    x() { return new Projection(this, 0, 2) }
    y() { return new Projection(this, 1, 2) }
    h() { return 0 }
    w() { return 0 }
}

// An expression x * y
class Times extends BinaryExpression {
    constructor(e1, e2) { super(e1, e2) }
    operation(a, b) { return numeric.mul(a, b) }
    gradop(a, b, da, db) {
        return [ a * b, numeric.add(numeric.mul(a, db), numeric.mul(b, da)) ]
    }
    backprop(task) {
        const a = solvedValue(this.e1),
              b = solvedValue(this.e2),
              d = this.bpDiff
        task.propagate(this.e1, numeric.dot(d,b))
        task.propagate(this.e2, numeric.dot(d,a))
    }
    opName() { return "*" }
    isLegalPoint() {
        if (legalPoint(this.e1) && legalScalar(this.e2)
         || legalPoint(this.e2) && legalScalar(this.e1)) {
            return this
        }
        return null
    }
}

// An expression x / y
class Divide extends BinaryExpression {
    constructor(e1, e2) { super(e1, e2) }
    operation(a, b) {
        if (b === 0) console.log("warning: divide by zero, using random answer")
        return b === 0 ? Math.random() - 0.5 : a / b }
    gradop(a, b, da, db) {
        return [a / b, numeric.add(numeric.mul(-a/(b*b), db),  numeric.mul(da, 1/b))]
    }
    backprop(task) {
        // d/da (a / b) = 1/b
        // d/db (a / b) = a * d/db(1/b) = a * (-1/b^2) = -a/b^2
        const a = solvedValue(this.e1),
              b = solvedValue(this.e2),
              ib = (b === 0) ? Math.random() - 0.5 : 1/b,
              d = this.bpDiff
        if (b === 0) console.log("warning: divide by zero, using random answer")
        task.propagate(this.e1, ib*d)
        task.propagate(this.e2, numeric.mul(a, -ib*ib*d))
    }
    opName() { return "/" }
}

// An expression that expects an arbitrary number of arguments.
class NaryExpression extends Expression {
    constructor(...arglist) {
        super()
        this.args = arglist.flat()
    }
    evaluate(valuation, doGrad) {
        const vals = this.args.map(e => evaluate(e, valuation, doGrad))
        if (doGrad) return this.gradop(vals)
        else return this.operation(vals)
    }
    variables() {
        let result = new Set()
        this.args.forEach(e => { result = union(result, exprVariables(e)) })
        return result
    }
    backprop(task) { // for ops like min and max that depend on only on argument this.which
        const n = this.args.length, d = this.bpDiff
        task.propagate(this.args[this.which], d)
    }
    addDependencies(task) {
        this.args.forEach(e => task.prepareBackProp(e))
    }
}

// The minimum of some number of arguments.
class Min extends NaryExpression {
    constructor(...args) { super(...args) }
    operation(vals) {
        let best = vals[0], n = vals.length, besti = [0]
        for (let i = 1; i < n; i++) {
            if (best > vals[i]) {
                best = vals[i]
                besti = [i]
            } else if (best == vals[i]) {
                besti.push(i)
            }
        }
        if (besti.length == 1) {
            this.which = besti[0]
        } else {
            this.which = besti[Math.floor(Math.random() * besti.length)]
        }
        return best
    }
    gradop(vals) {
        let [best, db] = vals[0], n = vals.length, besti = 0
        for (let i = 1; i < n; i++) {
            let [a, da] = vals[i]
            if (a < best) {
                best = a
                db = da
                besti = i
            }
        }
        this.which = besti
        return [best, db]
    }
    toString() { return "min(" + this.args + ")" }
}

// The maximum of some number of arguments.
class Max extends NaryExpression {
    constructor(...args) { super(...args) }
    operation(vals) {
        let best = vals[0], n = vals.length, besti = [0]
        for (let i = 1; i < n; i++) {
            if (best < vals[i]) {
                best = vals[i]
                besti = [i]
            } else if (best == vals[i]) {
                besti.push(i)
            }
        }
        if (besti.length == 1) {
            this.which = besti[0]
        } else {
            this.which = besti[Math.floor(Math.random() * besti.length)]
        }
        return best
    }
    gradop(vals) {
        let [best, db] = vals[0], n = vals.length, besti = 0
        for (let i = 1; i < n; i++) {
            let [a, da] = vals[i]
            if (a > best) {
                best = a
                db = da
                besti = i
            }
        }
        this.which = besti
        return [best, db]
    }
    toString() { return "max(" + this.args + ")" }
}

const RANDOM_ANGLE_WARNING = "Warning: zero distance, generating random angle"
const randomAngle = () => Math.random() * Math.PI * 2

// The distance between two points.
class Distance extends Expression {
    // The distance between two points.
    // The dimensionality of the points is dim (default: 2)
    constructor(p1, p2, dim) {
        super()
        this.p1 = p1
        this.p2 = p2
        this.dim = dim || 2
    }
    evaluate(valuation, doGrad) {
      if (!doGrad) {
        const p1 = evaluate(this.p1, valuation),
              p2 = evaluate(this.p2, valuation),
              rad = numeric.norm2Squared(numeric.sub(p2, p1))
        return Math.sqrt(rad)
      }
      const [p1, dp1] = evaluate(this.p1, valuation, true),
            [p2, dp2] = evaluate(this.p2, valuation, true),
            dpd = numeric.sub(dp2, dp1),
            pd = numeric.sub(p2, p1),
            rad = numeric.norm2Squared(pd),
            v = Math.sqrt(rad)
      // let xdn, ydn
      let dn
      if (v !== 0) {
        dn = numeric.mul(1/v, pd)
      } else {
        const ang = randomAngle()
        dn = [ Math.cos(ang), Math.sin(ang) ]
        for (let i = 2; i < this.dim; i++) dn.push(Math.random() - 0.5)
      }
      return [v, numeric.dot(dn, dpd)]
    }
    // Dx1(d) where rad = sqrt((x1-x2)^2 + (y1-y2)^2) is (x1-x2)/rad * dx1
    //
    // d(ab) = a db + b da
    // d(ab)/da = b
    // d(ab)/db = a
    // dO/a = dO/d(ab) * d(ab)/da = dO/d(ab) * b

    backprop(task) {
        const p1 = solvedValue(this.p1),
              p2 = solvedValue(this.p2),
              pd = numeric.sub(p2, p1),
              sd = numeric.norm2Squared(pd),
              d = this.bpDiff
        let dn
        if (sd != 0) {
            const idist = d/Math.sqrt(sd)
            dn = numeric.mul(idist, pd)
        } else {
            // positions of points are considered arbitrary, so generate a
            // differential in a random direction.
            console.log(RANDOM_ANGLE_WARNING)

            const ang = randomAngle()
            dn = [ d * Math.cos(ang) * RANDOM_GRADIENT_SCALING,
                   d * Math.sin(ang) * RANDOM_GRADIENT_SCALING ]
            for (let i = 2; i < this.dim; i++) dn.push(d * (Math.random() - 0.5))
        }
        task.propagate(this.p1, numeric.neg(dn))
        task.propagate(this.p2, dn)
    }
    addDependencies(task) {
        task.prepareBackProp(this.p1)
        task.prepareBackProp(this.p2)
    }
    variables() {
        return union(exprVariables(this.p1), exprVariables(this.p2))
    }
    toString() { return "distance(" + this.p1 + "," + this.p2 + ")" }
}

// A unary expression like -x
class UnaryExpression extends Expression {
    constructor(e) {
        super()
        this.expr = e
    }
    // The value of the expression at a
    operation(a) { console.error("Undefined unary operation") }
    // The value and gradient of the expression at a, where da is the
    // gradient of the argument.
    gradop(a, da) { console.error("Undefined unary operation") }
    evaluate(valuation, doGrad) {
        if (!doGrad) return this.operation(evaluate(this.expr, valuation))
        const [a, da] = evaluate(this.expr, valuation, true)
        return this.gradop(a, da)
    }
    variables() {
        return exprVariables(this.expr)
    }
    addDependencies(task) {
        task.prepareBackProp(this.expr)
    }
}

// Expression for an absolute value |x|
class Abs extends UnaryExpression {
    constructor(e) { super(e) }
    operation(a) { return Math.abs(a) }
    gradop(a, da) {
        if (a > 0) return [a, da]
        if (a < 0 || Math.random() < 0.5) return [-a, -da]
        return [a, da]
    }
    backprop(task) {
        const a = solvedValue(this.expr),
              d = this.bpDiff
        if (a < 0) task.propagate(this.expr, -d)
        else if (a < 0 || Math.random() < 0.5) task.propagate(this.expr, d)
        else task.propagate(this.expr, -d)
    }
    toString() {
        return "Abs(" + this.expr + ")"
    }
}

// The expression -x
class Neg extends UnaryExpression {
    constructor(e) { super(e) }
    operation(a) { return -a }
    gradop(a, da) { return [-a, -da] }
    backprop(task) {
        task.propagate(this.expr, -this.bpDiff)
    }
}

// The square root operation
class Sqrt extends UnaryExpression {
    constructor(e) { super(e) }
    operation(a) { return Math.sqrt(a) }
    gradop(a, da) {
        if (a <= 0) return [0, getZeros(da.length)]
        const s = Math.sqrt(a)
        return [s, numeric.mul(0.5/s), da]
    }
    backprop(task) {
        let a = evaluate(this.expr, task.valuation)
        const d = this.bpDiff
        if (a <= 0) {
            // console.log("Trying to take the sqrt of a nonpositive number, generating random answer")
            a = Math.random()/1000 + 0.001
        }
        task.propagate(this.expr, d * 0.5/a)
    }
    toString() {
        return "Sqrt(" + this.expr + ")"
    }
}

// Squared L2 norm
class Sq extends UnaryExpression {
    constructor(e) { super(e) }
    operation(a) { return numeric.dot(a, a) }
    gradop(a, da) {
        return [numeric.dot(a, a), numeric.mul(2, a, da)]
    }
    backprop(task) {
        const a = solvedValue(this.expr),
              d = this.bpDiff
        task.propagate(this.expr, numeric.mul(2, d, a))
    }
    toString() {
        return "Sq(" + this.expr + ")"
    }
}

// max(0,x)
class Relu extends UnaryExpression {
    constructor(e) { super(e) }
    operation(a) { if (a <= 0) return 0; else return a }
    gradop(a, da) { 
        if (a <= 0) return [0, getZeros(da.length)]
        return [a, da]
    }
    backprop(task) {
        const a = evaluate(this, task.valuation)
        if (a > 0) task.propagate(this.expr, this.bpDiff)
    }
    toString() { return "Relu(" + this.expr + ")" }
}

class Cos extends UnaryExpression {
    constructor(e) { super(e) }
    operation(a) { return Math.cos(a) }
    gradop(a, da) { return [ this.operation(a), -Math.sin(a) * da ] }
    backprop(task) {
        const a = evaluate(this, task.valuation)
        task.propagate(this.expr, -Math.sin(a) * this.bpDiff)
    }
}
class Sin extends UnaryExpression {
    constructor(e) { super(e) }
    operation(a) { return Math.sin(a) }
    gradop(a, da) { return [ this.operation(a), Math.cos(a) * da ] }
    backprop(task) {
        const a = evaluate(this, task.valuation)
        task.propagate(this.expr, Math.cos(a) * this.bpDiff)
    }
}

// A Conditional is an expression that evaluates to one expression if its condition is
// positive, and a second one otherwise.
class Conditional extends Expression {
    constructor(cond, epos, eneg) {
        super()
        this.cond = cond
        this.epos = epos
        this.eneg = eneg
    }
    evaluate(valuation, doGrad) {
        const cond = evaluate(this.cond, valuation, false)
        if (cond > 0) {
            return evaluate(this.epos, valuation, doGrad)
        } else {
            return evaluate(this.eneg, valuation, doGrad)
        }
    }
    addDependencies(task) {
        task.prepareBackProp(this.cond)
        task.prepareBackProp(this.epos)
        task.prepareBackProp(this.eneg)
    }
    initDiff() {
        this.bpDiff = 0
    }
    variables() {
        return union(union(exprVariables(this.cond), exprVariables(this.epos)),
                     exprVariables(this.eneg))
    }
    backprop(task) {
        const cond = this.cond.solutionValue
        if (cond === undefined) {
            console.error("undefined conditional guard ")
        }
        if (cond > 0) {
            task.propagate(this.epos, this.bpDiff)
        } else {
            task.propagate(this.eneg, this.bpDiff)
        }
    }
    toString() {
        return "conditional(" + this.cond + "," + this.epos + "," + this.eneg + ")"
    }
}

// A fixed value between 0 and 1 representing the
// time during the current animation frame
class Time extends Expression {
    constructor(figure) {
        super()
        this.figure = figure
    }
    evaluate(valuation, doGrad) {
        const t = this.figure.currentTime
        return doGrad ? [t, getZeros(valuation.length)] : t
    }
    variables() { return new Set() }
    backprop(task) {}
    toString() {
        return "Time"
    }
}

// A LinearInterpolation can interpolate, as a function of time, between two numbers or
// between any two expressions that evaluate to 1-D arrays, such as Points.
class LinearInterpolation extends Expression {
    constructor(figure, frame, e1, e2) {
        super()
        this.figure = figure
        this.frame = frame
        this.e1 = e1
        this.e2 = e2
    }
    interp(t) { return t }
    evaluate(valuation, doGrad) {
        const figure = this.figure, currentFrame = figure.currentFrame
        if (currentFrame.isBefore(this.frame)) {
            return evaluate(this.e1, valuation, doGrad)
        }
        if (currentFrame.isAfter(this.frame) && currentFrame != this.frame) {
            return evaluate(this.e2, valuation, doGrad)
        }
        const v1 = evaluate(this.e1, valuation, doGrad),
              v2 = evaluate(this.e2, valuation, doGrad),
              b = this.interp(this.figure.currentTime),
              a = 1 - b
        switch (doGrad ? typeof v1[0] : typeof v1) {
            case NUMBER:
                if (!doGrad) return v1 * a  + v2 * b
                return [ v1[0] * a + v2[0] * b,
                         numeric.add(numeric.mul(v1[1], a), numeric.mul(v2[1], b)) ]
            case OBJECT_STR:
                if (Array.isArray(v1)) {
                    var result = new Array(v1.length)
                    for (let i = 0; i < v1.length; i++) {
                        result[i] = numeric.add(numeric.mul(v1[i], a), numeric.mul(v2[i], b))
                    }
                    // return this.recordCache(valuation, doGrad, result)
                    return result
                }
        }
        console.error("Don't know how to interpolate between " + v1 + " and " + v2)
    }
    x() { return new Projection(this, 0, 2) }
    y() { return new Projection(this, 1, 2) }

    variables() {
        return union(exprVariables(this.e1), exprVariables(this.e2), [this.figure.timeVar])
    }
    backprop(task) {
      const figure = this.figure, currentFrame = figure.currentFrame
      if (currentFrame.isBefore(this.frame)) {
        task.propagate(this.e1, this.bpDiff)
      } else if (currentFrame.isAfter(this.frame) && currentFrame != this.frame) {
        task.propagate(this.e2, this.bpDiff)
      } else {
        const b = this.interp(this.figure.currentTime),
              a = 1 - b
        task.propagate(this.e1, numeric.mul(a, this.bpDiff))
        task.propagate(this.e2, numeric.mul(b, this.bpDiff))
      }
    }
    addDependencies(task) {
        const figure = this.figure, currentFrame = figure.currentFrame
        if (currentFrame.isBefore(this.frame) || currentFrame == this.frame)
            task.prepareBackProp(this.e1)
        if (currentFrame.isAfter(this.frame)) 
            task.prepareBackProp(this.e2)
    }
    toString() {
        return "LinearInterpolation(" + this.e1 + ", " + this.e2 + ")"
    }
}

// A cubic spline interpolator with slow out
// and slow in
class SmoothInterpolation extends LinearInterpolation {
    constructor(figure, frame, e1, e2) {
        super(figure, frame, e1, e2)
    }
    interp(t) { return cubicInterpWeight(t) }
    toString() {
        return "SmoothInterpolation(" + this.e1 + ", " + this.e2 + ")"
    }
}

function cubicInterpWeight(t) {
    return t*t*(3 - 2*t)
}

// A Projection can be used on an expression that returns an array. It
// picks out the value of the appropriate component of the array.
class Projection extends Expression {
    constructor(expr, index, n) {
        super()
        this.expr = expr
        this.index = index
        this.num = n
        if (index < 0 || index >= n) {
            console.error("Illegal index to Projection")
        }
    }
    evaluate(valuation, doGrad) {
        const v = Constrain.evaluate(this.expr, valuation, doGrad), i = this.index
        if (doGrad) {
            const [x, dx] = v
            return [x[i], dx[i]]
        } else {
            if (!Array.isArray(v))
                console.error("Projection expects its expression to have an array value: " + this.expr)
            if (i < 0 || i >= v.length)
                console.error("Attempt to project out a nonexistent element")
            return v[i]
        }
    }
    backprop(task) {
        const r = new Array(this.num).fill(0)
        r[this.index] = this.bpDiff
        task.propagate(this.expr, r)
    }
    addDependencies(task) {
        task.prepareBackProp(this.expr)
    }
    toString() { return "Projection(" + this.expr + "," + this.index + ")" }
    variables() {
        return exprVariables(this.expr)
    }
}

// A Temporal is an object that might only exist in some frames. It can be
// a Graphic or a Constraint. By default an object exists and
// is visible in every frame.
//
class Temporal {
    constructor(figure) {
        this.figure = figure
    }
    active() { return true }
    // Is this object visible in frame f?
    visible(f) {
        if (this.parent) return this.parent.visible(f)
        return true
    }
    renderIfVisible() {
        if (this.visible(this.figure.currentFrame)) this.render()
    }
}

// A TemporalFilter contains a graphical object or a constraint.
class TemporalFilter extends Temporal {
    constructor(figure, obj) {
        super(figure)
        if (Array.isArray(obj)) {
            console.error("Sorry, a Temporal can only hold one graphical object or one constraint. Use a Group or ConstraintGroup instead.")
        }
        if (!isFigure(figure)) {
            console.error("A Temporal must be constructed with a Figure")
        }
        this.obj = obj
        obj.installHolder(figure, this, obj) // tell the figure to install this object in the appropriate way
    }
    x() { return this.obj.x() }
    y() { return this.obj.y() }
    x0() { return this.obj.x0() }
    x1() { return this.obj.x1() }
    y0() { return this.obj.y0() }
    y1() { return this.obj.y1() }
    w() { return this.obj.w() }
    width() { return this.obj.width() }
    h() { return this.obj.h() }
    height() { return this.obj.height() }
    ul() { return this.obj.ul() }
    ll() { return this.obj.ll() }
    lr() { return this.obj.lr() }
    ur() { return this.obj.ur() }
    start() { return this.obj.start() }
    end() { return this.obj.end() }
    lc() { return this.obj.lc() }
    cr() { return this.obj.cr() }
    uc() { return this.obj.uc() }
    cl() { return this.obj.cl() }
    center() { return this.obj.center() }
    render() {
        this.obj.renderIfVisible()
    }
    getCost(valuation, doGrad) {
        if (this.active()) {
            return this.obj.getCost(valuation, doGrad)
        } else {
            return zeroCost(valuation, doGrad)
        }
    }
    variables() {
        if (this.active()) return this.obj.variables() 
        else return new Set()
    }
    installHolder(figure, holder, child) {
        this.obj.installHolder(figure, holder, child)
    }
    bestMagnetPt(px, py, valuation) {
        return this.obj.bestMagnetPt(px, py, valuation)
    }
    backprop(valuation) { this.obj.backprop(valuation) }
    addToTask(task) { this.obj.addToTask(task) }
}

function zeroCost(valuation, doGrad) {
    return doGrad ? [0, getZeros(valuation.length)] : 0
}

// An After wraps another object and makes it exist only on and
// after the specified frame. It can also be modified to set an
// end frame (inclusive or exclusive).
class After extends TemporalFilter {
    constructor(figure, frame, obj) {
        super(figure, obj)
        this.frame = frame
    }
    active() {
        if (this.parent && !this.parent.active()) {
            return false
        }
        if (!this.figure.currentFrame.isAfter(this.frame)) return false
        return (!this.endFrame ||
            this.figure.currentFrame.isBeforeOrOn(this.endFrame))
    }
    endWith(frame) {
        this.endFrame = frame
    }
    endBefore(frame) {
        this.endFrame = this.figure.prevFrame(frame)
    }
}

// An After wraps another object and makes it appear only on and
// after the specified frame. However, it still exists for solving
// purposes.
class DrawAfter extends TemporalFilter {
    constructor(figure, frame, obj) {
        super(figure, obj)
        this.frame = frame
    }
    visible() {
        return this.figure.currentFrame.isAfter(this.frame)
    }
    addToTask(task) {
        this.obj.addToTask(task)
    }
}

// A Before wraps another object and makes it exist only before
// the specified frame.
class Before extends TemporalFilter {
    constructor(figure, frame, obj) {
        super(figure, obj)
        this.frame = frame
    }
    active() {
        if (this.parent && !this.parent.active()) {
            return false
        }
        return !this.figure.currentFrame.isAfter(this.frame)
    }
}

// An InFrame object wraps another object and makes it exist only in
// the specified frame.
class InFrame extends TemporalFilter {
    constructor(figure, frame, obj) {
        super(figure, obj)
        this.frame = frame
    }
    active() {
        if (this.parent) {
            console.log("inFrame with a parent?")
        }
        if (this.parent && !this.parent.active()) {
            return false
        }
        return this.figure.currentFrame === this.frame
    }
}

// A Before wraps another object and makes it appear only before
// after the specified frame. However, it still exists for solving
// purposes.
class DrawBefore extends TemporalFilter {
    constructor(figure, frame, obj) {
        super(figure, obj)
        this.frame = frame
    }
    visible() {
        return !this.figure.currentFrame.isAfter(this.frame)
    }
}

// A Constraint has a cost that the system tries to minimize.
// A Constraint is associated with a Figure but might not be in
// its list of Constraints, because of ConstraintGroups.
class Constraint extends Temporal {

    // Create a constraint associated with figure.
    constructor(figure) {
        super(figure)
        if (!isFigure(figure)) {
            console.error("Constraints require an associated Figure")
            throw "no"
        }
        this.figure = figure
        this.stage = figure.currentStage
        figure.addConstraints(this)
    }
    getCost(valuation, doGrad) {
        console.error("No cost function defined for this constraint " + this)
        return zeroCost(valuation, doGrad)
    }
    addToTask(task) {
        console.error("No addToTask function defined for this constraint " + this.constructor)
        return
    }
    variables() { return new Set() }
    installHolder(figure, holder, child) {
        if (child.parent !== undefined) {
            console.error("Child Constraint already has a parent")
            return
        }
        child.parent = holder
        for (let i = 0; i < figure.Constraints.length; i++) {
            if (figure.Constraints[i] === child) {
                child.parent = holder
                break
            }
        }
        if (child.parent !== holder) {
            console.error("Child constraint not at top level")
        }
    }
    changeCost(cost) {
        this.cost *= cost
        return this
    }
    // Does this constraint need to be solved for in the specified stage, for
    // the active component? If c is omitted, checks for the whole stage
    active() {
        if (this.parent && !this.parent.active()) {
            return false
        }
        if (this.stage > this.figure.activeStage) return false
        const c = this.figure.activeComponent
        if (c === undefined) return true
        const vars = this.variables()
        let result = false
        vars.forEach(v => {
            if (v.variableComponent() === c) result = true
        })
        return result
    }
    toString() {
        return "Constraint"
    }
}

// A Loss just directly expresses the cost that
// it will report. So it can report negative costs.
class Loss extends Constraint {
    constructor(figure, expr) {
        super(figure)
        this.expr = expr
        this.cost = 1
    }
    addToTask(task) {
        task.addTask(this.expr, this.cost)
    }
    getCost(valuation, doGrad) {
      if (!doGrad) {
        const v = evaluate(this.expr, valuation)
        return v * this.cost
      } else {
        const [x, dx] = evaluate(this.expr, valuation, true)
        return [x*this.cost, numeric.mul(dx, this.cost)]
      }
    }
    variables() {
        return exprVariables(this.expr)
    }
    toString() {
        return "Loss"
    }
}

// A NearZero constraint tries to ensure that its expression is as close to
// zero as possible.
class NearZero extends Loss {
    constructor(figure, expr, cost) {
        super(figure, new Sq(expr))
        this.cost = cost || 1
    }
    toString() { return "0 ~ " + this.expr }
}

function constraintsCost(a, valuation, doGrad) {
    if (!Array.isArray(a)) console.error("constraintsCost expects an array of constraints")
    if (a.length == 0) return zeroCost(valuation, doGrad)
    if (a.length == 1) return a[0].getCost(valuation, doGrad)
    if (!doGrad) {
        let cost = 0
        a.forEach(c => { cost += c.getCost(valuation, doGrad) })
        return cost
    } else {
        let cost = 0, dc = getZeros(valuation.length)
        a.forEach(c => {
            const [cc, cd] = c.getCost(valuation, true)
            cost += cc
            dc = numeric.add(dc, cd)
        })
        return [cost, dc]
    }
}

// A group of constraints that acts like a single constraint.
class ConstraintGroup extends Constraint {
    constructor(figure, ...constraints) {
        super(figure)
        this.constraints = constraints.flat()
        this.constraints.forEach(c =>
            c.installHolder(figure, this, c)
        )
    }
    getCost(valuation, doGrad) {
        // constraint group doesn't have a cost of its own.
        if (doGrad) return [0, getZeros(valuation.length)]
        else return 0
        // return constraintsCost(this.constraints, valuation, doGrad)
    }
    variables() {
        let r = new Set()
        this.constraints.forEach(c => {
            r = union(r, c.variables())
        })
        return r
    }
    addToTask(task) {
        this.constraints.forEach(c => c.addToTask(task))
    }
    changeCost(x) {
        this.constraints.forEach(c => c.changeCost(x))
        return this
    }
    toString() {
        return "ConstraintGroup[" + this.constraints.toString() + "]"
    }
}

function half(x) {
    if (typeof x == NUMBER) return x * 0.5
    return new Times(x, 0.5)
}

// A LayoutObject does not support rendering and does not necessarily
// know what figure it is part of. It does not introduce any variables by
// default. Its size is 0 by default.
class LayoutObject extends Expression {
    constructor() { super() }
    toString() {
        return this.name ? this.constructor.name + " " + this.name : this.constructor.name
    }
    setName(name) {
        this.name = name
        return this
    }
    x() { return this.x_ }
    y() { return this.y_ }
    x0() { return new Minus(this.x(), half(this.w())) }
    x1() { return plus(this.x(), half(this.w())) }
    y0() { return new Minus(this.y(), half(this.h())) }
    y1() { return plus(this.y(), half(this.h())) }
    ul() { return new Point(this.x0(), this.y0()) }
    ur() { return new Point(this.x1(), this.y0()) }
    ll() { return new Point(this.x0(), this.y1()) }
    lr() { return new Point(this.x1(), this.y1()) }
    lc() { return new Point(this.x(), this.y1()) }
    cr() { return new Point(this.x1(), this.y()) }
    uc() { return new Point(this.x(), this.y0()) }
    cl() { return new Point(this.x0(), this.y()) }
    centerX() { return new Average(this.x0(), this.x1()) }
    centerY() { return new Average(this.y0(), this.y1()) }
    center() { return new Point(this.x(), this.y()) }
    target() { return this.center() }
    width() { return this.w() }
    height() { return this.h() }
    w() { return 0 }
    h() { return 0 }
    isLegalPoint() { return this }
    isLegalScalar() { return null }
    variables() { return new Set() }
    connectionPts() {
        return [
                new Point(this.x(), this.y()),
                new Point(this.x1(), this.y()),
                new Point(this.x0(), this.y()),
                new Point(this.x(), this.y0()),
                new Point(this.x(), this.y1())
               ]
    }
    bestMagnetPt(px, py, valuation) {
        let [x,y] = evaluate([this.x(), this.y()])
        const scs = evaluate(this.connectionPts()),
              scdirs = scs.map(p => {
                                  const [sx,sy] = p,
                                        nm = norm2d(sx - x, sy - y)
                                  return nm == 0 ? [0,0] : [(sx - x)/nm, (sy - y)/nm]
                                })
        let pn = norm2d(px - x, py - y),
            pxn = (px-x)/pn, pyn = (py-y)/pn
        let best = scs[0], bd = scdirs[0][0] * pxn + scdirs[0][1] * pyn // cos of angle
        for (let i = 1; i < scs.length; i++) {
           const d = scdirs[i][0] * pxn + scdirs[i][1] * pyn
           if (d > bd) { bd = d; best = scs[i] }
        }
        return best
    }
    // Return the intersection of the line from (x,y) to this
    // shape with the shape's boundary, as an array [x, y]
    intersectionPt(x, y, valuation) {
        let [xc, yc] = evaluate([this.target().x(), this.target().y()])
        let [x0, y0, x1, y1] = evaluate([this.x0(), this.y0(),
                                         this.x1(), this.y1()], valuation)
        if (Math.abs(x - xc) < TINY) {
            return [x, (y < yc) ? y0 : y1]
        }
        let slope = (y - yc)/(x - xc)
        let [xh, yh] = (x > xc)
            ? [x1, yc + slope * (x1 - xc)]
            : [x0, yc + slope * (x0 - xc)]
        if (yh < y1 && yh > y0) return [xh, yh]
        if (Math.abs(slope) < TINY) {
            return [ (x > xc) ? x1 : x0, y]
        }
        return (y > yc)
            ? [ xc + (y1 - yc)/slope, y1 ]
            : [ xc + (y0 - yc)/slope, y0 ]
    }

    // Return a range [x0, x1] that lies inside this object for the entirety of
    // the y range [y0, y1]. This is used to decide how to format text inside a shape.
    // Default is the full range [x0, x1]
    xSpan(y0, y1) {
        return evaluate([this.x0(), this.x1()])
    }
    render() {
        console.log("Attempted to render an object that has no rendering defined.")
    }
    renderIn(x, y, w, h) {
        console.log("Attempted to render an object that has no rendering defined.")
    }
    renderIfVisible() { }
    variables() {
        return new Set()
    }
    installHolder(figure, holder, child) {}
    // Any LayoutObject can be used as an expression, in which case it represents
    // its (x,y) position. By default, LayoutObjects cache their results.
    evaluate(valuation, doGrad) {
      const v = this.checkCache(valuation, doGrad)
      if (v) return v
      if (!doGrad) {
        const x = evaluate(this.x(), valuation),
              y = evaluate(this.y(), valuation)
        return this.recordCache(valuation, doGrad, [x, y])
      } else {
        const [x, dx] = evaluate(this.x(), valuation, true),
              [y, dy] = evaluate(this.y(), valuation, true)
        return this.recordCache(valuation, doGrad, [[x, y], [dx, dy]])
      }
    }
    backprop(task) {
        const d = this.bpDiff
        if (d.length != 2) {
            console.error("must backpropagate an (x,y) pair through a graphical object")
            return
        }
        task.propagate(this.x(), d[0])
        task.propagate(this.y(), d[1])
    }
    addDependencies(task) {
        task.prepareBackProp(this.x_)
        task.prepareBackProp(this.y_)
    }
    initDiff() {
        this.bpDiff = [0, 0]
    }

    toTop(v) {
        return new Point(this.x(), new Minus(this.y0(), legalExpr(v)))
    }
    toBottom(v) {
        return new Point(this.x(), new Plus(this.y1(), legalExpr(v)))
    }
    toLeft(v) {
        return new Point(new Minus(this.x0(), legalExpr(v)), this.y())
    }
    toRight(v) {
        return new Point(new Plus(this.x1(), legalExpr(v)), this.y())
    }
    inset(v) {
        const r = new Box(this.figure)
        this.figure.equal(r.x(), this.x())
        this.figure.equal(r.y(), this.y())
        const v2 = this.figure.times(2, legalExpr(v))
        this.figure.equal(r.w(), new Minus(this.w(), v2))
        this.figure.equal(r.h(), new Minus(this.h(), v2))
        return r
    }
    expand(v) {
        const r = new Box(this.figure)
        this.figure.equal(r.x(), this.x())
        this.figure.equal(r.y(), this.y())
        const v2 = this.figure.times(2, legalExpr(v))
        this.figure.equal(r.w(), plus(this.w(), v2))
        this.figure.equal(r.h(), plus(this.h(), v2))
        return r
    }
    // Builder to constrain both the x and y coordinates of a graphical object.
    // Arguments can be:
    //   x, y: the coordinates
    //   [x, y]: the coordinates
    //   a LayoutObject: coordinates are its x() and y()
    at() {
        if (arguments.length == 2) {
            this.figure.equal(this.x(), legalExpr(arguments[0]))
            this.figure.equal(this.y(), legalExpr(arguments[1]))
        } else if (arguments.length == 1) {
            const p = legalExpr(arguments[0])
            if (Array.isArray(p)) {
                this.figure.equal(this.x(), legalExpr(p[0]))
                this.figure.equal(this.y(), legalExpr(p[1]))
            } else {
                const o = legalPoint(p)
                this.figure.equal(this.x(), new Projection(o, 0, 2))
                this.figure.equal(this.y(), new Projection(o, 1, 2))
            }
        }
        return this
    }
    atSameSize(g) {
       this.figure.equal(this.x(), g.x())
       this.figure.equal(this.y(), g.y())
       this.figure.equal(this.w(), g.w())
       this.figure.equal(this.h(), g.h())
       return this
    }
    above(g) {
        this.figure.leq(this.y1(), g.y0())
        this.figure.equal(this.target().x(), g.target().x())
        return this
    }
    below(g) {
        this.figure.geq(this.y0(), g.y1())
        this.figure.equal(this.target().x(), g.target().x())
        return this
    }
    rightOf(g) {
        this.figure.geq(this.x0(), g.x1())
        this.figure.equal(this.target().y(), g.target().y())
        return this
    }
    leftOf(g) {
        this.figure.leq(this.x1(), g.x0())
        this.figure.equal(this.target().y(), g.target().y())
        return this
    }
    fromDirection(g, dir) {
        this.figure.direction(g, this, dir)
        return this
    }
}

Average.prototype.toTop = LayoutObject.prototype.toTop
Average.prototype.toLeft = LayoutObject.prototype.toLeft
Average.prototype.toBottom = LayoutObject.prototype.toBottom
Average.prototype.toRight = LayoutObject.prototype.toRight
Average.prototype.x0 = LayoutObject.prototype.x0
Average.prototype.x1 = LayoutObject.prototype.x1
Average.prototype.y0 = LayoutObject.prototype.y0
Average.prototype.y1 = LayoutObject.prototype.y1

// Check whether o can be used as a layout object and return it if so.
// Otherwise, log a suitable error message and return a legal layout object.
function legalLayoutObject(o) {
    if (o instanceof LayoutObject) return o
    if (o instanceof TemporalFilter) {
        const lo = legalLayoutObject(o.obj)
        return o
    }
    console.error("Not a legal graphical object: " + o)
    return new Point()
}

function legalPoint(p) {
    if (p.x && p.y) return p
    if (p instanceof Expression) return p.isLegalPoint()
    return null
}

function legalScalar(e) {
    if (typeof e == NUMBER) return e
    if (e instanceof Expression) return e.isLegalScalar()
    return null
}

// A Box is a layout object with a width and height. It does not necessarily
// render but is useful for positioning other objects, because it can be used
// with functions that expect graphical objects, such as align(). By default
// it introduces four variables to specify its position. Some subclasses choose
// to remove those variables (cf. Group).
class Box extends LayoutObject {
    constructor(figure, x_hint, y_hint, w_hint, h_hint) {
        super()
        this.figure = figure
        const prefix = this.toString() + "_"
        this.x_ = new Variable(figure, prefix + "x", x_hint)
        this.y_ = new Variable(figure, prefix + "y", y_hint)
        this.w_ = new Variable(figure, prefix + "w", w_hint)
        this.h_ = new Variable(figure, prefix + "h", h_hint)
    }
    w() { return this.w_ }
    h() { return this.h_ }
// convenience methods for positioning (by adding constraints)

    // Constrain the x coordinate of the object.
    setX(x) { this.figure.equal(this.x(), x); return this }
    // Constrain the y coordinate of the object.
    setY(y) { this.figure.equal(this.y(), y); return this }

    // Constrain the width of this object.
    setW(w) { this.figure.equal(this.w(), w); return this }
    // Constrain the height of this object.
    setH(h) { this.figure.equal(this.h(), h); return this }

    // The set of variables that are needed to be able to render
    // this object, if it is rendered.
    variables() {
        return new Set([this.x_, this.y_, this.w_, this.h_])
    }
}

// A Graphic is centered at (x,y) and has a width w and height h.
// It also has some style attributes and it may contain text.
// LineWidth can be a constrained attribute too.
class Graphic extends Box {
    constructor(figure, fillStyle, strokeStyle, lineWidth, x_hint,
                y_hint, w_hint, h_hint) {
        super(figure, x_hint, y_hint, w_hint, h_hint)

        figure.Graphics.push(this)

        this.fillStyle = fillStyle || figure.getFillStyle()
        this.strokeStyle = strokeStyle || figure.getStrokeStyle()
        this.lineWidth = lineWidth || figure.getLineWidth()
        this.lineDash = figure.getLineDash()
    }
// builder methods for setting rendering style
    setFillStyle(s) {
        this.fillStyle = s
        return this
    }
    setStrokeStyle(s) {
        this.strokeStyle = s
        return this
    }
    setLineWidth(s) {
        this.lineWidth = legalExpr(s)
        return this
    }
    setLineDash(d) {
        this.lineDash = d
        return this
    }
    setOpacity(o) {
        this.opacity = o
        return this
    }
    // Fill the current graphics context appropriately based on the fill style and opacity
    fill() {
        const ctx = this.figure.ctx,
              f = this.fillStyle
        if (f) {
            ctx.fillStyle = f
            ctx.fill()
        }
    }
    stroke() {
        const ctx = this.figure.ctx,
              s = this.strokeStyle
        if (s) {
            ctx.strokeStyle = s
            ctx.stroke()
        }
    }
// control contained text
    addText(...t) {
        this.text = new ContainedText(this.figure, createText(...t))
        return this
    }
    setTextStyle(s) {
        if (!this.text) console.error("This object does not contain text")
        this.text.setFillStyle(s)
        return this
    }
    setLayoutAlgorithm(a) {
        if (!this.text) console.error("This object does not contain text")
        this.text.setLayoutAlgorithm(a)
        return this
    }
    setJustification(j) {
        if (!this.text) console.error("This object does not contain text")
        this.text.setJustification(j)
        return this
    }
    setVerticalAlign(a) {
        if (!this.text) console.error("This object does not contain text")
        this.text.setVerticalAlign(a)
        return this
    }
    setLineSpacing(s) {
        if (!this.text) console.error("This object does not contain text")
        this.text.setLineSpacing(s)
        return this
    }
    setInset(ins) {
        if (!this.text) console.error("This object does not contain text")
        this.text.setInset(ins)
        return this
    }
    setFont(f) {
        if (!this.text) console.error("This object does not contain text")
        this.text.setFont(f)
        return this
    }
    // Set font size
    setFontSize(s) {
        if (!this.text) console.error("This object does not contain text")
        this.text.setFontSize(s)
        console.log("setting font size " + s)
        return this
    }
    // Set font name
    setFontName(f) {
        if (!this.text) console.error("This object does not contain text")
        this.text.setFontName(f)
        return this
    }
    // Set font style
    setFontStyle(s) {
        if (!this.text) console.error("This object does not contain text")
        this.text.setFontStyle(s)
        return this
    }
// rendering control

    // Make this object appear immediately underneath the named object
    placeUnder(obj) {
        let objects = this.figure.Graphics
        let new_objects = []
        for (const o of objects) {
            if (o == obj) {
                new_objects.push(this)
                new_objects.push(o)
            } else if (o != this) {
                new_objects.push(o)
            }
        }
        this.figure.Graphics = new_objects
        return this
    }
    // Make this object appear immediately over the named object
    placeOver(obj) {
        let objects = this.figure.Graphics
        let new_objects = []
        for (const o of objects) {
            if (o == obj) {
                new_objects.push(o)
                new_objects.push(this)
            } else if (o != this) {
                new_objects.push(o)
            }
        }
        this.figure.Graphics = new_objects
        return this
    }
    active(f) {
        if (this.parent) {
            /*
            if (!this.parent.active(f)) {
                console.log("Inactive: " + this)
            }
            */
            return this.parent.active(f)
        }
        return true
    }
    visible(f) {
        if (!this.active(f)) return false
        if (this.parent) {
            return this.parent.visible(f)
        }
        return true
    }
    renderIfVisible() {
        if (this.visible(this.figure.currentFrame))
            this.render()
    }
    installHolder(figure, holder, child) {
        const oldParent = child.parent
        for (let i = 0; i < figure.Graphics.length; i++) {
            if (figure.Graphics[i] === child) {
                figure.Graphics[i] = holder
                child.parent = holder
                if (oldParent) {
                    this.installHolder(figure, oldParent, holder)
                }
                break
            }
        }
        if (child.parent !== holder) {
            console.error("Child object not in top-level list")
            figure.Graphics.push(holder)
        }
    }
    className() {
        return "Graphic"
    }
    toString() {
        return this.constructor.name
    }
}

// A Point acts like a graphical object wrt layout but does not generate new variables (unlike Box).
// It has no rendering, so it does not add itself to the graphical objects
// list. It also can act as an expression.
class Point extends LayoutObject {
    constructor(vx, vy) {
        super()
        if (vx === undefined)
            console.error("undefined Point x")
        if (vy === undefined)
            console.error("undefined Point y")
        this.x_ = vx
        this.y_ = vy
    }
    variables() {
        return union(exprVariables(this.x()), exprVariables(this.y()))
    }
    toString() {
        return `Point(${this.x_}, ${this.y_})`
    }
    at() {
        console.error("Sorry, Point.at() cannot be used because a Point does not know its Figure.")
        return this
    }
}

// A Group groups together a set of layout objects into a single object that
// is rendered together and whose location and bounds can be used to constrain
class Group extends Graphic {
    constructor(figure, ...objects) {
        super(figure)
        this.x_.remove()
        this.y_.remove()
        this.w_.remove()
        this.h_.remove()
        this.objects = flattenGraphics(objects).map(o => legalLayoutObject(o))
        this.objects.forEach(o => {
            o.parent = this
        })
        this.x_ = this.centerX()
        this.y_ = this.centerY()
    }
    variables() {
        const result = new Set(), g = this
        this.objects.forEach(o => {
            o.variables().forEach(v => {
                result.add(v)
            })
        })
        return result
    }
    x0() { return new Min(this.objects.map(o => o.x0())) }
    x1() { return new Max(this.objects.map(o => o.x1())) }
    y0() { return new Min(this.objects.map(o => o.y0())) }
    y1() { return new Max(this.objects.map(o => o.y1())) }
    w() { return new Minus(this.x1(), this.x0()) }
    h() { return new Minus(this.y1(), this.y0()) }
    render() {
        if (!this.visible()) return
        if (DEBUG_GROUPS) {
            const figure = this.figure, ctx = figure.ctx
            const [x0, x1, y0, y1] = evaluate([this.x0(), this.x1(), this.y0(), this.y1()])
            ctx.save()
            ctx.strokeStyle = 'magenta'
            ctx.lineWidth = 2
            ctx.translate(x0, y0)
            const w = x1-x0, h = y1-y0
            ctx.beginPath()
            ctx.moveTo(0, 0)
            ctx.lineTo(w, 0)
            ctx.lineTo(w, h)
            ctx.lineTo(0, h)
            ctx.closePath()
            ctx.stroke()
            ctx.restore()
        }
        this.objects.forEach(o => o.renderIfVisible())
    }
    children() {
        return this.objects
    }
    child(i) {
        return this.objects[i]
    }
    align(horz, vert) {
        this.figure.align(horz, vert, ...this.objects)
        return this
    }
    setBounds(object) {
        this.x0 = () => object.x0()
        this.x1 = () => object.x1()
        this.y0 = () => object.y0()
        this.y1 = () => object.y1()
        return this
    }
    toString() {
        return "Group(" + (this.objects ? this.objects.join(",") : "") + ")"
    }
    addDependencies(task) {
        task.prepareBackProp(this.x())
        task.prepareBackProp(this.y())
        super.addDependencies(task)
    }
}

// A TextFrame is a graphical object that doesn't have any rendering but does
// format contained text into a rectangular shape.
class TextFrame extends Graphic {
    // text should be a ContainedText object
    constructor(figure, text, fillStyle) {
        super(figure, fillStyle)
        this.text = text
        figure.positive(this.h())
        figure.positive(this.w())
    }
    render() {
        if (this.text) {
            this.text.renderIn(this.figure, this)
        }
    }
    toString() {
        return "TextFrame" + this.text + ")"
    }
}

// A filled rectangle. It can have text inside it.
class Rectangle extends Graphic {
    constructor(figure, fillStyle, strokeStyle, lineWidth, x_hint, y, w_hint, h_hint) {
        super(figure, fillStyle, strokeStyle, lineWidth, x_hint, y, w_hint, h_hint)
        figure.positive(this.h())
        figure.positive(this.w())
        this.cornerRadius = 0
    }
    render() {
        const figure = this.figure, ctx = figure.ctx
        ctx.save()
        const [x0, x1, y0, y1] = evaluate([this.x0(), this.x1(), this.y0(), this.y1()])
        ctx.translate(x0, y0)
        const w = x1-x0, h = y1-y0
        if (this.cornerRadius === 0) {
            ctx.beginPath()
            ctx.moveTo(0, 0)
            ctx.lineTo(w, 0)
            ctx.lineTo(w, h)
            ctx.lineTo(0, h)
            ctx.closePath()
        } else {
            Paths.roundedRect(ctx, 0, w, 0, h, evaluate(this.cornerRadius))
        }
        ctx.lineWidth = evaluate(this.lineWidth)
        if (this.hasOwnProperty('opacity')) ctx.globalAlpha = evaluate(this.opacity)
        this.fill()
        if (this.strokeStyle != null) {
            ctx.strokeStyle = this.strokeStyle
            ctx.setLineDash(this.lineDash || [])
            this.stroke()
        }
        ctx.restore()
        if (this.text) {
            this.text.renderIn(this.figure, this)
        }
    }
    connectionPts() {
      if (this.cornerRadius === 0) {
        return [ this.ll(), this.lr(), this.ul(), this.ur(), this.cl(), this.cr(), this.uc(), this.lc() ]
      } else {
        const r = this.cornerRadius
        const a = (typeof r == NUMBER) ? r * 0.2929 : new Times(0.2929, r)
        return [ this.cl(), this.cr(), this.uc(), this.lc(),
                    new Point(plus(this.x0(), a), plus(this.y0(), a)),
                    new Point(new Minus(this.x1(), a), plus(this.y0(), a)),
                    new Point(new Minus(this.x1(), a), new Minus(this.y1(), a)),
                    new Point(plus(this.x0(), a), new Minus(this.y1(), a)) ]
      }
    }
    setCornerRadius(r) {
        this.cornerRadius = legalExpr(r)
        return this
    }
    intersectionPt(px, py, valuation) {
        let result = super.intersectionPt(px, py, valuation)
        const r = evaluate(this.cornerRadius)
        if (r === 0) return result
        const [x, y] = result
        const [x0, y0, x1, y1] = evaluate([this.x0(), this.y0(),
                                         this.x1(), this.y1()], valuation)
        const r2 = r * r
        if ((x - x0) * (x - x0) + (y - y0) * (y - y0) < r2) {
            // too near x0, y0
            const x2 = x - x0 - r, y2 = y - y0 - r
            const d = Math.sqrt(x2*x2 + y2*y2)
            const x3 = x0 + r + r/d*(x - x0 - r),
                  y3 = y0 + r + r/d*(y - y0 - r)
            return [x3, y3]
        } else
        if ((x - x1) * (x - x1) + (y - y0) * (y - y0) < r2) {
            // too near x1, y0
            const x2 = x - x1 + r, y2 = y - y0 - r
            const d = Math.sqrt(x2*x2 + y2*y2)
            const x3 = x1 - r + r/d*(x - x1 + r),
                  y3 = y0 + r + r/d*(y - y0 - r)
            return [x3, y3]
        } else
        if ((x - x0) * (x - x0) + (y - y1) * (y - y1) < r2) {
            // too near x0, y1
            const x2 = x - x0 - r, y2 = y - y1 + r
            const d = Math.sqrt(x2*x2 + y2*y2)
            const x3 = x0 + r + r/d*(x - x0 - r),
                  y3 = y1 - r + r/d*(y - y1 + r)
            return [x3, y3]
        } else
        if ((x - x1) * (x - x1) + (y - y1) * (y - y1) < r2) {
            // too near x1, y1
            const x2 = x - x1 + r, y2 = y - y1 + r
            const d = Math.sqrt(x2*x2 + y2*y2)
            const x3 = x1 - r + r/d*(x - x1 + r),
                  y3 = y1 - r + r/d*(y - y1 + r)
            return [x3, y3]
        }
        return result
    }
}

// Some useful paths for rendering.
const Paths = {
    roundedRect: function (ctx, x0, x1, y0, y1, r) {
        const k = bezier_k
        ctx.beginPath()
        ctx.moveTo(x0+r, y0)
        ctx.lineTo(x1-r, y0)
        ctx.bezierCurveTo(x1-r+k*r, y0,  x1, y0+r-k*r,  x1, y0+r)
        ctx.lineTo(x1, y1-r)
        ctx.bezierCurveTo(x1, y1-r+k*r,  x1-r+k*r, y1,  x1-r, y1)
        ctx.lineTo(x0+r, y1)
        ctx.bezierCurveTo(x0+r-k*r, y1,  x0, y1-r+k*r, x0, y1-r)
        ctx.lineTo(x0, y0+r)
        ctx.bezierCurveTo(x0, y0+r-k*r,  x0+r-k*r, y0,  x0+r, y0)
        ctx.closePath()
    },
    roundedPolygon: function(ctx, r, pts) {
        ctx.beginPath()
        function arcPt(p1, p2) {
            const dx = p2[0]-p1[0],
                  dy = p2[1]-p1[1],
                  d2 = dx*dx + dy*dy,
                  d = Math.sqrt(d2)
            if (d <= TINY) return p1
            if (d < 2*r) {
                return [(p1[0] + p2[0])/2, (p1[1] + p2[1])/2]
            }
            const nr = r/d;
            return [p1[0] + dx*nr, p1[1] + dy*nr]
        }
        for (let i = 0; i < pts.length; i++) {
            const j = (i+1) % pts.length,
                  k = (i+2) % pts.length
            const p1 = arcPt(pts[i], pts[j]),
                  p2 = arcPt(pts[j], pts[i]),
                  p3 = arcPt(pts[j], pts[k])
            if (i == 0) {
                ctx.moveTo(p1[0], p1[1])
            } else {
                ctx.lineTo(p1[0], p1[1])
            }
            ctx.lineTo(p2[0], p2[1])
            ctx.bezierCurveTo((p2[0] + pts[j][0])/2, (p2[1] + pts[j][1])/2,
                              (p3[0] + pts[j][0])/2, (p3[1] + pts[j][1])/2,
                              p3[0], p3[1])
        }
        ctx.closePath()
    },
// Create an ellipse path with center (x,y) and x radius rx, y radius ry
    ellipse: function(ctx, x, y, rx, ry) {
        const k = bezier_k, rxk = rx * k, ryk = ry * k
        var x1 = x-rx, x2 = x-rxk, x3 = x+rxk, x4 = x+rx,
            y1 = y-ry, y2 = y-ryk, y3 = y+ryk, y4 = y+ry
        ctx.beginPath()
        ctx.moveTo(x4, y)
        ctx.bezierCurveTo(x4, y3,  x3, y4,  x, y4)
        ctx.bezierCurveTo(x2, y4,  x1, y3,  x1, y)
        ctx.bezierCurveTo(x1, y2,  x2, y1,  x, y1)
        ctx.bezierCurveTo(x3, y1,  x4, y2,  x4, y)
        ctx.closePath()
    },
    circle: function(ctx, x, y, r) {
        var rk = r*bezier_k, x1 = x-r, x2 = x-rk, x3 = x+rk, x4 = x+r,
                             y1 = y-r, y2 = y-rk, y3 = y+rk, y4 = y+r
    
        ctx.beginPath()
        ctx.moveTo(x4, y)
        ctx.bezierCurveTo(x4, y3,  x3, y4,  x, y4)
        ctx.bezierCurveTo(x2, y4,  x1, y3,  x1, y)
        ctx.bezierCurveTo(x1, y2,  x2, y1,  x, y1)
        ctx.bezierCurveTo(x3, y1,  x4, y2,  x4, y)
        ctx.closePath()
    },
    // Using ctx, create a path of cubic splines going through or near the
    // points in pts. Near the endpoints, it acts like a Bezier spline: the
    // curve goes through the first and last point and its initial and final
    // direction are toward the second and second-to-last points.
    bsplines: function(ctx, pts) {
        ctx.beginPath()
        ctx.moveTo(pts[0][0], pts[0][1])
        let n = pts.length
        switch(n) {
            case 1: ctx.stroke(); return
            case 2:
                ctx.lineTo(pts[1][0], pts[1][1])
                ctx.stroke()
                return
            case 4:
                ctx.bezierCurveTo(pts[1][0], pts[1][1],
                                  pts[2][0], pts[2][1],
                                  pts[3][0], pts[3][1])
                ctx.stroke()
                return
            default: break
        }
        const bk = bezier_k, bk_ = 1 - bk
        // const k1 = 0.5*(1 - bk), k1_ = 1 - k1
        const k1 = 0.13, k1_ = 1 - k1
        for (let i = 0; i < n - 2; i++) {
            let p1=[], p2=[], p3=[]
            if (i == 0) {
                p1[0] = pts[i][0]*bk_ + pts[i+1][0]*bk
                p1[1] = pts[i][1]*bk_ + pts[i+1][1]*bk
            } else {
                p1[0] = pts[i][0]*k1 + pts[i+1][0]*k1_
                p1[1] = pts[i][1]*k1 + pts[i+1][1]*k1_
            }
            if (i == n-3) {
                p2[0] = pts[i+1][0]*bk + pts[i+2][0]*bk_
                p2[1] = pts[i+1][1]*bk + pts[i+2][1]*bk_
                p3 = pts[i+2]
            } else {
                p2[0] = pts[i+1][0]*k1_ + pts[i+2][0]*k1
                p2[1] = pts[i+1][1]*k1_ + pts[i+2][1]*k1

                p3[0] = pts[i+1][0]*bk + pts[i+2][0]*bk_
                p3[1] = pts[i+1][1]*bk + pts[i+2][1]*bk_
            }
            ctx.bezierCurveTo(p1[0], p1[1], p2[0], p2[1], p3[0], p3[1])
        }
    },
    // Using ctx, create a closed path of cubic splines going near the points in pts. 
    curve: function(ctx, pts) {
        ctx.beginPath()
        const n = pts.length,
              i0 = 0, i1 = 1,
              x0 = pts[0][0]*0.5 + pts[1][0]*0.5,
              y0 = pts[0][1]*0.5 + pts[1][1]*0.5
        ctx.moveTo(x0, y0)
        let p1=[], p2=[], p3=[]
        // const k1 = 0.5*(1 - bezier_k), k1_ = 1-k1
        const k1 = 0.15, k1_ = 1-k1
        for (let i = 0; i < n; i++) {
            let i0 = i, i1 = (i+1)%n, i2 = (i+2)%n

            p1[0] = pts[i0][0]*k1 + pts[i1][0]*k1_
            p1[1] = pts[i0][1]*k1 + pts[i1][1]*k1_
            p2[0] = pts[i1][0]*k1_ + pts[i2][0]*k1
            p2[1] = pts[i1][1]*k1_ + pts[i2][1]*k1
            p3[0] = pts[i1][0]*0.5 + pts[i2][0]*0.5
            p3[1] = pts[i1][1]*0.5 + pts[i2][1]*0.5
            ctx.bezierCurveTo(p1[0], p1[1], p2[0], p2[1], p3[0], p3[1])
        }
        ctx.closePath()
    }
}

class Square extends Rectangle {
    constructor(figure, fillStyle, strokeStyle, lineWidth, x_hint, y_hint, size_hint) {
        super(figure, fillStyle, strokeStyle, lineWidth, x_hint, y_hint, size_hint, size_hint)
        figure.equal(this.w(), this.h())
    }
}

class Ellipse extends Graphic {
    constructor(figure, fillStyle, strokeStyle, lineWidth, x_hint, y_hint, size_hint) {
        super(figure, fillStyle, strokeStyle, lineWidth, x_hint, y_hint, size_hint, size_hint)
        figure.positive(this.h())
        figure.positive(this.w())
    }
    render() {
        const figure = this.figure, ctx = figure.ctx
        ctx.save()
        const [x, y, w, h] = evaluate([this.x(), this.y(), this.w(), this.h()])
        ctx.translate(x - w/2, y - h/2)
        ctx.lineWidth = evaluate(this.lineWidth)
        Paths.ellipse(ctx, w/2, h/2, w/2, h/2)
        if (this.hasOwnProperty('opacity')) ctx.globalAlpha = evaluate(this.opacity)
        this.fill()
        if (this.strokeStyle != null) {
            ctx.strokeStyle = this.strokeStyle
            ctx.setLineDash(this.lineDash || [])
            ctx.stroke()
        }
        ctx.restore()
        if (this.text) {
            this.text.renderIn(this.figure, this)
        }
    }
    bestMagnetPt(px, py) {
        const x = evaluate(this.x()),
              y = evaluate(this.y()),
              pdx = px - x,
              pdy = py - y
        let xr = evaluate(this.w())/2,
            yr = evaluate(this.h())/2
        if (xr == 0 || yr == 0) return [x,y]
        const d = Math.sqrt(pdy*pdy*xr*xr + pdx*pdx*yr*yr)
        return [x + pdx*xr*yr/d, y + pdy*xr*yr/d]
    }
    intersectionPt(px, py) {
        return this.bestMagnetPt(px, py)
    }

    xSpan(y0, y1) {
        const [x,y,w,h] = evaluate([this.x(), this.y(), this.w(), this.h()])
        const y2 = Math.max(Math.abs(y - y0), Math.abs(y - y1))
        // equation: ((X - x)/(w/2))^2 + ((Y - y)/(h/2))^2 = 1
        const t = Math.min(1, 2*y2/h),
              d = 0.5 * w * Math.sqrt(1 - t*t)
        return [x - d, x + d]
    }
}

class Circle extends Ellipse {
    constructor(figure, fillStyle, strokeStyle, lineWidth, x_hint, y_hint, size_hint) {
        super(figure, fillStyle, strokeStyle, lineWidth, x_hint, y_hint, size_hint, size_hint)
        figure.equal(this.h(), this.w())
    }
    bestMagnetPt(px, py) {
        const x = evaluate(this.x()),
              y = evaluate(this.y()),
              r = evaluate(this.h())/2,
              d = norm2d(px - x, py - y)
        if (d == 0) return [x,y]
        return [x + (px - x)*r/d, y + (py-y)*r/d]
    }
}

// A filled polygon. The vertices must be specified explicitly.
// polygon.points is an array of the points.
//
class Polygon extends Graphic {
    constructor(figure, points, fillStyle, strokeStyle, lineWidth) {
        super(figure, fillStyle, strokeStyle, lineWidth)
        points = flattenGraphics(points)
        this.points = points
        const xpts = points.map(p => p.x()), ypts = points.map(p => p.y())
        const maxx = figure.max(xpts), minx = figure.min(xpts), maxy = figure.max(ypts), miny = figure.min(ypts)
        this.x_.remove()
        this.x_ = figure.average(minx, maxx)
        this.y_.remove()
        this.y_ = figure.average(miny, maxy)
        this.w_.remove()
        this.w_ = figure.minus(maxx, minx)
        this.h_.remove()
        this.h_ = figure.minus(maxy, miny)
    }
    render() {
        const figure = this.figure, ctx = figure.ctx
        ctx.save()
        let pts = this.points.map(pt => evaluate(pt))
        const x0 = pts[0][0], y0 = pts[0][1]
        pts = pts.map(p => [p[0] - x0, p[1] - y0])
        ctx.translate(x0, y0)
        ctx.lineWidth = evaluate(this.lineWidth)
        ctx.lineDash = this.lineDash
        ctx.fillStyle = this.fillStyle
        if (this.cornerRadius) {
            const r = evaluate(this.cornerRadius)
            Paths.roundedPolygon(ctx, r, pts)
        } else {
            ctx.beginPath()
            for (let i = 0; i < this.points.length; i++) {
                const [x, y] = pts[i]
                if (i == 0) {
                    ctx.moveTo(x, y)
                } else {
                    ctx.lineTo(x, y)
                }
            }
            ctx.closePath()
        }
        this.fill()
        if (this.strokeStyle != null) {
            ctx.setLineDash(this.lineDash || [])
            ctx.strokeStyle = this.strokeStyle
            ctx.stroke()
        }
        ctx.restore()
        if (this.text) {
            this.text.renderIn(this.figure, this)
        }
    }
    setCornerRadius(r) {
        this.cornerRadius = legalExpr(r)
        return this
    }
    variables() {
        let result = new Set(); // Graphic.prototype.variables.call(this)
        this.points.forEach(p => {
            result = union(result, exprVariables(p))
        })
        return result
    }
}

class ClosedCurve extends Polygon {
    constructor(figure, points) {
        super(figure, points)
    }
    render() {
        const figure = this.figure, ctx = figure.ctx
        ctx.save()
        const [x0, y0] = evaluate([this.x0(), this.y0()])
        ctx.translate(x0, y0)
        ctx.lineWidth = evaluate(this.lineWidth)
        ctx.lineDash = this.lineDash
        ctx.fillStyle = this.fillStyle
        if (this.hasOwnProperty('opacity')) ctx.globalAlpha = evaluate(this.opacity)
        const pts = []
        for (let i = 0; i < this.points.length; i++) {
            const [x, y] = evaluate(this.points[i])
            pts.push([x - x0, y - y0])
        }
        Paths.curve(ctx, pts)
        this.fill()
        if (this.strokeStyle != null) {
            ctx.setLineDash(this.lineDash || [])
            ctx.strokeStyle = this.strokeStyle
            ctx.stroke()
        }
        ctx.restore()
        if (this.text) {
            this.text.renderIn(this.figure, this)
        }
    }
    variables() {
        let r = union(exprVariables(this.x0()), exprVariables(this.y0()), exprVariables(this.lineWidth || 0),
            exprVariables(this.opacity || 0))
        for (let i = 0; i < this.points.length; i++) {
            r = union(r, exprVariables(this.points[i]))
        }
        return r
    }
}

// Return an array of [x, y, w, h] tuples describing the positions of
// the labels.
//   pts: array of [x, y] pairs describing the connected vertices
//   labels: the label objects
//   startAdj, endEdj: how much to shorten the start/end of the connector to compensate for
//     arrowheads on either end
// 
function positionLineLabels(figure, pts, labels, startAdj, endAdj) {
    let ctx = figure.ctx,
        n = pts.length,
        result = []
    if (startAdj === undefined) startAdj = 0
    if (endAdj === undefined) endAdj = 0
    if (!labels || labels.length == 0) return
    let total_d = 0, cdists = [total_d], dists = []
    for (let i = 0; i < n - 1; i++) {
      let d = norm2d(pts[i+1][0] - pts[i][0],
                     pts[i+1][1] - pts[i][1])
      dists[i] = d
      total_d += d
      cdists[i+1] = total_d
    }
    if (startAdj) {
      dists[0] += startAdj
      total_d += startAdj
    }
    if (endAdj) {
      dists[n-2] += endAdj
      cdists[n-1] += endAdj
      total_d += endAdj
    }

    labels.forEach(linelabel => {
      let pos = evaluate(linelabel.position),
          offset = evaluate(linelabel.offset),
          dpos = pos * total_d
      let i = 0
      for (i = 0; i < n - 1; i++) {
          if (cdists[i+1] > dpos) break
      }
      let x1 = pts[i][0],
          y1 = pts[i][1],
          x2 = pts[i+1][0],
          y2 = pts[i+1][1],
          f = (dpos - cdists[i])/(cdists[i+1] - cdists[i]),
          d = norm2d(x2-x1, y2-y1),
          dx12 = (x2 - x1)/d,
          dy12 = (y2 - y1)/d,
          dx, dy
      if (f < 0.0 || f > 1.0) {
        console.error("line label position is impossible")
      }
      if (f < 0.5) { // blend normal with previous normal
        let dx01 = dx12, dy01 = dy12
        if (i > 0) {
          let x0 = pts[i-1][0],
              y0 = pts[i-1][1],
              d01 = norm2d(x1-x0, y1-y0)
          dx01 = (x1 - x0)/d01
          dy01 = (x1 - x0)/d01
        }
        dx = (f + 0.5) * dx12 + (0.5 - f) * dx01
        dy = (f + 0.5) * dy12 + (0.5 - f) * dy01
      } else { // blend normal with next normal
        let dx23 = dx12, dy23 = dy12
        if (i < n-2) {
          let x3 = pts[i+2][0],
              y3 = pts[i+2][1],
              d23 = norm2d(x3 - x2, y3 - y2)
          dx23 = (x3 - x2)/d23
          dy23 = (y3 - y2)/d23
        }
        dx = (1.5 - f)*dx12 + (f - 0.5)*dx23
        dy = (1.5 - f)*dy12 + (f - 0.5)*dy23
      }
      if (i == 0) {
          x1 -= startAdj * dx
          y1 -= startAdj * dy
          d += startAdj
      }
      if (i == n-2) {
          x2 += endAdj * dx
          y2 += endAdj * dy
          d += endAdj
      }
      let f1 = (dpos - cdists[i])/d,
          x = x1 + (x2 - x1) * f1 + dy * offset,
          y = y1 + (y2 - y1) * f1 - dx * offset
      let [w, h] = linelabel.computeSize()
      result.push([x, y, w, h])
    })
    return result
}

function setupClipRegion(figure, boxes, inset) {
    if (inset == null) return
    const ctx = figure.ctx
    ctx.beginPath()
    ctx.rect(0, 0, figure.width, figure.height)
    boxes.forEach(box =>
        {
            const [x,y,w,h] = box
            const w2 = w/2 + inset, h2 = h/2 + inset
            ctx.moveTo(x - w2, y - h2)
            ctx.lineTo(x + w2, y - h2)
            ctx.lineTo(x + w2, y + h2)
            ctx.lineTo(x - w2, y + h2)
            ctx.closePath()
        })
    ctx.clip("evenodd")
}

// Draw an arrowhead of size s in the current style,
// based at x0,y0 and heading toward x1, y1
function drawArrowhead(ctx, x0, y0, x1, y1, s) {
    const dx = x1 - x0, dy = y1 - y0
    ctx.save()
    ctx.translate(x1, y1)
    ctx.rotate(Math.atan2(dy, dx))

    ctx.beginPath()
    ctx.moveTo(0,0)
    ctx.lineTo(-s, -0.4 * s)
    ctx.lineTo(-s, 0.4 * s)
    ctx.closePath()
    ctx.fill()

    ctx.restore()
}

// Draw a curved arrowhead of size s in the current style,
// based at x0,y0 and heading toward x1, y1
function drawCurvedArrowhead(ctx, x0, y0, x1, y1, s) {
    const dx = x1 - x0, dy = y1 - y0
    ctx.save()
    ctx.translate(x1, y1)
    ctx.rotate(Math.atan2(dy, dx))

    ctx.beginPath()
    ctx.moveTo(0,0)
    ctx.bezierCurveTo(-0.5*s, -0.1*s, -0.5*s, -0.1*s, -s, -0.4 * s)
    ctx.lineTo(-s, 0.4 * s)
    ctx.bezierCurveTo(-0.5*s, 0.1*s, -0.5*s, 0.1*s, 0, 0)
    ctx.closePath()
    ctx.fill()

    ctx.restore()
}


// Bezier constant for a circular arc: (4/3) tan(theta/4)
function circularArcConstant(degrees) {
    return (4/3) * Math.tan(degrees * Math.PI / 180 / 4)
}

const bezier_k = circularArcConstant(90)

// Draw a circular "bullet" head of size s in the current style,
// based at x0,y0 and heading toward x1, y1
function drawBulletHead(ctx, x0, y0, x1, y1, s) {
    const dx = x1 - x0, dy = y1 - y0
    ctx.save()
    ctx.translate(x1, y1)
    ctx.rotate(Math.atan2(dy, dx))

    ctx.beginPath()
    ctx.moveTo(0,0)
    ctx.lineTo(-s, 0)
    ctx.stroke()
    Paths.circle(ctx, 0, 0, s/4)
    ctx.fill()
    ctx.restore()
}

const arrows = {
    arrow: drawArrowhead,
    bullet: drawBulletHead,
    curved: drawCurvedArrowhead,
}

// Draw an arrowhead for a line or curve endpoint at (x,y)
// where the previous point on the line or curve is at (x2, y2).
// Return the point where the line should extend from.
// If style is undefined, nothing is drawn and [x,y] is returned.
function drawLineEndSeg(ctx, style, size, x, y, x2, y2) {
    if (style === undefined) return [x,y]
    const xd = x - x2, yd = y - y2,
          d = norm2d(xd, yd)
    let cosa = 1, sina = 0
    if (Math.abs(d) > 1e-7) {
        cosa = xd/d; sina = yd/d
    }
    return drawLineEndDir(ctx, style, size, x, y, cosa, sina)
}

// Draw an arrowhead for a line or curve endpoint at (x,y)
// where the direction of the line is described by (cosa, sina).
// Return the point where the line should extend from.
// If style is undefined, nothing is drawn and [x,y] is returned.
function drawLineEndDir(ctx, style, size, x, y, cosa, sina) {
    if (style === undefined) return [x,y]
    let x1 = x - cosa * size,
        y1 = y - sina * size
    let arrowFun = arrows[style]
    if (arrowFun) arrowFun(ctx, x1, y1, x, y, size)
    return [x1, y1]
}

// A straight line
class Line extends Graphic {
    // create a line from p1 to p2 (optionally specified)
    constructor(figure, p1, p2, strokeStyle, lineWidth) {
        super(figure, undefined, strokeStyle, lineWidth)
        this.p1 = p1 || new Point(figure.variable("p1x"), figure.variable("p1y"))
        this.p2 = p2 || new Point(figure.variable("p2x"), figure.variable("p2y"))
        this.startArrowStyle = figure.getStyle('startArrow')
        this.endArrowStyle = figure.getStyle('endArrow')
        this.arrowSize = figure.getStyle('arrowSize')
        this.labels = null
        this.x_.remove()
        this.y_.remove()
        this.w_.remove()
        this.h_.remove()
        this.x_ = new Average(this.p1.x(), this.p2.x())
        this.y_ = new Average(this.p1.y(), this.p2.y())
        this.w_ = new Abs(new Minus(this.p2.x(), this.p1.x()))
        this.h_ = new Abs(new Minus(this.p2.y(), this.p1.y()))
    }
    // The starting point of the line
    start() {
        return this.p1
    }
    // The ending point of the line
    end() {
        return this.p2
    }
    render() {
        const figure = this.figure, ctx = figure.ctx
        ctx.beginPath()
        ctx.strokeStyle = this.strokeStyle
        ctx.lineWidth = evaluate(this.lineWidth)
        const [x1, x2, y1, y2] = evaluate([this.p1.x(), this.p2.x(), this.p1.y(), this.p2.y()])
        const xd = x2 - x1, yd = y2 - y1,
                d = norm2d(xd, yd),
                cosa = xd/d, sina = yd/d
        if (this.fillstyle != null) ctx.fillStyle = this.fillStyle
        else ctx.fillStyle = this.strokeStyle
        ctx.setLineDash(this.lineDash || [])
        let [x1a, y1a] = drawLineEndDir(ctx, this.startArrowStyle, this.arrowSize, x1, y1, -cosa, -sina),
            [x2a, y2a] = drawLineEndDir(ctx, this.endArrowStyle, this.arrowSize, x2, y2, cosa, sina)

        if (this.hasOwnProperty('opacity')) ctx.globalAlpha = evaluate(this.opacity)
        ctx.beginPath()
        ctx.moveTo(x1a, y1a)
        ctx.lineTo(x2a, y2a)
        ctx.stroke()

        if (this.labels && this.labels.length > 0) {
            const pts =  [[x1, y1], [x2, y2]],
                  labelPosns = positionLineLabels(figure, pts, this.labels,
                    this.startArrowStyle ? this.arrowSize : 0,
                    this.endArrowStyle ? this.arrowSize : 0)
            for (let i = 0; i < this.labels.length; i++) {
                const box = labelPosns[i]
                this.labels[i].drawAt(ctx, ...box)
            }
        }
    }
    setStartArrow(style) {
        this.startArrowStyle = style
        return this
    }
    setEndArrow(style) {
        this.endArrowStyle = style
        return this
    }
    setArrowSize(s) {
        this.arrowSize = s
        return this
    }
    setStart(p) {
        this.figure.pin(this.start(), p)
        return this
    }
    setEnd(p) {
        this.figure.pin(this.end(), p)
        return this
    }
    addLabel(obj, pos, offset, margin) {
        this.labels = this.labels || []
        if (pos == undefined) pos = 0.5
        this.labels.push(this.figure.lineLabel(obj, pos, offset, margin))
        if (obj instanceof Graphic) {
            obj.installHolder(this.figure, this, obj)
        }
        return this
    }
    x0() {
        return new Min(this.p1.x(), this.p2.x())
    }
    x1() {
        return new Max(this.p1.x(), this.p2.x())
    }
    y0() {
        return new Min(this.p1.y(), this.p2.y())
    }
    y1() {
        return new Max(this.p1.y(), this.p2.y())
    }
    center() {
        return new Average(this.p1, this.p2)
    }
    variables() {
        let r = union(exprVariables(this.p1), exprVariables(this.p2))
        if (this.labels) this.labels.forEach(lb => {
            if (lb.text instanceof Graphic)
                r = union(r, lb.text.variables())
        })
        return r
    }
}

// A horizontal line, oriented left-to-right
class HorzLine extends Line {
    constructor(figure, p1, p2, strokeStyle, lineWidth) {
        super(figure, p1, p2, strokeStyle, lineWidth)
        figure.equal(this.start().y(), this.end().y())
        // Need a stronger constraint to get the line oriented correctly
        figure.leq(this.start().x(), this.end().x()).changeCost(10)
        this.w_ = new Minus(this.p2.x(), this.p1.x())
    }
    x0() {
        return this.p1.x()
    }
    x1() {
        return this.p2.x()
    }
}

// A vertical line, oriented downward
class VertLine extends Line {
    constructor(figure, p1, p2, strokeStyle, lineWidth) {
        super(figure, p1, p2, strokeStyle, lineWidth)
        figure.equal(this.start().x(), this.end().x())
        // Need a stronger constraint to get the line oriented correctly
        figure.leq(this.start().y(), this.end().y()).changeCost(10)
        this.h_ = new Minus(this.p2.y(), this.p1.y())
    }
    y0() {
        return this.p1.y()
    }
    y1() {
        return this.p2.y()
    }
}

function sqdist(xd, yd) { return xd*xd + yd*yd }
function norm2d(xd, yd) { return Math.sqrt(xd*xd + yd*yd) }

// The slice of the arguments starting from i as
// an array. Omit i to convert all.
function argsToArray(args, i) {
    var result = []
    if (i === undefined) i = 0
    while (i < args.length) result.push(args[i++])
    return result
}
// If args is an arguments object, call f() on each argument
// starting from index i.
function argsForEach(args, i, f) {
    while (i < args.length) {
        f(args[i++])
    }
}

function flattenGraphics(objects) {
    return objects.flat().filter(o => {
        if (!o) return false
        if (o && o.variables) return true
        console.error("Not a graphical object: " + o)
        return false
    })
}

// A Connector draws a curve from a first object to a last object, passing near 
// intermediate objects along the way. Bezier splines are used to connect objects.
class Connector extends Graphic {
    constructor(figure, ...objects) {
        super(figure, undefined, figure.getStrokeStyle(), figure.getLineWidth())
        this.fillStyle = this.strokeStyle
        this.objects = flattenGraphics(objects)
        this.labels = []
        this.arrowSize = figure.getArrowSize()
        this.connectionStyle = figure.getConnectionStyle()
        this.lineLabelInset = figure.getLineLabelInset() // may be null
        this.x_.remove()
        this.y_.remove()
        this.w_.remove()
        this.h_.remove()
        const x1 = new Max(this.objects.map(o => o.x())),
              y1 = new Max(this.objects.map(o => o.y())),
              x0 = new Min(this.objects.map(o => o.x())),
              y0 = new Min(this.objects.map(o => o.y()))
        this.x_ = figure.average(x0, x1)
        this.y_ = figure.average(y0, y1)
        this.w_ = figure.minus(x1, x0)
        this.h_ = figure.minus(y1, y0)
    }
    setConnectionStyle(s) {
        switch(s) {
            case 'magnet':
            case 'intersection':
                this.connectionStyle = s
            default:
                console.error(`Illegal connection style: "${s}"`)
        }
        return this
    }
    render() {
        const figure = this.figure, ctx = figure.ctx
        let objs = this.objects,
            i = 0, m = objs.length-1
        const pts = objs.map(o => evaluate([o.x(), o.y()]));
        switch (this.connectionStyle) {
            case 'magnet':
                [ pts[0][0], pts[0][1] ] = objs[0].bestMagnetPt(pts[1][0], pts[1][1]);
                [ pts[m][0], pts[m][1] ] = objs[m].bestMagnetPt(pts[m-1][0], pts[m-1][1]);
                break
            case 'intersection':
                [ pts[0][0], pts[0][1] ] = objs[0].intersectionPt(pts[1][0], pts[1][1]);
                [ pts[m][0], pts[m][1] ] = objs[m].intersectionPt(pts[m-1][0], pts[m-1][1]);
                break
        }
        const labelPosns = (this.labels && this.labels.length > 0)
            ? positionLineLabels(figure, pts, this.labels,
                    this.startArrowStyle ? this.arrowSize : 0,
                    this.endArrowStyle ? this.arrowSize : 0)
            : null

        ctx.save()
        if (labelPosns) setupClipRegion(figure, labelPosns, this.lineLabelInset)

        ctx.strokeStyle = this.strokeStyle
        ctx.lineWidth = evaluate(this.lineWidth)
        ctx.setLineDash(this.lineDash || [])
        if (this.hasOwnProperty('opacity')) ctx.globalAlpha = evaluate(this.opacity)
        if (this.fillStyle) ctx.fillStyle = this.fillStyle
        if (this.startArrowStyle) {
            [pts[0][0], pts[0][1]] = 
                drawLineEndSeg(ctx, this.startArrowStyle, this.arrowSize,
                               pts[0][0], pts[0][1], pts[1][0], pts[1][1])
        }
        if (this.endArrowStyle) {
            [pts[m][0], pts[m][1]] = 
                drawLineEndSeg(ctx, this.endArrowStyle, this.arrowSize,
                               pts[m][0], pts[m][1], pts[m-1][0], pts[m-1][1])
        }

        ctx.strokeStyle = this.strokeStyle
        Paths.bsplines(ctx, pts)
        ctx.stroke()
        ctx.restore()

        if (labelPosns) {
            for (let i = 0; i < this.labels.length; i++) {
                const box = labelPosns[i]
                this.labels[i].drawAt(ctx, ...box)
            }
        }
    }
    insert(object, pos) {
        objects = object.slice(0, pos).concat([object]).concat(object.slice(pos))
    }
    addLabel(obj, pos, offset, margin) {
        if (arguments.length == 1 && obj instanceof LineLabel) { // backward compat
            this.labels.push(obj)
        } else {
            if (pos == undefined) pos = 0.5
            this.labels.push(this.figure.lineLabel(obj, pos, offset, margin))
            if (obj instanceof Graphic) {
                obj.installHolder(this.figure, this, obj)
            }
        }
        return this
    }
    setLabelInset(inset) {
        this.lineLabelInset = inset
    }
    setStartArrow(style) {
        this.startArrowStyle = style
        return this
    }
    setEndArrow(style) {
        this.endArrowStyle = style
        return this
    }
    setArrowSize(s) {
        this.arrowSize = s
        return this
    }
    variables() {
        let r = new Set()
        this.objects.forEach(o =>
            r = union(r, o.variables()))
        this.labels.forEach(lb => {
            if (lb.text instanceof Graphic)
                r = union(r, lb.text.variables())
        })
        return r
    }
    className() {
        return "Connector"
    }
    toString() {
        return this.className() + "(" + (this.objects ? this.objects.join(',') : "") + ")"
    }
}

// Horizontal space.
class HSpace extends Graphic {
    constructor(figure, w) {
        super(figure)
        if (w) figure.equal(this.w(), w)
    }
    render() {}
    renderIfVisible() {}
}

// Vertical space.
class VSpace extends Graphic {
    constructor(figure, h) {
        super(figure)
        if (h) figure.equal(this.h(), h)
    }
    render() {}
    renderIfVisible() {}
}

// A Font object immutably encapsulates all the information needed to select a
// font to render text in.
class Font {
    constructor(figure, context) {
        if (figure) {
            this.figure = figure
        }
        if (!context) {
            this.fontStyle = Figure_defaults.FONT_STYLE
            this.fontSize = Figure_defaults.FONT_SIZE
            this.fontName = Figure_defaults.FONT_NAME
        } else {
            if (context instanceof Figure) context = context.currentStyle()
            this.fontStyle = context.get('fontStyle')
            this.fontSize = context.get('fontSize')
            this.fontName = context.get('fontName')
        }
    }
    copy() {
        const font = new Font()
        font.figure = this.figure
        if (this.fontName) font.fontName = this.fontName
        if (this.fontStyle) font.fontStyle = this.fontStyle
        console.log("overwriting font size " + font.fontSize + " with " + this.fontSize)
        font.fontSize = this.fontSize
        return font
    }
    getName() {
        return this.fontName
    }
    getSize() {
        return this.fontSize
    }
    getStyle() {
        return this.fontStyle
    }
    // Cause the rendering context `context` to start
    // rendering in this font.
    setContextFont(context) {
        let fs = this.fontSize
        // console.log("setting context font " + this.fontName + ", size = " + fs)
        if (fs instanceof Expression) {
            fs = evaluate(fs)
        }
        if (typeof fs === NUMBER) {
            fs = fs + "px"
        }
        const f = (this.fontStyle ? this.fontStyle + " " : "") + fs + " " + this.fontName
        context.font = f
        // console.log("  Setting font to " + f)
    }
    toString() {
        return "[Font family=" + this.fontName + " style=" + this.fontStyle
            + " size=" + this.fontSize + "]"
    }
}

// Measure the 'cost' of a successful text layout ly that starts from position x on the first line.
// Lower costs are better. Note that the last line does not have any cost.
function layoutCost(ly, x) {
    let cost = 0
    const lines = ly.lines, n = lines.length
    for (let i = 1; i < n; i++) {
        const line = lines[i],
              items = line.items,
              m = items.length
        const left = (i == n-1) ? x : line.x0
        let span = line.x1 - left
        for (let j = 0; j < m; j++) {
            const item = items[j]
            span -= item.width
            if (item.item && item.item.cost) cost += item.item.cost
        }
        cost += span * span * span
    }
    return cost
}

function spaces(n) {
    let result = "";
    while (n > 0) {
        result += "  ";
        n--;
    }
    return result;
}

// Whether ly1 is a better layout than ly2. Both layouts start from x on the first line.
// Successful layouts always beat unsuccessful ones. Successful layouts are compared using
// layout cost. Unsuccessful layouts are compared based on how much of the text was laid out.
function lowerCost(ly1, ly2, x) {
    if (ly1.success) {
        if (!ly2.success) return true;
        return (layoutCost(ly1, x) < layoutCost(ly2, x));
    }
    if (ly2.success) return false;
    return countItems(ly1) > countItems(ly2);
}

// Find a layout for the given sequence of items in context, within the container,
// starting from position (x, y) and not exceeding ymax, and assuming that the
// line that position is on extends from x0 to x1. The input sequence
// citems is an array of objects ("context-items") in reverse order, each
// with the following structure:
//    {
//       item: the text item 
//       context: the context of the item (Context)
//    }
// Only the first n items in citems are to be laid out.
// 
// The result is an object with two fields:
//  {
//     success: a boolean indicating whether layout was completed
//     lines: an array each of whose elements describe one formatted line. The
//            elements appear in *reverse order*.
//            In the case where success is false, lines contains an incomplete
//            layout.
//  }
// A lines array element is an object with
// the following properties:
// { x0:    the left margin of the line
//   x1:    the right margin of the line
//   y:     the vertical position of the baseline
//   items: an array of "renderable" items as defined in TextItem.layout. The items
//          are in *reverse order*
// }
function findLayout(figure, citems, n, x, y, x0, x1, ymax) {
    if (n == 0) {
        return {
            success: true,
            lines: [{ x0, x1, y, items: []}]
        }
    }
    const citem = citems[n-1],
          item = citem.item,
          tc = citem.context,
          fsPixels = figure.fontSizePixels(tc),
          ls =  tc.get('lineSpacing') * fsPixels,
          res0 = item.layout(figure, tc, x, y, x0, x1, ymax)
    if (!res0.success || res0.positions.length == 0) {
        return {
            success: false,
            lines: [{ x0, x1, y, items: []}]
        }
    }
    const posns = res0.positions
    n--
    let best = undefined, bestp = undefined
    if (res0.following.length > 0) {
        citems = citems.slice(0, n)
        const newItems = res0.following.reverse()
        for (let i=0; i < newItems.length; i++) {
            citems.push(newItems[i])
            n++
        }
    }
    const greedy = tc.get("layoutAlgorithm") == "greedy"
    function checkIfBest(posn) {
        let rest
        if (posn.newLine) {
            const inset = tc.get("inset"), container = tc.get("container")
            let [nx0, nx1] = container.xSpan(y, y + ls)
            nx0 += inset
            nx1 -= inset
            rest = findLayout(figure, citems, n, nx0, y + ls, nx0, nx1, ymax)
            rest.lines.push({x0, x1, y, items: []})
        } else {
            rest = findLayout(figure, citems, n, posn.x, y, x0, x1, ymax)
        }
        const renderable = posn.renderable, lines = rest.lines
        if (renderable) lines[lines.length - 1].items.push(renderable)
        if (best === undefined || lowerCost(rest, best, x)) {
            best = rest
            bestp = posn
        }
    }
    let key, cache
    if (posns.length > 1) {
        // key = `${x},${y}`
        key = x + y * 1009
        cache = item.cache
        if (!cache) item.cache = cache = new Map()
        const memoized = cache.get(key)
        if (memoized !== undefined) {
            checkIfBest(memoized)
            return best
        }
    }
    for (let i = 0; i < posns.length; i++) {
        const posn = posns[i]
        checkIfBest(posn)
        if (greedy && best !== undefined && best.success) break
    }
    if (key !== undefined) cache.set(key, bestp)
    return best
}

// A label.
class Label extends Graphic {
    constructor(figure, text, fontSize, fontName, fillStyle, x, y) {
        super(figure, fillStyle, undefined, 1, x, y)
        // this.text is either a string or a ContainedText object
        const style = this.style = new Context(figure.currentStyle())
        if (fontSize) style.set('fontSize', fontSize)
        if (fontName) style.set('fontName', fontName)
        if (text.layout) {
            this.text = new ContainedText(figure, text)
            this.font = new Font(figure, style)
            if (fillStyle != null) {
                this.fillStyle = fillStyle
                text.setFillStyle(fillStyle)
            } else {
                this.fillStyle = style.get('textStyle')
            }
        } else {
            this.text = text
            this.font = new Font(figure, style)
            if (fillStyle != undefined) this.fillStyle = fillStyle
            else this.fillStyle = style.get('textStyle')
        }

        this.setStrokeStyle(undefined)


        // Have to override Graphic in the object itself
        this.w_.remove()
        this.h_.remove()
        this.w = function() {
            if (!this.hasOwnProperty('computedWidth')) this.computeWidth(figure.ctx)
            return this.computedWidth
        }
        this.h = function() { return this.font.getSize() }
        this.variables = function() { return new Set([this.x_,this.y_]) }
    }
    installFont() {
        this.font.setContextFont(this.figure.ctx)
    }
    render() {
        const figure = this.figure, ctx = figure.ctx
        this.installFont()
        const x = evaluate(this.x0()),
              y = evaluate(figure.average(this.y(), this.y1()))
        if (typeof this.text == STRING_STR) { // instanceof String doesn't work
            if (this.fillStyle) {
                ctx.fillStyle = this.fillStyle
                ctx.fillText(this.text, x, y)
            }
            if (this.strokeStyle != null) {
                ctx.strokeStyle = this.strokeStyle
                if (this.lineWidth) {
                    ctx.lineWidth = evaluate(this.lineWidth)
                }
                ctx.strokeText(this.text, x, y)
            }
        } else {
            const tc = new Context(this.style).setAll([
              [ 'verticalAlign', "center"],
              [ 'justification', "center"],
              [ 'lineSpacing', 0],
              [ 'inset', 0],
              [ 'layoutAlgorithm', "greedy"],
              [ 'baseline', 0],
              [ 'fillStyle', this.fillStyle],
              [ 'strokeStyle', null],
              [ 'container', this]
            ])
            const layout = findLayout(figure, [{item: this.text.text, context: tc}], 1,
                                       x, y, x, Figure_defaults.LARGE_SPAN, y)
            let w = 0, items = layout.lines[0].items.reverse()
            for (let i = 0; i < items.length; i++) {
                const item = items[i]
                if (item.font) item.font.setContextFont(ctx)
                if (item.item) item.item.render(ctx, x + w, item.y)
                w += item.width
            }
        }
    }
    // A label will stretch as far as necessary to fit its text
    xSpan(y0, y1) {
        return [0, Figure_defaults.LARGE_SPAN]
    }
    computeWidth(ctx) {
        this.installFont()
        if (typeof this.text == STRING_STR) {
            this.computedWidth = ctx.measureText(this.text).width
        } else {
            let [w, h] = this.text.minimumSize()
            this.computedWidth = w
        }
        return this.computedWidth
    }

    // Set font size
    setFontSize(s) {
        this.style.set('fontSize', s)
        this.font = new Font(this.figure, this.style)
        delete this.computedWidth
        return this
    }

    // Set font name
    setFontName(n) {
        this.style.set('fontName', n)
        this.font = new Font(this.figure, this.style)
        delete this.computedWidth
        return this
    }

    // Set font style
    setFontStyle(n) {
        this.style.set('fontStyle', n)
        this.font = new Font(this.figure, this.style)
        delete this.computedWidth
        return this
    }

    // set text color etc.
    setTextStyle(s) {
        this.style.set('fillStyle', s)
        this.fillStyle = s
        this.computeWidth(this.figure.ctx)
        return this
    }

    toString() {
        return 'Label("' + this.text + '")'
    }
}

// A label somewhere along a connector.
// By default the label is simply text, but
// overriding the drawAt method allows rendering
// other graphics along the connector.
// position: fractional position along connector.
// offset: (optional) offset toward the port side of
// the connector.
class LineLabel {
    constructor(figure, text, position, offset) {
        this.figure = figure
        this.text = text // may be a Graphic or a string
        this.position = position
        this.offset = offset == undefined ? figure.getFontSize() : offset
        this.strokeStyle = null
        this.textStyle = figure.getTextStyle() || "black"
        this.font = figure.getFont()
    }
    computeSize() {
        const ctx = this.figure.ctx
        if (this.text instanceof Graphic) {
            this.computedHeight = evaluate(this.text.h())
            this.computedWidth = evaluate(this.text.w())
        } else if (typeof this.text == STRING_STR) {
            this.font.setContextFont(ctx)
            this.computedHeight = this.font.getSize()
            this.computedWidth = ctx.measureText(this.text).width
        } else {
            let [w, h] = this.text.minimumSize()
            this.computedHeight = h
            this.computedWidth = w
        }
        return [this.computedWidth, this.computedHeight]
    }
    drawAt(ctx, x, y) {
        this.font.setContextFont(ctx)
        ctx.fillStyle = this.textStyle
        this.computeSize()
        let w = this.computedWidth, h = this.computedHeight

        if (this.strokeStyle) {
            ctx.strokeStyle = this.strokeStyle
            ctx.beginPath()
            ctx.rect(x - w/2, y - h/2, w, h)
            ctx.stroke()
        }

        if (typeof this.text == STRING_STR) {
            ctx.fillText(this.text, x - w/2, y + h/2)
        } else if (this.text instanceof Graphic) {
            const g = this.text
            const gx = evaluate(g.x()), gy = evaluate(g.y())
            ctx.save()
            ctx.translate(x - gx, y - gy)
            g.render()
            ctx.restore()
        } else {
            const box = new LayoutObject()
            box.x = () => x
            box.y = () => y
            box.w = () => w
            box.h = () => h
            this.text.renderIn(this.figure, box)
        }
    }
    setFillStyle(s) { this.fillStyle = s; return this }
    setStrokeStyle(s) { this.strokeStyle = s; return this }
    setPosition(p) { this.position = p; return this }
    setOffset(o) { this.offset = o; return this }
}

function countItems(ly) {
    let c = 0
    const lines = ly.lines, nlines = lines.length
    for (let i = 0; i < nlines; i++) {
        c += lines[i].items.length
    }
    return c
}

// A ContainedText holds some text that can be formatted inside
// a graphical object. It is not a graphical object itself;
// it serves as the glue between a graphical object and the text
// it contains. It knows how to format the text and to render it
// into the containing shape. It has methods to control the presentation
// style (e.g., inset and centering) and the default style of the text it
// contains.
// 
class ContainedText {
    constructor(figure, ...text) {
        this.figure = figure
        this.style = new Context(figure.currentStyle())
        this.style.set('justification', 
                       this.style.get('justification') || "center")
        this.style.set('verticalAlign', this.style.get('verticalAlign') || "center")
        this.style.set('lineSpacing', this.style.get('lineSpacing')
            || Figure_defaults.LINE_SPACING),
        this.style.set('fillStyle', this.style.get('strokeStyle'))
        this.style.set('strokeStyle', null)

        this.inset = this.style.setDefault('inset', figure.fontSizePixels(this.style) / 3)
        this.font = new Font(figure, this.style)
        this.text = createText(...text)
    }
    setLineSpacing(s) {
        this.style.set('lineSpacing', s)
        return this
    }
    setInset(ins) {
        this.style.set('inset', ins)
        this.inset = ins
        return this
    }
    // justification can be "left", "center" (default), or "full"
    setJustification(j) {
        this.style.set('justification', j)
        return this
    }
    // can be "top", "center" (default), or "bottom"
    setVerticalAlign(va) {
        this.style.set('verticalAlign', va)
        return this
    }
    // Set font size
    setFontSize(s) {
        this.style.set('fontSize', s)
        return this
    }
    // Set font name
    setFontName(f) {
        this.style.set('fontName', f)
        return this
    }
    // Set font style
    setFontStyle(s) {
        this.style.set('fontStyle', s)
        return this
    }
    setFillStyle(s) {
        this.style.set('fillStyle', s)
        return this
    }
    setLayoutAlgorithm(a) {
        this.style.set('layoutAlgorithm', a)
        return this
    }

    // Return [w, h] where w and h are the width and height of the smallest rectangle
    // that contains the text when formatted in the smallest possible number of lines.
    minimumSize() {
        const tc = new Context(this.style).setAll([
                        ['forceLayout', false],
                        ['container', this],
                        ['layoutAlgorithm', 'greedy'],
                        ['justification', 'left'],
                        ['inset', 0],
                        ['verticalAlign', 'center'],
                        ['baseline', 0]])
        const ls = this.style.get('lineSpacing'),
              lineSpacing = this.font.getSize() * (ls == NUMBER ? ls : 1),
              layout = findLayout(this.figure, [{item: this.text, context: tc}], 1,
                    0, 0, 0, Figure_defaults.LARGE_SPAN, Figure_defaults.LARGE_SPAN)

        if (!layout.success) {
            console.error("Could not lay out a label")
            return 0
        }
        let w = 0, h = 0
        for (let l = 0; l < layout.lines.length; l++) {
            let lw = 0, items = layout.lines[l].items
            for (let i = 0; i < items.length; i++) {
                const item = items[i]
                lw += item.width
            }
            if (lw > w) w = lw
            h = Math.max(h, layout.lines[l].y)
        }
        const padding = 2 * this.inset
        return [w + padding, h + lineSpacing + padding]
    }

    // Draw this text inside a graphical object (container)
    renderIn(figure, container) {
        const ctx = figure.ctx,
            tc = new Context(this.style),
            fontSize = figure.fontSizePixels(tc),
            lineSpacing = fontSize * evaluate(tc.setDefault('lineSpacing', Figure_defaults.LINE_SPACING)),
            baseline = tc.setDefault('baseline', 0),
            layoutAlgorithm = tc.setDefault('layoutAlgorithm', "TeX"),
            strokeStyle = tc.setDefault('strokeStyle', null),
            inset = tc.setDefault('inset', 0),
            justification = this.style.setDefault('justification', "center"),
            verticalAlign = this.style.setDefault('verticalAlign', "center"),
            fillStyle = this.style.setDefault('fillStyle', "black"),
            maxh = evaluate(container.h()),
            y0 = evaluate(container.y0()) + fontSize + inset,
            y1 = evaluate(container.y1()) - inset,
            yc = evaluate(container.y())
        tc.set('container', container)
        let layout = {success: false, lines: []}
        this.text.resetCaches()
        let guessed_lines = 1,
            y = y0,
            max_guessed_lines = Math.floor(maxh/lineSpacing)
        if (verticalAlign == "top") guessed_lines = max_guessed_lines

        // if (DEBUG) console.log("max guessed lines = " + max_guessed_lines)

        // Compute the successful layout with the least guessed lines, or the largest
        // unsuccessful layout.
        let x0 = 0, x1 = 0, tries = 0
        for (; guessed_lines <= max_guessed_lines; guessed_lines++, tries++) {
            let ymax = y1
            switch (verticalAlign) {
                case "center":
                    y = yc - (guessed_lines - 1.5) * lineSpacing * 0.5
                    ymax = y + (guessed_lines - 0.25) * lineSpacing
                    break
                case "bottom":
                    y = y1 - (guessed_lines - 0.75) * lineSpacing
                    break
                default: break
            }
            [x0, x1] = container.xSpan(y - lineSpacing, y)
            x0 += inset
            x1 -= inset
            const ly = findLayout(figure, [{ item: this.text, context: tc }], 1,
                                  x0, y, x0, x1, ymax)
            if (ly.success) {
                layout = ly
                // if (DEBUG) console.log("found best layout at " + guessed_lines)
                break
            }
            if (!ly.success && verticalAlign == "top" && countItems(ly) == 0) {
                guessed_lines--
                y = y0 + tries
                if (y > ymax) break
            }
            if (countItems(ly) > countItems(layout)) layout = ly
        }

        if (!layout.success) {
            // console.log("Could not lay out text items in container " + container)
        }

        // Use the computed layout to horizontally position all the items
        // according to the current justification policy, and draw them.
        let currentFont = null, stretch = (justification == "full")
        const lines = layout.lines.reverse(), last = lines[lines.length - 1]
        for (let line of lines) {
            const {x0, x1, y, items} = line
            let items_rev = items.reverse()
            let lw = 0, stretchers = 0
            for (let i = 0; i < items_rev.length; i++) {
                const item = items_rev[i]
                lw += item.width
                stretchers += item.stretch
            }
            let extra = x1 - x0 - lw
            let x = x0
            switch (justification) {
                case "left":
                case "full": x = x0; break
                case "center": x = x0 + extra/2; break
                case "right": x = x0 + extra; break
            }
            for (let i = 0; i < items_rev.length; i++) {
                const item = items_rev[i],
                      font = item.font
                if (font && font != currentFont) {
                    font.setContextFont(ctx)
                    currentFont = font
                }
                if (item.item) {
                    if (item.fillStyle != null) ctx.fillStyle = item.fillStyle
                    if (item.strokeStyle != null) ctx.strokeStyle = item.strokeStyle
                    item.item.render(ctx, x, item.y)
                }
                if (stretch && stretchers > 0 && line !== last) {
                    x += (extra * item.stretch)/stretchers
                }
                x += item.width
            }
        }
    }

}

// A component of formatted text. It does not know what figure or container it belongs to.
class TextItem {
    constructor() {
    }

    // TextItem.layout tries to format this text item into the container
    // starting from baseline position (x,y) but without extending below y position
    // ymax, and with x1 as the right margin of the current line.  The result
    // is an object with these fields:
    // {
    //     success: a boolean indicating whether layout was completed
    //     positions: an array of positions at which formatting can continue
    //           after this item. For most text items, this is a single-element array, but
    //           breakable whitespace may return two positions. If success is false, this
    //           property is left undefined. A position has the following properties:
    //           {
    //              newLine: boolean; whether the next position is on the next line. In this
    //                 case there will be no x position
    //              x: the x position at which to start formatting the next context-item on the same line
    //                 (this property is undefined if newLine is true)
    //              renderable: an item appearing on the line (possibly undefined if nothing
    //                 to render or lay out or if success is false) with the following properties:
    //                   { item: the actual text item to render (may be null for non-rendered items)
    //                     y: vertical position of the item
    //                     width: the minimum width of this item
    //                     stretch: the amount of stretchiness (typically 0 for non-whitespace)
    //                     font: the font
    //                     fillStyle: the fill style
    //                     strokeStyle: the stroke style (if any)
    //                   }
    //           }
    //     following: an array of context-items (see findLayout) that should be
    //                formatted after this one, or undefined if success is false.
    //                Elements are in forward order.
    // }
    layout(figure, textContext, x, y, x0, x1, ymax) {
        return {success: false}
    }

    // Render this text item at (x,y) in graphics context ctx.  The font, fill
    // style, and stroke style are assumed already to be set correctly.
    // Default: do nothing
    render(ctx, x, y) {}

    // Report the width of this item in the given context and font choice.
    getWidth(ctx, font) { return 0 }

    // Erase any cached information specific to a given layout task
    resetCaches() {}
    toString() { return "[TextItem]" }
}

function createText(...text) {
    text = text.flat()
    const result = []
    text.forEach(t => {
        if (typeof t == STRING_STR) { 
            let lines = 0
            t.split(/\n/).forEach(ln => {
                let wds = 0
                if (lines++) {
                    result.push(new LineBreak())
                }
                ln.split(/  */).forEach(w => {
                    if (w) {
                        if (wds++) {
                            result.push(new Whitespace())
                        }
                        let parts = 0
                        w.split(/­/).forEach(part => {
                            if (parts++) result.push(new Hyphen())
                            result.push(new WordText(part))
                        })
                    }
                })
            })
        } else {
            result.push(t)
            if (!t.layout) console.error("Can't concatenate non-text item")
        }
    })
    if (result.length == 0) return new WordText("")
    else if (result.length == 1) return result[0]
    else return new ConcatText(...result)
}

//  A context for specifying the style of graphical objects, text items, etc.
//  It is provided at the point of rendering. The context is updated
//  imperatively, but it inherits properties from its parent context, so any
//  changes made to it do not affect the parent.
class Context {
    // Create a context that inherits from parent
    constructor(parent) {
        if (Array.isArray(parent)) {
            this.properties = new Map(parent)
            this.parent = null
        } else {
            this.properties = new Map()
            this.parent = parent
        }
    }
    has(name) {
        if (this.properties.has(name)) return true
        if (!this.parent) return false
        return this.parent.has(name)
    }
    set(name, value) {
        if (value === undefined) console.error("Setting an undefined style")
        this.properties.set(name, value)
        return this
    }
    // bind name to value if there is no existing binding
    setDefault(name, value) {
        if (this.has(name)) return this.get(name)
        this.properties.set(name, value)
        return value
    }
    setAll(dict) {
        if (Array.isArray(dict)) {
            for (const pair of dict) {
                this.set(pair[0], pair[1])
            }
        } else {
            for (let key in dict) {
                this.set(key, dict[key])
            }
        }
        return this
    }
    get(name, required) {
        const key = name,
              properties = this.properties,
              val = properties.get(key)
        if (val !== undefined) return val
        if (this.parent) {
            const v2 = this.parent.get(name)
            if (v2 !== undefined) properties.set(key, v2)
            return v2
        }
        if (required) console.error("Requested undefined style attribute '" + name + "'")
        return undefined
    }
}

// A text item that consists of a simple string that should not be broken.
class WordText extends TextItem {
    constructor(t) {
        super()
        this.text = t
    }
    toString() { return `[WordText ${this.text}]` }
    getWidth(ctx, font) {
        let width = this.width
        if (!width) {
            font.setContextFont(ctx)
            this.width = width = ctx.measureText(this.text).width
        }
        return width
    }

    // See TextItem.layout
    layout(figure, tc, x, y, x0, x1, ymax) {
        const ctx = figure.ctx,
              font = new Font(figure, tc),
              width = this.getWidth(ctx, font)
        if (x + width > x1) {
            return { success: false }
        }
        let renderable = {
          item: this,
          y: y - tc.get("baseline"),
          width,
          stretch: 0, 
          font,
          fillStyle: tc.get("fillStyle"),
          // strokeStyle: tc.get("strokeStyle"),
        }

        return { success: true,
                 positions: [{ newLine: false, x: x + width, renderable }],
                 following: []
               }
    }
    render(ctx, x, y) {
        ctx.fillText(this.text, x, y)
    }
    resetCaches() {
        delete this.width 
    }
}

var ws_counter = 0

var EMPTY_IMMUTABLE_ARRAY = []

class Whitespace extends TextItem {
    constructor() {
        super()
        this.index = ws_counter++
    }
    toString() { return `[Whitespace ${this.index}]` }
    // See TextItem.layout
    getWidth(ctx, font) {
        let space = this.width
        if (!space) {
              font.setContextFont(ctx)
              space = ctx.measureText(" ").width
              this.width = space
        }
        return space
    }
    layout(figure, tc, x, y, x0, x1, ymax) {
        const space = this.getWidth(figure.ctx, new Font(figure, tc))
        const positions = []
        if (x + space <= x1) {
            positions.push( { newLine: false,
                              x: x + space,
                              renderable: {
                                item: null,
                                width: space,
                                stretch: 1
                              }
                            } )
        }
        const ls = tc.get('lineSpacing') * figure.fontSizePixels(tc)
        if (y + ls <= ymax) {
            positions.push({
                newLine: true
            })
        }
        return {
            success: positions.length > 0,
            positions,
            following: []
        }
    }
    resetCaches() {
        delete this.width 
        delete this.cache
    }
}

// Create a negative space for text
class NegSpace extends WordText {
    constructor(size) {
        super()
        this.offset = -size
    }
    getWidth(ctx, font) {
        return this.offset
    }
    render(ctx, x, y) {}
}

class ConcatText extends TextItem {
    // The arguments (other than the figure) can be either other ContainedText
    // objects or strings. Strings are automatically split into words
    // around whitespace
    constructor(...text) {
        super()
        this.items = text
    }
    toString() { return "[ConcatText]" }
    // See TextItem.layout
    layout(figure, tc, x, y, x0, x1, ymax) {
        return {
            success: true,
            positions: [{newLine: false, x}],
            following: this.items.map(item => ({item, context: tc}))
        }
    }
    resetCaches() {
        for (let item of this.items) item.resetCaches();
    }
}

class Hyphen extends TextItem {
    constructor() {
        super()
        this.cost = Figure_defaults.HYPHEN_COST
    }
    toString() { return "[Hyphen]" }
    // See TextItem.layout
    layout(figure, tc, x, y, x0, x1, ymax) {
        let width = this.width
        if (!width) {
              const font = new Font(figure, tc)
              font.setContextFont(figure.ctx)
              width = figure.ctx.measureText("-").width
              this.width = width
        }
        const positions = [{ newLine: false, x }]
        const ls = tc.get('lineSpacing') * figure.fontSizePixels(tc)
        if (x + width <= x1 && y + ls <= ymax) {
            positions.push( { newLine: true,
                              renderable: {
                                 item: this,
                                 y,
                                 width,
                                 stretch: 0
                              }
                            } )
        }
        return {
            success: true,
            positions,
            following: []
        }
    }
    render(ctx, x, y) {
        ctx.fillText("-", x, y)
    }
}

class LineBreak extends TextItem {
    constructor() {
        super()
        this.cost = Figure_defaults.HYPHEN_COST
    }
    toString() { return "[LineBreak]" }
    // See TextItem.layout
    layout(figure, tc, x, y, x0, x1, ymax) {
        const positions = []
        const ls = tc.get('lineSpacing') * figure.fontSizePixels(tc)
        if (y + ls <= ymax) {
            positions.push( { newLine: true } )
        }
        return {
            success: true,
            positions,
            following: []
        }
    }
    render(ctx, x, y) {
        ctx.fillText("-", x, y)
    }
}

// A ComputedText is evaluated dynamically using a function, once per
// layout task
class ComputedText extends TextItem {
    constructor(f) {
        super()
        this.creator = f
    }
    initializeIfNecessary() {
        if (this.hasOwnProperty("item")) return
        this.item = this.creator()
    }
    layout(figure, textContext, x, y, x0, x1, ymax) {
        delete this.item
        this.initializeIfNecessary()
        return this.item.layout(figure, textContext, x, y, x0, x1, ymax)
    }
    render(ctx, x, y) {
        this.initializeIfNecessary()
        this.item.render(ctx, x, y)
    }
    getWidth(ctx, font) {
        this.initializeIfNecessary()
        return this.item.getWidth(ctx, font)
    }
    resetCaches() {
        delete this.item
    }
    toString() {
        this.initializeIfNecessary()
        return "computed[" + this.item.toString() + "]"
    }
}

// A ContextTransformer wraps some text in a context that is modified in
// some way to change how the text appears.
class ContextTransformer extends TextItem {
    // Create a ContextTransformer that wraps the text
    // and transforms the outer context tc into f(tc).
    constructor(f, text) {
        super()
        this.text = (typeof text == STRING_STR) ? new WordText(text) : text
        this.fun = f
    }
    // See TextItem.layout
    layout(figure, tc, x, y, x0, x1, ymax) {
        tc = this.transformContext(tc, figure)
        return this.text.layout(figure, tc, x, y, x0, x1, ymax)
    }
    // Transform the outside context in some way. Default
    // implementation: do nothing to context.
    transformContext(tc, figure) {
        return this.fun(new Context(tc))
    }
    resetCaches() {
        this.text.resetCaches()
    }
}

class SuperscriptText extends ContextTransformer {
    constructor(text) { super(null, text) }
    transformContext(tc, figure) {
        const baseline = tc.get("baseline") || 0,
              font = new Font(figure, tc),
              fontSize = tc.get("fontSize") || Figure_defaults.FONT_SIZE,
              scriptSize = tc.get("scriptSize") || Figure_defaults.SCRIPTSIZE,
              superscriptOffset = tc.get("superscriptOffset") ||
                                  Figure_defaults.SUPERSCRIPT_OFFSET
        tc = new Context(tc)
        tc.set('fontSize', fontSize * scriptSize)
          .set('baseline', baseline + superscriptOffset * fontSize)
        return tc
    }
}

class SubscriptText extends ContextTransformer {
    constructor(text) { super(null, text) }
    transformContext(tc, figure) {
        const baseline = tc.get("baseline") || 0,
              font = new Font(figure, tc),
              fontSize = tc.get("fontSize") || Figure_defaults.FONT_SIZE,
              scriptSize = tc.get("scriptSize") || Figure_defaults.SCRIPTSIZE,
              subscriptOffset = tc.get("subscriptOffset") ||
                                Figure_defaults.SUBSCRIPT_OFFSET
        tc = new Context(tc)
        tc.set('fontSize', fontSize * scriptSize)
          .set('baseline', baseline + subscriptOffset * fontSize)
        return tc
    }
}

class ItalicText extends ContextTransformer {
    constructor(text) { super(null, text) }
    transformContext(tc, figure) {
        tc = new Context(tc)
        tc.set('fontStyle', "italic")
        return tc
    }
}

class BoldText extends ContextTransformer {
    constructor(text) { super(null, text) }
    transformContext(tc, figure) {
        tc = new Context(tc)
        tc.set('fontStyle', "bold")
        return tc
    }
}

// A Graphic intended to be overridden by users with arbitrary
// rendering code.  It draws itself by calling a method draw(context, frame,
// time, x0, y0, x1, y1), simplifying the coding.
class UserDefined extends Graphic {
    constructor(figure) {
        super(figure)
    }
    render() {
        const [x0, y0, x1, y1] = evaluate([this.x0(), this.y0(), this.x1(), this.y1()]),
              fig = this.figure
        this.draw(fig.ctx, fig.currentFrame.index, fig.renderTime, x0, x1, y0, y1)
    }
    // Override this to change the appearance of this object
    //   context: the 2D rendering context
    //   frame: the index of the current animation frame
    //   time: the fraction of the current frame that is completed (0-1)
    draw(context, frame, time, x0, x1, y0, y1) {
        context.fillStyle = 'gray'
        context.fillRect(x0, y0, x1-x0, y1-y0)
    }
}

class InteractiveObject extends LayoutObject {
    constructor(figure) {
        super()
        figure.Graphics.push(this)
        figure.interactives.push(this)
        this.figure = figure
    }
    render() {}
    active() { return true }
    visible() { return true }
    // Whether (mx, my) is inside the perimeter of this object. By default
    // this is a bounding box check
    inBounds(mx, my) {
        const x0 = evaluate(this.x0()),
              x1 = evaluate(this.x1()),
              y0 = evaluate(this.y0()),
              y1 = evaluate(this.y1())
        return (mx >= x0 && mx <= x1 && my >= y0 && my <= y1)
    }
    // Check whether this object responds to the given (x,y) mouseup event,
    // and perform the appropriate action if so.
    mouseup(e) {}
    // Check whether this object responds to the given (x,y) mousedown event,
    // and perform the appropriate action if so.
    mousedown(x, y, e) {}
    mousemove(x, y, e) {}
}

InteractiveObject.prototype.renderIfVisible = Graphic.prototype.renderIfVisible
InteractiveObject.prototype.visible = Graphic.prototype.visible
InteractiveObject.prototype.placeOver = Graphic.prototype.placeOver
InteractiveObject.prototype.placeUnder = Graphic.prototype.placeUnder

// A handle that can be dragged interactively.
class Handle extends InteractiveObject {
    constructor(figure, strokeStyle, x, y) {
        super(figure)
        const vx = new Variable(figure, "hx"),
              vy = new Variable(figure, "hy")
        this.x_ = vx
        this.y_ = vy
        this.variables = () => new Set([vx, vy])
        this.size = 5
        this.strokeStyle = strokeStyle || figure.getStyle('strokeStyle')
        this.isActive = true
        this.isVisible = true
        figure.positive(vx)
        figure.positive(vy)
        figure.leq(vx, figure.canvasRect().x1())
        figure.leq(vy, figure.canvasRect().y1())
    }
    w() { return 0 }
    h() { return 0 }
    renderIfVisible() {
        if (this.visible(this.figure.currentFrame)) this.render()
    }
    render() {
        const figure = this.figure, ctx = figure.ctx
        if (ctx.printMedia) return
        ctx.beginPath()
        const x = evaluate(this.x()),
              y = evaluate(this.y())
        ctx.moveTo(x - this.size, y)
        ctx.lineTo(x, y + this.size)
        ctx.lineTo(x + this.size, y)
        ctx.lineTo(x, y - this.size)
        ctx.closePath()
        ctx.lineWidth = 1
        if (this.strokeStyle != null) {
            ctx.strokeStyle = this.strokeStyle
            ctx.setLineDash([])
            ctx.stroke()
        }
    }
    setStrokeStyle(style) {
        this.strokeStyle = style
        return this
    }
    mousedown(x, y, e) {
        if (this.figure.currentValuation === undefined)
            { console.error("No current valuation"); return }
        const hx = evaluate(this.x()), hy = evaluate(this.y()),
              expand = e.type == "touchstart" ? 20 : 0,
              // XXX should use radiusX/radiusY property when available
              r = this.size + expand
        if (sqdist(x - hx, y - hy) <= r * r) {
            this.figure.focused = this
            return false
        } else {
            return true
        }
    }
    mouseup(e) {
        if (this.figure.focused == this) {
            this.figure.focused = null
            if (this.xcon) {
                this.figure.removeConstraints(this.xcon, this.ycon)
            }
        }
    }
    mousemove(x, y, e) {
        if (this.xcon) {
            this.figure.removeConstraints(this.xcon, this.ycon)
        }
        this.xcon = new NearZero(this.figure, new Minus(this.x(), x), 10)
        this.ycon = new NearZero(this.figure, new Minus(this.y(), y), 10)
        for (let expr of this.x_.dependents) {
            if (expr.hasOwnProperty('cachedResult')) expr.clearCache()
            // console.log("clearing cached value for "+ expr)
        }
        this.xcon.stage = 0
        this.ycon.stage = 0
        if (!this.figure.renderNeeded) {
            this.figure.delayedRender()
        }
    }
    toString() { return "Handle" }
    variables() { return new Set().add(this.x_).add(this.y_) }
}

// An interactive Button. Subclasses are expected to provide its behavior when pressed
// by overriding activate(), and its appearance by overriding render()
class Button extends InteractiveObject {
    constructor(figure) {
        super(figure)
        const vx = new Variable(figure, "x"),
              vy = new Variable(figure, "y")
        this.x_ = vx
        this.y_ = vy
        this.variables = () => new Set([vx,vy])
        figure.geq(vx,0)
        figure.geq(vy,0)
        figure.leq(vx, figure.canvasRect().x1())
        figure.leq(vy, figure.canvasRect().y1())

        this.size = 30
        this.fillStyle = "#ccc"
        this.strokeStyle = "#444"
        this.pressed = false
    }
    w() { return this.size }
    h() { return this.size }
    
    inBounds(mx, my) {
        const [x, y] = evaluate([this.x(), this.y()])
        if (mx < x - this.size * 0.5) return false
        if (mx > x + this.size * 0.5) return false
        if (my > y + this.size * 0.3) return false
        if (my < y - this.size * 0.3) return false
        return true
    }
    mousedown(mx, my, e) {
        if (!this.inBounds(mx, my)) return true
        this.pressed = true
        this.figure.focused = this
        this.render(this.figure)
        return false
    }
    mouseup(e) {
        const [x, y] = evaluate([this.x(), this.y()])
        if (!this.pressed) return true
        this.pressed = false
        this.figure.focused = null
        this.render(this.figure)
        this.activate()
        return false
    }
    mousemove(mx, my, e) {
        const [x, y] = evaluate([this.x(), this.y()])
        if (this.inBounds(mx, my, x, y)) return
        if (this.pressed) {
            this.pressed = false
            this.figure.focused = null
            this.render(this.figure)
        }
    }
    active() { return true }
}

// A button that advances the animation.
class AdvanceButton extends Button {
    constructor(figure) {
        super(figure)
    }
    w() { return this.size * 1.1}
    h() { return this.size * 0.7 }

    render() {
        const figure = this.figure, ctx = figure.ctx
        if (ctx.printMedia) return
        const s = this.size
        ctx.beginPath()
        const x = evaluate(this.x()), y = evaluate(this.y())
        ctx.save()
        ctx.translate(x - s * 0.5, y - s*0.3)
        Paths.roundedRect(ctx, 0, s, 0, s*0.6, s*0.3)
        if (this.pressed)
            ctx.fillStyle = "#888"
        else
            ctx.fillStyle = this.fillStyle
        ctx.fill()
        ctx.strokeStyle = this.strokeStyle
        ctx.lineWidth = s/10
        ctx.setLineDash([])
        ctx.stroke()
        ctx.fillStyle = ctx.strokeStyle
        ctx.beginPath()
        ctx.moveTo(s*0.3, s*0.1)
        ctx.lineTo(s*0.8, s*0.3)
        ctx.lineTo(s*0.3, s*0.5)
        ctx.closePath()
        ctx.fill()
        ctx.restore()
    }
    activate() {
        this.figure.advance()
    }
}
AdvanceButton.prototype.installHolder = Graphic.prototype.installHolder

// A Control is a non-rendered object that receives input directed
// to a particular graphical object.
class Control extends InteractiveObject {
    constructor(figure, graphic) {
        super(figure)
        this.graphic = graphic
    }
    x() { return this.graphic.x() }
    y() { return this.graphic.y() }
    w() { return this.graphic.w() }
    h() { return this.graphic.h() }
}

// A global is an expression whose value may change but is not affected by 
// the values of variables that are being solved for. Its value is provided
// by a function that is passed to the constructor.
class Global extends Expression {
    constructor(fun, name) {
        super()
        this.fun = fun
        this.name = name
    }
    evaluate(valuation, doGrad) {
        const v0 = this.checkCache(valuation, doGrad)
        if (v0) return v0
        const v = (this.fun)(valuation)
        CHECK_NAN && checkNaNResult(v)
        if (valuation) {
            this.solutionValue = v
        } else {
            this.renderValue = v
        }
        return this.recordCache(valuation, doGrad, doGrad ? [v, getZeros(valuation.length)] : v)
    }
    backprop(task) {}
    addDependencies(task) {
        // despite lack of backpropagation, this is needed to force initialization
    }
    toString() { return this.name || "Global" }
}

// An expression that reports its value and gives information
// about backpropagation.
class DebugExpr extends Expression {
    constructor(name, expr) {
        super()
        this.expr = expr
        this.name = name
    }
    evaluate(valuation, doGrad) {
        const r = evaluate(this.expr, valuation, doGrad)
        console.log("debug expr " + this.name + " evaluated to ", r)
        return r
    }
    backprop(task) {
        console.log("backpropagating expr " + this.name + " : " + this.bpDiff)
        task.propagate(this.expr, this.bpDiff)
    }
    addDependencies(task) {
        task.prepareBackProp(this.expr)
    }
    variables() {
        return exprVariables(this.expr)
    }
    toString() {
        return "debug(" + this.expr + ")"
    }
    x() {
        return this.expr.x()
    }
    y() {
        return this.expr.y()
    }
    w() {
        return this.expr.w()
    }
    h() {
        return this.expr.h()
    }
    isLegalPoint() {
        return legalPoint(this.expr)
    }
}

class DOMElementBox extends LayoutObject {
    constructor(figure, id) {
        super()
        if (typeof id == STRING_STR) {
            this.id = id
        } else {
            this.obj = id
            this.id = "anonymous"
        }
        if (!isFigure(figure)) {
            console.error("DOMElementBox requires a figure to compute coordinates relative to")
        }
        this.figure = figure
        this.x_ = this.centerX()
        this.y_ = this.centerY()
    }
    boundingRect() {
        if (!this.obj) {
            this.obj = document.getElementById(this.id)
            if (!this.obj) {
                console.error("Can't find DOM element with id  " + id)
            }
        }
        return this.obj.getBoundingClientRect()
    }
    x0() { return new Global(() => this.boundingRect().left - this.figure.canvas.getBoundingClientRect().left, "DOM element " + this.id + ".x0") }
    y0() { return new Global(() => this.boundingRect().top - this.figure.canvas.getBoundingClientRect().top, "DOM element " + this.id + ".y0") }
    w() { return new Global(() => this.boundingRect().width, "DOM element " + this.id + ".w") }
    h() { return new Global(() => this.boundingRect().height, "DOM element " + this.id + ".h") }
    x1() { return new Global(() => {
             const b = this.boundingRect()
             return b.right - this.figure.canvas.getBoundingClientRect().left
           }, "DOM element " + this.id + ".x1")
         }
    y1() { return new Global(() => {
             const b = this.boundingRect()
             return b.bottom - this.figure.canvas.getBoundingClientRect().top
           }, "DOM element " + this.id + ".y1")
         }
    addDependencies(task) {
        task.prepareBackProp(this.x())
        task.prepareBackProp(this.y())
    }
}

function fullWindowCanvas(canvas) {
    const resizeCanvasToWindow = () => {
        const _width = window.innerWidth,
              _height = window.innerHeight
        // console.log("Resizing to " + _width + " " + _height)
        canvas.style.width = _width + "px"
        canvas.style.height = _height + "px"
    }
    addEventListener('resize', 
        () => resizeCanvasToWindow(canvas)
    )
    resizeCanvasToWindow(canvas)
}

class CanvasRect extends LayoutObject {
    constructor(figure) {
        super()
        this.figure = figure
        this.x_ = this.centerX()
        this.y_ = this.centerY()
    }
    x0() { return 0 }
    x1() { return new Global(() => {
        if (!this.figure.width) this.figure.setupCanvas()
        return this.figure.width
    }, "Max x coordinate of figure " + this.figure.name)}
    y0() { return 0 }
    y1() { return new Global(() => this.figure.height,
                             "Max y coordinate of figure " + this.figure.name) }
    w() { return new Global(() => this.figure.width,
                             "Width of figure " + this.figure.name)}
    h() { return new Global(() => this.figure.height,
                             "Height of figure " + this.figure.name) }
    backprop(task) {}
    addDependencies(task) {}
}

function exceedsError(x, y) {
    if (isNaN(x) || isNaN(y)) return true
    if (x > y) {
        const t = x; x = y; y = t
    }
    return (Math.abs(1.0 - y/x) > 0.00001 && Math.abs(y-x) > 0.00001)
}

function rgbStyle(r,g,b) {
    return `rgb(${r}, ${g}, ${b})`
}

function drawCorners(figure) {
    const ctx = figure.ctx,
          canvas = figure.canvas
    ctx.strokeStyle = "black"
    ctx.beginPath()
    ctx.moveTo(0, 0)
    ctx.lineTo(Figure_defaults.TRIANGLE_SIZE, 0)
    ctx.lineTo(0, Figure_defaults.TRIANGLE_SIZE)
    ctx.lineWidth = 1.5
    ctx.fillStyle = "green"
    ctx.closePath()
    ctx.fill()
    ctx.setLineDash([])
    ctx.stroke()

    ctx.beginPath()
    ctx.moveTo(figure.width, figure.height)
    ctx.lineTo(figure.width - Figure_defaults.TRIANGLE_SIZE, figure.height)
    ctx.lineTo(figure.width, figure.height - Figure_defaults.TRIANGLE_SIZE)
    ctx.closePath()
    ctx.fill()
    ctx.stroke()
}

class Corners extends Graphic {
    constructor(figure)  {
        super(figure) 
    }
    render() { drawCorners(this.figure) }
}

function autoResize() {
    window.addEventListener('resize',
      () =>
        Figures.forEach(f => {
            f.renderNeeded = true
            setTimeout(() => f.renderIfDirty(false), 1000/Figure_defaults.FRAMERATE) // collapse multiple renders
        })
        )
}

function setMinimizationAlgorithm(a) {
    algorithm = a
}
function reportPerformance(b) {
    REPORT_PERFORMANCE = b
}

  return ({
    Figure, Figures, Frame, Variable, LayoutObject, Graphic, GraphicalObject: Graphic,
    Point, Box, Line, Connector, Rectangle, Square, Circle, Ellipse, Polygon,
    ContainedText, Context, TextItem, createText, InteractiveObject,
    CanvasRect, Button, LineLabel, Group, ConstraintGroup, Loss, Font, Corners,
    Expression, Minus, Plus, Times, Divide, Sqrt, Distance, Average, Min, Max,
    Projection, Conditional, Paths, autoResize, rgbStyle, Global, UserDefined,
    ComputedText, Control,
    evaluate, SolverCallback, fullWindowCanvas, setupTouchListeners, getFigureByName,
    Figure_defaults, isFigure, statistics, solvedValue, drawLineEndSeg,
    evaluate, sqdist, exprVariables, DebugExpr, defaultMinimizationOptions,
    setMinimizationAlgorithm, reportPerformance, plus, terms, similarResults,
    UNCMIN_GRADIENT,
    UNCMIN_BFGS,
    UNCMIN_LBFGS,
    DEBUG
  })
}()