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

CI variable expression conjunction/disjunction

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

24 files changed, 957 insertions, 264 deletions

diff --git a/changelogs/unreleased/ci-variable-conjunction.yml b/changelogs/unreleased/ci-variable-conjunction.yml
new file mode 100644
index 00000000000..839c4285f3a
--- /dev/null
+++ b/changelogs/unreleased/ci-variable-conjunction.yml
@@ -0,0 +1,5 @@
+---
+title: Add support for && and || to CI Pipeline Expressions. Change CI variable expression matching for Lexeme::Pattern to eagerly return tokens.
+merge_request: 27925
+author: Martin Manelli
+type: added
diff --git a/doc/ci/variables/README.md b/doc/ci/variables/README.md
index c851931e85c..fe64f5ab2e0 100644
--- a/doc/ci/variables/README.md
+++ b/doc/ci/variables/README.md
@@ -479,6 +479,7 @@ Below you can find supported syntax reference:
 1. Equality matching using a string
 
     > Example: `$VARIABLE == "some value"`
+
     > Example: `$VARIABLE != "some value"` _(added in 11.11)_
 
     You can use equality operator `==` or `!=` to compare a variable content to a
@@ -489,6 +490,7 @@ Below you can find supported syntax reference:
 1. Checking for an undefined value
 
     > Example: `$VARIABLE == null`
+
     > Example: `$VARIABLE != null` _(added in 11.11)_
 
     It sometimes happens that you want to check whether a variable is defined
@@ -499,6 +501,7 @@ Below you can find supported syntax reference:
 1. Checking for an empty variable
 
     > Example: `$VARIABLE == ""`
+
     > Example: `$VARIABLE != ""` _(added in 11.11)_
 
     If you want to check whether a variable is defined, but is empty, you can
@@ -508,6 +511,7 @@ Below you can find supported syntax reference:
 1. Comparing two variables
 
     > Example: `$VARIABLE_1 == $VARIABLE_2`
+
     > Example: `$VARIABLE_1 != $VARIABLE_2` _(added in 11.11)_
 
     It is possible to compare two variables. This is going to compare values
@@ -527,6 +531,7 @@ Below you can find supported syntax reference:
 1. Pattern matching  _(added in 11.0)_
 
     > Example: `$VARIABLE =~ /^content.*/`
+
     > Example: `$VARIABLE_1 !~ /^content.*/` _(added in 11.11)_
 
     It is possible perform pattern matching against a variable and regular
@@ -536,6 +541,19 @@ Below you can find supported syntax reference:
     Pattern matching is case-sensitive by default. Use `i` flag modifier, like
     `/pattern/i` to make a pattern case-insensitive.
 
+1. Conjunction / Disjunction
+
+    > Example: `$VARIABLE1 =~ /^content.*/ && $VARIABLE2 == "something"`
+
+    > Example: `$VARIABLE1 =~ /^content.*/ && $VARIABLE2 =~ /thing$/ && $VARIABLE3`
+
+    > Example: `$VARIABLE1 =~ /^content.*/ || $VARIABLE2 =~ /thing$/ && $VARIABLE3`
+
+    It is possible to join multiple conditions using `&&` or `||`. Any of the otherwise
+    supported syntax may be used in a conjunctive or disjunctive statement.
+    Precedence of operators follows standard Ruby 2.5 operation
+    [precedence](https://ruby-doc.org/core-2.5.0/doc/syntax/precedence_rdoc.html).
+
 ## Debug tracing
 
 > Introduced in GitLab Runner 1.7.
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
diff --git a/spec/lib/gitlab/ci/pipeline/expression/lexeme/and_spec.rb b/spec/lib/gitlab/ci/pipeline/expression/lexeme/and_spec.rb
new file mode 100644
index 00000000000..006ce4d8078
--- /dev/null
+++ b/spec/lib/gitlab/ci/pipeline/expression/lexeme/and_spec.rb
@@ -0,0 +1,77 @@
+require 'fast_spec_helper'
+require 'rspec-parameterized'
+
+describe Gitlab::Ci::Pipeline::Expression::Lexeme::And do
+  let(:left) { double('left', evaluate: nil) }
+  let(:right) { double('right', evaluate: nil) }
+
+  describe '.build' do
+    it 'creates a new instance of the token' do
+      expect(described_class.build('&&', left, right)).to be_a(described_class)
+    end
+
+    context 'with non-evaluable operands' do
+      let(:left)  { double('left') }
+      let(:right) { double('right') }
+
+      it 'raises an operator error' do
+        expect { described_class.build('&&', left, right) }.to raise_error Gitlab::Ci::Pipeline::Expression::Lexeme::Operator::OperatorError
+      end
+    end
+  end
+
+  describe '.type' do
+    it 'is an operator' do
+      expect(described_class.type).to eq :operator
+    end
+  end
+
+  describe '.precedence' do
+    it 'has a precedence' do
+      expect(described_class.precedence).to be_an Integer
+    end
+  end
+
+  describe '#evaluate' do
+    let(:operator) { described_class.new(left, right) }
+
+    subject { operator.evaluate }
+
+    before do
+      allow(left).to receive(:evaluate).and_return(left_value)
+      allow(right).to receive(:evaluate).and_return(right_value)
+    end
+
+    context 'when left and right are truthy' do
+      where(:left_value, :right_value) do
+        [true, 1, 'a'].permutation(2).to_a
+      end
+
+      with_them do
+        it { is_expected.to be_truthy }
+        it { is_expected.to eq(right_value) }
+      end
+    end
+
+    context 'when left or right is falsey' do
+      where(:left_value, :right_value) do
+        [true, false, nil].permutation(2).to_a
+      end
+
+      with_them do
+        it { is_expected.to be_falsey }
+      end
+    end
+
+    context 'when left and right are falsey' do
+      where(:left_value, :right_value) do
+        [false, nil].permutation(2).to_a
+      end
+
+      with_them do
+        it { is_expected.to be_falsey }
+        it { is_expected.to eq(left_value) }
+      end
+    end
+  end
+end
diff --git a/spec/lib/gitlab/ci/pipeline/expression/lexeme/equals_spec.rb b/spec/lib/gitlab/ci/pipeline/expression/lexeme/equals_spec.rb
index 019a2ed184d..fcbd2863289 100644
--- a/spec/lib/gitlab/ci/pipeline/expression/lexeme/equals_spec.rb
+++ b/spec/lib/gitlab/ci/pipeline/expression/lexeme/equals_spec.rb
@@ -5,9 +5,21 @@ describe Gitlab::Ci::Pipeline::Expression::Lexeme::Equals do
   let(:right) { double('right') }
 
   describe '.build' do
-    it 'creates a new instance of the token' do
-      expect(described_class.build('==', left, right))
-        .to be_a(described_class)
+    context 'with non-evaluable operands' do
+      it 'creates a new instance of the token' do
+        expect { described_class.build('==', left, right) }
+          .to raise_error Gitlab::Ci::Pipeline::Expression::Lexeme::Operator::OperatorError
+      end
+    end
+
+    context 'with evaluable operands' do
+      it 'creates a new instance of the token' do
+        allow(left).to receive(:evaluate).and_return('my-string')
+        allow(right).to receive(:evaluate).and_return('my-string')
+
+        expect(described_class.build('==', left, right))
+          .to be_a(described_class)
+      end
     end
   end
 
@@ -17,23 +29,40 @@ describe Gitlab::Ci::Pipeline::Expression::Lexeme::Equals do
     end
   end
 
+  describe '.precedence' do
+    it 'has a precedence' do
+      expect(described_class.precedence).to be_an Integer
+    end
+  end
+
   describe '#evaluate' do
-    it 'returns false when left and right are not equal' do
-      allow(left).to receive(:evaluate).and_return(1)
-      allow(right).to receive(:evaluate).and_return(2)
+    let(:operator) { described_class.new(left, right) }
 
-      operator = described_class.new(left, right)
+    subject { operator.evaluate }
 
-      expect(operator.evaluate(VARIABLE: 3)).to eq false
+    before do
+      allow(left).to receive(:evaluate).and_return(left_value)
+      allow(right).to receive(:evaluate).and_return(right_value)
     end
 
-    it 'returns true when left and right are equal' do
-      allow(left).to receive(:evaluate).and_return(1)
-      allow(right).to receive(:evaluate).and_return(1)
+    context 'when left and right are equal' do
+      where(:left_value, :right_value) do
+        [%w(string string)]
+      end
+
+      with_them do
+        it { is_expected.to eq(true) }
+      end
+    end
 
-      operator = described_class.new(left, right)
+    context 'when left and right are not equal' do
+      where(:left_value, :right_value) do
+        ['one string', 'two string'].permutation(2).to_a
+      end
 
-      expect(operator.evaluate(VARIABLE: 3)).to eq true
+      with_them do
+        it { is_expected.to eq(false) }
+      end
     end
   end
 end
diff --git a/spec/lib/gitlab/ci/pipeline/expression/lexeme/matches_spec.rb b/spec/lib/gitlab/ci/pipeline/expression/lexeme/matches_spec.rb
index 49e5af52f4d..97da66d2bcc 100644
--- a/spec/lib/gitlab/ci/pipeline/expression/lexeme/matches_spec.rb
+++ b/spec/lib/gitlab/ci/pipeline/expression/lexeme/matches_spec.rb
@@ -6,9 +6,21 @@ describe Gitlab::Ci::Pipeline::Expression::Lexeme::Matches do
   let(:right) { double('right') }
 
   describe '.build' do
-    it 'creates a new instance of the token' do
-      expect(described_class.build('=~', left, right))
-        .to be_a(described_class)
+    context 'with non-evaluable operands' do
+      it 'creates a new instance of the token' do
+        expect { described_class.build('=~', left, right) }
+          .to raise_error Gitlab::Ci::Pipeline::Expression::Lexeme::Operator::OperatorError
+      end
+    end
+
+    context 'with evaluable operands' do
+      it 'creates a new instance of the token' do
+        allow(left).to receive(:evaluate).and_return('my-string')
+        allow(right).to receive(:evaluate).and_return('/my-string/')
+
+        expect(described_class.build('=~', left, right))
+          .to be_a(described_class)
+      end
     end
   end
 
@@ -18,63 +30,93 @@ describe Gitlab::Ci::Pipeline::Expression::Lexeme::Matches do
     end
   end
 
+  describe '.precedence' do
+    it 'has a precedence' do
+      expect(described_class.precedence).to be_an Integer
+    end
+  end
+
   describe '#evaluate' do
-    it 'returns false when left and right do not match' do
-      allow(left).to receive(:evaluate).and_return('my-string')
-      allow(right).to receive(:evaluate)
-        .and_return(Gitlab::UntrustedRegexp.new('something'))
+    let(:operator) { described_class.new(left, right) }
 
-      operator = described_class.new(left, right)
+    subject { operator.evaluate }
 
-      expect(operator.evaluate).to eq false
+    before do
+      allow(left).to receive(:evaluate).and_return(left_value)
+      allow(right).to receive(:evaluate).and_return(right_value)
     end
 
-    it 'returns true when left and right match' do
-      allow(left).to receive(:evaluate).and_return('my-awesome-string')
-      allow(right).to receive(:evaluate)
-        .and_return(Gitlab::UntrustedRegexp.new('awesome.string$'))
+    context 'when left and right do not match' do
+      let(:left_value)  { 'my-string' }
+      let(:right_value) { Gitlab::UntrustedRegexp.new('something') }
 
-      operator = described_class.new(left, right)
-
-      expect(operator.evaluate).to eq true
+      it { is_expected.to eq(nil) }
     end
 
-    it 'supports matching against a nil value' do
-      allow(left).to receive(:evaluate).and_return(nil)
-      allow(right).to receive(:evaluate)
-        .and_return(Gitlab::UntrustedRegexp.new('pattern'))
+    context 'when left and right match' do
+      let(:left_value)  { 'my-awesome-string' }
+      let(:right_value) { Gitlab::UntrustedRegexp.new('awesome.string$') }
+
+      it { is_expected.to eq(3) }
+    end
 
-      operator = described_class.new(left, right)
+    context 'when left is nil' do
+      let(:left_value)  { nil }
+      let(:right_value) { Gitlab::UntrustedRegexp.new('pattern') }
 
-      expect(operator.evaluate).to eq false
+      it { is_expected.to eq(nil) }
     end
 
-    it 'supports multiline strings' do
-      allow(left).to receive(:evaluate).and_return <<~TEXT
-        My awesome contents
+    context 'when left is a multiline string and matches right' do
+      let(:left_value) do
+        <<~TEXT
+          My awesome contents
+
+          My-text-string!
+        TEXT
+      end
+
+      let(:right_value) { Gitlab::UntrustedRegexp.new('text-string') }
+
+      it { is_expected.to eq(24) }
+    end
 
-        My-text-string!
-      TEXT
+    context 'when left is a multiline string and does not match right' do
+      let(:left_value) do
+        <<~TEXT
+          My awesome contents
 
-      allow(right).to receive(:evaluate)
-        .and_return(Gitlab::UntrustedRegexp.new('text-string'))
+          My-terrible-string!
+        TEXT
+      end
 
-      operator = described_class.new(left, right)
+      let(:right_value) { Gitlab::UntrustedRegexp.new('text-string') }
 
-      expect(operator.evaluate).to eq true
+      it { is_expected.to eq(nil) }
     end
 
-    it 'supports regexp flags' do
-      allow(left).to receive(:evaluate).and_return <<~TEXT
-        My AWESOME content
-      TEXT
+    context 'when a matching pattern uses regex flags' do
+      let(:left_value) do
+        <<~TEXT
+          My AWESOME content
+        TEXT
+      end
+
+      let(:right_value) { Gitlab::UntrustedRegexp.new('(?i)awesome') }
+
+      it { is_expected.to eq(3) }
+    end
 
-      allow(right).to receive(:evaluate)
-        .and_return(Gitlab::UntrustedRegexp.new('(?i)awesome'))
+    context 'when a non-matching pattern uses regex flags' do
+      let(:left_value) do
+        <<~TEXT
+          My AWESOME content
+        TEXT
+      end
 
-      operator = described_class.new(left, right)
+      let(:right_value) { Gitlab::UntrustedRegexp.new('(?i)terrible') }
 
-      expect(operator.evaluate).to eq true
+      it { is_expected.to eq(nil) }
     end
   end
 end
diff --git a/spec/lib/gitlab/ci/pipeline/expression/lexeme/not_equals_spec.rb b/spec/lib/gitlab/ci/pipeline/expression/lexeme/not_equals_spec.rb
index 9aa2f4efd67..38d30c9035a 100644
--- a/spec/lib/gitlab/ci/pipeline/expression/lexeme/not_equals_spec.rb
+++ b/spec/lib/gitlab/ci/pipeline/expression/lexeme/not_equals_spec.rb
@@ -5,9 +5,21 @@ describe Gitlab::Ci::Pipeline::Expression::Lexeme::NotEquals do
   let(:right) { double('right') }
 
   describe '.build' do
-    it 'creates a new instance of the token' do
-      expect(described_class.build('!=', left, right))
-        .to be_a(described_class)
+    context 'with non-evaluable operands' do
+      it 'creates a new instance of the token' do
+        expect { described_class.build('!=', left, right) }
+          .to raise_error Gitlab::Ci::Pipeline::Expression::Lexeme::Operator::OperatorError
+      end
+    end
+
+    context 'with evaluable operands' do
+      it 'creates a new instance of the token' do
+        allow(left).to receive(:evaluate).and_return('my-string')
+        allow(right).to receive(:evaluate).and_return('my-string')
+
+        expect(described_class.build('!=', left, right))
+          .to be_a(described_class)
+      end
     end
   end
 
@@ -17,23 +29,45 @@ describe Gitlab::Ci::Pipeline::Expression::Lexeme::NotEquals do
     end
   end
 
+  describe '.precedence' do
+    it 'has a precedence' do
+      expect(described_class.precedence).to be_an Integer
+    end
+  end
+
   describe '#evaluate' do
-    it 'returns true when left and right are not equal' do
-      allow(left).to receive(:evaluate).and_return(1)
-      allow(right).to receive(:evaluate).and_return(2)
+    let(:operator) { described_class.new(left, right) }
 
-      operator = described_class.new(left, right)
+    subject { operator.evaluate }
 
-      expect(operator.evaluate(VARIABLE: 3)).to eq true
+    before do
+      allow(left).to receive(:evaluate).and_return(left_value)
+      allow(right).to receive(:evaluate).and_return(right_value)
     end
 
-    it 'returns false when left and right are equal' do
-      allow(left).to receive(:evaluate).and_return(1)
-      allow(right).to receive(:evaluate).and_return(1)
+    context 'when left and right are equal' do
+      using RSpec::Parameterized::TableSyntax
+
+      where(:left_value, :right_value) do
+        'string' | 'string'
+        1        | 1
+        ''       | ''
+        nil      | nil
+      end
+
+      with_them do
+        it { is_expected.to eq(false) }
+      end
+    end
 
-      operator = described_class.new(left, right)
+    context 'when left and right are not equal' do
+      where(:left_value, :right_value) do
+        ['one string', 'two string', 1, 2, '', nil, false, true].permutation(2).to_a
+      end
 
-      expect(operator.evaluate(VARIABLE: 3)).to eq false
+      with_them do
+        it { is_expected.to eq(true) }
+      end
     end
   end
 end
diff --git a/spec/lib/gitlab/ci/pipeline/expression/lexeme/not_matches_spec.rb b/spec/lib/gitlab/ci/pipeline/expression/lexeme/not_matches_spec.rb
index fa3b9651fb4..99110ff8d88 100644
--- a/spec/lib/gitlab/ci/pipeline/expression/lexeme/not_matches_spec.rb
+++ b/spec/lib/gitlab/ci/pipeline/expression/lexeme/not_matches_spec.rb
@@ -6,9 +6,21 @@ describe Gitlab::Ci::Pipeline::Expression::Lexeme::NotMatches do
   let(:right) { double('right') }
 
   describe '.build' do
-    it 'creates a new instance of the token' do
-      expect(described_class.build('!~', left, right))
-        .to be_a(described_class)
+    context 'with non-evaluable operands' do
+      it 'creates a new instance of the token' do
+        expect { described_class.build('!~', left, right) }
+          .to raise_error Gitlab::Ci::Pipeline::Expression::Lexeme::Operator::OperatorError
+      end
+    end
+
+    context 'with evaluable operands' do
+      it 'creates a new instance of the token' do
+        allow(left).to receive(:evaluate).and_return('my-string')
+        allow(right).to receive(:evaluate).and_return('my-string')
+
+        expect(described_class.build('!~', left, right))
+          .to be_a(described_class)
+      end
     end
   end
 
@@ -18,63 +30,93 @@ describe Gitlab::Ci::Pipeline::Expression::Lexeme::NotMatches do
     end
   end
 
+  describe '.precedence' do
+    it 'has a precedence' do
+      expect(described_class.precedence).to be_an Integer
+    end
+  end
+
   describe '#evaluate' do
-    it 'returns true when left and right do not match' do
-      allow(left).to receive(:evaluate).and_return('my-string')
-      allow(right).to receive(:evaluate)
-        .and_return(Gitlab::UntrustedRegexp.new('something'))
+    let(:operator) { described_class.new(left, right) }
 
-      operator = described_class.new(left, right)
+    subject { operator.evaluate }
 
-      expect(operator.evaluate).to eq true
+    before do
+      allow(left).to receive(:evaluate).and_return(left_value)
+      allow(right).to receive(:evaluate).and_return(right_value)
     end
 
-    it 'returns false when left and right match' do
-      allow(left).to receive(:evaluate).and_return('my-awesome-string')
-      allow(right).to receive(:evaluate)
-        .and_return(Gitlab::UntrustedRegexp.new('awesome.string$'))
+    context 'when left and right do not match' do
+      let(:left_value)  { 'my-string' }
+      let(:right_value) { Gitlab::UntrustedRegexp.new('something') }
 
-      operator = described_class.new(left, right)
-
-      expect(operator.evaluate).to eq false
+      it { is_expected.to eq(true) }
     end
 
-    it 'supports matching against a nil value' do
-      allow(left).to receive(:evaluate).and_return(nil)
-      allow(right).to receive(:evaluate)
-        .and_return(Gitlab::UntrustedRegexp.new('pattern'))
+    context 'when left and right match' do
+      let(:left_value)  { 'my-awesome-string' }
+      let(:right_value) { Gitlab::UntrustedRegexp.new('awesome.string$') }
+
+      it { is_expected.to eq(false) }
+    end
 
-      operator = described_class.new(left, right)
+    context 'when left is nil' do
+      let(:left_value)  { nil }
+      let(:right_value) { Gitlab::UntrustedRegexp.new('pattern') }
 
-      expect(operator.evaluate).to eq true
+      it { is_expected.to eq(true) }
     end
 
-    it 'supports multiline strings' do
-      allow(left).to receive(:evaluate).and_return <<~TEXT
-        My awesome contents
+    context 'when left is a multiline string and matches right' do
+      let(:left_value) do
+        <<~TEXT
+          My awesome contents
+
+          My-text-string!
+        TEXT
+      end
+
+      let(:right_value) { Gitlab::UntrustedRegexp.new('text-string') }
+
+      it { is_expected.to eq(false) }
+    end
 
-        My-text-string!
-      TEXT
+    context 'when left is a multiline string and does not match right' do
+      let(:left_value) do
+        <<~TEXT
+          My awesome contents
 
-      allow(right).to receive(:evaluate)
-        .and_return(Gitlab::UntrustedRegexp.new('text-string'))
+          My-terrible-string!
+        TEXT
+      end
 
-      operator = described_class.new(left, right)
+      let(:right_value) { Gitlab::UntrustedRegexp.new('text-string') }
 
-      expect(operator.evaluate).to eq false
+      it { is_expected.to eq(true) }
     end
 
-    it 'supports regexp flags' do
-      allow(left).to receive(:evaluate).and_return <<~TEXT
-        My AWESOME content
-      TEXT
+    context 'when a matching pattern uses regex flags' do
+      let(:left_value) do
+        <<~TEXT
+          My AWESOME content
+        TEXT
+      end
+
+      let(:right_value) { Gitlab::UntrustedRegexp.new('(?i)awesome') }
+
+      it { is_expected.to eq(false) }
+    end
 
-      allow(right).to receive(:evaluate)
-        .and_return(Gitlab::UntrustedRegexp.new('(?i)awesome'))
+    context 'when a non-matching pattern uses regex flags' do
+      let(:left_value) do
+        <<~TEXT
+          My AWESOME content
+        TEXT
+      end
 
-      operator = described_class.new(left, right)
+      let(:right_value) { Gitlab::UntrustedRegexp.new('(?i)terrible') }
 
-      expect(operator.evaluate).to eq false
+      it { is_expected.to eq(true) }
     end
   end
 end
diff --git a/spec/lib/gitlab/ci/pipeline/expression/lexeme/or_spec.rb b/spec/lib/gitlab/ci/pipeline/expression/lexeme/or_spec.rb
new file mode 100644
index 00000000000..d542eebc613
--- /dev/null
+++ b/spec/lib/gitlab/ci/pipeline/expression/lexeme/or_spec.rb
@@ -0,0 +1,77 @@
+require 'fast_spec_helper'
+require 'rspec-parameterized'
+
+describe Gitlab::Ci::Pipeline::Expression::Lexeme::Or do
+  let(:left) { double('left', evaluate: nil) }
+  let(:right) { double('right', evaluate: nil) }
+
+  describe '.build' do
+    it 'creates a new instance of the token' do
+      expect(described_class.build('||', left, right)).to be_a(described_class)
+    end
+
+    context 'with non-evaluable operands' do
+      let(:left)  { double('left') }
+      let(:right) { double('right') }
+
+      it 'raises an operator error' do
+        expect { described_class.build('||', left, right) }.to raise_error Gitlab::Ci::Pipeline::Expression::Lexeme::Operator::OperatorError
+      end
+    end
+  end
+
+  describe '.type' do
+    it 'is an operator' do
+      expect(described_class.type).to eq :operator
+    end
+  end
+
+  describe '.precedence' do
+    it 'has a precedence' do
+      expect(described_class.precedence).to be_an Integer
+    end
+  end
+
+  describe '#evaluate' do
+    let(:operator) { described_class.new(left, right) }
+
+    subject { operator.evaluate }
+
+    before do
+      allow(left).to receive(:evaluate).and_return(left_value)
+      allow(right).to receive(:evaluate).and_return(right_value)
+    end
+
+    context 'when left and right are truthy' do
+      where(:left_value, :right_value) do
+        [true, 1, 'a'].permutation(2).to_a
+      end
+
+      with_them do
+        it { is_expected.to be_truthy }
+        it { is_expected.to eq(left_value) }
+      end
+    end
+
+    context 'when left or right is truthy' do
+      where(:left_value, :right_value) do
+        [true, false, 'a'].permutation(2).to_a
+      end
+
+      with_them do
+        it { is_expected.to be_truthy }
+      end
+    end
+
+    context 'when left and right are falsey' do
+      where(:left_value, :right_value) do
+        [false, nil].permutation(2).to_a
+      end
+
+      with_them do
+        it { is_expected.to be_falsey }
+        it { is_expected.to eq(right_value) }
+      end
+    end
+  end
+end
diff --git a/spec/lib/gitlab/ci/pipeline/expression/lexeme/pattern_spec.rb b/spec/lib/gitlab/ci/pipeline/expression/lexeme/pattern_spec.rb
index cff7f57ceff..30ea3f3e28e 100644
--- a/spec/lib/gitlab/ci/pipeline/expression/lexeme/pattern_spec.rb
+++ b/spec/lib/gitlab/ci/pipeline/expression/lexeme/pattern_spec.rb
@@ -1,4 +1,4 @@
-require 'fast_spec_helper'
+require 'spec_helper'
 
 describe Gitlab::Ci::Pipeline::Expression::Lexeme::Pattern do
   describe '.build' do
@@ -30,16 +30,6 @@ describe Gitlab::Ci::Pipeline::Expression::Lexeme::Pattern do
         .to eq Gitlab::UntrustedRegexp.new('pattern')
     end
 
-    it 'is a greedy scanner for regexp boundaries' do
-      scanner = StringScanner.new('/some .* / pattern/')
-
-      token = described_class.scan(scanner)
-
-      expect(token).not_to be_nil
-      expect(token.build.evaluate)
-        .to eq Gitlab::UntrustedRegexp.new('some .* / pattern')
-    end
-
     it 'does not allow to use an empty pattern' do
       scanner = StringScanner.new(%(//))
 
@@ -68,12 +58,90 @@ describe Gitlab::Ci::Pipeline::Expression::Lexeme::Pattern do
         .to eq Gitlab::UntrustedRegexp.new('(?im)pattern')
     end
 
-    it 'does not support arbitrary flags' do
+    it 'ignores unsupported flags' do
       scanner = StringScanner.new('/pattern/x')
 
       token = described_class.scan(scanner)
 
-      expect(token).to be_nil
+      expect(token).not_to be_nil
+      expect(token.build.evaluate)
+        .to eq Gitlab::UntrustedRegexp.new('pattern')
+    end
+
+    it 'is a eager scanner for regexp boundaries' do
+      scanner = StringScanner.new('/some .* / pattern/')
+
+      token = described_class.scan(scanner)
+
+      expect(token).not_to be_nil
+      expect(token.build.evaluate)
+        .to eq Gitlab::UntrustedRegexp.new('some .* ')
+    end
+
+    it 'does not match on escaped regexp boundaries' do
+      scanner = StringScanner.new('/some .* \/ pattern/')
+
+      token = described_class.scan(scanner)
+
+      expect(token).not_to be_nil
+      expect(token.build.evaluate)
+        .to eq Gitlab::UntrustedRegexp.new('some .* / pattern')
+    end
+
+    it 'recognizes \ as an escape character for /' do
+      scanner = StringScanner.new('/some numeric \/$ pattern/')
+
+      token = described_class.scan(scanner)
+
+      expect(token).not_to be_nil
+      expect(token.build.evaluate)
+        .to eq Gitlab::UntrustedRegexp.new('some numeric /$ pattern')
+    end
+
+    it 'does not recognize \ as an escape character for $' do
+      scanner = StringScanner.new('/some numeric \$ pattern/')
+
+      token = described_class.scan(scanner)
+
+      expect(token).not_to be_nil
+      expect(token.build.evaluate)
+        .to eq Gitlab::UntrustedRegexp.new('some numeric \$ pattern')
+    end
+
+    context 'with the ci_variables_complex_expressions feature flag disabled' do
+      before do
+        stub_feature_flags(ci_variables_complex_expressions: false)
+      end
+
+      it 'is a greedy scanner for regexp boundaries' do
+        scanner = StringScanner.new('/some .* / pattern/')
+
+        token = described_class.scan(scanner)
+
+        expect(token).not_to be_nil
+        expect(token.build.evaluate)
+          .to eq Gitlab::UntrustedRegexp.new('some .* / pattern')
+      end
+
+      it 'does not recognize the \ escape character for /' do
+        scanner = StringScanner.new('/some .* \/ pattern/')
+
+        token = described_class.scan(scanner)
+
+        expect(token).not_to be_nil
+        expect(token.build.evaluate)
+          .to eq Gitlab::UntrustedRegexp.new('some .* \/ pattern')
+      end
+
+      it 'does not recognize the \ escape character for $' do
+        scanner = StringScanner.new('/some numeric \$ pattern/')
+
+        token = described_class.scan(scanner)
+
+        expect(token).not_to be_nil
+        expect(token.build.evaluate)
+          .to eq Gitlab::UntrustedRegexp.new('some numeric \$ pattern')
+      end
     end
   end
 
diff --git a/spec/lib/gitlab/ci/pipeline/expression/lexer_spec.rb b/spec/lib/gitlab/ci/pipeline/expression/lexer_spec.rb
index 3f11b3f7673..d8db9c262a1 100644
--- a/spec/lib/gitlab/ci/pipeline/expression/lexer_spec.rb
+++ b/spec/lib/gitlab/ci/pipeline/expression/lexer_spec.rb
@@ -58,6 +58,56 @@ describe Gitlab::Ci::Pipeline::Expression::Lexer do
       expect { lexer.tokens }
         .to raise_error described_class::SyntaxError
     end
+
+    context 'with complex expressions' do
+      using RSpec::Parameterized::TableSyntax
+
+      subject { described_class.new(expression).tokens.map(&:value) }
+
+      where(:expression, :tokens) do
+        '$PRESENT_VARIABLE =~ /my var/ && $EMPTY_VARIABLE =~ /nope/' | ['$PRESENT_VARIABLE', '=~', '/my var/', '&&', '$EMPTY_VARIABLE', '=~', '/nope/']
+        '$EMPTY_VARIABLE == "" && $PRESENT_VARIABLE'                 | ['$EMPTY_VARIABLE', '==', '""', '&&', '$PRESENT_VARIABLE']
+        '$EMPTY_VARIABLE == "" && $PRESENT_VARIABLE != "nope"'       | ['$EMPTY_VARIABLE', '==', '""', '&&', '$PRESENT_VARIABLE', '!=', '"nope"']
+        '$PRESENT_VARIABLE && $EMPTY_VARIABLE'                       | ['$PRESENT_VARIABLE', '&&', '$EMPTY_VARIABLE']
+        '$PRESENT_VARIABLE =~ /my var/ || $EMPTY_VARIABLE =~ /nope/' | ['$PRESENT_VARIABLE', '=~', '/my var/', '||', '$EMPTY_VARIABLE', '=~', '/nope/']
+        '$EMPTY_VARIABLE == "" || $PRESENT_VARIABLE'                 | ['$EMPTY_VARIABLE', '==', '""', '||', '$PRESENT_VARIABLE']
+        '$EMPTY_VARIABLE == "" || $PRESENT_VARIABLE != "nope"'       | ['$EMPTY_VARIABLE', '==', '""', '||', '$PRESENT_VARIABLE', '!=', '"nope"']
+        '$PRESENT_VARIABLE || $EMPTY_VARIABLE'                       | ['$PRESENT_VARIABLE', '||', '$EMPTY_VARIABLE']
+        '$PRESENT_VARIABLE && null || $EMPTY_VARIABLE == ""'         | ['$PRESENT_VARIABLE', '&&', 'null', '||', '$EMPTY_VARIABLE', '==', '""']
+      end
+
+      with_them do
+        it { is_expected.to eq(tokens) }
+      end
+    end
+
+    context 'with the ci_variables_complex_expressions feature flag turned off' do
+      before do
+        stub_feature_flags(ci_variables_complex_expressions: false)
+      end
+
+      it 'incorrectly tokenizes conjunctive match statements as one match statement' do
+        tokens = described_class.new('$PRESENT_VARIABLE =~ /my var/ && $EMPTY_VARIABLE =~ /nope/').tokens
+
+        expect(tokens.map(&:value)).to eq(['$PRESENT_VARIABLE', '=~', '/my var/ && $EMPTY_VARIABLE =~ /nope/'])
+      end
+
+      it 'incorrectly tokenizes disjunctive match statements as one statement' do
+        tokens = described_class.new('$PRESENT_VARIABLE =~ /my var/ || $EMPTY_VARIABLE =~ /nope/').tokens
+
+        expect(tokens.map(&:value)).to eq(['$PRESENT_VARIABLE', '=~', '/my var/ || $EMPTY_VARIABLE =~ /nope/'])
+      end
+
+      it 'raises an error about && operators' do
+        expect { described_class.new('$EMPTY_VARIABLE == "" && $PRESENT_VARIABLE').tokens }
+          .to raise_error(Gitlab::Ci::Pipeline::Expression::Lexer::SyntaxError).with_message('Unknown lexeme found!')
+      end
+
+      it 'raises an error about || operators' do
+        expect { described_class.new('$EMPTY_VARIABLE == "" || $PRESENT_VARIABLE').tokens }
+          .to raise_error(Gitlab::Ci::Pipeline::Expression::Lexer::SyntaxError).with_message('Unknown lexeme found!')
+      end
+    end
   end
 
   describe '#lexemes' do
diff --git a/spec/lib/gitlab/ci/pipeline/expression/parser_spec.rb b/spec/lib/gitlab/ci/pipeline/expression/parser_spec.rb
index 2b78b1dd4a7..e88ec5561b6 100644
--- a/spec/lib/gitlab/ci/pipeline/expression/parser_spec.rb
+++ b/spec/lib/gitlab/ci/pipeline/expression/parser_spec.rb
@@ -2,25 +2,67 @@ require 'fast_spec_helper'
 
 describe Gitlab::Ci::Pipeline::Expression::Parser do
   describe '#tree' do
-    context 'when using operators' do
+    context 'when using two operators' do
+      it 'returns a reverse descent parse tree' do
+        expect(described_class.seed('$VAR1 == "123"').tree)
+          .to be_a Gitlab::Ci::Pipeline::Expression::Lexeme::Equals
+      end
+    end
+
+    context 'when using three operators' do
       it 'returns a reverse descent parse tree' do
         expect(described_class.seed('$VAR1 == "123" == $VAR2').tree)
           .to be_a Gitlab::Ci::Pipeline::Expression::Lexeme::Equals
       end
     end
 
-    context 'when using a single token' do
+    context 'when using a single variable token' do
       it 'returns a single token instance' do
         expect(described_class.seed('$VAR').tree)
           .to be_a Gitlab::Ci::Pipeline::Expression::Lexeme::Variable
       end
     end
 
+    context 'when using a single string token' do
+      it 'returns a single token instance' do
+        expect(described_class.seed('"some value"').tree)
+          .to be_a Gitlab::Ci::Pipeline::Expression::Lexeme::String
+      end
+    end
+
     context 'when expression is empty' do
       it 'returns a null token' do
-        expect(described_class.seed('').tree)
+        expect { described_class.seed('').tree }
+          .to raise_error Gitlab::Ci::Pipeline::Expression::Parser::ParseError
+      end
+    end
+
+    context 'when expression is null' do
+      it 'returns a null token' do
+        expect(described_class.seed('null').tree)
           .to be_a Gitlab::Ci::Pipeline::Expression::Lexeme::Null
       end
     end
+
+    context 'when two value tokens have no operator' do
+      it 'raises a parsing error' do
+        expect { described_class.seed('$VAR "text"').tree }
+          .to raise_error Gitlab::Ci::Pipeline::Expression::Parser::ParseError
+      end
+    end
+
+    context 'when an operator has no left side' do
+      it 'raises an OperatorError' do
+        expect { described_class.seed('== "123"').tree }
+            .to raise_error Gitlab::Ci::Pipeline::Expression::Lexeme::Operator::OperatorError
+      end
+    end
+
+    context 'when an operator has no right side' do
+      it 'raises an OperatorError' do
+        expect { described_class.seed('$VAR ==').tree }
+            .to raise_error Gitlab::Ci::Pipeline::Expression::Lexeme::Operator::OperatorError
+      end
+    end
   end
 end
diff --git a/spec/lib/gitlab/ci/pipeline/expression/statement_spec.rb b/spec/lib/gitlab/ci/pipeline/expression/statement_spec.rb
index a9fd809409b..057e2f3fbe8 100644
--- a/spec/lib/gitlab/ci/pipeline/expression/statement_spec.rb
+++ b/spec/lib/gitlab/ci/pipeline/expression/statement_spec.rb
@@ -1,4 +1,6 @@
-require 'fast_spec_helper'
+# TODO switch this back after the "ci_variables_complex_expressions" feature flag is removed
+# require 'fast_spec_helper'
+require 'spec_helper'
 require 'rspec-parameterized'
 
 describe Gitlab::Ci::Pipeline::Expression::Statement do
@@ -7,8 +9,12 @@ describe Gitlab::Ci::Pipeline::Expression::Statement do
   end
 
   let(:variables) do
-    { 'PRESENT_VARIABLE' => 'my variable',
-      EMPTY_VARIABLE: '' }
+    {
+      'PRESENT_VARIABLE'   => 'my variable',
+      'PATH_VARIABLE'      => 'a/path/variable/value',
+      'FULL_PATH_VARIABLE' => '/a/full/path/variable/value',
+      'EMPTY_VARIABLE'     =>  ''
+    }
   end
 
   describe '.new' do
@@ -21,105 +27,158 @@ describe Gitlab::Ci::Pipeline::Expression::Statement do
     end
   end
 
-  describe '#parse_tree' do
-    context 'when expression is empty' do
-      let(:text) { '' }
-
-      it 'raises an error' do
-        expect { subject.parse_tree }
-          .to raise_error described_class::StatementError
-      end
-    end
+  describe '#evaluate' do
+    using RSpec::Parameterized::TableSyntax
 
-    context 'when expression grammar is incorrect' do
-      table = [
-        '$VAR "text"',   # missing operator
-        '== "123"',      # invalid left side
-        '"some string"', # only string provided
-        '$VAR ==',       # invalid right side
-        'null',          # missing lexemes
-        ''               # empty statement
-      ]
-
-      table.each do |syntax|
-        context "when expression grammar is #{syntax.inspect}" do
-          let(:text) { syntax }
-
-          it 'raises a statement error exception' do
-            expect { subject.parse_tree }
-              .to raise_error described_class::StatementError
-          end
-
-          it 'is an invalid statement' do
-            expect(subject).not_to be_valid
-          end
-        end
-      end
+    where(:expression, :value) do
+      '$PRESENT_VARIABLE == "my variable"'                          | true
+      '"my variable" == $PRESENT_VARIABLE'                          | true
+      '$PRESENT_VARIABLE == null'                                   | false
+      '$EMPTY_VARIABLE == null'                                     | false
+      '"" == $EMPTY_VARIABLE'                                       | true
+      '$EMPTY_VARIABLE'                                             | ''
+      '$UNDEFINED_VARIABLE == null'                                 | true
+      'null == $UNDEFINED_VARIABLE'                                 | true
+      '$PRESENT_VARIABLE'                                           | 'my variable'
+      '$UNDEFINED_VARIABLE'                                         | nil
+      "$PRESENT_VARIABLE =~ /var.*e$/"                              | 3
+      '$PRESENT_VARIABLE =~ /va\r.*e$/'                             | nil
+      '$PRESENT_VARIABLE =~ /va\/r.*e$/'                            | nil
+      "$PRESENT_VARIABLE =~ /var.*e$/"                              | 3
+      "$PRESENT_VARIABLE =~ /^var.*/"                               | nil
+      "$EMPTY_VARIABLE =~ /var.*/"                                  | nil
+      "$UNDEFINED_VARIABLE =~ /var.*/"                              | nil
+      "$PRESENT_VARIABLE =~ /VAR.*/i"                               | 3
+      '$PATH_VARIABLE =~ /path\/variable/'                          | 2
+      '$FULL_PATH_VARIABLE =~ /^\/a\/full\/path\/variable\/value$/' | 0
+      '$FULL_PATH_VARIABLE =~ /\\/path\\/variable\\/value$/'        | 7
+      '$PRESENT_VARIABLE != "my variable"'                          | false
+      '"my variable" != $PRESENT_VARIABLE'                          | false
+      '$PRESENT_VARIABLE != null'                                   | true
+      '$EMPTY_VARIABLE != null'                                     | true
+      '"" != $EMPTY_VARIABLE'                                       | false
+      '$UNDEFINED_VARIABLE != null'                                 | false
+      'null != $UNDEFINED_VARIABLE'                                 | false
+      "$PRESENT_VARIABLE !~ /var.*e$/"                              | false
+      "$PRESENT_VARIABLE !~ /^var.*/"                               | true
+      '$PRESENT_VARIABLE !~ /^v\ar.*/'                              | true
+      '$PRESENT_VARIABLE !~ /^v\/ar.*/'                             | true
+      "$EMPTY_VARIABLE !~ /var.*/"                                  | true
+      "$UNDEFINED_VARIABLE !~ /var.*/"                              | true
+      "$PRESENT_VARIABLE !~ /VAR.*/i"                               | false
+
+      '$PRESENT_VARIABLE && "string"'          | 'string'
+      '$PRESENT_VARIABLE && $PRESENT_VARIABLE' | 'my variable'
+      '$PRESENT_VARIABLE && $EMPTY_VARIABLE'   | ''
+      '$PRESENT_VARIABLE && null'              | nil
+      '"string" && $PRESENT_VARIABLE'          | 'my variable'
+      '$EMPTY_VARIABLE && $PRESENT_VARIABLE'   | 'my variable'
+      'null && $PRESENT_VARIABLE'              | nil
+      '$EMPTY_VARIABLE && "string"'            | 'string'
+      '$EMPTY_VARIABLE && $EMPTY_VARIABLE'     | ''
+      '"string" && $EMPTY_VARIABLE'            | ''
+      '"string" && null'                       | nil
+      'null && "string"'                       | nil
+      '"string" && "string"'                   | 'string'
+      'null && null'                           | nil
+
+      '$PRESENT_VARIABLE =~ /my var/ && $EMPTY_VARIABLE =~ /nope/' | nil
+      '$EMPTY_VARIABLE == "" && $PRESENT_VARIABLE'                 | 'my variable'
+      '$EMPTY_VARIABLE == "" && $PRESENT_VARIABLE != "nope"'       | true
+      '$PRESENT_VARIABLE && $EMPTY_VARIABLE'                       | ''
+      '$PRESENT_VARIABLE && $UNDEFINED_VARIABLE'                   | nil
+      '$UNDEFINED_VARIABLE && $EMPTY_VARIABLE'                     | nil
+      '$UNDEFINED_VARIABLE && $PRESENT_VARIABLE'                   | nil
+
+      '$FULL_PATH_VARIABLE =~ /^\/a\/full\/path\/variable\/value$/ && $PATH_VARIABLE =~ /path\/variable/'      | 2
+      '$FULL_PATH_VARIABLE =~ /^\/a\/bad\/path\/variable\/value$/ && $PATH_VARIABLE =~ /path\/variable/'       | nil
+      '$FULL_PATH_VARIABLE =~ /^\/a\/full\/path\/variable\/value$/ && $PATH_VARIABLE =~ /bad\/path\/variable/' | nil
+      '$FULL_PATH_VARIABLE =~ /^\/a\/bad\/path\/variable\/value$/ && $PATH_VARIABLE =~ /bad\/path\/variable/'  | nil
+
+      '$FULL_PATH_VARIABLE =~ /^\/a\/full\/path\/variable\/value$/ || $PATH_VARIABLE =~ /path\/variable/'      | 0
+      '$FULL_PATH_VARIABLE =~ /^\/a\/bad\/path\/variable\/value$/ || $PATH_VARIABLE =~ /path\/variable/'       | 2
+      '$FULL_PATH_VARIABLE =~ /^\/a\/full\/path\/variable\/value$/ || $PATH_VARIABLE =~ /bad\/path\/variable/' | 0
+      '$FULL_PATH_VARIABLE =~ /^\/a\/bad\/path\/variable\/value$/ || $PATH_VARIABLE =~ /bad\/path\/variable/'  | nil
+
+      '$PRESENT_VARIABLE =~ /my var/ || $EMPTY_VARIABLE =~ /nope/' | 0
+      '$EMPTY_VARIABLE == "" || $PRESENT_VARIABLE'                 | true
+      '$PRESENT_VARIABLE != "nope" || $EMPTY_VARIABLE == ""'       | true
+
+      '$PRESENT_VARIABLE && null || $EMPTY_VARIABLE == ""'         | true
+      '$PRESENT_VARIABLE || $UNDEFINED_VARIABLE'                   | 'my variable'
+      '$UNDEFINED_VARIABLE || $PRESENT_VARIABLE'                   | 'my variable'
+      '$UNDEFINED_VARIABLE == null || $PRESENT_VARIABLE'           | true
+      '$PRESENT_VARIABLE || $UNDEFINED_VARIABLE == null'           | 'my variable'
     end
 
-    context 'when expression grammar is correct' do
-      context 'when using an operator' do
-        let(:text) { '$VAR == "value"' }
-
-        it 'returns a reverse descent parse tree' do
-          expect(subject.parse_tree)
-            .to be_a Gitlab::Ci::Pipeline::Expression::Lexeme::Equals
-        end
+    with_them do
+      let(:text) { expression }
 
-        it 'is a valid statement' do
-          expect(subject).to be_valid
-        end
+      it "evaluates to `#{params[:value].inspect}`" do
+        expect(subject.evaluate).to eq(value)
       end
 
-      context 'when using a single token' do
-        let(:text) { '$PRESENT_VARIABLE' }
+      # This test is used to ensure that our parser
+      # returns exactly the same results as if we
+      # were evaluating using ruby's `eval`
+      context 'when using Ruby eval' do
+        let(:expression_ruby) do
+          expression
+            .gsub(/null/, 'nil')
+            .gsub(/\$([a-zA-Z_][a-zA-Z0-9_]*)/) { "variables['#{Regexp.last_match(1)}']" }
+        end
 
-        it 'returns a single token instance' do
-          expect(subject.parse_tree)
-            .to be_a Gitlab::Ci::Pipeline::Expression::Lexeme::Variable
+        it 'behaves exactly the same' do
+          expect(instance_eval(expression_ruby)).to eq(subject.evaluate)
         end
       end
     end
-  end
 
-  describe '#evaluate' do
-    using RSpec::Parameterized::TableSyntax
+    context 'with the ci_variables_complex_expressions feature flag disabled' do
+      before do
+        stub_feature_flags(ci_variables_complex_expressions: false)
+      end
 
-    where(:expression, :value) do
-      '$PRESENT_VARIABLE == "my variable"' | true
-      '"my variable" == $PRESENT_VARIABLE' | true
-      '$PRESENT_VARIABLE == null'          | false
-      '$EMPTY_VARIABLE == null'            | false
-      '"" == $EMPTY_VARIABLE'              | true
-      '$EMPTY_VARIABLE'                    | ''
-      '$UNDEFINED_VARIABLE == null'        | true
-      'null == $UNDEFINED_VARIABLE'        | true
-      '$PRESENT_VARIABLE'                  | 'my variable'
-      '$UNDEFINED_VARIABLE'                | nil
-      "$PRESENT_VARIABLE =~ /var.*e$/"     | true
-      "$PRESENT_VARIABLE =~ /^var.*/"      | false
-      "$EMPTY_VARIABLE =~ /var.*/"         | false
-      "$UNDEFINED_VARIABLE =~ /var.*/"     | false
-      "$PRESENT_VARIABLE =~ /VAR.*/i"      | true
-      '$PRESENT_VARIABLE != "my variable"' | false
-      '"my variable" != $PRESENT_VARIABLE' | false
-      '$PRESENT_VARIABLE != null'          | true
-      '$EMPTY_VARIABLE != null'            | true
-      '"" != $EMPTY_VARIABLE'              | false
-      '$UNDEFINED_VARIABLE != null'        | false
-      'null != $UNDEFINED_VARIABLE'        | false
-      "$PRESENT_VARIABLE !~ /var.*e$/"     | false
-      "$PRESENT_VARIABLE !~ /^var.*/"      | true
-      "$EMPTY_VARIABLE !~ /var.*/"         | true
-      "$UNDEFINED_VARIABLE !~ /var.*/"     | true
-      "$PRESENT_VARIABLE !~ /VAR.*/i"      | false
-    end
+      where(:expression, :value) do
+        '$PRESENT_VARIABLE == "my variable"'                          | true
+        '"my variable" == $PRESENT_VARIABLE'                          | true
+        '$PRESENT_VARIABLE == null'                                   | false
+        '$EMPTY_VARIABLE == null'                                     | false
+        '"" == $EMPTY_VARIABLE'                                       | true
+        '$EMPTY_VARIABLE'                                             | ''
+        '$UNDEFINED_VARIABLE == null'                                 | true
+        'null == $UNDEFINED_VARIABLE'                                 | true
+        '$PRESENT_VARIABLE'                                           | 'my variable'
+        '$UNDEFINED_VARIABLE'                                         | nil
+        "$PRESENT_VARIABLE =~ /var.*e$/"                              | true
+        "$PRESENT_VARIABLE =~ /^var.*/"                               | false
+        "$EMPTY_VARIABLE =~ /var.*/"                                  | false
+        "$UNDEFINED_VARIABLE =~ /var.*/"                              | false
+        "$PRESENT_VARIABLE =~ /VAR.*/i"                               | true
+        '$PATH_VARIABLE =~ /path/variable/'                           | true
+        '$PATH_VARIABLE =~ /path\/variable/'                          | true
+        '$FULL_PATH_VARIABLE =~ /^/a/full/path/variable/value$/'      | true
+        '$FULL_PATH_VARIABLE =~ /^\/a\/full\/path\/variable\/value$/' | true
+        '$PRESENT_VARIABLE != "my variable"'                          | false
+        '"my variable" != $PRESENT_VARIABLE'                          | false
+        '$PRESENT_VARIABLE != null'                                   | true
+        '$EMPTY_VARIABLE != null'                                     | true
+        '"" != $EMPTY_VARIABLE'                                       | false
+        '$UNDEFINED_VARIABLE != null'                                 | false
+        'null != $UNDEFINED_VARIABLE'                                 | false
+        "$PRESENT_VARIABLE !~ /var.*e$/"                              | false
+        "$PRESENT_VARIABLE !~ /^var.*/"                               | true
+        "$EMPTY_VARIABLE !~ /var.*/"                                  | true
+        "$UNDEFINED_VARIABLE !~ /var.*/"                              | true
+        "$PRESENT_VARIABLE !~ /VAR.*/i"                               | false
+      end
 
-    with_them do
-      let(:text) { expression }
+      with_them do
+        let(:text) { expression }
 
-      it "evaluates to `#{params[:value].inspect}`" do
-        expect(subject.evaluate).to eq value
+        it "evaluates to `#{params[:value].inspect}`" do
+          expect(subject.evaluate).to eq value
+        end
       end
     end
   end
@@ -137,6 +196,8 @@ describe Gitlab::Ci::Pipeline::Expression::Statement do
       '$INVALID = 1'                       | false
       "$PRESENT_VARIABLE =~ /var.*/"       | true
       "$UNDEFINED_VARIABLE =~ /var.*/"     | false
+      "$PRESENT_VARIABLE !~ /var.*/"       | false
+      "$UNDEFINED_VARIABLE !~ /var.*/"     | true
     end
 
     with_them do