plan.lisp 21.3 KB
Newer Older
1
2
3
;;;; -------------------------------------------------------------------------
;;;; Plan

4
5
(asdf/package:define-package :asdf/plan
  (:recycle :asdf/plan :asdf)
6
  (:use :asdf/common-lisp :asdf/driver :asdf/upgrade
7
   :asdf/component :asdf/operation :asdf/system
8
   :asdf/cache :asdf/find-system :asdf/find-component
9
   :asdf/operation :asdf/action :asdf/lisp-action)
10
11
  (:export
   #:component-operation-time #:mark-operation-done
12
   #:plan-traversal #:sequential-plan #:*default-plan-class*
13
14
15
   #:planned-action-status #:plan-action-status #:action-already-done-p
   #:circular-dependency #:circular-dependency-actions
   #:node-for #:needed-in-image-p
16
   #:action-index #:action-planned-p #:action-valid-p
17
   #:plan-record-dependency
18
   #:normalize-forced-systems #:action-forced-p #:action-forced-not-p
19
   #:map-direct-dependencies #:reduce-direct-dependencies #:direct-dependencies
20
   #:visit-dependencies #:compute-action-stamp #:traverse-action
21
   #:circular-dependency #:circular-dependency-actions
22
   #:call-while-visiting-action #:while-visiting-action
23
   #:make-plan #:plan-actions #:perform-plan #:plan-operates-on-p
24
25
   #:planned-p #:index #:forced #:forced-not #:total-action-count
   #:planned-action-count #:planned-output-action-count #:visited-actions
26
   #:visiting-action-set #:visiting-action-list #:plan-actions-r
27
   #:required-components #:filtered-sequential-plan
28
   #:plan-system
29
30
   #:plan-action-filter #:plan-component-type #:plan-keep-operation #:plan-keep-component
   #:traverse-actions #:traverse-sub-actions))
31
(in-package :asdf/plan)
32

33
;;;; Generic plan traversal class
34
35
36
37
38
39
40
41
42
43
44
(with-upgradability ()
  (defclass plan-traversal ()
    ((system :initform nil :initarg :system :accessor plan-system)
     (forced :initform nil :initarg :force :accessor plan-forced)
     (forced-not :initform nil :initarg :force-not :accessor plan-forced-not)
     (total-action-count :initform 0 :accessor plan-total-action-count)
     (planned-action-count :initform 0 :accessor plan-planned-action-count)
     (planned-output-action-count :initform 0 :accessor plan-planned-output-action-count)
     (visited-actions :initform (make-hash-table :test 'equal) :accessor plan-visited-actions)
     (visiting-action-set :initform (make-hash-table :test 'equal) :accessor plan-visiting-action-set)
     (visiting-action-list :initform () :accessor plan-visiting-action-list))))
45
46


47
;;;; Planned action status
48
49
50
(with-upgradability ()
  (defgeneric plan-action-status (plan operation component)
    (:documentation "Returns the ACTION-STATUS associated to
51
52
the action of OPERATION on COMPONENT in the PLAN"))

53
54
  (defgeneric (setf plan-action-status) (new-status plan operation component)
    (:documentation "Sets the ACTION-STATUS associated to
55
56
the action of OPERATION on COMPONENT in the PLAN"))

57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
  (defclass planned-action-status (action-status)
    ((planned-p
      :initarg :planned-p :reader action-planned-p
      :documentation "a boolean, true iff the action was included in the plan.")
     (index
      :initarg :index :reader action-index
      :documentation "an integer, counting all traversed actions in traversal order."))
    (:documentation "Status of an action in a plan"))

  (defmethod print-object ((status planned-action-status) stream)
    (print-unreadable-object (status stream :type t :identity nil)
      (with-slots (stamp done-p planned-p index) status
        (format stream "~@{~S~^ ~}" :stamp stamp :done-p done-p :planned-p planned-p :index index))))

  (defmethod action-planned-p (action-status)
    (declare (ignorable action-status)) ; default method for non planned-action-status objects
    t)

  ;; TODO: eliminate NODE-FOR, use CONS.
  ;; Supposes cleaner protocol for operation initargs passed to MAKE-OPERATION.
  ;; However, see also component-operation-time and mark-operation-done
  (defun node-for (o c) (cons (type-of o) c))

  (defun action-already-done-p (plan operation component)
    (action-done-p (plan-action-status plan operation component)))

  (defmethod plan-action-status ((plan null) (o operation) (c component))
    (declare (ignorable plan))
    (multiple-value-bind (stamp done-p) (component-operation-time o c)
      (make-instance 'action-status :stamp stamp :done-p done-p)))

  (defmethod (setf plan-action-status) (new-status (plan null) (o operation) (c component))
    (declare (ignorable plan))
    (let ((to (type-of o))
          (times (component-operation-times c)))
      (if (action-done-p new-status)
          (remhash to times)
          (setf (gethash to times) (action-stamp new-status))))
    new-status))
96
97
98


;;;; forcing
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
(with-upgradability ()
  (defgeneric action-forced-p (plan operation component))
  (defgeneric action-forced-not-p (plan operation component))

  (defun normalize-forced-systems (x system)
    (etypecase x
      ((member nil :all) x)
      (cons (list-to-hash-set (mapcar #'coerce-name x)))
      ((eql t) (when system (list-to-hash-set (list (coerce-name system)))))))

  (defun action-override-p (plan operation component override-accessor)
    (declare (ignorable operation))
    (let* ((override (funcall override-accessor plan)))
      (and override
           (if (typep override 'hash-table)
               (gethash (coerce-name (component-system (find-component () component))) override)
               t))))

  (defmethod action-forced-p (plan operation component)
    (and
     ;; Did the user ask us to re-perform the action?
     (action-override-p plan operation component 'plan-forced)
     ;; You really can't force a builtin system and :all doesn't apply to it,
     ;; except it it's the specifically the system currently being built.
     (not (let ((system (component-system component)))
            (and (builtin-system-p system)
                 (not (eq system (plan-system plan))))))))

  (defmethod action-forced-not-p (plan operation component)
    (and
     ;; Did the user ask us to not re-perform the action?
     (action-override-p plan operation component 'plan-forced-not)
     ;; Force takes precedence over force-not
     (not (action-forced-p plan operation component))))

  (defmethod action-forced-p ((plan null) operation component)
    (declare (ignorable plan operation component))
    nil)

  (defmethod action-forced-not-p ((plan null) operation component)
    (declare (ignorable plan operation component))
    nil))
141
142
143


;;;; action-valid-p
144
145
146
147
148
149
150
151
152
153
154
(with-upgradability ()
  (defgeneric action-valid-p (plan operation component)
    (:documentation "Is this action valid to include amongst dependencies?"))
  (defmethod action-valid-p (plan operation (c component))
    (declare (ignorable plan operation))
    (if-let (it (component-if-feature c)) (featurep it) t))
  (defmethod action-valid-p (plan (o null) c) (declare (ignorable plan o c)) nil)
  (defmethod action-valid-p (plan o (c null)) (declare (ignorable plan o c)) nil)
  (defmethod action-valid-p ((plan null) operation component)
    (declare (ignorable plan operation component))
    (and operation component t)))
155
156
157


;;;; Is the action needed in this image?
158
159
160
(with-upgradability ()
  (defgeneric needed-in-image-p (operation component)
    (:documentation "Is the action of OPERATION on COMPONENT needed in the current image to be meaningful,
161
162
    or could it just as well have been done in another Lisp image?"))

163
164
165
166
167
168
  (defmethod needed-in-image-p ((o operation) (c component))
    ;; We presume that actions that modify the filesystem don't need be run
    ;; in the current image if they have already been done in another,
    ;; and can be run in another process (e.g. a fork),
    ;; whereas those that don't are meant to side-effect the current image and can't.
    (not (output-files o c))))
169
170
171


;;;; Visiting dependencies of an action and computing action stamps
172
173
174
(with-upgradability ()
  (defun map-direct-dependencies (operation component fun)
    (loop* :for (dep-o-spec . dep-c-specs) :in (component-depends-on operation component)
175
176
177
178
179
           :for dep-o = (find-operation operation dep-o-spec)
           :when dep-o
           :do (loop :for dep-c-spec :in dep-c-specs
                     :for dep-c = (and dep-c-spec (resolve-dependency-spec component dep-c-spec))
                     :when dep-c
180
                       :do (funcall fun dep-o dep-c))))
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232

  (defun reduce-direct-dependencies (operation component combinator seed)
    (map-direct-dependencies
     operation component
     #'(lambda (dep-o dep-c)
         (setf seed (funcall combinator dep-o dep-c seed))))
    seed)

  (defun direct-dependencies (operation component)
    (reduce-direct-dependencies operation component #'acons nil))

  (defun visit-dependencies (plan operation component dependency-stamper &aux stamp)
    (map-direct-dependencies
     operation component
     #'(lambda (dep-o dep-c)
         (when (action-valid-p plan dep-o dep-c)
           (latest-stamp-f stamp (funcall dependency-stamper dep-o dep-c)))))
    stamp)

  (defmethod compute-action-stamp (plan (o operation) (c component) &key just-done)
    ;; In a distant future, get-file-stamp and component-operation-time
    ;; shall also be parametrized by the plan, or by a second model object.
    (let* ((stamp-lookup #'(lambda (o c)
                             (if-let (it (plan-action-status plan o c)) (action-stamp it) t)))
           (out-files (output-files o c))
           (in-files (input-files o c))
           ;; Three kinds of actions:
           (out-op (and out-files t)) ; those that create files on the filesystem
                                        ;(image-op (and in-files (null out-files))) ; those that load stuff into the image
                                        ;(null-op (and (null out-files) (null in-files))) ; dependency placeholders that do nothing
           ;; When was the thing last actually done? (Now, or ask.)
           (op-time (or just-done (component-operation-time o c)))
           ;; Accumulated timestamp from dependencies (or T if forced or out-of-date)
           (dep-stamp (visit-dependencies plan o c stamp-lookup))
           ;; Time stamps from the files at hand, and whether any is missing
           (out-stamps (mapcar (if just-done 'register-file-stamp 'get-file-stamp) out-files))
           (in-stamps (mapcar #'get-file-stamp in-files))
           (missing-in
             (loop :for f :in in-files :for s :in in-stamps :unless s :collect f))
           (missing-out
             (loop :for f :in out-files :for s :in out-stamps :unless s :collect f))
           (all-present (not (or missing-in missing-out)))
           ;; Has any input changed since we last generated the files?
           (earliest-out (stamps-earliest out-stamps))
           (latest-in (stamps-latest (cons dep-stamp in-stamps)))
           (up-to-date-p (stamp<= latest-in earliest-out))
           ;; If everything is up to date, the latest of inputs and outputs is our stamp
           (done-stamp (stamps-latest (cons latest-in out-stamps))))
      ;; Warn if some files are missing:
      ;; either our model is wrong or some other process is messing with our files.
      (when (and just-done (not all-present))
        (warn "~A completed without ~:[~*~;~*its input file~:p~2:*~{ ~S~}~*~]~
233
             ~:[~; or ~]~:[~*~;~*its output file~:p~2:*~{ ~S~}~*~]"
234
235
236
237
238
239
240
241
242
243
              (action-description o c)
              missing-in (length missing-in) (and missing-in missing-out)
              missing-out (length missing-out)))
      ;; Note that we use stamp<= instead of stamp< to play nice with generated files.
      ;; Any race condition is intrinsic to the limited timestamp resolution.
      (if (or just-done ;; The done-stamp is valid: if we're just done, or
              ;; if all filesystem effects are up-to-date and there's no invalidating reason.
              (and all-present up-to-date-p (operation-done-p o c) (not (action-forced-p plan o c))))
          (values done-stamp ;; return the hard-earned timestamp
                  (or just-done
Francois-Rene Rideau's avatar
Francois-Rene Rideau committed
244
245
246
                      out-op ;; a file-creating op is done when all files are up to date
                      ;; a image-effecting a placeholder op is done when it was actually run,
                      (and op-time (eql op-time done-stamp)))) ;; with the matching stamp
247
248
          ;; done-stamp invalid: return a timestamp in an indefinite future, action not done yet
          (values t nil)))))
249
250


251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
;;;; Generic support for plan-traversal
(with-upgradability ()
  (defgeneric plan-record-dependency (plan operation component))

  (defgeneric call-while-visiting-action (plan operation component function)
    (:documentation "Detect circular dependencies"))

  (defmethod initialize-instance :after ((plan plan-traversal)
                                         &key (force () fp) (force-not () fnp) system
                                         &allow-other-keys)
    (with-slots (forced forced-not) plan
      (when fp (setf forced (normalize-forced-systems force system)))
      (when fnp (setf forced-not (normalize-forced-systems force-not system)))))

  (defmethod (setf plan-action-status) (new-status (plan plan-traversal) (o operation) (c component))
    (setf (gethash (node-for o c) (plan-visited-actions plan)) new-status))

  (defmethod plan-action-status ((plan plan-traversal) (o operation) (c component))
    (or (and (action-forced-not-p plan o c) (plan-action-status nil o c))
        (values (gethash (node-for o c) (plan-visited-actions plan)))))

  (defmethod action-valid-p ((plan plan-traversal) (o operation) (s system))
    (and (not (action-forced-not-p plan o s)) (call-next-method)))

  (defmethod call-while-visiting-action ((plan plan-traversal) operation component fun)
    (with-accessors ((action-set plan-visiting-action-set)
                     (action-list plan-visiting-action-list)) plan
      (let ((action (cons operation component)))
        (when (gethash action action-set)
          (error 'circular-dependency :actions
                 (member action (reverse action-list) :test 'equal)))
        (setf (gethash action action-set) t)
        (push action action-list)
        (unwind-protect
             (funcall fun)
          (pop action-list)
          (setf (gethash action action-set) nil))))))
288
289
290


;;;; Actual traversal: traverse-action
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
(with-upgradability ()
  (define-condition circular-dependency (system-definition-error)
    ((actions :initarg :actions :reader circular-dependency-actions))
    (:report (lambda (c s)
               (format s (compatfmt "~@<Circular dependency: ~3i~_~S~@:>")
                       (circular-dependency-actions c)))))

  (defmacro while-visiting-action ((p o c) &body body)
    `(call-while-visiting-action ,p ,o ,c #'(lambda () ,@body)))

  (defgeneric traverse-action (plan operation component needed-in-image-p))

  (defmethod traverse-action (plan operation component needed-in-image-p)
    (block nil
      (unless (action-valid-p plan operation component) (return nil))
      (plan-record-dependency plan operation component)
      (let* ((aniip (needed-in-image-p operation component))
             (eniip (and aniip needed-in-image-p))
             (status (plan-action-status plan operation component)))
        (when (and status (or (action-done-p status) (action-planned-p status) (not eniip)))
          ;; Already visited with sufficient need-in-image level: just return the stamp.
          (return (action-stamp status)))
        (labels ((visit-action (niip)
                   (visit-dependencies plan operation component
                                       #'(lambda (o c) (traverse-action plan o c niip)))
                   (multiple-value-bind (stamp done-p)
                       (compute-action-stamp plan operation component)
                     (let ((add-to-plan-p (or (eql stamp t) (and niip (not done-p)))))
                       (cond
                         ((and add-to-plan-p (not niip)) ;; if we need to do it,
                          (visit-action t)) ;; then we need to do it in the image!
                         (t
                          (setf (plan-action-status plan operation component)
                                (make-instance
                                 'planned-action-status
                                 :stamp stamp
                                 :done-p (and done-p (not add-to-plan-p))
                                 :planned-p add-to-plan-p
                                 :index (if status (action-index status) (incf (plan-total-action-count plan)))))
                          (when add-to-plan-p
                            (incf (plan-planned-action-count plan))
                            (unless aniip
                              (incf (plan-planned-output-action-count plan))))
                          stamp))))))
          (while-visiting-action (plan operation component) ; maintain context, handle circularity.
            (visit-action eniip)))))))
337
338
339


;;;; Sequential plans (the default)
340
341
342
(with-upgradability ()
  (defclass sequential-plan (plan-traversal)
    ((actions-r :initform nil :accessor plan-actions-r)))
343

344
  (defgeneric plan-actions (plan))
345
346
  (defmethod plan-actions ((plan list))
    plan)
347
348
  (defmethod plan-actions ((plan sequential-plan))
    (reverse (plan-actions-r plan)))
349

350
351
352
353
  (defmethod plan-record-dependency ((plan sequential-plan)
                                     (operation operation) (component component))
    (declare (ignorable plan operation component))
    (values))
354

355
356
357
358
  (defmethod (setf plan-action-status) :after
      (new-status (p sequential-plan) (o operation) (c component))
    (when (action-planned-p new-status)
      (push (cons o c) (plan-actions-r p)))))
359
360
361


;;;; high-level interface: traverse, perform-plan, plan-operates-on-p
362
(with-upgradability ()
363
364
365
366
367
  (defgeneric make-plan (plan-class operation component &key &allow-other-keys)
    (:documentation
     "Generate and return a plan for performing OPERATION on COMPONENT."))
  (define-convenience-action-methods make-plan (plan-class operation component &key))

368
369
  (defgeneric perform-plan (plan &key))
  (defgeneric plan-operates-on-p (plan component))
370

371
  (defvar *default-plan-class* 'sequential-plan)
372

373
  (defmethod make-plan (plan-class (o operation) (c component) &rest keys &key &allow-other-keys)
374
375
    (let ((plan (apply 'make-instance
                       (or plan-class *default-plan-class*)
376
                       :system (component-system c) keys)))
377
      (traverse-action plan o c t)
378
      plan))
379

380
  (defmethod perform-plan :around ((plan t) &key)
381
382
383
384
    (let ((*package* *package*)
          (*readtable* *readtable*))
      (with-compilation-unit () ;; backward-compatibility.
        (call-next-method))))   ;; Going forward, see deferred-warning support in lisp-build.
385

386
387
388
  (defmethod perform-plan ((plan t) &rest keys &key &allow-other-keys)
    (apply 'perform-plan (plan-actions plan) keys))

389
390
391
392
  (defmethod perform-plan ((steps list) &key force &allow-other-keys)
    (loop* :for (o . c) :in steps
           :when (or force (not (nth-value 1 (compute-action-stamp nil o c))))
           :do (perform-with-restarts o c)))
393

394
395
396
  (defmethod plan-operates-on-p ((plan plan-traversal) (component-path list))
    (plan-operates-on-p (plan-actions plan) component-path))

397
398
399
  (defmethod plan-operates-on-p ((plan list) (component-path list))
    (find component-path (mapcar 'cdr plan)
          :test 'equal :key 'component-find-path)))
400

401

402
;;;; Incidental traversals
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
(with-upgradability ()
  (defclass filtered-sequential-plan (sequential-plan)
    ((action-filter :initform t :initarg :action-filter :reader plan-action-filter)
     (component-type :initform t :initarg :component-type :reader plan-component-type)
     (keep-operation :initform t :initarg :keep-operation :reader plan-keep-operation)
     (keep-component :initform t :initarg :keep-component :reader plan-keep-component)))

  (defmethod initialize-instance :after ((plan filtered-sequential-plan)
                                         &key (force () fp) (force-not () fnp)
                                           other-systems)
    (declare (ignore force force-not))
    (with-slots (forced forced-not action-filter system) plan
      (unless fp (setf forced (normalize-forced-systems (if other-systems :all t) system)))
      (unless fnp (setf forced-not (normalize-forced-systems (if other-systems nil :all) system)))
      (setf action-filter (ensure-function action-filter))))

  (defmethod action-valid-p ((plan filtered-sequential-plan) o c)
    (and (funcall (plan-action-filter plan) o c)
         (typep c (plan-component-type plan))
         (call-next-method)))

  (defmethod traverse-actions (actions &rest keys &key plan-class &allow-other-keys)
    (let ((plan (apply 'make-instance (or plan-class 'filtered-sequential-plan) keys)))
      (loop* :for (o . c) :in actions :do
             (traverse-action plan o c t))
428
      plan))
429

430
  (define-convenience-action-methods traverse-sub-actions (operation component &key))
431
432
433
434
435
436
437
438
439
440
441
442
443
  (defmethod traverse-sub-actions ((operation operation) (component component) &rest keys &key &allow-other-keys)
    (apply 'traverse-actions (direct-dependencies operation component)
           :system (component-system component) keys))

  (defmethod plan-actions ((plan filtered-sequential-plan))
    (with-slots (keep-operation keep-component) plan
      (loop* :for (o . c) :in (call-next-method)
             :when (and (typep o keep-operation)
                        (typep c keep-component))
             :collect (cons o c))))

  (defmethod required-components (system &rest keys &key (goal-operation 'load-op) &allow-other-keys)
    (remove-duplicates
444
445
446
     (mapcar 'cdr (plan-actions
                   (apply 'traverse-sub-actions goal-operation system
                          (remove-plist-key :goal-operation keys))))
447
     :from-end t)))
448