tobogganSe connecter

louise

Clone avec HTTPS, un jeton personnel en mot de passe, ou avec SSH, une clé ajoutée dans vos paramètres.

1159 lignes · 30904 octetsBrut · Historique
1/// The differential fuzzer's program generator (issue #352; see
2/// fuzz/README.md): draws a small, deterministic, well-typed Louise
3/// program from LOUISE_FUZZ_SEED and prints it.
4/// crates/louise_codegen_c/tests/fuzz.rs runs each program interpreted
5/// and natively and compares stdout, exit code and the leak oracle.
6///
7/// Generated programs are deterministic: every random choice happens
8/// here, at generation time (the one exception reaches `std/random`
9/// through `random.with_seed`, which is deterministic too). They
10/// terminate by construction: recursion decreases an Int bounded at the
11/// call site, and list sizes are bounded.
12
13import gen
14import std/io
15import std/list
16import std/os
17import std/random.{type random}
18import std/ref.{type Ref, type st}
19import std/result
20import std/string
21
22/// The types expressions are generated at. `TChoice` is the program's
23/// generated enum and `TRec` its generated record; a program declares
24/// them at the top when it uses them.
25type Ty
26{ TInt, TBool, TString, TList(Ty), TOpt(Ty), TPair(Ty, Ty), TChoice, TRec }
27
28/// Generation state: a fresh-name counter, the imports the program
29/// needs, and the declarations, helpers and effects its statements and
30/// expressions may use.
31type Ctx<h>
32{ Ctx(
33 ctr: Ref<h, Int>
34 , imports: Ref<h, List<String>>
35 , helpers: Ref<h, List<(String, List<Ty>, Ty)>>
36 , decls: Ref<h, List<String>>
37 , effects: Ref<h, List<(String, String, String)>>
38 , handler_fns: Ref<h, List<String>>
39 , recursive: Ref<h, List<String>>
40 , fields: List<(String, Ty)>
41 , choice: Bool
42 )
43}
44
45fn fresh :: c: Ctx<h> prefix: String -> String / <st<h>>
46{
47 let n = ref.get c.ctr
48 ref.set c.ctr (n + 1)
49 prefix <> show n
50}
51
52/// Records that the program must import `module`.
53fn need :: c: Ctx<h> module: String -> () / <st<h>>
54{
55 if list.any (ref.get c.imports) fn m { m == module }
56 {
57 ()
58 }
59 else
60 {
61 ref.set c.imports [module, ..ref.get c.imports]
62 }
63}
64
65fn ty_src :: ty: Ty -> String
66{
67 match ty
68 { TInt -> "Int"
69 , TBool -> "Bool"
70 , TString -> "String"
71 , TList(t) -> "List<" <> ty_src t <> ">"
72 , TOpt(t) -> "Option<" <> ty_src t <> ">"
73 , TPair(a, b) -> "(" <> ty_src a <> ", " <> ty_src b <> ")"
74 , TChoice -> "Choice"
75 , TRec -> "R"
76 }
77}
78
79fn ty_eq :: a: Ty b: Ty -> Bool
80{
81 match (a, b)
82 { (TInt, TInt) -> True
83 , (TBool, TBool) -> True
84 , (TString, TString) -> True
85 , (TChoice, TChoice) -> True
86 , (TRec, TRec) -> True
87 , (TList(x), TList(y)) -> ty_eq x y
88 , (TOpt(x), TOpt(y)) -> ty_eq x y
89 , (TPair(x1, y1), TPair(x2, y2)) -> ty_eq x1 x2 && ty_eq y1 y2
90 , _ -> False
91 }
92}
93
94/// Whether the generated program may `show` a value of `ty`: the
95/// generated `Choice` and `R` derive nothing.
96fn showable :: ty: Ty -> Bool
97{
98 match ty { TChoice -> False, TRec -> False, _ -> True }
99}
100
101/// A scalar type: Int, Bool or String.
102fn scalar :: -> Ty / <random>
103{
104 gen.weighted [(4, TInt), (2, TBool), (2, TString)]
105}
106
107/// A type for a `let`; compound types hold scalars, so programs stay
108/// small.
109fn any_ty :: c: Ctx<h> -> Ty / <random>
110{
111 let compound =
112 [ (3, TList(TInt))
113 , (2, TList(TString))
114 , (1, TOpt(TInt))
115 , (1, TPair(TInt, TString))
116 ]
117 let user =
118 list.append
119 (if c.choice { [(2, TChoice)] } else { [] })
120 (if list.length c.fields == 0 { [] } else { [(2, TRec)] })
121 gen.weighted
122 ( list.append
123 [(5, TInt), (2, TBool), (2, TString)]
124 (list.append compound user)
125 )
126}
127
128/// The names in `env` with type `ty`.
129fn vars_of :: env: List<(String, Ty)> ty: Ty -> List<String>
130{
131 list.map (list.filter env fn v { ty_eq v.1 ty }) fn v { v.0 }
132}
133
134/// `text`, an expression of type `ty`, made to pin `ty` down in the
135/// source: a bare `[]` or `None` leaves the element type unknown
136/// (E0403 where a trait needs it), so it becomes a one-element literal.
137fn pin :: c: Ctx<h> ty: Ty text: String -> String / <st<h>, random>
138{
139 match ty
140 { TList
141 ( t
142 ) -> if string.contains text "[]"
143 {
144 "[" <> literal c t <> "]"
145 }
146 else
147 {
148 text
149 }
150 , TOpt
151 ( t
152 ) -> if string.contains text "None"
153 {
154 "Some(" <> literal c t <> ")"
155 }
156 else
157 {
158 text
159 }
160 , _ -> text
161 }
162}
163
164/// A string literal of lowercase letters (no escapes needed).
165fn word :: -> String / <random>
166{
167 "\"" <> gen.string ~alphabet: (gen.lower ()) ~min: 1 ~max: 8 <> "\""
168}
169
170fn literal :: c: Ctx<h> ty: Ty -> String / <st<h>, random>
171{
172 match ty
173 { TInt -> show (gen.int ~low: (0 - 20) ~high: 99)
174 , TBool -> if gen.bool () { "True" } else { "False" }
175 , TString -> word ()
176 , TList(t) -> list_lit c t
177 , TOpt(t) -> if gen.bool () { "None" } else { "Some(" <> literal c t <> ")" }
178 , TPair(a, b) -> "(" <> literal c a <> ", " <> literal c b <> ")"
179 , TChoice -> choice_lit ()
180 , TRec -> rec_lit c
181 }
182}
183
184fn list_lit :: c: Ctx<h> t: Ty -> String / <st<h>, random>
185{
186 let n = gen.int ~low: 0 ~high: 3
187 "[" <> string.join (list.map (list.range 1 n) fn _ { literal c t }) ", "
188 <> "]"
189}
190
191fn choice_lit :: -> String / <random>
192{
193 match gen.int ~low: 0 ~high: 2
194 { 0 -> "A"
195 , 1 -> "B(" <> show (gen.int ~low: 0 ~high: 9) <> ")"
196 , _ -> "C(" <> word () <> ")"
197 }
198}
199
200fn rec_lit :: c: Ctx<h> -> String / <st<h>, random>
201{
202 "R("
203 <> string.join
204 (list.map c.fields fn f { f.0 <> ": " <> literal c f.1 })
205 ", "
206 <> ")"
207}
208
209/// Flatten lists of lines.
210fn concat :: xss: List<List<String>> -> List<String>
211{
212 list.flat_map xss fn xs { xs }
213}
214
215// --- Expressions -------------------------------------------------------
216
217/// An expression of type `ty`; `depth` bounds its size. Expressions are
218/// pure: effects happen in statements, so a value can travel anywhere.
219fn expr ::
220 c: Ctx<h>
221 env: List<(String, Ty)>
222 ty: Ty
223 depth: Int
224 -> String / <st<h>, random>
225{
226 let vars = vars_of env ty
227 if depth <= 0
228 {
229 match vars
230 { [] -> literal c ty
231 , _ -> gen.weighted [(1, literal c ty), (3, gen.pick vars)]
232 }
233 }
234 else
235 {
236 match gen.weighted (expr_choices c env ty)
237 { 0 -> literal c ty
238 , 1 -> if_expr c env ty depth
239 , 2 -> match_expr c env ty depth
240 , 3 -> gen.pick vars
241 , 4 -> call c env ty depth
242 , 5 -> gen.pick (projectable env ty)
243 , 6 -> gen.pick (fieldable c env ty)
244 , tag -> typed_expr c env ty depth tag
245 }
246 }
247}
248
249/// (weight, tag) choices for `expr`; tags below 10 are generic, the
250/// rest are per type (`typed_expr`).
251fn expr_choices ::
252 c: Ctx<h>
253 env: List<(String, Ty)>
254 ty: Ty
255 -> List<(Int, Int)> / <st<h>>
256{
257 let base = [(1, 0), (2, 1), (2, 2)]
258 let with_var = match vars_of env ty { [] -> base, _ -> [(3, 3), ..base] }
259 let with_call = match helpers_to c ty
260 { [] -> with_var, _ -> [(2, 4), ..with_var] }
261 let with_proj = match projectable env ty
262 { [] -> with_call, _ -> [(1, 5), ..with_call] }
263 let with_field = match fieldable c env ty
264 { [] -> with_proj, _ -> [(1, 6), ..with_proj] }
265 list.append with_field (typed_choices c env ty)
266}
267
268/// The helpers whose result type is `ty`: (name, parameter types,
269/// result type).
270fn helpers_to :: c: Ctx<h> ty: Ty -> List<(String, List<Ty>, Ty)> / <st<h>>
271{
272 list.filter (ref.get c.helpers) fn h { ty_eq h.2 ty }
273}
274
275/// Projections of `ty` out of pairs in scope: "v.0" / "v.1".
276fn projectable :: env: List<(String, Ty)> ty: Ty -> List<String>
277{
278 list.flat_map
279 env
280 fn v
281 {
282 match v.1
283 { TPair(a, b) ->
284 list.append
285 (if ty_eq a ty { [v.0 <> ".0"] } else { [] })
286 (if ty_eq b ty { [v.0 <> ".1"] } else { [] })
287 , _ -> []
288 }
289 }
290}
291
292/// Field accesses of `ty` on records in scope: "v.a".
293fn fieldable :: c: Ctx<h> env: List<(String, Ty)> ty: Ty -> List<String>
294{
295 list.flat_map
296 env
297 fn v
298 {
299 match v.1
300 { TRec ->
301 list.map
302 (list.filter c.fields fn f { ty_eq f.1 ty })
303 fn f { v.0 <> "." <> f.0 }
304 , _ -> []
305 }
306 }
307}
308
309/// The per-type (weight, tag) choices.
310fn typed_choices :: c: Ctx<h> env: List<(String, Ty)> ty: Ty -> List<(Int, Int)>
311{
312 match ty
313 { TInt -> [(3, 10), (1, 11), (1, 12), (1, 13), (1, 14)]
314 , TBool -> [(3, 10), (1, 11), (1, 12), (1, 13)]
315 , TString -> [(3, 10), (1, 11), (2, 12)]
316 , TList(t) ->
317 list.append
318 [(2, 10), (2, 11), (2, 12), (1, 13), (1, 14), (1, 15), (1, 16), (1, 17)]
319 (if ty_eq t TInt { [(1, 18)] } else { [] })
320 , TOpt(_) -> [(2, 10)]
321 , TPair(_, _) -> [(2, 10)]
322 , TChoice -> [(2, 10)]
323 , TRec -> match list.find env fn v { ty_eq v.1 TRec }
324 { None -> [(2, 10)], Some(_) -> [(2, 10), (1, 11)] }
325 }
326}
327
328/// A tag of `typed_choices`: an expression of `ty` specific to `ty`.
329fn typed_expr ::
330 c: Ctx<h>
331 env: List<(String, Ty)>
332 ty: Ty
333 depth: Int
334 tag: Int
335 -> String / <st<h>, random>
336{
337 let at = fn t { expr c env t (depth - 1) }
338 match ty
339 { TInt -> match tag
340 { 10 ->
341 "(" <> at TInt <> " " <> gen.pick ["+", "-", "*"] <> " " <> at TInt
342 <> ")"
343 , 11 ->
344 // Division and remainder panic on zero; usually the divisor is
345 // kept nonzero, sometimes it is not (the panic path is part of
346 // the oracle).
347 {
348 let divisor =
349 gen.weighted [(7, "((" <> at TInt <> " % 5) + 6)"), (3, at TInt)]
350 "(" <> at TInt <> " " <> gen.pick ["/", "%"] <> " " <> divisor <> ")"
351 }
352 , 12 ->
353 {
354 need c "std/list"
355 let u = scalar ()
356 "list.length (" <> pin c (TList(u)) (at (TList(u))) <> ")"
357 }
358 , 13 ->
359 {
360 need c "std/string"
361 "string.length (" <> at TString <> ")"
362 }
363 , _ ->
364 {
365 need c "std/list"
366 "list.fold (" <> pin c (TList(TInt)) (at (TList(TInt)))
367 <> ") 0 fn a x \{ a + x \}"
368 }
369 }
370 , TBool -> match tag
371 { 10 ->
372 "(" <> at TInt <> " " <> gen.pick ["<", "<=", ">", ">=", "==", "!="]
373 <> " "
374 <> at TInt
375 <> ")"
376 , 11 -> "(" <> at TString <> " == " <> at TString <> ")"
377 , 12 -> "(" <> at TBool <> " == " <> at TBool <> ")"
378 , _ ->
379 {
380 need c "std/list"
381 let u = scalar ()
382 let x = fresh c "x"
383 "list.any (" <> pin c (TList(u)) (at (TList(u))) <> ") fn " <> x
384 <> " \{ "
385 <> expr c [(x, u), ..env] TBool (depth - 1)
386 <> " \}"
387 }
388 }
389 , TString -> match tag
390 { 10 -> "(" <> at TString <> " <> " <> at TString <> ")"
391 , 11 -> match vars_of env TInt
392 { [] -> "(" <> at TString <> " <> " <> at TString <> ")"
393 , vars ->
394 "\"" <> gen.string ~alphabet: (gen.lower ()) ~min: 0 ~max: 4 <> "\{"
395 <> gen.pick vars
396 <> "\}"
397 <> gen.string ~alphabet: (gen.lower ()) ~min: 0 ~max: 4
398 <> "\""
399 }
400 , _ ->
401 {
402 let t = showable_ty ()
403 let arg = match vars_of env t
404 { [] -> pin c t (literal c t)
405 , vars -> gen.weighted [(2, gen.pick vars), (1, pin c t (literal c t))]
406 }
407 "show (" <> arg <> ")"
408 }
409 }
410 , TList(t) ->
411 {
412 need c "std/list"
413 match tag
414 { 10 ->
415 {
416 let n = gen.int ~low: 0 ~high: 3
417 "[" <> string.join (list.map (list.range 1 n) fn _ { at t }) ", "
418 <> "]"
419 }
420 , 11 -> "[" <> at t <> ", .." <> at (TList(t)) <> "]"
421 , 12 ->
422 {
423 let u = scalar ()
424 let x = fresh c "x"
425 "list.map (" <> pin c (TList(u)) (at (TList(u))) <> ") fn " <> x
426 <> " \{ "
427 <> expr c [(x, u), ..env] t (depth - 1)
428 <> " \}"
429 }
430 , 13 ->
431 {
432 let x = fresh c "x"
433 "list.filter (" <> pin c (TList(t)) (at (TList(t))) <> ") fn " <> x
434 <> " \{ "
435 <> expr c [(x, t), ..env] TBool (depth - 1)
436 <> " \}"
437 }
438 , 14 ->
439 "list.append (" <> pin c (TList(t)) (at (TList(t))) <> ") ("
440 <> pin c (TList(t)) (at (TList(t)))
441 <> ")"
442 , 15 -> "list.reverse (" <> pin c (TList(t)) (at (TList(t))) <> ")"
443 , 16 ->
444 "list.take (" <> pin c (TList(t)) (at (TList(t))) <> ") (" <> at TInt
445 <> ")"
446 , 17 ->
447 "list.drop (" <> pin c (TList(t)) (at (TList(t))) <> ") (" <> at TInt
448 <> ")"
449 , _ -> "list.range 1 ((" <> at TInt <> " % 5) + 1)"
450 }
451 }
452 , TOpt(t) -> "Some(" <> at t <> ")"
453 , TPair(a, b) -> "(" <> at a <> ", " <> at b <> ")"
454 , TChoice -> match gen.int ~low: 0 ~high: 2
455 { 0 -> "A", 1 -> "B(" <> at TInt <> ")", _ -> "C(" <> at TString <> ")" }
456 , TRec -> if tag == 11
457 {
458 match list.find env fn v { ty_eq v.1 TRec }
459 { None -> rec_lit c
460 , Some(v) ->
461 {
462 let f = gen.pick c.fields
463 "R(.." <> v.0 <> ", " <> f.0 <> ": " <> expr c env f.1 (depth - 1)
464 <> ")"
465 }
466 }
467 }
468 else
469 {
470 "R("
471 <> string.join
472 (list.map c.fields fn f { f.0 <> ": " <> expr c env f.1 (depth - 1) })
473 ", "
474 <> ")"
475 }
476 }
477}
478
479/// A showable type, for `show`.
480fn showable_ty :: -> Ty / <random>
481{
482 gen.weighted
483 [ (3, TInt)
484 , (2, TBool)
485 , (1, TList(TInt))
486 , (1, TOpt(TInt))
487 , (1, TPair(TInt, TString))
488 ]
489}
490
491fn if_expr ::
492 c: Ctx<h>
493 env: List<(String, Ty)>
494 ty: Ty
495 depth: Int
496 -> String / <st<h>, random>
497{
498 "if " <> expr c env TBool (depth - 1) <> " \{ " <> expr c env ty (depth - 1)
499 <> " \} else \{ "
500 <> expr c env ty (depth - 1)
501 <> " \}"
502}
503
504/// A single-line `match` expression of type `ty`.
505fn match_expr ::
506 c: Ctx<h>
507 env: List<(String, Ty)>
508 ty: Ty
509 depth: Int
510 -> String / <st<h>, random>
511{
512 let kinds =
513 list.append
514 [(2, "opt"), (2, "list"), (1, "int")]
515 ( list.append
516 (if c.choice { [(2, "choice")] } else { [] })
517 (if list.length c.fields == 0 { [] } else { [(1, "rec")] })
518 )
519 let at = fn t { expr c env t (depth - 1) }
520 match gen.weighted kinds
521 { "opt" ->
522 {
523 let u = scalar ()
524 let x = fresh c "m"
525 "match " <> pin c (TOpt(u)) (at (TOpt(u))) <> " \{ None -> " <> at ty
526 <> ", Some("
527 <> x
528 <> ") -> "
529 <> expr c [(x, u), ..env] ty (depth - 1)
530 <> " \}"
531 }
532 , "list" ->
533 {
534 let u = scalar ()
535 let x = fresh c "m"
536 let rest = fresh c "m"
537 "match " <> pin c (TList(u)) (at (TList(u))) <> " \{ [] -> " <> at ty
538 <> ", ["
539 <> x
540 <> ", .."
541 <> rest
542 <> "] -> "
543 <> expr c [(x, u), (rest, TList(u)), ..env] ty (depth - 1)
544 <> " \}"
545 }
546 , "choice" ->
547 {
548 let n = fresh c "m"
549 let s = fresh c "m"
550 "match " <> at TChoice <> " \{ A -> " <> at ty <> ", B(" <> n <> ") -> "
551 <> expr c [(n, TInt), ..env] ty (depth - 1)
552 <> ", C("
553 <> s
554 <> ") -> "
555 <> expr c [(s, TString), ..env] ty (depth - 1)
556 <> " \}"
557 }
558 , "rec" ->
559 {
560 let names = list.map c.fields fn _ { fresh c "m" }
561 let binds = list.zip names (list.map c.fields fn f { f.1 })
562 "match " <> at TRec <> " \{ R(" <> string.join names ", " <> ") -> "
563 <> expr c (list.append binds env) ty (depth - 1)
564 <> " \}"
565 }
566 , _ ->
567 "match " <> at TInt <> " \{ 0 -> " <> at ty <> ", _ if "
568 <> expr c env TBool (depth - 1)
569 <> " -> "
570 <> at ty
571 <> ", _ -> "
572 <> at ty
573 <> " \}"
574 }
575}
576
577/// A call of a helper returning `ty`. Recursive helpers take Int, and
578/// their argument is clamped so the recursion is short.
579fn call ::
580 c: Ctx<h>
581 env: List<(String, Ty)>
582 ty: Ty
583 depth: Int
584 -> String / <st<h>, random>
585{
586 let h = gen.pick (helpers_to c ty)
587 let args =
588 list.map
589 h.1
590 fn p
591 {
592 if ty_eq h.2 TInt && ty_eq p TInt && is_recursive c h.0
593 {
594 "((" <> expr c env TInt (depth - 1) <> " % 7))"
595 }
596 else
597 {
598 expr c env p (depth - 1)
599 }
600 }
601 "(" <> h.0 <> " " <> string.join (list.map args fn a { "(" <> a <> ")" }) " "
602 <> ")"
603}
604
605/// Whether `name` is a recursive helper (its argument is clamped at
606/// call sites).
607fn is_recursive :: c: Ctx<h> name: String -> Bool / <st<h>>
608{
609 list.any (ref.get c.recursive) fn n { n == name }
610}
611
612// --- Statements --------------------------------------------------------
613
614/// `count` statements at `indent`, extending `env` with what they
615/// bind. Returns the lines and the extended environment.
616fn stmts ::
617 c: Ctx<h>
618 env: List<(String, Ty)>
619 depth: Int
620 indent: String
621 count: Int
622 -> (List<String>, List<(String, Ty)>) / <st<h>, random>
623{
624 if count <= 0
625 {
626 ([], env)
627 }
628 else
629 {
630 let (first, env2) = stmt c env depth indent
631 let (rest, env3) = stmts c env2 depth indent (count - 1)
632 (list.append first rest, env3)
633 }
634}
635
636fn stmt ::
637 c: Ctx<h>
638 env: List<(String, Ty)>
639 depth: Int
640 indent: String
641 -> (List<String>, List<(String, Ty)>) / <st<h>, random>
642{
643 let choices = if depth > 0
644 {
645 [(4, 0), (3, 1), (2, 2), (1, 3), (2, 4), (1, 5), (2, 6), (1, 7), (1, 8)]
646 }
647 else
648 {
649 [(4, 0), (3, 1), (2, 4)]
650 }
651 match gen.weighted choices
652 { 0 ->
653 {
654 let ty = any_ty c
655 let name = fresh c "v"
656 ( [ indent <> "let " <> name <> ": " <> ty_src ty <> " = "
657 <> expr c env ty 2
658 ]
659 , [(name, ty), ..env]
660 )
661 }
662 , 1 -> ([indent <> "io.println (" <> expr c env TString 2 <> ")"], env)
663 , 2 ->
664 {
665 let cond = expr c env TBool 1
666 let (then_ls, _) =
667 stmts c env (depth - 1) (indent <> " ") (gen.int ~low: 1 ~high: 2)
668 let (else_ls, _) =
669 stmts c env (depth - 1) (indent <> " ") (gen.int ~low: 1 ~high: 2)
670 ( concat
671 [ [indent <> "if " <> cond, indent <> "\{"]
672 , then_ls
673 , [indent <> "\}", indent <> "else", indent <> "\{"]
674 , else_ls
675 , [indent <> "\}"]
676 ]
677 , env
678 )
679 }
680 , 3 -> (match_stmt c env (depth - 1) indent, env)
681 , 4 ->
682 {
683 let d = fresh c "d"
684 ([indent <> "defer io.println \"" <> d <> "\""], env)
685 }
686 , 5 -> (region_stmt c env indent, env)
687 , 6 -> handle_stmt c env indent
688 , 7 -> ( [ indent <> "io.println (match " <> try_decl c
689 <> " () \{ Ok(v) -> \"ok \" <> show v, Error(e) -> \"err \" <> e \})"
690 ]
691 , env
692 )
693 , _ ->
694 {
695 need c "std/random"
696 let v = fresh c "v"
697 ( [ indent <> "let " <> v <> " = random.with_seed "
698 <> show (gen.int ~low: 1 ~high: 1000)
699 <> " fn \{ random.range 1 6 + random.range 1 6 \}"
700 , indent <> "io.println (show " <> v <> ")"
701 ]
702 , env
703 )
704 }
705 }
706}
707
708/// A `match` statement whose arms print.
709fn match_stmt ::
710 c: Ctx<h>
711 env: List<(String, Ty)>
712 depth: Int
713 indent: String
714 -> List<String> / <st<h>, random>
715{
716 let kinds =
717 list.append
718 [(2, "opt"), (2, "list"), (1, "int")]
719 (if c.choice { [(2, "choice")] } else { [] })
720 match gen.weighted kinds
721 { "opt" ->
722 {
723 let u = scalar ()
724 let x = fresh c "m"
725 [ indent <> "match " <> pin c (TOpt(u)) (expr c env (TOpt(u)) depth)
726 , indent <> "\{ None -> io.println \"none\""
727 , indent <> ", Some(" <> x <> ") -> io.println (\"some \" <> show " <> x
728 <> ")"
729 , indent <> "\}"
730 ]
731 }
732 , "list" ->
733 {
734 let u = scalar ()
735 let x = fresh c "m"
736 [ indent <> "match " <> pin c (TList(u)) (expr c env (TList(u)) depth)
737 , indent <> "\{ [] -> io.println \"empty\""
738 , indent <> ", [" <> x <> ", ..] -> io.println (\"head \" <> show " <> x
739 <> ")"
740 , indent <> "\}"
741 ]
742 }
743 , "choice" ->
744 {
745 let n = fresh c "m"
746 let s = fresh c "m"
747 [ indent <> "match " <> expr c env TChoice depth
748 , indent <> "\{ A -> io.println \"ca\""
749 , indent <> ", B(" <> n <> ") -> io.println (\"cb \" <> show " <> n <> ")"
750 , indent <> ", C(" <> s <> ") -> io.println (\"cc \" <> " <> s <> ")"
751 , indent <> "\}"
752 ]
753 }
754 , _ -> [ indent <> "match " <> expr c env TInt depth
755 , indent <> "\{ 0 -> io.println \"zero\""
756 , indent <> ", _ -> io.println (\"other \" <> show ("
757 <> expr c env TInt depth
758 <> "))"
759 , indent <> "\}"
760 ]
761 }
762}
763
764/// A `region` with a reference: ends by reading it (an Int), or uses
765/// `use n <- ref.update` for the update-in-the-rest form.
766fn region_stmt ::
767 c: Ctx<h>
768 env: List<(String, Ty)>
769 indent: String
770 -> List<String> / <st<h>, random>
771{
772 need c "std/ref"
773 let rx = fresh c "rx"
774 let inner = indent <> " "
775 if gen.bool ()
776 {
777 let v = fresh c "v"
778 [ indent <> "let " <> v <> " = region"
779 , indent <> "\{"
780 , inner <> "let " <> rx <> " = ref.new " <> show (gen.int ~low: 0 ~high: 20)
781 , inner <> "ref.set " <> rx <> " (ref.get " <> rx <> " + "
782 <> expr c env TInt 1
783 <> ")"
784 , inner <> "ref.get " <> rx
785 , indent <> "\}"
786 , indent <> "io.println (show " <> v <> ")"
787 ]
788 }
789 else
790 {
791 [ indent <> "region"
792 , indent <> "\{"
793 , inner <> "let " <> rx <> " = ref.new " <> show (gen.int ~low: 0 ~high: 20)
794 , inner <> "use n <- ref.update " <> rx
795 , inner <> "io.println (\"upd \" <> show n)"
796 , inner <> "n + (" <> expr c env TInt 1 <> ")"
797 , indent <> "\}"
798 ]
799 }
800}
801
802/// The effect named for `kind`, declaring it first if need be; at most
803/// two effects per program ("", "" when the budget is spent).
804fn effect_for :: c: Ctx<h> kind: String -> (String, String) / <st<h>>
805{
806 match list.find (ref.get c.effects) fn e { e.0 == kind }
807 { Some(e) -> (e.1, e.2)
808 , None -> if list.length (ref.get c.effects) >= 2
809 {
810 ("", "")
811 }
812 else
813 {
814 let k = list.length (ref.get c.effects)
815 let en = "F" <> show k
816 let on = "op" <> show k
817 ref.set c.effects [(kind, en, on), ..ref.get c.effects]
818 (en, on)
819 }
820 }
821}
822
823/// A `handle` statement: one of the effect templates (issue #352's
824/// "effects + handlers").
825fn handle_stmt ::
826 c: Ctx<h>
827 env: List<(String, Ty)>
828 indent: String
829 -> (List<String>, List<(String, Ty)>) / <st<h>, random>
830{
831 let inner = indent <> " "
832 match gen.weighted
833 [(3, "ask"), (2, "collect"), (1, "cancel"), (2, "fail"), (1, "install")]
834 { "ask" -> match effect_for c "ask"
835 { ("", _) -> ([indent <> "io.println " <> word ()], env)
836 , (_, on) ->
837 {
838 let v = fresh c "v"
839 ( [ indent <> "let " <> v <> " = handle"
840 , indent <> "\{"
841 , inner <> on <> " () + (" <> expr c env TInt 1 <> ")"
842 , indent <> "\}"
843 , indent <> "with"
844 , indent <> "\{ " <> on <> " -> " <> show (gen.int ~low: 20 ~high: 60)
845 <> " \}"
846 , indent <> "io.println (show " <> v <> ")"
847 ]
848 , env
849 )
850 }
851 }
852 , "collect" -> match effect_for c "yield"
853 { ("", _) -> ([indent <> "io.println " <> word ()], env)
854 , (_, on) ->
855 {
856 let v = fresh c "v"
857 let yields =
858 list.map
859 (list.range 1 (gen.int ~low: 1 ~high: 3))
860 fn _ { inner <> on <> " (" <> expr c env TInt 1 <> ")" }
861 ( concat
862 [ [indent <> "let " <> v <> " = handle", indent <> "\{"]
863 , yields
864 , [ indent <> "\}"
865 , indent <> "with"
866 , indent <> "\{ " <> on
867 <> " x -> [x, ..resume ()], return _ -> [] \}"
868 , indent <> "io.println (show " <> v <> ")"
869 ]
870 ]
871 , env
872 )
873 }
874 }
875 , "cancel" -> match effect_for c "yield"
876 { ("", _) -> ([indent <> "io.println " <> word ()], env)
877 , (_, on) ->
878 {
879 let v = fresh c "v"
880 ( [ indent <> "let " <> v <> " = handle"
881 , indent <> "\{"
882 , inner <> "defer io.println \"cgone\""
883 , inner <> on <> " (" <> expr c env TInt 1 <> ")"
884 , inner <> on <> " (" <> expr c env TInt 1 <> ")"
885 , indent <> "\}"
886 , indent <> "with"
887 , indent <> "\{ " <> on <> " x -> x, return _ -> 0 - 1 \}"
888 , indent <> "io.println (show " <> v <> ")"
889 ]
890 , env
891 )
892 }
893 }
894 , "fail" -> match effect_for c "fail"
895 { ("", _) -> ([indent <> "io.println " <> word ()], env)
896 , (_, on) ->
897 {
898 let v = fresh c "v"
899 ( [ indent <> "let " <> v <> ": Result<Int, String> = handle"
900 , indent <> "\{"
901 , inner <> "Ok(if " <> expr c env TBool 1 <> " \{ " <> on <> " \"f"
902 <> show (gen.int ~low: 0 ~high: 9)
903 <> "\" \} else \{ "
904 <> expr c env TInt 1
905 <> " \})"
906 , indent <> "\}"
907 , indent <> "with"
908 , indent <> "\{ " <> on <> " r -> Error(r) \}"
909 , indent <> "io.println (match " <> v
910 <> " \{ Ok(x) -> \"ok \" <> show x, Error(e) -> \"err \" <> e \})"
911 ]
912 , env
913 )
914 }
915 }
916 , _ -> // `use <- h` installs the ask effect's handler for the rest of
917 // the block.
918 match effect_for c "ask"
919 { ("", _) -> ([indent <> "io.println " <> word ()], env)
920 , (en, on) ->
921 {
922 let hn = handler_fn c en on
923 ( [ indent <> "\{"
924 , inner <> "use <- " <> hn
925 , inner <> "io.println (show (" <> on <> " () + ("
926 <> expr c env TInt 1
927 <> ")))"
928 , indent <> "\}"
929 ]
930 , env
931 )
932 }
933 }
934 }
935}
936
937/// The handler-installing function for the ask effect `en` (declared
938/// once): `fn h0 :: action: fn() -> a / <F0 | e> -> a / <e>`.
939fn handler_fn :: c: Ctx<h> en: String on: String -> String / <st<h>, random>
940{
941 let hn = "h" <> string.slice en 1 (string.length en)
942 if list.any (ref.get c.handler_fns) fn h { h == en }
943 {
944 hn
945 }
946 else
947 {
948 ref.set c.handler_fns [en, ..ref.get c.handler_fns]
949 ref.set
950 c.decls
951 [ ..ref.get c.decls
952 , "fn " <> hn <> " :: action: fn() -> a / <" <> en <> " | e> -> a / <e>"
953 , "\{ handle"
954 , " \{ action () \}"
955 , " with"
956 , " \{ " <> on <> " -> " <> show (gen.int ~low: 1 ~high: 40) <> " \}"
957 , "\}"
958 ]
959 hn
960 }
961}
962
963/// A `use x <- result.try` helper (declared) and its name.
964fn try_decl :: c: Ctx<h> -> String / <st<h>, random>
965{
966 need c "std/result"
967 need c "std/string"
968 let t = fresh c "t"
969 let digits = fn
970 {
971 if gen.weighted [(3, True), (1, False)]
972 {
973 show (gen.int ~low: 0 ~high: 99)
974 }
975 else
976 {
977 "x"
978 }
979 }
980 ref.set
981 c.decls
982 [ ..ref.get c.decls
983 , "fn " <> t <> " :: -> Result<Int, String>"
984 , "\{ use a <- result.try (string.to_int \"" <> digits () <> "\")"
985 , " use b <- result.try (string.to_int \"" <> digits () <> "\")"
986 , " Ok(a + b)"
987 , "\}"
988 ]
989 t
990}
991
992// --- Declarations ------------------------------------------------------
993
994/// The small helper functions a program starts with; expressions may
995/// call them.
996fn gen_helpers :: c: Ctx<h> -> () / <st<h>, random>
997{
998 let count = gen.int ~low: 0 ~high: 2
999 list.each (list.range 1 count) fn i { gen_helper c (i - 1) }
1000}
1001
1002fn gen_helper :: c: Ctx<h> i: Int -> () / <st<h>, random>
1003{
1004 let name = "f" <> show i
1005 if gen.bool ()
1006 {
1007 // Recursive: Int in, Int out, decreasing; call sites clamp the
1008 // argument, so the recursion is short.
1009 let op = gen.pick ["+", "*"]
1010 ref.set
1011 c.decls
1012 [ ..ref.get c.decls
1013 , "fn " <> name <> " :: n: Int -> Int"
1014 , "\{ if n <= 0"
1015 , " \{ " <> show (gen.int ~low: 0 ~high: 9) <> " \}"
1016 , " else"
1017 , " \{ (" <> name <> " (n - 1)) " <> op <> " "
1018 <> show (gen.int ~low: 1 ~high: 9)
1019 <> " \}"
1020 , "\}"
1021 ]
1022 ref.set c.helpers [(name, [TInt], TInt), ..ref.get c.helpers]
1023 ref.set c.recursive [name, ..ref.get c.recursive]
1024 }
1025 else
1026 {
1027 let pt = scalar ()
1028 let rt = scalar ()
1029 let body = expr c [("a", pt)] rt 2
1030 ref.set
1031 c.decls
1032 [ ..ref.get c.decls
1033 , "fn " <> name <> " :: a: " <> ty_src pt <> " -> " <> ty_src rt
1034 , "\{ " <> body <> " \}"
1035 ]
1036 ref.set c.helpers [(name, [pt], rt), ..ref.get c.helpers]
1037 }
1038}
1039
1040/// The record type's fields: none (no record in this program), or two
1041/// to three named scalar fields.
1042fn record_fields :: -> List<(String, Ty)> / <random>
1043{
1044 match gen.weighted [(2, 0), (2, 2), (1, 3)]
1045 { 0 -> []
1046 , 2 -> [("a", scalar ()), ("b", scalar ())]
1047 , _ -> [("a", scalar ()), ("b", scalar ()), ("c", scalar ())]
1048 }
1049}
1050
1051/// A final `use x <- list.each` over a list in scope: the rest of the
1052/// block runs per element.
1053fn use_tail ::
1054 c: Ctx<h>
1055 env: List<(String, Ty)>
1056 indent: String
1057 -> List<String> / <st<h>, random>
1058{
1059 match list.find env fn v { match v.1 { TList(t) -> showable t, _ -> False } }
1060 { None -> []
1061 , Some(v) -> if gen.weighted [(1, True), (3, False)]
1062 {
1063 need c "std/list"
1064 [ indent <> "use x <- list.each " <> v.0
1065 , indent <> "io.println (\"each \" <> show x)"
1066 ]
1067 }
1068 else
1069 {
1070 []
1071 }
1072 }
1073}
1074
1075/// The declaration text of an effect.
1076fn effect_decl :: kind: String en: String on: String -> String
1077{
1078 if kind == "ask"
1079 {
1080 "effect " <> en <> " \{ fn " <> on <> " :: -> Int \}"
1081 }
1082 else
1083 {
1084 if kind == "yield"
1085 {
1086 "effect " <> en <> " \{ ctl " <> on <> " :: x: Int -> () \}"
1087 }
1088 else
1089 {
1090 "effect " <> en <> " \{ final ctl " <> on
1091 <> " :: reason: String -> Never \}"
1092 }
1093 }
1094}
1095
1096/// A whole program.
1097fn program :: -> String / <random>
1098{
1099 region
1100 {
1101 let fields = record_fields ()
1102 let c =
1103 Ctx( ctr: ref.new 0
1104 , imports: ref.new []
1105 , helpers: ref.new []
1106 , decls: ref.new []
1107 , effects: ref.new []
1108 , handler_fns: ref.new []
1109 , recursive: ref.new []
1110 , fields: fields
1111 , choice: gen.weighted [(2, True), (1, False)]
1112 )
1113 gen_helpers c
1114 let (body, env) = stmts c [] 2 " " (gen.int ~low: 4 ~high: 9)
1115 let tail = use_tail c env " "
1116 let imports =
1117 list.map
1118 (list.sort ["std/io", ..ref.get c.imports])
1119 fn m { "import " <> m }
1120 let types =
1121 list.append
1122 (if c.choice { ["type Choice \{ A, B(Int), C(String) \}"] } else { [] })
1123 ( match fields
1124 { [] -> []
1125 , _ -> [ "type R \{ R("
1126 <> string.join
1127 (list.map fields fn f { f.0 <> ": " <> ty_src f.1 })
1128 ", "
1129 <> ") \}"
1130 ]
1131 }
1132 )
1133 let effects =
1134 list.map
1135 (list.reverse (ref.get c.effects))
1136 fn e { effect_decl e.0 e.1 e.2 }
1137 string.join
1138 ( concat
1139 [ imports
1140 , [""]
1141 , types
1142 , effects
1143 , ref.get c.decls
1144 , ["", "pub fn main :: -> () / <io>", "\{"]
1145 , list.append body tail
1146 , ["\}"]
1147 ]
1148 )
1149 "\n"
1150 <> "\n"
1151 }
1152}
1153
1154pub fn main :: -> () / <io>
1155{
1156 let seed = match os.env "LOUISE_FUZZ_SEED"
1157 { Some(s) -> result.unwrap_or (string.to_int s) 1, None -> 1 }
1158 io.print (random.with_seed seed fn { program () })
1159}