From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mp1 ([2001:41d0:2:4a6f::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by ms11 with LMTPS id cAxRGdrG9l+uDAAA0tVLHw (envelope-from ) for ; Thu, 07 Jan 2021 08:31:22 +0000 Received: from aspmx1.migadu.com ([2001:41d0:2:4a6f::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by mp1 with LMTPS id KC4SFdrG9l+1PQAAbx9fmQ (envelope-from ) for ; Thu, 07 Jan 2021 08:31:22 +0000 Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by aspmx1.migadu.com (Postfix) with ESMTPS id DB6629403C5 for ; Thu, 7 Jan 2021 08:31:21 +0000 (UTC) Received: from localhost ([::1]:59248 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1kxQhU-0006yo-RP for larch@yhetil.org; Thu, 07 Jan 2021 03:31:20 -0500 Received: from eggs.gnu.org ([2001:470:142:3::10]:37482) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1kxQhC-0006yi-6q for bug-guix@gnu.org; Thu, 07 Jan 2021 03:31:02 -0500 Received: from debbugs.gnu.org ([209.51.188.43]:34703) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1kxQhB-00033Y-TR for bug-guix@gnu.org; Thu, 07 Jan 2021 03:31:01 -0500 Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1kxQhB-000386-PU for bug-guix@gnu.org; Thu, 07 Jan 2021 03:31:01 -0500 X-Loop: help-debbugs@gnu.org Subject: bug#45570: [PATCH] system: Assert, that user and group names are unique. Resent-From: Ludovic =?UTF-8?Q?Court=C3=A8s?= Original-Sender: "Debbugs-submit" Resent-CC: bug-guix@gnu.org Resent-Date: Thu, 07 Jan 2021 08:31:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 45570 X-GNU-PR-Package: guix X-GNU-PR-Keywords: To: Leo Prikler Received: via spool by 45570-submit@debbugs.gnu.org id=B45570.161000821011968 (code B ref 45570); Thu, 07 Jan 2021 08:31:01 +0000 Received: (at 45570) by debbugs.gnu.org; 7 Jan 2021 08:30:10 +0000 Received: from localhost ([127.0.0.1]:46249 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1kxQgM-00036x-6E for submit@debbugs.gnu.org; Thu, 07 Jan 2021 03:30:10 -0500 Received: from eggs.gnu.org ([209.51.188.92]:44188) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1kxQgK-00035l-0Y for 45570@debbugs.gnu.org; Thu, 07 Jan 2021 03:30:08 -0500 Received: from fencepost.gnu.org ([2001:470:142:3::e]:51775) by eggs.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1kxQgD-0002WH-7C; Thu, 07 Jan 2021 03:30:01 -0500 Received: from [2a01:e0a:1d:7270:af76:b9b:ca24:c465] (port=43772 helo=ribbon) by fencepost.gnu.org with esmtpsa (TLS1.2:RSA_AES_256_CBC_SHA1:256) (Exim 4.82) (envelope-from ) id 1kxQgC-0007yR-7O; Thu, 07 Jan 2021 03:30:00 -0500 From: Ludovic =?UTF-8?Q?Court=C3=A8s?= References: <20210102055728.22594-1-leo.prikler@student.tugraz.at> <87v9cao0c8.fsf@gnu.org> <87k0sqkx7p.fsf@gnu.org> X-URL: http://www.fdn.fr/~lcourtes/ X-Revolutionary-Date: 18 =?UTF-8?Q?Niv=C3=B4se?= an 229 de la =?UTF-8?Q?R=C3=A9volution?= X-PGP-Key-ID: 0x090B11993D9AEBB5 X-PGP-Key: http://www.fdn.fr/~lcourtes/ludovic.asc X-PGP-Fingerprint: 3CE4 6455 8A84 FDC6 9DB4 0CFB 090B 1199 3D9A EBB5 X-OS: x86_64-pc-linux-gnu Date: Thu, 07 Jan 2021 09:29:59 +0100 In-Reply-To: (Leo Prikler's message of "Wed, 06 Jan 2021 22:00:03 +0100") Message-ID: <87im89jgjc.fsf@gnu.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.1 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-guix@gnu.org List-Id: Bug reports for GNU Guix List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: 45570@debbugs.gnu.org, conjaroy@gmail.com Errors-To: bug-guix-bounces+larch=yhetil.org@gnu.org Sender: "bug-Guix" X-Migadu-Flow: FLOW_IN X-Migadu-Spam-Score: -2.84 Authentication-Results: aspmx1.migadu.com; dkim=none; dmarc=pass (policy=none) header.from=gnu.org; spf=pass (aspmx1.migadu.com: domain of bug-guix-bounces@gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=bug-guix-bounces@gnu.org X-Migadu-Queue-Id: DB6629403C5 X-Spam-Score: -2.84 X-Migadu-Scanner: scn0.migadu.com X-TUID: SqfwoykU/0oE Hi, Leo Prikler skribis: > Am Mittwoch, den 06.01.2021, 14:32 +0100 schrieb Ludovic Court=C3=A8s: >> Hi, >>=20 >> Leo Prikler skribis: >>=20 >> > > > + ((first . rest) >> > > > + (if (member first rest =3D) ; (srfi srfi-1) member >> > > > + (cons first (find-duplicates rest =3D)) >> > > > + (find-duplicates rest =3D))))) >> > >=20 >> > > Note that this is quadratic; it=E2=80=99s fine as long as we don=E2= =80=99t have >> > > =E2=80=9Ctoo >> > > many=E2=80=9D users, which may be the case in general. >> > It is indeed quadratic, but would there even be an n log n >> > solution? >> > I've once done an n log n sort+delete-duplicates!, perhaps that'd >> > be a >> > nicer solution here? >>=20 >> You could first build a hash table or vhash or set with all the >> names, >> then traverse again the list of names and check whether they=E2=80=99re = in >> that >> table. That=E2=80=99d be linear (assuming the table is well balanced), = but >> the >> constant factor would be higher. > Yeah, I think the hash table solution would make the most sense here.=20 > Since VHashes are based on VLists, they're not actually purely > functional, are they? Their implementation is not =E2=80=9Cpurely functional=E2=80=9D but it=E2= =80=99s inconsequential; it=E2=80=99s a persistent data structure, and that=E2=80= =99s what matters (info "(guile) VLists"). >> > > (define (assert-unique-account-names users) >> > > (match (find-duplicates things =E2=80=A6) >> > > (() #t) >> > > (lst >> > > (raise (formatted-message (G_ "the following accounts >> > > appear >> > > more than once:~{ ~a~}~%" >> > > lst)))))) >> > >=20 >> > > ? >> > That'd be weird for duplicate duplicates, hence just reporting the >> > first. >>=20 >> You could do (delete-duplicates lst) in the message above? > Sure, but that'd be O(n^2) on top of O(n^2), which is less than ideal. Yes, but it=E2=80=99s a small =E2=80=98n=E2=80=99, typically one or two. Ludo=E2=80=99.