Repository navigation
Replies: 2 comments
|
ファイルリストでmigemo使えたら良いなあと漠然と投稿したが、考慮すべき問題が多く大変そうですね |
|
Following on from §3.4 and §4 — a threading angle I left out of the original post. Work this slow clearly belongs off the UI thread, and if it runs asynchronously then roughly 100ms of latency is tolerable, which relaxes the constraint considerably. Two things complicate that, though. Queries are CPU-bound, not I/O-boundI'd assumed Migemo would be doing file access per query. It isn't, at least not in pymigemo: That matters because a Python worker thread only truly parallelises I/O. For CPU-bound pure-Python work the GIL serialises execution, so the worker competes with the UI thread rather than running beside it. Measured with a 60Hz tick loop standing in for UI work, while a worker builds the regexes for
So it is not a 150ms freeze — the GIL switches every 5ms by default, so the UI thread keeps getting scheduled. But jitter rises to about one frame's worth at 60Hz. Acceptable for a keystroke-driven TUI redraw; worth knowing it isn't free. This adds an axis to §4.1 in C/Migemo's favour. A ctypes call into the C library releases the GIL for its duration, giving genuine parallelism rather than interleaving. What a 100ms budget does to the length gateAgainst a 100ms budget, using the numbers from §3.3 and §3.5:
So the 3-character gate from §3.4 survives, but its justification shifts. It's no longer about avoiding a UI freeze; it's about not queuing work whose result will be stale before it lands. Two-phase resultsRunning Migemo asynchronously means the search delivers results twice: substring matches immediately, Migemo matches merged in when they arrive. That's a good property — the UI never waits — but three things need specifying.
The dictionary load is worth putting on that same worker, since the 49ms is genuine I/O and does release the GIL. Two more for the list in §8
|
Uh oh!
There was an error while loading. Please reload this page.
Related: #302 (migemo対応), #283 (日本語ファイル名 / Windows TUI)
#302 asks for Migemo support in incremental search. Several implementation choices here are genuinely open, so I'd rather work them out in a Discussion than decide them inside the Issue.
1. What the request actually covers
#302 says: Windows 11, Migemo support wanted in incremental search, with a link to C/Migemo 1.6.0.
Three things follow from that:
F) only — not Filter (;) or content search (Shift-G)I'll treat that as the baseline scope and handle expansion separately in §5.
2. Why this is actionable now
Until recently this feature would have been hard to evaluate. #283 reported that Japanese filenames rendered incorrectly in the Windows terminal build —
あいうえお.txtdisplayed asあ い う.txt, extensions overflowing the column, path separators disappearing. Migemo exists to find Japanese filenames, so on that build a user could have matched a file and still not been able to read the row.That's fixed, which removes the blocker.
One thing to confirm: whether the fix is in a release the #302 reporter can actually install, or only on
main. If it hasn't shipped yet, we'd be asking them to validate Migemo on a build where they still can't read the results.3. Question A: how Migemo gets activated
3.1 The cfiler approach, and where it went wrong
cfiler (内骨格) used a two-stage design: switch I-Search into Migemo mode from the settings menu, and then apply Migemo only when the pattern mixes upper and lower case, otherwise search the literal alphabet.
cfiler's Issue #9 shows this backfiring. A user tried to find
無題.pngby typingmudai, got nothing, and had to writeMudai. Turning a mode on and then having it not fire is a confusing experience, and worth not repeating.3.2 We may not need a mode or a heuristic at all
The regex Migemo returns includes the original romaji as one of its alternatives:
So leaving Migemo on permanently doesn't break plain substring matching. cfiler's case heuristic is, in principle, unnecessary.
The one real conflict is globbing.
FileListManager.find_matchescurrently wraps each token as*token*and runs it throughfnmatch, so explicit globs like*.pywork today. Migemo returns a regex, and the two semantics collide.A clean split: patterns containing metacharacters (
*?[) keep the current behaviour; patterns without them go through Migemo.3.3 But short queries are slow (measured)
Time to generate the regex, using pymigemo (see §4):
c), 1439ms (k), 1213ms (t)Dictionary load is 49ms and total process RSS is about 14MB. Matching with the generated regex is cheap — 1.3ms across 10,000 filenames. The cost is entirely in regex generation, and it's concentrated in short queries.
Incremental search always starts at one character, so a naive integration freezes for two seconds on the first keystroke.
3.4 Proposal: a minimum query length gate
Two romaji characters is roughly one kana, so there's little to gain from Migemo at that length anyway. The user never sees a mode, and the cfiler #9 confusion can't occur. The numbers support it: at 3+ characters, p90 is 5.4ms, which keeps up with typing.
percol solves the same problem with a
minimum_query_lengthsetting.4. Question B: which engine
4.1 The two candidates
4.2 Known problems with pymigemo (found while testing)
It fails to start on LP64 systems. The dictionary reader uses
array.array('L').Lis 4 bytes on Windows (LLP64) but 8 bytes on macOS and Linux (LP64), while the file format assumes 4 — so it dies withEOFError. Changing it to'I'fixes it, one line.This doesn't reproduce on Windows. On the migemo対応 #302 reporter's platform, pymigemo works as shipped. macOS and Linux are where it breaks.
A one-character query of
sraisesIndexErrorinbitvector.next_clear_bit. The other 25 letters are clean. I only tested single characters, so I can't yet say whether multi-character strings starting withsare safe. The length gate in §3.4 means one-character queries never reach Migemo anyway.Module name collision. pymigemo imports as
migemo, which is exactly the name atzm's PyMigemo (a C/Migemo binding) uses. In an environment with both installed, which one we get is undefined.4.3 The distribution constraint
XeFM ships through three channels: Microsoft Store, macOS dmg, and PyPI/pipx.
4.4 If we go with pymigemo
Upstream is 3 stars, 5 commits, and no release in four years, so we can't count on external maintenance. That said, the author is active on GitHub, so sending a fix is realistic.
The catch is timing. Even if a PR merges,
pip install pymigemokeeps serving the broken 0.0.1 until oguna cuts a new release, so we still can't declare it as a dependency.That suggests doing both:
For (b) there are two options.
Vendor it — pull it in as
xefm/_migemo/. BSD-3-Clause, so including the copyright notice is sufficient. The code is roughly 30KB excluding the dictionary. This also eliminates the module name collision from §4.2-3. The cost is that XeFM formally takes on maintenance of a Migemo implementation.Patch at runtime — bug 1 can be fixed by swapping the
arrayattribute on themigemocompactdictionarymodule, about five lines, and it becomes inert automatically once upstream fixes it. The downsides are that we have to guard the name collision ourselves (verifying that what we imported is actually oguna's build) and pinpymigemo==0.0.1.Either choice is reversible later, so starting with the lighter one and revisiting costs us nothing.
5. Question C: how far to apply it
#302 only asks about incremental search, but several adjacent surfaces exist:
;Filter — closely tied, since isearch results feed into filter historyShift-Fprogressive filename searchShift-Gcontent search — expensive to regex-ify, and demand is unclearViewerISearch)filter_list_dialog(favorites / jump / drives)Extending across these naturally calls for a matcher strategy abstraction in
FileListManager— essentially rebuilding what cfiler had as [exact / substring / fuzzy / Migemo].That's a broader change than Migemo itself, so the prior question is whether to keep this scoped to isearch or use it as the entry point for reorganising matching generally.
6. Implementation notes
query()plusre.compile()runs on every keystroke; cache per pattern.query()in try/except and drop to plain substring matching. That absorbs unknown bugs like §4.2-2 without user-visible breakage.search_matchesis a set of indices), so no change is needed. Substring-level highlighting would require match spans.7. Limits of these measurements
The numbers in §3.3 and §4.2 come from a single run in a Linux container, with random ASCII strings rather than realistic romaji. They need re-measuring on Windows and macOS hardware, particularly against the Python bundled with the desktop builds.
Since the #302 reporter is on Windows, that thread may be a good place to ask for help with the Windows numbers.
8. What I'd like to settle
Comments welcome.
All reactions