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

[Ludovic Courtès]

Hi,

Leo Prikler <leo.prikler@student.tugraz.at> skribis:

> Am Mittwoch, den 06.01.2021, 14:32 +0100 schrieb Ludovic Courtès:
>> Hi,
>> 
>> Leo Prikler <leo.prikler@student.tugraz.at> 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?

Their implementation is not “purely functional” but it’s
inconsequential; it’s a persistent data structure, and that’s what
matters (info "(guile) VLists").

>> > >   (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.

Yes, but it’s a small ‘n’, typically one or two.

Ludo’.