summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorKaz Kylheku <kaz@kylheku.com>2021-01-22 06:27:40 -0800
committerKaz Kylheku <kaz@kylheku.com>2021-01-22 06:27:40 -0800
commit88b3ac140300a6014e271ff02e0e6901d35f18d1 (patch)
tree9ce88c5f5b1a329cb9bbdb66efb35293b7dde871
parent79e8b2534690bf7c427c28de7738705d5a372502 (diff)
downloadtxr-88b3ac140300a6014e271ff02e0e6901d35f18d1.tar.gz
txr-88b3ac140300a6014e271ff02e0e6901d35f18d1.tar.bz2
txr-88b3ac140300a6014e271ff02e0e6901d35f18d1.zip
matcher: document hash and some fixes.
* share/txr/stdlib/match.tl (compile-hash-match): Follow rename of is-pattern function to non-triv-pat-p. (is-pattern): Renamed to non-triv-pat-p, to follow terminology in the reference manual. A bug is fixed here: we must recognize cons patterns with operators and variables in the dotted position as non-trivial. * tests/011/patmatch.tl: New hash test case, from doc. * txr.1: Documented hash pattern operator.
-rw-r--r--share/txr/stdlib/match.tl10
-rw-r--r--tests/011/patmatch.tl3
-rw-r--r--txr.1125
3 files changed, 131 insertions, 7 deletions
diff --git a/share/txr/stdlib/match.tl b/share/txr/stdlib/match.tl
index 8cb29622..b6dcd442 100644
--- a/share/txr/stdlib/match.tl
+++ b/share/txr/stdlib/match.tl
@@ -318,8 +318,8 @@
(hash-matches
(collect-each ((pair pairs))
(mac-param-bind *match-form* (key val) pair
- (let ((key-pat-p (is-pattern key))
- (val-pat-p (is-pattern val)))
+ (let ((key-pat-p (non-triv-pat-p key))
+ (val-pat-p (non-triv-pat-p val)))
(cond
((and key-pat-p val-pat-p)
(set need-alist-p t)
@@ -436,8 +436,10 @@
^(defun ,name (. ,args)
(match-case ,args ,*clauses))))
-(defun is-pattern (syntax)
+(defun non-triv-pat-p (syntax)
(match-case syntax
((@(op eq 'sys:expr) (@(bindable) . @nil)) t)
((@(op eq 'sys:var) @(bindable) . @nil) t)
- (@(some @(is-pattern)) t)))
+ ((@pat . @rest) (or (non-triv-pat-p pat)
+ (non-triv-pat-p rest)))
+ (@(some @(non-triv-pat-p)) t)))
diff --git a/tests/011/patmatch.tl b/tests/011/patmatch.tl
index 2b1e26c8..a9bd57fa 100644
--- a/tests/011/patmatch.tl
+++ b/tests/011/patmatch.tl
@@ -129,3 +129,6 @@
((4 @x) x)
((@x 5) x)))
(3 5 3 6 (11 12) (2 time) (2020 1) (vec tor)))
+
+(test (when-match @(hash (x @y) (@y @datum)) #H(() (x k) (k 42)) datum)
+ (42))
diff --git a/txr.1 b/txr.1
index 4033359a..c49e52d6 100644
--- a/txr.1
+++ b/txr.1
@@ -39647,8 +39647,8 @@ and
provides a way to define a top-level function using the same concept.
\*(TL's structural pattern matching notation is template based.
-With the exception of structures, objects are matched using patterns which
-are based on their printed notation.
+With the exception of structures and hash tables, objects are matched using
+patterns which are based on their printed notation.
For instance instance, the pattern
.code "(1 2 @a)"
is a pattern matching the list
@@ -39681,6 +39681,16 @@ notation. The reason is that a struct literal produces an object
which loses information about how it was specified in the literal syntax,
but those details are critically important in pattern matching.
+Similarly, hash objects are matched using a
+.code "@(hash ...)"
+operator rather than
+.code "#H(...)"
+syntax. The reason is that the keys are not ordered in a hash
+table, whereas the order of sub-patterns in a pattern operator
+can be significant. One sub-pattern may be expected to produce
+a match for a variable, which is then back-referenced in another
+sub-pattern.
+
A pattern can contain multiple occurrences of the same variable.
Except in the case when these variables occur in different branches
of an
@@ -39854,7 +39864,9 @@ against the corresponding vector element.
.mets @(struct < pattern >> { slot-name << pattern }*)
.syne
.desc
-The structure pattern operator matches a structure object. The operator
+The
+.code struct
+pattern operator matches a structure object. The operator
supports two modes of matching, the choice of which depends on whether the
first argument is a
.meta name
@@ -39945,6 +39957,113 @@ object's structure type: the type itself, rather than its symbolic name.
(#<struct-type widget> :widg))
.brev
+.coNP Pattern operator @ hash
+.synb
+.mets @(hash >> {( key-pattern << value-pattern )}*)
+.syne
+.desc
+The
+.code hash
+pattern operator matches a hash table object by means of patterns
+which target keys, values or both.
+
+An important concept in the requirements governing the operation of the
+.code hash
+operator is that of a trivial pattern.
+
+A pattern is non-trivial if it is a variable or operator pattern.
+A pattern is also non-trivial if it is a list or vector pattern
+containing at least one non-trivial pattern. Otherwise, it is trivial.
+
+The
+.code hash
+operator requires the corresponding object to be a hash table,
+otherwise the match fails.
+
+If the corresponding object is a hash table, then matches each
+.meta key-pattern
+and
+.meta value-pattern
+pair against that object as described below. Each of
+the pairs must successfully match, otherwise the overall
+match fails.
+
+If
+.meta key-pattern
+is a trivial pattern, then the semantics of the match is that
+.meta key-pattern
+is taken as a literal object representing a hash key. The hash
+table is searched for that key. If the key is not found,
+the match fails. Otherwise, the value corresponding to
+that key is matched against the
+.meta value-pattern
+which may be trivial or non-trivial.
+
+If
+.meta key-pattern
+is a non-trivial pattern, but
+.meta value-pattern
+is trivial, then
+.meta value-pattern
+is taken as a literal object, which is used for searching
+the hash table for one or more keys, as if it were the
+.meta value
+argument in a call to the
+.code hash-keys-of
+function, to find all keys which have a value
+.code equal
+to that value. If no keys are found, then the match
+fails. Otherwise, the
+.code key-pattern
+is then matched against the retrieved list of hash keys.
+
+Finally, if both
+.meta key-pattern
+and
+.meta value-pattern
+are non-trivial, then an exhaustive search is performed of the hash table.
+Every key in the hash table is matched against
+.meta key-pattern
+and if it matches, the value is matched against
+.metn value-pattern .
+If both match, then the values from the matches are collected into lists.
+At least one matching key-value pair must be found, otherwise
+the overall match fails.
+Note: this situation can be understood as if the hash table were association
+list of
+.code cons
+cells of the form
+
+.verb
+.mets >> ( key . << value )
+.brev
+
+and as if the two patterns were combined into a
+.code coll
+operator against this list in the following way:
+
+.verb
+.mets @(coll >> ( key-pattern . << value-pattern ))
+.brev
+
+such that the semantics can then be understood in terms of the
+.code coll
+operator matching against an association list.
+
+.TP* Example:
+
+.verb
+ ;; First, (x @y) has a trivial key pattern so the x
+ ;; entry from the hash table is retrieved, the
+ ;; value being the symbol k. This k is bound to @y.
+ ;; Then the pattern (@y @datum) searches the entire
+ ;; hash table. The @y variable has a binding to k,
+ ;; so only the (k 42) entry is matched. The 42
+ ;; value matches @datum, and is collected into a list.
+ (when-match @(hash (x @y) (@y @datum)) #H(() (x k) (k 42)) datum)
+ --> (42)
+.brev
+
.coNP Pattern operator @ let
.synb
.mets @(let < name << pattern)