1 ;;;; page-layout.scm -- page breaking and page layout
3 ;;;; source file of the GNU LilyPond music typesetter
5 ;;;; (c) 2004--2005 Jan Nieuwenhuizen <janneke@gnu.org>
6 ;;;; Han-Wen Nienhuys <hanwen@cs.uu.nl>
8 (use-modules (oop goops describe)
12 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
14 (define-class <optimally-broken-page-node> ()
15 (prev #:init-value '() #:accessor node-prev #:init-keyword #:prev)
16 (page #:init-value 0 #:accessor node-page-number #:init-keyword #:pageno)
17 (force #:init-value 0 #:accessor node-force #:init-keyword #:force)
18 (penalty #:init-value 0 #:accessor node-penalty #:init-keyword #:penalty)
19 (configuration #:init-value '() #:accessor node-configuration #:init-keyword #:configuration)
20 (lines #:init-value 0 #:accessor node-lines #:init-keyword #:lines))
22 (define-method (display (node <optimally-broken-page-node>) port)
23 (map (lambda (x) (display x port))
25 "Page " (node-page-number node)
26 " Lines: " (node-lines node)
27 " Penalty " (node-penalty node)
30 (define-method (node-system-numbers (node <optimally-broken-page-node>))
31 (map (lambda (ps) (ly:paper-system-property ps 'number))
34 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
36 (define (annotate? layout)
37 (eq? #t (ly:output-def-lookup layout 'annotatespacing)))
40 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
42 (define-public (paper-system-staff-extents ps)
43 (ly:paper-system-property ps 'refpoint-Y-extent '(0 . 0)))
46 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
49 ;; annotations are arrows indicating the numerical value of
51 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
53 (define (annotate-y-interval layout name extent is-length?)
54 ;; do something sensible for 0,0 intervals.
55 (set! extent (interval-widen extent 0.001))
59 (font-family . typewriter))
60 (layout-extract-page-properties layout)))
61 (annotation (interpret-markup
65 (make-whiteout-markup (make-simple-markup name))
69 (format "~$" (interval-length extent))
70 (format "(~$,~$)" (car extent)
73 (ly:stencil-translate-axis
74 (dimension-arrows (cons 0 (interval-length extent)))
75 (interval-start extent) Y)))
78 (ly:stencil-aligned-to annotation Y CENTER))
80 (set! annotation (ly:stencil-translate annotation
81 (cons 0 (interval-center extent))))
84 (ly:stencil-combine-at-edge arrows X RIGHT annotation 0.5 0))
87 (ly:make-stencil (ly:stencil-expr annotation)
88 (ly:stencil-extent annotation X)
92 (define (paper-system-annotate-last system layout)
94 ((bottomspace (ly:paper-system-property system 'bottom-space))
95 (y-extent (paper-system-extent system Y))
96 (x-extent (paper-system-extent system X))
97 (stencil (ly:paper-system-property system 'stencil))
99 (arrow (if (number? bottomspace)
100 (annotate-y-interval layout
102 (cons (- (car y-extent) bottomspace)
109 (ly:stencil-add stencil arrow)))
111 (set! (ly:paper-system-property system 'stencil)
115 (define (paper-system-annotate system layout)
116 "Add arrows and texts to indicate which lengths are set."
118 ((annotations (ly:make-stencil '() (cons 0 2) (cons 0 0)))
121 (ly:stencil-combine-at-edge a X RIGHT b 0.5 0)))
124 (lambda (name extent is-length?)
126 (append-stencil annotations
127 (annotate-y-interval layout
128 name extent is-length?)))))
130 (bbox-extent (paper-system-extent system Y))
131 (refp-extent (ly:paper-system-property system 'refpoint-Y-extent))
132 (next-space (ly:paper-system-property system 'next-space
133 (ly:output-def-lookup layout 'betweensystemspace)
135 (next-padding (ly:paper-system-property system 'next-padding
136 (ly:output-def-lookup layout 'betweensystempadding)
141 (if (number-pair? bbox-extent)
143 (annotate-property "Y-extent"
145 (annotate-property "next-padding"
146 (interval-translate (cons (- next-padding) 0) (car bbox-extent))
149 ;; titles don't have a refpoint-Y-extent.
150 (if (number-pair? refp-extent)
152 (annotate-property "refpoint-Y-extent"
155 (annotate-property "next-space"
156 (interval-translate (cons (- next-space) 0) (car refp-extent))
161 (set! (ly:paper-system-property system 'stencil)
163 (ly:paper-system-property system 'stencil)
165 (ly:stencil-expr annotations)
166 (ly:stencil-extent empty-stencil X)
167 (ly:stencil-extent empty-stencil Y)
172 (define (annotate-page layout stencil)
174 ((topmargin (ly:output-def-lookup layout 'topmargin))
175 (vsize (ly:output-def-lookup layout 'vsize))
176 (bottommargin (ly:output-def-lookup layout 'bottommargin))
177 (add-stencil (lambda (y)
179 (ly:stencil-add stencil y))
183 (ly:stencil-translate-axis
184 (annotate-y-interval layout "vsize"
191 (ly:stencil-translate-axis
192 (annotate-y-interval layout "topmargin"
193 (cons (- topmargin) 0)
198 (ly:stencil-translate-axis
199 (annotate-y-interval layout "bottommargin"
200 (cons (- vsize) (- bottommargin vsize))
206 (define (annotate-space-left page-stencil layout bottom-edge)
208 ((arrow (annotate-y-interval layout
210 (cons (- bottom-edge) (car (ly:stencil-extent page-stencil Y)))
213 (set! arrow (ly:stencil-translate-axis arrow 8 X))
214 (ly:stencil-add page-stencil arrow)))
217 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
220 (define (page-headfoot layout scopes number
221 sym separation-symbol dir last?)
222 "Create a stencil including separating space."
224 (let* ((header-proc (ly:output-def-lookup layout sym))
225 (sep (ly:output-def-lookup layout separation-symbol))
226 (stencil (ly:make-stencil "" '(0 . 0) '(0 . 0)))
228 (if (procedure? header-proc)
229 (header-proc layout scopes number last?)
233 (if (and (number? sep)
234 (ly:stencil? head-stencil)
235 (not (ly:stencil-empty? head-stencil)))
239 (ly:stencil-combine-at-edge
240 stencil Y dir head-stencil
245 (if (annotate? layout)
248 (ly:stencil-translate-axis
249 (annotate-y-interval layout
250 (symbol->string separation-symbol)
251 (cons (min 0 (* dir sep))
254 (/ (ly:output-def-lookup layout 'linewidth) 2)
257 (ly:stencil-translate-axis
258 (annotate-y-interval layout
261 (- (min 0 (* dir sep))
262 (ly:output-def-lookup layout 'pagetopspace))
265 (+ 7 (interval-center (ly:stencil-extent head-stencil X))) X)
274 (define-public (default-page-music-height layout scopes number last?)
275 "Printable area for music and titles; matches default-page-make-stencil."
276 (let* ((h (- (ly:output-def-lookup layout 'vsize)
277 (ly:output-def-lookup layout 'topmargin)
278 (ly:output-def-lookup layout 'bottommargin)))
280 (head (page-headfoot layout scopes number 'make-header 'headsep UP last?))
281 (foot (page-headfoot layout scopes number 'make-footer 'footsep DOWN last?))
283 (- h (if (ly:stencil? head)
284 (interval-length (ly:stencil-extent head Y))
286 (if (ly:stencil? foot)
287 (interval-length (ly:stencil-extent foot Y))
290 ;; (display (list "\n available" available head foot))
293 (define-public (default-page-make-stencil
294 lines offsets layout scopes number last?)
295 "Construct a stencil representing the page from LINES.
297 Offsets is a list of increasing numbers. They must be negated to
301 (let* ((topmargin (ly:output-def-lookup layout 'topmargin))
303 ;; TODO: naming vsize/hsize not analogous to TeX.
305 (vsize (ly:output-def-lookup layout 'vsize))
306 (hsize (ly:output-def-lookup layout 'hsize))
308 (system-xoffset (ly:output-def-lookup layout 'horizontalshift 0.0))
309 (system-separator-markup (ly:output-def-lookup layout 'systemSeparatorMarkup))
310 (system-separator-stencil (if (markup? system-separator-markup)
311 (interpret-markup layout
312 (layout-extract-page-properties layout)
313 system-separator-markup)
315 (lmargin (ly:output-def-lookup layout 'leftmargin))
316 (leftmargin (if lmargin
319 (ly:output-def-lookup layout 'linewidth)) 2)))
321 (rightmargin (ly:output-def-lookup layout 'rightmargin))
322 (bottom-edge (- vsize
323 (ly:output-def-lookup layout 'bottommargin)))
325 (head (page-headfoot layout scopes number 'make-header 'headsep UP last?))
326 (foot (page-headfoot layout scopes number 'make-footer 'footsep DOWN last?))
328 (head-height (if (ly:stencil? head)
329 (interval-length (ly:stencil-extent head Y))
332 (height-proc (ly:output-def-lookup layout 'page-music-height))
334 (page-stencil (ly:make-stencil '()
335 (cons leftmargin hsize)
336 (cons (- topmargin) 0)))
339 (add-to-page (lambda (stencil y)
341 (ly:stencil-add page-stencil
342 (ly:stencil-translate stencil
345 (- 0 head-height y topmargin))
349 (lambda (stencil-position)
350 (let* ((system (car stencil-position))
351 (stencil (paper-system-stencil system))
352 (y (cadr stencil-position))
353 (is-title (paper-system-title?
354 (car stencil-position))))
355 (add-to-page stencil y)
356 (if (and (ly:stencil? system-separator-stencil)
358 (not (paper-system-title? system))
359 (not (paper-system-title? last-system)))
361 system-separator-stencil
363 (car (paper-system-staff-extents last-system)))
365 (cdr (paper-system-staff-extents system))))))
366 (set! last-system system)
371 (if (annotate? layout)
373 (for-each (lambda (sys) (paper-system-annotate sys layout))
375 (paper-system-annotate-last (car (last-pair lines)) layout)))
380 "leftmargin " leftmargin "rightmargin " rightmargin
383 (set! page-stencil (ly:stencil-combine-at-edge
387 (not (ly:stencil-empty? head)))
389 (ly:make-stencil "" (cons 0 0) (cons 0 0)))
392 (map add-system (zip lines offsets))
394 (if (annotate? layout)
397 (annotate-space-left page-stencil layout
399 (if (ly:stencil? foot)
400 (interval-length (ly:stencil-extent foot Y))
405 (if (and (ly:stencil? foot)
406 (not (ly:stencil-empty? foot)))
410 (ly:stencil-translate
414 (- (car (ly:stencil-extent foot Y)))))))))
417 (ly:stencil-translate page-stencil (cons leftmargin 0)))
420 (if (annotate? layout)
421 (set! page-stencil (annotate-page layout page-stencil)))
426 ;;; optimal page breaking
428 ;;; This is not optimal page breaking, this is optimal distribution of
429 ;;; lines over pages; line breaks are a given.
434 ;; - separate function for word-wrap style breaking?
435 ;; - raggedbottom? raggedlastbottom?
437 (define-public (optimal-page-breaks lines paper-book)
438 "Return pages as a list starting with 1st page. Each page is a list
441 (define MAXPENALTY 1e9)
442 (define paper (ly:paper-book-paper paper-book))
443 (define scopes (ly:paper-book-scopes paper-book))
444 (define force-equalization-factor #f)
446 (define (page-height page-number last?)
447 (let ((p (ly:output-def-lookup paper 'page-music-height)))
450 (p paper scopes page-number last?)
453 (define (get-path node done)
454 "Follow NODE.PREV, and return as an ascending list of pages. DONE
455 is what have collected so far, and has ascending page numbers."
457 (if (is-a? node <optimally-broken-page-node>)
458 (get-path (node-prev node) (cons node done))
461 (define (combine-penalties force user best-paths)
462 (let* ((prev-force (if (null? best-paths)
464 (node-force (car best-paths))))
465 (prev-penalty (if (null? best-paths)
467 (node-penalty (car best-paths))))
468 (inter-system-space (ly:output-def-lookup paper 'betweensystemspace))
469 (relative-force (/ force inter-system-space))
470 (abs-relative-force (abs relative-force)))
473 (+ (* abs-relative-force (+ abs-relative-force 1))
475 (* force-equalization-factor (/ (abs (- prev-force force))
479 (define (space-systems page-height lines ragged?)
480 (let* ((global-inter-system-space
481 (ly:output-def-lookup paper 'betweensystemspace))
483 (ly:output-def-lookup paper 'pagetopspace))
484 (global-fixed-dist (ly:output-def-lookup paper 'betweensystempadding))
486 (system-vector (list->vector
488 (if (= (length lines) 1)
493 (append (map paper-system-staff-extents lines)
494 (if (= (length lines) 1)
502 (lambda (sys) (paper-system-extent sys Y)) lines)
503 (if (= (length lines) 1)
507 (system-count (vector-length real-extents))
511 (interval-end (vector-ref staff-extents 0)))
512 (interval-end (vector-ref real-extents 0))
514 (last-system (vector-ref system-vector (1- system-count)))
515 (bottom-space (if (ly:paper-system? last-system)
516 (ly:paper-system-property last-system 'bottom-space 0.0)
518 (space-left (- page-height
520 (apply + (map interval-length
521 (vector->list real-extents)))))
523 (space (- page-height
527 (vector-ref real-extents (1- system-count))))))
532 (upper-system (vector-ref system-vector idx))
533 (between-space (ly:paper-system-property upper-system 'next-space
534 global-inter-system-space))
535 (fixed-dist (ly:paper-system-property upper-system 'next-padding
538 (this-system-ext (vector-ref staff-extents idx))
539 (next-system-ext (vector-ref staff-extents (1+ idx)))
540 (fixed (max 0 (- (+ (interval-end next-system-ext)
542 (interval-start this-system-ext))))
543 (title1? (and (vector-ref system-vector idx)
544 (paper-system-title? (vector-ref system-vector idx)
547 (vector-ref system-vector (1+ idx))
548 (paper-system-title? (vector-ref system-vector (1+ idx)))))
551 ((and title2? title1?)
552 (ly:output-def-lookup paper 'betweentitlespace))
554 (ly:output-def-lookup paper 'aftertitlespace))
556 (ly:output-def-lookup paper 'beforetitlespace))
557 (else between-space))
559 (hooke (/ 1 (- ideal fixed))))
560 (list ideal hooke))))
562 (springs (map calc-spring (iota (1- system-count))))
566 (upper-system (vector-ref system-vector idx))
567 (fixed-dist (ly:paper-system-property upper-system 'next-padding
569 (this-system-ext (vector-ref real-extents idx))
570 (next-system-ext (vector-ref real-extents (1+ idx)))
572 (distance (max (- (+ (interval-end next-system-ext)
574 (interval-start this-system-ext)
576 (entry (list idx (1+ idx) distance)))
578 (rods (map calc-rod (iota (1- system-count))))
580 ;; we don't set ragged based on amount space left.
581 ;; raggedbottomlast = ##T is much more predictable
582 (result (ly:solve-spring-rod-problem
594 (display (list "\n# systems: " system-count
595 "\nreal-ext" real-extents "\nstaff-ext" staff-extents
596 "\ninterscore" global-inter-system-space
597 "\nspace-left" space-left
598 "\nspring,rod" springs rods
601 "\npage-height" page-height
605 "\npositions" positions "\n"))))
607 (cons force positions)))
609 (define (walk-paths done-lines best-paths current-lines last? current-best)
610 "Return the best optimal-page-break-node that contains
611 CURRENT-LINES. DONE-LINES.reversed ++ CURRENT-LINES is a consecutive
612 ascending range of lines, and BEST-PATHS contains the optimal breaks
613 corresponding to DONE-LINES.
615 CURRENT-BEST is the best result sofar, or #f."
618 (let* ((this-page-num (if (null? best-paths)
619 (ly:output-def-lookup paper 'firstpagenumber)
620 (1+ (node-page-number (car best-paths)))))
622 (ragged-all? (eq? #t (ly:output-def-lookup paper 'raggedbottom)))
623 (ragged-last? (eq? #t (ly:output-def-lookup paper 'raggedlastbottom)))
624 (ragged? (or ragged-all?
627 (page-height (page-height this-page-num last?))
628 (vertical-spacing (space-systems page-height current-lines ragged?))
629 (satisfied-constraints (car vertical-spacing))
630 (force (if satisfied-constraints
631 (if (and last? ragged-last?)
633 satisfied-constraints)
635 (positions (cdr vertical-spacing))
636 (get-break-penalty (lambda (sys)
637 (ly:paper-system-property sys 'penalty 0.0)))
638 (user-nobreak-penalties
640 (apply + (filter negative?
641 (map get-break-penalty
642 (cdr current-lines))))))
645 (max (get-break-penalty (car current-lines)) 0.0)
646 user-nobreak-penalties))
648 (total-penalty (combine-penalties
654 (< total-penalty (node-penalty current-best))))
655 (new-best (if better?
656 (make <optimally-broken-page-node>
657 #:prev (if (null? best-paths)
660 #:lines current-lines
661 #:pageno this-page-num
663 #:configuration positions
664 #:penalty total-penalty)
667 ;; (display total-penalty) (newline)
671 "\nuser pen " user-penalty
672 "\nsatisfied-constraints" satisfied-constraints
673 "\nlast? " last? "ragged?" ragged?
674 "\nbetter? " better? " total-penalty " total-penalty "\n"
675 "\nconfig " positions
677 "\nlines: " current-lines "\n")))
680 (display (list "\nnew-best is " (node-lines new-best)
682 (if (null? best-paths)
684 (node-lines (car best-paths))))))
686 (if (and (pair? done-lines)
687 ;; if this page is too full, adding another line won't help
688 satisfied-constraints)
689 (walk-paths (cdr done-lines) (cdr best-paths)
690 (cons (car done-lines) current-lines)
694 (define (walk-lines done best-paths todo)
695 "Return the best page breaking as a single
696 <optimal-page-break-node> for optimally breaking TODO ++
697 DONE.reversed. BEST-PATHS is a list of break nodes corresponding to
702 (let* ((this-line (car todo))
703 (last? (null? (cdr todo)))
704 (next (walk-paths done best-paths (list this-line) last? #f)))
706 ;; (display "\n***************")
707 (walk-lines (cons this-line done)
708 (cons next best-paths)
711 (define (line-number node)
712 (ly:paper-system-property (car (node-lines node)) 'number))
714 (ly:message (_ "Calculating page breaks..."))
715 (set! force-equalization-factor
716 (ly:output-def-lookup paper 'verticalequalizationfactor 0.3))
718 (let* ((best-break-node (walk-lines '() '() lines))
719 (break-nodes (get-path best-break-node '()))
720 (last-node (car (last-pair break-nodes))))
722 (define (node->page-stencil node)
723 (if (not (eq? node last-node))
726 ((ly:output-def-lookup paper 'page-make-stencil)
728 (node-configuration node)
731 (node-page-number node)
732 (eq? node best-break-node))))
733 (if (not (eq? node last-node))
735 (ly:progress (number->string
736 (car (last-pair (node-system-numbers node)))))
740 (if #f; (ly:get-option 'verbose)
743 "\nbreaks: " (map line-number break-nodes))
744 "\nsystems " (map node-lines break-nodes)
745 "\npenalties " (map node-penalty break-nodes)
746 "\nconfigs " (map node-configuration break-nodes))))
748 (let ((stencils (map node->page-stencil break-nodes)))