scryer_prolog/
codegen.rs

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                        // iterate over unset bits.
81                        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        // add 2 in each arm length to compensate for each jump
108        // instruction and each branch instruction not yet added.
109        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        // calls are inference counted by default if and only if
264        // backtracking is counted too.
265        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
324// if the final argument of the structure is a Literal::Index,
325// decrement the arity of the PutStructure instruction by 1.
326fn 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                // it is acceptable if arity == 0 is the result of
332                // this decrement. call/N will have to read the index
333                // constant for '$call_inline' to succeed. to find it,
334                // it must know the heap location of the index.
335                // self.store must stop before reading the atom into a
336                // register.
337
338                *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        // inlined predicates are never counted, so this overrides nothing.
814        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 var is an anonymous variable, insert
870                        // is/2 call so that an instantiation error is
871                        // thrown when the predicate is run.
872                        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                /*
1245                   generate stub choice instructions for extensible
1246                   predicates. if predicates are added to either the
1247                   inner or outer thread of choice instructions,
1248                   these stubs will be used, and surrounding indexing
1249                   instructions modified accordingly.
1250
1251                   until then, the v offset of SwitchOnTerm will skip
1252                   over them.
1253                */
1254
1255                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            // the condition is the value of skip_stub_try_me_else, which is
1283            // true if the predicate is not dynamic. This operation must apply
1284            // to dynamic predicates also, though.
1285
1286            // remove the TryMeElse(0).
1287            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}