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  }