erg_compiler/ty/
free.rs

1use std::cell::{BorrowError, BorrowMutError, Ref, RefMut};
2use std::fmt;
3use std::hash::{Hash, Hasher};
4use std::mem;
5use std::sync::atomic::AtomicUsize;
6
7use erg_common::consts::DEBUG_MODE;
8use erg_common::shared::Forkable;
9use erg_common::traits::{LimitedDisplay, StructuralEq};
10use erg_common::Str;
11use erg_common::{addr, addr_eq, log};
12
13use super::typaram::TyParam;
14use super::Type;
15
16pub type Level = usize;
17pub type Id = usize;
18
19/// HACK: see doc/compiler/inference.md for details
20pub const GENERIC_LEVEL: usize = usize::MAX;
21static UNBOUND_ID: AtomicUsize = AtomicUsize::new(0);
22
23pub trait HasLevel {
24    fn level(&self) -> Option<Level>;
25    fn set_level(&self, lev: Level);
26    fn set_lower(&self, level: Level) {
27        if self.level() < Some(level) {
28            self.set_level(level);
29        }
30    }
31    fn lift(&self) {
32        if let Some(lev) = self.level() {
33            self.set_level(lev.saturating_add(1));
34        }
35    }
36    fn lower(&self) {
37        if let Some(lev) = self.level() {
38            self.set_level(lev.saturating_sub(1));
39        }
40    }
41    fn generalize(&self) {
42        self.set_level(GENERIC_LEVEL);
43    }
44    fn is_generalized(&self) -> bool {
45        self.level() == Some(GENERIC_LEVEL)
46    }
47}
48
49/// Represents constraints on type variables and type parameters.
50///
51/// Note that constraints can have circular references. However, type variable (`FreeTyVar`) is defined with various operations avoiding infinite recursion.
52///
53/// __NOTE__: you should use `Free::get_type/get_subsup` instead of deconstructing the constraint by `match`.
54/// Constraints may contain cycles, in which case using `match` to get the contents will cause memory destructions.
55#[derive(Debug, Clone, PartialEq, Eq, Hash)]
56pub enum Constraint {
57    // : Type --> (:> Never, <: Obj)
58    // :> Sub --> (:> Sub, <: Obj)
59    // <: Sup --> (:> Never, <: Sup)
60    /// :> Sub, <: Sup
61    Sandwiched {
62        sub: Type,
63        sup: Type,
64    },
65    // : Int, ...
66    TypeOf(Type),
67    Uninited,
68}
69
70impl fmt::Display for Constraint {
71    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
72        self.limited_fmt(f, <Self as LimitedDisplay>::DEFAULT_LIMIT)
73    }
74}
75
76impl LimitedDisplay for Constraint {
77    fn limited_fmt<W: std::fmt::Write>(&self, f: &mut W, limit: isize) -> fmt::Result {
78        if limit == 0 {
79            return write!(f, "...");
80        }
81        match self {
82            Self::Sandwiched { sub, sup } => match (sub == &Type::Never, sup == &Type::Obj) {
83                (true, true) => {
84                    write!(f, ": Type")?;
85                    if DEBUG_MODE {
86                        write!(f, "(:> Never, <: Obj)")?;
87                    }
88                    Ok(())
89                }
90                (true, false) => {
91                    write!(f, "<: ")?;
92                    sup.limited_fmt(f, limit - 1)?;
93                    Ok(())
94                }
95                (false, true) => {
96                    write!(f, ":> ")?;
97                    sub.limited_fmt(f, limit - 1)?;
98                    Ok(())
99                }
100                (false, false) => {
101                    write!(f, ":> ")?;
102                    sub.limited_fmt(f, limit - 1)?;
103                    write!(f, ", <: ")?;
104                    sup.limited_fmt(f, limit - 1)?;
105                    Ok(())
106                }
107            },
108            Self::TypeOf(t) => {
109                write!(f, ": ")?;
110                t.limited_fmt(f, limit - 1)
111            }
112            Self::Uninited => write!(f, "<uninited>"),
113        }
114    }
115}
116
117impl Constraint {
118    /// :> Sub, <: Sup
119    pub const fn new_sandwiched(sub: Type, sup: Type) -> Self {
120        Self::Sandwiched { sub, sup }
121    }
122
123    pub fn named_fmt(&self, f: &mut impl fmt::Write, name: &str, limit: isize) -> fmt::Result {
124        if limit == 0 {
125            return write!(f, "...");
126        }
127        match self {
128            Self::Sandwiched { sub, sup } => match (sub == &Type::Never, sup == &Type::Obj) {
129                (true, true) => {
130                    write!(f, "{name}: Type")?;
131                    Ok(())
132                }
133                (true, false) => {
134                    write!(f, "{name} <: ")?;
135                    sup.limited_fmt(f, limit - 1)?;
136                    Ok(())
137                }
138                (false, true) => {
139                    write!(f, "{name} :> ")?;
140                    sub.limited_fmt(f, limit - 1)?;
141                    Ok(())
142                }
143                (false, false) => {
144                    write!(f, "{name} :> ")?;
145                    sub.limited_fmt(f, limit - 1)?;
146                    write!(f, ", {name} <: ")?;
147                    sup.limited_fmt(f, limit - 1)?;
148                    Ok(())
149                }
150            },
151            Self::TypeOf(t) => {
152                write!(f, "{name}: ")?;
153                t.limited_fmt(f, limit - 1)
154            }
155            Self::Uninited => write!(f, "Never"),
156        }
157    }
158
159    pub fn new_type_of(t: Type) -> Self {
160        if t == Type::Type {
161            Self::new_sandwiched(Type::Never, Type::Obj)
162        } else {
163            Self::TypeOf(t)
164        }
165    }
166
167    /// <: sup
168    pub const fn new_subtype_of(sup: Type) -> Self {
169        Self::new_sandwiched(Type::Never, sup)
170    }
171
172    /// :> sub
173    pub const fn new_supertype_of(sub: Type) -> Self {
174        Self::new_sandwiched(sub, Type::Obj)
175    }
176
177    pub const fn is_uninited(&self) -> bool {
178        matches!(self, Self::Uninited)
179    }
180
181    pub fn lift(&self) {
182        match self {
183            Self::Sandwiched { sub, sup, .. } => {
184                sub.lift();
185                sup.lift();
186            }
187            Self::TypeOf(t) => t.lift(),
188            Self::Uninited => {}
189        }
190    }
191
192    pub fn get_type(&self) -> Option<&Type> {
193        match self {
194            Self::TypeOf(ty) => Some(ty),
195            Self::Sandwiched {
196                sub: Type::Never,
197                sup: Type::Obj,
198                ..
199            } => Some(&Type::Type),
200            _ => None,
201        }
202    }
203
204    /// :> Sub
205    pub fn get_sub(&self) -> Option<&Type> {
206        match self {
207            Self::Sandwiched { sub, .. } => Some(sub),
208            _ => None,
209        }
210    }
211
212    /// <: Sup
213    pub fn get_super(&self) -> Option<&Type> {
214        match self {
215            Self::Sandwiched { sup, .. } => Some(sup),
216            _ => None,
217        }
218    }
219
220    /// :> Sub, <: Sup
221    pub fn get_sub_sup(&self) -> Option<(&Type, &Type)> {
222        match self {
223            Self::Sandwiched { sub, sup, .. } => Some((sub, sup)),
224            _ => None,
225        }
226    }
227
228    pub fn get_super_mut(&mut self) -> Option<&mut Type> {
229        match self {
230            Self::Sandwiched { sup, .. } => Some(sup),
231            _ => None,
232        }
233    }
234
235    /// e.g.
236    /// ```erg
237    /// old_sub: ?T, constraint: (:> ?T or NoneType, <: Obj)
238    /// -> constraint: (:> NoneType, <: Obj)
239    /// ```
240    pub fn eliminate_subsup_recursion(self, target: &Type) -> Self {
241        match self {
242            Self::Sandwiched { sub, sup } => {
243                if sub.addr_eq(target) && sup.addr_eq(target) {
244                    Self::new_type_of(Type::Type)
245                } else if sub.addr_eq(target) {
246                    let sup = sup.eliminate_subsup(target);
247                    Self::new_subtype_of(sup)
248                } else if sup.addr_eq(target) {
249                    let sub = sub.eliminate_subsup(target);
250                    Self::new_supertype_of(sub)
251                } else {
252                    let sub = sub.eliminate_subsup(target);
253                    let sup = sup.eliminate_subsup(target);
254                    Self::new_sandwiched(sub, sup)
255                }
256            }
257            Self::TypeOf(t) => Self::new_type_of(t.eliminate_subsup(target)),
258            other => other,
259        }
260    }
261
262    pub fn to_type_constraint(self) -> Constraint {
263        match self {
264            Self::TypeOf(Type::Type) => Constraint::new_sandwiched(Type::Never, Type::Obj),
265            _ => self,
266        }
267    }
268}
269
270pub trait CanbeFree {
271    fn unbound_name(&self) -> Option<Str>;
272    fn unbound_id(&self) -> Option<usize>;
273    fn constraint(&self) -> Option<Constraint>;
274    fn destructive_update_constraint(&self, constraint: Constraint, in_instantiation: bool);
275}
276
277impl<T: CanbeFree + Send + Clone> Free<T> {
278    pub fn unbound_name(&self) -> Option<Str> {
279        self.borrow().unbound_name()
280    }
281
282    pub fn unbound_id(&self) -> Option<usize> {
283        self.borrow().unbound_id()
284    }
285
286    pub fn constraint(&self) -> Option<Constraint> {
287        self.borrow().constraint()
288    }
289}
290
291#[derive(Debug, Clone, Eq)]
292pub enum FreeKind<T> {
293    Linked(T),
294    UndoableLinked {
295        t: T,
296        previous: Box<FreeKind<T>>,
297        count: usize,
298    },
299    Unbound {
300        id: Id,
301        lev: Level,
302        constraint: Constraint,
303    },
304    NamedUnbound {
305        name: Str,
306        id: Id,
307        lev: Level,
308        constraint: Constraint,
309    },
310}
311
312impl<T: Hash> Hash for FreeKind<T> {
313    fn hash<H: Hasher>(&self, state: &mut H) {
314        match self {
315            Self::Linked(t) | Self::UndoableLinked { t, .. } => t.hash(state),
316            Self::Unbound { id, .. } | Self::NamedUnbound { id, .. } => {
317                id.hash(state);
318            }
319        }
320    }
321}
322
323impl<T: PartialEq> PartialEq for FreeKind<T> {
324    fn eq(&self, other: &Self) -> bool {
325        match (self, other) {
326            (
327                Self::Linked(t1) | Self::UndoableLinked { t: t1, .. },
328                Self::Linked(t2) | Self::UndoableLinked { t: t2, .. },
329            ) => t1 == t2,
330            (Self::Unbound { id: id1, .. }, Self::Unbound { id: id2, .. })
331            | (Self::NamedUnbound { id: id1, .. }, Self::NamedUnbound { id: id2, .. }) => {
332                id1 == id2
333            }
334            _ => false,
335        }
336    }
337}
338
339impl<T: CanbeFree> FreeKind<T> {
340    pub fn unbound_name(&self) -> Option<Str> {
341        match self {
342            FreeKind::NamedUnbound { name, .. } => Some(name.clone()),
343            FreeKind::Unbound { id, .. } => Some(Str::from(format!("%{id}"))),
344            FreeKind::Linked(t) | FreeKind::UndoableLinked { t, .. } => t.unbound_name(),
345        }
346    }
347
348    pub fn unbound_id(&self) -> Option<usize> {
349        match self {
350            FreeKind::NamedUnbound { id, .. } | FreeKind::Unbound { id, .. } => Some(*id),
351            FreeKind::Linked(t) | FreeKind::UndoableLinked { t, .. } => t.unbound_id(),
352        }
353    }
354
355    pub fn constraint(&self) -> Option<Constraint> {
356        match self {
357            FreeKind::Unbound { constraint, .. } | FreeKind::NamedUnbound { constraint, .. } => {
358                Some(constraint.clone())
359            }
360            FreeKind::Linked(t) | FreeKind::UndoableLinked { t, .. } => t.constraint(),
361        }
362    }
363}
364
365impl<T: LimitedDisplay> fmt::Display for FreeKind<T> {
366    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
367        self.limited_fmt(f, <Self as LimitedDisplay>::DEFAULT_LIMIT)
368    }
369}
370
371impl<T: LimitedDisplay> LimitedDisplay for FreeKind<T> {
372    fn limited_fmt<W: std::fmt::Write>(&self, f: &mut W, limit: isize) -> fmt::Result {
373        if limit == 0 {
374            return write!(f, "...");
375        }
376        match self {
377            Self::Linked(t) | Self::UndoableLinked { t, .. } => {
378                if DEBUG_MODE {
379                    write!(f, "(")?;
380                    t.limited_fmt(f, limit)?;
381                    write!(f, ")")
382                } else {
383                    t.limited_fmt(f, limit)
384                }
385            }
386            Self::NamedUnbound {
387                name,
388                id: _,
389                lev,
390                constraint,
391            } => {
392                if *lev == GENERIC_LEVEL {
393                    write!(f, "{name}")?;
394                    if DEBUG_MODE {
395                        write!(f, "(")?;
396                        constraint.limited_fmt(f, limit - 1)?;
397                        write!(f, ")")?;
398                    }
399                } else {
400                    write!(f, "?{name}")?;
401                    if DEBUG_MODE {
402                        write!(f, "(")?;
403                        constraint.limited_fmt(f, limit - 1)?;
404                        write!(f, ")")?;
405                        write!(f, "[{lev}]")?;
406                    }
407                }
408                Ok(())
409            }
410            Self::Unbound {
411                id,
412                lev,
413                constraint,
414            } => {
415                if *lev == GENERIC_LEVEL {
416                    write!(f, "%{id}")?;
417                    if DEBUG_MODE {
418                        write!(f, "(")?;
419                        constraint.limited_fmt(f, limit - 1)?;
420                        write!(f, ")")?;
421                    }
422                } else {
423                    write!(f, "?{id}")?;
424                    if DEBUG_MODE {
425                        write!(f, "(")?;
426                        constraint.limited_fmt(f, limit - 1)?;
427                        write!(f, ")")?;
428                        write!(f, "[{lev}]")?;
429                    }
430                }
431                Ok(())
432            }
433        }
434    }
435}
436
437impl<T> FreeKind<T> {
438    pub const fn unbound(id: Id, lev: Level, constraint: Constraint) -> Self {
439        Self::Unbound {
440            id,
441            lev,
442            constraint,
443        }
444    }
445
446    pub fn new_unbound(lev: Level, constraint: Constraint) -> Self {
447        UNBOUND_ID.fetch_add(1, std::sync::atomic::Ordering::SeqCst);
448        Self::Unbound {
449            id: UNBOUND_ID.load(std::sync::atomic::Ordering::SeqCst),
450            lev,
451            constraint,
452        }
453    }
454
455    pub const fn named_unbound(name: Str, id: usize, lev: Level, constraint: Constraint) -> Self {
456        Self::NamedUnbound {
457            name,
458            id,
459            lev,
460            constraint,
461        }
462    }
463
464    pub const fn linked(&self) -> Option<&T> {
465        match self {
466            Self::Linked(t) | Self::UndoableLinked { t, .. } => Some(t),
467            _ => None,
468        }
469    }
470
471    pub fn linked_mut(&mut self) -> Option<&mut T> {
472        match self {
473            Self::Linked(t) | Self::UndoableLinked { t, .. } => Some(t),
474            _ => None,
475        }
476    }
477
478    /// SAFETY: carefully ensure that `to` is not a freevar equal to `self`
479    ///
480    /// e.g.
481    /// ```erg
482    /// x = ?T
483    /// x.replace(Type::Free(?T))
484    /// x == (((...)))
485    /// ```
486    pub fn replace(&mut self, to: T) {
487        match self {
488            // REVIEW: What if `t` is also an unbound variable?
489            Self::Linked(t) | Self::UndoableLinked { t, .. } => {
490                *t = to;
491            }
492            _ => {
493                *self = Self::Linked(to);
494            }
495        }
496    }
497
498    pub const fn is_named_unbound(&self) -> bool {
499        matches!(self, Self::NamedUnbound { .. })
500    }
501
502    pub const fn is_unnamed_unbound(&self) -> bool {
503        matches!(self, Self::Unbound { .. })
504    }
505
506    pub const fn is_undoable_linked(&self) -> bool {
507        matches!(self, Self::UndoableLinked { .. })
508    }
509
510    pub fn undo_count(&self) -> usize {
511        match self {
512            Self::UndoableLinked { count, .. } => *count,
513            _ => 0,
514        }
515    }
516
517    pub fn inc_undo_count(&mut self) {
518        #[allow(clippy::single_match)]
519        match self {
520            Self::UndoableLinked { count, .. } => *count += 1,
521            _ => {}
522        }
523    }
524
525    pub fn dec_undo_count(&mut self) {
526        #[allow(clippy::single_match)]
527        match self {
528            Self::UndoableLinked { count, .. } => *count -= 1,
529            _ => {}
530        }
531    }
532
533    pub fn get_previous(&self) -> Option<&FreeKind<T>> {
534        match self {
535            Self::UndoableLinked { previous, .. } => Some(previous),
536            _ => None,
537        }
538    }
539}
540
541#[derive(Debug, Clone)]
542pub struct Free<T: Send + Clone>(Forkable<FreeKind<T>>);
543
544impl Hash for Free<Type> {
545    fn hash<H: Hasher>(&self, state: &mut H) {
546        if let Some(id) = self.unbound_id() {
547            id.hash(state);
548        } else if self.is_linked() {
549            let cracked = self.crack();
550            if !Type::FreeVar(self.clone()).addr_eq(&cracked) {
551                cracked.hash(state);
552            } else {
553                addr!(self).hash(state);
554            }
555        }
556    }
557}
558
559impl Hash for Free<TyParam> {
560    fn hash<H: Hasher>(&self, state: &mut H) {
561        if let Some(id) = self.unbound_id() {
562            id.hash(state);
563        } else if self.is_linked() {
564            self.crack().hash(state);
565        }
566    }
567}
568
569impl PartialEq for Free<Type> {
570    fn eq(&self, other: &Self) -> bool {
571        let linked = self.linked_free();
572        let this = if let Some(linked) = &linked {
573            linked
574        } else {
575            self
576        };
577        let linked = other.linked_free();
578        let other = if let Some(linked) = &linked {
579            linked
580        } else {
581            other
582        };
583        if let Some(self_id) = this.unbound_id() {
584            if let Some(other_id) = other.unbound_id() {
585                self_id == other_id
586            } else {
587                false
588            }
589        } else if this.is_linked() {
590            if other.is_linked() {
591                this.crack().eq(&other.crack())
592            } else {
593                false
594            }
595        } else {
596            false
597        }
598    }
599}
600
601impl PartialEq for Free<TyParam> {
602    fn eq(&self, other: &Self) -> bool {
603        let linked = self.linked_free();
604        let this = if let Some(linked) = &linked {
605            linked
606        } else {
607            self
608        };
609        let linked = other.linked_free();
610        let other = if let Some(linked) = &linked {
611            linked
612        } else {
613            other
614        };
615        if let Some(self_id) = this.unbound_id() {
616            if let Some(other_id) = other.unbound_id() {
617                self_id == other_id
618            } else {
619                false
620            }
621        } else if this.is_linked() {
622            if other.is_linked() {
623                this.crack().eq(&other.crack())
624            } else {
625                false
626            }
627        } else {
628            false
629        }
630    }
631}
632
633impl Eq for Free<Type> {}
634impl Eq for Free<TyParam> {}
635
636impl<T: LimitedDisplay + Send + Clone> fmt::Display for Free<T> {
637    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
638        write!(f, "{}", self.0.borrow())
639    }
640}
641
642impl<T: LimitedDisplay + Send + Clone> LimitedDisplay for Free<T> {
643    fn limited_fmt<W: std::fmt::Write>(&self, f: &mut W, limit: isize) -> fmt::Result {
644        self.0.borrow().limited_fmt(f, limit)
645    }
646}
647
648impl<T: Send + Clone> Free<T> {
649    #[track_caller]
650    pub fn borrow(&self) -> Ref<'_, FreeKind<T>> {
651        self.0.borrow()
652    }
653    #[track_caller]
654    pub fn borrow_mut(&self) -> RefMut<'_, FreeKind<T>> {
655        self.0.borrow_mut()
656    }
657    #[track_caller]
658    pub fn try_borrow(&self) -> Result<Ref<'_, FreeKind<T>>, BorrowError> {
659        self.0.try_borrow()
660    }
661    #[track_caller]
662    pub fn try_borrow_mut(&self) -> Result<RefMut<'_, FreeKind<T>>, BorrowMutError> {
663        self.0.try_borrow_mut()
664    }
665    /// very unsafe, use `force_replace` instead whenever possible
666    pub fn as_ptr(&self) -> *mut FreeKind<T> {
667        self.0.as_ptr()
668    }
669    pub fn forced_as_ref(&self) -> &FreeKind<T> {
670        unsafe { self.as_ptr().as_ref() }.unwrap()
671    }
672    pub fn forced_as_mut(&mut self) -> &mut FreeKind<T> {
673        unsafe { self.as_ptr().as_mut() }.unwrap()
674    }
675}
676
677impl Free<Type> {
678    /// (T) => T
679    /// ((T)) => T
680    pub fn linked_free(&self) -> Option<Free<Type>> {
681        let linked = self.get_linked()?;
682        let fv = linked.as_free()?;
683        if let Some(fv) = fv.linked_free() {
684            Some(fv)
685        } else {
686            Some(self.clone())
687        }
688    }
689
690    pub fn is_recursive(&self) -> bool {
691        Type::FreeVar(self.clone()).is_recursive()
692    }
693
694    /// interior-mut
695    fn _do_avoiding_recursion<O, F: FnOnce() -> O>(&self, placeholder: Option<&Type>, f: F) -> O {
696        let placeholder = placeholder.unwrap_or(&Type::Failure);
697        let is_recursive = self.is_recursive();
698        if is_recursive {
699            let target = Type::FreeVar(self.clone());
700            let placeholder_ = placeholder
701                .clone()
702                .eliminate_subsup(&target)
703                .eliminate_recursion(&target);
704            self.undoable_link(&placeholder_);
705        }
706        let res = f();
707        if is_recursive {
708            self.undo();
709        }
710        res
711    }
712
713    /// interior-mut
714    pub fn do_avoiding_recursion<O>(&self, f: impl FnOnce() -> O) -> O {
715        self._do_avoiding_recursion(None, f)
716    }
717
718    /// interior-mut
719    pub fn do_avoiding_recursion_with<O>(&self, placeholder: &Type, f: impl FnOnce() -> O) -> O {
720        self._do_avoiding_recursion(Some(placeholder), f)
721    }
722
723    pub fn has_unbound_var(&self) -> bool {
724        if self.is_unbound() {
725            true
726        } else {
727            self.crack().has_unbound_var()
728        }
729    }
730
731    /// interior-mut
732    /// if `in_inst_or_gen` is true, constraint will be updated forcibly
733    pub(super) fn update_constraint(&self, new_constraint: Constraint, in_inst_or_gen: bool) {
734        if new_constraint.get_type() == Some(&Type::Never) {
735            panic!("{new_constraint}");
736        }
737        // self: T
738        // new_constraint: (:> T, <: U) => <: U
739        if new_constraint.get_sub_sup().is_some_and(|(sub, sup)| {
740            sub.contains_tvar_in_constraint(self) || sup.contains_tvar_in_constraint(self)
741        }) {
742            return;
743        }
744        if let Some(linked) = self.get_linked() {
745            linked.destructive_update_constraint(new_constraint, in_inst_or_gen);
746        } else {
747            match &mut *self.borrow_mut() {
748                FreeKind::Unbound {
749                    lev, constraint, ..
750                }
751                | FreeKind::NamedUnbound {
752                    lev, constraint, ..
753                } => {
754                    if !in_inst_or_gen && *lev == GENERIC_LEVEL {
755                        log!(err "cannot update the constraint of a generalized type variable");
756                        return;
757                    }
758                    if addr_eq!(*constraint, new_constraint) {
759                        return;
760                    }
761                    *constraint = new_constraint;
762                }
763                FreeKind::Linked(_) | FreeKind::UndoableLinked { .. } => unreachable!(),
764            }
765        }
766    }
767}
768
769impl Free<TyParam> {
770    /// (T) => T
771    /// ((T)) => T
772    pub fn linked_free(&self) -> Option<Free<TyParam>> {
773        let linked = self.get_linked()?;
774        let fv = linked.as_free()?;
775        if let Some(fv) = fv.linked_free() {
776            Some(fv)
777        } else {
778            Some(self.clone())
779        }
780    }
781
782    pub fn is_recursive(&self) -> bool {
783        TyParam::FreeVar(self.clone()).is_recursive()
784    }
785
786    fn _do_avoiding_recursion<O, F: FnOnce() -> O>(
787        &self,
788        placeholder: Option<&TyParam>,
789        f: F,
790    ) -> O {
791        let placeholder = placeholder.unwrap_or(&TyParam::Failure);
792        let is_recursive = self.is_recursive();
793        if is_recursive {
794            let target = TyParam::FreeVar(self.clone());
795            let placeholder_ = placeholder.clone().eliminate_recursion(&target);
796            self.undoable_link(&placeholder_);
797        }
798        let res = f();
799        if is_recursive {
800            self.undo();
801        }
802        res
803    }
804
805    pub fn do_avoiding_recursion<O, F: FnOnce() -> O>(&self, f: F) -> O {
806        self._do_avoiding_recursion(None, f)
807    }
808
809    pub fn do_avoiding_recursion_with<O, F: FnOnce() -> O>(
810        &self,
811        placeholder: &TyParam,
812        f: F,
813    ) -> O {
814        self._do_avoiding_recursion(Some(placeholder), f)
815    }
816
817    pub fn has_unbound_var(&self) -> bool {
818        if self.is_unbound() {
819            true
820        } else {
821            self.crack().has_unbound_var()
822        }
823    }
824}
825
826impl<T: StructuralEq + CanbeFree + Clone + Default + fmt::Debug + Send + Sync + 'static>
827    StructuralEq for Free<T>
828{
829    fn structural_eq(&self, other: &Self) -> bool {
830        if let (Some((l, r)), Some((l2, r2))) = (self.get_subsup(), other.get_subsup()) {
831            self.dummy_link();
832            other.dummy_link();
833            let res = l.structural_eq(&l2) && r.structural_eq(&r2);
834            self.undo();
835            other.undo();
836            res
837        } else if let (Some(l), Some(r)) = (self.get_type(), other.get_type()) {
838            l.structural_eq(&r)
839        } else {
840            self.constraint_is_uninited() && other.constraint_is_uninited()
841        }
842    }
843}
844
845impl<T: Send + Clone> Free<T> {
846    pub fn clone_inner(&self) -> FreeKind<T> {
847        self.0.clone_inner()
848    }
849
850    pub fn update_init(&mut self) {
851        self.0.update_init();
852    }
853}
854
855impl HasLevel for Free<Type> {
856    fn set_level(&self, level: Level) {
857        match &mut *self.borrow_mut() {
858            FreeKind::Unbound { lev, .. } | FreeKind::NamedUnbound { lev, .. } => {
859                if addr_eq!(*lev, level) {
860                    return;
861                }
862                *lev = level;
863            }
864            _ => {}
865        }
866        if let Some(linked) = self.get_linked() {
867            linked.set_level(level);
868        } else if let Some((sub, sup)) = self.get_subsup() {
869            self.do_avoiding_recursion(|| {
870                sub.set_level(level);
871                sup.set_level(level);
872            });
873        } else if let Some(t) = self.get_type() {
874            t.set_level(level);
875        }
876    }
877
878    fn level(&self) -> Option<Level> {
879        match &*self.borrow() {
880            FreeKind::Unbound { lev, .. } | FreeKind::NamedUnbound { lev, .. } => Some(*lev),
881            FreeKind::Linked(t) | FreeKind::UndoableLinked { t, .. } => t.level(),
882        }
883    }
884}
885
886impl HasLevel for Free<TyParam> {
887    fn set_level(&self, level: Level) {
888        match &mut *self.borrow_mut() {
889            FreeKind::Unbound { lev, .. } | FreeKind::NamedUnbound { lev, .. } => {
890                if addr_eq!(*lev, level) {
891                    return;
892                }
893                *lev = level;
894            }
895            _ => {}
896        }
897        if let Some(linked) = self.get_linked() {
898            linked.set_level(level);
899        } else if let Some(t) = self.get_type() {
900            t.set_level(level);
901        }
902    }
903
904    fn level(&self) -> Option<Level> {
905        match &*self.borrow() {
906            FreeKind::Unbound { lev, .. } | FreeKind::NamedUnbound { lev, .. } => Some(*lev),
907            FreeKind::Linked(t) | FreeKind::UndoableLinked { t, .. } => {
908                if t.is_recursive() {
909                    None
910                } else {
911                    t.level()
912                }
913            }
914        }
915    }
916}
917
918impl<T: Send + Clone + CanbeFree> Free<T>
919where
920    Free<T>: HasLevel,
921{
922    pub fn deep_clone(&self) -> Self {
923        Self::new_named_unbound(
924            self.unbound_name().unwrap(),
925            self.level().unwrap(),
926            self.constraint().unwrap(),
927        )
928    }
929}
930
931impl<T: Send + Clone> Free<T> {
932    pub fn new(f: FreeKind<T>) -> Self {
933        Self(Forkable::new(f))
934    }
935
936    pub fn new_unbound(level: Level, constraint: Constraint) -> Self {
937        let id = UNBOUND_ID.fetch_add(1, std::sync::atomic::Ordering::SeqCst);
938        Self(Forkable::new(FreeKind::unbound(id + 1, level, constraint)))
939    }
940
941    pub fn new_named_unbound(name: Str, level: Level, constraint: Constraint) -> Self {
942        let id = UNBOUND_ID.fetch_add(1, std::sync::atomic::Ordering::SeqCst);
943        Self(Forkable::new(FreeKind::named_unbound(
944            name,
945            id + 1,
946            level,
947            constraint,
948        )))
949    }
950
951    pub fn new_linked(t: T) -> Self {
952        Self(Forkable::new(FreeKind::Linked(t)))
953    }
954
955    /// returns linked type (panic if self is unbounded)
956    /// NOTE: check by `.is_linked` before call
957    /// NOTE: Sometimes a `BorrowMut` error occurs when trying to pass the result of `crack().clone()` as an argument.
958    /// Bind it to a variable beforehand.
959    #[track_caller]
960    pub fn crack(&self) -> Ref<'_, T> {
961        Ref::map(self.borrow(), |f| match f {
962            FreeKind::Linked(t) | FreeKind::UndoableLinked { t, .. } => t,
963            FreeKind::Unbound { .. } | FreeKind::NamedUnbound { .. } => {
964                panic!("the value is unbounded")
965            }
966        })
967    }
968
969    #[track_caller]
970    pub fn crack_constraint(&self) -> Ref<'_, Constraint> {
971        Ref::map(self.borrow(), |f| match f {
972            FreeKind::Linked(_) | FreeKind::UndoableLinked { .. } => panic!("the value is linked"),
973            FreeKind::Unbound { constraint, .. } | FreeKind::NamedUnbound { constraint, .. } => {
974                constraint
975            }
976        })
977    }
978
979    pub fn unsafe_crack(&self) -> &T {
980        match unsafe { self.as_ptr().as_ref().unwrap() } {
981            FreeKind::Linked(t) | FreeKind::UndoableLinked { t, .. } => t,
982            FreeKind::Unbound { .. } | FreeKind::NamedUnbound { .. } => {
983                panic!("the value is unbounded")
984            }
985        }
986    }
987
988    pub fn addr_eq(&self, other: &Self) -> bool {
989        self.as_ptr() == other.as_ptr()
990    }
991}
992
993impl<T: Send + Sync + 'static + Clone> Free<T> {
994    pub fn is_linked(&self) -> bool {
995        self.borrow().linked().is_some()
996    }
997
998    pub fn is_undoable_linked(&self) -> bool {
999        self.borrow().is_undoable_linked()
1000    }
1001
1002    pub fn is_named_unbound(&self) -> bool {
1003        self.borrow().is_named_unbound()
1004    }
1005
1006    pub fn is_unnamed_unbound(&self) -> bool {
1007        self.borrow().is_unnamed_unbound()
1008    }
1009
1010    /// interior-mut
1011    #[track_caller]
1012    pub fn replace(&self, to: FreeKind<T>) {
1013        // prevent linking to self
1014        if self.is_linked() && addr_eq!(*self.borrow(), to) {
1015            return;
1016        }
1017        *self.borrow_mut() = to;
1018    }
1019}
1020
1021impl<T: Clone + Send + Sync + 'static> Free<T> {
1022    /// interior-mut
1023    /// SAFETY: use `Type/TyParam::link` instead of this.
1024    /// This method may cause circular references.
1025    #[track_caller]
1026    pub(super) fn link(&self, to: &T) {
1027        // prevent linking to self
1028        if self.is_linked() && addr_eq!(*self.crack(), *to) {
1029            return;
1030        }
1031        self.borrow_mut().replace(to.clone());
1032    }
1033
1034    /// interior-mut
1035    #[track_caller]
1036    pub(super) fn undoable_link(&self, to: &T) {
1037        if self.is_linked() && addr_eq!(*self.crack(), *to) {
1038            return;
1039        }
1040        let prev = self.clone_inner();
1041        let new = FreeKind::UndoableLinked {
1042            t: to.clone(),
1043            previous: Box::new(prev),
1044            count: 0,
1045        };
1046        *self.borrow_mut() = new;
1047    }
1048
1049    /// interior-mut
1050    pub fn undo(&self) {
1051        let prev = match &mut *self.borrow_mut() {
1052            FreeKind::UndoableLinked {
1053                previous, count, ..
1054            } => {
1055                if *count > 0 {
1056                    *count -= 1;
1057                    return;
1058                }
1059                *previous.clone()
1060            }
1061            _other => panic!("cannot undo"),
1062        };
1063        self.replace(prev);
1064    }
1065
1066    pub fn undo_stack_size(&self) -> usize {
1067        self.borrow().undo_count()
1068    }
1069
1070    pub fn inc_undo_count(&self) {
1071        self.borrow_mut().inc_undo_count();
1072    }
1073
1074    pub fn unwrap_unbound(self) -> (Option<Str>, usize, Constraint) {
1075        match self.clone_inner() {
1076            FreeKind::Linked(_) | FreeKind::UndoableLinked { .. } => panic!("the value is linked"),
1077            FreeKind::Unbound {
1078                constraint, lev, ..
1079            } => (None, lev, constraint),
1080            FreeKind::NamedUnbound {
1081                name,
1082                id: _,
1083                lev,
1084                constraint,
1085            } => (Some(name), lev, constraint),
1086        }
1087    }
1088
1089    pub fn unwrap_linked(&self) -> T {
1090        match self.clone_inner() {
1091            FreeKind::Linked(t) | FreeKind::UndoableLinked { t, .. } => t,
1092            FreeKind::Unbound { .. } | FreeKind::NamedUnbound { .. } => {
1093                panic!("the value is unbounded")
1094            }
1095        }
1096    }
1097
1098    pub fn get_linked(&self) -> Option<T> {
1099        if !self.is_linked() {
1100            None
1101        } else {
1102            Some(self.crack().clone())
1103        }
1104    }
1105
1106    #[track_caller]
1107    pub fn get_linked_ref(&self) -> Option<Ref<'_, T>> {
1108        Ref::filter_map(self.borrow(), |f| match f {
1109            FreeKind::Linked(t) | FreeKind::UndoableLinked { t, .. } => Some(t),
1110            FreeKind::Unbound { .. } | FreeKind::NamedUnbound { .. } => None,
1111        })
1112        .ok()
1113    }
1114
1115    #[track_caller]
1116    pub fn get_linked_refmut(&self) -> Option<RefMut<'_, T>> {
1117        RefMut::filter_map(self.borrow_mut(), |f| match f {
1118            FreeKind::Linked(t) | FreeKind::UndoableLinked { t, .. } => Some(t),
1119            FreeKind::Unbound { .. } | FreeKind::NamedUnbound { .. } => None,
1120        })
1121        .ok()
1122    }
1123
1124    #[track_caller]
1125    pub fn get_previous(&self) -> Option<Ref<'_, Box<FreeKind<T>>>> {
1126        Ref::filter_map(self.borrow(), |f| match f {
1127            FreeKind::UndoableLinked { previous, .. } => Some(previous),
1128            _ => None,
1129        })
1130        .ok()
1131    }
1132
1133    pub fn get_undoable_root(&self) -> Option<Ref<'_, FreeKind<T>>> {
1134        let mut prev = Ref::map(self.get_previous()?, |f| f.as_ref());
1135        loop {
1136            match Ref::filter_map(prev, |f| f.get_previous()) {
1137                Ok(p) => prev = p,
1138                Err(p) => {
1139                    prev = p;
1140                    break;
1141                }
1142            }
1143        }
1144        Some(prev)
1145    }
1146
1147    pub fn detach(&self) -> Self {
1148        match self.clone().unwrap_unbound() {
1149            (Some(name), lev, constraint) => Self::new_named_unbound(name, lev, constraint),
1150            (None, lev, constraint) => Self::new_unbound(lev, constraint),
1151        }
1152    }
1153}
1154
1155impl<T: Default + Clone + fmt::Debug + Send + Sync + 'static> Free<T> {
1156    /// interior-mut
1157    #[track_caller]
1158    pub fn dummy_link(&self) {
1159        self.undoable_link(&T::default());
1160    }
1161}
1162
1163impl<T: CanbeFree + Send + Clone> Free<T> {
1164    pub fn get_type(&self) -> Option<Type> {
1165        self.constraint().and_then(|c| c.get_type().cloned())
1166    }
1167
1168    /// <: Super
1169    pub fn get_super(&self) -> Option<Type> {
1170        self.constraint().and_then(|c| c.get_super().cloned())
1171    }
1172
1173    /// :> Sub
1174    pub fn get_sub(&self) -> Option<Type> {
1175        self.constraint().and_then(|c| c.get_sub().cloned())
1176    }
1177
1178    /// :> Sub, <: Super
1179    pub fn get_subsup(&self) -> Option<(Type, Type)> {
1180        self.constraint()
1181            .and_then(|c| c.get_sub_sup().map(|(sub, sup)| (sub.clone(), sup.clone())))
1182    }
1183
1184    pub fn is_unbound(&self) -> bool {
1185        matches!(
1186            &*self.borrow(),
1187            FreeKind::Unbound { .. } | FreeKind::NamedUnbound { .. }
1188        )
1189    }
1190
1191    pub fn is_unbound_and_sandwiched(&self) -> bool {
1192        self.is_unbound() && self.constraint_is_sandwiched()
1193    }
1194
1195    pub fn is_unbound_and_typed(&self) -> bool {
1196        self.is_unbound() && self.constraint_is_typeof()
1197    }
1198
1199    pub fn constraint_is_typeof(&self) -> bool {
1200        self.constraint()
1201            .map(|c| c.get_type().is_some())
1202            .unwrap_or(false)
1203    }
1204
1205    pub fn constraint_is_sandwiched(&self) -> bool {
1206        self.constraint()
1207            .map(|c| c.get_sub_sup().is_some())
1208            .unwrap_or(false)
1209    }
1210
1211    pub fn constraint_is_uninited(&self) -> bool {
1212        self.constraint().map(|c| c.is_uninited()).unwrap_or(false)
1213    }
1214}
1215
1216impl Free<TyParam> {
1217    pub fn map(&self, f: impl Fn(TyParam) -> TyParam) {
1218        if let Some(mut linked) = self.get_linked_refmut() {
1219            let mapped = f(mem::take(&mut *linked));
1220            *linked = mapped;
1221        }
1222    }
1223
1224    /// interior-mut
1225    /// if `in_inst_or_gen` is true, constraint will be updated forcibly
1226    pub fn update_constraint(&self, new_constraint: Constraint, in_inst_or_gen: bool) {
1227        if new_constraint.get_type() == Some(&Type::Never) {
1228            panic!("{new_constraint}");
1229        }
1230        if let Some(linked) = self.get_linked() {
1231            linked.destructive_update_constraint(new_constraint, in_inst_or_gen);
1232        } else {
1233            match &mut *self.borrow_mut() {
1234                FreeKind::Unbound {
1235                    lev, constraint, ..
1236                }
1237                | FreeKind::NamedUnbound {
1238                    lev, constraint, ..
1239                } => {
1240                    if !in_inst_or_gen && *lev == GENERIC_LEVEL {
1241                        log!(err "cannot update the constraint of a generalized type variable");
1242                        return;
1243                    }
1244                    if addr_eq!(*constraint, new_constraint) {
1245                        return;
1246                    }
1247                    *constraint = new_constraint;
1248                }
1249                FreeKind::Linked(_) | FreeKind::UndoableLinked { .. } => unreachable!(),
1250            }
1251        }
1252    }
1253
1254    /// interior-mut
1255    pub fn update_type(&self, new_type: Type) {
1256        let new_constraint = Constraint::new_type_of(new_type);
1257        self.update_constraint(new_constraint, true);
1258    }
1259}
1260
1261pub type FreeTyVar = Free<Type>;
1262pub type FreeTyParam = Free<TyParam>;
1263
1264mod tests {
1265    #![allow(unused_imports)]
1266    use erg_common::enable_overflow_stacktrace;
1267
1268    use crate::ty::constructors::*;
1269    use crate::ty::*;
1270    use crate::*;
1271
1272    #[test]
1273    fn cmp_freevar() {
1274        enable_overflow_stacktrace!();
1275        let t = named_uninit_var("T".into());
1276        let Type::FreeVar(fv) = t.clone() else {
1277            unreachable!()
1278        };
1279        let constraint = Constraint::new_subtype_of(poly("Add", vec![ty_tp(t.clone())]));
1280        fv.update_constraint(constraint.clone(), true);
1281        let u = named_free_var("T".into(), 1, constraint);
1282        println!("{t} {u}");
1283        assert_eq!(t, t);
1284        assert_ne!(t, u);
1285        assert!(t.structural_eq(&u));
1286    }
1287}
erg_compiler/ty/free.rs

erg_compiler/ty/
free.rs
