New faster Imenu implementation.

* lisp/progmodes/python.el:
(python-imenu-prev-index-position):
(python-imenu-format-item-label-function)
(python-imenu-format-parent-item-label-function)
(python-imenu-format-parent-item-jump-label-function):
New vars.
(python-imenu-format-item-label)
(python-imenu-format-parent-item-label)
(python-imenu-format-parent-item-jump-label)
(python-imenu--put-parent, python-imenu--build-tree)
(python-imenu-create-index, python-imenu-create-flat-index)
(python-util-popn): New functions.
(python-mode): Set imenu-create-index-function to
python-imenu-create-index.

* test/automated/python-tests.el (python-imenu-prev-index-position-1):
Removed test.
(python-imenu-create-index-1, python-imenu-create-flat-index-1):
New tests.

Fixes: debbugs:14058

4 files changed, 343 insertions, 59 deletions

diff --git a/lisp/ChangeLog b/lisp/ChangeLog
index 98ba110ab33..bc409171fb2 100644
--- a/lisp/ChangeLog
+++ b/lisp/ChangeLog
@@ -1,3 +1,21 @@
+2013-04-19  Fabián Ezequiel Gallina  <fgallina@gnu.org>
+
+        New faster Imenu implementation (bug#14058).
+        * progmodes/python.el:
+        (python-imenu-prev-index-position):
+        (python-imenu-format-item-label-function)
+        (python-imenu-format-parent-item-label-function)
+        (python-imenu-format-parent-item-jump-label-function):
+        New vars.
+        (python-imenu-format-item-label)
+        (python-imenu-format-parent-item-label)
+        (python-imenu-format-parent-item-jump-label)
+        (python-imenu--put-parent, python-imenu--build-tree)
+        (python-imenu-create-index, python-imenu-create-flat-index)
+        (python-util-popn): New functions.
+        (python-mode): Set imenu-create-index-function to
+        python-imenu-create-index.
+
 2013-04-18  Stefan Monnier  <monnier@iro.umontreal.ca>
 
         * winner.el (winner-active-region): Use region-active-p, activate-mark
diff --git a/lisp/progmodes/python.el b/lisp/progmodes/python.el
index 53aff94ae0e..06d07d6ee3c 100644
--- a/lisp/progmodes/python.el
+++ b/lisp/progmodes/python.el
@@ -177,12 +177,14 @@
 ;; might guessed you should run `python-shell-send-buffer' from time
 ;; to time to get better results too.
 
-;; Imenu: This mode supports Imenu in its most basic form, letting it
-;; build the necessary alist via `imenu-default-create-index-function'
-;; by having set `imenu-extract-index-name-function' to
-;; `python-info-current-defun' and
-;; `imenu-prev-index-position-function' to
-;; `python-imenu-prev-index-position'.
+;; Imenu: There are two index building functions to be used as
+;; `imenu-create-index-function': `python-imenu-create-index' (the
+;; default one, builds the alist in form of a tree) and
+;; `python-imenu-create-flat-index'. See also
+;; `python-imenu-format-item-label-function',
+;; `python-imenu-format-parent-item-label-function',
+;; `python-imenu-format-parent-item-jump-label-function' variables for
+;; changing the way labels are formatted in the tree version.
 
 ;; If you used python-mode.el you probably will miss auto-indentation
 ;; when inserting newlines.  To achieve the same behavior you have
@@ -1194,7 +1196,7 @@ Returns nil if point is not in a def or class."
 
 (defun python-nav--syntactically (fn poscompfn &optional contextfn)
   "Move point using FN avoiding places with specific context.
-FN must take no arguments. POSCOMPFN is a two arguments function
+FN must take no arguments.  POSCOMPFN is a two arguments function
 used to compare current and previous point after it is moved
 using FN, this is normally a less-than or greater-than
 comparison.  Optional argument CONTEXTFN defaults to
@@ -3008,15 +3010,192 @@ Interactively, prompt for symbol."
 
 ;;; Imenu
 
-(defun python-imenu-prev-index-position ()
-  "Python mode's `imenu-prev-index-position-function'."
-  (let ((found))
-    (while (and (setq found
-                      (re-search-backward python-nav-beginning-of-defun-regexp nil t))
-                (not (python-info-looking-at-beginning-of-defun))))
-    (and found
-         (python-info-looking-at-beginning-of-defun)
-         (python-info-current-defun))))
+(defvar python-imenu-format-item-label-function
+  'python-imenu-format-item-label
+  "Imenu function used to format an item label.
+It must be a function with two arguments: TYPE and NAME.")
+
+(defvar python-imenu-format-parent-item-label-function
+  'python-imenu-format-parent-item-label
+  "Imenu function used to format a parent item label.
+It must be a function with two arguments: TYPE and NAME.")
+
+(defvar python-imenu-format-parent-item-jump-label-function
+  'python-imenu-format-parent-item-jump-label
+  "Imenu function used to format a parent jump item label.
+It must be a function with two arguments: TYPE and NAME.")
+
+(defun python-imenu-format-item-label (type name)
+  "Return imenu label for single node using TYPE and NAME."
+  (format "%s (%s)" name type))
+
+(defun python-imenu-format-parent-item-label (type name)
+  "Return imenu label for parent node using TYPE and NAME."
+  (format "%s..." (python-imenu-format-item-label type name)))
+
+(defun python-imenu-format-parent-item-jump-label (type name)
+  "Return imenu label for parent node jump using TYPE and NAME."
+  (if (string= type "class")
+      "*class definition*"
+    "*function definition*"))
+
+(defun python-imenu--put-parent (type name pos num-children tree &optional root)
+  "Add the parent with TYPE, NAME, POS and NUM-CHILDREN to TREE.
+Optional Argument ROOT must be non-nil when the node being
+processed is the root of the TREE."
+  (let ((label
+         (funcall python-imenu-format-item-label-function type name))
+        (jump-label
+         (funcall python-imenu-format-parent-item-jump-label-function type name)))
+    (if root
+        ;; This is the root, everything is a children.
+        (cons label (cons (cons jump-label pos) tree))
+      ;; This is node a which may contain some children.
+      (cons
+       (cons label (cons (cons jump-label pos)
+                         ;; Append all the children
+                         (python-util-popn tree num-children)))
+       ;; All previous non-children nodes.
+       (nthcdr num-children tree)))))
+
+(defun python-imenu--build-tree (&optional min-indent prev-indent num-children tree)
+  "Recursively build the tree of nested definitions of a node.
+Arguments MIN-INDENT PREV-INDENT NUM-CHILDREN and TREE are
+internal and should not be passed explicitly unless you know what
+you are doing."
+  (setq num-children (or num-children 0)
+        min-indent (or min-indent 0))
+  (let* ((pos (python-nav-backward-defun))
+         (type)
+         (name (when (and pos (looking-at python-nav-beginning-of-defun-regexp))
+                 (let ((split (split-string (match-string-no-properties 0))))
+                   (setq type (car split))
+                   (cadr split))))
+         (label (when name
+                  (funcall python-imenu-format-item-label-function type name)))
+         (indent (current-indentation)))
+    (cond ((not pos)
+           ;; No defun found, nothing to add.
+           tree)
+          ((equal indent 0)
+           (if (> num-children 0)
+               ;; Append it as the parent of everything collected to
+               ;; this point.
+               (python-imenu--put-parent type name pos num-children tree t)
+             ;; There are no children, this is a lonely defun.
+             (cons label pos)))
+          ((equal min-indent indent)
+           ;; Stop collecting nodes after moving to a position with
+           ;; indentation equaling min-indent. This is specially
+           ;; useful for navigating nested definitions recursively.
+           tree)
+          (t
+           (python-imenu--build-tree
+            min-indent
+            indent
+            ;; Add another children, either when this is the
+            ;; first call or when indentation is
+            ;; less-or-equal than previous. And do not
+            ;; discard the number of children, because the
+            ;; way code is scanned, all children are
+            ;; collected until a root node yet to be found
+            ;; appears.
+            (if (or (not prev-indent)
+                    (and
+                     (> indent min-indent)
+                     (<= indent prev-indent)))
+                (1+ num-children)
+              num-children)
+            (cond ((not prev-indent)
+                   ;; First call to the function: append this
+                   ;; defun to the index.
+                   (list (cons label pos)))
+                  ((= indent prev-indent)
+                   ;; Add another defun with the same depth
+                   ;; as the previous.
+                   (cons (cons label pos) tree))
+                  ((and (< indent prev-indent)
+                        (< 0 num-children))
+                   ;; There are children to be appended and
+                   ;; the previous defun had more
+                   ;; indentation, the current one must be a
+                   ;; parent.
+                   (python-imenu--put-parent type name pos num-children tree))
+                  ((> indent prev-indent)
+                   ;; There are children defuns deeper than
+                   ;; current depth. Fear not, we already
+                   ;; know how to treat them.
+                   (cons
+                    (prog1
+                        (python-imenu--build-tree
+                         prev-indent indent 1 (list (cons label pos)))
+                      ;; Adjustment: after scanning backwards
+                      ;; for all deeper children, we need to
+                      ;; continue our scan for a parent from
+                      ;; the current defun we are looking at.
+                      (python-nav-forward-defun))
+                    tree))))))))
+
+(defun python-imenu-create-index ()
+  "Return tree Imenu alist for the current python buffer.
+Change `python-imenu-format-item-label-function',
+`python-imenu-format-parent-item-label-function',
+`python-imenu-format-parent-item-jump-label-function' to
+customize how labels are formatted."
+  (goto-char (point-max))
+  (let ((index)
+        (tree))
+    (while (setq tree (python-imenu--build-tree))
+      (setq index (cons tree index)))
+    index))
+
+(defun python-imenu-create-flat-index (&optional alist prefix)
+  "Return flat outline of the current python buffer for Imenu.
+Optional Argument ALIST is the tree to be flattened, when nil
+`python-imenu-build-index' is used with
+`python-imenu-format-parent-item-jump-label-function'
+`python-imenu-format-parent-item-label-function'
+`python-imenu-format-item-label-function' set to (lambda (type
+name) name).  Optional Argument PREFIX is used in recursive calls
+and should not be passed explicitly.
+
+Converts this:
+
+    \((\"Foo\" . 103)
+     (\"Bar\" . 138)
+     (\"decorator\"
+      (\"decorator\" . 173)
+      (\"wrap\"
+       (\"wrap\" . 353)
+       (\"wrapped_f\" . 393))))
+
+To this:
+
+    \((\"Foo\" . 103)
+     (\"Bar\" . 138)
+     (\"decorator\" . 173)
+     (\"decorator.wrap\" . 353)
+     (\"decorator.wrapped_f\" . 393))"
+  (apply
+   'nconc
+   (mapcar
+    (lambda (item)
+      (let ((name (if prefix
+                      (concat prefix "." (car item))
+                    (car item)))
+            (pos (cdr item)))
+        (cond ((or (numberp pos) (markerp pos))
+               (list (cons name pos)))
+              ((listp pos)
+               (message "%S" item)
+               (cons
+                (cons name (cdar pos))
+                (python-imenu-create-flat-index (cddr item) name))))))
+    (or alist
+        (let ((python-imenu-format-item-label-function (lambda (type name) name))
+              (python-imenu-format-parent-item-label-function (lambda (type name) name))
+              (python-imenu-format-parent-item-jump-label-function (lambda (type name) name)))
+          (python-imenu-create-index))))))
 
 
 ;;; Misc helpers
@@ -3337,6 +3516,22 @@ Optional argument DIRECTION defines the direction to move to."
       (goto-char comment-start))
     (forward-comment factor)))
 
+(defun python-util-popn (lst n)
+  "Return LST first N elements.
+N should be an integer, when it's a natural negative number its
+opposite is used.  When N is bigger than the length of LST, the
+list is returned as is."
+  (let* ((n (min (abs n)))
+         (len (length lst))
+         (acc))
+    (if (> n len)
+        lst
+      (while (< 0 n)
+        (setq acc (cons (car lst) acc)
+              lst (cdr lst)
+              n (1- n)))
+      (reverse acc))))
+
 
 ;;;###autoload
 (define-derived-mode python-mode prog-mode "Python"
@@ -3382,11 +3577,8 @@ if that value is non-nil."
   (add-hook 'post-self-insert-hook
             'python-indent-post-self-insert-function nil 'local)
 
-  (set (make-local-variable 'imenu-extract-index-name-function)
-       #'python-info-current-defun)
-
-  (set (make-local-variable 'imenu-prev-index-position-function)
-       #'python-imenu-prev-index-position)
+  (set (make-local-variable 'imenu-create-index-function)
+       #'python-imenu-create-index)
 
   (set (make-local-variable 'add-log-current-defun-function)
        #'python-info-current-defun)
diff --git a/test/ChangeLog b/test/ChangeLog
index c8cb8ee3b54..0c240394c5c 100644
--- a/test/ChangeLog
+++ b/test/ChangeLog
@@ -1,3 +1,10 @@
+2013-04-19  Fabián Ezequiel Gallina  <fgallina@gnu.org>
+
+        * automated/python-tests.el (python-imenu-prev-index-position-1):
+        Removed test.
+        (python-imenu-create-index-1, python-imenu-create-flat-index-1):
+        New tests.
+
 2013-04-17  Fabián Ezequiel Gallina  <fgallina@gnu.org>
 
         * automated/python-tests.el (python-nav-backward-defun-2)
diff --git a/test/automated/python-tests.el b/test/automated/python-tests.el
index 15089e6b393..8462a863b84 100644
--- a/test/automated/python-tests.el
+++ b/test/automated/python-tests.el
@@ -1673,66 +1673,133 @@ Using `python-shell-interpreter' and
 
 
 ;;; Imenu
-(ert-deftest python-imenu-prev-index-position-1 ()
-  (require 'imenu)
+
+(ert-deftest python-imenu-create-index-1 ()
   (python-tests-with-temp-buffer
    "
-def decoratorFunctionWithArguments(arg1, arg2, arg3):
+class Foo(models.Model):
+    pass
+
+
+class Bar(models.Model):
+    pass
+
+
+def decorator(arg1, arg2, arg3):
     '''print decorated function call data to stdout.
 
     Usage:
 
-    @decoratorFunctionWithArguments('arg1', 'arg2')
+    @decorator('arg1', 'arg2')
     def func(a, b, c=True):
         pass
     '''
 
-    def wwrap(f):
-        print 'Inside wwrap()'
+    def wrap(f):
+        print ('wrap')
         def wrapped_f(*args):
-            print 'Inside wrapped_f()'
-            print 'Decorator arguments:', arg1, arg2, arg3
+            print ('wrapped_f')
+            print ('Decorator arguments:', arg1, arg2, arg3)
             f(*args)
-            print 'After f(*args)'
+            print ('called f(*args)')
         return wrapped_f
-    return wwrap
+    return wrap
 
-def test(): # Some comment
-    'This is a test function'
-    print 'test'
 
-class C(object):
+class Baz(object):
 
-    def m(self):
-        self.c()
+    def a(self):
+        pass
 
-        def b():
-            pass
+    def b(self):
+        pass
 
-        def a():
+    class Frob(object):
+
+        def c(self):
             pass
+"
+   (goto-char (point-max))
+   (should (equal
+            (list
+             (cons "Foo (class)" (copy-marker 2))
+             (cons "Bar (class)" (copy-marker 38))
+             (list
+              "decorator (def)"
+              (cons "*function definition*" (copy-marker 74))
+              (list
+               "wrap (def)"
+               (cons "*function definition*" (copy-marker 254))
+               (cons "wrapped_f (def)" (copy-marker 294))))
+             (list
+              "Baz (class)"
+              (cons "*class definition*" (copy-marker 519))
+              (cons "a (def)" (copy-marker 539))
+              (cons "b (def)" (copy-marker 570))
+              (list
+               "Frob (class)"
+               (cons "*class definition*" (copy-marker 601))
+               (cons "c (def)" (copy-marker 626)))))
+            (python-imenu-create-index)))))
+
+(ert-deftest python-imenu-create-flat-index-1 ()
+  (python-tests-with-temp-buffer
+   "
+class Foo(models.Model):
+    pass
 
-    def c(self):
+
+class Bar(models.Model):
+    pass
+
+
+def decorator(arg1, arg2, arg3):
+    '''print decorated function call data to stdout.
+
+    Usage:
+
+    @decorator('arg1', 'arg2')
+    def func(a, b, c=True):
+        pass
+    '''
+
+    def wrap(f):
+        print ('wrap')
+        def wrapped_f(*args):
+            print ('wrapped_f')
+            print ('Decorator arguments:', arg1, arg2, arg3)
+            f(*args)
+            print ('called f(*args)')
+        return wrapped_f
+    return wrap
+
+
+class Baz(object):
+
+    def a(self):
+        pass
+
+    def b(self):
         pass
+
+    class Frob(object):
+
+        def c(self):
+            pass
 "
-   (let ((expected
-          '(("*Rescan*" . -99)
-            ("decoratorFunctionWithArguments" . 2)
-            ("decoratorFunctionWithArguments.wwrap" . 224)
-            ("decoratorFunctionWithArguments.wwrap.wrapped_f" . 273)
-            ("test" . 500)
-            ("C" . 575)
-            ("C.m" . 593)
-            ("C.m.b" . 628)
-            ("C.m.a" . 663)
-            ("C.c" . 698))))
-     (mapc
-      (lambda (elt)
-        (should (= (cdr (assoc-string (car elt) expected))
-                   (if (markerp (cdr elt))
-                       (marker-position (cdr elt))
-                     (cdr elt)))))
-      (imenu--make-index-alist)))))
+   (goto-char (point-max))
+   (should (equal
+            (list (cons "Foo" (copy-marker 2))
+                  (cons "Bar" (copy-marker 38))
+                  (cons "decorator" (copy-marker 74))
+                  (cons "decorator.wrap" (copy-marker 254))
+                  (cons "decorator.wrap.wrapped_f" (copy-marker 294))
+                  (cons "Baz" (copy-marker 519))
+                  (cons "Baz.a" (copy-marker 539))
+                  (cons "Baz.b" (copy-marker 570))
+                  (cons "Baz.Frob" (copy-marker 601))
+                  (cons "Baz.Frob.c" (copy-marker 626)))
+            (python-imenu-create-flat-index)))))
 
 
 ;;; Misc helpers