1 files changed, 63 insertions, 7 deletions
diff --git a/lib/gitlab/ci/pipeline/expression/parser.rb b/lib/gitlab/ci/pipeline/expression/parser.rb
index ed184309ab4..589bf32a4d7 100644
--- a/lib/gitlab/ci/pipeline/expression/parser.rb
+++ b/lib/gitlab/ci/pipeline/expression/parser.rb
@@ -5,17 +5,30 @@ module Gitlab
     module Pipeline
       module Expression
         class Parser
+          ParseError = Class.new(Expression::ExpressionError)
+
           def initialize(tokens)
             @tokens = tokens.to_enum
             @nodes = []
           end
 
-          ##
-          # This produces a reverse descent parse tree.
-          #
-          # It currently does not support precedence of operators.
-          #
           def tree
+            if Feature.enabled?(:ci_variables_complex_expressions, default_enabled: true)
+              rpn_parse_tree
+            else
+              reverse_descent_parse_tree
+            end
+          end
+
+          def self.seed(statement)
+            new(Expression::Lexer.new(statement).tokens)
+          end
+
+          private
+
+          # This produces a reverse descent parse tree.
+          # It does not support precedence of operators.
+          def reverse_descent_parse_tree
             while token = @tokens.next
               case token.type
               when :operator
@@ -32,8 +45,51 @@ module Gitlab
             @nodes.last || Lexeme::Null.new
           end
 
-          def self.seed(statement)
-            new(Expression::Lexer.new(statement).tokens)
+          def rpn_parse_tree
+            results = []
+
+            tokens_rpn.each do |token|
+              case token.type
+              when :value
+                results.push(token.build)
+              when :operator
+                right_operand = results.pop
+                left_operand  = results.pop
+
+                token.build(left_operand, right_operand).tap do |res|
+                  results.push(res)
+                end
+              else
+                raise ParseError, 'Unprocessable token found in parse tree'
+              end
+            end
+
+            raise ParseError, 'Unreachable nodes in parse tree'  if results.count > 1
+            raise ParseError, 'Empty parse tree'                 if results.count < 1
+
+            results.pop
+          end
+
+          # Parse the expression into Reverse Polish Notation
+          # (See: Shunting-yard algorithm)
+          def tokens_rpn
+            output = []
+            operators = []
+
+            @tokens.each do |token|
+              case token.type
+              when :value
+                output.push(token)
+              when :operator
+                if operators.any? && token.lexeme.precedence >= operators.last.lexeme.precedence
+                  output.push(operators.pop)
+                end
+
+                operators.push(token)
+              end
+            end
+
+            output.concat(operators.reverse)
           end
         end
       end