-! Copyright (C) 2008 Doug Coleman.
+! Copyright (C) 2008, 2009 Doug Coleman, Daniel Ehrenberg.
! See http://factorcode.org/license.txt for BSD license.
-USING: accessors combinators kernel math sequences strings
-sets assocs prettyprint.backend make lexer namespaces parser
-arrays fry regexp.backend regexp.utils regexp.parser regexp.nfa
-regexp.dfa regexp.traversal regexp.transition-tables splitting
-sorting ;
+USING: accessors arrays classes compiler.units kernel
+kernel.private lexer make math ranges namespaces quotations
+regexp.ast regexp.compiler regexp.negation regexp.parser
+sequences sequences.private splitting strings vocabs.loader
+words ;
IN: regexp
-: default-regexp ( string -- regexp )
- regexp new
- swap >>raw
- <transition-table> >>nfa-table
- <transition-table> >>dfa-table
- <transition-table> >>minimized-table
- H{ } clone >>nfa-traversal-flags
- H{ } clone >>dfa-traversal-flags
- H{ } clone >>options
- H{ } clone >>matchers
- reset-regexp ;
-
-: construct-regexp ( regexp -- regexp' )
- {
- [ parse-regexp ]
- [ construct-nfa ]
- [ construct-dfa ]
- [ ]
- } cleave ;
-
-: (match) ( string regexp -- dfa-traverser )
- <dfa-traverser> do-match ; inline
-
-: match ( string regexp -- slice/f )
- (match) return-match ;
-
-: match* ( string regexp -- slice/f captured-groups )
- (match) [ return-match ] [ captured-groups>> ] bi ;
+TUPLE: regexp
+ { raw read-only }
+ { parse-tree read-only }
+ { options read-only }
+ dfa next-match ;
+
+TUPLE: reverse-regexp < regexp ;
+
+<PRIVATE
+
+M: lookahead question>quot
+ ! Returns ( index string -- ? )
+ term>> ast>dfa dfa>shortest-word 1quotation [ f ] prepose ;
+
+: <reversed-option> ( ast -- reversed )
+ "r" string>options <with-options> ;
+
+M: lookbehind question>quot
+ ! Returns ( index string -- ? )
+ term>> <reversed-option>
+ ast>dfa dfa>reverse-shortest-word
+ 1quotation [ [ 1 - ] dip f ] prepose ;
+
+: match-index-from ( i string regexp -- index/f )
+ ! This word is unsafe. It assumes that i is a fixnum
+ ! and that string is a string.
+ dup dfa>> execute( index string regexp -- i/f ) ; inline
+
+GENERIC: end/start ( string regexp -- end start )
+M: regexp end/start drop length 0 ;
+M: reverse-regexp end/start drop length 1 - -1 swap ;
+
+PRIVATE>
: matches? ( string regexp -- ? )
- dupd match
- [ [ length ] bi@ = ] [ drop f ] if* ;
+ [ string check-instance ] dip
+ [ end/start ] 2keep
+ match-index-from
+ [ = ] [ drop f ] if* ;
-: match-head ( string regexp -- end/f ) match [ length ] [ f ] if* ;
+<PRIVATE
-: match-at ( string m regexp -- n/f finished? )
- [
- 2dup swap length > [ 2drop f f ] [ tail-slice t ] if
- ] dip swap [ match-head f ] [ 2drop f t ] if ;
+: search-range ( i string reverse? -- seq )
+ [ drop -1 ] [ length ] if [a..b] ; inline
+
+:: (next-match) ( i string regexp quot: ( i string regexp -- j ) reverse? -- start end ? )
+ i string regexp quot call dup
+ [| j | reverse? [ j i ] [ i j ] if string ] [ drop f f f ] if ; inline
+
+:: next-match ( i string regexp quot: ( i string regexp -- j ) reverse? -- start end ? )
+ f f f
+ i string reverse? search-range
+ [ 3nip string regexp quot reverse? (next-match) dup ] find 2drop ; inline
+
+: do-next-match ( i string regexp -- start end ? )
+ dup next-match>>
+ execute( i string regexp -- start end ? ) ; inline
+
+:: (each-match-forward) ( ... i string regexp quot: ( ... start end string -- ... ) -- ... )
+ i string length <= [
+ i string regexp do-next-match [| start end |
+ start end string quot call
+ start end eq? [ end 1 + ] [ end ] if
+ string regexp quot (each-match-forward)
+ ] [ 2drop ] if
+ ] when ; inline recursive
+
+:: (each-match-backward) ( ... i string regexp quot: ( ... start end string -- ... ) -- ... )
+ i -1 >= [
+ i string regexp do-next-match [| start end |
+ start 1 + end 1 + string quot call
+ start end eq? [ start 1 - ] [ start ] if
+ string regexp quot (each-match-backward)
+ ] [ 2drop ] if
+ ] when ; inline recursive
+
+: (each-match) ( ... i string regexp quot: ( ... start end string -- ... ) -- ... )
+ over reverse-regexp? [ (each-match-backward) ] [ (each-match-forward) ] if ; inline
+
+GENERIC: match-iterator-start ( string regexp -- start )
+M: regexp match-iterator-start 2drop 0 ;
+M: reverse-regexp match-iterator-start drop length ;
+
+: prepare-match-iterator ( string regexp -- i string regexp )
+ [ string check-instance ] dip [ match-iterator-start ] 2keep ; inline
+
+PRIVATE>
+
+: each-match ( ... string regexp quot: ( ... start end string -- ... ) -- ... )
+ [ prepare-match-iterator ] dip (each-match) ; inline
+
+: map-matches ( ... string regexp quot: ( ... start end string -- ... obj ) -- ... seq )
+ collector [ each-match ] dip >array ; inline
+
+: all-matching-slices ( string regexp -- seq )
+ [ <slice-unsafe> ] map-matches ;
+
+: all-matching-subseqs ( string regexp -- seq )
+ [ subseq ] map-matches ;
+
+: count-matches ( string regexp -- n )
+ [ 0 ] 2dip [ 3drop 1 + ] each-match ;
-: match-range ( string m regexp -- a/f b/f )
- 3dup match-at over [
- drop nip rot drop dupd +
- ] [
- [ 3drop drop f f ] [ drop [ 1+ ] dip match-range ] if
- ] if ;
+<PRIVATE
+
+:: (re-split) ( string regexp quot: ( from to seq -- slice ) -- new-slices )
+ 0 string regexp [| end start end' string |
+ end' ! leave it on the stack for the next iteration
+ end start string quot call
+ ] map-matches
+ ! Final chunk
+ swap string length string quot call suffix ; inline
-: first-match ( string regexp -- slice/f )
- dupd 0 swap match-range rot over [ <slice> ] [ 3drop f ] if ;
+PRIVATE>
-: re-cut ( string regexp -- end/f start )
- dupd first-match
- [ split1-slice swap ] [ "" like f swap ] if* ;
+:: first-match ( string regexp -- slice/f )
+ string regexp prepare-match-iterator do-next-match [
+ regexp reverse-regexp? [ [ 1 + ] bi@ ] when
+ string <slice-unsafe>
+ ] [ 2drop f ] if ;
+
+: re-contains? ( string regexp -- ? )
+ prepare-match-iterator do-next-match 2nip >boolean ;
: re-split ( string regexp -- seq )
- [ dup length 0 > ] swap '[ _ re-cut ] [ ] produce nip ;
+ [ <slice-unsafe> ] (re-split) ;
: re-replace ( string regexp replacement -- result )
- [ re-split ] dip join ;
+ [ [ subseq ] (re-split) ] dip join ;
+
+:: re-replace-with ( string regexp quot: ( slice -- replacement ) -- result )
+ [
+ 0 string regexp [
+ drop [ [ string <slice-unsafe> , ] keep ] dip
+ [ string <slice-unsafe> quot call( x -- x ) , ] keep
+ ] each-match string [ length ] [ <slice-unsafe> ] bi ,
+ ] { } make concat ;
-: next-match ( string regexp -- end/f match/f )
- dupd first-match dup
- [ [ split1-slice nip ] keep ] [ 2drop f f ] if ;
+<PRIVATE
-: all-matches ( string regexp -- seq )
- [ dup ] swap '[ _ next-match ] [ ] produce nip harvest ;
+: get-ast ( regexp -- ast )
+ [ parse-tree>> ] [ options>> ] bi <with-options> ;
-: count-matches ( string regexp -- n )
- all-matches length ;
+GENERIC: compile-regexp ( regex -- regexp )
-<PRIVATE
+: regexp-initial-word ( i string regexp -- i/f )
+ [ compile-regexp ] with-compilation-unit match-index-from ;
+
+M: regexp compile-regexp
+ dup '[
+ dup \ regexp-initial-word =
+ [ drop _ get-ast ast>dfa dfa>word ] when
+ ] change-dfa ;
-: find-regexp-syntax ( string -- prefix suffix )
- {
- { "R/ " "/" }
- { "R! " "!" }
- { "R\" " "\"" }
- { "R# " "#" }
- { "R' " "'" }
- { "R( " ")" }
- { "R@ " "@" }
- { "R[ " "]" }
- { "R` " "`" }
- { "R{ " "}" }
- { "R| " "|" }
- } swap [ subseq? not nip ] curry assoc-find drop ;
-
-: string>options ( string -- options )
- [ ch>option dup ] H{ } map>assoc ;
-
-: options>string ( options -- string )
- keys [ option>ch ] map natural-sort >string ;
+M: reverse-regexp compile-regexp
+ t backwards? [ call-next-method ] with-variable ;
+
+DEFER: compile-next-match
+
+: next-initial-word ( i string regexp -- start end string )
+ [ compile-next-match ] with-compilation-unit do-next-match ;
+
+: compile-next-match ( regexp -- regexp )
+ dup '[
+ dup \ next-initial-word = [
+ drop _ [ compile-regexp dfa>> def>> ] [ reverse-regexp? ] bi
+ '[ { array-capacity string regexp } declare _ _ next-match ]
+ ( i string regexp -- start end string ) define-temp
+ ] when
+ ] change-next-match ;
PRIVATE>
-: <optioned-regexp> ( string option-string -- regexp )
- [ default-regexp ] [ string>options ] bi* >>options
- construct-regexp ;
+: new-regexp ( string ast options class -- regexp )
+ [ \ regexp-initial-word \ next-initial-word ] dip boa ; inline
+
+: make-regexp ( string ast -- regexp )
+ f f <options> regexp new-regexp ;
+
+: <optioned-regexp> ( string options -- regexp )
+ [ dup parse-regexp ] [ string>options ] bi*
+ dup on>> reversed-regexp swap member?
+ [ reverse-regexp new-regexp ]
+ [ regexp new-regexp ] if ;
: <regexp> ( string -- regexp ) "" <optioned-regexp> ;
<PRIVATE
-: parsing-regexp ( accum end -- accum )
- lexer get dup skip-blank
- [ [ index-from dup 1+ swap ] 2keep swapd subseq swap ] change-lexer-column
- lexer get dup still-parsing-line?
- [ (parse-token) ] [ drop f ] if
- <optioned-regexp> parsed ;
+: take-until ( lexer -- string )
+ dup skip-blank [
+ dupd [
+ [ [ "\\/" member? ] find-from ] keep swap [
+ CHAR: \ = [ [ 2 + ] dip t ] [ f ] if
+ ] [
+ "Unterminated regexp" throw
+ ] if*
+ ] loop over [ subseq ] dip 1 +
+ ] change-lexer-column ;
+
+: parse-noblank-token ( lexer -- str/f )
+ dup still-parsing-line? [ (parse-raw) ] [ drop f ] if ;
+
+: parse-regexp ( accum -- accum )
+ lexer get [ take-until "\\/" "/" replace ] [ parse-noblank-token ] bi
+ <optioned-regexp> compile-next-match suffix! ;
PRIVATE>
-: R! CHAR: ! parsing-regexp ; parsing
-: R" CHAR: " parsing-regexp ; parsing
-: R# CHAR: # parsing-regexp ; parsing
-: R' CHAR: ' parsing-regexp ; parsing
-: R( CHAR: ) parsing-regexp ; parsing
-: R/ CHAR: / parsing-regexp ; parsing
-: R@ CHAR: @ parsing-regexp ; parsing
-: R[ CHAR: ] parsing-regexp ; parsing
-: R` CHAR: ` parsing-regexp ; parsing
-: R{ CHAR: } parsing-regexp ; parsing
-: R| CHAR: | parsing-regexp ; parsing
-
-M: regexp pprint*
- [
- [
- [ raw>> dup find-regexp-syntax swap % swap % % ]
- [ options>> options>string % ] bi
- ] "" make
- ] keep present-text ;
+SYNTAX: R/ parse-regexp ;
+
+
+{ "prettyprint" "regexp" } "regexp.prettyprint" require-when
projects / factor.git / blobdiff