basis/regexp/classes/classes.factor

   1 ! Copyright (C) 2008, 2009 Doug Coleman, Daniel Ehrenberg.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: accessors kernel math math.order words combinators locals
   4 ascii unicode.categories combinators.short-circuit sequences
   5 fry macros arrays assocs sets classes ;
   6 IN: regexp.classes
   7
   8 SINGLETONS: any-char any-char-no-nl
   9 letter-class LETTER-class Letter-class digit-class
  10 alpha-class non-newline-blank-class
  11 ascii-class punctuation-class java-printable-class blank-class
  12 control-character-class hex-digit-class java-blank-class c-identifier-class
  13 unmatchable-class terminator-class word-boundary-class ;
  14
  15 SINGLETONS: beginning-of-input ^ end-of-input $ end-of-file ;
  16
  17 TUPLE: range from to ;
  18 C: <range> range
  19
  20 GENERIC: class-member? ( obj class -- ? )
  21
  22 M: t class-member? ( obj class -- ? ) 2drop t ;
  23
  24 M: integer class-member? ( obj class -- ? ) = ;
  25
  26 M: range class-member? ( obj class -- ? )
  27     [ from>> ] [ to>> ] bi between? ;
  28
  29 M: any-char class-member? ( obj class -- ? )
  30     2drop t ;
  31
  32 M: any-char-no-nl class-member? ( obj class -- ? )
  33     drop CHAR: \n = not ;
  34
  35 M: letter-class class-member? ( obj class -- ? )
  36     drop letter? ;
  37
  38 M: LETTER-class class-member? ( obj class -- ? )
  39     drop LETTER? ;
  40
  41 M: Letter-class class-member? ( obj class -- ? )
  42     drop Letter? ;
  43
  44 M: ascii-class class-member? ( obj class -- ? )
  45     drop ascii? ;
  46
  47 M: digit-class class-member? ( obj class -- ? )
  48     drop digit? ;
  49
  50 : c-identifier-char? ( ch -- ? )
  51     { [ alpha? ] [ CHAR: _ = ] } 1|| ;
  52
  53 M: c-identifier-class class-member? ( obj class -- ? )
  54     drop c-identifier-char? ;
  55
  56 M: alpha-class class-member? ( obj class -- ? )
  57     drop alpha? ;
  58
  59 : punct? ( ch -- ? )
  60     "!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~" member? ;
  61
  62 M: punctuation-class class-member? ( obj class -- ? )
  63     drop punct? ;
  64
  65 : java-printable? ( ch -- ? )
  66     { [ alpha? ] [ punct? ] } 1|| ;
  67
  68 M: java-printable-class class-member? ( obj class -- ? )
  69     drop java-printable? ;
  70
  71 M: non-newline-blank-class class-member? ( obj class -- ? )
  72     drop { [ blank? ] [ CHAR: \n = not ] } 1&& ;
  73
  74 M: control-character-class class-member? ( obj class -- ? )
  75     drop control? ;
  76
  77 : hex-digit? ( ch -- ? )
  78     {
  79         [ CHAR: A CHAR: F between? ]
  80         [ CHAR: a CHAR: f between? ]
  81         [ CHAR: 0 CHAR: 9 between? ]
  82     } 1|| ;
  83
  84 M: hex-digit-class class-member? ( obj class -- ? )
  85     drop hex-digit? ;
  86
  87 : java-blank? ( ch -- ? )
  88     {
  89         CHAR: \s CHAR: \t CHAR: \n
  90         HEX: b HEX: 7 CHAR: \r
  91     } member? ;
  92
  93 M: java-blank-class class-member? ( obj class -- ? )
  94     drop java-blank? ;
  95
  96 M: unmatchable-class class-member? ( obj class -- ? )
  97     2drop f ;
  98
  99 M: terminator-class class-member? ( obj class -- ? )
 100     drop "\r\n\u000085\u002029\u002028" member? ;
 101
 102 M: ^ class-member? ( obj class -- ? )
 103     2drop f ;
 104
 105 M: $ class-member? ( obj class -- ? )
 106     2drop f ;
 107
 108 M: f class-member? 2drop f ;
 109
 110 TUPLE: primitive-class class ;
 111 C: <primitive-class> primitive-class
 112
 113 TUPLE: or-class seq ;
 114
 115 TUPLE: not-class class ;
 116
 117 TUPLE: and-class seq ;
 118
 119 GENERIC: combine-and ( class1 class2 -- combined ? )
 120
 121 : replace-if-= ( object object -- object ? )
 122     over = ;
 123
 124 M: object combine-and replace-if-= ;
 125
 126 M: t combine-and
 127     drop t ;
 128
 129 M: f combine-and
 130     nip t ;
 131
 132 M: not-class combine-and
 133     class>> 2dup = [ 2drop f t ] [
 134         dup integer? [
 135             2dup swap class-member?
 136             [ 2drop f f ]
 137             [ drop t ] if
 138         ] [ 2drop f f ] if
 139     ] if ;
 140
 141 M: integer combine-and
 142     swap 2dup class-member? [ drop t ] [ 2drop f t ] if ;
 143
 144 GENERIC: combine-or ( class1 class2 -- combined ? )
 145
 146 M: object combine-or replace-if-= ;
 147
 148 M: t combine-or
 149     nip t ;
 150
 151 M: f combine-or
 152     drop t ;
 153
 154 M: not-class combine-or
 155     class>> = [ t t ] [ f f ] if ;
 156
 157 M: integer combine-or
 158     2dup swap class-member? [ drop t ] [ 2drop f f ] if ;
 159
 160 : flatten ( seq class -- newseq )
 161     '[ dup _ instance? [ seq>> ] [ 1array ] if ] map concat ; inline
 162
 163 : try-combine ( elt1 elt2 quot -- combined/f ? )
 164     3dup call [ [ 3drop ] dip t ] [ drop swapd call ] if ; inline
 165
 166 :: prefix-combining ( seq elt quot: ( elt1 elt2 -- combined/f ? ) -- newseq )
 167     f :> combined!
 168     seq [ elt quot try-combine swap combined! ] find drop
 169     [ seq remove-nth combined prefix ]
 170     [ seq elt prefix ] if* ; inline
 171
 172 :: combine ( seq quot: ( elt1 elt2 -- combined/f ? ) empty class -- newseq )
 173     seq class flatten
 174     { } [ quot prefix-combining ] reduce
 175     dup length {
 176         { 0 [ drop empty ] }
 177         { 1 [ first ] }
 178         [ drop class new swap >>seq ]
 179     } case ; inline
 180
 181 : <and-class> ( seq -- class )
 182     [ combine-and ] t and-class combine ;
 183
 184 M: and-class class-member?
 185     seq>> [ class-member? ] with all? ;
 186
 187 : <or-class> ( seq -- class )
 188     [ combine-or ] f or-class combine ;
 189
 190 M: or-class class-member?
 191     seq>> [ class-member? ] with any? ;
 192
 193 GENERIC: <not-class> ( class -- inverse )
 194
 195 M: object <not-class>
 196     not-class boa ;
 197
 198 M: not-class <not-class>
 199     class>> ;
 200
 201 M: and-class <not-class>
 202     seq>> [ <not-class> ] map <or-class> ;
 203
 204 M: or-class <not-class>
 205     seq>> [ <not-class> ] map <and-class> ;
 206
 207 M: t <not-class> drop f ;
 208 M: f <not-class> drop t ;
 209
 210 M: not-class class-member?
 211     class>> class-member? not ;
 212
 213 M: primitive-class class-member?
 214     class>> class-member? ;
 215
 216 UNION: class primitive-class not-class or-class and-class range ;
 217
 218 TUPLE: condition question yes no ;
 219 C: <condition> condition
 220
 221 GENERIC# replace-question 2 ( class from to -- new-class )
 222
 223 M:: object replace-question ( class from to -- new-class )
 224     class from = to class ? ;
 225
 226 : replace-compound ( class from to -- seq )
 227     [ seq>> ] 2dip '[ _ _ replace-question ] map ;
 228
 229 M: and-class replace-question
 230     replace-compound <and-class> ;
 231
 232 M: or-class replace-question
 233     replace-compound <or-class> ;
 234
 235 M: not-class replace-question
 236     [ class>> ] 2dip replace-question <not-class> ;
 237
 238 : answer ( table question answer -- new-table )
 239     '[ _ _ replace-question ] assoc-map
 240     [ nip ] assoc-filter ;
 241
 242 : answers ( table questions answer -- new-table )
 243     '[ _ answer ] each ;
 244
 245 DEFER: make-condition
 246
 247 : (make-condition) ( table questions question -- condition )
 248     [ 2nip ]
 249     [ swap [ t answer ] dip make-condition ]
 250     [ swap [ f answer ] dip make-condition ] 3tri
 251     2dup = [ 2nip ] [ <condition> ] if ;
 252
 253 : make-condition ( table questions -- condition )
 254     [ keys ] [ unclip (make-condition) ] if-empty ;
 255
 256 GENERIC: class>questions ( class -- questions )
 257 : compound-questions ( class -- questions ) seq>> [ class>questions ] gather ;
 258 M: or-class class>questions compound-questions ;
 259 M: and-class class>questions compound-questions ;
 260 M: not-class class>questions class>> class>questions ;
 261 M: object class>questions 1array ;
 262
 263 : table>questions ( table -- questions )
 264     values [ class>questions ] gather >array t swap remove ;
 265
 266 : table>condition ( table -- condition )
 267     ! input table is state => class
 268     >alist dup table>questions make-condition ;
 269
 270 : condition-map ( condition quot: ( obj -- obj' ) -- new-condition )
 271     over condition? [
 272         [ [ question>> ] [ yes>> ] [ no>> ] tri ] dip
 273         '[ _ condition-map ] bi@ <condition>
 274     ] [ call ] if ; inline recursive
 275
 276 : condition-states ( condition -- states )
 277     dup condition? [
 278         [ yes>> ] [ no>> ] bi
 279         [ condition-states ] bi@ append prune
 280     ] [ 1array ] if ;
 281
 282 : condition-at ( condition assoc -- new-condition )
 283     '[ _ at ] condition-map ;