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  }