Summary

This is an alternative to #17557 which aims to implement t-strings in a more efficient way (less code size), leveraging the existing f-string parser in the lexer. It includes:

• t-string parsing in py/lexer.c
• new built-in __template__() function to construct t-string objects
• new built-in Template and Interpolation classes which implement all the functionality from PEP 750
• new built-in string module with templatelib sub-module, which contains the classes Template and Interpolation

This PR is built upon #18588.

The way it works is that an input t-string like:

t"hello {name:5}"

is converted character-by-character by the lexer/tokenizer to:

__template__(("hello ", "",), name, "name", None, "5")

(For reference, if it were an f-string it would be converted to "hello {:5}".format(name).)

Compared to #17557 which costs about +7400 bytes on stm32, this implementation costs +2844 bytes.

This is still a work-in-progress. It implements most of the t-string functionality including nested t-strings and f-strings, but there are a few corner cases yet to tidy up. I don't see any show stoppers though, and code size should hopefully not grow much more either.

Testing

All 16 tests from #17557 have been added here. So far 11 of them pass, and 1 is no longer relevant (testing runtime overflow limit which is no longer there).

Trade-offs and Alternatives

Being an alternative to #17557, it shows a different way to achieve the same end result. #17557 starts up a new parser instance each time a t-string is encountered and recursively parses the t-string, whereas the implementation here just transforms the input characters. After all, t-strings (and f-strings) are really just syntactic sugar.

This adds code size, but if t-strings are not used then there is very little execution overhead, all of which is contained to the lexer.

The changes to py/lexer.c are mildly complex, but not really much more complex than the existing f-string logic. It's just a different way of transforming the input stream.