Use StringSubstitutor from Apache Commons Text.

Dependency import

Import the Apache commons text dependency using maven as bellow:

Copy<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-text</artifactId>
    <version>1.10.0</version>
</dependency>

Example

CopyMap<String, String> valuesMap = new HashMap<String, String>();
valuesMap.put("animal", "quick brown fox");
valuesMap.put("target", "lazy dog");
String templateString = "The ${animal} jumped over the ${target}.";
StringSubstitutor sub = new StringSubstitutor(valuesMap);
String resolvedString = sub.replace(templateString);

The compile concept produced incorrect results for me. When I run your code the template does not produce the correct results. For the input parameters:

final Map<String,String> parms = new HashMap<>();
Stream.of("USER_NAME", "USER_PHONE", "USER_EMAIL", "LOGIN_URL")
      .forEach(tag -> parms.put(tag, tag));

I would expect the input String:

"Dear {{USER_NAME}},\n\n" +
"According to our records, your phone number is {{USER_PHONE}} and " +
"your e-mail address is {{USER_EMAIL}}.  If this is incorrect, please " +
"go to {{LOGIN_URL}} and update your contact information."

to produce:

Dear USER_NAME,

According to our records, your phone number is USER_PHONE and your e-mail address is USER_EMAIL.  If this is incorrect, please go to LOGIN_URL and update your contact information.

But, instead, it produces:

Dear USER_NAMEAccording to our records, your phone number is USER_PHONE and your e-mail address is USER_EMAIL.  If this is incorrect, please go to LOGIN_URL and update your contact information.

I have looked through the code, and I am not sure why it is dropping the newlines, and the comma-punctuation after "USER_NAME".

I looked through the TemplateCompile code, and while I like that you use a Pattern/Matcher to parse the template, the actual loop structure is really complicated. You shoe-horn the process in to a for-loop, when a while-loop would be much better. Additionally, you use a complicated double-matching named-group regular expression, when a single-matching one would be more than adequate.

I particularly dislike the rest variable, and how it is used.

I wonder if this complicated regex logic is the cause of the broken output?

I wrote a "competing" code block, and I also chose regex to parse the template, but my loop is very different:

private static final Pattern token = Pattern.compile("\\{\\{(\\w+)\\}\\}");

public static Template compile(String text) {

    Matcher mat = token.matcher(text);

    int last = 0;

    while (mat.find()) {
        // the non-token text is from the last match end,
        // to this match start
        final String constant = text.substring(last, mat.start());
        // this token's key is the regex group
        final String key = mat.group(1);

        // do stuff with the text and subsequent token
        ....

        last = mat.end();
    }
    final String tail = text.substring(last);
    if (!tail.isEmpty()) {
        // do something with trailing text after last token.
        ....
    }

}

A while loop on the Matcher.find() result is the natural loop constraint.

Instead of compiling the code down, I used an array of text injectors to perform the write. Some injectors inject a constant value, others inject a lookup value from the Parameters. I was able to reduce your class down to much simpler constructs, with no code abstraction and compilation, etc. From a readability and maintenance perspective I believe it is clearly better:

public class MonkeyFix implements Template {

    @FunctionalInterface
    private interface Injector {
        String get(Map<String,String> params);
    }

    private static final Pattern token = Pattern.compile("\\{\\{(\\w+)\\}\\}");

    public static Template compile(final String text) {
        final Matcher mat = token.matcher(text);
        final List<Injector> sequence = new ArrayList<>();
        int last = 0;

        while (mat.find()) {
            final String constant = text.substring(last, mat.start());
            final String key = mat.group(1);

            sequence.add(params -> constant);
            sequence.add(params -> params.get(key));

            last = mat.end();
        }

        final String tail = text.substring(last);
        if (!tail.isEmpty()) {
            sequence.add(params -> tail);
        }

        return new MonkeyFix(sequence.toArray(new Injector[sequence.size()]));
    }

    private final Injector[] sequence;

    public MonkeyFix(Injector[] sequence) {
        this.sequence = sequence;
    }

    @Override
    public void write(Writer out, Map<String, String> params) throws IOException {
        for (Injector lu : sequence) {
            out.write(lu.get(params));
        }
    }

}

How about the performance, though?

I pout the code through my MicroBench suite, using the following code (I had to use a different validation string for your code, I called that one wrong ... ;-) :

public class TemplateMain {

    private static final String text = 
            "Dear {{USER_NAME}},\n\n" +
            "According to our records, your phone number is {{USER_PHONE}} and " +
            "your e-mail address is {{USER_EMAIL}}.  If this is incorrect, please " +
            "go to {{LOGIN_URL}} and update your contact information.";

    private static final Template inmemcomp = TemplateCompiler.compile(text);

    private static final Template monkeyfix = MonkeyFix.compile(text);

    private static final String inMemFunc(Template t, Map<String, String> params) {
        StringWriter sw = new StringWriter();
        try {
            t.write(sw, params);
        } catch (IOException e) {
            e.printStackTrace();
        }
        return sw.toString();
    }

    public static void main(String[] args) {
        UUtils.setStandaloneLogging(Level.INFO);
        UBench bench = new UBench("Templating");
        final String expect = "Dear USER_NAME,\n\n" +
                "According to our records, your phone number is USER_PHONE and " +
                "your e-mail address is USER_EMAIL.  If this is incorrect, please " +
                "go to LOGIN_URL and update your contact information.";
        final String wrong = "Dear USER_NAMEAccording to our records, your phone number is USER_PHONE and your e-mail address is USER_EMAIL.  If this is incorrect, please go to LOGIN_URL and update your contact information.";

        System.out.println(expect);
        System.out.println(wrong);

        final Map<String,String> parms = new HashMap<>();
        Stream.of("USER_NAME", "USER_PHONE", "USER_EMAIL", "LOGIN_URL").forEach(tag -> parms.put(tag, tag));

        bench.addTask("InMemCompile", () -> inMemFunc(inmemcomp, parms), got -> wrong.equals(got));
        bench.addTask("MonkeyFix", () -> inMemFunc(monkeyfix, parms), got -> expect.equals(got));

        bench.press(10000).report();

    }
}

The results are inconclusive on my computer, sometimes your code wins, sometimes mine does. Regardless, they are both "fast enough", and the differences are marginal.

I really don't think you need to use a templating engine or anything like that for this. You can use the String.format method, like so:

String template = "Hello %s Please find attached %s which is due on %s";

String message = String.format(template, name, invoiceNumber, dueDate);