;;; wisi.el --- Utilities for implementing an indentation/navigation engine using a generalized LALR parser
;;
-;; Copyright (C) 2012, 2013 Free Software Foundation, Inc.
+;; Copyright (C) 2012 - 2014 Free Software Foundation, Inc.
;;
;; Author: Stephen Leake <stephen_leake@member.fsf.org>
-;; Version: 1.0
-;; url: http://stephe-leake.org/emacs/ada-mode/emacs-ada-mode.html
+;; Version: 1.0.4
+;; package-requires: ((cl-lib "0.4") (emacs "24.2"))
+;; URL: http://stephe-leake.org/emacs/ada-mode/emacs-ada-mode.html
;;
;; This file is part of GNU Emacs.
;;
;; You should have received a copy of the GNU General Public License
;; along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>.
;;
-;;; History: first experimental version Oct 2012
+
+;;; Commentary:
+
+;;;; History: first experimental version Oct 2012
;;
-;;; indentation algorithm overview
+;;;; indentation algorithm overview
;;
;; This design is inspired in part by experience writing a SMIE
;; indentation engine for Ada, and the wisent parser.
;; that lets us find statement indent points from arbitrary places in
;; the code.
;;
-;; The grammar for Ada as represented by the EBNF in LRM Annex P is
-;; not LALR(1), so we use a generalized LALR(1) parser (see
+;; For example, the grammar for Ada as represented by the EBNF in LRM
+;; Annex P is not LALR(1), so we use a generalized LALR(1) parser (see
;; wisi-parse, wisi-compile).
;;
;; The parser actions cache indentation and other information as text
;;
;; An indentation engine moves text in the buffer, as does user
;; editing, so we can't rely on character positions remaining
-;; constant. So the parser actions use markers to store
-;; positions. Text properties also move with the text.
+;; constant. So the parser actions use markers to store
+;; positions. Text properties also move with the text.
;;
;; The stored information includes a marker at each statement indent
-;; point. Thus, the indentation algorithm is: find the previous token
+;; point. Thus, the indentation algorithm is: find the previous token
;; with cached information, and either indent from it, or fetch from
;; it the marker for a previous statement indent point, and indent
;; relative to that.
;;
;; Since we have a cache (the text properties), we need to consider
-;; when to invalidate it. Ideally, we invalidate only when a change to
+;; when to invalidate it. Ideally, we invalidate only when a change to
;; the buffer would change the result of a parse that crosses that
-;; change, or starts after that change. Changes in whitespace
-;; (indentation and newlines) do not affect an Ada parse. Other
+;; change, or starts after that change. Changes in whitespace
+;; (indentation and newlines) do not affect an Ada parse. Other
;; languages are sensitive to newlines (Bash for example) or
-;; indentation (Python). Adding comments does not change a parse,
-;; unless code is commented out. For now we invalidate the cache after
+;; indentation (Python). Adding comments does not change a parse,
+;; unless code is commented out. For now we invalidate the cache after
;; the edit point if the change involves anything other than
;; whitespace.
;;
-;;; comparison to the SMIE parser
+;;;; comparison to the SMIE parser
;;
;; The central problem to be solved in building the SMIE parser is
;; grammar precedence conflicts; the general solution is refining
;; keywords so that each new keyword can be assigned a unique
-;; precedence. This means ad hoc code must be written to determine the
+;; precedence. This means ad hoc code must be written to determine the
;; correct refinement for each language keyword from the surrounding
-;; tokens. In effect, for a complex language like Ada, the knowledge
+;; tokens. In effect, for a complex language like Ada, the knowledge
;; of the language grammar is mostly embedded in the refinement code;
-;; only a small amount is in the refined grammar. Implementing a SMIE
+;; only a small amount is in the refined grammar. Implementing a SMIE
;; parser for a new language involves the same amount of work as the
;; first language.
;;
;; Using a generalized LALR parser avoids that particular problem;
;; assuming the language is already defined by a grammar, it is only a
;; matter of a format change to teach the wisi parser the
-;; language. The problem in a wisi indentation engine is caching the
+;; language. The problem in a wisi indentation engine is caching the
;; output of the parser in a useful way, since we can't start the
;; parser from arbitrary places in the code (as we can with the SMIE
;; parser). A second problem is determining when to invalidate the
-;; cache. But these problems are independent of the language being
+;; cache. But these problems are independent of the language being
;; parsed, so once we have one wisi indentation engine working,
;; adapting it to new languages should be quite simple.
;;
;; The SMIE parser does not find the start of each statement, only the
;; first language keyword in each statement; additional code must be
-;; written to find the statement start and indent points. The wisi
+;; written to find the statement start and indent points. The wisi
;; parser finds the statement start and indent points directly.
;;
;; In SMIE, it is best if each grammar rule is a complete statement,
-;; so forward-sexp will traverse the entire statement. If nested
+;; so forward-sexp will traverse the entire statement. If nested
;; non-terminals are used, forward-sexp may stop inside one of the
-;; nested non-terminals. This problem does not occur with the wisi
+;; nested non-terminals. This problem does not occur with the wisi
;; parser.
;;
;; A downside of the wisi parser is conflicts in the grammar; they can
-;; be much more difficult to resolve than in the SMIE parser. The
+;; be much more difficult to resolve than in the SMIE parser. The
;; generalized parser helps by handling conflicts, but it does so by
;; running multiple parsers in parallel, persuing each choice in the
-;; conflict. If the conflict is due to a genuine ambiguity, both paths
+;; conflict. If the conflict is due to a genuine ambiguity, both paths
;; will succeed, which causes the parse to fail, since it is not clear
-;; which set of text properties to store. Even if one branch
+;; which set of text properties to store. Even if one branch
;; ultimately fails, running parallel parsers over large sections of
-;; code is slow. Finally, this approach can lead to exponential growth
-;; in the number of parsers. So grammar conflicts must still be
+;; code is slow. Finally, this approach can lead to exponential growth
+;; in the number of parsers. So grammar conflicts must still be
;; analyzed and minimized.
;;
;; In addition, the complete grammar must be specified; in smie, it is
;;;; grammar compiler and parser
;;
;; Since we are using a generalized LALR(1) parser, we cannot use any
-;; of the wisent grammar functions. We use the OpenToken Ada package
+;; of the wisent grammar functions. We use OpenToken wisi-generate
;; to compile BNF to Elisp source (similar to
;; semantic-grammar-create-package), and wisi-compile-grammar to
;; compile that to the parser table.
;;
;; Semantic provides a complex lexer, more complicated than we need
-;; for indentation. So we use the elisp lexer, which consists of
-;; `forward-comment', `skip-syntax-forward', and `scan-sexp'. We wrap
+;; for indentation. So we use the elisp lexer, which consists of
+;; `forward-comment', `skip-syntax-forward', and `scan-sexp'. We wrap
;; that in functions that return tokens in the form wisi-parse
;; expects.
;;
;;
;;;;;
+;;; Code:
+
+(require 'cl-lib)
(require 'wisi-parse)
-(eval-when-compile (require 'cl-macs))
+
+;; WORKAROUND: for some reason, this condition doesn't work in batch mode!
+;; (when (and (= emacs-major-version 24)
+;; (= emacs-minor-version 2))
+ (require 'wisi-compat-24.2)
+;;)
;;;; lexer
(defvar-local wisi-keyword-table nil)
(defvar-local wisi-punctuation-table nil)
(defvar-local wisi-punctuation-table-max-length 0)
-(defvar-local wisi-string-double-term nil) ;; string delimited by double quotes
-(defvar-local wisi-string-quote-escape-doubled nil)
+(defvar-local wisi-string-double-term nil);; string delimited by double quotes
+(defvar-local wisi-string-quote-escape-doubled nil
+ "Non-nil if a string delimiter is escaped by doubling it (as in Ada).")
+(defvar-local wisi-string-quote-escape nil
+ "Cons '(delim . character) where 'character' escapes quotes in strings delimited by 'delim'.")
(defvar-local wisi-string-single-term nil) ;; string delimited by single quotes
(defvar-local wisi-symbol-term nil)
(let ((delim (char-after (point)))
(forward-sexp-function nil))
(forward-sexp)
- ;; point is now after the end quote; check for a doubled quote
- (while (and wisi-string-quote-escape-doubled
- (eq (char-after (point)) delim))
+ ;; point is now after the end quote; check for an escaped quote
+ (while (or
+ (and wisi-string-quote-escape-doubled
+ (eq (char-after (point)) delim))
+ (and (eq delim (car wisi-string-quote-escape))
+ (eq (char-before (1- (point))) (cdr wisi-string-quote-escape))))
(forward-sexp))
(setq token-text (buffer-substring-no-properties start (point)))
(setq token-id (if (= delim ?\") wisi-string-double-term wisi-string-single-term))))
"Non-nil when parse is needed - cleared when parse succeeds.")
(defvar-local wisi-change-need-invalidate nil)
-(defvar-local wisi-change-jit-lock-mode nil)
(defun wisi-invalidate-cache()
"Invalidate the wisi token cache for the current buffer.
(when (boundp 'jit-lock-mode)
(when (memq 'wisi-after-change (memq 'jit-lock-after-change after-change-functions))
(setq after-change-functions (delete 'wisi-after-change after-change-functions))
- (add-hook 'after-change-functions 'wisi-after-change nil t)
- (setq wisi-change-jit-lock-mode (1+ wisi-change-jit-lock-mode)))
+ (add-hook 'after-change-functions 'wisi-after-change nil t))
)
(save-excursion
(defun wisi-after-change (begin end length)
"For `after-change-functions'."
;; begin . end is range of text being inserted (may be empty)
- ;; (syntax-ppss-flush-cache begin) is in before-change-functions
- (syntax-ppss-flush-cache begin) ;; IMPROVEME: could check for whitespace
+ ;; (syntax-ppss-flush-cache begin) is in before-change-functions
(cond
(wisi-parse-failed
)
((>= wisi-cache-max begin)
- ;; The parse had succeeded paste the start of the inserted
+ ;; The parse had succeeded past the start of the inserted
;; text.
(save-excursion
(let ((need-invalidate t)
;; FIXME: insert newline in comment to create non-comment!?
;; or paste a chunk of code
;; => check that all of change region is comment or string
- (setq need-invalidate nil))
+ (setq need-invalidate nil)
+ ;; no caches to remove
+ )
((progn
(skip-syntax-forward " " end);; does not skip newlines
)
(if need-invalidate
- ;; The inserted or deleted text could alter the parse
+ ;; The inserted or deleted text could alter the parse;
+ ;; wisi-invalidate-cache removes all 'wisi-cache.
(wisi-invalidate-cache)
;; else move cache-max by the net change length. We don't
If accessing cache at a marker for a token as set by `wisi-cache-tokens', POS must be (1- mark)."
(get-text-property pos 'wisi-cache))
-(defvar wisi-debug 0
- "wisi debug mode:
-0 : normal - ignore parse errors, for indenting new code
-1 : report parse errors (for running tests)
-2 : show parse states, position point at parse errors, debug-on-error works in parser
-3 : also show top 10 items of parser stack.")
-
(defvar-local wisi-parse-error-msg nil)
(defun wisi-goto-error ()
(defun wisi-validate-cache (pos)
"Ensure cached data is valid at least up to POS in current buffer."
- (when (and wisi-parse-try
- (< wisi-cache-max pos))
- (when (> wisi-debug 0)
- (message "wisi: parsing ..."))
+ (let ((msg (format "wisi: parsing %s:%d ..." (buffer-name) (line-number-at-pos))))
+ (when (and wisi-parse-try
+ (< wisi-cache-max pos))
+ (when (> wisi-debug 0)
+ (message msg))
- (setq wisi-parse-try nil)
- (setq wisi-parse-error-msg nil)
- (save-excursion
- (goto-char wisi-cache-max)
- (if (> wisi-debug 1)
- ;; let debugger stop in wisi-parse
- (progn
- (wisi-parse wisi-parse-table 'wisi-forward-token)
- (setq wisi-cache-max (point))
- (setq wisi-parse-failed nil))
- ;; else capture errors from bad syntax, so higher level functions can try to continue
- (condition-case err
+ (setq wisi-parse-try nil)
+ (setq wisi-parse-error-msg nil)
+ (save-excursion
+ (goto-char wisi-cache-max)
+ (if (> wisi-debug 1)
+ ;; let debugger stop in wisi-parse
(progn
(wisi-parse wisi-parse-table 'wisi-forward-token)
(setq wisi-cache-max (point))
(setq wisi-parse-failed nil))
- (wisi-parse-error
- (setq wisi-parse-failed t)
- (setq wisi-parse-error-msg (cdr err)))
- )))
- (if wisi-parse-error-msg
- ;; error
+ ;; else capture errors from bad syntax, so higher level functions can try to continue
+ (condition-case err
+ (progn
+ (wisi-parse wisi-parse-table 'wisi-forward-token)
+ (setq wisi-cache-max (point))
+ (setq wisi-parse-failed nil))
+ (wisi-parse-error
+ (setq wisi-parse-failed t)
+ (setq wisi-parse-error-msg (cdr err)))
+ )))
+ (if wisi-parse-error-msg
+ ;; error
+ (when (> wisi-debug 0)
+ (message "%s error" msg)
+ (wisi-goto-error)
+ (error wisi-parse-error-msg))
+ ;; no msg; success
(when (> wisi-debug 0)
- (message "wisi: parsing ... error")
- (wisi-goto-error)
- (error wisi-parse-error-msg))
- ;; no msg; success
- (when (> wisi-debug 0)
- (message "wisi: parsing ... done")))
- ))
+ (message "%s done" msg)))
+ )))
(defun wisi-get-containing-cache (cache)
"Return cache from (wisi-cache-containing CACHE)."
(when region
(goto-char (car region))
(setq cache (wisi-get-cache (car region)))
+ (when (not cache)
+ ;; token is non-terminal; first terminal doesn't have cache.
+ (setq cache (wisi-forward-cache)))
(while (and cache
(< (point) (cdr region)))
(if (not (wisi-cache-end cache))
;; wisi-tokens is is bound in action created by wisi-semantic-action
(let* ((containing-region (cddr (nth (1- containing-token) wisi-tokens)))
(contained-region (cddr (nth (1- contained-token) wisi-tokens))))
+
+ (unless containing-region ;;
+ (signal 'wisi-parse-error
+ (wisi-error-msg
+ "wisi-containing-action: containing-region '%s' is empty. grammar error; bad action"
+ (nth 1 (nth (1- containing-token) wisi-tokens)))))
+
+ (unless (or (not contained-region) ;; contained-token is empty
+ (wisi-get-cache (car containing-region)))
+ (signal 'wisi-parse-error
+ (wisi-error-msg
+ "wisi-containing-action: containing-token '%s' has no cache. grammar error; missing action"
+ (nth 1 (nth (1- containing-token) wisi-tokens)))))
+
(while (not containing-region)
;; containing-token is empty; use next
(setq containing-region (cddr (nth containing-token wisi-tokens))))
list (number (token_id token_id)):
mark all tokens with token_id in the nonterminal given by the number."
(save-excursion
- (let (next-keyword-mark
- prev-keyword-mark
+ (let (prev-keyword-mark
prev-cache
cache
mark)
)
cache)
+(defun wisi-goto-end-1 (cache)
+ (goto-char (1- (wisi-cache-end cache))))
+
(defun wisi-goto-end ()
"Move point to token at end of statement point is in or before."
(interactive)
(wisi-forward-cache))))
(when (wisi-cache-end cache)
;; nil when cache is statement-end
- (goto-char (1- (wisi-cache-end cache))))
+ (wisi-goto-end-1 cache))
))
(defun wisi-next-statement-cache (cache)
(defun wisi-indent-paren (offset)
"Return indentation OFFSET relative to preceding open paren."
(save-excursion
- (ada-goto-open-paren 0)
+ (goto-char (nth 1 (syntax-ppss)))
(+ (current-column) offset)))
(defun wisi-indent-start (offset cache)
(syntax-propertize (point-max))
(wisi-invalidate-cache)
-
- ;; FIXME: debug counter
- (setq wisi-change-jit-lock-mode 0)
)
(provide 'wisi)
-
-;;; end of file
+;;; wisi.el ends here