001/* 002 * Copyright (c) 2016 Chris K Wensel <chris@wensel.net>. All Rights Reserved. 003 * Copyright (c) 2007-2017 Xplenty, Inc. All Rights Reserved. 004 * 005 * Project and contact information: http://www.cascading.org/ 006 * 007 * This file is part of the Cascading project. 008 * 009 * Licensed under the Apache License, Version 2.0 (the "License"); 010 * you may not use this file except in compliance with the License. 011 * You may obtain a copy of the License at 012 * 013 * http://www.apache.org/licenses/LICENSE-2.0 014 * 015 * Unless required by applicable law or agreed to in writing, software 016 * distributed under the License is distributed on an "AS IS" BASIS, 017 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 018 * See the License for the specific language governing permissions and 019 * limitations under the License. 020 */ 021 022package cascading.flow.planner.iso.finder; 023 024import java.util.Arrays; 025import java.util.Collections; 026import java.util.HashMap; 027import java.util.HashSet; 028import java.util.Iterator; 029import java.util.LinkedHashMap; 030import java.util.LinkedHashSet; 031import java.util.Map; 032import java.util.Set; 033 034import cascading.flow.FlowElement; 035import cascading.flow.planner.PlannerContext; 036import cascading.flow.planner.Scope; 037import cascading.flow.planner.graph.ElementGraph; 038import cascading.flow.planner.iso.expression.ElementCapture; 039import cascading.flow.planner.iso.expression.ElementExpression; 040import cascading.flow.planner.iso.expression.ExpressionGraph; 041import cascading.flow.planner.iso.expression.ScopeExpression; 042import cascading.util.EnumMultiMap; 043import cascading.util.Pair; 044import cascading.util.Util; 045import org.jgrapht.graph.DirectedMultigraph; 046import org.slf4j.Logger; 047import org.slf4j.LoggerFactory; 048 049import static cascading.flow.planner.graph.ElementGraphs.directed; 050 051/** 052 * 053 */ 054public class GraphFinder 055 { 056 private static final Logger LOG = LoggerFactory.getLogger( GraphFinder.class ); 057 058 ExpressionGraph matchExpression; 059 060 public GraphFinder( ExpressionGraph matchExpression ) 061 { 062 if( matchExpression == null ) 063 throw new IllegalArgumentException( "expressionGraph may not be null" ); 064 065 this.matchExpression = matchExpression; 066 } 067 068 public ExpressionGraph getMatchExpression() 069 { 070 return matchExpression; 071 } 072 073 public Match findFirstMatch( ElementGraph elementGraph ) 074 { 075 return findFirstMatch( new PlannerContext(), elementGraph ); 076 } 077 078 public Match findFirstMatch( PlannerContext plannerContext, ElementGraph elementGraph ) 079 { 080 return findFirstMatch( new FinderContext(), plannerContext, elementGraph ); 081 } 082 083 public Match findFirstMatch( PlannerContext plannerContext, ElementGraph elementGraph, Set<FlowElement> exclusions ) 084 { 085 return findFirstMatch( new FinderContext( exclusions ), plannerContext, elementGraph ); 086 } 087 088 protected Match findFirstMatch( FinderContext finderContext, PlannerContext plannerContext, ElementGraph elementGraph ) 089 { 090 Map<ElementExpression, FlowElement> mapping = findMapping( finderContext, plannerContext, elementGraph ); 091 092 return new Match( matchExpression, elementGraph, mapping, mapping.values(), getCapturedEdges( plannerContext, elementGraph, mapping ) ); 093 } 094 095 public Match findAllMatches( ElementGraph elementGraph ) 096 { 097 return findAllMatches( new PlannerContext(), elementGraph ); 098 } 099 100 public Match findAllMatches( PlannerContext plannerContext, ElementGraph elementGraph ) 101 { 102 return findAllMatches( plannerContext, elementGraph, Collections.<FlowElement>emptySet() ); 103 } 104 105 public Match findAllMatches( PlannerContext plannerContext, ElementGraph elementGraph, Set<FlowElement> exclusions ) 106 { 107 Set<ElementExpression> elementExpressions = matchExpression.getGraph().vertexSet(); 108 109 if( elementExpressions.size() != 1 ) 110 throw new IllegalStateException( "may not search multiple matches against multi-node expression: " + matchExpression ); 111 112 ElementExpression expression = Util.getFirst( elementExpressions ); 113 114 if( expression.getCapture() != ElementCapture.Primary ) 115 throw new IllegalStateException( "capture on expression must be Primary: " + expression ); 116 117 Set<FlowElement> foundElements = new LinkedHashSet<>(); 118 119 // no evidence elementGraph.vertexSet().iterator(); is faster without modifying jgrapht 120 Iterator<FlowElement> iterator = SearchOrder.getNodeIterator( matchExpression.getSearchOrder(), directed( elementGraph ) ); 121 122 while( iterator.hasNext() ) 123 { 124 FlowElement flowElement = iterator.next(); 125 126 if( exclusions.contains( flowElement ) ) 127 continue; 128 129 if( expression.applies( plannerContext, elementGraph, flowElement ) ) 130 foundElements.add( flowElement ); 131 } 132 133 // we are only capturing Primary distinguished elements 134 return new Match( matchExpression, elementGraph, null, foundElements, Collections.<Scope>emptySet() ) 135 { 136 @Override 137 public Set<FlowElement> getCapturedElements( ElementCapture... captures ) 138 { 139 if( !Arrays.asList( captures ).contains( ElementCapture.Primary ) ) 140 return Collections.emptySet(); 141 142 return (Set<FlowElement>) this.foundElements; 143 } 144 }; 145 } 146 147 public Match findAllMatchesOnPrimary( ElementGraph elementGraph ) 148 { 149 return findAllMatchesOnPrimary( new PlannerContext(), elementGraph ); 150 } 151 152 public Match findAllMatchesOnPrimary( PlannerContext plannerContext, ElementGraph elementGraph ) 153 { 154 return findMatchesOnPrimary( new FinderContext(), plannerContext, elementGraph, false ); 155 } 156 157 public Match findMatchesOnPrimary( PlannerContext plannerContext, ElementGraph elementGraph, boolean firstOnly, Set<FlowElement> excludes ) 158 { 159 return findMatchesOnPrimary( new FinderContext( excludes ), plannerContext, elementGraph, firstOnly ); 160 } 161 162 public Match findAllMatchesOnPrimary( PlannerContext plannerContext, ElementGraph elementGraph, Set<FlowElement> excludes ) 163 { 164 return findMatchesOnPrimary( new FinderContext( excludes ), plannerContext, elementGraph, false ); 165 } 166 167 protected Match findMatchesOnPrimary( FinderContext finderContext, PlannerContext plannerContext, ElementGraph elementGraph, boolean firstOnly ) 168 { 169 Match match = null; 170 171 EnumMultiMap<FlowElement> captureMap = new EnumMultiMap<>(); 172 173 while( true ) 174 { 175 Match current = findFirstMatch( finderContext, plannerContext, elementGraph ); 176 177 if( !current.foundMatch() ) 178 break; 179 180 captureMap.addAll( current.getCaptureMap() ); 181 182 Set<FlowElement> anchoredElements = current.getCapturedElements( ElementCapture.Primary ); 183 184 // should never capture new primary elements in subsequent searches 185 if( finderContext.getRequiredElements().isEmpty() ) 186 finderContext.getRequiredElements().addAll( anchoredElements ); 187 188 match = current; 189 190 Map<ElementExpression, FlowElement> vertexMapping = current.getVertexMapping(); 191 192 finderContext.getMatchedElements().addAll( vertexMapping.values() ); 193 finderContext.getMatchedScopes().addAll( getCapturedEdges( plannerContext, elementGraph, vertexMapping ) ); 194 195 if( firstOnly ) // we are not rotating around the primary capture 196 break; 197 198 Set<FlowElement> includedElements = current.getIncludedElements(); 199 200 if( includedElements.isEmpty() ) 201 break; 202 203 // should only ignore edges, not elements 204 finderContext.getIgnoredElements().addAll( includedElements ); 205 } 206 207 // TODO: must capture all vertex mappings in order to see all Secondary and Included elements for annotations 208 209 // this only returns the last mapping, but does capture the Primary matches as they are required across all matches 210 Map<ElementExpression, FlowElement> mapping = match == null ? null : match.getVertexMapping(); 211 212 return new Match( matchExpression, elementGraph, mapping, finderContext.getMatchedElements(), finderContext.getMatchedScopes(), captureMap ); 213 } 214 215 public Map<ScopeExpression, Set<Scope>> getEdgeMapping( PlannerContext plannerContext, ElementGraph elementGraph, Map<ElementExpression, FlowElement> vertexMapping ) 216 { 217 Map<ScopeExpression, Set<Scope>> edgeMapping = new HashMap<>(); 218 219 DirectedMultigraph<ElementExpression, ScopeExpression> delegate = matchExpression.getGraph(); 220 for( ScopeExpression scopeExpression : delegate.edgeSet() ) 221 { 222 ElementExpression lhs = delegate.getEdgeSource( scopeExpression ); 223 ElementExpression rhs = delegate.getEdgeTarget( scopeExpression ); 224 225 FlowElement lhsElement = vertexMapping.get( lhs ); 226 FlowElement rhsElement = vertexMapping.get( rhs ); 227 228 Set<Scope> edges = elementGraph.getAllEdges( lhsElement, rhsElement ); 229 230 if( edges != null ) 231 edgeMapping.put( scopeExpression, edges ); 232 } 233 234 return edgeMapping; 235 } 236 237 public Set<Scope> getCapturedEdges( PlannerContext plannerContext, ElementGraph elementGraph, Map<ElementExpression, FlowElement> vertexMapping ) 238 { 239 Set<Scope> scopes = new HashSet<>(); 240 241 if( vertexMapping.isEmpty() ) 242 return scopes; 243 244 for( Map.Entry<ScopeExpression, Set<Scope>> entry : getEdgeMapping( plannerContext, elementGraph, vertexMapping ).entrySet() ) 245 { 246 if( entry.getKey().isCapture() ) 247 scopes.addAll( entry.getValue() ); 248 } 249 250 return scopes; 251 } 252 253 public Map<ElementExpression, FlowElement> findMapping( PlannerContext plannerContext, ElementGraph elementGraph ) 254 { 255 return findMapping( new FinderContext(), plannerContext, elementGraph ); 256 } 257 258 protected Map<ElementExpression, FlowElement> findMapping( FinderContext finderContext, PlannerContext plannerContext, ElementGraph elementGraph ) 259 { 260 State state = new State( finderContext, plannerContext, matchExpression.getSearchOrder(), matchExpression.getGraph(), elementGraph ); 261 262 Map<Integer, Integer> vertexMap = new LinkedHashMap<>(); 263 264 boolean match = match( state, vertexMap ); 265 266 if( !match ) 267 return Collections.emptyMap(); 268 269 Map<ElementExpression, FlowElement> result = new LinkedHashMap<>(); 270 271 for( Map.Entry<Integer, Integer> entry : vertexMap.entrySet() ) 272 result.put( state.getMatcherNode( entry.getKey() ), state.getElementNode( entry.getValue() ) ); 273 274 return result; 275 } 276 277 /** 278 * Returns {@code true} if the graphs being matched by this state are 279 * isomorphic. 280 */ 281 private boolean match( State state, Map<Integer, Integer> vertexMap ) 282 { 283 if( LOG.isTraceEnabled() ) 284 LOG.trace( "begin matching with state: {}", state ); 285 286 if( state.isGoal() ) 287 return true; 288 289 if( state.isDead() ) 290 return false; 291 292 int n1 = State.NULL_NODE; 293 int n2 = State.NULL_NODE; 294 Pair<Integer, Integer> next; 295 boolean found = false; 296 297 while( !found && ( next = state.nextPair( n1, n2 ) ) != null ) 298 { 299 n1 = next.getLhs(); 300 n2 = next.getRhs(); 301 302 if( LOG.isTraceEnabled() ) 303 LOG.trace( "begin matching pair: N1: {}, N2: {}", n1, n2 ); 304 305 boolean feasiblePair = state.isFeasiblePair( n1, n2 ); 306 307 if( LOG.isTraceEnabled() && !feasiblePair ) 308 LOG.trace( "not feasible pair: N1: {}, N2: {}", n1, n2 ); 309 310 if( feasiblePair ) 311 { 312 State copy = state.copy(); 313 copy.addPair( n1, n2 ); 314 found = match( copy, vertexMap ); 315 316 // If we found a mapping, fill the vertex mapping state 317 if( found ) 318 { 319 for( Map.Entry<Integer, Integer> entry : copy.getVertexMapping().entrySet() ) 320 { 321 if( vertexMap.containsKey( entry.getKey() ) && !vertexMap.get( entry.getKey() ).equals( entry.getValue() ) ) 322 throw new IllegalStateException( "duplicate key with differing values" ); 323 } 324 325 if( LOG.isTraceEnabled() ) 326 LOG.trace( "match for feasible pair: N1: {}, N2: {}", n1, n2 ); 327 328 vertexMap.putAll( copy.getVertexMapping() ); 329 330 if( LOG.isTraceEnabled() ) 331 LOG.trace( "vertex map: {}", vertexMap ); 332 } 333 else 334 { 335 if( LOG.isTraceEnabled() ) 336 LOG.trace( "no match for feasible pair: N1: {}, N2: {}", n1, n2 ); 337 338 copy.backTrack(); 339 } 340 } 341 } 342 343 if( LOG.isTraceEnabled() ) 344 LOG.trace( "completed matching with state: {}, found: {}", state, found ); 345 346 return found; 347 } 348 }