implemented proper operand precedence using the shunting yard algorithm

1 files changed, 96 insertions, 22 deletions

diff --git a/src/sp_config_scanner.re b/src/sp_config_scanner.re
index b36423b..f911df3 100644
--- a/src/sp_config_scanner.re
+++ b/src/sp_config_scanner.re
@@ -71,20 +71,60 @@ static void str_dtor(zval *zv) {
   zend_string_release_ex(Z_STR_P(zv), 1);
 }
 
-static int apply_op(int v1, char op, int v2, int neg) {
-  if (neg) { v2 = !v2; }
+// sy_ functions and macros are helpers for the shunting yard algorithm
+#define sy_res_push(val) \
+  if (cond_res_i >= 100) { cs_error_log("condition too complex on line %d", lineno); goto out; } \
+  cond_res[cond_res_i++] = val;
+#define sy_res_pop() cond_res[--cond_res_i]
+#define sy_op_push(op) \
+  if (cond_op_i >= 100) { cs_error_log("condition too complex on line %d", lineno); goto out; } \
+  cond_op[cond_op_i++] = op;
+#define sy_op_pop() cond_op[--cond_op_i]
+#define sy_op_peek() cond_op[cond_op_i-1]
+
+static inline int sy_op_precedence(char op) {
   switch (op) {
-    case 0: return v2;
-    case '&': return (v1 && v2);
-    case '|': return (v1 || v2);
-    case '<': return (v1 < v2);
-    case '>': return (v1 > v2);
-    case '=': return (v1 == v2);
+    case '!': return 120;
+    case '<':
+    case '>':
+    case 'L': // <=
+    case 'G': // >=
+              return 90;
+    case '&': return 70;
+    case '|': return 60;
+    case '=': return 20;
   }
   return 0;
 }
+static inline int sy_op_is_left_assoc(char op) {
+  switch (op) {
+    case '!': return 0;
+  }
+  return 1;
+}
+static int sy_apply_op(char op, int a, int b) {
+  switch (op) {
+    case '!': return !a;
+    case '&': return (b && a);
+    case '|': return (b || a);
+    case '<': return (b < a);
+    case 'L': return (b <= a);
+    case 'G': return (b >= a);
+    case '>': return (b > a);
+    case '=': return (b == a);
+  }
+  return 0;
+}
+
+#define SY_APPLY_OP_FROM_STACK() \
+  char op = sy_op_pop(); \
+  int unary = (op == '!'); \
+  if (cond_res_i < (2 - unary)) { cs_error_log("not enough input on line %d", lineno); goto out; } \
+  int a = sy_res_pop(); \
+  int b = unary ? 0 : sy_res_pop(); \
+  int res = sy_apply_op(op, a, b); \
+  sy_res_push(res);
 
-#define APPLY_OP(v2) cond_res = apply_op(cond_res, cond_op, v2, cond_neg); cond_op = cond_neg = 0;
 
 zend_result sp_config_scan(char *data, zend_result (*process_rule)(sp_parsed_keyword*))
 {
@@ -100,10 +140,13 @@ zend_result sp_config_scan(char *data, zend_result (*process_rule)(sp_parsed_key
 
   HashTable vars;
   zend_hash_init(&vars, 10, NULL, str_dtor, 1);
+  zend_hash_str_add_ptr(&vars, ZEND_STRL("PHP_VERSION_ID"), zend_string_init(ZEND_STRL(ZEND_TOSTR(PHP_VERSION_ID)), 1));
 
-  int cond_res = 1;
-  char cond_op = 0;
-  int cond_neg = 0;
+
+  int cond_res[100] = {0};
+  int cond_res_i = 0;
+  char cond_op[100] = {0};
+  int cond_op_i = 0;
 
   int cond = yycinit;
   long lineno = 1;
@@ -141,14 +184,14 @@ zend_result sp_config_scan(char *data, zend_result (*process_rule)(sp_parsed_key
       goto yyc_init;
     }
     <init> "@condition" ws+ { goto yyc_cond; }
-    <init> "@end_condition" ws* ";" { cond_res = 1; goto yyc_init; }
+    <init> "@end_condition" ws* ";" { cond_res[0] = 1; goto yyc_init; }
 
     <cond> ws+ { goto yyc_cond; }
     <cond> nl  { lineno++; goto yyc_cond; }
     <cond> @t1 keyword @t2 "(" @t3 string? @t4 ")" {
       if (t4-t3 >= 2 && strlen("extension_loaded") == t2-t1 && strncmp("extension_loaded", t1, t2-t1) == 0) {
         int is_loaded = (zend_hash_str_find_ptr(&module_registry, t3+1, t4-t3-2) != NULL);
-        APPLY_OP(is_loaded);
+        sy_res_push(is_loaded);
       } else {
         cs_error_log("unknown function in condition on line %d", lineno);
         goto out;
@@ -161,21 +204,52 @@ zend_result sp_config_scan(char *data, zend_result (*process_rule)(sp_parsed_key
         cs_error_log("unknown variable in condition on line %d", lineno);
         goto out;
       }
-      APPLY_OP(atoi(ZSTR_VAL(tmp)));
+      sy_res_push(atoi(ZSTR_VAL(tmp)));
       goto yyc_cond_op;
     }
-    <cond> @t1 [0-9]+ @t2 { APPLY_OP(atoi(t1));  goto yyc_cond_op; }
-    <cond> @t1 "!" { cond_neg = (cond_neg + 1) % 2; goto yyc_cond; }
+    <cond> @t1 [0-9]+ @t2 { sy_res_push(atoi(t1));  goto yyc_cond_op; }
+    <cond> @t1 "!" { sy_op_push(*t1); goto yyc_cond; }
+    <cond> @t1 "(" { sy_op_push(*t1); goto yyc_cond; }
     <cond_op> ws+ { goto yyc_cond_op; }
     <cond_op> nl  { lineno++; goto yyc_cond_op; }
-    <cond_op> @t1 ( "&&" | "||" | "<" | ">" | "==" ) { cond_op = *t1; goto yyc_cond; }
-    <cond_op> ";" { goto yyc_init; }
-    <cond, cond_op> * { cs_error_log("Syntax error in condition on line %d", lineno); return false; }
+    <cond_op> @t1 ( "&&" | "||" | "<" | ">" | "==" | "<=" | ">=") @t2 {
+      char op1 = *t1;
+      if (t2-t1 == 2) {
+        switch (op1) {
+          case '<': op1 = 'L'; break; // <=
+          case '>': op1 = 'G'; break; // >=
+        }
+      }
+      while (cond_op_i && sy_op_peek() != '(' && ((sy_op_precedence(sy_op_peek()) > sy_op_precedence(*t1)) || (sy_op_precedence(sy_op_peek()) == sy_op_precedence(*t1)) && sy_op_is_left_assoc(*t1))) {
+          SY_APPLY_OP_FROM_STACK();
+        }
+        sy_op_push(*t1);
+        goto yyc_cond;
+      }
+    <cond_op> ")" {
+      while (cond_op_i && sy_op_peek() != '(') {
+        SY_APPLY_OP_FROM_STACK();
+      }
+      if (cond_op_i == 0 || sy_op_peek() != '(') {
+        cs_error_log("unbalanced parathesis on line %d", lineno); goto out;
+      }
+      sy_op_pop();
+      goto yyc_cond_op;
+    }
+    <cond_op> ";" {
+      while (cond_op_i) {
+        if (sy_op_peek() == '(') { cs_error_log("unbalanced parathesis on line %d", lineno); goto out; }
+        SY_APPLY_OP_FROM_STACK();
+      }
+      if (cond_res_i > 1) { cs_error_log("invalid condition on line %d", lineno); goto out; }
+      goto yyc_init;
+    }
+    <cond, cond_op> * { cs_error_log("Syntax error in condition on line %d", lineno); goto out; }
 
     <rule> ws+     {  goto yyc_rule; }
     <rule> nl / ( nl | ws )* "." {  lineno++; goto yyc_rule; }
     <rule> "." @t1 keyword @t2 ( "(" @t3 ( string? | keyword ) @t4 ")" )?  {
-      if (!cond_res) { goto yyc_rule; }
+      if (!cond_res[0]) { goto yyc_rule; }
       if (kw_i == max_keywords) {
         cs_error_log("Too many keywords in rule (more than %d) on line %d", max_keywords, lineno);
         goto out;
@@ -206,7 +280,7 @@ zend_result sp_config_scan(char *data, zend_result (*process_rule)(sp_parsed_key
     }
     <rule> ";"     {
       end_of_rule:
-      if (!cond_res) { goto yyc_init; }
+      if (!cond_res[0]) { goto yyc_init; }
       parsed_rule[kw_i++] = (sp_parsed_keyword){0, 0, 0, 0, 0, 0};
       if (process_rule && process_rule(parsed_rule) != SUCCESS) {
         goto out;