[11804] | 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 | } |
---|