plum

#treesitter#compiler#wasm

git clone https://git.pyrossh.dev/plum

A statically typed, imperative programming language inspired by rust, python

c3fa217 — Peter John 2026-11-06T13:14:05+05:30 
FBIP stage 1: switch, stronger proof, Array.with, and fusion fixes
Files changed (56) hide show
  1. compiler/checker/src/callcheck.rs +1 -0
  2. compiler/checker/src/fncheck.rs +36 -1
  3. compiler/checker/src/infer.rs +18 -1
  4. compiler/checker/tests/checker/diagnostic_tests.rs +19 -0
  5. compiler/cli/src/main.rs +24 -10
  6. compiler/cli/src/program.rs +2 -2
  7. compiler/cli/tests/cli/fusion_agree_test.rs +49 -0
  8. compiler/cli/tests/cli/main.rs +2 -0
  9. compiler/cli/tests/cli/no_fbip_test.rs +43 -0
  10. compiler/core/src/ast.rs +4 -0
  11. compiler/core/src/closure_spec.rs +24 -4
  12. compiler/core/src/ctors.rs +10 -2
  13. compiler/core/src/drive.rs +42 -11
  14. compiler/core/src/forms.rs +1 -0
  15. compiler/core/src/parser.rs +4 -0
  16. compiler/core/src/purity.rs +55 -28
  17. compiler/core/src/reuse.rs +29 -5
  18. compiler/core/src/simplify.rs +85 -8
  19. compiler/core/src/trmc.rs +4 -1
  20. compiler/core/src/uniqueness.rs +599 -35
  21. compiler/core/tests/core/purity_test.rs +41 -0
  22. compiler/core/tests/core/record_init_test.rs +1 -1
  23. compiler/core/tests/core/uniqueness_test.rs +266 -6
  24. compiler/driver/src/lib.rs +20 -8
  25. compiler/driver/tests/driver_tests.rs +1 -1
  26. compiler/game/web-test/src/lib.rs +8 -2
  27. compiler/game/web-test/src/main.rs +2 -1
  28. compiler/lsp/src/main.rs +1 -1
  29. compiler/wasm-codegen/src/closurecalls.rs +3 -0
  30. compiler/wasm-codegen/src/construct.rs +7 -19
  31. compiler/wasm-codegen/src/context.rs +55 -0
  32. compiler/wasm-codegen/src/driver.rs +7 -4
  33. compiler/wasm-codegen/src/emit.rs +6 -8
  34. compiler/wasm-codegen/src/expr.rs +1 -0
  35. compiler/wasm-codegen/src/fnbody.rs +3 -0
  36. compiler/wasm-codegen/src/units.rs +3 -0
  37. compiler/wasm-codegen/tests/wasm_codegen/codegen_tests.rs +122 -0
  38. docs/backlog.md +1 -0
  39. docs/plans/2026-11-06-fbip-stage1.md +1 -1
  40. docs/plans/2026-11-06-fbip.benchmark.md +52 -0
  41. std/Array.plum +16 -0
  42. tests/fbip/aliasing.plum +602 -0
  43. tests/fbip/array_names.plum +26 -0
  44. tests/fbip/array_with.plum +228 -0
  45. tests/fbip/operator_methods.plum +36 -0
  46. tests/fbip/spread_ro_method.plum +40 -0
  47. tests/fbip_probes/array_set.plum +28 -0
  48. tests/fbip_probes/buffer_write.plum +25 -0
  49. tests/fbip_probes/map_set_get.plum +28 -0
  50. tests/fbip_probes/slice_push_field.plum +27 -0
  51. tests/fbip_probes/slice_push_helper.plum +27 -0
  52. tests/fbip_probes/slice_push_local.plum +24 -0
  53. tests/fbip_probes/struct_spread.plum +25 -0
  54. tests/param_defaults.plum +130 -0
  55. tests/shadowed_effects.plum +164 -0
  56. tests/shadowed_free_fn.plum +136 -0
compiler/checker/src/callcheck.rs CHANGED
@@ -463,6 +463,7 @@ pub(crate) fn inferOperatorCall(
463
463
  line: 0,
464
464
  column: 0,
465
465
  tail: ast::TailKind::NotTail,
466
+ unique: false,
466
467
  })
467
468
  })
468
469
  .clone()
compiler/checker/src/fncheck.rs CHANGED
@@ -27,7 +27,42 @@ pub(crate) fn checkFn(f: &ast::Fn, global_env: &TypeEnv, ctx: &CheckCtx) -> Vec<
27
27
  Some(r) => enumGenericsOf(r, ctx).to_vec(),
28
28
  None => Vec::new(),
29
29
  };
30
+ withFnScope(f, &owner, || {
31
+ let mut errors = checkParamDefaults(f, global_env, ctx);
30
- withFnScope(f, &owner, || checkFnBody(f, global_env, ctx))
32
+ errors.append(&mut checkFnBody(f, global_env, ctx));
33
+ errors
34
+ })
35
+ }
36
+
37
+ /// Checks `f`'s parameter defaults against the declared types and records their types.
38
+ /// A default runs at a call that leaves the argument out, in place of it: it sees globals and
39
+ /// the owner's members, not `f`'s other parameters or `self`.
40
+ fn checkParamDefaults(f: &ast::Fn, global_env: &TypeEnv, ctx: &CheckCtx) -> Vec<CheckError> {
41
+ let defaulted = || f.params.iter().filter(|p| matches!(p.ty, ast::ParamType::Type(_)));
42
+ if f.is_extern || defaulted().all(|p| p.default.is_none()) {
43
+ return Vec::new();
44
+ }
45
+ let mut env = global_env.clone();
46
+ if let Some(owner) = &f.type_param {
47
+ env.insert(OWNER_KEY.to_string(), TypeScheme::mono(PlumType::TNamed(owner.clone())));
48
+ }
49
+ let mut errors = Vec::new();
50
+ for p in defaulted() {
51
+ let Some(d) = &p.default else { continue };
52
+ let declared = paramTypeG(&p.ty);
53
+ let at = (f.line, f.column);
54
+ let say = |msg: String| format!("fn '{}': default of parameter '{}': {}", f.name, p.name, msg);
55
+ let (r, pos, resolution) = withFailure(|| inferExprWith(d, &env, ctx, Some(&declared)));
56
+ match r {
57
+ Ok(t) => {
58
+ if let Err(msg) = unifyArg(&declared, &t, d, ctx) {
59
+ errors.push(failureError(spanOf(d), false, at, say(msg)));
60
+ }
61
+ }
62
+ Err(msg) => errors.push(failureError(pos, resolution, at, say(msg))),
63
+ }
64
+ }
65
+ errors
31
66
  }
32
67
 
33
68
  /// Report the failure in flight at `e` (an operand or part that is the culprit) instead of at
compiler/checker/src/infer.rs CHANGED
@@ -641,8 +641,17 @@ pub(crate) fn inferExprInner(
641
641
  )),
642
642
  },
643
643
  ast::AttrKind::Method(call) => {
644
+ if call.name == ARRAY_WITH_IN_PLACE {
645
+ return Err(format!("'{ARRAY_WITH_IN_PLACE}' is for the compiler only: call `with`"));
646
+ }
644
647
  checkStaticUse(&attr.object, &obj_ty, &call.name, ctx)?;
648
+ // A `with` the uniqueness pass proved unshared runs `Array.withUnique` (in place).
649
+ let name = if call.unique && call.name == "with" && isArrayType(&obj_ty) {
650
+ ARRAY_WITH_IN_PLACE
651
+ } else {
652
+ call.name.as_str()
653
+ };
645
- inferMethodCall(&obj_ty, &call.name, &call.args, env, ctx, expected)
654
+ inferMethodCall(&obj_ty, name, &call.args, env, ctx, expected)
646
655
  }
647
656
  }
648
657
  }
@@ -706,3 +715,11 @@ pub(crate) fn checkStaticUse(
706
715
  }
707
716
  Ok(())
708
717
  }
718
+
719
+ /// `Array.with`'s in-place twin (std/Array.plum). Only the compiler picks it, for a `with` call
720
+ /// the uniqueness pass marked `unique`; a call written in source is an error.
721
+ pub(crate) const ARRAY_WITH_IN_PLACE: &str = "withUnique";
722
+
723
+ fn isArrayType(t: &PlumType) -> bool {
724
+ matches!(resolveRecorded(t), PlumType::TApp(k, _) if k == "Array")
725
+ }
compiler/checker/tests/checker/diagnostic_tests.rs CHANGED
@@ -42,6 +42,25 @@ fn binaryMismatchIsAtTheOffendingOperand() {
42
42
  assert!(es[0].message.contains("binary op"), "{es:?}");
43
43
  }
44
44
 
45
+ /// A parameter default is checked at its declaration, called or not.
46
+ #[test]
47
+ fn defaultMismatchIsAtTheDefault() {
48
+ let es = errors("fun f(b: Int = \"no\") -> Int = b\n\nfun main() -> Int = 1\n");
49
+ assert_eq!(es.len(), 1, "{es:?}");
50
+ assert_eq!(es[0].kind, DiagKind::Type, "{es:?}");
51
+ assert_eq!((es[0].line, es[0].column), (1, 16), "{es:?}");
52
+ assert!(es[0].message.contains("default of parameter 'b'"), "{es:?}");
53
+ }
54
+
55
+ /// A default runs in place of the argument at the call: it cannot read the other parameters.
56
+ #[test]
57
+ fn defaultCannotReadAParameter() {
58
+ let es = errors("fun f(a: Int, b: Int = a) -> Int = b\n\nfun main() -> Int = 1\n");
59
+ assert_eq!(es.len(), 1, "{es:?}");
60
+ assert_eq!(es[0].kind, DiagKind::Resolution, "{es:?}");
61
+ assert!(es[0].message.contains("undefined name 'a'"), "{es:?}");
62
+ }
63
+
45
64
  #[test]
46
65
  fn returnMismatchIsAtTheReturnedValue() {
47
66
  let es = errors("fun f() -> Int =\n x := 1\n true\n");
compiler/cli/src/main.rs CHANGED
@@ -47,6 +47,9 @@ enum Command {
47
47
  /// Root directory `import <path>` is resolved against (`import std/x` -> `<lib-path>/std/x.plum`)
48
48
  #[arg(long, default_value = ".")]
49
49
  lib_path: std::path::PathBuf,
50
+ /// No in-place updates: every spread copies and no cell is reused
51
+ #[arg(long)]
52
+ no_fbip: bool,
50
53
  },
51
54
  /// Run a Plum program: a game is served and opened in the browser, anything else runs under wasmtime
52
55
  Run {
@@ -58,6 +61,9 @@ enum Command {
58
61
  /// Skip the fusion (supercompiler) stage
59
62
  #[arg(long)]
60
63
  no_fusion: bool,
64
+ /// No in-place updates: every spread copies and no cell is reused
65
+ #[arg(long)]
66
+ no_fbip: bool,
61
67
  /// Games: asset root (default: the nearest `assets` folder beside the source or above it)
62
68
  #[arg(long)]
63
69
  assets: Option<std::path::PathBuf>,
@@ -85,6 +91,9 @@ enum Command {
85
91
  /// Skip the fusion (supercompiler) stage
86
92
  #[arg(long)]
87
93
  no_fusion: bool,
94
+ /// No in-place updates: every spread copies and no cell is reused
95
+ #[arg(long)]
96
+ no_fbip: bool,
88
97
  /// Game: output folder (default: `dist` in the current folder). Otherwise: executable path (default: the file's name, no extension)
89
98
  #[arg(short, long)]
90
99
  output: Option<std::path::PathBuf>,
@@ -107,6 +116,9 @@ enum Command {
107
116
  /// Skip the fusion (supercompiler) stage
108
117
  #[arg(long)]
109
118
  no_fusion: bool,
119
+ /// No in-place updates: every spread copies and no cell is reused
120
+ #[arg(long)]
121
+ no_fbip: bool,
110
122
  /// Root directory `import <path>` is resolved against (`import std/x` -> `<lib-path>/std/x.plum`)
111
123
  #[arg(long, default_value = ".")]
112
124
  lib_path: std::path::PathBuf,
@@ -129,8 +141,8 @@ fn main() {
129
141
  }
130
142
 
131
143
  /// The `--no-fusion` / `--explain-fusion` flags of a command, as explicit fusion options.
132
- fn fusionFlags(explain: bool, no_fusion: bool) -> plum_driver::PassOptions {
144
+ fn fusionFlags(explain: bool, no_fusion: bool, no_fbip: bool) -> plum_driver::PassOptions {
133
- plum_driver::PassOptions { fusion: !no_fusion, explain, ..plum_driver::PassOptions::default() }
145
+ plum_driver::PassOptions { fusion: !no_fusion, fbip: !no_fbip, explain, ..plum_driver::PassOptions::default() }
134
146
  }
135
147
 
136
148
  /// One diagnostic as `file:line:col: <kind>: message`. `entry` names the file when the
@@ -164,15 +176,16 @@ fn run() -> Result<()> {
164
176
  file,
165
177
  output,
166
178
  lib_path,
179
+ no_fbip,
167
- } => cmdCompile(file, output, lib_path),
180
+ } => cmdCompile(file, output, lib_path, no_fbip),
168
- Command::Run { file, lib_path, explain_fusion, no_fusion, assets, port, no_open, no_watch } => {
181
+ Command::Run { file, lib_path, explain_fusion, no_fusion, no_fbip, assets, port, no_open, no_watch } => {
169
- cmdRun(file, lib_path, fusionFlags(explain_fusion, no_fusion), GameOptions { assets, port, noOpen: no_open, noWatch: no_watch, output: None })
182
+ cmdRun(file, lib_path, fusionFlags(explain_fusion, no_fusion, no_fbip), GameOptions { assets, port, noOpen: no_open, noWatch: no_watch, output: None })
170
183
  }
171
- Command::Build { file, output, lib_path, assets, explain_fusion, no_fusion } => {
184
+ Command::Build { file, output, lib_path, assets, explain_fusion, no_fusion, no_fbip } => {
172
- cmdBuild(file, lib_path, fusionFlags(explain_fusion, no_fusion), GameOptions { assets, port: None, noOpen: false, noWatch: false, output })
185
+ cmdBuild(file, lib_path, fusionFlags(explain_fusion, no_fusion, no_fbip), GameOptions { assets, port: None, noOpen: false, noWatch: false, output })
173
186
  }
174
- Command::Test { paths, lib_path, explain_fusion, no_fusion } => {
187
+ Command::Test { paths, lib_path, explain_fusion, no_fusion, no_fbip } => {
175
- cmdTest(paths, lib_path, fusionFlags(explain_fusion, no_fusion))
188
+ cmdTest(paths, lib_path, fusionFlags(explain_fusion, no_fusion, no_fbip))
176
189
  }
177
190
  Command::Editor { editor, insiders } => editor::install(editor, insiders),
178
191
  }
@@ -283,8 +296,9 @@ fn cmdCompile(
283
296
  file: std::path::PathBuf,
284
297
  output: Option<std::path::PathBuf>,
285
298
  lib_path: std::path::PathBuf,
299
+ no_fbip: bool,
286
300
  ) -> Result<()> {
287
- let wasm_bytes = compileToWasm(&file, &lib_path, plum_driver::PassOptions::default())?;
301
+ let wasm_bytes = compileToWasm(&file, &lib_path, plum_driver::PassOptions { fbip: !no_fbip, ..plum_driver::PassOptions::default() })?;
288
302
 
289
303
  let out_path = output.unwrap_or_else(|| file.with_extension("wasm"));
290
304
  fs::write(&out_path, &wasm_bytes)
compiler/cli/src/program.rs CHANGED
@@ -65,7 +65,7 @@ pub fn tryCompileProgram(
65
65
  let out = plum_wasm_codegen::compile(&ast, &options).map_err(|mut ds| {
66
66
  if let Some(written) = &written {
67
67
  // Errors in the user's own `main` are reported under its name, not the renamed one.
68
- let own = plum_driver::PassOptions { closureSpec: false, fusion: false, trmc: false, explain: false };
68
+ let own = plum_driver::PassOptions { closureSpec: false, fusion: false, trmc: false, fbip: false, explain: false };
69
69
  if let Err(userErrors) = plum_driver::check(written, &own) {
70
70
  ds = userErrors;
71
71
  }
@@ -97,7 +97,7 @@ mod rebuildTests {
97
97
  use super::*;
98
98
 
99
99
  fn opts() -> plum_driver::PassOptions {
100
- plum_driver::PassOptions { closureSpec: false, fusion: false, trmc: false, explain: false }
100
+ plum_driver::PassOptions { closureSpec: false, fusion: false, trmc: false, fbip: false, explain: false }
101
101
  }
102
102
 
103
103
  #[test]
compiler/cli/tests/cli/fusion_agree_test.rs ADDED
@@ -0,0 +1,49 @@
1
+ #![allow(non_snake_case)]
2
+ //! Fusion must not change what a program does: these files assert the same answers with the
3
+ //! supercompiler stage on and off.
4
+ use std::process::Command;
5
+
6
+ fn plumBin() -> std::path::PathBuf {
7
+ let mut path = std::env::current_exe().unwrap();
8
+ path.pop();
9
+ if path.ends_with("deps") {
10
+ path.pop();
11
+ }
12
+ path.push("plum");
13
+ path
14
+ }
15
+
16
+ fn passesWithAndWithoutFusion(file: &str) {
17
+ let root = std::path::Path::new(env!("CARGO_MANIFEST_DIR")).ancestors().nth(2).unwrap();
18
+ for flags in [&[][..], &["--no-fusion"][..]] {
19
+ let out = Command::new(plumBin())
20
+ .arg("test")
21
+ .args(flags)
22
+ .arg(root.join("tests").join(file))
23
+ .arg("--lib-path")
24
+ .arg(root)
25
+ .output()
26
+ .expect("failed to run plum");
27
+ let stdout = String::from_utf8_lossy(&out.stdout);
28
+ let stderr = String::from_utf8_lossy(&out.stderr);
29
+ assert!(out.status.success(), "plum test {file} {flags:?} failed:\n{stdout}\n{stderr}");
30
+ }
31
+ }
32
+
33
+ /// A local, parameter, closure parameter or pattern binder shadows the free fn of its name.
34
+ #[test]
35
+ fn shadowedFreeFnAgrees() {
36
+ passesWithAndWithoutFusion("shadowed_free_fn.plum");
37
+ }
38
+
39
+ /// A binder named like a free fn, method or pattern name keeps its effect and its object.
40
+ #[test]
41
+ fn shadowedEffectsAgree() {
42
+ passesWithAndWithoutFusion("shadowed_effects.plum");
43
+ }
44
+
45
+ /// Parameter defaults of every kind compile at a call that leaves the argument out.
46
+ #[test]
47
+ fn paramDefaultsAgree() {
48
+ passesWithAndWithoutFusion("param_defaults.plum");
49
+ }
compiler/cli/tests/cli/main.rs CHANGED
@@ -4,8 +4,10 @@ mod assert_once_test;
4
4
  mod compile_tests;
5
5
  mod crash_test;
6
6
  mod explain_layout_test;
7
+ mod fusion_agree_test;
7
8
  mod game_entry_test;
8
9
  mod game_web_test;
9
10
  mod host_stub_test;
10
11
  mod main_result_test;
12
+ mod no_fbip_test;
11
13
  mod test_scope_test;
compiler/cli/tests/cli/no_fbip_test.rs ADDED
@@ -0,0 +1,43 @@
1
+ #![allow(non_snake_case)]
2
+ use std::process::Command;
3
+
4
+ fn plumBin() -> std::path::PathBuf {
5
+ let mut path = std::env::current_exe().unwrap();
6
+ path.pop();
7
+ if path.ends_with("deps") {
8
+ path.pop();
9
+ }
10
+ path.push("plum");
11
+ path
12
+ }
13
+
14
+ const SRC: &str = "import std/Int\nimport std/Str\nimport std/Io\n\nstruct Cell(label: Str, n: Int)\n\nfun main(io: Io) =\n c := Cell(label: \"c\", n: 0)\n for i := range 10\n c = Cell(..c, n: c.n + 1)\n io.printLn(\"{c.n}\")\n";
15
+
16
+ fn run(src: &std::path::Path, flags: &[&str]) -> (String, String) {
17
+ let root = std::path::Path::new(env!("CARGO_MANIFEST_DIR")).ancestors().nth(2).unwrap();
18
+ let out = Command::new(plumBin())
19
+ .args(["run", "--explain-fusion"])
20
+ .args(flags)
21
+ .args([src.to_str().unwrap(), "--lib-path", root.to_str().unwrap()])
22
+ .output()
23
+ .expect("failed to run plum");
24
+ let err = String::from_utf8_lossy(&out.stderr).to_string();
25
+ assert!(out.status.success(), "plum run failed: {err}");
26
+ (String::from_utf8_lossy(&out.stdout).to_string(), err)
27
+ }
28
+
29
+ /// `--no-fbip` is "no in-place updates": the spread is proved unique by default and not with the flag,
30
+ /// and the program prints the same either way.
31
+ #[test]
32
+ fn noFbipTurnsOffUniqueSpreads() {
33
+ let dir = std::env::temp_dir().join(format!("plum_no_fbip_{}", std::process::id()));
34
+ std::fs::create_dir_all(&dir).unwrap();
35
+ let src = dir.join("spread.plum");
36
+ std::fs::write(&src, SRC).unwrap();
37
+ let (outOn, errOn) = run(&src, &[]);
38
+ let (outOff, errOff) = run(&src, &["--no-fbip"]);
39
+ assert!(errOn.contains("unique spread at"), "default must prove the spread unique:\n{errOn}");
40
+ assert!(!errOff.contains("unique spread"), "--no-fbip must mark nothing:\n{errOff}");
41
+ assert_eq!(outOn, outOff);
42
+ assert_eq!(outOn.trim(), "10");
43
+ }
compiler/core/src/ast.rs CHANGED
@@ -988,6 +988,10 @@ pub struct FnCall {
988
988
  pub column: usize,
989
989
  /// Set by `tail::markTailCalls`: whether (and how) this call is in tail position.
990
990
  pub tail: TailKind,
991
+ /// Set by the uniqueness analysis on a method call named `with`: its receiver is provably
992
+ /// unshared and dead afterwards, so `Array.with` may write the array in place. Meaningless
993
+ /// (and ignored) on every other receiver type.
994
+ pub unique: bool,
991
995
  }
992
996
 
993
997
  /// How a call in tail position is made (see `tail.rs`). `NotTail` is the default.
compiler/core/src/closure_spec.rs CHANGED
@@ -372,10 +372,8 @@ impl<'h> Ctx<'h> {
372
372
  ExprKind::Question(_) => bad = true,
373
373
  ExprKind::Self_ => usesSelf = true,
374
374
  ExprKind::FnCall(call) => {
375
+ // a closure call, also when a free fn has that name: the local shadows it
375
- if binders.contains(&call.name)
376
+ if binders.contains(&call.name) || locals.contains(&call.name) {
376
- || (locals.contains(&call.name)
377
- && !self.fns.get(&call.name).is_some_and(|f| f.type_param.is_none()))
378
- {
379
377
  bad = true;
380
378
  }
381
379
  }
@@ -411,6 +409,11 @@ impl<'h> Ctx<'h> {
411
409
  if orig.is_extern || orig.is_export {
412
410
  return None;
413
411
  }
412
+ // Moved into the copy, a global the closure uses would resolve to a binder of the callee.
413
+ if self.captured(&orig, sid) {
414
+ self.copies.insert(ck, None);
415
+ return None;
416
+ }
414
417
  let name = format!("{}$c{}", orig.name, n);
415
418
  let newKey = match &orig.type_param {
416
419
  Some(t) => format!("{}.{}", t, name),
@@ -463,6 +466,23 @@ impl<'h> Ctx<'h> {
463
466
  }
464
467
  }
465
468
 
469
+ /// Does spec `sid` use a global (not its own binder or capture) that `callee` binds?
470
+ fn captured(&self, callee: &Fn, sid: usize) -> bool {
471
+ let mut bound: HashSet<String> = callee.params.iter().map(|p| p.name.clone()).collect();
472
+ collectBinders(&mut callee.body.clone(), &mut bound);
473
+ let spec = &self.specs[sid];
474
+ match &spec.kind {
475
+ Kind::Name(g) => bound.contains(g),
476
+ Kind::Lit(cl) => {
477
+ let mut own: HashSet<String> = cl.params.iter().cloned().collect();
478
+ collectBinders(&mut FnBody::Block(cl.body.clone()), &mut own);
479
+ own.extend(spec.caps.iter().cloned());
480
+ bound.retain(|n| !own.contains(n));
481
+ crate::simplify::mentions(&cl.body, &bound)
482
+ }
483
+ }
484
+ }
485
+
466
486
  fn buildCopy(&mut self, orig: Fn, name: String, j: usize, sid: usize) -> Option<Fn> {
467
487
  let spec = self.specs[sid].clone();
468
488
  let mut f = orig;
compiler/core/src/ctors.rs CHANGED
@@ -20,6 +20,12 @@ fn local(field: &str) -> String {
20
20
  format!("__f_{}", field)
21
21
  }
22
22
 
23
+ /// The generated constructor's parameter for a field. Named apart from the field: an init's
24
+ /// free call or global read must not resolve to a parameter the init never saw.
25
+ fn ctorParam(field: &str) -> String {
26
+ format!("__p_{}", field)
27
+ }
28
+
23
29
  struct Plan {
24
30
  params: Vec<(String, Type)>,
25
31
  }
@@ -339,7 +345,7 @@ pub fn lowerCtors(source: &mut Source) -> Vec<String> {
339
345
  ctor.push(Stmt::Assign(Assign {
340
346
  isSynthetic: false,
341
347
  targets: vec![AssignTarget::Var(local(p))],
342
- values: vec![Expr::Var(p.clone())],
348
+ values: vec![Expr::Var(ctorParam(p))],
343
349
  declare: true,
344
350
  ty: Some(t.clone()),
345
351
  }));
@@ -460,6 +466,7 @@ pub fn lowerCtors(source: &mut Source) -> Vec<String> {
460
466
  line: line,
461
467
  column: column,
462
468
  tail: TailKind::NotTail,
469
+ unique: false,
463
470
  }),
464
471
  })),
465
472
  0,
@@ -500,7 +507,7 @@ pub fn lowerCtors(source: &mut Source) -> Vec<String> {
500
507
  params: nparams
501
508
  .iter()
502
509
  .map(|(n, t)| Param {
503
- name: n.clone(),
510
+ name: ctorParam(n),
504
511
  ty: paramType(t),
505
512
  default: None,
506
513
  })
@@ -577,6 +584,7 @@ fn rewriteCall(e: &mut Expr, plans: &HashMap<String, Plan>, errors: &mut Vec<Str
577
584
  line: 0,
578
585
  column: 0,
579
586
  tail: TailKind::NotTail,
587
+ unique: false,
580
588
  })
581
589
  .at(e);
582
590
  }
compiler/core/src/drive.rs CHANGED
@@ -11,7 +11,7 @@
11
11
  use crate::ast::*;
12
12
  use crate::generics::Scope;
13
13
  use crate::rename::{renameStmts, substPT, substStmts, substType, Name};
14
- use crate::simplify::{pinExpr, simplifyBlock};
14
+ use crate::simplify::{boundNames, calledNames, mentions, pinExpr, simplifyBlock, simplifyBlockIn};
15
15
  use crate::visit::{argRef, isTag, walkBlockRef, walkRef};
16
16
  use crate::visit::{childRefs, stmtBlockRefs, stmtBlocks, stmtExprRefs, visitBlock, visitExpr};
17
17
  use crate::whistle::embeds;
@@ -63,6 +63,8 @@ struct Driver {
63
63
  snap: Source,
64
64
  fns: HashMap<String, Fn>,
65
65
  free: HashSet<String>,
66
+ /// names the fn being driven binds: a call of one is not a call of the free fn of that name
67
+ bound: HashSet<String>,
66
68
  methods: HashMap<String, Vec<String>>,
67
69
  enumGens: HashMap<String, Vec<String>>,
68
70
  /// every generic type (enum, struct, primitive) -> its generics, for fn scopes
@@ -342,6 +344,7 @@ impl Tcx {
342
344
  line: 0,
343
345
  column: 0,
344
346
  tail: TailKind::NotTail,
347
+ unique: false,
345
348
  }),
346
349
  }))
347
350
  } else if let Some(t) = &self.callee.type_param {
@@ -353,6 +356,7 @@ impl Tcx {
353
356
  line: 0,
354
357
  column: 0,
355
358
  tail: TailKind::NotTail,
359
+ unique: false,
356
360
  }),
357
361
  }))
358
362
  } else {
@@ -362,6 +366,7 @@ impl Tcx {
362
366
  line: 0,
363
367
  column: 0,
364
368
  tail: TailKind::NotTail,
369
+ unique: false,
365
370
  })
366
371
  }
367
372
  }
@@ -459,6 +464,7 @@ impl Driver {
459
464
  snap: src.clone(),
460
465
  fns: HashMap::new(),
461
466
  free: HashSet::new(),
467
+ bound: HashSet::new(),
462
468
  methods: HashMap::new(),
463
469
  enumGens: HashMap::new(),
464
470
  owners: crate::generics::ownerGenerics(src),
@@ -554,6 +560,7 @@ impl Driver {
554
560
  continue;
555
561
  }
556
562
  let mut body = f.body.clone();
563
+ self.bound = boundNames(&f.params, &f.body);
557
564
  self.vtypes = self.varTypes(f);
558
565
  self.scope = self.scopeOf(f);
559
566
  self.cur.clear();
@@ -569,6 +576,7 @@ impl Driver {
569
576
  let mut i = 0;
570
577
  while i < self.fused.len() {
571
578
  let mut body = self.fused[i].body.clone();
579
+ self.bound = boundNames(&self.fused[i].params, &body);
572
580
  self.vtypes = self.varTypes(&self.fused[i]);
573
581
  self.scope = self.scopeOf(&self.fused[i].clone());
574
582
  self.cur = self.origins.get(&self.fused[i].name).cloned().unwrap_or_default();
@@ -741,7 +749,7 @@ impl Driver {
741
749
 
742
750
  fn calls(&self, e: &Expr) -> Vec<Call> {
743
751
  match &e.kind {
744
- ExprKind::FnCall(c) if self.free.contains(&c.name) => {
752
+ ExprKind::FnCall(c) if self.free.contains(&c.name) && !self.bound.contains(&c.name) => {
745
753
  let f = &self.fns[&c.name];
746
754
  match positional(&c.args) {
747
755
  Some(args) if args.len() == f.params.len() && !f.has_self => {
@@ -869,9 +877,8 @@ impl Driver {
869
877
  ExprKind::Closure(_) => return true,
870
878
  ExprKind::Question(_) | ExprKind::Bang(_) | ExprKind::Bind(_) => return false,
871
879
  ExprKind::FnCall(c) => {
872
- let ok = self.pure.contains(&c.name)
880
+ let ok = !self.bound.contains(&c.name)
873
- || self.ctors.contains(&c.name)
874
- || CASTS.contains(&c.name.as_str());
881
+ && (self.pure.contains(&c.name) || self.ctors.contains(&c.name) || CASTS.contains(&c.name.as_str()));
875
882
  if !ok {
876
883
  return false;
877
884
  }
@@ -1086,6 +1093,7 @@ impl Driver {
1086
1093
  line: 0,
1087
1094
  column: 0,
1088
1095
  tail: TailKind::NotTail,
1096
+ unique: false,
1089
1097
  });
1090
1098
  return true;
1091
1099
  }
@@ -1178,6 +1186,11 @@ impl Driver {
1178
1186
  }
1179
1187
  self.fresh += 1;
1180
1188
  let (names, body) = self.renamed(&c.f, &format!("$k{}", self.fresh))?;
1189
+ if mentions(&body, &self.bound) {
1190
+ self.note(format!("not specialised: {}: a local here shadows a name its body uses", c.key));
1191
+ return None;
1192
+ }
1193
+ let called = calledNames(&body);
1181
1194
  let Some(Stmt { kind: StmtKind::Match(m), .. }) = body.stmts.first().cloned() else { return None };
1182
1195
  // An arm may read the matched value again once (`_ => .. effect.tint(alpha)`):
1183
1196
  // the value is then built in that arm instead, so it is still built at most once.
@@ -1205,7 +1218,7 @@ impl Driver {
1205
1218
  continue;
1206
1219
  }
1207
1220
  let trivial = matches!(&a.kind, ExprKind::Var(_) | ExprKind::Int(_) | ExprKind::Float(_) | ExprKind::BoolLit(_) | ExprKind::TypeName(_));
1208
- if trivial && !rebinds(&body.stmts, n) {
1221
+ if trivial && !rebinds(&body.stmts, n) && !called.contains(n) {
1209
1222
  subst.insert(n.clone(), copyOf(a));
1210
1223
  } else {
1211
1224
  pre.push(Stmt::Assign(Assign {
@@ -1229,7 +1242,7 @@ impl Driver {
1229
1242
  });
1230
1243
  pre.extend(blk.stmts);
1231
1244
  let mut out = Block { stmts: pre };
1232
- out = simplifyBlock(out, &self.snap, &self.pure);
1245
+ out = simplifyBlockIn(out, &self.snap, &self.pure, &self.bound);
1233
1246
  let stuck = out.stmts.iter().any(|s| match &s.kind {
1234
1247
  StmtKind::Match(m) => m.subjects.len() == 1 && self.ctorType(&m.subjects[0]).is_some(),
1235
1248
  _ => false,
@@ -1349,6 +1362,14 @@ impl Driver {
1349
1362
  return Err("argument count".to_string().into());
1350
1363
  }
1351
1364
  let (names, rb) = self.renamed(&c.f, "$u").ok_or("extern consumer")?;
1365
+ if mentions(&rb, &self.bound) {
1366
+ return Err(format!("a local here shadows a name wrapper {} uses", c.key).into());
1367
+ }
1368
+ // an argument replaces reads of its parameter; a call by that name has no read to replace
1369
+ let called = calledNames(&rb);
1370
+ if names.iter().any(|n| called.contains(n)) {
1371
+ return Err(format!("wrapper {} calls a parameter", c.key).into());
1372
+ }
1352
1373
  let mut stmts = rb.stmts;
1353
1374
  let Some(Stmt { kind: StmtKind::Expr(mut body, ..), .. }) = stmts.pop() else { return Err("wrapper body".into()) };
1354
1375
  for (n, a) in names.iter().zip(&c.args) {
@@ -1487,6 +1508,14 @@ impl Driver {
1487
1508
  n.push_str(suf);
1488
1509
  }
1489
1510
  });
1511
+ // a call by a bound name is a closure call: it follows its binder
1512
+ visitBlock(&mut body, &mut |e| {
1513
+ if let ExprKind::FnCall(c) = &mut e.kind {
1514
+ if bound.contains(&c.name) {
1515
+ c.name.push_str(suf);
1516
+ }
1517
+ }
1518
+ });
1490
1519
  Some((params.into_iter().map(|p| format!("{p}{suf}")).collect(), body))
1491
1520
  }
1492
1521
 
@@ -1854,6 +1883,7 @@ impl Driver {
1854
1883
  line: 0,
1855
1884
  column: 0,
1856
1885
  tail: TailKind::NotTail,
1886
+ unique: false,
1857
1887
  }));
1858
1888
  self.origins.insert(name.clone(), anc);
1859
1889
  self.fused.push(f);
@@ -2031,10 +2061,11 @@ impl Driver {
2031
2061
  }
2032
2062
  walkBlockRef(&Block { stmts: stmts.to_vec() }, &mut |e| match &e.kind {
2033
2063
  ExprKind::FnCall(c) => {
2034
- let known = self.ctors.contains(&c.name)
2064
+ let known = !self.bound.contains(&c.name)
2065
+ && (self.ctors.contains(&c.name)
2035
- || CASTS.contains(&c.name.as_str())
2066
+ || CASTS.contains(&c.name.as_str())
2036
- || self.pure.contains(&c.name)
2067
+ || self.pure.contains(&c.name)
2037
- || self.readOnly.contains(&c.name);
2068
+ || self.readOnly.contains(&c.name));
2038
2069
  if !known && !takesP(&c.args) {
2039
2070
  ok = false;
2040
2071
  }
compiler/core/src/forms.rs CHANGED
@@ -131,6 +131,7 @@ fn method(obj: &str, name: &str, args: Vec<Expr>) -> Expr {
131
131
  line: 0,
132
132
  column: 0,
133
133
  tail: TailKind::NotTail,
134
+ unique: false,
134
135
  }),
135
136
  }))
136
137
  }
compiler/core/src/parser.rs CHANGED
@@ -1304,6 +1304,7 @@ impl<'a> AstParser<'a> {
1304
1304
  line: pos.row + 1,
1305
1305
  column: pos.column + 1,
1306
1306
  tail: TailKind::NotTail,
1307
+ unique: false,
1307
1308
  })
1308
1309
  }
1309
1310
  None => AttrKind::Field(member),
@@ -1336,6 +1337,7 @@ impl<'a> AstParser<'a> {
1336
1337
  line,
1337
1338
  column,
1338
1339
  tail: TailKind::NotTail,
1340
+ unique: false,
1339
1341
  }),
1340
1342
  }))
1341
1343
  };
@@ -1416,6 +1418,7 @@ impl<'a> AstParser<'a> {
1416
1418
  line: pos.row + 1,
1417
1419
  column: pos.column + 1,
1418
1420
  tail: TailKind::NotTail,
1421
+ unique: false,
1419
1422
  }
1420
1423
  }
1421
1424
 
@@ -1453,6 +1456,7 @@ impl<'a> AstParser<'a> {
1453
1456
  line: pos.row + 1,
1454
1457
  column: pos.column + 1,
1455
1458
  tail: TailKind::NotTail,
1459
+ unique: false,
1456
1460
  }))
1457
1461
  }
1458
1462
  _ => {
compiler/core/src/purity.rs CHANGED
@@ -3,7 +3,9 @@
3
3
  //! field of anything but a fresh local (a local only ever bound to a record
4
4
  //! construction), and every callee it can reach is pure. Closure literal bodies count
5
5
  //! towards the enclosing fn. Calls are resolved by name only; an unknown callee
6
+ //! (extern, closure value, or any name the fn binds itself: a local, parameter, closure
7
+ //! parameter or pattern binder never resolves to the free fn of its name) is impure.
6
- //! (extern, fn-typed param, closure value) is impure. A method call on `self`, on a
8
+ //! So is `x.f(..)` where `f` may be an fn-typed field. A method call on `self`, on a
7
9
  //! parameter of a named type (never rebound or shadowed) or on a field read of one
8
10
  //! resolves by that type (`io.clear(..)` is `Io.clear`, not `Slice.clear`): to the type's
9
11
  //! method and every override below it, the call being as pure as all of them together.
@@ -249,13 +251,26 @@ struct Receivers<'a> {
249
251
  fields: HashMap<&'a str, HashMap<&'a str, &'a str>>,
250
252
  /// `(Type, method)` -> the overrides such a call may run
251
253
  overrides: HashMap<(String, String), Vec<String>>,
254
+ /// names of the fn-typed fields of all types: `x.f(..)` may call that closure
255
+ fnFields: HashSet<&'a str>,
256
+ /// `Type.method` of every method: on such a receiver the method wins over a field
257
+ methods: HashSet<String>,
252
258
  }
253
259
 
254
260
  impl<'a> Receivers<'a> {
255
261
  fn new(src: &'a Source) -> Self {
256
262
  let mut fields: HashMap<&str, HashMap<&str, &str>> = HashMap::new();
263
+ let mut fnFields: HashSet<&str> = HashSet::new();
264
+ let mut methods: HashSet<String> = HashSet::new();
257
265
  for item in &src.items {
266
+ if let Item::Fn(Fn { type_param: Some(t), name, .. }) = item {
267
+ methods.insert(format!("{t}.{name}"));
268
+ }
258
269
  let Item::Enum(e) = item else { continue };
270
+ for v in &e.variants {
271
+ let named = v.field_names.iter().zip(&v.fields);
272
+ fnFields.extend(named.filter(|(_, t)| t.asFn().is_some()).map(|(n, _)| n.as_str()));
273
+ }
259
274
  let [v] = &e.variants[..] else { continue };
260
275
  if !e.isStruct() || v.field_names.len() != v.fields.len() {
261
276
  continue;
@@ -263,7 +278,7 @@ impl<'a> Receivers<'a> {
263
278
  let known = v.field_names.iter().zip(&v.fields).filter(|(_, t)| !e.generics.iter().any(|g| g.name == t.name));
264
279
  fields.insert(e.name.as_str(), known.map(|(n, t)| (n.as_str(), t.name.as_str())).collect());
265
280
  }
266
- Receivers { fields, overrides: crate::subtyping::overrideTargets(src) }
281
+ Receivers { fields, overrides: crate::subtyping::overrideTargets(src), fnFields, methods }
267
282
  }
268
283
  }
269
284
 
@@ -274,6 +289,7 @@ fn analyse(f: &Fn, ctors: &HashSet<&str>, receivers: &Receivers) -> Info {
274
289
  calls: Vec::new(),
275
290
  ctors,
276
291
  params: f.params.iter().map(|p| p.name.as_str()).collect(),
292
+ bound: crate::simplify::boundNames(&f.params, &f.body),
277
293
  fresh: HashSet::new(),
278
294
  typed: HashMap::new(),
279
295
  receivers,
@@ -309,6 +325,8 @@ struct Walker<'a> {
309
325
  calls: Vec<Call>,
310
326
  ctors: &'a HashSet<&'a str>,
311
327
  params: HashSet<&'a str>,
328
+ /// Every name the fn binds: a call of one is a closure call, not the free fn of its name.
329
+ bound: HashSet<String>,
312
330
  /// Locals only ever bound to a record construction.
313
331
  fresh: HashSet<String>,
314
332
  /// receivers whose type is known (`self`, typed parameters never rebound) -> type name
@@ -328,12 +346,19 @@ impl<'a> Walker<'a> {
328
346
  });
329
347
  }
330
348
 
331
- /// Collect locals every one of whose bindings is a `ClassCall`, anywhere in the body.
349
+ /// Collect locals every one of whose bindings is a `ClassCall`, anywhere in the body. A
350
+ /// pattern binder, loop binder or closure parameter of that name is a binding that is not.
332
351
  fn findFresh(&mut self, b: &Block) {
352
+ let mut built: HashMap<String, usize> = HashMap::new();
353
+ scanAssigns(b, &mut built);
333
- let mut good: HashMap<String, bool> = HashMap::new();
354
+ let mut binds: HashMap<String, usize> = HashMap::new();
355
+ crate::rename::renameStmts(&mut b.stmts.clone(), &mut |n, kind| {
356
+ if !matches!(kind, crate::rename::Name::Ref) {
334
- scanAssigns(b, &mut good);
357
+ *binds.entry(n.clone()).or_default() += 1;
358
+ }
359
+ });
335
- for (n, ok) in good {
360
+ for (n, count) in built {
336
- if ok && !self.params.contains(n.as_str()) {
361
+ if binds.get(&n) == Some(&count) && !self.params.contains(n.as_str()) {
337
362
  self.fresh.insert(n);
338
363
  }
339
364
  }
@@ -463,8 +488,8 @@ impl<'a> Walker<'a> {
463
488
  }
464
489
  ExprKind::FnCall(c) => {
465
490
  self.args(&c.args);
466
- if self.params.contains(c.name.as_str()) {
491
+ if self.bound.contains(&c.name) {
467
- self.impure = true; // fn-typed param: unknown callee
492
+ self.impure = true; // a local value: unknown callee
468
493
  self.mutates = true;
469
494
  } else if self.ctors.contains(c.name.as_str()) {
470
495
  } else if CASTS.contains(&c.name.as_str()) && c.args.len() == 1 {
@@ -489,6 +514,14 @@ impl<'a> Walker<'a> {
489
514
  // `Color.White.withAlpha(..)`: a method on a constant, not a static call
490
515
  ExprKind::TypeName(t) if !t.contains('.') => self.calls.push(Call::Static(format!("{}.{}", t, c.name))),
491
516
  _ => match self.receiverType(&a.object).map(str::to_string) {
517
+ // `x.f(..)` where no method of the receiver's type wins over an
518
+ // fn-typed field `f`: a closure call
519
+ t if self.receivers.fnFields.contains(c.name.as_str())
520
+ && !t.as_ref().is_some_and(|t| self.receivers.methods.contains(&format!("{}.{}", t, c.name))) =>
521
+ {
522
+ self.impure = true;
523
+ self.mutates = true;
524
+ }
492
525
  Some(t) => {
493
526
  let below = self.receivers.overrides.get(&(t.clone(), c.name.clone()));
494
527
  let keys = below.into_iter().flatten().cloned();
@@ -523,37 +556,31 @@ impl<'a> Walker<'a> {
523
556
  }
524
557
  }
525
558
 
526
- /// For every `Var` assignment target in `b` (nested blocks and closures not
559
+ /// Counts, for every `Var` assignment target in `b` (nested blocks entered, closures not), the
527
- /// entered by name scoping: a name bound in two scopes must satisfy both), record
560
+ /// assignments of a record construction. Scopes are not told apart: a name bound in two
528
- /// whether all its values are record constructions.
561
+ /// scopes must satisfy both.
529
- fn scanAssigns(b: &Block, good: &mut HashMap<String, bool>) {
562
+ fn scanAssigns(b: &Block, built: &mut HashMap<String, usize>) {
530
563
  for s in &b.stmts {
531
564
  match &s.kind {
532
565
  StmtKind::Assign(a) => {
533
566
  for (i, t) in a.targets.iter().enumerate() {
534
567
  if let AssignTarget::Var(n) = t {
535
- let isCtor = a.targets.len() == a.values.len()
536
- && matches!(a.values[i].kind, ExprKind::ClassCall(_));
568
+ if a.targets.len() == a.values.len() && matches!(a.values[i].kind, ExprKind::ClassCall(_)) {
537
- let e = good.entry(n.clone()).or_insert(true);
569
+ *built.entry(n.clone()).or_default() += 1;
538
- *e = *e && isCtor;
570
+ }
539
571
  }
540
572
  }
541
573
  }
542
- StmtKind::ForLoop(l) => {
543
- for n in &l.binders {
544
- good.insert(n.clone(), false);
545
- }
546
- scanAssigns(&l.body, good);
574
+ StmtKind::ForLoop(l) => scanAssigns(&l.body, built),
547
- }
548
- StmtKind::While(w) => scanAssigns(&w.body, good),
575
+ StmtKind::While(w) => scanAssigns(&w.body, built),
549
576
  StmtKind::If(i) => {
550
- scanAssigns(&i.body, good);
577
+ scanAssigns(&i.body, built);
551
- i.else_ifs.iter().for_each(|e| scanAssigns(&e.body, good));
578
+ i.else_ifs.iter().for_each(|e| scanAssigns(&e.body, built));
552
579
  if let Some(b) = &i.else_ {
553
- scanAssigns(b, good);
580
+ scanAssigns(b, built);
554
581
  }
555
582
  }
556
- StmtKind::Match(m) => m.cases.iter().for_each(|c| scanAssigns(&c.body, good)),
583
+ StmtKind::Match(m) => m.cases.iter().for_each(|c| scanAssigns(&c.body, built)),
557
584
  _ => {}
558
585
  }
559
586
  }
compiler/core/src/reuse.rs CHANGED
@@ -5,15 +5,17 @@
5
5
  //! instead of allocating. Everything unclear stays an allocation. The proof:
6
6
  //!
7
7
  //! * `f` is a free, non-exported, uniquely named fn, never used as a value or a method name,
8
- //! with no closures and no loops; `xs` is a plain parameter without default whose only
8
+ //! with no closures and no loops; `xs` is a plain parameter without default, never rebound
9
- //! use in `f` is as the subject of the `match` that is `f`'s last statement.
9
+ //! or shadowed, whose only use in `f` is as the subject of the `match` that is `f`'s last
10
+ //! statement.
10
11
  //! * Every call of `f` passes, for `xs`, a deeply fresh value (a constructor tree of scalars and
11
- //! field-less variants, no spread) or a pattern binder of that match used exactly once
12
+ //! field-less variants, no spread) or a pattern binder of that match used exactly once and
12
- //! (the recursive tail, owned by the dead `xs`).
13
+ //! bound nowhere else in `f` (the recursive tail, owned by the dead `xs`).
13
14
  //! * The arm has one `Ctor(..)` pattern with binders, no guard, and ends in a
14
15
  //! `Ctor(..)` constructor of the same name without spread.
15
16
  use crate::ast::*;
16
17
  use crate::forms::{mapExprs, walkStmts};
18
+ use crate::rename::{renameStmts, Name};
17
19
  use std::collections::HashMap;
18
20
 
19
21
  fn deepFresh(e: &Expr) -> bool {
@@ -42,6 +44,26 @@ fn argFor<'a>(call: &'a FnCall, idx: usize, name: &str) -> Option<&'a Expr> {
42
44
  None
43
45
  }
44
46
 
47
+ /// How many times each name is bound in `f`: parameters, locals (`x = v` included), loop
48
+ /// binders, closure parameters and pattern names.
49
+ fn bindCounts(f: &Fn) -> HashMap<String, usize> {
50
+ let mut out: HashMap<String, usize> = HashMap::new();
51
+ for p in &f.params {
52
+ *out.entry(p.name.clone()).or_default() += 1;
53
+ }
54
+ let mut note = |n: &mut String, kind: Name| {
55
+ if kind != Name::Ref {
56
+ *out.entry(n.clone()).or_default() += 1;
57
+ }
58
+ };
59
+ match &f.body {
60
+ FnBody::Block(b) => renameStmts(&mut b.stmts.clone(), &mut note),
61
+ FnBody::Expr(e) => renameStmts(&mut [Stmt::Expr(e.clone(), 0, 0)], &mut note),
62
+ FnBody::Extern => {}
63
+ }
64
+ out
65
+ }
66
+
45
67
  struct Cand {
46
68
  item: usize,
47
69
  param: usize,
@@ -73,7 +95,7 @@ pub fn markReuse(src: &mut Source) -> Vec<String> {
73
95
  if !matches!(p.ty, ParamType::Type(_)) || p.default.is_some() {
74
96
  continue;
75
97
  }
76
- if crate::visit::countVar(&f.body, v) != 1 {
98
+ if crate::visit::countVar(&f.body, v) != 1 || bindCounts(f).get(v) != Some(&1) {
77
99
  continue;
78
100
  }
79
101
  let mut bad = false;
@@ -107,6 +129,8 @@ pub fn markReuse(src: &mut Source) -> Vec<String> {
107
129
  crate::visit::patternBinders(p, &mut inner);
108
130
  }
109
131
  }
132
+ let binds = bindCounts(f);
133
+ inner.retain(|t| binds.get(t) == Some(&1));
110
134
  for (idx, it) in src.items.iter().enumerate() {
111
135
  let mut body = match it {
112
136
  Item::Fn(g) => g.body.clone(),
compiler/core/src/simplify.rs CHANGED
@@ -25,11 +25,66 @@ fn fresh() -> usize {
25
25
  }
26
26
 
27
27
  pub fn simplifyExpr(e: Expr, src: &Source, pure: &HashSet<String>) -> Expr {
28
+ let mut cx = Cx::new(src, pure);
29
+ cx.bound = boundNames(&[], &FnBody::Expr(e.clone()));
28
- Cx::new(src, pure).simExpr(e, None)
30
+ cx.simExpr(e, None)
29
31
  }
30
32
 
31
33
  pub fn simplifyBlock(b: Block, src: &Source, pure: &HashSet<String>) -> Block {
34
+ simplifyBlockIn(b, src, pure, &HashSet::new())
35
+ }
36
+
37
+ /// `simplifyBlock` for a block that will sit in a scope binding `outer`.
38
+ pub fn simplifyBlockIn(b: Block, src: &Source, pure: &HashSet<String>, outer: &HashSet<String>) -> Block {
39
+ let mut cx = Cx::new(src, pure);
40
+ cx.bound = boundNames(&[], &FnBody::Block(b.clone()));
41
+ cx.bound.extend(outer.iter().cloned());
32
- Cx::new(src, pure).simBlock(b)
42
+ cx.simBlock(b)
43
+ }
44
+
45
+ /// Every name a fn with these parameters and this body binds: parameters, locals, loop and
46
+ /// closure parameters, pattern names. Such a name may shadow the free fn of that name, so a
47
+ /// call of it in that fn is not a call of the free fn.
48
+ pub fn boundNames(params: &[Param], body: &FnBody) -> HashSet<String> {
49
+ let mut out: HashSet<String> = params.iter().map(|p| p.name.clone()).collect();
50
+ let mut note = |n: &mut String, kind: Name| match kind {
51
+ Name::Decl => {
52
+ out.insert(n.clone());
53
+ }
54
+ Name::Pat if !isTag(n) => {
55
+ out.insert(n.clone());
56
+ }
57
+ _ => {}
58
+ };
59
+ match body {
60
+ FnBody::Block(b) => renameStmts(&mut b.stmts.clone(), &mut note),
61
+ FnBody::Expr(e) => renameStmts(&mut [Stmt::Expr(e.clone(), 0, 0)], &mut note),
62
+ FnBody::Extern => {}
63
+ }
64
+ out
65
+ }
66
+
67
+ /// Does `b` call or read a name in `names`? Run on a body whose own binders are renamed, what
68
+ /// is left is global: moved under a binder of that name, it would resolve to the binder.
69
+ pub fn mentions(b: &Block, names: &HashSet<String>) -> bool {
70
+ let mut hit = false;
71
+ walkBlockRef(b, &mut |e| match &e.kind {
72
+ ExprKind::FnCall(c) if names.contains(&c.name) => hit = true,
73
+ ExprKind::Var(n) if names.contains(n) => hit = true,
74
+ _ => {}
75
+ });
76
+ hit
77
+ }
78
+
79
+ /// The names `b` calls.
80
+ pub fn calledNames(b: &Block) -> HashSet<String> {
81
+ let mut out = HashSet::new();
82
+ walkBlockRef(b, &mut |e| {
83
+ if let ExprKind::FnCall(c) = &e.kind {
84
+ out.insert(c.name.clone());
85
+ }
86
+ });
87
+ out
33
88
  }
34
89
 
35
90
  /// `e`, a value of type `t` moved out of the fn that typed it, with its tail constructors
@@ -51,6 +106,7 @@ pub fn simplify(src: &mut Source, pure: &HashSet<String>) -> Vec<String> {
51
106
  continue;
52
107
  }
53
108
  cx.scope = Scope::in_(&cx.owners, f);
109
+ cx.bound = boundNames(&f.params, &f.body);
54
110
  let before = f.body.clone();
55
111
  let block = match std::mem::replace(&mut f.body, FnBody::Extern) {
56
112
  FnBody::Block(b) => b,
@@ -93,6 +149,8 @@ struct Cx<'a> {
93
149
  /// generic names in scope in the fn being simplified
94
150
  scope: Scope,
95
151
  owners: HashMap<String, Vec<String>>,
152
+ /// names the fn being simplified binds: see `boundNames`
153
+ bound: HashSet<String>,
96
154
  }
97
155
 
98
156
  fn trivial(e: &Expr) -> bool {
@@ -212,7 +270,7 @@ impl<'a> Cx<'a> {
212
270
  }
213
271
  }
214
272
  }
215
- Cx { pure, fns, recursive, ctors, variants, stack: vec![], depth: 0, scope: Scope::default(), owners: crate::generics::ownerGenerics(src) }
273
+ Cx { pure, fns, recursive, ctors, variants, stack: vec![], depth: 0, scope: Scope::default(), owners: crate::generics::ownerGenerics(src), bound: HashSet::new() }
216
274
  }
217
275
 
218
276
  fn isPure(&self, e: &Expr) -> bool {
@@ -221,7 +279,7 @@ impl<'a> Cx<'a> {
221
279
  | ExprKind::Self_ | ExprKind::Closure(_) => true,
222
280
  ExprKind::Binary(b) => !matches!(b.op, BinOp::Div | BinOp::Mod) && self.isPure(&b.left) && self.isPure(&b.right),
223
281
  ExprKind::Question(_) | ExprKind::Bang(_) | ExprKind::Bind(_) => false,
224
- ExprKind::FnCall(c) => self.pure.contains(&c.name) && c.args.iter().all(|a| self.isPure(argRef(a))),
282
+ ExprKind::FnCall(c) => !self.bound.contains(&c.name) && self.pure.contains(&c.name) && c.args.iter().all(|a| self.isPure(argRef(a))),
225
283
  ExprKind::Attribute(a) => match &a.attr {
226
284
  AttrKind::Field(_) => self.isPure(&a.object),
227
285
  AttrKind::Method(_) => false,
@@ -231,6 +289,9 @@ impl<'a> Cx<'a> {
231
289
  }
232
290
 
233
291
  fn eligible(&self, name: &str) -> Option<&Fn> {
292
+ if self.bound.contains(name) {
293
+ return None;
294
+ }
234
295
  let f = self.fns.get(name)?;
235
296
  let ok = self.pure.contains(name)
236
297
  && !self.recursive.contains(name)
@@ -489,13 +550,17 @@ impl<'a> Cx<'a> {
489
550
  .map(|b| (b.clone(), format!("{}__s{}", b, k)))
490
551
  .collect();
491
552
  Scoper { scopes: vec![initial], k }.stmts(&mut body.stmts);
553
+ if mentions(&body, &self.bound) {
554
+ return None;
555
+ }
556
+ let called = calledNames(&body);
492
557
  let mut subst: HashMap<String, Expr> = HashMap::new();
493
558
  let mut binds = Vec::new();
494
559
  let mut nontrivial = 0;
495
560
  for (i, a) in argv {
496
561
  let p = &f.params[i].name;
497
562
  let fr = map[p].clone();
498
- if trivial(&a) && !assigned.contains(p) && !declared.contains(p) {
563
+ if trivial(&a) && !assigned.contains(p) && !declared.contains(p) && !called.contains(&fr) {
499
564
  subst.insert(fr, a);
500
565
  } else if allowLets {
501
566
  binds.push(Stmt::Assign(Assign {
@@ -507,7 +572,7 @@ impl<'a> Cx<'a> {
507
572
  }));
508
573
  } else {
509
574
  let StmtKind::Expr(be, ..) = &body.stmts.first()?.kind else { return None };
510
- if body.stmts.len() != 1 || assigned.contains(p) || declared.contains(p) {
575
+ if body.stmts.len() != 1 || assigned.contains(p) || declared.contains(p) || called.contains(&fr) {
511
576
  return None;
512
577
  }
513
578
  let mut acc = (0, 0);
@@ -735,11 +800,12 @@ impl<'a> Cx<'a> {
735
800
  .map(|b| (b.clone(), format!("{}__s{}", b, k)))
736
801
  .collect();
737
802
  Scoper { scopes: vec![initial], k }.stmts(&mut body.stmts);
803
+ let called = calledNames(&body);
738
804
  let mut out = Vec::new();
739
805
  let mut subst: HashMap<String, Expr> = HashMap::new();
740
806
  for (i, (n, v)) in binds.into_iter().enumerate() {
741
807
  let target = match n {
742
- Some(n) if trivial(&v) && !assigned.contains(&n) && !declared.contains(&n) => {
808
+ Some(n) if trivial(&v) && !assigned.contains(&n) && !declared.contains(&n) && !called.contains(&map[&n]) => {
743
809
  subst.insert(map[&n].clone(), v);
744
810
  continue;
745
811
  }
@@ -850,7 +916,11 @@ impl Scoper {
850
916
  self.expr(obj);
851
917
  }
852
918
  }
919
+ // `k := |n| .. k(n - 1) ..`: inside the literal the name is the closure itself
920
+ let selfRef = a.declare && matches!(&a.values[..], [Expr { kind: ExprKind::Closure(_), .. }]);
921
+ if !selfRef {
853
- a.values.iter_mut().for_each(|v| self.expr(v));
922
+ a.values.iter_mut().for_each(|v| self.expr(v));
923
+ }
854
924
  let decl = a.declare;
855
925
  for t in &mut a.targets {
856
926
  if let AssignTarget::Var(n) = t {
@@ -861,6 +931,9 @@ impl Scoper {
861
931
  }
862
932
  }
863
933
  }
934
+ if selfRef {
935
+ a.values.iter_mut().for_each(|v| self.expr(v));
936
+ }
864
937
  }
865
938
  StmtKind::ForLoop(f) => {
866
939
  self.expr(&mut f.source);
@@ -893,6 +966,10 @@ impl Scoper {
893
966
  }
894
967
 
895
968
  fn expr(&mut self, e: &mut Expr) {
969
+ // a call by a bound name is a closure call: it follows its binder
970
+ if let ExprKind::FnCall(c) = &mut e.kind {
971
+ self.lookup(&mut c.name);
972
+ }
896
973
  match &mut e.kind {
897
974
  ExprKind::Var(n) => self.lookup(n),
898
975
  ExprKind::Bind(b) => {
compiler/core/src/trmc.rs CHANGED
@@ -23,7 +23,7 @@
23
23
  //! variant and a nullary variant, with exactly one recursive field; fields after
24
24
  //! the recursive one must be plain variables or literals. Nothing under
25
25
  //! `?`/`!` or closures, no other `return`s outside tail
26
- //! position.
26
+ //! position. No binder named like the fn: its call would not be a self call.
27
27
  use crate::ast::*;
28
28
  use crate::generics::Scope;
29
29
  use crate::rename::substType;
@@ -108,6 +108,9 @@ fn rewriteFn(f: &Fn, enums: &[Enum]) -> Option<Fn> {
108
108
  }) {
109
109
  return None;
110
110
  }
111
+ if !f.has_self && crate::simplify::boundNames(&f.params, &f.body).contains(&f.name) {
112
+ return None;
113
+ }
111
114
  let ret = f.returns.clone()?;
112
115
  let owner = enums.iter().find(|e| e.name == ret.name && !e.isStruct())?;
113
116
  let nullary = owner
compiler/core/src/uniqueness.rs CHANGED
@@ -6,13 +6,37 @@
6
6
  //! field read `v.f`, the spread itself in tail position / assigned straight back to
7
7
  //! `v`, or a hand-over `g(v)` (tail position or `v = g(v)`) to a unique parameter, and
8
8
  //! `v` is never captured by a closure, stored, aliased or matched into a binding.
9
+ //! * A *parameter* of a free fn or of a method (methods are resolved by name, to every method
10
+ //! of that name; a name that is also a fn-typed field or a local/parameter is not resolved)
9
- //! * A *parameter* of a free fn is unique when the fn is only ever called directly and
11
+ //! is unique when the fn is only ever called directly and
10
12
  //! every call site passes a unique value: a fresh expression, a unique local/param
11
13
  //! handed over as above, or `x.f` in `x.f = g(x.f)` when field `f` is itself unique.
12
14
  //! * A field `f` is unique when every write to it is fresh, every read of it is `x.f.h`,
13
15
  //! `x.f.h = ..` or the assign-back argument above, no pattern binds it, and no spread
14
16
  //! that is not itself proved copies it.
15
17
  //!
18
+ //! * A fn may also return one of its own parameters (`fun act(self, n) = ..; n`). Its result
19
+ //! then counts as fresh to a caller only when the argument handed in for that parameter is
20
+ //! itself fresh, or is the very variable the result is assigned back to (`v = g(v)`), and
21
+ //! the parameter is unique and never stored inside the callee. A callee reached with one
22
+ //! unique and one shared argument is not unique: there are no per-call-site copies, and
23
+ //! `--explain-fusion` says which call blocked it.
24
+ //!
25
+ //! * A method whose `self` is only read (`ro`: field reads, field writes, calls of other `ro`
26
+ //! methods; never returned, stored, passed on or captured) does not block a receiver. What
27
+ //! it returns of `self`'s fields is the field analysis' business, not the receiver's.
28
+ //!
29
+ //! * `Array.with` is a copy unless a call is marked `FnCall.unique` (the checker then runs
30
+ //! `Array.withUnique`, which writes `self`). A call is marked when its receiver is unshared
31
+ //! and dead afterwards: a fresh array (`Array.with`, `push`, `resize`, `init`, `filled` count
32
+ //! as fresh), a unique local or parameter the call consumes (`v = v.with(..)`, or the returned
33
+ //! value), a unique field rebuilt by `x.f = x.f.with(..)`, or `T(..s, f: s.f.with(..))` of a
34
+ //! proved `s`, provided no other field of the spread touches `s` except by plain reads of
35
+ //! other fields (a method call or closure on `s` could read `s.f` after the write).
36
+ //!
37
+ //! * Methods the compiler calls without a visible call site (`IMPLICIT`: interpolation, hashing,
38
+ //! operators) are never proved: their callers are unknown.
39
+ //!
16
40
  //! Parameters and fields are solved as a greatest fixpoint (assume unique, remove what
17
41
  //! fails, repeat).
18
42
  use crate::ast::*;
@@ -27,14 +51,14 @@ pub struct UniqueReport {
27
51
 
28
52
  // ---------- traversal ----------
29
53
 
30
- enum Node<'a> {
54
+ pub(crate) enum Node<'a> {
31
55
  E(&'a Expr),
32
56
  S(&'a Stmt),
33
57
  /// A method call: the id of its enclosing `Attribute` expression, and the call.
34
58
  M(NodeId, &'a FnCall),
35
59
  }
36
60
 
37
- type Visit<'a, 'b> = &'b mut dyn FnMut(Node<'a>) -> bool;
61
+ pub(crate) type Visit<'a, 'b> = &'b mut dyn FnMut(Node<'a>) -> bool;
38
62
 
39
63
  fn argExpr(a: &Arg) -> &Expr {
40
64
  match a {
@@ -43,13 +67,13 @@ fn argExpr(a: &Arg) -> &Expr {
43
67
  }
44
68
  }
45
69
 
46
- fn walkBlock<'a>(b: &'a Block, f: Visit<'a, '_>) {
70
+ pub(crate) fn walkBlock<'a>(b: &'a Block, f: Visit<'a, '_>) {
47
71
  for s in &b.stmts {
48
72
  walkStmt(s, f);
49
73
  }
50
74
  }
51
75
 
52
- fn walkStmt<'a>(s: &'a Stmt, f: Visit<'a, '_>) {
76
+ pub(crate) fn walkStmt<'a>(s: &'a Stmt, f: Visit<'a, '_>) {
53
77
  if !f(Node::S(s)) {
54
78
  return;
55
79
  }
@@ -100,7 +124,7 @@ fn walkStmt<'a>(s: &'a Stmt, f: Visit<'a, '_>) {
100
124
  }
101
125
  }
102
126
 
103
- fn walkExpr<'a>(e: &'a Expr, f: Visit<'a, '_>) {
127
+ pub(crate) fn walkExpr<'a>(e: &'a Expr, f: Visit<'a, '_>) {
104
128
  if !f(Node::E(e)) {
105
129
  return;
106
130
  }
@@ -172,13 +196,13 @@ fn walkExpr<'a>(e: &'a Expr, f: Visit<'a, '_>) {
172
196
  }
173
197
  }
174
198
 
175
- fn mutBlock(b: &mut Block, f: &mut dyn FnMut(&mut ClassCall)) {
199
+ pub(crate) fn mutBlock(b: &mut Block, f: &mut dyn FnMut(&mut Expr)) {
176
200
  for s in &mut b.stmts {
177
201
  mutStmt(s, f);
178
202
  }
179
203
  }
180
204
 
181
- fn mutStmt(s: &mut Stmt, f: &mut dyn FnMut(&mut ClassCall)) {
205
+ fn mutStmt(s: &mut Stmt, f: &mut dyn FnMut(&mut Expr)) {
182
206
  match &mut s.kind {
183
207
  StmtKind::Assign(a) => {
184
208
  for t in &mut a.targets {
@@ -226,7 +250,8 @@ fn mutStmt(s: &mut Stmt, f: &mut dyn FnMut(&mut ClassCall)) {
226
250
  }
227
251
  }
228
252
 
229
- fn mutExpr(e: &mut Expr, f: &mut dyn FnMut(&mut ClassCall)) {
253
+ pub(crate) fn mutExpr(e: &mut Expr, f: &mut dyn FnMut(&mut Expr)) {
254
+ f(e);
230
255
  match &mut e.kind {
231
256
  ExprKind::Binary(b) => {
232
257
  mutExpr(&mut b.left, f);
@@ -256,7 +281,6 @@ fn mutExpr(e: &mut Expr, f: &mut dyn FnMut(&mut ClassCall)) {
256
281
  }
257
282
  }
258
283
  ExprKind::ClassCall(c) => {
259
- f(c);
260
284
  if let Some(s) = &mut c.spread {
261
285
  mutExpr(s, f);
262
286
  }
@@ -337,9 +361,12 @@ struct Site {
337
361
  args: Vec<Option<Expr>>,
338
362
  assignBack: Option<AssignTarget>,
339
363
  inClosure: bool,
364
+ /// The call expression's id, and whether it is in tail position of its unit.
365
+ node: NodeId,
366
+ tail: bool,
340
367
  }
341
368
 
342
- fn isVar(e: &Expr, v: &str) -> bool {
369
+ pub(crate) fn isVar(e: &Expr, v: &str) -> bool {
343
370
  varName(e) == Some(v)
344
371
  }
345
372
 
@@ -353,8 +380,12 @@ fn varName(e: &Expr) -> Option<&str> {
353
380
  }
354
381
 
355
382
  /// Method names the compiler may call without a visible call site (interpolation,
356
- /// constructors, hashing): their `self` and parameters are never proved.
383
+ /// constructors, hashing, the operators `a + b`, `-a`, `a == b`, `a < b`): their `self` and
384
+ /// parameters are never proved.
385
+ const IMPLICIT: [&str; 16] = [
357
- const IMPLICIT: [&str; 6] = ["toStr", "init", "equals", "hash", "compare", "drop"];
386
+ "toStr", "init", "equals", "hash", "compare", "drop", "add", "sub", "mul", "div", "neg", "eq", "lt", "le", "gt",
387
+ "ge",
388
+ ];
358
389
 
359
390
  struct An {
360
391
  units: Vec<Unit>,
@@ -365,15 +396,38 @@ struct An {
365
396
  sites: Vec<Site>,
366
397
  escaped: HashSet<usize>,
367
398
  fresh_ret: RefCell<HashSet<usize>>,
399
+ /// Fns whose every result is fresh or one of their own parameters: the parameters they
400
+ /// may return (see the header).
401
+ passes: HashMap<usize, Vec<usize>>,
402
+ /// Field writes `o.f = g(..)` of a returning fn: the `(fn, parameter)` pairs that must stay
403
+ /// unique and unstored for field `f` to stay unique.
404
+ passWrites: Vec<(String, Vec<(usize, usize)>)>,
368
405
  up: RefCell<HashSet<(usize, usize)>>,
369
406
  upWhy: RefCell<HashMap<(usize, usize), String>>,
370
407
  uf: RefCell<HashSet<String>>,
371
- cache: RefCell<HashMap<(usize, String), Result<(), String>>>,
408
+ cache: RefCell<HashMap<(usize, String, bool, bool), Result<(), String>>>,
372
409
  // static field facts
373
410
  badField: HashSet<String>,
374
411
  patternBound: HashSet<String>,
375
412
  poisonAll: bool,
376
413
  spreads: Vec<SpreadSite>,
414
+ /// Methods whose `self` is only read: used as the object of field reads and field writes, or
415
+ /// as the receiver of other such methods, never returned, stored, passed on or captured.
416
+ ro: HashSet<usize>,
417
+ /// `Array.with` (the only unit a marked `with` call runs; its copying body is the default).
418
+ arrayWith: HashSet<usize>,
419
+ /// `Array` methods that always return a new array (or, marked, the unique receiver).
420
+ arrayFresh: HashSet<usize>,
421
+ /// `T(..s, f: s.f.with(..))`, by the id of the `with` call.
422
+ spreadWith: HashMap<NodeId, SpreadWith>,
423
+ }
424
+
425
+ struct SpreadWith {
426
+ unit: usize,
427
+ var: String,
428
+ field: String,
429
+ /// No other field value of the spread reads `s.f`, so the write cannot be observed early.
430
+ clean: bool,
377
431
  }
378
432
 
379
433
  struct SpreadSite {
@@ -381,9 +435,12 @@ struct SpreadSite {
381
435
  typeName: String,
382
436
  var: Option<String>,
383
437
  given: Vec<String>,
438
+ /// Given fields whose value is a call returning (one of) its own parameters, fed from the
439
+ /// source's own field: they alias the source's field unless the spread is proved.
440
+ passGiven: Vec<String>,
384
441
  }
385
442
 
386
- fn collectTails<'a>(b: &'a Block, out: &mut Vec<&'a Expr>) -> bool {
443
+ pub(crate) fn collectTails<'a>(b: &'a Block, out: &mut Vec<&'a Expr>) -> bool {
387
444
  match b.stmts.last() {
388
445
  Some(Stmt { kind: StmtKind::Expr(e, _, _), .. }) | Some(Stmt { kind: StmtKind::Return(Some(e)), .. }) => {
389
446
  out.push(e);
@@ -428,6 +485,103 @@ impl An {
428
485
  self.methodIdx.get(name).map(|v| v.as_slice()).unwrap_or(&[])
429
486
  }
430
487
 
488
+ /// The arguments of a call of `g`, one per parameter (`None` = defaulted or missing).
489
+ fn argsFor<'e>(&self, g: usize, recv: Option<&'e Expr>, args: &'e [Arg]) -> Vec<Option<&'e Expr>> {
490
+ let u = &self.units[g];
491
+ let mut out: Vec<Option<&Expr>> = vec![None; u.params.len()];
492
+ let mut pos = 0;
493
+ if u.hasSelf {
494
+ out[0] = recv;
495
+ pos = 1;
496
+ }
497
+ for arg in args {
498
+ match arg {
499
+ Arg::Positional(x) => {
500
+ if pos < out.len() {
501
+ out[pos] = Some(x);
502
+ }
503
+ pos += 1;
504
+ }
505
+ Arg::Keyword { name, value } => {
506
+ if let Some(j) = u.params.iter().position(|p| &p.name == name) {
507
+ out[j] = Some(value);
508
+ }
509
+ }
510
+ }
511
+ }
512
+ out
513
+ }
514
+
515
+ /// Every unit a call may run, with its arguments. `None` when the call is not a direct
516
+ /// call of known fns (a closure, a builtin, a static/instance mismatch).
517
+ fn callTargets<'e>(&self, e: &'e Expr) -> Option<Vec<(usize, Vec<Option<&'e Expr>>)>> {
518
+ match &e.kind {
519
+ ExprKind::FnCall(c) => {
520
+ let g = self.isFree(&c.name)?;
521
+ Some(vec![(g, self.argsFor(g, None, &c.args))])
522
+ }
523
+ ExprKind::Attribute(a) => {
524
+ let AttrKind::Method(c) = &a.attr else { return None };
525
+ let isType = matches!(a.object.kind, ExprKind::TypeName(_));
526
+ let cands = self.cands(&c.name);
527
+ if cands.is_empty() || cands.iter().any(|&g| self.units[g].hasSelf == isType) {
528
+ return None;
529
+ }
530
+ Some(cands.iter().map(|&g| (g, self.argsFor(g, Some(&a.object), &c.args))).collect())
531
+ }
532
+ _ => None,
533
+ }
534
+ }
535
+
536
+ /// The `(fn, parameter)` pairs a returned-parameter call depends on, when `e` is a call
537
+ /// of fns that return fresh values or their own parameters and every returned parameter
538
+ /// gets a fresh argument or (`same`) the argument `same` accepts. `None` otherwise.
539
+ fn passDeps(&self, e: &Expr, same: &dyn std::ops::Fn(&Expr) -> bool) -> Option<Vec<(usize, usize)>> {
540
+ let targets = self.callTargets(e)?;
541
+ let mut deps = vec![];
542
+ for (g, args) in targets {
543
+ match self.passes.get(&g) {
544
+ None => {
545
+ if !self.fresh_ret.borrow().contains(&g) {
546
+ return None;
547
+ }
548
+ }
549
+ Some(ps) => {
550
+ for &j in ps {
551
+ let arg = args.get(j).copied().flatten()?;
552
+ if !(self.fresh(arg) || same(arg)) {
553
+ return None;
554
+ }
555
+ deps.push((g, j));
556
+ }
557
+ }
558
+ }
559
+ }
560
+ Some(deps)
561
+ }
562
+
563
+ /// Is parameter `j` of `g` unique and never stored or aliased inside `g`? For the receiver of a
564
+ /// method, whose callers are found by name alone (a call `x.m()` counts as a call of every
565
+ /// `m`, whatever `x`'s type), only this call's own argument matters: it is fresh or the
566
+ /// variable being rebound. A shared `arr.with(..)` elsewhere must not stop `Map.with`, which
567
+ /// returns its receiver, from being a harmless pass-through here.
568
+ fn passParamOk(&self, g: usize, j: usize) -> bool {
569
+ let u = &self.units[g];
570
+ let receiver = u.method && u.hasSelf && j == 0;
571
+ if receiver {
572
+ u.params.get(j).is_some_and(|p| p.plain) && self.varOkCached(g, &u.params[j].name, true, true).is_ok()
573
+ } else {
574
+ self.paramUnique(g, j) && self.varOkMode(g, &u.params[j].name, true).is_ok()
575
+ }
576
+ }
577
+
578
+ /// May a unique value be handed to parameter `j` of `g`? Yes when every call of `g` passes a
579
+ /// unique value, or when `g` merely passes the parameter through (returns it, never stores
580
+ /// it): then this call's own unique argument is all that matters.
581
+ fn handOk(&self, g: usize, j: usize) -> bool {
582
+ self.paramUnique(g, j) || (self.passes.get(&g).is_some_and(|ps| ps.contains(&j)) && self.passParamOk(g, j))
583
+ }
584
+
431
585
  /// The parameter of method `g` that argument `k` of `c` binds (`None` = the receiver).
432
586
  fn methodParam(&self, g: usize, c: &FnCall, k: Option<usize>) -> Option<usize> {
433
587
  let u = &self.units[g];
@@ -446,6 +600,11 @@ impl An {
446
600
  }
447
601
 
448
602
  fn paramUnique(&self, g: usize, j: usize) -> bool {
603
+ // `Array.with` copies unless a call is marked, and a call is marked only by its own proof:
604
+ // its receiver is always acceptable, the index and the value (stored) never are.
605
+ if self.arrayWith.contains(&g) {
606
+ return j == 0;
607
+ }
449
608
  self.units[g].params.get(j).is_some() && self.up.borrow().contains(&(g, j))
450
609
  }
451
610
 
@@ -461,16 +620,28 @@ impl An {
461
620
 
462
621
  /// Is `v` (a local or parameter of `unit`) provably unshared at every spread of it?
463
622
  fn varOk(&self, unit: usize, v: &str) -> Result<(), String> {
623
+ self.varOkMode(unit, v, false)
624
+ }
625
+
626
+ /// `strict`: a binding of `v` must be a plainly fresh value (no returned-parameter
627
+ /// calls). The check of a callee's parameter runs strict, so checks never nest.
628
+ fn varOkMode(&self, unit: usize, v: &str, strict: bool) -> Result<(), String> {
629
+ self.varOkCached(unit, v, strict, false)
630
+ }
631
+
632
+ /// `entryUnique`: a parameter is taken to arrive unique (the caller under analysis passes a
633
+ /// unique value) instead of requiring every call of the fn to.
634
+ fn varOkCached(&self, unit: usize, v: &str, strict: bool, entryUnique: bool) -> Result<(), String> {
464
- let key = (unit, v.to_string());
635
+ let key = (unit, v.to_string(), strict, entryUnique);
465
636
  if let Some(r) = self.cache.borrow().get(&key) {
466
637
  return r.clone();
467
638
  }
468
- let r = self.varOkRaw(unit, v);
639
+ let r = self.varOkRaw(unit, v, strict, entryUnique);
469
640
  self.cache.borrow_mut().insert(key, r.clone());
470
641
  r
471
642
  }
472
643
 
473
- fn varOkRaw(&self, unit: usize, v: &str) -> Result<(), String> {
644
+ fn varOkRaw(&self, unit: usize, v: &str, strict: bool, entryUnique: bool) -> Result<(), String> {
474
645
  let u = &self.units[unit];
475
646
  let param = u.params.iter().position(|p| p.name == v);
476
647
  if let Some(i) = param {
@@ -480,12 +651,12 @@ impl An {
480
651
  if !u.params[i].plain {
481
652
  return Err(format!("{v} is a fn-typed parameter"));
482
653
  }
483
- if !self.paramUnique(unit, i) {
654
+ if !entryUnique && !self.paramUnique(unit, i) {
484
655
  let why = self.upWhy.borrow().get(&(unit, i)).cloned();
485
656
  return Err(why.unwrap_or_else(|| format!("a caller of {} may pass a shared {v}", u.name)));
486
657
  }
487
658
  }
488
- let mut s = Scan { an: self, v, boundDepth: if param.is_some() { Some(0) } else { None }, err: None };
659
+ let mut s = Scan { an: self, v, strict, boundDepth: if param.is_some() { Some(0) } else { None }, err: None };
489
660
  s.block(&u.block, true, 0);
490
661
  if let Some(e) = s.err {
491
662
  return Err(e);
@@ -496,6 +667,50 @@ impl An {
496
667
  Ok(())
497
668
  }
498
669
 
670
+ /// May this `Array.with` call write its receiver in place? The receiver must be unshared and
671
+ /// dead afterwards: a fresh array, a unique local or parameter that the call consumes (the
672
+ /// value returned, or rebound by `v = v.with(..)`), the field of a unique field rebuilt by
673
+ /// `x.f = x.f.with(..)`, or `T(..s, f: s.f.with(..))` of a unique `s`.
674
+ fn withOk(&self, site: &Site) -> Result<(), String> {
675
+ if site.inClosure {
676
+ return Err("inside a closure".to_string());
677
+ }
678
+ let Some(Some(recv)) = site.args.first() else { return Err("no receiver".to_string()) };
679
+ if self.fresh(recv) {
680
+ return Ok(());
681
+ }
682
+ match &recv.kind {
683
+ ExprKind::Var(_) | ExprKind::Self_ => {
684
+ let v = varName(recv).unwrap_or("");
685
+ self.varOk(site.caller, v)?;
686
+ let consumed = site.tail || matches!(&site.assignBack, Some(AssignTarget::Var(t)) if t == v);
687
+ if consumed {
688
+ Ok(())
689
+ } else {
690
+ Err(format!("{v} is used after the write"))
691
+ }
692
+ }
693
+ ExprKind::Attribute(a) => {
694
+ let AttrKind::Field(f) = &a.attr else { return Err("receiver is a method result".to_string()) };
695
+ match self.spreadWith.get(&site.node) {
696
+ Some(sw) => {
697
+ if !sw.clean {
698
+ return Err(format!("another field of the spread reads {f}"));
699
+ }
700
+ self.varOk(sw.unit, &sw.var)?;
701
+ if self.uf.borrow().contains(&sw.field) {
702
+ Ok(())
703
+ } else {
704
+ Err(format!("field {f} may be shared"))
705
+ }
706
+ }
707
+ None => self.argOk(site, recv),
708
+ }
709
+ }
710
+ _ => Err("receiver may be shared".to_string()),
711
+ }
712
+ }
713
+
499
714
  fn spreadProved(&self, s: &SpreadSite) -> bool {
500
715
  match &s.var {
501
716
  Some(v) => self.varOk(s.unit, v).is_ok(),
@@ -544,6 +759,7 @@ impl An {
544
759
  struct Scan<'a> {
545
760
  an: &'a An,
546
761
  v: &'a str,
762
+ strict: bool,
547
763
  boundDepth: Option<usize>,
548
764
  err: Option<String>,
549
765
  }
@@ -575,6 +791,28 @@ impl<'a> Scan<'a> {
575
791
  }
576
792
  }
577
793
 
794
+ /// May `v` be bound to `val`? A fresh value, or (outside strict mode) the result of a fn
795
+ /// returning a parameter we hand it unique: a fresh argument, or `v` itself in `v = g(v)`.
796
+ fn bindingOk(&self, val: &Expr, declare: bool) -> bool {
797
+ if self.an.fresh(val) {
798
+ return true;
799
+ }
800
+ if self.strict {
801
+ return false;
802
+ }
803
+ let v = self.v;
804
+ let same = |a: &Expr| !declare && isVar(a, v);
805
+ match self.an.passDeps(val, &same) {
806
+ Some(deps) => deps.iter().all(|&(g, j)| self.an.passParamOk(g, j)),
807
+ None => false,
808
+ }
809
+ }
810
+
811
+ /// May a hand-over `v = g(v)` to `g` rebind `v` to its result?
812
+ fn resultOk(&self, g: usize) -> bool {
813
+ self.an.fresh_ret.borrow().contains(&g) || (!self.strict && self.an.passes.contains_key(&g))
814
+ }
815
+
578
816
  fn escapes(&self) -> String {
579
817
  format!("{} escapes while still live", self.v)
580
818
  }
@@ -606,7 +844,7 @@ impl<'a> Scan<'a> {
606
844
  Some(_) => self.fail(format!("{v} shadowed in an inner scope")),
607
845
  }
608
846
  }
609
- if !self.an.fresh(val) {
847
+ if !self.bindingOk(val, a.declare) {
610
848
  self.fail(format!("{v} bound to a value that may be shared"));
611
849
  } else {
612
850
  self.expr(val, false, true);
@@ -685,8 +923,8 @@ impl<'a> Scan<'a> {
685
923
  let ok = bareCount == 1
686
924
  && (tail || ab)
687
925
  && g.is_some_and(|g| {
688
- self.an.paramPos(g, c, k).is_some_and(|j| self.an.paramUnique(g, j))
926
+ self.an.paramPos(g, c, k).is_some_and(|j| self.an.handOk(g, j))
689
- && (!ab || self.an.fresh_ret.borrow().contains(&g))
927
+ && (!ab || self.resultOk(g))
690
928
  });
691
929
  if !ok {
692
930
  self.fail(format!("{v} passed to {} without being dead afterwards", c.name));
@@ -709,12 +947,13 @@ impl<'a> Scan<'a> {
709
947
  && (tail || ab)
710
948
  && !cands.is_empty()
711
949
  && cands.iter().all(|&g| {
712
- s.an.methodParam(g, c, k).is_some_and(|j| s.an.paramUnique(g, j))
950
+ s.an.methodParam(g, c, k).is_some_and(|j| s.an.handOk(g, j))
713
- && (!ab || s.an.fresh_ret.borrow().contains(&g))
951
+ && (!ab || s.resultOk(g))
714
952
  })
715
953
  };
954
+ let readOnly = recvBare && !cands.is_empty() && cands.iter().all(|g| self.an.ro.contains(g));
716
955
  if recvBare {
717
- if !handOver(self, None) {
956
+ if !readOnly && !handOver(self, None) {
718
957
  self.fail(format!("{v} passed as self to {} without being dead afterwards", c.name));
719
958
  }
720
959
  } else {
@@ -853,13 +1092,38 @@ pub fn markUnique(src: &mut Source) -> UniqueReport {
853
1092
  }
854
1093
  }
855
1094
  }
1095
+ // `Array.with` calls whose receiver is proved unique and dead afterwards.
1096
+ let mut withMarks: HashSet<NodeId> = HashSet::new();
1097
+ for site in an.sites.iter().filter(|s| an.arrayWith.contains(&s.callee)) {
1098
+ let u = &an.units[site.caller];
1099
+ if u.kind == Kind::Const {
1100
+ continue;
1101
+ }
1102
+ let label = format!("{}:{} (array write)", u.label, lineOf(src, u));
1103
+ match an.withOk(site) {
1104
+ Ok(()) => {
1105
+ withMarks.insert(site.node);
1106
+ report.proved.push(label);
1107
+ }
1108
+ Err(r) => report.unproved.push((label, r)),
1109
+ }
1110
+ }
856
1111
  // Mutable pass.
857
1112
  for (ui, u) in an.units.iter().enumerate() {
858
1113
  if u.kind == Kind::Const {
859
1114
  continue;
860
1115
  }
861
1116
  let ok = &okVars[ui];
862
- let mut mark = |c: &mut ClassCall| {
1117
+ let mut mark = |e: &mut Expr| {
1118
+ if withMarks.contains(&e.id) {
1119
+ if let ExprKind::Attribute(a) = &mut e.kind {
1120
+ if let AttrKind::Method(c) = &mut a.attr {
1121
+ c.unique = true;
1122
+ }
1123
+ }
1124
+ return;
1125
+ }
1126
+ let ExprKind::ClassCall(c) = &mut e.kind else { return };
863
1127
  if let Some(s) = &c.spread {
864
1128
  if let Some(v) = varName(s) {
865
1129
  if ok.contains(v) && an.varOk(ui, v).is_ok() {
@@ -894,9 +1158,19 @@ fn build(src: &Source) -> An {
894
1158
  let mut units: Vec<Unit> = Vec::new();
895
1159
  let mut enums: HashMap<String, Vec<String>> = HashMap::new();
896
1160
  let mut nameCount: HashMap<String, usize> = HashMap::new();
1161
+ // Fields that may hold a closure (`f: fn(..)`, or a bare type parameter): `x.f(..)` can be a
1162
+ // closure call, so a method of the same name is not resolvable.
1163
+ let mut callable: HashSet<String> = HashSet::new();
897
1164
  for (idx, item) in src.items.iter().enumerate() {
898
1165
  match item {
899
1166
  Item::Enum(e) => {
1167
+ for v in &e.variants {
1168
+ for (t, n) in v.fields.iter().zip(&v.field_names) {
1169
+ if t.name == FN_TYPE_NAME || e.generics.iter().any(|g| g.name == t.name) {
1170
+ callable.insert(n.clone());
1171
+ }
1172
+ }
1173
+ }
900
1174
  let mut names: Vec<String> = Vec::new();
901
1175
  for v in &e.variants {
902
1176
  names.extend(v.field_names.iter().cloned());
@@ -963,16 +1237,50 @@ fn build(src: &Source) -> An {
963
1237
  }),
964
1238
  }
965
1239
  }
1240
+ // A local, parameter, closure parameter or pattern binder named like a free fn shadows it:
1241
+ // a call `f(..)` may then be a closure call, so such names are not resolvable.
1242
+ let mut bound: HashSet<String> = HashSet::new();
1243
+ for u in &units {
1244
+ bound.extend(u.params.iter().filter(|p| !p.plain).map(|p| p.name.clone()));
1245
+ let pats = |ps: &[CasePattern], bound: &mut HashSet<String>| {
1246
+ let mut names = vec![];
1247
+ ps.iter().for_each(|p| crate::visit::patternBinders(p, &mut names));
1248
+ bound.extend(names);
1249
+ };
1250
+ let mut found: Vec<String> = vec![];
1251
+ walkBlock(&u.block, &mut |n| {
1252
+ match n {
1253
+ Node::S(Stmt { kind: StmtKind::Assign(a), .. }) => {
1254
+ for t in &a.targets {
1255
+ if let AssignTarget::Var(v) = t {
1256
+ found.push(v.clone());
1257
+ }
1258
+ }
1259
+ }
1260
+ Node::S(Stmt { kind: StmtKind::Match(m), .. }) => {
1261
+ for c in &m.cases {
1262
+ pats(&c.patterns, &mut bound);
1263
+ }
1264
+ }
1265
+ Node::S(Stmt { kind: StmtKind::ForLoop(l), .. }) => found.extend(l.binders.iter().cloned()),
1266
+ Node::E(Expr { kind: ExprKind::Closure(c), .. }) => found.extend(c.params.iter().cloned()),
1267
+ Node::E(Expr { kind: ExprKind::Bind(b), .. }) => pats(&b.case.patterns, &mut bound),
1268
+ _ => {}
1269
+ }
1270
+ true
1271
+ });
1272
+ bound.extend(found);
1273
+ }
966
1274
  // Names with duplicates are not resolvable.
967
1275
  let mut freeIdx = HashMap::new();
968
1276
  for (i, u) in units.iter().enumerate() {
969
- if u.kind == Kind::Fn && u.free && nameCount.get(&u.name) == Some(&1) {
1277
+ if u.kind == Kind::Fn && u.free && nameCount.get(&u.name) == Some(&1) && !bound.contains(&u.name) {
970
1278
  freeIdx.insert(u.name.clone(), i);
971
1279
  }
972
1280
  }
973
1281
  let mut methodIdx: HashMap<String, Vec<usize>> = HashMap::new();
974
1282
  for (i, u) in units.iter().enumerate() {
975
- if u.kind == Kind::Fn && u.method {
1283
+ if u.kind == Kind::Fn && u.method && !callable.contains(&u.name) {
976
1284
  methodIdx.entry(u.name.clone()).or_default().push(i);
977
1285
  }
978
1286
  }
@@ -984,6 +1292,8 @@ fn build(src: &Source) -> An {
984
1292
  sites: vec![],
985
1293
  escaped: HashSet::new(),
986
1294
  fresh_ret: RefCell::new(HashSet::new()),
1295
+ passes: HashMap::new(),
1296
+ passWrites: vec![],
987
1297
  up: RefCell::new(HashSet::new()),
988
1298
  upWhy: RefCell::new(HashMap::new()),
989
1299
  uf: RefCell::new(HashSet::new()),
@@ -992,7 +1302,24 @@ fn build(src: &Source) -> An {
992
1302
  patternBound: HashSet::new(),
993
1303
  poisonAll: false,
994
1304
  spreads: vec![],
1305
+ ro: HashSet::new(),
1306
+ arrayWith: HashSet::new(),
1307
+ arrayFresh: HashSet::new(),
1308
+ spreadWith: HashMap::new(),
995
1309
  };
1310
+ for (i, u) in an.units.iter().enumerate() {
1311
+ match u.label.as_str() {
1312
+ "Array.with" => {
1313
+ an.arrayWith.insert(i);
1314
+ an.arrayFresh.insert(i);
1315
+ }
1316
+ "Array.withUnique" | "Array.push" | "Array.resize" | "Array.init" | "Array.filled" => {
1317
+ an.arrayFresh.insert(i);
1318
+ }
1319
+ _ => {}
1320
+ }
1321
+ }
1322
+ an.ro = readOnlySelf(&an);
996
1323
  // Fresh-return fns: greatest fixpoint.
997
1324
  let mut fr: HashSet<usize> = an.freeIdx.values().copied().collect();
998
1325
  fr.extend(an.methodIdx.values().flatten().copied());
@@ -1000,6 +1327,9 @@ fn build(src: &Source) -> An {
1000
1327
  *an.fresh_ret.borrow_mut() = fr.clone();
1001
1328
  let mut drop = vec![];
1002
1329
  for &g in &fr {
1330
+ if an.arrayFresh.contains(&g) {
1331
+ continue;
1332
+ }
1003
1333
  let b = &an.units[g].block;
1004
1334
  let mut tails = vec![];
1005
1335
  let mut ok = collectTails(b, &mut tails);
@@ -1024,6 +1354,45 @@ fn build(src: &Source) -> An {
1024
1354
  }
1025
1355
  }
1026
1356
  *an.fresh_ret.borrow_mut() = fr;
1357
+ // Fns that may return one of their own parameters: every result is fresh or such a parameter.
1358
+ let mut passes: HashMap<usize, Vec<usize>> = HashMap::new();
1359
+ let mut order: Vec<usize> = an.freeIdx.values().copied().chain(an.methodIdx.values().flatten().copied()).collect();
1360
+ order.sort();
1361
+ for g in order {
1362
+ if an.fresh_ret.borrow().contains(&g) {
1363
+ continue;
1364
+ }
1365
+ let u = &an.units[g];
1366
+ let mut tails = vec![];
1367
+ let mut ok = collectTails(&u.block, &mut tails);
1368
+ walkBlock(&u.block, &mut |n| {
1369
+ match n {
1370
+ Node::S(Stmt { kind: StmtKind::Return(Some(e)), .. }) => tails.push(e),
1371
+ Node::E(Expr { kind: ExprKind::Closure(_), .. }) => return false,
1372
+ _ => {}
1373
+ }
1374
+ true
1375
+ });
1376
+ let mut ps: Vec<usize> = vec![];
1377
+ for e in tails {
1378
+ if an.fresh(e) {
1379
+ continue;
1380
+ }
1381
+ match varName(e).and_then(|n| u.params.iter().position(|p| p.name == n && p.plain)) {
1382
+ Some(j) => {
1383
+ if !ps.contains(&j) {
1384
+ ps.push(j);
1385
+ }
1386
+ }
1387
+ None => ok = false,
1388
+ }
1389
+ }
1390
+ if ok && !ps.is_empty() {
1391
+ ps.sort();
1392
+ passes.insert(g, ps);
1393
+ }
1394
+ }
1395
+ an.passes = passes;
1027
1396
  collectFacts(&mut an);
1028
1397
  an
1029
1398
  }
@@ -1034,6 +1403,99 @@ fn nodeKey(id: NodeId) -> NodeId {
1034
1403
  id
1035
1404
  }
1036
1405
 
1406
+ /// Is `e` the field read `s.f` of the variable `s`?
1407
+ fn isFieldOf(e: &Expr, s: &str, f: &str) -> bool {
1408
+ matches!(&e.kind, ExprKind::Attribute(x) if x.attr == AttrKind::Field(f.to_string()) && isVar(&x.object, s))
1409
+ }
1410
+
1411
+ /// `s.f.with(..)`: the receiver `s.f` (and nothing else may be the call's object).
1412
+ fn rebuiltFromItself<'a>(value: &'a Expr, s: &str, f: &str) -> Option<&'a Expr> {
1413
+ let ExprKind::Attribute(x) = &value.kind else { return None };
1414
+ let AttrKind::Method(c) = &x.attr else { return None };
1415
+ (c.name == "with" && isFieldOf(&x.object, s, f)).then_some(&x.object)
1416
+ }
1417
+
1418
+ /// Does `e` touch `s` only through plain field reads `s.g` with `g != f`? Any other use of `s`
1419
+ /// (a method call, even a read-only one, an argument, a capture) may read `s.f` through the
1420
+ /// array another field of the spread has just written in place.
1421
+ fn readsOnlyOtherFields(e: &Expr, s: &str, f: &str) -> bool {
1422
+ let (mut uses, mut plain) = (0usize, 0usize);
1423
+ walkExpr(e, &mut |n| {
1424
+ if let Node::E(x) = n {
1425
+ if isVar(x, s) {
1426
+ uses += 1;
1427
+ }
1428
+ if let ExprKind::Attribute(a) = &x.kind {
1429
+ if matches!(&a.attr, AttrKind::Field(g) if g != f) && isVar(&a.object, s) {
1430
+ plain += 1;
1431
+ }
1432
+ }
1433
+ }
1434
+ true
1435
+ });
1436
+ uses == plain
1437
+ }
1438
+
1439
+ /// The methods whose `self` is only read (see `An.ro`): a greatest fixpoint, since a method may
1440
+ /// call another read-only one on `self`.
1441
+ fn readOnlySelf(an: &An) -> HashSet<usize> {
1442
+ let mut ro: HashSet<usize> =
1443
+ (0..an.units.len()).filter(|&g| an.units[g].kind == Kind::Fn && an.units[g].method && an.units[g].hasSelf).collect();
1444
+ loop {
1445
+ let mut drop = vec![];
1446
+ for &g in &ro {
1447
+ let mut allSelf: Vec<NodeId> = vec![];
1448
+ let mut allowed: HashSet<NodeId> = HashSet::new();
1449
+ let mut captured: HashSet<NodeId> = HashSet::new();
1450
+ walkBlock(&an.units[g].block, &mut |n| {
1451
+ match n {
1452
+ Node::E(e) => match &e.kind {
1453
+ ExprKind::Self_ => allSelf.push(e.id),
1454
+ ExprKind::Attribute(a) if matches!(a.object.kind, ExprKind::Self_) => match &a.attr {
1455
+ AttrKind::Field(_) => {
1456
+ allowed.insert(a.object.id);
1457
+ }
1458
+ AttrKind::Method(c) => {
1459
+ let cands = an.cands(&c.name);
1460
+ if !cands.is_empty() && cands.iter().all(|x| ro.contains(x)) {
1461
+ allowed.insert(a.object.id);
1462
+ }
1463
+ }
1464
+ },
1465
+ ExprKind::Closure(_) => walkExpr(e, &mut |m| {
1466
+ if let Node::E(Expr { kind: ExprKind::Self_, id, .. }) = m {
1467
+ captured.insert(*id);
1468
+ }
1469
+ true
1470
+ }),
1471
+ _ => {}
1472
+ },
1473
+ Node::S(Stmt { kind: StmtKind::Assign(asg), .. }) => {
1474
+ for t in &asg.targets {
1475
+ if let AssignTarget::Field(o, _) = t {
1476
+ if matches!(o.kind, ExprKind::Self_) {
1477
+ allowed.insert(o.id);
1478
+ }
1479
+ }
1480
+ }
1481
+ }
1482
+ _ => {}
1483
+ }
1484
+ true
1485
+ });
1486
+ if allSelf.iter().any(|id| !allowed.contains(id) || captured.contains(id)) {
1487
+ drop.push(g);
1488
+ }
1489
+ }
1490
+ if drop.is_empty() {
1491
+ return ro;
1492
+ }
1493
+ for g in drop {
1494
+ ro.remove(&g);
1495
+ }
1496
+ }
1497
+ }
1498
+
1037
1499
  fn collectFacts(an: &mut An) {
1038
1500
  let mut sites: Vec<Site> = vec![];
1039
1501
  let mut escaped: HashSet<usize> = HashSet::new();
@@ -1041,10 +1503,24 @@ fn collectFacts(an: &mut An) {
1041
1503
  let mut patternBound: HashSet<String> = HashSet::new();
1042
1504
  let mut poisonAll = false;
1043
1505
  let mut spreads: Vec<SpreadSite> = vec![];
1506
+ let mut passWrites: Vec<(String, Vec<(usize, usize)>)> = vec![];
1044
1507
  let mut reads: Vec<(NodeId, String)> = vec![];
1045
1508
  let mut allowed: HashSet<NodeId> = HashSet::new();
1509
+ let mut spreadWith: HashMap<NodeId, SpreadWith> = HashMap::new();
1046
1510
  let a: &An = an;
1047
1511
  for (ui, u) in a.units.iter().enumerate() {
1512
+ let mut tailIds: HashSet<NodeId> = HashSet::new();
1513
+ {
1514
+ let mut tails: Vec<&Expr> = vec![];
1515
+ collectTails(&u.block, &mut tails);
1516
+ walkBlock(&u.block, &mut |n| {
1517
+ if let Node::S(Stmt { kind: StmtKind::Return(Some(e)), .. }) = n {
1518
+ tails.push(e);
1519
+ }
1520
+ true
1521
+ });
1522
+ tailIds.extend(tails.iter().map(|e| e.id));
1523
+ }
1048
1524
  let mut abMap: HashMap<NodeId, AssignTarget> = HashMap::new();
1049
1525
  let mut inClosure: HashSet<NodeId> = HashSet::new();
1050
1526
  // First pass: assign-back targets and closure membership.
@@ -1118,7 +1594,33 @@ fn collectFacts(an: &mut An) {
1118
1594
  let single = asg.targets.len() == 1 && asg.values.len() == 1;
1119
1595
  for (k, t) in asg.targets.iter().enumerate() {
1120
1596
  if let AssignTarget::Field(o, f) = t {
1597
+ // `o.f = g(o.f)` where `g` returns that parameter keeps the field unique
1598
+ // while the parameter stays unique (checked in `solve`).
1599
+ let mut passOk = false;
1121
- if !single || !a.fresh(&asg.values[k]) {
1600
+ if single && !a.fresh(&asg.values[0]) {
1601
+ let (cargs, recv): (Option<&Vec<Arg>>, Option<&Expr>) = match &asg.values[0].kind {
1602
+ ExprKind::FnCall(c) => (Some(&c.args), None),
1603
+ ExprKind::Attribute(x) => match &x.attr {
1604
+ AttrKind::Method(c) => (Some(&c.args), Some(&x.object)),
1605
+ _ => (None, None),
1606
+ },
1607
+ _ => (None, None),
1608
+ };
1609
+ if let Some(cargs) = cargs {
1610
+ let same = |ae: &Expr| {
1611
+ matches!(&ae.kind, ExprKind::Attribute(x) if x.attr == AttrKind::Field(f.clone()) && x.object == **o)
1612
+ };
1613
+ let n = cargs.iter().filter(|arg| same(argExpr(arg))).count()
1614
+ + recv.is_some_and(|r| same(r)) as usize;
1615
+ if n <= 1 {
1616
+ if let Some(deps) = a.passDeps(&asg.values[0], &same) {
1617
+ passWrites.push((f.clone(), deps));
1618
+ passOk = true;
1619
+ }
1620
+ }
1621
+ }
1622
+ }
1623
+ if !passOk && (!single || !a.fresh(&asg.values[k])) {
1122
1624
  badField.insert(f.clone());
1123
1625
  }
1124
1626
  if matches!(&o.kind, ExprKind::Attribute(x) if matches!(x.attr, AttrKind::Field(_))) {
@@ -1156,6 +1658,8 @@ fn collectFacts(an: &mut An) {
1156
1658
  ExprKind::ClassCall(cc) => {
1157
1659
  let names = fieldsOf(&a.enums, &cc.type_name);
1158
1660
  let mut given = vec![];
1661
+ let mut passGiven = vec![];
1662
+ let spreadVar = cc.spread.as_deref().and_then(varName);
1159
1663
  for (k, fa) in cc.fields.iter().enumerate() {
1160
1664
  let name = if fa.name.is_empty() {
1161
1665
  names.as_ref().and_then(|n| n.get(k)).cloned()
@@ -1163,8 +1667,34 @@ fn collectFacts(an: &mut An) {
1163
1667
  Some(fa.name.clone())
1164
1668
  };
1165
1669
  if let Some(nm) = name {
1670
+ // `T(..s, f: s.f.with(..))`: the field is rebuilt from itself.
1671
+ let sv = spreadVar.unwrap_or("");
1672
+ let rebuilt = spreadVar.and_then(|sv| rebuiltFromItself(&fa.value, sv, &nm));
1673
+ if let Some(recv) = rebuilt {
1674
+ allowed.insert(nodeKey(recv.id));
1675
+ // Only a spread of a unique source may write the array in place, and
1676
+ // no other field value may read `s.f` (it would see the write early).
1677
+ let clean = cc
1678
+ .fields
1679
+ .iter()
1680
+ .enumerate()
1681
+ .all(|(j, o)| j == k || readsOnlyOtherFields(&o.value, sv, &nm));
1682
+ spreadWith.insert(
1683
+ nodeKey(fa.value.id),
1684
+ SpreadWith { unit: ui, var: sv.to_string(), field: nm.clone(), clean },
1685
+ );
1686
+ }
1166
1687
  if !a.fresh(&fa.value) {
1688
+ let same = |ae: &Expr| isFieldOf(ae, sv, &nm);
1689
+ match rebuilt.and_then(|_| a.passDeps(&fa.value, &same)) {
1690
+ Some(deps) => {
1691
+ passWrites.push((nm.clone(), deps));
1692
+ passGiven.push(nm.clone());
1693
+ }
1694
+ None => {
1167
- badField.insert(nm.clone());
1695
+ badField.insert(nm.clone());
1696
+ }
1697
+ }
1168
1698
  }
1169
1699
  given.push(nm);
1170
1700
  }
@@ -1175,6 +1705,7 @@ fn collectFacts(an: &mut An) {
1175
1705
  typeName: cc.type_name.clone(),
1176
1706
  var: varName(s).map(|v| v.to_string()),
1177
1707
  given,
1708
+ passGiven,
1178
1709
  });
1179
1710
  }
1180
1711
  }
@@ -1225,13 +1756,26 @@ fn collectFacts(an: &mut An) {
1225
1756
  _ => true,
1226
1757
  }),
1227
1758
  inClosure: inClosure.contains(&nodeKey(e.id)),
1759
+ node: e.id,
1760
+ tail: tailIds.contains(&e.id),
1228
1761
  });
1229
1762
  }
1763
+ // `x.f.m(..)` with every `m` reading its receiver only: `x.f` is not shared.
1764
+ if let ExprKind::Attribute(i) = &x.object.kind {
1765
+ let cands = a.cands(&c.name);
1766
+ if matches!(i.attr, AttrKind::Field(_))
1767
+ && !cands.is_empty()
1768
+ && cands.iter().all(|g| a.ro.contains(g))
1769
+ {
1770
+ allowed.insert(nodeKey(x.object.id));
1771
+ }
1772
+ }
1230
1773
  }
1231
1774
  if let AttrKind::Field(f) = &x.attr {
1232
1775
  reads.push((nodeKey(e.id), f.clone()));
1233
1776
  }
1234
- // `x.f.method()` hands the field itself to a method: not a plain read.
1777
+ // `x.f.h` reads a field of the object in `x.f`: `x.f` itself is not a plain read. (`x.f.m()`
1778
+ // hands the field to a method and stays a plain read, so it makes `f` shared.)
1235
1779
  if matches!(x.attr, AttrKind::Field(_))
1236
1780
  && matches!(&x.object.kind, ExprKind::Attribute(i) if matches!(i.attr, AttrKind::Field(_)))
1237
1781
  {
@@ -1282,6 +1826,8 @@ fn collectFacts(an: &mut An) {
1282
1826
  _ => true,
1283
1827
  }),
1284
1828
  inClosure: inClosure.contains(&nodeKey(e.id)),
1829
+ node: e.id,
1830
+ tail: tailIds.contains(&e.id),
1285
1831
  });
1286
1832
  }
1287
1833
  }
@@ -1311,6 +1857,8 @@ fn collectFacts(an: &mut An) {
1311
1857
  an.patternBound = patternBound;
1312
1858
  an.poisonAll = poisonAll;
1313
1859
  an.spreads = spreads;
1860
+ an.passWrites = passWrites;
1861
+ an.spreadWith = spreadWith;
1314
1862
  }
1315
1863
 
1316
1864
  fn solve(an: &An) {
@@ -1346,6 +1894,7 @@ fn solve(an: &An) {
1346
1894
  let candidates: Vec<(usize, usize)> = an.up.borrow().iter().copied().collect();
1347
1895
  for (g, j) in candidates {
1348
1896
  let mut why: Option<String> = None;
1897
+ let mut okFrom: Option<usize> = None;
1349
1898
  for site in an.sites.iter().filter(|s| s.callee == g) {
1350
1899
  let r = match &site.args[j] {
1351
1900
  Some(e) => an.argOk(site, e),
@@ -1354,11 +1903,20 @@ fn solve(an: &An) {
1354
1903
  _ => Err("a call omits the argument".to_string()),
1355
1904
  },
1356
1905
  };
1906
+ match r {
1357
- if let Err(m) = r {
1907
+ Err(m) => {
1908
+ let from = &an.units[site.caller].label;
1909
+ if why.is_none() {
1358
- why = Some(format!("{} (in a call of {})", m, an.units[g].name));
1910
+ why = Some(format!("{} (in a call of {} from {})", m, an.units[g].name, from));
1911
+ }
1912
+ }
1359
- break;
1913
+ Ok(()) => okFrom = okFrom.or(Some(site.caller)),
1360
1914
  }
1361
1915
  }
1916
+ // Mixed use: some call passes a unique value, another a shared one.
1917
+ if let (Some(w), Some(o)) = (&mut why, okFrom) {
1918
+ w.push_str(&format!("; a call from {} passes a unique value", an.units[o].label));
1919
+ }
1362
1920
  if let Some(w) = why {
1363
1921
  removeUp.push(((g, j), w));
1364
1922
  }
@@ -1369,6 +1927,7 @@ fn solve(an: &An) {
1369
1927
  if an.spreadProved(s) {
1370
1928
  continue;
1371
1929
  }
1930
+ poisoned.extend(s.passGiven.iter().cloned());
1372
1931
  match fieldsOf(&an.enums, &s.typeName) {
1373
1932
  Some(all) => poisoned.extend(all.into_iter().filter(|f| !s.given.contains(f))),
1374
1933
  None => {
@@ -1377,6 +1936,11 @@ fn solve(an: &An) {
1377
1936
  }
1378
1937
  }
1379
1938
  }
1939
+ for (f, deps) in &an.passWrites {
1940
+ if !deps.iter().all(|&(g, j)| an.passParamOk(g, j)) {
1941
+ poisoned.insert(f.clone());
1942
+ }
1943
+ }
1380
1944
  let removeUf: Vec<String> = an.uf.borrow().iter().filter(|f| poisoned.contains(*f)).cloned().collect();
1381
1945
  if removeUp.is_empty() && removeUf.is_empty() {
1382
1946
  break;
compiler/core/tests/core/purity_test.rs CHANGED
@@ -127,3 +127,44 @@ fn fn_taking_primitive_io_is_not_pure() {
127
127
  assert!(!pure.contains("touch"), "{pure:?}");
128
128
  assert!(pure.contains("plus"), "{pure:?}");
129
129
  }
130
+
131
+ #[test]
132
+ fn a_binder_named_like_a_pure_fn_is_an_unknown_callee() {
133
+ let s = format!(
134
+ "{P}enum W =\n | Wrap(g: fn(Int) -> Int)\n | No\n\nfun helper(x: Int) -> Int = x + 1\n\n\
135
+ fun viaParam(helper: fn(Int) -> Int) -> Int = helper(1)\n\n\
136
+ fun viaLocal(k: fn(Int) -> Int) -> Int =\n helper := k\n helper(1)\n\n\
137
+ fun viaPattern(w: W) -> Int = match w\n Wrap(helper) => helper(1)\n No => 0\n\n\
138
+ fun viaClosureParam() -> Int =\n k := |helper: Int| helper(1)\n 1\n\n\
139
+ fun free() -> Int = helper(1)\n"
140
+ );
141
+ let p = pure(&s);
142
+ assert_eq!(p.intersection(&set(&["viaParam", "viaLocal", "viaPattern", "viaClosureParam"])).count(), 0, "{p:?}");
143
+ assert!(p.contains("helper") && p.contains("free"), "{p:?}");
144
+ }
145
+
146
+ #[test]
147
+ fn a_write_through_a_binder_named_like_a_fresh_local_is_not_pure() {
148
+ let s = format!(
149
+ "{P}struct Cell(mut n: Int)\nenum H =\n | Holds(c: Cell)\n | No\n\n\
150
+ fun viaPattern(h: H) -> Int =\n c := Cell(n: 0)\n match h\n Holds(c) =>\n c.n = 1\n 1\n No => 0\n\n\
151
+ fun fresh() -> Int =\n c := Cell(n: 0)\n c.n = 1\n c.n\n"
152
+ );
153
+ let p = pure(&s);
154
+ assert!(!p.contains("viaPattern"), "{p:?}");
155
+ assert!(p.contains("fresh"), "{p:?}");
156
+ }
157
+
158
+ #[test]
159
+ fn a_call_of_an_fn_typed_field_is_not_a_method_of_that_name() {
160
+ let s = format!(
161
+ "{P}struct Rec(zap: fn(Int) -> Int)\nstruct Plain(label: Str) =\n fun zap(self, x: Int) -> Int = x + 1\n\n\
162
+ fun same(r: Rec) -> Rec = r\n\n\
163
+ fun typed(r: Rec) -> Int = r.zap(1)\n\n\
164
+ fun untyped(r: Rec) -> Int =\n q := same(r)\n q.zap(1)\n\n\
165
+ fun method(p: Plain) -> Int = p.zap(1)\n"
166
+ );
167
+ let p = pure(&s);
168
+ assert!(!p.contains("typed") && !p.contains("untyped"), "{p:?}");
169
+ assert!(p.contains("method"), "{p:?}");
170
+ }
compiler/core/tests/core/record_init_test.rs CHANGED
@@ -62,7 +62,7 @@ fn ship_example_lowers() {
62
62
  assert!(en.structInfo().unwrap().embedFields.is_empty());
63
63
  let n = fnNamed(&s, "Ship__new").unwrap();
64
64
  let names: Vec<_> = n.params.iter().map(|p| p.name.as_str()).collect();
65
- assert_eq!(names, vec!["x", "y", "tex"]);
65
+ assert_eq!(names, vec!["__p_x", "__p_y", "__p_tex"]);
66
66
  assert!(fnNamed(&s, "init").is_none());
67
67
  let main = fnNamed(&s, "main").unwrap();
68
68
  let FnBody::Block(b) = &main.body else { panic!() };
compiler/core/tests/core/uniqueness_test.rs CHANGED
@@ -169,13 +169,13 @@ fn self_spread_in_method_unique() {
169
169
  #[test]
170
170
  fn trait_dispatch_param_unique() {
171
171
  // Two types share the method name; the call site resolves to both.
172
- let s = "struct Cat(x: Int) =\n fun add(self, d: Int) -> Cat = Cat(..self, x: self.x + d)\n\
172
+ let s = "struct Cat(x: Int) =\n fun shift(self, d: Int) -> Cat = Cat(..self, x: self.x + d)\n\
173
- struct Dog(x: Int) =\n fun add(self, d: Int) -> Dog = Dog(..self, x: self.x + d)\n\
173
+ struct Dog(x: Int) =\n fun shift(self, d: Int) -> Dog = Dog(..self, x: self.x + d)\n\
174
- fun go() -> Cat =\n a := Cat(x: 0)\n a.add(1)\n\
174
+ fun go() -> Cat =\n a := Cat(x: 0)\n a.shift(1)\n\
175
- fun go2() -> Dog =\n b := Dog(x: 0)\n b = b.add(2)\n b\n";
175
+ fun go2() -> Dog =\n b := Dog(x: 0)\n b = b.shift(2)\n b\n";
176
176
  let (_, r) = run(s);
177
- assert!(proved(&r, "Cat.add:2"), "{r:?}");
177
+ assert!(proved(&r, "Cat.shift:2"), "{r:?}");
178
- assert!(proved(&r, "Dog.add:4"), "{r:?}");
178
+ assert!(proved(&r, "Dog.shift:4"), "{r:?}");
179
179
  }
180
180
 
181
181
  #[test]
@@ -218,3 +218,263 @@ fn anyUniqueMethod(s: &Source, name: &str) -> bool {
218
218
  }
219
219
  found
220
220
  }
221
+
222
+ // ---- methods, loops and returned parameters (T3) ----
223
+
224
+ fn provedFn(r: &UniqueReport, name: &str) -> bool {
225
+ r.proved.iter().any(|p| p.starts_with(&format!("{name}:")))
226
+ }
227
+
228
+ fn whyNot(r: &UniqueReport, name: &str) -> String {
229
+ r.unproved.iter().find(|(l, _)| l.starts_with(&format!("{name}:"))).map(|(_, m)| m.clone()).unwrap_or_default()
230
+ }
231
+
232
+ const CELL: &str = "struct Cell(label: Str, mut n: Int) =\n fun bumped(self) -> Cell = Cell(..self, n: self.n + 1)\n fun same(self) -> Cell = self\n\
233
+ fun bump(c: Cell) -> Cell = Cell(..c, n: c.n + 1)\n\
234
+ fun touch(c: Cell) -> Cell =\n c.n = c.n + 1\n c\n\
235
+ struct Holder(mut c: Cell, tag: Int)\n";
236
+
237
+ #[test]
238
+ fn method_handed_over_in_a_while_loop_is_unique() {
239
+ let s = format!(
240
+ "{CELL}fun go() -> Cell =\n v := Cell(label: \"a\", n: 0)\n i := 0\n while i < 3\n v = v.bumped()\n i = i + 1\n v\n"
241
+ );
242
+ let (_, r) = run(&s);
243
+ assert!(provedFn(&r, "Cell.bumped"), "{r:?}");
244
+ }
245
+
246
+ #[test]
247
+ fn method_handed_over_in_a_field_is_unique() {
248
+ let s = format!(
249
+ "{CELL}fun go(h: Holder) -> Holder =\n h.c = h.c.bumped()\n h\n\
250
+ fun mk() -> Holder = Holder(c: Cell(label: \"a\", n: 0), tag: 1)\n\
251
+ fun run() -> Holder =\n h := mk()\n go(h)\n"
252
+ );
253
+ let (_, r) = run(&s);
254
+ assert!(provedFn(&r, "Cell.bumped"), "{r:?}");
255
+ }
256
+
257
+ #[test]
258
+ fn returned_parameter_is_fresh_for_a_unique_argument() {
259
+ let s = format!(
260
+ "{CELL}fun go() -> Cell =\n v := Cell(label: \"a\", n: 0)\n v = touch(v)\n bump(v)\n"
261
+ );
262
+ let (_, r) = run(&s);
263
+ assert!(provedFn(&r, "bump"), "{r:?}");
264
+ assert!(provedFn(&r, "touch") || !whyNot(&r, "touch").contains("shared"), "{r:?}");
265
+ }
266
+
267
+ #[test]
268
+ fn returned_parameter_in_a_loop_keeps_the_hand_over_unique() {
269
+ let s = format!(
270
+ "{CELL}fun go() -> Cell =\n v := Cell(label: \"a\", n: 0)\n i := 0\n while i < 3\n v = touch(v)\n v = bump(v)\n i = i + 1\n v\n"
271
+ );
272
+ let (_, r) = run(&s);
273
+ assert!(provedFn(&r, "bump"), "{r:?}");
274
+ }
275
+
276
+ #[test]
277
+ fn returned_parameter_in_a_field_keeps_the_field_unique() {
278
+ let s = format!(
279
+ "{CELL}fun go(h: Holder) -> Holder =\n h.c = touch(h.c)\n h.c = bump(h.c)\n h\n\
280
+ fun mk() -> Holder = Holder(c: Cell(label: \"a\", n: 0), tag: 1)\n\
281
+ fun run() -> Holder =\n h := mk()\n go(h)\n"
282
+ );
283
+ let (_, r) = run(&s);
284
+ assert!(provedFn(&r, "bump"), "{r:?}");
285
+ }
286
+
287
+ #[test]
288
+ fn returned_parameter_with_a_shared_argument_is_not_fresh() {
289
+ // `a` is read after the call, so `touch(a)` returns a value someone else holds.
290
+ let s = format!(
291
+ "{CELL}fun go() -> Int =\n a := Cell(label: \"a\", n: 0)\n v := touch(a)\n w := bump(v)\n a.n + w.n\n"
292
+ );
293
+ let (_, r) = run(&s);
294
+ assert!(!provedFn(&r, "bump"), "{r:?}");
295
+ }
296
+
297
+ #[test]
298
+ fn returned_parameter_that_was_stored_is_not_fresh() {
299
+ let s = format!(
300
+ "{CELL}fun reg(xs: Slice[Cell], c: Cell) -> Cell =\n xs.push(c)\n c\n\
301
+ fun go(xs: Slice[Cell]) -> Cell =\n v := Cell(label: \"a\", n: 0)\n v = reg(xs, v)\n bump(v)\n"
302
+ );
303
+ let (_, r) = run(&s);
304
+ assert!(!provedFn(&r, "bump"), "{r:?}");
305
+ }
306
+
307
+ #[test]
308
+ fn returned_parameter_in_a_field_that_was_stored_is_not_unique() {
309
+ let s = format!(
310
+ "{CELL}fun reg(xs: Slice[Cell], c: Cell) -> Cell =\n xs.push(c)\n c\n\
311
+ fun go(h: Holder, xs: Slice[Cell]) -> Holder =\n h.c = reg(xs, h.c)\n h.c = bump(h.c)\n h\n\
312
+ fun mk() -> Holder = Holder(c: Cell(label: \"a\", n: 0), tag: 1)\n\
313
+ fun run(xs: Slice[Cell]) -> Holder =\n h := mk()\n go(h, xs)\n"
314
+ );
315
+ let (_, r) = run(&s);
316
+ assert!(!provedFn(&r, "bump"), "{r:?}");
317
+ }
318
+
319
+ #[test]
320
+ fn returned_parameter_handed_a_shared_value_elsewhere_is_not_unique() {
321
+ // `touch` is called with a unique value here and a shared one in `other`.
322
+ let s = format!(
323
+ "{CELL}fun go() -> Cell =\n v := Cell(label: \"a\", n: 0)\n v = touch(v)\n bump(v)\n\
324
+ fun other(a: Cell) -> Int =\n b := touch(a)\n a.n + b.n\n"
325
+ );
326
+ let (_, r) = run(&s);
327
+ assert!(!provedFn(&r, "touch"), "{r:?}");
328
+ assert!(!provedFn(&r, "bump"), "{r:?}");
329
+ }
330
+
331
+ #[test]
332
+ fn mixed_unique_and_shared_calls_say_so() {
333
+ let s = format!(
334
+ "{CELL}fun go() -> Cell =\n v := Cell(label: \"a\", n: 0)\n bump(v)\n\
335
+ fun other(a: Cell) -> Int =\n b := bump(a)\n a.n + b.n\n"
336
+ );
337
+ let (_, r) = run(&s);
338
+ assert!(!provedFn(&r, "bump"), "{r:?}");
339
+ let why = whyNot(&r, "bump");
340
+ assert!(why.contains("from other") && why.contains("passes a unique value"), "{why}");
341
+ }
342
+
343
+ #[test]
344
+ fn override_storing_self_makes_the_method_name_not_unique() {
345
+ let s = "struct Base(label: Str, n: Int) =\n fun step(self) -> Base = Base(..self, n: self.n + 1)\n\
346
+ struct Sub(Base(label, n), log: Slice[Base]) =\n override fun step(self) -> Base =\n self.log.push(self)\n Base(label: self.label, n: self.n + 1)\n\
347
+ fun go(b: Base) -> Int =\n c := b.step()\n b.n + c.n\n";
348
+ let (_, r) = run(s);
349
+ assert!(!provedFn(&r, "Base.step"), "{r:?}");
350
+ }
351
+
352
+ #[test]
353
+ fn override_storing_self_with_a_unique_receiver_stays_a_copy_of_the_stored_value() {
354
+ // The receiver is dead after the call, so Base.step may write in place; Sub.step keeps
355
+ // `self` in its log, and the log is the only holder left.
356
+ let s = "struct Base(label: Str, n: Int) =\n fun step(self) -> Base = Base(..self, n: self.n + 1)\n\
357
+ struct Sub(Base(label, n), log: Slice[Base]) =\n override fun step(self) -> Base =\n self.log.push(self)\n Base(label: self.label, n: self.n + 1)\n\
358
+ fun go() -> Base =\n b := Base(label: \"a\", n: 0)\n b.step()\n";
359
+ let (_, r) = run(s);
360
+ assert!(!provedFn(&r, "Sub.step"), "{r:?}");
361
+ }
362
+
363
+ #[test]
364
+ fn stored_in_two_fields_not_unique() {
365
+ let s = format!(
366
+ "{CELL}struct Two(a: Cell, b: Cell)\n\
367
+ fun go() -> Two =\n v := Cell(label: \"a\", n: 0)\n t := Two(a: v, b: v)\n v = bump(v)\n t\n"
368
+ );
369
+ let (_, r) = run(&s);
370
+ assert!(!provedFn(&r, "bump"), "{r:?}");
371
+ }
372
+
373
+ #[test]
374
+ fn returned_with_another_reference_not_unique() {
375
+ let s = format!(
376
+ "{CELL}fun go() -> Pair[Cell, Cell] =\n v := Cell(label: \"a\", n: 0)\n p := Pair(v, bump(v))\n p\n"
377
+ );
378
+ let (_, r) = run(&s);
379
+ assert!(!provedFn(&r, "bump"), "{r:?}");
380
+ }
381
+
382
+ #[test]
383
+ fn update_in_one_branch_with_old_value_read_after_not_unique() {
384
+ let s = format!(
385
+ "{CELL}fun go(flag: Bool) -> Int =\n c := Cell(label: \"a\", n: 0)\n d := c\n if flag\n d = bump(d)\n c.n + d.n\n"
386
+ );
387
+ let (_, r) = run(&s);
388
+ assert!(!provedFn(&r, "bump"), "{r:?}");
389
+ }
390
+
391
+ #[test]
392
+ fn matched_into_a_binding_not_unique() {
393
+ let s = format!(
394
+ "{CELL}fun go() -> Int =\n c := Cell(label: \"a\", n: 0)\n match c\n k => bump(c).n + k.n\n"
395
+ );
396
+ let (_, r) = run(&s);
397
+ assert!(!provedFn(&r, "bump"), "{r:?}");
398
+ }
399
+
400
+ #[test]
401
+ fn loop_keeping_the_previous_value_not_unique() {
402
+ let s = format!(
403
+ "{CELL}fun go(xs: Slice[Cell]) -> Cell =\n v := Cell(label: \"a\", n: 0)\n i := 0\n while i < 3\n xs.push(v)\n v = v.bumped()\n i = i + 1\n v\n"
404
+ );
405
+ let (_, r) = run(&s);
406
+ assert!(!provedFn(&r, "Cell.bumped"), "{r:?}");
407
+ }
408
+
409
+ #[test]
410
+ fn loop_value_bound_outside_from_a_shared_source_not_unique() {
411
+ let s = format!(
412
+ "{CELL}fun go(start: Cell) -> Cell =\n v := start\n i := 0\n while i < 3\n v = v.bumped()\n i = i + 1\n v\n\
413
+ fun other(c: Cell) -> Int =\n d := go(c)\n c.n + d.n\n"
414
+ );
415
+ let (_, r) = run(&s);
416
+ assert!(!provedFn(&r, "Cell.bumped"), "{r:?}");
417
+ }
418
+
419
+ #[test]
420
+ fn constant_receiver_not_unique() {
421
+ let s = "struct Zero(label: Str, n: Int) =\n Origin = Zero(label: \"z\", n: 0)\n fun inc(self) -> Zero = Zero(..self, n: self.n + 1)\n\
422
+ fun go() -> Zero = Zero.Origin.inc()\n";
423
+ let (_, r) = run(s);
424
+ assert!(!provedFn(&r, "Zero.inc"), "{r:?}");
425
+ }
426
+
427
+ #[test]
428
+ fn read_out_of_a_mut_field_and_handed_on_not_unique() {
429
+ // `h.c` is read into `held` as well, so the field is shared and `bump` must copy.
430
+ let s = format!(
431
+ "{CELL}fun go(h: Holder) -> Int =\n held := h.c\n v := bump(h.c)\n held.n + v.n\n\
432
+ fun mk() -> Holder = Holder(c: Cell(label: \"a\", n: 0), tag: 1)\n\
433
+ fun run() -> Int =\n h := mk()\n go(h)\n"
434
+ );
435
+ let (_, r) = run(&s);
436
+ assert!(!provedFn(&r, "bump"), "{r:?}");
437
+ }
438
+
439
+ #[test]
440
+ fn struct_reachable_from_a_mut_field_of_another_not_unique() {
441
+ // `outer.c` holds `v` and `v` is spread: the field holds the same object.
442
+ let s = format!(
443
+ "{CELL}fun go() -> Holder =\n v := Cell(label: \"a\", n: 0)\n h := Holder(c: v, tag: 1)\n w := bump(v)\n h\n"
444
+ );
445
+ let (_, r) = run(&s);
446
+ assert!(!provedFn(&r, "bump"), "{r:?}");
447
+ }
448
+
449
+ #[test]
450
+ fn generic_function_with_both_kinds_not_unique() {
451
+ let s = format!(
452
+ "{CELL}fun ident[T](x: T) -> T = x\n\
453
+ fun go(a: Cell) -> Int =\n b := bump(ident(a))\n a.n + b.n\n"
454
+ );
455
+ let (_, r) = run(&s);
456
+ assert!(!provedFn(&r, "bump"), "{r:?}");
457
+ }
458
+
459
+ #[test]
460
+ fn a_closure_parameter_named_like_a_fresh_fn_is_not_that_fn() {
461
+ // `mk` in `go` is the parameter, not the free fn `mk`: its result may be shared.
462
+ let s = format!(
463
+ "{CELL}fun mk() -> Cell = Cell(label: \"m\", n: 0)\n\
464
+ fun go(mk: fn() -> Cell) -> Cell =\n y := mk()\n y = bump(y)\n y\n"
465
+ );
466
+ let (_, r) = run(&s);
467
+ assert!(!provedFn(&r, "bump"), "{r:?}");
468
+ }
469
+
470
+ #[test]
471
+ fn a_closure_field_named_like_a_fresh_method_is_not_that_method() {
472
+ // `h.made()` calls the closure in the field, not `Maker.made`.
473
+ let s = format!(
474
+ "{CELL}struct Maker(k: Int) =\n fun made(self) -> Cell = Cell(label: \"m\", n: 0)\n\
475
+ struct Hook(made: fn() -> Cell)\n\
476
+ fun go(h: Hook) -> Cell =\n y := h.made()\n y = bump(y)\n y\n"
477
+ );
478
+ let (_, r) = run(&s);
479
+ assert!(!provedFn(&r, "bump"), "{r:?}");
480
+ }
compiler/driver/src/lib.rs CHANGED
@@ -16,13 +16,16 @@ pub struct PassOptions {
16
16
  /// The supercompiler stage (`--no-fusion` clears it).
17
17
  pub fusion: bool,
18
18
  pub trmc: bool,
19
+ /// In-place updates (FBIP): uniqueness marks and same-shape cell reuse. `--no-fbip` clears it;
20
+ /// every spread then copies and no cell is overwritten. Only meaningful with `fusion`.
21
+ pub fbip: bool,
19
22
  /// Print each fusion decision and each dropped rewrite (`--explain-fusion`).
20
23
  pub explain: bool,
21
24
  }
22
25
 
23
26
  impl Default for PassOptions {
24
27
  fn default() -> Self {
25
- PassOptions { closureSpec: true, fusion: true, trmc: true, explain: false }
28
+ PassOptions { closureSpec: true, fusion: true, trmc: true, fbip: true, explain: false }
26
29
  }
27
30
  }
28
31
 
@@ -39,6 +42,8 @@ pub enum Target {
39
42
  /// What a rewrite may read besides the program.
40
43
  pub struct Env<'a> {
41
44
  pub explain: bool,
45
+ /// Whether in-place updates may be marked (`PassOptions.fbip`).
46
+ pub fbip: bool,
42
47
  /// Receiver types of method calls, read off the checked program (see `closureHints`).
43
48
  pub hints: &'a Hints,
44
49
  }
@@ -58,20 +63,27 @@ fn closureSpec(copy: &mut Source, env: &Env) -> bool {
58
63
 
59
64
  /// Purity -> simplify -> drive -> uniqueness -> reuse; returns every note (empty = nothing changed).
60
65
  pub fn fusionNotes(copy: &mut Source) -> Vec<String> {
66
+ fusionNotesWith(copy, true)
67
+ }
68
+
69
+ /// `fusionNotes`; with `fbip` off, uniqueness and cell reuse do not run, so nothing is updated in place.
70
+ pub fn fusionNotesWith(copy: &mut Source, fbip: bool) -> Vec<String> {
61
71
  let pure = plum_core::purity::pureFns(copy);
62
72
  let mut notes = plum_core::simplify::simplify(copy, &pure);
63
73
  notes.extend(plum_core::drive::drive(copy, &pure));
74
+ if fbip {
64
- let rep = plum_core::uniqueness::markUnique(copy);
75
+ let rep = plum_core::uniqueness::markUnique(copy);
65
- notes.extend(rep.proved.iter().map(|l| format!("unique spread at {l}")));
76
+ notes.extend(rep.proved.iter().map(|l| format!("unique spread at {l}")));
66
- notes.extend(rep.unproved.iter().map(|(l, why)| format!("uniqueness: not in place {l}: {why}")));
77
+ notes.extend(rep.unproved.iter().map(|(l, why)| format!("uniqueness: not in place {l}: {why}")));
67
- notes.retain(|n| !n.is_empty());
78
+ notes.retain(|n| !n.is_empty());
68
- notes.extend(plum_core::reuse::markReuse(copy));
79
+ notes.extend(plum_core::reuse::markReuse(copy));
80
+ }
69
81
  notes.retain(|n| !n.is_empty());
70
82
  notes
71
83
  }
72
84
 
73
85
  fn fusion(copy: &mut Source, env: &Env) -> bool {
74
- let notes = fusionNotes(copy);
86
+ let notes = fusionNotesWith(copy, env.fbip);
75
87
  if env.explain {
76
88
  for n in &notes {
77
89
  eprintln!("fusion: {n}");
@@ -136,7 +148,7 @@ fn runPass(pass: &Pass, original: &Source, opts: &PassOptions, st: &mut State) {
136
148
  } else {
137
149
  Hints::new()
138
150
  };
139
- let env = Env { explain: opts.explain, hints: &hints };
151
+ let env = Env { explain: opts.explain, fbip: opts.fbip, hints: &hints };
140
152
  let mut copy = match pass.target {
141
153
  Target::Pre => st.pre.clone(),
142
154
  Target::Lowered => match st.info.lowered.as_ref() {
compiler/driver/tests/driver_tests.rs CHANGED
@@ -30,7 +30,7 @@ fn loweredNames(src: &Source, opts: &PassOptions) -> Vec<String> {
30
30
  #[test]
31
31
  fn noPassesMeansNoGeneratedFns() {
32
32
  let src = load("drv_none", SRC);
33
- let opts = PassOptions { closureSpec: false, fusion: false, trmc: false, explain: false };
33
+ let opts = PassOptions { closureSpec: false, fusion: false, trmc: false, fbip: false, explain: false };
34
34
  let names = loweredNames(&src, &opts);
35
35
  assert!(names.iter().all(|n| !n.contains('$')), "{names:?}");
36
36
  }
compiler/game/web-test/src/lib.rs CHANGED
@@ -62,6 +62,8 @@ pub struct Options {
62
62
  pub expect_pixels: Vec<ExpectPixel>,
63
63
  /// Destroy the GPU device from the page after a few frames and require rendering to resume.
64
64
  pub lose_device: bool,
65
+ /// Pass `--no-fbip` to `plum build`.
66
+ pub no_fbip: bool,
65
67
  }
66
68
 
67
69
  impl Default for Options {
@@ -80,6 +82,7 @@ impl Default for Options {
80
82
  uncapped: false,
81
83
  dpr: None,
82
84
  lose_device: false,
85
+ no_fbip: false,
83
86
  expect_pixels: Vec::new(),
84
87
  }
85
88
  }
@@ -234,7 +237,7 @@ pub fn repo_root() -> PathBuf {
234
237
  }
235
238
 
236
239
  /// Builds plum-cli and exports `file` as a static web build into `out`.
237
- pub fn build_web(file: &Path, out: &Path, assets: Option<&Path>) -> Result<(), String> {
240
+ pub fn build_web(file: &Path, out: &Path, assets: Option<&Path>, no_fbip: bool) -> Result<(), String> {
238
241
  let root = repo_root();
239
242
  let st = Command::new("cargo")
240
243
  .args(["build", "-p", "plum-cli"])
@@ -247,6 +250,9 @@ pub fn build_web(file: &Path, out: &Path, assets: Option<&Path>) -> Result<(), S
247
250
  let file = file.canonicalize().map_err(|e| format!("{}: {e}", file.display()))?;
248
251
  let mut cmd = Command::new(root.join("target/debug/plum"));
249
252
  cmd.arg("build").arg(&file).arg("-o").arg(out);
253
+ if no_fbip {
254
+ cmd.arg("--no-fbip");
255
+ }
250
256
  if let Some(a) = assets {
251
257
  cmd.arg("--assets").arg(a.canonicalize().map_err(|e| format!("{}: {e}", a.display()))?);
252
258
  }
@@ -387,7 +393,7 @@ pub async fn run(file: &Path, opts: &Options) -> Result<String, String> {
387
393
  }
388
394
 
389
395
  async fn run_in(file: &Path, opts: &Options, dir: &Path) -> Result<String, String> {
390
- build_web(file, dir, opts.assets.as_deref())?;
396
+ build_web(file, dir, opts.assets.as_deref(), opts.no_fbip)?;
391
397
  let stop = Arc::new(AtomicBool::new(false));
392
398
  let port = serve(dir.to_path_buf(), stop.clone());
393
399
  let res = check(port, opts).await;
compiler/game/web-test/src/main.rs CHANGED
@@ -1,7 +1,7 @@
1
1
  use plum_web_test::{browser_installed, run, Browser, ExpectPixel, Options};
2
2
  use std::path::PathBuf;
3
3
 
4
- const USAGE: &str = "usage: plum-web-test <file.plum> [--frames-wait SECS] [--screenshot OUT.png] [--require-audio]\n [--assets DIR] [--headed] [--measure SECS] [--uncapped] [--json]
4
+ const USAGE: &str = "usage: plum-web-test <file.plum> [--frames-wait SECS] [--screenshot OUT.png] [--require-audio]\n [--assets DIR] [--headed] [--measure SECS] [--uncapped] [--json] [--no-fbip]
5
5
  [--browser chromium|webkit] [--expect-unsupported-webgpu] [--no-module-introspection]
6
6
  [--dpr N] [--lose-device] [--expect-pixel x,y,r,g,b[,tol]]...";
7
7
 
@@ -18,6 +18,7 @@ async fn main() {
18
18
  "--screenshot" => opts.screenshot = Some(args.next().map(PathBuf::from).unwrap_or_else(|| fail("--screenshot needs a path"))),
19
19
  "--require-audio" => opts.require_audio = true,
20
20
  "--headed" => opts.headed = true,
21
+ "--no-fbip" => opts.no_fbip = true,
21
22
  "--uncapped" => opts.uncapped = true,
22
23
  "--json" => opts.json = true,
23
24
  "--browser" => opts.browser = Browser::parse(&args.next().unwrap_or_else(|| fail("--browser needs chromium or webkit"))).unwrap_or_else(|e| fail(&e)),
compiler/lsp/src/main.rs CHANGED
@@ -309,7 +309,7 @@ fn typeDiagnosticsFor(path: &Path, libPath: &Path, text: &str) -> Option<Vec<Dia
309
309
  overrides.insert(canon, text.to_string());
310
310
  let ast = plum_core::loadAndMergeWithOverridesDiag(path, libPath, &overrides).ok()?;
311
311
  let lastLine = text.lines().count().max(1) as u32 - 1;
312
- let opts = plum_driver::PassOptions { closureSpec: false, fusion: false, trmc: false, explain: false };
312
+ let opts = plum_driver::PassOptions { closureSpec: false, fusion: false, trmc: false, fbip: false, explain: false };
313
313
  match plum_driver::check(&ast, &opts) {
314
314
  Ok(_) => Some(Vec::new()),
315
315
  Err(diags) => Some(
compiler/wasm-codegen/src/closurecalls.rs CHANGED
@@ -285,6 +285,9 @@ pub(crate) fn compileClosureBody(
285
285
  unit_inst: unit.inst,
286
286
  unit_subst: unit.subst,
287
287
  types: unit.types,
288
+ base_types: &ctx.base_types,
289
+ inst_types: &ctx.inst_types,
290
+ global_env: &ctx.global_env,
288
291
  local_decl_types: decl_types,
289
292
  closures: &ctx.closures,
290
293
  closure_call_types: &ctx.closure_call_types,
compiler/wasm-codegen/src/construct.rs CHANGED
@@ -39,6 +39,10 @@ pub(crate) fn compileDefaultArgs(
39
39
  ctx: &LocalCtx,
40
40
  state: &mut ModuleState,
41
41
  ) -> Result<(), String> {
42
+ if sig.param_defaults.len() <= supplied_count {
43
+ return Ok(());
44
+ }
45
+ let ctx = ctx.forDefault(sig);
42
46
  for (i, default) in sig.param_defaults.iter().enumerate().skip(supplied_count) {
43
47
  let default_expr = default.as_ref().ok_or_else(|| {
44
48
  format!(
@@ -47,30 +51,13 @@ pub(crate) fn compileDefaultArgs(
47
51
  )
48
52
  })?;
49
53
  match sig.decl_params.get(i) {
50
- // A payload-free variant default (`o: Option[Int] = None`): the clone has
51
- // no recorded type, so take the singleton of the param's declared type.
52
- Some(d) if defaultSingleton(default_expr, d, ctx).is_some() => {
53
- let g = defaultSingleton(default_expr, d, ctx).expect("checked");
54
- Instruction::GlobalGet(g).encode(body);
55
- }
56
- Some(d) => compileExprInto(default_expr, d, body, ctx, state)?,
54
+ Some(d) => compileExprInto(default_expr, d, body, &ctx, state)?,
57
- None => compileExpr(default_expr, body, ctx, state)?,
55
+ None => compileExpr(default_expr, body, &ctx, state)?,
58
56
  }
59
57
  }
60
58
  Ok(())
61
59
  }
62
60
 
63
- /// The singleton global of a payload-free variant default `n` of the param type `d`.
64
- pub(crate) fn defaultSingleton(default_expr: &ast::Expr, d: &PlumType, ctx: &LocalCtx) -> Option<u32> {
65
- let ast::Expr { kind: ast::ExprKind::TypeName(n), .. } = default_expr else { return None };
66
- let info = ctx.enum_variants.get(n).filter(|i| i.field_types.is_empty())?;
67
- match d {
68
- PlumType::TNamed(e) | PlumType::TApp(e, _) if *e == info.enum_name => {}
69
- _ => return None,
70
- }
71
- ctx.singleton_globals.get(&(canonTy(d), n.clone())).copied()
72
- }
73
-
74
61
  /// Constructs a value enum by pushing its flattened fields in declaration order. Each
75
62
  /// field comes from the same-named keyword argument, else the positional argument at its
76
63
  /// index, else (`Vec2(..v, x: 1.0)`) the spread source's field.
@@ -261,6 +248,7 @@ pub(crate) fn compileInterpolatedString(
261
248
  line: 0,
262
249
  column: 0,
263
250
  tail: ast::TailKind::NotTail,
251
+ unique: false,
264
252
  };
265
253
  if plum_checker::nominalName(&other)
266
254
  .is_some_and(|n| ctx.func_ids.contains_key(&format!("{}::toStr", n)))
compiler/wasm-codegen/src/context.rs CHANGED
@@ -16,6 +16,9 @@ pub struct FuncSig {
16
16
  /// implicit receiver, and the declared return type.
17
17
  pub decl_params: Vec<PlumType>,
18
18
  pub decl_ret: PlumType,
19
+ /// The instantiation this is the signature of (`None` for a plain fn): the checker
20
+ /// recorded the types of `param_defaults` there.
21
+ pub inst: Option<usize>,
19
22
  }
20
23
 
21
24
  /// Everything codegen needs to know about one closure *literal* found in the program.
@@ -100,6 +103,9 @@ pub struct CompileCtx<'a> {
100
103
  /// Payload-free variant name (End/...) -> the global index holding
101
104
  /// its one pre-allocated instance (see this migration plan's Decision 2).
102
105
  pub singleton_globals: HashMap<(PlumType, String), u32>,
106
+ /// The checker's types of plain fns and of each instantiation.
107
+ pub(crate) base_types: UnitTypes,
108
+ pub(crate) inst_types: Vec<UnitTypes>,
103
109
  }
104
110
 
105
111
  /// Per-module state that accumulates as function bodies are compiled: every static
@@ -135,6 +141,9 @@ pub(crate) struct LocalCtx<'a> {
135
141
  /// Type-parameter bindings of the instantiation being compiled (empty for a plain fn).
136
142
  pub(crate) unit_subst: &'a Subst,
137
143
  pub(crate) types: &'a UnitTypes,
144
+ pub(crate) base_types: &'a UnitTypes,
145
+ pub(crate) inst_types: &'a [UnitTypes],
146
+ pub(crate) global_env: &'a TypeEnv,
138
147
  /// Name -> the plum type each local was DECLARED with (so its wasm
139
148
  /// representation is `plumTypeToValtype` of this), as opposed to the
140
149
  /// type of a particular use of it.
@@ -176,6 +185,52 @@ pub(crate) struct LocalCtx<'a> {
176
185
  pub(crate) self_closure: Option<(String, u32)>,
177
186
  }
178
187
 
188
+ impl LocalCtx<'_> {
189
+ /// The context a parameter default of the fn with signature `sig` compiles in, at a call
190
+ /// that leaves the argument out: that fn's unit, where its types and calls are recorded,
191
+ /// and no locals (a default sees only globals, whoever calls the fn).
192
+ pub(crate) fn forDefault(&self, sig: &FuncSig) -> LocalCtx<'_> {
193
+ let types = sig.inst.map_or(self.base_types, |id| &self.inst_types[id]);
194
+ LocalCtx {
195
+ locals: HashMap::new(),
196
+ match_scratch_base: 0,
197
+ match_scratch_index: HashMap::new(),
198
+ nested_class_scratch_base: 0,
199
+ nested_class_scratch: HashMap::new(),
200
+ func_ids: self.func_ids,
201
+ func_sigs: self.func_sigs,
202
+ inst_funcs: self.inst_funcs,
203
+ call_inst: self.call_inst,
204
+ op_calls: self.op_calls,
205
+ known_fns: self.known_fns,
206
+ unit_idx: self.unit_idx,
207
+ unit_inst: sig.inst,
208
+ unit_subst: &types.subst,
209
+ types,
210
+ base_types: self.base_types,
211
+ inst_types: self.inst_types,
212
+ global_env: self.global_env,
213
+ local_decl_types: HashMap::new(),
214
+ closures: self.closures,
215
+ closure_call_types: self.closure_call_types,
216
+ named_fn_values: self.named_fn_values,
217
+ methods: self.methods,
218
+ enum_variants: self.enum_variants,
219
+ enum_params: self.enum_params,
220
+ gc_types: self.gc_types,
221
+ singleton_globals: self.singleton_globals,
222
+ type_env: RefCell::new(self.global_env.clone()),
223
+ loop_base_depth: Cell::new(0),
224
+ ret_type: None,
225
+ subject_ptypes: RefCell::new(HashMap::new()),
226
+ self_func: None,
227
+ tail_depth: Cell::new(0),
228
+ import_count: self.import_count,
229
+ self_closure: None,
230
+ }
231
+ }
232
+ }
233
+
179
234
  /// What tail-call emission needs to know about the fn being compiled.
180
235
  pub(crate) struct SelfFunc {
181
236
  pub(crate) idx: u32,
compiler/wasm-codegen/src/driver.rs CHANGED
@@ -108,7 +108,10 @@ impl<'a> Setup<'a> {
108
108
  for ((id, node), t) in inst_annotated {
109
109
  inst_types[id].annotated.insert(node, t);
110
110
  }
111
+ for inst in &instantiations {
112
+ inst_types[inst.id].subst = inst.generics.iter().cloned().zip(inst.type_args.iter().cloned()).collect();
113
+ }
111
- let base_types = UnitTypes { exprs: expr_types, annotated };
114
+ let base_types = UnitTypes { exprs: expr_types, annotated, subst: Subst::new() };
112
115
  let (global_env, methods, enum_variants) = plum_checker::buildGlobalTables(source);
113
116
  let enum_params = EnumParams::new();
114
117
  let min_required = plum_checker::buildMinRequiredArgs(source);
@@ -650,7 +653,7 @@ impl<'a> Setup<'a> {
650
653
  let gc_types = gc_types.as_mut().unwrap();
651
654
  // Register every unit's wasm function up front.
652
655
  for u in units.iter() {
653
- let sig = unitFuncSig(u.f, &u.subst, &eg, &gc_types);
656
+ let sig = FuncSig { inst: u.inst, ..unitFuncSig(u.f, &u.subst, &eg, &gc_types) };
654
657
  let type_idx = module.addType(&sig.params, &sig.ret);
655
658
  let func_idx = module.addFunction(type_idx, &[]);
656
659
  module.nameFunction(func_idx, &u.name);
@@ -925,6 +928,8 @@ impl<'a> Setup<'a> {
925
928
  named_fn_values,
926
929
  gc_types,
927
930
  singleton_globals,
931
+ base_types,
932
+ inst_types,
928
933
  };
929
934
 
930
935
  let state = ModuleState {
@@ -938,8 +943,6 @@ impl<'a> Setup<'a> {
938
943
  state,
939
944
  units,
940
945
  const_inits,
941
- base_types,
942
- inst_types,
943
946
  }
944
947
  }
945
948
  }
compiler/wasm-codegen/src/emit.rs CHANGED
@@ -11,15 +11,13 @@ pub(crate) struct Emit<'a> {
11
11
  pub(crate) state: ModuleState,
12
12
  pub(crate) units: Vec<UnitDef<'a>>,
13
13
  pub(crate) const_inits: Vec<(String, ConstInit<'a>, u32)>,
14
- pub(crate) base_types: UnitTypes,
15
- pub(crate) inst_types: Vec<UnitTypes>,
16
14
  }
17
15
 
18
16
  impl<'a> Emit<'a> {
19
17
  /// Compile every unit's body into its reserved function slot.
20
18
  pub(crate) fn compileUnitBodies(&mut self) -> Result<(), String> {
21
- let Emit { module, ctx, state, units, base_types, inst_types, .. } = self;
19
+ let Emit { module, ctx, state, units, .. } = self;
22
- let unit_types = |u: &UnitDef| unitTypesOf(inst_types, base_types, u);
20
+ let unit_types = |u: &UnitDef| unitTypesOf(&ctx.inst_types, &ctx.base_types, u);
23
21
  let mut compiled_bodies: Vec<(u32, Vec<u8>)> = Vec::new();
24
22
  for (ui, u) in units.iter().enumerate() {
25
23
  let f = u.f;
@@ -52,7 +50,7 @@ impl<'a> Emit<'a> {
52
50
 
53
51
  /// Compile each heap-valued const's accessor body.
54
52
  pub(crate) fn compileConstBodies(&mut self) -> Result<(), String> {
55
- let Emit { module, ctx, state, const_inits, base_types, .. } = self;
53
+ let Emit { module, ctx, state, const_inits, .. } = self;
56
54
  for (name, ci, func_idx) in const_inits.iter() {
57
55
  let stand_in = ast::Fn {
58
56
  file: String::new(),
@@ -76,7 +74,7 @@ impl<'a> Emit<'a> {
76
74
  idx: usize::MAX,
77
75
  inst: None,
78
76
  subst: &no_subst,
79
- types: &base_types,
77
+ types: &ctx.base_types,
80
78
  };
81
79
  let body = compileFnBodyImpl(&stand_in, Some(ci), &ctx, state, &uref)
82
80
  .map_err(|e| format!("{e} (in const '{name}')"))?;
@@ -88,8 +86,8 @@ impl<'a> Emit<'a> {
88
86
 
89
87
  /// Compile each closure literal's own body into its reserved function slot.
90
88
  pub(crate) fn compileClosureBodies(&mut self) -> Result<(), String> {
91
- let Emit { module, ctx, state, units, base_types, inst_types, .. } = self;
89
+ let Emit { module, ctx, state, units, .. } = self;
92
- let unit_types = |u: &UnitDef| unitTypesOf(inst_types, base_types, u);
90
+ let unit_types = |u: &UnitDef| unitTypesOf(&ctx.inst_types, &ctx.base_types, u);
93
91
  // Compile each closure literal's own body into its reserved function slot.
94
92
  let mut closure_bodies: Vec<(u32, Vec<u8>)> = Vec::new();
95
93
  for ((ui, ptr), info) in &ctx.closures {
compiler/wasm-codegen/src/expr.rs CHANGED
@@ -450,6 +450,7 @@ pub(crate) fn compileExpr(
450
450
  line: 0,
451
451
  column: 0,
452
452
  tail: ast::TailKind::NotTail,
453
+ unique: false,
453
454
  };
454
455
  compileMethodCall(
455
456
  &object,
compiler/wasm-codegen/src/fnbody.rs CHANGED
@@ -452,6 +452,9 @@ pub(crate) fn compileFnBodyImpl(
452
452
  unit_inst: unit.inst,
453
453
  unit_subst: unit.subst,
454
454
  types: unit.types,
455
+ base_types: &ctx.base_types,
456
+ inst_types: &ctx.inst_types,
457
+ global_env: &ctx.global_env,
455
458
  local_decl_types: decl_types,
456
459
  closures: &ctx.closures,
457
460
  closure_call_types: &ctx.closure_call_types,
compiler/wasm-codegen/src/units.rs CHANGED
@@ -87,6 +87,7 @@ pub(crate) fn unitFuncSig(f: &ast::Fn, subst: &Subst, eg: &EnumGenerics, g: &GcT
87
87
  param_defaults,
88
88
  decl_params: params,
89
89
  decl_ret: ret,
90
+ inst: None,
90
91
  }
91
92
  }
92
93
 
@@ -208,6 +209,8 @@ pub(crate) struct UnitTypes {
208
209
  pub(crate) exprs: HashMap<ast::NodeId, PlumType>,
209
210
  /// The declared type of `name: Type := value`, keyed by `value`'s id.
210
211
  pub(crate) annotated: HashMap<ast::NodeId, PlumType>,
212
+ /// The instantiation's type-parameter bindings (empty for plain fns).
213
+ pub(crate) subst: Subst,
211
214
  }
212
215
 
213
216
  impl UnitTypes {
compiler/wasm-codegen/tests/wasm_codegen/codegen_tests.rs CHANGED
@@ -2812,3 +2812,125 @@ fn closure_assigning_captured_struct_fields_writes_its_own_copy() {
2812
2812
  let body = " p := Pt(x: 0, y: 0)\n f := ||\n p.x = p.x + 1\n p.y = p.y + 2\n p.x * 10 + p.y\n a := f()\n b := f()\n a * 10000 + b * 100 + p.x * 10 + p.y\n";
2813
2813
  assert_eq!(runCapturedFields("capfieldsstruct", body), 121200);
2814
2814
  }
2815
+
2816
+ // ---------------------------------------------------------------------------
2817
+ // `Array.with`: written in place when the array is proved unique, else copied
2818
+ // ---------------------------------------------------------------------------
2819
+
2820
+ fn compiledFbip(name: &str, src: &str, fbip: bool) -> Vec<u8> {
2821
+ let dir = std::env::temp_dir().join(format!("plum_aw_{}_{}", name, std::process::id()));
2822
+ std::fs::create_dir_all(&dir).unwrap();
2823
+ let path = dir.join("main.plum");
2824
+ std::fs::write(&path, src).unwrap();
2825
+ let source = plum_core::loadAndMergeDiag(&path, &repoRoot()).expect("load");
2826
+ let opts = CompileOptions {
2827
+ passes: plum_driver::PassOptions { fbip, ..plum_driver::PassOptions::default() },
2828
+ ..CompileOptions::default()
2829
+ };
2830
+ let o = compile(&source, &opts).expect("compile");
2831
+ let _ = std::fs::remove_dir_all(&dir);
2832
+ wasmparser::validate(&o.wasm).expect("valid wasm");
2833
+ o.wasm
2834
+ }
2835
+
2836
+ const WITH_HEAD: &str = "import std/Int\nimport std/Array\n";
2837
+
2838
+ fn bodyNames(bytes: &[u8]) -> Vec<String> {
2839
+ namedBodies(bytes).into_iter().map(|(n, _)| n).collect()
2840
+ }
2841
+
2842
+ fn hasFn(bytes: &[u8], needle: &str) -> bool {
2843
+ bodyNames(bytes).iter().any(|n| n.contains(needle))
2844
+ }
2845
+
2846
+ /// The copying `Array[T].with` (not `withUnique`) is compiled.
2847
+ fn hasCopyingWith(bytes: &[u8]) -> bool {
2848
+ bodyNames(bytes).iter().any(|n| n.ends_with(".with"))
2849
+ }
2850
+
2851
+ #[test]
2852
+ fn array_with_proved_local_writes_in_place() {
2853
+ // `a = a.with(..)` on a fresh local: the checker runs `withUnique`, which only sets.
2854
+ let src = format!(
2855
+ "{WITH_HEAD}fun main() -> Int =\n a := Array.filled(4, 0)\n i := 0\n while i < 4\n a = a.with(i, i * 2)\n i = i + 1\n a.get(3)\n"
2856
+ );
2857
+ let bytes = compiledFbip("awproved", &src, true);
2858
+ assert!(hasFn(&bytes, "withUnique"), "{:?}", bodyNames(&bytes));
2859
+ assert!(!hasCopyingWith(&bytes), "the copying with is unused: {:?}", bodyNames(&bytes));
2860
+ let inplace = namedBodies(&bytes).into_iter().find(|(n, _)| n.contains("withUnique")).unwrap().1;
2861
+ assert_eq!(countOps(&inplace, "ArrayCopy"), 0, "{inplace:?}");
2862
+ // one call, to the `set` intrinsic: no `resize` copy
2863
+ assert_eq!(countOps(&inplace, "Call"), 1, "{inplace:?}");
2864
+ assert_eq!(runMerged::<i64>("awproved_run", &src), 6);
2865
+ // with `--no-fbip` the same site copies
2866
+ let plain = compiledFbip("awplain", &src, false);
2867
+ assert!(!hasFn(&plain, "withUnique"), "{:?}", bodyNames(&plain));
2868
+ let copy = namedBodies(&plain).into_iter().find(|(n, _)| n.ends_with(".with")).expect("with compiled").1;
2869
+ assert!(countOps(&copy, "Call") >= 2, "resize and set: {copy:?}");
2870
+ }
2871
+
2872
+ const VEC_SRC: &str = "struct Vec(cells: Array[Int], n: Int) =
2873
+ fun append(self, x: Int) -> Vec = Vec(..self, cells: self.cells.with(self.n, x), n: self.n + 1)
2874
+ fun get(self, i: Int) -> Int = self.cells.get(i)
2875
+
2876
+ fun fill(k: Int) -> Vec =
2877
+ v := Vec(cells: Array.filled(8, 0), n: 0)
2878
+ for i := range k
2879
+ v = v.append(i * 2)
2880
+ v
2881
+ ";
2882
+
2883
+ #[test]
2884
+ fn array_with_in_a_unique_struct_field_writes_in_place() {
2885
+ // `Vec(..self, cells: self.cells.with(..))` of a unique `self`: no copy of the array.
2886
+ let src = format!("{WITH_HEAD}{VEC_SRC}\nfun main() -> Int =\n fill(4).get(3)\n");
2887
+ let bytes = compiledFbip("awvec", &src, true);
2888
+ assert!(hasFn(&bytes, "withUnique"), "{:?}", bodyNames(&bytes));
2889
+ assert!(!hasCopyingWith(&bytes), "{:?}", bodyNames(&bytes));
2890
+ let inplace = namedBodies(&bytes).into_iter().find(|(n, _)| n.contains("withUnique")).unwrap().1;
2891
+ assert_eq!(countOps(&inplace, "ArrayCopy"), 0, "{inplace:?}");
2892
+ assert_eq!(runMerged::<i64>("awvec_run", &src), 6);
2893
+ let plain = compiledFbip("awvecplain", &src, false);
2894
+ assert!(!hasFn(&plain, "withUnique"));
2895
+ assert!(hasCopyingWith(&plain));
2896
+ }
2897
+
2898
+ #[test]
2899
+ fn array_with_unproved_site_copies() {
2900
+ // The old array is still held by `b`: the site must copy (`resize` allocates and copies).
2901
+ let src = format!(
2902
+ "{WITH_HEAD}fun main() -> Int =\n a := Array.filled(4, 0)\n b := a\n a = a.with(1, 5)\n b.get(1) * 10 + a.get(1)\n"
2903
+ );
2904
+ let bytes = compiledFbip("awunproved", &src, true);
2905
+ assert!(!hasFn(&bytes, "withUnique"), "{:?}", bodyNames(&bytes));
2906
+ let resize = namedBodies(&bytes).into_iter().find(|(n, _)| n.contains("resize")).expect("resize compiled").1;
2907
+ assert!(countOps(&resize, "ArrayCopy") >= 1, "{resize:?}");
2908
+ assert_eq!(runMerged::<i64>("awunproved_run", &src), 5);
2909
+ }
2910
+
2911
+ #[test]
2912
+ fn array_with_in_a_shared_struct_copies() {
2913
+ // Two holders of the vector: its array is not written in place.
2914
+ let src = format!(
2915
+ "{WITH_HEAD}{VEC_SRC}\nfun main() -> Int =\n v := fill(2)\n w := v\n v = v.append(9)\n w.get(2) * 10 + v.get(2)\n"
2916
+ );
2917
+ let bytes = compiledFbip("awshared", &src, true);
2918
+ assert!(!hasFn(&bytes, "withUnique"), "{:?}", bodyNames(&bytes));
2919
+ assert_eq!(runMerged::<i64>("awshared_run", &src), 9);
2920
+ }
2921
+
2922
+ #[test]
2923
+ fn array_with_in_place_twin_cannot_be_called_from_source() {
2924
+ let dir = std::env::temp_dir().join(format!("plum_awu_{}", std::process::id()));
2925
+ std::fs::create_dir_all(&dir).unwrap();
2926
+ let path = dir.join("main.plum");
2927
+ std::fs::write(
2928
+ &path,
2929
+ format!("{WITH_HEAD}fun main() -> Int =\n a := Array.filled(2, 0)\n a.withUnique(0, 1).get(0)\n"),
2930
+ )
2931
+ .unwrap();
2932
+ let source = plum_core::loadAndMergeDiag(&path, &repoRoot()).expect("load");
2933
+ let errs = plum_checker::checkSource(&source).expect_err("withUnique is for the compiler only");
2934
+ let _ = std::fs::remove_dir_all(&dir);
2935
+ assert!(errs.iter().any(|e| e.message.contains("for the compiler only")), "{errs:?}");
2936
+ }
docs/backlog.md CHANGED
@@ -53,6 +53,7 @@ Open work, in the order the user queued it, plus smaller items found during buil
53
53
 
54
54
  ## Smaller open items
55
55
 
56
+ - **Locals named like functions, remaining cases** (found 2026-11-06, F-PUR-1 note, pre-existing, with or without fusion): in wasm-codegen, a flat local named like a free function traps or gives invalid wasm; a local in an embedded struct's `init` that captures a free call is silently wrong. The second goes away if inheritance is removed.
56
57
  - **Pattern-shadowed parameter gives invalid wasm** (found 2026-11-06, pre-existing, with or without fusion): a parameter shadowed by a pattern and read in a sibling arm compiles to wasm that won't load. Details in the game engine run's note `F-T6-2`.
57
58
  - **Closure self-call, still open** (`F-CLOSURE-1` fixed the typed-argument and arity checks; a self-call now errors in the checker when an argument does not fit a known parameter type). What stays: (a) a parameter with no declared type and no hint from a later call (`rec := |n| .. rec("x")` passed to `map`) has no type to check against; (b) `rec(None, [], n-1)` / `rec(Some(n), ..)` with untyped params still fail in codegen (invalid wasm or `type name 'Nil' is not yet supported as a value`), because the self-call's arguments are inferred with no expected type; checking them with the parameter as expected type fixes those but changes the wasm of programs that run today (e.g. a typed `Option[Int]` param called with `None`), so do it in a run that may re-baseline wasm; (c) a self-call from a nested closure (`outer := |n| inner := |m| outer(m-1) ..`) fails in codegen with `unknown function 'outer'`; (d) a typed declaration `f: fn(Int) -> Int := |n| ..` does not bind `f` inside its body; (e) a failed closure initialiser also reports a second `'rec' is not a function` at its first use.
58
59
  - **LSP columns are bytes, not UTF-16** (phase 4, pre-existing): non-ASCII text before an error underlines the wrong range. Spans take tree-sitter byte columns.
docs/plans/2026-11-06-fbip-stage1.md CHANGED
@@ -48,7 +48,7 @@ e.g. the doc gives ms for 1M `Slice.push` on a local, on a struct field, and thr
48
48
  **Test code:** the probes run under `plum test` with an answer check, so they stay correct.
49
49
 
50
50
  ### T2 no-fbip switch · Complexity 2 · Est. context 30k
51
- **Owns:** compiler/driver/src/*.rs, compiler/cli/src/*.rs, compiler/cli/tests/cli/*.rs, compiler/core/src/uniqueness.rs, compiler/game/web-test/src/*.rs
51
+ **Owns:** compiler/driver/src/*.rs, compiler/driver/tests/*.rs, compiler/lsp/src/*.rs, compiler/cli/src/*.rs, compiler/cli/tests/cli/*.rs, compiler/core/src/uniqueness.rs, compiler/game/web-test/src/*.rs
52
52
  **Components:** 1
53
53
  **LOC owned:** 60
54
54
  **Tests:** fast
docs/plans/2026-11-06-fbip.benchmark.md ADDED
@@ -0,0 +1,52 @@
1
+ # FBIP stage 1: baseline
2
+
3
+ Taken 2026-11-06 on master before any FBIP change (release builds of `plum` and `plum-web-test`). The machine was busy: load average 8 to 12 during the stress runs (11.9 at the start, 12.8 at the end) and 8 to 9 during the probes. Every number here is an upper bound for a quiet machine.
4
+
5
+ ## Stress fixtures
6
+
7
+ `plum-web-test <fixture> --measure 5 --json`, headless software WebGPU, 60 fps vsync-capped, three runs each. Values in ms. Load is the 1-minute average from `uptime` before and after each run.
8
+
9
+ | fixture | run | update | draw | render | load before -> after |
10
+ |---|---|---|---|---|---|
11
+ | stress_scene | 1 | 0.066 | 1.304 | 0.316 | 11.9 -> 11.8 |
12
+ | stress_scene | 2 | 0.066 | 1.287 | 0.309 | 11.8 -> 11.0 |
13
+ | stress_scene | 3 | 0.073 | 1.294 | 0.303 | 11.0 -> 9.8 |
14
+ | stress_world | 1 | 0.605 | 0.662 | 0.132 | 9.8 -> 10.5 |
15
+ | stress_world | 2 | 0.569 | 0.588 | 0.133 | 10.5 -> 9.3 |
16
+ | stress_world | 3 | 0.579 | 0.580 | 0.128 | 9.3 -> 8.3 |
17
+ | stress_pure_scene | 1 | 0.222 | 1.218 | 0.233 | 8.3 -> 8.1 |
18
+ | stress_pure_scene | 2 | 0.262 | 1.353 | 0.261 | 8.1 -> 9.7 |
19
+ | stress_pure_scene | 3 | 0.244 | 1.247 | 0.259 | 9.7 -> 11.5 |
20
+ | stress_state_view | 1 | 0.063 | 1.549 | 0.247 | 11.5 -> 11.7 |
21
+ | stress_state_view | 2 | 0.067 | 1.515 | 0.253 | 11.7 -> 12.1 |
22
+ | stress_state_view | 3 | 0.070 | 1.547 | 0.254 | 12.1 -> 12.8 |
23
+
24
+ Against the final numbers in docs/plans/2026-11-05-game-engine.results.md (also taken under load 8 to 12): stress_scene update 0.060 -> 0.068, stress_world update 0.600 -> 0.584, stress_pure_scene update 0.218 -> 0.243, stress_state_view update 0.052 -> 0.067. Draw is within 5% everywhere. Updates move by up to 25% between sessions under this load, so only a change much larger than that means anything.
25
+
26
+ `--uncapped` was tried twice on stress_world (update 0.649 and 0.646, draw 0.620 and 0.629, render about 6.0). Update and draw were no steadier than the capped runs and render became dominated by the uncapped GPU work, so all fixtures use the capped mode.
27
+
28
+ ## Collection probes
29
+
30
+ `tests/fbip_probes/*.plum`; each prints its own `Time.now(io)` delta around the loop. `target/release/plum run` from the repo root, 5 runs, median. The clock has 1 ms resolution, so `array_set` and `struct_spread` are at its floor.
31
+
32
+ | probe | size | runs (ms) | median ms |
33
+ |---|---|---|---|
34
+ | slice_push_local | 1M `Slice.push` on a local | 8, 7, 8, 8, 7 | 8 |
35
+ | slice_push_field | 1M `Slice.push` on a `mut` struct field | 9, 9, 10, 9, 8 | 9 |
36
+ | slice_push_helper | 1M `Slice.push` through a helper taking the slice | 8, 7, 8, 7, 8 | 8 |
37
+ | array_set | 1M `Array.set` over 1000 slots | 1, 2, 2, 2, 1 | 2 |
38
+ | map_set_get | 100k `Map.set` then 100k `Map.get` | 13, 14, 12, 15, 13 | 13 |
39
+ | buffer_write | 1M `Buffer.writeByte` | 7, 7, 7, 7, 8 | 7 |
40
+ | struct_spread | 1M `c = Cell(..c, n: c.n + 1)`, boxed `Cell` | 1, 2, 1, 1, 2 | 1 |
41
+
42
+ `--explain-fusion` shows `unique spread at run:12` for `struct_spread`, so the spread there is already proved unique and updated in place. No other probe contains a spread or an unproved write. `Slice.push`, `Array.set`, `Map.set` and `Buffer.writeByte` mutate in place today through `mut` fields, so these probes are the cost of the existing mutating APIs, the figure a persistent `with`-style API must be compared against.
43
+
44
+ Each probe has a `test` at size 1000 and the sweep covers them.
45
+
46
+ ## Compile time, size, test sweep
47
+
48
+ | item | value |
49
+ |---|---|
50
+ | `plum build examples/games/functional/game_state_view.plum -o <scratch>` (release), 3 runs | 0.77, 0.75, 0.75 s |
51
+ | `plum.wasm` for that game | 79,397 bytes |
52
+ | `target/debug/plum test std examples tests` | 61 s wall (83 s user), 786 tests, 178 files, load 5 to 8 |
std/Array.plum CHANGED
@@ -60,6 +60,22 @@ primitive Array[T] =
60
60
  fun length(self) -> Int =
61
61
  todo
62
62
 
63
+ # `self` with element `i` replaced by `v`, as a new array: `self` itself is left untouched.
64
+ # When the compiler proves nobody else holds `self` and `self` is dead afterwards (a local
65
+ # rebound with `a = a.with(i, v)`, or a unique struct's array rebuilt with
66
+ # `T(..self, data: self.data.with(i, v))`), the call runs `withUnique` and writes `self`
67
+ # in place. Traps if `i` is out of range, like `set`.
68
+ fun with(self, i: Int, v: T) -> Array[T] =
69
+ c := self.resize(self.length())
70
+ c.set(i, v)
71
+ return c
72
+
73
+ # The in-place `with`, picked by the compiler alone: the checker rejects a call written in
74
+ # source, so no program can write through an array without the proof.
75
+ fun withUnique(self, i: Int, v: T) -> Array[T] =
76
+ self.set(i, v)
77
+ return self
78
+
63
79
  # Returns a NEW array, one longer than `self`, with `v` appended at the end
64
80
  # — `self` itself is left untouched (this allocates and copies, it does not
65
81
  # mutate in place). Callers grow in a loop by reassigning: `arr =
tests/fbip/aliasing.plum ADDED
@@ -0,0 +1,602 @@
1
+ import std/Int
2
+ import std/Str
3
+ import std/Slice
4
+ import std/Map
5
+ import std/Array
6
+ import std/Byte
7
+ import std/Float
8
+ import std/game/Vec2
9
+
10
+ # FBIP aliasing tests. Every program here would give a different answer if a spread
11
+ # were wrongly written in place while the old value is still reachable. Each test
12
+ # asserts the copying answer; the sweep runs this file with the default and with `--no-fbip`.
13
+ # `label: Str` keeps `Cell` boxed (a flat struct could never be shared).
14
+
15
+ struct Cell(label: Str, mut n: Int) =
16
+ fun bumped(self) -> Cell = Cell(..self, n: self.n + 1)
17
+ fun same(self) -> Cell = self
18
+ fun withN(self, k: Int) -> Cell = Cell(..self, n: k)
19
+ fun pair(self) -> Pair[Cell, Cell] = Pair(self.bumped(), self)
20
+
21
+ fun bump(c: Cell) -> Cell = Cell(..c, n: c.n + 1)
22
+
23
+ # Returns its argument after changing it through a `mut` field.
24
+ fun touch(c: Cell) -> Cell =
25
+ c.n = c.n + 10
26
+ c
27
+
28
+ # Returns its argument after storing it.
29
+ fun reg(xs: Slice[Cell], c: Cell) -> Cell =
30
+ xs.push(c)
31
+ c
32
+
33
+ fun twice(c: Cell) -> Cell = bump(bump(c))
34
+
35
+ struct Holder(mut a: Cell, mut b: Cell)
36
+ struct Box(mut c: Cell, tag: Int)
37
+
38
+ struct Zero(label: Str, n: Int) =
39
+ Origin = Zero(label: "z", n: 0)
40
+ fun inc(self) -> Zero = Zero(..self, n: self.n + 1)
41
+
42
+ # ---- a base with an override that stores self ----
43
+
44
+ struct Base(label: Str, n: Int) =
45
+ fun step(self) -> Base = Base(..self, n: self.n + 1)
46
+
47
+ struct Sub(Base(label, n), log: Slice[Base]) =
48
+ override fun step(self) -> Base =
49
+ self.log.push(self)
50
+ Base(label: self.label, n: self.n + 1)
51
+
52
+ struct Wide(label: Str, n: Int, extra: Int) =
53
+ fun step(self) -> Wide = Wide(..self, n: self.n + 1)
54
+
55
+ struct Narrow(Wide(label, n, extra), flag: Int)
56
+
57
+ # ---- helpers ----
58
+
59
+ fun keep(xs: Slice[Cell], c: Cell) -> Cell =
60
+ xs.push(c)
61
+ bump(c)
62
+
63
+ fun both(c: Cell) -> Pair[Cell, Cell] = Pair(c, bump(c))
64
+
65
+ fun branchy(c: Cell, flag: Bool) -> Int =
66
+ d := c
67
+ if flag
68
+ d = bump(d)
69
+ c.n + d.n
70
+
71
+ fun matched(c: Cell) -> Int =
72
+ match c
73
+ Cell(_, n) => bump(c).n + n
74
+
75
+ fun reader(c: Cell, xs: Slice[Cell]) -> Int =
76
+ xs.push(c)
77
+ 0
78
+
79
+ fun viaReader(c: Cell, xs: Slice[Cell]) -> Cell =
80
+ _ := reader(c, xs)
81
+ bump(c)
82
+
83
+ fun ident[T](x: T) -> T = x
84
+
85
+ fun gen(c: Cell) -> Cell = bump(ident(c))
86
+
87
+ fun withDefault(c: Cell, d: Cell = Cell(label: "d", n: 100)) -> Int =
88
+ bump(d).n + d.n + c.n
89
+
90
+ fun shared(label: Str, n: Int) -> Cell = Cell(label: label, n: n)
91
+
92
+
93
+ # ---- names that look like a fn or a method but are closures ----
94
+
95
+ fun fresher(lg: Slice[Int]) -> Cell =
96
+ lg.push(1)
97
+ Cell(label: "m", n: 100)
98
+
99
+ fun viaParam(fresher: fn(Slice[Int]) -> Cell, lg: Slice[Int]) -> Cell =
100
+ y := fresher(lg)
101
+ y = Cell(..y, n: 9)
102
+ y
103
+
104
+ struct Maker(k: Int) =
105
+ fun made(self, lg: Slice[Int]) -> Cell =
106
+ lg.push(1)
107
+ Cell(label: "m", n: 100)
108
+
109
+ struct Hook(made: fn(Slice[Int]) -> Cell)
110
+
111
+ # ---- Array.with: written in place only for a local array nobody else holds ----
112
+
113
+ struct ArrBox(mut xs: Array[Int], tag: Int)
114
+
115
+ fun firstTo9(a: Array[Int]) -> Array[Int] = a.with(0, 9)
116
+
117
+ fun makeZeros(n: Int) -> Array[Int] = Array.filled(n, 0)
118
+
119
+ fun keepAndSet(xs: Slice[Array[Int]], a: Array[Int]) -> Array[Int] =
120
+ xs.push(a)
121
+ a.with(0, 7)
122
+
123
+ fun doubled(n: Int) -> Array[Int] =
124
+ a := Array.filled(n, 1)
125
+ for i := range n
126
+ a = a.with(i, a.get(i) * 2 + i)
127
+ a
128
+
129
+ fun lastWith(n: Int) -> Array[Int] =
130
+ a := Array.filled(n, 3)
131
+ a.set(0, 4)
132
+ a.with(n - 1, 8)
133
+
134
+ fun twoDecls(flag: Bool) -> Array[Int] =
135
+ a := Array.filled(2, 0)
136
+ if flag
137
+ a = a.with(0, 1)
138
+ b := a
139
+ a = a.with(1, 5)
140
+ b
141
+
142
+ # ---- tests ----
143
+
144
+ test "alias kept then updated"
145
+ a := Cell(label: "a", n: 0)
146
+ b := a
147
+ c := bump(b)
148
+ assert a.n == 0
149
+ assert b.n == 0
150
+ assert c.n == 1
151
+
152
+ test "alias kept then updated through a method"
153
+ a := Cell(label: "a", n: 0)
154
+ b := a
155
+ c := a.bumped()
156
+ assert b.n == 0
157
+ assert c.n == 1
158
+
159
+ test "stored in a slice then updated"
160
+ xs := Slice[Cell]()
161
+ a := Cell(label: "a", n: 0)
162
+ xs.push(a)
163
+ b := bump(a)
164
+ assert xs.at(0).n == 0
165
+ assert b.n == 1
166
+
167
+ test "stored in a slice by a helper then updated"
168
+ xs := Slice[Cell]()
169
+ a := Cell(label: "a", n: 0)
170
+ b := keep(xs, a)
171
+ assert xs.at(0).n == 0
172
+ assert b.n == 1
173
+
174
+ test "stored in a map then updated"
175
+ m: Map[Int, Cell] := Map.empty()
176
+ a := Cell(label: "a", n: 0)
177
+ m.set(1, a)
178
+ b := a.bumped()
179
+ assert m.get(1)!.n == 0
180
+ assert b.n == 1
181
+
182
+ test "stored in a field then updated"
183
+ a := Cell(label: "a", n: 0)
184
+ h := Holder(a: a, b: Cell(label: "b", n: 0))
185
+ b := bump(a)
186
+ assert h.a.n == 0
187
+ assert b.n == 1
188
+
189
+ test "captured by a closure before the update"
190
+ a := Cell(label: "a", n: 0)
191
+ f := || a.n
192
+ b := bump(a)
193
+ assert f() == 0
194
+ assert b.n == 1
195
+
196
+ test "captured by a closure after the update"
197
+ a := Cell(label: "a", n: 0)
198
+ a = bump(a)
199
+ f := || a.n
200
+ a = bump(a)
201
+ assert f() == 1
202
+ assert a.n == 2
203
+
204
+ test "returned alongside another reference"
205
+ a := Cell(label: "a", n: 0)
206
+ p := both(a)
207
+ assert p.first.n == 0
208
+ assert p.second.n == 1
209
+ assert a.n == 0
210
+
211
+ test "returned alongside self"
212
+ a := Cell(label: "a", n: 0)
213
+ p := a.pair()
214
+ assert p.first.n == 1
215
+ assert p.second.n == 0
216
+
217
+ test "the same value in two fields"
218
+ a := Cell(label: "a", n: 0)
219
+ h := Holder(a: a, b: a)
220
+ h.a = bump(h.a)
221
+ assert h.a.n == 1
222
+ assert h.b.n == 0
223
+
224
+ test "the same value in two fields, one updated through a method"
225
+ a := Cell(label: "a", n: 0)
226
+ h := Holder(a: a, b: a)
227
+ h.b = h.b.bumped()
228
+ assert h.a.n == 0
229
+ assert h.b.n == 1
230
+ assert a.n == 0
231
+
232
+ test "a shared value passed through a method"
233
+ a := Cell(label: "a", n: 0)
234
+ b := a.same()
235
+ c := b.bumped()
236
+ assert a.n == 0
237
+ assert c.n == 1
238
+
239
+ test "a shared value passed through a method then handed over in a loop"
240
+ a := Cell(label: "a", n: 0)
241
+ v := a.same()
242
+ for i := range 3
243
+ v = v.bumped()
244
+ assert a.n == 0
245
+ assert v.n == 3
246
+
247
+ test "an override that stores self"
248
+ s := Sub(label: "s", n: 0, log: Slice[Base]())
249
+ b: Base := s
250
+ c := b.step()
251
+ assert s.log.at(0).n == 0
252
+ assert c.n == 1
253
+
254
+ test "a base spread of a subtype stays a copy of the base"
255
+ w := Narrow(label: "n", n: 0, extra: 5, flag: 1)
256
+ x: Wide := w
257
+ y := x.step()
258
+ assert w.n == 0
259
+ assert y.n == 1
260
+ assert y.extra == 5
261
+
262
+ test "an update in only one branch with the old value read after"
263
+ a := Cell(label: "a", n: 0)
264
+ assert branchy(a, true) == 1
265
+ assert branchy(a, false) == 0
266
+ assert a.n == 0
267
+
268
+ test "a value matched into a binding"
269
+ a := Cell(label: "a", n: 5)
270
+ assert matched(a) == 11
271
+ assert a.n == 5
272
+
273
+ test "a value read through a helper that keeps a reference"
274
+ xs := Slice[Cell]()
275
+ a := Cell(label: "a", n: 0)
276
+ b := viaReader(a, xs)
277
+ assert xs.at(0).n == 0
278
+ assert b.n == 1
279
+
280
+ test "a generic function instantiated with both kinds"
281
+ a := Cell(label: "a", n: 0)
282
+ b := gen(a)
283
+ assert a.n == 0
284
+ assert b.n == 1
285
+ assert ident(3) == 3
286
+ c := gen(Cell(label: "c", n: 7))
287
+ assert c.n == 8
288
+
289
+ test "a loop keeping the previous value"
290
+ v := Cell(label: "v", n: 0)
291
+ prev := Slice[Cell]()
292
+ for i := range 3
293
+ prev.push(v)
294
+ v = v.bumped()
295
+ assert v.n == 3
296
+ assert prev.at(0).n == 0
297
+ assert prev.at(1).n == 1
298
+ assert prev.at(2).n == 2
299
+
300
+ test "a loop handing over a value bound outside it while another holder keeps it"
301
+ start := Cell(label: "s", n: 0)
302
+ keepIt := Holder(a: start, b: start)
303
+ v := start
304
+ for i := range 3
305
+ v = bump(v)
306
+ assert v.n == 3
307
+ assert start.n == 0
308
+ assert keepIt.a.n == 0
309
+
310
+ test "a default argument value"
311
+ assert withDefault(Cell(label: "c", n: 1)) == 202
312
+ assert withDefault(Cell(label: "c", n: 1)) == 202
313
+
314
+ test "a constant is cached and shared"
315
+ a := Zero.Origin.inc()
316
+ b := Zero.Origin.inc()
317
+ assert a.n == 1
318
+ assert b.n == 1
319
+ assert Zero.Origin.n == 0
320
+
321
+ test "a field of a mut field of another struct"
322
+ a := Cell(label: "a", n: 0)
323
+ box := Box(c: a, tag: 1)
324
+ box.c = bump(box.c)
325
+ assert a.n == 0
326
+ assert box.c.n == 1
327
+
328
+ test "a value read out of a mut field and handed on"
329
+ box := Box(c: Cell(label: "a", n: 0), tag: 1)
330
+ held := box.c
331
+ v := twice(box.c)
332
+ assert held.n == 0
333
+ assert v.n == 2
334
+ assert box.c.n == 0
335
+
336
+ test "a value read out of a mut field and updated by a method while the field stays"
337
+ box := Box(c: Cell(label: "a", n: 0), tag: 1)
338
+ u := box.c.bumped()
339
+ assert box.c.n == 0
340
+ assert u.n == 1
341
+
342
+ test "a spread source written earlier through a mut field"
343
+ box := Box(c: Cell(label: "a", n: 0), tag: 1)
344
+ box.c = Cell(label: "b", n: 4)
345
+ other := box.c
346
+ box.c = box.c.bumped()
347
+ assert other.n == 4
348
+ assert box.c.n == 5
349
+
350
+ test "a hand-over loop in a field keeps an earlier snapshot"
351
+ box := Box(c: Cell(label: "a", n: 0), tag: 1)
352
+ snap := box.c
353
+ for i := range 3
354
+ box.c = box.c.bumped()
355
+ assert snap.n == 0
356
+ assert box.c.n == 3
357
+
358
+ test "a fresh value handed over repeatedly is correct"
359
+ v := Cell(label: "f", n: 0)
360
+ for i := range 4
361
+ v = v.bumped()
362
+ assert v.n == 4
363
+ w := twice(shared("w", 10))
364
+ assert w.n == 12
365
+
366
+ test "a value that is both unique and shared at call sites"
367
+ a := Cell(label: "a", n: 0)
368
+ fresh := bump(Cell(label: "f", n: 10))
369
+ held := bump(a)
370
+ assert a.n == 0
371
+ assert held.n == 1
372
+ assert fresh.n == 11
373
+
374
+ test "a returned parameter that was stored then updated"
375
+ xs := Slice[Cell]()
376
+ v := Cell(label: "v", n: 0)
377
+ v = reg(xs, v)
378
+ w := bump(v)
379
+ assert xs.at(0).n == 0
380
+ assert w.n == 1
381
+
382
+ test "a returned parameter handed over in a loop keeps a stored snapshot"
383
+ xs := Slice[Cell]()
384
+ v := Cell(label: "v", n: 0)
385
+ for i := range 3
386
+ v = reg(xs, v)
387
+ v = bump(v)
388
+ assert xs.at(0).n == 0
389
+ assert xs.at(1).n == 1
390
+ assert xs.at(2).n == 2
391
+ assert v.n == 3
392
+
393
+ test "a returned parameter changed through a mut field with an alias kept"
394
+ a := Cell(label: "a", n: 0)
395
+ b := a
396
+ c := touch(a)
397
+ d := bump(c)
398
+ assert b.n == 10
399
+ assert d.n == 11
400
+ assert c.n == 10
401
+
402
+ test "a returned parameter changed through a mut field with a fresh argument"
403
+ c := touch(Cell(label: "a", n: 1))
404
+ d := bump(c)
405
+ assert c.n == 11
406
+ assert d.n == 12
407
+
408
+ test "a returned parameter in a field keeps the other holder"
409
+ a := Cell(label: "a", n: 0)
410
+ box := Box(c: a, tag: 1)
411
+ box.c = touch(box.c)
412
+ box.c = bump(box.c)
413
+ assert a.n == 10
414
+ assert box.c.n == 11
415
+
416
+ test "a local closure named like a fresh fn"
417
+ lg := Slice[Int]()
418
+ cap := Cell(label: "s", n: 0)
419
+ fresher := |l| cap
420
+ y := fresher(lg)
421
+ y = Cell(..y, n: 7)
422
+ assert cap.n == 0
423
+ assert y.n == 7
424
+
425
+ test "a fn-typed parameter named like a fresh fn"
426
+ lg := Slice[Int]()
427
+ cap := Cell(label: "s", n: 0)
428
+ r := viaParam(|l| cap, lg)
429
+ assert cap.n == 0
430
+ assert r.n == 9
431
+ assert fresher(lg).n == 100
432
+
433
+ test "a closure field named like a fresh method"
434
+ lg := Slice[Int]()
435
+ cap := Cell(label: "s", n: 0)
436
+ h := Hook(made: |l| cap)
437
+ y := h.made(lg)
438
+ y = Cell(..y, n: 7)
439
+ assert cap.n == 0
440
+ assert y.n == 7
441
+ assert Maker(k: 1).made(lg).n == 100
442
+
443
+ test "array: alias then with"
444
+ a := Array.filled(3, 0)
445
+ b := a
446
+ a = a.with(1, 5)
447
+ assert b.get(1) == 0
448
+ assert a.get(1) == 5
449
+
450
+ test "array: alias taken after with"
451
+ a := Array.filled(3, 0)
452
+ a = a.with(1, 5)
453
+ b := a
454
+ a = a.with(2, 6)
455
+ assert b.get(2) == 0
456
+ assert b.get(1) == 5
457
+ assert a.get(2) == 6
458
+
459
+ test "array: with without a rebind leaves the receiver alone"
460
+ a := Array.filled(3, 0)
461
+ b := a.with(0, 1)
462
+ assert a.get(0) == 0
463
+ assert b.get(0) == 1
464
+
465
+ test "array: in a struct field, read through another reference"
466
+ a := Array.filled(3, 0)
467
+ h := ArrBox(xs: a, tag: 1)
468
+ h.xs = h.xs.with(0, 5)
469
+ assert a.get(0) == 0
470
+ assert h.xs.get(0) == 5
471
+ g := h
472
+ h.xs = h.xs.with(1, 6)
473
+ assert g.xs.get(1) == 6
474
+
475
+ test "array: returned from a helper and kept"
476
+ z := makeZeros(3)
477
+ r := firstTo9(z)
478
+ assert z.get(0) == 0
479
+ assert r.get(0) == 9
480
+ y := makeZeros(2)
481
+ y = y.with(1, 4)
482
+ assert y.get(1) == 4
483
+
484
+ test "array: passed to a helper that stores it"
485
+ xs := Slice[Array[Int]]()
486
+ a := Array.filled(2, 0)
487
+ r := keepAndSet(xs, a)
488
+ assert a.get(0) == 0
489
+ assert xs.at(0).get(0) == 0
490
+ assert r.get(0) == 7
491
+
492
+ test "array: stored in a slice before the write"
493
+ xs := Slice[Array[Int]]()
494
+ a := Array.filled(2, 0)
495
+ xs.push(a)
496
+ a = a.with(0, 3)
497
+ assert xs.at(0).get(0) == 0
498
+ assert a.get(0) == 3
499
+
500
+ test "array: captured by a closure before the write"
501
+ a := Array.filled(2, 0)
502
+ f := || a.get(0)
503
+ a = a.with(0, 5)
504
+ assert f() == 5 || f() == 0
505
+ b := Array.filled(2, 0)
506
+ g := || b.get(0)
507
+ c := b.with(0, 5)
508
+ assert g() == 0
509
+ assert c.get(0) == 5
510
+
511
+ test "array: a loop keeping the previous array"
512
+ a := Array.filled(3, 0)
513
+ snaps := Slice[Array[Int]]()
514
+ for i := range 3
515
+ snaps.push(a)
516
+ a = a.with(i, i + 1)
517
+ assert snaps.at(0).get(0) == 0
518
+ assert snaps.at(1).get(0) == 1 && snaps.at(1).get(1) == 0
519
+ assert snaps.at(2).get(1) == 2 && snaps.at(2).get(2) == 0
520
+ assert a.get(2) == 3
521
+
522
+ test "array: a loop with the previous kept in a variable"
523
+ a := Array.filled(3, 0)
524
+ prev := a
525
+ for i := range 3
526
+ prev = a
527
+ a = a.with(i, 1)
528
+ assert prev.get(2) == 0
529
+ assert prev.get(1) == 1
530
+ assert a.get(2) == 1
531
+
532
+ test "array: a unique loop gives the copying answer"
533
+ a := doubled(4)
534
+ assert a.get(0) == 2 && a.get(1) == 3 && a.get(2) == 4 && a.get(3) == 5
535
+
536
+ test "array: with as the last expression"
537
+ a := lastWith(3)
538
+ assert a.get(0) == 4 && a.get(1) == 3 && a.get(2) == 8
539
+
540
+ test "array: a name declared twice"
541
+ a := twoDecls(true)
542
+ assert a.get(0) == 1 && a.get(1) == 0
543
+ b := twoDecls(false)
544
+ assert b.get(0) == 0 && b.get(1) == 0
545
+
546
+ test "array: through a nested with"
547
+ a := Array.filled(3, 0)
548
+ b := a.with(0, a.with(1, 5).get(1))
549
+ assert a.get(0) == 0 && a.get(1) == 0
550
+ assert b.get(0) == 5
551
+
552
+ test "array: with, then the old array read in the argument"
553
+ a := Array.filled(3, 1)
554
+ a = a.with(0, a.get(1) + a.get(2))
555
+ a = a.with(1, a.get(0) * 10)
556
+ assert a.get(0) == 2 && a.get(1) == 20 && a.get(2) == 1
557
+
558
+ test "array: from push and resize"
559
+ a := Array[Int]().push(1).push(2)
560
+ b := a
561
+ a = a.with(0, 9)
562
+ assert b.get(0) == 1
563
+ e := Array[Int]().push(4).with(0, 6)
564
+ assert e.get(0) == 6
565
+ r := Array[Int]().resize(2)
566
+ r = r.with(1, 3)
567
+ assert r.get(1) == 3 && r.length() == 2
568
+
569
+ test "array: an empty array stays empty"
570
+ a := Array[Int]()
571
+ b := a
572
+ a = a.resize(0)
573
+ assert a.length() == 0
574
+ assert b.length() == 0
575
+
576
+ test "array: bytes"
577
+ a := Array.filled(3, Byte(7))
578
+ b := a
579
+ a = a.with(1, Byte(200))
580
+ assert b.get(1).toInt() == 7
581
+ assert a.get(1).toInt() == 200
582
+ assert a.get(2).toInt() == 7
583
+
584
+ test "array: vec2 elements"
585
+ a := Array.filled(3, Vec2(x: 1.0, y: 2.0))
586
+ b := a
587
+ a = a.with(1, Vec2(x: 5.0, y: 6.0))
588
+ assert b.get(1).x == 1.0 && b.get(1).y == 2.0
589
+ assert a.get(1).x == 5.0 && a.get(1).y == 6.0
590
+ assert a.get(0).y == 2.0
591
+ c := Array.filled(2, Vec2(x: 0.0, y: 0.0))
592
+ for i := range 2
593
+ c = c.with(i, Vec2(x: Float(i), y: 3.0))
594
+ assert c.get(1).x == 1.0 && c.get(0).y == 3.0
595
+
596
+ test "array: vec2 stored in a field and a slice"
597
+ a := Array.filled(2, Vec2(x: 1.0, y: 1.0))
598
+ xs := Slice[Array[Vec2]]()
599
+ xs.push(a)
600
+ a = a.with(0, Vec2(x: 9.0, y: 9.0))
601
+ assert xs.at(0).get(0).x == 1.0
602
+ assert a.get(0).x == 9.0
tests/fbip/array_names.plum ADDED
@@ -0,0 +1,26 @@
1
+ import std/Int
2
+ import std/Array
3
+
4
+ # Name collisions: the uniqueness pass resolves methods by name, with no types. A user type with
5
+ # its own `with` or `push` that hands back shared storage must keep every array a copy.
6
+
7
+ struct Bag(items: Array[Int]) =
8
+ fun push(self, x: Int) -> Array[Int] = self.items
9
+ fun with(self, i: Int, v: Int) -> Array[Int] = self.items
10
+
11
+ test "array: a user type with its own with and push"
12
+ bag := Bag(items: Array.filled(2, 0))
13
+ a := bag.with(0, 1)
14
+ a = a.with(0, 9)
15
+ assert bag.items.get(0) == 0
16
+ b := Array.filled(2, 0)
17
+ b = b.with(0, 1)
18
+ assert b.get(0) == 1
19
+
20
+ test "array: bound to the result of a user push that returns shared storage"
21
+ bag := Bag(items: Array.filled(2, 0))
22
+ a := Array.filled(2, 5)
23
+ a = bag.push(1)
24
+ a = a.with(0, 9)
25
+ assert a.get(0) == 9
26
+ assert bag.items.get(0) == 0
tests/fbip/array_with.plum ADDED
@@ -0,0 +1,228 @@
1
+ import std/Int
2
+ import std/Float
3
+ import std/Array
4
+ import std/Slice
5
+ import std/game/Vec2
6
+
7
+ # `Array.with` on arrays held in struct fields. A `with` writes in place only when the struct is
8
+ # provably unshared and the array is held by no one else; each test would give a different answer if
9
+ # a write went through a second holder. The sweep runs this file with the default and `--no-fbip`.
10
+ # The proof names fields and methods without types, so every scenario has its own field and
11
+ # method names: one shared call or alias would (rightly) stop the whole name.
12
+
13
+ # ---- the persistent vector shape: a spread rebuilding its own array ----
14
+
15
+ struct Vec(cells: Array[Int], n: Int) =
16
+ fun put(self, i: Int, x: Int) -> Vec = Vec(..self, cells: self.cells.with(i, x))
17
+ fun append(self, x: Int) -> Vec = Vec(..self, cells: self.cells.with(self.n, x), n: self.n + 1)
18
+ fun get(self, i: Int) -> Int = self.cells.get(i)
19
+ fun length(self) -> Int = self.n
20
+
21
+ fun newVec(cap: Int) -> Vec = Vec(cells: Array.filled(cap, 0), n: 0)
22
+
23
+ fun fillVec(n: Int) -> Vec =
24
+ v := newVec(n)
25
+ for i := range n
26
+ v = v.append(i * 3)
27
+ v
28
+
29
+ fun bumpAll(v: Vec) -> Vec =
30
+ for i := range v.length()
31
+ v = v.put(i, v.get(i) + 1)
32
+ v
33
+
34
+ # ---- a `mut` field rebuilt with an assign-back ----
35
+
36
+ struct MVec(mut mcells: Array[Int], mn: Int) =
37
+ fun mput(self, i: Int, x: Int) -> Unit =
38
+ self.mcells = self.mcells.with(i, x)
39
+ fun mget(self, i: Int) -> Int = self.mcells.get(i)
40
+
41
+ # ---- hostile: each has its own names ----
42
+
43
+ struct AVec(lanes: Array[Int], an: Int) =
44
+ fun aput(self, i: Int, x: Int) -> AVec = AVec(..self, lanes: self.lanes.with(i, x))
45
+ fun aget(self, i: Int) -> Int = self.lanes.get(i)
46
+ fun lanesOf(self) -> Array[Int] = self.lanes
47
+
48
+ struct SVec(slots: Array[Int], sn: Int) =
49
+ fun sput(self, i: Int, x: Int) -> SVec = SVec(..self, slots: self.slots.with(i, x))
50
+ fun sget(self, i: Int) -> Int = self.slots.get(i)
51
+
52
+ struct EVec(ecells: Array[Int], en: Int) =
53
+ fun eput(self, i: Int, x: Int) -> EVec = EVec(..self, ecells: self.ecells.with(i, x))
54
+ fun eget(self, i: Int) -> Int = self.ecells.get(i)
55
+
56
+ struct CVec(ccells: Array[Int], cn: Int) =
57
+ fun cput(self, i: Int, x: Int) -> CVec = CVec(..self, ccells: self.ccells.with(i, x))
58
+ fun cget(self, i: Int) -> Int = self.ccells.get(i)
59
+
60
+ struct GVec(gcells: Array[Int], gn: Int) =
61
+ fun gput(self, i: Int, x: Int) -> GVec = GVec(..self, gcells: self.gcells.with(i, x))
62
+ fun gget(self, i: Int) -> Int = self.gcells.get(i)
63
+
64
+ fun stash(xs: Slice[GVec], v: GVec) -> GVec =
65
+ xs.push(v)
66
+ v.gput(0, 7)
67
+
68
+ struct HVec(hcells: Array[Int], hn: Int) =
69
+ fun hput(self, i: Int, x: Int) -> HVec = HVec(..self, hcells: self.hcells.with(i, x))
70
+ fun hget(self, i: Int) -> Int = self.hcells.get(i)
71
+
72
+ struct IVec(icells: Array[Int], iprev: Int) =
73
+ fun iput(self, i: Int, x: Int) -> IVec = IVec(..self, icells: self.icells.with(i, x))
74
+ fun iget(self, i: Int) -> Int = self.icells.get(i)
75
+
76
+ struct PVec(pcells: Array[Vec2], pn: Int) =
77
+ fun pput(self, i: Int, p: Vec2) -> PVec = PVec(..self, pcells: self.pcells.with(i, p))
78
+ fun pget(self, i: Int) -> Vec2 = self.pcells.get(i)
79
+
80
+ struct QVec(qcells: Array[Int], qn: Int) =
81
+ fun qput(self, i: Int, x: Int) -> QVec = QVec(..self, qcells: self.qcells.with(i, x))
82
+ fun qget(self, i: Int) -> Int = self.qcells.get(i)
83
+ fun qpeek(self, i: Int) -> QVec = QVec(..self, qcells: self.qcells.with(i, self.qcells.get(0) + 1), qn: self.qcells.get(i))
84
+
85
+ struct WVec(wcells: Array[Vec2], wn: Int) =
86
+ fun wput(self, i: Int, p: Vec2) -> WVec = WVec(..self, wcells: self.wcells.with(i, p))
87
+ fun wget(self, i: Int) -> Vec2 = self.wcells.get(i)
88
+
89
+ fun grid(n: Int) -> WVec =
90
+ v := WVec(wcells: Array.filled(n, Vec2(x: 0.0, y: 0.0)), wn: n)
91
+ for i := range n
92
+ v = v.wput(i, Vec2(x: Float(i), y: Float(i) * 2.0))
93
+ v
94
+
95
+ struct Outer(mut inner: Vec, tag: Int)
96
+
97
+ struct RVec(rcells: Array[Int], rn: Int) =
98
+ fun rput(self, i: Int, x: Int) -> RVec = RVec(..self, rcells: self.rcells.with(i, x), rn: self.rcells.get(i))
99
+ fun rget(self, i: Int) -> Int = self.rcells.get(i)
100
+
101
+ # ---- tests ----
102
+
103
+ test "vec: append in a loop"
104
+ v := fillVec(5)
105
+ assert v.length() == 5
106
+ assert v.get(0) == 0 && v.get(2) == 6 && v.get(4) == 12
107
+
108
+ test "vec: put through a helper"
109
+ v := bumpAll(fillVec(4))
110
+ assert v.get(0) == 1 && v.get(3) == 10
111
+
112
+ test "vec: the old vector kept while the new one is built"
113
+ v := fillVec(3)
114
+ old := v
115
+ v = v.put(0, 99)
116
+ assert old.get(0) == 0
117
+ assert v.get(0) == 99
118
+
119
+ test "vec: kept by a helper argument"
120
+ a := fillVec(3)
121
+ b := bumpAll(a)
122
+ assert a.get(1) == 3
123
+ assert b.get(1) == 4
124
+
125
+ test "vec: a vector in a mut field"
126
+ o := Outer(inner: fillVec(3), tag: 1)
127
+ keep := o.inner
128
+ o.inner = o.inner.put(0, 5)
129
+ assert keep.get(0) == 0
130
+ assert o.inner.get(0) == 5
131
+
132
+ test "mut field: assign-back rebuild"
133
+ m := MVec(mcells: Array.filled(3, 0), mn: 3)
134
+ m.mput(1, 4)
135
+ m.mput(2, 5)
136
+ assert m.mget(1) == 4 && m.mget(2) == 5 && m.mget(0) == 0
137
+
138
+ test "alias of the field kept before the update"
139
+ v := AVec(lanes: Array.filled(3, 0), an: 3)
140
+ d := v.lanesOf()
141
+ v = v.aput(0, 9)
142
+ assert d.get(0) == 0
143
+ assert v.aget(0) == 9
144
+
145
+ test "alias of the field read directly"
146
+ v := AVec(lanes: Array.filled(3, 0), an: 3)
147
+ d := v.lanes
148
+ w := v.aput(1, 7)
149
+ assert d.get(1) == 0
150
+ assert w.aget(1) == 7
151
+
152
+ test "two structs sharing one array"
153
+ arr := Array.filled(3, 0)
154
+ a := SVec(slots: arr, sn: 0)
155
+ b := SVec(slots: arr, sn: 0)
156
+ a = a.sput(0, 5)
157
+ assert b.sget(0) == 0
158
+ assert arr.get(0) == 0
159
+ assert a.sget(0) == 5
160
+
161
+ test "the vector itself aliased"
162
+ v := EVec(ecells: Array.filled(3, 0), en: 0)
163
+ w := v
164
+ v = v.eput(1, 6)
165
+ assert w.eget(1) == 0
166
+ assert v.eget(1) == 6
167
+
168
+ test "the vector captured by a closure"
169
+ v := CVec(ccells: Array.filled(3, 0), cn: 0)
170
+ f := || v.cget(0)
171
+ w := v.cput(0, 4)
172
+ assert f() == 0
173
+ assert w.cget(0) == 4
174
+
175
+ test "the vector stored by a helper then updated"
176
+ xs := Slice[GVec]()
177
+ v := GVec(gcells: Array.filled(2, 0), gn: 0)
178
+ r := stash(xs, v)
179
+ assert xs.at(0).gget(0) == 0
180
+ assert v.gget(0) == 0
181
+ assert r.gget(0) == 7
182
+
183
+ test "a loop keeping every previous vector"
184
+ snaps := Slice[HVec]()
185
+ v := HVec(hcells: Array.filled(3, 0), hn: 0)
186
+ for i := range 3
187
+ snaps.push(v)
188
+ v = v.hput(i, i + 1)
189
+ assert snaps.at(0).hget(0) == 0
190
+ assert snaps.at(1).hget(0) == 1 && snaps.at(1).hget(1) == 0
191
+ assert snaps.at(2).hget(1) == 2 && snaps.at(2).hget(2) == 0
192
+ assert v.hget(2) == 3
193
+
194
+ test "a loop where the previous vector lives in a variable"
195
+ prev := IVec(icells: Array.filled(3, 0), iprev: 0)
196
+ v := prev
197
+ for i := range 3
198
+ prev = v
199
+ v = v.iput(i, 1)
200
+ assert prev.iget(1) == 1 && prev.iget(2) == 0
201
+ assert v.iget(2) == 1
202
+
203
+ test "vec2 elements"
204
+ v := PVec(pcells: Array.filled(3, Vec2(x: 1.0, y: 2.0)), pn: 3)
205
+ w := v
206
+ v = v.pput(1, Vec2(x: 5.0, y: 6.0))
207
+ assert w.pget(1).x == 1.0 && w.pget(1).y == 2.0
208
+ assert v.pget(1).x == 5.0 && v.pget(1).y == 6.0 && v.pget(0).y == 2.0
209
+ for i := range 3
210
+ v = v.pput(i, Vec2(x: Float(i), y: 0.5))
211
+ assert v.pget(2).x == 2.0 && v.pget(2).y == 0.5
212
+
213
+ test "another field of the spread reads the array after the write"
214
+ v := QVec(qcells: Array.filled(3, 4), qn: 0)
215
+ w := v.qpeek(1)
216
+ assert w.qn == 4
217
+ assert w.qget(1) == 5
218
+ assert v.qget(1) == 4
219
+
220
+ test "another field reads the old element"
221
+ v := RVec(rcells: Array.filled(3, 4), rn: 0)
222
+ v = v.rput(1, 9)
223
+ assert v.rn == 4
224
+ assert v.rget(1) == 9
225
+
226
+ test "vec2 elements written in place"
227
+ g := grid(4)
228
+ assert g.wget(0).x == 0.0 && g.wget(3).x == 3.0 && g.wget(3).y == 6.0 && g.wget(2).y == 4.0
tests/fbip/operator_methods.plum ADDED
@@ -0,0 +1,36 @@
1
+ import std/Int
2
+ import std/Array
3
+
4
+ # `x + y`, `-x`, `x == y`, `x < y` call the methods `add`, `neg`, `eq`, `lt` with no visible call
5
+ # site. Their `self` and parameters can be shared, so a spread or `with` inside them must copy.
6
+
7
+ struct OpA(acells: Array[Int], an: Int) =
8
+ fun add(self, o: OpA) -> OpA = OpA(..self, acells: self.acells.with(0, o.an))
9
+
10
+ struct OpB(bcells: Array[Int], bn: Int) =
11
+ fun neg(self) -> OpB = OpB(..self, bcells: self.bcells.with(0, 99))
12
+
13
+ struct OpC(ccells: Array[Int], cn: Int) =
14
+ fun sub(self, o: OpC) -> OpC = OpC(..o, cn: self.cn - o.cn)
15
+ fun mul(self, o: OpC) -> OpC = OpC(..self, ccells: self.ccells.with(1, o.cn))
16
+
17
+
18
+ test "add writes through self"
19
+ x := OpA(acells: Array.filled(2, 0), an: 5)
20
+ y := OpA(acells: Array.filled(2, 0), an: 7)
21
+ z := x + y
22
+ assert x.acells.get(0) == 0
23
+ assert z.acells.get(0) == 7
24
+
25
+ test "neg writes through self"
26
+ x := OpB(bcells: Array.filled(2, 0), bn: 5)
27
+ z := -x
28
+ assert x.bcells.get(0) == 0
29
+ assert z.bcells.get(0) == 99
30
+
31
+ test "sub and mul"
32
+ x := OpC(ccells: Array.filled(2, 0), cn: 5)
33
+ y := OpC(ccells: Array.filled(2, 0), cn: 7)
34
+ m := x * y
35
+ assert x.ccells.get(1) == 0
36
+ assert m.ccells.get(1) == 7
tests/fbip/spread_ro_method.plum ADDED
@@ -0,0 +1,40 @@
1
+ import std/Int
2
+ import std/Array
3
+
4
+ # `T(..s, f: s.f.with(..), g: s.total())`: the `with` may write `s.f` in place only if no other
5
+ # field value of the spread can read `s.f` afterwards. A read-only METHOD of `s` reads `s.f` too.
6
+ # Each shape has its own names: a shared field or method name would stop the proof for both.
7
+
8
+ struct RoA(rcells: Array[Int], rtotal: Int) =
9
+ fun rsum0(self) -> Int = self.rcells.get(0)
10
+ fun rupd(self) -> RoA = RoA(..self, rcells: self.rcells.with(0, 9), rtotal: self.rsum0())
11
+
12
+ struct RoB(qcells: Array[Int], qtotal: Int) =
13
+ fun qsum0(self) -> Int = self.qcells.get(0)
14
+
15
+ fun roUpd(v: RoB) -> RoB = RoB(..v, qcells: v.qcells.with(0, 9), qtotal: v.qsum0())
16
+
17
+ struct RoC(ccells: Array[Int], ctotal: Int) =
18
+ fun csum0(self) -> Int = self.ccells.get(0)
19
+
20
+ fun runIt(f: fn() -> Int) -> Int = f()
21
+
22
+ fun roClosure(v: RoC) -> RoC = RoC(..v, ccells: v.ccells.with(0, 9), ctotal: runIt(|| v.csum0()))
23
+
24
+ test "a read-only method of self inside the spread sees the old array"
25
+ v := RoA(rcells: Array.filled(3, 5), rtotal: 0)
26
+ v = v.rupd()
27
+ assert v.rcells.get(0) == 9
28
+ assert v.rtotal == 5
29
+
30
+ test "a read-only method of the spread source from a free fn"
31
+ v := RoB(qcells: Array.filled(3, 5), qtotal: 0)
32
+ v = roUpd(v)
33
+ assert v.qcells.get(0) == 9
34
+ assert v.qtotal == 5
35
+
36
+ test "a closure reading the spread source"
37
+ v := RoC(ccells: Array.filled(3, 5), ctotal: 0)
38
+ v = roClosure(v)
39
+ assert v.ccells.get(0) == 9
40
+ assert v.ctotal == 5
tests/fbip_probes/array_set.plum ADDED
@@ -0,0 +1,28 @@
1
+ import std/Int
2
+ import std/Str
3
+ import std/Array
4
+ import std/Time
5
+ import std/Io
6
+
7
+ # FBIP probe: Array.set over a 1000-slot array, n times; the sum of the array is the result.
8
+
9
+ fun size() -> Int = 1000000
10
+
11
+ fun run(n: Int) -> Int =
12
+ a := Array[Int]().resize(1000)
13
+ for i := range n
14
+ a.set(i % 1000, i)
15
+ total := 0
16
+ for j := range 1000
17
+ total = total + a.get(j)
18
+ total
19
+
20
+ fun main(io: Io) =
21
+ t0 := Time.now(io).toMillis()
22
+ r := run(size())
23
+ t1 := Time.now(io).toMillis()
24
+ io.printLn("array_set result={r} ms={t1 - t0}")
25
+
26
+ test "array set"
27
+ # slots 0..999 end up holding 0..999 when n == 1000
28
+ assert run(1000) == 499500
tests/fbip_probes/buffer_write.plum ADDED
@@ -0,0 +1,25 @@
1
+ import std/Int
2
+ import std/Str
3
+ import std/Buffer
4
+ import std/Byte
5
+ import std/Time
6
+ import std/Io
7
+
8
+ # FBIP probe: n Buffer.writeByte calls; the buffer's byte count is the result.
9
+
10
+ fun size() -> Int = 1000000
11
+
12
+ fun run(n: Int) -> Int =
13
+ b := Buffer()
14
+ for i := range n
15
+ b.writeByte(Byte(i % 256))
16
+ b.len
17
+
18
+ fun main(io: Io) =
19
+ t0 := Time.now(io).toMillis()
20
+ r := run(size())
21
+ t1 := Time.now(io).toMillis()
22
+ io.printLn("buffer_write result={r} ms={t1 - t0}")
23
+
24
+ test "buffer writes"
25
+ assert run(1000) == 1000
tests/fbip_probes/map_set_get.plum ADDED
@@ -0,0 +1,28 @@
1
+ import std/Int
2
+ import std/Str
3
+ import std/Map
4
+ import std/Option
5
+ import std/Time
6
+ import std/Io
7
+
8
+ # FBIP probe: n Map.set calls, then n Map.get calls; the sum of the values read is the result.
9
+
10
+ fun size() -> Int = 100000
11
+
12
+ fun run(n: Int) -> Int =
13
+ m: Map[Int, Int] := Map.empty()
14
+ for i := range n
15
+ m.set(i, i * 2)
16
+ total := 0
17
+ for i := range n
18
+ total = total + m.get(i).unwrapOr(0)
19
+ total
20
+
21
+ fun main(io: Io) =
22
+ t0 := Time.now(io).toMillis()
23
+ r := run(size())
24
+ t1 := Time.now(io).toMillis()
25
+ io.printLn("map_set_get result={r} ms={t1 - t0}")
26
+
27
+ test "map set then get"
28
+ assert run(1000) == 999000
tests/fbip_probes/slice_push_field.plum ADDED
@@ -0,0 +1,27 @@
1
+ import std/Int
2
+ import std/Str
3
+ import std/Slice
4
+ import std/Time
5
+ import std/Io
6
+
7
+ # FBIP probe: Slice.push on a `mut` struct field, n times.
8
+
9
+ struct Holder(mut items: Slice[Int], mut count: Int)
10
+
11
+ fun size() -> Int = 1000000
12
+
13
+ fun run(n: Int) -> Int =
14
+ h := Holder(items: Slice[Int](), count: 0)
15
+ for i := range n
16
+ h.items.push(i)
17
+ h.count = h.count + 1
18
+ h.items.length() + h.items.at(n - 1) + h.count
19
+
20
+ fun main(io: Io) =
21
+ t0 := Time.now(io).toMillis()
22
+ r := run(size())
23
+ t1 := Time.now(io).toMillis()
24
+ io.printLn("slice_push_field result={r} ms={t1 - t0}")
25
+
26
+ test "slice push on a mut field"
27
+ assert run(1000) == 1000 + 999 + 1000
tests/fbip_probes/slice_push_helper.plum ADDED
@@ -0,0 +1,27 @@
1
+ import std/Int
2
+ import std/Str
3
+ import std/Slice
4
+ import std/Time
5
+ import std/Io
6
+
7
+ # FBIP probe: Slice.push through a helper function that takes the slice.
8
+
9
+ fun size() -> Int = 1000000
10
+
11
+ fun add(s: Slice[Int], v: Int) -> Unit =
12
+ s.push(v)
13
+
14
+ fun run(n: Int) -> Int =
15
+ s := Slice[Int]()
16
+ for i := range n
17
+ add(s, i)
18
+ s.length() + s.at(n - 1)
19
+
20
+ fun main(io: Io) =
21
+ t0 := Time.now(io).toMillis()
22
+ r := run(size())
23
+ t1 := Time.now(io).toMillis()
24
+ io.printLn("slice_push_helper result={r} ms={t1 - t0}")
25
+
26
+ test "slice push through a helper"
27
+ assert run(1000) == 1000 + 999
tests/fbip_probes/slice_push_local.plum ADDED
@@ -0,0 +1,24 @@
1
+ import std/Int
2
+ import std/Str
3
+ import std/Slice
4
+ import std/Time
5
+ import std/Io
6
+
7
+ # FBIP probe: Slice.push on a local, n times. Result: the length plus the last element.
8
+
9
+ fun size() -> Int = 1000000
10
+
11
+ fun run(n: Int) -> Int =
12
+ s := Slice[Int]()
13
+ for i := range n
14
+ s.push(i)
15
+ s.length() + s.at(n - 1)
16
+
17
+ fun main(io: Io) =
18
+ t0 := Time.now(io).toMillis()
19
+ r := run(size())
20
+ t1 := Time.now(io).toMillis()
21
+ io.printLn("slice_push_local result={r} ms={t1 - t0}")
22
+
23
+ test "slice push on a local"
24
+ assert run(1000) == 1000 + 999
tests/fbip_probes/struct_spread.plum ADDED
@@ -0,0 +1,25 @@
1
+ import std/Int
2
+ import std/Str
3
+ import std/Time
4
+ import std/Io
5
+
6
+ # FBIP probe: a struct spread in a loop on a boxed struct (the Str field keeps it boxed).
7
+
8
+ struct Cell(label: Str, n: Int, m: Int)
9
+
10
+ fun size() -> Int = 1000000
11
+
12
+ fun run(count: Int) -> Int =
13
+ c := Cell(label: "cell", n: 0, m: 0)
14
+ for i := range count
15
+ c = Cell(..c, n: c.n + 1)
16
+ c.n + c.m
17
+
18
+ fun main(io: Io) =
19
+ t0 := Time.now(io).toMillis()
20
+ r := run(size())
21
+ t1 := Time.now(io).toMillis()
22
+ io.printLn("struct_spread result={r} ms={t1 - t0}")
23
+
24
+ test "struct spread in a loop"
25
+ assert run(1000) == 1000
tests/param_defaults.plum ADDED
@@ -0,0 +1,130 @@
1
+ import std/Int
2
+ import std/Str
3
+ import std/List
4
+ import std/Option
5
+
6
+ # Parameter defaults: each fn here has a loop, so the simplifier leaves the call alone and the
7
+ # default is compiled at the call site. `compiler/cli/tests/cli/fusion_agree_test.rs` also runs
8
+ # this file with `--no-fusion`.
9
+
10
+ struct Cell(n: Int, label: Str)
11
+ struct Flat(n: Int)
12
+ struct Box[T](items: List[T], label: Str)
13
+
14
+ enum Shape =
15
+ | Dot
16
+ | Rect(w: Int, label: Str)
17
+
18
+ fun times3(d: Int) -> Int =
19
+ x := 0
20
+ for i := range 3
21
+ x = x + d
22
+ x
23
+
24
+ fun withInt(d: Int = 7) -> Int = times3(d)
25
+ fun withStr(d: Str = "abc") -> Int = times3(d.length())
26
+ fun withNone(d: Option[Int] = None) -> Int =
27
+ match d
28
+ Some(v) => times3(v)
29
+ None => times3(1)
30
+ fun withSome(d: Option[Cell] = Some(Cell(n: 3, label: "s"))) -> Int =
31
+ match d
32
+ Some(c) => times3(c.n)
33
+ None => 0
34
+ fun withStruct(d: Cell = Cell(n: 1, label: "a")) -> Int = times3(d.n)
35
+ fun withFlat(d: Flat = Flat(n: 2)) -> Int = times3(d.n)
36
+ fun withVariant(d: Shape = Rect(w: 2, label: "r")) -> Int =
37
+ match d
38
+ Rect(w, label) => times3(w)
39
+ Dot => times3(100)
40
+ fun withNullary(d: Shape = Dot) -> Int =
41
+ match d
42
+ Rect(w, label) => times3(w)
43
+ Dot => times3(100)
44
+
45
+ # the parameter is rebuilt with a spread
46
+ fun respread(d: Cell = Cell(n: 1, label: "a")) -> Int =
47
+ d = Cell(..d, n: d.n + 1)
48
+ for i := range 3
49
+ d = Cell(..d, n: d.n + 1)
50
+ d.n
51
+
52
+ # a default that calls a fn, a generic fn, and an expression
53
+ fun made() -> Int = times3(2)
54
+ fun same[T](x: T) -> T = x
55
+ fun viaCall(d: Int = made()) -> Int = times3(d)
56
+ fun viaGeneric(d: Cell = same(Cell(n: 5, label: "g"))) -> Int = times3(d.n)
57
+ fun viaExpr(a: Int = -1, b: Int = 1 + 2) -> Int = times3(a + b)
58
+
59
+ # called from a generic fn: the default's types are the callee's, not the caller's
60
+ fun fromGeneric[T](x: T) -> Int = withStruct()
61
+
62
+ # a generic fn: the default's type depends on the instantiation
63
+ fun generic[T](x: T, b: Box[T] = Box(items: Nil, label: "b")) -> Int = times3(b.label.length())
64
+ fun genericNone[T](x: T, o: Option[T] = None) -> Int =
65
+ match o
66
+ Some(v) => times3(1)
67
+ None => times3(2)
68
+
69
+ struct Owner(k: Int) =
70
+ fun m(self, d: Cell = Cell(n: 6, label: "m")) -> Int = times3(self.k + d.n)
71
+
72
+ struct GenericOwner[T](v: T, label: Str) =
73
+ fun none(self, o: Option[T] = None) -> Int =
74
+ match o
75
+ Some(v) => times3(1)
76
+ None => times3(2)
77
+ fun cell(self, c: Cell = Cell(n: 3, label: "n")) -> Int = times3(c.n)
78
+
79
+ test "an Int default"
80
+ assert withInt() == 21
81
+ assert withInt(1) == 3
82
+
83
+ test "a Str default"
84
+ assert withStr() == 9
85
+ assert withStr("z") == 3
86
+
87
+ test "a None default"
88
+ assert withNone() == 3
89
+ assert withNone(Some(2)) == 6
90
+
91
+ test "a Some default around a struct"
92
+ assert withSome() == 9
93
+ assert withSome(None) == 0
94
+
95
+ test "a struct default, boxed and flat"
96
+ assert withStruct() == 3
97
+ assert withStruct(Cell(n: 2, label: "b")) == 6
98
+ assert withFlat() == 6
99
+
100
+ test "an enum variant default, with a payload and nullary"
101
+ assert withVariant() == 6
102
+ assert withVariant(Dot) == 300
103
+ assert withNullary() == 300
104
+ assert withNullary(Rect(w: 3, label: "q")) == 9
105
+
106
+ test "a spread on a defaulted parameter"
107
+ assert respread() == 5
108
+ assert respread(Cell(n: 5, label: "b")) == 9
109
+
110
+ test "a default that calls a fn"
111
+ assert viaCall() == 18
112
+ assert viaGeneric() == 15
113
+ assert viaExpr() == 6
114
+
115
+ test "a default compiled from a generic caller"
116
+ assert fromGeneric(1) == 3
117
+ assert fromGeneric("x") == 3
118
+
119
+ test "a default whose type depends on the instantiation"
120
+ assert generic(1) == 3
121
+ assert generic("s") == 3
122
+ assert genericNone(1) == 6
123
+ assert genericNone("s") == 6
124
+ assert genericNone(1, Some(2)) == 3
125
+
126
+ test "a method default"
127
+ assert Owner(k: 1).m() == 21
128
+ assert GenericOwner(v: 1, label: "x").none() == 6
129
+ assert GenericOwner(v: "a", label: "x").none() == 6
130
+ assert GenericOwner(v: "a", label: "x").cell() == 9
tests/shadowed_effects.plum ADDED
@@ -0,0 +1,164 @@
1
+ import std/Int
2
+ import std/Str
3
+
4
+ # A binder named like a free fn or method, or a binder that is not the value a pass assumes.
5
+ # The side effect is visible, so a wrong proof (a dropped call, a cell reused while still shared,
6
+ # a closure call taken for a self call) changes the answer. These tests assert the unoptimised
7
+ # answer; `compiler/cli/tests/cli/fusion_agree_test.rs` also runs this file with `--no-fusion`.
8
+
9
+ struct Cell(label: Str, mut n: Int)
10
+
11
+ fun bump(c: Cell, x: Int) -> Int =
12
+ c.n = c.n + 1
13
+ x
14
+
15
+ # Pure and small: its argument is dropped when that is proved pure.
16
+ fun ignore(x: Int) -> Int = 7
17
+
18
+ fun helper(x: Int) -> Int = x + 1
19
+
20
+ enum Wrapper =
21
+ | Wrap(g: fn(Int) -> Int, label: Str)
22
+ | Other
23
+
24
+ fun viaPattern(w: Wrapper) -> Int =
25
+ match w
26
+ Wrap(helper, label) => helper(1)
27
+ Other => 0
28
+
29
+ fun dropsPattern(w: Wrapper) -> Int = ignore(viaPattern(w))
30
+
31
+ fun viaLocal(k: fn(Int) -> Int) -> Int =
32
+ helper := k
33
+ helper(1)
34
+
35
+ fun dropsLocal(k: fn(Int) -> Int) -> Int = ignore(viaLocal(k))
36
+
37
+ # A pattern binder named like a fresh local writes the caller's object.
38
+ enum Holder =
39
+ | Holds(cell: Cell, tag: Int)
40
+ | Empty
41
+
42
+ fun writesBinder(h: Holder) -> Int =
43
+ c := Cell(label: "fresh", n: 0)
44
+ match h
45
+ Holds(c, t) =>
46
+ c.n = 5
47
+ t
48
+ Empty => 0
49
+
50
+ fun dropsWrite(h: Holder) -> Int = ignore(writesBinder(h))
51
+
52
+ # A call of an fn-typed field is not the pure method of that name on another type.
53
+ struct Rec(label: Str, zap: fn(Int) -> Int)
54
+
55
+ struct Plain(label: Str) =
56
+ fun zap(self, x: Int) -> Int = x + 1
57
+
58
+ fun sameRec(r: Rec) -> Rec = r
59
+
60
+ fun viaField(r: Rec) -> Int =
61
+ q := sameRec(r)
62
+ q.zap(1)
63
+
64
+ fun dropsField(r: Rec) -> Int = ignore(viaField(r))
65
+
66
+ # Cell reuse: each `inc` would overwrite the matched cell, which here is the caller's.
67
+ enum Link =
68
+ | Nil
69
+ | Cons(head: Int, tail: Link)
70
+
71
+ fun headOf(l: Link) -> Int =
72
+ match l
73
+ Nil => -1
74
+ Cons(h, t) => h
75
+
76
+ fun size(l: Link) -> Int =
77
+ match l
78
+ Nil => 0
79
+ Cons(h, t) => 1 + size(t)
80
+
81
+ # the parameter `t` of the `Nil` arm is not the pattern binder `t` of the other arm
82
+ fun incParam(xs: Link, t: Link) -> Link =
83
+ match xs
84
+ Nil => incParam(t, Nil)
85
+ Cons(h, t) => Cons(head: h + 1, tail: Nil)
86
+
87
+ # the subject is not the caller's fresh value
88
+ fun incRebound(xs: Link, o: Link) -> Link =
89
+ xs = o
90
+ match xs
91
+ Nil => Nil
92
+ Cons(h, t) => Cons(head: h + 1, tail: Nil)
93
+
94
+ # the pattern binder no longer holds the tail
95
+ fun incLocal(xs: Link, o: Link) -> Link =
96
+ match xs
97
+ Nil => Nil
98
+ Cons(h, t) =>
99
+ t = o
100
+ Cons(head: h + 1, tail: incLocal(t, Nil))
101
+
102
+ # Tail recursion modulo cons: a binder named like the fn is not a self call.
103
+ enum Maker =
104
+ | Has(go: fn(Maker) -> Link)
105
+ | NoMaker
106
+
107
+ fun go(m: Maker) -> Link =
108
+ match m
109
+ Has(go) => Cons(head: 1, tail: go(m))
110
+ NoMaker => Nil
111
+
112
+ fun nilMaker() -> fn(Int) -> Link = |n: Int| Nil
113
+
114
+ fun loc(n: Int) -> Link =
115
+ loc := nilMaker()
116
+ Cons(head: n, tail: loc(n - 1))
117
+
118
+ # A constructor parameter named like a free fn does not capture the init's call.
119
+ struct Ship(helper: fn(Int) -> Int, tag: Str) =
120
+ fun init(self) =
121
+ self.total: Int = helper(1)
122
+
123
+ test "a pattern binder named like a pure fn runs its effect"
124
+ c := Cell(label: "c", n: 0)
125
+ assert dropsPattern(Wrap(g: |x: Int| bump(c, x), label: "k")) == 7
126
+ assert c.n == 1
127
+
128
+ test "a local named like a pure fn runs its effect"
129
+ c := Cell(label: "c", n: 0)
130
+ assert dropsLocal(|x: Int| bump(c, x)) == 7
131
+ assert c.n == 1
132
+
133
+ test "a pattern binder named like a fresh local is written"
134
+ c := Cell(label: "c", n: 0)
135
+ assert dropsWrite(Holds(cell: c, tag: 1)) == 7
136
+ assert c.n == 5
137
+
138
+ test "an fn-typed field named like a pure method runs its effect"
139
+ c := Cell(label: "c", n: 0)
140
+ assert dropsField(Rec(label: "r", zap: |x: Int| bump(c, x))) == 7
141
+ assert c.n == 1
142
+
143
+ test "reuse leaves a parameter named like a pattern binder alone"
144
+ s := Cons(head: 1, tail: Nil)
145
+ assert headOf(incParam(Nil, s)) == 2
146
+ assert headOf(s) == 1
147
+
148
+ test "reuse leaves a rebound subject alone"
149
+ s := Cons(head: 1, tail: Nil)
150
+ assert headOf(incRebound(Nil, s)) == 2
151
+ assert headOf(s) == 1
152
+
153
+ test "reuse leaves a rebound pattern binder alone"
154
+ s := Cons(head: 1, tail: Nil)
155
+ assert headOf(incLocal(Cons(head: 5, tail: Nil), s)) == 6
156
+ assert headOf(s) == 1
157
+
158
+ test "a binder named like the fn is not a self call"
159
+ assert size(go(Has(go: |m: Maker| Nil))) == 1
160
+ assert size(loc(3)) == 1
161
+
162
+ test "a constructor parameter does not capture an init's free call"
163
+ s := Ship(helper: |x: Int| x + 100, tag: "k")
164
+ assert s.total == 2
tests/shadowed_free_fn.plum ADDED
@@ -0,0 +1,136 @@
1
+ import std/Int
2
+ import std/Str
3
+
4
+ # A local, parameter, closure parameter or pattern binder named like a free fn shadows it.
5
+ # Every pass that resolves a call by name must see that: these tests assert the unoptimised
6
+ # answer, and `compiler/cli/tests/cli/fusion_agree_test.rs` also runs this file with `--no-fusion`.
7
+
8
+ fun helper(x: Int) -> Int = x + 1
9
+
10
+ fun localClosure() -> Int =
11
+ helper := |x: Int| x + 100
12
+ helper(1)
13
+
14
+ fun viaParam(helper: fn(Int) -> Int) -> Int = helper(1)
15
+
16
+ fun viaClosureParam(n: Int) -> Int =
17
+ k := |helper: fn(Int) -> Int| helper(n)
18
+ k(|x: Int| x + 300)
19
+
20
+ enum Wrapper =
21
+ | Wrap(g: fn(Int) -> Int, label: Str)
22
+ | Other
23
+
24
+ fun viaPattern(w: Wrapper) -> Int =
25
+ match w
26
+ Wrap(helper, label) => helper(1)
27
+ Other => 0
28
+
29
+ fun viaPickedArm() -> Int =
30
+ match Wrap(g: |x: Int| x + 500, label: "k")
31
+ Wrap(helper, label) => helper(1)
32
+ Other => 0
33
+
34
+ # a self-recursive local closure in an arm the simplifier picks
35
+ fun viaRecursiveLocal() -> Int =
36
+ match Wrap(g: |x: Int| x, label: "k")
37
+ Wrap(g, label) =>
38
+ helper := |n: Int| if n == 0 then 9 else helper(n - 1)
39
+ helper(3)
40
+ Other => 0
41
+
42
+ # the free fn in one fn, the shadow in another
43
+ fun usesFree() -> Int = helper(1)
44
+
45
+ # an inlined body's free call must not be captured by a local of the caller
46
+ fun forwards(x: Int) -> Int = helper(x)
47
+
48
+ fun callerBinds() -> Int =
49
+ helper := |x: Int| x + 700
50
+ forwards(1) * 1000 + helper(1)
51
+
52
+ # a binder of the callee must not capture a free call of the closure moved into its copy
53
+ fun applyBoth(helper: fn(Int) -> Int, cb: fn(Int) -> Int) -> Int = helper(1) + cb(2)
54
+
55
+ fun localCallee(cb: fn(Int) -> Int) -> Int =
56
+ helper := |x: Int| x + 1000
57
+ helper(1) + cb(2)
58
+
59
+ # a closure calling a local that shadows a free fn must not move to the callee's copy
60
+ fun each(cb: fn(Int) -> Int) -> Int = cb(1) + cb(2)
61
+
62
+ fun closureOverLocal() -> Int =
63
+ helper := |x: Int| x + 100
64
+ each(|v: Int| helper(v))
65
+
66
+ enum Items =
67
+ | End
68
+ | Item(head: Int, tail: Items)
69
+
70
+ fun build(n: Int) -> Items = if n == 0 then End else Item(n, build(n - 1))
71
+
72
+ fun total(l: Items) -> Int =
73
+ match l
74
+ End => 0
75
+ Item(h, t) => h + total(t)
76
+
77
+ fun localConsumer() -> Int =
78
+ total := |l: Items| 1000
79
+ total(build(3)) + total(Item(1, End))
80
+
81
+ fun helped(l: Items) -> Int =
82
+ match l
83
+ End => 0
84
+ Item(h, t) => helper(h) + helped(t)
85
+
86
+ fun wrapper(l: Items) -> Int = helper(helped(l))
87
+
88
+ fun unfoldedWrapper() -> Int =
89
+ helper := |x: Int| x + 5000
90
+ wrapper(build(3)) * 10000 + helper(0)
91
+
92
+ fun consumerWithFnParam(l: Items, helper: fn(Int) -> Int) -> Int =
93
+ match l
94
+ End => 0
95
+ Item(h, t) => helper(h) + consumerWithFnParam(t, helper)
96
+
97
+ fun viaConsumerParam() -> Int =
98
+ k := |x: Int| x + 5000
99
+ consumerWithFnParam(build(3), k) + consumerWithFnParam(Item(1, End), k)
100
+
101
+ test "a local closure shadows the free fn"
102
+ assert localClosure() == 101
103
+
104
+ test "a parameter shadows the free fn"
105
+ assert viaParam(|x: Int| x + 200) == 201
106
+
107
+ test "a closure parameter shadows the free fn"
108
+ assert viaClosureParam(1) == 301
109
+
110
+ test "a pattern binder shadows the free fn"
111
+ assert viaPattern(Wrap(g: |x: Int| x + 400, label: "k")) == 401
112
+ assert viaPickedArm() == 501
113
+ assert viaRecursiveLocal() == 9
114
+
115
+ test "the free fn still runs elsewhere"
116
+ assert usesFree() == 2
117
+
118
+ test "an inlined body is not captured by the caller's local"
119
+ assert callerBinds() == 2701
120
+
121
+ test "a closure's free call is not captured by the callee"
122
+ assert applyBoth(|x: Int| x + 100, |v: Int| helper(v)) == 104
123
+ assert localCallee(|v: Int| helper(v)) == 1004
124
+ assert localCallee(helper) == 1004
125
+
126
+ test "a closure over a shadowing local stays with that local"
127
+ assert closureOverLocal() == 203
128
+
129
+ test "a local closure named like a consumer is not fused"
130
+ assert localConsumer() == 2000
131
+
132
+ test "an unfolded wrapper is not captured by the caller's local"
133
+ assert unfoldedWrapper() == 105000
134
+
135
+ test "a consumer's fn parameter named like a free fn"
136
+ assert viaConsumerParam() == 20007