What are the conditions under which a browser will re-assess and reapply CSS selectors and styles?

That really depends on what you call "restyling".

Here it seems you are only talking about recalculating all the styles applied by all the stylesheets in the document, which is also known as "reflow" or "layout".

Any change to the DOM will mark the CSSOM as dirty, and before the time of rendering, the browser will perform such a reflow if the CSSOM is dirty.
Note that some operations, (most being referenced in this gist by Paul Irish), will force a synchronous reflow, because they do require that an up-to-date boxing model is calculated to return the correct values, or to act correctly. So one must be careful when doing DOM changes in a loop to not also force such a synchronous reflow and let the browser do it at the best time, (generally just before the next paint, but in some browsers it's also done at idle).

However this reflow may not cost much, browser may very well have enough optimizations to know what could have changed and go only through these. Moreover, these don't include the repaint operation, which will only happen at the next screen refresh.

But this is not the only time the browser needs to recalculate the boxes layout, for instance every time the page is resized, or even if an in-flow element's size changes as part of an animation etc. but here, the full stylesheets are not recomputed.

There is not really a place in the specs where it is defined what should trigger these operations, nor even when they should occur. The HTML specification only asks that the browser performs the "rendering steps" of the event-loop, which does end with a quite underspecified "update the rendering or user interface of that Document". The ResizeObserver API does extend the rendering step to include styles recalc and layout update but they don't go as far as defining these steps. Note that there is an open issue on the HTML specs to define it more clearly, but for the time being we don't even have browser interoperability.

CSS3 is a series of separate specifications covering individual topics but includes CSS2 within the official definition of CSS.

CSS2 definitions define rendered content as (the emphasis mine)

The content of an element after the rendering that applies to it according to the relevant style sheets has been applied. How a replaced element's content is rendered is not defined by this specification. Rendered content may also be alternate text for an element (e.g., the value of the XHTML "alt" attribute), and may include items inserted implicitly or explicitly by the style sheet, such as bullets, numbering, etc.

I take this to mean that when a document or part thereof is rendered, the browser is responsible for ensuring that CSS rules are correctly applied according to the content rendered, with DOM content and CSS rules specifiying the logical requirements of the rendering and the browser ensuring it produces page layout in conformance with the logical model.

My experience is that browsers will update the DOM when vanilla JavaScript¹ code adds, moves or removes elements in the DOM, and also when changes to style sheet content or element style attributes are updated in script. Changes in the DOM appear to take place synchronously when modifying element placement or styling rules: getting the bounding rectangles of elements in the DOM whose styling or location in the DOM has been modified does not require browses to render the content first.

Hence you're basic assumptions about what you can rely on are essentially correct apart from the wording

reviewed for restyling

There is no active "review" taking place - excepting that modifying some properties can trigger a automatic and synchronous reflow operation in order for the calling script to have synchronous access to DOM property values that would need a reflow to calculate.

• If you change the position of an element in the DOM, it's position has been changed upon return from the method used to change it's position.

• If you add, delete or modify an attribute of an element (in the DOM), changes to the attribute and any side effects produced will have been put into effect upon return from the method used to make the change.

• If you add, delete or modify style sheet rules, changes are effective in results returned from DOM inspection after the method used to change the style sheet returns.

There is a hint of this in the MDN article on `Window.getCommputedStyle. Overall I don't think it's mentioned anywhere specifically because it's inherent in the behavior of the DOM. You only get to know about it when a) you need to use the results of changes synchronously and b) are curious as to why it works as you hoped it would! :)

Examples showing synchronous results:

Changing element location in the DOM, style attribute changes:

setTimeout( ()=> {
  const [div1, div2] = Array.from(document.querySelectorAll('div'));
  div2.appendChild(div1);
  div1.style.backgroundColor = "yellow";
  div1.style.textAlign = "center";
  const rect = div1.getBoundingClientRect();
  const style = getComputedStyle(div1);
  console.log("Synchronous results for div1: ",
    {top: rect.top, backgroundColor: style.backgroundColor});
}, 3000);
  

<div>Division 1</div>
<div>Division 2</div>
... please wait 3 seconds

Changing CSS rules in the CSSOM

"use strict";
let div = document.querySelector('div');
let sheet = Array.from(document.styleSheets)
  .find(sheet=> sheet.ownerNode.id == "absDiv");

console.log("div offsetWidth ",  div.offsetWidth); // before

sheet.insertRule("div{ width: 200px;}");

console.log("after width set in CSS: ",  div.offsetWidth);

<style id="absDiv">
div { background-color: yellow; }
</style>
<div>Div element</div>

¹ Vanilla Javascript implicitly excludes cases of shadow DOMs and components. Refer to Kaido's answer for broader treatment.