1 | // Copyright (c) 2009-2013 AlphaSierraPapa for the SharpDevelop Team |
---|
2 | // |
---|
3 | // Permission is hereby granted, free of charge, to any person obtaining a copy of this |
---|
4 | // software and associated documentation files (the "Software"), to deal in the Software |
---|
5 | // without restriction, including without limitation the rights to use, copy, modify, merge, |
---|
6 | // publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons |
---|
7 | // to whom the Software is furnished to do so, subject to the following conditions: |
---|
8 | // |
---|
9 | // The above copyright notice and this permission notice shall be included in all copies or |
---|
10 | // substantial portions of the Software. |
---|
11 | // |
---|
12 | // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, |
---|
13 | // INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR |
---|
14 | // PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE |
---|
15 | // FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR |
---|
16 | // OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER |
---|
17 | // DEALINGS IN THE SOFTWARE. |
---|
18 | |
---|
19 | using System; |
---|
20 | using System.Linq; |
---|
21 | using System.Collections.Generic; |
---|
22 | using System.Diagnostics; |
---|
23 | using System.Threading; |
---|
24 | using ICSharpCode.NRefactory.Editor; |
---|
25 | using ICSharpCode.NRefactory.Utils; |
---|
26 | |
---|
27 | namespace ICSharpCode.NRefactory.Xml |
---|
28 | { |
---|
29 | class TagMatchingHeuristics |
---|
30 | { |
---|
31 | readonly ITextSource textSource; |
---|
32 | |
---|
33 | const int MaxConfigurationCount = 30; |
---|
34 | |
---|
35 | public TagMatchingHeuristics(ITextSource textSource) |
---|
36 | { |
---|
37 | this.textSource = textSource; |
---|
38 | } |
---|
39 | |
---|
40 | public InternalDocument CreateDocument(List<InternalObject> tagSoup, CancellationToken cancellationToken) |
---|
41 | { |
---|
42 | var stack = InsertPlaceholderTags(tagSoup, cancellationToken); |
---|
43 | InternalDocument doc = new InternalDocument(); |
---|
44 | var docElements = CreateElements(ref stack); |
---|
45 | docElements.Reverse(); // reverse due to stack |
---|
46 | doc.NestedObjects = new InternalObject[docElements.Count]; |
---|
47 | int pos = 0; |
---|
48 | for (int i = 0; i < docElements.Count; i++) { |
---|
49 | doc.NestedObjects[i] = docElements[i].SetStartRelativeToParent(pos); |
---|
50 | pos += doc.NestedObjects[i].Length; |
---|
51 | } |
---|
52 | doc.Length = pos; |
---|
53 | return doc; |
---|
54 | } |
---|
55 | |
---|
56 | #region Heuristic implementation - Inserting place holders into object stream |
---|
57 | // Tags used to guide the element creation |
---|
58 | static readonly InternalTag StartTagPlaceholder = new InternalTag { OpeningBracket = "<", ClosingBracket = ">" }; |
---|
59 | static readonly InternalTag EndTagPlaceholder = new InternalTag { OpeningBracket = "</", ClosingBracket = ">" }; |
---|
60 | |
---|
61 | class OpenTagStack |
---|
62 | { |
---|
63 | readonly OpenTagStack prev; |
---|
64 | public readonly string Name; |
---|
65 | public readonly int IndentationLevel; |
---|
66 | readonly int hashCode; |
---|
67 | |
---|
68 | public OpenTagStack() |
---|
69 | { |
---|
70 | } |
---|
71 | |
---|
72 | private OpenTagStack(OpenTagStack prev, string name, int indentationLevel) |
---|
73 | { |
---|
74 | this.prev = prev; |
---|
75 | this.Name = name; |
---|
76 | this.IndentationLevel = indentationLevel; |
---|
77 | unchecked { |
---|
78 | this.hashCode = prev.hashCode * 27 + (name.GetHashCode() ^ indentationLevel); |
---|
79 | } |
---|
80 | } |
---|
81 | |
---|
82 | public bool IsEmpty { |
---|
83 | get { return prev == null; } |
---|
84 | } |
---|
85 | |
---|
86 | public OpenTagStack Push(string name, int indentationLevel) |
---|
87 | { |
---|
88 | return new OpenTagStack(this, name, indentationLevel); |
---|
89 | } |
---|
90 | |
---|
91 | public OpenTagStack Pop() |
---|
92 | { |
---|
93 | return prev; |
---|
94 | } |
---|
95 | |
---|
96 | public override int GetHashCode() |
---|
97 | { |
---|
98 | return hashCode; |
---|
99 | } |
---|
100 | |
---|
101 | public override bool Equals(object obj) |
---|
102 | { |
---|
103 | OpenTagStack o = obj as OpenTagStack; |
---|
104 | if (o != null && hashCode == o.hashCode && IndentationLevel == o.IndentationLevel && Name == o.Name) { |
---|
105 | if (prev == o.prev) |
---|
106 | return true; |
---|
107 | if (prev == null || o.prev == null) |
---|
108 | return false; |
---|
109 | return prev.Equals(o.prev); |
---|
110 | } |
---|
111 | return false; |
---|
112 | } |
---|
113 | } |
---|
114 | |
---|
115 | struct Configuration |
---|
116 | { |
---|
117 | public readonly OpenTagStack OpenTags; |
---|
118 | public readonly ImmutableStack<InternalObject> Document; |
---|
119 | public readonly uint Cost; |
---|
120 | |
---|
121 | public Configuration(OpenTagStack openTags, ImmutableStack<InternalObject> document, uint cost) |
---|
122 | { |
---|
123 | this.OpenTags = openTags; |
---|
124 | this.Document = document; |
---|
125 | this.Cost = cost; |
---|
126 | } |
---|
127 | } |
---|
128 | |
---|
129 | struct ConfigurationList |
---|
130 | { |
---|
131 | internal Configuration[] configurations; |
---|
132 | internal int count; |
---|
133 | |
---|
134 | public static ConfigurationList Create() |
---|
135 | { |
---|
136 | return new ConfigurationList { |
---|
137 | configurations = new Configuration[MaxConfigurationCount], |
---|
138 | count = 0 |
---|
139 | }; |
---|
140 | } |
---|
141 | |
---|
142 | public void Clear() |
---|
143 | { |
---|
144 | this.count = 0; |
---|
145 | } |
---|
146 | |
---|
147 | public void Add(OpenTagStack openTags, ImmutableStack<InternalObject> document, uint cost) |
---|
148 | { |
---|
149 | Add(new Configuration(openTags, document, cost)); |
---|
150 | } |
---|
151 | |
---|
152 | public void Add(Configuration configuration) |
---|
153 | { |
---|
154 | for (int i = 0; i < count; i++) { |
---|
155 | if (configuration.OpenTags.Equals(configurations[i].OpenTags)) { |
---|
156 | // We found an existing configuration with the same state. |
---|
157 | // Either replace it, or drop this configurations -- |
---|
158 | // we don't want to add multiple configurations with the same state. |
---|
159 | if (configuration.Cost < configurations[i].Cost) |
---|
160 | configurations[i] = configuration; |
---|
161 | return; |
---|
162 | } |
---|
163 | } |
---|
164 | if (count < configurations.Length) { |
---|
165 | configurations[count++] = configuration; |
---|
166 | } else { |
---|
167 | int index = 0; |
---|
168 | uint maxCost = configurations[0].Cost; |
---|
169 | for (int i = 1; i < configurations.Length; i++) { |
---|
170 | if (configurations[i].Cost < maxCost) { |
---|
171 | maxCost = configurations[i].Cost; |
---|
172 | index = i; |
---|
173 | } |
---|
174 | } |
---|
175 | configurations[index] = configuration; |
---|
176 | } |
---|
177 | } |
---|
178 | } |
---|
179 | |
---|
180 | const uint InfiniteCost = uint.MaxValue; |
---|
181 | const uint MissingEndTagCost = 10; |
---|
182 | const uint IgnoreEndTagCost = 10; |
---|
183 | const uint MismatchedNameCost = 6; |
---|
184 | |
---|
185 | int GetIndentationBefore(int position) |
---|
186 | { |
---|
187 | int indentation = 0; |
---|
188 | while (--position >= 0) { |
---|
189 | char c = textSource.GetCharAt(position); |
---|
190 | switch (c) { |
---|
191 | case ' ': |
---|
192 | indentation++; |
---|
193 | break; |
---|
194 | case '\t': |
---|
195 | indentation += 4; |
---|
196 | break; |
---|
197 | case '\n': |
---|
198 | return indentation; |
---|
199 | default: |
---|
200 | return -1; |
---|
201 | } |
---|
202 | } |
---|
203 | return indentation; |
---|
204 | } |
---|
205 | |
---|
206 | ImmutableStack<InternalObject> InsertPlaceholderTags(List<InternalObject> objects, CancellationToken cancellationToken) |
---|
207 | { |
---|
208 | // Calculate indentation levels in front of the tags: |
---|
209 | int[] indentationBeforeTags = new int[objects.Count]; |
---|
210 | int pos = 0; |
---|
211 | for (int i = 0; i < objects.Count; i++) { |
---|
212 | if (objects[i] is InternalTag) |
---|
213 | indentationBeforeTags[i] = GetIndentationBefore(pos); |
---|
214 | pos += objects[i].Length; |
---|
215 | } |
---|
216 | |
---|
217 | // Create initial configuration: |
---|
218 | ConfigurationList listA = ConfigurationList.Create(); |
---|
219 | ConfigurationList listB = ConfigurationList.Create(); |
---|
220 | listA.Add(new Configuration(new OpenTagStack(), ImmutableStack<InternalObject>.Empty, 0)); |
---|
221 | |
---|
222 | for (int i = 0; i < indentationBeforeTags.Length; i++) { |
---|
223 | cancellationToken.ThrowIfCancellationRequested(); |
---|
224 | ProcessObject(objects[i], indentationBeforeTags[i], listA, ref listB); |
---|
225 | Swap(ref listA, ref listB); |
---|
226 | } |
---|
227 | |
---|
228 | Configuration cheapestConfiguration = new Configuration(null, null, InfiniteCost); |
---|
229 | for (int i = 0; i < listA.count; i++) { |
---|
230 | Configuration c = listA.configurations[i]; |
---|
231 | if (c.Cost < cheapestConfiguration.Cost) { |
---|
232 | while (!c.OpenTags.IsEmpty) { |
---|
233 | c = new Configuration(c.OpenTags.Pop(), c.Document.Push(EndTagPlaceholder), c.Cost + MissingEndTagCost); |
---|
234 | } |
---|
235 | if (c.Cost < cheapestConfiguration.Cost) |
---|
236 | cheapestConfiguration = c; |
---|
237 | } |
---|
238 | } |
---|
239 | Log.WriteLine("Best configuration has cost {0}", cheapestConfiguration.Cost); |
---|
240 | return cheapestConfiguration.Document; |
---|
241 | } |
---|
242 | |
---|
243 | static void Swap(ref ConfigurationList a, ref ConfigurationList b) |
---|
244 | { |
---|
245 | ConfigurationList tmp = a; |
---|
246 | a = b; |
---|
247 | b = tmp; |
---|
248 | } |
---|
249 | |
---|
250 | void ProcessObject(InternalObject obj, int indentationLevel, ConfigurationList oldConfigurations, ref ConfigurationList newConfigurations) |
---|
251 | { |
---|
252 | newConfigurations.Clear(); |
---|
253 | InternalTag tag = obj as InternalTag; |
---|
254 | for (int i = 0; i < oldConfigurations.count; i++) { |
---|
255 | Configuration c = oldConfigurations.configurations[i]; |
---|
256 | if (c.Cost == InfiniteCost) |
---|
257 | continue; |
---|
258 | if (tag != null && tag.IsStartTag) { |
---|
259 | // Push start tag |
---|
260 | newConfigurations.Add( |
---|
261 | c.OpenTags.Push(tag.Name, indentationLevel), |
---|
262 | c.Document.Push(obj), |
---|
263 | c.Cost |
---|
264 | ); |
---|
265 | } else if (tag != null && tag.IsEndTag) { |
---|
266 | // We can ignore this end tag |
---|
267 | newConfigurations.Add( |
---|
268 | c.OpenTags, |
---|
269 | c.Document.Push(StartTagPlaceholder).Push(obj), |
---|
270 | c.Cost + IgnoreEndTagCost |
---|
271 | ); |
---|
272 | // We can match this end tag with one of the currently open tags |
---|
273 | var openTags = c.OpenTags; |
---|
274 | var documentWithInsertedEndTags = c.Document; |
---|
275 | uint newCost = c.Cost; |
---|
276 | while (!openTags.IsEmpty) { |
---|
277 | uint matchCost = 0; |
---|
278 | if (openTags.IndentationLevel >= 0 && indentationLevel >= 0) |
---|
279 | matchCost += (uint)Math.Abs(openTags.IndentationLevel - indentationLevel); |
---|
280 | if (openTags.Name != tag.Name) |
---|
281 | matchCost += MismatchedNameCost; |
---|
282 | newConfigurations.Add( |
---|
283 | openTags.Pop(), |
---|
284 | documentWithInsertedEndTags.Push(obj), |
---|
285 | newCost + matchCost |
---|
286 | ); |
---|
287 | newCost += MissingEndTagCost; |
---|
288 | openTags = openTags.Pop(); |
---|
289 | documentWithInsertedEndTags = documentWithInsertedEndTags.Push(EndTagPlaceholder); |
---|
290 | } |
---|
291 | } else { |
---|
292 | newConfigurations.Add( |
---|
293 | c.OpenTags, |
---|
294 | c.Document.Push(obj), |
---|
295 | c.Cost |
---|
296 | ); |
---|
297 | } |
---|
298 | } |
---|
299 | } |
---|
300 | #endregion |
---|
301 | |
---|
302 | #region Create Elements from stack with place holders |
---|
303 | List<InternalObject> CreateElements(ref ImmutableStack<InternalObject> inputObjects) |
---|
304 | { |
---|
305 | List<InternalObject> objects = new List<InternalObject>(); |
---|
306 | while (!inputObjects.IsEmpty) { |
---|
307 | var obj = inputObjects.Peek(); |
---|
308 | var tag = obj as InternalTag; |
---|
309 | if (tag != null && tag.IsStartTag) |
---|
310 | break; |
---|
311 | inputObjects = inputObjects.Pop(); |
---|
312 | if (tag != null && tag.IsEndTag) { |
---|
313 | if (inputObjects.Peek() == StartTagPlaceholder) { |
---|
314 | objects.Add(tag.AddSyntaxError("Matching opening tag was not found")); |
---|
315 | inputObjects = inputObjects.Pop(); |
---|
316 | } else { |
---|
317 | var childElements = CreateElements(ref inputObjects); |
---|
318 | var startTag = (InternalTag)inputObjects.Peek(); |
---|
319 | inputObjects = inputObjects.Pop(); |
---|
320 | childElements.Add(startTag); |
---|
321 | childElements.Reverse(); |
---|
322 | if (tag != EndTagPlaceholder) { |
---|
323 | // add end tag |
---|
324 | if (startTag.Name != tag.Name) { |
---|
325 | childElements.Add(tag.AddSyntaxError("Expected '</" + startTag.Name + ">'. End tag must have same name as start tag.")); |
---|
326 | } else { |
---|
327 | childElements.Add(tag); |
---|
328 | } |
---|
329 | } |
---|
330 | InternalElement e = new InternalElement(startTag); |
---|
331 | e.HasEndTag = (tag != EndTagPlaceholder); |
---|
332 | e.NestedObjects = new InternalObject[childElements.Count]; |
---|
333 | int pos = 0; |
---|
334 | for (int i = 0; i < childElements.Count; i++) { |
---|
335 | e.NestedObjects[i] = childElements[i].SetStartRelativeToParent(pos); |
---|
336 | pos += e.NestedObjects[i].Length; |
---|
337 | } |
---|
338 | e.Length = pos; |
---|
339 | if (tag == EndTagPlaceholder) { |
---|
340 | e.SyntaxErrors = new [] { new InternalSyntaxError(pos, pos, "Missing '</" + startTag.Name + ">'") }; |
---|
341 | } |
---|
342 | objects.Add(e); |
---|
343 | } |
---|
344 | } else { |
---|
345 | objects.Add(obj); |
---|
346 | } |
---|
347 | } |
---|
348 | return objects; |
---|
349 | } |
---|
350 | #endregion |
---|
351 | } |
---|
352 | } |
---|