1 /*
2  * [The "BSD license"]
3  *  Copyright (c) 2016 Terence Parr
4  *  Copyright (c) 2016 Sam Harwell
5  *  Copyright (c) 2017 Egbert Voigt
6  *  All rights reserved.
7  *
8  *  Redistribution and use in source and binary forms, with or without
9  *  modification, are permitted provided that the following conditions
10  *  are met:
11  *
12  *  1. Redistributions of source code must retain the above copyright
13  *     notice, this list of conditions and the following disclaimer.
14  *  2. Redistributions in binary form must reproduce the above copyright
15  *     notice, this list of conditions and the following disclaimer in the
16  *     documentation and/or other materials provided with the distribution.
17  *  3. The name of the author may not be used to endorse or promote products
18  *     derived from this software without specific prior written permission.
19  *
20  *  THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
21  *  IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
22  *  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
23  *  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
24  *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
25  *  NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26  *  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27  *  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28  *  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
29  *  THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30  */
31 
32 module antlr.v4.runtime.atn.SemanticContext;
33 
34 import std.conv;
35 import antlr.v4.runtime.RuleContext;
36 import antlr.v4.runtime.InterfaceRecognizer;
37 import antlr.v4.runtime.atn.AND;
38 import antlr.v4.runtime.atn.OR;
39 import antlr.v4.runtime.misc.MurmurHash;
40 
41 
42 /**
43  * @uml
44  * A tree structure used to record the semantic context in which
45  * an ATN configuration is valid.  It's either a single predicate,
46  * a conjunction {@code p1&&p2}, or a sum of products {@code p1||p2}.
47  *
48  * <p>I have scoped the {@link AND}, {@link OR}, and {@link Predicate} subclasses of
49  * {@link SemanticContext} within the scope of this outer class.</p>
50  */
51 class SemanticContext
52 {
53     public bool eval(InterfaceRecognizer parser, RuleContext parserCallStack)
54     {
55         return true;
56     }
57     /**
58      * @uml
59      * The default {@link SemanticContext}, which is semantically equivalent to
60      * a predicate of the form {@code {true}?}.
61      */
62     public static SemanticContext NONE;
63 
64 
65     /**
66      * @uml
67      * For context independent predicates, we evaluate them without a local
68      * context (i.e., null context). That way, we can evaluate them without
69      * having to create proper rule-specific context during prediction (as
70      * opposed to the parser, which creates them naturally). In a practical
71      * sense, this avoids a cast exception from RuleContext to myruleContext.
72      *
73      * <p>For context dependent predicates, we must pass in a local context so that
74      * references such as $arg evaluate properly as _localctx.arg. We only
75      * capture context dependent predicates in the context in which we begin
76      * prediction, so we passed in the outer context here in case of context
77      * dependent predicate evaluation.</p>
78      */
79     //abstract public bool eval(InterfaceRecognizer parser, RuleContext parserCallStack);
80 
81     /**
82      * @uml
83      * Evaluate the precedence predicates for the context and reduce the result.
84      *
85      *  @param parser The parser instance.
86      *  @param parserCallStack
87      *  @return The simplified semantic context after precedence predicates are
88      *  evaluated, which will be one of the following values.
89      * <ul>
90      *  <li>{@link #NONE}: if the predicate simplifies to {@code true} after
91      *  precedence predicates are evaluated.</li>
92      *  <li>{@code null}: if the predicate simplifies to {@code false} after
93      *  precedence predicates are evaluated.</li>
94      *  <li>{@code this}: if the semantic context is not changed as a result of
95      *  precedence predicate evaluation.</li>
96      *  <li>A non-{@code null} {@link SemanticContext}: the new simplified
97      *  semantic context after precedence predicates are evaluated.</li>
98      * </ul>
99      */
100     public SemanticContext evalPrecedence(InterfaceRecognizer parser, RuleContext parserCallStack)
101     {
102         return this;
103     }
104     // Class Predicate
105     /**
106      * TODO add class description
107      */
108     class Predicate : SemanticContext
109     {
110         /**
111          * The single instance of LexerMoreAction.
112          */
113         private static __gshared Predicate instance_;
114 
115         public int ruleIndex;
116 
117         public int predIndex;
118 
119         /**
120          * @uml
121          * e.g., $i ref in pred
122          */
123         public bool isCtxDependent;
124 
125         public this()
126         {
127             this.ruleIndex = -1;
128             this.predIndex = -1;
129             this.isCtxDependent = false;
130         }
131 
132         public this(int ruleIndex, int predIndex, bool isCtxDependent)
133         {
134             this.ruleIndex = ruleIndex;
135             this.predIndex = predIndex;
136             this.isCtxDependent = isCtxDependent;
137         }
138 
139         /**
140          * @uml
141          * @override
142          */
143         public override bool eval(InterfaceRecognizer parser, RuleContext parserCallStack)
144         {
145             RuleContext localctx = isCtxDependent ? parserCallStack : null;
146             return parser.sempred(localctx, ruleIndex, predIndex);
147         }
148 
149         /**
150          * @uml
151          * @override
152          * @safe
153          * @nothrow
154          */
155         public override size_t toHash() @safe nothrow
156         {
157             size_t hashCode = MurmurHash.initialize();
158             hashCode = MurmurHash.update(hashCode, ruleIndex);
159             hashCode = MurmurHash.update(hashCode, predIndex);
160             hashCode = MurmurHash.update(hashCode, isCtxDependent ? 1 : 0);
161             hashCode = MurmurHash.finish(hashCode, 3);
162             return hashCode;
163         }
164 
165         /**
166          * @uml
167          * @override
168          */
169         public override bool opEquals(Object obj)
170         {
171             if (typeid(typeof(obj)) != typeid(Predicate*)) return false;
172             if ( this is obj ) return true;
173             Predicate p = cast(Predicate)obj;
174             return this.ruleIndex == p.ruleIndex &&
175                 this.predIndex == p.predIndex &&
176                 this.isCtxDependent == p.isCtxDependent;
177         }
178 
179         /**
180          * @uml
181          * @override
182          */
183         public override string toString()
184         {
185             return "{" ~ to!string(ruleIndex) ~ ":" ~ to!string(predIndex) ~ "}?";
186         }
187 
188         // /**
189         //  * Creates the single instance of Predicate.
190         //  */
191         // private shared static this()
192         // {
193         //     instance_ = new Predicate;
194         // }
195 
196         // /**
197         //  * Returns: A single instance of LexerMoreAction.
198         //  */
199         // public static Predicate instance()
200         // {
201         //     return instance_;
202         // }
203 
204     }
205     // Class PrecedencePredicate
206     /**
207      * TODO add class description
208      */
209     class PrecedencePredicate : SemanticContext
210     {
211 
212         /**
213          * @uml
214          * @final
215          */
216         public int precedence;
217 
218         protected this()
219         {
220             this.precedence = 0;
221         }
222 
223         public this(int precedence)
224         {
225             this.precedence = precedence;
226         }
227 
228         /**
229          * @uml
230          * @override
231          */
232         public override bool eval(InterfaceRecognizer parser, RuleContext parserCallStack)
233         {
234             return parser.precpred(parserCallStack, precedence);
235         }
236 
237         /**
238          * @uml
239          * @override
240          */
241         public override SemanticContext evalPrecedence(InterfaceRecognizer parser, RuleContext parserCallStack)
242         {
243             if (parser.precpred(parserCallStack, precedence)) {
244                 if (!SemanticContext.NONE)
245                     SemanticContext.NONE = new Predicate;
246                 return SemanticContext.NONE;
247             }
248             else {
249                 return null;
250             }
251         }
252 
253         /**
254          * @uml
255          * @override
256          */
257         public override int opCmp(Object o)
258         {
259             return precedence - (cast(PrecedencePredicate)o).precedence;
260         }
261 
262         /**
263          * @uml
264          * @override
265          * @safe
266          * @nothrow
267          */
268         public override size_t toHash() @safe nothrow
269         {
270             int hashCode = 1;
271             hashCode = 31 * hashCode + precedence;
272             return hashCode;
273         }
274 
275         /**
276          * @uml
277          * @override
278          */
279         public override bool opEquals(Object obj)
280         {
281             if (! cast(PrecedencePredicate)obj) {
282                 return false;
283             }
284 
285             if (this is obj) {
286                 return true;
287             }
288 
289             PrecedencePredicate other = cast(PrecedencePredicate)obj;
290             return this.precedence == other.precedence;
291         }
292 
293         /**
294          * @uml
295          * @override
296          * precedence >= _precedenceStack.peek()
297          */
298         public override string toString()
299         {
300             return "{" ~ to!string(precedence) ~ ">=prec}?";
301         }
302 
303     }
304 
305     /**
306      * @uml
307      * @safe
308      * @nothrow
309      * @override
310      */
311     public override size_t toHash() @safe nothrow
312     {
313         return 1;
314     }
315 
316     public static SemanticContext and(SemanticContext a, SemanticContext b)
317     {
318 	if (a is null || a == NONE ) return b;
319         if (b is null || b == NONE ) return a;
320         AND result = new AND(a, b);
321         if (result.opnds.length == 1) {
322             return result.opnds[0];
323         }
324         return result;
325     }
326 
327     public static SemanticContext or(SemanticContext a, SemanticContext b)
328     {
329 	if (a is null ) return b;
330         if (b is null ) return a;
331         if (a == NONE || b == NONE ) return NONE;
332         OR result = new OR(a, b);
333         if (result.opnds.length == 1) {
334             return result.opnds[0];
335         }
336         return result;
337     }
338 
339     public PrecedencePredicate[] filterPrecedencePredicates(SemanticContext[] collection)
340     {
341 	PrecedencePredicate[] result;
342         foreach (context; collection) {
343             if (context.classinfo == PrecedencePredicate.classinfo) {
344                 result ~= cast(PrecedencePredicate)context;
345             }
346         }
347         return result;
348     }
349 
350 }