basis/regexp/classes/classes.factor

   1 ! Copyright (C) 2008, 2009 Doug Coleman, Daniel Ehrenberg.
   2 ! See https://factorcode.org/license.txt for BSD license.
   3 USING: accessors arrays assocs classes combinators
   4 combinators.short-circuit combinators.smart hex-strings kernel
   5 math math.order sequences sets unicode unicode.data ;
   6 FROM: ascii => ascii? ;
   7 IN: regexp.classes
   8
   9 SINGLETONS: dot 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 ^crlf end-of-input $crlf end-of-file
  16 ^unix $unix word-break ;
  17
  18 TUPLE: range-class { from read-only } { to read-only } ;
  19 C: <range-class> range-class
  20
  21 TUPLE: primitive-class { class read-only } ;
  22 C: <primitive-class> primitive-class
  23
  24 TUPLE: category-class { category read-only } ;
  25 C: <category-class> category-class
  26
  27 TUPLE: category-range-class { category read-only } ;
  28 C: <category-range-class> category-range-class
  29
  30 TUPLE: script-class { script read-only } ;
  31 C: <script-class> script-class
  32
  33 GENERIC: class-member? ( obj class -- ? )
  34
  35 M: t class-member? 2drop t ; inline
  36
  37 M: integer class-member? = ; inline
  38
  39 M: range-class class-member?
  40     [ from>> ] [ to>> ] bi between? ; inline
  41
  42 M: letter-class class-member?
  43     drop letter? ; inline
  44
  45 M: LETTER-class class-member?
  46     drop LETTER? ; inline
  47
  48 M: Letter-class class-member?
  49     drop Letter? ; inline
  50
  51 M: ascii-class class-member?
  52     drop ascii? ; inline
  53
  54 M: digit-class class-member?
  55     drop digit? ; inline
  56
  57 : c-identifier-char? ( ch -- ? )
  58     { [ alpha? ] [ CHAR: _ = ] } 1|| ;
  59
  60 M: c-identifier-class class-member?
  61     drop c-identifier-char? ; inline
  62
  63 M: alpha-class class-member?
  64     drop alpha? ; inline
  65
  66 : punct? ( ch -- ? )
  67     "!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~" member? ;
  68
  69 M: punctuation-class class-member?
  70     drop punct? ; inline
  71
  72 : java-printable? ( ch -- ? )
  73     { [ alpha? ] [ punct? ] } 1|| ;
  74
  75 M: java-printable-class class-member?
  76     drop java-printable? ; inline
  77
  78 M: non-newline-blank-class class-member?
  79     drop { [ blank? ] [ CHAR: \n = not ] } 1&& ; inline
  80
  81 M: control-character-class class-member?
  82     drop control? ; inline
  83
  84 M: hex-digit-class class-member?
  85     drop hex-digit? ; inline
  86
  87 : java-blank? ( ch -- ? )
  88     {
  89         CHAR: \s CHAR: \t CHAR: \n
  90         CHAR: \v CHAR: \a CHAR: \r
  91     } member? ;
  92
  93 M: java-blank-class class-member?
  94     drop java-blank? ; inline
  95
  96 M: unmatchable-class class-member?
  97     2drop f ; inline
  98
  99 M: terminator-class class-member?
 100     drop "\r\n\u000085\u002029\u002028" member? ; inline
 101
 102 M: f class-member? 2drop f ; inline
 103
 104 M: script-class class-member?
 105     [ script-of ] [ script>> ] bi* = ; inline
 106
 107 M: category-class class-member?
 108     [ category ] [ category>> ] bi* = ; inline
 109
 110 M: category-range-class class-member? inline
 111     [ category first ] [ category>> ] bi* = ; inline
 112
 113 TUPLE: not-class { class read-only } ;
 114
 115 PREDICATE: not-integer < not-class class>> integer? ;
 116
 117 UNION: simple-class
 118     primitive-class range-class dot ;
 119 PREDICATE: not-simple < not-class class>> simple-class? ;
 120
 121 M: not-class class-member?
 122     class>> class-member? not ; inline
 123
 124 TUPLE: or-class { seq read-only } ;
 125
 126 M: or-class class-member?
 127     seq>> [ class-member? ] with any? ; inline
 128
 129 TUPLE: and-class { seq read-only } ;
 130
 131 M: and-class class-member?
 132     seq>> [ class-member? ] with all? ; inline
 133
 134 DEFER: (substitute)
 135
 136 : flatten ( seq class -- newseq )
 137     '[ dup _ instance? [ seq>> ] [ 1array ] if ] map concat ; inline
 138
 139 :: sequence>instance ( seq empty class -- instance )
 140     seq length {
 141         { 0 [ empty ] }
 142         { 1 [ seq first ] }
 143         [ drop seq { } like class boa ]
 144     } case ; inline
 145
 146 TUPLE: class-partition integers not-integers simples not-simples and or other ;
 147
 148 : partition-classes ( seq -- class-partition )
 149     members
 150     [ integer? ] partition
 151     [ not-integer? ] partition
 152     [ simple-class? ] partition
 153     [ not-simple? ] partition
 154     [ and-class? ] partition
 155     [ or-class? ] partition
 156     class-partition boa ;
 157
 158 : class-partition>sequence ( class-partition -- seq )
 159     {
 160         [ integers>> ]
 161         [ not-integers>> ]
 162         [ simples>> ]
 163         [ not-simples>> ]
 164         [ and>> ]
 165         [ or>> ]
 166         [ other>> ]
 167     } cleave>array concat ;
 168
 169 : repartition ( partition -- partition' )
 170     ! This could be made more efficient; only and and or are effected
 171     class-partition>sequence partition-classes ;
 172
 173 : filter-not-integers ( partition -- partition' )
 174     dup
 175     [ simples>> ] [ not-simples>> ] [ or>> ] tri
 176     3append and-class boa
 177     '[ [ class>> _ class-member? ] filter ] change-not-integers ;
 178
 179 : answer-ors ( partition -- partition' )
 180     dup [ not-integers>> ] [ not-simples>> ] [ simples>> ] tri 3append
 181     '[ [ _ [ t (substitute) ] each ] map ] change-or ;
 182
 183 : contradiction? ( partition -- ? )
 184     {
 185         [ [ simples>> ] [ not-simples>> ] bi intersects? ]
 186         [ other>> f swap member? ]
 187     } 1|| ;
 188
 189 : make-and-class ( partition -- and-class )
 190     answer-ors repartition
 191     [ t swap remove ] change-other
 192     dup contradiction?
 193     [ drop f ]
 194     [ filter-not-integers class-partition>sequence members t and-class sequence>instance ] if ;
 195
 196 : <and-class> ( seq -- class )
 197     dup and-class flatten partition-classes
 198     dup integers>> length {
 199         { 0 [ nip make-and-class ] }
 200         { 1 [ integers>> first [ '[ _ swap class-member? ] all? ] keep and ] }
 201         [ 3drop f ]
 202     } case ;
 203
 204 : filter-integers ( partition -- partition' )
 205     dup
 206     [ simples>> ] [ not-simples>> ] [ and>> ] tri
 207     3append or-class boa
 208     '[ [ _ class-member? ] reject ] change-integers ;
 209
 210 : answer-ands ( partition -- partition' )
 211     dup [ integers>> ] [ not-simples>> ] [ simples>> ] tri 3append
 212     '[ [ _ [ f (substitute) ] each ] map ] change-and ;
 213
 214 : tautology? ( partition -- ? )
 215     {
 216         [ [ simples>> ] [ not-simples>> ] bi intersects? ]
 217         [ other>> t swap member? ]
 218     } 1|| ;
 219
 220 : make-or-class ( partition -- and-class )
 221     answer-ands repartition
 222     [ f swap remove ] change-other
 223     dup tautology?
 224     [ drop t ]
 225     [ filter-integers class-partition>sequence members f or-class sequence>instance ] if ;
 226
 227 : <or-class> ( seq -- class )
 228     dup or-class flatten partition-classes
 229     dup not-integers>> length {
 230         { 0 [ nip make-or-class ] }
 231         { 1 [
 232             not-integers>> first
 233             [ class>> '[ _ swap class-member? ] any? ] keep or
 234         ] }
 235         [ 3drop t ]
 236     } case ;
 237
 238 GENERIC: <not-class> ( class -- inverse )
 239
 240 M: object <not-class>
 241     not-class boa ;
 242
 243 M: not-class <not-class>
 244     class>> ;
 245
 246 M: and-class <not-class>
 247     seq>> [ <not-class> ] map <or-class> ;
 248
 249 M: or-class <not-class>
 250     seq>> [ <not-class> ] map <and-class> ;
 251
 252 M: t <not-class> drop f ;
 253 M: f <not-class> drop t ;
 254
 255 : <minus-class> ( a b -- a-b )
 256     <not-class> 2array <and-class> ;
 257
 258 : <sym-diff-class> ( a b -- a~b )
 259     2array [ <or-class> ] [ <and-class> ] bi <minus-class> ;
 260
 261 M: primitive-class class-member?
 262     class>> class-member? ; inline
 263
 264 TUPLE: condition question yes no ;
 265 C: <condition> condition
 266
 267 GENERIC#: answer 2 ( class from to -- new-class )
 268
 269 M:: object answer ( class from to -- new-class )
 270     class from = to class ? ;
 271
 272 : replace-compound ( class from to -- seq )
 273     [ seq>> ] 2dip '[ _ _ answer ] map ;
 274
 275 M: and-class answer
 276     replace-compound <and-class> ;
 277
 278 M: or-class answer
 279     replace-compound <or-class> ;
 280
 281 M: not-class answer
 282     [ class>> ] 2dip answer <not-class> ;
 283
 284 GENERIC#: (substitute) 1 ( class from to -- new-class )
 285 M: object (substitute) answer ;
 286 M: not-class (substitute) [ <not-class> ] bi@ answer ;
 287
 288 : assoc-answer ( table question answer -- new-table )
 289     '[ _ _ (substitute) ] assoc-map sift-values ;
 290
 291 : assoc-answers ( table questions answer -- new-table )
 292     '[ _ assoc-answer ] each ;
 293
 294 DEFER: make-condition
 295
 296 : (make-condition) ( table questions question -- condition )
 297     [ 2nip ]
 298     [ swap [ t assoc-answer ] dip make-condition ]
 299     [ swap [ f assoc-answer ] dip make-condition ] 3tri
 300     2dup = [ 2nip ] [ <condition> ] if ;
 301
 302 : make-condition ( table questions -- condition )
 303     [ keys ] [ unclip (make-condition) ] if-empty ;
 304
 305 GENERIC: class>questions ( class -- questions )
 306 : compound-questions ( class -- questions ) seq>> [ class>questions ] gather ;
 307 M: or-class class>questions compound-questions ;
 308 M: and-class class>questions compound-questions ;
 309 M: not-class class>questions class>> class>questions ;
 310 M: object class>questions 1array ;
 311
 312 : table>questions ( table -- questions )
 313     values [ class>questions ] gather >array t swap remove ;
 314
 315 : table>condition ( table -- condition )
 316     ! input table is state => class
 317     >alist dup table>questions make-condition ;
 318
 319 : condition-map ( condition quot: ( obj -- obj' ) -- new-condition )
 320     over condition? [
 321         [ [ question>> ] [ yes>> ] [ no>> ] tri ] dip
 322         '[ _ condition-map ] bi@ <condition>
 323     ] [ call ] if ; inline recursive
 324
 325 : condition-states ( condition -- states )
 326     dup condition? [
 327         [ yes>> ] [ no>> ] bi
 328         [ condition-states ] bi@ union
 329     ] [ 1array ] if ;
 330
 331 : condition-at ( condition assoc -- new-condition )
 332     '[ _ at ] condition-map ;