# HG changeset patch
# User Yuya Nishihara <yuya@tcha.org>
# Date 2016-10-25 12:49:30
# Node ID 362740e054609d55dea1403ce5fdfcb1379403fb
# Parent  741e5d7f282da2ce85b13792d86c902ee64fc3c5

templater: use unfiltered changelog to calculate shortest() at constant time

cl._partialmatch() can be pretty slow if hidden revisions are involved. This
patch cancels the slowdown introduced by the previous patch by using an
unfiltered changelog, which means shortest(node) isn't always the shortest.

The result isn't perfect, but seems okay as long as shortest(node) is short
enough to type and can be used as an identifier.

  (with hidden revisions)
  % hg log -R hg-committed -r0:20000 -T '{node|shortest}\n' --time > /dev/null
  (.^^) time: real 1.530 secs (user 1.480+0.000 sys 0.040+0.000)
  (.^)  time: real 43.080 secs (user 43.060+0.000 sys 0.030+0.000)
  (.)   time: real 1.680 secs (user 1.650+0.000 sys 0.020+0.000)

diff --git a/mercurial/templater.py b/mercurial/templater.py
--- a/mercurial/templater.py
+++ b/mercurial/templater.py
@@ -837,7 +837,10 @@ def shortest(context, mapping, args):
                                 # i18n: "shortest" is a keyword
                                 _("shortest() expects an integer minlength"))
 
-    cl = mapping['ctx']._repo.changelog
+    # _partialmatch() of filtered changelog could take O(len(repo)) time,
+    # which would be unacceptably slow. so we look for hash collision in
+    # unfiltered space, which means some hashes may be slightly longer.
+    cl = mapping['ctx']._repo.unfiltered().changelog
     def isvalid(test):
         try:
             if cl._partialmatch(test) is None:
diff --git a/tests/test-command-template.t b/tests/test-command-template.t
--- a/tests/test-command-template.t
+++ b/tests/test-command-template.t
@@ -3469,9 +3469,10 @@ Test shortest(node) with the repo having
   4:107
 
  node 'c562' should be unique if the other 'c562' nodes are hidden
+ (but we don't try the slow path to filter out hidden nodes for now)
 
   $ hg log -r 8 -T '{rev}:{node|shortest}\n'
-  8:c562
+  8:c5625
   $ hg log -r 8:10 -T '{rev}:{node|shortest}\n' --hidden
   8:c5625
   9:c5623