Subject: Re: bug#45570: [PATCH] system: Assert, that user and group names are unique.

From: Leo Prikler <[email-masked]>
Date: Wed, 06 Jan 2021 13:34:26 +0100

Hi,

Am Mittwoch, den 06.01.2021, 10:56 +0100 schrieb Ludovic Courtès:
> Hi,
> 
> Leo Prikler <[email-masked]> skribis:
> 
> > *gnu/system/shadow.scm (find-duplicates): New variable.
> > (assert-unique-account-names, assert-unique-group-names): New
> > variables.
> > (account-activation): Use them here.
> 
> [...]
> 
> > +(define (find-duplicates list =)
> > +  (match list
> > +    ('() '())
> 
> This should be:
> 
>   (match list
>     (() '())
>     …)
> 
> I’m surprised '() works as a pattern.
I think it's because matching literals works, but you're right.

> > +    ((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?

> > +(define (assert-unique-account-names users)
> > +  (for-each
> > +   (lambda (account)
> > +     (raise (condition
> > +             (&message
> > +              (message
> > +               (format #f (G_ "account with name '~a' found
> > twice.")
> > +                       (user-account-name account)))))))
> > +   (find-duplicates users (lambda (alice bob)
> > +                            (string=? (user-account-name alice)
> > +                                      (user-account-name bob))))))
> 
> ‘for-each’ looks awkward since we’ll stop on the first one.  How
> about
> something like:
> 
>   (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.  Of course we could always count occurrences by allocating a
local hash table and then do some fancy hash-map->list conversion.  If
we do use hash-tables, perhaps this could even be a linear algorithm?

Regards,
Leo