rng-match.el 52.3 KB
Newer Older
1
;;; rng-match.el --- matching of RELAX NG patterns against XML events  -*- lexical-binding:t -*-
Mark A. Hershberger's avatar
Mark A. Hershberger committed
2

3
;; Copyright (C) 2003, 2007-2014 Free Software Foundation, Inc.
Mark A. Hershberger's avatar
Mark A. Hershberger committed
4 5

;; Author: James Clark
6
;; Keywords: wp, hypermedia, languages, XML, RelaxNG
Mark A. Hershberger's avatar
Mark A. Hershberger committed
7

Glenn Morris's avatar
Glenn Morris committed
8
;; This file is part of GNU Emacs.
Mark A. Hershberger's avatar
Mark A. Hershberger committed
9

10
;; GNU Emacs is free software: you can redistribute it and/or modify
Glenn Morris's avatar
Glenn Morris committed
11
;; it under the terms of the GNU General Public License as published by
12 13
;; the Free Software Foundation, either version 3 of the License, or
;; (at your option) any later version.
Mark A. Hershberger's avatar
Mark A. Hershberger committed
14

Glenn Morris's avatar
Glenn Morris committed
15 16 17 18 19 20
;; GNU Emacs is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;; GNU General Public License for more details.

;; You should have received a copy of the GNU General Public License
21
;; along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.
Mark A. Hershberger's avatar
Mark A. Hershberger committed
22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

;;; Commentary:

;; This uses the algorithm described in
;;   http://www.thaiopensource.com/relaxng/derivative.html
;;
;; The schema to be used is contained in the variable
;; rng-current-schema.  It has the form described in the file
;; rng-pttrn.el.
;;
;;; Code:

(require 'rng-pttrn)
(require 'rng-util)
(require 'rng-dt)
37
(eval-when-compile (require 'cl-lib))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
38 39 40 41 42 43 44 45 46

(defvar rng-not-allowed-ipattern nil)
(defvar rng-empty-ipattern nil)
(defvar rng-text-ipattern nil)

(defvar rng-compile-table nil)

(defvar rng-being-compiled nil
  "Contains a list of ref patterns currently being compiled.
47
Used to detect invalid recursive references.")
Mark A. Hershberger's avatar
Mark A. Hershberger committed
48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

(defvar rng-ipattern-table nil)

(defvar rng-last-ipattern-index nil)

(defvar rng-match-state nil
  "An ipattern representing the current state of validation.")

;;; Inline functions

(defsubst rng-update-match-state (new-state)
  (if (and (eq new-state rng-not-allowed-ipattern)
	   (not (eq rng-match-state rng-not-allowed-ipattern)))
      nil
    (setq rng-match-state new-state)
    t))

;;; Interned patterns

67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
(cl-defstruct (rng--ipattern
               (:constructor nil)
               (:type vector)
               (:copier nil)
               (:constructor rng-make-ipattern
                (type index name-class child nullable)))
  type
  index
  name-class ;; Field also known as: `datatype' and `after'.
  child      ;; Field also known as: `value-object'.
  nullable
  (memo-text-typed 'unknown)
  memo-map-start-tag-open-deriv
  memo-map-start-attribute-deriv
  memo-start-tag-close-deriv
  memo-text-only-deriv
  memo-mixed-text-deriv
  memo-map-data-deriv
  memo-end-tag-deriv)

;; I think depending on the value of `type' the two fields after `index'
;; are used sometimes for different purposes, hence the aliases here:
(defalias 'rng--ipattern-datatype 'rng--ipattern-name-class)
(defalias 'rng--ipattern-after 'rng--ipattern-name-class)
(defalias 'rng--ipattern-value-object 'rng--ipattern-child)
Mark A. Hershberger's avatar
Mark A. Hershberger committed
92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108

(defconst rng-memo-map-alist-max 10)

(defsubst rng-memo-map-get (key mm)
  "Return the value associated with KEY in memo-map MM."
  (let ((found (assoc key mm)))
    (if found
	(cdr found)
      (and mm
	   (let ((head (car mm)))
	     (and (hash-table-p head)
		  (gethash key head)))))))

(defun rng-memo-map-add (key value mm &optional weakness)
  "Associate KEY with VALUE in memo-map MM and return the new memo-map.
The new memo-map may or may not be a different object from MM.

109
Alists are better for small maps.  Hash tables are better for large
Mark A. Hershberger's avatar
Mark A. Hershberger committed
110
maps.  A memo-map therefore starts off as an alist and switches to a
111 112
hash table for large memo-maps.  A memo-map is always a list.  An empty
memo-map is represented by nil.  A large memo-map is represented by a
Mark A. Hershberger's avatar
Mark A. Hershberger committed
113 114
list containing just a hash-table.  A small memo map is represented by
a list whose cdr is an alist and whose car is the number of entries in
115
the alist.  The complete memo-map can be passed to `assoc' without
Mark A. Hershberger's avatar
Mark A. Hershberger committed
116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137
problems: assoc ignores any members that are not cons cells.  There is
therefore minimal overhead in successful lookups on small lists
\(which is the most common case)."
  (if (null mm)
      (list 1 (cons key value))
    (let ((head (car mm)))
      (cond ((hash-table-p head)
	     (puthash key value head)
	     mm)
	    ((>= head rng-memo-map-alist-max)
	     (let ((ht (make-hash-table :test 'equal
					:weakness weakness
					:size (* 2 rng-memo-map-alist-max))))
	       (setq mm (cdr mm))
	       (while mm
		 (setq head (car mm))
		 (puthash (car head) (cdr head) ht)
		 (setq mm (cdr mm)))
	       (cons ht nil)))
	    (t (cons (1+ head)
		     (cons (cons key value)
			   (cdr mm))))))))
138

Mark A. Hershberger's avatar
Mark A. Hershberger committed
139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185
(defun rng-ipattern-maybe-init ()
  (unless rng-ipattern-table
    (setq rng-ipattern-table (make-hash-table :test 'equal))
    (setq rng-last-ipattern-index -1)))

(defun rng-ipattern-clear ()
  (when rng-ipattern-table
    (clrhash rng-ipattern-table))
  (setq rng-last-ipattern-index -1))

(defsubst rng-gen-ipattern-index ()
  (setq rng-last-ipattern-index (1+ rng-last-ipattern-index)))

(defun rng-put-ipattern (key type name-class child nullable)
  (let ((ipattern
	 (rng-make-ipattern type
			    (rng-gen-ipattern-index)
			    name-class
			    child
			    nullable)))
    (puthash key ipattern rng-ipattern-table)
    ipattern))

(defun rng-get-ipattern (key)
  (gethash key rng-ipattern-table))

(or rng-not-allowed-ipattern
    (setq rng-not-allowed-ipattern
	  (rng-make-ipattern 'not-allowed -3 nil nil nil)))

(or rng-empty-ipattern
    (setq rng-empty-ipattern
	  (rng-make-ipattern 'empty -2 nil nil t)))

(or rng-text-ipattern
    (setq rng-text-ipattern
	  (rng-make-ipattern 'text -1 nil nil t)))

(defconst rng-const-ipatterns
  (list rng-not-allowed-ipattern
	rng-empty-ipattern
	rng-text-ipattern))

(defun rng-intern-after (child after)
  (if (eq child rng-not-allowed-ipattern)
      rng-not-allowed-ipattern
    (let ((key (list 'after
186 187
		     (rng--ipattern-index child)
		     (rng--ipattern-index after))))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
188 189 190 191 192 193
      (or (rng-get-ipattern key)
	  (rng-put-ipattern key
			    'after
			    after
			    child
			    nil)))))
194

Mark A. Hershberger's avatar
Mark A. Hershberger committed
195 196 197 198 199
(defun rng-intern-attribute (name-class ipattern)
  (if (eq ipattern rng-not-allowed-ipattern)
      rng-not-allowed-ipattern
    (let ((key (list 'attribute
		     name-class
200
		     (rng--ipattern-index ipattern))))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
201 202 203 204 205 206 207 208 209 210 211 212 213 214 215
      (or (rng-get-ipattern key)
	  (rng-put-ipattern key
			    'attribute
			    name-class
			    ipattern
			    nil)))))

(defun rng-intern-data (dt matches-anything)
  (let ((key (list 'data dt)))
    (or (rng-get-ipattern key)
	(let ((ipattern (rng-put-ipattern key
					  'data
					  dt
					  nil
					  matches-anything)))
216 217
	  (setf (rng--ipattern-memo-text-typed ipattern)
                (not matches-anything))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240
	  ipattern))))

(defun rng-intern-data-except (dt ipattern)
  (let ((key (list 'data-except dt ipattern)))
    (or (rng-get-ipattern key)
	(rng-put-ipattern key
			  'data-except
			  dt
			  ipattern
			  nil))))

(defun rng-intern-value (dt obj)
  (let ((key (list 'value dt obj)))
    (or (rng-get-ipattern key)
	(rng-put-ipattern key
			  'value
			  dt
			  obj
			  nil))))

(defun rng-intern-one-or-more (ipattern)
  (or (rng-intern-one-or-more-shortcut ipattern)
      (let ((key (cons 'one-or-more
241
		       (list (rng--ipattern-index ipattern)))))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
242 243 244 245 246
	(or (rng-get-ipattern key)
	    (rng-put-ipattern key
			      'one-or-more
			      nil
			      ipattern
247
			      (rng--ipattern-nullable ipattern))))))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
248 249 250 251 252 253

(defun rng-intern-one-or-more-shortcut (ipattern)
  (cond ((eq ipattern rng-not-allowed-ipattern)
	 rng-not-allowed-ipattern)
	((eq ipattern rng-empty-ipattern)
	 rng-empty-ipattern)
254
	((eq (rng--ipattern-type ipattern) 'one-or-more)
Mark A. Hershberger's avatar
Mark A. Hershberger committed
255 256 257 258 259 260 261
	 ipattern)
	(t nil)))

(defun rng-intern-list (ipattern)
  (if (eq ipattern rng-not-allowed-ipattern)
      rng-not-allowed-ipattern
    (let ((key (cons 'list
262
		     (list (rng--ipattern-index ipattern)))))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
263 264 265 266 267 268 269 270
      (or (rng-get-ipattern key)
	  (rng-put-ipattern key
			    'list
			    nil
			    ipattern
			    nil)))))

(defun rng-intern-group (ipatterns)
271
  "Return an ipattern for the list of group members in IPATTERNS."
Mark A. Hershberger's avatar
Mark A. Hershberger committed
272 273 274 275 276
  (or (rng-intern-group-shortcut ipatterns)
      (let* ((tem (rng-normalize-group-list ipatterns))
	     (normalized (cdr tem)))
	(or (rng-intern-group-shortcut normalized)
	    (let ((key (cons 'group
277
			     (mapcar #'rng--ipattern-index normalized))))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
278 279 280 281 282 283 284 285
	      (or (rng-get-ipattern key)
		  (rng-put-ipattern key
				    'group
				    nil
				    normalized
				    (car tem))))))))

(defun rng-intern-group-shortcut (ipatterns)
286 287
  "Try to shortcut interning a group list.
If successful, return the interned pattern.  Otherwise return nil."
Mark A. Hershberger's avatar
Mark A. Hershberger committed
288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322
  (while (and ipatterns
	      (eq (car ipatterns) rng-empty-ipattern))
    (setq ipatterns (cdr ipatterns)))
  (if ipatterns
      (let ((ret (car ipatterns)))
	(if (eq ret rng-not-allowed-ipattern)
	    rng-not-allowed-ipattern
	  (setq ipatterns (cdr ipatterns))
	  (while (and ipatterns ret)
	    (let ((tem (car ipatterns)))
	      (cond ((eq tem rng-not-allowed-ipattern)
		     (setq ret tem)
		     (setq ipatterns nil))
		    ((eq tem rng-empty-ipattern)
		     (setq ipatterns (cdr ipatterns)))
		    (t
		     ;; Stop here rather than continuing
		     ;; looking for not-allowed patterns.
		     ;; We do a complete scan elsewhere.
		     (setq ret nil)))))
	  ret))
    rng-empty-ipattern))

(defun rng-normalize-group-list (ipatterns)
  "Normalize a list containing members of a group.
Expands nested groups, removes empty members, handles notAllowed.
Returns a pair whose car says whether the list is nullable and whose
cdr is the normalized list."
  (let ((nullable t)
	(result nil)
	member)
    (while ipatterns
      (setq member (car ipatterns))
      (setq ipatterns (cdr ipatterns))
      (when nullable
323 324
	(setq nullable (rng--ipattern-nullable member)))
      (cond ((eq (rng--ipattern-type member) 'group)
Mark A. Hershberger's avatar
Mark A. Hershberger committed
325
	     (setq result
326
		   (nconc (reverse (rng--ipattern-child member))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
327 328 329 330 331 332 333 334 335 336 337 338 339 340
			  result)))
	    ((eq member rng-not-allowed-ipattern)
	     (setq result (list rng-not-allowed-ipattern))
	     (setq ipatterns nil))
	    ((not (eq member rng-empty-ipattern))
	     (setq result (cons member result)))))
    (cons nullable (nreverse result))))

(defun rng-intern-interleave (ipatterns)
  (or (rng-intern-group-shortcut ipatterns)
      (let* ((tem (rng-normalize-interleave-list ipatterns))
	     (normalized (cdr tem)))
	(or (rng-intern-group-shortcut normalized)
	    (let ((key (cons 'interleave
341
			     (mapcar #'rng--ipattern-index normalized))))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360
	      (or (rng-get-ipattern key)
		  (rng-put-ipattern key
				    'interleave
				    nil
				    normalized
				    (car tem))))))))

(defun rng-normalize-interleave-list (ipatterns)
  "Normalize a list containing members of an interleave.
Expands nested groups, removes empty members, handles notAllowed.
Returns a pair whose car says whether the list is nullable and whose
cdr is the normalized list."
  (let ((nullable t)
	(result nil)
	member)
    (while ipatterns
      (setq member (car ipatterns))
      (setq ipatterns (cdr ipatterns))
      (when nullable
361 362
	(setq nullable (rng--ipattern-nullable member)))
      (cond ((eq (rng--ipattern-type member) 'interleave)
Mark A. Hershberger's avatar
Mark A. Hershberger committed
363
	     (setq result
364
		   (append (rng--ipattern-child member)
Mark A. Hershberger's avatar
Mark A. Hershberger committed
365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384
			    result)))
	    ((eq member rng-not-allowed-ipattern)
	     (setq result (list rng-not-allowed-ipattern))
	     (setq ipatterns nil))
	    ((not (eq member rng-empty-ipattern))
	     (setq result (cons member result)))))
    (cons nullable (sort result 'rng-compare-ipattern))))

;; Would be cleaner if this didn't modify IPATTERNS.

(defun rng-intern-choice (ipatterns)
  "Return a choice ipattern for the list of choices in IPATTERNS.
May alter IPATTERNS."
  (or (rng-intern-choice-shortcut ipatterns)
      (let* ((tem (rng-normalize-choice-list ipatterns))
	     (normalized (cdr tem)))
	(or (rng-intern-choice-shortcut normalized)
	    (rng-intern-choice1 normalized (car tem))))))

(defun rng-intern-optional (ipattern)
385
  (cond ((rng--ipattern-nullable ipattern) ipattern)
Mark A. Hershberger's avatar
Mark A. Hershberger committed
386 387 388 389 390 391 392
	((eq ipattern rng-not-allowed-ipattern) rng-empty-ipattern)
	(t (rng-intern-choice1
	    ;; This is sorted since the empty pattern
	    ;; is before everything except not allowed.
	    ;; It cannot have a duplicate empty pattern,
	    ;; since it is not nullable.
	    (cons rng-empty-ipattern
393 394
		  (if (eq (rng--ipattern-type ipattern) 'choice)
		      (rng--ipattern-child ipattern)
Mark A. Hershberger's avatar
Mark A. Hershberger committed
395 396 397 398 399 400
		    (list ipattern)))
	    t))))


(defun rng-intern-choice1 (normalized nullable)
  (let ((key (cons 'choice
401
		   (mapcar #'rng--ipattern-index normalized))))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
402 403 404 405 406 407
    (or (rng-get-ipattern key)
	(rng-put-ipattern key
			  'choice
			  nil
			  normalized
			  nullable))))
408

Mark A. Hershberger's avatar
Mark A. Hershberger committed
409
(defun rng-intern-choice-shortcut (ipatterns)
410 411
  "Try to shortcut interning a choice list.
If successful, return the interned pattern.  Otherwise return nil."
Mark A. Hershberger's avatar
Mark A. Hershberger committed
412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427
  (while (and ipatterns
	      (eq (car ipatterns)
		  rng-not-allowed-ipattern))
    (setq ipatterns (cdr ipatterns)))
  (if ipatterns
      (let ((ret (car ipatterns)))
	(setq ipatterns (cdr ipatterns))
	(while (and ipatterns ret)
	  (or (eq (car ipatterns) rng-not-allowed-ipattern)
	      (eq (car ipatterns) ret)
	      (setq ret nil))
	  (setq ipatterns (cdr ipatterns)))
	ret)
    rng-not-allowed-ipattern))

(defun rng-normalize-choice-list (ipatterns)
428 429 430 431
  "Normalize a list of choices.
Expands nested choices, removes not-allowed members, sorts by index
and removes duplicates.  Return a pair whose car says whether the
list is nullable and whose cdr is the normalized list."
Mark A. Hershberger's avatar
Mark A. Hershberger committed
432 433 434 435 436 437 438 439 440 441 442 443
  (let ((sorted t)
	(nullable nil)
	(head (cons nil ipatterns)))
    (let ((tail head)
	  (final-tail nil)
	  (prev-index -100)
	  (cur ipatterns)
	  member)
      ;; the cdr of tail is always cur
      (while cur
	(setq member (car cur))
	(or nullable
444 445
	    (setq nullable (rng--ipattern-nullable member)))
	(cond ((eq (rng--ipattern-type member) 'choice)
Mark A. Hershberger's avatar
Mark A. Hershberger committed
446
	       (setq final-tail
447
		     (append (rng--ipattern-child member)
Mark A. Hershberger's avatar
Mark A. Hershberger committed
448 449 450 451 452 453 454 455 456
			     final-tail))
	       (setq cur (cdr cur))
	       (setq sorted nil)
	       (setcdr tail cur))
	      ((eq member rng-not-allowed-ipattern)
	       (setq cur (cdr cur))
	       (setcdr tail cur))
	      (t
	       (if (and sorted
457
			(let ((cur-index (rng--ipattern-index member)))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478
			  (if (>= prev-index cur-index)
			      (or (= prev-index cur-index) ; will remove it
				  (setq sorted nil)) ; won't remove it
			    (setq prev-index cur-index)
			    ;; won't remove it
			    nil)))
		   (progn
		     ;; remove it
		     (setq cur (cdr cur))
		     (setcdr tail cur))
		 ;; don't remove it
		 (setq tail cur)
		 (setq cur (cdr cur))))))
      (setcdr tail final-tail))
    (setq head (cdr head))
    (cons nullable
	  (if sorted
	      head
	    (rng-uniquify-eq (sort head 'rng-compare-ipattern))))))

(defun rng-compare-ipattern (p1 p2)
479 480
  (< (rng--ipattern-index p1)
     (rng--ipattern-index p2)))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514

;;; Name classes

(defsubst rng-name-class-contains (nc nm)
  (if (consp nc)
      (equal nm nc)
    (rng-name-class-contains1 nc nm)))

(defun rng-name-class-contains1 (nc nm)
  (let ((type (aref nc 0)))
    (cond ((eq type 'any-name) t)
	  ((eq type 'any-name-except)
	   (not (rng-name-class-contains (aref nc 1) nm)))
	  ((eq type 'ns-name)
	   (eq (car nm) (aref nc 1)))
	  ((eq type 'ns-name-except)
	   (and (eq (car nm) (aref nc 1))
		(not (rng-name-class-contains (aref nc 2) nm))))
	  ((eq type 'choice)
	   (let ((choices (aref nc 1))
		 (ret nil))
	     (while choices
	       (if (rng-name-class-contains (car choices) nm)
		   (progn
		     (setq choices nil)
		     (setq ret t))
		 (setq choices (cdr choices))))
	     ret)))))

(defun rng-name-class-possible-names (nc accum)
  "Return a list of possible names that nameclass NC can match.

Each possible name should be returned as a (NAMESPACE . LOCAL-NAME)
pair, where NAMESPACE is a symbol or nil and LOCAL-NAME is a string.
515 516 517
NAMESPACE, if nil, matches the absent namespace.  ACCUM is a list of
names which should be appended to the returned list.  The returned
list may contain duplicates."
Mark A. Hershberger's avatar
Mark A. Hershberger committed
518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534
  (if (consp nc)
      (cons nc accum)
    (when (eq (aref nc 0) 'choice)
      (let ((members (aref nc 1)) member)
	(while members
	  (setq member (car members))
	  (setq accum
		(if (consp member)
		    (cons member accum)
		  (rng-name-class-possible-names member
						 accum)))
	  (setq members (cdr members)))))
    accum))

;;; Debugging utilities

(defun rng-ipattern-to-string (ipattern)
535
  (let ((type (rng--ipattern-type ipattern)))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
536 537
    (cond ((eq type 'after)
	   (concat (rng-ipattern-to-string
538
		    (rng--ipattern-child ipattern))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
539 540
		   " </> "
		   (rng-ipattern-to-string
541
		    (rng--ipattern-after ipattern))))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
542 543 544
	  ((eq type 'element)
	   (concat "element "
		   (rng-name-class-to-string
545
		    (rng--ipattern-name-class ipattern))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
546 547 548 549 550
		   ;; we can get cycles with elements so don't print it out
		   " {...}"))
	  ((eq type 'attribute)
	   (concat "attribute "
		   (rng-name-class-to-string
551
		    (rng--ipattern-name-class ipattern))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
552 553
		   " { "
		   (rng-ipattern-to-string
554
		    (rng--ipattern-child ipattern))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
555 556 557 558 559 560
		   " } "))
	  ((eq type 'empty) "empty")
	  ((eq type 'text) "text")
	  ((eq type 'not-allowed) "notAllowed")
	  ((eq type 'one-or-more)
	   (concat (rng-ipattern-to-string
561
		    (rng--ipattern-child ipattern))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
562 563 564 565
		   "+"))
	  ((eq type 'choice)
	   (concat "("
		   (mapconcat 'rng-ipattern-to-string
566
			      (rng--ipattern-child ipattern)
Mark A. Hershberger's avatar
Mark A. Hershberger committed
567 568 569 570 571
			      " | ")
		   ")"))
	  ((eq type 'group)
	   (concat "("
		   (mapconcat 'rng-ipattern-to-string
572
			      (rng--ipattern-child ipattern)
Mark A. Hershberger's avatar
Mark A. Hershberger committed
573 574 575 576 577
			      ", ")
		   ")"))
	  ((eq type 'interleave)
	   (concat "("
		   (mapconcat 'rng-ipattern-to-string
578
			      (rng--ipattern-child ipattern)
Mark A. Hershberger's avatar
Mark A. Hershberger committed
579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641
			      " & ")
		   ")"))
	  (t (symbol-name type)))))

(defun rng-name-class-to-string (nc)
  (if (consp nc)
      (cdr nc)
    (let ((type (aref nc 0)))
      (cond ((eq type 'choice)
	     (mapconcat 'rng-name-class-to-string
			(aref nc 1)
			"|"))
	    (t (concat (symbol-name type) "*"))))))


;;; Compiling

(defun rng-compile-maybe-init ()
  (unless rng-compile-table
    (setq rng-compile-table (make-hash-table :test 'eq))))

(defun rng-compile-clear ()
  (when rng-compile-table
    (clrhash rng-compile-table)))

(defun rng-compile (pattern)
  (or (gethash pattern rng-compile-table)
      (let ((ipattern (apply (get (car pattern) 'rng-compile)
			     (cdr pattern))))
	(puthash pattern ipattern rng-compile-table)
	ipattern)))

(put 'empty 'rng-compile 'rng-compile-empty)
(put 'text 'rng-compile 'rng-compile-text)
(put 'not-allowed 'rng-compile 'rng-compile-not-allowed)
(put 'element 'rng-compile 'rng-compile-element)
(put 'attribute 'rng-compile 'rng-compile-attribute)
(put 'choice 'rng-compile 'rng-compile-choice)
(put 'optional 'rng-compile 'rng-compile-optional)
(put 'group 'rng-compile 'rng-compile-group)
(put 'interleave 'rng-compile 'rng-compile-interleave)
(put 'ref 'rng-compile 'rng-compile-ref)
(put 'one-or-more 'rng-compile 'rng-compile-one-or-more)
(put 'zero-or-more 'rng-compile 'rng-compile-zero-or-more)
(put 'mixed 'rng-compile 'rng-compile-mixed)
(put 'data 'rng-compile 'rng-compile-data)
(put 'data-except 'rng-compile 'rng-compile-data-except)
(put 'value 'rng-compile 'rng-compile-value)
(put 'list 'rng-compile 'rng-compile-list)

(defun rng-compile-not-allowed () rng-not-allowed-ipattern)
(defun rng-compile-empty () rng-empty-ipattern)
(defun rng-compile-text () rng-text-ipattern)

(defun rng-compile-element (name-class pattern)
  ;; don't intern
  (rng-make-ipattern 'element
		     (rng-gen-ipattern-index)
		     (rng-compile-name-class name-class)
		     pattern		; compile lazily
		     nil))

(defun rng-element-get-child (element)
642
  (let ((tem (rng--ipattern-child element)))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
643 644
    (if (vectorp tem)
	tem
645
      (setf (rng--ipattern-child element) (rng-compile tem)))))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
646 647 648 649 650 651 652 653 654 655 656 657 658 659

(defun rng-compile-attribute (name-class pattern)
  (rng-intern-attribute (rng-compile-name-class name-class)
			(rng-compile pattern)))

(defun rng-compile-ref (pattern name)
  (and (memq pattern rng-being-compiled)
       (rng-compile-error "Reference loop on symbol %s" name))
  (setq rng-being-compiled
	(cons pattern rng-being-compiled))
  (unwind-protect
      (rng-compile pattern)
    (setq rng-being-compiled
	  (cdr rng-being-compiled))))
660

Mark A. Hershberger's avatar
Mark A. Hershberger committed
661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711
(defun rng-compile-one-or-more (pattern)
  (rng-intern-one-or-more (rng-compile pattern)))

(defun rng-compile-zero-or-more (pattern)
  (rng-intern-optional
   (rng-intern-one-or-more (rng-compile pattern))))

(defun rng-compile-optional (pattern)
  (rng-intern-optional (rng-compile pattern)))

(defun rng-compile-mixed (pattern)
  (rng-intern-interleave (cons rng-text-ipattern
			       (list (rng-compile pattern)))))

(defun rng-compile-list (pattern)
  (rng-intern-list (rng-compile pattern)))

(defun rng-compile-choice (&rest patterns)
  (rng-intern-choice (mapcar 'rng-compile patterns)))

(defun rng-compile-group (&rest patterns)
  (rng-intern-group (mapcar 'rng-compile patterns)))

(defun rng-compile-interleave (&rest patterns)
  (rng-intern-interleave (mapcar 'rng-compile patterns)))

(defun rng-compile-dt (name params)
  (let ((rng-dt-error-reporter 'rng-compile-error))
    (funcall (let ((uri (car name)))
	       (or (get uri 'rng-dt-compile)
		   (rng-compile-error "Unknown datatype library %s" uri)))
	     (cdr name)
	     params)))

(defun rng-compile-data (name params)
  (let ((dt (rng-compile-dt name params)))
    (rng-intern-data (cdr dt) (car dt))))

(defun rng-compile-data-except (name params pattern)
  (rng-intern-data-except (cdr (rng-compile-dt name params))
			  (rng-compile pattern)))

(defun rng-compile-value (name str context)
  (let* ((dt (cdr (rng-compile-dt name '())))
	 (rng-dt-namespace-context-getter (list 'identity context))
	 (obj (rng-dt-make-value dt str)))
    (if obj
	(rng-intern-value dt obj)
      (rng-compile-error "Value %s is not a valid instance of the datatype %s"
			 str
			 name))))
712

Mark A. Hershberger's avatar
Mark A. Hershberger committed
713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816
(defun rng-compile-name-class (nc)
  (let ((type (car nc)))
    (cond ((eq type 'name) (nth 1 nc))
	  ((eq type 'any-name) [any-name])
	  ((eq type 'any-name-except)
	   (vector 'any-name-except
		   (rng-compile-name-class (nth 1 nc))))
	  ((eq type 'ns-name)
	   (vector 'ns-name (nth 1 nc)))
	  ((eq type 'ns-name-except)
	   (vector 'ns-name-except
		   (nth 1 nc)
		   (rng-compile-name-class (nth 2 nc))))
	  ((eq type 'choice)
	   (vector 'choice
		   (mapcar 'rng-compile-name-class (cdr nc))))
	  (t (error "Bad name-class type %s" type)))))

;;; Searching patterns

;; We write this non-recursively to avoid hitting max-lisp-eval-depth
;; on large schemas.

(defun rng-map-element-attribute (function pattern accum &rest args)
  (let ((searched (make-hash-table :test 'eq))
	type todo patterns)
    (while (progn
	     (setq type (car pattern))
	     (cond ((memq type '(element attribute))
		    (setq accum
			  (apply function
				 (cons pattern
				       (cons accum args))))
		    (setq pattern (nth 2 pattern)))
		   ((eq type 'ref)
		    (setq pattern (nth 1 pattern))
		    (if (gethash pattern searched)
			(setq pattern nil)
		      (puthash pattern t searched)))
		   ((memq type '(choice group interleave))
		    (setq todo (cons (cdr pattern) todo))
		    (setq pattern nil))
		   ((memq type '(one-or-more
				 zero-or-more
				 optional
				 mixed))
		    (setq pattern (nth 1 pattern)))
		   (t (setq pattern nil)))
	     (cond (pattern)
		   (patterns
		    (setq pattern (car patterns))
		    (setq patterns (cdr patterns))
		    t)
		   (todo
		    (setq patterns (car todo))
		    (setq todo (cdr todo))
		    (setq pattern (car patterns))
		    (setq patterns (cdr patterns))
		    t))))
    accum))

(defun rng-find-element-content-pattern (pattern accum name)
  (if (and (eq (car pattern) 'element)
	   (rng-search-name name (nth 1 pattern)))
      (cons (rng-compile (nth 2 pattern)) accum)
    accum))

(defun rng-search-name (name nc)
  (let ((type (car nc)))
    (cond ((eq type 'name)
	   (equal (cadr nc) name))
	  ((eq type 'choice)
	   (let ((choices (cdr nc))
		 (found nil))
	     (while (and choices (not found))
	       (if (rng-search-name name (car choices))
		   (setq found t)
		 (setq choices (cdr choices))))
	     found))
	  (t nil))))

(defun rng-find-name-class-uris (nc accum)
  (let ((type (car nc)))
    (cond ((eq type 'name)
	   (rng-accum-namespace-uri (car (nth 1 nc)) accum))
	  ((memq type '(ns-name ns-name-except))
	   (rng-accum-namespace-uri (nth 1 nc) accum))
	  ((eq type 'choice)
	   (let ((choices (cdr nc)))
	     (while choices
	       (setq accum
		     (rng-find-name-class-uris (car choices) accum))
	       (setq choices (cdr choices))))
	   accum)
	  (t accum))))

(defun rng-accum-namespace-uri (ns accum)
  (if (and ns (not (memq ns accum)))
      (cons ns accum)
    accum))

;;; Derivatives

(defun rng-ipattern-text-typed-p (ipattern)
817
  (let ((memo (rng--ipattern-memo-text-typed ipattern)))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
818
    (if (eq memo 'unknown)
819 820
	(setf (rng--ipattern-memo-text-typed ipattern)
              (rng-ipattern-compute-text-typed-p ipattern))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
821 822 823
      memo)))

(defun rng-ipattern-compute-text-typed-p (ipattern)
824
  (let ((type (rng--ipattern-type ipattern)))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
825
    (cond ((eq type 'choice)
826
	   (let ((cur (rng--ipattern-child ipattern))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
827 828 829 830 831 832 833
		 (ret nil))
	     (while (and cur (not ret))
	       (if (rng-ipattern-text-typed-p (car cur))
		   (setq ret t)
		 (setq cur (cdr cur))))
	     ret))
	  ((eq type 'group)
834
	   (let ((cur (rng--ipattern-child ipattern))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
835 836 837 838 839 840 841
		 (ret nil)
		 member)
	     (while (and cur (not ret))
	       (setq member (car cur))
	       (if (rng-ipattern-text-typed-p member)
		   (setq ret t))
	       (setq cur
842
		     (and (rng--ipattern-nullable member)
Mark A. Hershberger's avatar
Mark A. Hershberger committed
843 844 845
			  (cdr cur))))
	     ret))
	  ((eq type 'after)
846
	   (rng-ipattern-text-typed-p (rng--ipattern-child ipattern)))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
847
	  (t (and (memq type '(value list data data-except)) t)))))
848

Mark A. Hershberger's avatar
Mark A. Hershberger committed
849 850 851
(defun rng-start-tag-open-deriv (ipattern nm)
  (or (rng-memo-map-get
       nm
852
       (rng--ipattern-memo-map-start-tag-open-deriv ipattern))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
853 854
      (rng-ipattern-memo-start-tag-open-deriv
       ipattern
855
       nm
Mark A. Hershberger's avatar
Mark A. Hershberger committed
856
       (rng-compute-start-tag-open-deriv ipattern nm))))
857

Mark A. Hershberger's avatar
Mark A. Hershberger committed
858 859
(defun rng-ipattern-memo-start-tag-open-deriv (ipattern nm deriv)
  (or (memq ipattern rng-const-ipatterns)
860 861 862 863 864
      (setf (rng--ipattern-memo-map-start-tag-open-deriv ipattern)
            (rng-memo-map-add nm
                              deriv
                              (rng--ipattern-memo-map-start-tag-open-deriv
                               ipattern))))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
865 866 867
  deriv)

(defun rng-compute-start-tag-open-deriv (ipattern nm)
868
  (let ((type (rng--ipattern-type ipattern)))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
869
    (cond ((eq type 'choice)
870 871
	   (rng-transform-choice (lambda (p)
                                   (rng-start-tag-open-deriv p nm))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
872 873 874
				 ipattern))
	  ((eq type 'element)
	   (if (rng-name-class-contains
875
		(rng--ipattern-name-class ipattern)
Mark A. Hershberger's avatar
Mark A. Hershberger committed
876 877 878 879 880 881
		nm)
	       (rng-intern-after (rng-element-get-child ipattern)
				 rng-empty-ipattern)
	     rng-not-allowed-ipattern))
	  ((eq type 'group)
	   (rng-transform-group-nullable
882
	    (lambda (p) (rng-start-tag-open-deriv p nm))
883
	    'rng-cons-group-after
Mark A. Hershberger's avatar
Mark A. Hershberger committed
884 885 886
	    ipattern))
	  ((eq type 'interleave)
	   (rng-transform-interleave-single
887
	    (lambda (p) (rng-start-tag-open-deriv p nm))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
888 889 890
	    'rng-subst-interleave-after
	    ipattern))
	  ((eq type 'one-or-more)
891 892 893 894 895
           (let ((ip (rng-intern-optional ipattern)))
             (rng-apply-after
              (lambda (p) (rng-intern-group (list p ip)))
              (rng-start-tag-open-deriv (rng--ipattern-child ipattern)
                                        nm))))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
896
	  ((eq type 'after)
897 898 899 900 901
           (let ((nip (rng--ipattern-after ipattern)))
             (rng-apply-after
              (lambda (p) (rng-intern-after p nip))
              (rng-start-tag-open-deriv (rng--ipattern-child ipattern)
                                        nm))))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
902 903 904 905 906
	  (t rng-not-allowed-ipattern))))

(defun rng-start-attribute-deriv (ipattern nm)
  (or (rng-memo-map-get
       nm
907
       (rng--ipattern-memo-map-start-attribute-deriv ipattern))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
908 909
      (rng-ipattern-memo-start-attribute-deriv
       ipattern
910
       nm
Mark A. Hershberger's avatar
Mark A. Hershberger committed
911
       (rng-compute-start-attribute-deriv ipattern nm))))
912

Mark A. Hershberger's avatar
Mark A. Hershberger committed
913 914
(defun rng-ipattern-memo-start-attribute-deriv (ipattern nm deriv)
  (or (memq ipattern rng-const-ipatterns)
915 916 917 918 919
      (setf (rng--ipattern-memo-map-start-attribute-deriv ipattern)
            (rng-memo-map-add
             nm
             deriv
             (rng--ipattern-memo-map-start-attribute-deriv ipattern))))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
920 921 922
  deriv)

(defun rng-compute-start-attribute-deriv (ipattern nm)
923
  (let ((type (rng--ipattern-type ipattern)))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
924
    (cond ((eq type 'choice)
925 926
	   (rng-transform-choice (lambda (p)
                                   (rng-start-attribute-deriv p nm))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
927 928 929
				 ipattern))
	  ((eq type 'attribute)
	   (if (rng-name-class-contains
930
		(rng--ipattern-name-class ipattern)
Mark A. Hershberger's avatar
Mark A. Hershberger committed
931
		nm)
932
	       (rng-intern-after (rng--ipattern-child ipattern)
Mark A. Hershberger's avatar
Mark A. Hershberger committed
933 934 935 936
				 rng-empty-ipattern)
	     rng-not-allowed-ipattern))
	  ((eq type 'group)
	   (rng-transform-interleave-single
937
	    (lambda (p) (rng-start-attribute-deriv p nm))
938
	    'rng-subst-group-after
Mark A. Hershberger's avatar
Mark A. Hershberger committed
939 940 941
	    ipattern))
	  ((eq type 'interleave)
	   (rng-transform-interleave-single
942
	    (lambda (p) (rng-start-attribute-deriv p nm))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
943 944 945
	    'rng-subst-interleave-after
	    ipattern))
	  ((eq type 'one-or-more)
946 947 948 949 950
           (let ((ip (rng-intern-optional ipattern)))
             (rng-apply-after
              (lambda (p) (rng-intern-group (list p ip)))
              (rng-start-attribute-deriv (rng--ipattern-child ipattern)
                                         nm))))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
951
	  ((eq type 'after)
952 953 954 955 956
           (let ((nip (rng--ipattern-after ipattern)))
             (rng-apply-after
              (lambda (p) (rng-intern-after p nip))
              (rng-start-attribute-deriv (rng--ipattern-child ipattern)
                                         nm))))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
957 958 959
	  (t rng-not-allowed-ipattern))))

(defun rng-cons-group-after (x y)
960
  (rng-apply-after (lambda (p) (rng-intern-group (cons p y)))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
961 962 963
		   x))

(defun rng-subst-group-after (new old list)
964 965
  (rng-apply-after (lambda (p)
                     (rng-intern-group (rng-substq p old list)))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
966 967 968
		   new))

(defun rng-subst-interleave-after (new old list)
969 970
  (rng-apply-after (lambda (p)
                     (rng-intern-interleave (rng-substq p old list)))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
971 972 973
		   new))

(defun rng-apply-after (f ipattern)
974
  (let ((type (rng--ipattern-type ipattern)))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
975 976
    (cond ((eq type 'after)
	   (rng-intern-after
977 978
	    (rng--ipattern-child ipattern)
	    (funcall f (rng--ipattern-after ipattern))))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
979
	  ((eq type 'choice)
980
	   (rng-transform-choice (lambda (x) (rng-apply-after f x))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
981 982 983 984
				 ipattern))
	  (t rng-not-allowed-ipattern))))

(defun rng-start-tag-close-deriv (ipattern)
985 986 987
  (or (rng--ipattern-memo-start-tag-close-deriv ipattern)
      (setf (rng--ipattern-memo-start-tag-close-deriv ipattern)
            (rng-compute-start-tag-close-deriv ipattern))))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
988 989 990 991 992 993 994 995 996

(defconst rng-transform-map
  '((choice . rng-transform-choice)
    (group . rng-transform-group)
    (interleave . rng-transform-interleave)
    (one-or-more . rng-transform-one-or-more)
    (after . rng-transform-after-child)))

(defun rng-compute-start-tag-close-deriv (ipattern)
997
  (let* ((type (rng--ipattern-type ipattern)))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
998 999 1000 1001 1002 1003 1004 1005 1006 1007
    (if (eq type 'attribute)
	rng-not-allowed-ipattern
      (let ((transform (assq type rng-transform-map)))
	(if transform
	    (funcall (cdr transform)
		     'rng-start-tag-close-deriv
		     ipattern)
	  ipattern)))))

(defun rng-ignore-attributes-deriv (ipattern)
1008
  (let* ((type (rng--ipattern-type ipattern)))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1009 1010 1011 1012 1013 1014 1015 1016
    (if (eq type 'attribute)
	rng-empty-ipattern
      (let ((transform (assq type rng-transform-map)))
	(if transform
	    (funcall (cdr transform)
		     'rng-ignore-attributes-deriv
		     ipattern)
	  ipattern)))))
1017

Mark A. Hershberger's avatar
Mark A. Hershberger committed
1018
(defun rng-text-only-deriv (ipattern)
1019 1020 1021
  (or (rng--ipattern-memo-text-only-deriv ipattern)
      (setf (rng--ipattern-memo-text-only-deriv ipattern)
            (rng-compute-text-only-deriv ipattern))))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1022 1023

(defun rng-compute-text-only-deriv (ipattern)
1024
  (let* ((type (rng--ipattern-type ipattern)))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039
    (if (eq type 'element)
	rng-not-allowed-ipattern
      (let ((transform (assq type
			     '((choice . rng-transform-choice)
			       (group . rng-transform-group)
			       (interleave . rng-transform-interleave)
			       (one-or-more . rng-transform-one-or-more)
			       (after . rng-transform-after-child)))))
	(if transform
	    (funcall (cdr transform)
		     'rng-text-only-deriv
		     ipattern)
	  ipattern)))))

(defun rng-mixed-text-deriv (ipattern)
1040 1041 1042
  (or (rng--ipattern-memo-mixed-text-deriv ipattern)
      (setf (rng--ipattern-memo-mixed-text-deriv ipattern)
            (rng-compute-mixed-text-deriv ipattern))))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1043 1044

(defun rng-compute-mixed-text-deriv (ipattern)
1045
  (let ((type (rng--ipattern-type ipattern)))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1046 1047 1048 1049 1050 1051 1052 1053 1054 1055
    (cond ((eq type 'text) ipattern)
	  ((eq type 'after)
	   (rng-transform-after-child 'rng-mixed-text-deriv
				      ipattern))
	  ((eq type 'choice)
	   (rng-transform-choice 'rng-mixed-text-deriv
				 ipattern))
	  ((eq type 'one-or-more)
	   (rng-intern-group
	    (list (rng-mixed-text-deriv
1056
		   (rng--ipattern-child ipattern))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069
		  (rng-intern-optional ipattern))))
	  ((eq type 'group)
	   (rng-transform-group-nullable
	    'rng-mixed-text-deriv
	    (lambda (x y) (rng-intern-group (cons x y)))
	    ipattern))
	  ((eq type 'interleave)
	   (rng-transform-interleave-single
	    'rng-mixed-text-deriv
	    (lambda (new old list) (rng-intern-interleave
				    (rng-substq new old list)))
	    ipattern))
	  ((and (eq type 'data)
1070
		(not (rng--ipattern-memo-text-typed ipattern)))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1071 1072 1073 1074
	   ipattern)
	  (t rng-not-allowed-ipattern))))

(defun rng-end-tag-deriv (ipattern)
1075 1076 1077
  (or (rng--ipattern-memo-end-tag-deriv ipattern)
      (setf (rng--ipattern-memo-end-tag-deriv ipattern)
            (rng-compute-end-tag-deriv ipattern))))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1078 1079

(defun rng-compute-end-tag-deriv (ipattern)
1080
  (let ((type (rng--ipattern-type ipattern)))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1081 1082 1083
    (cond ((eq type 'choice)
	   (rng-intern-choice
	    (mapcar 'rng-end-tag-deriv
1084
		    (rng--ipattern-child ipattern))))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1085
	  ((eq type 'after)
1086 1087 1088
	   (if (rng--ipattern-nullable
		(rng--ipattern-child ipattern))
	       (rng--ipattern-after ipattern)
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1089 1090 1091 1092 1093
	     rng-not-allowed-ipattern))
	  (t rng-not-allowed-ipattern))))

(defun rng-data-deriv (ipattern value)
  (or (rng-memo-map-get value
1094
			(rng--ipattern-memo-map-data-deriv ipattern))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1095 1096
      (and (rng-memo-map-get
	    (cons value (rng-namespace-context-get-no-trace))
1097
	    (rng--ipattern-memo-map-data-deriv ipattern))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1098 1099 1100
	   (rng-memo-map-get
	    (cons value (apply (car rng-dt-namespace-context-getter)
			       (cdr rng-dt-namespace-context-getter)))
1101
	    (rng--ipattern-memo-map-data-deriv ipattern)))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129
      (let* ((used-context (vector nil))
	     (rng-dt-namespace-context-getter
	      (cons 'rng-namespace-context-tracer
		    (cons used-context
			  rng-dt-namespace-context-getter)))
	     (deriv (rng-compute-data-deriv ipattern value)))
	(rng-ipattern-memo-data-deriv ipattern
				      value
				      (aref used-context 0)
				      deriv))))

(defun rng-namespace-context-tracer (used getter &rest args)
  (let ((context (apply getter args)))
    (aset used 0 context)
    context))

(defun rng-namespace-context-get-no-trace ()
  (let ((tem rng-dt-namespace-context-getter))
    (while (and tem (eq (car tem) 'rng-namespace-context-tracer))
      (setq tem (cddr tem)))
    (apply (car tem) (cdr tem))))

(defconst rng-memo-data-deriv-max-length 80
  "Don't memoize data-derivs for values longer than this.")

(defun rng-ipattern-memo-data-deriv (ipattern value context deriv)
  (or (memq ipattern rng-const-ipatterns)
      (> (length value) rng-memo-data-deriv-max-length)
1130 1131 1132 1133 1134
      (setf (rng--ipattern-memo-map-data-deriv ipattern)
            (rng-memo-map-add (if context (cons value context) value)
                              deriv
                              (rng--ipattern-memo-map-data-deriv ipattern)
                              t)))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1135 1136 1137
  deriv)

(defun rng-compute-data-deriv (ipattern value)
1138
  (let ((type (rng--ipattern-type ipattern)))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1139 1140
    (cond ((eq type 'text) ipattern)
	  ((eq type 'choice)
1141
	   (rng-transform-choice (lambda (p) (rng-data-deriv p value))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1142 1143 1144
				 ipattern))
	  ((eq type 'group)
	   (rng-transform-group-nullable
1145
	    (lambda (p) (rng-data-deriv p value))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1146 1147 1148 1149
	    (lambda (x y) (rng-intern-group (cons x y)))
	    ipattern))
	  ((eq type 'one-or-more)
	   (rng-intern-group (list (rng-data-deriv
1150
				    (rng--ipattern-child ipattern)
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1151 1152 1153
				    value)
				   (rng-intern-optional ipattern))))
	  ((eq type 'after)
1154 1155
	   (let ((child (rng--ipattern-child ipattern)))
	     (if (or (rng--ipattern-nullable
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1156
		      (rng-data-deriv child value))
1157
		     (and (rng--ipattern-nullable child)
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1158
			  (rng-blank-p value)))
1159
		 (rng--ipattern-after ipattern)
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1160 1161
	       rng-not-allowed-ipattern)))
	  ((eq type 'data)
1162
	   (if (rng-dt-make-value (rng--ipattern-datatype ipattern)
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1163 1164 1165 1166
				  value)
	       rng-empty-ipattern
	     rng-not-allowed-ipattern))
	  ((eq type 'data-except)
1167
	   (if (and (rng-dt-make-value (rng--ipattern-datatype ipattern)
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1168
				       value)
1169
		    (not (rng--ipattern-nullable
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1170
			  (rng-data-deriv
1171
			   (rng--ipattern-child ipattern)
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1172 1173 1174 1175
			   value))))
	       rng-empty-ipattern
	     rng-not-allowed-ipattern))
	  ((eq type 'value)
1176
	   (if (equal (rng-dt-make-value (rng--ipattern-datatype ipattern)
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1177
					 value)
1178
		      (rng--ipattern-value-object ipattern))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1179 1180 1181 1182
	       rng-empty-ipattern
	     rng-not-allowed-ipattern))
	  ((eq type 'list)
	   (let ((tokens (split-string value))
1183
		 (state (rng--ipattern-child ipattern)))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1184 1185 1186 1187
	     (while (and tokens
			 (not (eq state rng-not-allowed-ipattern)))
	       (setq state (rng-data-deriv state (car tokens)))
	       (setq tokens (cdr tokens)))
1188
	     (if (rng--ipattern-nullable state)
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1189 1190 1191 1192 1193 1194 1195
		 rng-empty-ipattern
	       rng-not-allowed-ipattern)))
	  ;; don't think interleave can occur
	  ;; since we do text-only-deriv first
	  (t rng-not-allowed-ipattern))))

(defun rng-transform-multi (f ipattern interner)
1196
  (let* ((members (rng--ipattern-child ipattern))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211
	 (transformed (mapcar f members)))
    (if (rng-members-eq members transformed)
	ipattern
      (funcall interner transformed))))

(defun rng-transform-choice (f ipattern)
  (rng-transform-multi f ipattern 'rng-intern-choice))

(defun rng-transform-group (f ipattern)
  (rng-transform-multi f ipattern 'rng-intern-group))

(defun rng-transform-interleave (f ipattern)
  (rng-transform-multi f ipattern 'rng-intern-interleave))

(defun rng-transform-one-or-more (f ipattern)
1212
  (let* ((child (rng--ipattern-child ipattern))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1213 1214 1215 1216 1217 1218
	 (transformed (funcall f child)))
    (if (eq child transformed)
	ipattern
      (rng-intern-one-or-more transformed))))

(defun rng-transform-after-child (f ipattern)
1219
  (let* ((child (rng--ipattern-child ipattern))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1220 1221 1222 1223
	 (transformed (funcall f child)))
    (if (eq child transformed)
	ipattern
      (rng-intern-after transformed
1224
			(rng--ipattern-after ipattern)))))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1225 1226

(defun rng-transform-interleave-single (f subster ipattern)
1227
  (let ((children (rng--ipattern-child ipattern))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1228 1229 1230 1231 1232 1233 1234 1235 1236 1237
	found)
    (while (and children (not found))
      (let* ((child (car children))
	     (transformed (funcall f child)))
	(if (eq transformed rng-not-allowed-ipattern)
	    (setq children (cdr children))
	  (setq found
		(funcall subster
			 transformed
			 child
1238
			 (rng--ipattern-child ipattern))))))
Mark A. Hershberger's avatar
Mark A. Hershberger committed
1239 1240 1241 </