@kumu/hydra - npm Package Compare versions

Comparing version 0.0.0-kumu.20 to 0.0.0-kumu.21

package.json

 {
   "name": "@kumu/hydra",
-  "version": "0.0.0-kumu.20",
+  "version": "0.0.0-kumu.21",
   "type": "module",
@@ -29,3 +29,5 @@ "types": "./dist/index.d.ts",
     "vite-plugin-dts": "^3.6.3",
-    "vitest": "^0.34.4"
+    "vitepress": "^1.1.0",
+    "vitest": "^0.34.4",
+    "vue": "^3.4.23"
   },
@@ -40,4 +42,7 @@ "lint-staged": {
     "test": "vitest",
-    "typecheck": "tsc && tsc -p ./playground && tsc -p ./examples"
+    "typecheck": "tsc && tsc -p ./playground && tsc -p ./examples",
+    "docs:dev": "vitepress dev docs",
+    "docs:build": "vitepress build docs",
+    "docs:preview": "vitepress preview docs"
   }
 }

src/core.test.ts

 import { expect, test, vi } from "vitest";
 import { Core } from "./core";
-import { Edge, Node } from "./entity";
+import { Edge, EntityType, Group, Node } from "./entity";
+import { parseSelectorOrThrow } from "./selectors";
+import { scale } from "./style";
 
+/**
+ * Restyles don't get scheduled in tests because `queueMicrotask` doesn't work,
+ * so we need this function to flush any that are pending after doing any
+ * operation that might trigger a restyle.
+ */
+function flushPendingRestyles(core: Core) {
+  // @ts-expect-error (using a private property)
+  core.restyleImmediately(core.restyleEntityQueue);
+}
+
 test("construct with entities", () => {
@@ -456,1 +468,65 @@ let a = new Node({ data: { id: "a" } });
 });
+
+test("interactive traversal selectors disable incremental restyling", async () => {
+  let a = new Node({ data: { id: "a", foo: "" } });
+  let g = new Group({ data: { id: "g", children: ["a"] } });
+
+  let core = new Core({
+    entities: [a, g],
+    styleRules: [
+      {
+        type: EntityType.Node,
+        // Select children of groups that are currently hovered. Because this
+        // style rule affects entities that are not actually interacted with
+        // during hovering, incremental restyling needs to be disabled to apply
+        // the styles to the correct entities.
+        selector: parseSelectorOrThrow(":child(:hover)"),
+        style: { backgroundColor: "blue" },
+      },
+    ],
+  });
+
+  expect(a.style.backgroundColor).not.toBe("blue");
+
+  // Hover over the group and expect the child to turn blue
+  core.setHoveredEntity(g);
+  flushPendingRestyles(core);
+  expect(a.style.backgroundColor).toBe("blue");
+
+  // Unhover the group and expect the child to revert to its original color.
+  core.setHoveredEntity(undefined);
+  flushPendingRestyles(core);
+  expect(a.style.backgroundColor).not.toBe("blue");
+});
+
+test("dynamic style values disable incremental restyling", () => {
+  let a = new Node({ data: { id: "a", weight: 0 } });
+  let b = new Node({ data: { id: "b", weight: 0.5 } });
+  let c = new Node({ data: { id: "c", weight: 1 } });
+
+  let core = new Core({
+    entities: [a, b],
+    styleRules: [
+      {
+        type: EntityType.Node,
+        selector: parseSelectorOrThrow("*"),
+        style: {
+          padding: scale("weight", { to: { min: 0, max: 100 } }),
+        },
+      },
+    ],
+  });
+
+  flushPendingRestyles(core);
+  expect(a.style.padding).toBe(0);
+  expect(b.style.padding).toBe(100);
+
+  // If incremental restyling was enabled, only C would be restyled, meaning
+  // that B would still have padding=100, but B's weight is in the middle of
+  // the new scaled range, so it should have been restyled.
+  core.add(c);
+  flushPendingRestyles(core);
+  expect(a.style.padding).toBe(0);
+  expect(b.style.padding).toBe(50);
+  expect(c.style.padding).toBe(100);
+});

src/core.ts

@@ -17,8 +17,14 @@ import {
 import { Renderer } from "./renderer";
-import { assert, debug, getIterableLength, warn } from "./utils";
+import { assert, debug, warn } from "./utils";
 import { Viewport } from "./viewport";
 import { Behaviour, Events } from "./behaviours";
-import { StyleRule, applyStyleRulesToGraph } from "./style";
+import {
+  StyleRule,
+  applyStyleRulesToGraph,
+  isCategorizeValue,
+  isScaleValue,
+} from "./style";
 import { invalidateEntityGeometries } from "./geometry";
 import { AnimationQueue } from "./animations";
+import { isInteractiveTraversalSelector } from "./selectors";
 
@@ -139,2 +145,9 @@ /**
   /**
+   * Allow restyles to partial graphs. Defaults to true so that an interaction
+   * like hovering or selecting only restyles the entities that were directly
+   * affected.
+   */
+  private incrementalRestyling = true;
+
+  /**
    * The entity that is currently hovered, if there is one.
@@ -231,2 +244,6 @@ */
     this.styleRules = rules;
+
+    // Turn on incremental restyling if all of the style rules support it.
+    this.incrementalRestyling = rules.every(supportsIncrementalRestyling);
+
     this.requestRestyle();
@@ -463,4 +480,8 @@ debug(`set style rules`, rules);
     this.invalidateValueCache();
-    this.requestRender();
 
+    // We need to pass an empty array so that we don't end up restyling the
+    // entire graph (the default value) when we're in incremental restyling
+    // mode.
+    this.requestRestyle([]);
+
     let arrayOfRemovedEntities = Array.from(removals);
@@ -676,3 +697,6 @@ debug("removed", arrayOfRemovedEntities);
   public restyleImmediately(entities: Iterable<Entity<N, E, G>> = this.graph) {
-    let graph = entities === this.graph ? this.graph : new Graph(entities);
+    let graph =
+      entities === this.graph || !this.incrementalRestyling
+        ? this.graph
+        : new Graph(entities);
 
@@ -692,3 +716,3 @@ applyStyleRulesToGraph(this, graph, this.styleRules);
     this.profiling.lastRestyleTime = performance.now();
-    this.profiling.lastRestyleEntityCount = getIterableLength(entities);
+    this.profiling.lastRestyleEntityCount = graph.size();
   }
@@ -756,3 +780,2 @@
     this.dataValueCache.rebuild(this.graph);
-    this.requestRestyle(this.graph);
   }
@@ -918,2 +941,23 @@
 
+/**
+ * Check whether a given style rule is compatible with incremental restyling.
+ *
+ * If a style rule uses an interactive traversal selector or contains dynamic
+ * scale/categorize values then there's a chance that changes to the graph
+ * (like adding/removing/updating/hovering/selecting an entity) have the
+ * potential to affect the styles of other (apparently unrelated) entities.
+ */
+function supportsIncrementalRestyling(styleRule: StyleRule): boolean {
+  let styleValues = Object.values(styleRule.style);
+
+  return !(
+    isInteractiveTraversalSelector(styleRule.selector) ||
+    // Technically we could be a little bit smarter here and check whether the
+    // domains are known. We only need to restyle everything if the domains are
+    // being calculated automatically.
+    styleValues.some(isScaleValue) ||
+    styleValues.some(isCategorizeValue)
+  );
+}
+
 class ValueCache {
@@ -920,0 +964,0 @@ private values: {

src/geometry.ts

@@ -41,2 +41,3 @@ import { Core } from "./core";
   isPointInPolygon,
+  isPolygonInBoundingBox,
 } from "./math";
@@ -63,3 +64,3 @@ import { measureMultiLineText } from "./text";
   } else {
-    return isGroupInBoundingBox(entity, box);
+    return isGroupInBoundingBox(entity, box, testVisibleBounds);
   }
@@ -130,9 +131,34 @@ }
 /**
- * Test whether any part of a group is inside a bounding box. Rather than
- * checking the polygonal geometry of the group, we just do a cheap check
- * to see whether the group's bounding box or circle overlaps the box in
- * question.
+ * Test whether any part of a group is inside a bounding box.
  */
-export function isGroupInBoundingBox(group: Group, box: BoundingBox): boolean {
-  if (group.style.shape === "circle") {
+export function isGroupInBoundingBox(
+  group: Group,
+  box: BoundingBox,
+  testVisibleBounds: boolean,
+): boolean {
+  if (group.style.shape === "polygon") {
+    const boundsOverlap = isBoundingBoxInBoundingBox(
+      group.geometry.boundingBox.x1,
+      group.geometry.boundingBox.y1,
+      group.geometry.boundingBox.x2,
+      group.geometry.boundingBox.y2,
+      box.x1,
+      box.y1,
+      box.x2,
+      box.y2,
+    );
+
+    if (testVisibleBounds) return boundsOverlap;
+
+    return (
+      boundsOverlap &&
+      isPolygonInBoundingBox(
+        group.geometry.polygonPoints,
+        box.x1,
+        box.y1,
+        box.x2,
+        box.y2,
+      )
+    );
+  } else if (group.style.shape === "circle") {
     return isCircleInBoundingBox(
@@ -139,0 +165,0 @@ group.geometry.center.x,

src/index.ts

@@ -27,2 +27,3 @@ /**
   EdgeStyleRule,
+  GroupStyleRule,
   DataValue,
@@ -64,2 +65,4 @@ ScaleValue,
   createTapBehaviour,
+  type TapToSelectConfig,
+  createTapToSelectBehaviour,
   type HoverConfig,
@@ -66,0 +69,0 @@ createHoverBehaviour,

src/math.test.ts

@@ -14,2 +14,3 @@ import { test, expect } from "vitest";
   createCircleFromTwoPoints,
+  createCircleFromThreePoints,
   getAngleBetweenPoints,
@@ -150,2 +151,15 @@ getArcMidPoint,
 
+test("createCircleFromThreePoints", () => {
+  expect(createCircleFromThreePoints(0, 0, 5, -1, 10, 0)).toEqual({
+    center: { x: 5, y: 12 },
+    radius: 13,
+  });
+
+  // Points are collinear, circle is illegal.
+  expect(createCircleFromThreePoints(0, 0, 5, 0, 10, 0)).toEqual({
+    center: { x: NaN, y: Infinity },
+    radius: Infinity,
+  });
+});
+
 test("isPointInCircle", () => {
@@ -152,0 +166,0 @@ expect(isPointInCircle(-10, -10, 0, 0, 5)).toBe(false);

src/math.ts

@@ -316,16 +316,20 @@ export const DEG_90 = Math.PI / 2;
 ): Circle {
-  let a21 = (y2 - y1) / (x2 - x1);
-  let a31 = (y3 - y1) / (x3 - x1);
-  let b21 = 1 / a21;
-  let b31 = 1 / a31;
-  let xb21 = (x1 + x2) / 2;
-  let yb21 = (y1 + y2) / 2;
-  let xb31 = (x1 + x3) / 2;
-  let yb31 = (y1 + y3) / 2;
+  let a = x1 * (y2 - y3) - y1 * (x2 - x3) + x2 * y3 - x3 * y2;
 
-  let x0 = (b31 * xb31 - b21 * xb21 + yb31 - yb21) / (b31 - b21);
-  let y0 = (a31 * yb31 - a21 * yb21 + xb31 - xb21) / (a31 - a21);
-  let radius = Math.hypot(x3 - x0, y3 - y0);
+  let b =
+    (x1 * x1 + y1 * y1) * (y3 - y2) +
+    (x2 * x2 + y2 * y2) * (y1 - y3) +
+    (x3 * x3 + y3 * y3) * (y2 - y1);
 
-  return { center: { x: x0, y: y0 }, radius };
+  let c =
+    (x1 * x1 + y1 * y1) * (x2 - x3) +
+    (x2 * x2 + y2 * y2) * (x3 - x1) +
+    (x3 * x3 + y3 * y3) * (x1 - x2);
+
+  let x = -b / (2 * a);
+  let y = -c / (2 * a);
+
+  let radius = Math.hypot(x - x1, y - y1);
+
+  return { center: { x, y }, radius };
 }
@@ -633,13 +637,10 @@
 ): boolean {
-  // TODO: Turning the line into a bounding box is a bit lazy and will return
-  // some false positives.
-  return isBoundingBoxInBoundingBox(
-    Math.min(lx1, lx2),
-    Math.min(ly1, ly2),
-    Math.max(lx1, lx2),
-    Math.max(ly1, ly2),
-    bx1,
-    by1,
-    bx2,
-    by2,
+  const bw = bx2 - bx1;
+  const bh = by2 - by1;
+
+  return (
+    isLineInLine(lx1, ly1, lx2, ly2, bx1, by1, bx1, by1 + bh) ||
+    isLineInLine(lx1, ly1, lx2, ly2, bx1 + bw, by1, bx1 + bw, by1 + bh) ||
+    isLineInLine(lx1, ly1, lx2, ly2, bx1, by1, bx1 + bw, by1) ||
+    isLineInLine(lx1, ly1, lx2, ly2, bx1, by1 + bh, bx1 + bw, by1 + bh)
   );
@@ -649,2 +650,58 @@ }
 /**
+ * Test whether a polygon and a bounding box intersect.
+ */
+export const isPolygonInBoundingBox = (
+  polygon: Point[],
+  x1: number,
+  y1: number,
+  x2: number,
+  y2: number,
+) => {
+  // See if any of the polygon's points are within the bounding box
+  for (let i = 0; i < polygon.length; i++) {
+    const a = polygon[i];
+    if (isPointInBoundingBox(a.x, a.y, x1, y1, x2, y2)) {
+      return true;
+    }
+  }
+
+  // See if any of the polygon's sides intersect with the bounding box
+  for (let i = 0; i < polygon.length; i++) {
+    const a = polygon[i];
+    const b = polygon[i + 1] ?? polygon[0];
+
+    if (isLineInBoundingBox(a.x, a.y, b.x, b.y, x1, y1, x2, y2)) {
+      return true;
+    }
+  }
+
+  return false;
+};
+
+/**
+ * Test whether two lines intersect.
+ */
+export const isLineInLine = (
+  x1: number,
+  y1: number,
+  x2: number,
+  y2: number,
+  x3: number,
+  y3: number,
+  x4: number,
+  y4: number,
+) => {
+  // Calculate the direction of the lines.
+  const d1 =
+    ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) /
+    ((y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1));
+  const d2 =
+    ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) /
+    ((y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1));
+
+  // If d1 and d2 are between 0-1, lines intersect.
+  return d1 >= 0 && d1 <= 1 && d2 >= 0 && d2 <= 1;
+};
+
+/**
  * Find the points of intersection between two circles.
@@ -651,0 +708,0 @@ */

src/selectors.test.ts

@@ -1,3 +0,9 @@
-import { expect, test } from "vitest";
-import { testSelector, parseSelector, parseSelectorOrThrow } from "./selectors";
+import { assert, expect, test, vi } from "vitest";
+import {
+  testSelector,
+  parseSelector,
+  parseSelectorOrThrow,
+  isInteractiveTraversalSelector,
+  walk,
+} from "./selectors";
 import { Edge, EdgeData, Entity, Node, NodeData } from "./entity";
@@ -90,2 +96,17 @@ import { Graph } from "./graph";
 
+test("walk is recursive", () => {
+  let selector = parseSelectorOrThrow(":not(:from(#a))");
+  let callback = vi.fn();
+  walk(selector, callback);
+
+  let not = selector;
+  assert(not.type === "pseudo-class");
+  let from = not.subtree;
+  assert(from?.type === "pseudo-class");
+  let id = from.subtree;
+  assert(id?.type === "id");
+
+  expect(callback.mock.calls).toEqual([[not], [from], [id]]);
+});
+
 test("id selectors", () => {
@@ -189,2 +210,6 @@ expect(match("#a", N({ id: "a" }))).toBe(true);
 
+test("nested quoted attribute selectors", () => {
+  expect(match(`:not([id="a"])`, N({ id: "b" }))).toBe(true);
+});
+
 test("list selectors", () => {
@@ -273,1 +298,24 @@ expect(match(`#a,:node,[id]`, N({ id: "a" }))).toBe(true);
 });
+
+test("identifying interactive traversal selectors", () => {
+  let isInteractiveTraversal = (str: string) =>
+    isInteractiveTraversalSelector(parseSelectorOrThrow(str));
+
+  expect(isInteractiveTraversal("*")).toBe(false);
+  expect(isInteractiveTraversal("[id]")).toBe(false);
+  expect(isInteractiveTraversal(":hover")).toBe(false);
+  expect(isInteractiveTraversal(":from(#a)")).toBe(false);
+  expect(isInteractiveTraversal(":from(#a):to(#b)")).toBe(false);
+  expect(isInteractiveTraversal(":group")).toBe(false);
+  expect(isInteractiveTraversal("a likes b")).toBe(false);
+
+  expect(isInteractiveTraversal(":hover likes b")).toBe(true);
+  expect(isInteractiveTraversal("a :grabbed b")).toBe(true);
+  expect(isInteractiveTraversal("a :grabbed b")).toBe(true);
+  expect(isInteractiveTraversal("a likes :selected")).toBe(true);
+  expect(isInteractiveTraversal("a > likes > :selected")).toBe(true);
+  expect(isInteractiveTraversal(":hover < likes < :selected")).toBe(true);
+  expect(isInteractiveTraversal(":not(:hover)")).toBe(true);
+  expect(isInteractiveTraversal(":child(:hover)")).toBe(true);
+  expect(isInteractiveTraversal(":child(:group(:hover))")).toBe(true);
+});

src/selectors.ts

@@ -8,3 +8,3 @@ import {
   parse,
-  walk,
+  walk as nonRecursiveWalk,
 } from "parsel-js";
@@ -271,1 +271,48 @@ import { Entity, EntityType, isGroup } from "./entity";
 }
+
+/**
+ * An enhanced version of Parsel's `walk` function which also visits selectors
+ * with subtrees.
+ */
+export function walk(
+  selector: Selector | undefined,
+  visit: (node: Selector) => void,
+): void {
+  nonRecursiveWalk(selector, (node) => {
+    visit(node);
+    if (node.type === "pseudo-class" && node.subtree) {
+      walk(node.subtree, visit);
+    }
+  });
+}
+
+/**
+ * Test whether a given selector contains both traversals _and_ interactivity
+ * selectors. This is a sign that we'll want to bail out of incremental
+ * restyling because interactions such as hovering might cause restyles to
+ * parts of the graph that weren't explicitly part of the interaction.
+ */
+export function isInteractiveTraversalSelector(selector: Selector): boolean {
+  let interactive = false;
+  let traversal = selector.type === "complex"; // Check the root selector before we walk.
+
+  let interactiveSelectorNames = ["selected", "hover", "grabbed"];
+  let traversalSelectorNames = ["not", "from", "to", "group", "child"];
+
+  // We can't use Parsel's `walk` function here because it doesn't walk into
+  // selectors with recursive subtrees (e.g. `:not(:hover)` doesn't visit `:hover`).
+  walk(selector, (node) => {
+    if (node.type === "pseudo-class") {
+      if (interactiveSelectorNames.includes(node.name)) {
+        interactive = true;
+      }
+      if (traversalSelectorNames.includes(node.name)) {
+        traversal = true;
+      }
+    } else if (node.type === "complex") {
+      traversal = true;
+    }
+  });
+
+  return interactive && traversal;
+}

src/utils.ts

@@ -51,3 +51,3 @@ /**
 export function debug(...args: any[]) {
-  if (process.versions.bun || import.meta.env.MODE !== "test") {
+  if (import.meta.env.MODE !== "test") {
     console.debug("%c[hydra]", "color:#673ae7;font-weight:bold", ...args);
@@ -54,0 +54,0 @@ }

No alert changes

Improved metrics

Total package byte prevSize

877167

increased by2.39%

Lines of code

16002

increased by2.28%

Worsened metrics

Dev dependency count

9

increased by28.57%

No dependency changes