package toffee

Build not yet checked
  1. Overview
  2. Docs
CSS layout engine for OCaml (Flexbox, Grid, Block)

Install

dune-project
 Dependency

Authors

Maintainers

Sources

mosaic-0.3.0.tbz
sha256=a92cbbcbe016fb19fb0a749222da0e459a9567aef3f4c7340d9bd6b71c53ed6f
sha512=6a7ab054605538bb31a2b73a1a6d093981a2704c9f0af5852221c05735290d74aca7c7282298c4d0f91e86a800e2ccd94b4918af883cd963449c758eb6b272b3

doc/src/toffee.tree/cache.ml.html

Source file cache.ml

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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
96
97
98
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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
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
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
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
288
289
290
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
337
338
339
340
(* A port of Taffy's cache (src/tree/cache.rs): the final layout and up to
   [cache_size] measurements, each found by its full key and evicted by second
   chance (CLOCK). *)

module Geometry = Toffee_geometry

(* Taffy keeps 9, fewer than a flex column asks each of its children in one
   layout under a root that sizes it by its content: three questions (the
   max-content and min-content heights, then the size at a known height) at
   the max-content width, at the min-content width, and at each definite width
   the column is tried at, those once with the parent's width and once
   without. A scroll box's content in a column is tried at three definite
   widths, 24 questions. They come in the same order in every layout, and
   second chance over fewer entries than questions evicts each one before it
   is asked again, so no child hits. *)
let cache_size = 24

(* A key. Every field is a float, so an entry is a single flat block, which a
   store overwrites in place.

   [width_key] and [height_key] encode an axis's known dimension when there is
   one, and else its available space: a known dimension as itself, a definite
   available space as its negation, min-content as negative infinity and
   max-content as infinity (Taffy's [mixed_cache_key]). A negative available
   space negates to a value a known dimension can take too, so [known] tells
   which axes the two keys give a known dimension: 1 the width, 2 the height,
   3 both, 0 neither. [parent_width] and [parent_height] are the parent size,
   infinity for none. [axis] is the requested axis: 1 horizontal, 2 vertical,
   3 both. *)
type entry = {
  mutable width_key : float;
  mutable height_key : float;
  mutable known : float;
  mutable parent_width : float;
  mutable parent_height : float;
  mutable axis : float;
}

(* The absent entry, told apart by physical equality and never written. *)
let no_entry =
  {
    width_key = nan;
    height_key = nan;
    known = nan;
    parent_width = nan;
    parent_height = nan;
    axis = nan;
  }

(* [entries.(cache_size)] keys the final layout and the others the
   measurements, and [outputs] holds their results at the same indices. The
   arrays are made by the first store, as many nodes are never laid out. An
   entry counts only while its valid bit is set, so clearing a cache keeps its
   entries for the next stores to overwrite. A hit returns the result as it was
   stored, with its [Some], so that asking a cache allocates nothing. [state]
   packs those bits and the rest of Taffy's cache into one int: which
   measurements were used since the eviction cursor last passed them (one bit
   each), which entries are valid (one bit each), the cursor (5 bits) and the
   cache's mode (3 bits, see [mode]). *)
type t = {
  mutable entries : entry array;
  mutable outputs : Layout_output.t option array;
  mutable state : int;
}

let used_mask = (1 lsl cache_size) - 1
let valid_shift = cache_size
let valid_mask = ((1 lsl (cache_size + 1)) - 1) lsl valid_shift
let cursor_shift = valid_shift + cache_size + 1
let mode_shift = cursor_shift + 5
let recently_used t = t.state land used_mask
let valid t index = t.state land (1 lsl (valid_shift + index)) <> 0
let cursor t = (t.state lsr cursor_shift) land 0x1f
let cache_mode t = (t.state lsr mode_shift) land 0x7
let set_recently_used t used = t.state <- t.state land lnot used_mask lor used

let set_cursor t cursor =
  t.state <-
    t.state land lnot (0x1f lsl cursor_shift) lor (cursor lsl cursor_shift)

let set_cache_mode t mode =
  t.state <- t.state land lnot (0x7 lsl mode_shift) lor (mode lsl mode_shift)

let make () = { entries = [||]; outputs = [||]; state = 0 }

type clear_state = Cleared | Already_empty

(* The inputs that affect a layout but are not in the key: its sizing mode and
   which of its vertical margins are collapsible. They change for a node only
   when its parent's algorithm or its own style does, so instead of keying each
   entry on them a cache records the one mode its entries were computed with
   (Taffy's [CacheMode]). *)
let mode inputs =
  let collapsible = Layout_input.vertical_margins_are_collapsible inputs in
  (match Layout_input.sizing_mode inputs with
    | Sizing_mode.Inherent_size -> 1
    | Content_size -> 0)
  lor (if collapsible.start then 2 else 0)
  lor if collapsible.end_ then 4 else 0

let axis_key = function
  | Requested_axis.Horizontal -> 1.
  | Vertical -> 2.
  | Both -> 3.
[@@inline]

let mixed_key known (available : Available_space.t) =
  match known with
  | Some value -> value
  | None -> (
      match available with
      | Definite value -> -.value
      | Min_content -> neg_infinity
      | Max_content -> infinity)
[@@inline]

(* Which dimensions are known, and which of those are not definite. *)
let known_key (known : float option Geometry.size)
    (definite : bool Geometry.size) =
  (match known.width with
    | Some _ -> if definite.width then 1. else 5.
    | None -> 0.)
  +.
  match known.height with
  | Some _ -> if definite.height then 2. else 10.
  | None -> 0.
[@@inline]

let parent_key = function Some value -> value | None -> infinity [@@inline]

(* Keys compare by their bits, as in Taffy. *)
let same (a : float) (b : float) =
  Int64.equal (Int64.bits_of_float a) (Int64.bits_of_float b)
[@@inline]

(* The parent height an entry is keyed on: the parent's height when
   [style] resolves a percentage or calc height, minimum height or maximum
   height against it, and else negative infinity, which no parent height
   takes. A layout reads its parent's height through those properties
   alone. *)
let parent_height_key (style : Toffee_style.t)
    (parent : float option Geometry.size) =
  let reads (size : Toffee_style.Dimension.t Geometry.size) =
    Toffee_style.Dimension.is_percent size.height
    || Toffee_style.Dimension.is_calc size.height
  in
  if
    reads (Toffee_style.size style)
    || reads (Toffee_style.min_size style)
    || reads (Toffee_style.max_size style)
  then parent_key parent.height
  else neg_infinity

let entry inputs ~parent_height =
  let known = Layout_input.known_dimensions inputs in
  let available = Layout_input.available_space inputs in
  let parent = Layout_input.parent_size inputs in
  {
    width_key = mixed_key known.width available.width;
    height_key = mixed_key known.height available.height;
    known = known_key known (Layout_input.known_dimensions_are_definite inputs);
    parent_width = parent_key parent.width;
    parent_height;
    axis = axis_key (Layout_input.axis inputs);
  }

(* Makes [entries.(index)] a valid entry keyed on [inputs] and
   [parent_height]: the entry there
   overwritten, or a new one in place of [no_entry]. *)
let set t index inputs ~parent_height =
  if Array.length t.entries = 0 then (
    t.entries <- Array.make (cache_size + 1) no_entry;
    t.outputs <- Array.make (cache_size + 1) None);
  let e = t.entries.(index) in
  (if e == no_entry then t.entries.(index) <- entry inputs ~parent_height
   else
     let known = Layout_input.known_dimensions inputs in
     let available = Layout_input.available_space inputs in
     let parent = Layout_input.parent_size inputs in
     e.width_key <- mixed_key known.width available.width;
     e.height_key <- mixed_key known.height available.height;
     e.known <-
       known_key known (Layout_input.known_dimensions_are_definite inputs);
     e.parent_width <- parent_key parent.width;
     e.parent_height <- parent_height;
     e.axis <- axis_key (Layout_input.axis inputs));
  t.state <- t.state lor (1 lsl (valid_shift + index))

let get t style inputs =
  if cache_mode t <> mode inputs then None
  else
    let known = Layout_input.known_dimensions inputs in
    let available = Layout_input.available_space inputs in
    let parent = Layout_input.parent_size inputs in
    let width_key = mixed_key known.width available.width in
    let height_key = mixed_key known.height available.height in
    let known =
      known_key known (Layout_input.known_dimensions_are_definite inputs)
    in
    let parent_width = parent_key parent.width in
    let axis = axis_key (Layout_input.axis inputs) in
    match Layout_input.run_mode inputs with
    | Run_mode.Perform_layout ->
        if
          valid t cache_size
          &&
          let e = t.entries.(cache_size) in
          same e.width_key width_key
          && same e.height_key height_key
          && e.known = known
          && same e.parent_width parent_width
          && same e.parent_height (parent_height_key style parent)
          && e.axis = axis
        then t.outputs.(cache_size)
        else None
    | Compute_size ->
        let parent_height = parent_height_key style parent in
        let found = ref (-1) and i = ref 0 in
        while !found < 0 && !i < cache_size do
          if
            valid t !i
            &&
            let e = t.entries.(!i) in
            same e.width_key width_key
            && same e.height_key height_key
            && e.known = known
            && same e.parent_width parent_width
            && same e.parent_height parent_height
            (* A measurement for a single axis may hold garbage in the
               other, so it answers only queries for that axis; one for both
               axes answers any. *)
            && (e.axis = 3. || e.axis = axis)
          then found := !i;
          incr i
        done;
        if !found < 0 then None
        else (
          set_recently_used t (recently_used t lor (1 lsl !found));
          t.outputs.(!found))
    | Perform_hidden_layout -> None

let clear t =
  if t.state land valid_mask = 0 then Already_empty
  else (
    t.outputs.(cache_size) <- None;
    t.state <- t.state land (0x7 lsl mode_shift);
    Cleared)

let carries_margin_collapse output =
  let zero (m : Collapsible_margin_set.t) =
    m.positive = 0. && m.negative = 0.
  in
  Layout_output.margins_can_collapse_through output
  || (not (zero (Layout_output.top_margin output)))
  || not (zero (Layout_output.bottom_margin output))

let store t style inputs output =
  match Layout_input.run_mode inputs with
  | Run_mode.Perform_hidden_layout -> ()
  | (Perform_layout | Compute_size) as run_mode -> (
      let mode = mode inputs in
      if cache_mode t <> mode then (
        ignore (clear t);
        set_cache_mode t mode);
      match run_mode with
      | Perform_layout ->
          set t cache_size inputs
            ~parent_height:
              (parent_height_key style (Layout_input.parent_size inputs));
          t.outputs.(cache_size) <- Some output
      | Compute_size ->
          (* A measurement keeps only the size and comes back through
             [Layout_output.from_outer_size], without margin-collapse
             metadata: a result that carries some is not cached. *)
          if not (carries_margin_collapse output) then (
            let size = Layout_output.size output in
            let known = Layout_input.known_dimensions inputs in
            let available = Layout_input.available_space inputs in
            let parent = Layout_input.parent_size inputs in
            let width_key = mixed_key known.width available.width in
            let height_key = mixed_key known.height available.height in
            let known =
              known_key known
                (Layout_input.known_dimensions_are_definite inputs)
            in
            let parent_width = parent_key parent.width in
            let parent_height = parent_height_key style parent in
            let axis = axis_key (Layout_input.axis inputs) in
            let index = ref (-1) and i = ref 0 in
            while !index < 0 && !i < cache_size do
              if
                valid t !i
                &&
                let e = t.entries.(!i) in
                same e.width_key width_key
                && same e.height_key height_key
                && e.known = known
                && same e.parent_width parent_width
                && same e.parent_height parent_height
                && e.axis = axis
              then index := !i;
              incr i
            done;
            if !index < 0 then (
              (* Second chance: pass over the entries used since the cursor
                 last passed them, clearing their bit, and replace the first
                 that was not. *)
              let cursor = ref (cursor t)
              and used = ref (recently_used t) in
              while !used land (1 lsl !cursor) <> 0 do
                used := !used land lnot (1 lsl !cursor);
                cursor := (!cursor + 1) mod cache_size
              done;
              index := !cursor;
              set_recently_used t !used;
              set_cursor t ((!cursor + 1) mod cache_size));
            set t !index inputs ~parent_height;
            t.outputs.(!index) <-
              Some
                (Layout_output.from_outer_size
                   { Geometry.Sizef.width = size.width; height = size.height });
            set_recently_used t (recently_used t lor (1 lsl !index)))
      | Perform_hidden_layout -> ())

(* The entry is valid, even in a cache that had none, as dirtying stops at a
   node whose cache is already empty and takes its ancestors to be dirty
   already, but no inputs match its key: no requested axis is NaN. *)
let forget_final_layout t =
  if Array.length t.entries = 0 then (
    t.entries <- Array.make (cache_size + 1) no_entry;
    t.outputs <- Array.make (cache_size + 1) None);
  let e = t.entries.(cache_size) in
  if e == no_entry then
    (* A copy, as [no_entry] is never written *)
    t.entries.(cache_size) <- { no_entry with axis = nan }
  else e.axis <- nan;
  t.outputs.(cache_size) <- None;
  t.state <- t.state lor (1 lsl (valid_shift + cache_size))

let is_empty t = t.state land valid_mask = 0