[postgis-tickets] [PostGIS] #4684: concurrent topology construction routine may result in invalid topology

[PostGIS]

#4684: concurrent topology construction routine may result in invalid topology
-----------------------+-------------------
  Reporter:  laopsahl  |      Owner:  strk
      Type:  defect    |     Status:  new
  Priority:  medium    |  Milestone:
 Component:  topology  |    Version:  3.0.x
Resolution:            |   Keywords:
-----------------------+-------------------

Comment (by strk):

 It looks like my pessimistic approach was not pessimistic enough, as it
 forgot to deal with the hard step of finding:

  - edges of any face that will be affected by the insertion (hard to find)

 Let's consider this simple starting condition:

   - Topology has a single face, bound by a single closed edge
   - A second edge goes around the existing face but is NOT closed

 {{{

              ____
             /    \
            /      \
           /  o     \ E2
          /  / \     \
         /  /   \ E1  \
        /  /     \     \
       /  /  F1   \     \
      /  /         \     \
     /   `---------'      \
    /                 F0   \
   /                        \
   `----o          o--------'
 }}}

 Now, two separate transactions want to add each a new edge. Let's call
 them E3 and E4:

 {{{
              ____
             /    \
            /      \
           /  o     \ E2
          /  / \     \
         /  /   \ E1  \
        /  /     \     \
       /  /  F1   \     \
      /  /         \     \
     /   `---------'      \
    /                 F0   \
   /                        \
   `----o---(E3)---o--------'
        |          |
        `---(E4)---'
 }}}

 Both transactions will want to update E2 labeling and edge linking but
 they will be conflicting.
 Shall E2 be connected to E3 or E4 ? Whichever transaction is committed
 last will decide, leaving effectively the topology in an invalid state.

 Scenarios like the above should be used for testing row-level locking.
 Eventually we might want to implement row-level locking in PostGIS
 Topology core.

 How to solve the above ? We need to ALSO lock E2, but neither E3 nor E4
 overlap any faces bound by E2, so the recipe given before won't catch this
 case.

 E3 intersects E2 though, so that's another thing to check:

  1. Lock all edges intersecting the incoming input line
  2. Lock all faces found on both sides of the above edges
  3. Lock all edges having any of the above faces on their side

 We need manageable data to make this ticket workable so please if you have
 a way use scenarios like this one.

 Note I filed https://github.com/larsop/resolve-overlap-and-gap/issues/16
 to discuss the code you're working on to try these locking strategies.

-- 
Ticket URL: <https://trac.osgeo.org/postgis/ticket/4684#comment:12>
PostGIS <http://trac.osgeo.org/postgis/>
The PostGIS Trac is used for bug, enhancement & task tracking, a user and developer wiki, and a view into the subversion code repository of PostGIS project.