1 ;; SPDX-License-Identifier: BSD-3-Clause
3 (in-package #:parenscript
)
5 ;;; bind and bind* - macros used for destructuring bindings in PS LOOP
9 ((not (listp (cdr x
))) ; dotted list
10 (list (dot->rest
(car x
)) '&rest
(dot->rest
(cdr x
))))
11 (t (cons (dot->rest
(car x
)) (dot->rest
(cdr x
))))))
13 (defun property-bindings-p (x)
16 (or (keywordp y
) ; standalone property name
17 (and (consp y
) ; var name paired with property name
20 (not (keywordp (car y
)))
21 (keywordp (cadr y
)))))
24 (defun extract-bindings (x)
25 ;; returns a pair of destructuring bindings and property bindings
26 (cond ((atom x
) (list x nil
))
27 ((property-bindings-p x
)
28 (let ((var (ps-gensym)))
29 (list var
(list x var
))))
31 :for
(d p
) = (extract-bindings (car y
))
33 :when p
:append p
:into ps
34 :finally
(return (list ds ps
))))))
36 (defun property-bindings (bindings expr body
)
37 `(let ,(loop :for b
:in bindings
38 :for
(var p
) = (cond ((consp b
) b
) ; var name paired with property name
39 (t (list (intern (string b
)) b
))) ; make var from prop
40 :collect
`(,var
(@ ,expr
,p
)))
43 (defpsmacro bind
(bindings expr
&body body
)
44 (let ((bindings (dot->rest bindings
)))
45 (destructuring-bind (d p
)
46 (extract-bindings bindings
)
48 (or (= (length bindings
) 1)
49 (atom (ps-macroexpand expr
))))
50 (property-bindings bindings expr body
))
52 (with-ps-gensyms (var)
54 (bind ,bindings
,var
,@body
))))
56 `(destructuring-bind ,bindings
,expr
,@body
))
57 (t `(destructuring-bind ,d
,expr
58 (bind* ,p
,@body
)))))))
60 (defpsmacro bind
* (bindings &body body
)
61 (cond ((= (length bindings
) 2)
62 `(bind ,(car bindings
) ,(cadr bindings
) ,@body
))
63 (t `(bind ,(car bindings
) ,(cadr bindings
)
64 (bind* ,(cddr bindings
) ,@body
)))))
66 (eval-when (:compile-toplevel
:load-toplevel
:execute
)
67 (defvar *loop-keywords
*
68 '(:named
:for
:repeat
:with
:while
:until
:initially
:finally
69 :from
:downfrom
:to
:below
:downto
:above
:by
:in
:across
:on
:= :then
70 :when
:unless
:if
:else
:end
:do
:doing
:return
71 :sum
:summing
:collect
:collecting
:append
:appending
:count
:counting
72 :minimize
:minimizing
:maximize
:maximizing
:map
:mapping
75 (defun as-keyword (key)
76 (cond ((not (symbolp key
)) key
)
78 (t (intern (symbol-name key
) :keyword
)))))
80 (defmacro loop-case
(key &body forms
)
81 (loop :for
(match . nil
) :in forms
82 :for keys
= (if (listp match
) match
(list match
)) :do
83 (loop :for k
:in keys
:do
84 (assert (member k
(append *loop-keywords
* '(t otherwise
)))
85 nil
"~a isn't a recognized loop keyword." k
)))
86 `(case (as-keyword ,key
) ,@forms
))
88 (defun err (expected got
)
89 (error "PS-LOOP expected ~a, got ~a." expected got
))
91 (defclass loop-state
()
92 ((tokens :initarg
:tokens
:accessor tokens
)
93 (name :initform nil
:accessor name
)
94 ;; A clause is either (:BODY FORM) or (:ITER PLACE INIT STEP TEST &OPTIONAL JS-OBJ)
95 (clauses :initform nil
:accessor clauses
)
96 (prologue :initform nil
:accessor prologue
)
97 (finally :initform nil
:accessor finally
)
98 (accum-var :initform nil
:accessor accum-var
)
99 (accum-kind :initform nil
:accessor accum-kind
)))
101 (defun push-body-clause (clause state
)
102 (push (list :body clause
) (clauses state
)))
104 (defun push-iter-clause (clause state
)
105 (push (cons :iter clause
) (clauses state
)))
107 (defun push-tokens (state toks
)
108 (setf (tokens state
) (append toks
(tokens state
))))
111 (car (tokens state
)))
113 (defun eat (state &optional what tag
)
114 "Consumes the next meaningful chunk of loop for processing."
116 (:if
(when (eq (as-keyword (peek state
)) tag
)
118 (values (eat state
) t
)))
119 (:progn
(cons 'progn
(loop :collect
(if (consp (peek state
))
121 (err "a compound form" (peek state
)))
122 :until
(atom (peek state
)))))
123 (otherwise (let ((tok (pop (tokens state
))))
124 (when (and (eq what
:atom
) (not (atom tok
)))
126 (when (and (eq what
:symbol
) (not (symbolp tok
)))
127 (err "a symbol" tok
))
130 (defun maybe-hoist (expr state
)
131 (cond ((complex-js-expr? expr
)
132 (let ((var (ps-gensym)))
133 (push (list 'setf var expr
) (prologue state
))
137 (defun for-from (from-key var state
)
139 (err "an atom after FROM" var
))
140 (let ((start (eat state
))
141 (op (loop-case from-key
(:downfrom
'-
) (otherwise '+)))
142 (test-op (loop-case from-key
(:downfrom
'>=) (otherwise '<=)))
145 (loop while
(member (as-keyword (peek state
)) '(:to
:below
:downto
:above
:by
)) do
146 (let ((term (eat state
)))
147 (if (eq (as-keyword term
) :by
)
148 (setf by
(eat state
))
149 (setf op
(loop-case term
((:downto
:above
) '-
) (otherwise op
))
150 test-op
(loop-case term
(:to test-op
) (:below
'<) (:downto
'>=) (:above
'>))
152 (let ((test (when test-op
153 (list test-op var
(maybe-hoist end state
)))))
154 (push-iter-clause `(,var
,start
(,op
,var
,(or by
1)) ,test
) state
))))
156 (defun for-= (place state
)
157 (let ((start (eat state
)))
158 (multiple-value-bind (then thenp
)
159 (eat state
:if
:then
)
160 (push-iter-clause (list place start
(if thenp then start
) nil
) state
))))
162 (defun for-in (place state
)
163 (let ((arr (maybe-hoist (eat state
) state
))
165 (push-tokens state
`(,index
:from
0 :below
(length ,arr
)
166 ,place
:= (aref ,arr
,index
)))
170 (defun for-on (place state
)
171 (let* ((arr (eat state
))
172 (by (or (eat state
:if
:by
) 1))
173 (var (if (atom place
) place
(ps-gensym)))
174 (then (if (numberp by
) `((@ ,var
:slice
) ,by
) `(,by
,var
))))
175 (push-tokens state
`(,var
:= ,arr
:then
,then
))
177 ;; set the end-test by snooping into the iteration clause we just added
178 (setf (fifth (car (clauses state
))) `(> (length ,var
) 0))
179 (unless (eq place var
)
180 (push-tokens state
`(,place
:= ,var
))
181 (for-clause state
))))
183 (defun for-keys-of (place state
)
184 (when (clauses state
)
185 (error "FOR..OF is only allowed as the first clause in a loop."))
187 (unless (<= (length place
) 2) ; length 1 is ok, treat (k) as (k nil)
188 (error "FOR..OF must be followed by a key variable or key-value pair."))
189 (unless (atom (first place
))
190 (error "The key in a FOR..OF clause must be a variable.")))
191 (let ((k (or (if (atom place
) place
(first place
)) (ps-gensym)))
192 (v (when (consp place
) (second place
))))
193 (let ((js-obj (eat state
)))
194 (when v
; assign JS-OBJ to a local var if we need to for value binding (otherwise inline it)
195 (setf js-obj
(maybe-hoist js-obj state
)))
196 (push-iter-clause (list k nil nil nil js-obj
) state
)
198 (let ((val `(getprop ,js-obj
,k
)))
199 (push-iter-clause (list v val val nil
) state
))))))
201 (defun for-clause (state)
202 (let ((place (eat state
))
203 (term (eat state
:atom
)))
205 ((:from
:downfrom
) (for-from term place state
))
206 (:= (for-= place state
))
207 ((:in
:across
) (for-in place state
))
208 (:on
(for-on place state
))
209 (:of
(for-keys-of place state
))
210 (otherwise (error "FOR ~s ~s is not valid in PS-LOOP." place term
)))))
212 (defun a-with-clause (state) ;; so named to avoid with-xxx macro convention
213 (let ((place (eat state
)))
214 (push (list 'setf place
(eat state
:if
:=)) (prologue state
))))
216 (defun accumulate (kind item var state
)
218 (when (and (accum-kind state
) (not (eq kind
(accum-kind state
))))
219 (error "PS-LOOP encountered illegal ~a: ~a was already declared, and there can only be one kind of implicit accumulation per loop." kind
(accum-kind state
)))
220 (unless (accum-var state
)
221 (setf (accum-var state
)
222 (ps-gensym (string (loop-case kind
223 ((:minimize
:minimizing
) 'min
)
224 ((:maximize
:maximizing
) 'max
)
226 (setf (accum-kind state
) kind
))
227 (setf var
(accum-var state
)))
228 (let ((initial (loop-case kind
229 ((:sum
:summing
:count
:counting
) 0)
230 ((:maximize
:maximizing
:minimize
:minimizing
) nil
)
231 ((:collect
:collecting
:append
:appending
) '[])
232 ((:map
:mapping
) '{}))))
233 (push (list 'setf var initial
) (prologue state
)))
235 ((:sum
:summing
)`(incf ,var
,item
))
236 ((:count
:counting
)`(when ,item
(incf ,var
))) ;; note the JS semantics - neither 0 nor "" will count
237 ((:minimize
:minimizing
) `(setf ,var
(if (null ,var
) ,item
(min ,var
,item
))))
238 ((:maximize
:maximizing
) `(setf ,var
(if (null ,var
) ,item
(max ,var
,item
))))
239 ((:collect
:collecting
) `((@ ,var
'push
) ,item
))
240 ((:append
:appending
) `(setf ,var
(append ,var
,item
)))
241 ((:map
:mapping
) (destructuring-bind (key val
) item
242 `(setf (getprop ,var
,key
) ,val
)))))
244 (defun repeat-clause (state)
245 (let ((index (ps-gensym)))
246 (setf (tokens state
) (append `(,index
:from
0 :below
,(eat state
)) (tokens state
)))
249 (defun while-clause (state)
250 (push-iter-clause (list nil nil nil
(eat state
)) state
))
252 (defun until-clause (state)
253 (push-iter-clause (list nil nil nil
`(not ,(eat state
))) state
))
255 (defun body-clause (term state
)
258 (let* ((test-form (eat state
))
259 (seqs (list (body-clause (eat state
:atom
) state
)))
261 (loop while
(eq (as-keyword (peek state
)) :and
)
263 (push (body-clause (eat state
:atom
) state
) seqs
))
264 (when (eq (as-keyword (peek state
)) :else
)
266 (push (body-clause (eat state
:atom
) state
) alts
)
267 (loop while
(eq (as-keyword (peek state
)) :and
)
269 (push (body-clause (eat state
:atom
) state
) alts
)))
270 (when (eq (as-keyword (peek state
)) :end
)
273 `(,(loop-case term
((:unless
) 'unless
) (otherwise 'when
))
276 `(if ,(loop-case term
277 ((:unless
) `(not ,test-form
))
278 (otherwise test-form
))
279 (progn ,@(reverse seqs
))
280 (progn ,@(reverse alts
))))))
281 ((:sum
:summing
:collect
:collecting
:append
:appending
:count
:counting
282 :minimize
:minimizing
:maximize
:maximizing
)
283 (accumulate term
(eat state
) (eat state
:if
:into
) state
))
284 ((:map
:mapping
) (let ((key (eat state
)))
285 (multiple-value-bind (val valp
)
288 (error "MAP must be followed by a TO to specify value."))
289 (accumulate :map
(list key val
) (eat state
:if
:into
) state
))))
290 ((:do
:doing
) (eat state
:progn
))
291 (:return
`(return-from ,(name state
) ,(eat state
)))
292 (otherwise (err "a PS-LOOP keyword" term
))))
294 (defun clause (state)
295 (let ((term (eat state
:atom
)))
297 (:named
(setf (name state
) (eat state
:symbol
)))
298 (:with
(a-with-clause state
))
299 (:initially
(push (eat state
:progn
) (prologue state
)))
300 (:for
(for-clause state
))
301 (:repeat
(repeat-clause state
))
302 (:while
(while-clause state
))
303 (:until
(until-clause state
))
304 (:finally
(push (eat state
:progn
) (finally state
)))
305 (otherwise (push-body-clause (body-clause term state
) state
)))))
307 (defun parse-ps-loop (terms)
308 (cond ((null terms
) (err "loop definition" nil
))
309 (t (let ((state (make-instance 'loop-state
:tokens terms
)))
310 (loop :while
(tokens state
) :do
(clause state
))
313 (defun fold-iterations-where-possible (clauses)
315 (loop :for clause
:in clauses
:do
316 (assert (member (car clause
) '(:iter
:body
)))
318 (when (and (eq (car clause
) :iter
) (eq (caar folded
) :iter
))
319 (destructuring-bind (tag place init step test
&optional js-obj
) clause
320 (declare (ignore tag
))
321 (when (null place
) ;; can't combine two iterations that both have state
322 (assert (not (or init step js-obj
)) nil
"Invalid iteration ~a: PLACE should not be null." clause
)
323 (assert test nil
"Iteration ~a has neither PLACE nor TEST." clause
)
324 (unless (sixth (car folded
)) ;; js-obj means a for..in loop and those can't have tests
325 (let ((prev-test (fifth (car folded
))))
326 (setf (fifth (car folded
)) (if prev-test
`(and ,prev-test
,test
) test
))
327 (setf folded? t
))))))
329 (push clause folded
))))
332 (defun organize-iterations (clauses)
333 ;; we want clauses to start with a master loop to provide the
334 ;; skeleton for everything else. secondary iterations are ok but
335 ;; will be generated inside the body of this master loop
336 (unless (eq (caar clauses
) :iter
)
337 (push (list :iter nil nil nil t
) clauses
))
338 ;; unify adjacent test expressions by ANDing them together where possible
339 (setf clauses
(fold-iterations-where-possible clauses
))
340 ;; if leading iteration has a binding expression, replace it with a var
341 (destructuring-bind (tag place init step test
&optional js-obj
) (car clauses
)
342 (assert (eq tag
:iter
))
343 (when (complex-js-expr? place
)
344 (assert (null js-obj
) nil
"Invalid iteration ~a: FOR..IN can't have a binding expression." (car clauses
))
345 (let ((var (ps-gensym)))
347 (push (list :iter place var var nil
) clauses
)
348 (push (list :iter var init step test
) clauses
))))
351 (defun build-body (clauses firstvar
)
352 (cond ((null clauses
) nil
)
353 ((eq (caar clauses
) :body
)
354 (cons (second (car clauses
)) (build-body (cdr clauses
) firstvar
)))
355 (t (destructuring-bind (tag place init step test
) (car clauses
)
356 (assert (eq tag
:iter
))
357 (let ((body (build-body (cdr clauses
) firstvar
)))
359 (push `(unless ,test
(break)) body
))
361 (let ((expr (if (tree-equal init step
) init
`(if ,firstvar
,init
,step
))))
363 (cond ((and (atom place
) (eq expr init
))
364 `((let ((,place
,expr
)) ,@body
)))
365 ;; can't use LET because EXPR may reference PLACE
366 ((atom place
) `((var ,place
,expr
) ,@body
))
367 ;; BIND has scoping problems. For example,
368 ;; (loop :for (a b) = x :then b) doesn't work
369 ;; since EXPR is referencing part of PLACE.
370 ;; But the following is ok for known uses so far.
371 (t `((bind ,place
,expr
,@body
)))))))
374 (defun master-loop (master-iter body
)
375 (destructuring-bind (tag place init step test
&optional js-obj
) master-iter
376 (assert (eq tag
:iter
))
377 (cond ((null place
) `(while ,test
,@body
))
379 (assert (not (or init step test
)) nil
"Unexpected iteration state in for..in loop: ~a" master-iter
)
380 `(for-in (,place
,js-obj
) ,@body
))
381 (t (assert (atom place
) nil
"Unexpected destructuring list ~a in master loop" place
)
382 `(for ((,place
,init
)) (,(or test t
)) ((setf ,place
,step
)) ,@body
)))))
384 (defun build-loop (clauses)
385 (destructuring-bind (master . rest
) clauses
386 (assert (eq (car master
) :iter
) nil
"First clause is not master loop: ~a" master
)
387 (let* ((firstvar (loop :for
(tag nil init step
) :in rest
388 :when
(and (eq tag
:iter
) (not (tree-equal init step
)))
389 :do
(return (ps-gensym "first"))))
390 (body (build-body rest firstvar
)))
392 (setf body
(append body
`((setf ,firstvar nil
)))))
393 (let ((form (master-loop master body
)))
394 (if firstvar
`(let ((,firstvar t
)) ,form
) form
)))))
396 (defun prologue-wrap (prologue body
)
397 (cond ((null prologue
) body
)
398 ((equal 'setf
(caar prologue
))
399 (destructuring-bind (place expr
) (cdr (car prologue
))
402 (cond ((atom place
) (cons `(var ,place
,expr
) body
))
403 (t `((bind ,place
,expr
,@body
)))))))
406 (cons (car prologue
) body
)))))
408 (defpsmacro loop
(&rest keywords-and-forms
)
409 (let ((state (parse-ps-loop keywords-and-forms
)))
410 (let* ((clauses (organize-iterations (reverse (clauses state
))))
411 (main `(,(build-loop (organize-iterations clauses
))
412 ,@(reverse (finally state
))
413 ,@(awhen (accum-var state
) (list it
))))
414 (full `(block ,(name state
) ,@(prologue-wrap (prologue state
) main
))))
415 (if (accum-var state
)