Source code

001/*
002 * Copyright (C) 2009-2011 Mathias Doenitz
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package org.parboiled;
018
019import org.parboiled.buffers.InputBuffer;
020import org.parboiled.common.ImmutableLinkedList;
021import org.parboiled.common.Preconditions;
022import org.parboiled.common.StringUtils;
023import org.parboiled.errors.BasicParseError;
024import org.parboiled.errors.ErrorUtils;
025import org.parboiled.errors.GrammarException;
026import org.parboiled.errors.ParseError;
027import org.parboiled.errors.ParserRuntimeException;
028import org.parboiled.matchers.ActionMatcher;
029import org.parboiled.matchers.Matcher;
030import org.parboiled.matchers.MatcherUtils;
031import org.parboiled.matchers.ProxyMatcher;
032import org.parboiled.matchers.SequenceMatcher;
033import org.parboiled.matchers.TestMatcher;
034import org.parboiled.matchers.TestNotMatcher;
035import org.parboiled.parserunners.RecoveringParseRunner;
036import org.parboiled.parserunners.ReportingParseRunner;
037import org.parboiled.support.Checks;
038import org.parboiled.support.IndexRange;
039import org.parboiled.support.MatcherPath;
040import org.parboiled.support.MatcherPosition;
041import org.parboiled.support.ParseTreeUtils;
042import org.parboiled.support.Position;
043import org.parboiled.support.ValueStack;
044import org.parboiled.matchers.ActionMatcher;
045import org.parboiled.matchers.Matcher;
046import org.parboiled.matchers.MatcherUtils;
047import org.parboiled.matchers.ProxyMatcher;
048import org.parboiled.matchers.SequenceMatcher;
049import org.parboiled.matchers.TestMatcher;
050import org.parboiled.matchers.TestNotMatcher;
051import org.parboiled.parserunners.RecoveringParseRunner;
052import org.parboiled.parserunners.ReportingParseRunner;
053import org.parboiled.support.Checks;
054import org.parboiled.support.IndexRange;
055import org.parboiled.support.MatcherPath;
056import org.parboiled.support.MatcherPosition;
057import org.parboiled.support.ParseTreeUtils;
058import org.parboiled.support.Position;
059import org.parboiled.support.ValueStack;
060
061import java.util.HashSet;
062import java.util.List;
063import java.util.Set;
064
065/**
066 * <p>The Context implementation orchestrating most of the matching process.</p>
067 * <p>The parsing process works as following:
068 * After the rule tree (which is in fact a directed and potentially even cyclic graph of {@link Matcher} instances)
069 * has been created a root MatcherContext is instantiated for the root rule (Matcher).
070 * A subsequent call to {@link #runMatcher()} starts the parsing process.</p>
071 * <p>The MatcherContext delegates to a given {@link MatchHandler} to call {@link Matcher#match(MatcherContext)},
072 * passing itself to the Matcher which executes its logic, potentially calling sub matchers.
073 * For each sub matcher the matcher creates/initializes a subcontext with {@link Matcher#getSubContext(MatcherContext)}
074 * and then calls {@link #runMatcher()} on it.</p>
075 * <p>This basically creates a stack of MatcherContexts, each corresponding to their rule matchers. The MatcherContext
076 * instances serve as companion objects to the matchers, providing them with support for building the
077 * parse tree nodes, keeping track of input locations and error recovery.</p>
078 * <p>At each point during the parsing process the matchers and action expressions have access to the current
079 * MatcherContext and all "open" parent MatcherContexts through the {@link #getParent()} chain.</p>
080 * <p>For performance reasons subcontext instances are reused instead of being recreated. If a MatcherContext instance
081 * returns null on a {@link #getMatcher()} call it has been retired (is invalid) and is waiting to be reinitialized
082 * with a new Matcher by its parent</p>
083 */
084public class MatcherContext<V> implements Context<V> {
085
086    private final InputBuffer inputBuffer;
087    private final ValueStack<V> valueStack;
088    private final List<ParseError> parseErrors;
089    private final MatchHandler matchHandler;
090    private final MatcherContext<V> parent;
091    private final int level;
092    private final boolean fastStringMatching;
093    private final Set<MatcherPosition> memoizedMismatches;
094
095    private MatcherContext<V> subContext;
096    private int startIndex;
097    private int currentIndex;
098    private char currentChar;
099    private Matcher matcher;
100    private Node<V> node;
101    private ImmutableLinkedList<Node<V>> subNodes = ImmutableLinkedList.nil();
102    private MatcherPath path;
103    private int intTag;
104    private boolean hasError;
105    private boolean nodeSuppressed;
106    private boolean inErrorRecovery;
107
108    /**
109     * Initializes a new root MatcherContext.
110     *
111     * @param inputBuffer        the InputBuffer for the parsing run
112     * @param valueStack         the ValueStack instance to use for the parsing run
113     * @param parseErrors        the parse error list to create ParseError objects in
114     * @param matchHandler       the MatcherHandler to use for the parsing run
115     * @param matcher            the root matcher
116     * @param fastStringMatching <p>Fast string matching "short-circuits" the default practice of treating string rules
117     *                           as simple Sequence of character rules. When fast string matching is enabled strings are
118     *                           matched at once, without relying on inner CharacterMatchers. Even though this can lead
119     *                           to significant increases of parsing performance it does not play well with error
120     *                           reporting and recovery, which relies on character level matches.
121     *                           Therefore the {@link ReportingParseRunner} and {@link RecoveringParseRunner}
122     *                           implementations only enable fast string matching during their basic first parsing run
123     *                           and disable it once the input has proven to contain errors.</p>
124     */
125    public MatcherContext(InputBuffer inputBuffer, ValueStack<V> valueStack, List<ParseError> parseErrors,
126                          MatchHandler matchHandler, Matcher matcher, boolean fastStringMatching) {
127        this(Preconditions.checkArgNotNull(inputBuffer, "inputBuffer"), Preconditions.checkArgNotNull(valueStack, "valueStack"),
128                Preconditions.checkArgNotNull(parseErrors, "parseErrors"), Preconditions.checkArgNotNull(matchHandler, "matchHandler"),
129                null, 0, fastStringMatching,  new HashSet<MatcherPosition>());
130        this.currentChar = inputBuffer.charAt(0);
131        this.matcher = ProxyMatcher.unwrap(Preconditions.checkArgNotNull(matcher, "matcher"));
132        this.nodeSuppressed = matcher.isNodeSuppressed();
133    }
134
135    private MatcherContext(InputBuffer inputBuffer, ValueStack<V> valueStack, List<ParseError> parseErrors,
136                           MatchHandler matchHandler, MatcherContext<V> parent, int level, boolean fastStringMatching,
137                           Set<MatcherPosition> memoizedMismatches) {
138        this.inputBuffer = inputBuffer;
139        this.valueStack = valueStack;
140        this.parseErrors = parseErrors;
141        this.matchHandler = matchHandler;
142        this.parent = parent;
143        this.level = level;
144        this.fastStringMatching = fastStringMatching;
145        this.memoizedMismatches = memoizedMismatches;
146    }
147
148    @Override
149    public String toString() {
150        return getPath().toString();
151    }
152
153    //////////////////////////////// CONTEXT INTERFACE ////////////////////////////////////
154
155    public MatcherContext<V> getParent() {
156        return parent;
157    }
158
159    public InputBuffer getInputBuffer() {
160        return inputBuffer;
161    }
162
163    public int getStartIndex() {
164        return startIndex;
165    }
166
167    public Matcher getMatcher() {
168        return matcher;
169    }
170
171    public char getCurrentChar() {
172        return currentChar;
173    }
174
175    public List<ParseError> getParseErrors() {
176        return parseErrors;
177    }
178
179    public int getCurrentIndex() {
180        return currentIndex;
181    }
182
183    public MatcherPath getPath() {
184        if (path == null) {
185            path = new MatcherPath(new MatcherPath.Element(matcher, startIndex, level),
186                    parent != null ? parent.getPath() : null);
187        }
188        return path;
189    }
190
191    public int getLevel() {
192        return level;
193    }
194
195    public boolean fastStringMatching() {
196        return fastStringMatching;
197    }
198
199    public ImmutableLinkedList<Node<V>> getSubNodes() {
200        return matcher.isNodeSkipped() ? subNodes : getSubNodes(subNodes, ImmutableLinkedList.<Node<V>>nil());
201    }
202
203    private static <V> ImmutableLinkedList<Node<V>> getSubNodes(ImmutableLinkedList<Node<V>> remaining,
204                                                                ImmutableLinkedList<Node<V>> tail) {
205        while (!remaining.isEmpty()) {
206            Node<V> head = remaining.head();
207            if (head.getMatcher().isNodeSkipped()) {
208                tail = getSubNodes(((ImmutableLinkedList<Node<V>>)head.getChildren()), tail);
209            } else {
210                tail = tail.prepend(head);
211            }
212            remaining = remaining.tail();
213        }
214        return tail;
215    }
216
217    public boolean inPredicate() {
218        return matcher instanceof TestMatcher || matcher instanceof TestNotMatcher ||
219                parent != null && parent.inPredicate();
220    }
221
222    public boolean inErrorRecovery() {
223        return inErrorRecovery;
224    }
225    
226    public boolean isNodeSuppressed() {
227        return nodeSuppressed;
228    }
229
230    public boolean hasError() {
231        return hasError;
232    }
233
234    public String getMatch() {
235        checkActionContext();
236        MatcherContext prevContext = subContext;
237        if (hasError) {
238            Node prevNode = prevContext.node;
239            return prevNode != null ? ParseTreeUtils.getNodeText(prevNode, inputBuffer) : "";
240        }
241        return inputBuffer.extract(prevContext.startIndex, prevContext.currentIndex);
242    }
243
244    public char getFirstMatchChar() {
245        checkActionContext();
246        int ix = subContext.startIndex;
247        if (subContext.currentIndex <= ix) {
248            throw new GrammarException("getFirstMatchChar called but previous rule did not match anything");
249        }
250        return inputBuffer.charAt(ix);
251    }
252
253    public int getMatchStartIndex() {
254        checkActionContext();
255        return subContext.startIndex;
256    }
257
258    public int getMatchEndIndex() {
259        checkActionContext();
260        return subContext.currentIndex;
261    }
262
263    public int getMatchLength() {
264        checkActionContext();
265        return subContext.currentIndex - subContext.getStartIndex();
266    }
267
268    public Position getPosition() {
269        return inputBuffer.getPosition(currentIndex);
270    }
271
272    public IndexRange getMatchRange() {
273        checkActionContext();
274        return new IndexRange(subContext.startIndex, subContext.currentIndex);
275    }
276
277    private void checkActionContext() {
278        // make sure all the constraints are met
279        Checks.ensure(MatcherUtils.unwrap(matcher) instanceof SequenceMatcher && intTag > 0 &&
280                subContext.matcher instanceof ActionMatcher,
281                "Illegal call to getMatch(), getMatchStartIndex(), getMatchEndIndex() or getMatchRange(), " +
282                        "only valid in Sequence rule actions that are not in first position");
283    }
284
285    public ValueStack<V> getValueStack() {
286        return valueStack;
287    }
288
289    //////////////////////////////// PUBLIC ////////////////////////////////////
290
291    public void setMatcher(Matcher matcher) {
292        this.matcher = matcher;
293    }
294
295    public void setStartIndex(int startIndex) {
296        Preconditions.checkArgument(startIndex >= 0);
297        this.startIndex = startIndex;
298    }
299
300    public void setCurrentIndex(int currentIndex) {
301        Preconditions.checkArgument(currentIndex >= 0);
302        this.currentIndex = currentIndex;
303        currentChar = inputBuffer.charAt(currentIndex);
304    }
305    
306    public void setInErrorRecovery(boolean flag) {
307        inErrorRecovery = flag;
308    }
309
310    public void advanceIndex(int delta) {
311        currentIndex += delta;
312        currentChar = inputBuffer.charAt(currentIndex);
313    }
314
315    public Node<V> getNode() {
316        return node;
317    }
318
319    public int getIntTag() {
320        return intTag;
321    }
322
323    public void setIntTag(int intTag) {
324        this.intTag = intTag;
325    }
326
327    public void markError() {
328        if (!hasError) {
329            hasError = true;
330            if (parent != null) parent.markError();
331        }
332    }
333
334    public Boolean hasMismatched() {
335        return memoizedMismatches.contains(MatcherPosition.at(matcher, currentIndex));
336    }
337
338    public void memoizeMismatch() {
339        memoizedMismatches.add(MatcherPosition.at(matcher, currentIndex));
340    }
341
342    @SuppressWarnings({"ConstantConditions"})
343    public void createNode() {
344        if (!nodeSuppressed) {
345            node = new NodeImpl<V>(matcher, getSubNodes(), startIndex, currentIndex,
346                    valueStack.isEmpty() ? null : valueStack.peek(), hasError);
347            if (parent != null) {
348                parent.subNodes = parent.subNodes.prepend(node);
349            }
350        }
351    }
352
353    public final MatcherContext<V> getBasicSubContext() {
354        if (subContext == null) {
355            // init new level
356            subContext = new MatcherContext<V>(inputBuffer, valueStack, parseErrors, matchHandler, this, level + 1,
357                        fastStringMatching, memoizedMismatches);
358        } else {
359            subContext.path = null; // we always need to reset the MatcherPath, even for actions
360        }
361        return subContext;
362    }
363
364    public final MatcherContext<V> getSubContext(Matcher matcher) {
365        MatcherContext<V> sc = getBasicSubContext();
366        sc.matcher = matcher;
367        sc.startIndex = sc.currentIndex = currentIndex;
368        sc.currentChar = currentChar;
369        sc.node = null;
370        sc.subNodes = ImmutableLinkedList.nil();
371        sc.nodeSuppressed = nodeSuppressed || this.matcher.areSubnodesSuppressed() || matcher.isNodeSuppressed();
372        sc.hasError = false;
373        return sc;
374    }
375
376    public boolean runMatcher() {
377        try {
378            if (matchHandler.match(this)) {
379                if (parent != null) {
380                    parent.currentIndex = currentIndex;
381                    parent.currentChar = currentChar;
382                }
383                matcher = null; // "retire" this context
384                return true;
385            }
386            matcher = null; // "retire" this context until is "activated" again by a getSubContext(...) on the parent
387            return false;
388        } catch (ParserRuntimeException e) {
389            throw e; // don't wrap, just bubble up
390        } catch (RecoveringParseRunner.TimeoutException e) {
391            throw e; // don't wrap, just bubble up
392        } catch (Throwable e) {
393            throw new ParserRuntimeException(e,
394                    ErrorUtils.printParseError(new BasicParseError(inputBuffer, currentIndex,
395                            StringUtils.escape(String.format("Error while parsing %s '%s' at input position",
396                                    matcher instanceof ActionMatcher ? "action" : "rule", getPath())))) + '\n' + e);
397        }
398    }
399}