An automaton for indenting the lisp code in linear time

[A Soare <alinsoar@voila.fr>]

[-- Attachment #1: Type: text/plain, Size: 3333 bytes --]


Here I send the old promised automaton for indenting in linear time...

I looked in the code of emacs to the function scan_sexps_forward,
because I want to write for myself a little web browser, and I saw
that its automaton of changing the classes of syntax looks very
closely to the automaton that I wrote about 1 year ago to indent the
lisp code.

That is the reason for which I decided to open the archives and
to remember.

This code indents a line of code and a whole region in O(n) time
complexity; oups! no, sorry, in O(n+l) (the automaton in O(n) + O(l)
to use its output to indent), where n is the number of bytes from the
beginning of the function to the ending point, and l is the number of
lines from the beginning of the function to the ending point. (in the
code it's true that (current-column) is called very often, but I can
insert a variable `column' that keeps the current column, and it is
reset when we meet newline, and grows by 1 when the automaton passes
to the next state, and I think that I will modify it to keep the idea
of O(n)).

This code is very compact; installing it will cut thousands of lines
of old code from Emacs.

And, besides, it is imcomplete! Here are just the most basics. I can
complete it just after I speak with the emacs developers, in order to
agree on its behaviour. I do not like to work on in vain.

In this period I wish to work for this code, in order to finish it. If
I do not work now, I do not know when I can work on.

Besides, looking these days to write my web browser, I realised that
it would be a good idea embedding this automaton in C. But, again, I
do not want to work on it before asking you, because I want this job
to have a practical utility, not just to spend time working on this.

Here I give you just 2 very samples examples of how this automaton
works. It's evident how it works, and these 2 examples are too much!

There are a few new things in this code: for example, note the
easyness to add indent for comments, constant symbols, and look at the
easyness with which I made the indentation of a parameter of a
function before the first parameter, not under the second (i.e. one
makes now the difference between many kinds of list : not all the
lists have the first parameter a function):

(defun a (x y
          z t)
  ...

and not the old behaviour:

(defun a (x y
            z t)
  ...

The problem of indentig of lisp code is a problem of... homotopy:
however I deform the code (the spaces at the beginning of the lines),
this automaton must always return the same result.

Before calling (lisp-indent-automaton), one must have in the upper
environment the variables `state' and `indents-lines' initialised with
nil. It will return the result in indents-lines. The mapcar of car of
indents-lines is a list that contains the correct answer to the
homotopy problem. This result must be the same however I deform the
code (spaces at the beginning of lines). The mapcar of the cdr is a
list with the current indentation.



Please, tell me your impressions and... give me to work in order to
finish it well :)




Alin Soare.





____________________________________________________

Sur le mail Voila, vous pouvez personnaliser l’anti-spam ! http://mail.voila.fr

[-- Attachment #2: indent.el --]
[-- Type: application/octet-stream, Size: 8137 bytes --]


(defun lisp-indent-value ()
  "
  VERSION : NEW
  "
  (cond ((elt state 3)
         ;; Inside a string, don't change indentation.
         nil
         )
        ((null (cadr state))
         ;; outside an expression align to the left column
         0
         )
        ((null indent)
         ;; and empty parethesis
         (1+ start-col))
        ((and (integerp lisp-indent-offset)
              (integerp (cadr indent)))
         ;; indent by constant offset
         (+ (cadr indent) lisp-indent-offset)
         )
        ((looking-at "\\s<\\s<\\s<")
         ;; Comments that start with three semicolons or more, should
         ;; start at the left margin
         0
         )
        ((eq (car indent) :l)
         ;; indent beneath a list
         (caddr indent)
         )
         ((and (eq (car indent) :w)
              (stringp (cadr indent))
              (string-match "def" (cadr indent))
              (zerop (string-match "def" (cadr indent))))
         ;; indent a def-form
         (+ lisp-body-indent start-col)
         )
        ((and (eq (car indent) :w)
              (wholenump (get (intern-soft (cadr indent)) 'lisp-indent-function)))
         ;; here there is a special form
         (setq oo (or (get (intern-soft (cadr indent)) 'lisp-indent-function)
                      (get (intern-soft (cadr indent)) 'lisp-indent-hook)))
         (if (> (length indent) (* 3 oo))
             (+ lisp-body-indent start-col)
           (+ (* 2 lisp-body-indent) start-col))
         )
        ((and (eq (car indent) :w)
              (get (intern-soft (cadr indent)) 'lisp-indent-hook))
         ;; indent defined by another function
         (funcall (get (intern-soft (cadr indent)) 'lisp-indent-hook))
         )
        ((and (equal (following-char) ?:)
              nil)
         ;; indent of a constant symbol
         ;; not yed defined
         (caddr indent)
         )
        ((and (eq (car indent) :w)
              (> (length indent) 3))
         ;; indent beneath the `indent-what-argument' parameter
         (elt indent (+ 3 (1- (* 3 indent-what-argument))))
         )
        (t
         ;;  the first parameter of a function call
         (caddr indent))
         ))

(defun lisp-indent-what-argument nil
  (cond ((and (eq (car indent) :w)
              (stringp (cadr indent))
              (string-match "def" (cadr indent))
              (= (length indent) 9)
              (zerop (string-match "def" (cadr indent))))
         ;; if the third parameter of defun is a list, then this list
         ;; is not a function call
         0)
        ((or
          (and (>= (length indent) 6)
               (eq (elt indent (- (length indent ) 6)) :q))
          (and (eq (car indent) :w)
               (stringp (cadr indent))
               (string-equal "quote" (cadr indent))))
         ;; a quoted list is not a function call
         0
         )
        (t
         ;; for the rest, always indent after the first parameter of
         ;; the function...
         1)))

(defun lisp-indent-next-state (&optional n)
  (parse-partial-sexp (point) (+ (or n 1) (point)) () () state))

(defun lisp-indent-automaton (&optional end state indent-what-argument start-col)
  "
   an automaton to indent the lisp code
   VERSION: NEW
  "
  (let (
        indent
        indent-next-line-to
        )
    (or end (beginning-of-line) (setq end (point)))
    (or indent-what-argument
        (setq indent-what-argument 0))
    (or state (beginning-of-defun))
    (and (null start-col) (setq start-col 0))
    (catch 'STOP
      (while (< (point) end)
        (cond ((and (elt state 8)
                    (not (elt state 4)))
               ;; inside a string
               (and (looking-at "\\s>")
                    (setq indent-lines (cons (lisp-indent-value) indent-lines)))
               (setq state (lisp-indent-next-state))
               )
              ((looking-at "\\s\"")
               ;; the start of a string
               (setq indent (append indent (list :s () (current-column)))
                     state (lisp-indent-next-state))
               )
              ((looking-at "\\s\(")
               ;; open a parenthesis
               (let ((col (if indent-lines
                              (+ (current-column) (- (caar indent-lines) (cdar indent-lines)))
                            (current-column))))
                 (setq indent (append indent (list :l () col))
                       state (lisp-indent-automaton end (lisp-indent-next-state)
                                                    (lisp-indent-what-argument)
                                                    col)))
               )
              ((looking-at "\\s\)")
               ;; close a parenthesis
               (throw 'STOP (lisp-indent-next-state))
               )
              ((looking-at "\\s ")
               ;; spaces are ignored
               (while (looking-at "[[:blank:]]")
                 (setq state (lisp-indent-next-state)))
               )
              ((looking-at "\\sw\\|\\s_")
               ;; a function or a parameter
               (let* ((col (if indent-lines
                              (+ (current-column) (- (caar indent-lines) (cdar indent-lines)))
                            (current-column)))
                      r
                      (w (catch 'WORD
                           (while t
                             (setq r (concat r (string (following-char))))
                             (setq state (lisp-indent-next-state))
                             (and (not (looking-at "\\w\\|\\s_"))
                                  (throw 'WORD r))))))
                 (setq indent (append indent (list :w w col))))
               )
              ((looking-at "\\s<")
               ;; start of a comment
               (setq indent (append indent (list :c (current-column))))
               (while (not (looking-at "\\s>"))
                 (setq state (lisp-indent-next-state)))
               )
              ((looking-at "\\s\'")
               ;; quote
               (setq indent (append indent (list :q () (current-column))))
               (setq state (lisp-indent-next-state))
               )
              ((looking-at "\\s\\")
               ;; a special character
               (setq state (lisp-indent-next-state 2))
               )
              ((looking-at "\\s>")
               ;; end of line
               (setq state (lisp-indent-next-state))
               (while (looking-at "\\s ")
                 (setq state (lisp-indent-next-state)))
               (setq indent-lines (cons (cons (lisp-indent-value) (current-column)) indent-lines))
               )
              (t
               (error "oops! unknown class of syntax ! (indent failed at position %d)" (point))))))))

(defun indent-defun-example nil
  "
  An example how to use the automatonin for indentig a whole region
  of lisp code in linear time (a function from the beginning to the point).
  "
  (let* (indent-lines
         state 
         l)
    (save-excursion
      (lisp-indent-automaton)
      (dolist (i indent-lines)
        (when (consp i)
          (setq l (prog2 (beginning-of-line) (point)))
          (skip-chars-forward "[[:blank:]]")
          (when (not (zerop (-  (- l (point)) (- (cdr i) (car i)))))
            (delete-region l (point))
            (indent-to (car i))))
        (previous-line)))))

(defun indent-line-example nil
  "
  An example how to indent a line of code using the automaton
  "
  (let* (indent-lines
         state 
         dif
         (pos (point-marker))
         (l (prog2 (beginning-of-line) (point))))
    (save-excursion (lisp-indent-automaton))
    (if (not (consp (car indent-lines)))
        nil
      (setq dif
            (catch 'DIF
              (dolist (i (cdr indent-lines))
                (and (consp i)
                     (throw 'DIF (- (cdr i) (car i)))))))
      (skip-chars-forward "[[:blank:]]")
      (when (not (zerop (- (+ (caar indent-lines) dif) (- (point) l))))
        (delete-region l (point))
        (indent-to (+ (caar indent-lines) dif))
        (goto-char (max pos (point)))))))