← Back to branch summary

~ubuntu-branches/ubuntu/wily/parboiled/wily-proposed

« back to all changes in this revision

Viewing changes to parboiled-core/src/main/java/org/parboiled/matchers/FirstOfStringsMatcher.java

  • Committer: Package Import Robot
  • Author(s): Emmanuel Bourg
  • Date: 2014-11-10 21:10:42 UTC
  • Revision ID: package-import@ubuntu.com-20141110211042-wcmfz25icr5ituj5
Tags: upstream-1.1.6
Import upstream version 1.1.6

Show diffs side-by-side

added added

removed removed

Lines of Context:
parboiled-core/src/main/java/org/parboiled/matchers/FirstOfStringsMatcher.java
 
1
/*
 
2
 * Copyright (C) 2009-2011 Mathias Doenitz
 
3
 *
 
4
 * Licensed under the Apache License, Version 2.0 (the "License");
 
5
 * you may not use this file except in compliance with the License.
 
6
 * You may obtain a copy of the License at
 
7
 *
 
8
 * http://www.apache.org/licenses/LICENSE-2.0
 
9
 *
 
10
 * Unless required by applicable law or agreed to in writing, software
 
11
 * distributed under the License is distributed on an "AS IS" BASIS,
 
12
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 
13
 * See the License for the specific language governing permissions and
 
14
 * limitations under the License.
 
15
 */
 
16
 
 
17
package org.parboiled.matchers;
 
18
 
 
19
import static org.parboiled.common.Preconditions.*;
 
20
import org.parboiled.MatcherContext;
 
21
import org.parboiled.Rule;
 
22
import org.parboiled.errors.GrammarException;
 
23
import org.parboiled.buffers.InputBuffer;
 
24
 
 
25
import java.util.HashSet;
 
26
import java.util.Map;
 
27
import java.util.Set;
 
28
import java.util.TreeMap;
 
29
 
 
30
/**
 
31
 * A specialized FirstOfMatcher that handles FirstOf(string, string, ...) rules much faster that the regular
 
32
 * FirstOfMatcher. If fast string matching is enabled this matcher uses a prebuilt character tree to efficiently
 
33
 * determine whether the next input characters match the rule expression.
 
34
 */
 
35
public class FirstOfStringsMatcher extends FirstOfMatcher {
 
36
 
 
37
    // a node in the character tree
 
38
    static class Record {
 
39
        final char[] chars; // the sub characters of this node
 
40
        final Record[] subs; // the sub records corresponding to the respective character
 
41
        final boolean complete; // flag indicating that the path up to this record also constitutes a valid match
 
42
 
 
43
        private Record(char[] chars, Record[] subs, boolean complete) {
 
44
            this.chars = chars;
 
45
            this.subs = subs;
 
46
            this.complete = complete;
 
47
        }
 
48
    }
 
49
 
 
50
    private final Record root; // the root of the character tree
 
51
    public final char[][] strings;
 
52
 
 
53
    public FirstOfStringsMatcher(Rule[] subRules, char[][] strings) {
 
54
        super(checkArgNotNull(subRules, "subRules"));
 
55
        verify(strings);
 
56
        this.strings = strings;
 
57
        root = createRecord(0, strings);
 
58
    }
 
59
 
 
60
    @Override
 
61
    public boolean match(MatcherContext context) {
 
62
        if (!context.fastStringMatching()) {
 
63
            return super.match(context);
 
64
        }
 
65
 
 
66
        Record rec = root;
 
67
        int ix = context.getCurrentIndex();
 
68
        InputBuffer buffer = context.getInputBuffer();
 
69
        char c = context.getCurrentChar();
 
70
        int endIx = -1;
 
71
 
 
72
        loop:
 
73
        while (true) {
 
74
            char[] chars = rec.chars;
 
75
            for (int i = 0; i < chars.length; i++) {
 
76
                if (c == chars[i]) {
 
77
                    ix++;
 
78
                    rec = rec.subs[i];
 
79
                    if (rec == null) { // success, we complected a tree path to a leave
 
80
                        endIx = ix;
 
81
                        break loop;
 
82
                    }
 
83
                    if (rec.complete) { // we completed a valid match path, but continue looking for a longer match
 
84
                        endIx = ix;
 
85
                    }
 
86
                    c = buffer.charAt(ix);
 
87
                    continue loop;
 
88
                }
 
89
            }
 
90
            // we checked all sub branches of the current node, none matched, so we are done
 
91
            break;
 
92
        }
 
93
 
 
94
        if (endIx == -1) return false; // we matched no complete path, so fail
 
95
 
 
96
        context.advanceIndex(endIx - context.getCurrentIndex());
 
97
        context.createNode();
 
98
        return true;
 
99
    }
 
100
 
 
101
    static Record createRecord(int pos, char[][] strings) {
 
102
        Map<Character, Set<char[]>> map = new TreeMap<Character, Set<char[]>>();
 
103
        boolean complete = false;
 
104
        for (char[] s : strings) {
 
105
            if (s.length == pos) complete = true;
 
106
            if (s.length <= pos) continue;
 
107
            char c = s[pos];
 
108
            Set<char[]> charStrings = map.get(c);
 
109
            if (charStrings == null) {
 
110
                charStrings = new HashSet<char[]>();
 
111
                map.put(c, charStrings);
 
112
            }
 
113
            charStrings.add(s);
 
114
        }
 
115
 
 
116
        if (map.isEmpty()) return null;
 
117
 
 
118
        char[] chars = new char[map.size()];
 
119
        Record[] subs = new Record[map.size()];
 
120
        int i = 0;
 
121
        for (Map.Entry<Character, Set<char[]>> entry : map.entrySet()) {
 
122
            chars[i] = entry.getKey();
 
123
            subs[i++] = createRecord(pos + 1, entry.getValue().toArray(new char[entry.getValue().size()][]));
 
124
        }
 
125
        return new Record(chars, subs, complete);
 
126
    }
 
127
 
 
128
    // make sure that a string is no prefix of another string later in the array
 
129
    // this would cause the second string to never match without fast-string-matching,
 
130
    // but match in the fast implementation
 
131
 
 
132
    private static void verify(char[][] strings) {
 
133
        int length = strings.length;
 
134
        for (int i = 0; i < length; i++) {
 
135
            char[] a = strings[i];
 
136
            inner:
 
137
            for (int j = i + 1; j < length; j++) {
 
138
                char[] b = strings[j];
 
139
                if (b.length < a.length) continue;
 
140
                for (int k = 0; k < a.length; k++) {
 
141
                    if (a[k] != b[k]) continue inner;
 
142
                }
 
143
                String sa = '"' + String.valueOf(a) + '"';
 
144
                String sb = '"' + String.valueOf(b) + '"';
 
145
                String msg = a.length == b.length ? sa + " is specified twice in a FirstOf(String...)" : sa +
 
146
                        " is a prefix of " + sb + " in a FirstOf(String...) and comes before " +
 
147
                        sb + ", which prevents " + sb +
 
148
                        " from ever matching! You should reverse the order of the two alternatives.";
 
149
                throw new GrammarException(msg);
 
150
            }
 
151
        }
 
152
    }
 
153
}
 
 
b'\\ No newline at end of file'