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