1use std::collections::HashMap;
5
6use source_map::{BaseSpan, Nullable, SpanWithSource};
7
8use crate::{
9 context::{
10 environment::Label, invocation::InvocationContext, CallCheckingBehavior,
11 ClosedOverReferencesInScope, Environment, LocalInformation, Scope,
12 },
13 events::{
14 application::ApplicationInput, apply_events, ApplicationResult, Event, FinalEvent,
15 RootReference,
16 },
17 features::{functions::ClosedOverVariables, operations::CanonicalEqualityAndInequality},
18 types::{
19 calling::{CallingContext, CallingDiagnostics},
20 properties::get_properties_on_single_type,
21 substitute, Constructor, ObjectNature, PolyNature, SubstitutionArguments, TypeStore,
22 },
23 CheckingData, Constant, Type, TypeId, VariableId,
24};
25
26#[derive(Clone, Copy)]
28pub enum IterationBehavior<'a, A: crate::ASTImplementation> {
29 While(&'a A::MultipleExpression<'a>),
30 DoWhile(&'a A::MultipleExpression<'a>),
32 For {
33 initialiser: &'a Option<A::ForStatementInitiliser<'a>>,
34 condition: &'a Option<A::MultipleExpression<'a>>,
35 afterthought: &'a Option<A::MultipleExpression<'a>>,
36 },
37 ForIn {
38 lhs: &'a A::VariableField<'a>,
39 rhs: &'a A::MultipleExpression<'a>,
40 },
41 ForOf {
42 lhs: &'a A::VariableField<'a>,
43 rhs: &'a A::Expression<'a>,
44 },
45}
46
47#[allow(clippy::needless_pass_by_value)]
48pub fn synthesise_iteration<T: crate::ReadFromFS, A: crate::ASTImplementation>(
49 behavior: IterationBehavior<A>,
50 label: Label,
51 environment: &mut Environment,
52 checking_data: &mut CheckingData<T, A>,
53 loop_body: impl FnOnce(&mut Environment, &mut CheckingData<T, A>),
54 position: SpanWithSource,
55) {
56 let application_input = ApplicationInput {
57 this_value: crate::types::calling::ThisValue::UseParent,
58 call_site: position,
59 max_inline: checking_data.options.max_inline_count,
60 };
61
62 match behavior {
63 IterationBehavior::While(condition) => {
64 let (condition, result, ..) = environment.new_lexical_environment_fold_into_parent(
65 Scope::Iteration { label },
66 checking_data,
67 |environment, checking_data| {
68 let condition = A::synthesise_multiple_expression(
69 condition,
70 TypeId::ANY_TYPE,
71 environment,
72 checking_data,
73 );
74
75 let values = super::narrowing::narrow_based_on_expression_into_vec(
76 condition,
77 false,
78 environment,
79 &mut checking_data.types,
80 );
81
82 crate::utilities::notify!("{:?}", values);
83
84 environment.info.narrowed_values = values;
85
86 add_loop_described_break_event(
88 condition,
89 position,
90 &mut environment.info.events,
91 );
92
93 loop_body(environment, checking_data);
95
96 condition
97 },
98 );
99
100 let (
101 LocalInformation { variable_current_value, current_properties, events, .. },
102 closes_over,
103 ) = result.unwrap();
104
105 let loop_info = Values {
106 variable_values: variable_current_value,
107 _properties_values: current_properties,
108 };
109
110 let fixed_iterations = calculate_result_of_loop(
111 condition,
112 None,
113 environment,
114 &checking_data.types,
115 &loop_info,
116 );
117
118 let mut diagnostics = CallingDiagnostics::default();
119
120 run_iteration_block(
121 IterationKind::Condition { under: fixed_iterations.ok(), postfix_condition: false },
122 &events,
123 &application_input,
124 RunBehavior::References(closes_over),
125 &mut SubstitutionArguments::new_arguments_for_use_in_loop(),
126 environment,
127 &mut InvocationContext::new_empty(),
128 &mut diagnostics,
129 &mut checking_data.types,
130 );
131
132 diagnostics
133 .append_to(CallingContext::Iteration, &mut checking_data.diagnostics_container);
134
135 }
140 IterationBehavior::DoWhile(condition) => {
141 let (condition, result, ..) = environment.new_lexical_environment_fold_into_parent(
143 Scope::Iteration { label },
144 checking_data,
145 |environment, checking_data| {
146 loop_body(environment, checking_data);
147
148 let condition = A::synthesise_multiple_expression(
149 condition,
150 TypeId::ANY_TYPE,
151 environment,
152 checking_data,
153 );
154
155 add_loop_described_break_event(
157 condition,
158 position,
159 &mut environment.info.events,
160 );
161
162 condition
163 },
164 );
165
166 let (
167 LocalInformation { variable_current_value, current_properties, events, .. },
168 closes_over,
169 ) = result.unwrap();
170
171 let loop_info = Values {
172 variable_values: variable_current_value,
173 _properties_values: current_properties,
174 };
175
176 let fixed_iterations = calculate_result_of_loop(
177 condition,
178 None,
179 environment,
180 &checking_data.types,
181 &loop_info,
182 );
183
184 let mut diagnostics = CallingDiagnostics::default();
185
186 run_iteration_block(
187 IterationKind::Condition { under: fixed_iterations.ok(), postfix_condition: true },
188 &events,
189 &application_input,
190 RunBehavior::References(closes_over),
191 &mut SubstitutionArguments::new_arguments_for_use_in_loop(),
192 environment,
193 &mut InvocationContext::new_empty(),
194 &mut diagnostics,
195 &mut checking_data.types,
196 );
197
198 diagnostics
199 .append_to(CallingContext::Iteration, &mut checking_data.diagnostics_container);
200
201 }
205 IterationBehavior::For { initialiser, condition, afterthought } => {
206 let ((condition, result, dependent_variables), ..) = environment
208 .new_lexical_environment_fold_into_parent(
209 Scope::Block {},
210 checking_data,
211 |environment, checking_data| {
212 let dependent_variables_initial_values: HashMap<VariableId, TypeId> =
213 if let Some(initialiser) = initialiser {
214 A::synthesise_for_loop_initialiser(
215 initialiser,
216 environment,
217 checking_data,
218 );
219
220 environment
221 .variables
222 .values()
223 .map(|v| {
224 let id = v.get_id();
225 let end_value = environment
226 .info
227 .variable_current_value
228 .get(&id)
229 .expect("loop variable with no initial value");
230 (id, *end_value)
231 })
232 .collect()
233 } else {
234 Default::default()
235 };
236
237 let ((condition, dependent_variables), events, ..) = environment
238 .new_lexical_environment_fold_into_parent(
239 Scope::Iteration { label },
240 checking_data,
241 |environment, checking_data| {
242 let condition = if let Some(condition) = condition {
243 A::synthesise_multiple_expression(
244 condition,
245 TypeId::ANY_TYPE,
246 environment,
247 checking_data,
248 )
249 } else {
250 TypeId::TRUE
251 };
252
253 let values =
254 super::narrowing::narrow_based_on_expression_into_vec(
255 condition,
256 false,
257 environment,
258 &mut checking_data.types,
259 );
260
261 crate::utilities::notify!(
262 "Narrowed values in loop {:?}",
263 values
264 );
265 environment.info.narrowed_values = values;
266
267 add_loop_described_break_event(
269 condition,
270 position,
271 &mut environment.info.events,
272 );
273
274 loop_body(environment, checking_data);
275
276 if let Some(afterthought) = afterthought {
278 let _ = A::synthesise_multiple_expression(
279 afterthought,
280 TypeId::ANY_TYPE,
281 environment,
282 checking_data,
283 );
284 }
285
286 let dependent_variables: HashMap<VariableId, (TypeId, TypeId)> =
287 dependent_variables_initial_values
288 .into_iter()
289 .map(|(id, start_value)| {
290 let end_value = environment
291 .info
292 .variable_current_value
293 .get(&id)
294 .expect("loop variable with no initial value");
295 (id, (start_value, *end_value))
296 })
297 .collect();
298
299 (condition, dependent_variables)
300 },
301 );
302
303 let values = super::narrowing::narrow_based_on_expression_into_vec(
306 condition,
307 false,
308 environment,
309 &mut checking_data.types,
310 );
311
312 environment.info.narrowed_values = values;
313
314 (condition, events, dependent_variables)
315 },
316 );
317
318 let (
319 LocalInformation { variable_current_value, current_properties, events, .. },
320 closes_over,
321 ) = result.unwrap();
322
323 let loop_info = Values {
324 variable_values: variable_current_value,
325 _properties_values: current_properties,
326 };
327
328 let fixed_iterations = calculate_result_of_loop(
329 condition,
330 Some(&dependent_variables),
331 environment,
332 &checking_data.types,
333 &loop_info,
334 );
335
336 for (var, (start, _)) in dependent_variables {
337 environment.info.variable_current_value.insert(var, start);
338 }
339
340 let mut diagnostics = CallingDiagnostics::default();
341
342 run_iteration_block(
343 IterationKind::Condition { under: fixed_iterations.ok(), postfix_condition: false },
344 &events,
345 &application_input,
346 RunBehavior::References(closes_over),
347 &mut SubstitutionArguments::new_arguments_for_use_in_loop(),
348 environment,
349 &mut InvocationContext::new_empty(),
350 &mut diagnostics,
351 &mut checking_data.types,
352 );
353
354 diagnostics
355 .append_to(CallingContext::Iteration, &mut checking_data.diagnostics_container);
356 }
360 IterationBehavior::ForIn { lhs, rhs } => {
361 let on = A::synthesise_multiple_expression(
362 rhs,
363 TypeId::ANY_TYPE,
364 environment,
365 checking_data,
366 );
367
368 let variable =
369 checking_data.types.register_type(Type::RootPolyType(PolyNature::Parameter {
370 fixed_to: TypeId::STRING_TYPE,
372 }));
373
374 let ((), result, ..) = environment.new_lexical_environment_fold_into_parent(
375 Scope::Iteration { label },
376 checking_data,
377 |environment, checking_data| {
378 let arguments = crate::VariableRegisterArguments {
379 constant: true,
381 space: None,
382 initial_value: Some(variable),
383 allow_reregistration: false,
384 };
385 A::declare_and_assign_to_fields(lhs, environment, checking_data, arguments);
386 loop_body(environment, checking_data);
387 },
388 );
389
390 let (LocalInformation { events, .. }, closes_over) = result.unwrap();
391
392 let mut diagnostics = CallingDiagnostics::default();
393
394 run_iteration_block(
395 IterationKind::Properties { on, variable },
396 &events,
397 &application_input,
398 RunBehavior::References(closes_over),
399 &mut SubstitutionArguments::new_arguments_for_use_in_loop(),
400 environment,
401 &mut InvocationContext::new_empty(),
402 &mut diagnostics,
403 &mut checking_data.types,
404 );
405
406 diagnostics
407 .append_to(CallingContext::Iteration, &mut checking_data.diagnostics_container);
408
409 }
413 IterationBehavior::ForOf { lhs: _, rhs } => {
414 let _position = A::expression_position(rhs).with_source(environment.get_source());
415 let _rhs = A::synthesise_expression(rhs, TypeId::ANY_TYPE, environment, checking_data);
416
417 todo!()
419 }
420 }
421}
422
423fn add_loop_described_break_event(
425 condition: TypeId,
426 position: SpanWithSource,
427 events: &mut Vec<Event>,
428) {
429 let break_event =
430 Event::Conditionally { condition, truthy_events: 0, otherwise_events: 1, position };
431 events.push(break_event);
432 events.push(FinalEvent::Break { position, carry: 0 }.into());
433 events.push(Event::EndOfControlFlow(1));
434}
435
436pub enum InitialVariablesInput {
437 Calculated,
438 Compute(ClosedOverReferencesInScope),
439}
440
441#[derive(Debug, Clone, Copy, binary_serialize_derive::BinarySerializable)]
442pub enum IterationKind {
443 Condition {
444 under: Option<LoopStructure>,
446 postfix_condition: bool,
448 },
449 Properties {
450 on: TypeId,
451 variable: TypeId,
453 },
454 Iterator {
455 on: TypeId,
456 variable: TypeId,
458 },
459}
460
461pub enum RunBehavior {
462 Run,
464 References(ClosedOverReferencesInScope),
466}
467
468#[allow(clippy::too_many_arguments)]
469pub(crate) fn run_iteration_block(
470 condition: IterationKind,
471 events: &[Event],
472 input: &ApplicationInput,
473 initial: RunBehavior,
474 type_arguments: &mut SubstitutionArguments,
475 top_environment: &mut Environment,
476 invocation_context: &mut InvocationContext,
477 errors: &mut CallingDiagnostics,
478 types: &mut TypeStore,
479) -> Option<ApplicationResult> {
480 match condition {
487 IterationKind::Condition { postfix_condition, under } => {
488 crate::utilities::notify!("under={:?}", under);
502
503 let non_exorbitant_amount_of_iterations = under
504 .and_then(|under| under.calculate_iterations(types).ok())
505 .and_then(|iterations| {
506 let events_to_be_applied = iterations * events.len();
507
508 crate::utilities::notify!(
509 "applying {:?} events (max {:?})",
510 events_to_be_applied,
511 input.max_inline
512 );
513 (events_to_be_applied < input.max_inline as usize).then_some(iterations)
514 });
515
516 if let Some(mut iterations) = non_exorbitant_amount_of_iterations {
517 if postfix_condition {
519 iterations += 1;
520 }
521
522 crate::utilities::notify!("Running {} times", iterations);
523
524 run_iteration_loop(
525 invocation_context,
526 iterations,
527 events,
528 input,
529 type_arguments,
530 top_environment,
531 types,
532 errors,
533 |_, _| {},
534 )
535 } else {
536 evaluate_unknown_iteration_for_loop(
537 events,
538 initial,
539 condition,
540 type_arguments,
541 invocation_context,
542 top_environment,
543 types,
544 );
545 None
546 }
547 }
548 IterationKind::Properties { on, variable } => {
549 if let Type::Object(ObjectNature::RealDeal) = types.get_type_by_id(on) {
551 let properties = get_properties_on_single_type(
552 on,
553 types,
554 top_environment,
555 true,
556 TypeId::ANY_TYPE,
557 );
558 let mut n = 0;
559 run_iteration_loop(
560 invocation_context,
561 properties.len(),
562 events,
563 input,
564 type_arguments,
565 top_environment,
566 types,
567 errors,
568 |type_arguments, types| {
569 let (_publicity, property, _value) = &properties[n];
570 let property_key_as_type = property.into_type(types);
571
572 type_arguments.set_during_application(variable, property_key_as_type);
573
574 n += 1;
575 },
576 )
577 } else {
578 evaluate_unknown_iteration_for_loop(
579 events,
580 initial,
581 condition,
582 type_arguments,
583 invocation_context,
584 top_environment,
585 types,
586 );
587 None
588 }
589 }
590 IterationKind::Iterator { .. } => {
591 evaluate_unknown_iteration_for_loop(
595 events,
596 initial,
597 condition,
598 type_arguments,
599 invocation_context,
600 top_environment,
601 types,
602 );
603 None
604 }
606 }
607}
608
609#[allow(clippy::too_many_arguments)]
610fn run_iteration_loop(
611 invocation_context: &mut InvocationContext,
612 iterations: usize,
613 events: &[Event],
614 input: &ApplicationInput,
615 type_arguments: &mut SubstitutionArguments,
616 top_environment: &mut Environment,
617 types: &mut TypeStore,
618 errors: &mut CallingDiagnostics,
619 mut each_iteration: impl for<'a> FnMut(&'a mut SubstitutionArguments, &mut TypeStore),
621) -> Option<ApplicationResult> {
622 invocation_context.new_loop_iteration(|invocation_context| {
623 crate::utilities::notify!("running inline events: {:#?}", events);
624 for _ in 0..iterations {
625 each_iteration(type_arguments, types);
626 let result = apply_events(
627 events,
628 input,
629 type_arguments,
630 top_environment,
631 invocation_context,
632 types,
633 errors,
634 );
635
636 if let Some(result) = result {
637 crate::utilities::notify!("{:?}", result);
638 match result {
639 ApplicationResult::Continue { carry: 0, position: _ } => {
640 continue;
641 }
642 ApplicationResult::Break { carry: 0, position: _ } => {
643 break;
644 }
645 ApplicationResult::Continue { carry, position } => {
646 return Some(ApplicationResult::Continue { carry: carry - 1, position });
647 }
648 ApplicationResult::Break { carry, position } => {
649 return Some(ApplicationResult::Break { carry: carry - 1, position });
650 }
651 result => {
652 return Some(result);
653 }
654 }
655 }
656 }
657
658 None
659 })
660}
661
662fn evaluate_unknown_iteration_for_loop(
663 events: &[Event],
664 initial: RunBehavior,
665 kind: IterationKind,
666 type_arguments: &mut SubstitutionArguments,
667 invocation_context: &mut InvocationContext,
668 top_environment: &mut Environment,
669 types: &mut TypeStore,
670) {
671 let initial = match initial {
672 RunBehavior::Run => ClosedOverVariables(Default::default()),
673 RunBehavior::References(v) => {
674 crate::features::create_closed_over_references(&v, top_environment, types)
675 }
676 };
677
678 let mut calling_diagnostics = CallingDiagnostics::default();
679
680 let _res = invocation_context.new_unknown_target(|invocation_context| {
683 let max_inline = 10;
685
686 apply_events(
687 events,
688 &ApplicationInput {
689 this_value: crate::types::calling::ThisValue::UseParent,
690 call_site: BaseSpan::NULL,
691 max_inline,
692 },
693 type_arguments,
694 top_environment,
695 invocation_context,
696 types,
697 &mut calling_diagnostics,
698 )
699 });
700
701 {
703 {
704 }
718
719 let get_latest_info = invocation_context.get_latest_info(top_environment);
720 get_latest_info.events.push(Event::Iterate {
721 kind,
722 initial,
723 iterate_over: events.len() as u32,
724 });
725
726 get_latest_info.events.extend(events.iter().cloned());
727 get_latest_info.events.push(Event::EndOfControlFlow(events.len() as u32));
728 }
729}
730
731struct Values {
734 pub variable_values: HashMap<VariableId, TypeId>,
735 pub _properties_values: HashMap<
736 TypeId,
737 Vec<(
738 crate::types::properties::Publicity,
739 crate::types::properties::PropertyKey<'static>,
740 crate::PropertyValue,
741 )>,
742 >,
743}
744
745#[derive(Debug, Clone, Copy, binary_serialize_derive::BinarySerializable)]
747pub struct LoopStructure {
748 pub start: TypeId,
749 pub increment_by: TypeId,
750 pub roof: TypeId,
751}
752
753impl LoopStructure {
754 pub(crate) fn specialise(
755 self,
756 arguments: &SubstitutionArguments,
757 top_environment: &mut Environment,
759 types: &mut TypeStore,
760 ) -> Self {
761 Self {
762 start: substitute(self.start, arguments, top_environment, types),
763 increment_by: substitute(self.increment_by, arguments, top_environment, types),
764 roof: substitute(self.roof, arguments, top_environment, types),
765 }
766 }
767
768 pub fn calculate_iterations(self, types: &TypeStore) -> Result<usize, Self> {
769 self.calculate_iterations_f64(types).map(|result| result as usize)
770 }
771
772 pub fn known_to_never_exist(self, types: &TypeStore) -> bool {
773 self.calculate_iterations_f64(types).map_or(false, f64::is_infinite)
774 }
775
776 fn calculate_iterations_f64(self, types: &TypeStore) -> Result<f64, Self> {
777 let values = (
778 types.get_type_by_id(self.start),
779 types.get_type_by_id(self.increment_by),
780 types.get_type_by_id(self.roof),
781 );
782
783 if let (
784 Type::Constant(Constant::Number(start)),
785 Type::Constant(Constant::Number(increments_by)),
786 Type::Constant(Constant::Number(roof)),
787 ) = values
788 {
789 let iterations = (roof - start) / increments_by;
790 Ok(iterations.ceil())
798 } else {
799 Err(self)
801 }
802 }
803}
804
805fn calculate_result_of_loop(
806 condition: TypeId,
807 loop_variables: Option<&HashMap<VariableId, (TypeId, TypeId)>>,
808 parent_environment: &Environment,
809 types: &TypeStore,
810 inside_loop: &Values,
811) -> Result<LoopStructure, ()> {
812 let condition_ty = types.get_type_by_id(condition);
813
814 crate::utilities::notify!("condition is {:?}", condition_ty);
815
816 if let Type::Constructor(Constructor::CanonicalRelationOperator {
819 lhs: less_than_reference_type_id,
820 operator: CanonicalEqualityAndInequality::LessThan,
821 rhs: roof,
822 }) = condition_ty
823 {
824 let reference_ty = types.get_type_by_id(*less_than_reference_type_id);
826 crate::utilities::notify!("{:?}", reference_ty);
827
828 if let Type::RootPolyType(PolyNature::FreeVariable {
830 reference: less_than_reference,
831 based_on: _,
832 }) = reference_ty
833 {
834 if let RootReference::Variable(possible_changing_variable_id) = less_than_reference {
835 let roof_ty = types.get_type_by_id(*roof);
836 let roof: TypeId = if let Type::RootPolyType(PolyNature::FreeVariable {
838 reference: RootReference::Variable(roof_id),
839 based_on: _,
840 }) = roof_ty
841 {
842 let changed = if let Some((_start, _end)) =
843 loop_variables.as_ref().and_then(|vs| vs.get(roof_id).copied())
844 {
845 crate::utilities::notify!("Found loop variables");
846 false
847 } else if let Some(inside) = inside_loop.variable_values.get(roof_id) {
848 crate::utilities::notify!(
849 "Found loop here {:?}",
850 types.get_type_by_id(*inside)
851 );
852 false
853 } else {
854 crate::utilities::notify!("Here, roof not changed");
855 true
856 };
857
858 if changed {
859 if let Some((_start, end)) =
860 loop_variables.as_ref().and_then(|vs| vs.get(roof_id).copied())
861 {
862 end
863 } else {
864 *parent_environment.info.variable_current_value.get(roof_id).unwrap()
865 }
866 } else {
867 crate::utilities::notify!("Roof changed in loop");
868 return Err(());
869 }
870 } else if let Type::Constant(_) = roof_ty {
871 *roof
872 } else {
873 return Err(());
874 };
875
876 let value_after_running_expressions_in_loop = types.get_type_by_id(
877 if let Some((_start, end)) = loop_variables
878 .as_ref()
879 .and_then(|vs| vs.get(possible_changing_variable_id).copied())
880 {
881 end
882 } else {
883 inside_loop
884 .variable_values
885 .get(possible_changing_variable_id)
886 .or_else(|| {
887 parent_environment
889 .info
890 .variable_current_value
891 .get(possible_changing_variable_id)
892 })
893 .copied()
894 .unwrap_or(TypeId::ERROR_TYPE)
895 },
896 );
897
898 if let Type::Constructor(Constructor::BinaryOperator {
905 lhs: assignment,
906 operator: _,
907 rhs: increments_by,
908 result: _,
909 }) = value_after_running_expressions_in_loop
910 {
911 let assignment = crate::types::helpers::get_origin(*assignment, types);
912 debug_assert!(
913 assignment == *less_than_reference_type_id,
914 "incrementor free variable type not the same as condition free variable type?"
915 );
916
917 let start = if let Some((start, _end)) = loop_variables
918 .as_ref()
919 .and_then(|vs| vs.get(possible_changing_variable_id).copied())
920 {
921 start
922 } else {
923 *parent_environment
929 .info
930 .variable_current_value
931 .get(possible_changing_variable_id)
932 .unwrap()
933 };
934
935 return Ok(LoopStructure { start, roof, increment_by: *increments_by });
936 }
937 } else {
938 crate::utilities::notify!("{:?} has no max", roof);
939 }
940 } else {
941 crate::utilities::notify!("LHS {:?} is not free variable ", reference_ty);
942 }
943 }
944 Err(())
945}