rewriter: Sort source files (#5010)

* rewriter: Sort source files

* rewriter: Natural sorting

* rewriter: Fix flake8

* rewriter: Fixed sorting

* rewriter: Make sorting key more readable

* rewriter: Even simpler key

4 files changed, 114 insertions, 19 deletions

diff --git a/mesonbuild/rewriter.py b/mesonbuild/rewriter.py
index c997434..2619aae 100644
--- a/mesonbuild/rewriter.py
+++ b/mesonbuild/rewriter.py
@@ -565,6 +565,8 @@ class Rewriter:
                 args = n.arguments
             return args
 
+        to_sort_nodes = []
+
         if cmd['operation'] == 'src_add':
             node = None
             if target['sources']:
@@ -592,14 +594,17 @@ class Rewriter:
                 to_append += [StringNode(token)]
 
             # Append to the AST at the right place
-            if isinstance(node, FunctionNode):
-                node.args.arguments += to_append
-            elif isinstance(node, ArrayNode):
-                node.args.arguments += to_append
+            arg_node = None
+            if isinstance(node, (FunctionNode, ArrayNode)):
+                arg_node = node.args
             elif isinstance(node, ArgumentNode):
-                node.arguments += to_append
+                arg_node = node
+            assert(arg_node is not None)
+            arg_node.arguments += to_append
 
             # Mark the node as modified
+            if arg_node not in to_sort_nodes and not isinstance(node, FunctionNode):
+                to_sort_nodes += [arg_node]
             if node not in self.modefied_nodes:
                 self.modefied_nodes += [node]
 
@@ -622,11 +627,9 @@ class Rewriter:
 
                 # Remove the found string node from the argument list
                 arg_node = None
-                if isinstance(root, FunctionNode):
-                    arg_node = root.args
-                if isinstance(root, ArrayNode):
+                if isinstance(root, (FunctionNode, ArrayNode)):
                     arg_node = root.args
-                if isinstance(root, ArgumentNode):
+                elif isinstance(root, ArgumentNode):
                     arg_node = root
                 assert(arg_node is not None)
                 mlog.log('  -- Removing source', mlog.green(i), 'from',
@@ -634,6 +637,8 @@ class Rewriter:
                 arg_node.arguments.remove(string_node)
 
                 # Mark the node as modified
+                if arg_node not in to_sort_nodes and not isinstance(root, FunctionNode):
+                    to_sort_nodes += [arg_node]
                 if root not in self.modefied_nodes:
                     self.modefied_nodes += [root]
 
@@ -685,6 +690,17 @@ class Rewriter:
             }
             self.add_info('target', target['id'], test_data)
 
+        # Sort files
+        for i in to_sort_nodes:
+            convert = lambda text: int(text) if text.isdigit() else text.lower()
+            alphanum_key = lambda key: [convert(c) for c in re.split('([0-9]+)', key)]
+            path_sorter = lambda key: ([(key.count('/') <= idx, alphanum_key(x)) for idx, x in enumerate(key.split('/'))])
+
+            unknown = [x for x in i.arguments if not isinstance(x, StringNode)]
+            sources = [x for x in i.arguments if isinstance(x, StringNode)]
+            sources = sorted(sources, key=lambda x: path_sorter(x.value))
+            i.arguments = unknown + sources
+
     def process(self, cmd):
         if 'type' not in cmd:
             raise RewriterException('Command has no key "type"')
diff --git a/run_unittests.py b/run_unittests.py
index c1337a3..90a726b 100755
--- a/run_unittests.py
+++ b/run_unittests.py
@@ -5242,16 +5242,16 @@ class RewriterTests(BasePlatformTests):
         out = self.extract_test_data(out)
         expected = {
             'target': {
-                'trivialprog0@exe': {'name': 'trivialprog0', 'sources': ['main.cpp', 'fileA.cpp', 'a1.cpp', 'a2.cpp', 'a6.cpp', 'fileB.cpp', 'fileC.cpp', 'a7.cpp']},
-                'trivialprog1@exe': {'name': 'trivialprog1', 'sources': ['main.cpp', 'fileA.cpp', 'a1.cpp', 'a2.cpp', 'a6.cpp']},
-                'trivialprog2@exe': {'name': 'trivialprog2', 'sources': ['fileB.cpp', 'fileC.cpp', 'a7.cpp']},
-                'trivialprog3@exe': {'name': 'trivialprog3', 'sources': ['main.cpp', 'fileA.cpp', 'a5.cpp']},
-                'trivialprog4@exe': {'name': 'trivialprog4', 'sources': ['main.cpp', 'a5.cpp', 'fileA.cpp']},
-                'trivialprog5@exe': {'name': 'trivialprog5', 'sources': ['main.cpp', 'a3.cpp', 'fileB.cpp', 'fileC.cpp', 'a7.cpp']},
+                'trivialprog0@exe': {'name': 'trivialprog0', 'sources': ['a1.cpp', 'a2.cpp', 'a6.cpp', 'fileA.cpp', 'main.cpp', 'a7.cpp', 'fileB.cpp', 'fileC.cpp']},
+                'trivialprog1@exe': {'name': 'trivialprog1', 'sources': ['a1.cpp', 'a2.cpp', 'a6.cpp', 'fileA.cpp', 'main.cpp']},
+                'trivialprog2@exe': {'name': 'trivialprog2', 'sources': ['a7.cpp', 'fileB.cpp', 'fileC.cpp']},
+                'trivialprog3@exe': {'name': 'trivialprog3', 'sources': ['a5.cpp', 'fileA.cpp', 'main.cpp']},
+                'trivialprog4@exe': {'name': 'trivialprog4', 'sources': ['a5.cpp', 'main.cpp', 'fileA.cpp']},
+                'trivialprog5@exe': {'name': 'trivialprog5', 'sources': ['a3.cpp', 'main.cpp', 'a7.cpp', 'fileB.cpp', 'fileC.cpp']},
                 'trivialprog6@exe': {'name': 'trivialprog6', 'sources': ['main.cpp', 'fileA.cpp', 'a4.cpp']},
-                'trivialprog7@exe': {'name': 'trivialprog7', 'sources': ['fileB.cpp', 'fileC.cpp', 'main.cpp', 'fileA.cpp', 'a1.cpp', 'a2.cpp', 'a6.cpp']},
-                'trivialprog8@exe': {'name': 'trivialprog8', 'sources': ['main.cpp', 'fileA.cpp', 'a1.cpp', 'a2.cpp', 'a6.cpp']},
-                'trivialprog9@exe': {'name': 'trivialprog9', 'sources': ['main.cpp', 'fileA.cpp', 'a1.cpp', 'a2.cpp', 'a6.cpp']},
+                'trivialprog7@exe': {'name': 'trivialprog7', 'sources': ['fileB.cpp', 'fileC.cpp', 'a1.cpp', 'a2.cpp', 'a6.cpp', 'fileA.cpp', 'main.cpp']},
+                'trivialprog8@exe': {'name': 'trivialprog8', 'sources': ['a1.cpp', 'a2.cpp', 'a6.cpp', 'fileA.cpp', 'main.cpp']},
+                'trivialprog9@exe': {'name': 'trivialprog9', 'sources': ['a1.cpp', 'a2.cpp', 'a6.cpp', 'fileA.cpp', 'main.cpp']},
             }
         }
         self.assertDictEqual(out, expected)
@@ -5355,6 +5355,52 @@ class RewriterTests(BasePlatformTests):
         expected = {'name': 'something', 'sources': ['first.c', 'second.c']}
         self.assertDictEqual(out['target']['94b671c@@something@exe'], expected)
 
+    def test_target_source_sorting(self):
+        self.prime('5 sorting')
+        add_json = json.dumps([{'type': 'target', 'target': 'exe1', 'operation': 'src_add', 'sources': ['a666.c']}])
+        inf_json = json.dumps([{'type': 'target', 'target': 'exe1', 'operation': 'info'}])
+        out = self.rewrite(self.builddir, add_json)
+        out = self.rewrite(self.builddir, inf_json)
+        out = self.extract_test_data(out)
+        expected = {
+            'target': {
+                'exe1@exe': {
+                    'name': 'exe1',
+                    'sources': [
+                        'aaa/a/a1.c',
+                        'aaa/b/b1.c',
+                        'aaa/b/b2.c',
+                        'aaa/f1.c',
+                        'aaa/f2.c',
+                        'aaa/f3.c',
+                        'bbb/a/b1.c',
+                        'bbb/b/b2.c',
+                        'bbb/c1/b5.c',
+                        'bbb/c2/b7.c',
+                        'bbb/c10/b6.c',
+                        'bbb/a4.c',
+                        'bbb/b3.c',
+                        'bbb/b4.c',
+                        'bbb/b5.c',
+                        'a1.c',
+                        'a2.c',
+                        'a3.c',
+                        'a10.c',
+                        'a20.c',
+                        'a30.c',
+                        'a100.c',
+                        'a101.c',
+                        'a110.c',
+                        'a210.c',
+                        'a666.c',
+                        'b1.c',
+                        'c2.c'
+                    ]
+                }
+            }
+        }
+        self.assertDictEqual(out, expected)
+
     def test_kwargs_info(self):
         self.prime('3 kwargs')
         out = self.rewrite(self.builddir, os.path.join(self.builddir, 'info.json'))
diff --git a/test cases/rewrite/1 basic/addSrc.json b/test cases/rewrite/1 basic/addSrc.json
index 1a8630f..b8bc439 100644
--- a/test cases/rewrite/1 basic/addSrc.json
+++ b/test cases/rewrite/1 basic/addSrc.json
@@ -3,7 +3,7 @@
     "type": "target",
     "target": "trivialprog1",
     "operation": "src_add",
-    "sources": ["a1.cpp", "a2.cpp", "a1.cpp"]
+    "sources": ["a2.cpp", "a1.cpp", "a2.cpp"]
   },
   {
     "type": "target",
diff --git a/test cases/rewrite/5 sorting/meson.build b/test cases/rewrite/5 sorting/meson.build
new file mode 100644
index 0000000..80934a0
--- /dev/null
+++ b/test cases/rewrite/5 sorting/meson.build
@@ -0,0 +1,33 @@
+project('rewriter source sorting', ['c', 'cpp'])
+
+src1 = files([
+  'a1.c',
+  'a10.c',
+  'a2.c',
+  'a3.c',
+  'bbb/a/b1.c',
+  'bbb/a4.c',
+  'bbb/b3.c',
+  'bbb/b4.c',
+  'bbb/b/b2.c',
+  'bbb/c1/b5.c',
+  'bbb/c10/b6.c',
+  'bbb/c2/b7.c',
+  'bbb/b5.c',
+  'a110.c',
+  'aaa/f1.c',
+  'aaa/f2.c',
+  'aaa/f3.c',
+  'a20.c',
+  'b1.c',
+  'aaa/b/b1.c',
+  'aaa/b/b2.c',
+  'a30.c',
+  'a100.c',
+  'aaa/a/a1.c',
+  'a101.c',
+  'a210.c',
+  'c2.c'
+])
+
+exe1 = executable('exe1', src1)