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