Page Menu
Home
WickedGov Phorge
Search
Configure Global Search
Log In
Files
F7436052
ve.dm.TreeCursor.js
No One
Temporary
Actions
View File
Edit File
Delete File
View Transforms
Subscribe
Flag For Later
Award Token
Size
7 KB
Referenced Files
None
Subscribers
None
ve.dm.TreeCursor.js
View Options
/*!
* VisualEditor DataModel TreeCursor class
*
* @copyright See AUTHORS.txt
*/
// TODO identify a core of "trusted" code that is guaranteed to detect tree invalidation.
// Probably needs: removeNode insertNode removeText insertText
/**
* DataModel TreeCursor - a tree walker that tracks the path to the current position.
*
* @class
*
* @constructor
* @param {ve.dm.Node} root A document node or a branch root within which to walk
* @param {ve.dm.Node[]} liveIgnoreNodes Live array of nodes to ignore (cross without counting)
* @param {number} [linearOffset] The first linear model offset inside root; default 0
*/
ve
.
dm
.
TreeCursor
=
function
VeDmTreeCursor
(
root
,
liveIgnoreNodes
,
linearOffset
)
{
this
.
root
=
root
;
this
.
liveIgnoreNodes
=
liveIgnoreNodes
;
this
.
path
=
[];
this
.
offset
=
0
;
this
.
nodes
=
[
root
];
this
.
node
=
root
;
this
.
lastStep
=
null
;
if
(
linearOffset
===
undefined
)
{
linearOffset
=
0
;
}
this
.
linearOffset
=
linearOffset
;
};
/* Inheritance */
OO
.
initClass
(
ve
.
dm
.
TreeCursor
);
/* Methods */
/**
* Skip past ignored nodes and text node boundaries
*
* @param {number} [tooShort] Only step into text nodes longer than this
*/
ve
.
dm
.
TreeCursor
.
prototype
.
normalizeCursor
=
function
(
tooShort
)
{
if
(
!
this
.
node
)
{
return
;
}
if
(
tooShort
===
undefined
)
{
tooShort
=
-
1
;
}
// If at the end of a text node, step out
if
(
this
.
node
.
type
===
'text'
&&
this
.
offset
===
this
.
node
.
length
)
{
this
.
nodes
.
pop
();
this
.
node
=
this
.
nodes
[
this
.
nodes
.
length
-
1
];
this
.
offset
=
this
.
path
.
pop
()
+
1
;
}
this
.
crossIgnoredNodes
();
let
item
;
// If at the start of long enough text node, step in
if
(
this
.
node
.
hasChildren
()
&&
(
item
=
this
.
node
.
children
[
this
.
offset
]
)
&&
item
.
type
===
'text'
&&
item
.
length
>
tooShort
)
{
this
.
node
=
item
;
this
.
nodes
.
push
(
item
);
this
.
path
.
push
(
this
.
offset
);
this
.
offset
=
0
;
}
};
/**
* Cross any immediately following nodes that are in liveIgnoreNodes
*/
ve
.
dm
.
TreeCursor
.
prototype
.
crossIgnoredNodes
=
function
()
{
let
parent
,
nextSibling
;
if
(
this
.
node
&&
this
.
node
.
type
===
'text'
&&
this
.
offset
===
this
.
node
.
length
&&
(
parent
=
this
.
nodes
[
this
.
nodes
.
length
-
2
]
)
&&
(
nextSibling
=
parent
.
children
[
this
.
path
[
this
.
path
.
length
-
1
]
+
1
]
)
&&
this
.
liveIgnoreNodes
.
includes
(
nextSibling
)
)
{
// At the end of a text node and the next node is ignored
this
.
stepOut
();
}
const
len
=
(
this
.
node
&&
this
.
node
.
hasChildren
()
&&
this
.
node
.
children
.
length
)
||
0
;
let
item
;
while
(
this
.
offset
<
len
&&
(
item
=
this
.
node
.
children
[
this
.
offset
]
)
&&
this
.
liveIgnoreNodes
.
includes
(
item
)
)
{
this
.
offset
++
;
this
.
linearOffset
+=
item
.
getOuterLength
();
}
};
/**
* Validate this.linearOffset against this.node and this.offset
*
* TODO: Improve the unit tests, then move this method to the unit testing framework
*
* @throws {Error} If this.linearOffset does not match this.node and this.offset
*/
ve
.
dm
.
TreeCursor
.
prototype
.
checkLinearOffset
=
function
()
{
let
expected
=
this
.
node
.
getOffset
();
if
(
this
.
node
.
type
===
'text'
)
{
expected
+=
this
.
offset
;
}
else
{
if
(
this
.
node
!==
this
.
root
)
{
// Add 1 for the open tag
expected
+=
1
;
}
if
(
this
.
node
.
hasChildren
()
)
{
// Add the outer length of each crossed child
this
.
node
.
children
.
slice
(
0
,
this
.
offset
).
forEach
(
(
child
)
=>
{
expected
+=
child
.
getOuterLength
();
}
);
}
}
if
(
expected
!==
this
.
linearOffset
)
{
throw
new
Error
(
'Linear offset does not match tree position'
);
}
};
/**
* @typedef {Object} Step
* @memberof ve.dm.TreeCursor
* @property {string} type open|close|cross|crosstext
* @property {number} length Linear length of the step (integer >= 1)
* @property {number[]} path Offset path from the root to the node containing the stepped item
* @property {ve.dm.Node|null} node The node containing the stepped item
* @property {number} offset The offset of the stepped item within its parent
* @property {number} [offsetLength] Number of characters 'crosstext' passed
* @property {ve.dm.Node} [item] The node stepped into/out of/across (absent for 'crosstext')
*/
/**
* Take a single step in the walk, consuming no more than a given linear model length
*
* A "single step" means either stepping across text content, or stepping over a node, or
* stepping into/out of a non-text node. (Steps into/out of text nodes happen transparently)
*
* See https://phabricator.wikimedia.org/T162762 for the algorithm
*
* @param {number} maxLength Maximum linear model length to step over (integer >= 1)
* @return {ve.dm.TreeCursor.Step|null} The type of step taken, or null if there are no more steps
*/
ve
.
dm
.
TreeCursor
.
prototype
.
stepAtMost
=
function
(
maxLength
)
{
if
(
!
this
.
node
)
{
this
.
lastStep
=
null
;
return
null
;
}
// On very large pages this is a performance bottleneck, so only run in tests
if
(
ve
.
test
)
{
this
.
checkLinearOffset
();
}
this
.
normalizeCursor
(
maxLength
);
let
length
,
step
;
if
(
this
.
node
.
type
===
'text'
)
{
// We cannot be the end, because we just normalized
length
=
Math
.
min
(
maxLength
,
this
.
node
.
length
-
this
.
offset
);
step
=
{
type
:
'crosstext'
,
length
:
length
,
path
:
this
.
path
.
slice
(),
node
:
this
.
node
,
offset
:
this
.
offset
,
offsetLength
:
length
};
this
.
offset
+=
step
.
length
;
this
.
lastStep
=
step
;
this
.
linearOffset
+=
length
;
return
step
;
}
// Else not a text node
const
childLength
=
this
.
node
.
hasChildren
()
?
this
.
node
.
children
.
length
:
0
;
if
(
this
.
offset
>
childLength
)
{
throw
new
Error
(
'Offset '
+
this
.
offset
+
' > childLength '
+
childLength
);
}
if
(
this
.
offset
===
childLength
)
{
return
this
.
stepOut
();
}
// Else there are unpassed child nodes
const
item
=
this
.
node
.
children
[
this
.
offset
];
if
(
item
.
getOuterLength
()
>
maxLength
)
{
return
this
.
stepIn
();
}
// Else step across this item
length
=
item
.
getOuterLength
();
step
=
{
type
:
'cross'
,
length
:
length
,
path
:
this
.
path
.
slice
(),
node
:
this
.
node
,
offset
:
this
.
offset
,
item
:
item
};
this
.
offset
++
;
this
.
lastStep
=
step
;
this
.
linearOffset
+=
length
;
return
step
;
};
/**
* Step into the next node
*
* @return {Object} The step
*/
ve
.
dm
.
TreeCursor
.
prototype
.
stepIn
=
function
()
{
if
(
this
.
node
.
type
===
'text'
||
!
this
.
node
.
hasChildren
()
||
this
.
offset
>=
this
.
node
.
children
.
length
)
{
throw
new
Error
(
'No node to step into'
);
}
const
item
=
this
.
node
.
children
[
this
.
offset
];
const
length
=
item
.
type
===
'text'
?
0
:
1
;
const
step
=
{
type
:
'open'
,
length
:
length
,
path
:
this
.
path
.
slice
(),
node
:
this
.
node
,
offset
:
this
.
offset
,
item
:
item
};
this
.
path
.
push
(
this
.
offset
);
this
.
nodes
.
push
(
item
);
this
.
node
=
item
;
this
.
offset
=
0
;
this
.
lastStep
=
step
;
this
.
linearOffset
+=
length
;
return
step
;
};
/**
* Step out of the current node (skipping past any uncrossed children or text within)
*
* @return {Object|null} The step
*/
ve
.
dm
.
TreeCursor
.
prototype
.
stepOut
=
function
()
{
const
priorOffset
=
this
.
offset
;
const
item
=
this
.
nodes
.
pop
();
this
.
node
=
this
.
nodes
[
this
.
nodes
.
length
-
1
];
this
.
offset
=
this
.
path
.
pop
();
if
(
this
.
node
===
undefined
)
{
// Stepped out of the root
this
.
lastStep
=
null
;
return
null
;
}
if
(
item
.
type
===
'text'
)
{
this
.
linearOffset
+=
item
.
getLength
()
-
priorOffset
;
}
else
{
if
(
item
.
hasChildren
()
)
{
// Increase linearOffset by the length of each child
item
.
children
.
slice
(
priorOffset
).
forEach
(
(
child
)
=>
{
this
.
linearOffset
+=
child
.
getOuterLength
();
}
);
}
// Increase linearOffset for the close tag
this
.
linearOffset
++
;
}
const
step
=
{
type
:
'close'
,
length
:
item
.
type
===
'text'
?
0
:
1
,
path
:
this
.
path
.
slice
(),
node
:
this
.
node
,
offset
:
this
.
offset
,
item
:
item
};
this
.
offset
++
;
this
.
lastStep
=
step
;
return
step
;
};
File Metadata
Details
Attached
Mime Type
text/plain
Expires
Sun, Nov 22, 13:14 (2 h, 39 m ago)
Storage Engine
local-disk
Storage Format
Raw Data
Storage Handle
12/3c/9793d39d496983b7af41ebf10cdc
Default Alt Text
ve.dm.TreeCursor.js (7 KB)
Attached To
Mode
rMWPROD MediaWiki Production
Attached
Detach File
Event Timeline
Log In to Comment