basis/regexp/regexp.factor

   1 ! Copyright (C) 2008, 2009 Doug Coleman, Daniel Ehrenberg.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: accessors combinators kernel math sequences strings sets
   4 assocs prettyprint.backend prettyprint.custom make lexer
   5 namespaces parser arrays fry locals regexp.parser splitting
   6 sorting regexp.ast regexp.negation regexp.compiler words
   7 call call.private math.ranges ;
   8 IN: regexp
   9
  10 TUPLE: regexp
  11     { raw read-only }
  12     { parse-tree read-only }
  13     { options read-only }
  14     dfa next-match ;
  15
  16 TUPLE: reverse-regexp < regexp ;
  17
  18 <PRIVATE
  19
  20 : maybe-negated ( lookaround quot -- regexp-quot )
  21     '[ term>> @ ] [ positive?>> [ ] [ not ] ? ] bi compose ; inline
  22
  23 M: lookahead question>quot ! Returns ( index string -- ? )
  24     [ ast>dfa dfa>shortest-word '[ f _ execute ] ] maybe-negated ;
  25
  26 : <reversed-option> ( ast -- reversed )
  27     "r" string>options <with-options> ;
  28
  29 M: lookbehind question>quot ! Returns ( index string -- ? )
  30     [
  31         <reversed-option>
  32         ast>dfa dfa>reverse-shortest-word
  33         '[ [ 1- ] dip f _ execute ]
  34     ] maybe-negated ;
  35
  36 <PRIVATE
  37
  38 : check-string ( string -- string )
  39     ! Make this configurable
  40     dup string? [ "String required" throw ] unless ;
  41
  42 : match-index-from ( i string regexp -- index/f )
  43     ! This word is unsafe. It assumes that i is a fixnum
  44     ! and that string is a string.
  45     dup dfa>> execute( index string regexp -- i/f ) ;
  46
  47 GENERIC: end/start ( string regexp -- end start )
  48 M: regexp end/start drop length 0 ;
  49 M: reverse-regexp end/start drop length 1- -1 swap ;
  50
  51 PRIVATE>
  52
  53 : matches? ( string regexp -- ? )
  54     [ end/start ] 2keep
  55     [ check-string ] dip
  56     match-index-from
  57     [ swap = ] [ drop f ] if* ;
  58
  59 <PRIVATE
  60
  61 : match-slice ( i string quot -- slice/f )
  62     [ 2dup ] dip call
  63     [ swap <slice> ] [ 2drop f ] if* ; inline
  64
  65 : match-from ( i string quot -- slice/f )
  66     [ [ length [a,b) ] keep ] dip
  67     '[ _ _ match-slice ] map-find drop ; inline
  68
  69 : next-match ( i string quot -- i match/f )
  70     match-from [ dup [ to>> ] when ] keep ; inline
  71
  72 : do-next-match ( i string regexp -- i match/f )
  73     dup next-match>> execute( i string regexp -- i match/f ) ;
  74
  75 PRIVATE>
  76
  77 : all-matches ( string regexp -- seq )
  78     [ check-string ] dip
  79     [ 0 [ dup ] ] 2dip '[ _ _ do-next-match ] produce
  80     nip but-last ;
  81
  82 : count-matches ( string regexp -- n )
  83     all-matches length ;
  84
  85 <PRIVATE
  86
  87 :: split-slices ( string slices -- new-slices )
  88     slices [ to>> ] map 0 prefix
  89     slices [ from>> ] map string length suffix
  90     [ string <slice> ] 2map ;
  91
  92 : match-head ( str regexp -- slice/f )
  93     [
  94         [ 0 ] [ check-string ] [ dup dfa>> '[ _ _ execute ] ] tri*
  95         match-from
  96     ] call( str regexp -- slice/f ) ;
  97
  98 PRIVATE>
  99
 100 : re-split1 ( string regexp -- before after/f )
 101     dupd match-head [ 1array split-slices first2 ] [ f ] if* ;
 102
 103 : re-split ( string regexp -- seq )
 104     dupd all-matches split-slices ;
 105
 106 : re-replace ( string regexp replacement -- result )
 107     [ re-split ] dip join ;
 108
 109 <PRIVATE
 110
 111 : get-ast ( regexp -- ast )
 112     [ parse-tree>> ] [ options>> ] bi <with-options> ;
 113
 114 GENERIC: compile-regexp ( regex -- regexp )
 115
 116 : regexp-initial-word ( i string regexp -- i/f )
 117     compile-regexp match-index-from ;
 118
 119 : do-compile-regexp ( regexp -- regexp )
 120     dup '[
 121         dup \ regexp-initial-word =
 122         [ drop _ get-ast ast>dfa dfa>word ] when
 123     ] change-dfa ;
 124
 125 M: regexp compile-regexp ( regexp -- regexp )
 126     do-compile-regexp ;
 127
 128 M: reverse-regexp compile-regexp ( regexp -- regexp )
 129     t backwards? [ do-compile-regexp ] with-variable ;
 130
 131 GENERIC: compile-next-match ( regexp -- regexp )
 132
 133 : next-initial-word ( i string regexp -- i slice/f )
 134     compile-next-match do-next-match ;
 135
 136 M: regexp compile-next-match ( regexp -- regexp )
 137     dup '[
 138         dup \ next-initial-word = [
 139             drop _ compile-regexp dfa>>
 140             '[ _ '[ _ _ execute ] next-match ]
 141             (( i string -- i match/f )) simple-define-temp
 142         ] when
 143     ] change-next-match ;
 144
 145 ! Write M: reverse-regexp compile-next-match
 146
 147 PRIVATE>
 148
 149 : new-regexp ( string ast options class -- regexp )
 150     [ \ regexp-initial-word \ next-initial-word ] dip boa ; inline
 151
 152 : make-regexp ( string ast -- regexp )
 153     f f <options> regexp new-regexp ;
 154
 155 : <optioned-regexp> ( string options -- regexp )
 156     [ dup parse-regexp ] [ string>options ] bi*
 157     dup on>> reversed-regexp swap member?
 158     [ reverse-regexp new-regexp ]
 159     [ regexp new-regexp ] if ;
 160
 161 : <regexp> ( string -- regexp ) "" <optioned-regexp> ;
 162
 163 <PRIVATE
 164
 165 ! The following two should do some caching
 166
 167 : find-regexp-syntax ( string -- prefix suffix )
 168     {
 169         { "R/ "  "/"  }
 170         { "R! "  "!"  }
 171         { "R\" " "\"" }
 172         { "R# "  "#"  }
 173         { "R' "  "'"  }
 174         { "R( "  ")"  }
 175         { "R@ "  "@"  }
 176         { "R[ "  "]"  }
 177         { "R` "  "`"  }
 178         { "R{ "  "}"  }
 179         { "R| "  "|"  }
 180     } swap [ subseq? not nip ] curry assoc-find drop ;
 181
 182 : take-until ( end lexer -- string )
 183     dup skip-blank [
 184         [ index-from ] 2keep
 185         [ swapd subseq ]
 186         [ 2drop 1+ ] 3bi
 187     ] change-lexer-column ;
 188
 189 : parse-noblank-token ( lexer -- str/f )
 190     dup still-parsing-line? [ (parse-token) ] [ drop f ] if ;
 191
 192 : parsing-regexp ( accum end -- accum )
 193     lexer get [ take-until ] [ parse-noblank-token ] bi
 194     <optioned-regexp> compile-next-match parsed ;
 195
 196 PRIVATE>
 197
 198 : R! CHAR: ! parsing-regexp ; parsing
 199 : R" CHAR: " parsing-regexp ; parsing
 200 : R# CHAR: # parsing-regexp ; parsing
 201 : R' CHAR: ' parsing-regexp ; parsing
 202 : R( CHAR: ) parsing-regexp ; parsing
 203 : R/ CHAR: / parsing-regexp ; parsing
 204 : R@ CHAR: @ parsing-regexp ; parsing
 205 : R[ CHAR: ] parsing-regexp ; parsing
 206 : R` CHAR: ` parsing-regexp ; parsing
 207 : R{ CHAR: } parsing-regexp ; parsing
 208 : R| CHAR: | parsing-regexp ; parsing
 209
 210 M: regexp pprint*
 211     [
 212         [
 213             [ raw>> dup find-regexp-syntax swap % swap % % ]
 214             [ options>> options>string % ] bi
 215         ] "" make
 216     ] keep present-text ;
 217