StructUtility.ts

/* Copyright (c) 2025-2026 Voxgig Ltd. MIT LICENSE. */

// String constants are explicitly defined.

// Mode value for inject step (bitfield).
const M_KEYPRE = 1
const M_KEYPOST = 2
const M_VAL = 4

const S_BKEY = '`$KEY`'
const S_BANNO = '`$ANNO`'
const S_BEXACT = '`$EXACT`'
const S_BVAL = '`$VAL`'

const S_DKEY = '$KEY'
const S_DTOP = '$TOP'
const S_DERRS = '$ERRS'
const S_DSPEC = '$SPEC'

const S_list = 'list'
const S_base = 'base'
const S_boolean = 'boolean'
const S_function = 'function'
const S_symbol = 'symbol'
const S_instance = 'instance'
const S_key = 'key'
const S_any = 'any'
const S_nil = 'nil'
const S_null = 'null'
const S_number = 'number'
const S_object = 'object'
const S_string = 'string'
const S_decimal = 'decimal'
const S_integer = 'integer'
const S_map = 'map'
const S_scalar = 'scalar'
const S_node = 'node'

const S_BT = '`'
const S_CN = ':'
const S_CS = ']'
const S_DS = '$'
const S_DT = '.'
const S_FS = '/'
const S_KEY = 'KEY'
const S_MT = ''
const S_OS = '['
const S_SP = ' '
const S_CM = ','
const S_VIZ = ': '

let t = 31
const T_any = (1 << t--) - 1
const T_noval = 1 << t-- // Means property absent, undefined. Also NOT a scalar!
const T_boolean = 1 << t--
const T_decimal = 1 << t--
const T_integer = 1 << t--
const T_number = 1 << t--
const T_string = 1 << t--
const T_function = 1 << t--
const T_symbol = 1 << t--
const T_null = 1 << t--
t -= 7
const T_list = 1 << t--
const T_map = 1 << t--
const T_instance = 1 << t--
t -= 4
const T_scalar = 1 << t--
const T_node = 1 << t--

const TYPENAME = [
  S_any,
  S_nil,
  S_boolean,
  S_decimal,
  S_integer,
  S_number,
  S_string,
  S_function,
  S_symbol,
  S_null,
  '',
  '',
  '',
  '',
  '',
  '',
  '',
  S_list,
  S_map,
  S_instance,
  '',
  '',
  '',
  '',
  S_scalar,
  S_node,
]

// The standard undefined value for this language.
const NONE = undefined

const SKIP = { '`$SKIP`': true }
const DELETE = { '`$DELETE`': true }

const R_INTEGER_KEY = /^[-0-9]+$/
const R_ESCAPE_REGEXP = /[.*+?^${}()|[\]\\]/g // Chars that need escaping in regexp.
const R_QUOTES = /"/g
const R_DOT = /\./g
const R_CLONE_REF = /^`\$REF:([0-9]+)`$/
const R_META_PATH = /^([^$]+)\$([=~])(.+)$/
const R_DOUBLE_DOLLAR = /\$\$/g
const R_TRANSFORM_NAME = /`\$([A-Z]+)`/g
const R_INJECTION_FULL = /^`(\$[A-Z]+|[^`]*)[0-9]*`$/
const R_BT_ESCAPE = /\$BT/g
const R_DS_ESCAPE = /\$DS/g
const R_INJECTION_PARTIAL = /`([^`]+)`/g

const MAXDEPTH = 32

// Keys are strings for maps, or integers for lists.
type PropKey = string | number

// Type that can be indexed by both string and number keys.
type Indexable = { [key: string]: any } & { [key: number]: any }

type InjectMode = number

// Handle value injections using backtick escape sequences:
// - `a.b.c`: insert value at {a:{b:{c:1}}}
// - `$FOO`: apply transform FOO
type Injector = (
  inj: Injection,
  val: any,
  ref: string, // Original injection reference string.
  store: any,
) => any

// Apply a custom modification to injections.
type Modify = (val: any, key?: PropKey, parent?: any, inj?: Injection, store?: any) => void

type WalkApply = (
  // Map keys are strings, list keys are numbers, top key is NONE
  key: string | number | undefined,
  val: any,
  parent: any,
  path: string[],
) => any

// Return type string for narrowest type.
function typename(t: number) {
  return getelem(TYPENAME, Math.clz32(t), TYPENAME[0])
}

// Get a defined value. Returns alt if val is undefined.
function getdef(val: any, alt: any) {
  if (NONE === val) {
    return alt
  }
  return val
}

// Value is a node - defined, and a map (hash) or list (array).
// NOTE: typescript
// things
function isnode(val: any): val is Indexable {
  return null != val && S_object == typeof val
}

// Value is a defined map (hash) with string keys.
function ismap(val: any): val is { [key: string]: any } {
  return null != val && S_object == typeof val && !Array.isArray(val)
}

// Value is a defined list (array) with integer keys (indexes).
function islist(val: any): val is any[] {
  return Array.isArray(val)
}

// Value is a defined string (non-empty) or integer key.
function iskey(key: any): key is PropKey {
  const keytype = typeof key
  return (S_string === keytype && S_MT !== key) || S_number === keytype
}

// Check for an "empty" value - undefined, empty string, array, object.
function isempty(val: any) {
  return (
    null == val ||
    S_MT === val ||
    (Array.isArray(val) && 0 === val.length) ||
    (S_object === typeof val && 0 === Object.keys(val).length)
  )
}

function isfunc(val: any): val is (...args: any[]) => any {
  return S_function === typeof val
}

// The integer size of the value. For arrays and strings, the length,
// for numbers, the integer part, for boolean, true is 1 and falso 0, for all other values, 0.
function size(val: any): number {
  if (islist(val)) {
    return val.length
  } else if (ismap(val)) {
    return Object.keys(val).length
  }

  const valtype = typeof val

  if (S_string == valtype) {
    return val.length
  } else if (S_number == typeof val) {
    return Math.floor(val)
  } else if (S_boolean == typeof val) {
    return true === val ? 1 : 0
  } else {
    return 0
  }
}

function slice<V>(val: V, start?: number, end?: number, mutate?: boolean): V {
  if (S_number === typeof val) {
    start = null == start || S_number !== typeof start ? Number.MIN_SAFE_INTEGER : start
    end = (null == end || S_number !== typeof end ? Number.MAX_SAFE_INTEGER : end) - 1
    return Math.min(Math.max(val as number, start), end) as V
  }

  const vlen = size(val)

  if (null != end && null == start) {
    start = 0
  }

  if (null != start) {
    if (start < 0) {
      end = vlen + start
      if (end < 0) {
        end = 0
      }
      start = 0
    } else if (null != end) {
      if (end < 0) {
        end = vlen + end
        if (end < 0) {
          end = 0
        }
      } else if (vlen < end) {
        end = vlen
      }
    } else {
      end = vlen
    }

    if (vlen < start) {
      start = vlen
    }

    if (-1 < start && start <= end && end <= vlen) {
      if (islist(val)) {
        if (mutate) {
          for (let i = 0, j = start; j < end; i++, j++) {
            val[i] = val[j]
          }
          val.length = end - start
        } else {
          val = val.slice(start, end) as V
        }
      } else if (S_string === typeof val) {
        val = (val as string).substring(start, end) as V
      }
    } else {
      if (islist(val)) {
        val = [] as V
      } else if (S_string === typeof val) {
        val = S_MT as V
      }
    }
  }

  return val
}

function pad(str: any, padding?: number, padchar?: string): string {
  str = S_string === typeof str ? str : stringify(str)
  padding = null == padding ? 44 : padding
  padchar = null == padchar ? S_SP : (padchar + S_SP)[0]
  return -1 < padding ? str.padEnd(padding, padchar) : str.padStart(0 - padding, padchar)
}

// Determine the type of a value as a bit code.
function typify(value: any): number {
  if (undefined === value) {
    return T_noval
  }

  const typestr = typeof value

  if (null === value) {
    return T_scalar | T_null
  } else if (S_number === typestr) {
    if (Number.isInteger(value)) {
      return T_scalar | T_number | T_integer
    } else if (isNaN(value)) {
      return T_noval
    } else {
      return T_scalar | T_number | T_decimal
    }
  } else if (S_string === typestr) {
    return T_scalar | T_string
  } else if (S_boolean === typestr) {
    return T_scalar | T_boolean
  } else if (S_function === typestr) {
    return T_scalar | T_function
  }

  // For languages that have symbolic atoms.
  else if (S_symbol === typestr) {
    return T_scalar | T_symbol
  } else if (Array.isArray(value)) {
    return T_node | T_list
  } else if (S_object === typestr) {
    if (value.constructor instanceof Function) {
      const cname = value.constructor.name
      if ('Object' !== cname && 'Array' !== cname) {
        return T_node | T_instance
      }
    }

    return T_node | T_map
  }

  // Anything else (e.g. bigint) is considered T_any
  return T_any
}

// Get a list element. The key should be an integer, or a string
// that can parse to an integer only. Negative integers count from the end of the list.
function getelem(val: any, key: any, alt?: any) {
  let out = NONE

  if (NONE === val || NONE === key) {
    return alt
  }

  if (islist(val)) {
    const nkey = parseInt(key)
    if (Number.isInteger(nkey) && re_test(R_INTEGER_KEY, '' + key)) {
      if (nkey < 0) {
        key = val.length + nkey
      }
      out = val[key]
    }
  }

  // null at a slot counts as "no value" — same Group A rule as getprop.
  if (null == out) {
    return 0 < (T_function & typify(alt)) ? alt() : alt
  }

  return out
}

// Safely get a property of a node. Undefined arguments return undefined.
// If the key is not found, return the alternative value, if any.
function getprop(val: any, key: any, alt?: any) {
  let out = alt

  if (NONE === val || NONE === key) {
    return alt
  }

  if (isnode(val)) {
    out = val[key]
  }

  // JSON null at a key is treated as "no value" for the default-substitution
  // rule. This unifies cross-port behaviour: every host language conflates
  // null and absent at the value level either always or via positional
  // checks; the library follows that constraint on observation.
  if (null == out) {
    return alt
  }

  return out
}

// Internal: literal value lookup that preserves stored JSON null. Group B
// callers (validate / transform commands / builders / inject internals) use
// this when they need to inspect the raw stored value at a slot regardless
// of whether it is null. The public getprop / getelem / haskey APIs treat
// null as absent (Group A) per UNDEF_SPEC.md.
function _lookup(val: any, key: any): any {
  if (NONE === val || NONE === key) return NONE
  if (isnode(val)) return val[key]
  return NONE
}

// Convert different types of keys to string representation.
// String keys are returned as is.
// Number keys are converted to strings.
// Floats are truncated to integers.
// Booleans, objects, arrays, null, undefined all return empty string.
function strkey(key: any = NONE): string {
  if (NONE === key) {
    return S_MT
  }

  const t = typify(key)

  if (0 < (T_string & t)) {
    return key
  } else if (0 < (T_boolean & t)) {
    return S_MT
  } else if (0 < (T_number & t)) {
    return key % 1 === 0 ? String(key) : String(Math.floor(key))
  }

  return S_MT
}

// Sorted keys of a map, or indexes (as strings) of a list.
// Root utility - only uses language facilities.
function keysof(val: any): string[] {
  return !isnode(val)
    ? []
    : ismap(val)
      ? Object.keys(val).sort()
      : (val as any).map((_n: any, i: number) => S_MT + i)
}

// Value of property with name key in node val is defined.
// Root utility - only uses language facilities.
function haskey(val: any, key: any) {
  // null at a key counts as "no value" — same rule as getprop.
  return null != getprop(val, key)
}

// List the sorted keys of a map or list as an array of tuples of the form [key, value].
// As with keysof, list indexes are converted to strings.
// Root utility - only uses language facilities.
function items(val: any): [string, any][]
function items<T>(val: any, apply: (item: [string, any]) => T): T[]
function items(val: any, apply?: (item: [string, any]) => any): any[] {
  let out: [string, any][] = keysof(val).map((k: any) => [k, val[k]])
  if (null != apply) {
    out = out.map(apply)
  }
  return out
}

function flatten(list: any[], depth?: number) {
  if (!islist(list)) {
    return list
  }
  return list.flat(getdef(depth, 1))
}

// Filter item values using check function.
function filter(val: any, check: (item: [string, any]) => boolean): any[] {
  const all = items(val)
  const numall = size(all)
  const out = []
  for (let i = 0; i < numall; i++) {
    if (check(all[i])) {
      out.push(all[i][1])
    }
  }
  return out
}

function escre(s: string) {
  return re_replace(R_ESCAPE_REGEXP, s, '\\$&')
}

// Alias so call sites read naturally next to the other re_* helpers.
function re_escape(s: string) {
  return escre(s)
}

function escurl(s: string) {
  s = null == s ? S_MT : s
  return encodeURIComponent(s)
}

// ===========================================================================
// Regex utility — uniform API. Every port exposes these same names. The
// dialect is the RE2 subset documented in /REGEX.md. Internal library code
// uses these helpers instead of host-language regex methods directly.
// ===========================================================================

function re_compile(pattern: string | RegExp, flags?: string): RegExp {
  if (pattern instanceof RegExp) {
    return pattern
  }
  return new RegExp(pattern, flags)
}

// First match. Returns [whole, capture1, ...] or null.
function re_find(pattern: string | RegExp, input: string): RegExpMatchArray | null {
  const re = pattern instanceof RegExp ? pattern : new RegExp(pattern)
  return input.match(re)
}

// All non-overlapping matches, left to right. Each element is the same shape
// as re_find's array.
function re_find_all(pattern: string | RegExp, input: string): RegExpMatchArray[] {
  let re: RegExp
  if (pattern instanceof RegExp) {
    re = pattern.global ? pattern : new RegExp(pattern.source, pattern.flags + 'g')
  } else {
    re = new RegExp(pattern, 'g')
  }
  const out: RegExpMatchArray[] = []
  let m: RegExpExecArray | null
  while ((m = re.exec(input)) !== null) {
    out.push(m as unknown as RegExpMatchArray)
    if (m[0] === '') re.lastIndex++ // avoid infinite loop on empty match
  }
  return out
}

// Replace every match. `replacement` is either a string (with $& and $1..$9)
// or a callback receiving the same array as re_find returns.
function re_replace(
  pattern: string | RegExp,
  input: string,
  replacement: string | ((m: RegExpMatchArray) => string),
): string {
  let re: RegExp
  if (pattern instanceof RegExp) {
    re = pattern.global ? pattern : new RegExp(pattern.source, pattern.flags + 'g')
  } else {
    re = new RegExp(pattern, 'g')
  }
  if (typeof replacement === 'function') {
    return input.replace(re, (...args: any[]) => {
      // Strip the trailing offset + full string args String.prototype.replace passes.
      // The callback below receives just the capture groups (whole at [0]).
      const groups = args.slice(0, -2) as unknown as RegExpMatchArray
      return replacement(groups)
    })
  }
  return input.replace(re, replacement)
}

function re_test(pattern: string | RegExp, input: string): boolean {
  const re = pattern instanceof RegExp ? pattern : new RegExp(pattern)
  return re.test(input)
}

// Replace a search string (all), or a regexp, in a source string.
function replace(s: string, from: string | RegExp, to: any) {
  let rs = s
  const ts = typify(s)
  if (0 === (T_string & ts)) {
    rs = stringify(s)
  } else if (0 < ((T_noval | T_null) & ts)) {
    rs = S_MT
  } else {
    rs = stringify(s)
  }
  return rs.replace(from, to)
}

// Concatenate url part strings, merging sep char as needed.
function join(arr: any[], sep?: string, url?: boolean) {
  const sarr = size(arr)
  const sepdef = getdef(sep, S_CM)
  const sepre = 1 === size(sepdef) ? escre(sepdef) : NONE
  const out = filter(
    items(
      // filter(arr, (n) => null != n[1] && S_MT !== n[1]),
      filter(arr, (n) => 0 < (T_string & typify(n[1])) && S_MT !== n[1]),
      (n) => {
        const i = +n[0]
        let s = n[1]

        if (NONE !== sepre && S_MT !== sepre) {
          if (url && 0 === i) {
            s = re_replace(re_compile(sepre + '+$'), s, S_MT)
            return s
          }

          if (0 < i) {
            s = re_replace(re_compile('^' + sepre + '+'), s, S_MT)
          }

          if (i < sarr - 1 || !url) {
            s = re_replace(re_compile(sepre + '+$'), s, S_MT)
          }

          s = re_replace(
            re_compile('([^' + sepre + '])' + sepre + '+([^' + sepre + '])'),
            s,
            '$1' + sepdef + '$2',
          )
        }

        return s
      },
    ),
    (n) => S_MT !== n[1],
  ).join(sepdef)

  return out
}

function jsonify(val: any, flags?: { indent?: number; offset?: number }) {
  let str = S_null

  if (null != val) {
    try {
      const indent = getprop(flags, 'indent', 2)
      str = JSON.stringify(val, null, indent)
      if (NONE === str) {
        str = S_null
      }
      const offset = getprop(flags, 'offset', 0)
      if (0 < offset) {
        // Left offset entire indented JSON so that it aligns with surrounding code
        // indented by offset. Assume first brace is on line with asignment, so not offset.
        str =
          '{\n' +
          join(
            items(slice(str.split('\n'), 1), (n: any) => pad(n[1], 0 - offset - size(n[1]))),
            '\n',
          )
      }
    } catch {
      str = '__JSONIFY_FAILED__'
    }
  }

  return str
}

// Safely stringify a value for humans (NOT JSON!).
function stringify(val: any, maxlen?: number, pretty?: any): string {
  let valstr = S_MT
  pretty = !!pretty

  if (NONE === val) {
    return pretty ? '<>' : valstr
  }

  if (S_string === typeof val) {
    valstr = val
  } else {
    try {
      valstr = JSON.stringify(val, function (_key: string, val: any) {
        if (val !== null && typeof val === 'object' && !Array.isArray(val)) {
          // Emit map keys in sorted order (deterministic output). Building the
          // sorted copy directly avoids the intermediate key/tuple arrays that
          // items() would allocate for every node.
          const keys = Object.keys(val).sort()
          const sortedObj: any = {}
          for (let i = 0; i < keys.length; i++) {
            sortedObj[keys[i]] = val[keys[i]]
          }
          return sortedObj
        }
        return val
      })
      valstr = re_replace(R_QUOTES, valstr, S_MT)
    } catch {
      valstr = '__STRINGIFY_FAILED__'
    }
  }

  if (null != maxlen && -1 < maxlen) {
    const js = valstr.substring(0, maxlen)
    valstr = maxlen < valstr.length ? js.substring(0, maxlen - 3) + '...' : valstr
  }

  if (pretty) {
    // Indicate deeper JSON levels with different terminal colors (simplistic wrt strings).
    const c = items(
      [81, 118, 213, 39, 208, 201, 45, 190, 129, 51, 160, 121, 226, 33, 207, 69],
      (n) => '\x1b[38;5;' + n[1] + 'm',
    )
    const r = '\x1b[0m'
    let d = 0,
      o = c[0],
      t = o
    for (const ch of valstr) {
      if (ch === '{' || ch === '[') {
        d++
        o = c[d % c.length]
        t += o + ch
      } else if (ch === '}' || ch === ']') {
        t += o + ch
        d--
        o = c[d % c.length]
      } else {
        t += o + ch
      }
    }
    return t + r
  }

  return valstr
}

// Build a human friendly path string.
function pathify(val: any, startin?: number, endin?: number) {
  let pathstr: string | undefined = NONE

  let path: any[] | undefined = islist(val)
    ? val
    : S_string == typeof val
      ? [val]
      : S_number == typeof val
        ? [val]
        : NONE

  const start = null == startin ? 0 : -1 < startin ? startin : 0
  const end = null == endin ? 0 : -1 < endin ? endin : 0

  if (NONE != path && 0 <= start) {
    path = slice(path, start, path.length - end)
    if (0 === path.length) {
      pathstr = '<root>'
    } else {
      pathstr = join(
        items(
          filter(path, (n) => iskey(n[1])),
          (n) => {
            const p = n[1]
            return S_number === typeof p ? S_MT + Math.floor(p) : re_replace(R_DOT, p, S_MT)
          },
        ),
        S_DT,
      )
    }
  }

  if (NONE === pathstr) {
    pathstr = '<unknown-path' + (NONE === val ? S_MT : S_CN + stringify(val, 47)) + '>'
  }

  return pathstr
}

// Clone a JSON-like data structure.
// NOTE: function and instance values are copied, *not* cloned.
function clone(val: any): any {
  const refs: any[] = []
  // Copy (don't clone) functions and non-plain-object instances by reference.
  // This inlines `0 < ((T_function | T_instance) & typify(v))` — the same set
  // of values (functions, class instances, bigints) — without a typify() call
  // per value, which dominated clone's cost.
  const replacer: any = (_k: any, v: any) => {
    const t = typeof v
    if (
      S_function === t ||
      'bigint' === t ||
      (S_object === t &&
        null !== v &&
        !Array.isArray(v) &&
        v.constructor instanceof Function &&
        'Object' !== v.constructor.name &&
        'Array' !== v.constructor.name)
    ) {
      return (refs.push(v), '`$REF:' + (refs.length - 1) + '`')
    }
    return v
  }
  const reviver: any = (_k: any, v: any, m: any) =>
    S_string === typeof v ? ((m = re_find(R_CLONE_REF, v)), m ? refs[m[1]] : v) : v
  if (NONE === val) {
    return NONE
  }
  const json = JSON.stringify(val, replacer)
  // A reviver forces V8 off its native JSON.parse fast path (a large cost). It
  // is only needed to swap `$REF:n` placeholders back for the copied-by-ref
  // functions/instances the replacer captured — so when none were captured,
  // parse without it.
  return 0 === refs.length ? JSON.parse(json) : JSON.parse(json, reviver)
}

// Define a JSON Object using function arguments.
function jm(...kv: any[]): Record<string, any> {
  const kvsize = size(kv)
  const o: any = {}
  for (let i = 0; i < kvsize; i += 2) {
    // Builders are Group B (value processing): preserve literal stored
    // values, including null. Direct array index distinguishes "slot exists
    // with value null" from "slot beyond end of kv".
    let k = i < kv.length ? kv[i] : '$KEY' + i
    k = 'string' === typeof k ? k : stringify(k)
    o[k] = i + 1 < kv.length ? kv[i + 1] : null
  }
  return o
}

// Define a JSON Array using function arguments.
function jt(...v: any[]): any[] {
  const vsize = size(v)
  const a: any = new Array(vsize)
  for (let i = 0; i < vsize; i++) {
    a[i] = getprop(v, i, null)
  }
  return a
}

function delprop<PARENT>(parent: PARENT, key: any): PARENT {
  if (!iskey(key)) {
    return parent
  }

  if (iscondensed(parent as any)) {
    throw new Error(
      'struct: condensed structures are immutable - ' + 'expand() first, then modify the copy',
    )
  }

  if (ismap(parent)) {
    key = strkey(key)
    delete (parent as any)[key]
  } else if (islist(parent)) {
    let keyI = +key

    if (isNaN(keyI)) {
      return parent
    }

    keyI = Math.floor(keyI)

    // Delete list element at position keyI, shifting later elements down.
    const psize = size(parent)
    if (0 <= keyI && keyI < psize) {
      for (let pI = keyI; pI < psize - 1; pI++) {
        parent[pI] = parent[pI + 1]
      }

      parent.length = parent.length - 1
    }
  }

  return parent
}

// Safely set a property. Undefined arguments and invalid keys are ignored.
// Returns the (possibly modified) parent.
// If the parent is a list, and the key is negative, prepend the value.
// NOTE: If the key is above the list size, append the value; below, prepend.
// NOTE: parent list may be new list, thus update references.
function setprop<PARENT>(parent: PARENT, key: any, val: any): PARENT {
  if (!iskey(key)) {
    return parent
  }

  if (iscondensed(parent as any)) {
    throw new Error(
      'struct: condensed structures are immutable - ' + 'expand() first, then modify the copy',
    )
  }

  if (ismap(parent)) {
    key = S_MT + key
    const pany = parent as any
    pany[key] = val
  } else if (islist(parent)) {
    let keyI = +key

    if (isNaN(keyI)) {
      return parent
    }

    keyI = Math.floor(keyI)

    // Set or append value at position keyI, or append if keyI out of bounds.
    if (0 <= keyI) {
      parent[slice(keyI, 0, size(parent) + 1)] = val
    } else {
      parent.unshift(val)
    }
  }

  return parent
}

function walk(
  val: any,

  before?: WalkApply,

  after?: WalkApply,

  maxdepth?: number,

  key?: string | number,
  parent?: any,
  path?: string[],
  pool?: string[][],
): any {
  if (NONE === pool) {
    pool = [[]]
  }
  if (NONE === path) {
    path = pool[0]
  }

  const depth = path.length

  let out = null == before ? val : before(key, val, parent, path)

  maxdepth = null != maxdepth && 0 <= maxdepth ? maxdepth : MAXDEPTH
  if (0 === maxdepth || (0 < maxdepth && maxdepth <= depth)) {
    return out
  }

  if (isnode(out)) {
    const childDepth = depth + 1
    let childPath = pool[childDepth]
    if (NONE === childPath) {
      childPath = new Array(childDepth)
      pool[childDepth] = childPath
    }
    // Sync prefix [0..depth-1] from the current path. Only needed once per
    // parent: siblings share the same prefix and will each overwrite slot
    // [depth] below.
    for (let i = 0; i < depth; i++) {
      childPath[i] = path[i]
    }

    // Iterate the sorted keys directly (as items() would order them) without
    // building the intermediate [key, value] tuple array items() allocates for
    // every node.
    const ckeys = keysof(out)
    for (let cI = 0; cI < ckeys.length; cI++) {
      const ckey = ckeys[cI]
      childPath[depth] = S_MT + ckey
      setprop(
        out,
        ckey,
        walk((out as any)[ckey], before, after, maxdepth, ckey, out, childPath, pool),
      )
    }
  }

  out = null == after ? out : after(key, out, parent, path)

  return out
}

// Merge a list of values into each other. Later values have
// precedence.  Nodes override scalars. Node kinds (list or map)
// override each other, and do *not* merge.  The first element is
// modified; the others are not.
function merge(val: any, maxdepth?: number): any {
  const md: number = slice(maxdepth ?? MAXDEPTH, 0)
  let out: any = NONE

  if (!islist(val)) {
    return val
  }

  const list = val as any[]
  const lenlist = list.length

  if (0 === lenlist) {
    return NONE
  } else if (1 === lenlist) {
    return list[0]
  }

  out = getprop(list, 0, {})

  for (let oI = 1; oI < lenlist; oI++) {
    const obj = list[oI]

    if (!isnode(obj)) {
      out = obj
    } else {
      // Current value at path end in overriding node.
      const cur: any[] = [out]

      // Current value at path end in destination node.
      const dst: any[] = [out]

      function before(key: string | number | undefined, val: any, _parent: any, path: string[]) {
        const pI = size(path)

        if (md <= pI) {
          setprop(cur[pI - 1], key, val)
        } else if (!isnode(val)) {
          cur[pI] = val
        }

        // Descend into override node - Set up correct target in `after` function.
        else {
          // Descend into destination node using same key.
          dst[pI] = 0 < pI ? getprop(dst[pI - 1], key) : dst[pI]
          const tval = dst[pI]

          const vtype = typify(val)

          // Matching override and destination so continue with their values.
          if (vtype === typify(tval)) {
            cur[pI] = tval
          }

          // Otherwise the override wins: a plain node is copied, taking
          // nothing from the destination, so no later merge writes into it.
          else if (0 === (T_instance & vtype)) {
            cur[pI] = islist(val) ? [] : {}
            dst[pI] = NONE
          } else {
            cur[pI] = val

            // A class instance is kept as is, so there is nothing to descend.
            val = NONE
          }
        }

        return val
      }

      function after(key: string | number | undefined, _val: any, parent: any, path: string[]) {
        const cI = size(path)
        const target = cur[cI - 1]
        const value = cur[cI]

        setprop(target, key, value)

        // walk writes this back into the override, so below the root it is
        // the override's own child (_lookup keeps a null, getprop would not).
        return 0 === cI ? value : _lookup(parent, key)
      }

      // Walk overriding node, creating paths in output as needed.
      out = walk(obj, before, after, maxdepth)
    }
  }

  if (0 === md) {
    out = getelem(list, -1)
    out = islist(out) ? [] : ismap(out) ? {} : out
  }

  return out
}

// Set a value using a path. Missing path parts are created.
// String paths create only maps. Use a string list to create list  parts.
function setpath(
  store: any,
  path: number | string | string[],
  val: any,
  injdef?: Partial<Injection>,
) {
  // Same contract as setprop/delprop: a condensed store is immutable.
  if (iscondensed(store)) {
    throw new Error(
      'struct: condensed structures are immutable - ' + 'expand() first, then modify the copy',
    )
  }

  const pathType = typify(path)

  const parts =
    0 < (T_list & pathType)
      ? path
      : 0 < (T_string & pathType)
        ? (path as string).split(S_DT)
        : 0 < (T_number & pathType)
          ? [path]
          : NONE

  if (NONE === parts) {
    return NONE
  }

  const base = getprop(injdef, S_base)
  const numparts = size(parts)
  let parent = getprop(store, base, store)

  for (let pI = 0; pI < numparts - 1; pI++) {
    const partKey = getelem(parts, pI)
    let nextParent = getprop(parent, partKey)
    if (!isnode(nextParent)) {
      nextParent = 0 < (T_number & typify(getelem(parts, pI + 1))) ? [] : {}
      setprop(parent, partKey, nextParent)
    }
    parent = nextParent
  }

  if (DELETE === val) {
    delprop(parent, getelem(parts, -1))
  } else {
    setprop(parent, getelem(parts, -1), val)
  }

  return parent
}

function getpath(store: any, path: number | string | string[], injdef?: Partial<Injection>) {
  const parts = islist(path)
    ? path
    : 'string' === typeof path
      ? path.split(S_DT)
      : 'number' === typeof path
        ? [strkey(path)]
        : NONE

  if (NONE === parts) {
    return NONE
  }

  // TRANSPARENT CONDENSED READ. A condensed store answers the same path with
  // the same value as the ordinary node it was built from - the caller does
  // not need to know which it holds. Only the nodes ON the path are touched,
  // so this never materialises the whole structure.
  if (iscondensed(store)) {
    // The fast path applies only when there are no injection options to
    // honour. base/dparent/dpath/meta change what the walk below resolves
    // against, and silently ignoring them would make a condensed store
    // answer differently from the node it was built from - the opposite of
    // the transparent-read contract. Rare enough to be worth materialising.
    if (null == injdef || null == getprop(injdef, S_base)) {
      const found = condenseResolve(store, (store as any)[S_condroot], parts)
      const val = 0 > found ? undefined : condenseMaterialise(store, found)
      // Group A null-as-absent: an ordinary getpath observes a stored null
      // through getprop and reports it as absent, so this must too.
      return null == val ? undefined : val
    }
    store = expand(store)
  }

  let val = store
  const base = getprop(injdef, S_base)
  const src = getprop(store, base, store)
  const numparts = size(parts)
  const dparent = getprop(injdef, 'dparent')

  // An empty path (incl empty string) just finds the store.
  if (null == path || null == store || (1 === numparts && S_MT === parts[0])) {
    val = src
  } else if (0 < numparts) {
    if (1 === numparts) {
      val = getprop(store, parts[0])
    }

    if (!isfunc(val)) {
      val = src

      const m = re_find(R_META_PATH, parts[0])
      if (m && injdef && injdef.meta) {
        val = getprop(injdef.meta, m[1])
        parts[0] = m[3]
      }

      const dpath = getprop(injdef, 'dpath')

      for (let pI = 0; NONE !== val && pI < numparts; pI++) {
        let part = parts[pI]

        if (injdef && S_DKEY === part) {
          part = getprop(injdef, S_key)
        } else if (injdef && part.startsWith('$GET:')) {
          // $GET:path$ -> get store value, use as path part (string)
          part = stringify(getpath(src, slice(part, 5, -1)))
        } else if (injdef && part.startsWith('$REF:')) {
          // $REF:refpath$ -> get spec value, use as path part (string)
          part = stringify(getpath(getprop(store, S_DSPEC), slice(part, 5, -1)))
        } else if (injdef && part.startsWith('$META:')) {
          // $META:metapath$ -> get meta value, use as path part (string)
          part = stringify(getpath(getprop(injdef, 'meta'), slice(part, 6, -1)))
        }

        // $$ escapes $ (skip the regex for the common no-`$$` segment).
        if (-1 !== part.indexOf('$$')) {
          part = re_replace(R_DOUBLE_DOLLAR, part, '$')
        }

        if (S_MT === part) {
          let ascends = 0
          while (S_MT === parts[1 + pI]) {
            ascends++
            pI++
          }

          if (injdef && 0 < ascends) {
            if (pI === parts.length - 1) {
              ascends--
            }

            if (0 === ascends) {
              val = dparent
            } else {
              const fullpath = flatten([slice(dpath, 0 - ascends), parts.slice(pI + 1)])

              if (ascends <= size(dpath)) {
                val = getpath(store, fullpath)
              } else {
                val = NONE
              }

              break
            }
          } else {
            val = dparent
          }
        } else {
          val = getprop(val, part)
        }
      }
    }
  }

  // Inj may provide a custom handler to modify found value.
  const handler = getprop(injdef, 'handler')
  if (null != injdef && isfunc(handler)) {
    const ref = pathify(path)
    val = handler(injdef, val, ref, store)
  }

  return val
}

function inject(val: any, store: any, injdef?: Partial<Injection>) {
  const valtype = typeof val
  let inj: Injection = injdef as Injection

  // Create state if at root of injection.  The input value is placed
  // inside a virtual parent holder to simplify edge cases.
  if (NONE === injdef || null == injdef.mode) {
    inj = new Injection(val, { [S_DTOP]: val })
    inj.dparent = store
    inj.errs = getprop(store, S_DERRS, [])
    inj.meta.__d = 0

    if (NONE !== injdef) {
      inj.modify = null == injdef.modify ? inj.modify : injdef.modify
      inj.extra = null == injdef.extra ? inj.extra : injdef.extra
      inj.meta = null == injdef.meta ? inj.meta : injdef.meta
      inj.handler = null == injdef.handler ? inj.handler : injdef.handler
    }
  }

  inj.descend()

  // console.log('INJ-START', val, inj.mode, inj.key, inj.val,
  //  't=', inj.path, 'P=', inj.parent, 'dp=', inj.dparent, 'ST=', store.$TOP)

  if (isnode(val)) {
    let nodekeys: any[]
    nodekeys = keysof(val)

    if (ismap(val)) {
      nodekeys = flatten([
        filter(nodekeys, (n) => !n[1].includes(S_DS)),
        filter(nodekeys, (n) => n[1].includes(S_DS)),
      ])
    } else {
      nodekeys = keysof(val)
    }

    for (let nkI = 0; nkI < nodekeys.length; nkI++) {
      const childinj = inj.child(nkI, nodekeys)
      const nodekey = childinj.key
      childinj.mode = M_KEYPRE

      // Peform the key:pre mode injection on the child key.
      const prekey = _injectstr(nodekey, store, childinj)

      // The injection may modify child processing.
      nkI = childinj.keyI
      nodekeys = childinj.keys

      // Prevent further processing by returning an undefined prekey
      if (NONE !== prekey) {
        childinj.val = getprop(val, prekey)
        childinj.mode = M_VAL

        // Perform the val mode injection on the child value.
        // NOTE: return value is not used.
        inject(childinj.val, store, childinj)

        // The injection may modify child processing.
        nkI = childinj.keyI
        nodekeys = childinj.keys

        // Peform the key:post mode injection on the child key.
        childinj.mode = M_KEYPOST
        _injectstr(nodekey, store, childinj)

        // The injection may modify child processing.
        nkI = childinj.keyI
        nodekeys = childinj.keys
      }
    }
  } else if (S_string === valtype) {
    inj.mode = M_VAL
    val = _injectstr(val, store, inj)
    if (SKIP !== val) {
      inj.setval(val)
    }
  }

  if (inj.modify && SKIP !== val) {
    const mkey = inj.key
    const mparent = inj.parent
    const mval = getprop(mparent, mkey)

    inj.modify(mval, mkey, mparent, inj, store)
  }

  inj.val = val

  return _lookup(inj.parent, S_DTOP)
}

// The transform_* functions are special command inject handlers (see Injector).

const transform_DELETE: Injector = (inj: Injection) => {
  inj.setval(NONE)
  return NONE
}

const transform_COPY: Injector = (inj: Injection, _val: any) => {
  const ijname = 'COPY'

  if (!checkPlacement(M_VAL, ijname, T_any, inj)) {
    return NONE
  }

  const out = _lookup(inj.dparent, inj.key)
  inj.setval(out)

  return out
}

// As a value, inject the key of the parent node.
// As a key, defined the name of the key property in the source object.
const transform_KEY: Injector = (inj: Injection) => {
  const { mode, path, parent } = inj

  // Do nothing in val mode - not an error.
  if (M_VAL !== mode) {
    return NONE
  }

  // Key is defined by $KEY meta property.
  const keyspec = _lookup(parent, S_BKEY)
  if (NONE !== keyspec) {
    delprop(parent, S_BKEY)
    return getprop(inj.dparent, keyspec)
  }

  return _lookup(_lookup(parent, S_BANNO), S_KEY) ?? getelem(path, -2)
}

// Annotate node.  Does nothing itself, just used by
// other injectors, and is removed when called.
const transform_ANNO: Injector = (inj: Injection) => {
  const { parent } = inj
  delprop(parent, S_BANNO)
  return NONE
}

// Merge a list of objects into the current object.
// Must be a key in an object. The value is merged over the current object.
// If the value is an array, the elements are first merged using `merge`.
// If the value is the empty string, merge the top level store.
// Format: { '`$MERGE`': '`source-path`' | ['`source-paths`', ...] }
const transform_MERGE: Injector = (inj: Injection) => {
  const { mode, key, parent } = inj

  // Ensures $MERGE is removed from parent list (val mode).
  let out: any = NONE

  if (M_KEYPRE === mode) {
    out = key
  }

  // Operate after child values have been transformed.
  else if (M_KEYPOST === mode) {
    out = key

    let args = getprop(parent, key)
    args = Array.isArray(args) ? args : [args]

    // Remove the $MERGE command from a parent map.
    inj.setval(NONE)

    const mergelist = flatten([[parent], args, [clone(parent)]])

    merge(mergelist)
  }

  return out
}

// Convert a node to a list.
// Format: ['`$EACH`', '`source-path-of-node`', child-template]
const transform_EACH: Injector = (inj: Injection, _val: any, _ref: string, store: any) => {
  const ijname = 'EACH'

  if (!checkPlacement(M_VAL, ijname, T_list, inj)) {
    return NONE
  }

  // Remove remaining keys to avoid spurious processing.
  slice(inj.keys, 0, 1, true)

  const [err, srcpath, child] = injectorArgs([T_string, T_any], slice(inj.parent, 1))
  if (NONE !== err) {
    inj.errs.push('$' + ijname + ': ' + err)
    return NONE
  }

  const srcstore = getprop(store, inj.base, store)

  const src = getpath(srcstore, srcpath, inj)
  const srctype = typify(src)

  // Create parallel data structures:
  // source entries :: child templates
  let tcur: any = []
  let tval: any = []

  const tkey = getelem(inj.path, -2)
  const target = getelem(inj.nodes, -2, () => getelem(inj.nodes, -1))

  // Create clones of the child template for each value of the current soruce.
  if (0 < (T_list & srctype)) {
    tval = items(src, () => clone(child))
  } else if (0 < (T_map & srctype)) {
    tval = items(src, (n) =>
      merge(
        [
          clone(child),
          // Make a note of the key for $KEY transforms.
          { [S_BANNO]: { KEY: n[0] } },
        ],
        1,
      ),
    )
  }

  let rval = []

  if (0 < size(tval)) {
    tcur = null == src ? NONE : items(src, (n: [string, any]) => n[1])

    const ckey = getelem(inj.path, -2)

    const tpath = slice(inj.path, -1)
    const dpath = flatten([S_DTOP, srcpath.split(S_DT), '$:' + ckey])

    tcur = { [ckey]: tcur }

    if (1 < size(tpath)) {
      const pkey = getelem(inj.path, -3, S_DTOP)
      tcur = { [pkey]: tcur }
      dpath.push('$:' + pkey)
    }

    const tinj = inj.child(0, [ckey])
    tinj.path = tpath
    tinj.nodes = slice(inj.nodes, -1)

    tinj.parent = getelem(tinj.nodes, -1)
    setprop(tinj.parent, ckey, tval)

    tinj.val = tval
    tinj.dpath = dpath
    tinj.dparent = tcur

    inject(tval, store, tinj)
    rval = tinj.val
  }

  setprop(target, tkey, rval)

  return rval[0]
}

// Convert a node to a map.
// Format: { '`$PACK`':['source-path', child-template]}
const transform_PACK: Injector = (inj: Injection, _val: any, _ref: string, store: any) => {
  const { key, path, parent, nodes } = inj

  const ijname = 'EACH'

  if (!checkPlacement(M_KEYPRE, ijname, T_map, inj)) {
    return NONE
  }

  const args = getprop(parent, key)
  const [err, srcpath, origchildspec] = injectorArgs([T_string, T_any], args)
  if (NONE !== err) {
    inj.errs.push('$' + ijname + ': ' + err)
    return NONE
  }

  const tkey = getelem(path, -2)
  const pathsize = size(path)
  const target = getelem(nodes, pathsize - 2, () => getelem(nodes, pathsize - 1))

  const srcstore = getprop(store, inj.base, store)
  let src = getpath(srcstore, srcpath, inj)

  if (!islist(src)) {
    if (ismap(src)) {
      src = items(src, (item: [string, any]) => {
        setprop(item[1], S_BANNO, { KEY: item[0] })
        return item[1]
      })
    } else {
      src = NONE
    }
  }

  if (null == src) {
    return NONE
  }

  const keypath = getprop(origchildspec, S_BKEY)
  const childspec = delprop(origchildspec, S_BKEY)

  const child = getprop(childspec, S_BVAL, childspec)

  const tval: any = {}

  items(src, (item: [string, any]) => {
    const srckey = item[0]
    const srcnode = item[1]

    let key: string = srckey
    if (NONE !== keypath) {
      if (keypath.startsWith('`')) {
        key = inject(keypath, merge([{}, store, { $TOP: srcnode }], 1))
      } else {
        key = getpath(srcnode, keypath, inj)
      }
    }

    const tchild = clone(child)
    setprop(tval, key, tchild)

    const anno = getprop(srcnode, S_BANNO)
    if (NONE === anno) {
      delprop(tchild, S_BANNO)
    } else {
      setprop(tchild, S_BANNO, anno)
    }
  })

  let rval = {}

  if (!isempty(tval)) {
    const tsrc: any = {}
    src.reduce((a: any, n: any, i: any) => {
      const kn =
        null == keypath
          ? i
          : keypath.startsWith('`')
            ? inject(keypath, merge([{}, store, { $TOP: n }], 1))
            : getpath(n, keypath, inj)

      setprop(a, kn, n)
      return a
    }, tsrc)

    const tpath = slice(inj.path, -1)

    const ckey = getelem(inj.path, -2)
    const dpath = flatten([S_DTOP, srcpath.split(S_DT), '$:' + ckey])

    let tcur = { [ckey]: tsrc }

    if (1 < size(tpath)) {
      const pkey = getelem(inj.path, -3, S_DTOP)
      tcur = { [pkey]: tcur }
      dpath.push('$:' + pkey)
    }

    const tinj = inj.child(0, [ckey])
    tinj.path = tpath
    tinj.nodes = slice(inj.nodes, -1)

    tinj.parent = getelem(tinj.nodes, -1)
    tinj.val = tval

    tinj.dpath = dpath
    tinj.dparent = tcur

    inject(tval, store, tinj)
    rval = tinj.val
  }

  setprop(target, tkey, rval)

  return NONE
}

const transform_REF: Injector = (inj: Injection, val: any, _ref: string, store: any) => {
  const { nodes } = inj

  if (M_VAL !== inj.mode) {
    return NONE
  }

  // Get arguments: ['`$REF`', 'ref-path'].
  const refpath = _lookup(inj.parent, 1)
  inj.keyI = size(inj.keys)

  const spec = getprop(store, S_DSPEC)()

  const dpath = slice(inj.path, 1)
  const ref = getpath(spec, refpath, {
    dpath,
    // dparent: getpath(spec, inj.path.slice(1))
    dparent: getpath(spec, dpath),
  })

  let hasSubRef = false
  if (isnode(ref)) {
    walk(ref, (_k: any, v: any) => {
      if ('`$REF`' === v) {
        hasSubRef = true
      }
      return v
    })
  }

  const tref = clone(ref)

  const cpath = slice(inj.path, -3)
  const tpath = slice(inj.path, -1)
  const tcur = getpath(store, cpath)
  const tval = getpath(store, tpath)
  let rval = NONE

  if (!hasSubRef || NONE !== tval) {
    const tinj = inj.child(0, [getelem(tpath, -1)])

    tinj.path = tpath
    tinj.nodes = slice(inj.nodes, -1)
    tinj.parent = getelem(nodes, -2)
    tinj.val = tref

    tinj.dpath = flatten([cpath])
    tinj.dparent = tcur

    inject(tref, store, tinj)

    rval = tinj.val
  } else {
    rval = NONE
  }

  const grandparent = inj.setval(rval, 2)

  if (islist(grandparent) && inj.prior) {
    inj.prior.keyI--
  }

  return val
}

const transform_FORMAT: Injector = (inj: Injection, _val: any, _ref: string, store: any) => {
  // Remove remaining keys to avoid spurious processing.
  slice(inj.keys, 0, 1, true)

  if (M_VAL !== inj.mode) {
    return NONE
  }

  const name = _lookup(inj.parent, 1)
  const child = _lookup(inj.parent, 2)

  const tkey = getelem(inj.path, -2)
  const target = getelem(inj.nodes, -2, () => getelem(inj.nodes, -1))

  const cinj = injectChild(child, store, inj)
  const resolved = cinj.val

  const formatter = 0 < (T_function & typify(name)) ? name : getprop(FORMATTER, name)

  if (NONE === formatter) {
    inj.errs.push('$FORMAT: unknown format: ' + name + '.')
    return NONE
  }

  const out = walk(resolved, formatter)

  setprop(target, tkey, out)

  return out
}

const FORMATTER: Record<string, WalkApply> = {
  identity: (_k: any, v: any) => v,
  upper: (_k: any, v: any) => (isnode(v) ? v : ('' + v).toUpperCase()),
  lower: (_k: any, v: any) => (isnode(v) ? v : ('' + v).toLowerCase()),
  string: (_k: any, v: any) => (isnode(v) ? v : '' + v),
  number: (_k: any, v: any) => {
    if (isnode(v)) {
      return v
    } else {
      let n = Number(v)
      if (isNaN(n)) {
        n = 0
      }
      return n
    }
  },
  integer: (_k: any, v: any) => {
    if (isnode(v)) {
      return v
    } else {
      let n = Number(v)
      if (isNaN(n)) {
        n = 0
      }
      return n | 0
    }
  },
  concat: (k: any, v: any) =>
    null == k && islist(v)
      ? join(
          items(v, (n) => (isnode(n[1]) ? S_MT : S_MT + n[1])),
          S_MT,
        )
      : v,
}

const transform_APPLY: Injector = (inj: Injection, _val: any, _ref: string, store: any) => {
  const ijname = 'APPLY'

  if (!checkPlacement(M_VAL, ijname, T_list, inj)) {
    return NONE
  }

  const [err, apply, child] = injectorArgs([T_function, T_any], slice(inj.parent, 1))
  if (NONE !== err) {
    inj.errs.push('$' + ijname + ': ' + err)
    return NONE
  }

  const tkey = getelem(inj.path, -2)
  const target = getelem(inj.nodes, -2, () => getelem(inj.nodes, -1))

  const cinj = injectChild(child, store, inj)
  const resolved = cinj.val

  const out = apply(resolved, store, cinj)

  setprop(target, tkey, out)

  return out
}

// Transform data using spec.
// Only operates on static JSON-like data.
// Arrays are treated as if they are objects with indices as keys.
function transform(
  data: any, // Source data to transform into new data (original not mutated)
  spec: any, // Transform specification; output follows this shape
  injdef?: Partial<Injection>,
) {
  // Clone the spec so that the clone can be modified in place as the transform result.
  const origspec = spec
  spec = clone(origspec)

  const extra = injdef?.extra

  const collect = null != injdef?.errs
  const errs = injdef?.errs || []

  const extraTransforms: any = {}
  const extraData =
    null == extra
      ? NONE
      : items(extra).reduce(
          (a: any, n: any[]) => (
            n[0].startsWith(S_DS) ? (extraTransforms[n[0]] = n[1]) : (a[n[0]] = n[1]),
            a
          ),
          {},
        )

  const dataClone = merge([isempty(extraData) ? NONE : clone(extraData), clone(data)])

  // Define a top level store that provides transform operations.
  const store = merge(
    [
      {
        // The inject function recognises this special location for the root of the source data.
        // NOTE: to escape data that contains "`$FOO`" keys at the top level,
        // place that data inside a holding map: { myholder: mydata }.
        $TOP: dataClone,

        $SPEC: () => origspec,

        // Escape backtick (this also works inside backticks).
        $BT: () => S_BT,

        // Escape dollar sign (this also works inside backticks).
        $DS: () => S_DS,

        // Insert current date and time as an ISO string.
        $WHEN: () => new Date().toISOString(),

        $DELETE: transform_DELETE,
        $COPY: transform_COPY,
        $KEY: transform_KEY,
        $ANNO: transform_ANNO,
        $MERGE: transform_MERGE,
        $EACH: transform_EACH,
        $PACK: transform_PACK,
        $REF: transform_REF,
        $FORMAT: transform_FORMAT,
        $APPLY: transform_APPLY,
      },

      extraTransforms,

      {
        $ERRS: errs,
      },
    ],
    1,
  )

  const out = inject(spec, store, injdef)

  const generr = 0 < size(errs) && !collect
  if (generr) {
    throw new Error(join(errs, ' | '))
  }

  return out
}

// A required string value. NOTE: Rejects empty strings.
const validate_STRING: Injector = (inj: Injection) => {
  const out = _lookup(inj.dparent, inj.key)

  const t = typify(out)
  if (0 === (T_string & t)) {
    const msg = _invalidTypeMsg(inj.path, S_string, t, out, 'V1010')
    inj.errs.push(msg)
    return NONE
  }

  if (S_MT === out) {
    const msg = 'Empty string at ' + pathify(inj.path, 1)
    inj.errs.push(msg)
    return NONE
  }

  return out
}

const validate_TYPE: Injector = (inj: Injection, _val: any, ref: string) => {
  const tname = slice(ref, 1).toLowerCase()
  const typev = 1 << (31 - TYPENAME.indexOf(tname))
  const out = _lookup(inj.dparent, inj.key)

  const t = typify(out)

  // console.log('TYPE', tname, typev, tn(typev), 'O=', t, tn(t), out, 'C=', t & typev)

  if (0 === (t & typev)) {
    inj.errs.push(_invalidTypeMsg(inj.path, tname, t, out, 'V1001'))
    return NONE
  }

  return out
}

const validate_ANY: Injector = (inj: Injection) => {
  const out = _lookup(inj.dparent, inj.key)
  return out
}

// Specify child values for map or list.
// Map syntax: {'`$CHILD`': child-template }
// List syntax: ['`$CHILD`', child-template ]
const validate_CHILD: Injector = (inj: Injection) => {
  const { mode, key, parent, keys, path } = inj

  // Setup data structures for validation by cloning child template.

  if (M_KEYPRE === mode) {
    const childtm = getprop(parent, key)

    const pkey = getelem(path, -2)
    let tval = getprop(inj.dparent, pkey)

    if (NONE == tval) {
      tval = {}
    } else if (!ismap(tval)) {
      inj.errs.push(_invalidTypeMsg(slice(inj.path, -1), S_object, typify(tval), tval), 'V0220')
      return NONE
    }

    const ckeys = keysof(tval)
    for (const ckey of ckeys) {
      setprop(parent, ckey, clone(childtm))

      // NOTE: modifying inj! This extends the child value loop in inject.
      keys.push(ckey)
    }

    inj.setval(NONE)
    return NONE
  }

  if (M_VAL === mode) {
    if (!islist(parent)) {
      inj.errs.push('Invalid $CHILD as value')
      return NONE
    }

    const childtm = _lookup(parent, 1)

    if (NONE === inj.dparent) {
      slice(parent, 0, 0, true)
      return NONE
    }

    if (!islist(inj.dparent)) {
      const msg = _invalidTypeMsg(
        slice(inj.path, -1),
        S_list,
        typify(inj.dparent),
        inj.dparent,
        'V0230',
      )
      inj.errs.push(msg)
      inj.keyI = size(parent)
      return inj.dparent
    }

    // Clone children and reset inj key index.
    // The inject child loop will now iterate over the cloned children,
    // validating them against the current list values.
    items(inj.dparent, (n) => setprop(parent, n[0], clone(childtm)))
    slice(parent, 0, inj.dparent.length, true)

    // NOTE: modifying inj! This extends the child value loop in inject
    // to cover every cloned child.
    for (let ckeyI = size(keys); ckeyI < size(parent); ckeyI++) {
      keys.push(strkey(ckeyI))
    }

    // Restart the child value loop at the first element (the loop
    // increments keyI on resume) so that the first element is also
    // validated against the child template.
    inj.keyI = -1

    // SKIP leaves the cloned child template in place at the first
    // element so the resumed loop can validate it.
    return SKIP
  }

  return NONE
}

const validate_ONE: Injector = (inj: Injection, _val: any, _ref: string, store: any) => {
  const { mode, parent, keyI } = inj

  // Only operate in val mode, since parent is a list.
  if (M_VAL === mode) {
    if (!islist(parent) || 0 !== keyI) {
      inj.errs.push(
        'The $ONE validator at field ' +
          pathify(inj.path, 1, 1) +
          ' must be the first element of an array.',
      )
      return
    }

    inj.keyI = size(inj.keys)

    // Clean up structure, replacing [$ONE, ...] with current
    inj.setval(inj.dparent, 2)

    // Path shortens for the message only: `modify` reads
    // getprop(inj.parent, inj.key), and inj.parent is still this list.
    inj.path = slice(inj.path, -1)

    const tvals = slice(parent, 1)
    if (0 === size(tvals)) {
      inj.errs.push(
        'The $ONE validator at field ' +
          pathify(inj.path, 1, 1) +
          ' must have at least one argument.',
      )
      return
    }

    for (const tval of tvals) {
      const terrs: any[] = []

      const vstore = merge([{}, store], 1)
      vstore.$TOP = inj.dparent

      const vcurrent = validate(inj.dparent, tval, {
        extra: vstore,
        errs: terrs,
        meta: inj.meta,
      })

      inj.setval(vcurrent, -2)

      // Accept current value if there was a match
      if (0 === size(terrs)) {
        return
      }
    }

    const valdesc = replace(
      join(
        items(tvals, (n) => stringify(n[1])),
        ', ',
      ),
      R_TRANSFORM_NAME,
      (_m: any, p1: string) => p1.toLowerCase(),
    )

    inj.errs.push(
      _invalidTypeMsg(
        inj.path,
        (1 < size(tvals) ? 'one of ' : '') + valdesc,
        typify(inj.dparent),
        inj.dparent,
        'V0210',
      ),
    )
  }
}

const validate_EXACT: Injector = (inj: Injection) => {
  const { mode, parent, key, keyI } = inj

  // Only operate in val mode, since parent is a list.
  if (M_VAL === mode) {
    if (!islist(parent) || 0 !== keyI) {
      inj.errs.push(
        'The $EXACT validator at field ' +
          pathify(inj.path, 1, 1) +
          ' must be the first element of an array.',
      )
      return
    }

    inj.keyI = size(inj.keys)

    // Clean up structure, replacing [$EXACT, ...] with current data parent
    inj.setval(inj.dparent, 2)

    inj.path = slice(inj.path, 0, -1)
    inj.key = getelem(inj.path, -1)

    const tvals = slice(parent, 1)
    if (0 === size(tvals)) {
      inj.errs.push(
        'The $EXACT validator at field ' +
          pathify(inj.path, 1, 1) +
          ' must have at least one argument.',
      )
      return
    }

    let currentstr: string | undefined = undefined
    for (const tval of tvals) {
      let exactmatch = tval === inj.dparent

      if (!exactmatch && isnode(tval)) {
        currentstr = undefined === currentstr ? stringify(inj.dparent) : currentstr
        const tvalstr = stringify(tval)
        exactmatch = tvalstr === currentstr
      }

      if (exactmatch) {
        return
      }
    }

    const valdesc = replace(
      join(
        items(tvals, (n) => stringify(n[1])),
        ', ',
      ),
      R_TRANSFORM_NAME,
      (_m: any, p1: string) => p1.toLowerCase(),
    )

    inj.errs.push(
      _invalidTypeMsg(
        inj.path,
        (1 < size(inj.path) ? '' : 'value ') +
          'exactly equal to ' +
          (1 === size(tvals) ? '' : 'one of ') +
          valdesc,
        typify(inj.dparent),
        inj.dparent,
        'V0110',
      ),
    )
  } else {
    delprop(parent, key)
  }
}

// This is the "modify" argument to inject. Use this to perform
// generic validation. Runs *after* any special commands.
const _validation: Modify = (pval: any, key?: any, parent?: any, inj?: Injection) => {
  if (NONE === inj) {
    return
  }

  if (SKIP === pval) {
    return
  }

  const exact = getprop(inj.meta, S_BEXACT, false)

  const cval = getprop(inj.dparent, key)

  if (NONE === inj || (!exact && NONE === cval)) {
    return
  }

  const ptype = typify(pval)

  // Delete any special commands remaining.
  if (0 < (T_string & ptype) && pval.includes(S_DS)) {
    return
  }

  const ctype = typify(cval)

  if (ptype !== ctype && NONE !== pval) {
    inj.errs.push(_invalidTypeMsg(inj.path, typename(ptype), ctype, cval, 'V0010'))
    return
  }

  if (ismap(cval)) {
    if (!ismap(pval)) {
      inj.errs.push(_invalidTypeMsg(inj.path, typename(ptype), ctype, cval, 'V0020'))
      return
    }

    const ckeys = keysof(cval)
    const pkeys = keysof(pval)

    // Empty spec object {} means object can be open (any keys).
    if (0 < size(pkeys) && true !== getprop(pval, '`$OPEN`')) {
      const badkeys = []
      for (const ckey of ckeys) {
        // Literal presence: _validation needs to know if the SHAPE declares
        // this key, regardless of whether the validator stored null in that
        // slot. The Group A haskey would miss null-valued slots.
        if (NONE === _lookup(pval, ckey)) {
          badkeys.push(ckey)
        }
      }

      // Closed object, so reject extra keys not in shape.
      if (0 < size(badkeys)) {
        const msg = 'Unexpected keys at field ' + pathify(inj.path, 1) + S_VIZ + join(badkeys, ', ')
        inj.errs.push(msg)
      }
    } else {
      // Object is open, so merge in extra keys.
      merge([pval, cval])
      if (isnode(pval)) {
        delprop(pval, '`$OPEN`')
      }
    }
  } else if (islist(cval)) {
    if (!islist(pval)) {
      inj.errs.push(_invalidTypeMsg(inj.path, typename(ptype), ctype, cval, 'V0030'))
    }
  } else if (exact) {
    if (cval !== pval) {
      const pathmsg = 1 < size(inj.path) ? 'at field ' + pathify(inj.path, 1) + S_VIZ : S_MT
      inj.errs.push('Value ' + pathmsg + cval + ' should equal ' + pval + S_DT)
    }
  } else {
    // Spec value was a default, copy over data
    setprop(parent, key, cval)
  }

  return
}

function validate(
  data: any, // Source data to transform into new data (original not mutated)
  spec: any, // Transform specification; output follows this shape
  injdef?: Partial<Injection>,
) {
  const extra = injdef?.extra

  const collect = null != injdef?.errs
  const errs = injdef?.errs || []

  const store = merge(
    [
      {
        $DELETE: null,
        $COPY: null,
        $KEY: null,
        $META: null,
        $MERGE: null,
        $EACH: null,
        $PACK: null,

        $STRING: validate_STRING,
        $NUMBER: validate_TYPE,
        $INTEGER: validate_TYPE,
        $DECIMAL: validate_TYPE,
        $BOOLEAN: validate_TYPE,
        $NULL: validate_TYPE,
        $NIL: validate_TYPE,
        $MAP: validate_TYPE,
        $LIST: validate_TYPE,
        $FUNCTION: validate_TYPE,
        $INSTANCE: validate_TYPE,
        $ANY: validate_ANY,
        $CHILD: validate_CHILD,
        $ONE: validate_ONE,
        $EXACT: validate_EXACT,
      },

      getdef(extra, {}),

      // A special top level value to collect errors.
      // NOTE: collecterrs parameter always wins.
      {
        $ERRS: errs,
      },
    ],
    1,
  )

  const meta = getprop(injdef, 'meta', {})
  setprop(meta, S_BEXACT, getprop(meta, S_BEXACT, false))

  const out = transform(data, spec, {
    meta,
    extra: store,
    modify: _validation,
    handler: _validatehandler,
    errs,
  })

  const generr = 0 < size(errs) && !collect
  if (generr) {
    throw new Error(join(errs, ' | '))
  }

  return out
}

const select_AND: Injector = (inj: Injection, _val: any, _ref: string, store: any) => {
  if (M_KEYPRE === inj.mode) {
    const terms = _lookup(inj.parent, inj.key)

    const ppath = slice(inj.path, -1)
    const point = getpath(store, ppath)

    const vstore = merge([{}, store], 1)
    vstore.$TOP = point

    for (const term of terms) {
      const terrs: any[] = []

      validate(point, term, {
        extra: vstore,
        errs: terrs,
        meta: inj.meta,
      })

      if (0 != size(terrs)) {
        inj.errs.push(
          'AND:' + pathify(ppath) + S_VIZ + stringify(point) + ' fail:' + stringify(terms),
        )
      }
    }

    const gkey = getelem(inj.path, -2)
    const gp = getelem(inj.nodes, -2)
    setprop(gp, gkey, point)
  }
}

const select_OR: Injector = (inj: Injection, _val: any, _ref: string, store: any) => {
  if (M_KEYPRE === inj.mode) {
    const terms = _lookup(inj.parent, inj.key)

    const ppath = slice(inj.path, -1)
    const point = getpath(store, ppath)

    const vstore = merge([{}, store], 1)
    vstore.$TOP = point

    for (const term of terms) {
      const terrs: any[] = []

      validate(point, term, {
        extra: vstore,
        errs: terrs,
        meta: inj.meta,
      })

      if (0 === size(terrs)) {
        const gkey = getelem(inj.path, -2)
        const gp = getelem(inj.nodes, -2)
        setprop(gp, gkey, point)

        return
      }
    }

    inj.errs.push('OR:' + pathify(ppath) + S_VIZ + stringify(point) + ' fail:' + stringify(terms))
  }
}

const select_NOT: Injector = (inj: Injection, _val: any, _ref: string, store: any) => {
  if (M_KEYPRE === inj.mode) {
    const term = _lookup(inj.parent, inj.key)

    const ppath = slice(inj.path, -1)
    const point = getpath(store, ppath)

    const vstore = merge([{}, store], 1)
    vstore.$TOP = point

    const terrs: any[] = []

    validate(point, term, {
      extra: vstore,
      errs: terrs,
      meta: inj.meta,
    })

    if (0 == size(terrs)) {
      inj.errs.push('NOT:' + pathify(ppath) + S_VIZ + stringify(point) + ' fail:' + stringify(term))
    }

    const gkey = getelem(inj.path, -2)
    const gp = getelem(inj.nodes, -2)
    setprop(gp, gkey, point)
  }
}

const select_CMP: Injector = (inj: Injection, _val: any, ref: string, store: any) => {
  if (M_KEYPRE === inj.mode) {
    const term = _lookup(inj.parent, inj.key)
    const gkey = getelem(inj.path, -2)

    const ppath = slice(inj.path, -1)
    const point = getpath(store, ppath)

    let pass = false

    if ('$GT' === ref && point > term) {
      pass = true
    } else if ('$LT' === ref && point < term) {
      pass = true
    } else if ('$GTE' === ref && point >= term) {
      pass = true
    } else if ('$LTE' === ref && point <= term) {
      pass = true
    } else if ('$LIKE' === ref && re_test(re_compile(term), stringify(point))) {
      pass = true
    }

    if (pass) {
      // Update spec to match found value so that _validate does not complain.
      const gp = getelem(inj.nodes, -2)
      setprop(gp, gkey, point)
    } else {
      inj.errs.push(
        'CMP: ' +
          pathify(ppath) +
          S_VIZ +
          stringify(point) +
          ' fail:' +
          ref +
          ' ' +
          stringify(term),
      )
    }
  }

  return NONE
}

function select(children: any, query: any): any[] {
  if (!isnode(children)) {
    return []
  }

  if (ismap(children)) {
    children = items(children, (n) => {
      setprop(n[1], S_DKEY, n[0])
      return n[1]
    })
  } else {
    children = items(children, (n) => (setprop(n[1], S_DKEY, +n[0]), n[1]))
  }

  const results: any[] = []
  const injdef = {
    errs: [],
    meta: { [S_BEXACT]: true },
    extra: {
      $AND: select_AND,
      $OR: select_OR,
      $NOT: select_NOT,
      $GT: select_CMP,
      $LT: select_CMP,
      $GTE: select_CMP,
      $LTE: select_CMP,
      $LIKE: select_CMP,
    },
  }

  const q = clone(query)

  walk(q, (_k: PropKey | undefined, v: any) => {
    if (ismap(v)) {
      setprop(v, '`$OPEN`', getprop(v, '`$OPEN`', true))
    }
    return v
  })

  for (const child of children) {
    injdef.errs = []

    validate(child, clone(q), injdef)

    if (0 === size(injdef.errs)) {
      results.push(child)
    }
  }

  return results
}

// Injection state used for recursive injection into JSON - like data structures.
class Injection {
  mode: InjectMode // Injection mode: M_KEYPRE, M_VAL, M_KEYPOST.
  full: boolean // Transform escape was full key name.
  keyI: number // Index of parent key in list of parent keys.
  keys: string[]
  key: string
  val: any
  parent: any // Current parent (in transform specification).
  path: string[]
  nodes: any[]
  handler: Injector
  errs: any[]
  meta: Record<string, any> // Custom meta data. NOTE: do not merge, values must remain as-is.
  dparent: any // Current data parent node (contains current data value).
  dpath: string[]
  base?: string // Base key for data in store, if any.
  modify?: Modify
  prior?: Injection
  extra?: any

  constructor(val: any, parent: any) {
    this.val = val
    this.parent = parent
    this.errs = []

    this.dparent = NONE
    this.dpath = [S_DTOP]

    this.mode = M_VAL
    this.full = false
    this.keyI = 0
    this.keys = [S_DTOP]
    this.key = S_DTOP
    this.path = [S_DTOP]
    this.nodes = [parent]
    this.handler = _injecthandler
    this.base = S_DTOP
    this.meta = {}
  }

  toString(prefix?: string) {
    return (
      'INJ' +
      (null == prefix ? '' : S_FS + prefix) +
      S_CN +
      pad(pathify(this.path, 1)) +
      MODENAME[this.mode] +
      (this.full ? '/full' : '') +
      S_CN +
      'key=' +
      this.keyI +
      S_FS +
      this.key +
      S_FS +
      S_OS +
      this.keys +
      S_CS +
      '  p=' +
      stringify(this.parent, -1, 1) +
      '  m=' +
      stringify(this.meta, -1, 1) +
      '  d/' +
      pathify(this.dpath, 1) +
      '=' +
      stringify(this.dparent, -1, 1) +
      '  r=' +
      stringify(this.nodes[0]?.[S_DTOP], -1, 1)
    )
  }

  descend() {
    this.meta.__d++
    const parentkey = getelem(this.path, -2)

    // Resolve current node in store for local paths.
    if (NONE === this.dparent) {
      // Even if there's no data, dpath should continue to match path, so that
      // relative paths work properly.
      if (1 < size(this.dpath)) {
        this.dpath = flatten([this.dpath, parentkey])
      }
    } else {
      // this.dparent is the containing node of the current store value.
      if (null != parentkey) {
        this.dparent = getprop(this.dparent, parentkey)

        const lastpart = getelem(this.dpath, -1)
        if (lastpart === '$:' + parentkey) {
          this.dpath = slice(this.dpath, -1)
        } else {
          this.dpath = flatten([this.dpath, parentkey])
        }
      }
    }

    return this.dparent
  }

  child(keyI: number, keys: string[]) {
    const key = strkey(keys[keyI])
    const val = this.val

    const cinj = new Injection(getprop(val, key), val)
    cinj.keyI = keyI
    cinj.keys = keys
    cinj.key = key

    cinj.path = flatten([getdef(this.path, []), key])
    cinj.nodes = flatten([getdef(this.nodes, []), [val]])

    cinj.mode = this.mode
    cinj.handler = this.handler
    cinj.modify = this.modify
    cinj.base = this.base
    cinj.meta = this.meta
    cinj.errs = this.errs
    cinj.prior = this

    cinj.dpath = flatten([this.dpath])
    cinj.dparent = this.dparent

    return cinj
  }

  setval(val: any, ancestor?: number) {
    let parent = NONE
    if (null == ancestor || ancestor < 2) {
      parent =
        NONE === val
          ? (this.parent = delprop(this.parent, this.key))
          : setprop(this.parent, this.key, val)
    } else {
      const aval = getelem(this.nodes, 0 - ancestor)
      const akey = getelem(this.path, 0 - ancestor)
      parent = NONE === val ? delprop(aval, akey) : setprop(aval, akey, val)
    }

    return parent
  }
}

// Internal utilities
// ==================

// Build a type validation error message.
function _invalidTypeMsg(path: any, needtype: string, vt: number, v: any, _whence?: string) {
  const vs = null == v ? 'no value' : stringify(v)

  return (
    'Expected ' +
    (1 < size(path) ? 'field ' + pathify(path, 1) + ' to be ' : '') +
    needtype +
    ', but found ' +
    (null != v ? typename(vt) + S_VIZ : '') +
    vs +
    // Uncomment to help debug validation errors.
    // ' [' + _whence + ']' +

    '.'
  )
}

// Default inject handler for transforms. If the path resolves to a function,
// call the function passing the injection inj. This is how transforms operate.
const _injecthandler: Injector = (inj: Injection, val: any, ref: string, store: any): any => {
  let out = val
  const iscmd = isfunc(val) && (NONE === ref || ref.startsWith(S_DS))

  if (iscmd) {
    out = (val as Injector)(inj, val, ref, store)
  }

  // Update parent with value. Ensures references remain in node tree.
  else if (M_VAL === inj.mode && inj.full) {
    inj.setval(val)
  }

  return out
}

const _validatehandler: Injector = (inj: Injection, val: any, ref: string, store: any): any => {
  let out = val

  const m = re_find(R_META_PATH, ref)
  const ismetapath = null != m

  if (ismetapath) {
    if ('=' === m[2]) {
      inj.setval([S_BEXACT, val])
    } else {
      inj.setval(val)
    }
    inj.keyI = -1

    out = SKIP
  } else {
    out = _injecthandler(inj, val, ref, store)
  }

  return out
}

function _injectstr(val: string, store: any, inj?: Injection): any {
  if (S_string !== typeof val || S_MT === val) {
    return S_MT
  }

  let out: any = val

  const m = re_find(R_INJECTION_FULL, val)

  // Full string of the val is an injection.
  if (m) {
    if (null != inj) {
      inj.full = true
    }
    let pathref = m[1]

    if (3 < size(pathref)) {
      pathref = re_replace(R_DS_ESCAPE, re_replace(R_BT_ESCAPE, pathref, S_BT), S_DS)
    }

    out = getpath(store, pathref, inj)
  } else {
    // Check for injections within the string.
    const partial = (_m: string, ref: string) => {
      if (3 < size(ref)) {
        ref = re_replace(R_DS_ESCAPE, re_replace(R_BT_ESCAPE, ref, S_BT), S_DS)
      }

      if (inj) {
        inj.full = false
      }

      const found = getpath(store, ref, inj)

      return NONE === found ? S_MT : S_string === typeof found ? found : JSON.stringify(found)
    }

    out = re_replace(R_INJECTION_PARTIAL, val, (m) => partial('', m[1]))

    // Also call the inj handler on the entire string, providing the
    // option for custom injection.
    if (null != inj && isfunc(inj.handler)) {
      inj.full = true
      out = inj.handler(inj, out, val, store)
    }
  }

  return out
}

// Handler Utilities
// =================

const MODENAME: any = {
  [M_VAL]: 'val',
  [M_KEYPRE]: 'key:pre',
  [M_KEYPOST]: 'key:post',
}

const PLACEMENT: any = {
  [M_VAL]: 'value',
  [M_KEYPRE]: S_key,
  [M_KEYPOST]: S_key,
}

function checkPlacement(
  modes: InjectMode,
  ijname: string,
  parentTypes: number,
  inj: Injection,
): boolean {
  if (0 === (modes & inj.mode)) {
    inj.errs.push(
      '$' +
        ijname +
        ': invalid placement as ' +
        PLACEMENT[inj.mode] +
        ', expected: ' +
        join(
          items(
            [M_KEYPRE, M_KEYPOST, M_VAL].filter((m) => modes & m),
            (n: any) => PLACEMENT[n[1]],
          ),
          ',',
        ) +
        '.',
    )
    return false
  }
  if (!isempty(parentTypes)) {
    const ptype = typify(inj.parent)
    if (0 === (parentTypes & ptype)) {
      inj.errs.push(
        '$' +
          ijname +
          ': invalid placement in parent ' +
          typename(ptype) +
          ', expected: ' +
          typename(parentTypes) +
          '.',
      )
      return false
    }
  }
  return true
}

function injectorArgs(argTypes: number[], args: any[]): any {
  const numargs = size(argTypes)
  const found = new Array(1 + numargs)
  found[0] = NONE
  for (let argI = 0; argI < numargs; argI++) {
    const arg = args[argI]
    const argType = typify(arg)
    if (0 === (argTypes[argI] & argType)) {
      found[0] =
        'invalid argument: ' +
        stringify(arg, 22) +
        ' (' +
        typename(argType) +
        ' at position ' +
        (1 + argI) +
        ') is not of type: ' +
        typename(argTypes[argI]) +
        '.'
      break
    }
    found[1 + argI] = arg
  }
  return found
}

function injectChild(child: any, store: any, inj: Injection): Injection {
  let cinj = inj

  // Replace ['`$FORMAT`',...] with child
  if (null != inj.prior) {
    if (null != inj.prior.prior) {
      cinj = inj.prior.prior.child(inj.prior.keyI, inj.prior.keys)
      cinj.val = child
      setprop(cinj.parent, inj.prior.key, child)
    } else {
      cinj = inj.prior.child(inj.keyI, inj.keys)
      cinj.val = child
      setprop(cinj.parent, inj.key, child)
    }
  }

  inject(child, store, cinj)

  return cinj
}

class StructUtility {
  clone = clone
  condense = condense
  condenseview = condenseview
  delprop = delprop
  escre = escre
  escurl = escurl
  expand = expand
  filter = filter
  flatten = flatten
  getdef = getdef
  getelem = getelem
  getpath = getpath
  getprop = getprop
  haskey = haskey
  inject = inject
  isempty = isempty
  iscondensed = iscondensed
  isfunc = isfunc
  iskey = iskey
  islist = islist
  ismap = ismap
  isnode = isnode
  items = items
  join = join
  jsonify = jsonify
  keysof = keysof
  merge = merge
  pad = pad
  pathify = pathify
  select = select
  setpath = setpath
  setprop = setprop
  size = size
  slice = slice
  strkey = strkey
  stringify = stringify
  transform = transform
  typify = typify
  typename = typename
  validate = validate
  walk = walk

  re_compile = re_compile
  re_find = re_find
  re_find_all = re_find_all
  re_replace = re_replace
  re_test = re_test
  re_escape = re_escape

  SKIP = SKIP
  DELETE = DELETE

  jm = jm
  jt = jt
  tn = typename

  T_any = T_any
  T_noval = T_noval
  T_boolean = T_boolean
  T_decimal = T_decimal
  T_integer = T_integer
  T_number = T_number
  T_string = T_string
  T_function = T_function
  T_symbol = T_symbol
  T_null = T_null
  T_list = T_list
  T_map = T_map
  T_instance = T_instance
  T_scalar = T_scalar
  T_node = T_node

  checkPlacement = checkPlacement
  injectorArgs = injectorArgs
  injectChild = injectChild
}

const CONDENSE_VERSION = 1

const CONDENSE_MAP = 0
const CONDENSE_LIST = 1
const CONDENSE_STR = 2
const CONDENSE_NUM = 3
const CONDENSE_TRUE = 4
const CONDENSE_FALSE = 5
const CONDENSE_NULL = 6

const S_condense = '$condense'
const S_condsym = 'sym'
const S_condnode = 'node'
const S_condroot = 'root'

function condenseCmp(a: string, b: string): number {
  let i = 0
  let j = 0
  while (i < a.length && j < b.length) {
    const ca = a.codePointAt(i) as number
    const cb = b.codePointAt(j) as number
    if (ca !== cb) {
      return ca < cb ? -1 : 1
    }
    i += 0xffff < ca ? 2 : 1
    j += 0xffff < cb ? 2 : 1
  }
  return a.length - i - (b.length - j)
}

function condenseSet(obj: any, key: string, val: any) {
  if ('__proto__' === key) {
    Object.defineProperty(obj, key, {
      value: val,
      enumerable: true,
      writable: true,
      configurable: true,
    })
  } else {
    obj[key] = val
  }
}

function iscondensed(val: any): boolean {
  // The version must MATCH, not merely be numeric: a future profile would
  // otherwise be decoded under this one's schema.
  return (
    ismap(val) &&
    CONDENSE_VERSION === (val as any)[S_condense] &&
    islist((val as any)[S_condsym]) &&
    islist((val as any)[S_condnode]) &&
    'number' === typeof (val as any)[S_condroot]
  )
}

// Condense any JSON-shaped node. Pure: the same input always produces a
// byte-identical result, on every port.
function condense(val: any): any {
  // Pass one: every distinct map key and string value, once, sorted.
  const symset: { [sym: string]: boolean } = Object.create(null)

  const collect = (n: any) => {
    if (ismap(n)) {
      const keys = keysof(n)
      for (let i = 0; i < keys.length; i++) {
        symset[keys[i]] = true
        collect((n as any)[keys[i]])
      }
    } else if (islist(n)) {
      for (let i = 0; i < n.length; i++) {
        collect(n[i])
      }
    } else if ('string' === typeof n) {
      symset[n] = true
    }
  }
  collect(val)

  const sym = Object.keys(symset).sort(condenseCmp)
  const symid: { [sym: string]: number } = Object.create(null)
  for (let i = 0; i < sym.length; i++) {
    symid[sym[i]] = i
  }

  // Pass two: build post-order, interning on the canonical encoding. Because
  // children are built first, identical subtrees have already been interned
  // by the time a parent references them, so sharing costs nothing extra.
  const node: any[][] = []
  const seen: { [enc: string]: number } = Object.create(null)

  const intern = (enc: any[]): number => {
    // The kind tag leads every encoding, so a string node and a number node
    // can never collide on the same joined key.
    const enckey = enc.join(',')
    const hit = seen[enckey]
    if (undefined !== hit) {
      return hit
    }
    const idx = node.length
    node.push(enc)
    seen[enckey] = idx
    return idx
  }

  const build = (n: any): number => {
    if (ismap(n)) {
      const enc: any[] = [CONDENSE_MAP]
      // keysof sorts, so the key ids ascend and lookup can bisect.
      const keys = keysof(n)
      for (let i = 0; i < keys.length; i++) {
        enc.push(symid[keys[i]])
        enc.push(build((n as any)[keys[i]]))
      }
      return intern(enc)
    }
    if (islist(n)) {
      const enc: any[] = [CONDENSE_LIST]
      for (let i = 0; i < n.length; i++) {
        enc.push(build(n[i]))
      }
      return intern(enc)
    }
    if ('string' === typeof n) {
      return intern([CONDENSE_STR, symid[n]])
    }
    if ('number' === typeof n) {
      return intern([CONDENSE_NUM, n])
    }
    if (true === n) {
      return intern([CONDENSE_TRUE])
    }
    if (false === n) {
      return intern([CONDENSE_FALSE])
    }
    return intern([CONDENSE_NULL])
  }

  const root = build(val)

  const out: any = {}
  out[S_condense] = CONDENSE_VERSION
  out[S_condsym] = sym
  out[S_condnode] = node
  out[S_condroot] = root
  return out
}

// Resolve a symbol to its id by bisecting the sorted symbol table. -1 when
// the string does not occur anywhere in the structure, which is itself a fast
// negative answer for a key lookup.
function condenseSymId(cond: any, key: string): number {
  const sym = (cond as any)[S_condsym]
  let lo = 0
  let hi = sym.length - 1
  while (lo <= hi) {
    const mid = (lo + hi) >> 1
    if (sym[mid] === key) {
      return mid
    }
    if (0 > condenseCmp(sym[mid], key)) {
      lo = mid + 1
    } else {
      hi = mid - 1
    }
  }
  return -1
}

// The node index of `key` inside node `idx`, or -1. Touches only this node.
function condenseChild(cond: any, idx: number, key: any): number {
  const enc = (cond as any)[S_condnode][idx]
  if (null == enc) {
    return -1
  }

  if (CONDENSE_MAP === enc[0]) {
    const symid = condenseSymId(cond, S_MT + key)
    if (0 > symid) {
      return -1
    }
    // Pairs live at [1,2], [3,4], ... with keys ascending: bisect the pairs.
    let lo = 0
    let hi = (enc.length - 1) / 2 - 1
    while (lo <= hi) {
      const mid = (lo + hi) >> 1
      const k = enc[1 + mid * 2]
      if (k === symid) {
        return enc[2 + mid * 2]
      }
      if (k < symid) {
        lo = mid + 1
      } else {
        hi = mid - 1
      }
    }
    return -1
  }

  if (CONDENSE_LIST === enc[0]) {
    // Canonical integer keys ONLY. Unary + would accept "01", "1e0", " 1"
    // and "+1", which an ordinary list lookup treats as plain (absent)
    // properties - condensing must not change which value a path selects.
    const k = S_MT + key
    if (!/^(0|[1-9][0-9]*)$/.test(k)) {
      return -1
    }
    const i = +k
    if (i >= enc.length - 1) {
      return -1
    }
    return enc[1 + i]
  }

  return -1
}

// Walk a path from a starting node, returning the node index or -1.
function condenseResolve(cond: any, idx: number, path: any): number {
  const parts = islist(path)
    ? path
    : 'string' === typeof path
      ? '' === path
        ? []
        : path.split(S_DT)
      : null == path
        ? []
        : [S_MT + path]

  let at = idx
  for (let i = 0; i < parts.length; i++) {
    if (0 > at) {
      return -1
    }
    if (S_MT === parts[i]) {
      continue
    }
    at = condenseChild(cond, at, parts[i])
  }
  return at
}

function condenseMaterialise(cond: any, idx: number): any {
  const sym = (cond as any)[S_condsym]
  const node = (cond as any)[S_condnode]

  const rebuild = (i: number): any => {
    const enc = node[i]
    if (null == enc) {
      return undefined
    }
    const kind = enc[0]
    if (CONDENSE_MAP === kind) {
      const out: any = {}
      for (let j = 1; j < enc.length; j += 2) {
        condenseSet(out, sym[enc[j]], rebuild(enc[j + 1]))
      }
      return out
    }
    if (CONDENSE_LIST === kind) {
      const out: any[] = []
      for (let j = 1; j < enc.length; j++) {
        out.push(rebuild(enc[j]))
      }
      return out
    }
    if (CONDENSE_STR === kind) {
      return sym[enc[1]]
    }
    if (CONDENSE_NUM === kind) {
      return enc[1]
    }
    if (CONDENSE_TRUE === kind) {
      return true
    }
    if (CONDENSE_FALSE === kind) {
      return false
    }
    return null
  }

  return 0 > idx ? undefined : rebuild(idx)
}

// Fully materialise a condensed structure. The escape hatch: correct for any
// caller, but it gives up every benefit of condensing, so prefer a view or a
// path read.
function expand(cond: any): any {
  if (!iscondensed(cond)) {
    return cond
  }
  return condenseMaterialise(cond, (cond as any)[S_condroot])
}

// The keys of node `idx`, WITHOUT materialising any of its values. This is
// the point of the whole exercise for enumeration: listing the names in a
// large collection should cost a symbol-table read, not a full decode.
function condenseKeys(cond: any, idx: number): string[] {
  const enc = (cond as any)[S_condnode][idx]
  if (null == enc) {
    return []
  }
  const sym = (cond as any)[S_condsym]
  const out: string[] = []
  if (CONDENSE_MAP === enc[0]) {
    for (let j = 1; j < enc.length; j += 2) {
      out.push(sym[enc[j]])
    }
    return out
  }
  if (CONDENSE_LIST === enc[0]) {
    for (let j = 1; j < enc.length; j++) {
      out.push(S_MT + (j - 1))
    }
    return out
  }
  return []
}

// A cursor into a condensed structure. Reads resolve by integer index and
// touch only the nodes on the path, so the cost of a lookup is proportional
// to path depth and result size, never to total structure size.
type CondenseView = {
  get: (path?: any) => any
  keys: (path?: any) => string[]
  has: (path?: any) => boolean
  at: (path?: any) => CondenseView
  value: () => any
  size: () => number
  exists: () => boolean
  ref: () => any
}

function condenseview(cond: any, idx?: number, memo?: any): CondenseView {
  const start = null == idx ? (iscondensed(cond) ? (cond as any)[S_condroot] : -1) : idx

  // Shared materialisations, handed out ONLY by ref(). Threaded through at()
  // so every cursor into the same structure shares one memo - otherwise
  // ref() would hand out a different object per cursor and quietly stop
  // being the shared-reference escape hatch it claims to be.
  const refmemo: { [idx: string]: any } = null == memo ? {} : memo

  const view: CondenseView = {
    // The value at path, materialised. Scalars come back directly; a
    // container comes back as an independent copy.
    get: (path?: any) => condenseMaterialise(cond, condenseResolve(cond, start, path)),

    // Key names at path, with no value decoding at all.
    keys: (path?: any) => {
      const at = condenseResolve(cond, start, path)
      return 0 > at ? [] : condenseKeys(cond, at)
    },

    has: (path?: any) => 0 <= condenseResolve(cond, start, path),

    // Chainable cursor. Cheap: no decoding happens here.
    at: (path?: any) => condenseview(cond, condenseResolve(cond, start, path), refmemo),

    value: () => condenseMaterialise(cond, start),

    size: () => {
      const enc = 0 > start ? null : (cond as any)[S_condnode][start]
      if (null == enc) {
        return 0
      }
      if (CONDENSE_MAP === enc[0]) {
        return (enc.length - 1) / 2
      }
      if (CONDENSE_LIST === enc[0]) {
        return enc.length - 1
      }
      return 0
    },

    exists: () => 0 <= start,

    // DANGER, and named to say so. Returns a SHARED materialisation: the same
    // object for the same node, every time. Mutating it corrupts every other
    // reader of that node, including ones reached by a different path,
    // because the structure is a DAG. Use value() unless a profile says this
    // matters.
    ref: () => {
      const k = S_MT + start
      if (undefined === refmemo[k]) {
        refmemo[k] = condenseMaterialise(cond, start)
      }
      return refmemo[k]
    },
  }

  return view
}

export {
  StructUtility,
  clone,
  condense,
  condenseview,
  expand,
  iscondensed,
  delprop,
  escre,
  escurl,
  filter,
  flatten,
  getdef,
  getelem,
  getpath,
  getprop,
  haskey,
  inject,
  isempty,
  isfunc,
  iskey,
  islist,
  ismap,
  isnode,
  items,
  join,
  jsonify,
  keysof,
  merge,
  pad,
  pathify,
  select,
  setpath,
  setprop,
  size,
  slice,
  strkey,
  stringify,
  transform,
  typify,
  typename,
  validate,
  walk,
  re_compile,
  re_find,
  re_find_all,
  re_replace,
  re_test,
  re_escape,
  SKIP,
  DELETE,
  jm,
  jt,
  T_any,
  T_noval,
  T_boolean,
  T_decimal,
  T_integer,
  T_number,
  T_string,
  T_function,
  T_symbol,
  T_null,
  T_list,
  T_map,
  T_instance,
  T_scalar,
  T_node,
  M_KEYPRE,
  M_KEYPOST,
  M_VAL,
  MODENAME,
  checkPlacement,
  injectorArgs,
  injectChild,
}

export type { Injection, Injector, WalkApply }