private boolean crevdissect ( RuntimeSubexpression t , int begin , int end ) { Dfa d ; Dfa d2 ; int mid ; assert t . op == ' ' ; assert t . left != null && t . left . machine . states . length > 0 ; assert t . right != null && t . right . machine . states . length > 0 ; assert 0 != ( t . left . flags & Subre . SHORTER ) ; /* concatenation -- need to split the substring between parts */ d = new Dfa ( this , t . left . machine ) ; d2 = new Dfa ( this , t . right . machine ) ; /* pick a tentative midpoint */ if ( mem [ t . retry ] == 0 ) { mid = d . shortest ( begin , begin , end , null , null ) ; if ( mid == - 1 ) { return false ; } mem [ t . retry ] = ( mid - begin ) + 1 ; } else { mid = begin + ( mem [ t . retry ] - 1 ) ; } /* iterate until satisfaction or failure */ for ( ; ; ) { /* try this midpoint on for size */ boolean cdmatch = cdissect ( t . left , begin , mid ) ; if ( cdmatch && d2 . longest ( mid , end , null ) == end && ( cdissect ( t . right , mid , end ) ) ) { break ; /* NOTE BREAK OUT */ } /* that midpoint didn't work, find a new one */ if ( mid == end ) { /* all possibilities exhausted */ return false ; } mid = d . shortest ( begin , mid + 1 , end , null , null ) ; if ( mid == - 1 ) { /* failed to find a new one */ return false ; } mem [ t . retry ] = ( mid - begin ) + 1 ; zapmem ( t . left ) ; zapmem ( t . right ) ; } /* satisfaction */ return true ; }
crevdissect - determine backref shortest - first subexpression matches The retry memory stores the offset of the trial midpoint from begin plus 1 so that 0 uniquely means clean slate .