Merge branch 'fuzzy-issue-search' into 'master'

Fuzzy search issues / merge requests

Closes #26835, #29994, and #20362

See merge request !13780

9 files changed, 211 insertions, 26 deletions

diff --git a/app/models/concerns/issuable.rb b/app/models/concerns/issuable.rb
index 3731b7c8577..681c3241dbb 100644
--- a/app/models/concerns/issuable.rb
+++ b/app/models/concerns/issuable.rb
@@ -6,6 +6,7 @@
 #
 module Issuable
   extend ActiveSupport::Concern
+  include Gitlab::SQL::Pattern
   include CacheMarkdownField
   include Participable
   include Mentionable
@@ -122,7 +123,9 @@ module Issuable
     #
     # Returns an ActiveRecord::Relation.
     def search(query)
-      where(arel_table[:title].matches("%#{query}%"))
+      title = to_fuzzy_arel(:title, query)
+
+      where(title)
     end
 
     # Searches for records with a matching title or description.
@@ -133,10 +136,10 @@ module Issuable
     #
     # Returns an ActiveRecord::Relation.
     def full_search(query)
-      t = arel_table
-      pattern = "%#{query}%"
+      title = to_fuzzy_arel(:title, query)
+      description = to_fuzzy_arel(:description, query)
 
-      where(t[:title].matches(pattern).or(t[:description].matches(pattern)))
+      where(title&.or(description))
     end
 
     def sort(method, excluded_labels: [])
diff --git a/changelogs/unreleased/fuzzy-issue-search.yml b/changelogs/unreleased/fuzzy-issue-search.yml
new file mode 100644
index 00000000000..8195e97ed59
--- /dev/null
+++ b/changelogs/unreleased/fuzzy-issue-search.yml
@@ -0,0 +1,5 @@
+---
+title: Support a multi-word fuzzy seach issues/merge requests on search bar
+merge_request: 13780
+author: Hiroyuki Sato
+type: changed
diff --git a/doc/user/search/img/issue_search_by_term.png b/doc/user/search/img/issue_search_by_term.png
new file mode 100644
index 00000000000..66e612c4ea6
--- /dev/null
+++ b/doc/user/search/img/issue_search_by_term.png
diff --git a/doc/user/search/index.md b/doc/user/search/index.md
index f5c7ce49e8e..21e96d8b11c 100644
--- a/doc/user/search/index.md
+++ b/doc/user/search/index.md
@@ -40,6 +40,20 @@ The same process is valid for merge requests. Navigate to your project's **Merge
 and click **Search or filter results...**. Merge requests can be filtered by author, assignee,
 milestone, and label.
 
+### Searching for specific terms
+
+You can filter issues and merge requests by specific terms included in titles or descriptions.
+
+* Syntax
+    * Searches look for all the words in a query, in any order. E.g.: searching
+      issues for `display bug` will return all issues matching both those words, in any order.
+    * To find the exact term, use double quotes: `"display bug"`
+* Limitation
+    * For performance reasons, terms shorter than 3 chars are ignored. E.g.: searching
+      issues for `included in titles` is same as `included titles`
+
+![filter issues by specific terms](img/issue_search_by_term.png)
+
 ### Issues and merge requests per group
 
 Similar to **Issues and merge requests per project**, you can also search for issues
diff --git a/lib/gitlab/sql/pattern.rb b/lib/gitlab/sql/pattern.rb
index b42bc67ccfc..7c2d1d8f887 100644
--- a/lib/gitlab/sql/pattern.rb
+++ b/lib/gitlab/sql/pattern.rb
@@ -4,6 +4,7 @@ module Gitlab
       extend ActiveSupport::Concern
 
       MIN_CHARS_FOR_PARTIAL_MATCHING = 3
+      REGEX_QUOTED_WORD = /(?<=^| )"[^"]+"(?= |$)/
 
       class_methods do
         def to_pattern(query)
@@ -17,6 +18,28 @@ module Gitlab
         def partial_matching?(query)
           query.length >= MIN_CHARS_FOR_PARTIAL_MATCHING
         end
+
+        def to_fuzzy_arel(column, query)
+          words = select_fuzzy_words(query)
+
+          matches = words.map { |word| arel_table[column].matches(to_pattern(word)) }
+
+          matches.reduce { |result, match| result.and(match) }
+        end
+
+        def select_fuzzy_words(query)
+          quoted_words = query.scan(REGEX_QUOTED_WORD)
+
+          query = quoted_words.reduce(query) { |q, quoted_word| q.sub(quoted_word, '') }
+
+          words = query.split(/\s+/)
+
+          quoted_words.map! { |quoted_word| quoted_word[1..-2] }
+
+          words.concat(quoted_words)
+
+          words.select { |word| partial_matching?(word) }
+        end
       end
     end
   end
diff --git a/spec/features/boards/add_issues_modal_spec.rb b/spec/features/boards/add_issues_modal_spec.rb
index a6ad5981f8f..c480b5b7e34 100644
--- a/spec/features/boards/add_issues_modal_spec.rb
+++ b/spec/features/boards/add_issues_modal_spec.rb
@@ -8,8 +8,8 @@ describe 'Issue Boards add issue modal', :js do
   let!(:label) { create(:label, project: project) }
   let!(:list1) { create(:list, board: board, label: planning, position: 0) }
   let!(:list2) { create(:list, board: board, label: label, position: 1) }
-  let!(:issue) { create(:issue, project: project) }
-  let!(:issue2) { create(:issue, project: project) }
+  let!(:issue) { create(:issue, project: project, title: 'abc', description: 'def') }
+  let!(:issue2) { create(:issue, project: project, title: 'hij', description: 'klm') }
 
   before do
     project.team << [user, :master]
diff --git a/spec/features/boards/boards_spec.rb b/spec/features/boards/boards_spec.rb
index 913258ca40f..e010b5f3444 100644
--- a/spec/features/boards/boards_spec.rb
+++ b/spec/features/boards/boards_spec.rb
@@ -73,15 +73,15 @@ describe 'Issue Boards', js: true do
     let!(:list2) { create(:list, board: board, label: development, position: 1) }
 
     let!(:confidential_issue) { create(:labeled_issue, :confidential, project: project, author: user, labels: [planning], relative_position: 9) }
-    let!(:issue1) { create(:labeled_issue, project: project, assignees: [user], labels: [planning], relative_position: 8) }
-    let!(:issue2) { create(:labeled_issue, project: project, author: user2, labels: [planning], relative_position: 7) }
-    let!(:issue3) { create(:labeled_issue, project: project, labels: [planning], relative_position: 6) }
-    let!(:issue4) { create(:labeled_issue, project: project, labels: [planning], relative_position: 5) }
-    let!(:issue5) { create(:labeled_issue, project: project, labels: [planning], milestone: milestone, relative_position: 4) }
-    let!(:issue6) { create(:labeled_issue, project: project, labels: [planning, development], relative_position: 3) }
-    let!(:issue7) { create(:labeled_issue, project: project, labels: [development], relative_position: 2) }
-    let!(:issue8) { create(:closed_issue, project: project) }
-    let!(:issue9) { create(:labeled_issue, project: project, labels: [planning, testing, bug, accepting], relative_position: 1) }
+    let!(:issue1) { create(:labeled_issue, project: project, title: 'aaa', description: '111', assignees: [user], labels: [planning], relative_position: 8) }
+    let!(:issue2) { create(:labeled_issue, project: project, title: 'bbb', description: '222', author: user2, labels: [planning], relative_position: 7) }
+    let!(:issue3) { create(:labeled_issue, project: project, title: 'ccc', description: '333', labels: [planning], relative_position: 6) }
+    let!(:issue4) { create(:labeled_issue, project: project, title: 'ddd', description: '444', labels: [planning], relative_position: 5) }
+    let!(:issue5) { create(:labeled_issue, project: project, title: 'eee', description: '555', labels: [planning], milestone: milestone, relative_position: 4) }
+    let!(:issue6) { create(:labeled_issue, project: project, title: 'fff', description: '666', labels: [planning, development], relative_position: 3) }
+    let!(:issue7) { create(:labeled_issue, project: project, title: 'ggg', description: '777', labels: [development], relative_position: 2) }
+    let!(:issue8) { create(:closed_issue, project: project, title: 'hhh', description: '888') }
+    let!(:issue9) { create(:labeled_issue, project: project, title: 'iii', description: '999', labels: [planning, testing, bug, accepting], relative_position: 1) }
 
     before do
       visit project_board_path(project, board)
diff --git a/spec/lib/gitlab/sql/pattern_spec.rb b/spec/lib/gitlab/sql/pattern_spec.rb
index 9d7b2136dab..48d56628ed5 100644
--- a/spec/lib/gitlab/sql/pattern_spec.rb
+++ b/spec/lib/gitlab/sql/pattern_spec.rb
@@ -52,4 +52,124 @@ describe Gitlab::SQL::Pattern do
       end
     end
   end
+
+  describe '.select_fuzzy_words' do
+    subject(:select_fuzzy_words) { Issue.select_fuzzy_words(query) }
+
+    context 'with a word equal to 3 chars' do
+      let(:query) { 'foo' }
+
+      it 'returns array cotaining a word' do
+        expect(select_fuzzy_words).to match_array(['foo'])
+      end
+    end
+
+    context 'with a word shorter than 3 chars' do
+      let(:query) { 'fo' }
+
+      it 'returns empty array' do
+        expect(select_fuzzy_words).to match_array([])
+      end
+    end
+
+    context 'with two words both equal to 3 chars' do
+      let(:query) { 'foo baz' }
+
+      it 'returns array containing two words' do
+        expect(select_fuzzy_words).to match_array(%w[foo baz])
+      end
+    end
+
+    context 'with two words divided by two spaces both equal to 3 chars' do
+      let(:query) { 'foo  baz' }
+
+      it 'returns array containing two words' do
+        expect(select_fuzzy_words).to match_array(%w[foo baz])
+      end
+    end
+
+    context 'with two words equal to 3 chars and shorter than 3 chars' do
+      let(:query) { 'foo ba' }
+
+      it 'returns array containing a word' do
+        expect(select_fuzzy_words).to match_array(['foo'])
+      end
+    end
+
+    context 'with a multi-word surrounded by double quote' do
+      let(:query) { '"really bar"' }
+
+      it 'returns array containing a multi-word' do
+        expect(select_fuzzy_words).to match_array(['really bar'])
+      end
+    end
+
+    context 'with a multi-word surrounded by double quote and two words' do
+      let(:query) { 'foo "really bar" baz' }
+
+      it 'returns array containing a multi-word and tow words' do
+        expect(select_fuzzy_words).to match_array(['foo', 'really bar', 'baz'])
+      end
+    end
+
+    context 'with a multi-word surrounded by double quote missing a spece before the first double quote' do
+      let(:query) { 'foo"really bar"' }
+
+      it 'returns array containing two words with double quote' do
+        expect(select_fuzzy_words).to match_array(['foo"really', 'bar"'])
+      end
+    end
+
+    context 'with a multi-word surrounded by double quote missing a spece after the second double quote' do
+      let(:query) { '"really bar"baz' }
+
+      it 'returns array containing two words with double quote' do
+        expect(select_fuzzy_words).to match_array(['"really', 'bar"baz'])
+      end
+    end
+
+    context 'with two multi-word surrounded by double quote and two words' do
+      let(:query) { 'foo "really bar" baz "awesome feature"' }
+
+      it 'returns array containing two multi-words and tow words' do
+        expect(select_fuzzy_words).to match_array(['foo', 'really bar', 'baz', 'awesome feature'])
+      end
+    end
+  end
+
+  describe '.to_fuzzy_arel' do
+    subject(:to_fuzzy_arel) { Issue.to_fuzzy_arel(:title, query) }
+
+    context 'with a word equal to 3 chars' do
+      let(:query) { 'foo' }
+
+      it 'returns a single ILIKE condition' do
+        expect(to_fuzzy_arel.to_sql).to match(/title.*I?LIKE '\%foo\%'/)
+      end
+    end
+
+    context 'with a word shorter than 3 chars' do
+      let(:query) { 'fo' }
+
+      it 'returns nil' do
+        expect(to_fuzzy_arel).to be_nil
+      end
+    end
+
+    context 'with two words both equal to 3 chars' do
+      let(:query) { 'foo baz' }
+
+      it 'returns a joining LIKE condition using a AND' do
+        expect(to_fuzzy_arel.to_sql).to match(/title.+I?LIKE '\%foo\%' AND .*title.*I?LIKE '\%baz\%'/)
+      end
+    end
+
+    context 'with a multi-word surrounded by double quote and two words' do
+      let(:query) { 'foo "really bar" baz' }
+
+      it 'returns a joining LIKE condition using a AND' do
+        expect(to_fuzzy_arel.to_sql).to match(/title.+I?LIKE '\%foo\%' AND .*title.*I?LIKE '\%baz\%' AND .*title.*I?LIKE '\%really bar\%'/)
+      end
+    end
+  end
 end
diff --git a/spec/models/concerns/issuable_spec.rb b/spec/models/concerns/issuable_spec.rb
index dfbe1a7c192..37f6fd3a25b 100644
--- a/spec/models/concerns/issuable_spec.rb
+++ b/spec/models/concerns/issuable_spec.rb
@@ -66,56 +66,76 @@ describe Issuable do
   end
 
   describe ".search" do
-    let!(:searchable_issue) { create(:issue, title: "Searchable issue") }
+    let!(:searchable_issue) { create(:issue, title: "Searchable awesome issue") }
 
-    it 'returns notes with a matching title' do
+    it 'returns issues with a matching title' do
       expect(issuable_class.search(searchable_issue.title))
         .to eq([searchable_issue])
     end
 
-    it 'returns notes with a partially matching title' do
+    it 'returns issues with a partially matching title' do
       expect(issuable_class.search('able')).to eq([searchable_issue])
     end
 
-    it 'returns notes with a matching title regardless of the casing' do
+    it 'returns issues with a matching title regardless of the casing' do
       expect(issuable_class.search(searchable_issue.title.upcase))
         .to eq([searchable_issue])
     end
+
+    it 'returns issues with a fuzzy matching title' do
+      expect(issuable_class.search('searchable issue')).to eq([searchable_issue])
+    end
+
+    it 'returns all issues with a query shorter than 3 chars' do
+      expect(issuable_class.search('zz')).to eq(issuable_class.all)
+    end
   end
 
   describe ".full_search" do
     let!(:searchable_issue) do
-      create(:issue, title: "Searchable issue", description: 'kittens')
+      create(:issue, title: "Searchable awesome issue", description: 'Many cute kittens')
     end
 
-    it 'returns notes with a matching title' do
+    it 'returns issues with a matching title' do
       expect(issuable_class.full_search(searchable_issue.title))
         .to eq([searchable_issue])
     end
 
-    it 'returns notes with a partially matching title' do
+    it 'returns issues with a partially matching title' do
       expect(issuable_class.full_search('able')).to eq([searchable_issue])
     end
 
-    it 'returns notes with a matching title regardless of the casing' do
+    it 'returns issues with a matching title regardless of the casing' do
       expect(issuable_class.full_search(searchable_issue.title.upcase))
         .to eq([searchable_issue])
     end
 
-    it 'returns notes with a matching description' do
+    it 'returns issues with a fuzzy matching title' do
+      expect(issuable_class.full_search('searchable issue')).to eq([searchable_issue])
+    end
+
+    it 'returns issues with a matching description' do
       expect(issuable_class.full_search(searchable_issue.description))
         .to eq([searchable_issue])
     end
 
-    it 'returns notes with a partially matching description' do
+    it 'returns issues with a partially matching description' do
       expect(issuable_class.full_search(searchable_issue.description))
         .to eq([searchable_issue])
     end
 
-    it 'returns notes with a matching description regardless of the casing' do
+    it 'returns issues with a matching description regardless of the casing' do
       expect(issuable_class.full_search(searchable_issue.description.upcase))
         .to eq([searchable_issue])
     end
+
+    it 'returns issues with a fuzzy matching description' do
+      expect(issuable_class.full_search('many kittens')).to eq([searchable_issue])
+    end
+
+    it 'returns all issues with a query shorter than 3 chars' do
+      expect(issuable_class.search('zz')).to eq(issuable_class.all)
+    end
   end
 
   describe '.to_ability_name' do