-! Copyright (C) 2008 Doug Coleman.
+! Copyright (C) 2008, 2009 Doug Coleman, Daniel Ehrenberg.
! See http://factorcode.org/license.txt for BSD license.
-USING: accessors arrays assocs grouping kernel
-locals math namespaces sequences fry quotations
-math.order math.ranges vectors unicode.categories
-regexp.transition-tables words sets
-unicode.case.private regexp.ast regexp.classes ;
-! This uses unicode.case.private for ch>upper and ch>lower
-! but case-insensitive matching should be done by case-folding everything
-! before processing starts
+USING: accessors arrays assocs combinators.short-circuit kernel
+math namespaces regexp.ast regexp.classes
+regexp.transition-tables sequences sets unicode vectors ;
IN: regexp.nfa
-ERROR: feature-is-broken feature ;
-
-SYMBOL: negated?
-
-: negate ( -- )
- negated? [ not ] change ;
-
-SINGLETON: eps
+! This uses unicode for ch>upper and ch>lower
+! but case-insensitive matching should be done by case-folding everything
+! before processing starts
SYMBOL: option-stack
-SYMBOL: combine-stack
-
SYMBOL: state
: next-state ( -- state )
: option? ( obj -- ? )
option-stack get assoc-stack ;
-: set-start-state ( -- nfa-table )
- nfa-table get
- combine-stack get pop first >>start-state ;
-
-GENERIC: nfa-node ( node -- )
-
-:: add-simple-entry ( obj class -- )
- [let* | s0 [ next-state ]
- s1 [ next-state ]
- stack [ combine-stack get ]
- table [ nfa-table get ] |
- negated? get [
- s0 f obj class make-transition table add-transition
- s0 s1 <default-transition> table add-transition
- ] [
- s0 s1 obj class make-transition table add-transition
- ] if
- s0 s1 2array stack push
- t s1 table final-states>> set-at ] ;
-
-:: concatenate-nodes ( -- )
- [let* | stack [ combine-stack get ]
- table [ nfa-table get ]
- s2 [ stack peek first ]
- s3 [ stack pop second ]
- s0 [ stack peek first ]
- s1 [ stack pop second ] |
- s1 s2 eps <literal-transition> table add-transition
- s1 table final-states>> delete-at
- s0 s3 2array stack push ] ;
-
-:: alternate-nodes ( -- )
- [let* | stack [ combine-stack get ]
- table [ nfa-table get ]
- s2 [ stack peek first ]
- s3 [ stack pop second ]
- s0 [ stack peek first ]
- s1 [ stack pop second ]
- s4 [ next-state ]
- s5 [ next-state ] |
- s4 s0 eps <literal-transition> table add-transition
- s4 s2 eps <literal-transition> table add-transition
- s1 s5 eps <literal-transition> table add-transition
- s3 s5 eps <literal-transition> table add-transition
- s1 table final-states>> delete-at
- s3 table final-states>> delete-at
- t s5 table final-states>> set-at
- s4 s5 2array stack push ] ;
-
-M: star nfa-node ( node -- )
- term>> nfa-node
- [let* | stack [ combine-stack get ]
- s0 [ stack peek first ]
- s1 [ stack pop second ]
- s2 [ next-state ]
- s3 [ next-state ]
- table [ nfa-table get ] |
- s1 table final-states>> delete-at
- t s3 table final-states>> set-at
- s1 s0 eps <literal-transition> table add-transition
- s2 s0 eps <literal-transition> table add-transition
- s2 s3 eps <literal-transition> table add-transition
- s1 s3 eps <literal-transition> table add-transition
- s2 s3 2array stack push ] ;
-
-M: concatenation nfa-node ( node -- )
- seq>> [ eps literal-transition add-simple-entry ] [
- reversed-regexp option? [ <reversed> ] when
- [ [ nfa-node ] each ]
- [ length 1- [ concatenate-nodes ] times ] bi
- ] if-empty ;
-
-M: alternation nfa-node ( node -- )
- seq>>
- [ [ nfa-node ] each ]
- [ length 1- [ alternate-nodes ] times ] bi ;
-
-M: integer nfa-node ( node -- )
- case-insensitive option? [
- dup [ ch>lower ] [ ch>upper ] bi
- 2dup = [
- 2drop
- literal-transition add-simple-entry
- ] [
- [ literal-transition add-simple-entry ] bi@
- alternate-nodes drop
- ] if
- ] [
- literal-transition add-simple-entry
- ] if ;
+GENERIC: nfa-node ( node -- start-state end-state )
+
+: add-simple-entry ( obj -- start-state end-state )
+ [ next-state next-state 2dup ] dip
+ nfa-table get add-transition ;
+
+: epsilon-transition ( source target -- )
+ epsilon nfa-table get add-transition ;
+
+M:: star nfa-node ( node -- start end )
+ node term>> nfa-node :> ( s0 s1 )
+ next-state :> s2
+ next-state :> s3
+ s1 s0 epsilon-transition
+ s2 s0 epsilon-transition
+ s2 s3 epsilon-transition
+ s1 s3 epsilon-transition
+ s2 s3 ;
+
+DEFER: modify-class
+
+! Potential off-by-one errors when lookaround nested in lookbehind
+
+M: tagged-epsilon nfa-node
+ clone [ modify-class ] change-tag add-simple-entry ;
+
+M: concatenation nfa-node
+ [ first>> ] [ second>> ] bi
+ reversed-regexp option? [ swap ] when
+ [ nfa-node ] bi@
+ [ epsilon-transition ] dip ;
-M: primitive-class nfa-node ( node -- )
- class>> dup
- { letter-class LETTER-class } member? case-insensitive option? and
- [ drop Letter-class ] when
- class-transition add-simple-entry ;
+:: alternate-nodes ( s0 s1 s2 s3 -- start end )
+ next-state :> s4
+ next-state :> s5
+ s4 s0 epsilon-transition
+ s4 s2 epsilon-transition
+ s1 s5 epsilon-transition
+ s3 s5 epsilon-transition
+ s4 s5 ;
-M: any-char nfa-node ( node -- )
- [ dotall option? ] dip any-char-no-nl ?
- class-transition add-simple-entry ;
+M: alternation nfa-node
+ [ first>> ] [ second>> ] bi
+ [ nfa-node ] bi@
+ alternate-nodes ;
-M: negation nfa-node ( node -- )
- negate term>> nfa-node negate ;
+GENERIC: modify-class ( char-class -- char-class' )
-M: range nfa-node ( node -- )
+M: object modify-class ;
+
+M: concatenation modify-class
+ [ first>> ] [ second>> ] bi [ modify-class ] bi@
+ concatenation boa ;
+
+M: alternation modify-class
+ [ first>> ] [ second>> ] bi [ modify-class ] bi@
+ alternation boa ;
+
+M: lookahead modify-class
+ term>> modify-class lookahead boa ;
+
+M: lookbehind modify-class
+ term>> modify-class lookbehind boa ;
+
+: line-option ( multiline unix-lines default -- option )
+ multiline option? [
+ drop [ unix-lines option? ] 2dip swap ?
+ ] [ 2nip ] if ;
+
+M: $crlf modify-class
+ $unix end-of-input line-option ;
+
+M: ^crlf modify-class
+ ^unix beginning-of-input line-option ;
+
+M: integer modify-class
case-insensitive option? [
- ! This should be implemented for Unicode by case-folding
- ! the input and all strings in the regexp.
- dup [ from>> ] [ to>> ] bi
- 2dup [ Letter? ] bi@ and [
- rot drop
- [ [ ch>lower ] bi@ <range> ]
- [ [ ch>upper ] bi@ <range> ] 2bi
- [ class-transition add-simple-entry ] bi@
- alternate-nodes
- ] [
- 2drop
- class-transition add-simple-entry
- ] if
- ] [
- class-transition add-simple-entry
+ dup Letter? [
+ [ ch>lower ] [ ch>upper ] bi 2array <or-class>
+ ] when
+ ] when ;
+
+M: primitive-class modify-class
+ class>> modify-class <primitive-class> ;
+
+M: or-class modify-class
+ seq>> [ modify-class ] map <or-class> ;
+
+M: not-class modify-class
+ class>> modify-class <not-class> ;
+
+MEMO: unix-dot ( -- class )
+ CHAR: \n <not-class> ;
+
+MEMO: nonl-dot ( -- class )
+ { CHAR: \n CHAR: \r } <or-class> <not-class> ;
+
+M: dot modify-class
+ drop dotall option? [ t ] [
+ unix-lines option?
+ unix-dot nonl-dot ?
] if ;
-M: with-options nfa-node ( node -- )
+: modify-letter-class ( class -- newclass )
+ case-insensitive option? [ drop Letter-class ] when ;
+M: letter-class modify-class modify-letter-class ;
+M: LETTER-class modify-class modify-letter-class ;
+
+: cased-range? ( range -- ? )
+ [ from>> ] [ to>> ] bi {
+ [ [ letter? ] both? ]
+ [ [ LETTER? ] both? ]
+ } 2|| ;
+
+M: range-class modify-class
+ case-insensitive option? [
+ dup cased-range? [
+ [ from>> ] [ to>> ] bi
+ [ [ ch>lower ] bi@ <range-class> ]
+ [ [ ch>upper ] bi@ <range-class> ] 2bi
+ 2array <or-class>
+ ] when
+ ] when ;
+
+M: object nfa-node
+ modify-class add-simple-entry ;
+
+M: with-options nfa-node
dup options>> [ tree>> nfa-node ] using-options ;
: construct-nfa ( ast -- nfa-table )
[
- negated? off
- V{ } clone combine-stack set
- 0 state set
- <transition-table> clone nfa-table set
+ 0 state namespaces:set
+ <transition-table> nfa-table namespaces:set
nfa-node
- set-start-state
+ nfa-table get
+ swap 1array fast-set >>final-states
+ swap >>start-state
] with-scope ;
projects / factor.git / blobdiff