Elides the beginning of tab titles that have common prefixes.

BUG=69304
TEST=Make sure the tab titles are displayed as spec'd, and that there isn't any performance issues.
 
Review URL: http://codereview.chromium.org/6579050

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@77860 0039d316-1c4b-4281-b951-d872f2087c98

10 files changed, 303 insertions, 1 deletions

diff --git a/chrome/browser/ui/title_prefix_matcher.cc b/chrome/browser/ui/title_prefix_matcher.cc
new file mode 100644
index 0000000..55e052c
--- /dev/null
+++ b/chrome/browser/ui/title_prefix_matcher.cc
@@ -0,0 +1,96 @@
+// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "chrome/browser/ui/title_prefix_matcher.h"
+
+#include "base/hash_tables.h"
+#include "base/i18n/break_iterator.h"
+#include "base/logging.h"
+
+namespace {
+// We use this value to identify that we have already seen the title associated
+// to this value in the duplicate_titles hash_set, ans marked it as a duplicate.
+const size_t kPreviouslySeenIndex = 0xFFFFFFFF;
+}
+
+TitlePrefixMatcher::TitleInfo::TitleInfo(const string16* title,
+                                         int caller_value)
+    : title(title),
+      prefix_length(0),
+      caller_value(caller_value) {
+  DCHECK(title != NULL);
+}
+
+// static
+void TitlePrefixMatcher::CalculatePrefixLengths(
+    std::vector<TitleInfo>* title_infos) {
+  DCHECK(title_infos != NULL);
+  // This set will contain the indexes of the TitleInfo objects in the vector
+  // that have a duplicate.
+  base::hash_set<size_t> duplicate_titles;
+  // This map is used to identify duplicates by remembering the vector indexes
+  // we have seen with a given title string. The vector index is set to
+  // kPreviouslySeenIndex once we identified duplicates and placed their
+  // indices in duplicate_titles.
+  base::hash_map<string16, size_t> existing_title;
+  // We identify if there are identical titles upfront,
+  // because we don't want to remove prefixes for those at all.
+  // We do it as a separate pass so that we don't need to remove
+  // previously parsed titles when we find a duplicate title later on.
+  for (size_t i = 0; i < title_infos->size(); ++i) {
+    // We use pairs to test existence and insert in one shot.
+    std::pair<base::hash_map<string16, size_t>::iterator, bool> insert_result =
+        existing_title.insert(std::make_pair(*title_infos->at(i).title, i));
+    if (!insert_result.second) {
+      // insert_result.second is false when we insert a duplicate in the set.
+      // insert_result.first is a map iterator and thus
+      // insert_result.first->first is the string title key of the map.
+      DCHECK(*title_infos->at(i).title == insert_result.first->first);
+      duplicate_titles.insert(i);
+      // insert_result.first->second is the value of the title index and if it's
+      // not kPreviouslySeenIndex yet, we must remember it as a duplicate too.
+      if (insert_result.first->second != kPreviouslySeenIndex) {
+        duplicate_titles.insert(insert_result.first->second);
+        insert_result.first->second = kPreviouslySeenIndex;
+      }
+    }
+  }
+
+  // This next loop accumulates all the potential prefixes,
+  // and remember on which titles we saw them.
+  base::hash_map<string16, std::vector<size_t> > prefixes;
+  for (size_t i = 0; i < title_infos->size(); ++i) {
+    // Duplicate titles are not to be included in this process.
+    if (duplicate_titles.find(i) != duplicate_titles.end())
+      continue;
+    const string16* title = title_infos->at(i).title;
+    // We only create prefixes at word boundaries.
+    base::BreakIterator iter(title, base::BreakIterator::BREAK_WORD);
+    // We ignore this title if we can't break it into words, or if it only
+    // contains a single word.
+    if (!iter.Init() || !iter.Advance())
+      continue;
+    // We continue advancing even though we already advanced to the first
+    // word above, so that we can use iter.prev() to identify the end of the
+    // previous word and more easily ignore the last word while iterating.
+    while (iter.Advance()) {
+      if (iter.IsWord())
+        prefixes[title->substr(0, iter.prev())].push_back(i);
+    }
+  }
+
+  // Now we parse the map to find common prefixes
+  // and keep the largest per title.
+  for (base::hash_map<string16, std::vector<size_t> >::iterator iter =
+       prefixes.begin(); iter != prefixes.end(); ++iter) {
+    // iter->first is the prefix string, iter->second is a vector of indices.
+    if (iter->second.size() > 1) {
+      size_t prefix_length = iter->first.size();
+      for (size_t i = 0; i < iter->second.size(); ++i){
+        if (title_infos->at(iter->second[i]).prefix_length < prefix_length)
+          title_infos->at(iter->second[i]).prefix_length = prefix_length;
+      }
+    }
+  }
+}
diff --git a/chrome/browser/ui/title_prefix_matcher.h b/chrome/browser/ui/title_prefix_matcher.h
new file mode 100644
index 0000000..94cbb6d
--- /dev/null
+++ b/chrome/browser/ui/title_prefix_matcher.h
@@ -0,0 +1,46 @@
+// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef CHROME_BROWSER_UI_TITLE_PREFIX_MATCHER_H_
+#define CHROME_BROWSER_UI_TITLE_PREFIX_MATCHER_H_
+#pragma once
+
+#include <vector>
+
+#include "base/string16.h"
+
+// This class exposes a static method that receives a vector of TitleInfo
+// objects so that it can find the length of the common prefixes among all
+// the titles. It can be used for tab titles for example so that the common
+// prefixes can be elided.
+// First, the caller needs to fill a vector of TitleInfo objects with the titles
+// for which they want to find the common prefix lengths. They can also provide
+// an optional caller_value where the index of the tabs could be saved
+// for example. This way the caller can remember which tab this title belongs
+// to, if not all tabs are passed into the vector.
+// When CalculatePrefixLengths returns, the TitleInfo objects in the vector
+// are set with the prefix_length that is common between this title
+// and at least one other.
+// Note that the prefix_length is only calculated at word boundaries.
+class TitlePrefixMatcher {
+ public:
+  struct TitleInfo {
+    TitleInfo(const string16* title, int caller_value);
+    // We assume the title string will be valid throughout the execution of
+    // the prefix lengths calculation, and so we use a pointer to avoid an
+    // unnecessary string copy.
+    const string16* title;
+    // This contains the number of characters at the beginning of title that
+    // are common with other titles in the TitleInfo vector.
+    size_t prefix_length;
+    // Utility data space for the caller. Unused by CalculatePrefixLengths.
+    int caller_value;
+  };
+  static void CalculatePrefixLengths(std::vector<TitleInfo>* title_infos);
+
+ private:
+  DISALLOW_IMPLICIT_CONSTRUCTORS(TitlePrefixMatcher);
+};
+
+#endif  // CHROME_BROWSER_UI_TITLE_PREFIX_MATCHER_H_
diff --git a/chrome/browser/ui/title_prefix_matcher_unittest.cc b/chrome/browser/ui/title_prefix_matcher_unittest.cc
new file mode 100644
index 0000000..5aa4a26
--- /dev/null
+++ b/chrome/browser/ui/title_prefix_matcher_unittest.cc
@@ -0,0 +1,112 @@
+// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "base/logging.h"
+#include "base/utf_string_conversions.h"
+#include "chrome/browser/ui/title_prefix_matcher.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace {
+
+const string16 kFoofooAbcdef(ASCIIToUTF16("Foofoo abcdef"));
+const string16 kFoofooAbcdeg(ASCIIToUTF16("Foofoo abcdeg"));
+const string16 kFooAbcdef(ASCIIToUTF16("Foo abcdef"));
+const string16 kFooAbcdeg(ASCIIToUTF16("Foo abcdeg"));
+const string16 kBarAbcDef(ASCIIToUTF16("Bar abc def"));
+const string16 kBarAbcDeg(ASCIIToUTF16("Bar abc deg"));
+const string16 kBarAbdDef(ASCIIToUTF16("Bar abd def"));
+const string16 kBar(ASCIIToUTF16("Bar"));
+const string16 kFoo(ASCIIToUTF16("Foo"));
+
+}
+
+TEST(TitlePrefixMatcherTest, BasicTests) {
+  std::vector<TitlePrefixMatcher::TitleInfo> tab_title_infos;
+  tab_title_infos.push_back(TitlePrefixMatcher::TitleInfo(&kFoofooAbcdef, 0));
+  tab_title_infos.push_back(TitlePrefixMatcher::TitleInfo(&kFoofooAbcdeg, 1));
+
+  TitlePrefixMatcher::CalculatePrefixLengths(&tab_title_infos);
+  EXPECT_EQ(0, tab_title_infos[0].caller_value);
+  EXPECT_EQ(7U, tab_title_infos[0].prefix_length);
+
+  EXPECT_EQ(1, tab_title_infos[1].caller_value);
+  EXPECT_EQ(7U, tab_title_infos[1].prefix_length);
+
+  tab_title_infos.clear();
+  tab_title_infos.push_back(TitlePrefixMatcher::TitleInfo(&kFoofooAbcdef, 0));
+  tab_title_infos.push_back(TitlePrefixMatcher::TitleInfo(&kFoofooAbcdeg, 1));
+  tab_title_infos.push_back(TitlePrefixMatcher::TitleInfo(&kFooAbcdef, 2));
+  tab_title_infos.push_back(TitlePrefixMatcher::TitleInfo(&kFooAbcdeg, 3));
+
+  TitlePrefixMatcher::CalculatePrefixLengths(&tab_title_infos);
+  EXPECT_EQ(0, tab_title_infos[0].caller_value);
+  EXPECT_EQ(7U, tab_title_infos[0].prefix_length);
+
+  EXPECT_EQ(1, tab_title_infos[1].caller_value);
+  EXPECT_EQ(7U, tab_title_infos[1].prefix_length);
+
+  EXPECT_EQ(2, tab_title_infos[2].caller_value);
+  EXPECT_EQ(4U, tab_title_infos[2].prefix_length);
+
+  EXPECT_EQ(3, tab_title_infos[3].caller_value);
+  EXPECT_EQ(4U, tab_title_infos[3].prefix_length);
+}
+
+TEST(TitlePrefixMatcherTest, Duplicates) {
+  std::vector<TitlePrefixMatcher::TitleInfo> tab_title_infos;
+  tab_title_infos.push_back(TitlePrefixMatcher::TitleInfo(&kFoofooAbcdef, 0));
+  tab_title_infos.push_back(TitlePrefixMatcher::TitleInfo(&kFoofooAbcdeg, 1));
+  tab_title_infos.push_back(TitlePrefixMatcher::TitleInfo(&kFooAbcdef, 2));
+  tab_title_infos.push_back(TitlePrefixMatcher::TitleInfo(&kFooAbcdeg, 3));
+  tab_title_infos.push_back(TitlePrefixMatcher::TitleInfo(&kFoofooAbcdef, 4));
+
+  TitlePrefixMatcher::CalculatePrefixLengths(&tab_title_infos);
+  EXPECT_EQ(0, tab_title_infos[0].caller_value);
+  EXPECT_EQ(0U, tab_title_infos[0].prefix_length);
+
+  EXPECT_EQ(1, tab_title_infos[1].caller_value);
+  EXPECT_EQ(0U, tab_title_infos[1].prefix_length);
+
+  EXPECT_EQ(2, tab_title_infos[2].caller_value);
+  EXPECT_EQ(4U, tab_title_infos[2].prefix_length);
+
+  EXPECT_EQ(3, tab_title_infos[3].caller_value);
+  EXPECT_EQ(4U, tab_title_infos[3].prefix_length);
+
+  EXPECT_EQ(4, tab_title_infos[4].caller_value);
+  EXPECT_EQ(0U, tab_title_infos[4].prefix_length);
+}
+
+TEST(TitlePrefixMatcherTest, MultiplePrefixes) {
+  std::vector<TitlePrefixMatcher::TitleInfo> tab_title_infos;
+  tab_title_infos.push_back(TitlePrefixMatcher::TitleInfo(&kFooAbcdef, 0));
+  tab_title_infos.push_back(TitlePrefixMatcher::TitleInfo(&kFooAbcdeg, 1));
+  tab_title_infos.push_back(TitlePrefixMatcher::TitleInfo(&kBarAbcDef, 2));
+  tab_title_infos.push_back(TitlePrefixMatcher::TitleInfo(&kBarAbcDeg, 3));
+  tab_title_infos.push_back(TitlePrefixMatcher::TitleInfo(&kBarAbdDef, 4));
+  tab_title_infos.push_back(TitlePrefixMatcher::TitleInfo(&kBar, 5));
+  tab_title_infos.push_back(TitlePrefixMatcher::TitleInfo(&kFoo, 6));
+
+  TitlePrefixMatcher::CalculatePrefixLengths(&tab_title_infos);
+  EXPECT_EQ(0, tab_title_infos[0].caller_value);
+  EXPECT_EQ(4U, tab_title_infos[0].prefix_length);
+
+  EXPECT_EQ(1, tab_title_infos[1].caller_value);
+  EXPECT_EQ(4U, tab_title_infos[1].prefix_length);
+
+  EXPECT_EQ(2, tab_title_infos[2].caller_value);
+  EXPECT_EQ(8U, tab_title_infos[2].prefix_length);
+
+  EXPECT_EQ(3, tab_title_infos[3].caller_value);
+  EXPECT_EQ(8U, tab_title_infos[3].prefix_length);
+
+  EXPECT_EQ(4, tab_title_infos[4].caller_value);
+  EXPECT_EQ(4U, tab_title_infos[4].prefix_length);
+
+  EXPECT_EQ(5, tab_title_infos[5].caller_value);
+  EXPECT_EQ(0U, tab_title_infos[5].prefix_length);
+
+  EXPECT_EQ(6, tab_title_infos[6].caller_value);
+  EXPECT_EQ(0U, tab_title_infos[6].prefix_length);
+}
diff --git a/chrome/browser/ui/views/tabs/base_tab.cc b/chrome/browser/ui/views/tabs/base_tab.cc
index e6d6bc8..4eb08b6 100644
--- a/chrome/browser/ui/views/tabs/base_tab.cc
+++ b/chrome/browser/ui/views/tabs/base_tab.cc
@@ -21,6 +21,7 @@
 #include "ui/base/animation/throb_animation.h"
 #include "ui/base/l10n/l10n_util.h"
 #include "ui/base/resource/resource_bundle.h"
+#include "ui/base/text/text_elider.h"
 #include "ui/base/theme_provider.h"
 #include "ui/gfx/canvas_skia.h"
 #include "ui/gfx/favicon_size.h"
@@ -442,6 +443,7 @@ void BaseTab::PaintIcon(gfx::Canvas* canvas) {
 
 void BaseTab::PaintTitle(gfx::Canvas* canvas, SkColor title_color) {
   // Paint the Title.
+  const gfx::Rect& title_bounds = GetTitleBounds();
   string16 title = data().title;
   if (title.empty()) {
     title = data().loading ?
@@ -449,8 +451,15 @@ void BaseTab::PaintTitle(gfx::Canvas* canvas, SkColor title_color) {
         TabContentsWrapper::GetDefaultTitle();
   } else {
     Browser::FormatTitleForDisplay(&title);
+    // If we'll need to truncate, check if we should also truncate
+    // a common prefix, but only if there is enough room for it.
+    // We arbitrarily choose to request enough room for 10 average chars.
+    if (data().common_prefix_length > 0 &&
+        font_->GetExpectedTextWidth(10) < title_bounds.width() &&
+        font_->GetStringWidth(title) > title_bounds.width()) {
+      title.replace(0, data().common_prefix_length, UTF8ToUTF16(ui::kEllipsis));
+    }
   }
-  const gfx::Rect& title_bounds = GetTitleBounds();
   canvas->DrawStringInt(title, *font_, title_color,
                         title_bounds.x(), title_bounds.y(),
                         title_bounds.width(), title_bounds.height());
diff --git a/chrome/browser/ui/views/tabs/base_tab_strip.cc b/chrome/browser/ui/views/tabs/base_tab_strip.cc
index 8809641..3d476b2 100644
--- a/chrome/browser/ui/views/tabs/base_tab_strip.cc
+++ b/chrome/browser/ui/views/tabs/base_tab_strip.cc
@@ -5,6 +5,7 @@
 #include "chrome/browser/ui/views/tabs/base_tab_strip.h"
 
 #include "base/logging.h"
+#include "chrome/browser/ui/title_prefix_matcher.h"
 #include "chrome/browser/ui/view_ids.h"
 #include "chrome/browser/ui/views/tabs/dragged_tab_controller.h"
 #include "chrome/browser/ui/views/tabs/tab_strip_controller.h"
@@ -137,6 +138,7 @@ void BaseTabStrip::AddTabAt(int model_index,
 
   TabData d = { tab, gfx::Rect() };
   tab_data_.insert(tab_data_.begin() + ModelIndexToTabIndex(model_index), d);
+  UpdateCommonTitlePrefix();
 
   AddChildView(tab);
 
@@ -167,6 +169,7 @@ void BaseTabStrip::SetTabData(int model_index, const TabRendererData& data) {
   BaseTab* tab = GetBaseTabAtModelIndex(model_index);
   bool mini_state_changed = tab->data().mini != data.mini;
   tab->SetData(data);
+  UpdateCommonTitlePrefix();
 
   if (mini_state_changed) {
     if (GetWindow() && GetWindow()->IsVisible())
@@ -425,6 +428,30 @@ void BaseTabStrip::RemoveAndDeleteTab(BaseTab* tab) {
   tab_data_.erase(tab_data_.begin() + tab_data_index);
 
   delete tab;
+  UpdateCommonTitlePrefix();
+}
+
+void BaseTabStrip::UpdateCommonTitlePrefix() {
+  std::vector<TitlePrefixMatcher::TitleInfo> tab_title_infos;
+  for (int tab_index = 0; tab_index < tab_count(); ++tab_index) {
+    DCHECK(tab_data_[tab_index].tab != NULL);
+    if (!tab_data_[tab_index].tab->data().mini &&
+        !tab_data_[tab_index].tab->data().title.empty()) {
+      tab_title_infos.push_back(TitlePrefixMatcher::TitleInfo(
+          &tab_data_[tab_index].tab->data().title, tab_index));
+    }
+  }
+  TitlePrefixMatcher::CalculatePrefixLengths(&tab_title_infos);
+  for (size_t title_index = 0; title_index < tab_title_infos.size();
+       ++title_index) {
+    int tab_index = tab_title_infos[title_index].caller_value;
+    TabRendererData data = tab_data_[tab_index].tab->data();
+    if (data.common_prefix_length !=
+        tab_title_infos[title_index].prefix_length) {
+      data.common_prefix_length = tab_title_infos[title_index].prefix_length;
+      tab_data_[tab_index].tab->SetData(data);
+    }
+  }
 }
 
 int BaseTabStrip::TabIndexOfTab(BaseTab* tab) const {
diff --git a/chrome/browser/ui/views/tabs/base_tab_strip.h b/chrome/browser/ui/views/tabs/base_tab_strip.h
index 3e4581e..e7e8c10 100644
--- a/chrome/browser/ui/views/tabs/base_tab_strip.h
+++ b/chrome/browser/ui/views/tabs/base_tab_strip.h
@@ -191,6 +191,10 @@ class BaseTabStrip : public AbstractTabStripView,
     tab_data_[index].ideal_bounds = bounds;
   }
 
+  // Update the lengths of common title prefixes for all tabs. This needs
+  // to be done every time tabs are added/removed or when titles change.
+  virtual void UpdateCommonTitlePrefix();
+
   // Returns the index into |tab_data_| corresponding to the specified tab, or
   // -1 if the tab isn't in |tab_data_|.
   int TabIndexOfTab(BaseTab* tab) const;
diff --git a/chrome/browser/ui/views/tabs/tab_renderer_data.cc b/chrome/browser/ui/views/tabs/tab_renderer_data.cc
index 47f96d6..fae7114 100644
--- a/chrome/browser/ui/views/tabs/tab_renderer_data.cc
+++ b/chrome/browser/ui/views/tabs/tab_renderer_data.cc
@@ -6,6 +6,7 @@
 
 TabRendererData::TabRendererData()
     : network_state(NETWORK_STATE_NONE),
+      common_prefix_length(0),
       loading(false),
       crashed_status(base::TERMINATION_STATUS_STILL_RUNNING),
       off_the_record(false),
@@ -24,6 +25,7 @@ bool TabRendererData::Equals(const TabRendererData& data) {
       favicon.pixelRefOffset() == data.favicon.pixelRefOffset() &&
       network_state == data.network_state &&
       title == data.title &&
+      common_prefix_length == data.common_prefix_length &&
       loading == data.loading &&
       crashed_status == data.crashed_status &&
       off_the_record == data.off_the_record &&
diff --git a/chrome/browser/ui/views/tabs/tab_renderer_data.h b/chrome/browser/ui/views/tabs/tab_renderer_data.h
index 28b55fc..49af30a 100644
--- a/chrome/browser/ui/views/tabs/tab_renderer_data.h
+++ b/chrome/browser/ui/views/tabs/tab_renderer_data.h
@@ -40,6 +40,9 @@ struct TabRendererData {
   SkBitmap favicon;
   NetworkState network_state;
   string16 title;
+  // Identifies the number of chars at the beginning of the string
+  // that are common to other tab titles.
+  size_t common_prefix_length;
   bool loading;
   base::TerminationStatus crashed_status;
   bool off_the_record;
diff --git a/chrome/chrome_browser.gypi b/chrome/chrome_browser.gypi
index 849ff3c..d21d2cc 100644
--- a/chrome/chrome_browser.gypi
+++ b/chrome/chrome_browser.gypi
@@ -2784,6 +2784,8 @@
         'browser/ui/tabs/dock_info_win.cc',
         'browser/ui/tabs/tab_menu_model.cc',
         'browser/ui/tabs/tab_menu_model.h',
+        'browser/ui/title_prefix_matcher.cc',
+        'browser/ui/title_prefix_matcher.h',
         'browser/ui/toolbar/back_forward_menu_model.cc',
         'browser/ui/toolbar/back_forward_menu_model.h',
         'browser/ui/toolbar/encoding_menu_controller.cc',
diff --git a/chrome/chrome_tests.gypi b/chrome/chrome_tests.gypi
index a7f0314..8285db2 100644
--- a/chrome/chrome_tests.gypi
+++ b/chrome/chrome_tests.gypi
@@ -1679,6 +1679,7 @@
         'browser/ui/tabs/tab_menu_model_unittest.cc',
         'browser/ui/tests/ui_gfx_image_unittest.cc',
         'browser/ui/tests/ui_gfx_image_unittest.mm',
+        'browser/ui/title_prefix_matcher_unittest.cc',
         'browser/ui/toolbar/back_forward_menu_model_unittest.cc',
         'browser/ui/toolbar/encoding_menu_controller_unittest.cc',
         'browser/ui/toolbar/wrench_menu_model_unittest.cc',