Function isTree

packages/effect/src/SchemaAST.ts:4193–4251

(u: unknown, isLeaf: (u: unknown) => boolean)

}

function isTree(u: unknown, isLeaf: (u: unknown) => boolean): boolean {
  const cache = new WeakMap<object, boolean>()
  const stack: Array<TreeFrame> = []
  outer: while (true) {
    if (typeof u !== "object" || u === null) {
      if (!isLeaf(u)) {
        return false
      }
    } else {
      const value = u
      const cached = cache.get(value)
      // `false` marks a node on the current path, while `true` marks a fully
      // validated node that can be safely reused by a DAG.
      if (cached === false) {
        return false
      }
      if (cached === undefined) {
        const isArray = Array.isArray(value)
        if (!isArray) {
          const prototype = Object.getPrototypeOf(value)
          // A plain object from another realm has a different Object.prototype,
          // but that prototype still has a null prototype.
          if (
            prototype !== null &&
            prototype !== Object.prototype &&
            Object.getPrototypeOf(prototype) !== null
          ) {
            return false
          }
        }
        cache.set(value, false)
        stack.push({
          value,
          keys: isArray ? value.length : Object.keys(value),
          index: 0
        })
      }
    }

    while (stack.length > 0) {
      const frame = stack[stack.length - 1]
      const keys = frame.keys
      if (typeof keys === "number") {
        if (frame.index < keys) {
          // A sparse slot is read as `undefined`; the leaf predicate determines
          // whether that is valid for the current tree.
          u = (frame.value as ReadonlyArray<unknown>)[frame.index++]
          continue outer
        }
      } else if (frame.index < keys.length) {
        u = (frame.value as Record<string, unknown>)[keys[frame.index++]]
        continue outer
      }
      cache.set(frame.value, true)
      stack.pop()
    }
    return true
  }