/* * list.c - List related functions * * Copyright (c) 2000-2024 Shiro Kawai * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * 3. Neither the name of the authors nor the names of its contributors * may be used to endorse or promote products derived from this * software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #define LIBGAUCHE_BODY #include "gauche.h" #include "gauche/priv/pairP.h" /* * Classes */ static ScmClass *list_cpl[] = { SCM_CLASS_STATIC_PTR(Scm_ListClass), SCM_CLASS_STATIC_PTR(Scm_SequenceClass), SCM_CLASS_STATIC_PTR(Scm_CollectionClass), SCM_CLASS_STATIC_PTR(Scm_TopClass), NULL }; SCM_DEFINE_BUILTIN_CLASS(Scm_ListClass, NULL, NULL, NULL, NULL, list_cpl+1); SCM_DEFINE_BUILTIN_CLASS(Scm_PairClass, NULL, NULL, NULL, NULL, list_cpl); SCM_DEFINE_BUILTIN_CLASS(Scm_NullClass, NULL, NULL, NULL, NULL, list_cpl); /* * CONSTRUCTOR */ ScmObj Scm_Cons(ScmObj car, ScmObj cdr) { ScmPair *z = SCM_NEW(ScmPair); /* NB: these ENSURE_MEMs are moved here from vm loop to reduce the register pressure there. In most cases these increases just a couple of mask-and-test instructions on the data on the register. */ SCM_FLONUM_ENSURE_MEM(car); SCM_FLONUM_ENSURE_MEM(cdr); SCM_SET_CAR_UNCHECKED(z, car); SCM_SET_CDR_UNCHECKED(z, cdr); return SCM_OBJ(z); } ScmObj Scm_Acons(ScmObj caar, ScmObj cdar, ScmObj cdr) { ScmPair *y = SCM_NEW(ScmPair); ScmPair *z = SCM_NEW(ScmPair); SCM_SET_CAR_UNCHECKED(y, caar); SCM_SET_CDR_UNCHECKED(y, cdar); SCM_SET_CAR_UNCHECKED(z, SCM_OBJ(y)); SCM_SET_CDR_UNCHECKED(z, cdr); return SCM_OBJ(z); } ScmObj Scm_List(ScmObj elt, ...) { if (elt == NULL) return SCM_NIL; va_list pvar; va_start(pvar, elt); ScmObj cdr = Scm_VaList(pvar); va_end(pvar); return Scm_Cons(elt, cdr); } ScmObj Scm_Conses(ScmObj elt, ...) { if (elt == NULL) return SCM_NIL; va_list pvar; va_start(pvar, elt); ScmObj cdr = Scm_VaCons(pvar); va_end(pvar); if (cdr == NULL) return elt; else return Scm_Cons(elt, cdr); } ScmObj Scm_VaList(va_list pvar) { ScmObj start = SCM_NIL, cp = SCM_NIL, obj; for (obj = va_arg(pvar, ScmObj); obj != NULL; obj = va_arg(pvar, ScmObj)) { if (SCM_NULLP(start)) { start = SCM_OBJ(SCM_NEW(ScmPair)); SCM_SET_CAR_UNCHECKED(start, obj); SCM_SET_CDR_UNCHECKED(start, SCM_NIL); cp = start; } else { ScmObj item; item = SCM_OBJ(SCM_NEW(ScmPair)); SCM_SET_CDR_UNCHECKED(cp, item); SCM_SET_CAR_UNCHECKED(item, obj); SCM_SET_CDR_UNCHECKED(item, SCM_NIL); cp = item; } } return start; } ScmObj Scm_VaCons(va_list pvar SCM_UNUSED) { Scm_Panic("Scm_VaCons: not implemented"); return SCM_UNDEFINED; } ScmObj Scm_ArrayToList(ScmObj *elts, ScmSize nelts) { return Scm_ArrayToListWithTail(elts, nelts, SCM_NIL); } ScmObj Scm_ArrayToListWithTail(ScmObj *elts, ScmSize nelts, ScmObj tail) { ScmObj h = SCM_NIL, t = SCM_NIL; if (elts) { for (ScmSize i=0; iflags & SCM_PAIR_IMMUTABLE) { Scm_Error("attempt to mutate car of an immutable pair %S with %S", pair, obj); } if (d->setCar) { d->setCar(pair, obj); return; } } SCM_CAR(pair) = obj; } void Scm_SetCdr(ScmObj pair, ScmObj obj) { if (!SCM_PAIRP(pair)) { Scm_Error("set-cdr!: Pair required, but got: %S", pair); } ScmExtendedPairDescriptor *d = Scm__GetExtendedPairDescriptor(pair); if (d) { if (d->flags & SCM_PAIR_IMMUTABLE) { Scm_Error("attempt to mutate cdr of an immutable pair %S with %S", pair, obj); } if (d->setCdr) { d->setCdr(pair, obj); return; } } SCM_CDR(pair) = obj; } /* * List manipulate routines: */ /* Scm_Length return length of list in C integer. If the argument is a dotted list, return -1. If the argument is a circular list, return -2. */ ScmSize Scm_Length(ScmObj obj) { ScmObj slow = obj; ScmSize len = 0; for (;;) { if (SCM_NULLP(obj)) break; if (!SCM_PAIRP(obj)) return SCM_LIST_DOTTED; obj = SCM_CDR(obj); len++; if (SCM_NULLP(obj)) break; if (!SCM_PAIRP(obj)) return SCM_LIST_DOTTED; obj = SCM_CDR(obj); slow = SCM_CDR(slow); if (obj == slow) return SCM_LIST_CIRCULAR; len++; } return len; } /* Scm_CopyList(list) * Copy toplevel list LIST. LIST can be improper. * If LIST is not a pair, return LIST itself. * Note: For the naming consistency, this should be Scm_ListCopy(). */ ScmObj Scm_CopyList(ScmObj list) { if (!SCM_PAIRP(list)) return list; ScmObj tortoise = list, hare = list; ScmObj start = SCM_NIL, last = SCM_NIL; for (;;) { if (!SCM_PAIRP(hare)) break; SCM_APPEND1(start, last, SCM_CAR(hare)); hare = SCM_CDR(hare); if (!SCM_PAIRP(hare)) break; SCM_APPEND1(start, last, SCM_CAR(hare)); hare = SCM_CDR(hare); tortoise = SCM_CDR(tortoise); if (hare == tortoise) { Scm_Error("Attempt to copy a circular list: %S", list); } } if (!SCM_NULLP(hare)) SCM_SET_CDR_UNCHECKED(last, hare); return start; } /* Scm_AlistCopy(alist) * Copy the spine and each pair of alist. If there's non-pair element * it's included as is. We detect a cycle. * NB: We won't allow 'dotted' alist. */ ScmObj Scm_AlistCopy(ScmObj alist) { if (!SCM_PAIRP(alist)) return alist; ScmObj tortoise = alist, hare = alist; ScmObj start = SCM_NIL, last = SCM_NIL; for (;;) { if (!SCM_PAIRP(hare)) break; if (SCM_PAIRP(SCM_CAR(hare))) { ScmObj p = Scm_Cons(SCM_CAAR(hare), SCM_CDAR(hare)); SCM_APPEND1(start, last, p); } else { SCM_APPEND1(start, last, SCM_CAR(hare)); } hare = SCM_CDR(hare); if (!SCM_PAIRP(hare)) break; if (SCM_PAIRP(SCM_CAR(hare))) { ScmObj p = Scm_Cons(SCM_CAAR(hare), SCM_CDAR(hare)); SCM_APPEND1(start, last, p); } else { SCM_APPEND1(start, last, SCM_CAR(hare)); } hare = SCM_CDR(hare); tortoise = SCM_CDR(tortoise); if (hare == tortoise) { Scm_Error("Attempt to copy a circular alist: %S", alist); } } if (!SCM_NULLP(hare)) Scm_Error("Dotted alist isn't allowed: %S", alist); return start; } /* Scm_MakeList(len, fill) * Make a list of specified length. * Note that is C-integer. */ ScmObj Scm_MakeList(ScmSmallInt len, ScmObj fill) { if (len < 0) { Scm_Error("make-list: negative length given: %ld", len); } ScmObj start = SCM_NIL, last = SCM_NIL; while (len--) { SCM_APPEND1(start, last, fill); } return start; } /* Scm_Append2X(list, obj) * Replace cdr of last pair of LIST for OBJ. * If LIST is not a pair, return OBJ. */ ScmObj Scm_Append2X(ScmObj list, ScmObj obj) { ScmObj cp; SCM_FOR_EACH(cp, list) { if (SCM_NULLP(SCM_CDR(cp))) { Scm_SetCdr(cp, obj); return list; } } return obj; } /* Scm_Append2(list, obj) * Copy LIST and append OBJ to it. * If LIST is not a pair, return OBJ. */ ScmObj Scm_Append2(ScmObj list, ScmObj obj) { if (SCM_NULLP(list)) return obj; ScmObj cp, start = SCM_NIL, last = SCM_NIL; SCM_FOR_EACH(cp, list) { SCM_APPEND1(start, last, SCM_CAR(cp)); } if (!SCM_NULLP(cp)) { Scm_Error("proper list required, but got %S", list); } SCM_SET_CDR_UNCHECKED(last, obj); return start; } ScmObj Scm_Append(ScmObj args) { ScmObj start = SCM_NIL, last = SCM_NIL, cp; SCM_FOR_EACH(cp, args) { if (!SCM_PAIRP(SCM_CDR(cp))) { if (SCM_NULLP(start)) return SCM_CAR(cp); SCM_SET_CDR_UNCHECKED(last, SCM_CAR(cp)); break; } else if (SCM_NULLP(SCM_CAR(cp))) { continue; } else if (!SCM_PAIRP(SCM_CAR(cp))) { Scm_Error("pair required, but got %S", SCM_CAR(cp)); } else { SCM_APPEND(start, last, Scm_CopyList(SCM_CAR(cp))); if (SCM_PAIRP(last) && !SCM_NULLP(SCM_CDR(last))) { Scm_Error("proper list required, but got %S", SCM_CAR(cp)); } } } return start; } /* Scm_Reverse2(list, tail) * Reverse LIST, and append TAIL to the result. * If LIST is an improper list, cdr of the last pair is ignored. * If LIST is not a pair, TAIL is returned. * Scm_Reverse(list) * Scm_Reverse2(list, SCM_NIL). Just for the backward compatibility. */ ScmObj Scm_Reverse2(ScmObj list, ScmObj tail) { if (!SCM_PAIRP(list)) return tail; ScmPair *p = SCM_NEW(ScmPair); SCM_SET_CAR_UNCHECKED(p, SCM_NIL); SCM_SET_CDR_UNCHECKED(p, tail); ScmObj result = SCM_OBJ(p); ScmObj cp; SCM_FOR_EACH(cp, list) { SCM_SET_CAR_UNCHECKED(result, SCM_CAR(cp)); p = SCM_NEW(ScmPair); SCM_SET_CAR_UNCHECKED(p, SCM_NIL); SCM_SET_CDR_UNCHECKED(p, result); result = SCM_OBJ(p); } return SCM_CDR(result); } ScmObj Scm_Reverse(ScmObj list) { return Scm_Reverse2(list, SCM_NIL); } /* Scm_Reverse2X(list, tail) * Return reversed list of LIST. Pairs in previous LIST is used to * create new list. TAIL is appended to the result. * If LIST is not a pair, returns TAIL. * If LIST is an improper list, cdr of the last cell is ignored. */ ScmObj Scm_Reverse2X(ScmObj list, ScmObj tail) { if (!SCM_PAIRP(list)) return tail; ScmObj first, next, result = tail; for (first = list; SCM_PAIRP(first); first = next) { next = SCM_CDR(first); Scm_SetCdr(first, result); result = first; } return result; } ScmObj Scm_ReverseX(ScmObj list) { return Scm_Reverse2X(list, SCM_NIL); } /* Scm_ListTail(list, i, fallback) * Scm_ListRef(list, i, fallback) * Note that i is C-INTEGER. If i is out of bound, signal error. */ ScmObj Scm_ListTail(ScmObj list, ScmSmallInt i, ScmObj fallback) { if (i < 0) goto err; ScmSmallInt cnt = i; while (cnt-- > 0) { if (!SCM_PAIRP(list)) goto err; list = SCM_CDR(list); } return list; err: if (SCM_UNBOUNDP(fallback)) Scm_Error("argument out of range: %ld", i); return fallback; } ScmObj Scm_ListRef(ScmObj list, ScmSmallInt i, ScmObj fallback) { if (i < 0) goto err; for (ScmSmallInt k=0; khiddenTag = SCM_WORD((ScmByte*)desc + 7); xp->data.car = car; xp->data.cdr = cdr; xp->data.attributes = attrs; return SCM_OBJ(&xp->data); /* hide the first word */ } /* "vanilla" extended pair. used mainly to hold extra attributes, but otherwise behaves like normal pairs. NB: Static initialization with ScmClass* requires extra care on Windows. To avoid complication, we initialize the klass field in _Init() routine. */ static ScmExtendedPairDescriptor mpair_desc SCM_ALIGN8 = { NULL, /* will be SCM_CLASS_PAIR */ 0, NULL, NULL }; ScmObj Scm_MakeExtendedPair(ScmObj car, ScmObj cdr, ScmObj attrs) { return make_extended_pair(&mpair_desc, car, cdr, attrs); } /* Returns NULL if p isn't an extended pair. */ ScmExtendedPairDescriptor *Scm__GetExtendedPairDescriptor(ScmObj p) { if (!SCM_EXTENDED_PAIR_P(p)) return NULL; ScmRealExtendedPair *z = (ScmRealExtendedPair*)(((ScmObj*)p) - 1); SCM_ASSERT((z->hiddenTag&0x7) == 0x7); return (ScmExtendedPairDescriptor *)(z->hiddenTag-7); } /* Returns vanilla extended pair descriptor */ ScmExtendedPairDescriptor *Scm__GetDefaultExtendedPairDesctiptor() { return &mpair_desc; } ScmObj Scm_PairAttr(ScmPair *pair) { if (SCM_EXTENDED_PAIR_P(pair)) { return SCM_EXTENDED_PAIR(pair)->attributes; } else { return SCM_NIL; } } /* The common scenario is to use ExtendedCons in place of Cons, then add attributes later. So we provide this. */ ScmObj Scm_ExtendedCons(ScmObj car, ScmObj cdr) { return Scm_MakeExtendedPair(car, cdr, SCM_NIL); } ScmObj Scm_PairAttrGet(ScmPair *pair, ScmObj key, ScmObj fallback) { if (!SCM_EXTENDED_PAIR_P(pair)) { goto fallback; } ScmObj p = Scm_Assq(key, SCM_EXTENDED_PAIR(pair)->attributes); if (SCM_PAIRP(p)) return SCM_CDR(p); fallback: if (fallback == SCM_UNBOUND) Scm_Error("No value associated with key %S in pair attributes of %S", key, SCM_OBJ(pair)); return fallback; } ScmObj Scm_PairAttrSet(ScmPair *pair, ScmObj key, ScmObj value) { if (!SCM_EXTENDED_PAIR_P(pair)) { Scm_Error("Cannot set pair attribute (%S) to non-extended pair: %S", key, SCM_OBJ(pair)); } /* We update the attribute list non-destructively. In case if two threads update the list simultaneously, one change can be lost, but no invalid access can occur. Guaranteeing mutex is the caller's responsibility, though. */ ScmObj xs, attrs = SCM_EXTENDED_PAIR(pair)->attributes; SCM_FOR_EACH(xs, attrs) { SCM_ASSERT(SCM_PAIRP(SCM_CAR(xs))); if (SCM_EQ(SCM_CAAR(xs), key)) { /* need to copy up to here */ ScmObj h = SCM_NIL, t = SCM_NIL, ys; SCM_FOR_EACH(ys, attrs) { if (SCM_EQ(ys, xs)) { SCM_APPEND1(h, t, Scm_Cons(key, value)); SCM_APPEND(h, t, SCM_CDR(xs)); SCM_EXTENDED_PAIR(pair)->attributes = h; return SCM_UNDEFINED; } SCM_APPEND1(h, t, SCM_CAR(ys)); } SCM_ASSERT(FALSE); /* Shouldn't be here */ } } SCM_EXTENDED_PAIR(pair)->attributes = Scm_Acons(key, value, attrs); return SCM_UNDEFINED; } /* * Immutable pairs */ /* not cheap. usually you don't want to check this and let it catched in set-car!/set-cdr!. */ int Scm_ImmutablePairP(ScmObj obj) { if (!SCM_EXTENDED_PAIR_P(obj)) return FALSE; ScmExtendedPairDescriptor *d = Scm__GetExtendedPairDescriptor(obj); return d->flags & SCM_PAIR_IMMUTABLE; } static ScmExtendedPairDescriptor ipair_desc SCM_ALIGN8 = { NULL, /* will be SCM_CLASS_PAIR. see above. */ SCM_PAIR_IMMUTABLE, NULL, NULL }; ScmObj Scm_MakeImmutablePair(ScmObj car, ScmObj cdr, ScmObj attrs) { return make_extended_pair(&ipair_desc, car, cdr, attrs); } void Scm__InitList() { mpair_desc.klass = SCM_CLASS_PAIR; ipair_desc.klass = SCM_CLASS_PAIR; } /* Temporary - Check if normal pairs are all aligned with 2-word boundary */ #if GAUCHE_CHECK_PAIR_ALIGNMENT int Scm_CheckingPairP(ScmObj obj) { if (SCM_HPTRP(obj)&&(SCM_HTAG(obj)!=7||Scm_PairP(SCM_OBJ(obj)))) { if (SCM_WORD(obj) & SIZEOF_LONG) { if ((SCM_WORD((ScmObj*)obj - 1) & 7) != 7) { fprintf(stderr, "Unaligned pair %p\n", obj); } } return TRUE; } return FALSE; } #endif /*GAUCHE_CHECK_PAIR_ALIGNMENT*/