From d1b3ad7b302d037c8154bab9c4810d499c0bf1e4 Mon Sep 17 00:00:00 2001
From: Boris Kolpackov <boris@codesynthesis.com>
Date: Thu, 14 Mar 2019 17:19:01 +0200
Subject: Change variable::override list order, make doubly-linked

---
 build2/context.cxx  | 36 +++++++++++++++++++++++++++---------
 build2/scope.cxx    | 15 +++++++++++----
 build2/variable.hxx | 14 ++++++++++----
 3 files changed, 48 insertions(+), 17 deletions(-)

diff --git a/build2/context.cxx b/build2/context.cxx
index 7b473e20..633f3ff6 100644
--- a/build2/context.cxx
+++ b/build2/context.cxx
@@ -682,27 +682,45 @@ namespace build2
                              c == '%' ? variable_visibility::project :
                              variable_visibility::normal);
 
-      const variable& var (vp.insert (n, true)); // Allow overrides.
+      variable& var (const_cast<variable&> (
+                       vp.insert (n, true /* overridable */)));
       const char* k (tt == token_type::assign ? ".__override" :
                      tt == token_type::append ? ".__suffix" : ".__prefix");
 
       // We might already have a variable for this kind of override.
       //
-      const variable* o (&var); // Step behind.
-      for (; o->override != nullptr; o = o->override.get ())
+      const variable* o (var.override.get ());
+      for (; o != nullptr; o = o->override.get ())
       {
-        if (o->override->visibility == v &&
-            o->override->name.rfind (k) != string::npos)
+        if (o->visibility == v && o->name.rfind (k) != string::npos)
           break;
       }
 
       // Add it if not found.
       //
-      if (o->override == nullptr)
-        const_cast<variable*> (o)->override.reset (
-          new variable {n + k, nullptr , nullptr, nullptr, v});
+      if (o == nullptr)
+      {
+        unique_ptr<variable> p (
+          new variable {
+            n + k,
+            nullptr /* alias    */,
+            nullptr /* type     */,
+            nullptr /* override */,
+            v});
+
+        // Back link.
+        //
+        p->alias = p.get ();
+        if (var.override != nullptr)
+          swap (p->alias, const_cast<variable*> (var.override.get ())->alias);
 
-      o = o->override.get ();
+        // Forward link.
+        //
+        p->override = move (var.override);
+        var.override = move (p);
+
+        o = var.override.get ();
+      }
 
       // Currently we expand project overrides in the global scope to keep
       // things simple. Pass original variable for diagnostics. Use current
diff --git a/build2/scope.cxx b/build2/scope.cxx
index 69ab4b64..4dd475dc 100644
--- a/build2/scope.cxx
+++ b/build2/scope.cxx
@@ -397,6 +397,9 @@ namespace build2
 
       // Then look for an __override that applies.
       //
+      // Note that the override list is in the reverse order of appearance and
+      // so we will naturally see the most recent override first.
+      //
       for (const variable* o (var.override.get ());
            o != nullptr;
            o = o->override.get ())
@@ -488,14 +491,18 @@ namespace build2
     {
       ++ovr_depth;
 
-      // Skip any append/prepend overrides that appear before __override,
-      // provided it is from this scope.
+      // The override list is in the reverse order of appearance so we need to
+      // iterate backwards in order to apply things in the correct order.
+      //
+      // We also need to skip any append/prepend overrides that appear before
+      // __override (in the command line order), provided it is from this
+      // scope.
       //
       bool skip (stem_ovr != nullptr && stem_depth == ovr_depth);
 
-      for (const variable* o (var.override.get ());
+      for (const variable* o (var.override->alias); // Last override.
            o != nullptr;
-           o = o->override.get ())
+           o = (o->alias != var.override->alias ? o->alias : nullptr))
       {
         if (skip)
         {
diff --git a/build2/variable.hxx b/build2/variable.hxx
index 51e6eedc..2bdfe30d 100644
--- a/build2/variable.hxx
+++ b/build2/variable.hxx
@@ -149,10 +149,16 @@ namespace build2
   // variable itself).
   //
   // If the variable is overridden on the command line, then override is the
-  // chain of the special override variables. Their names are derived from the
-  // main variable name as <name>.{__override,__prefix,__suffix} and they are
-  // not entered into the var_pool. The override variables only vary in their
-  // names and visibility. Their alias pointer is always NULL.
+  // linked list of the special override variables. Their names are derived
+  // from the main variable name as <name>.{__override,__prefix,__suffix} and
+  // they are not entered into the var_pool. The override variables only vary
+  // in their names and visibility. Their alias pointer is re-purposed to make
+  // the list doubly-linked with the first override's alias pointing to the
+  // last element (or itself).
+  //
+  // Note that the override list is in the reverse order of the overrides
+  // appearing on the command line, which is important when deciding whether
+  // and in what order they apply (see find_override() for details).
   //
   // Note also that we don't propagate the variable type to override variables
   // and we keep override values as untyped names. They get "typed" when they
-- 
cgit