• 
  
    
 
    
 
    

    



    
    
    
    
     
    




    
 
    

  
    



    
 

 

  

  

 

    


  
    





    
 
    



  

    
 
 
    
  
    Buffer incoming opcodes and the filtered interdiff opcodes.
    
 
    

    



 
    
 
    

  Review Request #15202
  —
  Created July 29, 2026 and updated 

 
    


    




    




    






 
    
  
    
   Information

  
    



    
 
 
    
  chipx86
 
    

    





    
 
 
    
  Review Board
 
    

    





    
 
 
    
  release-8.x
 
    

    





    
 
 
    
  
 
    

    





    
 
 
    
  15204
 
    

    





    
 
 
    
  15206
 
    

    



 
    



 
    
  
    
   Reviewers

  
    



    
 
 
    
  reviewboard
 
    

    





    
 
 
    
  
 
    

    



 
    



    


    
 
    




  

    
 
 
    
  
    The existing interdiff filtering algorithm tracks a single pending
    
opcode to process the next iteration, and yields filtered-equal
    
opcodes as they're calculated.
    

    In preparation for some additional work on the algorithm that will
    
require opcode backtracking, this change switches to a
    
DiffOpcodeBuffer, which provides peek, consume, and queue operations
    
for the opcodes. This replaces the old pending_opcode, simplifies the
    
opcode loop, and gives us some look-ahead features we'll be using.
    

    filtered-equal opcodes are no longer yielded as they're calculated.
    
Instead, they're added to a list, which tracks the original tag for
    
processing (in the upcoming algorithm changes). When it's time to yield
    
an opcode, it will first flush the filtered opcodes, turning them into
    
filtered-equal as they're yielded, and once that's flushed the new
    
non-filtered opcode will be yielded.
    

    At the moment, this doesn't change anything about the processing of
    
interdiffs. The upcoming changes will take advantage of this to
    
backtrack and buffer opcodes through some new heuristics.
    
 
    

    





  

    
 
 
    
  
    Unit tests pass.
    
 
    

    




 
    

    





    
 
    




  
    
 
 
    
  


    
 
    
  
   
    

    Summary
    ID

   
    
      
  

   
    

    

     
    
      Buffer incoming opcodes and the filtered interdiff opcodes.
      
    The existing interdiff filtering algorithm tracks a single pending
opcode to process the next iteration, and yields `filtered-equal`
opcodes as they're calculated.

In preparation for some additional work on the algorithm that will
require opcode backtracking, this change switches to a
`DiffOpcodeBuffer`, which provides peek, consume, and queue operations
for the opcodes. This replaces the old `pending_opcode`, simplifies the
opcode loop, and gives us some look-ahead features we'll be using.

`filtered-equal` opcodes are no longer yielded as they're calculated.
Instead, they're added to a list, which tracks the original tag for
processing (in the upcoming algorithm changes). When it's time to yield
an opcode, it will first flush the filtered opcodes, turning them into
`filtered-equal` as they're yielded, and once that's flushed the new
non-filtered opcode will be yielded.

At the moment, this doesn't change anything about the processing of
interdiffs. The upcoming changes will take advantage of this to
backtrack and buffer opcodes through some new heuristics.
    
     
    

        		
    8f967eee7c4fb49d827f164a5f8f5b07ae06140e

   
    


      
 
    

    
    
 
    

    






 





    
 
 
 
    
  
    
   
    
    
    
     
    
    
    
      
     
    • 
      
     
      • 
     
    • 
      
     
      • 
     
    • 
      
     
      • 
     
    • 
      
     
      • 
     
    • 
      
     
      • 
    
    
   
    
   
    
    
     
    
      Description
      From
      Last Updated
     
    
        
    



     
    
      
       
       
    This needs to be updated--no longer a one-entry buffer.
    
          		
      


david

  david
 

      
      
       
      
     
    



     
    
      
       
       
    On release-9.x we have a DiffOpcode type alias (in differ.py). Can we port that over to use here?
    
          		
      


david

  david
 

      
      
       
      
     
    



     
    
      
       
       
    I feel like this might be cleaner (and potentially more resilient to future re-queuing changes) if we also make filtered_buffer …
    
          		
      


david

  david
 

      
      
       
      
     
    



     
    
      
       
       
    This is out of date. Perhaps something like "One or more opcodes were queued for re-processing. Take the next one, …
    
          		
      


david

  david
 

      
      
       
      
     
    



     
    
      
       
       
    This is emitting a filtered-equal without buffering it. Is that intentional? According to the description, filtered_buffer is supposed to retain …
    
          		
      


david

  david
 

      
      
       
      
     
    



     
    
      
       
       
    'collections.deque' imported but unused Column: 1 Error code: F401
    
          		
      


reviewbot

  reviewbot
 

      
      
       
      
     
    

        
   
    
  
    
 
    

    




 
    

    



  
    
 
    

    


    












    
 




 

    


 













    
 





 
    
  
    
   
    



david




   
    
   
    





    
  
    
 
    


 
    
  
    

   
    

   
    

    
    





  david
 


    
    
    
    
     


      


     
    
    
   
    


  
    
  
    
  
    


      




    1. 
 
      
  
      
   
      
  
      
 
      

 
      
  


      
 
      
 
        

  

 
      


      

 
      

      2. 

















    2. 
 
      
  
  
      
  
 
      
  
      
   
      
    
     
      
      
       reviewboard/diffviewer/processors.py
       


        (Diff revision 1)


       
      
     
      
          
    
     
       
      

     
       
      

     
       
      

     
       
      

     
       
      

          
   
      
  
      
 
      

   
      
    
    




      
 
      
  
  
  

  
  
   Show all issues
  
 
      

      



    
      This needs to be updated--no longer a one-entry buffer.
      
  
      
 
      

 
      
  


      
 
      
 
        

  




      1. 
 
 
        

 

 
        
  
        It got folded into my fix change. I'll backport.
        
 
        

        2. 


 
      


      

 
      

      3. 






    3. 
 
      
  
  
      
  
 
      
  
      
   
      
    
     
      
      
       reviewboard/diffviewer/processors.py
       


        (Diff revision 1)


       
      
     
      
          
    
     
       
      

     
       
      

     
       
      

          
   
      
  
      
 
      

   
      
    
    




      
 
      
  
  
  

  
  
   Show all issues
  
 
      

      



    
      On release-9.x we have a DiffOpcode type alias (in differ.py). Can we port that over to use here?
      
  
      
 
      

 
      
  


      
 
      
 
        

  




      1. 
 
 
        

 

 
        
  
        I was avoiding going down that rabbit hole with the work for 8. I'm going to keep scope minimal here.
        
 
        

        2. 





      2. 
 
 
        

 

 
        
  
        It's just two small definitions, and it'll simplify the merge a lot:
        

        

        #: The potential values for opcode tags.
#:
#: Version Added:
#:     9.0
DiffOpcodeTag: TypeAlias = Literal[
    'delete',
    'equal',
    'filtered-equal',
    'insert',
    'replace',
]


#: The structure used for opcodes.
#:
#: Version Added:
#:     9.0
DiffOpcode: TypeAlias = tuple[
    DiffOpcodeTag,  # tag
    int,  # i1
    int,  # i2
    int,  # j1
    int,  # j2
]

        
 
        

        3. 





      3. 
 
 
        

 

 
        
  
        Moved it to /r/15204/.
        
 
        

        4. 


 
      


      

 
      

      4. 






    4. 
 
      
  
  
      
  
 
      
  
      
   
      
    
     
      
      
       reviewboard/diffviewer/processors.py
       


        (Diff revision 1)


       
      
     
      
          
    
     
       
      

     
       
      

     
       
      

     
       
      

     
       
      

     
       
      

          
   
      
  
      
 
      

   
      
    
    




      
 
      
  
  
  

  
  
   Show all issues
  
 
      

      



    
      I feel like this might be cleaner (and potentially more resilient to future re-queuing changes) if we also make filtered_buffer a deque and drain it instead of yielding all and then clearing. That way if there's ever any writes during a flush, we don't silently discard those entries.
      

      

      pending_opcodes: deque[DiffOpcode] = deque()
filtered_opcodes: deque[DiffOpcode] = deque()
...

def _flush_filtered() -> Iterator[DiffOpcode]:
    while filtered_opcodes:
        _tag, i1, i2, i1, i2 = filtered_opcodes.popleft()

        yield 'filtered-equal', i1, i2, j1, j2

      

      

      That also makes both pending/filtered have the same shape.
      
  
      
 
      

 
      
  


      
 
      
 
        

  




      1. 
 
 
        

 

 
        
  
        A deque is the wrong tool for this job. I want to keep this a list. There is zero possibility of a write during flush (nothing here works that way and fundamentally never can), we should not be mutating on iterate (there's no reason to do so and it's less efficient), and entries may only ever append (anything else corrupts the diff).
        
 
        

        2. 


 
      


      

 
      

      5. 






    5. 
 
      
  
  
      
  
 
      
  
      
   
      
    
     
      
      
       reviewboard/diffviewer/processors.py
       


        (Diff revision 1)


       
      
     
      
          
    
     
       
      

     
       
      

     
       
      

          
   
      
  
      
 
      

   
      
    
    




      
 
      
  
  
  

  
  
   Show all issues
  
 
      

      



    
      This is out of date. Perhaps something like "One or more opcodes were queued for re-processing. Take the next one, in order, before pulling anything new from the generator"?
      
  
      
 
      

 
      
  


      
 
      
 
        

  




      1. 
 
 
        

 

 
        
  
        This was folded into the fix change. I'll backport.
        
 
        

        2. 


 
      


      

 
      

      6. 






    6. 
 
      
  
  
      
  
 
      
  
      
   
      
    
     
      
      
       reviewboard/diffviewer/processors.py
       


        (Diff revision 1)


       
      
     
      
          
    
     
       
      

     
       
      

     
       
      

     
       
      

     
       
      

     
       
      

     
       
      

     
       
      

          
   
      
  
      
 
      

   
      
    
    




      
 
      
  
  
  

  
  
   Show all issues
  
 
      

      



    
      This is emitting a filtered-equal without buffering it. Is that intentional?
      

      According to the description, filtered_buffer is supposed to retain the original tag of filtered opcodes. This one emits directly, losing the original tag, so this opcode is invisible to any future backtracking.
      

      If Phase 1 are never candidates for reconsideration, we should have a comment, because otherwise there's a weird asymmetry with Phase 2's "Queue it as a filtered-equal" step.
      
  
      
 
      

 
      
  


      
 
      
 
        

  




      1. 
 
 
        

 

 
        
  
        I'll look into this. I had wanted to yield the filtered-equal immediately here since we're completing a batch before re-processing the split op, but I'll see if that's necessary.
        
 
        

        2. 


 
      


      

 
      

      7. 




    7. 
 
      
  
      
   
      
  
      
 
      

 
      
  


      
 
      
 
        

  

 
      


      

 
      

      8. 


    

  
    
 
    

    












    
 



 
    
  
    
   
    



chipx86




   
    
   
    
  
    
 
    


 
    
  
    

   
    

   
    

    
    
Review request changed
    
    
    
    
     


      


     
    
    
   
    


  
    
  
    
  
    




    



  
    
   
    
    Change Summary:
   
    
   
    
    
    Reworked this to use the new DiffOpcodeBuffer.
    
   
    
  
    







  
    
   
    
    Summary:
   
    
   
    
    
    Buffer filtered interdiff opcodes and add a queue of pending opcodes.
    Buffer incoming opcodes and the filtered interdiff opcodes.
    
   
    
  
    




  
    
   
    
    Description:
   
    
   
    
    
         
    The existing interdiff filtering algorithm tracks a single pending
         opcode to process the next iteration, and yields filtered-equal
         opcodes as they're calculated.
         

         
    In preparation for some additional work on the algorithm that will
     ~   require opcode backtracking, this change switches the pending opcodes to
     ~   a deque and adds a buffer for filtered opcodes.
     ~   

     ~   
    The pending_opcodes queue may contain zero or more opcodes to process.
       ~ require opcode backtracking, this change switches to a
       ~ DiffOpcodeBuffer, which provides peek, consume, and queue operations
       ~ for the opcodes. This replaces the old pending_opcode, simplifies the
       ~ opcode loop, and gives us some look-ahead features we'll be using.
     -   If populated, they will always be used over pulling from the provided
     -   opcodes generator. While in the current algorithm this will only ever
     -   have a max of one, the upcoming changes will re-queue opcodes for
     -   processing at times.
         

         
    filtered-equal opcodes are no longer yielded as they're calculated.
     ~   Instead, they're added to a buffer, which tracks the original tag for
       ~ Instead, they're added to a list, which tracks the original tag for
         processing (in the upcoming algorithm changes). When it's time to yield
     ~   an opcode, it will first yield anything in the buffer, turning them into
     ~   filtered-equal opcodes as they're yielded.
       ~ an opcode, it will first flush the filtered opcodes, turning them into
       ~ filtered-equal as they're yielded, and once that's flushed the new
       + non-filtered opcode will be yielded.
         

         
    At the moment, this doesn't change anything about the processing of
         interdiffs. The upcoming changes will take advantage of this to
         backtrack and buffer opcodes through some new heuristics.
    
   
    
  
    




  
    
   
    
    Commits:
   
    
   
    
    
    



    
 
    
  
   
    

    

    Summary
    ID

   
    
      
  

   
    

    

    

     
    
      Buffer filtered interdiff opcodes and add a queue of pending opcodes.
      
    The existing interdiff filtering algorithm tracks a single pending
opcode to process the next iteration, and yields `filtered-equal`
opcodes as they're calculated.

In preparation for some additional work on the algorithm that will
require opcode backtracking, this change switches the pending opcodes to
a `deque` and adds a buffer for filtered opcodes.

The `pending_opcodes` queue may contain zero or more opcodes to process.
If populated, they will always be used over pulling from the provided
opcodes generator. While in the current algorithm this will only ever
have a max of one, the upcoming changes will re-queue opcodes for
processing at times.

`filtered-equal` opcodes are no longer yielded as they're calculated.
Instead, they're added to a buffer, which tracks the original tag for
processing (in the upcoming algorithm changes). When it's time to yield
an opcode, it will first yield anything in the buffer, turning them into
`filtered-equal` opcodes as they're yielded.

At the moment, this doesn't change anything about the processing of
interdiffs. The upcoming changes will take advantage of this to
backtrack and buffer opcodes through some new heuristics.
    
     
    

        		
    38f55153a34169f7598ed6d3ec4873f4d983406e

   
    



   
    

    

    

     
    
      Buffer incoming opcodes and the filtered interdiff opcodes.
      
    The existing interdiff filtering algorithm tracks a single pending
opcode to process the next iteration, and yields `filtered-equal`
opcodes as they're calculated.

In preparation for some additional work on the algorithm that will
require opcode backtracking, this change switches to a
`DiffOpcodeBuffer`, which provides peek, consume, and queue operations
for the opcodes. This replaces the old `pending_opcode`, simplifies the
opcode loop, and gives us some look-ahead features we'll be using.

`filtered-equal` opcodes are no longer yielded as they're calculated.
Instead, they're added to a list, which tracks the original tag for
processing (in the upcoming algorithm changes). When it's time to yield
an opcode, it will first flush the filtered opcodes, turning them into
`filtered-equal` as they're yielded, and once that's flushed the new
non-filtered opcode will be yielded.

At the moment, this doesn't change anything about the processing of
interdiffs. The upcoming changes will take advantage of this to
backtrack and buffer opcodes through some new heuristics.
    
     
    

        		
    3956148e2ac06cb8f7f37a2c9779abfc5b2f2fb9

   
    


      
 
    

    


    

   
    
  
    




  
    
   
    
    Depends On:
   
    
   
    
    
    15204 - Add DiffOpcodeBuffer for peeking and mutating an opcode buffer stream.
    
   
    
  
    




  
    
   
    
    Diff:
   
    
   
    
    
     Revision 2 (+74 -66)
    Show changes
     
        reviewboard/diffviewer/processors.py 
     
    
   
    
  
    





    



    
 
    
  
    Checks run (1 failed, 1 succeeded)
    


  
    
 flake8
 failed.
 


    


  
    
 JSHint
 passed.
 


    


 
    





    
 
    flake8
    
 
    

 

    








    




  
    
 
    

    












    
 



 
    
  
    
   
    



chipx86




   
    
   
    
  
    
 
    


 
    
  
    

   
    

   
    

    
    
Review request changed
    
    
    
    
     


      


     
    
    
   
    


  
    
  
    
  
    




    



  
    
   
    
    Change Summary:
   
    
   
    
    
      

    • Removed an unused import.
      • 

    • Changed an immediate filtered-equal yield to a buffer.
      • 

    
   
    
  
    







  
    
   
    
    Commits:
   
    
   
    
    
    



    
 
    
  
   
    

    

    Summary
    ID

   
    
      
  

   
    

    

    

     
    
      Buffer incoming opcodes and the filtered interdiff opcodes.
      
    The existing interdiff filtering algorithm tracks a single pending
opcode to process the next iteration, and yields `filtered-equal`
opcodes as they're calculated.

In preparation for some additional work on the algorithm that will
require opcode backtracking, this change switches to a
`DiffOpcodeBuffer`, which provides peek, consume, and queue operations
for the opcodes. This replaces the old `pending_opcode`, simplifies the
opcode loop, and gives us some look-ahead features we'll be using.

`filtered-equal` opcodes are no longer yielded as they're calculated.
Instead, they're added to a list, which tracks the original tag for
processing (in the upcoming algorithm changes). When it's time to yield
an opcode, it will first flush the filtered opcodes, turning them into
`filtered-equal` as they're yielded, and once that's flushed the new
non-filtered opcode will be yielded.

At the moment, this doesn't change anything about the processing of
interdiffs. The upcoming changes will take advantage of this to
backtrack and buffer opcodes through some new heuristics.
    
     
    

        		
    3956148e2ac06cb8f7f37a2c9779abfc5b2f2fb9

   
    



   
    

    

    

     
    
      Buffer incoming opcodes and the filtered interdiff opcodes.
      
    The existing interdiff filtering algorithm tracks a single pending
opcode to process the next iteration, and yields `filtered-equal`
opcodes as they're calculated.

In preparation for some additional work on the algorithm that will
require opcode backtracking, this change switches to a
`DiffOpcodeBuffer`, which provides peek, consume, and queue operations
for the opcodes. This replaces the old `pending_opcode`, simplifies the
opcode loop, and gives us some look-ahead features we'll be using.

`filtered-equal` opcodes are no longer yielded as they're calculated.
Instead, they're added to a list, which tracks the original tag for
processing (in the upcoming algorithm changes). When it's time to yield
an opcode, it will first flush the filtered opcodes, turning them into
`filtered-equal` as they're yielded, and once that's flushed the new
non-filtered opcode will be yielded.

At the moment, this doesn't change anything about the processing of
interdiffs. The upcoming changes will take advantage of this to
backtrack and buffer opcodes through some new heuristics.
    
     
    

        		
    8f967eee7c4fb49d827f164a5f8f5b07ae06140e

   
    


      
 
    

    


    

   
    
  
    




  
    
   
    
    Diff:
   
    
   
    
    
     Revision 3 (+80 -74)
    Show changes
     
        reviewboard/diffviewer/processors.py 
     
    
   
    
  
    





    



    
 
    
  
    Checks run (2 succeeded)
    


  
    
 flake8
 passed.
 


    


  
    
 JSHint
 passed.
 


    


 
    









    




  
    
 
    

    












    
 





 
    
  
    
   
    



david




   
    
   
    





    
  
    
 
    


 
    
  
    

   
    

   
    

    
    





  david
 


    
    
    
    
     


      


     
    
    
   
    


  
    
  
    
  
    


      




    1. 
 
      
  
      
   
      Ship It!
      
  
      
 
      

 
      
  


      
 
      
 
        

  

 
      


      

 
      

      2. 















    2. 
 
      
  
      
   
      
  
      
 
      

 
      
  


      
 
      
 
        

  

 
      


      

 
      

      3.