-! 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 hashtables
-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
-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
state [ get ] [ inc ] bi ;
SYMBOL: nfa-table
-: table ( -- table ) nfa-table get ;
: set-each ( keys value hashtable -- )
'[ _ swap _ set-at ] each ;
GENERIC: nfa-node ( node -- start-state end-state )
-:: add-simple-entry ( obj class -- start-state end-state )
- next-state :> s0
- next-state :> s1
- 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 ;
+: add-simple-entry ( obj -- start-state end-state )
+ [ next-state next-state 2dup ] dip
+ nfa-table get add-transition ;
: epsilon-transition ( source target -- )
- eps <literal-transition> table add-transition ;
+ epsilon nfa-table get add-transition ;
M:: star nfa-node ( node -- start end )
- node term>> nfa-node :> s1 :> s0
+ node term>> nfa-node :> ( s0 s1 )
next-state :> s2
next-state :> s3
s1 s0 epsilon-transition
s1 s3 epsilon-transition
s2 s3 ;
-M: epsilon nfa-node
- drop eps literal-transition add-simple-entry ;
+DEFER: modify-class
+
+! Potential off-by-one errors when lookaround nested in lookbehind
-M: concatenation nfa-node ( node -- start end )
+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@
s3 s5 epsilon-transition
s4 s5 ;
-M: alternation nfa-node ( node -- start end )
+M: alternation nfa-node
[ first>> ] [ second>> ] bi
[ nfa-node ] bi@
alternate-nodes ;
-M: integer nfa-node ( node -- start end )
- case-insensitive option? [
- dup [ ch>lower ] [ ch>upper ] bi
- 2dup = [
- 2drop
- literal-transition add-simple-entry
- ] [
- [ literal-transition add-simple-entry ] bi@
- alternate-nodes [ nip ] dip
- ] if
- ] [ literal-transition add-simple-entry ] if ;
-
-M: primitive-class nfa-node ( node -- start end )
- class>> dup
- { letter-class LETTER-class } member? case-insensitive option? and
- [ drop Letter-class ] when
- class-transition add-simple-entry ;
-
-M: or-class nfa-node class-transition add-simple-entry ;
-M: not-class nfa-node class-transition add-simple-entry ;
-
-M: any-char nfa-node ( node -- start end )
- [ dotall option? ] dip any-char-no-nl ?
- class-transition add-simple-entry ;
-
-! M: negation nfa-node ( node -- start end )
-! negate term>> nfa-node negate ;
-
-M: range nfa-node ( node -- start end )
+GENERIC: modify-class ( char-class -- char-class' )
+
+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 -- start end )
+: 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
- 0 state set
- <transition-table> clone nfa-table set
+ 0 state namespaces:set
+ <transition-table> nfa-table namespaces:set
nfa-node
- table
- swap dup associate >>final-states
+ nfa-table get
+ swap 1array fast-set >>final-states
swap >>start-state
] with-scope ;
projects / factor.git / blobdiff