Skip to content

Commit c4298a6

Browse files
WebReflectionWebReflection
committed
working on JSON variant
1 parent c830d27 commit c4298a6

20 files changed

Lines changed: 371 additions & 239 deletions

‎src/constants.js‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
export const ARRAY = 1 << 0;
2+
export const ARIA = 1 << 1;
3+
export const ATTRIBUTE = 1 << 2;
4+
export const COMMENT = 1 << 3;
5+
export const COMPONENT = 1 << 4;
6+
export const DATA = 1 << 5;
7+
export const DIRECT = 1 << 6;
8+
export const DOTS = 1 << 7;
9+
export const EVENT = 1 << 8;
10+
export const KEY = 1 << 9;
11+
export const PROP = 1 << 10;
12+
export const TEXT = 1 << 11;
13+
export const TOGGLE = 1 << 12;
14+
export const UNSAFE = 1 << 13;
15+
export const REF = 1 << 14;
16+
17+
// COMPONENT flags
18+
export const COMPONENT_DIRECT = COMPONENT | DIRECT;
19+
export const COMPONENT_DOTS = COMPONENT | DOTS;
20+
export const COMPONENT_PROP = COMPONENT | PROP;
21+
22+
// ARRAY flags
23+
export const EVENT_ARRAY = EVENT | ARRAY;
24+
export const COMMENT_ARRAY = COMMENT | ARRAY;

‎src/dom/diff.js‎

Lines changed: 130 additions & 122 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,5 @@
1+
// @ts-check
2+
13
// @see https://github.com/WebReflection/udomdiff
24

35
/**
@@ -19,142 +21,148 @@
1921
*/
2022

2123
/**
22-
* @param {Node[]} a The list of current/live children
24+
* @param {Node[]} a The list of previous/current/live children
2325
* @param {Node[]} b The list of future children
2426
* @param {(entry: Node, action: number) => Node} get
2527
* The callback invoked per each entry related DOM operation.
26-
* @param {Node} [before] The optional node used as anchor to insert before.
27-
* @returns {Node[]} The same list of future children.
28+
* @param {Node} before The node used as anchor to insert before.
29+
* @returns
2830
*/
2931
export default (a, b, get, before) => {
30-
const parentNode = before.parentNode;
31-
const bLength = b.length;
32+
const parentNode = /** @type {Element} */(before.parentNode);
3233
let aEnd = a.length;
33-
let bEnd = bLength;
3434
let aStart = 0;
35-
let bStart = 0;
36-
let map = null;
37-
while (aStart < aEnd || bStart < bEnd) {
38-
// append head, tail, or nodes in between: fast path
39-
if (aEnd === aStart) {
40-
// we could be in a situation where the rest of nodes that
41-
// need to be added are not at the end, and in such case
42-
// the node to `insertBefore`, if the index is more than 0
43-
// must be retrieved, otherwise it's gonna be the first item.
44-
const node = bEnd < bLength ?
45-
(bStart ?
46-
(get(b[bStart - 1], -0).nextSibling) :
47-
get(b[bEnd], 0)) :
48-
before;
49-
while (bStart < bEnd)
50-
parentNode.insertBefore(get(b[bStart++], 1), node);
51-
}
52-
// remove head or tail: fast path
53-
else if (bEnd === bStart) {
54-
while (aStart < aEnd) {
55-
// remove the node only if it's unknown or not live
56-
if (!map || !map.has(a[aStart]))
57-
//@ts-ignore
58-
get(a[aStart], -1).remove();
35+
if (aStart === aEnd)
36+
parentNode.replaceChildren(...b);
37+
else {
38+
const bLength = b.length;
39+
let aEnd = a.length;
40+
let bEnd = bLength;
41+
let aStart = 0;
42+
let bStart = 0;
43+
let map;
44+
while (aStart < aEnd || bStart < bEnd) {
45+
// append head, tail, or nodes in between: fast path
46+
if (aEnd === aStart) {
47+
// we could be in a situation where the rest of nodes that
48+
// need to be added are not at the end, and in such case
49+
// the node to `insertBefore`, if the index is more than 0
50+
// must be retrieved, otherwise it's gonna be the first item.
51+
const node = bEnd < bLength ?
52+
(bStart ?
53+
(get(b[bStart - 1], -0).nextSibling) :
54+
get(b[bEnd], 0)) :
55+
before;
56+
while (bStart < bEnd)
57+
parentNode.insertBefore(get(b[bStart++], 1), node);
58+
}
59+
// remove head or tail: fast path
60+
else if (bEnd === bStart) {
61+
while (aStart < aEnd) {
62+
// remove the node only if it's unknown or not live
63+
if (!map?.has(a[aStart]))
64+
//@ts-ignore
65+
get(a[aStart], -1).remove();
66+
aStart++;
67+
}
68+
}
69+
// same node: fast path
70+
else if (a[aStart] === b[bStart]) {
5971
aStart++;
72+
bStart++;
6073
}
61-
}
62-
// same node: fast path
63-
else if (a[aStart] === b[bStart]) {
64-
aStart++;
65-
bStart++;
66-
}
67-
// same tail: fast path
68-
else if (a[aEnd - 1] === b[bEnd - 1]) {
69-
aEnd--;
70-
bEnd--;
71-
}
72-
// The once here single last swap "fast path" has been removed in v1.1.0
73-
// https://github.com/WebReflection/udomdiff/blob/single-final-swap/esm/index.js#L69-L85
74-
// reverse swap: also fast path
75-
else if (
76-
a[aStart] === b[bEnd - 1] &&
77-
b[bStart] === a[aEnd - 1]
78-
) {
79-
// this is a "shrink" operation that could happen in these cases:
80-
// [1, 2, 3, 4, 5]
81-
// [1, 4, 3, 2, 5]
82-
// or asymmetric too
83-
// [1, 2, 3, 4, 5]
84-
// [1, 2, 3, 5, 6, 4]
85-
const node = get(a[--aEnd], -0).nextSibling;
86-
parentNode.insertBefore(
87-
get(b[bStart++], 1),
88-
get(a[aStart++], -0).nextSibling
89-
);
90-
parentNode.insertBefore(get(b[--bEnd], 1), node);
91-
// mark the future index as identical (yeah, it's dirty, but cheap 👍)
92-
// The main reason to do this, is that when a[aEnd] will be reached,
93-
// the loop will likely be on the fast path, as identical to b[bEnd].
94-
// In the best case scenario, the next loop will skip the tail,
95-
// but in the worst one, this node will be considered as already
96-
// processed, bailing out pretty quickly from the map index check
97-
a[aEnd] = b[bEnd];
98-
}
99-
// map based fallback, "slow" path
100-
else {
101-
// the map requires an O(bEnd - bStart) operation once
102-
// to store all future nodes indexes for later purposes.
103-
// In the worst case scenario, this is a full O(N) cost,
104-
// and such scenario happens at least when all nodes are different,
105-
// but also if both first and last items of the lists are different
106-
if (!map) {
107-
map = new Map;
108-
let i = bStart;
109-
while (i < bEnd)
110-
map.set(b[i], i++);
74+
// same tail: fast path
75+
else if (a[aEnd - 1] === b[bEnd - 1]) {
76+
aEnd--;
77+
bEnd--;
11178
}
79+
// The once here single last swap "fast path" has been removed in v1.1.0
80+
// https://github.com/WebReflection/udomdiff/blob/single-final-swap/esm/index.js#L69-L85
81+
// reverse swap: also fast path
82+
else if (
83+
a[aStart] === b[bEnd - 1] &&
84+
b[bStart] === a[aEnd - 1]
85+
) {
86+
// this is a "shrink" operation that could happen in these cases:
87+
// [1, 2, 3, 4, 5]
88+
// [1, 4, 3, 2, 5]
89+
// or asymmetric too
90+
// [1, 2, 3, 4, 5]
91+
// [1, 2, 3, 5, 6, 4]
92+
const node = get(a[--aEnd], -0).nextSibling;
93+
parentNode.insertBefore(
94+
get(b[bStart++], 1),
95+
get(a[aStart++], -0).nextSibling
96+
);
97+
parentNode.insertBefore(get(b[--bEnd], 1), node);
98+
// mark the future index as identical (yeah, it's dirty, but cheap 👍)
99+
// The main reason to do this, is that when a[aEnd] will be reached,
100+
// the loop will likely be on the fast path, as identical to b[bEnd].
101+
// In the best case scenario, the next loop will skip the tail,
102+
// but in the worst one, this node will be considered as already
103+
// processed, bailing out pretty quickly from the map index check
104+
a[aEnd] = b[bEnd];
105+
}
106+
// map based fallback, "slow" path
107+
else {
108+
// the map requires an O(bEnd - bStart) operation once
109+
// to store all future nodes indexes for later purposes.
110+
// In the worst case scenario, this is a full O(N) cost,
111+
// and such scenario happens at least when all nodes are different,
112+
// but also if both first and last items of the lists are different
113+
if (!map) {
114+
map = new Map;
115+
let i = bStart;
116+
while (i < bEnd)
117+
map.set(b[i], i++);
118+
}
112119

113-
const index = map.get(a[aStart]) ?? -1;
120+
const index = map.get(a[aStart]) ?? -1;
114121

115-
// this node has no meaning in the future list, so it's more than safe
116-
// to remove it, and check the next live node out instead, meaning
117-
// that only the live list index should be forwarded
118-
//@ts-ignore
119-
if (index < 0) get(a[aStart++], -1).remove();
120-
// it's a future node, hence it needs some handling
121-
else {
122-
// if it's not already processed, look on demand for the next LCS
123-
if (bStart < index && index < bEnd) {
124-
let i = aStart;
125-
// counts the amount of nodes that are the same in the future
126-
let sequence = 1;
127-
while (++i < aEnd && i < bEnd && map.get(a[i]) === (index + sequence))
128-
sequence++;
129-
// effort decision here: if the sequence is longer than replaces
130-
// needed to reach such sequence, which would brings again this loop
131-
// to the fast path, prepend the difference before a sequence,
132-
// and move only the future list index forward, so that aStart
133-
// and bStart will be aligned again, hence on the fast path.
134-
// An example considering aStart and bStart are both 0:
135-
// a: [1, 2, 3, 4]
136-
// b: [7, 1, 2, 3, 6]
137-
// this would place 7 before 1 and, from that time on, 1, 2, and 3
138-
// will be processed at zero cost
139-
if (sequence > (index - bStart)) {
140-
const node = get(a[aStart], 0);
141-
while (bStart < index)
142-
parentNode.insertBefore(get(b[bStart++], 1), node);
143-
}
144-
// if the effort wasn't good enough, fallback to a replace,
145-
// moving both source and target indexes forward, hoping that some
146-
// similar node will be found later on, to go back to the fast path
147-
else {
148-
// TODO: benchmark replaceWith instead
149-
parentNode.replaceChild(
150-
get(b[bStart++], 1),
151-
get(a[aStart++], -1)
152-
);
122+
// this node has no meaning in the future list, so it's more than safe
123+
// to remove it, and check the next live node out instead, meaning
124+
// that only the live list index should be forwarded
125+
//@ts-ignore
126+
if (index < 0) get(a[aStart++], -1).remove();
127+
// it's a future node, hence it needs some handling
128+
else {
129+
// if it's not already processed, look on demand for the next LCS
130+
if (bStart < index && index < bEnd) {
131+
let i = aStart;
132+
// counts the amount of nodes that are the same in the future
133+
let sequence = 1;
134+
while (++i < aEnd && i < bEnd && map.get(a[i]) === (index + sequence))
135+
sequence++;
136+
// effort decision here: if the sequence is longer than replaces
137+
// needed to reach such sequence, which would brings again this loop
138+
// to the fast path, prepend the difference before a sequence,
139+
// and move only the future list index forward, so that aStart
140+
// and bStart will be aligned again, hence on the fast path.
141+
// An example considering aStart and bStart are both 0:
142+
// a: [1, 2, 3, 4]
143+
// b: [7, 1, 2, 3, 6]
144+
// this would place 7 before 1 and, from that time on, 1, 2, and 3
145+
// will be processed at zero cost
146+
if (sequence > (index - bStart)) {
147+
const node = get(a[aStart], 0);
148+
while (bStart < index)
149+
parentNode.insertBefore(get(b[bStart++], 1), node);
150+
}
151+
// if the effort wasn't good enough, fallback to a replace,
152+
// moving both source and target indexes forward, hoping that some
153+
// similar node will be found later on, to go back to the fast path
154+
else {
155+
// TODO: benchmark replaceWith instead
156+
parentNode.replaceChild(
157+
get(b[bStart++], 1),
158+
get(a[aStart++], -1)
159+
);
160+
}
153161
}
162+
// otherwise move the source forward, 'cause there's nothing to do
163+
else
164+
aStart++;
154165
}
155-
// otherwise move the source forward, 'cause there's nothing to do
156-
else
157-
aStart++;
158166
}
159167
}
160168
}

‎src/dom/ish.js‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -54,6 +54,22 @@ export const prop = (node, name, value) => {
5454
node.props[name] = value;
5555
};
5656

57+
export const replaceWith = (source, target) => {
58+
const { children } = source.parent;
59+
children[children.indexOf(source)] = target;
60+
target.parent = source.parent;
61+
source.parent = null;
62+
};
63+
64+
export const remove = node => {
65+
const { parent } = node;
66+
if (parent) {
67+
const { children } = parent;
68+
children.splice(children.indexOf(node), 1);
69+
node.parent = null;
70+
}
71+
};
72+
5773
const addJSON = (value, comp, json) => {
5874
if (value !== comp) json.push(value);
5975
};

‎src/dom/node.js‎

Lines changed: 8 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,14 @@ import props from './props.js';
88
// import { isArray } from '../utils.js';
99
import { children } from './ish.js';
1010
import { set as setRefs } from './ref.js';
11-
import { ARRAY, COMMENT, COMPONENT, KEY, REF } from './update.js';
11+
12+
import {
13+
ARRAY,
14+
COMMENT,
15+
COMPONENT,
16+
KEY,
17+
REF,
18+
} from '../constants.js';
1219

1320
/** @typedef {globalThis.Element | globalThis.HTMLElement | globalThis.SVGSVGElement | globalThis.DocumentFragment} Container */
1421

‎src/dom/process.js‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,8 @@ import {
1111

1212
import parser from '../parser/index.js';
1313
import templates from './templates.js';
14-
import { isKeyed, fragment, update, pdt } from './update.js';
14+
import { isKeyed, fragment, update } from './update.js';
15+
import { pdt } from '../utils.js';
1516

1617
const parse = parser({
1718
Comment,

‎src/dom/rabbit.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@ import resolve from './resolve.js';
77
import { children } from './ish.js';
88
import { isArray } from '../utils.js';
99
import { PersistentFragment, diffFragment, nodes } from './persistent-fragment.js';
10-
import { ARRAY, COMMENT, COMPONENT, EVENT, KEY, REF } from './update.js';
10+
import { ARRAY, COMMENT, COMPONENT, EVENT, KEY, REF } from '../constants.js';
1111

1212
import { _get as getDirect, _set as setDirect } from './direct.js';
1313

‎src/dom/resolve.js‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,8 @@
11
import DEBUG from '../debug.js';
22

33
const tree = DEBUG ?
4-
((node, i) => i < 0 ? node?.content : node?.childNodes?.[i]) :
5-
((node, i) => i < 0 ? node.content : node.childNodes[i])
4+
((node, i) => node?.childNodes?.[i]) :
5+
((node, i) => node.childNodes[i])
66
;
77

88
export default (root, path) => path.reduceRight(tree, root);

0 commit comments

Comments
 (0)