Build a recursive parser for pipeline expressions

9 files changed, 61 insertions, 18 deletions

diff --git a/lib/gitlab/ci/pipeline/expression/equals.rb b/lib/gitlab/ci/pipeline/expression/equals.rb
index 46b8ebb63e3..93883982b63 100644
--- a/lib/gitlab/ci/pipeline/expression/equals.rb
+++ b/lib/gitlab/ci/pipeline/expression/equals.rb
@@ -4,6 +4,7 @@ module Gitlab
       module Expression
         class Equals < Expression::Lexeme
           PATTERN = /==/.freeze
+          TYPE = :operator
 
           def initialize(left, right)
             @left = left
@@ -13,6 +14,10 @@ module Gitlab
           def evaluate(**variables)
             @left.evaluate(variables) == @right.evaluate(variables)
           end
+
+          def self.build(value, behind, ahead)
+            new(behind, ahead)
+          end
         end
       end
     end
diff --git a/lib/gitlab/ci/pipeline/expression/lexeme.rb b/lib/gitlab/ci/pipeline/expression/lexeme.rb
index 91ba333d8dd..d44bf9e419d 100644
--- a/lib/gitlab/ci/pipeline/expression/lexeme.rb
+++ b/lib/gitlab/ci/pipeline/expression/lexeme.rb
@@ -11,6 +11,10 @@ module Gitlab
             raise NotImplementedError
           end
 
+          def self.type
+            self::TYPE
+          end
+
           def self.scan(scanner)
             if scanner.scan(self::PATTERN)
               Expression::Token.new(scanner.matched, self)
diff --git a/lib/gitlab/ci/pipeline/expression/null.rb b/lib/gitlab/ci/pipeline/expression/null.rb
index ae5ab7f37d0..a70cdd5fc73 100644
--- a/lib/gitlab/ci/pipeline/expression/null.rb
+++ b/lib/gitlab/ci/pipeline/expression/null.rb
@@ -4,6 +4,7 @@ module Gitlab
       module Expression
         class Null < Expression::Lexeme
           PATTERN = /null/.freeze
+          TYPE = :value
 
           def initialize(value)
             @value = value
diff --git a/lib/gitlab/ci/pipeline/expression/parser.rb b/lib/gitlab/ci/pipeline/expression/parser.rb
index f3201ec0979..6eb77351dcf 100644
--- a/lib/gitlab/ci/pipeline/expression/parser.rb
+++ b/lib/gitlab/ci/pipeline/expression/parser.rb
@@ -3,20 +3,31 @@ module Gitlab
     module Pipeline
       module Expression
         class Parser
-          def initialize(syntax)
-            if syntax.is_a?(Expression::Lexer)
-              @tokens = syntax.tokens
-            else
-              @tokens = syntax.to_a
-            end
+          def initialize(tokens)
+            # raise ArgumentError unless tokens.enumerator?
+
+            @tokens = tokens
+            @nodes = []
           end
 
           def tree
-            if @tokens.many?
-              Expression::Equals.new(@tokens.first.build, @tokens.last.build)
-            else
-              @tokens.first.build
+            while token = @tokens.next
+              case token.type
+              when :operator
+                lookbehind = @nodes.last
+                lookahead = Parser.new(@tokens).tree
+
+                token.build(lookbehind, lookahead).tap do |node|
+                  @nodes.push(node)
+                end
+              when :value
+                token.build.tap do |leaf|
+                  @nodes.push(leaf)
+                end
+              end
             end
+          rescue StopIteration
+            @nodes.last
           end
         end
       end
diff --git a/lib/gitlab/ci/pipeline/expression/statement.rb b/lib/gitlab/ci/pipeline/expression/statement.rb
index e1e37f0f5cb..07b84c89899 100644
--- a/lib/gitlab/ci/pipeline/expression/statement.rb
+++ b/lib/gitlab/ci/pipeline/expression/statement.rb
@@ -15,7 +15,6 @@ module Gitlab
           ].freeze
 
           def initialize(statement, pipeline)
-            @pipeline = pipeline
             @lexer = Expression::Lexer.new(statement)
 
             @variables = pipeline.variables.map do |variable|
@@ -30,7 +29,7 @@ module Gitlab
               raise StatementError, 'Unknown pipeline expression!'
             end
 
-            Expression::Parser.new(@lexer).tree
+            Expression::Parser.new(@lexer.tokens.to_enum).tree
           end
 
           def evaluate
diff --git a/lib/gitlab/ci/pipeline/expression/string.rb b/lib/gitlab/ci/pipeline/expression/string.rb
index 6a59b81467c..bbd75cb4632 100644
--- a/lib/gitlab/ci/pipeline/expression/string.rb
+++ b/lib/gitlab/ci/pipeline/expression/string.rb
@@ -4,6 +4,7 @@ module Gitlab
       module Expression
         class String < Expression::Lexeme
           PATTERN = /"(?<string>.+?)"/.freeze
+          TYPE = :value
 
           def initialize(value)
             @value = value
diff --git a/lib/gitlab/ci/pipeline/expression/token.rb b/lib/gitlab/ci/pipeline/expression/token.rb
index 3b957c83016..58211800b88 100644
--- a/lib/gitlab/ci/pipeline/expression/token.rb
+++ b/lib/gitlab/ci/pipeline/expression/token.rb
@@ -3,19 +3,23 @@ module Gitlab
     module Pipeline
       module Expression
         class Token
-          attr_reader :value, :type
+          attr_reader :value, :lexeme
 
-          def initialize(value, type)
+          def initialize(value, lexeme)
             @value = value
-            @type = type
+            @lexeme = lexeme
           end
 
-          def build
-            @type.build(@value)
+          def build(*args)
+            @lexeme.build(@value, *args)
+          end
+
+          def type
+            @lexeme.type
           end
 
           def to_lexeme
-            type.name.demodulize.downcase
+            @lexeme.name.demodulize.downcase
           end
         end
       end
diff --git a/lib/gitlab/ci/pipeline/expression/variable.rb b/lib/gitlab/ci/pipeline/expression/variable.rb
index d6a7a655220..379f8168ca9 100644
--- a/lib/gitlab/ci/pipeline/expression/variable.rb
+++ b/lib/gitlab/ci/pipeline/expression/variable.rb
@@ -4,6 +4,7 @@ module Gitlab
       module Expression
         class Variable < Expression::Lexeme
           PATTERN = /\$(?<name>\w+)/.freeze
+          TYPE = :value
 
           def initialize(name)
             @name = name
diff --git a/spec/lib/gitlab/ci/pipeline/expression/parser_spec.rb b/spec/lib/gitlab/ci/pipeline/expression/parser_spec.rb
index 180b6908fb5..c70bcc8438c 100644
--- a/spec/lib/gitlab/ci/pipeline/expression/parser_spec.rb
+++ b/spec/lib/gitlab/ci/pipeline/expression/parser_spec.rb
@@ -2,5 +2,22 @@ require 'spec_helper'
 
 describe Gitlab::Ci::Pipeline::Expression::Parser do
   describe '#tree' do
+    context 'when using an operator' do
+      it 'returns a reverse descent parse tree' do
+        expect(described_class.new(tokens('$VAR == "123"')).tree)
+          .to be_a Gitlab::Ci::Pipeline::Expression::Equals
+      end
+    end
+
+    context 'when using a single token' do
+      it 'returns a single token instance' do
+        expect(described_class.new(tokens('$VAR')).tree)
+          .to be_a Gitlab::Ci::Pipeline::Expression::Variable
+      end
+    end
+  end
+
+  def tokens(statement)
+    Gitlab::Ci::Pipeline::Expression::Lexer.new(statement).tokens.to_enum
   end
 end