285 lines
11 KiB
Racket
285 lines
11 KiB
Racket
#lang scribble/doc
|
|
@(require "common.rkt"
|
|
(for-label syntax/id-set
|
|
racket/set
|
|
(only-in racket/stream gen:stream)))
|
|
|
|
@title[#:tag "idset"]{Sets with Identifier Keys}
|
|
|
|
@defmodule[syntax/id-set]
|
|
|
|
This module provides @deftech{identifier sets}:
|
|
sets with identifier keys that use identifier-specific
|
|
comparisons instead of the usual equality operators such as
|
|
@racket[eq?] or @racket[equal?].
|
|
|
|
This module implements two kinds of identifier sets: one via
|
|
@racket[free-identifier=?] and one via @racket[bound-identifier=?].
|
|
Each are available in both mutable and immutable variants and
|
|
implement the @racket[gen:set],
|
|
@racket[gen:stream],
|
|
@racket[prop:sequence], and @racket[gen:equal+hash]
|
|
generic interfaces.
|
|
|
|
Identifier sets are implemented using @tech{identifier tables},
|
|
in the same way that
|
|
@tech[#:doc '(lib "scribblings/reference/reference.scrbl")]{hash sets}
|
|
are implemented with
|
|
@tech[#:doc '(lib "scribblings/reference/reference.scrbl")]{hash tables}.
|
|
|
|
|
|
@section{Sets for @racket[free-identifier=?]}
|
|
|
|
A free-identifier set is a set whose keys are compared using
|
|
@racket[free-identifier=?]. Free-identifier sets implement the
|
|
@racket[gen:set] interface, so all of the
|
|
appropriate generic functions (e.g., @racket[set-add], @racket[set-map],
|
|
etc) can be used on free-identifier sets.
|
|
|
|
@deftogether[[
|
|
@defproc[(mutable-free-id-set
|
|
[init-set generic-set? null]
|
|
[#:phase phase (or/c exact-integer? #f) (syntax-local-phase-level)])
|
|
mutable-free-id-set?]
|
|
@defproc[(immutable-free-id-set
|
|
[init-set generic-set? null]
|
|
[#:phase phase (or/c exact-integer? #f) (syntax-local-phase-level)])
|
|
immutable-free-id-set?]]]{
|
|
|
|
Produces a mutable free-identifier set or immutable free-identifier
|
|
set, respectively. The set uses @racket[free-identifier=?]
|
|
to compare keys.
|
|
|
|
The identifiers are compared at phase level @racket[phase]. The
|
|
default phase, @racket[(syntax-local-phase-level)], is generally
|
|
appropriate for identifier sets used by macros, but code that
|
|
analyzes fully-expanded programs may need to create separate
|
|
identifier sets for each phase of the module.
|
|
|
|
The optional @racket[init-set] argument provides the initial
|
|
set elements. It must be a set of identifiers. If the @racket[init-set]
|
|
set has multiple distinct entries whose keys are @racket[free-identifier=?],
|
|
only one of the entries appears in the new id-set, and it is not specified
|
|
which entry is picked.
|
|
}
|
|
|
|
@defproc[(free-id-set? [v any/c]) boolean?]{
|
|
|
|
Returns @racket[#t] if @racket[v] was produced by
|
|
@racket[mutable-free-id-set] or
|
|
@racket[immutable-free-id-set], @racket[#f] otherwise.
|
|
}
|
|
|
|
@defproc[(mutable-free-id-set? [v any/c]) boolean?]{
|
|
|
|
Returns @racket[#t] if @racket[v] was produced by
|
|
@racket[mutable-free-id-set], @racket[#f] otherwise.
|
|
}
|
|
|
|
@defproc[(immutable-free-id-set? [v any/c]) boolean?]{
|
|
|
|
Returns @racket[#t] if @racket[v] was produced by
|
|
@racket[immutable-free-id-set], @racket[#f] otherwise.
|
|
}
|
|
|
|
@defproc[(free-id-set-empty? [s free-id-set?]) boolean?]{
|
|
Like @racket[set-empty?].}
|
|
|
|
@defproc[(free-id-set-count [s free-id-set?]) exact-nonnegative-integer?]{
|
|
Like @racket[set-count].}
|
|
|
|
@defproc[(free-id-set-member? [s free-id-set?] [v identifier?]) boolean?]{
|
|
Like @racket[set-member?].}
|
|
|
|
@defproc[(free-id-set=? [s1 free-id-set?] [s2 free-id-set?]) boolean?]{
|
|
Like @racket[set=?].}
|
|
|
|
@defproc[(free-id-set-add [s immutable-free-id-set?] [v identifier?])
|
|
immutable-free-id-set?]{
|
|
Like @racket[set-add].}
|
|
|
|
@defproc[(free-id-set-add! [s mutable-free-id-set?] [v identifier?]) void?]{
|
|
Like @racket[set-add!].}
|
|
|
|
@defproc[(free-id-set-remove [s immutable-free-id-set?] [v identifier?])
|
|
immutable-free-id-set?]{
|
|
Like @racket[set-remove].}
|
|
|
|
@defproc[(free-id-set-remove! [s mutable-free-id-set?] [v identifier?]) void?]{
|
|
Like @racket[set-remove!].}
|
|
|
|
@defproc[(free-id-set-first [s free-id-set?]) identifier?]{
|
|
Like @racket[set-first].}
|
|
|
|
@defproc[(free-id-set-rest [s immutable-free-id-set?]) immutable-free-id-set?]{
|
|
Like @racket[set-rest].}
|
|
|
|
@defproc[(in-free-id-set [s free-id-set?]) sequence?]{
|
|
Like @racket[in-set].}
|
|
|
|
@defproc[(free-id-set->stream [s free-id-set?]) stream?]{
|
|
Like @racket[set->stream].}
|
|
|
|
@defproc[(free-id-set->list [s free-id-set?]) list?]{
|
|
Like @racket[set->list].}
|
|
|
|
@defproc[(free-id-set-copy [s free-id-set?]) free-id-set?]{
|
|
Like @racket[set-copy].}
|
|
|
|
@defproc[(free-id-set-copy-clear [s free-id-set?]) free-id-set?]{
|
|
Like @racket[set-copy-clear].}
|
|
|
|
@defproc[(free-id-set-clear [s immutable-free-id-set?]) immutable-free-id-set?]{
|
|
Like @racket[set-clear].}
|
|
|
|
@defproc[(free-id-set-clear! [s mutable-free-id-set?]) void?]{
|
|
Like @racket[set-clear!].}
|
|
|
|
@defproc[(free-id-set-union [s0 immutable-free-id-set?] [s free-id-set?] ...)
|
|
immutable-free-id-set?]{
|
|
Like @racket[set-union].}
|
|
|
|
@defproc[(free-id-set-union! [s0 mutable-free-id-set?] [s free-id-set?] ...)
|
|
void?]{
|
|
Like @racket[set-union!].}
|
|
|
|
@defproc[(free-id-set-intersect
|
|
[s0 immutable-free-id-set?] [s free-id-set?] ...)
|
|
immutable-free-id-set?]{
|
|
Like @racket[set-intersect].}
|
|
|
|
@defproc[(free-id-set-intersect! [s0 mutable-free-id-set?] [s free-id-set?] ...)
|
|
void?]{
|
|
Like @racket[set-intersect!].}
|
|
|
|
@defproc[(free-id-set-subtract [s0 immutable-free-id-set?] [s free-id-set?] ...)
|
|
immutable-free-id-set?]{
|
|
Like @racket[set-subtract].}
|
|
|
|
@defproc[(free-id-set-subtract! [s0 mutable-free-id-set?] [s free-id-set?] ...)
|
|
void?]{
|
|
Like @racket[set-subtract!].}
|
|
|
|
@defproc[(free-id-set-symmetric-difference
|
|
[s0 immutable-free-id-set?] [s free-id-set?] ...)
|
|
immutable-free-id-set?]{
|
|
Like @racket[set-symmetric-difference].}
|
|
|
|
@defproc[(free-id-set-symmetric-difference!
|
|
[s0 mutable-free-id-set?] [s free-id-set?] ...) void?]{
|
|
Like @racket[set-symmetric-difference!].}
|
|
|
|
@defproc[(free-id-subset? [s1 free-id-set?] [s2 free-id-set?]) boolean?]{
|
|
Like @racket[subset?].}
|
|
|
|
@defproc[(free-id-proper-subset? [s1 free-id-set?] [s2 free-id-set?]) boolean?]{
|
|
Like @racket[proper-subset?].}
|
|
|
|
@defproc[(free-id-set-map [s free-id-set?] [f (-> identifier? any/c)]) list?]{
|
|
Like @racket[set-map].}
|
|
|
|
@defproc[(free-id-set-for-each [s free-id-set?] [f (-> identifier? any/c)]) void?]{
|
|
Like @racket[set-for-each].}
|
|
|
|
|
|
|
|
@defproc[(id-set/c
|
|
[elem-ctc flat-contract?]
|
|
[#:setidtype idsettype
|
|
(or/c 'dont-care 'free 'bound) 'dont-care]
|
|
[#:mutability mutability
|
|
(or/c 'dont-care 'mutable 'immutable) 'immutable])
|
|
contract?]{
|
|
Creates a contract for identifier sets. If
|
|
@racket[mutability] is @racket['immutable], the contract accepts only
|
|
immutable identifier sets; if @racket[mutability] is @racket['mutable],
|
|
the contract accepts only mutable identifier sets.
|
|
}
|
|
|
|
@defproc[(free-id-set/c
|
|
[elem-ctc flat-contract?]
|
|
[#:mutability mutability
|
|
(or/c 'dont-care 'mutable 'immutable) 'immutable])
|
|
contract?]{
|
|
Creates a contract for free-identifier sets. If
|
|
@racket[mutability] is @racket['immutable], the contract accepts only
|
|
immutable identifier sets; if @racket[mutability] is @racket['mutable],
|
|
the contract accepts only mutable identifier sets.
|
|
}
|
|
|
|
@;{----------}
|
|
@section{Sets for @racket[bound-identifier=?]}
|
|
|
|
A bound-identifier set is a set whose keys are compared using
|
|
@racket[bound-identifier=?]. Bound-identifier sets implement the
|
|
@racket[gen:set] interface, so all of the
|
|
appropriate generic functions (e.g., @racket[set-add], @racket[set-map],
|
|
etc.) can be used on bound-identifier sets.
|
|
|
|
@deftogether[[
|
|
@defproc[(mutable-bound-id-set
|
|
[init-set set? null]
|
|
[#:phase phase (or/c exact-integer? #f) (syntax-local-phase-level)])
|
|
mutable-bound-id-set?]
|
|
@defproc[(immutable-bound-id-set
|
|
[init-set set? null]
|
|
[#:phase phase (or/c exact-integer? #f) (syntax-local-phase-level)])
|
|
immutable-bound-id-set?]
|
|
@defproc[(bound-id-set? [v any/c]) boolean?]
|
|
@defproc[(mutable-bound-id-set? [v any/c]) boolean?]
|
|
@defproc[(immutable-bound-id-set? [v any/c]) boolean?]
|
|
@defproc[(bound-id-set-empty? [s bound-id-set?]) boolean?]
|
|
@defproc[(bound-id-set-count [s bound-id-set?]) exact-nonnegative-integer?]
|
|
@defproc[(bound-id-set-member? [s bound-id-set?] [v identifier?]) boolean?]
|
|
@defproc[(bound-id-set=? [s1 bound-id-set?] [s2 bound-id-set?]) boolean?]
|
|
@defproc[(bound-id-set-add [s immutable-bound-id-set?] [v identifier?])
|
|
immutable-bound-id-set?]
|
|
@defproc[(bound-id-set-add! [s mutable-bound-id-set?] [v identifier?]) void?]
|
|
@defproc[(bound-id-set-remove [s immutable-bound-id-set?] [v identifier?])
|
|
immutable-bound-id-set?]
|
|
@defproc[(bound-id-set-remove! [s mutable-bound-id-set?] [v identifier?]) void?]
|
|
@defproc[(bound-id-set-first [s bound-id-set?]) identifier?]
|
|
@defproc[(bound-id-set-rest [s immutable-bound-id-set?]) immutable-bound-id-set?]
|
|
@defproc[(in-bound-id-set [s bound-id-set?]) sequence?]
|
|
@defproc[(bound-id-set->stream [s bound-id-set?]) stream?]
|
|
@defproc[(bound-id-set->list [s bound-id-set?]) list?]
|
|
@defproc[(bound-id-set-copy [s bound-id-set?]) bound-id-set?]
|
|
@defproc[(bound-id-set-copy-clear [s bound-id-set?]) bound-id-set?]
|
|
@defproc[(bound-id-set-clear [s immutable-bound-id-set?])
|
|
immutable-bound-id-set?]
|
|
@defproc[(bound-id-set-clear! [s mutable-bound-id-set?]) void?]
|
|
@defproc[(bound-id-set-union [s0 immutable-bound-id-set?] [s bound-id-set?] ...)
|
|
immutable-bound-id-set?]
|
|
@defproc[(bound-id-set-union! [s0 mutable-bound-id-set?] [s bound-id-set?] ...)
|
|
void?]
|
|
@defproc[(bound-id-set-intersect
|
|
[s0 immutable-bound-id-set?] [s bound-id-set?] ...)
|
|
immutable-bound-id-set?]
|
|
@defproc[(bound-id-set-intersect!
|
|
[s0 mutable-bound-id-set?] [s bound-id-set?] ...) void?]
|
|
@defproc[(bound-id-set-subtract
|
|
[s0 immutable-bound-id-set?] [s bound-id-set?] ...)
|
|
immutable-bound-id-set?]
|
|
@defproc[(bound-id-set-subtract!
|
|
[s0 mutable-bound-id-set?] [s bound-id-set?] ...) void?]
|
|
@defproc[(bound-id-set-symmetric-difference
|
|
[s0 immutable-bound-id-set?] [s bound-id-set?] ...)
|
|
immutable-bound-id-set?]
|
|
@defproc[(bound-id-set-symmetric-difference!
|
|
[s0 mutable-bound-id-set?] [s bound-id-set?] ...) void?]
|
|
@defproc[(bound-id-subset? [s1 bound-id-set?] [s2 bound-id-set?]) boolean?]
|
|
@defproc[(bound-id-proper-subset? [s1 bound-id-set?] [s2 bound-id-set?])
|
|
boolean?]
|
|
@defproc[(bound-id-set-map [s bound-id-set?]) list?]
|
|
@defproc[(bound-id-set-for-each [s bound-id-set?]) void?]
|
|
@defproc[(bound-id-set/c
|
|
[elem-ctc flat-contract?]
|
|
[#:mutability mutability
|
|
(or/c 'dont-care 'mutable 'immutable) 'immutable])
|
|
contract?]]]{
|
|
Like the procedures for free-identifier sets
|
|
(e.g., @racket[immutable-free-id-set], @racket[free-id-set-add], etc.), but
|
|
for bound-identifier sets, which use @racket[bound-identifier=?] to
|
|
compare keys.
|
|
}
|