| blob | fb1e4737d39c0650723b6dc2e065237a08b6c862 |
1 ;;; smie.el --- Simple Minded Indentation Engine
3 ;; Copyright (C) 2010 Free Software Foundation, Inc.
5 ;; Author: Stefan Monnier <monnier@iro.umontreal.ca>
6 ;; Keywords: languages, lisp, internal, parsing, indentation
8 ;; This file is part of GNU Emacs.
10 ;; GNU Emacs is free software; you can redistribute it and/or modify
11 ;; it under the terms of the GNU General Public License as published by
12 ;; the Free Software Foundation, either version 3 of the License, or
13 ;; (at your option) any later version.
15 ;; GNU Emacs is distributed in the hope that it will be useful,
16 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of
17 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 ;; GNU General Public License for more details.
20 ;; You should have received a copy of the GNU General Public License
21 ;; along with this program. If not, see <http://www.gnu.org/licenses/>.
23 ;;; Commentary:
25 ;; While working on the SML indentation code, the idea grew that maybe
26 ;; I could write something generic to do the same thing, and at the
27 ;; end of working on the SML code, I had a pretty good idea of what it
28 ;; could look like. That idea grew stronger after working on
29 ;; LaTeX indentation.
30 ;;
31 ;; So at some point I decided to try it out, by writing a new
32 ;; indentation code for Coq while trying to keep most of the code
33 ;; "table driven", where only the tables are Coq-specific. The result
34 ;; (which was used for Beluga-mode as well) turned out to be based on
35 ;; something pretty close to an operator precedence parser.
37 ;; So here is another rewrite, this time following the actual principles of
38 ;; operator precedence grammars. Why OPG? Even though they're among the
39 ;; weakest kinds of parsers, these parsers have some very desirable properties
40 ;; for Emacs:
41 ;; - most importantly for indentation, they work equally well in either
42 ;; direction, so you can use them to parse backward from the indentation
43 ;; point to learn the syntactic context;
44 ;; - they work locally, so there's no need to keep a cache of
45 ;; the parser's state;
46 ;; - because of that locality, indentation also works just fine when earlier
47 ;; parts of the buffer are syntactically incorrect since the indentation
48 ;; looks at "as little as possible" of the buffer to make an indentation
49 ;; decision.
50 ;; - they typically have no error handling and can't even detect a parsing
51 ;; error, so we don't have to worry about what to do in case of a syntax
52 ;; error because the parser just automatically does something. Better yet,
53 ;; we can afford to use a sloppy grammar.
55 ;; The development (especially the parts building the 2D precedence
56 ;; tables and then computing the precedence levels from it) is largely
57 ;; inspired from page 187-194 of "Parsing techniques" by Dick Grune
58 ;; and Ceriel Jacobs (BookBody.pdf available at
59 ;; http://www.cs.vu.nl/~dick/PTAPG.html).
60 ;;
61 ;; OTOH we had to kill many chickens, read many coffee grounds, and practice
62 ;; untold numbers of black magic spells, to come up with the indentation code.
63 ;; Since then, some of that code has been beaten into submission, but the
64 ;; smie-indent-keyword is still pretty obscure.
66 ;;; Code:
73 ;;; Building precedence level tables from BNF specs.
81 ;; FIXME: The override is meant to resolve ambiguities,
82 ;; but it also hides real conflicts. It would be great to
83 ;; be able to distinguish the two cases so that overrides
84 ;; don't hide real conflicts.
90 "Compute a 2D precedence table from a list of precedences.
93 or (right OP ...) or (nonassoc OP ...) or (assoc OP ...). All operators in
94 one of those elements share the same precedence level and associativity."
110 prec2-table))
119 table))
120 prec2)))
131 again)
144 ;; If the first is not an OP we add the second (which
145 ;; should be an OP if BNF is an "operator grammar").
146 ;; Strictly speaking, this should only be done if the
147 ;; first is a non-terminal which can expand to a phrase
148 ;; without any OP in it, but checking doesn't seem worth
149 ;; the trouble, and it lets the writer of the BNF
150 ;; be a bit more sloppy by skipping uninteresting base
151 ;; cases which are terminals but not OPs.
165 ;; Compute all first-ops by propagating the initial ones we have
166 ;; now, according to first-nts.
177 ;; Same thing for last-ops.
188 ;; Now generate the 2D precedence table.
204 prec2))
207 "Take a 2D precedence table and turn it into an alist of precedence levels.
208 PREC2 is a table as returned by `smie-precs-precedence-table' or
209 `smie-bnf-precedence-table'."
210 ;; For each operator, we create two "variables" (corresponding to
211 ;; the left and right precedence level), which are represented by
212 ;; cons cells. Those are the vary cons cells that appear in the
213 ;; final `table'. The value of each "variable" is kept in the `car'.
217 tmp x y)
218 ;; From `prec2' we construct a list of constraints between
219 ;; variables (aka "precedence levels"). These can be either
220 ;; equality constraints (in `eqs') or `<' constraints (in `csts').
234 prec2)
235 ;; First process the equality constraints.
242 nil ;Nothing to do.
246 ;; This can happen because of `assoc' settings in precs
247 ;; or because of a rhs like ("op" foo "op").
252 ;; Then eliminate trivial constraints iteratively.
260 ;; We could give each var in a given iteration the same value,
261 ;; but we can also give them arbitrarily different values.
262 ;; Basically, these are vars between which there is no
263 ;; constraint (neither equality nor inequality), so
264 ;; anything will do.
265 ;; We give them arbitrary values, which means that we
266 ;; replace the "no constraint" case with either > or <
267 ;; but not =. The reason we do that is so as to try and
268 ;; distinguish associative operators (which will have
269 ;; left = right).
277 ;; Propagate equalities back to their source.
281 ;; Finally, fill in the remaining vars (which only appeared on the
282 ;; right side of the < constraints).
284 ;; When both sides are nil, it means this operator binds very
285 ;; very tight, but it's still just an operator, so we give it
286 ;; the highest precedence.
287 ;; OTOH if only one side is nil, it usually means it's like an
288 ;; open-paren, which is very important for indentation purposes,
289 ;; so we keep it nil, to make it easier to recognize.
293 table))
295 ;;; Parsing using a precedence level table.
298 "List of token parsing info.
299 Each element is of the form (TOKEN LEFT-LEVEL RIGHT-LEVEL).
300 Parsing is done using an operator precedence parser.
301 LEFT-LEVEL and RIGHT-LEVEL can be either numbers or nil, where nil
302 means that this operator does not bind on the corresponding side,
303 i.e. a LEFT-LEVEL of nil means this is a token that behaves somewhat like
304 an open-paren, whereas a RIGHT-LEVEL of nil would correspond to something
308 "Function to scan forward for the next token.
309 Called with no argument should return a token and move to its end.
310 If no token is found, return nil or the empty string.
311 It can return nil when bumping into a parenthesis, which lets SMIE
315 "Function to scan backward the previous token.
316 Same calling convention as `smie-forward-token-function' except
337 ;; in "a + b + c" we want to stop at each +, but in
338 ;; "if a then b else c" we don't want to stop at each keyword.
339 ;; To distinguish the two cases, we made smie-prec2-levels choose
340 ;; different levels for each part of "if a then b else c", so that
341 ;; by checking if the left-level is equal to the right level, we can
342 ;; figure out that it's an associative operator.
343 ;; This is not 100% foolproof, tho, since a grammar like
344 ;; (exp ("A" exp "C") ("A" exp "B" exp "C"))
345 ;; will cause "B" to have equal left and right levels, even though
346 ;; it is not an associative operator.
347 ;; A better check would be the check the actual previous operator
348 ;; against this one to see if it's the same, but we'd have to change
349 ;; `levels' to keep a stack of operators rather than only levels.
353 "Skip over one sexp.
354 NEXT-TOKEN is a function of no argument that moves forward by one
355 token (after skipping comments if needed) and returns it.
356 NEXT-SEXP is a lower-level function to skip one sexp.
357 OP-FORW is the accessor to the forward level of the level data.
358 OP-BACK is the accessor to the backward level of the level data.
359 HALFSEXP if non-nil, means skip over a partial sexp if needed. I.e. if the
360 first token we see is an operator, skip over its left-hand-side argument.
361 Possible return values:
362 (FORW-LEVEL POS TOKEN): we couldn't skip TOKEN because its back-level
363 is too high. FORW-LEVEL is the forw-level of TOKEN,
364 POS is its start position in the buffer.
365 (t POS TOKEN): same thing when we bump on the wrong side of a paren.
366 (nil POS TOKEN): we skipped over a paren-like pair.
367 nil: we skipped over an identifier, matched parentheses, ..."
382 ;; We did not move, so let's abort the loop.
385 ;; A token like a paren-close.
410 ;; We just found a match to the previously pending operator
411 ;; but this new operator is still part of a larger RHS.
412 ;; E.g. we're now looking at the "then" in
413 ;; "if a then b else c". So we have to keep parsing the
414 ;; rest of the construct.
419 levels)
423 "Skip over one sexp.
424 HALFSEXP if non-nil, means skip over a partial sexp if needed. I.e. if the
425 first token we see is an operator, skip over its left-hand-side argument.
426 Possible return values:
427 (LEFT-LEVEL POS TOKEN): we couldn't skip TOKEN because its right-level
428 is too high. LEFT-LEVEL is the left-level of TOKEN,
429 POS is its start position in the buffer.
430 (t POS TOKEN): same thing but for an open-paren or the beginning of buffer.
431 (nil POS TOKEN): we skipped over a paren-like pair.
432 nil: we skipped over an identifier, matched parentheses, ..."
438 halfsexp))
441 "Skip over one sexp.
442 HALFSEXP if non-nil, means skip over a partial sexp if needed. I.e. if the
443 first token we see is an operator, skip over its left-hand-side argument.
444 Possible return values:
445 (RIGHT-LEVEL POS TOKEN): we couldn't skip TOKEN because its left-level
446 is too high. RIGHT-LEVEL is the right-level of TOKEN,
447 POS is its end position in the buffer.
448 (t POS TOKEN): same thing but for an open-paren or the beginning of buffer.
449 (nil POS TOKEN): we skipped over a paren-like pair.
450 nil: we skipped over an identifier, matched parentheses, ..."
456 halfsexp))
459 "Move backward through N logical elements."
472 nil))))))
475 "Move forward through N logical elements."
488 nil))))))
490 ;;; The indentation engine.
493 "Basic amount of indentation."
497 ;; TODO: For SML, we need more rule formats, so as to handle
498 ;; structure Foo =
499 ;; Bar (toto)
500 ;; and
501 ;; structure Foo =
502 ;; struct ... end
503 ;; I.e. the indentation after "=" depends on the parent ("structure")
504 ;; as well as on the following token ("struct").
505 "Rules of the following form.
506 \((:before . TOK) . OFFSET-RULES) how to indent TOK itself.
507 \(TOK . OFFSET-RULES) how to indent right after TOK.
508 \((T1 . T2) . OFFSET) how to indent token T2 w.r.t T1.
509 \((t . TOK) . OFFSET) how to indent TOK with respect to its parent.
510 \(list-intro . TOKENS) declare TOKENS as being followed by what may look like
511 a funcall but is just a sequence of expressions.
512 \(t . OFFSET) basic indentation step.
513 \(args . OFFSET) indentation of arguments.
515 OFFSET-RULES is a list of elements which can each either be:
517 \(:hanging . OFFSET-RULES) if TOK is hanging, use OFFSET-RULES.
518 \(:parent PARENT . OFFSET-RULES) if TOK's parent is PARENT, use OFFSET-RULES.
519 \(:next TOKEN . OFFSET-RULES) if TOK is followed by TOKEN, use OFFSET-RULES.
520 \(:prev TOKEN . OFFSET-RULES) if TOK is preceded by TOKEN, use OFFSET-RULES.
521 a number the offset to use.
522 `point' align with the token.
523 `parent' align with the parent.
528 ;; A hanging keyword is one that's at the end of a line except it's not at
529 ;; the beginning of a line.
532 ;; Could be an open-paren.
544 smie-indent-basic))
547 "Apply the OFFSET-RULES in TOKINFO.
548 Point is expected to be right in front of the token corresponding to TOKINFO.
549 If computing the indentation after the token, then AFTER is the position
550 after the token."
552 parent next prev
553 offset)
585 offset))
588 "Skip token forward and return it, along with its levels."
597 "Skip token backward and return it, along with its levels."
601 ;; 4 == Open paren syntax.
607 ;; We used to take an optional arg (with value :not-hanging) to specify that
608 ;; we should only use (smie-indent-calculate) if we're looking at a hanging
609 ;; keyword. This was a bad idea, because the virtual indent of a position
610 ;; should not depend on the caller, since it leads to situations where two
611 ;; dependent indentations get indented differently.
612 "Compute the virtual indentation to use for point.
613 This is used when we're not trying to indent point but just
614 need to compute the column at which point should be indented
615 in order to figure out the indentation of some other (further down) point."
616 ;; Trust pre-existing indentation on other lines.
620 ;; Obey the `fixindent' special comment.
625 "fixindent"
626 comment-end-skip)
627 ;; 1+ to account for the \n comment termination.
632 ;; Start the file at column 0.
638 ;; Align close paren with opening paren.
640 ;; (forward-comment (point-max))
651 ;; Align closing token with the corresponding opening one.
652 ;; (e.g. "of" with "case", or "in" with "let").
658 ;; Different case:
659 ;; - smie-bolp: "indent according to others".
660 ;; - common hanging: "indent according to others".
661 ;; - SML-let hanging: "indent like parent".
662 ;; - if-after-else: "indent-like parent".
663 ;; - middle-of-line: "trust current position".
667 ;; For an open-paren-like thingy at BOL, always indent only
668 ;; based on other rules (typically smie-indent-after-keyword).
669 nil)
672 ;; By default use point unless we're hanging.
687 ;; FIXME: This still looks too much like black magic!!
688 ;; FIXME: Rather than a bunch of rules like (PARENT . TOKEN), we
689 ;; want a single rule for TOKEN with different cases for each PARENT.
694 ;; If we didn't move at all, that means we didn't really skip
695 ;; what we wanted.
696 nil)
698 ;; We bumped into a same-level operator. align with it.
700 ;; Don't use (smie-indent-virtual :not-hanging) here, because we
701 ;; want to jump back over a sequence of same-level ops such as
702 ;; a -> b -> c
703 ;; -> d
704 ;; So as to align with the earliest appropriate place.
707 smie-indent-rules))
710 ;; FIXME: The rules ((t . TOK) . OFFSET) either indent
711 ;; relative to "before the parent" or "after the parent",
712 ;; depending on details of the grammar.
719 ;; Since we started at BOL, we're not computing a virtual
720 ;; indentation, and we're still at the starting point, so the
721 ;; next (default) rule can't be used since it uses `current-column'
722 ;; which would cause. indentation to depend on itself.
723 ;; We could just return nil, but OTOH that's not good enough in
724 ;; some cases. Instead, we want to combine the offset-rules for
725 ;; the current token with the offset-rules of the previous one.
727 ;; FIXME: This is odd. Can't we make it use
728 ;; smie-indent-(calculate|virtual) somehow?
735 ;; Indentation of a comment.
743 ;; indentation of comment-continue lines.
758 ;; Indentation right after a special keyword.
766 ;; (if (and tokinfo (null toklevel))
767 ;; (error "Token %S has indent rule but has no parsing info" tok))
773 ;; The default indentation after a keyword/operator
774 ;; is 0 for infix and t for prefix.
775 ;; Using the BNF syntax, we could come up with
776 ;; better defaults, but we only have the
777 ;; precedence levels here.
780 ;; For indentation after "(let" in SML-mode, we end up accumulating
781 ;; the offset of "(" and the offset of "let", so we use `min' to try
782 ;; and get it right either way.
786 ;; Indentation of sequences of simple expressions without
787 ;; intervening keywords or operators. E.g. "a b c" or "g (balbla) f".
788 ;; Can be a list of expressions or a function call.
789 ;; If it's a function call, the first element is special (it's the
790 ;; function). We distinguish function calls from mere lists of
791 ;; expressions based on whether the preceding token is listed in
792 ;; the `list-intro' entry of smie-indent-rules.
793 ;;
794 ;; TODO: to indent Lisp code, we should add a way to specify
795 ;; particular indentation for particular args depending on the
796 ;; function (which would require always skipping back until the
797 ;; function).
798 ;; TODO: to indent C code, such as "if (...) {...}" we might need
799 ;; to add similar indentation hooks for particular positions, but
800 ;; based on the preceding token rather than based on the first exp.
803 arg)
808 ;; Figure out if the atom we just skipped is an argument rather
809 ;; than a function.
815 ;; We're the first expression of the list. In that case, the
816 ;; indentation should be (have been) determined by its context.
817 nil)
819 ;; There's a previous element, and it's not special (it's not
820 ;; the function), so let's just align with that one.
824 ;; We skipped some args plus the function and bumped into something.
825 ;; Align with the first arg.
829 ;; We're the first arg.
832 ;; We used to use (smie-indent-virtual), but that
833 ;; doesn't seem right since it might then indent args less than
834 ;; the function itself.
839 smie-indent-comment-continue smie-indent-keyword smie-indent-after-keyword
840 smie-indent-exps)
841 "Functions to compute the indentation.
842 Each function is called with no argument, shouldn't move point, and should
843 return either nil if it has no opinion, or an integer representing the column
847 "Compute the indentation to use for point."
851 "Indent current line using the SMIE indentation engine."
862 ;; If something funny is used (e.g. `noindent'), return it.
863 indent
869 ;;;###autoload
877 ;;; smie.el ends here