basis/regexp/regexp.factor

   1 ! Copyright (C) 2008, 2009 Doug Coleman, Daniel Ehrenberg.
   2 ! See https://factorcode.org/license.txt for BSD license.
   3 USING: accessors arrays classes compiler.units kernel
   4 kernel.private lexer make math ranges namespaces quotations
   5 regexp.ast regexp.compiler regexp.negation regexp.parser
   6 sequences sequences.private splitting strings vocabs.loader
   7 words ;
   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 M: lookahead question>quot
  21     ! Returns ( index string -- ? )
  22     term>> ast>dfa dfa>shortest-word 1quotation [ f ] prepose ;
  23
  24 : <reversed-option> ( ast -- reversed )
  25     "r" string>options <with-options> ;
  26
  27 M: lookbehind question>quot
  28     ! Returns ( index string -- ? )
  29     term>> <reversed-option>
  30     ast>dfa dfa>reverse-shortest-word
  31     1quotation [ [ 1 - ] dip f ] prepose ;
  32
  33 : match-index-from ( i string regexp -- index/f )
  34     ! This word is unsafe. It assumes that i is a fixnum
  35     ! and that string is a string.
  36     dup dfa>> execute( index string regexp -- i/f ) ; inline
  37
  38 GENERIC: end/start ( string regexp -- end start )
  39 M: regexp end/start drop length 0 ;
  40 M: reverse-regexp end/start drop length 1 - -1 swap ;
  41
  42 PRIVATE>
  43
  44 : matches? ( string regexp -- ? )
  45     [ string check-instance ] dip
  46     [ end/start ] 2keep
  47     match-index-from
  48     [ = ] [ drop f ] if* ;
  49
  50 <PRIVATE
  51
  52 : search-range ( i string reverse? -- seq )
  53     [ drop -1 ] [ length ] if [a..b] ; inline
  54
  55 :: (next-match) ( i string regexp quot: ( i string regexp -- j ) reverse? -- start end ? )
  56     i string regexp quot call dup
  57     [| j | reverse? [ j i ] [ i j ] if string ] [ drop f f f ] if ; inline
  58
  59 :: next-match ( i string regexp quot: ( i string regexp -- j ) reverse? -- start end ? )
  60     f f f
  61     i string reverse? search-range
  62     [ 3nip string regexp quot reverse? (next-match) dup ] find 2drop ; inline
  63
  64 : do-next-match ( i string regexp -- start end ? )
  65     dup next-match>>
  66     execute( i string regexp -- start end ? ) ; inline
  67
  68 :: (each-match-forward) ( ... i string regexp quot: ( ... start end string -- ... ) -- ... )
  69     i string length <= [
  70         i string regexp do-next-match [| start end |
  71             start end string quot call
  72             start end eq? [ end 1 +  ] [ end ] if
  73             string regexp quot (each-match-forward)
  74         ] [ 2drop ] if
  75     ] when ; inline recursive
  76
  77 :: (each-match-backward) ( ... i string regexp quot: ( ... start end string -- ... ) -- ... )
  78     i -1 >= [
  79         i string regexp do-next-match [| start end |
  80             start 1 + end 1 + string quot call
  81             start end eq? [ start 1 - ] [ start ] if
  82             string regexp quot (each-match-backward)
  83         ] [ 2drop ] if
  84     ] when ; inline recursive
  85
  86 : (each-match) ( ... i string regexp quot: ( ... start end string -- ... ) -- ... )
  87     over reverse-regexp? [ (each-match-backward) ] [ (each-match-forward) ] if ; inline
  88
  89 GENERIC: match-iterator-start ( string regexp -- start )
  90 M: regexp match-iterator-start 2drop 0 ;
  91 M: reverse-regexp match-iterator-start drop length ;
  92
  93 : prepare-match-iterator ( string regexp -- i string regexp )
  94     [ string check-instance ] dip [ match-iterator-start ] 2keep ; inline
  95
  96 PRIVATE>
  97
  98 : each-match ( ... string regexp quot: ( ... start end string -- ... ) -- ... )
  99     [ prepare-match-iterator ] dip (each-match) ; inline
 100
 101 : map-matches ( ... string regexp quot: ( ... start end string -- ... obj ) -- ... seq )
 102     collector [ each-match ] dip >array ; inline
 103
 104 : all-matching-slices ( string regexp -- seq )
 105     [ <slice-unsafe> ] map-matches ;
 106
 107 : all-matching-subseqs ( string regexp -- seq )
 108     [ subseq-unsafe ] map-matches ;
 109
 110 : count-matches ( string regexp -- n )
 111     [ 0 ] 2dip [ 3drop 1 + ] each-match ;
 112
 113 <PRIVATE
 114
 115 : (re-split) ( string regexp quot -- pieces )
 116     [ 0 ] 3dip [
 117         '[ swap _ dip swap ] collector [ each-match ] dip swap
 118     ] 3keep nip [ [ length ] keep ] dip call suffix! >array ; inline
 119
 120 PRIVATE>
 121
 122 : first-match ( string regexp -- slice/f )
 123     [ prepare-match-iterator do-next-match ] 2keep swap '[
 124         _ reverse-regexp? [ [ 1 + ] bi@ ] when _ <slice-unsafe>
 125     ] [ 2drop f ] if ;
 126
 127 : re-contains? ( string regexp -- ? )
 128     prepare-match-iterator do-next-match 2nip >boolean ;
 129
 130 : re-split ( string regexp -- seq )
 131     [ <slice-unsafe> ] (re-split) ;
 132
 133 : re-replace ( string regexp replacement -- result )
 134     [ [ subseq-unsafe ] (re-split) ] dip join ;
 135
 136 :: re-replace-with ( string regexp quot: ( slice -- replacement ) -- result )
 137     [
 138         0 string regexp [
 139             drop [ [ string <slice-unsafe> , ] keep ] dip
 140             [ string <slice-unsafe> quot call( x -- x ) , ] keep
 141         ] each-match string [ length ] [ <slice-unsafe> ] bi ,
 142     ] { } make concat ;
 143
 144 <PRIVATE
 145
 146 : get-ast ( regexp -- ast )
 147     [ parse-tree>> ] [ options>> ] bi <with-options> ;
 148
 149 GENERIC: compile-regexp ( regex -- regexp )
 150
 151 : regexp-initial-word ( i string regexp -- i/f )
 152     [ compile-regexp ] with-compilation-unit match-index-from ;
 153
 154 M: regexp compile-regexp
 155     dup '[
 156         dup \ regexp-initial-word =
 157         [ drop _ get-ast ast>dfa dfa>word ] when
 158     ] change-dfa ;
 159
 160 M: reverse-regexp compile-regexp
 161     t backwards? [ call-next-method ] with-variable ;
 162
 163 DEFER: compile-next-match
 164
 165 : next-initial-word ( i string regexp -- start end string )
 166     [ compile-next-match ] with-compilation-unit do-next-match ;
 167
 168 : compile-next-match ( regexp -- regexp )
 169     dup '[
 170         dup \ next-initial-word = [
 171             drop _ [ compile-regexp dfa>> def>> ] [ reverse-regexp? ] bi
 172             '[ { array-capacity string regexp } declare _ _ next-match ]
 173             ( i string regexp -- start end string ) define-temp
 174         ] when
 175     ] change-next-match ;
 176
 177 PRIVATE>
 178
 179 : new-regexp ( string ast options class -- regexp )
 180     [ \ regexp-initial-word \ next-initial-word ] dip boa ; inline
 181
 182 : make-regexp ( string ast -- regexp )
 183     f f <options> regexp new-regexp ;
 184
 185 : <optioned-regexp> ( string options -- regexp )
 186     [ dup parse-regexp ] [ string>options ] bi*
 187     dup on>> reversed-regexp swap member?
 188     [ reverse-regexp new-regexp ]
 189     [ regexp new-regexp ] if ;
 190
 191 : <regexp> ( string -- regexp ) "" <optioned-regexp> ;
 192
 193 <PRIVATE
 194
 195 : take-until ( lexer -- string )
 196     dup skip-blank [
 197         dupd [
 198             [ [ "\\/" member? ] find-from ] keep swap [
 199                 CHAR: \ = [ [ 2 + ] dip t ] [ f ] if
 200             ] [
 201                 "Unterminated regexp" throw
 202             ] if*
 203         ] loop over [ subseq ] dip 1 +
 204     ] change-lexer-column ;
 205
 206 : parse-noblank-token ( lexer -- str/f )
 207     dup still-parsing-line? [ (parse-raw) ] [ drop f ] if ;
 208
 209 : parse-regexp ( accum -- accum )
 210     lexer get [ take-until "\\/" "/" replace ] [ parse-noblank-token ] bi
 211     <optioned-regexp> compile-next-match suffix! ;
 212
 213 PRIVATE>
 214
 215 SYNTAX: R/ parse-regexp ;
 216
 217
 218 { "prettyprint" "regexp" } "regexp.prettyprint" require-when