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