lt-proc -b explodes on a-zA-Z regexes + long input

[unhammer]

b.dix:

<?xml version="1.0" encoding="UTF-8"?>
<dictionary>
<alphabet/>
<sdefs>
  <sdef n="guess"       c="Guesser"/>
</sdefs>

<pardefs>
<pardef n="a-zA-Z+">
  <e><re>[a-zA-Z]+</re></e>
</pardef>
</pardefs>

<section id="regex" type="standard">
        <e><par n="a-zA-Z+"/><i><s n="guess"/></i></e>
</section>
</dictionary>

$ lt-comp lr b.dix b.bin
regex@standard 3 105

$ echo '^HYPERSENSITIVITET<guess>$' | \time lt-proc -b b.bin
^HYPERSENSITIVITET<guess>/HYPERSENSITIVITET<guess>$
0.18user 0.04system 0:00.22elapsed 100%CPU (0avgtext+0avgdata 141920maxresident)k
0inputs+0outputs (0major+36137minor)pagefaults 0swaps

$ echo '^HYPERSENSITIVITETSTING<guess>$' | \time lt-proc -b b.bin
^HYPERSENSITIVITETSTING<guess>/HYPERSENSITIVITETSTING<guess>$
6.64user 1.49system 0:08.13elapsed 100%CPU (0avgtext+0avgdata 5240216maxresident)k
0inputs+0outputs (0major+1492655minor)pagefaults 0swaps

$ echo '^HYPERSENSITIVITETSTINGEN<guess>$' | \time lt-proc -b b.bin
^HYPERSENSITIVITETSTINGEN<guess>/HYPERSENSITIVITETSTINGEN<guess>$
27.51user 6.36system 0:33.88elapsed 99%CPU (0avgtext+0avgdata 22483912maxresident)k
0inputs+0outputs (0major+6540906minor)pagefaults 0swaps

if I remove A-Z from the regex, it's fine again, but I get wrong lemmas (e.g. FooBar becomes FooBar<guess>/Foobar<guess>, wrong capitalisation on the output)

[mr-martian]

Each time you step by an uppercase letter, it also steps by the lowercase version, so for an N-letter word, you have 2^N states when you reach the end.

[unhammer]

Oh the reason we only see one result is that if it's not dictionaryCase, we apply input casing to each result, and they're merged into one.

$ echo BADGER | lt-proc --dictionary-case a.bin
^BADGER/baDGER<guess>/bADGEr<guess>/bADGeR<guess>/bADGer<guess>/bADgER<guess>/bADgEr<guess>/bADgeR<guess>/bADger<guess>/bAdGER<guess>/bAdGEr<guess>/bAdGeR<guess>/bAdGer<guess>/bAdgER<guess>/bAdgEr<guess>/bAdgeR<guess>/bAdger<guess>/bADGER<guess>/baDGEr<guess>/baDGeR<guess>/baDGer<guess>/baDgER<guess>/baDgEr<guess>/baDgeR<guess>/baDger<guess>/badGER<guess>/badGEr<guess>/badGeR<guess>/badGer<guess>/badgER<guess>/badgEr<guess>/badgeR<guess>/badger<guess>/BaDGER<guess>/BADGEr<guess>/BADGeR<guess>/BADGer<guess>/BADgER<guess>/BADgEr<guess>/BADgeR<guess>/BADger<guess>/BAdGER<guess>/BAdGEr<guess>/BAdGeR<guess>/BAdGer<guess>/BAdgER<guess>/BAdgEr<guess>/BAdgeR<guess>/BAdger<guess>/BADGER<guess>/BaDGEr<guess>/BaDGeR<guess>/BaDGer<guess>/BaDgER<guess>/BaDgEr<guess>/BaDgeR<guess>/BaDger<guess>/BadGER<guess>/BadGEr<guess>/BadGeR<guess>/BadGer<guess>/BadgER<guess>/BadgEr<guess>/BadgeR<guess>/Badger<guess>$

I feel like it should be possible to do some filtering earlier. We're looping back to the same FST-node over and over again: but fst_processor doesn't just keep track of the Node, but also the sequence leading up to it:

  struct TNodeState
  {
    Node *where;
    std::vector<std::pair<int, double>> *sequence;
    // a state is "dirty" if it was introduced at runtime (case variants, etc.)
    bool dirty;

Would it be possible to filter out ones where the node is the same and the last part of the sequence differs?

Alternatively when doing step/apply, could we check if the result is the same, and never use the tolower(val) (alt) if they end up in the same Node? It wouldn't be a general solution, but would help in the common case of a-zA-Z.

[unhammer]

Another option, which I think we should do regardless (to prevent me from DoS-ing our servers with bad regexes), is have a max state size. As soon as you go over about 2^16 states you can feel the slowdown for a single (long, uppercase) word (and you're bound to be getting so many results it's mostly garbage), so perhaps simply

diff --git a/lttoolbox/fst_processor.cc b/lttoolbox/fst_processor.cc
index 1466ffb..98caea7 100644
--- a/lttoolbox/fst_processor.cc
+++ b/lttoolbox/fst_processor.cc
@@ -1087,7 +1087,7 @@ FSTProcessor::analysis(InputFile& input, UFILE *output)
     }
     else
     {
-      current_state.step_case(val, caseSensitive);
+      current_state.step_case(val, caseSensitive || current_state.size() >= 65536);
     }
 
     if(current_state.size() != 0)
@@ -2277,7 +2277,7 @@ FSTProcessor::bilingual(InputFile& input, UFILE *output, GenerationMode mode)
       }
       if(current_state.size() != 0)
       {
-        current_state.step_case(val, caseSensitive);
+        current_state.step_case(val, caseSensitive || current_state.size() >= 65536);
       }
       if(current_state.isFinal(all_finals))
       {

Maybe with a warning the first time we reach that size.

[unhammer]

when doing step/apply, could we check if the result is the same, and never use the tolower(val) (alt) if they end up in the same Node?

@ftyers can you imagine anywhere we would want a lowercase character (on the output-side) if input was upper and upper is possible and we end up in the same FST node? (That'd be like if you had both "iphone" and "iPhone" in your dix and user wrote "iPhone" – analysis would now only give "iPhone" instead of both. I would see that as a good thing, but maybe there are use-cases for having both.)

[mr-martian]

Another thing we could do is within State::step() record each (src, trg) pair for the main symbol and then skip any alt step that would be between the same pair. (Though we'd probably want to check whether that noticeably slowed anything down.)