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