Merge branch 'ci-variable-expression-con-dis-junction' into 'master'

CI variable expression conjunction/disjunction

See merge request gitlab-org/gitlab-ce!27925

12 files changed, 204 insertions, 56 deletions

diff --git a/lib/gitlab/ci/pipeline/expression/lexeme/and.rb b/lib/gitlab/ci/pipeline/expression/lexeme/and.rb
new file mode 100644
index 00000000000..54a0e2ad9dd
--- /dev/null
+++ b/lib/gitlab/ci/pipeline/expression/lexeme/and.rb
@@ -0,0 +1,27 @@
+# frozen_string_literal: true
+
+module Gitlab
+  module Ci
+    module Pipeline
+      module Expression
+        module Lexeme
+          class And < Lexeme::Operator
+            PATTERN = /&&/.freeze
+
+            def evaluate(variables = {})
+              @left.evaluate(variables) && @right.evaluate(variables)
+            end
+
+            def self.build(_value, behind, ahead)
+              new(behind, ahead)
+            end
+
+            def self.precedence
+              11 # See: https://ruby-doc.org/core-2.5.0/doc/syntax/precedence_rdoc.html
+            end
+          end
+        end
+      end
+    end
+  end
+end
diff --git a/lib/gitlab/ci/pipeline/expression/lexeme/base.rb b/lib/gitlab/ci/pipeline/expression/lexeme/base.rb
index 70c774416f6..7ebd2e25398 100644
--- a/lib/gitlab/ci/pipeline/expression/lexeme/base.rb
+++ b/lib/gitlab/ci/pipeline/expression/lexeme/base.rb
@@ -15,10 +15,14 @@ module Gitlab
             end
 
             def self.scan(scanner)
-              if scanner.scan(self::PATTERN)
+              if scanner.scan(pattern)
                 Expression::Token.new(scanner.matched, self)
               end
             end
+
+            def self.pattern
+              self::PATTERN
+            end
           end
         end
       end
diff --git a/lib/gitlab/ci/pipeline/expression/lexeme/equals.rb b/lib/gitlab/ci/pipeline/expression/lexeme/equals.rb
index 668e85f5b9e..62f4c14f597 100644
--- a/lib/gitlab/ci/pipeline/expression/lexeme/equals.rb
+++ b/lib/gitlab/ci/pipeline/expression/lexeme/equals.rb
@@ -8,11 +8,6 @@ module Gitlab
           class Equals < Lexeme::Operator
             PATTERN = /==/.freeze
 
-            def initialize(left, right)
-              @left = left
-              @right = right
-            end
-
             def evaluate(variables = {})
               @left.evaluate(variables) == @right.evaluate(variables)
             end
@@ -20,6 +15,10 @@ module Gitlab
             def self.build(_value, behind, ahead)
               new(behind, ahead)
             end
+
+            def self.precedence
+              10 # See: https://ruby-doc.org/core-2.5.0/doc/syntax/precedence_rdoc.html
+            end
           end
         end
       end
diff --git a/lib/gitlab/ci/pipeline/expression/lexeme/matches.rb b/lib/gitlab/ci/pipeline/expression/lexeme/matches.rb
index cd17bc4d78b..ecfab627226 100644
--- a/lib/gitlab/ci/pipeline/expression/lexeme/matches.rb
+++ b/lib/gitlab/ci/pipeline/expression/lexeme/matches.rb
@@ -8,21 +8,36 @@ module Gitlab
           class Matches < Lexeme::Operator
             PATTERN = /=~/.freeze
 
-            def initialize(left, right)
-              @left = left
-              @right = right
-            end
-
             def evaluate(variables = {})
               text = @left.evaluate(variables)
               regexp = @right.evaluate(variables)
 
               regexp.scan(text.to_s).any?
+
+              if ci_variables_complex_expressions?
+                # return offset of first match, or nil if no matches
+                if match = regexp.scan(text.to_s).first
+                  text.to_s.index(match)
+                end
+              else
+                # return true or false
+                regexp.scan(text.to_s).any?
+              end
             end
 
             def self.build(_value, behind, ahead)
               new(behind, ahead)
             end
+
+            def self.precedence
+              10 # See: https://ruby-doc.org/core-2.5.0/doc/syntax/precedence_rdoc.html
+            end
+
+            private
+
+            def ci_variables_complex_expressions?
+              Feature.enabled?(:ci_variables_complex_expressions, default_enabled: true)
+            end
           end
         end
       end
diff --git a/lib/gitlab/ci/pipeline/expression/lexeme/not_equals.rb b/lib/gitlab/ci/pipeline/expression/lexeme/not_equals.rb
index 5fcc9406cc8..8166bcd5730 100644
--- a/lib/gitlab/ci/pipeline/expression/lexeme/not_equals.rb
+++ b/lib/gitlab/ci/pipeline/expression/lexeme/not_equals.rb
@@ -8,11 +8,6 @@ module Gitlab
           class NotEquals < Lexeme::Operator
             PATTERN = /!=/.freeze
 
-            def initialize(left, right)
-              @left = left
-              @right = right
-            end
-
             def evaluate(variables = {})
               @left.evaluate(variables) != @right.evaluate(variables)
             end
@@ -20,6 +15,10 @@ module Gitlab
             def self.build(_value, behind, ahead)
               new(behind, ahead)
             end
+
+            def self.precedence
+              10 # See: https://ruby-doc.org/core-2.5.0/doc/syntax/precedence_rdoc.html
+            end
           end
         end
       end
diff --git a/lib/gitlab/ci/pipeline/expression/lexeme/not_matches.rb b/lib/gitlab/ci/pipeline/expression/lexeme/not_matches.rb
index 14544d33e25..831c27fa0ea 100644
--- a/lib/gitlab/ci/pipeline/expression/lexeme/not_matches.rb
+++ b/lib/gitlab/ci/pipeline/expression/lexeme/not_matches.rb
@@ -8,11 +8,6 @@ module Gitlab
           class NotMatches < Lexeme::Operator
             PATTERN = /\!~/.freeze
 
-            def initialize(left, right)
-              @left = left
-              @right = right
-            end
-
             def evaluate(variables = {})
               text = @left.evaluate(variables)
               regexp = @right.evaluate(variables)
@@ -23,6 +18,10 @@ module Gitlab
             def self.build(_value, behind, ahead)
               new(behind, ahead)
             end
+
+            def self.precedence
+              10 # See: https://ruby-doc.org/core-2.5.0/doc/syntax/precedence_rdoc.html
+            end
           end
         end
       end
diff --git a/lib/gitlab/ci/pipeline/expression/lexeme/operator.rb b/lib/gitlab/ci/pipeline/expression/lexeme/operator.rb
index 3ebceb92eb7..3ddab7800c8 100644
--- a/lib/gitlab/ci/pipeline/expression/lexeme/operator.rb
+++ b/lib/gitlab/ci/pipeline/expression/lexeme/operator.rb
@@ -6,9 +6,29 @@ module Gitlab
       module Expression
         module Lexeme
           class Operator < Lexeme::Base
+            # This operator class is design to handle single operators that take two
+            # arguments. Expression::Parser was originally designed to read infix operators,
+            # and so the two operands are called "left" and "right" here. If we wish to
+            # implement an Operator that takes a greater or lesser number of arguments, a
+            # structural change or additional Operator superclass will likely be needed.
+
+            OperatorError = Class.new(Expression::ExpressionError)
+
+            def initialize(left, right)
+              raise OperatorError, 'Invalid left operand' unless left.respond_to? :evaluate
+              raise OperatorError, 'Invalid right operand' unless right.respond_to? :evaluate
+
+              @left = left
+              @right = right
+            end
+
             def self.type
               :operator
             end
+
+            def self.precedence
+              raise NotImplementedError
+            end
           end
         end
       end
diff --git a/lib/gitlab/ci/pipeline/expression/lexeme/or.rb b/lib/gitlab/ci/pipeline/expression/lexeme/or.rb
new file mode 100644
index 00000000000..807876f905a
--- /dev/null
+++ b/lib/gitlab/ci/pipeline/expression/lexeme/or.rb
@@ -0,0 +1,27 @@
+# frozen_string_literal: true
+
+module Gitlab
+  module Ci
+    module Pipeline
+      module Expression
+        module Lexeme
+          class Or < Lexeme::Operator
+            PATTERN = /\|\|/.freeze
+
+            def evaluate(variables = {})
+              @left.evaluate(variables) || @right.evaluate(variables)
+            end
+
+            def self.build(_value, behind, ahead)
+              new(behind, ahead)
+            end
+
+            def self.precedence
+              12 # See: https://ruby-doc.org/core-2.5.0/doc/syntax/precedence_rdoc.html
+            end
+          end
+        end
+      end
+    end
+  end
+end
diff --git a/lib/gitlab/ci/pipeline/expression/lexeme/pattern.rb b/lib/gitlab/ci/pipeline/expression/lexeme/pattern.rb
index 2b719c9c6fc..e4cf360a1c1 100644
--- a/lib/gitlab/ci/pipeline/expression/lexeme/pattern.rb
+++ b/lib/gitlab/ci/pipeline/expression/lexeme/pattern.rb
@@ -8,10 +8,11 @@ module Gitlab
           require_dependency 're2'
 
           class Pattern < Lexeme::Value
-            PATTERN = %r{^/.+/[ismU]*$}.freeze
+            PATTERN     = %r{^/.+/[ismU]*$}.freeze
+            NEW_PATTERN = %r{^\/([^\/]|\\/)+[^\\]\/[ismU]*}.freeze
 
             def initialize(regexp)
-              @value = regexp
+              @value = self.class.eager_matching_with_escape_characters? ? regexp.gsub(/\\\//, '/') : regexp
 
               unless Gitlab::UntrustedRegexp::RubySyntax.valid?(@value)
                 raise Lexer::SyntaxError, 'Invalid regular expression!'
@@ -24,9 +25,17 @@ module Gitlab
               raise Expression::RuntimeError, 'Invalid regular expression!'
             end
 
+            def self.pattern
+              eager_matching_with_escape_characters? ? NEW_PATTERN : PATTERN
+            end
+
             def self.build(string)
               new(string)
             end
+
+            def self.eager_matching_with_escape_characters?
+              Feature.enabled?(:ci_variables_complex_expressions, default_enabled: true)
+            end
           end
         end
       end
diff --git a/lib/gitlab/ci/pipeline/expression/lexer.rb b/lib/gitlab/ci/pipeline/expression/lexer.rb
index e14edfae51d..22c210ae26b 100644
--- a/lib/gitlab/ci/pipeline/expression/lexer.rb
+++ b/lib/gitlab/ci/pipeline/expression/lexer.rb
@@ -20,6 +20,19 @@ module Gitlab
             Expression::Lexeme::NotMatches
           ].freeze
 
+          NEW_LEXEMES = [
+            Expression::Lexeme::Variable,
+            Expression::Lexeme::String,
+            Expression::Lexeme::Pattern,
+            Expression::Lexeme::Null,
+            Expression::Lexeme::Equals,
+            Expression::Lexeme::Matches,
+            Expression::Lexeme::NotEquals,
+            Expression::Lexeme::NotMatches,
+            Expression::Lexeme::And,
+            Expression::Lexeme::Or
+          ].freeze
+
           MAX_TOKENS = 100
 
           def initialize(statement, max_tokens: MAX_TOKENS)
@@ -45,7 +58,7 @@ module Gitlab
 
               return tokens if @scanner.eos?
 
-              lexeme = LEXEMES.find do |type|
+              lexeme = available_lexemes.find do |type|
                 type.scan(@scanner).tap do |token|
                   tokens.push(token) if token.present?
                 end
@@ -58,6 +71,10 @@ module Gitlab
 
             raise Lexer::SyntaxError, 'Too many tokens!'
           end
+
+          def available_lexemes
+            Feature.enabled?(:ci_variables_complex_expressions, default_enabled: true) ? NEW_LEXEMES : LEXEMES
+          end
         end
       end
     end
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
diff --git a/lib/gitlab/ci/pipeline/expression/statement.rb b/lib/gitlab/ci/pipeline/expression/statement.rb
index ab5ae9caeea..0e81e1bd34c 100644
--- a/lib/gitlab/ci/pipeline/expression/statement.rb
+++ b/lib/gitlab/ci/pipeline/expression/statement.rb
@@ -7,27 +7,6 @@ module Gitlab
         class Statement
           StatementError = Class.new(Expression::ExpressionError)
 
-          GRAMMAR = [
-            # presence matchers
-            %w[variable],
-
-            # positive matchers
-            %w[variable equals string],
-            %w[variable equals variable],
-            %w[variable equals null],
-            %w[string equals variable],
-            %w[null equals variable],
-            %w[variable matches pattern],
-
-            # negative matchers
-            %w[variable notequals string],
-            %w[variable notequals variable],
-            %w[variable notequals null],
-            %w[string notequals variable],
-            %w[null notequals variable],
-            %w[variable notmatches pattern]
-          ].freeze
-
           def initialize(statement, variables = {})
             @lexer = Expression::Lexer.new(statement)
             @variables = variables.with_indifferent_access
@@ -36,10 +15,6 @@ module Gitlab
           def parse_tree
             raise StatementError if @lexer.lexemes.empty?
 
-            unless GRAMMAR.find { |syntax| syntax == @lexer.lexemes }
-              raise StatementError, 'Unknown pipeline expression!'
-            end
-
             Expression::Parser.new(@lexer.tokens).tree
           end
 
@@ -54,6 +29,7 @@ module Gitlab
           end
 
           def valid?
+            evaluate
             parse_tree.is_a?(Lexeme::Base)
           rescue Expression::ExpressionError
             false