Page Menu
Home
WickedGov Phorge
Search
Configure Global Search
Log In
Files
F7414879
GenReplFst.php
No One
Temporary
Actions
Download File
Edit File
Delete File
View Transforms
Subscribe
Flag For Later
Award Token
Size
15 KB
Referenced Files
None
Subscribers
None
GenReplFst.php
View Options
<?php
namespace
Wikimedia\LangConv\Construct
;
use
Wikimedia\Assert\Assert
;
/**
* GENerate a REPLacement string FST.
*
* Create an FST from a replacement string array (aka, as would be provided
* to `str_tr` or `ReplacementArray` in mediawiki core).
*/
class
GenReplFst
{
// This can be anything, as long as it is longer than 1 character
// (so it doesn't conflict w/ any of the single-character keys)
private
const
END_OF_STRING
=
'*END*'
;
// correlation of tree nodes to state machine states
private
const
STATE
=
'*STATE*'
;
// UTF-8 decode state: 0=first byte, 1/2/3=bytes remaining in char
private
const
UTF8STATE
=
'*UTF8STATE*'
;
// Character index of this tree node
private
const
INDEX
=
'*INDEX*'
;
/** @var array<int|string,int|string|array> */
private
$prefixTree
=
[];
/** @var MutableFST */
private
$fst
;
/** @var array */
private
$alphabet
;
/**
* Prefix to use on flag diacritics (so they are unique to this FST).
* @var string
*/
private
$fdPrefix
;
/**
* How many flag diacritic features are needed. At most one less than
* the longest string, but can be shorter.
* @var int
*/
private
$maxLookahead
;
/**
* Cache of shift machines.
* @var array
*/
private
$shiftCache
=
[];
/**
* Add each letter in the given word to our alphabet.
* @param array &$alphabet
* @param string $word
*/
private
static
function
addAlphabet
(
array
&
$alphabet
,
string
$word
):
void
{
for
(
$i
=
0
;
$i
<
strlen
(
$word
);
$i
++
)
{
$alphabet
[
ord
(
$word
[
$i
]
)]
=
true
;
}
}
/**
* Add the given string (the substring of $from starting from $index) to
* the prefix tree $tree, along with the conversion output $to.
* @param array<int|string,string|array> &$tree
* @param string $from
* @param int $index
* @param int $utf8state 0=first byte, 1/2/3 = bytes remaining in char
* @param string $to
* @param bool $suppressUtf8Checks Whether to suppress the checks that the
* $from string is complete utf8.
*/
private
static
function
addEntry
(
array
&
$tree
,
string
$from
,
int
$index
,
int
$utf8state
,
string
$to
,
bool
$suppressUtf8Checks
=
false
):
void
{
$c
=
ord
(
$from
[
$index
]
);
if
(
!
isset
(
$tree
[
$c
]
)
)
{
$tree
[
$c
]
=
[];
}
if
(
!
isset
(
$tree
[
self
::
UTF8STATE
]
)
)
{
$tree
[
self
::
UTF8STATE
]
=
$utf8state
;
}
Assert
::
invariant
(
isset
(
$tree
[
self
::
UTF8STATE
]
)
&&
$tree
[
self
::
UTF8STATE
]
===
$utf8state
,
"Should never happen"
);
if
(
!
isset
(
$tree
[
self
::
INDEX
]
)
)
{
$tree
[
self
::
INDEX
]
=
$index
;
}
Assert
::
invariant
(
isset
(
$tree
[
self
::
INDEX
]
)
&&
$tree
[
self
::
INDEX
]
===
$index
,
"Should never happen"
);
$nextUtf8State
=
self
::
nextUtf8State
(
$utf8state
,
$c
);
$nextIndex
=
$index
+
1
;
if
(
$nextIndex
<
strlen
(
$from
)
)
{
self
::
addEntry
(
$tree
[
$c
],
$from
,
$nextIndex
,
$nextUtf8State
,
$to
);
}
else
{
if
(
!
$suppressUtf8Checks
)
{
Assert
::
invariant
(
$nextUtf8State
===
0
,
"Bad UTF-8 in input"
);
}
$tree
[
$c
][
self
::
UTF8STATE
]
=
$nextUtf8State
;
$tree
[
$c
][
self
::
INDEX
]
=
$nextIndex
;
$tree
[
$c
][
self
::
END_OF_STRING
]
=
$to
;
}
}
/**
* Return the next UTF-8 state, given the current state and the
* current character.
* @param int $utf8state 0=first byte, 1/2/3 = bytes remaining in char
* @param int $c The current character
* @return int The next UTF-8 state
*/
private
static
function
nextUtf8State
(
int
$utf8state
,
int
$c
):
int
{
if
(
$utf8state
===
0
)
{
if
(
$c
<=
0x7F
)
{
return
0
;
}
elseif
(
$c
<=
0xDF
)
{
Assert
::
invariant
(
$c
>=
0xC0
,
"Bad UTF-8 in input"
);
return
1
;
}
elseif
(
$c
<=
0xEF
)
{
Assert
::
invariant
(
$c
>=
0xE0
,
"Bad UTF-8 in input"
);
return
2
;
}
elseif
(
$c
<=
0xF7
)
{
Assert
::
invariant
(
$c
>=
0xF0
,
"Bad UTF-8 in input"
);
return
3
;
}
}
else
{
return
$utf8state
-
1
;
}
// @phan-suppress-next-line PhanImpossibleCondition
Assert
::
invariant
(
false
,
"Bad UTF-8 in input"
);
}
/**
* Return the subset of the given alphabet appropriate for the current
* UTF-8 state.
* @param int $utf8state 0=first byte, 1/2/3 = bytes remaining in char
* @return \Generator<int>
*/
private
function
utf8alphabet
(
int
$utf8state
)
{
foreach
(
$this
->
alphabet
as
$c
)
{
if
(
$c
>=
0x80
&&
$c
<=
0xBF
)
{
// UTF-8 continuation character
if
(
$utf8state
!==
0
)
{
yield
$c
;
}
}
else
{
if
(
$utf8state
===
0
)
{
yield
$c
;
}
}
}
}
/**
* Split a given string into the first utf8 char, and "everything else".
* @param string $s
* @return string[]
*/
private
static
function
splitFirstUtf8Char
(
string
$s
)
{
$utf8state
=
0
;
$i
=
0
;
while
(
$i
<
strlen
(
$s
)
)
{
$c
=
ord
(
$s
[
$i
]
);
$utf8state
=
self
::
nextUtf8State
(
$utf8state
,
$c
);
$i
+=
1
;
if
(
$utf8state
===
0
)
{
break
;
}
}
return
[
substr
(
$s
,
0
,
$i
),
substr
(
$s
,
$i
)
];
}
/**
* Return the name of a flag diacritic for matching character at a
* specified offset.
* @param string $type Flag diacritic operator: P/R/D/C/U
* @param int $offset Identifies the feature
* @param int|null $value The value to set/test (optional)
* @return string The symbol name for the given flag diacritic operation
*/
private
function
flagDiacritic
(
string
$type
,
int
$offset
,
?
int
$value
=
null
):
string
{
$str
=
"@$type."
.
$this
->
fdPrefix
.
"char$offset"
;
if
(
$value
!==
null
)
{
$str
.=
"."
;
if
(
$value
>=
0
)
{
$str
.=
self
::
byteToHex
(
$value
);
}
else
{
$str
.=
"UNK"
;
}
}
return
$str
.
"@"
;
}
/**
* Add a flag diacritic edge between $from and $to. By convention the
* flag diacritic is on both the upper and lower slots of the edge.
* @param State $from The source of the new edge
* @param State $to The destination of the new edge
* @param string $type The flag diacritic operator
* @param int $offset The flag diacritic feature
* @param int|null $value The flag diacritic value (optional)
*/
private
function
addFdEdge
(
State
$from
,
State
$to
,
string
$type
,
int
$offset
,
?
int
$value
=
null
):
void
{
$fdName
=
$this
->
flagDiacritic
(
$type
,
$offset
,
$value
);
$from
->
addEdge
(
$fdName
,
$fdName
,
$to
);
}
/**
* Add two flag diacritic edge between $from and $to. By convention the
* flag diacritics are on both the upper and lower slots of the edge.
* @param State $from The source of the new edges
* @param State $to The destination of the new edges
* @param string $type1 The first flag diacritic operator
* @param int $offset1 The first flag diacritic feature
* @param int|null $value1 The first flag diacritic value (optional)
* @param string $type2 The second flag diacritic operator
* @param int $offset2 The second flag diacritic feature
* @param int|null $value2 The second flag diacritic value (optional)
*/
private
function
addFdEdgePair
(
State
$from
,
State
$to
,
string
$type1
,
int
$offset1
,
?
int
$value1
,
string
$type2
,
int
$offset2
,
?
int
$value2
):
void
{
$n
=
$this
->
fst
->
newState
();
$this
->
addFdEdge
(
$from
,
$n
,
$type1
,
$offset1
,
$value1
);
$this
->
addFdEdge
(
$n
,
$to
,
$type2
,
$offset2
,
$value2
);
}
/**
* Add edges from state $from corresponding to the prefix tree $tree,
* given the $lastMatch and the characters seen since then, $seen.
* @param State $from
* @param array &$tree
* @param ?string $lastMatch (null if we haven't seen a match)
* @param string $seen characters seen since last match
*/
private
function
buildState
(
State
$from
,
array
&
$tree
,
?
string
$lastMatch
,
string
$seen
):
void
{
$tree
[
self
::
STATE
]
=
$from
;
$index
=
$tree
[
self
::
INDEX
];
$utf8state
=
$tree
[
self
::
UTF8STATE
];
if
(
$index
<
$this
->
maxLookahead
)
{
$noBufState
=
$this
->
fst
->
newState
();
$this
->
addFdEdge
(
$from
,
$noBufState
,
'D'
,
$index
);
}
else
{
$noBufState
=
$from
;
}
$noMatchState
=
$this
->
fst
->
newState
();
if
(
isset
(
$tree
[
self
::
END_OF_STRING
]
)
)
{
$lastMatch
=
$tree
[
self
::
END_OF_STRING
];
$seen
=
''
;
}
foreach
(
$this
->
utf8alphabet
(
$utf8state
)
as
$c
)
{
if
(
isset
(
$tree
[
$c
]
)
)
{
$nextSeen
=
$seen
.
chr
(
$c
);
$n
=
$this
->
fst
->
newState
();
$noBufState
->
addEdge
(
self
::
byteToHex
(
$c
),
MutableFST
::
EPSILON
,
$n
);
if
(
$index
<
$this
->
maxLookahead
)
{
$this
->
addFdEdge
(
$from
,
$n
,
'R'
,
$index
,
$c
);
}
$nn
=
$this
->
fst
->
newState
();
$this
->
addFdEdge
(
$n
,
$nn
,
'P'
,
strlen
(
$seen
),
$c
);
$this
->
buildState
(
$nn
,
$tree
[
$c
],
$lastMatch
,
$nextSeen
);
}
else
{
Assert
::
invariant
(
$index
!==
0
,
"fake single-char matches should always exist"
);
$n
=
$this
->
fst
->
newState
();
$noBufState
->
addEdge
(
self
::
byteToHex
(
$c
),
MutableFST
::
EPSILON
,
$n
);
if
(
$index
<
$this
->
maxLookahead
)
{
$this
->
addFdEdge
(
$from
,
$n
,
'R'
,
$index
,
$c
);
}
Assert
::
invariant
(
strlen
(
$seen
)
<
$this
->
maxLookahead
,
"Max lookahead should always account for seen"
);
$this
->
addFdEdge
(
$n
,
$noMatchState
,
'P'
,
strlen
(
$seen
),
$c
);
}
}
// our first state must echo all continuation characters, since
// the anythingState transitions there and we don't know what
// utf8 state IDENTITY will leave us in. (The characters not in
// our alphabet could consist of 1-/2-/3-/4-byte sequences.)
if
(
$index
===
0
)
{
foreach
(
self
::
utf8alphabet
(
1
/*continuation chars*/
)
as
$c
)
{
$nextSeen
=
$seen
.
chr
(
$c
);
$n
=
$this
->
fst
->
newState
();
$noBufState
->
addEdge
(
self
::
byteToHex
(
$c
),
MutableFST
::
EPSILON
,
$n
);
if
(
$index
<
$this
->
maxLookahead
)
{
$this
->
addFdEdge
(
$from
,
$n
,
'R'
,
$index
,
$c
);
}
$fakeTree
=
[];
$fakeTree
[
self
::
UTF8STATE
]
=
1
;
$fakeTree
[
self
::
INDEX
]
=
$index
+
1
;
$fakeTree
[
self
::
END_OF_STRING
]
=
chr
(
$c
);
$this
->
buildState
(
$n
,
$fakeTree
,
$lastMatch
,
$nextSeen
);
}
}
// "anything else"
$anythingElse
=
$this
->
fst
->
newState
();
$noBufState
->
addEdge
(
MutableFST
::
EPSILON
,
MutableFST
::
EPSILON
,
$anythingElse
);
if
(
$index
!==
0
)
{
$this
->
addFdEdge
(
$from
,
$anythingElse
,
'R'
,
$index
,
-
1
);
}
$this
->
addFdEdge
(
$anythingElse
,
$noMatchState
,
'P'
,
strlen
(
$seen
),
-
1
);
// Emit the last match
if
(
$lastMatch
!==
null
)
{
$noMatchState
=
$this
->
emit
(
$noMatchState
,
MutableFST
::
EPSILON
,
$lastMatch
);
}
// Shift over queued input
for
(
$i
=
$index
+
1
;
true
;
$i
++
)
{
$j
=
strlen
(
$seen
)
+
(
$i
-
$index
);
$key
=
$i
.
':'
.
$j
;
if
(
isset
(
$this
->
shiftCache
[
$key
]
)
)
{
$noMatchState
->
addEdge
(
MutableFST
::
EPSILON
,
MutableFST
::
EPSILON
,
$this
->
shiftCache
[
$key
]
);
return
;
}
$this
->
shiftCache
[
$key
]
=
$noMatchState
;
if
(
$i
<
$this
->
maxLookahead
)
{
$n
=
$this
->
fst
->
newState
();
$this
->
addFdEdge
(
$noMatchState
,
$n
,
'D'
,
$i
);
}
else
{
$n
=
$noMatchState
;
}
for
(
$k
=
$j
;
$k
<
$i
&&
$k
<
$this
->
maxLookahead
;
$k
++
)
{
$nn
=
$this
->
fst
->
newState
();
$this
->
addFdEdge
(
$n
,
$nn
,
'C'
,
$k
);
$n
=
$nn
;
}
$n
->
addEdge
(
MutableFST
::
EPSILON
,
MutableFST
::
EPSILON
,
$this
->
fst
->
getStartState
()
);
if
(
!(
$i
<
$this
->
maxLookahead
)
)
{
break
;
}
$n
=
$this
->
fst
->
newState
();
$this
->
addFdEdgePair
(
$noMatchState
,
$n
,
'R'
,
$i
,
-
1
,
'P'
,
$j
,
-
1
);
foreach
(
$this
->
alphabet
as
$c
)
{
$this
->
addFdEdgePair
(
$noMatchState
,
$n
,
'R'
,
$i
,
$c
,
'P'
,
$j
,
$c
);
}
$noMatchState
=
$n
;
}
}
/**
* Chain states together from $fromState to emit $emitStr.
* @param State $fromState
* @param string $fromChar
* @param string $emitStr
* @return State the resulting state (after the string has been emitted)
*/
private
function
emit
(
State
$fromState
,
string
$fromChar
,
string
$emitStr
):
State
{
if
(
strlen
(
$emitStr
)
===
0
&&
$fromChar
!==
MutableFST
::
EPSILON
)
{
$n
=
$this
->
fst
->
newState
();
$fromState
->
addEdge
(
$fromChar
,
MutableFST
::
EPSILON
,
$n
);
return
$n
;
}
for
(
$i
=
0
;
$i
<
strlen
(
$emitStr
);
$i
++
)
{
$c
=
ord
(
$emitStr
[
$i
]
);
$n
=
$this
->
fst
->
newState
();
$fromState
->
addEdge
(
$fromChar
,
self
::
byteToHex
(
$c
),
$n
);
$fromState
=
$n
;
$fromChar
=
MutableFST
::
EPSILON
;
}
return
$fromState
;
}
/**
* Private helper function: convert a numeric byte to the string
* token we use in the FST.
* @param int $byte
* @return string Token
*/
private
static
function
byteToHex
(
int
$byte
):
string
{
$s
=
strtoupper
(
dechex
(
$byte
)
);
while
(
strlen
(
$s
)
<
2
)
{
$s
=
"0$s"
;
}
return
$s
;
}
/**
* Private helper function: convert a UTF-8 string byte-by-byte into
* an array of tokens.
* @param string $s
* @return string[]
*/
private
static
function
stringToTokens
(
string
$s
):
array
{
$toks
=
[];
for
(
$i
=
0
;
$i
<
strlen
(
$s
);
$i
++
)
{
$toks
[]
=
self
::
byteToHex
(
ord
(
$s
[
$i
]
)
);
}
return
$toks
;
}
/**
* Private helper function: convert an array of tokens into
* a UTF-8 string.
* @param string[] $toks
* @return string
*/
private
static
function
tokensToString
(
array
$toks
):
string
{
$s
=
''
;
foreach
(
$toks
as
$token
)
{
if
(
strlen
(
$token
)
===
2
)
{
$s
.=
chr
(
hexdec
(
$token
)
);
}
else
{
// shouldn't happen, but handy for debugging if it does
$s
.=
$token
;
}
}
return
$s
;
}
/**
* For testing: apply the resulting FST to the given input string.
* @param string $input
* @return string[] The possible outputs.
*/
public
function
applyDown
(
string
$input
):
array
{
// convert input to byte tokens
$result
=
$this
->
fst
->
applyDown
(
self
::
stringToTokens
(
$input
)
);
return
array_map
(
function
(
$toks
)
{
return
self
::
tokensToString
(
$toks
);
},
$result
);
}
/**
* For testing: run the resulting FST "in reverse" against the given
* input string.
* @param string $input
* @return string[] The possible outputs.
*/
public
function
applyUp
(
string
$input
):
array
{
// convert input to byte tokens
$result
=
$this
->
fst
->
applyUp
(
self
::
stringToTokens
(
$input
)
);
return
array_map
(
function
(
$toks
)
{
return
self
::
tokensToString
(
$toks
);
},
$result
);
}
/**
* Convert the given $replacementTable (strtr-style) to an FST.
* @param string $name
* @param array<string,string> $replacementTable
* @param string $fdPrefix Flag diacritic feature prefix, for uniqueness
*/
public
function
__construct
(
string
$name
,
array
$replacementTable
,
string
$fdPrefix
=
''
)
{
$this
->
fdPrefix
=
$fdPrefix
;
$alphabet
=
[];
$longestWord
=
0
;
foreach
(
$replacementTable
as
$from
=>
$to
)
{
$longestWord
=
max
(
$longestWord
,
strlen
(
$from
)
);
self
::
addAlphabet
(
$alphabet
,
$from
);
self
::
addAlphabet
(
$alphabet
,
$to
);
self
::
addEntry
(
$this
->
prefixTree
,
$from
,
0
,
0
,
$to
);
}
// fake one character matches!
foreach
(
$alphabet
as
$sym
=>
$value
)
{
if
(
$sym
<
0x80
||
$sym
>
0xBF
)
{
// not continuation chars
self
::
addEntry
(
$this
->
prefixTree
,
chr
(
$sym
),
0
,
0
,
chr
(
$sym
),
true
);
}
}
$this
->
maxLookahead
=
$longestWord
-
1
;
// XXX could be shorter
$this
->
alphabet
=
array_keys
(
$alphabet
);
sort
(
$this
->
alphabet
,
SORT_NUMERIC
);
// ok, now we're ready to emit the FST
$this
->
fst
=
new
MutableFST
(
array_map
(
function
(
$n
)
{
return
self
::
byteToHex
(
$n
);
},
$this
->
alphabet
)
);
$anythingState
=
$this
->
fst
->
newState
();
$anything2State
=
$this
->
fst
->
newState
();
$anythingState
->
addEdge
(
MutableFST
::
UNKNOWN
,
MutableFST
::
IDENTITY
,
$anything2State
);
$this
->
addFdEdge
(
$this
->
fst
->
getStartState
(),
$anythingState
,
'R'
,
0
,
-
1
);
$this
->
addFdEdge
(
$anything2State
,
$this
->
fst
->
getStartState
(),
'C'
,
0
);
// The anything state could also be the end of the string
// (which for modelling purposes we can think of as a special
// "EOF" token not in the alphabet)
// Important that there are no outgoing edges from the $endState!
$endState
=
$this
->
fst
->
newState
();
$endState
->
isFinal
=
true
;
$anythingState
->
addEdge
(
MutableFST
::
EPSILON
,
MutableFST
::
EPSILON
,
$endState
);
// Create states corresponding to prefix tree nodes
$this
->
buildState
(
$this
->
fst
->
getStartState
(),
$this
->
prefixTree
,
null
,
''
);
// ok, done!
$this
->
fst
->
optimize
();
}
/**
* Write the FST to the given file handle in AT&T format.
* @param resource $handle
*/
public
function
writeATT
(
$handle
):
void
{
$this
->
fst
->
writeATT
(
$handle
);
}
}
File Metadata
Details
Attached
Mime Type
text/x-php
Expires
Sun, Nov 22, 01:52 (1 d, 14 h)
Storage Engine
local-disk
Storage Format
Raw Data
Storage Handle
02/92/867d4b47347a3a1858c4ae1fd8a4
Default Alt Text
GenReplFst.php (15 KB)
Attached To
Mode
rMWPROD MediaWiki Production
Attached
Detach File
Event Timeline
Log In to Comment