Skip to content

Commit e1e706d

Browse files
committed
fix(android): measure occlusion by overlapped area, not bounding box
Review on #1808: a bounding box of two corner controls spans the viewport, so a transparent overlay with a control in each corner still acquired a full-screen footprint and could prune the app beneath it. Footprints now keep their presented rects apart, and coverage is the overlapped area of the two unions (coordinate-compressed cell sweep). Scrollables count as presenting their box: they consume touches over it, which is what lets a real pushed screen (header, scrollable body, footer) still cover a drawer surface. Adds the disconnected-corner regression.
1 parent 2d3ccdf commit e1e706d

2 files changed

Lines changed: 109 additions & 45 deletions

File tree

‎src/platforms/android/__tests__/ui-hierarchy.test.ts‎

Lines changed: 30 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -329,14 +329,16 @@ test('parseUiHierarchy prunes descendants of Android nodes that are not visible
329329
});
330330

331331
test('parseUiHierarchy prunes lower drawing-order subtrees covered by a foreground sibling', () => {
332-
// A pushed screen (header + full-width rows) drawn above a still-attached drawer surface. The
333-
// pushed screen's presented content lies over the drawer's content, so the drawer is covered.
332+
// A pushed screen (header, scrollable body, footer) drawn above a still-attached drawer surface.
333+
// The pushed screen's presented content lies over the drawer's content, so the drawer is covered.
334334
const xml = `<hierarchy>
335335
<node class="android.widget.FrameLayout" bounds="[0,0][390,844]" visible-to-user="true" drawing-order="0">
336336
<node class="android.view.ViewGroup" bounds="[0,0][390,844]" visible-to-user="true" drawing-order="2">
337337
<node class="android.widget.Button" content-desc="Back" bounds="[8,40][56,88]" clickable="true" enabled="true" visible-to-user="true" drawing-order="1"/>
338338
<node class="android.widget.TextView" text="Foreground screen" bounds="[72,44][300,84]" enabled="true" visible-to-user="true" drawing-order="2"/>
339-
<node class="android.widget.Button" text="Foreground action" bounds="[0,120][390,180]" clickable="true" enabled="true" visible-to-user="true" drawing-order="3"/>
339+
<node class="android.widget.ScrollView" bounds="[0,120][390,780]" scrollable="true" enabled="true" visible-to-user="true" drawing-order="3">
340+
<node class="android.widget.Button" text="Foreground action" bounds="[24,140][366,200]" clickable="true" enabled="true" visible-to-user="true" drawing-order="1"/>
341+
</node>
340342
<node class="android.widget.Button" text="Foreground footer" bounds="[0,780][390,844]" clickable="true" enabled="true" visible-to-user="true" drawing-order="4"/>
341343
</node>
342344
<node class="android.view.ViewGroup" bounds="[0,0][390,844]" visible-to-user="true" drawing-order="1">
@@ -399,6 +401,31 @@ test('parseUiHierarchy keeps app content beside an empty labelled full-screen pl
399401
);
400402
});
401403

404+
test('parseUiHierarchy keeps app content under an overlay whose only controls sit in opposite corners', () => {
405+
// Two floating controls in opposite corners present two corners, not the screen between them.
406+
// A bounding box of the presented content would span the viewport and condemn the whole app.
407+
const xml = `<hierarchy>
408+
<node class="android.widget.FrameLayout" bounds="[0,0][390,844]" visible-to-user="true" drawing-order="0">
409+
<node class="android.widget.LinearLayout" bounds="[0,0][390,844]" visible-to-user="true" drawing-order="1">
410+
<node class="android.widget.TextView" text="Editor" bounds="[24,60][300,120]" enabled="true" visible-to-user="true" drawing-order="1"/>
411+
<node class="android.widget.ScrollView" bounds="[0,140][390,760]" scrollable="true" enabled="true" visible-to-user="true" drawing-order="2">
412+
<node class="android.widget.Button" text="Save" bounds="[24,400][366,460]" clickable="true" enabled="true" visible-to-user="true" drawing-order="1"/>
413+
</node>
414+
</node>
415+
<node class="android.widget.FrameLayout" bounds="[0,0][390,844]" visible-to-user="true" drawing-order="2">
416+
<node class="android.widget.ImageView" content-desc="Debug menu" bounds="[8,8][56,56]" clickable="true" enabled="true" visible-to-user="true" drawing-order="1"/>
417+
<node class="android.widget.ImageView" content-desc="Frame stats" bounds="[334,788][382,836]" clickable="true" enabled="true" visible-to-user="true" drawing-order="2"/>
418+
</node>
419+
</node>
420+
</hierarchy>`;
421+
422+
const result = parseUiHierarchy(xml, 800, { raw: true });
423+
assert.deepEqual(
424+
result.nodes.filter((node) => node.label).map((node) => node.label),
425+
['Editor', 'Save', 'Debug menu', 'Frame stats'],
426+
);
427+
});
428+
402429
test('parseUiHierarchy compares presented footprints so a sparse overlay never condemns a rich sibling', () => {
403430
// The overlay's only content is a corner badge; the sibling's content spans the screen. Box
404431
// geometry alone (overlay box ⊇ sibling box) would call this covered.

‎src/platforms/android/ui-hierarchy.ts‎

Lines changed: 79 additions & 42 deletions
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,6 @@ import type { RawSnapshotNode, Rect, SnapshotOptions } from '@agent-device/kerne
22
import { parseBounds } from '@agent-device/kernel/bounds';
33
import { decodeXmlCharacterReferences } from '@agent-device/xml';
44
import { isScrollableType } from '@agent-device/contracts/snapshot';
5-
import { intersectArea } from '../../utils/screenshot-geometry.ts';
65
import {
76
type AndroidSystemChromeProvenance,
87
isAndroidSystemChromeWindowResourceId,
@@ -453,8 +452,8 @@ type AndroidNodeInclusionInfo = {
453452
};
454453

455454
type AndroidFootprint = {
456-
/** Bounding box of what the subtree presents (agent targets and labelled leaves), if anything. */
457-
rect: Rect | null;
455+
/** Boxes of what the subtree presents: touch/focus targets, scrollables and labelled leaves. */
456+
rects: Rect[];
458457
hasAgentTarget: boolean;
459458
};
460459

@@ -465,7 +464,7 @@ type AndroidTreePruneState = {
465464
type AndroidCoveringCandidate = {
466465
node: AndroidNode;
467466
drawingOrder: number;
468-
footprint: Rect;
467+
footprint: Rect[];
469468
};
470469

471470
const ANDROID_WINDOW_TYPE_APPLICATION = 1;
@@ -574,42 +573,84 @@ function hasDescendantOcclusionEvidence(node: AndroidNode, state: AndroidTreePru
574573
}
575574

576575
/**
577-
* Where a subtree visibly presents something: the bounding box of its agent targets and labelled
578-
* leaves. A full-screen debug overlay holding one floating icon presents only that icon, so it can
579-
* only hide what sits under the icon, never the whole app behind it (#1806).
576+
* Where a subtree visibly presents something: the boxes of its touch-consuming surfaces (touch
577+
* targets, scrollables), focus targets and labelled leaves. A full-screen debug overlay holding one
578+
* floating icon presents only that icon, so it can only hide what sits under the icon, never the
579+
* whole app behind it (#1806). The rects are kept apart rather than merged into one bounding box:
580+
* two controls in opposite corners present two corners, not the screen between them.
580581
*/
581582
function subtreeFootprint(node: AndroidNode, state: AndroidTreePruneState): AndroidFootprint {
582583
const cached = state.footprintMemo.get(node);
583584
if (cached !== undefined) return cached;
584-
let hasAgentTarget = isAgentTarget(node);
585-
let rect: Rect | null =
586-
(isAgentTarget(node) || isLabelledLeaf(node)) && hasPositiveRect(node) ? node.rect : null;
587-
for (const child of node.children) {
588-
if (child.visibleToUser === false) continue;
589-
const childFootprint = subtreeFootprint(child, state);
590-
hasAgentTarget ||= childFootprint.hasAgentTarget;
591-
rect = unionRect(rect, childFootprint.rect);
585+
let footprint: AndroidFootprint;
586+
if (presentsOwnBox(node) && hasPositiveRect(node)) {
587+
// Its box is presented as a whole; whatever it contains lies inside that box.
588+
footprint = { rects: [node.rect], hasAgentTarget: isAgentTarget(node) };
589+
} else {
590+
footprint = { rects: [], hasAgentTarget: isAgentTarget(node) };
591+
for (const child of node.children) {
592+
if (child.visibleToUser === false) continue;
593+
const childFootprint = subtreeFootprint(child, state);
594+
footprint.hasAgentTarget ||= childFootprint.hasAgentTarget;
595+
footprint.rects.push(...childFootprint.rects);
596+
}
592597
}
593-
const footprint = { rect, hasAgentTarget };
594598
state.footprintMemo.set(node, footprint);
595599
return footprint;
596600
}
597601

598-
function isLabelledLeaf(node: AndroidNode): boolean {
599-
return node.children.length === 0 && hasMeaningfulLabel(node);
602+
function presentsOwnBox(node: AndroidNode): boolean {
603+
return (
604+
isAgentTarget(node) ||
605+
node.scrollable === true ||
606+
(node.children.length === 0 && hasMeaningfulLabel(node))
607+
);
600608
}
601609

602-
function unionRect(left: Rect | null, right: Rect | null): Rect | null {
603-
if (!left) return right;
604-
if (!right) return left;
605-
const x = Math.min(left.x, right.x);
606-
const y = Math.min(left.y, right.y);
607-
return {
608-
x,
609-
y,
610-
width: Math.max(left.x + left.width, right.x + right.width) - x,
611-
height: Math.max(left.y + left.height, right.y + right.height) - y,
612-
};
610+
/** Fraction of the covered rects' union that lies under the covering rects' union. */
611+
function unionCoverage(coveringRects: Rect[], coveredRects: Rect[]): number {
612+
const xs = compressedEdges([...coveringRects, ...coveredRects], (rect) => [
613+
rect.x,
614+
rect.x + rect.width,
615+
]);
616+
const ys = compressedEdges([...coveringRects, ...coveredRects], (rect) => [
617+
rect.y,
618+
rect.y + rect.height,
619+
]);
620+
const covering = markCells(coveringRects, xs, ys);
621+
const covered = markCells(coveredRects, xs, ys);
622+
let coveredArea = 0;
623+
let overlapArea = 0;
624+
for (let column = 0; column < xs.length - 1; column += 1) {
625+
const width = xs[column + 1]! - xs[column]!;
626+
for (let row = 0; row < ys.length - 1; row += 1) {
627+
const cell = column * (ys.length - 1) + row;
628+
if (!covered[cell]) continue;
629+
const area = width * (ys[row + 1]! - ys[row]!);
630+
coveredArea += area;
631+
if (covering[cell]) overlapArea += area;
632+
}
633+
}
634+
return coveredArea <= 0 ? 0 : overlapArea / coveredArea;
635+
}
636+
637+
function compressedEdges(rects: Rect[], edgesOf: (rect: Rect) => [number, number]): number[] {
638+
return [...new Set(rects.flatMap(edgesOf))].sort((left, right) => left - right);
639+
}
640+
641+
function markCells(rects: Rect[], xs: number[], ys: number[]): Uint8Array {
642+
const rows = ys.length - 1;
643+
const cells = new Uint8Array((xs.length - 1) * rows);
644+
for (const rect of rects) {
645+
const firstColumn = xs.indexOf(rect.x);
646+
const lastColumn = xs.indexOf(rect.x + rect.width);
647+
const firstRow = ys.indexOf(rect.y);
648+
const lastRow = ys.indexOf(rect.y + rect.height);
649+
for (let column = firstColumn; column < lastColumn; column += 1) {
650+
cells.fill(1, column * rows + firstRow, column * rows + lastRow);
651+
}
652+
}
653+
return cells;
613654
}
614655

615656
/**
@@ -663,9 +704,10 @@ function shouldKeepAndroidSibling(
663704
}
664705

665706
/**
666-
* Covered means the sibling's presented content lies under the candidate's presented content.
667-
* Comparing footprints rather than boxes lets two stacked screens with the same layout margins
668-
* still register as covered, while a sparse overlay never condemns a rich screen.
707+
* Covered means the sibling's presented content lies under the candidate's presented content, by
708+
* actual overlapped area. Comparing footprints rather than boxes lets two stacked screens with the
709+
* same layout margins still register as covered, while a sparse overlay never condemns a rich
710+
* screen however far apart its controls sit.
669711
*/
670712
function isCoveredByHigherDrawingOrderSibling(
671713
node: AndroidNode,
@@ -675,12 +717,13 @@ function isCoveredByHigherDrawingOrderSibling(
675717
if (node.visibleToUser === false || node.drawingOrder === undefined || !hasPositiveRect(node)) {
676718
return false;
677719
}
678-
const coveredRect = subtreeFootprint(node, state).rect ?? node.rect;
720+
const footprint = subtreeFootprint(node, state).rects;
721+
const coveredRects = footprint.length > 0 ? footprint : [node.rect];
679722
for (const candidate of coveringCandidates) {
680723
if (candidate.node === node || candidate.drawingOrder <= node.drawingOrder) {
681724
continue;
682725
}
683-
if (rectCoverage(candidate.footprint, coveredRect) >= 0.9) {
726+
if (unionCoverage(candidate.footprint, coveredRects) >= 0.9) {
684727
return true;
685728
}
686729
}
@@ -704,8 +747,8 @@ function coveringCandidateOf(
704747
if (!hasDirectOcclusionEvidence(node) && !hasDescendantOcclusionEvidence(node, state)) {
705748
return null;
706749
}
707-
const footprint = subtreeFootprint(node, state).rect;
708-
return footprint ? { node, drawingOrder, footprint } : null;
750+
const footprint = subtreeFootprint(node, state).rects;
751+
return footprint.length > 0 ? { node, drawingOrder, footprint } : null;
709752
}
710753

711754
function hasMeaningfulLabel(node: AndroidNode): boolean {
@@ -717,12 +760,6 @@ function hasPositiveRect(node: AndroidNode): node is AndroidNode & { rect: Rect
717760
return Boolean(node.rect && node.rect.width > 0 && node.rect.height > 0);
718761
}
719762

720-
function rectCoverage(coveringRect: Rect, targetRect: Rect): number {
721-
const targetArea = targetRect.width * targetRect.height;
722-
if (targetArea <= 0) return 0;
723-
return intersectArea(coveringRect, targetRect) / targetArea;
724-
}
725-
726763
function applyAndroidScrollActionHints(root: AndroidUiHierarchy): void {
727764
const stack = [...root.children];
728765
while (stack.length > 0) {

0 commit comments

Comments
 (0)