cmodule AModule {
  switchable S input = "STATICALAFLATTENLISTOFPAIRSLPAIRALLAOUTEMPTYLISTLLFORPAIRAPUNNULLLOUTADDPAOUTADDPBRETOUT";
  switchable S words = "ret ll ls static out list pair pairs flatten null of if else while for";
  
  S firstResult;
  transient BigInt totalCombinations;

  // basically immutable (we make a new copy for every step)
  // to allow evaluating states in parallel and in any order
  class GreedySplitIntoWordsCI_Multi implements IF0<Either<Iterable<GreedySplitIntoWordsCI_Multi>, LS>> {
    S s; // the input to be split
    TreeSet<S> wordsSet;
    Map<Int> longestMatchMap;
    int i = 0, last = 0;
    ReverseChain<S> out;
    
    *() {}
    *(S *s, Cl<S> words) {
      wordsSet = asCISet(words);
      longestMatchMap = new AutoMap<Int>(i -> dontPrint("longest match at " + i + ": ", lengthOfLongestPrefixInCISet(substring(s, i), wordsSet)));
    }
    
    Cl<S> wordsAtPosition(int i) {
      int longestMatch = longestMatchMap.get(i);
      ret mapNonNulls(countBackwardsTo1(longestMatch), matchLength -> {
        S word = substring(s, i, i+matchLength);
        ret contains(wordsSet, word) ? word : null;
      });
    }
      
    // either we return some choices or a final result
    Either<Iterable<GreedySplitIntoWordsCI_Multi>, LS> get() {
      if (i >= l(s)) ret done(); // done with input
      ret eitherA(listPlus(map(wordsAtPosition(i), wordMatched -> {
        GreedySplitIntoWordsCI_Multi clone = shallowClone(this, new GreedySplitIntoWordsCI_Multi);
        clone.flush();
        clone.i = clone.last = i+l(wordMatched);
        clone.out = revChainPlus(clone.out, substring(s, i, clone.i));
        ret clone;
      }), getVar(() -> {
        GreedySplitIntoWordsCI_Multi clone = shallowClone(this, new GreedySplitIntoWordsCI_Multi);
        clone.i++;
        ret clone;
      })));
    }

    Either<Iterable<GreedySplitIntoWordsCI_Multi>, LS> done() {
      flush();
      ret eitherB(asList(out));
    }
    
    S unflushed() { ret substring(s, last, i); }

    void flush {
      if (i <= last) ret;
      // modifying this object in spite of convention
      out = revChainPlus(out, unflushed());
      last = i;
    }
    
    toString { ret asList(out) + prependIfNempty("|", unflushed()) + ", " + i + "/" + l(s); }
    
    S sentence() { ret joinNemptiesWithSpace(listPlus(asList(out), unflushed())); }
  }
  
  GreedySplitIntoWordsCI_Multi root() {
    ret new GreedySplitIntoWordsCI_Multi(input, splitAtSpace(words));
  }
  
  visual northAndCenterWithMargins(
    jvstackWithSpacing(
      withLabel("Total combinations:", dm_label totalCombinations()),
      withLabel("Preferred result:", dm_label firstResult())),
    jDynamicEitherTree(root(),
      valueToText := (IF1<Either<GreedySplitIntoWordsCI_Multi, LS>, S>) x
        -> isEitherA(x) ? eitherAOpt(x).sentence() + "..." : joinWithSpace(eitherBOpt(x))));

  start-thread {
    dm_reloadOnFieldChange('words, 'input);
    time {
      print("First result: " + setField(firstResult := joinWithSpace(getFirstResultOfEitherTree(root()!))));
    }
    
    GreedySplitIntoWordsCI_Multi root = root();
    // We should subtract combinationsAtPosition(i-l(word)) for each word because I think it is counted twice
    setField(totalCombinations := combinationsForPositionalParser(
      l(input), i -> listPlus(lambdaMap l(root.wordsAtPosition(i)), 1), debug := true);
  }
}

Began life as a copy of #1028153