static Set<S> gazelle_allSyntacticPatternsFromInput(S input) {
  Chain<S> tokens = toChain(javaTokC(input));
  new LinkedHashSet<S> out;
  gazelle_allSyntacticPatternsFromInput_collect(null, tokens, out);
  ret out;
}

svoid gazelle_allSyntacticPatternsFromInput_collect(ReverseChain<S> prefix, Chain<S> tokens, Set<S> out) {
  ping();
  if (empty(tokens)) {
    out.add(joinWithSpace(asList(prefix)));
    ret;
  }
  
  // output one token
  gazelle_allSyntacticPatternsFromInput_collect(
    chainPlus(prefix, first(tokens)),
    dropFirst(tokens), out);
    
  // output * unless last token output was a *
  // consume between 1 and all tokens
  if (!eq(last(prefix), "*")) {
    ReverseChain<S> prefix2 = chainPlus(prefix, "*");
    Chain<S> tokens2 = tokens;
    while (!empty(tokens2)) {
      tokens2 = dropFirst(tokens2);
      gazelle_allSyntacticPatternsFromInput_collect(prefix2, tokens2, out);
    }
  }
}