revset: fix alias substitution recursion (issue3240)

The revset aliases expansion worked like:

  expr = "some revset"
  for alias in aliases:
      expr = alias.process(expr)

where "process" was replacing the alias with its *unexpanded* substitution,
recursively. So it only worked when aliases were applied in proper dependency
order.

This patch rewrites the expansion process so all aliases are expanded
recursively at every tree level, after parent alias rewriting and variable
expansion.

mercurial/revset.py

@@ -1071,46 +1071,85 b' class revsetalias(object):'
         h = heads(default)
         b($1) = ancestors($1) - ancestors(default)
         '''
-        if isinstance(name, tuple): # parameter substitution
-            self.tree = name
-            self.replacement = value
-        else: # alias definition
             m = self.funcre.search(name)
             if m:
+            self.name = m.group(1)
                 self.tree = ('func', ('symbol', m.group(1)))
                 self.args = [x.strip() for x in m.group(2).split(',')]
                 for arg in self.args:
                     value = value.replace(arg, repr(arg))
             else:
+            self.name = name
                 self.tree = ('symbol', name)
 
             self.replacement, pos = parse(value)
             if pos != len(value):
                 raise error.ParseError(_('invalid token'), pos)
 
-    def process(self, tree):
-        if isinstance(tree, tuple):
-            if self.args is None:
-                if tree == self.tree:
-                    return self.replacement
-            elif tree[:2] == self.tree:
+def _getalias(aliases, tree):
+    """If tree looks like an unexpanded alias, return it. Return None
+    otherwise.
+    """
+    if isinstance(tree, tuple) and tree:
+        if tree[0] == 'symbol' and len(tree) == 2:
+            name = tree[1]
+            alias = aliases.get(name)
+            if alias and alias.args is None and alias.tree == tree:
+                return alias
+        if tree[0] == 'func' and len(tree) > 1:
+            if tree[1][0] == 'symbol' and len(tree[1]) == 2:
+                name = tree[1][1]
+                alias = aliases.get(name)
+                if alias and alias.args is not None and alias.tree == tree[:2]:
+                    return alias
+    return None
+
+def _expandargs(tree, args):
+    """Replace all occurences of ('string', name) with the
+    substitution value of the same name in args, recursively.
+    """
+    if not isinstance(tree, tuple):
+        return tree
+    if len(tree) == 2 and tree[0] == 'string':
+        return args.get(tree[1], tree)
+    return tuple(_expandargs(t, args) for t in tree)
+
+def _expandaliases(aliases, tree, expanding):
+    """Expand aliases in tree, recursively.
+
+    'aliases' is a dictionary mapping user defined aliases to
+    revsetalias objects.
+    """
+    if not isinstance(tree, tuple):
+        # Do not expand raw strings
+        return tree
+    alias = _getalias(aliases, tree)
+    if alias is not None:
+        if alias in expanding:
+            raise error.ParseError(_('infinite expansion of revset alias "%s" '
+                                     'detected') % alias.name)
+        expanding.append(alias)
+        result = alias.replacement
+        if alias.args is not None:
                 l = getlist(tree[2])
-                if len(l) != len(self.args):
+            if len(l) != len(alias.args):
                     raise error.ParseError(
                         _('invalid number of arguments: %s') % len(l))
-                result = self.replacement
-                for a, v in zip(self.args, l):
-                    valalias = revsetalias(('string', a), v)
-                    result = valalias.process(result)
+            result = _expandargs(result, dict(zip(alias.args, l)))
+        # Recurse in place, the base expression may have been rewritten
+        result = _expandaliases(aliases, result, expanding)
+        expanding.pop()
+    else:
+        result = tuple(_expandaliases(aliases, t, expanding)
+                       for t in tree)
                 return result
-            return tuple(map(self.process, tree))
-        return tree
 
 def findaliases(ui, tree):
+    aliases = {}
     for k, v in ui.configitems('revsetalias'):
         alias = revsetalias(k, v)
-        tree = alias.process(tree)
-    return tree
+        aliases[alias.name] = alias
+    return _expandaliases(aliases, tree, [])
 
 parse = parser.parser(tokenize, elements).parse
 

tests/test-revset.t

@@ -430,6 +430,7 b' aliases:'
 
   $ echo '[revsetalias]' >> .hg/hgrc
   $ echo 'm = merge()' >> .hg/hgrc
+  $ echo 'sincem = descendants(m)' >> .hg/hgrc
   $ echo 'd($1) = reverse(sort($1, date))' >> .hg/hgrc
   $ echo 'rs(ARG1, ARG2) = reverse(sort(ARG1, ARG2))' >> .hg/hgrc
   $ echo 'rs4(ARG1, ARGA, ARGB, ARG2) = reverse(sort(ARG1, ARG2))' >> .hg/hgrc
@@ -438,6 +439,46 b' aliases:'
   ('symbol', 'm')
   ('func', ('symbol', 'merge'), None)
   6
+
+test alias recursion
+
+  $ try sincem
+  ('symbol', 'sincem')
+  ('func', ('symbol', 'descendants'), ('func', ('symbol', 'merge'), None))
+  6
+  7
+
+test infinite recursion
+
+  $ echo 'recurse1 = recurse2' >> .hg/hgrc
+  $ echo 'recurse2 = recurse1' >> .hg/hgrc
+  $ try recurse1
+  ('symbol', 'recurse1')
+  hg: parse error: infinite expansion of revset alias "recurse1" detected
+  [255]
+
+test nesting and variable passing
+
+  $ echo 'nested($1) = nested2($1)' >> .hg/hgrc
+  $ echo 'nested2($1) = nested3($1)' >> .hg/hgrc
+  $ echo 'nested3($1) = max($1)' >> .hg/hgrc
+  $ try 'nested(2:5)'
+  ('func', ('symbol', 'nested'), ('range', ('symbol', '2'), ('symbol', '5')))
+  ('func', ('symbol', 'max'), ('range', ('symbol', '2'), ('symbol', '5')))
+  5
+
+test variable isolation, variable placeholders are rewritten as string
+then parsed and matched again as string. Check they do not leak too
+far away.
+
+  $ echo 'injectparamasstring = max("$1")' >> .hg/hgrc
+  $ echo 'callinjection($1) = descendants(injectparamasstring)' >> .hg/hgrc
+  $ try 'callinjection(2:5)'
+  ('func', ('symbol', 'callinjection'), ('range', ('symbol', '2'), ('symbol', '5')))
+  ('func', ('symbol', 'descendants'), ('func', ('symbol', 'max'), ('string', '$1')))
+  abort: unknown revision '$1'!
+  [255]
+
   $ try 'd(2:5)'
   ('func', ('symbol', 'd'), ('range', ('symbol', '2'), ('symbol', '5')))
   ('func', ('symbol', 'reverse'), ('func', ('symbol', 'sort'), ('list', ('range', ('symbol', '2'), ('symbol', '5')), ('symbol', 'date'))))