From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mp2 ([2001:41d0:2:4a6f::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by ms11 with LMTPS id +GNYDxsl9l+CVgAA0tVLHw (envelope-from ) for ; Wed, 06 Jan 2021 21:01:15 +0000 Received: from aspmx1.migadu.com ([2001:41d0:2:4a6f::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by mp2 with LMTPS id EIZACxsl9l+EdQAAB5/wlQ (envelope-from ) for ; Wed, 06 Jan 2021 21:01:15 +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 A73D994050C for ; Wed, 6 Jan 2021 21:01:14 +0000 (UTC) Received: from localhost ([::1]:49916 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1kxFvd-0001o4-80 for larch@yhetil.org; Wed, 06 Jan 2021 16:01:13 -0500 Received: from eggs.gnu.org ([2001:470:142:3::10]:52694) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1kxFvS-0001ns-1c for bug-guix@gnu.org; Wed, 06 Jan 2021 16:01:02 -0500 Received: from debbugs.gnu.org ([209.51.188.43]:34182) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1kxFvR-0000Zl-QE for bug-guix@gnu.org; Wed, 06 Jan 2021 16:01:01 -0500 Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1kxFvR-0003Fp-MZ for bug-guix@gnu.org; Wed, 06 Jan 2021 16:01:01 -0500 X-Loop: help-debbugs@gnu.org Subject: bug#45570: [PATCH] system: Assert, that user and group names are unique. Resent-From: Leo Prikler Original-Sender: "Debbugs-submit" Resent-CC: bug-guix@gnu.org Resent-Date: Wed, 06 Jan 2021 21:01: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: Ludovic =?UTF-8?Q?Court=C3=A8s?= Received: via spool by 45570-submit@debbugs.gnu.org id=B45570.160996680912437 (code B ref 45570); Wed, 06 Jan 2021 21:01:01 +0000 Received: (at 45570) by debbugs.gnu.org; 6 Jan 2021 21:00:09 +0000 Received: from localhost ([127.0.0.1]:45728 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1kxFub-0003EX-6m for submit@debbugs.gnu.org; Wed, 06 Jan 2021 16:00:09 -0500 Received: from mailrelay.tugraz.at ([129.27.2.202]:38643) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1kxFuY-0003DN-Tt for 45570@debbugs.gnu.org; Wed, 06 Jan 2021 16:00:07 -0500 Received: from nijino.local (217-149-174-13.nat.highway.telekom.at [217.149.174.13]) by mailrelay.tugraz.at (Postfix) with ESMTPSA id 4DB1w41KLYz1LLyW; Wed, 6 Jan 2021 22:00:03 +0100 (CET) DKIM-Filter: OpenDKIM Filter v2.11.0 mailrelay.tugraz.at 4DB1w41KLYz1LLyW DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=tugraz.at; s=mailrelay; t=1609966804; bh=jd3gON0HPwX1p7XCwPPufT/Tgx4jwLi2L3nn+J2Y3mY=; h=Subject:From:To:Cc:Date:In-Reply-To:References:From; b=J6N+D9CoLPkG5fS4vh2LCMraDZOrmGPdkudzq6IFU24t2LLOWm6xuaLHM+gYvnkSX blTXYuyc48MW6QLz2fQbw87rfuut2CmXfPDUW5gBXe0SolzturwjfG3iYVg1vAkMD1 0N6V+xh2+41tYK76ou+sjLOSaxb9NleKGyCweHQo= Message-ID: From: Leo Prikler Date: Wed, 06 Jan 2021 22:00:03 +0100 In-Reply-To: <87k0sqkx7p.fsf@gnu.org> References: <20210102055728.22594-1-leo.prikler@student.tugraz.at> <87v9cao0c8.fsf@gnu.org> <87k0sqkx7p.fsf@gnu.org> Content-Type: text/plain; charset="UTF-8" User-Agent: Evolution 3.34.2 MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-TUG-Backscatter-control: bt4lQm5Tva3SBgCuw0EnZw X-Spam-Scanner: SpamAssassin 3.003001 X-Spam-Score-relay: -1.9 X-Scanned-By: MIMEDefang 2.74 on 129.27.10.116 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: -1.24 Authentication-Results: aspmx1.migadu.com; dkim=fail (headers rsa verify failed) header.d=tugraz.at header.s=mailrelay header.b=J6N+D9Co; dmarc=fail reason="SPF not aligned (relaxed)" header.from=student.tugraz.at (policy=none); 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: A73D994050C X-Spam-Score: -1.24 X-Migadu-Scanner: scn0.migadu.com X-TUID: 8kTTA7ojjTyg Hi, Am Mittwoch, den 06.01.2021, 14:32 +0100 schrieb Ludovic Courtès: > Hi, > > Leo Prikler skribis: > > > > > + ((first . rest) > > > > + (if (member first rest =) ; (srfi srfi-1) member > > > > + (cons first (find-duplicates rest =)) > > > > + (find-duplicates rest =))))) > > > > > > Note that this is quadratic; it’s fine as long as we don’t have > > > “too > > > many” 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? > > 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’re in > that > table. That’d 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. Since VHashes are based on VLists, they're not actually purely functional, are they? > > > (define (assert-unique-account-names users) > > > (match (find-duplicates things …) > > > (() #t) > > > (lst > > > (raise (formatted-message (G_ "the following accounts > > > appear > > > more than once:~{ ~a~}~%" > > > lst)))))) > > > > > > ? > > That'd be weird for duplicate duplicates, hence just reporting the > > first. > > 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. I think I'll try working on a hash-based implementation for now. Regards, Leo