Repository: CrossGL/crosstl
Issue category: Performance Issue

Optimize Lexer Performance with Token Caching and Pattern Combining
## Description  
The lexer can be optimized to improve performance and reduce memory usage. This task focuses on implementing token caching, combining similar regex patterns, and caching compiled patterns.  

### Proposed Changes  
1. **Token Caching**  
   - Add a `token_cache` dictionary to reuse frequently used tokens.  
   - Introduce a `_get_cached_token` helper method to manage the cache.  

2. **Combined Regex Patterns**  
   - Group similar patterns (e.g., numbers, vectors, matrices) into combined regex patterns.  
   - Add a `COMBINED_PATTERNS` dictionary to simplify and speed up token matching.  

3. **Pattern Precompilation**  
   - Cache compiled regex patterns to avoid recompilation.  
   - Add a `_compile_patterns` method for one-time regex compilation and store patterns in `REGEX_CACHE`.  

## Files to Modify  
[crosstl/translator/lexer.py](https://github.com/CrossGL/crosstl/blob/main/crosstl/translator/lexer.py)  

---  

@NripeshN, I would love to work on this task. Let me know if it sounds good!  

<!-- BOT_STATE: {"assignee": "Swish78", "assigned_at": "2024-12-26T13:56:30.681969+00:00", "reminder_sent": false, "unassigned": false} -->


Functions to edit:
crosstl/translator/lexer.py:Lexer.tokenize
crosstl/translator/lexer.py:Lexer.__init__
Functions added: crosstl/translator/lexer.py:Lexer._compile_patterns
crosstl/translator/lexer.py:Lexer._get_cached_token

Patch:
diff --git a/crosstl/translator/lexer.py b/crosstl/translator/lexer.py
index e6540499..ac89f534 100644
--- a/crosstl/translator/lexer.py
+++ b/crosstl/translator/lexer.py
@@ -1,81 +1,82 @@
 import re
+from collections import OrderedDict
 
-TOKENS = [
-    ("COMMENT_SINGLE", r"//.*"),
-    ("COMMENT_MULTI", r"/\*[\s\S]*?\*/"),
-    ("SHADER", r"\bshader\b"),
-    ("VOID", r"\bvoid\b"),
-    ("STRUCT", r"\bstruct\b"),
-    ("CBUFFER", r"\bcbuffer\b"),
-    ("AT", r"\@"),
-    ("SAMPLER2D", r"\bsampler2D\b"),
-    ("SAMPLERCUBE", r"\bsamplerCube\b"),
-    ("VECTOR", r"\bvec[2-4]\b"),
-    ("MATRIX", r"\bmat[2-4]\b"),
-    ("BOOL", r"\bbool\b"),
-    ("VERTEX", r"\bvertex\b"),
-    ("FRAGMENT", r"\bfragment\b"),
-    ("FLOAT_NUMBER", r"\d*\.\d+|\d+\.\d*"),
-    ("FLOAT", r"\bfloat\b"),
-    ("INT", r"\bint\b"),
-    ("UINT", r"\buint\b"),
-    ("DOUBLE", r"\bdouble\b"),
-    ("SAMPLER", r"\bsampler\b"),
-    ("IDENTIFIER", r"[a-zA-Z_][a-zA-Z_0-9]*"),
-    ("ASSIGN_SHIFT_RIGHT", r">>="),
-    ("ASSIGN_SHIFT_LEFT", r"<<="),
-    ("NUMBER", r"\d+(\.\d+)?"),
-    ("LBRACE", r"\{"),
-    ("RBRACE", r"\}"),
-    ("LPAREN", r"\("),
-    ("RPAREN", r"\)"),
-    ("SEMICOLON", r";"),
-    ("COMMA", r","),
-    ("ASSIGN_ADD", r"\+="),
-    ("ASSIGN_SUB", r"-="),
-    ("ASSIGN_MUL", r"\*="),
-    ("ASSIGN_DIV", r"/="),
-    ("WHITESPACE", r"\s+"),
-    ("IF", r"\bif\b"),
-    ("ELSE", r"\belse\b"),
-    ("FOR", r"\bfor\b"),
-    ("RETURN", r"\breturn\b"),
-    ("BITWISE_SHIFT_LEFT", r"<<"),
-    ("BITWISE_SHIFT_RIGHT", r">>"),
-    ("LESS_EQUAL", r"<="),
-    ("GREATER_EQUAL", r">="),
-    ("GREATER_THAN", r">"),
-    ("LESS_THAN", r"<"),
-    ("INCREMENT", r"\+\+"),
-    ("DECREMENT", r"--"),
-    ("EQUAL", r"=="),
-    ("NOT_EQUAL", r"!="),
-    ("ASSIGN_AND", r"&="),
-    ("ASSIGN_OR", r"\|="),
-    ("ASSIGN_XOR", r"\^="),
-    ("LOGICAL_AND", r"&&"),
-    ("LOGICAL_OR", r"\|\|"),
-    ("NOT", r"!"),
-    ("ASSIGN_MOD", r"%="),
-    ("MOD", r"%"),
-    ("INCREMENT", r"\+\+"),
-    ("DECREMENT", r"\-\-"),
-    ("PLUS", r"\+"),
-    ("MINUS", r"-"),
-    ("MULTIPLY", r"\*"),
-    ("DIVIDE", r"/"),
-    ("DOT", r"\."),
-    ("EQUALS", r"="),
-    ("QUESTION", r"\?"),
-    ("COLON", r":"),
-    ("CONST", r"\bconst\b"),
-    ("BITWISE_AND", r"&"),
-    ("BITWISE_OR", r"\|"),
-    ("BITWISE_XOR", r"\^"),
-    ("BITWISE_NOT", r"~"),
-    ("shift_left", r"<<"),
-    ("shift_right", r">>"),
-]
+TOKENS = OrderedDict(
+    [
+        ("COMMENT_SINGLE", r"//.*"),
+        ("COMMENT_MULTI", r"/\*[\s\S]*?\*/"),
+        ("SHADER", r"\bshader\b"),
+        ("VOID", r"\bvoid\b"),
+        ("STRUCT", r"\bstruct\b"),
+        ("CBUFFER", r"\bcbuffer\b"),
+        ("AT", r"\@"),
+        ("SAMPLER2D", r"\bsampler2D\b"),
+        ("SAMPLERCUBE", r"\bsamplerCube\b"),
+        ("VECTOR", r"\bvec[2-4]\b"),
+        ("MATRIX", r"\bmat[2-4]\b"),
+        ("BOOL", r"\bbool\b"),
+        ("VERTEX", r"\bvertex\b"),
+        ("FRAGMENT", r"\bfragment\b"),
+        ("FLOAT_NUMBER", r"\d*\.\d+|\d+\.\d*"),
+        ("FLOAT", r"\bfloat\b"),
+        ("INT", r"\bint\b"),
+        ("UINT", r"\buint\b"),
+        ("DOUBLE", r"\bdouble\b"),
+        ("SAMPLER", r"\bsampler\b"),
+        ("IDENTIFIER", r"[a-zA-Z_][a-zA-Z_0-9]*"),
+        ("ASSIGN_SHIFT_RIGHT", r">>="),
+        ("ASSIGN_SHIFT_LEFT", r"<<="),
+        ("NUMBER", r"\d+(\.\d+)?"),
+        ("LBRACE", r"\{"),
+        ("RBRACE", r"\}"),
+        ("LPAREN", r"\("),
+        ("RPAREN", r"\)"),
+        ("SEMICOLON", r";"),
+        ("COMMA", r","),
+        ("ASSIGN_ADD", r"\+="),
+        ("ASSIGN_SUB", r"-="),
+        ("ASSIGN_MUL", r"\*="),
+        ("ASSIGN_DIV", r"/="),
+        ("WHITESPACE", r"\s+"),
+        ("IF", r"\bif\b"),
+        ("ELSE", r"\belse\b"),
+        ("FOR", r"\bfor\b"),
+        ("RETURN", r"\breturn\b"),
+        ("BITWISE_SHIFT_LEFT", r"<<"),
+        ("BITWISE_SHIFT_RIGHT", r">>"),
+        ("LESS_EQUAL", r"<="),
+        ("GREATER_EQUAL", r">="),
+        ("GREATER_THAN", r">"),
+        ("LESS_THAN", r"<"),
+        ("INCREMENT", r"\+\+"),
+        ("DECREMENT", r"--"),
+        ("EQUAL", r"=="),
+        ("NOT_EQUAL", r"!="),
+        ("ASSIGN_AND", r"&="),
+        ("ASSIGN_OR", r"\|="),
+        ("ASSIGN_XOR", r"\^="),
+        ("LOGICAL_AND", r"&&"),
+        ("LOGICAL_OR", r"\|\|"),
+        ("NOT", r"!"),
+        ("ASSIGN_MOD", r"%="),
+        ("MOD", r"%"),
+        ("INCREMENT", r"\+\+"),
+        ("DECREMENT", r"\-\-"),
+        ("PLUS", r"\+"),
+        ("MINUS", r"-"),
+        ("MULTIPLY", r"\*"),
+        ("DIVIDE", r"/"),
+        ("DOT", r"\."),
+        ("EQUALS", r"="),
+        ("QUESTION", r"\?"),
+        ("COLON", r":"),
+        ("CONST", r"\bconst\b"),
+        ("BITWISE_AND", r"&"),
+        ("BITWISE_OR", r"\|"),
+        ("BITWISE_XOR", r"\^"),
+        ("BITWISE_NOT", r"~"),
+    ]
+)
 
 KEYWORDS = {
     "shader": "SHADER",
@@ -91,46 +92,61 @@
 
 
 class Lexer:
-    """A simple lexer for the shader language
+    """A simple lexer for the shader language with optimizations
 
     This lexer tokenizes the input code into a list of tokens.
+    Includes optimizations:
+    - Token caching for frequently used tokens
+    - Combined regex patterns for similar tokens
+    - Precompiled regex patterns
 
     Attributes:
         code (str): The input code to tokenize
         tokens (list): A list of tokens generated from the input code
-
+        token_cache (dict): Cache for frequently used tokens
     """
 
     def __init__(self, code):
         self.code = code
         self.tokens = []
+        self.token_cache = {}
+        self.regex_cache = self._compile_patterns()
         self.tokenize()
 
-    def tokenize(self):
-        pos = 0
-        while pos < len(self.code):
-            match = None
-            for token_type, pattern in TOKENS:
-                regex = re.compile(pattern)
-                match = regex.match(self.code, pos)
-                if match:
-                    text = match.group(0)
-                    if token_type == "IDENTIFIER" and text in KEYWORDS:
-                        token_type = KEYWORDS[text]
-                    if token_type != "WHITESPACE":  # Ignore whitespace tokens
+    def _compile_patterns(self):
+        """Compile a single regex with named groups for all tokens."""
+        combined_pattern = "|".join(
+            f"(?P<{name}>{pattern})" for name, pattern in TOKENS.items()
+        )
+        return re.compile(combined_pattern)
 
-                        token = (token_type, text)
+    def _get_cached_token(self, text, token_type):
+        """Return a cached token tuple if possible."""
+        cache_key = (text, token_type)
+        if cache_key not in self.token_cache:
+            self.token_cache[cache_key] = (token_type, text)
+        return self.token_cache[cache_key]
 
-                        self.tokens.append(token)
-                    pos = match.end(0)
-                    break
-            if not match:
-                unmatched_char = self.code[pos]
-                highlighted_code = (
-                    self.code[:pos] + "[" + self.code[pos] + "]" + self.code[pos + 1 :]
+    def tokenize(self):
+        pos = 0
+        length = len(self.code)
+        while pos < length:
+            match = self.regex_cache.match(self.code, pos)
+            if match:
+                token_type = match.lastgroup
+                text = match.group(token_type)
+                if token_type == "IDENTIFIER" and text in KEYWORDS:
+                    token_type = KEYWORDS[text]
+                if token_type != "WHITESPACE":
+                    token = self._get_cached_token(text, token_type)
+                    self.tokens.append(token)
+                pos = match.end(0)
+            else:
+                bad_char = self.code[pos]
+                highlighted = (
+                    self.code[:pos] + "[" + bad_char + "]" + self.code[pos + 1 :]
                 )
                 raise SyntaxError(
-                    f"Illegal character '{unmatched_char}' at position {pos}\n{highlighted_code}"
+                    f"Illegal character '{bad_char}' at position {pos}\n{highlighted}"
                 )
-
-        self.tokens.append(("EOF", None))  # End of file token
+        self.tokens.append(self._get_cached_token(None, "EOF"))

Test patch: diff --git a/tests/test_translator/test_lexer.py b/tests/test_translator/test_lexer.py
index abff042f..35c778a1 100644
--- a/tests/test_translator/test_lexer.py
+++ b/tests/test_translator/test_lexer.py
@@ -1,6 +1,6 @@
-from crosstl.translator.lexer import Lexer
 import pytest
 from typing import List
+from crosstl.translator.lexer import Lexer
 
 
 def tokenize_code(code: str) -> List:
@@ -21,7 +21,8 @@ def test_struct_tokenization():
 
     """
     try:
-        tokenize_code(code)
+        tokens = tokenize_code(code)
+        assert any(t[0] == "STRUCT" for t in tokens), "Missing 'STRUCT' token"
     except SyntaxError:
         pytest.fail("Struct tokenization not implemented.")
 
@@ -35,7 +36,9 @@ def test_if_statement_tokenization():
     }
     """
     try:
-        tokenize_code(code)
+        tokens = tokenize_code(code)
+        assert any(t[0] == "IF" for t in tokens), "Missing 'IF' token"
+        assert any(t[0] == "ELSE" for t in tokens), "Missing 'ELSE' token"
     except SyntaxError:
         pytest.fail("if tokenization not implemented.")
 
@@ -47,7 +50,8 @@ def test_for_statement_tokenization():
     }
     """
     try:
-        tokenize_code(code)
+        tokens = tokenize_code(code)
+        assert any(t[0] == "FOR" for t in tokens), "Missing 'FOR' token"
     except SyntaxError:
         pytest.fail("for tokenization not implemented.")
 
@@ -61,7 +65,8 @@ def test_else_statement_tokenization():
     }
     """
     try:
-        tokenize_code(code)
+        tokens = tokenize_code(code)
+        assert any(t[0] == "ELSE" for t in tokens), "Missing 'ELSE' token"
     except SyntaxError:
         pytest.fail("else tokenization not implemented.")
 
@@ -82,9 +87,10 @@ def test_else_if_statement_tokenization():
     }
     """
     try:
-        tokenize_code(code)
+        tokens = tokenize_code(code)
+        assert tokens, "No tokens generated"
     except SyntaxError:
-        pytest.fail("else if  tokenization not implemented.")
+        pytest.fail("else if tokenization not implemented.")
 
 
 def test_function_call_tokenization():
@@ -98,11 +104,9 @@ def test_function_call_tokenization():
     
     fragment {
         vec4 main(VSOutput input) @ gl_FragColor {
-            // Sample brightness and calculate bloom
             float brightness = texture(iChannel0, input.color.xy).r;
             float bloom = max(0.0, brightness - 0.5);
             bloom = perlinNoise(input.color.xy);
-            // Apply bloom to the texture color
             vec3 texColor = texture(iChannel0, input.color.xy).rgb;
             vec3 colorWithBloom = texColor + vec3(bloom);
 
@@ -112,7 +116,9 @@ def test_function_call_tokenization():
 }
 """
     try:
-        tokenize_code(code)
+        tokens = tokenize_code(code)
+        assert any(t[0] == "SHADER" for t in tokens), "Missing 'SHADER' token"
+        assert any(t[0] == "FRAGMENT" for t in tokens), "Missing 'FRAGMENT' token"
     except SyntaxError:
         pytest.fail("Function call tokenization not implemented.")
 
@@ -122,15 +128,19 @@ def test_bitwise_operator_tokenization():
     int a = 60; // 60 = 0011 1100
     int b = 13; // 13 = 0000 1101
     int c = 0;
-    c = a & b; // 12 = 0000 1100
-    c = a | b; // 61 = 0011 1101
-    c = a ^ b; // 49 = 0011 0001
-    c = ~a; // -61 = 1100 0011
-    c = a << 2; // 240 = 1111 0000
-    c = a >> 2; // 15 = 0000 1111
-      """
+    c = a & b; 
+    c = a | b; 
+    c = a ^ b; 
+    c = ~a; 
+    c = a << 2; 
+    c = a >> 2; 
+    """
     try:
-        tokenize_code(code)
+        tokens = tokenize_code(code)
+        assert any(t[0] == "BITWISE_AND" for t in tokens), "Missing '&' token"
+        assert any(t[0] == "BITWISE_OR" for t in tokens), "Missing '|' token"
+        assert any(t[0] == "BITWISE_XOR" for t in tokens), "Missing '^' token"
+        assert any(t[0] == "BITWISE_NOT" for t in tokens), "Missing '~' token"
     except SyntaxError:
         pytest.fail("Bitwise operator tokenization not implemented.")
 
@@ -144,7 +154,12 @@ def test_data_types_tokenization():
     bool e;
     """
     try:
-        tokenize_code(code)
+        tokens = tokenize_code(code)
+        assert any(t[0] == "INT" for t in tokens), "Missing 'INT' token"
+        assert any(t[0] == "UINT" for t in tokens), "Missing 'UINT' token"
+        assert any(t[0] == "FLOAT" for t in tokens), "Missing 'FLOAT' token"
+        assert any(t[0] == "DOUBLE" for t in tokens), "Missing 'DOUBLE' token"
+        assert any(t[0] == "BOOL" for t in tokens), "Missing 'BOOL' token"
     except SyntaxError:
         pytest.fail("Data types tokenization not implemented.")
 
@@ -153,13 +168,18 @@ def test_operators_tokenization():
     code = """
     int a;
     a = 2 + 1;
-    a = a -  2;
+    a = a - 2;
     a = a / 1;
     a = a * 2;
     a = a % 2;
     """
     try:
-        tokenize_code(code)
+        tokens = tokenize_code(code)
+        assert any(t[0] == "PLUS" for t in tokens), "Missing '+' token"
+        assert any(t[0] == "MINUS" for t in tokens), "Missing '-' token"
+        assert any(t[0] == "DIVIDE" for t in tokens), "Missing '/' token"
+        assert any(t[0] == "MULTIPLY" for t in tokens), "Missing '*' token"
+        assert any(t[0] == "MOD" for t in tokens), "Missing '%' token"
     except SyntaxError:
         pytest.fail("Operators tokenization not implemented.")
 
@@ -173,7 +193,9 @@ def test_logical_operators_tokenization():
     }
     """
     try:
-        tokenize_code(code)
+        tokens = tokenize_code(code)
+        assert any(t[0] == "LOGICAL_OR" for t in tokens), "Missing '||' token"
+        assert any(t[0] == "LOGICAL_AND" for t in tokens), "Missing '&&' token"
     except SyntaxError:
         pytest.fail("Logical Operators tokenization not implemented.")
 
@@ -182,10 +204,11 @@ def test_assignment_shift_operators():
     code = """
     a >>= 1;
     b <<= 1;
-        """
-
+    """
     try:
-        tokenize_code(code)
+        tokens = tokenize_code(code)
+        assert any(t[0] == "ASSIGN_SHIFT_RIGHT" for t in tokens), "Missing '>>=' token"
+        assert any(t[0] == "ASSIGN_SHIFT_LEFT" for t in tokens), "Missing '<<=' token"
     except SyntaxError:
         pytest.fail("Shift operators tokenization failed.")
 
@@ -203,7 +226,15 @@ def test_assignment_operators_tokenization():
     a ^= 1;
     """
     try:
-        tokenize_code(code)
+        tokens = tokenize_code(code)
+        assert any(t[0] == "ASSIGN_ADD" for t in tokens), "Missing '+=' token"
+        assert any(t[0] == "ASSIGN_MUL" for t in tokens), "Missing '*=' token"
+        assert any(t[0] == "ASSIGN_DIV" for t in tokens), "Missing '/=' token"
+        assert any(t[0] == "ASSIGN_SUB" for t in tokens), "Missing '-=' token"
+        assert any(t[0] == "ASSIGN_MOD" for t in tokens), "Missing '%=' token"
+        assert any(t[0] == "ASSIGN_AND" for t in tokens), "Missing '&=' token"
+        assert any(t[0] == "ASSIGN_OR" for t in tokens), "Missing '|=' token"
+        assert any(t[0] == "ASSIGN_XOR" for t in tokens), "Missing '^=' token"
     except SyntaxError:
         pytest.fail("Assignment operators tokenization not implemented.")
 
@@ -212,12 +243,18 @@ def test_const_tokenization():
     code = """
     const int a;
     """
-
     try:
-        tokenize_code(code)
+        tokens = tokenize_code(code)
+        assert any(t[0] == "CONST" for t in tokens), "Missing 'CONST' token"
     except SyntaxError:
         pytest.fail("Const keyword tokenization failed")
 
 
+def test_illegal_character():
+    code = "int a = 1 @#"
+    with pytest.raises(SyntaxError):
+        tokenize_code(code)
+
+
 if __name__ == "__main__":
     pytest.main()