From 84ee28f13d37e31e270674e48b9d95b4b097383c Mon Sep 17 00:00:00 2001
From: alexlamsl <alexlamsl@gmail.com>
Date: Mon, 2 May 2016 03:06:15 +0800
Subject: [PATCH] fix performance corner case in sort functionality

---
 src/tokenchain.js | 40 +++++++++++++++++++++++++---------------
 tests/minifier.js |  6 ++++++
 2 files changed, 31 insertions(+), 15 deletions(-)

diff --git a/src/tokenchain.js b/src/tokenchain.js
index 36a6c93..377e496 100644
--- a/src/tokenchain.js
+++ b/src/tokenchain.js
@@ -1,7 +1,6 @@
 'use strict';
 
-function Sorter(tokens) {
-  this.tokens = tokens;
+function Sorter() {
 }
 
 Sorter.prototype.sort = function(tokens, fromIndex) {
@@ -30,26 +29,37 @@ TokenChain.prototype = {
   add: function(tokens) {
     var self = this;
     tokens.forEach(function(token) {
-      (self[token] || (self[token] = [])).push(tokens);
+      if (!self[token]) {
+        self[token] = [];
+        self[token].processed = 0;
+      }
+      self[token].push(tokens);
     });
   },
   createSorter: function() {
     var self = this;
-    var sorter = new Sorter(Object.keys(this).sort(function(j, k) {
+    var sorter = new Sorter();
+    sorter.tokens = Object.keys(this).sort(function(j, k) {
       var m = self[j].length;
       var n = self[k].length;
       return m < n ? 1 : m > n ? -1 : j < k ? -1 : j > k ? 1 : 0;
-    }));
-    sorter.tokens.forEach(function(token) {
-      var chain = new TokenChain();
-      self[token].forEach(function(tokens) {
-        var index;
-        while ((index = tokens.indexOf(token)) !== -1) {
-          tokens.splice(index, 1);
-        }
-        chain.add(tokens.slice(0));
-      });
-      sorter[token] = chain.createSorter();
+    }).filter(function(token) {
+      if (self[token].processed < self[token].length) {
+        var chain = new TokenChain();
+        self[token].forEach(function(tokens) {
+          var index;
+          while ((index = tokens.indexOf(token)) !== -1) {
+            tokens.splice(index, 1);
+          }
+          tokens.forEach(function(token) {
+            self[token].processed++;
+          });
+          chain.add(tokens.slice(0));
+        });
+        sorter[token] = chain.createSorter();
+        return true;
+      }
+      return false;
     });
     return sorter;
   }
diff --git a/tests/minifier.js b/tests/minifier.js
index 09a7f17..bc45d12 100644
--- a/tests/minifier.js
+++ b/tests/minifier.js
@@ -2487,6 +2487,9 @@ test('sort attributes', function() {
     ignoreCustomFragments: [/<#[\s\S]*?#>/],
     sortAttributes: true
   }), output);
+
+  input = '<a 0 1 2 3 4 5 6 7 8 9 a b c d e f g h i j k l m n o p q r s t u v w x y z></a>';
+  equal(minify(input, { sortAttributes: true }), input);
 });
 
 test('sort style classes', function() {
@@ -2524,6 +2527,9 @@ test('sort style classes', function() {
     ignoreCustomFragments: [/<#[\s\S]*?#>/],
     sortClassName: true
   }), output);
+
+  input = '<a class="0 1 2 3 4 5 6 7 8 9 a b c d e f g h i j k l m n o p q r s t u v w x y z"></a>';
+  equal(minify(input, { sortClassName: true }), input);
 });
 
 test('decode entity characters', function() {
-- 
2.34.1