1use crate::allocator::*;
2use crate::arithmetic::*;
3use crate::atom_table::*;
4use crate::debray_allocator::*;
5use crate::forms::*;
6use crate::indexing::*;
7use crate::instructions::*;
8use crate::iterators::*;
9use crate::parser::ast::*;
10use crate::targets::*;
11use crate::temp_v;
12use crate::types::*;
13use crate::variable_records::*;
14
15use crate::instr;
16use crate::machine::disjuncts::*;
17use crate::machine::machine_errors::*;
18
19use fxhash::FxBuildHasher;
20use indexmap::IndexSet;
21
22use std::cell::Cell;
23use std::collections::VecDeque;
24
25#[derive(Debug)]
26pub struct BranchCodeStack {
27 pub stack: Vec<Vec<CodeDeque>>,
28}
29
30pub type SubsumedBranchHits = IndexSet<usize, FxBuildHasher>;
31
32impl BranchCodeStack {
33 fn new() -> Self {
34 Self { stack: vec![] }
35 }
36
37 fn add_new_branch_stack(&mut self) {
38 self.stack.push(vec![]);
39 }
40
41 fn add_new_branch(&mut self) {
42 if self.stack.is_empty() {
43 self.add_new_branch_stack();
44 }
45
46 if let Some(branches) = self.stack.last_mut() {
47 branches.push(CodeDeque::new());
48 }
49 }
50
51 fn code<'a>(&'a mut self, default_code: &'a mut CodeDeque) -> &'a mut CodeDeque {
52 self.stack
53 .last_mut()
54 .and_then(|stack| stack.last_mut())
55 .unwrap_or(default_code)
56 }
57
58 fn push_missing_vars(
59 &mut self,
60 depth: usize,
61 marker: &mut DebrayAllocator,
62 ) -> SubsumedBranchHits {
63 let mut subsumed_hits = SubsumedBranchHits::with_hasher(FxBuildHasher::default());
64 let mut propagated_var_nums = IndexSet::with_hasher(FxBuildHasher::default());
65
66 for idx in (self.stack.len() - depth..self.stack.len()).rev() {
67 let branch = &mut marker.branch_stack[idx];
68 let branch_hits = &branch.hits;
69
70 for (&var_num, branches) in branch_hits.iter() {
71 let record = &marker.var_data.records[var_num];
72
73 if record.running_count < record.num_occurrences {
74 if !branches.all() {
75 branch.deep_safety.insert(var_num);
76 branch.shallow_safety.insert(var_num);
77
78 let r = record.allocation.as_reg_type();
79
80 for branch_idx in branches.iter_zeros() {
82 if branch_idx + 1 == branches.len() && idx + 1 != self.stack.len() {
83 break;
84 }
85
86 self.stack[idx][branch_idx].push_back(instr!("put_variable", r, 0));
87 }
88 }
89
90 if idx > self.stack.len() - depth {
91 propagated_var_nums.insert(var_num);
92 }
93
94 subsumed_hits.insert(var_num);
95 }
96 }
97
98 for var_num in propagated_var_nums.drain(..) {
99 marker.branch_stack[idx - 1].add_branch_occurrence(var_num);
100 }
101 }
102
103 subsumed_hits
104 }
105
106 fn push_jump_instrs(&mut self, depth: usize) {
107 let mut jump_span: usize = self.stack[self.stack.len() - depth..]
110 .iter()
111 .map(|branch| branch.iter().map(|code| code.len() + 2).sum::<usize>())
112 .sum();
113
114 jump_span -= depth;
115
116 for idx in self.stack.len() - depth..self.stack.len() {
117 let inner_len = self.stack[idx].len();
118
119 for (inner_idx, code) in self.stack[idx].iter_mut().enumerate() {
120 if inner_idx + 1 == inner_len {
121 jump_span -= code.len() + 1;
122 } else {
123 jump_span -= code.len() + 1;
124 code.push_back(instr!("jmp_by_call", jump_span));
125
126 jump_span -= 1;
127 }
128 }
129 }
130 }
131
132 fn pop_branch(&mut self, depth: usize, settings: CodeGenSettings) -> CodeDeque {
133 let mut combined_code = CodeDeque::new();
134
135 for mut branch_arm in self.stack.drain(self.stack.len() - depth..).rev() {
136 let num_branch_arms = branch_arm.len();
137 if let Some(code) = branch_arm.last_mut() {
138 code.extend(combined_code.drain(..))
139 }
140
141 for (idx, code) in branch_arm.into_iter().enumerate() {
142 combined_code.push_back(if idx == 0 {
143 Instruction::TryMeElse(code.len() + 1)
144 } else if idx + 1 < num_branch_arms {
145 settings.retry_me_else(code.len() + 1)
146 } else {
147 settings.trust_me()
148 });
149
150 combined_code.extend(code.into_iter());
151 }
152 }
153
154 combined_code
155 }
156}
157
158#[derive(Clone, Copy, Debug)]
159pub(crate) struct CodeGenSettings {
160 pub global_clock_tick: Option<usize>,
161 pub is_extensible: bool,
162 pub non_counted_bt: bool,
163}
164
165impl CodeGenSettings {
166 #[inline]
167 pub(crate) fn is_dynamic(&self) -> bool {
168 self.global_clock_tick.is_some()
169 }
170
171 #[inline]
172 pub(crate) fn internal_try_me_else(&self, offset: usize) -> Instruction {
173 if let Some(global_clock_time) = self.global_clock_tick {
174 Instruction::DynamicInternalElse(
175 global_clock_time,
176 Death::Infinity,
177 if offset == 0 {
178 NextOrFail::Next(0)
179 } else {
180 NextOrFail::Next(offset)
181 },
182 )
183 } else {
184 Instruction::TryMeElse(offset)
185 }
186 }
187
188 pub(crate) fn try_me_else(&self, offset: usize) -> Instruction {
189 if let Some(global_clock_tick) = self.global_clock_tick {
190 Instruction::DynamicElse(
191 global_clock_tick,
192 Death::Infinity,
193 if offset == 0 {
194 NextOrFail::Next(0)
195 } else {
196 NextOrFail::Next(offset)
197 },
198 )
199 } else {
200 Instruction::TryMeElse(offset)
201 }
202 }
203
204 pub(crate) fn internal_retry_me_else(&self, offset: usize) -> Instruction {
205 if let Some(global_clock_tick) = self.global_clock_tick {
206 Instruction::DynamicInternalElse(
207 global_clock_tick,
208 Death::Infinity,
209 if offset == 0 {
210 NextOrFail::Next(0)
211 } else {
212 NextOrFail::Next(offset)
213 },
214 )
215 } else {
216 Instruction::RetryMeElse(offset)
217 }
218 }
219
220 pub(crate) fn retry_me_else(&self, offset: usize) -> Instruction {
221 if let Some(global_clock_tick) = self.global_clock_tick {
222 Instruction::DynamicElse(
223 global_clock_tick,
224 Death::Infinity,
225 if offset == 0 {
226 NextOrFail::Next(0)
227 } else {
228 NextOrFail::Next(offset)
229 },
230 )
231 } else if self.non_counted_bt {
232 Instruction::DefaultRetryMeElse(offset)
233 } else {
234 Instruction::RetryMeElse(offset)
235 }
236 }
237
238 pub(crate) fn internal_trust_me(&self) -> Instruction {
239 if let Some(global_clock_tick) = self.global_clock_tick {
240 Instruction::DynamicInternalElse(
241 global_clock_tick,
242 Death::Infinity,
243 NextOrFail::Fail(0),
244 )
245 } else if self.non_counted_bt {
246 Instruction::DefaultTrustMe(0)
247 } else {
248 Instruction::TrustMe(0)
249 }
250 }
251
252 pub(crate) fn trust_me(&self) -> Instruction {
253 if let Some(global_clock_tick) = self.global_clock_tick {
254 Instruction::DynamicElse(global_clock_tick, Death::Infinity, NextOrFail::Fail(0))
255 } else if self.non_counted_bt {
256 Instruction::DefaultTrustMe(0)
257 } else {
258 Instruction::TrustMe(0)
259 }
260 }
261
262 pub(crate) fn default_call_policy(&self) -> CallPolicy {
263 if self.non_counted_bt {
266 CallPolicy::Default
267 } else {
268 CallPolicy::Counted
269 }
270 }
271}
272
273#[derive(Debug)]
274pub(crate) struct CodeGenerator<'a> {
275 pub(crate) atom_tbl: &'a AtomTable,
276 marker: DebrayAllocator,
277 settings: CodeGenSettings,
278 pub(crate) skeleton: PredicateSkeleton,
279}
280
281impl DebrayAllocator {
282 fn mark_var_in_non_callable(
283 &mut self,
284 var_num: usize,
285 term_loc: GenContext,
286 vr: &Cell<VarReg>,
287 code: &mut CodeDeque,
288 ) -> RegType {
289 self.mark_var::<QueryInstruction>(var_num, Level::Shallow, vr, term_loc, code);
290 vr.get().norm()
291 }
292
293 pub(crate) fn mark_non_callable(
294 &mut self,
295 var_num: usize,
296 arg: usize,
297 term_loc: GenContext,
298 vr: &Cell<VarReg>,
299 code: &mut CodeDeque,
300 ) -> RegType {
301 match self.get_binding(var_num) {
302 RegType::Temp(t) if t != 0 => RegType::Temp(t),
303 RegType::Perm(p) if p != 0 => {
304 if let GenContext::Last(_) = term_loc {
305 self.mark_var_in_non_callable(var_num, term_loc, vr, code);
306 temp_v!(arg)
307 } else {
308 if let VarAlloc::Perm(_, PermVarAllocation::Pending) =
309 &self.var_data.records[var_num].allocation
310 {
311 self.mark_var_in_non_callable(var_num, term_loc, vr, code);
312 } else {
313 self.increment_running_count(var_num);
314 }
315
316 RegType::Perm(p)
317 }
318 }
319 _ => self.mark_var_in_non_callable(var_num, term_loc, vr, code),
320 }
321 }
322}
323
324fn trim_structure_by_last_arg(instr: &mut Instruction, last_arg: &Term) {
327 match instr {
328 Instruction::PutStructure(_, ref mut arity, _)
329 | Instruction::GetStructure(.., ref mut arity, _) => {
330 if let Term::Literal(_, Literal::CodeIndex(_)) = last_arg {
331 *arity -= 1;
339 }
340 }
341 _ => {}
342 }
343}
344
345trait AddToFreeList<'a, Target: CompilationTarget<'a>> {
346 fn add_term_to_free_list(&mut self, r: RegType);
347 fn add_subterm_to_free_list(&mut self, term: &Term);
348}
349
350impl<'a, 'b> AddToFreeList<'a, FactInstruction> for CodeGenerator<'b> {
351 fn add_term_to_free_list(&mut self, r: RegType) {
352 self.marker.add_reg_to_free_list(r);
353 }
354
355 fn add_subterm_to_free_list(&mut self, _term: &Term) {}
356}
357
358impl<'a, 'b> AddToFreeList<'a, QueryInstruction> for CodeGenerator<'b> {
359 #[inline(always)]
360 fn add_term_to_free_list(&mut self, _r: RegType) {}
361
362 #[inline(always)]
363 fn add_subterm_to_free_list(&mut self, term: &Term) {
364 if let Some(cell) = structure_cell(term) {
365 self.marker.add_reg_to_free_list(cell.get());
366 }
367 }
368}
369
370fn structure_cell(term: &Term) -> Option<&Cell<RegType>> {
371 match term {
372 &Term::Cons(ref cell, ..)
373 | &Term::Clause(ref cell, ..)
374 | Term::PartialString(ref cell, ..)
375 | Term::CompleteString(ref cell, ..) => Some(cell),
376 _ => None,
377 }
378}
379
380impl<'b> CodeGenerator<'b> {
381 pub(crate) fn new(atom_tbl: &'b AtomTable, settings: CodeGenSettings) -> Self {
382 CodeGenerator {
383 atom_tbl,
384 marker: DebrayAllocator::new(),
385 settings,
386 skeleton: PredicateSkeleton::new(),
387 }
388 }
389
390 fn add_or_increment_void_instr<'a, Target>(target: &mut CodeDeque)
391 where
392 Target: crate::targets::CompilationTarget<'a>,
393 {
394 if let Some(ref mut instr) = target.back_mut() {
395 if Target::is_void_instr(instr) {
396 Target::incr_void_instr(instr);
397 return;
398 }
399 }
400
401 target.push_back(Target::to_void(1));
402 }
403
404 fn deep_var_instr<'a, Target: crate::targets::CompilationTarget<'a>>(
405 &mut self,
406 cell: &'a Cell<VarReg>,
407 var_num: usize,
408 term_loc: GenContext,
409 target: &mut CodeDeque,
410 ) {
411 if self.marker.var_data.records[var_num].num_occurrences > 1 {
412 self.marker
413 .mark_var::<Target>(var_num, Level::Deep, cell, term_loc, target);
414 } else {
415 Self::add_or_increment_void_instr::<Target>(target);
416 }
417 }
418
419 fn subterm_to_instr<'a, Target: crate::targets::CompilationTarget<'a>>(
420 &mut self,
421 subterm: &'a Term,
422 term_loc: GenContext,
423 target: &mut CodeDeque,
424 ) {
425 match subterm {
426 &Term::AnonVar => {
427 Self::add_or_increment_void_instr::<Target>(target);
428 }
429 &Term::Cons(ref cell, ..)
430 | &Term::Clause(ref cell, ..)
431 | Term::PartialString(ref cell, ..)
432 | Term::CompleteString(ref cell, ..) => {
433 self.marker
434 .mark_non_var::<Target>(Level::Deep, term_loc, cell, target);
435 target.push_back(Target::clause_arg_to_instr(cell.get()));
436 }
437 Term::Literal(_, ref constant) => {
438 target.push_back(Target::constant_subterm(*constant));
439 }
440 Term::Var(ref cell, ref var_ptr) => {
441 self.deep_var_instr::<Target>(
442 cell,
443 var_ptr.to_var_num().unwrap(),
444 term_loc,
445 target,
446 );
447 }
448 };
449 }
450
451 fn compile_target<'a, Target, Iter>(&mut self, iter: Iter, term_loc: GenContext) -> CodeDeque
452 where
453 Target: crate::targets::CompilationTarget<'a>,
454 Iter: Iterator<Item = TermRef<'a>>,
455 CodeGenerator<'b>: AddToFreeList<'a, Target>,
456 {
457 let mut target = CodeDeque::new();
458
459 for term in iter {
460 match term {
461 TermRef::AnonVar(lvl @ Level::Shallow) => {
462 if let GenContext::Head = term_loc {
463 self.marker.advance_arg();
464 } else {
465 self.marker
466 .mark_anon_var::<Target>(lvl, term_loc, &mut target);
467 }
468 }
469 TermRef::Clause(lvl, cell, name, terms) => {
470 self.marker
471 .mark_non_var::<Target>(lvl, term_loc, cell, &mut target);
472 target.push_back(Target::to_structure(lvl, name, terms.len(), cell.get()));
473
474 <CodeGenerator<'b> as AddToFreeList<'a, Target>>::add_term_to_free_list(
475 self,
476 cell.get(),
477 );
478
479 if let Some(instr) = target.back_mut() {
480 if let Some(term) = terms.last() {
481 trim_structure_by_last_arg(instr, term);
482 }
483 }
484
485 for subterm in terms {
486 self.subterm_to_instr::<Target>(subterm, term_loc, &mut target);
487 }
488
489 for subterm in terms {
490 <CodeGenerator<'b> as AddToFreeList<'a, Target>>::add_subterm_to_free_list(
491 self, subterm,
492 );
493 }
494 }
495 TermRef::Cons(lvl, cell, head, tail) => {
496 self.marker
497 .mark_non_var::<Target>(lvl, term_loc, cell, &mut target);
498 target.push_back(Target::to_list(lvl, cell.get()));
499
500 <CodeGenerator<'b> as AddToFreeList<'a, Target>>::add_term_to_free_list(
501 self,
502 cell.get(),
503 );
504
505 self.subterm_to_instr::<Target>(head, term_loc, &mut target);
506 self.subterm_to_instr::<Target>(tail, term_loc, &mut target);
507
508 <CodeGenerator<'b> as AddToFreeList<'a, Target>>::add_subterm_to_free_list(
509 self, head,
510 );
511 <CodeGenerator<'b> as AddToFreeList<'a, Target>>::add_subterm_to_free_list(
512 self, tail,
513 );
514 }
515 TermRef::Literal(lvl @ Level::Shallow, cell, Literal::String(ref string)) => {
516 self.marker
517 .mark_non_var::<Target>(lvl, term_loc, cell, &mut target);
518 target.push_back(Target::to_pstr(lvl, *string, cell.get(), false));
519 }
520 TermRef::Literal(lvl @ Level::Shallow, cell, constant) => {
521 self.marker
522 .mark_non_var::<Target>(lvl, term_loc, cell, &mut target);
523 target.push_back(Target::to_constant(lvl, *constant, cell.get()));
524 }
525 TermRef::PartialString(lvl, cell, string, tail) => {
526 self.marker
527 .mark_non_var::<Target>(lvl, term_loc, cell, &mut target);
528 let atom = AtomTable::build_with(self.atom_tbl, string);
529
530 target.push_back(Target::to_pstr(lvl, atom, cell.get(), true));
531 self.subterm_to_instr::<Target>(tail, term_loc, &mut target);
532 }
533 TermRef::CompleteString(lvl, cell, atom) => {
534 self.marker
535 .mark_non_var::<Target>(lvl, term_loc, cell, &mut target);
536 target.push_back(Target::to_pstr(lvl, atom, cell.get(), false));
537 }
538 TermRef::Var(lvl @ Level::Shallow, cell, var) => {
539 self.marker.mark_var::<Target>(
540 var.to_var_num().unwrap(),
541 lvl,
542 cell,
543 term_loc,
544 &mut target,
545 );
546 }
547 _ => {}
548 };
549 }
550
551 target
552 }
553
554 fn add_call(&mut self, code: &mut CodeDeque, call_instr: Instruction, call_policy: CallPolicy) {
555 if self.marker.in_tail_position && self.marker.var_data.allocates {
556 code.push_back(instr!("deallocate"));
557 }
558
559 match call_policy {
560 CallPolicy::Default => {
561 if self.marker.in_tail_position {
562 code.push_back(call_instr.to_execute().to_default());
563 } else {
564 code.push_back(call_instr.to_default())
565 }
566 }
567 CallPolicy::Counted => {
568 if self.marker.in_tail_position {
569 code.push_back(call_instr.to_execute());
570 } else {
571 code.push_back(call_instr)
572 }
573 }
574 }
575 }
576
577 fn compile_inlined(
578 &mut self,
579 ct: &InlinedClauseType,
580 terms: &'_ [Term],
581 term_loc: GenContext,
582 code: &mut CodeDeque,
583 ) -> Result<(), CompilationError> {
584 let call_instr = match ct {
585 &InlinedClauseType::CompareNumber(mut cmp) => {
586 self.marker.reset_arg(2);
587
588 let (mut lcode, at_1) = self.compile_arith_expr(&terms[0], 1, term_loc, 1)?;
589
590 if !matches!(terms[0], Term::Var(..)) {
591 self.marker.advance_arg();
592 }
593
594 let (mut rcode, at_2) = self.compile_arith_expr(&terms[1], 2, term_loc, 2)?;
595
596 code.append(&mut lcode);
597 code.append(&mut rcode);
598
599 let at_1 = at_1.unwrap_or(interm!(1));
600 let at_2 = at_2.unwrap_or(interm!(2));
601
602 compare_number_instr!(cmp, at_1, at_2)
603 }
604 InlinedClauseType::IsAtom(..) => match &terms[0] {
605 Term::Literal(_, Literal::Char(_))
606 | Term::Literal(_, Literal::Atom(atom!("[]")))
607 | Term::Literal(_, Literal::Atom(..)) => {
608 instr!("$succeed")
609 }
610 Term::Var(ref vr, ref name) => {
611 self.marker.reset_arg(1);
612
613 let r = self.marker.mark_non_callable(
614 name.to_var_num().unwrap(),
615 1,
616 term_loc,
617 vr,
618 code,
619 );
620
621 instr!("atom", r)
622 }
623 _ => {
624 instr!("$fail")
625 }
626 },
627 InlinedClauseType::IsAtomic(..) => match &terms[0] {
628 Term::AnonVar
629 | Term::Clause(..)
630 | Term::Cons(..)
631 | Term::PartialString(..)
632 | Term::CompleteString(..) => {
633 instr!("$fail")
634 }
635 Term::Literal(_, Literal::String(_)) => {
636 instr!("$fail")
637 }
638 Term::Literal(..) => {
639 instr!("$succeed")
640 }
641 Term::Var(ref vr, ref name) => {
642 self.marker.reset_arg(1);
643
644 let r = self.marker.mark_non_callable(
645 name.to_var_num().unwrap(),
646 1,
647 term_loc,
648 vr,
649 code,
650 );
651
652 instr!("atomic", r)
653 }
654 },
655 InlinedClauseType::IsCompound(..) => match &terms[0] {
656 Term::Clause(..)
657 | Term::Cons(..)
658 | Term::PartialString(..)
659 | Term::CompleteString(..)
660 | Term::Literal(_, Literal::String(..)) => {
661 instr!("$succeed")
662 }
663 Term::Var(ref vr, ref name) => {
664 self.marker.reset_arg(1);
665
666 let r = self.marker.mark_non_callable(
667 name.to_var_num().unwrap(),
668 1,
669 term_loc,
670 vr,
671 code,
672 );
673
674 instr!("compound", r)
675 }
676 _ => {
677 instr!("$fail")
678 }
679 },
680 InlinedClauseType::IsRational(..) => match terms[0] {
681 Term::Literal(_, Literal::Rational(_)) => {
682 instr!("$succeed")
683 }
684 Term::Var(ref vr, ref name) => {
685 self.marker.reset_arg(1);
686 let r = self.marker.mark_non_callable(
687 name.to_var_num().unwrap(),
688 1,
689 term_loc,
690 vr,
691 code,
692 );
693 instr!("rational", r)
694 }
695 _ => {
696 instr!("$fail")
697 }
698 },
699 InlinedClauseType::IsFloat(..) => match terms[0] {
700 Term::Literal(_, Literal::Float(_)) => {
701 instr!("$succeed")
702 }
703 Term::Var(ref vr, ref name) => {
704 self.marker.reset_arg(1);
705
706 let r = self.marker.mark_non_callable(
707 name.to_var_num().unwrap(),
708 1,
709 term_loc,
710 vr,
711 code,
712 );
713
714 instr!("float", r)
715 }
716 _ => {
717 instr!("$fail")
718 }
719 },
720 InlinedClauseType::IsNumber(..) => match terms[0] {
721 Term::Literal(_, Literal::Float(_))
722 | Term::Literal(_, Literal::Rational(_))
723 | Term::Literal(_, Literal::Integer(_))
724 | Term::Literal(_, Literal::Fixnum(_)) => {
725 instr!("$succeed")
726 }
727 Term::Var(ref vr, ref name) => {
728 self.marker.reset_arg(1);
729
730 let r = self.marker.mark_non_callable(
731 name.to_var_num().unwrap(),
732 1,
733 term_loc,
734 vr,
735 code,
736 );
737
738 instr!("number", r)
739 }
740 _ => {
741 instr!("$fail")
742 }
743 },
744 InlinedClauseType::IsNonVar(..) => match terms[0] {
745 Term::AnonVar => {
746 instr!("$fail")
747 }
748 Term::Var(ref vr, ref name) => {
749 self.marker.reset_arg(1);
750
751 let r = self.marker.mark_non_callable(
752 name.to_var_num().unwrap(),
753 1,
754 term_loc,
755 vr,
756 code,
757 );
758
759 instr!("nonvar", r)
760 }
761 _ => {
762 instr!("$succeed")
763 }
764 },
765 InlinedClauseType::IsInteger(..) => match &terms[0] {
766 Term::Literal(_, Literal::Integer(_)) | Term::Literal(_, Literal::Fixnum(_)) => {
767 instr!("$succeed")
768 }
769 Term::Var(ref vr, name) => {
770 self.marker.reset_arg(1);
771
772 let r = self.marker.mark_non_callable(
773 name.to_var_num().unwrap(),
774 1,
775 term_loc,
776 vr,
777 code,
778 );
779
780 instr!("integer", r)
781 }
782 _ => {
783 instr!("$fail")
784 }
785 },
786 InlinedClauseType::IsVar(..) => match terms[0] {
787 Term::Literal(..)
788 | Term::Clause(..)
789 | Term::Cons(..)
790 | Term::PartialString(..)
791 | Term::CompleteString(..) => {
792 instr!("$fail")
793 }
794 Term::AnonVar => {
795 instr!("$succeed")
796 }
797 Term::Var(ref vr, ref name) => {
798 self.marker.reset_arg(1);
799
800 let r = self.marker.mark_non_callable(
801 name.to_var_num().unwrap(),
802 1,
803 term_loc,
804 vr,
805 code,
806 );
807
808 instr!("var", r)
809 }
810 },
811 };
812
813 self.add_call(code, call_instr, CallPolicy::Counted);
815
816 Ok(())
817 }
818
819 fn compile_arith_expr(
820 &mut self,
821 term: &Term,
822 target_int: usize,
823 term_loc: GenContext,
824 arg: usize,
825 ) -> Result<ArithCont, ArithmeticError> {
826 let mut evaluator = ArithmeticEvaluator::new(&mut self.marker, target_int);
827 evaluator.compile_is(term, term_loc, arg)
828 }
829
830 fn compile_is_call(
831 &mut self,
832 terms: &[Term],
833 code: &mut CodeDeque,
834 term_loc: GenContext,
835 call_policy: CallPolicy,
836 ) -> Result<(), CompilationError> {
837 macro_rules! compile_expr {
838 ($self:expr, $terms:expr, $term_loc:expr, $code:expr) => {{
839 let (acode, at) = $self.compile_arith_expr($terms, 1, $term_loc, 2)?;
840 $code.extend(acode.into_iter());
841 at
842 }};
843 }
844
845 self.marker.reset_arg(2);
846
847 let at = match terms[0] {
848 Term::Var(ref vr, ref name) => {
849 let var_num = name.to_var_num().unwrap();
850
851 if self.marker.var_data.records[var_num].num_occurrences > 1 {
852 self.marker.mark_var::<QueryInstruction>(
853 var_num,
854 Level::Shallow,
855 vr,
856 term_loc,
857 code,
858 );
859
860 self.marker.mark_safe_var_unconditionally(var_num);
861 compile_expr!(self, &terms[1], term_loc, code)
862 } else {
863 self.marker
864 .mark_anon_var::<QueryInstruction>(Level::Shallow, term_loc, code);
865
866 if let Term::Var(ref vr, ref var) = &terms[1] {
867 let var_num = var.to_var_num().unwrap();
868
869 if self.marker.var_data.records[var_num].num_occurrences > 1 {
873 self.marker.mark_var::<QueryInstruction>(
874 var_num,
875 Level::Shallow,
876 vr,
877 term_loc,
878 code,
879 );
880
881 self.marker.mark_safe_var_unconditionally(var_num);
882
883 let at = ArithmeticTerm::Reg(vr.get().norm());
884 self.add_call(code, instr!("$get_number", at), call_policy);
885
886 return Ok(());
887 }
888 }
889
890 compile_expr!(self, &terms[1], term_loc, code)
891 }
892 }
893 Term::Literal(
894 _,
895 c @ Literal::Integer(_)
896 | c @ Literal::Float(_)
897 | c @ Literal::Rational(_)
898 | c @ Literal::Fixnum(_),
899 ) => {
900 let v = HeapCellValue::from(c);
901 code.push_back(instr!("put_constant", Level::Shallow, v, temp_v!(1)));
902
903 self.marker.advance_arg();
904 compile_expr!(self, &terms[1], term_loc, code)
905 }
906 _ => {
907 code.push_back(instr!("$fail"));
908 return Ok(());
909 }
910 };
911
912 let at = at.unwrap_or(interm!(1));
913 self.add_call(code, instr!("is", temp_v!(1), at), call_policy);
914
915 Ok(())
916 }
917
918 fn compile_seq(
919 &mut self,
920 clauses: &ChunkedTermVec,
921 code: &mut CodeDeque,
922 ) -> Result<(), CompilationError> {
923 let mut chunk_num = 0;
924 let mut branch_code_stack = BranchCodeStack::new();
925 let mut clause_iter = ClauseIterator::new(clauses);
926
927 while let Some(clause_item) = clause_iter.next() {
928 match clause_item {
929 ClauseItem::Chunk(chunk) => {
930 for (idx, term) in chunk.iter().enumerate() {
931 let term_loc = if idx + 1 < chunk.len() {
932 GenContext::Mid(chunk_num)
933 } else {
934 self.marker.in_tail_position = clause_iter.in_tail_position();
935 GenContext::Last(chunk_num)
936 };
937
938 match term {
939 &QueryTerm::GetLevel(var_num) => {
940 let code = branch_code_stack.code(code);
941 let r = self.marker.mark_cut_var(var_num, chunk_num);
942 code.push_back(instr!("get_level", r));
943 }
944 &QueryTerm::GetCutPoint { var_num, prev_b } => {
945 let code = branch_code_stack.code(code);
946 let r = self.marker.mark_cut_var(var_num, chunk_num);
947
948 code.push_back(if prev_b {
949 instr!("get_prev_level", r)
950 } else {
951 instr!("get_cut_point", r)
952 });
953 }
954 &QueryTerm::GlobalCut(var_num) => {
955 let code = branch_code_stack.code(code);
956
957 if chunk_num == 0 {
958 code.push_back(instr!("neck_cut"));
959 } else {
960 let r = self.marker.get_binding(var_num);
961 code.push_back(instr!("cut", r));
962 }
963
964 if self.marker.in_tail_position {
965 if self.marker.var_data.allocates {
966 code.push_back(instr!("deallocate"));
967 }
968
969 code.push_back(instr!("proceed"));
970 }
971 }
972 &QueryTerm::LocalCut { var_num, cut_prev } => {
973 let code = branch_code_stack.code(code);
974 let r = self.marker.get_binding(var_num);
975
976 code.push_back(if cut_prev {
977 instr!("cut_prev", r)
978 } else {
979 instr!("cut", r)
980 });
981
982 if self.marker.in_tail_position {
983 if self.marker.var_data.allocates {
984 code.push_back(instr!("deallocate"));
985 }
986
987 code.push_back(instr!("proceed"));
988 } else {
989 self.marker.free_var(chunk_num, var_num);
990 }
991 }
992 &QueryTerm::Clause(
993 _,
994 ClauseType::BuiltIn(BuiltInClauseType::Is(..)),
995 ref terms,
996 call_policy,
997 ) => self.compile_is_call(
998 terms,
999 branch_code_stack.code(code),
1000 term_loc,
1001 call_policy,
1002 )?,
1003 &QueryTerm::Clause(_, ClauseType::Inlined(ref ct), ref terms, _) => {
1004 self.compile_inlined(
1005 ct,
1006 terms,
1007 term_loc,
1008 branch_code_stack.code(code),
1009 )?
1010 }
1011 &QueryTerm::Fail => {
1012 branch_code_stack.code(code).push_back(instr!("$fail"));
1013 }
1014 term @ &QueryTerm::Clause(..) => {
1015 self.compile_query_line(
1016 term,
1017 term_loc,
1018 branch_code_stack.code(code),
1019 );
1020
1021 if self.marker.max_reg_allocated() > MAX_ARITY {
1022 return Err(CompilationError::ExceededMaxArity);
1023 }
1024 }
1025 }
1026 }
1027
1028 chunk_num += 1;
1029 self.marker.in_tail_position = false;
1030 self.marker.reset_contents();
1031 }
1032 ClauseItem::FirstBranch(num_branches) => {
1033 branch_code_stack.add_new_branch_stack();
1034 branch_code_stack.add_new_branch();
1035
1036 self.marker.branch_stack.add_branch_stack(num_branches);
1037 self.marker.add_branch();
1038 }
1039 ClauseItem::NextBranch => {
1040 branch_code_stack.add_new_branch();
1041
1042 self.marker.add_branch();
1043 self.marker.branch_stack.incr_current_branch();
1044 }
1045 ClauseItem::BranchEnd(depth) => {
1046 if !clause_iter.in_tail_position() {
1047 let subsumed_hits =
1048 branch_code_stack.push_missing_vars(depth, &mut self.marker);
1049 self.marker.pop_branch(depth, subsumed_hits);
1050 branch_code_stack.push_jump_instrs(depth);
1051 } else {
1052 self.marker.branch_stack.drain_branches(depth);
1053 }
1054
1055 let settings = CodeGenSettings {
1056 non_counted_bt: self.settings.non_counted_bt,
1057 is_extensible: false,
1058 global_clock_tick: None,
1059 };
1060
1061 let branch_code = branch_code_stack.pop_branch(depth, settings);
1062 branch_code_stack.code(code).extend(branch_code);
1063 }
1064 }
1065 }
1066
1067 if self.marker.var_data.allocates {
1068 code.push_front(instr!("allocate", self.marker.num_perm_vars()));
1069 }
1070
1071 Ok(())
1072 }
1073
1074 pub(crate) fn compile_rule(
1075 &mut self,
1076 rule: &Rule,
1077 var_data: VarData,
1078 ) -> Result<Code, CompilationError> {
1079 let Rule {
1080 head: (_, args),
1081 clauses,
1082 } = rule;
1083 self.marker.var_data = var_data;
1084 let mut code = VecDeque::new();
1085
1086 self.marker.reset_at_head(args);
1087
1088 let iter = FactIterator::from_rule_head_clause(args);
1089 let fact = self.compile_target::<FactInstruction, _>(iter, GenContext::Head);
1090
1091 if self.marker.max_reg_allocated() > MAX_ARITY {
1092 return Err(CompilationError::ExceededMaxArity);
1093 }
1094
1095 self.marker.reset_free_list();
1096 code.extend(fact);
1097
1098 self.compile_seq(clauses, &mut code)?;
1099
1100 Ok(Vec::from(code))
1101 }
1102
1103 pub(crate) fn compile_fact(
1104 &mut self,
1105 fact: &Fact,
1106 var_data: VarData,
1107 ) -> Result<Code, CompilationError> {
1108 let mut code = Vec::new();
1109 self.marker.var_data = var_data;
1110
1111 if let Term::Clause(_, _, args) = &fact.head {
1112 self.marker.reset_at_head(args);
1113
1114 let iter = FactInstruction::iter(&fact.head);
1115 let compiled_fact = self.compile_target::<FactInstruction, _>(iter, GenContext::Head);
1116
1117 if self.marker.max_reg_allocated() > MAX_ARITY {
1118 return Err(CompilationError::ExceededMaxArity);
1119 }
1120
1121 code.extend(compiled_fact);
1122 }
1123
1124 code.push(instr!("proceed"));
1125 Ok(code)
1126 }
1127
1128 fn compile_query_line(&mut self, term: &QueryTerm, term_loc: GenContext, code: &mut CodeDeque) {
1129 self.marker.reset_arg(term.arity());
1130
1131 let iter = QueryIterator::new(term);
1132 let query = self.compile_target::<QueryInstruction, _>(iter, term_loc);
1133
1134 code.extend(query);
1135
1136 match term {
1137 &QueryTerm::Clause(_, ref ct, _, call_policy) => {
1138 self.add_call(code, ct.to_instr(), call_policy);
1139 }
1140 _ => unreachable!(),
1141 };
1142 }
1143
1144 fn split_predicate(clauses: &[PredicateClause]) -> Vec<ClauseSpan> {
1145 let mut subseqs = Vec::new();
1146 let mut left = 0;
1147 let mut optimal_index = 0;
1148
1149 'outer: for (right, clause) in clauses.iter().enumerate() {
1150 if let Some(args) = clause.args() {
1151 for (instantiated_arg_index, arg) in args.iter().enumerate() {
1152 match arg {
1153 Term::Var(..) | Term::AnonVar => {}
1154 _ => {
1155 if optimal_index != instantiated_arg_index {
1156 if left >= right {
1157 optimal_index = instantiated_arg_index;
1158 continue 'outer;
1159 }
1160
1161 subseqs.push(ClauseSpan {
1162 left,
1163 right,
1164 instantiated_arg_index: optimal_index,
1165 });
1166
1167 optimal_index = instantiated_arg_index;
1168 left = right;
1169 }
1170
1171 continue 'outer;
1172 }
1173 }
1174 }
1175 }
1176
1177 if left < right {
1178 subseqs.push(ClauseSpan {
1179 left,
1180 right,
1181 instantiated_arg_index: optimal_index,
1182 });
1183 }
1184
1185 optimal_index = 0;
1186
1187 subseqs.push(ClauseSpan {
1188 left: right,
1189 right: right + 1,
1190 instantiated_arg_index: optimal_index,
1191 });
1192
1193 left = right + 1;
1194 }
1195
1196 if left < clauses.len() {
1197 subseqs.push(ClauseSpan {
1198 left,
1199 right: clauses.len(),
1200 instantiated_arg_index: optimal_index,
1201 });
1202 }
1203
1204 subseqs
1205 }
1206
1207 fn compile_pred_subseq<I: Indexer>(
1208 &mut self,
1209 clauses: &mut [PredicateClause],
1210 optimal_index: usize,
1211 ) -> Result<Code, CompilationError> {
1212 let mut code = VecDeque::new();
1213 let mut code_offsets =
1214 CodeOffsets::new(I::new(), optimal_index + 1, self.settings.non_counted_bt);
1215
1216 let mut skip_stub_try_me_else = false;
1217 let clauses_len = clauses.len();
1218
1219 for (i, clause) in clauses.iter_mut().enumerate() {
1220 self.marker.reset();
1221
1222 let mut clause_index_info = ClauseIndexInfo::new(code.len());
1223
1224 let clause_code = match clause {
1225 PredicateClause::Fact(fact, var_data) => {
1226 let var_data = std::mem::take(var_data);
1227 self.compile_fact(fact, var_data)?
1228 }
1229 PredicateClause::Rule(rule, var_data) => {
1230 let var_data = std::mem::take(var_data);
1231 self.compile_rule(rule, var_data)?
1232 }
1233 };
1234
1235 if clauses_len > 1 {
1236 let choice = match i {
1237 0 => self.settings.internal_try_me_else(clause_code.len() + 1),
1238 _ if i + 1 == clauses_len => self.settings.internal_trust_me(),
1239 _ => self.settings.internal_retry_me_else(clause_code.len() + 1),
1240 };
1241
1242 code.push_back(choice);
1243 } else if self.settings.is_extensible {
1244 code.push_front(self.settings.internal_try_me_else(0));
1256 skip_stub_try_me_else = !self.settings.is_dynamic();
1257 }
1258
1259 let arg = clause.args().and_then(|args| args.get(optimal_index));
1260
1261 if let Some(arg) = arg {
1262 let index = code.len();
1263
1264 if clauses_len > 1 || self.settings.is_extensible {
1265 code_offsets.index_term(arg, index, &mut clause_index_info, self.atom_tbl);
1266 }
1267 }
1268
1269 self.skeleton.clauses.push_back(clause_index_info);
1270 code.extend(clause_code.into_iter());
1271 }
1272
1273 let index_code = if clauses_len > 1 || self.settings.is_extensible {
1274 code_offsets.compute_indices(skip_stub_try_me_else)
1275 } else {
1276 vec![]
1277 };
1278
1279 if !index_code.is_empty() {
1280 code.push_front(Instruction::IndexingCode(index_code));
1281 } else if clauses.len() == 1 && self.settings.is_extensible {
1282 code.pop_front();
1288 }
1289
1290 Ok(Vec::from(code))
1291 }
1292
1293 pub(crate) fn compile_predicate(
1294 &mut self,
1295 mut clauses: Vec<PredicateClause>,
1296 ) -> Result<Code, CompilationError> {
1297 let mut code = Code::new();
1298
1299 let split_pred = Self::split_predicate(&clauses);
1300 let multi_seq = split_pred.len() > 1;
1301
1302 for ClauseSpan {
1303 left,
1304 right,
1305 instantiated_arg_index,
1306 } in split_pred
1307 {
1308 let skel_lower_bound = self.skeleton.clauses.len();
1309 let code_segment = if self.settings.is_dynamic() {
1310 self.compile_pred_subseq::<DynamicCodeIndices>(
1311 &mut clauses[left..right],
1312 instantiated_arg_index,
1313 )?
1314 } else {
1315 self.compile_pred_subseq::<StaticCodeIndices>(
1316 &mut clauses[left..right],
1317 instantiated_arg_index,
1318 )?
1319 };
1320
1321 let clause_start_offset = code.len();
1322
1323 if multi_seq {
1324 let choice = match left {
1325 0 => self.settings.try_me_else(code_segment.len() + 1),
1326 _ if right == clauses.len() => self.settings.trust_me(),
1327 _ => self.settings.retry_me_else(code_segment.len() + 1),
1328 };
1329
1330 code.push(choice);
1331 } else if self.settings.is_extensible {
1332 code.push(self.settings.try_me_else(0));
1333 }
1334
1335 if self.settings.is_extensible {
1336 let segment_is_indexed = code_segment[0].to_indexing_line().is_some();
1337
1338 for clause_index_info in
1339 self.skeleton.clauses.make_contiguous()[skel_lower_bound..].iter_mut()
1340 {
1341 clause_index_info.clause_start +=
1342 clause_start_offset + 2 * (segment_is_indexed as usize);
1343 clause_index_info.opt_arg_index_key += clause_start_offset + 1;
1344 }
1345 }
1346
1347 code.extend(code_segment.into_iter());
1348 }
1349
1350 Ok(code)
1351 }
1352}