Stack

/*
 * A page, read as a stack of plates, and the camera that looks at it sideways.
 *
 * Firefox used to ship a 3D view of the DOM and people still miss it. The idea
 * is one line long: a box's nesting depth is a z coordinate. Everything after
 * that is a rigid rotation and a divide.
 *
 * Two things this file deliberately does not use. There is no 3D library,
 * because a scene of flat quads with no lighting is a four by four matrix and a
 * sort, and importing a renderer for it would be more code than the renderer.
 * And there is no GPU: the projection is the whole of the 3D, and once a corner
 * is a pair of screen coordinates, a 2D canvas draws a crisp hairline round it
 * more easily than WebGL does. Perspective is arithmetic, not hardware.
 */

export type Layer = {
  /** How deep in the document this box is nested. This is its z. */
  depth: number;
  x: number;
  y: number;
  width: number;
  height: number;
  /** Something like `div.card`, short enough to sit in a label. */
  label: string;
  /** The computed background, or null when the box paints nothing at all. */
  fill: string | null;
  /** Whether this box holds text of its own rather than only other boxes. */
  ink: boolean;
  /**
   * Why this box starts a new stacking context, if it does. The most useful
   * thing on the whole plate: a stacking context is invisible in the page and
   * is the reason a z-index that "should work" does not.
   */
  context: string | null;
};

/* Boxes that are not layout. `br` and `wbr` have rects and mean nothing here. */
const SKIP = new Set([
  "script",
  "style",
  "link",
  "meta",
  "title",
  "head",
  "noscript",
  "br",
  "wbr",
  "template",
]);

/* Anything smaller than this in either direction is a hairline or a spacer, and
   a plate you cannot see is a plate that only slows the sort down. */
const MIN = 4;

/*
 * The list of things that quietly start a stacking context, in the order worth
 * reporting them. Only the ones that actually turn up in ordinary layout • the
 * full list in the spec runs to about twenty entries, most of which nobody has
 * ever typed.
 */
function contextFor(style: CSSStyleDeclaration): string | null {
  if (style.position === "fixed" || style.position === "sticky") {
    return style.position;
  }
  if (style.position !== "static" && style.zIndex !== "auto") {
    return `${style.position} + z-index`;
  }
  if (style.transform !== "none") return "transform";
  if (style.filter !== "none") return "filter";
  if (style.mixBlendMode !== "normal") return "mix-blend-mode";
  if (style.isolation === "isolate") return "isolation";
  if (style.opacity !== "" && Number(style.opacity) < 1) return "opacity";
  if (/transform|opacity|filter/.test(style.willChange)) return "will-change";
  return null;
}

/** `section.tray`, or just `section` • one class is a hint, five is a paragraph. */
function labelFor(element: Element) {
  const tag = element.tagName.toLowerCase();
  const first = element.classList[0];
  if (!first) return tag;
  /* Utility class names are long and there are dozens of them per element; the
     first one is as good a name as any and the only one that fits. */
  return `${tag}.${first.length > 18 ? `${first.slice(0, 17)}…` : first}`;
}

/** True when the box has text of its own rather than only more boxes. */
function hasInk(element: Element) {
  for (const node of element.childNodes) {
    if (node.nodeType === Node.TEXT_NODE && node.textContent?.trim()) {
      return true;
    }
  }
  return false;
}

/*
 * The document, flattened.
 *
 * Breadth first rather than depth first, so a cap on the number of boxes cuts
 * the deepest ones rather than everything after the first long branch • the
 * shape of the page survives being truncated.
 */
export function read(doc: Document, cap = 420): Layer[] {
  const root = doc.body;
  if (!root) return [];

  const view = doc.defaultView;
  if (!view) return [];

  const layers: Layer[] = [];
  let queue: { element: Element; depth: number }[] = [
    { element: root, depth: 0 },
  ];

  while (queue.length > 0 && layers.length < cap) {
    const next: { element: Element; depth: number }[] = [];
    for (const { element, depth } of queue) {
      if (layers.length >= cap) break;
      const rect = element.getBoundingClientRect();
      if (rect.width < MIN || rect.height < MIN) continue;

      const style = view.getComputedStyle(element);
      if (style.display === "none" || style.visibility === "hidden") continue;

      const background = style.backgroundColor;
      layers.push({
        depth,
        x: rect.x,
        y: rect.y,
        width: rect.width,
        height: rect.height,
        label: labelFor(element),
        /* rgba(0, 0, 0, 0) is what "no background" computes to. Painting it
           would be painting nothing, slowly. */
        fill:
          background && !/^rgba\(0, 0, 0, 0\)$/.test(background)
            ? background
            : null,
        ink: hasInk(element),
        context: contextFor(style),
      });

      for (const child of element.children) {
        if (!SKIP.has(child.tagName.toLowerCase())) {
          next.push({ element: child, depth: depth + 1 });
        }
      }
    }
    queue = next;
  }

  return layers;
}

export type Camera = {
  /** Radians. Yaw turns the stack, pitch tips it. */
  yaw: number;
  pitch: number;
  /** Pixels between one nesting level and the next. */
  spread: number;
};

export type Viewport = { width: number; height: number };

/**
 * A function from a point on a plate to a point on the canvas.
 *
 * Built once per frame rather than per corner: the eight sines and cosines of
 * the rotation are the same for every one of a few thousand corners, and
 * recomputing them inside the loop is most of the cost of the whole draw.
 */
export function project(
  camera: Camera,
  view: Viewport,
  page: { width: number; height: number; depth: number },
) {
  const cosYaw = Math.cos(camera.yaw);
  const sinYaw = Math.sin(camera.yaw);
  const cosPitch = Math.cos(camera.pitch);
  const sinPitch = Math.sin(camera.pitch);

  /* Far enough back that the perspective is a hint rather than a fisheye. Tied
     to the width of the page so a narrow layout is not viewed from orbit. */
  const distance = Math.max(page.width, page.height) * 1.9;

  /*
   * The scale that fits the page on the canvas when it is facing you, with room
   * left for the corners a rotation swings outwards. Focal length is that scale
   * times the distance, which is what makes an unrotated plate at z = 0 land at
   * exactly its own size.
   */
  const fit =
    Math.min(view.width / page.width, view.height / page.height) * 0.62;
  const focal = distance * fit;

  const halfDepth = (page.depth * camera.spread) / 2;

  return (x: number, y: number, depth: number) => {
    const px = x - page.width / 2;
    const py = y - page.height / 2;
    const pz = depth * camera.spread - halfDepth;

    const ax = px * cosYaw + pz * sinYaw;
    const az = pz * cosYaw - px * sinYaw;

    const by = py * cosPitch - az * sinPitch;
    const bz = az * cosPitch + py * sinPitch;

    /*
     * Clamped rather than allowed to cross zero. A point level with the eye
     * divides by nothing and comes back as an infinity that poisons the whole
     * path it belongs to; at these angles it cannot happen, and the day
     * somebody widens the pitch slider it should bend rather than explode.
     */
    const scale = focal / Math.max(distance * 0.2, distance - bz);
    return {
      x: view.width / 2 + ax * scale,
      y: view.height / 2 + by * scale,
      /* Kept for the sort. Plates are parallel and never intersect, so ordering
         by the depth of their centres is not an approximation here • it is
         exactly right, which is why this needs no depth buffer. */
      z: bz,
    };
  };
}

/** Whether a point is inside a projected plate, for hit testing under the cursor. */
export function inside(
  point: { x: number; y: number },
  quad: { x: number; y: number }[],
) {
  let hit = false;
  for (let i = 0, j = quad.length - 1; i < quad.length; j = i++) {
    const a = quad[i];
    const b = quad[j];
    if (
      a.y > point.y !== b.y > point.y &&
      point.x < ((b.x - a.x) * (point.y - a.y)) / (b.y - a.y) + a.x
    ) {
      hit = !hit;
    }
  }
  return hit;
}