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